Повышение производительности реализации схемы цифровой подписи за счет использования модуля специального вида

НАУЧНО-ТЕХНИЧЕСКАЯ КОНФЕРЕНЦИЯ
"БЕЗОПАСНОСТЬ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ"
Повышение производительности реализации схемы цифровой подписи за счет использования модуля специального вида

Спиридонов А.В. E-mail: spx@mail15.com
Пензенский государственный университе

1. Введение

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

В Российской Федерации до недавнего времени действовал стандарт на процедуры ЭЦП ГОСТ Р 34.10-94, использовавший (как и большинство иностранных алгоритмов) криптографическую технику, основанную на арифметике мультипликативной группы простого поля. Однако с 1 июля 2002 г. вступил в действие ГОСТ Р 34.10-2001, который в отличие от прежнего предлагает использовать криптографическую схему, основанную (что также является мировой тенденцией) на арифметике группы точек эллиптической кривой. Переход к эллиптической криптографии обусловлен теми преимуществами, которые дает её использование – меньшая длина ключа при заданной стойкости. Например, в построенных на основе эллиптических кривых криптосистемах бинарной размерности в диапазоне от 150 до 350 обеспечивается уровень криптографической стойкости, который требует использования в известных криптосистемах бинарной размерности от 600 до 1400 и более [1]. Кроме этого, несмотря на то, что операции в эллиптической криптографии сложнее (вычислительно), за счет меньшей длины операндов и выбора наиболее эффективных арифметических алгоритмов можно даже получить выигрыш в производительности по сравнению с процедурами ЭЦП на основе арифметики мультипликативной группы простого поля (при сохранении заданной криптографической стойкости).

В данной работе рассматриваются методы вычисления модулярной редукции (вычисление остатка от деления целых чисел на целое число – модуль) – одной из базовых элементарных криптографических операций. Эта довольно старая тема вызвала интерес в новом контексте по следующей причине: новый стандарт на ЭЦП открывает путь, ранее закрытый, – применение в качестве модуля чисел специального вида, вычисление редукции по которым можно реализовать весьма эффективно. ГОСТ 34.10-94 не позволял использовать в качестве модуля такие числа в силу четкого определения процедуры генерации используемых простых чисел. Новый ГОСТ 34.10-2001 не накладывает подобных ограничений. Особо следует отметить, что к настоящему времени неизвестно о каких-либо негативных последствиях использования такого числа в качестве параметра схемы ЭЦП (а именно как модуля кривой) по ГОСТ 34.10-2001.

Таким образом, данная работа посвящена исследованию чисел специального вида и соответствующих им алгоритмов вычисления редукции, позволяющих повысить производительность вычислений процессов формирования/проверки ЭЦП на основе криптографии эллиптических кривых. В работе проводится сравнение данных алгоритмов с универсальными алгоритмами (не зависящими от вида модуля), а также производится оценка вклада перехода на модули специального вида в повышение общей производительности вычисления алгоритмов ГОСТ 34.10-2001.

2. <![endif]> Методы вычисления модулярной редукции

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

В данной работе рассматриваются пять методов вычисления модулярной редукции (далее просто редукция):

- классический алгоритм деления длинных чисел;

- редукция Барретта;

- редукция Монтгомери;

- редукция по модулю чисел Кронделла;

- редукция по модулю обобщенных чисел Мерсенна.

Первые три являются универсальными, т.е. не зависят от вида модуля, два последних – требуют модуля специального вида. Как уже упоминалось выше, в действовавшем раннее ГОСТ Р 34.10-94 зафиксирована процедура генерации простого числа p, которая не позволяла получать числа специального вида, и соответственно, применение специальных методов было невозможно. ГОСТ Р 34.10-2001 ничего подобного не содержит, поэтому исследование методов вычисления редукции по модулю специального вида становится актуальным в контексте поиска решений по повышению производительности реализаций алгоритмов ГОСТ Р 34.10-2001.

3. Дополнительная терминология

Будем называть числа, двоичное представление которых имеет больше разрядов, чем штатно используется в ЭВМ для представления целого числа (обычно это 16, 32 или 64 бита), длинными числами (числами повышенной разрядности). Например, число длиной 256 бит определённо длинное число.

Обозначим через m длину машинного слова, а в качестве основания системы счисления примем b = 2m. Как известно, любое неотрицательное целое число X < bn можно разложить в сумму степеней числа b:

X = X0b0 + X1b1 + … + Xn – 2bn – 2 + Xn – 1bn – 1

где Xi – некоторые неотрицательные целые числа меньшие b. Число X хранится в памяти компьютера как массив m-битовых слов с элементами X[i] = Xi. Будем называть числа Xi цифрами числа X, а число X – n‑значным длинным числом.

Можно отождествить поле GF(p) с множеством целых неотрицательных чисел меньших p. Тогда элементы поля GF(p) можно представить как неотрицательные длинные целые числа меньшие p. Если обозначить через n количество цифр числа p, то элементы GF(p) в памяти компьютера представляются как массивы из n элементов-цифр.

4. Классический алгоритм деления длинных чисел

Для вычисления остатка можно тривиально воспользоваться классическим алгоритмом деления «лесенкой». Он широко известен, достаточно точно формализован (см., например, алгоритм 14.20 в [6]) и является одним из самых медленных вариантов вычисления редукции. Не будем на нём подробно останавливаться, отметим только, что при вычислении редукции числа длины 2n цифр по модулю числа длины n цифр с помощью деления требуется в среднем выполнение порядка n элементарных делений и n(n + 2,5) умножений [3].

5. Редукция Барретта

Барретт предложил алгоритм, позволяющий вычислить r = x mod p для данных x и p длиной k бит (частное в ходе вычислений не определяется). При этом алгоритм требует предварительного вычисления числа μ = |_ b2k / p _|, что позволяет значительно упростить вычисления в дальнейшем. В частности в алгоритме отсутствуют «тяжелые» операции деления – остаются только деления на степень основания системы счисления, которые на практике реализуются «легкой» операцией сдвига. При однократном вычислении редукции по вычислительной сложности алгоритм Барретта близок к делению, однако при многократном вычислении редукции по одному и тому же модулю, что и наблюдается при вычислениях в группе, он оказывается гораздо эффективнее (ведь μ достаточно вычислить один раз!). В [3] показывается, что при вычислении редукции числа длины 2 n цифр по модулю числа длины n цифр с помощью алгоритма Барретта требуется выполнить n(n + 4) элементарных операций умножения. Сам алгоритм достаточно прост и приведен, например, в [6].

6. Редукция Монтгомери

Монтгомери [7] предложил пойти другим путём. Пусть p ‑ натуральное число, T и R ‑ целые числа, такие что

0 £ T < pR,

p < R,

НОД (p, R) = 1.

(НОД – наибольший общий делитель.)

Число TR –1 mod p называется редукцией Монтгомери числа T по модулю p относительно R. При подходящем выборе R редукцию Монтгомери можно вычислить весьма эффективно.

Пусть x и y – целые числа: 0 £ x, y < p. Пусть x’ = xR mod p, y’ = yR mod p. Тогда редукцией Монтгомери произведения x’y’ является x’y’R-1 mod p = xyR mod p. Именно это свойство позволяет использовать редукцию Монтгомери для эффективного вычисления модулярной экспоненты (что весьма кстати в процедурах ЭЦП).

Для вычисления значения редукции Монтгомери используется следующий факт.

Пусть p' = – p –1 mod R, U = Tp' mod R. Тогда число (T+Up)/R целое и

(T+Up)/R º TR –1 (mod p).

Если представить число p в общем случае в b-ичной системе счисления, то удобно использовать R = bn. Условие p < R очевидно выполняется. Что же касается требования НОД(p,R) = 1, то оно равносильно НОД(p,b) = 1. Если b – степень 2, то последнее условие равносильно тому, что p – нечетное число. Для простых p, используемых в процедурах цифровой подписи, это верно. В [7] (а также в [3] и [6]) приводится алгоритм для вычисления редукции Монтгомери, причем в [3] показано, что он требует выполнения n(n + 1) элементарных операций умножения и некоторого количества операций сложения.

Как видно, скорости вычисления редукции Монтгомери и Барретта довольно близки. И всё же редукция Монтгомери требует слегка меньшего количества операций и легче поддается распараллеливанию, поэтому она, как правило, и используется в реализациях ГОСТ Р 34.10‑94.

7. Редукция по модулю обобщенных чисел Мерсенна
Вышеприведённые алгоритмы являлись универсальными, т.е. позволяли вычислить редукцию по произвольному простому модулю. Однако можно выбрать модуль, для которого вычисление редукции выполняется особенно эффективно. Наиболее известным из таких чисел является число Мерсенна – число, в общем случае имеющее вид p = 2 k – 1. Для вычисления редукции 2 k‑битного числа A по такому модулю следует представить его в виде

A = A1 + 2kA2,

где 0 £ A1, A2 < 2k.

Тогда

A º A1 + A2 (mod p).

Как видно, редукция по модулю числа Мерсенна может быть выполнена без деления или умножения, а только с помощью сложения.

На практике было бы удобно, чтобы k было кратно длине машинного слова используемой ЭВМ (степень двойки), но в этом случае k – составное число и p = 2 k – 1 не простое. Следовательно, автоматическое использование упрощения редукции, предоставляемого числами Мерсенна, не применимо в контексте нашей задачи.

Однако можно расширить понятие чисел Мерсенна одним из следующих способов:

- числа Кронделла вида p = bn ± c, где 0 < c < b ([4]), длину b можно выбрать равной длине машинного слова;

- обобщенные числа Мерсенна вида p = bn – cn – 1bn – 1 – … – c0, где лишь малое число ci не равны 0 ([8]).

Пусть модуль p = bn – cn – 1bn – 1 – … – c0, с большим количеством нулевых ci. В [8] разработана техника вычисления редукции по таким модулям. При этом применяются регистры сдвига с линейной обратной связью.

В качестве примера, подходящего для случая ГОСТ Р 34.10‑2001, рассмотрим простое число, предложенное в новой редакции американского стандарта цифровой подписи ECDSA [5] (там же указаны параметры кривой, построенной с его использованием). Это

p = 2256 – 2224 + 2192 + 296 – 1.

В [5] приводятся формулы, позволяющие вычислить редукцию по этому модулю, выполнив в общей сложности всего 10 операций сложения, вычитания и сдвига 256-битных чисел с последующей редукцией по модулю p числа, которое превышает p на 0¸6 разрядов. Таким образом, в данном случае не требуется использовать ни операций деления, ни операций умножения. Все вычисления выполняются с помощью аддитивных операций. Соответственно, скорость такой редукции существенно выше всех ранее рассмотренных методов. Это же верно для многих обобщенных чисел Мерсенна с небольшой плотностью (см. [8]).

8. Редукция по модулю чисел Кронделла

Числами Кронделла называют простые числа вида p = bn ± c, где 0 < c < b. Редукция по модулю таких чисел также может быть реализована более эффективно, чем для произвольных простых чисел.

Пусть p = bn – c, где 0 < c < b.Тогда

bn º c (mod p).

Значит для числа A = A1 + bnA2, где 0 £ A1, A2 < bn,

A º A1 + сA2 (mod p).

Следовательно, для вычисления редукции 2n-значного числа по модулю n-значного числа Кронделла необходимо выполнить умножение n‑значного числа на цифру, сложение (n + 1)‑значного и n‑значного чисел, и после этого вычислить редукцию (n + 1)‑значного числа по n‑значному модулю. Если на последнем шаге применить классический алгоритм деления, то вся процедура потребует выполнения 2 n элементарных операций умножения и 2 n + 2 операций сложения.

Если p = 2 nm – 1 + c, где 0 < c < b/2. Тогда

bn º – 2c (mod p).

Значит для числа A = A1 + bnA2, где 0 £ A1, A2 < bn,

A º A1 – 2с A2 (mod p).

Как видно, для вычисления редукции 2n‑значного числа по модулю такого n‑значного числа Кронделла необходимо выполнить умножение n-значного числа на цифру, вычитание (n + 1)-значного из n-значного числа, и после этого вычислить редукцию (n + 1)-значного числа по n-значному модулю. Опять вся процедура потребует выполнения порядка 2n элементарных операций умножения и 2n + 2 операций сложения.

9. Сравнение методов

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

В ходе выполнения работы была написана библиотека функций, реализующих описанные методы. Также была написана библиотека функций, реализующих процессы формирования и проверки ЭЦП по ГОСТ Р 34.10‑2001, позволяющая использовать специальные методы вычисления редукции в случае применения в качестве модуля кривой соответствующего числа. В качестве языка программирования был выбран С, легко переносимый между различными платформами.

10. Сравнение методов вычисления редукции

В ходе тестирования проводилось вычисление редукции 512-битного числа по 256‑битному модулю. Так как методы вычисления редукции по числам Мерсенна и Кронделла зависят от выбора модуля, то было проведено три теста, в каждом из которых один из методов сравнивался с делением и универсальным методом Баррета по скорости вычисления (метод Монтгомери не рассматривался, т. к. его результат не есть остаток в чистом виде и требует дополнительной обработки, а его производительность сравнима с производительностью метода Барретта):

Тест №1 Модуль: p = 2256 – 2224 + 2192 + 296 – 1 (обобщенное число Мерсенна P-256 из [5]). Специализированный метод: вычисление редукции по обобщённому числу Мерсенна.

Тест №2 Модуль: p = 2255 + 1073 (число Кронделла – тестовый модуль из ГОСТ Р 34.10-2001). Специализированный метод: вычисление редукции для числа Кронделла вида p = 2 nm – 1 + c.

Тест №3 Модуль: p = 2256 – 3911 (число Кронделла). Специализированный метод: вычисление редукции для числа Кронделла вида p = bn – c.

Результаты измерения приведены в таблице 1. Для упрощения сравнения представлены не абсолютные значения времен выполнения, а отношения ко времени выполнения самого медленного метода – деления.

Таблица 1

Результаты измерений времени вычисления редукции различными методами

№ теста | Метод вычисления редукции | Время выполнения (в % к делению)
1 | Деление | 100.00
 | Редукция Барретта | 37.54
 | Редукция Мерсенна | 5.75
2 | Деление | 100.00
 | Редукция Барретта | 37.78
 | Редукция Кронделла | 17.77
3 | Деление | 100.00
 | Редукция Барретта | 37.45
 | Редукция Кронделла | 12.45

Видно, что применение специальных методов (там, где они применимы) позволяет получить ощутимый выигрыш в скорости вычисления модулярной редукции. Наибольший выигрыш даёт применение в качестве модуля обобщенного числа Мерсенна и соответствующего ему метода при вычислении редукции – почти в 17.5 (!) раз по отношению к тривиальному делению и в 6.5 раз по отношению к достаточно быстрому методу Барретта.

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

11. Сравнение производительности процессов формирования и проверки ЭЦП при использовании различных методов вычисления редукции

Проводились следующие тесты (в каждом тесте 1000 раз формировалась и проверялась цифровая подпись по алгоритмам ГОСТ Р 34.10-2001):

Тест №4 Исходные данные: кривая из контрольного примера ГОСТ Р 34.10-2001 (модуль p = 2255 + 1073 – число Кронделла). Используемые методы вычисления редукции: деление, редукция Барретта, редукция по модулю числа Кронделла вида p = 2 nm – 1 + c.

Тест №5 Исходные данные: кривая P–256 из таблиц [5] (модуль – обобщенное число Мерсенна). Используемые методы вычисления редукции: деление, редукция Барретта, редукция по модулю обобщенного числа Мерсенна.

Результаты измерений представлены в таблице 2.

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

Таблица 2

Результаты измерений времени вычисления процессов формирования и проверки цифровой подписи по ГОСТ Р 34.10-2001 при использовании различных методов редукции

№ теста | Метод вычисления редукции | Время формирования подписи (в % к делению) | Время проверки подписи (в % к делению)
4 | Деление | 100.00 | 100.00
 | Редукция Барретта | 52.56 | 51.05
 | Редукция Кронделла | 37.09 | 35.52
5 | Деление | 100.00 | 100.00
 | Редукция Барретта | 52.53 | 51.16
 | Редукция Мерсенна | 26.50 | 25.05

12. Вывод

По результатам работы следует признать, что одной из мер по повышению производительности реализаций процессов ЭЦП, основанных на криптографии эллиптических кривых (и ГОСТ Р 34.10-2001 в частности), может служить применение в качестве модулей кривых чисел специального вида и соответствующих им методов редукции.

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

ЛИТЕРАТУРА

1 Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А, Алгоритмические основы эллиптической криптографии – М.: 2000 г.

2 Домашев А.В., Грунтович М.М., Попов В.О., Правиков Д.И., Щербаков А.Ю. Программирование алгоритмов защиты информации – М.: «Нолидж», 2002.

3 A. Bosselaers, R. Govaerts, J. Vandewalle. Comparison of three modular reduction functions. Crypto '93, LNCS 773, 1994, pp. 175‑186.

4 R.E. Crandall. Method and apparatus for public key exchange in a cryptographic system (Oct. 27, 1992), U.S. Patent #5,159,632.

5 NIST, Digital Signature Standard, FIPS Publication 186‑2, February 2000

6 A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography. – CRC Press, 1996.

7 Peter L. Montgomery. Modular multiplication without trial division. Mathematics of Computation, v.44, n.170, 1985, pp. 519‑521.

8 J. Solinas. Generalized Mersenne numbers. Technical Report CORR 99‑39, Dept.of C&O, University of Waterloo, 1999.

Получено 12.10.2003. Доклад опубликован в Internet 18.10.2003.