# US 2021/0243006 A1 · Integrated circuit for modular multiplication of two integers for a cryptographic method, and method for the cryptographic processing of data based on modular multiplication > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0243006 A1 - Document ID: US20210243006A1 - Status: Published application - Kind: A1 - Application number: 17/161,716 - Filed: 2021-01-29 - Published: 2021-08-05 - Earliest claimed: 2020-01-31 - Assignees: Infineon Technologies AG - Applicants: Infineon Technologies AG - Inventors: Bernd MEYER - Web page: https://patentgrep.com/patent/US20210243006A1 ## CPC - G06F 7/728: {using Montgomery reduction} - G06F 7/5443: {Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00)} - G06F 7/722: {Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Integrated circuits for modular multiplication of two integers for a cryptographic method, and methods for the cryptographic processing of data based on modular multiplication are herein disclosed. For example, an integrated circuit for modular multiplication of two integers for a cryptographic method has a processor that represents the integers to be multiplied in Montgomery representation with a specified Montgomery representation parameter and a specified modulus, and calculates the result of the modular multiplication of the integers to be multiplied in Montgomery representation iteratively from the least significant word to the most significant word, where for a word calculated in an iteration, the product of the word with a specified factor is added to the words of subsequent iterations, the specified factor given by the product of the negative inverse of the least significant word of the modulus and the modulus, without the least significant word of the product, plus one. ## Claims ### Claim 1 An integrated circuit for the modular multiplication of two integers for a cryptographic method, the integrated circuit comprising: a processor configured to: represent two integers to be multiplied in Montgomery representation with a specified Montgomery representation parameter and a specified modulus, and calculate a result of a modular multiplication of the two integers to be multiplied in Montgomery representation iteratively from a least significant word to a most significant word, wherein, for a word calculated in an iteration, a product of the word and a specified factor is added to words of subsequent iterations, wherein the specified factor is given by a product of a negative inverse of a least significant word of the specified modulus and the specified modulus, without the least significant word of the product, plus one. ### Claim 2 (depends on 1) The integrated circuit as claimed in claim 1, further comprising: a memory, wherein, for a classification of the specified modulus into words according to a specified word width, the processor is further configured to: pre-calculate the product of the negative inverse of the least significant word of the specified modulus and the specified modulus, and store at least part of the product in the memory in the form of a constant derived therefrom; and wherein the processor is further configured to calculate the specified factor from the stored constant. ### Claim 3 (depends on 1) The integrated circuit as claimed in claim 1, wherein the processor is further configured to calculate scalar products in order to calculate the result of the modular multiplication of the two integers to be multiplied in Montgomery representation. ### Claim 4 (depends on 3) The integrated circuit as claimed in claim 3, wherein the processor is further configured to: calculate scalar products between words of the two integers to be multiplied, and calculate scalar products of words of the result of the modular multiplication of the two integers to be multiplied in Montgomery representation and words of the specified factor. ### Claim 5 (depends on 3) The integrated circuit as claimed in claim 3, wherein the processor is configured to calculate the scalar products by means of pipelining. ### Claim 6 (depends on 3) The integrated circuit as claimed in claim 3, wherein the processor comprises at least one multiplier-accumulator unit configured to calculate the scalar products by means of the at least one multiplier-accumulator unit. ### Claim 7 (depends on 1) The integrated circuit as claimed in claim 1, wherein, for each of a number of less significant words of the result of multiplying the two integers to be multiplied in Montgomery representation equal to the number of words of the specified Montgomery representation parameter, the processor is further configured to add the product of the word and a specified factor to the words of subsequent iterations. ### Claim 8 (depends on 1) The integrated circuit as claimed in claim 1, wherein, for each iteration up to an iteration corresponding to a number of words of the specified Montgomery representation parameter, the processor is further configured to add the product of the word calculated in the iteration and the specified factor to the words of subsequent iterations. ### Claim 9 (depends on 1) The integrated circuit as claimed in claim 1, wherein a number of words of the specified Montgomery representation parameter is equal to a number of words of the two integers to be multiplied in Montgomery representation and a number of the specified modulus. ### Claim 10 (depends on 1) The integrated circuit as claimed in claim 1, wherein a specified word width is a register width or bus width of the processor. ### Claim 11 (depends on 1) The integrated circuit as claimed in claim 1, wherein the specified Montgomery representation parameter is a power of two and the specified modulus is odd. ### Claim 12 (depends on 1) The integrated circuit as claimed in claim 1, wherein the processor is further configured to calculate a product of the modular multiplication of the two integers to be multiplied in Montgomery representation from the result of the modular multiplication of the two integers to be multiplied in Montgomery representation, by modular division by the specified Montgomery representation parameter. ### Claim 13 (depends on 1) The integrated circuit as claimed in claim 1, wherein the cryptographic method is an asymmetric method for signing, decrypting or encrypting data, for signature verification or for key exchange. ### Claim 14 (depends on 1) The integrated circuit as claimed in claim 1, further comprising: a memory containing cryptographic data to be processed and a cryptographic key, wherein the processor is further configured to form the two integers to be multiplied in Montgomery representation from the cryptographic data and/or the cryptographic key. ### Claim 15 A method for cryptographic processing of data based on modular multiplication, the method comprising: representing two integers to be multiplied in Montgomery representation with a specified Montgomery representation parameter and a specified modulus, and calculating a result of a modular multiplication of the two integers to be multiplied in Montgomery representation iteratively from a least significant word to a most significant word, wherein, for a word calculated in an iteration, a product of the word and a specified factor is added to words of subsequent iterations, wherein the specified factor is given by a product of a negative inverse of a least significant word of the specified modulus and the specified modulus, without the least significant word of the product, plus one. ### Claim 16 (depends on 15) The method as claimed in claim 15, further comprising: for a classification of the specified modulus into words according to a specified word width: pre-calculating the product of the negative inverse of the least significant word of the specified modulus and the specified modulus, and storing at least part of the product in a memory in the form of a constant derived therefrom; and calculating the specified factor from the stored constant. ### Claim 17 (depends on 15) The method as claimed in claim 15, further comprising: calculating scalar products in order to calculate the result of the modular multiplication of the two integers to be multiplied in Montgomery representation. ### Claim 18 (depends on 17) The method as claimed in claim 17, further comprising: calculating scalar products between words of the two integers to be multiplied; and calculating scalar products of words of the result of the modular multiplication of the two integers to be multiplied in Montgomery representation and words of the specified factor. ### Claim 19 (depends on 17) The method as claimed in claim 17, wherein calculating the scalar products comprises calculating the scalar products by means of pipelining. ### Claim 20 (depends on 17) The method as claimed in claim 17, wherein calculating the scalar products comprises calculating the scalar products by means of at least one multiplier-accumulator unit.