[논문]변형된 RBA를 이용한 몽고메리 곱셈기와 하드웨어 구조

지성연; 임대성; 장남수; 김창한; 이상진

변형된 RBA를 이용한 몽고메리 곱셈기와 하드웨어 구조
Montgomery Multiplier Base on Modified RBA and Hardware Architecture 원문보기

지성연 (고려대학교 정보보호대학원) , 임대성 (고려대학교 정보보호대학원) , 장남수 (고려대학교 정보보호대학원) , 김창한 (세명대학교 정보보호학과) , 이상진 (고려대학교 정보보호대학원)

RSA 암호 시스템은 IC카드, 모바일 및 WPKI, 전자화폐, SET, SSL 시스템 등에 많이 사용된다. RSA는 모듈러 지수승 연산을 통하여 수행되며, Montgomery 곱셈기를 사용하는 것이 효율적이라고 알려져 있다. Montgomery 곱셈기에서 임계 경로 지연 시간(Critical Path Delay)은 세 피연산자의 덧셈에 의존하고 캐리 전파를 효율적으로 처리하는 문제는 Montgomery 곱셈기의 효율성에 큰 영향을 미친다. 최근 캐리 전파를 제거하는 방법으로 캐리 저장 덧셈기(Carry Save Adder, CSA)를 사용하는 연구가 계속 되고 있다. McIvor외 세 명은 지수승 연산에 최적인 CSA 3단계로 구성된 Montgomery 곱셈기와 CSA 2단계로 구성된 Montgomery 곱셈기를 제안했다. 시간 복잡도 측면에서 후자는 전자에 비해 효율적이다. 본 논문에서는 후자보다 빠른 연산을 수행하기 위해 캐리 전파 제거 특성을 가진 이진 부호 자리(Signed-Digit, SD) 수 체계를 사용한다. 두 이진 SD 수의 덧셈을 수행하는 잉여 이진 덧셈기(Redundant Binary Adder, RBA)를 새로 제안하고 Montgomery 곱셈기에 적용한다. 기존의 RBA에서 사용하는 이진 SD 덧셈 규칙 대신 새로운 덧셈 규칙을 제안하고 삼성 STD130 $0.18{\mu}m$ 1.8V 표준 셀 라이브러리에서 지원하는 게이트들을 사용하여 설계하고 시뮬레이션 하였다. 그 결과 McIvor의 2 방법과 기존의 RBA보다 최소 12.46%의 속도 향상을 보였다.

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

문제 정의

본 논문에서는 기존의 덧셈 규칙을 따르지 않고 고속 연산에 적합하도록 새로운 덧셈 규칙을 제안하고 이를 이용하여 새로운 RBA를 제안한다. 제안하는 새로운 RBA는 알고리즘 2와 같다.

제안 방법

제안하는 곱셈기는 연산 속도를 향상시키기 위해 이진 SD 수 체계를 사용하여 임계 경로 지연 시간의 대부분을 차지하는 세 피연산자의 덧셈을 효율적으로 구성했다. 기존의 이진 SD 덧셈 규칙을 사용하지 않고 새로운 방법을 제안하여 속도를 향상시켰다. 삼성 STD130 0.
본 논문에서 사용하는 삼성 STD130 0.18pm 1.8V 표준 셀 라이브러리에서는 NAND 게이트나 NOR 게이트에 비해 AND 게이트 OR 게이트 XOR 게이트 등은 크기가 크고 지연 시간을 크게 증가시키므로 NAND 게이트, NOR 게이트, NOT 게이트 등으로만 구성된 하드웨어 구조를 설계하기 위하여 입력 값과 출력 값을 다음과 같이 바꿀 수 있다.
특히 이진 수 체계에서 지수승 연산에 적합하도록 Mclvor가 제시한 구조는 이러한 측면을 고려할 때 효율적이다. 본 논문에서는 덧셈기의 효율적인 구성을 위하여 이진 SD 수 체계를 사용한다.
제안하는 RB 곱셈기는 Mclvor의 구조와 유사한 형태로 이진 SD 수로 표현된 X,Y와 이진 수로 표현된 M을 입력받아 Y+M을 계산하여 저장하고 x_i와 u_i에 따라 MUX를 통해 {Y+M,Y,M,0} 에서 선택하여 덧셈을 수행한다.
제안하는 곱셈기는 연산 속도를 향상시키기 위해 이진 SD 수 체계를 사용하여 임계 경로 지연 시간의 대부분을 차지하는 세 피연산자의 덧셈을 효율적으로 구성했다. 기존의 이진 SD 덧셈 규칙을 사용하지 않고 새로운 방법을 제안하여 속도를 향상시켰다.

이론/모형

Montgomery 곱셈은 RSA 암호 시스템에서의 지수승 연산과 같이 반복적인 모듈러 곱셈을 요구되는 환경에서 효율적이다. 본 논문에서 이진 Montgomery 곱셈 알고리즘은 알고리즘 1과 같이 구성된다. Montgomery 곱셈 알고리즘을 보다 효율적으로 구성하여 복잡도를 줄이기 위해 다양한 방법들이 제안되었으며 이는 다음과 같다: 1) 반복적인 곱셈으로 이루어진 지수승의 경우 단계 3에서 수행되는 비교 연산과 뺄셈은 큰 연산량을 차지하게 되므로 단계 3을 제거하는 방법 [9]; 2) Y를 한 비트 늘려 최하위 비트를 0으로 만들어 알고리즘 1의 단계 2.
본 논문에서는 캐리 전파를 제거하기 위한 방법으로 Avizienis에 의해 [4]에서 처음으로 제안된 SD 수 체계를 사용한다. SD 수 체계에서는 동일한 수에 대해서 다른 표현 방법이 존재하므로 덧 셈 설계 방법 또한 다양하다.

성능/효과

최근 CSA를 이용한 5개의 입력 값과 2개의 출력 값을 가지는 곱셈 기([3]에서 Mclvor 외 세 명이 제안한 첫 번째 방법: Mclvor의 1 방법)와 4개의 입력 값과 2개의 출력 값을 가지는 곱셈기([3]에서 Mclvor 외 세 명이 제안한 두 번째 방법: Mclvor의 2 방법)가 제안되었다.[3] 전자의 곱셈기는 3단계의 CSA를 이용하지만 후자의 곱셈기는 사전 계산을 통해 값을 저장하여 MUX를 이용해서 사용하는 방법으로 5개의 입력 값을 4개로 줄여 2단계의 CSA로 구현 이 가능하다. 4개의 입력 값은 캐리와 합으로 표현된 2개의 정수가 된다.
RBA3[7]기는 다중 입력 게이트를 활용하여 속도를 향상시키고자 하였다. 그 결과 XOR 게이트 2단계, XNOR 게이트 1단계, NAND 게이트 1단계, OA21 게이트 1단계로 구성되어 있다. 또한 [1, 6, 7]의 RBA 중 삼성 STD130 0.
그 결과 XOR 게이트 2단계, XNOR 게이트 1단계, NAND 게이트 1단계, OA21 게이트 1단계로 구성되어 있다. 또한 [1, 6, 7]의 RBA 중 삼성 STD130 0.18um 1.8V 표준 셀 라이브러리에서 지원하는 게이트로 설계하여 지연 시간을 측정한 결과 가장 빠른 속도를 나타내었다.
기존의 이진 SD 덧셈 규칙을 사용하지 않고 새로운 방법을 제안하여 속도를 향상시켰다. 삼성 STD130 0.18 pm 1.8V 표준 셀 라이브러리에서 지원하는 게이트로 덧셈을 설계 할 경우 기존의 RBA보다 12.46%의 속도 향상을 보였다. 이진 SD 수 체계는 캐리 전파 제거 특성이 외에도 음수를 표현하는 경우 2의 보수나 1의 보수 등으로 변환 시 요구되는 연산량이 필요하지 않고 바로 변환이 가능하므로 장점을 가진다.
제안하는 RB 곱셈기의 속도는 임계 경로 지연 시간에 따라 클럭의 주기가 결정되므로 가장 많은 시간이 소요되는 덧셈기의 효율성에 크게 의존하게 된다. 삼성 STD130 0.18pm 1.8V 표준 셀 라이브러리에서 지원하는 게이트[13]를 이용하여 Mclvor의 2 방법 및 기존의 RBA 등과 속도를 비교하면 표 1과 같이 제안한 RBA는 Mclvor 방법과 기존의 RBA들에 비해 최소 12.46%의 속도 향상을 보였다.
제안하는 RB 곱셈기의 속도는 임계 경로 지연 시간에 따라 클럭의 주기가 결정되므로 가장 많은 시간이 소요되는 덧셈기의 효율성에 크게 의존하게 된다. 삼성 STD130 0.

후속연구

이진 SD 수 체계는 캐리 전파 제거 특성이 외에도 음수를 표현하는 경우 2의 보수나 1의 보수 등으로 변환 시 요구되는 연산량이 필요하지 않고 바로 변환이 가능하므로 장점을 가진다. 본 논문에서 제안한 곱셈기는 연산을 빠르게 수행해야 하고 충분한 게이트들을 사용할 수 있는 서버 등에서 효율적이라 예상되며 여러 응용 분야에 활발히 사용될 수 있을 것으로 보인다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

변형된 RBA를 이용한 몽고메리 곱셈기와 하드웨어 구조
Montgomery Multiplier Base on Modified RBA and Hardware Architecture 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

변형된 RBA를 이용한 몽고메리 곱셈기와 하드웨어 구조 Montgomery Multiplier Base on Modified RBA and Hardware Architecture 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

변형된 RBA를 이용한 몽고메리 곱셈기와 하드웨어 구조
Montgomery Multiplier Base on Modified RBA and Hardware Architecture 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper