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

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

Как строить криптосистемы с открытым ключом? Мы уже знаем, что Боб должен суметь зашифровать сообщение, но потом никто не должен иметь возможности расшифровать его - кроме Алисы, конечно. Говоря математическим языком, функция шифрования должна легко вычисляться, а вот вычисление обратной к ней должно быть «практически неосуществимым» [Объем вычислений должен расти быстрее полинома любой степени от длины ключа или аналогичного «параметра безопасности» системы]. Одной из первых криптосистем с открытым ключом была система 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 всегда стоит особняком и требует более изощренной техники, нежели все остальные. Поэтому в дальнейшем мы не будем его рассматривать]