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

P.S.

Это карма - как ни начну писать статью, вечно новая зеркалка выходит. Вот и сейчас - Canon EOS 400D уже практически анонсирован.

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

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 и Диффи-Хеллмана. Во всяком случае, суть «эллиптического шифрования» (будем иногда для краткости использовать этот не вполне корректный термин) я намереваюсь рассказать прямо сейчас, фактически с нуля.

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

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

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

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

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