Method of performing modular inversion

Details Method of performing modular inversion Method of performing modular inversion

2000-10-13

2003-08-19

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06609141

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to a method of performing a modular inversion, especially, though not exclusively, in the context of generating so-called RSA™ public and private key pairs.
BACKGROUND OF THE INVENTION
In the RSA™ cryptographic scheme, an RSA key pair consists of an RSA public key and an RSA private key. Further information regarding the RSA scheme can be found in an article entitled “A Method of Obtaining Digital Signatures and Public Key Cryptosystems” by R. L. Rivest, A. Shamir & L. Adleman, published in Communications of the ACM, Vol 21 (1978), pages 120-126. The public and private keys are generated by some agent and then typically assigned to a particular user. The user makes use of the private key for generating digital signatures and for decrypting messages, and distributes the public key so that other users may verify the signatures generated or encrypt messages to be sent to the user in question. Often, the private key resides on a smart card because this class of device offers both secure storage and secure usage of the key.
It is also becoming increasingly common, because of needs for higher levels of security in some contexts, that there are requirements for RSA keys used by smart cards to be generated by the card itself. In this case, the private key data is never, at any stage, available off the card. It is only recently that smart cards have reached the levels of computational capability necessary to make this key pair generation feasible within an acceptable time.
A valid RSA public key, consists of the following data:
a modulus n, which is a non-negative integer equal to the product of two odd primes p and q; and
a public exponent e, which is a non-negative integer between 3 and n−1 inclusive, and whose greatest common divisor with l(n) is 1. Here l(n) is the least common multiple of both p−1 and q−1.
A valid RSA private key, in one of the two common representations, consists of the following data:
a modulus n, equal to that in the corresponding RSA public key; and
a private exponent d, which is a positive integer less than n satisfying e d=1 mod l(n). By “mod” is meant modular reduction, i.e. the remainder when e d is divided by l(n) is equal to 1.
The public key is typically used to encrypt data, while the corresponding private key may be used to decrypt data so encrypted. Alternatively, the private key may be used to sign data. The corresponding public key may then be used to validate the signature so computed.
Typically in RSA key pair generation, the public exponent e is specified to be some predefined value. It is advantageous that this value be prime (so that the condition that the greatest common divisor of e and l(n)=1 is more likely to hold), and that its binary representation consist of as few non-zero digits as possible (so that exponentiation computations using it are fast). Typical values used in practice are 3, 17, 257 and 65537. This is a very small value in relation to the typical size of the modulus (200-300 digits) required for reasonable levels of security.
During key generation therefore, having computed the modulus by whatever means are appropriate, the problem is then, given the value e, to compute the corresponding private exponent d. Since e d=1 mod l(n), it is required to compute d=e
−1
mod l(n). This so-called modular inversion is the operation with which the present invention is concerned. The method is one which should be suitable for implementation on memory constrained devices, such as smart cards, under the typical constraints on the value of e noted above.
It should be noted that the other common representation of the RSA private key data is in the so-called Chinese Remainder Theorem form. In this form, the factors p and q of the modulus are stored, as well as the values dp=d mod p−1 and dq=d mod q−1. The purpose of storing the key data in this form is that operations using the private key can then typically be performed much more quickly. The two values dp and dq represent the private exponent d. Their relation to the public exponent e is given by: dp=e
−1
mod p−1 and dq=e
−
1 mod q−1. In other words, two modular inversions are required in this case. Hence, the method of the present invention is also relevant, i.e. an efficient computation of the modular inverse is required.
To summarize, the object of the present invention is to provide an efficient method for modular inversion. This is of specific use in the context of RSA key generation in smart cards. Also, it may be of use in other applications requiring modular inversion operations with values of input parameters restricted as is typical for RSA.
There are a number of methods available for modular inversion. In particular, the most commonly used are, or are variants of, the following two methods:
the extended Euclidean algorithm,
the binary extended GCD algorithm
(see algorithms 2.107 and 14.61 in the book “Handbook of Applied Cryptography” by A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, CRC Press, 1996, and algorithm X in section 4.5.2 of “The Art of Computer Programming. Volume 2 Seminumerical Algorithms” by D. Knuth, Addison Wesley, 1981). It should be noted that variants such as Lehmer's algorithm (algorithm L in section 4.5.2 of “The Art of Computer Programming. Volume 2 Seminumerical Algorithms” by D. Knuth, Addison Wesley, 1981) are not considered here since they are complex (large code size) algorithms unsuitable for the smart card applications.
The drawbacks of these methods are similar in that both have sizeable requirements in terms of RAM usage for temporary variables, together with significant requirements in terms of code size. In the context of smart card applications, these issues are of great significance. Another drawback of the known methods is that it is common, in practice, that cryptographic coprocessors available on smart card platforms are restricted to support modular arithmetic operations with only odd values for the modulus, since use is made of Montgomery arithmetic. In this case direct application of the conventional inversion techniques to the original problem with hardware support for the relevant arithmetic operations may prove problematic, since e.g. l(n) is even.
BRIEF SUMMARY OF THE INVENTION
The present invention therefore seeks to provide a method of performing a modular inversion, which overcomes, or at least reduces, the above-mentioned problems of the prior art.
Accordingly, in a first aspect, the invention provides a method of determining a modular inverse e
−1
mod m of a data value e, the method comprising the steps of:
(i) determining the value of the data value e;
(ii) determining a value of m for the inversion;
(iii) calculating the value of m mod e by determining a remainder value r of m divided by e;
(iv) determining an inverse t=r
−1
mod e; and
(v) determining the modular inverse e
−1
mod m utilising at least the value t.
In preferred embodiments, the step (iv) of determining an inverse t=a
−1
mod e, is performed either by computing a
e−2
mod e if e is prime or by using the extended Euclidean or binary extended GCD algorithms for more general values of e.
Preferably, the method is utilized in an RSA™ cryptographic system to generate a private exponent d used to determine an RSA™ private key for the cryptographic system. The method is preferably carried out by a processor on a smartcard.


REFERENCES:
patent: 5448639 (1995-09-01), Arazi
[KNU]The Art of Computer Programming, 2ndet, vol. 2: Semi-numerical Algorithms,D.E. Knuth, Addison-Wesley, 1981.
[MEN]Handbook of Applied Cryptography,A.J. Menezes, P.C. vanOorschot and S.A. Vanstone, CRC Press, 1996. pp. 67, 325, 608, 329-330.
[RSA]A Method for Obtaining Digital Signatures and public Key Cryptosystems,R.L. Rivest, A. Shamir and L. Adleman, Communications of the ACM, 21 (1978), 120-126.
[PKC1]PKCS#1 RSA Cryptography Specific

Affiliated with

Also associated with

Rating

Method of performing modular inversion does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of performing modular inversion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of performing modular inversion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3123748