Быстрая цифровая подпись

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

Проблемы ЭЦП

С момента изобретения ЭЦП в 1976 году, она является самой многообещающей областью исследований в криптосистемах с открытым ключом. Одним из стандартных математических решений для построения криптографических алгоритмов является задача дискретного логарифмирования, на основе которой были разработаны многие алгоритмы получения ЭЦП. Главным недостатком традиционных алгоритмов ЭЦП, таких как схема Эль-Гамаля и RSA, является их вычислительная сложность. Вычисление экспонент в модульной арифметике требует наибольших вычислительных затрат в схемах криптосистем с открытым ключом. В настоящее время ведется большое количество работ по улучшению производительности криптографических алгоритмов путем сокращения количества вычислений экспонент. Наиболее короткой известной схемой ЭЦП является BLS (Boneh – Lynn - Shacham), использующая эллиптические кривые, но она ограничена группами, в которых есть функция составления пары. Разработчики алгоритмов работают как над улучшением традиционных схем с дискретным логарифмированием, используя параллельные вычисления экспонент, так и изучают принципиально другие подходы, основанные, например, на теории графов вместо модульной арифметики.

Некоторые алгоритмы быстрой цифровой подписи

Схема быстрой ЭЦП, основанная на алгоритме Диффи-Хеллмана

Пусть $\ G$ – абелева группа, $\ G_{g,q}$ – её циклическая подгруппа с генератором $\ g$ порядка $\ q$, где $\ q$ – большое простое число. Пусть $\ l_q$ и $\ l_p$ - параметры безопасности, причем $\ l_q = |q|$. Пусть $H: { \{0, 1\}^* } \rightarrow\ G_{g,q}$, $L: { \{ 0, 1 \}^*}\rightarrow\ Z_q^*$ и $G: { \{0, 1 \}^*}\rightarrow\ Z_q^*$- хэш-функции. Схема подписи представляет из себя следующее:

Генерация ключа

Пользователь выбирает случайный секретный ключ $x \in\ Z_q^*$ и вычисляет открытый ключ $y = g^x$.

Создание подписи

Входными данными являются секретный ключ $x \in\ Z_q^*$ и сообщение $m \in \{ 0, 1 \}^*$.

Далее сторона, создающая подпись:

1. выбирает случайное число $k \in \Z_q^*$ и случайный бит $b_m \in \{ 0, 1 \}$;

2. вычисляет $\ h = H (m, b_m)$;

3. вычисляет $\ u = h^x$;

4. вычисляет $\ v = ( g^n*h)^k$, где $\ n = L (m, g, h, y, u)$;

5. вычисляет $\ r = G (m, g, h, y, u, v)$;

6. вычисляет $s = k - xr \ mod\ q$.

Подписью сообщения $\ m$ является $\sigma\ = (u,r,s,b_m)$.

Проверка подписи

Чтобы проверить подпись $\ \sigma$ сообщения m, делается следующее:

1. $\ \sigma$ представляется как $\ (u,r,s,b_m)$;

2. вычисляется $\ h = H (m,b_m)$ и $\ n = L(m,g,h,y,u)$;

3. вычисляется $v \prime \ = (g^n*h)^s* (y^n*u)^r$;

4. проверяется, выполняется ли $\ r = G(m,g,h,y,u,v\prime)$.

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

Схема быстрой ЭЦП, основанная на алгоритме Фиата-Шамира

ZN обозначает кольцо целых чисел по модулю $\ N$, $\ t$ и $\ p$ — параметры безопасности, обычно $\ t \leqslant\ 4$, $\ p \leqslant\ 20$

Роль центра аутентификации ключей (ЦАК)

ЦАК выбирает:

• случайные простые числа $\ p$ и $\ q$ так, чтобы $\ p,q \geqslant\ 2^{256}$;

• однонаправленную хэш-функцию $\ h: Z_N\otimes Z \rightarrow\ {\{0,1\}}^tk$;

• свои собственные секретный и открытый ключи.

КАЦ публикует $\ N=p*q$, $\ h$ и открытый ключ.

Секретный ключ ЦАК используется для подписи создаваемых им открытых ключей. Для создания таких подписей ЦАК может использовать любую безопасную схему ЭЦП.

Генерация пользовательских ключей.

Каждый пользователь выбирает секретный ключ $\ s = (s_1,\cdots\,s_k)$, состоящий из случайных чисел $\ s_i$, $\ s_i$ меняется от 1 до $\ N$, таких, что НОД$\ (si,N)= 1$ для всех $\ s$ от 1 до $\ k$. Создание подписи может быть ускорено, если выбирать в качестве $\ s_1,\cdots\,s_k$ небольшие целые числа. Безопасность такой схемы основана на предположении о том, что вычисление корней $2^t \mod\ N$ является трудным. В настоящее время неизвестно о существовании алгоритмов, вычисляющих корни $2^t \mod\ N$ при условии, что эти корни порядка $\ N^{2^{-t+1}}$.

Регистрация пользователей.

ЦАК проверяет соответствие пользователя, создает строку $\ I$, содержащую имя, адрес и т. д. и создает подпись $\ S$ для пары $\ (I,v)$, состоящую из $\ I$ и открытого ключа пользователя $\ v$.

Создание подписи.

Входное сообщение $\ m$, секретный ключ $\ s = (s_1,\cdots\,s_k)$ и $\ N$ — модуль, по которому проводят вычисления.

1. Выбирается случайное число $\ r$ из диапазона $\ [1,N]$, вычисляется $\ x = r^{2^t}$.

2. Вычисляется $\ e = (e_11,\cdots\, e_tk) = h(x,m)$.

3. Вычисляется $\ y = r \prod\nolimits_{j=1}^k s_j^{\sum\nolimits_{i=1}^t e_{ij}*2^{i-1}} \mod\ N$.

Подписью на выходе является пара $\ (e,y)$.

Создание подписи требует не более $\ {k*t+t-1}$ операций умножения по модулю, а в среднем для случайного $\ e$ требуется только $\ t(k+2)/2+1$ операций умножения.

Проверка подписи.

Входные данные — подпись $\ (e,y)$, сообщение$\ m$, $\ v = (v_1,\cdots\,v_k)$, $\ I,S,N$.

1. Проверяется подпись $\ S$ для $\ (I,v)$.

2. Вычисляется $\ z = y^{2^t}\prod\nolimits_{j=1}^k v_j^{\sum\nolimits_{i=1} e_{ij}*2^{i-1}} \mod\ N$.

3. Проверяется, что $\ e =h (z,m)$.

Для проверки подписи требуется в среднем для случайного $\ e$ $\ t(k+2)/2+1$ операций умножения по модулю, максимум $\ {k*t + t}$.

Безопасность подписи.

Чтобы подделать подпись сообщения $\ m$, криптоаналитик должен решить уравнение $\ e =h (y^{2^t}\prod\nolimits_{j=1}^k v_j^{\sum\nolimits_{i=1}^t e_{i,j}*2^{i-1}},m) \mod\ N$ для $\ e$ и $\ y$.

В настоящее время неизвестно алгоритмов для решения этого уравнения.

Применение быстрой ЭЦП

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

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

Литература

• Fast Digital Signature Schemes as Secure as Diffie-Hellman Assumptions, Changshe Ma, Jian Weng and Dong Zheng, January 22, 2007

• Fasr Signature Generation with a Fiat Shamir-Like Scheme, H.Ong,C.P.Schnorr

См. также

• Алгоритм Диффи-Хеллмана

• Схема Шамира

• Быстрая криптосистема с открытым ключом

• Криптосистема с открытым ключом

• RSA

• Схема Эль-Гамаля

• Цифровая подпись

Ссылки

• [1]
• [2]
• [3]

• U.S. Patent 5 263 085