Claude восстановил вероятное происхождение семян пяти кривых NIST

Чтобы проверить цифровую подпись на эллиптических кривых, сторонам нужны общие математические параметры. Пять стандартизованных кривых NIST – P-192, P-224, P-256, P-384 и P-521 – связаны с опубликованными исходными значениями, или «семенами»: из них по заданной процедуре можно проверить получение параметров. Загадка заключалась в более раннем шаге. Было известно, какие семена указаны в стандарте, но не было ясного объяснения, почему выбрали именно эти числа.

Долгое время поиски шли в том числе вокруг воспоминания одного из участников разработки: исходные числа могли быть связаны с хешированием шуточной фразы о повышении зарплаты и добавленным счётчиком. По описанию Anthropic, при постановке задачи её внутренней исследовательской модели эту подсказку не передали. Claude проверил другой путь: могли ли семена оказаться выходом генератора псевдослучайных чисел, применявшегося в программах 1990-х годов. Такой генератор выдаёт числа, которые выглядят случайными, но следуют определённым правилам.

Модель написала программу для проверки битовых последовательностей и перебрала 34 сочетания генераторов и способов извлечения выходных данных. В четырёх наборах семян она обнаружила характерный признак: если представить данные последовательностью 32-битных чисел, старший бит у 20 таких чисел равен нулю. Это согласуется с устройством lrand48, который выдаёт 31-битный результат. Затем с помощью метода восстановления скрытого состояния генератора, основанного на сокращении решётки LLL, исследователи продвинулись от опубликованных семян к возможным начальным значениям.

Следующий шаг связал числа со временем. Функция srand48 задаёт начальное состояние генератора; восстановленные значения соответствовали временным меткам Unix в диапазоне с мая 1997 года по апрель 1998 года. Для P-256 приводится воспроизводимый пример: при инициализации временем 16 августа 1997 года, 01:52:34 UTC, нужное семя получается из 1842-го набора кандидатов. Для остальных четырёх кривых также удалось найти соответствия. По данным Anthropic, поиск занял у Claude менее получаса, а организатор ранее объявленной награды независимо проверил результат.

Объяснение происхождения пяти семян не восстанавливает всю процедуру выбора кривых. Исследователи пока не знают, почему при подборе были пропущены некоторые, на вид подходящие, кандидаты; также не объяснены семя B-163 и получение части базовых точек кривых. Найденная связь с lrand48 делает версию о намеренно подобранных именно этих семенах менее вероятной, но сама по себе не служит доказательством отсутствия любых уязвимостей в криптографических стандартах.