우리가 쓰는 암호의 원리: 소인수분해와 양자컴퓨터 이야기

어느 숫자에 숨겨진 비밀 이야기

어느 날, 인터넷 쇼핑몰에서 결제를 하려다 문득 이런 생각이 들었다.
“이 수많은 사람들 속에서, 내 카드 정보는 어떻게 안전하게 지켜질까?”

화면에는 단지 자물쇠 모양 하나만 떠 있지만, 그 뒤에서는 아주 복잡한 계산이 순식간에 이루어진다. 그리고 그 계산의 출발점에는, 의외로 중학교 때 배웠던 소수가 있다.

---

1. 아주 쉬운 계산, 그런데 왜 안전할까?

소수는 1과 자기 자신으로만 나누어지는 수다.
2, 3, 5, 7 같은 숫자들은 누구에게나 익숙하다.

이 소수 두 개를 골라 곱해 보자.

• 11 × 17 = 187

이 계산은 몇 초도 걸리지 않는다.
그런데 만약 187이라는 숫자만 던져주고 “이걸 다시 소수의 곱으로 나눠봐”라고 하면, 잠깐 생각이 필요해진다.

숫자가 작을 때는 괜찮다.
하지만 이 소수들이 수백 자릿수라면 어떨까?

곱하는 건 여전히 쉽지만,
거꾸로 나누는 일은 갑자기 끝이 보이지 않는 미로가 된다.

이 불균형이 바로 암호의 출발점이다.

---

2. 암호는 “숨기는 기술”이 아니라 “늦추는 기술”

많은 사람들이 암호를 “절대 풀 수 없는 것”이라고 생각한다.
하지만 실제로는 그렇지 않다.

현대 암호는 이렇게 말한다.

“풀 수는 있다. 다만 너무 오래 걸린다.”

암호는 수학적으로 불가능한 문제를 쓰지 않는다.
대신 계산 시간이 기하급수적으로 늘어나는 문제를 선택한다.

그 대표적인 예가 바로 소인수분해다.

---

3. 공개된 비밀, 공개키 암호의 아이디어

인터넷에서는 이상한 일이 벌어진다.
우리는 서로 얼굴도 모르는 상태에서, 비밀 정보를 주고받는다.

이게 가능한 이유는 공개키 암호라는 구조 덕분이다.

이 구조는 마치 이런 이야기와 같다.

• 나는 자물쇠를 하나 만들어서 모두에게 나눠준다
• 누구든 그 자물쇠로 상자를 잠글 수 있다
• 하지만 열 수 있는 열쇠는 나만 가지고 있다

여기서 자물쇠 역할을 하는 것이
두 개의 큰 소수를 곱해 만든 숫자다.

이 숫자는 공개된다.
하지만 그 안에 어떤 소수들이 숨어 있는지는 공개되지 않는다.

---

4. 왜 고전 컴퓨터는 포기할 수밖에 없을까

고전 컴퓨터는 아주 성실하다.
가능한 경우를 하나씩 차례대로 계산한다.

소인수분해 문제 앞에서, 고전 컴퓨터는 묵묵히 말한다.
“그럼 처음부터 끝까지 다 해보자.”

문제는 경우의 수다.
숫자의 자릿수가 조금만 늘어나도, 시도해야 할 조합은 폭발적으로 증가한다.

그래서 암호는 이렇게 믿어왔다.

“이 계산은 우주의 나이보다 오래 걸릴 것이다.”

이 믿음 위에서 오늘날의 인터넷 보안이 유지되고 있다.

---

5. 갑자기 등장한 다른 사고방식, 양자컴퓨터

여기서 이야기가 바뀐다.

양자컴퓨터는 계산을 “더 빨리” 하는 기계가 아니다.
다르게 생각하는 기계다.

고전 컴퓨터가

• 한 갈래 길을 끝까지 가본 뒤
• 다시 돌아와 다음 길을 가는 방식이라면

양자컴퓨터는

• 여러 갈래 길을 한 번에 겹쳐 놓고
• 그중 의미 있는 패턴만 골라낸다

이 방식은 특히 주기성을 찾는 문제에서 강력하다.

---

6. 소인수분해의 숨겨진 얼굴

겉으로 보면 소인수분해는 “나누기 문제”처럼 보인다.
하지만 수학적으로 들여다보면, 이 문제는 주기성을 찾는 문제로 바꿀 수 있다.

양자컴퓨터는 이 주기성을 빠르게 찾아낸다.
그래서 고전 컴퓨터에게는 끝이 보이지 않던 문제가,
양자컴퓨터에게는 전혀 다른 풍경으로 보이게 된다.

이 때문에 “양자컴퓨터가 암호를 깬다”는 말이 나온다.

---

7. 그런데 지금 당장 무너질까?

이야기는 여기서 멈추지 않는다.

현실의 양자컴퓨터는 아직 미완성이다.
양자 상태는 아주 섬세해서, 작은 흔들림에도 쉽게 흐트러진다.

계산 도중 오류가 생기고,
오래 유지하기도 어렵다.

그래서 현재 우리가 쓰는 암호가
오늘이나 내일 갑자기 무너질 가능성은 크지 않다.

---

8. 암호는 이미 다음 수를 두고 있다

암호 기술은 이 가능성을 이미 알고 있었다.
그래서 새로운 수학 문제들을 준비해 두고 있다.

• 소인수분해에 의존하지 않는 방식
• 양자컴퓨터로도 빠르게 풀기 어려운 문제들

이런 암호들을 양자내성 암호라고 부른다.

즉, 이 이야기는 “종말”이 아니라
규칙이 바뀌는 장면에 가깝다.

---

마치며: 숫자는 거짓말을 하지 않는다

우리가 쓰는 암호는 눈에 보이지 않는다.
하지만 그 안에는 아주 인간적인 질문이 숨어 있다.

“무엇이 가능한가, 그리고 얼마나 오래 걸리는가?”

소인수분해는 그 질문에 오랫동안 안전한 답을 주었다.
양자컴퓨터는 그 답을 다시 생각하게 만들고 있다.

다만 한 가지는 분명하다.
암호는 언제나 계산 능력의 경계선에서 진화해 왔고,
이번에도 그 경계선을 한 걸음 옮기고 있을 뿐이다.