Simplified Data Encryption Standard (Simplified DES)

Author silnex

---

Introduce S-DES

TL; DR
바로 Example로 넘어가고 싶다면,
[SimpleDES] Simplified Data Encryption Standard Practice 로…

Padding Oracle Attack을 공부하기 위해 CBC에 대해서 공부하던 중 Block Cipher에 대해 자세히 알고 싶다는 생각이 들어,
지금은 사용되지 않지만 가장 유명한 암호화 방식인 Data Encryption Standard(DES)를 공부하게 되었다.
DES알고리즘을 학습해야하지만 일반적인 DES에서 사용되는 key인 56bit는 다소 복잡해 이해 하기가 어려워,
key가 10bit로 이루어진 Simplified DES를 통해 DES알고리즘에 대해서 학습해본다.

SDES는 기존 DES와 Key의 bit수 차이와 반복되는 Round 의 차이만 있을 뿐 알고리즘은 동일하며,
SDES의 확장을 통해 DES를 이해를 위해 만들어진 SDES인 만큼 DES의 56bit키가 왜 위험한지에 대해서도 충분이 이해 할 수 있다고 한다.

Analyze DES

DES는 대칭키 암호이기 때문에 Key를 통해 subKey인 K₁과 K₂를 생성하는 Key Generation(①)과정, (PlainText를 Block단위로 쪼개어 암호화 하기위해서다. DES가 Block Cipher라 불리는 이유)
PlainText(평문)를 암호화하는 Encryption(②) 과정,
암호화된 CipherText(암호문)를 복호화 하는 Decryption(③)과정까지 총 3개의 과정이 필요하다.

이제 필요한 함수에(P₁₀, P₈, Shift, IP, IP^-1, SW, f_k, E/P, S-Box, P4 )대해서 알아보자.

Functions

Key Generation에서 사용되는 함수들

 

Function P₁₀ 

input length(or bit): 10
output length(or bit): 10

P₁₀의 P는 Permutation(순열)의 약자로, 아래와 같은 함수로 표현된다.

P₁₀(k₁, k₂, k₃, k₄, k₅, k₆, k₇, k₈, k₉, k₁₀) = (k₃, k₅, k₂, k₇, k₄, k₁₀, k₁, k₉, k₈, k₆)

수식으로 표현하니 이해하기 여러울 수 도있지만, 단순히 순서를 바꾸는 역할을 할 뿐이다.
예를들어 P₁₀(1,2,3,4,5,6,7,9,0) = (3,5,2,7,4,10,1,9,8,6) 처럼 순서만 바꾸는 역할을 한다.
다만, P₁₀에서 사용되는 바뀌는 순서에 대한 값은 임의의 값이 아닌 SDES에서 고정적인 값이다.

P₁₀을 표로써 표현하면 아래와 같이 표현할 수 있다.

P10

3 5 2 7 4 10 1 9 8 6

 

Function P₈ 

input length(or bit): 10
output length(or bit): 8

또한 P₁₀과 같은 의미이나 10개의 인자값을 받아 8개만 선택해 출력하는 함수이다.
수식으로 표현하면,

P₈(k₁, k₂, k₃, k₄, k₅, k₆, k₇, k₈, k₉, k₁₀) = (k₆, k₃, k₇, k₄, k₈, k₅, k₁₀, k₉)

즉, 결과 값에 없는 k₁, k₂는 버려진다. 이를 표로 표현하면 아래와 같이 표현 할 수 있다.

P8

3 7 4 8 5 10 9

 

Function Shift

input length(or bit): 5
output length(or bit): 5

Shift는 BitShift연산자중에서 Left Shift를 의미하는데, 왼쪽으로 넘어간 bit는 오른쪽에서 나오게 된다.
즉, 10011₍₂₎을 Shift 2번 이라고 한다면, 00111₍₂₎이 되는것이다.
대게 줄여서 LS라고 하며 Shift횟수에 따라 한번이면 LS-1 두번이면 LS-2라고 한다.

수식으로 표현하자면,

LS-1(10110₍₂₎) = 01101₍₂₎; LS-2(11011₍₂₎) = 01111₍₂₎

 

Encryption, Decryption에서 사용되는 함수들

XOR(⊕)은 따로 설명하지 않는다.

 

Function IP and IP^-1

input length(or bit): 8
output length(or bit): 8

IP는 Initial and Final Permutations의 약자로, 처음과 끝에 순서를 바꾸어 주는 역할을 한다.
즉 P₁₀ 과 크게 다르지 않다. 다만 IP는 ‘역’인 IP^-1 가 존재한다. 
수식으로 표현하면,

IP(k₁, k₂, k₃, k₄, k₅, k₆, k₇, k₈) = (k₂, k₆, k₃, k₁, k₄, k₈, k₅, k₇)
IP^-1(k₂, k₆, k₃, k₁, k₄, k₈, k₅, k₇) = (k₁, k₂, k₃, k₄, k₅, k₆, k₇, k₈)

으로 표현된다. 즉, IP-1(IP(X)) = X란 뜻이다.
이를 간단히 표를 통해 표현하면 아래와 같다.

IP

2 6 3 1 4 8 5 7

IP-1

4 1 3 5 7 2 8 6

 

Function f_k

input length(or bit): 8
output length(or bit): 8

f_k에서 k는 keygen에서 생성된 key의 종류를 의미한다.
f_k는 입력받은 8bit의 값을 4bit/4bit 으로 쪼개어 왼쪽bit/오른쪽bit라고 부르며 나누어 사용한다.

중요한건 오른쪽bit인데 순서데로 E/P를 거쳐 Xor후에 S₀, S₁로 나누어져 동작 하고,
이를 다시 P₄의 넣어 출력후 왼쪽bit와 Xor한다.
말로 표현하니 이해가 힘들수도 있지만, DES에서 가장 핵심이기에 잘 알아두자.

 

Function E/P

input length(or bit): 4
output length(or bit): 8

E/P는 Expansion/Permutation의 약자로 말 그대로 확장하고 순서를 바꾼단 뜻이다.
이도 IP나 P10과 같이 순서를 바꾸는 것은 동일하지만 4자리의 bit를 8bit로 확장 한다는 점이다르다.

E/P를 수식으로 나타내면 다음과 같고,

E/P(k₁, k₂, k₃, k₄) = (k₄, k₁, k₂, k₃, k₂, k₃, k₄, k₁)

이를 표로 나타내면 아래와 같다.

E/P

4 1 2 3 2 3 4 1

 

Function S₀ S₁(S-Box)

S₀, S₁ 각각 input length(or bit): 4
output length(or bit): 2

S₀와 S₁는 S-Box라고 불리며, 기존의 E/P, IP, P10과는 달리 행렬을 이용한 연산이지만,
그렇게 복잡한 연산은 아니다.
다만, 이를 위해선 고정된 S-box 행렬이 필요한데 두 행렬은 아래와 같다.

S0	1	0	3	2	S1	0	1	2	3
	3	2	1	0		2	0	1	3
	0	2	1	3		3	0	1	0
	3	1	3	2		2	1	0	3

입력(4bit)에대하여 위의 행렬을 참고해 다음과 같은 연산을 진행한다.

Ex) input : 0101 1010₍₂₎ 
(구분을 위해 색을 칠했으며, E/P와 key을 xor한 8bit 입력을 4bit로 쪼개어 각각 대입하여 사용한다.)
S₀(01₍₂₎,10₍₂₎) S₁(10₍₂₎,01₍₂₎) => S₀(1,2) S₁(2,2) => 1, 1 => 01 01₍₂₎

S-box를 수식으로 표현하면 다음과 같이 표현할 수 있으나 이해가 위 예제를 통해 이해가 힘들때 참고 정도로만 사용하면된다.

i = input; n = 0, 1;
S_n(i_1,4,i_2,3)

Function P₄

input length(or bit): 4
output length(or bit): 4

P4는 기존의 IP P10과 동일하게 4자리의 bit를 순서를 바꾸어 주는 역할을 한다.
수식으로 표현하면 다음과 같고,

P₄(k₁, k₂, k₃, k₄) = (k₂, k₄, k₃, k₁)

표로 표현하면 아래와 같다.

P4

2 4 3 1

 

Function SW

input length(or bit): 8
output length(or bit): 8

SW는 단순히 왼쪽 4bit와 오른쪽4bit를 바꾸어주는 역할을 한다.
간단한 과정이니 수식으로만 표현하겠다.

SW(k₁, k₂, k₃, k₄, k₅, k₆, k₇, k₈) = (k₅, k₆, k₇, k_8, k₁, k₂, k₃, k₄)

---

이로써 S DES에서 암호화, 복호화와 키 생성에 필요한 함수를 모두 알아보았다.
이를 통해 다음 글에선Key를 직접 생성해 보고 Encryption과 Decryption을 직접 해본다.

 

---

이미지 출처 및 참고 자료

http://homepage.smc.edu/morgan_david/vpn/C-SDES.pdf