Источники настоящих случайных чисел найти трудно. Физические шумы, такие как детекторы событий ионизирующей радиации, дробовой шум в резисторе или космическое излучение могут быть такими источниками. Однако применяются такие устройства в приложениях сетевой безопасности редко. Сложности также вызывают грубые атаки на подобные устройства. Альтернативным решением является создание некоторого набора из большого количества случайных чисел и опубликование его в некотором словаре. Тем не менее, и такие наборы обеспечивают очень ограниченный источник чисел по сравнению с тем количеством, которое требуется приложениям сетевой безопасности. Хотя данные наборы действительно обеспечивает статистическую случайность, они не достаточно случайны, так как противник может получить копию словаря.
Криптографические приложения используют для генерации случайных чисел особенные алгоритмы. Эти алгоритмы заранее определены и, следовательно, генерируют последовательность чисел, которая теоретически не может быть статистически случайной. В то же время, если выбрать хороший алгоритм, полученная численная последовательность будет проходить большинство тестов на случайность. Такие числа называют псевдослучайными числами.
2. Детерминированные ГПСЧ
Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые их свойства. Как сказал Джон фон Нейман, « всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений ».
Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и составляет около 2 n /2 , где n — размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2n . Если порождаемая ГПСЧ последовательность сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений.
Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:
- Слишком короткий период/периоды.
- Последовательные значения не являются независимыми.
- Некоторые биты «менее случайны», чем другие.
- Неравномерное одномерное распределение.
- Обратимость.
В частности, алгоритм RANDU, десятилетиями использовавшийся на мейнфреймах, оказался очень плохим [1] [2] , что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.
Генератор случайных чисел
... алгоритмы получения случайных чисел называют генераторами случайных чисел (ГСЧ) или датчиками случайных чисел. ... числа называются псевдослучайными. В дальнейшем мы будем рассматривать лишь программные генераторы псевдослучайных чисел. 2. Характеристики ГСЧ Последовательности случайных чисел, ... таким образом, чтобы обеспечить хорошую «случайность» значений при считывании. Очень часто используются ...
Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, регистр сдвига с линейной обратной связью, Generalized feedback shift register.
Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (2 19937 −1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод).
Однако, существуют алгоритмы, распознающие последовательность, порождаемую вихрем Мерсенна, как неслучайную.
3. ГПСЧ с источником энтропии или ГСЧ
Наравне с существующей необходимостью генерировать легко воспроизводимые последовательности случайных чисел, также существует необходимость генерировать совершенно непредсказуемые или попросту абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (ГСЧ — англ. random number generator, RNG ).
Так как такие генераторы чаще всего применяются для генерации уникальных симметричных и асимметричных ключей для шифрования, они чаще всего строятся из комбинации криптостойкого ГПСЧ и внешнего источника энтропии (и именно такую комбинацию теперь и принято понимать под ГСЧ).
Почти все крупные производители микрочипов поставляют аппаратные ГСЧ с различными источниками энтропии, используя различные методы для их очистки от неизбежной предсказуемости. Однако на данный момент скорость сбора случайных чисел всеми существующими микрочипами (несколько тысяч бит в секунду) не соответствует быстродействию современных процессоров.
В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора. Сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ используют традиционные испытанные, хотя и медленные, методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в PGP и Yarrow [3] , или взаимодействия между потоками, как, например, в Java secure random.
3.1. Пример простейшего ГСЧ с источником энтропии
Если в качестве источника энтропии использовать текущее время, то для получения натурального числа от 0 до N достаточно вычислить остаток от деления текущего времени в миллисекундах на число N +1. Недостатком этого ГСЧ является то, что в течение одной миллисекунды он выдает одно и то же число.
3.2. Примеры ГСЧ и источников энтропии
[Электронный ресурс]//URL: https://drprom.ru/referat/datchiki-sluchaynyih-chisel/
| ГПСЧ | Достоинства | Недостатки | ||
|---|---|---|---|---|
| /dev/random в UNIX/Linux | Счётчик тактов процессора, однако собирается только во время аппаратных прерываний | LFSR, с хешированием выхода через SHA-1 | Есть во всех Unix, надёжный источник энтропии | Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ ( /dev/urandom ) |
| Yarrow от Брюса Шнайера[3] | Традиционные методы | AES-256 и SHA-1 маленького внутреннего состояния | Гибкий криптостойкий дизайн | Медленный |
| Microsoft CryptoAPI | Текущее время, размер жёсткого диска, размер свободной памяти, номер процесса и NETBIOS-имя компьютера | MD5-хеш внутреннего состояния размером в 128 бит | Встроен в Windows, не «застревает» | Сильно зависит от используемого криптопровайдера (CSP).
|
| Java SecureRandom | Взаимодействие между потоками | SHA-1-хеш внутреннего состояния (1024 бит) | Большое внутреннее состояние | Медленный сбор энтропии |
| Chaos от Ruptor [4] | Счётчик тактов процессора, собирается непрерывно | Хеширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia-генератора | Пока самый быстрый из всех, большое внутреннее состояние, не «застревает» | Оригинальная разработка, свойства приведены только по утверждению автора |
| RRAND от Ruptor [5] | Счётчик тактов процессора | Зашифровывание внутреннего состояния поточным шифром EnRUPT в authenticated encryption режиме (aeRUPT) | Очень быстр, внутреннее состояние произвольного размера по выбору, не «застревает» | Оригинальная разработка, свойства приведены только по утверждению автора. Шифр EnRUPT не является криптостойким. |
4. ГПСЧ в криптографии
Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а также различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или зерном (англ. seed ), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.
Хотя многие криптостойкие ГПСЧ или поточные шифры предлагают гораздо более «случайные» числа, такие генераторы гораздо медленнее обычных арифметических и могут быть непригодны во всякого рода исследованиях, требующих, чтобы процессор был свободен для более полезных вычислений.
В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются RC4, ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюма, Блюма и Шуба, а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.
4.1. Примеры криптостойких ГПСЧ
4.1.1. Циклическое шифрование
В данном случае используется способ генерации ключа сессии из мастер-ключа. Счетчик с периодом N используется в качестве входа в шифрующее устройство. Например, в случае использования 56-битного ключа DES может использоваться счетчик с периодом 256. После каждого созданного ключа значение счетчика повышается на 1. Таким образом, псевдослучайная последовательность, полученная по данной схеме, имеет полный период: каждое выходное значение Х0, Х1,…XN-1 основано на разных значениях счетчика и, по этому, Х0 ≠ X1 ≠ XN-1. Так как мастер-ключ является секретным, легко показать, что любой секретный ключ не зависит от знания одного или более предыдущих секретных ключей.
4.1.2. ANSI X9.17
ГПСЧ из стандарта ANSI X9.17 используется во многих приложениях финансовой безопасности и PGP. В основе этого ГПСЧ лежит тройной DES. Генератор ANSI X9.17 состоит из следующих частей:
- Вход: генератором управляют два псевдослучайных входа. Один является 64-битным представлением текущих даты и времени, которые меняются каждый раз при создании числа. Другой является 64-битным исходным значением. Оно инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел.
- Ключи: генератор использует три модуля тройного DES. Все три используют одну и ту же пару 56-битных ключей, которая держится в секрете и применяется только при генерации псевдослучайного числа.
- Выход: выход состоит из 64-битного псевдослучайного числа и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа.
- DTi — значение даты и времени на начало i-ой стадии генерации.
- Vi — начальное значение для i-ой стадии генерации.
- Ri — псевдослучайное число, созданное на i-ой стадии генерации.
- K1, K2 — ключи, используемые на каждой стадии.
Тогда:
Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.
5. Аппаратные ГПСЧ
Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы и также держатся в секрете. Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA- или ASIC-ячеек).
Из-за таких строгих требований к аппаратным ГПСЧ очень трудно создать криптостойкий генератор, поэтому до сих пор все известные аппаратные ГПСЧ были взломаны. Примерами таких генераторов являются Toyocrypt и LILI-128, которые оба являются LFSR-генераторами, и оба были взломаны с помощью алгебраических атак.
Из-за недостатка хороших аппаратных ГПСЧ производители вынуждены применять имеющиеся под рукой гораздо более медленные, но широко известные блочные шифры (DES, AES) и хеш-функции (SHA-1) в поточных режимах.
Примечания
Литература
[Электронный ресурс]//URL: https://drprom.ru/referat/datchiki-sluchaynyih-chisel/
- Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М .: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 экз . — ISBN 5-8459-0081-6 (рус.) ISBN 0-201-89684-2 (англ.)
Данный реферат составлен на основе .
