dreamhack [블록암호 :DES] 정리
https://dreamhack.io/lecture/courses/72 를 바탕으로 정리했습니다.
블록암호: DES
DES의 기본 원리와, DES로 데이터를 암복호화하는 과정을 설명합니다.
dreamhack.io
1. 들어가며
-서론
DES(Data Encryption Standard) 는 미국의 국가 안보국(NSA) 에서 만든 56비트 키 길이의 대칭키 암호이다.
8바이트(64비트)를 한 블록으로 하는 블록 암호.
DES 구조:
초기순열(Initial Permutation, IP) 최종 순열(final permutation, FP), 페이스텔(feistel)구조의 16라운드
+ 각 라운드에 키 생성(48비트) 함수 사용
2. DES의 원리
-순열과 치환, 그리고 곱 암호
치환(subsitution) : 혼돈 성질을 만족하기 위해
순열(permutation) : 확산 성질을 만족하기 위해
이들을 한 번 적용한 것만으론 암호학적 효과를 기대하기 어렵다.
그러나, 여러 번 반복적으로 교차 적용하면 혼돈, 확산 성질 모두 만족할 수 있다.
곱 암호 (product cipher)
단순 연산들로 한 라운드 구성 -> 각 라운드를 여러 번 반복해 안정성 확보
-페이스텔 구조
: DES에서 라운드 함수를 적용하는 전체과정을 이루고 있는 구조
(1) 왼쪽 블록 L, 오른쪽 블록 R
(2) 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력됨
(3) 왼쪽 블록은 오른쪽 블록의 라운드 함수 결과와 xor되어 다음 라운드의 오른쪽 블록으로 입력됨
<정형화한 식>
(1)L0=P[:len(P)/2], R0=P[len(P)/2:]
(2)Ln+1=Rn
(3)Rn+1=Ln⊕F(Rn,Kn)
3. DES의 과정
-step1 & step3. 초기 순열과 최종 순열
: DES의 안정성을 높이진 않지만, DES를 하드웨어에 구현하기 쉽게 해줌
시작 : 초기 순열(initial permutation) 수행
마지막 : 최종 순열(final permutation) 수행
(서로 역관계. 따라서 64비트 데이터에 초기 순열을 적용하고, 최종 순열을 적용하면 입력 값이 그대로 출력됨)
이 둘은 65비트 입력을 테이블을 이용해 비트 단위로 전치함.
(테이블 n번째 값:m, 출력 n번째 비트:입력의 m번째 비트)
초기 순열 테이블 (initial permutation table,IPT), 최종 순열 테이블 (final permutation table, FPT) 이용
#!/usr/bin/python3
# Name: des.py
# Initial/Final Permutation Table
IPT = [58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7]
FPT = [40, 8, 48, 16, 56, 24, 64, 32,
39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30,
37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28,
35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26,
33, 1, 41, 9, 49, 17, 57, 25]
def plain2bitstring(plain: str):
return "".join(format(ord(c), "0>8b") for c in plain)
def plain2bitarray(plain: str):
bitstring = plain2bitstring(plain)
encoded = bytearray([int(b) for b in bitstring])
return encoded
def bitarray2plain(bitarray: bytearray):
bitstring = bitarray2bitstring(bitarray)
encoded = "".join([chr(int(bitstring[i*8:i*8+8], 2))
for i in range(len(bitstring)//8)])
return encoded
def bitarray2bitstring(bitarray: bytearray):
return "".join([str(b) for b in bitarray])
def permutation(block: bytearray, table: list[int], outlen: int):
permutated = bytearray(outlen)
for n in range(len(table)):
m = table[n]-1
permutated[n] = block[m]
return permutated
plain = "DEScrypt"
key = "DREAMCRY"
bitarray = plain2bitarray(plain)
print(f"bitstring of '{plain}': {bitarray2bitstring(bitarray)}")
# Initial permutation
initial_permutated = permutation(bitarray, IPT, 64)
print(
f"bitstring of initial_permutated: {bitarray2bitstring(initial_permutated)}")
# Final permutation
final_permutated = permutation(initial_permutated, FPT, 64)
print(f"bitstring of final_permutated: {bitarray2bitstring(final_permutated)}")
# plain == FP(IP(plain)) => FP = IP^{-1}
print(f"plaintext of final_permutated: {bitarray2plain(final_permutated)}")// 이 과정을 파이썬 코드로 구현한 것
-step2. 라운드 함수
라운드 함수 F엔 오른쪽 블록만 입력됨. 입력 길이 32비트.
* 확장 순열 (expansion p-box)
* 라운드 키 결합 (XOR)
* 치환 테이블 (S-Box)
* 고정 순열 (Straight P-Box)
-step2.1. 확장 순열과 라운드 키 결합
확장 순열 : 입력을 비트 단위로 전치 & 전체 길이를 48비트로 확장 (4비트씩 8개로 나눈 후, 각 6비트로 확장)
: 테이블을 제외하곤 초기순열, 최종 순열과 같은 방식
라운드 키 결합 : 확장 순열로 나온 출력을 라운드 키와 xor 하는 것
#!/usr/bin/env python3
# Name: DES
# Expansion P-Box Table
EPT = [32, 1, 2, 3, 4, 5,
4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13,
12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21,
20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29,
28, 29, 30, 31, 32, 1]
#Initial permutation
...
# Feistel
left_half = initial_permutated[:32]
right_half = initial_permutated[32:]
# Iterates 16 rounds
for round in range(16):
# Expansion
expansioned = permutation(right_half, EPT, 48)
# XOR with round key
for bit_idx in range(48):
expansioned[bit_idx] ^= round_keys[round][bit_idx]
...
# Final permutation
...// 아직 키 생성 함수 정의하지 않았기 때문에 실행 불가
-step2.2 S-box와 고정 순열
S-Box(Substitution-Box) : 라운드 키 결합에서 출력된 48비트 결과 값을 32비트로 축소
4행 16열 표 사용. 각 값은 4비트로 표현된 수.
S-Box 적용되는 과정
1. 입력을 6비트씩 8 부분으로 나눈다
2. 6비트 중 처음과 마지막 비트로 '행'을 결정. 중간 비트들로 '열'을 결정
3. S-Box 표에서 행,열을 참고해 값 반환
(DES에선 여섯 비트로 자른 부분마다 다른 S-Box 사용)
* S-Box로 길이 축소하면, 고정 순열(straight p-box)로 비트 단위 전치 이뤄짐
#!/usr/bin/env python3
# Name: des.py
# S-Boxes
S = [
# S1
[
[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],
[0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],
[4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],
[15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]
],
...
# S8
[
[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7],
[1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2],
[7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8],
[2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11],
]
]
# Straight P-Box Table
SPT = [16, 7, 20, 21, 29, 12, 28, 17,
1, 15, 23, 26, 5, 18, 31, 10,
2, 8, 24, 14, 32, 27, 3, 9,
19, 13, 30, 6, 22, 11, 4, 25]
def substitution(block, table):
row = (block[0] << 1) + block[5]
column = (block[1] << 3) + (block[2] << 2) + (block[3] << 1) + block[4]
val = table[row][column]
binary = bin(val)[2:].zfill(4)
return bytearray([int(b) for b in binary])
#Initial Permutation
...
# Feistel
...
# Iterate 16 rounds
for i in range(16):
# Expansion
expansioned = permutation(right_half, EPT, 48)
# XOR with round key
for j in range(48):
expansioned[j] ^= round_keys[i][j]
# Substitution
substituted = bytearray(32)
for block_idx in range(8):
substituted[4*block_idx:4*block_idx+4] = substitution(expansioned[6*block_idx:6*block_idx+6], S[block_idx])
# Straight
straighted = permutation(substituted, SPT, 32)
...
# Final Permutation
...
-키 생성 함수
키 생성 함수 (key scheduling) : 64비트 입력 값으로 48비트 라운드 키를 생성하는 함수
구성
* 패리티 비트 제거 (parity bit drop)
* 쉬프트 (shift)
* 압축 순열 (compression p-box)
패리티 비트 제거
: 입력에서 패리티 비트 제거하고, 남은 56비트에 순열 적용
DES 비밀키에서 바이트들의 가장 오른쪽 비트는 나머지 7비트에 대한 홀수 패리티 비트(Odd Parity Bit)
홀수 패리티 비트
: 한 바이트를 이진수로 표현했을 때, 1의 수가 홀수가 되도록 덧붙인 비트
패리티 비트 역할 : 통신 중에 비트 반전이 일어나지 않았음을 보증. 패리티 비트를 확인하고 손상되지 않은 데이터를 얻기 위해 재전송을 요구할 수 있음
쉬프트
: 입력을 왼쪽, 오른쪽 각 28비트로 나눠 1이나 2비트 만큼 왼쪽으로 순환 쉬프트(cycle shift)
압축순열
: 56비트 입력을 48비트 길이로 압축
-키 생성 함수 구현
#!/usr/bin/env python3
# Name: des.py
# Parity Bit Drop Table
PBDT = [57, 49, 41, 33, 25, 17, 9,
1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27,
19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15,
7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29,
21, 13, 5, 28, 20, 12, 4]
# Compression P-Box Table
CPBT = [14, 17, 11, 24, 1, 5, 3, 28,
15, 6, 21, 10, 23, 19, 12, 4,
26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40,
51, 45, 33, 48, 44, 49, 39, 56,
34, 53, 46, 42, 50, 36, 29, 32]
...
def key_scheduling(key: bytearray):
shift_1 = [0, 1, 8, 15]
round_keys = []
# Drop parity bit
parity_erased = permutation(key, PBDT, 56)
left = parity_erased[:28]
right = parity_erased[28:]
# Shift
for i in range(16):
if i in shift_1:
left = left[1:] + left[0:1]
right = right[1:] + right[0:1]
else:
left = left[2:] + left[:2]
right = right[2:] + right[:2]
# Compression
round_keys.append(permutation(left+right, CPBT, 48))
return round_keys
...
key = "DreamCry"
key_bitarray = plain_to_bits(key)
# Key scheduling
round_keys = key_scheduling(key_bitarray)
4. DES의 응용
-다중 DES
시간이 지나면서 DES는 안전한 암호 시스템이라고 볼 수 없게 됐다.
다중 DES : 서로 다른 키를 사용하는 DES 모듈을 여러개 이어붙임. (이중DES : DES두겹112비트, 삼중 : 169비트 키 사용)
평문, c 암호문
이중 DES : E_{k_2}(E_{k_1}(p)) = c
삼중 DES : E_{k_3}(D_{k_2}(E_{k_1}(p))) = c
삼중 DES에서 중간에 복호화를 하는 이유는 k_2 = k_3로 설정하면, E_{k3}와 D_{k2}가 상쇄되어 키가 k_1인 단일 DES로도 사용할 수 있기 때문.
그러나, 이중 삼중 DES도 중간 일치 공격 으로 인해 안전성을 많이 확보할 수 는 없다.
중간 일치 공격
: 공격자가 어떤 평문 p와, p를 암호화한 암호문 c를 알 수 있을 때, 수행할 수 있는 공격
1. 56비트 키 공간(k)에서 모든 키k1으로 p를 암호화해 집합 S1 생성 S1={Ek1(p)∣k1∈K}
2. K에서 가능한 모든 키 k2로 c 복호화해서 집합 S2 생성 S2={Dk2(c)∣k2∈K}
3. S1 원소들과 S2 원소들에 대해 를 만족하는 k_1, k_2의 쌍으로 후보키의 집합 CK를 생성 CK={(k1,k2)∣Ek1(p)=Dk2(c),Ek1(p)∈S1,Dk2(c)∈S2}
4. 다른 평문 p'과 p'을 암호화한 암호문 c'을 생성
5. CK의 모든 원소에 대해 E_{k_1}(p')=D_{k_2}(c')을 만족하는 k_1과 k_2의 쌍으로 집합 CK를 갱신
6. CK의 원소가 하나가 될 때까지 4와 5의 과정 반복
5. 마치며
-마치며
퀴즈 : 16, 56,X