Схема цифровой подписи ESIGN
Esign --- это схема подписи, предложенная Okamoto и Shiraishi в 1985 году. Она использует вычисления в кольце вычетов со специальным типом модуля. Главное преимущество схемы Esign --- это ее скорость. В сравнении с системами, основанными на схеме RSA или схеме Эль-Гамаля, Esign отличается в несколько раз более высоким быстродействием процессов подписи документа и проверки подписи. Пусть N = p2 q --- 3k разрядное целое, где p и q - два простых числа примерно одинаковой длины. Секретную часть ключа составляют два k-битных простых числа p и q, а открытую часть ключа --- пара (N,e), где e - целое число, большее четырех. Схема Esign использует (k-1) битную хэш-функцию H, для вычисления хэш-значения от подписываемого сообщения. Подпись для сообщения M вычисляется следующим образом:
  1. Сообщение M сначала хэшируется, то есть вычисляется H(M). Мы обозначим за y '3k' разрядное целое число, соответствующее битовой строке 0||H(M)||02k, где 02k - последовательность из 2k нулей.
  2. Число r случайно выбирается из Z p q * (обратимые элементы кольца Z p q).
  3. Вычисляются значения:
    (a)
    z = x - r e (mod N).
    (b)
    w0 = ⌈ z/pq ⌉ + 1.
    (b)
    w1 = w0 pq - z.
    Если w1 > 22k-1 тогда снова выполнить шаг 2.
    (c)
    u = w0 (e re-1)-1 (mod p).
    (d)
    s = r + u*p*q.
  4. Подписью M будет s.
Для проверки правильности подписи сообщения M проверяющий просто сравнивает k старших разрядов se (mod N) с 0||H(M) и на основании этого сравнения делает вывод о принятии (если битовые последовательности совпадают) или отклонении (если битовые последовательности не совпадают) подписи. Истинность алгоритм проверки подписи следует из
se = (r + u*p*q)e (mod N) = re + e*r e-1*u*p* q ( mod N)=
= (y-z) + w0*p*q ( mod N) = y + w1 (mod N).
Так как w1 < 2 2k-1 и N - в точности 3k разрядное целое число, то k старших разрядов ( se (mod N) ) те же, что и у y, то есть 0||H(M). Стойкость схемы Esign основывается на разновидности проблемы RSA, на извлечении корня e-й степени в кольце вычетов. Точнее, вычисление 'приближенного' значения корня, что считается сложной задачей. Формально задача извлечения приближенного корня (AER Approximate e-th Root problem ) описывается следующим образом: даны модуль N = p2*q, экспонента e>3 и y - обратимый элемент кольца вычетов ZN, найти x - обратимый элемент кольца вычетов ZN такой, что y <= xe <= y + 22k-1. Известно, что факторизация N дает эффективное решение данной задачи. Без знания pили qэта задача считается сложной. Предположение AER заключается в том, что проблема AER является трудноразрешимой.
Важно отметить, что в первоначальном варианте схемы допускался выбор экспоненты e равной 2 или 3, что упрощало вычисление подписи и ее проверку. Однако в этом случае имеются алгоритмы криптоанализа данной схемы, разработанные E. F. Brickell, J. M. DeLaurentis и A. M. Odlyzko. В [2] cказано, что случайные числа r должны выбираться независимо, случайно и равновероятно из Zp*q* . В частности, использование линейного конгруэнтного генератора для задания r с опубликованными параметрами приводит к компроментации секретного ключа.

back next
Hosted by uCoz