Symmetric key Encryption - DES

DES :: Data Encryption Standard 

DES는 저번 글에서 살펴본 Block cipher에 사용하는 암호화 기법 중 대표적인 예시라 할 수 있다. 

 

CBC의 경우 plaintext와 IV를 XOR 한 후 key를 가지고 Encryption 하여 ciphertext를 만들어냈다.

이 과정에서 Encryption에 해당하는 방법 중 하나가 DES인 것이다. 

 

DES 과정을 살펴볼 때 input text의 길이는 고정적으로 64 bits로 볼 것이고 key는 56 bits이다.

전체적인 과정은 지금까지 봐온 것과 마찬가지로 plaintext와 key를 사용해 암호화 과정을 거치고,

ciphertext와 key를 사용해 복호화하는 과정을 거친다. 

 

DES의 경우, 어떤 암호화 과정을 거치는 지에 대해 상세히 알아보도록 하자.

---

Encryption 부분을 확대해서 드려다봤다고 상상하면 다음과 같다. 

64 bit의 input이 들어오면 initial permutaion 과정을 거치고 나서 16번의 round를 진행한다. 

모든 round가 끝나고 나면 final permutation을 거치고 나서 64 bit의 output이 나오게 된다. 

 

각 round에서는 key generator 과정에서 생성한 key를 사용하며 

key는 원래 56 bits이지만 48 bits로 축소된 길이의 key를 만들어 암호화에 사용한다.

 

 

 

Initial permutation & Final permutation

우선 initial & final permutation에 대해 알아보자. 

permutation은 이전 글에서 설명했듯이 하나의 input에 대해 하나의 output이 매칭되는 성질을 말한다. 

 

DES에서 permutation이라는 단어가 들어가는 과정에서는 이미 만들어진 table에 따라 매칭된 값을 사용한다.

initial Permutation & final permutation은 모두 64 bits인 input & output에 적용하기 위한 테이블이라서 

8X8 크기로 구성되어있다. 

 

 

initial permutation에서 첫 번째 요소인 58을 예시로 테이블의 내용을 설명해 보자면,

"input text의 58번째 bit는 58이 쓰여 있는 (row 1, col 1) 자리로 이동해라!"

라는 뜻이다. 64 bits의 input에 대해 각 bits가 이동할 자리표라고 생각하면 된다. 

 

 

final permutation은 그 반대로 이동시킨 bit를 원래 자리로 되돌리는 자리표라고 할 수 있다.

그렇기 때문에 initial & final permutation table은 서로 inverse 한 성질을 갖는다. 

 

ex)  inverse한 initial permutation & final permutation table

initial permutation에서 01의 위치 = 40번째	final permutation에서 40의 위치 = 01번째
input에서 1번째 비트 40번째 자리로 이동해라!	round를 마친 후의 text에서 40번째 비트는 1번째 자리로 이동해라!

 

 

---

Round

initial permutation을 마친 후에는 총 16번의 Round 과정을 거치게 된다. 

Round 과정을 확대해서 보자면 다음과 같다. 

64 bits를 왼쪽 32 bits, 오른쪽 32 bits로 나눠 L과 R로 구분한다. 

현재 round의 R은 그대로 내려와 Swapper를 통해 다음 round의 L 자리로 이동하게 되고 

현재 round의 L은 Mixer를 통해 xor 연산을 거친 후 다음 round의 R 자리로 이동하게 된다. 

(* 16번째 round에서 swap 과정은 일어나지 않는다. )

 

xor 연산을 하기 전에 실행되는 DES function에서는 현재 round의 R과 key가 사용된다. 

그렇다면 DES function에서 어떤 과정이 일어나는지 알아보자.

 

 

DES function

DES function에서는 일단 R 자리에서 들어온 input 32 bits를 48 bits로 확장시킨다.

그 후 48 bits의 key와 XOR 연산을 하고 S-box라는 과정을 통해 다시 32 bits 길이로 축소된다. 

 

 

Expansion P-box))

32 bits를 48 bits로 확장하는 과정은 그리 어렵지 않다. 원래의 32 bits는 4 bits X 8 block으로 구성된다고 상상해 보자! 

이때 이웃 block의 사이드 비트를 가져와 앞뒤로 붙여주면 끝이다. 

 

 

그러면 6 bits X 8 block으로 총 48 bits의 bit string이 만들어진다. 

그 상태에서 S-box 과정을 거치게 된다. 

그림에서와 같이 S-box를 실행하고 나면 48 bits로 확장되었던 길이가 다시 32 bits로 돌아가게 된다.

 

 

S-box))

6 bits X 8 block의 데이터에 대해 각 block마다 이 과정을 처리한다고 보면 된다.

6 bits 중에서 맨 처음과 끝 비트로 나타낸 값은 row,

2~5번째 비트로 나타낸 값은 column으로 삼아 해당 row, col에 해당하는 값 4 bits을 output으로 뽑아낸다.

 

1, 6번째 비트를 사용하면 총 2개의 비트로 수를 나타내는 것이기 때문에 2^2 = 4개의 row,

2~5번째 비트를 사용하면 총 2^4 = 16개의 col 수가 나오고 

이 테이블에서 나타내는 값은 16진수이기 때문에 4 bits 값이 output으로 나오게 되는 것이다.

 

따라서~

8 block이 이 과정을 거치게 되면 4 bits X 8 block이 되기 때문에 원래의 길이 32 bits로 돌아가게 된다!

 

 

Straight P-box))

이 부분은 permutation과 비슷하게 이미 정해져 있는 table 값을 보고 bit의 자리를 섞는 과정이라 할 수 있다.

 

---

마지막으로 각 round에서 사용하기 위한 key를 만드는 "key generator"에 대해 알아보자.

맨 처음에 제공되는 key는 64 bits인데 이는 data 7 bits + parity 1 bits가 붙어서 만들어진 것이기 때문에

generator로 들어가기 전 parity bit를 제거하는 과정을 거친다. [64 bits → 56 bits]

 

56 bits key는 28 bits + 28 bits로 쪼개지고 각 28 bits에 대해 shift left가 실행된다.

! round 1 & 2 & 9 & 16에서는 shift를 한 번만, 나머지 round에서는 2번 shift를 실행한다.

 

shift를 진행한 후 각 28 bits를 이어 붙인 56 bits에 대해 compression P-box를 실행하는데, 

compression P-box의 경우도 이미 지정된 table 값을 보고 해당하는 bit를 48개 가져와 48 bits key를 만든다.

 

 

? 56 bits 중에서 48 bits만 선택해서 key로 사용하게 되면 낭비 아닌가? 싶을 수 있지만

각 round key를 생성할 때 shift 연산을 진행하기 때문에 bit의 자리가 계속해서 바뀌게 된다.

따라서 모든 bit가 골고루 key를 만드는 데에 사용될 수 있다. 

 

---

[ Summary ]

DES )) 

:: 크게 permutation & round 단계로 구성된다.

:: round = Mixer & swapper & DES function

:: 마지막 round에서는 swapper 과정이 제외된다.

:: DES function = expansion & XOR & S-box & P-box 

:: key generator = 28 bits로 쪼개 shift 연산