La cursul meu de criptografie mi s-a dat următorul exercițiu:
ElGamal a propus următoarea schemă de semnătură digitală folosind logaritmi discreti pe un câmp $\mathbb{F}_p$, Unde $p$ este un prim mare.
Pasul 1) Toată lumea este de acord asupra unui prim $p$ si un generator
$g$ pentru $\mathbb{F}_p^*$.
Pasul 2) A (și toate celelalte utilizări) alege un exponent secret $d_A$, și face public
$e_A\equiv g^{d_A}\mod p$ (la fel ca în criptosistemul ElGamal).
Pasul 3) Pentru a semna un mesaj, codificat ca un număr întreg $m$ cu $0\le m\le
p-1$, A alege un număr întreg aleatoriu
$k$ relativ prim pentru $p-1$ (adică $\gcd(k,p-1)=1$). Apoi calculează $r\equiv g^k \mod p$ și rezolvă ecuația
$g^m\equiv e_A^r r^s
\mod p$ în necunoscut $s$. În cazul în care $s=0$ (destul de puțin probabil), ea începe din nou cu altceva $k$. În cele din urmă, A îi trimite lui B mesajul $m$ împreună cu perechea $(r,s)$, care este semnatura ei pentru acel mesaj.
Pasul 4) Beatriz verifică asta $g^m \equiv
e_A^r r^s \mod p$. Dacă acest lucru este valabil, B acceptă semnătura $(r,s)$ chiar aparține lui A.
a) Verifică dacă Ana știe tot ce trebuie să calculeze $s$.
b) Verificați că C nu poate pretinde că este A fără să știe $d_A$, adică fără a putea rezolva o problemă de logaritm discret și, prin urmare $B$ pot fi sigur că mesajul vine cu adevărat de la A.
c) De ce trebuie A arunca $k$ dacă se dovedește că $s=0$?
Asta am:
a) Din moment ce $r\equiv g^k\mod p$ și $e_A=g^{d_A}\mod p$ atunci:
$$g^m\equiv e_A^rr^s\equiv (g^{d_A})^{r}(g^k)^s=g^{d_Ar+ks}\mod p$$
Și mica teoremă a lui Fermat implică asta $m\equiv d_Ar+ks\mod p-1\Rightarrow ks\equiv m-d_Ar\mod p-1$. Prin urmare, din moment ce $\gcd(k,p-1)=1$ avem asta $k$ este inversabilă în $\mathbb{F}^*_p$ Așadar $s\equiv k^{-1}(m-d_Ar)\mod p-1$. Prin urmare, am terminat, din moment ce Ana știe $p,k,m,d_A$ și $r$.
b) Dacă $C$ vreau să pretind că sunt $A$, trebuie trimis $m$ și $(r,s)$ astfel încât $g^m\equiv e_A^rr^s\mod p$. Dar $s$ depinde de $d_A$ după cum am văzut în $a)$. Prin urmare, nu putem construi $s$ fara sa stie $d_A$, și așa, dacă $C$ vreau să pretind că sunt $B$, trebuie să găsească $d_A$. Dar asta este greu, din moment ce singurul lucru despre care știm $d_A$ (dacă nu suntem $A$) este asta $e_A\equiv g^{d_A}\mod p$ și așa, prefăcându-se că sunt $A$ este echivalent cu rezolvarea unei probleme de logaritm discret.
c) Dacă $s=0$ atunci $g^m\equiv e_A^r\equiv g^{d_Ar}\mod p$ Așadar $m\equiv d_Ar\mod p-1$. De aici sunt blocat, deoarece acestea sunt singurele informații pe care le am, dar nu văd cum ne permite asta să construim o semnătură fără să știm $d_A$. Desigur, putem rezolva $m\equiv d_Ar\mod p-1$, care va avea $\gcd(r,p-1)$ soluții și apoi verifică care este cea corectă $d_A$, dar $\gcd(r,p-1)$ poate fi aproape de $p-1$ dacă avem ghinion, și asta ar însemna că acest proces este în timp exponențial și nu este mai bine decât rezolvarea logaritmului discret.
Dacă puteți verifica dacă a) și b) au dreptate și dați-mi un indiciu cu privire la c) vă voi fi foarte recunoscător.
