Таким образом, идея, используемая при нахождении длины ключа, заключается в следующем. Многократно запуская генетический алгоритм в предположении, что длина секретного ключа равна l, и каждый раз увеличивая этот параметр на единицу, получаем последовательность c[l], c[l + 1], c[l + 2] и т.д. из "рекордных" значений фитнесс-функции. В этой последовательности обязательно будет присутствовать подпоследовательность, состоящая из элементов, чьи номера образуют арифметическую прогрессию j, j + d, j + 2d и т.д., а сами элементы этой подпоследовательности c[j], c[j + d], c[j + 2d] и т.д. будут заметно отличаться в меньшую сторону от остальных элементов последовательности. Тогда разность прогрессии d окажется в точности равной искомой длине п секретного ключа.
После того, как длина ключа будет найдена, снова запускаем генетический алгоритм. Полученное им решение, соответствующее "рекордному" значению фитнесс-функции, либо окажется искомым секретным ключом, либо будет близко к нему.
Выше был приведен пример исходного текста, который затем зашифровали с помощью ключа математика. Генетический алгоритм был запущен для расшифровки полученного зашифрованного текста с предполагаемой длиной l секретного ключа, равной 4, 5, 6, …, 34, и вычислены соответствующие "рекордные" значения фитнесс-функции с[4], c[5], c[6], …, c[34]. Оказалось, например, что
c[8] = 159.46,
c[9] = 148.49,
c[10] = 42.59 (абсолютный "рекорд"),
c[11] = 148.46,
c[12] = 156.63.
На рисунке хорошо видны "провалы", которые соответствуют "рекордным" значениям фитнесс-функции, полученным для предполагаемых длин l, равных 10, 20 и 30. Поскольку эти числа образуют арифметическую прогрессию с разностью 10, то можно сделать вывод, что искомая длина секретного ключа равна 10.
В. В. Морозенко, Г. О. Елисеев
76
"Рекордные" значения фитнесс-функции для различных предполагаемых длин секретного ключа
генетический алгоритм криптоанализ шифр виженер
Повторная работа генетического алгоритма над тем же зашифрованным текстом, но с уже известной длиной секретного ключа позволила найти ключ математила, который отличается от настоящего секретного ключа только в предпоследней позиции. В результате расшифрования с помощью этого ключа получен следующий текст:
"греция_счановится_ыентром_ресесленно
й_нндустрии_н_орговли.восуществлбется_
переъод_от_пержобытнообщннного".
Полностью расшифровать зашифрованный текст не удалось, поскольку полученный текст не совпадает с исходным. Однако можно заметить, что он очень близок к исходному. В нем можно заметить осмысленные ("греция") или почти осмысленные слова ("ыентром", "нндустрии"). Благодаря наличию таких слов процесс расшифрования полученного текста можно довести до конца "вручную".
При работе алгоритма были выбраны следующие значения основных параметров: численность популяции - 70 особей, количество поколений - 40, вероятность мутации - 0.2, в каждом поколении 50% особей участвовали в скрещивании.
Отметим, что для ускорения работы алгоритма при поиске длины ключа можно использовать популяции с малой численностью и небольшое число поколений, а после нахождения истинной длины ключа n можно повторно применить генетический алгоритм с большими значениями указанных параметров для более точного отыскания секретного ключа.
Заключение
Исследование показало, что предложенный в данной статье генетический алгоритм вполне может быть использован для криптоанализа шифра Виженера, если верно предположение о том, что исходный текст, подвергшийся шифрованию, является осмысленным текстом достаточной длины и обладает среднестатистическим частотным профилем. Такое предположение вполне естественно и почти не сужает область применимости данного алгоритма. Более того, устойчивыми частотными характеристиками обладают все "живые" языки, поэтому алгоритм можно легко адаптировать для расшифрования текстов, написанных, например, на английском или французском языке. Для этого достаточно ввести в алгоритм информацию о среднестатистических частотах биграмм указанных языков.
Предложенный генетический алгоритм далеко не всегда полностью расшифровывает зашифрованное сообщение. Получаемый на выходе алгоритма текст чаще всего отличается от исходного текста, хотя и незначительно. Как правило, расшифрованный текст имеет неточности, которые не бросаются в глаза. При удачном подборе параметров генетический алгоритм показывает вполне хорошие результаты как по скорости сходимости, так и по качеству получаемого решения. Нельзя сказать, что применение описанного генетического алгоритма позволяет полностью автоматизировать процедуру криптоанализа, однако он сводит к минимуму участие человека и его "ручную" работу в этом процессе.
Частным случаем шифра Виженера является шифр Вернама, в котором длина секретного ключа совпадает с длиной исходного текста. К.Шеннон доказал, что шифр Вернама абсолютно надежен [7]. Естественно, что и попытки "взломать" этот шифр с помощью описанного генетического алгоритма окажутся неудачными. Этот факт объясняется тем, что для успешной работы алгоритма необходимо, чтобы длина зашифрованного текста многократно превосходила длину секретного ключа. В ситуации с шифром Вернама это условие, очевидно, не выполняется.
Список литературы
Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: учебн. пос. М.: Гелиос АРВ, 2001.
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Изд-во Триумф, 2002.
Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / под ред. В.М.Курейчика. М.: Физматлит, 2006.
Delman B. GeneticAlgorithms in Cryptography // A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Engineering. New York, 2004.
Городилов А.Ю. Криптоанализ перестановочного шифра с помощью генетического алгоритма // Вестн. Перм. ун-та. Пермь, 2007. Вып. 7(12). С.44-49.
Jakobsen T. A Fast Method for the Cryptanalysis of Substitution Ciphers. 1995.
Шеннон К. Теория связи в секретных системах // Работы по теории информации и кибернетике. М.: ИЛ, 1963.