Случайности не случайны, Или как компьютеры генерируют случайные числа

Генератор случайных чисел — это намного сложнее, чем кажется.

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

Это заставляет задуматься: а как именно компьютеры генерируют случайные числа?

Если вы занимались программированием, то наверняка использовали в своем коде генератор случайных чисел. Для этого в Ruby достаточно вызвать «rand», а в Python — «random ()». Создание ряда случайных чисел может показаться простым. В конце концов числа на компьютере — это набор единиц и нулей. Машине просто нужно случайным образом выбрать 1 или 0 и повторить это столько раз, сколько нужно. Даже мы, люди, можем сделать это легко и просто на листе бумаги.

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

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

^Unsplash

Первый и самый распространенный тип называется «генератор псевдослучайных чисел (ГПСЧ)». Как следует из названия, он не создает «истинных» случайных чисел. Чтобы сгенерировать с помощью него число, понадобится единственное начальное значение, откуда последует псевдослучайность. Алгоритмы генерации, используемые для ГПСЧ, включают в себя «метод извлечения квадратов», «линейный конгруэнтный метод», «регистр сдвига с линейной обратной связью» и «вихрь Мерсенна».

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

Нельзя не сказать о том, что слабым местом ГПСЧ все-таки пользуются: например, любители гонок, которые манипулируют ГСЧ и заставляют игру работать предсказуемо, чтобы пройти ее как можно скорее. Есть случаи, когда предсказание случайных чисел имеет более серьезные последствия. Зная начальное значение, злоумышленник может угадать сгенерированный пароль и получить доступ к личным данным пользователя.

Второй тип генератора — генератор «истинно» случайных чисел (ГИСЧ или TRNG). В качестве внешнего источника случайности он использует энтропию. Не углубляясь в теорию хаоса и термодинамику, отметим, что энтропия — это чистый нефильтрованный хаос. И лучший источник этого хаоса — сам компьютер. Компьютер не может работать случайным образом, чего не скажешь о его составляющих.

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

^{Магнус Энгё / Unsplash}

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

Однако на самом деле спектр использования ГИСЧ тоже ограничен, ведь у него есть свои недостатки. Во-первых, для генерации чисел требуется много времени. А еще ГИСЧ не всегда надежны. Компьютерам требуется достаточное количество энтропии для создания истинных случайных чисел, но случайность заключается в том, что она возникает… случайно! Неактивный или новый сервер не сможет создавать номера такого же высокого качества, как активный.

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

КСГПЧ — это генератор, использующий высококачественный источник энтропии для создания начального числа. Затем оно вводится в алгоритм, который производит случайные и безопасные числа. Проще говоря, он использует ГИСЧ для создания начального числа для ГПСЧ. Если все сделано правильно, КСГПЧ гарантирует, что начальное число действительно случайно, а полученный результат нельзя взломать или реконструировать. Обычно его используют в операционных системах вроде Unix и Linux.

Тем не менее, даже несмотря на преимущества КСГПЧ, как и всего остального в технологической индустрии, абсолютная безопасность недостижима.

Теперь, когда в следующий раз вы будете играть в видеоигру, слушать музыку в случайном порядке или просто генерировать случайное число в своем коде, вы осознаете всю магию, которая творится «под капотом».

^{Обложка: Маркус Кристи / Unsplash}

^{Источник статьи: Generating Random Numbers Is a Lot Harder Than You Think}