Вариант цифровой подписи Шамира
Данная схема цифровой подписи основана на проверке выполнения соотношения вида
se = i×t¦(t, m) (mod n), (3.3.1)
где m – сообщение,
(s,t) - цифровая подпись,
i - личный идентификатор пользователя,
n - произведение двух больших простых чисел,
e - большое простое число такое, что (e, j(n)) = 1,
¦ - однонаправленная функция.
Параметры n, e и функция ¦ выбираются для организуемой сети пользователей специальным центром генерации ключей. Эти параметры являются общими для всех пользователей и хранятся в их личных электронных карточках. Данные параметры не являются секретными, однако факторизация модуля n должна быть известна только центру генерации ключей. Секретным же ключом пользователя “i” является число “g” такое, что
ge = i (mod n).
Числа “g” для пользователей легко могут быть вычислены в центре генерации ключей (так как там известна факторизация модуля n), в то время как посторонний человек в попытке восстановить “g” по известным e, i, n должен будет решить сложную задачу извлечения корня e-й степени в кольце Zn.
Каждое сообщение mÎZn будет иметь большое число “правильных” подписей (s,t), однако при случайном выборе пары (s,t) вероятность выполнения соотношения (3.3.1) будет очень мала ( » n-1). Если же зафиксировать один из параметров цифровой подписи, то попытка нахождения второго параметра подписи из уравнения (3.3.1) наталкивается на необходимость извлечения модулярных корней, что, как считается до настоящего времени, является сложной вычислительной задачей.
|
|
|
Тем не менее, если “g” известно, то имеется простой способ получения подписи для любого сообщения m, даже не имея разложения числа n.
Этот способ заключается в следующем.
Выбираем случайное число r и вычисляем
t = re (mod n).
Тогда проверочное уравнение (3.3.1) будет иметь вид
se = ge re¦(t, m) (mod n).
Так как (e, j(n)) = 1, то общий множитель “e” можно исключить из экспоненты:
s = g×r¦(t, m) ,
что приводит к нахождению параметра “s” и, следовательно, подписи к сообщению “m”.
Возможные слабости данной системы цифровой подписи могут проявиться при мультипликативных связях между идентификаторами пользователей. Действительно, из соотношения
i(k+1)=i(1)×i(2)…×i(k) (mod n)
следует, что gi(k+1)=gi(1)×gi(2)×…×gi(k) (mod n), где gj – идентификатор пользователя j.
|
|
|
В частности, если идентификаторы пользователей i и j связаны соотношением: j=i2 (mod n), тогда их секретные ключи gi, gj будут удовлетворять аналогичному соотношению: gj=gi2 (mod n). Следовательно, пользователь i из своего секретного ключа сможет восстановить секретный ключ пользователя j.
С целью ликвидации указанных связей можно предусмотреть общую для всех (открытую) процедуру перевода достаточно короткого идентификатора в длинную псевдослучайную последовательность, которая и будет играть роль идентификатора в проверочном соотношении.
Схема цифровой подписи Эль-Гамаля
Пусть a - примитивный элемент поля Zp вычетов по модулю большого простого числа p. Пусть m - сообщение, которое требуется подписать, 0 £ m £ p-1. Полагаем, что у каждого пользователя есть открытый ключ вида
y = ax (mod p),
где x – секретный ключ.
Чтобы подписать сообщение пользователь должен быть способен, используя свой секретный ключ x , найти подпись для “m” так, что все другие пользователи могли бы проверить истинность этой подписи, используя открытый ключ y (вместе с общими для всех a и p); и, кроме того, без знания секретного x было бы очень сложно подобрать подпись к сообщению “m”.
|
|
|
В качестве подписи для сообщения “m” предлагается использовать пару (r, s), 0 £ r, s £ p-1 такую, чтобы выполнялось уравнение
am = yr rs (mod p). (3.4.1)
Процедура подписи будет состоять из следующих трех шагов.
1. Выбирается случайное число k из интервала от 0 до p-1 такое, что
(k, p-1) = 1.
2. Вычисляется
r = ak (mod p). (3.4.2)
3. Перепишем уравнение (1) в виде
am = axr aks (mod p). (3.4.3)
Отсюда получим
m = xr + ks (mod p-1). (3.4.4)
Уравнение (3.4.4) разрешимо относительно s, если k выбрано таким, что
(k, p-1) = 1.
Отметим, что число k, выбираемое на шаге 1, нельзя использовать более одного раза.
Некоторые подходы к раскрытию данной схемы цифровой подписи
1. Пусть имеются L подписей {(ri, si), i=1, 2, ... , L} к соответствующим сообщениям (документам) {mi: i=1,2,...,L}. Тогда можно составить “L” линейных уравнений от L+1 неизвестных вида (3.3.4) и пытаться найти “x”.
|
|
|
Если какое-то значение k использовалось дважды, то система может стать практически однозначно разрешимой относительно “x”.
Например, если одно и то же значение k использовалось для подписи сообщений m1 и m2, то будем иметь систему уравнений над кольцом вычетов Zp-1:
m1 = x×r + k×s1 (mod p-1),
m2 = x×r + k×s2 (mod p-1).
Вычитая из первого уравнения второе, получим уравнение относительно k:
k×(s1-s2)=m1-m2 (mod p-1)
Данное уравнение будет иметь в точности НОД(s1-s2, p-1) решений, которые легко вычисляются.
Далее, подставив найденное значение k в первое из уравнений, получим уравнение относительно секретного ключа x:
x×r =m1- k×s1 (mod p-1),
из которого находится секретный ключ x. Знание ключа x в дальнейшем позволит злоумышленнику подписывать любые сообщения от имени законного пользователя.
2. Пусть задано “m”, и будем пытаться найти r,s такие, чтобы проверочное соотношение (3.4.1) выполнялось. Если зафиксировать r случайным образом в виде
r = aj mod p,
где j - случайное число, тогда нахождение для выбранного “r” соответствующего ему “s” равносильно решению задачи дискретного логарифмирования в поле GF(p).
Если же сначала зафиксировать s, то для вычисления r необходимо решить уравнение
rs ys = а (mod p),
которое, как считается, решить не проще, чем задачу дискретного логарифмирования в GF(p).
3. Как и другие предлагавшиеся системы цифровой подписи, данная система позволяет легко строить специального вида сообщения вместе с подписями. Пусть, например,
r' = aB yC (mod p), s' = -r'/С (mod p-1), m' = -r' B/С (mod p-1).
Тогда нетрудно проверить, что (r', s') является подписью для сообщения m'.
Заключительные замечания
Дата добавления: 2019-02-12; просмотров: 172; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!