DeepMind 'Fan Factories' 논문: 1024비트 RSA 키를 여러 개 깰 때의 비용과 1024비트 DKIM 키 점검

Google DeepMind는 2026년 11월 6일(미국 시간), AI 에이전트를 써서 1024비트 RSA의 약점 두 가지를 찾았다고 발표했습니다. 이 글은 그중 원문을 열어 확인할 수 있었던 일괄 인수분해 논문 "Fan Factories"만 다룹니다. 이 논문은 같은 크기의 키를 여러 개 깰 때 키 하나당 드는 비용을 줄이는 방법입니다. 키 크기가 1024비트일 때 키 하나를 인수분해하는 비용만큼 미리 계산해 두면, 그다음 키는 키 하나를 따로 깨는 기존 최선의 방법(MNFS)보다 약 30배 싸진다고 계산했습니다. 이 30배는 실행해서 잰 값이 아니라 이론 추정이고, 논문은 지금 배포된 2048비트 이상 RSA 암호 시스템을 위협하지 않는다고 초록 아래에 따로 강조해 적었습니다.

그래서 당장 바꿔야 할 것은 없습니다. 다만 "같은 크기의 1024비트 키가 많이 쓰이는 곳"이 이 논문의 대상이고, 메일 발송 서명인 DKIM이 그런 곳입니다. 이 사이트 kortress.com이 메일 발송에 쓰는 Resend의 DKIM 키도 조회해 보니 1024비트였습니다. 이 글에서는 논문이 바꾼 숫자, 논문 식으로 직접 계산한 여러 키의 총비용, 계산에 들어가지 않은 것, DKIM 키 조회 결과와 두 기준의 차이, 반응, 그리고 한국 개발자에게 바뀌는 것을 다룹니다.

33년 만에 바뀐 지수

인수분해 알고리즘의 빠르기는 비용식 L[c]의 상수 c로 비교합니다. c가 작을수록 빠르고, 1024비트에서는 c가 0.1만 줄어도 비용이 약 23배 달라진다고 논문은 설명합니다. 일반 정수를 인수분해하는 표준 방법인 일반 수체 체(GNFS)의 c는 약 1.9230입니다. Coppersmith의 다중 수체 체(MNFS)가 이를 1.9019로 낮췄고, 논문에 따르면 이 값은 1993년부터 그대로였습니다.

여러 키를 한꺼번에 깨는 방법으로는 Coppersmith의 "인수분해 공장(factorization factory)"이 있었습니다. 같은 크기 키에 공통인 계산을 미리 한 번 해 두고 키마다 재사용하는 방식입니다. 문제는 미리 하는 계산이 키 하나를 깨는 비용 정도로 작으면 공장이 아무 이득을 주지 못한다는 점이었습니다. 그래서 이 예산에서 키 하나당 최선은 1993년부터 MNFS의 1.9019였습니다.

Fan Factories는 키마다 수체를 여러 개 묶은 "팬(fan)"을 주고, 미리 계산한 공통 부분을 그 팬 전체에 대어 보는 방식입니다. 그 결과 사전계산 예산이 GNFS 한 번일 때 키 하나당 지수가 1.9019에서 1.7929로 내려갔습니다. 논문 그림 4는 이 구간을 "no change for 33 years"라고 표시합니다.

마지막 줄이 중요합니다. 사전계산에 예산을 무제한으로 쓰면 1993년의 Coppersmith 공장이 여전히 최선이고, 팬은 아무것도 더하지 않습니다. 논문 표현으로는 "새로운 바닥"이 아니라 "적은 예산에서의 개선"입니다. 바뀐 것은 대량 공격의 상한이 아니라 진입 비용입니다.

논문은 결과가 "두 에이전트로 된 AI 하네스"에서 나왔다고 적었습니다. 한 모델이 증명을 만들고 다른 모델이 검증했으며, 닫힌 식 뒤의 대수 항등식은 증명 보조 도구 Lean 4로 기계 검증했습니다. 어떤 모델을 썼는지는 논문에 없습니다. 저자는 Google DeepMind 연구진과 암호학자 Nadia Heninger(UC San Diego·Inria), Emmanuel Thomé(Inria) 등이며, 2026년 11월 5일 날짜의 워킹 페이퍼로 공개됐습니다.

키 개수에 따른 총비용 계산

이 30배는 "사전계산을 이미 끝낸 뒤 추가 키 하나"의 비교입니다. 실제로 몇 개를 깨야 이득인지는 사전계산까지 더해 봐야 합니다. 논문 4.1절은 1024비트에서 키 M개를 깨는 총비용을 팬 공장은 GNFS 1 + M/58.5회, MNFS는 M/1.94회로 적었습니다. 이 식에 M을 넣어 직접 계산한 결과가 그림 1입니다.

키가 하나뿐이면 팬 공장이 오히려 두 배 가까이 비쌉니다(MNFS 0.52 대 팬 1.02). 셋부터 팬이 싸지고, 100개면 MNFS 51.5회 분량이 팬으로는 2.71회 분량이 됩니다. 논문도 "M ≥ 3이면 팬 공장이 더 싸다"고 적었습니다.

같은 계산을 2048비트에 하면 추가 키 하나의 비율은 1/240, MNFS 대비 99배로 더 커집니다(논문 표 2). 그런데도 2048비트가 안전한 이유는 사전계산 자체가 키 하나를 깨는 비용, 선행 차수로 약 2^117 연산이기 때문입니다. 비율이 커져도 출발선에 설 수가 없습니다.

계산에 들어가지 않은 것

그림 1은 실행 시간 예측이 아닙니다. 논문이 직접 밝힌 제약은 네 가지입니다.

• 모든 수치는 o(1) 항을 0으로 둔 선행 차수 추정입니다. 논문은 숨은 상수가 알고리즘마다 다르고 클 수 있어 "실행 시간 예측이 아니다"라고 씁니다.
• 팬 공장은 구현된 적이 없습니다. 잘 조율된 수체 체 구현을 어느 크기부터 앞지를지도 주장하지 않는다고 적었습니다.
• 메모리가 두 번째 장벽입니다. 사전계산 GNFS 1회 예산에서 저장해야 하는 표가 1024비트 기준 약 2^75쌍입니다.
• 결과는 NFS 분석의 표준 휴리스틱 가정 위에 서 있습니다.

벤치마크라고 부를 만한 실측은 이 논문에 없습니다. 모든 수치는 저자 자신의 이론 계산입니다. 제3자 확인은 아래 반응 절의 frank chu가 논문 상수로 1/58과 30배를 다시 계산해 맞춘 것이 전부이고, 구현해서 잰 결과는 이 글을 쓰는 시점에 찾지 못했습니다.

kortress.com DKIM 키 조회 결과

DKIM은 보내는 메일에 RSA 서명을 붙이고, 받는 쪽이 DNS에 공개된 공개키로 확인하는 방식입니다. 메일 발송 서비스가 도메인마다 같은 크기의 키를 대량으로 발급하므로 "같은 크기 키가 많이 쓰이는" 환경입니다. 그래서 이 사이트의 키부터 조회했습니다.

공개키 문자열이 MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQ로 시작하면 1024비트 RSA 키입니다. 같은 방식으로 2048비트 키는 MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA로 시작합니다. 자기 도메인의 선택자(selector)를 알면 아래 두 줄로 같은 확인을 할 수 있습니다.

curl -s "https://dns.google/resolve?name=<selector>._domainkey.<도메인>&type=TXT"
# p= 뒤의 값을 PEM으로 감싼 뒤
openssl pkey -pubin -in key.pem -noout -text | head -1

1024비트 DKIM을 둘러싼 두 기준

이 키가 1024비트인 것은 설정 실수가 아니라 Resend의 방침입니다. Resend 문서는 "1024비트 DKIM 키로 서명하며 2048비트 DKIM 키는 지원하지 않는다"고 적었고, 키 길이를 바꿀 수 없으며 요청해도 키를 교체하거나 다시 만들지 않는다고 밝혔습니다. 근거로 RFC 8301 3.2절을 들어 "서명자가 최소 1024비트 키를 쓰도록 권고한다"고 설명합니다.

RFC 8301 원문은 조금 다릅니다. 서명자는 최소 1024비트 키를 "MUST" 써야 하고, 최소 2048비트 키를 "SHOULD" 써야 한다고 적었습니다. 즉 1024비트는 허용 하한이고, 권고는 2048비트입니다. Resend 문서의 요약은 앞 문장만 옮긴 셈입니다.

Resend가 드는 1024비트의 장점(서명·검증 속도, DNS TXT 레코드 길이 문제 회피, 주요 메일 사업자의 대량 발송 요건 충족)은 사실이고, 이번 논문으로 1024비트 DKIM 키 하나를 깨는 비용이 바뀐 것도 아닙니다. 바뀐 것은 "1024비트 키가 많이 깔린 집단 전체"를 겨냥하는 공격의 진입 비용에 대한 이론적 그림입니다.

반응

Hacker News에는 논문 공저자인 Pushmeet Kohli(Google DeepMind)의 X 발표 글이 11월 7일(UTC) 올라왔지만, 11월 9일 확인 시점에 3점, 댓글 0개였습니다(https://news.ycombinator.com/item?id=50401254). 의미 있는 토론은 아직 없습니다.

비판 쪽에서는 개발자 frank chu가 DEV Community에 쓴 "1,600x is arithmetic, not an attack: I checked DeepMind RSA"가 있습니다(https://dev.to/frankchu/1600x-is-arithmetic-not-an-attack-i-checked-deepmind-rsa-12di). 그는 논문 상수로 비율을 직접 다시 계산해 "NFS/fan: 58.3", "MNFS/fan: 30.2"를 얻었고, 이것이 "genuine check(진짜 확인)"이지만 그 이상은 아니라고 썼습니다. 또 발표 수치를 실측과 추정으로 나눠 표로 정리하고, 팬 공장 항목에 "Fan factories built: 0"이라고 적었으며, 추정치는 "treat them as directions, not arrival times(도착 시각이 아니라 방향으로 읽어라)"라고 썼습니다. 같은 글은 동시에 발표된 서명 위조 논문에 대해서는 에이전트가 기존 공격을 1,380 CPU 코어년에서 391 코어년으로 다시 돌린 것을 "실제로 실행된 것"으로 꼽았습니다. 그 서명 위조 논문은 이 글을 쓰는 시점에 공개 사본을 찾지 못해 이 글에서는 다루지 않습니다.

찬성 쪽 제3자 반응은 찾지 못했습니다. 긍정적인 해석은 지금까지 DeepMind와 논문 저자 쪽에서만 나왔습니다.

한국 개발자에게 바뀌는 것

키 길이 2048비트 이상 RSA를 쓰는 TLS 인증서·코드 서명·로그인 토큰은 이번 발표로 바뀌는 것이 없습니다. 논문이 스스로 그렇게 적었고, 계산도 그 결론을 뒷받침합니다.

움직일 곳은 아직 1024비트 RSA가 남아 있는 곳입니다. 메일 DKIM 키가 대표적이고, 오래된 HSM 설정이나 펌웨어 서명 키도 점검 대상으로 보입니다. 공격이 당장 가능해진 것이 아니라, 같은 크기 키가 많을수록 키 하나당 비용이 줄어드는 방향의 연구가 AI 도움으로 33년 만에 한 걸음 나갔다는 점이 근거입니다. 논문 저자들도 이런 분석이 "많은 키가 같은 크기로 쓰일 때 그 키 크기가 주는 보호 수준을 판단하는 데" 쓰인다고 적었습니다.

Resend처럼 2048비트를 지원하지 않는 발송 서비스를 쓰는 경우, 키 길이를 직접 바꿀 방법은 없습니다. 서비스를 바꾸거나 2048비트 요구를 서비스에 전달하는 정도가 선택지로 보입니다. 메일 위조 방지 정책이 엄격한 금융·공공 서비스라면 RFC 권고(2048비트)와 사용 중인 발송 서비스의 기본값이 다를 수 있다는 점을 한 번 확인할 가치가 있습니다.

한계

일반화되는 것은 "같은 크기 1024비트 키가 많은 환경일수록 이론적 여유가 줄어든다"는 방향이지 30배라는 숫자 자체가 아닙니다.

출처

• Google DeepMind, Fan Factories: Multiple Number Fields in Factorization Factories and Batch NFS (워킹 페이퍼, 2026-11-05): https://storage.googleapis.com/deepmind-media/papers/Fan_Factories_Multiple_Number_Fields_in_Factorization_Factories_and_Batch_NFS.pdf
• IETF, RFC 8301 3.2절 Key Sizes: https://www.rfc-editor.org/rfc/rfc8301.txt
• Resend, Do You Need 2048-bit DKIM?: https://resend.com/docs/knowledge-base/do-i-need-2048-dkim.md
• Hacker News, DeepMind AI agents find two weaknesses in legacy 1024-bit RSA cryptosystems: https://news.ycombinator.com/item?id=50401254
• frank chu, 1,600x is arithmetic, not an attack: I checked DeepMind RSA (DEV Community): https://dev.to/frankchu/1600x-is-arithmetic-not-an-attack-i-checked-deepmind-rsa-12di