2014-02-24
912
Схема цифровой подписи RSA
Конструкция с использованием схемы с открытым ключом
Конструкция цифровой подписи с использованием односторонней функции с секретом
Необходимо подписать документ m.
k – секрет односторонней функции.
– односторонняя функция с секретом.
Процедура проверки подписи:
.
.
Знание позволяет определить открытый ключ.
Схема шифрования с открытым ключом:
,
Закрытый ключ цифровой подписи совпадает с закрытым ключом схемы шифрования.
Открытый ключ цифровой подписи совпадает с открытым ключом схемы шифрования.
длина подписи увеличивается в 2 раза.
Существуют два вида цифровой подписи:
1) цифровая подпись с извлечением сообщения: если сообщение m обладает внутренней избыточностью, то сообщение m можно не пересылать.
В качестве подписанного сообщения используется сообщение цифровой подписи:
;
;
осмысленность, избыточность);
2)цифровая подпись с дополнением: вычисление цифровой подписи.
;
;
.
Закрытый ключ:
Открытый ключ:
– шифрование;
– расшифрование.
Цифровая подпись с извлечением: для того, чтобы подписать сообщение, необходимо расшифровать его на закрытом ключе.
Цифровая подпись с дополнением:
;
Безопасность:
Решение задачи факторизации. Задача сложная при правильном выборе p и q.
Мультиплекативность:
;
;
;
=>;
Произведение подписей есть подписи произведения сообщения
=> (m1, m2, S1, S2) => (mi, Si),
Проверка для подписи с извлечением: Se = осмысленному?
Для подписи с дополнением: Чтобы атака удалась необходимо, чтоб хэш-функция была мультиплекативна:
H(m1, m2) = H(m1)∙ H(m2).
Подпись с извлечением сообщения и с дополнением позволяют противостоять такой атаке.
Атаки на схемы шифрования:
1) если противник имеет доступ к расшифрованию, если используется один ключ шифрования и цифровой подписи, то он может:
- выбрать сообщение m;
- расшифровывать сообщение m:;
- использовать S в качестве подписи сообщение m.
2) если используется хэш-функция:
- выбрать сообщение m;
- расшифровать;
- использовать S в качестве подписи сообщение m.
Вывод: шифрование и цифровая подпись должны шифроваться на разных ключах.
Схема Эль-Гамаля=>Схема ЭЦП Шпорра=>DSА (американский стандарт ЭЦП)=>ГОСТ Р 34.10-94.
Параметры:
- хэш функция Н – ГОСТ Р 34.11;
- простое число p:;;
- простое число q:;;
- целое число а:;.
В ГОСТ Р 34.10-94 приведено полное описание процедуры генерации параметров (p,q,a).
Ключи:
- закрытый ключ – целое число x:;
- открытый ключ – целое число у:.
Процедура вычисления подписи:
1) вычислить (хэшировать);
2) выбрать число е: (двоичное число е совпадает с h);
3) если е(mod q)=0, то е=1;
4) вырабатываем случайное число k: 0<k<q;
5) вычисляем r и r’:,;
6) если r’=0, то повторить с шага 4;
7) вычислить значение;
8) если s=0, повторить шаг 4;
9) подпись.
,
1) проверить m, что 0<s<q, 0<r’<q. Если хотя бы одно из неравенств нарушено, то подпись отвергается;
2) вычислить;
3) выбрать число е:;
4) если е(mod q)=0, то е=1;
5);
6),;
7);
8).
, => 0<r’<q и пункт 6);
=> 0<s<q и пункт 8);
;
Корректность:.
Проверим, что:
;
;
;
По малой теореме Ферма:
Из теоремы Эллера:
=>;
;
;
=>
Стойкость:
1) Атака на закрытый ключ:
y=>x
=>можно решить задачу дискретного логарифмирования:
(если длина р=1024 бит);
если учесть, что 0<x256<q=>метод Полларда;
(если длина q=256 бит).
2) Атака на неотказуемость:
Мошенник пытается отказаться от подписанного им сообщения.
m – сообщение, s – подпись.
(m1,s1) => получатель
(m2,s2) предъявляет как истинное (m2,s2) и отказывается от первого сообщения.
Можно: s1=s2.
,
Следовательно, противник формирует сообщение с одинаковой подписью (m1,s), (m2,s), посылает (m1,s), предъявляет (m2,s), отказывается от m1.
;
;
,;
одинаково для m1,m2.
Необходимо определить, совпадают ли следующие две формулы:
;
;
;
фиксируем х1,k,e2,e1 => вычисляем x2.
Для того чтобы противостоять этой атаки, противник не должен знать полное содержание сообщения m1,m2 в момент генерации ключа. Это реализуется путем добавления в подписываемое сообщение атрибутов сертификата открытого ключа, которое формируется удостоверяющим центром, а не самим пользователем.
3) Атака на редуцированную хэш-функцию.
В формулах: e,
.
Криптографическая хэш-функция противостоит этим атакам.
Но в формулах используется следовательно, противник может подобрать также - коллизия редукции хэш-функции.
Противник при произвольном выборе параметров может подобрать q,m1,m2, чтобы выполнялось последнее равенство. Реализующие подписи должны выбирать правильность параметров p,q,а или вообще фиксировать параметры проверенным набором.
Уязвимости рандомизатора k:
k…ak, 0<k<q,
,
=>,;
;
=> ЭЦП=(1,x) – не зависит от m.
=> Проверка условия 0<k<q, необходима.
,; k1=k2=k.
,
,
=> противник вычисляет x.
Если значение k повториться при подписи двух разных документов, то противник легко вычислит ключ ЭЦП. Значение k должно генерироваться качественным датчиком случайных или псевдослучайных чисел.
2.3.5 «ГОСТ Р 34.10-2001»
, где n – количество бит q (n=256).
.
Есть две арифметики ГОСТ Р 34.10-94:
- mod p - сложность ниже, чем mod q;
- mod q.
Следовательно, надо заменить вычисление mod p на другую группу.
=> Заменили на группу точек эллиптической кривой.
Группа точек эллиптической кривой
Простое число p>3, эллиптической кривой E над полем Zp называется множество пар (x,y) где x,y ϵ Zp удовлетворяют следующему уравнению:.
.
Кривая может иметь следующий вид:
В проективном пространстве:
.
Сложение,,;
;
;
;
.
Если есть точка Q ϵ E:
.
;
Необходимо определить, где ноль.
Q + R = Q, следовательно Q + 0 = Q, 0 = (∞,∞).
Образовывается группа E = (+, -, 0).
Если есть точка
Сложности в Е: для того, чтобы вычислить кратную точку нужно использовать бинарный алгоритм возведения в степень в аддитивной форме, следовательно имеем дело с полимеальной сложностью.
Имеется т.. Требуется по известным P и Q найти. Задача дискретного логарифмирования в группе Е.
)=>экспоненциальная сложность.
Параметры схемы подписи ГОСТ Р 34.10-2001:
- простое число р:;
- эллиптическая кривая E,;
- простое число q,;
- т..
На параметры накладываются ограничения.
Ключи:
- з.к. - число d:;
- о.к. – т. эллиптической кривой.
Формирование с цифровой подписью:
1.;
2.
если е=0,то е=1;
3. случайное число k: 0<k<q;
4.,
,
,если r=0, то повторить с шага 3;
5.,если s=0, то повторить с шага 3;
6. цифровая подпись (r,s).
Проверка ц.п.:
1.Проверка
если хотя бы одно неравенство нарушено, то подпись не принимается;
2.,
3.
если е=0,то е=1;
4.
5.,;
6.,
;
7.проверить выполнение равенства.
Корректность:
По пункту 4 формирования ц.п.: =>.
Проверка, если r =0 =>не проходит =>.
По пункту 5 формирования ц.п.:,
=>.
s =0 => =>.
По пункту 7 проверки ц.п.: проверим неравенство.
;
;
;
;
(по пункту 4 формирования ц.п.);
(по пункту 4 формирования ц.п.);
(по пункту 6 проверки ц.п.).
Стойкость:
1)Атаки по mod q на з.к. d
(противник хочет узнать закрытый ключ d) =>задача дискретного логарифмирования в Е.
Используется метод Полларда:
Дискретное логарифмирование:
,
2)Атаки на неотказуемость (не доказано, что возможно).
3)Уязвимость рандомизатора k (актуальны).
