Наука: Эллиптическая криптография

Наука: Эллиптическая криптография

Автор: Сергей Николенко

But the security of cryptosystems based on elliptic curves is not well understood, due in large part to the abstruse nature of elliptic curves. Few cryptographers understand elliptic curves, so there is not the same widespread understanding and consensus concerning the security of elliptic curves that RSA enjoys. Over time, this may change, but for now trying to get an evaluation of the security of an elliptic-curve cryptosystem is a bit like trying to get an evaluation of some recently discovered Chaldean poetry.

«Стойкость криптосистем, основанных на эллиптических кривых, недостаточно изучена, во многом из-за переусложненного взгляда на природу самих эллиптических кривых. Очень немногие криптографы понимают, что такое эллиптические кривые, поэтому, в отличие от RSA, нет широкого понимания и консенсуса относительно стойкости, обеспечиваемой их использованием при шифровании. Со временем ситуация может измениться, но сейчас получить оценку стойкости криптосистемы, основанной на эллиптических кривых, - все равно что получить оценку недавно обнаруженной древневавилонской поэзии»

Рональд Ривест, создатель RSA, комментарии к предлагаемому стандарту FIPS, 1997

Когда я впервые услышал о криптосистемах, основанных на эллиптических кривых, они показались мне чем-то безумно сложным: жуткая криптография, в которой совершенно ничего понять невозможно. Дальше - больше: я немного узнал об алгебраической геометрии и о самих эллиптических кривых. Это, разумеется, тоже мгновенно отправилось в категорию «очень сложная наука» (алгебраическая геометрия действительно дело непростое), а соответствующие криптографические протоколы заняли еще более высокое место в моей личной иерархии.

Как вы уже, наверное, догадались, все изменилось в одночасье, когда мне довелось познакомиться с этими протоколами поближе. Оказалось, что идеи, лежащие в их основе, немногим сложнее классических схем RSA и Диффи-Хеллмана. Во всяком случае, суть «эллиптического шифрования» (будем иногда для краткости использовать этот не вполне корректный термин) я намереваюсь рассказать прямо сейчас, фактически с нуля.

Криптография с открытым ключом

Начать, наверное, следует с основ, на которых стоит современная криптография. Всевозможные хитроумные шифры, которые придумывали криптографы прошлого (от Цезаря до «Энигмы») по сути представляли собой системы с секретным ключом: существовало некое тайное знание (способ шифрования или ключ к нему), и тот, у кого был доступ к этому знанию, мог зашифровать и дешифровать любое сообщение.

Среди систем с секретным ключом есть очень стойкие: пока вы не узнаете или не подберете ключ, расшифровать сообщение невозможно. Более того, дешифровщику придется решать, является ли то, что у него получилось, валидным (проще говоря, «правильным») сообщением. Конечно, если был зашифрован текст на естественном языке, распознавание труда не составит. Кроме того, на помощь в случае естественного языка приходит еще и частотный анализ (вспомните Холмса, с помощью частотно-лингвистического анализа разгадавшего записки, написанные «пляшущими человечками»). Но если сообщение - набор цифр (координаты военной базы или количество самолетов на ней), то дешифровальщику может быть практически невозможно установить, правильно ли оно расшифровано.

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

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

Криптография с открытым ключом разрывает этот круг. В криптосистеме уже не один ключ, а два - открытый и секретный. Алиса публикует свой открытый ключ - он доступен для всех. Боб (эти имена в криптографии используются с незапамятных времен) берет свое сообщение и шифрует его при помощи ключа Алисы (алгоритм шифрования известен). Однако ни Боб, ни кто-либо другой не может расшифровать это сообщение. Для этого нужно знать секретный ключ Алисы. Преимущество в том, что Алисе не нужно ни с кем делиться своим ключом. Только она одна должна иметь возможность расшифровать сообщение Боба, а чтобы зашифровать его, секретный ключ не нужен.

Криптография с открытым ключом уязвима по отношению к некоторым очевидным атакам. Вот алгоритм, который гарантированно взломает любую такую криптосистему: перебирать всевозможные сообщения, шифруя их при помощи открытого ключа, до тех пор пока результат не совпадет с шифром, который мы хотим разгадать. Это на первый взгляд может показаться обескураживающим, но на самом деле ничего страшного нет: никто никогда не переберет даже все возможные комбинации ста битов входа; что уж говорить о ключах длиной 512 или 1024 бит. Главное - чтобы у противника не было возможности сделать что-нибудь поумнее. Это и есть главная задача построения стойких криптосистем.

RSA и криптосистема Диффи-Хеллмана

Как строить криптосистемы с открытым ключом? Мы уже знаем, что Боб должен суметь зашифровать сообщение, но потом никто не должен иметь возможности расшифровать его - кроме Алисы, конечно. Говоря математическим языком, функция шифрования должна легко вычисляться, а вот вычисление обратной к ней должно быть «практически неосуществимым» [Объем вычислений должен расти быстрее полинома любой степени от длины ключа или аналогичного «параметра безопасности» системы]. Одной из первых криптосистем с открытым ключом была система RSA, названная так по именам создателей: Ривеста (Rivest), Шамира (Shamir) и Адлемана (Adleman) [Примечательно, что на самом деле приоритет принадлежит британскому математику Клиффорду Коксу (Clifford Cocks), который придумал эту криптосистему в 1973 году. Однако его работа оставалась неизвестной до 1997 года, так как относилась к разряду top secret (не только в Советском Союзе ученые работали на ВПК)]. Система, созданная в 1977 году, оказалась на редкость жизнеспособной и по сей день успешно применяется в огромном количестве приложений. Успех не в последнюю очередь объясняется простотой и глубиной математической идеи, лежащей в основе RSA. Поскольку для понимания сути эллиптических шифров лучше сначала «потренироваться на кошках», изложим эту идею и мы (это потребует некоторых знаний по элементарной теории чисел, см. врезку внизу справа). В ее основе - предположение о «практической неосуществимости» разложения на множители больших целых чисел.

С другой сложной для решения проблемой - дискретным логарифмированием - связана так называемая криптосистема Диффи-Хеллмана (Diffie-Hellman), которая появилась даже раньше, чем RSA, - в 1976 году [Кстати, сам Мартин Хеллман утверждает, что по справедливости ее нужно было бы называть криптосистемой Диффи-Хеллмана-Меркле; Ральф Меркле (Ralph Merkle) фактически был автором идеи криптографии с открытым ключом. К сожалению, криптосистема, которая все-таки была названа его именем - основанная на «задаче о рюкзаке» система Меркле-Хеллмана, - оказалась криптографически нестойкой и, как следствие, не приобрела популярности]. Ее краткое математическое описание см. во врезке на следующей странице.

Здесь стоит немного порассуждать о том, что значит «вычислительно трудно». В применении к только что перечисленным задачам математически это не значит ровным счетом ничего - никаких доказательных утверждений о вычислительной трудности разложения простых чисел или дискретного логарифмирования не существует. Однако много лет подряд криптографы всего мира пытались найти эффективные алгоритмы для решения этих задач - и не преуспели. Криптографы стараются использовать как можно больше задач, для которых еще не найдены эффективные алгоритмы [В этом смысле примечательно, что до сих пор неизвестны криптографические протоколы, основанные на NP-трудных задачах. Разумеется, такие протоколы были бы надежнее любых других - разложение чисел на простые множители или дискретный логарифм отлично укладываются в NP, и более того - дешифровка любой криптосистемы должна укладываться в NP, ведь при наличии секретного ключа, играющего роль подсказки, расшифровать сообщение должно быть возможно. Поиск связанных с NP-трудными задачами протоколов или обоснование (не путать с доказательством) того, что построить их невозможно, - одна из самых интересных задач современной криптографии, заслуживающая отдельного разговора]. В рамках этой концепции и были разработаны криптосистемы, основанные на эллиптических кривых.

Эллиптические кривые

Начнем сразу с определения. Эллиптические кривые - это кривые вида y^2 =x^3 +ax+b . [В полях размера 2m («полях характеристики 2»; к ним относится и привычное программистам поле из двух элементов) определения становятся чуть более сложными, а стандартные доказательства и рассуждения перестают работать; в алгебре и алгебраической геометрии случай характеристики 2 всегда стоит особняком и требует более изощренной техники, нежели все остальные. Поэтому в дальнейшем мы не будем его рассматривать]

Они занимают промежуточную нишу между коническими сечениями и кривыми более высоких порядков - про них известно не все, но многое. О том, что это серьезный объект для исследований, говорит хотя бы то, что именно теория эллиптических кривых привела Эндрю Уайлса к доказательству великой теоремы Ферма. Но нас будут интересовать куда менее эзотеричные материи.

Хотя примеры, изображенные на стр. 58, нарисованы на плоскости, то есть на множестве пар вещественных чисел (x, y), в криптографии все структуры, разумеется, должны быть дискретными. Поэтому решения уравнения ищутся над конечными полями. Чтобы конечное множество могло стать полем, его размер должен иметь вид p^m , где p - простое число. Конечное поле с простым количеством элементов (m=1) можно представлять как множество неотрицательных целых чисел, меньших p, в котором все алгебраические операции производятся «по модулю p» (то есть с переходом к остатку от деления результата на p). В криптографии используются конечные поля двух типов - с простым количеством элементов (m=1) и «поля характеристики два» (у которых 2 m элементов); мы ограничимся первым случаем. Кстати, термин «эллиптическая кривая» над конечным полем в изрядной степени теряет смысл - какая же это кривая, если это конечное множество точек? Но о терминах спорить - последнее дело, особенно в математике, где белая лошадь, в полном соответствии с Гунсунь Лун-цзы, может оказаться вовсе не лошадью.Ранее мы говорили, что сложность криптосистемы Диффи-Хеллмана связана с дискретным логарифмированием. Однако конструкция, аналогичная использованной в этой системе, может быть реализована над любым множеством, где есть похожая на умножение операция (например, сложение), подчиняющаяся своим естественным законам (такое множество называется в математике группой). Суть применения эллиптических кривых в криптографии сводится к тому, что группа чисел по простому модулю (как было в криптосистеме Диффи-Хеллмана) заменяется группой решений уравнения y^2 = x^3+ax+b. Осталось лишь указать, как складывать друг с другом решения такого уравнения.

На плоскости это делается так, как показано на рисунке выше. Чтобы сложить две точки на эллиптической кривой, нужно провести через них прямую. Она пересечет кривую в третьей точке. Эту третью точку мы будем считать суммой первых двух со знаком минус; чтобы получить собственно сумму, отразим полученную точку относительно оси 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

Секретный ключ Алисы в 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) за предоставленные изображения множеств Жюлиа.