# US 11,029,922 B2 · 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 11,029,922 B2 - Document ID: US11029922B2 - Status: Granted - Kind: B2 - Application number: 16/426,824 - Filed: 2019-05-30 - Published: 2019-12-12 - Granted: 2021-06-08 - Earliest claimed: 2018-06-08 - Assignees: Idemia France - Applicants: IDEMIA France - Inventors: Thomas Chabrier; Gilles Piret - Web page: https://patentgrep.com/patent/US11029922B2 ## 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 A method of implementing a cryptographic algorithm using a modular inverse of a number, the method comprising: storing cryptographic data including the number at an electronic entity; applying, at the electronic entity, successive iterations to two pairs each comprising a first variable and a second variable such that at an end of each iteration and for each pair, a product of the second variable and said number is equal to the first variable modulo a given module, the two pairs comprising a first pair and a second pair, each of the iterations 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, at least some of the iterations including a combination by addition or subtraction comprising modifying the first variable of a pair determined randomly from among the first pair and the second pair by a result of the combination; after the iterations are performed, determining the modular inverse of the number using the second variable of the first pair or the second variable of the second pair; implementing the cryptographic algorithm using the determined modular inverse; and one of (i) transmitting a result of the implemented cryptographic algorithm to another electronic entity, and (ii) storing the result of the implemented cryptographic algorithm in a memory of the electronic entity. ### Claim 2 (depends on 1) The method according to claim 1, wherein, when the number of iterations performed is greater than a threshold, each of the iterations including a combination by addition or subtraction comprises modifying one of the first variable of the first pair and the first variable of the second pair having the greater absolute value by the result of the combination. ### Claim 3 (depends on 2) The method according to claim 2, further comprising determining the threshold by random draw. ### Claim 4 (depends on 1) The method according to claim 1, wherein, for at least one of the iterations comprising the combination by addition or subtraction, the combination is made by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign. ### Claim 5 (depends on 1) The method according to claim 1, wherein each of the iterations comprising a division of the first variable of a given pair by two comprises, when the second variable of said given pair is even, dividing the second variable of said given pair by two, and when the second variable of said given pair is odd, determining a sum of the second variable of said given pair and of the module, and dividing said sum by two. ### Claim 6 (depends on 1) The method according to claim 1, further comprising modifying an additional variable by a random value, wherein, in at least one iteration, when the additional variable is even, performing a division of the additional variable by two, and when the additional variable is odd, determining a sum of the additional variable and the module, and performing a division of said sum by two. ### Claim 7 (depends on 1) The method according to claim 1, wherein each of the iterations including the 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 (depends on 1) The cryptographic processing device according to claim 1, wherein the number is one of (i) a public exponent of the public key of an asymmetric encryption scheme, (ii) a secret factor of an RSA algorithm module, (iii), a scalar number, and (iv) a multiplicative mask. ### Claim 9 (depends on 2) The method according to claim 2, wherein, for at least one of the iterations comprising the combination by addition or subtraction, the combination is made by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign. ### Claim 10 (depends on 2) The method according to claim 2, wherein each of the iterations comprising a division of the first variable of a given pair by two comprises, when the second variable of said given pair is even, dividing the second variable of said given pair by two, and when the second variable of said given pair is odd, determining a sum of the second variable of said given pair and of the module, and dividing said sum by two. ### Claim 11 (depends on 2) The method according to claim 2, further comprising modifying an additional variable by a random value, wherein, in at least one iteration, when the additional variable is even, performing a division of the additional variable by two, and when the additional variable is odd, determining a sum of the additional variable and the module, and performing a division of said sum by two. ### Claim 12 (depends on 2) The method according to claim 2, wherein each of the iterations including the 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 13 (depends on 3) The method according to claim 3, wherein, for at least one of the iterations comprising the combination by addition or subtraction, the combination is made by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign. ### Claim 14 (depends on 3) The method according to claim 3, wherein each of the iterations comprising a division of the first variable of a given pair by two comprises, when the second variable of said given pair is even, dividing the second variable of said given pair by two, and when the second variable of said given pair is odd, determining a sum of the second variable of said given pair and of the module, and dividing said sum by two. ### Claim 15 (depends on 3) The method according to claim 3, further comprising modifying an additional variable by a random value, wherein, in at least one iteration, when the additional variable is even, performing a division of the additional variable by two, and when the additional variable is odd, determining a sum of the additional variable and the module, and performing a division of said sum by two. ### Claim 16 (depends on 3) The method according to claim 3, wherein each of the iterations including the 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 17 A cryptographic processing device, comprising: a memory configured to store cryptographic data including a number; and at least one processor configured to: determine a modular inverse of the number stored in the memory by applying successive iterations to two pairs each comprising a first variable and a second variable such that at an end of each iteration and for each pair, a product of the second variable and said number is equal to the first variable modulo a given module, the two pairs comprising a first pair and a second pair, the at least one processor being configured to activate, at each of the iterations, 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, the at least one processor being configured, for at least some of the iterations, to modify the first variable of a pair determined randomly from among the first pair and the second pair by a result of the combination, after the iterations are performed, determine the modular inverse of the number using the second variable of the first pair or the second variable of the second pair, implement the cryptographic algorithm using the determined modular inverse, and one of (i) transmit a result of the implemented cryptographic algorithm to another cryptographic processing device, and (ii) store the result of the implemented cryptographic algorithm in the memory. ### Claim 18 (depends on 17) The cryptographic processing device according to claim 17, wherein the at least one processor is configured to, when the number of iterations performed is greater than a threshold, modify one of the first variable of the first pair and the first variable of the second pair having the greater absolute value by the result of the combination. ### Claim 19 (depends on 18) The cryptographic processing device according to claim 18, wherein the combination block performs the combination by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign. ### Claim 20 (depends on 17) The cryptographic processing device according to claim 17, wherein the combination block performs the combination by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign.