Criptografie - math.uaic.rocriptografie/slides_crypto1_2017_h.pdf · OutlinePlanul cursuluiCe este...

Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

Criptografie

Curs 1

Anul II

Februarie 2017

1 Planul cursului

2 Ce este criptografia?

3 Terminologie

4 Repere istorice

5 Elemente de complexitate a algoritmilor

Planul cursului

1 Notiuni si rezultate de aritmetica, algoritmi: baze denumeratie, congruente, divizibilitate, algoritmul lui Euclid,estimari ale timpului de calcul; teste de primalitate; algoritmide factorizare

2 Criptosisteme cu cheie privata: criptosistemul lui Iulius Cezar,criptosisteme afine, matrici de cifrare, criptosistemul Vigenere;DES; Rijndael

3 Criptosisteme cu cheie publica: notiunea de cheie publica,semnatura, functii trapa; logaritmul discret; criptosisteme :RSA, Diffie-Hellman, ElGamal, Massey-Omura,Merkle-Hellman

4 Protocoale criptografice: schimburi de chei, autentificare,secret sharing, secret splitting, semnatura ın grup, pokermental, ...; functii hash

5 Curbe eliptice: Criptosisteme pe curbe eliptice.

Planul cursului

Obiective

1 Recapitularea unor notiuni fundamentale de aritmetica

2 Insusirea de ctre studenti a notiunilor, conceptelor i exemplelorfundamentale din criptografie si securitatea datelor

3 Familiarizarea studentilor cu tehnici de baza din criptografie sicriptanaliza

4 Constructia si analiza unor algoritmi criptografici de baza

Participantii la curs vor fi capabili sa:

Explice functionarea principalilor algoritmi criptografici

Utilizeze notiuni si rezultate de baza din aritmetica

Analizeze metode de securizare a informatiei

Calculeze cheile, mesajele ın clar si mesajele criptate ın cadrulprincipalelor criptosisteme studiate

Compare principalele metode de criptare sau de semnaturadigitala

Obiective

1 Recapitularea unor notiuni fundamentale de aritmetica

2 Insusirea de ctre studenti a notiunilor, conceptelor i exemplelorfundamentale din criptografie si securitatea datelor

3 Familiarizarea studentilor cu tehnici de baza din criptografie sicriptanaliza

4 Constructia si analiza unor algoritmi criptografici de baza

Participantii la curs vor fi capabili sa:

Explice functionarea principalilor algoritmi criptografici

Utilizeze notiuni si rezultate de baza din aritmetica

Analizeze metode de securizare a informatiei

Calculeze cheile, mesajele ın clar si mesajele criptate ın cadrulprincipalelor criptosisteme studiate

Compare principalele metode de criptare sau de semnaturadigitala

Bibliografie

1 www.math.uaic.ro/ criptografie

2 www.math.uaic.ro/ aritmetica

3 Menezes A., van Oorschot P., Vanstone, S.: Handbook ofapplied cryptography, http://www.cacr.math.uwaterloo.ca/hac/

4 Leoreanu V., Tamas V., Tofan I.: Curs de aritmetica, Edit.Univ. Al. I. Cuza, 2001

5 Buchmann J.: Introduction to Cryptography, Springer, 2004

6 Koblitz N.: A Course in Number Theory and Cryptography,Springer, 1994

7 Languasco A.; Zaccagnini A.: Introduzione alla Crittografia,Hoepli, Milano, 2004

Criptografie

Motive pentru a “codifica” informatia:

pentru a o face inaccesibila persoanelor / entitatilorneautorizate criptografie

pentru a detecta si eventual corecta erorile produse in timpultransmiterii teoria codurilor

pentru a o comprima in vederea reducerii spatiului necesarstocarii

CRIPTOGRAFIE: Studiul metodelor si tehnicilor matematicefolosite pentru tratarea informatiei astfel ıncat doar entitatiautorizate sa aiba acces la aceasta.TEORIA CODURILOR: Studiul metodelor si tehnicilormatematice folosite pentru tratarea informatiei astfel ıncat erorileaparute in cursul transmiterii acesteia sa poata fi corectate, iarinformatia initiala sa fie recuperata.

Criptografie

Ce este criptografia?

kryptos + graphein (κρνπτoς + γραφειν)= scriere ascunsa.

Are ın vedere, printre altele, urmatoarele aspecte:

CONFIDENTIALITATEA: O entitate neautorizata nu are accesla informatie.AUTENTIFICAREA: Identificarea entitatii care a emisinformatia si a entitatilor care acceseaza informatia.INTEGRITATEA DATELOR: Identificarea unei eventualemodificari neautorizate a informatiei.NON-REPUDIEREA: O entitate nu poate nega o actiune pecare a ınfaptuit-o anterior.

Aplicatii

comunicatii

securitatea fisierelor, bazelor de date

transfer monetar electronic

comert electronic

semnari contracte

e-mail

parole, PIN

control acces

protocoale de securitate

vot electronic

protectia copyright-ului

Terminologie

Criptografia: Studiul metodelor si tehnicilor matematicefolosite pentru tratarea informatiei astfel ıncat doar entitatiautorizate sa aiba acces la aceasta.

Criptanaliza: Studiul metodelor si tehnicilor matematicefolosite pentru atacul sistemelor criptografice.

Criptologie = criptografie + criptanaliza

Steganografie: Nu numai infomatia este ascunsa, ci si ınsusifaptul ca aceasta a fost transmisa.

Terminologie

Criptare (“encryption”): Succesiune de transformari aleinformatiei ın vederea ascunderii continutului acesteia pentruentitati neautorizate ( cifrare)

Text ın clar (“plaintext”): Mesajul (informatia) ınainte decriptare

Text cifrat (“cyphertext”): Mesajul (informatia) dupa criptare

Decriptare (“decryption”): Succesiune de transformari aletextului cifrat ın vederea reobtinerii textului ın clar

Cheie (“key”): Informatie necesara realizarii actiunii decriptare sau de decriptare

Terminologie

Exemple

Exemplul 1

Text ın clar: AZI ESTE PRIMUL CURSText cifrat: DCL HVWH SULPXO FXUVCheie: 3

Exemplul 2

Text ın clar: AZI ESTE PRIMUL CURSText cifrat: AXY MCFM TZYKIH GIZCCheie: 3

Exemplul 3

Text ın clar: AZI ESTE PRIMUL CURSText cifrat: KCFJIPCIXZVFWYIJGVAWXCheie: KEY

Exemple

Exemplul 1

Exemplul 2

Exemplul 3

Exemple

Exemplul 1

Exemplul 2

Exemplul 3

Exemple

Exemplul 1

Exemplul 2

Exemplul 3

Exemple

Exemplul 1

Exemplul 2

Exemplul 3

Exemple

Exemplul 1

Exemplul 2

Exemplul 3

Exemple

Exemplul 1

Exemplul 2

Exemplul 3

Exemple

Exemplul 1

Exemplul 2

Exemplul 3

Exemple

Exemplul 1

Exemplul 2

Exemplul 3

CriptosistemP = multimeamesajelor ın clar

K = multimeacheilor

f−→C = multimeamesajelor cifrate

C = multimeamesajelor cifrate

K = multimeacheilor

g−→P = multimeamesajelor ın clar

∀k ∈ K functia m 7→ fk(m) := f (m, k) este injectiva∀k ∈ K , ∃k ′ ∈ K astfel ıncat

m 7→ c := f (m, k) 7→ g(c , k ′) = m (⇔ gk ′ ◦ fk = IdP)

CriptosistemP = multimeamesajelor ın clar

K = multimeacheilor

f−→C = multimeamesajelor cifrate

C = multimeamesajelor cifrate

K = multimeacheilor

g−→P = multimeamesajelor ın clar

∀k ∈ K functia m 7→ fk(m) := f (m, k) este injectiva∀k ∈ K , ∃k ′ ∈ K astfel ıncat

m 7→ c := f (m, k) 7→ g(c , k ′) = m (⇔ gk ′ ◦ fk = IdP)

Tipuri de criptosisteme

Criptosistem simetric (cu cheie privata)

Cheia de criptare “=” cheia de decriptare

Criptosistem antisimetric (cu cheie publica)

Cheia de criptare “6=” cheia de decriptare

Inca un exemplu

Exemplul 4

Text ın clar: HELPText cifrat: EBLEZNCheie de criptare (publica): (5063,19)Cheie de decriptare (privata): (5063,259)

Inca un exemplu

Exemplul 4

Inca un exemplu

Exemplul 4

Inca un exemplu

Exemplul 4

Tipuri de atac

Atac: Incercare a unei entitati neautorizate ( “adversar”) de adecripta un text cifrat, fara a cunoaste cheia de decriptare.

Atac pasiv: Adversarul urmareste decriptarea informatiei.

Atac activ: Adversarul urmareste modificarea / ınlocuireainformatiei initiale, furtul de identitate, etc..

Tipuri de atac

Metode de atac:

Cyphertext-only attack: Adversarul are acces la texte cifrate .

Known-plaintext attack: Adversarul are acces la unul sau maimulte texte ın clar si la textele cifrate corespunzatoare.

Chosen-plaintext attack: Adversarul poate cripta texte ın clar,fara a cunoaste cheile.

Adaptative chosen-plaintext attack: Adversarul poate variatextul ın clar pe care ıl cifreaza ın functie de textele cifrateobtinute anterior.

Chosen-cyphertext attack: Adversarul poate decripta dar nucunoaste cheile.

Tipuri de atac

Metode de atac:

Tipuri de atac

Metode de atac:

Tipuri de atac

Metode de atac:

Tipuri de atac

Metode de atac:

Tipuri de atac

Metode de atac:

Repere istorice

2000 i.C.: Mormantul lui Khnumhotep II

1500 i.C.: Mesopotamia: semnaturi

800 i.C.: Homer, Iliada, Bellerophon

Repere istorice

600-500 i.C.: Biblie, Cartea lui Ieremia:ATBASH (codul ebraic)

475 i.C.: Scytal. Pasanius, Sparta

50 i.C.: Criptosistemul lui Iulius CezarSuetonius

Repere istorice

Sec. IV: Kama Sutra (Vatsyayana). Cartea 44: Stiinta scrieriiın cifrari secrete.

Sec. VIII-XV: Criptologia araba

Al-Khalil: Cartea mesajelor cifrateAl-Kindi: Scrieri despre descifrarea mesajelor cifrateQalqashandi: Enciclopedie ın 14 volume care include o sectiunede criptologie

Sec. XIII: Roger Bacon (1214-1294)Descrie 7 metode de a cripta mesaje.

Repere istorice

1411: Michele Steno, substitutie omofonica

1585:Blaise de VigenereTraite des chiffres

1587: Mary Stuarteste executata ca urmare a descifrarii unor mesaje criptateprin care complota la asasinarea reginei Elisabeta I

Repere istorice

1691: Antoine Rossignol“Marele Cifru” al lui Ludovic al XIV-lea (→ 1890).

1840: Samuel Morse (1791-1872)

1843: Edgar Allan Poe“Scorpionul de aur”

Repere istorice

1840: Samuel Morse (1791-1872)

Repere istorice

1840: Samuel Morse (1791-1872)

Repere istorice

1854: Charles Babbage (1791-1871)“Parintele calculatorului”; sparge sistemul lui Vigenere.

1917: 19 ianuarie, decriptarea telegramei lui Zimmerman catreAmbasada Germaniei ın Mexic duce la intrarea SUA ın razboi.

1918: Gilbert Sandford Vernam“One time pad”

Repere istorice

1923: Arthur Scherbius . Enigma

1939-1945: Razboiul provoaca o dezvoltare deosebita acriptografiei si criptanalizei.Marian Rejewski (1905-1980), Alan Turing (1912-1954)

Repere istorice

1923: Arthur Scherbius . Enigma

1939-1945: Razboiul provoaca o dezvoltare deosebita acriptografiei si criptanalizei.Marian Rejewski (1905-1980), Alan Turing (1912-1954)

Repere istorice

1948: Claude Elwood Shannon (1916-2001)Teoria informatiei, A Communications Theory of SecrecySystems

1976: DES (Data Encryption Standard).

1976: Whitfield Diffie (n.1944), Martin Hellman (n.1945):New Directions in Cryptography.

Repere istorice

1977: Ronald L. Rivest (n.1947), Adi Shamir (n.1952),Leonard M. Adleman (n.1945): RSA

2001: Rijndael devine Advanced Encryption Standard (AES)

Repere istorice

Elemente de complexitate a algoritmilorDefinitie

Fie f , g : N → R+ doua functii. Spunem ca cresterea lui f estemarginita de cea a lui g (sau cresterea lui f este de ordinul lui g),si scriem f = O(g), daca exista o constanta C > 0 astfel ıncatf (x) < C · g(x) pentru orice x .

Exemple: 3n2 − 7n + 10 = O(n2), 15en + 1356n2012 = O(en),ln(n7 + 3n − 4) = O(n), ln(n7 + 3n − 4) = O(ln n).Daca P este un polinom de gradul d , atunci P(n) = O(nd).

f = O(1) este echivalent cu faptul ca f este marginita.

f = O(g) daca si numai daca lim supn→∞f (n)g(n) = C <∞.

Spunem ca f creste polinomial daca exista d ∈ N∗ astfel ıncatf = O(nd).

Spunem ca f creste exponential daca exista d ∈ N∗ astfel ıncatf = O(en

Elemente de complexitate a algoritmilor

Fie n ∈ N, b ∈ N, b ≥ 2. Sa presupunem ca pentru a scrie n ınbaza b sunt necesare k cifre:

n = (εk−1εk−2 . . . ε1ε0)b ; εi ∈ {0, 1, . . . , b − 1} ; εk−1 6= 0}.

Atunci

bk−1 ≤ n < bk ⇔ k − 1 ≤ logb n < k ⇔ k = [logb n] + 1.

Lungimea numarului natural n (scris ın baza b) este

[logb n] + 1 =1

ln b· ln n + 1 = O(ln n).

Fie n ∈ N, b ∈ N, b ≥ 2. Sa presupunem ca pentru a scrie n ınbaza b sunt necesare k cifre:

n = (εk−1εk−2 . . . ε1ε0)b ; εi ∈ {0, 1, . . . , b − 1} ; εk−1 6= 0}.

Atunci

bk−1 ≤ n < bk ⇔ k − 1 ≤ logb n < k ⇔ k = [logb n] + 1.

Lungimea numarului natural n (scris ın baza b) este

[logb n] + 1 =1

ln b· ln n + 1 = O(ln n).

Timpul de calcul al unui algoritm A:Time(A) = numarul de operatii elementare necesare pentruobtinerea output-ului

- exprimat ca functie de lungimea datelor de intrare

- calculat ın situatia cea mai defavorabila.

In practica vom determina ordinul de crestere al functiei Time(A),

Time(A) = O(f )

cu f o functie cu cresterea cat mai mica.

Time(A) = O(f )

Operatie elementara (binara)

Input: bitii a, b, r . Output: bitii s, r .

a b r s r

0 0 0 0 01 0 0 1 00 1 0 1 00 0 1 1 01 1 0 0 11 0 1 0 10 1 1 0 11 1 1 1 1

Operatie elementara (binara)

Input: bitii a, b, r . Output: bitii s, r .

a b r s r

0 0 0 0 01 0 0 1 00 1 0 1 00 0 1 1 01 1 0 0 11 0 1 0 10 1 1 0 11 1 1 1 1

Exemplu: Fie m si n doua numere naturale, care scrise ın baza 2au cel mult k biti. Fie Ad algoritmul care realizeaza suma celordoua numere. Atunci

Time(Ad) = O(k).

Exercitii: Fie m, n, a numere naturale. Estimati timpul de calculpentru:

ınmultire: m · nridicarea la putere: ma

calculul n!

transformarea n (ın baza 10) −→ n (ın baza a)

Exemplu: Fie m si n doua numere naturale, care scrise ın baza 2au cel mult k biti. Fie Ad algoritmul care realizeaza suma celordoua numere. Atunci

Time(Ad) = O(k).

Exercitii: Fie m, n, a numere naturale. Estimati timpul de calculpentru:

ınmultire: m · nridicarea la putere: ma

calculul n!

transformarea n (ın baza 10) −→ n (ın baza a)

Clasificari ale algoritmilor / problemelor

Algoritmi decizionali / probleme de decizie: exista douavariante ale output-ului: DA sau NU (Adevarat sau Fals).Exemplu: teste de primalitate: algoritmi care decid daca unnumar natural este prim sau nu.

Algoritmi computationali / probleme de calcul: scopul esterezolvarea unei probleme de calcul.Exemplu: algoritmi de factorizare: input: n ∈ N; output:factorii primi ai lui n.

Algoritmi / probleme de cautare: scopul este alegerea, dintr-omultime finita (dar foarte mare) de variante, pe cea / celecare ındeplinesc anumite conditii. Solutia (output-ul) poate sanu fie unica.Exemplu: Problema comisului voiajor. Input: un graf finit siun varf fixat A. Output: un circuit de lungime minima carepleaca din A si contine toate varfurile grafului.

Fie A un algoritm decizional. Fie n o valoare a input-ului (o“instanta a problemei”) si sa presupunem ca algoritmul A verificadaca n are proprietatea P.Un astfel de algoritm decizional poate fi:

Algoritm determinist: daca output-ul este “DA”, atunci cusiguranta n are proprietatea P.

Algoritm probabilistic: daca output-ul este “DA”, atunciprobabil n are proprietatea P, cu o probabilitate p;probabilitatea ca n sa aiba proprietatea P devine cu atat maimare cu cat el trece testul de mai multe ori. Daca dacaoutput-ul este “NU”, atunci cu siguranta n nu areproprietatea P.

Algoritmi conditionati: corectitudinea algoritmului /raspunsului depinde de demonstrarea unui enunt matematicdespre care se presupune ca e adevarat, dar nu estedemonstrat.

Algoritmi neconditionati: corectitudinea algoritmului /raspunsului se bazeaza pe enunturi si teorii matematicedemonstrate.

Fie k lungimea input-ului algoritmului A.

Algoritmi care functioneaza in timp polinomial:∃d ∈ N∗,Time(A) = O(kd).

Algoritmi care functioneaza in timp exponential:Time(A) 6= O(kd),∀d ∈ N∗;∃d ∈ N∗,Time(A) = O(ek

Algoritmi care functioneaza in timp subexponential.

Algoritmi conditionati: corectitudinea algoritmului /raspunsului depinde de demonstrarea unui enunt matematicdespre care se presupune ca e adevarat, dar nu estedemonstrat.

Algoritmi neconditionati: corectitudinea algoritmului /raspunsului se bazeaza pe enunturi si teorii matematicedemonstrate.

Fie k lungimea input-ului algoritmului A.

Algoritmi care functioneaza in timp polinomial:∃d ∈ N∗,Time(A) = O(kd).

Algoritmi care functioneaza in timp exponential:Time(A) 6= O(kd),∀d ∈ N∗;∃d ∈ N∗,Time(A) = O(ek

Algoritmi care functioneaza in timp subexponential.

Criptografie - math.uaic.rocriptografie/slides_crypto1_2017_h.pdf · OutlinePlanul cursuluiCe este...

Documents

Transcript of Criptografie - math.uaic.rocriptografie/slides_crypto1_2017_h.pdf · OutlinePlanul cursuluiCe este...