«Это просто временные метки»: Claude вывел происхождение seed-значений кривых NIST меньше чем за полчаса

Что нашла модель

В октябре 2026 года сотрудник Anthropic спросил внутреннюю исследовательскую модель, можно ли понять, как были получены seed-значения кривых NIST, не подсказывая ей известную версию. Меньше чем за полчаса модель нашла происхождение seed-значений для P-192, P-224, P-256, P-384 и P-521.

Ни одно из них не оказалось результатом хеш-функции. Все они — вывод генератора псевдослучайных чисел lrand48 из стандартной библиотеки C, инициализированного отметкой времени Unix. Алгоритм выдавал байты очередями по 20 штук: первые 20 байт — первый кандидат, следующие 20 — второй, и так далее; для стандартизированного seed P-256 потребовалось 1842 итерации.

В публикации отдельно подчёркнуто, чего эта находка не означает: это не криптографический взлом, не новая атака и не слабость самих кривых ECDSA. Авторы пишут, что результат скорее повышает уверенность в том, что кривые выбирали без закладок и намеренных слабостей, и просят читателей воспринимать текст как финальную главу многолетних спекуляций, а не как повод что-то менять.

Почему происхождение seed-значений было загадкой

ECDSA — самый распространённый стандарт криптографии на эллиптических кривых; NIST принял его в 2000 году в составе FIPS 186-2 вместе с набором стандартных кривых разного размера и уровня стойкости. Для кривых над простыми и бинарными полями спецификация публиковала параметр «seed», хеш которого задаёт коэффициент b кривой, а происхождение этих значений оставалось открытым вопросом: их предоставила АНБ без объяснений и обоснований. Стандарт FIPS 186-2 сам определяет SEED как произвольную последовательность длиной не менее 160 бит, из которой строится простое число q, а затем и кривая.

Пример из публикации — seed кривой P-256: SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90, и никакой информации о его происхождении не прилагалось.

Об этой истории писали Neal Koblitz и Alfred Menezes в разборе «A Riddle Wrapped in an Enigma»; были и любительское расследование происхождения seed-значений, и денежное вознаграждение за их находку. Лучшей версией была история о том, что сотрудник АНБ Джерри Солинас получил эти значения хешем шутливой фразы: в 2015 году он рассказывал, что, возможно, использовался счётчик, а сообщение было в духе «Give Bob and Jerry a raise», но деталей не помнил никто, включая написавшего код Боба Рейтера, и архивов тех лет не нашлось. Солинас умер в 2023 году, и вопрос о том, как именно выведены seed-значения, оставался без ответа.

Как искали: генератор вместо фразы

Поиск по фразе, построенной из слухов, ничего не дал, и модель попробовала другой угол зрения: предположила, какой должна была быть программа, генерировавшая кривые. Ставка была на генератор псевдослучайных чисел из библиотек C 1990-х годов — такие генераторы достаточно слабы, чтобы их вывод можно было распознать и, возможно, восстановить состояние инициализации.

Модель написала сканер, который скользил по каждому опубликованному seed по одному биту и проверял, являются ли соседние фрагменты последовательными выводами генератора того времени. Сканирование покрыло 34 комбинации генератора и срезов вывода, после чего модель заметила закономерность в старших битах части seed-значений: они были нулевыми — вероятность случайного совпадения такой картины оценивается как 1 к 5810.

Это оказалось подписью линейного конгруэнтного генератора lrand48, который возвращает только старшие 31 бита 48-битного состояния: узор становится виден глазом, если знать, что искать. Чтобы восстановить состояние, модель брала первое слово, перебирала все 2 в степени 17 вариантов 17 скрытых битов и проверяла, следуют ли за ним остальные четыре слова; для обсуждавшихся четырёх seed-значений это сработало.

LLL и усечённый генератор

Seed-значения кривых над простыми полями пришли из того же lrand48, но сохраняли меньше битов каждого вывода. Восстановление состояния усечённого линейного конгруэнтного генератора по таким данным — учебная задача на решётках, которая решается приведением базиса алгоритмом Ленстры — Ленстры — Ловаса (LLL).

Модель не знала, какие именно биты состояния показывают seed-значения, поэтому прогнала решатель по всем окнам. У пяти seed-значений кривых NIST над простыми полями и у пяти дополнительных из стандарта ANSI X9.62 картина оказалась одной и той же: lrand48() >> 23; каждое восстановленное 48-битное состояние воспроизводит все 160 бит своего seed-значения, а такое совпадение случайным быть не может.

Обратный ход: даты 1997–1998 годов

Линейный конгруэнтный генератор так же легко работает назад, поэтому для каждого seed-значения модель отступала по состояниям до формы, которую задаёт инициализация srand48: у неё младшие 16 битов равны 0x330E. Такое состояние встречается примерно раз в 65 536 шагов, так что само по себе оно ничего не доказывает.

Дальше картина сложилась: для десяти seed-значений кривых над простыми полями каждая инициализация srand48 оказалась отметкой времени Unix, соответствующей дате между маем 1997 и апрелем 1998 года. Четыре инициализации для бинарных кривых читались как февраль 1984 года, а если отметки времени удвоить, они попадают на 17 апреля 1998 года — через две недели после запуска для P-224, то есть программа, возможно, делила показания часов пополам.

Базовые точки: второй слой находок

Помимо seed-значений у каждой кривой есть базовая точка G, то есть фиксированная точка, кратной которой является каждый открытый ключ ECDSA; seed этот выбор не определяет. Проверяя seed-значения, модель нашла и происхождение части базовых точек.

Базовые точки шести кривых, сгенерированных в мае 1997 года — P-192 и пяти примерных кривых ANSI X9.62 prime192v2, prime192v3 и prime239v1–v3, — пришли из генератора случайных чисел пакета FreeLIP для длинной арифметики, написанного Арьеном Ленстрой; ранние версии библиотеки NTL Виктора Шоупа поставлялись с тем же кодом. Рецепт оказался простым: инициализировать генератор небольшим целым числом, отбросить семь выводов, получать кандидаты в координату x из 26-битных выводов по модулю p и повторять до тех пор, пока x не окажется на кривой. Найденные начальные значения: 20000 для P-192, 20420, 20507 и 20509 для prime239v1–v3, 20512 и 20517 для prime192v2 и v3.

Что осталось необъяснённым

Не каждый 20-байтовый кандидат давал жизнеспособную кривую, и часть потенциально пригодных вариантов была пропущена. Для P-256 опубликован кандидат 1842, но кандидат 876 из того же прогона тоже даёт кривую с простым порядком нужного размера и параметрами, выбранными тем же способом; прогон для P-224 прошёл мимо трёх таких кривых, а два прогона примерных кривых ANSI X9.62 — ещё мимо семи. По каким критериям пропускали кандидатов и был ли это непреднамеренный артефакт, авторы не знают.

Поскольку пропущенных кандидатов мало, авторы считают малоправдоподобным, что отбирались ослабленные кривые: это означало бы, что ослабленные кривые встречаются часто и находятся легко. Они оговаривают и другую возможность — поиск по отметкам времени генератора, — но замечают, что это имело бы смысл только при намерении предъявить отметку как доказательство безобидной генерации, и по числам нельзя понять, сколько было прогонов.

Открытыми остаются и конкретные вопросы: seed-значение пятой бинарной кривой B-163 не подошло ни под одну проверенную версию, а как получены базовые точки P-224, P-256, P-384 и P-521, а также бинарных кривых NIST, установить не удалось. Вознаграждение за находку seed-значений — 36 864 доллара — Anthropic передаёт организации Internet Security Research Group. Работу вели John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini и Steve Weis, а код, воспроизводящий все seed-значения и часть базовых точек, опубликован прямо в посте.