AI 에이전트가 RSA-260을 인수분해하다: GPU와 데번의 실전 성능 엔지니어링

RSA 인수분해 챌린지에서 새로운 기록이 나왔다. 코그니션(Cognition)의 한 연구자가 자사의 자율 소프트웨어 엔지니어링 에이전트 '데번(Devin)'을 동원해 260자리 정수인 RSA-260을 인수분해한 것이다. 이는 2020년 2월에 세워진 이전 공개 기록 RSA-250을 넘어서는, 지금까지 공개적으로 풀린 가장 큰 RSA 챌린지 문제다. 흥미로운 점은 이 작업이 LLM 학습·추론 클러스터의 자원 스케줄러를 개선하던 부수 프로젝트로 진행됐고, 전체 클러스터의 한 자릿수 퍼센트에 해당하는 자투리 연산 자원만으로 이뤄졌다는 사실이다.

먼저 오해를 걷어낼 필요가 있다. 연구자는 손으로 130자리 소수를 추측해 맞춘 것도 아니고, 수천 큐비트급 양자컴퓨터를 쓴 것도 아니라고 못박는다. 사용된 방법은 100자리 이상 대부분의 수에 대해 알려진 가장 효율적인 알고리즘인 일반 수체 체(GNFS, general number field sieve)이며, 이는 과거의 RSA 기록들에서도 쓰인 정통 기법이다. 구현은 팩토링 애호가 커뮤니티와 역대 기록에서 검증된 오픈소스 CADO-NFS를 상당히 개조한 것으로, 저자 본인도 '알고리즘적 혁신은 사실상 없다'고 밝힌다. 핵심은 GPU의 메모리 시스템을 최대한 활용하는 '고전적인 성능 엔지니어링'이었다.

왜 GPU였고, 왜 자투리 연산이었나

이 프로젝트의 출발점은 암호 해독이 아니라 스케줄러 최적화였다. LLM 워크로드가 도는 NVL72 랙은 NVLink로 묶인 18대 규모의 컴퓨터로 구성되는데, 작업을 랙에 채워 넣는 과정에서 한두 노드가 놀거나 장애 대비용으로 비어 있는 경우가 생긴다. 이런 파편화된 자원이 전체의 한 자릿수 퍼센트에 이른다. 문제는 이 틈을 메울, 언제든 즉시 중단 가능한 단일 노드 작업이 마땅치 않았다는 점이다.

격자 체질(lattice sieving)은 여기에 딱 맞았다. 수십억 개의 작은 작업 단위에 대해 거의 완전히 병렬로 돌아가고, 노드 하나로도 진행되며, 언제든 안전하게 중단할 수 있다. 게다가 GNFS에서 계산량이 가장 많은 단계이기도 하다. 그런데 역대 공개 기록들은 모두 격자 체질에 CPU만 썼다. GPU에서 효율적으로 구현하기가 까다로워, GPU 체질이 전체적으로 더 저렴할지조차 오랫동안 불분명했기 때문이다. 필요한 것은 RSA-260 규모의 파라미터를 받아낼 수 있는, 충분히 빠른 GPU 격자 체 하나였다.

데번에게 시킨 결과

저자는 8월 13일 새벽, CADO-NFS의 CPU 체 프로그램 'las'를 그대로 대체할 GPU 버전을 만들라고 데번에게 지시했다. 두 시간 뒤 RSA-250 파라미터를 처리할 수 있어야 한다는 조건을 덧붙이고 잠자리에 들었다. 아침에 일어나 보니 데번은 약 7시간의 반복 작업 끝에 'glas(GPU las)'를 완성해 놓았다. 이후 한 주에 걸쳐 격자 체질과 나머지 파이프라인 전반을 최적화했다. 3주간 평균 3개, 최대 18개의 데번 세션이 동시에 돌았고, 폴리노미얼 선택을 GPU로 옮긴 gps1, 8.3억 개의 관계식을 만들어내는 체질, 그리고 블록 비더만 알고리즘 기반의 선형대수 풀이까지 파이프라인의 거의 모든 조각이 개조됐다.

다만 저자는 자신이 수학 자체를 깊이 이해하지는 못한다고 솔직히 인정한다. 중급 자동차 애호가가 부품의 역할과 성능 영향은 알아도 그 물리적 원리나 제조법은 모르는 것과 같다는 것이다. 그럼에도 데번이 사람의 개입 없이 완전히 자율적으로 처음부터 끝까지 돌린 것은 아니다. 저자는 233개 세션 중 192개에서 3,328개 메시지, 8만여 단어를 보냈다. 데번에게 필요했던 것은 '무엇을 하고 있는지 함께 짚어주고 점검하는' 집행 기능이었고, 저자의 가장 큰 기여는 측정 결과와 벤치마크, 성능 추정치를 하나로 통합해 진행 상황을 파악할 수 있게 만든 일이었다고 회고한다.

실무자가 읽어야 할 함의와 한계

총비용은 약 4,900 GPU일, 즉 13.5 GPU년으로 현 시세 기준 약 40만 달러로 추산된다. 이전 공개 기술 수준 대비 10분의 1 비용이라는 것이 핵심 주장이다. 여기서 세 가지 변화가 두드러진다. 인수분해의 금전·시간 비용이 낮아졌다는 점, 전용 하드웨어 없이 충분한 GPU만 있으면 되므로 수행 가능한 주체가 늘어난다는 점, 그리고 비암호학자도 팩토링 고속화 작업에 뛰어들 수 있게 됐다는 점이다. RSA-1024(약 309자리)는 표준 GNFS 스케일링상 RSA-260의 78배 연산량으로, 시장 가격 기준 약 3천만 달러 규모로 추정되며 추가 최적화로 다시 절반까지 줄일 여지가 있다고 본다.

그러나 실무 관점에서 냉정히 볼 지점도 분명하다. RSA-1024가 안전하지 않다는 것은 새로운 사실이 아니다. 이미 2000년대 중반부터 TWIRL이나 번스타인 행렬 기계 같은 전용 하드웨어로 NSA가 경제적으로 처리할 수 있으리라는 추정이 있었고, 1024비트 RSA는 2013년 이미 폐기 권고된 규격이다. 또한 이번 효율 개선은 실제 현대 공개키가 쓰는 2048비트(약 617자리) 규모의 인수분해 가능성에는 거의 영향을 주지 못한다. 결국 이 성과는 '지금 쓰는 암호가 깨졌다'는 이야기가 아니라, 프로그래밍으로 풀 수 있는 대규모 과학 계산 연구의 진입 장벽이 자율 에이전트로 인해 크게 낮아지고 있다는 신호로 읽는 편이 정확하다. 오래된 규격을 아직 운용 중인 조직이라면 폐기 일정을 재점검할 이유는 충분하다.