Criptografia si codurile secrete

Rodica Bita

Aspecte introductive

Criptografia reprezintă o ramură a matematicii care se ocupă cu securizarea informației precum și cu autentificarea și restricționarea accesului într-un sistem informatic. În realizarea acestora se utilizează atât metode matematice (profitând, de exemplu, de dificultatea factorizării numerelor foarte mari), cât și metode de criptare cuantică. 

Criptologia este considerată ca fiind cu adevărat o știință de foarte puțin timp.

Aceasta cuprinde atât criptografia - scrierea secretizată - cât și criptanaliza.

De asemenea, criptologia reprezintă nu numai o artă veche, ci și o știința nouă: veche pentru că Iulius Cezar a utilizat-o deja, dar nouă pentru că a devenit o temă de cercetare academico-științifică abia începând cu anii 1970.

Această disciplină este legată de multe altele, de exemplu de teoria numerelor, algebră, teoria complexității, informatică.

Motive pentru a codica informatia:

Pentru a o face inaccesibila persoanelor / entiitatilor neautorizate ► criptografia;

Pentru a detecta si, eventual, corecta erorile produse in timpul transmiterii teoria codurilor ►teoria codurilor;

Pentru a o comprima in vederea reducerii spatiului necesar stocarii

CRIPTOGRAFIE: Studiul metodelor si tehnicilor matematice folosite pentru tratarea informatiei astfel incat doar entitatile autorizate sa aiba acces la aceasta.TEORIA CODURILOR: Studiul metodelor si tehnicilor matematice folosite pentru tratarea informatiei astfel incat erorile aparute in cursul transmiterii acesteia sa poata fi corectate, iar informatia initiala sa fie recuperata.

Ce este criptografia?

Termenul criptografie este compus din cuvintele de origine greacă κρυπτός kryptós(ascuns) și γράφειν gráfein (a scrie).

Are in vedere, printre altele, urmatoarele aspecte: CONFIDENTIALITATEA: O entitate neautorizata nu are acces

la informatie. AUTENTIFICAREA: Identicarea entitatii care a emis informatia

si a entitatilor care acceseaza informatia. INTEGRITATEA DATELOR: Identicarea unei eventuale

modifiari neautorizate a informatiei. NON-REPUDIEREA: O entitate nu poate nega o actiune pe

care a infaptuit-o anterior.

Aplicatii:

comunicatii securitatea fsierelor, bazelor de date transfer monetar electronic comert electronic semnari contracte e-mail parole, PIN control acces protocoale de securitate protectia copyright-ului

Terminologie

Criptografia: Studiul metodelor si tehnicilor matematice folosite pentru tratarea informatiei astfel incat doar entitatile autorizate sa aiba acces la aceasta.

Criptanaliza: Studiul metodelor si tehnicilor matematice folosite pentru atacul sistemelor criptografice.

Criptologie = criptografie + criptanaliza Steganografie: Nu numai infomatia este ascunsa, ci

si insusi faptul ca aceasta a fost transmisa.

Terminologie

Criptare (encryption): Succesiune de transformari ale informatiei in vederea ascunderii continutului acesteia pentru entitati neautorizate (cifrare);

Text in clar (plaintext): Mesajul (informatia) inainte de criptare;

Text cifrat (cyphertext): Mesajul (informatia) dupa criptare;

Decriptare (decryption): Succesiune de transformari ale textului cifrat in vederea reobtinerii textului in clar;

Cheie (key): Informatie necesara realizarii actiunii de criptare sau de decriptare;

Tipuri clasice de cifruri

Principalele tipuri clasice de cifruri sunt cifrurile cu transpoziție, care modifică ordinea literelor dintr-un mesaj (de exemplu „ajutor” devine „ojartu” într-o schemă trivială de rearanjare), și cifrurile cu substituție, care înlocuiesc sistematic litere sau grupuri de litere cu alte litere și grupuri de litere (de exemplu, „conexiune” devine „dpofyjvof” înlocuind fiecare literă cu următoarea din alfabet). Versiuni simple ale celor două tipuri de cifruri ofereau un grad mic de confidențialitate în cazul oponenților instruiți. Unul din primele cifruri cu substituție a fost Cifrul lui Cezar, în care fiecare literă din textul clar era înlocuită cu o literă aflată la un număr fix de poziții distanță de ea în alfabet. Cifrul a fost denumit astfel după Iulius Cezar despre care se spune că l-a folosit, cu o deplasare de 3, în comunicația cu generalii săi în timpul campaniilor militare.

Steganografia

Steganografia (ascunderea existenței mesajului) a fost și ea dezvoltată în antichitate.

Unul din primele exemple, de la Herodot, implica ascunderea unui mesaj tatuat pe capul unui sclav ras - sub părul crescut după tatuare.

Exemple mai moderne de steganografie includ utilizarea de cerneală invizibilă, micropuncte, și watermarking digital.

Exemplu:

Text în clar: AZI ESTE ZI DE CURS Text cifrat: DCL HVWH CL AH FXUV Cheie: 3

Sistemul de criptare:

Criteriile sistemului de criptare:

Pentru ca un sistem de criptare sa fie considerat bun, trebuie indeplinite trei criterii (enuntate de Francis Bacon ın sec. XVII):

1. Fiind date eK si α P, este usor de determinat eK(α);∈2. Fiind date dK si w C, este usor de determinat dK(w);∈3. α este imposibil de determinat din w, fara a cunoaste dK.Ultimul criteriu defineste – sub o forma vaga – ideea de ”securitate” a sistemului.La aceste criterii, Bacon adauga si o a patra regula:4 Textul criptat trebuie sa fie un text banal, fara suspiciuni.

Tipuri de criptosisteme

Criptosistem simetric (cu cheie privata)

Cheia de criptare = cheia de decriptare

Criptosistem antisimetric (cu cheie publica)

Cheia de criptare ≠ cheia de decriptare

Criptanaliza

Procesul de determinare a unei chei K folosind un text criptat α (asociat eventual cu alte informatii auxiliare) se numeste ”criptanaliza”.

Deci decriptarea si criptanaliza au in final acela si scop: aflarea textului clar. Diferent consta in faptul ca in criptanaliza el trebuie aflat fara a sti cheia de decriptare. Exista o ”regula de aur” a creatorilor de sisteme de criptare:Nu subestimati niciodata pe criptanalist.Regula s-a verificat din punct de vedere istoric pentru toate sistemele create pana in prezent: acestea, fie au fost sparte, fie, trebuie sa se revizuiasca periodic pentru a rezista atacurilor permanente ale intrusilor.

Tipuri de atac

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

Atac pasiv: Adversarul urmareste decriptarea informatiei. Atac activ: Adversarul urmareste modicarea / inlocuirea

informatiei initiale, furtul de identitate, etc.

Repere istorice

2000 i.H.: Mormantul lui Khnumhotep II 1500 i.H.: Mesopotamia: semnaturi 800 i.H.: Homer, Iliada, Bellerophon 600-500 i.H.: Biblie, Cartea lui Ieremia: ATBASH

(codul ebraic) 475 i.H.: Scytal. Pasanius, Sparta 50 i.H.: Criptosistemul lui Iulius Cezar Suetonius

Repere istorice

Sec. IV: Kama Sutra (Vatsyayana). Sec. VIII-XV: Criptologia araba:

Al-Khalil: Cartea mesajelor cifrate

Al-Kindi: Scrieri despre descifrarea mesajelor cifrate

Qalqashandi: Enciclopedie In 14 volume care include o sectiune de criptologie

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

Repere istorice

1411: Michele Steno, substitutie omofonica Leon Battista Alberti în preajma anului 1467 a folosit cifruri diferite pe

părți diferite ale mesajului (la limită, pentru fiecare literă diferită). El a inventat și ceea ce a fost poate primul dispozitiv autinat de cifrare, o roată ce implementa o realizare parțială a invenției sale.

1585: Blaise de Vigenère: Traite des chiffres. În cifrul polialfabetic Vigenère, criptarea se bazează pe un cuvânt cheie, care controlează substituția în funcție de ce literă a cuvântului cheie se folosește

1587: Mary Stuart este executata ca urmare a descifrarii unor mesaje criptate prin care complota la asasinarea reginei Elisabeta I

1691: Antoine Rossignol: Marele Cifru al lui Ludovic al XIV-lea 1840: Samuel Morse (1791-1872) 1843: Edgar Allan Poe Scorpionul de aur"

Repere istorice

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

1917: 19 ianuarie, are loc decriptarea telegramei lui Zimmerman catre Ambasada Germaniei in Mexic care duce la intrarea SUA in razboi.

1918: Gilbert Sandford Vernam “One time pad”.

Repere istorice

1923: Arthur Scherbius. EnigmaLa începutul secolului al XX-lea, printre care s-au numărat mașinile rotitoare — cea mai celebră fiind mașina Enigma folosită de Germania în al doilea război mondial. Cifrurile implementate de mașini similare dar îmbunătățite au adus o creștere a dificultății criptanalizei după al doilea război mondial.

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

Masina “Enigma”

Repere istorice

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

1976: DES (Data Encryption Standard). 1976: Whiteld Diffie (n.1944), Martin Hellman (n.1945): New Directions

in Cryptography 1977: Ronald L. Rivest (n.1947), Adi Shamir (n.1952), Leonard M.

Adleman (n.1945): RSADezvoltarea electronicii și a calculatoarelor numerice au făcut posibile cifruri mult mai complexe. Mai mult, calculatoarele au permis criptarea oricărui fel de date reprezentate de calculator în format binar, spre deosebire de cifrurile clasice care criptau doar texte în limbaj scris. Multe cifruri informatice pot fi caracterizate prin operarea pe secvențe de biți (uneori pe grupuri sau blocuri), spre deosebire de schemele clasice și mecanice, care manevrează caractere tradiționale (litere și cifre) direct. Totuși, calculatoarele au ajutat și criptanaliștii, ceea ce a compensat până la un punct creșterea complexității cifrurilor.

2001: Rijndael devine Advanced Encryption Standard (AES)

Data Encryption Standard

Totusi, cercetările academice deschise desfășurate în domeniul criptografiei sunt relativ recente, au început doar la jumătatea anilor 1970 cu specificațiile publice ale DES (Data Encryption Standard) la NBS, lucrarea Diffie-Hellman, și publicarea algoritmului RSA.

De atunci, criptografia a devenit o unealtă folosită pe scară largă în comunicații, rețele de calculatoare, și în securitatea informatică în general. 

Criptografia modernă

Criptografia cu chei simetrice se referă la metode de criptare în care atât trimițătorul cât și receptorul folosesc aceeași cheie (sau, mai rar, în care cheile sunt diferite, dar într-o relație ce la face ușor calculabile una din cealaltă). Acest tip de criptare a fost singurul cunoscut publicului larg până în 1976.

Criptografia modernă

Data Encryption Standard (DES) și Advanced Encryption Standard (AES) sunt cifruri pe blocuri care sunt considerate standarde de criptografie de guvernul american (deși DES a fost în cele din urmă retras după adoptarea AES).

În ciuda decăderii ca standard oficial, DES (mai ales în varianta triple-DES, mult mai sigură) rămâne încă popular; este folosit într-o gamă largă de aplicații, de la criptarea ATM, la securitatea e-mail-urilor și accesul la distanță securizat.

 Multe alte cifruri pe blocuri au fost elaborate și lansate, cu diverse calități. Multe au fost sparte.

Criptografia modernă

Cifrurile pe flux de date, în contrast cu cele pe blocuri, creează un flux arbitrar de material-cheie, care este combinat cu textul clar, bit cu bit sau caracter cu caracter. Într-un cifru pe flux de date, fluxul de ieșire este creat pe baza unei stări interne care se modifică pe parcursul operării cifrului. Această schimbare de stare este controlată de cheie, și, la unele cifruri, și de fluxul de text clar. RC4 este un exemplu de binecunoscut cifru pe flux

Criptografia modernă

Funcțiile hash criptografice (adesea numite message digest) nu folosesc neapărat chei, sunt o clasă importantă de algoritmi criptografici.

Aceștia primesc date de intrare (adesea un întreg mesaj), și produc un hash scurt, de lungime fixă, sub forma unei funcții neinversabile.

Bibliografie

A. Salomaa, Criptografie cu chei publice, Ed. Militara, 1996

www.descopera.ro http://www.galaxyng.com/adrian_atanasiu/cript.htm http://www.math.uaic.ro/~litcanu/

slides_crypto1_2013_h.pdf http://www.win.tue.nl/ gwoegi/P-versus-NP.htm S. Cook, http : //www.claymath.org/millennium/P vs

NP/Official Problem Description.pdf

Multumesc!