Как использовать часы для отправки секретных сообщений через интернет

Мы теперь почти готовы показать, как эти часы применяются для обмена секретными сообщениями в интернете.

Когда вы покупаете что-либо на веб-сайте, номер кредитной карты кодируется вашим компьютером, который использует публичный часовой калькулятор данного веб-сайта. Итак, веб-сайт должен сообщить вашему компьютеру, сколько часов на его калькуляторе. Это первое из двух чисел, которые получает ваш компьютер. Давайте назовем его 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-часовом калькуляторе

Но как мы можем быть уверены, что 29, закодированное число покупателя, надежно защищено? В конце концов, хакер может перехватить это число, когда оно путешествует по интернету. Также он может легко найти открытый ключ Боба, состоящий из 33-часового калькулятора и инструкции возвести номер кредитной карты в 7-ю степень. Все, что необходимо хакеру, чтобы взломать код, – найти число, 7-я степень которого, вычисленная на 33-часовом калькуляторе, равна 29.

Нет необходимости говорить, что это совсем нелегко. Даже при обычной арифметике, когда можно возвести число в квадрат на клапане конверта, значительно труднее совершить обратное действие и извлечь квадратный корень. При вычислении степеней на часовом калькуляторе появляется дополнительное усложнение. Очень скоро вы теряете из вида число, с которого стартовали, потому что величина ответа совершенно теряет связь с этим числом.

В нашем примере числа достаточно малы, чтобы хакер мог попытаться, пробуя различные изменения, найти ответ. Но на практике веб-сайты используют часовые калькуляторы, у которых в числе часовых делений более 100 цифр, поэтому метод перебора становится невозможным. Вы также можете задаться вопросом, каким же образом компания, ведущая продажи в интернете, извлекает номер кредитной карты покупателя, если настолько трудно решить эту задачу на 33-часовом калькуляторе?

Обобщение малой теоремы Ферма, найденное Эйлером, гарантирует существование магического декодирующего числа D. Боб может найти произведение D множителей, каждый из которых равен закодированному номеру кредитной карты, и восстановить исходный номер кредитной карты. Но вы можете определить число D, только если знаете секретные простые числа p и q. Знание этих простых чисел становится ключом к раскрытию кодов интернета, потому что вам требуется решить следующую задачу на секретном часовом калькуляторе:

E × D = 1 (modulo (p –  1) × (q – 1)).

Когда мы подставим наши числа, то придем к уравнению

7 × D = 1 (modulo 2 × 10).

Значит, вопрос состоит в нахождении числа, которое при умножении на 7 дает результат, который при делении на 20 дает остаток 1. D = 3 подойдет, потому что 7 × 3 = 21 = 1 (modulo 20).

И, если мы возведем закодированный номер кредитной карты в третью степень, вновь появится исходный номер:

29³ = 2 (modulo 33).

Возможность восстановления номера кредитной карты из закодированного сообщения зависит от знания секретных простых чисел p и q. Поэтому любому, кто захочет взломать коды из интернета, необходимо найти способ разложить число N на простые множители. Каждый раз, когда вы покупаете книгу онлайн или скачиваете музыкальный трек, вы используете магию простых чисел для защиты вашей кредитной карты.

Вопрос на миллион долларов