Cheie – informatie secreta folosita pentru criptare si decriptare.Sisteme simetrice – aceiasi cheie este folosita si la criptare si la decriptareSisteme asimetrice – cheie diferita la criptare fata de decriptare.

Primitive cu cheie simetrica Cifruri cu cheie simetrica

- Cifruri block- Cifruri sir

Functii hash de lugime variabila Semnaturi Siruri pseudoaleatoare

Primitive cu cheie publica Semnaturi Cifruri cu cheie publica

CRIPTAREA CU CHEIE SIMETRICADefinitie: Consideram o schema de criptare in care criptarea se face cu cheia e iar decriptatarea se face cu cheia d, M este multimea mesajelor clare, C multimea mesajelo criptate iar K multimea cheilor de criptare. Schema de criptare este cu cheie simetrica daca este usor de calculat d cunoscind e si invers, e este usor de dedus din d.Observatie. Cea mai practica scheme cu cheie simetrica este cea in care e=d. Schema de criptare cu cheie simetrica se mai numeste si: schema single-key, one-key, private-key sau conventional-key.

O comunicare care foloseste o criptare cu cheie simetrica poate fi descrisa de:

PROBLEMA DISTRIBUTIEI - Gasirea unei metode eficiente de schimbare sigura a cheilor.

Scheme de criptare cu cheie simetrica:– Cifruri block– Cifruri stream

CIFRURI BLOCK

Definitie: Un cifru block este o schema de criptare care desface textul sursa in cuvinte de lungime t peste un alfabet A, cuvinte numite blocuri, si cripteaza un bloc la fiecare moment.

Cifruri block:

– Cifrul substitutie

– Cifrul transpozitie

– Cifrul produs, o combinatie a primelor doua.

CIFRURI de SUBSTITUTIE SIMPLA

Definitie: Fie A un alfabet de q simboluri si M multimea tuturor sirurilor de lungime t peste A. Fie K multimea tuturor permutarilor peste A . Definim pentru fiecare e Î K criptarea Ee de forma:

Ee(m) = ( e(m1), e(m2), . . . , e(mt) ) = (c1, c2,. . . , ct) = c, unde m=m1, m2, . . . ,mt Î M. Pentru a decripta

c=(c1, c2,. . . , ct) se calculeaza permutarea inversa d=e-1

Dd(c) = ( d(c1), d(c2), . . . , d(ct) ) = (m1, m2,. . . , mt) = m.

Ee cifru de substitutie simpla sau cifru de substitutie mono-alfabetica.

EXEMPLE DE CIFRU DE SUBSTITUTIE SIMPLA

Ex 1. Fie A= {A,B,C, . . . ,Z} iar M si C multimile de cuvintelor formate din literele din A de lungime 5 (lungimea blocului). Algoritmul de cifrare este cel al lui Cezar (shift by 3) – se muta primele 3 litere la final

Mesajul m = CIFRU LACES TAEST ECIFR ULLUI CEZAR Este criptat prin c = E(m), c = FLIUY ODFHU XDHVX HFLIU YOOYL FHCDU

Ex 2. Patratul istoric (Bigramme)

Fara cheie Cu cheia CIFRU

Textul cifrat “1224224211323215” inseamna:

“BIGRAMME” fara cheie si “ IEBOCJJU” cu cheie

Obs1. Numarul de cifruri de substitutie distincte este q! si nu depinde de lungimea blocului.

Obs2. Daca alfabetul folosit este alfabetul englez cu 26 de litere atunci exista 26! ≈4 x 1026 chei si cifrul poate fi spart usor. Asta se face calculind frecventa aparitiei simbolurilor in textul cifrat (in engleza cea mai mare frecventa o are litera e) si observind ca distributia frecventelor literelor este aceiasi in textul sursa si in cel cifrat.

CIFRURI DE SUBSTITUTIE HOMOMORFICA

Definitia 4. Fiecarui simbol a Î A i se asociaza o multime H(a) de siruri de simboluri de lungime t, cu restrictia ca multimile H(a) sunt disjuncte doua cite doua. Un cifru de substitutie homomorfica inlocuiescte fiecare simbol a dintr-un bloc de mesaj text printr-un sir ales aleator din multimea H(a). Pentru a decripta mesajul c format din t simboluri trebuie determinat un a Î A astfel incit c Î H(a).

Cheia cifrului consta din multimile H(a) pentru a Î A .

EXEMPLU DE CIFRU DE SUBSTITUTIE HOMOMORFIC

A = {a,b}, H(a) = {00,10}, H(b) ={01,11}. Blocul ab dintr-un mesaj text se cripteaza in una din formele {0001,0011,1001, 1011}. Pentru blocurile de lungime 2 variantele posibile sunt:

aa {0000, 0010,1000,1010}

ab {0001, 0011,1001, 1011}

ba {0100, 0110, 1100,1110}

bb {0101, 0111, 1101,1111}

Observatie. Desi mesajul text se poate cripta in mai multe feluri, pornind de la mesajul cifrat se obtine un unic mesaj text.

Observatie. In cifrul de substitutie homomorfica frecventa devine mai uniforma si de aceea este mai greu de spart.

CIFRUL DE SUBSTITUTIE POLIALFABETICA

Definitia 5. Un cifru de substitutie polialfabetica este un cifru bloc cu lungimea blocului t peste un alfabet A avind proprietatile:

(i) Spatiul cheilor K, este format din toate multimile ordonate de permutari de cite t elemente (p1,p2,...,pt), unde fiecare permutare pi, este definita pe multimea A.

(ii) Criptarea mesajului m=(m1 m2. . . mt) in raport cu cheia e=(p1, p2,. . . , pt) este Ee (m) = ( p1(m1

)p2( m2 ). . . pt(mt) )

(iii)Cheia de decriptare asociata lui e= (p1,p2,...,pt),este: d= (p1-1,p2

-1,...,pt-1),

EXEMPLU DE CIFRU DE SUBSTITUTIE POLIALFABETIC

Cifrul Vigenère- A= {A,B,C, . . . ,Z} , t=3. Alegem e= (p1,p2, p3),unde :

– p1 asociaza fiecarei litere a 3-a litera spre dreapta

– p2 asociaza fiecarei litere a 7-a litera spre dreapta

– p3 asociaza fiecarei litere a 10-a litera spre dreapta

Daca m= ACE STA EST ECI FRU LVI GEN ERE

c= DJO VBK HAE HJS IZF ODS JOY HZO

Observatie. Fata de cifrul de substitutie simpla, cifrul de substitutie polialfabetica nu pastreaza frecventa simbolurilor. Totusi criptanaliza nu este semnificativ mai complicata. De fapt cind lungimea blocului, t, este determinata, textul cifrat se imparte in t grupuri, unde fiecare grup i consta din literele textului cifrat derivate prin permutarea pi, si se determina frecventa pe fiecare grup in parte.

CIFRURI TRANSPOZITIE

Cifrul transpozitie permuta simplu simbolurile dintr-un bloc.

Definitia 6. Consideram o schema de criptare cu cheie simetrica cu cifrul block, unde lungimea blocului este t. Fie K multimea tuturor permutarilor multimii {1,2, . . . ,t}. Pentru fiecare e Î K definim functia de criptare:

Ee (m) = ( me(1) me(2) . . . me(t)), unde m=(m1 m2. . . mt) ∈ M (spatiul mesajelor).

Multimea tuturor transformarilor de aceasta forma este un cifru de transpozitie simpla. Cheia de decriptare corespunzind lui e este inversa permutarii d=e-1. Pentru a decripta

c =(c1 c2. . . ct), se calculeaza Dd (c) = (cd(1) cd(2) . . . cd(t) ).

A= {A,B,C, . . . ,Z} , t=3 si e permutarea e(1)=3, e(2)=1, e(3)=2

Daca m= ACE STA EST ECI FRU LLU ICE ZAR Atunci c= EAC AST TES IEC UFR ULL EIC RZA

Observatie. Un cifru cu transpozitie simpla pastreaza numarul de simboluri de un anumit tip in bloc si astfel criptanaliza este usor de facut.

Ex 2. Transpozitia pe coloane

Pentru a cripta un text se executa pasii:

Se scrie textul in linii de cite k elemente;

Se permuta coloanele cu permutarea s Î Sk;

Se citeste textul cifrat pe coloane.

Pentru a cripta “transpozitiapecoloane”, cu k=7, cu s=(3 2 4 1 5 6 7 ):

t r a n s p o a r n t s p o

z i t i a p e t i i z a p e

c o l o a n e l o o c a n e

“atlrioniotzcsaappnoee”

COMPUNEREA CIFRURILOR

Definitia 7.Fie S,T si U multimi finite si functiile: f : S T g :T U

Compunerea functiilor g cu f este o functie g ○ f : S U si este definita de g ○ f (x) = g( f(x) ) pentru toti x ∈ S.

COMPUNEREA INVOLUTIILOR

Involutia este o functie, f, egala cu inversa sa, f-1 , adica f = f-1 si deci: f(f(x)) = x

Observatie. Compunerea a doua involutii nu este, in mod necesar, o involutie.

Involutiile pot fi compuse pentru a da niste functii mai complicate a caror inversa este usor de aflat (important din punct de vedere al decriptarii!).

Propozitie. Fie involutiile Ek1, Ek2,. . ., Ekt. Inversa functiei Ek, definita de: Ek = Ek1Ek2 . . . Ekt

este functia Ek-1

= EktEkt-1 . . . Ek1

CIFRURI PRODUS

Cifrul de substitutie simpla si cel de transpozitie nu produc, individual, un nivel foarte ridicat de securitate dar combinarea lor conduce la un cifru puternic. Cele mai practice sisteme cu cheie simetrica sunt cifrurile produs. Un exemplu de cifru produs este Ek1Ek2 . . . Ekt unde fiecare Eki este sau un cifru de substitutie sau unul de transpozitie.

Runda - Compunerea unei substitutii cu o transpozitie.

Ex. Fie M = C = K multimea tuturor sirurilor binare de lungime 6 ( M - 26 = 64 elemente) , m=(m1

m2. . . m6)

Ek(1) (m) = m ⊕ k, unde k ∈ K, (⊕ sau exclusiv)

Ek(2) (m) = (m4 m5m6 m1 m2m3).

Ek(1) - cifru de substitutie polialfabetica, Ek

(2) -cifru de transpozitie. Ek(1) Ek

(2) este o runda.

CONFUZIE SI DIFUZIE

Definitia 8. O substitutie dintr-o runda se spune ca adauga confuzie in procesul de criptare iar o transpozitie dintr-o runda adauga difuzie.

Confuzia intentioneaza sa faca relatia dintre cheie si textul cifrat cit de complexa se poate iar difuzia se refera la rearanjarea sau imprastierea bitilor in mesaj.

O runda trebuie sa adauge procesului de criptare si confuzie si difuzie.

Cele mai multe sisteme de cifrare block moderne aplica un numar de runde succesive pentru criptarea mesajului text.

CIFRURI STREAM

Cifrul Stream este, intr-un anume sens, un cifru block in care lungimea blocului este 1. Intr-un astfel de cifru transformarea de criptare se poate schimba la fiecare simbol din textul sursa.

O astfel de cifrare este utila din doua puncte de vedere:

– nu se propaga erorile la fel ca intr-un cifru block;

– se utilizeaza atunci cind datele trebuiesc procesate simbol cu simbol (de exemplu atunci cind echipmentul folosit nu are memorie suficienta).

Cifrul cu cheie simetrica de tip stream (flux) este un cifru foarte rapid, mult mai rapid decit orice cifru simetric de tip bloc.

Criptarea oricarui text clar folosind un cifru bloc produce intotdeauna acelasi text criptat, pe cind criptarea cu cifrul stream poate produce texte cifrate diferite din acelasi text clar.

Definitia 1. Fie K spatiul cheilor pentru o multime de transformari de criptare. Un sir de simboluri e1 e2. . . ei Î K se numeste un keystream (flux de chei).

Definitia 2. Fie A un alfabet de q simboluri si fie Ee un cifru de substitutie simpla cu lungimea blocului egala cu 1, unde e Î K. Fie m1 m2m3 . . . sirul textului sursa si e1e2e3 . . . un keystream din K. Un cifru stream transforma textul sursa intr-un text cifrat c1c2c3 . . . unde ci = Eei(mi). Daca di indica inversa lui ei atunci Ddi (ci) = mi decripteaza textul cifrat.

Observatie. Sirul cheilor, keystream, poate fi generat aleator sau poate fi folosita o procedura de generare a lui pornind de la un mic sir initial, numit seed (graunte, bob, germene) sau de la un seed si de la simbolurile anterioare ale textului cifrat. Un astfel de algoritm se numeste un keystream generator.

Daca Keystream-ul este generat independent de textul clar se obtine un Synchronous stream cipher;

Daca Kysteam-ul depinde de datele de intrare se obtine un Self-Synchronizing stream cipher;

CIFRUL VERNAM

Un streamcipher foarte simplu si usor de implementat.

Definitia 3. – Cifrul Vernam este un cifru stream definit pe un alfabet, A = {0, 1}. Un mesaj binar m1 m2 . . . mt este transformat cu un streamkey binar k1 k2 . . . kt de aceiasi lungime care produce un text cifrat c1 c2 . . . ct unde:

ci = mi Å ki , 1 ≤ i ≤ t

Daca sirul cheilor este ales aleator si nu mai este folosit niciodata, atunci cifrul Vernam este numit un sistem one-time sau un one-time pad.

In cifrul Vernam exista doua cifruri de substitutie: E0 si E1, unde E0 este substitutia identica care trimite 0 in 0 si 1 in 1, iar E1 este substitutia care trimite 0 in 1 si 1 in 0, adica negatia caracterului mi . Atunci cind sirul cheilor contine un 0 se aplica cheia E0 iar in rest cheia E1.

EXEMPLU DE CIFRARE CU CIFRUL VERNAM

Consideram mesajul text binar de forma:

m = 00011011,

si sirul de chei:

k = 10010101

Atunci textul cifrat va fi obtinut printr-un „sau exclusiv“, bit

cu bit, dintre m si k, m Å k :

c = 10001110

Cheia de decriptare este identica cu k:

m = c Å k ;

CRIPTANALIZA in CIFRUL VERNAM

Observatia 1. Daca sirul de chei este reutilizat atunci exista posibilitati de a ataca sistemul. De exemplu, daca c1 c2 . . . ct si c‘1 c‘2 . . . c‘t sunt doua siruri de text cifrat cu acelasi keystream k1 k2

. . . kt atunci:

ci = mi Å ki , c‘i = m‘i Å ki

Deci ci Å c‘i = mi Å m‘i .(pentru ca ki Å ki =0, adica transformarea identica). In acest caz redondanta in ultimul dintre texte poate permite criptanaliza.

Observatia 2. Din punct de vedere teoretic un cifru one-time pad este imposibil de spart. Adica daca un criptanalist are sirul cifrat c1 c2 . . . ct in care s-a folosit un streamkey ales aleator atunci el nu poate decit sa deduca ca este vorba de un sir binar de lungime t.

Un astfel de cifru este utilizat pe linia de comunicatie dintre Washinton si Moscova.

Evident, transportul cheii a fost realizat printr-un curier de incredere.

DEZAVANTAJE ALE CRIPTARII CU CIFRUL STREAM

Streamkey intr-un cifru stream se foloseste de preferinta o singura data (one-time pad) si trnsmiterea sa necesita masuri exceptionale de securitate.

Cheia secreta (streamkey) este la fel de lunga ca si sirul de biti ai textului clar. Rezulta mari probleme de management al cheii.

Desi este complet sigur cifrul one-time pad este impracticabil !!!!!!

Algoritmi de criptare simetrici

1. DES (Data Encryption Standard) - lungimea cheii de criptare este de 56 biti;- a fost dezvoltat de IBM si devenit standard federal in 1976;- a fost folosit ca algoritm oficial de criptare pana in 2001 de catre guvernul USA;- in acest moment se considera nesigur, el fiind "spart" intre timp (cheia DES poate fi aflata in mai putin de 24 ore folosind hardware extrem de performant si/sau procesare distribuita.

2. 3DES (3 Data Encryption Standard)- lungimea cheii de criptare este de 56 biti;- reprezinta acelasi algoritm ca si DES doar ca textul in clar trece prin 3 runde de criptare pana cand se ajunge la textul criptat (chipher-text). De fiecare data se foloseste o alta cheie, deci exista in total 3 chei.- este considerat nesigur, a fost "spart";

3. AES (Advanced Encryption Standard)- lungimea cheii de criptare este de 128, 192 sau 256 biti;- se mai numeste si Rijndael Algorithm dupa numele celor 2 inventatori belgieni: Joan Daemen si Vincent Rijmen;- este standardul oficial de criptare al guvernului USA incepand cu anul 2001 (NIST);- este considerat sigur, nu a fost inca "spart", nu se cunosc bug-uri si este folosit in aplicatii enterprise cu succes;- Bruce Schneier (unul dintre cei mai cunoscuti criptografi din lume si care a dezcoperit o serie de algoritmi) a declarat: "I do not believe that anyone will ever discover an attack that will allow someone to read Rijndael traffic";

4. Blowfish- a fost dezvoltat de catre Bruce Schneier in 1993;- lungimea cheii de criptare este intre 32 si 448 biti;- este considerat sigur, nu a fost inca "spart", nu se cunosc bug-uri si este folosit in aplicatii enterprise cu succes;

5. Twofish- a fost dezvoltat de catre Bruce Schneier in 1998;- lungimea cheii de criptare este de 128, 192 sau 256 bitieste unul dintre finalistii concursului pentru alegerea noului standard AES;

6. Rivest Ciphers (aka Ron's Code)- reprezinta o familie de algoritmi de criptare dezvoltati de americanul Ronald Rivest. Este cel care a dezvoltat si algoritmi de hashing MD2, MD4 si MD5;- aceasta familie de algoritmi cuprinde RC1, RC2, RC3, RC4, RC5 si RC6. Cei mai importanti sunt RC4 folositi in produse comerciale si RC6 unul dintre finalistii concursului pentru AES;

CRIPTOGRAFIE CU CHEIE PUBLICA

Ideea criptarii cu cheie publica li se datoreaza lui Diffie si Hellman si rezolva o deficienta a criptarii cu cheie simetrica si anume transmiterea cheii. Aceasta pentru ca in criptarea cu cheie simetrica in momentul in care se cunoaste cheia de criptare, e, se poate foarte usor calcula inversa ei, cheia de decriptare, d.

Daca insa calculul functiei inverse, d, devine o problema imposibila din punct de vedere computational, cel putin pentru majoritatea situatiilor, atunci functia e se numeste one-way si criptarea este o criptare cu cheie publica. In acest caz cheia de criptare poate fi cunoscuta de orice persoana, devine cheie publica, fara insa ca o persoana sa poata descifra mesajele criptate de alta persoana.

Fie {Ee: e Î K} o multime de transformari de criptare si {Dd: d Î K} multimea de transformari de decriptare corespondenta, unde K este spatiul cheilor. Consideram o pereche de transformari criptare/decriptare, (Ee, Dd), si presupunem ca fiecare pereche are proprietatea ca pentru un Ee

cunoscut si un text cifrat dat ,c, este practic imposibil sa gasim un mesaj m Î M astfel incit Ee(m)=c.

Aceasta implica faptul ca dat fiind un e este imposibil sa determinam cheia de decriptare corespunzatoare, d.

Aici Ee este vazuta ca o functie one-way, unde d este informatia trapdoor necesara pentru calcularea functiei inverse.

CRIPTARE UTILIZIND TECHINICILE DE CHEIE PUBLICA

Consideram o comunicare bi-partida intre Vlad si Ana ca in Fig.1. Vlad va alege o pereche de chei (e,d) si trimite catre Ana, cheia de criptare, e, numita cheie publica, pe un canal considerat nesigur. In acelasi timp pastreaza secreta cheia de decriptare, d, numita si cheie privata. Ana poate acum sa-i trimita lui Vald mesajul m prin aplicarea transformarii de criptare Ee(m)=c, folosind cheia publica, e. Vlad descifreaza textul cifrat c prin aplicarea transformarii inverse Dd determinata in mod unic de cheia privata, d.

Adversar pasiv

Sursa cheii

Decriptarea Dd(c)=m

Destinatie

d

m

Decriptarea Ee(m)=c

Text sursa

m

c

Canal nesecurizat

Canal nesecurizat

Vlad Ana

Pentru ca nu este nevoie ca cheia de criptare, e, sa fie secreta, ea poate fi facuta publica. In aceste fel orice entitate poate sa transmita lui Vlad un mesaj cifrat pe care, insa, numai Vlad il va putea descifra. Figura 2 ilustreaza aceasta idee, unde A1, A2 si A3 sunt entitati distincte.

EXEMPLU DE UTILIZARE A CRIPTARII CU CHEIE PUBLICA

Definitia 1. Consideram o schema de criptare formata dintr-o multime de transformari de criptare si de decriptare {Ee: e Î K} respectiv {Dd: d Î K}. Metoda de criptare se numeste schema cu cheie publica daca in fiecare pereche (e,d) o cheie, e, (cheia publica) este facuta publica in timp ce cheia d, (cheia privata) este tinuta secreta. Pentru ca schema sa fie sigura trebuie ca d sa fie practic imposibil de calculat din e.

PROCEDURA DE CHEIE PUBLICA MODIFICATA

Presupunem ca criptosistemul este comutativ adica orice compunere a cheilor publice eA, eB si deasemenea orice compunere a inverselor sale este comutativa. Presupunem ca A vrea sa-i trimita un mesaj, w, lui B. Atunci asta se poate intimpla conform cu urmatorul protocol:

– A trimite eA (w) lui B;– B ii trimite inapoi eB (eA (w));– A trimite dA (eB (eA (w))) = dA (eA (eB (w))) = eB (w) lui B;– B decripteaza dB (eB (w))=w.

In acest fel A si B pot comunica fiecare cunoscind cheia publica si cheia sa privata.

CHEIE PRIVATA SI CHEIE SECRETA

Conventie. Numele de cheie privata (care este tot o cheie secreta!!) este asociat cu notiunea de criptosistem cu cheie publica, iar numele de cheie secreta este asociat cu notiunea de criptosistem cu cheie simetrica.

Dd(c1)=m1

Dd(c2)=m2

Dd(c3)=m3

Ee(m1)=c1

Ee(m2)=c2

Ee(m3)=c3

c1

e

c2

c3

e

eVlad

A1

A2

A3

Acest lucru ar putea fi justificat de urmatorul fapt: la un secret iau parte mai multe parti pe cind o cheie este privata numai daca o singura parte o cunoaste.

Observatie. Exista multe scheme cunoscute despre care se crede ca sunt metode sigure de criptare cu cheie publica dar nu s-a demonstrat inca faptul ca ele sunt intradevar sigure!

NECESITATEA AUTENTIFICARII IN SISTEME CU CHEIE PUBLICA

EXEMPLU DE FALS PROTOCOL

Un adversar poate pacali entitatea B trimitind entitatii A o cheie de criptare e’, Aceasta cheie este privita de A, incorect, ca fiind cheia publica a lui B. Adversarul intercepteaza mesajul criptat de la A la B, il decripteaza cu propria lui cheie privata, d’, iar apoi il recripteaza cu cheia publica a lui B, e. Mesajul astfel obtinut este trimis lui B, ca si cind ar fi mesajul trimis de A.

Din acest exemplu rezulta necesitatea autentificarii cheii publice, care conduce la autentificarea intregului sistem. Adica A trebuie sa fie convinsa ca foloseste cheie privata trimisa de B nu de un adversar.

SEMNATURI DIGITALE PRIN CRIPTARE CU CHEIE PUBLICA REVERSIBILA

Vom considera o clasa de semnaturi digitale care este bazata pe sisteme de criptare cu cheie publica de un tip particular

Sursa cheiiCriptare

Ee(m) = c

Decriptare

Dd’(c’) = m

Criptare

Ee’(m) = c’

Text sursa

Sursa cheii

Decriptare

Dd(c) = m

Destinatie

m

d

m

m

d’

c’

e’

ADVERSAR

A B

c

Daca Dd este o transformare de decriptarea care corespunde lui Ee atunci pentru cazul in care Dd si Ee sunt ambele permutari vom avea:

Dd (Ee(m)) = Ee ( Dd (m)) = m, m Î M

O schema de criptare cu cheie publica de acest tip se numeste reversibila. Se observa ca este esential ca M = C pentru ca relatia sa fie adevarata pentru orice m Î M; in caz contrar Dd (m) ar fi nedefinit pentru m ∉ C.

CONSTRUCTIA UNEI SCHEME DE SEMNATURA DIGITALA

1. Fie M spatiul mesajelor pentru schema de semnatura.

2. Fie C = M spatiul semnaturilor S.

3. Fie (e,d) o pereche de chei pentru o schema de criptare cu cheie publica.

4. Definim o functie de semnare SA ca fiind Dd, adica semnatura pentru mesajul m Î M este s = Dd

(m).

5. Definim functia de verificare VA prin:

true, daca Ee (s) = m

VA (m,s) =

false, in caz contrar.

SCHEMA DE SEMNATURA DIGITALA CU RECUPERAREA MESAJULUI

Schema de semnatura poate fi simplificata in continuare numai daca A semneaza mesajele cu o structura speciala, public cunoscuta. Fie M‘ o submultime a lui M unde elementele lui M‘ au o structura speciala, astfel incit M‘ contine numai o parte neglijabila din M.

De exemplu putem considera M multimea tuturor sirurilor binare de lungime 2n pentru un anume intreg, n, iar M‘ multimea sirurilor in care primii n biti sunt dublati in ultimele n pozitii (ex. 110110 ar fi un astfel de sir pentru n=3). Daca A semneaza numai mesajele din M‘ acestea sunt usor de recunoscut de un verificator.

Redefinim atunci functia de verificare:

true, daca Ee (s) Î M‘

VA (s) =

false, in caz contrar.

In acest caz A are nevoie sa transmita numai semnatura s pentru ca mesajul, m = Ee (s), va fi descoperit prin aplicarea functiei de verificare, VA (s). Figura 4. ilustreaza modul de functionare a acestui tip de semnatura.

Mesajele cu o structura speciala din M‘ se vor numi mesaje cu redundanta

FALSIFICAREA SEMNATURII

Modificarea prezentata anterior este mai mult decit o simplificare. Ea este cruciala pentru a reduce posibilitatea falsificarii semnaturii lui A.

Falsificarea poate fi facuta de orice entitatea B care selecteaza aleator o semnatura s din S si apoi aplica Ee pentru a obtine Ee (s) = u, pentru ca S=M si Ee este public cunoscuta. B poate apoi lua mesajul m=u si semnatura s si poate transmite (m,s) altei entitati. Este usor de observat ca in acest caz semnatura s pentru m pare o semnatura a lui A, dar la care A nu a luat parte. In acest caz se spune ca B a falsificat semnatura lui A (falsificare existentiala).

Daca M‘ contine numai o fractiune neglijabila de mesaje din M atunci probabilitatea ca o anume entitate sa falsifice o semnatura a lui A, in acest mod, este redusa.

SEMNATURI DIGITALE SI CONFIDENTIALITATE

Observatie. Desi schemele de semntura digitala bazate pe criptare cu cheie publica reversibila sunt atractive, ele cer o metoda de criptare. Exista, insa, situatii in care mecanismul de semnatura digitala este cerut dar criptarea este interzisa. In acest caz nu se poate folosi acest tip de schema de semnatura digitala.

SEMNATURA DIGITALA IN PRACTICA

Ee (s)

m‘

Accepta daca

m‘ M‘Mesaje sursa

M‘

s

e

d

m

Semnatarul A

Verificatorul B

Pentru ca o semnatura digitala sa fie utila in practica ea trebuie sa indeplineasca citeva cerinte:

1. Sa fie usor de calculat de catre semnatar;

2. Sa fie usor de verificat de catre oricine;

3. Sa aiba o rezistenta in timp adecvata, adica sa fie sigura computational la falsificare pina cind este necesar, in functie de scopul propus.

REZOLVAREA DISPUTELOR

Scopul unei semnaturi digitale este de a permite rezolvarea disputelor. De exemplu astfel de dispute ar fi daca o entitatea A ar nega la un moment dat ca a semnat un mesaj sau o alta entitate B ar afirma, in mod fals, ca o anumita semnatura apartine lui A. Pentru a rezolva o astfel de disputa este chemat un judecator, un trusted third party (TTP). TTP este o entitate agreata de toate partile implicate.

Daca A neaga ca mesajul m, primit de B a fost semnat de A, atunci B prezinta TTP-ului semnatura sA pentru m impreuna cu m. TTP decide in favoarea lui B daca VA(m,sA) = true si in favoarea lui A in caz contrar. Si A si B accepta decizia TTP daca au incrdere ca TTP a folosit VA si ca sA nu a fost compromisa.

CERINTE PENTRU REZOLVAREA UNEI DISPUTE DE SEMNATURA DIGITALA

Pentru ca o disputa de semnatura electronica sa fie rezolvata trebuie sa fie indeplinite urmatoarele:

1. SA si VA sa aiba proprietatile a) si b) ale functiilor de semnare si de verificare.

2. TTP sa aiba o copie autentica a lui VA..

3. Transformarea SA sa fie tinuta secreta.

S-ar putea ca, in practica, sa nu poata fi indeplinite toate aceste cerinte, de ex. 1, sau ca A sa afirme in mod fals ca semnatura sa a fost compromisa. Pentru a depasi aceste probleme este necesara o metoda de validare a perioadei de timp in care A a aceptat responsabilitatea transformarii de verificare. Analog cu acest lucru este situatia revocarii unei carti de credit (posesorul unei carti de credit este responsabil pentru operatiunile efectuate pina cind el reclama ca a pierdut sau i s-a furat cartea de credit).

Cele mai cunoscute sisteme de securitate bazate pe probleme calculatorii ın acest moment sunt:

Sistemul RSA: se bazeaza pe dificultatea descompunerii ın factori primi a numerelor mari (de sute de cifre). Este sistemul cel mai larg utilizat ın acest moment.Sistemul El Gamal: se bazeaza pe dificultatea calculului logaritmului discret ıntr-un corp finit.Sistemul Merkle - Hellman: primul sistem definit cu cheie publica, bazat pe problema {0, 1} a rucsacului, problema NP - completa.

Sistemul McEliece: este bazat pe teoria algebrica a codurilor, decodificarea unui cod liniar fiind de asemenea o problema NP - completa.Curbe eliptice: Sunt sisteme de criptare care ısi desfasoara calculele pe multimea punctelor unei curbe eliptice (ın locul unui inel finit Zn).

AVANTAJE SI DEZAVANTAJE ALE CRIPTARII CU CHEIE SIMETRICA SAU PUBLICA

AVANTAJE ALE CRIPTARII CU CHEIE SIMETRICA

1. Cifrurile cu cheie simetrica pot fi descrise ca avind o rata ridicata de transfer a datelor. Anumite implementari hard ating o rata de transfer de ordinul a sute de megabyti pe secunda, in timp ce implementari soft pot atinge rate de magabyti pe secunda.

2. Cheile pentru cifruri simetrice sunt relativ scurte.

3. Cifrurile cu cheie simetrica pot fi folosite ca primitive pentru a construi variate mecanisme criptografice (generatoare de numere pseudoaleatoare, functii de hash-de imprastiere- scheme de semnatura digitala).

4. Cifrurile cu cheie simetrica pot fi compuse pentru a produce cifruri mai puternice.

5. Cifrarea cu cheie simetrica are o istorie indelungata.

DEZAVANTAJELE CRIPTARII CU CHEIE SIMETRICA

1. Intr-o comunicarea intre doi parteneri cheia trebuie tinuta secreta la ambele capete.

2. Intr-o retea mare exista multe perechi de chei care trebuiesc administrate. In consecinta administrarea cheilor cere un TTP de incredere neconditionta.

3. Intr-o comunicare intre doua entitati A si B, practica criptografica cere ca cheile sa fie schimbate frecvent, probabil la fiecare sesiune de comunicare.

Mecanismele de semnatura digitala bazate pe cheia simetrica cer sau chei lungi pentru functia de verificare sau folosirea unui mecanism TTP.

AVANTAJE ALE CRIPTARII CU CHEIE PUBLICA

1. Numai cheia privata trebuie tinuta secreta, si asta numai de catre una din cele doua parti. Totusi cheia publica trebuie autentificata.

2. Administrarea cheilor pe retea cere prezenta unui TTP de incredere functionala, spre deosebire de TTP-ul de incredere neconditionata. TTP-ul poate functiona „off-line“, spre deosebire de celalalt in timp real.

3. O pereche de chei, cheie publica/cheie privata, poate fi utilizata o perioada indelungata de timp, de ex., mai multe sesiuni sau chiar citiva ani.

4. Multe scheme cu cheie publica produc mecanisme eficiente de semnatura digitala. Cheia folosita pentru functia de veificare este mai scurta decit cea pentru cheie simetrica.

DEZAVANTAJELE CRIPTARII CU CHEIE PUBLICA

1. Rata de transfer pentru cele mai populare metodele de criptare cu cheie publica este de citeva ori lenta decit pentru cele mai cunoscute scheme cu cheie simetrica.

2. Lungimea cheii este mai mare decit pentru criptarea cu cheie simetrica. Deasemenea semnatura cu cheie publica este mai lunga decit cea provenita din tehnicile cu cheie simetrica.

3. Nici o schema cu cheie publica nu s-a dovedit a fi sigura (acelasi lucru se poate spune si despre cifrul block). Cea mai sigura metoda cu cheie publica se bazeaza pe dificultatea (actuala) a unui mic numar de probleme din teoria numerelor.

4. Criptografia cu cheie publica este mai noua si deci mai putin folosita.

CONCLUZII

Criptarea cu cheie publica si cea cu cheie simetrica au avantaje si dezavantaje complementare care sunt expoatate de sisteme criptografice moderne.

Exemplu. Tehnicile de criptare cu cheie publica pot fi utilizate pentru transmiterea cheii intr-un sistem de criptare cu cheie simetrica, care poate fi utilizat pentru comunicarea intre doua entitati A si B.

In momentul de fata performanta criptarii cu cheie publica este inferioara celei cu cheie simetrica, fara insa sa existe nici o demonstratie in acest sens.

Din punct de vedere practic se pot evidentia urmatoarele:

Sursa cheii publicee

d

Criptare k‘ = Ee(k)

Sursa cheii simetrice

kk‘

Decriptare k = Dd(k‘)A B

– Criptografia cu cheie publica faciliteaza semnaturi digitale eficiente si un management eficient al cheilor.

– Criptografia cu cheie simetrica este eficienta pentru criptarea anumitor aplicatii de integritate a datelor.

DIMENSIUNILE CHEII PRIVATE SI ALE CELEI SIMETRICE

In sistemele cu cheie publica cheile private au lungimea mai mare (de ex. 1024 biti pentru RSA) decit cheia secreta (de ex. 64 sau 128 de biti) in sistemele cu cheie simetrica. In aceste fel cea mai eficienta forma de atac a sistemelor simetrice este cautarea exhaustiva, in timp ce pentru sistemele cu cheie publica exista variante mai scurte (factorizarea) decit cautarea exhaustiva.

Sistemele cu cheie simetrica au lungimea cheii de apoximativa 10 ori mai scurta decit la cele cu cheie publica.