[go: up one dir, main page]

KR100436814B1 - 아이씨카드용 알에스에이 암호 연산 장치 - Google Patents

아이씨카드용 알에스에이 암호 연산 장치 Download PDF

Info

Publication number
KR100436814B1
KR100436814B1 KR10-2001-0081717A KR20010081717A KR100436814B1 KR 100436814 B1 KR100436814 B1 KR 100436814B1 KR 20010081717 A KR20010081717 A KR 20010081717A KR 100436814 B1 KR100436814 B1 KR 100436814B1
Authority
KR
South Korea
Prior art keywords
modular
data
value
register
unit
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR10-2001-0081717A
Other languages
English (en)
Other versions
KR20030051992A (ko
Inventor
김무섭
김호원
최용제
박영수
정교일
Original Assignee
한국전자통신연구원
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 한국전자통신연구원 filed Critical 한국전자통신연구원
Priority to KR10-2001-0081717A priority Critical patent/KR100436814B1/ko
Priority to US10/318,034 priority patent/US7197141B2/en
Publication of KR20030051992A publication Critical patent/KR20030051992A/ko
Application granted granted Critical
Publication of KR100436814B1 publication Critical patent/KR100436814B1/ko
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G06F7/552—Powers or roots, e.g. Pythagorean sums
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/70—Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer
    • G06F21/71—Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer to assure secure computing or processing of information
    • G06F21/72—Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer to assure secure computing or processing of information in cryptographic circuits
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/728—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic using Montgomery reduction

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Analysis (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Computer Hardware Design (AREA)
  • Computing Systems (AREA)
  • Computer Security & Cryptography (AREA)
  • Software Systems (AREA)
  • Storage Device Security (AREA)

Abstract

본 발명에 따른 IC카드용 RSA암호 연산 장치는, 적은 면적에서 고속의 연산 기능을 갖는 RSA암호 연산 장치에 관한 것으로, 입력되는 제어 신호에 따라 모듈러 곱셈 연산 또는 RSA 암호 연산인 모듈러 지수승 연산을 선택적으로 수행하고, 32bit 연산 장치를 이용하여 512~1024bit 데이터의 모듈러 연산을 반복 수행하며, 512~1024bit의 데이터를 32bit 연산기를 사용하여 연산하므로 데이터를 저장하는 레지스터의 면적을 최소화하여 암호 장치의 면적을 줄이고, 연산 과정에서 발생하는 중간값을 메모리 대신 내부 레지스터에 저장함으로써 메모리 액세스 횟수를 최소화하여 고속의 암호화 연산을 가능하게 한다.

Description

아이씨카드용 알에스에이 암호 연산 장치{apparatus for RSA Crypto Processing of IC card}
본 발명은 IC카드용 RSA암호 연산 장치에 관한 것으로, 상세하게는, IC카드 시스템에서 카드 사용자의 개인 정보를 보호하고 카드의 중요 정보를 도용하지 못하도록 보안성을 제공하기 위해 사용하는 공개키 암호 알고리즘 중 RSA 암호 알고리즘의 수행을 위한 IC카드용 RSA암호 연산 장치에 관한 것이다.
이하에서 설명하는 본 발명의 실시 예에서는, IC(Integrated Circuit) 카드 시스템을 일례로 들어 설명하겠으나, 본 발명은 IC 카드 시스템 뿐만 아니라 암호 프로세서 등의 소형 패키지나 고가의 전자 제품 등과 같이 사용에 있어 사용자의 신원 확인이 필요하고 필요에 따라 타인의 접근을 제한하는 기능을 필요로 하는 모든 장치에 적용될 수 있다.
일반적으로 IC카드 또는 스마트카드(Smart Card)는 일반적으로 카드에 마이크로프로세서와 메모리 장치를 내장하고 있어 카드 내에서 정보의 저장과 관리 및 처리가 가능한 카드를 통칭한다. 이러한 IC카드는 기존의 Magnetic strip 카드나Memory카드에서 제공하지 못하였던 우수한 보안 특성으로 각종 금융 application뿐만 아니라 컴퓨터, 자동판매기, 통행제어기, 휴대폰 등 다양한 목적의 카드 리더(Card Reader)와 함께 사용되어 정보 자원에 대한 사용자 접근 통제에 사용되고 있으며, 전자 상거래, 교통 및 방송통신 분야등과 같은 다양한 정보통신 서비스에 응용되고 있다. IC카드는 이렇게 다양한 응용분야에서의 사용 조건에 적합한 보안성을 제공하기 위해 암호기능을 제공하고 있다. IC카드에서 많이 사용되는 공개키 암호 알고리즘 중 RSA 암호 알고리즘은 암호화 연산 또는 전자 서명을 위해 가장 널리 쓰이는 비대칭키 암호 알고리즘이며, SET(Secure Electronic Transaction) 프로토콜과 같이 카드를 이용한 거래등에서 안전성을 제공하기 위하여 Visa, Mastercard 그리고 EMV카드 시스템에 채택되어 사용되어지고 있다.
일반적으로 RSA 암호 알고리즘의 연산은 수학식 1과 같이 모듈러 곱셈이라고 하는 연산 과정을 반복하여 모듈러 지수승 연산을 수행함으로써 이루어진다.
RSA 공개키 암 복호화 알고리즘
B가 메시지 m을 A에게 보내는 경우의 암호화 :
1. A의 공개키 (n, e)를 얻는다.
2. 메시지 m을 [0, n-1] 사이의 정수로 표현.
3. c = memod n을 계산.
4. 생성된 암호문 c를 A에게 전송.
전송된 메시지 c를 받은 A의 복호화 :
1. 비밀키 d를 이용하여 m = cdmod n을 계산
즉, RSA알고리즘의 기본 연산은 수학식1의 단계3에서 알 수 있듯이 일반적으로 512 ~ 1024bit 이상의 큰 수에 대한 반복적인 모듈러 곱셈 연산이다. 두 수 A와 B 그리고 모듈러 값 M에 대하여, A와 B를 곱한 결과를 M으로 나누었을 때의 나머지를 C라고 했을 때, 모듈러 곱셈은 수학식 2와 같이 나타낼 수 있다.
수학식2의 모듈러 곱셈을 수행하는 여러 알고리즘 중 몽고메리 알고리즘은, 나눗셈을 구하기 위해 연산에 많은 시간이 걸리는 나눗셈 연산을 사용하지 않고 곱셈과 덧셈만으로 모듈러 연산을 수행 할 수 있으므로 가장 널리 사용되어지고 있다.
몽고메리 알고리즘은 임의의 정수 A를 모듈러스M에 의해 생성된 정수 R에 대한 정수 M의 잉여류 수 체계인 AR mod M으로 변환하여 정의하고, 새로 변환된 집합 내에서 모듈러 연산을 수행한다. 이때, 정수 R은 모듈러스 M 보다 크고, M과 서로 소인 정수로 선택된다. 모듈러 곱셈을 위한 몽고메리 모듈러 곱셈 알고리즘은 수학식3과 같다.
몽고메리 모듈러 곱셈 : ABR-1
1. S = 0
2. 0에서부터 (n-1) 까지 i에 대해 다음을 반복
3. begin
4. Qi= ((S0+ AiB0)( r - M0)-1) mod r
5. S = (S + Ai B + Qi M) div r
6. end
7. 만일 S ≥ M인 경우, S = S - M를 계산
수학식 3에 나타낸 몽고메리 곱셈 연산은 원래의 수 체계를 새로운 잉여류 수 체계로 변환하여 연산하고 있으므로 이를 수학식1의 RSA 암호 알고리즘에 적용하여 사용할 수 없으며, 몽고메리 곱셈을 이용한 RSA 암호 알고리즘의 계산은 수학식 4와 같은 몽고메리 지수승 알고리즘을 이용하여 연산을 수행한다.
몽고메리 지수승 알고리즘.
입력 : m = (mn-1…m1m0)r, xp = xR mod m, A = R mod m, e = (et…e1e0)2.
출력 : xemod m
1. t에서부터 0까지 다음을 반복 :
2. A = Mont(A, A).
3. 만일 ei= 1이면 A = Mont(A, xp).
4. A = Mont(A, 1).
수학식 4에서 알 수 있듯이 몽고메리 모듈러 지수승 연산을 이용한 RSA 암호 연산은 지수승 값에 따라 Mont()로 표시되어진 몽고메리 모듈러 곱셈 연산을 반복하여 수행된다.
수학식 3에 나타낸 몽고메리 모듈러 곱셈 연산은 값S를 계산 할 때, 결과값에 대한 추정에 의한 연산을 수행하므로 연산의 결과값 S는 모듈러 곱셈 연산의 실제 결과값이거나 또는 실제 결과값보다 모듈러스M만큼 큰 경우로 나타날 수 있다. 따라서 몽고메리 모듈러 곱셈의 실제 결과값을 구하기 위해 단계 7에서와 같이 마지막 보정 단계가 필요하다.
상기한 바와 같이 몽고메리 모듈러 곱셈 연산을 이용한 RSA 암호 연산 회로는 한 번에 처리되는 데이터가 512~1024bit이상으로 그 연산 단위가 크므로 연산 과정에서 발생하는 중간 값을 저장하기 위한 레지스터 또는 메모리 영역 또한 512~1024bit 이상 되는 큰 저장 공간을 사용하여야 한다. 이러한 경우, RSA 암호 연산을 위해 입력되는 데이터와 모듈러 값 및 지수승 값(사용자 키 값)을 저장하기 위해 사용되는 레지스터들이 증가할수록 회로의 면적은 증가하게 되며, 사용하는 메모리가 많을 수록 메모리에 데이터를 저장하거나 읽기 위한 메모리의 액세스 횟수가 증가하여 암호화 연산을 수행하는 속도를 저하시키게 되므로 저 면적이면서고속의 암호 회로를 요구하는 IC카드에 적용하기에는 부적합 하다는 단점이 있다.
본 발명은 이러한 종래의 문제점을 해결하기 위하여 안출된 것으로, 적은 면적에서 고속의 연산 기능을 갖는 RSA암호 연산 장치를 제공하기 위한 방안으로, 입력되는 제어 신호에 따라 모듈러 곱셈 연산 또는 RSA 암호 연산인 모듈러 지수승 연산을 선택적으로 수행하고, 32bit 연산 장치를 이용하여 512~1024bit 데이터의 모듈러 연산을 반복 수행하며, 512~1024bit의 데이터를 32bit 연산기를 사용하여 연산하므로 데이터를 저장하는 레지스터의 면적을 최소화하여 암호 장치의 면적을 줄이고, 연산 과정에서 발생하는 중간값을 메모리 대신 내부 레지스터에 저장함으로써 메모리 액세스 횟수를 최소화하여 고속의 암호화 연산을 가능하게 하는 IC카드용 RSA암호 연산 장치를 제공하는데 그 목적이 있다.
도 1은 본 발명이 적용되는 IC 카드 시스템의 전체적인 구성 블럭도.
도 2는 도 1에 도시된 암호프로세서의 구성 블록도.
도 3은 도 2에 도시된 모듈러부의 구성 블럭도.
도 4는 도 2에 도시된 감산부의 구성 블록도.
도 5는 도 2에 도시된 모듈러 연산부의 일시예에 따른 곱셈기의 구성 블럭도.
도 6은 도 2에 도시된 제어 레지스터의 일실시예.
* 도면의 주요 부분에 대한 부호의 설명
10 : 데이터 버스 11 : 내부 데이터 버스
100 : 암호프로세서 110 : 메모리
120 : 인터페스부 130 : 제어 레지스터
140 : 제어기부 150 : 입력 레지스터
160 : 모듈러부 161 : 제 1 데이터선택회로
162 : 제 2 데이터선택회로 163 : 덧셈회로
164 : 곱셈회로 165 : 임시 레지스터
166 : 중간값 저장 레지스터 167 : 제3데이터선택회로
170 : 감산부 171 : 뺄셈회로
172 : 출력신호선택회로
이러한 목적을 달성하기 위한 본 발명의 IC카드용 RSA암호 연산 장치의 일측면에 따르면, IC카드 시스템의 프로세서에 연동되는 RSA 암호 연산 장치에 있어서, 모듈러 연산에 필요한 데이터를 각각 할당된 영역에 저장하고, 모듈러 연산이 수행됨에 따라 제어 신호에 의해 순차적으로 연산에 필요한 데이터를 제공하며, 모듈러 연산의 결과값을 저장하는 메모리와, IC카드 시스템의 프로세서에서 전송되는 제어 신호 및 암호 연산을 위한 데이터를 송수신하는 인터페이스부와, 프로세서로부터인터페이스부를 통해 전송되는 제어신호에 따라 암호 연산의 동작모드를 제어하기 정보를 저장하는 제어 레지스터와, 제어 레지스터에 저장된 정보에 따라 모듈러 곱셈 또는 모듈러 지수승 연산을 수행하기 위한 데이터를 메모리로부터 미리 읽어 저장하는 입력 레지스터와, 입력 레지스터에 저장된 값을 읽어 내부 레지스터를 이용하여 암호 연산에 필요한 모듈러 곱셈 또는 모듈러 지수승 연산을 수행하는 모듈러부와, 모듈러부에 의해 연산된 결과값을 보정하는 감산부와, IC카드 프로세서로부터 전송되는 제어신호를 제어 레지스터에 저장하고, 그 제어신호에 따라 모듈러 연산 수행을 위해 메모리로부터 데이터를 로드하여 입력 레지스터를 통해 모듈러부에 제공하여 모듈러 연산을 수행하기 위한 제어신호를 생성하는 제어부를 포함하여 구성된다.
본 발명의 목적과 특징 및 장점들은 첨부된 도면과 관련한 다음의 설명을 통하여 보다 분명해 질 것이다. 이하, 첨부된 도면을 참조하여 본 발명에 따른 실시 예를 상세히 설명한다.
도 1은 본 발명이 적용되는 IC 카드 시스템의 전체적인 구성 블록도로서, 도시된 바와 같이 전원 공급부(1), 암호와 연산을 위한 난수를 발생하는 난수발생부(2), 암호연산을 위한 각종 데이터를 저장하는 메모리(3), 외부의 보안확인장치에 접촉하여 보안확인을 위한 보안센서부(4), IC 카드의 전체적인 동작을 제어하는 프로세서(5), 암호연산을 수행하기 위한 리셋신호를 발생하는 리셋신호 발생부(6), 인터럽트 신호 발생을 위한 인터럽트 발생부(7), 클럭을 발생하기 위한 타이밍부(8), 외부장치와의 인터페이스를 위한 인터페이스부(9), 프로세서(5)의 제어를 받아 암호연산을 수행하는 암호프로세서(100)로 구성된다. 이와 같은 IC 카드 시스템의 전체적인 구성 및 동작은 해당분야에서 공지된 것이므로 상세한 설명은 하지 않기로 하며, 본 발명에 따른 암호프로세서(100)의 구성 및 동작에 대하여 설명하기로 하자.
도 2는 수학식1의 RSA 암호알고리즘을, 수학식3의 몽고메리 모듈러 곱셈 알고리즘과 수학식4의 몽고메리 지수승 알고리즘을 이용하여 효율적으로 구현하기 위한 암호프로세서(110)의 구성을 도시하고 있다. 도 2를 참조하면, 본 발명에 따른 암호프로세서(100)는, 메모리(110), 인터페이스회로(120), 제어 레지스터(130), 제어부(140), 입력 레지스터(150), 모듈러부(160) 및 감산부(170)로 구성된다.
데이터버스(10)는 IC카드 시스템의 데이터버스(155)로서, 메모리(110)와 모듈러 연산을 위한 데이터를 저장하는 입력 레지스터(150), 모듈러부(160)의 출력에 연결되어 모듈러 곱셈에 필요한 데이터나 모듈러 값을 읽어 들이고, 모듈러 연산의 결과값을 메모리(110)에 저장하는 데이터의 경로로 사용된다.
메모리(110)는 데이터와 모듈러 값, 사용자 키 등과 같이 모듈러 연산에 필요한 데이터를 각각 할당된 영역에 저장하고, 모듈러 연산이 수행됨에 따라 제어부(140)에서 발생하는 제어 신호에 의해 순차적으로 연산에 필요한 데이터를 32bit씩 데이터버스(10)를 통해 제공하며, 최종적으로 모듈러 연산의 결과값을 데이터버스(10)를 통해 32bit씩 읽어서 저장한다.
인터페이스회로(120)는 IC카드 시스템의 프로세서(5)에서 전송되는 제어 신호나 데이터를 송수신하며, 암호 회로와 IC카드 시스템의 프로세서(5)와 연산에 필요한 통신을 수행한다.
제어 레지스터(130)는 IC카드 시스템의 프로세서(5)에서 인터페이스회로(120)로 전송되는 제어신호에 따라 암호 회로의 연산 명령과 내부 상태에 관련한 데이터를 저장한다. 제어 레지스터(130)에 저장되는 정보는 도 6에 도시한 바와 같이, 암호 회로의 초기화를 위한 reset 신호, 암호 회로의 연산 시작을 지시하는 start 신호, 암호 회로에서 수행할 동작이 모듈러 곱셈 연산인지 모듈러 지수승 연산인지를 결정하는 동작 모드 선택신호, 암호 회로의 동작이 모듈러 지수승 연산인 경우, 암호화 연산인지 복호화 연산인지를 결정하는 지수승 모드 선택 신호, 암호 회로에서 연산의 수행이 끝났음을 알려주는 end 신호가 저장되어 진다. 각 제어 신호는 1bit데이터로 설정되며 제어 레지스터(130)에 데이터를 저장하는 레지스터 제어신호는 제어부(140)에서 제공된다.
제어부(140)는 모듈러 연산 수행에 필요한 제어신호를 생성하여 각 회로들에 제공하며, IC카드 프로세서(5)에서 암호 회로로 전송되는 제어신호를 제어 레지스터(130)에 저장하기 위한 제어신호와, 모듈러 연산 수행을 위해 메모리(110)에서의 데이터 load를 위한 제어신호와, 모듈러 연산을 수행하기 위해 모듈러 곱셈 연산을 수행하는데 필요한 모든 제어신호, 및 연산이 수행된 후 결과값을 메모리(110)에 다시 저장하는데 필요한 제어신호를 제공한다.
즉 제어부(140)는, 모듈러 연산의 수행을 위해 IC카드의 프로세서(5)에서 암호 회로로 전송되는 제어신호를 제어 레지스터(130)에 저장하기 위한 레지스터 제어신호를 생성하고, 메모리(110)로부터 모듈러 연산에 필요한 데이터를 순차적으로읽어 들이기 위한 메모리(110)의 주소와 메모리(110)의 데이터를 읽고 쓰기 위한 메모리 제어신호를 메모리(110)에 제공하며, 메모리(110)에서 모듈러 회로로 입력되는 데이터들을 입력 레지스터(150)에 선택적으로 저장하기 위한 레지스터 제어신호를 생성하며, 입력 레지스터(150)에 순차적으로 저장되는 데이터들을 이용하여 모듈러 연산을 수행하는 과정에 필요한 제어신호를 생성하며, 모듈러 연산이 수행된 후 결과값을 메모리(110)에 저장하는데 필요한 제어신호와 메모리 주소 및 메모리 제어 신호를 생성하며, 모듈러 곱셈 연산이 종료되었음을 알리는 제어신호를 제어 레지스터(130)에 제공한다.
입력 레지스터(150)는 모듈러 곱셈 또는 모듈러 지수승 연산을 수행하기 위한 데이터를 메모리(110)로부터 32bit단위로 읽어서 저장한다. 이때 입력되는 데이터는 제어 레지스터(130)에 저장된 암호 회로의 동작 모드에 따라 달라지게 된다. 만일 제어 레지스터(130)에 저장된 암호 회로의 동작 모드가 모듈러 곱셈인 경우, 입력 값은 승수A, 피승수B 그리고 모듈러 M 및 몽고메리 모듈러 곱셈을 위해 사전 계산된 값이 되며, 암호 회로의 동작 모드가 모듈러 지수승인 경우, 입력 값은 암호화할 데이터 D, 암호화 키 E, 그리고 모듈러 M 및 몽고메리 모듈러 지수승 연산을 위해 사전 계산된 값이 될 것이다. 이때, 메모리(110)의 데이터를 각 레지스터에 저장하는 레지스터 제어신호는 제어부(130)에서 제공 되어진다.
모듈러부(160)는 암호 연산에 필요한 모듈러 곱셈 또는 모듈러 지수승 연산을 수행하며, 기본적으로 32bit 곱셈 연산을 수행하는 곱셈기와 32bit 덧셈 연산을 수행하는 덧셈기, 연산의 중간값을 저장하기 위한 레지스터, 그리고 덧셈기와 곱셈기의 연산에 필요한 데이터를 선택적으로 설정해 주는 데이터 선택기로 구성되어 있으며, 수학식 3의 몽고메리 모듈러 곱셈 연산과 수학식4의 몽고메리 모듈러 지수승 연산을 제어 레지스터(130)에 설정된 암호 회로 동작 모드 값에 따라, 32bit단위로 반복 연산하여 내부의 중간값 저장 레지스터에 연산 결과를 저장한다. 이때 모듈러부(150)는 모듈러 연산의 수행에 필요한 각 과정의 모든 제어 신호를 제어부(140)로부터 제공 받는다.
감산부(170)는 몽고메리 모듈러 곱셈 또는 지수승 알고리즘에 의해 계산된 결과값을 보정하는 부분으로 수학식3의 단계7의 과정을 수행하며, 모듈러부(160)에서 수행된 결과를 모듈러M과 비교하여 모듈러 값보다 큰 경우에는 모듈러부(160)의 결과값에서 모듈러 값을 뺀 후 그 결과를 메모리(110)에 저장하고, 그렇지 않은 경우에는 모듈러부(160)의 연산 결과를 메모리(110)에 저장한다. 이때 모듈러 연산의 결과가 모듈러M보다 큰 가의 판단은, 모듈러부(160)의 결과값에서 모듈러 값을 최하위 워드에서부터 상위 워드로 32bit씩 뺄셈을 수행하여 최상위 워드의 뺄셈 결과가 자리 빌림 신호를 발생하면, 모듈러부(160)의 연산 결과가 모듈러M보다 적으므로 모듈러부(160)의 연산 결과를 메모리(110)에 저장하고, 자리 빌림 신호가 발생하지 않는 경우에는 뺄셈의 결과를 메모리(110)에 저장한다.
이러한 구성을 갖는 본 발명에 따른 IC카드용 암호 회로의 구체적인 동작을 살펴보자. 도 3은 도 2의 입력 레지스터(150)와 모듈러부(160)를 세부적으로 설명한 도면이다.
도 3에 따른 입력 레지스터(150, 150)는 다시 레지스터Re(151),레지스터Ra(152), 레지스터Rn'(153), 레지스터Rb(154) 그리고 레지스터Rn(155)으로 구성된다.
레지스터Re(151)는 수학식4에 나타낸 몽고메리 모듈러 지수승 연산에서 지수 값 e를 저장하기 위한 레지스터로 32bit 씩 데이터를 저장하며, 제어 레지스터(130)에 설정된 암호 회로의 동작 모드의 값이 지수승 연산으로 설정되면 연산에 필요한 데이터를 메모리(110)로부터 읽어와서 저장한다. 레지스터Re(151)에 데이터를 저장하기 위한 레지스터 제어신호는 제어부(140)에서 제공된다.
레지스터Ra(152)는 32bit 레지스터로써, 제어 레지스터(130)에 설정되는 암호회로의 동작 모드 값에 따라 메모리(110)에서 읽어오는 데이터가 달라진다. 제어 레지스터(130)의 동작 모드가 몽고메리 모듈러 곱셈 연산으로 설정되면, 레지스터Ra(152)에는 수학식3의 승수A를 저장하며, 제어 레지스터(130)의 연산 모드가 몽고메리 모듈러 지수승 연산으로 설정되면, 레지스터Ra(152)에는 수학식4의 데이터A(R mod M)를 저장한다. 레지스터Ra(152)로 데이터의 저장은 제어부(140)에서 메모리(110)로 제공하는 메모리 제어신호에 의해 메모리(110)의 해당 주소의 데이터가 데이터버스(10)에 전송되면, 제어부(140)에서 제공하는 레지스터 제어신호에 의해 데이터버스(10)의 데이터를 저장한다.
레지스터Rn'(153)은 수학식3의 몽고메리 모듈러 곱셈 연산을 수행하는 단계4에서 (r - M0)-1값을 저장하는 32bit 레지스터로써, (r - M0)-1값은 제어 레지스터(130)에 설정되는 암호 회로의 동작 모드에 상관없이, 모듈러M에 대해 일정한 값을 가지며, 미리 계산되어 메모리(110)에 저장된 값이다. 또한 (r - M0)-1값은 모듈러 곱셈 연산이나 모듈러 지수승 연산에 상관없이 정해진 모듈러M값에 대해 일정하므로 암호 회로의 동작에서 한 번만 읽어 들이면 된다. 레지스터 Rn'에 메모리의 데이터를 load하는 레지스터 제어신호 역시 제어부(140)에서 제공된다.
레지스터Rb(154)는 레지스터Ra(152)와 같이 모듈러 연산에 필요한 데이터를 저장하는 32bit 레지스터이며, 제어 레지스터(130)에 설정된 암호 회로의 동작 모드의 값에 따라 메모리(110)에서 읽어오는 데이터가 달라진다. 제어 레지스터(130)의 동작 모드가 몽고메리 모듈러 곱셈 연산으로 설정되면, 레지스터Rb(154)에는 수학식3의 피승수B를 저장하며, 제어 레지스터(130)의 연산 모드가 몽고메리 모듈러 지수승 연산으로 설정되면, 레지스터Rb(154)에는 수학식4의 데이터xp(xR mod M)를 저장한다. 레지스터Rb(154)에 데이터를 저장하기 위한 레지스터 제어신호 역시 제어부(140)에서 제공된다.
레지스터Rn(155)은 암호 회로의 연산을 위한 모듈러M 값을 메모리(110)에서 읽어서 저장하는 레지스터이며 제어부(130)에서 제공되는 레지스터 제어신호에 의해 동작한다.
도 3은 도 2의 모듈러부(160)의 세부 구조를 도시하고 있다. 도 3을 참조하여 모듈러부(160)를 살펴보면, 제1데이터선택회로(161), 제2데이터선택회로(162), 덧셈회로(163), 곱셈회로(164), 임시 레지스터(165), 중간값 저장 레지스터(166), 내부 데이터버스(11) 및 제3데이터선택회로(167)로 구성된다.
제 1데이터선택회로(161)는 수학식3의 32bit 곱셈 연산을 수행하는 곱셈회로(164)의 입력 데이터들을 내부 데이터버스(11)에서 선택적으로 공급하며,데이터의 순차적 선택을 위한 선택 제어신호는 제어부(140)에서 제공받는다.
제 2데이터선택회로(162)는 수학식3의 몽고메리 곱셈 알고리즘을 위한 덧셈 연산을 수행하는 덧셈회로(163)에 입력되는 데이터를 순차적으로 선택하며, 덧셈 연산을 위한 데이터의 경로를 설정하는 제어신호는 제어부(130)에서 제공된다.
32bit 데이터의 덧셈 연산을 수행하는 덧셈회로(163)는 수학식3에서 덧셈 연산의 수행뿐 아니라, 32bit 곱셈회로(164)의 출력 중 상위 32bit 결과를 다음 곱셈의 결과와 더하여 순차적인 곱셈 과정을 수행하는 과정에서 사용되어지며, 또한 전체 데이터의 곱셈 연산의 결과를 저장하는 중간값 저장 레지스터(166)에 연산 결과를 저장하기 전에 최상위 워드의 캐리 값을 계산하기 위해 사용된다.
덧셈회로(163)는 32bit 데이터의 덧셈 연산을 수행하는 덧셈기(163a)와 덧셈 결과를 저장하기 위한 레지스터R_sum(163b), 덧셈 결과 발생하는 캐리를 저장하기 위한 1bit 레지스터C(163c)로 구성된다. 덧셈 연산의 결과를 저장하는 레지스터 R_sum(163b)의 데이터는 다음 연산을 위해 내부 데이터버스(11)를 통해 회로들에 제공되며, 덧셈 연산의 자리올림을 저장하는 레지스터C(163c)의 데이터는 다음 연산의 입력으로 사용되거나 또는 경우에 따라 버려지게 된다. 레지스터R_sum(163b)과 레지스터C(163c)의 데이터를 저장하기 위한 레지스터 제어신호 및 레지스터C(163c)의 값을 버리기 위한 제어신호는 제어부(140)에서 공급되어진다.
곱셈회로(164)는 곱셈 연산을 수행하는 회로로써, 모듈러 연산 수행을위해 32bit 데이터를 입력으로 받아서 64bit의 곱셈 출력을 갖는 조합 회로이다. 곱셈회로(164)는 수학식3에서 단계4의 Qi= ((S0+ AiB0)( r - M0)-1) mod r에서 AiB0의 곱셈 연산과 단계5의 (S + AiB + QiM) div r에서 AiB와 QiM의 곱셈 연산을 32bit씩 순차적으로 수행한다. 이때, 곱셈 연산의 반복적이고 순차적 수행은 제어부(140)에서 제공되는 제어신호에 의해 제1데이터선택회로(161)가 입력 레지스터(150), 임시 레지스터(165) 또는 중간값 저장 레지스터(166)의 데이터를 선택하여 공급함으로써 수행된다.
곱셈회로(164)는 수학식3의 단계4와 단계5의 곱셈 연산과 덧셈 연산을 동시에 수행하기 위하여 구성된 회로로써, 연산의 수행 속도를 높이기 위해 미리 32bit 데이터를 저장하기 위한 레지스터(164a~164d)와 32bit 데이터의 곱셈을 8bit나 16bit 또는 32bit 단위로 분할하여 반복적으로 연산을 수행하기 위해 곱셈기(164g)의 데이터를 8bit, 16bit 또는 32bit씩 선택하여 입력하는 데이터 선택기(164e), 그리고 32bit 데이터를 입력 받아 32bit*32bit+32bit+32bit 연산을 수행하는 곱셈기(164g), 그리고 곱셈기(164g)의 64bit 출력 데이터를 순차적으로 저장하는 레지스터(164h)로 구성된다.
또한 곱셈회로(164)는 곱셈 연산을 보다 빨리 수행하기 위하여 곱셈연산과 덧셈 연산을 한 클럭에 수행할 수 있게 도 5에 도시한바와 같이 additive 곱셈기(164_8)를 사용하여 구성 할 수도 있으며, 도 5에서 곱셈에 사용되는 데이터를 레지스터(164_1, 164_3, 164_4, 164_6)에 저장하지 않고 데이터버스(10)에서 직접 입력 받을 수도 있다.
임시 레지스터(165)는 수학식3의 몽고메리 곱셈 연산을 수행할 때 곱셈회로(164)의 출력 중 상위 32bit의 데이터를 저장하는 Reg_hi(165a)과 하위 32bit의 데이터를 저장하는 Reg_low(165b)로 구성된다. 임시 레지스터(165a, 352)의 데이터는 내부 데이터버스(11)를 통해 상기한 연산 회로들에 공급되며, 다음 순서의 연산에 사용되어지거나 중간값 저장 레지스터(166)에 저장된다.
중간값 저장 레지스터(166)는 수학식3과 수학식4에 따른 모듈러 연산을 반복하여 수행할 때 각 단계의 결과값을 순차적으로 저장한다. 모듈러 곱셈 연산의 중간값을 메모리(110)에 직접 저장하는 경우, 연산을 수행할 때 마다 필요한 데이터를 메모리(110)에서 직접 load하는 방식은 메모리에 액세스하는 횟수에 비례하여 시간이 증가되므로, 중간값을 메모리(110)에 저장하는 대신 빠른 시간에 데이터를 load할 수 있는 레지스터에 저장하여 메모리에 액세스하는 횟수를 줄임으로써, 모듈러 연산에 걸리는 시간을 줄이기 위해 사용한다. 중간값 저장 레지스터(166)는 32bit로 이루어진 레지스터의 조합으로 이루어지며, 그 크기는 모듈러 곱셈 연산을 수행하는 과정에서 발생하는 자리올림을 고려하여 모듈러 곱셈을 계산하는 데이터의 길이보다 1워드 더 크게 사용한다. 즉, 512bit의 모듈러 곱셈 연산을 수행하는 경우에는 544bit의 크기를 사용하며, 1024bit의 모듈러 곱셈을 사용하는 경우에는 1056bit의 길이를 갖는다. 또한, 중간값 저장 레지스터(166)의 각 워드의 값은, 32bit 곱셈회로(164)를 이용한 모듈러 곱셈 연산의 결과를 순차적으로 하위 워드에서 상위 워드로 저장하며, 이때 곱셈회로(164)의 결과를 저장하기 위한 중간값 저장 레지스터(166)의 워드 위치는 제어부(140)에서 제공하는 제어신호에 따라 제3데이터선택회로(167)가 설정한다.
중간값 저장 레지스터(166)의 최상위 워드는 실제로 최하위의 1bit만 사용하므로 중간값 저장 레지스터(166)의 크기는, 계산하는 데이터의 길이보다 1bit만 더 길게 사용할 수도 있다. 32bit씩 곱셈 연산을 이용하여 모듈러 곱셈 연산을 수행하여 모든 곱셈 과정이 끝난 후, 중간값 저장 레지스터(166)에 저장된 값은 몽고메리 모듈러 곱셈의 결과일 수도 있고, 결과보다 모듈러 값 만큼 클 수도 있다. 만일 중간값 저장 레지스터(166)의 값이 모듈러 값보다 큰 경우, 중간값 저장 레지스터(166)의 값에서 다시 모듈러 값을 빼 주는 연산을 수행하여야 한다.
내부 데이터버스(11)는 암호 회로 내부에서 연산 회로 사이에 연결된 데이터 경로로써, 각 연산 회로들은 서로 공통적으로 사용하는 데이터 경로를 사용할 수도 있고 또는 독립적으로 연결된 데이터버스를 사용할 수도 있다. 내부 데이터버스(11)는 입력 레지스터(150)의 데이터를 연산 회로에 제공하는 경로로 사용되고, 암호 회로의 연산 과정에서 발생하는 값들을 연산을 수행하는 덧셈회로(163), 곱셈회로(164)에 제공하는 경로로 사용되며, 곱셈회로(164)의 연산 결과를 임시 레지스터(165)에 저장하는 경로를 제공하며, 덧셈회로(163)의 연산 결과를 다른 연산 회로에 제공하며, 연산의 결과를 중간값 저장 레지스터(166)에 저장하는 경로로 사용된다.
제3데이터선택회로(167)는 512~1024bit 이상의 큰 데이터를 32bit곱셈회로(164)와 32bit 덧셈회로(163)를 이용하여 반복적으로 계산할 때, 각 연산 과정에서 발생하는 결과값을 중간값 저장 레지스터(166)의 적절한 위치에 순차적으로 저장하기 위한 워드의 위치를 지정하며, 중간값 저장 레지스터(166)의 위치를 지정하는 경로 제어신호는 컨트롤 회로(140)에서 제공 받는다.
중간값 저장 레지스터(166)에 저장된 값과 모듈러 값의 비교를 통한 모듈러 연산 값의 보정은 도2의 감산부(170)에서 수행하게 된다. 도2의 감산부(170)를 도4에서 세부적으로 살펴보면, 뺄셈회로(171), 출력신호선택회로(172)로 구성된다.
뺄셈회로(171)는 모듈러 연산이 끝난 후 모듈러 연산의 결과값을 보정하기 위해, 모듈러부(160)의 출력에서 모듈러M값을 32bit씩 뺄셈 연산을 수행하는 조합회로로써, 중간값 저장 레지스터(166)의 값과 모듈러M값을 하위 워드에서 상위 워드로 32bit씩 차례로 입력 받아 뺄셈 연산을 수행한다. 이때 중간값 저장 레지스터(166)의 값과 메모리(110)로부터 모듈러M값을 순차적으로 읽어 들이는 제어신호는 제어부(140)에서 제공된다.
뺄셈회로(171)의 동작을 살펴보면, 32bit씩 하위 워드에서 상위 워드로 32bit 뺄셈기(171a)에서 수행되는 뺄셈 연산의 결과값은 레지스터R_sub(171b)에 저장되며, 레지스터R_sub(171b)에 저장된 32bit의 뺄셈 결과는 다음 상위 워드의 뺄셈 연산 과정에서 메모리(110)에 저장되고, 뺄셈 과정에서 발생하는 자리 빌림 신호는 다음 상위 워드의 뺄셈 연산에 사용되기 위해 자리 빌림 레지스터B(171c)에 저장되어 다시 뺄셈기(171a)에 입력 되어진다. 이때, 뺄셈 연산의 결과를 메모리(110)에 저장하기위해 제어부(140)는 출력신호선택회로(172)를 설정한다.
하위 워드에서 최상위 워드까지 뺄셈 연산의 수행이 끝나면, 메모리(110)에는 모듈러부(160)의 결과에서 모듈러M값을 뺀 결과가 저장되어 있고, 중간값 저장레지스터(166)에는 모듈러 연산의 결과가 저장되어 있다. 뺄셈 연산을 수행하는 과정에서 뺄셈 연산의 결과값을 레지스터R_sub(171b)에 저장하기 위한 레지스터 제어신호와 뺄셈 과정에서 발생하는 자리 빌림 신호를 자리 빌림 레지스터B(171c)에 저장하기 위한 레지스터 제어신호는 제어부(140)에서 제공된다.
모듈러 연산의 결과값에 대해 보정을 위한 뺄셈 연산이 끝난 후, 제어부(140)가 뺄셈회로(171)의 자리 빌림 레지스터B(171c)의 값을 검사하여 메모리(110)에 저장되어질 결과값을 중간값 저장 레지스터(166)의 값으로 다시 저장할 것인지, 아니면 뺄셈 과정을 수행하면서 메모리(110)에 저장된 값을 그냥 둘 것인지를 결정하면, 출력신호선택회로(172)는 메모리(110)에 저장될 데이터의 경로를 설정한다.
즉, 모듈러부(160)에서 몽고메리 모듈러 연산이 끝난 후, 감산부(170)는 32bit씩 뺄셈 연산을 순차적으로 수행하면서 레지스터R_sub(163b)에 저장되는 뺄셈의 결과는 다음 상위 워드의 뺄셈 과정에서 메모리(110)에 저장된다. 이러한 순서를 반복하여 뺄셈 연산이 끝나면 메모리(110)에는 모듈러부(160)의 결과값에서 모듈러M값을 뺀 결과가 저장되어 있으며, 중간값 저장 레지스터(166)에는 모듈러부(160)의 연산 결과가 그대로 저장되어 있다.
제어부(140)에서는 뺄셈 연산이 수행된 후 뺄셈회로(171)의 자리 빌림 레지스터B(171c)의 값을 검사 하였을 때, 자리 빌림이 있으면 모듈러부(160)의 연산 결과가 모듈러M 보다 적으므로 중간값 저장 레지스터(166)의 값을 메모리(110)에 저장한다. 이때 중간값 저장 레지스터(166)의 값을 메모리(110)에 순차적으로 저장하기 위해 중간값 저장 레지스터(166)에서 32bit씩 데이터를 읽어서 데이터버스(10)에 load하는 레지스터 제어신호와 데이터버스(10)의 데이터를 메모리(110)의 해당 번지에 저장하기 위한 메모리 주소 및 메모리에 데이터를 쓰기 위한 메모리 제어신호는 제어부(140)에 의해 제공된다. 이러한 순서로 중간값 저장 레지스터(166)의 값들이 메모리(110)에 저장되면, 제어부(140)는 제어 레지스터(130)에 연산이 끝났음을 표시하는 end 신호를 저장한다. 이때 제어 레지스터(130)에 end 신호를 설정하기 위한 레지스터 제어신호는 제어부(140)에서 공급한다.
만일 제어부(140)가 뺄셈 연산이 수행된 후 뺄셈회로(171)의 자리 빌림 레지스터B(171c)의 값을 검사 하였을 때, 자리 빌림이 없으면 모듈러부(160)의 연산 결과에서 모듈러M을 뺀 결과가 모듈러 연산의 결과이며, 뺄셈 연산 과정에서 이미 그 결과 값이 메모리(110)에 저장 되었으므로, 제어부(140)는 제어 레지스터(130)에 연산이 끝났음을 표시하는 end 신호를 저장한다.
도2와 도3, 도4의 구성을 갖는 모듈러부의 보다 구체적인 동작을 모듈러 곱셈 연산과 모듈러 지수승 연산에 대해 각각 살펴보기로 하자. 먼저, 본 발명에서 제안하는 암호 회로가 1024bit의 모듈러 곱셈 연산을 수행하는 경우를 설명한다.
메모리(110)에는 모듈러 곱셈을 위한 1024bit 데이터 값인 승수 A와 피승수 B, 그리고 모듈러 M 및 몽고메리 알고리즘을 이용하여 모듈러 곱셈을 수행하기 위한 32bit 값인 사전 계산 값 R'이 IC카드의 프로세서(5)에 의해 저장되어 있다.
IC카드의 프로세서(5)에서 모듈러 곱셈의 연산이 필요하여 암호프로세서(100) 내의 암호 회로를 구동하기 위해, IC카드 프로세서(5)는 데이터버스(10)를 통해 제어신호를 암호프로세서(100)로 보내게 된다. 암호프로세서(100)로 보내진 제어신호는 인터페이스회로(120)에 전달된 후, 제어 레지스터(130)에 암호 회로의 동작 모드가 모듈러 곱셈이며, 동작의 시작을 알리는 start 신호가 입력되었음을 각각 설정한다.
제어 레지스터(130)의 데이터를 통해 암호 회로의 동작 모드가 모듈러 곱셈 연산이며, 연산의 시작 명령을 탐지한 제어부(140)는 먼저 암호 회로 내의 모든 블럭들을 초기화 한 후, 모듈러 곱셈 연산을 수행하기 위하여 초기 데이터 값인 승수A와 피승수B, 모듈러M의 최하위 워드의 값 및 몽고메리 곱셈을 수행하기 위해 미리 계산된 값R'을 순차적으로 읽어서 레지스터Ra(152), Rb(154), Rn(155), Rn'(153)에 저장하도록 메모리 제어신호와 레지스터 제어신호를 발생한다.
수학식 3의 단계2에서 인수i는 단계4와 단계5의 연산을 반복하는 횟수를 나타내는 인수로써, 1024bit 데이터의 모듈러 곱셈 연산을 수행하기 위한 n값이 32이므로, i값은 0에서 31까지 32번의 반복 과정을 갖는다.
단계4의 Qi는 단계2의 i값이 0, 1, ……, 31까지 증가하는 과정에서 각 반복 과정에서 일정한 값을 가지며, 단계4의 Qi = ((S0 + Ai B0 )( r - M0 )-1 ) mod r 연산은 다시 두 번의 곱셈 과정을 거치게 된다. 먼저 (r - M0)-1값은 사전 계산 값으로 메모리(110)에 저장되어 초기 데이터로써 레지스터Rn'(153)에 저장되어 있으며, (S0 + Ai B0 ) 값은 i번째 반복 루틴에서의 승수A의 i번째 워드 데이터와 피승수B의 최하위 워드의 곱과 중간값 저장 레지스터(166)의 최하위 워드의 합으로 구해지며, 다시 이 값들은 레지스터Rn'(153)에 저장된 값과 곱셈 연산을 수행 후 modr연산에 의해 하위 32bit 데이터만 Qi 의 값으로 남게 된다. 단계4의 연산 과정은 2번의 곱셈 연산과 덧셈 연산에 의해 이루어지므로 연산의 수행 시간을 줄이기 위해 곱셈 연산 과정 중에 다음 곱셈을 위한 데이터를 메모리(110)에서 읽어서 해당 레지스터에 저장하도록 제어부(140)에서 제어신호를 발생한다.
단계5의 연산은 모듈러 곱셈 연산을 수행하기 위해 가장 많은 수행 시간이 소요되는 부분으로써, S와 B, M은 모두 1024bit 길이를 갖는 데이터이다. 따라서 32bit 곱셈기와 32bit 덧셈기를 이용하여 연산을 수행하는 경우 모두 32번의 반복적인 연산이 수행되어진다. 단계5의 연산을 수행하기 위하여 S와 B, M 데이터들은 각각 32bit씩 메모리(110)로부터 입력되어지며, S0+AiB0+QiM0, S1+AiB1+QiM1, ……, S31+AiB31+QiM31의 순서로 하위 워드에서 상위 워드로 연산을 수행하며 그 값들은 중간값 저장 레지스터(166)에 순차적으로 저장된다. 만일 단계5의 각 연산의 결과값들을 중간값 저장 레지스터(166)가 아닌 메모리에 직접 저장하는 경우, 단계5를 수행하기 위해 승수와 피승수를 읽어 들이는 시간 뿐 아니라 각 반복 단계의 결과값을 메모리에 쓰기 위한 시간까지 필요하므로, 모듈러 곱셈을 수행하기 위한 연산 시간이 증가하게 되어 고속의 모듈러 곱셈 연산을 수행할 수 없다.
루틴i에 대해 각 덧셈들은 Sj+AiBj+QiMj로 표시되며 여기서 j는 단계 5를 0에서 31까지 반복 수행하는 내부 루틴의 횟수를 나타내는 인수이다. 각 j번째 연산은 다시 Sj+AiBj 연산과 그 결과에 QiMj의 결과를 더하는 단계로 구분되어지며, 연산에서 발생하는 64bit데이터 중 하위 32bit데이터는 임시 레지스터Reg_low(165b)에 저장된 후, 중간값 저장 레지스터(166)의 j번째 워드 위치에 저장되고, 상위 32bit데이터는 임시 레지스터Reg_hi(165a)에 저장된 후, j+1번째 루틴의 연산에서 사용되어 더해지게 된다. 단계5의 j가 32번의 반복 연산을 수행하면 중간값 저장 레지스터(166)에는 루틴 i에 대한 S값인 1024bit데이터가 저장되고, 중간값 저장 레지스터(166)의 최상위 워드에는 연산5의 단계에서 발생한 자리 올림 데이터가 저장된다.
루틴 i에 대해 단계4와 단계5의 반복 연산이 모두 끝나면 인수 i값을 1증가 시킨 후, 다시 단계4와 단계5의 반복 연산을 수행하며, 이러한 연산은 인수 i가 32번 반복할 때까지 계속된다. 위의 반복 과정을 위해서 메모리에서 i번째 승수 값 Ai와 j번째 피승수 값 Bj, 그리고 모듈러값 Mj는 연산의 수행 속도를 높이기 위하여, 현재 곱셈 연산 중에 다음 반복 과정의 데이터를 미리 읽어서 저장함으로써 메모리(110)로부터 데이터를 load하는데 걸리는 시간을 감소할 수 있다.
이러한 방법으로 반복 회수 값을 증가하면서 연산을 수행하여, 최상위 워드까지 모듈러 곱셈 연산을 수행하면, 중간값 저장 레지스터(166)에는 모듈러 회로의 연산 결과값이 저장되어 있다. 몽고메리 모듈러 곱셈 알고리즘은 결과값에 대한 어떠한 추정에 의해 승수와 피승수 값을 다른 잉여류 수 체계로 변환하여 연산을 수행하므로, 그 결과 역시 정확한 값이 아닐 수 있다. 따라서 모듈러 곱셈을 수행 한 후의 값이 정확한 값인지 검토하여 결과값을 보정해주는 작업이 필요하다.이러한 보정 작업은 몽고메리 모듈러 곱셈의 결과값이 원래 원하는 출력 값이거나 또는 원래 출력 값보다 모듈러M만큼 크다는 몽고메리 알고리즘의 사실을 이용한다.
몽고메리 곱셈 연산의 결과값을 보정하기 위하여 먼저, 제어부(140)는 중간값 저장 레지스터(166)의 최상위 워드 값이 1인지 검사한다. 만일 중간값 저장 레지스터(166)의 최상위 워드가 1이면, 몽고메리 모듈러 곱셈 연산의 값이 원래 원하는 값보다 모듈러M만큼 큰 경우이므로, 중간값 저장 레지스터(166)의 데이터에서 모듈러M을 빼는 연산을 수행해야 한다. 뺄셈 연산은 중간값 저장 레지스터(166)의 최하위 워드와 메모리(110)에 저장된 모듈러 값 M의 최하위 워드에서 상위 워드로 뺄셈이 수행되며, 뺄셈의 결과는 레지스터R_sub(171b)에 저장된 후 다시 메모리(110)에 저장된다. 이때 중간값 저장 레지스터(166)에는 모듈러 곱셈 연산의 결과가 그대로 저장되어 있다.
모듈러 곱셈 연산의 결과값 보정을 위한 뺄셈 연산을 수행 할 때, 메모리(110)에서 모듈러M을 순차적으로 읽어와서 레지스터Rn(155)에 저장하기 위한 메모리와 레지스터 제어신호는 제어부(140)에서 공급되며, 뺄셈 연산이 수행되는 동안 다음 상위 워드의 뺄셈을 위해서 미리 상위 워드의 모듈러 값을 메모리(110)에서 읽어와서 레지스터Rn(155)에 저장 할 수 있게 제어신호를 발생한다.
중간값 저장 레지스터(166)의 최상위 워드가 1인 경우에는 중간값 저장 레지스터(166)의 데이터는 1024bit데이터인 모듈러M보다 크므로, 뺄셈 연산을 32개 워드의 데이터만 뺄셈에 사용하고, 최상위 워드 데이터의 뺄셈 결과 발생하는 레지스터B(171c)의 자리 빌림 신호는 무시하고, 제어부(140)는 연산이 종료되었음을 알리는 제어신호를 제어 레지스터(130)에 설정한다.
만일 중간값 저장 레지스터(166)의 최상위 워드 값이 0이라면 모듈러 곱셈연산의 결과로 저장된 중간값 저장 레지스터(166)의 값과 모듈러M값 중 어느 값이 큰지 알 수 없게 된다. 따라서 이 경우에는 중간값 저장 레지스터(166)의 값에서 모듈러M을 빼서 나오는 레지스터B(171c)의 자리 빌림 데이터를 이용하여 크기를 판단할 수 있다.
중간값 저장 레지스터(166)의 최상위 워드의 값이 0인 경우 모듈러 곱셈의 결과를 보정하기 위하여, 중간값 저장 레지스터(166)의 최하위 워드 값과 메모리(110)에 저장된 모듈러M의 최하위 워드를 load하여 32bit 뺄셈 연산을 수행하여 발생하는 결과값은 레지스터R_sub(171b)에 저장한 후 다시 메모리(110)에 저장하고, 뺄셈 과정에서 발생하는 자리 빌림 신호는 다음 상위 워드 데이터의 뺄셈 연산을 위하여 레지스터B(171c)에 저장되어 다음 뺄셈 연산에 제공되어 진다.
이때 다음 상위 워드의 데이터는 빠른 연산 수행을 위해 뺄셈 연산을 수행하는 과정에서 메모리(110)에서 레지스터Rn(155)에 저장할 수 있도록 레지스터 제어신호를 제어부(140)에서 제공한다.
상기와 같이 하위 워드에서 최상위 워드까지 순차적으로 뺄셈 연산을 수행하면, 중간값 저장 레지스터(166)에는 여전히 몽고메리 모듈러 곱셈 연산의 결과가 저장되어 있고, 메모리(110)에는 몽고메리 모듈러 곱셈 연산의 결과인 중간값 저장 레지스터(166)의 값에서 모듈러M을 뺀 결과가 저장되어 있다. 뺄셈 연산이 모두 끝난 후 모듈러 곱셈의 결과값 선택은 최상위 워드의 뺄셈을 수행하고 발생한 레지스터B(171c)의 자리 빌림 신호를 이용하여 결정할 수 있다.
만일 자리 빌림 신호가 1이면 중간값 저장 레지스터(166)의 데이터가모듈러M 보다 작으므로 중간값 저장 레지스터(166)의 값을 메모리(110)에 다시 저장하도록 제어신호를 제어부(140)에서 공급하며, 중간값 저장 레지스터(166)의 데이터가 메모리(110)에 모두 저장되면 제어부(140)는 연산이 끝났음을 지시하는 제어신호를 제어 레지스터(130)에 설정한다.
만일 자리 빌림 신호가 0이면 중간값 저장 레지스터(166)의 값이 모듈러M 보다 큰 경우이므로, 뺄셈 연산 과정에서 저장된 현재 메모리(110)의 값이 모듈러 곱셈의 결과이므로 제어부(140)는 제어 레지스터(130)에 연산이 끝났음을 지시하는 제어 신호를 설정한다.
인터페이스회로(120)를 통해 제어 레지스터(130)로부터 연산이 끝났음을 알리는 제어신호를 받은 프로세서(5)는 모듈러 곱셈 연산의 결과를 메모리(110)로부터 데이터버스(155, 10)를 통해 load하여 연산에 사용한다.
이러한 과정은 제어 레지스터(130)에 설정된 암호 회로의 동작 모드가 모듈러 곱셈 연산으로 설정된 경우에 대하여 기술하였다. 지금부터는 암호 회로의 동작이 모듈러 지수승 연산으로 설정된 경우에 대해 살펴보자.
먼저, 수학식4에 따른 모듈러 지수승 연산을 위한 데이터 A(R mod M), 암호화 할 데이터 x에 대한 몽고메리 잉여류 수 체계로의 변환 값 xp(xR mod M), 사용자의 키 값인 E 또는 D, 모듈러M값들이 프로세서(5)에 의해 메모리(110)에 저장되어 있다.
모듈러 지수승 연산을 위해 몽고메리 잉여류 수 체계로 변환되는 값 A와 xp는 소프트웨어에서 계산하여 메모리(110)에 입력되어 질 수도 있고, 모듈러 곱셈연산을 이용하여 하드웨어적으로 계산하여 메모리(110)에 저장될 수도 있다.
IC카드 프로세서(5)에서 데이터의 암호화를 위해 모듈러 지수승 연산을 수행하려는 경우, IC카드 프로세서(5)는 데이터버스(10)를 통해 암호회로의 동작 모드와 동작의 시작을 알리는 제어신호를 암호프로세서(100)로 전송한다. 암호프로세서(100)로 전송된 제어신호는 인터페이스회로(120)를 통해 제어 레지스터(130)에 암호회로의 동작 모드가 모듈러 지수승이며, 지수승 연산을 시작을 의미하는 start 신호를 설정한다.
제어 레지스터(130)를 통해 암호회로의 동작 모드가 모듈러 지수승 연산이며, 연산의 시작을 지시하는 start 신호가 설정되었음을 인지한 제어부(140)는 먼저 암호 회로 내의 모든 블럭들을 초기화 한 후, 모듈러 지수승 연산을 수행하기 위하여 메모리(110)로부터 데이터 A, xp, M을 최하위 워드 값을 읽어서 레지스터Ra(152), Rb(154), Rn(155)에 각각 저장한다. 또한 지수 값 E(또는 D)는 수학식4의 연산에서 최상위 bit에서부터 연산을 시작하므로, 지수 값 E(또는 D)의 최상위 워드의 값을 읽어서 Re(151)에 저장한다.
수학식4의 모듈러 지수승 연산을 위해 사용되는 지수승 값 e = (et…e1e0)2에서 et=1이다. 즉 지수 값의 최상위 bit et는 0이 아닌 첫번째 1의 값을 갖는 e 값의 실질적인 최상위 자리를 의미하므로, 먼저 제어부(140)는 지수 값E의 실질적인 최상위 bit를 의미하는 t값을 찾아야 한다.
지수 값E의 실질적인 최상위 bit를 의미하는 t값을 구하기 위해,제어부(140)는 초기에 t값을 구하기 위한 반복 인수 i를 데이터의 최대값인 1024로 설정하고, 레지스터Re(151)에 저장된 32bit값 E가 0인지 검사한다. 만일 레지스터Re(151)에 저장된 E가 0이면, 제어부(140)는 반복 인수 i에서 워드의 bit수 32를 감소시키고, 다음 상위 워드의 E값을 읽어 들여서 레지스터Re(151)에 저장한 후 다시 32bit값 E가 0인지 검사한다. 상기 과정은 지수승 E의 실질적인 최상위 bit의 위치를 찾기 위해 먼저 최상위 워드를 찾는 과정으로, 인수 i의 값은 32의 배수 값을 갖는다.
이러한 과정을 반복하여 0이 아닌 최상위 워드의 위치를 찾았으면, 그 워드에서 다시 최상위 bit의 위치를 찾는 과정을 수행한다. 먼저 해당 워드의 최상위 bit부터 하위 bit로 검색하면서 bit의 값이 1인지 검사 한다. 만일 bit의 값이 0이면, 인수 i의 값을 1감소한 후 다음 bit의 값이 1인지 검사하는 과정을 거친다. 이러한 과정을 반복하면서 bit의 값이 1이 나오면 그때의 인수 i값이 지수 값E의 실질적인 최상위 위치를 나타내는 t의 값이며, 인수 i는 수학식4의 단계1과 3에서 연산의 반복 회수를 지정하는 변수i로 사용된다.
지수 값 E의 최상위 위치 t를 찾기 위해 상기와 같이 워드의 위치를 찾는 대신 최상위 워드부터 하위 워드로 진행하면서 각 워드의 최상위 bit부터 최하위 bit로 각 bit의 값이 1인지 검색하여, t의 위치를 구하는 방법을 적용할 수 있음은 물론이다.
지수 값E의 최상위1의 위치 t를 구한 후, 암호 회로는 수학식4에 단계2의 제곱 연산에 따라 먼저 A = Mont(A, A)를 수행한다. Mont()는 상기한 몽고메리 모듈러 곱셈 연산을 의미하고 Mont(A, A)는 몽고메리 모듈러 곱셈 연산에 사용되는 승수와 피승수가 모두 A값으로, 상기한 몽고메리 모듈러 곱셈을 수행한 후 그 결과를 다시 메모리(110)의 A영역에 저장함을 의미한다. 상기 단계2의 제곱 연산을 보다 빨리 수행하기 위해 모듈러 곱셈 연산장치 대신 제곱 회로를 별도로 사용할 수도 있다.
단계3에서는 단계2의 제곱과정 수행 후 현재 반복 인수 i번째 bit에 해당하는 지수 값 ei가 1이면 A = Mont(A, xp) 연산을 상기한 모듈러 곱셈 연산을 이용하여 수행한다. 만일 현재 인수 i에 해당하는 지수 값 ei의 bit값이 0이면 반복 회수를 나타내는 인수 i의 값을 1감소한 후, 다시 단계2와 단계3의 과정을 수행한다. 상술한 단계2와 단계3의 반복을 수행할 때마다 반복 인수 i를 1씩 감소하여, 지수 값E의 최하위 bit를 나타내는 i=0까지 반복하여 수행한다.
몽고메리 모듈러 연산은 결과값에 대한 추정에 의한 연산을 위해 원래 데이터들을 몽고메리 잉여류 수 체계로 변환하기 위하여 모듈러M에 의해 구한 상수 R을 이용하였다. 몽고메리 잉여류 수 체계로 변환된 값으로 상술한 반복 과정을 (t+1)번 수행하여 얻은 결과값에는 계속해서 상수R에 관련한 값이 포함되어 있다.
따라서 원래의 모듈러 연산 값을 구하기 위해서는 몽고메리 모듈러 연산 결과에 포함되어 있는 상수 R에 의한 값들을 소거해주어야 한다. 이러한 과정을 몽고메리 리덕션 과정이라 하며, 수학식4의 단계4와 같이 A = Mont(A, 1)의 연산을 수행함으로써 원래의 모듈러 지수승 값을 구할 수 있다.
단계4의 Mont(A, 1)을 수행하기 위한 몽고메리 곱셈 연산에서, 피승수B의 값을 1로 설정하는 것은 IC카드 프로세서(5)에서 메모리(110)의 피승수B의 값을 1로 설정하여 계산할 수 있다. 또한 상술한 단계4의 연산을 위한 피승수B의 값은, 메모리(110)의 데이터는 유지하고 제어부(140)에서 단계4의 몽고메리 곱셈을 수행할 때, 곱셈의 첫번째 반복에서 레지스터Rb(154)의 값을 1로 설정하고 나머지 반복에서는 0으로 설정하여 구동 할 수도 있다.
이와 같이 반복적인 연산에 의해 모듈러 지수승 연산이 수행되면, 제어부(140)는 연산이 끝났음을 지시하는 end 제어신호를 제어 레지스터(130)에 설정하고, 다음 연산의 명령을 기다리는 초기 상태로 설정한다.
결국 본 발명에 따른 IC카드용 암호 장치는 512~1024bit 이상의 큰 데이터에 대해 모듈러 연산을 수행하는 경우, 암호회로의 동작을 제어하는 제어 레지스터를 이용하여 모듈러 곱셈 연산과 모듈러 지수승 연산을 선택적으로 수행하여 암호회로의 활용성을 높이고, 연산에 필요한 회로를 32bit 연산기를 이용하여 효율적으로 구현하여 암호회로의 면적을 최소화하며, 연산 과정에서 발생하는 중간값을 메모리 대신 내부 레지스터에 저장하여 사용함으로써 메모리 액세스 횟수를 최소화하여, 모듈러 연산을 고속화하는 것이다.
이상에서 설명한 본 발명은 전술한 실시예 및 첨부된 도면에 한정하는 것이 아니고, 본 발명의 기술적 사상을 벗어나지 않는 범위 내에서 여러 가지 치환, 변형 및 변경이 가능하다는 것이 명백할 것이다.
상술한 바와 같은 본 발명은 IC카드 시스템에서 사용자에게 보안성과 기밀성을 제공하는 RSA 암호 알고리즘을 수행하는 암호 연산을 적은 면적에서 고속으로 수행함으로써, IC카드의 보안성을 향상 시킬 수 있으며, IC카드뿐 아니라 암호 프로세서나 사용자 인증과 같은 적은 면적에서 암호 기능을 필요로 하는 시스템에 적용되어 사용 될 수 있다.

Claims (29)

  1. IC카드 시스템의 프로세서에 연동되는 RSA 암호 연산 장치에 있어서,
    모듈러 연산에 필요한 데이터를 각각 할당된 영역에 저장하고, 모듈러 연산이 수행됨에 따라 제어 신호에 의해 순차적으로 연산에 필요한 데이터를 제공하며, 모듈러 연산의 결과값을 저장하는 메모리와,
    상기 IC카드 시스템의 프로세서에서 전송되는 제어 신호 및 암호 연산을 위한 데이터를 송수신하는 인터페이스부와,
    상기 프로세서로부터 상기 인터페이스부를 통해 전송되는 제어신호에 따라 암호 연산의 동작모드를 제어하기 정보를 저장하는 제어 레지스터와,
    상기 제어 레지스터에 저장된 정보에 따라 모듈러 곱셈 또는 모듈러 지수승 연산을 수행하기 위한 데이터를 상기 메모리로부터 미리 읽어 저장하는 입력 레지스터와,
    상기 입력 레지스터에 저장된 값을 읽어 내부 레지스터를 이용하여 암호 연산에 필요한 모듈러 곱셈 또는 모듈러 지수승 연산을 수행하는 모듈러부와,
    상기 모듈러부에 의해 연산된 결과값을 보정하는 감산부와,
    상기 IC카드 프로세서로부터 전송되는 제어신호를 상기 제어 레지스터에 저장하고, 그 제어신호에 따라 모듈러 연산 수행을 위해 상기 메모리로부터 데이터를 로드하여 상기 입력 레지스터를 통해 상기 모듈러부에 제공하여 모듈러 연산을 수행하기 위한 제어신호를 생성하는 제어부를 포함하는 IC카드용 RSA암호 연산 장치.
  2. 제 1 항에 있어서, 상기 메모리는,
    데이터의 입력과 출력을 위한 데이터 경로를 같이 사용하는 메모리외에 데이터의 입력과 출력을 따로 사용하는 메모리를 더 포함하는 IC카드용 RSA암호 연산 장치.
  3. 제 1 항에 있어서, 상기 제어 레지스터에 저장되는 정보는,
    암호 회로의 초기화를 위한 reset 신호,
    암호 회로의 연산 시작을 지시하는 start 신호,
    암호 회로에서 수행할 동작이 모듈러 곱셈 연산인지 모듈러 지수승 연산인지를 결정하는 모드 선택신호,
    암호 회로의 동작이 모듈러 지수승 연산인 경우, 암호화 연산인지 복호화 연산인지를 결정하는 지수승 모드 선택 신호,
    암호 연산의 수행이 끝났음을 알려주는 end 신호중 적어도 하나를 포함하는 IC카드용 RSA암호 연산 장치.
  4. 제1항에 있어서, 상기 입력 레지스터는 32bit로 구성되는 IC카드용 RSA암호연산 장치.
  5. 제 1항에 있어서, 상기 입력 레지스터는,
    데이터를 위해 메모리에서 입력 받는 것 외에 특정 주소가 가해지는 경우, 상기 인터페이스부로부터 직접 데이터를 입력 받는 IC카드용 RSA암호 연산 장치.
  6. 제 1 항에 있어서, 모듈러부는,
    곱셈연산을 위한 입력 데이터를 선택하는 제 1 데이터 선택부와,
    상기 제 1 데이터 선택부에 의해 입력된 데이터에 대한 반복 연산을 수행하는 곱셈부와,
    덧셈 연산을 위한 입력 데이터를 선택하는 제 2 데이터 선택부와,
    상기 제 2 데이터 선택부에 의해 입력된 데이터에 대한 덧셈 연산을 수행하는 덧셈부와,
    상기 곱셈부 또는 덧셈부의 연산에 의한 중간값을 저장하는 중간값 저장 레지스터와,
    상기 중간값 저장 레지스터의 데이터 저장 경로를 설정하는 제3데이터 선택부를 포함하는 IC카드용 RSA암호 연산 장치.
  7. 제 6 항에 있어서, 상기 제 1, 2, 3데이터 선택부는,
    데이터의 선택적 설정이 가능한 다중화기 또는 역 다중화기를 포함하는 IC카드용 RSA암호 연산 장치.
  8. 제 6항에 있어서, 상기 제1, 2, 3데이터 선택부는,
    곱셈과 덧셈 연산을 위해 데이터를 순차적으로 선택하는 IC카드용 RSA암호 연산 장치.
  9. 제 6 항에 있어서, 상기 곱셈부는, 곱셈과 덧셈 연산을 동시에 1클럭에 수행하는 IC카드용 RSA암호 연산 장치.
  10. 제 6 항에 있어서, 상기 곱셈부는, 32bit 데이터를 8bit 또는 16bit 단위로 나누어서 반복 연산을 수행하는 IC카드용 RSA암호 연산 장치.
  11. 제 6 항에 있어서, 상기 곱셈부는,
    32bit 데이터의 곱셈을 수행하기 위하여, 8bit 또는 16bit 단위로 나누어서 반복 연산을 수행하기 위한 경로 설정부를 그 내부에 포함하는 IC카드용 RSA암호 연산 장치.
  12. 제 6 항에 있어서, 상기 중간값 저장 레지스터는, 순차적으로 배열된 32bit 레지스터를 포함하는 IC카드용 RSA암호 연산 장치.
  13. 제 6항에 있어서, 상기 중간값 저장 레지스터에서,
    최상위 워드 또는 비트 값은 결과값 보정을 위해 판단 값으로 사용되는 IC카드용 RSA암호 연산 장치.
  14. 제 6항에 있어서, 상기 중간값 저장 레지스터는,
    그 길이가 모듈러 곱셈 연산을 수행하는 모듈러 값보다 1워드 또는 1bit 더 큰 크기를 갖는 IC카드용 RSA암호 연산 장치.
  15. 제 1 항에 있어서, 상기 모듈러부는,
    모듈러 지수승 연산을 수행하기 위해, 아래 수학식의 지수 값 e = (et…e1e0)2의 최상위 1의 bit 자릿수 t를 찾는 탐색부를 포함하는 IC카드용 RSA암호 연산 장치.
    (몽고메리 지수승 알고리즘)
    입력 : m = (mn-1…m1m0)r, xp = xR mod m, A = R mod m, e = (et…e1e0)2.
    출력 : xemod m
    1. t에서부터 0까지 다음을 반복 :
    2. A = Mont(A, A).
    3. 만일 ei= 1이면 A = Mont(A, xp).
    4. A = Mont(A, 1).
  16. 제 1항에 있어서, 상기 모듈러부는,
    모듈러 지수승 연산을 수행하기 위해, 아래 수학식의 Mont(A, A)와 같이, 동일 데이터의 곱셈 연산을 위한 제곱 연산부를 더 포함하는 IC카드용 RSA암호 연산 장치.
    (몽고메리 지수승 알고리즘)
    입력 : m = (mn-1…m1m0)r, xp = xR mod m, A = R mod m, e = (et…e1e0)2.
    출력 : xemod m
    1. t에서부터 0까지 다음을 반복 :
    2. A = Mont(A, A).
    3. 만일 ei= 1이면 A = Mont(A, xp).
    4. A = Mont(A, 1).
  17. 제 1항에 있어서, 상기 모듈러부는,
    모듈러 지수승 연산을 수행하기 위해, 지수 값의 자릿수를 외부로부터 입력 받아서 연산을 수행하는 IC카드용 RSA암호 연산 장치.
  18. 제 1항에 있어서, 상기 모듈러부는,
    모듈러 연산을 수행함에 있어, 몽고메리 잉여류 수 체계로 변환하기 위하여, 모듈러 곱셈 연산을 먼저 수행한 후, 다시 그 값을 입력 값으로 사용하는 IC카드용 RSA암호 연산 장치.
  19. 제 1항에 있어서, 상기 모듈러부는,
    모듈러 연산을 수행함에 있어, 몽고메리 잉여류 수 체계로 변환되어진 값을 입력으로 받아서 연산을 수행하는 IC카드용 RSA암호 연산 장치.
  20. 제 1항에 있어서, 상기 모듈러부에서, 모듈러 지수승 연산의 수행시, 메모리에서 지수승 값을 32bit씩 읽어올 때, 카운터 장치를 이용하여 일정한 연산 수행 횟수에 동기화 되어, 지수승 값을 로드하는 IC카드용 RSA암호 연산 장치.
  21. 제 1항에 있어서, 상기 모듈러부에서, 모듈러 지수승 연산을 수행함에 있어, 지수승 값을 상기 제어부에서 발생하는 제어신호에 의해서 입력 받는 IC카드용 RSA암호 연산 장치.
  22. 제 15항에 있어서, 상기 모듈러부에서, 지수 값e의 자릿수 t를 구하기 위해, 워드(32bit) 단위로 지수 값을 읽어서, 해당 워드의 값이 0인가 검사 후, 0이 아닌 워드에서 다시 0이 아닌 bit의 위치를 찾는 IC카드용 RSA암호 연산 장치.
  23. 제 15항에 있어서, 상기 모듈러부에서, 지수 값e의 자릿수 t를 구하기 위해, 워드 단위로 지수 값을 읽어서, 해당 워드의 최상위 bit부터 하위 bit로 각 bit의 값이 1인지 검사하여 위치를 찾는 IC카드용 RSA암호 연산 장치.
  24. 제 1 항에 있어서, 상기 모듈러는,
    모듈러 지수승 연산을 수행함에 있어서, 아래 수학식에서 Mont(A, 1)를 수행하는 경우, 피승수 1의 값을 프로세서가 메모리에 설정하여 구동하는 IC카드용 RSA암호 연산 장치.
    (몽고메리 지수승 알고리즘)
    입력 : m = (mn-1…m1m0)r, xp = xR mod m, A = R mod m, e = (et…e1e0)2.
    출력 : xemod m
    1. t에서부터 0까지 다음을 반복 :
    2. A = Mont(A, A).
    3. 만일 ei= 1이면 A = Mont(A, xp).
    4. A = Mont(A, 1).
  25. 제 1항에 있어서,
    모듈러 지수승 연산을 수행함에 있어 아래 수학식에서 Mont(A, 1)를 수행하는 경우, 피승수 1의 값을, 곱셈을 수행하는 반복과정에서, 레지스터Rb의 값을 초기에 1로 설정하고, 나머지 연산 과정에서 레지스터Rb 값을 0으로 설정하는 IC카드용 RSA암호 연산 장치.
    (몽고메리 지수승 알고리즘)
    입력 : m = (mn-1…m1m0)r, xp = xR mod m, A = R mod m, e = (et…e1e0)2.
    출력 : xemod m
    1. t에서부터 0까지 다음을 반복 :
    2. A = Mont(A, A).
    3. 만일 ei= 1이면 A = Mont(A, xp).
    4. A = Mont(A, 1).
  26. 제 1항에 있어서, 상기 감산부는,
    모듈러 연산의 결과값에 대해 보정을 위해 상기 모듈러부의 출력으로부터 모듈러M값을 뺄셈 연산을 수행하는 뺄셈부와,
    상기 뺄셈부의 연산결과에 대하여 상기 제어부의 제어신호에 따라 상기 메모리에 저장될 데이터의 경로를 설정하는 출력선택부를 포함하는 IC카드용 RSA암호 연산 장치.
  27. 제 26항에 있어서, 상기 뺄셈부는,
    상기 모듈러에 중간값으로 저장된 데이터와 상기 메모리에 저장된 모듈러 값을 그 입력으로 하며, 하위 워드에서 상위 워드로 32bit씩 순차적 뺄셈 연산을 수행하는 IC카드용 RSA암호 연산 장치.
  28. 제 1항에 있어서, 상기 제어부에서 생성하는 제어신호는,
    모듈러 연산의 수행을 위해 상기 IC카드의 프로세서로부터 전송되는 제어신호를 상기 제어 레지스터에 저장하거나, 모듈러 곱셈 연산이 종료되었음을 알리기 위한 레지스터 제어신호와,
    상기 메모리로부터 모듈러 연산에 필요한 데이터를 순차적으로 읽어 들이거나, 모듈러 연산이 수행된 후 결과값을 저장하기 위한 메모리 제어신호와,
    상기 메모리로부터 모듈러부로 입력되는 데이터들을 상기 입력 레지스터에 선택적으로 저장하기 위한 입력 레지스터 제어신호와,
    상기 입력 레지스터에 순차적으로 저장되는 데이터들을 이용하여 모듈러 연산을 수행하는 과정에 필요한 모듈러 제어신호를 포함하는 IC카드용 RSA암호 연산 장치.
  29. 제 1항에 있어서, 상기 제어부는,
    모듈러 연산의 결과값을 보정하기 위하여, 상기 감산부의 뺄셈 연산에서 발생하는 자리 빌림 신호에 따라 상기 모듈러 연산결과를 상기 메모리에 저장하기 위한 주소를 설정하는 IC카드용 RSA암호 연산 장치.
KR10-2001-0081717A 2001-12-20 2001-12-20 아이씨카드용 알에스에이 암호 연산 장치 Expired - Fee Related KR100436814B1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
KR10-2001-0081717A KR100436814B1 (ko) 2001-12-20 2001-12-20 아이씨카드용 알에스에이 암호 연산 장치
US10/318,034 US7197141B2 (en) 2001-12-20 2002-12-13 RSA cryptographic processing apparatus for IC card

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR10-2001-0081717A KR100436814B1 (ko) 2001-12-20 2001-12-20 아이씨카드용 알에스에이 암호 연산 장치

Publications (2)

Publication Number Publication Date
KR20030051992A KR20030051992A (ko) 2003-06-26
KR100436814B1 true KR100436814B1 (ko) 2004-06-23

Family

ID=19717300

Family Applications (1)

Application Number Title Priority Date Filing Date
KR10-2001-0081717A Expired - Fee Related KR100436814B1 (ko) 2001-12-20 2001-12-20 아이씨카드용 알에스에이 암호 연산 장치

Country Status (2)

Country Link
US (1) US7197141B2 (ko)
KR (1) KR100436814B1 (ko)

Families Citing this family (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005141160A (ja) * 2003-11-10 2005-06-02 Japan Science & Technology Agency セキュア・プロセッサ
US7636858B2 (en) * 2003-12-11 2009-12-22 Intel Corporation Management of a trusted cryptographic processor
US20050132226A1 (en) * 2003-12-11 2005-06-16 David Wheeler Trusted mobile platform architecture
US20050132186A1 (en) * 2003-12-11 2005-06-16 Khan Moinul H. Method and apparatus for a trust processor
KR100652376B1 (ko) * 2004-07-29 2006-12-01 삼성전자주식회사 분리 연산 가능한 구조를 가지는 모듈러 곱셈기와 이를포함하는 암호화 시스템
JP2009515449A (ja) * 2005-11-04 2009-04-09 ジェムプリュス 組み込みシステム上での暗号アルゴリズム実行中にデータを安全に処理するための方法
KR100808953B1 (ko) * 2006-05-22 2008-03-04 삼성전자주식회사 모듈러곱셈 방법 및 상기 곱셈방법을 수행할 수 있는스마트카드
FR2917197B1 (fr) * 2007-06-07 2009-11-06 Thales Sa Procede de masquage du resultat d'une operation de multiplication modulaire et dispositif associe.
JP5222534B2 (ja) * 2007-11-16 2013-06-26 株式会社エヌ・ティ・ティ・ドコモ 緊急情報配信システム、緊急情報配信方法、送信サーバ及び携帯端末
JP2010139544A (ja) * 2008-12-09 2010-06-24 Renesas Electronics Corp 剰余演算装置、及び剰余演算方法
EP2523385B1 (en) * 2011-05-05 2017-07-12 Proton World International N.V. Method and circuit for cryptographic operation
US9965632B2 (en) * 2014-12-22 2018-05-08 Capital One Services, Llc System and methods for secure firmware validation
EP3543892B1 (en) 2015-04-14 2021-05-26 Capital One Services, LLC Systems and methods for secure firmware validation
US12143490B1 (en) * 2015-06-18 2024-11-12 Chorus Call, Inc. Method, software and apparatus for computing discrete logarithms modulo a prime
KR102006222B1 (ko) * 2018-01-05 2019-08-01 금오공과대학교 산학협력단 타원곡선 암호와 rsa 공개키 암호를 통합 구현하기 위한 연산장치 및 방법
FR3076925B1 (fr) 2018-01-16 2020-01-24 Proton World International N.V. Fonction cryptographique
KR102253211B1 (ko) * 2019-08-30 2021-05-17 금오공과대학교 산학협력단 소수체와 이진체 상의 타원곡선을 지원하는 공개키 암호 시스템의 하드웨어 구현을 위한 연산장치 및 방법
US11508263B2 (en) * 2020-06-24 2022-11-22 Western Digital Technologies, Inc. Low complexity conversion to Montgomery domain
CN116647318A (zh) 2022-02-16 2023-08-25 瑞昱半导体股份有限公司 防御密码系统时间攻击的方法及密码系统处理电路
CN115756391B (zh) * 2022-11-25 2025-10-17 杭州电子科技大学 用于实现非对称算法rsa模幂计算的硬件电路及方法

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4870681A (en) * 1986-03-05 1989-09-26 Holger Sedlak Cryptographic method and cryptographic processor for carrying out the method
US5261001A (en) * 1991-03-04 1993-11-09 Fortress U&T (2000) Ltd Microcircuit for the implementation of RSA algorithm and ordinary and modular arithmetic, in particular exponentiation, with large operands
KR19990064878A (ko) * 1999-05-18 1999-08-05 최돈익 고속의 모듈라 멱승 연산기
US6085210A (en) * 1998-01-22 2000-07-04 Philips Semiconductor, Inc. High-speed modular exponentiator and multiplier
KR20030004925A (ko) * 2001-07-07 2003-01-15 최준림 모듈라 지수승 연산 방식을 이용한 ｒｓａ 암호 장치

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CA2008774C (en) * 1989-01-30 1999-10-05 Hikaru Morita Modular multiplication method and the system for processing data
US5144574A (en) * 1989-01-30 1992-09-01 Nippon Telegraph And Telephone Corporation Modular multiplication method and the system for processing data
EP0656709B1 (en) * 1993-11-30 2005-07-13 Canon Kabushiki Kaisha Encryption device and apparatus for encryption/decryption based on the Montgomery method using efficient modular multiplication
EP0890147B1 (en) * 1996-10-31 2004-02-25 Atmel Research Co-processor for performing modular multiplication
DE69828150T2 (de) * 1998-03-30 2005-12-15 Rainbow Technologies Inc., Irvine Vom Rechenaufwand her effizientes modulares Multiplikationsverfahren und Gerät
US6356636B1 (en) * 1998-07-22 2002-03-12 Motorola, Inc. Circuit and method for fast modular multiplication
US6397241B1 (en) * 1998-12-18 2002-05-28 Motorola, Inc. Multiplier cell and method of computing
US6922717B2 (en) * 2001-09-28 2005-07-26 Intel Corporation Method and apparatus for performing modular multiplication

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4870681A (en) * 1986-03-05 1989-09-26 Holger Sedlak Cryptographic method and cryptographic processor for carrying out the method
US5261001A (en) * 1991-03-04 1993-11-09 Fortress U&T (2000) Ltd Microcircuit for the implementation of RSA algorithm and ordinary and modular arithmetic, in particular exponentiation, with large operands
US6085210A (en) * 1998-01-22 2000-07-04 Philips Semiconductor, Inc. High-speed modular exponentiator and multiplier
KR19990064878A (ko) * 1999-05-18 1999-08-05 최돈익 고속의 모듈라 멱승 연산기
KR20030004925A (ko) * 2001-07-07 2003-01-15 최준림 모듈라 지수승 연산 방식을 이용한 ｒｓａ 암호 장치

Also Published As

Publication number Publication date
US7197141B2 (en) 2007-03-27
US20030120944A1 (en) 2003-06-26
KR20030051992A (ko) 2003-06-26

Similar Documents

Publication Publication Date Title
KR100436814B1 (ko) 아이씨카드용 알에스에이 암호 연산 장치
US6434585B2 (en) Computationally efficient modular multiplication method and apparatus
US6182104B1 (en) Circuit and method of modulo multiplication
US5742530A (en) Compact microelectronic device for performing modular multiplication and exponentiation over large numbers
CN101540672B (zh) 数据处理系统以及数据处理方法
US6356636B1 (en) Circuit and method for fast modular multiplication
US5414772A (en) System for improving the digital signature algorithm
US6085210A (en) High-speed modular exponentiator and multiplier
EP0872795A1 (en) High speed modular exponentiator
JPS61223876A (ja) 暗号装置と累乗方法
EP1068565B1 (en) Acceleration and security enhancements for elliptic curve and rsa coprocessors
CN108108614A (zh) 安全处理器以及安全处理器的操作方法
EP0938790A2 (en) A method and device for executing a decrypting mechanism through calculating a standardized modular exponentiation for thwarting timing attacks
EP1818810B1 (en) Circuit and method for multiplying long integer values
US12231530B2 (en) Method for performing power disturbing operation to reduce success rate of cryptosystem power analysis attack, cryptosystem processing circuit, and electronic device
KR100449491B1 (ko) 모듈러 곱셈 장치
KR100564599B1 (ko) 역원 계산 회로, 역원계산 방법 및 상기 역원계산 방법을실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수있는 기록매체
Nedjah et al. Four hardware implementations for the m-ary modular exponentiation
JP2003216411A (ja) 多倍長演算処理装置およびｉｃデバイス
JP5179933B2 (ja) データ処理装置
JP2000214777A (ja) 巾乗剰余演算を行う演算装置
KR100399048B1 (ko) 타원곡선 암호화 장치
WO2018088958A1 (en) System and method for performing cryptographic operations
JP2002175178A (ja) 除算方法，除算回路，乗除算回路
Großschädl A new serial/parallel architecture for a low power modular multiplier

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

St.27 status event code: A-0-1-A10-A12-nap-PA0109

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

PN2301 Change of applicant

St.27 status event code: A-3-3-R10-R13-asn-PN2301

St.27 status event code: A-3-3-R10-R11-asn-PN2301

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

D13-X000 Search requested

St.27 status event code: A-1-2-D10-D13-srh-X000

D14-X000 Search report completed

St.27 status event code: A-1-2-D10-D14-srh-X000

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U11-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 5

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 6

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R13-asn-PN2301

St.27 status event code: A-5-5-R10-R11-asn-PN2301

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 7

FPAY Annual fee payment

Payment date: 20110531

Year of fee payment: 8

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 8

LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20120611

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20120611

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R13-asn-PN2301

St.27 status event code: A-5-5-R10-R11-asn-PN2301