Дешифрация и криптоанализ шифров

Дешифрация сообщений для методов перестановок и простых замен при знании ключа шифрования состоит в прохождении всех этапов алгоритма шифрования в обратном порядке.

Для шифрующих таблиц и шифра «скитала» необходимо вписать шифртекст в таблицу в том порядке, в котором он был выписан из нее, затем выполнить предпоследний этап шифрования и так далее до первого этапа шифрования. Таким образом, последний этап дешифрации соответствует первому этапу шифрования, и исходное сообщение считывается из таблицы в том порядке, в котором было вписано в нее.

Для дешифрации методами простых замен, как правило, выполняется всего один основной этап, обратный процессу шифрования, например, дешифрация по методу Цезаря заключается в замене каждой буквы шифртекста на букву, стоящую в алфавите впереди на K позиций.

Криптоанализ. Фундаментальное правило криптоанализа, заключается в том, что стойкость шифра (криптосистемы) должна опре­деляться только секретностью ключа. То есть предполагаем, что весь алгоритм шифрования, кроме значения секретного ключа, известен криптоаналитику. Следующее допущение в криптоанализе состоит в том, что криптоаналитик имеет в своем распоряжении шифртексты сообщений.

Одной из простых и универсальных криптоаналитических атак является метод полного перебора всех возможных ключей с проверкой, является ли осмысленным получающийся открытый текст.

Определить осмысленность текста можно на основе статистического анализа частот появления букв, например, вероятность появления в русскоязычном тексте буквы «О» 9% - она встречается чаще других, а буква «Ф» является «редкой», вероятность ее появления в тексте всего 0,2%. Таким образом, проанализировав частоты появления различных букв в расшифрованном тексте, можно подтвердить или опровергнуть используемый ключ при дешифрации ключ шифра. Данные о распределении вероятности появления букв в русском тексте приведены в табл. 5.

Таблица 5

Статистические данные по распределению вероятностей букв

в русских текстах

Символ	Вероятность	Символ	Вероятность	Символ	Вероятность
Пробел	0,175	К	0,028	Ч	0,012
О	0,090	М	0,026	Й	0,010
Е	0,072	Д	0,025	Х	0,009
А	0,062	П	0,023	Ж	0,007
И	0,062	У	0,021	Ю	0,006
Н	0,053	Я	0,018	Ш	0,006
Т	0,053	Ы	0,016	Ц	0,004
С	0,045	З	0,016	Щ	0,003
Р	0,040	Ъ	0,014	Э	0,003
В	0,038	Б	0,014	Ф	0,002
Л	0,035	Г	0,013

Для многих методов простых замен путем статистического анализа частот появления букв в шифртексте можно определить ключ шифрования, например, если в шифртексте, полученном по методу Цезаря, больше всего букв «Р», «З», «В» и «Л» (при условии отсутствия в алфавите пробела) можно с большой степенью вероятности утверждать что ключ шифрования K=2. Действительно, если вычесть из кодов этих букв 2, то получатся наиболее часто встречаемые буквы открытого текста «О», «И», «А», «И». Вероятность правильности криптоанализа в данном случае напрямую зависит от размера, анализируемого шифртекста.

Короткие сообщения не могут дать достаточно точной статистической информации о частоте встречаемости букв. Для криптоанализа шифров таких сообщений, чтобы определить ключ шифрования, дополнительно необходимо знать открытый текст сообщения или его фрагмент.

Если криптоаналитик знает открытый текст и шифртекст, использование метода перебора становится универсальным для любых методов шифрования перестановками и простыми заменами, даже для коротких, состоящих из нескольких десятков символов сообщений.

Пример 12. На основании фрагмента открытого текста и полученного из него методом шифрующих таблиц шифртекста необходимо найти ключ шифрования.

Ключом для метода шифрующих таблиц является число строк и число столбцов таблицы. Поэтому, начиная с таблицы минимального размера, подбираем ключ. Для каждого размера таблицы (2х2, 2х3, 3х3, 3х4 и т.д.) проверяем, позволяет ли выбранная нами таблица правильно дешифровать шифртекст. Если при дешифрации с помощью таблицы размером 3х5 получается сообщение, полностью совпадающее с соответствующим фрагментом исходного текста, то ключ считается раскрытым и подбор завершается. Следующую часть сообщения дешифруют с помощью полученного ключа – таблицы, состоящей из 3 строк и 5 столбцов.

Варианты заданий

Во всех вариантах необходимо разработать программы для решения перечисленных в них задач. Программы необходимо ориентировать на шифрование и дешифрацию русскоязычных сообщений, в которых используются только русские прописные буквы от А до Я (кроме буквы «Ё»), пробел, запятая, точка и дефис. Обрабатываемые сообщения, результаты шифрования и символьные ключи должны хранится в текстовых файлах. Числовые ключи должны вводиться с клавиатуры.

1. Зашифровать и расшифровать с помощью шифра «скитала» сообщение длиной от 15 до 100 символов.

2. Найти ключ для метода шифрования Цезаря по известному фрагменту открытого текста (10 символов), расположенному в неизвестном месте текста.

3. Найти ключ для метода шифрования Цезаря по частоте встречаемости символов. Недостающие статистические сведения собрать самостоятельно с помощью автоматизированного анализа частот встречаемости символов.

4. Зашифровать и расшифровать сообщение с помощью аффинной системы подстановок Цезаря.

5. Зашифровать и расшифровать сообщение методом Цезаря с ключевым словом.

6. Зашифровать и расшифровать сообщение методом таблиц Трисемуса.

7. Зашифровать и расшифровать сообщение с помощью биграммного шифра Плейфейра.

8. Зашифровать и расшифровать сообщение с помощью метода полибианского квадрата.

9. Зашифровать и расшифровать сообщение по методу простых шифрующих таблиц.

10. Зашифровать и расшифровать сообщение по методу шифрующих таблиц с одиночной перестановкой по ключу.

11. Зашифровать и расшифровать сообщение по методу шифрующих таблиц с двойной перестановкой по ключу.

12. Зашифровать и расшифровать сообщение по методу магических квадратов.

13. Найти числовую часть ключа для метода шифрования Цезаря с ключевым словом при известном ключевом слове по фрагменту открытого текста (10 символов), расположенному в неизвестном месте текста.

14. Найти ключ аффинной системы подстановок Цезаря по известному фрагменту открытого текста (10 символов), расположенному в конце сообщения.

15. Найти одну из частей числового ключа аффинной системы подстановок Цезаря по известному фрагменту открытого текста (10 символов), расположение которого неизвестно.

16. Найти ключевое слово для метода шифрующих таблиц Трисемуса по известному фрагменту открытого текста, расположенному в начале сообщения. Размер таблицы считать известным.

17. Найти параметры шифрующей таблицы Трисемуса по известному фрагменту открытого текста, расположенному в середине сообщения. Ключевое слово таблицы считать известным.

18. Найти параметры шифрующей таблицы в биграммном шифре Плейфейра по известному фрагменту открытого текста, расположенному в начале сообщения. Ключевое слово таблицы считать известным.

19. Найти параметры шифрующей таблицы в биграммном шифре Плейфейра по известному фрагменту открытого текста, расположенному в начале сообщения. Ключевое слово таблицы считать известным.

20. Найти ключевое слово шифрующей таблицы для биграммного шифра Плейфейра по известному фрагменту открытого текста, расположенному в начале сообщения. Размер таблицы считать известным.

21. Найти ключ метода «скитала» по известному открытому тексту.

22. Найти ключ метода простых шифрующих таблиц по известному фрагменту открытого текста, расположенному в середине сообщения.

23. Найти ключевое слово метода шифрующих таблиц с одиночной перестановкой по ключу. Считать известными: открытый текст сообщения и размер таблицы.

24. Найти размер таблицы для метода шифрующих таблиц с одиночной перестановкой по ключу. Считать известными: открытый текст сообщения и ключевое слово.

25. Найти ключевое слово, определяющее перестановку по столбцам для метода шифрующих таблиц с двойной перестановкой по ключу. Считать известными: открытый текст сообщения и второе ключевое слово.

26. Найти ключевое слово, определяющее перестановку по строкам для метода шифрующих таблиц с двойной перестановкой по ключу. Считать известными: открытый текст сообщения и второе ключевое слово.

Дата добавления: 2015-07-08