Using cryptographic blinding for efficient use of Montgomery multiplication
Aspects of the present disclosure involves receiving an input message, generating a first random value that is used to blind the input message input message to prevent a side-channel analysis (SCA) attack, computing a second random value using the first random value and a factor used to compute the Montgomery form of a blinded input message without performing an explicit Montgomery conversion of the input message, and computing a signature using Montgomery multiplication, of the first random value and the second random value, wherein the signature is resistant to the SCA attack.
1. A computer-implemented method comprising:
receiving an input message at a processor executing a cryptographic algorithm;
generating, by the processor, a first random value that is used to blind the input message to prevent a side-channel analysis (SCA) attack;
computing, by the processor, a second random value, using the first random value and a factor used to create a Montgomery form of the blinded input message without performing a Montgomery conversion of the input message, wherein the processor causes the second random value to take the form h=r R 2 mod n,
where ‘r’ is the first random value that is used to blind the input message,
‘n’ is a public modulus, and
‘R’ is the factor used to create the Montgomery form, wherein
R=2 bx mod n,
where ‘b’ is a bit length, and ‘x’ is the number of words of bit length ‘b’ used to form ‘n’; and
computing, by the processor, a signature by performing Montgomery multiplications using the first random value and the second random value, wherein the signature is a countermeasure against the SCA attack.
2. The method of claim 1 , wherein computing the signature comprises:
computing a first intermediate value ‘v’ by multiplying ‘h’ with 1, where v=r R mod n;
computing a second intermediate value ‘k’ using Montgomery multiplication, where k=r e−1 R mod n, where ‘e’ is a public exponent, and ‘m’ is the input message;
computing a third intermediate value ‘j’ using Montgomery multiplication, where j=r e−1 m mod n; and
computing a fourth intermediate value ‘p’ using Montgomery multiplication, where p=r e m R mod n.
3. The method of claim 2 , wherein computing the signature further comprises:
Montgomery multiplying the third intermediate value ‘j’ by the fourth intermediate value ‘p’ to produce the signature ‘S,’ wherein S=p d−1 j mod n, where ‘d’ is a private exponent.
4. The method of claim 3 , wherein an equation representing the signature ‘S’ takes the form of:
S =( r e m ) d−1 ( r e−1 m )mod n.
5. The method of claim 1 , wherein the first random value ‘r’ has a bit length equal to or less than the public modulus ‘n.’
6. The method of claim 1 , wherein the signature is compatible with public-key cryptography.
7. The method of claim 6 , wherein the method further comprises:
transmitting the signature from a first node to a second node within a public-key cryptography system, wherein the second node is capable of deciphering the blinded input message.
8. The method of claim 1 , wherein the SCA attack comprises a Differential Power Analysis (DPA) attack.
9. The method of claim 8 , wherein the method further comprises: providing a DPA-resistant software library that includes codes containing the first random value ‘r.’
10. The method of claim 1 , wherein the Montgomery multiplications are performed in a public key engine (PKE).
11. A public-key cryptography system comprising:
an external memory; and
a processor, executing a cryptography algorithm and being operatively coupled with the external memory, to:
receive an input message;
generate, a first random value that is used to blind the input message to prevent a side-channel analysis (SCA) attack;
compute a second random value, using the first random value and a factor used to create a Montgomery form of the blinded input message without performing a Montgomery conversion of the input message, wherein the processor causes the second random value to take the form h=r R 2 mod n,
where ‘r’ is the first random value that is used to blind the input message,
‘n’ is a public modulus, and
‘R’ is the factor used to create the Montgomery form, wherein
R=2 bx mod n,
where ‘b’ is a bit length, and ‘x’ is the number of words of bit length ‘b’ used to form ‘n’; and
compute a signature by performing Montgomery multiplications using the first random value and the second random value, wherein the signature is a countermeasure against the SCA attack.
12. The system of claim 11 , wherein the processor is further to:
compute a first intermediate value ‘v’ by multiplying ‘h’ with 1, where v=r R mod n;
compute a second intermediate value ‘k’ using Montgomery multiplication, where k=r e−1 R mod n, where ‘e’ is a public exponent, and ‘m’ is the input message;
compute a third intermediate value ‘j’ using Montgomery multiplication, where j=r e−1 m mod n; and
compute a fourth intermediate value ‘p’ using Montgomery multiplication, where p=r e m R mod n.
13. The system of claim 12 , wherein the processor is further to:
Montgomery multiply the third intermediate value ‘j’ by the fourth intermediate value ‘p’ to produce the signature ‘S,’ wherein S=p d−1 j mod n, where ‘d’ is a private exponent.
14. The system of claim 13 , wherein an equation representing the signature ‘S’ takes the form of:
S =( r e m ) d−1 ( r e−1 m )mod n.
15. The system of claim 11 , wherein the first random value ‘r’ has a bit length equal to or less than the public modulus ‘n.’
16. The system of claim 11 , wherein the signature is compatible with public-key cryptography.
17. The system of claim 15 , wherein the processor is further to:
transmit the signature from a first node to a second node within the public-key cryptography system, wherein the second node is capable of deciphering the blinded input message.
18. The system of claim 11 , wherein the SCA attack comprises a Differential Power Analysis (DPA) attack.