16 라운드 : Initial Permtation(IP) 초기순열 → Final Permutation(FP) 최종 순열 → Feistel 페이스텔
각 라운드 : 48비트의 키를 생성하는 키 생성 함수
DES의 원리
혼돈 성질 > Substitution(치환)확산 성질 > Permutation(순열)Product Cipher (곱 암호) : 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호
페이스텔 구조
평문 : \(P\) 각 라운드에서 생성된 키 : \(K\) 라운드 함수 : \(F\)
- 입력으로 들어온 블록을 동일한 길이의 왼쪽 블록 \(L\)과 오른쪽 블록 \(R\)로 나눈다 $$ L_0 = P[:len(P)/2], R_0 = P [len(P)/2 :]$$
- 각 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력됨 $$ L_{n+1} = R_n $$
- 왼쪽 블록은 오른쪽 블록에 라운드 함수 \(F\)를 적용한 결과와 XOR되어 다음 라운드의 오른쪽 블록으로 입력됨 $$R_{n+1} = L_n \bigoplus F(R_n, K) $$
* 비페이스텔 암호와 같은 안전성을 갖기 위해 두 배 정도 라운드를 사용해야함
DES의 과정
# STEP 1 : Initial Permutation(IP) 초기순열
64비트 입력을 비트 단위로 전치Initial Permutation Table(IPT) 초기 순열 테이블 > n번째 값이 m일 때 출력의 n번째 비트는 입력의 m번째 비트가 됨ex) IPT[1] = 58 > 58번째 비트가 제일 첫번째로 출력
▶DES를 하드웨어에 구현하기 쉽게 해줌
# STEP 2 : 라운드 함수 \(F\)
Expansion P-Box(확장 순열) → XOR(라운드 키 결합) → S-Box(치환 테이블) → Straight P-Box(고정 순열)
1) Expansion P-Box(확장 순열)
- 입력을 비트 단위로 전치
- 전체 길이를 48비트로 확장
- Expansion P-Box Table을 참고하여 4비트 단위를 6비트로 확장함
2) XOR(라운드 키 결합)
- 확장 순열로 나온 출력을 라운드 키 \(K\)와 xor함
3) S-Box(치환 테이블)
규칙 1 > 1, 6번째 비트를 붙여 10진수로 나타냄 → 0~3의 숫자 : 행 결정
규칙 2 > 2, 5번째 비트로 열을 결정해서 값을 반환
- 48비트 결과 값을 32비트로 축소
- 4개의 행과 16개의 열로 이루어진 표 사용
- 6비트씩 나눔 → 첫번째, 마지막 비트로 행 결정 → 나머지 네 개의 비트로 열 결정 → 행과 열을 참조하여 값 반환
4) Straight P-Box(고정 순열)
- 비트 단위 전치가 이루어짐
# STEP 3 : Final Permutation(FP) 최종 순열
64비트 입력을 비트 단위로 전치
Final Permutation Table(FPT) 초기 순열 테이블 > n번째 값이 m일 때 출력의 n번째 비트는 입력의 m번째 비트가 됨
▶DES를 하드웨어에 구현하기 쉽게 해줌
키 생성 함수
64비트의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수
Parity Bit Drop (패리티 비트 제거)
입력에서 패리티 비트를 제거하고 남은 56비트에순열 적용
DES 비밀키에서 각 바이트의 가장 오른쪽 비트 : 홀수 패리티 비트
Shift (쉬프트)
입력을 왼쪽 28비트와 오른쪽 28비트로 나누어 각각을 1, 2비트 왼쪽으로 순환 쉬프트 하는 과정
Compression P-Box (압축 순열)
56비트의 입력을 48 비트 길이로 압축하는 과정
다중 DES
서로 다른 키를사용하는 DES 모듈을 여러개 이어 붙여 DES의 약점을 보완함 암호 시스템
▶ Double DES (2-DES) > 112비트 키 사용
$$ E_{k_2}(E_{k_1}(p)) = c $$
▶ Triple DES (3-DES) > 168비트 키 사용
$$ E_{k_3}(D_{k_2}(E_{k_1}(p))) = c$$
* 복호화를 하는 이유 : \(k_2 = k_3\) 이면 상쇄되기 때문
중간 일치 공격
중간 일치 공격(Meet-in-the-middle Attack)으로 인해 안전성을 획기적으로 높이지는 못함
공격자가 어떤 평문 \(p\)와, \(p\)를 암호화 한 암호문 \(c\)를 알 수 있을 때 수행할 수 있는 공격
- 56비트 키 공간 \(K\)에서 가능한 모든 키 \(k_1\)으로 \(p\)를 암호화하여 집합 \(S_1\)을 생성 $$S_1 = \{D_{K_1}(c)|k_1 \in K\} $$
- \(K\)에서 가능한 모든 키 \(k_2\)로 \(c\)를 복호화하여 집합 \(S_2\)를 생성 $$ S_2 = \{D_{k_2}(c)|k_2 \in K\} $$
- \(S_1\)의 모든 원소와 \(S_2\)의 모든 원소에 대해 E_{k_1}(p) = D_{k_2}(c)를 만족하는 \(k_1\), \(k_2\)의 쌍으로 후보키의 집합 \(CK\)를 생성 $$ CK = \{(k_1,k_2)|E_{k_1}(p) = D_{k_2}(c), E_{k_1}(p) \in S_1, E_{k_2} \in S_2\} $$
- 다른 평문 \(p'\)과 이를 암호화한 암호문 \(c'\)을 생성
- \(CK\)의 모든 원소에 대해 \(E_{k_1}(p') = D_{k_2}(c')\)을 만족하는 \(k_1\)과 \(k_2\)의 쌍으로 집합 \(CK\)를 갱신 $$ CK = \{(k_1,k_2)|E_{k_1}(p') = D_{k_2}(c'), (k_1, k_2) \in CK\} $$
- \(CK\)의 원소가 하나가 될 때까지 4, 5를 반복
reference
- Dreamhack Cryptography> 블록암호 : DES
'Hacking > Cryptography' 카테고리의 다른 글
[키 교환] Diffie-Hellman Algorithm (1) | 2024.02.12 |
---|---|
[블록 암호] 운영모드 (0) | 2024.02.12 |
[블록 암호] AES (1) | 2024.02.11 |
현대 암호 (0) | 2024.02.09 |
고전 암호 (0) | 2024.02.09 |