slides crypto1 2015 h
DESCRIPTION
wTRANSCRIPT
-
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