Method and apparatus for calculating a multiplicative inverse of an element of a prime field

• US 7,191,333 B1
• Filed: 10/25/2001
• Issued: 03/13/2007
• Est. Priority Date: 10/25/2001
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Tomei, Kenneth J., Maddury, Mahesh S.
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): Powers; William S
• Application Number:
  US10/040,050
• Time in Patent Office: 1,965 Days
• Field of Search: 713/161, 713/180, 713/200, 708/135, 708/190, 708/490, 708/504, 380/277, 380 28- 30, 705/50
• US Class Current: 713/174
• CPC Class Codes: G06F 7/726 Inversion; Reciprocal calculation; Division of elements of a finite field
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Techniques for implementing a digital signature algorithm in electronic computer hardware include computing the multiplicative inverse of a particular integer modulo a prime modulus by computing a first quantity modulo the prime modulus. The first quantity substantially equals, modulo the prime modulus, the particular integer raised to a power of a second quantity. The second quantity is two less than the prime modulus. The techniques allow an integrated circuit block to compute a modulo multiplicative inverse, such as for signing and verifying digital signatures, using existing blocks of circuitry that consume considerably less area on a chip, and incur fewer developmental costs, than an implementation of an algorithm conventionally used in software.

Claims

1. A data processing method for generating a multiplicative inverse for use in determining a digital signature, the method comprising the computer-implemented steps of:

receiving and storing a first integer data value relating to a digital signature of an electronic message;

determining a multiplicative inverse of the first integer data value modulo a prime modulus data value by computing a first quantity modulo the prime modulus data value, wherein said computing includes using a modulo exponentiation block;

wherein the first quantity equals, modulo the prime modulus data value, the first integer data value raised to a power of a second quantity;

wherein the second quantity is two less than the prime modulus data value; and

storing the multiplicative inverse in a computer hardware storage element for use in determining the digital signature of the electronic message.

2. A method for generating an output signal indicating a multiplicative inverse of an integer data value modulo a prime modulus for use in performing a particular operation, the method comprising the steps of:

sending a first signal, indicating a value of the integer data value, to a base input of a modulo exponentiation block of an electronic integrated circuit;

sending a second signal, indicating a value of the prime modulus, to a modulus input of the modulo exponentiation block; and

sending a third signal, indicating a value of the prime modulus less two, to an exponent input of the modulo exponentiation block;

wherein the modulo exponentiation block generates an output based on a first quantity modulo a value at the modulus input;

wherein the first quantity equals, modulo the value at the modulus input, a value at the base input raised to a power of a value at the exponent input; and

wherein the output generated by the modulo exponentiation block is stored in a computer hardware storage element for use in performing a particular operation that is selected from the group consisting of a digital signature algorithm signing operation, a digital signature algorithm verifying operation, an encryption operation for a first electronic message, and a decryption operation for a second electronic message.

3. A method for fabricating an electronic circuit that generates an output signal indicating a multiplicative inverse of an integer data value modulo a prime modulus, the method comprising the steps of:

connecting a first register holding signals indicating a value of the integer data value to a base input of a modulo exponentiation block;

connecting a second register holding signals indicating a value of the prime modulus, to a modulus input of the modulo exponentiation block;

connecting a third register holding signals indicating a value of the prime modulus less two, to an exponent input of the modulo exponentiation block;

wherein the modulo exponentiation block generates an output based on a first quantity modulo a value at the modulus input; and

wherein the first quantity equals, modulo the value at the modulus input, a value at the base input raised to a power of a value at the exponent input.

4. An apparatus for generating an output signal indicating a multiplicative inverse of an integer modulo a prime modulus comprising:

a modulo exponentiation block configured to generate the output signal based on a first quantity modulo a value at a modulus input, the first quantity equal, modulo the value at the modulus input, to a value at a base input raised to a power of a value at an exponent input;

a first input for receiving a first signal indicating a value of the integer, the first input connected to the base input;

a second input for receiving a second signal indicating a value of the prime modulus, the second input connected to the modulus input; and

a circuit connected to the second input configured to generate on a first output a third signal indicating a value of the prime modulus less two, the first output connected to the exponent input.

5. An apparatus for performing a particular operation for using digital signatures on a network, the apparatus comprising a modulo exponentiation block configured for producing a multiplicative inverse of an integer modulo a prime modulus, wherein:

said multiplicative inverse of an integer modulo a prime modulus, wherein said multiplicative inverse is used in performing the particular operation;

the particular operation is performed in a series of sequential computations accomplished over a corresponding series of computation cycles; and

the apparatus further comprises connections configured to use the modulo exponentiation block during a plurality of computation cycles of the series of computation cycles.

6. The apparatus as recited in claim 5, wherein the apparatus has no circuitry block configured to perform an extended Euclidian algorithm (EEA) and no general-purpose processor configured by instructions to perform the EEA.

7. The apparatus as recited in claim 5, wherein the particular operation is a Rivest, Shamir, and Adleman encrypting operation.

8. The apparatus as recited in claim 5, wherein the particular operation is a Rivest, Shamir, and Adleman decrypting operation.

9. The apparatus as recited in claim 5, wherein the particular operation is a digital signature algorithm signing operation.

10. The apparatus as recited in claim 5, wherein the particular operation is a digital signature algorithm verifying operation.

11. A computer-readable medium carrying one or more sequences of instructions for generating a multiplicative inverse of an integer modulo a prime modulus for use in performing a particular operation, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

sending data indicating a value of the integer as an base input to a modulo exponentiation function;

sending data indicating a value of the prime modulus as an modulus input to the modulo exponentiation function; and

sending data indicating a value of the prime modulus less two as an exponent input of the modulo exponentiation function,

wherein

the modulo exponentiation function generates an output based on a first quantity modulo the modulus input,

the first quantity equals, modulo the modulus input, the base input raised to a power of the exponent input; and

the output generated by the modulo exponentiation function is used in performing a particular operation that is selected from the group consisting of a digital signature algorithm signing operation, a digital signature algorithm verifying operation, an encryption operation for a first electronic message, and a decryption operation for a second electronic message.

12. The computer-readable medium recited in claim 11, wherein the exponentiation function sends the base input, the modulus input and the exponent input to a special-purpose block of circuitry configured to perform modulo exponentiation.

13. A computer-readable medium carrying one or more sequences of instructions for generating a multiplicative inverse for use in determining a digital signature, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of

receiving and storing a first integer data value relating to a digital signature of an electronic message;

determining a multiplicative inverse of the first integer data value modulo a prime modulus data value by computing a first quantity modulo the prime modulus data value, wherein said computing includes using a modulo exponentiation block;

wherein the first quantity equals, modulo the prime modulus data value, the first integer data value raised to a power of a second quantity;

wherein the second quantity is two less than the prime modulus data value; and

storing the multiplicative inverse in a computer hardware storage element for use in determining the digital signature of the electronic message.

14. An apparatus for generating a multiplicative inverse for use in determining a digital signature, the method comprising the computer-implemented steps of:

means for receiving and storing a first integer data value relating to a digital signature of an electronic message;

means for determining a multiplicative inverse of the first integer data value modulo a prime modulus data value by computing a first quantity modulo the prime modulus data value, wherein said computing includes using a modulo exponentiation block;

wherein the first quantity equals, modulo the prime modulus data value, the first integer data value raised to a power of a second quantity;

wherein the second quantity is two less than the prime modulus data value; and

means for storing the multiplicative inverse in a computer hardware storage element for use in determining the digital signature of the electronic message.

15. An apparatus for generating a output signal indicating a multiplicative inverse of an integer data value modulo a prime modulus for use in performing a particular operation, the apparatus comprising:

means for sending a first signal, indicating a value of the integer data value, to a base input of a modulo exponentiation block of an electronic integrated circuit;

means for sending a second signal, indicating a value of the prime modulus, to a modulus input of the modulo exponentiation block; and

means for sending a third signal, indicating a value of the prime modulus less two, to an exponent input of the modulo exponentiation block;

wherein the modulo exponentiation block includes means for generating an output based on a first quantity modulo a value at the modulus input;

wherein the first quantity equals, modulo the value at the modulus input, a value at the base input raised to a power of a value at the exponent input; and

wherein the output generated by the modulo exponentiation block is stored in a computer hardware storage element for use in performing a particular operation that is selected from the group consisting of a digital signature algorithm signing operation, a digital signature algorithm verifying operation, an encryption operation for a first electronic message, and a decryption operation for a second electronic message.