Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
1. (Позначная модель) алисъ проситете пригнуть стречи разве возникла
2. (Второе приближение) н умере данного отствии официант простояло его то;
3. (Третье приближение) уэт быть как ты хоть а что я спящихся фигурой куда п;
4. (Четвертое приближение) ество что ты и мы сдохнуть пересовались ярким сторож;
5. (Пятое приближение) луну него словно него словно из ты в его не полагаете помощи я д;
6. (Шестое приближение) о разведения которые звенел в тонкостью огнем только.
Как видим, тексты вполне “читаемы”.
Отметим, что с более общих позиций открытый текст может рассматриваться как реализация стационарного эрго-дического случайного процесса с дискретным временем и конечным числом состояний [Гне88].
82
Основные понятия
Критерии распознавания открытого текста
Заменив реальный открытый текст его моделью, мы можем теперь построить критерий распознавания открытого текста. При этом можно воспользоваться либо стандартными методами различения статистических гипотез, либо наличием в открытых текстах некоторых запретов, таких, например, как биграмма ЪЪ в русском тексте. Проиллюстрируем первый подход при распознавании позначной модели открытого текста.
Итак, согласно нашей договоренности, открытый текст представляет собой реализацию независимых испытаний случайной величины, значениями которой являются буквы алфавита А = появляющиеся в соответствии с распределением вероятностей Р(A) = (P^ai р(ап)) . Требу-
ется определить, является ли случайная последовательность ClC2t-Xl букв алфавита А открытым текстом или нет.
Пусть H0 — гипотеза, состоящая в том, что данная последовательность — открытый текст, H1 — альтернативная гипотеза. В простейшем случае последовательность ClC2^xl можно рассматривать при гипотезе H1 как случайную и равновероятную. Эта альтернатива отвечает субъективному представлению о том, что при расшифровании криптограммы с помощью ложного ключа получается “бессмысленная” последовательность знаков. В более общем случае можно считать, что при гипотезе H1 последовательность CxC2..X1 представляет собой реализацию независимых испытаний некоторой случайной величины, значениями которой являются буквы алфавита А = {а, появляющиеся в соответствии с
распределением вероятностей Q(A) = (q(al)9...9q(an)). При таких договоренностях можно применить, например, наибо-
83
fлава 2
лее мощный критерий различения двух простых гипотез, который дает лемма Неймана—Пирсона [Кра75]
В силу своего вероятностного характера такой критерий может совершать ошибки двух родов. Критерий может принять открытый текст за случайный набор знаков. Такая ошибка обычно называется ошибкой первого рода, ее вероятность равна a = р (H1ZH0) . Аналогично вводится ошибка второго
рода и ее вероятность /? — /?{H0/Hj} . Эти ошибки определяют качество работы критерия. В криптографических исследованиях естественно минимизировать вероятность ошибки первого рода, чтобы не “пропустить” открытый текст. Лемма Неймана—Пирсона при заданной вероятности первого рода минимизирует также вероятность ошибки второго рода.
Критерии на открытый текст, использующие запретные сочетания знаков, например к -граммы подряд идущих букв, будем называть критериями запретных к-грамм. Они устроены чрезвычайно просто. Отбирается некоторое число s редких А;-грамм, которые объявляются запретными. Теперь, просматривая последовательно к -грамму за к -граммой анализируемой последовательности C1C2...^, мы объявляем ее
случайной, как только в ней встретится одна из запретных к -грамм, и открытым текстом в противном случае. Такие критерии также могут совершать ошибки в принятии решения. В простейших случаях их можно рассчитать. Несмотря на свою простоту, критерии запретных к -грамм являются весьма эффективными.
Контрольные вопросы
1. Чем отличаются подходы к обеспечению безопасности информации в криптографии и в методах сокрытия информации?
84
Основные понятия
2. Какими методами обеспечивается конфиденциальность информации?
3. Что такое целостность информации?
4. Для каких аспектов информационного взаимодействия необходима аутентификация?
5. Какие средства используются для обеспечения невозможности отказа от авторства?
6. В чем суть предварительного распределения ключей?
7. В чем разница между обычным и открытым распределениями ключей?
8. Для чего нужны схемы разделения секрета?
9. Что такое сертификат открытого ключа?
10. Каковы функции центра сертификации ключей?
11. Чем отличаются алгебраическая и вероятностная модели шифра?
12. С какими целями в криптографии вводят модели открытых текстов?
13. Как подсчитать вероятность данного открытого текста в модели первого приближения?
14. Какие подходы используются для распознавания открытых текстов?
15. Какая идея воплощена в расположении клавиш на клави-туре пишущей машинке, компьютера, логотипа?
Глава З
Классификация шифров по различным признакам
В качестве первичного признака, по которому производится классификация шифров, используется тип преобразования, осуществляемого с открытым текстом при шифровании. Если фрагменты открытого текста (отдельные буквы или группы букв) заменяются некоторыми их эквивалентами в шифртексте, то соответствующий шифр относится к классу шифров замены. Если буквы открытого текста при шифровании лишь меняются местами друг с другом, то мы имеем дело с шифром перестановки. С целью повышения надежности шифрования шифрованный текст, полученный применением некоторого шифра, может быть еще раз зашифрован с помощью другого шифра. Все возможные такие композиции различных шифров приводят к третьему классу шифров, которые обычно называют композиционными шифрами. Заметим, что композиционный шифр может не входить ни в класс шифров замены, ни в класс шифров перестановки. В результате получаем первый уровень классификации шифров (см. рис. 8).
