К.т.н., с.н.с., доцент
Тел. 8-926-237-3501
Cand. Sci. (Engineering), Senior researcher, Associate Professor
Tel.: 8-926-237-3501
Эта работа была выполнена при обучении студентов криптоанализу. Курс включает изучение статистики (русских зашифрованных) текстов. Цель тренинга-научиться извлекать избыточную информацию из текста и расшифровывать криптограмму без пароля. Одним из наиболее удобных для обучения является простой метод замещения и аналогичные системы шифрования, которые представлены в большинстве курсов криптографии. В статье представлен метод автоматического разделения гласных и согласных в русских текстах, который освобождает часть избыточности шифротекста. Кроме того, этот метод значительно облегчает задачу расшифровки некоторых других симметричных шифров, которые могут быть сведены к простой подстановке.
Данная работа подготовлена в процессе обучения студентов навыкам криптографического анализа. В курс обучения входит изучение статистики русских (зашифрованных) текстов. Цель обучения – научиться извлекать избыточную информацию текста и вскрывать шифрограммы при отсутствии пароля. Одним из самых удобных для изучения является метод простой замены, который излагается в большинстве курсов криптографии. В статье рассмотрен метод автоматического метода разделения гласных и согласных в русских текстах, повышающего избыточность зашифрованного текста. Кроме того, данный метод значительно облегчает задачи вскрытия некоторых других симметричных шифров, сводящихся к простой замене.
Целью работы является разработка автоматического метода разделения гласных и согласных в русских текстах, зашифрованных простой подстановкой и сводящихся к ней систем шифрования и выявление свойств и характеристик этого метода. Согласно теории Шеннона, для однозначной расшифровки текста требуется, чтобы его избыточность была больше, чем энтропия пароля. После разделения гласных и согласных избыточность текста возрастает до одного бита на символ, что позволяет вскрывать более короткие зашифрованные тексты. Кроме того, разделение гласных и согласных значительно облегчает задачу вскрытия некоторых шифров. Например, вскрытие самого известного способа шифрования – метода подстановок, требует выбора одного из N! возможных паролей (здесь N – количество букв алфавита). Для русского языка это составляет 33! или примерно 2 в 123 степени вариантов. После разделения гласных и согласных потребуется выбор из 10!*23!, или около 2 в 96 степени вариантов. Число вариантов пароля сокращается примерно в сто миллионов раз, и это существенно упрощает криптоанализ.
Программа, реализующая этот метод, сначала создает матрицу вероятностей биграмм текста.
Для этой матрицы выполняется расчет критерия Маркова, определенного как разность условных вероятностей биграмм типов гласная-согласная и гласная-гласная. Разработана программа, реализующая этот алгоритм. Для текста, использующего алфавит из N символов программа находит подмножество из k «гласных». Это подмножество, максимизирующее критерий, определяется полным перебором всевозможных сочетаний из N по k символов. Порядок появления новых «гласных» при k = 1, 2, 3. . . характеризует их «силу» по убыванию и может быть использован для разделения гласных и согласных, а при достаточном объеме текста – и для приближенного ранжирования гласных. Можно достигнуть более точного ранжирования, если в качестве меры «силы» символа использовать не очередность появления «гласных» в подмножестве других «гласных», а приращение величины критерия Маркова при появлении данной буквы Работу данного алгоритма можно существенно ускорить, используя методы быстрого спуска. Испытание программы выявило независимость критерия Маркова от автора текста, а также его унимодальность для достаточно длинных текстов. Используя этот критерий, алгоритм сохраняет работоспособность при разделении гласных и согласных для коротких (до 100 символов) текстов и при ранжировании гласных для текстов размером 250–500 букв и более. Впервые замечено сходство статистики биграмм гласных букв и символов «Ь» и «Ъ», которые неотделимы данным методом от обычных гласных. Результаты испытаний показали, что данный метод можно эффективно использовать при криптоанализа коротких русских текстов, а также текстов других консонантных языков.
This work was developed while teaching students the cryptanalysis. The course includes the study of statistics of (Russian encrypted) texts. The purpose of training is to learn how to extract redundant information of the text and to descript the cryptogram without a password. One of the most comfortable methods for learning is a simple substitution and similar encryption systems, which are presented in most courses of cryptography. This paper presents a method of automatic separation of vowels and consonants in Russian texts, which releases some of the redundancy of the cipher text. In addition, this method greatly facilitates the task of descript some other symmetric ciphers which may be reduced to simple substitution.
The aim of this work is to develop and implement a method for the automatic selection of vowels in Russian texts, enciphered by a simple substitution and similar encryption systems.
According to the theory of Shannon, for unambiguous decoding of the text you want the redundancy of the text that exceeds the entropy of the password. After the separation of vowels and consonants redundancy of the text increases to one bit per symbol, this allows you to open shorter encrypted texts. Moreover, the separation of vowels and consonants greatly simplifies the cryptanalysis of some ciphers. For instance, cryptanalysis of the most famous encryption method - method of simple substitution-requires selection of one of N! possible passwords (where N is the number of letters in the alphabet). For the Russian language it is 33! or nearly 2 to 123rd degrees of options. After the separation of vowels and consonants you will need a selection of 10!*23!, or nearly 2 to 96th degrees of options. The number of combinations is reduced to one hundred million times, that makes the cryptanalysis much easier. The program that implements this method first creates a matrix of the probabilities of bigrams of the text.
For this matrix Markov criterion calculated, defined as the difference between the conditional probabilities of vowel-consonant and vowelvowel diagram’s types. For an alphabet consisted of N characters the program defines a combination of a given number k of “vowels” by exhaustive search. This combination of k symbols maximizes Markov criterion. The order relation of the new “vowels” for k = 1, 2, 3... characterizes the descending of their “strength” and can be used to separate vowels from consonants. In texts of sufficient volume there are possible approximate ranking of the vowel’s set. A more accurate ranking is possible when as a measure of “symbol power” Markov criterion’s increments are used. The algorithm speed can be greatly accelerated by using some tricks of steepest descent method. The test program discovered the independence of Markov criterion from the text’s author as well as its unimodality for long texts. Using this criterion, the algorithm can separate vowels from consonants for short (up to 100 characters) texts as well as the ranking of vowels for texts as small as 250-500 letters. The similarity of Markov criterion’s statistics of letters “ь”, “ъ” and standard vowels is discovered. These two letters are inseparable by Markov criterion method from the standard vowels. The test results showed that Markov criterion method can be used for cryptanalysis of short Russian texts as well as texts of the other consonant languages.
The authors declare that there are no conflicts of interest present.