Журнал «Компьютерра» № 31 от 29 августа 2006 года
Шрифт:
Криптография с открытым ключом разрывает этот круг. В криптосистеме уже не один ключ, а два — открытый и секретный. Алиса публикует свой открытый ключ — он доступен для всех. Боб (эти имена в криптографии используются с незапамятных времен) берет свое сообщение и шифрует его при помощи ключа Алисы (алгоритм шифрования известен). Однако ни Боб, ни кто-либо другой не может расшифровать это сообщение. Для этого нужно знать секретный ключ Алисы. Преимущество в том, что Алисе не нужно ни с кем делиться своим ключом. Только она одна должна иметь возможность расшифровать сообщение Боба, а чтобы зашифровать его, секретный ключ не нужен.
Криптография с открытым ключом уязвима по отношению к некоторым очевидным атакам. Вот алгоритм, который гарантированно взломает любую такую криптосистему: перебирать всевозможные сообщения, шифруя их при помощи открытого ключа, до тех пор пока результат не совпадет с шифром, который мы хотим разгадать. Это на первый взгляд может показаться обескураживающим,
Как строить криптосистемы с открытым ключом? Мы уже знаем, что Боб должен суметь зашифровать сообщение, но потом никто не должен иметь возможности расшифровать его — кроме Алисы, конечно. Говоря математическим языком, функция шифрования должна легко вычисляться, а вот вычисление обратной к ней должно быть «практически неосуществимым» [Объем вычислений должен расти быстрее полинома любой степени от длины ключа или аналогичного «параметра безопасности» системы]. Одной из первых криптосистем с открытым ключом была система 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 — это два простых числа p и q. Чем больше эти числа, тем шифр надежнее. Именно поэтому многие организации готовы платить деньги за большие простые числа; давно существуют онлайн-проекты распределенных вычислений по поиску простых чисел. Алиса публикует произведение этих чисел N=pq. Ключевое предположение, на котором основана RSA, — то, что большое число трудно разложить на множители. То есть N можно распространять, а p и q все равно никто не узнает.