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

Abstract

Multiprecision Squaring 은 공개키 알고리즘을 구성하는 연산 중에서 가장 중요한 연산 중 하나이다. 본 논문에서는 기존의 Multiprecision Squaring 알고리즘을 개선하여 연산 양을 줄이고 레지스터를 보다 효율적으로 사용하는 방법들을 제시하고 구현하였다. 기존에 연구된 Multiprecision 곱셈 알고리즘과 표준 Squaring 알고리즘을 소개하고, MIRACL에 구현된 Multiprecision 알고리즘의 성능을 테스트 하기 위해 RSA 의 복호화 로직의 수행 속도를 측정하였다. Gura가 [2]에 제시한 atmega128 상에서의 1024bit decryption 수행 속도는 10.99초였으나 Scott의 Carry-Catcher Hybrid 곱셈 알고리즘이 적용된 MIRACL 라이브러리를 이용한 구현은 9.2초로 더 빠른 것을 확인할 수 있었다. Scott이 [1]에서 제안한 Carry-Catcher Hybrid 곱셈 알고리즘은 Gura가 제안한 Hybrid 곱셈 알고리즘을 계승 발전시킨 것으로 MIRACL 라이브러리에 구현되어 있으며, 동일한 Carry-Catcher Hybrid 방법으로 Multiprecision Squaring 알고리즘도 구현되어 있다. 본 논문에서 이 Carry-Catcher Hybrid Squaring 알고리즘을 발전시켜 보다 효율적인 Squaring 알고리즘인 Lazy Doubling Squaring 알고리즘을 제안하고 구현하였으며, atmega128상에서 성능테스터를 수행하여 Carry-Catcher Hybrid Squaring 알고리즘과 비교하여 더 효율적인 알고리즘임을 보였다. 표준 Squaring 알고리즘이 S_(ij) = x_(i) * x_(j) = S_(ji) 인 사실을 기반으로 곱셈의 횟수를 절반 가까이 줄인 알고리즘이라면 본 논문에서 제시한 Lazy Doubling Squaring 알고리즘은 a_(0)*2+ a₁*2+…+ a_(n-1)*2+ a_(n)*2=( a_(0)+a₁+…+a_(n-1)+a_(n))*2 라는 사실을 기반으로 하여 doubling 연산 횟수를 획기적으로 줄인 알고리즘으로, MIRACL에 구현되어 있는 Multiprecision Squaring 알고리즘 보다 atmega128상에서 약 25% 정도의 향상된 성능의 알고리즘임을 보였다. 그리고 ADCC라는 새로운 CPU연산자를 제안하고, 이 연산자가 추가된다면 제안한 Squaring 알고리즘의 속도를 12.7% 더 향상 시킬 수 있으며, Scott의 Carry-Catcher Hybrid 곱셈 알고리즘에 적용해도 15%정도의 속도가 향상 될 수 있음을 보였다.; 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, 1024bit RSA decryption performance tests were done with the MIRACL’s RSA implementation in order to measure the performance of the multiprecision algorithm in it. MIRACL library in which Scott’s Carry-Catcher Hybrid multiplication algorithm is implemented runs in 9.2 seconds proving that it is much faster than Gura’s RSA decryption test [2] which runs in 10.99 seconds. In MIRACLE library, Scott’s Carry-Catcher Hybrid multiplication technique 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 a_(0)*2+ a₁*2+…+ a_(n-1)*2+ a_(n)*2=( a_(0)+a₁+…+a_(n-1)+a_(n))*2 while the standard squaring algorithm reduces multiplication instructions by the fact S_(ij) = x_(i) * x_(j) = S_(ji). Experimental results show that the proposed squaring method is 25% faster than that in MIRACL. Furthermore, a new CPU instruction, ADCC, is designed. It is shown that with this instruction, proposed squaring algorithm and Scott’s carry-catcher hybrid multiplication algorithm are speeded up at 12.7 % and 15%, respectively.