9.6. $RANDOM: генерация псевдослучайных целых чисел
$RANDOM — внутренняя функция Bash (не константа), которая возвращает псевдослучайные целые числа в диапазоне 0 — 32767. Функция $RANDOM не должна использоваться для генераци ключей шифрования.
Пример 9-23. Генерация случайных чисел
Пример 9-24. Выбор случайной карты из колоды
Jipe подсказал еще один способ генерации случайных чисел из заданного диапазона.
Насколько случайны числа, возвращаемые функцией $RANDOM? Лучший способ оценить «случайность» генерируемых чисел — это написать сценарий, который будет имитировать бросание игрального кубика достаточно большое число раз, а затем выведет количество выпадений каждой из граней.
Пример 9-25. Имитация бросания кубика с помощью RANDOM
Как видно из последнего примера, неплохо было бы производить переустановку начального числа генератора случайных чисел RANDOM перед тем, как начать работу с ним. Если используется одно и то же начальное число, то генератор RANDOM будет выдавать одну и ту же последовательность чисел. (Это совпадает с поведением функции random() в языке C.)
Пример 9-26. Переустановка RANDOM
Системный генератор /dev/urandom дает последовательность псевдослучайных чисел с более равномерным распределением, чем $RANDOM. Команда dd if=/dev/urandom of=targetfile bs=1 count=XX создает файл, содержащий последовательность псевдослучайных чисел. Однако, эти числа требуют дополнительной обработки, например с помощью команды od (этот прием используется в примере выше) или dd (см. Пример 12-42).
Есть и другие способы генерации псевдослучайных последовательностей в сценариях. Awk имеет для этого достаточно удобные средства.
Пример 9-27. Получение псевдослучайных чисел с помощью awk
Источник
Случайные числа в Linux(RNG) или как «наполнить» /dev/random и /dev/urandom
Пожалуй всем пользователям Linux известны такие файлы псевдо-устройств как /dev/random и /dev/urandom. Эти устройства являются интерфейсом к генератору случайных чисел ядра(RNG, random number generator).
Случайные числа(они же — непредсказуемый набор битов) очень важны в криптографии. Они являются базовыми кирпичиками для криптографических протоколов. От качества (неповторимости, непредсказуемости) этих чисел зависит стойкость всевозможных TLS-сертификатов, SSH и GPG ключей, сессионных симметричных TLS-ключей и т.д. Так же случайные числа являются основой для генерации UUID’ов, PID’ов, TCP sequence numbers и многого другого.
RNG генерит случайные числа на основе данных из пула энтропии(entropy pool) в ядре Linux. Наполнением этого пула так же занимается RNG и делается это на основе случайных событий в системе таких как: тайминги клавиатуры и дисков, движения мыши, прерывания(interrupts), сетевой трафик.
Пул энтропии имеет фиксированный объем 4096 bits:
Размер пула нельзя изменить, это захардкожено в ядре.
Посмотреть текущий объем данных в пуле:
Доступный объем энтропии постоянно меняется, в зависимости от скорости пополнения и потребления соответственно.
Собственно через /dev/random и /dev/urandom приложения в user space получают эти самые случайные числаданные.
/dev/random является источником случайных данных наивысшего качества которые может предоставить ядро. Но при этом он блокирующийся, что означает, что приложение читающее из /dev/random повиснет в ожидании данных если пул энтропии окажется пустым.
/dev/urandom — unlimited random, не блокирующийся и приложения могут читать из него бесконечно. Предоставляет случайные данные такого же высокого качества что и /dev/random но до тех пор пока пул энтропии не опустеет. Когда пул будет пустым, /dev/urandom продолжит выдавать случайные данные но теоретически сильно меньшего качества.
Настоятельно рекомендуется для любых долго-живущих ключей, например для TLS-сертификатов использовать /dev/random т.к. только он гарантирует качество случайных чисел. Но, большинство приложений таких как Apache, Nginx, sshd и о Боже ssh-keygen, openssl используют /dev/urandom. Тут в принципе понятно Apache, Nginx, sshd не хотят блокироваться при генерации сессионных ключей. Но то, что ssh-keygen и openssl используют по умолчанию /dev/urandom меня поразило. Причем для openssl можно задать устройство при генерации ключей(ниже пример) а вот для ssh-keygen я возможности переопределить поведение не нашел.
В общем не важно откуда читают ваши приложения, нельзя допускать опустошение этого самого пула энтропии и тогда счастье будет и с /dev/urandom.
Прежде чем начать “майнить” энтропию, пара слов о ее корректном использовании из man /dev/random:
The amount of seed material required to generate a cryptographic key equals the effective key size of the key. For example, a 3072-bit RSA or Diffie-Hellman private key has an effective key size of 128 bits (it requires about 2^128 operations to break) so a key generator only needs 128 bits (16 bytes) of seed material from /dev/random.
Например openssl для генерации RSA ключа длиной 10240 bit использует всего 2048 исходного материала из /dev/random:
Как заполнить пул энтропии?
Лучшее решение это использование специальных аппаратных средств(TPM, Trusted Platform Module) или инструкций процессора типа RDRAND(есть в Intel IvyBridge и Haswell процессорах).
Проверить наличие подобных устройств на сервере поможет утилита rngd из пакета rng-tools
Если rngd обнаружит поддерживаемые средства то вам повезло и вы можете запустить сервис rngd. В моем случае их нет)
Собственно задача rngd читать энтропию из аппаратных средств и наполнять ей пул энтропии ядра. Делается это через специальный ioctl вызов(RNDADDENTROPY) интерфейса /dev/random.
Если нет аппаратной поддержки
В интернете можно встретить рекомендации, где предлагают указывать /dev/urandom как источник энтропии для rngd. То есть источником энтропии для ядра по сути будет само ядро). Это довольно сомнительная идея, и я бы не стал так делать и вам не советую. Но ради эксперимента я провел тесты и результаты(которые ниже) тоже довольно не плохие.
Havegd
В основе лежит алгоритм HAVAGE который генерирует энтропию на основе счётчиков и состояний процессора. В силу сложного, многоуровневого устройства процессоров, один и тот же код всегда выполняется за разное время и это не постоянство является основой для алгоритма HAVAGE.
На практике, это user space демон который как и rngd наполняет пул энтропии ядра через ioctl интерфейс /dev/random. при этом не нуждается в источнике энтропии как rngd.
Для centos пакет доступен из epel.
После установки нужно просто запустить сервис. С параметрами по умолчанию haveged будет стараться держать пул энтропии ядра на уровне не ниже 1024.
Тестирование
Без rngd и haveged, команда(ниже будет понятно, что она делает):
Не завершилась за сутки!
rngd с /dev/urandom в качестве источника энтропии
(то, что я вам не рекомендовал)
Тест(худший из 3-х результат):
Тут нужно смотреть на successes, failures, и на input channel speed.
При этом утилизация CPU процессом rngd: 57%
haveged
Тест(худший из 3-х результат):
При этом утилизация CPU процессом haveged:12%
Виртуальные машины
Не рекомендуется использовать haveged внутри ВМ, т.к. там вроде как счетчики CPU не такие точные(типа округляются) и это сказывается на качестве энтропии. Тру путь это использовать virt-ioRNG(qemu-kvm) — паравиртуальное устройство которое будет брать энтропию из пула хоста. Но, это уже совсем другая история…)
Источник
Приложение Б Генератор случайных чисел ядра
Генератор случайных чисел ядра
В ядре Linux реализован генератор случайных чисел, который теоретически может генерировать истинно случайные числа. Генератор случайных чисел собирает в пул энтропии шумы внешней среды, которые поступают из драйверов устройств. Этот пул доступен как в ядре, так и для пользовательских процессов в качестве источника данных, которые не только случайны внутри системы, но и недетерминированы для внешних источников атак. Такие случайные числа используются различными внешними приложениями, особенно для целей криптографии.
Истинно случайные числа отличаются от псевдослучайных чисел, которые генерируются библиотечными функциями языка С. Псевдослучайные числа создаются с помощью детерминированных функций. Хотя такие функции и могут генерировать последовательности чисел, которые обладают некоторыми свойствами истинно случайных чисел, тем не менее такие числа только статистически случайны. Псевдослучайные числа являются детерминированными, потому что если известно хотя бы одно число последовательности, то можно определить и все остальные. Если известно так называемое порождающее число последовательности (seed), то обычно по нему определяется и вся последовательность. Для приложений, которые требуют истинно случайных чисел, как, например, криптография, псевдослучайные числа обычно не подходят.
В отличие от псевдослучайных чисел, истинно случайные числа не зависят от той функции, которая используется для их генерации. Более того, если известен некоторый член последовательности истинно случайных чисел, то внешний наблюдатель не сможет определить, какие числа будет выдавать генератор в будущем, т.е. такой генератор — недетерминированный.
Физический термин энтропия — это мера беспорядка и случайности в любой системе. Энтропия измеряется в единицах энергии на единицу температуры (Джоуль на градус Кельвина). Когда Клод Шеннон (Claude Shennon)[98], создатель информационной теории, искал термин для представления случайности информации, великий математик Джон фон Нейман (John von Neumann)[99] предложил ему использовать термин энтропия, потому что никто толком не понимает, что за этим понятием кроется. Шеннон согласился, и сегодня это звучит как энтропия Шеннона. Некоторые ученые считают, что такое двойное название только вносит путаницу, и когда речь идет об информации, то используют термин неопределенность. Разработчики ядра, наоборот, считают, что «энтропия» — это «круто», и поддерживают использование данного термина.
При рассмотрении генераторов случайных чисел понятие энтропии Шеннона является очень важным. Эта характеристика измеряется в битах на символ. Высокое значение энтропии означает, что в последовательности символов мало полезной (точнее, предсказуемой) информации и много случайного «мусора». Ядро поддерживает пул энтропии, который пополняется данными, возникающими в результате недетерминированных событий, связанных с аппаратными устройствами. В идеале, этот пул содержит полностью случайные данные. Для того чтобы иметь представление о значении энтропии пула, ядро постоянно вычисляет меру неопределенности данных в пуле. По мере того как ядро добавляет данные в пул, оно оценивает меру случайности добавляемых данных. И наоборот, по мере того как данные извлекаются из пула, ядро уменьшает значение оценки энтропии. Соответствующая количественная характеристика называется оценкой энтропии. Если значение оценки энтропии становится равным нулю, то ядро может отказаться выполнять запрос по считыванию данных из пула.
Генератор случайных чисел ядра был предложен в версии 1.3.30 и находится в файле drivers/char/random.c.
Читайте также
Приложение 4 Дерево параметров настройки ядра
Приложение 4 Дерево параметров настройки ядра В этом приложении приведено дерево настроек ядра Linux с настройками, используемыми по умолчанию в дистрибутиве Red Hat Linux 7.2. Используемые соглашения:• [*] – вкомпилировано в ядро;• [ ] – не компилируется;• – вынесено в
6. Генератор идей
6. Генератор идей В разных сферах уже существует что-то, сделанное за клиента, генератор идей – 101 идея по организации детского праздника, 101 идея продающего текста, 101 способ сбросить лишний вес. Почему генератор идей так привлекателен? Потенциальный клиент знает: если
4. Генератор идей
4. Генератор идей «15 идей, как провести классный праздник», «Два лучших способа раскрутки сайтов» – то, что можно сразу начать
Генератор Колпитца
Генератор Колпитца Чтобы описать генератор Колпитца или генератор Хартли, зачастую используется одна и та же схема (рис. 8.16), где Z1, Z2 и Z3 представляют собой полные сопротивления. Условие установления колебаний при этом задается уравнениемZ1 + Z2 + Z3 = 0. Рис. 8.16. Базовая схема
KPT Orb-It (Генератор сфер)
KPT Orb-It (Генератор сфер) Эффект, который создает этот фильтр, может пригодиться нечасто, однако в некоторых случаях он будет незаменим. Представьте себе, например, сцену под водой, где нужно добавить пузырьки воздуха (рис. 8.46), или поверхность стола, на котором рассыпаны
5.28. Генерирование случайных чисел
5.28. Генерирование случайных чисел Если вас устраивают псевдослучайные числа, вам повезло. Именно они предоставляются в большинстве языков, включая и Ruby.Метод rand из модуля Kernel возвращает псевдослучайное число x с плавающей точкой, отвечающее условиям x >= 0.0 и x
Источник
Генерация случайных чисел в Linux и Windows
Заметил, что в линуксе сей процесс происходит намного медленне, чем в винде и это не зависит от используемого языка программирования. Причём, винда стоит под виртуальной машиной, но один и тот же код с генерацией этих чисел выполняется там в среднем в 2 раза быстрее, чем под линуксом.
Где-то в интернете нашёл, что в линуксе по-умолчанию используется криптостойкий генератор случайных чисел, в то время как в винде — обыкновенный.
Собственно, кто-нибудь знает точно в чём причина такого поведения?
Re: Генерация случайных чисел в Linux и Windows
А вы там, часом /dev/random читаете? Тогда попробуйте /dev/urandom, если, конечно, важна именно скорость.
/dev/random конечно медленнее, но оттуда имеет смысл брать только один из seed для генерации ключей и прочего. А на тривиальную генерацию хватает urandom
Re: Генерация случайных чисел в Linux и Windows
> Заметил, что в линуксе сей процесс происходит намного медленне, чем в винде
Что вообще подразумевается под «генератором случайных чисел ОСи»? «генератора случайных чисел независимо от языка программирования»? Какие конкретно генераторы сравнивались? И каким образом происходило сравнение? А-то заявление выглядит бредово. Код в студию.
Re: Генерация случайных чисел в Linux и Windows
Да я понимаю, что первое сообщение немного странное получилось. 🙂 Просто дело в том, что несколько раз приходилось писать небольшие программки, в которых производительность очень сильно зависила от генерации случайных чисел. В итоге получалось, что под виртуальной машиной с виндой они работали примерно в 2 раза быстрее, чем на основной системе с линуксом. Опытным путём установил, что всё дело в собственно генерации. Подобное наблюдалось со стандартным C’шным rand(), с Qt’шным потоко-безопасным qrand() и с D’шным собственным движком. Стало любопытно, в чём же дело. 🙂
Конкретный код пока, к сожалению, привести не могу, ибо там будет очень много мусора, не касающегося темы. Сейчас как раз пытаюсь создать минимально-воспроизводимый пример.
