Pentru a încerca ceea ce s-a încercat, ar trebui să definim $H$ cu ieșire pe setul tuturor textelor cifrate ElGamal. Acest lucru este posibil și presupun acest lucru în paragraful următor.
Spre deosebire de manualul RSA, criptarea ElGamal nu este o funcție: criptarea în mod repetat a unui anumit text simplu generează (cu o probabilitate covârșitoare) texte cifrate diferite. Prin urmare, atunci când încercăm să verificăm o semnătură ca în întrebare, nu există niciun motiv pentru care criptarea semnăturii ar produce hash-ul original și (cu o probabilitate covârșitoare) verificarea semnăturii ar eșua. Sistemul de semnătură luat în considerare în întrebare nu este solid.
Pentru simplitate, luați în considerare ElGamal în grupa multiplicativă modulo $p$, remarcat $\mathbb Z_p^*$, cu $p$ și $(p-1)/2$ prim, și $G$ astfel încât $G^{(p-1)/2}\bmod p\,=\,p-1$:
- Cheia privată este un secret aleatoriu $x\in[0,p-1)$, cheia publică este $X:=G^x\bmod p\in[1,p)$.
- Criptarea textului simplu arbitrar $M\în[1,p)$ merge
- generează secret aleatoriu efemer $y\în[0,p-1)$
- calcula $Y:=G^y\bmod n$
- calcula $Z:=M\cdot X^y\bmod n$
- text cifrat de ieșire $(Y,Z)$
- Decriptarea textului cifrat arbitrar $(Y,Z)\în[1,p)\time[1,p)$ iesiri $M':=Y^{n-1-x}\cdot Z\bmod n$.
$M'=M$ indiferent de $y$. Sugestie de probă: Mica teoremă a lui Fermat.
Spre deosebire de manualul RSA, această variantă de ElGamal este aproape de a fi IND-CPA, dar nu este deloc. Sugestie de probă: luați în considerare relațiile dintre Simboluri Legendre de $\stanga(\frac M p\dreapta)$, $\stanga(\frac X p\dreapta)$, $\left(\frac Y p\right)$. Ignorăm această problemă relativ minoră în cele ce urmează.
Una dintre cele mai simple încercări de a corecta problema ridicată în al doilea paragraf al acestui răspuns ar fi remedierea $y=1$, prin urmare $Y=G$. Schema de semnătură a întrebării poate folosi apoi un hash $H$ cu ieșire $H(m)$ în întregul domeniu $[1,p)$ precum
$$H(m):=\big(\operatorname{SHAKE256}(m,b)\bmod p-1\big)+1\text{ cu }b=64\left\lceil\log_2(p)/64 +2\dreapta\rceil$$
și apoi
- Cheile private și publice sunt ca în criptare
- Semnătura de $m$ este $\sigma:=G^{n-1-x}\cdot H(m)\bmod n$
- Verificări de verificare $\sigma\cdot X\bmod n=H(m)$.
Cel puțin, verificarea reușește în absența modificărilor, astfel această schemă de semnătură este solidă. Dar este nesigur chiar și după cele mai simple criterii UF-KOA.
De asemenea, alte încercări simple eșuează, inclusiv
- realizarea $y$ un secret adăugat la cheia privată, cu $Y:=G^y\bmod n$ și $Y':=X^y\bmod n$ adăugat la cheia publică
- realizarea $y$ un hash al mesajului $m$
- realizarea $Y$ un hash al mesajului $m$
- aparent, orice lucru care funcționează într-un grup arbitrar, așa cum folosește criptarea ElGamal, iar semnătura este un element de grup ca ieșirile de decriptare ElGamal.
Deși acest lucru nu se aplică pentru ElGamal, apare o altă problemă atunci când se încearcă construirea unei semnături dintr-o schemă de criptare cu cheie publică generală și un hash pe domeniul său de text cifrat: decriptarea unui text cifrat arbitrar poate eșua (și se întâmplă pentru sisteme practice precum RSA-OAEP, RSAES-OAEP, RSAES-PKCS1-v1_5). Aceasta este de fapt o caracteristică în interesul IND-CCA Securitate.
Nu există o modalitate generală de a construi semnătură securizată din criptarea securizată cu cheie publică. Nici măcar semnătura RSA-FDH nu funcționează în acest fel: ea construiește semnătura dintr-o permutare unidirecțională și un hash pe domeniul permutației.
