prezantare cc - cifruri bloc - varianta finala

Moscaliuc OvidiuPăun Adrian

Stancu Elena Andreea

Cifruri bloc

• cifrurile bloc criptează blocuri de lungime fixă în blocuri de aceeaşi lungime

• cifrurile bloc constau într-o pereche de 2 algoritmi: unul de criptare (E) şi unul de decriptare (E-1)

• funcţiile de criptare ale unui cifru bloc sunt permutări

2

• pentru a mări securitatea, se poate aplica “cifrarea multiplă”

• pentru mesajele mai lungi decât lungimea blocului (de obicei n=64) se împarte mesajul în blocuri de lungime egală cu n şi se critează separat fiecare bloc.

• există mai multe moduri de operare ale cifrurilor bloc, prezentate în continuare.

Cifruri bloc

3

Se alege n ca lungimea blocurilor şi un alfabet Σ. Fie K mulţimea cheilor şi Ek, Dkfuncţiile de cifrare, respectiv decifrare.

Folosind ECB, blocuri identice de text sunt criptate în blocuri identice. Acest lucru conferă atacatorului posibilitatea de a identifica secvenţe de text simplu în textul cifrat.

Modul de cifrare ECB

4

Modul ECB(electronic code book) are următorii paşi:

• textul simplu de lungime m se împarte în blocuri de lungime n (se adaugă simboluri din Σ dacă m nu este divizibil cu n)

• se alege cheia e şi blocurile de lungime n se criptează folosind funcţia de criptare Ee

• decriptarea se face similar, folosind Dd


5


6


ECB nu trebuie folosit la criptarea unor texte mari şi nu trebuie folosită aceeaşi cheie pentru criptarea a două blocuri diferite.

7

Exerciţiu:n=4, , m=101100010100101

• adăugăm un 0 la final pentru ca lungimea lui m să fie divizibilă cu 4• descompunem textul în blocuri de câte 4 biţi:m1=1011, m2=0001, m3=0100, m4=1010• cu funcţia de criptare EPI cifrăm fiecare bloc şi obţinem: E(m)=c1c2c3c4 cu c1=0111, c2=0010, c3=1000, c4=0101• c=0111001010000101


8

Modul CBC (cypher-block chaining) a fostcreat de IBM în 1976. Fiecărui bloc de text simplu i se aplică operatorul XOR cu textul cifrat anterior.

Astfel, blocurile criptate sunt dependente de blocurile simple procesate până la momentul respectiv.

Pentru primul bloc text se va folosi un vector de iniţializare.

Modul de cifrare CBC

9

Modul CCB are următorii paşi:• textul simplu de lungime m se împarte în blocuri de lungime n (se adaugă simboluri din Σ dacă m nu este divizibil cu n –idem ECB)

• se alege vectorul iniţial u Σn

• se cifrează mesajul m cu cheia e, astfel: c0=u, cj=Ee(cj-1 mj) pentru 1≤j≤t; c=c1c2...ct

• decriptarea:c0=u, mj=cj-1 Dd(cj), cu Dd=Ee-1


10


11

Exerciţiu:n=4, , m=101100010100101

• adăugăm un 0 la final pentru ca lungimea lui m să fie divizibilă cu 4

• descompunem textul în blocuri de câte 4 biţi:m1=1011, m2=0001, m3=0100, m4=1010

• considerăm vectorul iniţial u=1010


12

• c0=u;c1=EPI(c0 m1)=EPI(0001)=0010;c2=EPI(c1 m2)=EPI(0011)=0110; c3=EPI(c2 m3)=EPI(0010)=0100;c4=EPI(c3 m4)=EPI(1110)=1101.c=0010011001001101.


13

• decriptarea se face astfel:m1=c0+Dd(c1)=u+EPI

-1(0010)=1010 0001=1011;m2=c1+Dd(c2)=u+EPI

-1(0110)=0010 0011=0001;m3=c2+Dd(c3)=u+EPI

-1(0100)=0110 0010=0100;m4=c3+Dd(c4)=u+EPI

-1(1101)=0100 1110=1010;


14

Modul CFB (cypher feedback) este foarte asemănător cu CBC, dar vine cu unele îmbunătăţiri ce permit transmiterea mesajelor criptate mai rapid decât în cazul CBC – caz în care timpul de calculare a funcţiilor de criptare/decriptare poate dura foarte mult în cazul textelor mari.

Modul de cifrare CFB

15

În modul CFB, funcţiile de criptare nu sunt folosite pentru a cripta blocuri de text simplu, ci pentru a obţine un şir de chei bloc. Criptarea se face adunând cheile bloc modulo 2. Decriptarea se face folosind suma aceloraşi chei bloc modulo 2. Blocurile cheie pot fi generate simultan de către cei care comunică folosind CFB.


16

Algoritmul este următorul:• se alege un vector u Z2

n

• se alege un întreg pozitiv r, 1 r<n• textul simplu se împarte in blocuri de lungime r: m=m1...mt•I1=u•pt 1 j t avem Oj=Ek(Ij) Z2

n , tj=stringul format din primii r biţi din Oj , cj=mj tj , Ij+1=2rIj+cj mod 2n adică se şterg primii r biţi din Ij şi se adaugă cj în drepta biţilor rămaşi


17

Algoritmul pentru decriptare este similar:• I1=u• Oj=Ek(Ij) Z2

n

• tj=stringul format din primii r biţi din Oj• mj=cj tj•Ij+1=2rIj+cj mod 2n adică se şterg primii r biţi din Ij şi se adaugă cj în drepta biţilor rămaşi


18


19

Exerciţiu:n=4, , m=101100010100101

• considerăm vectorul iniţial u=1010 şi r=3• blocurile lui m sunt: m1=101, m2=100, m3=010, m4=100, m5=101


j Ij Oj tj mj cj

1 1010 0101 010 101 111

2 0111 1110 111 100 011

3 1011 0111 011 010 001

4 1001 0011 001 100 101

5 1101 1011 101 101 00020

Observaţii:• fie A şi B participanţii la comunicaţie, A->B, B având cj poate afla Ij+1, Oj+1, tj+1, în timp ce A află cj+1. Când B primeşte cj+1 de la A, B obţine imediat mj+1=cj+1 tj+1. Acest mod de cifrare este rapid în transmiterea mesajelor.• în CFB blocul criptat anterior este folosit ca intrare în algoritm pentru a obţine blocul cifrat.


21

Modul de criptare OFB (output feedback mode)

• este foarte asemănător cu modul CFB

• la fel ca în modul CFB, OFB foloseşte un cifru bloc de lungime n, un alt bloc de lungime r , şi un vector iniţial I1.

• dacă avem de criptat un text simplu folosind cheia e, atunci mesajul simplu trebuie descompus în blocuri simple de lungime r, ca în modul CFB

22

Modul de criptare OFB- schema de funcţionare -

23

Modul de criptare OFB - criptarea

24

Modul de criptare OFB- algoritmul de criptare -

•I1 = IV;

•Ij = Oj -1 pentru j = 2...n;

•Oj = CIPHK(Ij) pentru j = 1, 2...n;

•Cj = Pj XOR Oj pentru j = 1, 2...n.

25

• la criptarea cu OFB, IV ( vectorul iniţial ), este transformat de către funcţia cifru pentru a produce prima ieşire ( output block )• primului bloc de ieşire îi este aplicată funcţia logică XOR, cu primul bloc de text ( în clar ), pentru a produce prima ieşire a cifrului bloc• celui de-al doilea bloc de ieşire i se aplică funcţia logică XOR, împreună cu al doilea bloc de text în clar, pentru a produce a treia ieşire a cifrului bloc• astfel blocurile succesive de ieşire sunt produse din cifrarea cu blocurile anterioare de ieşire, iar blocurilor de ieşire le este aplicată funcţia logică OR, împreună cu textul iniţial în clar pentru a produce cifrul bloc în întregime.

Modul de criptare OFB- algoritmul de criptare -

26

Modul de criptare OFB -decriptarea

27

•I1 = IV;

•Ij = Oj -1 pentru j = 2...n;

•Oj = CIPHK(Ij) pentru j = 1, 2...n;

•Pj = Cj XOR Oj pentru j = 1, 2...n.

Modul de criptare OFB- algoritmul de decriptare -

28

• la decriptarea cu OFB, IV ( vectorul iniţial ), este transformat de către funcţia cifru (decriptare) pentru a produce prima ieşire ( output block ) .• acestuia i se aplică funcţia logică XOR, împreună cu primul cifru bloc , pentru a recupera primul bloc al mesajului iniţial.• primul bloc de ieşire este folosit mai apoi pentru a genera al doilea bloc de ieşire; acestuia din urmă i se aplică funcţia XOR împreună cu al 2 lea cifru bloc, pentru a recupera al 2 lea bloc al mesajului iniţial• se repetă până când mesajul iniţial este recuperat în întregime.

Modul de criptare OFB- algoritmul de decriptare -

29

Modul de criptare OFB

• în ambele situaţii de criptare şi decriptare, fiecare funcţie cifru ( exceptând-o pe prima), depinde de rezultatele funcţiei anterioare.

• prin urmare, mai multe funcţii cifru nu pot fi executate în paralel.

• cu toate acestea în cazul în care este cunoscut vectorul iniţial, blocurile de ieşire pot fi generate în conformitate cu disponibilitatea datelor textului iniţial sau a cifrului bloc.

30

Modul de criptare OFB- avantaje şi limitări -

• similar cu CFB, feedback-ul care iese din ieşirea cifrului este independent de mesaj.

• este o varianta a cifrului Vernam.

• emiţătorul şi destinatarul trebuie să rămână sincronizaţi şi este nevoie de nişte metode de recuperare, pentru a asigura acest lucru.

31

• studiile au arătat că doar OFB 64 ar trebui folosit vreodată

• avantajul major al acestui mod este că cifrarea şi decifrarea merg foarte repede şi că eventualele erori de transmisie ale unui bloc cifrat cj afectează doar la decifrare blocul mj.

• la modul OFB cifrarea nu depinde de blocurile precedente, ci doar de poziţia blocului în cauză

Modul de criptare OFB- avantaje şi limitări -

32

Modul de criptare OFB - exemplu

• date: Având un cifru bloc care aplică permutări la nivel de bit unui vector de dimensiune 4 ( exemplu permutarea cu cifru cu alfabet Σ= {1,0}, iar lungimea blocului este 4. Atunci K=S4, iar funcţia de decriptare a cheii, este :

• codăm mesajul în clar:

• blocurile mesajului în clar sunt:

33

• cheia folosită este:

• ca vector de iniţializare folosim:

• obţinem

Modul de criptare OFB - exemplu

34

Cifruri şuvoi (stream chipers)

• am văzut cum cifrurile de bloc pot fi folosite la cifrarea unor texte simple mari, astfel încât, criptarea blocurilor simple depinde de poziţia lor în text

• o generalizare este dată de cifrurile şuvoi

35

• alfabetul este ,unde lungimea nu e precizată ; Fie n un număr natural şi . Cuvintele din sunt cifrate bit cu bit în felul următor: Fie o cheie şi un cuvânt de lungime t în .Alice generează un şuvoi de chei astfel : , unde sunt coeficienţi întregi fixaţi. O astfel de ecuaţie se numeşte recurenţă liniară de grad n. Atunci criptarea şi decriptarea se fac prin:

şi respectiv

*2 , ∑==Ζ=∑ CP

nK ∑= *∑

κ∈= ),....,,( 221 kkkk aaaa ,....,, 21=*∑ tzzzz ,....,, 21=

2mod,,11

ji

n

jjiii zwztinnipentrukz −

=∑≤<≤≤= nww ,...1

ttk zazaaE ++= ,....,)( 11

ttk zazaaD ++= ,....,)( 11

Cifruri şuvoi (stream chipers)

36

• fie n=4, k=(1,0,0,0) . Şuvoiul de chei este dat prin recurenţa: , adică am ales

• obţinem şuvoiul de chei : 1,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1,0,0,0,... , care este periodic cu perioada 15

κ∈14 ++ += iii zzz

13,0 421 ==== wwww

Cifruri şuvoi - exemplu

37

Probabilităţi

• Fie S o multime finită, nevidă, numităspaţiu de modelare

• Eveniment: A⊂S• Eveniment elementar: a∈S• S s.n. evenimentul sigur• Ø⊂S s.n. evenimentul nul• A,B ⊂S se numesc (mutual) exclusive dacă

A∩B=Ø

38

Distributie de probabilitate

• Pr:P(S) → R• Proprietăți:

• Pr(A)≥0, ∀ A⊂S• Pr(S)=1• A,B evenimente mutual exclusive ⇒

Pr(A∪B)=Pr(A)+Pr(B)• Pr(A) s.n. probabilitatea lui A• Consecințe:

• Pr(A)∈[0,1] ∀ A⊂P(S)• Pr(Ø)=0• Dacă A⊂B ⇒ Pr(A) ≤ Pr(B)• Pr(S\A)=1-Pr(A)• A1,A2,…,An ⊂ S două câte două mutual exclusive ⇒ ∑

===

n

ii

n

ii AA

11)Pr()Pr(

39

Teorema lui Bayes

• Distribuția uniformă: ∀a∈S Pr(a)=1/|s|• Probabilitatea condiționată

• A si B sunt evenimente independente dacă

• Teorema lui Bayes: Fie A si B două evenimente pentru care Pr(A)>0 si Pr(B)>0. Atunci:

)Pr()Pr(

)|Pr(B

BABA

∩=

)Pr()|Pr()Pr()Pr()Pr( ABABABA =⇔=∩

)|Pr()Pr()|Pr()Pr( ABABAB ⋅=⋅

40

Exemplu: probabilitate condiţionată

• Aruncarea unui zar• S={1,2,3,4,5,6}• Distribuție uniformă: • Pr(a)=1/6 ∀a∈S

• Se presupune că a avut loc deja evenimentul {4,5,6}

• Care este probabilitatea ca la urmatoarea aruncaresă obținem număr par?

• A={2,4,6}• Pr(B)=3/6• Pr(A∩B)=Pr({4,6})=2/4• Pr(A|B)=Pr(A∩B)/Pr(B)=(2/6)/(3/6)=2/3

41

Teorema lui Shannon - Istoric

• Are ca origine articolul publicat de Shannon în 1949 cu titlul: “Communication theory of secrecy systems”

• Folosește concepte din teoria informației(ilustrate în articolul său, publicat în anul1948: “A mathematical theory of communication”)

• Demonstrează că pot exista criptosistemeperfect sigure.

42

Criptosistem perfect sigur- concepte generale -• Lungimea cheii utilizate trebuie să fie egală

cu lungimea textului ce trebuie criptat• Pentru fiecare nou mesaj criptat se va

utiliza o cheie nouă• Deşi există astfel de criptosisteme(ex: One

Time Pad), ele sunt utilizate doar în mediicu un grad ridicat de securizare, necesitândtransmiterea unei cantități mari de informație.

43

Criptosistem perfect sigur- scenariu -• Se consideră urmatorul scenariu:

• Folosind un criptosistem, Alice trimite mesaje cătreBob

• Mesajul criptat trimis este interceptat de Oscar• Criptosistemul este considerat perfect sigur dacă

Oscar nu poate deduce mesajul original din mesajul criptat.

44

Criptosistem perfect sigur- modelare matematică -• Se consideră un criptosistem (M,C,K,E,D) cu

• M – spațiul mesajelor ce pot fi trimise• C – spațiul mesajelor criptate posibile• K – spațiul tuturor cheilor ce pot fi utilizate• Ek – funcția de criptare folosind cheia k∈K• Dk – funcția de decriptare folosind cheia k∈K

• Pentru criptarea fiecărui mesaj nou, Alice folosește o cheie diferită, independentă de textul ce urmează a fi criptat.

45

• Se consideră:• PrM distribuția de probabilitate pe M• PrM(m)>0, ∀m∈M• PrK distribuția de probabilitate pe K• PrK(k)>0, ∀k∈K• Pr distribuția de probabilitate pe MxK cu

Pr(m,k)= PrM(m) PrK(k) fiind probabilitatea de apariție a mesajului m și criptarea acestuiafolosind cheia k.

• Pr(c)>0, ∀c∈C

Criptosistem perfect sigur- modelare matematică -

46

• Se consideră evenimentele:• Mesajul este criptat:

• Cheia k este folosită pentru criptare:

• Mesajul m este criptat folosind cheia k, iarrezultatul este c:

• Obs: evenimentele m si k sunt independente:

}|),{( Kkkmm ∈=

}|),{( Mmkmk ∈=

})(|),{( cmEkmc k ==

)Pr()Pr()Pr()Pr(),Pr()Pr( kmkmkmkm ⋅=⋅==

},|),{( KkMmkmkm ∈∈=


47

• Se poate demonstra că: , undeeste probabilitatea ca mesajul m să fie criptat

• Analog: , unde esteprobabilitatea să fie folosită cheia k

• este probabilitatea ca un mesaj c recepționat să fi fost criptat

)(Pr)Pr( mm M=

)(Pr)(Pr)(Pr)(Pr)(Pr),Pr()Pr( mkmkmkmm MKk

KMKk

KMKk

∑∑∑∈∈∈

=⋅=⋅==

)(Pr)Pr( kk K=

)Pr(m

)Pr(k

),Pr( cm


48

• Se consideră că Oscar a interceptat mesajulcifrat c și cunoaște distribuția de probabilitățiPrM (cunoaște limba folosită de Alice si Bob)

• Putem spune că un criptosistem este perfect sigur daca Oscar nu poate “invăța” nimic din mesajul cifrat interceptat c, adică dacă aparițialui c nu face ca anumite texte simple să fie privilegiate.

• Definiţie: Un criptosistem (M,C,K,E,D) esteperfect sigur dacă evenimentele m si c suntindependente:

KkMmmcm ∈∀∈∀= ,),Pr()|Pr(


49

Criptosistem perfect sigur- exemplu-

Fie M={0,1} cu Pr(0)=1/4 si Pr(1)=3/4 K={A,B} cu Pr(A)=1/4 si Pr(B)=3/4 C={a,b} Functiile de criptare EA si EB cu EA(0)=a,

EA(1)=b, EB(0)=b si EB(1)=a

50


Posibilitatea ca textul original 1 sa fie cifrat cu cheia B este:

Posibilitatea de aparitie a textului cifrat aeste:

Iar a textului b:

51

169

43

43

)Pr()1Pr(),1Pr( =⋅=⋅= BB

85

169

161

),1Pr(),0Pr(}))(|),Pr({()Pr( =+=+=== BAamEkma K

83

163

163

),0Pr(),1Pr(}))(|),Pr({()Pr( =+=+=== BAbmEkmb K


Calculam probabilitatile conditionate

52

),( cmP

101

161

58

),0Pr(58

85

}))0(|),0Pr({()Pr(

)0Pr()|0Pr( =⋅=⋅=

=== A

aEka

aa

k

109

169

58

)Pr(),1Pr(

)|1Pr( =⋅==aB

a

21

163

38

)Pr(),1Pr(

)|1Pr( =⋅==bA

b

21

163

38

)Pr(),0Pr(

)|0Pr( =⋅==bB

b


Reamintim ca un sistem este perfect sigur daca

Caz particular:

⇒ Criptosistemul nu este perfect sigur(dacaOscar intercepteaza textul cifrat a, poate fiaproape sigur ca mesajul original a fost 1)

53

KkMmmcm ∈∀∈∀= ,),Pr()|Pr(

),0Pr(101

41

)0Pr()0Pr( a=≠==

Shannon a dat o caracterizare a schemelor de criptare perfect sigure.

Teoremă: Fie (E,D) o schemă de criptare peste (P,C,K) astfel încât |P|=|C|=|K|. Atunci schema este perfect sigură. Adică:

• orice cheie k este aleasă cu aceeaşi probabilitate 1/|K|• pentru m P şi c P, există o singură cheie k K astfel încât Ek(m)=c

Teorema lui Shannon

54

VERNAM ONE TIME PAD

• reprezintă cel mai faimos criptosistem perfect sigur

• a fost inventat şi patentat de Gilbert Vernam în 1917, dar abia în 1949 Shannon a demonstrat că acesta este perfect sigur

56

Întrebări

57

prezantare cc - cifruri bloc - varianta finala

Documents