8비트 센서 노드 상에서 효율적인 공개키 암호를 위한 다정도 제곱 연산의 최적화

Multiprecision squaring is one of the most significant algorithms in the core public key cryptography operation. The aim of this work is to present a new improved squaring algorithm compared with the MIRACL’s multiprecision squaring algorithm in which the previous work [1] on multiprecision multiplication is implemented.
First, previous works on multiprecision multiplication and standard squaring are analyzed. Then, our new Lazy Doubling squaring algorithm is introduced.
In MIRACLE library [3], Scott’s Carry-Catcher Hybrid multiplication technique [1] is applied to implementation of multiprecision multiplication and squaring. Experimental results of the Carry- Catcher hybrid squaring algorithm and the proposed Lazy Doubling squaring algorithm both of which are tested on Atmega128 CPU show that proposed idea has achieved significant performance improvements.
The proposed Lazy Doubling Squaring algorithm reduces addition instructions by the fact a0*2+a1*2+...+an-1*2+an*2=(a0+a1+...+an-1+an)*2 while the standard squaring algorithm reduces multiplication instructions by the fact Sij=xi*xj=Sji. Experimental results show that the proposed squaring method is 25% faster than that in MIRACL.