Claude 半小時追出 NIST 曲線種子：P-256 來自 1997-08-16 01:52:34、候選第 1,842 次；賞金 36,864 美元捐 Let's Encrypt

那串十六進位 C49D360886E704936A6678E1139D26B7819F7E90 掛在 NIST P-256 規格裡超過四分之一世紀。瀏覽器核對網站憑證、許多程式碼簽章、大量 TLS 握手，都踩在同一條橢圓曲線上。種子從哪裡來，規格沒寫。NSA 數學家 Jerry Solinas 2015 年回憶，可能是某句幽默口號的雜湊，連他自己也記不清。

Anthropic 一名員工把這題丟給內部研究用的 Claude，沒有把那句口號線索餵進去。半小時內，模型對上了 1990 年代 C 函式庫裡的 lrand48：P-256 種子是 1997 年 8 月 16 日 01:52:34 UTC 那一秒鐘啟動的產生器，跑到第 1,842 個 20 位元組候選。

官方第一段就先把讀者要做的事寫死：當成一篇收尾的考古，沒有要改憑證、沒有要換曲線、沒有要立刻重簽網站。Filippo Valsorda 在賞金頁用 Go 重寫同一套流程後核過輸出，並在 UTC 10 月 15 日 01:07:51 受理全額賞金。十人小組選擇捐給營運 Let's Encrypt 的 Internet Security Research Group，金額依當初規則乘三，落到 36,864 美元（36 Ki$）。

官方原文寫：這不是密碼學破解、新攻擊，也不是 ECDSA 曲線本身的弱點。多數研究者本來就信任這些曲線。Enjoy.

CryptoBriefing 把同一件事講得更白話：最好的結果，本來就該是「無聊」。

種子怎麼被做出來

NIST 在 2000 年把 P-192、P-224、P-256、P-384、P-521 寫進 FIPS 186-2。規格依 ANSI X9.62：先給一顆任意種子，用 SHA-1 雜湊，再推出曲線係數 b。被追問了二十多年的，不是雜湊步驟，是那顆「任意種子」本身。P-256 那串 C49D3608…7E90 就是例子。

Claude 沒有去撞幽默口號。它先假設 1990 年代寫曲線產生程式的人，會用當時 C 函式庫內建的偽隨機數產生器。那些產生器夠弱，輸出可以被認出來。模型寫了一支掃描器，沿著每顆已公開種子一次移一 bit，測試相鄰區塊是不是某套 1990 年代產生器的連續輸出，一共試了 34 種「產生器 × 切片」組合。

它先看見一個肉眼就能核的簽名：把十顆素數域種子寫成五個 32-bit 字時，其中四顆每個字的最高 bit 全是 0。隨機碰上的機率約 1/5,810。這正是 lrand48 的指紋——它每次只吐 48-bit 狀態的高 31 bit。對那四顆種子，模型拿第一個字、窮舉隱藏的 17 bit（2¹⁷ 種），檢查後面四個字是否接著出現，四顆都對上。

其餘素數域種子留下的 bit 更少。從截斷的線性同餘產生器還原內部狀態，是教科書等級的格問題，用 Lenstra–Lenstra–Lovász（LLL）基底約化就能做。模型不知道種子露出的是哪一段，於是對每個視窗都跑一次求解器。五顆 NIST 素數域種子，加上 ANSI X9.62 另外五顆範例曲線，全部對上同一條規則：lrand48() >> 23。還原出的 48-bit 狀態可以再生全部 160 bit 種子，不是碰巧對上幾個位元。

線性同餘產生器能往前走也能往後走。模型把狀態往回退，直到出現 srand48 初始化會留下的形式：低 16 bit 等於 0x330E。這種形式每 65,536 步才出現一次，單靠碰到一次還不能當證據。真正把故事釘死的是時間：十顆素數域種子的初始化，全部是 1997 年 5 月到 1998 年 4 月之間的 Unix 時間戳。

四顆二進位域曲線（B-233、B-283、B-409、B-571）的初始化讀起來像 1984 年 2 月；時間戳乘以 2 之後，落到 1998 年 4 月 17 日，比 P-224 那一次晚兩週。官方推測當時程式可能把時鐘除以 2。Valsorda 補充：沒人在用那些 B 曲線，所以這條支線比較像考古註腳。

流程可以縮成四步。用當下 Unix 時間呼叫 srand48；每次抽 20 個位元組當候選種子；拿 ANSI X9.62 規則檢查能不能長出合法曲線；不合法就繼續抽。同一顆時間戳可以連抽多次，所以 1997-05-15 那一秒鐘同時養出三條 prime239 範例曲線，1997-05-18 那一秒鐘同時養出 P-192 和兩條 prime192 範例。

Claude 在內部推理裡寫過一段幾乎像人類的自我檢查：先說「這解開了 25 年的謎」，立刻問自己是不是在模擬環境，再拿種子與記憶中的公開值對表，最後用「20 個最高 bit 全清、機率約 10⁻⁶」以及「十顆種子 × 160 bit 對上 32-bit 種子加小索引」把巧合排除掉。官方把這段思考公開了。它用的是大型語言模型認舊軟體指紋、再寫求解器的路，不是把幽默口號當密碼去撞。

基點 G 也被追到一部分

每條曲線還有一個基點 G：所有 ECDSA 公鑰都是這個點的倍數。上面的種子推不出 G。Claude 在核種子時，一併找到其中六條曲線的基點來源：1997 年 5 月產出的 P-192，以及五條 ANSI X9.62 範例曲線（prime192v2、prime192v3、prime239v1 到 v3）。它們來自 Arjen Lenstra 長整數套件 FreeLIP 裡的隨機數產生器；Victor Shoup 的 NTL 早期版本帶過同一段程式碼。

食譜也很短：用一個小整數當種子，丟掉前七次輸出，再把 26-bit 輸出對模數 p 取餘當成候選 x 座標，直到點落在曲線上。官方公開的產生器種子是：P-192 用 20000，prime239v1 到 v3 用 20420、20507、20509，prime192v2 / v3 用 20512、20517。重跑程式後，六條的 x 座標都與規格一致。官方寫，就他們所知，此前沒有任何 NIST 基點被解釋過。

P-224、P-256、P-384、P-521 的基點對不上這套食譜。NIST 二進位域曲線的基點同樣沒解開。B-163 那顆種子，模型試過的組合全部落空，現在仍是唯一沒被還原的二進位種子。

被跳過的合法曲線，以及 30 bit

不是每個 20 位元組候選都能長出可用曲線。更麻煩的是：有些看起來合法的曲線也被跳過了。P-256 同一輪裡，第 876 個候選已經能長出正確大小、同樣選參方式的素數階曲線，規格卻採用第 1,842 個。P-224 那一輪跳過三條；ANSI X9.62 範例曲線那兩輪再跳過七條。官方說不知道篩選條件是什麼，也不知道是不是無心的程式瑕疵。

Valsorda 另外量到一條規格沒寫的拒絕條件：若曲線階 n 的 bit 長度大於基底域 p 的 bit 長度，種子會被丟掉（還不是更嚴的 n 小於 p，因為 prime239v2 滿足 p 小於 n 小於 2²³⁹）。扣掉這條之後，仍大約有兩倍於已發表數量的合法種子。空隙不規則。他列過兩種還說得通的猜測：同一顆 RNG 在驗證種子時自己消耗了輸出；或者 1997 年那套曲線合法性檢查有 bug，錯判大約一半——這些計算現在用現成軟體幾分鐘能做完，當時仍接近前沿。

跳過的候選不多，官方因此不認為「故意選弱曲線」說得通：那會暗示弱曲線既常見又好找。理論上仍可對時間戳做搜尋，讓產生器吐出帶特定性質的曲線。官方補了一句：你通常只會在打算公開時間戳、當作「種子是無辜產生的證據」時才這麼做；數字本身看不出一共跑過幾輪。

Hacker News 主串過 900 分、三百多則留言。最集中的爭點不是「lrand48 有沒有對上」，而是「對上產生方法，等不等於對上選擇方法」。有人抓住官方自己那句「仍可想像對時間戳搜尋」；也有人問，為什麼後來的曲線 n 愈來愈大，是不是愈找愈用力。Valsorda 自己回串：就算假設對方能挑 1997–98 任何一秒、再從每輪前 16 個素數階候選裡任意選（已把未解釋的拒絕算進去），自由度也大約只剩 30 bit。要在 256-bit 橢圓曲線裡隨機撞上夠大一類弱曲線，本身會是足以推翻整套 ECC 的密碼分析突破。

2017 年，Daniel Bernstein 與 Tanja Lange 向 Koblitz、Menezes 描述過一種手法：若種子選擇有約 70 bit 自由度，理論上可以瞄準一類大約 2⁶¹ 條弱素數階曲線。Bernstein 也是競爭設計 Curve25519 的作者。Valsorda 寫，這週的結果把那條手法直接排除。30 bit 不夠瞄準那類弱曲線，也不夠塞進 NOBUS 後門。Koblitz 與 Menezes 2015 年的論文〈A Riddle Wrapped in an Enigma〉第 3.1 節本來就認為，就算有 160 bit 自由度，NSA 要藏弱點也不合理；現在連那點選擇空間都大幅縮小。

這件事會被拿出來反覆講，是因為 2013 年 Dual_EC_DRBG 的揭露，讓 NSA 參與標準化這件事本身變成長期政治傷口。P-256 沒解釋的種子，後來經常跟那條後門故事綁在一起。Solinas 2015 年寫給 Bernstein 的信裡，記得的是「幫 Bob 和 Jerry 加薪」這類口號，還說 Bob Reiter 寫了程式、細節雙方都忘了，舊檔案大概躺在「約櫃旁邊那顆硬碟」上。Solinas 2023 年初過世。Valsorda 說記憶會騙人：現在對上的是 POSIX 標準的 drand48，不是那句被忘掉的英語。

留言區仍有人不買單。一種說法是：Solinas 當初故意講錯，就是為了讓來源永遠講不清。另一種是：時間戳可以事後偽造成「看起來像 1997 年跑過」。這兩種都還沒有對得上公開程式與十顆種子的新證據。Valsorda 的立場寫在賞金頁結尾：加上確定性與 hedged（對沖式）ECDSA 簽章、形式化驗證過的體運算、以及 2015 年 Renes、Costello、Batina 的完整加法公式，NIST 橢圓曲線的「平反弧」對他來說已經走完，他個人會把 NIST 曲線排到 Curve25519／Ed25519／X25519 前面。下一句是冷的：剛好趕上它們要被後量子簽章換掉。

賞金、獨立重跑，以及模型實際做了什麼

Valsorda 2023 年 10 月開出這項賞金時，現金是 12,288 美元（12 Ki$）；捐給合格的 501(c)(3) 則乘三。半額給第一顆被解的種子，另半額給五顆 NIST 素數域種子全部解完。Anthropic 十人小組——John Wood、Henry de Valence、Ava Howell、Zack Voase、Lucy Sweet、Amir Omidi、Paul Crowley、Iain McGinniss、Nicholas Carlini、Steve Weis——一次領完，並指定 ISRG。Amir Omidi 同時出現在解題名單與賞金贊助名單裡。

獨立核對不是口頭背書。Valsorda 公開寫他用 Go 重實現，輸出對得上。Anthropic 頁面把產生種子與核對基點的 Python 程式直接貼出，授權 CC0。任何人現在都能在自己的機器上，用同一組時間戳與候選序 n，印出 P-256 那串 C49D3608…。這和「模型說它找到了」不是同一層證據。實驗室用模型長證明、再用 Lean 核對的做法，本月稍早已出現在 OpenAI 那批 722 篇數學手稿裡；差別是這次公開的是可重跑的產生程式，不是一疊還沒全部核完的手稿。

模型這邊的工作方式，比較接近寫掃描器的研究助理，而不是聊天機器人答題。提示詞沒有把「去雜湊那句口號」當主軸；員工先前依這條線索追過，失敗了。換過角度之後，AI 做的是：猜 1990 年代程式會用哪類 PRNG、寫掃描器、認 lrand48 指紋、還原狀態、把狀態退回 srand48、對上 Unix 時間。人類同事把結果收成可重跑的程式，再拿去領賞金。Hacker News 有人把「半小時」讀成「零成本」；官方寫法是內部研究模型、一名好奇的員工、先前整組人依錯誤線索追過。

對開發者和維運的實務影響，目前被寫成「信心，不是程式碼」。曲線參數沒變，憑證不用撤，函式庫不用為了這則新聞緊急改曲線。該檢查的是另一件事：你們的密碼學盤點裡，P-256 被標成「來源不明、可能有後門」，還是「來源已重跑、選擇空間約 30 bit、基點仍有缺口」。兩種標籤會導向不同的遷移優先順序。後量子簽章時程、對 Curve25519 的既有投資、對 NIST 曲線的合規要求，都不會因為一則考古被自動改寫；被改寫的是「為什麼有人當初不肯用 P-256」這段理由裡，最常被引用的那一條。

仍沒被填上的格子，比慶祝文案長。B-163 種子下落不明。P-224 起四條 NIST 素數域曲線的基點來路不明。合法但未發表的候選為什麼被丟，Valsorda 與官方都還沒給出對得上空隙的規則。時間戳搜尋在原則上仍可想像，只是空間已不夠支撐 Bernstein–Lange 那類弱曲線瞄準。這些缺口不否定這次對上的產生方法，它們標出下一題還能問什麼。

若你手上有舊標準、舊測試向量、或一串從沒人解釋過的常數，這則新聞給的方法比口號更具體：先假設它是當時語言標準庫裡的弱 PRNG，再讓模型去認指紋，最後一定要用人手把程式重跑一遍。半小時是模型掃描的時間，不是這則聲明可以被相信的時間。可以被相信的，是公開程式、獨立重跑，以及那串掛了二十六年的種子現在對得上哪一秒鐘。