Программные генераторы псевдослучайных двоичных последовательностей
Авторы: Гусаров Александр Вячеславович, Хачикова Наталия Алексеевна
Рубрика: 4. Информатика
Опубликовано в
IV международная научная конференция «Исследования молодых ученых» (Казань, ноябрь 2019)
Дата публикации: 31.10.2019
Статья просмотрена: 168 раз
Библиографическое описание:
Гусаров, А. В. Программные генераторы псевдослучайных двоичных последовательностей / А. В. Гусаров, Н. А. Хачикова. — Текст : непосредственный // Исследования молодых ученых : материалы IV Междунар. науч. конф. (г. Казань, ноябрь 2019 г.). — Казань : Молодой ученый, 2019. — С. 3-5. — URL: https://moluch.ru/conf/stud/archive/350/15392/ (дата обращения: 17.08.2024).
Псевдослучайные двоичные последовательности применяются в системах сбора и обработки информации. Такие последовательности перед применением требует проверки их качества. Это предъявляет высокие требования к генераторам псевдослучайных последовательностей. Темой данной работы является изучение свойств наиболее известных программных генераторов псевдослучайных двоичных последовательностей.
Ключевые слова: псевдослучайные двоичные последовательности, генераторы псевдослучайных двоичных последовательностей, качество ключей.
В информационных системах используются псевдослучайные двоичные последовательности. Они применяются в различных областях науки и техники: в системах передачи данных для генерации кодов, обнаруживающих и исправляющих ошибки, в системах самотестирования сверхбольших интегральных схем, в системах защиты информации и пр. Для их генерации обычно используются программные генераторы двоичных последовательностей. Важнейшим требованием, предъявляемым к таким двоичным последовательностям, является случайный характер следования нулевых и единичных битов внутри последовательности. Для оценки случайности следования битов в последовательности используют различные критерии [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 бита.
Приведенные материалы не связаны ни с одной из существующих криптографических систем и носят исследовательский характер.
Литература:
- Иванов М. А., Чугунков И. В. Теория, применение и оценка качества генераторов псевдослучайных чисел. М.: “КУДИЦ-ОБРАЗ”, 2003. — 240 с.
- ГОСТ Р 34.12–2018 Информационная технология. Криптографическая защита информации. Блочные шифры. Введен 01.06.2019 [Электронный ресурс] URL: http://docs.cntd.ru/document/1200161708 (дата обращения 26.10.2019).
- Гусаров А. В., Гусарова Н. И. Об одном способе оценки параметров криптографических ключей // Информационные системы и технологии, 2013, № 1. С. 124–128.
- Алгоритм Блюма — Блюма — Шуба. Словари и энциклопедии на Академике. Википедия[Электронный ресурс] URL: https://dic.academic.ru/dic.nsf/ruwiki/614129 (дата обращения 26.10.2019).
- Вихрь Мерсенна. Словари и энциклопедии на Академике.Википедия [Электронный ресурс] URL: https://dic.academic.ru/dic.nsf/ruwiki/88739 (дата обращения 26.10.2019).
- ГОСТ Р 34.11–89. Информационная технология. Криптографическая защита информации. Функция хэширования.. Введ. 1995–01–01. М.: Ордена «Знак почета» Издательство стандартов, 1994. — 11 с.
- ГОСТ Р 34.11–2012 Информационная технология. Криптографическая защита информации. Функция хэширования. Введен 2013–01–01. М.: ФГУП СТАНДАРТИНФОРМ, 2013. – 20 с. Прил. на 1 с.
- ГОСТ 28147–89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. Введ. 1990–07–01. Переиздание. М.: ИПК Издательство стандартов, 1996. — 26 с.
- Генератор псевдослучайных чисел. [Электронный ресурс] URL: http://ru.wikipedia.org/wiki/Генератор_псевдослучайных_чисел (дата обращения 26.10.2019).
Ключевые слова
качество ключей, псевдослучайные двоичные последовательности, генераторы псевдослучайных двоичных последовательностейПохожие статьи
Лабораторные методы измерения и приборы контроля коррозии
Десятибалльная шкала коррозионной стойкости металлов (ГОСТ 13819–68).
Гравиметрический метод — один из наиболее распространенных методов определения скорости коррозии. Самый простой и доступный способ испытания в электролитах — это испытание в...
Выбор конструкционных материалов для оборудования установки...
Транспортировка неосушенного газа в присутствие сероводорода двуокиси углерода и других агрессивно компонентов нецелесообразна в виду высокой коррозионной агрессивности сыре и соответственно, резкого снижения надёжности эксплуатируемого оборудования и трубопроводов.
Методология сравнения потоковых шифров | Статья в журнале...
Данная статья посвящена методологии сравнения потоковых шифров. В статье рассматриваются потоковые шифры и их основные параметры. На основе этих параметров предлагается методика сравнения данных шифров, а также приводится пример применения данной методики к...
Применение стандарта криптосистем DES для шифрования...
достаточно высокая стойкость алгоритма. Литература.
Рассмотрим режим простой замены для ГОСТ 28147–89. Результат разбивается на восемь 4- битовых последовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания...
Применение стандартов AS 9100 и ГОСТ Р EN 9100–2011 для...
Отрасли промышленности, такие как авиационная, космическая и оборонная являются наукоемкими и специфичными отраслями с высокими рисками, связанными с качеством производимой продукции.
Роль ускоренных испытаний в определении надежности...
Элементная база современных радиоэлектронных изделий состоит из высокоинтегрированных компонентов (интегральных схем, печатных плат). В связи с тем, что разработчики компонентов более высокой интеграции ИС делают разработку под общие для ряда предприятий...
Оценка механических свойств металла по твердости при...
Проведен анализ основных неразрушающих методов контроля твердости металла, наиболее часто применяемых для косвенного определения механических свойств (σв, σ0,2) элементов газопроводов в эксплуатационных условиях. С использованием известных корреляционных...
Пост-квантовый алгоритм электронно-цифровой подписи на...
Исследование алгоритмов пост-квантовой криптографии, основанных на хэш-функциях, и последующая разработка алгоритма, в основу которого берётся ГОСТ РФ 34.11–12 «Стрибог» и дерево Меркла.
Современные методы мониторинга коррозии | Статья в журнале...
Самая простая конфигурация датчика – это тип датчика с неподвижным чувствительным элементом (Рис. 2.). Чувствительные элементы
У этого типа есть высокая чувствительность и низкая восприимчивость к шуму системы, и это делает его оптимальным для мониторинга.
Похожие статьи
Лабораторные методы измерения и приборы контроля коррозии
Десятибалльная шкала коррозионной стойкости металлов (ГОСТ 13819–68).
Гравиметрический метод — один из наиболее распространенных методов определения скорости коррозии. Самый простой и доступный способ испытания в электролитах — это испытание в...
Выбор конструкционных материалов для оборудования установки...
Транспортировка неосушенного газа в присутствие сероводорода двуокиси углерода и других агрессивно компонентов нецелесообразна в виду высокой коррозионной агрессивности сыре и соответственно, резкого снижения надёжности эксплуатируемого оборудования и трубопроводов.
Методология сравнения потоковых шифров | Статья в журнале...
Данная статья посвящена методологии сравнения потоковых шифров. В статье рассматриваются потоковые шифры и их основные параметры. На основе этих параметров предлагается методика сравнения данных шифров, а также приводится пример применения данной методики к...
Применение стандарта криптосистем DES для шифрования...
достаточно высокая стойкость алгоритма. Литература.
Рассмотрим режим простой замены для ГОСТ 28147–89. Результат разбивается на восемь 4- битовых последовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания...
Применение стандартов AS 9100 и ГОСТ Р EN 9100–2011 для...
Отрасли промышленности, такие как авиационная, космическая и оборонная являются наукоемкими и специфичными отраслями с высокими рисками, связанными с качеством производимой продукции.
Роль ускоренных испытаний в определении надежности...
Элементная база современных радиоэлектронных изделий состоит из высокоинтегрированных компонентов (интегральных схем, печатных плат). В связи с тем, что разработчики компонентов более высокой интеграции ИС делают разработку под общие для ряда предприятий...
Оценка механических свойств металла по твердости при...
Проведен анализ основных неразрушающих методов контроля твердости металла, наиболее часто применяемых для косвенного определения механических свойств (σв, σ0,2) элементов газопроводов в эксплуатационных условиях. С использованием известных корреляционных...
Пост-квантовый алгоритм электронно-цифровой подписи на...
Исследование алгоритмов пост-квантовой криптографии, основанных на хэш-функциях, и последующая разработка алгоритма, в основу которого берётся ГОСТ РФ 34.11–12 «Стрибог» и дерево Меркла.
Современные методы мониторинга коррозии | Статья в журнале...
Самая простая конфигурация датчика – это тип датчика с неподвижным чувствительным элементом (Рис. 2.). Чувствительные элементы
У этого типа есть высокая чувствительность и низкая восприимчивость к шуму системы, и это делает его оптимальным для мониторинга.