Интернет магазин китайских планшетных компьютеров

Компьютеры - Эллиптическая криптография - Реализация шифрования

Конкретные реализации алгоритмов шифрования на эллиптической кривой описаны выше. Здесь мы рассмотрим общие принципы эллиптической криптографии.

Набор параметров

Для использования эллиптической криптографии все участники должны согласовать все параметры, определяющие эллиптическую кривую, т.е. набор параметров криптографического протокола. Эллиптическая кривая определяется константами a и b из уравнения. Абелева подгруппа точек является циклической и задается одной порождающей точкой G. При этом кофактор , где n — порядок точки G, должен быть небольшим.

Итак, для поля характеристики 2 набор параметров: , а для конечного поля , где p > 3, набор параметров: .

Существует несколько рекомендованных наборов параметров:

• NIST
• SECG

Для создания собственного набора параметров необходимо:

1. Выбрать набор параметров.
2. Найти эллиптическую кривую, удовлетворяющую этому набору параметров.

Для нахождения кривой для заданного набора параметров используются два метода:

• Выбрать случайную кривую, затем воспользоваться алгоритмом подсчета точек.
• Выбрать точки, после чего построить кривую по этим точкам, используя технику умножения.

Существует несколько классов криптографически «слабых» кривых, которых следует избегать:

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

Быстрая редукция

Деление по модулю p могут выполняться быстрее, если в качестве p выбрать простое число близкое к степени числа 2. В частности, в роли p может выступать простое число Мерсенна. Например, хорошим выбором являются p = 2 − 1 или p = 2 − 2 − 2 − 2 − 2 − 2 − 2 − 1. Национальный институт стандартов и технологий рекомендует использовать подобные простые числа в качестве p.

Ещё одним преимуществом кривых, рекомендованных NIST, является выбор значения a = − 3, что ускоряет операцию сложения в координатах Якоби.

Эллиптические кривые, рекомендованные NIST

NIST рекомендует 15 эллиптических кривых. В частности, FIPS 186-3 рекомендует 10 конечных полей. Некоторые из них:

• поля , где простое p имеет длину 192, 224, 256, 384 или 521 битов.
• поля , где m = 163, 233, 283, 409 или 571.

Причем для каждого конечного поля рекомендуется одна эллиптическая кривая. Эти конечные поля и эллиптические кривые выбраны из-за высокого уровня безопасности и эффективности программной реализации.

Размер ключа

Самым быстрым алгоритмам, решающим задачу дискретного логарифмирования на эллиптических кривых, таким как алгоритм Шенкса и ρ-метод Полларда, необходимо операций. Поэтому размер поля должен как минимум в два раза превосходить размер ключа. Например, для 128-битного ключа рекомендуется использовать эллиптическую кривую над полем , где p имеет длину 256 битов.

Самые сложные схемы на эллиптических кривых, публично взломанные к настоящему времени, содержали 112-битный ключ для конечного простого поля и 109-битный ключ для конечного поля характеристики 2. В июле 2009 года, кластер из более чем 200 Sony Playstation 3 за 3.5 месяца нашел 109-битный ключ. Ключ над полем характеристики 2 был найден в апреле 2004 года, с использованием 2600 компьютеров, в течение 17 месяцев.