В чем секрет силы выбора из двух

 

Эффективность метода выбора из двух удивительна. Но если задуматься, этот результат вполне логичен, и мы постараемся предложить вам простое объяснение.

Давайте вернемся к рис. 5.1. У сервера 5 самая длинная очередь. Если выбрать сервер наудачу, наши шансы наткнуться на сервер 5 будут 1:5. Это 20 % случаев! При этом шансы попасть на самый лучший сервер, сервер 2, точно такие же.

Теперь представьте, что мы сначала выбираем два сервера, а потом наименьшую очередь из двух. Во‑первых, в этом случае на сервер 5 мы в принципе не попадаем никогда. В худшем случае мы попадем на сервер 4. Но для этого мы должны наудачу вытянуть сервер 4 и сервер 5. Два сервера из пяти можно выбрать десятью способами: 1 и 2, 1 и 3, 1 и 4, 1 и 5, 2 и 3, 2 и 4, 2 и 5, 3 и 4, 3 и 5, 4 и 5. Все эти пары равновероятны. Шансы, что из десяти возможных пар мы вытянем именно самую неудачную, 4 и 5, всего 1:10. При этом свободный сервер 2 входит в четыре из десяти пар. Выбрав пару, в которую входит этот сервер, мы непременно на него попадем. Значит, наши шансы попасть на сервер 2 равны 4:10; это уже не 20 %, а 40 %.

Итак, у нас набралось три причины, по которым выбор из двух выгоднее выбора наугад:

1) мы никогда не попадаем в самую длинную очередь;

2) маловероятно, что мы выберем сразу два сервера с длинной очередью;

3) увеличиваются шансы попасть на пустой сервер.

 

Какая из этих причин самая значительная? Из математических уравнений следует, что причина 2. Представьте, что серверов много и у 20 % серверов длинная очередь. Тогда шансы наткнуться на два таких сервера всего 0,2×0,2×100 %=4 %.

Именно это перемножение вероятностей 0,2×0,2 и приводит к совершенно другому решению уравнения, согласно которому длинные очереди становятся практически невероятными[12].

Так получилось, что Нелли, будучи аспиранткой, присутствовала на одном из первых докладов Никиты Введенской о силе выбора из двух на конференции в Израиле в 1996 году. Когда Никита Дмитриевна объяснила решение, оно оказалось таким красивым и простым, что создавалось впечатление, что каждый мог догадаться! В перерыве Никита Дмитриевна сказала: «На самом деле это так просто, что можно объяснять студентам!» Это был блестящий пример математической работы – красивой и полезной!

Спустя почти 20 лет, на конференции в Стамбуле в 2015 году, пленарный доклад делала Кавита Раманан из университета Брауна в США. Кавита – блестящий математик с огромным количеством фундаментальных работ и профессиональных наград. На одном из первых слайдов она сослалась на работу Введенской, Добрушина и Карпелевича. Доклад Кавиты тоже был о методе выбора из двух. Но на данный момент эти исследования уже перешли на иной уровень обобщения и абстракции. Кавита занимается очень сложными асимптотическими процессами, ее доклад выходит за рамки нашей книги. Проблема развивается и ставит перед математиками новые задачи, еще красивее, еще сложнее и, кто знает, возможно, еще полезнее.

Приложение для подготовленного читателя к главе 5

 

 

Глава 6

Секретные числа

 

Массовый обмен шифровками

 

Классическая музыка по радио прервалась, и голос диктора стал зачитывать цифры, которые Штирлиц быстро записывал в аккуратные колонки. Диктор называл цифры привычно сухо и четко. «Для него эти цифры всего лишь цифры», – подумал Штирлиц. Когда сообщение закончилось, Штирлиц взял с полки томик Шиллера, открыл на нужной странице и начал превращать цифры в слова. «Центр – Юстасу…»

Сообщение передавалось по открытому радиоканалу, но прочитать его мог только Штирлиц, потому что только он знал, как расшифровать переданные цифры. Шифрование – это не что иное, как сокрытие информации от посторонних.

Шифрование в том или ином виде существует много тысячелетий. Однако в середине XX века произошла своего рода революция. Если раньше шифровками пользовались, как правило, представители государственных спецслужб (или, если угодно, сами спецслужбы и даже государства), то к 70‑м годам XX века стало ясно, что совсем скоро шифрование понадобится самым обычным людям, причем не изредка, а буквально каждый день. Это связано с лавинообразным развитием технологий, плоды которых доступны каждому: компьютеры, сотовые телефоны и тому подобное.

Каждый раз, когда вы вводите свой пароль или номер кредитной карты на сайте, вы отправляете личную конфиденциальную информацию по открытым каналам интернета. У многих к этим каналам есть доступ, например у вашего интернет‑провайдера. В принципе перехватить ваше сообщение может даже компьютерщик‑любитель с обычным ноутбуком и подходящим для этой цели программным обеспечением. Конфиденциальность информации обеспечивается именно тем, что она передается в виде шифровки. Вы можете легко узнать сайты, на которых действует протокол безопасной передачи данных: в этом случае веб‑адрес начинается с https://… HTTP – обычный протокол передачи данных по интернету. А дополнительная буква S происходит от английского слова secure (безопасный) и означает, что данные будут передаваться в зашифрованном виде.

Каким образом зашифровывается и расшифровывается ежедневный гигантский поток конфиденциальной информации? Естественно, математика, как всегда, опережала технологии и стояла у их истока. Задачами шифрования занимается криптография – очень активная и интересная область математики и информатики[13].

 

Ключ к шифру

 

В зашифрованном сообщении каждая буква заменяется какой‑либо другой буквой, числом или знаком. Например, возьмем самый простой шифр. Будем зашифровывать каждую букву следующей буквой алфавита. Вместо А напишем Б, вместо Б – В и так далее, а вместо Я – А. Например, слово ПРИВЕТ будет выглядеть так:

 

РСЙГЁУ

 

Это очень простой шифр, потому что каждая буква всегда зашифровывается одной и той же буквой, и взломать его – пара пустяков. Достаточно угадать одно слово в сообщении. Например, мы догадались, что сообщение начинается со слова «привет», и вот в нашем распоряжении уже шифры для шести букв: П, Р, И, В, Е и Т. С их помощью мы можем угадать другие слова, пока наконец не расшифруем весь алфавит. Именно так расшифровал секретные послания Шерлок Холмс в рассказе «Пляшущие человечки».

Конечно, любой серьезный шифр гораздо сложнее. Например, одна и та же буква, скажем А, может каждый раз обозначать разные буквы. Или, как в фильме «Семнадцать мгновений весны», буквы могут быть зашифрованы с помощью цифрового кода. Понятно, что у Штирлица в сборнике Шиллера были не стихи, а ключи для расшифровки секретных сообщений. Если бы у Штирлица не было этой книги, то для него, как и для диктора, цифры так и остались бы только цифрами.

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

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

Но для начала давайте познакомимся со знаменитой шифровальной машиной «Энигма», которая использовалась немецкой армией во время Второй мировой войны. Это один из самых изощренных шифров той эпохи, когда шифрование еще не было таким массовым и обыденным явлением. А ключ к этому шифру нашел английский математик Алан Тьюринг.

 

Алан Тьюринг и «Энигма»

 

Фильм «Игра в имитацию» (2014) именно об этой потрясающей истории. К сожалению, в нем не объясняется, как устроена «Энигма» и как Тьюринг взломал этот шифр. Наш рассказ хотя бы частично восполнит эти упущенные подробности. Мы воспользуемся видео Кембриджского университета[14]. Очень рекомендуем посмотреть их, чтобы увидеть «Энигму» в действии.

«Энигма» совсем небольшая, по размеру сравнима с печатной машинкой. Снаружи она состоит из клавиатуры и панели, на которой расположены буквы с подсветкой. Если нажать букву на клавиатуре, скажем A, то на панели высветится другая буква, например Q. Это означает, что в шифровке в этом месте вместо А появится Q. Внутри у машины три вращающихся диска, и их положение меняется после набора каждой буквы. Диск повернулся, провода соединились по‑другому, и когда мы в следующий раз нажимаем А, на панели высвечивается уже не Q, а, скажем, G.

В набор «Энигмы» входят пять дисков, использовать можно любые три, в любом порядке. У каждого диска – 26 изначальных положений. И это еще не все. В военном варианте у «Энигмы» была передняя панель с буквами и 10 кабелей. Каждый кабель соединял две любые буквы между собой, и при шифровании они менялись местами. Диски можно было перебрать достаточно быстро, но количество комбинаций на панели было настолько велико, что перебрать их было невозможно. Всего у «Энигмы» было

 

158 962 555 217 826 360 000

 

возможных изначальных установок. Каждые сутки ровно в полночь они менялись. Новое изначальное положение дисков, новые пары букв на панели. Перебрать все комбинации за 24 часа было совершенно нереально. Шифр считался неуязвимым.

Зашифрованное сообщение передавали по радио. У немецкого офицера, который его получал, была такая же машина. Кроме того, он имел секретный документ – установки «Энигмы» на каждый день текущего месяца. Это был ключ к шифру машины. Офицер соединял нужные пары букв, ставил диски в заданное исходное положение, набирал Q, и на панели высвечивалась А. Поступая и дальше таким образом, он расшифровывал секретное сообщение.

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

Алан Тьюринг и его команда совершили настоящий прорыв. Они научились разгадывать шифр каждое утро всего за 20 минут! Мы только вкратце объясним, как им это удалось.

Прежде всего в шифре было слабое место. Буква никогда не превращалась сама в себя. Это стало хоть какой‑то зацепкой. Важным оказалось и предположение, что сообщения утром начинаются с чего‑то однотипного, например с прогноза погоды. По‑немецки wetterbericht. Зная, что буква не превращается сама в себя, мы можем найти слово в начале шифровки, которое в принципе может обозначать wetterbericht. Теперь нужно отыскать такую изначальную установку, чтобы шифр совпал с расшифровкой.

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

Для ускорения процесса Алан Тьюринг сделал две существенные вещи. Во‑первых, он понял, что если пара букв оказалась неправильной, то и все другие пары, следовавшие из нее, тоже неправильные. А значит, их уже не надо проверять. Во‑вторых, он построил огромную машину, которая с помощью электрического тока позволяла исключить все неправильные пары одновременно. Оставалось только повторить операцию для каждой позиции дисков, а на это уходило всего 20 минут.

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

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