resursĂ educaȚionalĂ deschisĂƒ_aurel... · descompunerea lui n e uşor de calculat i n. dacă...
TRANSCRIPT
1
RESURSĂ EDUCAȚIONALĂ DESCHISĂ
Denumire: MATEMATICĂ APLICATĂ ÎN INFORMATICĂ- CRIPTARE
Autor: CHIRIȚĂ AUREL
Unitatea de învățămînt :Colegiul Național Ion Minulescu Slatina
Disciplina: Matematică
Clasa :Liceu
Scopul materialului propus :documentare pentru cadrele didactice
2
CHIRIŢĂ ION ALEXANDRU CHIRIŢĂ AUREL
MATEMATICĂ APLICATĂ ÎN INFORMATICĂ
CRIPTOGRAFIE-APLICAŢII
Slatina 2018
3
Cuvînt înainte.
Lucrarea de faţă se adresează eleviilor de clasa 12 profilul matematică –
informatică şi matematică-informatică-intensiv, studenţilor de la facultăţiile
matematica-informatică, automatică, electronică şi calculatoare cât şi celor care
se ocupă de sistemele de protecţie în domeniul calculatoarelor fie protecţia
informaţiei, secrete bancare, sistemelor de informaţii diplomatice şi militare.
Lucrarea se vrea a fi o continuitate a cunoştiinţelor fundamentale dobîndite în
clasa 12, la orele de algebră elementară şi informatică trecute din abstract în
mod practic ( aplicaţiile informatice).Teoria grupurilor se dovedeşte a fi un teren
fertil pentru fixarea cunoştiinţelor în domeniul informaticii . Avem nevoie şi de
clase de resturi modulo m , cât şi de proprietăţile lor. Vom folosi şi cunoştiinţe
legate de teoria numerelor prime regăsite în pZ , cu p prim. Lucrarea de faţă
conţine numeroase aplicaţii concrete rezolvate tocmai pentru a uşura întelegerea
noţiunilor. Această carte constituie un curs opţional pentru clasa a-12 profilul
informatică şi informatică-intensiv. În definitiv acesta este unul dintre scopurile
pentru care a fost concepută această carte.
Autorii.
4
Cuprins
1. Elemente de criptografie.
-Securitatea informaţiei..................................................................
-Clasificarea atacurilor...................................................................
-Securitatea reţlelor locale pentru calculatoarele individuale........
-Nivel de securitate.........................................................................
-Securitate fizică.............................................................................
-Nivelurile logice de securitate.Sisteme paralele............................
-Cifrarea..........................................................................................
2. Complemente de algebra necesare
-Elemente de teoria numerelor.Numere prime……………………
-Congruenţa de întregi....................................................................
-Clase de resturi modulo m.............................................................
-Teorema Fundamentală a aritimetici.............................................
-Teorema lui Euler..........................................................................
-Mica Teoremă a lui Fermat. Teorema Euler.Grup ciclic...............
3. Criptografia cu cheie publică
-Public sau non-public.Trapdoor....................................................
-Sistemul de criptare RSA.Numere prime.......................................
-Funcţia Totient a lui Euler………………………………………..
-Teoria numerelor.Cum lucrează RSA……………………………
-Operaţii cu numere……………………………………………….
-Atacuri prin temporizare………………………………………….
-Algoritmul lui Euclid……………………………………………..
-Atacuri prin factorizare…………………………………………...
-Teorema restului chinezesc……………………………………….
-Generarea de numere prime pentru criptarea RSA……………….
-Congruenţe.
4. Sistemul El Gamal -Clase de grupuri…………………………………………………..
-Sistemul de criptare EL Gamal.......................................................
-Sistemul de criptare RSA................................................................
-Exemplu...........................................................................................
-Algoritmul El Gamal.......................................................................
-Criptare............................................................................................
-Weierstrass Ecuation.......................................................................
5
5. Curbe eliptice
-Ecuaţii liniare....................................................................................
-Exemple.............................................................................................
-Ecuaţii Conice...................................................................................
-Teorema Legendre.............................................................................
-Ecuaţii Cubice....................................................................................
-Nume curbă eliptică............................................................................
-Evitarea singularităţilor......................................................................
6. Curbe eliptice peste pZ .
-Proprietăţi...........................................................................................
-Sisteme de criptare u curbe eliptice…………………………………
-Factorizare Grupuri Primalitate……………………………………..
-Puncte pe curbe eliptice……………………………………………..
-Exemple de curbe eliptice…………………………………………...
-Dublarea unui punct…………………………………………………
-Punctul de la infinit………………………………………………….
-Singularitate………………………………………………………….
-Aplicaţii………………………………………………………………
7. Criptosistemele cu cheie publică
-Pohlig-Hellman……………………………………………………….
-Metoda Index Calculus……………………………………………….
-Schimbarea cheii de acces Diffie-Hellman…………………………...
-Utilităţile(CCE)……………………………………………………….
-Criptare pe curbe eliptice.......................................................................
8. Logaritmul discret
-Algoritmul Shanks…………………………………………………….
-Reprezentări............................................................................................
-Logaritmi discreţi în *
11Z .......................................................................
-Atacuri la logaritmii discreţi...................................................................
-Logaritmii discreţi în *
pZ.......................................................................
-Algoritmul lui Schank.............................................................................
6
1. COMPLEMENTE DE MATEMATICĂ
Elemente de teoria numerelor
Numere prime
Dacă r, s şi t sunt numere întregi şi dacă
(1)
se spune că t se divide la r sau că r este divizorul lui t. Numărul întreg p (p>1),
care se divide numai la +1 şi la p se numeşte număr prim.
Cel mai mare divizor comun (c.m.m.d.c.) a două numere întregi este cel mai
mare număr întreg care divide ambele numere.
Două numere sunt prime între ele dacă cel mai mare divizor comun al lor este
1.
Pentru orice pereche de numere întregi s şi d, există o pereche de numere întregi,
q şi r, unde q este câtul, iar r este restul, astfel că:
(2)
Această afirmaţie este teorema împărţirii cu rest. O consecinţă a teoremei este
algoritmul lui Euclid. Cu ajutorul lui se demonstrează faptul că orice număr
întreg se poate reprezenta în mod unic sub forma unui produs de puteri de
numere prime.
Cel mai mare divizor comun a două numere întregi r şi s se poate pune sub
forma:
(3)
a, b fiind numere întregi.
7
De exemplu, cel mai mare divizor comun al numerelor 120 şi 56 poate fi găsit
astfel:
08756
8562120
(1)
Cel mai mare divizor comun al celor două numere date este d = 8.
Acest rezultat permite să se scrie 8 (c.m.m.d.c.) sub forma
Error! Reference source not found.), pag. Error! Bookmark not defined.:
562-1201
5621208
(2)
Congruenţe de întregi
Două numere întregi a şi b se numesc congruențe modulo m, dacă numărul
întreg m divide pe a - b, adică dacă:
m|a-b (3)
Numărul întreg m se numeşte modulul relaţiei de congruenţă. În loc de m|a-b se
scrie:
(7)
şi se citeşte a este congruent cu b modulo m. Dacă b = r, în care r este restul
împărţirii lui a la m, rezultă:
(8)
În acest caz r se numeşte restul lui a în raport cu modulul m, se mai spune că a
este egal cu r modulo m.
8
Pentru m = 2 orice număr întreg este congruent cu 0 sau cu 1 modulo 2. Orice
valoare ar avea întregul a, relaţiile Error! Reference source not found.), pag. Error!
Bookmark not defined.) se pot scrie sub forma:
sau (9)
Pentru m = 3 orice număr este congruent cu 0, cu 1 sau cu 2, adică indiferent
care ar fi numărul întreg a, avem:
(10)
Adică orice număr împărţit la 3 are ca rest fie 0, fie 1, fie 2.
În cazul general m, orice întreg este congruent cu unul din numerele 0, 1, 2, …,
m - 1.
Congruenţele faţă de acelaşi se adună membru cu membru:
(4)
şi
(5)
atunci
(6)
În cazul când m = 2, congruenţa a b va fi:
(14)
9
Acest rezultat se poate scrie într-o tabelă numită tabla adunării mod 2:
0 1
0 0 1
1 1 0
Tabelul 1. Tabla adunării modulo 2
Analog se poate arăta cu ce este egal a b(mod 3). Rezultă tabla adunării mod
3:
0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
Tabelul 2. Tabla adunării modulo 3.
Dacă și , atunci:
(15)
adică congruenţele se înmulţesc membru cu membru.
Pentru m = 2 rezultatul se obţine astfel:
(16)
10
Rezultă tabelul următor, numit tabla înmulţirii modulo 2:
0 1
0 0 0
1 0 1
Tabelul 3. Tabla înmulţirii modulo 2.
Analog se poate arăta cu ce este egal a b( mod 3). Rezultă tabla înmulţirii
mod 3:
0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
Tabelul 4. Tabla înmulţirii modulo 3.
Clase de resturi modulo m
Mulţimea numerelor întregi congruente cu i mod m, formează o clasă de
echivalenţe, numită clasă de resturi. Orice număr întreg, împărţit la m, va avea
un rest în mulţimea: { 0, 1, 2, … ,m -1 }. Deci pot exista cel mult m clase de
resturi mod m, notate:
{0}, {1}, {2}, … ,{m-1} (7)
De exemplu, pentru m = 3 se formează următoarele 3 clase de resturi:
{0} = {0, 3, 6, 9, … ,3n}
{1} = {1, 4, 7, 10, … ,3n+1} (8)
{2} = {2, 5, 8, 11, … ,3n+2}
Deci clasa {i} este mulţimea numerelor care împărţite la modul dau rest i.
Referitor la mulţimea claselor de resturi mod m, se definește suma şi produsul a
două clase de resturi astfel:
11
{a} + {b} = {c}, unde c = a + b ( mod m)
{a} {b} = {c}, unde c = a b ( mod m) (9)
Algoritmii cu cheie publică sunt folosiţi pentru schimbul cheilor simetrice.
1.Cheile publice sunt importante chei de criptare.
2.Cheile simetrice sunt chei de criptare a datelor.
Numere prime.
Un număr natural p ≥ 2 e prim dacă 1 şi p sunt singurii lui divizori pozitivi.
Teoremă.(Fundamentală a aritimetici).
Fiecare număr natural n ≥ 2 se descompune ca un produs de numere prime la
diferite puteri de numere naturale pozitive.
Numere relativ prime .
Fiind date numerele a şi b ele sunt relativ prime dacă cel mai mare divizor
comun al lor este 1. Numerele a şi b nu au factori comuni.
Teorema lui Euler.
n numără elementele din mulţimea 1,2,3,... 1n prime cu n. Fiind dată
descompunerea lui n e uşor de calculat .n Dacă n e prim atunci n = n -1.
Pentru numerele distincte prime p şi q, avem 1 1 .p q n p
Numerele modulo n , nZ .
Fie n pozitiv, avem 0,1,2,3... 1nZ n care constituie echivalentul claselor
modulo n.
Fie ,na Z inversul lui a modulo n în raport cu înmulţirea e unicul nx Z ,
astfel încât . Acest x dacă există atunci c.m.m.d.c. alui a şi n este
1. Putem defini grupul *
nZ astfel.
* / , 1n nZ a Z a n
12
1. Lui *
nZ i se adaugă operaţia de înmulţire.
2. Cardinalul lui *
nZ este n
3. Pentru n prim * 1,2,3... 1 .nZ n
Mica teoremă a lui Fermat.
Dacă p este prim şi , 1a p atunci 1 1 modpa p
Teorema lui Euler.
Dacă , 1a n atunci 1 mod .n
a n
Generalizare.
Dacă modx y n atunci mod .x ya a n
Grupuri ciclice.
Fie *
na Z ,ordinul lui a este cel mai mic număr pozitiv t astfel încât
1 mod .ta n
Dacă g are ordinul n atunci Z este ciclic şi g este generatorul elementului
fundamental în *.nZ
*
nZ e ciclic dacă 2,4,... ,...2k kn p p pentru numere prime p.
Logaritmul discret al lui b în baza g este x astfel încât :
mod .xg b n
Este un algoritm eficient pentru calcularea înregistrărilor în *
nZ dacă 1p are
factori primi.
Exp . *
5Z ,care arată mod5x y
* 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1
13
Cardinalul lui * 5 4nZ . Inversurile lui 1 1 12 3;3 2;4 4 . Generatorii
sunt 2,3,4.
Obs: 4 4 42 1;3 4 1
În *
5Z înregistrarea lui 4 în baza 3 şi 2.
Exp: *
15Z
1 2 4 7 8 11 13 14
1 1 2 4 7 8 11 13 14
2 2 4 8 14 1 7 11 13
4 4 8 1 13 2 14 7 11
7 7 14 13 4 11 2 1 8
8 8 1 2 11 4 13 14 7
11 11 7 14 2 13 1 8 4
13 13 11 7 1 14 8 4 2
14 14 13 11 8 7 4 2 1
*
15 15 3 1 5 1 8Z
Acest grup nu este ciclic.
14
2. CRIPTOGRAFIA CU CHEIE PUBLICĂ
Public sau non-public.
Spre deosebire de criptografia cu cheie privată, criptografia cu cheie publică nu
necesită un schimb de chei. În loc de asta, există un “număr de telefon” public,
disponibil oricărui utilizator și o cheie
TRAPDOOR
Criptografia cu cheie publică (PKC – Public Key Cryptography) se bazează pe
ideea unei funcții trapdoor f: X → Y, adică o funcție biunivocă, ușor de calculat,
publică, cu inversa greu de calculat și cu inversa ușor de calculat dacă este
cunoscută trapdoor.
Astfel, deși în criptografia convențională este necesar un schimb prealabil de
chei, în criptografia cu cheie publică nu este necesar un asemenea schimb.
Ideea de PKC a fost propusă prima oară de Diffie și Hellman în 1976. Iată cele
câteva PKC-uri importante care vor fi studiate mai departe.
· RSA;
· Rabin;
· Merkle-Hellman;
· McEliece;
· ElGamal;
· Elliptic Curve;
SISTEMUL DE CRIPTARE RSA
n, p, q: Se definește n = pq cu p și q două numere prime mari.
d, e: gcd(e, (n)) = 1 și ed ≡ 1 mod (n)
15
M: M este numărul care reprezintă mesajul de criptat.
C: C este numărul care reprezintă textul cifrat (textul criptat).
Informație publică: n, e.
Informație privată: d.
NUMERE PRIME
Un întreg n > 1 este prim dacă numerele 1 și n sunt singurii lui divizori.
Euclid: Există o infinitate de numere prime.
Dacă p1 < p2 < … < pn sunt primele n numere prime, atunci orice divizor prim
al întregului 1 + p1p2 … pn trebuie să fie mai mare decât pn.
Numărul (n) de numere prime mai mici sau egale cu n este asimptotic egal cu
. Mai general,
Dirichlet-Hadamard-de la Vallé Poussin: Dacă gcd(a, b) = 1 atunci numărul
a,b(n) al numerelor prime p ≤ n de forma p = ak + b este asimptotic egal cu (1/
(a))∙(
).
Postulatul lui Bertrand: Pentru orice întreg n, există un număr prim
între n + 1 și 2n. Erdos a dat o demonstrație elementară elegantă. Ce se observă
dacă se scriu întregi consecutivi într-o spirală rulată în sens anterior ?
Numerele prime se aliniază pe diagonale. Se poate dovedi sau nu această
observatie? Se poate experimenta.
Care este raportul primelor de forma n2 + n + 17? Dar între cele de forma n
2 + n
+ 41? Probleme dificile. Nici un polinom de o singură variabilă cu coeficienții
întregi nu poate genera toate numerele prime ( în legătură cu problema a zecea a
lui Hilbert).
16
FUNCȚIA TOTIENT A LUI EULER
(n) este numărul de întregi nenegativi mai mici decât n care sunt relativ primi
cu n.
Câteva valori importante ale lui (n):
TEORIA NUMERELOR
Exemplul 1: Este ușor de generat e astfel încât gcd(e, (n)) = 1 deoarece
|{e < n: gcd(e, (n)) = 1}| = ( (n))
Exemplul 2: Fie p = 101, q = 113, n = 11413. Atunci (n) = (p – 1)(q – 1) =
11200 = 26527.
Astfel, orice întreg care nu este divizibil cu 2, 5, 7 poate fi utilizat ca fiind o
cheie publică. Se poate alege e = 3533. Folosind algoritmul lui Euclid, se poate
calcula ușor e-1
mod 11200 = 6597.
17
Exemplul 3: Fie p = 5, q = 7, n = 35. Se poate alege e = 11. Cum se calculează
1211
mod 35?
Mai multe concepte din teoria numerelor vor fi rememorate aici.
CUM LUCREAZĂ RSA?
Criptarea RSA: M → E(M) := M e ≡ C mod n.
Decriptarea RSA: C → D(C) := C d ≡ M mod n.
Când si de ce lucrează? De rememorat că (n) = (p – 1)(q – 1). Pentru ca RSA
să lucreze M < n, gcd(e, (p – 1)(q – 1)) = 1, p și q sunt prime și de ≡ 1 mod (p –
1)(q – 1).
RSA lucrează deoarece: Cd ≡ (M
e)
d ≡ M
ed .mod111 nM qp
Se admite că gcd(M, q) = gcd(M, p) = 1. Atunci conform micii teoreme a lui
Fermat:
Cd ≡ M(M
p-1)
k(q-1) ≡ M(1)
k(p-1) ≡ M mod p
Cd≡ M(M
q-1)
k(p-1) ≡ M(1)
k(p-1) ≡ M mod q
Astfel, Cd ≡ M mod n.
REPREZENTĂRI ALE NUMERELOR
Reprezentări în baza b.
ii
k
k
k
k
k
k
k
k
abb
n
ababababb
n
amabababn
mod
..............................................................................
mod...mod
mod...mod
11
1
2
1
1
00
1
1
Folosind acest fapt se poate scrie un algoritm de schimbare a reprezentării
unui număr in orice bază
18
Procedure scriere_în_baza_b (n, b)
q := n
k := 0
while q ≠ 0
ak := q mod b
1:
:
kk
b
end while
return bkkk aaaaa 0121 ...
OPERAȚII CU NUMERE
Adunarea a două numere de k biți se poate executa într-un timp O(k).
010110101
11010010
---------
110000111
Multiplicarea a două numere de k biți se poate executa într-un timp O(k2).
1011
110
--------
0000
1011
1011
--------
1000010
Ambii algoritmi sunt binecunoscuți. Există desigur algoritmi mai rapizi (v.
Knuth: “Art of Computer Programming”).
Exponențierea a două numere de k biți se poate face într-un timp O(k3).
Exemplu: p = 5, q = 7, n = 35.
Exponențierea a două numere de k biți se poate face într-un timp O(k3).
Exemplu: p = 5, q = 7, n = 35.
Se poate alege e = 11. Fie mesajul M = 12. Pentru a calcula 1211
mod 35:
Se scrie mai întâi (11)10 = (1011)2. Apoi se calculează
19
MMMMMMMMMM222
22
20212
2120212121202111 010120123
Algoritmul formal este următorul: se calculează reprezentarea binară
ecukeeni
i
i
i 2
0
log2
și se execută următoarea procedură:
Procedure exponentiere (x, e, n)
z := 1
for i := k – 1 downto 0 do
z := z2 mod n
if ei = 1 then z := z∙x mod n
return xe mod n
ATACUL PRIN TEMPORIZARE
Acest atac este similar celui prin care un pungaș observă cât timp îi ia cuiva
pentru a forma la disc cifrul unui seif. Genul acesta de atac se poate aplica și
altor sisteme cu criptare.
Un analist criptolog poate calcula o cheie privată prin urmărirea pas cu pas a
duratei necesare unui calculator pentru a descifra un mesaj. Exponentul este
calculat bit cu bit începând cu bitul cel mai puțin semnificativ.
Pentru un text cifrat dat este posibil a măsura cât timp este necesar pentru a
executa exponențierea modulară. Se pot așadar determina biții necunoscuți prin
exploatarea diferențelor de timp în răspuns (acest atac a fost implementat de
Koeher în 1996).
Problema este eliminată prin utilizarea unuia dintre următoarele remedii: (a)
timp de exponențiere constant, (b) întârzieri aleatoare sau (c) “orbirea” prin
multiplicarea textului cifrat cu un număr aleator înainte de exponențiere.
20
ALGORITMUL LUI EUCLID
Aflarea gcd(a, b) fără factorizarea numerelor a și b utilizează algoritmul lui
Euclid. Fără a pierde din generalitate se presupune a > b.
Lemă: Fie a = bq + r cu a, b, q și r numere întregi, r < b. Atunci gcd(a, b) =
gcd(b, r).
Demonstrație: Fiind date condițiile din enunț, dacă d este un număr care divide
atât pe a cât și pe b, atunci d|(a – bq). Deoarece (a – bq) = r atunci d|r. Așadar,
orice divizor al numerelor a și b divide și pe r. Aceasta implică gcd(a, b) =
gcd(b, r). Deoarece r = a – bq, rezultă r = a mod b. Se iterează (r0 = a, r1 = b, r2
= r, q1 = q):
12211
233221
122110
0
........................................
0
0
iiiiii rrcurrqr
rrcurrqr
rrcurrqr
Se definește gcd(x, 0) = x. Se observă că secvența r0 > r1 > … > rn este
descrescătoare. Deoarece există un termen rn astfel încât rn + 1 = 0 și gcd(rn, 0)
= rn, rezultă gcd(a, b) = rn.
Fie fn al n-lea număr Fibonacci. De rememorat: f0 = f1 = 1, fn = fn-1 + fn-2.
Rezolvând această ecuație cu diferențe (prin aprecierea că fn = Rn, pentru un
amumit R) se obține fn = ((1+ 5) / 2)n.
Frumusețea și media de aur: Dreptunghiul este “cel mai plăcut estetic” când
prin tăiere, portiunea rămasă este asemenea cu dreptunghiul initial! (Construirea
Parthenonului a utilizat acest principiu!).
Dreptunghiul mare are dimensiunile a×b. Dreptunghiul mic are dimensiunile a
× (a – b). Asemănarea cere ca
21
.1
1;
RR
ba
b
b
aR
Prin tratarea ultimei egalități ca o ecuație, se obține R = (1+ 5) / 2 .Prin inducție
se poate dovedi că rn-i ≥ fi. Pasul de început, pentru i = 0 este facil.
Apoi
rn-(i+1) = qn-i∙rn-i + rn+1-i ≥ rn-i + rn+1-i ≥ fi + fi-1 = fi+1
Rezultă că a = r0 ≥ fn și n = O( loga ).
Procedure gcd(a, b; întregi pozitivi)
x := a;
y := b;
while y ≠ 0 do
r := x mod y
x := y
y := r
end while
return x
Teoremă: Dacă a și b sunt întregi pozitivi, atunci există doi întregi s și t astfel
încât gcd(a, b) = sa + tb. În plus, s, t se pot calcula într-un timp logaritmic în
lungimea argumentelor.
Exemplu: 1 = gcd(50, 21).
50 mod 21 ≡ 8 8 = 50 – 2∙21
21 mod 8 ≡ 5 5 = 21 – 2∙8
8 mod 5 ≡ 3 3 = 8 – 1∙5
5 mod 3 ≡ 2 3 = 5 – 1∙3
3 mod 2 ≡ 1 1 = 3 – 1∙2
Prin inversarea pașilor se obține succesiv:
8 = 50 – 2∙21
5 = 21 – 2∙8
5 = 21 – 2∙(50 – 2∙21)
5 = 5∙21 – 2∙50
3 = 8 – 1∙5
22
3 = (50 – 2∙21) – 1∙ (5∙21 – 2∙50)
3 = – 7∙21 +3∙50
2 = 50 -1
∙3
ATACUL PRIN FACTORIZARE
Mesajul criptat poate fi decriptat dacă se cunoaște cheia de decriptare. Un
posibil atac RSA poate consta în încercarea de a factoriza pe n. Dacă ar fi posibil
atunci s-ar calcula p, q astfel încât n = pq. Cu p și q cunoscute, cu e cunoscut ca
parte a cheii publice ar fi de rezolvat ecuația matematică ex ≡ 1 mod (p – 1)(q –
1). Rezultatul ar fi exponentul d de decriptare .Problema factorizări nu este deloc
uşoară.
TEOREMA RESTULUI CHINEZESC
Să se afle un număr x care are restul 1 la împărțirea cu 3, restul 2 la împărțirea
cu 5 și restul 3 la împărțirea cu 7. Formulare echivalentă: un x care să verifice x
≡ 1 mod 3, x ≡ 2 mod 5 și x ≡ 3 mod 7. Soluția acestei probleme este x ≡ 52
mod 105. Cum a fost găsită?
Teoremă: Fie m1, m2, …, mn întregi pozitivi mutual primi doi câte doi și Mk =
m/mk. Sistemul
.
are o soluție unică modulo
Demonstraţie: Fie ./...21 kkn mmşiMmmmm Pentru fiecae valoare Mk
se stabileşte inversul yk modulo mk ( adică Mkyk = 1 mod mk ). Atunci
....222111 nNn yMayMayMax
Ceea ce încheie demonstraţia. Pentru n = pq, aplicaţia:
Este biunivocă, dar şi pentru că
23
.
nnn ZZqpnZ
Teorema restului chinezesc dă posibilitatea de a rezolva congruențele de modul
compus prin inversa(rea) aplicației de mai sus. Iată cum lucrează:
Pentru o pereche ., 21
nn ZZaa Se consideră:
și
Se pune pbaqbaa 2211 şi se observă că
qapbaqbaa
papbaqbaa
mod
mod
22211
12211
Exemplu: Să se rezolve x ≡ 5 mod 7, x ≡ 6 mod 11. Se calculează 7-1
mod 11 =
8 și 11-1
mod 7 = 2. Astfel, a = 5∙2∙11 + 6∙8∙7 = 446 ≡ 61 mod 77 este soluția
celor două congruenţe simultane.
Zn : mulțimea de întregi 0 ≤ a < n este un grup aditiv modulo n;
Zn* : mulțimea de numere întregi 0 ≤ a < n care sunt prime cu n este grup
multiplicativ modulo n.
Exemplu: Tablele de adunare pentru (Z6, +) și de multiplicare pentru ,*
6 Z :
Mica teoremă a lui Fermat: Dacă p este prim și p nu divide pe a atunci a p-1
≡ 1
24
mod p.
Demonstrație: Fie a un număr care nu se divide cu p. Fie lista tuturor
elementelor din Zp*, x1, x2, …, xp-1. Lista a x1, a x2, …, a xp-1 reproduce (eventual
într-o altă ordine) listă anterioară și:
x1∙x2∙…∙xp-1 = (a∙x1)∙(a∙x2)∙…∙(a∙xp-1) = ap-1
∙(x1∙x2…∙xp-1).
Grupul Zp*
este ciclic în sensul că există un element generator g astfel încât
Zp*= { g
0, g
1, …, g
p-1}. Faptul acesta a fost dovedit prima oară de Gauss care a
dovedit și un adevăr ceva mai general:
Pentru orice m, Zm * este ciclic dacă și numai dacă m este de forma 1, 2, 4, pk,
cu p un număr prim impar și k un întreg pozitiv. Ordinul unui element pZa *
este cel mai mic i ≤ 1 pentru care 1ia .
Teorema lui Lagrange: Dacă H este un subgrup al unui grup G, atunci |H|
divide pe |G|.
Demonstrație: Se definește pe mulțimea elementelor lui G relația de
echivalență:
a ~ b ab-1
H
Este ușor de arătat că clasele de echivalență sunt comulțimile Ha = {ha: h Î H }.
Toate aceste comulțimi au același cardinal și anume |H|. Urmează că |H| divide
pe |G|. Pentru un generator g al lui Z*p, elementul g
k are ordinul (p – 1) / gcd(p –
1, k). Mai mult, gk generează pe Z
*p dacă și numai dacă gcd (p – 1, k) = 1.
Grupul Z*p are (p – 1) generatori.
Teorema lui Euler: Dacă a este un întreg care este prim cu n, atunci:
25
Atac asupra sistemului RSA prin funcția totient
Există un algoritm “eficient” prin care, fiind dat un n ( produs de două numere
prime ), să se calculeze f(n)?
Se presupune că un asemenea algoritm n → f(n) există! Se poate dovedi că n + 1
– (n) = p + q. Acest fapt se întâmplă deoarece:
(n) = (p – 1)(q – 1) = pq – p – q + 1 = n – p – q + 1
Urmează că (n) = (p – 1)(n/p – 1) = n – n/p – p + 1 și apoi ecuația de gradul al
doilea:
p2 – (n + 1 – (n))p + n = 0
Formula binecunoscută conduce la
2
4112
nnnnnp
Așadar, existența unui algoritm “eficient” n → (n) implică existența unui
algoritm “eficient” de factorizare a lui n.
GENERAREA DE NUMERE PRIME PENTRU CRIPTAREA RSA
(euristică)
1. Se alege la întâmplare un întreg p impar lung de k biți;
2. Se divide p prin toate numerele prime mai mici sau egale cu un prim mic;
3. Dacă p trece testul de mai sus atunci se aplică testul Miller-Rabin pentru r
“baze” diferite
4. Dacă p trece toate aceste teste atunci el este prim cu o probabilitate superioară
cel putin egală lui 1 – 4-r
;
5. Dacă p nu este prim atunci se schimbă p în p + 2 și se reia pasul 1.
CONGRUENȚE
Congruențele sunt ca și egalitățile dar cu semnul “=” schimbat cu “≡”. O
congruență liniară are forma
cu x variabila necunoscută.
26
Congruența aceasta are o soluție dacă și numai dacă gcd(a, n)|b. Dacă x0 este o
soluție atunci orice altă soluție este de forma x = x0 + in/gcd(a, n) cu 0 ≤ i <
gcd(a, n). Se pot rezolva și congruențe de grad mai înalt cum ar fi:
Similar, se poate determina exact când:
are soluție. Pentru a rezolva congruențele ultime avem nevoie de “logaritmii
discreți” ai ambelor părți și se reduc la congruențe liniare.
SISTEME DE CRIPTARE BAZATE PE GRUPURI
Un grup finit este o pereche (G, ∙), cu G o mulțime finită și ∙ : G×G → G o
operație binară astfel încât:
1. operația este asociativă: " u, v, w Î G, u∙(v∙w) = (u∙v)∙w;
2. orice element are un invers unic: " u, $ v, u∙v = e, cu e un element distinct
(unitate, neutru). Elementul invers se notează u-1
.
De ce sunt interesante grupurile în cromatografie?
Pornind de la un element u al grupului se pot itera puteri întregi ale lui, adică u,u
u2, u
3 etc. care sunt elemente ale lui G. Fiind dată o “bază” u Î G și un element v
Î G care este o putere întreagă a lui u, de pildă uk, se poate calcula k?
Exemplu: În grupul *
19Z se pot forma puteri 7i mod 19.
70 ≡ 1 mod 19
71 ≡ 7 mod 19
72 ≡ 11 mod 19
73 ≡ 1 mod 19
74 ≡ 7 mod 19
75 ≡ 11 mod 19
Acum, fiind dat un element, de pildă 11, se poate calcula exponentul 5 care
satisface relația 75 ≡ 11 mod 19 ?
27
Cu cât numărul prim implicat este mai mare, cu atât este mai complicată
problema. Un alt exemplu: În grupul Z* 2579 numărul 435 este o putere a lui 2.
Se poate stabili exponentul?
Clase de grupuri.
1. Zn* mulțimea întregilor relativi primi cu n, modulo n;
2. Grupul multiplicativ din câmpul Galois GF(pn); cele mai utilizate, cu p =2;
3. Grupurile curbelor eliptice peste Zp;
4. Grupurile simetriilor (de pildă mulțimea simetriilor unui poligon regulat);
5. Grupurile de permutări;
6. Grupurile formate din cuvinte și relații.
28
3. SISTEMUL DE CRIPTARE EL GAMAL
Pentru orice grup (G, ∙) se definește sistemul de criptare următor:
Sistemul de criptare ElGamal ,,G
Public: (G, ∙), G ,
Privat: Exponentul a Z supus relației a
Criptarea: Pentru a cripta mesajul M se alege un întreg aleator k și se face
criptarea după schema: M → E(M) = ( kk M , )
Decriptarea: (y1, y2) → D(y1, y2) = 1
12
ayy
În continuare se discută securitatea acestui sistem de criptare în relație cu
dificultatea de a calcula logaritmii discreți din grupul (G, ∙). Fie a G.
Problema logaritmului discret al lui a: Fiind dat un element să se
găsească un întreg s astfel încât s . ElGamal se aplică la orice subgrup ciclic
< > al lui (G, ∙) astfel încât problema logaritmului discret este dificilă pe acest
subgrup. ElGamal se aplică uzual grupului multiplicative *
PZ , pentru un număr
p prim mare.
Exemplu de ElGamal (2579, 2, 949):
Privat: a = 765
Public: p = 2579, 2
9492579mod765
Pentru a trimite un mesaj M = 1299 se alege la întâmplare k = 853 și se
calculează:
y1 = 2853
mod 2579 = 435
y2 = 1299∙949853
mod 2579 = 2396
Textul cifrat este (435, 2396). Pentru decriptare se calculează:
2396∙(435765) +1
mod 2579 = 1299
Sistemul de criptare cu curbe eliptice este în esență El Gamal pe o clasă specială
de grupuri denumite grupuri eliptice.
Sistemul de criptare RSA.
29
O importantă pereche e produsul a două numere mari, distincte aleatoare şi
prime n p q şi e un număr cu 1 e şi , 1e , unde 1, 1 .n p q
Cheia publică este ,n e şi n se numeşte modulo n.
Cheia privată este d dacă 1 mod .e d
Mesajul de criptare şi spaţiul este:
0,1,2,3....n 1 .M C
Criptarea este exponenţială cu cheia publică e. Decriptarea este
exponenţială cu cheia privată d.
,mod .
mod .
e
n e
d
d
E m m n
D c c n
Decriptarea merge de la câţiva , 1k ed k și
1 mod ,d
e e d k km m m m m m n folosiind teorema lui Fermat.
Practic vom lucra RSA astfel:
Regula generală:
1
.
1 1 .
1 .î . , 1.
d e mod .
n p q
f n q
c na e f
f
Se calculează folosiind algoritmul lui Euclid extins. Algoritmul lui Euclid,
extins pentru aflarea inversului unui număr într-un modulo n. Vom nota paşii
algoritmului lui Euclid pornind de la pasul 0. Coeficientul obţinut la pasul i va
fi notat iq . În timp ce efectuăm fiecare pas al algoritmului ,vom calcula şi un
număr auxiliar ip .
Pentru primii doi paşi ştim deja valorile:
0
1
0.
1.
p
p
30
Pentru restul paşilor vom calcula respectiv cu :
2 1 2 modi i i ip p p q n
Continuăm calculul numărului auxiliar încă un pas după terminarea
algoritmului. Algoritmul începe prin împărţirea lui n la x, apoi continuă prin
împărţirea împărţitorului la rest. Când ultimul rest diferit de zero, se află la pasul
k ,dacă acest rest e 1, x admite un invers care va fi 2kp . Dacă restul nu e 1,atunci
x nu admite un invers.
Exemplu.
Calculăm inversul lui 15 mod 26 .
0
1
2
3
4
0 : 26 /15 1 11...... 0
1:15 /11 1 4.........p 1
2 :11/ 4 2 3..........p 0 1 1 mod 26 25
3: 4 / 3 1 1 ... 1 25 1 mod 26 24mod 26 2
4 : 3 /1 3 0............p 25 4 2 mod 26 21
..
pas rest p
pas rest
pas rest
pas rest xadmiteinvers p
pas rest
5.........................................p 2 21 1 mod 26 19mod 26 7
:15 7 105 1 4 26 mod 26 .Obs
RSA Exemplul 1.
1 1
0
1
2
3, 5, 7, ?
1 1 2 4 8
mod 7 mod8
8 / 7 1 1 0
7 /1 7 0 1
..................... 0 1 1 mod8 1 mod8 7
................ d 7
p q e d
f p q
d e f
rest p
rest p
p
31
RSA Exemplul 2.
1 1
0
1
2
3
7, 5, 11 ?
1 1 6 4 24
mod 11 mod 24
24 /11 2 2 0
11/ 2 5 1 1
2 /1 2 0 0 1 2 mod 24 22
.....................p 1 22 5 mod 24 109 mod 24 11.
................. e 11
p q d e
f p q
e d f
rest p
rest p
rest p
RSA Exemplul 3.
1
7, 11, 11
1 1 6 10 60
1 1111 mod 60 mod 60 mod 60 11 mod 60 11.
11 121
p q d
f p q
e
RSA Exemplul 4.
4
15, 4, 11 ?
mod 4 11 mod15 14641 mod15 1
................ 1
e
n e m c
c m
c
RSA Exemplul 5.
5
, 35,5 : 5, 3, ?
mod 3 mod35 243 mod35 33.
................ 33
d
n e d c m
m c n
m
RSA Exemplul 6.
4
3, 5, 4
15, 4, 11
mod 4 11 mod15
121 121 mod15 1
14641/15 976 1.
e
p q c
n p q e m
c m
c
rest
32
RSA Exemplul 7.
Cheia publică , 35,5n e
Cheia secretă 5d .
Dacă primeşte textul criptat 3c atunci textul clar de codificat de utilizator
este ?m
5mod 3 mod35
81 3 mod35
243 mod35
243 / 35 6 33
33
dm c n
m
m
rest
m
RSA Exemplul 8.
inversul lui 5 este
RSA Exemplul 9.
1 1
0
1
2
2 1 2
3, 5, 7, ?
1 1 2 4 8
mod8 7 mod8
8 : 7 1 1 0
7 :1 7 0 1
....................p 0 1 mod8 1 mod8 7
..........regulap mod .
7
i i i i
p q e d
f p q
d e
rest p
rest p
p p q n
d
33
RSA Exemplul 10.
1
11, 2, 7, ?
1 1 10
1 1 3 37 mod10 mod10 mod10 mod10 3 mod10
7 7 3 21
3
p q e d
f p q
d
d
RSA Exemplul 11.
1 1
7, 3, 5, ?
1 1 12
1 1 5mod 5 mod12 mod12 mod12 5 mod12 5
5 5 5
5
p q d e
f p q
e d f
e
RSA Exemplul 12.
5
13,e 5,m 9,c ?
c m mod 9 mod13 59049 mod13 3
3
e
n
n
c
RSA Exemplul 13.
7
, 17,3 , 7, 4, ?
mod 4 mod17 1028 mod17 8
8.
d
n e d c m
m e n
m
RSA Exemplul 14.
7
, 15,7
7, 3, ?
mod 7 mod15 823543 mod15 13.
13.
d
n e
d c m
m e n
m
34
RSA Exemplul 15.
7
15, 7, 11, ?
modn 11 mod15 2357947691 mod15 11
11.
e
n e m c
c m
c
RSA Exemplul 16. Contra exemplu.
Atenție 24 nu este prim.
RSA Exemplul 17. Contra exemplu.
Atenție 18 nu este prim.
Trebuie ca
RSA Exemplul 18.
1 1
8, 4, 2, ?
1 1 21 8
1 11mod 2 mod 21 mod 21 mod 21 11 mod 21 .
2 2 11
11.
p q e d
f p q primcu
d e f
d
35
Algoritmul EL Gamal
Algoritmul EL Gamal poate fi folosit atât pentru criptare cât și pentru
semnături digitale. Securitatea acestui criptosistem se bazează pe
intractabilitatea problemei logaritmului discret. Este un sistem de criptare
probabilist, în sensul că unui plaintext îi pot corespunde mai multe criptotexte.
Cu alte cuvinte, criptotextul este de două ori mai mare faţă de textul clar. În
continuare vom prezenta un algoritm pentru găsirea unui generator a unui grup
ciclic. Folosim algoritmul în procesul de generare al cheilor în cadrul
algortmului de criptare EL Gamal.
Problema logaritmului discret. Se dă un număr prim p şi generatorul g din *
pZ , şi un element *
pa Z . Să se afle numărul ,x cu 0 2x p astfel încât
mod .abg p
Problema Diffie-Hellman.
Se dă numărul prim p, generatorul g din *
pZ şi elementele modag p şi
modbg p să se afle mod .abg p
Caracterul privind cheia Diffie Hellman.
1....... : g mod .
1....... : mod .
x
x
MESAJUL A B p
MESAJUL B A g p
Cei doi operatori distribuie cheia fără autentificare.
A alege un x aleator 1 1.x p
B alege un y aleator 1 1.y p
B primeşte xg , calculează cheia distribuită mod .y
xK g p
A primeşte yg , calculează cheia distribuită mod .x
yK g p
36
Criptarea EL Gamal.
- Perechea importantă se bazează pe un număr mare, aleator prim şi un
generator g, din *
pZ şi un număr d.
Cheia publică este : , , mod .dp g g p
Cheia privată este: d
- Mesajul este cuprins în 0,1,2...p 1 .M Operaţia de criptare e dată de
selectarea unui număr aleator r şi calcularea perechii:
, ,
,dp g gE m e c unde mod , mod .
cde g p c m g p
- Decriptarea ia un element criptat C M M
şi calculează :
1, mod mod .d d p d
dD e c e c p undee e p
- Decriptarea merge deoarece d dre g
aşa că:
, mod .dr dr
dD e c g mg m p
Înainte de a începe exemplele să mai amintim algoritmul El Gamal cu
notaţiile mai pe scurt prezentate.
A = cheia privată a lui Alexandru.
B = cheia privată a lui Badea.
p = număr prim mare.
primitiv
cheia plublică Alexandru.
cheia publică Badea.
Criptare:
Badea obţine cheia publică a lui Alexandru calculează textul criptat c1
folosiind cheia lui privată şi c2 folosind α4 a lui Alexandru pe care-l obţine din
cheia lui publică
37
1
2
1 2
mod .
mod .
, .
B
A
c p
c m p
c c c
Trimite textul cifrat c = ( c1 , c2 ) la utilizatorul Alexandru.
Decriptare:
Pentru a determina textul m din textul cifrat c, utilizatorul Alexandru execută
următoarele:
1. Utilizează cheia sa privată pentru a calcula:
1
1 mod .p Af c p
2. Determină textul clar m astfel:
2 mod .m f c p
El Gamal
Exemplul 1.
4
1
43 12
2
1 2
1 13 1 3 9
1
2
13, 2, 3, 4, 7, ?
mod 2 mod13 16 mod13 3
mod 7 2 mod13 7 2 mod13 28672 mod13 7
, 3,7 .
.
mod 3 mod13 3 mod13 19683 mod13 1.
mod 1 7 mod13 7 mod
BA
p A
p A B m c
c p
c m p
Atunci c c c
Decriptare
f c p
m f c p
13 7.
38
El Gamal
Exemplul 2.
2
1
32 6
2
1 2
17, 3,A 2,B 3,m 6
3 mod17 9 mod17 9 mod17 9.
6 3 mod17 6 3 mod17 4374 mod17 5.
c , 9,5 .
p
c
c
c c
El Gamal
Eemplu3.
1 2
5
1
53 15
2
1 2
7, 4, 3, 5, 9... , ?
mod 7 4 mod 7 1024 mod 7 2.
mod 7 9 4 mod 7 9 4 mod 7 1073741824 mod 7 2.
, 2,2 .
BA
p A B m c c c
c
c m
c c c
Decriptare:
1 7 1 3 3
1 1
1 2
2 mod 7 2 mod 7 1
mod 7 2 2 mod 7 4.
p Af c
m f c
El Gamal
Exemplul 4.
1 2
1 13 1 2 9
1 1
1 2
13, 2, 2, 3.
.
, 5,3 ..... ?
mod 5 mod13 5 mod13 1953125 mod13 5
mod13 15 mod13 2
2.
p A
p A B
AprimeştedelaB
y y txt x
f y p
x f y
x
39
El Gamal
Exemplul 5.
1 2
1 2
1 15 1 3 9
1 1
1 2
15, 3, 3, 6, , 3,6 .
: , 3,6 .
x ?
mod 3 mod15 3 mod15 6561 mod15 6.
mod15 6 6 mod15 36 mod15 6
6.
p A
p A B y y
AprimeştedelaB y y
f y p
x f y
x
Algoritmul de cifrare El Gamal poate fi definit de un număr prim p şi un
element numit generator *
pg Z.
Pentru cheia privată *
px Z vom calcula
modxy g p, cheia publică fiind
tripletul ( y , g, p ).
Pentru a cifra un mesaj pM Zse alege aleatoriu 1pk Z
, textul cifrat fiind:
1 2, mod , mod .k ky y g p My p
Pentru a descifra mesajul 1 2,y y
se calculează :
1
2 1 mod .xy y p
El Gamal
Exemplul 6.
Se cifrează mesajul M = 7 cu ajutorul algoritmului El Gamal cu parametrii: p
= 11, g = 3, x = 4
Cheia publică este:
4y, , mod , , 3 mod11,3,11 81mod11,3,11 1,3,11 .xg p g p g p
Cheia privată este x = 4. Alegem k = 3 prim cu p-1. Obţinem mesajul cifrat.
40
3 3
1 2, mod ; mod 3 mod11,7 1 mod11 27mod11,7mod11 5,7 .k kC y y g p My p
El Gamal
Exemplul 7.
Când nu sunt îndeplinite condiţile, nu putem obţine nimic.
Se criptează mesajul M = 5 cu parametrii; p = 8, g = 2, x =5. Observăm că p
nu este prim. Mergem mai departe să vedem ce se întâmplă .
Cheia publică este dată de :
5, , mod , , 2 mod8,2,8 32mod8,2,8 8,2,8 .xy g p g p g p
Cheia privată este x =5. Alegem k = 6 prim cu p-1 adică 7. Obţinem mesajul
cifrat:
6 6
1 2
1 2
, mod , mod 2 mod8,5 8 mod8 .
, 0,0 .
k kC y y g p My p
C y y
El Gamal
Exemplul 8.
Se criptează mesajul M = 9 cu ajutorul algoritmului El Gamal cu parametrii
p =11, g = 3, x = 4. Cheia publică este:
4, , mod , , 3 mod11,3,4 81mod11,3,4 4,3,11 .xy g p g p g p
Cheia privată x = 6. Alegem k = 3 prim cu 10. Mesajul cifrat C este:
3 3
1 2, mod11, mod11 3 mod11,9 4 mod11 5,4 .k kC y y g M y
El Gamal
Exemplul 9.
Putem să decifrăm mesajul {6,8} ştiind că a fost cifrat cu algoritmul El
Gamal cu parametrii p = 17, g =14, x = 2. Cheia publică este {y, g, p}={9, 14,
17}. Cheia privată este x = 2. Menţionez că am utilizat şi M = 4. Mesajul clar se
obţine aplicând formula :
41
2 1 mod .xy y p
2 1
27 7
2
mod mod mod mod
4 9 mod17 14 mod17 mod17
8 88 6 mod17 mod17 mod17
36 2
4 mod17 4
xx k ky y p My p g p p
El Gamal
Exemplul 10.
Să se decifreze mesajul {7,9} ştiind că a fost criptat cu algoritmul El Gamal
cu parametri: p = 23, g = 3, x = 5. Calculăm direct cu formula:
11 5 1 1
2 1 mod 9 7 mod 23 9 16807 mod 23 9 17 mod 23
19 9 19 171mod 23 mod 23 mod 23 171 mod 23 10.
17 17 19 323
xy y p
Metoda lui Diophatus
Utilizând un set de puncte cunoscute, pentru a produce noi puncte (0 , 0) și (1,1)
sunt două solţii banale. Ecuaţia liniară prin care trece această dreapta este y = x.
22
6
121x
xxxy
22
2
6122
6121
xxxxx
xxxx
02
1
2
3
032
23
23
xxx
xxx
22
1,
2
1
2
162
2
3
2
1
12
1,
2
11
2
121
2
1
2
1
2
1
2
2
solutiayy
solutiayx
42
curba este simetrică
yxxxx
y
yxxxx
y
,6
121
,6
121
2
2
Acum vom considera o linie prin punctele ( 1/2, -1/2) și (1,1). Folosim formula:
2
21
212 xx
xx
yyyy
Obținem ecuaţia unei drepte și anume:
23 xy
Intersectăm din nou această dreaptă cu curba eliptică:
7024
0122
73
2
51
24725432
1249622
23612
236
121
23
223
2223
22
222
yx
xxx
xxxxx
xxxxxx
xxxx
yxxxx
y
Considerăm:
0,45mod004
4,3;1,35mod4,115mod363
0,25mod02
.4,1;1,15mod4,11
0
5mod32
2
2
32
yyx
yyx
yx
yx
nuexistayx
xxy
Punctele de pe curbele eliptice sunt :
0,4.4,3.1,3.0,2.4,1.1,1 și punctul de la ∞.
43
Folosiind câmpurile finite putem forma un grup de curbe eliptice unde avem, de
asemenea o problema DLP, care este mai greu de rezolvat. O curbă eliptică
peste un câmp K e o curbă f(x,y) = 0 non singulară cu un punct raţional. Câmpul
K e luat de obicei, de numerele complexe, reale, raţionale, extensi algebrice de
numere raţionale, numere periodice sau de un câmp finit.
Grupurile de curbe eliptice pentru criptografie sunt examinate cu următoarele
câmpuri din :
Weierstrass Equation.
Ecuaţia în două variabile F(x,y) = 0 formează o curbă în plan. Căutam metode
aritimetice sau geometrice pentru a găsi soluţii.
Ecuaţia generală a lui Weierstrass pentru curba eliptică este:
64
2
2
2
31
2 axaxaxyaxyay
Aici a, b, x aparţin unui câmp de numere raţionale complexe, corpuri ( FP ) finite
sau câmpuri Galois (GF( 2n )).
În cazul în care câmpul caracteristic nu e 2:
.4422
64
2
2
31
2
6
32
4
212
2
3
2
31 axaxaxyaa
xaxa
axa
xa
y
Dacă câmpul caracteristic nu e nici 2 nici 3:
.
3
1132
1
21
BAxxy
axx
44
4. CURBE ELIPTICE: MOTIVAȚIE
O întrebare fundamentală este dacă o ecuație cu coeficienții întregi F(x1, …, xn)
= 0 (1) are soluții întregi. F este un polinom în variabilele x1, …, xn cu
coeficienții întregi.
1. Are ecuația (1) soluții întregi?
2. Are ecuația (1) soluții raționale?
3. Numărul soluțiilor întregi este finit sau infinit?
4. Numărul soluțiilor raționale este finit sau infinit?
O ecuație în două variabile F(x, y) = 0 reprezintă o curbă în plan. Se caută
metode geometrice - aritmetice pentru a afla soluțiile.
ECUAȚII LINIARE
ax + by = c, a, b, c Z
Ecuația are o soluție întreagă dacă și numai dacă gcd(a, b)|c – cel mai mare
divizor comun al coeficienților a, b divide pe c – și dacă are o soluție, are o
infinitate de soluții. Mulțimea soluțiilor raționale este infinită.
EXEMPLE
1. 2x + 3y = 13 are o soluție întreagă și anume x = 2, y = 3. Are și soluții
raționale. Pentru fiecare valoare rațională a lui x, valoarea corespunzătoare a lui
y este (13 – 2x)/3.
2. 4x – 6y = 13 nu are soluții întregi deoarece gcd(4, 6) = 2, număr care nu-l
divide pe 13. Dar are soluții rationale.
3. Pentru n ≥ 3, ecuatia:
nnn zyx
45
nu are soluții întregi (conjunctura lui Fermat), ceea ce este echivalent cu a spune
că ecuatia xn + yn = 1 nu are soluții raționale pentru n ≥ 3.
4. Triplele pitagorice ( x, y, z ) sunt triple de întregi care satisfac ecuația :
222 zyx
de pildă (3, 4, 5). Există o echivalență cu rezolvarea ecuației:
122 yx
în numere raționale. Soluțiile sunt:
22
2
1
2.,
1
1
t
ty
t
tx
ECUAȚII CONICE ( PĂTRATICE )
Ecuațiile de acest tip au forma generală:
Qfedcbaefdxcxybyax ,,,,,,022
O transformare de variabile (rotație și translație) aduce această formă la o
ecuație familiară a unei elipse sau a unei hiperbole (c = d = e = 0). Dacă se
caută intersecția unei drepte raționale cu conică, punctele de intersecție sunt sau
nu raționale?
Rezolvarea sistemului de ecuații, a conicei și a dreptei, trece prin rezolvarea unei
ecuații pătratice care are două soluții. În plus, dacă una din soluții este rațională
la fel este și cealaltă (radicalul din formulă are ca rezultat un număr rațional).
Dacă se cunoaște un punct rațional, de pildă O, iată cum se stabilesc toate
celelalte. Pentru un punct P oarecare, se trasează linia OP și se determină
intersecția P’ cu linia rațională L. Dacă P este rațional atunci P’ este rațional și
reciproc.
Întrebare: Cum se face testarea pentru un punct rațional?
Se convertește ecuația la forma ei omogenă ( prin schimbarea x = X/Z, y = Y/Z)
46
222 cZbYaX
Teoremă (Legendre): Există un întreg m care depinde de a, b, c astfel încât
ecuația (2) să aibă o soluție întreagă netrivală dacă și numai dacă:
222 cZbYaX mod mare soluţii în Zm*.
Exemplu: Se poate aplica metoda pe cercul C: x2+y
2 = 1. Se consideră punctul
(x, y) mobil pe cerc. Se ia linia L care leagă (0, 0) de (x, y). Această linie
intersectează axa y în (0, t).
Ecuația dreptei L este L: y = t(1 + x). Deoarece punctul se află pe dreaptă și pe
cerc 1 –x2= y
2 = t
2 (1 + x
2), ceea ce produce ecuațiile parametrice familiar:
47
22
2
1
2,
1
1
t
ty
t
tx
În plus, t este rațional dacă și numai dacă x și y sunt raționale, ceea ce oferă toate
punctele raționale de pe cerc.
ECUAȚII CUBICE
Este vorba de ecuații de forma:
ax3 +by
3 +cyx
2 + dxy
2 + exy + fx + gy + h = 0,
cu coeficienții raționali. Weierstrass a arătat că prin utilizarea unor transformări
potrivite (proiective, care este posibil a schimba coeficienții) ecuația devine
echivalentă cu forma normală Weierstrass:
y2 = x
3 + ax
2 + bx + c.
Admițând că rădăcinile ei sunt distincte ea este expresia unei curbe eliptice.
Polinomul x3 + ax
2 + bx + c are fie o rădăcină reală și două complexe, fie toate
trei rădăcinile reale.
DE UNDE PROVIN NUMELE DE CURBA ELIPTICĂ?
Se consideră elipsa:
.12
2
2
2
b
y
a
x
Rezultă:
48
.2
2
222 x
a
bby
Prin diferenţiere se obţine:
.2
2' x
a
byy
Şi mai departe obținem:
.'
2
222
2
4
4
24
242
a
xbb
x
a
b
ya
xby
Lungimea elipsei este dată de formula:
dxxkx
xkdx
x
xkdxy
222
22
2
222
11
1
1
1'1
cu constanta k aleasă potrivit. Se notează g(x) = (1 – x2)(1 –x
2k
2). Se consideră
curba u2 = g(x). Prin utilizarea transformărilor:
2
2
1,
1
1
u
uuxy
xx
u2 = g(x) devine xfu 2 astfel încât
dxu
xkdxy
gxgxgxgxf
222
23
1'1
1''''24
11'''
6
11''
2
11'
EVITAREA SINGULARITĂȚILOR
Fie E(a, b) grupul abelian al punctelor raționale ale curbei eliptice:
y2 = f(x) = x
3 + ax + b.
49
S-a arătat că o curbă eliptică nu are puncte singulare dacă și numai dacă f(x) nu
are rădăcină dublă. A avea rădăcină dublă echivalează : f(x) = f’(x) = 0, adică:
x3 + ax + b = 3x
2 + a = 0. (4)
Urmează că x2 = – a/3. Dar totodată x
4 + ax
2 + bx = 0. Asta implică a
2/9 + a(–
a/3) + bx = 0 și în consecință, x = 2a2/9b. Prin substituire în (4) se obține
3(2a2/9b)
2 + a = 0 și în cele din urmă 4a
3 + 27b
2 = 0.
Teoremă: Curba y2 = x
3 + ax + b este nesingulară dacă și numai dacă 4a
3 + 27b
2
≠ 0.
50
5. CURBE ELIPTICE PESTE Zp
Aproape toate cele spuse mai sus se potrivesc și în cazul câmpurilor finite. Fiind
dat un număr prim p, o curbă eliptică peste Zp este o congruență y2 = x
3 + ax + b
mod p la care se adaugă un punct O la infinit astfel încât condiția de
“nesingularitate” 4a3 + 27b
2 ≠ 0 mod p să fie satisfăcută. Fiind date punctele P1
= (x1, y1) și P2 = (x2, y2) pe curba eliptică se definește:
1312121 ,12 yxxxxPP
cu
21
1
2
1
21
12
12
2
3PpentruP
y
ax
PpentruPxx
yy
Se consideră totodată că (x1, y1) + (x1, –y1) = O și P1 + O = O + P1 = P1. Acesta
este un grup abelian denumit Ep(a, b). Acceași idee se potrivește și câmpului
finit GF(pn).
PROPRIETĂŢI
Fie p un număr prim mai mare decât 3.
Hasse: ppbaEpp p 21,21
Schoof: Există un algoritm eficient ca O(log8p) pentru a calcula: |Ep(a, b)|.
Waterhouse: Pentru orice întreg n care:
ppnpp 2121
există a, b < p astfel încât |Ep(a, b)| = n. În plus, ordinele grupurilor de curbele
eliptice sunt uniform distribuite în acest interval.
Teoremă: |Ep(a, b)| Zn1 Z n2, pentru n1, n2 astfel încât n2|n1 și n2|(p –
1).
51
Exemplu: Se consideră curba eliptică y2 = x
3 + x + 6 peste Z11*. Pentru a
determina punctele din E, se ia fiecare punct din Z11, se calculează x3 + x + 6 și
apoi se rezolvă ecuația y2 ≡ x
3 + x + 6 mod 11.
Calculul acesta cere evaluarea de radicali modulo 11. Există o formulă explicită
pentru aceasta deoarece 11 ≡ 3 mod 4. De fapt rădăcinile pătrate ale unui rest
pătratic r sunt •r(11 + 1)/4 ≡ r 3mod 11. Pentru calcul se completează tabelul
următor:
x x3+x+6 R11 y
0 6 nu
1 8 nu
2 5 da 4,7
3 3 da 5,6
4 8 nu
5 4 da 2,9
6 8 nu
7 4 da 2,9
8 9 da 3,8
9 7 nu
10 4 da 2,9
Curba eliptică are pe ea 13 puncte (x, y), încluzând și punctul de la infinit. Fiind
de ordinul prim 13 ea însăși trebuie să fie un grup ciclic. De pildă, dacă se ia
generatorul a = (2, 7).
Puterile lui , de pildă (2, 7) + (2, 7), pot fi calculate după cum urmează. Se
evaluează mai întâi :
= (3∙22 + 1)(2∙7)
-1 mod 11 = (2∙3)
-1 mod 11 = 2∙4 mod 11 = 8.
Așadar x3 = 82 – 2 – 2 = 5 mod 11 și y3 = 8(2 – 5) – 7 = 2 mod 11. Decurge de
aici că (2, 7) + (2, 7) = (5, 2). Apoi, (2, 7) + (2, 7) + (2, 7) = 2(2, 7) + (2, 7) =
(5, 2) + (2, 7).
52
SISTEME DE CRIPTARE CU CURBE ELIPTICE
Algoritmul El Gamal se poate aplica la un subgrup ciclic 1nZ al lui Ep(a, b), dar
factorul lui de dezvoltare este 4 ( față de 2 peste Zp). În plus, spațiul textelor în
clar (plaintext space) constă din punctele din Ep(a, b) și nu există metodă
convenabilă de a genera în mod determinist puncte din Ep(a, b).
Se ia o curbă eliptică Ep care conține un subgrup ciclic H = 1nZ cu algoritm
discret intractabil. Spațiul textelor în clar este 21 nn ZZ și spațiul textelor cifrate
este **
ppp ZZE . Un program care poate fi utilizat în timp real poate fi găsit la
adresa:
http://www-fs.informatik.unituebingen.de/~reinhard/krypto/English/4.4.en.html
Sistemul Menezes – Vanstone:
Public: PE,
Privat: a astfel ca a
Criptare: Se alege aleator1nZ
(x, k) → E(x, k) = (y0, y1, y2): kccky 210 ,,
x = (x1, x2), pxcpsiyxcy modmod 222111
Decriptare: (y0, y1, y2) → D(y0, y1, y2) = (y1c1-1
mod p, y2 c2-1
mod p)
ay0 = (c1, c2).
FACTORIZARE, PRIMALITATE, GRUPURI
Se dă un întreg n pentru a fi testat dacă este prim şi un grup knZG
pentru un anumit k. Pentru Gx se defineşteG
x ca fiind ordinul lui x în
G.
Premisă: Există o mulţime de întregi SG, astfel încât GGSxGx n este
prim.
Testul de primalitate: ?GGSxGx
Se poate testa |x|G = m astfel:
53
|x|G= m xm = e & ( prim p | m)(
ex p
m
).
Astfel, testarea primalității lui n se reduce la factorizarea lui GSm . De obicei,
factorii primi pentru orice GSm sunt cunoscuti. Grupurile de curbe eliptice En
(a, b) sunt utilizate pentru testarea primalității și pentru factorizarea lui n.
Puncte pe curbele eliptice(EC)
Curba eliptică peste câmpul L este:
baxxyaxyayLLyxLE 3
31
2,,
Punctul stă în vîrful axei yy’ și orice linie trece prin el din moment ce e raţional.
Este şi în vîrful şi la paralele la axa yy’.
Grupul Abelian
Se dau două puncte (P,Q) în E(FP). Acolo este un al treilea punct, desemnat de
P+Q în E(Fp) și următoarele relaţii pentru P,Q,R în E(Fp).
1.P+Q=Q+R
2.(P+Q)+R=P+(Q+R)
3.P+0=0+P=P
4.Există –P ai –P+P=P+(-P)=0.
54
55
Se dovedește că este vorba de un grup abelian și că operația este independentă
de alegerea punctului O. Acum se poate răspunde la întrebarea inițială.
Teoremă (Mordel): Grupul punctelor raționale ale unei curbe eliptice
nesingulare este generat infinit. În practică, punctul O se determină utilizând
puțină geometrie proiectivă. Se presupune că O este un punct la infinit care este
un punct rațional pentru cubică. Acum se pot dezvolta formule explicite pentru
operațiile în grup.
Exemple de curbe eliptice.
56
Fig. y2=x
3-x+1.
57
Se consideră curba eliptică y2 = x
3 - x + 1. Dacă P și Q sunt pe E, putem defini
R = P + Q.
332211 ,,;, yxQPRyxQyxP .
Fie P diferit de Q . Pentru a găsi intersecţia cu E rezultă:
1111
1
12
121
11
32 .;
yxxmyxxmyy
xxxx
yyyy
xxmyyBAXxy
12
12121321
2
3
23
32
11
;;
............0
.
xx
yyundemyxxmyxxmxx
mxx
BAxxyxxm
Calculele în detaliu arată cam aşa:
.02)22(
0222
222
222
2
11
2
1
2
1
2
11
223
111
2
1
2
1
2
1
223
1111
2
1
2
1
2
1
223
111
2
1
2
11
223
3
11
2
1
2
1
232
11
xmyyxmBmymxAxxmx
xmyxmyyxmmxxxmBAxx
xmyxmyyxmmxxxmBAxx
xmyxmyyxxxxmBAxx
BAxxxxmyyxxmBAxxyxxm
1313
21
2
3
yxxmy
xxmx
58
Dublarea unui punct
Fie P = Q , y2 = x
3 + Ax + B
1313
1
2
21
2
21
2
3
223
211
1
2
12
2
2
...............0
;0
2
3
2
3;32
yxxmy
xmxxmxxmx
xmx
PavemPDacăa
y
Ax
y
Ax
dx
dymAx
dx
dyy
Ce se întâmplă când P2 este infinit?
111 POPP
Punctul de la infinit.
Ca rezultat al cazului de mai sus O este numit identitatea adăugată la grupul de
curbe eliptice. P + (-P) = O. Prin urmare, toate curbele eliptice au o identitate
adăugată O.
Coordonate Proiective.
Spaţiul proiectiv tridimensional Pk2
peste K este dat de clasele de echivalenţa
triple cu x, z, y în K şi cel puţin una dintre x, z, y nenule. Două triplele sunt
numite echivalente dacă există un element a nenul în K astfel încât (x, y, z) =
(ax, ay, az). Clasa de echivalenţă depinde de raţii şi prin urmare, depinde de
(x,y,z). Dacă:
1,,,,,0
z
y
z
xzyxz
Dacă z = 0, obţinem un punct la infinit și un plan bidimensional afin peste K:
KKyxAk ,2
Prin urmare folosim:
221;;, KK PAYXyx
59
Sunt avantaje cu folosirea coordonatelor proiective de la implementarea
punctelor de vedere.
Singularitatea
De la curba eliptică y2
= f(x) definim: F( x , y ) = y2
- f(x). Singularitatea unei
curbe eliptice este un punct (x0,y0) care satisface:
0
'
0
0
'
0
0000
02
0,,
xfxf
xfy
yxy
Fyx
x
F
f are rădăcină dublă.
Este obişnuit să spui că o curbă (Ec) eliptică nu are puncte singulare. Dacă
caracteristica câmpului nu este 3.
BAXxxfy 32
Condiţia pentru singularitate este:
0274 23 BA
În general, curbele eliptice n-au singularităţi.
0
'
0
0
'
0
0000
02
0,,
xfxf
xfy
yxy
Fyx
x
F
f are radăcină dublă. Pentru rădăcini duble avem:
60
.027409
2
981
80
9
2
9
2
9
229092
093
039
033
0
00
0)(
3
03
03
3
3
233
3
623
2
222
22
22
2
222
243
3
00
3
2
0
23
0
23
2
23
32
BABB
A
B
AB
B
AA
B
A
B
AxABxBxA
BxAA
BxAA
BxA
AA
BxAxx
BxAxxBAxx
BAxxxfBAxxxf
Ax
ABAxxx
AxBAxx
Ax
AxBAXx
BAXxy
Aplicaţii.
Fie curba eliptică :
433
03313
3313
3313
1,313
0
2
0
3
0
0
2
0
3
0
3
00
3
0
2
00
'
0
3
00
32
xxx
xxx
xxx
xxfxxxf
BcuAxxxfy
Verificăm condiţia din teoria de mai sus expusă:
0273127342742333 BA
Deci avem puncte critice şi vrem să vedem câte sunt şi cum le aflăm. Folosim
şirul lui Rolle.
61
;11,31
1,101133313 21
2'3
ff
xxxxxxfxxxf
Deci avem trei rădăcini în intervalele :
,1,1,1,1, 321 xxx
Dacă am lucra prin metoda grafică am obţine o aproximare şi mai bună:
12
57,
2
1
4,
2
6
573,
6
573
6
4893
32
434930433
433
212,10
2
0
0
2
0
3
0
Vaa
bV
xxxxx
xxx
Există trei puncte :
,1;1,
6
573;1;
6
573tvu
Alte exemple:
32
22 1
xy
xxy
62
Curbe Eliptice în caracteristica 2.
Ecuaţia generalizată este:
642
3
31
2 axaxaxyaxyay
Dacă a1 nu este zero se reduce la forma asta:
BAxxxyy 232
Dacă a1 este zero forma redusă e asta:
CBxxAyy 32
Forma nu poate fi acesta:
BAxxy 32 .
63
6. CRIPTOSISTEME CU CHEIE PUBLICĂ
Criptografia curbei eliptice( CCE)
Dacă A poate genera mesajul criptat, doar B poate decripta mesajul. CCE e un
criptosistem cu cheie publică cu RSA sau EL GAMAL.
Fiecare utilizator are o cheie publică şi una privată. Cea publică este folosită
pentru criptare iar ceea privată este folosită pentru decriptare. Curbele eliptice
sunt folosite ca o extensie pentru criptare. Ceea mai importantă parte a unui
criptosistem o reprezintă grupul eliptic. Toate criptosistemele cu cheie publică
au la bază operaţii matematice. Procedurile generice pentru CCE sunt:
1. Ambele părţi sunt de acord cu unele elemente cunoscute de public;
2. Ecuaţia curbei eliptice;
3. Valorile a şi b;
4. Numărul prim p;
5. Grupul eliptic calculat din ecuaţia curbei eliptice (CE);
6. Punctul de bază B, luat din grupul eliptic;
7. Similar cu generatorul folosit în Criptosistem;
8. Fiecare utilizator generează cheia publică sau secretă;
9. Cheia privată x este un număr întreg, absolut din intervalul [1,p-1];
10. Cheia publică este un produs al cheii private şi al punctului de bază Q = x*B.
Exemplu de criptare pe curbele ( CCE ) analog la ElGamal.
Alice vrea să-i trimită lui Bob un mesaj criptat.
1. Ambii sunt de acord cu punctul de bază B.
2. Ambii creează cheile.
Alice: Cheia privată a. Cheia publică PA = a*B.
64
3. Bob : Cheia privată b. Cheia public PB = b*B. Alice ia mesajul și îl codează.
Exemple CCE. Analog la El Gamal.
Alice alege alt număr real aleatoriu h din [1,p-1]. Textul cifrat e o pereche de
puncte PC = [ (kB) , (PM+kPB) ].
Pentru a -l decripta, Bob calculează produsul primului din Pk şi cheia privată b
b*( kB ). Bob ia primul produs şi-l scade din al doilea punct din PC.
MMBM PkBbbBkPkBbkPP
Bob decodează Pm pentru a vedea mesajul M.
Exemplu. Comparaţie cu El Gamal.
Textul criptat e o pereche de puncta:
PC = [ (KB) , (PM+KPB) ].
Textul cifrat în El Gamal e o pereche:
C = ( gk mod p, m PB
k mod p ).
Bob ia produsul şi îl scade din al doilea punct:
( PM + k PB ) - [ b ( kB )] = PM + k (bB) – b (kB) ] = PM.
În El Gamal, Bob ia coeficientul valorii o dată şi a primei valori crescute:
M = m PBk / (g
k)
b = mg
k*b / g
k*b = m.
POHLIG-HELLMAN ,,p
Fie ke
k
eepppp ...1 21
21 . Dacă pa mod atunci loga este unic determinat
modulo .1p Se presupune q prim în condițiile p ≡ 1 mod qc şi ￢(p ≡ 1 mod
qc+1
). Se exprimă astfel:
65
ici
i
i qx
1
1
Cu 10 qai . Se scrie a = x + sqc. Se poate face următoarea
Afirmaţie:
pq
p
q
p
mod
11 0
Demonstraţie:
pq
psqx
q
pa
q
p c
mod
111
Este, prin urmare suficent a arăta că:
pq
p
q
psqx c
mod
110
ceea ce este echivalent cu a demonstra congruența exponențiilor modulo (p-1)
1mod11
0
pq
p
q
psqx c
adică:
1mod0
1111 1
1
111
1
1
0
00
1
p
qsqpqsqq
pqsq
q
psqx
q
p c
i
i
i
cci
i
i
i
cci
i
i
i
c
Se calculează acum .
1
q
p
Dacă pq
p
mod1
1
atunci .00 Dacă nu, atunci se
calculează:
,...mod,mod,mod
13
12
1
ppp q
p
q
p
q
p
până când .mod
11
pq
pi
q
p
Urmează
Dacă c = 1, calculul s-a încheiat.
Altminteri, c > 1. Se defineşte 0
1
şi fie .modlog 11
cqx Urmează că
.mod2
0
2
11
1
1
1
pşiqx q
p
q
ppi
i
i
ii
Se poate calcula 1 ca mai sus. Dacă c = 2
calculul s-a încheiat, altminteri c > 2 şi se continuă ca mai sus.
66
1. Se calculează pq
pi
i mod
1
pentru
2. Se pune j = 0 şi j
While j < c -1 do
Calculează pjq
p
mod1
1
Caută i astfel încât i
1
mod1
jj
p
i
jjq
jj
j
Exemplu pentru Pohlig-Hellman (29, 2, 18)
p – 1 = 28 = 22∙7, 18,2 . Se urmărește evaluarea logaritmului discret
18log2 . Exponentul a pentru care 2a= 18 mod 29 este necunoscut. Se calculează
separat a mod 22 și a mod 7.
q = 2, c = 2:
2
28
= 214
= 28 mod 29
2
28
= 1814
= 28 mod 29
așadar 10
q = 22, c =2:
31
29mod289
29mod9
1
74
28
1
1
01
sia
q = 7, c = 1:
29mod2518
29mod162
144
28
44
28
așadar 440 sia .
Se utilizează teorema restului chinezesc pentru a rezolva sistemul x ≡ 3 mod 4, x ≡ 4 mod 7 pentru a obține x = 11. Așadar, 1118log2 .
67
METODA INDEX CALCULUS
Metoda uzează de baza de factori: B = {p1, p2, …, pB}.
Pasul 1: Se calculează logaritmii a B numere prime din baza B, adică:
.log,...log,log 21 Bppp
Explicații la pasul 1: Se iau C = B + 10 congruenţe pppp jBjjj
B
xmod...21
21
, Cj , ceea ce este totuna cu .1modlog...log 1,1 pppx BBjjj Aceasta
conduce la un sistem liniar de C congruenţe în necunoscutele .,log Cipi
Pasul 2: Se calculează log folosind cunoștințele de la pasul 1.
Explicatii la pasul 2: Acest calcul se face cu un algoritm Las Vegas. Se admite
succesul în pasul 1 și cunoașterea valorilor .log,...log 1 Bpp . Se alege la
întâmplare 1 ≤ s ≤ p – 2.
Se calculează ps mod în baza de factori dată ,,...,, 321 BppppB de pildă
.mod...21
21 pppp Bc
B
ccs Urmează că ,log...log 11 BB
s pcpcs
Analizele arată că precalculul are un timp de execuție asimptotic, adică:
ppO
eOlnlnln11
și timpul de aflare a logaritmului discret este:
ppO
eOlnlnln1
2
1
EXEMPLU
p = 10007, 5 , 9451 , B = {2, 3, 5, 7}. Mai întâi se calculează
.7log,5log,3log,2log 5555 Se încearcă factorizarea lui x
pentru x = 4063, 5136, 9865:
54063
≡ 42 = 2∙3 7 mod 10007
55136
≡ 54 = 2∙33 mod 10007
59865
≡ 189 = 33∙7 mod 10007
68
care dau congruenţele liniare:
10006mod98657log3log3
10006mod51363log32log
10006mod40637log3log2log
55
55
555
cu soluţia unică .13017log,61903log,65782log 555 Pentru a afla 9451log5 se
alege un exponent aleator s = 7736 și se calculează 9451∙5776 ≡ 8400 mod
10007. Peste B, acesta se factorizează ca .7532 1214 Se dezvoltă:
60571301126190667847log5log23log2log477369451log 55555
Schimbarea cheii de acces Diffie-Hellman(DH)
(CCE) Diffie-Hellman
Public: (CE) şi punctul B = (x,y) pe curbă;
Secret: Alice a = (x,y) şi Bob b = (x,y);
Alice calculează: a ( b(x,y) );
Bob calculează b ( a(x,y) );
69
Acestea sunt la fel de când ab = ba.
Exemple-EC.
Diffie-Hellman Exchange
Alice şi Bob agrează setul de Key pe calculator.
Alice Private: Key = a;
Public: Key = PA = a*B.
Bob: Private: Key = b;
Public: Key = PB =b*B.
Acestea sunt la fel de când ab = ba.
De ce folosim (CCE)?.
Cum analizăm criptosistemele?.
Cât de dificilă e problema bazată…..___de tradus ?
1. RSA: factorizarea numere întregi;
2. DH: Logaritmii discreţi;
3. ECC: Problema logaritmului discretşi al CE;
Cum măsurăm dificultatea?
Examinăm algoritmii folosiţi pentru a rezolva aceste probleme.
Securitatea CCE.
Pentru a proteja AES cheia ar trebui:::::de::tradus
Mărimea RSA dată 3072 biţi.
Cum întărim RSA –ul?
Mărim lungimea cheii.
Inutil?.
70
Utilităţile( CCE).
Multe aparate, calculatoare sunt mici şi au spaţiile de stocare mic şi putere de
calcul mică. Unde aplicăm CCE? Sistemul de comunicaţie fără....traducere???
Carduri de memorie bancare. Selectare.....????
Selectoare nule???? De tradus.
Orice aplicaţie unde securitatea e necesară dar nu prea este spaţiu de stocare ???
De tradus.
Beneficii ale (CCE).
Aceleaşi beneficii ca la alte criptosisteme: confidenţialitate, integritate.
Mărimi mai mici ale cheilor. Criptare, decriptare cu viteză mare.
Salvarea spaţiului de stocare şi a lungimii de bandă.
Rezumatul (CCE).
1. Problemă grea analog la logaritmul discret.
Q = kP unde Q, P aparţine unei prime curbe;
E dat k, p atunci este uşor de calculat Q;
E dat O,P atunci este greu de calculat k;
Cunoscut ca problemea logaritmului discret , k trebuie să fie suficent de mare.
2. Securitatea CCE se bazează pe ecuaţia logaritmului discret şi a CE adică
criptarea curbelor eliptice. În comparaţie cu factorizarea poate utiliza chei
cu dimensiuni mai mici.
Implementarea ( CCE) în câmpuri binare.
1. Introducerea în CE;
2. Criptarea curbelor eliptice CCE;
71
3. Implementarea CCE în câmpuri binare.
Sub- capitol
1. Multiplicarea scalară LSB;
2. Tehnica MONTGOMERZ de multiplicare scalară;
3. Multiplicarea scalară rapidă fără prelucrare;
4. Transformarea proiectivă pentru a reduce.....???traducere;
5. Coordonate amestecate;
6. Tehnici de paralelizare;
7. Tehnici de înjumătăţire şi adăugare pentru multiplicarea scalară.
Criptarea pe curbe eliptice.
Algoritmul El Gamal poate fi extins pe orice grup finit G în care problema
logaritmului discret este dificilă, în particular şi în grupul punctelor de pe o
curbă eliptică. Astfel fie G
pentru care problema logaritmului în subgrupul H
ciclic
/ 0iH i
este dificilă. Menţionez că elementele grupului sunt perechi de puncte din plan
de pe curba eliptică. Folosind cheia privată x din Z, se construieşte:
Pentru a cifra un mesaj M se foloseşte aleatoriu Hk G
şi se aplică regula de
cifrare:
1 2,k , , .k kE M M y y
Mesajul m se recuperează din mesajul cifrat (y1 ,y2). Mesajul m se recuperează
din mesajul cifrat (y1, y2) după regula: 1
2 1 .xy y
.
Într-adevăr avem:
1
1 1
2 1 .x
x k k kx kxy y M M M
72
Exemplul 1.
Să se cifreze mesajul (10,9) utilizând curba eliptică (publică):
E: y2 = x
3+ x + 6 pe Z11
cu ajutorul Algoritmului El Gamal. Calculăm punctele curbei eliptice pentru a
vedea cine sunt elementele grupului G. Calculele se fac în Z11.
2 3 2
11.
2 3 2
11
2 3 2
1 2
2 3 2
1
0 0 0 6 mod11 6mod11 6
1 1 1 6mod11 8mod11 8 .
2 2 2 6mod11 5mod11 5 . 4, 7 2,4 ; 2,7 .
3 3 3 6mod11 3mod11 3 . 5
x y ecuaţiay carenuaresoluţiiînZ
x y y nuavemsoluţiiînZ
x y y sol y y
x y y sol y
2
2 3 2
11
2 3 2
1 2
, 6 3,5 ; 3,6 .
4 y 4 4 6 mod11 8mod11 8
5 5 5 6mod11 4mod11 4 . 2, 9 5,2 , 5,9 .
y
x y nuavemsoluţiiînZ
x y y sol y y
Deci punctele de pe curbă sunt:
{(2,7);(2,4);(3,5);(3,6);(5,2);(5,9);(7,2);(7,9);(8,3);(8,8);(10,2);(10,9)}.
Deci cardinalul grupului este 13 număr prim. Grupul E este grup ciclic
(numărul de elemente este 13). Generatorul grupului este punctual (2,7)
element public.
Cheia privată de descifrare, notată prin d, este o valoare între 1 şi p-1 adică 12.
Cheia publică, notată prin , se obţine din şi exponentul secret d prin
formula:
d .
Operaţia de cifrare a mesajului M cu ajutorul cheii (secrete) k este:
, , .E M k k M k
Operaţia de descifrare pentru a obţine M este :
1 2 2 1, .kD y y y dy
73
Fie d = 3. Atunci avem:
3 2,7 2,7 2,7 2,7 .d
Acum folosim proprietatea de adunare a punctelor pe curbe eliptice cu
formulele date de:
,
cu
,
unde a este coeficientul lui x în ecuația curbei
1 1 2 2
2
1
1
2
3 1 2
2
3 1 3 1
3 2,7 2,7 2,7 2,7 2 ,7 , 2, 7.
3 3 4 1 2 2 4 8(mod11) 8.
2 2 7 3 3 4 12
(mod11) 64 2 2 mod11 60 mod11 5.
mod11 8 2 5 7 mod11 5,2 .
2,7 2,7 5,7 .
unde x y x y
x a
y
x x x
y x x y
DeciP Q P P
Acum adunăm (P + P) + P = (5,2)+(2,7). Schimbăm formula de calcul de
data asta deoarece în rolul lui P este (5,2) şi în rolul lui Q este (2,7).
Atunci avem:
În final obținem .
Considerăm valoarea aleatoare k = 4, criptăm cu ajutorul formulei:
74
2 2
11 1 2 2
1
2
3 1 2
, 10,9 ;4 4 2,7 ; 10,9 4 8,3
4 2,7 2,7 2,7 2,7 2,7 5,3 5,3 10,2 .AiciaplicămformulaîncazulP Q
2,7 2,7
.......
3 3 2 1 13 2 2 4 8......x 8 mod11 .
2 2 7 14 3 3 4 1
mod11
E M k M
x ax y y
y
x x x
2
2
3 1 3 1
1 1 2 2
2
1
1
8 2 2 mod11 60 mod11 5.
mod11 64 2 4 7 mod11 76 mod11 10.
4 8,3 8,3 8,3 8,3 8,3 7,5 7,5 2,4 .
8; 3; 8; 3 :
3 3 64 1 193mod11 1. :
2 2 3 6
:
y x x y
x y x y
x aAplicămformulacunotaţiileconsacrate
y
Atunci
2
3 1 2
3 1 3 1 3 3
1 1 2
;
mod11 1 8 8 mod11 7 mod11 7.
mod11 6 mod11 5 mod11 5. , 7,5 .
10,2 ; 10,9 2,4 Re ;
10,9 2,4 : x 2, 9; 2,
cîndP QşiatuncicîndP Q
x x x
y x x y x y
petămformulaîncădedouăori
Odatăpentru cazulP Q y x
2
2 1
2 1
2
3 1 2
3 1 3
1 1 2 2
2 1
2 1
4.
4 9 1 1 6mod11 mod11 6 mod11 6.
2 10 2 2 6
mod11 3
mod11 5 10,9 2,4 3,5 . :
10,2 2,6 10, 2; 2, 6 .
6 2 6mod11 mod11 5
2 10 12
y
y yAtunci
x x
x x x
y x x y Atunciavem
cux y x y cazulP Q
y y
x x
.
, 10,9 ; 3,5 .ÎnfineavemE M k
Exemplul 2.
Să descifrăm mesajul ((10,2);(3,5)) ştiind că a fost cifrat cu algoritmul El
Gamal utilizînd curba eliptică publică E.
E: y = x + x + 6 pe Z11 şi cheia privată d = 3.
Mesajul este M = y2 – dy1 = (3,5) - 3(10,2).
75
Calculăm:
2 2
11 1 2 2
1
2
3 1 2
3 1 3 1
3 10,2 10,2 10,2 10,2 .
: 10,2 10,2
3 3 10 1 30110, 2; 10, 2. mod11 1.
2 2 2 4
mod11 19 mod11 8 mod11 3 mod11 3.
mod11 1 10 3 2 mod11
PentruînceputavemcazulcîndP Q
x ax y x y Atunci
y
x x x
y x x y
2 1
2 1
2 1
7 2 mod11 5 mod11 5.
10,2 10,2 10,2 3,5 10, 2 . .
;3 10,2 2,4 .
AtunciM y 3,5 3 10,2 3,5 2,4 3,5 2, 4 mod11
y yAtunciavem SuntemîncazulP Q
x x
Înfinalaplicămformulaadouaoarăcînd
P Qşigăsim
d y
încăod
1 1 2 2
2 1
2 1
2
3 1 2
3 1 3 1
3, 5; 2, 7
7 5 2mod11 2 mod11 9 mod11 9
2 3 1
mod11 .
mod11 .
şi ;
3,5 2,7 10,9 .
atăformulaP Qcux y x y
y ycu
x x
x x x
y x x y
devine
Exemplul 3.
Să se cifreze M = (3,4) utilizând curba eliptică (publică) E: y = x3 + 2x + 3(
mod 5).
a = 2, b = 3.
2 3
2 3
1
2 3
2 3 2
2 2 2
0 0 2 0 3 mod 5 3 mod 5 3 mod 5 .
1 1 2 1 3 mod 5 6 mod 5 1 1,4 mod 5 .
x 2 y 2 2 2 3 mod 5 15 mod 5 0 0 mod 5 .
3 3 2 3 3 mod 5 36 mod 5 1 1 1,4 mod 5 .
4 4 2 4 3 mod 5 75 mod 5 0 0
x y nuavemsoluţii
x y y
y
x y y y
x y y
0 mod 5 .y
Avem punctele pe curba eliptică E şi care formează grupul nostru ciclic. G
={(1,1);(1,4);(2,0);(3,1);(3,4);(4,0); }. Luăm ca generator pe = (1,1).
76
Cheia privată de descifrare, notată prin d 1,7 1 1,6 luăm d = 2.
Cheia publică, notată prin , se obţine din şi exponentul secret d prin
formula:
2 1,1d .
Operaţia de cifrare a mesajului M cu ajutorul cheii secrete K este:
, , .E M k k M k
Fie d = 2. Să determinăm:
1 1 2 22 1,1 1,1 1,1 1, 1; 1, y 1.cux y x
Aplicăm formula de adunare în cazul P = Q pe curbe eliptice.
2
3 1 2 3 1 3 1
2 2
1
1
3 1 2
3
mod5 ; mod5
3 3 1 2 5 5 3mod5 mod5 15 mod5 0.
2 2 1 2 2 3
0 mod5 0 1 1 mod5 2 mod5 3.
0 1 mod5 4. 3,4 .
x x x y x x y
x aunde
y
x x x
y
Considerăm valoarea aleatoare k = 3 se obţine:
, 3 , 3 3 ; 3,4 3 3,4 3 1,1 ; 3,4 3 3,4 .
3 1,1 1,1 1,1 1,1 .
E M k M
Pentru paranteza dreaptă se aplică formula în cazul P = Q, după care aplicăm
formula în cazul P Q dacă coordonatele sunt diferite.
2
11 1 2 2
1
2
3 1 2
3 1 3 1
2 11 1 2 2
2 1
3 2 3 1 2 5 31, 1; 1, 1 . mod 5 mod 5 0.
2 2 1 2 3
mod 5 0 1 1 mod 5 2 mod 5 3 mod 5 3
mod 5 1 mod 5 4 mod 5 4.
2 23 1,1 3, 4 1,1 .x 3, 4; 1, 1
3
xx y x y cazulP Q
y
x x x
y x x y
y ycazulP Q y x y
x x
2
3 1 2
3 1 3 1
mod 5 4.2
mod 5 16 3 1 mod 5 12 mod 5 2.
mod 5 4 3 3 4 mod 5 4 mod 5 1mod 5 1
3 1,1 2,1 .
x x x
y x x y
77
Calculăm 3(3,4)=[(3,4)+(3,4)]+(3,4).
2
1 1 2 2
2
3 1 2
3 1 3 1
1 1
3 3 2 4 23, 4 3, 4 ; 3, 4; 3, 4 mod 5 mod 5 3.
2 4 3 2
mod 5 9 3 3 mod 5 3 mod 5 3.
mod 5 3 3 3 4 mod 5 1 mod 5 1.
3, 4 3, 4 3,1 .Avem 4 3, 4 3, 4 3, 4 3, 4 3, 4 .
33, 1;
x y x y cazulP Q
x x x
y x x y
cazulP Q
xx y
2
1
1
2
3 1 2
3 1 3 1
3 9 2 29 29 3mod 5 mod 5 mod 5 2.
2 2 1 2 2 3
mod 5 4 3 3 mod 5 4 6 mod 5 2 mod 5 3.
mod 5 3 3 3 1 mod 5 0 1 mod 5 4.
Aunci : 4 3, 4 3, 4 .
: E ; 2,1 ; 3, 4
a
y
x x x
y x x y
Deci M k
Exemplul 4.
Să se descifreze mesajul: ((2,1);(3,4)), ştiind că a fost cifrat cu algoritmul El
Gamal, utilizând curba eliptică (publică):
E: y = x3 + 2x + 3 ( mod 5), a = 2, b = 3 şi cheia privată d = 2.
Mesajul clar determinat este M = y2 - dy1 = (3,4) - 2(2,1).
1 1
2
1
1
2 2
3 1 2
3 1 3 1
2
2 2,1 2,1 2,1 , 2, 1 .
3 3 2 2 14mod5 mod5 7 mod5 2.
2 2 1 2
: mod5 2 2 2 mod5 4 4 mod5 0
mod5 2 2 0 1 mod5 4 1 mod5 3 mod5 3.
2 2,1 0,3 0, 3 .
undex y suntemîncazulP Q
x a
y
Atunci x x x
y x x y
Deci
M y
1 1 2 2
2 1
2 1
2
3 1 2
3 1 3 1
2 2,1 3,4 0, 3 .
3, 4; 0, 3 . .
3 4 7 7 2mod5 mod5 mod5 mod5 14 mod5 4.
0 3 3 3 2
mod5 16 3 0 mod5 13 mod5 3
mod5 4 3 3 4 mod5 4 mod5 1.
M 3,1 .
undex y x y suntemîncazulPdif deQ
y y
x x
x x x
y x x y
78
7. PROBLEMA LOGARITMULUI DISCRET
Securitatea multor criptosisteme se bazează pe problema logaritmului
discret.
Dacă considerăm un grup ciclic G, de ordin n, cu g un generator al său,
atunci 132 ,....,,,1 nggggG . Pentru Gb , definim bglog logaritmul discret al
lui b în bază g ca fiind unicul număr 11 nx care verifică .xgb
Un caz particular a fost deja studiat şi anume situaţia în care grupul )( nZU
este ciclic .
În acest caz, un generator al grupului este rădăcina primitivă r, iar
logaritmul discret a fost numit index aritimetic. Dăm un exemplu, 17ZU este un
grup ciclic de ordin 16. Cum 16317 ord 3 este un generator sau, rădăcină
primitivă modulo 17. Deoarece )17(mod138134 , obţinem .413log3
Problema logaritmului discret, DLP se formulează astfel:
Considerăm un număr prim p , g un generator al grupului *
nZ ( rădăcină
primitivă modulo p) și un element *
PZb , să se determine 11 px pentru care
pgb x mod .
Dacă în locul lui *
pZ alegem un grup ciclic oarecare, spunem că am enunţat
problema generalizată a logaritmului discret, GDLP.
Subliniem un lucru important legat de sistemul de generatori diferiţi ai
grupului G, ciclic de ordin n, iar Gb obţinem relaţia:
bgbb gggg gggb
22121loglog
1
log
2
log
1
Din schimbarea bazei logaritmului găsim:
ngbb ggg modlogloglog 2121
De aici constatăm că un algoritm care calculează logaritmi relativi la baza
g1 poate calcula logaritmi în orice bază g, cu g un generator oarecare al
grupului.
79
Vom prezenta în continuare cei mai cunoscuți algoritmi de rezolvare a
DLP arătând calculele în detaliu. Grupul ciclic G fiind multiplicativ al unui corp
finit cu p elemente, deci un grup de ordin p - 1.
Algoritmul Shanks
Considerăm 1 pm . Dacă Ggbx
atunci x = cm + d, .1,0 mdc
Atunci avem: dcmdcmx ggggb
dcm ggb o înmulţim la dreapta cu dg şi obţinem
ddcmd gggbg
0ggbg cmd
cmcmd ggbg
mc
g
cm
g
d
g ggbg logloglog
mcgb
d
gg
loglog
mcdbg log
dmcgb log
Se creează două liste:
121
12
,..,,
....,,1
m
mmmm
bgbgbgb
ggg
și vedem pentru ce valori ale lui c şi d obţinem dcm bgg . Atunci obţinem:
.log dcmbb
80
Algoritm-Shanks
1. INPUT: g, p , b sunt cei de sus din teorie.
2. Pentru c = 0, …, m - 1, construieste un tabel cu mcgc, , care se ordonează
după a doua componentă.
3. Calculează 1g şi pune ba .
4. Pentru d = 0,… , m – 1 , execută :
4.1.Verifică dacă a este a doua componentă a unui element din
tabel.
4.2. Dacă mcga , returnează x = mc + d și se oprește.
4.3. Pune 1 aga .
Exemplul 1.
Considerăm:
*
7 , p 7 prim,m 1 7 1 6 2.G Z p
Atunci avem m = 4 şi în consecinţă:
0 , 2c d .
Folosim tabelul pentru a pune în practică algoritmul Shanks.
Observăm că pentru c = 1 avem 4 şi pentru d = 2 avem 4.
Deci c = 1 şi d = 2. Atunci putem scrie:
c 0 1 2
22c
1 4 2
d 0 1 2
30*2-d
2 1 4
81
2log 30 2 2 2 6c m d
Calculele sunt realizate în mod 7.
Exemplul 2.
Considerăm generatorii din Z11.
11
1 1 1 1
2 2 2 2
3 3 3 3
4
0,1,2.......10 2,3,5 deg
2 2 mod11 ...;5 5 mod11 ....;3 3 mod11 ...;4 4 mod11
2 4 mod11 ...;5 3 mod11 ...;3 9 mod11 ...;4 5 mod11
2 8 mod11 ...;5 4 mod11 ....;3 5 mod11 ...;4 9 mod11
2 5 mod11
Z şiB sistem eneratori
4 4 4
5 5 5 5
6
7
8
9
10
...;5 9 mod11 ...;3 4 mod11 ...;4 3 mod11
2 10 mod11 ...;5 1 mod11 ...3 1 mod11 ....;4 1 mod11
2 9 mod11
2 7 mod11
2 3 mod11
2 6 mod11
2 1 mod11
Aceasta este caracteristica generatorilor care permite efectuarea calculelor.
Exemplul 3.
log230.
Considerăm 29 0,1,2.....28Z clasele de resturi mod 29. Atunci avem:
29 1 28 5,0 c,d m 1,0 , 5m c d
C 0 1 2 3 4 5
25m 1 3 9 27 23 7
Facem tabelul pentru d.
D 0 1 2 3 4 5
30*2-d 1 15 22 11 20 1
82
Atunci avem: c = 0 şi d = 5. Deci log230 = m*c + d = 5*0 + 5 = 5.
Calculele:
5 0 0 5 1 5 2
5 3 5 4
5 5
0 1 2
2 2 mod 29 1;2 mod 29 32 mod 29 3;2 mod 29 1024 mod 29 9;
2 mod 29 32768 mod 29 27;2 mod 29 1048576 mod 29 23;
2 mod 29 33554432 mod 29 7 :
15 15 1530 2 mod 29 1;30 2 mod 29 15;30 2 mod 29 mod 29 mod 29 22;
2 2 15
3
4
30 15 15 22 33030 2 mod 29 mod 29 mod 29 mod 29 mod 29 11;
8 4 4 22 88
30 15 15 1130 2 mod 29 mod 29 mod 29 mod 29 165 mod 29 20.
16 8 88
REPREZENTĂRI DE GRUP.
Cât de dificilă este rezolvarea problemei logaritmilor discreți? Depinde de
reprezentarea grupului!
Se consideră grupul (Zp*, ∙) și grupul (Zp-1, +). Se ia un generator g al lui pZ *
şi se definește aplicația:
( ,1pZ , +) → (Zp*, ∙): x → (x) = gx mod p.
Este clar că:
1. (x + y mod p) = ( (x), (y)) mod (p – 1)
2. af (a) = ( i mod p) mod (p – 1)
3. ≡ i mod p ≡ a ( ) mod (p – 1)
Este ușor de rezolvat congruențele liniare! Înseamnă că este ușor și a rezolva
problema logaritmilor discreți ? Nu! A stabili izomorfismul înseamnă a găsi
generatorul! Dar sunt prea mulți generatori posibili!
83
LOGARITMI DISCRETI în Z*
11.
Atacuri la logaritmii discrete
Atacurile care urmează au în vedere descompunerea:
k
kppppp
...1 321
321
Așadar, algoritmul Pohlig - Hellman cere factorizarea numărului p – 1.
84
O metodă generală
Se consideră o permutare f: X → Y a unei mulțimi de n elemente X, o permutare
fără puncte fixe, adică f(x) ≠ x pentru toti x-ii.
Exemplu: f:Zp* → Zp*: u → ∙u.
Fie definită orbita lui x X ca Orb f(x) = [x, f(x), f2(x), …, fn(x)]. Fiind dat un y
Orbf(x), să se găsească un întreg k astfel încât y = fk(x).
Se pune m = n . Prin împărțirea euclidiană, orice întreg a < n este de forma a
= qm + r, cu 0 ≤ q, r < n. Așadar:
fa(x) = f
qm+r(x) = f
qm(f
r(x)) = f
m◦…◦f
m(f
r(x))
Se calculează (r, f-r(y)) pentru r ≤ m și se sortează după coordonata a doua. Se
calculează de asemenea (q, fqm
(x)) pentru q ≤ m și se sortează după a doua
coordonată.
Se găsesc două perechi (q, fqm
(x)), (r, f-r(y)) care au a doua coordonată identică,
adică f-r(y) = f
qm(x). Decurge de aici că y = f
qm+r(x). Timpul de căutare este O ( n
) .
LOGARITMI DISCREŢI ÎN Zp*
Instanță a problemei: p prim, a generator pentru Zp* și b un element din Zp*
Obiectiv: Stabilirea unui k ≤ p – 1 unic astfel încât = k mod p (se introduce
notația logk ). O cale de a obține pe k poate consta în a genera toate puterile
lui ( , 2 , 3 ,…) și a reține exponentul corect printr-o explorare exhaustivă.
Aceasta consumă un timp O(p).
O altă cale poate fi utilizarea metodei generale precedente pentru a reduce
timpul de căuatre la O n . Aceasta este cunoscută ca algoritmul lui Schank.
85
ALGORITMUL LUI SCHANK
Algoritmul lui Schank ( ,,p ): Dacă 1 pm atunci se observă că fiecare
întreg a < p – 1 este de forma: a = qm + r, cu 0 ≤ q, r ≤ m – 1. Astfel, a ≡ (am)
q
r mod p.
1. Se calculează (r, r mod p) pentru r = 0, 1, …, m – 1 și se sortează după
coordonata a doua.
2. Se calculează (q, mq mod p) pentru q = 0, 1, …, m – 1 și se sortează după
coordonata a doua.
3. Se găsesc două perechi identice la a doua coordonată, adică (r, r mod p)
și (q, mq mod p) astfel încât r ≡ mq mod p. Timpul de execuție a
algoritmului este O( n ) .
Exemplu: Fie p = 809 și se urmărește calcularea lui log3(525). În cazul acesta a
= 3, = 525, 29808 m si .99808mod29 . Se tabelează apoi (i, 99i
mod 809) și (i, 525∙(3i)
-1 mod 809), pentru i = 0, …, 28.
(10,644) și (19,644) au acceași a doua coordonată.Așadar:
309191029525log3 .
86
Bibliografie
[1] Debdeep Mukhopadhyay,” The Discret Logarithm Problem,”IIT Kharagpur,pp.437- 480,
June 1996.
[2] David Aspinall,Cryptography IV:Asymmetric Ciphers Computer Security Lecture7,
School of Informatics University of Edinburgh,31 st January 2011.
[3] Debdeep Mukhopadhyay,Elliptic Curve Cryptography,Adept of Computer Sc and Engg
IIT Madras,2011.
[4] Dumitru Buşneag, Florentina Chirtes,Dana Piciu, “Complemente de Aritimetică Şi Teoria
Elementară A Numerelor,2007.
[5] Alexandru Dincă,’’Algebra Pentru Perfecţionarea Profesorilor, “ 1983
[6] Constantin Popescu ,’’Introducere în Criptografie,”Departamentul de Matematică şi
Informatică.
[7] (Capitolul 17),’’Sistemul de cifrare EL Gamal bazat pe curbe eliptice.’’
[8] Ion.D.Ion,Lucian Morogan, “ Criptare şi Decriptare,” Departamentul de Matematică şi
Informatică.