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

Может показаться что эта проблема была решена уже давно, но те же процессоры обзавелись модулями энтропии только в 2012-2014 годах. И на этом прогресс не останавливается: всё доступнее становятся квантовые генераторы энтропии, полностью лишённые изъяна детерминизма. Давайте посмотрим, как от ложного рандома мы пришли к недетерминированному.

Миллион случайных цифр

В  мае 1947 года пока ещё коммерческая компания RAND, созданная как «Think Tank» для нужд ВВС США, занялась решением нетривиальной для тех лет задачи: генерацией большого массива случайных чисел. На Random.org тогда было не зайти, человеческой способности к генерации случайных чисел не доверяли уже тогда, но источники случайности для криптографии, исследований и ряда других задач уже надо было откуда-то брать.

Для этого инженеры RAND сделали то, чего до них почти никто не пробовал — прибегли к компьютерам. Пока ещё аналоговым: их генератор представлял из себя электрическую рулетку в форме колеса на 32 разряда. На колесо поступал импульсный сигнал с частотой 0,1 мегагерца, за раз колесо совершало 3000 оборотов и производило 1 случайное число в секунду, которое передавалось на компьютер. Для этого использовался двоично-десятичный преобразователь, который преобразовывал 20 из 32 чисел (оставшиеся 12 не использовались). Далее на перфоратор IBM поступала только пара из двух двузначных чисел, из которых на перфокарту переносилась последняя цифра. И так процесс повторяли, пока не накопили необходимое количество случайных чисел, перенесённых на перфокарты. Всего было сделано 20 000 перфокарт по 50 цифр на каждой. Далее, чтобы дополнительно перерандомизировать, к каждой цифре добавили по модулю 10,  взятому из соответствующей по расположению цифры на предшествовавшей карте.

Полученный массив чисел подобным образом несколько раз переделывали, пока не добились частоты случайности для каждого отдельного числа в 2 %. Для этого вычисляли отдельные массивы на 125 тысяч цифр с такими вводными:

В конечном итоге, после ещё ряда тестов и перепроверок в 1951 году, в ставшей к тому времени некоммерческой компанией RAND написали книгу под названием «A Million Random Digits with 100,000 Normal Deviates», которая на долгие годы станет настольной для тысяч специалистов и исследователей в самых различных областях и дисциплинах.
Её содержимое выглядело подобным образом:

Страшно представить, что происходило, если номер случайного числа терялся и его приходилось искать самостоятельно, вручную. Ctrl+F и удобных читалок для файлов ведь тоже не было, а закладку легко забыть сделать, да и вкладыш легко мог потеряться.

Какое число вы загадали, мистер Тьюринг?

Физики и математики часто любят шутить, что всё было придумано Гауссом либо Эйлером. В случае же компьютерных наук, куда бы мы ни пошли, везде мы встретим Алана Тьюринга и Джона фон Неймана. Конечно же, без них не могло обойтись и тут.

В 1951 году начались работы над первым в мире коммерчески доступным компьютером общего назначения, Ferranti Mark I. Хотя сам Тьюрин называл этот компьютер Mark II, так как ранее он уже работал вместе с Манчестерским Университетом над созданием схожего компьютера. Помимо прочего, это также был первый компьютер, обладавший аппаратным модулем и поддержкой инструкций для создания энтропии для случайных чисел. Всего с помощью инструкции /W он мог помещать 20 случайных битов в младшие половины регистра, беря в качестве источника энтропии «шум», создаваемый сопротивлением в резисторе.

Однако идея Тьюринга по созданию случайных чисел аппаратным методом слишком опережала своё время. Для программистов той эпохи, не имевших привычных нам инструментов разработки и отладки, это была настоящая головная боль. Из-за своей недетерминированной природы аппаратный метод генерации случайных чисел внёс слишком много неопределённости в ранее непредсказуемую среду. Надёжность и предсказуемость в тот исторический период были в приоритете у разработчиков программного обеспечения, а программы, использующие эту инструкцию /W, по своей природе не могли быть запущены так, чтобы можно было пошагово повторить их исполнение. 

Новая, случайная надежда

Прошло почти полвека с создания Тьюрингом инструкций и аппаратной поддержки генерации случайных чисел для компьютеров. И вот, неожиданно для всех, в 1999 году Intel добавляет в свой чипсет i810 аппаратный генератор случайных чисел.
Компания не стала изобретать велосипед: как и в Ferranti Mark I, модуль Intel RNG в качестве источника энтропии использовал шум, получаемый с резистора, измеряя, как под воздействием тепла меняется сопротивление резистора, а с ним и напряжение.

Однако в Intel также зачем-то решили применить фон Неймановский экстрактор случайности, разработанный им в 1951 году и по сей день активно использующийся, но предназначенный для псевдослучайных чисел. Зачем же его использовать для равномерного распределения вывода с аппаратного генератора, и не делает ли это медвежью услугу?

В Intel отмечают, что одно из последствий использования корректора — нестабильный битрейт на выходе, с примерным уровнем преобразования 6 бит на входе и 1 на выходе, и общей пропускной способностью чуть выше 75 Кбит/с.

И зачем всё это нужно? Более 50 лет ведь как-то жили же без таких модулей. Верно, но тут есть нюанс: более детерминированные механизмы генерации случайных чисел более чем реально предсказуемы и взламываемы, нет даже нужды ждать, когда наконец-то выйдут квантовые компьютеры. Одной из наиболее известных уязвимостей детерминированных генераторов было открытие в 1994 году механизма подбора ключа шифрования к SSL-сертификату веб-сервера Netscape. Для его реверс-инжиниринга требовалось знать всего лишь три переменные: время суток, идентификатор процесса и идентификатор родительского процесса. Но и позднее, из более безобидного: в 2009 у энтузиастов получалось взломать HackerNews. С учётом того, что культура безопасности — это то, что в ИТ традиционно находится под постоянным давлением, требующим постоянного развития.  При должном внимании подобных уязвимостей и сейчас можно найти немало в современном софте. И как не трудно догадаться, нововведение Intel с 1999 года особой популярности не обрело.

Настоящая случайность

В 2012 году на рынок выходит новое поколение процессоров Intel из линейки Ivy Bridge. Конца света не случилось, но зато появились две новые процессорные инструкции: RDSEED и RDRAND. Последняя истинно случайная, работает на аппаратном уровне, но более медленная, а вторая использует первую как ключ для генерации. Реализовали это с помощью изменений на архитектурном уровне, вместо использования аналогового терморезистора генератор стал цифровым.

Теперь он состоит из пары инверторов — логических вентилей, меняющих входное значение на противоположное. Выход одного инвертора подключён на вход другого. Если на выходе у одного 0, то другой инвертор получает его на входе и, соответственно, выдаёт 1. Если же первый инвертор выдаёт 1, то второй инвертор будет выдавать 0. Дополнительно в цепь к ним добавлены два транзистора, подающих на входе и на выходе обоих инверторов 1.

И откуда же тут взяться случайности, если логические схемы детерминированней некуда? В сферическо-вакуумном пространстве математической логики это возможно. Однако в реальном мире логические вентили материальны и имеют физические свойства. Когда тактовый генератор отключает транзисторы, у инверторов на выходах оказывается одинаковое состояние, а они по своей природе стремятся принять противоположное. И какой инвертор поменяется на 0? Неизвестно. В теории, одинаковое состояние обоих инверторов может сохраняться вечно, но в реальности любое воздействие — от теплового шума до случайных колебаний в атомах — приводит цепь в одно из двух возможных устойчивых состояний.

Без дополнительного запаса прочности, как и в аналоговом генераторе, не обошлось, но вместо экстрактора фон Неймана используется уже более продвинутый нормализатор на основе алгоритма AES.

В 2015 поддержку инструкций RDRAND и RDSEED добавила в свои процессоры и AMD.
Примерно в это же время аналогичные инструкции и аппаратные модули появляются для ARM-процессоров. Ядро Linux получает поддержку этих инструкций, однако для генерации рандома в /dev/urandom им не доверяет, сомневаясь в их безопасности и оставаясь верным своим генераторам случайных чисел на основе иных источников.

По сей день RDRAND и RDSEED остаются основными инструкциями в тех случаях, когда требуется генерация случайных чисел на аппаратной основе. Несмотря на сложность их принципов работы и того, что на слуху они достаточно редко, применение их в коде под Linux не является затруднительным. Вот пример кода на C++ с их использованием:

#include <iostream>
#include <cstdint>
#include <random>

// rdseed
void rdseed() {

uint64_t result;
asm volatile("rdseed %0" : "=r" (result));

std::cout << "Random value by rdseed: " << result << std::endl;

}

//rdrand
void rdrand(){

std::random_device rd;
unsigned long long randomValue = rd();

std::cout << "Random value by rdrand: " << randomValue << std::endl;
}

int main() {

rdseed();
rdrand();

return 0;
}

В квантовый мир

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

Один из наиболее популярных методов получения энтропии на основе квантовых явлений — это анализ скорости прибытия фотона на детектор, в определённый отрезок времени.

Впрочем, никто не запрещает использовать известную, наверное, всем особенность света, обнаруженную в знаменитом эксперименте с двойной щелью: корпускулярно-волновой дуализм. То есть поведение света и как частицы, и как волны. Что и сделал один энтузиаст в своём простом генераторе, с поправкой на то, что выдавать он может либо 0, либо 1, наравне с подбросом монетки. Но от того менее занимательной идея не становится.

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

Заключение

Криптография, шифрование и случайность используются везде, буквально. От генерации миров в Minecraft до веб-сертификатов и ключей безопасности, обеспечивающих надёжность ваших транзакций в банке. Но многие даже не задумываются, чем это всё обеспечено, как не задумывались и 30 лет назад. К счастью, современные тенденции идут наоборот в сторону большего внимания к этим вопросам и улучшения состояния информационной безопасности ИТ-систем. Пусть тот же проект Linux не особо доверяет аппаратным генераторам случайных чисел, всё по тем же причинам, что и во времена Тьюринга, недетерминированность — это обоюдоострый меч. Полезный для конечного результата, но больно бьющий по пытающемуся отлаживать проект разработчику. Но теория и историческая практика уже не раз показали, что закрыть глаза и надеяться на «и так сойдёт» — не вариант. В лучшем случае проверку на прочность устроит белый хакер, в худшем — злонамеренный взломщик.

Как и в прошлом веке, конечное решение только за индустрией. Поэтому интересно услышать ваше мнение на этот счёт в комментариях. – Достаточен ли текущий уровень внимания к информационной безопасности в ИТ-индустрии, возможно он наоборот избыточен? Или, быть может, для большей части проектов с избытком хватит и справочника с заранее расписанными вариантами ключей шифрования, которые остаётся только захардкодить в проект?