Разделение и ранжирование гласных в русских текстах для задач криптоанализа

Эта работа была выполнена при обучении студентов криптоанализу. Курс включает изучение статистики (русских зашифрованных) текстов. Цель тренинга-научиться извлекать избыточную информацию из текста и расшифровывать криптограмму без пароля. Одним из наиболее удобных для обучения является простой метод замещения и аналогичные системы шифрования, которые представлены в большинстве курсов криптографии. В статье представлен метод автоматического разделения гласных и согласных в русских текстах, который освобождает часть избыточности шифротекста. Кроме того, этот метод значительно облегчает задачу расшифровки некоторых других симметричных шифров, которые могут быть сведены к простой подстановке.

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

Целью работы является разработка автоматического метода разделения гласных и согласных в русских текстах, зашифрованных простой подстановкой и сводящихся к ней систем шифрования и выявление свойств и характеристик этого метода. Согласно теории Шеннона, для однозначной расшифровки текста требуется, чтобы его избыточность была больше, чем энтропия пароля. После разделения гласных и согласных избыточность текста возрастает до одного бита на символ, что позволяет вскрывать более короткие зашифрованные тексты. Кроме того, разделение гласных и согласных значительно облегчает задачу вскрытия некоторых шифров. Например, вскрытие самого известного способа шифрования – метода подстановок, требует выбора одного из N! возможных паролей (здесь N – количество букв алфавита). Для русского языка это составляет 33! или примерно 2 в 123 степени вариантов. После разделения гласных и согласных потребуется выбор из 10!*23!, или около 2 в 96 степени вариантов. Число вариантов пароля сокращается примерно в сто миллионов раз, и это существенно упрощает криптоанализ.

Программа, реализующая этот метод, сначала создает матрицу вероятностей биграмм текста.

Для этой матрицы выполняется расчет критерия Маркова, определенного как разность условных вероятностей биграмм типов гласная-согласная и гласная-гласная. Разработана программа, реализующая этот алгоритм. Для текста, использующего алфавит из N символов программа находит подмножество из k «гласных». Это подмножество, максимизирующее критерий, определяется полным перебором всевозможных сочетаний из N по k символов. Порядок появления новых «гласных» при k = 1, 2, 3. . . характеризует их «силу» по убыванию и может быть использован для разделения гласных и согласных, а при достаточном объеме текста – и для приближенного ранжирования гласных. Можно достигнуть более точного ранжирования, если в качестве меры «силы» символа использовать не очередность появления «гласных» в подмножестве других «гласных», а приращение величины критерия Маркова при появлении данной буквы Работу данного алгоритма можно существенно ускорить, используя методы быстрого спуска. Испытание программы выявило независимость критерия Маркова от автора текста, а также его унимодальность для достаточно длинных текстов. Используя этот критерий, алгоритм сохраняет работоспособность при разделении гласных и согласных для коротких (до 100 символов) текстов и при ранжировании гласных для текстов размером 250–500 букв и более. Впервые замечено сходство статистики биграмм гласных букв и символов «Ь» и «Ъ», которые неотделимы данным методом от обычных гласных. Результаты испытаний показали, что данный метод можно эффективно использовать при криптоанализа коротких русских текстов, а также текстов других консонантных языков. 

1. Марков А.А. Исследование замечательного случая зависимых испытаний // Известия Императорской академии наук. Серия 6. 1907. Т. 1. Вып. 3 С. 61-80.

2. Марков А.А. Пример статистическаго изследованiя над текстом «Евгенiя Онегина», иллюстрирующiй связь испытанiй в цепь» // Известия Императорской Академии Наук. VI серiя. 1913. Т. 7. Вып. 3. С. 153–162.

3. Шеннон К. Теория связи в секретных системах. В кн.: Работы по теории информации и кибернетике. М.: ИЛ, 1963.

4. Friedman W. F.,Callimahos D. Military cryptanalysis. Aegean Park Press, Laguna Hills CA, 1985. Part I. Vol. 2.

5. Moler C., Morrison D. Singular Value Analysis of Cryptograms. The American Mathematical Monthly. 1983. Vol. 90. № 2. P. 78–87.

6. Kahn D. The codebreakers. The story of secret writing. Macmillan, N.Y., 1967.

7. Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии. М.: Гелиос АРВ, 2002.

8. Sikora T.F. Field Manual 34-40-2, Basic Cryptanalysts. USA, Washington, DC, 13 September 1990.

9. Пушкин А.С. Евгений Онегин, М.: Эксмо, 2017. 10. Яглом А.М. Яглом И.М. Вероятность и информация. М.: Наука, 1973.

10. Конан Дойль А., Приключения Шерлока Холмса. Пляшущие человечки. М.: АСТ, 2016.

11. Пиотровский Р.Г., К.Б. Бектаев, А.А. Пиотровская. Математическая лингвистика. М.: Высшая школа. 1977. С. 383.

12. Машинный фонд русского языка. URL: http//cfrl.ruslang.ru.

13. Пушкин А.С. Капитанская дочка. М.: Эксмо, 2015. С. 1–640.

14. Аксаков С.Т. Детские годы Багрова-внука. М.: АСТ, 2017. С. 1–416.

15. Куприн А.И. Поединок. М.: Эксмо, 2013. С. 1–640.

16. Тургенев И.С. Дворянское гнездо. М.: АСТ, 2017. С. 384

17. Лермонтов М.Ю. Герой нашего времени. М.: АСТ, 2015. С. 1-285.

18. Чехов А.П. Цветы запоздалые. А. П. Чехов. Полное собрание сочинений и писем в 30-ти томах. Сочинения. М.: Наука, 1983. Том 1.

19. Шукшин В.М. Киноповести. М., 1988. C. 115.