공개키 암호가 필요한 이유

05편에서 대칭키 암호의 근본 약점이 키 분배 문제임을 확인했다. 두 사람이 안전하게 통신하려면 사전에 같은 비밀키를 공유해야 하는데, 인터넷처럼 사전에 만난 적 없는 두 사람 사이에서는 이 공유 자체가 도청 위험에 노출된다. 공개키 암호(public-key cryptography, 비대칭키 암호라고도 함)는 1976년 디피(Diffie)와 헬만(Hellman)이 제안한 개념으로, 이 문제를 근본적으로 다른 방식으로 해결한다.

쉽게 말하면: 공개키 암호는 “누구나 넣을 수 있지만(공개키로 잠그기) 나만 열 수 있는(개인키로 열기) 우편함”과 같다.

공개키 암호의 구조: 키쌍

공개키 암호에서는 각 사용자가 수학적으로 연결된 키쌍(key pair)을 갖는다.

• 공개키(public key): 누구에게나 공개해도 되는 키. 상대방이 나에게 보낼 메시지를 암호화할 때 사용한다.
• 개인키(private key, 비밀키라고도 하나 대칭키의 “비밀키”와 구분하기 위해 이 문서에서는 “개인키”로 통일한다): 오직 본인만 보관하는 키. 공개키로 암호화된 메시지를 복호화할 때 사용한다.

두 키는 수학적으로 짝지어져 있어 한 키로 암호화한 것은 반드시 짝이 되는 다른 키로만 복호화할 수 있다. 이 성질 덕분에 사전에 비밀 채널로 키를 나눌 필요가 없다 — 공개키는 게시판에 올려도 되고, 개인키만 본인이 지키면 되므로 키 분배 문제가 대칭키보다 근본적으로 가벼워진다.

RSA: 실제 작은 소수로 키를 만들어 본다

RSA(Rivest, Shamir, Adleman 세 발명자의 이름 첫 글자)는 가장 널리 쓰인 공개키 암호 알고리즘이다. 안전성은 두 개의 큰 소수를 곱한 값을 다시 소인수분해하기가 계산적으로 매우 어렵다는 사실(소인수분해 문제, factoring problem)에 기반한다. 실제로는 수백 자리 소수를 쓰지만, 원리를 이해하기 위해 교과서에서 널리 쓰는 **아주 작은 소수 $p=61$, $q=53$**으로 키 생성부터 암복호화까지 전 과정을 직접 계산해 본다.

1단계 — 두 소수 선택과 $n$ 계산

• $n$: 공개키·개인키에 공통으로 쓰이는 법(modulus, 나머지 연산의 기준이 되는 수). 실제 RSA에서는 이 $n$을 소인수분해해 $p$, $q$를 알아내는 것이 공격자의 목표이며, $n$이 충분히 크면(현재 권장 2048비트 이상) 현실적인 시간 안에 풀 수 없다.

2단계 — 오일러 피 함수 계산

• $\varphi(n)$(파이 함수, 오일러 토션트 함수라고 읽는다): $1$부터 $n-1$까지의 수 중 $n$과 서로소(공약수가 1뿐인 관계)인 수의 개수. $p$, $q$가 소수일 때는 $(p-1)(q-1)$로 간단히 계산된다.

3단계 — 공개 지수 $e$ 선택

• $e$: 공개키를 구성하는 값. $1 < e < \varphi(n)$이면서 $e$와 $\varphi(n)$이 서로소여야 한다. $17$은 소수이고 $3120 = 2^4 \times 3 \times 5 \times 13$의 소인수 어느 것과도 겹치지 않으므로 서로소 조건을 만족한다.

4단계 — 개인 지수 $d$ 계산

$d$는 $e \times d \equiv 1 \pmod{\varphi(n)}$을 만족하는 값, 즉 $e$의 모듈러 역원(modular inverse)이다. 확장 유클리드 알고리즘으로 구하면 다음과 같다.

검산해 보면 $17 \times 2753 = 46801$이고, $46801 \div 3120 = 15 \text{ 나머지 } 1$이므로 $17 \times 2753 \equiv 1 \pmod{3120}$이 성립한다.

• 공개키: $(e, n) = (17, 3233)$ — 상대방에게 공개한다.
• 개인키: $(d, n) = (2753, 3233)$ — 본인만 보관한다.

5단계 — 암호화

평문을 숫자 $m = 65$ (알파벳 “A”의 아스키(ASCII) 코드 값이라고 생각해도 좋다)라 하자. 암호화는 다음 식으로 이루어진다.

$65^{17}$을 직접 계산하면 매우 큰 수가 되지만, 모듈러 거듭제곱(modular exponentiation)을 이용해 중간중간 3233으로 나눈 나머지만 유지하며 계산하면 실제로는 다음 값이 나온다.

즉 공개키 $(17, 3233)$로 평문 $65$를 암호화하면 암호문 $2790$이 된다.

6단계 — 복호화

개인키로 복호화하면 원래 평문이 정확히 복원되어야 한다.

이 값이 다시 $65$로 돌아오는 이유는 오일러의 정리(Euler’s theorem)에 의해 $m^{e \cdot d} \equiv m \pmod{n}$이 성립하기 때문이다 — $e \cdot d \equiv 1 \pmod{\varphi(n)}$로 설계했으므로, 지수 부분이 결국 $m^1 = m$으로 정리된다. 이 “지수를 곱하면 1로 되돌아온다”는 관계가 RSA 전체의 수학적 근거이며, 시험에서 “왜 복호화가 원래 평문을 복원하는가”를 물을 때의 정답 근거가 된다.

RSA 안전성의 핵심

공격자가 공개키 $(e, n) = (17, 3233)$만 보고 개인키 $d$를 알아내려면, $n = 3233$을 소인수분해해 $p=61$, $q=53$을 찾아야 한다. 이 예시는 숫자가 작아 손으로도 풀리지만($3233 = 61 \times 53$), 실제 RSA는 $n$이 617자리(2048비트) 이상이어서 현재 컴퓨팅 성능으로는 사실상 풀 수 없다. RSA의 안전성은 이 대규모 소인수분해의 계산적 어려움에 전적으로 의존한다는 것이 핵심 개념이다.

디피-헬만(Diffie-Hellman) 키교환: 실제 숫자로

RSA가 “암호화·복호화” 용도라면, 디피-헬만 키교환(Diffie-Hellman Key Exchange, DH)은 암호화 자체를 하지 않고도 두 사람이 공개된 통신선을 통해 같은 비밀값(공유 비밀, shared secret)에 합의하는 프로토콜이다. 이렇게 만든 공유 비밀을 이후 대칭키(05편의 AES 등)의 세션 키로 사용하는 것이 실무의 표준 흐름이다.

쉽게 말하면: 서로 다른 두 가지 색 페인트를 몰래 섞어도, 특정 순서로 섞으면 도청자는 알 수 없지만 두 사람만 같은 색을 다시 만들어낼 수 있는 방식이다.

공개 값 합의

두 사람(전통적으로 앨리스Alice와 밥Bob으로 부른다)은 먼저 공개된 두 값을 정한다. 도청자가 봐도 상관없다.

• $p$: 나머지 연산의 기준이 되는 소수
• $g$: 생성자(generator). $g$의 거듭제곱을 $p$로 나눈 나머지가 $1$부터 $p-1$까지 골고루 나오게 하는 특별한 성질을 가진 수

각자의 개인 값 선택과 공개 값 계산

앨리스는 자신만 아는 개인 값 $a=6$을 고른 뒤 공개 값을 계산해 밥에게 보낸다.

밥은 자신만 아는 개인 값 $b=15$를 고른 뒤 공개 값을 계산해 앨리스에게 보낸다.

여기서 통신선을 통해 오간 값은 $p=23$, $g=5$, $A=8$, $B=19$뿐이다. $a=6$과 $b=15$는 각자 머릿속에만 있고 한 번도 전송되지 않는다.

공유 비밀 계산

이제 앨리스는 밥의 공개 값 $B$를 받아 자신의 개인 값 $a$로 거듭제곱하고, 밥은 앨리스의 공개 값 $A$를 받아 자신의 개인 값 $b$로 거듭제곱한다.

두 사람이 계산한 값이 **똑같이 $2$**로 일치한다. 이는 지수법칙 $(g^b)^a = g^{ab} = (g^a)^b$이 성립하기 때문이다 — 곱셈의 순서를 바꿔도 결과가 같다는 아주 단순한 원리가 이 프로토콜 전체를 지탱한다.

왜 도청자는 이 값을 계산할 수 없는가

도청자는 $p=23$, $g=5$, $A=8$, $B=19$를 전부 볼 수 있지만, 공유 비밀 $s=2$를 얻으려면 $A=g^a \bmod p$로부터 $a$를 역으로 알아내야 한다. 이렇게 거듭제곱의 결과에서 지수를 역산하는 문제를 이산로그 문제(Discrete Logarithm Problem, DLP)라고 부르며, $p$가 충분히 크면(실제로는 2048비트 이상) 현재 알려진 방법으로는 현실적 시간 안에 풀 수 없다. 즉 RSA는 소인수분해 문제, 디피-헬만은 이산로그 문제라는 서로 다른 수학적 난제에 안전성을 의존한다는 점이 시험에서 자주 대조되는 포인트다.

디피-헬만의 한계 — 중간자 공격

디피-헬만은 공유 비밀 합의는 안전하게 해 주지만, 상대방이 정말 그 사람이 맞는지(신원 인증, authentication)는 보장하지 않는다. 공격자가 앨리스와 밥 사이에 끼어들어 앨리스에게는 “나는 밥이다”, 밥에게는 “나는 앨리스다”라고 각각 다른 키교환을 수행하면, 앨리스와 밥은 서로 통신한다고 믿지만 실제로는 둘 다 공격자와 키를 교환한 것이 된다. 이를 중간자 공격(Man-in-the-Middle Attack, MITM)이라 한다. 이 한계를 보완하기 위해 실제 프로토콜(TLS 등, 08편에서 다룸)은 디피-헬만에 전자서명이나 인증서로 신원을 확인하는 절차를 결합한다.

전자서명: 공개키 암호를 거꾸로 쓰다

전자서명(digital signature)은 공개키 암호의 키 사용 순서를 뒤집어 인증(authentication, 보낸 사람이 맞다는 확인)과 부인방지(non-repudiation, 나중에 보낸 적 없다고 발뺌하지 못하게 하는 것)를 제공하는 기술이다.

쉽게 말하면: 암호화가 “공개키로 잠그고 개인키로 연다”면, 전자서명은 “개인키로 서명하고 공개키로 확인한다” — 열쇠 사용 방향이 정반대다.

전자서명의 절차

1. 서명자는 메시지의 해시값(hash, 07편에서 자세히 다룬다. 메시지를 고정 길이의 짧은 값으로 요약한 것)을 계산한다.
2. 서명자는 이 해시값을 자신의 개인키로 암호화한다 — 이 결과가 곧 전자서명이다.
3. 서명자는 원본 메시지와 전자서명을 함께 전송한다.
4. 검증자는 받은 메시지의 해시값을 직접 계산하고, 받은 전자서명을 서명자의 공개키로 복호화해 두 값을 비교한다.
5. 두 값이 같으면 서명이 유효하다 — 이 메시지는 서명자의 개인키를 가진 사람만 만들 수 있으므로, 서명자 본인이 작성했고(인증) 이후 변경되지 않았다는(무결성) 것이 동시에 증명된다.

여기서 개인키는 오직 서명자 본인만 가지고 있으므로, 서명자는 나중에 “나는 서명한 적 없다”고 주장할 수 없다 — 이것이 부인방지가 성립하는 근거다. 반면 단순 암호화(공개키로 잠그고 개인키로 열기)는 “누가 보냈는지” 증명하지 못한다는 점과 정확히 대비된다. 이 차이는 07편에서 해시·MAC·전자서명을 정면으로 비교할 때 다시 정리한다.

자주 틀리는 점

• RSA에서 “공개키로 암호화, 개인키로 복호화”만 외우고 전자서명에서는 방향이 반대(개인키로 서명, 공개키로 검증)라는 점을 놓치는 경우가 많다.
• 디피-헬만을 “암호화 알고리즘”으로 착각하는 경우 — DH는 메시지를 암호화하는 것이 아니라 공유 비밀에 합의하는 프로토콜이다.
• “공개키 암호는 완벽히 안전해서 인증이 필요 없다”는 오해 — 순수 디피-헬만은 인증 기능이 없어 중간자 공격에 취약하며, 실제로는 인증서(08편)와 결합해야 한다.
• RSA의 안전성 근거를 “키 길이가 길어서”로만 답하는 경우 — 정확한 근거는 큰 수의 소인수분해가 계산적으로 어렵다는 수학적 난제다.

핵심 정리

• 공개키 암호는 공개키·개인키로 이루어진 키쌍을 쓰며, 사전 비밀 공유 없이도 안전한 통신을 가능하게 한다.
• RSA는 $n=p \times q$, $\varphi(n)=(p-1)(q-1)$, $e \cdot d \equiv 1 \pmod{\varphi(n)}$의 관계로 키를 만들고, 안전성은 $n$의 소인수분해 난이도에 의존한다.
• 디피-헬만은 이산로그 문제에 기반해 공개된 통신선에서도 공유 비밀을 안전하게 합의하지만, 신원 인증 기능이 없어 중간자 공격에 취약하다.
• 전자서명은 개인키로 서명하고 공개키로 검증해 인증과 부인방지를 제공한다 — 암호화(공개키로 잠그고 개인키로 열기)와 키 사용 방향이 반대다.

마무리 복습

참고 자료

• NIST — Cryptographic Standards and Guidelines 
• 국가평생교육진흥원 독학학위제