CRIPTOSISTEME SIMETRICE I - math.uaic.rocriptografie/slides_crypto4_2017_h.pdf · miscarea brownian...

Moduri de criptare Flux Blocuri Iulius Cezar Criptosisteme afine Digrafi Matrici Vigenere

CRIPTOSISTEME SIMETRICE I

Criptografie

Anul II

Martie 2017

Criptosistem

P = multimeamesajelor ın clar

K = multimeacheilor

E−→C = multimeamesajelor criptate

C = multimeamesajelor criptate

K = multimeacheilor

D−→C = multimeamesajelor ın clar

Criptosistem

Notatie: E (m, k) = Ek(m), D(c , k) = Dk(c)

∀k ∈ K functia m 7→ Ek(m) este injectiva

∀k ∈ K , ∃k ′ ∈ K astfel ıncat

m 7→ c := Ek(m) 7→ Dk ′(c) = m

(conditia de reversibilitate a criptarii)

Criptosistem simetric (cu cheie privata)

Cheia de criptare “=” cheia de decriptare

Criptosistem

m 7→ c := Ek(m) 7→ Dk ′(c) = m

Criptosistem

m 7→ c := Ek(m) 7→ Dk ′(c) = m

Metode de criptare

Criptare ın sistem flux (stream cypher)

Criptare pe blocuri (block cypher)

Criptare prin substitutie (substitution cypher)Criptare prin transpozitie (transposition cypher)

Metode de criptare

Criptare in sistem flux

Fie A un alfabet (cu n caractere) si K o multime (chei). Pentrufiecare k ∈ K este data o functie bijectiva

Ek : A −→ A

Fie M = m1m2 . . . un sir de caractere din A si K = k1k2 . . . un sirde chei de aceeasi lungime (keystream = flux de chei). O criptareın sistem flux consta ın obtinerea unui text criptat C = c1c2 . . .unde ci = Eki (mi ).

AVANTAJE

Functia de criptare se schimba la fiecare caracter

Erorile nu se propaga

Util ın cazurile sistemelor fara memorie

Ek : A −→ A

AVANTAJE

Ek : A −→ A

AVANTAJE

Criptare ın sistem flux

GENERAREA CHEILOR

Aleatoriu

Algoritm de generare plecand de la un flux de chei initial delungime mica (seed)

ki = fi (k1, . . . , kn0) , i > n0

ci = Eki (mi ) , i > 0

Algoritm de generare care depinde de un flux de chei initial delungime mica (seed) si de caracterele criptate deja obtinute

ki = fi (k1, . . . , kn0 , ci−1) , i > n0

ci = Eki (mi ) , i > 0

GENERAREA CHEILOR

Aleatoriu

ki = fi (k1, . . . , kn0) , i > n0

ci = Eki (mi ) , i > 0

ki = fi (k1, . . . , kn0 , ci−1) , i > n0

ci = Eki (mi ) , i > 0

GENERAREA CHEILOR

Aleatoriu

ki = fi (k1, . . . , kn0) , i > n0

ci = Eki (mi ) , i > 0

ki = fi (k1, . . . , kn0 , ci−1) , i > n0

ci = Eki (mi ) , i > 0

Criptare ın sistem fluxCriptosistemul Vernam

Alfabetul: A = {0, 1}.Mesaj ın clar: m1m2 . . .mt

Keystream: k1k2 . . . ktMesaj criptat: c1c2 . . . ct

ci = mi ⊕ ki ⊕ = XOR

Exemplu

Text ın clar: TEST = 10011001001001010011Keystream: 11011101101111101010Text criptat: 01000100100110111001 = ISNZ

Exemplu

ONE TIME PAD = criptosistem Vernam cu cheie generataaleatoriu si folosita o singura data

One Time Pad are securitate absoluta: singura metoda deatac este cautarea exhaustiva

Pentru aceasta fluxul de chei trebuie sa fie generat totalaleatoriu, impredictibil (folosind, de exemplu, surse fizice, camiscarea browniana a particulelor sau procese radioactive) siutilizat o singura data.

Folosit de: spionii sovietici; CIA; comunicatiile “red line”Washington – Moscova.

Cunoasterea a doua mesaje criptate cu acelasi flux de cheiduce la cunoasterea sumei XOR a mesajelor ın clarcorespunzatoare.

Criptare ın sistem fluxRC4

criptosistem bazat pe criptarea ın sistem flux

pentru obtinerea unui bit criptat sunt necesare ıntre 8 si 16operatii

optimizat pentru implementare software rapida

utilizat ın produse Microsoft (parole Windows, MSAccess,MSWord, ...), SSL (Netscape, Explorer), Adobe Acrobat ...

Criptare pe blocuri

Mesajul ın clar este ımpartit ın blocuri de o anumita lungime,fiecare din acestea fiind criptat si obtinandu-se astfel un alt bloc,eventual de lungime diferita.

Criptarea prin substitutie: S-BOX. Un bloc de n caractere(biti) este ınlocuit cu o alta combinatie de caractere (biti)

Substitutie monoalfabeticaExemplu: Criptosistemul lui Iulius CezarSubstitutie polialfabeticaExemplu: Criptosistemul lui Vigenere

Criptarea prin substitutie induce confuzie: legatura dintrecheie si textul cifrat este pe cat posibil de complexa.

Criptare pe blocuri

Criptarea prin permutare: P-BOX. Fiecare bloc este criptatprin permutarea caracterelor (bitilor) sale.Criptarea prin permutare induce difuzie: posibilele puncteslabe sunt imprastiate ın ıntreg textul cifrat.

Exemplu

Text ın clar: VINDETI TOATE ACTIUNILE DE LA FIRMA XAlgoritm de criptare:VINDETITOATEACTIUNILEDELAFIRMAXText criptat: VIAIAXITCLFNOTEIDAIDRETUEMTENLACheia: 6

Criptare pe blocuri

Exemplu

Criptare pe blocuri

Exemplu

Criptare pe blocuri

Exemplu

Criptare pe blocuri

Exemplu

Criptare pe blocuri

Criptosisteme produs: RUNDE. Un bloc este criptat prinaplicarea succesiva a unui numar determinat de S-Box siP-Box

Arhitectura Feistel

Data Encryption System

Rijndael (Advanced Encryption System).

Criptosistemul lui Iulius Cezar

Mentionat de Suetonius ın biografia lui Iulius Cezar

Criptare pe blocuri

Mesajele (ın clar si criptate) sunt scrise ıntr-un alfabet cu Ncaractere. Fiecare bloc are un caracter.

Fiecarui caracter i se asociaza un element m ∈ ZN . Multimeacheilor este ZN .

Functia de criptare:

Ek(m) = m + k (mod N)

Criptare pe blocuri

Exemplu

N = 26

A B C D E F G H I J K L M N0 1 2 3 4 5 6 7 8 9 10 11 12 13

O P Q R S T U V W X Y Z14 15 16 17 18 19 20 21 22 23 24 25

Text ın clar: ALTE EXEMPLE LA SEMINARText criptat: DOWH HAHPSOH OD VHPLQDUCheie: 3

Exemplu

N = 26

A B C D E F G H I J K L M N0 1 2 3 4 5 6 7 8 9 10 11 12 13

O P Q R S T U V W X Y Z14 15 16 17 18 19 20 21 22 23 24 25

Exemplu

N = 26

A B C D E F G H I J K L M N0 1 2 3 4 5 6 7 8 9 10 11 12 13

O P Q R S T U V W X Y Z14 15 16 17 18 19 20 21 22 23 24 25

Exercitiu

Criptati textul ın clar: INTRODUCERE IN CRIPTOGRAFIECheie: 10

Conditia de reversibilitate a criptarii este satisfacuta. Functia dedecriptare:

Dk ′(c) = c + k ′ (mod N)

unde k ′ = −k (mod N).

Criptosistemul este foarte usor de spart: analiza frecventelor.

Exercitiu

Decriptati:HAHJBSCHHCLHSVJHGP

Exercitiu

Dk ′(c) = c + k ′ (mod N)

Exercitiu

Dk ′(c) = c + k ′ (mod N)

Exercitiu

Dk ′(c) = c + k ′ (mod N)

Exercitiu

Criptosisteme afine

Criptare pe blocuri

Functia de criptare: Ek(m) = am + b (mod N).Cheia: k = (a, b) ∈ Z2

O generalizare directa a Criptosistemului lui Cezar (a = 1)

Criptosisteme afine

Criptare pe blocuri

Criptosisteme afine

Criptare pe blocuri

Criptosisteme afine

Criptare pe blocuri

Criptosisteme afine

Criptare pe blocuri

Criptosisteme afine

Exemplu

Cheia: a = 3, b = 2Text ın clar: CRIPTOGRAFIEText criptat: IBAVHSUBCRAO

Pentru decriptare, este necesara inversarea functiei

m 7→ c := am + b (mod N)

Conditia de reversibilitate a criptarii:

(a,N) = 1

In acest caz functia de decriptare este

c 7→ m := a′c + b′ (mod N)

unde a′ = a−1 (mod N) , b′ = −a−1b (mod N).

Criptosisteme afine

Exemplu

m 7→ c := am + b (mod N)

(a,N) = 1

c 7→ m := a′c + b′ (mod N)

Criptosisteme afine

Exemplu

m 7→ c := am + b (mod N)

(a,N) = 1

c 7→ m := a′c + b′ (mod N)

Criptosisteme afine

Exemplu

m 7→ c := am + b (mod N)

(a,N) = 1

c 7→ m := a′c + b′ (mod N)

Criptosisteme afine

Daca (a,N) 6= 1, functia de criptare nu este injectiva.

Exemplu

a = 2, b = 3C 7→ H, P 7→ H.

Pentru atac: analiza frecventelor.Este necesar sa detinem a doua informatii.Exemplu

Determinati cheia de decriptare pentru un criptosistem afin dacanumarul caracterelor este N = 28 (A – Z ?) si se cunoaste ca siA sunt criptate ın B, respectiv ?.

Criptosisteme afine

Daca (a,N) 6= 1, functia de criptare nu este injectiva.

Exemplu

a = 2, b = 3C 7→ H, P 7→ H.

Pentru atac: analiza frecventelor.Este necesar sa detinem a doua informatii.Exemplu

Determinati cheia de decriptare pentru un criptosistem afin dacanumarul caracterelor este N = 28 (A – Z ?) si se cunoaste ca siA sunt criptate ın B, respectiv ?.

Criptosisteme bazate pe transformari aledigrafilor

Presupunem ca mesajele sunt scrise folosind caracterele unuialfabet A, de cardinal N.

Fiecare bloc are doua caractere. Fiecarui bloc xy i se asociazaun element

m = xN + y ∈ {0, 1, . . . ,N2 − 1} = ZN2

Functia de criptare este o aplicatie bijectiva

Ek : ZN2 −→ ZN2

De exemplu, poate fi o transformare afina

Ek(m) = am + b (mod N2)

cu cheia k = (a, b) ∈ Z2N2 ,

Conditia de reversibilitate a criptarii:a inversabil in Z2

N2 ⇔ (a,N) = 1.

m = xN + y ∈ {0, 1, . . . ,N2 − 1} = ZN2

Ek : ZN2 −→ ZN2

N2 ⇔ (a,N) = 1.

m = xN + y ∈ {0, 1, . . . ,N2 − 1} = ZN2

Ek : ZN2 −→ ZN2

N2 ⇔ (a,N) = 1.

m = xN + y ∈ {0, 1, . . . ,N2 − 1} = ZN2

Ek : ZN2 −→ ZN2

N2 ⇔ (a,N) = 1.

Exemplu

N = 26, a = 159, b = 580Text in clar: NO Text criptat: QYText in clar: ON Text criptat: NV

Functia de decriptare este

c 7→ m := a′c + b′ (mod N2)

unde a′ = a−1 (mod N2) , b′ = −a−1b (mod N2)Pentru atac: este necesar sa cunoastem unitati ale textului criptatcorespunzatoare a 2 digrafi din textul in clar(de exemplu: prin analiza frecventelor).

Exemplu

c 7→ m := a′c + b′ (mod N2)

Exemplu

c 7→ m := a′c + b′ (mod N2)

Exemplu

Decriptati mesajul NDXBHO stiind ca s-a realizat o criptare afinape digrafi, cu un alfabet cu 27 de caractere (A – Z ). De asemenea,se cunoaste ca prin criptarea digrafilor ın clar E S T se obtindigrafii ZA IA IW .

Matrici de criptare

Fiecare bloc are l caractere (l ∈ N∗ fixat). Fiecarui blocm1m2 . . .ml i se asociaza o matrice coloanam := (m1 m2 . . . ml)

T (mi ∈ ZN , i = 1, . . . , l).

. . .ml

7→ c :=

a11 . . . a1la21 . . . a2l. . . . . . . . .al1 . . . all

. . .ml

b1b2. . .bl

aij ∈ ZN (i , j = 1, . . . , l), bi ∈ ZN (i = 1, . . . , l)

m 7→ c := Am + B

Matrici de criptare

T (mi ∈ ZN , i = 1, . . . , l).

. . .ml

7→ c :=

a11 . . . a1la21 . . . a2l. . . . . . . . .al1 . . . all

. . .ml

b1b2. . .bl

aij ∈ ZN (i , j = 1, . . . , l), bi ∈ ZN (i = 1, . . . , l)

m 7→ c := Am + B

Matrici de criptare

T (mi ∈ ZN , i = 1, . . . , l).

. . .ml

7→ c :=

a11 . . . a1la21 . . . a2l. . . . . . . . .al1 . . . all

. . .ml

b1b2. . .bl

aij ∈ ZN (i , j = 1, . . . , l), bi ∈ ZN (i = 1, . . . , l)

m 7→ c := Am + B

Matrici de criptare

T (mi ∈ ZN , i = 1, . . . , l).

. . .ml

7→ c :=

a11 . . . a1la21 . . . a2l. . . . . . . . .al1 . . . all

. . .ml

b1b2. . .bl

aij ∈ ZN (i , j = 1, . . . , l), bi ∈ ZN (i = 1, . . . , l)

m 7→ c := Am + B

Matrici de criptare

Cheia: k = (A,B).Conditia de reversibilitate a criptarii:

A matrice inversabila in Ml(ZN)

detA ∈ Z×N ⇔ (detA,N) = 1

Functia de decriptare:

c 7→ m := A′c + B ′