Электронный документооборот

 

 

     Схема цифровой подписи  ElGamal

     Для генерации ключевой пары выбираются большое простое число р и примитивный элемент g мультипликативной группы поля GF(p). Выбирается случайное число х такое, что x<p-1. Открытым ключом является y = g^x ( mod p), секретным ключем является x.

     Подпись сообщения M Для того, чтобы подписать сообщение M пользователю A необходимо выполнить следующие действия:

1. выбрать случайно и равновероятно число k из группы обратимых элементов кольца Z _p-1 ^*. То есть НОД(k,p-1) = 1,
2. вычислить a = g^k (mod q),
3. вычислить b = (M-xa)k^-1 (mod p-1),
4. подписью для сообщения M является пара (a,b).

     Проверка  подписи для сообщения M Для проверки подписи (a,b) для сообщения M получатель B проверяет выполнение равенства  
g^M = y^a a^b (mod p).

     Надо  заметить, что для ускорения процесса подписи вычисления на шагах 1,2 можно  проводить заранее, вычислять значения k^-1 тоже. Как и в других похожих схемах подписи значение k должно оставаться в секрете и выбираться cлучайно.  

     Вероятностная схема подписи Рабина

     В 1978 г. Рабин предложил следующий  способ подписи. Пусть E - функция шифрования некоторой криптосистемы, (k_i, 1 <= i <= 2r) - последовательность случайно выбранных ключей, которые отправитель A держит в секрете. Пользователь B получает список параметров проверки (X_i,U_i) (1 <= i <= 2r), где

     E(X_i,k_i) = U_i (1 <= i <= 2r).

     Эти параметры хранятся в доступном  для всех месте.

     Предположим, что A хочет подписать сообщение m. Его подписью будет цепочка S = S₁S₂..S_2r, для каждого i (1<=i<=2r) S_i =E(m,k_i). B делает следующее. Сначала он выбирает случайным образом r ключей, которые A должен ему предъявить: k_i1 , k_i2 ,..,k_ir. При получении этих ключей от A он проверяет:

     E(m,k_i1) = S_i1, E(X_i1,k_i1) = U_i1

     и далее для всех индексов i₂, i₃ ,.., i_r . Он считает действительной подпись от A только в том случае, когда выдерживаются все проверки. Безопасность получателя зависит от его уверенности в том, что только отправитель, знающий секретный ключ, может послать так подписанное сообщение. Что касается A, то предположим, что он отказывается от сообщения, которое по утверждению B он подписал. Тогда протокол для A следующий: он должен предъявить судье свои секретные ключи k₁,k₂,..,k_2r, и в присутствии обеих сторон делается 2r проверок:

     E(m,k_i)=S_i, E(X_i,k_i)=U_i.

     Рассмотрим, что это означает в трех возможных  случаях.

1. Корректными являются менее r проверок. Тогда B не должен был принимать подписанное сообщение.
2. Выдерживается точно r проверок, то есть при формировании ключей B выбрал именно это подмножество из r ключей. Вероятность, что он угадает это подмножество, равна

   p_r = (C_2r ^r)^-1,

   для r=18, p_r примерно равно 10^-10.

3. Выдерживается r+1 и более проверок: отказ абонента A не принимается.

 

     Схема Диффи - Лампорта

     Для аутентификации пользователя можно  применять произвольную симметрическую схему. Пусть отправитель сообщения  A хочет подписать n-битовое бинарное сообщение  
m=m₁.. m_n из V₂ⁿ.

     Он  выбирает 2n ключей некоторой криптосистемы, которые хранятся в секрете. Обозначим  их так: a₁,..,a_n;b₁,..,b_n.

     Если  E - алгоритм шифрования, то A генерирует 4n параметров проверки { (X_i,Y_i,U_i,V_i): 1<= i <= n}, где X_i и Y_i - величины, подаваемые на вход E и связанные соотношениями

     U_i = E(X_i,a_i), V_i = E(Y_i,b_i), 1 <= i < n.

     Параметры проверки заранее посылаются получателю B и третьему доверенному лицу.

     Чтобы подписать n-битовое сообщение m=(m₁,..,m_n), пользователь A применяет следующую процедуру: его подпись будет цепочкой S = S₁ ..S_n,  
где для каждого i

     S_i = a_i, если m_i =0,

     S_i = b_i, если m_i =1.

     Пользователь  B проверяет подпись следующим образом: для каждого i (0 <= i <= n) он использует бит m_i и ключ S_i, чтобы проверить:

     если  m_i = 0, то E(X_i,S_i) = U_i,

     если  m_i = 1, то E(Y_i,S_i) = V_i.

     Пользователь  B принимает подписанное сообщение за истинное только в том случае, если при процедуре проверки эти равенства выполнены для каждого L.

     Эта система проста в использовании, но у нее есть, по крайней мере, два очевидных недостатка. Во-первых, необходима предварительная передача параметров проверки. Во-вторых, что более важно, подпись сильно увеличивает длину сообщения. Если в криптосистеме используются ключи длиной, скажем, 64 бита, то длина подписанного сообщения увеличится в 64 раза.  

     Схема цифровой подписи ESIGN

     Esign --- это схема подписи, предложенная Okamoto и Shiraishi в 1985 году. Она использует вычисления в кольце вычетов со специальным типом модуля. Главное преимущество схемы Esign --- это ее скорость. В сравнении с системами, основанными на схеме RSA или схеме Эль-Гамаля, Esign отличается в несколько раз более высоким быстродействием процессов подписи документа и проверки подписи. Пусть N = p² q --- 3k разрядное целое, где p и q - два простых числа примерно одинаковой длины. Секретную часть ключа составляют два k-битных простых числа p и q, а открытую часть ключа --- пара (N,e), где e - целое число, большее четырех. Схема Esign использует (k-1) битную хэш-функцию H, для вычисления хэш-значения от подписываемого сообщения. Подпись для сообщения M вычисляется следующим образом:

1. Сообщение M сначала хэшируется, то есть вычисляется H(M). Мы обозначим за y '3k' разрядное целое число, соответствующее битовой строке 0||H(M)||0^2k, где 0^2k - последовательность из 2k нулей.
2. Число r случайно выбирается из Z _{p q} ^* (обратимые элементы кольца Z _{p q}).
3. Вычисляются значения:

    z = x - r ^e (mod N).

    w₀ = ⌈ z/pq ⌉ + 1.

    w₁ = w₀ pq - z.

    Если w₁ > 2^2k-1 тогда снова выполнить шаг 2.

    u = w₀ (e r^e-1)^-1 (mod p).

    s = r + u*p*q.

4. Подписью M будет s.

     Для проверки правильности подписи сообщения M проверяющий просто сравнивает k старших разрядов s^e (mod N) с 0||H(M) и на основании этого сравнения делает вывод о принятии (если битовые последовательности совпадают) или отклонении (если битовые последовательности не совпадают) подписи. Истинность алгоритм проверки подписи следует из

     s^e = (r + u*p*q)^e (mod N) = r^e + e*r ^e-1*u*p* q ( mod N)=  
= (y-z) + w₀*p*q ( mod N) = y + w₁ (mod N).

     Так как w₁ < 2 ^2k-1 и N - в точности 3k разрядное целое число, то k старших разрядов ( s^e (mod N) ) те же, что и у y, то есть 0||H(M). Стойкость схемы Esign основывается на разновидности проблемы RSA, на извлечении корня e-й степени в кольце вычетов. Точнее, вычисление 'приближенного' значения корня, что считается сложной задачей. Формально задача извлечения приближенного корня (AER Approximate e-th Root problem ) описывается следующим образом: даны модуль N = p²*q, экспонента e>3 и y - обратимый элемент кольца вычетов Z_N, найти x - обратимый элемент кольца вычетов Z_N такой, что y <= x^e <= y + 2^2k-1. Известно, что факторизация N дает эффективное решение данной задачи. Без знания pили qэта задача считается сложной. Предположение AER заключается в том, что проблема AER является трудноразрешимой.

     Важно отметить, что в первоначальном варианте схемы допускался выбор экспоненты e равной 2 или 3, что упрощало вычисление подписи и ее проверку. Однако в этом случае имеются алгоритмы криптоанализа данной схемы, разработанные E. F. Brickell, J. M. DeLaurentis и A. M. Odlyzko. В [2] cказано, что случайные числа r должны выбираться независимо, случайно и равновероятно из Z_p*q^* . В частности, использование линейного конгруэнтного генератора для задания r с опубликованными параметрами приводит к компроментации секретного ключа.