Font Size: 

In 1976, Diffie and Hellman [2] proposed the first public-key exchange protocol for exchanging secret keys over insecure channels. This protocol is not a public-key cryptosystem, but it is the basis for the cryptosystems. In 1978, Rivest, Shamir and Adleman [9] proposed the first practical public-key cryptosystem, now widely known as the RSA public-key cryptosystem. Its security is based on the assumption that it is not so difficult to find two large prime numbers, but it is very difficult to factor a large composite into its prime factorization form. The modulus n of the RSA cryptosystem is the product of two different large primes p and q. The public exponent e and the secret exponent d are related by ed ? 1 (mod (p - 1) (q - 1)).
In 1985, Koblitz [5] and Miller [7] independently proposed new public-key cryptosystems based on elliptic curves. These cryptosystems rely on the difficulty to solve the discrete logarithm problem for elliptic curves.
In 1991, Koyama, Maurer, Okamoto and Vanstone [6] proposed another kind of elliptic curve based cryptosystems. Their shemes are based on the difficulty of factoring large numbers and are similar to RSA. The most practical of these shemes (Type 1) is generally called the KMOV public-key cryptosystem, according to the first letters of the author's names. Public key is (n, e), where n is the product of two different large primes p and q, where p and q are both congruent to 2 mod 3. The number e must be chosen so it is relatively prime to lcm (p + 1, q + 1). The public key number e and the private key number d are related by ed ? 1 (mod lcm (p + 1, q + 1)).
A well-known attack on RSA with small secret exponent d, which is called the Wiener attack, was proposed by Wiener [11] in 1990. He showed that using continued fractions, one can efficiently recover the secret exponent d from public key (n, e) as long as d < n0.25 . In this case d is the denominator of some convergent pm /qm of the continued fraction expansion of e/n.
In 1997, Verheul and van Tilborg [10] extended the boundary of the Wiener attack on RSA. They propose a technique to raise the security boundary of n0.25 with exhaustive-searching for 2t + 8 bits, where t = log2 d - log2 n0.25 . The candidates for the secret exponent d are of the form d = rqm+1 + sqm , for some positive integers r and s.
In 2004, Dujella [3] described a modification of the Verheul and van Tilborg variant of the Wiener attack on RSA. Dujella's modifications of this attack is based on the Worley result on Diophantine approximations [12] of the form |? - a/b| < c/b2 , for a positive real number c. The candidates for the secret exponent d are of the form d = rqm+1 ? sqm , for some nonnegative integers r
and s.
In 1995, Pinch [8] extended the Wiener attack to KMOV cryptosystem.
Here we extend the Dujella variant of the Wiener attack to KMOV cryptosystem. We describe an algorithm for finding secret key d of the form d = rqm+1 ? sqm , for some nonnegative integers r and s. Using results on connection between continued fractions and rational approximations of the form |? - a/b| < c/b2 , for a positive integer c, from Dujella and Ibrahimpa?i? [4] sc and above mentioned results on Diophantine approximations [3, 12], we derive
bounds for r and s.

References
[1] D. Bleichenbacher, On the security of KMOV public-key cryptosystem, Advances in Cryptology - Crypto '97, Lecture Notes in Computer Science, vol. 1294, Springer-Verlag, 1997, 235-248.
[2] W. Diffie, E. Hellman, New directions in cryptographyt, IEEE Transactions on Information Theory, 22(1976), 644-654.
[3] A. Dujella, Continued fractions and RSA with small secret exponent, Tatra Mt. Math. Publ. 29(2004), 101-112.
[4] A. Dujella, B. Ibrahimpa?i?, On Worley's theorem in Diophantine approximations, sc preprint.
[5] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation 48(1987), 203-209.
[6] K. Koyama, U. M. Maurer, T. Okamoto, S. A. Vanstone, New public-key schemes based on elliptic curves over the ring Zn , Advances in Cryptology - Crypto '91, Lecture Notes in Computer Science, vol. 576, Springer-Verlag, 1991, 252-266.
[7] V. S. Miller, Use of elliptic curves in cryptography, Advances in Cryptology - Crypto '85, Lecture Notes in Computer Science, vol. 218, Springer-Verlag, 1986, 417-426.
[8] R. G. E. Pinch, Extending the Wiener attack to RSA-type cryptosystems, Electronics Letters 31(1995), 1736-1738.
[9] R. L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21(1978), 120-126.
[10] E. R. Verheul, H. C. A. van Tilborg, Cryptanalysis of 'less short' RSA secret exponents, Applicable Algebra Engineering Communication and Computing 8(1997), 425-435.
[11] M. J. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Trans. on Information Theory 36(1990), 553-558.
[12] R. T. Worley, Estimating |? - p/q|, Austral. Math. Soc. Ser. A 31(1981), 202-206.