«Когда я задался целью получить действительно случайное число, то не нашел для этого ничего лучшего, чем обычная игральная кость» — писал в 1890 году Фрэнсис Гальтон в журнале Nature. «После того, как кости встряхивают и бросают в корзинку, они ударяются друг о друга и о стенки корзинки столь непредсказуемым образом, что даже после легкого броска становится совершенно невозможным предопределить его результат».
(Игральные кости времён Римской Империи)
Как мы можем сгенерировать равномерную последовательность случайных чисел? Случайность, столь прекрасная в своём многообразии, часто встречается в живой природе, но её не всегда легко было извлечь искусственным путём. Самые древние из игральных костей были найдены на Среднем Востоке, и они датируются примерно 24 столетием до нашей эры. Другим примером может быть Китай, где ещё в 11 столетии до нашей эры применялось разбивание ударом черепашьего панциря, с дальнейшей интерпретацией размера полученных случайных частей. Столетиями позже люди разрубали несколько раз стебли растений и сравнивали размеры полученных частей.
Но к середине 40-ых годов ХХ столетия человечеству понадобилось значительно больше случайных чисел, чем можно было получить от бросков костей или разрезания стеблей. Американский аналитический центр RAND создал машину, которая была способна генерировать случайные числа с помощью использования случайного генератора импульсов (что-то вроде электронной рулетки). Они запустили её и через какое-то время получили достаточное количество случайных чисел, которые опубликовали в виде книги "Один миллион случайных чисел и сто тысяч нормальных отклонений".
Книгу можно почитать онлайн или купить бумажное переиздание 2001 года на Amazon. То, что сегодня может показаться абсурдным арт-проектом, в то время было серьёзным прорывом. Впервые учёным стала доступна действительно большая последовательность действительно случайных чисел.
Другая похожая машина, ERNIE, построенная в знаменитом сегодня Блетчли-парке в 40-ых годах ХХ века, использовалась для генерации случайных чисел в британской лотерее Premium Bond. Для того, чтобы развеять страхи по поводу случайности и честности результатов, была даже снята документальная лента «The Importance of Being E.R.N.I.E.». Сегодня её можно посмотреть на Youtube:
В 1951 году случайность наконец была формализована и воплощена в реальном компьютере Ferranti Mark 1, который поставлялся со встроенным генератором случайных данных на основе дробовых шумов и инструкцией, позволяющей получить 20 случайных бит. Этот функционал был разработан Аланом Тьюрингом. Его коллега Кристофер Стрэчи применил его для создания «генератора любовных писем». Вот пример текста, который был сгенерирован данной программой:
JEWEL LOVE
MY LIKING HUNGERS FOR YOUR ADORABLE INFATUATION.
YOU ARE MY EROTIC ARDOUR.: MY FOND RAPTURE. MY THIRST
SIGHS FOR YOUR INFATUATION. MY HEART SEDUCTIVELY WISHES YOUR
BREATHLESS LONGING.
YOURS CURIOUSLY
M. U. C.
Но генератор случайных чисел Тьюринга не делал программистов тех лет счастливыми, поскольку привносил в и так новые и нестабильные компьютерные системы фактор ещё большей нестабильности. Желая добиться стабильной работы некоторой программы — без отладчиков и со случайными данными — никогда нельзя было достичь повторяемости результатов. Тогда возникла следующая мысль: «А что, если генератор случайных чисел может быть представлен в виде некоторой детерминированной функции?» Тогда получилось бы, что, с одной стороны, генерируемые числа имели бы признаки случайных, но с другой стороны, при одинаковой инициализации генератора данные последовательности были бы каждый раз одни и те же. Так появились генераторы псевдослучайных чисел (ГПСЧ).
Джон фон Нейман разработал ГПСЧ в 1946 году. Его идеей было начать с некоторого числа, взять его квадрат, отбросить цифры из середины результата, снова взять квадрат и отбросить середину, и т.д. Полученная последовательность, по его мнению, обладала теми же свойствами, что и случайные числа. Теория фон Неймана не выдержала испытания временем, поскольку какое бы начальное число вы не выбрали, сгенерированная таким образом последовательность вырождалась в короткий цикл повторяющихся значений, вроде 8100, 6100, 4100, 8100, 6100, 4100,…
Полностью избежать циклов невозможно, когда мы работаем с детерминированной функцией, чьи последующие значения основаны на предыдущих. Но что, если период цикла будет столь большим, что на практике это уже не будет иметь значения?
Математик Деррик Генри Лемер развил эту идею в 1949 году с изобретением линейного конгруэнтного метода. Вот генератор псевдослучайных чисел, основанный на подходе Лемера и написанный на Javascript:
// The Central Randomizer 1.3 (C) 1997 by Paul Houle (paul@honeylocust.com)
// 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);
};Вы можете заметить в коде ряд «магических констант». Эти числа (как правило, простые) выбирались таким образом, чтобы максимизировать период цикла до повторения последовательности результатов. Данный генератор использует в качестве начального значения текущее время и имеет период около 2^31. Он стал популярным с выходом JavaScript 1.0, поскольку он тогда ещё не имел встроенной функции Math.random(), а все ведь хотели, чтобы их баннер времён Web 1.0 вращался случайным образом. «Я не использовал бы этот алгоритм для чего-то связанного с безопасностью, но для многих применений его достаточно», — писал автор вышеуказанного кода Paul Houle.
Но Интернет как раз требовал чего-то, связанного с безопасностью. SSL появился в 1995 году и его реализация требовала высококачественного генератора псевдослучайных чисел. Это привело к серии достаточно диких экспериментов в данной области. Если вы посмотрите на патенты, связанные с генерацией случайных чисел, выданные в те времена, то получите ощущение, будто смотрите на осовремененные попытки построения первого самолёта.
Большинство популярных процессоров в 90-ых годах не имели специальной инструкции для генерации случайных чисел, так что выбор хорошего начального значения для генератора псевдослучайных чисел имел очень важное значение. Это вылилось в проблемы с безопасностью, когда Phillip Hallam-Baker обнаружил, что в браузере Netscape (доминирующем в то время) реализация SSL использовала для инициализации ГПСЧ комбинацию текущего времени и ID своего процесса. Он показал, как хакер может легко подобрать это значение и расшифровать SSL-трафик. Угадывание начального значения алгоритма генерации псевдослучайных чисел — до сих пор популярная атака, хотя с годами она стала слегка сложнее. Вот пример удачной атаки, опубликованный на Hacker News в 2009 году.
В 1997 году программисты были ограничены в способах получения по-настоящему случайных чисел, так что команда SGI создала LavaRand, который состоял из вебкамеры, направленной на пару лава-ламп, стоявших рядом на столе. Картинка с этой камеры была отличным источником энтропии — Настоящим Генератором Случайных Чисел, таким же, как у Тьюринга. Но в этот раз получалось генерировать 165 Кб случайных чисел в секунду. Изобретение было тут же запатентовано.
Большинство экспериментов в этой области не выдержали испытания временем, но один ГПСЧ, названный Вихрем Мерсенна и разработанный в 1997 году Макото Мацумото и Такудзи Нисимура, смог удержать пальму первенства. В нём сочетались производительность и качество результатов, что позволило ему быстро распространиться на многие языки и фреймворки. Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей и генерирует детерминированную последовательность с огромным периодом цикла. В текущей реализации период равен 2¹⁹⁹³⁷− 1 и именно эта реализация входит сегодня в большинство языков программирования.
В 1999 году Intel добавил аппаратный генератор случайных чисел в чипсет i810. Это было хорошо, поскольку данная реализация давала по-настоящему случайные числа (на основе температурных шумов), но работало не настолько же быстро, как программные ГПСЧ, так что большинство криптоприложений всё ещё используют ГПСЧ, которые теперь, по крайней мере, можно инициализировать начальным значением от аппаратного генератора случайных чисел.
Это приводит нас к понятию криптографически-безопасного генератора псевдослучайных чисел (КБГПСЧ). (Ох уж эти аббревиатуры! Не удивительно, что компьютерные науки кажутся некоторым людям скучными.) КБГПСЧ стали очень популярными в эпоху SSL. Каким требованиям должен удовлетворять КБГПСЧ? Ну вот вам 131-страничный документ с этими требованиями, развлекайтесь. Как вы уже понимаете, требований не мало. Например, тот же Вихрь Мерсенна им не удовлетворяет, поскольку, имея достаточно большую последовательность сгенерированных им чисел, можно угадать следующее число.
В 2012 году INTEL добавил в свои чипы инструкции RDRAND и RDSEED, позволяющие получить настоящие случайные числа на основе тех же колебаний температуры, но теперь уже на скорости до 500 Мб/с, что должно бы сделать применение программных ГПСЧ ненужным. Но в обществе бродят слухи и сомнения в честности этих инструкций. Нет ли в них специально сделанной закладки для NSA? Никто не может сказать этого точно. Вернее, кто-то, наверное, может, но он точно не напишет об этом в Твиттере.
(Случайные данные полученные от аппаратного генератора случайных чисел Redoubler)
В последние годы начали появляться также аппаратные генераторы случайных чисел от сторонних производителей и даже полностью открытые (как в плане софта, так и аппаратной части). Сила этих продуктов именно в открытости: можно изучить их самостоятельно и даже построить дома самому из общедоступных компонентов. Примерами могут быть REDOUBLER и Infinite Noise TRNG.
Сегодня люди всё ещё ведут дискуссии о том, какой именно генератор случайных чисел стоит использовать в той или иной системе, ядре ОС, языке программирования, криптографической библиотеке и т.д. Есть много вариантов алгоритмов, заточенных на скорость, экономию памяти, безопасность. И каждый из них постоянно подвергается атакам хакеров и специалистов по безопасности. Но для ежедневных задач, не связанных с безопасностью, вы вполне можете положиться на данные из /dev/random или функции rand(), доступных на большинстве платформ. Это даст вам достаточно большую и случайную последовательность данных, которая бы сделала в своё время счастливым Алана Тьюринга.
Автор: Инфопульс Украина
