Методы и средства криптографической защиты информации. Жданов О.Н - 154 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

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

Рубрика: 

154
Описание алгоритма RSA
В 1978 г. Появилась работа [20], в которой Рон Райвест(Ron Rivest), Ади
Шамир(Adi Shamir) и Лен Адлеман(Len Adleman) предложили алгоритм с
открытым ключом. Схема Райвеста–Шамира–Адлемана (RSA) получила
широкое распространение.
Опишем процесс шифрования. Исходный текст должен быть переведен в
числовую форму. Метод преобразования текста в числовую форму считается
известным. В результате текст представляется в
виде одного большого числа.
Затем полученное число разбивается на части (блоки) так, чтобы каждая из
них была числом в промежутке [0,N-1], о выборе N — см. ниже. Процесс
шифрования одинаков для каждого блока. Поэтому мы можем считать, что
блок исходного текста представлен числом x,
10
−
≤
≤
Nx .
Каждый абонент вырабатывает свою пару ключей. Для этого он
генерирует два больших простых числа p и q, вычисляет произведение
qpN ⋅= . Затем он вырабатывает случайное число e, взаимно простое со
значением функцией Эйлера от числа N,
(
)
(
)
(
)
11 −
⋅
−
=
qpN
ϕ
и находит число d
из условия
()()
Nde
ϕ
mod1
=
⋅ . Так как
(
)
(
)
1,
=
Ne
ϕ
, то такое число d существует и
единственно. Пару (N,e) он объявляет открытым ключом и помещает в
открытый доступ. Пара (N,d) является секретным ключом. Для
расшифрования достаточно знать секретный ключ. Числа p, q,
(
)
N
ϕ
в
дальнейшем не нужны, поэтому их можно уничтожить.
Пользователь A, отправляющий сообщение x абоненту B, выбирает из
открытого каталога пару (N,e) абонента B и вычисляет шифрованное
сообщение
()
Nxy
e
mod= . Чтобы получить исходный текст, абонент B
вычисляет
()
Ny
d
mod . Так как ))((mod1 Nde
ϕ
≡
⋅
, т.е. 1)( +⋅
=
⋅
kNde
ϕ
, k — целое,
то применяя теорему Эйлера получим:
)(mod)()(
)(1)(
Nxxxxxxy
kNkNedded
≡⋅≡≡≡≡
+⋅
ϕϕ
.
Пример 1. Пусть p = 7, q = 17. Тогда N = 7·17 = 119,
96)( =N
ϕ
. Выбираем e
такое, что:
1)96,(,96 =
<
ee . Пусть в нашем случае e = 5. Находим d:
)96(mod/1 ed = . Получаем d = 77, т.к. 77·5 = 4·96+1. Открытый ключ: (119,5).
Личный ключ: (119,77). Пусть, например, X = 19. Для зашифрования число 19
возводим в степень 5 по модулю 119. Имеем: 19
5
= 2476099, и остаток от
деления 2476099 на 119 равен 66. Итак, y = 19
5
mod 119 = 66.
Расшифрование: x = 66
7
mod 119 = 19.
О вычислениях
Как шифрование, так и расшифрование в RSA предполагают
использовании операции возведения целого числа в целую степень по
модулю N. Если возведение в степень выполнять непосредственно с целыми
числами и только потом проводить сравнение по модулю N, то
промежуточные значения окажутся огромными. К счастью, здесь можно
воспользоваться свойствами арифметики в
классах вычетов:
NabNNbNa mod)(mod)mod()mod( =⋅
. Таким образом, мы можем

Страницы