Inverse calculation circuit, inverse calculation method, and storage medium encoded with computer-readable computer program code

An inverse calculation method used for elliptic curve cryptography, the method comprising:

• providing a random number generator that generates a first random number and a second random number;
• and
• providing an inverter that receives a plurality of first bits expressing a first element of a finite field as first inputs, wherein the first element is a (n−1)-degree polynomial, and receiving a plurality of second bits expressing a second element of the finite field as second inputs, wherein the second element is a n-degree polynomial, and in response to the first random number and the second random number, outputting a plurality of third bits expressing an inverse element of the first element, wherein the inverse element is a (n−1)-degree polynomial,
• wherein the inverter comprises:
• a first register;
• a second register;
• a third register;
• a fourth register;
• a first right shift register shifting output data of the first register one bit to the right;
• a second right shift register shifting output data of the second register one bit to the right;
• a first XOR gate performing a bitwise XOR operation between the output data of the first register and the output data of the second register;
• a third right shift register shifting output data of the first XOR gate one bit to the right;
• a first multiplexer selecting any one of the plurality of first bits, the output data of the first register, output data of the first right shift register, and output data of the third right shift register, and providing the selected data as input data of the first register;
• a second multiplexer selecting any one of the plurality of second bits, the output data of the second register, output data of the second right shift register, and the output data of the third right shift register, and providing the selected data as input data of the second register;
• a first left shift register shifting output data of the third register one bit to the left;
• a second left shift register shifting output data of the fourth register one bit to the left;
• a second XOR gate performing a bitwise XOR operation between the output data of the third register and the output data of the fourth register;
• a third XOR gate performing a bitwise XOR operation between the output data of the third register and the plurality of second bits;
• a fourth XOR gate performing a bitwise XOR operation between the output data of the fourth register and the plurality of second bits;
• a third left shift register shifting output data of the third XOR gate one bit to the left;
• a fourth left shift register shifting output data of the fourth register one bit to the left;
• a third multiplexer selecting any one of the output data of the third register, output data of the first left shift register, output data of the second XOR gate, and output data of the third left shift register, and providing the selected data as input data of the third register;
• and
• a fourth multiplexer selecting any one of the output data of the fourth register, output data of the second left shift register, the output data of the second XOR gate, and output data of the fourth left shift register, and providing the selected data as input data of the fourth register,
• wherein the output data of the third register corresponds to the plurality of third bits expressing the inverse element of the first element.

A computer readable non-transitory storage medium having embodied thereon a computer program executed by a cryptography application circuit to perform an inverse calculation method used for elliptic curve cryptography, the method comprising:

• generating a first random number and a second random number;
• and
• receiving a plurality of first bits expressing a first element of a finite field as first inputs, wherein the first element is a (n−1)-degree polynomial, and receiving a plurality of second bits expressing a second element of the finite field as second inputs, wherein the second element is a n-degree polynomial, and in response to the first random number and the second random number, outputting a plurality of third bits expressing an inverse element of the first element, wherein the inverse element is a (n−1)-degree polynomial,
• wherein the cryptography application circuit comprises:
• a random number generator;
• and
• an inverter,
• wherein the inverter comprises:
• a first register;
• a second register;
• a third register;
• a fourth register;
• a first right shift register shifting output data of the first register one bit to the right;
• a second right shift register shifting output data of the second register one bit to the right;
• a first XOR gate performing a bitwise XOR operation between the output data of the first register and the output data of the second register;
• a third right shift register shifting output data of the first XOR gate one bit to the right;
• a first multiplexer selecting any one of the plurality of first bits, the output data of the first register, output data of the first right shift register, and output data of the third right shift register, and providing the selected data as input data of the first register;
• a second multiplexer selecting any one of the plurality of second bits, the output data of the second register, output data of the second right shift register, and the output data of the third right shift register, and providing the selected data as input data of the second register;
• a first left shift register shifting output data of the third register one bit to the left;
• a second left shift register shifting output data of the fourth register one bit to the left;
• a second XOR gate performing a bitwise XOR operation between the output data of the third register and the output data of the fourth register;
• a third XOR gate performing a bitwise XOR operation between the output data of the third register and the plurality of second bits;
• a fourth XOR gate performing a bitwise XOR operation between the output data of the fourth register and the plurality of second bits;
• a third left shift register shifting output data of the third XOR gate one bit to the left;
• a fourth left shift register shifting output data of the fourth register one bit to the left;
• a third multiplexer selecting any one of the output data of the third register, output data of the first left shift register, output data of the second XOR gate, and output data of the third left shift register, and providing the selected data as input data of the third register;
• and
• a fourth multiplexer selecting any one of the output data of the fourth register, output data of the second left shift register, the output data of the second XOR gate, and output data of the fourth left shift register, and providing the selected data as input data of the fourth register,
• wherein the output data of the third register corresponds to the plurality of third bits expressing the inverse element of the first element.