Генераторы псевдослучайных чисел на основе РСЛОС07.12.2020 18:32

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

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

Целью данной статьи является ознакомление с ГПСЧ на основе регистров сдвига с линейной обратной связью, несколькими их модификациями, а также несколькими криптографически стойкими ГПСЧ, которые применяются на практике.

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

Начнём немного издалека, с рассмотрения общей структуры ГПСЧ. За основу взята структура, которая рекомендуется и более детально рассмотрена авторами в [2].

https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800–90Ar1.pdf, страница 11

Кратко рассмотрим каждый блок:

1. Источник энтропии — некоторый внешний источник случайности или, иными словами, механизм, генерирующий случайные величины (совокупность таких величин ещё называют начальным вектором), которые в дальнейшем используются для инициализации состояния внутреннего состояния ГПСЧ.

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

3. Внутреннее состояние — память ГПСЧ, в которой хранятся параметры и переменные, которые необходимы для работы генератора;

4. Функция инициализации получает входные данные энтропии и объединяет их с полученным nonce и строкой персонализации, в результате чего создаётся некоторое начальное значение, из которого в свою очередь создаётся начальное внутреннее состояние;

5. Функция реинициализации отличается от функции инициализации данными, которые используются для установки нового внутреннего состояния. Главным отличием является то, что помимо внешних данных здесь учитывается и предыдущее внутреннее состояние;

6. Функция деинициализации очищает внутреннее состояние системы, что полезно делать в целях противодействия анализу системы;

7. Функция генерации создаёт на выходе псевдослучайное число на основании полученных данных (дополнительный вход и внутреннее состояние) и генерирует новое внутреннее состояние для следующего запроса;

8. Блок тестирования производит проверку корректности работы ГПСЧ.

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

Регистр сдвига с линейной обратной связью

Рассматриваемый класс генераторов построен на идее использования регистров сдвига с линейной обратной связью (РСЛОС), т.е. преобразовании двоичного представления некоторого числа.

Регистр сдвига с линейной обратной связью. Источник: [3, стр. 105]

Регистр сдвига состоит из n однобитовых ячеек b1, b2, . . . , bn и линейной обратной связи с коэффициентами C1 = 1, C2, C3, . . . , Cn ∈ {0, 1}. Ненулевые коэффициенты называют отводами (рекомендуемые индексы отводов в зависимости от длины битового поля регистра можно найти в [8]). Выходная последовательность задаётся многочленом над полем Галуа GF (2), т.е происходит суммирование по модулю 2:

C (x) = С1xn + C2xn-1 + . . . + Cnx + 1,

который называют характеристическим многочленом РСЛОС. На каждом этапе генератор

1. Суммирует по модулю 2 значения ячеек, индексы которых совпадают с индексами отводов, т.е. коэффициенты Ci которых равны 1;

2. Сдвигает значения на одну ячейку влево;

3. В самый правый бит записывает значение, полученное на шаге 1.

Выходом такого генератора является значение самого левого бита b1 после сдвига. Максимальный период выходной последовательности такого генератора равен 2n-1, причём он достигается только тогда, когда характеристический многочлен является примитивным.

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

Регистр сдвига с обратной связью по переносу

Хочется обратить внимание на существующую модификацию генератора ГПСЧ на основе РСЛОС, а именно: регистр сдвига с обратной связью по переносу. Отличием от предыдущего случая является наличие дополнительного регистра переноса, который является не битом, а числом, возникающим в результате определённых преобразований (такое преобразование называется функцией обратной связи).

Алгоритм работы также очень похож на предыдущий:

1. В начале каждой итерации складываются значения ячеек, индексы которых совпадают с индексами отводов, и значение регистра переноса;

2. Значения сдвигаются на одну ячейку;

3. Остаток от деления по модулю 2 полученного результата помещается в последнюю ячейку;

4. Целая часть такого деления становится новым значением регистра переноса.

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

Хоть и становится очевидным, что одним из способов улучшения показателя криптостойкости является увеличение периода генерируемой последовательности, регистр сдвига с обратной связью по переносу не относят к криптографически стойким ГПСЧ.

Криптографически стойкие ГПСЧ на основе РСЛОС

Прежде чем перейти к рассмотрению более сложных алгоритмов, хотелось бы всё-таки понять, какие требования накладываются на ГПСЧ, чтобы его можно было считать криптографически стойким ГПСЧ (КСГПСЧ). Чтобы последовательность можно было считать криптографически безопасной псевдослучайной, она должна быть максимально непредсказуемой[9, п. 2.8], т.е. должно быть как можно труднее предсказать, каким будет следующий бит, даже если полностью известен алгоритм или устройство, генерирующее последовательность, и все предыдущие биты потока.

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

Перейдём, наконец, к рассмотрению некоторых примеров «хороших» генераторов, основанных на уже разобранных выше методах.

Нелинейная комбинация РСЛОС

Одним из способов улучшения криптостойкости последовательности, генерируемой РСЛОС, является осуществление преобразования с помощью функции, содержащей нелинейные члены. Для большей ясности воспользуемся фактом из дискретного анализа: любая булева функция может быть единственным образом записана через полином Жегалкина:

Слева — поясняющая схема, справа — представление функции в виде полинома Жегалкина

Т.е. если до этого функцию преобразования можно было представить как сумму по модулю 2 значений битов с отводами, то теперь в неё добавляются комбинации из произведений некоторых значений таких бит. Преимуществом данного метода заключается в том, что из-за нелинейности функции в общем случае неизвестен полиномиальный алгоритм восстановления состояния регистров по предыдущим выходам. Кроме того, сильно увеличивается период генерируемой последовательности. Для улучшения стойкости последовательности рекомендуется брать больше нелинейных членов полинома Жегалкина.

Генераторы с несколькими регистрами сдвига

Ещё одним способом улучшения криптографических свойств последовательности состоит в создании генераторов из нескольких регистров сдвига L1 . . . LM, выходы которых подсоединены к устройству преобразования, задаваемого некоторой булевой функцией.

В каждом i-м регистре ровно Li ячеек, причём регистры подобраны таким образом, чтобы значения их длин были взаимно-простыми величинами, т.е. НОД (Li, Lj) = 1 для i≠j. Булева функция f должна включать слагаемое по одному из входов, т.е. f = . . . + xi + . . . , чтобы значения на выходе функции были равновероятными. Период такого генератора может достигать величины 2L, где L — сумма длин всех регистров, что сильно увеличивает стойкость по сравнению с обычным РСЛОС.

Генератор «стоп-пошёл»

Генератор «стоп-пошёл» представляет из себя объединение двух РСЛОС (условно обозначим их РСЛОС-1 и РСЛОС-2). РСЛОС-2 работает только в том случае, если в предыдущий момент времени выходное значение РСЛОС-1 было равно 1. Такой принцип работы генератора РСЛОС-2 ещё называют тактирвоанием, т.е. можно говорить, что РСЛОС-1 тактирует РСЛОС-2.

Очевидно, что период такого генератора больше, чем каждого РСЛОС по отдельности, однако одним из недостатков является задержка при генерации чисел, зависящая от длины последовательности нулей на выходе РСЛОС-1.

Для увеличения криптостойкости и чтобы избавиться от указанного выше недостатка, может быть использован генератор «стоп-пошёл», состоящий из 3 РСЛОС. При такой конфигурации РСЛОС-2 меняет своё состояние при наличии 1 на выходе РСЛОС-1, а РСЛОС-3 при 0. Выходом генератора является операция побитового сложения выходов РСЛОС-2 и РСЛОС-3. В источнике [4] утверждается, что сложность и длина периода такого генератора обладают хорошими показателями стойкости.

Каскад Голлмана

Каскад Голлмана является некоторым обобщением генератора «стоп-пошёл»: он состоит из последовательности РСЛОС, каждый из которых, кроме начального, тактируется предыдущим. Схема получается такая:

Каскад Голлмана, источник: [6, стр 50]

Если выходом РСЛОС-1 является 1, то тактируется РСЛОС-2. Если выходом РСЛОС-2 является 1 — тактируется РСЛОС-3 и т.д. Выход последнего РСЛОС является выходом генератора.

Каскад Голлмана показывает хорошие результаты: с ростом числа генераторов последовательность приближается к случайной. В своей книге[9] Б. Шнайер рекоемендует использовать как минимум 15 РСЛОС в каскаде.

Алгоритм А5/1

Напоследок хотелось бы разобрать один из алгоритмов, который, хоть и не является криптографически устойчивым, но интересен с той точки зрения, что он применяется для шифрования данных в сетях мобильной связи стандарта GSM. Это так называемый алгоритм А5, первый вариант которого был разработан в 1987 году и и который сейчас обозначается как А5/1, т.к. на данный момент существуют модификации А5/2 и А5/3.

Рассмотрим работу такого генератора: он сотсоит из трёх РСЛОС, длинами 19, 22 и 23 бит. Ны выход подаётся сумма по модулю два всех трёх РСЛОС. В А5 используется условный сдвиг регистров, т.е. на каждом такое регистрв не обязаны сдвигаться.

Схема алгоритма А5/1, источник: [3, стр 113]Система уравнений для генератора А5/1

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

В рассматриваемом алгоритме регистры сдвигаются по определённому правилу: в каждом регистре есть тктовый бит, который определяет сдвиг (восьмой бит C1 для первого регистра, десятый C2, C3- для второго и третьего). На каждом такте вычисляется мажоритарное значение тактового бита m = majotiry (C1, C2, C3) , т.е. по большинству значений вычисляется 0 или 1. Если да данного регистра значение тактового бита совпадает с мажоритарным решением, то регистр сдвигается.

Заключение

Сегодня существует невероятное множество алгоритмов, генерирующих псведослучайные последовательности, которые необходимы во многих областях. В зависимости от решаемой задачи к ГПСЧ могут быть предъявлены различные требования. Для тестирования ГПСЧ на криптостойкость разработано большое количество тестов, оценивающих различные характеристки генераторов [10].

Список литературы:

1. Кнут Д.Э. Искусство программирования (Том 2. Получисленные алгоритмы)

2. nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800–90Ar1.pdf

3. Габидулин Э. М., Кшевецкий А. С., Колыбельников А.И. Защита информации: учебное пособие — М.: МФТИ, 2019

4. C.G. Gunter, «Alternating Step Generators Contolled by de Bruijn Sequenc-es», Advances in Cryptology EUROCRYPT »87 Proceedings, Springer-Verlag, 1988

5. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. — М.: Мир. — 1989

6. Слеповичев И.И. Генераторы псевдослучайных чисел: учебное пособие, 2017

7. https://software.intel.com/sites/default/files/m/d/4/1/d//441IntelR_DRNGSoftwareImplementationGuidefinalAug7.pdf

8. https://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

9. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — Триумф, 2013. — 816 с

10. https://csrc.nist.gov/publications/detail/sp/800–22/rev-1a/final

© Habrahabr.ru