A New RSA-Type Scheme Based on Singular Cubic Curves y²x³+bx² (mod n)

Hidenori KUWAKADO, Kenji KOYAMA, Yukio TSURUOKA

Summary :

We propose an RSA-type scheme over the nonsingular part of a singular cubic curve En (0,b) : y²x³+bx² (mod n), where n is a product of form-free primes p and q. Our new scheme encrypts/decrypts messages of 2 log n bits by operations of the x and y coordinates. The decryption is carried out over F_p or a subgroup of a quadratic extension of F_p, depending on quadratic residuosity of message-dependent parameter b. The decryption speed in our new scheme is about 4.6 and 5.8 times faster than that in the KMOV scheme and the Demytko scheme, respectively. We prove that if b is a quadratic residue in Z_n, breaking our new scheme over E_n(0,b) is not easier than breaking the RSA scheme.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.1 pp.27-33
• Publication Date: 1995/01/25
• Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Authors

Hidenori KUWAKADO
Kenji KOYAMA
Yukio TSURUOKA

Keyword

cryptography,  RSA cryptosystem,  cubic curve