Using cryptographic blinding for efficient use of montgomery multiplication

Patent metadata

Field	Value
Publication number	US-2023179395-A1
Application number	US-202218061879-A
Country	US
Kind code	A1
Filing date	Dec 5, 2022
Priority date	Mar 28, 2018
Publication date	Jun 8, 2023
Grant date	—

Abstract

Aspects of the present disclosure involves receiving an input message, generating a first random value that is used to blind the 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 .- 20 . (canceled)

21 . 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 blinds the input message; computing, by the processor, a second random value by using the first random value and a factor, wherein the factor transforms the input message in a Montgomery form; computing, by the processor, a first intermediate value by using the second random value, wherein the first intermediate value comprises the factor; computing, by the processor, a second intermediate value by raising the first intermediate value to a power of (e−1), wherein ‘e’ is a public exponent; computing, by the processor, a third intermediate value by using the second intermediate value and the input message; computing, by the processor, a fourth intermediate value by using the third intermediate value and the second intermediate value; and computing, by the processor, an RSA signature by using the third intermediate value, the fourth intermediate value, and a private exponent.

22 . The method of claim 21 , wherein the RSA signature is resistant to a Differential Power Analysis (DPA) attack to decipher the input message.

23 . The method of claim 22 , wherein generating the first random value further comprises:
selecting the first random value from a DPA-resistant software library.

24 . The method of claim 21 , wherein the RSA signature ‘S’ takes the form of:
S= ( r e m ) d−1 ( r e−1 m ) mod n,
where ‘m’ is the input message,
‘r’ is the first random value,
‘e’ is the public exponent,
‘d’ is the private exponent, and
‘n’ is a public modulus.

25 . The method of claim 24 , wherein computing the second random value further comprises:
causing the second random value to take the form:
h=r R 2 mod n,
where ‘R’ is the factor that transforms the input message in the Montgomery form.

26 . The method of claim 25 , wherein the factor ‘R’ takes the form:
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 the public modulus ‘n’.

27 . The method of claim 25 , wherein computing the first intermediate value ‘v’ comprises Montgomery multiplying ‘h’ by 1, such that v=r R mod n.

28 . The method of claim 27 , wherein computing the second intermediate value ‘k’ comprises raising the first intermediate value ‘v’ to a power of (e−1) using Montgomery multiplication, such that k=r e−1 R mod n.

29 . The method of claim 28 , wherein computing the third intermediate value ‘j’ comprises Montgomery multiplying the second intermediate value ‘k’ by the input message ‘m’, such that j=re e−1 m mod n.

30 . The method of claim 29 , wherein computing the fourth intermediate value ‘p’ comprises Montgomery multiplying the third intermediate value ‘j’ by the second intermediate value ‘k’, such that p=r e m R mod n.

31 . The method of claim 30 , wherein computing the RSA signature ‘S’ comprises using Montgomery multiplication to cause ‘S’ to take the form:
S=p d−1 j mod n,
where ‘d’ is the private exponent.

32 . The method of claim 31 , wherein the Montgomery multiplications to compute ‘v’, ‘k’, ‘j’, ‘p’ and ‘S’ are performed in a public key engine (PKE).

33 . A cryptography system comprising:
an external memory; and a processor, executing a cryptography algorithm and being operatively coupled with the external memory, to perform operations comprising: receiving an input message at a processor executing a cryptographic algorithm; generating a first random value that blinds the input message; computing a second random value by using the first random value and a factor, wherein the factor transforms the input message in a Montgomery form; computing a first intermediate value by using the second random value, wherein the first intermediate value comprises the factor; computing a second intermediate value by raising the first intermediate value to a power of (e−1), wherein ‘e’ is a public exponent; computing a third intermediate value by using the second intermediate value and the input message; computing a fourth intermediate value by using the third intermediate value and the second intermediate value; and computing an RSA signature by using the third intermediate value, the fourth intermediate value, and a private exponent.

34 . The system of claim 33 , wherein the RSA signature is resistant to a Differential Power Analysis (DPA) attack to decipher the input message.

35 . The system of claim 34 , wherein the external memory stores a DPA-resistant software library from which the first random value is chosen.

36 . The system of claim 31 , wherein the RSA signature ‘S’ takes the form of:
S= ( r e m ) d−1 ( r e−1 m ) mod n,
where ‘m’ is the input message,
‘r’ is the first random value,
‘e’ is a public exponent,
‘d’ is a private exponent, and
‘n’ is the public modulus.

37 . The system of claim 35 , wherein the processor causes the second random value to take the form:
h=r R 2 mod n, where ‘R’ is the factor that transforms the input message in the Montgomery form.

38 . The system of claim 35 , wherein the processor causes the factor ‘R’ to take the form:
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 the public modulus ‘n’.

39 . The system of claim 38 , wherein the first, second, third and fourth intermediate values are computed performing a sequence of Montgomery multiplications.

40 . A non-transitory machine-readable storage medium storing instructions, which, when executed, cause a processing device executing a cryptographic algorithm to perform operations comprising:
receiving an input message at a processor executing a cryptographic algorithm; generating a first random value that blinds the input message; computing a second random value by using the first random value and a factor, wherein the factor transforms the input message in a Montgomery form; computing a first intermediate value by using the second random value, wherein the first intermediate value comprises the factor; computing a second intermediate value by raising the first intermediate value to a power of (e−1), wherein ‘e’ is a public exponent; computing a third intermediate value by using the second intermediate value and the input message; computing a fourth intermediate value by using the third intermediate value and the second intermediate value; and computing an RSA signature by using the third intermediate value, the fourth intermediate value, and a private exponent.

Assignees

• Cryptography Res Inc

Inventors

• Tunstall Michael

Classifications

• 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

• H04L9/3249

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