ЗАРОЖДЕНИЕ КРИПТОГРАФИИ

       

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


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


где  - -й член псевдослучайной последовательности; , ,  - некоторые целые числа.

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

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

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

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

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

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

в точности столько же, сколько различных значений . В нашем примере  - короткое целое число, принимающее значения от 0 до

. Оказывается, что стойкость ключевой системы (число различных вариантов ключа) равна не , а всего лишь , что в раз меньше!

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

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

Next: Где взять истинно случайную

Up: 6.3. Как зашифровать файл?

Previous: А можно ли обойтись

Contents:



Содержание раздела