Apparatus and method for modular multiplication resistant to side-channel attack

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.

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.