Кажется, что люди стремятся исключить из своей жизни случайности. Обычно мы стремимся контролировать всё и вся. Но случайность значима для нас. Выбор того, кто будет играть за белых в шахматах, люди скорее доверят случайности, чем судье. То же относится к лотереям и любым другим играм, в которых требуется справедливое распределение выигрыша. Кроме того, случайность крайне важна для всей современной криптографии и, соответственно, работы интернета.
КРИТЕРИИ СЛУЧАЙНОСТИ
В первую очередь мы должны чётко понять, что случайность не является характеристикой отдельно взятого числа. Нельзя сравнить между собой числа 400 и 397 и сказать, что 397 более случайное.
Это далеко не лучший способ определять случайность последовательности. Но из примера выше мы можем вывести одну из главных её характеристик: ни одно число в ней не должно зависеть от предыдущего. Никуда не годится, если наш генера- тор случайных чисел, выдав, например, цифру 5, будет думать: «Я в прошлый раз назвал пятёрку, так что сейчас назову какое-нибудь другое число, а то вдруг кто-то подумает, что это недостаточно случайная последовательность». В каждый момент времени вероятность выпадения любого числа из возможных должна быть одинакова. Даже у пятёрки, которая только что уже выпадала. Предположим, у нас 10 чисел, тогда вероятность выпадения каждого числа должна быть равна 10 %. Способен ли человек учитывать эту вероятность? Нет, не способен.
Предлагаем вам простой эксперимент: загадайте случайное число от 1 до 10. Загадали? Отлично, запомните его! А теперь давайте разберёмся, насколько человек хорош в генерации случайных чисел.
ЧЕЛОВЕК КАК ГЕНЕРАТОР
Скажем сразу: человек в этом качестве очень плох. Любой, кто играл в какие-либо игры один на один с одним и тем же соперником достаточно долго, знает, что рано или поздно соперник становится предсказуемым. Это относится и к шахматам, и к шашкам, и даже к фехтованию. Клод Шеннон, английский математик, основоположник современной теории информации, придумал алгоритм, который сейчас известен как «Гадалка Шеннона». Он позволил превратить утверждение о пред- сказуемости человека из субъективного ощущения игроков в математически доказанный факт. Суть алгоритма в следующем: человек записывает на бумажку либо 1, либо 0, а машина пытается предположить, что человек загадал. После того, как машина озвучивает своё предположение, человек открывает бумажку, и машина запоминает то, что человек загадал. Поначалу машина проигрывает человеку в половине случаев, как и положено, но спустя при- мерно 50 итераций машина добивается невероятной точности прогнозов — 85–95 %. Неужели человек действительно настолько предсказуем?
Вернёмся к числу, которое вы загадали. Согласно статистике, более половины из вас загадало число 7. Если бы мы попросили загадать число от 1 до 20, то примерно треть из вас загадала бы 17. Между 1 и 100 самое популярное «случайное» число — это 73, а второе по популярности — 37. Почему так происходит? Похоже, в голове у нас выстраивается какая-то сложная схема, согласно которой мы оцениваем уровень этой случайности для каждого числа и останавливаемся, когда нам кажется, что эта характеристика находится на достаточно высоком уровне. Это легко заметить, если задуматься над тем, является ли 10 случайным числом. Большинство скажет, что нет. Но на самом деле это число является случайным ровно в той же степени, как и любое другое.
Более того, человек не может каждый раз называть случайное число, не опираясь на предыдущее, которое он назвал. Если попросить того же человека назвать ещё одно случайное число, скорее всего, опять семёрку он не назовёт. А генератор случайных чисел вполне может выдать и семёрку. Монетка не знает, какой стороной она выпала в прошлый раз, и каждый раз вероятность выпадения решки остаётся равной 50 %. Мы неспособны придумывать случайные числа потому, что наш мозг всегда ищет закономерности. Мы пытаемся систематизировать наши знания и ищем связи. Именно поэтому существуют чемпионаты даже по таким простым играм, как «камень-ножницы-бумага». Именно поэтому есть люди, которые более успешны в играх, чем другие, хотя, на первый взгляд, в них всё решает случай. И тем не менее любая компьютерная программа, использующая принцип «Гадалки Шеннона», легко победит человека.
Генераторы случайных чисел — это модули программ, которые выдают последовательности чисел: псевдослучайных и настоящих случайных. Первые используют гораздо чаще, потому что такие генераторы проще интегрировать и для большинства задач нам достаточно псевдослучайных последовательностей. Генераторы случайных чисел делятся на программные и аппаратные. Программные являются всего лишь алгоритмом, а аппаратные — это самостоятельная «железяка», которая выполняет всего одну задачу: создаёт случайные числа. Реализовать программный генератор настоящих случайных чисел представляется невозможным, и чуть ниже мы обсудим, почему именно.
ПОИСК ЗАКОНОМЕРНОСТЕЙ
Не только люди пытаются выявить закономерности. Американский психолог Беррес Скиннер провёл забавный эксперимент: он сажал голубей в специальные изолированные контейнеры и давал им еду в случайные промежутки времени, никак не зависящие от действий птицы. Если совпадало, что птица получала еду после какого-то действия, например, птица вертелась на месте или била клювом в угол клетки, то она начинала повторять это действие в надежде снова получить еду. Аналогичные эксперименты с людьми показали при- мерно такой же результат. Представьте кабинку, где находятся несколько кнопок и лампочка. Человеку объясняют, что его за- дача заключается в том, чтобы заставить лампочку загореться. На самом деле лампочка загоралась случайным образом.
Человек не мог никак на это повлиять. Но почти все участники эксперимента были убеждены, что им удалось найти последовательность действий, приво- дящую к тому, что лампочка загоралась. Они верили, что стоит им подпрыгнуть на одной ноге и хлопнуть в ладоши или встать на стул и дотронуться до потолка, и лампочка загорится. Мы можем находить закономерности даже там, где их нет. И это довольно сильно ме- шает нам в понимании, что есть случайность. Иногда нам проще найти закономерности в по-настоящему случайной последовательности, чем в той, которая учитывает эту особен- ность нашего разума и корректируется под неё.
НЕ ПЫТАЙТЕСЬ УГАДАТЬ
Если люди хотят получить по-настоящему случайный результат, то они обычно используют монетку. Она отвечает правилу «несвязанности»: предыдущий бросок монеты никак не влияет на следующий. Вероятность, что нам выпадет четыре «решки» подряд, равна вероятности, что выпадут последовательно решка-орёл-орёл-решка. Монетка также отличается предельной «честностью»: вероятность выпадения орла и решки примерно одинакова. Более сложный пример случайности — это карты в колоде. Число возможных перестановок карт в колоде составляет 52! или примерно 8*1067.
Это значит, что каждый раз, когда вы тщательно перемешиваете колоду карт, у вас в руках, скорее всего, окажется совершенно уникальная последовательность карт, которая не выпадала ещё ни одному человеку на Земле, и более того, скорее всего, уже никому и никогда не выпадет. Вытягивая карту из колоды, мы понимаем, что теперь там на одну карту меньше. Мы видим, что среди оставшихся 51 карты нет, допустим, дамы пик. Вынимая из колоды карту за картой, мы каждый раз увеличиваем вероятность того, что сможем угадать следующую карту, но всё равно эта вероятность ничтожно мала. Мера этой неопределённости, невозможности угадать следующий элемент, называется информационной энтропией. Чем выше энтропия, тем более случайна последовательность. Когда карты одной масти лежат в колоде одна за другой, это говорит о недостаточно высоком уровне энтропии в колоде.
Бесплатный совет: если мама будет ругать вас за беспорядок в комнате, скажите ей, что это не беспорядок, а слегка повышенный уровень энтропии.
О БЕЗОПАСНОСТИ
Зачем в компьютерах нужны случайные числа? В первую очередь, они часто встречаются в играх: расположение карт в колоде пасьянса, очерёдность фигур в тетрисе, случайно сгенерированный мир в какой-нибудь игре-песочнице. За это отвечает генератор псевдослучайных чисел («псевдо» — потому что он каждый раз ищет баланс между менее и более случайным, а значит, его выбор уже не является полностью случайным). В играх мы ничем не рискуем, пусть генератор делает, как хочет. А как быть, когда дело касается более серьёзных вещей? Например, ваших личных данных? Предположим, что вам нужен надёжный пароль. Но вот проблема: генератор псевдослучайных чисел сгенерирует вам псевдослучайный пароль. А значит, злоумышленник может узнать алгоритм генерации пароля и подобрать его.
Американский хакер Кевин Митник в «Искусстве вторжения» рассказывает историю группы хакеров, которые в начале 1990-х купили игровой автомат той же серии, что использовались тогда в Лас-Вегасе. Преступники разобрали его, докопались до исходного кода, вычленили фрагмент отвечающий за генерацию простых чисел, и на основе вы даваемых игровым автоматом колод карт смогли написать программу, которая формирует те же последовательности, что и программа автомата.
Таким образом, они всегда знали, какие карты были «загаданы» машиной. Это хороший пример, почему генераторы псевдослучайных чисел не считаются надёжными.
ВЫСОКАЯ ЗАЩИТА
По-настоящему криптостойкими считаются только настоящие генераторы случайных чисел. Принцип их работы состоит в том, что они берут информацию извне компьютера. Например, некоторые из них основаны на считывании данных о погоде. Другие — на вычленении произвольных пакетов информации из реликтового излучения. Третьи — на броуновском движении мельчайших частиц. Задача настоящих генераторов случайных чисел — максимально быстро извлекать случайность из «рудника энтропии». На их основе можно быстро создавать безопасные, неподбираемые пароли и ключи для больших информационных систем, требующих высокой степени защиты. Так что случайностью мы называем то, что находится за пре- делами нашего контроля. Но чем лучше человек знает мир, тем меньше ему кажется, что жизнь полна случайностей.
