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