BAZELE CRIPTOGRAFIEI

14 martie 2009

Grigore ALBEANU / USH-PIRC4

TerminologiePrin criptografie intelegem studiul metodelor matematice legate de securitatea informatiei, capabile sa asigure confidentialitatea, autentificarea si non-repudierea mesajelor, precum si integritatea datelor vehiculate.

Confidentialitate (privacy) = proprietatea de a pastra secretul informatiei, pentru ca aceasta sa fie folosita numai de persoanele autorizate.Integritatea datelor = proprietatea de a evita orice modificare (inserare, stergere, substituire partiala sau inlocuire totala) neautorizata a informatiei.Autentificare = Proprietatea de a identifica o entitate conform anumitor standarde. Se refera la: (a) autentificarea entitatii; (b) Autentificarea sursei de informare;Non - repudierea = Proprietatea care previne negarea unor evenimente anterioare.

Securitatea informatiei are si obiective suplimentare precum: autentificarea mesajelor, semnaturi, autorizare, validare, controlul accesului, certificare, timestamping, confirmarea receptiei, anonimitate, revocare

[1] A. Menezes, P. Oorschot, S. Vanstome, Handbook of Applied Cryptography

Criptografie - CriptologieDomeniul criptografiei cuprinde atat operatia de criptare (cifrare) a unui text, cat si eventualele ıncercari de descifrare si de aflare a cheii.In unele lucrari, cadrul general de lucru este numit criptologie, termenul de criptografie desemnand numai operatia de cifrare si descifrare legala.Locul criptanalistului:

Procesul de determinare a unei chei K folosind un text criptat w (asociateventual cu alte informatii auxiliare) se numeste ”criptanaliza”. Decriptarea si criptanaliza au ın final acelasi scop: aflarea textului clar. Diferenta consta ın faptul ca ın criptanaliza el trebuie aflat fara a sticheia de decriptare.

Sistem criptograficUn sistem criptografic este o structura (P, C, K, E, D), unde: P este multimea ”textelor clare”formate cu simboluri ale unui alfabet finit si nevid V (uzual V = {0, 1} sau {litere, cifre}), C este multimea ”textelor criptate”, peste un alfabet finit si nevid W (uzual W = V ), K este o multime finita si nevida de chei, fiecare cheie determina o metoda de criptare f din E, f[k] (ce este o functie injectiva) si o metoda de decriptare g, din D, g[k] astfel incatg[k](f[k](w)) = w. Daca f[k] este bijectiva (atunci este inversabila) sistemul criptografic este unul simetric.Calitatea unui sistem criptografic depinde de indeplinirea urmatoarelor cerinte:

1. Complexitatea evaluarii f[k](t) este mica, t este orice text clar;

2. Complexitatea evaluarii g[k](w) este mica, w este orice text criptat;

3. t nu se poate afla („deduce”) din w daca nu se cunoaste functia g[k].

Intreaga disciplina numita ”criptografie” se bazeaza pe o conjectura notata prescurtat P # NP. P reprezinta clasa problemelorrezolvabile prin algoritmi a carorcomplexitate este marginita superior de o functiie polinomiala ın lungimea datelor de intrare. Modelul standard de calculabilitate este masina Turing. NP este clasa problemelor rezolvabile prin algoritmi nedeterministicpolinomiali(care sunt inclusi ˆın algoritmii de complexitate cel putin exponentiala).

Evident, P#NP, dar se pare ca problema egalitatii este nedecidabila (ˆın termeni matematici).

Exemple de sisteme criptograficeSistemul CezarChampollion a descifrat hieroglifele folosind piatra de la Rosetta. Gasirea cheii duce la decriptare.Sistemul de criptare Hill, creat ın 1929 de Lester Hill.Cifruri de permutare: textul clar se ımparte ın blocuri de n (n cel putin 2) caractere, dupa care fiecarui bloc i se aplicao permutare fixata. Exemplu: sistemul RichelieuPropozitie. Un cifru de permutare este un sistem de criptareHill.

Cifruri cu substitutie. Un astfel de cifru consta ın ınlocuireafiecarui caracter din V cu alt caracter (din W).Exista doua clase mari de cifruri de substitutie: sisteme monoalfabetice si polialfabetice.

Sisteme de criptare monoalfabetice

Sistemul CezarSistemul afinSistemul de criptare PolybiosSistemul cavalerilor de Malta

Punctul slab al sistemelor de criptare monoalfabetice consta ın frecventa de aparitie a caracterelor ın text.

Sisteme de criptare polialfabetice

Primul sistem de criptare polialfabetic a fost creat de Leon Battista ın 1568Sistemul homofonic: este un sistem intermediar ıntre sistemele mono si celepolialfabetice. Principalul lui scop este de a evita atacul prin frecventa de aparitie acaracterelor. Se pare ca a fost utilizat prima oara ın 1401 de catre ducele de Mantua.Sistemul de criptare Playfair: inventat 1854 de Sir Charles Wheatstone.Sistemul de criptare Vigenere

Sisteme mecanice de criptare

Sistemul antic SkitalaCilindrul JeffersonMasini de criptat (C−36, Enigma, etc.)

Bibliografie (cartile anuntate, Atanasiu A., …)