Что общего у любителей проходить видеоигры на скорость, азартных игроков и криптографов? Они зависят от случайных чисел. От перетасовки музыки до шифрования интернета, случайные числа — важнейшая часть современной жизни. И мы, как правило, полагаемся на компьютеры, которые генерируют их.
Это заставляет задуматься: как именно компьютеры это делают? Скорее всего, вы когда-либо использовали генератор случайных чисел. Языки программирования очень упрощают это действие. Например, в Ruby достаточно вызвать rand.
На первый взгляд, создание случайных чисел может показаться простым. В конце концов, числа на компьютере — это набор единиц и нулей. Компьютеру просто нужно случайным образом выбрать 1 или 0 и повторить это столько раз, сколько необходимо.
Человеку не составит труда сделать это:
100101011010010110001101
Вот, готово.
Примечание: ведутся споры о том, может ли человек демонстрировать по-настоящему случайное поведение. Но это выходит за рамки данной статьи.
Тем не менее, все еще остается вопрос: как компьютер случайно выбирает между нулем и единицей? Ответ оказывается довольно сложным. Он коренится в таких темах, как рекурсивные алгоритмы, компьютерное оборудование и немного — теория хаоса.
Если это звучит для вас интересно, тогда погрузимся глубже.
Как компьютеры генерируют случайные числа?
Простой ответ на этот вопрос заключается в том, что они не могут. По крайней мере, не сами по себе.
Люди создали компьютеры, чтобы они были тем, чем не являемся мы, — полностью логическими машинами. Случайность не в их природе. В конце концов, вы же не хотите, чтобы сервер спонтанно решил не следовать логике приложения.
По своей сути компьютеры — простые машины, которые принимают данные и выдают их обратно. Чтобы компьютеры могли генерировать случайные числа, им нужен внешний источник случайности. И этот источник будет варьироваться в зависимости от того, каким генератором случайных чисел вы решите воспользоваться.
Вероятно, последнее предложение вызвало несколько растерянных взглядов. Что подразумевается под “своего рода генератором случайных чисел”? Разве они не все одинаковы?
Не совсем. Существует два основных типа генераторов случайных чисел.
Примечание: далее названия генераторов случайных чисел будут использоваться в сокращении.
Генератор псевдослучайных чисел (ГПСЧ)
Наиболее распространенный тип — генератор псевдослучайных чисел. Он называется псевдослучайным, потому что не создает “по-настоящему” случайных чисел.
Согласно Википедии:
“ГПСЧ — это алгоритмы, которые могут автоматически создавать длинные ряды чисел с хорошими случайными свойствами, но в конечном итоге последовательность повторяется”.
Несмотря на то, что ГПСЧ следуют определенной схеме, эта схема не прослеживается людьми. Поэтому они “достаточно хороши” для большинства случаев, к примеру для видеоигр.
Генераторам псевдослучайных чисел для работы необходимы две составляющие:
- алгоритм генерации случайных чисел;
- семя.
Первоначально в качестве алгоритмов ГПСЧ применялись линейные конгруэнтные генераторы. Это рекурсивные алгоритмы, которые генерируют следующую величину на основе предыдущей. Вот почему этим алгоритмам требуется “семя” (seed) или начальное значение. О семени можно думать как о фрагменте случайности.
Однако со временем на смену линейным конгруэнтным генераторам пришел вихрь Мерсенна, и он по сей день остается самым популярным алгоритмом ГПСЧ.
Хотя псевдослучайные числа на самом деле не случайные, есть множество причин ими пользоваться. Во-первых, они быстры и дешевы в создании. Кроме того, поскольку ГПСЧ — всего лишь алгоритмы, их можно протестировать и убедиться, что они всегда будут работать правильно.
Вот почему в большинстве, если не во всех, языках программирования случайные числа по умолчанию генерируются именно через ГПСЧ.
Но у генерации псевдослучайных чисел есть и свои недостатки. ГСПЧ работают, потому что случайны для неподготовленного глаза. Однако, если бы вы знали начальное значение для определенной последовательности ГПСЧ, то могли бы предсказать, какие числа будут следующими.
Этой уязвимостью часто пользуются любители ускоренного прохождения видеоигр — они называют это манипулированием ГСЧ. Они заставляют игру работать предсказуемо, чтобы пройти ее как можно быстрее. К счастью, если семя видеоигры будет скомпрометировано, ничего особенного не случится. В этом нет ни вреда, ни зла.
Но бывают случаи, когда предсказание случайных чисел имеет гораздо большее значение. Например, создание ключей безопасности.
Если злоумышленник выяснит исходное значение, используемое для создания ключей RSA в сертификатах TLS, он потенциально может расшифровать сетевой трафик. Это означает, что он сможет получать пароли и другую личную информацию, передаваемую через интернет.
В таких ситуациях нужен более безопасный способ получения случайных чисел.
Генератор истинно случайных чисел (ГИСЧ)
Как вы можете догадаться, истинно случайные числа непредсказуемы и не следуют шаблону.
Но как компьютер может достичь этого? Как было указано ранее, компьютерам требуется внешний источник случайности. В случае ГПСЧ, это было семя. В случае ГИСЧ, это энтропия.
Теория хаоса и термодинамика выходят далеко за рамки данной статьи. Достаточно сказать, что энтропия — это чистый нефильтрованный хаос. И лучший источник этого хаоса — сам компьютер.
Компьютер не может функционировать случайным образом, но составляющие его части — могут. Компьютер — это сложная система со множеством движущихся частей и изменчивостью. Тепловой шум, фотоэффект и другие квантовые явления происходят постоянно.
Компьютерное оборудование — не единственный источник энтропии. Также можно использовать движения мыши и клавиатуры пользователя.
Но хаос был бы бесполезен, если бы его нельзя было обуздать. К счастью, инженеры-аппаратчики придумали, как это сделать. Посредством сложной схемы аппаратных микросхем и компонентов, компьютеры могут преобразовывать этот физический шум в цифровые нули и единицы.
Один из наиболее очевидных вариантов применения ГИСЧ — цифровые азартные игры. Бросание костей, перетасовка карт и вращение колеса рулетки — все это зависит от того, чтобы быть неопределимым. Хотя он часто используется при опросах общественного мнения, призыве на военную службу и отборе присяжных, а также там, где случайность используется как метод справедливости.
В действительности сферы применения ГИСЧ довольно ограничены, поскольку у них есть свой набор недостатков. Во-первых, они медлительны. Хотя это варьируется, ГИСЧ может выдавать только небольшое количество бит в секунду.
Кроме того, ГИСЧ не всегда надежны. Компьютерам требуется достаточное количество энтропии для производства истинно случайных чисел. Но суть случайности в том, что она возникает случайным образом. Простаивающий или новый сервер не сможет генерировать числа настолько же качественно, как активный.
Эта ненадежность создает угрозу безопасности при использовании ГИСЧ для создания криптографических ключей. В 2012 году в исследовательской работе под названием Ron was Wrong, Whit is Right обнаружилось, что тысячи SSL-ключей небезопасны. Хотя основная причина неизвестна, обычно считается, что это результат ошибочной генерации случайных чисел.
Криптографически стойкий генератор псевдослучайных чисел (КСГПЧ)
Из-за недостатков ГИСЧ и ГПСЧ криптографы разработали гибридный подход, называемый криптографически защищенной генерацией псевдослучайных чисел. Этот метод направлен на обеспечение скорости ГПСЧ с гарантией безопасности ГИСЧ.
КСГПЧ прост в теории. В нем применяется высококачественный источник энтропии для получения начального значения, которое дальше вводится в алгоритм, а тот затем выдает безопасные случайные числа.
Проще говоря, он задействует ГИСЧ при создании начального значения для ГПСЧ. Если все сделано правильно, КСГПЧ гарантирует, что начальное значение действительно случайное, и ГПСЧ не может быть скомпрометирован или изменен.
Пример этому — /dev/random в системах Unix и Linux.
Несмотря на преимущества КСГПЧ, здесь, как и везде в технологической отрасли, нельзя гарантировать полную безопасность.
Завершающие мысли
Многие разработчики программного обеспечения не понимают сложности, связанной с генерацией случайных чисел. Это свидетельствует в пользу архитекторов, которые создали существующую систему. От инженеров-аппаратчиков, которые разрабатывали чипы для преобразования шума в данные, до разработчиков ядра и языков программирования, которые преобразовали эти данные в простые для использования API.
Возможно, в следующий раз, когда вы будете играть в видеоигру, слушать музыку в случайном порядке или просто генерировать произвольное число у себя в коде, вы лучше станете понимать волшебство, которое происходит под капотом.
Читайте также:
- Как сгенерировать настоящие случайные числа в Solidity с блокчейном
- Векторы - прошлое ИИ, хэши - будущее
- NeuralHash от Apple: принцип работы и слабые места
Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи Sunny Beatteay: Generating Random Numbers Is a Lot Harder Than You Think
