[논문]RSA 암호시스템의 모듈러 승산기 처리속도 향상을 위한 연구

이석근; 정우열

RSA 암호시스템의 모듈러 승산기 처리속도 향상을 위한 연구
A Study on the Modulus Multiplier Speed-up Throughput in the RSA Cryptosystem 원문보기

한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences, v.4 no.3, 2009년, pp.217 - 223

이석근 ((주)율시스템즈) , 정우열 (한려대학교 멀티미디어정보통신공학과)

초록
AI-Helper

최근, 다양한 네트워크의 발달은 심각한 사회문제를 발생시킨다. 그러므로 네트워크의 보안성을 통제할 수 있는 방법이 요구되어진다. 보안과 관련된 이러한 문제들은 해킹, 크래킹과 같은 비 보안분야에 직면해 있다. 새로운 암호알고리즘의 개발없이 해커나 크래커로부터 안전성을 보장받기 위한 방법은 확장된 키 길이를 통한 비 암호해석법을 유지시키는 것이다. 본 논문에서는 RSA 암호시스템에서 병목현상을 제거하기 위해서 가변길이 곱셈, 캐리 생성 부분을 하나의 어레이 방식을 사용하는 몽고메리 곱셈기 구조를 제안하였다. 그러므로 제안된 몽고메리 곱셈기는 크래킹으로부터 안전성을 제공하게 되며 실시간 처리가 가능해질 것이다.

Abstract ▼ AI-Helper

Recently, the development of the various network method can generate serious social problems. So, it is highly required to control security of network. These problems related security will be developed and keep up to confront with anti-security field such as hacking, cracking. The way to preserve security from hacker or cracker without developing new cryptographic algorithm is keeping the state of anti-cryptanalysis in a prescribed time by means of extending key-length. In this paper, the proposed montgomery multiplication structured unit array method in carry generated part and variable length multiplication for eliminating bottle neck effect with the RSA cryptosystem. Therefore, this proposed montgomery multiplier enforce the real time processing and prevent outer cracking.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 RSA와 같은 비대칭 암호시스템에서 성능을 좌우하게 되는 모듈러 승산기와 지수 승산기에 대하여 매트릭스 룩업 테이블을 이용한 MM 방식을 제안하였으며 MM 방식을 적용한 RSA 암호시스템을 설계하였다. 설계된 MM-RSA는 기존 몽고메리 승산기를 적용한 RSA 암호시스템에 비하여 어레이 배열로 인한 면적과 외부 메모리 사용으로 인한 단점이 있지만 처리 속도 면에서 기존 RSA에 비하여 MM-RSA는 응답시간이 30% 향상되었음을 확인하였다.

제안 방법

그러므로 몽고메리 알고리즘을 적용한 RSA 암호시스템에서 기존에 사용된 모듈러 연산의 처리시간 지연 및 고속처리 저해요인인 버퍼포화 및 병목현상, 가변길이 데이터와 대용량의 데이터 그리고 계산상의 지연 등을 없애기 위하여 본 논문에서는 병렬처리의 방해요인의 제거를 위한 룩업 테이블 사용 및 모듈러 배수 연산에 대한 캐리 생성 부분만을 어레이 방식의 구조로 채택하는 것과 더불어 MM 방식을 이용한 연산 수행 단계를 줄여 모듈러 승산 연산이 고속으로 수행될 수 있도록 하였다.
또한 모듈러 승산연산의 고속수행을 위하여 룩업 테이블을 사용함으로서 1회의 연산횟수를 가지고 처리하도록 하였다. 그리고 전체 승산기를 시스토릭 어레이 구조를 사용하지 않고 단지 모듈러 배수에 대한 캐리 생성부분만을 어레이 방식으로 채택함으로서 154 자리 이상의 정수가 입력되더라도 외부 인터페이스에 해당하는 어레이 부분만을 확장함으로서 주위환경에 대한 아무런 제약조건이 발생하지 않도록 하였다. 또한 제안된 MM 방식은 알고리즘 전체 중 일부만이 어레이 구조로 되어 있고 나머지 부분은 룩업 테이블을 사용하여 계산하는 구조로 되어 있으므로 하드웨어 구현시 가장 큰 단점이었던 외부로부터의 크래킹에 의한 공격으로부터 더욱 자유로울 수 있다는 것이다.
기존 몽고메리 승산 알고리즘은 초기값과 계산과정에서 산출되어지는 중간단계의 값을 저장하기 위한 매체인 버퍼가 별도로 필요하였으나, 본 논문에서 제안한 몽고메리 매트릭스 승산 알고리즘(MM)은 별도의 저장 매체가 불필요하며 단지 2진 비트 레벨들에 대한 1회의 승산연산을 수행하기 위한 룩업 테이블 만이 필요하게 된다.
이런 결과로 입력 정수들이 가변 데이터량에 의한 연산 수행에 있어서 병목현상으로 인한 처리시간 지연을 효과적으로 감소할 수 있도록 연산이 수행된다. 또한 모듈러 승산연산의 고속수행을 위하여 룩업 테이블을 사용함으로서 1회의 연산횟수를 가지고 처리하도록 하였다. 그리고 전체 승산기를 시스토릭 어레이 구조를 사용하지 않고 단지 모듈러 배수에 대한 캐리 생성부분만을 어레이 방식으로 채택함으로서 154 자리 이상의 정수가 입력되더라도 외부 인터페이스에 해당하는 어레이 부분만을 확장함으로서 주위환경에 대한 아무런 제약조건이 발생하지 않도록 하였다.
즉, 입력 정수중의 어느 하나가 0 또는 1인 경우에는 P_{i, j} 값은 룩업테이블을 거치지 않고 즉시 출력하도록 하였다. 또한 병렬처리가 가능하도록 하기 위하여 시스템 구성은 정수값 가중치에 대한 어레이 구조를 채택하였다.
설계된 MM 방식의 블록은 연산속도를 증가시키기 위하여 룩업 테이블을 사용하였으며 입력되는 데이터의 스트림 값에 따라 어레이 구조를 사용할 수 있도록 가변적으로 설계하였다.
식(11)에서 MM 방식의 연산과정은 매우 단순하다. 즉, 입력 정수중의 어느 하나가 0 또는 1인 경우에는 P_{i, j} 값은 룩업테이블을 거치지 않고 즉시 출력하도록 하였다. 또한 병렬처리가 가능하도록 하기 위하여 시스템 구성은 정수값 가중치에 대한 어레이 구조를 채택하였다.

성능/효과

그리고 전체 승산기를 시스토릭 어레이 구조를 사용하지 않고 단지 모듈러 배수에 대한 캐리 생성부분만을 어레이 방식으로 채택함으로서 154 자리 이상의 정수가 입력되더라도 외부 인터페이스에 해당하는 어레이 부분만을 확장함으로서 주위환경에 대한 아무런 제약조건이 발생하지 않도록 하였다. 또한 제안된 MM 방식은 알고리즘 전체 중 일부만이 어레이 구조로 되어 있고 나머지 부분은 룩업 테이블을 사용하여 계산하는 구조로 되어 있으므로 하드웨어 구현시 가장 큰 단점이었던 외부로부터의 크래킹에 의한 공격으로부터 더욱 자유로울 수 있다는 것이다.
본 논문에서는 RSA와 같은 비대칭 암호시스템에서 성능을 좌우하게 되는 모듈러 승산기와 지수 승산기에 대하여 매트릭스 룩업 테이블을 이용한 MM 방식을 제안하였으며 MM 방식을 적용한 RSA 암호시스템을 설계하였다. 설계된 MM-RSA는 기존 몽고메리 승산기를 적용한 RSA 암호시스템에 비하여 어레이 배열로 인한 면적과 외부 메모리 사용으로 인한 단점이 있지만 처리 속도 면에서 기존 RSA에 비하여 MM-RSA는 응답시간이 30% 향상되었음을 확인하였다. 이러한 결과는 암호시스템의 특성상 처리속도가 우선임을 고려할 때 네트워크 기반 통신시스템에 매우 적합할 것으로 생각된다.
설계된 MM-RSA는 기존 몽고메리 승산기를 적용한 RSA 암호시스템에 비하여 어레이 배열로 인한 면적과 외부 메모리 사용으로 인한 단점이 있지만 처리 속도 면에서 기존 RSA에 비하여 MM-RSA는 응답시간이 30% 향상되었음을 확인하였다. 이러한 결과는 암호시스템의 특성상 처리속도가 우선임을 고려할 때 네트워크 기반 통신시스템에 매우 적합할 것으로 생각된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	비대칭형 암호방식이 네트워크 환경에 적합한 암호방식인 이유는?	비대칭형 암호방식은 네트워크 환경속에서 키분배 및 관리측면에서 매우 탁월한 성능을 발휘하기 때문에 네트워크 환경에 적합한 암호방식이다. 그러나 비대칭형 암호시스템은 수학적인 해를 구하는 방법을 이용하여 암호화를 수행하기 때문에 처리시간이 매우 길다는 단점을 가진다.
	RSA 암호시스템에서 사용되어 지는 모듈러 연산은 어떻게 나뉘어지나?	RSA 암호시스템에서 사용되어 지는 모듈러 연산은 크게 두 부분으로 나뉘어진다. 즉, 모듈러 승산(modular multiplication) 연산부와 모듈러 리덕션(modular reduction) 연산부로 구성되어 있으며 이들 중에서 모듈러 승산 연산부분이 전체 모듈러 연산 처리시간의 거의 대부분을 차지하고 있는 것이 현실정이다. 모듈러 지수 연산을 수행하기 위하여 개발된 방법은 이진방식, r -진방식, 누승테이블방식, 가산고리 방식 등이 있으나 이중에서 이진방식을 적용한 몽고메리 모듈러 지수연산(montgomery modular exponent) 방식이 개발된 방식 중에서 처리속도에서 가장 빠른 것으로 보고되고 있다.
	비대칭형 암호시스템은 어떤 단점을 가지나?	비대칭형 암호방식은 네트워크 환경속에서 키분배 및 관리측면에서 매우 탁월한 성능을 발휘하기 때문에 네트워크 환경에 적합한 암호방식이다. 그러나 비대칭형 암호시스템은 수학적인 해를 구하는 방법을 이용하여 암호화를 수행하기 때문에 처리시간이 매우 길다는 단점을 가진다. 비대칭형 암호시스템의 대표적인 방식인 RSA 역시 수학적인 해를 찾기 위해서는 매우 오랜 시간이 소요된다.

참고문헌 (9)

T. ElGamal, "A Public Key Cryptosystem and Signature Scheme Based on Discrete Logarithms", IEEE Trans. Information Theory, Vol. 31, pp.469-472, 1985.

상세보기
O. Goldreich, "Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme", In Proceeding CRYPTO'86, Lecture Notes in Computer Science, No. 263, Springer-verlag, pp.104-110, 1987.
O. Goldreich, H. Krawczyk and M. Luby, "On the existence of pseudorandom generators", SIAMJ, on Computing, Vol. 22(6), pp.1163-1175, 1993.

상세보기
O. Goldreich and L. A. Levin, "A Hard-core Predicate for All One-Way Functions", Proceedings of the 21st ACM Symposium on Theory of Computing, pp.25-32, 1989
P. L. Montgomery, "Modular multiplication without trial division", Mathematics of computation, Vol. 44, pp.519-521, 1985.

상세보기
C. N. Zhang, H. L. Martin and D. Y. Yun, "Parallel algorithms and systolic array designs for RSA cryptosystem", Intel Confer. on systolic arrays, pp.341-350, 1988
K. Iwamura, T. Matsumoto and H. Imai, "Systolic arrays for modular exponentiation using montgomery method", Proc. EUROCRYPT'92, pp.477-481, 1992.
S. E. Eldridge and C. D. Walter, "Hardware implementation of montgomery's modular multiplication algorithm", IEEE Trans. Comput., Vol. 42, No. 6, pp.693-699, 1993.

상세보기
C. D. Walter, "Systolic modular multiplication", IEEE Trans. Comput., Vol. 42, No. 3, pp.376-378, 1993.

상세보기

저자의 다른 논문 :

표제어: 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

연합인증