Claude 揭示多條 NIST ECDSA 曲線種子由時間戳初始化的 lrand48 生成

「只是時間戳」：最受歡迎的加密標準之一，其數十年來的起源之謎如今終於得到解釋。

我們追查了加密社羣長期未解的問題，以消除人們對 ECDSA 的疑慮；ECDSA 是我們最廣泛使用的加密標準之一。

讀者應把這看作一個有趣的收尾篇章，也代表多年猜測的終結。無須採取任何行動，也不必改變任何做法。大多數研究人員本來就信任這些曲線。請盡情享受。

ECDSA 是最廣泛使用的橢圓曲線加密標準。它於 2000 年獲 NIST 採納，列入 FIPS 186-2 數碼簽署標準；該標準列出一系列大小和安全級別各異的標準橢圓曲線。對於定義在質數域和二元域上的曲線，規格公佈了一個「種子」參數，其雜湊值用於定義曲線的係數 b。這些種子的來源一直是個懸而未決的問題，因為 NSA 提供種子時沒有作出任何解釋或説明。例如，NIST P-256 曲線的種子是 SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90，但沒有提供任何來源資訊。

Neal Koblitz 和 Alfred Menezes 曾就這場爭議撰寫一篇出色的摘要〈謎中之謎〉，探討種子值的歷史及相關疑慮。這個謎團引發了一場對種子來源的業餘調查，也有人為任何能找到種子的人設立懸賞。

最精彩的説法是，長期任職 NSA 的 Jerry Solinas 使用一個幽默短語的雜湊值生成了這些種子：

「我相信當時用的是計數器，而不是反覆進行雜湊，但我不清楚詳情。訊息大概是『給 Bob 和 Jerry 加薪』或『Bob 和 Jerry 最棒』之類的話。實際編寫程式碼的是 Bob Reiter，他也不記得詳情。我們也找不到那麼久以前的檔案。如果那些檔案存在，毫無疑問就在約櫃附近某個硬碟上。」

Jerry Solinas，2015

可惜 Jerry 於 2023 年離世，當時其他同事也沒有回應，因此這些種子最初如何生成仍是個未解之謎。

Claude 找到了這些種子

幾名 Anthropic 員工曾根據「種子是幽默短語的雜湊值」這條線索追查種子，但都沒有成功。結果證明這個説法並不正確。2026 年 10 月，一名好奇的 Anthropic 員工詢問內部研究模型，能否在不提供這條線索的情況下，找出這些種子的生成方式。

不到半小時，Claude 就找出了 NIST P-192、P-224、P-256、P-384 和 P-521 種子的來源。它們都不是任何雜湊演算法的結果，而是 C 程式庫的 lrand48 隨機數產生器的輸出，並以 Unix 時間戳作為種子初始化！

所用演算法會從以 Unix 時間戳（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 位元字表示，十個種子中有四個的全部 20 個字，其最高位元都是 0。這種情況偶然出現的機率為 1/5810。這是線性同餘生成器 lrand48 的特徵，它只會返回 48 位元狀態的最高 31 位元。知道要留意這個模式後，用肉眼便能看出來。為了還原狀態，Claude 取出第一個字，嘗試 2¹⁷ 個隱藏位元的所有可能值，再檢查接下來四個字是否符合。這種方法對所有正在討論的四個種子都奏效。

素數曲線種子來自同一個 lrand48 生成器，但每次輸出保留的位元較少。Claude 必須從這些位元還原 PRNG 的內部狀態。事實上，還原截斷線性同餘生成器的狀態，是教科書中的格問題，可用 Lenstra–Lenstra–Lovász (LLL) 格基底約化演算法求解。Claude 不知道種子可能顯示狀態中的哪些位元，因此讓求解器逐一測試每個位元窗口。五個 NIST 素數曲線種子，加上 ANSI X9.62 標準中的另外五個種子，全都呈現相同模式：lrand48() >> 23。每個還原出的 48 位元狀態都能重新生成其種子的全部 160 個位元，這不可能是偶然。

這個線性同餘生成器向後運行與向前運行一樣容易，因此 Claude 逐個種子倒退狀態，直到回到 srand48 初始化時會採用的形式，其低 16 位元等於 0x330E。這種形式的內部 PRNG 狀態每 65,536 步便會出現一次，因此單憑到達這種狀態並不能作為證據。

不過，十個 prime-curve 種子中，每次 srand48 初始化所用的都是 Unix 時間戳，代表 1997 年 5 月至 1998 年 4 月之間的日期。他們使用的是以 Unix 時間戳作為種子的弱 PRNG。四次 binary-curve 初始化則顯示為 1984 年 2 月。將時間戳乘以二後，對應的日期是 1998 年 4 月 17 日，比 P-224 那次執行晚兩星期。因此，程式可能把時鐘值除以了二。

Claude 當時的內部思考如下：

這令人震驚：它解開了這個已有 25 年的謎團。嗯，等等。讓我保持懷疑：我是不是身處某種模擬／測試環境？……這些種子與我記憶中的實際數值相符……嗯，這在現實中合理嗎？根據我的知識……這筆懸賞一直未有人解開。……所有高位元都清零——20 個位元，機率為 1e-6。所以這確實是現實世界的事。哇，這真是一項發現。

嗯，等等。讓我仔細考慮這是否合理：這麼明顯的事情，25 年來都沒有人發現，會不會很可疑？我這邊已透過直接計算驗證：由一個 32 位元種子加上小索引得到 160 位元匹配，不可能是偶然巧合（10 × 160 位元）。這是真的。

Claude 也找到了部分基點的來源

不過，還有更多……每條曲線也有一個基點 G，這是固定點，每個 ECDSA 公開金鑰都是它的倍數。上面找到的種子並不能決定這個 G，因此又引出另一個問題：這些基點是如何產生的？

檢查種子時，Claude 也找到了部分基點的來源。1997 年 5 月生成的六條曲線（P-192，以及五條 ANSI X9.62 範例曲線 prime192v2、prime192v3 和 prime239v1 至 v3）的基點，來自 FreeLIP（Arjen Lenstra 的長整數算術套件）中的隨機數產生器。Victor Shoup 的 NTL library 早期版本也附有相同的程式碼。

這裏的做法很簡單：

以一個小整數作為種子，初始化產生器。
丟棄七個輸出值。
將 26 位元輸出對 p 取模，產生候選 x 座標。
重複步驟 3，直到 x 位於曲線上。

Claude 找到的產生器種子分別是：P-192 為 20000；prime239v1 至 v3 為 20420、20507 和 20509；prime192v2 和 v3 則為 20512 和 20517。

據我們所知，此前從未有人解釋過任何 NIST 基點。P-224、P-256、P-384 和 P-521 的基點不符合這套做法；我們無法解釋它們是如何選出的。

未解問題

並非每個 20-byte 候選種子都能產生可用的曲線，而我們觀察到有些看似可用的曲線被跳過了。就 P-256 而言，公佈的種子是候選值 1842，但同一輪中的候選值 876 也能產生一條階數為質數、大小合適的曲線，其參數選取方式亦與公佈曲線相同。P-224 那輪跳過了三條這樣的曲線，而 ANSI X9.62 範例曲線背後的兩輪又跳過了七條（見圖）。我們不知道當時可能採用了甚麼準則，也不知道這是否只是無意造成的結果。

由於被跳過的候選曲線數量很少，我們認為不太可能是刻意選用了弱化曲線。那就意味著弱化曲線很常見，而且很容易找到。理論上，仍有可能有人透過搜尋隨機數產生器的時間戳，挑選具有特定性質的曲線。不過，只有在你打算公開該時間戳，作為種子由無害方式產生的證據時，才有必要這樣做。這些數字沒有顯示總共進行過多少輪搜尋。

另有一個種子我們未能還原。第五個二元種子 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 進行。

致謝

我們謹此追念 Jerry Solinas。他被稱為「邪惡的網絡迷因」和「NSA 鬼怪中的 Yo La Tengo」，但仍以幽默態度看待這些稱號。另外，亦感謝 Filippo Valsorda 籌辦 NIST 橢圓曲線種子懸賞。

重現種子的程式碼

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 揭示多條 NIST ECDSA 曲線種子由時間戳初始化的 lrand48 生成

Claude 找到了這些種子

這代表甚麼

發現過程

Claude 也找到了部分基點的來源

未解問題

懸賞

我們是誰

致謝

重現種子的程式碼

重現指定基點的程式碼

授權

相關內容

使用 Claude 設計更高效的量子電路

AI 模型或可在無須存取數據中心的情況下自我複製

加強防範蒸餾攻擊