Математика — царица наук, но многие ли знают, решение каких прикладных задач ей по плечу? На этот вопрос отвечает простая и увлекательная книга Нелли Литвак и Андрея Райгородского «Кому нужна математика?». В этой книге описываются различные разделы прикладной математики, от логистики до математики онлайн-рекламы. Мы решили познакомить читателей N + 1 с фрагментом главы, посвященной криптографии.
Классическая музыка по радио прервалась, и голос диктора стал зачитывать цифры, которые Штирлиц быстро записывал в аккуратные колонки. Диктор называл цифры привычно сухо и четко. «Для него эти цифры всего лишь цифры», — подумал Штирлиц. Когда сообщение закончилось, Штирлиц взял с полки томик Шиллера, открыл на нужной странице и начал превращать цифры в слова. «Центр — Юстасу…» Сообщение передавалось по открытому радиоканалу, но прочитать его мог только Штирлиц, потому что только он знал, как расшифровать переданные цифры. Шифрование — это не что иное, как сокрытие информации от посторонних.
Шифрование в том или ином виде существует много тысячелетий. Однако в середине XX века произошла своего рода революция. Если раньше шифровками пользовались, как правило, представители государственных спецслужб (или, если угодно, сами спецслужбы и даже государства), то к 70-м годам XX века стало ясно, что совсем скоро шифрование понадобится самым обычным людям, причем не изредка, а буквально каждый день. Это связано с лавинообразным развитием технологий, плоды которых доступны каждому: компьютеры, сотовые телефоны и тому подобное.
Каждый раз, когда вы вводите свой пароль или номер кредитной карты на сайте, вы отправляете личную конфиденциальную информацию по открытым каналам интернета. У многих к этим каналам есть доступ, например у вашего интернет-провайдера. В принципе перехватить ваше сообщение может даже компьютерщик-любитель с обычным ноутбуком и подходящим для этой цели программным обеспечением. Конфиденциальность информации обеспечивается именно тем, что она передается в виде шифровки. Вы можете легко узнать сайты, на которых действует протокол безопасной передачи данных: в этом случае веб-адрес начинается с https://... HTTP — обычный протокол передачи данных по интернету. А дополнительная буква S происходит от английского слова secure (безопасный) и означает, что данные будут передаваться в зашифрованном виде.
Каким образом зашифровывается и расшифровывается ежедневный гигантский поток конфиденциальной информации? Естественно, математика, как всегда, опережала технологии и стояла у их истока. Задачами шифрования занимается криптография — очень активная и интересная область математики и информатики.
В зашифрованном сообщении каждая буква заменяется какой-либо другой буквой, числом или знаком. Например, возьмем самый простой шифр. Будем зашифровывать каждую букву следующей буквой алфавита. Вместо А напишем Б, вместо Б — В и так далее, а вместо Я — А. Например, слово ПРИВЕТ будет выглядеть так: РСЙГЁУ
Это очень простой шифр, потому что каждая буква всегда зашифровывается одной и той же буквой, и взломать его — пара пустяков. Достаточно угадать одно слово в сообщении . Например, мы догадались, что сообщение начинается со слова «привет», и вот в нашем распоряжении уже шифры для шести букв: П, Р, И, В, Е и Т. С их помощью мы можем угадать другие слова, пока наконец не расшифруем весь алфавит. Именно так расшифровал секретные послания Шерлок Холмс в рассказе «Пляшущие человечки».
Конечно, любой серьезный шифр гораздо сложнее. Например, одна и та же буква, скажем А, может каждый раз обозначать разные буквы. Или, как в фильме «Семнадцать мгновений весны», буквы могут быть зашифрованы с помощью цифрового кода. Понятно, что у Штирлица в сборнике Шиллера были не стихи, а ключи для расшифровки секретных сообщений. Если бы у Штирлица не было этой книги, то для него, как и для диктора, цифры так и остались бы только цифрами.
В протоколах интернета ключом может быть всего лишь одно число, которое необходимо «подставить в формулу» для расшифровки. В данном случае «формула» — это очень длинная последовательность достаточно сложных операций.
Если вы сумели перехватить или вычислить ключ противника, то все его секреты — в вашем распоряжении. В этой главе мы расскажем, как с помощью математики удается генерировать ключи для передачи конфиденциальной информации по интернету. Причем завладеть этими ключами невозможно или по меньшей мере очень дорого — для это требуются колоссальные компьютерные ресурсы.
Но для начала давайте познакомимся со знаменитой шифровальной машиной «Энигма», которая использовалась немецкой армией во время Второй мировой войны. Это один из самых изощренных шифров той эпохи, когда шифрование еще не было таким массовым и обыденным явлением. А ключ к этому шифру нашел английский математик Алан Тьюринг.
Фильм «Игра в имитацию» (2014) — именно об этой потрясающей истории . К сожалению, в нем не объясняется, как устроена «Энигма» и как Тьюринг взломал этот шифр. Наш рассказ хотя бы частично восполнит эти упущенные подробности. Мы воспользуемся видео Кембриджского университета. Очень рекомендуем посмотреть их, чтобы увидеть «Энигму» в действии (первое и второе).
«Энигма» совсем небольшая, по размеру сравнима с печатной машинкой. Снаружи она состоит из клавиатуры и панели, на которой расположены буквы с подсветкой. Если нажать букву на клавиатуре, скажем A, то на панели высветится другая буква, например Q. Это означает, что в шифровке в этом месте вместо А появится Q. Внутри у машины три вращающихся диска, и их положение меняется после набора каждой буквы. Диск повернулся, провода соединились по-другому, и когда мы в следующий раз нажимаем А, на панели высвечивается уже не Q, а, скажем, G.
В набор «Энигмы» входят пять дисков, использовать можно любые три, в любом порядке. У каждого диска — 26 изначальных положений. И это еще не все. В военном варианте у «Энигмы» была передняя панель с буквами и 10 кабелей. Каждый кабель соединял две любые буквы между собой, и при шифровании они менялись местами. Диски можно было перебрать достаточно быстро, но количество комбинаций на панели было настолько велико, что перебрать их было невозможно. Всего у «Энигмы» было
158 962 555 217 826 360 000
возможных изначальных установок. Каждые сутки ровно в полночь они менялись. Новое изначальное положение дисков, новые пары букв на панели. Перебрать все комбинации за 24 часа было совершенно нереально. Шифр считался неуязвимым.
Зашифрованное сообщение передавали по радио. У немецкого офицера, который его получал, была такая же машина. Кроме того, он имел секретный документ — установки «Энигмы» на каждый день текущего месяца. Это был ключ к шифру машины. Офицер соединял нужные пары букв, ставил диски в заданное исходное положение, набирал Q, и на панели высвечивалась А. Поступая и дальше таким образом, он расшифровывал секретное сообщение.
Перехватить документ с установками хоть и было непросто, но иногда удавалось, а потом месяц заканчивался и разгадать шифр опять не представлялось возможным.
Алан Тьюринг и его команда совершили настоящий прорыв. Они научились разгадывать шифр каждое утро всего за 20 минут! Мы только вкратце объясним, как им это удалось.
Прежде всего в шифре было слабое место. Буква никогда не превращалась сама в себя. Это стало хоть какой-то зацепкой. Важным оказалось и предположение, что сообщения утром начинаются с чего-то однотипного, например с прогноза погоды. По-немецки wetterbericht. Зная, что буква не превращается сама в себя, мы можем найти слово в начале шифровки, которое в принципе может обозначать wetterbericht. Теперь нужно отыскать такую изначальную установку, чтобы шифр совпал с расшифровкой.
Очень важно определить, какие буквы соединены в пары, потому что здесь вариантов особенно много. Поскольку никаких сведений нет, начинать приходится наобум. Зато дальше из первой догадки следуют сразу несколько других.
Для ускорения процесса Алан Тьюринг сделал две существенные вещи. Во-первых, он понял, что если пара букв оказалась неправильной, то и все другие пары, следовавшие из нее, тоже неправильные. А значит, их уже не надо проверять. Во-вторых, он построил огромную машину, которая с помощью электрического тока позволяла исключить все неправильные пары одновременно. Оставалось только повторить операцию для каждой позиции дисков, а на это уходило всего 20 минут.
Интересно, что принцип решения Тьюринга заключался не в том, чтобы найти правильный вариант, а в том, чтобы исключить неправильные варианты и сделать это максимально быстро! Это была огромная работа и колоссальное достижение, сильно повлиявшее на ход Второй мировой войны.
Заметим, кстати, что в математике есть понятие «машина Тьюринга», но это вовсе не та машина, которая вычисляла ключ «Энигмы». «Машина Тьюринга» — абсолютно абстрактная концепция, формально описывающая работу компьютера. Это очень важная фундаментальная концепция в математике и информатике, но она выходит за рамки нашей книги.
Подробнее читайте:
Литвак, Нелли. Кому нужна математика? Понятная книга о том, как устроен цифровой мир / Нелли Литвак, Андрей Райгородский. — М. : Манн, Иванов и Фербер, 2017. — 192 с.