보훔대·막스플랑크 연구진, 타원곡선암호 푸는 새 알고리즘 제시
양자 공격 회로 비용, 구글 추정치 대비 70% 감소
앨리스앤밥 "캣 큐비트 3만개 미만으로 1시간 내 해독"
[블록미디어 이혜연 기자] 샤를 기예메(Charles Guillemet) 레저 최고기술책임자(CTO)가 비트코인(BTC)을 비롯한 디지털자산(가상자산)의 보안 기반을 흔들 수 있는 암호학 연구 성과 2건을 짚으며 경고에 나섰다. 하나는 비트코인 보안의 근간인 타원곡선암호(ECC)의 수학적 난제를 더 쉽게 풀 수 있다는 연구이고, 다른 하나는 양자컴퓨터로 타원곡선암호를 공격하는 데 필요한 자원이 크게 줄었다는 연구다.
기예메 CTO는 30일(현지시각) 엑스(X)에 올린 글에서 “디지털자산 시장에 힘든 한 주였다고 생각했나. 진짜 뉴스는 놓쳤을지도 모른다”고 밝혔다.
새 알고리즘 등장…양자 공격 비용 70% 줄어
첫 번째는 독일 보훔 루르대학교와 막스플랑크 보안·프라이버시연구소 연구진이 공개한 ‘타원곡선 이산로그 문제를 위한 준지수 시간 알고리즘(A Subexponential Time Algorithm for Elliptic Curve Discrete Logarithm)’ 논문이다.
타원곡선암호는 ‘타원곡선 이산로그 문제’를 현실적으로 풀 수 없다는 점에 보안을 기대고 있다. 지금까지 이 문제를 푸는 가장 좋은 일반적 방법은 폴라드 로(Pollard’s rho) 알고리즘이었는데, 키 길이가 길어질수록 계산 비용이 지수적으로 늘어나는 구조다. 연구진은 이보다 효율적으로 문제를 풀 수 있는 준지수 시간 알고리즘을 이론적으로 제시했다.
다만 큰 단서가 붙는다. 이 알고리즘은 추가 검증이 필요한 오픈AI 연구진의 또 다른 주장을 전제로 하고 있다. 기예메 CTO도 새 알고리즘이 현재 쓰이는 암호 체계를 위협하지는 않는다고 강조했다. 비트코인의 secp256k1을 비롯해 NIST P-256, Ed25519 등 널리 쓰이는 곡선에 대한 최선의 공격은 여전히 폴라드 로 알고리즘에 기반하며, 새 방식은 매우 큰 크기의 가상 곡선에서만 더 효율적이라는 설명이다. 현재로서는 이론적 성과에 그친다는 의미다.
두 번째는 양자컴퓨터로 타원곡선암호를 공격하는 효율이 크게 높아졌다는 연구다. 기예메 CTO는 타원곡선 디지털 서명(ECDSA)에 대한 양자 공격 효율을 높이기 위한 공개 연구 프로젝트 ‘ECDSA.fail’을 언급했다.
ECDSA.fail은 아이겐랩스(Eigen Labs)가 지난 5월부터 운영해 온 공개 벤치마크로, 참가자들은 쇼어(Shor) 알고리즘이 개인키를 찾아낼 때 반복하는 ‘점 덧셈’ 양자회로를 더 적은 자원으로 구현하는 경쟁을 벌이고 있다. 이달 17일 기준 147개 계정에서 1589건의 회로가 제출됐으며, 상당수 참가자가 AI 코딩 에이전트를 활용했다. 실제로 개인키를 깨는 공격이 아니라 회로 설계를 최적화하는 경쟁이라는 점에서, 이 수치가 곧바로 비트코인 해킹 가능성을 의미하지는 않는다.
기예메 CTO에 따르면 연구진은 양자회로 비용 추정치를 구글이 앞서 발표한 수치보다 약 70% 낮췄다. 논리 큐비트 수에 토폴리(Toffoli) 게이트 수를 곱한 지표 기준으로 구글 추정치는 29억9000만이었지만, 현재 추정치는 약 9억1000만까지 내려왔다.
You thought this was a bad week in crypto? You might have missed the bigger news.
Two results just landed on elliptic-curve cryptography. Both are worrying. Neither one breaks a key anyone uses today.
1️⃣ The problem under ECC is less hard than we thought.
ECC is secure because… pic.twitter.com/urLoFGdW2J
— Charles Guillemet (@P3b7_) October 30, 2026
“캣 큐비트 3만개면 1시간”…현실화는 아직
기예메 CTO가 더 중요하게 본 것은 프랑스 양자컴퓨터 기업 앨리스앤밥(Alice & Bob)의 새 논문이다. 앨리스앤밥은 물리적 ‘캣 큐비트(cat qubit)’ 3만개 미만으로 약 1시간 만에 비트코인의 secp256k1 암호를 깰 수 있다는 이론적 추정을 내놨다. 같은 논문은 RSA-2048 암호를 소인수분해하는 데에는 캣 큐비트 2만2593개와 약 3.14일이 필요하다고 추산했다.
국제암호학회(IACR) 사전공개 저장소에 올라온 이 논문은 공격에 필요한 자원을 최대 2만9588개 큐비트, 61.8분으로 제시하며 이를 상한치로 봤다. 앨리스앤밥 연구진은 2023년에는 256비트 타원곡선 문제에 캣 큐비트 12만6133개와 9시간이 필요하다고 추산했는데, 3년 만에 필요 자원이 크게 줄어든 셈이다. 캣 큐비트는 앨리스앤밥이 자체 설계한 초전도 큐비트로, 오류 정정에 필요한 물리 큐비트 수를 줄이는 방식이다.
다만 이 추정은 계산 중 비트 반전 오류가 전혀 없다는 가정을 깔고 있다. 한 시간에 한 번꼴로 비트 반전이 일어난다고 보면 RSA-2048에 필요한 큐비트는 약 4만5000개로 늘어난다. 회사 측은 1시간이 넘는 공격 시간은 비트코인의 평균 블록 생성 간격인 약 10분보다 길어, 전송 후 확정을 기다리는 거래를 노리기는 어렵다고 설명했다.
물론 이 수치들은 아직 존재하지 않는 고도의 오류 내성(fault-tolerant) 양자컴퓨터를 전제로 한다. 기예메 CTO는 이런 양자컴퓨터가 없는 만큼 비트코인에 당장의 위험은 없다고 짚었다. 다만 이번 연구들은 널리 쓰이는 암호 체계를 깨는 데 필요한 자원 추정치가 계속 줄고 있다는 점을 다시 일깨운다는 것이 그의 설명이다.
앨리스앤밥은 하드웨어 발전과 자원 추정치 하락이 2030년대 초 맞물릴 것으로 내다보며, 실제 양자 공격이 나오기 전에 양자내성암호 전환을 시작해야 한다고 촉구했다. 비트코인 업계에서도 양자 위협에 대비한 전환 논의가 이어질 전망이다.