Подобные приемы лежат в основе так называемого кода с коррекцией ошибок, применяемого компьютерами для исправления ошибок, которые могли вкрасться в сообщения при их передаче. Замените орлы и решки на нули и единицы, и внезапно сетка становится цифровым сообщением. Например, каждый столбец в сетке 5 × 5, первоначально выложенной для показа фокуса, мог бы представлять букву в коде Бодо. Тогда сетка 5 × 5 стала бы сообщением длиной в пять букв. Дополнительные строки и столбцы добавляются компьютером для отслеживания ошибок.
Следовательно, пожелай мы отправить кодированное сообщение о третьем альбоме Coldplay, можно воспользоваться тем же приемом, что и ранее, примененным к сетке 5 × 4. Это даст возможность понять, где и когда вкрадываются ошибки. Вот как должно выглядеть название альбома, если цветные блоки заменить на 1, а пропуски на 0:
Таблица 4.10
Теперь добавим дополнительную строку и столбец с нулями и единицами, чтобы обозначить, четное или нечетное количество единиц имеется в каждой из строк и столбцов:
Таблица 4.11
Теперь представим, что при передаче сообщения произошла ошибка, и одно из чисел изменилось. В результате графический дизайнер получил вот что:
Таблица 4.12
Проверяя контрольные цифры в последнем столбце и строке, дизайнер может заметить ошибку. В данном случае имеется несоответствие во второй строке и в третьем столбце.
Подобные коды с коррекцией ошибок используются повсюду, от CD-дисков до связи с космическими аппаратами. Вы знаете, как бывает при разговоре по телефону, когда вы не можете разобрать все, что говорит ваш собеседник. При связи компьютеров друг с другом могут возникнуть схожие проблемы. Но использование умной математики позволило нам предложить такие варианты кодирования данных, которые помогают избавиться от этих сбоев. Именно так поступило агентство НАСА, когда космический аппарат «Вояджер-2» выслал первые фотографии Сатурна. Использование кодов с коррекцией ошибок позволило специалистам НАСА превратить неразборчивые изображения в кристально четкие.
Как честно кидать монету через интернет
Коды с коррекцией ошибок позволяют четко передавать информацию. Но зачастую мы хотим воспользоваться нашими компьютерами, чтобы поделиться секретными сведениями. Мария, королева Шотландии, лорд Нельсон или кто-либо другой, вознамерившийся обмениваться секретными сообщениями, должен был сначала встретиться со своим агентом, чтобы договориться о коде, который будут использовать обе стороны. Но в наш компьютерный век у нас то и дело появляется необходимость послать секретные сведения. При совершении покупок онлайн мы щелкаем по веб-сайтам и посылаем данные своих кредитных карт людям, с которыми никогда не встречались. Совершение сделок через интернет было бы невозможно со старой криптографией, когда требовалась первоначальная встреча с глазу на глаз. К счастью, у математики есть решение.
Чтобы объяснить его идею, давайте начнем с простого сценария. Я собираюсь играть в шахматы через интернет. Я живу в Лондоне, а мой соперник – в Токио. Мы хотим бросить монету, чтобы решить, кто будет ходить первым. «Орел или решка?» – спрашиваю я у своего соперника по электронной почте. «Орел», – отвечает он. Я подбрасываю монету и пишу: «Решка. Я начинаю». Существует ли возможность удостовериться, что я не сжульничал?
Как это ни поразительно, вы можете честно бросать монету через интернет. Такая возможность появляется благодаря математике простых чисел. Все простые числа нечетны за исключением 2 (это странное простое число, ведь лишь оно четно). Если мы разделим одно из этих нечетных простых чисел на 4, то получим в остатке 1 или 3. Например, остаток от деления 17 на 4 равен 1, а при делении 23 на 4 в остатке получается 3.
Как мы узнали в главе 1, две тысячи лет назад древние греки доказали, что существует бесконечно много простых чисел. Но существует ли бесконечно много тех из них, которые дают при делении на 4 остаток 1, или бесконечно много дающих остаток 3? Это один из тех вопросов, которые Пьер де Ферма поставил перед математиками 350 лет назад, однако ответ был дан лишь в XIX в. немецким математиком Густавом Лежёном Дирихле. Используя очень сложный математический аппарат, он сумел доказать, что половина простых чисел дает остаток 1, а другая половина 3 – никакой из остатков не оказывается предпочтительнее. Впрочем, не совсем легко понять, что математики имеют в виду под половиной, когда речь идет о бесконечном множестве. Но, по существу, это означает, что если вы возьмете простые числа, меньшие заданного большого числа, то почти в точности половина из них даст при делении на 4 остаток 1.
Итак, остаток 1 или 3 при делении простого числа на 4 не более «предвзят», чем выпадение орла или решки при подкидывании честной монеты. Для изучения нашей задачи по бросанию монеты давайте отождествим орлы с простыми числами, дающими остаток 1 при делении на 4, а с решками мы отождествим простые числа, дающие остаток 3. А теперь последует искусный математический пассаж. Если я возьму два простых числа, скажем 17 и 41, оба из которых относятся к орлам – они дают остаток 1 при делении на 4, – и перемножу их, то произведение также будет характеризоваться остатком 1 при делении на 4. Например, 41 × 17 = 697 = 174 × 4 + 1. Если же я возьму два простых числа, скажем 23 и 43, оба из набора решек – они дают остаток 3 при делении на 4… то получится не то, чего вы могли бы ожидать. У произведения этих двух чисел при делении на 4 также будет остаток 1: в данном случае 23 × 43 = 989 = 247 × 4 + 1. Итак, произведение простых чисел не дает намека на то, взяты ли сомножители из набора орлов или из набора решек. Этим свойством мы можем воспользоваться, чтобы играть в «орла или решку по интернету».
Если я подброшу монету и выпадет орел, я выберу два простых числа из набора орлов и перемножу их. Если выпадет решка, я выберу два простых числа из набора решек и перемножу их. После того как я подкинул свою монету и сделал вычисления, я посылаю ответ моему сопернику в Токио. Оказалось, что он равен 6497. Поскольку ответ при делении на 4 всегда дает остаток 1, мой соперник не может, не зная простых чисел, сказать, выбрал ли я их из набора орлов или же из набора решек. Теперь он может сказать «орел» или «решка».
Чтобы мой соперник убедился, что он выиграл или проиграл, мне достаточно будет выслать ему два выбранных мною простых числа. В данном случае ими были 89 и 73, два простых числа из набора орлов. Поскольку никакие другие числа при перемножении не дадут 6497, то я предоставил ему достаточно информации, чтобы доказать, что я не жульничал. С другой стороны, я не предоставил ему достаточно информации, чтобы мой соперник мог жульничать.
На самом деле это не совсем верно. Если соперник сумеет разложить 6497 на простые множители 89 и 73, то он поймет, что нужно сказать «орел». Но, если я буду выбирать достаточно большие простые числа (много-много бо́льшие двузначных чисел), то будет почти невозможно даже с современными вычислительными возможностями разложить произведение на простые множители. Схожий принцип используется в кодах, которые защищают номера кредитных карт, посылаемые через интернет.
Я бросил монету, выбрал два простых числа из набора орлов или из набора решек и перемножил их. У меня получилось число 13 068 221. Что выпало? Орел или решка? Постарайтесь найти ответ без компьютера (решение приведено в конце главы).
А что скажете, если получилось число
На этот раз можно использовать компьютер.
Почему разложение чисел означает взлом кода?
Боб – администратор веб-сайта, продающего футболки в Англии. Элис живет в Сиднее, и она намеревается купить футболку на сайте и при этом послать данные своей кредитной карты так, чтобы никто другой не смог увидеть их. Боб размещает специальное кодовое число на своем веб-сайте, скажем 126 619. Это кодовое число чем-то напоминает ключ, который запирает сообщение Элис и делает его защищенным. Поэтому, когда Элис посещает веб-сайт, она получает копию кодирующего ключа, опубликованного Бобом, и использует его, чтобы «запереть» свою кредитную карту.
В реальности компьютер Элис совершает специальное математическое вычисление, использующее этот ключ, 126 619, и номер ее кредитной карты. Теперь этот номер зашифрован и может быть послан открытым образом через интернет на веб-сайт Боба. (Детали упомянутого вычисления приведены в следующем разделе.) Но постойте, разве при этом не возникнет проблема? Предположим, я хакер. Тогда что помешает мне посетить веб-сайт Боба, получить копию кодирующего ключа и расшифровать сообщение? Однако кодирование в интернете устроено довольно интригующе: вам нужен другой ключ, чтобы отпереть дверь, а этот отпирающий ключ хранится в большом секрете в офисе Боба.
Декодирующий ключ представляет собой два простых числа, которые при умножении дают то самое число 126 619. В действительности Боб выбирает два простых числа 127 и 997, чтобы изготовить свой кодирующий ключ. Именно с помощью этих двух простых чисел Боб дешифрует то математическое вычисление, которое совершил компьютер Элис, чтобы закодировать номер ее кредитной карты. Боб поместил кодирующий ключ 126 619 на своем веб-сайте, но хранит в тайне декодирующие простые числа 127 и 997.
Если я смогу найти два простых числа, которые при умножении дают 126 619, я сумею получить доступ к номерам кредитных карт, посылаемым на веб-сайт Боба. Но 126 619 – достаточно небольшое число, чтобы я мог делить его на одно число за другим. Так, потратив не слишком много времени, я нашел бы два простых числа 127 и 997. Однако вы не сможете воспользоваться этим приемом на настоящих веб-сайтах, потому что их ключи основаны на значительно бо́льших числах – они настолько велики, что найти пару простых чисел методом проб и ошибок почти невозможно. Математики, придумавшие эти коды, были настолько уверены в их надежности, что на протяжении многих лет предлагали приз $ 200 000 тому, кто сможет найти два простых множителя следующего числа из 617 цифр: