Week 2 - 대칭 암호화

주로 기밀성을 제공하기 위해 가장 널리 쓰이는 기법은 대칭 암호화 기법이다.

1️⃣ 대칭 암호화 기법

전통적인 암호화 기법 또는 싱글키 암호화 기법으로도 일컬어진다. 대칭 암호화 기법(symmentric encryption)은 1970년대 후반 공개키 암호화 기법의 등장 이전에 사용되던 유일한 암호화 기법이다.

송신된 데이터나 저장된 데이터에 기밀성을 제공하기 위한 가장 일반적인 기법이다.

🔍 대칭 암호화 기법의 다섯 가지 요소

평문(plaintext): 암호화 알고리즘의 입력 값.

원래의 메세지나 데이터이다.

암호화 알고리즘(encryption algorithm): 평문에 대해 다양한 치환 작업과 변환 작업 수행.

비밀키(secret key): 암호화 알고리즘의 입력 값.

알고리즘에 의해 수행되는 정확한 치환과 변형이 여기에 달려 있다.

암호문(cipher text): 출력 데이터로 생성된 암호회된 메세지.

평문과 비밀키에 따라 달라진다. 두 개의 다른 키는 두 개의 다른 암호문을 생성한다.

복호화 알고리즘(decryption algorithm): 암호화 알고리즘과 같지만 정반대로 진행.

암호문과 비밀키를 가지고 원래의 평문을 생성한다.

대칭 암호화 기법의 안전한 사용을 위한 두 가지 요구사항:

강력한 암호화 알고리즘

최소한 알고리즘을 알고 있고 하나 혹은 그 이상의 암호문에 접근하는 상대가 암호문을 해독할 수 없거나 키를 알아낼 수 없기를 원한다.

메세지의 송신자와 수신자는 안전한 방식으로 비밀키의 복사본을 얻고 잘 보관해야 한다.

🔍 대칭 암호화 구조 공격

1. 암호 해독 (cryptanalysis)

알고리즘의 특성 (알고리즘의 약점을 이용함)

평문의 일반적인 특징 (특정한 패턴이나 통계적 특정을 가짐)

몇 개의 평문-암호문 쌍의 샘플

이 공격 유형은 특정 평문을 추정하거나 사용되고 있는 키를 추정하기 위해 알고리즘의 특성을 이용한다.

2. 무차별 대입 공격 (brute-force attack)

하나의 암호문에 대해 이해할 수 있는 평문으로 전환될 때까지 가능한 모든 키를 대입, 공격자는 평균적으로 번의 시도 끝에 실제 키를 찾아낼 수 있다.

대칭 암호화 알고리즘에서 가장 많이 쓰이는 것은 블록 암호화다. 블록 암호화 기법은 평문 입력을 고정된 크기의 블록으로 처리하고 각각의 평문 블록의 길이와 같은 크기의 암호문을 만들어낸다.

이 알고리즘은 길이가 더 긴 평문은 고정된 크기의 연속된 블록으로 처리한다.

가장 널리 사용되는 암호화 구조는 DES(Data Encryption Algorithm)이다. DES는 64비트의 평문 블록과 56비트의 키를 이용해 64비트의 암호화 블록을 만든다.

DES는 알고리즘 자체에 대한 우려와 56비트 사용에 대한 우려가 존재한다.

2️⃣ DES

🔍 암호 시스템

암호(cryptography) 시스템은 일반적으로 세 가지 독립적 차원에 따라 분류된다.

평문을 암호문으로 변환하는 데 사용되는 운영의 유형.

모든 암호화 알고리즘은 두 가지 일반 원칙에 기반한다.

대치(substitution): 평문의 각 원소(비트, 글자, 비트 또는 글자들의 모임)가 다른 원소로 사상된다.

치환(transposition): 평문의 원소들의 재배열된다.

근본적으로, 어떤 정보도 손실되어도 안 된다.

사용되는 키의 개수.

송신자와 수신자가 모두 같은 키를 사용하면 대칭, 단일키, 비밀키, 관용 암호라 부른다.

아니라면 비대칭, 두 개의 키, 혹은 공캐기 암호라 부른다.

평문이 처리되는 방법.

블록 사이퍼(block cipher): 한 번에 원소들의 한 블록을 입력으로 처리하고 각 입력 블록에 대해 출력 블록을 산출한다.

스트림 사이퍼(stream cipher): 입력 원소들을 연속적으로 처리하고, 진행함에 따라 한 번에 하나의 출력을 산출한다.

암호화 알고리즘은 그것에 의해 만들어진 암호문이 다음 두 가지 기준 중 하나를 만족하면 계산적으로 안전하다.

사이퍼를 깨뜨리는 데 드는 비용이 암호화된 정보의 가치를 초과

사이퍼를 깨뜨리는 데 드는 시간이 정보의 유용한 수명 초과

🔍 파이스텔 사이퍼(Feistal cipher) 구조

파이스텔 사이퍼 구조(Feistel Cipher Structure)는 대칭키 블록 암호 알고리즘에서 사용되는 기본 구조 중 하나로, DES(Data Encryption Standard)와 같은 고전적인 암호화 알고리즘에 사용된다. 1973년에 IBM의 호레이스 파이스텔(Horst Feistel)에 의해 제안되었으며, 라운드 기반 암호화 방식을 사용한다. 여기서 라운드란 암호화 과정의 반복적인 단계로, 각 라운드에서 입력 데이터를 변환하는 일련의 연산이 수행된다.

블록 크기: 블록 크기가 클수록 더 높은 안정성을 의미하나 암호화/복호화 속도를 떨어뜨린다.

키 크기: 키가 크면 더 높은 안정성을 의미하나 암호화/복호화 속도를 떨어뜨린다.

라운드 수: 대칭 블록 사이퍼의 본질은 한 라운드만으로는 안전성이 불완전하며, 다중 라운드가 더 높은 안전성을 제공한다는 점이다.

부분 키 생성 알고리즘: 알고리즘의 복잡도가 클수록 분석이 더 어려워진다.

라운드 함수: 복잡도가 클수록 암호 분석의 저항성이 커진다.

💡 파이스텔 사이퍼 구조의 주요 특징

파이스텔 구조는 블록 암호화 알고리즘에 적용되며, 입력 블록을 두 부분으로 나누고, 여러 라운드를 거치며 데이터를 암호화한다. 암호화와 복호화 과정이 거의 동일한 구조를 따르지만 라운드 키의 순서만 다르게 적용되는 점이 큰 장점이다.

1. 블록 분할

암호화할 데이터 블록을 두 부분으로 나눈다. 보통 왼쪽 절반(L)과 오른쪽 절반(R)으로 나눈다.

2. 라운드 함수

파이스텔 구조에서는 각 라운드마다 라운드 함수(F)가 사용된다. 이 함수는 데이터의 오른쪽 절반(R)을 입력으로 받고, 해당 라운드에 해당하는 서브키를 적용하여 연산을 수행한다. 그 결과를 왼쪽 절반(L)과 XOR 연산하여 새로운 값을 만든다.

라운드 함수(F)는 암호화 과정에서 비선형성을 추가하고, 복잡한 변환을 수행하는 부분이다. 이 함수는 암호 알고리즘마다 다르며, 복잡한 수학적 연산이나 혼합을 포함할 수 있다.

3. XOR 연산

각 라운드에서 오른쪽 절반에 라운드 함수를 적용하고, 그 결과를 왼쪽 절반과 XOR 연산한다. XOR 연산은 대칭적이어서 복호화할 때도 동일한 방식으로 처리할 수 있다.

4. 좌우 교환

라운드가 끝날 때마다 왼쪽과 오른쪽을 교환한다. 이 과정을 여러 라운드 반복하게 되면, 왼쪽과 오른쪽 절반이 서로 뒤섞여 복잡한 암호문을 생성한다.

5. 복호화 과정

파이스텔 구조에서 복호화는 암호화 과정의 역순으로 수행되지만, 중요한 점은 암호화와 동일한 구조를 사용한다는 것이다. 복호화 시에는 라운드 키의 적용 순서만 반대로 해주면 된다.

📌 파이스텔 보조키 생성 예시

Feistel 보조키 생성 과정에 대한 더 자세한 설명은 다음과 같다:

1️⃣ Error 정정 비트 설정:

보조키 생성을 시작할 때, 초기 비트 배열이 설정된다. 이 배열은 보조키 생성의 기초가 되는 값으로 사용된다. 예를 들어:


0100111 0011011 1101110 1000110 0101011 1000001 1000010 1100100

이러한 비트 배열은 Feistel 구조에서 암호화 및 복호화 작업에 필요한 초기 값을 제공한다.

2️⃣ 전치(퍼뮤테이션) - Permutation Choice 1 (PC-1):

Permutation Choice 1, 또는 PC-1 전치는 초기 비트 배열에서 특정 비트들을 선택하고 그 위치를 재배열하는 과정이다. 이 과정은 보안성을 높이기 위해 원본 키에서 비트를 무작위로 섞어준다. 예를 들어, 57번째 비트를 첫 번째 자리에, 49번째 비트를 두 번째 자리에 위치시킨다는 의미다. PC-1 전치의 결과는 새로운 비트 배열을 생성하여 다음 단계로 넘기게 된다.

Left (좌측): 1110110 0100101 0100000 0100001 (28비트)

Right (우측): 0011001 1010111 1110000 1010110 (28비트)

3️⃣ 좌측 순환 이동 (Left Circular Shift):

PC-1 전치 후, 비트 배열을 좌측으로 순환 이동시키는 과정을 거친다. 좌측 순환 이동은 일정한 비트 수 만큼 배열을 왼쪽으로 이동시켜 새로운 배열을 만든다. 예시를 보면:

순환 이동 전: 1110110 0100101 0100000 0100001

순환 이동 후: 1101100 1001010 1000000 1000011

이 과정은 보조키의 무작위성을 증가시켜 암호화 과정을 더욱 안전하게 만든다.

4️⃣ Permutation Choice 2 (PC-2 전치):

Permutation Choice 2, 또는 PC-2 전치는 PC-1 전치와 유사하게 새로운 비트 배열에서 선택된 비트들의 위치를 재배열하는 과정이다. PC-2 전치의 결과는 최종적으로 사용할 보조키를 생성하는 데 사용된다. 이 과정을 통해 16개의 보조키가 생성되며, 각각의 보조키는 Feistel 구조의 16개 라운드에서 사용된다. 각 라운드에서 서로 다른 보조키를 사용함으로써 암호화의 복잡성과 보안성을 극대화한다.


10100111 01011000 11010110 01110011 01010101 11001100 10111010

이런 56비트가 생성되었다고 하고, 위 사진과 같은 패턴을 따른다고 하자. 그러면 아래와 같은 보조키가 생성된다.

비트 위치	선택된 비트
14	1
17	0
11	1
24	0
1	1
5	0
3	1
28	1
15	0
6	1
21	0
10	0
23	1
19	0
12	1
4	0
26	1
8	0
16	1
7	0
27	1
20	1
13	0
2	0
41	1
52	1
31	0
37	1
47	0
55	1
30	1
40	0
51	0
45	1
33	0
48	0
44	1
49	0
39	1
56	0
34	1
53	1
46	0
42	1
50	1
36	0
29	0
32	1


10101011 01010101 10010101 00101100 11010010 11011001

이처럼 보조키 생성 과정은 Feistel 구조의 핵심 요소로, 각 라운드에서 사용되는 고유한 보조키는 암호화 과정에서 중요한 역할을 한다.

📌 파이스텔 라운드 함수 예시

Feistel 라운드 함수는 Feistel 구조에서 암호화와 복호화를 수행하는 핵심적인 단계이다.

1️⃣ Initial Permutation (IP) - 초기 순열:

먼저, 입력된 64비트 데이터에 대해 초기 순열(IP)을 수행한다. 이 과정은 단순히 비트들의 순서를 변경하는 것으로, 암호화나 복호화에 직접적인 영향을 주지는 않지만 보안성을 높이기 위한 중요한 절차이다.

입력: 64비트 데이터

출력: 순서가 변경된 64비트 데이터

2️⃣ Left와 Right로 분리:

IP 과정을 거친 후, 64비트 데이터를 32비트씩 두 부분으로 분리한다. 왼쪽 32비트는 Left (L0), 오른쪽 32비트는 Right (R0)로 나뉜다. 이 두 부분이 Feistel 라운드에서 번갈아 가며 교환되면서 암호화가 진행된다.

L0: 좌측 32비트

R0: 우측 32비트

3️⃣ Expansion Permutation (확장 순열):

이제 R0 (Right 32비트)에 대해 확장 순열(Expansion Permutation)을 수행한다. 이 단계에서는 R0의 32비트를 48비트로 확장하는데, 이는 나중에 사용할 48비트 보조키와 XOR 연산을 하기 위한 준비 과정이다.

입력: R0 (32비트)

출력: 확장된 48비트

4️⃣ 보조키와 XOR 연산:

확장된 48비트와, 보조키(K) (PC-2 과정을 통해 생성된 48비트 보조키)를 사용하여 XOR 연산을 수행한다. 이 XOR 연산을 통해 데이터를 난독화하여 암호화의 복잡성을 더한다.

입력: 48비트 확장된 R0, 48비트 보조키

출력: XOR 결과 (48비트)

5️⃣ S-Box 치환:

XOR 연산을 마친 48비트 값을 8개의 S-Box를 사용하여 32비트로 줄인다. 각 S-Box는 6비트 입력을 받아 4비트 출력을 생성하는데, 이 과정을 통해 48비트 입력이 32비트로 변환된다.

S-Box의 규칙은 미리 정의되어 있으며, 6비트 입력 중 1번째와 6번째 비트로 행(row)을 선택하고, 2, 3, 4, 5번째 비트로 열(column)을 선택하여 4비트 출력을 얻는다.

입력: XOR 결과 (48비트)

출력: S-Box를 거쳐 32비트로 줄어든 값

6️⃣ P-Box (최종 순열):

S-Box 치환으로 얻은 32비트에 대해 최종 순열(P-Box)을 적용한다. 이 순열은 단순히 32비트의 순서를 다시 한번 섞어주는 과정이다.

입력: 32비트

출력: 순서가 섞인 32비트

7️⃣ Left와의 XOR 연산:

P-Box를 통과한 32비트 값을 이전 단계에서 나온 L0(Left 32비트)와 XOR 연산을 수행한다. 이를 통해 새로운 R1 값을 얻고, 원래 R0 값은 L1으로 설정하여 Left와 Right가 교환된다.

입력: L0(Left 32비트), P-Box 결과(32비트)

출력: R1 = L0 ⊕ P-Box 결과

8️⃣ 다음 라운드 준비:

이제 새로운 L1과 R1이 만들어졌다. L1은 이전 라운드의 R0 값이 되고, R1은 새로 만들어진 값이 된다. 이 과정을 16라운드 동안 반복하게 된다. 마지막 라운드가 끝난 후에는, 최종적으로 Initial Permutation의 역(IP-1)을 적용하여 암호화가 완성된다.