Регистрация Войти
Рейтинг:1
xrbToTheMoon avatar Crypto

Путаница с восстановлением закрытого ключа в подписи DSA, когда происходит дублирование значения r

флаг th
xrbToTheMoon

В подписи DSA, где подписание выполняется через

$$s = k^{-1}(H(m) + xr) \mod{q} $$

Я понимаю, почему, если два сообщения подписаны одним и тем же закрытым ключом $х$ использовать то же самое $к$ значение вы можете восстановить закрытый ключ

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

С $$r = (g^k \mod{p}) \mod{q}$$

как два $г$равные дают вам то же самое $к$? Разве не должно быть что-то вроде $\lfloor p/ q\rfloor$ разные $к$это приводит к тому же $г$ поскольку $г$ является генератором циклической группы $\mathbb{Z}_p^*$? У них не будет одинакового обратного модуля $q$ так как же решить два уравнения, если неизвестных три, $k_1^{-1}, k_2^{-1}, x$

Что мне не хватает?

67
0 + 0
Рейтинг:2
Daniel S avatar Crypto
флаг ru
Daniel S

Во-первых, обратите внимание, что $г$ не является генератором полной циклической группы $(\mathbb Z/p\mathbb Z)^*$, но циклической подгруппы порядка $q$. Таким образом, мы можем видеть только самое большее $q$ возможное $г$ значения, и мы ожидаем увидеть любой заданный $r\pmod q$ значение примерно в Пуассон(1) раз. Это означает, что мы ожидаем примерно $(1-2/e)q$ $г$ значения, соответствующие более чем одному $к$.

Однако, даже если бы нам гарантировали, что мы всегда будем выбирать разные $к$ значения с каждой подписью, мы не ожидали бы увидеть повторяющееся $г$ значение до $\квт д$ подписи были сгенерированы (по парадоксу дня рождения). На самом деле, это очень маловероятное количество подписей для криптографического размера. $q$ поэтому любое повторение с гораздо большей вероятностью может быть связано с повторяющимся $к$ значение из-за какой-то ошибки реализации. Это не теорема, а надежное эмпирическое правило.

0 + 0
xrbToTheMoon avatar
флаг th
xrbToTheMoon
хорошо, мне становится легче, я не сумасшедший! :) Спасибо, что нашли время ответить!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.