В качестве инструмента для случайного выбора я не нашел ничего лучше игральных костей, - писал статистик Фрэнсис Гальтон в выпуске журнала Nature за 1890 год. «Когда их встряхивают и бросают в корзину, они так сильно ударяются друг о друга и о ребра плетеной корзины, что дико кувыркаются, и их положение вначале не дает ощутимой подсказки о том, кем они будут, даже после одно хорошее встряхивание и подбрасывание ".

Как мы можем сгенерировать однородную последовательность случайных чисел? Случайность, столь красиво и обильно генерируемая природой, не всегда было легко извлекать и определять количественно. Самые старые известные игральные кости были обнаружены в 24 веке до нашей эры. гробница на Ближнем Востоке. Совсем недавно, около 1100 г. до н. Э. в Китае панцири черепах нагревали кочергой до тех пор, пока они не треснули наугад, и гадалка интерпретировала эти трещины. Спустя столетия гексаграммы И Цзин для гадания были созданы с помощью 49 стеблей тысячелистника, разложенных на столе и разделенных несколько раз, с результатами, аналогичными подбрасыванию монеты.

Но к середине 1940-х годов современный мир требовал гораздо большего количества случайных чисел, чем могли предложить игральные кости или стебли тысячелистника. Корпорация RAND создала машину, которая будет генерировать числа с помощью генератора случайных импульсов. Некоторое время они запускали его и собрали результаты в книгу под названием Миллион случайных цифр со 100 000 нормальных отклонений. То, что сейчас могло показаться абсурдным арт-проектом, тогда было прорывом. Впервые красивая длинная последовательность высококачественных случайных чисел была доступна всем, кто в ней нуждался: ученым, исследователям, математикам. (Книга была переиздана RAND в 2001 году и доступна на Amazon.)

Похожая машина ERNIE, разработанная ныне известной командой по взлому кода Второй мировой войны в Блетчли-парке в 1940-х годах, использовалась для генерации случайных чисел для лотереи премиальных облигаций Великобритании. Чтобы развеять опасения по поводу справедливости и точности ERNIE, почтовое отделение в начале 1960-х сняло отличный документальный фильм под названием Как важно быть E.R.N.I.E. Стоит посмотреть:

В 1951 году случайность была окончательно формализована в реальном компьютере, Ferranti Mark 1, который поставлялся со встроенной инструкцией случайных чисел, которая могла генерировать 20 случайных битов за раз с использованием электрического шума. Функция была разработана Аланом Тьюрингом. Кристофер Стрейчи нашел ему хорошее применение, написав генератор случайных любовных записок. Вот образец любовной записки из программы Дэвида Линка Воскрешение 2009 года:

ДРАГОЦЕННАЯ ЛЮБОВЬ
МОЙ НРАВИТСЯ ГОЛОД ДЛЯ ВАШЕЙ УКРАШЕННОЙ ИНФОРМАЦИИ.
ТЫ МОЙ ЭРОТИЧЕСКИЙ АРДОР: ПОНЯТИЕ МОЕГО ФОНДА. МОЯ ЖАЖДА
ВДОХНОВЛЯЕТ ВАШУ ИНФОРМАЦИЮ. МОЕ СЕРДЦЕ ОБЪЯВЛЕННО ЖЕЛАЕТ ВАШЕГО
БЕЗДЫХАТЕЛЬНОЙ ПРОДОЛЖИТЕЛЬНОСТИ.
ВАШЕ ЛЮБОПЫТНО
M. U. C.

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

Идея генератора псевдослучайных чисел (ГПСЧ) предоставила возможный путь вперед. ГПСЧ - это генератор случайных чисел, выраженный как детерминированная математическая функция. Его можно вызывать повторно для доставки последовательности случайных чисел, но при одних и тех же начальных условиях (если задано одно и то же начальное «начальное» значение) он всегда будет производить одну и ту же последовательность.

Джон фон Нейман разработал ГПСЧ примерно в 1946 году. Его идея заключалась в том, чтобы начать с начального случайного начального значения, возвести его в квадрат и вырезать средние цифры. Если вы несколько раз возведете результат в квадрат и вырежете средние цифры, вы получите последовательность чисел, которая проявляет статистические свойства случайности.

Однако подход фон Неймана не выдержал проверки временем, потому что независимо от того, какое начальное значение использовалось, последовательность в конечном итоге упадет в короткий повторяющийся цикл чисел, например 8100, 6100, 4100, 8100, 6100, 4100, ...

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

В 1949 г. математик Д. Х. Лемер продвинулся к этой идее, создав линейный конгруэнтный генератор (LCG). Вот наивный ГПСЧ под названием Центральный рандомизатор, основанный на подходе Лемера и написанный на JavaScript в 1995 году:

// The Central Randomizer 1.3 (C) 1997 by Paul Houle ([email protected])
// See:  http://www.honeylocust.com/javascript/randomizer.html
rnd.today=new Date();
rnd.seed=rnd.today.getTime();
function rnd() {
  rnd.seed = (rnd.seed*9301+49297) % 233280;
  return rnd.seed/(233280.0);
};

function rand(number) {
  return Math.ceil(rnd()*number);
};

Здесь задействовано несколько магических чисел. Эти числа (обычно простые) были выбраны для максимального увеличения периода - количества итераций до того, как последовательность, сгенерированная rand(), начнет повторяться. Этот PRNG использует текущее время в качестве начального значения, а период составляет не более 233280.

Central Randomizer стал популярным, потому что JavaScript 1.0 не имел встроенной функции Math.random(), и все хотели, чтобы их рекламные баннеры Web 1.0 вращались случайным образом. «Я бы не стал использовать его для хранения секретов, - писал автор Пол Хоул, - но он годится для многих целей».

Однако Интернет действительно должен был хранить секреты. Шифрование транспортного уровня для HTTP-соединений (TLS / SSL) было разработано примерно в 1995 году, и его безопасность зависит от высококачественного PRNG, особенно на стороне веб-сервера. Это развитие могло привести к периоду бурных инноваций в ГСЧ. Если вы посмотрите на все патенты середины 90-х годов на новые генераторы случайных чисел, это будет похоже на более современную версию попыток построить первый самолет.

Наиболее распространенные процессоры середины 1990-х годов не имели инструкции для генерации случайных чисел, поэтому тогда было трудно найти хорошие начальные значения. Это стало настоящей проблемой безопасности, когда Филип Халлам-Бейкер обнаружил, что веб-сервер SSL Netscape (один из крупнейших на рынке в то время) использовал комбинацию текущего времени и пары идентификаторов процессов для заполнения своего генератора случайных чисел. Халлам-Бейкер показал, что злоумышленник может легко угадать начальное значение и расшифровать как можно больше трафика сервера. Угадывание начального значения - обычная атака, хотя она стала более изощренной: вот красивое пошаговое описание успешной атаки на Hacker News за 2009 год.

К 1997 году компьютерным специалистам надоели ограниченные возможности для генерации действительно случайных чисел, поэтому команда из SGI создала LavaRand, которая представляла собой веб-камеру, направленную на пару лавовых ламп на столе. Данные изображения с камеры были отличным источником энтропии - генератором истинных случайных чисел (TRNG), подобным генератору Тьюринга, - и он мог генерировать 165 Кб / с случайных данных. В моде Кремниевой долины оборудование для лавовой лампы было быстро запатентовано.

Основатель Autodesk Джон Уокер, который намеревался распространить случайность по всему миру, создал HotBits, приложение Случайные числа как услугу, поддерживаемое счетчиком Гейгера, которое гарантирует истинную квантовую случайность. Random.org, созданный в 1998 году, бесплатно предоставляет действительно случайные числа. Теперь они предлагают мобильные приложения для действительно случайного подбрасывания монет, бросания игральных костей, тасования карт и т. Д.

Большинство этих изобретений остались незамеченными, но один программный ГПСЧ, названный The Mersenne Twister, разработанный в 1997 году Макото Мацумото (松本 眞) и Такудзи Нисимура (西村 拓 士), является хоум-рангом. В нем прекрасно сочетаются производительность и качество, и он выдержал испытание временем. Он основан на идее регистра сдвига с линейной обратной связью (LFSR), который производит детерминированную последовательность с очень длинными периодами цикла. В текущих реализациях он имеет период 2¹⁹⁹³⁷− 1, и сегодня он по-прежнему является ГПСЧ по умолчанию во многих языках программирования.

В 1999 году Intel добавила встроенный генератор случайных чисел в свой серверный набор микросхем i810. Наконец, у новых серверов был хороший локальный источник случайности от теплового шума - истинный генератор случайных чисел (TRNG). Отлично, но все же не так быстро, как программные ГПСЧ, поэтому криптографическому программному обеспечению все еще приходилось полагаться на ГПСЧ, которые теперь, по крайней мере, можно было повторно заполнить с помощью встроенной инструкции.

Это подводит нас к криптографически безопасному ГПСЧ (CSPRNG). (Эти аббревиатуры! Неудивительно, что некоторые люди думают, что информатика скучна.) CSPRNG стал очень важным для обеспечения связи через TLS, соединения Wi-Fi WPA2 и т. Д. Что представляет собой CSPRNG? Вот 131-страничный документ с подробным описанием статистических требований. Повеселись.

Излишне говорить, что к CSPRNG предъявляются очень строгие требования. Mersenne Twister не является CSPRNG, потому что его значения можно предсказать, если у вас есть достаточно большая выборка предыдущих значений в последовательности.

Совсем недавно, в 2012 году, Intel добавила инструкции RDRAND и RDSEED для TRNG, используя встроенный в кристалл генератор теплового шума, обеспечивающий пропускную способность 500 МБ / с. Но RDRAND окружен сомнениями в его целостности. Есть ли в нем тонкая слабость, добавленная специально для АНБ и никого другого? Точно никто не знает. Ну, я полагаю, кто-то где-то знает, но точно не пишет об этом в Твиттере.

Аппаратные TRNG с открытым исходным кодом также появились в последние годы. Сила этих систем заключается в прозрачности их конструкции: вы можете проверить схему самостоятельно, и вы можете построить ее дома, используя готовые компоненты. Полная прозрачность не оставляет сомнений в потрясающей случайности этих схем. REDOUBLER и Infinite Noise TRNG - это два аппаратных генератора случайных чисел со схемой и кодом драйвера на GitHub.

Сегодня все еще ведутся споры о том, какие схемы генерации случайных чисел использовать в программном обеспечении ядра ОС, языках программирования и пакетах безопасности, таких как OpenSSL или OpenSSH. Существует множество вариантов этих алгоритмов для различных требований к скорости, пространству и безопасности, и эксперты по безопасности всегда ищут новые способы атаки на реализацию. Но для большинства повседневных задач вы можете с комфортом использовать специальный файл /dev/random в большинстве операционных систем или функцию rand() в большинстве языков программирования, чтобы получить быстрый и бесконечный поток случайности, который очень обрадовал бы Алана Тьюринга.

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

Источники:
Методы выбора хороших магических чисел для LCG подробно описаны в The Art of Computer Programming vol. 2, глава 3, Дональд Кнут.
Машина любви 1950-х Кристофера Стрейчи, The New Yorker
Документация Генератор случайных чисел Linux i830
Лаваран: Википедия, Статья Wired Magazine
Mersenne Twister : Википедия
Тепловой шум: Википедия
В 2013 году Cloudflare написал в блоге хороший пост о почему случайность имеет значение
RDRAND: Википедия, Stack Overflow статьи о пропускной способности