Где взять ключи?

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

Где взять ключи?

Каким должен быть ключ шифрования? Случайным и равновероятным. А как получить случайную и равновероятную последовательность символов? Правильно, с помощью генератора случайных чисел. Написать свой генератор ``случайных'' чисел очень просто. Хорошие по статистическим свойствам последовательности получаются по формуле линейного конгруэнтного метода:

$\begin{displaymath} r_{n+1} = (ar_n + b) \mod{m}, \end{displaymath}$

где

-й член псевдослучайной последовательности;

- некоторые целые числа.

Качество псевдослучайной последовательности зависит от выбора чисел , и . Эти числа обязательно должны быть взаимно просты. Есть и другие правила выбора этих коэффициентов, о них можно прочитать в [1]. В Diskreet, например, используется следующий генератор псевдослучайной последовательности:

$\begin{displaymath} r_{n+1}= (214013r_n + 2531011) \mod{2^{32}}. \end{displaymath}$

Как видите, формула для получения очередного ``случайного'' числа рекурсивна - каждый член последовательности зависит от предыдущего. Возникает вопрос: откуда берется первый член? Обычно в качестве берут текущее время с точностью до тика таймера (0,054945 сек.). Если для генерации ключа используется линейный конгруэнтный метод, ключом является последовательность чисел $(r_1, r_2,\dots,r_N)$ , где

$\begin{displaymath} N= \frac{\text{(длина ключа)}}{\text{(длина $r_i$ в байтах)}}. \end{displaymath}$

Предположим, что с помощью линейного конгруэнтного метода сгенерирована последовательность $(r_1, r_2, \dots, r_{128})$ , где каждое есть короткое целое число (16 бит). Созданный ключ представляет собой случайную равновероятную последовательность длиной 256 байт. Оценим, сколько различных вариантов ключа можно получить по данной схеме.

Зафиксируем значение . Какие значения может принимать ? Только одно значение. Если фиксировано, то значение определено однозначно:

$\begin{displaymath} r_2 = (ar_1 + b) \mod{m}. \end{displaymath}$

Значение тоже определено однозначно. Оно равно

$\begin{displaymath} r_3 = (ar_2 + b) \mod{m}= (a ((ar_1 + b) \mod{m}) + b) \mod{m}. \end{displaymath}$

Таким образом, значение однозначно определяет значения всех следующих членов последовательности. Получается, что различных последовательностей $(r_1, r_2,\dots,r_{128})$ в точности столько же, сколько различных значений . В нашем примере - короткое целое число, принимающее значения от 0 до $2^{16}-1=65535$ . Оказывается, что стойкость ключевой системы (число различных вариантов ключа) равна не $2^{256}$ , а всего лишь $2^{16}$ , что в $1{,}77 \cdot10^{72}$ раз меньше!

Получается, что псевдослучайные последовательности в качестве ключей использовать нельзя. А что можно?

В чем слабость псевдослучайных последовательностей? В том, что они псевдослучайны. Первый член последовательности однозначно определяет остальные. Чтобы ключ был по-настоящему случайным и равновероятным, последовательность должна быть не псевдослучайной, а истинно случайной.

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