10장. 기타 공개키 암호시스템

개요

Diffie-Hellman 키 교환, Elgamal 암호시스템, 타원곡선 산술, ECC, 비대칭 기반 PRNG

학습 목표

• Diffie-Hellman 키 교환을 정의한다.
• 중간자 공격(man-in-the-middle attack)을 이해한다.
• Elgamal 암호시스템의 개요를 제시한다.
• 타원곡선 산술을 이해한다.
• 타원곡선 암호(ECC)의 개요를 제시한다.
• 비대칭 암호 기반 의사난수 생성 기법 두 가지를 설명한다.

---

10.1 Diffie-Hellman 키 교환

최초로 발표된 공개키 알고리즘(1976, Diffie & Hellman). 목적은 두 사용자가 대칭 암호에 사용할 비밀키를 안전하게 교환하는 것이다. 알고리즘 자체는 비밀값의 교환에 한정되며, 그 효과는 이산대수(discrete logarithm) 계산의 어려움에 기반한다.

이산대수

소수 $p$의 원시근(primitive root) $\alpha$가 있을 때, $\alpha \bmod p,\; \alpha^2 \bmod p,\; \dots,\; \alpha^{p-1} \bmod p$는 $1$부터 $p-1$까지의 모든 정수를 한 번씩 생성한다.

임의의 정수 $b$에 대해 $b \equiv \alpha^i \pmod{p}$인 유일한 $i$를 $b$의 이산대수 $\text{dlog}_{\alpha, p}(b)$라 한다.

알고리즘

공개 파라미터: 소수 $q$, $q$의 원시근 $\alpha$

1. A: 비밀 정수 $X_A < q$ 를 랜덤 선택, 공개키 $Y_A = \alpha^{X_A} \bmod q$ 계산
2. B: 비밀 정수 $X_B < q$ 를 랜덤 선택, 공개키 $Y_B = \alpha^{X_B} \bmod q$ 계산
3. A 계산: $K = Y_B^{X_A} \bmod q$
4. B 계산: $K = Y_A^{X_B} \bmod q$

두 계산의 결과가 동일함은 다음으로 증명된다:

$K = (Y_B)^{X_A} \bmod q = (\alpha^{X_B})^{X_A} \bmod q = \alpha^{X_A X_B} \bmod q = (Y_A)^{X_B} \bmod q$

공격자는 $q$, $\alpha$, $Y_A$, $Y_B$만 알고 있으므로, 비밀키를 구하려면 이산대수 $X_B = \text{dlog}_{\alpha,q}(Y_B)$를 계산해야 한다. 큰 소수에서는 이것이 실행 불가능하다.

예시

$q = 353, \quad \alpha = 3, \quad X_A = 97, \quad X_B = 233$

$Y_A = 3^{97} \bmod 353 = 40, \quad Y_B = 3^{233} \bmod 353 = 248$

$K = 248^{97} \bmod 353 = 40^{233} \bmod 353 = 160$

키 교환 프로토콜

• 일회성 교환: A가 $X_A$, $Y_A$를 생성·전송, B가 응답 → 일회용 세션키 생성. $q$와 $\alpha$는 사전에 알려져 있거나 첫 메시지에 포함.
• 장기 공개키 디렉토리: 각 사용자가 장기 $X_i$를 유지하고 $Y_i$를 중앙 디렉토리에 공개. 누구든지 상대의 공개값으로 비밀키를 계산하여 암호화된 메시지 전송 가능. 기밀성과 일정 수준의 인증을 제공하지만, 재전송 공격은 방어하지 못한다.

중간자 공격 (Man-in-the-Middle Attack)

프로토콜이 참가자를 인증하지 않기 때문에 중간자 공격에 취약하다.

공격 절차:

1. Darth가 비밀키 $X_{D1}$, $X_{D2}$를 생성하고 공개키 $Y_{D1}$, $Y_{D2}$를 계산
2. Alice가 $Y_A$를 Bob에게 전송 → Darth가 가로채고 $Y_{D1}$을 Bob에게 전달
3. Darth는 $K_2 = Y_A^{X_{D2}} \bmod q$ 계산 (Alice와의 공유키)
4. Bob이 $Y_B$를 Alice에게 전송 → Darth가 가로채고 $Y_{D2}$를 Alice에게 전달
5. Darth는 $K_1 = Y_B^{X_{D1}} \bmod q$ 계산 (Bob과의 공유키)

결과: Alice-Darth는 $K_2$, Darth-Bob은 $K_1$을 공유. Darth는 모든 통신을 복호화·변조·재암호화 가능.

방어

이 취약점은 전자서명과 공개키 인증서(13·14장)를 통해 극복할 수 있다.

---

10.2 Elgamal 암호시스템

1984년 T. Elgamal이 발표한 이산대수 기반 공개키 방식으로, Diffie-Hellman과 밀접하게 관련된다. DSS(13장)와 S/MIME(19장) 등 여러 표준에서 사용된다.

키 생성

• 공개 파라미터: 소수 $q$, 원시근 $\alpha$
• 랜덤 정수 $X_A$ 선택 ($1 < X_A < q - 1$)
• $Y_A = \alpha^{X_A} \bmod q$ 계산
• 개인키: $X_A$ / 공개키: $\{q, \alpha, Y_A\}$

암호화 (B → A)

1. 메시지 $M$을 $0 \le M \le q - 1$인 정수로 표현
2. 랜덤 정수 $k$ 선택 ($1 \le k \le q - 1$)
3. 일회용 키 $K = Y_A^k \bmod q$ 계산
4. 암호문 생성:

$C_1 = \alpha^k \bmod q, \quad C_2 = K \cdot M \bmod q$

복호화 (A)

1. $K = C_1^{X_A} \bmod q$ 로 일회용 키 복원
2. $M = C_2 \cdot K^{-1} \bmod q$

동작 증명

$K = Y_A^k \bmod q = (\alpha^{X_A})^k \bmod q = \alpha^{kX_A} \bmod q = (C_1)^{X_A} \bmod q$

따라서 복호화 시 동일한 $K$를 복원할 수 있고, $C_2 \cdot K^{-1} = K \cdot M \cdot K^{-1} = M$이다.

예시 ($q = 19$, $\alpha = 10$, $X_A = 5$)

$Y_A = 10^5 \bmod 19 = 3, \quad \text{공개키} = \{19, 10, 3\}$

$M = 17$을 암호화 ($k = 6$):

$K = 3^6 \bmod 19 = 7$

$C_1 = 10^6 \bmod 19 = 11, \quad C_2 = 7 \times 17 \bmod 19 = 5$

복호화:

$K = 11^5 \bmod 19 = 7, \quad K^{-1} \bmod 19 = 11$

$M = 5 \times 11 \bmod 19 = 17$

각 블록마다 고유한 $k$ 필수

같은 $k$를 두 블록에 사용하면, 한 블록 $M_1$을 알 때 다른 블록을 쉽게 복원할 수 있다:

$M_2 = C_{2,1}^{-1} \cdot C_{2,2} \cdot M_1 \bmod q$

보안: 공격자가 개인키 $X_A$를 복원하려면 $X_A = \text{dlog}_{\alpha,q}(Y_A)$를 계산해야 한다. $p$가 최소 300자릿수이고 $q - 1$에 큰 소인수가 포함되면 안전하다.

---

10.3 타원곡선 산술

RSA의 키 길이가 보안 강화를 위해 계속 증가하면서 처리 부담이 커지고 있다. 이에 대한 대안으로 **타원곡선 암호(ECC)**가 도전하고 있다. ECC의 핵심 매력은 훨씬 작은 키 크기로 동등한 보안을 제공한다는 점이다.

아벨 그룹 (Abelian Group) 복습

아벨 그룹 $\{G, \cdot\}$은 다섯 가지 공리를 만족하는 집합과 이항 연산의 쌍이다:

• (A1) 닫힘: $a, b \in G \Rightarrow a \cdot b \in G$
• (A2) 결합법칙: $a \cdot (b \cdot c) = (a \cdot b) \cdot c$
• (A3) 항등원: $\exists\, e \in G$, $a \cdot e = a$
• (A4) 역원: 각 $a$에 대해 $a' \in G$, $a \cdot a' = e$
• (A5) 교환법칙: $a \cdot b = b \cdot a$

Diffie-Hellman은 $\mathbb{Z}_p^*$ 위의 곱셈 그룹을 사용하고, ECC는 타원곡선 위의 덧셈 그룹을 사용한다. DH에서 $a^k \bmod q$에 대응하는 ECC 연산은 $k \cdot P = \underbrace{P + P + \cdots + P}_{k\text{번}}$이다.

실수 위의 타원곡선

타원곡선은 (타원이 아니라) 다음과 같은 3차 방정식으로 정의된다:

$y^2 = x^3 + ax + b$

여기에 무한원점(point at infinity) $\mathcal{O}$를 포함한 점의 집합 $E(a, b)$를 정의한다. 다음 조건을 만족하면 그룹이 형성된다:

$4a^3 + 27b^2 \neq 0$

덧셈 규칙 (기하학적)

1. $\mathcal{O}$는 항등원: $P + \mathcal{O} = P$
2. $P = (x, y)$의 역원은 $-P = (x, -y)$, $P + (-P) = \mathcal{O}$
3. 두 점 $P$, $Q$의 덧셈: $P$와 $Q$를 잇는 직선의 세 번째 교점 $R$에 대해 $P + Q = -R$ (x축 대칭)
4. $P$와 $-P$ (동일 x좌표, 수직선): $P + (-P) = \mathcal{O}$
5. 점의 배가: $Q$에서의 접선의 다른 교점 $S$에 대해 $2Q = -S$

덧셈 규칙 (대수적)

서로 다른 두 점 $P = (x_P, y_P)$, $Q = (x_Q, y_Q)$에 대해 $R = P + Q = (x_R, y_R)$:

$\lambda = \frac{y_Q - y_P}{x_Q - x_P}$

$x_R = \lambda^2 - x_P - x_Q, \quad y_R = -y_P + \lambda(x_P - x_R)$

점의 배가 $P + P = 2P$ ($y_P \neq 0$):

$\lambda = \frac{3x_P^2 + a}{2y_P}$

$x_R = \lambda^2 - 2x_P, \quad y_R = \lambda(x_P - x_R) - y_P$

$\mathbb{Z}_p$ 위의 타원곡선

변수와 계수를 $\mathbb{Z}_p$로 제한:

$y^2 \bmod p = (x^3 + ax + b) \bmod p$

그룹 형성 조건: $(4a^3 + 27b^2) \bmod p \neq 0$

$\mathbb{Z}_p$ 위에서의 덧셈 규칙은 실수 위와 동일한 대수적 형태를 따르되, 모든 연산을 $\bmod p$로 수행하고 나눗셈은 모듈러 역원으로 대체한다.

예시: $E_{23}(1, 1)$에서 $P = (3, 10)$, $Q = (9, 7)$

$\lambda = \frac{7 - 10}{9 - 3} \bmod 23 = \frac{-3}{6} \bmod 23 = \frac{-1}{2} \bmod 23 = 11$

$x_R = (11^2 - 3 - 9) \bmod 23 = 109 \bmod 23 = 17$

$y_R = (11(3 - 17) - 10) \bmod 23 = -164 \bmod 23 = 20$

$P + Q = (17, 20)$

점의 수 $N$은 다음 범위에 있다:

$p + 1 - 2\sqrt{p} \le N \le p + 1 + 2\sqrt{p}$

$GF(2^m)$ 위의 타원곡선

이 경우 사용되는 방정식 형태가 다르다:

$y^2 + xy = x^3 + ax^2 + b$

그룹 형성 조건: $b \neq 0$. 하드웨어 구현에 적합하며 (비트 연산만으로 강력한 암호시스템 구축 가능), 소수 곡선($\mathbb{Z}_p$)은 소프트웨어에 적합하다.

---

10.4 타원곡선 암호 (ECC)

타원곡선 이산대수 문제 (ECDLP)

$Q = kP \quad (Q, P \in E_q(a,b),\; k < q)$

$k$와 $P$가 주어졌을 때 $Q$를 계산하는 것은 쉽지만, $Q$와 $P$가 주어졌을 때 $k$를 결정하는 것은 어렵다. 이것이 ECC 보안의 근거이며, 가장 빠른 알려진 기법은 Pollard rho 방법이다.

ECC 키 크기 비교 (NIST SP 800-57)

대칭키 (비트)	DH/DSA $(L, N)$	RSA (비트)	ECC (비트)
80	1024, 160	1024	160–223
112	2048, 224	2048	224–255
128	3072, 256	3072	256–383
192	7680, 384	7680	384–511
256	15360, 512	15360	512+

SP 800-57은 2030년까지 RSA 3072비트, ECC 256비트 이상을 권장한다. 동일 키 길이에서 ECC와 RSA의 계산 비용은 유사하므로, ECC는 더 짧은 키로 계산적 이점을 가진다.

ECC Diffie-Hellman 키 교환

공통 파라미터: 타원곡선 $E_q(a, b)$, 베이스 포인트 $G$ (큰 위수 $n$)

1. A: 비밀 $n_A < n$ 선택, 공개키 $P_A = n_A \times G$ 계산
2. B: 비밀 $n_B < n$ 선택, 공개키 $P_B = n_B \times G$ 계산
3. 공유 비밀:

$K = n_A \times P_B = n_A \times (n_B \times G) = n_B \times (n_A \times G) = n_B \times P_A$

예시

$p = 211, \quad E_p(0, -4): y^2 = x^3 - 4, \quad G = (2, 2), \quad 240G = \mathcal{O}$

$n_A = 121 \;\to\; P_A = 121 \cdot (2,2) = (115, 48)$

$n_B = 203 \;\to\; P_B = 203 \cdot (2,2) = (130, 203)$

$K = 121 \cdot (130, 203) = 203 \cdot (115, 48) = (161, 69)$

비밀키는 점 쌍

공유 비밀키는 좌표 쌍이다. 대칭 암호의 세션키로 사용하려면 $x$ 좌표 등에서 단일 값을 추출한다.

ECC 암호화/복호화

각 사용자 A는 개인키 $n_A$를 선택하고 공개키 $P_A = n_A \times G$를 생성한다.

암호화 (A → B): 메시지를 타원곡선 점 $P_m$으로 인코딩한 뒤, 랜덤 $k$를 선택:

$C_m = \{kG, \;\; P_m + kP_B\}$

복호화 (B): 첫 번째 점에 자신의 개인키를 곱하여 마스크를 제거:

$P_m + kP_B - n_B(kG) = P_m + k(n_BG) - n_B(kG) = P_m$

마스킹 원리

A는 $kP_B$를 더해 메시지를 마스킹한다. $k$를 아는 사람은 A뿐이므로 공격자가 마스크를 제거할 수 없다. 동시에 A는 "단서" $kG$를 포함시켜, 개인키 $n_B$를 아는 B만이 $n_B(kG) = kP_B$를 계산하여 마스크를 제거할 수 있게 한다.

예시

$q = 257, \quad E_{257}(0, -4): y^2 = x^3 - 4, \quad G = (2, 2)$

$n_B = 101, \quad P_B = 101 \cdot (2,2) = (197, 167)$

$P_m = (112, 26), \quad k = 41$

$kG = 41 \cdot (2,2) = (136, 128)$

$kP_B = 41 \cdot (197, 167) = (68, 84)$

$C_m = \{(136, 128),\;\; (112,26) + (68,84)\} = \{(136, 128),\;\; (246, 174)\}$

복호화: $(246, 174) - 101 \cdot (136, 128) = (246, 174) - (68, 84) = (112, 26) = P_m$

---

10.5 비대칭 암호 기반 의사난수 생성

비대칭 암호 알고리즘은 겉보기에 랜덤한 출력을 생성하므로 PRNG의 기반이 될 수 있다. 대칭 알고리즘보다 느리기 때문에, 개방형 비트 스트림이 아니라 짧은 의사난수 비트 시퀀스를 생성하는 PRF 용도로 사용된다.

Micali-Schnorr PRNG (RSA 기반)

ANSI X9.82, ISO 18031에 권장. OFB 모드와 유사한 구조에서 RSA를 사용한다. 출력을 두 부분으로 나누어 **순방향 예측 불가능성(forward unpredictability)**을 확보한다.

절차:

$y_i = x_{i-1}^e \bmod n$

• $x_i$ = $y_i$의 상위 $r$비트 (다음 반복의 입력)
• $z_i$ = $y_i$의 하위 $k$비트 (의사난수 출력)

$r + k = N$ ($N$은 $n$의 비트 길이). 파라미터 조건:

조건	목적
$n = pq$ (두 소수의 곱)	RSA 수준의 암호 강도
$\gcd(e, \phi(n)) = 1$	$s \mapsto s^e \bmod n$ 매핑이 일대일
$r \cdot e \ge 2^N$	완전한 모듈러 축소 보장
$r \ge 2 \times \text{strength}$	암호 공격 방어

예: $e = 3$, $N = 1024$이면 $3r > 1024$이므로 $r \ge 683$, $k = 341$비트가 매 지수 연산마다 생성된다.

Dual EC PRNG (ECC 기반)

NSA가 개발. 타원곡선 위의 알려진 두 점 $P$, $Q$를 사용한다:

$s_i = x(s_{i-1} \cdot P), \quad r_i = \text{lsb}_{240}(x(s_i \cdot Q))$

보안 논란

이 알고리즘의 보안성과 효율성에 대한 논란이 있다. ECC를 이미 구현했지만 다른 PRNG 알고리즘이 없는 시스템에서만 사용 동기가 있다.

---

주요 용어

한글	영문
아벨 그룹	abelian group
이진 곡선	binary curve
3차 방정식	cubic equation
Diffie-Hellman 키 교환	Diffie-Hellman key exchange
이산대수	discrete logarithm
타원곡선	elliptic curve
타원곡선 산술	elliptic curve arithmetic
타원곡선 암호	elliptic curve cryptography (ECC)
유한체	finite field
중간자 공격	man-in-the-middle attack
Micali-Schnorr	Micali-Schnorr
소수 곡선	prime curve
원시근	primitive root
무한원점	zero point