S-DES
S-DES 암호화 과정
- 입력: 8비트
- 출력: 8비트
- IP(초기 순열)과 IP^-1(역 초기 순열)
P8
6 3 7 4 8 5 10 9 (i)
1 2 3 4 5 6 7 8 (j)
출력 비트의 i번째 수는 입력 비트의 j번째 수이다.
함수 fk
- 전치(Transposition)과 치환(Substitution) 연산 수행
- 입력: 8비트 워드
- L (Left most 4 bits)
- R (Right most 4 bits)
- 처리 방법
- 여기서 SK는 Sub Key로써, K1 or K2
E/P(Expansion/Permutation)
- 입력: 4비트
- 출력: 8비트
- P4
S-DES 분석
- 전수조사(Brute force)공격 가능
- 10비트 키로 단지 2^10 = 1024가지의 가능성이 존재하므로 전수조사 공격이 충분히 가능함
- 기지 평문 공격 가능
- 10개의 미지수(키)를 갖는 8개의 비선형 방정식(p, c)으로 나타낼 수 있어 기지 평문 공격 (= 단일 평문과 그 출력 암호문이 알려져 있을 때 사용하는 공격)이 가능함
-> 키 개수 제한되어 있기 때문에 가능함
cf) 선형 방정식: 선형 조합으로 나타낼 수 있는 방정식
현대 블록 암호의 구성 요소
- 현대 블록 암호는 확산과 혼돈과 같은 성질을 만족시키기 위해 이를 결합해 설계
- 전치 요소(P-박스)
- 대치 요소(S-박스)
- 그 밖의 구성 요소들(XOR, Shift, Swap 등)
P-박스(P-box)
- P-박스란?
- 문자 단위로 수행했던 고전 전치 암호를 비트 단위로 수행
- 세 종류의 P-박스가 존재
- 단순(Straight) P-박스
- 확장(Expansion) P-박스
- 축소(Compression) P-박스
단순 P-박스
- n비트 길이의 워드를 입력 받아 n비트 길이의 워드를 출력하는 치환(Permutation) 함수
- n개의 비트에 대해 치환 수행
- 따라서, n비트 워드에 대해 n! 경우 대응(mapping)이 존재
- 예제)
p박스 개수(출력의 비트 수)와 n값(입력 길이)이 동일하면 단순 p박스
- 단순 p박스 -> 중복x
축소 P-박스
- n비트 길이의 워드를 입력 받아 m비트 길이의 워드(n > m)를 출력하는 P-박스
- 입력 비트 중 특정 비트는 소실
- 키가 사용되지 않으며 비트를 전치하기 위한 규칙으느 치환 테이블로 정의
확장 P-박스
- n비트 길이의 워드를 입력 받아 m비트 길이 (n<m)의 워드를 출력하는 P-박스
- 특정 입력 비트는 한 개 이상의 출력 비트와 연결
- 키가 사용되지 않으며 전치 비트에 대한 규칙은 치환 테이블로 정의
- 확장 P-박스에 대한 테이블은 m개의 성분을 가지며 m-n개의 성분을 반복적으로 사용
P-박스의 역함수 존재성
- 단순 P-박스는 입력 워드와 출력 워드이 비트 간의 관계가 일대일 대응이므로 역함수가 존재함
- 그러나, 축소 P-박스와 확장 P-박스는 일대일 대응이 아니므로 역함수가 존재하지 않음
- 예제) 1차원의 테이블로 표현된 치환 테이블의 역 구성 방법
- 역함수가 존재하지 않는 축소 P-박스와 확장 P-박스
S-박스 (S-Box)
- S-박스란?
- P-박스가 전치 암호라면, S-박스는 대치 암호를 나타냄
- S-박스는 입력과 출력의 개수가 달라도 됨
- S-박스는 mxn 대치 단위로 정의되며, 이 때 m과 n이 반드시 같을 필요는 없음
- 예제1) 3비트 워드를 입력받아 2비트 워드를 출력하는 S-박스
- 예제2) 3비트 워드를 입력받아 2비트 워드를 출력하는 S-박스
- 예제3) 3x2의 S-박스에 대한 입출력 관계식 정의
S-박스의 역함수 존재성
- S-박스는 입력 값과 출력 값 사이의 관계가 테이블 혹은 수학적 관계로 정의되는 대치암호
- S-박스는 역함수가 존재할 수도 있고, 존재하지 않을 수도 있음
- 이때, 역함수가 존재하는 S-박스는 입력 비트와 출력 비트의 개수가 동일해야 함
배타적 논리합 (Exclusive - OR)
- 현대 블록 암호에서 중요한 구성요소
- 체 GF(2^n)상에서의 덧셈과 뺄셈 연산은 배타적 논리합(XOR)으로 부리는 단인 연산에 의해 수행됨
암호화 단계 -> 배타적 논리합 연산
복호화 단계 -> 배타적 논리합의 역 연산
순환 이동 (Circular Shift)
- n비트 워드의 각 비트 내용을 왼쪽 또는 오른쪽으로 k비트씩 이동(shift)시키는 연산
