Comments 14
Что дает эта структура, если k выбирается каждый раз случайно? Чтобы увидеть эту структуру надо получить множество Ur и Uz для фиксированного k. Именно поэтому k и выбирается случайно, а не является, например, частью секретного ключа.
Иногда не случайно, если например ГПСЧ тупит и кластеризует K из-за хреновой энтропии, например, или вообще переиспользует K для подписец. Тогда на подобном графике можно увидеть «облако» или явные точки на одной линии и уже бить более целенаправлено например через LLL алгоритм.
Но при текущей реализации ECDSA в нормальных библиотеках это крайне маловероятно. Статья просто как информация, практической ценности не несет.
Спасибо за Ваш ответ! Он не менее важен! Ваш комментарий частично верен, но содержит существенное заблуждение: проблема не только в плохой генерации 
, а в фундаментальной структуре ECDSA. Даже при идеально случайной генерации параметры 
образуют детерминированную сетку параллельных линий с наклоном 
на торе, что вытекает из математического соотношения 
. Это не уязвимость, а свойство алгоритма, которое критически важно для аудита безопасности — оно позволяет обнаруживать аномалии даже в современных реализациях, где генерируется по RFC 6979. Главная фишка здесь — искусственная адаптивная генерация сигнатур, которая позволяет анализировать структуру без полного перебора, фокусируясь на ключевых областях (например, первой четверти таблицы), где можно обнаруживать уязвимости через анализ повторов 
и вычисление наклона линий для восстановления секретного ключа, что делает этот метод незаменимым для практического криптоанализа и аудита безопасности.
Ну-ка поясни, я как-то про это не думал. То есть даже при абсолютно рандомных K мы можем найти закономерности на графике, которые могут ограничить поиск закрытого ключа не всем порядком кривой, а только ее части?
Таблица — это не график, а матрица всех возможных комбинаций сигнатур для фиксированного секретного ключа 
. Это биекция (взаимно-однозначное соответствие) между тройками 
и точками на торе 
. Для каждого значения существует ровно одна прямая линия 
, а для каждой пары — ровно одно значение .
Да, даже при абсолютно случайном мы можем найти закономерности с помощью искусственной генерации сигнатур для открытого ключа! Дело в том, что все точки , соответствующие разным подписям, лежат на строго определенных параллельных линиях с наклоном . Это не случайное облако точек — это детерминированная сетка. Жаль, что это пока ни кто не понимает…
Именно поэтому можно ограничить поиск закрытого ключа не всем порядком кривой 
, а только частью пространства. Например, анализ первой четверти таблицы (![U_r, U_z \in [1, n/4]](https://habrastorage.org/getpro/habr/formulas/6/6b/6b5/6b5dedb5bd15ae885fa0c4b7439925f3.svg)
) позволяет:
Обнаруживать повторы
(x-координаты точки 
)Вычислять коллизии для восстановления
Проверять симметрию для обнаружения аномалий
Я не математик, я практик с небольшой подготовкой в криптографии (https://github.com/Dookoo2) потому могу задавать глуповатые вопросы для подготовленного человека. Но если это так как написано в статье, то, блин, это прорыв на самом деле. Я попробую алгоритмически описать ваши наблюдения и протестировать.
Ничего страшного! Я открыт для диалога и готов всё рассказать! Это новая теория… пока её наверное ни кто не понимает, но она есть была и будет. Мои черновики, моя теория, это не завершенный код, а попытка сделать наброски, доработать пока не получается: https://github.com/miroaleksej/AuditCore
Спасибо за вопрос! Он очень важен для понимания! Ваш комментарий основан на распространенном заблуждении: структура не требует множества точек для фиксированного , а проявляется даже при случайной генерации , поскольку каждое значение соответствует своей прямой линии на торе, и при объединении всех таких линий формируется детерминированная сетка параллельных линий с наклоном , где — секретный ключ; это свойство не является уязвимостью самой схемы, но позволяет криптоаналитикам обнаруживать аномалии в реализации (такие как предсказуемая генерация или повторное использование ), даже когда генерируется правильно, что делает этот анализ критически важным для аудита безопасности ECDSA-реализаций. Главная фишка здесь — искусственная адаптивная генерация сигнатур, которая позволяет анализировать структуру без полного перебора всей таблицы 
(невозможного для ), фокусируясь на ключевых областях, таких как первая четверть таблицы (), где можно обнаруживать повторы , анализировать симметрию и вычислять наклон линий для восстановления секретного ключа , что делает этот метод незаменимым для практического криптоанализа.
До нашей работы не существовало систематического исследования структуры в ECDSA с точки зрения топологического анализа данных. Предыдущие исследования фокусировались на анализе генерации и других аспектах безопасности, но не рассматривали параметры как топологический объект. Мы впервые применили методы TDA (Mapper-алгоритм, персистентная гомология) для анализа этой структуры и доказали, что она формирует строго детерминированную сетку параллельных линий на торе даже при идеально случайной генерации . Наша статья стала первым систематическим исследованием топологической природы ECDSA-подписей, где мы впервые показали, что математическое соотношение порождает характерную тороидальную структуру, которую можно анализировать без знания секретного ключа. Это открытие положило начало новому направлению в криптоанализе, позволяющему обнаруживать уязвимости через топологические аномалии, а не только через статистические отклонения.
Интересное наблюдение! Когда-то слышал историю (байку?) что в конце 1950-х (или начале 1960-х) в США решили привлечь новомодные ЭВМ общего назначения от IBM для решения задач зенитной артиллерии. Ну и запустили моделирование с условными самолётами противника в виде точек с трёхмерными координатами, которые получали тремя последовательными вызовами RAND(). А используемая реализация PRNG привела к тому, что все эти точки-самолёты оказывались в нескольких (до десяти) параллельных плоскостях — что, очевидно, слабо соответствовало поставленной задаче.
(ну а я, на всякий случай, продолжаю RSA-4096 использовать; хоть и ключи у него намного длиннее, чем у ECDSA)
Как применить описанную здесь методику не к подписям, а к шифрованию данных?
Почему структура Ur, Uz не случайна даже при случайном k в ECDSA: математика за топологией цифровых подписей