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

 

 

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ  

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ 

«РОССИЙСКИЙ УНИВЕРСИТЕТ 

ТРАНСПОРТА (МИИТ)» 

ИНСТИТУТ ТРАНСПОРТНОЙ ТЕХНИКИ И СИСТЕМ УПРАВЛЕНИЯ 

(ИТТСУ) 

Кафедра «Управление и защита информации» 

 

 

 

 

 

Е.Г. Воронина, В.Г. Сидоренко 

 

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

 

 

 

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

 

 

 

 

 

 

 

 

Москва – 2018

 

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ 

 ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ 

«РОССИЙСКИЙ УНИВЕРСИТЕТ 

ТРАНСПОРТА (МИИТ)» 

ИНСТИТУТ ТРАНСПОРТНОЙ ТЕХНИКИ И СИСТЕМ УПРАВЛЕНИЯ 

(ИТТСУ) 

Кафедра «Управление и защита информации» 

 

 

 

 

 

Е.Г. Воронина, В.Г. Сидоренко 

 

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

 

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

для студентов 

специальности 10.05.01 «Компьютерная безопасность» 

 

 

 

 

 

 

 

 

Москва – 2018 

 

УДК 519.2 
В-75 

 

 

 

Воронина Е.Г., Сидоренко В.Г. Генераторы случайных чисел: Учебное пособие. – М.: 

РУТ (МИИТ). 2018. – 80 с. 

 
В учебном пособии излагаются методы генерации случайных чисел, являющиеся 

основой решения многих задач информационной безопасности, в частности, задач 
криптографической 
и 
стеганографической 
защиты 
информации. 
Учебное 
пособие 

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

 
Рецензенты: 
д.т.н. Ромашкова О.Н. (Московский городской педагогический университет) 
к.т.н. Голдовский Я.М. РУТ (МИИТ) 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

© РУТ (МИИТ), 2018

СОДЕРЖАНИЕ 

ВВЕДЕНИЕ .................................................................................................................................... 4 

1. Уязвимости CWE ...................................................................................................................... 5 

2. Случайные числа. Генераторы случайных чисел .................................................................. 8 

2.1. Генераторы псевдослучайных последовательностей...................................................... 9 

2.2. Криптографически устойчивые генераторы случайных чисел .................................... 25 

2.3. Генераторы реальных случайных чисел......................................................................... 37 

2.4. Программная реализация генераторов случайных чисел ............................................. 41 

3. Статические тесты .................................................................................................................. 43 

3.1. Примеры статических тестов .......................................................................................... 43 

3.2. Программная реализация статических тестов ............................................................... 47 

3.3. Результаты применения статических тестов к исследуемым ГПСЧ ........................... 50 

ЗАКЛЮЧЕНИЕ............................................................................................................................ 53 

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ ....................................................................... 54 

Приложение А .......................................................................................................................... 55 

Приложение Б ........................................................................................................................... 56 

Приложение В .......................................................................................................................... 57 

Приложение Г ........................................................................................................................... 58 

Приложение Д .......................................................................................................................... 60 

Приложение Е .......................................................................................................................... 64 

Приложение Ж ......................................................................................................................... 69 

Приложение З ........................................................................................................................... 71 

Приложение И .......................................................................................................................... 74 

Приложение К .......................................................................................................................... 76 

Приложение Л .......................................................................................................................... 79 

 
 

 
 

ВВЕДЕНИЕ 

В настоящее время, в век мультимедийных технологий, проблема защиты 

информации стоит особенно остро. Информационные системы активно развиваются, но 

также развиваются и методы взлома, хищения и несанкционированного доступа к 

информации, представленной в цифровом виде  

Защита информации ведется с древнейших времен. Основными направлениями 

данного вопроса являются криптография и стеганография.  

Слово «криптография» в переводе с древне греческого означает «скрыто пишу». 

Данная наука занимается методами обеспечения конфиденциальности информации, 

невозможности прочтения информации, нарушения ее целостности и т.д. Криптография 

обеспечивает сокрытие содержимого сообщений за счет их шифрования.  

Генерирование и использование случайных чисел при шифровании сообщения – 

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

одноразовых паролей, одноразовых шифроблакнотов, в схемах цифровой подписи и т.д. 

В начале XX века ГСЧ имитировались простыми случайными экспериментами: 

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

В 1946 году Джоном фон Нейманом впервые был предложен компьютерный алгоритм 

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

случайных чисел. 

В данном учебном пособии рассмотрены различные методы генерации случайных 

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

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

 
 

1. Уязвимости CWE 

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

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

потребность в криптографически стойких ГСЧ. Такие уязвимости были выявлены и 

сгруппированы в Common Weakness Enumeration (CWE) [1]. 

Common Weakness Enumeration (общее перечисление слабостей) – это проект 

сообщества разработчиков программного обеспечения, целью которого является создание 

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

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

использоваться для выявления, исправления и предотвращения этих недостатков. 

Выделяют некоторые уязвимости из CWE, связанные с некачественным 

генерированием случайных чисел: 

– CWE-330: использование недостаточно случайных значений; 

– CWE-331: недостаточная энтропия; 

– CWE-334: небольшое пространство случайных значений; 

– CWE-335: ошибка инициализации ГСЧ; 

– CWE-338: использование криптографически слабого ГСЧ; 

– CWE-340: проблемы прогнозируемости; 

– CWE-341: прогнозируемость по наблюдаемому состоянию; 

–CWE-342: прогнозирование точного значения по предыдущим значениям; 

– CWE-343: прогнозирование диапазона значений по предыдущим значениям. 

CWE-330: использование недостаточно случайных значений 

Когда программное обеспечение генерирует предсказуемые значения в контексте, 

требующем непредсказуемости, злоумышленник может угадать следующее значение, 

которое будет сгенерировано, и использовать это значение для олицетворения другого 

пользователя или доступа к конфиденциальной информации. 

CWE-331: недостаточная энтропия 

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

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

вероятны, чем другие. 

Злоумышленник может угадать генерируемые случайные числа и получить 

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

аутентификации и авторизации. 

Для того, чтобы избежать данную проблему, требуется определить необходимую 

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

достигнуто за счет увеличения количества бит объектов, таких как ключи и исходные 

данные. 

CWE-334: небольшое пространство случайных значений 

Количество возможных случайных значений меньше, чем необходимо для 

продукта, что делает его более восприимчивым к атакам грубой силы. 

Злоумышленник может легко угадать используемые значения. Это может привести 

к несанкционированному доступу к системе, если исходные данные используются для 

аутентификации и авторизации. 

CWE-335: ошибка инициализации ГСЧ. 

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

Если ГСЧ используется неправильно, например, используя одно и то же входное 

значение для каждой инициализации или используя предсказуемое исходное значение, 

тогда злоумышленник может легко угадать его, следовательно, может предсказать и 

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

доступу к системе, если исходные данные используются для аутентификации и 

авторизации. 

Когда некриптографический ГСЧ используется в криптографическом контексте, он 

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

CWE-338: использование криптографически слабого ГСЧ. 

Часто ГСЧ не предназначен для криптографии. Иногда посредственный источник 

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

используют случайные числа. Слабые генераторы обычно потребляют меньше 

вычислительной мощности и/или не используют ценные, конечные, энтропийные 

источники в системе. Хотя такие ГСЧ могут иметь очень полезные функции, эти же 

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

Если ГСЧ используется для 
аутентификации и авторизации, например, 

идентификатор сеанса или исходные данные для генерации криптографического ключа, 

тогда злоумышленник может легко угадать идентификатор или криптографический ключ 

и получить доступ к ограниченной функциональности. 

CWE-340: проблемы прогнозируемости 

Слабые стороны этой категории связаны со схемами, которые генерируют числа 

или идентификаторы, которые более предсказуемы, чем требуется приложению. 

CWE-341: прогнозируемость по наблюдаемому состоянию 

Число 
или 
объект 
предсказуемы 
на 
основании 
наблюдений, 
которые 

злоумышленник может сделать о состоянии системы или сети, таких как время, 

идентификатор процесса и т.д.  

Эта слабость может быть использована злоумышленником несколькими способами 

в зависимости от контекста. Если для генерации идентификаторов или ключей, которые 

используются 
в 
механизмах 
защиты, 
используется 
прогнозируемое 
число, 

злоумышленник может получить несанкционированный доступ к системе. Если для 

хранения конфиденциальной информации используются предсказуемые имена файлов, 

злоумышленник может получить доступ к системе и к информации в файле. 

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

для исходных значений ГСЧ. 

Также стоит использовать ГСЧ, который использует вход из высококачественных 

источников, таких как аппаратные устройства с высокой энтропией. Однако не следует 

повторять это слишком часто, иначе источник энтропии может блокироваться. 

CWE-342: прогнозирование точного значения по предыдущим значениям 

 Точное значение или случайное число можно точно предсказать, наблюдая 

предыдущие значения. 

Стоит 
использовать 
ГСЧ, 
который 
периодически 
использует 
вход 
из 

высококачественных источников, таких как аппаратные устройства с высокой энтропией.  

CWE-343: прогнозирование диапазона значений по предыдущим значениям 

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

наблюдений предыдущих значений. В некоторых случаях злоумышленник не может 

предсказать точное значение, которое будет производиться дальше, но может значительно 

сузить возможности. Это уменьшает количество усилий для атаки грубой силы. 

Например, предположим, что продукт генерирует случайные числа от 1 до 100, но он 

всегда дает большее значение, пока не достигнет 100. Если генератор создает 80, тогда 

злоумышленник знает, что следующее значение будет где-то между 81 и 100. Вместо 

этого из 100 возможностей, злоумышленнику нужно только рассмотреть 20. 

Для решения этой проблемы следует применять ГСЧ, который использует вход из 

высококачественных источников, таких как аппаратные устройства с высокой энтропией. 

Однако не стоит повторять это слишком часто, иначе источник энтропии может 

блокироваться. 
 

2. Случайные числа. Генераторы случайных чисел 

При выполнении криптографических преобразований используются различные 

случайные первичные состояния или готовые последовательности. Соответственно, 

криптографическая безопасность таких преобразований в первую очередь зависит от 

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

На настоящий момент компиляторы имеют собственную реализацию генерации 

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

Основная трудность таких генераторов на персональном компьютере (ПК) 

заключается в том, что ПК детерминированы. Они могут быть только в конкретном 

количестве состояний (число состояний конечно). Отсюда следует, что каждый датчик 

случайных чисел (ДСЧ) периодический. Так как все периодическое может быть 

предсказано, соответственно результаты работы ДСЧ не случайны. 

Единственное, 
что 
под 
силу 
ПК 
– 
это 
генерация 
псевдослучайной 

последовательности. Период этой последовательности псевдослучайных чисел должен 

быть таким, чтобы она не была периодичной. Непериодические части последовательности 

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

случайности. 

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

отвечает всем требованиям статических тестов. Статическая случайность является 

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

Последовательность является криптографически надежной, только если она 

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

знание алгоритма (или аппаратного обеспечения) и всех предыдущих бит потока. 

Криптографически 
надежная 
псевдослучайная 
последовательность 
так 
же 

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

Генератор является случайным, если он не воспроизводится (при повторном 

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

последовательности). Кроме того, случайная последовательность не может быть сжата. 

 

 
 

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

Во многих алгоритмах шифрования, в частности в потоковых шифрах, 

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

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

может быть точно воспроизведен на стороне получателя. Чем больше сгенерированный 

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

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

простой криптографический анализ здесь не возможен [2]. 

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

автомат с памятью, состоящий из трех блоков: 

– блока памяти, который хранит информацию о состоянии генератора; 

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

состояния;  

– функции перехода, которая определяет новое состояние, на которое генератор 

переходит на следующем шаге. 

На сегодняшний день существует несколько тысяч различных генераторов 

псевдослучайных чисел. 

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

которые наиболее подходят для компьютерной криптографии. 

Использование стандартных функций языков программирования          

Функция Rand создает псевдослучайное число в указанном диапазоне (метод 

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

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

специальной функции. Для C это функция srand, в Object Pascal начальное значение 

устанавливается через свойство RandSeed. В реальных криптосистемах эта функция не 

используется, так как она имеет низкую криптостойкость из-за ее доступности [3, 4]. 

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

Линейный конгруэнтный генератор (ЛКГ) представляет собой последовательность 

чисел от 0 до m-1, которая удовлетворяет рекуррентному выражению: 

 

𝑋𝑘+1 = 𝑋𝐾𝑎 + 𝑏 𝑚𝑜𝑑 𝑚 

 

где X0 - начальное значение,  

a - множитель, 

b - приращение, 

 m - модуль.  

Такой генератор имеет период меньше m. В случае если a, b и m выбраны 

правильно, генератор будет с максимальной длиной и с периодом m (например, gcd (m, b) 

= 1, где gcd – наибольший общий делитель (НОД)) [5]. 

Если b = 0, то ЛКГ имеет вид: 

 

𝑋𝑘+1 = 𝑋𝐾𝑎 𝑚𝑜𝑑 𝑚 

 

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

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

a может принимать значения 75 или 16807, а m -  231-1=2147483647. У такого генератора 

будет максимальный период повторения. Эти константы были представлены Парком и 

Миллером, поэтому ЛКГ, описываемый ниже приведенным выражением, называется 

генератором Парка-Миллера: 

 

Xk+1 = 75Xk mod(231-1)  

 

 Основным преимуществом ЛКГ является их скорость из-за небольшого количества 

операций на каждый байт и простоты реализации. Однако такие генераторы редко 

используются в криптографии, потому что они предсказуемы. Впервые ЛКГ взломаны 

Д.Бояр  [3]. 

Нелинейные конгруэнтные генераторы 

В некоторых случаях используются квадратичные и кубические конгруэнтные 

генераторы (КГ), которые имеют более высокую устойчивость к взлому [6]. 

Квадратичный конгруэнтный генератор:  

 

𝑋𝑘+1 = (𝑎𝑋𝑘

2 + 𝑏𝑋𝑘 + 𝑐)𝑚𝑜𝑑 𝑚 

 

Кубический конгруэнтный генератор: 

 

𝑋𝑘+1 = ( 𝑎𝑋𝑘

3 + 𝑏𝑋𝑘

2 + 𝑐𝑋𝑘 + 𝑑)𝑚𝑜𝑑 𝑚