Residue number system based pre-computation and dual-pass arithmetic modular operation approach to implement encryption protocols efficiently in electronic integrated circuits

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).

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).

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).