Alti Algoritmi cu Cheie
Publica
Cu toate ca RSA este larg raspandit, nu este in
nici un caz singurul algoritm cu cheie cunoscut. Primul algoritm cu cheie
publica a fost algoritmul rucsacului (Merkle si Hellmann, 1978).
Ideea este ca cineva poseda un numar mare de obiecte, fiecare cu
greutate diferita. Posesorul codifica mesajul prin selectia
secreta a unei submultimi de obiecte si plasarea lor in rucsac.
Greutatea totala a obiectelor din rucsac este facuta
publica, ca si lista tuturor obiectelor posibile. Lista obiectelor
din rucsac este tinuta secreta. Cu cateva restrictii
suplimentare, problema gasirii unei liste de obiecte cu greutatea
data a fost gandita ca fiind imposibil de calculat si
formeaza baza pentru algoritmul cu cheie publica.
Inventatorul algoritmului, Ralph Merkle, a fost aproape
sigur ca acest algoritm nu poate fi spart, astfel ca el a oferit o
recompensa de 100 de dolari oricui il va putea sparge. Adi Shamir ("S"-ul
din RSA) l-a spart cu promptitudine si a primit recompensa. Fara
a-si pierde curajul Merkle si-a intarit algoritmul si a
oferit o recompensa de 1 000 de dolari oricui va putea sparge noul
algoritm. Ron Rivest ("R' -ul din RSA) l-a spart cu promptitudine si a
luat banii. Merkle nu a indraznit sa ofere 10000 de dolari pentru
urmatoarea versiune, astfel ca "A" (Leonard Adelman) nu a avut noroc.
Cu toate ca a fost corectat si imbunatatit din nou,
algoritmul rucsacului nu este considerat sigur si este rareori utilizat.
Alte scheme cu cheie publica sunt bazate pe dificultatea calculului
logaritmilor discreti (Rabin, 1979). Algoritmii care folosesc acest
principiu au fost inventati de El Gamal (1985) si Schnorr (1991).
Exista cateva alte scheme, cum ar fi cele bazate pe
curbe eliptice (Menezes si Vanstone, 1993) dar cele trei categorii majore
sunt cele bazate pe dificultatea factorizarii numerelor mari, a calcului
logaritmilor discreti si a determinarii continutului unui
rucsac din greutatea sa. Aceste probleme sunt considerate ca fiind autentic
dificile deoarece matematicienii le studiaza de multi ani
fara vreun progres notabil.
