9장. 공개키 암호와 RSA

학습 목표

• 공개키 암호시스템의 기본 원리를 설명한다.
• 공개키 암호의 세 가지 활용(암·복호화, 전자서명, 키 교환)을 구분한다.
• 공개키 암호시스템이 충족해야 할 요구사항을 나열·설명한다.
• RSA 알고리즘의 동작 원리를 제시한다.
• 타이밍 공격을 이해한다.
• 알고리즘 복잡도 관련 이슈를 요약한다.

---

9.1 공개키 암호시스템의 원리

대칭 암호와의 차이

공개키(비대칭) 암호는 암호학 역사상 유일한 진정한 혁명으로 평가된다. 기존의 모든 암호가 치환과 순열에 기반한 반면, 공개키 암호는 수학적 함수에 기반하며 두 개의 별도 키를 사용한다.

흔한 세 가지 오해:

1. 공개키 암호가 대칭 암호보다 더 안전하다 → 아니다. 보안은 키 길이와 계산 복잡도에 의존한다.
2. 공개키 암호가 대칭 암호를 완전히 대체한다 → 아니다. 계산 부하 때문에 현재는 키 관리와 서명에 한정된다.
3. 공개키 방식에서는 키 분배가 간단하다 → 아니다. 여전히 프로토콜과 중앙 에이전트가 필요하다.

공개키 암호시스템의 구성

구분	대칭(관용) 암호	공개키 암호
동작 요건	동일 알고리즘·동일 키로 암·복호화	한 알고리즘, 두 개의 관련 키
보안 요건	비밀키가 비밀로 유지	두 키 중 하나만 비밀이면 됨
키 공유	송·수신자가 동일 키 공유	송·수신자가 쌍의 각각 다른 키 보유

여섯 가지 구성 요소: 평문, 암호화 알고리즘, 공개키·개인키 쌍, 암호문, 복호화 알고리즘.

공개키의 세 가지 활용

활용	설명	사용 키
암·복호화	수신자 공개키로 암호화, 개인키로 복호화	수신자의 $PU / PR$
전자서명	송신자 개인키로 서명, 공개키로 검증	송신자의 $PR / PU$
키 교환	두 당사자가 세션키를 안전하게 교환	양측의 키

알고리즘	암·복호화	전자서명	키 교환
RSA	Yes	Yes	Yes
타원곡선	Yes	Yes	Yes
Diffie-Hellman	No	No	Yes
DSS	No	Yes	No

인증과 기밀성의 동시 제공

두 공개키 연산을 결합하면 인증 + 기밀성을 모두 달성할 수 있다.

$Z = E\bigl(PU_b,\; E(PR_a,\; X)\bigr)$

$X = D\bigl(PU_a,\; D(PR_b,\; Z)\bigr)$

송신자 개인키로 먼저 서명(인증) → 수신자 공개키로 암호화(기밀성). 단점은 공개키 알고리즘을 4회 수행해야 한다는 것이다.

요구사항

Diffie와 Hellman이 제시한 조건:

1. 키 쌍 $(PU_b, PR_b)$ 생성이 계산적으로 쉬워야 한다.
2. 공개키와 메시지로 암호문을 생성하기 쉬워야 한다: $C = E(PU_b, M)$
3. 개인키로 복호화가 쉬워야 한다: $M = D(PR_b, C)$
4. $PU_b$로부터 $PR_b$를 결정하는 것이 계산적으로 불가능해야 한다.
5. $PU_b$와 $C$로 원본 $M$을 복원하는 것이 계산적으로 불가능해야 한다.
6. (선택) 두 키를 어느 순서로든 적용 가능: $D[PU_b, E(PR_b, M)] = D[PR_b, E(PU_b, M)]$

Trap-Door One-Way Function

공개키 암호의 핵심은 트랩도어 단방향 함수이다.

• $Y = f_k(X)$ — $k$와 $X$가 알려져 있으면 쉬움
• $X = f_k^{-1}(Y)$ — $k$와 $Y$가 알려져 있으면 쉬움
• $X = f_k^{-1}(Y)$ — $Y$만 알고 $k$를 모르면 실행 불가능

공개키 암호분석

• 무차별 대입: 큰 키로 방어하되, 공개키 연산의 계산 부하로 키 크기와 성능 간 트레이드오프가 있다.
• 수학적 공격: 공개키로부터 개인키를 계산하는 시도. 수학적으로 불가능함이 증명된 적은 없다.
• 확률적 메시지 공격 (Probable-message attack): 짧은 메시지(예: 56비트 DES 키)를 모든 가능한 값으로 암호화하여 전송된 암호문과 매칭. 랜덤 비트를 추가하여 방어한다.

---

9.2 RSA 알고리즘

알고리즘 설명

1977년 Rivest, Shamir, Adleman(MIT)이 개발한, 가장 널리 사용되는 공개키 암·복호화 알고리즘이다. 평문과 암호문은 $0$부터 $n - 1$ 사이의 정수이며, 전형적인 $n$의 크기는 1024비트 이상이다.

키 생성:

단계	내용	공개/비밀
1	두 소수 $p$, $q$ 선택	비밀
2	$n = p \times q$	공개
3	$\phi(n) = (p-1)(q-1)$	—
4	$\gcd(\phi(n), e) = 1$, $1 < e < \phi(n)$인 $e$ 선택	공개
5	$d \equiv e^{-1} \pmod{\phi(n)}$ 계산	비밀

• 공개키: $PU = \{e, n\}$
• 개인키: $PR = \{d, n\}$

$\text{암호화: } C = M^e \bmod n$

$\text{복호화: } M = C^d \bmod n$

RSA가 성립하는 이유

$e$와 $d$는 $\phi(n)$에 대한 곱셈 역원, 즉 $ed \equiv 1 \pmod{\phi(n)}$이다. 오일러 정리에 의해 $M^{ed} \bmod n = M$이 성립한다.

예시 ($p = 17$, $q = 11$)

$n = 187, \quad \phi(n) = 160, \quad e = 7, \quad d = 23$

$PU = \{7, 187\}, \quad PR = \{23, 187\}$

$M = 88 \;\longrightarrow\; C = 88^{7} \bmod 187 = 11$

$C = 11 \;\longrightarrow\; M = 11^{23} \bmod 187 = 88$

계산적 측면

고속 모듈러 지수 연산

$a^b \bmod n$을 계산할 때, $b$를 이진수 $b_k b_{k-1} \cdots b_0$으로 표현한 뒤 비트별 제곱·곱셈을 반복한다.

$a^b \bmod n = \left(\prod_{b_i \neq 0} a^{2^i} \bmod n\right) \bmod n$

예를 들어 $x^{16}$은 일반적으로 15회 곱셈이 필요하지만, 반복 제곱 $x^2 \to x^4 \to x^8 \to x^{16}$으로 4회로 축소된다.

공개키 연산 효율화

$e = 65537 = 2^{16} + 1$을 자주 사용한다. 이진 표현에 $1$인 비트가 2개뿐이므로 곱셈 횟수가 최소화된다. 다른 선택지로 $e = 3$이나 $e = 17$이 있다.

$e = 3$의 취약점

3명의 서로 다른 사용자(모두 $e = 3$)에게 동일 메시지 $M$을 보내면, 공격자는 $C_1 = M^3 \bmod n_1$, $C_2 = M^3 \bmod n_2$, $C_3 = M^3 \bmod n_3$로부터 CRT를 이용해 $M^3 \bmod (n_1 n_2 n_3)$를 구한 뒤, $M < n_i$이므로 단순히 세제곱근을 취해 $M$을 복원할 수 있다. 랜덤 패딩으로 방어한다.

개인키 연산 효율화 (CRT 활용)

$C^d \bmod n$을 직접 계산하는 대신, 페르마 소정리를 활용하여:

$V_p = C^{d \bmod (p-1)} \bmod p, \quad V_q = C^{d \bmod (q-1)} \bmod q$

CRT로 $M$을 복원하면 약 4배 속도 향상된다.

키 생성 — 소수 찾기

원하는 크기의 홀수를 랜덤으로 뽑아 밀러-라빈(Miller-Rabin) 등 확률적 소수 판정 테스트를 수행한다. 소수 정리에 의해, $N$ 근처의 소수는 평균 $\ln(N)$개마다 하나씩 존재한다. 따라서 $2^{200}$ 근처의 소수를 찾으려면 평균 약 $\ln(2^{200})/2 \approx 70$번 시도하면 된다.

$e$와 $d$의 결정에는 확장 유클리드 알고리즘을 사용한다. 이 알고리즘은 $\gcd(\phi(n), e)$와 $e^{-1} \bmod \phi(n)$을 동시에 계산한다. 두 랜덤 수가 서로소일 확률은 약 $0.6$이므로 소수의 시도만 필요하다.

RSA의 보안

다섯 가지 공격 접근법이 있다:

공격 유형	설명
무차별 대입	가능한 모든 개인키를 시도 → 큰 키로 방어
수학적 공격	$n$을 소인수분해하여 $p$, $q$ 발견
타이밍 공격	복호화 소요 시간의 차이를 분석하여 키 비트 추론
하드웨어 오류 공격	프로세서 전원을 조작하여 서명 생성 중 오류 유도
선택 암호문 공격 (CCA)	RSA의 곱셈적 성질을 악용

소인수분해 문제

RSA 수학적 공격의 세 가지 접근:

1. $n$을 소인수분해하여 $p$, $q$ 발견 → $\phi(n) = (p-1)(q-1)$ 계산 → $d \equiv e^{-1} \pmod{\phi(n)}$
2. $\phi(n)$을 직접 결정 (소인수분해와 동등한 난이도)
3. $d$를 직접 결정 (소인수분해 이상으로 어려움)

해독된 RSA 챌린지	비트 수	달성 시기
RSA-129	428	1994년 4월
RSA-155	512	1999년 8월
RSA-200	663	2005년 5월
RSA-768	768	2009년 12월

768비트 해독 팀은, 1024비트 해독이 약 1000배 더 어렵지만 향후 10년 내 가능하다고 보고 1024비트 RSA의 단계적 폐지를 권고했다.

$p$, $q$ 선택 시 추가 제약

1. $p$와 $q$의 길이 차이가 소수 자릿수 이내여야 한다.
2. $(p-1)$과 $(q-1)$ 각각에 큰 소인수가 포함되어야 한다.
3. $\gcd(p-1, q-1)$이 작아야 한다.
4. $e < n$이고 $d < n^{1/4}$이면 $d$를 쉽게 결정할 수 있으므로 주의.

타이밍 공격

Paul Kocher가 시연한 공격. 컴퓨터의 복호화 소요 시간을 관측하여 개인키를 비트별로 추론한다. 고속 지수 알고리즘에서 비트가 $1$인 경우 추가 모듈러 곱셈이 발생하므로, 특정 반복에서 시간이 길어지면 해당 비트가 $1$이라고 판단한다.

대응책 세 가지:

• 상수 시간 연산: 모든 지수 연산이 동일 시간 소요하도록 강제. 단순하지만 성능 저하.
• 랜덤 지연: 무작위 지연을 추가하여 타이밍 분석 교란. 노이즈가 충분하지 않으면 추가 측정으로 극복 가능.
• 블라인딩 (Blinding): 가장 효과적. 암호문에 랜덤 값을 곱하여 내부 처리 비트를 숨긴다.

$C' = C \cdot r^e \bmod n$

$M' = (C')^d \bmod n$

$M = M' \cdot r^{-1} \bmod n$

$r^{ed} \bmod n = r$이므로 올바른 결과를 얻는다. RSA Data Security는 이 기법을 제품에 포함하며, 약 2~10%의 성능 비용을 보고했다.

하드웨어 오류 기반 공격

프로세서의 전원을 조작하여 RSA 서명 생성 중 단일 비트 오류를 유도한다. 약 100시간 만에 1024비트 개인키를 추출한 사례가 보고되었다. 공격자가 물리적 접근과 전원 제어가 필요하므로 심각한 위협은 아니다.

선택 암호문 공격 (CCA)과 OAEP

기본 RSA는 다음과 같은 곱셈적 성질을 가진다:

$E(PU, M_1) \cdot E(PU, M_2) = E(PU, M_1 \cdot M_2)$

이를 악용하여, $C = M^e \bmod n$를 다음과 같이 해독할 수 있다:

1. $X = (C \cdot 2^e) \bmod n$ 계산
2. $X$를 선택 암호문으로 제출하면 $Y = X^d \bmod n = (2M) \bmod n$을 얻음
3. $M$을 복원

OAEP (Optimal Asymmetric Encryption Padding)

이 공격을 방어하기 위해 RSA Security는 OAEP를 권장한다. 절차는 다음과 같다:

1. 선택적 파라미터 $P$의 해시값에 0을 패딩하여 데이터 블록 $DB$ 생성
2. 랜덤 시드를 MGF(마스크 생성 함수)에 통과시켜 $DB$와 XOR → $\text{maskedDB}$
3. $\text{maskedDB}$를 다시 MGF에 통과시켜 시드와 XOR → $\text{maskedseed}$
4. $EM = \text{maskedseed} \| \text{maskedDB}$
5. $EM$을 RSA로 암호화

시드가 매번 달라지므로 동일 메시지를 두 번 암호화해도 다른 암호문이 생성되어 곱셈적 성질 기반 공격이 무효화된다.

---

주요 용어

한글	영문
선택 암호문 공격	chosen ciphertext attack (CCA)
전자서명	digital signature
키 교환	key exchange
단방향 함수	one-way function
최적 비대칭 암호화 패딩	optimal asymmetric encryption padding (OAEP)
개인키	private key
공개키	public key
공개키 암호	public-key cryptography
RSA	RSA
타이밍 공격	timing attack
트랩도어 단방향 함수	trap-door one-way function