8 Глава

8.1Криптоанализ

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

Современная криптография — соревнование методов шифрования и криптоанализа. Криптоанализом (от греческого krypts - "скрытый" и analein - "ослаблять" или избавлять") называют науку восстановления (дешифрования) открытого текста без доступа к ключу. Хотя история криптоанализа насчитывает многие века, особенно интенсивно эта область знаний начала развиваться с наступлением компьютерной эры. Задача криптоанализа состоит в том, чтобы определить вероятность взлома шифра и, таким образом, оценить его применимость в той или иной области.

8.2Классический криптоанализ.

Хотя понятие криптоанализ было введено сравнительно недавно, некоторые методы взлома были изобретены десятки веков назад. Первым известным письменным упоминанием о криптоанализе является «Манускрипт о дешифровке криптографических сообщений», написанный арабским учёным Ал-Кинди ещё в IX веке. В этом научном труде содержится описание метода частотного анализа.

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

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

В период XV-XVI веков в Европе создавались и развивались полиалфавитные шифры замены. Наиболее известным является шифр французского дипломата Блеза де Виженера, в основу которого легло использование последовательности нескольких шифров Цезаря с различными значениями сдвига. На протяжении трёх веков Шифр Виженера считался полностью криптографически устойчивым, пока в 1863 году Фридрих Касиски не предложил свою методику взлома этого шифра. Основная идея метода Касиски заключается в следующем: если в открытом тексте между двумя одинаковыми наборами символов находится такой блок текста, что его длина кратна длине ключевого слова, то эти одинаковые наборы символов открытого текста при шифровании перейдут в одинаковые отрезки шифротекста. На практике это означает то, что при наличии в шифротексте одинаковых отрезков длиной в три и больше символов, велика вероятность того, что эти отрезки соответствуют одинаковым отрезкам открытого текста. Как применяется метод Касиски: в шифротексте ищутся пары одинаковых отрезков длины три или больше, затем вычисляется расстояние между ними, то есть количество символов, разделяющих стартовые позиции парных отрезков. В результате анализа всех пар одинаковых отрезков мы получим совокупность расстояний d₁, d₂, d₃,… Очевидно, что длина ключевого слова будет делителем для каждого из расстояний и, следовательно, для их наибольшего общего делителя.

Следующий этап развития криптоанализа связан с изобретением роторных шифровальных машин таких как, например, изобретённая Артуром Шербиусом Энигма. Целью таких устройств было минимизировать количество повторяющихся отрезков шифротекста, статистика появления которых использовалась при взломе шифра Виженера.