Miyaji Laboratory

In recent years，IoT devices have supported the modern information society．However，security vul nerabilities can cause serious damage．In particular，side-channel attacks that exploit the difference in processing time during operations to decipher ciphers and obtain information have been developed， making the security of IoT devices more and more important．The inverse operation is used in many cryptographic schemes，and can be computed using Extended Euclid 's Algorithm or Fermat 's Little Theorem as a main algorithm．These algorithms iterate a main algorithm ．Therefore，the performance of the inverse operation is determined by the computational complexity of the main algorithm and the number of its iterations. To be resistant to side-channel attacks，the number of iterations must remain constant and independent of the input．JIN and Miyaji proposed an algorithm in which the number of loops depends on the prime p. The computational complexity for a p-size input is 2 subtractions，2 shifts，10 multiplications，6 xor，1 comparison. At the word level, the computational complexity is 3 and operations，1 or operation，1 negation，and 4 array selections in a single loop．In order to eliminate conditional branches，the main algorithm relies on xor operations，stores the results of the operations in arrays，and selects the output accordingly. Here, the array selection refers to the amount of computation required to select the correct result．Additionally, PORNIN proposed an inverse algorithm that takes into account a register capacity of 2k．In this study, we improve upon JIN and Miyaji's algorithm by reducing the number of and,not and select operations by 1, 2, and 4 times, respectively, in the word-size computations. Furthermore, we reduce the total number of iterations by two. Using an 11th Gen In tel(R) Core(TM) i5-1135G7 @ 2.40GHz as our experimental environment，we confirm that the improved algorithm is 8.5% faster than the inverse algorithm by JIN and Miyaji.