Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Генерация случайных чисел в криптографии: зачем и как

На главную Математический раздел Криптография и т.д. Новости

Генерация случайных чисел слишком важна,
чтобы оставлять её на волю случая
(Р. Кавью)

Случайные числа требуются в криптографии очень часто. Симметричный ключ шифрования должен выбираться случайным образом. При генерации ключей для асимметричной криптосистемы необходимо иметь достаточно большой объем случайных данных. Корректная реализация асимметричных криптоалгоритмов, например RSA, требует добавлять к каждой порции открытого текста несколько случайных байт. Из того, о чём идёт речь на данном сайте, явно просятся случайные величины в шифре Вернама и гаммировании.
В компьютере, в общем случае, нет хорошего источника случайности, способного выдавать значительные объемы истинно случайных данных. Поэтому в криптографии находят широкое применение так называемые генераторы псевдослучайных чисел (ГПСЧ).

1. Генераторы псевдослучайных чисел: характеристики, требования

ГПСЧ не являются истинно случайными, поскольку генерируют последовательность чисел по некоторому алгоритму.

Основные характеристики алгоритма псевдослучайной генерации: начальное значение и период.

Начальное значение требуется по той причине, что обычно следующие числа зависят от предыдущих (рекуррентные соотношения). Вспомните: в любом адекватном рекуррентном соотношении есть некое граничное условие, например, если факториал представлять как n! = n * (n-1)!, то 0! = 1 - граничное условие. Другое пример - числа Фибоначчи: f(0) = f(1) = 1 - граничное условие, f(n) = f(n - 1) + f(n - 2) - рекуррентное соотношение. Каждый запросто может придумать другие - самопальные - рекуррентные соотношения...

Период - наименьшее T такое, что гарантированно X(i) = X(i + T), где i - целое неотрицательное (ведём нумерацию элементов последовательности с нуля), X(i) - i-ый член последовательности. Иначе говоря, псевдослучайная последовательность представляет собой серию повторяющихся групп из T чисел. Например, {2, 3, 0, 1, 2, 3, 0, 1, 2, ...} - здесь период T = 4, начальное значение X(0) = 2.

Зная алгоритм ГПСЧ и начальное значение, легко восстановить любое число X(i).

А теперь сформулируем требования, по которым в криптографии создаются ГПСЧ:

1. Псевдослучайная последовательность, выдаваемая ГПСЧ, должна иметь как можно больший период. Чем секретнее данные, тем больший период желательно иметь.
2. Зная любой фрагмент последовательности, выдаваемой генератором, злоумышленник не должен иметь эффективной возможности найти начальное значение, загруженное в генератор.
3. Зная любой фрагмент последовательности, выдаваемой генератором, злоумышленник не должен иметь возможности получить достоверную информацию о предыдущих или последующих элементах последовательности.
4. Ну и, разумеется, хотелось бы повыше скорость работы генератора. К сожалению, это несколько противоречит тому, что требуется как можно более высокая защищённость.

Требования 2 и 3 можно считать требованиями непредсказуемости.

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

Далее рассмотрим парочку примеров ГПСЧ.

2. Линейный конгруэнтный генератор

Просьба не бояться страшного названия, генератор его не оправдывает.

Имеется начальное значение X(0), i-ое число задаётся как X(i) = (A * X(i - 1) + C) mod M, где A - множитель, C - приращение, M - модуль.
В лучшем случае период T = M. Основная сложность в том, чтобы подобрать как раз такие A, C, M.
M обычно берётся как степень двойки либо простое число (то есть делящееся без остатка только на 1 и само себя). Большие простые числа можно получить по формуле так называемых чисел Мерсенна:

Здесь p - некоторое натуральное число. Если p не является простым числом, то и соответствующее число Мерсенна не является простым числом. Но даже если p - простое число, не факт, что число Мерсенна будет простым. Первые 10 значений p, которые можно подставлять в формулу чисел Мерсенна, чтобы получить простое число: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89. А вот если подставить, скажем, p = 11, то получим 2047 = 23 * 89, то есть это число Мерсенна не является простым числом.

Рекомендуется брать A нечётным, а C - взаимно простым с M.

Пример условий, подходящих под рекомендацию: A = 5, C = 3, M = 64. Такие условия использованы в демонстрации, потому любой желающий легко проверит, что T = M = 64.

Тем не менее приведённые рекомендации тоже не гарантируют результатов. Так, A = 7, C = 3, M = 64 удовлетворяет им, но T = 16.

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

На всякий случай для блондинов и блондинок: начальное значение X(0) выбирается как целое неотрицательное число, меньшее M.

Кроме того, получаемый ГПСЧ строится по довольно простой закономерности. Как вариант сделать её более изощрённой - подавать на выход не сами числа, а результат их циклического сдвига, если M - степень двойки.

Допустим, X(0) = 2, A = 5, C = 3, M = 64. Используем циклический сдвиг бит влево на 2. X(0) = 000010, поэтому на выход подаём Y(0) = 001000 = 8. X(1) = (5 * 2 + 3) mod 64 = 13 = 001101, тогда Y(1) = 110100 = 52. X(2) = (5 * 13 + 3) mod 64 = 4 = 000100, то есть Y(2) = 010000 = 16. X(3) = (5 * 4 + 3) mod 64 = 23 = 010111. Y(3) = 011101 = 29 и т.д. Вместо 2, 13, 4, 23, ... на выходе 8, 52, 16, 29, ... Обратите внимание при изучении демонстрации - в оригинальном варианте ГПСЧ чередуются чётные и нечётные числа, в усовершенствованном эта закономерность "убита".

3. BBS-генератор

Данный генератор основан на формуле

Число m должно быть произведением двух больших простых чисел p и q, при этом p mod 4 = 3, q mod 4 = 3.
Иначе говоря, p + 1 и q + 1 должны делиться на 4 без остатка. Приведённая в пункте 2 супер-пупер-формула для простых чисел здесь тоже пригодится. Приведём весьма боевой пример:

BBS-генератор имеет более высокую криптографическую стойкость, чем выше рассмотренный конкурент. Но и реализация его сложнее.

ДЕМОНСТРАЦИЯ

Линейный генератор псевдослучайных чисел: Кнопка ОРИГИНАЛ: X(i + 1) = (5 * X(i) + 3) mod 64, i = 0...62, X(0) = 2; Усовершенствованный: та же формула, но выводятся не сами X(i), а результат циклического сдвига бит влево на 2. Полагается, что для хранения каждого числа используется 6 бит.

Если что-то непонятно, ещё раз вернитесь к описанию генератора.

copyright © Исканцев Н.В., 2011

На главную
X