암호학 5주차 - DES

0. 서론

DES(Data Encryption Standard)

: 미국의 국가 안보국에서 IBM의 루시퍼 알고리즘을 개량하여 만든 대칭키 암호

​

• DES는 키 길이를 56비트로 줄였고 내부에서 사용하는 알고리즘도 일부 변경했다.
• 현대에는 DES에 대한 공격 기법이 많이 연구되어 더 이상 블록 암호의 표준으로 사용하지 않는다.
• DES는 8바이트를 한 블록으로 하는 블록 암호이고 전체 구조는 초기 순열, 최종 순열, 페이스텔 구조의 16 라운드, 그리고 각 라운드에 사용되는 48비트의 키를 생성하는 키 생성 함수로 구성되어있다.

 

---

1. DES의 원리

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

치환과 순열을 여러 번 교차해서 반복 적용하면 혼돈과 확산의 성질을 모두 만족할 수 있다.

​

• 곱암호(Product Cipher)

: 치환이나 순열과 같은 단순 연산으로 한 라운드를 구성하고 각 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호

​

​

​

• 페이스텔(Feistel) 구조

- 특징

- 역함수가 존재하지 않아도 된다.

- 암호화에 사용한 라운드 키를 역순으로 입력하면 복호화가 이루어진다.

- 오른쪽 블록은 처리되지 않아 비페이스텔 암호화와 같은 안전성을 갖기 위해 라운드를 2배 정도 사용해야 한다.

 

- 페이스텔 구조를 따르는 과정

1. 입력으로 들어온 블록을 동일한 길이의 왼쪽 블록과 오른쪽 블록으로 나눈다.

2. 각 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력된다.

3. 왼쪽 블록은 오른쪽 블록에 라운드 함수 F를 적용한 결과와 xor 되어 다음 라운드의 오른쪽 블록으로

입력된다.

 

-> P=평문, K=라운드에서 생성된 키 라고 할 때

​

(1)L0 =P[:len(P)/2], R0 =P[len(P)/2:]

(2)Ln+1 =Rn

​(3)Rn+1=Ln⊕F(Rn,Kn)

​

---

2. DES의 과정

• 1&3번째 단계에서

DES 는 시작할 때 초기 순열(Initial Permutation, IP)을, 마지막에는 최종 순열(Final Permutation, FP)을

수행한다.

- 초기 순열과 최종 순열은 정해진 테이블을 이용해 64비트 입력을 비트 단위로 전치한다.

- 테이블의 n번째 값이 m일 때 출력의 n번째 비트는 입력의 m번째 비트가 된다.

- 초기 순열과 최종순열은 각각 초기 순열 테이블(IPT)과 최종 순열 테이블(FPT)을 이용한다.

- 초기 순열과 최종 순열은 역관계에 있다.

​

​

​

• 2번째 단계 개요

: 라운드 함수를 사용한다

- 라운드 함수 F에는 오른쪽 블록만 입력되므로 입력의 길이는 32비트이다.

- 라운드 함수는 확장 순열(Expansion P-Box), 라운드 키 결합 (XOR), 치환 테이블(S-Box), 고정 순열

(Straight P-Box)로 이루어져 있다.

 

 

• 2단계 구체적인 과정

1. 확장 순열과 라운드 키 결합

• 확장 순열은 입력을 비트 단위로 전치하고 전체 길이를 48비트로 확장한다.
• 32비트의 입력값을 4비트씩 8개의 부분으로 나누고 테이블을 참조하여 각각 6비트로 확장한다.
• 라운드 키 결합은 확장 순열로 나온 출력을 라운드 키와 xor 하는 것이며 초기 순열, 최종순열과 같은 방식이다.

 

 

​

2. S-Box와 고정 순열

• S-Box(Substitution-Box)는 라운드 키 결합에서 출력된 48비트 결과 값을 32비트로 축소한다.
• S-Box는 4행 16열로 이루어진 표를 사용하고 표의 각 값은 4비트로 표현되는 수
• S-Box 적용 과정

1. 입력을 6비트씩 8개의 부분으로 나눈다.

2. 여섯 비트 중 첫 번째와 마지막 비트로 행을 결정하고 나머지 네 개의 비트로 열을 결정한다.

3. S-Box표에서 행과 열을 참조하여 값을 반환한다. DES에서는 여섯 비트로 자른 부분마다 다른 S-Box를

사용한다.

4. S-Box로 길이를 축소하고 나면 고정 순열(Straight P-Box)로 다시 비트 단위 전치가 이루어진다.

​

• 키 생성 함수

키 생성 함수(key scheduling): 64비트의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수

- 패리티 비트 제거(Parity Bit Drop), 쉬프트(Shift), 압축 순열(Compression P-Box)로 구성되어 있다.

 

 

• 패리티 비트 제거(Parity Bit Drop)

: 입력에서 패리티 비트를 제거하고 남은 56비트에 순열을 적용하는 과정

DES의 비밀키에서 각 바이트의 가장 오른쪽 비트는 자신이 속한 바이트의 나머지 7비트에 대한 홀수 패리티 비트이다.

 

• 홀수 패리티 비트(Odd Parity Bit)

: 한 바이트를 이진수로 표현했을 때 1의 개수가 홀수가 되도록 덧붙인 비트

ex. 1010101 -> 10101011

​

- 특징

- 패리티 비트는 통신 중에 비트 반전이 일어나지 않았음을 보증한다.

- 홀수 패리티 비트를 사용해서 통신할 때 1의 개수가 짝수인 바이트가 있으면 반전이 일어났다는 것을

알 수 있고 수신자가 재전송을 요구할 수 있다.

​

​

• 쉬프트(Shift)

: 입력을 왼쪽 28비트와 오른쪽 28비트로 나누어 각각을 1비트나 2비트만큼 왼쪽으로

순환 쉬프트(Cyclic Shift)하는 과정

- 1, 2, 9, 16 라운드: 1비트 쉬프트 // 나머지 라운드는 2비트만큼 쉬프트

ex. 10101111 - 왼쪽 1비트 순환 쉬프트 -> 왼쪽 끝의 비트가 오른쪽 끝으로 이동해서 01011111

​

• 압축 순열(Compression P-Box)

: 56비트의 입력을 48비트의 길이로 압축하는 과정

​

---

3. DES의 응용

• 다중 DES

: 서로 다른 키를 사용하는 DES모듈을 여러 개 이어붙여서 DES의 약점을 보완한 암호 시스템

 

- 이중 DES: DES를 두 겹으로 사용, 112비트의 키 사용

- p를 평문, c를 암호문이라고 할 때

암호화: Ek2(Ek1(p))=c

​

- 삼중 DES: DES를 세 겹으로 사용, 168비트의 키 사용

- p를 평문, c를 암호문이라고 할 때

암호화: Ek3(Dk2(Ek1(p)))=c

- 중간에 복호화 하는 이유: k2=k3 설정 시 E_k3와 D_k2가 상쇄되어 키가 k1인 단일 DES로도

사용할 수 있기 때문이다.

- 중간 일치 공격(Meet-in-the-Middle-Attack)으로 안전성을 많이 높일 수 없다.

이중 DES는 단일 DES와 비슷한 안전성을 가지고 삼중 DES는 키 길이를 2배로 늘리는 효과만 얻는다.

​

​

• 중간 일치 공격

: 어떤 평문 p와 p를 암호화한 암호문 c를 알 수 있을 때 수행 가능한 공격

 

- 이중 DES에 대한 중간 일치 공격 방법

1. 56비트 키 공간 K에서 가능한 모든 키 k1으로 p를 암호화하여 집합 S1를 생성한다.

S1={Ek1(p)∣k1∈K}

​

2. K에서 가능한 모든 키 k2로 c를 복호화하여 집합 S2를 생성한다.

S2={Dk2(c)∣k2∈K}

​

3. S1의 모든 원소와 S2의 모든 원소에 대해 Ek1(p)=Dk2(c)를 만족하는 k1, k2의 쌍으로

후보키의 집합 CK를 생성한다.

CK={(k1,k2)∣Ek1(p)=Dk2(c),Ek1(p)∈S1,Dk2(c)∈S2}

​

4. 다른 평문 p′과 p′ 암호화한 암호문 c'을 생성한다.

​

5. CK의 모든 원소에 대해 Ek1(p′)=Dk2(c′)을 만족하는 k1과 k2의 쌍으로 집합 CK를 갱신한다.

CK={(k1,k2)∣Ek1(p′)=Dk2(c′),(k1,k2)∈CK}

 

6. CK의 원소가 하나가 될 때까지 4와 5의 과정을 반복한다.

​

​

• 이중 DES에 중간 일치 공격을 수행할 때 연산량에 영향을 미치는 것은 2^56번의 DES암복호화이다.
• 삼중 DES는 이 공격을 적용해도 112비트 키를 사용하는 DES 이상의 안전성을 가진다고 있어서 다중 DES 사용할 때는 일반적으로 삼중 DES를 사용한다.

​