[암호학] DES (Data Encryption Standard)

---

DES (Data Encryption Standard)

미국의 표준 암호 알고리즘
대칭키 암호로 암호화 및 복호화 키가 동일
블록 단위 암호화 / 복호화

---

DES의 개요

• 블록 크기 : 64비트
• 64비트 평문 블록 → 64비트 암호문 블록

평문 메시지를 64비트 블록 단위로 나눔 → 패딩과정 필요

• 암호화와 복호화에서 같은 키를 사용

64비트 키 선택하여 56비트만 이용한다 → 8, 16, 24, 32, 40, 48, 56, 64번째 비트 무시
라운드 수와 같은 수의 서브키(subkey) 생성하여 이용

• 라운드 (Round)

암호화 과정을 위한 최소 연산 단위
연산을 16회 사용함 → DES는 총 16라운드

---

DES 구조

1. 64비트 평문이 1라운드를 거치기전 IP(초기 전치)을 거침
 
2. IP를 거친 후 나온 64비트 값이 각 32비트로 나누어짐
3. 키 스케줄로 나온 48비트 키 K와 32비트 R이 F 함수에 input이고 32비트 output이 나옴
4. f 함수 32비트 output이랑 32비트 L을 XOR
 
5. 마지막 라운드 종료 후 역전치 후 64비트 암호문이 만들어짐
 
* 2, 3, 4 단계를 총 16라운드까지 반복

---

 

초기 전치 (Initial Permutaion; IP)

• 1라운드 시작 전에 초기 전치 수행
• 초기 전치와 최종 전치는 안전성과 관련 없음

입력 평문 블록 64bit 들의 위치를 표와 같이 바꿈

---

DES - f 함수

F function

• 각 라운드마다 오른쪽 R의 32비트가 E(확대 전치)를 거쳐 48비트로 확장
• 확장된 R 48비트와 서브키를 XOR
• XOR로 얻은 48비트는 6비트씩 8부분으로 나뉘어 S-Box에 들어감
• S-Box의 output은 4비트로 8부분을 모두 합쳐 32비트로 도출
• 32비트는 P(평형 전치)를 거쳐 나열
• P(평형 전치)를 거쳐나온 32비트는 L과 XOR
• f 함수 완료

---

f 함수 - 확대 전치 E (Expansion Permutation)

32bit R을 48비트로 확장
R을 서브키와 같은 크기로 만들어 서브키와 XOR

---

f 함수 - S-Box (S-Box Substitution)

8개의 S-Box에 의해 치환 수행
확대 전치의 결과 48비트를 6비트씩 묶어 8개를 만든 후 8개의 S-box에 입력
6비트의 입력을 받아 S-Box는 4비트를 출력

• 각 S-Box는 4행 16열로 구성됨 → 각 구성요소의 값은 4비트로 표현 가능한 수 (10진수로 0~15까지)
• 입력의 6bit로 출력의 행과 열을 정의

→ S-Box의 입력 6bit가 2진수로

이면 
 

 
ex) S6의 입력 110011 (2) 의 출력은?
 
행 : 11 (2)  → 3
열 : 1101 (2) → 9
S6의 3번행 9번 열의 값 → 14 = 1110 (2)
110011의 S6-Box 출력은 1110

---

키 스케줄 (Key Schedule)

각 라운드에서 사용될 서브키(라운드키)를 생성하는 알고리즘

사용자는 64비트 암호화/복호키 지정

• 알고리즘에서 8비트를 제외한 56비트를 키 K로 사용함
• 키 K를 바탕으로 f-함수에서 사용되는 서브키(라운드키) K를 생성함
• 각 라운드마다 다른 서브키 K를 생성하는 것이 목적

Rotation(순환 시프트), 축약전치를 연산자로 사용

축약전치 - 8비트는 사라지고 48비트까지 출력됨

Rotation의 양

---

DES의 복호 (Decryption)

암호화 알고리즘을 그대로 사용함

• 별도의 복호 알고리즘 필요 없음

암호화 과정의 반대 순서로 서브키 입력

---

DES의 규칙성

• 보수 특성

• 취약키 (Weak Key)

• 초기키를 이용하여 서브키를 만들 때, 안전성이 취약한 키가 존재할 수 있음
• 서브키가 모두 같은 형태의 계열
• 암호화를 2번 하면 평문이 드러남

 

---

DES의 안전성

키의 소모적 공격

• 안전성 평가할 때 키의 길이가 중요
• 키의 소모적 공격 = 전수공격

• 공격자는 (암호문, 평문)의 쌍을 알고 있다고 가정
• 암호기에 평문 입력 후 모든 키를 차례로 입력
• 알고 있는 암호문이 나올 때 까지 반복하여 키를 알아냄

2중 DES의 사용

• 서로 다른 키로 DES를 반복 적용하면 안전성 향상될 것으로 예측 → 안전성 향상 안되었음

3중 DES (Triple DES)

• 키의 길이가 2배 확대된 효과 → 안전성 향상

평문P를 Key K1을 가지고 암호화 한 것을 K2로 복호화하고 K1으로 암호화 하면 암호문이 나옴

S-Box의 선택

• 안전한 비선형적 S-box이 선택이 중요함

---

DES에 대한 공격

블록 암호에 대한 공격

• 공격의 목적은 키의 발견
• 전수 공격보다 효율적인 공격을 서공적인 공격이라고 함

차분 분석 (Differential Cryptanalysis)

• 선택 평문 공격
• 입력 차분(input difference)이 어떤 출력 차분(output difference)으로 높은 확률로 전파되는지 검색
• 라운드 수를 늘임으로써 공격에 대해 대응

선형 분석 (Linear Cryptanalysis)

• 기지 평문 공격 (Known-plaintext attack)
• 입력의 특정 비트들의 XOR 값, 출력의 특정 비트들의 XOR값을 이용하여 키 추정
• 라운드 수를 늘리고 S-Box 설계 시 선형 확률이 작아지는 함수 이용하여 공격에 대해 대응 (비선형성 설계)