Интернет магазин китайских планшетных компьютеров

Компьютеры - Криптографически стойкий генератор псевдослучайных чисел - Реализации

Рассмотрим три класса реализации КСГПСЧ:

1. На основе криптографических алгоритмов
2. На основе вычислительно сложных математических задач
3. Специальные реализации

В последних часто используются дополнительные источники энтропии, поэтому, строго говоря, они не являются «чистыми» генераторами, так как их выход не полностью определяется исходным состоянием. Это позволяет дополнительно защититься от атак, направленных на определение исходного состояния.

Реализации на основе криптографических алгоритмов

• Безопасный блочный шифр можно преобразовать в КСГПСЧ запустив его в режиме счетчика. Таким образом, выбрав случайный ключ, можно получать следующий случайный блок применяя алгоритм к последовательным натуральным числам. Счет можно начинать с произвольного натурального числа. Очевидно, что периодом будет не больше чем 2 для n-битного блочного шифра. Также очевидно, что безопасность такой схемы полностью зависит от секретности ключа.

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

• Большинство потоковых шифров работают на основе генерации псевдослучайного потока бит, которые некоторым образом комбинируется с битами открытого текста. Запуск такого шифра на последовательности натуральных чисел даст новую псевдослучайную последовательность, возможно, даже с более длинным периодом. Такой метод безопасен только если в самом потоковом шифре используется надежный КСГПСЧ. Опять же, начальное состояние счетчика должно оставаться секретным.

Реализации на основе математических задач

• Алгоритм Блюма — Блюма — Шуба имеет высокую криптостойкость, основанную на предполагаемой сложности факторизации целых чисел. Однако, этот алгоритм отличается очень медленной работой.
• Алгоритм Блюма-Микали основан на задаче дискретного логарифма.

Специальные реализации

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

• Алгоритм Ярроу который пытается определить энтропию входных данных. Он используется в FreeBSD, OpenBSD и Mac OS X
• Алгоритм Fortuna, наследник алгоритма Ярроу.
• Специальный файл ОС UNIX /dev/random, в частности, /dev/urandom, реализованный в Linux.
• Функция CryptGenRandom предоставленная в CryptoAPI компании Microsoft