[정보보안] DES Algorithm

중앙대학교 소프트웨어대학 김성권교수님의 "정보보호이론(Information Security Theory)" 과목을 듣는 과정에서 작성한 포스트입니다. 

 

DES는 Data Encryption Standard의 줄임말로, 현대 대칭키 블록 암호중 하나이다. 1973년 NIST 미국 표준 대칭키 암호 공모를 통해 탄생했으며, IBM의 Lucifer였는데 DES로 이름이 바뀌었다 .1975년 미국 표준이 되었고 현재는 표준은 아니지만 자주 사용된다. 

 

대칭키 암호(Symmetric key)란 암호문을 생성(암호화)할 때 사용하는 키와 암호문으로부터 평문을 복원할 때 사용하는 키가 동일한 암호 시스템이다. 

 

* confusion, diffusion이라는 성질을 만족시키기 위해 Feistel(피스텔)암호를 어떻게 사용했는지 보는것이 DES Algorithm을 공부하는 핵심이다. 

 

DES는 64비트의 평문을 가지고 64비트의 암호문을 생성한다. 이때 동일한 56비트의 암호키(cipher key)가 암호화, 복호화 과정에 모두 사용된다. 

 

DES의 과정은 2번의 두번의 순열(Permutation)(P-box라고 부른다)(initial, final)이랑, 16번의 Feistel 함수로 만들어진다.

 

 

 

block cipher, symeetric key cipher이다. 

 

 

한글이 2바이트(16비트), 영어가 한글자에 1바이트(8비트)임을 생각하면, 매우 작은 단위로 끊어서 암호화, 복호화 한다는걸 생각할 수 있다. 

 

1. initial and final permutations

 

초기 치환, 최종 치환은 테이블을 보고 이루어진다.  

 

 

1번째 자리에 58이라는 숫자가 들어가있다. 즉, 평문의 58번째에 있는 숫자를 암호문의 1번째 글자로 쓰라는 뜻이다. 

마찬가지로 평문의 50번째 있는 숫자는 암호문의 2번째로 사용된다. 

 

 

2. 16번의 Feistel cipher

 

오른쪽 그림의 과정을 16번 반복하게 된다. 64-bit의 input을 32bit씩 잘라서, 오른쪽 파트는 그대로 왼쪽으로 가고 왼쪽 파트는 F함수를 거쳐서 오른쪽으로 붙는다.  이 F함수(Mixer)가 DES의 핵심이다.

 

F함수 내부를 자세히 보면, Expansion P-box, XOR, S-Boxes, Straight P-box 이렇게 4개의 과정으로 구성되어 있다. 

 

 

 

1. expansion P-box

32bit를 48bit로 바꿔준다. 

 

 

2. XOR

말그대로 XOR...

 

 

3. S-Boxes

 

하나의 S-box 안은 이렇게 생겼다. 각 줄에는 0부터 15까지의 숫자가 섞여서 나열되어있다. 

 

 

참고로 S-box는 알고리즘을 설계한 사람이 만든거다. 우리 맘대로 바꿀 수 없다!! 설계된 테이블을 갖다 써야한다.  또, S-box를 설계한 사람은 설계 아이디어, 이유 등은 설명하지 않았다. 

 

   - 규칙 1. 입력된 6비트 중 1번째와 6번째 비트를 붙여서 십진수 로 나타내면 0부터 3까지의 수 중 하나가 되는데, 이 값으로 행 을 결정한다. 
   - 규칙 2. 나머지 2번째부터 5번째까지 4 비트를 붙여서 십진수로 나타내면 0부터 15까지의 수 중 하나가 되는데, 이 값으로 열을 결정한다.

 

4. Straight P-box

 

1~32의 숫자가 들어있는 p-box이다. 아까 permutation 했던 방식과 같이, 아까 얻은 string에서 16번째에 있던 글자를 첫번째 글자로 쓰고, 7번째 있던 글자를 2번째 글자로 쓰고..이런식으로 하면 된다. 

 

 

** Round16만 다른점 **

 

16번의 Feistel함수를 하면서, 마지막 16번째 라운드만 살짝 다른 방식을 취해준다.  mixer만 있고, swapper은 없다는 점이다.

 

 

16번 라운드만 swapper가 없다는걸 볼 수 있다. 

 

 

 

복호화하기

 

 

반대로 가면 된다...

그런데 이런 의문점이 들 수 있다. 중간에 mixer(f함수)에서 굉장히 복잡한 계산을 거쳤는데, 이거를 다시 mixer를 콜해준다고 기존 결과로 원복되는게 맞을까?

 

mixer의 성질은 self-invertible하다는 것이다. 즉, f함수를 두번 취해주면 원복 된다. 이를 증명해보자. 

 

 

이렇게 되어서 self-invertible임이 증명된다. 

 

3. Pseudo-code

실제 코드는 깃헙에도 매우 많으니까 생략

 

4. Round-Key Generator

56bit의 cypher key는 Round-key generator를 통해서 K1...K16의 48bit key를 만든다. 이 과정에 대해서 알아보자. 

cipher key에 대해서 parity bit를 더해서 64비트를 만들어주고, Parity drop을 하고, circular shift left하고, Compression P-box를 해서 키를 완성한다. 

 

1. Parity-bit drop table

 

2. circular shift left

Round마다 shift할 bit의 수가 다르다. 1, 2, 9, 16 round에서는 1비트만, 나머지 라운드에서는 2bit를 left shift 해주면 된다.

 

 

 

 

3. Key-Compression Table

 

 

 

특성

(1) avalanche effect

Plain Text에서 한글자만 달라져도, Cypher text에서는 여러 글자를 다르게 만든다. 

(2) completeness effect

한 글자가 여러 글자에 의해서 고르게 영향을 받았다. 

(3) confusion, diffusion

confusion: ciphertext, key의 관계 잘 숨김

diffusion: ciphertext, plaintext의 관계 잘 숨김

 

S-box와 P-box가 confusion과 diffusion을 잘 만족하고 있다. 

 

약점

1. key가 너무 작다!

key가 56bit여서, key의 경우의 수가 2^56밖에 되지 않는다. 

2. round key가 모두 같아서, cipher와 reverse cipher가 같아진다. 

cipher에 한번 더 cipher를 취해주면 원복되어 버린다.

3. key complement에 의해서 2^56 -> 2^55, 반밖에 안해봐도 된다.