Отправьте статью сегодня! Журнал выйдет 26 июля, печатный экземпляр отправим 30 июля
Опубликовать статью

Молодой учёный

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

4. Информатика
31.10.2019
202
Поделиться
Библиографическое описание
Гусаров, А. В. Программные генераторы псевдослучайных двоичных последовательностей / А. В. Гусаров, Н. А. Хачикова. — Текст : непосредственный // Исследования молодых ученых : материалы IV Междунар. науч. конф. (г. Казань, ноябрь 2019 г.). — Казань : Молодой ученый, 2019. — С. 3-5. — URL: https://moluch.ru/conf/stud/archive/350/15392/.


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

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

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

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

Таблица 1

Алгоритм

Достоинства

Недостатки

Алгоритм Блюма — Блюма — Шуба [4]

Высокая стойкость

Невысокая скорость

Нельзя предсказать ни предыдущий, ни следующий бит последовательности

Операции с целыми числами являются наиболее ресурсоемкими и сложными

Вихрь Мерсенна [5]

Малый период и предсказуемость

Не является криптостойким

Легко выявляемые статистические закономерности

ГОСТ Р 34.11–94 [6]

На данный момент нахождение коллизий практически не реализуемо

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

Вычисляется примерно в 2 раза медленнее ГОСТ Р 34.11–2012 на современных процессорах

ГОСТ Р 34.11–2012 [7]

Высокая криптостойкость

В системах с ограниченными аппаратными ресурсами вычисление хэш-функции производится медленно

ГОСТ 28147–89 [8]

Бесперспективность атаки полным перебором

Наличие «слабых» ключей

Эффективность реализации и высокое быстродействие на современных компьютерах

ANSI X9.17 [9]

Высокая стойкость

Малая длина генерируемой последовательности

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

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

(1)

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

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

Далее необходимо проверить выполнение условия браковки

Kкр < Kmax. (2)

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

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

Таблица 2

Алгоритм

Условие браковки Kкр < Kmax

Nбр., шт.

Блюма — Блюма — Шуба [4]

Выполнялось

8

Вихрь Мерсенна [5]

Выполнялось

3

ГОСТ Р 34.11–94 [6]

Выполнялось

2

ГОСТ Р 34.11–2012 [7]

Выполнялось

2

ГОСТ 28147–89 [8]

Выполнялось

1

ANSI X9.17 [9]

Выполнялось

1

Анализ табл. 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).
Можно быстро и просто опубликовать свою научную статью в журнале «Молодой Ученый». Сразу предоставляем препринт и справку о публикации.
Опубликовать статью
Ключевые слова
псевдослучайные двоичные последовательности
генераторы псевдослучайных двоичных последовательностей
качество ключей

Молодой учёный