이 엔지니어를 위한 이야기 공장 AI 기술에 인문학의 온기를

딥마인드 AI가 33년 만에 내린 인수분해 비용

딥마인드 AI가 33년 만에 내린 인수분해 비용

구글 딥마인드가 11월 6일 레거시 1024비트 RSA에서 두 가지 암호해독 진전을 냈다고 발표했습니다. 사람이 지도한 AI 에이전트가 몇 주 만에 해낸 일이라고 하고요. 논문은 두 편인데, 하나는 서명 위조 쪽입니다. 공격자가 서명될 데이터의 일부를 통제할 수 있을 때 기존 최선보다 약 1,600배 낫다는 이론적 추정치가 붙어 있습니다. 다른 하나가 「Fan Factories」, 여러 개를 한꺼번에 소인수분해하는 이야기예요.

발표도 논문도 같은 문장을 달고 있습니다. 2048비트 이상을 쓰는 오늘의 시스템은 위협받지 않는다는 것. 그래서 기사 제목도 딱 둘로 갈렸습니다. "AI가 RSA를 깼다"와 "당신 키는 안전하니 넘어가도 된다".

그런데 논문이 자기 의의라고 적어 둔 것은 둘 다 아닙니다.

「Fan Factories」 초록에는 이렇게 쓰여 있어요. 이 결과의 주된 의의는 "보통 느리게 움직이는 분야를 AI 보조 연구가 얼마나 빨리 움직일 수 있는지" 그림을 선명하게 해 준 데 있다고. 무슨 말인지 알려면 그 분야가 왜 느렸는지를 봐야 하는데, 이게 생각보다 재미있습니다.

특수한 형태가 아닌 큰 수를 소인수분해할 때 지금까지 알려진 가장 빠른 알고리즘은 수체 체(number field sieve)입니다. 이 작업은 두 덩이로 나뉘는데요. 목표 숫자가 무엇이든, 크기만 같다면 미리 해 둘 수 있는 밑작업이 있고, 그 숫자에만 해당하는 마무리가 있습니다. 그러면 자연스럽게 이런 생각이 들죠. 밑작업을 한 번만 해 두고 여러 숫자에 돌려 쓰면 되지 않나?

1993년에 돈 코퍼스미스가 낸 '인수분해 공장'이 정확히 그 아이디어입니다. 다만 함정이 있었어요. 여럿이 나눠 쓸 수 있게 만든 그 밑작업이, 숫자 하나를 통째로 분해하는 것보다 비쌌습니다. 그래서 밑작업에 쓸 예산이 숫자 하나 분해할 만큼뿐이면 공장은 아무것도 주지 못했어요. 논문의 표현을 그대로 옮기면 "With a smaller budget the factory gives nothing"입니다.

그 자리가 33년 동안 비어 있었습니다.

그러니까 밑작업 예산을 그 정도로 묶어 두면, 두 번째 숫자부터 드는 비용은 1993년 이후로 줄곧 같은 값이었다는 뜻입니다. 이번 논문이 한 일은 숫자마다 수체를 하나씩 붙이는 대신 부채(fan)처럼 여러 개를 펼쳐 달고, 그 전부를 공유된 밑작업 하나에 물린 겁니다. 그러면 밑작업이 비쌀 필요가 없어져요. 1024비트로 환산하면 한 번 분해할 만큼만 밑작업을 해 둬도 그다음 숫자부터는 한 번 분해 비용의 약 1/58로 떨어집니다. 종전 최선 대비 30배 싸진 거죠.

여기서 실무로 돌아와 보면요. 우리가 "1024비트는 위험하고 2048비트는 당분간 괜찮다"라고 말할 때, 그 계산은 전부 키 하나를 깨는 비용입니다. 그런데 현실에서 같은 크기의 키는 혼자 있지 않죠. 논문의 마지막 문단이 정확히 그 얘기를 합니다. 이런 분석이 "같은 크기의 키가 많이 쓰이고 있을 때 그 키 길이가 얼마나 보호해 주는지"를 판단하는 데 도움이 된다고요.

그래서 내일 할 수 있는 일은 꽤 단순합니다. 1024비트 RSA가 아직 어디에 남아 있는지 목록을 뽑는 것. 예전에 만든 코드 서명 키, 출하된 지 오래된 장비의 펌웨어 검증 키, 사내 인증기관이 옛날에 발급한 하위 인증서, 한 번도 손대지 않은 VPN과 SSH 호스트 키, DNSSEC 서명 키. 개수와 위치만 있으면 됩니다. 그 목록이 없으면 두 번째 키부터 싸진다는 이야기는 끝까지 남의 집 사정으로 남아요.

물론 당장 무엇이 깨진 것은 아닙니다. 논문이 스스로 선을 긋고 있는데요. 부채 공장은 한 번도 구현된 적이 없습니다. 위 수치들은 측정값이 아니라 선도 차수 추정이고, 잘 튜닝된 기존 구현을 어느 크기에서 앞지르는지는 경험적으로 열린 문제라고 적혀 있어요. 메모리도 장벽입니다. 1024비트에서 저장해야 할 표가 2의 75제곱 개 쌍 규모니까요. 서명 위조 쪽 1,600배 역시 이론적 추정치입니다. (요즘 "4096비트도 128비트 보안 수준에 못 미친다"는 문장이 같이 돌아다니던데, 그건 딥마인드가 아니라 9월에 나온 선행 논문의 문장이고, 서명 오라클을 쓸 수 있다는 특정 공격 모델 안에서의 이야기예요.)

예측은 아니고 가정입니다만, 이번에 흔들린 것은 키 길이가 아니라 가정의 유효기간 쪽이라고 봅니다. 우리가 키 길이를 고를 때 숫자만 보는 게 아니잖아요. "이 분야는 천천히 움직이니까 이 정도면 한참 간다"는 전제를 같이 깝니다. 그 전제의 근거는 꽤 단단했어요. 두 번째 숫자부터의 비용을 재는 그 지수가 1993년 이후 33년을 꼼짝하지 않았으니까요. 그게 이번에 내려갔고, 증명은 두 에이전트가 하나는 만들고 하나는 검증하는 방식으로 나왔습니다. 그 바탕이 되는 대수적 항등식은 Lean 4로 기계가 다시 확인했고요. 근거 없이 하는 말은 아니고, 논문이 자기 결과의 의의를 바로 거기에 둔 것을 따라가 본 겁니다.

키를 당장 늘려야 할 만큼 급해 보이지는 않습니다. 다만 우리가 깔고 있는 암호 가정이 마지막으로 점검된 게 언제였나, 이걸 물어보는 주기는 좀 당겨야 하지 않나 싶네요.


커버 이미지: 아르곤 국립연구소의 IBM Blue Gene/P 슈퍼컴퓨터 — Wikimedia Commons, Argonne National Laboratory

#암호학 #RSA #딥마인드 #보안 #AI에이전트 #키관리