[암호] DES

DES 알고리즘이 뭔지 알기 전에 블록암호와 블록암호의 구조에 대해 생각하여 보자. 

블록암호는 주로 단순한 함수를 반복적으로 적용해서 암호학적으로 강한 함수를 만드는 과정으로 개발된다.

이때 반복되는 함수를 라운드 함수라고 하고, 라운드 함수에 적용되는 키는 라운드키라고 한다.

라운드키 자체도 독립적으로 생성하는 것이 좋지만, 여러가지 관리상 문제 등등으로 보통은 키(비밀키)를 기반으로

라운드키를 발생시켜 사용한다. 이러한 것을 키 스케줄이라고 한다.

블록암호는 라운드 함수를 적용하는 방법에 따라 

Feistel Cipher과 SPN(Substitution-Paermutataion Network)방식으로 나뉘어 진다.

DES는 Feistel 방식을 사용하고 AES는 SPN방식을 사용한다.

※ DES(Data Encryption Standard)

평문을 64비트로 나눠 56비트의 키를 이용해 다시 64비트의 암호문을 만들어 내는 알고리즘 (대칭형 블록암호)

DES의 기본구조는 페이스텔 네트워크, 페이스텔(Feistel) 방식, 페이스텔 암호 등등으로 불리고 있는데 

이 구조는 DES뿐만 아니라 많은 블록 암호에서 사용하고 있다.

1. 페이스텔 방식

먼저 암호화하려는 정보를 길이가 같은 두 개의 정보로 쪼갠다. 이를 이라고 하고, 라운드 에서 사용되는 키를 , 그리고 라운드 함수를 로 놓는다. 

암호화 과정의 각 라운드에서는 다음과 같은 연산이 이루어진다.

$$
{\displaystyle 0,1,\cdots ,n}

${\displaystyle R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i})}$

모든 라운드가 끝난 후, 최종적으로 가 암호화된 값이 된다. 

복호화 과정에서는 반대의 연간이 이루어 진다. 가 주어졌을 때, 각 복호화 라운드에서는 다음과 같은 연산이 이루어 진다.

${\displaystyle L_{i}=R_{i+1}\oplus {\rm {F}}(L_{i+1},K_{i})}$

최종적으로 원래 값 를 얻는다.

이 방식의 장점 중 하나는 암호화 과정과 복호화 과정이 키 순서를 제외한 전체가 같은 계산을 반복한다는 것.

또한 라운드 함수가 역연산이 존재해야할 필요성이 없음.

마지막 라운드시엔 L과 R이 교체하지 않고 하나로 합쳐져 64비트로 돌아가 암호화된 암호문을 출력한다.

2.  DES 알고리즘

1)  페이스텔 방식을 사용

     - DES는 16회의 라운드를 반복해서 암호화가 진행.

     - 암호화키 56비트를 이용하여 64비트 출력으로 변환.

     - 복호화는 암호화의 역순 

1. 먼저 64비트의 평문이 첫 라운드를 거치기 전에 IP(initial pernutation)를 거침

2. IP를 거친 뒤 평문은 위에서 설명한 페이스탈 구조 원리를 통한 16개의 라운드를 거침

3. 마지막 라운드를 거친 뒤 IP-1에 들어가게 되는데 그 결과가 64비트의 암호문이다. 

2) 평문 

    평문 블록의 크기는 64비트

3) 라운드 함수 ()

확장→XOR연산→ 축소→치환→대체 를 시행

4) 키 스케줄 

64비트의 준비된 키로부터 실제 연산에 쓰일 56비트 DES키 추출. 

그리고 56비트 키로부터 16개의 48비트 라운드 키를 생성. 

3.  DES 알고리즘의 동작

1) IP, IP-1 (Initial Permutation)

IP 표에 의해서 평문을 치환하고 라운드 함수동작

라운드 함수가 끝나면 IP-1로 역연산한다. 

표를 보면 8×8로 64개의 칸이 있고 1-64 수들이 채워져 있고 표안의 숫자가 의미하는 것은 몇 번째 비트인지를 나타낸다. 

즉, IP의 경우엔 입력된 64비트 중 n번째 칸에 해당하는 비트를 n번째에 위치(치환)하도록하여 순서를 바꾸라는 의미이다.

2) 키 스케줄(Key Schedule)

64비트의 입력한 키값으로부터 16개의 라운드키 생성

                                                        

                                          

- PC1 (Permutaion Choice)

64비트 키 입력으로부터 parity bits를 제거하고 56비트로 줄임 (표의 칸이 56개임을 알 수 있음. 그리고 8의 배수가 없음)

- Shift 연산 

매 라운드마다 서로 다른 키 값을 갖기 위해 좌측 쉬프트 연산, 연산시 비트순환

표에서 i는 라운드 수를 의미한다. 키 스케줄 도식도에서 C3, D3 (i=3)은 C2, D2를 좌로 2비트 shift함으로써 구해진다는 의미.

왼쪽으로 shift할 때 오른쪽을 0으로 채우는 것이 아니라 비트가 순환된다는 점을 주의.

- PC2

각 단계에서 생성된 56비트 키를 자리바꿈하며 48비트로 출력 (표의 칸은 48개)

// DES는 64비트 블록 54비트 키 암호 알고리즘이라고 했는데 키 스케줄 도식도를 보면 입력되는 키의 길이가 64비트인 이유는?

사용자는 56비트의 키를 입력하는데 사실은 8비트의 *parity bits가 포함되어 키 스케줄에는 모두 64비트의 키가 들어간다. PC1을 거치면서 56비트로 줄어드는데 이때 parity bits를 제거하기 때문이다. (8번째, 16번째, ... 를 제거)

// 키 입력은 64비트이지만 실제 사용되는 것은 56비트 라는 사실! → DES의 키 길이는 56비트 

3)  함수 (Round Function)

   

함수에는 오른쪽의 32비트 텍스트와 키 스케줄을 거친 키가 들어간다.

- 확장 (Expantation)

입력된 32비트 블록을 48비트로 확장 

- XOR 연산

확장된 블록은 라운드키와 XOR 연산 

- 대체 (Substitution)

XOR연산의 결과로 나온 48비트는 6비트씩 잘려서 8개의 S-box에 대입

각각의 6비트는 S-box에 의하여 치환되면서 4비트로 축소

각 비트에 대해서 해당하는 S-box를 행렬로 생각하여 (첫번째와 마지막 비트를 붙인 값, 첫번째와 마지막 비트를 제외한 나머지 비트 값) 위치에 해당하는 값으로 바꿔주면 4비트 값이 나온다.

4) DES의 복호화 

복호화 엔 암호문을 각 라운드의 라운드키를 역으로 적용

4. DES의 효과

- S-box는 암호화의 선형성을 비선형성으로 바꾸어줌 (그게 없었다면 이진 것셈으로만 구성되므로 선형대수를 이용한 수학적인 공격에 취약)

- S-box, 확장 함수, 비트 혼합함수 덕분에 확산의 성질을 제공

확산(diffusion) : 입력비트의 작은 변화가 출력에는 하나 이상의 비트에 영향을 주는 성질

선형 공격(linear crytanalysis) : 암호 공격의 한 방법으로, 암호화 과정에서의 근사적 선형관계성을 찾는 것을 목적.

5. DES의 취약점

- 각 라운드의 키는 암호 키로부터 선택된 몇 가지 비트만으로 만들어진다. 암호키가 0이라면 모든 라운드키는 0으로 동일하게 된다, 복호화 역시 0으로 가능하다.

- 모든 키 K와 평문 M에 대해 보수적인 특징을 갖는다. 

  평문의 보수 값을 키의 보수 값으로 암호화 하면 기존 암호화된 값의 보수를 얻을 수 있다.( 공격시에 시간을 반으로 줄일 수 있음)

- 블록의 크기가 64비트로 작아서 하나의 키로 암호화할 수 있는 데이터 양이 제한됨

- 트리플 DES는 키의 길이가 3배 늘어나지만 DES가 갖는 취약점을 그대로 가져가서 이상적인 블록암호는 아님 

6. 다중 DES

1) Double DES

DES 알고리즘 자체는 변형시키지 않고 DES의 안정성을 증대시키기 위한 방법 중의 하나로

2개의 서로 다른 키로 2번 암호화 수행. 

여기서 취약한 부분은 첫번째 키로 암호화해서 얻은 암호문과 두번째 키로 복호화해서 얻은 평문을 비교하면 두 개의 암호키를 한꺼번에 찾을 수 있다는 점으로 DES에서 1개의 키를 찾는 것과 2중 DES에서 2개의 키를 한꺼번에 찾을 수 있다는 거와 별반 다를바 없다.

결론적으로 2중 DES의 암호해독시간이 DES의 암호해독 시간의 2배가 되지 않기에 효과가 없다고 보면 된다. 

2) Triple DES (트리플 DES)

DES는 무차별 공격으로 현실적인 시간 내에 해독되어 결국에는 뚫린다.

그래서 DES를 대신할 암호 블록암호가 필요하게 됬는데 이를 위해 개발된 것이 트리플 DES.

DES보다 강력하도록 DES를 3단 겹치게 한 암호 알고리즘 

각 데이터 블록에 DES를 3번 적용한 결과가 암호문이 된다.

DES의 키는 parity bit를 뺀 나머지 56비트이므로 56×3=168비트가 됨

여기서 3번 적용한다는 말을 "암호화→암호화→암호화"라고 생각할 수 있겠지만 

그게 아니라 "암호화→복호화→암호화"형식이다.

트리플 DES의 종류는 키의 동일한지 아닌지에 따라 구분된다.

• DES : 모든 키에 같은 비트열을 사용
• DES-EDE2 : 키1과 키3은 같은 키를 사용하고 키2에 다른키 사용
• DES-EDE3 : 키1, 키2, 키3이 모두 다른 비트열을 사용 

EDE는 암호화(Encryption)→복호화(Decryption)→암호화(Encryption) 순서를 뜻함

트리플 DES의 복호화는 암호화의 역순을 수행하면 됨

*parity bits 란 

https://ko.wikipedia.org/wiki/%ED%8C%A8%EB%A6%AC%ED%8B%B0_%EB%B9%84%ED%8A%B8