Файл: Разработка программного обеспечения алгоритма Диффи Хелмана на основе эллиптических кривых.docx

С первого взгляда логика алгоритма может быть неочевидной, однако если объединить все ранее записанные нами уравнения, всё становится понятнее.

Начнём с

. Из определения открытого ключа мы знаем, что

(где

— закрытый ключ). Можно записать:

С учётом определений

можно записать:

Здесь мы опустили "

", как для краткости, так и потому, что циклическая подгруппа, сгенерированная точкой

, имеет порядок

, то есть часть "

" избыточна.

Ранее мы определили

. Умножив обе части уравнения уравнения на

и поделив на

, мы получаем:

. Подставляя этот результат в наше уравнение для

, получаем:

Это то же самое уравнение , которое было у нас на шаге 2 алгоритма генерирования подписи! При генерировании подписей и при их проверке мы вычисляем одну и ту же точку

, просто разными наборами уравнений. Именно поэтому алгоритм работает.

Экспериментируем с ECDSA

Разумеется, я написал скрипт на Python для генерирования и проверки подписей. Код копирует некоторые части из скрипта ECDH, в частности, параметры области определения и алгоритм генерирования пары закрытого/открытого ключей.

Вот какие выходные данные создаются этим скриптом:

Curve: secp256k1

Private key: 0x9f4c9eb899bd86e0e83ecca659602a15b2edb648e2ae4ee4a256b17bb29a1a1e

Public key: (0xabd9791437093d377ca25ea974ddc099eafa3d97c7250d2ea32af6a1556f92a, 0x3fe60f6150b6d87ae8d64b78199b13f26977407c801f233288c97ddc4acca326)
Message: b'Hello!'

Signature: (0xddcb8b5abfe46902f2ac54ab9cd5cf205e359c03fdf66ead1130826f79d45478, 0x551a5b2cd8465db43254df998ba577cb28e1ee73c5530430395e4fba96610151)

Verification: signature matches
Message: b'Hi there!'

Verification: invalid signature
Message: b'Hello!'

Public key: (0xc40572bb38dec72b82b3efb1efc8552588b8774149a32e546fb703021cf3b78a, 0x8c6e5c5a9c1ea4cad778072fe955ed1c6a2a92f516f02cab57e0ba7d0765f8bb)

Verification: invalid signature

Как видите, скрипт сначала подписывает сообщение (байтовую строку «Hello!»), а затем проверяет подпись. После чего он пробует проверить ту же подпись для другого сообщения («Hi there!») и проверка не удаётся. Наконец, он пробуем проверить проверить подпись для правильного сообщения, но с другим случайным открытым ключом, после чего проверка тоже не удаётся.

Важность k

При генерировании подписей ECDSA важно хранить секретный

по-настоящему в тайне. Если бы мы использовали одну

для всех подписей или генератор случайных чисел оказался бы в какой-нибудь степени предсказуемым, то атакующий смог бы определить закрытый ключ!

Подобную ошибку сделала Sony несколько лет назад. На игровой консоли PlayStation 3 можно было запускать игры, только подписанные Sony алгоритмом ECDSA. То есть, если бы я хотел создать новую игру для PlayStation 3, я не смог бы распространять её среди пользователей без подписи Sony. Проблема заключалась в том, что все созданные Sony подписи были сгенерированы с помощью статичного

.

(Похоже, создатели генератора случайных чисел Sony вдохновлялись или XKCD, или Дилбертом.)

В такой ситуации можно запросто восстановить закрытый ключ

Sony, купив всего две подписанные игры, после чего извлечь их хеши (

) и подписи (

) вместе с параметрами области определения. Это делается так:

Сначала нужно учесть, что (потому что и одинаковы для обеих подписей).
Принять, что (этот результат следует непосредственно из уравнения для ).
Умножить обе части уравнения на : .
Разделить на , чтобы получить .

Последнее уравнение позволяет нам вычислить

с помощью всего двух хешей и соответствующих им подписей. Теперь с помощью уравнения для

мы можем получить закрытый ключ:

Похожие техники можно применить, если

не статично, но каким-то образом предсказуемо.

Часть 4: алгоритмы для взлома защиты ECC и сравнение с RSA

В предыдущей части мы рассмотрели два алгоритма (ECDH and ECDSA) и разобрались, почему задача дискретного логарифмирования для эллиптических кривых играет важную роль для их безопасности. Но, если вы помните, мы сказали, что математических доказательств сложности задачи дискретного логарифмирования нет: мы полагаем, что она «сложна», но не уверены в этом. В первой части статьи мы попробовали оценить, насколько «сложна» она на практике в условиях современных технологий.

Во второй части мы попытались ответить на вопрос: зачем нам нужна криптография на эллиптических кривых, если RSA (и другие криптосистемы, основанные на модулярной арифметике) хорошо работают?

Взлом задачи дискретного логарифмирования

Теперь мы рассмотрим два наиболее эффективных алгоритма вычисления дискретных алгоритмов на эллиптической кривой: алгоритм «baby-step, giant-step» и ρ-алгоритм Полларда.

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

и порядком

Baby-step, giant-step

Для начала приведу простое рассуждение: мы всегда можем записать любое целое

как

, где

— три произвольных целых. Например, можно записать

С учётом этого можно переписать уравнение задачи дискретного логарифмирования следующим образом:

Baby-step giant-step — это алгоритм «встречи посередине». В отличие от атаки перебором (при которой придётся вычислять все точки

для каждого

, пока мы не найдём

), можно вычислять «несколько» значений для

и «несколько» значений для

, пока мы не найдём соответствие. Алгоритм работает следующим образом:

Вычисляем
Для каждого из вычисляем и сохраняем результаты в хеш-таблицу.
Для каждого из :
1. вычисляем ;
2. вычисляем ;
3. проверяем хеш-таблицу и ищем точку , такую, что ;
4. если такая точка существует, то мы нашли .