Тайны чисел. Математическая одиссея - читать онлайн книгу. Автор: Маркус Дю Сотой cтр.№ 53

Страница

(p – 1)! = (p – 1)! × А^{p – 1} (modulo p).

Из этого следует, что (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-часовым калькулятором. Таким образом, получается закодированное число C^E (modulo N), и именно его ваш компьютер посылает на веб-сайт.

Но как же веб-сайт декодирует это число? И снова магия простых чисел играет в этом ключевую роль. Давайте предположим, что N – простое число (позже мы увидим, что это не слишком подходит для надежного шифрования, зато данное предположение помогает понять, куда мы направляемся). Если мы перемножим числа C^E достаточное количество раз, то чудесным образом снова появится число С. Но сколько множителей (D), каждый из которых представляет C^E, мы должны взять? Другими словами, когда (C^E)^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 – число повторений последовательности.

Теперь мы знаем, что для того, чтобы декодировать сообщение C^E на часах с 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.

Вот умный способ вычислить 2⁷ на 33-часовом калькуляторе. Мы начинаем с перемножения 2: 2² = 4, 2³ = 8, 2⁴ = 16, 2⁵ = 32. Когда мы переходим к более высоким степеням 2, стрелка на циферблате движется дальше и дальше, и, когда мы возводим 2 в 6-ю степень, она совершает более чем оборот. Можно применить следующий небольшой трюк, из-за которого стрелка словно меняет направление движения, вместо того чтобы вращаться и дальше по часовой. Мы просто говорим, что 32 часа на нашем 33-часовом калькуляторе это –1 час. Потом, когда мы делаем два последующих умножения на 2, то получаем –4 часа, или 29 часов. Благодаря этому приему нам не требуется возводить 2 в 7-ю степень, что равно 128, и затем находить остаток при делении на 33. Для очень больших чисел подобный метод экономии неоценим для компьютерных вычислений, когда нужно сделать все как можно быстрее.

Рис. 4.17. Вычисление степеней 2 на 33-часовом калькуляторе

Страница