# US 2019/0165928 A1 · Protection of a modular reduction calculation

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

- Number: US 2019/0165928 A1
- Document ID: US20190165928A1
- Status: Published application
- Kind: A1
- Application number: 15/827,994
- Filed: 2017-11-30
- Published: 2019-05-30
- Earliest claimed: 2017-11-30
- Assignees: STMicroelectronics S.r.l.
- Applicants: STMICROELECTRONICS S.r.l.
- Inventors: Ruggero Susella
- Web page: https://patentgrep.com/patent/US20190165928A1

## CPC

- H04L 9/005: {for timing attacks}
- G06F 7/72: using residue arithmetic
- G06F 7/725: {over elliptic curves}
- G06F 21/44: Program or device authentication
- G06F 21/72: in cryptographic circuits
- H04L 9/002: {Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441)}
- H04L 9/3271: {using challenge-response}
- H04L 2209/12: Details relating to cryptographic hardware or logic circuitry
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A modular reduction calculation on a first number and a second number is protected from side-channel attacks, such as timing attacks. A first intermediate modular reduction result is calculated. A value corresponding to four times the first number is added to the first intermediate modular reduction result, generating a second intermediate modular reduction result. A value corresponding to the first number multiplied by a most significant word of the second intermediate modular reduction result plus 1, is subtracted from the second intermediate modular reduction result, generating a third intermediate modular reduction result. A cryptographic operation is performed using a result of the modular reduction calculation.

## Claims

### Claim 1

A device, comprising:
one or more memories; and
processing circuitry to perform a cryptographic operation, wherein the processing circuitry, in operation:
performs a modular reduction calculation on a first number and a second number, the performing the modular reduction calculation including:
calculating a first intermediate modular reduction result B;
adding, to the first intermediate modular reduction result B, a first value corresponding to an integer multiple of the second number, generating a second intermediate modular reduction result B′;
subtracting, from the second intermediate modular reduction result B′, a second value corresponding to the second number multiplied by a most significant word m of the second intermediate modular reduction result B′ plus 1, generating a third intermediate modular reduction result B″; and
generating a result of the modular reduction calculation using the third intermediate modular reduction result B″; and
uses the result of the modular reduction calculation in the cryptographic operation.

### Claim 2 (depends on 1)

The device of claim 1, wherein the generating the result of the modular reduction calculation using the third intermediate modular reduction result B″ comprises:
adding, word by word, a word of the third intermediate modular reduction result B″ to a result of a logical AND of a respective word of the second number and a most significant word of the third intermediate modular reduction result B″, generating a modular reduction value; and
generating a result of the modular reduction calculation using the modular reduction value.

### Claim 3 (depends on 1)

The device of claim 1 wherein the processing circuitry performs the modular reduction calculation using a determined number of steps which is independent of the first number.

### Claim 4 (depends on 1)

The device of claim 1 wherein the first number represents an intermediate result of an elliptic curve group operation.

### Claim 5 (depends on 4)

The device of claim 4 wherein the performing the modular reduction calculation comprises performing a Solinas modular reduction.

### Claim 6 (depends on 5)

The device of claim 5 wherein the elliptic curve is an NIST P-256 curve.

### Claim 7 (depends on 1)

The device of claim 1, comprising a Cortex-MO processor and a USB-C interface.

### Claim 8 (depends on 1)

The device of claim 1 wherein the integer multiple is 4.

### Claim 9

A system, comprising:
one or more processing cores, which in operation, process digital data; and
cryptographic circuitry, coupled to the one or more processing cores, wherein the cryptographic circuitry, in operation:
performs a cryptographic operation by performing a modular reduction calculation using a first number and a second number, the performing the modular reduction calculation including:
calculating a first intermediate modular reduction result B;
adding, to the first intermediate modular reduction value B, a first value corresponding to an integer multiple of the second number, generating a second intermediate modular reduction result B′; and
subtracting, from the second intermediate modular reduction result B′, a second value corresponding to the second number multiplied by a most significant word m of the second intermediate modular reduction result B′ plus 1, generating a third intermediate modular reduction result B″.

### Claim 10 (depends on 9)

The system of claim 9 wherein the performing the modular reduction calculation includes:
adding, word by word, a word of the third intermediate modular reduction result B″ to a result of a logical AND of a respective word of the second number and a most significant word of the third intermediate modular reduction result B″, generating a result of the modular reduction calculation.

### Claim 11 (depends on 9)

The system of claim 9 wherein the cryptographic circuitry performs the modular reduction calculation using a determined number of steps which is independent of the first number.

### Claim 12 (depends on 11)

The system of claim 11 wherein the first number represents an intermediate result of an elliptic curve group operation.

### Claim 13 (depends on 9)

The system of claim 9 wherein the performing the modular reduction calculation comprises performing a Solinas modular reduction.

### Claim 14 (depends on 12)

The system of claim 12 wherein the elliptic curve is an NIST P-256 curve.

### Claim 15 (depends on 9)

The system of claim 9 wherein the cryptographic circuitry comprises a Cortex-MO processor and a USB-C interface.

### Claim 16 (depends on 9)

The system of claim 9 wherein the adding, to the first intermediate modular reduction value B, the first value corresponding to the integer multiple of the second number, comprises representing the first value in hexadecimal as 32-bit words corresponding to:
−4, −1, −1, 3, 0, 0, 4, −4, 3.

### Claim 17 (depends on 9)

The system of claim 9 wherein the subtracting, from the second intermediate modular reduction result B′, the second value corresponding to the second number multiplied by a most significant word m of the second intermediate modular reduction result B′ plus 1 comprises determining:
(m+1)*p,
where m is the most significant word of B′ and p is the second number.

### Claim 18 (depends on 15)

The system of claim 15 wherein the cryptographic circuitry, in operation, authenticates a device coupled to the USB-C interface, the authenticating including performing the cryptographic operation.

### Claim 19

A non-transitory computer-readable medium having contents which cause one or more processing devices to perform a method, the method comprising:
performing a cryptographic operation, the performing the cryptographic operation including performing a modular reduction calculation using a first number and a second number, the performing the modular reduction calculation including:
calculating a first intermediate modular reduction result B;
adding a value corresponding to an integer multiple of the second number to the first intermediate modular reduction result B, generating a second intermediate modular reduction result B′;
subtracting, from the second intermediate modular reduction result B′, a value corresponding to the second number multiplied by a most significant word m of the second intermediate modular reduction result B′ plus 1, generating a third intermediate modular reduction result B″; and
generating a result of the modular reduction calculation using the third intermediate modular reduction result B″.

### Claim 20 (depends on 19)

The non-transitory computer-readable medium of claim 19 wherein the integer multiple is 4.

### Claim 21 (depends on 19)

The non-transitory computer-readable medium of claim 19 wherein the method comprises processing transaction data.

### Claim 22

A method, comprising:
performing, using cryptographic circuitry, a cryptographic operation, wherein the performing the cryptographic operation includes performing a modular reduction calculation on a first number and a second number, the performing the modular reduction calculation including:
calculating a first intermediate modular reduction result B;
adding, to the first intermediate modular reduction result B, a first value corresponding to an integer multiple of the second number, generating a second intermediate modular reduction result B′;
subtracting, from the second intermediate modular reduction result B′, a second value corresponding to the second number multiplied by a most significant word m of the second intermediate modular reduction result B′ plus 1, generating a third intermediate modular reduction result B″; and
generating a result of the modular reduction calculation using the third intermediate modular reduction result B″.

### Claim 23 (depends on 22)

The method of claim 22, wherein the generating the result of the modular reduction calculation using the third intermediate modular reduction result B″ comprises:
adding, word by word, a word of the third intermediate modular reduction result B″ to a result of a logical AND of a respective word of the second number and a most significant word of the third intermediate modular reduction result B″, generating a modular reduction value; and
generating a result of the modular reduction calculation using the modular reduction value.

### Claim 24 (depends on 22)

The method of claim 22 wherein the cryptographic circuitry performs the modular reduction calculation using a determined number of steps which is independent of the first number.

### Claim 25 (depends on 22)

The method of claim 22 wherein the first number represents an intermediate result of an elliptic curve group operation.

### Claim 26 (depends on 22)

The method of claim 22 wherein the integer multiple is 4.

### Claim 27 (depends on 22)

The method of claim 22, comprising:
authenticating a device coupled to the cryptographic circuitry, the authenticating including performing the cryptographic operation; and
enabling operation of the device based on the authenticating.