[security] DES (Data Encryption Standard)

1. DES (Data Encryption Standard)의 탄생 

1960년대 말, 기업들이 파일을 보내는 안전한 방법들을 필요로 하기 시작했을 때, 암호계에 새로운 시대가 시작되었다. 컴퓨터 암호화 프로그램이 있다고 주장하는 많은 보안회사들이 있을지라도 세계 표준으로 승인된 암호화 방법(즉, 산업표준)이 없었다.

 

금융 기관들은 특히 신뢰할 수 있고 안전한 데이터 교환에 사용할 수 있는 표준 암호화 방법이 필요했다. 금융 기관들은 그들이 믿을 수 있는 어떤 사람들이 테스트한 암호화 방법이 필요했다.

 

US (National Security: 미국 국가 보안)는 안전한 암호에 의존하기 때문에, 미국정부 기관들은 암호를 항상 수반했다. 가령, 미국 국가 안전 기획부 (NSA: National Security Agency)는 그들의 전문적인 기술들을 공개한 적이 없었다. 비밀을 지키는 것이 NSA 에게는 항상 중요한 것이었다. 그러나 사기업들은 그 정보들의 필요로 인해 컴퓨터 암호화 방법을 공개하도록 NSA를 압박하기 시작했다.

 

마침내 1972년 국립 표준 기술 연구소 (NIST: National Institute of Standard and Technology)

는 안전한 암호화 방법 (암호화 알고리즘) 개발에 도움을 주기로 결정했다. 그 후 2년 뒤 1974년에 NIST는 IBM이 제시한 DES 개발에 착수했다. DES는 또한 DEA (Data Encryption Algorithm) 이라고도 불려진다.

 

2. DES의 특징 : 블록 암호화 와 대칭키 암호화 

 

DES의 특징

 

DES는 64비트 단위로 나뉘어 진 각각의 블록이 한번의 암호화 알고리즘을 거쳐 암호화 된다. 대칭알고리즘으로서 똑같은 키와 알고리즘이 암호화 복호화에 쓰인다. (복호화 할 때 키를 반대로 적용하는 등의 약간의 차이는 있다.)

 

키 길이는 64비트로 표현되는데, 이 중에서 실제로는 56비트만이 키로서 사용되고 나머지 8비트는 패리티 체크 비트로 사용된다. 암호화는 64비트 블록과 56비트 키를 바탕으로 만든 16개의  보조키가 총 16번의 혼돈 (confusion)과 확산 (diffusion)을 거쳐 완료된다. 

 

블록 암호화

 

블록 암호화는 크기가 고정된 블록을 위한 암호화 함수이다. 블록 암호화는 일정한 크기의 평문을 암호화해서 암호문을 만들어 내는데, 이 암호화 방법은 되돌리는 것이 가능한데, 일정한 암호문을 복호화하여 원래의 평문을 얻을 수 있다. 평문과 암호문은 항상 같은 크기를 가지는데, 이것을 블록 암호화의 블록 크기라 한다. 

 

대칭키 암호화 (비밀키 암호화)

 

대칭키 암호 알고리즘은 같은 키로 암호화, 복호화 하기 때문에, “대칭적 암호 알고리즘” 이라 언급된다. 평소에 특정한 비밀키를 가지는 두 사람이 있다면 그들은 같은 키를 공유한다. 다른 사람이 비밀키를 알아서는 안 된다. 대칭키 암호 알고리즘은 키를 가진 서로에게 기밀성, 인증, 무결성을 제공한다.  

 

3. DES 알고리즘의 분석

 

[Outline of the Algorithm]

 

① Initial Permutation을 실행한다.

② 64비트 블록을 왼쪽, 오른쪽 각각 32비트로 나눈다.

③ 데이터와 키를 조합하여 16 round의 동일한 연산을 반복실행 한다.

④ 왼쪽, 오른쪽으로 나누어진 블록을 하나로 합친다.

⑤ Final Permutation을 실행한다.

 

             Figure: Outline of DES

 

[One round of DES]

 

① 56비트 키 중에서 48비트를 선택한다. (Compression Permutation)

② 48비트 키를 왼쪽으로 정해진 만큼 시프트 한다. (실행 round 순서에 의존한다.)

③ 블록의 오른쪽 절반 (32비트)을 48비트로 확장한다. (Expansion Permutation)

④ 48비트 키와 48비트 블록의 오른쪽 절반을 XOR 한다.

⑤ S-Box Substitution을 실행 하여 32비트 결과 값을 얻는다.

⑥ P-Box Permutation을 실행 하여 32비트 결과 값을 얻는다.

⑦ P-Box를 통해 얻은 값 (32비트)과 블록의 왼쪽 절반 (32비트)를 XOR 한다.

⑧ 기존의 오른쪽 절반을 새로운 왼쪽 절반에 넣고 위의 과정을 반복한다.

 

     Figure: One round of DES

 

      Li = Ri-1

      Ri = Li-1 ⊕ f(Ri-1, ki)

 

Bi를 i번째 과정의 결과라 할 때 Li, Ri는 Bi 와 Ki의 왼쪽, 오른쪽 절반

f는 round 안에서의 블록과 키에 대한 Substitution, Permutation, XORing 연산이다.

 

[Initial Permutation]

 

암호화 알고리즘 처음과 끝에 수행되는 Initial Permutation과 이에 역인 Final Permutation은 실제적으로 데이터의 암호화에 별 도움이 되지 않는다. 개발당시 DES chip에서 데이터를 읽기 쉬운 단위로 묶기 위한 목적으로 구상되었으나 이후에 DES의 후속으로 개발되는 알고리즘에는 더 이상 사용되지 않는다.  

 

                      Table: Initial Permutation                             

58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,

62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,

57, 49, 41, 33, 25, 17,  9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 

61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7

 

[Key Transformation]

 

초기에 64비트인 DES 키는 56비트로 축소된다. 이때 나머지 8비트는 패리티 체크 비트로 사용되거나 무시된다. 56비트로 축소된 DES 키는 16 round의 연산에 쓰이는 16개의 48비트 sub key로 만들어진다.

 

처음 56비트 키는 절반인 28비트씩 왼쪽, 오른쪽으로 나뉘어 지고 이 두 개의 절반은 순환적으로 l 혹은 2씩 왼쪽으로 시프트 된다. 이 과정은 round에 따른 shift 회수를 정해놓은 table에 의해 결정된다. 키를 시프트 하는 이유는 16개의 round에서 사용할 sub key를 서로 다르게 하기 위해서 이다.

 

시프트 된 키는 Compression Permutation을 통해서 56비트에서 48비트로 축소된다. 

 

Table: Key Permutation

57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,

10,  2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,

63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,

14,  6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4

 

Table: Compression Permutation

14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,

23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,

41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,

44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32

 

Table: Number of Key Bits Shifted per Round

1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1

 

[Expansion Permutation]

 

이 과정에서는 블록의 오른쪽 절반 (32비트)을 48비트로 확장한다. 이 것은 두 가지 목적을 가지는데 첫 번째는 32비트인 블록을 48비트인 sub key의 사이즈에 맞추기 위해서 이고, 두 번째는 이어서 실행되는 S-Box Substitution에서 필요한 만큼의 길이를 맞추기 위해서 이다. 그림을 보면 4비트 입력 블록의 첫 번째, 네 번째 비트가 2개로 나뉘어 지면서 6비트의 출력 블록을 만드는 것을 볼 수 있다.

 

Table: Expansion Permutation

32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9,

8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,

16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,

24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1

 

[S-Box Substitution]

 

지난 과정에서 블록의 오른쪽 절반과 sub key와의 XOR 후 얻은 48비트 결과 값을 6비트의 보조 블록 8개로 나눈다. 이때 8개로 나뉘어 진 블록을 역시 8개로 분리된 S-Box에 넣어 4비트 결과 값을 얻게 된다. 이때 연산의 순서는 첫 번째 블록이 첫 번째 S-Box에, 두 번째 블록은 두 번째 S-Box에 들어가는 식이다. S-Box는 4개의 행과 16개의 열로 이루어져 있는데 각각에는 4비트 정수의 값 (0~15)이 저장되어 있다. 이 값들은 6비트 보조블록에 의해 지정되는 행과 열에 의해 결정된다.

 

6비트 보조블록을 각각 B1, B2, B3, B4, B5, B6 이라고 하면 B1과 B6이 합쳐서 2비트의 정수 값 (0~3)을 얻을 수 있는데 이 값은 S-Box에서 행을 결정하게 된다. 또한 나머지 4비트를 같은 방식으로 합치면 4비트의 정수 값 (0~15)를 얻을 수 있는데 이 값은 S-Box의 열을 결정한다.

예를 들어 6번째 보조 블록의 값이 110011(2)이라면 행은 11(2) 이므로 4행, 열은 1001(2) 이므로 10열이다. 이것을 S-Box table에서 찾아보면 6번째 Box, 4행, 10열의 값인 14 (1110(2)) 이다. 

 

S-Box 연산은 DES에서 가장 중요한 과정이다. 다른 연산과 비교했을 때 S-Box는 비선형구조에다 분석하기 어렵기 때문이다. 결과 값은 8개의 4비트 블록이다. 이것을 하나의 32비트 블록으로 합친 뒤, 다음 단계인 P-Box Permutation으로 넘어간다.

 

Table: S-Boxes Substitution

S-box 1:

14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,

0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,

4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,

15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6,13

 

S-box 2:

15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,

3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,

0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,

13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9

 

S-box 3:

10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,

13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,

13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,

1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12

 

S-box 4:

7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,

13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,

10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,

3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14

 

S-box 5:

2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,

14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,

4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,

11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3

 

S-box 6:

12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,

10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,

9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,

4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13

 

S-box 7:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,

13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,

1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,

6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12

 

S-box 8:

13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,

1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,

7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,

2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11

 

[P-Box Permutation]

 

S-Box Substitution의 결과 값인 32비트 블록을 P-Box Permutation을 통해 동일한 크기의 결과 값 (32비트)을 얻는다. 이번 연산에서는 무시되거나 두 번 사용되는 비트가 없다. 즉, 모든 입력은 하나의 출력을 가진다. 이 과정은 Straight Permutation이라고도 불린다.

 

P-Box의 결과 값은 초기에 나뉘어졌던 32비트 왼쪽 절반과 XOR 되어 새로운 오른쪽 절반이 되고, 기존의 오른쪽 절반은 새로운 왼쪽 절반이 되어 다음 round를 준비한다.

 

Table: P-Box Permutation

16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,

2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25

 

[Final Permutation]

 

모든 round를 거친 32비트 왼쪽 절반과 오른쪽 절반은 64비트 하나의 블록이 된다. 그러나 마지막 round에서는 오른쪽과 왼쪽의 절반은 서로 교환되지 않았다. 그 대신 Final Permutation을 거치게 된다. 이 연산은 Initial Permutation의 역 연산이다.

 

Table: Final Permutation

40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31,

38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,

36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27,

34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41,  9, 49, 17, 57, 25

 

[Decrypting of DES]

 

DES 알고리즘은 대칭 구조이기 때문에 복호화와 암호화를 같은 알고리즘으로 구현 할 수 있다. 단 복호화 알고리즘에서는 sub key를 암호화와 때의 역순으로 주어야 한다. 암호화 때의 sub key가 k1, k2, k3,...k16 이었다면 복호화 때의 sub key는 k16, k15, k14,...k1 순서 이어야 한다.

 

4. C를 이용한 DES 알고리즘 구현

 

프로그램 개요:

 

- 소스 파일을 열고 8바이트씩 읽어 암호화 한 뒤 새로운 파일에 저장한다.

- 암호화 된 파일을 열고 8바이트씩 읽어 복호화 한 뒤 새로운 파일에 저장한다.

- 암호화, 복호화에 사용되는 키는 8바이트에 해당되는 8개의 문자 혹은 숫자를 사용한다.

 

프로그램 요약:

 

- encrypt_data.h : 8바이트 데이터와 16개의 48비트 sub key를 입력받아 암호화 한다.

- decrypt_data.h : 8바이트 데이터와 16개의 48비트 sub key를 입력받아 복호화 한다.

- bit_operaion.h : 보조블록의 1,6비트 & 2,3,4,5비트를 합친 값을 구한다.

- des_table.h : 연산에 필요한 table을 배열로 저장한다.

- des_main.c : 사용할 8바이트 키를 입력받아 16개의 48비트 sub key를 생성하고, 암호화/복호화 할 파일과 새로운 파일을 열어 입/출력 한다.

 

실행결과

 

- 평문 파일을 암호화 한 결과 사이즈가 약간 늘어나는 현상을 발견하였다. 원본의 1085바이트에서 1088바이트로 3바이트가 늘어났는데 이것은 파일 입출력을 8바이트 씩 하기 때문에 발생한 결점이다. 평문의 사이즈는 1085바이트로 8바이트씩 데이터를 처리하면 135블록이 형성되고 나머지 1블록은 5바이트가 되는데 이것을 저장할 때 8바이트로 저장하기 때문에 암호화 한 파일은 3바이트가 늘어난 1088바이트로 저장되는 것이다. 

 

이 문제는 마지막 블록이 8바이트가 되지 않을 경우 16개의 round를 거치는 블록암호화가 아닌, 단일 암호화 방식으로 필요한 용량만을 암호화 하여 저장하는 방법을 사용하면 해결할 수 있을 것이다. 그러나 실제적으로 늘어나는 용량이 최대 7바이트 밖에 안 되므로 사용상 큰 문제는 없을 것으로 생각된다.

 

구분	파일명	사이즈(바이트)	비고
평문	source.txt	1085	한글 텍스트
암호화	encrypt.txt	1088	해독 불가능
복호화	decrypt.txt	1088	해독 가능