#4. 일회용 패드 & 블록 암호

 

 

 

1. 비트 연산 & 선형 함수 2. 일회용 패드 (One-Time Pad) 3. 블록 암호 (Block Cipher) 4. DES (Data Encryption Standard)

 

 

 

1. 비트 연산 & 선형함수

 

1) 비트 연산

 

비트열

- 0과 1로 표현된 수열

- 어떤 수 x가 n비트 <=> x는 0과 1이 n개로 이루어진 수

- 1비트: 비트열의 최소 단위

- 1바이트: 8-비트 비트열

 

컴퓨터는 모든 문자와 숫자를 비트열로 이해하고 처리함.

 

 

2) 배타적 논리합

 

XOR (exclusive or)

- ⊕로 표시

 

비트 단위 XOR 규칙

- 0 ⊕ 0 = 0

- 0 ⊕ 1 = 1

- 1 ⊕ 0 = 1

- 1 ⊕ 1 = 0

(즉, XOR는 mod2 연산과 같음)

 

비트열 XOR

- 비트열 x ⊕ 비트열 y

- 각 비트 단위로 XOR 연산을 수행

 

 

3) 배타적 논리합 성질

 

비트열 x, y 에 대해 일반적인 덧셈의 성질을 다 가짐 (교환, 결합, 항등원..)

 

자기 자신에 대한 ⊕는 0으로 이루어진 비트열이 된다.

- 즉, 덧셈에 대한 역원이 자기자신이다.

 

 

4) 바이트

 

Byte

- 8비트로 구성된 비트열 (10진수 0 ~ 255)

 

Byte와 16진수

- 주로 4비트 씩 끊어서 16진수로 쓴다.

- 16진수로 썼다는 것을 표시하기 위해 비트열 앞쪽에 0x를 붙인다. (자명한 경우 생략)

10진수	2진수	16진수
0	0000 0000	0x00
8	0000 1000	0x08
16	0001 0000	0x10
90	0101 1010	0x5A
255	1111 1111	0xFF

 

 

5) 선형과 비선형

선형 함수 (Linear Function) 함수 f: X-> Y가 임의의 x1, x2에 대해 f(x1 + x2) = f(x1) + f(x2)를 만족한다.

위에 해당하지 않는다면 f는 비선형 함수(non-linear function)이다.

 

ex. 행렬과 곱셈 연산, 바이트열과 XOR 연산

 

 

 

 

 

 

 

2.일회용 패드 (One - Time Pad)

 

- Vernam이 1917년 고안했다.

- 냉전시기 미국과 러시아 사이 hot line을 통한 통신 암호화에 사용

- 1940년대 Shannon에 의해 Perfect Secrecy를 가진다는 것이 증명됨.

 

1) 암호화

평문 비트열 p와 비트열 k의 XOR 연산

- c = p ⊕ k

 

키 비트열 k

- 평문 비트열 p와 같은 크기

 - Random 비트열

 

 

2) 복호화

XOR는 자기자신이 덧셈에 대한 역원

c = p ⊕ k 

=> p = c ⊕ k

 

 

3) Perfect Secrecy

어떠한 공격으로도 평문에 대한 정보를 얻는 것이 불가능하다.

- 암호화 키 k는 8 x 5 비트 숫자를 random하게 선택 - 임의의 단어 p에 대해서 유일한 키 k가 존재    k = c ⊕ p    => 어떠한 단어도 같은 확률로 올바른 평문일 수 있다.    => 암호문이 평문의 어떠한 정보도 포함하고 있지 않다. (암호문 자체가 그냥 random)

 

4) 장단점

장점

- 매우 안전하다

- 빠른 암/복호화 연산을 지원 (가장 간단한 연산 XOR만을 사용한다.)

 

단점

- 키 배송 및 보관 (앞으로 사용할 메시지 길이 만큼의 키를 사전에 공유해야 함)

- 키 재사용 불가

- 키 동기화 (sender와 receiver사이에 동기화가 어긋날 경우 복구할 방법 없음)

- 키 생성 (대량의 예측불가능한 random을 생성하는 것이 어려움)

 

 

 

 

3. 블록 암호

 

1) 비즈네르 암호

 

2) 힐 암호

: 비즈네르 암호에서 일대일 대응을 행렬 M 곱하기 바꾼 것이다.

https://yenas0.tistory.com/64

#3-1. 고전암호

 

위 글에서 비즈네르 암호화 힐 암호에 대해 설명해 두었다.

 

 

 

3) 블록 암호

 

비즈네르 암호 & 힐 암호

- 평문을 블록화

- 개별 블록에 대해 암호화

 

위와 같은 형태의 암호화 알고리즘 종류를 블록 암호라고 함.

 

 

 

4) 이상적인 블록 암호

 

블록 암호

- m - 비트 평문들의 집합에 대한 permutation으로 이해할 수 있음

 

이상적인 블록암호는 (2^m)!개 전체에서 암호화 키를 random 하게 뽑는 것

- 키를 표현하는데 필요한 비트 수 = log(2^m!) / log 2 > 2^m

- m = 40 -> 너무 크다

 

사용 블록 암호 permutation 전체 집합에서 극히 일부만을 사용

- DES, AES 등..

 

 

 

5) 현실적 & 안전한 블록 암호

 

Confusion

- 목적: 키와 암호문과의 관계 감추기

- 암호문의 각 자리(bit)가 키의 여러 부분(bits)들로부터 영향을 받게

- 키에서 1비트만 바뀌어도 암호문의 많은 부분들이 영향을 받음

 

Diffusion

- 목적: 평문와 암호문과의 관계 감추기

- 평문에서 1 비트만 바뀌어도 암호문의 반 정도가 영향을 받게

- 암호문에서 1비트만 바뀌어도 평문의 반 정도가 영향을 받게

 

 

 

6) 블록 암호 알고리즘 구조

 

블록별 암호화 구조

- Confusion과 Diffusion의결합으로 Round를 구성

- Round를 반복 (Iteration)

 

블록암호는 2개의 기본 구조를 가진다.

- Feistel Network

- Substitution - Permutation Network

 

 

 

 

 

4. DES

 

1) Feistel Network

 

Feistel system

- Horst Feistel

- IBM 암호팀의 멤버

- 암호 알고리즘 LUCIFER를 개발

 

Feistel network, Feistel structure, Feistel cipher 등으로 불림]

 

암호화의 기본 모듈(라운드)를 여러 번 반복해서 수행

평문 블록  ->  Round1  ->  ...  ->  Round n  ->  암호문 블록

 

 

 

 

2) Feistel  Network 입력부

-입력 평문을 반으로 나눈 후 각각에 대해 연산을 수행한다.

 

 

 

 

 

3) Feistel Network 암호화 및 복호화

 

복호화는 암호화와 같은 구조로 라운드키만 역순으로 입력하여 진행한다.

 

 

 

4) Feistel Network 특징

 

원하는 만큼 라운드 수를 늘릴 수 있다.

 

라운드 함수 F는 어떤 것을 써도 복호화가 된다.

- Feistel network 의 복호화는 F의 역함수를 몰라도 된다.

- 원하는 만큼 복잡한 F를 역함수 계산가능성 고려없이 만들면 됨

 

암호화 구조 = 복호화 구조

- 하드웨어 구현에 적합