[정보보호] DES 암호 알고리즘

자 드디어 본격적으로 암호 알고리즘을 공부해 봅시다.

DES 알고리즘을 들어가기 전에 블록 암호의 구조를 간단하게 살펴보도록 하겠습니다.

아래 사진은 IBM의 암호학자였던 Horst Feistel (독일) 의 사진입니다.

흐 .. 아무래도 사진을 보면 친숙해서 머리속에 더 잘 남을 것 같아 ...

하나 올려봅니다. ^^;

[사진 1] Horst Feistel

이 분이 만든 블록암호의 구조가 DES에 그대로 쓰입니다.

일명, Feistel Cipher 라고 불리는 방식입니다.

(Feistel Network 라고도 합니다.)

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

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

라운드키 자체도 독립적으로 생성하는 것이 좋겠지만, 여러가지 관리상의 문제도 있고 하여 ... 보통은 키(비밀키)를 기반으로 라운드키를 발생시켜 사용합니다. 이러한 것을 키 스케줄이라고 합니다.

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

SPN(Substitution-Permutation Network) 방식과 Feistel Cipher 로 나눕니다.

AES 에서는 SPN 방식을 쓰고 DES 는 Feistel 방식을 씁니다.

SPN 은 AES 알고리즘 할 때 살펴보기로 합시다.

(사실은 적당한 그림이 안 찾아지네요.. ㅋㅋㅋ)

아래 그림을 보세요.

[그림 1] Feistel Cipher

[그림 1]은 Feistel 구조를 나타내 보여주고 있습니다. (Encryption 부분만 보세요..)

평문 64bit 가 입력된다고 하면, 32bit 씩 두개로 나누어서 오른쪽 32bit 와 라운드 키 K 를 F 함수에 통과 시킵니다.

여기서 나온 결과와 왼쪽 32bit 를 XOR합니다.

이러한 과정을 라운드라 하고 라운드를 여러번 반복하게 됩니다.

Feistel Cipher 에서는 입력 블록을 2개로 분리하는데, 입력 블록을 2개보다 더 많이 분리하는 방식이 있습니다.

이러한 방식은 Unbalanced Feistel Cipher 라고 부릅니다.

블록 암호의 구조중 Feistel Cipher 에 대해서 잠깐 살펴보았는데요....

DES 에서는 F함수가 어떻게 구성되고 키 스케줄은 어떻게 하는가 ? 이런 의문을 가지고 .. 쭉 읽어내려 가시면 되겠습니다. ^^;

[DES 알고리즘]

AES 와 DES 를 구현해 보면 AES 가 깔끔하게 구현된다고 하였습니다.

알고리즘에 있어서 .. DES 는 어려운 수학이 사용되지 않습니다.

그림을 보면서 bit 연산만 잘 수행하면 됩니다. 흐 ... 말은 쉬운데 ...

반면, AES는 어렵다고 해야할지 모르겠지만 수학공식이 한번 사용됩니다.

그대신 복잡한 그림이 많이 필요하지 않습니다.

아래 그림들을 보면서 미리 쫄지 마세요... DES 는 어려운 수학은 전혀 사용되지 않습니다.

[그림 2] DES 알고리즘 : 데이터 암호화 부분

위의 [그림 2] 는 DES 알고리즘 중에서 평문을 암호화 하는 부분을 도식화 한 것입니다. 빠진 부분은 K1 ... K16 의 값인데요... 이 값은 라운드키로써 키 스케줄을 통해서 생성됩니다. [그림 3] 에서는 키 스케줄을 보여줍니다.

[그림 2] 를 가만히 보면 Feistel Cipher 방식과 비슷하지 않나요 ?

64bit 를 입력 받아서 IP(Initial Permutation) 과정을 거치면 bit 의 순서가 바뀐 64bit 가 출력됩니다.

출력된 값을 32bit 씩 나누고(좌측은 L0, 우측은 R0) ... R0 와 라운드키 K1 을 f 함수에 통과 시킨 값과 L0를 XOR 합니다. 이값은 R1 으로 가고 ..... R0 는 L1 으로 갑니다.

이런식으로 ... 쭉 진행됩니다. f 함수를 16번 통과할 때까지 반복됩니다(라운드 함수 16회 적용).

그리고 맨 마지막에서 .... IP^-1(Inverse Permutation) 을 수행합니다.

이제 K₁ ~ K₁₆ 까지의 값과 IP 와 IP^-1 를 어떻게 구하는지... f 함수는 어떻게 처리되는지 알면 DES 를 구현할 수 있습니다. [그림 4] 는 f 함수를 나타내 보여 줍니다.

먼저 키 스케줄을 살펴봅시다.

[그림 3] DES 알고리즘 : 키 스케줄 부분

흠 별건 없는 것 같네요 .. 64bit 키가 입력되면 PC1 을 거쳐(56bit 로 변환) 28bit 씩 쪼개서 각각을 좌로 shift 연산 후 PC2 를 거쳐 48bit 짜리 키를 뱉어냅니다.

16개의 라운드 함수마다 키를 공급해 주어야 하므로 여기서도 16번 48bit 짜리 키를 뱉어냅니다.

일단 PC1, PC2, 좌로 shift 연산 ... 이런 것들을 알아야 완전해지겠네요 .....

결코 쫄지 맙시다...

어려운 수학은 없습니다.

별로 안 어려운데 표현이 어려울 따름입니다.

일단 라운드키는 공급할 수 있겠는데... 아직까지 ....좌로 shift 연산, IP, IP^-1, PC1, PC2, f 함수 등의 실체가 밝혀지지 않았네요.

일단 f 함수의 그림을 살펴봅시다.

[그림 4] f 함수 (라운드 함수)

앗 .. [그림 4] 를 보니 드디어 .. f 함수의 실체가 밝혀지네요 ...

그런데 ... 이 무슨 ... E(Expansion), P(Permutation), S₁ ~ S₈ 과 같이 모르는게 더 많아져 버렸네요.

f 함수 흐름만 설명하고 나서 빨간 놈들의 실체가 곧 밝혀집니다. 두둥 ~~~

일단 f 함수 자체는 이해가 됩니다. 그렇지요 ? ^^;

입력값으로 R₀, K₁ .... R₁₅, K₁₆ 을 사용합니다.

32bit R₀ 값을 확장(Expansion) 하여 48bit 로 만들어 48bit K₁ 키와 XOR 연산합니다.

그러면 48bit 나올텐데 이 48bit 를 8개로 쪼갭니다. 한 조각은 6bit 가 되겠죠 ....?

이 6bit 각각이 S1 ~ S8 을 통과합니다(S-Box). 그러면 각각은 4bit 로 줄어들게 됩니다. 그래서 최종 32bit 출력이 되고 P(Permutaion) 연산을 수행하여 최종 32bit 값이 나옵니다.

이제 다음 빨간 글씨만 해독하면 DES 는 모두 구현할 수 있을것 같습니다.

좌로 shift 연산, IP, IP^-1, PC1, PC2, E(Expansion), P(Permutation), S₁ ~ S₈

잠시 한숨 돌리는 차원에서 ... 한가지 짚고 넘어갑시다.

DES 는 64bit 블록 56bit 키 암호 알고리즘으로 알고 있지요 ? 그런데 ... [그림 3] 에서 보면 입력되는 키(비밀키)의 길이가 64bit 지요 ? 이상하지 않나요 ?

PC1 을 거치면서 56bit 로 줄어들게 됩니다. parity bit 를 제거해 버리는데요 .. 8번째bit 제거, 16번째bit 제거 .....

이런식을 1byte 를 없애 버립니다.

즉, 키 입력은 64bit 지만 실제 사용되는 것은 56bit 이라는 사실을 명심하셔야 합니다.

DES 의 키길이는 ? 이런 질문을 했을 경우에 56bit 라고 대답하는 것이 정답입니다.

자 이제 ... 빨간 글씨를 해독해 봅시다 .....

Permutation 이라는 말이 있으면 암호학 개요에서 살펴보았던 전치(transposition) 와 거의 같다고 보시면 됩니다.

S-Box 는 치환(substitution) 을 할 수 있도록 구성된 테이블입니다.

* IP, IP^-1

[표 1] IP 와 IP^-1

위의 [표 1]을 보세요 ... 8x8 로 64개의 칸이 있고 1부터 64까지 채워져 있습니다.

표안의 숫자가 의미하는 것은 몇번째 bit 인지를 나타냅니다.

즉, IP 의 경우엔 입력된 64bit 중 58번째 bit 를 제일 앞에 위치하도록 순서를 바꾸라는 의미입니다.

50번째 bit 를 두번째로 위치하도록 하고 ...계속 진행하면서 ..

표의 순서대로 bit 의 배열을 바꾸면 되는 것입니다.

IP^-1 의 경우엔 40번째 bit 가 맨 앞으로 오도록 ... 표에 적힌 숫자를 보면서 bit 의 순서를 바꾸면 됩니다.

* PC1, PC2

[표 2] PC1 : 64bit 를 56bit 로 줄임

[표 3] PC2 : 56bit 를 48bit 로 줄임

위의 [표 2]에서 보여지듯이 Permutation Choice 과정은 bit 의 순서를 바꿉니다. 하지만, 표의 칸이 56개밖에 되지 않습니다. 입력은 64bit 인데 말이죠.... 즉 .. 8, 16, 24 .... 번째 bit 는 버리게 됩니다.

표에서도 보면 8의 배수가 쏙~~ 빠진 것을 알 수 있습니다.

[표 3]에서는 칸이 48개입니다. 즉 56bit 를 48bit 로 바꾸는 것입니다.

* 좌로 shift 연산

[표 4] Key Left Shift

위의 [표 4]를 보시면 i 는 라운드 수를 의미합니다. [그림 3]의 키 스케줄 부분에서 C3,D3 는 즉 i 가 3일 때는 C2,D2 를 좌로 2bit shift 함으로써 구해집니다.

왼쪽으로 shift 를 할 때 오른쪽을 0 으로 채우는 것이 아니고 bit 가 순환된다는 것을 주의 하세요.

* E(Expansion), P(Permutation)

[표 5] Expansion : 32bit 를 48bit 로 늘임

위의 [표 5]를 보시면 ..... 같은 숫자가 나타나는 것을 보실 수 있습니다.

지금까지 봐왔던 표와 마찬가지로 숫자는 몇번째 bit 인지를 나타냅니다. 같은게 있으므로 키 길이가 늘어나겠죠?^^;

[표 6] P-Box (Permutation) : bit 의 순서를 표에 나타낸 것처럼 바꿈

위의 [표 6] 은 Permutation 과정인데 P-Box 라고도 얘기합니다. 32 bit 의 순서를 바꿉니다. 표에 나타낸 순서대로 ...

이것도 별로 어려울게 없는것 같네요 ...

* S^₁ ~ S₈ (S-Box)

S-Box 는 지금까지 봐왔던 Permutation 과는 조금 다르게 변환이 일어납니다.

일단 아래 S-Box 표를 보시기 바랍니다.

 

[표 7] S-Box : 6bit 를 4bit 로 변환

위의 표에서처럼.. S-Box 는 6bit 입력을 4bit 로 변환시킵니다.

Permutation 과는 다른 방식으로 진행이 됩니다.

만약 011011 의 6bit 입력된다고 하면 S1 에다가 적용을 해봅시다.

먼저 행을 구하기 위해 첫번째 bit 와 마지막 bit 를 가져옵니다. 01 이 되고 즉 1이 됩니다.

열을 구하기 위해 첫번째와 마지막 bit 를 제외한 나머지 bit 를 가져옵니다. 1101 이 되고 이 값은 13이 됩니다.

행은 0~3까지 열은 0~15까지입니다. (1,13) 을 S1 에서 찾아보면 5가 되고 이것은 0101 이 됩니다.

즉, 6bit 입력이 4bit 로 바뀐 것을 알 수 있습니다. 이런 식으로 S-Box 치환이 진행됩니다.

드디어 DES 의 알고리즘이 끝이 났네요 ...

다음번에는 DES 의 취약키를 한번 알아보고 ... AES 로 넘어가도록 하겠습니다. ^^;