# US 2021/0083840 A1 · Using cryptographic blinding for efficient use of montgomery multiplication

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0083840 A1
- Document ID: US20210083840A1
- Status: Published application
- Kind: A1
- Application number: 17/042,006
- Filed: 2019-03-26
- Published: 2021-03-18
- Earliest claimed: 2018-03-28
- Assignees: Cryptography Research, Inc.
- Applicants: Cryptography Research, Inc.
- Inventors: Michael TUNSTALL
- Web page: https://patentgrep.com/patent/US20210083840A1

## CPC

- G06F 21/602: {Providing cryptographic facilities or services}
- H04L 9/003: {for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]}
- H04L 9/0825: {using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates}
- H04L 9/302: {involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes}
- H04L 9/3249: {using RSA or related signature schemes, e.g. Rabin scheme}
- H04L 2209/046: of operations, operands or results of the operations
- H04L 2209/12: Details relating to cryptographic hardware or logic circuitry
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

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

## Claims

### Claim 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; 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.

### Claim 2 (depends on 1)

The method of claim 1, wherein computing the second random value comprises:
causing the second random value to take the form h=r R2 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=2bx mod n,
where ‘b’ is a bit length, and ‘x’ is the number of words of bit length ‘b’ used to form ‘n’.

### Claim 3 (depends on 2)

The method of claim 2, 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=re−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=re−1 m mod n; and
computing a fourth intermediate value ‘p’ using Montgomery multiplication, where p=re m R mod n.

### Claim 4 (depends on 3)

The method of claim 3, 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=pd−1 j mod n, where ‘d’ is a private exponent.

### Claim 5 (depends on 4)

The method of claim 4, wherein an equation representing the signature ‘S’ takes the form of:
S=(rem)d−1(re−1m)mod n.

### Claim 6 (depends on 1)

The method of claim 1, wherein the first random value ‘r’ has a bit length equal to or less than the public modulus ‘n.’

### Claim 7 (depends on 1)

The method of claim 1, wherein the signature is compatible with public-key cryptography.

### Claim 8 (depends on 7)

The method of claim 7, 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.

### Claim 9 (depends on 1)

The method of claim 1, wherein the SCA attack comprises a Differential Power Analysis (DPA) attack.

### Claim 10 (depends on 9)

The method of claim 9, wherein the method further comprises: providing a DPA-resistant software library that includes codes containing the first random value ‘r.’

### Claim 11 (depends on 1)

The method of claim 1, wherein the Montgomery multiplications are performed in a public key engine (PKE).

### Claim 12

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

### Claim 13 (depends on 12)

The system of claim 12, wherein the processor is further to:
causing the second random value to take the form h=r R2 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=2bx mod n,
where ‘b’ is a bit length, and ‘x’ is the number of words of bit length ‘b’ used to form ‘n’.

### Claim 14 (depends on 13)

The system of claim 13, 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=re−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=re−1m mod n; and
compute a fourth intermediate value ‘p’ using Montgomery multiplication, where p=re m R mod n.

### Claim 15 (depends on 14)

The system of claim 14, 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=pd−1 j mod n, where ‘d’ is a private exponent.

### Claim 16 (depends on 15)

The system of claim 15, wherein an equation representing the signature ‘S’ takes the form of:
S=(rem)d−1(re−1m)mod n.

### Claim 17 (depends on 12)

The system of claim 12, wherein the first random value ‘r’ has a bit length equal to or less than the public modulus ‘n.’

### Claim 18 (depends on 12)

The system of claim 12, wherein the signature is compatible with public-key cryptography.

### Claim 19 (depends on 17)

The system of claim 17, 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.

### Claim 20 (depends on 11)

The system of claim 11, wherein the SCA attack comprises a Differential Power Analysis (DPA) attack.
