Журнал «Компьютерра» № 31 от 29 августа 2006 года - Компьютерра - Страница 30

На плоскости это делается так, как показано на рисунке выше. Чтобы сложить две точки на эллиптической кривой, нужно провести через них прямую. Она пересечет кривую в третьей точке. Эту третью точку мы будем считать суммой первых двух со знаком минус; чтобы получить собственно сумму, отразим полученную точку относительно оси X. Можно проверить, что такое сложение будет ассоциативным. Остается только один вопрос: что делать, когда третьей точки нет? Например, если нужно сложить точку с самой собой, то для этого нужно провести касательную в этой точке. Если мы проведем касательную в точке (0, 0), она будет направлена вертикально вверх; казалось бы, никакой третьей точки уже не получится. Это затруднение решается просто: к множеству решений эллиптического уравнения добавляют еще одну точку O, о которой проще всего думать как о бесконечности (бесконечные значения x и y действительно удовлетворяют уравнению). Сумма двух точек (0, 0) в нашем примере будет равна O. O играет роль нуля в этом своеобразном сложении. Мы уже говорили, что обратный элемент получится, если отразить точку относительно оси X; если теперь соединить прямой точку и ее обратную, прямая будет вертикальной, и третьей точкой как раз будет бесконечность:

P+(—P)=O.

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

Вот, собственно, и все. Эллиптический аналог криптосистемы Диффи-Хеллмана выглядит так. Алиса и Боб выбирают (и сообщают всем) эллиптическую кривую, поле и точку B, лежащую на этой кривой. Затем Алиса секретно выбирает число a и подсчитывает точку aB (складывает B с самой собой a раз), а Боб выбирает число b и вычисляет bB. Затем они обмениваются полученными результатами, и их общим секретным ключом становится точка abB. Чтобы взломать этот шифр, нужно научиться по aB и B вычислять a — это в точности аналог дискретного логарифмирования!

В чем же преимущество шифров, основанных на эллиптических кривых? В том, что в них можно использовать меньшие по величине простые числа, чем в классических системах с открытым ключом.

Напоследок поговорим о том, что многим кажется серьезной угрозой для современной криптографии, — квантовых компьютерах и их возможностях. Прежде всего напомню, что квантовая информатика фактически ведет свою историю с того, что Питер Шор (Peter Shor) в 1994 году представил алгоритмы, которые за полиномиальное время раскладывали числа на простые множители и подсчитывали дискретные логарифмы — на квантовом компьютере, разумеется.

Секретный ключ Алисы в RSA — это два простых числа p и q. Чем больше эти числа, тем шифр надежнее. Именно поэтому многие организации готовы платить деньги за большие простые числа; давно существуют онлайн-проекты распределенных вычислений по поиску простых чисел. Алиса публикует произведение этих чисел N=pq. Ключевое предположение, на котором основана RSA, — то, что большое число трудно разложить на множители. То есть N можно распространять, а p и q все равно никто не узнает.

Кроме собственно N в открытый ключ входит также число e, которое должно быть меньше числа ? (N)=(p-1)(q-1) и взаимно просто с ним.[ ?(N) — это функция Эйлера, играющая очень важную роль в теории чисел; здесь, правда, используется ограниченный частный случай; в общем случае функция Эйлера от n равна количеству чисел, меньших n и взаимно простых с ним. ] Секретный же ключ — такое число d, что de ? 1 mod ? (N). Алиса может с легкостью вычислить d, но никто другой на это не способен — ведь если трудно разложить N на множители, то трудно и подсчитать функцию Эйлера. Боб теперь, желая зашифровать свое сообщение m, вычисляет y ? m e mod N и передает его Алисе (и всем желающим). Алиса может расшифровать его, вычислив y d ? m ed ? m mod N (последнее сравнение выполняется благодаря малой теореме Ферма — не путать с заметкой на полях «Арифметики»; доказательство малой теоремы достаточно просто и входит в любой базовый учебник теории чисел).

Было бы наивно ожидать, что криптосистемы на эллиптических кривых, столь похожие на дискретное логарифмирование, не поддадутся квантовому компьютеру. И действительно, алгоритм Шора можно без особого труда модифицировать так, чтобы он взламывал описанный выше протокол, а равно и другие аналоги классических криптосистем, основанные на эллиптических кривых.

Но бояться этого, по моему личному мнению, не следует. Квантовые компьютеры сейчас находятся в самом начале своего пути. Пока никто не может предсказать, удастся ли построить квантовый компьютер хоть сколько-нибудь интересного с практической точки зрения размера (текущие рекорды — семь кубитов, одиннадцать кубитов — как-то не впечатляют). А для работы алгоритма Шора, например, нужен квантовый компьютер на стольких кубитах, сколько классических битов в раскладываемом простом числе; на меньшем числе просто ничего не получится. Скорее всего, в ближайшие десятилетия квантовые компьютеры, способные взломать даже сегодняшние шифры, не появятся. А если и появятся — уже существует и активно развивается так называемая квантовая криптография.

Суть криптосистемы Диффи-Хеллмана в том, чтобы перед началом коммуникации с секретным ключом об этом самом ключе договориться (этот процесс в криптографии называют «протоколом key agreement»; кстати, в реальных приложениях криптография с открытым ключом очень часто используется именно для этой цели). Иными словами, цель не в том, чтобы передать сообщение от одного участника к другому, а в том, чтобы у обоих участников в конце концов обнаружилось одно и то же число, которое можно будет использовать как секретный ключ [Есть и «настоящая» криптосистема с открытым ключом, основанная на той же идее — так называемая система ElGamal; она немногим сложнее Диффи-Хеллмана, но описание ее более громоздко, и поэтому для иллюстрации Диффи-Хеллман подходит лучше]. Делается это так: Алиса и Боб выбирают простое число p, по модулю которого будут проводиться все вычисления, и основание g, которое они потом будут возводить в степень. Затем Алиса выбирает число a (никому его не показывая) и передает Бобу (g^a mod p), а Боб выбирает число b и передает Алисе (g^b mod p). Теперь Алисе достаточно возвести полученное число в степень a, а Бобу — в степень b, и у них обоих будет один и тот же ключ, так как, разумеется, g^ab mod p = g^ba mod p. Как видите, ничего сложного. Почему же этот шифр трудно разгадать? Стойкость этой криптосистемы тесно связана с вычислительной трудностью операции дискретного логарифмирования — зная g^a mod p, g и p (все эти числа в принципе доступны противнику), вычислить a. Отметим, что взлом Диффи-Хеллмана вовсе не обязательно решит задачу дискретного логарифмирования — этот вопрос еще остается открытым, но если научатся эффективно вычислять искать дискретные логарифмы, то и Диффи-Хеллман падет тут же.

Редакция благодарит профессора Колледжа Лафайет (Lafayette College) Клиффорда Рейтера (Clifford Reiter) за предоставленные изображения множеств Жюлиа.

ПИСЬМОНОСЕЦ: Прикол в пространстве Лобачевского!

Автор: Леонид Левкович-Маслюк

Живу в глуши, Интернет через дайлап, качаю да читаю «Компьютерру»! Красота! Да, о чем это я? Ах, да! Жил был один англичанин и состряпал сайт на миллион!!! Долларов почему-то, а не фунтов. Ну да ладно, это мелочи, я о своем. О сайте в смысле. Состряпал я сайт www.historyinternet.ru , и вот сижу и думаю, будет у меня миллион рублей или нет? Ну там рублем больше, рублем меньше. Ну почему больше — ответ на сайте. В общем там больше чем 1 000 000. Думаю, программисты меня поймут. Ну вот и все!