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

Шифр Цезаря и брутфорс

Симметричные шифры предполагают использование одного и того же ключа (в частном случае, привычного пароля) для шифрования и дешифрования сообщений. Простейший симметричный метод – «шифр Цезаря», предполагает сдвиг каждой буквы в исходном сообщении на фиксированное число позиций в алфавите вправо. Значение этого сдвига также является ключом для дешифровки – в этом случае символы в алфавите сдвигаются влево. Например, при сдвиге k=2 слово «МЦКО» будет зашифровано в слово «ОШМР».

Разумеется, стойкость шифра Цезаря оставляет желать лучшего. Его взлом легко осуществить при помощи метода полного перебора, то есть брутфорса (от англ. «brute force» – «грубая сила»). Сколько же вариантов ключей может использоваться в методе Цезаря для русскоязычных текстов? Всего лишь 32 варианта величины сдвига. При сдвиге на 33 позиции текст останется в своём первоначальном виде.

Шифр заменами и частотный метод

Теперь представь, что тебе посчастливилось принять участие в популярной телепередаче «Поле чудес». Какие буквы ты будешь называть первыми в незнакомом слове? Все ли буквы встречаются одинаково часто? Для каждого человеческого языка известно распределение вероятностей букв в нём. Благодаря этому факту, например, возможно автоматическое распознавание языка текста в компьютерных программах.

В статистике доказано, что в больших текстах частоты появления букв близки к их теоретическим вероятностям. В таблице представлены частоты появления букв в романе Л. Н. Толстова «Война и мир». Буква «е» и «ё» считаются вместе.

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

Шифр Цезаря является частным случаем шифра заменами. В общем случае составляется матрица замен (например, буква «А» меняется на «Ю», буква «Б» на букву «Т», буква «Т» на букву «А» и т.д.). По сути, ключом является любая перестановка букв алфавита. Таким образом имеется 33!≈8,68∙10³⁶ ключей, что на практике исключает использование брутфорса для проведения криптоатак.

Кажется, что шифр замен достаточно стойкий. Увы, но нет! Против него криптоаналитики легко применят мощнейший частотный метод. А именно, вычислят распределение частот в зашифрованном тексте и быстро выяснят, какой «реальной» букве соответствует каждая частота буквы зашифрованного текста.

Частотный метод абсолютно бессилен лишь перед идеальным шифром, представляющий собой «белый шум» (все буквы равновероятны и не зависимы). С независимостью появления букв тоже всё печально… ведь помимо анализа распределения букв криптоаналитики изучают распределения морфем. Некоторые морфемы запрещены правилами, вероятность их появления – нуль (например, известные со школы «чя»/«щя» и менее очевидные «жш», «юэ» или «щэх»). Другие же морфемы очень распространены (например, пары «согласная + гласная»).

Частотные словари

Использование в качестве паролей «словарных» слов человеческого языка также имеет большие изъяны. Слов достаточно мало (поэтому их легко перебрать), кроме того, известны законы распределения вероятностей появления слов в текстах. Для каждого языка составлены частотные словари, в которых слова расположены в порядке убывания частоты их употребления. Такими словарями нередко пользуются полиглоты для быстрого изучения нового языка.

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

Как и в случае с буквами, в больших текстах частоты появления слов близки к их теоретическим вероятностям. В романе Л. Н. Толстова «Война и мир» автором используется 14591 уникальное слово в нормальной форме, с учётом повторов – 47463 слова. Топовая пятёрка слов приведена в таблице.

Если исключить предлоги и союзы (и вообще слова короче четырёх букв), то достаточно частыми окажутся различные формы глаголов «быть» (837), «сказать» (537), «говорить» (236), специфическое существительное «князь» (471), имена «Анна» (184), «Пьер» (149) и «Андрей» (138). Подумай, есть ли закономерность в полученных результатах?