2020-01-14
111
Расширенный алгоритм Евклида
Формулы для 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)}.
