Журнал «Компьютерра» N 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 всегда стоит особняком и требует более изощренной техники, нежели все остальные. Поэтому в дальнейшем мы не будем его рассматривать]

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