Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
K(Piylv) = fi(<p(y)9<p(v)) = M(y,v) = 1 •
Аналогично получаем равенство ju(<p(y)9u) = 1. Следовательно, <p(y)eO](u)nO](v).
200
Надежность шифров
Легко заметить, что пересечение Oj(«)nO|(v) состоит лишь из двух точек — d и у . Поэтому <р(у) є {d,y} . По предположению индукции (p{d) = J, а так как (р — биекция, то ф(у) = JF, что и требуется.
Мы доказали равенство (50). Тем самым теорема доказана.
Согласно теореме А.А.Маркова, в классе эндоморфных шифров, не изменяющих длины сообщений, не распространяют искажений типа замены знаков, например, шифры перестановки, поточные шифры однозначной замены, а также их композиции типа шифр замены — шифр перестановки.
Шифры, не распространяющие искажений типа “пропуск-вставка знаков”
При исследовании свойств шифров, не распространяющих искажений типа “пропуск знаков”, так же, как и в предыдущем случае, ограничимся рассмотрением лишь эндоморфных шифров. Отметим также, что исследование вопроса об искажениях типа “вставка знаков” производится совершенно аналогично, поэтому далее пойдет речь лишь об искажениях типа “пропуск знаков”.
Приведем результат характеризации множества E подстановок на множестве X = Y, отвечающего подстановочной модели эндоморфного шифра Yn =(ХЩЕ), не распространяющего искажений типа “пропуск знаков”.
L
В данном случае X = Y = \^АЛ , где А — алфавит со-
/1=1
общений. Пусть є — бинарное отношение на множестве X, определенное следующим образом. Пусть а,а’єХ, тогда
201
І лава 7
aea'o 3j є I,Я :a = (ax,...,ax),a'= (a,,...,a7_,,ay+1 к
Через є обозначим “степень” отношения є :
аєка'<ї> За1,...,#*-1 є X, аєах 9...9ак~х єа'.
Определение 3. Будем говорить, что шифр Y,n=(X,E) не распространяет искажений типа “пропуск знаков ”, если для любых х, у є X, любого к, меньшего длины слова х,
а также любого ееЕ из условия XSkу следует, что
(е~хх)єк(е~V).
Обозначим через пL отображение множества X в себя, определенное для любого a = (аІ9...,ад) є X формулой
nL(aX9...9ax) = (к(ах\...9тг(ах)),
где п — некоторая подстановка множества А, а через f — отображение X в себя, меняющее порядок следования букв любого слова на противоположный: /(#],...,ад) =
Приведем без доказательства следующий результат [Глу98,99].
Теорема. Если Yn =(X9E) — шифр, не распространяющий искажений типа “пропуск знаков ”, то для любого ееЕ либо е = пі, либо е = пі • f (при подходящем TreS(A)).
Таким образом, класс шифров, не распространяющих искажений типа “пропуск-вставка знаков”, более беден,
202
Надежность шифров
нежели класс шифров, не распространяющих искажений типа замены знаков. Таковыми являются, например, шифры простой замены (или одноалфавитные шифры замены) или шифры простой замены, усложненные перестановкой, осуществляющей изменение порядка следования знаков любого слова на противоположный.
Контрольные вопросы
1. Как определяются энтропия и избыточность языка?
2. Как можно качественно охарактеризовать избыточность языка?
3. Какие тексты на русском языке имеют большую избыточность: литературные или технические?
4. Почему неопределенность шифра по открытому тексту (или по ключу) можно рассматривать как меру теоретической стойкости шифра?
5. Как зависит расстояние единственности для шифра от энтропии языка?
6. Найдите расстояние единственности для шифра Виже-нера, который используется для шифрования русских технических текстов с избыточностью 0,5.
7. Какие атаки используются в криптоанализе?
8. Каким образом априорные вероятностные распределения на множествах открытых текстов и ключей индуцируют вероятностное распределение на множестве шифрованных текстов?
9. Какой шифр называется совершенным (для атаки на основе шифртекста)?
10. В каком случае шифр модульного гаммирования является совершенным (для атаки на основе шифртекста)?
11. Верно ли, что лишь шифры табличного гаммирования являются совершенными?
12. Чем отличаются понятия теоретической и практической стойкости шифра?
203
І лава 7
13. Что такое имитостойкость шифра? Что может служить мерой имитостойкости шифра? Является ли шифр гаммирования имитостойким?
14. Что такое совершенная имитостойкость шифра?
15. Является ли шифр гаммирования шифром, не размножающим искажений типа “замена знаков”, “пропуск знаков”?
Глава 8
Блочные системы шифрования
Используемые в настоящее время системы шифрования делятся на два класса: блочные и поточные системы. Как отмечалось в § 3.2, основной критерий такого разделения — мощность алфавита, над знаками которого производится операция шифрования. Если открытый текст перед шифрованием разбивается на блоки, состоящие из нескольких знаков, то есть исходное сообщение обрабатывается блоками, то мы имеем дело с блочным шифром. Если каждый знак сообщения шифруется отдельно, то такой шифр — поточный.
Разделение шифров на поточные и блочные связано с алгоритмическими и техническими особенностями реализации шифрующих преобразований, использующими возможности существующей элементной базы (разрядность процессоров, быстродействие микросхем, объем памяти компьютера). При увеличении мощности алфавита необходимо исследовать, прежде всего, вопросы о выборе преобразований, реализуемых криптосхемой, и способе их практической реализации, влияющем на эффективность функционирования криптосхемы с точки зрения эксплуатационных характеристик.
