# US 2019/0377554 A1 · Method for determining a modular inverse and associated cryptographic processing device

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

- Number: US 2019/0377554 A1
- Document ID: US20190377554A1
- Status: Published application
- Kind: A1
- Application number: 16/426,824
- Filed: 2019-05-30
- Published: 2019-12-12
- Earliest claimed: 2018-06-08
- Assignees: Idemia France
- Applicants: IDEMIA France
- Inventors: Thomas CHABRIER; Gilles PIRET
- Web page: https://patentgrep.com/patent/US20190377554A1

## CPC

- G06F 7/721: {Modular inversion, reciprocal or quotient calculation (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- H04L 9/004: {for fault attacks}
- G06F 7/723: {Modular exponentiation (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- G06F 7/725: {over elliptic curves}
- G06F 7/727: {Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 (G06F7/728 takes precedence)}
- H04L 9/302: {involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes}
- 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

In a method for determining the modular inverse of a number, successive iterations are applied to two pairs each including a first variable and a second variable, such that at the end of each iteration and for each pair, the product of the second variable and of the number is equal to the first variable modulo a given module. Each iteration includes at least one division by two of the first variable of a first pair or of a second pair, or a combination of the first variable of the first pair and of the first variable of the second pair by addition or subtraction. At least some of the iterations including a combination by addition or subtraction include a step of storing the result of the combination in the first variable of a pair determined randomly from among the first pair and the second pair. An associated cryptographic processing device is also described.

## Claims

### Claim 1

Method for determining a modular inverse of a number, wherein successive iterations are applied to two pairs each comprising a first variable and a second variable such that at the end of each iteration and for each pair, a product of the second variable and of said number is equal to the first variable modulo a given module, the two pairs comprising a first pair and a second pair,
each iteration including at least one division of the first variable of the first pair or of the second pair by two, or a combination of the first variable of the first pair and of the first variable of the second pair by addition or subtraction,
wherein at least some of the iterations including a combination by addition or subtraction comprise a step of storing a result of said combination in the first variable of a pair determined randomly from among the first pair and the second pair.

### Claim 2 (depends on 1)

Method according to claim 1, wherein, when the number of iterations performed is greater than a threshold, each iteration including a combination by addition or subtraction comprises a step of storing the result of said combination in a variable with greater absolute value from among the first variable of the first pair and the first variable of the second pair.

### Claim 3 (depends on 2)

Method according to claim 2, comprising a prior step of determining the threshold by random draw.

### Claim 4 (depends on 1)

Method according to claim 1, wherein, for at least one iteration comprising a combination by addition or subtraction, the combination is made by addition if the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction if the first variable of the first pair and the first variable of the second pair have the same sign.

### Claim 5 (depends on 1)

Method according to claim 1, wherein each iteration comprising a division of the first variable of a given pair by two comprises, if the second variable of said given pair is even, a step of dividing the second variable of said given pair by two, and, if the second variable of said given pair is odd, a step of determining a sum of the second variable of said given pair and of the module, and a step of dividing said sum by two.

### Claim 6 (depends on 1)

Method according to claim 1, comprising a step of storing a random value in an additional variable wherein, in at least one iteration, if the additional variable is even, a division of the additional variable by two is performed, and, if the additional variable is odd, a sum of the additional variable and of the module is determined and a division of said sum by two is performed.

### Claim 7 (depends on 1)

Method according to claim 1, wherein each iteration including a combination by addition or subtraction comprises a corresponding combination of the second variable of the first pair and of the second variable of the second pair.

### Claim 8

Cryptographic processing device, comprising a unit for determining the modular inverse of a number designed to apply successive iterations to two pairs each comprising a first variable and a second variable such that at the end of each iteration and for each pair, a product of the second variable and of said number is equal to the first variable modulo a given module, the two pairs comprising a first pair and a second pair,
wherein said unit is designed to activate, at each iteration, at least one division block for dividing by two the first variable of the first pair or of the second pair, or a combination block for combining the first variable of the first pair and the first variable of the second pair by addition or subtraction,
wherein said unit is designed, for at least some of the iterations, to store a result produced by the combination block in the first variable of a pair determined randomly from among the first pair and the second pair.

### Claim 9 (depends on 8)

Cryptographic processing device according to claim 8, wherein the unit for determining the modular inverse is designed to, when the number of iterations performed is greater than a threshold, store the result produced by the combination block in the variable with greater absolute value from among the first variable of the first pair and the first variable of the second pair.

### Claim 10 (depends on 8)

Cryptographic processing device according to claim 8, wherein the combination block is designed to perform the combination by addition if the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction if the first variable of the first pair and the first variable of the second pair have the same sign.

### Claim 11 (depends on 2)

Method according to claim 2, wherein, for at least one iteration comprising a combination by addition or subtraction, the combination is made by addition if the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction if the first variable of the first pair and the first variable of the second pair have the same sign.

### Claim 12 (depends on 3)

Method according to claim 3, wherein, for at least one iteration comprising a combination by addition or subtraction, the combination is made by addition if the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction if the first variable of the first pair and the first variable of the second pair have the same sign.

### Claim 13 (depends on 2)

Method according to claim 2, wherein each iteration comprising a division of the first variable of a given pair by two comprises, if the second variable of said given pair is even, a step of dividing the second variable of said given pair by two, and, if the second variable of said given pair is odd, a step of determining a sum of the second variable of said given pair and of the module, and a step of dividing said sum by two.

### Claim 14 (depends on 3)

Method according to claim 3, wherein each iteration comprising a division of the first variable of a given pair by two comprises, if the second variable of said given pair is even, a step of dividing the second variable of said given pair by two, and, if the second variable of said given pair is odd, a step of determining a sum of the second variable of said given pair and of the module, and a step of dividing said sum by two.

### Claim 15 (depends on 2)

Method according to claim 2, comprising a step of storing a random value in an additional variable wherein, in at least one iteration, if the additional variable is even, a division of the additional variable by two is performed, and, if the additional variable is odd, a sum of the additional variable and of the module is determined and a division of said sum by two is performed.

### Claim 16 (depends on 3)

Method according to claim 3, comprising a step of storing a random value in an additional variable wherein, in at least one iteration, if the additional variable is even, a division of the additional variable by two is performed, and, if the additional variable is odd, a sum of the additional variable and of the module is determined and a division of said sum by two is performed.

### Claim 17 (depends on 2)

Method according to claim 2, wherein each iteration including a combination by addition or subtraction comprises a corresponding combination of the second variable of the first pair and of the second variable of the second pair.

### Claim 18 (depends on 3)

Method according to claim 3, wherein each iteration including a combination by addition or subtraction comprises a corresponding combination of the second variable of the first pair and of the second variable of the second pair.

### Claim 19 (depends on 9)

Cryptographic processing device according to claim 9, wherein the combination block is designed to perform the combination by addition if the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction if the first variable of the first pair and the first variable of the second pair have the same sign.
