Skąd się wzięły krzywe NIST? Zagadka ziaren ECDSA

Liczby, którym trzeba było uwierzyć

Podpis cyfrowy ECDSA i krzywe eliptyczne z normy NIST zabezpieczają m.in. połączenia HTTPS. Szeroko stosowana krzywa P-256 trafiła do normy FIPS 186-2 w 2000 roku razem z czterema innymi: P-192, P-224, P-384 i P-521. Bitcoin poszedł inną drogą – o tym pod koniec artykułu.

Każda z tych krzywych ma postać y² = x³ − 3x + b, przy czym wszystkie rachunki wykonuje się modulo ustalonej liczby pierwszej p, czyli na resztach z dzielenia przez p. Współczynnika b nie wybrano ręcznie. Norma podaje 160-bitowe ziarno (ang. seed) i przepis: przepuść ziarno przez funkcję skrótu SHA-1, a z wyniku wyliczysz liczbę c, do której b musi pasować. Znalezienie ziarna, które da z góry narzucony wynik skrótu, jest w praktyce niewykonalne, więc nie da się dobrać ziarna pod upatrzone wcześniej b. Sprawdź ten przepis na prawdziwych liczbach z normy:

Czego ten rachunek dowodzi, a czego nie

Rachunek pokazuje, że opublikowane b pasuje do opublikowanego ziarna. Nie mówi natomiast nic o tym, skąd jest samo ziarno. Ziarna dostarczyła NSA, amerykańska agencja wywiadu elektronicznego, i nigdy nie wyjaśniła, jak powstały. Gdyby słabe krzywe zdarzały się dość często i dało się je rozpoznać, ktoś mógłby sprawdzać kolejne ziarna, aż któreś da słabą krzywą, i opublikować tylko to jedno. Neal Koblitz i Alfred Menezes opisali tę wątpliwość w 2015 roku w pracy „A Riddle Wrapped in an Enigma”.

Nieufność miała tło. We wrześniu 2013 roku, po ujawnieniu dokumentów NSA, NIST odradził używanie generatora liczb losowych Dual_EC_DRBG, podejrzewanego o ukrytą furtkę. To inna konstrukcja niż krzywe ECDSA, ale ze wspólnym źródłem nieufności: niewyjaśnionym pochodzeniem stałych. O ziarnach krążyła za to anegdota: Jerry Solinas z NSA wspominał, że były skrótami żartobliwego zdania w rodzaju „dajcie Bobowi i Jerry’emu podwyżkę”, ale szczegółów nikt nie pamiętał. Solinas zmarł w 2023 roku, zdania nie znaleziono, a nagroda za odkrycie pochodzenia ziaren czekała na zwycięzcę.

Ślad w najwyższym bicie

W październiku 2026 roku badacze z Anthropic zapytali model Claude, jak mogły powstać te ziarna, nie podsuwając mu anegdoty o zdaniu. Według ich relacji Claude znalazł odpowiedź w niecałe pół godziny, bo przyjął inne założenie: program z lat 90. najpewniej brał liczby ze zwykłego generatora z biblioteki języka C. Takie generatory są tak proste, że ich wyniki zostawiają rozpoznawalne ślady – pokazujemy to w artykule skąd komputer bierze losowość.

Generator lrand48 trzyma 48-bitowy stan i w każdym kroku liczy z niego następny według wzoru x′ = (a·x + c) mod 2⁴⁸. Na zewnątrz oddaje tylko 31 najwyższych bitów stanu. Każda taka wartość zapisana jako liczba 32-bitowa ma więc zero w najwyższym bicie. Oprócz pięciu krzywych P norma zawiera też pięć krzywych binarnych, od B-163 do B-571. Poszukaj śladu w ziarnach wszystkich dziesięciu:

Sam wzór zer to tylko poszlaka. Dowodem jest to, co dzieje się dalej. Ziarno krzywej binarnej to pięć kolejnych 32-bitowych wyników generatora. Pierwszy z nich zdradza 31 z 48 bitów stanu, a brakujące 17 bitów daje tylko 131 072 możliwości. Dokładnie jedna z nich odtwarza pozostałe cztery części ziarna. Taki generator można też cofać krok po kroku aż do stanu, który na starcie programu ustawia funkcja srand48. Jej argument okazał się znacznikiem czasu z zegara komputera.

Ziarno z zegara

Ziarna krzywych od P-192 do P-521 nie mają takiego śladu, bo program zostawiał z każdej liczby generatora tylko jej osiem najwyższych bitów. Odzyskanie stanu z tak okrojonych wyników to klasyczne zadanie, które rozwiązuje algorytm LLL (Lenstra–Lenstra–Lovász): wykorzystuje zależności między wieloma częściowo znanymi liczbami z tego samego generatora. Wynik był ten sam: ziarna wszystkich pięciu krzywych NIST i pięciu krzywych przykładowych z normy ANSI X9.62 pochodzą z lrand48 uruchomionego z datą i godziną z okresu od maja 1997 do kwietnia 1998 roku.

Program losował kolejne 20-bajtowe propozycje ziarna i sprawdzał, czy dają krzywą o właściwych parametrach. Ziarno P-256 to propozycja nr 1842 z uruchomienia 16 sierpnia 1997 roku o 01:52:34 czasu UTC. Autorzy odkrycia przekazali kod do domeny publicznej (CC0), więc każdy może to powtórzyć. Tu w przeglądarce:

Czy to słabość krzywych?

Nie. Odtworzenie ziaren nie jest atakiem na ECDSA i nie zmienia zaleceń co do wyboru krzywych (NIST i tak traktuje dziś P-192 jako krzywą historyczną, a krzywe binarne odradza). Autorzy uważają, że odkrycie raczej zwiększa zaufanie: generator z zegarem to mechanizm tak prosty, że trudno w nim coś ukryć. To jednak ich ocena, nie dowód – nikt nie wie, ile znaczników czasu wypróbowano, zanim zostały te opublikowane. Otwartych pytań jest więcej:

• Pominięte propozycje. Według autorów w uruchomieniu, z którego pochodzi P-256, wymagania spełniała już propozycja nr 876 (właściwy rozmiar i liczba punktów będąca liczbą pierwszą). Mimo to wybrano dopiero nr 1842. W innych uruchomieniach pominięto jeszcze kilka. Kryterium wyboru jest nieznane. Autorzy nie widzą w tym śladu manipulacji: pominięć jest mało, a celowe szukanie słabej krzywej miałoby sens tylko wtedy, gdyby słabe krzywe były częste.
• Zegar podzielony przez dwa. Odzyskane znaczniki czasu czterech krzywych binarnych wskazują luty 1984 roku. Pomnożone przez dwa dają 17 kwietnia 1998, dwa tygodnie po uruchomieniu dla P-224. To, że program dzielił wskazanie zegara przez dwa, jest hipotezą autorów.
• Czego nie wyjaśniono. Ziarna krzywej B-163 nie udało się odtworzyć. Nie wiadomo też, jak wybrano punkty bazowe krzywych P-224, P-256, P-384 i P-521 ani krzywych binarnych. Dla P-192 i pięciu krzywych z ANSI X9.62 autorzy odtworzyli współrzędną x punktu bazowego z generatora biblioteki FreeLIP Arjena Lenstry.

Nagroda za rozwiązanie zagadki – 36 864 dolary – zostanie według Anthropic przekazana Internet Security Research Group, organizacji prowadzącej Let’s Encrypt.

Bitcoin i krzywa bez ziarna

Gdy w styczniu 2009 roku Satoshi Nakamoto uruchomił Bitcoina, do podpisów transakcji nie wybrał P-256, tylko krzywą secp256k1 z normy SEC 2, przygotowanej przez grupę skupioną wokół firmy Certicom. W kodzie pierwszej wersji Bitcoina komentarz wymienia jako możliwości wyłącznie krzywe z tej samej rodziny „k”: secp160k1, secp192k1, secp224k1 i secp256k1. Żadnej z ziarnem.

Krzywa secp256k1 ma postać y² = x³ + 7. Nie ma w niej ziarna ani SHA-1. Według normy SEC 2 parametry tej rodziny wybierano tak, by krzywa miała szczególną budowę, która pozwala liczyć szybciej, i sprawdzano kolejne wartości, aż trafiono na krzywą, której liczba punktów jest liczbą pierwszą. Sprawdziliśmy to rachunkiem: przy tej liczbie p krzywe z b od 1 do 6 nie spełniają tego warunku, a dla b = 7 – spełniają. Mało liczb do wyjaśnienia to mało miejsca na ukrycie czegoś.

Wybór budził pytania już w 2011 roku. 9 stycznia Hal Finney, kryptograf i odbiorca pierwszej transakcji bitcoinowej od Satoshiego, napisał na forum Bitcoina, że to dość nietypowa krzywa. Według niego organizacje normalizacyjne unikały krzywych Koblitza, bo obawiały się, że ich wewnętrzną strukturę ktoś kiedyś wykorzysta do ataku. Finney sam nie tracił z tego powodu snu, ale zaproponował rozważenie przejścia na P-256 – także dlatego, że biblioteki kryptograficzne obsługiwały ją szerzej.

Mike Hearn zapytał wtedy Satoshiego wprost, czy chodziło o szybkość. Satoshi odpisał 10 stycznia 2011 roku, że ECDSA było wówczas dość nowe i nie znalazł wskazówek, którą krzywą wybrać: „I didn’t find anything to recommend a curve type so I just... picked one” – po prostu wybrał jedną. Liczył, że duży rozmiar klucza wynagrodzi ewentualne słabości (korespondencja opublikowana przez Hearna). Miesiąc później Finney zaczął implementować przyspieszenie oparte właśnie na szczególnej budowie secp256k1.

Ten e-mail warto zestawić z popularną w sieci tezą, że Satoshi celowo ominął krzywe NIST z nieufności wobec NSA. Nie potwierdza jej: Satoshi pisał tylko, że nie znalazł wskazówek co do wyboru krzywej i po prostu jedną wybrał.

Ironia polega na tym, że po ujawnieniach z 2013 roku nasiliła się nieufność wobec niewyjaśnionych ziaren krzywych NIST, w tym właśnie P-256, na którą Finney proponował się przenieść. Spór o obie krzywe trwa w różnych formach:

• Szczególna budowa. secp256k1 należy do rzadkiej klasy krzywych o szczególnej symetrii matematycznej (ma bardzo mały tzw. wyróżnik mnożenia zespolonego, CM). Zestawienie SafeCurves Daniela Bernsteina i Tanji Lange stawia ostrożny warunek, by wartość bezwzględna tego wyróżnika była duża, a secp256k1 go nie spełnia. Nie oznacza to znanego ataku.
• Swoboda twórców. Według oceny SafeCurves P-256 dawała twórcom pole do manipulacji, bo jej współczynnik pochodzi z niewyjaśnionego ziarna. Nie jest to zarzut, że manipulacja nastąpiła. secp256k1 jest tam „częściowo sztywna”, czyli jej twórcy mieli mało swobody: p i współczynniki nie są w pełni uzasadnione, choć mogą być po prostu najmniejszymi działającymi wartościami. Obie krzywe nie spełniają też kilku innych kryteriów tego zestawienia.
• Uznanie z zastrzeżeniem. NIST w wytycznych SP 800-186 z lutego 2023 roku dopuszcza secp256k1 do zastosowań związanych z blockchainem.

Ostatnia zagadka dotyczy punktu bazowego G. To ustalony punkt krzywej, od którego zaczyna się każdy klucz publiczny: klucz publiczny to G dodane do siebie tyle razy, ile wynosi klucz prywatny. Norma SEC 2 podaje G bez wyjaśnienia, skąd się wziął. Sprawdź sam:

Ten ślad nie osłabia Bitcoina. Na krzywej, której liczba punktów jest liczbą pierwszą, rolę punktu bazowego może pełnić każdy punkt oprócz tzw. punktu w nieskończoności, który działa tu jak zero w dodawaniu. Kto potrafiłby złamać klucze dla jednego punktu bazowego, czyli rozwiązać tzw. problem logarytmu dyskretnego, zrobiłby to równie łatwo dla każdego innego. Historia obu krzywych pokazuje, że niewyjaśnione liczby budzą podejrzenia latami, nawet jeśli wyjaśnienie okazuje się banalne – jak zegar i lrand48.

Czy sztuczna inteligencja łamie ECDSA?

Nie. Odkrycie opisane w tym artykule to wyjaśnienie, jak powstały liczby w normie, a nie sposób na łamanie kluczy. W październiku 2026 roku łatwo jednak było odnieść inne wrażenie. Nieco ponad tydzień przed publikacją odkrycia Anthropic głos zabrał Justin Drake z Ethereum Foundation. Ostrzegł, że dzięki postępom w matematyce AI może złamać ECDSA szybciej niż komputery kwantowe – w najgorszym razie „w ciągu miesięcy, nie lat”. Zaproponował tzw. tryb bunkra: spokojne przenoszenie środków na adresy, które nie ujawniły jeszcze klucza publicznego.

Yehuda Lindell, szef kryptografii w Coinbase, odpowiedział, że nie ma żadnych dowodów na osłabienie założeń stojących za ECDSA. Z kolei Vitalik Buterin odradzał pospieszne przenosiny środków, bo łatwo przy nich coś stracić (relacja The Block). Żadna z tych wypowiedzi nie przedstawiła ataku na ECDSA. Znanym zagrożeniem pozostaje dostatecznie duży komputer kwantowy, choć nie wiadomo, kiedy powstanie. Wykorzystując algorytm Shora, odtworzyłby klucz prywatny z publicznego, i to zarówno dla P-256, jak i dla secp256k1. Dlatego NIST w sierpniu 2024 roku opublikował pierwsze normy podpisów odpornych na komputery kwantowe, FIPS 204 i FIPS 205.

Lekcja dla każdego losowania

• Zegar to nie losowość. Kto zna przybliżony czas uruchomienia, sprawdzi wszystkie sekundy: cała doba to tylko 86 400 możliwości. Dlatego nasze narzędzia, z generatorem haseł na czele, biorą losowość z kryptograficznego generatora przeglądarki, a nie z zegara ani z Math.random().
• Opublikowane ziarno to za mało. Pokazuje, że wynik da się z niego wyliczyć, ale nie dowodzi, że samego ziarna nie wybrano spośród wielu prób. Uczciwe losowanie musi z góry wskazać źródło, którego wartości nikt jeszcze nie zna – tak działa weryfikowalne losowanie z drand, gdzie wynik pochodzi z rundy ogłoszonej dopiero po zobowiązaniu, a umówiona z góry godzina losowania utrudnia ukrycie dodatkowych prób.
• Sprawdzaj, zamiast wierzyć. W przeglądarce sprawdzisz tu związek ziarna z b, odtworzysz ziarna z zegara i policzysz G/2. Pozostałe wyniki, np. odzyskanie stanu metodą LLL, opisujemy za autorami odkrycia, a rachunek dla b od 1 do 7 sprawdzają testy kodu tej strony. Do sprawdzania losowań służy weryfikacja losowania.

Źródła: Anthropic, „Claude reveals ECDSA curve origins” (16 października 2026), NIST FIPS 186-4, dodatki D.1.2 i D.6, N. Koblitz, A. Menezes, „A Riddle Wrapped in an Enigma” (2015), SEC 2 v2.0, rozdz. 2.1 i 2.4.1, NIST SP 800-186, SafeCurves (odczyt 17 października 2026), korespondencja Satoshiego z Mike’em Hearnem i wątki Hala Finneya na bitcointalk.org (linki w tekście).