Итак, остаток 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 цифр:
Если вы попытаетесь взломать это число из 617 цифр, поочередно пробуя одно простое число за другим, вы переберете больше чисел, чем имеется атомов во Вселенной, до того, как доберетесь до множителей. Неудивительно, что никто не подал заявку на приз, и в 2007 г. данное предложение было снято.
Эти коды, основанные на простых числах, не только не поддаются взлому, но и обладают довольно инновационным свойством, которое решило проблему, преследовавшую все предыдущие коды. Ведь обычные коды были подобны ключу, который используется как для того, чтобы запереть дверь, так и для того, чтобы открыть ее. А изобретенные коды для интернета схожи с замком нового образца: он запирается одним ключом, а отпирается другим. Это позволяет веб-сайту свободно раздавать ключи для запирания сообщений, в то время как другой ключ, позволяющий отпирать их, хранится в большой тайне. Если вы достаточно отважны, изучите славные детали того, как на самом деле работает кодирование в интернете. Мы начнем с того, что познакомимся с любопытным калькулятором.
Что такое часовой калькулятор?
Передовые коды, которые используются в интернете, на самом деле опираются на математическое изобретение, которому сотни лет, сделанному, когда никто и не мечтал об интернете. Я имею в виду часовой калькулятор. В следующем разделе мы узнаем, как часовые калькуляторы используются при кодировании в интернете, но сначала давайте познакомимся с принципом их работы. Сперва рассмотрим случай 12-часового циферблата. Мы все знакомы со сложением на таких часах – мы понимаем, что через четыре часа после 9 будет 1 час. Это то же самое, что сложение чисел с последующим нахождением остатка при делении суммы на 12. Данное действие можно записать так:
Мы пишем «modulo 12», потому что 12 – это модуль, точка, после которой числа стартуют снова. Мы можем находить подобные суммы и на часах с другим количеством часовых делений, не ограничиваясь двенадцатью. Так, в случае 10 часов на циферблате:
А как умножаются числа на часовом калькуляторе? Умножение сводится к прибавлению определенное количество раз. Например, 4 × 9 означает, что нужно взять четыре девятки и сложить их вместе. Где окажется стрелка на 12-часовом циферблате после сложения четырех девяток? 9 + 9 – то же самое, что 6 часов. Каждый раз, когда мы прибавляем последующую девятку, часовая стрелка движется назад на 3 часа. В конце она окажется на 12 часах. Поскольку 0 – крайне важное число в математике, мы далее будем называть это положение, которое заканчивает круг и начинает следующий, 0 часов. Итак, у нас получится странный на вид ответ:
А как будет происходить возведение какого-либо числа в степень? Давайте рассмотрим 94, что означает перемножение четырех девяток. Мы только что научились делать модульное умножение, поэтому должны легко справиться и с этим. Поскольку числа становятся большими, будет легче взять остаток от деления на 12, чем следить за числами на часах. Начнем с 9 × 9, что равняется 81. Каков будет остаток при делении на 12, другими словами, чему соответствует 81 час на циферблате? Оказывается, остаток равен снова 9. Сколько бы мы ни перемножали 9, всякий раз мы опять придем к 9:
Ответ на часовом калькуляторе можно получить, сделав вычисления на обычном калькуляторе и затем взяв остаток от деления на число часовых делений. Но сила часового калькулятора состоит в том, что часто вам вовсе не требуется совершать вычисление на обычном калькуляторе. Вы можете найти, чему равно 799, на 12-часовом калькуляторе? Подсказка: сначала вычислите 7 × 7, а потом снова умножьте результат на 7. Вы видите закономерность?