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

UptoLike

ВУЗ: 

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

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

Рубрика: 

105
легко вычисляются за полиномиальное время.
4. Почти для всех
K
K
~
∈
вычислительно невозможно из Е
К
вывести какое - либо легко вычисляемое преобразование, экви-
валентное
D
K
.
Свойство 4 отличает криптосистемы с открытым ключом
от традиционных криптосистем с секретным ключом, в которых
преобразования
E
K
и D
K
также зависят от секретного ключа К, но
знание преобразования
Е
К
дает знание К и D
K
или наоборот, зна-
ние
D
K
позволяет определить К и Е
К
, поэтому преобразования
E
K
и D
K
либо оба известны, либо оба неизвестны. Это свойство 4
позволяет не засекречивать преобразование зашифрования
Е
К,
а
делать его открытым для всех, кто хочет послать секретное со-
общение.
Так как в силу открытости любой злоумышленник имеет
доступ к преобразованию зашифрования Е
К
, то он может всегда
выбрать любой открытый текст и получить соответствующий
ему шифрованный текст. Поэтому системы с открытым ключом
должны быть всегда устойчивы к методам атаки по выбранному
открытому тексту.
Криптосистемы с открытым ключом обеспечивают только
практическую стойкость.
106
12. Алгоритм RSA и алгоритм Эль Гамаля работы
криптосистем с открытым ключом. Цифровая
подпись. Алгоритм цифровой подписи Эль Гамаля.
Алгоритм Ривеста (Rivest) - Шамира (Shamir) – Алде-
мана (Aldeman) – RSA(1978 год).
Одной из первых криптосистем с открытым ключом была
предложенная в 1978 году система на алгоритма
RSA. Как видно
название алгоритма,
RSA образовано из первых букв фамилий
авторов этого алгоритма. В его основе лежит использование сте-
пенной односторонней функции с секретом, которую мы рас-
сматривали на прошлых лекциях.
RSA относится к блочным ал-
горитмам, так как каждый блок ]1,0[
−
∈
nM открытого текста,
представленный как целое число из интервала
(1,2,…,n -1), пре-
образуются в блок ]1,0[
−
∈
nC шифрованного текста путем вы-
числения
),(mod)(
),(
nMMEC
e
ne
==
где e, n – ключ преобразования зашифрования.
При расшифровании блок отрытого текста
М восстанавли-
вается также путем экспоненцирования, но с другой степенью
d
в качестве ключа расшифрования, т.е.
).(mod)(
),(
ncCDM
d
nd
==
Зашифрование и расшифрование могут быть выполнены с
использованием быстрых алгоритмов экспоненцирования не бо-
лее чем за
][log0
2
n операций.
В основе алгоритма лежит известная уже теорема Эйлера,
согласно которой для каждого целого числа
М, взаимно просто-
го с модулем
n (т.е. MOD(M, n)=1) выполняется соотношение
),(mod1
)(
nM
n
≡
ϕ
где
)(n
ϕ
- функция Эйлера, т.е. число целых чисел < n и
взаимно простых с
n.
Можно показать, что если числа
e и d удовлетворяют соот-
ношению
)),((mod1 nde
ϕ
≡
⋅

Страницы