Задачка на основы криптографии с подробным разбором

Как удостовериться, что у друга есть ваш номер телефона так, чтобы никто об этом не узнал, причём нельзя спросить его напрямую?

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

Даже если вы дадите короткий и простой ответ, вас могут попросить представить и ответ на основе RSA. Он не такой сложный, если у Пети есть компьютер, и если он сможет следовать вашим рекомендациям. Спросите интервьюера, насколько Петя продвинут в математике и компьютерах.

При использовании RSA генерируется два ключа: общественный и частный. Общественный ключ похож на адрес электронной почты. Он позволяет любому человеку отправить вам сообщение. Частный ключ — это что-то вроде вашего пароля к электронной почте. Вам он необходим, чтобы получить ваши е-мейлы, и вы должны держать его в секрете, так как в противном случае сообщение, адресованное вам, сможет прочитать любой желающий.

Вы не сможете послать Пете секретное сообщение, поскольку он не создал свои ключи. Он, может быть, даже не знает, что такое RSA, и не будет о нем ничего знать до тех пор, пока вы ему не расскажете! Но для этого вам и не нужно отправлять ему секретное сообщение. Вы хотите, чтобы Петя отправил такое сообщение вам, а именно — ваш номер телефона. Это означает, что нам нужны ключи для себя, а не для Пети. Вот общая схема решения.

«Привет, Петя! Мы собираемся воспользоваться криптографией RSA. Может быть, ты не знаешь, что это такое, но я объясню тебе, что надо сделать. Вот мой общественный ключ… Возьми его и мой номер телефона и придумай зашифрованный номер, следуя инструкциям. Пришли этот зашифрованный номер обратно мне через Катю».

Трюк в том, чтобы составить инструкцию так, чтобы ею мог воспользоваться практически каждый. К тому же вам нужно обеспечить и необходимую точность.

Криптография RSA впервые была описана, как теперь считается, в 1973 году. Её первым создателем был британский математик Клиффорд Кок, который тогда работал на секретной службе Её Величества. В те годы его схема считалась непрактичной: для нее обязательно нужен был компьютер. В те времена, когда шпионы обычно обходились фотоаппаратами, спрятанными в запонки, эту трудность было не так легко преодолеть. До 1997 года идея Кока считалась секретной. Однако в 1978 году трое ученых из MIT, Рональд Ривест, Ади Шамир и Леонард Адлеман, предложили ее независимо от Кока. Первые буквы их фамилий (RSA) стали акронимом и названием этого алгоритма.

В системе RSA человек, который хочет получать сообщения, должен выбрать два случайных простых числа p и q. Числа должны быть большими и, по крайней мере, такими же крупными (по числу цифр), как и числа или сообщения, которые надо передать. Для телефонного номера из десяти цифр р и q также должны состоять (каждое) по крайней мере из десяти цифр.

Один из способов выбора p и q — воспользоваться Google и найти веб-сайт, на котором перечисляются крупные простые числа. Скажем, Primes Pages, который ведет Крис Колдуэлл из Университета Теннесси в Мартине. Выберите случайным образом два десятизначных простых числа. Вот пример такой парочки:

1 500 450 271 и 3 367 900 313.

Назовите их соответственно р и q. Вам придется перемножить их и получить точный ответ. Здесь может быть небольшая трудность, так как вы не сможете воспользоваться калькуляторами, Excel или Google, да и большинством любых других потребительских программ, поскольку они показывают ограниченное число значимых цифр. Один из вариантов — умножить вручную. Или использовать Wolfram Alpha. Введите

1 500 450 271 и 3 367 900 313

и вы получите точный ответ:

5 053 366 937 341 834 823.

Назовите это произведение N. Оно является одной из составляющих вашего общественного ключа. Другим компонентом является число, называемое е, произвольно выбранное и равное по длине, в идеале N, но которое не делится точно на произведение (р - 1) (q - 1). Я, возможно, запутал вас последним предложением, но пока об этом не беспокойтесь.

Во многих прикладных программах в качестве е шифровальщики выбирают простую тройку. Этот достаточно хороший вариант для многих целей и позволяет быстро шифровать.

Вы получили N и е, у вас теперь имеется все необходимое для решения задачи. Всего лишь нужно отправить эти два числа Пете, а также полное «Руководство для чайников по криптографии RSA». Пете необходимо вычислить

хe mod N,

где Х – это номер телефона. Поскольку в качестве e мы выбрали 3, часть слева — это х, возведенное в куб. Это будет число из 30 цифр. «Mod» указывает на деление по модулю, что означает, что вы разделите x³ на N и возьмете только остаток. Этот остаток должен быть в диапазоне от 0 до N - 1. Вполне вероятно, что будет число из 20 цифр. Это число является зашифрованным посланием, которое Петя отправит обратно вам.

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

«Петя, я хочу, чтобы ты внимательно следовал этим инструкциям и не сомневался. Исходи из того, что мой телефонный номер — это обычное число из десяти цифр. Вначале необходимо, чтобы ты возвел в куб это число (умножь вначале его на само себя, а затем полученное произведение умножь еще раз на первоначальный номер). Ответ будет числом из 30 цифр, и оно должно быть точным. Выполни это умножение, даже если придется сделать это вручную, и дважды его проверь. Затем необходимо, чтобы ты осуществил самый длинный процесс деления за всю свою жизнь. Раздели полученный результат на число 5 053 366 937 341 834 823. Важно не ошибиться! Пришли мне только остаток этого деления. Важно, чтобы ты не прислал целую часть, а только остаток».

Предположим, что у Пети есть доступ к Интернету (довольно обоснованное допущение в настоящее время, не так ли?), тогда пишем:

«Петя, отправляйся на веб-сайт и www.wolframalpha.com. Ты увидишь там длинный прямоугольник с границами, окрашенными в оранжевый цвет. Введи мой номер телефона из 10 цифр в этот прямоугольник без всяких дефисов, точек и скобок, только десять цифр. Сразу же после номера телефона напечатай следующее

^3 mod 5053366937341834823.

Затем кликни на маленький знак равенства, находящийся в правой части прямоугольника. Ответом будет, вероятно, число из 20 цифр, которое появится в прямоугольнике со словом Result (Результат). Пришли мне этот ответ, и только этот ответ».

Естественно, Катя прочитает эти инструкции, а также прочитает ответ Пети. Но она не сможет ничего понять. Она получила число из 20 цифр, которое, как она знает, является остатком куба телефонного номера, разделенного на 5053366937341834823, по модулю. Пока никто не придумал эффективного способа, позволяющего восстановить по остатку исходное число, в данном случае являющееся телефонным номером.

Можете ли вы предложить что-то еще лучше? Да, поскольку у вас есть секретный декодирующий ключ. Это d, инверсивное значение е mod (р - 1) (q - 1). Для его вычисления имеется удобный алгоритм, которым можно воспользоваться, конечно, при условии, что вы знаете два простых числа p и q, которые были использованы для получения N. (Вы ведь знаете их, потому что сами их выбрали, не забыли?)

Назовите кодированное число/сообщение, которое Петя отправил вам назад. Y. Его первоначальное сообщение было

Yd mod N.

Для определения этого значения нужно всего лишь ввести это в Wolfram Alpha (замените Y, d и N фактическими числами).

Катя знает N, поскольку оно было написано на карточке, которую вы попросили её передать Пете. Она знает Y, поскольку это число было указано в ответе Пети, отправленном вам. Но она не знает d, и у нее нет возможности его выяснить. Катя сталкивается с алгоритмической трудностью. При умножении двух чисел никаких сложностей ни у кого не возникнет, ведь этому все-таки в школе всех научили. А вот определить множитель, имея огромное число, гораздо сложнее.

Разбор по книге «Действительно ли Вы достаточно умны, чтобы работать в Google?»