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

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

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

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

Случайные и псевдослучайные двоичные последовательности используются в качестве исходных данных для получения ключей, синхропосылок, стартовых векторов и других случайных параметров в системах защиты информации [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.