DES(Data Encryption Standard)

DES는 1977년에 미국의 연방 정보 처리 표준 규격(FIPS)으로 채택된 대칭암호이다. 

전사 공격을 통해서 해독할 수 있는 수준의 보안 강도를 가지고 있다. 

여기서 전사 공격이란 가능한 모든 경우의 수를 다 대입함으로써 암호를 찾아내는 방식이며, 

브루트포스 방식과 같다. 

DES는 64 비트의 키를 적용하여, 64 비트의 평문을 64 비트의 암호문으로 암호화 시키는 대칭형 블록 암호이다. 

여기서 대칭형 암호라는 것은 암호화에 쓰이는 키와, 복호화에 쓰이는 키가 동일한 방식을 말한다. 

그리고 이러한 대칭키 암호는 블록 암호화와 스트림 암호화로 분류된다. 

여기서 블록 암호는 고정된 N 비트의 블록으로 나누어 암호화 알고리즘을 적용하고
스트림 암호는 유사 난수를 생성하여 암호화하려는 값과 XOR 연산을 통해 1비트씩 암호화를 수행한다.

스트림 암호의 경우, 암호화 알고리즘이 블록 암호보다 단순하기 때문에 구현이 쉽고 암호화 속도가 빠르기 때문에 무선통신에 주로 사용한다. 

DES 알고리즘에서 사용하는 함수

• - 대체(substitution)
• - 치환(permutation)
• 대체와 치환은 1949년도에 Claude Shanon 이 제시한 혼돈confusion과 확산difusion 이라는 두 가지 개념에 기반을 두고 있다. 

보조키생성

DES 암호화 알고리즘의 과정 중에는 키를 이용하여 생성한 보조키가 쓰인다. 이 보조키는 다음의 과정을 통해서 생성된다. 

DES 보조키 생성 과정

DES는 56 비트의 비밀키를 사용하는데, 중간중간 7비트 마다 에러정정을 위한 비트를 삽입하기 때문에 보조키를 생성할 때는 총 64비트의 키가 들어가게 된다. 56/7 = 8 , "56+8 = 64" 

DES supplementary material : 위키 피디아(영문)

1. 먼저 64 비트의 키 중에서 정정 비트를 제외한 56 비트를 대상으로 PC-1(Permutation Choice) table을 적용해서 전치한다.

위의 표의 첫번째, 두 번째 수를 보면 57, 49가 있는 것을 볼 수 있다. 이것의 의미는 57번째 비트를 첫 번째 자리로, 49번째 비트를 두 번째 자리로 위치시키라는 뜻이다. 그리고 이 표에서 8의 배수가 없는 것을 확인할 수 있는데, 이것은 7비트 마다 삽입된 에러 정정 비트를 제외시킨 것을 말한다. 이 작업을 통해 56 비트의 배열이 만들어 진다. 

이것을 예시를 통해서 알아보자.  

암호화 키 56 비트는 "Notepad"라고 할 때, 이것은 56비트이며, 다음과 같은 이진수 값을 가진다. 

01001110 01101111 01110100 01100101 01110000 01100001 01100100

8비트씩 분리해서 보면 7개로 나눌 수 있고, 그 부분에 에러 정정 비트를 삽입하면, 

01001110 00110110 11011101 10001101 01010110 10000010 10000100 11001001

이렇게 밑줄 쳐진 8개의 비트가 삽입되어 최종적으로 64 비트가 된다. 

여기에 PC-1 전치를 적용한 결과는 다음과 같다. 

Left 1110110 0100101 0100000 0100001

Right 0011001 1010111 1110000 1010110

왼쪽 오른쪽 각각 28비트씩 총 56비트가 된다. 이 둘은 위 그림의 C0, D0로 생각하면 된다. 

그 다음으로 이렇게 구해진 left와 Right 각각에 대해 좌측 순환 이동을 적용한다. 그 횟수는 총 16회 

수행하는데, 한 회마다 몇 비트씩 이동하는 지는 아래 표에 따른다. 

DES supplementary material 

먼저, 위에서 살펴본 C0, left를 먼저 살펴보면, 1라운드에서 1비트 좌측으로 이동하게 된다. 

Before 1110110 0100101 0100000 0100001

 After  1101100 1001010 1000000 1000011 

오른쪽도 마찬가지로 1라운드 순환이동을 하고 그 다음  Left와 Right는 다시 합쳐진 다음, PC-2 전치를 거친다.

PC-2에서는 8개의 비트가 제외되게 되고, 48개의 비트만 남는다. 여기까지의 과정을 마치게 되면 16개의 보조키 중, 

첫 번째 보조키(48 비트)가 완성된다.

두 번째 보조키는 1라운드 순환을 마친 Left와 Right를 가지고 2라운드 순환과 PC-2를 거쳐 만들어 지고, 

16라운드 반복을 통해 16개의 보조키가 만들어 진다. 

이제 이 보조키를 활용한 암호화 과정에 대해 알아보도록 하자.

암호화 과정

가장 먼저 암호화 하려는 평문을 이진수로 바꾸고, 해당 이진수를 64비트의 블록 단위로 쪼개는 작업을 진행한다. 

암호화 알고리즘은 64비트 단위로 적용된다. 이 64비트 블록은  IP(Initial Permutation)이라는 초기 순열을 이용한 전치를 거쳐 새로운 64 비트를 생성한다. 

58번째 비트가 첫 번째 자리로, 50번째 비트가 두 번째 자리로, 재배열된 64비트 배열

이 배열은 왼쪽과 오른쪽, 각각 32비트씩 분리되어 암호화 과정을 거친다. 

이때, 왼쪽 32비트를 L0, 오른쪽 비트를 R0라고 하면 1라운드 암호화를 거치면 L1, R1이 생성된다. 

L1은 R0를 그대로 가져 오는데 미해 ,  R1 추가 과정을 거쳐서 만들어진다. 

먼저 R1을 만들기 위해서, 32비트은 R0를 확장순열(Expansion permutation)를 통해 전치해서 48비트의 배열로 확장한다. 

이 48비트의 배열을 48비트인 보조키와 XOR 해주는데, 1라운드 이기 때문에 첫번째 보조키와 XOR 연산해준다. 

연산된 48비트를 6비트 길이로 나누어 8등분 해준다. 

이제 이 8등분한 6비트를 가지고, S-box를 통해 치환을 적용한다. 

치환을 이용할 때는, 6 비트 중 첫번째 비트와 여섯번째 비트를 사용해서 행번호를 나타내고, 2비트 이므로 4가지

2, 3, 4 번째 비트를 통해 열번호를 가리킨다. 

그럼 이 표를 통해서 8토막은 8개의 숫자(6비트 8토막)로 변경된다. 

이 각각을 4비트의 이진수로 바꾸어서 연결해 주면, 32 비트 배열로 바꿔 줄 수 있다. 

마지막으로 이 32비트 배열에 p(permutation) 전치를 거친다. 

최종적으로 나온 32비트 배열을 앞서 계산한 L0와 XOR 연산을 해준다. 

여기서, 나온 32비트의 배열 까지의 과정을 F(Feistel)연산이라고 한다. 

이렇게 되면 L1 과 R1을 구할 수 있다. 

이런 연산을 16라운드 수행하고

마지막으로 생성된 L16, R16의 위치를 바꿔서 R16, L16로 바꿔주고 초기 전치에 사용된 IP 순열의 역순열(IP-1)을 사용해서 이 64비트에 적용한다. 

[보조키 16개 생성]

1. 64 bits 키에 PC-1 전치를 적용하여 56 bits 생성
2. 56 bits 를 28 bits 씩, C0와 D0로 나누기
3. C0와 D0, 각각에 좌측 순환 이동을 적용하여 C1과 D1 생성
4. C1과 D1에 PC-2 전치를 적용하여 48 bits 보조키 K1 생성
5. C1과 D1에 3, 4 번 과정 적용, 16번 반복하며 총 16개의 보조키 생성

[암호화 과정]

1. 평문 -> 이진수 -> 64 bits 블록 단위로 쪼개기
2. 64 bits 블록에 IP 초기 전치를 적용하여 새로운 64 bits 생성
3. 왼쪽 32 bits 인 L0와 오른쪽 32 bits 인 R0 로 L1과 R1 만들기
   • 3-1. L1 = R0
   • 3-2. R1 = f(R0) XOR L0, f(x) : x -> 확장 전치(48비트) -> 보조키와 XOR -> S-box 치환(32비트) -> P 전치(32비트)
4. 3의 과정을 16번 반복
5. 최종 생성된 L16과 R16을 서로 바꾸어 합침
6. 합친 64 bits 에 IP 역 전치 적용하여 최종 암호문 생성

이러한 DES의 운영방식에는 다음의 4가지가 잇다. 

• ECB(Electronic CodeBook) 가장 간단한 방식. 평문을 64 bits 씩 나누어 암호화 한다. 64 bits 로 나누어 떨어지지 않으면 약속된 패딩 비트를 삽입한다.
• CBC(Cipher Block Chaining) 출력 암호문이 다음 평문 블록에 영향을 미치게 하여 ECB와는 달리 동일한 평문이라 하더라도 다른 암호문이 생성된다.
• CFB(Cipher FeedBack) 통신 프로토콜에 사용될 수 있다. DES 알고리즘으로 생성된 키 수열과 r 비트 단위의 평문을 XOR 하여 암호문을 만든다. 암호문은 다시 키 수열을 만든는데에 쓰인다. CBC와 마찬가지로 동일한 평문에 대해 다른 암호문을 생성할 수 있다.
• OFB(Output FeedBacck) CFB 와 비슷하지만 생성된 암호문이 다음 암호문에 영향을 미치지 않는다. DES 알고리즘으로 생성된 키 수열 중 왼쪽의 r 비트를 암호화하는데 사용하고, 키 수열의 왼쪽 r 비트가 다음 키 수열을 만드는데에 사용된다. 동일한 평문에 대해 다른 암호문을 생성하면서, CFB에서 잡음에 의해 잘못 생성된 암호문으로 인해 발생할 수 있는 오류 전파 문제를 해결할 수 있다.