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

Интернет магазин китайских планшетных компьютеров

Компьютеры - Быстрая цифровая подпись - Некоторые алгоритмы быстрой цифровой подписи

22 января 2011

Оглавление:
1. Быстрая цифровая подпись
2. Некоторые алгоритмы быстрой цифровой подписи
3. Применение быстрой ЭЦП.

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

Пусть $\ 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 \in\ Z_q^*$ и сообщение $m \in \{ 0, 1 \}^*$ .

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

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

2. вычисляет $\ h = H$ ;

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

4. вычисляет $\ v =^k$ , где $\ n = L$ ;

5. вычисляет $\ r = G$ ;

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

Подписью сообщения $\ m$ является $\sigma\ =$ .

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

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

1. $\ \sigma$ представляется как $\$ ;

2. вычисляется $\ h = H$ и $\ n = L$ ;

3. вычисляется $v \prime \ =^s*^r$ ;

4. проверяется, выполняется ли $\ r = G$ .

Если равенство на шаге 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_i$ , $\ s_i$ меняется от 1 до $\ 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$ .

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

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

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

2. Вычисляется $\ e = = h$ .

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

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

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