earticle

영어

Recently, the result of TinyECCK (Tiny Elliptic Curve Cryptosystem with Koblitz curve) shows that both field multiplication and reduction over GF(2m) are related to a heavy amount of duplicated memory accesses and that reducing the number of these duplications noticeably improves the performance of elliptic curve operations such as scalar multiplications, signing and verification. However, in case that the underlying word size is expanded from 8-bit to 16-bit or 32-bit, the efficiency of the proposed techniques in TinyECCK is decreased because the number of memory accesses to load or store an element in GF(2m) is almost halved. Therefore, in this paper, we propose a technique which makes left-to-right comb method suitable on expanded word sizes and present the performance of TinyECCK16 which is implemented with the proposed multiplication algorithm. With the proposed multiplication algorithm, 17-23% of running time in elliptic curve operations such as scalar multiplication, signing and verification is saved. Furthermore, TinyECCK16 is superior to existing ECC softwares implemented on 16-bit Tmote Sky sensor mote with regards to running time and memory requirement. TinyECCK16 with 5TNAF can generate a signature and verify it within 0.81 and 1.35secs with 14,422-byte of ROM and 1,750-byte of RAM.

한국어

최근, 8-bit MICAz 센서모트 상에서 구현된 TinyECCK (Tiny Elliptic Curve Cryptosystem with Koblitz curve)의 연구 결과는 유한체 GF(2m) 상에서의 곱셈과 감산 연산은 많은 수의 중복된 메모리 접근에 연관되어 있으며, 이러한 불필요한 메모리 접근 연산을 줄임으로써 전체적인 타원곡선 암호 연산의 성능을 현저히 높일 수 있음을 보였다. 하지만, 사용되는 워드의 비트가 8-bit에서 16-bit 혹은 32-bit로 확장될 경우, 메모리 상에 존재하는 GF(2m)상의 원소에 접근하기 위해 사용되는 메모리 접근의 횟수가 줄어들기 때문에, TinyECCK에 적용된 곱셈과 감산 알고리즘의 효율성은 떨어지게 된다. 따라서 본 논문에서는 GF(2m)의 곱셈 연산에서 많이 사용되는 left-to-right comb 방법을 16-bit 및 32-bit 환경에 맞도록 변형하고 이를 이용하여 16-bit Tmote Sky 모트에서 TinyECCK의 확장 버전인 TinyECCK16을 구현하여 그 성능을 제시한다. 제안 곱셈 방법을 통하여 TinyECCK16의 타원곡선 암호연산의 성능은 약, 17-23% 정도 향상될 수 있었으며, 또한 TinyECCK16은 기존에 GF(p) 및 GF(2m)상에서 소프트웨어적으로 구현된 것들과 비교하여 메모리 사용량 및 연산 시간 측면에서 가장 뛰어나다. 5TNAF를 사용한 TinyECCK16은 14,422-byte의 ROM과 1,750-byte의 RAM을 이용하여 0.81초 안에 하나의 전자 서명을 생성할 수 있으며, 또한 이것을 1.35초 안에 검증할 수 있다.