고속 RSA 하드웨어 곱셈 연산과 하드웨어 구조

국문 초록 (Abstract)

몽고메리 곱셈 방법을 이용한 고속 연산은 RSA 암호 시스템의 설계에 중요한 부분을 차지한다. 몽고메리 곱셈은 두번의 덧셈 연산으로 구성되며 CSA를 이용한 방법과 RBA를 이용한 방법이 있다. CSA의 경우 4-2 CSA 또는 5-2 CSA를 이용하여 구현하며, RBA의 경우 기존 이진 방법과 달리 잉여 이진체계를 이용한다는 특징을 가진다. [1]에서는 기존의 RBA와 다른 새로운 이진 체계와 하드웨어 구조를 제안하고 몽고메리 곱셈에 적용하였다. 본 논문에서는[1]에서 제안한 RBA의 로직 구조를 재구성하여 시간 복잡도 뿐만 아니라 결합기가 필요하지 않도록 구성하여 공간 복잡도를 크게 줄였다. 또한 입?출력 값을 변형시켜 지수승 연산에 적합하도록 설계하였다. 그 결과 제안하는 RBA는 삼성 STD130 0.18㎛ 1.8V 표준 셀 라이브러리에서 지원하는 게이트들을 사용하여 설계하는 환경에서, 기존의 4-2 CSA 보다 공간과 시간 복잡도를 각각 18.5%와 25.24%를, 기존의 RBA 보다 6.3%와 14%를 감소시킨다. 또한[1]의 RBA와 비교시 44.3%, 2.8%의 감소된 복잡도를 갖는다.

다국어 초록 (Multilingual Abstract)

A fast Montgomery multiplication occupies important to the design of RSA cryptosystem. Montgomery multiplication consists of two addition, which calculates using CSA or RBA. In terms of CSA, the multiplier is implemented using 4-2 CSA or 5-2 CSA. In terms of RBA, the multiplier is designed based on redundant binary system. In[1], A new redundant binary adder that performs the addition between two binary signed-digit numbers and apply to Montgomery multiplier was proposed. In this paper, we reconstruct the logic structure of the RBA in[1]for reducing time and space complexity. Especially, the proposed RB multiplier has no coupler like the RBA in[1]. And the proposed RB multiplier is suited to binary exponentiation as modified input and output forms. We simulate to the proposed NRBA using gates provided from SAMSUNG STD130 0.18㎛ 1.8V CMOS Standard Cell Library. The result is smaller by 18.5%, 6.3% and faster by 25.24%, 14% than 4-2 CSA, existing RBA, respectively. And Especially, the result is smaller by 44.3% and faster by 2.8% than the RBA in[1].

목차 (Table of Contents)

• 요약
• ABSTRACT
• Ⅰ. 서론
• Ⅱ. Montgomery 곱셈 구조
• Ⅲ. 기존의 곱셈기
• Ⅳ. 제안하는 RSA 연산
• Ⅴ. 비교 및 결과
• 참고문헌
• 〈著者紹介〉

참고문헌 (Reference)

1 "새로운 잉여 이진 Montgomery 곱셈기와 하드웨어 구조" 16 (16): 33-41, 2006.

2 "TWIRL and RSA Key Size" 2003.05

3 "Signed-digit number representations for fast parallel arithmetic" ec-io (ec-io): 389-400, sept.1961.

4 "SAMSUNG STD130 0.18㎛ 1.8V CMOS Standard Cell Library for Pure Logic Products."

5 "Redundant Binary 연산을 이용한 실수/복소수 승산기" 1999.

6 "Montgomery Exponentiation Needs No Final Subtractions" 35 (35): 1831-1832, 1999

7 "Modified radix- 2 Montgomery modular multiplication to make it faster and simpler" 598-602, 2004

8 "High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree" c-34 (c-34): 789-796, sep.1985.

9 "High radix Montgomery modular exponentiation on reconfigurable hardware" 50 (50): 759-764, 2001.

10 "Fast Montgomery modular multiplication and RSA cryptographic processor architectures" 379-384, 2003.

11 "Computer Arithmetic Algorithms" 1993.

12 "An 8.8-ns 54×54 bit multiplier with high speed redundant bi- nary architecture" 31 (31): 773-783, 1996.06

13 "A unified framework for redundant number representations with bounded carry propagation chains IEEE Transactions on Computers" 880-891, aug.1994.

14 "A 33 MFLOPS floating point processor using redundant binary representation" dig. tech. papers of 1988 isscc. pp. 152-153 : -1988,

15 "0.13㎛ CMOS Synthesis of Common Arithmetic Units" Department of electrical and electronic engineering, University college Cork (03-11) : 2003.