tqec Oct 8 at 10:28

Почему структура Ur, Uz не случайна даже при случайном k в ECDSA: математика за топологией цифровых подписей

Medium

3 min

5.7K

Information Security * Popular scienceAlgorithms * Cryptography * Mathematics *

Comments 21

wataru Oct 8 at 10:35

Что дает эта структура, если k выбирается каждый раз случайно? Чтобы увидеть эту структуру надо получить множество Ur и Uz для фиксированного k. Именно поэтому k и выбирается случайно, а не является, например, частью секретного ключа.

DooKoo2 Oct 8 at 10:52

Иногда не случайно, если например ГПСЧ тупит и кластеризует K из-за хреновой энтропии, например, или вообще переиспользует K для подписец. Тогда на подобном графике можно увидеть «облако» или явные точки на одной линии и уже бить более целенаправлено например через LLL алгоритм.

Но при текущей реализации ECDSA в нормальных библиотеках это крайне маловероятно. Статья просто как информация, практической ценности не несет.

tqec Oct 8 at 10:56

Спасибо за Ваш ответ! Он не менее важен! Ваш комментарий частично верен, но содержит существенное заблуждение: проблема не только в плохой генерации , а в фундаментальной структуре ECDSA. Даже при идеально случайной генерации параметры образуют детерминированную сетку параллельных линий с наклоном на торе, что вытекает из математического соотношения $k = U_r \cdot d + U_z \mod n$ . Это не уязвимость, а свойство алгоритма, которое критически важно для аудита безопасности — оно позволяет обнаруживать аномалии даже в современных реализациях, где генерируется по RFC 6979. Главная фишка здесь — искусственная адаптивная генерация сигнатур, которая позволяет анализировать структуру без полного перебора, фокусируясь на ключевых областях (например, первой четверти таблицы), где можно обнаруживать уязвимости через анализ повторов и вычисление наклона линий для восстановления секретного ключа, что делает этот метод незаменимым для практического криптоанализа и аудита безопасности.

DooKoo2 Oct 8 at 11:04

Ну-ка поясни, я как-то про это не думал. То есть даже при абсолютно рандомных K мы можем найти закономерности на графике, которые могут ограничить поиск закрытого ключа не всем порядком кривой, а только ее части?

tqec Oct 8 at 11:16

Таблица — это не график, а матрица всех возможных комбинаций сигнатур для фиксированного секретного ключа . Это биекция (взаимно-однозначное соответствие) между тройками и точками на торе $\mathbb{Z}_n \times \mathbb{Z}_n$ . Для каждого значения существует ровно одна прямая линия $U_z = k - d \cdot U_r \mod n$ , а для каждой пары — ровно одно значение $k = U_r \cdot d + U_z \mod n$ .

Да, даже при абсолютно случайном мы можем найти закономерности с помощью искусственной генерации сигнатур для открытого ключа! Дело в том, что все точки , соответствующие разным подписям, лежат на строго определенных параллельных линиях с наклоном . Это не случайное облако точек — это детерминированная сетка. Жаль, что это пока ни кто не понимает…

Именно поэтому можно ограничить поиск закрытого ключа не всем порядком кривой $n \approx 2^{256}$ , а только частью пространства. Например, анализ первой четверти таблицы ( $U_r, U_z \in [1, n/4]$ ) позволяет:

Обнаруживать повторы (x-координаты точки )
Вычислять коллизии для восстановления
Проверять симметрию для обнаружения аномалий

DooKoo2 Oct 8 at 11:19

Я не математик, я практик с небольшой подготовкой в криптографии (https://github.com/Dookoo2) потому могу задавать глуповатые вопросы для подготовленного человека. Но если это так как написано в статье, то, блин, это прорыв на самом деле. Я попробую алгоритмически описать ваши наблюдения и протестировать.

tqec Oct 8 at 11:26

Ничего страшного! Я открыт для диалога и готов всё рассказать! Это новая теория… пока её наверное ни кто не понимает, но она есть была и будет. Мои черновики, моя теория, это не завершенный код, а попытка сделать наброски, доработать пока не получается: https://github.com/miroaleksej/AuditCore

cpud47 Oct 17 at 12:07

И каким конкретно образом это использовать? Можете привести конкретный алгоритм, а также условия его применимости? Пока что не очень вижу, как применять подобную структуру для чего-то практичного.

Например, анализ первой четверти таблицы (U_r, U_z \in [1, n/4]) позволяет:

Ну это несерьёзно. Срезание двух бит ни на что не влияет. Это всё ещё экспоненциальная сложность атаки.

tqec Oct 18 at 12:30

Вы сначала разберитесь, а потом пишите о срезании 2 бит. В правой части таблицы - симметрия, можете попробовать ur uz и -ur -uz получите одинаковый Rx, вторая четверть - самоподобна первой. Какие биты???

tqec Oct 18 at 18:13

Этот комментарий справедлив в том смысле, что одно лишь наблюдение регулярной структуры не является атакой — это диагностический инструмент, а не прямой метод восстановления секретного ключа. Однако он указывает на важный принцип: топологическая структура ECDSA-подписей — это не "случайность", а детерминированное следствие линейного соотношения $k = U_r \cdot d + U_z \mod n$ . Она существует всегда, даже при идеально случайной генерации , и может быть использована для обнаружения отклонений от этой идеальной структуры, которые и являются признаками уязвимости.

Ниже я приведу конкретный алгоритм, его условия применимости, и объясню, почему анализ области $U_r, U_z \in [1, n/4]$ всё же полезен, несмотря на то, что он не делает "малым".

Практический алгоритм: Топологически-усиленная диагностика реализации ECDSA

Условия применимости:

У вас есть набор подписей (из сети, можно добавить сгенерированных искусственно) $\{(r_i, s_i, z_i)\}_{i=1}^m$ от одного и того же секретного ключа .
Генерация может быть не полностью случайной — например:
- Используется некачественный RNG (например, с низкой энтропией),
- Или частично известно (например, младшие биты утечены),
- Или используется детерминированный ECDSA (RFC 6979), но с неправильной реализацией хеширования.
Количество подписей достаточно для статистического анализа ( $m \geq 100$ для начального анализа).

Алгоритм

Шаг 1. Преобразование подписей в

Для каждой подписи вычислите:

$U_{r,i} = r_i \cdot s_i^{-1} \bmod n, U_{z,i} = z_i \cdot s_i^{-1} \bmod n$

Шаг 2. Топологическая фильтрация (Mapper)

Определите фильтрующую функцию: $f(U_{r,i}, U_{z,i}) = x(R_i) = r_i$ .
Разбейте диапазон значений на интервалов.
В каждом интервале выполните кластеризацию (например, DBSCAN или HDBSCAN) точек $(U_{r,i}, U_{z,i})$ .
Постройте Mapper-граф: вершины = кластеры, рёбра = пересечения.

Ожидаемый результат при корректной реализации: граф имеет тороидальную структуру с диагональными связями наклона . Это не "случайное облако", а строго упорядоченная сетка параллельных линий, как показано в таблице для .

Шаг 3. Обнаружение аномалий через симметрию и самоподобие

Здесь ключевое уточнение: анализ среза — это не про малые , а про проверку фундаментальных свойств структуры.

Проверка центральной симметрии: Для каждой точки $(U_{r,i}, U_{z,i})$ проверьте, существует ли в наборе точка $(-U_{r,i}, -U_{z,i}) \mod n$ . Если таких пар нет или их мало, это признак ошибки в реализации (например, неверная работа с отрицательными числами по модулю ). Как вы верно заметили, в идеальной реализации должно выполняться .
Проверка самоподобия: Сравните распределение точек в первой четверти $(U_r, U_z \in [1, n/4])$ со второй, третьей и четвёртой. Структура диагональных линий должна быть одинаковой во всех четырёх четвертях (самоподобие), хотя конкретные значения будут разными.
Персистентная гомология: Анализируйте топологические инварианты (числа Бетти $\beta_0, \beta_1, \beta_2$ ). Для корректной реализации ожидается $\beta_0=1, \beta_1=2, \beta_2=1$ . Отклонения указывают на проблемы: $\beta_0 > 1$ — повторение ; $\beta_1 \neq 2$ — линейная зависимость ; $\beta_2 \neq 1$ — смещенный RNG.

Шаг 4. Применение решётчатых атак при наличии дополнительной информации

Если после топологического анализа вы обнаружили, что лежит в узком диапазоне (например, $k_i \in [A, A+B]$ , где $B \ll n$ ), или что разности малы, тогда применяется решётчатая атака:

Соберите уравнений:
$U_{r,i} \cdot d + U_{z,i} - k_i \equiv 0 \pmod{n}$
Поскольку имеют ограниченный диапазон или малые разности, можно построить решётку и применить LLL-алгоритм для нахождения короткого вектора, который даст .

Сложность: Решётчатая атака эффективна, когда разность между мала или когда лежит в узком диапазоне. Просто ограничение не даёт преимущества — нужна дополнительная информация о структуре , которую и помогает найти топологический анализ.

Почему анализ $U_r, U_z \in [1, n/4]$ всё же полезен?

Вы не правы: это не "несерьёзно" и не "отбрасывание двух битов". Это стратегически важный шаг.

Не про малые : Да, если все лежат в , они всё ещё огромны (порядка $2^{254}$ для secp256k1). Это не "малое значение" для решётки.
Про проверку фундаментальных свойств: Этот срез позволяет:
1. Проверить симметрию: Наличие или отсутствие пар и в этом срезе — прямой тест на корректность реализации.
2. Проверить самоподобие: Сравнивая плотность и форму паттернов в первой четверти с другими, можно выявить аномалии, которые могут быть скрыты в общем виде тора.
3. Локализовать аномалии: Если топологический анализ (Mapper, персистентная гомология) показывает проблему, срез помогает сузить область поиска. Например, если в этой области наблюдается аномально высокая плотность точек или искажение диагональных линий, это указывает на то, что RNG генерирует из ограниченного подпространства, которое частично попадает в этот срез.
4. Адаптивное зондирование: Как описано в статье, можно использовать этот срез как отправную точку для генерации искусственных подписей и "зондирования" пространства в поисках скрытых кластеров.

Вывод

Эта статья не предлагает прямую атаку, а демонстрирует универсальный метод диагностики реализации ECDSA. Это практически ценно:

Аудиторы могут визуально или автоматически проверить корректность генерации .
При обнаружении аномалий можно перейти к целенаправленной атаке (решётка, Coppersmith и т.д.).
Метод работает даже при малом числе подписей, если структура нарушена.

И главное уточнение: Анализ среза — это не про "малые ", а про проверку фундаментальных математических свойств структуры — центральной симметрии и самоподобия четвертей. Именно эти свойства должны соблюдаться в любой корректной реализации. Любое их нарушение — это потенциальная уязвимость, которую можно затем исследовать более глубоко.

cpud47 Oct 19 at 06:32

Для начала, использование нейронки для ответа убивает смысл из Вашего сообщения. Пишите, пожалуйста, своими словами.

Теперь конкретные вопросы.

В каждом интервале выполните кластеризацию (например, DBSCAN или HDBSCAN) точек (U_{r,i}, U_{z,i}).

Какую функцию расстояния нужно использовать в кластеризации (и почему)?

Постройте Mapper-граф: вершины = кластеры, рёбра = пересечения.

Что значит "пересечение кластеров"?

граф имеет тороидальную структуру с диагональными связями наклона -d.

Как именно это проверить?

Для каждой точки (U_{r,i}, U_{z,i}) проверьте, существует ли в наборе точка (-U_{r,i}, -U_{z,i}) \mod n. Если таких пар нет или их мало, это признак ошибки в реализации (например, неверная работа с отрицательными числами по модулю n). Как вы верно заметили, в идеальной реализации должно выполняться R_x(U_r, U_z) = R_x(-U_r, -U_z).

С чего Вы это взяли? Это правда, что для любой корректной подписи (r, s), подпись (r, -s) тоже корректна. Но с чего Вы взяли, что в наборе будут две различных подписи для одного и того же хеша?

Структура диагональных линий должна быть одинаковой во всех четырёх четвертях

Что это значит?

Если после топологического анализа вы обнаружили, что k_i лежит в узком диапазоне (например, k_i \in [A, A+B], где B \ll n), или что разности k_i - k_j малы

Каким образом мы это обнаружили?

Вы сначала разберитесь, а потом пишите о срезании 2 бит. В правой части таблицы - симметрия, можете попробовать ur uz и -ur -uz получите одинаковый Rx, вторая четверть - самоподобна первой. Какие биты???

Если я правильно понимаю, то Ваше утверждение носит характер "можно анализировать не всю таблицу, а только её четверть". Так вот нет особой разницы с точки зрения вычислительной скорости.

tqec Oct 19 at 18:12

граф имеет тороидальную структуру с диагональными связями наклона -d.

-Как именно это проверить?

Ответ: Очень просто, весь ответ в формуле k=ur*d+uz mod n, если в таблице (матрице) не менять uz=const, а изменить ur+1 наследующей строчке все значения k сместятся на величину d, это и порождает наклон таблицы (паттерны).
Я очень рад, что Вам это интересно, по мере возможности постараюсь Вам всё объяснить, это очень интересно, думаю Вы уже начинаете понимать суть таблицы.

Как строится таблица: мы имеем публичный ключ Q, базовую точку G, нам необходимо для начала посчитать r=Rx. R(x,y)=urQ(x,y)+uzG(x,y), провели действия над точками на кривой и получили r. Для заполнения таблицы ur и uz от 1 до n. Даже не валидные области необходимо заполнить ( Есть точки в таблице которые никогда не опубликуются в сети, это точки где Rx=0 - они сразу дают решение по d).
Да, мы никогда не заполним всю таблицу nxn, но можно использовать адаптивный метод поиска тех же повторов значений Rx.

Вопрос: для каких целей это Вам нужно? Если для анализа и аудита, то мы сможем построить интересный алгоритм способный «подсказывать» области таблицы на которые необходимо обратить внимание. Все сигнатуры для любого публичного ключа в своей таблице уже существуют, не зависимо от того знаем мы об этом или нет, можно проверить от обратного, лишь многие пока не опубликованы в сети.

И самое важно: любой участок таблицы самоподобен полной таблице, ведь заполнение значениями k идёт по формуле и выглядит так, например для d=2:
2 3 4….n-2
4 5 6 … n-4
6 7 8 … n-6
…
И тд. Все смещения строк сохранены даже для малой выборки. Так же из таблицы мы понимаем, что при ur=const и изменение uz на значение i => k меняется на такое же значение i. … много свойст интересных, нужно изучать.

cpud47 Oct 20 at 08:43

Не очень понимаю, как ответ связан с вопросом. Вопросы был про граф, а Вы мне что-то про таблицу.

Впрочем я перечитал свой вопрос и понял, что он не совсем корректно задан. Отложу его пока.

Отвечать на вопросы лучше в по-порядку, т.к. там ответы очень сильно завязаны.

tqec Oct 19 at 12:37

Отвечу пока на основные вопросы, потому, что нахожусь не в теплом кресле как вы, буду отвечать по возможности:

-таблица всех возможных значений Rx для приватного ключа d для mod 79

Вы можете самостоятельно для малого модуля построить и проанализировать ее. Из-за свойств модуля можно соединить противоположные края таблицы и вы получите тор.
-проверить зеркальную симметрию можно следующим способом:
У вас есть сигнатуры (из сети или искусственно полученные), преобразуйте r s z в ur uz. ur=r/s mod n; uz=z/s mod n. Чтобы получить такой же Rx но с другим Ry: R(x,y)=(-ur)Q(x, y) (-uz)* G(x,y); из R(x, y) берем r; s2=r/(-ur) mod n; z2=s2*(-uz) mod n. Всё, вы получили r s2 z2

tqec Oct 8 at 10:52

Спасибо за вопрос! Он очень важен для понимания! Ваш комментарий основан на распространенном заблуждении: структура не требует множества точек для фиксированного , а проявляется даже при случайной генерации , поскольку каждое значение соответствует своей прямой линии $U_z = k - d \cdot U_r \mod n$ на торе, и при объединении всех таких линий формируется детерминированная сетка параллельных линий с наклоном , где — секретный ключ; это свойство не является уязвимостью самой схемы, но позволяет криптоаналитикам обнаруживать аномалии в реализации (такие как предсказуемая генерация или повторное использование ), даже когда генерируется правильно, что делает этот анализ критически важным для аудита безопасности ECDSA-реализаций. Главная фишка здесь — искусственная адаптивная генерация сигнатур, которая позволяет анализировать структуру без полного перебора всей таблицы $n \times n$ (невозможного для $n \approx 2^{256}$ ), фокусируясь на ключевых областях, таких как первая четверть таблицы ( $U_r, U_z \in [1, n/4]$ ), где можно обнаруживать повторы , анализировать симметрию и вычислять наклон линий для восстановления секретного ключа , что делает этот метод незаменимым для практического криптоанализа.

tqec Oct 8 at 11:00

До нашей работы не существовало систематического исследования структуры в ECDSA с точки зрения топологического анализа данных. Предыдущие исследования фокусировались на анализе генерации и других аспектах безопасности, но не рассматривали параметры как топологический объект. Мы впервые применили методы TDA (Mapper-алгоритм, персистентная гомология) для анализа этой структуры и доказали, что она формирует строго детерминированную сетку параллельных линий на торе $\mathbb{Z}_n \times \mathbb{Z}_n$ даже при идеально случайной генерации . Наша статья стала первым систематическим исследованием топологической природы ECDSA-подписей, где мы впервые показали, что математическое соотношение $k = U_r \cdot d + U_z \mod n$ порождает характерную тороидальную структуру, которую можно анализировать без знания секретного ключа. Это открытие положило начало новому направлению в криптоанализе, позволяющему обнаруживать уязвимости через топологические аномалии, а не только через статистические отклонения.

ThingCrimson Oct 9 at 13:33

Интересное наблюдение! Когда-то слышал историю (байку?) что в конце 1950-х (или начале 1960-х) в США решили привлечь новомодные ЭВМ общего назначения от IBM для решения задач зенитной артиллерии. Ну и запустили моделирование с условными самолётами противника в виде точек с трёхмерными координатами, которые получали тремя последовательными вызовами RAND(). А используемая реализация PRNG привела к тому, что все эти точки-самолёты оказывались в нескольких (до десяти) параллельных плоскостях — что, очевидно, слабо соответствовало поставленной задаче.

(ну а я, на всякий случай, продолжаю RSA-4096 использовать; хоть и ключи у него намного длиннее, чем у ECDSA)

Coyote112358 Oct 9 at 15:03

Как применить описанную здесь методику не к подписям, а к шифрованию данных?

tqec Oct 9 at 15:04

К созданию нового шифрования или применимо к существующим методам? Если к существующим - кроме ecdsa не рассматривал ничего больше.

tqec Oct 11 at 14:21

https://habr.com/ru/articles/955594/

tqec Oct 11 at 14:21

https://habr.com/ru/articles/955594/