Since 1976, Deffie and Hellman proposed public-key cryptography, many public-key cryptosystems have been developed. But, most of them require very large key-space and take much time in encryption and decryption. Therefore they cannot be used in various applications.
In 1985, Koblitz and Miller independently proposed an elliptic curve cryptosystem (ECC), which is based on the discrete logarithm problem over the elliptic curve additive group defined on the finite field. This problem is much more difficult than the previous ones such as integer factorization. So, ECC manages only 140 ~ 200-bit key-space so as to get the same security level as 512 ~ 1024-bit RSA or ElGamal cryptosystem. The performance of ECC depends on the efficiency of finite field operations, especially the multiplication and squaring that take most time in ECC operations.
We present fast multiplication and squaring algorithms in a finite field $F_p^m$ which is based on polynomial basis, and the result of software implementation. Finite field multiplication and squaring operations take the most time in elliptic curve operation. So, efficient multiplication and squaring can help fast elliptic curve operation. The efficiency of finite field multiplication and squaring depends on the number of single-precision multiplications. Previous work did not provide any particular algorithm for finite field squaring operation, then use the same procedure as general finite field multiplication. We show that finite field squaring can be optimized than the means of usual multiplication.
We improved about 27% speed of finite field multiplication and about 40% of squaring compared with ordinary multiplication.
1976년 Deffie와 Hellman에 의해 공개키 암호시스템이 제안된 이래 많은 종류의 암호시스템이 개발되었으나, 대부분은 키 공간이 매우 넓어 암호화와 복호화에 많은 계산량이 필요하며, 계산시간이 지나치게 오래 걸리므로 실용적이지 못하다. 이러한 문제점을 해결하기 위하여, 1985년 Koblitz와 Miller는 각각 유한체 상에서 정의되는 타원곡선에서의 이산대수 문제를 기반으로 하는 타원곡선 암호시스템을 제안하였다. 이러한 문제는 정수의 인수분해 문제와 같은 기존의 암호시스템에서 사용하던 문제들보다 훨씬 어려워, RSA나 ElGamal 암호법에서 512 $\sim$ 1024 비트로 제공할 수 있는 안전도를 140 $\sim$ 200 비트 정도로 제공할 수 있게 되었다. 타원곡선 암호시스템의 성능은 유한체 연산의 효율성에 의존하며, 특히 곱셈과 제곱 연산은 시간이 가장 많이 걸리는 연산이다. 본 논문에서는 타원곡선이 정의되는 다항식 기저로 표현되는 유한체 $F_{p^m}$ 상에서의 곱셈과 제곱 연산을 빠르게 수행할 수 있는 알고리즘을 제안하고, 소프트웨어로 구현하여 성능을 측정 하였다. 유한체 상에서의 곱셈과 제곱 연산은 다른 연산에 비하여 사용되는 빈도가 높고 많은 시간이 소요되므로, 이들 연산의 속도를 빠르게 하는 것이 타원곡선 암호시스템 전체의 성능 개선에 가장 큰 영향을 미친다. 유한체 곱셈과 제곱 연산의 성능은 여기에 필요한 단정도 곱셈 횟수에 비례한다. 본 논문에서 제안하는 유한체 곱셈 연산은 기존의 방법에 비하여 최대 27\%의 성능 향상을 보인다. 유한체 제곱 연산은 기존의 연구에서 곱셈과 같은 방법으로 계산되었지만, 본 논문에서는 제곱을 위한 새로운 알고리즘을 제안하여 최대 27\%와 40\% 정도의 성능 향상을 보인다.
