Using cryptographic blinding for efficient use of Montgomery multiplication

Patent metadata

Field	Value
Publication number	US-11522669-B2
Application number	US-201917042006-A
Country	US
Kind code	B2
Filing date	Mar 26, 2019
Priority date	Mar 28, 2018
Publication date	Dec 6, 2022
Grant date	Dec 6, 2022

Abstract

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.

First claim

What is claimed is:

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.

Assignees

• Cryptography Res Inc

Inventors

• Tunstall Michael

Classifications

• H04L9/3249

  using RSA or related signature schemes, e.g. Rabin scheme · CPC title

• H04L9/003 Primary

  for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA] · CPC title

• H04L2209/046

  of operations, operands or results of the operations · CPC title

• G06F21/602 Primary

  Providing cryptographic facilities or services · CPC title

• H04L9/302

  involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes · CPC title