slides crypto1 2015 h

Upload: lia-levy

Post on 10-Jan-2016

8 views

Category:

Documents


0 download

DESCRIPTION

w

TRANSCRIPT

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Criptografie

    Curs 1

    Anul II

    Februarie 2015

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    1 Planul cursului

    2 Ce este criptografia?

    3 Terminologie

    4 Repere istorice

    5 Elemente de complexitate a algoritmilor

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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 Vigene`re;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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Bibliografie

    1 Bucataru I.: Aritmetica, note de curs,http://www.math.uaic.ro/ bucataru/

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

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

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

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

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

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Criptografie

    Motive pentru a codifica informatia:

    pentru a o face inaccesibila persoanelor / entitatilorneautorizate criptografiepentru a detecta si eventual corecta erorile produse in timpultransmiterii teoria codurilorpentru 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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Ce este criptografia?

    kryptos + graphein (pio + )= 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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Aplicatii

    comunicatii

    securitatea fisierelor, bazelor de date

    transfer monetar electronic

    comert electronic

    semnari contracte

    e-mail

    parole, PIN

    control acces

    protocoale de securitate

    protectia copyright-ului

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Terminologie

    CriptosistemP = multimeamesajelor n clar

    K = multimeacheilor

    fC = multimeamesajelor cifrate

    C = multimeamesajelor cifrate

    K = multimeacheilor

    g C = multimeamesajelor n clar

    k K functia m 7 f (m, k) este injectivak K , k K astfel ncat

    m 7 c := f (m, k) 7 g(c , k ) = m

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Inca un exemplu

    Exemplul 4

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

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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..

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Repere istorice

    2000 i.C.: Mormantul lui Khnumhotep II

    1500 i.C.: Mesopotamia: semnaturi

    800 i.C.: Homer, Iliada, Bellerophon

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Repere istorice

    Sec. IV: Kama Sutra (Vatsyayana). Cartea 44: Stiinta scrieriin 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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Repere istorice

    1411: Michele Steno, substitutie omofonica

    1585:Blaise de Vigene`reTraite des chiffres

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

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Repere istorice

    1691: Antoine RossignolMarele Cifru al lui Ludovic al XIV-lea ( 1890).

    1840: Samuel Morse (1791-1872)

    1843: Edgar Allan PoeScorpionul de aur

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Repere istorice

    1854: Charles Babbage (1791-1871)Parintele calculatorului; sparge sistemul lui Vigene`re.

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

    1918: Gilbert Sandford VernamOne time pad

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Repere istorice

    1923: Arthur Scherbius . Enigma

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

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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)

    ...

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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 supnf (n)g(n) = C

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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 = (k1k2 . . . 10)b ; i {0, 1, . . . , b 1} ; k1 6= 0}.

    Atunci

    bk1 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).

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Elemente de complexitate a algoritmilor

    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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Elemente de complexitate a algoritmilor

    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)

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Clasificari ale algoritmilor / problemelor

    Fie A un algoritm decizional. Fie n o valoare a input-ului (oinstanta 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.

  • Outline Planul cursului Ce este criptografia? Terminologie Repere istorice Complexitate

    Clasificari ale algoritmilor / problemelor

    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(ekd ).Algoritmi care functioneaza in timp subexponential.

    Planul cursuluiCe este criptografia?TerminologieRepere istoriceElemente de complexitate a algoritmilor