RSA-podpis, ki je opisan v [5], je za razliko od Elgamalovega determinističen. Kako bi ga lahko spremenili v nedeterminističnega? Varnostno analiziraj svoj predlog.

Sporočilo lahko podaljšamo z naključnimi biti preden ga podpišemo. Pri preverjanju iz podpisa dobimo sporočilo z naključnimi biti. Za sporočilo preverimo, če je pravilno, naključne bite pa ignoriramo.
Dobili smo več različnih podpisov za vsako sporočilo. S tem poenostavimo nalogo napadalcu, ki si lahko izmisli podpis in izračuna kateremu sporočilu pripada. Da se zavarujemo pred tem, moramo dodati še zgoščevalno funkcijo.
Sporočilo podpišemo tako, da najprej uporabimo zgoščevalno funkcijo in rezultatu dodamo naključne bite. Ko preverjamo veljavnost podpisa, najprej iz podpisa izračunamo zgoščeno vrednost z naključnimi biti. Naključne bite lahko ignoriramo, zgoščeno vrednost pa primerjamo z zgoščeno vrednostjo sporočila.
Napadalec si še vedno lahko izbere podpis in iz njega izračuna zgoščeno vrednost z naključnimi biti, ampak zaradi lastnosti zgoščevalnih funkcij, ne more izračunati sporočila iz zgoščene vrednosti.

Kakšne lastnosti naj ima zgoščevalna funkcija, da ne bo ogrožena varnost podpisa?

Odpornost praslik (enosmernost): težko je najti vhodno vrednost, ki jo zgoščevalna funkcija preslika v izbrano zgoščeno vrednost.

Odpornost drugih praslik: za izbrano vhodno vrednost je težko najti drugačno vhodno vrednost z enako zgoščeno vrednostjo.

Odpornost na trke: težko je najti dve različni vhodni vrednosti z enako zgoščeno vrednostjo.

S prijateljem drug drugemu predlagajta način, s katerim bi iz dokumenta poljubne dolžine z bločno šifro skonstruirali izvleček fiksne dolžine, nato pa poskusita prijateljeve predloge analizirati.

Recimo, da imamo bločno šifro z dolžino bloka 64 bitov in tudi dolžino ključa 64 bitov. Dokument poljubne dolžine razdelimo na bloke dolžine 64 bitov. Vsak blok zašifriramo z bločno šifro, za ključ pa vzamemo kriptogram prejšnjega bloka $$ H_i = E_k(x_i),$$ kjer je $x_i$ blok dokumenta, $H_i$ kriptogram bloka in $k = H_{i-1}$ ključ. Opazimo, da smo iz 128b (64b je blok dokumenta in 64b je ključ) dobili rezultat ($H_i$) dolžine 64b. Če to ponovimo za vsak blok iz dokumenta, dobimo končen rezultat dolžine 64b. S tem smo skonstruirali zgoščevalno funkcijo z izvlečkom dolžine 64b.
Izkaže se, da lahko za tako zgoščevalno funkcijo hitro najdemo trk, kar pomeni, da funkcija ni varna. To popravimo tako, da malo spremenimo računanje $H_i$. Ena od možnosti je $$ H_i = E_k(x_i) \oplus x_i,$$ kjer $\oplus$ predstavlja XOR oziroma ekskluzivni ali.

V razdelku o digitalnem podpisu smo omenili šifrirno funkcijo $e_{J(B)}$, ki jo uporabi Anita, in Bojanovo odšifrirno funkcijo $d_{Z(B)}$. Elgamal je predlagal taki funkciji na osnovi DLP. Če je sporočilo $m$ iz grupe $G$, ki je generirana z $\alpha$, potem Anita izbere naključno naravno število $k$, ki je manjše od števila elementov v grupi $G$, ter z njim in Bojanovim javnim ključem $\beta=\alpha^b$ izračuna par $(\alpha^k,m\beta^k)$ ter ga pošlje Bojanu. Opiši odšifrirno funkcijo.

Bojan je dobil par števil $(\gamma, \delta)$, kjer je $\gamma = \alpha^k$ in $\delta = m \beta^k$. On pozna svoj zasebni ključ $b$, ne pozna pa vrednosti $k$. Bojan odšifrira sporočilo tako, da izračuna $m = \gamma^{-b} \cdot \delta$, ker $\gamma^{-b} \cdot \delta = \alpha^{-bk} \cdot m \beta^k = \beta^{-k} \cdot m \beta^k = m$.

Prepričaj se, da je opisano preverjanje Elgamalovega podpisa pravilno. (Namig: pomagaj si s Fermatovim izrekom, da bo jasno, zakaj računamo $\delta$ po modulu $p-1$.)

Torej, želimo pokazati, da če je podpis pravilno narejen, potem velja $\ \beta^{\gamma} \gamma^{\delta} \equiv \alpha^x \pmod{p}$. Da to dosežeš, moraš vsakič izbrati pravilno možnosti v stolpcu.

Podpisovalec ni bil pazljiv in je ponesreči izgubil naključno število $k$, ki ga je uporabil pri Elgamalovem podpisu. Uporabi njegovo napako za izračun zasebnega ključa $a$.

Poznamo podpisovalčev javni ključ $\left(p, \alpha, \beta \right)$, sporočilo $x$ in pripadajoči podpis $\left( \gamma, \delta \right)$. Poleg tega poznamo še naključno vrednost $k$, ki je bila uporabljena pri izračunu podpisa. Podpisovalčev zasebni ključ $a$ lahko izračunamo iz enačbe $$\delta \equiv \left(x - a \gamma\right) k^{-1} \pmod{p-1},$$ ker poznamo vse ostale vrednosti. Za to moramo izraziti vrednost $a$ $$\delta k \equiv x - a \gamma \pmod{p-1},$$ $$a \gamma \equiv x - \delta k \pmod{p-1},$$ $$a \equiv \left(x - \delta k\right) \gamma^{-1} \pmod{p-1}.$$ Vrednost $\gamma^{-1}$ pomeni inverz po modulu $p-1$. Izračunamo jo z uporabo razširjenega Evklidovega algoritma. Problem nastane v primeru, ko je $\textrm{gcd}\left(\gamma, p-1\right) \neq 1$, kar pomeni, da inverz $\gamma^{-1}$ ne obstaja in zasebnega ključa $a$ ne moremo izračunati na opisan način.

Generator naključnih števil je tako počasen, da se je podpisovalec odločil uporabiti število $k$ dvakrat. Ali lahko uporabiš njegovo napako za izračun zasebnega ključa $a$?

Poznamo napadalčev javni ključ $\left(p, \alpha, \beta \right)$, sporočili $x_1$ in $x_2$ ter njuna podpisa $\left( \gamma, \delta_1 \right)$ in $\left( \gamma, \delta_2 \right)$. Ker je naključna vrednost $k$ enaka za oba podpisa, je tudi vrednost $\gamma$ enaka. Podpisovalčev zasebni ključ $a$ lahko izračunamo iz enačb $$ \delta_1 \equiv \left(x_1 - a \gamma\right) k^{-1} \pmod{p-1} \quad\textrm{in}\quad \delta_2 \equiv \left(x_2 - a \gamma\right) k^{-1} \pmod{p-1}, $$ ker ne poznamo le vrednosti $a$ in $k$. Iz obeh enačb lahko izrazimo člen $a\gamma$ in dobimo $$ a \gamma \equiv x_1 - \delta_1 k \pmod{p-1} \quad\textrm{in}\quad a \gamma \equiv x_2 - \delta_2 k \pmod{p-1}. $$ To pomeni, da velja $$ x_1 - \delta_1 k \equiv x_2 - \delta_2 k \pmod{p-1}. $$ Zdaj lahko izrazimo $k$ $$ k \equiv \left(x_1 - x_2\right) \left(\delta_1 - \delta_2\right)^{-1} \pmod{p-1}. $$ Da obstaja inverz, mora veljati $\textrm{gcd}\left(\delta_1 - \delta_2, p-1\right) = 1$. Ko izračunamo $k$, lahko izračunamo podpisovalčev zasebni ključ $a$ z rešitvijo prejšnje naloge.

(*) Predlagaj novo varianto Elgamalovega podpisa, kjer ne bomo več potrebovali računanja inverza ($k^{-1}$), ki ga ponavadi izračunamo z razširjenim Evklidovim algoritmom.

Hkratno računanje vrednosti $x$, $\gamma$ in $\delta$: naj bosta $i$ in $j$ takšni števili, da velja \\ $0\le i,j \le p-2$ in $D(j, p-1) = 1$. Prepričaj se, da potem števila $$ \gamma \equiv \alpha^i \beta^j \!\!\pmod{p}, \ \ \ \ \ \delta \equiv - \gamma j^{-1} \!\!\pmod{p-1}\ \ \ {\rm in} \ \ \ x \equiv - \gamma i j^{-1} \!\!\pmod{p-1} $$ zadoščajo enačbi za preverjanje Elgamalovega podpisa: $\beta^{\gamma} \gamma^{\delta} \equiv \alpha^x \pmod{p}$.\\[-5mm]

(*) Ali lahko pri veljavnem podpisu $(\gamma,\delta)$ za $x$ najdemo še kakšen podpis za kakšno drugo sporočilo $x'$?
(Postaviti na konec.) Odg. je "DA". Naj bodo $h,i$ in $j$ takšna števila, da velja $0 \le h,i,j \le p-2$ in $D(h \gamma - j \delta, p-1) = 1$. Potem se prepričaj, da je par $(\lambda, \mu)$ veljaven podpis za $x'$, kjer je $$ \lambda =\ \gamma^h \alpha^i \beta^j \ \mod p, \ \ \mu =\ \delta \lambda (h \gamma -j \delta)^{-1}\ \mod p-1 {\ \ \rm in}\ \ x' =\ \lambda (hx+i\delta)(h\gamma-j\delta)^{-1}\ \mod p-1. $$ V drugem razdelku je v tretji točki "ČE", zaradi katerega še nismo povsem rešili problema identifikacije Bojana. Ta se je le prenesla na prepoznavanje Bojanovega javnega ključa. Če se morata Anita in Bojan prej sestati, da bi si izmenjala javna ključa, potem bi se lahko ob tej priložnosti dogovorila za skupen ključ za kakšno simetrično šifro. Več o tem, kako lahko s certifikati in z infrastrukturo javnih klju"cev rešimo ta problem, pa v zadnjem (5.) delu.