본문으로 건너뛰기

4장. 블록 암호와 DES

DES(Data Encryption Standard)는 AES 도입 전까지 가장 널리 사용된 대칭 암호 알고리즘이다. DES의 구조를 이해하면 다른 대칭 암호의 원리도 파악할 수 있다. 이 장에서는 블록 암호의 일반적 구조와 DES의 동작, 설계 원칙을 다룬다.

학습 목표

  • 스트림 암호와 블록 암호의 차이를 이해한다.
  • Feistel 암호 구조와 복호화가 암호화의 역과정임을 설명한다.
  • DES의 전체적인 구조를 설명한다.
  • 눈사태 효과(Avalanche Effect)의 개념을 이해한다.
  • DES의 암호학적 강도를 논의한다.
  • 블록 암호의 주요 설계 원칙을 요약한다.

4.1 전통적 블록 암호 구조​

스트림 암호 vs 블록 암호​

구분스트림 암호 (Stream Cipher)블록 암호 (Block Cipher)
처리 단위1비트 또는 1바이트고정 크기 블록 (64 또는 128비트)
키스트림키 기반 비트 스트림 생성기 사용블록 단위 변환
예시Autokey Vigenère, VernamDES, AES
활용특수 목적네트워크 기반 응용에서 주류

이상적 블록 암호의 한계​

nn비트 블록 암호에서 가능한 가역 매핑(reversible mapping) 수는 2n!2^n!이다. 이상적 블록 암호는 이 모든 매핑을 허용하지만, 키 크기가 n×2nn \times 2^n 비트로 실용적이지 않다.

예시: 64비트 블록의 경우 필요한 키 길이 = 64×264=270≈102164 \times 2^{64} = 2^{70} \approx 10^{21} 비트

확산과 혼돈 (Diffusion and Confusion)​

Claude Shannon이 제안한 암호 시스템의 두 가지 기본 요소이다.

개념목적구현 방법
확산 (Diffusion)평문의 통계적 구조를 암호문 전체에 분산순열(Permutation) 반복 적용
혼돈 (Confusion)암호문과 키 간의 관계를 복잡하게 만듦복잡한 치환(Substitution) 알고리즘

Feistel 암호 구조​

Feistel은 곱 암호(Product Cipher) 개념을 이용하여 치환과 순열을 교대로 수행하는 실용적인 블록 암호를 제안했다.

암호화 과정​

  1. 2w2w비트 평문을 두 반쪽 LE0LE_0, RE0RE_0으로 분할
  2. nn라운드 반복 처리 (일반적으로 16라운드)
  3. 각 라운드 ii에서:

LEi=REi−1LE_i = RE_{i-1} REi=LEi−1⊕F(REi−1,  Ki)RE_i = LE_{i-1} \oplus F(RE_{i-1},\; K_i)

  1. 최종 출력에서 좌우 반쪽 교환 → 암호문

복호화 과정​

암호화와 동일한 알고리즘을 사용하되, 서브키를 역순으로 적용한다.

REi−1=LEiRE_{i-1} = LE_i LEi−1=REi⊕F(LEi,  Ki)LE_{i-1} = RE_i \oplus F(LE_i,\; K_i)

XOR의 성질 ([A⊕B]⊕B=A[A \oplus B] \oplus B = A)에 의해 복호화가 성립한다. 라운드 함수 FF가 가역일 필요는 없다.

Feistel 암호의 설계 매개변수​

매개변수설명일반적 값
블록 크기클수록 안전하지만 속도 저하64비트 (전통), 128비트 (AES)
키 크기클수록 무차별 대입에 강함128비트 이상
라운드 수많을수록 안전16라운드
서브키 생성복잡할수록 분석 어려움—
라운드 함수 F복잡할수록 분석 어려움비선형 함수

4.2 DES (Data Encryption Standard)​

개요​

항목값
발표1977년, NIST (당시 NBS)
표준 번호FIPS PUB 46
블록 크기64비트
키 크기56비트 (실제 입력 64비트 중 8비트는 패리티)
라운드 수16
구조Feistel 암호

DES 암호화 과정​

  1. 초기 순열 (IP): 64비트 평문의 비트 재배열
  2. 16라운드 Feistel 처리: 각 라운드에서 48비트 서브키 KiK_i 사용
  3. 32비트 교환: 최종 라운드 후 좌우 반쪽 교환
  4. 역초기 순열 (IP⁻¹): 초기 순열의 역과정 → 64비트 암호문

서브키 생성​

  1. 64비트 키 → Permuted Choice 1 (56비트 선택)
  2. 각 라운드마다 좌순환 시프트(left circular shift) 수행
  3. Permuted Choice 2로 48비트 서브키 KiK_i 추출

DES 복호화​

Feistel 구조이므로 암호화와 동일한 알고리즘을 사용하되, 서브키를 K16,K15,…,K1K_{16}, K_{15}, \ldots, K_1 역순으로 적용한다.

4.3 DES 예제​

예제 데이터​

항목16진수 값
평문02468aceeca86420
키0f1571c947d9e859
암호문da02ce3a89ecac3b

초기 순열 후 L0=5a005a00L_0 = \texttt{5a005a00}, R0=3cf03c0fR_0 = \texttt{3cf03c0f}에서 시작하여 16라운드를 거쳐 최종 역초기 순열을 적용하면 암호문이 생성된다.

눈사태 효과 (Avalanche Effect)​

평문이나 키의 1비트 변화가 암호문의 다수 비트 변화를 유발하는 성질이다.

평문 1비트 변경 시:

  • 1라운드 후: 1비트 차이
  • 3라운드 후: 18비트 차이
  • 최종 암호문: 32비트 차이 (64비트 중 절반)

키 1비트 변경 시:

  • 3라운드 후: 25비트 차이
  • 최종 암호문: 30비트 차이

4.4 DES의 강도​

56비트 키의 문제​

공격 시스템탐색 속도DES (56비트) 해독 시간
단일 PC10910^9 키/초약 1.125년
슈퍼컴퓨터101310^{13} 키/초약 1시간

키 크기별 무차별 대입 공격 시간 비교​

키 크기암호10910^9 키/초101310^{13} 키/초
56비트DES약 1.125년약 1시간
128비트AES5.3×10215.3 \times 10^{21}년5.3×10175.3 \times 10^{17}년
168비트Triple DES5.8×10335.8 \times 10^{33}년5.8×10295.8 \times 10^{29}년
256비트AES1.8×10601.8 \times 10^{60}년1.8×10561.8 \times 10^{56}년

알고리즘 자체의 강도​

DES의 8개 S-box의 설계 기준이 공개되지 않아 의도적인 약점 삽입 여부에 대한 의혹이 있었으나, 치명적인 약점은 발견되지 않았다.

타이밍 공격 (Timing Attack)​

복호화 시간의 미세한 차이를 관찰하여 키 정보를 추론하는 공격이다. DES는 타이밍 공격에 비교적 강한 것으로 평가된다.

4.5 블록 암호 설계 원칙​

라운드 수 (Number of Rounds)​

라운드 수가 많을수록 암호 분석이 어려워진다. 설계 기준은 알려진 암호 분석 공격이 무차별 대입 공격보다 더 많은 연산량을 요구하도록 하는 것이다.

DES의 경우: 16라운드 DES의 차분 암호 분석(differential cryptanalysis)에 필요한 연산량은 255.12^{55.1}으로, 무차별 대입(2552^{55})과 비슷하다. 15라운드 이하에서는 차분 암호 분석이 무차별 대입보다 효율적이다.

라운드 함수 F의 설계​

기준설명
비선형성선형 방정식으로 근사하기 어려워야 함
엄격 눈사태 기준 (SAC)입력 1비트 반전 시 출력 각 비트가 확률 1/2로 변화
비트 독립 기준 (BIC)입력 1비트 반전 시 출력 비트들이 독립적으로 변화

키 스케줄 알고리즘​

서브키 생성 알고리즘은 개별 서브키의 추론과 전체 키로의 역추적을 최대한 어렵게 해야 한다. 최소한 키/암호문에 대해 SAC와 BIC를 보장해야 한다.

주요 용어​

한국어영어설명
눈사태 효과Avalanche Effect입력 1비트 변화가 출력 다수 비트에 영향
블록 암호Block Cipher고정 크기 블록 단위 암호화
혼돈Confusion암호문-키 관계의 복잡화
확산Diffusion평문 통계 구조의 분산
Feistel 암호Feistel Cipher치환/순열 교대 반복 구조
곱 암호Product Cipher둘 이상의 암호를 순차 적용
라운드 함수Round Function각 라운드에서 수행되는 함수 FF
서브키Subkey각 라운드에 사용되는 키
가역 매핑Reversible Mapping역변환이 가능한 매핑
S-박스S-boxDES의 치환 테이블
차분 암호 분석Differential Cryptanalysis입력 차이와 출력 차이의 관계를 이용한 공격
타이밍 공격Timing Attack연산 시간 차이를 이용한 공격