New Key Generation Algorithm for RSA Cryptosystem

Ryuichi SAKAI, Masakatu MORII, Masao KASAHARA

Summary :

For improving the RSA cryptosystem, more desirable conditions on key structures have been intensively studied. Recently, M.J.Wiener presented a cryptanalytic attack on the use of small RSA secret exponents. To be secure against the Wiener's attack, the size of a secret exponent d should be chosen more than one-quarter of the size of the modulus n = pq (in bits). Besides, it is more desirable, in frequent cases, to make the public exponent e as small as possible. However if small d is chosen first, in such case as the digital signature system with smart card, the size of e is inevitably increased to that of n when we use the conventional key generation algorithm. This paper presents a new algorithm, Algorithm I, for generating of the secure RSA keys against Wiener's attack. With Algorithm I, it is possible to choose the smaller sizes of the RSA exponents under certain conditions on key parameters. For example, with Algorithm I, we can construct the RSA keys with the public exponent e of two-thirds and secret exponent d of one-third of the size of modulus n (in bits). Furthermore we present a modified version of Algorithm I, Algorithm II, for generating of the strong RSA keys having the difficulty of factoring n. Finally we analyze the performances of Algorithm I and Algorithm II.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.1 pp.89-97
• Publication Date: 1994/01/25
• Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Authors

Ryuichi SAKAI
Masakatu MORII
Masao KASAHARA

Keyword

cryptography,  public-key cryptosystem,  RSA,  key generation algorithm,  primality test