Современные информационные технологии/4. Информационная безопасность

Овчаренко М.А.

Национальный горный университет, Украина

Генераторы случайных чисел

Во многих криптографических алгоритмах, например в системах с открытым ключом, используются случайные числа. Для получения таких чисел можно использовать аппаратные средства – датчики случайных чисел. Аппаратные генераторы случайных чисел основываются на разных нелинейных процессах в электронных схемах, основанных на транзисторах или диодах. Такой генератор может быть реализован в виде отдельной микросхемы или быть интегрирован в сам процессор, практически все аппаратные криптопроцессоры содержат встроенные генераторы.

Говоря о стойкости серии случайных чисел, подразумевают, что:

· нет аналитической зависимости между последовательно сгенерированными числами;

· зная предыдущие числа, криптоаналитик не может найти следующие число х (атака из прошлого);

· зная последующие числа, нельзя установить предшествующие (атака из будущего);

· вероятность появления любого числа в последовательности одинаковая.

Генераторы случайных чисел делятся на:

· физические;

· табличные.

1. Физические (аппаратные) генераторы случайных чисел.

Наиболее перспективными являются физические (аппаратные) генераторы случайных чисел. Аппаратный генератор случайных чисел — устройство, которое генерирует последовательности случайных чисел на основе измеряемых параметров протекающего физического процесса.

В качестве генераторы шума используют шумящее тепловое устройство, например транзистор. Существуют генераторы случайных чисел, использующие различные физические процессы, такие как радиоактивный распад, шумы аналоговых сетей, космическое излучение. Примером может быть генератор случайных чисел с использованием полупроводникового лазера с короткими и резкими пиками интенсивности. Лазер пропускается через среду с обратной связью с задержкой, то есть интенсивность излучения на выходе определяется интенсивностью сигнала на входе и состоянием среды, которое зависит от интенсивности на выходе. Известно, что интенсивность подобного луча является процессом квазипериодическим, то есть с течением времени почти повторяется, поэтому напрямую использовать его в качестве генератора случайных чисел нельзя. Для того, чтобы избавиться от квазипериодичности интенсивность луча замеряется примерно 2,5 миллиарда раз в секунду. Результат каждого измерения записывается в строку длиной в 8 бит. Оно вычитается из значения предыдущего измерения, а результат усекается. Таким образом удается избавиться от квазипериодичности и добиться генерации случайного потока нулей и единиц со скоростью примерно 12,5 Гигабит в секунду.

2. Табличные генераторы случайных чисел.

Случайное число в заданном интервале (например, от 0 до 1) формируется из случайных цифр, записанных в таблице.

таблица число

3 5 2 0.352

7 4 1 0.741

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

К генераторам псевдослучайных чисел относят алгоритмические генераторы случайных чисел.

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

Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдослучайных бит, а также различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или зерном (англ. seed), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

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

В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются RC4, ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюма, Блюма и Шуба, а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.

Литература:

1. И.М. Белова «Компьютерное моделирование» — М.: МГИУ, 2007. — 81 c.

2. http://prostonauka.com/lazernyj-generator-sluchajnyh-chisel

3. http://ru.wikipedia.org/wiki/Случайное_число