Почему надёжная кривая не защищает слабый ключ

Почему надёжная кривая не защищает слабый ключ Секретный ключ, равный 4, можно раскрыть и на эллиптической кривой с примерно 2^384 точками. История с сертификатами eMudrha показывает, почему происхождение параметров, трудность математической задачи и выбор секрета требуют отдельных проверок. Кривые Национального института стандартов и технологий США (NIST) оказались в центре двух новостей. Сначала исследователи Anthropic восстановили происхождение исходных значений, из которых получали параметры кривых. Затем обнаружились сертификаты eMudrha с чрезвычайно малыми секретными ключами. Исходные значения предоставило Агентство национальной безопасности США (NSA), но точная процедура их получения долго оставалась неизвестной. Подозрения усиливала реальная закладка агентства в другом продукте, генераторе псевдослучайных чисел. Сама по себе она не доказывала наличия закладки в кривых. Как описано в истории реконструкции, разработчик вспоминал хеширование юмористической английской фразы, но забыл подробности. Восстановленная процедура использовала дату. Это сняло конкретное подозрение в злонамеренном происхождении параметров, но не доказывает отсутствия любых возможных уязвимостей. Вторая новость касается применения кривой P-384. Её точки удовлетворяют уравнению y² = x³ − 3x + b (mod p), p = 2^384 − 2^128 − 2^96 + 2^32 − 1. Здесь b задаёт фиксированный коэффициент, а координаты вычисляются по простому модулю p. Точек примерно 2^384. При этом классическая стойкость P-384 оценивается в 192 бита. Размер поля и криптографическая стойкость не совпадают. Обозначим базовую точку через G, секретное целое число через e, открытый ключ через Q. Тогда Q = eG. Умножение здесь означает сложение точки G с собой e раз по правилам группы точек кривой. В степенной записи это та же групповая операция, а не обычное возведение чисел в степень. По известному e вычислить Q практически выполнимо. Восстановление e по G и Q называется задачей дискретного логарифмирования. Её предполагаемая вычислительная трудность при корректном выборе ключа лежит в основе защиты. У eMudrha использовались секреты 4, 56, 115, 155, 156, 230 и 237. Проверяем G, 2G, 3G, 4G и сравниваем с открытым ключом. Совпадение Q = 4G раскрывает секрет на четвёртой проверке. Все перечисленные значения находятся среди первых 237 положительных кандидатов. Такой перебор не решает эффективно общую задачу дискретного логарифмирования, но справляется с этими ключами. Прозрачное происхождение кривой не исправляет неудачный выбор секрета. Для раскрытия перечисленных ключей достаточно обычных вычислений. Если появятся криптографически значимые квантовые компьютеры, они позволят решать саму задачу дискретного логарифмирования и подорвут математическую основу этой защиты. Это отдельная угроза, не причина описанной компрометации. Наши каналы MAX · Telegram · Дзен #Криптография #ЭллиптическиеКривые #ТеорияЧисел #Безопасность