Безопасная модификация DSA?

mti

28.09.2023, 13:21

В ДСА, мы вычисляем подпись $(р,с)$ на $м$ путем выборки $k\in\{1,...,q-1\}$ а затем вычисления

$r := g^k \bmod p$

$s := k^{-1}*(m+x*r) \bmod q$

При проверке вычисляем $v:=g^{m*s^{-1}}*y^{r*s^{-1}}\bmod p$ а потом проверь $r=v \bmod q$.

Вопрос: Было бы хорошо уйти $к^{-1}$ из расчета $s$ (т.е. $s := m+x*r$), а затем вместо этого проверьте $ г = v $?

0 + 0

дискретный логарифм

теория чисел

Рейтинг:3

Crypto

poncho

28.09.2023, 14:06

Вопрос: Было бы хорошо уйти $к^{-1}$ из расчета $s$ (т.е. $s := m+x*r$), а затем вместо этого проверьте $ г = v $?

Другими словами, тогда чек будет $g = g^{ms^{-1}}y^{rs^{-1}}$

Это было бы небезопасно; предположим, что у нас есть действительная подпись для $м$, то есть имеем значения $(м, г, с)$ такой, что $g = g^{ms^{-1}}y^{rs^{-1}}$

Тогда для произвольного сообщения $м'$, мы можем вычислить $s' = м'м^{-1}s$ и $r' = rs's^{-1}$; У нас есть $g^{m's'^{-1}}y^{r's'^{-1}} = g^{ms^{-1}} y^{rs^{-1}}$, который $г$ (поскольку исходная подпись действительна); это, $(м', г', с')$ является подделкой.

0 + 0

Daniel S

28.09.2023, 16:00

Что еще хуже, мы можем восстановить закрытый ключ $x$, потому что $x=(s-m)/r\pmod q$, а $s$, $m$ и $r$ — общедоступные значения.

Ответить

Admin