Вычислительные усилия, необходимые для криптоанализа при использовании эллиптических кривых и rsa

Операции	Размер ключа	MIPS-годы
Логарифмирование на эллиптической кривой с помощью ρ-метода Полларда (ECC)	150	3,8 · 1010
	205	7,1 · 1018
	234	1,6 · 1028

Окончание табл. 8

Операции	Размер ключа	MIPS-годы
Разложение на множители в целых числах с помощью метода решета в поле чисел общего вида (RSA)	512	3 · 104
	768	3 · 102
	1024	3 · 1011
	1280	1 · 1014
	1536	3 · 1016
	2048	3 · 1020

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

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

§ 3. Алгоритм цифровой подписи, основанный на группе точек эллиптической кривой

Электронная цифровая подпись (ЭЦП) для сообщения является числом, зависящим от самого сообщения, и от секретного, известного только подписывающему субъекту ключа. При этом подпись должна быть легко проверяемой без знания секретного ключа. При возникновении спорной ситуации, связанной с отказом подписавшего от факта подписи им некоторого сообщения либо с попыткой подделки подписи, третья независимая сторона (арбитр) должна иметь возможность разрешить спор.

Применение ЭЦП позволяет решить следующие задачи:

– осуществить аутентификацию источника сообщения;

– установить целостность сообщения;

– обеспечить невозможность отказа от факта подписи конкретного сообщения.

В настоящее время используются различные схемы ЭЦП. Их можно разделить на три класса:

– схемы на основе симметричных систем шифрования;

– схемы на основе систем шифрования с открытыми ключами;

– схемы со специально разработанными алгоритмами вычисления и проверки подписи.

Замечание. Распространенной практикой является формирование ЭЦП не для самого сообщения, а для его хеш-образа при соответствующем выборе хеш-функции.

В качестве международного стандарта принят американский алгоритм цифровой подписи на эллиптических кривых (ECDSA). В этом стандарте используются эллиптические кривые над полем характеристики 2. Однако криптографически стойких кривых над полем такой характеристики сравнительно мало. Поэтому мы рассмотрим ЭЦП на эллиптических кривых, заданных над полем большей характеристики.

Замечание. В России официально принят стандарт ЭЦП на эллиптических кривых над полем большей характеристики – ГОСТ 34.10–2001 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи» (см. прил. 1).

Выбор кривой и точки на ней подразумевает решение ряда вспомогательных задач. Прежде всего это подсчет количества точек на кривой. Если N – количество точек на 𝐸( , то должны выполняться следующие условия:

(31)

(32)

Таким образом, чтобы отсеять лишние числа из интервала , можно проверять условие (32) для разных точек G. Единственное оставшееся число и будет искомым порядком кривой.

Замечание. Существует несколько методов оптимизации нахождения порядка кривой, например, метод больших-малых шагов, метод Шуфа. Познакомиться с ними можно по книгам, приведенным в библиографическом списке^*.

Для получения криптографически стойкой системы ЭЦП должны выполняться следующие условия:

1. порядок точки G, используемой в системе ЭЦП, должен быть простым числом n,

2. и , где N – порядок кривой;

3. для всех где C настолько велико, что вычислить дискретный логарифм в за приемлемое время невозможно.

Замечание. В настоящее время значение C = 20 считается достаточным.

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

После того как порядок N кривой определен, требуется найти большой простой делитель n порядка кривой. Такого делителя может не существовать, и тогда потребуется повторять процедуру выбора кривой до тех пор, пока не будут выполнены все требуемые условия. Поиск числа n может потребовать как разложения на множители числа N, так и доказательства простоты числа n.

Точку G можно выбрать следующим образом. Найдем случайную точку 𝐺′ ∈ 𝐸( ) и вычислим . Если , то требуемая точка найдена, если же , то выбираем другую точку .

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

Генерация подписи.

Входные данные: сообщение m, исходные параметры и ключ подписи. Выходные данные: подпись .

Алгоритм:

1. Выбрать случайное число k в интервале .

2. Вычислить .

3. Вычислить .

4. Если , то вернуться к шагу 1.

5. Вычислить .

6. Вычислить .

7. Вычислить .

8. Если , то вернуться к шагу 1.

9. Вывести пару – подпись к m.

Замечания. 1) при результат вычисления s не зависит от секретного ключа d; 2) при необходимого для проверки подписи числа не существует; 3) в качестве хеш-функции h на шаге 6 в стандартах ANSIX9F1 и IEEEP1363 используется SHA-1, в российском стандарте ГОСТ Р 34.10–2001 – хеширование по стандарту ГОСТ Р 34.11–94.

Проверка подписи. Входные данные: сообщение m, исходные параметры, ключ проверки подписи и подпись к m. Выходные данные: заключение о подлинности или фальсификации подписи.

Алгоритм:

1. Если хотя бы одно из условий , нарушается, то подпись фальшивая и работа алгоритма закончена.

2. Вычислить .

3. Вычислить .

4. Вычислить .

5. Вычислить .

6. Вычислить .

7. Если , то подпись действительная, иначе подпись фальшивая.

Доказательство корректности алгоритма генерации и алгоритма проверки подписи очень простое и предоставляется в качестве упражнения.

Пример 20. Построение системы цифровой подписи. Используем построенную ранее эллиптическую кривую над конечным полем GF(2¹⁸⁴), ее порядок равен

24519928653854221733733552425551231120507846775650841870

и в группе точек этой эллиптической кривой существует циклическая подгруппа простого порядка

2098301128811779764490989552582298324221657814667.

Нетрудно убедиться, что число u удовлетворяет условию Менезеса–Окамото–Вэнстона и поэтому эту кривую можно использовать в криптографических алгоритмах. Легко проверить, что точка

𝐺 = (8718530218176903146207227181110236173128144216155151198161,

2618723313241163311561151819363208871622011861361892123221245)

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

𝑑 = 639976254049691330438880136087803025472585373106

и вычислить открытый ключ

Q = 𝑑P = (2012355114217111017775249223891566918510915221922014271635084,

67182421615615694798118212159190631191991922031851725515671).

Система цифровой подписи построена. Заметим, что стойкость этой системы эквивалентна стойкости цифровой подписи в простом поле с ключом, размер которого равен 1 200 битам.

* * *

Для дальнейшего изучения затронутых вопросов можно рекомендовать работы [11; 12; 17].