[암호학] 대칭키 암호 - DES(Data Encryption Standard)

---

[암호학] 대칭키 암호 - DES(Data Encryption Standard)

---

데이터 암호화 표준

DES(Data Encryption standard)

1. 개요

• DES는 대칭형 암호(비밀키 암호)이다. 즉, 암호화 및 복호화 키가 동일하다.
• 비대칭형 암호에 비해 암호 및 복호 속도가 빠르다.

DES 암호 방식

• 미국 정부의 상무부 표준국(NBS:현재는 NIST로 개편됨)이 1977년에 IBM사의 제안을 바탕으로 제정한 데이터 암호화 표준 규격이다. 
• 데이터 암호화 표준(DES)은 64비트 평문을 64비트 암호문으로 암호화하는 대칭키 암호 알고리즘이다.
• DES의 키는 7비트마다 오류검출을 위한 정보가 1비트씩 들어가기 때문에 실질적으로는 56비트이다.
• DES 구조는 Feistel 네트워크의 변형된 형태이다. 라운드 횟수는 16이다. 56비트짜리 원래 키로부터 16개의 서브키를 생성하고 그 서브키를 각 라운드에서 사용한다.
• DES의 가장 좋은 암호 분석 방법은 모든 키를 다 적용하는 전수조사공격 방법이다.
• 최근 반도체 칩 기술의 발달로 64비트 암호 키에 의한 DES 암호는 쉽게 해독 가능하다.
• 암호학자들은 56비트의 암호키 길이를 112비트로 늘려서 암호하는 2중 DES, 3중 DES 사용을 권고하고 있다.

 

2. DES의 구조

• 암호화 과정은 두 개의 전치(P-박스)와 16개의 Feistel 라운드 함수로 구성된다.
• 라운드는 초기전치 박스의 출력 값 또는 이전 라운드 함수의 출력 값 L(i-1)과 R(i-1)을 입력 받아 다음 라운드의 입력 값 L(i) 와 R(i)를 생성한다.
• DES 알로기즘은 16개의 라운드 함수로 구성된다.

DES 암호화 과정

• 각 라운드는 암호 혼합기(Mixer)와 스와퍼(Swapper)로 구성된다.

DES 구조, 라운드 함수

• 16개의 라운드 함수 중에 사용된 두 개의 P-박스 중 하나는 초기 전치, 다른 하나는 최종 전치라고 한다. 
• 초기 전치박스와 최종 전치박스는 서로 역의 관계에 있는 단순 P-박스이다. 최종 전치는 DES에 있어서 암호학적으로 중요하지 않다.

DES, 초기 전치박스와 최종 전치박스는 역관계이다

• 각 라운드는 라운드 키 생성기에 의해 암호키로부터 생성된 48비트 라운드 키를 사용한다.

 

3. DES 함수

• DES 함수란 라운드 함수에 사용된 아래 함수를 가리킨다.

DES 함수

• DES 함수는 32비트 출력 값을 산출하기 위하여 가장 오른쪽의 32비트 R(i-1)에 48비트 라운드키를 적용한다.
• DES 함수는 확장 P-박스, 키 XOR, 8개의 S-박스 그리고 단순 P-박스의 4개 부분으로 구성되어 있다.

DES 함수

4. 확장 P-박스

• R(i-1) 32비트에고 K(i) 는 48비트 이므로, R(i-1) 32비트를 48비트로 확장 시켜서 전치한다.
• 각 4비트 값이 6비트 값으로 확장되는데, 입력 비트 1, 2, 3, 4는 출력 비트 2, 3, 4, 5로 되고, 출력 비트 1은 이전 입력 값의 4번째 비트로부터 나오고, 출력 비트 6은 다음 입력 값의 1번째 비트로부터 나온다.

확장 전치

5. S-박스

• S-박스는 평문의 입력 비트를 치환시킨다.
• DES는 각각 6비트 입력 값과 4비트 출력 값을 갖는 8개의 S-박스를 사용한다.
• S-박스의 6비트의 입력 값 중 1과 6은 행을 결정하고, 2~5까지는 열을 결정한다.

DES, S-박스

• S-박스 1 테이블

S-박스 1 테이블

 

6. 처리과정

DES 암호화 처리 과정

• 64비트의 평문을 초기전치(IP:l Initial Permutation) 테이블을 통하여 평문의 문자를 재배열한다.
• 실선 상자 안의 과정이 16회(round) 반복한다.

① 초기전치를 통하여 64비트가 32비트의 L0, R0 로 분할된다.

② i = 1,2,3 .... 16 까지 아래의 연산을 수행한다.

③ 함수 f는 P-박스에 의한 전치(Permutation)와 S-Box에 의한 치환(substitution)을 처리한다(확산과 혼돈 구현)

④ 16라운드의 결과인 L16, R16을 초기 전치 (IP)의 역전치인 IP(-1) 를 거쳐 64비트의 암호문(C)를 생성한다.

 

7. 세부 처리 과정

DES, 세부 처리 과정

① R(i-1) 입력 32비트는 E-Table의 확대전치(Expansion/Permutation) 과정을 거쳐 48비트로 확대됨

    ▶ E{R(i-1)}는 R(i-1)의 32비트 중 16비트는 2회씩 나타남 (1,4,5,8,9,12,13,16,17,20,21,24,25,28,29,32번째의 비트는 2번씩 반복하여 나타남)

48비트 확대전치

② 확대전치 E-Table의 결과인 E{R(i-1)} 는 서브키 K(i)와 X-OR 된 이후 6비트씩 8개의 S-Box에 입력되된다.

③ S-BOX 처리 과정

DES, S-BOX 처리 과정

④ S-Box의 출력 결과인 32비트는 다시 P-table에 의한 전치(Transposition)/Permutation) 과정을 거쳐 f{R(i-1), K(i)} 결과가 됨

⑤ 이어서 아래 함수의 연산을 시작한다.

 

8. 라운드 키 생성과정

DES, 라운드 키 생성 과정

① f 함수 계산에 입력되는 라운크 키 K(i)는 64비트 암호키 K에 의해 생성된다.

• 암호 키 K는 길이가 64비트이나 8번째 비트(8, 16, 24, 32, 40, 48, 56, 64 비트)마다 패리티 비트로 활용된다.
• 암호 키 K에서 실제 암호에 사용되는 길이는 56비트 이다.

② 암호키 56 비트를 PC-1(Permuted Choice1-) 테이블에 따라 전치한 후, 28비트의 길이로 C(0), D(0) 구분한다.

③ C(i), D(i)는 각각 Left shift(s) 테이블에 의해 왼쪽으로 시프트 된 후, PC-2 테이블에 따라 56비트가 48비트로 축소된다.

 

9. DES의 특징

• 64비트 블록 암호 알고리즘이다.
• 키의 크기는 64비트(56비트의 비밀키 + 8비트의 parity 비트)이다.
• 안전성은 주로 비선형 함수로 구성된 8개의 S-Box에 의존한다.
• 16라운드의 페이스텔(Feistel) 구조이다.
• 복호화는 암호화의 역순이다.

 

10. DES의 취약점

• DES는 평문 또는 키의 작은 변화가 암호문에 큰 변화를 만드는 쇄도효과가 매우 크고, 암호문의 각 비트가 평문의 많은 비트들에 의존하는 완비성이 높은 것으로 증명되어 암호문으로부터 평문을 추론하기가 매우 어렵다.
• 그러나 DES는 56비트 키를 사용하므로 최대 키 공간의 크기는 2^56이 되고, 이 수는 DES 개발 당시에는 전사 공격을 감행할 수 없을 정도로 큰 수였지만 계싼 능력이 크게 발전한 현대에는 더 이상 전사 공격에 안전하지 못하다.
• 실제로 DES 키는 1998년 3일 만에 전사 공격에 의해 해독되었으며, 이후 컴퓨터 성능 발전으로 해독에 걸리는 시간이 점차 짧아져 지금은 중요 정보의 암호화에는 적용할 수 없는 상태가 되었다.

 

11. 대칭키(비밀키) 문제점

(1) 키 관리 문제

• A 사람이 B와 C사람과 비밀키 암호통신을 할 경우, 사용하는 비밀키는 각각 달라야 한다. (Kab, Kac)
• n사람이 암호화 통신할 경우 필요한 키 개수는? n*(n-1)/2

(2) 키 분배 문제

• 송신자가 암호화 할 때 사용한 키를 수신자에게 안전하게 전달하는 방법이 필요하다 ☞ 공개키 암호 사용