쇼어 알고리즘과 RSA: 양자컴퓨터가 암호를 깨는 원리와 주기 찾기

핵심 메시지

• 쇼어 알고리즘은 RSA 같은 공개키 암호의 근간인 '정수 인수분해' 문제를 이론적으로 빠르게 풀어 암호를 깰 수 있는 양자 알고리즘이다.
• 핵심은 인수분해를 '주기 찾기(period finding)' 문제로 바꾸는 재구성이며, 이 부분은 양자역학 없이도 성립하는 우아한 고전적 아이디어다.
• 실제 주기를 찾는 무거운 계산만 양자컴퓨터가 담당하고, 앞뒤 단계는 고전 컴퓨터가 처리한다.
• 양자컴퓨터의 '마법'은 평행우주가 아니라 파동의 중첩과 간섭이며, 위상을 제어해 원하는 답이 드러나게 만든다.
• 지금 양자컴퓨터는 잡음이 커서 15 정도밖에 인수분해하지 못하지만, 언젠가 커질 것에 대비해 암호 체계를 미리 고민해야 한다.

쉽게 이해하기

이 영상은 컴퓨터파일이 컴퓨터과학자와 물리학자를 함께 불러 쇼어 알고리즘을 설명한다. 먼저 왜 이 알고리즘이 중요한지 RSA 암호를 통해 짚는다. RSA는 인터넷 곳곳의 디지털 서명·인증서에 쓰이는 대표적 공개키(비대칭) 암호로, 개인키로 서명하고 공개키로 검증하는 방식이다.

RSA의 안전성은 정수 인수분해의 어려움에 기댄다. 공개키에 들어 있는 큰 반소수 N은 두 소수 P와 Q의 곱인데, P와 Q는 비밀이다. 만약 N을 인수분해해 P와 Q를 얻으면 개인키를 유도할 수 있고, 그러면 특정 사이트의 서명을 위조하거나 가짜 사이트·피싱을 훨씬 쉽게 벌일 수 있다. 현실적인 키 크기에서는 이 인수분해가 사실상 수억 년이 걸릴 만큼 어렵다.

쇼어의 통찰은 이 어려운 문제를 우회하는 것이다. 임의의 A를 골라 A의 거듭제곱을 N으로 나눈 나머지를 계산하면, 값이 1에서 출발해 여러 수를 거쳐 다시 1로 돌아오는 주기적 함수가 된다. 영상은 N=15, A=2일 때 나머지가 1, 2, 4, 8, 1, 2, 4, 8…로 반복되어 주기 R=4임을 보여준다. 주기 R(짝수)만 찾으면 제곱의 차 공식을 통해 gcd 계산으로 P와 Q가 바로 튀어나온다. 예시에서 2^(4/2)+1=5, gcd(5,15)=5로 소인수 3과 5를 얻는다.

문제는 실제 N이 약 2,000비트, 곧 600자리에 이르는 거대한 수라는 점이다. 고전 컴퓨터로는 이 함수의 주기를 무차별 계산으로 찾을 수 없다. 여기서 양자컴퓨터가 등장한다. 물리학자는 주기 찾기를 푸리에 변환으로 설명하는데, 복잡한 패턴을 사인·코사인 파동의 합으로 분해해 어떤 주파수(반복 횟수)가 들어 있는지 알아내는 방식이다. 이는 JPEG이 이미지를 압축하는 원리와도 같다.

양자 부분의 핵심은 파동의 중첩과 간섭이다. 위상을 어긋나게 하면 상쇄 간섭, 맞추면 보강 간섭이 일어나며 이는 신호발생기와 오실로스코프로도 보이는 순수한 고전 물리다. 트랩된 이온 방식 양자컴퓨터는 초고진공·저온에 가둔 이온의 두 에너지 상태를 큐비트의 0과 1로 삼고, 정밀한 마이크로파 펄스로 상태 확률을 조절한 뒤 레이저로 광자를 세어 측정한다. 측정은 파동함수를 붕괴시키므로 매번 다시 준비해 반복·평균해야 하는 확률적 과정이다. 다만 발표자들은 이 모든 일이 무수한 평행우주가 아니라 '이 우주 하나'에서 일어난다고 거듭 강조한다.

주요 인사이트

• 쇼어 알고리즘의 진짜 우아함은 양자역학이 아니라 문제 재구성에 있다. 인수분해를 주기 찾기로 바꾸는 고전적 단계 덕분에, 주기라면 자신 있는 양자컴퓨터의 강점을 끌어다 쓸 수 있게 된다.
• N=15 예시는 답이 눈에 보여 교육적이지만, 바로 그 때문에 충격이 덜하다. 중요한 점은 4비트든 4,096비트든 적용하는 펄스·대기·측정의 순서가 동일하다는 것이다. 답을 미리 알아서가 아니라, 푸리에 변환이 주파수(주기)를 드러내주기 때문에 답이 튀어나온다.
• 양자컴퓨팅을 '평행우주에서 계산한다'는 식으로 이해하면 오해다. 발표자는 지도(수학 모델)와 실제 영토(현실)를 혼동하지 말라고 경고하며, 관측된 근거 없는 다세계 해석을 사실처럼 말하지 말라고 지적한다.
• 당장의 위협은 제한적이다. 잡음과 오류 정정 부담 때문에 현재 양자컴퓨터는 15 남짓만 인수분해할 수 있다. 그러나 충분히 큰 기기가 5년, 20~30년, 혹은 수백 년 뒤 언제 등장할지 모르기에, 암호학은 그 전에 대비를 시작할 이유가 있다.

자주 묻는 질문

관련 AI 소식