Криптографические алгоритмы. Стригунов В.В. - 10 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

Составители: 

Рубрика: 

10
)1,0,15(U
,
)1,1,9( V
и опять вычисляется строка
T
. Этот процесс
продолжается до тех пор, пока первый элемент строки
V
не станет равным нулю.
Тогда строка
U
(предпоследний столбец в схеме) содержит ответ. В нашем
случае
)3,2,3( U
. Выполним проверку
3)3(15224
.
У алгоритма Евклида есть одно важное применение. В некоторых задачах
криптографии для заданных чисел
e
и
требуется найти такое число
zd
, что
1mod zde
. (2)
Такое число
d
существует тогда и только тогда, когда числа
и
z
взаимно
простые.
Определение. Число
d
, удовлетворяющее (2), называется инверсией
по
модулю
(обозначается
zed mod
1
).
Равенство (2) означает, что для некоторого целого
k
1 zkde
. (3)
Учитывая, что
и
z
взаимно простые, перепишем (3) в виде
),()( ezНОДdekz
, (4)
что полностью соответствует (1). Поэтому, чтобы вычислить
d
, нужно просто
использовать обобщенный алгоритм Евклида для решения уравнения (4).
Значение переменной
k
нас не интересует, поэтому можно не вычислять вторые
элементы строк
U
,
V
,
T
. Если число
d
получается отрицательным, то нужно
прибавить к нему
z
, так как по определению число берется из множества
}1,...,1,0{ z
.
Следующей важной операцией в криптографии с открытыми ключами
является операция возведения в степень по модулю. Рассмотрим алгоритм,
возвращающий вычисленное значение
mod
x
ap
, где
a
,
x
,
p
целые числа.
Вход: Целые числа
a
,
1 0 2
( ... )
tt
x x x x
,
p
.
Выход: Число
mod
x
y a p
.
1, .
FOR 0,1,..., DO
IF 1 THEN mod ;
mod .
RETURN .
i
y s a
it
x y y s p
s s s p
y


В данном алгоритме биты показателя степени просматриваются справа-
налево (от младшего бита к старшему), поэтому он называется возведение в
степень справа-налево.

Страницы