Алгоритм RSA. Жданов О.Н - 5 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

5
1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Концепция криптографии с открытым ключом была предложена Уитфил-
дом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman), и, неза-
висимо от них, Ральфом Мерклом (Ralph Merkle). Основная идея заключается в
том, чтобы использовать ключи парами, состоящими из ключа зашифрования и
ключа расшифрования, которые невозможно вычислить один из другого.
В 1976 г. вышла основополагающая работа [1]. С этого времени
было создано
много алгоритмов, использующих концепцию открытых ключей. Алгоритм яв-
ляется общедоступным, нет необходимости в секретных каналах связи. Общая
схема выглядит следующим образом:
1. Каждый пользователь генерирует пару ключей: один для шифрования,
другой для дешифрования.
2. Каждый пользователь публикует свой ключ шифрования, размещает его
в открытом для всех доступе. Второй ключ, соответствующий
открытому, со-
храняется в секрете.
3. Если пользователь
A собирается послать сообщение пользователю B, он
шифрует сообщение открытым ключом пользователя
B.
4. Когда пользователь
B получает сообщение, он дешифрует его с помо-
щью своего личного (секретного) ключа. Другой получатель не сможет дешиф-
ровать сообщение, поскольку личный ключ
B знает только B.
1.1. ОПИСАНИЕ АЛГОРИТМА RSA
В 1978 г. появилась работа [2], в которой Рон Райвест (Ron Rivest), Ади
Шамир (Adi Shamir) и Лен Адлеман (Len Adleman) предложили алгоритм с от-
крытым ключом. Схема Райвеста–Шамира–Адлемана (RSA) получила широкое
распространение.
Опишем процесс шифрования. Исходный текст должен быть переведен в
числовую форму, этот метод считается известным. В результате этого текст
представляется в виде одного большого числа
. Затем полученное число разби-
вается на части (блоки) так, чтобы каждая из них была числом в промежутке
[0,
N – 1] (о выборе N — см. ниже). Процесс шифрования одинаков для каждого
блока. Поэтому мы можем считать, что блок исходного текста представлен чис-
лом
x, 01
x
N≤≤ −.
Каждый абонент вырабатывает свою пару ключей. Для этого он генериру-
ет два больших простых числа
p и q, вычисляет произведение Npq=⋅. Затем
он вырабатывает случайное число e, взаимно простое со значением функции
Эйлера от числа N,
(
)
()
(
)
11Np qϕ =−⋅− и находит число d из условия
e·d = 1(
mod φ(N)). Так как
(
)
(
)
,1eNϕ
=
, то такое число d существует и оно един-
ственно. Пару (N, e) он объявляет открытым ключом и помещает в открытый
доступ. Пара (N, d) является секретным ключом. Для расшифрования достаточ-

Страницы