of 32
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
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