NIST 타원곡선 시드 생성의 수수께끼가 풀려 현상금 지급

필리포 발소르다의 블로그 글(2026-10-16) 전체를 읽고 옮겼어요.

무엇이 풀렸나

NIST 타원곡선 P-192, P-224, P-256, P-384, P-521은 2000년 FIPS 186-2로 발표됐어요. ANSI X9.62에 따라 임의의 시드를 SHA-1로 해시해 일부 파라미터를 만들었는데, 그 시드를 어떻게 골랐는지는 지금까지 아무도 몰랐어요. 2023년 초 세상을 떠난 제리 솔리나스 박사가 1997년 영어 문장 몇 개를 해시했는데 그 문장을 잊었다는 이야기가 정설이었어요.

이번에 밝혀진 답은 이래요.

• POSIX 표준 난수 생성기 drand48을 썼어요. 당시 UNIX 시각을 srand48()에 넣고 drand48로 한 바이트씩 뽑아요.
• 20바이트씩 묶어 ANSI X9.62 시드로 시험하고, 유효한 곡선이 안 나오면 버려요. 한 시각으로 여러 곡선을 만들기도 했어요.
• 필리포는 Go로 알고리즘을 다시 구현해 주장을 검증했어요.

누가 풀었나

Anthropic의 존 우드, 헨리 드 발랑스, 에이바 하월, 잭 보스, 루시 스위트, 아미르 오미디, 폴 크롤리, 이언 맥기니스, 니컬러스 칼리니, 스티브 와이스가 2026년 10월 15일 01:07:51 UTC에 3년 전 걸린 현상금 전액을 받았어요. 팀은 상금을 ISRG(Let's Encrypt 운영 비영리)에 기부했고, 3배로 늘어 36,864달러(36 Ki$)가 됐어요.

남은 수수께끼

ANSI X9.62 외에 문서화되지 않은 조건이 두 개 있었어요.

1. 곡선 위수 n의 비트 길이가 기반 체 p보다 길면 버림(prime239v2 때문에 n < p 조건은 아님).
2. 그래도 공개된 것보다 유효 시드가 약 두 배 많아요. 같은 난수기를 검증에도 써서 후보를 건너뛰었거나, 1997년 당시 최첨단 계산이던 알고리즘의 버그였을 가능성을 들지만 설명은 아직 못 찾았어요.

예를 들어 P-256은 srand48(871696354)(1997-08-16 01:52:34 UTC)에서 1,842번째로 채택된 시드, P-521은 1997-08-08 시각의 1,136번째 시드였어요.

보안에 대한 의미

• 실무자 사이에 원래 심각한 우려는 없었어요. 2015년 코블리츠·메네지스 논문은 NSA가 수십 년 암호 분석을 피한 약점을 노려 시드를 골랐을 가능성이 낮다고 봤어요.
• 하지만 번스타인·랑게가 2017년 시드 선택의 70비트 자유도로 가상의 약한 곡선 집합을 노릴 수 있다고 설명하면서 음모론이 퍼졌어요.
• 이번 발견으로 그 기법은 완전히 배제돼요. 1997~98년의 어떤 시각이든, 처음 16개 후보 중 무엇이든 골랐다고 넉넉히 쳐도 자유도는 약 30비트뿐이라 백도어를 심기엔 부족해요.
• 필리포는 결정적 ECDSA 서명, 형식 검증된 구현, 2015년 완전 덧셈 공식과 함께 NIST 곡선의 "복권"이 완성됐다며 이제 개인적으로 Curve25519보다 추천한다고 해요. 다만 곧 양자 내성 서명으로 대체될 참이라고 덧붙여요. Anthropic 팀은 이진체 B-곡선의 시드 생성 방식도 알아냈어요.