ФЭНДОМ


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

Проблемы ЭЦП Править

С момента изобретения ЭЦП в 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

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

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

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

КАЦ публикует \ 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

См. также Править


Ссылки Править

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики