Генераторы псевдослучайных чисел на регистрах сдвига с нелинейными обратными связями тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Саликов Евгений Александрович

• Саликов Евгений Александрович
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Саликов Евгений Александрович

Аннотация

Введение

1 Основы теории генераторов псевдослучайных чисел, функционирующих в конечных полях

1.1 Области применения генераторов псевдослучайных чисел

1.2 Требования к качественным генераторам псевдослучайных чисел

1.3 Уточненная классификация ГПСЧ

1.4 ГПСЧ, функционирующие в конечных полях

1.4.1 Основы теории конечных полей

1.4.2 ГПСЧ, функционирующие в конечном поле ОБ(рп), р - простое, п - натуральное

1.4.3 Конечные поля ОБ(2п)

1.5 Генераторы псевдослучайных чисел на регистрах сдвига с нелинейными обратными связями

Выводы к главе

2 Разработка математических моделей и логических схем генераторов псевдослучайных чисел

2.1 Генераторы (М - р + ^-последовательностей

2.2 От генераторов (М - р + ^-последовательностей к генераторам

(М + ^-последовательностей

2.3 Разработка генераторов (М - 2п + ^-последовательностей

2.4 Разработка нового класса генераторов (М - ^-последовательностей

на базе ГПСЧ, функционирующих в GF(2п)

2.5 Разработка генераторов (М + ^-последовательностей на базе генераторов (М - ^-последовательностей

Выводы к главе

3 Исследование разработанных ГПСЧ

3.1 Разработка программных моделей ГПСЧ

3.2 Программная реализация вычислений в конечных полях ОБ(2п)

3.2.1 Вычисление произведения двух элементов поля ОБ(2п)

3.2.2 Вычисление мультипликативной инверсии в ОБ(2п)

3.2.3 Нахождение примитивных элементов поля ОБ(д)

3.3 Результаты исследований генераторов

(М - 2п + 1) - последовательностей

3.4 Аппаратная реализация блоков умножения в поле GF(2n)

3.5 Деление полиномов в поле GF(2n)

Выводы к главе

4 Повышение эффективности стохастических алгоритмов обработки данных

4.1 ГПСЧ с самоконтролем

4.2 Хеш-функции на основе 3D стохастических преобразований

4.2.1 Основы теории хеш- функций

4.2.2 Новые конструкции

4.2.3 Разработка алгоритма хеширования

4.3 Обфускация логической схемы двоичного ГПСЧ

Выводы к главе

Заключение

Список источников информации

Список сокращений

Список терминов

Приложение

Приложение

Приложение

Приложение 4. Акты о внедрении

Приложение 5. Патенты

ВВЕДЕНИЕ

Актуальность. Важным элементом вычислительной техники являются генераторы псевдослучайных чисел (PRNG, Pseudo-Random Number Generator).

Многими авторами справедливо отмечается, что в различных отраслях науки и техники приходится иметь дело с объектами или процессами сложной структуры, а применение классических аналитических методов для их исследования затруднено или недостаточно эффективно. По этой причине в подобных ситуациях применяется имитационное моделирование, которое требует генерации случайных чисел [22, 23, 33, 40].

Аналогичные особенности имеют место и при проведении испытаний объектов цифровой техники на надежность, живучесть и отказоустойчивость, а также при решении задач защиты информации (ЗИ) от случайных и преднамеренных деструктивных воздействий. Следствием непрерывного роста сложности цифровых устройств (ЦУ), повышения степени интеграции элементной базы являются повышенные требования к обеспечению вышеупомянутых характеристик. Перспективным направлением во всех этих случаях является использование стохастических алгоритмов обработки данных, главный результат применения которых - внесение непредсказуемости в работу ЦУ, как в программном, так и аппаратном исполнении. Речь идет о таких универсальных приемах, как рандомизация, обфускация, ^-вариантная логика и полиморфизм [11, 23, 29, 30, 33, 34, 36, 39, 42, 46, 47].

ЭВМ, функционирование которых основано на использовании генераторов случайных или псевдослучайных чисел, традиционно называют стохастическими вычислительными машинами (СтВМ). Можно упомянуть два основных направления развития СтВМ:

- ЭВМ, использующие вероятностное представление информации [2, 11, 18, 30, 46, 47, 49];

- вычислительные машины и системы, в которых используется рандомизация последовательности адресов, рандомизация среды исполнения программ или рандомизация архитектуры [34, 39, 70].

Задача генерации случайных чисел в компьютерных системах и сетях решается различными способами. Первый предполагает использование физических процессов различной природы, которые преобразуются в пригодную для обработки в ЭВМ цифровую форму. Недостатком этого подхода являются сложности обеспечения требуемых статистических характеристик. Проблемы на практике создают особенности физических источников случайности, которые подвержены влиянию дестабилизирующих факторов, при их использовании отсутствует возможность повторной генерации последовательностей, что требуется при решении ряда задач ЗИ. Также следует отметить, что очень часто при реализации данного подхода применяются уникальные методы схемотехнического построения, не допускающие программной реализации. В результате случайные последовательности с заданными характеристиками ввиду сложности их формирования на практике очень часто заменяются псевдослучайными [23, 33, 50].

Непредсказуемые псевдослучайные последовательности (PRS, PseudoRandom Sequences), несмотря на то, что являются детерминированными, имеют практически все свойства реализации истинно случайных процессов и по этой причине успешно их заменяют во многих ситуациях. Можно отметить такие достоинства второго подхода, основанного на использовании PRS, как гарантированная точность формирования требуемых статистических характеристик на выходе PRNG, отсутствие влияния дестабилизирующих факторов, отсутствие проблем с подтверждения полученных результатов за счет возможности многократной повторной генерации PRS, эффективная программная реализация. Самый существенный недостаток второго подхода - сложности в части обеспечения важнейшего требования по непредсказуемости формируемых последовательностей [23, 33, 50].

Стоит упомянуть и третий подход, основанный на логичном предположении, что случайные последовательности можно получить, если инициализировать непредсказуемый PRNG случайными значениями в случайные

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

Требования к качественному PRNG:

- непредсказуемость и статистическая безопасность формируемых последовательностей ;

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

- возможность эффективной аппаратной или программной реализация, простота интегрального исполнения.

Важным и самым распространенным классом PRNG являются генераторы на регистрах сдвига с линейными и нелинейными обратными связями (далее РСЛОС и РСНОС). Основные преимущества, которые они имеют:

- хорошие статистические свойства формируемых PRS;

- гарантированно большой период формируемых последовательностей;

- эффективные как аппаратная, так и программная реализация, регулярная структура;

Введение диссертации (часть автореферата) на тему «Генераторы псевдослучайных чисел на регистрах сдвига с нелинейными обратными связями»

- высокая скорость работы.

Развитием теории PRNG на РСЛОС и РСНОС в нашей стране занимались в разные годы В.Н. Ярмолик, В.А. Песошин, В.М. Кузнецов, В.И. Доценко, Р.Г. Фараджев, О.А. Козлитин, на западе - А. Гилл (A. Gill), С.В. Голомб (S.W. Golomb), Б. Элспас (B. Elspas), Е. Дуброва (E. Dubrova) и другие.

Математический аппарат, лежащий в основе PRNG рассматриваемого класса - это, в первую очередь, теория конечных полей, также известная как теория полей Галуа GF(pn). В этой части можно отметить фундаментальные работы Ю.Л. Сагаловича.

Области использования этих генераторов [1-3, 9-11, 21, 28-30, 37, 39, 40, 42, 46, 47, 50, 51, 53, 55, 79]:

- Вероятностное тестирование ЦУ (Random Testing);

- Встроенное диагностирование ЦУ на СБИС (Built-in Self Testing);

- Кодирование с обнаружением и исправлением ошибок при передаче данных по каналам связи (Error Correcting Coding);

- Построение систем связи с шумоподобными сигналами;

- Скремблирование информации (Data Scrambling Techniques);

- Синтез синхронных счетчиков, в том числе самопроверяемых;

- Обфускация логики работы средств вычислительной техники (Design Obfuscation);

- Контроль хода выполнения программ и микропрограмм в ЭВМ (Online decking of Control Flow, Control Flow Integrity);

- Реализация стохастических методов обработки информации, в том числе минималистских (L ight-Weight) для RFID-систем и Интернета вещей.

В последнем случае, учитывая главный недостаток этих генераторов, связанный с предсказуемостью, они применяются лишь в качестве строительных блоков, особенно в тех ситуациях, где к PRNG предъявляются наиболее жесткие требования. Самый показательный пример на эту тему - это реализация одного из трех (при этом самого сложного) раундовых преобразований в специфицированном в российском стандарте ГОСТ Р 34.12-2015 алгоритме Кузнечик. Шаг перемешивания состояния алгоритма стохастического преобразования - это шестнадцать тактов работы 128-разрядного генератора Фибоначчи, функционирующего в конечном поле GF(28).

Наконец, можно упомянуть возможность использования схем с линейными и нелинейными обратными связями на цифровых элементах задержки для реализации физически неклонируемых функций (Physical Unclonable Functions), одно из назначений которых - защита от аппаратных недокументированных возможностей [69].

Таким образом, развитие теоретической и схемотехнической базы PRNG на РСЛОС и РСНОС является актуальной научной задачей.

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

Предметом исследования являются PRNG на РСЛОС и РСНОС.

Целью работы является повышение эффективности стохастических алгоритмов за счет увеличения периода формируемых последовательностей, исключения линейных зависимостей между отдельными фрагментами недвоичных PRS, обеспечения возможности самоконтроля правильности функционирования PRNG, разработки схем генераторов, ориентированных на реализацию технологий Design Obfuscation и Logic Encryption.

Для достижения поставленной цели в работе решались следующие задачи:

1) Обобщение результатов, полученных в последние годы в части двоичных PRNG, функционирующих в GF(2), на случай генераторов, функционирующих в конечных полях общего вида GF(pn); разработка математических моделей и логических схем генераторов (M - 2n + 1) и (M - 1)-последовательностей, где p - простое, n -натуральное;

2) Разработка методов перехода от генераторов M-, (M - p + 1)-, (M - 2n + 1) и (M - ^-последовательностей к генераторам (M + 1)-последовательностей, т.е. генераторам PRS максимально возможной длины при заданном количестве элементов памяти;

3) Разработка методов синтеза PRNG, обладающих свойством самоконтроля, на основе выбора характеристических полиномов специального вида;

4) Разработка логических схем PRNG, ориентированных на реализацию технологий Design Obfuscation и Logic Encryption;

5) Разработка математических и программных моделей PRNG новых классов и проведение исследований их технических характеристик;

6) В подтверждение тезиса о том, что хеш-генератор - это PRNG со входом, разработка способа хеширования данных на основе использования конструкции Sponge и 3D алгоритма стохастического преобразования, один из трех шагов преобразования которого суть 16 тактов генератора Галуа, функционирующего в GF(28). Основные результаты, выносимые на защиту:

- Математические и программные модели генераторов (M - 2n + 1)- и (M - 1)-последовательностей, функционирующих в конечном поле GF(2n), где n > 1 -целое; генераторы ориентированы в том числе на реализацию механизма скрытых функций;

- Методы перехода от генераторов M-, (M - p + 1)-, (M - 2n + 1) и (M - ^-последовательностей к генераторам (M + ^-последовательностей, т.е. генераторам PRS максимально возможной длины при заданном количестве элементов памяти;

- Методы синтеза PRNG, обладающих свойством самоконтроля, на основе выбора характеристических полиномов специального вида и предсказания значения свертки в GF(pn) содержимого регистров генератора при его правильном функционировании.

Соответствие паспорту специальности 2.3.2.

Направления исследований:

- Разработка научных основ создания новых классов PRNG, исследование их свойств и принципов функционирования;

- Теоретический анализ и экспериментальное исследование функционирования генераторов на РСЛОС и РСНОС с целью улучшения их технических характеристик;

- Разработка методов, алгоритмов и программ, обеспечивающих надежность, контроль и диагностирование ЦУ, учитывая возможность применения PRNG рассматриваемого класса для решения задач встроенного диагностирования,

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

Методы исследований. При проведении исследований и разработок в диссертационной работе были использованы теория линейных последова-тельностных машин, теория полей Галуа, а также методы стохастической информатики.

Научная новизна. В результате выполнения работы получены следующие новые научные результаты:

- Известные результаты исследований двоичных генераторов (M - 1)-последовательностей обобщены на случай генерации (M - 2n + 1)- и (M - ^-последовательностей, функционирующих в конечном поле GF(2n), где n > 1 - целое;

- Разработаны методы построения недвоичных генераторов (M + 1)-по-следовательностей на базе PRNG, функционирующих в конечном поле GF(pn), где p - простое, n - натуральное;

- Разработаны логические схемы PRNG, ориентированных на реализацию концепции Design Obfuscation и Logic Encryption, которые ориентированы на решение задач соответственно защиты от использования технических решений по двойному назначению и от аппаратных троянов и защиты от реверс-инжиниринга логических схем генераторов;

- Разработаны математические модели всех разработанных PRNG;

- Разработан алгоритм поиска управляющих воздействий, при подаче которых на входы PRNG, функционирующих в поле GF(2n), последние превращаются в генераторы (M - 2n + ^-последовательностей;

- Разработан новый алгоритм хеширования данных на основе использования модифицированной конструкции SPONGE (губка) и многомерных стохастических преобразований.

Практическая значимость работы.

PRNG все чаще используются в тех приложениях, где требуется высокая надежность функционирования. Известные методы аппаратного контроля ЦУ в реальном масштабе времени, такие как дублирование, контроль с использованием корректирующих кодов и другие, требуют значительных аппаратных затрат на их реализацию.

Разработан метод построения недвоичных PRNG в конечном поле GF(pn) с самоконтролем правильности функционирования на основе выбора характеристических полиномов специального вида. Метод основан на предсказании значения свертки содержимого элементов памяти генератора. Одна из возможных областей применения метода - синтез синхронных самопроверяемых счетчиков.

Разработана программная модель генератора (M - p + ^-последовательностей, где p - простое. Разработана программная модель генератора (M- 2n + 1)-последовательностей, где n - натуральное. Разработана программная модель генератора (M - ^-последовательности на основе PRNG, функционирующих в поле GF(2n).

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

Апробация результатов. Результаты работы докладывались на всероссийской конференции The Radio-Electronic Devices and Systems for Infocommu-nication Technologies» (REDS-2019) и на четырех международных конференциях Advanced Technologies in Robotics and Intelligent Systems (2020), IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (El-ConRus 2019, ElConRus 2020 и EIConRus 2022).

Публикации. По результатам работы опубликованы 15 печатных работ, в том числе 8 в печатных изданиях, индексированных в Scopus и Web of Science, получены четыре патента на изобретения РФ, изданы два учебных пособия.

Внедрение. Полученные результаты научной работы внедрены в учебный процесс НИЯУ МИФИ, РГУ нефти и газа (НИУ) имени И.М. Губкина и Государственного университета управления, а также в учебную и научную деятельность АНО "Центр стратегических оценок и прогнозов".

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

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

Структура и объем работы. Работа включает в себя введение, четыре главы, заключение, приложение, список использованных источников информации. Она состоит из 115 страниц, включая 78 рисунков, 9 таблиц, 85 наименований источников информации.

Содержание работы.

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

В первой главе изложен материал об областях применения PRNG на РСЛОС и РСНОС, их главных действующих свойствах. Перечислены требования к PRNG, дана классификация PRNG, при этом в качестве параметров классификации выбраны тип используемой нелинейной функции, структура генератора, тип используемых табличных преобразований, характер доступа к элементам

13

РЯБ, использование внешних источников случайности. Рассмотрены математические основы РЯ^и на РСЛОС, иначе говоря, РЯКО, функционирующих в полях Галуа.

Во второй главе показано, как известные результаты в части генерации двоичных (М - ^-последовательностей обобщаются на случай генерации р-ичных (М -р + ^-последовательностей, где р - простое. Граф переходов РЯКО в этом случае состоит из двух циклов длиной (рм - р) и р, где N - число регистров РЯКО, равное степени характеристического р-ичного полинома особого вида ф(х) = (х - 1)Х(х), где Х(х) - полином, примитивный над GF(р). Сумма по модулю р значений сигналов на управляющих входах генератора должна быть отлична от нуля.

Показано, что этот прием работает только тогда, когда число элементов поля - простое число. Для полей вида GF(2п), где п > 1 - натуральное, требуется иной подход, который и был разработан. Предложено на управляющие входы генератора подавать не фиксированные, как в известном случае, а динамически изменяющиеся значения. Рассмотрены математическая модель и логическая схема генератора (М - 2п + ^-последовательностей. Граф переходов РЯКО в этом случае при правильно подобранных значениях на управляющих входах состоит из двух циклов длиной 2п(2'¥ - 1) и 2п, где N - число регистров РЯКО, равное степени характеристического полинома особого вида ф( х) = (х - 1)Х(х), где Х(х) - полином, примитивный над GF(2п).

Рассмотрены математическая модель и логическая схема генератора (М - ^-последовательностей, построенного на основе генератора, функционирующего в поле GF(2n). Граф переходов РЯКО в этом случае при правильно подобранных фиксированных значениях на управляющих входах состоит из двух циклов длиной 2^ - 2 и 2, где N - число регистров РЯКО, равное степени характеристического полинома особого вида ф( х) = (х - 1)Х(х), где Х(х) - полином, примитивный над GF(2n). В рассматриваемом случае в схему вводятся сумматоры по модулю 2п по числу ненулевых управляющих воздействий.

Предложены и описаны методы перехода от всех разработанных генераторов последовательностей не максимальной длины к генераторам (М + ^-последовательностей.

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

В четвертой главе рассмотрены вопросы повышения эффективности стохастических алгоритмов обработки данных.

Предложены и описаны методы организации самоконтроля правильности работы генераторов рассматриваемого типа.

Предложена модификация генератора RC4, основанная на использовании LFSR (Linear Feedback Shift Register) и стохастических сумматоров (^-блоков). Модифицированный PRNG превосходит прототип с точки зрения непредсказуемости формируемых последовательностей.

Предложена модификация конструкции хеширования Sponge, на основе использования многомерного стохастического преобразования.

В заключении отражены основные результаты, полученные в диссертационной работе.

Глава 1. Основы теории генераторов псевдослучайных чисел, функционирующих в конечных полях

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

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

Аналогичные особенности характерны при проведении испытаний объектов цифровой техники на надежность, живучесть и отказоустойчивость, для решения задач по защите информации от различного рода деструктивных воздействий. Непрерывный рост сложности ЦУ и повышение степени интеграции элементной базы определяют повышенные требования к обеспечению перечисленных выше характеристик. Перспективным направлением во всех этих случаях следует признать применение стохастических алгоритмов обработки данных, главный результат использования которых - внесение непредсказуемости в работу ЦУ, как в программном, так и аппаратном исполнении. Иначе говоря, применение таких универсальных приемов, как рандомизация, обфускация и полиморфизм, которые предполагают использование генераторов случайных или псевдослучайных чисел. Задача формирования случайных чисел на объектах вычислительной техники решается различными способами. Первый предполагает использование физических процессов различной природы, преобразуемых в форму, пригодную для обработки в ЭВМ. Основной недостаток такого подхода - это ограниченная точность при обеспечении требуемых статистических характеристик. Необходимо также помнить, что физические источники энтропии подвержены влиянию дестабилизирующих факторов, при их использовании нет возможности повторного формирования после-

довательностей для подтверждения ранее полученных результатов исследования. Очень часто в рассматриваемой ситуации применяются уникальные методы схемотехнического построения, которые не позволяют разработать программную модель. Как результат, учитывая, что случайные последовательности чрезвычайно трудно формировать, они очень часто заменяются на псевдослучайные. Непредсказуемые псевдослучайные последовательности являются детерминированными, но обладают практически всеми свойствами реализации случайных процессов и довольно успешно заменяют их во многих приложениях [23, 33, 50].

Можно отметить такие достоинства второго подхода, основанного на использовании РЯБ, как гарантированная и сколь угодно высокая точность формирования требуемых статистических характеристик, отсутствие влияния дестабилизирующих факторов, отсутствие проблем с подтверждения полученных результатов, простота программной, а в некоторых случаях и аппаратной реализации [23, 33]. Самый существенный недостаток второго подхода -сложности в части обеспечения важнейшего требования по непредсказуемости формируемых РЯБ.

Необходимо упомянуть и третий подход, основанный на логичном предположении, что случайные последовательности можно получить, если инициализировать непредсказуемый РЯКО случайными значениями в случайные моменты времени. Иначе говоря, вариант использования РЯКО совместно с внешними источниками случайности, в первую очередь физические.

1.2. Требования к качественным генераторам псевдослучайных чисел

Можно выделить следующие основные требования, предъявляемые к РЯ^ [39]:

- Формируемые РЯБ должны быть непредсказуемыми;

- Формируемы РЯБ должны быть статистически безопасными;

- Формируемые РЯБ должны иметь гарантированно большой период при всех возможных значениях ключевых параметров;

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

1) Нахождение (i - 1)-го элемента у- - 1 на основании известного фрагмента PRS у, у- + 1 ... у- + ь - 1 конечной длины b (непредсказуемость влево);

2) Нахождение (i + b) - го элемента у- + ь на основании известного фрагмента PRS у- у- + 1 ... у- + ь - 1 конечной длины b (непредсказуемость вправо) [7, 37, 42, 80].

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

Свойство непредсказуемости появляется при применении для построения PRNG нелинейных преобразований, обладающих свойствами рассеивания и перемешивания информации. Любые изменения на их входах должны приводить к вероятности изменения каждого выходного бита, равной 1/2, т.е в среднем при большом количестве испытаний должно измениться 50% выходных бит [7, 37, 42, 80].

Обычно суть подобных преобразований - это многократное воспроизведение одной и той же итерации (раунда преобразования), в состав которой обязательно входят операции замены (Substitution) и перестановки (Permutation). Такие конструкции по этой причине называются SP-сетями.

Статистическая безопасность. PRNG считается статистически безопасным, если он проходит все оценочные статистические тесты, в частности тесты НИСТ [7, 37, 42, 80]. Наиболее полные наборы статистических тестов, используемых для оценки качества PRNG, содержатся в [52]. Одной из наиболее эффективных систем оценки статистической безопасности PRNG является система, разработанная И.В. Чугунковым (НИЯУ

МИФИ), в которой реализованы многие известные на тот момент времени графические и оценочные статистические тесты [43].

Гарантированно большой период. PRNG должен иметь гарантированно большой период при любых значениях ключевой информации и любых значениях векторов инициализации (IV, Initialization Vector). Это, казалось бы, очевидное с точки зрения необходимости его обеспечения требование, очень часто не выполняется даже в стандартах криптографической защиты информации. Речь идет о построении PRNG по схеме OFB (Output Feedback), о которой речь пойдет в следующем разделе.

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

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

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

1.3. Уточненная классификация ГПСЧ

В качестве важнейших параметров классификации PRNG верхнего уровня традиционно выделяют [ 7, 37, 42, 80]:

- Тип используемого нелинейного преобразования (криптографическое или некриптографическое);

- Конструкцию используемого нелинейного преобразования (Сеть Фейстеля, Квадрат, Куб), перспективным направлением является использование 2 D и 3 D преобразований, обладающими свойствами параллелизма на уровне элементарных операций;

- Структуру генератора (OFB - обратная связь по выходу, СTM -Counter Mode, Sponge - губка);

- Тип доступа к элементам PRS (последовательный или произвольный);

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

В тех ситуациях, когда к PRNG предъявляются особо жесткие требования используются блочные (блоковые), поточные (потоковые) генераторы и генераторы на основе One-Way Function и One-Way Trapdoor Functions [7, 37, 42, 80].

Стоит упомянуть, что некоторые поточные PRNG по сути - это NLFSR. Что не удивительно, учитывая, что главное требование к поточным генераторам - их высокое быстродействие. Иначе говоря, генераторы на NLFSR - это некий промежуточный тип PRNG, при этом можно выделить следующие разновидности подобных генераторов:

- дихотомические генераторы И.А. Кулакова [24, 25];

- генераторы на основе использования в цепи обратной связи стохастических сумматоров (R - блоков) [29, 30, 39];

- модификации PRNG, функционирующих в расширенных конечных полях, в первую очередь генераторы (М - pn + 1)-, (М - 1)- и (М + 1)-последовательностей [15-17, 38, 64, 65, 72].

Структура генератора. Это важнейший параметр, при этом с точки зрения структуры можно выделить четыре варианта построения непредсказуемых PRNG:

1) С нелинейной внутренней логикой (OFB, Output Feedback); иначе говоря, эти генераторы основаны на использовании сложной нелинейной функции перехода Ftr (Transition Function);

2) Двухступенчатая структура с нелинейной внешней логикой (CTR, Counter Mode), эти генераторы основаны на использовании сложной нелинейной функции выхода Fout (Output Function); в этой ситуации счетчик первой ступени может быть реализован на основе LFSR или NLFSR;

3) Двухступенчатая структура с нелинейной внутренней и нелинейной внешней логикой.

В первом случае уравнения работы PRNG имеют вид

Q(t + 1) = FTR(k,Q(t));

Q(0) = IV; ОЛ)

PRS(t) = Q(t),

где Ftr - функция перехода, Q(t) и Q(t + 1) - состояние PRNG соответственно в моменты времени t и (t + 1), к - ключ, PRS(t) - очередной элемент PRS, IV - вектор инициализации (Initialization Vector). Во втором случае уравнения работы PRNG имеют вид

Q(t + 1) = Q(t) + 1;

Q(0) = IV; (1.2)

PRS(t) = F0UT(k,Q(t)),

где Fout - функция выхода.

В третьем самом общем случае, когда обе функции (Ftr и Fout) зависят от ключевой информации, уравнения работы PRNG имеют вид

Q(t + 1) = FTR(k1,Q(t));

Q(0) = IV; (1.3)

PRS(t) = F0UT(k2,Q(t)).

Четвертый случай предполагает использование новой конструкции хеширования Sponge [77, 78] для генерации PRS. Уравнения работы генератора в этом случае имеют вид либо (1.4), либо (1.5)

Q(t + 1) = FPRP(Q(t));

Q(0) = IV || к; (1.4)

PRS(t) = Q(t)lp;

где Q(t)lp -p младших разрядов состояния,p < | Q(t) |, Fprp - псевдослучайная перестановка (Pseudo-Random Permutation), || - операция конкатенации;

PRS(i)= Fprp(IV || к || i)lp. (1.5)

В последнем случае при большой длине PRS может потребоваться две (или более) итерации Sponge.

Тип доступа к элементам PRS. PRNG, соответствующие уравнениям (1.1) и (1.4) являются устройствами с последовательным доступом к элементам PRS, а соответствующие уравнениям (1.2), (1.3) и (1.5) - c произвольным доступом к элементам PRS [7, 37, 42, 80].

1.4. ГПСЧ, функционирующие в конечных полях 1.4.1. Основы теории конечных полей

Конечное поле, также известное как поле Галуа GF(q) (GF - Galois Fields), q = pn - число элементов поля, p - простое, n - натуральное) - это конечное множество элементов, которое обладает следующими свойствами [27, 35, 39]:

1) В конечном поле определены две операции, первая называется сложением, вторая - умножением ;

2) Для любых элементов конечного поля а, P, у справедливы следующие соотношения а + P = P + а, ар = Ра, ( а + P ) у = ау + Ру ;

3) В конечном поле существуют два особых элемента, нулевой и единичный, они обозначаются соответственно, как 0 и 1, при этом справедливы соотношения 0 + а = а, 0 а = 0, 1 а = а;

4) В конечном поле для любого а ф 0 существует обратный ему элемент по сложению, обозначаемый как (-а), для него справедливо соотношение а + (- а) = 0; и обратный ему элемент по умножению, обозначаемый как а-1, для него справедливо аа-1 = 1;

5) В конечном поле существует хотя бы один особый элемент ю, называемый примитивным. Любой ненулевой элемент конечного поля является степенью примитивного элемента: У а ф 0 а = ю!, иначе говоря, поле Галуа можно представить так

Список литературы диссертационного исследования кандидат наук Саликов Евгений Александрович, 2023 год

СПИСОК ИСТОЧНИКОВ ИНФОРМАЦИИ

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. - М.: Мир, 1986.

2. Варакин Л.Е. Системы связи с шумоподобными сигналами. - М.: Радио и связь, 1985.

3. Гараков Г.А. Таблицы неприводимых полиномов над полем ОБ(р) (р < 11). Математические вопросы кибернетики и вычислительной техники. - Ереван: Изд. АН Арм. ССР, 1970, с. 112-142.

4. Гилл А. Линейные последовательностные машины. - М.: Наука, 1974.

5. Доценко В.И., Фараджев Р.Г. Анализ и свойства последовательностей максимальной длины. // Автоматика и телемеханика, 1969, № 11, с. 119-127.

6. Доценко В.И., Фараджев Р.Г., Чхартишвили Г.С. Свойства последовательностей максимальной длины с Р-уровнями. // Автоматика и телемеханика, 1971, № 8, с. 189-194.

7. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. Серия СКБ (специалисту по компьютерной безопасности). Книга 2. - М.: КУДИЦ - ОБРАЗ, 2003.

8. Иванов М.А., Кларин А.П. Генераторы псевдослучайных последовательностей. Учебное пособие. - М.: МИФИ, 1987.

9. Иванов М.А., Кларин А.П. Сигнатурный анализ в задачах контроля и диагностики цифровых устройств. Учебное пособие. - М.: МИФИ, 1986.

10. Иванов М.А., Зиборова М.Э., Тышкевич В.Г. Техническое диагностирование цифровых устройств с использованием сигнатурного анализа. - М.: МИФИ, 1989.

11. Иванов М.А. Способ обеспечения универсальной защиты информации, пересылаемой по каналу связи // Вопросы кибербезопасности. 2019, № 3 (31), с. 45-50.

12. Иванов М.А., Саликов Е.А. Генератор псевдослучайных чисел. Патент РФ на изобретение № 2 740 339, Бюл. № 2, 13.01.2021.

13. Иванов М.А., Саликов Е.А. Способ хеширования информации. Патент РФ на изобретение № 2 747 517, Бюл. № 13, 06.05.2021.

14. Иванов М.А., Саликов Е.А., Степанова М.А. Генератор псевдослучайных чисел. Патент РФ на изобретение № 2 756 833, Бюл. № 28, 06.10.2021.

15. Иванов М.А. Способ нелинейного трехмерного многораундового преобразования данных. Патент РФ на изобретение № 2 683 689, Бюл. № 10, 01.04.2019.

16. Кирьянов Б.Ф. Основы теории стохастических вычислительных машин. - Казань, 1975.

17. Кнут Д. Искусство программирования. Том 2. Получисленные алгоритмы: Пер. с англ. 3-е изд. - М.: Издательский дом «Вильямс», 2007.

18. Иванов М.А., Саликов Е.А., Козлов А.А., Григорьев М.П., Хисамутдинов М.А., Чуркин К.Ю. Генератор псевдослучайных чисел. Патент РФ на изобретение № 2 776 346, Бюл. № 20, 19.07.2022.

19. Контроль хода выполнения программ в ЭВМ с использованием сигнатурного анализа / В.Г. Тышкевич, М.Э. Зиборова, М.А. Иванов и др. // Зарубежная радиоэлектроника, 1990, № 1, с. 32-45.

20. Кузин Л.Т., Летунов Ю.П., Плахотишин А.Н. Принципы построения вероятностных моделей сетевых систем. В сборнике: Некоторые вопросы кибернетики. - М.: 1970, вып. 1, с. 62-71.

21. Кузнецов В.М., Песошин В.А. Генераторы случайных и псевдослучайных последовательностей на цифровых элементах задержки. - Казань, Изд-во Казан. Гос. техн. ун-та, 2013.

22. Кулаков И.А. Стохастическая криптография. Дихотомические последовательности и их свойства. http://random-art.ru/

23. Кулаков И.А. Стохастическая криптография: минималистский и легковесный подход. http://random-art.ru/

24. МакВильямс Ф.Дж., Слоан Н.Дж.А. Псевдослучайные последовательности и таблицы // ТИИЭР, 1976, № 12, с. 80-95.

25. Математические и компьютерные основы криптологии. Учебное пособие / Ю.С. Харин, В.И. Берник, Г.В. Матвеев, С.В. Агиевич. - Минск: Новое знание, 2003.

26. Обфускация логических схем генераторов псевдослучайных чисел на регистрах сдвига с линейными и нелинейными обратными связями. М.А. Иванов, И.Г. Коннова, Е.А. Саликов, М.А. Степанова. // Безопасность информационных технологий, 2021 г., Том 28, № 1, с. 74-83.

27. Осмоловский С.А. Стохастические методы передачи данных. - М.: Радио и связь, 1991.

28. Осмоловский С.А. Стохастические методы защиты информации. - М.: Радио и связь, 2003.

29. Песошин В.А., Кузнецов В.М., Н.Н. Сергеев. Цифровые генераторы случайных сигналов для защиты информационных средств телекоммуникаций. // Вопросы радиоэлектроники, 1993, вып. 4, с. 95-113.

30. Песошин В.А., Бурнашев М.И., Кузнецов В.М. Генераторы случайных чисел на микропрограммируемых БИС. // Вопросы радиоэлектроники, 1991, вып. 6, с. 77-88.

31. Песошин В.А., Кузнецов В.М. Генераторы псевдослучайных и случайных чисел на регистрах сдвига. - Казань, Изд-во Казан. Гос. техн. ун -та, 2007.

32. Разрушающие программные воздействия: Учебно-методическое пособие. А.Б. Вавренюк, Н.П. Васильев, Е.В. Вельмякина и др. - М.: НИЯУ МИФИ, 2011.

33. Сагалович Ю.Л. Введение в алгебраические коды. - М.: ИППИ РАН, 2010.

34. Скремблирование и дескремблирование. http://opds.spbsut.ru/data/_up-loaded/mu/zsspd/vlss_lections/zisopd_ lec_scrambler.pdf

35. Слоан Н.Дж.А. Коды, исправляющие ошибки и криптография. В кн.: Математический цветник / Сост. и ред. Д.А. Кларнер; Пер. с англ. Данилова Ю.А.; Под ред. И.М. Яглома. - М.: Мир, 1983.

36. Стариковский А.В. Рукопись диссертации на соискание ученой степени к.т.н. по специальности 05.13.11, НИЯУ МИФИ, 2018.

37. Стохастические методы и средства защиты информации в компьютерных системах и сетях / М.А. Иванов, Н.А. Мацук, И.В. Чугунков и др. - М.: Кудиц-Пресс, 2009.

38. Теория и применение псевдослучайных сигналов / А.И. Алексеев, А. Г. Шереметьев, Г.И. Тузов, В.И. Глазов. - М.: Наука, 1969.

39. Фараджев Р.Г. Линейные последовательностные машины. - М.: Советское радио, 1975.

40. Цифровые методы в космической связи. Под ред. С. Голомба.

- М.: Связь, 1969.

41. Чугунков И.В. Методы и средства оценки качества генераторов псевдослучайных последовательностей. - М.: МИФИ, 2012.

42. Чугунков И.В. Разработка и исследование алгоритмов генерации псевдослучайных последовательностей для компьютерных систем ответственного назначения. - Диссертация на соискание ученой степени к.т.н. по специальности 05.13.11, МИФИ, 2003.

43. Хеш-функция на основе 3D стохастических преобразований / М.А. Иванов, Т.И. Комаров, Е.А. Саликов, Н.А. Чепик. // Информационные войны, 2019, № 4, с. 71 -76.

44. Шевкопляс Б. В. Вероятностная синхронизация в телекоммуникационных системах: учебное пособие. - М.: БИНОМ. Лаборатория знаний, 2008.

45. Шевкопляс Б. Скремблирование передаваемых данных. // Схемотехника, 2004, № 12, с. 24-27; 2005, № 1, с. 29 -32; 2005, № 2, с. 32-35; 2005, № 3, с. 30-33.

46. Элспас Б. Теория автономных линейных последовательных сетей. Кибернетический сборник. - М.: ИЛ, 1963, № 7, с. 90-128.

47. Яковлев В.В., Федоров Р.Ф. Стохастические вычислительные машины.

- Л.: Машиностроение, 1974.

48. Ярмолик В.Н., Демиденко С.Н. Генерирование и применение псевдослучайных сигналов в системах испытаний и контроля. - Мн.: Наука и техника, 1986.

49. Ярмолик В.Н. Контроль и диагностика цифровых узлов ЭВМ. - Мн.: Наука и техника, 1988.

50. А statistical test suite for random and pseudorandom number generators for cryptographic application. NIST Special Publications 800-22, Revision 1.a, April, 2010.

51. Agrawal V. D. Built-in self-test. http://www.eng.auburn.edu/ ~va-grawal/E6970/LECTURES/chap 15.pdf

52. Chabloz J.-M., Mansouri S., Dubrova E. An algorithm for constructing a fastest Galois NLFSR generating a given sequence. In C. Carlet and A. Pott, editors, Sequences and Their Applications - SETA 2010, volume 6338 of Lecture Notes in Computer Science, pages 41 -54. Springer Berlin / Heidelberg, 2010.

53. Grout I.A. Integrated Circuit Test Engineering. Modern Techniques. -Springer-Verlag London Limited, 2006.

54. Dubrova E. An Equivalence Preserving Transformation from the Fibonacci to the Galois NLFSRs. 2008. https://arxiv.org/abs/0801.4079

55. Dubrova E. A List of Maximum Period NLFSRs. Cryptology ePrint Archive, Report 2012/166, 2012. http://eprint.iacr.org/2012/166.

56. Dubrova E. A Scalable Method for Constructing Galois NLFSRs with Period 2n - 1 using Cross-Join Pairs. Cryptology ePrint Archive, Report 2011/632, 2011. http://eprint.iacr.org/2011/632.

57. Dubrova E. A Method for Generating Full Cycles by a Composition of NLFSRs. https://eprint.iacr.org/2012/492.pdf

58. Dubrova E., Teslenko M., Tenhunen H. On analysis and synthesis of (n, k)-non-linear feedback shift registers. Design and Test in Europe, pp. 133-137, 2008. https://citeseerx.ist.psu.edu/viewdoc/download?Doi=10.1. 1.605.8382&rep=rep 1 &type=pdf

59. Dubrova E. Finding matching initial states for equivalent NLFSRs in the Fibonacci to the Galois configurations. // IEEE Transactions on Information Theory, vol. 56, pp. 2961 -2967, June 2010.

60. Dubrova E. An Equivalence-Preserving Transformation of Shift Registers. https://eprint.iacr.org/2014/051.pdf

61. GDozenHash Hash Function Based on Three-Dimensional Stochastic Transformations. M. Ivanov, T. Komarov, E. Salikov, N. Chepik. // Mechanisms and Machine Science, 2020, Vol. 80, Q3, pp. 375-385.

62. Kelsey J.G., Schneier B., Ferguson N. Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator. https://link.springer.com/content/pdf/10.1007/3-540-46513-8_2.pdf

63. Kiryakina M.A., Kuzmicheva S.A., Ivanov M.A. Encrypted PRNG by Logic Encryption. - Proceedings of the 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, ElConRus 2020, pp. 356-358.

64. Lin P.-C.K., Khatr S.P. VLSI Implementation of a Non-Linear Feedback Shift Register for High-Speed Cryptography Applications. https://peo-ple.engr.tamu.edu/sunilkhatri/projects-web/papers/nlfsr.pdf

65. Maes R., Ingrid Verbauwhede I. Physically Unclonable Functions: a Study on the State of the Art and Future Research Directions. https://www.researchgate.net/publication/226371108_Physically_Unclon-able_Functions_A_Study_on_the_State_of_the_Art_and_Future_Re-search_Directions

66. Morpheus: A Vulnerability-Tolerant Secure Architecture Based on Ensembles of Moving Target Defenses with Churn. M. Gallagher, L. Bier-nacki, S. Chen et.al. https://web.eecs.umich.edu/~barisk/public/mor-pheus.pdf

67. New Class of Pseudorandom Number Generators for Logic Encryption Realization. I.V. Chugunkov, M.A. Ivanov, E.A. Salikov, et. al. - Proceedings of the 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, EIConRus 2020, pp. 271-273.

68. New Class of Non-binary Pseudorandom Number Generators. M.A. Ivanov, B.V. Kliuchnikova, E.A. Salikov, et. al. // Mechanisms and Machine Science, 2020, V. 80, Q3, Стр. 291 -298.

69. Pesoshin V.A., Kuznetsov V.M., Shirshova D.V. Generators of the equi-probable pseudorandom nonmaximal-length sequences based on linearfeedback shift registers. // Automation and Remote Control, 2016, Volume 77, Issue 9, pp 1622-1632.

70. Pseudorandom Number Generators with Predeterminated Period and Pre-period. I.V. Chugunkov; B.V. Kliuchnikova; V.S. Tsyganov; et. al. - Proceedings of the 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, ElConRus 2020, pp. 268-270.

71. Searching for Nonlinear Feedback Shift Registers with Parallel Computing. P. D^browski, G. Labuzek, T. Rachwalik, J. Szmidt. https://eprint.iacr.org/2013/542.pdf

72. Song H.-Y. Feedback Shift Register Sequences. http ://165.132.121.177/pdf/journal_reprint/bookchapter_bc3 .pdf

73. Sponge-based pseudo-random number generators / G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche. CHES (S. Mangard and F.- X. Standaert, eds.), Lecture Notes in Computer Science, vol. 6225, Springer, 2010, pp. 33-47.

74. Sponge functions. G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche. http://www.csrc.nist.gov/pki/HashWorkshop/Public_Comments/2007_ May.html.

75. Wang L.-T., Wu C.-W., X. Wen: VLSI Test Principles and Architectures: Design for Testability, 2006.

76. Yao G. Transformation and Security Analysis of NLFSR-based Stream Ciphers. A thesis submitted in total fulfillment for the degree of Doctor of Philosophy in the School of Computing and Information Systems. The University of Melbourne, March 2021.

77. Zelenoritskaya A.V., Ivanov M.A., Salikov E.A. Possible Modifications of RC4 Stream Cipher. // Mechanisms and Machine Science, 2020 Vol. 80, Q3 pp. 335-341.

78. (M + 1)-Sequence Generators with Concurrent Error Detection / M. Ivanov, I. Chugunkov, B. Kliuchnikova, and E. Salikov. Procedia Computer Science, 2021, Vol. 190, Q2, pp. 361-369.

79. Computing in Finite Fields. Chugunkov I.V., Kliuchnikova B.V., Salikov E.A. et. al. - Proceedings of the 2022 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, ElCon-Rus 2022, pp. 270-276.

80. Иванов М.А., Чугунков И.В. Криптографические методы защиты информации в компьютерных системах и сетях: Учебное пособие / Под ред. М.А. Иванова. М.: НИЯУ МИФИ, 2012.

81. Иванов М.А., Саликов Е.А. Генераторы псевдослучайных чисел на регистрах сдвига с линейными и нелинейными обратными связями . Учебное пособие. - М.: НИЯУ МИФИ, 2021.

82. Иванов М.А., Саликов Е.А., Чукова Д.И. Генераторы псевдослучайных чисел в задачах защиты информации. Учебное пособие. -М.: РГУ нефти и газа имени И.М. Губкина, 2021.

83. Зензин О.С., Иванов М.А. Стандарт криптографической защиты - AES. Конечные поля. - М.: КУДИЦ - ОБРАЗ, 2002. - (СКБ - специалисту по компьютерной безопасности. Книга 1).

84. Иванов М.А., Стариковский А.В. Хеш-функции. Теория, применение и новые стандарты (часть 1), 2015.

85. Иванов М. А., Ковалев А. В., Мацук Н. А., Чугунков И. В. Методы и средства защиты информации в компьютерных системах и сетях - М.: Кудиц - Пресс, 2009.

Список сокращений

БУВ - блок управляющих воздействий;

ВИ - вектор инициализации;

ГПСЧ - генератор псевдослучайных чисел;

ЗИ - защита информации;

ИС - интегральная схема;

НСД - несанкционированный доступ (к информации);

ООП - объектно-ориентированное программирование;

ПО - программное обеспечение;

ПСП - псевдослучайная последовательность;

РСЛОС - регистр сдвига с линейной обратной связью;

РСНОС - регистр сдвига с нелинейной обратной связью;

УВ - управляющее воздействие;

ЦУ - цифровое устройство;

ЭВМ - электронная вычислительная машина;

CRC - Cyclic Redundancy Code;

LFSR - Linear Feedback Shift Register;

NLFSR - Non-Linear Linear Feedback Shift Register;

PRNG - Pseudo-Random Number Generator;

PRS - Pseudo-Random Sequence;

PUF - Physical Unclonable Function.

Список терминов

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

Генератор псевдослучайных чисел - устройство или программа, формирующее псевдослучайную последовательность

Конечная группа - конечное множество, на котором определена ассоциативная бинарная операция, сложение или умножение; в первом случае группа называется аддитивной, во втором - мультипликативной; причем для этой операции имеется нейтральный элемент (аналог нуля - для сложения, аналог единицы - для умножения) и каждый элемент группы имеет обратный (по сложению для аддитивной или по умножению для мультипликативной группы);

Ключ - секретный параметр;

Конечное поле - конечное множество, на котором определены две ассоциативные бинарные операции, сложение и умножение; причем для каждой операции имеется нейтральный элемент (аналог нуля - для сложения, аналог единицы - для умножения) и каждый ненулевой элемент поля а имеет обратный (-а) по сложению и обратный а-1 по умножению; см. также поле Галуа;

Мультипликативная инверсия - операция нахождения обратного элемента в мультипликативной группе, иначе говоря, нахождения заданного элемента а значения а-1;

Непредсказуемость - 1) непредсказуемость генератора - невозможность восстановления предшествующего элемента или предсказания последующего элемента по перехваченному выходному фрагменту конечной длины; в первом случае речь идет о непредсказуемости влево, во втором случае - о непредсказуемости вправо; 2) непредсказуемость преобразования - ситуация, когда любые входные изменения приводят в среднем к 50%-му изменению выхода; иначе говоря, при любых входных изменениях вероятность изменения каждого выходного бита равна 1/2; непредсказуемые преобразования обладают свойством интенсивного рассеивания и перемешивания информации;

Неприводимый полином - полином степени N над полем ОБ(д), не имеющий делителей кроме полиномов степени 0 и N; своеобразный аналог простого числа в мире полиномов; в частном случае q = 2, двоичные неприводимые полиномы не имеют делителей кроме единицы и самого себя;

Полином над полем Галуа - полином с коэффициентами, принадлежащими конечному полю;

Поле Галуа - конечное поле, обозначаемое GF(q) (GF - Galois Field); число элементов поля Галуа q = pn называется порядком поля, простое число p называется характеристикой поля; см. также конечное поле;

Полиморфизм - технология, затрудняющая реверс-инжиниринг; для ПО -технология непредсказуемой мутации одного и того же по выполняемым функциям кода за счет замены фрагментов кода на аналоги; ввода мусорных фрагментов кода, не несущих никакой функциональной нагрузки; псевдослучайной пермутации фрагментов кода и других приемов так называемого «изощренного» программирования; в случае ЦУ речь чаще всего идет о многовариантной логике (N variant Logic); не путать с полиморфизмом ООП;

Последователъностная машина - цифровое устройство с памятью;

Последовательность максимальной длины - см. M-последователъностъ

Примитивный полином - полином ) степени N над полем GF(q) называется примитивным, если его корень является генератором мультипликативной группы GF( qN); иначе говоря, РСЛОС, для которого ф(л) является характеристическим полиномом, формирует М- последовательность;

Примитивный элемент - элемент конечного поля GF(q), различные степени которого от 0 до q - 2 образуют все ненулевые элементы поля; иначе говоря, примитивный элемент является генератором мультипликативной группы GF*(q);

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

Рандомизация - стохастический метод ЗИ, обеспечивающий непредсказуемое поведение объектов и средств их защиты;

Статистическая безопасность - ситуация, когда на выходе ЦУ ни один статистический тест не может обнаружить никаких закономерностей; иначе говоря, выходная последовательность ЦУ неотличима от истинно случайной последовательности;

Стохастический метод защиты информации - метод ЗИ, основанный на использовании непредсказуемых преобразований; иначе говоря, метод, основанный на использовании ГПСЧ или хеш-функций;

Стохастическое преобразование - непредсказуемое преобразование информации;

Хеширование - необратимое преобразование информации с использованием хеш-функции;

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

Design Obfuscation (Hardware Obfuscation) - 1) технология модификации структуры и графа переходов цифрового устройства, направленная на защиту от аппаратных закладок за счет сокрытия его функциональных возможностей; 2) технология модификации структуры и графа переходов цифрового устройства, направленная на реализацию механизма скрытых функций для защиты от использования устройства по двойному назначению;

Logic Encryption (Logic Obfuscation) - технология, направленная на защиту от реверс-инжиниринга логической схемы цифрового устройства; конструкция ЦУ меняется таким образом, что оно работает правильно, только в том случае, если сигналы на дополнительных ключевых входах принимают правильные значения;

М-последовательность - последовательность длиной М = qN - 1, формируемая РСЛОС, соответствующим характеристическому полиному степени N, примитивному над GF(q);

Physical Unclonable Function - физически неклонируемая функция, используемая для генерации случайных параметров ИС.

Приложение 1. Битовая АКФ РЯ8 с выхода генератора (М - 1)-последовательности. Тестовый пример

Битовая АКФ для ОБ(2и) считается по формуле

г/-Т—2й

где Т = пБ, I - величина циклического сдвига анализируемой последовательности относительно исходной, й - расстояние Хэмминга, Б - длина (период) последовательности.

1111101100001101010001101001 28 -0 0

1111011000011010100011010011 14- 14 1

1110110000110101000110100111 14- 14 2

1101100001101010001101001111 14- 14 3

1011000011010100011010011111 12- 16 4

0110000110101000110100111111 14- 14 5

1100001101010001101001111110 14- 14 6

1000011010100011010011111101 14- 14 7

0000110101000110100111111011 12- 16 8

0001101010001101001111110110 14- 14 9

0011010100011010011111101100 14- 14 10

0110101000110100111111011000 14- 14 11

1101010001101001111110110000 12- 16 12

1010100011010011111101100001 14- 14 13

0101000110100111111011000011 14- 14 14

1010001101001111110110000110 14- 14 15

0100011010011111101100001101 12- 16 16

1000110100111111011000011010 14- 14 17

0001101001111110110000110101 14- 14 18

0011010011111101100001101010 14- 14 19

0110100111111011000011010100 12- 16 20

1101001111110110000110101000 14- 14 21

1010011111101100001101010001 14- 14 22

0100111111011000011010100011 14- 14 23

1001111110110000110101000110 12- 16 24

0011111101100001101010001101 14- 14 25

0111111011000011010100011010 14- 14 26

1111110110000110101000110100 14- 14 27

1111101100001101010001101001 28 -0 28

Рисунок П1.1 - Тестовый пример. АКФ РЯБ с выхода генератора (М - 1)-последовательности, п = N = 2, £ = 14, ф(х) = (х + 1)(х + ю). Первый столбец - сдвинутые копии (М - ^-последовательности, второй столбец - число совпадений/несовпадений, третий столбец - величина сдвига.

000101110100101001100011111011 30-0 0

001011101001010011000111110110 14-16 1

010111010010100110001111101100 14-16 2

101110100101001100011111011000 14-16 3

011101001010011000111110110001 14-16 4

111010010100110001111101100010 14-16 5

110100101001100011111011000101 14-16 6

101001010011000111110110001011 14-16 7

010010100110001111101100010111 14-16 8

100101001100011111011000101110 14-16 9

001010011000111110110001011101 14-16 10

010100110001111101100010111010 21-9 11

101001100011111011000101110100 14-16 12

010011000111110110001011101001 14-16 13

100110001111101100010111010010 14-16 14

001100011111011000101110100101 14-16 15

011000111110110001011101001010 14-16 16

110001111101100010111010010100 14-16 17

100011111011000101110100101001 14-16 18

000111110110001011101001010011 21-9 19

001111101100010111010010100110 14-16 20

011111011000101110100101001100 14-16 21

111110110001011101001010011000 14-16 22

111101100010111010010100110001 14-16 23

111011000101110100101001100011 14-16 24

110110001011101001010011000111 14-16 25

101100010111010010100110001111 14-16 26

011000101110100101001100011111 14-16 27

110001011101001010011000111110 14-16 28

100010111010010100110001111101 14-16 29

000101110100101001100011111011 30-0 30

Рисунок П1.2 - Тестовый пример. АКФ РЯБ с выхода генератора М -последовательности, п = N = 2, Б = 15, ф(х) = х2 + х + ю. Первый столбец - сдвинутые копии М -последовательности, второй столбец - число совпадений/несовпадений, третий столбец - величина сдвига.

Приложение 2. Битовая АКФ РЯ8 с выхода генератора (М - 1)-последовательности. Вывод программы

I I I I I I

Рисунок П2.1 - АКФ РЯБ с выхода генератора (М - ^-последовательности, п = N = 2, Б = 14, ф(х) = (х + 1)(х + ю).

Рисунок П2.2 - АКФ РЯБ с выхода генератора М -последовательности, п = N = 2, Б = 15, ф(х) = х2 + х + ю.

Приложение 3. Битовая АКФ РЯ8 с выхода генератора (М - 1)-последовательности. Вывод программы

1.0 -0.8 -0.6 -

0.4 -0.2 -

Рисунок П3.1 - АКФ РЯБ с выхода генератора (М - ^-последовательности, п = 4, N = 2, £ = 254, ф(х) = (х + 1)(х + ю).

0.6

0.4

0.2

0.0

Рисунок П3.2 - АКФ РЯБ с выхода генератора М -последовательности, п = 4, N = 2, Б = 255, ф(х) = х2 + х + ю.

Приложение 4. Акты о внедрении

Центр стратегических оценок и прогнозов

Двтси-кмнея некоммерческая организация Per. IIP 11£779â00e077 1ИН 77T7-Eae&4 / Km 771701001

17BS15. t. MiSMS. у." Аквднм .на Королева, цаы 13. çrp 1 e-miii ru. ww.csef.ni

H> 131

«11л Октября 2Q21 г.

; АКТ

о внедрении результатов диссертационной работы Сн.шковз Е.Л,

«Генераторы псевдослучайных чисел на регистрах сдвига с нелинейными обратными связями» в учебной и научной деятельности Центра

Результаты диссертационной работы Саликова Е.А. на соискание ученой степени кандидата технических наук внедрены в учебный процесс AHO «Центр стратегических оценок и прогнозов».

Разработанные Саликовым Е.А. модели генераторов псевдослучайных чисел (ГПСЧ) использовались при проведении учебно-методических занятий для экспертного пула Центра по проблемам информационной безопасности.

Разработанные устройства позволяют создавать на их основе непредсказуемые ГПСЧ специального назначения, примитивы хеширования и поточного стохастического преобразования дашгых. Предлагаемые алгоритмы особенно эффективны при их использовании в условиях ограниченных ресурсов, например, при реализации стохастических алгоритмов обработки данных в КГЩ-системах, Интернете вещей. Особенностями генераторов являются эффективная программная и аппаратная реализация; высокое быстродействие; регулярная структура, удобная для интегрального исполнения; возможность организации самоконтроля правильности работы ГПСЧ и самое главное ■ нелинейный закон формирования последовательности, что выгодно отличает семейство этих генераторов от классических ГПСЧ, функционирующих в нолях Галуа.

Генеральный директор,

доктор технических наук, старший научный сотрудни

УТВЕРЖДАЮ

И.о. Директора Института информационных систем ФГБОУ ВО «Государственный университет

^^е^даРЧвленил» (ГУ У) /г ЪСЬ Писарева О.М.

Щ»н2021 г.

%

АКТ

о внедрении результатов диссертационной работы Саликова Е.А.

«Генераторы псевдослучайных чисел на регистрах сдвига с нелинейными обратными связями» в учебный процесс ФГБОУ ВО «Государственный университет управления» (ГУУ)

Настоящий акт подтверждает, что результаты диссертационной работы Саликова Е.А. на соискание ученой степени кандидата технических наук внедрены в учебный процесс Института информационных систем ГУУ.

Разработанные Садиковым Е.А. генераторы псевдослучайных чисел (ГПСЧ) использовались при проведении лекционных и практических занятий по дисциплине «Информационная безопасность» со студентами 4-го курса бакалавриата, 2020/2021 и 2021/2022 учебных годов.

Разработанные устройства позволяют создавать на их основе непредсказуемые ГПСЧ специального назначения, примитивы хеширования и поточного стохастического преобразования данных. Предлагаемые алгоритмы особенно эффективны при их использовании в условиях ограниченных ресурсов, например, при реализации стохастических алгоритмов обработки данных в ИТЮ-системах. Интернете вещей. Особенностями генераторов являются эффективная программная и аппаратная реализация; высокое быстродействие; регулярная структура, удобная для интегрального исполнения; возможность организации самоконтроля правильности работы ГПСЧ и самое главное - нелинейный закон формирования последовательности, что выгодно отличает семейство этих генераторов от

» щих в полях Галуа.

Приложение 5. Патенты

РОССИЙСКАЯ ФЕДЕРАЦИЯ

(19)

RU

(id

2 747 517131 С1

(51) МПК G06F7/58 (2006,011 H04L9/00 (2006.01)

ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ

(12) ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ

(Í2) С ПК

G06F 7/58 (2021.02); H04L 9/00 (202102)

О

ш

I-(М

=)

(21X22) Заявка; 2020109725. 05.03 2020

(24) Дата начала отсчета сроки действия патента:

05.03.2020

Дата регистрации:

06.05.2021

Приоритет! ы):

(225 Дата подачи заявки: 05.03.2020

(45) Опубликовано: 06.05.202l Бюп. № 13

Адрес для переписки:

115405, Москьа, Каширское ш„ 31, НИЯУ МИФИ, ОУИС УН И, Бейгул Г В.

(72) Автор(ы):

Иванов Михаил Александрович (ДЦ), Саликов Евгений Александрович (1Ш)

(73) Патентообладатель^):

федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский ядерный университет МИФИ" (НИЯУ МИФИ) (ИТ!)

(56) Список документов, цитированных в отчете о поиске: Ни 2303994 С1.10.01.2014.КЛ 2591015 С1,10.07.2016.1Ш 2683689 С1. 01,04.2019. Ки 2504911 С1,20.01.2014.1Ш 2519004 С2,10.06.2014. ЦЯ 2011/0179281 А1, 21.07.2011. и5 2016/0013932 А1.14.01.2016, WO 2019/190411 А1,03.102019.

(54) СПОСОБ ХЕШИРОВАНИЯ ИНФОРМАЦИИ

(57) Реферат:

Изобретение относится к способу хеширования информации. Техническим результатом является повышение

криптостойкости хеширования. Способ включает в себя разбиение входной строки М на п г-разрядных блоков фиксированной длины М|, М;, ,,. Мп; дополнение в случае необходимости последнего блока Мп до длины, кратной разрядности блоков; выполнение п итераций ввода информации с использованием нелинейной

функции Я(Р!_1, М5), где ¡=1, 2, 3.....п; Ро=Р(1У),

ТУ - вектор инициализации; выполнение (¡2.0 итераций обработки информации где

1, 2, 3, ,, <1; Ро - результат последней итерации ввода: выполнение к>0 итераций вывода и н форма ц ии

1=1, 2, 3, к; где Рг).,_ [ ( и Рс:(-[_^, - соответственно

г младших и с старших разрядов результата (t-1) -Й. итерации обработки информации, Tyi и Гс0 -соответственно г младших и с старших разрядов результата последней итерации обработки информации, после чего конкатенация г младших разрядов результата последней итерации обработки! информации и г младших разрядов результатов всех итераций вывода информации

Fr0 II Frl 1 FrZ II ■ ■ ■ II ?гк объявляется

результатом хеширования, т.е. хеш-образом строки М. При выполнении каждой <-й итерации ввода информации используется блок трехвходового многораундового стохастического преобразования данных R(A, В, С), где А -преобразуемый блок данных, В - параметр преобразования, С - параметр раундовых преобразований, при этом итерация ввода осуществляется по формуле

7J С

to

-(ь Vi

О