4. 블록 암호 : DES

 

저번 시간에는 현대 암호에 대하여 공부하였다. 

이번시간에는 블록암호인 DES에 대하여 공부할 것이다.

 

---

1. DES

DES는 미국의 국가 안보국에서 IBM의 루시퍼 알고리즘을 개량하여 만든 대칭키 암호이다. DES는 루시퍼와 달리 키 길이를 56비트로 줄였고, 내부에서 사용하는 알고리즘도 변경하였다. 하지만 현대에는 DES에 대한 공격 기법이 많이 연구되어 더이상 블록 암호 표준으로 사용하지 않는다. 

DES는 8바이트(64비트)를 한 블록으로 암호화하는 블록 암호이다. 전체 구조는 초기 순열, 페이스텔 구조의 16 라운드, 최종 순열 그리고 각 라운드에 사용되는 48비트의 키를 생성하는 키 생성 함수로 구성된다.

 

DES의 구조

 

1) 순열, 치환, 곱 암호

DES는 혼돈 성질을 만족하기 위해 치환, 확산 성질을 만족하기 위해 순열을 사용한다.

---

※혼돈과 확산은 현대 암호에서 공부하였다. 밑에 링크는 현대 암호 링크이다.

3. 현대 암호

---

치환과 순열은 단순한 연산이기 때문에 평문에 이들을 한 번 적용한다고 해서 암호학적 효과를 기대할 수 없다. 그러나 이들을 교차해서 반복 적용하면 혼돈과 확산의 성질을 모두 만족한다. 이런 특성으로 치환이나 순열 같은 연산들로 하나의 라운드로 구성하고, 각 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호를 곱 암호라고 한다.

DES는 여러 라운드에 걸쳐 치환과 순열을 반복하는 곱 암호의 일종이다.

 

2) 페이스텔 구조

DES에서 라운드 함수를 적용하는 전체 과정은 페이스텔 구조를 이루고 있다.

페이스텔 구조를 를 따르는 DES는

1. 입력으로 들어온 블록을 동일한 길이의 왼쪽 블록 L과 오른쪽 블록 R로 나눈다.
2. 각 라운드 마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력된다.
3. 왼쪽 블록은 오른쪽 블록에 라운드 함수 F를 적용한 결과와 xor 연산을 하고 다음 라운드의 오른쪽 블록으로 입력된다.

페이스텔 구조(출처 : 드림핵)

 

3) 페이스텔 암호의 특징

블록 암호는 평문을 복호화 할 수 있어야 하므로 일반적으로 암호화를 구성하는 각 함수들에 역함수가 존재한다. 그러나 페이스텔 구조를 사용하면 F가 복호화 과정에서 xor 연산으로 상쇄되므로 역함수가 존재하지 않아도 된다. 또한 암호화와 복호화의 구조가 동일하기 때문에 암호화에 사용한 라운드 키를 역순으로 입력하면 복호화가 된다.

오른쪽 블록은 다음 라운드의 왼쪽 블록으로 어떠한 처리 없이 입력되기 때문에 비페이스텔 암호와 같은 안전성을 갖기 위해 두배 정도 라운드를 사용해야 한다는 단점이 있다.

 

2. DES의 과정

DES는 위에서 말했듯이 1) 초기 순열, 2) 페이스텔 구조의 16 라운드, 3) 최종 순열 그리고 각 라운드에 사용되는 4) 48비트의 키를 생성하는 키 생성 함수로 구성된다.

1) 초기 순열

초기 순열은 DES가 시작할 때 수행한다. 초기 순열 테이블(IPT)을 이용하여 64비트 입력을 비트 단위로 전치한다. 

 

2) 라운드 함수

라운드 함수 F에는 오른쪽 블록만 입력되므로, 입력 길이는 32비트이다. 라운드 함수는 1. 확장 순열, 2. 라운드 키 결합(XOR), 3. 치환 테이블, 4. 고정 순열로 이루어져 있다.

1. 확장 순열(Expansion P-Box)
   입력을 비트 단위로 전치하는 동시에 전체 길이를 32비트에서 48비트로 확장한다. 32비트 입력값을 4비트씩 8개의 부분으로 나누고 테이블을 참조하여 각각 6비트로 확장한다. 
                                              
2. 라운드 키 결합(XOR)
   확장 순열로 나온 출력을 라운드 키와 xor 연산을 한다.       
                                                           
3. 치환 테이블(Substitution-Box)
   라운드 키 결합에서 출력된 48비트 결과 값을 32비트로 축소한다. S-Box는 4개의 행과 16개의 열로 이루어진 표이다. 표의 각 값은 4비트로 표현되는 수이다. 
   
   (1) 입력을 여섯 비트씩 8개로 나눈다. 여섯 비트로 자른 부분마다 다른  S-Box를 사용한다.
   (2) 여섯 비트 중 첫 번째와 마지막 비트로 행을 결정하고 나머지 네 개의 비트로 열을 결정한다.
   (3) S-Box의 표에서 행과 열을 참조하여 값을 반환한다.
   
   
4. 고정 순열(Straight P-Box)
   입력을 비트 단위로 전치가 이루어진다.

 

3) 최종 순열

최종 순열은 DES 마지막에 수행한다. 최종 순열 테이블(IPT)을 이용하여 64비트 입력을 비트 단위로 전치한다. 초기 순열과 최종 순열은  서로 역관계이다. 임의의 64비트 데이터에 초기 순열을 적용하고 최종 순열을 적용하면 입력 값이 그대로 출력된다. 

 

4) 키 생성 함수

키 생성 함수는 64비트(56비트 비밀키 + 8비트 패리티)의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수이다. 키 생성 함수는 1. 패리티 비트 제거, 2. 쉬프트, 3. 압축 순열로 구성된다.

1. 패리티 비트 제거
   입력에서 패리티 비트를 제거하고 남은 56비트에 순열을 적용하는 과정이다. DES의 비밀키에서 각 바이트의 가장 오른쪽 비트는 자신이 속한 바이트의 나머지 7비트에 대한 홀수 패리티 비트이다.
   
   홀수 패리티 비트 : 한바이트를 이진수로 표현했을 때, 1의 개수가 홀수가 되도록 덧붙인 비트를 말한다. 예를 들어, 1001101에는 1이 4개 즉 1의 개수가 짝수이므로 홀수 패리티 비트를 적용하면 맨 오른쪽에 비트 1을 덧붙인 10011011을 전송한다. 통신 중에 비트 반전이 일어나지 않았음을 보증하는 역할을 한다. 홀수 패리티 비트를 사용하여 통신하는데 1의 개수가 짝수인 바이트가 있으면 반전이 일어났다고 알 수 있다. 그러므로 수신자는 재전송을 요구할 수 있다.
   
   
2. 쉬프트
   입력을 왼쪽 28비트와 오른쪽 28비트로 나누어 각각을 1비트나 2비트 만큼 왼쪽으로 순환 쉬프트하는 과정이다. 1,2,9,16 라운드에서는 1비트, 나머지 라운드에서는 2비트만큼 쉬프트한다.
   
   
3. 압축 순열
   56비트의 입력을 48비트 길이로 압축하는 과정이다. 

 

3. 다중 DES

연산 능력이 증대되고 관련 공격 기법이 연구로 인해 DES는 더이상 안전한 암호 시스템이 아니다. 다중 DES는 서로 다른 키를 사용하여 DES모듈을 여러개 이어서 붙여 DES의 약점을 보완하였다. 두 겹이면 이중 DES으로 112비트 키를 사용하고, 세 겹이면 삼중 DES으로 168비트의 키를 사용한다. 

삼중 DES를 식으로 표현하면 E_k3(D_k2(E_k1(p))) = c이다. 삼중 DES에서 중간에 암호화가 아닌 복호화를 하는 이유는 k2 = k3로 설정하면, E_k3와 D_k2가 상쇄되어 키가 k1인 단일 DES로도 사용할 수 있기 때문이다. 이중 DES나 삼중 DES는 늘어난 키 길이 만큼 단일 DES보다 안전할 것 같지만, 중간 일치 공격으로 인해 안전성을 획기적으로 높이지는 못한다.

---

※ 중간 일치 공격에 대한 링크이다.

 

---

---

 

이번 시간은 블록 암호인 DES에 대하여 공부하였다.

다음 시간은 블록 암호 AES에 대하여 공부할 것이다.