Атака на редуцированную хэш-функцию.

В формулах: e ,

.

Криптографическая хэш-функция противостоит этим атакам.

Но в формулах используется следовательно, противник может подобрать также - коллизия редукции хэш-функции.

Противник при произвольном выборе параметров может подобрать q,m₁,m₂, чтобы выполнялось последнее равенство. Реализующие подписи должны выбирать правильность параметров p,q,а или вообще фиксировать параметры проверенным набором.

Уязвимости рандомизатора k:

k…a^k, 0<k<q,

,

=> , ;

;

=> ЭЦП=(1,x) – не зависит от m.

=> Проверка условия 0<k<q, необходима.

, ; k₁=k₂=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 над полем Z_p называется множество пар (x,y) где x,y ϵ Z_p удовлетворяют следующему уравнению: .

.

Кривая может иметь следующий вид:

В проективном пространстве:

.

Сложение , , ;

;

;

;

.

Если есть точка 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).

Проверка ц.п. :

Проверка

если хотя бы одно неравенство нарушено, то подпись не принимается;

2. ,

3.

если е=0,то е=1;

4.

5. , ;

6. ,

;