49783156431138-я попытка

Next: 6.3. Как зашифровать файл? Up: 6.2. Немного теории Previous: Удобно ли носить большую Contents: Содержание

49783156431138-я попытка

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

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

$\begin{displaymath} \sum_{i=1}^{\infty}\frac{i}{2^i}. \end{displaymath}$

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

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

$\begin{displaymath} \sum_{i=1}^{n}\frac{ik_i}{n!}, \end{displaymath}$

где

- число различных упорядочений множества из

ключей, у которых истинный ключ стоит на месте с номером

. Так как легко подсчитать, что

, то наша сумма равна

$\begin{displaymath} \sum_{i=1}^{n}\frac{ik_i}{n!}=\sum_{i=1}^{n}\frac{i}{n} = \frac{n(n+1)}{2n}=\frac{(n+1)}{2}. \end{displaymath}$

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

Теперь вернемся от математики к суровой действительности. Пусть вы написали великолепную программу, которая проверяет за одну секунду один миллион вариантов ключа. Тогда за час программа переберет 3600000000 ключей, за сутки - 86400000000 ключей, а за год - более 30000000000000. Короче, для перебора $2^{56}$ ключей шифратора DES вашей программе потребуется в среднем чуть более 1500 лет. Вдохновляющий результат, не правда ли? А теперь подсчитайте, сколько лет потребуется вашей программе для нахождения неизвестного ключа у отечественного алгоритма шифрования ГОСТ 28147, в котором число ключей равно $2^{256}$ .

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

А теперь перейдем к решению практических вопросов.

Next: 6.3. Как зашифровать файл? Up: 6.2. Немного теории Previous: Удобно ли носить большую Contents: Содержание