Чтобы попробовать то, что было предпринято, нам нужно определить $Ч$ с выходом на множество всех шифротекстов Эль-Гамаля. Это возможно, и я предполагаю это в следующем абзаце.
В отличие от учебника RSA, шифрование Эль-Гамаля не является функцией: повторное шифрование заданного открытого текста дает (с подавляющей вероятностью) разные зашифрованные тексты. Поэтому, когда мы пытаемся проверить подпись, как в вопросе, нет никаких причин, по которым шифрование подписи даст исходный хеш, и (с большой вероятностью) проверка подписи не удастся. Рассматриваемая в вопросе система подписи не является надежной.
Для простоты рассмотрим Эль-Гамаля в мультипликативная группа по модулю $р$, отмеченный $\mathbb Z_p^*$, с $р$ и $(p-1)/2$ премьер, и $G$ такой, что $G^{(p-1)/2}\bmod p\,=\,p-1$:
- Закрытый ключ — это случайный секрет $х\в[0,р-1)$, открытый ключ $X:=G^x\bmod p\in[1,p)$.
- Шифрование произвольного открытого текста $M\in[1,p)$ идет
- генерировать эфемерный случайный секрет $y\in[0,p-1)$
- вычислять $Y:=G^y\bmod n$
- вычислять $Z:=M\cdot X^y\bmod n$
- выходной зашифрованный текст $(Г,Z)$
- Расшифровка произвольного зашифрованного текста $(Y,Z)\in[1,p)\times[1,p)$ выходы $M':=Y^{n-1-x}\cdot Z\bmod n$.
$М'=М$ невзирая на $у$. Доказательство подсказки: Маленькая теорема Ферма.
В отличие от учебника RSA, этот вариант Эль-Гамаля близок к Индивидуальная цена за конверсию, но не совсем. Подсказка: рассмотрим отношения между Символы Лежандра из $\left(\frac M p\right)$, $\влево(\фракция X p\вправо)$, $\влево(\фракция Y p\вправо)$. В дальнейшем мы игнорируем эту относительно незначительную проблему.
Одной из самых простых попыток исправить проблему, поднятую во втором абзаце этого ответа, было бы исправить $у=1$, таким образом $Y=G$. Затем схема подписи вопроса может использовать хэш $Ч$ с выходом $Ч(м)$ в полном домене $[1,р)$ такие как
$$H(m):=\big(\operatorname{SHAKE256}(m,b)\bmod p-1\big)+1\text{с}b=64\left\lceil\log_2(p)/64 +2\право\rceil$$
а потом
- Закрытый и открытый ключи как в шифровании
- Подпись $м$ является $\sigma:=G^{n-1-x}\cdot H(m)\bmod n$
- Проверочные чеки $\sigma\cdot X\bmod n=H(m)$.
По крайней мере, проверка проходит без изменений, так что эта схема подписи верна. Но это небезопасно даже по самым простым критериям УФ-КОА.
Другие простые попытки также терпят неудачу, в том числе
- изготовление $у$ секрет, добавленный к закрытому ключу, с $Y:=G^y\bmod n$ и $Y':=X^y\bmod n$ добавлен в открытый ключ
- изготовление $у$ хэш сообщения $м$
- изготовление $Y$ хэш сообщения $м$
- по-видимому, все, что работает в произвольной группе, как использует шифрование Эль-Гамаля, а подпись является групповым элементом, как выводит дешифрование Эль-Гамаля.
Хотя это не относится к Эль-Гамалю, возникает другая проблема при попытке создать подпись из общей схемы шифрования с открытым ключом и хэша в его домене зашифрованного текста: расшифровка произвольного зашифрованного текста может завершиться неудачно (что и происходит для практических систем, таких как РСА-ОАЭП, РГАЭС-ОАЭП, RSAES-PKCS1-v1_5). Это на самом деле функция в интересах IND-CCA безопасность.
Не существует общего способа создания безопасной подписи из безопасного шифрования с открытым ключом.. Даже подпись RSA-FDH не работает таким образом: она строит подпись из односторонней перестановки с лазейкой и хэша в домене перестановки.
