Residue number system based pre-computation and dual-pass arithmetic modular operation approach to implement encryption protocols efficiently in electronic integrated circuits
First Claim
1. A method for encrypting and decrypting electronic messages based on an encryption protocol, the method comprising the computer-implemented steps of:
- selecting, based on a modulus (M) that is associated with a first electronic message, a first constant (W) such that W≧
4M, a second constant (V), wherein the first constant (W) and the second constant (V) are relatively prime;
generating a third constant (R) based on the first constant (W) and a modular reduction operation by determining the third constant (R) according to the expression R=W2(mod(M));
identifying, based on at least part of the encryption protocol, a first operand (X) and a second operand (Y) for at least one modular operation that is part of the encryption protocol;
generating a first residual number system (RNS) representation in a first RNS base and a second RNS representation in a second RNS base of each of the third constant (R) and the first operand (X), wherein the first RNS base is based on the first constant (W) and the second RNS base is based on the second constant (V);
generating a first RNS representation in the first RNS base of the first constant (W), a second RNS representation in the second RNS base of the second constant (V), a first RNS representation in the first RNS base of a negative multiplicative inverse of the modulus (M′
), a second RNS representation in the second RNS base of the modulus (M), and a second RNS representation in the second RNS base of a multiplicative inverse of the first constant (W−
1);
determining at least part of a second electronic message based on at least the first electronic message, the encryption protocol, and the at least one modular operation, wherein the at least one modular operation is implemented using two passes of Montgomery'"'"'s method;
wherein a first pass of the two passes of Montgomery'"'"'s method includes the computer-implemented steps of;
determining both a first RNS representation in the first RNS base and a second RNS representation in the second RNS base of an intermediate result (S) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), and both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the third constant (R) and the first operand (X);
wherein a second pass of the two passes of Montgomery'"'"'s method includes the computer-implemented steps of;
determining an RNS representation in one of the first RNS base and the second RNS base of a final result (F) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the intermediate result (S), and the second operand (Y).
1 Assignment
0 Petitions
Accused Products
Abstract
A pre-computation and dual-pass modular operation approach to implement encryption protocols efficiently in electronic integrated circuits is disclosed. An encrypted electronic message is received and another electronic message generated based on the encryption protocol. Two passes of Montgomery'"'"'s method are used for a modular operation that is associated with the encryption protocol along with pre-computation of a constant based on a modulus. The modular operation may be a modular multiplication or a modular exponentiation. Modular arithmetic may be performed using the residue number system (RNS) and two RNS bases with conversions between the two RNS bases. A minimal number of register files are used for the computations along with an array of multiplier circuits and an array of modular reduction circuits. The approach described allows for high throughput for large encryption keys with a relatively small number of logical gates.
-
Citations
44 Claims
-
1. A method for encrypting and decrypting electronic messages based on an encryption protocol, the method comprising the computer-implemented steps of:
-
selecting, based on a modulus (M) that is associated with a first electronic message, a first constant (W) such that W≧
4M, a second constant (V), wherein the first constant (W) and the second constant (V) are relatively prime;generating a third constant (R) based on the first constant (W) and a modular reduction operation by determining the third constant (R) according to the expression R=W2(mod(M)); identifying, based on at least part of the encryption protocol, a first operand (X) and a second operand (Y) for at least one modular operation that is part of the encryption protocol; generating a first residual number system (RNS) representation in a first RNS base and a second RNS representation in a second RNS base of each of the third constant (R) and the first operand (X), wherein the first RNS base is based on the first constant (W) and the second RNS base is based on the second constant (V); generating a first RNS representation in the first RNS base of the first constant (W), a second RNS representation in the second RNS base of the second constant (V), a first RNS representation in the first RNS base of a negative multiplicative inverse of the modulus (M′
), a second RNS representation in the second RNS base of the modulus (M), and a second RNS representation in the second RNS base of a multiplicative inverse of the first constant (W−
1);determining at least part of a second electronic message based on at least the first electronic message, the encryption protocol, and the at least one modular operation, wherein the at least one modular operation is implemented using two passes of Montgomery'"'"'s method; wherein a first pass of the two passes of Montgomery'"'"'s method includes the computer-implemented steps of; determining both a first RNS representation in the first RNS base and a second RNS representation in the second RNS base of an intermediate result (S) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), and both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the third constant (R) and the first operand (X);wherein a second pass of the two passes of Montgomery'"'"'s method includes the computer-implemented steps of; determining an RNS representation in one of the first RNS base and the second RNS base of a final result (F) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the intermediate result (S), and the second operand (Y). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A computer-readable medium carrying one or more sequences of instructions for encrypting and decrypting electronic messages based on an encryption protocol, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:
-
selecting, based on a modulus (M) that is associated with a first electronic message, a first constant (W) such that W≧
4M, a second constant (V), wherein the first constant (W) and the second constant (V) are relatively prime;generating a third constant (R) based on the first constant (W) and a modular reduction operation by determining the third constant (R) according to the expression R=W2(mod(M)); identifying, based on at least part of the encryption protocol, a first operand (X) and a second operand (Y) for at least one modular operation that is part of the encryption protocol; generating a first residual number system (RNS) representation in a first RNS base and a second RNS representation in a second RNS base of each of the third constant (R) and the first operand (X), wherein the first RNS base is based on the first constant (W) and the second RNS base is based on the second constant (V); generating a first RNS representation in the first RNS base of the first constant (W), a second RNS representation in the second RNS base of the second constant (V), a first RNS representation in the first RNS base of a negative multiplicative inverse of the modulus (M′
), a second RNS representation in the second RNS base of the modulus (M), and a second RNS representation in the second RNS base of a multiplicative inverse of the first constant (W−
1);determining at least part of a second electronic message based on at least the first electronic message, the encryption protocol, and the at least one modular operation, wherein the at least one modular operation is implemented using two passes of Montgomery'"'"'s method; wherein a first pass of the two passes of Montgomery'"'"'s method comprises instructions which, when executed by one or more processors, cause the one or more processors to carry out the steps of; determining both a first RNS representation in the first RNS base and a second RNS representation in the second RNS base of an intermediate result (S) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), and both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the third constant (R) and the first operand (X);wherein a second pass of the two passes of Montgomery'"'"'s method comprises instructions which, when executed by one or more processors, cause the one or more processors to carry out the steps of; determining an RNS representation in one of the first RNS base and the second RNS base of a final result (F) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the intermediate result (S), and the second operand (Y). - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. An apparatus for encrypting and decrypting electronic messages based on an encryption protocol, comprising:
-
means for selecting, based on a modulus (M) that is associated with a first electronic message, a first constant (W) such that W≧
4M, a second constant (V), wherein the first constant (W) and the second constant (V) are relatively prime;means for generating a third constant (R) based on the first constant (W) and a modular reduction operation by determining the third constant (R) according to the expression R=W2(mod(M)); means for identifying, based on at least part of the encryption protocol, a first operand (X) and a second operand (Y) for at least one modular operation that is part of the encryption protocol; means for generating a first residual number system (RNS) representation in a first RNS base and a second RNS representation in a second RNS base of each of the third constant (R) and the first operand (X), wherein the first RNS base is based on the first constant (W) and the second RNS base is based on the second constant (V); means for generating a first RNS representation in the first RNS base of the first constant (W), a second RNS representation in the second RNS base of the second constant (V), a first RNS representation in the first RNS base of a negative multiplicative inverse of the modulus (M′
), a second RNS representation in the second RNS base of the modulus (M), and a second RNS representation in the second RNS base of a multiplicative inverse of the first constant (W−
1);means for determining at least part of a second electronic message based on at least the first electronic message, the encryption protocol, and the at least one modular operation, wherein the at least one modular operation is implemented using two passes of Montgomery'"'"'s method; wherein a first pass of the two passes of Montgomery'"'"'s method comprises; means for determining both a first RNS representation in the first RNS base and a second RNS representation in the second RNS base of an intermediate result (S) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), and both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the third constant (R) and the first operand (X);wherein a second pass of the two passes of Montgomery'"'"'s method comprises; means for determining an RNS representation in one of the first RNS base and the second RNS base of a final result (F) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the intermediate result (S), and the second operand (Y). - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35)
-
-
34. An apparatus for encrypting and decrypting electronic messages based on an encryption protocol, comprising:
-
an interface; a processor coupled to the interface and receiving information from the interface; and one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of; selecting, based on a modulus (M) that is associated with a first electronic message, a first constant (W) such that W≧
4M, a second constant (V), wherein the first constant (W) and the second constant (V) are relatively prime;generating a third constant (R) based on the first constant (W) and a modular reduction operation by determining the third constant (R) according to the expression R=W2(mod(M)); identifying, based on at least part of the encryption protocol, a first operand (X) and a second operand (Y) for at least one modular operation that is part of the encryption protocol; generating a first residual number system (RNS) representation in a first RNS base and a second RNS representation in a second RNS base of each of the third constant (R) and the first operand (X), wherein the first RNS base is based on the first constant (W) and the second RNS base is based on the second constant (V); generating a first RNS representation in the first RNS base of the first constant (W), a second RNS representation in the second RNS base of the second constant (V), a first RNS representation in the first RNS base of a negative multiplicative inverse of the modulus (M′
), a second RNS representation in the second RNS base of the modulus (M), and a second RNS representation in the second RNS base of a multiplicative inverse of the first constant (W−
1);determining at least part of a second electronic message based on at least the first electronic message, the encryption protocol, and the at least one modular operation, wherein the at least one modular operation is implemented using two passes of Montgomery'"'"'s method; wherein a first pass of the two passes of Montgomery'"'"'s method comprises instructions which, when executed by the processor, cause the processor to carry out the steps of; determining both a first RNS representation in the first RNS base and a second RNS representation in the second RNS base of an intermediate result (S) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), and both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the third constant (R) and the first operand (X);wherein a second pass of the two passes of Montgomery'"'"'s method comprises instructions which, when executed by the processor, cause the processor to carry out the steps of; determining an RNS representation in one of the first RNS base and the second RNS base of a final result (F) for the at least one modular operation based on at least Montgomery'"'"'s method, the first RNS representation in the first RNS base of the first constant (W), the second RNS representation in the second RNS base of the second constant (V), the first RNS representation in the first RNS base of the negative multiplicative inverse of the modulus (M′
), the second RNS representation in the second RNS base of the modulus (M), the second RNS representation in the second RNS base of the multiplicative inverse of the first constant (W−
1), both the first RNS representation in the first RNS base and the second RNS representation in the second RNS base of each of the intermediate result (S), and the second operand (Y). - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44)
-
Specification