New Key Generation Algorithm for RSA Cryptosystem (Special Section on Cryptography and Information Security)

概要

論文の詳細を見る
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.
社団法人電子情報通信学会の論文
1994-01-25