Public-key Cryptosystems
Abstract
In computer communications, cryptography is indispensable for deterring wiretappers andfor detecting unauthorized modiﬁcations. Public-key cryptosystems in particular, make it easy
to manage keys securely, and are widely in use. In order to invent faster and more securepublic-key cryptosystems, we have conducted research on public-key cryptosystems based on
elliptic curves. Our main results are as follows.
Equivalence of Counting the Number of Points on Elliptic Curve over the Ring Znand Factoring n
Elliptic curves and cubic curves can be applied to public-key cryptosystems, and as suchseveral schemes have been proposed [1]. There are two typical elliptic curve cryptosystems:
ElGamal-type schemes and RSA-type schemes. The security of the former schemes is basedon the diﬃculty of solving an elliptic curve discrete logarithm problem modulo a large prime.
However, the security of the latter schemes is based on the diﬃculty of factoring a large composite. RSA-type elliptic curve schemes can be broken if the eavesdropper knows the order ofelliptic curves used, instead of knowing the prime factors of used composites. No relation hadbeen known between these two diﬃculties, 1) the diﬃculty of the obtaining the order of elliptic
curve modulo n, and 2) the diﬃculty of factoring the composite.Recently, we proved that thetwo diﬃculties are computationally equivalent [2]. Accordingly, we proved that factoring a large
composite leads to the obtainment of the elliptic curve order modulo n. Conversely, we provedthat obtaining the elliptic curve order modulo n leads to success in factoring a large composite
n. This result implies that we must carefully design the RSA-type elliptic curve scheme so thatthe eavesdropper cannot obtain the elliptic curve order modulo n. Furthermore, we showed
the relation between factoring a composite and solving the elliptic curve logarithm problem
modulo the composite. As a result, 1) you can factor the composite n if you solve the discrete
logarithm problem modulo n, and 2) you can solve the discrete logarithm problem modulo a
composite n if you factor the composite and solve the discrete logarithm problem modulo aprime. Hence, this results in greater safety standards for public-key cryptosystems.
Security analysis based on diophantine equation for RSA-type cryptosystems
A broadcast message attack against RSA-type cryptosystems was proposed in 1997 [3]. In
this attack, an adversary obtains a diophantine equation from broadcasted ciphertexts and thencomputes the plaintext by solving the equation. However, this attack can be made ineﬀective
by properly choosing the plaintext space. We show another attack based on computing integral
points of elliptic curves [4]. This new attack can be eﬀectively applied when both coeﬃcientsand the rank of the elliptic curve are small. We show that all plaintext that is a torsion pointof elliptic curves is weak against the new attack. We will conduct numerical experiments anda complexity analysis of the new attack algorithm.
(Contact: Yukio Tsuruoka; Email: tsuru@cslab.kecl.ntt.co.jp)[1] Koyama, K.: Fast RSA-type schemes based on singular cubic curves y 2 + axy ≡ x3
(mod n), Advances in Cryptology — EUROCRYPT’95, LNCS 921, pp. 329–340 (1995).
[2] Kunihiro, N. and Koyama, K.: Equivalence of Counting the Number of Points on Elliptic
Curve over the Ring Zn and Factoring n, Advances in Cryptology — EUROCRYPT’98,(1998) (to appear).
[3] Bleichenbacher, D.: On the Security of the KMOV Public Key Cryptosystem, Advances inCryptology — CRYPTO’97, LNCS 1294, pp. 235–248 (1997).
[4] Tsuruoka, Y. and Koyama, K.: Security analysis based on diophantine equation for RSAtype elliptic curve cryptosystems (in Japanese), Proc. of the 1998 Symposium on Cryptography and Information Security, SCIS’98-4.1.E (1998).
cCopyright1998
Nippon Telegraph and Telephone Corporation