Ассиметричное шифрование на базе эллиптических кривых
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?елых чисел в интервале от 1 до N, которые взаимно просты с N.
Кроме того, открытый ключ Ко и функция Эйлера ?(N) также должны
быть взаимно простыми.
Затем, используя расширенный алгоритм Евклида, вычисляют секретный ключ Кс такой, что
Данное вычисление возможно, поскольку получатель знает пару простых чисел (P, Q) и может легко найти ?(N), при этом Кс и N должны быть взаимно простыми. Задачу зашифрования открытого текста М в криптограмму С можно решить, используя открытый ключ Ko, по следующей формуле:
Задачу расшифрования криптограммы С можно решить, используя секретный ключ Кс, по следующей формуле:
Процесс расшифрования можно записать так:
Подставляя значение в предыдущие 2 формулы, получаем:
Таким образом, получатель, который создает криптосистему, защищает два параметра: секретный ключ Кс и пару чисел P и Q, произведение которых даёт модуль N. Одновременно публикует значения модуля N и открытого ключа Ко, поэтому противнику известны только значения Ко и N. Если бы криптоаналитик смог разложить число N на множители P и Q, то он узнал бы тройку чисел (P,Q, Ko), значение функции Эйлера ?(N) = (P - 1) (Q - 1) и определил значение секретного ключа Kc.
Однако, как отмечалось выше, разложение большого числа N на множители вычислительно не осуществимо при длине выбранных P и Q не менее 100 десятичных знаков.
2.3 Используемые алгоритмы
Расширенный алгоритм Евклида
Формулы для ri могут быть переписаны следующим образом:
r1 = a + b(- q0)2 = b ? r1q1 = a(? q1) + b(1 + q1q0)
gcd(a,b) = rn = as + bt
здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t - коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
Связь iепными дробями
Отношение a / b допускает представление в виде цепной дроби:
.
При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t / s, взятому со знаком минус:
.
Ускоренные версии алгоритма
Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка:
где
Одна из наиболее многообещающих версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии Разделяй и "аствуй позволяет уменьшить асимптотическую сложность алгоритма.
ECЕS
В алгоритме ECES (Elliptic Curve Encryption Scheme) на первом этапе должны быть определены параметры, являющиеся общей открытой информацией для всех пользователей системы:
конечное поле GF(p);
эллиптическая кривая E(GF(p));
большой простой делитель количества точек кривой p;
точка G, координаты которой имеют порядок, что и число p.
Каждый пользователь системы генерирует пару ключей следующим образом:
выбирает случайное целое число Kc, 1 < Kc < p -1;
вычисляет точку Kо = Kc P.
При этом секретным ключом пользователя является число Kc, открытым ключом - точка Kо. Кроме того, сообщение M разбивается на блоки длиной 2L - 16 бит, где L равно ближайшему большему целому от log2 p;
выбирается случайное целое число k, 1 < k < n - 1;
вычисляется точка (х1, у1) = kP;
вычисляется точка (х2, у2) = k Kо.
Известно несколько подходов к зашифрованию - расшифрованию информации, предполагающих использование эллиптических кривых. Мы рассмотрим наиболее простой из этих подходов. Как было изложено выше, зашифрованное сообщение пересылается в виде значения (х, у) для точки Pm. Здесь точка Рm будет представлять зашифрованный текст и впоследствии будет расшифроваться. В качестве параметров данной криптосистемы рассматривается точка G и эллиптическая группа Еp (а, b).
Пользователи А и В выбирают секретные ключи KcА и KcB, а также генерируют открытые ключи KоA = KcА P и KоB = KcB P соответственно. Чтобы зашифровать сообщение Рm, пользователь А выбирает случайное положительное целое число k и вычисляет криптограмму Сm с помощью открытого ключа стороны В, - KоB, состоящую из двух точек
Cm = {(kG), (Pm + k KоB) }.
Чтобы расшифровать эту криптограмму, пользователь В умножает первую точку (kP) на cвой секретный ключ KcB и вычитает результат из второй точки:
(Рm + k KоB) - KcB (kP) = Рm + k(KcB P) - KcB (kP) = Рm.
Пользователь А замаскировал сообщение Рm с помощью добавления к нему маски k KоB.. Однако следует заметить, что никто не сможет убрать маску k KоB, кроме пользователя, который знает значение k и имеет личный ключ KcB. Противнику для восстановления сообщения придется вычислить k по данным P и kP, что является трудной задачей. В качестве примера возьмем
р = 751, ЕP = (-1, 188) и P = (0, 376).
Все расчеты в данном примере выполняются по модулю p.
Предположим, что пользователь А отправляет пользователю В сообщение, которое кодируется точкой Рm = (562, 201), и выбирает случайное число k = 386. Открытым ключом В является KоB = (201, 5). Мы имеем 386(0, 376) = (676, 558) и (562, 201) + 386(201, 5) = (385, 328).
Таким образом, пользователь А должен послать зашифрованный текст {(676, 558), (385, 328)}.
2.4 Выполнение алгоритмов
Нахождение обратного элемента с помощью расширенного алгоритма Евклида
Теоретические сведения
Вычисляем значение х, в выражении х * А=В mod С
1.Выбор