Компьютерра, 2006 № 31 (651) - [41]

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

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

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

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

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

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

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

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

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

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

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

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

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