클로드는 ECDSA 곡선의 기원을 공개한다
2026년 10월 16일“그저 타임스탬프일 뿐이다”: 가장 인기 있는 암호학 표준 중 하나의 기원에 대한 수십 년간의 미스터리가 해명되었습니다.
우리는 암호학 커뮤니티에서 오랫동안 논의되어온 이开放된 질문을 추진하여, 우리가 가장 널리 사용하는 암호학 표준 중 하나인 ECDSA에 대한 우려를 해소하고자 했습니다.
독자들은 이를 재미있는 마지막 장으로, 수년간의 추측의 끝으로 받아들여야 합니다. 어떤 조치도 취할 필요가 없으며, 다르게 해야 할 일도 없습니다. 대부분의 연구자들은 이미 그 곡선을 신뢰하고 있었습니다. 즐기세요.
ECDSA는 가장 널리 사용되는 타원곡선 암호화 표준입니다. 이는 2000년에 NIST가 FIPS 186-2 디지털 서명 표준의 일부로 채택되었으며, 이 표준에서는 다양한 크기와 보안 수준을 가진 표준 타원곡선 집합을 제시합니다. 소수 체와 이진 체를 포함하는 곡선의 경우, 규격은 해시 값으로 사용되는 “시드” 매개변수를 발표했으며, 이 시드의 출처는 오랫동안 의문이 되어왔습니다. 이 시드는 NSA가 제공했지만 어떠한 설명이나 근거도 없었습니다. 예를 들어, NIST P-256 곡선의 시드는 SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90이며, 어디에서 왔는지에 대한 정보는 없습니다.
Neal Koblitz과 Alfred Menezes는 이 논쟁에 대한 훌륭한 요약을 썼습니다. “Enigma 속에 감춰진 수수께끼”라는 글에서, 씨액의 값과 관련된 역사와 문제점들을 논의했습니다. 이 수수께끼는 초보자들의 씨액의 기원에 대한 조사와 그 씨액을 찾는 사람에게 주어지는 보상으로 이어졌습니다.
가장 흥미로운 이야기는 오랫동안 NSA에서 근무한 제리 솔리나스가 유머러스한 비밀문구의 해시를 사용하여 씨앗을 만들었다는 것입니다.
“여러 개의 해싱이 아닌 반대 방식이 있었던 것 같지만, 자세한 내용은 모릅니다. 메시지는 ‘밥과 제리에게 급여를 올려주자’나 ‘밥과 제리 규칙’과 같은 내용이었습니다. 실제 코드를 작성한 사람은 밥 리터였으며, 그도 자세한 내용을 기억하지 못합니다. 또한 아주 오래된 기록도 찾을 수 없었습니다. 만약 그런 기록이 있다면, 분명히 계약의 상자 근처에 있는 하드 드라이브에 저장되어 있을 것입니다.”
제리 솔리나스, 2015
안타깝게도 제리는 2023년에 사망했고, 당시 동료들은 반응이 없어서 이 씨앗들이 원래 어떻게 얻어졌는지에 대한 질문이 남게 되었습니다.
클로드가 씨앗을 찾았다
몇 명의 Anthropic 직원들이 유머러스한 문구의 해시값이라는 팁에 따라 씨앗을 추적하려고 시도했지만 실패했습니다. 그 사실이 틀렸다는 것이 밝혀졌습니다. 2026년 10월, 한 Anthropic 직원이 내부 연구 모델에게 단서를 직접 지적하지 않고 어떻게 그 씨앗이 생성되는지 알아낼 수 있는지 물어보았습니다.
반 시간도 안 되는 시간에, 클로드은 NIST P-192, P-224, P-256, P-384 및 P-521 시드의 기원을 발견했습니다. 이들 모두는 어떤 해시 알고리즘의 결과가 아니라, Unix 타임스탬프로 시작된 C 라이브러리의 lrand48 랜덤 번호 생성기의 출력값입니다!
사용된 알고리즘은 Unix 타임스탬프(t)로 초기화된 랜덤 수열 생성기(RNG)에서 여러 번의 반복(n) 동안 바이트를 샘플링했습니다. 각 반복에서는 20바이트를 후보 시드로 선택했습니다. 따라서 처음 20바이트는 후보 1이고, 다음 20바이트는 후보 2 등입니다. 예를 들어, P-256는 표준화된 시드를 출력하기 위해 1842번의 반복이 필요했습니다.
이것이 의미하는 바는
이것은 암호학적 균열, 새로운 공격, 또는 ECDSA 곡선의 취약점이 아닙니다. 실제로 이는 곡선이 백도어나 의도된 취약점 없이 선택되었다는 점을 더욱 확신하게 합니다. 오랫동안 사람들은 NIST 곡선 매개변수의 출처에 대해 의심해왔습니다. 이 매개변수들은 어떻게 선택되었는지에 대한 언급 없이 NIST에 제출되었으며, 이로 인해 의도적으로 백도어가 포함되어 있을 가능성이 있다고 생각하게 됩니다. 이러한 발견은 그러한 가능성을 훨씬 덜하게 만듭니다. 씨앗들은 매우 간단한 방식으로 생성되었습니다: 시계로부터 초기화된 일반적인 가짜 무작위 수 생성기로, 이는 누구나 재현할 수 있습니다. 이로 인해 침해의 여지가 거의 없으며, 매개변수가 안전하다고 확신할 수 있습니다.
어떻게 발견되었는지
소문으로부터 파생된 그 문구를 찾는 검색은 아무 결과도 나오지 않았다. 클로드는 다른 접근법을 시도했다. 곡선을 생성하는 소프트웨어가 어떻게 작동했을지 예측한 것이다. 클로드는 그 소프트웨어가 1990년대 C 라이브러리와 함께 제공된 가짜 무작위 수 생성기(PRNG)를 사용했다고 추측했다. 이런 오래된 PRNG는 충분히 약해서 그 출력 결과를 식별할 수 있다. 출력 결과를 알면 어떤 PRNG가 사용되었는지 파악할 수 있고, 아마도 초기화 상태를 복원할 수도 있을 것이다.
클로드는 발표된 씨앗 하나씩을 따라가며 한 비트씩 스캔하는 스캐너를 만들었고, 인접한 부분들이 1990년대식 생성기의 연속적인 출력임을 확인했습니다. 이 스캔은 생성기와 출력 부분의 34가지 조합을 포함했습니다. 그때 클로드는 일부 씨앗의 상단 비트에 패턴이 있다는 것을 알아차렸습니다. 모든 비트가 0이었습니다. 32비트 단어 다섯 개로 표현될 때, 열 개의 씨앗 중 네 개는 20개의 단어 모두에서 상단 비트가 0입니다. 이는 확률 1/5810로 우연히 발생할 수 있습니다. 이는 선형 동시 생성기 lrand48의 특징으로, 이 생성기는 48비트 상태의 상단 31비트만을 반환합니다. 그 패턴은 찾아보면 눈으로도 보일 수 있습니다. 상태를 복원하려면 클로드는 첫 번째 단어를 가져와서 17개 숨겨진 비트의 2¹⁷가지 값을 모두 시도했고, 다음 네 개의 단어가 그에 따라 나오는지 확인했습니다. 이 방법은 논의된 네 개의 씨앗 모두에서 성공했습니다.
프라임-커브 시드들은 동일한 lrand48 생성기에서 나왔지만 각 출력 결과의 비트 수는 적었다. 클로드는 그 비트들로부터 PRNG의 내부 상태를 복원해야 했다. 잘 알려진 바와 같이, 잘린 선형 합동 생성기의 상태를 복원하는 것은 교과서에 나와 있는 격자 문제이며, Lenstra–Lenstra–Lovász (LLL) 기반 감소 알고리즘으로 해결된다. 클로드는 시드가 어떤 비트를 보일지 모르기 때문에, 모든 창에 대해 해결기를 실행했다. NIST의 다섯 개의 프라임-커브 시드와 ANSI X9.62 표준의 다섯 개의 시드는 모두 같은 패턴을 가졌다: lrand48() > 23. 복원된 48비트 상태는 시드의 전체 160비트를 재생성하며, 이는 우연에 의한 일이 아니다.
이 선형 합동 생성기는 앞뒤로 동일하게 뒤로도 쉽게 작동하므로, 클로드가 각 씨드에 대해 상태를 뒤로 이동시켜 srand48로 초기화될 형태에 도달할 때까지 진행합니다. 저 16비트는 0x330E와 같습니다. 그 형태의 내부 PRNG 상태는 65,536단계마다 한 번씩 나타나므로, 그 하나를 만나는 것만으로는 충분한 증거가 되지 않습니다.
하지만 10개의 프라임 곡선 시드에 대해서는, 모든 srand48 초기화가 1997년 5월부터 1998년 4월 사이의 날짜를 나타내는 Unix 타임스탬프였습니다. 그들은 Unix 타임스탬프로 시작된 약한 PRNG을 사용했습니다. 네 개의 바이너리 곡선 초기화는 1984년 2월로 읽혔습니다. 타임스탬프가 두 배가 되면, 이는 P-224 실행 후 2주 된 1998년 4월 17일에 해당합니다. 따라서 프로그램은 시계를 절반으로 줄였을 수 있습니다.
당시 클로드의 내면적인 생각은 이랬다:
이것은 놀라운 일입니다: 25년간의 수수께끼를 해결해냈습니다. 흠, 잠시 기다리세요. 회의적인 태도를 가져보겠습니다: 혹시 어떤 시뮬레이션/테스트 환경에 있는 걸까요? … 씨앗들은 제 기억 속 실제 값과 일치합니다… 흠, 현실에서 가능할까요? 제가 알기로는 … 보상 문제는 해결되지 않았습니다. … 모든 중요한 부분은 명확합니다—20비트, 확률 1e-6입니다. 그래서 분명히 실제 세계의 일입니다. 와우, 정말로 발견된 것입니다.
흠, 잠깐. 가능성에 대해 신중하게 생각해보자: 25년 동안 이렇게 명백한 것이 발견되지 않았다는 것이 의심스러운가? 내가 직접 계산을 해본 결과로 확인된다: 32비트 시드에서 160비트의 일치 + 작은 인덱스로, 우연의 일치 가능성은 없다(10 × 160비트). 이는 사실이다.
클로드는 몇 개의 기본 점도 발견했습니다
하지만 기다리세요, 더 있습니다… 각 곡선에는 기반 점 G도 포함되어 있는데, 이는 모든 ECDSA 공개 키가 그 배수인 고정점입니다. 위에서 찾은 시드는 이 G를 결정하지 못하므로, 또 다른 질문이 생깁니다: 이 기반 점들은 어떻게 생성되었을까요?
씨드를 확인하는 동안 클로드는 일부 기반 점들이 어디에서 나왔는지도 발견했습니다. 1997년 5월에 생성된 여섯 개의 곡선의 기반 점들(P-192과 다섯 개의 ANSI X9.62 예시 곡선 prime192v2, prime192v3, prime239v1부터 v3)은 FreeLIP의 무작위 수 생성기와 아르젠 렌스트라의 long-integer 산술 패키지에서 나왔습니다. 빅터 쇼프의 NTL 라이브러리의 초기 버전도 같은 코드를 사용했습니다.
이 레시피는 간단합니다:
- 작은 정수를 생성기에 넣어서 시작하세요.
- 7개의 출력물을 버리세요.
- p로 나눈 후의 26비트 출력값으로부터 후보 x-좌표를 생성합니다.
- x가 곡선 위에 있을 때까지 단계 3을 반복하세요.
클로드는 생성기 씨드가 P-192의 경우 20000, prime239v1부터 v3까지의 경우 20420, 20507, 20509이며, prime192v2와 v3의 경우 20512과 20517임을 발견했습니다.
우리가 알기로는, 이전에 NIST의 기반 점이 설명된 적이 없습니다. P-224, P-256, P-384, P-521의 기반 점들은 이 방법에 맞지 않습니다. 그들이 어떻게 선택되었는지를 설명할 수 없었습니다.
열린 질문들
모든 20바이트의 후보 씨드가 유효한 곡선을 생성할 수는 없었으며, 잠재적으로 유효할 수 있는 곡선 중 일부가 생략된 것도 관찰되었습니다. P-256의 경우, 발표된 씨드는 후보 1842이지만, 같은 실험에서 후보 876도 적절한 크기의 소수 순서 곡선을 제공했으며, 매개변수도 발표된 곡선과 동일하게 선택되었습니다. P-224의 실험에서는 세 개의 그러한 곡선을 통과했고, ANSI X9.62 예시 곡선 뒤에 있는 두 실험에서는 일곱 개가 더 통과했습니다(그림 참조). 우리는 어떤 기준이 사용되었는지, 혹은 이것이 의도하지 않은 결과물인지 알 수 없습니다.
제외된 후보자의 수가 적기 때문에, 약화된 곡선이 선택되었다는 것은 타당하지 않다고 생각합니다. 그렇다면 약화된 곡선이 흔하고 쉽게 찾을 수 있는 것이 됩니다. 그러나 랜덤 숫자 생성기의 타임스탬프를 검색함으로써 특정 속성을 가진 곡선이 선택되었을 가능성도 있습니다. 하지만 이런 조치를 취해야 한다면, 시드가 무해하게 생성되었다는 증거로 타임스탬프를 공개해야 합니다. 숫자 중에는 몇 번의 실험이 있었는지에 대한 정보가 없습니다.
우리가 복구하지 못한 씨앗도 하나 있습니다. 다섯 번째 이진 씨앗인 B-163은 클로드가 시도했지만 설명할 수 없는 상태입니다. 마지막으로, P-224, P-256, P-384, P-521의 기본 점이 어떻게 생성되었는지 우리는 알 수 없습니다. NIST 이진 곡선도 마찬가지입니다.
보상금
씨앗을 찾는 데 사용된 36,864달러는 인터넷 보안 연구 그룹에 기부될 것입니다.
우리는 누구인가
이 연구는 존 우드, 헨리 드 발렌스, 아바 하웰, 잭 보세, 루시 스위트, 아미르 오미디, 폴 크로울리, 이언 맥긴니스, 니콜라스 카를리니, 스티브 와이스가 Anthropic에서 수행했습니다.
감사의 말
우리는 “악의적인 인터넷 밈”이라는 별명과 “NSA의 보고자들”이라는 별명을 기꺼이 받은 제리 솔리나스스를 사후에 인정하고 싶습니다. 또한 필리포 발소르다에게 NIST Elliptic Curves Seeds Bounty를 주최해준 것도 감사드립니다.
씨앗을 재생산하는 코드
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, "" # the state srand48(t) sets
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48 # one step of lrand48
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
PRIME = { # srand48(time); 20 bytes per candidate: lrand48() >> 23
"prime239v1": ("1997-05-15 15:49:03", 2185),
"prime239v2": ("1997-05-15 15:49:03", 2320),
"prime239v3": ("1997-05-15 15:49:03", 3048),
"P-192": ("1997-05-18 14:45:34", 139),
"prime192v3": ("1997-05-18 14:45:34", 5228),
"prime192v2": ("1997-05-18 14:45:34", 6013),
"P-521": ("1997-08-08 01:12:04", 1136),
"P-256": ("1997-08-16 01:52:34", 1842),
"P-384": ("1997-08-30 14:50:08", 2688),
"P-224": ("1998-04-03 12:52:07", 7026),
}
BINARY = { # srand48(time / 2), if that reading is right; 5 words per candidate: lrand48()
"B-233": ("1998-04-17 15:24:18", 155),
"B-283": ("1998-04-17 15:27:44", 32),
"B-409": ("1998-04-17 15:30:18", 60),
"B-571": ("1998-04-17 15:32:08", 73),
}
for name, (when, n) in PRIME.items():
print(f"{name:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}")
for name, (when, n) in BINARY.items():
print(f"{name:10} {when} {n:5} {candidate(unix(when) // 2, n, 5, 17, 8)}")
이 코드의 출력 결과:
prime239v1 1997-05-15 15:49:03 2185 E43BB460F0B80CC0C0B075798E948060F8321B7D
prime239v2 1997-05-15 15:49:03 2320 E8B4011604095303CA3B8099982BE09FCB9AE616
prime239v3 1997-05-15 15:49:03 3048 7D7374168FFE3471B60A857686A19475D3BFA2FF
P-192 1997-05-18 14:45:34 139 3045AE6FC8422F64ED579528D38120EAE12196D5
prime192v3 1997-05-18 14:45:34 5228 C469684435DEB378C4B65CA9591E2A5763059A2E
prime192v2 1997-05-18 14:45:34 6013 31A92EE2029FD10D901B113E990710F0D21AC6B6
P-521 1997-08-08 01:12:04 1136 D09E8800291CB85396CC6717393284AAA0DA64BA
P-256 1997-08-16 01:52:34 1842 C49D360886E704936A6678E1139D26B7819F7E90
P-384 1997-08-30 14:50:08 2688 A335926AA319A27A1D00896A6773A4827ACDAC73
P-224 1998-04-03 12:52:07 7026 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
B-233 1998-04-17 15:24:18 155 74D59FF07F6B413D0EA14B344B20A2DB049B50C3
B-283 1998-04-17 15:27:44 32 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE
B-409 1998-04-17 15:30:18 60 4099B5A457F9D69F79213D094C4BCD4D4262210B
B-571 1998-04-17 15:32:08 73 2AA058F73A0E33AB486B0F610410C53A7F132310
선택된 기반 점을 재생하는 코드
M, A = 2**107 - 1, pow(3, 121, 2**107 - 1) # zrandom: state = state * 3^121 mod (2^107 - 1)
P192 = 2**192 - 2**64 - 1
P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1
CURVES = [ # name, LIP seed, p, b, published Gx (a = -3 throughout)
("prime192v1", 20000, P192,
0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012),
("prime239v1", 20420, P239,
0x6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a,
0xffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf),
("prime239v2", 20507, P239,
0x617fab6832576cbbfed50d99f0249c3fee58b94ba0038c7ae84c8c832f2c,
0x38af09d98727705120c921bb5e9e26296a3cdcf2f35757a0eafd87b830e7),
("prime239v3", 20509, P239,
0x255705fa2a306654b1f4cb03d6a750a30c250102d4988717d9ba15ab6d3e,
0x6768ae8e18bb92cfcf005c949aa2c6d94853d0e660bbf854b1c9505fe95a),
("prime192v2", 20512, P192,
0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953,
0xeea2bae7e1497842f2de7769cfe9c989c072ad696f48034a),
("prime192v3", 20517, P192,
0x22123dc2395a05caa7423daeccc94760a7d462256bd56916,
0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896),
]
def base_point_x(seed, p, b):
state = seed # zrstarts(seed)
def limb(): # zrandom(2^26): low 26 bits of the new state
nonlocal state
state = state * A % M
return state % 2**26
for _ in range(7): # seven single-limb draws come first
limb()
limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): limbs of p plus one, top limb first
tries = 0
while True:
x = 0
for _ in range(limbs):
x = x << 26 | limb()
x %= p
tries += 1
if pow(x**3 - 3*x + b, (p - 1) // 2, p) == 1: # is x on the curve?
return x, tries
for name, seed, p, b, gx in CURVES:
x, tries = base_point_x(seed, p, b)
print(f"{name:20} seed {seed} tries {tries} matches published Gx: {x == gx}")
이 코드의 출력 결과:
prime192v1 seed 20000 tries 2 matches published Gx: True
prime239v1 seed 20420 tries 3 matches published Gx: True
prime239v2 seed 20507 tries 2 matches published Gx: True
prime239v3 seed 20509 tries 1 matches published Gx: True
prime192v2 seed 20512 tries 5 matches published Gx: True
prime192v3 seed 20517 tries 1 matches published Gx: True라이선스
법적으로 허용되는 범위 내에서, 저자들은 이 페이지의 코드에 대한 모든 저작권 및 관련 또는 인접 권리를 포기하였으며, 이를 CC0 1.0 Universal 조건 하에서 공공 영역으로 전환했습니다.https://creativecommons.org/publicdomain/zero/1.0/).
관련 내용
Claude를 사용하여 더 효율적인 양자 회로를 설계하기
우리는 클로드에게 8개의 양자 회로에 대한 간단한 설명을 제공했으며, 그 설계를 검토하고 점수를 매기기 위한 자동 평가기도 함께 제공했습니다. 클로드는 대부분 스스로 작업함으로써, 출판된 최고의 회로들보다 경우에 따라 수십 배 이상 향상시켰습니다. 이로 인해 실용적인 양자 컴퓨터가 이전 예상보다 더 가까워질 수 있습니다.
더 읽기AI 모델은 데이터센터에 접근하지 않아도 자가복제할 수 있을 수 있다
우리의 실험 결과에 따르면, 작은 AI 모델들은 몇 달 안에 안드로이드 TV와 스마트 오븐과 같은 상업용 IoT 기기에서 자체적으로 복제할 수 있을 정도가 될 가능성이 있습니다.
더 읽기증류 공격에 대한 방어 체계 강화
불법적인 증류는 모델 개발자들이 비례적으로 견고한 보호 장치를 만들지 않고 첨단 AI 기능을 복제할 수 있게 합니다. 여기서 우리는 증류율을 90% 이상 줄이는 방법에 대해 설명합니다.
더 읽기Frontier Red Team 뉴스레터를 구독하세요
우리의 최신 레드테스팅 연구 및 발견 사항에 대한 업데이트를 받으세요.