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

Проблемы ЭЦП

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

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

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

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

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

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

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

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

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

1. выбирает случайное число ${\displaystyle k\in \mathbb {Z} _{q}^{*}}$ и случайный бит ${\displaystyle b_{m}\in \{0,1\}}$ ;

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

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

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

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

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

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

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

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

1. ${\displaystyle \ \sigma }$ представляется как ${\displaystyle \ (u,r,s,b_{m})}$ ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Вычисляется ${\displaystyle \ e=(e_{1}1,\cdots \,e_{t}k)=h(x,m)}$ .

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

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

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

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

Входные данные — подпись ${\displaystyle \ (e,y)}$ , сообщение ${\displaystyle \ m}$ , ${\displaystyle \ v=(v_{1},\cdots \,v_{k})}$ , ${\displaystyle \ I,S,N}$ .

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

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

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

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

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

Чтобы подделать подпись сообщения ${\displaystyle \ m}$ , криптоаналитик должен решить уравнение ${\displaystyle \ 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}$ для ${\displaystyle \ e}$ и ${\displaystyle \ 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

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

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

Ссылки