Abstract
This paper proposes fast RSA-type public-key schemes based on singular cubic curves y 2 + axy = x 3 over the ring Z n. The x and y coordinates of a 2 log n-bit long plaintext/ciphertext are transformed to a log n-bit long shadow plaintext/ciphertext by isomorphic mapping. Decryption is carried out by ex- ponentiating this shorter shadow ciphertext over Z n. The decryption speed of the proposed schemes is about 2.0 times faster than that of the RSA scheme for a K-bit long message if ⌈K/log n⌉ is even. We prove that breaking each of the proposed schemes is computationally equivalent to breaking the RSA scheme in one-to-one communication circumstances. We also prove that the proposed schemes have the same security as the RSA scheme against the Hastad attack when linearly related plaintexts are encrypted in broadcast applications.
Chapter PDF
References
N. Demytko: “A new elliptic curves based analogue of RSA”, Advances in Cryptology-Eurocrypt'93, LNCS 765 pp. 40–49 (1992).
J. Hastad: “On using RSA with low exponent in a public key network”, Advances in Cryptology-Crypto'85, LNCS 218 pp. 403–408 (1985).
D. Husemöller: “Elliptic Curves”, Springer-Verlag (1987).
K. Koyama, U. M. Maurer, T. Okamoto and S. A. Vanstone: “New public-key schemes based on elliptic curves over the ring Z n”, Advances in Cryptology-Crypto'91, LNCS 576 pp. 252–266 (1991).
K. Koyama and Y. Tsuruoka: “A signed binary window method for fast computing over elliptic curves”, Advances in Cryptology-Crypto'92, LNCS 740 pp. 345–357 (1992).
H. Kuwakado and K. Koyama: “On the security of RSA-type cryptosystems over elliptic curves against the Hastad attack”, IEE Electronics Letters, Vol.30, No.22, pp. 1843–1844 (1994).
A. J. Menezes: “Elliptic Curve Public Key Cryptosystems”, Kluwer Academic Publishers (1993).
M. Rabin: “Digital signatures and public-key cryptosystems”, MIT/LCS/TR-21, (1979).
R. L. Rivest, A. Shamir and L. Adleman: “A method for obtaining digital signatures and public-key cryptosystems”, Comm. of the ACM, 21,2, pp. 120–126 (1978).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koyama, K. (1995). Fast RSA-type Schemes Based on Singular Cubic Curves y 2 + axy ≡ x 3 (mod n). In: Guillou, L.C., Quisquater, JJ. (eds) Advances in Cryptology — EUROCRYPT ’95. EUROCRYPT 1995. Lecture Notes in Computer Science, vol 921. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49264-X_27
Download citation
DOI: https://doi.org/10.1007/3-540-49264-X_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59409-3
Online ISBN: 978-3-540-49264-1
eBook Packages: Springer Book Archive