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

UptoLike

ВУЗ: 

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

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

Рубрика: 

15
2. Стойкость криптографических систем и
алгоритмов. Информационно - теоретический
подход и подход на основе теории сложности.
Основным назначением криптосистем является обеспече-
ние передачи секретных сообщений через несекретные каналы
связи. Поэтому важнейшей характеристикой любой криптоси-
стемы является ее стойкость, т.е. способность противостоять
попыткам дешифровать перехваченный шифротекст или рас-
крыть ключи шифра.
Исторически первым подходом к определению стойкости
криптосистем был информационно - теоретический подход,
предложенный К. Шенноном. Этот подход основан на понятии
информации, ее количественной оценке и анализе количества
информации об открытом тексте, для обеспечения стойкости
криптосистемы.
Формально количество информации в сообщении измеря-
ется энтропией.
Пусть
n
xx ,...,
1
есть n возможных сообщений, появляю-
щихся с вероятностями
∑
=
=
n
i
in
xPпричемxPxP
1
1
1)( ) (),...,(
Тогда энтропия сообщения x есть
22
11
1
() ( )log ( ) ( )log
()
nn
ii i
ii
i
Hx Px Px Px
P
x
==
=− =
∑∑
Для заданного n величина H(x) принимает max значение,
равное
n
2
log
при
n
xPxP
n
1
)(...)(
1
===
,
т.е. когда все сообщения равновероятны. Неопределен-
ность (энтропия) уменьшается, когда распределение вероятно-
стей сообщений становится все более отличным от равновероят-
ного и достигает min H(X)=0 когда 1)(
=
i
xP для некоторого
16
сообщения
i
x . Энтропия сообщения измеряет его неопреде-
ленность в числе бит информации, которая должна быть восста-
новлена, когда сообщение было скрыто от криптоаналитика в
шифротексте.
К. Шеннон различал теоретическую и практическую стой-
кость криптосистем. Криптосистема называется теоретически
стойкой, если криптоаналитик не может уточнять распределе-
ние вероятностей возможных открытых текстов по имеющемуся
и у него шифротексту, даже если он обладает всеми необходи-
мыми для этого средствами. При этом предполагается, что сек-
ретный ключ используется только один раз (т.е. сеансовый ре-
жим использование ключа).
Совершенная секретность означает, что открытый текст
М и шифротекст С статистически независимы т.е. совпадают ве-
роятности
)()/(
M
P
C
M
P
=
для всех возможных M и C и получение шифротекста не
дает криптоаналитику дополнительной информации о послан-
ном открытом тексте.
Определение совершенной секретности можно также пред-
ставить в виде
)()/(
M
H
C
M
H
Пусть P(C/M) - условная вероятность получения шифро-
текста С при условии, что известно, что зашифрован текст М на
некотором неизвестном ключе. Тогда
:()
(/ ) (),
k
kE M C
PC M Pk
=
=
∑
где
k
P
- вероятность использования ключа
k
,
k
E
- пре-
образование зашифрования на ключе
k
.
Обычно существует по крайней мере один ключ
k
, такой
что CME
k
=
)( для данных М и С, но иногда текст М может
быть зашифрован в текст С при нескольких различных ключах.
Необходимым и достаточным условием для совершенной
секретности является то, что для каждого С и для всех М выпол-
нено

Страницы