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

Министерство науки и высшего образования
Российской Федерации
Томский государственный университет

Г. П. Агибалов

ТЕОРИЯ ПСЕВДОСЛУЧАЙНЫХ ГЕНЕРАТОРОВ

Учебное пособие

Томск
2019

УДК 519.7
ББК 22.13я7
A24

A24
Агибалов Г. П. Теория псевдослучайных генераторов:
учеб. пособие. — Томск: Издательский Дом Томского
государственного университета, 2019. — 68 с.

ISBN 978-5-94621-801-6

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

УДК 519.7
ББК 22.13я7

c⃝ Г.П. Агибалов, 2019
c⃝ Томский государственный
ISBN 978-5-94621-801-6
университет, 2019

Предисловие
Материал этого учебного пособия сложился из соответствующих разделов курсов лекций «Криптографические методы защиты информации» и «Методы криптанализа», которые в течение 15 лет автор читал студентам кафедры защиты информации
и криптографии ТГУ по специальности «Компьютерная безопасность». С выделением теории псевдослучайных генераторов
в самостоятельную дисциплину этой специальности стало целесообразным сосредоточить материал к ней в отдельном учебном
пособии, что, собственно, и случилось за одним исключением:
материал по криптанализу таких генераторов на базе их систем
логических уравнений остался в прежней дисциплине и входит
в готовящееся учебное пособие по ней. Главное же содержание
данного пособия, рассчитанного на семестровый курс лекций, касается четырёх тем: общей теории псевдослучайных генераторов
(глава 2), теории линейных (глава 3) и нелинейных (глава 4) генераторов рекуррентных последовательностей и описания ряда
известных генераторов на регистрах сдвига с линейной обратной
связью (LFSR) системами логических уравнений (глава 5).
Общая теория генераторов псевдослучайных последовательностей (ПСП) представлена в пособии теоремами A. C. Yao о равносильности понятий псевдослучайности последовательностей и
их непредсказуемости и о существовании ПСП при наличии односторонних подстановок с так называемыми ядрёными (hard-core)
предикатами.
Для линейных рекуррентных последовательностей доказывается теорема о периоде, описываются частотные свойства таких
последовательностей максимального периода и строится формула для автокорреляционной функции последних над произвольным простым полем.
Для нелинейных рекуррентных последовательностей максимального периода, называемых нормальными рекуррентными
последовательностями, или н.р.п., излагаются различные методы
их построения, свойства булевых функций, порождающих двоичные н.р.п., оценки линейной сложности и степени различимости
последних, распределение таких нрп по их линейной сложности
и алгоритмы вычисления их степени различимости, сформулирован ряд нерешённых проблем и гипотез, касающихся н.р.п.

3

Описание конкретных генераторов ПСП на базе LFSR системами уравнений даётся с расчётом на их криптанализ решением этих систем уравнений, изучаемый автором (и его коллегами)
в научных исследованиях, и на их обобщение заменой LFSR в них
конечными автоматами, представляемое в ещё одном авторском
курсе лекций — «Конечные автоматы в криптографии».
И содержательно, и текстуально излагаемый в пособии материал заимствован из некоторых предыдущих публикаций автора.
Так, главы 2 и 3 в нём совпадают с главами 3 и 4 соответственно из давнего учебного пособия автора «Избранные теоремы начального курса криптографии» (Томск: Изд-во НТЛ, 2005), глава 4 настоящего пособия повторяет одноимённую с ней обзорную
статью автора из журнала «Вестник Томского государственного университета. Приложение», №23, август 2007, c. 4–11, а глава 5 — фрагменты двух давних статей автора, указанных в списке литературы к этой главе. Цитированные в пособии источники
пронумерованы по главам натуральными числами, и в каждой
главе ссылки на конкретный источник производятся по его номеру в этой главе.

С благодарностью

Ирине Анатольевне Панкратовой за организацию издания пособия, за его редактирование и компьютерную вёрстку.

Геннадий Петрович Агибалов
Март 2019

4

1. Псевдослучайные генераторы в криптографии
1.1. Генераторы случайных битов
Безопасность многих криптографических систем зависит от
генерирования в них непредсказуемых величин — битов, чисел,
последовательностей и т. п., таких, как ключевой поток в поточном шифре, секретный ключ в алгоритме шифрования, простые
числа в криптосистеме RSA, подстановки в шифрах замены, запросы в запрос-ответных протоколах идентификации, векторы
инициализации в некоторых режимах блочных шифров, секретное число разового пользования в шифрах и схемах ЦП ElGamal
и др. Во всех этих случаях генерируемые величины должны
быть достаточно большими и случайными — в том смысле, что
вероятность любого конкретного значения, которое выбирается,
должна быть достаточно малой, чтобы не дать криптоаналитику возможности получить преимущества посредством оптимизации поиска на основе этой вероятности. Например, ключевое
пространство AES может иметь размер 2128, а российского стандарта шифрования — 2256. Если секретный ключ k выбирается
с помощью случайного генератора, криптоаналитик в атаке грубой силы будет испытывать в среднем в первом случае 2127, а во
втором — 2255 возможных ключей прежде, чем отгадает правильно ключ. Если же, с другой стороны, ключ k порождается путём
выбора сначала случайного 40-битного секрета s, а затем расширения его до 128- или 256-битного ключа k с использованием
некоторой открытой функции f как k = f(s), то криптоаналитику понадобится испытать в среднем 239 возможных ключей,
получаемых преобразованием каждого возможного значения s
функцией f.
Генератор случайных битов, или RBG (Random Bit Generator) — это устройство (или алгоритм), вырабатывающее последовательность независимых и несмещённых (равновероятных) битов. Его можно использовать и для генерирования (равномерно
распределённых) случайных чисел. Например, случайное целое
в интервале [0, n] может быть получено путём порождения последовательности случайных бит длины ⌊log n⌋ + 1 и преобразования её в целое число. Если это число окажется больше n, его
надо зачеркнуть и сгенерировать другую последовательность.

5

Генератор действительно случайных битов, RBG, требует
естественного (встречающегося в природе) источника случайности. Построение устройства или программы, использующих эту
случайность и вырабатывающих последовательность, свободную
от смещения (неравновероятности) и корреляции, является трудной задачей. Кроме того, для большинства криптографических
приложений RBG не должен быть предметом наблюдения, доступа и манипуляций со стороны злоумышленного криптоаналитика. RBG на основе природных источников случайности подвержены влиянию внешних факторов, а также нарушениям в функционировании. Обязательно регулярное тестирование таких генераторов, в том числе с помощью статистических тестов.
Аппаратные RBG (hardware-based generators). Они используют случайность, которая присуща некоторым физическим явлениям. Такие физические процессы могут производить биты, которые смещены или коррелированы. В этом случае они должны быть подвергнуты методам выравнивания и сглаживания
(de-skewing). Примеры таких физических явлений следующие:
1) промежуток времени между вылетами частиц при радиоактивном распаде; 2) тепловой шум в полупроводниковом диоде
или транзисторе; 3) нестабильность частоты автономного осциллятора; 4) величина заряда ёмкостного конденсатора за определённое время; 5) звук от микрофона или изображение от видео
камеры; 6) турбулентность воздуха в запечатанном драйвере диска, вызывающая флуктуации времени чтения с сектора диска.
Генераторы, основанные на первых двух явлениях, должны
быть пристроены снаружи к устройству, использующему случайные биты, и, следовательно, могут быть подвержены наблюдению или манипуляциям злоумышленника. Генераторы, основанные на автоосцилляторах или ёмкостях, могут быть построены
на СБИС, заключены в крепкие корпуса и тем самым защищены
от активного противника.
Программные RBG (software-based generators). Построение
RBG в виде программ ещё сложнее, чем аппаратно. Процессы, на
которых они основаны, следующие: 1) системные часы; 2) промежутки времени между ударами по клавишам и между движениями мыши; 3) содержимое некоторых буферов; 4) данные,
вводимые пользователем; 5) численные характеристики ОС, такие, как статистика загрузки и сети.

6

Поведение таких процессов может значительно изменяться
в зависимости от различных факторов, в том числе от платформы компьютера. Бывает также трудно предотвратить наблюдения и манипуляции этими процессами со стороны злоумышленника. Например, если он примерно знает, когда случайная последовательность генерировалась, то он может угадать содержимое
системных часов в тот момент с высокой точностью.
Хорошо сделанный программный RBG должен использовать
много источников случайности. Это уменьшает вероятность выхода из строя всех их одновременно и возможность злоумышленника наблюдать и манипулировать ими всеми одновременно. Каждый источник должен браться многократно и последовательности от них должны комбинироваться в одну при помощи некоторой сложно перемешивающей функции. Для этого
рекомендуется применять хэш-функцию типа MD5 или SHA-1
к конкатенации последовательностей, снимаемых со всех источников. Цель перемешивающей функции — извлечь истинную случайность из снятых последовательностей.
Сглаживание, выравнивание (de-skewing). Естественный источник случайных битов может быть дефективным в том, что
выходные биты могут быть смещены (вероятность испускания
источником бита отличается от 1/2) или коррелированы (вероятность испускания источником очередного бита зависит от
предыдущих выпущенных битов). Имеются различные методы
превращения выходных последовательностей такого генератора
в действительно случайные последовательности битов — методы
выравнивания (de-skewing). Предположим, к примеру, что генератор испускает смещённые, но не коррелированные биты, и что
вероятность бита 1 равна p, а бита 0 — (1 − p), где p неизвестное,
но фиксированное число, 0 < p < 1. Если на выходе такого генератора пары битов 10 и 01 заменять на 1 и 0 соответственно, а
пары битов 00 и 11 вычеркивать, то будет получаться последовательность битов, которая является и несмещённой, и некоррелированной. Пример: 100111001011011. . . → 10101. . .
1.2. Генераторы псевдослучайных битов
В идеале секреты, требуемые в криптоалгоритмах и протоколах, должны генерироваться действительно случайно. Выше
мы описали некоторые физические источники случайных битов,

7