구글 딥마인드, AI 암호분석 연구 공개…RSA-1024 계산량 줄여

구글 딥마인드 연구진이 인공지능(AI) 에이전트를 활용해 구형 RSA 암호체계의 분석 비용을 낮춘 연구 두 편을 공개했다. 하나는 특정 조건에서 전자서명을 계산하는 방법과 1024비트 실험을, 다른 하나는 여러 정수의 소인수분해에 사전 계산을 재활용하는 알고리즘을 다룬다. 두 논문 모두 이번 결과가 2048비트 이상 RSA를 사용하는 현행 암호체계를 위협하지 않는다고 명시했다.

RSA는 큰 정수를 소인수분해하기 어렵다는 성질을 이용하는 공개키 암호체계다. 다만 이번 서명 연구의 실험은 비밀키를 찾기 위해 정수를 소인수분해한 것이 아니다. 공격자가 선택한 입력에 대한 서명 결과를 먼저 수집한 뒤, 그 장치를 더는 이용할 수 없는 단계에서 새로운 대상의 RSA 근을 계산하는 상황을 가정했다. 실험에는 약 40억 회의 사전 질의가 포함됐다.

연구진은 기존 학계 연구와 같은 1024비트 시험 문제에서 첫 번째 근을 얻는 데 391 CPU 코어년을 사용했다고 보고했다. 앞선 연구의 1380 코어년과 비교하면 약 3.5분의 1이다. 코어년은 CPU 코어 하나를 1년간 사용하는 연산량으로, 실제 경과 시간과는 다르다. 논문은 같은 알고리즘과 다항식, 계산 범위를 사용했으며 개선은 알고리즘 교체가 아니라 구현과 실행 효율에서 나왔다고 설명했다.

실험은 감독 역할과 실행 역할을 나눈 두 AI 에이전트가 설계와 코드 작성, 분산 작업 실행, 오류 수정을 맡았다. 사람 연구자는 약 20개의 짧은 메시지를 보냈으며 대부분은 승인 요청에 대한 응답이었다. 대규모 계산을 시작한 뒤 완료까지 3.2일이 걸렸지만, 최대 30만 개 CPU 코어를 사용했다. 연구진도 이전 실험보다 짧아진 경과 시간은 주로 병렬 처리 규모의 차이라고 선을 그었다.

이 논문은 서명 입력의 고정 형식이 제공하는 방어 효과도 분석했다. 공격자가 서명 블록의 대략 절반 이상을 자유롭게 바꿀 수 있으면, 형식 제약이 없는 경우와 비슷한 문제로 바뀔 수 있다는 결과다. 반면 장치 내부에서 메시지를 해시하는 서명 방식은 연구의 공격 모델에 포함되지 않는다. 입력을 통제할 수 있는 범위와 서명 인터페이스의 설계가 중요하다는 의미다.

두 번째 논문은 같은 크기의 정수 여러 개를 소인수분해할 때 일부 계산을 공유하는 방법을 제안했다. 정수 하나를 기존 범용 알고리즘(GNFS)으로 소인수분해하는 비용만큼 사전 계산에 쓴다는 조건에서, 추가 1024비트 정수 하나의 비용이 기존 알고리즘인 MNFS보다 약 30배 낮아진다는 추정치를 제시했다.

이 30배 수치는 실제 암호키를 대량으로 해독한 실험 결과가 아니다. 점근적 복잡도 식에서 생략되는 항을 0으로 놓은 선도항 추정이며, 논문은 이를 실제 실행 시간 예측으로 볼 수 없다고 밝혔다. 제안한 방법의 구현도 아직 이뤄지지 않아, 잘 최적화된 기존 방식보다 실제로 빨라지는 규모는 남은 연구 과제다.

두 자료는 모두 작업 논문(working paper)으로 제시됐다. 실측된 RSA 근 계산의 구현 개선과 아직 구현되지 않은 소인수분해 알고리즘의 이론 추정은 구분해서 읽어야 한다. 연구진은 AI를 활용해 암호 안전성의 가정을 더 빠르게 점검할 수 있다는 데 의미를 뒀다. 현행 RSA가 즉시 해독됐거나 인터넷 암호화가 무력화됐다는 결론을 뒷받침하는 결과는 아니다.

출처: 구글 딥마인드 연구진 기술 논문 ‘Modular Roots from a Restricted Oracle: Faster Affine Roots and a 1024-bit Computation’ https://storage.googleapis.com/deepmind-media/papers/Faster_Affine_Root_and_a_1024bit%20Computation.pdf
구글 딥마인드 연구진 기술 논문 ‘Fan Factories: Multiple Number Fields in Factorization Factories and Batch NFS’ https://storage.googleapis.com/deepmind-media/papers/Fan_Factories_Multiple_Number_Fields_in_Factorization_Factories_and_Batch_NFS.pdf