Ассиметричное шифрование на базе эллиптических кривых (стр. 5 из 10)
· НОД(-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) – функция Эйлера, которая указывает количество положительных целых чисел в интервале от 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)
r2 = b − r1q1 = a(− q1) + b(1 + q1q0)
gcd(a,b) = rn = as + bt
здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
Связь с цепными дробями
Отношение 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. Выбор 2-х взаимно простых чисел А и С;
2. Выбор числа В < С;
3. Устанавливаем начальные значения для вычисления обратного элемента:
4. Подставляем значения в формулы:
5. Последовательно выполняем вычисление шага 4, пока
. В ответ пойдет последний, отличный от нуля остаток 
6. После вычисления мы получим следующее равенство:
7. Подставляем полученное значение r в выражение и вычисляем значение x:
8. Подставляем полученный результат в исходное выражение
х * А=В mod С и проверяем полученный результат.
Алгоритм формирования конечного поля Галуа GF(p) и подсчет количества точек эллиптической кривой n=#Ep
Теоретические сведения
На момент начала формирования поля GF(p) необходимо иметь инициализованные переменные эллиптической кривой, такие как p (простое число), a, b, а также выбрать координату х первой точки. Рассмотрим порядок формирования GF(p):
1. Проверяем условие несингулярности кривой:
2. Рассчитываем координату Yпервой точки по формуле:
3. Находим следующую точку поля, путем удваивания первой точки: