Symmetric key(대칭키) 암호화

📡 Symmetric key(대칭키) 암호화

symmetric key cryptography(대칭키 암호화)는 송신자와 수신자가 동일한 키($K$)를 사용해 데이터를 암호화하고 복호화하는 방식이다.

예를 들어 Alice가 Bob에게 메시지 $m$을 보내고 싶다고 하자. Alice는 공유된 키 $K$를 이용해 메시지를 암호화하고 암호문 $K(m)$ 형태로 전송한다. Bob은 같은 키 $K$를 가지고 있어 이를 이용해 원래의 메시지 $m$을 복호화할 수 있다. 같은 키를 양쪽에서 모두 사용한다는 점에서 ‘대칭’이라는 이름이 붙는다.

고전적인 방식 중 하나인 monoalphabetic substitution cipher(단일 치환 암호)도 대칭키 암호의 한 예다. 이 경우 키는 단순한 알파벳 치환표일 수 있고, Alice와 Bob은 문자 간의 치환 규칙을 미리 알고 있어야 한다. 현대에는 AES, DES와 같은 고성능 알고리즘이 대칭키 암호화에 널리 사용된다.

키 분배의 어려움

대칭키 암호의 가장 큰 문제는 바로 이 질문이다.

Alice와 Bob은 이 비밀 키를 어떻게 미리 공유할 수 있을까?

서로 직접 만나 키를 주고받을 수 있다면 문제가 없지만, 대부분의 네트워크 통신은 물리적으로 떨어진 위치에서 일어나기 때문에, 키를 안전하게 교환하는 것이 가장 큰 걸림돌이 된다. 이를 초기 키 분배 문제라고 부른다.

이 문제를 해결하기 위해 다양한 기술이 도입되었다. 대표적으로는 다음과 같은 방법이 있다.

• Diffie–Hellman 키 교환: 중간에 키 값을 노출하지 않고, 두 사람이 동일한 키를 계산해내도록 설계된 수학적 프로토콜이다.
• 공개키 암호 방식과의 결합 사용: 처음에는 공개키 방식을 사용해 대칭키를 안전하게 교환하고, 이후 데이터 통신은 대칭키로 처리한다.
  • 우리가 흔히 사용하는 HTTPS(TLS)에서는 이 구조가 사용된다. 서버와 클라이언트는 공개키 암호를 통해 세션 키를 교환한 뒤, 실제 웹 페이지나 데이터는 대칭키 암호화로 주고받는다.

대칭키 암호는 초기 키 분배와 관리의 어려움을 동반한다는 점에서 다른 방식과 함께 사용하는 것이 일반적인 설계 방식이다.

📡 고전적 대칭키 암호 - 치환 암호

monoalphabtic ciper (단일 치환 암호)

치환 암호(substitution cipher)는 평문의 각 요소(예: 문자)를 다른 것으로 대체(substitute)함으로써 암호문을 생성하는 방식이다. 그중에서도 단일 치환 암호(monoalphabetic cipher)는 각 알파벳을 고정된 방식으로 다른 알파벳으로 대응시키는 단순한 암호화 기법이다. 즉, 평문에 나오는 ‘a’를 항상 같은 암호문자 ‘m’으로, ‘b’를 항상 ‘n’으로 바꾸는 식이다.

예를 들어 다음과 같은 평문 알파벳과 암호문 알파벳 사이의 매핑이 있다고 하자.

Plaintext: abcdefghijklmnopqrstuvwxyz
Ciphertext: mnbvcxzasdfghjklpoiuytrewq

Plaintext: abcdefghijklmnopqrstuvwxyz
Ciphertext: mnbvcxzasdfghjklpoiuytrewq

이 경우, 평문의 각 문자는 암호표에 따라 다음과 같이 치환된다.

예시로,

• Plaintext: bob. i love you. alice
• Ciphertext: nkn. s gktc wky. mgsbc

여기서 암호화 키는 알파벳 26개를 서로 대응시키는 표(mapping)로 정의된다.

• b → n
• o → k
• i → s
• l → g
• v → t
• e → c
• y → w
• u → y
• a → m
• c → b

한계

이 방식은 구현이 매우 간단하고 직관적으로 이해하기도 쉽지만, 암호학적으로는 매우 약한 방식이다. 이유는,

• 통계적 분석이 매우 쉽다. 예를 들어 ‘e’가 가장 많이 등장하는 문자라는 점을 이용하면 쉽게 추정이 가능하다
• 패턴이 고정되어있다. 한 번 치환된 문자는 항상 같은 결과를 만들어내므로, 반복 패턴이 그대로 노출된다
• 키 공간이 작다. 이론적으로 26! (약 $4 \times 10^{26}$)개의 키가 존재하지만, 요즘 컴퓨터 연산 능력이라면 쉽게 탐색 가능하다

결국 이 방식은 암호화의 기본 원리를 학습하는 수준에서는 적합하지만, 실제로 쓰기에는 적합하지 않다.

다중 치환 암호 (Substitution + Cycle)

단일 치환 암호는 같은 문자를 항상 같은 방식으로 치환하기 때문에, 빈도 분석이나 반복 패턴에 쉽게 노출된다는 약점이 있다. 이를 보완하기 위한 방법 중 하나가 여러 개의 치환 암호를 조합하여 사용하는 방식이다. 이때 핵심 아이디어는 여러 개의 서로 다른 치환 매핑($M1, M2, …, Mn$)을 주기적으로 순환(cycle)하면서 사용하는 것이다.

예를 들어, 암호화 키가 다음과 같이 구성되어 있다고 하자

• 총 $n$개의 치환 암호표: $M_1, M_2, …, M_n$
• 순환 패턴: $M_1 → M_3 → M_4 → M_3 → M_2 → M_1 → …$ (반복)

이때 평문을 암호화할 때는 각 문자에 대해 순서대로 치환표를 적용한다.

• "$d$"는 $M_1$을 사용해 치환
• "$o$"는 $M_3$을 사용해 치환
• "$g$"는 $M_4$를 사용해 치환

그다음 문자는 다시 $M_3$, $M_2$, $M_1$ 순으로 반복된다. 이렇게 되면 동일한 문자가 여러 번 등장해도 항상 같은 방식으로 치환되지 않기 때문에 패턴 노출을 막고 통계적 분석을 어렵게 만든다.

이 방식에서의 암호화 키는 단순한 비트열이 아니라, 다음 두 가지 정보를 모두 포함한다.

• n개의 개별 치환 암호표 ($M_1$, $M_2$, …, $M_n$)
• 순환 패턴(sequence)
  • ex, $[1, 3, 4, 3, 2]$처럼 암호표를 어떤 순서로 반복 적용할 것인지

이 구조는 단일 치환 암호에 비해 훨씬 복잡하고 안전한 암호화를 가능하게 해준다. 실제로 이러한 아이디어는 역사적인 비젠네르(Vigenère) 암호와 같은 고전 암호 시스템의 기반이 되었고, 현대 암호 알고리즘에서도 비슷한 원칙(ex, 키 스트림, 라운드별 키 적용 등)이 사용된다.

📡 현대에서 사용하는 대칭키 암호 - 블록 암호

블록 암호의 구조

블록 암호(block cipher)는 입력 데이터를 일정한 길이의 블록 단위로 나눈 뒤, 각 블록을 독립적으로 암호화한다. 일반적으로 하나의 평문 블록은 $n$비트고, 암호화한 결과도 동일한 길이인 $n$비트의 암호문 블록이 된다. 이때 사용되는 암호화와 복호화 작업에는 모두 동일한 비밀 키($k$비트)가 필요하다.

암호화는 평문 블록과 키를 입력으로 받아 암호문 블록을 출력하는 방식으로 진행된다. 반대로 복호화는 암호문 블록과 같은 키를 입력으로 받아 원래의 평문 블록을 복원한다. 이렇게 암호화와 복호화가 한 쌍으로 동작하기 때문에, 블록 암호는 데이터의 양방향 보호에 적합하다. 입력과 출력의 블록 크기는 항상 같지만 출력 내용은 키와 알고리즘의 복잡도에 따라 완전히 달라진다.

블록 암호가 널리 사용되는 이유 중 하나는 구현의 효율성에 있다. 고정된 크기의 블록 단위로 처리하기 때문에 하드웨어나 소프트웨어에서 병렬화나 최적화가 용이하다. 또한 블록 암호는 ‘운용 모드(mode of operation)’에 따라 다양한 형태로 응용될 수 있다. 예를 들어 각 블록을 독립적으로 암호화하는 ECB 모드, 이전 블록의 암호문을 다음 블록 암호화에 반영하는 CBC 모드, 스트림처럼 동작할 수 있도록 구성하는 CTR 모드 등이 존재한다. 운용 모드를 적절히 선택하면 에러 전파를 줄이거나 보안성을 높이는 등 다양한 목적에 대응할 수 있다.

현대 블록 암호의 대표적인 예로는 AES(Advanced Encryption Standard)가 있으며, 그 이전에는 DES(Data Encryption Standard)가 널리 사용되었다. AES는 DES에 비해 보안성과 성능 면에서 큰 개선을 이룬 알고리즘으로, 현재는 대부분의 시스템에서 표준으로 채택되어 있다.

블록 암호 구성 요소

현대의 블록 암호 알고리즘은 치환이나 반복만으로 구성되어 있지 않다. 보안을 강화하기 위해 다양한 연산들을 조합한 구조를 반복적으로 적용한다. 이 구조는 혼란(confusion)과 확산(diffusion)이라는 두 가지 암호학적 원칙을 만족시키기 위해 설계되었다.

하나의 라운드 내부에는 다음과 같은 주요 구성 컴포넌트들이 사용된다.

• Substitution (치환)
  • 가장 대표적인 예는 S-box이다. 입력된 비트 집합을 복잡한 규칙에 따라 완전히 다른 비트로 바꿔준다. 이 치환 과정은 암호에 비선형성(non-linearity)을 부여해 공격자가 입력과 출력 사이의 관계를 단순한 수식으로 예측하지 못하게 만든다.
• Permutation (전치)
  • 전치는 입력 비트들의 순서를 재배열하는 작업이다. 이때 순서 변경은 정해진 규칙에 따라 수행되고, 목적은 입력의 일부 변화가 출력 전체에 영향을 미치도록 만드는 것이다. 일반적으로 Straight permutation이나 Compression permutation, 혹은 Transposition이라는 용어로 구분된다.
• Expansion (확장)
  • 특정 비트 수를 늘리는 연산이다. 예를 들어 DES에서는 32비트 입력을 48비트로 확장해 라운드 키와 XOR을 할 수 있게 만든다. 이 확장은 비트 중복을 포함하기 때문에 S-box에서 더 큰 혼란 효과를 낼 수 있다.
• XOR (배타적 논리합)
  • 가장 단순하면서도 강력한 연산이다. 평문이나 중간 결과를 키와 결합할 때 사용되며, 입력이나 키의 작은 변화도 결과 전체에 영향을 주게 만든다. 대부분의 블록 암호에서 XOR은 라운드의 핵심 결합 연산으로 사용된다.
• Shift (비트 이동)
  • 비트들을 좌측이나 우측으로 일정 비트 수만큼 이동시키는 연산이다. 특히 키 스케줄(Key schedule) 단계에서 자주 등장하며, 라운드마다 다른 키를 생성하기 위한 도구로 사용된다.
• Swap (위치 교환)
  • 비트들의 위치를 서로 맞바꾸는 연산이다. 이 역시 혼란을 더하기 위한 장치로 일정 규칙에 따라 비트들의 상대적 위치를 바꾼다.
• Split and Combine (분할과 결합)
  • 입력 블록을 여러 개의 작은 블록으로 나눈 뒤, 각각 다른 연산을 적용하고 다시 합치는 방식이다. 이 과정을 통해 각 부분의 영향을 전체 블록으로 확산시킬 수 있다.

이 연산들은 여러 개의 라운드로 구성된 블록 암호 구조 속에서 반복적으로 적용된다. 라운드가 많을수록 입력의 작은 변화가 더 넓게 퍼지고, 복호화 없이 원문을 유추하기가 어려워진다.

📡 DES

개요

DES(Data Encryption Standard)는 1977년 미국 NIST(국립표준기술연구소)에 의해 공식 표준으로 채택된 대칭키 블록 암호화 알고리즘이다. DES는 입력으로 64비트의 평문을 받아, 56비트 비밀키를 이용해 암호문으로 변환한다. (엄밀히는 64비트 키를 사용하지만, 이 중 8비트는 패리티 검사용이므로 실질적인 키 길이는 56비트다.)

DES는 블록 암호(block cipher) 방식으로 동작해 주로 CBC(Cipher Block Chaining) 모드에서 운용된다. CBC 방식에서는 각 블록의 암호화 결과가 다음 블록 암호화에 영향을 주기 때문에, 반복되는 평문이라도 서로 다른 암호문을 생성할 수 있다.

DES 구조

DES는 1970년대에 개발된 고전적인 블록 암호 알고리즘이다. 단순한 암호처럼 보이지만 실제로는 데이터의 혼란(confusion)과 확산(diffusion)을 반복해서 적용함으로써 입력과 출력 사이의 관계를 매우 복잡하게 만든다.

DES의 핵심은 다음과 같은 질문에서 시작된다.

‘같은 입력이라도 매번 다른 결과를 만들고, 해커가 원래 데이터를 유추하지 못하게 하려면 어떻게 해야 할까?’

답은 반복과 치환, 그리고 구조화된 섞기에 있다.

전체 흐름을 간략화해보면 아래와 같다.

64비트 평문
 ↓
Initial Permutation (비트 재배열)
 ↓
L₀ / R₀ 분할 (32비트씩)
 ↓
16 라운드 반복 (Feistel 구조)
 ↓
L₁₆ / R₁₆ 병합
 ↓
Final Permutation
 ↓
64비트 암호문 출력

64비트 평문
 ↓
Initial Permutation (비트 재배열)
 ↓
L₀ / R₀ 분할 (32비트씩)
 ↓
16 라운드 반복 (Feistel 구조)
 ↓
L₁₆ / R₁₆ 병합
 ↓
Final Permutation
 ↓
64비트 암호문 출력

1. Initial Permutation (초기 전치)

• 처음 입력된 64비트 평문을 정해진 규칙에 따라 섞는다. 혼란성(confusion)을 증가시키고, 이후 연산이 더 고르게 확산되도록 한다.
• 실제 보안 강도에 큰 영향은 없지만 전체 구조의 기반을 잡아주는 준비 작업이다.

2. 좌우 분할: $L₀$와 $R₀$

• 입력을 왼쪽($L$) 32비트, 오른쪽($R$) 32비트로 나눈다. 이후 16번의 라운드에서 이 두 부분이 서로 교차하면서 변한다.

3. 16 라운드 반복: Feistel 구조

이 구조는 아래를 계속 반복한다.

• $Lᵢ = Rᵢ₋₁$
• $Rᵢ = Lᵢ₋₁ ⊕ F(Rᵢ₋₁, Kᵢ)$

오른쪽 절반을 기준으로 함수 F를 적용하고 그 결과를 왼쪽과 XOR해서 새로운 오른쪽을 만든다. 이 방식은 복호화할 때도 같은 구조를 그대로 사용할 수 있어서 16번 반복한다.

4. 라운드 함수 $F$

$F(Rᵢ₋₁, Kᵢ)$는 DES의 심장이다. 이 함수가 없다면 DES는 단순 반복 노동일 뿐이다.

$F$ 함수 내부 구조는 다음과 같다.

1. 확장 (Expansion): 32비트 $R$을 48비트로 확장한다.
   • DES의 라운드 키는 48비트인데, 입력인 $R$은 32비트다. 그래서 R을 48비트로 확장해야 둘을 XOR할 수 있다.
   • 나중에 S-box에서 혼란을 더 키울 수 있다.
2. XOR: 확장된 값과 라운드 키 $Kᵢ$를 XOR한다.
   • 키에 따라 결과가 달라지게 만들기 위함이다. 같은 입력 $R$이라도 $K_i$가 다르면 전혀 다른 결과가 나온다.
3. S-box 통과: 48비트를 6비트씩 나눠 8개의 S-box에 통과시켜 32비트로 축소
   • S-box는 복잡한 치환을 담당해 DES의 비선형성을 제공한다.
   • 암호학에서 중요한 건 공격자가 입력과 출력의 관계를 수학적으로 예측할 수 없게 만드는 것인데, 이건 선형 연산 (XOR, shift 등) 으로는 부족하다. 그래서 미리 정의된 복잡한 테이블인 S-box를 활용해 입력 6비트를 완전히 새로운 4비트로 치환한다. 이걸 통해 예측 불가능성을 넣는 것이다.
4. 전치 (Permutation): 결과 비트들을 다시 섞음

이 과정을 통해 입력의 작은 변화가 출력 전체에 영향을 미치는 확산 효과를 얻는다.

5. 키 스케줄: 16개의 라운드 키 생성

• DES는 56비트 비밀 키를 입력으로 받아 48비트 라운드 키 16개를 생성한다. 각 라운드 키는 이전 키를 기반으로 부분 선택 + shift + 재배열을 통해 만들어진다. 이렇게 하면 매 라운드마다 전혀 다른 키가 적용되어 보안성이 올라간다.

6. Final Permutation (최종 전치)

• 마지막 라운드 결과인 $L₁₆$과 $R₁₆$을 붙여 다시 64비트로 만들고 Initial Permutation의 역순으로 다시 비트를 재배열한다. 이로써 최종 암호문이 완성된다.

보안성 문제

DES가 처음 도입되었을 때는 56비트 키도 충분히 안전했지만, 시간이 지나면서 컴퓨터의 연산 능력이 크게 향상되었다. 그 결과 DES는 무차별 대입(brute force) 공격에 점점 더 취약해졌다.

이 문제를 상징적으로 보여준 사건이 바로 DES Challenge다. 이 공개 이벤트에서 참가자들은 DES로 암호화된 메시지를 단 하루도 안 되어 복호화하는 데 성공했고, 이는 DES가 더 이상 현대 보안 환경에 적합하지 않다는 점을 드러냈다. 단, 구조적인 취약점이나 암호 해석적 공격(cryptanalytic attack)에 대해서는 아직까지 치명적인 문제가 발견된 바는 없다.

3DES

DES의 보안성 문제를 해결하기 위해 등장한 것이 3DES(Triple DES)다. 이름 그대로 DES 알고리즘을 세 번 반복 적용하는 방식이다. 기본 절차는 다음과 같다.

1. 첫 번째 키로 암호화
2. 두 번째 키로 복호화
3. 세 번째 키로 다시 암호화

이때 세 개의 키를 모두 다르게 쓸 수도 있고, 일부 키를 공유해 성능을 조금 개선할 수도 있다. 결과적으로 3DES는 112비트 또는 168비트 수준의 키 강도를 제공해 단일 DES보다 훨씬 높은 보안성을 확보했다.

📡 AES

AES(Advanced Encryption Standard)는 DES의 보안 한계를 극복하기 위해, 2001년 미국 NIST(국립표준기술연구소)가 새로운 대칭키 암호화 표준으로 채택한 알고리즘이다. DES가 짧은 키 길이(56비트)로 인해 더 이상 안전하지 않다는 평가를 받으면서 더 강력한 보안성과 유연한 구조를 갖춘 AES가 등장하게 되었다.

AES는 DES보다 구조적으로 훨씬 발전된 형태다.

• 블록 크기: DES는 64비트 단위로 데이터를 처리했지만, AES는 128비트 블록 단위로 암호화를 수행한다.
• 키 길이 선택: DES는 고정된 56비트 키만 사용했지만, AES는 128, 192, 256비트 키 중 선택이 가능하다.
• 라운드 수: 키 길이에 따라 암호화 라운드 수가 달라진다. 각각 10, 12, 14 라운드를 거치게 된다.

AES가 DES를 대체할 수 있었던 결정적인 이유는 압도적인 키 공간에 있다. DES의 56비트 키는 약 7천억 개의 조합을 가진다. 요즘 컴퓨터로 1초 이내에 모두 시도해볼 수 있을 정도로 작은 수다. 반면 AES의 128비트 키는 $2^{128} ≈ 3.4 × 10^{38}$개의 조합을 갖는다. 초당 수조 개의 키를 대입하더라도 149조 년이 걸린다. 무차별 대입(brute force) 공격이 사실상 불가능한 수준이다.