Browse Prior Art Database

Look-Ahead Processing for High Speed RSA Cryptographic Key Pair Generation

IP.com Disclosure Number: IPCOM000110787D
Original Publication Date: 1994-Jan-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 157K

Publishing Venue

IBM

Related People

Butter, AS: AUTHOR [+3]

Abstract

Disclosed is a high performance method for generating cryptographic key pairs for the RSA Public Key encryption algorithm.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 44% of the total text.

Look-Ahead Processing for High Speed RSA Cryptographic Key Pair Generation

      Disclosed is a high performance method for generating
cryptographic key pairs for the RSA Public Key encryption algorithm.

      Public Key encryption has become a common method for providing
security for sensitive data.  One of the more popular Public Key
encryption algorithms in use today is RSA [1].  The RSA algorithm is
an exponentiation cipher which uses two different keys to perform the
encipher and decipher transformations.  The key used to encipher data
is called the Public Key because any potential transmitter of secure
data can access this key in a non-secure way (for example, through an
electronic bulletin board).  The key used to decipher data is called
the Private Key, whose value is known only to the receiver.

      The level of data security provided by the RSA scheme is
dependent on the secrecy of the receiver's Private Key.  In order to
increase the level of security offered, it is common practice for the
receiver to periodically update its Public/Private Key pair.
Unfortunately, the amount of time required for the receiver to
generate a RSA Public/Private Key pair is orders of magnitude greater
than that required to perform the encipher and decipher
transformations.  This disclosure describes a method that will
substantially increase the performance of RSA Public/Private Key
generation from the system perspective.

      The procedure for generating a single RSA Public/Private Key
pair is extremely computer-intensive.  The following procedure has
been suggested in the literature [2]:

1.  Select two large (512-bit) prime numbers p and q.

2.  Calculate the modulus n and Phi(n) as follows:

    o   n = pxq

    o   Phi (n) = (p-1)x(q-1)

3.  Select the Private Key d relatively prime to Phi(n).

4.  Derive the Public Key e as follows:

    o   e = inv(d,Phi(n)), where inv denotes the multiplicative
        inverse operator.

      It is suggested that the numbers p, q and d be selected at
random and tested discretely for primality.  In addition, certain
guidelines should be adhered to in selecting p, q, d and e in order
to strengthen the system against outside attacks.  Combined with the
iterative nature of the inv operation, it becomes clear that the
amount of time required to generate RSA Public/Private Key pairs is
substantial.

      In a typical cryptographic system, like the Transaction
Security System [3], the previously outlined procedure is invoked at
the time a RSA Public/Private Key Pair Generation request is
received.  This request-driven processing scheme is illustrated in
Fig. 1 for the first generation request received after hardware
power-on.  Note that the amount of time required to process the RSA
Public/Private Key Pair Generation request is equal to the time it
takes to perform the steps previously outlined for generating RSA
keys plus the time required to return the Publ...