Файл: Разработка программного обеспечения алгоритма Диффи Хелмана на основе эллиптических кривых.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 22.11.2023
Просмотров: 286
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Часть 1: эллиптические кривые над вещественными числами и групповой закон
Групповой закон для эллиптических кривых
Часть 2: эллиптические кривые над конечными полями и задача дискретного логарифмирования
Порядок группы эллиптической кривой
Скалярное умножение и циклические подгруппы
Криптография на эллиптических кривых
Часть 4: алгоритмы для взлома защиты ECC и сравнение с RSA
Взлом задачи дискретного логарифмирования
В сущности, мы берём псевдослучайную последовательность пар
вместе с соответствующей последовательностью точек . Последовательность пар может быть или не быть циклической, но последовательность точек точно циклическая, потому что и сгенерированы из одной базовой точки, а из свойство подгрупп мы знаем, что не можем «сбежать» из подгруппы только скалярным умножением и сложением.Теперь мы берём двух животных, черепаху и зайца, и заставляем обходить последовательность слева направо. Черепаха (зелёная точка на изображении) медленная и считывает каждую точку, одну за другой; заяц (красная точка) быстр и пропускает точку на каждом шаге.
Через какое-то время черепаха и заяц найдут одну точку, но с разными парами коэффициентов. Или, если выразить это уравнениями, черепаха найдёт пару
, а заяц — пару , такие, что .Если случайная последовательность определяется через алгоритм (а не хранится статически), легко увидеть, что принцип работы требует всего
пространства. Вычисление сложности асимптотического времени не так просто, но мы можем построить вероятностное доказательство, показывающее, что временная сложность равна ), как мы уже говорили.Экспериментируем с ρ Полларда
Я создал скрипт на Python, вычисляющий дискретные логарифмы с помощью ρ-алгоритма Полларда. Это не реализация исходного ρ Полларда, а небольшая его вариация (я использовал более эффективный способ генерирования псевдослучайной последовательности пар). В скрипте есть полезные комментарии, так что прочитайте его, если вам интересны подробности алгоритма.
Этот скрипт, как и baby-step giant-step, работает для маленьких кривых и создаёт те же выходные данные.
Ро Полларда на практике
Мы говорили, что baby-step giant-step невозможно использовать на практике из-за огромных требований к памяти. С другой стороны, ро-алгоритм Полларда требует очень мало памяти. Насколько же он практичен?
В 1998 году Certicom начала соревнование по вычислению дискретных логарифмов на эллиптических кривых с битовой длиной от 109 до 369. На сегодняшний день успешно взломаны только кривые длиной 109 бит. Последняя успешная попытка была совершена в 2004 году. Процитируем Википедию:
Награда была вручена 8 апреля 2004 года примерно 2600 людям, которых представлял Крис Монико. Они тоже использовали разновидность распараллеленного ро-алгоритма Полларда, вычисления по которому заняли 17 месяцев календарного времени.
Как мы уже сказали, prime192v1 — это одна из «наименьших» эллиптических кривых. Мы также сказали, что ρ Полларда имеет временную сложность
. Если бы мы использовали ту же технику, что и Крис Монико (тот же алгоритм, то же оборудование и количество машин), сколько бы заняло вычисление логарифма для prime192v1? Полученный результат говорит сам за себя и даёт чётко понять, насколько сложно взломать дискретный логарифм с помощью таких техник.
Сравниние ρ Полларда и Baby-step giant-step
Я решил объединить скрипт baby-step giant-step, скрипт ро Полларда и скрипт перебора в четвёртый скрипт для сравнения их производительности.
Этот четвёртый скрипт вычисляет все логарифмы для всех точек на «маленькой» кривой с помощью разных алгоритмов и сообщает, сколько времени это заняло:
Curve order: 10331
Using bruteforce
Computing all logarithms: 100.00% done
Took 2m 31s (5193 steps on average)
Using babygiantstep
Computing all logarithms: 100.00% done
Took 0m 6s (152 steps on average)
Using pollardsrho
Computing all logarithms: 100.00% done
Took 0m 21s (138 steps on average)
Как и можно ожидать, метод перебора чудовищно медленный по сравнению с двумя другими. Baby-step giant-step быстрее, а ро-алгоритм Полларда больше чем в три раза медленнее baby-step giant-step (хоть он и использует гораздо меньше памяти и меньшее количество шагов в среднем).
Посмотрите ещё и на количество шагов: для вычисления каждого логарифма способом перебора в среднем потребовалось 5193 шагов. 5193 очень близко к 10331 / 2 (половина порядка кривой). Baby-step giant-steps и ро Полларда использовали 152 шага и 138 шагов соответственно. Эти два числа очень близки к квадратному корню 10331 (101,64).
Дальнейшие рассуждения
В обсуждении этих алгоритмов я использовал много чисел. При их чтении важно быть внимательным: алгоритмы во многих аспектах можно сильно оптимизировать. Оборудование может улучшаться. Можно создать специализированное оборудование.
Если сегодня подход кажется непрактичным, это не значит, что его нельзя улучшить. Это также не значит, что нет других, более хороших подходов (не забывайте, что у нас нет доказательств сложности задачи дискретного логарифмирования).