KR100316025B1

KR100316025B1 - 데이터 암호 표준 알고리즘을 이용한 암호 및 복호 장치

Info

Publication number: KR100316025B1
Application number: KR1019990025795A
Authority: KR
Inventors: 윤주영
Original assignee: 박종섭; 주식회사 하이닉스반도체
Priority date: 1999-06-30
Filing date: 1999-06-30
Publication date: 2001-12-12
Anticipated expiration: 2019-06-30
Also published as: KR20010005012A

Abstract

본 발명은 암호 및 복호장치에 관한 것으로, 특히 데이터 암호 표준 알고리즘을 이용한 암호 및 복호장치에 관한 것이다. 그 장치는 카운팅값에 따라 키값을 발생하는 키 발생부, 64비트 입력 데이터를 입력받아 순열 연산하는 순열 연산부, 상기 순열 연산부의 연산 결과와 상기 키 발생부로부터의 키값을 배타 논리합 연산하는 제1배타 논리합 연산부, 상기 제1배타 논리합 연산부의 출력을 입력받아 치환 연산하는 치환부, 및 상기 순열 연산부 및 상기 치환부의 출력을 배타 논리합 연산하는 배타 논리합 연산부를 포함하는 것을 특징으로 하는 한다. 본 발명에 의하면, 연산 속도를 유지하면서도 칩 면적을 대폭 줄일 수 있다는 효과가 있다.

Description

데이터 암호 표준 알고리즘을 이용한 암호 및 복호 장치{Encryption and decryption device using data encryption standard algorithm}

본 발명은 암호 및 복호 장치에 관한 것으로, 특히 데이터 암호화 표준 알고리즘을 이용한 암호 및 복호 장치에 관한 것이다.

일반적으로 집적 회로 카드(Integrated circuit card) 분야에서는 사용자 인증(authentication)을 위해 고도의 복잡한 암호화(Encryption) 및 복호화(decryption) 알고리즘을 이용해야 하는데, 그중 하나가 데이터 암호 표준(Data Encryption Standard: 이하, DES라 칭함) 알고리즘이다. DES 알고리즘은 데이터와 키(key) 모두 64비트를 사용하여 16 라운드(round) 연산후, 64 비트의 암호화 데이터를 생성한다. 또한, 원래 하드웨어 구현에 적합하도록 비트 조작 및 서플링(shuffling) 동작이 대부분이고 16 라운드의 반복 연산을 수행하여 소프트웨어로 구현을 하였을 때에는 상당히 연산 시간이 길어지고 보통 5ms 정도의 연산 시간이 소요된다. 물론, 하드웨어적으로 구현한 경우에는 연산 시간이 짧아지는데 구현 면적이 커지게 된다. 일반적으로 전용 DES 칩은 면적에 대한 고려보다는 연산 시간을 줄이는데 초점을 맞추기 때문에 파이프라인(pipeline) 구조를 사용하여 연산 시간을 상당히 줄일 수 있다. 그리고 64비트 단위의 블록이 상당히 많은 연산을 필요로 하는 경우에는 암호화 블록 상호간에 데이터 암호화를 또 수행하게 되는데 보통 전자적 코드 북(electronic code book: ECB), 시퍼 블록 체이닝(cipher block chaining: CBC), 출력 피드백(out feedback: OFB), 시퍼 피드백(cipher feedback:CFB) 등이 사용된다. 그 중 ECD는 상용 소프트웨어 제품에 많이 사용되지만 외부 공격에 약해서 좀더 복잡하지만 보안에 강한 CBC를 많이 사용한다.

도 1은 종래의 DES 알고리즘을 이용한 암호화 장치를 설명하기 위한 도면으로, 도면 부호 1은 초기 순열(initial permutation)을, 10은 DES 알고리즘을 수행하는 기본 구조를 나타내며, L(i)은 i번째 64비트중 왼쪽 32비트를, R(i)은 i번째 64비트중 오른쪽 32비트를, Ki는 i번째 키를, 그리고 XOR는 배타논리합 게이트를 각각 나타낸 것이다.

먼저, 기본 구조(10)를 살펴보면, 왼쪽 32비트 L(0)(11)과 오른쪽 32비트 R(0)(12)에 대해서, R(0)(12)과 키(k1)(13)가 DES 연산부(14)에 입력되고 연산 처리된 후, 그 결과와 L(0)(11)이 배타논리합 연산부(15)에 의해 배타논리합 연산되어 출력된다. 이때, R(0)(12)은 다음 단의 왼쪽 32비트(L(1))가 된다. 이때, DES 연산부(14)는 DES 알고리즘을 수행하기 위한 확장 순열(expansion permuation), 키 생성(key generation), 치환(S-BOX subsitution), 그리고 순열(P-BOX permuation) 등의 연산을 수행한다.

기본 DES 알고리즘은 다음 과정을 통해 수행되며, 이를 상세히 설명하면 다음과 같다.

(1). 64 비트 입력(I64)중 오른쪽 32비트 R(i)은 다음 단의 왼쪽 32비트(L(i+1))가 된다.

(2). 오른쪽 32 비트(R(i))는 선택 과정을 거쳐 48비트 데이터가 된다.

(3). 64비트 키는 48비트 1~16까지의 n번째 보조 키를 생성하기 위해 사용된다. 이때, 48비트 보조 키는 (2) 과정을 통해 생성된 48비트와 배타논리합 연산을 통해 48비트의 결과를 얻는다.

(4). (2) 과정을 수행한 후의 48비트의 결과는 8개의 6비트 블록으로 나누어지며, 6비트중 4비트가 선택되어 32비트 출력이 얻어진다.

(5). (4)과정의 32비트 출력은 각 비트마다 위치를 새로이 변환한다.

(6). 32비트 블록은 입력의 왼쪽 32비트(L(i))와 배타 논리합 연산을 행한 결과가 다음 단의 오른쪽 32비트(L(i+1))가 된다.

상술한 과정을 통해 64비트의 결과를 얻게 되고, 이러한 과정을 총 16번 반복 수행된 후, 그 결과로서 왼쪽 32비트(L(16))(16)와 오른쪽 32비트(R(16))(17)를 얻게 되며, 이는 초기 순열(1)에 대한 역 순열(18)로서 출력된다.

이상에서 살펴본 바와 같이, 종래의 DES 알고리즘을 이용한 암호화 장치는 기본 구조(10)를 통해 연산을 총 16회에 걸쳐서 쉬프팅 및 키 처리 과정을 반복 수행하는 형태의 구조를 가진다. 따라서, 집적화시 칩 면적을 크게 차지하게 되고, 하드웨어 효율성이 떨어진다는 문제점이 있었다.

본 발명은 칩면적을 최소화할 수 있는 데이터 암호화 표준 알고리즘을 이용한 암호 및 복호장치를 제공하는데 그 목적이 있다.

도 1은 종래의 데이터 암호 표준 알고리즘을 이용한 암호 장치를 설명하기 위한 도면.

도 2a는 본 발명에 따른 데이터 암호 표준 알고리즘을 이용한 암호 및 복호장치를 설명하기 위한 도면.

도 2b는 도 2a에 도시된 암호 및 복호 장치의 동작을 설명하기 위한 신호 파형도.

도 3a는 도 2a에 도시된 치환부(50)를 설명하기 위한 상세 도면.

도 3b는 도 3a에 도시된 치환부의 동작을 설명하기 위한 신호 파형도.

* 도면의 주요 부분에 대한 설명

20 : 4비트 카운터 30 : 키 발생부

40 : 순열 연산부 50 : 치환부

60, 70 : 배타 논리합 연산부

상기 목적을 달성하기 위한 본 발명에 따른 데이터 암호화 표준 알고리즘을 이용한 암호 및 복호장치는 카운팅값에 따라 키값을 발생하는 키 발생부, 64비트 입력 데이터를 입력받아 순열 연산하는 순열 연산부, 상기 순열 연산부의 연산 결과와 상기 키 발생부로부터의 키값을 배타 논리합 연산하는 제1배타 논리합 연산부, 상기 제1배타 논리합 연산부의 출력을 입력받아 치환 연산하는 치환부, 및 상기 순열 연산부 및 상기 치환부의 출력을 배타 논리합 연산하는 배타 논리합 연산부를 포함하여 이루어진다.

이하, 첨부된 도면을 참조하여 본 발명을 상세히 설명하면 다음과 같다.

도 2A는 본 발명에 따른 DES 알고리즘을 이용한 암호 및 복호 장치를 설명하기 위한 도면으로, 도면 부호 20은 4비트 카운터를, 30은 키 발생부를, 40은 순열(P-BOX permutation) 연산부를, 50은 치환부(S-BOX substitution)를, 60 및 70은 배타 논리합 연산부를 각각 나타낸 것이다.

먼저, 4비트 카운터(20)는 enc 신호에 의해 증가되고, dec 신호에 의해 감소 카운팅 동작을 수행하며, reset 신호에 의해 리셋된다. 키 발생부(30)는 반복되는 다음 키값을 순차적으로 발생하는 부분으로, 카운터(20)의 카운팅값과, enc 및 dec 신호에 따라 키(key)값 혹은 피드백된 키값을 선택 출력하는 멀티플렉서(MUX)(32)와, 멀티플렉서(32)의 출력을 쉬프팅 시키는 쉬프트 레지스터(34)로 구성된다. 순열 연산부(40)는 순열(P-BOX permutation) 연산을 수행하는 부분으로, 두 개의 멀티플렉서(42, 44)와 레지스터(46)로 구성된다. 치환부(50)는 치환(S-BOX substitution) 연산을 수행하는 부분이다. 배타 논리합 연산부(60, 70)는 각각 배타 논리합 연산을 수행한다.

도 2B는 도 2A에 도시된 암호 및 복호 장치의 동작을 설명하기 위한 파형도를 도시한 것으로, 미설명된 clk는 클럭신호를, counter는 4비트 카운터의 카운트값을, key는 킷값을 각각 나타낸 것이다.

도 2A 및 도 2B를 참조하여 본 발명의 동작을 상세히 설명하면 다음과 같다.

DES 알고리즘의 암호화(encryption)와 복호화(decryption)의 차이는 키 쉬프트 방향과 횟수만 차이가 있다. 따라서, enc 및 dec 신호에 따라 암호화 또는 복호화 동작을 선택할 수 있게 된다. 키 발생부(30)는 카운터(20)의 카운팅 동작의 시작과 함께 다음 반복 연산을 위한 키값을 차례대로 발생한다. 키 발생부(30)의 키값과 순열 연산부(40)의 연산 결과는 배타 논리합 연산부(60)에 의해 배타 논리합 연산된 후, 치환부(50)에 입력된다. 순열 연산부(40)는 64 비트 입력 데이터(data)를 두 개의 멀티플렉서(42, 44)에 각각 32비트씩 입력되며, 멀티플렉서들(42, 44)의 출력은 레지스터(46)에 저장된 후, 배타 논리합 연산부(60, 70)에 각각 입력된다. 이때, 멀티플렉서(42)는 배타 논리합 연산부(70)의 출력을 다른 하나의 입력으로 하며, 멀티플렉서(42)는 레지스터(46)에 저장값을 다른 하나의 입력으로 받아들인다.

도 3A는 도 2A에 도시된 치환부(50)의 상세 도면으로, 도면 부호 52, 및 56은 멀티플렉서(MUX)를, 54는 롬(ROM)을, 58은 디멀티플렉서(DEMUX)를, 그리고 r_clk는 키값과 연산한 데이터를 다음 연산을 위한 데이터로 레치하기 위한 클럭신호를 각각 나타낸 것이다.

도 3B는 도 3A에 도시된 치환부(50)의 동작을 설명하기 위한 신호 파형도를 도시한 것으로, key는 키값을, data는 롬(54)의 출력을 나타낸 것이다.

도 3A 및 도 3B를 참조하여 치환부(50)를 상세히 설명하면 다음과 같다.

먼저, 입력 데이터(data_in)에 대하여 멀티플렉서(52)는 3비트 r_clk 신호에 따라 6비트를 선택 출력한다. 선택된 6비트중 1 비트는 멀티플렉서(56)의 선택신호(SEL)로서 이용되고 나머지 5비트는 3비트의 r_clk 신호와 함께 롬(54)의 어드레스로서 입력된다. 이때, 롬(54)은 치환 연산용 데이터를 저장하는 곳으로, 일반 조합 로직(combination logic)으로 구현하면 1 사이클 동작으로 가능하나, 칩면적을 크게 차지하게 된다. 따라서, 롬(54)으로 대체하게 되면 8 사이클 동작이 필요하게 된다. 롬(54)의 4비트 출력을 8번 연결시켜 최종 32비트 출력 데이터(data_out)를 얻을 수 있게 된다. 따라서, 연산 속도는 총 16회 연산에 16 사이클이 필요하므로 256 사이클이 소요된다. 만약, 5MHz의 클럭 주기라면 51.2us가 소요된다.

본 발명의 기술 사상은 상기 바람직한 실시예에 따라 구체적으로 기술되었으나, 상기한 실시예는 그 설명을 위한 것이며, 그 제한을 위한 것이 아님을 주의하여야 한다. 또한, 본 발명의 기술 분야의 통상의 전문가라면 본 발명의 기술 사상의 범위 내에서 다양한 실시예가 가능함을 이해할 수 있을 것이다.

상기와 같이 이루어지는 본 발명에 따른 DES 알고리즘을 이용한 암호 및 복호 장치는 연산 속도를 유지하면서도 반복 동작 하드웨어를 공유하고, 치환 연산을 롬으로 대체함으로써, 칩 면적을 대폭 줄일 수 있다.

Claims

카운팅값에 따라 키값을 발생하는 키 발생부;

64비트 입력 데이터를 입력받아 순열 연산하는 순열 연산부;

상기 순열 연산부의 연산 결과와 상기 키 발생부로부터의 키값을 배타 논리합 연산하는 제1배타 논리합 연산부;

상기 제1배타 논리합 연산부의 출력을 입력받아 치환 연산하는 치환부; 및

상기 순열 연산부 및 상기 치환부의 출력을 배타 논리합 연산하는 배타 논리합 연산부를 포함하는 것을 특징으로 하는 데이터 암호화 표준 알고리즘을 이용한 암호 및 복호 장치.
제1항에 있어서, 상기 키 발생부는 상기 카운팅값에 따라 제1 및 제2키값을 선택 출력하는 제1멀티플렉서; 및

상기 제1멀티플렉서의 출력을 쉬프팅하는 쉬프트 레지스터를 포함하는 것을 특징으로 하는 데이터 암호화 표준 알고리즘을 이용한 암호 및 복호장치.
제1항에 있어서, 상기 순열 연산부는 64비트 입력 데이터중 32비트와 상기 제2배타 논리합 연산부의 출력을 선택 출력하는 제2멀티플렉서;

상기 제2멀티플렉서의 출력을 저장하는 레지스터; 및

상기 64비트 입력 데이터중 다른 32비트와 상기 레지스터의 출력을 선택 출력하는 제3멀티플렉서를 포함하는 것을 특징으로 하는 데이터 암호화 표준 알고리즘을 이용한 암호 및 복호 장치
제1항에 있어서, 상기 치환부는 클럭신호에 따라 입력 데이터중 소정 비트를 선택 출력하는 제4멀티플렉서;

상기 제4멀티플렉서의 출력과 상기 클럭신호를 어드레스로서 입력받아 저장된 데이터를 출력하는 롬;

상기 제4멀티플렉서의 출력중 소정 비트에 따라 상기 롬의 출력중 소정 비트들을 선택 출력하는 제5멀티플렉서; 및

상기 제5멀티플렉서의 출력을 상기 클럭신호에 따라 디멀티플렉싱 동작을 수행하는 디멀티플렉서를 포함하는 것을 특징으로 하는 데이터 암호화 표준 알고리즘을 이용한 암호 및 복호장치.