Четверть века криптографы задавались вопросом, не подстроило ли АНБ втайне числа, лежащие в основе набора широко используемых эллиптических кривых. Как выяснилось, разгадкой может оказаться генератор псевдослучайных чисел из старой библиотеки C, на который модель ИИ вышла меньше чем за полчаса. Никто и не обещал, что объяснение будет эффектным.
Кратко о загадке
В 2000 году Национальный институт стандартов и технологий США (NIST) утвердил набор эллиптических кривых, предложенный АНБ. Эти кривые используются в криптографии с открытым ключом: они позволяют доказать, что у вас есть секретный ключ, не раскрывая его. Полезно и ничем не примечательно — пока не задашься вопросом, откуда взялись параметры кривых.
Агентство так и не объяснило происхождение некоторых чисел, использованных при построении кривых. Это молчание вызывало очевидное подозрение: возможно, АНБ перебрало множество вариантов и выбрало тот, который давал ему способ обойти защиту. Раскрытые Эдвардом Сноуденом сведения о попытках ослабить криптографические стандарты ничуть не развеяли этих подозрений.
В криптографии константу с необъяснённым происхождением редко считают милой причудой.
Длинный список тех, кто пытался найти ответ
Загадка привлекла внимание именитых исследователей. Криптографы Нил Коблиц и Альфред Менезес изложили её историю в статье 2015 года под названием «Загадка, окутанная тайной». Для Менезеса это был ещё и личный вопрос. Он участвовал в подготовке исходного стандарта и вспоминал, что в 1997 году получил начальные значения от математика АНБ Джерри Солинаса.
Исследователь безопасности Стив Вайс годами искал объяснение, в том числе направляя запросы на доступ к государственным документам. В 2023 году инженер-криптограф Филиппо Вальсорда и другие участники сообщества учредили награду за разгадку. Базовая сумма составляла 12 288 долларов. Если победитель передавал деньги на благотворительность, она могла вырасти до 36 864 долларов.
Итак: десятилетия пристального внимания, официальные запросы, научная статья и денежная награда. В итоге дело с мёртвой точки сдвинула языковая модель.
Что именно сделал Claude
Сотрудник Anthropic поручил внутренней модели Claude самостоятельно исследовать происхождение этих чисел. Здесь важна одна деталь. Модели не рассказали о гипотезе, согласно которой начальные значения могли быть получены из какой-то забытой фразы. Ей пришлось самой искать подход к задаче.
И она его нашла. Модель восстановила последовательность чисел с помощью lrand48 — генератора псевдослучайных чисел из старой библиотеки языка C. Такие генераторы работают по фиксированному алгоритму, поэтому при одинаковых начальных параметрах каждый раз выдают один и тот же результат. Именно эта воспроизводимость и делает весь фокус возможным.
Модель связала пять начальных значений с этим генератором менее чем за 30 минут. Для одного из них, использованного при построении кривой P-256, точное совпадение нашлось на 1842-м проверенном варианте. Временные метки 1997 и 1998 годов помогли соотнести последовательность с историческими данными.
Что по-прежнему не объяснено
История ещё не завершена, и в отчёте об этом сказано прямо. Остаётся неясным, почему программа пропускала некоторые подходящие варианты. Неясно и то, как выбирались остальные параметры кривых.
Итак, для происхождения начальных значений теперь есть правдоподобное и воспроизводимое объяснение. А вот весь процесс принятия решений, связанных с ними, пока не объяснён.
Что это значит для тех, кто использует эти кривые
Это открытие снижает вероятность того, что в кривых NIST есть намеренно встроенный механизм обхода защиты. Начальное значение, полученное обычным воспроизводимым генератором, куда меньше похоже на иголку, специально выбранную из стога возможных вариантов. И всё же перечисленные выше открытые вопросы не позволяют считать это полным оправданием.
Ещё два момента помогают не переоценивать значение новости:
- Никакого секретного ключа не обнаружено. Опубликованные начальные значения всегда были доступны. Выяснение того, как они были получены, не раскрывает никакого скрытого ключа АНБ и само по себе не ставит под угрозу ни одну систему.
- Ничего предпринимать не нужно. Anthropic заявила, что пользователям этих кривых не требуется менять настройки или переходить на другие алгоритмы.
Ещё одно уточнение для тех, кто интересуется криптовалютами. Кривая secp256k1, которую использует Bitcoin, к этой истории отношения не имеет. Её параметры получены другим способом, и эта загадка к ней не относится.
Куда пойдут деньги
Награду направят в Internet Security Research Group — некоммерческую организацию, которая поддерживает Let's Encrypt, проект по выпуску бесплатных сертификатов безопасности для сайтов. Удачная развязка для награды, которая начиналась со ставки на то, не затеяло ли АНБ чего-то подозрительного.
Главный вывод
Самое интересное здесь, возможно, не итог, а метод. Человек поставил перед моделью открытый вопрос, не рассказал ей о популярной гипотезе, и модель пришла к ответу, который люди искали 25 лет. Скептики вполне обоснованно захотят получить ответы на оставшиеся вопросы, и в отчёте прямо сказано: пока этих ответов нет.
И всё же наиболее вероятное объяснение великой загадки АНБ — функция стандартной библиотеки, которую любой мог вызвать ещё в 1997 году. Теории заговора обычно увлекательнее того, что послужило для них поводом.