Реферат: Реализация алгоритмов формирования и проверки подлинности электронной цифровой подписи

Реализация алгоритмов формирования и проверки подлинности электронной цифровой подписи


О.Х. Расулов (ГУП «UNICON.UZ»)


В статье предложены методы реализации арифметических вычислений в алгоритмах формирования и проверки подлинности электронной цифровой подписи стандарта O’z DST 1092:2009.

Мақолада O’z DST 1092:2009 стандартининг электрон рақамли имзони шакллантириш ва уни хақиқийлигини текшириш алгоритмларида қўлланилган арифметик амалларини бажариш усуллари таклиф қилинган.

In this article methods of implementation of arithmetic calculations in algorithms of digital signature generation and verification of O’z DST 1092:2009 standard are supposed.


^ Актуальность вопроса:

В основу национального стандарта формирования и проверки подлинности электронной цифровой подписи (ЭЦП) [4, алгоритмы 1.1 и 1.2] положено выполнение модульных арфметических операций с большими числами, что при аппаратной реализации представляет повышенную трудоемкость. В предыдущих статьях [1], [2] предложены методы повышения эффективности выполнения таких операций на основе модульного умножения Монтгомери [3]. В результате исследований выработаны модифицированные алгоритмы Монтгомери, позволяющие такие операции как умножение и возведение в степень в алгебре с параметром перенести на аппаратную платформу. В связи с тем, что алгоритмы формирования и проверки подлинности ЭЦП состоят из последовательности различных модульных операций, имеется необходимость выработать порядок применения предложенных методов при вычислениях ЭЦП. При этом, так как аппаратная реализация предполагает использование программируемой логической интегральной схемы (ПЛИС) с ограниченной логической емкостью и фиксированной логической структурой, необходимо по возможности сократить количество разнотипных операций.

^ Постановка задачи:

С целью обеспечения возможности аппаратной реализации алгоритмов формирования и проверки подлинности ЭЦП на базе ПЛИС необходимо:

- разработать эффективный метод вычисления мультипликативно обратных чисел по модулю без использования операций деления;

- определить порядок применения методов модульного умножения и возведения в степень, разработанных в [1] и [2];

- максимально унифицировать перечень выполняемых операций.

^ Решение задачи:

Рассмотрим алгоритм формирования ЭЦП [4, алгоритм 1.1] с точки зрения оптимизации выполнения отдельных его функций. Предположим, что заданы параметры ЭЦП p, q, R, R1, g, x, u, μ. Тогда, алгоритм формирования ЭЦП под сообщением M состоит из следующей последовательности функций (упрощенно):

Шаг 1. Вычислить хеш-функцию сообщения m = H(М);

Шаг 2. Вычислять k = H(m+(1+mR)x);

Шаг 3. Вычислить Т ≡ g\-k (mod p);

Шаг 4. Вычислить r ≡ m + (1 + mR)T (mod p);

Шаг 5. Вычислить s1 ≡ k – rx (mod q);

Шаг 6. Вычислить s ≡ s1 u -1 (mod q);

Если μ = 0, выдать ЭЦП в виде пары чисел (r, s). Конец алгоритма.

Шаг 7. Вычислить r1 ≡ R1 + (1 + RR1)r (mod q);

Шаг 8. Вычислить x1 ≡ (k – suR1)r1-1 (mod q);

Шаг 9. Вычислить y1 ≡ (gR1-1)\x1 (mod p);

Выдать ЭЦП в виде тройки чисел (r, s, y1). Конец алгоритма.


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

На шаге 3 вычисляется k-кратная мультипликативно обратная величина g по модулю p с параметром R:


T ≡ g\-k (mod p) ≡ -g (1 + gR)-k (mod p) (1)

Классическими способами нахождения обратных чисел по модулю являются расширенный алгоритм Евклида и Китайская теорема об остатках. Эти способы предполагают применение операции деления на модуль, что при использовании больших чисел резко увеличивает трудоемкость вычислений. С целью снижения общей трудоемкости и обеспечения возможности аппаратной реализации алгоритма ЭЦП предлагается обратные величины вычислять с использованием операции модульного возведения в степень.

В соответствии с малой теоремой Ферма, если p является простым числом, справедливо сравнение


A(p-1) ≡ 1 (mod p) (2)


Мультипликативно обратным числом является число такое, что справедливо сравнение


A∙A-1 ≡ 1 (mod p) (3)


Из сравнений (2) и (3) следует, что для вычисления мультипликативно обратного числа А по модулю p достаточно вычислить


A-1 ≡ A(p-1)∙A-1 (mod p) ≡ A(p-2)(mod p) (4)


Таким образом, при условии что p является простым числом, для нахождения обратных чисел нет необходимости применять алгоритмы с трудоемкой операцией деления и выражение (1) можно вычислить как


T ≡ g\-k (mod p) ≡ -g (1 + gR)-k (mod p) ≡ -g(1 + gR)(p-k-2) (mod p) (5)


Очевидно, что сравнение (4) можно использовать на шагах 6, 8 и 9 алгоритма формирования ЭЦП. Для рассмотрения результирующей последовательности действий при формировании ЭЦП, перечислим обозначения операций из [1] и [2]:


MonPro(A, B, N) – операция модульного умножения, вычисляющая


S = MonPro(A, B, N) = A B r -1 (mod N)


MonExp(A, B, N) – операция модульного возведения в степень, вычисляющая


S = MonExp(A, B, N) = A B (mod N)


^ MonProX(A, B, C, N) – операция модульного умножения со сложением, вычисляющая


S = MonProX(A, B, С, N) = (A B + C) r -1 (mod N)


MonExpX(A, B, N) – операция модульного возведения в степень с параметром, вычисляющая

S = MonExpX(A, B, N) = A \B (mod N)


Дополнительно введем обозначение для модульного умножения с параметром, алгоритм которого описан в [2].


MonProR(A, B, N) – операция модульного умножения с параметром, вычисляющая


S = MonProR(A, B, N) = A ® B (mod N)


Результирующая последовательность действий для алгоритма формирования ЭЦП [4, алгоритм 1.1] имеет следующий вид (упрощенно, без приведения чисел к виду Монтгомери и обратно):

Шаги 1 и 2. Вычислить m и k используя хеш-функции (в данной статье не рассматривается);

Шаг 3. Вычислить

T = MonProX(g, R, 1, p);

T = MonExp(T, p-k-2, p);

T = MonPro(p-g, T, p)

Шаг 4. Вычислить

r = MonProR(m, T, p)

Шаг 5. Вычислить

s1 = k – MonProR(r, x, q) (mod q)

Шаг 6. Вычислить

s = MonExp(u, q-2, q);

s = MonPro(s1, s, q)

Если μ = 0, выдать ЭЦП в виде пары чисел (r, s). Конец алгоритма.

Шаг 7. Вычислить

r1 = MonProR(R1 , r, q)

Шаг 8. Вычислить

x1 = MonPro(s, u, q);

x1 = MonPro(x1, R1, q);

r1 = MonExp(r1, q-2, q);

x1 = MonPro(k-x1, r1, q)

Шаг 9. Вычислить

y1 = MonExp(R1, p-2, p);

y1 = MonPro(g, y1, p);

y1 = MonExpX(y1, x1, p) с параметром RR1

Выдать ЭЦП в виде тройки чисел (r, s, y1). Конец алгоритма.


Алгоритм проверки подлинности ЭЦП на приемной стороне [4, алгоритм 1.2] также может быть выполнен с использованием перечисленных операций:

Шаги 1 и 2. Вычисление m с использованием хеш-функции и проверка размеров полученных параметров ЭЦП – в данной статье не рассматриваются.

Шаг 3. Вычислить

z0 = MonExpX(z, s, p)

Шаг 4. Вычислить

r’ = r (mod q)

Шаг 5. Вычислить

y2 = MonExpX(y, r’, p)

Шаг 6. Вычислить

z1 = MonProR(z0, y2, p)

Шаг 7. Вычислить

y3 = MonProR(z1, r, p)

Шаг 8. Если m ≠ y3 выдать «подпись не подлинна». Конец алгоритма.

Иначе если μ = 0, выдать «подпись подлинна». Конец алгоритма.

Шаг 9. Вычислить

g3 = MonExp(R1, p-2, p);

g3 = MonPro(g3, z1, p)

Шаг 10. Вычислить

s1 = MonPro(s, R1, q)

Шаг 11. Вычислить

r1 = MonProR(R1, r’, q)

Шаг 12. Вычислить

z2 = MonExp(R1, p-2, p)

z2 = MonPro(z, z2, p)

Шаг 13. Принять y4 = y1

Шаг 14. Вычислить

z3 = MonExpX(z2, s1, p) с параметром RR1

Шаг 15. Вычислить

y5 = MonExpX(y4, r1, p) с параметром RR1

Шаг 16. Вычислить

g4 = MonProR(z3, y5, p) с параметром RR1

Шаг 17. Если g3 = g4, выдать «подпись подлинна», иначе выдать подпись не подлинна». Конец алгоритма.

Выводы:

Алгоритмы 1.1 и 1.2 стандарта [4] за исключением некоторых операций, можно реализовать с использованием ограниченного количества разнотипных операций. Это означает, что в ПЛИС достаточно реализовать фиксированный набор арифметико-логических модулей и по мере выполнения алгоритмов по шагам использовать одни и те же модули, загружая в них соответствующие входные данные. Такой подход к реализации позволит эффективно использовать недорогие ПЛИС с относительно небольшой логической емкостью и малыми габаритами.

Литература

1. О. Х. Расулов. Исследование и анализ арифметических операций современной криптографии и способы их аппаратной реализации. «ИНФОКОММУНИКАЦИИ: СЕТИ-ТЕХНОЛОГИИ-РЕШЕНИЯ» №1 (17) 2011.

2. О. Х. Расулов. Повышение эффективности выполнения арифметических операций в алгебре с параметром. «ИНФОКОММУНИКАЦИИ: СЕТИ-ТЕХНОЛОГИИ-РЕШЕНИЯ» №2 (18) 2011.

3. P.L. Montgomery. Modular Multiplication without Trial Division. Mathematics of Computation, Vol. 44, No. 170, 1985.

4. O’z DSt 1092: 2009 Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.