[논문]시스톨릭 어레이 구조를 갖는 효율적인 n-비트 Radix-4 모듈러 곱셈기 구조

박태근; 조광원

doi:10.3745/kipsta.2003.10a.4.279

초록
AI-Helper

본 논문에서는 Montgomery 알고리즘을 기반으로 시스톨릭 어레이 구조를 이용한 효율적인 Radix-4 모듈러 곱셈기 구조를 제안한다. 제안된 알고리즘을 이용하여 모듈러 곱셈을 위한 반복의 수가 감소되었으며, 따라서 n-비트의 모듈러 곱셈을 수행하기 위하여 (3/2)n+2 클럭이 소요된다. 그러나 하드웨어의 이용도를 감안할 때 두 개의 곱셈에 대한 중첩(interleaving) 연산이 가능하며, 가장 빠른 시기에 새로운 곱셈을 시작한다면 하나의 모듈러 곱셈을 수행하기 위하여 평균 n/2 클럭이 필요하다. 제안된 구조는 시스톨릭 어레이 구조의 잇점으로 규칙성과 확장성을 갖기 때문에 효율적인 VLSI 구조로 설계하기가 용이하다. 기존의 다른 구조들과 비교하여 볼 때 제안된 구조는 상대적으로 적은 하드웨어들을 사용하여 높은 수행 속도를 보여주었다.

Abstract ▼ AI-Helper

In this paper, we propose an efficient architecture for radix-4 modular multiplication in systolic array structure based on the Montgomery's algorithm. We propose a radix-4 modular multiplication algorithm to reduce the number of iterations, so that it takes (3/2)n+2 clock cycles to complete an n-bi...

In this paper, we propose an efficient architecture for radix-4 modular multiplication in systolic array structure based on the Montgomery's algorithm. We propose a radix-4 modular multiplication algorithm to reduce the number of iterations, so that it takes (3/2)n+2 clock cycles to complete an n-bit modular multiplication. Since we can interleave two consecutive modular multiplications for 100% hardware utilization and can start the next multiplication at the earliest possible moment, it takes about only n/2 clock cycles to complete one modular multiplication in the average. The proposed architecture is quite regular and scalable due to the systolic array structure so that it fits in a VLSI implementation. Compared to conventional approaches, the proposed architecture shows shorter period to complete a modular multiplication while requiring relatively less hardware resources.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 Montgomery 알고리즘을 기반으로 효과적으로 연산을 수행할 수 있는 Radix-4 모듈러 알고리즘과 그를 위한 고속 시스톨릭 구조를 제안하였다. Booth 인코딩을 이용하여 부분 곱을 효율적으로 연산하기 위한 구조를 설계하였으며, 제안된 Radix-4 모듈러 곱셈 알고리즘은 무수의 곱을 상, 하위비트로 나누어서 Radix-4 수 체계로 하위 /l비트만 모듈러 처리하고 상위 k-비트를 더하여 올바른 결과 값을 얻음으로써 계산시간을 줄일 수 있었다.
구조 등 다양한 형태의 구조들이 제안되었다. 본 논문에서는 구조가 규칙적이고 확장이 용이하여 효율적으로 구현할 수 있고 고속 수행이 가능한 시스톨릭 어레이 구조를 이용한 Radix-4 모듈러 곱셈기 구조를 제안한다.

제안 방법

즉, Radix-4 수 체계를 사용하여 두 비트를 한 번에 코딩하여 처리함으로써 곱셈의 부분곱을 반으로 줄였기 때문에 성능이 향상되었으며 시스톨릭 구조를 적용하여 고속수행이 가능하다. 또한 제안된 구조는 간단한 FA를 기반으로 구성되어 간단하게 설계할 수 있다. 시스톨릭 구조로 인해 하나의 연산이 끝나기 전에 다음 연산을 수행 할 수 있으며 규칙성과 확장성을 갖기 때문에 효율적인 VLSI 구조로 설계가 용이한 장점을 가지고 있다.
이 알고리즘들은 Montgomery 알고리즘의 단점을 없애고 k 번의 반복으로 연산을 할 수 있다. 본 논문에서는 Radix-4의 수 체계를 적용하여 두 비트씩 효율적으로 인코딩함으로써 전체 모듈러 곱셈의 수행시간을 반으로 줄이고 고속 수행이 가능한 시스톨릭 어레이 구조를 이용한 Radix-4 모듈러 곱셈기 구조를 제안한다.
시스톨릭 구조에서는 한 행의 시스톨릭 어레이만 구성하여 매 클럭마다 PE (Processing Element)가 수행되기 때문에 하드웨어 효율이 높아 고속 수행이 가능하다. 본 논문에서는 개선된 Booth 알고리즘을 적용하고 이를 시스톨릭 어레이로 구현하여 효율적인 곱셈을 수행하도록 한다.[표 1]은 개선된 Booth 알고리즘을 나타내며 승수의 3비트를 표와 같이 인코딩하여 곱셈의 부분 곱을 생성하여 준다.
제안된 구조는 Verilog HDL로 모델링 되었으며 Modelsim SE-EE 5.4e 환경에서 시뮬레이션 되어 그 동작이 검증되었다. (그림 5)는 전체 블록 다이어그램을 보여준다.

이론/모형

점선은 같은 시간에 처리 되어지는 연산들을 나타낸다. 부분 곱을 계산하여 올바른 곱셈 값을 얻기 위해서는 부호 비트를 확장해야 하는데 하드웨어의 크기를 줄이고 연산의 효율성을 높이기 위해서 부호확장 제거기법(4)을 사용하였다. 각 처리기에 부분곱 생성기에서 마들어진 부분 곱 두 비트가 입력이 되어 덧셈 연산을 수행한다: a, b, c, d는 인코더기의 출력으로 생성되는 부분 곱을 나耳내며 (그림 2) 하단의 시스톨릭 구조에서는 玖로 표시되었다.

성능/효과

위한 고속 시스톨릭 구조를 제안하였다. Booth 인코딩을 이용하여 부분 곱을 효율적으로 연산하기 위한 구조를 설계하였으며, 제안된 Radix-4 모듈러 곱셈 알고리즘은 무수의 곱을 상, 하위비트로 나누어서 Radix-4 수 체계로 하위 /l비트만 모듈러 처리하고 상위 k-비트를 더하여 올바른 결과 값을 얻음으로써 계산시간을 줄일 수 있었다. 또한 시스톨릭 구조를 적용함으로써 규칙적이고 확장성 있게 설계할 수 있었다.
또한 시스톨릭 구조를 적용함으로써 규칙적이고 확장성 있게 설계할 수 있었다. 기존의 다른 구조들과 비교하여 볼 때 상대적으로 적은 하드웨어들을 사용하여 높은 수행 속도를 보여주었다. 이 Radix-4 모듈러 곱셈기를 RSA 암호화 시스템에 적용하여 설계하면 효율적인 구조를 기대할 수 있다.
이때 곱셈의 상위 비트와 모듈러스 연산된 Yk/2 값을 더하는 덧셈기 블록의 실제적인 계산은 시스톨릭 곱셈기 내부의 덧셈기에서 처리할 수 있으므로 추가되는 하드웨어는 없다. 본 논문에서 제안한 Radix-4 구조를 이용하여 곱셈의 부분곱을 반으로 감소시켰으나 Radix-4 Booth 곱셈기 내부에 인코딩하는 블록이 첨가되어 Radix-2에 시스톨릭 구조에 비해서 하드웨어 복잡도는 다소 증가되었다.
그러나 (그림 6)에서 보여 주는 것과 같이 시스톨릭 구조를 갖기 때문에 n+5 클럭이 지난 후부터 다음 모듈러 곱셈의 상위 비트 계산을 시작할 수 있으므로약 평균 n 사이클에 하나의 모듈러 곱셈을 수행할 수 있다. 즉, Radix-4 수 체계를 사용하여 두 비트를 한 번에 코딩하여 처리함으로써 곱셈의 부분곱을 반으로 줄였기 때문에 성능이 향상되었으며 시스톨릭 구조를 적용하여 고속수행이 가능하다. 또한 제안된 구조는 간단한 FA를 기반으로 구성되어 간단하게 설계할 수 있다.
현재 제안된 시스톨릭 구조의 하드웨어 효율은 50%이다. 따라서 홀수 번째 클럭과 짝수 번째 클럭에서 두 개의 모듈러 곱셈을 각각 중첩(interleaving)하여 연산할 수 있으며 RSA 암호화시스템과 같이 연속된 모듈러 곱셈을 수행할 경우 하나의 지수 비트를 처리할 경우 두 개의 모듈러 곱셈을 해야 하므로 이 경우 제안된 구조에서는 한 번에 처리할 수 있다.

참고문헌 (11)

R. L. Rivest, A. Shamir and L. Adelman, 'A Method for Obtaining Digital-Signatures and Public-Key Cryptosystern,' Commun. ACM, Vol.21, No.2, pp.120-126, Feb., 1978

상세보기
P. L. Montgomery, 'Modular Multiplication Without Trivial Division,' Math. Comput, Vol.44, pp.519-521, 1985

상세보기
C. D. Walter, 'Systolic Modular Multiplication,' IEEE Trans. Computers, Vol.42, No.3, pp.376- 378, Mar., 1993

상세보기
K. Hwang, 'Computer Arithmetic: Principles, Architecture, and Design,' Wiley, 1979
P. S. Chen, S. A. Hwang and C. W. Wu, 'A systolic RSA Public Key Cryptosystern,' in Proc. IEEE Int. Symp. Circuits Syst, pp.408-411, May, 1996
C. Y. Su, S. A. Hwang, P. S. Chen and C. W. Wu, 'An Improved Montgomery's Algorithm for High-Speed RSA Public-Key Cryptosystem,' IEEE Trans. VLSI Syst, Vol.7, No.2, June, 1999

상세보기
C. C. Yang, T. S. Chang and C. W. jen, 'A New RSA Cryptosystern Hardware-Design Based on Montgomery's Algorithm,' IEEE Trans. Circuits and Systems II, Vol.45, No.7, pp.908-913, July, 1998

상세보기
J. L. Sheu, M. D. Shieh, C. H. Wu and M. H. Sheu, 'A Pipelined-Architecture of Fast Modular Multiplication for RSA Cryptography,' Proc. IEEE ISCAS, Vol.2, pp.121-124, 1998
J. S. Chiang and J. K. Chen, 'An Efficient VLSI Architecture for RSA Public-Key Cryptosystem,' Proc. IEEE Int. Symp, on Circuits and Systems, pp.496-499, 1999
J. J. Leu and A. Y. Wu, 'Design Methodology for Booth-encoded Montgomery Module Design for RSA Cryptosystern,' Proc. IEEE ISCAS, pp.357-360, 2000
C. W. Chiou, T. C. Yang, 'Parallel Modular Multiplication with Table Look-up,' Int. J. Computer Math., Vol.69, pp. 49-55, 1997

상세보기

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

연합인증

시스톨릭 어레이 구조를 갖는 효율적인 n-비트 Radix-4 모듈러 곱셈기 구조
Efficient Architecture of an n-bit Radix-4 Modular Multiplier in Systolic Array Structure 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

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

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

선택된 텍스트

연합인증

시스톨릭 어레이 구조를 갖는 효율적인 n-비트 Radix-4 모듈러 곱셈기 구조 Efficient Architecture of an n-bit Radix-4 Modular Multiplier in Systolic Array Structure 원문보기

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

Abstract ▼ AI-Helper

주제어

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

문제 정의

제안 방법

이론/모형

성능/효과

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

박태근 (22)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

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

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

선택된 텍스트

시스톨릭 어레이 구조를 갖는 효율적인 n-비트 Radix-4 모듈러 곱셈기 구조
Efficient Architecture of an n-bit Radix-4 Modular Multiplier in Systolic Array Structure 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper