Method of performing modular inversion
AssigneeMotorola, Inc.
InventorPaul Montague
Life of this patent
Estimating the term…
Abstract
As part of a process to generate a private key for RSA™ digital signature generation on a smartcard, it is necessary to determine a modular inverse e−1 mod m of a data value e. In order to determine the modular inverse from a data value e and a value of m for the inversion, the value of m mod e is calculated by determining a remainder value r of m divided by e and then an inverse t=r−1 mod e is determined. The modular inverse e−1 mod m is then determined utilising at least the value t by determining a value w=e−t and then determining e−1 mod m by computing (q*w)+1+the integer part of ((w*r)/e).
Claims6
A method of determining a modular inverse e−1 mod m of a data value e 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 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.
Dependencies are inferred from the claim text.