# US 12,192,319 B2 · Apparatus and method for modular multiplication resistant to side-channel attack > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,192,319 B2 - Document ID: US12192319B2 - Status: Granted - Kind: B2 - Application number: 17/467,546 - Filed: 2021-09-07 - Published: 2022-07-21 - Granted: 2025-01-07 - Earliest claimed: 2021-01-20 - Assignees: Samsung Electronics Co., Ltd. - Applicants: Samsung Electronics Co., Ltd. - Inventors: Hyosun Hwang; Gisoo Seo; Jonghoon Shin; Hyojoon Jin; Ingoo Heo; Jinsu Hyun - Web page: https://patentgrep.com/patent/US12192319B2 ## CPC - H04L 9/004: {for fault attacks} - G06F 7/588: {Random number generators, i.e. based on natural stochastic processes} - G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06F 21/556: {involving covert channels, i.e. data leakage between processes (inhibiting the analysis of circuitry or operation with measures against power attack G06F21/755)} - G06F 21/72: in cryptographic circuits - G06F 21/755: {with measures against power attack} - G06F 21/78: to assure secure storage of data (address-based protection against unauthorised use of memory G06F12/14; record carriers for use with machines and with at least a part designed to carry digital markings G06K19/00) - H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords} - H04L 9/0869: {involving random numbers or seeds} - G06F 7/722: {Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence)} - G06F 21/55: Detecting local intrusion or implementing counter-measures - G06F 2207/7223: Randomisation as countermeasure against side channel attacks - H04L 2209/043: of tables, e.g. lookup, substitution or mapping - 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 device includes a random number generator configured to generate a random number, a memory configured to store at least one lookup table, and a processing circuit configured to generate a generator based on the random number, create the at least one lookup table based on the generator, and write the created at least one lookup table to the memory, wherein the processing circuit is configured to access the memory based on a first input and a second input, and generate a result of a modular multiplication of the first input by the second input based on the at least one lookup table. ## Claims ### Claim 1 A device comprising: a random number generator configured to generate a random number; a memory configured to store at least one lookup table; and a processing circuit configured to generate a generator based on the random number, create the at least one lookup table based on the generator, and write the at least one lookup table to the memory, wherein the processing circuit is configured to access the memory based on a first input and a second input, and generate a result of a modular multiplication of the first input by the second input based on the at least one lookup table, and wherein the processing circuit is configured to obtain a plurality of candidate generators smaller than a modulus of the modular multiplication based on the modulus of the modular multiplication, and select one of the plurality of candidate generators based on the random number. ### Claim 2 (depends on 1) The device of claim 1, wherein the processing circuit is configured to access the memory a constant number of times independently of values of the first input and the second input. ### Claim 3 (depends on 1) The device of claim 1, wherein the memory is configured to store the plurality of candidate generators, and wherein the processing circuit is configured to read the generator from the memory based on the random number. ### Claim 4 (depends on 1) The device of claim 1, wherein each of the plurality of candidate generators corresponds to g such that a finite field GF(p) is to be a union of {gi mod p; i=0, . . . , p−2} and {0}. ### Claim 5 (depends on 1) The device of claim 1, wherein the modulus of the modular multiplication is 3329, and wherein the processing circuit is configured to select one of 1536 candidate generators based on the random number. ### Claim 6 (depends on 1) The device of claim 1, wherein the processing circuit is further configured to perform the modular multiplication, and wherein the at least one lookup table is used for the modular multiplication. ### Claim 7 (depends on 1) The device of claim 1, wherein the at least one lookup table comprises: a first lookup table including input and output pairs of a function Log[gi mod p]=i where the generator is g and a modulus of the modular multiplication is p; and a second lookup table including input and output pairs of a function Exp[i]=gi mod p. ### Claim 8 (depends on 7) The device of claim 7, wherein, when the first input is a and the second input is b, the processing circuit is configured to obtain values respectively corresponding to Log[a] and Log[b] from the first lookup table, obtain a value corresponding to Exp[Log[a]+Log[b]] from the second lookup table, and generate the result of the modular multiplication as the value obtained from the second lookup table. ### Claim 9 (depends on 8) The device of claim 8, wherein each of the first lookup table and the second lookup table comprises (p−1) entries, and wherein, when a sum of Log[a] and Log[b] is greater than or equal to (p−1), the processing circuit is configured to obtain a value corresponding to Exp[Log[a]+Log[b]−p+1] from the second lookup table, and generate the result of the modular multiplication as the value obtained from the second lookup table. ### Claim 10 (depends on 8) The device of claim 8, wherein, when the modulus is p, the first lookup table comprises (p−1) entries and the second lookup table comprises 2(p−1) entries. ### Claim 11 (depends on 1) The device of claim 1, wherein the first input is a coefficient of a first polynomial, wherein the second input is a coefficient of a second polynomial, and wherein the result of the modular multiplication is used to calculate a coefficient of a polynomial obtained by multiplying the first polynomial by the second polynomial. ### Claim 12 A method for modular multiplication of a first input and a second input, the method comprising: generating a random number; generating a generator based on the random number; creating at least one lookup table based on the generator; writing the at least one lookup table to a memory; accessing the memory based on the first input and the second input; and generating a result of the modular multiplication based on the at least one lookup table, wherein the generating of the generator comprises: obtaining a plurality of candidate generators smaller than a modulus of the modular multiplication based on the modulus of the modular multiplication; and selecting one of the plurality of candidate generators based on the random number. ### Claim 13 (depends on 12) The method of claim 12, wherein the accessing of the memory is performed in the memory a constant number of times independently of values of the first input and the second input. ### Claim 14 (depends on 11) The method of claim 11, wherein the at least one lookup table comprises: a first lookup table including input and output pairs of a function Log[gi mod p]=i where the generator is g and a modulus of the modular multiplication is p; and a second lookup table including input and output pairs of a function Exp[i]=gi mod p. ### Claim 15 A non-transitory computer-readable recording medium including instructions executed by at least one processor, wherein the instructions cause the at least one processor to perform operations for modular multiplication of a first input and a second input, wherein the operations comprise: generating a generator based on a random number; creating at least one lookup table based on the generator; writing the at least one lookup table to a memory; accessing the memory based on the first input and the second input; and generating a result of the modular multiplication based on the at least one lookup table, wherein the generating of the generator comprises: obtaining a plurality of candidate generators smaller than a modulus of the modular multiplication based on the modulus of the modular multiplication; and selecting one of the plurality of candidate generators based on the random number. ### Claim 16 (depends on 15) The non-transitory computer-readable recording medium of claim 15, wherein the accessing of the memory is performed in the memory a constant number of times independently of values of the first input and the second input. ### Claim 17 (depends on 15) The non-transitory computer-readable recording medium of claim 15, wherein the at least one lookup table comprises: a first lookup table including input and output pairs of a function Log[gi mod p]=i where the generator is g and the modulus of the modular multiplication is p; and a second lookup table including input and output pairs of a function Exp[i]=gi mod p.