Пишу, по большей части, про историю, свою жизнь и немного про программирование.

/dev/random

В комментариях мне вопрос задали — откуда в компьютере взяться случайным числам. Казалось бы — там же всё детерминированно. С одной стороны — да, с другой стороны…

Помню, в «Спектруме» (это компьютер, на котором я работал больше всего в детстве), в Бейсике, был оператор RANDOMIZE — инициализация генератора случайных чисел. Если вызвать его с каким-то фиксированным параметром, то генератор (его значения выдавала функция RND) возвращал всегда одну и ту же цепочку чисел. Так у многих языков устроено:

bolk@Bolk /$ php -r 'mt_srand(1); echo mt_rand();'
1244335972
bolk@Bolk /$ php -r 'mt_srand(1); echo mt_rand();'
1244335972

Если же вызывать RANDOMIZE без параметров, то его значение инициализируется текущим временем. Это уже лучше, потому что в данном случае элемент случайности вносит сам пользователь — как просчитать когда он запустит программу? Какое будет время на часах? На «Спектруме» отследить запуск программы не получится, а без этого нельзя ответить на вопрос какое значение выдаст генератор случайных чисел.

Но на компьютерах посложнее, например, на том, с которого вы сейчас это читаете, отследить запуск проще простого, посмотреть в этот момент на часы — ещё проще. Что делать? Значит надо собирать больше «шумов» окружающего мира.

Какие «шумы» может собирать компьютер вокруг себя?

Как уже было сказано, сильную сумятицу в стройность машинной логики вносит пользователь, грех не пользоваться: нажатия клавиш, движения мышкой, запуск программ, управление ими. Ещё можно, например, снимать значения с загрузки процессора, со списка процессов, занимаемой процессами память и расходуемого время (при условии, что на машине работает сейчас пользователь), вполне источник случайных данных. Ведь эти значения зависят от действий пользователя.

Что делать, когда пользователь пошёл налить себе кофе? Вполне можно использовать шумы внешнего мира. Шумы в прямом смысле, с микрофона послушать что там снаружи происходит — окружающие звуки или просто шумы аудиотракта в отсутствие микрофона. Можно глянуть, что там бегает по сети — широковещательную активность других пользователей. Что ещё? Мало ли у компьютера датчиков? Например, можно смотреть что у нас там на с температурой на процессоре, которая зависит и от температуры в комнате, и от собственных шумов схемотехники датчиков.

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

Температурные датчики на «Маке» (12.60КиБ)

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

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

В юникс-подобных системах есть специальный файл, лежащий в каталоге «/dev» — «random», обращение к нему как раз возвращает данные из этого буфера. А что будет, если данные в буфере кончаются? Посмотреть мне сейчас негде, я в машине, в пробке это всё пишу, а мобильный интернет какой-то медленный сегодня, но насколько я помню, процесс, читающий из «/dev/random» будет просто ждать появления данных. На случай, если вам ждать не хочется, есть другое устройство — «/dev/urandom», которое будет отдавать менее случайные числа, если кончились случайные, такой вот недостаток.

Под занавес, наверное нужно прояснить — для чего нужны такие «суперслучайные» числа. Ну, казалось бы, инициализируем временем и все дела, для чего использовать какие-то датчики, устраивать весь этот джаз? Нужно это всё для криптографии. Если случайные числа на вашем компьютере можно будет предугадывать, то можно будет просматривать и вносить изменения в зашифрованное соединение с сайтом вашего банка, вашей почты и так далее. Потеряют надёжность сгенерированные вами сертификаты и тому подобное.

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

26 комментариев
paulradzkov.com 2013

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

http://forum.xda-developers.com/showthread.php?t=1987032%26nocache=0

По моим собственным наблюдениям сильно ничего не изменилось. Лаги изредка появляются.

Евгений Степанищев (bolknote.ru) 2013

Комментарий для paulradzkov.com:

Да, я видел статью на «Хабре».

Alexander 2013

Из курсеровских лекций по криптографии мне запомнилось, что достаточно чуть-чуть ошибиться в генерации случайных чисел, внести минимальный элемент предсказуемости и время взлома шифра меняется с десятилетий на дни.

Евгений Степанищев (bolknote.ru) 2013

Комментарий для Alexander:

Да, такое возможно, так как поле перебора резко сокращается.

Lex Rivera (lex.io) 2013

А некоторые криптоманьяки (ну или серьезные организации) вообще аппаратные генераторы рандомных чисел используют. Они кажется тепловой шум используют в качестве источника, те тут рандом совсем уж «рандомный»

Евгений Степанищев (bolknote.ru) 2013

Комментарий для lex.io:

Да, там используется поведение элементарных частиц. Это уж совсем для маньяков. Кстати, есть любопытный генератор, основанный на шуме Wi-Fi сетей: http://www.freewebs.com/pmutaf/iwrandom.html

Дмитрий Радищев (dibr.livejournal.com) 2013

Комментарий для Евгения Степанищева:

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

Ох. А зачем для прорисовки интерефейса нужны (высокоэнтропийные) случайные числа?..

Евгений Степанищев (bolknote.ru) 2013

Комментарий для dibr.livejournal.com:

Насколько я помню, так и не удалось пока узнать зачем это :)

DuMOHsmol (anothersite.ru) 2013

Ох. А зачем для прорисовки интерефейса нужны (высокоэнтропийные) случайные числа?..

Поговаривают, что работа этой проги в фоне просто держит процессор на максимальной частоте, вот и лагов меньше.

DuMOHsmol (anothersite.ru) 2013

Комментарий для Евгения Степанищева:

P.S. Что-то печальное у меня с комментариями, отправляются только со второго раза.

masterspammer (masterspammer.livejournal.com) 2013

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

Внутреннее Коралио (kalvado.livejournal.com) 2013

Комментарий для lex.io:

А некоторые криптоманьяки (ну или серьезные организации) вообще аппаратные генераторы рандомных чисел используют. Они кажется тепловой шум используют в качестве источника, те тут рандом совсем уж «рандомный»

Более того, Интел это извращение вставлял одно время как стандартную функцию чипсета. Потом вроде, отказались.

Сергей 2013

Комментарий для kalvado.livejournal.com:

Очевидно у вас есть основания называть чужую работу, и неплохую, причём, извращением.
Однако Интел не отказывается, и вряд ли в этой вселенной откажется когда либо -​-​ http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator/0

Внутреннее Коралио (kalvado.livejournal.com) 2013

Комментарий для Сергей:

Я смотрел документацию на последующие чипсеты — я не видел этой фичи. Я не видел библиотек,которые бы использовали эту возможность
Но я видел продающиеся генераторы аппаратного шума. Для меня это все несколько не укладывается в картину «не отказывается и вряд ли откажется»
У вас есть ссылки на библиотеки и даташиты?

Евгений Степанищев (bolknote.ru) 2013

Комментарий для kalvado.livejournal.com:

Я смотрел документацию на последующие чипсеты — я не видел этой фичи. Я не видел библиотек,которые бы использовали эту возможность.

Хорошее начало для песни :-D

Сергей 2013

Комментарий для Евгения Степанищева:

Да, практически ранний «Аквариум» 8-)

Сергей 2013

Комментарий для kalvado.livejournal.com:

Я бы в таком случае назвал извращенцами тех, кто не использует, по-моему, у меня больше оснований. Документация и библиотека есть. Движение, в среде linux, например, тоже есть, вокруг rdrand.

хвв 2013

Извините, конечно, но автор и комментаторы — ламерье в этом вопросе, судя по изречениям :(

Евгений Степанищев (bolknote.ru) 2013

Комментарий для хвв:

Спасибо за Ваше интересное мнение!

Внутреннее Коралио (kalvado.livejournal.com) 2013

Комментарий для Сергей:

Движение, в среде linux, например, тоже есть, вокруг rdrand.

Считая что шумогенераторы появились в 440 чипсетах для П-2... Движнья нет,сказал я-не брадатый!
(раз уж начал говорить стихами, да)

Евгений Степанищев (bolknote.ru) 2014
Евгений Степанищев (bolknote.ru) 2015
vladon 2015

mt_rand этот ваш из PHP — т. е. mt19937 из C++ в реализации PHP (гуглите Mersenne Twister) — его достаточно инициализировать (про-seed-ить) один раз истинно случайным числом (std::random_device в C++, в PHP — не знаю), и уже нельзя (не зная сида) будет его подобрать, даже зная все сгенерированные до этого значения. Ну теоретически, конечно, можно, но раньше Солнце погаснет.

А вот rand (что в PHP, что в C/C++) лучше не использовать вообще. Никогда.

vladon 2015

А особенно нельзя использовать все эти вошедшие даже в туториалы по языкам `rand() % 100` (чтобы получить псевдослучайное значение от 0 до 99) и т. п. Потому что случайность такая будет неравномерно распределённой.

vladon 2015

Комментарий для kalvado.livejournal.com:

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

Всё проще. RDRAND использовали (и Linux, и FreeBSD), но отказались из-за заложенного Интелом (и VIA) бэкдора.

Там суть в том, что Intel заявил, что RDRAND соответствует Dual_EC_DRBG — ГСЧ с бэкдором NSA. Потом, Intel, конечно, начал говорить, что не соответствует всё же, но осадочек остался.

vladon 2015

Комментарий для kalvado.livejournal.com:

А, и из существующих библиотек RDRAND используется в OpenSSL (не по дефолту).