코그니션(Cognition)은 9월 9일, 자사 연구원 에릭 루(Eric Lu)가 자체 코딩 에이전트 데빈(Devin)을 이용해 RSA-260을 소인수분해했다고 발표했다. 이는 RSA 인수분해 챌린지에서 현재까지 공개된 가장 큰 기록이다. 이전 기록인 RSA-250은 2020년 2월 이후 6년 반 동안 깨지지 않았다.
RSA-260은 260자리 십진수로, 130자리 소수 두 개로 나뉜다. 사용된 알고리즘 자체는 새롭지 않다. 1990년대부터 대형 정수를 분해하는 표준 기법으로 쓰여온 일반 수체 체(GNFS, General Number Field Sieve)가 그대로 사용됐다. 달라진 것은 구현 단계다. 전체 파이프라인이 CPU 클러스터에서 GPU로 옮겨갔다.
4900 GPU일은 어디에 쓰였나
코그니션이 공개한 세부 내역은 다항식 선택에 643 GPU일, 격자 체(lattice sieve)에 3813 GPU일, 선형 방정식 풀이에 467 GPU일이다. 체 작업 하나가 전체 연산량의 4분의 3 이상을 차지했는데, 이는 GNFS의 일반적인 특징과 일치한다.
핵심 산출물은 CUDA로 다시 작성된 GPU 격자 체 엔진 '글라스(glas)'다. 개조된 CADO-NFS, GPU에 최적화된 블록 위더만(Wiedemann) 알고리즘과 함께 쓰였다. 코그니션은 이 구현으로 체 작업의 단위 비용을 약 한 자릿수(10배가량) 낮췄다고 밝혔다.
CADO-NFS는 2020년 프랑스 연구팀이 RSA-250을 분해할 때 사용한 것과 같은 오픈소스 소프트웨어다. 코드베이스는 같고 하드웨어 백엔드만 바뀌었다. 6년이라는 시간 차이가 이 두 수치에 그대로 드러난다.
데빈이 여기서 한 일은 엔지니어링 작업이지, 수학적 발견이 아니다. 코드 최적화, 파라미터 튜닝, 클러스터 관리가 그 내용이다. 코그니션은 발표문에서 이를 '계산 수론과 GPU 성능 엔지니어링이 만나는 지점의 문제를 풀 수 있을 만큼 충분히 뛰어난 소프트웨어 엔지니어'라고 표현했다.
사람의 관여도 공개된 수치에 담겨 있다. 233개 세션, 8만 2702단어 분량의 지시가 투입됐다. 세션당 평균 300여 단어로, 코드 리뷰 코멘트 한 건 정도의 분량이다. 무인 운영은 아니었다. 한 사람이 지속적으로 작업할 수 있는 도구를 이끌며, 과거에는 팀이 몇 달에 걸쳐 조율해야 했던 엔지니어링 작업을 3주로 압축한 것이다.
외삽하면 어떤 모습일까
코그니션은 두 가지 외삽 추정치도 제시했는데, 모두 현재 GPU 가격 기준의 대략적인 계산이라고 명시했다. RSA-1024는 RSA-260보다 난이도가 약 78배 높고 비용은 약 3000만 달러다. RSA-2048은 난이도가 9조 1200억 배로, 비용은 3.77×10^16 달러로 제시됐다.
첫 번째 수치는 짚어볼 만하다. 3000만 달러는 국가 기관은 물론 대기업도 감당할 수 있는 규모다. RSA-1024는 표준 체계에서 이미 오래전에 비권장(deprecated)으로 분류됐지만, 임베디드 기기, 구버전 펌웨어 서명, 관리되지 않는 일부 인증서 체인에는 여전히 이 키 길이가 남아 있다. 두 수치 사이의 약 10억 배 격차가 2048비트가 지금도 안전하다고 여겨지는 이유의 전부다.
기록의 역사를 쭉 펼쳐보면, 1999년 RSA-155 분해는 약 8000 MIPS년으로 추정됐고, 2009년 말 RSA-768은 2.2GHz 옵테론(Opteron) 코어 1개 기준 약 2000년, 2020년 RSA-250은 2700 코어년, 이번에는 13.5 GPU년이다. 앞선 세 번의 발전은 주로 무어의 법칙과 알고리즘 튜닝 덕분이었고, 속도는 대략 10년에 한 단계씩이었다. 이번 도약에서는 하드웨어 세대교체와 'CUDA 코드를 누가 짜는가'라는 문제가 겹쳐서 일어났다.
아직 답이 없는 부분
논문과 코드를 완전히 공개할지, 글라스(glas)를 오픈소스로 풀지에 대해 코그니션의 발표문은 언급하지 않았다. 독립적인 제3자의 재현도 아직 이뤄지지 않았다. RSA-250 당시에는 여러 팀이 체 파라미터를 교차 검증했지만, 이번 결과는 현재로선 한 곳의 데이터뿐이다.
분해 결과 자체는 검증하기 쉽다. 두 소수를 곱해보면 된다. 검증하기 어려운 쪽은 비용 계산이다. 4900 GPU일에 어떤 GPU 모델이 쓰였는지, 단가는 얼마였는지, 실패한 시도까지 포함됐는지를 발표문은 항목별로 나눠 밝히지 않았다. 40만 달러라는 수치가 보안 평가에 어떤 의미를 갖는지는 이런 세부 사항에 달려 있다.
참고 출처: 코그니션 공식 기술 블로그, caramba.loria.fr의 RSA-250 분해 발표, CocoLoop. GPU일과 코어년 수치는 각 발표문 원문 표기를 그대로 인용했으며 통일된 환산은 하지 않았다.