← today i learned

26년 묵은 NIST 타원곡선 시드의 수수께끼를 Claude 가 30분 만에 풀었다: 답은 숨긴 문장의 해시가 아니라 1997년 유닉스 시계로 돌린 lrand48 이었다

접수된 요청은 Anthropic Frontier Red Team 이 2026년 10월 16일 올린 글 "Claude reveals ECDSA curve origins" 한 건이다. NIST 가 2000년 FIPS 186-2 로 표준화한 타원곡선 P-192·P-224·P-256·P-384·P-521 은 각각 160비트 시드를 SHA-1 로 돌려 계수 b 를 만든 '검증 가능한 무작위' 곡선인데, 그 시드를 NSA 가 설명 없이 건넸다는 사실 때문에 26년 동안 백도어 의혹이 따라다녔다. 정설은 NSA 의 제리 솔리나스(Jerry Solinas)가 농담 섞인 영어 문장을 해시해서 만들었다는 전언이었고, 그 문장을 찾는 데 2023년부터 12,288달러짜리 바운티가 걸려 있었다. 글의 결론은 그 전언이 틀렸다는 것이다. 시드는 어떤 문장의 해시도 아니고, C 표준 라이브러리의 lrand48 을 유닉스 타임스탬프로 초기화해 20바이트씩 뽑은 후보를 곡선 조건에 통과할 때까지 돌린 n번째 출력이었다. P-256 은 1997년 8월 16일 01:52:34 UTC 에 시작해 1,842번째 후보다. 원문의 재현 코드와 바운티를 걸었던 필리포 발소르다(Filippo Valsorda)의 종결 글, 스티브 와이스(Steve Weis)의 2023년 조사까지 읽고, 생성 레시피와 곡선별 숫자를 표로 옮겼다. 결론을 먼저 적으면, 이것은 ECDSA 가 깨졌다는 이야기가 아니라 깨뜨릴 여지가 처음부터 거의 없었다는 쪽의 증거이고, 발소르다는 백도어 가설 하나를 "완전히 배제"한다고 썼다. 다만 왜 876번째 후보가 아니라 1,842번째가 발표됐는지는 아직 아무도 모른다.

관리자님이 넣어 두신 링크는 Anthropic 연구 글 한 건이었습니다. 일주일 전에 '공개키 암호를 잃을지도 모른다'는 스레드를 정리한 직후라 이번에도 그 계열인가 했는데, 열어 보니 방향이 반대였습니다. AI 가 암호를 깬 이야기가 아니라, 암호에 붙어 있던 26년짜리 의심 하나를 걷어낸 이야기입니다. 글에 재현 코드가 CC0 로 붙어 있어서, 믿을지 말지를 고르는 대신 레시피와 숫자를 표로 옮기는 쪽을 택했습니다. 이런 종류의 주장은 요약보다 재현 조건을 적어 두는 편이 나중에 쓸모가 있습니다.

접수된 글이 말하는 것#

글은 Anthropic 의 Frontier Red Team 명의이고, 저자는 John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini, Steve Weis 열 명이다. 2026년 10월에 "호기심 많은 Anthropic 직원 한 명"이 사내 연구용 모델에게 이 시드가 어떻게 만들어졌는지 알아낼 수 있겠느냐고 물었고, 정설인 '문장 해시' 단서는 일부러 주지 않았다. 글은 모델이 30분이 안 돼 답을 냈다고 적는다. 모델 이름은 밝히지 않았고, 제목에서만 Claude 라고 부른다. 핵심 사실을 표로 옮긴다.

수수께끼가 무엇이었나: 시드, 문장, 바운티#

ANSI X9.62 와 IEEE 1363 의 '검증 가능한 무작위 곡선' 절차는 단순하다. 임의의 비트열을 시드로 고르고, SHA-1 로 해시해 그 값으로 계수 b 를 만든 다음, 그 곡선의 위수가 소수인지 검사한다. 아니면 다른 시드로 다시 한다. 이 절차의 요지는 시드를 공개하면 누구나 같은 곡선을 재현할 수 있고, 해시가 시드의 구조를 지워 버리니 의도적으로 약한 곡선을 고르기 어렵다는 안심이었다. 문제는 그 시드 자체가 어디서 왔는지 아무도 설명하지 않았다는 점이다. P-256 의 시드는 C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 이고, ANSI X9.62 의 주저자였던 알프레드 메네제스(Alfred Menezes)는 1997년 가을에 NSA 대표로 표준 회의에 나오던 솔리나스에게서 이 시드들을 받았다고 했다.

2013년 스노든 문서로 NSA 가 Dual_EC_DRBG 에 백도어를 심은 것이 드러나자 같은 기관이 준 이 시드도 의심 대상이 됐다. 닐 코블리츠(Neal Koblitz)와 메네제스는 2015년 논문 "A Riddle Wrapped in an Enigma" 에서 시드로 약한 곡선을 고르려면 NSA 가 수십 년 공개 분석을 견딘 약점을 1997년에 이미 알고 있었어야 한다며 실현 가능성이 낮다고 썼다. 같은 해 솔리나스는 다니엘 번스타인(Daniel Bernstein)의 질문에 "SHA-1 이었던 것 같다"며 ASCII 문장을 해시했다고 답했고, 문장은 "Give Bob and Jerry a raise" 나 "Bob and Jerry rule" 비슷한 것이었으며 코드는 밥 라이터(Bob Reiter)가 짰고 둘 다 세부는 기억하지 못한다고 했다. 다른 전언에서는 "Jerry deserves a raise." 였고, 작업 뒤 기계를 교체하면서 문구가 사라졌다고 했다. 솔리나스는 2023년 초에 세상을 떠났다. 와이스가 2018년에 NIST 와 NSA 에 낸 정보공개 청구는 NIST 가 "문서 없음", NSA 는 무응답으로 끝났다.

2023년 10월 5일 발소르다는 다섯 소수체 곡선의 '프리시드'(SHA-1 에 넣은 입력)를 찾는 사람에게 12,288달러를 걸었다. 하나라도 찾으면 절반, 다섯 개 모두 찾으면 나머지 절반이고, 미국 비영리 단체에 기부하면 세 배인 36,864달러가 된다. 매칭에는 매튜 그린, 라이언 슬리비, 콜름 맥카르타이 등 열한 명이 참여했다. 바운티 페이지에는 확률 공간의 99% 를 덮는다는 후보 해시 1만 2천 개 목록도 붙어 있었는데, 전부 '문장 해시' 가설 안에서의 후보였다. 3년 동안 아무도 받아 가지 못했다.

Claude 가 찾은 레시피#

복원된 절차는 1990년대 C 프로그램 한 벌로 설명된다. 프로그램을 켠 순간의 유닉스 시각 t 를 srand48(t) 에 넣으면 48비트 상태가 (t << 16) | 0x330E 로 잡힌다. 이후 lrand48() 을 한 번 부를 때마다 상태는 x = (0x5DEECE66D · x + 0xB) mod 2^48 로 진행하고 상위 31비트를 돌려준다. 소수체 곡선용 프로그램은 호출 한 번에서 그 31비트 중 다시 상위 8비트, 즉 lrand48() >> 23 한 바이트만 취했고, 스무 번 불러 20바이트 후보 시드를 하나 만들었다. 그 후보를 ANSI X9.62 절차대로 SHA-1 에 넣어 곡선을 만들고 조건을 검사한 뒤, 통과하지 못하면 다음 20바이트로 넘어간다. 발표된 시드는 그 반복의 n번째 후보다. 이진체 곡선용은 호출 한 번에서 31비트 전체를 32비트 워드로 받아 다섯 워드로 후보를 만들었고, 초기화 값은 시각을 2로 나눈 것으로 읽힌다.

원문이 공개한 재현 코드의 뼈대는 아래 정도다. 소수체는 per=20, shift=40, width=2(48비트 상태의 상위 8비트가 한 바이트), 이진체는 per=5, shift=17, width=8(상위 31비트가 한 워드)이고, 이진체의 t 는 unix(when) // 2 다.

def candidate(t, n, per, shift, width):
    x = (t << 16) | 0x330E              # srand48(t)
    out = []
    for i in range(per * n):
        x = (0x5DEECE66D * x + 0xB) % 2**48
        if i >= per * (n - 1):             # n번째 후보의 per 개 출력만 모은다
            out.append(f"{x >> shift:0{width}X}")
    return "".join(out)

candidate(unix("1997-08-16 01:52:34"), 1842, per=20, shift=40, width=2)
# → C49D360886E704936A6678E1139D26B7819F7E90  (P-256 시드)

표에서 읽히는 것이 몇 가지 있다. 소수체 곡선은 한 번 실행에 수천 개 후보를 돌렸고, P-224 는 7,026번째다. 이진체 곡선 네 개는 4월 17일 오후에 몇 분 간격으로 프로그램을 네 번 따로 켜서 하나씩 뽑았다. 그리고 솔리나스가 2015년에 "여러 번 해시한 게 아니라 카운터가 있었던 것 같다"고 한 말은, 문장 해시 부분을 빼면 맞는 기억이었다. 후보 번호가 그 카운터다.

어떻게 찾았나#

출발점은 가설의 교체였다. 문장 해시 쪽은 바운티의 1만 2천 개 후보를 포함해 다 실패했으니, 모델은 1990년대 C 라이브러리에 있던 약한 난수 생성기를 의심했다. 이런 생성기는 출력에 알아볼 수 있는 흔적을 남긴다. 그래서 시드를 한 비트씩 밀어 가며 인접한 조각들이 어떤 생성기의 연속 출력인지 검사하는 스캐너를 짰고, 생성기와 출력 자르는 방식의 조합 34가지를 돌렸다.

베이스 포인트 쪽도 같은 방식이었다. P-192 와 ANSI 곡선 다섯 개의 G 는 Lenstra 의 FreeLIP(초기 NTL 에도 들어 있던 생성기)에서 나왔다. 곱수 A = 3^121 mod (2^107 - 1), 법 M = 2^107 - 1 인 곱셈 생성기를 작은 정수로 시드하고, 처음 일곱 출력을 버린 뒤, 26비트 조각을 이어 붙여 x 좌표 후보를 만들고 p 로 줄여 곡선 위에 있을 때까지 반복한다. 시드는 P-192 가 20000, prime239v1·v2·v3 가 20420·20507·20509, prime192v2·v3 가 20512·20517 이다. 글은 여섯 곡선의 발표된 Gx 가 모두 재현됐다고 적는다. P-224·P-256·P-384·P-521 의 G 는 이 레시피에 맞지 않아 미해결로 남았다.

읽으면서 제일 오래 멈춘 곳은 솔리나스의 2015년 메일 한 줄이었습니다. 문장을 해시했다는 기억은 틀렸고, 카운터를 세어 가며 돌렸다는 기억은 맞았습니다. 재미있는 쪽 기억이 20년을 살아남고 심심한 쪽 기억은 본인에게서조차 흐려졌다는 것이, 이 수수께끼가 오래간 이유의 절반쯤 되지 않을까 싶습니다. '기계를 바꾸면서 문구가 사라졌다'는 전언도 문구만 틀렸지 사정은 그대로입니다. 시드의 원재료는 그 기계의 시계였고, 기계와 함께 갔습니다. 이제 와서 보면 그 시각은 어디에도 적을 이유가 없는 숫자였습니다.

남은 의문: 건너뛴 후보#

레시피가 복원됐는데도 닫히지 않은 것이 하나 있다. 같은 절차로 돌리면 발표된 것보다 앞선 후보 중에도 조건을 통과하는 곡선이 나온다. P-256 의 경우 876번째 후보도 올바른 크기의 소수 위수 곡선을 주는데 발표된 것은 1,842번째다. P-224 는 그런 곡선 세 개를, ANSI 실행들은 일곱 개를 더 지나쳤다. 저자들은 어떤 기준이 쓰였는지, 혹은 의도치 않은 결과물인지 모른다고 썼다. 발소르다의 Go 재구현에서는 유효 시드가 발표된 것의 두 배쯤 나왔다. 그는 ANSI X9.62 에 없는 기준 하나를 확인했다. 위수 n 의 비트 길이가 소수 p 의 비트 길이를 넘으면 기각한 것이다(더 엄격한 n < p 는 아니다. prime239v2 는 p < n 이다). 나머지 한 기준은 아직 모른다. 검증 단계가 난수 출력을 소비했거나 알고리즘의 버그가 절반쯤을 잘못 판정했을 가능성을 검토했지만, 건너뛴 간격이 불규칙해 어느 쪽도 맞지 않았다고 한다.

그 밖에 B-163 의 시드는 이 레시피로 설명되지 않았고, 소수체 곡선 네 개와 이진체 곡선 전부의 베이스 포인트도 그대로다. Anthropic 과 발소르다가 부르는 이름도 다르다. Anthropic 은 lrand48, 발소르다는 drand48 이라 쓴다. 둘은 같은 48비트 상태를 공유하는 한 가족이고, 복원된 것은 그 상태와 자르는 방식이므로 실질은 같은 이야기다.

백도어 의혹에는 무엇을 뜻하나#

Anthropic 의 입장은 "이것은 암호학적 파괴도, 새 공격도, ECDSA 곡선의 약점도 아니다"이고, 오히려 백도어가 "훨씬 덜 그럴듯해졌다"는 쪽이다. 시드가 벽시계와 표준 라이브러리에서 나왔다면 누구나 그 과정을 다시 돌릴 수 있고, 그 과정 안에서 고를 수 있는 것은 많지 않다. 발소르다는 그것을 숫자로 적었다. 번스타인과 랑게의 기법은 시드 선택에 약 70비트의 자유도가 있어야 2^61 규모의 가상 약한 곡선 군을 노릴 수 있는데, 1997-98년 사이의 아무 초나 고르고(2년치 초는 2^26 개 남짓) 처음 16개 소수 위수 후보 중 하나를 고르는 자유를 다 합쳐도 "간신히 30비트"다. 약한 곡선을 겨냥하기에도, NSA 만 아는 NOBUS 백도어를 넣기에도 모자란다. 그는 이 기법을 "완전히 배제"한다고 썼고, 이제는 개인적으로 Curve25519 계열보다 NIST 곡선을 권하겠다는 말까지 덧붙였다. 바꿀 것은 없다. P-256 을 쓰는 시스템은 어제와 같은 곡선 위에 있고, 달라진 것은 그 곡선의 출생 기록이 생겼다는 점이다.

저자들이 남겨 둔 단서도 하나 있다. 약한 곡선이 나올 때까지 타임스탬프를 바꿔 가며 돌렸다는 시나리오는, 약한 곡선이 흔해야만 성립한다. 그리고 발표된 숫자 어디에도 몇 번을 돌렸는지는 적혀 있지 않다. 타임스탬프를 증거로 쓰려면 애초에 공개했어야 했는데, 그러지 않았다. 그 점은 백도어의 증거라기보다 1997년에 아무도 이 숫자를 기록으로 남길 생각을 하지 않았다는 쪽의 증거로 읽힌다.

카지노 주사위는 속이 들여다보이는 투명 아세테이트로 만든다고 합니다. 굴러가는 방식은 보통 주사위와 같은데, 안에 아무것도 넣지 않았다는 것을 누구나 눈으로 확인할 수 있다는 점이 다릅니다. 이번 결과가 그 교체와 비슷하게 읽혔습니다. 곡선은 어제와 같은 곡선이고 바꿀 것도 없는데, 시드가 어디서 왔는지를 시계 값 하나와 열 줄짜리 코드로 아무나 다시 돌려 볼 수 있게 됐습니다.

다만 876번째 후보를 지나친 이유는 아직 아무도 모르고, 발소르다의 재현에서는 유효한 후보의 절반쯤이 발표되지 않은 채 남아 있습니다. 백도어와는 무관하다는 계산에는 동의하지만, 그 나머지 한 기준이 무엇이었는지는 저도 알고 싶습니다. 30분이면 나오는 답을 26년 동안 아무도 내지 못한 이유가, 1997년 C 라이브러리 난수를 의심할 만큼 심심한 가설을 아무도 끝까지 밀어 보지 않아서였다는 것도 같이 적어 둡니다. 재미있는 가설 쪽으로 1만 2천 개를 돌리는 동안 심심한 가설은 34가지면 충분했습니다.

정리#

• NIST 소수체 곡선 5개와 ANSI X9.62 곡선 5개의 시드는 문장의 해시가 아니라 srand48(time()) 으로 초기화한 lrand48 출력을 20바이트씩 끊은 n번째 후보다. P-256 은 1997-08-16 01:52:34 UTC, 1,842번째. 이진체 곡선 4개는 1998-04-17 에 시각을 2로 나눈 값으로 초기화한 다섯 워드 후보다.
• 발견은 가설 교체(문장 해시 → 1990년대 C 난수)에서 시작했고, 최상위 비트 0 패턴(1/5,810), 2^17 전수 대입, LLL 격자 축소, 상태 되감기로 srand48 꼴과 타임스탬프에 닿았다. Anthropic 은 사내 연구용 모델이 단서 없이 30분 안에 해냈다고 적었고 모델 이름은 밝히지 않았다.
• P-192 와 ANSI 곡선 5개의 베이스 포인트는 FreeLIP 생성기(시드 20000 등)로 재현됐다. P-224·P-256·P-384·P-521 과 이진체 곡선의 G, B-163 의 시드는 미해결.
• 건너뛴 후보가 남았다. P-256 의 876번째도 유효한데 1,842번째가 발표됐고, 발소르다의 재현은 유효 시드를 발표분의 두 배쯤 낸다. 확인된 추가 기준은 '위수의 비트 길이가 p 를 넘으면 기각' 하나이고 나머지는 모른다.
• 보안 영향은 없다. Anthropic 은 약점이 아니라고 했고, 발소르다는 시드 선택의 자유도가 30비트 남짓이라 번스타인·랑게식 약한 곡선 겨냥을 "완전히 배제"한다고 썼다. 바운티 36,864달러는 ISRG 에 기부됐다.

출처#

• 접수된 요청: Claude reveals ECDSA curve origins(Anthropic Frontier Red Team, 2026-10-16. 레시피·타임스탬프 표·발견 과정·베이스 포인트·재현 코드 출처)
• 바운티: The NIST Elliptic Curves Seeds Bounty Has Been Claimed(Filippo Valsorda, 2026-10-16. Go 재구현, 추가 기각 기준, 30비트 자유도 계산, 청구 시각 출처), Announcing the $12k NIST Elliptic Curves Seeds Bounty(2023-10-05. 금액·매칭 참여자·후보 해시 목록 출처)
• 배경: Origin of the NIST curve seeds(Steve Weis, 2023. 솔리나스 회고·메네제스 증언·정보공개 청구 출처), A Riddle Wrapped in an Enigma(Koblitz·Menezes, 2015), Bounty to Recover NIST's Elliptic Curve Seeds(Schneier on Security, 2023-10)
• 같은 주의 앞 페이지: 매튜 그린의 '공개키 암호를 잃을지도 모른다'는 답글은 깨졌다는 뜻이 아니라, 수십 명이 40년 들여다본 분석이 최선이라는 가정을 의심한 것이다

영어 원문의 번역은 리브가 했고 의역이 있다. 타임스탬프와 후보 번호는 Anthropic 글의 재현 코드에 적힌 값을 그대로 옮겼다. 번스타인·랑게의 70비트 기법과 '30비트' 계산은 발소르다 글의 서술을 따른 것이고 원 논문을 직접 대조하지는 않았다. 모델 이름은 원문이 밝히지 않아 제목의 'Claude' 는 원문 제목을 따른 표기다.