А × (n – m) равно нулю на часовом калькуляторе, то есть А × (n – m) на обычном калькуляторе делится на p.
Ключевым в следующем шаге доказательства будет использование того факта, что p – простое число. Подобно химической молекуле, число А × (n – m) построено из произведения атомов (простых чисел), составляющих А, и простых чисел, составляющих n – m. Но число p – простое, атом арифметики, и его нельзя расщепить далее. Поскольку А × (n – m) делится на p, это число должно быть одним из атомов, использованных при построении А × (n – m), ведь каждое число однозначно разлагается на простые множители. Но А не делится на p без остатка, поэтому p должно входить в список атомов, использованных при построении n – m. Другими словами, n – m делится на p. Но что это означает? Это означает, что n и m соответствуют одному и тому же времени на нашем p-часовом циферблате. Вы можете использовать схожую аргументацию, чтобы показать, что А × n не может быть нулем часов, если ни А, ни n не равны нулю часов.
Заметьте, что крайне важно то, что на циферблате простое число часов. Мы уже видели, что 4 × 9 равняется нулю на 12-часовом калькуляторе, хотя ни 4, ни 9 не равно нулю.
Теперь у нас есть два списка – 1, 2, …, p – 1 и А × 1, А × 2, …, А × (p – 1), – составленные из одних и тех же чисел, хотя и расположенных в разном порядке. Теперь мы можем воспользоваться эффектным трюком, который, вероятно, открыл сам Ферма. Если мы перемножим все числа в каждом из списков, то получим один и тот же ответ, потому что порядок перемножения не имеет значения. Первый список даст нам 1 × 2 × … × (p – 1), что мы можем записать как (p – 1)!. Второй список приводит к p – 1 множителю А и опять-таки произведению чисел от 1 до p – 1. После небольшой перестановки мы можем переписать это как (p – 1)!× Аp – 1. И эти два ответа равны на нашем часовом калькуляторе:
Из этого следует, что (p – 1)! × (1 – Аp – 1) делится на p, и мы можем использовать тот же трюк, что и ранее. Никакое из чисел 1, 2, …, p – 1 не делится на p, значит, (p – 1)! не может делиться на p. Единственная возможность состоит в том, что 1 – Аp – 1 делится на p. А это приводит к тому, что вычисление Аp – 1 на часовом калькуляторе всегда будет давать ответ 1 – предложением объяснить данный результат Ферма и раззадорил математиков.
В этой аргументации есть несколько интересных ингредиентов. Разумеется, немаловажно то обстоятельство, что если A × B делится без остатка на простое число p, то либо А, либо B должно также делиться на данное простое число. Это следует из специального свойства простых чисел. Но мне представляется красивым взгляд на список 1, 2, …, p – 1 с двух различных перспектив. Для меня это образец умения рассматривать задачу с разных сторон.
Как использовать часы для отправки секретных сообщений через интернет
Мы теперь почти готовы показать, как эти часы применяются для обмена секретными сообщениями в интернете.
Когда вы покупаете что-либо на веб-сайте, номер кредитной карты кодируется вашим компьютером, который использует публичный часовой калькулятор данного веб-сайта. Итак, веб-сайт должен сообщить вашему компьютеру, сколько часов на его калькуляторе. Это первое из двух чисел, которые получает ваш компьютер. Давайте назовем его N. В нашем примере с веб-сайтом футболок, администратором которого был Боб, это число равнялось 126 619. Также для совершения вычисления вашему компьютеру требуется второе кодирующее число, которое мы назовем Е. Номер вашей кредитной карты C кодируется путем возведения его в степень Е, причем вычисления совершаются N-часовым калькулятором. Таким образом, получается закодированное число CE (modulo N), и именно его ваш компьютер посылает на веб-сайт.
Но как же веб-сайт декодирует это число? И снова магия простых чисел играет в этом ключевую роль. Давайте предположим, что N – простое число (позже мы увидим, что это не слишком подходит для надежного шифрования, зато данное предположение помогает понять, куда мы направляемся). Если мы перемножим числа CE достаточное количество раз, то чудесным образом снова появится число С. Но сколько множителей (D), каждый из которых представляет CE, мы должны взять? Другими словами, когда (CE)D = C на p-часовом калькуляторе?
Конечно, последнее равенство выполнится, если E × D = p. Но p – простое число, поэтому такого числа D не может быть. Однако если мы продолжим перемножать С, то найдется другая точка, где мы гарантированно получим в ответе С. В следующий раз номер кредитной карты появится, когда мы возведем его в степень 2(p – 1) + 1. Он появится снова при возведении в степень 3(p – 1) + 1. Значит, чтобы найти декодирующее число, нам необходимо найти такое D, что E × D = 1 (modulo (p – 1)). Такое уравнение значительно легче решить. Но проблема в том, что Е и p – открытые числа, поэтому хакер также может легко найти декодирующее число D. Для безопасной процедуры мы можем воспользоваться открытием, которое сделал Эйлер о часах, на которых p × q, a не просто p часовых делений (p и q – простые числа).
Если вы возьмете время С на циферблате, где имеется p × q часов, то через сколько шагов последовательность C, C × C, C × C × C, … начнет повторяться? Эйлер обнаружил, что это произойдет через (p – 1) × (q – 1) шагов. Итак, чтобы вернуться к первоначальному времени, нужно возвести C в степень (p – 1) × (q – 1) + 1, или k × (p – 1) × (q – 1) + 1, где k – число повторений последовательности.
Теперь мы знаем, что для того, чтобы декодировать сообщение CE на часах с p × q часовыми делениями, нам требуется найти такое декодирующее число D, что E × D = 1 (modulo (p – 1) × (q – 1)). Итак, нам необходимо делать вычисления на секретном часовом калькуляторе с (p – 1) × (q – 1) часами. Хакер знает только числа N и Е, и он должен найти секретные простые числа p и q, чтобы получить секретный часовый калькулятор. Следовательно, взлом кодов интернета сводится к разложению числа N на простые множители. А как мы видели в разделе о подкидывании монеты через интернет, это фактически невозможно, когда числа достаточно большие.
Давайте посмотрим на коды интернета в действии, но для очень небольших p и q. Тогда нам легко будет проследить за происходящим. Пусть Боб выбрал для своего веб-сайта футболок простые числа 3 и 11, так что открытый часовой калькулятор, с помощью которого покупатели кодируют номера своих кредитных карт, имеет 33 часа. Боб хранит в тайне простые числа 3 и 11, потому что они являются ключом к декодированию сообщений. Но Боб не делает секрета из числа 33, ведь это число часов на открытом часовом калькуляторе. Вторая порция информации, которая доступна на веб-сайте Боба, – кодирующее число Е. Пусть оно равно 7. Каждый, кто покупает футболку на веб-сайте Боба, делает одно и то же: возводит номер своей кредитной карты в 7-ю степень на 33-часовом калькуляторе.
Сайт Боба посещает покупатель, который был одним из самых первых получателей кредитных карт, и ее номер равен 2. Возведите 2 в 7-ю степень на 33-часовом калькуляторе, что равно 29.
Вот умный способ вычислить 27 на 33-часовом калькуляторе. Мы начинаем с перемножения 2: 22 = 4, 23 = 8, 24 = 16, 25 = 32. Когда мы переходим к более высоким степеням 2, стрелка на циферблате движется дальше и дальше, и, когда мы возводим 2 в 6-ю степень, она совершает более чем оборот. Можно применить следующий небольшой трюк, из-за которого стрелка словно меняет направление движения, вместо того чтобы вращаться и дальше по часовой. Мы просто говорим, что 32 часа на нашем 33-часовом калькуляторе это –1 час. Потом, когда мы делаем два последующих умножения на 2, то получаем –4 часа, или 29 часов. Благодаря этому приему нам не требуется возводить 2 в 7-ю степень, что равно 128, и затем находить остаток при делении на 33. Для очень больших чисел подобный метод экономии неоценим для компьютерных вычислений, когда нужно сделать все как можно быстрее.
Рис. 4.17. Вычисление степеней 2 на 33-часовом калькуляторе
Но как мы можем быть уверены, что 29, закодированное число покупателя, надежно защищено? В конце концов, хакер может перехватить это число, когда оно путешествует по интернету. Также он может легко найти открытый ключ Боба, состоящий из 33-часового калькулятора и инструкции возвести номер кредитной карты в 7-ю степень. Все, что необходимо хакеру, чтобы взломать код, – найти число, 7-я степень которого, вычисленная на 33-часовом калькуляторе, равна 29.
Нет необходимости говорить, что это совсем нелегко. Даже при обычной арифметике, когда можно возвести число в квадрат на клапане конверта, значительно труднее совершить обратное действие и извлечь квадратный корень. При вычислении степеней на часовом калькуляторе появляется дополнительное усложнение. Очень скоро вы теряете из вида число, с которого стартовали, потому что величина ответа совершенно теряет связь с этим числом.