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

김일희; 박용수; 이윤호

8 비트 센서 노드 상에서 효율적인 공개키 암호를 위한 다정도 제곱 연산의 최적화
Optimizing Multiprecision Squaring for Efficient Public Key Cryptography on 8-bit Sensor Nodes 원문보기

정보과학회논문지. Journal of KIISE. 시스템 및 이론, v.36 no.6, 2009년, pp.502 - 510

김일희 (한양대학교 전자컴퓨터통신공학과) , 박용수 (한양대학교 정보통신대학) , 이윤호 (영남대학교 정보통신공학과)

초록
AI-Helper

Multiprecision Squaring은 공개키 알고리즘을 구성하는 연산 중에서 가장 중요한 연산 중 하나이다. 본 논문에서는 기존의 Multiprecision Squaring 알고리즘을 개선하여 연산 양을 줄임으로 성능을 항상시키는 Squaring 기법들을 제시하고 구현하였다. Scott이[1]에서 제안한 Carry-Catcher Hybrid 곱셈 알고리즘은 Gura가 제안한 Hybrid 곱셈 알고리즘[2]을 계승 발전시킨 것으로 MRACL 라이브러리에 구현되어 있으며, Carry-Catcher Hybrid 방법 사용한 Multiprecision Squaring 알고리즘도 MIRACL에 함께 구현되어 있다. 본 논문에서 이 Carry-Catcher Hybrid Squaring 알고리즘을 발전시켜 보다 효율적인 Squaring 알고리즘인 Lazy Doubling Squaring 알고리즘을 제안하고 구현하였으며, atmega128상에서 성능테스터를 수행하여 Carry-Catcher Hybrid Squaring 알고리즘과 비교하여 더 효율적인 알고리즘임을 보였다. 표준 Squaring 알고리즘이 $S_{ij}\;=\;x_i\;{\ast}\;x_j\;=\;S_{ij}$인 사실을 기반으로 곱셈의 횟수를 절반 가까이 줄인 알고리즘이라면 본 논문에서 제시한 Lazy Doubling Squaring 알고리즘은 $a_0\;{\ast}\;2\;+\;a_1\;{\ast}\;2\;+\;...\;+\;a_{n-1}\;{\ast}\;2\;+\;a_n\;{\ast}\;2\;=\;(a_0\;+\;a_1\;+\;...\;+\;a_{n-1}\;+\;a_n)\;{\ast}\;2$ 라는 사실을 기반으로 하여 doubling 연산 횟수를 획기적으로 줄인 알고리즘으로, MIRACL에 구현되어 있는 Multiprecision Squaring 알고리즘 보다 atmega128상에서 약 25% 정도의 빠른 결과를 얻을 수 있었으며, 저자가 아는 바로는 현재까지 나온 어떤 방법보다 빠르다.

Abstract ▼ AI-Helper

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 multi precision 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 $a_0\;{\ast}\;2\;+\;a_1\;{\ast}\;2\;+\;...\;+\;a_{n-1}\;{\ast}\;2\;+\;a_n\;{\ast}\;2\;=\;(a_0\;+\;a_1\;+\;...\;+\;a_{n-1}\;+\;a_n)\;{\ast}\;2$ while the standard squaring algorithm reduces multiplication instructions by the fact $S_{ij}\;=\;x_i\;{\ast}\;x_j\;=\;S_{ij}$. Experimental results show that the proposed squaring method is 25% faster than that in MIRACL.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 센서노드나 스마트카드와 같은 저전력 CPU에서 효율적인 Carry-Catcher Hybrid 알고리즘을개선하여 보다 효율적인 Squaring 알고리즘을 제안하였다. 제안하는 알고리즘은 Atmel AVR 플랫폼상에서 MIRACL에 구현되어 있는 Carry-Catcher Hybrid Squaring 알고리즘 보다 월등한 연산 효율성을 보인다.

제안 방법

본 논문의 구성은 2장에서 기존에 연구되어 활용되고있는 Multiprecision 곱셈 및 표준 Squaring 알고리즘을 소개하고, 3장에서는 Carry-Catcher Hybrid S않侦- aring 의 성능을 향상시킨 Lazy Doubling Squaring 기법을 소개와 향상된 성능측정 결과를 Carry-Catcher Hybrid Squaring 알고리즘과 비교하여 제시하였다. 마지막으로 4장에서는 결론과 향후 연구방향을 기술한다,
위의개념적인 내용을 바탕으로 제안 방법을 설계하였다. 제안 방법의 첫번째 핵심은 아래와 같이 기존의 Carry- Catcher Hybrid Squaring 방법에 위의 Lazy Doubling Squaring 방법을 적용시킬 경우 추가적으로 요구되는레지스터가 발생하지 않게 되는 것이다.
위의개념적인 내용을 바탕으로 제안 방법을 설계하였다. 제안 방법의 첫번째 핵심은 아래와 같이 기존의 Carry- Catcher Hybrid Squaring 방법에 위의 Lazy Doubling Squaring 방법을 적용시킬 경우 추가적으로 요구되는레지스터가 발생하지 않게 되는 것이다. 제안 방법과 Carry-Catcher Hybrid Squaring 방법과 비교해 보면, 그림 7의 오른쪽 그림과 같이 레지스터 m0-m7이 그림 5의 오른쪽 그림의 S0-S7과 동일한 역할을 수행하게 된다.

이론/모형

, 즉. Hybrid 단위 내의 각 수를 곱해주는 내부 알고리즘으로는 가용한 레지스터를 가능한 많이 이용하도록 Row-Wise 곱셈 알고리즘을 사용하고, Hybrid 단위끼리 곱해주는 외부 알고리즘으로는 carry 처리의 효율을향상 시키기 위해 Colum-Wise 곱셈을 사용한다.
본방법도 Hybird 기법을 이용한다. Hybrid 단위 내부의 곱셈을 도식한 그림 5의 좌측 그림을 보면 a0 * a4는 a4 * a0 와 같으므로 각각을 두 번씩 곱하는 것이 아니라 한 번만 곱하고 그 곱한 값을 doubling하는 것을 통해 곱셈 횟수를 줄이고 있는 것을 확인할 수 있다.

성능/효과

전체 N 개의 Hybrid 단위 제곱에서 위와 같은 s이f 곱셈의 경우는 N번 발생한다. 결과적으로 doubling 으로 인해 야기되는 총 덧셈 횟수는 d*N₂(N-l)/2 + (d2- 也 / 2 * N 二 Nd(Nd-l)/2 번이 발생한다. 그렇지만 각 곱셈의결과가 2바이트 단위이므로 최종적으로 Nd(Nd-1) 번의덧셈이 발생한다.
우리는 MIRACL에 구현되어 있는 Multiprecision Squaring을 고쳐서 원 알고리즘 보다 상에서 약 25% 정도의 빼른 결과를 얻을 수 있었으며, 저자가 아는 바로는 현재까지 나온 어떤 방법보다 빠르다. 더 나아가, ADCC라는 새로운 CPU연산자를 제안하고, 이 연산자가 추가된다편 제안한 Squaring 알고리즘의 속도를 12.7% 더 향상시킬 수 있으며, Scofh의 Carry-Ca比her Hybrid 곱셈 알고리즘에 적용해도 15%정도의 속도가 향상 될 수 있음을 보였다.
제안 방법과 Carry-Catcher Hybrid Squaring 알고리즘과의 비교 결과를 나타낸다. 사용되는 cycle의 수에서 제안 방법이 기존 방법에 비해 약 20.19% 감소된 것을 알 수 있다.
+ an-y + art) * 2 라는 사실을 기반으로 하여 doubling 연산 횟수를 획기적으로 줄인 알고리즘이다. 우리는 MIRACL에 구현되어 있는 Multiprecision Squaring을 고쳐서 원 알고리즘 보다 상에서 약 25% 정도의 빼른 결과를 얻을 수 있었으며, 저자가 아는 바로는 현재까지 나온 어떤 방법보다 빠르다. 더 나아가, ADCC라는 새로운 CPU연산자를 제안하고, 이 연산자가 추가된다편 제안한 Squaring 알고리즘의 속도를 12.
이것은 Lazy doubling 으로 인해 덧셈 연산이 절약된 것임을 알 수 있다, 그러나 Idd instruction 횟수에서는 제안 방법이 기존의 Carry-Catcher Hybrid 방법보다 횟수가 던 많은 것을 알 수 있는데, 이는 그림 7의 오른쪽 그림에서 byte 단위의 s시f 곱셈 결과를 추후에 더해주기 때문에 발생한다. 그러나 이러한 오버헤드는 제안 방법이 감소시킨 덧셈 연산의 양에 비해 미미하므로 전체적으로 성능 향상이 있게 된다.
실제 필요한 레지스터 수는 중간 결과값을 저장하기 위해 2d개가 필요하고 Carry-Catcher# 위해 2d-l개가 필요하다. 이렇게함으로써 중간 결과값을 구하기 위해 수행하는 덧셈으로안해 생기는 연속적인 carry 처리를 대폭 줄일 수 있게된다. 중간 결과값은 Hybrid단위를 한 번씩만 곱해서구해지는 것이 아니라, N개의 Hybrid단위끼리 곱할 경우 최대 2N-1 번의 Hybrid단위 곱셈을 수행하여 구하게 된다.
전체적으로계산하는 비트 길이가 길어질수록 제안 방법의 이득이증가함을 알 수 있다.
제안하는 알고리즘은 Atmel AVR 플랫폼상에서 MIRACL에 구현되어 있는 Carry-Catcher Hybrid Squaring 알고리즘 보다 월등한 연산 효율성을 보인다. Squaring 연산은 RSA나 ECC와 같은 공개키 알고리즘의 핵심적인 연산이기 때문에 이 논문의 결과를 이용하여 이러한 공개키 알고리즘의 성능을 직접적으로 향상시킬 것으로 기대한다.

후속연구

제안하는 알고리즘은 Atmel AVR 플랫폼상에서 MIRACL에 구현되어 있는 Carry-Catcher Hybrid Squaring 알고리즘 보다 월등한 연산 효율성을 보인다. Squaring 연산은 RSA나 ECC와 같은 공개키 알고리즘의 핵심적인 연산이기 때문에 이 논문의 결과를 이용하여 이러한 공개키 알고리즘의 성능을 직접적으로 향상시킬 것으로 기대한다. 또한 제안된 알고리즘은 비교적간단하기 때문에 여러 다른 플랫폼에도 어렵지 않게 적용 가능할 것으로 예상한다.
Squaring 연산은 RSA나 ECC와 같은 공개키 알고리즘의 핵심적인 연산이기 때문에 이 논문의 결과를 이용하여 이러한 공개키 알고리즘의 성능을 직접적으로 향상시킬 것으로 기대한다. 또한 제안된 알고리즘은 비교적간단하기 때문에 여러 다른 플랫폼에도 어렵지 않게 적용 가능할 것으로 예상한다. 향후, 제안된 알고리즘을 ARM이나 x86 등 다양한 플랫폼에 적용하는 연구를 통해 본 알고리즘을 일반화하는 작업을 하고자 한다.
또한 제안된 알고리즘은 비교적간단하기 때문에 여러 다른 플랫폼에도 어렵지 않게 적용 가능할 것으로 예상한다. 향후, 제안된 알고리즘을 ARM이나 x86 등 다양한 플랫폼에 적용하는 연구를 통해 본 알고리즘을 일반화하는 작업을 하고자 한다.

참고문헌 (11)

M. Scott and P. Szczechowiak, "Optimizing Multiprecision Multiplication for Public Key Cryptography," Cryptology ePrint Archive, Report 2007/299, 2007. http://eprint.iacr.org/.
N. Gura, A. Patel,A. Wander, H. Eberle, and S.C. Shantz, "Comparing Elleptic Curve Cryptography and RSA on 8-bit CPUs. Proceedings of Workshop on Cryptographic Hardware and Embedded Systems," CHES 2004, 6th Intermational Workshop, pp.119-132, 2004.
MIRACL, Multiprecision Integer and Rational Artihmetic C/C++ Library. hppt://www.shamus.ie/.
Koc. C. K, "High-Speed RSA Implementation," Technical Report TR-201, version 2.0, RSA Laboratiories, November 1994.
D. Zuras, "More on Squaring and Multiplying Large Integers," IEEE Transactions on Computers, vol.43, no.8, pp.899-908, August 1994.

상세보기
A. Karastuba and Y. Ofman, "Multiplication of Multidigit Numbers on Automata," Soviet PhysicsDoklady (English translation), vol.7, no.7, pp.595-596, 1963.
P. Comba, "Exponentiation cryptosystems on the IBM PC," IBM Systems Journal, 29(4):526(538, 1990.

상세보기
Leif Uhsadel, Axel Poschmann, and Christof Paar, "Enabling Full-Size Public-Key Algorithms on 8-bit Sensor Nodes," In Proceedings of ESAS 2007, volume 4572 of LNCS. Spriner, 2007. http://www.ist-ubisecsens.org/publications/ecc_esas2007.pdf.
P. Szczechowiak, L. Olveira, M.Scott, M. Collier and R. Dahab, NonoECC: "Testing the limits of elliptic curve cryptography in sensor networks, Wireless Sensor Networks," (EWSN 2008), LNCS 4913 (2008), 305-320.
H. Thapliyal and M.B. Srinivas, "An Efficient Method of Elliptic Curve Encryption Using Ancient Indian Vedic Mathematice," 48th IEEE MIDWEST Symposium on Circuits and Systems (MWSCAS 2005).
Donald Knuth, The Art of Computer Programming, Third Edition, Volume Two, Seminumerical Algorithms, Addison-Wesley, 1998.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증