На моем курсе криптографии мне дали следующее упражнение:
Эль-Гамаль предложил следующую схему цифровой подписи с использованием дискретных логарифмов по полю. $\mathbb{F}_p$, куда $р$ является большим простым числом.
Шаг 1) Все согласны с простым числом $р$ и генератор
$г$ за $\mathbb{F}_p^*$.
Шаг 2) A (и все другие варианты использования) выбирает секретный показатель $d_A$, и обнародует
$ e_A \ эквив г ^ {d_A} \ мод р $ (как и в криптосистеме Эль-Гамаля).
Шаг 3) Чтобы подписать сообщение, закодированное как целое число $м$ с $0\ле м\ле
р-1$, A выбирает случайное целое число
$к$ относительно простой $p-1$ (т.е. $\gcd(k,p-1)=1$). Затем вычисляет $r\эквив g^k \mod p$ и решает уравнение
$g^m\equiv e_A^r r^s
\ мод р $ в неизвестном $s$. В случае $с=0$ (весьма маловероятно), она снова начинает с другого $к$. Наконец, A отправляет B сообщение $м$ вместе с парой $(р,с)$, что является ее подписью для этого сообщения.
Шаг 4) Беатрис проверяет, что $г^м \экв
e_A^r r^s \mod p$. Если это верно, B принимает, что подпись $(р,с)$ действительно принадлежит А.
а) Убедитесь, что Ана знает все, что ей нужно для расчета $s$.
б) Проверить, что C не может выдать себя за A, не зная $d_A$, то есть не имея возможности решить задачу дискретного логарифмирования и, следовательно, $В$ можно быть уверенным, что сообщение действительно исходит от А.
c) Почему A должен отбрасывать $к$ если окажется, что $с=0$?
Вот что у меня есть:
а) Поскольку $ г \ эквив г ^ к \ мод р $ и $e_A=g^{d_A}\mod p$ тогда:
$$g^m\equiv e_A^rr^s\equiv (g^{d_A})^{r}(g^k)^s=g^{d_Ar+ks}\mod p$$
А из малой теоремы Ферма следует, что $m\equiv d_Ar+ks\mod p-1\Rightarrow ks\equiv m-d_Ar\mod p-1$. Следовательно, поскольку $\gcd(k,p-1)=1$ у нас есть это $к$ обратим в $\mathbb{F}^*_p$ и другие $s\equiv k^{-1}(m-d_Ar)\mod p-1$. Итак, мы закончили, так как Ана знает $p,k,m,d_A$ и $г$.
б) Если $С$ хочу притвориться $А$, нужно отправить $м$ и $(р,с)$ такой, что $g^m\equiv e_A^rr^s\mod p$. Но $s$ зависит от $d_A$ как мы видели в $а)$. Следовательно, мы не можем построить $s$ не зная $d_A$, и так, если $С$ хочу притвориться $В$, нужно найти $d_A$. Но это трудно, так как единственное, что мы знаем о $d_A$ (если мы не $А$) в том, что $ e_A \ эквив г ^ {d_A} \ мод р $ так и притворяясь $А$ эквивалентно решению задачи дискретного логарифмирования.
в) Если $с=0$ тогда $g^m\equiv e_A^r\equiv g^{d_Ar}\mod p$ и другие $m\equiv d_Ar\mod p-1$. Отсюда я застрял, так как это единственная информация, которая у меня есть, но я не понимаю, как это позволяет нам создавать сигнатуру, не зная $d_A$. Конечно, мы можем решить $m\equiv d_Ar\mod p-1$, который будет иметь $\gcd(r,p-1)$ решения, а затем проверить, какое из них является правильным $d_A$, но $\gcd(r,p-1)$ может быть близко к $p-1$ если нам не повезло, и это означало бы, что этот процесс экспоненциальный, и это не лучше, чем решение дискретного логарифма.
Если вы можете проверить правильность а) и б) и подсказать в) буду очень признателен.
