Программные и аппаратные генераторы двоичных последовательностей в информационных системах | Статья в сборнике международной научной конференции

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

Опубликовать статью в журнале

Библиографическое описание:

Гусаров А. В., Хачикова Н. А. Программные и аппаратные генераторы двоичных последовательностей в информационных системах [Текст] // Технические науки в России и за рубежом: материалы VIII Междунар. науч. конф. (г. Краснодар, июнь 2019 г.). — Краснодар: Новация, 2019. — С. 1-3. — URL https://moluch.ru/conf/tech/archive/332/15127/ (дата обращения: 21.10.2019).



Случайные и псевдослучайные двоичные последовательности находят всё более широкое применение в системах сбора и обработки информации. Генерация таких последовательностей требует применения математических моделей как в процессе генерации, так и в процессе оценки качества случайных и псевдослучайных двоичных последовательностей. Темой данной работы является исследование процесса генерации последовательностей псевдослучайных двоичных последовательностей и проверка их качества.

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

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

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

Программные генераторы двоичных последовательностей выполняют генерацию двоичной последовательности по какому-либо алгоритму, поэтому случайность такой последовательности всегда под вопросом. Двоичные последовательности, генерируемые таким способами, следует обязательно проверять на случайность, т. к. фактически такие последовательности являются псевдослучайными из-за наличия фиксированного периода повторяемости и их вычисления по алгоритму. Вследствие этого программные генераторы двоичных последовательностей фактически являются генераторами псевдослучайных чисел (ГПСЧ). Несмотря на свои недостатки, ГПСЧ имеют одно неоспоримое достоинство. Они позволяют генерировать повторяющиеся псевдослучайные двоичные последовательности, если начальные условия для генерации не меняются. Это бывает необходимо, например, в процессе генерации гаммы шифра на приемном и передающем устройстве в системах засекреченного обмена информацией [1].

Основной проблемой при генерации последовательностей длиной более 64 бит является то, что большинство известных генераторов псевдослучайных последовательностей формируют результат длиной не более 64 бит, поэтому более длинные последовательности должны формироваться путем «склеивания» из более коротких. Еще одним вариантом формирования длинных последовательностей является использование хэш-функции, например функции по ГОСТ Р 34.11–94 или по ГОСТ Р 34.11–2012.

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

Для математической модели должна быть обеспечена энтропия как минимум одного из параметров, иначе теряется «случайность» результата. В ситуации, когда математическая модель реализуется на персональном компьютере, источником энтропии могут быть либо пользователь, либо генераторы внешних событий, подключаемые к сети или внешним устройствам ПК. Проанализируем эти источники энтропии.

Достоинствами пользователя (человека) как источника энтропии являются:

– широкие возможности в выборе способов формирования энтропии;

– огромный разброс параметров человеческого организма, увеличивающий энтропию;

– нет необходимости в дополнительных устройствах, подключении к сети, зависимости от внешних событий. Человек использует стандартные устройства ввода информации (например, клавиатуру, мышь).

К недостаткам пользователя как источника энтропии можно отнести:

– возможность влияния на энтропию путем сознательного или подсознательного упорядочивания своих действий, что может привести к снижению энтропии;

– необходимость в сложных алгоритмах обработки входных данных, которые служат источником энтропии;

– необходимость присутствия человека во время генерации двоичных последовательностей, что ограничивает гибкость процесса генерации, «привязывает» его к определенным периодам времени;

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

Достоинствами генераторов внешних событий как источника энтропии являются:

– возможность автоматизации процесса генерации двоичных последовательностей;

– высокая скорость генерации двоичных последовательностей.

К недостаткам генераторов внешних событий как источника энтропии можно отнести:

– высокую стоимость реализации генераторов внешних событий;

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

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

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

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

На первом этапе необходимо установить, значимо или нет отличается относительная частота появления нулей (единиц) в данной выборке от теоретического значения вероятности появления единицы (нуля), равной 0,5. Другими словами, нужно проверить, является ли количество нулей и единиц в выборке примерно равным. Если нет, то значимо ли отклонение в ту или иную сторону. В качестве уровня значимости здесь и в дальнейшем достаточно выбрать  = 0,05. Этот этап, конечно, не дает ответа на вопрос о случайности выборки. В случае значимого отклонения относительной частоты от 0,5, можно утверждать, что выборка не является случайной. Положительным для дальнейшего исследования является незначимое отклонение.

На втором этапе используется критерий пиков (критерий поворотных точек), на основе которого можно проверить, не слишком ли часто (или редко) в последовательности возникают изолированные нули или единицы. Этот этап позволяет исключить из рассмотрения выборки, имеющие вид «гребенки» или наоборот, содержащие только наборы групп нулей и единиц.

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

Разработана программа, реализующая данный метод [4]. Проводятся исследования, направленные на оценку влияния параметров программного ГСПЧ и способа формирования 256-битовой ключевой последовательности на случайность получаемых ключей. Для этого разработан программный комплекс, состоящий из программ генерации ключей, программ оценки качества ключей и интерфейса пользователя, позволяющего задать исходные данные и сформировать результат на экране дисплея компьютера и в файле на диске [4]. Проводятся сравнительные исследования качества ключей, полученных программными генераторами псевдослучайных последовательностей, а также разрабатывается математические модели, позволяющие реализовать источники энтропии.

Литература:

  1. Романец Ю. В., Тимофеев П. А., Шаньгин В. Ф. Защита информации в компьютерных системах и сетях / Под ред. В. Ф. Шаньгина. — 2-е изд., перераб. и доп. — М.: Радио и связь, 2001. 376 с.: ил.
  2. ГОСТ 28147–89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. Введ. 01.07.1990. Переиздание. М.: ИПК Издательство стандартов, 1996. — 26 с.
  3. Гусаров А. В., Гусарова Н. И. Об одном способе оценки параметров криптографических ключей \\ Информационные системы и технологии, 2013, № 1 с. 124–128.
  4. Гусаров А. В., Жолобов А. М. Исследование качества генерации псевдослучайных чисел в техническом вузе \\ «Технические науки: теория и практика»: Материалы IV Mеждунар. науч. конф. (г. Казань, ноябрь 2018 г.). — Казань: Молодой ученый, 2018. — С. 6–7.
Основные термины (генерируются автоматически): последовательность, источник энтропии, событие, математическая модель, генератор, качество ключей, двоичная последовательность, обработка информации, программный генератор, высокая скорость генерации.

Ключевые слова

энтропия, качество ключей, симметричная криптосистема, псевдослучайные двоичные последовательности, случайные двоичные последовательности

Похожие статьи

Методы генерации случайных чисел | Статья в журнале...

‒ Pseudo random number generator (ГПСЧ, генератор псевдослучайных чисел). Эти два генератора задания случайной последовательности отличаются способом получения случайного числа. ГНСЧ использует в качестве механизма получения случайного числа некий...

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

Основная сложность генерации последовательности псевдослучайных чисел на

Генератор ключевой последовательности выдает поток битов, который выглядит случайными, но в

С точки зрения теории информации количество случайности — энтропия, которая может быть...

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

Ключевые слова: криптографические ключи, алгоритмы генерации ключей, качество ключей, симметричная криптосистема.

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

Анализ процедур генерации ключей криптографических...

Программная реализация теста на оценку энтропии для равномерно распределенных

Библиографическое описание: Ставер Е. В. Анализ процедур генерации ключей

Данный тест оценивает энтропию на выходе генератора равномерно распределенной величины...

Анализ процедур генерации ключей криптографических...

Библиографическое описание: Ставер Е. В. Анализ процедур генерации ключей криптографических алгоритмов.

Его замечательная работа рассматривается как фундамент современной математической статистики [1]. Для

Программная реализация. Литература

Обзор аппаратных генераторов случайных чисел

Подобные квантовые генераторы имеют высокую скорость выходного потока — до

Одним из успешных примеров построения ГСЧ на базе теплового шума является генератор

В статье были рассмотрены основные способы построения аппаратных генераторов случайных чисел.

Подробный аналитический разбор физического датчика calif.bit...

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

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

Исследования прецизионного генератора. Качество работы П-генератора оценивается при помощи критериев согласованности.

Объектом исследований стало качество выборок, полученных в результате генерации П-генератором выборки значений случайных величин...

О случайности псевдослучайных последовательностей

Вычислительные последовательности оказываются не случайными по любому из выше

Тест на несцеплинные серии данный генератор тоже не прошел. В статье показано, что генератор

Программная реализация теста на оценку энтропии для равномерно распределенных...

Похожие статьи

Методы генерации случайных чисел | Статья в журнале...

‒ Pseudo random number generator (ГПСЧ, генератор псевдослучайных чисел). Эти два генератора задания случайной последовательности отличаются способом получения случайного числа. ГНСЧ использует в качестве механизма получения случайного числа некий...

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

Основная сложность генерации последовательности псевдослучайных чисел на

Генератор ключевой последовательности выдает поток битов, который выглядит случайными, но в

С точки зрения теории информации количество случайности — энтропия, которая может быть...

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

Ключевые слова: криптографические ключи, алгоритмы генерации ключей, качество ключей, симметричная криптосистема.

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

Анализ процедур генерации ключей криптографических...

Программная реализация теста на оценку энтропии для равномерно распределенных

Библиографическое описание: Ставер Е. В. Анализ процедур генерации ключей

Данный тест оценивает энтропию на выходе генератора равномерно распределенной величины...

Анализ процедур генерации ключей криптографических...

Библиографическое описание: Ставер Е. В. Анализ процедур генерации ключей криптографических алгоритмов.

Его замечательная работа рассматривается как фундамент современной математической статистики [1]. Для

Программная реализация. Литература

Обзор аппаратных генераторов случайных чисел

Подобные квантовые генераторы имеют высокую скорость выходного потока — до

Одним из успешных примеров построения ГСЧ на базе теплового шума является генератор

В статье были рассмотрены основные способы построения аппаратных генераторов случайных чисел.

Подробный аналитический разбор физического датчика calif.bit...

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

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

Исследования прецизионного генератора. Качество работы П-генератора оценивается при помощи критериев согласованности.

Объектом исследований стало качество выборок, полученных в результате генерации П-генератором выборки значений случайных величин...

О случайности псевдослучайных последовательностей

Вычислительные последовательности оказываются не случайными по любому из выше

Тест на несцеплинные серии данный генератор тоже не прошел. В статье показано, что генератор

Программная реализация теста на оценку энтропии для равномерно распределенных...