Ассиметричное шифрование на базе эллиптических кривых
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Вµдующих требований:
вычисление пары ключей (Ко, Кс) должно быть простым;
отправитель может легко вычислить криптограмму, зная открытый ключ Ко и сообщение М;
= ЕКо(М) (3)
получатель может легко восстановить исходное сообщение, используя секретный ключ Кс и криптограмму С
М = DКс (С) (4)
при попытке вычислить секретный ключ Кс противник наталкивается на непреодолимую вычислительную проблему, даже зная открытый ключ Ко;
при попытке вычислить исходное сообщение М противник также наталкивается на непреодолимую вычислительную проблему, даже зная пару (Ко, С).
2.2 Анализ существующих алгоритмов
Для выполнения дипломной работы понадобилось изучить два вида алгоритмов:
алгоритмы нахождения НОД;
алгоритмы ассиметричного шифрования.
Алгоритмы нахождения НОД
Алгоритм Евклида
Алгоритм Евклида - алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин.
Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В Началах Евклида он описан дважды - в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения общей меры двух отрезков.
Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.
Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида теорию отношений, альтернативную по отношению теории отношений Евдокса, изложенной в V книге Начал Евклида. Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.
Алгоритм Евклида для целых чисел
Пусть a и b целые числа, не равные одновременно нулю, и последовательность чисел
определена тем, что каждое rk - это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
a = bq0 + r1= r1q1 + r2= r2q2 + r3
? 2 = rk ? 1qk ? 1 + rk
? 1 = rnqn
Тогда НОД(a,b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности.
Существование таких r1,r2,..., то есть возможность деления с остатком m на n для любого целого m и целого , доказывается индукцией по m.
Проще сформулировать алгоритм Евклида так: если даны натуральные числа a и b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
Бинарный алгоритм
Бинарный алгоритм Евклида - метод нахождения наибольшего общего делителя двух целых чисел, основанный на использовании следующих свойств НОД:
НОД(2m, 2n) = 2 НОД(m, n),
НОД(2m, 2n+1) = НОД(m, 2n+1),
НОД(-m, n) = НОД(m, n)
Алгоритм
НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
НОД(1, n) = 1; НОД(m, 1) = 1;
Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
Если m, n нечётные, то НОД(m, n) = НОД(n, |m - n|).
Так как алгоритм является Хвостовой рекурсией, то рекурсию можно заменить итерацией.
Криптосистема шифрования данных RSA
В настоящее время наиболее изученным методом криптографической защиты, основанным на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов, является алгоритм RSA (названый по начальным буквам фамилий ее изобретателей Rivest, Shamir, Adleman). Этот алгоритм может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.
Схема RSA представляет собой блочный шифр, в котором открытый и зашифрованный тексты представляются целыми числами из диапазона от 0 до N - 1 для некоторого N, т.е. открытый текст шифруется блоками, каждый из которых содержит двоичное значение, меньшее некоторого заданного числа N. Это значит, что длина блока должна быть меньше или равна log2(N).
Трудность факторизации больших чисел и трудность вычисления дискретных логарифмов определяют надежность алгоритма RSA. В данной криптосистеме открытый ключ Ко, секретный ключ Кс, сообщение М и криптограмма С принадлежат множеству целых чисел
где N - модуль, P и Q являются случайными большими взаимно простыми числами. Их выбирают равной длины и хранят в секрете для обеспечения максимальной безопасности.
Множество ZN с операциями сложения и умножения по модулю N образует арифметику по модулю N.
Открытый ключ Ко выбирают случайным образом так, чтобы выполнялись условия
где (N) - функция Эйлера, которая указывает количество положительных