Введение в криптографию



         

-Я попытка


Теперь встанем на сторону нападающей стороны и попробуем написать программу для нахождения неизвестного ключа. Пусть у вас есть исходный и закрытый файлы. Если это не так, то надо постараться получить хотя бы общее представление о том, что представляет собой исходный файл: исполняемый код, текст программы на каком-либо языке программирования, текст в кодировке ASCII, ANSI, KOI-8 и т.п. Если даже это неизвестно, то возможность определен ия правильного ключа зачастую вообще становится проблематичной. Но не будем о грустном. Пусть у вас есть оба файла. Воспользуемся написанной ранее программой шифрования и добавим к ней блоки генерации ключей и сравнения полученного зашифрованного текста с имеющимся открытым. Прежде чем запустить на исполнение программу, подумаем, сколько времени она может работать.

Сначала найдем среднее число знаков текста, которое требуется для отбраковки случайного ключа. Предположим, что наша программа последовательно сравнивает биты текста, полученного шифрованием с помощью случайно выбранного ключа, с битами имеющегося закрытого файла. Если реализованный в программе шифр обладает хорошими свойствами и дает , похожий на случайную последовательность, то по первому биту будет забракована приблизительно половина ключей, по второму - еще четверть, и т.д. В итоге мы получим, что среднее число знаков для отбраковки оценивается бесконечной суммой

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

Данный результат обнадеживает своей неожиданностью. Поэтому сразу переходим ко второй части задачи и найдем, сколько потребуется в среднем перебрать вариантов ключа до появления искомого. Считаем, что все ключи равноправны. Перенумеруем их и начнем по очереди проверять с помощью нашей программы. На первый взгляд кажется, что от выбора порядка нумерации ключей зависит очень много. Действительно, если у вас есть дар предвидения и вы выбрали такой порядок, что искомый ключ имеет первый номер, то программа сработает уже на первом шаге. Но не будем верить в чудо и найдем среднее число шагов для случайно выбранного порядка. Оно равно




Содержание  Назад  Вперед