Файл: Разработка программного обеспечения алгоритма Диффи Хелмана на основе эллиптических кривых.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 22.11.2023
Просмотров: 273
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Часть 1: эллиптические кривые над вещественными числами и групповой закон
Групповой закон для эллиптических кривых
Часть 2: эллиптические кривые над конечными полями и задача дискретного логарифмирования
Порядок группы эллиптической кривой
Скалярное умножение и циклические подгруппы
Криптография на эллиптических кривых
Часть 4: алгоритмы для взлома защиты ECC и сравнение с RSA
Взлом задачи дискретного логарифмирования
Что даёт нам
. Верно!Хотя процедура получения результатов очень утомительна, наши уравнения довольно кратки. Всё это благодаря обычной формулировке Вейерштрасса: без неё эти уравнения были бы очень длинными и сложными!
Скалярное умножение
Кроме сложения, мы можем определить и другую операцию: скалярное умножение, то есть:
где
— натуральное число. Я написал визуальный инструмент и для скалярного умножения, так что можете поэкспериментировать с ним.При записи в такой форме очевидно, что вычисление
требует сложений. Если состоит из десятичных разрядов, то алгоритм будет иметь сложность , что не очень хорошо. Но существуют и более быстрые алгоритмы.Один из них — алгоритм удвоения-сложения. Принцип его работы проще объяснить на примере. Возьмём
. В двоичном форме оно имеет вид . Такую двоичную форму можно представить как сумму степеней двойки: (Мы взяли каждый двоичный разряд
и умножили на степень двойки.)С учётом этого можно записать:
Алгоритм удвоения-сложения задаёт следующий порядок действий:
-
Взять . -
Удвоить его, чтобы получить . -
Сложить и (чтобы получить результат ). -
Удвоить , чтобы получить . -
Сложить с результатом (чтобы получить ). -
Удвоить , получить . -
Не выполнять сложение с . -
Удвоить , чтобы получить . -
Сложить с результатом (чтобы получить ). -
...
В результате мы вычислим
, выполнив всего семь удвоений и четыре сложения.Если вам это понятно не до конца, то вот скрипт на Python, реализующий этот алгоритм:
def bits(n):
"""
Генерирует двоичные разряды n, начиная
с наименее значимого бита.
bits(151) -> 1, 1, 1, 0, 1, 0, 0, 1
"""
while n:
yield n & 1
n >>= 1
def double_and_add(n, x):
"""
Возвращает результат n * x, вычисленный
алгоритмом удвоения-сложения.
"""
result = 0
addend = x
for bit in bits(n):
if bit == 1:
result += addend
addend *= 2
return result
Если удвоение и сложение являются операциями
, то этот алгоритм имеет сложность (или , если учитывать битовую длину), что довольно неплохо. И, конечно, намного лучше, чем изначальный алгоритм !Логарифм
Для заданных
и у нас есть по крайней мере один полиномиальный алгоритм вычисления . Но как насчёт обратной задачи? Что если мы знаем и , а нам нужно определить ? Эта задача известна как задача логарифмирования. Мы употребляем слово «логарифм» вместо термина «деление» для согласованности с другими криптосистемами (в которых вместо умножения используется возведение в степень).Я не знаю ни одного «простого» алгоритма для решения задачи логарифмирования, однако экспериментируя с умножением, легко обнаружить некоторые закономерности. Например, возьмём кривую
и точку . Мы можем сразу убедиться, что если нечётное, то находится на кривой в левой полуплоскости; если чётное, то — в правой полуплоскости. Если поэкспериментировать ещё, мы, возможно, найдём и другие закономерности, которые приведут нас к написанию алгоритма для эффективного вычисления логарифма этой кривой.
Но существует вариация задачи логарифмирования: задача дискретного логарифмирования. Как мы увидим в следующей части, если уменьшить область определения эллиптических кривых, скалярное умножение остаётся «простым», а дискретный логарифм становится «сложной» задачей. Такая двойственность является ключевой особенностью криптографии на эллиптических кривых.
В следующей части мы исследуем конечные поля и задачу дискретной логарифмизации, а также примеры и инструменты для экспериментов.
Часть 2: эллиптические кривые над конечными полями и задача дискретного логарифмирования
В предыдущей части мы обсудили, как эллиптические кривые над вещественными числами можно использовать для определения групп. А именно, мы определили правило сложения точек: сумма трёх точек, лежащих на одной прямой, равна нулю (
). Мы вывели геометрический и алгебраический способы вычисления сложения точек.Затем мы ввели понятие скалярного умножения (
) и нашли «простой» алгоритм для вычисления скалярного умножения: удвоение-сложение.Теперь мы ограничим эллиптические кривые конечными полями, а не вещественными числами, и посмотрим, что это изменит.
Поле целых чисел по модулю p
Конечное поле — это, в первую очередь, множество конечного числа элементов. Примером конечного поля является множество целых чисел по модулю
, где — простое число. В общем виде это записывается как , или . Мы будем использовать последнюю запись.Для полей существует две двухместные операции: сложение (+) и умножение (·). Обе они замкнуты, ассоциативны и коммутативны. Для обеих операций существует уникальный единичный элемент и для каждого элемента есть уникальный элемент обратной величины. И, наконец, умножение дистрибутивно относительно сложения:
.Множество целых чисел по модулю
состоит из всех целых чисел от 0 до . Сложение и умножение работают как в модулярной арифметике. Вот несколько примеров операций над :