Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

33
http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1
  • date post

    19-Dec-2015
  • Category

    Documents

  • view

    246
  • download

    8

Transcript of Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Page 1: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

http://ssc.users.ro

Curs 4 – Cifru bloc, semnatura digitala

Bogdan Carstoiu

1

Page 2: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Permutari si inverse

O functie f:{0,1}l→ {0,1}l este o permutare daca aceasta are o functie inversa f-1:{0,1}l→ {0,1}l care pentru orice x ce apartine la {0,1}l satisface relatia f-1(f(x))=x.

Altfel spus pentru orice y exista un unic x astfel incat f(x)=y.

Cifru bloc:Daca notam E:{0,1}Kx{0,1}l->{0,1}l ca fiind o functie care preia o cheie K

si o intrare x pentru a returna E(K,x) atunci

pentru fiecare K vom nota EK:{0,1}l->{0,1}l ca functia definita prin EK(x) = E(K,x).

Spunem ca E este un cifru bloc daca:• EK:{0,1}l->{0,1}l este o permutare pentru fiecare K, adica are o

inversa EK-1;

• EK, EK-1 sunt calculabile eficient si E-1(K,x)= EK

-1(x).

2

Page 3: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Exemple cifru bloc

Sa presupunem l=k si definim E:{0,1}Kx{0,1}l->{0,1}l prin EK(x) = E(K,x) = K + x.

Atunci EK are o inversa EK-1 cu EK

-1(y) = K+y. EK

-1(y)= EK-1(EK(x)) = EK

-1 (K+x)=K+K+x = x

Utilizare:• K<-{0,1}k;• K este cunoscut doar de parti (T-transmitator, R-Receptor), nu si de

atacator (A);• T si R utilizeaza Ek, algoritmul E este public;• Mesajele criptate sunt y1,y2,…

Probleme:• Greu de obtinut K de la y1,y2,…• Greu de obtinut xi de la yi.

3

Page 4: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

DES (1)

Istoric:• Propus in 1972 de catre NBS (astazi NIST)• Larg adoptat ca un standard• Utilizat in masinile ATM• Inlocuit de AES

Paramerii DES:• Lungime cheie k = 56;• Lungime bloc l= 64;• DES: {0,1}56 x{0,1}64->{0,1}64

• DES-1: {0,1}56 x{0,1}64->{0,1}64

4

Page 5: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

DES (2)

function DES(M) // |K| = 56 si |M| = 64Generare (K1,….,K16) din K // |Ki| = 48 pentru 0<i<16

M = IP(M) //aplica permutarea initialaFormeaza M ca L0||R0 // |L0| = |R0| = 32for i = 1 to 16 do

Li<-Ri-1, Ri<-f (Ki,Ri-1) + Li-1

C<-IP-1(L16 || R16)return C

Obs:• Se aplica permutarea initiala mesajului de 64 biti• Se separa mesajul permutat in cele doua jumatati stanga si dreapta

de cate 32 biti• Se aplica cele 16 runde utilizand setul de chei• Se aplica permutarea inversa pe concatenarea partii stangi cu cea

dreapta dupa runda 16

5

Page 6: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

DES (3)

function DES-1(C) // |K| = 56 si |C| = 64Generare (K1,….,K16) din K // |Ki| = 48 pentru 0<i<17

C = IP(C) //aplica permutarea initialaFormeaza C ca L16||R16 // |L16| = |R16| = 32

for i = 16 to 1 doRi-1<-Li, Li-1 <-f (Ki,Ri-1) + Ri

M<-IP-1(L0 || R0)

return M

Obs: • Procedura este similara cu cea de criptare. • Permutarea are inversa.

6

Page 7: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

DES (4)

Functia f (K,R) // |J| = 48 and |R| = 32Expandeaza R la 48 biti, R<-R+JDescompune R=R1||R2||R3…||R8 //|Ri|=6 pt 0<i<9for i = 1 to 8 doRi <- Si(Ri) // Fiecare aplicare Si returneaza 4 biti

R<- R1||R2||R3…||R8 // |R| = 32 bitiR<-P(R)return RObs:– Pentru expandare la 48 biti din 32 si aplicare Si se cerceteaza

bibliografia. – Idem pentru permutare.

7

Page 8: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Analiza criptarii

Adversarul A cunoaste E:{0,1}Kx{0,1}l->{0,1}l T <-{0,1}k este cheia tinta.Fiind date: (M1,C1),….,(Mq,Cq) unde Ci = E(T,Mi ) pentru i = 1,…..,q,

si M1,….,Mq distincte se cere sa se gaseasca T

Analiza: Sigur A poate sa cunoasca C1,….,Cq, dar cum poate sa afle A mesajele M1,…, Mq?

Doua situatii posibile:• Informatii aflate dupa mesaj (T si R cunosc cheia K, T transmite un

mesaj de genul “sa ne intalnim pe 1 Mai”, atacatorul observa ca s-au intalnit si intuieste ca acesta este mesajul. Asa cunoaste C si M).

• Cunostinte apriorice despre context (Criptare de mail care in mod uzual incepe cu From si atacatorul intuieste aceasta parte a mesajului).

8

Page 9: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Tipuri de atacuri

Cu formulare anterioara avand (M1,C1),…., (Mq,Cq) cu Ci = E(T,Mi) pentru i=1,…,q si M1,…, Mq distincte.

A trimite un mesaj mail lui T pe care T il cripteaza si il trimite lui R;T este un ruter care cripteaza orice pachet pe care il receptioneaza;Cautare exhaustiva a cheilor:• Notam T1,….,T2k ca lista tuturor cheilor de k biti. Tinta este de a

gasi T<-{0,1}k care satisface ET (M1) = C1.Algorithm EKSE (M1,C1)

for i = 1,….,2k doif E(Ti,M1) = C1 then return Ti

Este aceasta cheia tinta T?• Def: O cheie K este consistenta cu (M1,C1) daca C1=E(K,M1)• Daca notam cu SET toate cheile consistente cu (M1,C1) algoritmul

gaseste unele chei din SET• Daca l>=k si q este suficient de extins atunci T poate fi unic.

9

Page 10: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Consideram DES calculat hardware la 1,6 Gb/sec.Un mesaj DES are 64 biti• Pot fi realizate (1,6*109)/64=2,5*107 calcule DES pe

secunda;• Presupunem ca pentru EKS incercam toate variantele

adica 255 calcule DESPentru executie rezulta

Analiza timp de calcul pentru spargere

10

ani45~sec10*4,110*5,2

2 97

55

Obtinem in medie 22,5 ani, operatie prohibitiva, motiv pentru care este considerat sigur.

Obs: • Daca se analizeaza q mesaje timpul se multiplica si in plus

avem nevoie de spatiu de stocare pentru ele.• Calculul paralel pe mai multe masini poate diminua timpul de

calcul• DES poate fi spart datorita lungimi mici a cheii si facilitatilor

de calcul paralel

Page 11: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

2 DES

• Cifrul bloc 2DES:{0,1}112x{0,1}64->{0,1}64 sau2DESK1K2(M)=DESK2(DESK1(M))

Obs:• Cautarea exhaustiva nu da rezultate datorita efortului de calcul chiar

pentru calcul paralel (2112)Atacuri 2DES:• Daca presupunem K1K2 cheia tinta in 2DES si adversarul are M si

C din 2DESK1K2(M)=DESK2(DESK1(M)), rezulta DES-1K2(C)=DESK1(M)

• Presupunand DES-1K2(C) = DESK1(M) and T1,…..,TN toate cheile

posibile, N=256. • O idee de atac este de a construi membrul stang cu N intrari ca

rezultat al DES-1K2(C) si membrul drept cu N intrari ca rezultat din

DESK1(M)• Se poate gasi K1K2 prin concatenare Ti||Tj pentru care membrul

stang L[i] este egal cu membrul drept R[j].• Numar de oparatii 257

Obs: 3DES opereaza cu chei de 168 biti.

11

Page 12: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

AES

In 1998 NIST anunta o competitie pentru un nou cifru:• Lungime cheie 128• Lungime bloc 128• Mai rapid decat DES la implementare softwareIn 2001 se alege AESfunctia AESK(M)

Obtine vector de 11 chei (K0,….., K10) din cheia K //functii de transformare bijectives <-M+K0for r = 1 to 10 do

s<-S(s) //S(s) este o amestecare de biti s<- shift-rows(s) //operatii facute pe tablouri de 4x4 bitiif r < 9 then s <- mix-cols(s) //operatii facute pe tablouri de 4x4 biti

s <- s + Krend forreturn s

Caracteristici:• Mai putine tabele de calcul decat la DES;• Operatii de campuri finite (Galois);• Nu de cunoaste inca o metoda buna de spargere pentru chei de 128

biti;

12

Page 13: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Functii pseudorandom (1)

• Fie D={0,1}l si R={0,1}L. f:D->R este multimea tuturor functiilor cu domeniul D si valori in R. Alegerea aleatoare a unei functii definite pe D cu valori in R este o functie random (de ex, o permutare).

• O familie de functii F: Keys(F)xDom(F)->Range(F) este o mapare de doua argumente. Pentru K din multimea Keys(F) vom nota FK:Dom(F)->Range(F) ca fiind definita prin:

Exemple:• DES: Keys(F) = {0,1}56, Dom(F) = Range(F) = {0,1}64

• In orice cifru bloc: Dom(F) = Range(F) si fiecare FK este o permutare

13

),()(:)( xKFxFFDomx K

Page 14: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Functii pseudorandom (2)

F este o functie pseudo random (PRF) in cazul in care comportarea intrare-iesire Fk arata un comportament aleator (comportament pentru adversar).

• Pentru a mentine o functie pseudo random putem vedea o tabela cu

maxim 2L intrari;• Daca se apeleaza cu valoarea x:

– T[x] nu exista in tabela se genetreaza o valoare aleatoare din cele ramase;

– T[x] exista se returneaza valoarea corespunzatoare;

• Cele mai uzuale functii pseudorandom sunt permutarile

• La permutari Dom si Range sunt identice.

14

Page 15: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Semnatura digitala

O schema de semnatura digitala este similara cu o autentificare de mesaj cu chei asimetrice.

• Cheia sk utilizata pentru generarea semnaturii este diferita de cheia pk utilizata la verificarea semnaturii.

• Cheia pk este publica, in sensul ca adversarii o cunosc si numai cel care semneaza este in posesia cheii secrete sk.

O schema de semnatura digitala DS = (K,Sign,VF) consta din trei algoritmi:

• Algoritmul de generare aleatoare de chei K ce genereaza perechea de chei (pk,sk) [(pk,sk)K]

• Algoritmul de semnatura care ia cheia secreta sk un mesaj M si returneaza semnatura (numit si marcaj) σ Є{0,1}*U{Δ}. Algoritmul poate fi aleator sau cu stare completa. Vom scrie Signsk(M) sau Sign(sk,M) pentru operatia de semnare a intrarilor sk si M.

• Algoritmul deterministic de verificare VF care ia cheia publica pk, mesajul M si semnatura candidata σ si returneaza un bit. Vom scrie d VFpk(M, σ) sau d VF(pk,M, σ).

15

Page 16: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Semnatura digitala, interpretare

• Se cere ca VFpk(M,σ)=1 pentru orice pereche de chei (pk,sk), care poate fi iesire a lui K, orice mesaj M si orice σ # Δ care poate fi iesire a lui Signsk(M). Daca Sign este stateless atunci vom asocia la fiecare cheie publica un spatiu mesaj Messages(pk) care este setul tuturor mesajelor pentru care Signsk(M) nu returneaza niciodata Δ.

• Daca notam cu S o entitate care doreste sa aiba capabilitate de semnatura digitala:– Pas1. Generare cheie: S ruleaza K pentru a genera o pereche de chei

(pk,sk) pentru el insusi. Algoritmul de generare este executat local de S.– Pas2. S poate produce semnatura digitala a documentului M Є

Messages(pk) ruland Signsk(M) pentru a returna semnatura σ. Perechea M, σ reprezinta versiunea autentificata a documentului.

– Pas3. Dupa receptia documentului M si a marcajului σ presupus ca venind de la S, receptorul B in posesia cheii pk verifica autenticitatea semnaturii utilizand procedura specificata de verificare. Daca VFpk(M, σ) este 1, B intelege ca mesajul este transmis de S, altfel va fi rejectat nefiind autentic.

16

Page 17: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Semnatura digitala – scop atacator

• Semnatura digitala are ca scop furnizarea proprietatilor de securitate, cum ar fi schemele de autentificare ale mesajelor.

• Diferenta consta in mai marea flexibilitate a structurii cheii. Adversarul are acces la cheia publica.

• In acest caz scopul adversarului F este falsificarea, adica sa produca un document M si un marcaj σ astfel incat VFpk(M,σ) = 1, cu toate ca M nu este transmis de catre S (transmitatorul autorizat – cazul cecurilor bancare).

• Notand prin DS = (K,Sign,VF) o schema de semnatura digitala, actiunile atactorului pot fi impartite in doua faze:– Faza de “invatare”, faza in care executa Signsk(.), cu (pk,sk) alesi aprioric

aleator din K. Poate incerca de un numar q de ori, in orice maniera doreste, pentru mesajele din spatiul messages(pk) asociate cheii.

– Faza de “falsificare”, in care produce perechi (M, σ). Adversarul obtine succes daca VFpk(M,σ) = 1. Probabilitatea de succes este data de resursele pe care le are la dispozitie (timpul de rulare, numarul de interogari).

17

Page 18: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Observatii, comparatii

• Utilizarea cheilor in semnatura digitala poate fi considerata ca vazuta in oglinda fata de schema de criptare asimetrica. In semnatura digitala detinatorul cheii secrete este trasmitatorul si o utilizeaza pentru a marca mesajul, marcaj ce va fi verificat de receptor. In schemele de criptare asimetrica posesorul cheii secrete este receptorul si o utilizeaza pentru a decripta mesajul primit de la altii.

• Algoritmul de semnatura digitala poate fi generat aleator caz in care pot fi mai multe marcaje corecte asociate aceluiasi mesaj M.

• Algoritmul poate fi stateful, de exemplu utilizand un contor care este gestionat de transmitator. In acest caz algoritmul de semnatura va accesa si actualiza acest contor ca o variabila globala.

• Algoritmul poate fi aleator si statefull.

• Totusi, spre deosebire de schemele de criptare, unde algoritmii de criptare pot fi ori aleatori, ori stateful pentru ca schema sa fie sigura, un algoritm de semnatura determinist stateless este uzual.

18

Page 19: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Definire avantaj atacator

Fie DS = (K,Sign,VF) o schema de semnatura digitala si A un algoritm care returneaza o pereche (M, σ). Se executa experimentul:

ExpDS(A)

(pk,sk)K(M,σ)ASgnsk(.)(pk)

if(VFpk(M,σ)=1 and MЄMessages(pk)) return 1

Definim avantajul algoritmului A prin

AdvDS(A)=Pr[ExpDS(A)=1]

19

Page 20: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Descrierea schematica

Cititi dupa RSA. A castiga daca:

d=1

MЄ{M1,M2,…,Mq}

20

A

pk

M1

Mq

σ1

σq

σ

M

sk

pk

d

Sign

VF

Page 21: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Diseminare chei publice, comparatie MA

Diseminarea cheii publice:• Cheile publice nu se pastreaza secret si trebuie raspandite• Se pastreaza in asociatie (S,pk), posibil pe un server de incredere• Metoda uzuala de diseminare este cea de utilizare certificate

In schemele de autentificare:• Pentru verificare este nevoie de partajarea unui secret cu

transmitatorul• Verificarea se face fara personalizarea transmitatorului

In schemele de semnatura digitala:• Pentru verificare nu este necesar secret• Verificarea necesita personalizarea transmitatorului

21

Page 22: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Putina matematica

Numar compozit: intreg pozitiv care are un divizor pozitiv altul decat el SAU orice numar pozitiv mai mare decat 1 care nu e prim

Factorizare (descompunere in factori primi): scrierea unui numar compozit ca produs de factori primi.

Cele mai greu numere de factorizat sunt semiprimele (produs a doua numere prime).

Coprime: doua numere n si m se numesc coprime daca nu au alti divizori comuni in afara de 1.

Functia totient a lui Euler: Φ(n) a lui n pozitiv, intreg, este egal cu numarul intregilor pozitivi mai mici decat n care sunt coprimi cu n

22

Page 23: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Putina matematica

Congruenta: pentru un n pozitiv intreg, doi intregi a si b sunt congruenti modulo n, notat:

a ≡ b (mod n), daca a – b este un intreg multiplu de n.

Teorema lui Euler: daca n si a sunt pozitivi intregi atunci:

aφ(n) ≡ 1 (mod n)

Radacina prima modulo n este orice numar g cu proprietatea ca orice numar coprim cu n este congruent cu o putere a lui g modulo n. eg: 3 radacina prima modulo 7.

Pentru ca g sa fie radacina prima modulo n, Φ(n) trebuie sa fie cea mai mica putere a lui a care este congruenta cu 1 (mod n)

23

Page 24: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Semnatura RSA

Fixand generatorul RSA Krsa si notand algoritmul de generare a cheii cu:

Alg K(N,p,q,e,d)Krsa

pk(N,e), sk(N,d)

return pk,sk

Unde:• p,q sunt doua numere prime al caror produs este N• φ(n)=(p-1)(q-1) numarul numerelor prime mai mici decat n• Se alege e, un intreg mai mic decat φ(n) coprim cu φ(n);

• Se determina d astfel incat de ≡ 1(mod φ(n))Obs: e,dЄZ*

φ(n)

24

Page 25: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Semnatura RSA (ideea)

Avem pk(N,e), sk(N,d)

Notam f,f−1: Z*N Z*

N ca fiind functia RSA de criptare si functia inversa de decriptare definite ca:

• f (x) = xe mod N • f−1(y) = yd mod N.

Semnarea cu functia de decriptare a semnaturii y• y = SignN,d (x) = f−1(y) = yd mod N

Verificarea prin criptare a mesajului x:• VFN,e(x) = 1 daca f(x) = y, adica xe=y mod N .Obs: x mesaj, y semnatura

25

Page 26: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Securitate semnatura RSA

• Pentru a contraface semnatura mesajului (y) atacatorul cunoaste N,e dar nu cunoaste d.

• Pentru a calcula yd mod N, inseamna ca trebuie sa inverseze functia f.

• RSA este 1-way, este dificil si schema este sigura? NU

Justificare:

• In principal contrafacerea semnaturii nu este facuta pe baza mesajului.

• Astfel, fiind dat pk = (N, e), se ia mesajul y=1 si semnatura x=1. Atacatorul castiga.

• Pentru un xЄZ*N, mesajul y=xe mod N permite obtinerea perechii

(y,x) si iarasi atacatorul castiga

26

Page 27: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Atacuri bazate pe proprietati RSA

Avand pk=(N,e) si sk=(N, d) chei RSA, oricare ar fi x1,x2 ЄZ*N si y1,y1ЄZ*

N avem

• (x1x2)e mod N = (x1)e(x2)e mod N• (y1y2)e mod N = (y1)e(y2)e mod NCeea ce duce la • f(x1x2)=f(x1)·f(x2) mod N• f−1(y1y2)=f−1(y1)·f−1(y2) mod N

Unde:• f(x) = xe mod N si f−1(y) = yd mod N sunt functiile RSA directa si

inversaPentru toate mesajele y1,y2 ЄZ*

N avem:• SignN,d(y1y2) = SignN,d (y1) SignN,d (y2) =x1 x2 asa ca se poate forta

semnatura mesajului y1y2 mod N, pornind de la x1 x2.Atac A(N, e):

Ia y1,y1ЄZ*N –{1} distincte

x1 = Sign(y1), x2 = Sign(y2) return (y1y2 mod N, x1x2 mod N)27

Page 28: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Diffie and Hellman

Este cunoscut ca un protocol criptografic care permite ca doua parti sa stabileasca un secret partajat (cheie) peste un canal de comunicatie nesigur. Aceasta cheie va fi utilizata pentru criptarea urmatoarelor mesaje utilizand cifru simetric.

• Transmitatorul (T) si receptorul (R) agreaza sa utilizeze un numar prim p si g primitive root mod p (ex: p=23 si g=5).

• T alege un intreg secret a (ex: a=6) si trimite la R, A=(ga mod p) (ex: A=56 mod 23 = 8).

• R alege un numar intreg secret b=15 si trimite lui T, B=(gb mod p) (ex: B = 515 mod 23 = 19).

• T calculeaza s = (B)a mod p (ex: 196 mod 23 = 2). • R calculeaza s = (A)b mod p (ex: 815 mod 23 = 2).

Obs: • Numai a, b si gab = gba mod p sunt tinute secret. • Toate celelalte valori p, g, ga mod p, and gb mod p sunt transmise

in clar.

28

Page 29: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Semnatura Diffie - Hellman

Cand Diffie si Hellman au introdus criptografia cu cheie publica au sugerat urmatoarea schema pentru semnatura digitala:

• Sign(sk,M) = D(sk,M)• VF(pk,M,σ) = 1 daca E(pk,σ) = M

unde (E,D) este o schema de criptare cu cheie publica• Cu toate ca criptarea cu cheie publica este determinista multe

documentatii vad semnatura digitala in acest mod.

Ce se intampla la sirurile lungi, daca in RSA mesajul este un element din Z*

N?

Raspuns: O abordare posibila este hash urmata de schema de decriptare.

29

Page 30: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Semnatura Diffie - Hellman

Cand Diffie si Hellman au introdus criptografia cu cheie publica au sugerat urmatoarea schema pentru semnatura digitala:

• Sign(sk,M) = D(sk,M)• VF(pk,M,σ) = 1 daca E(pk,σ) = M

unde (E,D) este o schema de criptare cu cheie publica• Cu toate ca criptarea cu cheie publica este determinista multe

documentatii vad semnatura digitala in acest mod.

Ce se intampla la sirurile lungi, daca in RSA mesajul este un element din Z*

N?

Raspuns: O abordare posibila este hash urmata de schema de decriptare.

30

Page 31: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Introducere functie Hash

Fie H:{0,1}* Z*N o functie hash publica si notam pk=(N,e) si sk=(N,d) o

cheile de semnare. Schema devine:

Alg SignN,d(M):yH(M)xyd mod Nreturn x

Alg VFN,e(M,x):yH(M)if xey(mod N) then return 1return 0

Succint:SignN,d(M)=H(M)d mod N,

Si alegeri diferite pentru H dau diferite scheme de semnare.

31

Page 32: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Cerinte pentru hash

Presupunand ca atacatorul poate gasi o coliziune pentru H, insemnand mesaje distincte M1,M2 pentru care H(M1) = H(M2).

AtunciH(M1)d =H(M2)d (mod N)

Ceea ce inseamna ca M1 si M2 au aceeasi semnatura.

Asa compromiterea este simpla:• Obtinerea unei semnaturi x1 = H(M1)d mod N a lui M1• Trimitere M2 si semnatura x1

Concluzie: H trebuie sa fie rezistent la coliziuni.

32

Page 33: Http://ssc.users.ro Curs 4 – Cifru bloc, semnatura digitala Bogdan Carstoiu 1.

Prevenire atacuri cu hash

Reamintim pentru RSA• 1 este semnatura lui 1• SignN,d (y1y2) = SignN,d (y1) · SignN,d (y2)

Dar la RSA cu hash:• H(1)d # 1, asa ca semnatura lui 1 este diferita de 1• SignN,d (y1y2) = H(y1y2)d #H(y1)d · H(y2)d (mod N)

Concluzie: Prin hash avem o buna sansa de a preveni atacuri cunoscute

33