Q-Day Prize는 왜 실패했을까 - 양자컴퓨터가 RSA를 깰 날은 아직 한참 멀었다

Q-Day Prize가 뭔가요?

작년에 Project 11이라는 단체가 "Q-Day Prize"라는 흥미로운 상금을 내걸었어요. 내용은 간단해요. 양자컴퓨터로 비트코인이 사용하는 ECDSA 키를 가장 먼저 깨는 팀에게 상금을 주겠다. 이걸 통해 "양자컴퓨터가 정말 암호를 깰 수 있는 시대가 왔는지"를 공개적으로 검증해 보자는 취지였어요.

그리고 그 마감 시한이 지났는데, 결과는 다들 짐작하시는 대로예요. 아무도 깨지 못했어요. 그런데 이 결과를 두고 구글의 양자컴퓨팅 연구자 Craig Gidney가 "이건 실패할 수밖에 없는 시도였다"라는 분석 글을 올렸어요. 이게 단순히 "거봐 안 되잖아"가 아니라, 양자컴퓨팅의 현재 위치를 정확히 짚어주는 좋은 글이라 풀어볼게요.

양자컴퓨터가 RSA를 깬다는 게 무슨 뜻인가요?

현대 인터넷의 거의 모든 보안은 "큰 수를 소인수분해 하기는 어렵다"는 수학적 사실에 기대고 있어요. RSA, ECDSA 같은 알고리즘이 다 그래요. 그런데 1994년에 수학자 Peter Shor가 "양자컴퓨터가 있다면 이걸 다항시간 안에 풀 수 있다"는 알고리즘을 발표했어요. 이걸 "Shor's algorithm"이라고 해요. 그래서 사람들이 "언젠가 양자컴퓨터가 충분히 커지면 인터넷 보안이 다 무너진다"고 걱정하기 시작한 거예요.

그 "언젠가"가 바로 Q-Day예요.

그런데 왜 아직도 한참 멀었나

Gidney의 분석에서 핵심은 "논리 큐비트(logical qubit)"와 "물리 큐비트(physical qubit)"의 차이예요. 한번 풀어볼게요.

양자컴퓨터의 큐비트는 노이즈에 정말 약해요. 주변에 작은 진동만 있어도 계산이 어긋나요. 그래서 "오류 정정(quantum error correction)"이라는 기술을 써요. 이게 뭐냐면, 안정적인 "논리 큐비트 1개"를 만들기 위해서 노이즈 많은 "물리 큐비트" 수천 개를 묶어 쓰는 거예요. 마치 흔들리는 사진 1000장을 평균 내서 한 장의 또렷한 사진을 얻는 것과 비슷해요.

현재 RSA-2048을 깨려면 논리 큐비트가 수천~수만 개 필요하고, 그러려면 물리 큐비트가 수백만 개에서 천만 개 단위로 있어야 해요. 그런데 지금 세계 최고 수준인 IBM, Google이 만든 양자컴퓨터의 물리 큐비트는 1,000개 안팎이에요. 세 자릿수 정도가 부족한 게 아니라, 네 자릿수가 부족한 상태예요. 비트코인 ECDSA는 RSA-2048보다 살짝 깨기 쉽다고 해도, 여전히 수십만~수백만 큐비트가 필요해요.

Gidney가 글에서 강조하는 건 "이게 단순히 기다리면 되는 문제가 아니라, 큐비트 수를 늘리는 동시에 오류율도 같이 낮춰야 하는 두 축의 문제"라는 점이에요. 큐비트만 많아져도 안 되고, 정확도만 높아져도 안 돼요. 둘이 같이 가야 하는데, 둘 다 매우 어려워요.

그럼 양자컴퓨팅이 사기인가요?

그건 아니에요. Gidney 본인도 구글에서 양자컴퓨터를 만드는 사람이고, 분야는 꾸준히 진보하고 있어요. 다만 "내년쯤이면 비트코인이 깨진다"는 식의 자극적인 뉴스는 현실과 동떨어져 있다는 게 그의 메시지예요. 진짜 Q-Day가 온다면 그건 적어도 10년에서 20년 이상의 시간 후에 가까울 거예요.

그래도 "포스트 양자 암호"는 지금 준비해야 한다

역설적인 건, 그래서 지금부터 대비해야 한다는 거예요. 왜냐하면 "지금 통신을 가로채서 저장해 뒀다가, 미래에 양자컴퓨터로 푼다(harvest now, decrypt later)"는 공격이 가능하거든요. 그래서 미국 NIST는 이미 CRYSTALS-Kyber, CRYSTALS-Dilithium 같은 "포스트 양자 암호(PQC)" 표준을 발표했고, 클라우드플레어, 구글, AWS 같은 곳들이 TLS에 PQC를 도입하기 시작했어요.

한국 개발자에게 주는 시사점

실무에서는 두 가지를 챙기시면 좋아요. 첫째, "양자컴퓨터로 RSA가 깨진다"는 식의 보고서가 회사 보안팀에서 나올 때, 시점을 차분하게 평가할 수 있어야 해요. 사기성 마케팅도 종종 있거든요. 둘째, TLS 라이브러리의 포스트 양자 암호 지원을 미리 점검해 두세요. OpenSSL 3.x, BoringSSL 등이 PQC 지원을 추가하고 있어서, 장기적으로 인증서나 키 교환 알고리즘을 갈아끼울 준비를 해두면 좋아요.