Математические основы криптологии. Галуев Г.А. - 55 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

109
).(mod nMC
e
=
5. Получатель сообщения (пользователь , у которого хра-
нится ключ
d) расшифровывает сообщение С, возводя его в сте-
пень
d по модулю n, т.е.
).(mod)(mod nMnCM
ded ⋅
==
Пример.
Пусть р=211, q=223 – простые числа. Тогда
n=p·q=47053,
46620)1)(1()( =−
−
=
qpn
ϕ
. Выберем открытый
ключ
с = 16813 и вычислим секретный ключ расшифрования d
такой, что
,46620(mod116813))(mod(1
≡
⋅=
≡
⋅
dnde
откуда
d = 19837. Возьмем в качестве сообщения М название ал-
горитма, т.е.
RSA. Чтобы перевести RSA в число будем считать
букву
R= 18, S= 19, A = 1 по порядковому номеру в латинском
алфавите. На представление каждой буквы отведем по 5 бит
числа, представляющего открытый текст
М. Тогда слову RSA
будет соответствовать число
16501832)19)321((
=
+
⋅+⋅
=
M
С помощью открытого ключа
е получим шифровку:
1650)(mod == nMC
e
16813
3071)47053(mod
=
.
Получатель расшифрует эту шифровку с помощью секрет-
ного ключа
d
19837
(mod ) 3071
d
MC n==(mod 47053) 1650
=
.
Для полноты изложения отметим, что для алгоритма
RSA
существует малая вероятность того, что шифровка числа
М воз-
ведем в степень
е по модулю n может не изменить открытый
текст
М. Это следует из теоретического факта, что для каждого
значения
е существует, по крайней мере, 9 таких значений М,
что
).(mod nMM
e
≡
Например,
для n=p·q= 47·59=2773 это числа
М = 0,1,2773,2537,2303,235,2538,471,236.
В алгоритме
RSA вместо функции Эйлера )(n
ϕ
можно ис-
пользовать функцию Кармайкла )(n
λ
, которая для произвольно-
го целого числа определяется
110
⎪
⎩
⎪
⎨
⎧
=
≥=
<=
=
−
−
....2)),(),...,2((
3,2,2
3,2,2
)(
1
00
1
2
1
rr
a
r
a
a
a
r
a
tt
tt
ppnpHOK
tn
tт
n
λλ
λ
Для )(n
λ
справедлива теорема Камайкла, обобщающая
теорему Эйлера: для любого целого
М, взаимно простого с чис-
лом
n, верно сравнение
).(mod1
)(
nM
n
≡
λ
Если теперь в алгоритме
RSA заменить )(n
ϕ
на )(n
λ
и при
n=p·q считать
),1,1(
)1,1(
)(
)( −−=
−−
= qpHOK
qpHOD
n
n
ϕ
λ
то получим модификацию
RSA на основе функции Кармайкла
).(n
λ
Стойкость алгоритма
RSA можно оценить сверху сложно-
стью разложения целого числа
n на простые сомножители p и q с
последующим определением )(n
ϕ
. Это весьма трудная задача.
Другим примером криптосистемы с открытым ключом яв-
ляется система открытого шифрования Эль Гамаля, предложен-
ная в 1985 году. Алгоритм, лежащий в основе этой системы,
предлагает следующую последовательность действий:
1. Отправитель
А и получатель В знают большое простое
число
Р. Сообщения М представляются целыми числами из ин-
тервала
{1, p} т.е. M=2,…, p -1. Отправитель А генерирует слу-
чайное число
},1{ pe
∈
, получатель В также генерирует случай-
ное число
d из интервала {1, p}.
2. Отправитель
А шифрует сообщение ключом е в виде
)(mod pCC
d
AB
= и посылает его В.
3. Получатель В шифрует принятое сообщение
A
C своим
ключом
d в виде
)(mod pCC
d
AB
=
и посылает его
А.
4. Отправитель
А «снимает» свой ключ операцией

Страницы