Программные генераторы псевдослучайных двоичных последовательностей

Псевдослучайные двоичные последовательности применяются в системах сбора и обработки информации. Такие последовательности перед применением требует проверки их качества. Это предъявляет высокие требования к генераторам псевдослучайных последовательностей. Темой данной работы является изучение свойств наиболее известных программных генераторов псевдослучайных двоичных последовательностей.

Ключевые слова: псевдослучайные двоичные последовательности, генераторы псевдослучайных двоичных последовательностей, качество ключей.

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

С целью проверки качества последовательностей, сформированных различными генераторами псевдослучайных чисел, был проведен анализ двоичных последовательностей, сформированных генераторами, реализованными на основе различных алгоритмов. В табл. 1 приведены достоинства и недостатки современных алгоритмов генерации псевдослучайных чисел. Для оценки случайности сгенерированных ключевых последовательностей используется методика, предложенная в [3].

Таблица 1

В табл. 2 приведены результаты анализа алгоритмов генерации двоичных последовательностей, приведенных в табл. 1, на основании одного лишь критерия, приведенного в [3], а именно — максимальное число нулей или единиц K_max в самой длинной серии не должно превышать критического значения K_кр. Невыполнение этого критерия приводит к браку сгенерированной двоичной последовательности.

Критическое значение числа нулей (единиц) в самой длинной серии K_кр при уровне значимости , равном 0,05, определяем по формуле [3]

(1)

где n — общее количество единиц и нулей в ключе; n = 64.

Подставив значение n = 64 в (1), после округления до целого числа в большую сторону получаем, что K_кр = 10.

K_кр < K_max. (2)

При невыполнении этого условия двоичная последовательность бракуется независимо от того, были выполнены другие условия браковки, или нет.

Количество забракованных последовательностей N_бр. в табл. 2 определялось из условия (2) в выборке из 100 двоичных последовательностей, сгенерированных при помощи алгоритма, указанного в текущей строке таблицы.

Таблица 2

Анализ табл. 2 позволяет предположить, что наиболее качественные ключи генерируются при использовании алгоритмов генерации в соответствии с ГОСТ 28147–89 [8] и ANSI X9.17 [9].

Проверка ключей по полной методике, изложенной в [3] показала, что из 100 сгенерированных ключей некачественными оказываются 15–20 %, что соответствует результатам, приведенным в табл. 2 и является довольно большой величиной. Поэтому дальнейшие исследования будут направлены на формирование генератора, позволяющего улучшить эти показатели. Предполагается совместно использовать генераторы ГОСТ 28147–89 [8] и ANSI X9.17 [9], однако следует проверить и другие варианты реализации, например ГОСТ Р 34.11–94 [6] и ГОСТ 28147–89 [8], ГОСТ Р 34.11–2012 [7] и ГОСТ 28147–89 [8], а также ГОСТ Р 34.11–94 [6] и ANSI X9.17 [9], ГОСТ Р 34.11–2012 [7] и

ANSI X9.17 [9]. Алгоритм ANSI X9.17 [9] следует использовать в тех случаях, когда достаточно сгенерировать последовательность длиной не более 64 бит, например для синхропосылки длиной 64 бита.

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

Литература:

1. Иванов М. А., Чугунков И. В. Теория, применение и оценка качества генераторов псевдослучайных чисел. М.: “КУДИЦ-ОБРАЗ”, 2003. — 240 с.
2. ГОСТ Р 34.12–2018 Информационная технология. Криптографическая защита информации. Блочные шифры. Введен 01.06.2019 [Электронный ресурс] URL: http://docs.cntd.ru/document/1200161708 (дата обращения 26.10.2019).
3. Гусаров А. В., Гусарова Н. И. Об одном способе оценки параметров криптографических ключей // Информационные системы и технологии, 2013, № 1. С. 124–128.
4. Алгоритм Блюма — Блюма — Шуба. Словари и энциклопедии на Академике. Википедия[Электронный ресурс] URL: https://dic.academic.ru/dic.nsf/ruwiki/614129 (дата обращения 26.10.2019).
5. Вихрь Мерсенна. Словари и энциклопедии на Академике.Википедия [Электронный ресурс] URL: https://dic.academic.ru/dic.nsf/ruwiki/88739 (дата обращения 26.10.2019).
6. ГОСТ Р 34.11–89. Информационная технология. Криптографическая защита информации. Функция хэширования.. Введ. 1995–01–01. М.: Ордена «Знак почета» Издательство стандартов, 1994. — 11 с.
7. ГОСТ Р 34.11–2012 Информационная технология. Криптографическая защита информации. Функция хэширования. Введен 2013–01–01. М.: ФГУП СТАНДАРТИНФОРМ, 2013. – 20 с. Прил. на 1 с.
8. ГОСТ 28147–89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. Введ. 1990–07–01. Переиздание. М.: ИПК Издательство стандартов, 1996. — 26 с.
9. Генератор псевдослучайных чисел. [Электронный ресурс] URL: http://ru.wikipedia.org/wiki/Генератор_псевдослучайных_чисел (дата обращения 26.10.2019).