1. 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 nakjluč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.
  2. Kakšne lastnosti naj ima zgoščevalna funkcija, da ne bo ogrožena varnost podpisa?
  3. 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.
  4. 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.
  5. 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.
  6. 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$.
  7. 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$?
  8. (*) 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.
  9. 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]
  10. (*) 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.