A new attack on the KMOV cryptosystem
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper, we analyze the security of the KMOV public key cryptosystem. KMOV is based on elliptic curves over the ring Zn where n = pq is the product of two large unknown primes of equal bitsize. We consider KMOV with a public key (n, e) where the exponent e satisfies an equation ex−(p+1)(q+1)y = z, with unknown parameters x, y, z. Using Diophantine approximations and lattice reduction techniques, we show that KMOV is insecure when x, y, z are suitably small.
Abstract
In this paper, we analyze the security of the KMOV public key cryptosystem. KMOV is based on elliptic curves over the ring Zn where n = pq is the product of two large unknown primes of equal bitsize. We consider KMOV with a public key (n, e) where the exponent e satisfies an equation ex−(p+1)(q+1)y = z, with unknown parameters x, y, z. Using Diophantine approximations and lattice reduction techniques, we show that KMOV is insecure when x, y, z are suitably small.
참고문헌 (11)
- J. Bl¨omer, "Public Key Cryptography - PKC 2004", pp.1~13 (2004), Springer-Verlag
- D. Boneh, "Twenty years of attacks on the RSA cryptosystem", Notices Amer. Math. Soc, 46(2), pp.203~213 (1999)
- D. Coppersmith, "Small solutions to polynomial equations, and low exponent RSA vul-nerabilities", J. Cryptology, 10(4), pp.233~260 (1997)
- G. H. Hardy, "An Introduction to the Theory of Numbers" (1975), Oxford University Press
- CRC Cryptography and Network Security, "Cryptanalysis of RSA and its Variants, Chapman & Hall", pp.2010, M. J. Hinek
- B. Ibrahimpaˇsi´c, "Cryptanalysis of KMOV cryptosystem with short secret exponent", Central European Conference on Information and Intelligent Systems (2008)
- K. Koyama, "New public-key schemes based on elliptic curves over the ring Zn, Advances in Cryptology - Crypto’91", Lecture Notes in Computer Science, 576, pp.252~266 (1991), Springer-Verlag
- R. G. E. Pinch, "Extending the Wiener attack to RSA-type cryptosystems", Electronics Letters, 31, pp.1736~1738 (1995)
- R. Rivest, "A method for obtaining digital signatures and public-key cryptosystems", Comm. ACM, 21(2), pp.120~126 (1978)
- J. H. Silverman, "The Arithmetic of Elliptic Curves" (2009), Springer-Verlag
- M. Wiener, "Cryptanalysis of short RSA secret exponents", IEEE Trans. Inform. Theory, 36(3), pp.553~558 (1990)