7 O problema de criptologie
Alice si Bob doresc sa comunice anumite secrete prin telefon. Convorbirea telefonica
poate fi insa ascultata si de Eva. In prealabil, Alice si Bob nu au stabilit
nici un protocol de codificare si pot face acum acest lucru doar prin telefon.
Eva va asculta insa si ea modul de codificare. Problema este cum sa comunice
Alice si Bob, astfel incat Eva sa nu poata descifra codul, cu toate ca va cunoaste
si ea protocolul de codificare[**]
.
Pentru inceput, Alice si Bob convin in mod
deschis asupra unui intreg p cu
cateva sute de cifre si asupra unui alt intreg g intre 2 si p-1. Securitatea
secretului nu este compromisa prin faptul ca Eva afla aceste numere.
La pasul doi, Alice si Bob aleg la intimplare
cate un intreg A, respectiv B, mai mici decat p, fara sa-si comunice aceste numere. Apoi, Alice calculeaza a = gA mod p si transmite rezultatul lui Bob; similar, Bob transmite lui Alice
valoarea b = gB mod p. In final, Alice calculeaza x = bA mod p, iar Bob calculeaza y = aB mod p. Vor ajunge la acelasi rezultat,
deoarece x = y = gAB mod p. Aceasta valoare este deci cunoscuta de Alice si Bob, dar ramane
necunoscuta lui Eva. Evident, nici Alice si nici Bob nu pot controla direct
care va fi aceasta valoare. Deci ei nu pot folosi acest protocol pentru a
schimba in mod direct un anumit mesaj. Valoarea rezultata poate fi insa cheia
unui sistem criptografic conventional.
Interceptand convorbirea telefonica, Eva va
putea cunoaste in final urmatoarele numere: p,
q, a si b. Pentru a-l
deduce pe x, ea trebuie sa gaseasca
un intreg A‘, astfel incat a = gA‘ mod p si sa
procedeze apoi ca Alice pentru a-l calcula pe x‘ = bA‘ mod p. Se poate arata (Exercitiul 7.21)
ca x‘ = x, deci ca Eva poate calcula astfel
corect secretul lui Alice si Bob.
Calcularea lui A‘ din p, g si a
este cunoscuta ca problema logaritmului
discret si poate fi realizata de urmatorul algoritm.
function dlog(g, a, p)
A
0; k 1
repeat
A A+1
k kg
until
(a = k mod p) or
(A = p)
return
A
Daca logaritmul nu exista, functia dlog va returna valoarea p. De exemplu, nu exista un intreg A, astfel incat 3 = 2A mod 7.
Algoritmul de mai sus este insa extrem de ineficient. Daca p este un numar prim impar, atunci este nevoie in medie de p/2 repetari ale buclei repeat pentru a ajunge la solutie
(presupunand ca aceasta exista). Daca pentru efecuarea unei bucle este necesara
o microsecunda, atunci timpul de executie al algoritmului poate fi mai mare
decat varsta Pamantului! Iar aceasta se intampla chiar si pentru un numar
zecimal p cu doar 24 de cifre.
Cu toate ca exista si algoritmi mai rapizi
pentru calcularea logaritmilor discreti, nici unul nu este suficient de
eficient daca p este un numar prim cu
cateva sute de cifre. Pe de alta parte, nu se cunoaste pana in prezent un alt
mod de a-l obtine pe x din p, g,
a si b, decat prin calcularea logaritmului discret.
Desigur, Alice si Bob trebuie sa poata
calcula rapid exponentierile de forma a = gA mod p, caci altfel ar fi si ei pusi in
situatia Evei. Urmatorul algoritm pentru calcularea exponentierii nu este cu
nimic mai subtil sau eficient decat cel pentru logaritmul discret.
function dexpo1(g, A,
p)
a
1
for i 1 to A do
a ag
return
a mod p
Faptul ca x y z mod p = ((x y mod p) z) mod p pentru orice x, y, z si p,
ne permite sa evitam memorarea unor numere extrem de mari. Obtinem astfel o
prima imbunatatire:
function dexpo2(g, A,
p)
a
1
for i 1 to A do
a ag mod p
return a
Din fericire pentru Alice si Bob, exista un
algoritm eficient pentru calcularea exponentierii si care foloseste
reprezentarea binara a lui A. Sa
consideram pentru inceput urmatorul exemplu
x25 = (((x2x)2 )2 )2x
L-am obtinut deci pe x25 prin doar doua inmultiri si patru
ridicari la patrat. Daca in expresia
x25 = (((x2x)21)21)2x
inlocuim fiecare x cu un 1 si fiecare 1 cu un 0, obtinem secventa 11001, adica
reprezentarea binara a lui 25. Formula precedenta pentru x25 are aceasta forma, deoarece x25 = x24x, x24 = (x12 )2 etc. Rezulta un algoritm divide et
impera in care se testeaza in mod recursiv daca exponentul curent este par sau
impar.
function dexpo(g, A,
p)
if
A = 0 then return 1
if
A este impar then a dexpo(g, A-1, p)
return (ag mod p)
else a
dexpo(g, A/2, p)
return (aa mod p)
Fie h(A) numarul de inmultiri modulo p efectuate atunci cand se calculeaza dexpo(g, A, p), inclusiv ridicarea la patrat.
Atunci,
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_10.gif" v:shapes="_x0000_i1034">
Daca M(p) este limita superioara a timpului
necesar inmultirii modulo p a doua
numere naturale mai mici decat p,
atunci calcularea lui dexpo(g, A, p) necesita un
timp in O(M(p) h(A)).
Mai mult, se poate demonstra ca timpul este in O(M(p) log A), ceea
ce este rezonabil. Ca si in cazul cautarii binare, algoritmul dexpo este mai curand un exemplu de
simplificare decat de tehnica divide et impera.
Vom intelege mai bine acest algoritm, daca
consideram si o versiune iterativa a lui.
function dexpoiter1(g, A,
p)
c
0; a 1
{fie
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_11.gif" v:shapes="_x0000_i1035">reprezentarea
binara a lui A}
for i k downto
0 do
c 2c
a aa
mod p
if Ai = 1 then c c + 1
a ag
mod p
return
a
Fiecare iteratie foloseste una din
identitatile
g2c mod p = (gc )2 mod p
g2c+1 mod p = g(gc )2 mod p
in functie de valoarea lui Ai (daca este 0, respectiv
1). La sfarsitul pasului i, valoarea lui c, in reprezentare binara,
este
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_12.gif" v:shapes="_x0000_i1036"> . Reprezentrea
binara a lui A este parcursa de la stanga spre dreapta, invers ca la
algoritmul dexpo. Variabila c a fost introdusa doar pentru a intelege
mai bine cum functioneaza algoritmul si putem, desigur, sa o eliminam.
Daca parcurgem reprezentarea binara a lui A de la dreapta spre stanga, obtinem un
alt algoritm iterativ la fel de interesant.
function dexpoiter2(g, A,
p)
n A; y
g; a 1
while
n > 0 do
if n este impar then a ay
mod p
y yy
mod p
n n
div 2
return
a
Pentru a compara acesti trei algoritmi, vom
considera urmatorul exemplu. Algoritmul dexpo
il calculeaza pe x15 sub forma
(((1 x)2x)2x)2x, cu sapte inmultiri;
algoritmul dexpoiter1 sub forma (((12x)2x)2x)2x, cu opt inmultiri; iar dexpoiter2 sub forma 1 x x2x4x8, tot cu opt inmultiri (ultima din
acestea fiind pentru calcularea inutila a lui x16).
Se poate observa ca nici unul din acesti
algoritmi nu minimizeaza numarul de inmultiri efectuate. De exemplu, x15 poate fi obtinut prin sase inmultiri,
sub forma ((x2x)2x)2x. Mai mult, x15 poate fi obtinut prin doar cinci inmultiri
(Exercitiul 7.22).
