소수가 지키는 비밀

두 소수의 곱으로 잠그고, 그 곱을 다시 풀 수 없게 만드는 암호

단계 1

두 소수를 고른다

RSA는 두 소수 p, q의 곱 N = p · q를 만드는 것에서 시작한다. 너무 작으면 안전하지 않고, 너무 크면 한눈에 보기 어렵다. 학습용으로 두 자리 소수를 골라 본다.

p (첫 번째 소수) q (두 번째 소수)

예시 11, 13 61, 53 101, 103 467, 389

단계 2

두 소수를 곱해 N을 만든다

N은 공개해도 되는 자물쇠 번호다. 다른 사람이 N을 보더라도 p와 q로 다시 쪼개기 어렵다는 점이 RSA의 핵심이다.

N = p × q = 61 × 53 = 3233

단계 3

공개키와 개인키를 만든다

공개키는 모두에게 알려 주는 자물쇠, 개인키는 자기만 가지는 열쇠다. 둘 다 N과 짝을 이루어 사용된다. 자세한 계산은 컴퓨터가 알아서 해 주니 결과만 보면 된다.

단계 4

메시지를 암호화한다

각 글자를 숫자로 바꾼 다음, 공개키로 잠근 새 숫자를 만든다. 받는 사람의 공개키만 있으면 누구나 잠글 수 있다.

평문

단계 5

메시지를 복호화한다

개인키를 가진 사람만 잠긴 숫자를 원래 글자로 되돌릴 수 있다. 다른 사람은 N을 알아도 풀 수 없다.

왜 이 게임인가

RSA의 안전은 이 문제에 달려 있다

두 소수를 곱하는 것은 쉽지만, 곱셈 결과만 보고 원래 두 소수를 알아내는 것은 어렵다. 이 비대칭성이 RSA를 지킨다. 직접 N을 받고 p와 q를 찾아 보자.

남은 시간

--:--

점수

평균 풀이 시간

—

시도

쉬움두 자리 · 60초

보통세 자리 · 120초

어려움네 자리 · 180초

다음 수를 두 소수의 곱으로 나타내라

— · —

N = p × q (둘 다 소수)

시도 기록

아직 시도한 기록이 없다. 게임을 시작하면 여기에 쌓인다.

—

두 자리 소수의 곱

사람이 종이로도 금방 풀 수 있다. 컴퓨터는 거의 0초.

—

네 자리 소수의 곱

사람에게는 매우 어렵다. 컴퓨터는 여전히 한순간에 끝낸다.

—

여섯 자리 소수의 곱

사람이 직접 풀기는 사실상 불가능하다. 컴퓨터에게도 일이 늘어난다.

자릿수에 따른 인수분해 시간

자릿수가 커질수록 걸리는 시간이 가파르게 늘어난다

키 크기	N의 자릿수	분해에 걸리는 시간	실용성
RSA-128	약 39자리	수 분	이미 깨짐
RSA-512	약 155자리	수 일 ~ 수 주	이미 깨짐 (1999)
RSA-1024	약 309자리	수 년 (국가급 자원)	권장하지 않음
RSA-2048	약 617자리	슈퍼컴으로도 비현실적	현재 표준
RSA-4096	약 1233자리	우주 나이의 수십억 배	장기 안전

질문

양자 컴퓨터가 나오면 RSA는 끝인가

결론부터 말하면 그렇다. 다만 그 전에 대비는 이미 시작되고 있다.

쇼어 알고리즘

1994 피터 쇼어

피터 쇼어가 1994년에 제안한 방법. 일반 컴퓨터는 큰 N을 두 소수로 쪼개는 데 엄청난 시간이 걸리지만, 양자 컴퓨터는 같은 일을 매우 짧은 시간에 끝낼 수 있다.

다시 말해, 지금까지 RSA를 안전하게 지켜 주던 “소인수분해가 어렵다”는 전제가 무너진다.

단, 실제로 RSA-2048을 깨려면 매우 큰 양자 컴퓨터가 필요하다. 2026년 기준 가장 큰 양자칩도 그 규모에는 한참 못 미치기 때문에 아직 갈 길이 멀다.

양자 내성 암호

NIST 2024 표준화 완료

양자 컴퓨터가 풀기 어려운 새로운 종류의 수학 문제를 활용해 만든 암호. 미국 NIST가 2024년 8월에 첫 표준 세 가지를 확정했다.

이름이 어렵지만 핵심은 “양자 컴퓨터가 나와도 안전한 다른 자물쇠를 미리 만들어 두자”는 것이다.

애플은 이미 2024년 메시지 앱에 새 방식을 적용했고, 구글과 시그널, 클라우드플레어도 도입을 진행 중이다. RSA에서 양자 내성 암호로의 전환은 앞으로 5~10년에 걸쳐 천천히 이루어질 전망이다.

주의

지금 수확, 나중에 해독

국가급 공격자는 오늘 암호화된 통신을 그대로 저장해 두고, 양자 컴퓨터가 실용화될 때 한꺼번에 복호화하려 한다. 의료 기록이나 국가 기밀처럼 수십 년이 지나도 가치 있는 데이터는 지금 당장 양자 내성 암호로 옮기는 것이 안전하다.