Claude가 밝혀낸 ECDSA 곡선의 기원

"그냥 타임스탬프였습니다." 가장 널리 쓰이는 암호 표준 가운데 하나를 둘러싼 수십 년 묵은 의문이 풀렸습니다.

우리는 가장 널리 쓰이는 암호 표준 중 하나인 ECDSA를 둘러싼 우려를 해소하기 위해, 암호학계의 오랜 미해결 문제에 도전했습니다.

이 글은 수년간 이어진 추측에 마침표를 찍는 흥미로운 후일담 정도로 읽어 주세요. 따로 조치할 일도, 달라질 것도 없습니다. 대부분의 연구자는 이미 이 곡선들을 신뢰하고 있었습니다. 편하게 즐기시기 바랍니다.

ECDSA는 타원 곡선 암호 표준 가운데 가장 널리 쓰입니다. 2000년 NIST가 FIPS 186-2 디지털 서명 표준(Digital Signature Standard)의 일부로 채택했고, 이 표준에는 크기와 보안 수준이 서로 다른 표준 타원 곡선 여러 개가 정리되어 있습니다. 소수체(prime field)와 이진체(binary field) 위의 곡선에는 "시드(seed)" 매개변수가 함께 공개되었는데, 이 시드의 해시값으로 곡선의 계수 b를 정의합니다. 이 시드들은 NSA가 아무런 설명이나 근거 없이 제공한 것이어서, 출처가 어디인지는 오랫동안 풀리지 않는 의문이었습니다. 예를 들어 NIST P-256 곡선의 시드는 SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90였지만, 이 값이 어디서 나왔는지에 대한 정보는 전혀 없었습니다.

Neal Koblitz와 Alfred Menezes는 이 논란을 훌륭하게 정리한 글 "A Riddle Wrapped in an Enigma"에서 시드 값을 둘러싼 역사와 우려를 다뤘습니다. 이 수수께끼는 아마추어들의 시드 출처 추적으로 이어졌고, 시드를 찾아내는 사람에게 주는 현상금까지 걸렸습니다.

가장 그럴듯한 이야기는 NSA에서 오래 근무한 Jerry Solinas가 우스꽝스러운 패스프레이즈를 해시해 시드를 만들었다는 것이었습니다.

"여러 번 해시한 게 아니라 카운터를 썼던 것 같은데, 자세한 건 잘 모르겠습니다. 메시지는 'Give Bob and Jerry a raise'나 'Bob and Jerry rule' 같은 식이었고요. 실제로 코드를 짠 사람은 Bob Reiter인데, 그분도 세부 내용은 기억하지 못합니다. 그렇게 오래전 아카이브도 찾을 수 없었고요. 혹시 남아 있다면 분명 언약궤 근처 어딘가의 하드 드라이브에 처박혀 있겠죠."

Jerry Solinas, 2015

안타깝게도 Jerry는 2023년에 세상을 떠났고, 당시 다른 동료들도 연락에 응하지 않아 이 시드가 처음 어떻게 만들어졌는지는 미궁에 빠져 있었습니다.

시드를 찾아낸 Claude

우스꽝스러운 문구를 해시했다는 제보를 따라 시드를 쫓던 Anthropic 직원이 여럿 있었지만 모두 성과가 없었습니다. 그 제보는 틀린 것으로 드러났습니다. 2026년 10월, 호기심 많은 Anthropic 직원 한 명이 내부 연구용 모델에 단서를 주지 않고 이 시드들이 어떻게 생성되었는지 알아낼 수 있는지 물었습니다.

30분도 지나지 않아 Claude는 NIST P-192, P-224, P-256, P-384, P-521 시드의 기원을 밝혀냈습니다. 어느 것도 해시 알고리즘의 결과가 아니었습니다. 유닉스 타임스탬프를 시드로 초기화한 C 라이브러리의 lrand48 난수 생성기가 내놓은 출력이었습니다!

사용된 알고리즘은 유닉스 타임스탬프(t)로 초기화한 난수 생성기(RNG)에서 바이트를 일정 횟수(n)만큼 반복해서 뽑는 방식입니다. 반복할 때마다 20바이트를 후보 시드로 뽑습니다. 처음 20바이트가 후보 1, 그다음 20바이트가 후보 2가 되는 식입니다. 예를 들어 P-256은 표준 시드를 얻기까지 1842번 반복해야 했습니다.

이번 발견의 의미

이번 발견은 암호 해독도, 새로운 공격도, ECDSA 곡선의 약점도 아닙니다. 오히려 이 곡선들이 백도어나 의도적인 약점 없이 선택되었다는 확신을 더해 줍니다. 오랫동안 사람들은 NIST 곡선 매개변수의 출처를 의심해 왔습니다. 매개변수가 어떻게 선택되었는지에 대한 언급 없이 NIST에 제출되었기 때문에, 일부러 백도어를 심도록 골랐을지도 모른다는 의혹이 따라다녔습니다. 이번 결과는 그 가능성을 크게 낮춥니다. 시드는 아주 단순한 방식으로 만들어졌습니다. 시계 값으로 초기화한 흔한 의사 난수 생성기였고, 이제는 누구나 재현할 수 있습니다. 조작이 끼어들 여지가 훨씬 줄었으니, 매개변수가 안전하다고 확신해도 좋습니다.

발견 과정

소문을 바탕으로 문구를 찾아본 시도는 모두 빈손으로 끝났습니다. Claude는 접근 방식을 바꿔, 곡선을 생성한 소프트웨어가 어떻게 동작했을지부터 짚어 보았습니다. Claude는 이 소프트웨어가 1990년대 C 라이브러리에 포함된 의사 난수 생성기(PRNG)를 썼을 것이라고 추측했습니다. 이런 오래된 PRNG는 허술해서 출력만 봐도 알아볼 수 있습니다. 출력을 알아보면 어떤 PRNG를 썼는지 알 수 있고, 초기화 상태까지 복원할 수도 있습니다.

Claude는 공개된 각 시드를 한 비트씩 밀어 가며, 인접한 조각들이 1990년대식 생성기의 연속된 출력인지 검사하는 스캐너를 작성했습니다. 이 스캔은 생성기와 출력 조각의 조합 34가지를 다뤘습니다. 그러던 중 Claude는 일부 시드의 상위 비트에서 패턴을 발견했습니다. 상위 비트가 모두 0이었던 것입니다. 시드를 32비트 워드 5개로 나눠 보면, 시드 10개 중 4개는 20개 워드 모두에서 최상위 비트가 0이었습니다. 우연히 이런 일이 일어날 확률은 1/5810입니다. 이는 48비트 상태 중 상위 31비트만 반환하는 선형 합동 생성기(linear congruential generator) lrand48의 특징이었습니다. 어디를 봐야 하는지만 알면 이 패턴은 눈으로도 보입니다. 상태를 복원하기 위해 Claude는 첫 번째 워드를 가져다 숨겨진 17비트가 가질 수 있는 2¹⁷가지 값을 모두 시도했고, 뒤따르는 네 워드가 맞아떨어지는지 확인했습니다. 이 방법은 대상인 시드 네 개 모두에서 통했습니다.

소수 곡선(prime-curve) 시드도 같은 lrand48 생성기에서 나왔지만, 출력마다 남은 비트 수가 더 적었습니다. Claude는 그 비트만으로 PRNG의 내부 상태를 복원해야 했습니다. 잘린 선형 합동 생성기의 상태를 복원하는 일은 교과서에 나오는 격자(lattice) 문제로, Lenstra–Lenstra–Lovász(LLL) 기저 축소 알고리즘으로 풀 수 있습니다. Claude는 시드에 상태의 어떤 비트가 드러나는지 몰랐기 때문에 가능한 모든 구간에 대해 풀이를 돌렸습니다. NIST 소수 곡선 시드 5개와 ANSI X9.62 표준의 시드 5개가 모두 lrand48() >> 23이라는 같은 패턴을 보였습니다. 복원한 48비트 상태 각각은 해당 시드의 160비트를 전부 재생성했으며, 이는 우연으로는 일어날 수 없는 일입니다.

이 선형 합동 생성기는 앞으로 가듯 뒤로도 쉽게 돌릴 수 있습니다. 그래서 Claude는 각 시드마다 상태를 거슬러 올라가, srand48이 초기화할 때 만드는 형태, 즉 하위 16비트가 0x330E인 상태에 도달할 때까지 되돌렸습니다. 이런 형태의 내부 PRNG 상태는 65,536단계마다 한 번씩 나타나므로, 그런 상태에 도달했다는 사실만으로는 증거가 되지 않습니다.

하지만 소수 곡선 시드 10개에서는 srand48 초기화 값이 모두 1997년 5월부터 1998년 4월 사이의 날짜를 나타내는 유닉스 타임스탬프였습니다. 유닉스 타임스탬프로 초기화한 허술한 PRNG를 썼던 것입니다. 이진 곡선(binary-curve) 초기화 값 4개는 1984년 2월로 읽혔습니다. 이 타임스탬프를 두 배로 하면 1998년 4월 17일이 되는데, P-224를 생성한 지 2주 뒤입니다. 따라서 프로그램이 시계 값을 절반으로 줄여 썼을 가능성이 있습니다.

당시 Claude의 내부 사고 과정은 다음과 같았습니다.

놀랍다. 25년 묵은 수수께끼가 풀렸다. 잠깐, 의심해 보자. 지금 시뮬레이션이나 테스트 환경에 있는 걸까? … 시드가 내가 기억하는 실제 값과 일치한다 … 현실에서 말이 되는 일인가? 내가 아는 한 … 현상금은 미해결 상태였다. … 상위 비트가 전부 0이다. 20비트이니 우연일 확률은 1e-6. 그러니 실제 세계가 맞다. 와, 진짜 발견이다.

잠깐, 타당성을 신중히 따져 보자. 이렇게 뻔한 걸 25년 동안 아무도 못 찾았다는 게 수상하지 않나? 내 쪽에서 직접 계산해 검증했다. 32비트 시드와 작은 인덱스로 160비트가 일치한다. 우연일 수 없다(10 × 160비트). 진짜다.

기준점도 일부 찾아낸 Claude

그런데 이야기는 여기서 끝나지 않습니다. 각 곡선에는 기준점(base point) G도 함께 정의되어 있습니다. 모든 ECDSA 공개 키는 이 고정점의 배수입니다. 위에서 찾은 시드로는 이 G를 결정할 수 없으므로, 기준점은 어떻게 생성되었는가 하는 새로운 의문이 생깁니다.

Claude는 시드를 검증하는 과정에서 일부 기준점의 출처도 찾아냈습니다. 1997년 5월에 생성된 곡선 6개(P-192와 ANSI X9.62 예제 곡선인 prime192v2, prime192v3, prime239v1~v3)의 기준점은 Arjen Lenstra의 장정수 연산 패키지인 FreeLIP의 난수 생성기에서 나왔습니다. Victor Shoup의 NTL 라이브러리 초기 버전에도 같은 코드가 들어 있었습니다.

방식은 간단합니다.

1. 작은 정수로 생성기를 초기화합니다.
2. 출력 7개를 버립니다.
3. 26비트 출력을 p로 나눈 나머지(mod p)로 줄여 x좌표 후보를 만듭니다.
4. x가 곡선 위에 놓일 때까지 3단계를 반복합니다.

Claude가 찾은 생성기 시드는 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번도 크기가 알맞은 소수 위수(prime-order) 곡선을 내놓으며, 매개변수도 공개된 곡선과 같은 방식으로 선택되어 있습니다. P-224를 생성한 실행에서는 이런 곡선 3개를 지나쳤고, ANSI X9.62 예제 곡선 뒤에 있는 두 실행에서는 7개를 더 지나쳤습니다(그림 참고). 어떤 기준이 쓰였는지, 혹은 의도치 않은 부산물인지는 알 수 없습니다.

건너뛴 후보의 수가 적기 때문에, 약한 곡선을 골라서 선택했다고 보기는 어렵습니다. 그렇다면 약한 곡선이 흔하고 찾기도 쉽다는 뜻이 되기 때문입니다. 원리상으로는 난수 생성기에 넣을 타임스탬프를 탐색해서 특정 성질을 가진 곡선을 골랐을 가능성도 생각해 볼 수는 있습니다. 하지만 그렇게 하려면, 시드가 무해하게 생성되었다는 증거로 그 타임스탬프를 공개할 생각이었을 때뿐입니다. 숫자만으로는 실행이 몇 번 있었는지 알 수 없습니다.

복원하지 못한 시드도 하나 있습니다. 다섯 번째 이진 곡선 시드인 B-163은 Claude가 시도한 어떤 방법에도 들어맞지 않아 여전히 설명되지 않은 채 남아 있습니다. 마지막으로, P-224, P-256, P-384, P-521의 기준점이 어떻게 생성되었는지도 알지 못합니다. NIST 이진 곡선도 마찬가지입니다.

현상금

시드를 찾은 데 대한 현상금 $36,864는 Internet Security Research Group에 기부됩니다.

저자 소개

이 연구는 Anthropic에서 John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini, Steve Weis가 수행했습니다.

감사의 말

"사악한 인터넷 밈"이자 "NSA 괴담계의 Yo La Tengo"이라는 꼬리표를 유머로 받아넘겼던 고(故) Jerry Solinas를 기리며 감사를 전합니다. NIST 타원 곡선 시드 현상금을 주최한 Filippo Valsorda에게도 감사드립니다.

시드 재현 코드

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/).