2.3.5 Гост р 34.10-2001

ГОСТ 34 – 10²⁶, , у=а^х, r=a^k(modp) – надо улучшать, r’=r(modq), S=ke+xr’(modq).

- надо улучшать, .

ГРУППА ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ

Простое число р>3.

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

Сложение точек

Удвоение точек

О( )

Р+О=Р, (-Р)+Р=О, Р=(х,у), -Р=(х,-у)

Множество точек кривой Е являются коммутативной группой.

Задача дискретного логарифмирования на эллиптической кривой

Q=xP, при известных Q и P найти х. В настоящее время не известно быстрого алгоритма решения этой задачи, чем алгоритма со сложностью быстрее .

ГОСТ Р 34.10-2001

Выбор параметров:

- простое число р, р>2²⁵⁵;

- эллиптическая кривая Е, ;

- простое число q, 2²⁵⁴<q<2²⁵⁶;

- : qP=o(a^q=1(modp);

- фиксируется ХФ ГОСТ 34.11 Н.

Условия:

- должно быть выполнено , для t=1….B(B=31);

- ;

-

Выбор ключей:

- З.К. d: 0<d<q;

- О.К. Q=dP (аналог у=а^х)

Формирование ЦП: S(H,d)= :

1. h=H(m);

2. α: h=<α>₂₅₆, e=α(modq), если е=0, то е:=1;

3. генерируется специальное число k: 0<k<q;

4. C=kP, r=x_c(modq), если r=0, то переходить к 3);

5. s=(ke+rd)(modq), если s=0, то переходим к 3);

6. =<r>256||<s>256.

Проверка ЦП: V(m, ,Q), =<r>||<s>:

1) проверка 0<r<1, 0<s<q. Если хоть одно нарушается, то ЦП не действительна;

2) h=H(m);

3) α: h=<α>₂₅₆, e=α(modq), если е=0, то е:=1;

4) v=e^-1(modq);

5) z₁=sv(modq), z₂=-rv(modq);

6) C=z₁P+z₂Q, R=x_c(modq)

Аналог ГОСТ 34.10 – 94 –

7) , если совпали, то ЦП действительна, если нет, то не действительна.

Корректность

s=S(m,d),

z₁=sv(modq), z₁=sv+qt₁, z₂=-rv+qt₂, c₂=(sv+qt₁)P+(-rv+qt₂)Q=, где Q=dP, =(sv-rvd)P+(t₁+t₂d)*qP=, где qP=0, =(sv-rvd)P=v(s-rd)P=, где ev=1(modq) => ev=1+qt₃, s=(ke+rd)(modp) => s-rd=ke+qt₄, =r(ke+qt₄)P=v(keP+t₄qP)=, где t₄qP=0, = vkeP=(1+(q)t₃)k(P)=kP=c₁ => c₂=c₁ => .

0<s<q, 0<r<q. s<q, т.к. остаток , т.к. не может выпустить алгоритм.

r<q , т.к. остаток , т.к. не может выпустить алгоритм.

Безопасность

1) Атака на З.К. Задача нахождения значения d при условии, что известно Q и P, называется задачей дискретного логарифмирования в группе точек эллиптической кривой

, , а для ГОСТ 94 Т~10²⁶.

2) Атака на неотказуемость. Представляет собой для данной съемы. Сам ГОСТ не предоставляет методы защиты от таких атак. Безопасность должен обеспечивать протокол.

3) Уязвимости эфемерного ключа k.

2.4 ХЭШ-ФУНКЦИЯ

- одностороння функция

Сложно найти - коллизия ХФ.

Сложно вычислить прообраз (односторонняя функция)

2.4.1 Слабые и сильные хф

Слабой ХФ называется односторонняя функция, коорая удовлетворяет следующим условиям:

, где n – некоторое число, V_n – бит последовательности длины n, V* - бит последовательности длины.

1) легко вычислить H(x);

2) фиксированный , где : трудно найти H(x)=H(x’)

Сильная ХФ это односторонняя функция, которая удовлетворяет следующим условиям:

1) легко вычислить H(x);

2) трудно найти пару , : H(x)=H(x’)

Сильная также является слабой за счет 2-го условия, т.к. найти фиксированные коллизии нельзя.

Безопасность слабой ХФ

Найти коллизию k фиксированного х. Пербор х’ => различие H(x’)=H(x). Всего образов |V_n|=2ⁿ. В среднем противнику придется перебрать |V_n|/2 вариантов.

Если есть время Т, тогда T(n)=>n>log₂T+1, чтобы ХФ была безопасной должна выполняться функция.

Безопасность сильной ХФ

Найти коллизию . Перебор дает H(x)=H(x’). Всего образов |V_n|=2ⁿ. С вероятность 0,63 достаточно перебрать значений. . Чтобы ХФ была безопасной, должно выполняться

2^n/2>T=>n>log₂T

При одном и том же ресурсе противника сильная должна быть длинее в 2 раза, следовательно, снижается скорость ее работы.