Securitate Si Criptografie

INTRODUCERE

Criptografia protejează informația vehiculată prin rețelele moderne de calculatoare. De-a lungul istoriei omenirii, dorința și necesitatea comunicării confidențiale au dus la perfecționarea științei scrierilor secrete, numite azi criptografie. Cunoștințele actuale referitoare la începuturile criptografiei sunt furnizate de diferite lucrări despre științele, religiile, războaiele de pe vremea unor civilizații de mult apuse. Este de apreciat că apariția criptografiei s-a petrecut în mod independent în mai multe părți ale lumii, la mai multe popoare. Dezvoltarea și continua perfecționare a criptografiei se datorează, în primul rând, războaielor și activității diplomatice.

Istoria criptografiei este deci lungă si pitorească. Evident, dezvoltarea tehnicilor de criptare a constituit o prioritate pentru organizațiile militare, care utilizau frecvent asemenea procedee. Înainte de apariția calculatoarelor, volumul mare de mesaje criptate sau transmise a fost gestionat de un număr mare de funcționari „codori”. Evident, tehnicile folosite erau limitate de capacitatea codorilor de realizare a transformărilor necesare și de însușirea de către aceștia a unor tehnici criptografice noi. Totuși, pericolul de capturare a codurilor de către „inamici” făcea necesară schimbarea periodică a metodei de criptare.

Necesitatea protecțiilor informațiilor a reprezentat un deziderat mereu actual al omenirii. Tehnici secrete de codificare a mesajelor au fost utilizate încă din antichitate și au prezentat o evoluție continuă de-a lungul timpului, afectând în multe cazuri chiar istoria.

Criptarea mesajelor și trimiterea lor sub aceasta forma este utilizată de foarte mult timp. Unul dintre primii care au folosit tehnici de criptare pentru trimiterea mesajelor a fost celebrul împărat Cezar si dacă ar trebui ales un singur exemplu al criptografiei „clasice”, acesta ar fi cifrul lui Cezar, nu atât datorită celebrității împăratului roman de care se leagă folosirea lui, ci pentru că principiul său de bază s-a menținut nealterat aproape două milenii. În comunicarea privată cu o persoană folosirea unui cod secret poate preveni citirea intenționată sau neintenționată a mesajelor de către cei care intră în posesia acestora, fie că trebuie să le transporte până la destinatar, fie că le interceptează în timp ce mesajul este transmis.

Încă din cele mai vechi timpuri tehnologia în ceea ce privește domeniul criptografic a cunoscut progrese majore, și tocmai de aceea se poate spune că în momentul de față se asistă la o informatizare pe scară largă a mai multor instituții, lucru datorat avantajelor aduse de sistemele informatice: colectarea, transmiterea, procesarea și regăsirea datelor se face mai rapid, mai ieftin, mai ușor, cu o economie mai mare de spațiu. Astfel se face o economie semnificativă de timp și de efort care pot fi investite pentru realizarea altor acte de mai bună calitate. Cu toate acestea există însă și un dezavantaj major, și anume securitatea datelor devine mai greu de asigurat. Se poate spune că unul din cele mai studiate domenii din zilele noastre este criptarea mesajelor. Complexitatea tehnicilor de criptare și de trimitere a mesajelor crește permanent pentru a obține o securitate cât mai ridicată a comunicațiilor.

Puține sunt persoanele care să nu fi încercat, măcar o dată, transmiterea cifrată a unor mesaje personale foarte importante. Și mai puține sunt, probabil, cele care nu s-au amuzat niciodată rezolvând jocuri rebus unde, pe baza unor frânturi de mesaj trebuie descoperită regula de reconstituire a mesajului. Explicația este atracția firească pe care o prezintă un astfel de exercițiu intelectual și satisfacția pe care ți-o dă reușita rezolvării. Criptografia sau știința codificării informației în vederea împiedicării acceselor neautorizate are o lungă istorie, confidențialitatea comunicării fiind o cerință a tuturor timpurilor.

Criptarea sau cifrarea definită și ca un mecanism puternic de asigurare a confidențialității asigura confidențialitatea datelor atunci când mecanismele de împiedicare a accesului la date au eșuat. Este un lucru înțelept să se folosească și criptarea, deoarece sistemele informatice sunt foarte complexe, atât din punct de vedere hard, cât și soft, așa că întotdeauna vor exista breșe în sistemele de restricționare a accesului. Dacă mecanismul de criptare a datelor este puternic și aplicat în mod corect, atacatorul va avea în față niște date pe care nu va putea să le folosească.

Criptografia este știința care folosește matematica pentru a codifica si decodifica informațiile. Cu ajutorul criptografiei se pot stoca ușor informațiile sau se pot transmite de-a lungul unor rețele nesigure, de exemplu Internetul, și nu pot fi citite decât de aceia care posedă cheia pentru decriptare. În timp ce criptografia este știința securizării informațiilor, criptanaliza este știința analizării și verificării securității comunicației. Criptanaliza clasică implică combinații interesante de judecăți analitice, aplicații ale metodelor matematice, căutarea șabloanelor, determinare si noroc. Criptologia le include pe ambele, criptografia și criptanaliza.

Criptografia poate fi puternică sau slabă. Puterea procesului de criptografie este măsurată în timp și în resurse informatice necesare pentru a cripta un text. Rezultatul unei criptografii avansate este un text criptat, foarte greu de descifrat fără a fi în posesia unui instrument de decriptare. Cât de dificil? Dată fiind toată puterea de calcul din momentul de față și tot timpul disponibil, luând în considerare un miliard de calculatoare care fac un miliard de operații pe secundă, este practic imposibil de descifrat rezultatul unei criptografii avansate înainte de sfârșitul Universului. Unii s-ar putea gândi deci, că criptografia avansată poate fi folosită foarte bine chiar împotriva unui criptanalist extrem de bine motivat. Cine spune asta? Nimeni n-a dovedit că este posibil ca folosind cea mai avansată tehnică de criptografie posibilă astăzi poate fi considerat la fel mâine, la puterea de calcul a zilei de mâine. Oricum, criptografia avansată este cea mai bună dintre cele disponibile astăzi. Vigilența si dorința de a păstra informațiile intacte vor proteja mai bine oricum decât tendința de a proteja prin impenetrabilitatea sistemelor informatice.

În cadrul criptografiei, criptarea se definește ca fiind procesul de aducere a informației din forma ei inițială, inteligibilă, într-o formă neinteligibilă, astfel încât să fie făcută imposibil de citit fără cunoștințe secrete. Deci textul inițial, care se dorește a fi protejat, se numește „text în clar”, iar rezultatul criptării se numește „text cifrat” sau „criptogramă”. Decriptarea sau descifrarea este procesul invers, recuperând textul în clar din textul cifrat.

CAPITOLUL I. DELIMITÃRI CONCEPTUALE PRIVIND CRIPTOGRAFIA

1.1. Noțiuni introductive

Criptografia protejează informația vehiculată prin rețelele moderne de calculatoare. De-a lungul istoriei omenirii, dorința și necesitatea comunicării confidențiale au dus la perfecționarea științei scrierilor secrete, numite azi criptografie. Cunoștințele actuale referitoare la începuturile criptografiei sunt furnizate de diferite lucrări despre științele, religiile, războaiele de pe vremea unor civilizații de mult apuse. Este de apreciat că apariția criptografiei s-a petrecut în mod independent în mai multe părți ale lumii, la mai multe popoare. Dezvoltarea și continua perfecționare a criptografiei se datorează, în primul rând, războaielor și activității diplomatice.

Istoria criptografiei este deci lungă si pitorească. Evident, dezvoltarea tehnicilor de criptare a constituit o prioritate pentru organizațiile militare, care utilizau frecvent asemenea procedee. Înainte de apariția calculatoarelor, volumul mare de mesaje criptate sau transmise a fost gestionat de un număr mare de funcționari „codori”. Evident, tehnicile folosite erau limitate de capacitatea codorilor de realizare a transformărilor necesare și de însușirea de către aceștia a unor tehnici criptografice noi. Totuși, pericolul de capturare a codurilor de către „inamici” făcea necesară schimbarea periodică a metodei de criptare.

Necesitatea protecțiilor informațiilor a reprezentat un deziderat mereu actual al omenirii. Tehnici secrete de codificare a mesajelor au fost utilizate încă din antichitate și au prezentat o evoluție continuă de-a lungul timpului, afectând în multe cazuri chiar istoria.

Criptarea mesajelor și trimiterea lor sub aceasta forma este utilizată de foarte mult timp. Unul dintre primii care au folosit tehnici de criptare pentru trimiterea mesajelor a fost celebrul împărat Cezar si dacă ar trebui ales un singur exemplu al criptografiei „clasice”, acesta ar fi cifrul lui Cezar, nu atât datorită celebrității împăratului roman de care se leagă folosirea lui, ci pentru că principiul său de bază s-a menținut nealterat aproape două milenii. În comunicarea privată cu o persoană folosirea unui cod secret poate preveni citirea intenționată sau neintenționată a mesajelor de către cei care intră în posesia acestora, fie că trebuie să le transporte până la destinatar, fie că le interceptează în timp ce mesajul este transmis.

Încă din cele mai vechi timpuri tehnologia în ceea ce privește domeniul criptografic a cunoscut progrese majore, și tocmai de aceea se poate spune că în momentul de față se asistă la o informatizare pe scară largă a mai multor instituții, lucru datorat avantajelor aduse de sistemele informatice: colectarea, transmiterea, procesarea și regăsirea datelor se face mai rapid, mai ieftin, mai ușor, cu o economie mai mare de spațiu. Astfel se face o economie semnificativă de timp și de efort care pot fi investite pentru realizarea altor acte de mai bună calitate. Cu toate acestea există însă și un dezavantaj major, și anume securitatea datelor devine mai greu de asigurat. Se poate spune că unul din cele mai studiate domenii din zilele noastre este criptarea mesajelor. Complexitatea tehnicilor de criptare și de trimitere a mesajelor crește permanent pentru a obține o securitate cât mai ridicată a comunicațiilor.

Puține sunt persoanele care să nu fi încercat, măcar o dată, transmiterea cifrată a unor mesaje personale foarte importante. Și mai puține sunt, probabil, cele care nu s-au amuzat niciodată rezolvând jocuri rebus unde, pe baza unor frânturi de mesaj trebuie descoperită regula de reconstituire a mesajului. Explicația este atracția firească pe care o prezintă un astfel de exercițiu intelectual și satisfacția pe care ți-o dă reușita rezolvării. Criptografia sau știința codificării informației în vederea împiedicării acceselor neautorizate are o lungă istorie, confidențialitatea comunicării fiind o cerință a tuturor timpurilor.

Informațiile care pot fi citite și înțelese fără a folosi instrumente speciale, sunt numite „text în clar” sau în limba engleză „plaintext” ori „cleartext”. Metoda de camuflare a textului în clar în așa fel încât substanța să nu sufere modificări semantice, este denumită criptare. Din criptarea unui „plaintext” rezultã un text ilizibil numit criptotext. Se folosește criptarea pentru a fi sigur că informația este inaccesibilă oricărei persoane care nu deține instrumentul necesar decriptării, chiar dacă oricine poate vedea datele în formă criptografică. Oricum nu va înțelege nimic, care să conducă spre descifrarea textului original. Procesul retransformării criptogramei în textul original este numit decriptare.

Criptarea sau cifrarea definită și ca un mecanism puternic de asigurare a confidențialității asigura confidențialitatea datelor atunci când mecanismele de împiedicare a accesului la date au eșuat. Este un lucru înțelept să se folosească și criptarea, deoarece sistemele informatice sunt foarte complexe, atât din punct de vedere hard, cât și soft, așa că întotdeauna vor exista breșe în sistemele de restricționare a accesului. Dacă mecanismul de criptare a datelor este puternic și aplicat în mod corect, atacatorul va avea în față niște date pe care nu va putea să le folosească.

Criptografia este știința care folosește matematica pentru a codifica si decodifica informațiile. Cu ajutorul criptografiei se pot stoca ușor informațiile sau se pot transmite de-a lungul unor rețele nesigure, de exemplu Internetul, și nu pot fi citite decât de aceia care posedă cheia pentru decriptare. În timp ce criptografia este știința securizării informațiilor, criptanaliza este știința analizării și verificării securității comunicației. Criptanaliza clasică implică combinații interesante de judecăți analitice, aplicații ale metodelor matematice, căutarea șabloanelor, determinare si noroc. Criptologia le include pe ambele, criptografia și criptanaliza.

Criptografia poate fi puternică sau slabă. Puterea procesului de criptografie este măsurată în timp și în resurse informatice necesare pentru a cripta un text. Rezultatul unei criptografii avansate este un text criptat, foarte greu de descifrat fără a fi în posesia unui instrument de decriptare. Cât de dificil? Dată fiind toată puterea de calcul din momentul de față și tot timpul disponibil, luând în considerare un miliard de calculatoare care fac un miliard de operații pe secundă, este practic imposibil de descifrat rezultatul unei criptografii avansate înainte de sfârșitul Universului. Unii s-ar putea gândi deci, că criptografia avansată poate fi folosită foarte bine chiar împotriva unui criptanalist extrem de bine motivat. Cine spune asta? Nimeni n-a dovedit că este posibil ca folosind cea mai avansată tehnică de criptografie posibilă astăzi poate fi considerat la fel mâine, la puterea de calcul a zilei de mâine. Oricum, criptografia avansată este cea mai bună dintre cele disponibile astăzi. Vigilența si dorința de a păstra informațiile intacte vor proteja mai bine oricum decât tendința de a proteja prin impenetrabilitatea sistemelor informatice.

În cadrul criptografiei, criptarea se definește ca fiind procesul de aducere a informației din forma ei inițială, inteligibilă, într-o formă neinteligibilă, astfel încât să fie făcută imposibil de citit fără cunoștințe secrete. Deci textul inițial, care se dorește a fi protejat, se numește „text în clar”, iar rezultatul criptării se numește „text cifrat” sau „criptogramă”. Decriptarea sau descifrarea este procesul invers, recuperând textul în clar din textul cifrat.

1.2 Evoluția criptografiei

Criptografia în antichitate

Egiptul antic de acum circa patru mii de ani ne furnizează primele indicii despre criptografie sub forma unor formule funerare care conțin, într-o formă incipientă, elemente constitutive ale științei de astăzi. Grecii au practicat în multe variante scrierea secretă, așa cum atestă documentele istorice.

În lucrări antice din secolele IV-V î.e.n. se prezintă diferite variante de scriere secretă, cum ar fi „discul cu orificii”, „bastonul cu panglica scitală”. Istoricul grec Polibiu, martor ocular la al treilea război punic (149-146 î.e.n.), prezintă în lucrarea sa „Istoria generală” următorul sistem de cifrare: un pătrat conține literele grecești și are numerotate liniile și coloanele. Fiecare literă se codifică prin două cifre date de numerele de linie și coloană ale celulei în care se află. Roma antică a folosit „cifrul lui Cezar” în transmiterea mesajelor. Principiul substituției (fiecare literă este înlocuită cu cea aflată la o distanță de 3 în alfabetul latin), ce stă la baza acestui cifru, s-a menținut nealterat aproape două milenii.

Criptografia clasică

Societatea feudală timpurie, ridicată pe ruinele Imperiului roman, nu a favorizat dezvoltarea științei și culturii. Descoperirea tiparului în jurul anului 1440 a dat un nou impuls preocupărilor umane pentru dezvoltarea criptografiei.

În perioada Renașterii umaniștii au studiat manuscrise ale autorilor antici și au redescoperit, printre altele, metodele de cifrare folosite în antichitate. Extinderea și amplificarea relațiilor diplomatice dintre diferitele state feudale au dat un nou avânt dezvoltării criptologiei. Curțile regale și statul papal dispuneau de criptologi și criptanaliști.

„Poligraphiae libri sex” este prima carte asupra criptologiei, a apărut în anul 1518 și descrie metoda de cifrare numită „tablou de transpoziție”, bazată pe transpoziții și substituții.

Giambattista della Porta scrie în anul 1563 lucrarea „De Furtivis Literarum Notis” în care prezintă drumul parcurs de criptologie, observații critice asupra metodelor folosite de predecesori și aduce contribuții personale la dezvoltarea criptologiei pe baza „tabelelor de frecvență a literelor”, propunând un nou procedeu de cifrare bazat pe transpoziții și substituții.

Vigenère scrie în anul 1586 cartea „Tratatul cifrurilor sau modalități secrete de a scrie” în care prezintă metode noi de cifrare bazate pe substituția polialfabetică.

Cardan (1501-1576), matematician italian, naturalist, medic renumit al epocii sale, a influențat și criptografia. În lucrarea „De rerum varietate” a conceput mărirea siguranței secretului prin schimbarea cheii la fiecare mesaj, utilizând mesajul însuți drept cheie de cifrare prin folosirea „grilei cu ferestre”.

Rossignol a fost primul criptolog profesionist din Franța și printre cei mai abili descifratori din Europa. El a contribuit la multe succese diplomatice și victorii în bătăliile purtate de Ludovic al XIII-lea și Ludovic al XIV-lea. A reușit să modifice modul de stabilire a corespondenței între elementele clare ale mesajului și cifruri, introducând două tipuri de corespondențe, numite „tabel de cifrare” și „tabel de descifrare”.

Maiorul Bazaries a contribuit în anii 1800 la dezvoltarea serviciului de cifrare al armatei franceze, a descifrat „Marele cifru” folosit de Ludovic al XIV-lea (a cărui cheie a fost mult timp pierdută), a inventat dispozitivul numit „cilindru de cifrare” prin care s-au pus bazele cifrării mecanizate. Perfecționarea mașinilor de cifrat este legată de nivelul de dezvoltare al științei și tehnicii din epoca respectivă. Primele mașini de cifrat erau construite din elemente simple, cum ar fi roți dințate, elevatori etc.

Constructorii mașinilor de cifrat au urmărit de-a lungul timpului două scopuri: mărirea siguranței în cifrare și simplificarea activității de cifrare. Dezvoltarea mecanizării a dus la apariția mașinilor de cifrat din ce în ce mai performante construite cu discuri, roți dințate, bare și puse în funcțiune manual sau prin intermediul unui arc.

Telegraful, folosit pentru transmiterea unor volume mari de date în condițiile dezvoltării impetuoase a industriei și comerțului, a stimulat dezvoltarea criptografiei pentru transmiterea în secret a informațiilor în condiția unui trafic intens de mesaje. Mașinile de tip telegraf au mărit ritmul cifrării până la viteza dactilografierii (150-200 litere/minut).

Radioul, folosit pentru transmiterea informațiilor secrete de natură militară și diplomatică începând cu perioada premergătoare Primului Război Mondial, a impus în anii 1920 introducerea unei metode noi în criptografie numită „bloc cu o singură utilizare”. Mașina Hagelin C-48 a fost construită la nivelul anilor 1940 și a fost utilizată de către armata americană în al doilea război mondial sub numele M-209. Construcția mecanică cu roți dințate, cutii, bare, mânere a mașinii M-209 evidențiază tehnici general valabile pentru elaborarea dispozitivelor de cifrare, combină textul clar, caracter cu caracter, cu un șir cheie (care este o secvență pseudo aleatoare derivată din cheie), obținându-se textul cifrat.

Mașinile cu rotor au fost folosite în perioada 1940-1950. Cele mai cunoscute modele: M-134 sau SIGABA (SUA), TYPEX (Anglia), ENIGMA (Germania). Componenta centrală este rotorul cu contacte electrice sau roata cablată. În perioada celui de-al doilea război mondial s-au produs mari acumulări cantitative în domeniul criptologiei (cifrarea și descifrarea mesajelor).

C. E. Shannon contribuie fundamental la saltul calitativ în dezvoltarea criptologiei prin două lucrări de referință: „The Matematical Theory of Communication” (Bell System Journal, iulie și octombrie 1948) și „Communication Theory of Secrecy Systems” (Bell System Journal, octombrie 1949). El reușește să evidențieze legătura dintre teoria informației și criptologie, dă o definiție abstractă a sistemului secret și-i stabilește structura matematică. Considera că problema decriptării criptogramelor interceptate este asemănătoare cu problema decodificării mesajului în prezența zgomotului. Demonstrează posibilitatea de a construi un sistem secret cu o mulțime finită de chei în care echivocul criptanalistului nu tinde către zero, chiar dacă volumul criptogramei tinde spre infinit.

Criptografia în epoca modernă

Având în vedere faptul că transmisia de date în Internet este neprotejată, a apărut necesitatea dezvoltării tehnicilor de criptare în direcția automatizării acestora si a implementării lor în rețele de calculatoare. Astfel, utilizarea unor algoritmi pentru criptarea informațiilor transmise va deveni principalul mijloc de rezolvare a problemelor de interceptare în rețele.

În descrierea unei transmisii de date prin rețea se obișnuiește să se numească generic "mesaj" un ansamblu de date trimis de un „emițător” unui „receptor”. Printr-o metodă de criptare, mesajele vor fi transformate, pe baza unei chei de criptare, astfel încât să poată fi înțelese doar de destinatar.

Dezvoltarea sistemelor criptografice cunoaște o cotitură semnificativă în epoca modernă, datorită următoarelor patru elemente

Utilizarea calculatorului electronic a permis potențarea gamei de instrumente folosite efectiv în execuția algoritmilor de cifrare. Folosirea unor chei de dimensiuni mai mari, au sporit rezistența la atacurile criptanalitice, datorită puterii de calcul mereu sporite Criptografia clasică asigura secretul mesajelor în principal prin nedivulgarea algoritmului (metodei) de criptare și complicarea lui combinând substituții și transpoziții. Criptografia modernă asigură secretul mesajelor prin folosirea unor chei de cifrare de dimensiuni mari frecvent schimbate, chiar dacă se cunoaște algoritmul de cifrare. Pe această idee se bazează Standardul american de cifrare a datelor DES (Data Encryption Standard) adoptat în 1977 și bazat pe criptografia simetrică.

Dezvoltarea rețelelor de calculatoare și a Internetului au impus dorința utilizatorilor (persoane, organizații economice și comerciale) pentru păstrarea secretului și siguranței poștei electronice, transferului electronic de fonduri, comunicațiilor și altor aplicații, ceea ce a dus la perfecționarea metodelor și algoritmilor de criptare.

Criptografia asimetrică sau cu chei publice aduce un principiu nou prin cercetările din 1976 ale lui Whitfield Diffie și Martin Hellman de la Universitatea Stanford-California.

Criptografia simetrică folosea o singură cheie, atât la cifrarea mesajului cât și la descifrarea lui. Trimiterea cheii de la emițătorul mesajului la receptorul lui, se realiza printr-un canal sigur (clasic: un curier, modern: prin telefon). Criptografia asimetrică folosește două chei diferite, una pentru cifrarea mesajului la emițător, cealaltă pentru descifrarea lui la receptor. Deoarece deducerea unei chei din cealaltă este imposibilă, una din chei poate fi făcută publică și poate fi folosită de către oricine pentru a transmite un mesaj cifrat; doar destinatarul care deține a doua cheie (secretă) poate descifra și utiliza mesajul. Autentificarea mesajelor poate fi asigurată prin tehnica cheilor publice. Datorită acestor avantaje, guvernul SUA dorește schimbarea standardului de cifrare a datelor, orientându-se în 1990 și 1991 spre metodele de cifrare asimetrică RSA (prezentă deja în domeniul industriei) și DSS (dezvoltată de Agenția Națională de Securitate a SUA).

Criptografia cu chei în custodie (Key Escrow Systems) este un concept nou pe care au încercat să-l impună în anii ‘90 agențiile statului pentru securitatea națională a SUA. Acest concept ar fi dus către elaborarea unui sistem care permitea agențiilor statului să decripteze legal mesajele transmise în rețelele de calculatoare ale unor firme, corporații și persoane. Conceptul reprezintă nucleul programului guvernamental Clipper (numit și EES – Escrowed Encryption Standard), care este integrat în programul Capstone. Motivațiile legale și sociale ale acestui „drept de ascultare” sunt discutabile și au dus la tensiuni între interesele publice (pentru protecția informațiilor) și interesele guvernamentale (pentru accesul la informațiile adversarilor). În prezent s-a ajuns la concluzia că este nevoie de mecanisme care să permită unei persoane autorizată accesul la informație, dar protejându-se informația în fața altor persoane.

În epoca modernă criptografia a devenit un domeniu de intense cercetări academice și nu numai. Tradițional, criptografii foloseau algoritmi simpli asociați cu chei de securitate foarte lungi. Azi se urmărește crearea unor algoritmi de criptare atât de complecși încât să fie practic ireversibili, chiar dacă un criptanalist achiziționează cantități foarte mari de text cifrat. O altă caracteristică a criptografiei moderne constă în automatizarea tehnicilor clasice, prin folosirea unor dispozitive special concepute. Transpozițiile si substituțiile vor fi implementate cu circuite simple, de viteză mare, care vor fi conectate în cascadă astfel încât dependenta ieșirii de intrare devine extrem de complicată si dificil de descoperit.

În 1977, guvernul SUA a adoptat ca standard oficial pentru informațiile nesecrete un cifru produs si dezvoltat de IBM, numit DES (Data Encryption System), care a fost larg adoptat în industrie. DES este cel mai popular algoritm cu cheie secretă; el continuă să stea la baza unor sisteme folosite în mod curent. DES folosește (uzual) o cheie de 56 de biți. Aceasta a fost în cele din urmă adoptată în locul uneia de 128 de biți, neagreată de NSA (National Security Agency), agenția „spărgătoare de coduri a guvernului”, care dorea supremația în domeniul criptografic.

Din 1977, cercetătorii în criptografie au încercat să proiecteze mașini pentru a sparge DES. Prima asemenea mașină (1977) a fost concepută de Diffie si Hellman, avea nevoie de mai puțin de o zi iar costul ei a fost estimat la 20 de milioane de dolari. După aproape 2 decenii, costul unei astfel de mașini a ajuns la 1 milion de dolari iar timpul necesar spargerii codului a scăzut la 4 ore. Ulterior, s-au dezvoltat si alte metode, cum ar fi folosirea unui cip DES încorporat (loteria chinezească).

În scopul decriptării s-ar mai putea folosi mecanisme soft specifice (cum ar fi algoritmul asimetric Diffie-Hellman) si resursele libere ale unor calculatoare cu destinație universală. Astfel, s-a demonstrat că rularea pe mai multe calculatoare a unor programe distribuite de criptare (uzual, pe un număr mare de mașini, de ordinul miilor sau chiar zecilor de mii) creste considerabil eficienta procesului de decriptare.

Un alt cifru renumit este IDEA (International Data Encryption Algorithm), realizat de doi cercetători la Politehnica Federală din Zürich (ETHZ). Acest algoritm folosește o cheie de 128 de biți si este inspirat din metodele anterioare – DES si cele imaginate pentru spargerea DES.

Un alt algoritm performant a fost descoperit de un grup de cercetători de la MIT – Ronald Rivest, Adi Shamir, Leonard Adelman, și s-a numit cu inițialele creatorilor lui RSA. Algoritmul de criptare RSA folosește o cheie publică. Se observă că utilizarea unor astfel de algoritmi de criptare a datelor asigură transmisii confidențiale de date în rețele neprotejate, rezolvând problema interceptării. De fapt, riscul de interceptare / modificare nu dispare cu totul, din cauză că orice mesaj criptat poate fi în general decriptat fără a deține cheia corespunzătoare, dacă se dispune de suficiente resurse materiale si de timp.

Evident, dimensiuni variate ale cheii asigură diferite grade de confidențialitate iar perioada de timp necesară pentru decriptare poate fi prevăzută în funcție de mărimea cheii utilizate. Totuși, dacă procesul de decriptare este lent, este posibil ca în momentul în care s-ar obține datele dorite, acestea să nu mai fie actuale sau utile.

Timpul de decriptare depinde în mod natural si de puterea procesoarelor utilizate în acest scop, astfel încât utilizarea distribuită a unui foarte mare număr de procesoare poate duce la o micșorare considerabilă a timpului necesar. Din acest motiv, pentru transmisii de date în care este necesară o confidențialitate strică se utilizează chei de dimensiuni mult mai mari, chiar pentru algoritmul DES (de 256, 512, 1024 si chiar 2048 sau 4096 de biți), știut fiind că timpul necesar decriptării crește exponențial cu dimensiunea cheii de criptare / decriptare.

Pentru utilizatorii obișnuiți ai Internet-ului, cei mai convenabili algoritmi de criptare sunt cei cu cheie publică fiindcă folosirea lor nu implică schimbul preliminar de chei pe canale de transmisie protejate, ca în cazul algoritmilor cu cheie secretă. Cheia publică poate fi distribuită fără restricții pe intranet (rețeaua locală) sau Internet, iar mesajele criptate cu această cheie de un emițător vor putea fi decriptate numai utilizând cheia privată, care este deținută exclusiv de către destinatar. Astfel, nici măcar expeditorul nu ar putea realiza decriptarea mesajului trimis.

1.3 Tipuri de criptografie

Criptografia se folosește pentru securizarea comunicațiilor. Ea ar trebui sa aibă următoarele proprietăți:

Confidențialitate: doar un receptor autorizat al mesajului ar trebui sa fie capabil sa extragă conținutul mesajului din forma sa criptată. Altfel, nu ar trebui sa fie posibil sa se obțină vreo informație semnificativă despre conținutul mesajului.

Integritate: destinatarul ar trebui să poată detecta dacă mesajul a fost modificat în cursul transmisiei.

Autentificare: destinatarul ar trebui să poată să-l identifice pe expeditor, și să verifice că presupusul expeditor într-adevăr a transmis mesajul.

Nerepudiere: expeditorul nu ar trebui să poată nega că a transmis mesajul.

Protecție la trimitere multiplă: mesajului nu ar trebui să-i fie permisă trimiterea multiplă la destinatar fără ca expeditorul să știe acest lucru.

Criptografia poate asigura mecanisme pentru a atinge obiectivele de mai sus. Totuși, unele scopuri nu sunt întotdeauna necesare, practice sau dezirabile în anumite contexte. De exemplu, expeditorul unui mesaj ar vrea sa rămână anonim, și în acest caz, nerepudierea ar fi nepotrivită. Există două mari categorii de cifruri, una cu cheie simetrică și una cu cheie asimetrică.

Criptografia cu cheie simetrică

Unul din principiile mai recent apărute în criptanaliză constă în utilizarea unei alte chei pentru decodificarea mesajului decât cea folosită la codificare. Această tehnică este mai eficientă dar complică puțin procedeul general si de aceea se preferă când criptarea / decriptarea se realizează automat. Evident, dimensiunea unei chei de criptare (exprimate în general în biți) este o măsură a nivelului de securitate dat de acea cheie, ea indicând rezistenta mesajului cifrat la încercările de descifrare de către cineva care nu deține cheia de descifrare potrivită.

Principiile de criptare din algoritmii cu cheie secretă au evoluat odată cu apariția calculatoarelor; ele continuă însă să se bazeze pe metodele tradiționale, cum ar fi transpoziția si substituția. Algoritmii cu cheie secretă sunt caracterizați de faptul că folosesc aceeași cheie atât în procesul de criptare, cât si în cel de decriptare, ca in figura de mai jos. Din acest motiv, acești algoritmi mai sunt cunoscuți sub numele de algoritmi simetrici; pentru aplicarea lor este necesar ca înaintea codificării / decodificării, atât emițătorul cât si receptorul să posede deja cheia respectivă. În mod evident, cheia care caracterizează acești algoritmi trebuie să fie secretă.

Principalul dezavantaj al algoritmilor simetrici constă în faptul că impun un schimb de chei private înainte de a se începe transmisia de date. Altfel spus, pentru a putea fi utilizați, este necesar un canal cu transmisie protejată pentru a putea fi transmise cheile de criptare / decriptare.

Figura 1.1

Schema de aplicare a unui algoritm simetric

Sursa: Colin Boyd, Anish Mathuria, „Protocols for Authentication and Key Establishment”, Springer 2003.

Cifrurile cu cheie simetrică folosesc aceeași cheie pentru criptare si decriptare (sau cheia pentru decriptare este relativ ușor de calculat din cheia pentru criptare). Mai este numita si criptografie cu cheie privată.

Cifrurile cu cheie simetrică pot fi clasificate în cifruri bloc și cifruri secvențiale. Cifrurile secvențiale criptează informația bit cu bit, spre deosebire de cifrurile bloc, care criptează succesiv din mesaj blocuri de biți de o anumita lungime. Între cele două categorii există o dualitate, în sensul că pot fi făcute să opereze într-o manieră asemănătoare categoriei opuse. Ca exemple de cifruri bloc se cunosc: DES, 3DES, IDEA, AES, iar de cifruri secvențiale: RC4, A5/1, A5/2.

Există de asemenea unele primitive criptografice care pot fi desemnate ca fiind criptografie simetrică.

Un exemplu îl constituie funcțiile hash criptografice, care produc un „rezumat” (hash) al mesajului. În timp ce sunt foarte ușor de calculat, ele sunt foarte greu de inversat (one-way). Astfel, cineva trimite un mesaj și îi calculează hash-ul, apoi trimite mesajul împreuna cu hash-ul către receptor. Receptorul primește mesajul și calculează la rândul lui hash-ul. Dacă cele doua valori diferă, înseamnă ca mesajul a fost modificat. Este practic imposibil ca un intrus care interceptează mesajul să-l modifice astfel încât aplicarea funcției de hash să dea aceeași valoare cu valoarea inițiala. Exemple binecunoscute de astfel de funcții de hash sunt MD5 și SHA-1.

Criptografia cu cheie asimetrică

Ulterior, vor apărea și algoritmi cu cheie publică, caracterizați prin faptul că criptarea si decriptarea folosesc chei diferite ca în Figura 1.2. Această caracteristică a dat algoritmilor cu cheie publică și numele de algoritmi asimetrici. În acest caz, una dintre chei poate fi publică (general cunoscută – poate fi distribuită oricui) iar cealaltă va trebui să fie privată / secretă (cunoscută doar de cel care o folosește). Fiecare dintre aceste chei poate cripta mesajul, dar un mesaj criptat cu o anumită cheie nu poate fi decriptat decât cu cheia sa pereche.

Astfel, în cazul utilizării unui algoritm asimetric în comunicarea dintre un emițător si un receptor, fiecare dintre aceștia va deține câte o pereche de chei – publică si privată. Emițătorul poate cripta mesajul cu cheia publică a receptorului, astfel încât doar acesta să poată decripta mesajul cu cheia sa privată. În cazul unui răspuns, receptorul va utiliza cheia publică a emițătorului astfel încât decriptarea să se poată face exclusiv de către emițător (cu cheia sa pereche, privată).

Cheile algoritmilor asimetrici sunt obținute pe baza unei formule matematice din algebra numerelor mari, pentru numere prime între ele, iar din valoarea unei chei nu poate fi dedusă valoarea cheii asociate. Remarcăm faptul că aplicarea în informatică a calculelor modulo numere prime s-a dovedit extrem de benefică pentru mulți algoritmi moderni.

Figura 1.2

Schema de aplicare a unui algoritm asimetric

Criptarea cu cheie simetrică are un deficit care provoacă probleme serioase. De exemplu doi oameni care doresc să schimbe între ei mesaje confidențiale trebuie să partajeze o cheie secretă. Cheia trebuie transmisă într-un mod sigur, și nu prin mijloacele prin care ar comunica în mod normal. Acest lucru de obicei nu este convenabil, și criptografia asimetrica sau cu cheie publica asigură o alternativă. În criptografia cu cheie publică se folosesc doua chei, o cheie publică si o cheie privată. Cheia publică este folosită pentru criptare, iar cea privată pentru decriptare.

Trebuie să fie foarte dificil să se deducă cheia privată din cheia publică. Aceasta înseamnă că o persoană poate trimite fără nici o problema cheia publică printr-un canal de comunicații nesigur, și totuși să fie sigură că doar ea va putea decripta mesajele criptate cu ajutorul ei.

Algoritmii cu cheie publică se bazează de obicei pe probleme matematice dificil de rezolvat. RSA, de exemplu, se bazează pe dificultatea factorizării unui număr foarte mare. Mai este folosita si criptografia bazată pe curbe eliptice, care poate fi mai eficientă.

Din rațiuni de eficientă, în practică se folosesc sisteme de criptare hibride. Cu ajutorul unui cifru cu cheie publică se transmite o cheie între cei doi parteneri de comunicație, iar restul comunicației va fi criptat folosind un algoritm cu cheie simetrică, care este de obicei mult mai rapid.

Criptografia asimetrica oferă mecanisme pentru semnăturile digitale, care sunt un mod de a stabili cu un grad mare de încredere ( presupunând ca nu s-a compromis în vre-un fel cheia privata relevantă ) ca mesajul receptionat a fost trimis de utilizatorul care a pretins acest lucru. Aceste semnături sunt văzute adesea, conform legii sau prin deducție, ca fiind echivalentul digital al semnăturilor fizice de pe documentele de hârtie. În sens tehnic, ele nu sunt, deoarece nu există nici contact fizic, nici conexiune fizică între cel care semnează și documentul semnat. Dacă se folosesc în mod adecvat sisteme cu o concepție și implementare de înaltă calitate, se pot obține grade foarte înalte de încredere, depășind probabil semnăturile fizice. Exemple de protocoale de semnături digitale sunt DSA si ElGamal. Semnăturile digitale sunt de baza pentru operarea PKI (Public Key Infrastructure) si a multor scheme de securitate în retea ( Kerberos, cele mai multe VPN-uri, etc). Ca și la criptare, se pot folosi în practica algoritmi hibrizi, se poate semna un hash criptografic al documentului, în locul documentului întreg.

1.4. Comparație între criptarea simetrică și cea cu cheie publică

Avantaje ale sistemelor de criptare cu cheie simetrică

Pot transmite volume mari de date. Există implementări hard care pentru unele sisteme de criptare pot asigura rate de criptare de sute de mega-octeți pe secundă, sunt și implementări soft cu rate de mega-octeți pe secundă, deci are avantajul vitezei.

Cheile sunt relativ scurte.

Pot fi folosite ca bază de construcție a diverselor mecanisme de criptare, cum ar fi generatori de numere pseudo-aleatoare, generatori de funcții de dispersie, scheme de semnătură.

Prin compunere pot conduce la sisteme de criptare puternice.

Au o istorie bogată în evenimente și experiență.

Dezavantaje ale sistemelor de criptare cu cheie simetrică

Cheia trebuie să rămână permanent secretă în cel puțin două locuri distincte.

Cu cât lungimea unui mesaj criptat este mai mare, cu atât el este mai ușor de spart.

În rețele mari, o gestionare a cheilor devine extrem de dificilă.

Necesită un canal sigur de comunicare, cel puțin pentru transmiterea cheii. Acest lucru devine dificil mai ales pentru sistemele care necesită schimbări frecvente ale cehilor de criptare sau de decriptare.

Avantaje ale sistemelor de criptare cu cheie publică:

Sistemul este ideal pentru transmiterea informației prin canale nesigure.

Sistemele cu cheie publică asigură identitatea. Dacă o persoana X criptează un mesaj cu o cheie privată și transmițându-l unei persoane Y, aceasta îl poate decripta cu o cheie publică putem spune că Y are certitudinea că mesajul vine de la X.

Sistemele cu cheie publică sunt simplu de definit și elegante matematic.

Doar cheia de decriptare trebuie ținută secretă, la un singur punct (destinatar).

În funcție de modul de utilizare, o pereche de chei (publică,privată) poate fi păstrată o perioadă mai lungă de timp.

Conduc la aplicații de mare întindere ca semnături electronice, algoritmi de autentificare, componente de comerț electronic etc.

Dezavantaje ale sistemelor de criptare cu cheie publică

Sunt semnificativ mai lente decât sistemele simetrice.

Sunt necesare chei de lungimi mult mai mari.

Nu se poate garanta securitatea absolută a nici unei scheme de criptare cu cheie publică.

Implementarea trebuie realizată cu foarte mare grijă. Sisteme cu grad ridicat teoretic de securitate pot fi sparte ușor printr-o implementare neglijentă.

După cum se observă, cele două clase de sisteme de criptare dispun de o serie de avantaje complementare. Acest lucru face ca ele să fie folosite combinat.

CAPITOLUL II. ALGORITMI CU CHEI PUBLICE

2.1. Infrastructura cheilor publice

Electronic, confidențialitatea unui mesaj se asigură prin criptarea acestuia cu o cheie secretă și un algoritm asociat. Versiunea criptată a mesajului poate fi citită de destinatar numai dacă acesta posedă cheia secretă și algoritmul de criptare. Problema esențială a majorității aplicațiilor de criptografie este păstrarea secretului acestor chei. Criptografia bazată pe chei publice rezolvă această problemă înlocuind cheia secretă cu o pereche de chei – una privată iar cealaltă publică.

Infrastructura cheilor publice este o combinație de produse hardware și software, politici și proceduri care asigură securitatea de bază necesară astfel încât doi utilizatori, care nu se cunosc sau se află în puncte diferite de pe glob, să poată comunica în siguranță. La baza ei se află certificatele digitale, un fel de pașapoarte electronice ce mapează semnătura digitală a utilizatorului la cheia publică a acestuia. Aceste obiecte informaționale sunt cărămizile care stau la baza unei implementări cu chei publice și reprezintă mijlocul de identificare digitală a fiecărui subiect participant într-o relație derulată prin mijloace electronice.

O implementare de acest gen conferă o capabilitate, un atribut tehnologic și organizațional, nefiind un produs sau o aplicație în sine. Rolul său este acela de a crește valoarea sistemelor informatice existente, precum și de a crea posibilitatea implementării unor sisteme care să răspundă cerințelor în creștere ale societății informaționale.

Cheia utilizată trebuie să fie secretă ambelor părți, problema reprezentând-o managementul cheilor și menținerea lor secretă. Criptografia are la bază codificarea mesajelor, un bloc fiind substituit prin altul, respectând anumite reguli. Codificarea se poate realiza în mai multe moduri acestea având următoarele proprietăți comune:

atât intrările cât și ieșirile sunt reprezentate ca stream-uri de octeți;

criptarea unei date se realizează cu ajutorul unei chei;

decriptarea datei se realizează tot cu o cheie.

Modul de funcționare

Criptografia bazată pe chei publice trebuie însoțită de un set de politici de definire a regulilor sub care sistemele de criptografie pot opera și de un set de proceduri care specifică modalitățile de generare, distribuție și utilizare a cheilor. Pe scurt, este nevoie de o infrastructură, denumită „infrastructura cheilor publice” , care stabilește cadrul funcțional, bazat pe standarde, pentru o mare varietate de componente, aplicații, politici și practici al căror scop este atingerea celor patru funcționalități principale: confidențialitatea, integritatea, autentificarea, non-repudierea.

Pentru a înțelege modul de funcționare este nevoie de cunoașterea unui alt algoritm și anume funcțiile hash. Acestea, spre deosebire de algoritmii de criptare și decriptare realizează doar funcția de criptare iar mesajul original nu va fi recuperat niciodată. În principiu, un mesaj are întotdeauna aceeași valoare după aplicarea funcției și este imposibil ca două mesaje oarecare să genereze aceeași valoare.

Pentru a putea construi cheia ce se utilizează în timpul transmisiei se apelează la o altă parte de încredere denumită autoritate certificatoare. Ea generează un certificat general ce generează o cheie publică. Cheia nu trebuie să conțină ambiguități, înglobând datele personale care apoi sunt împachetate și semnate.

Un certificat digital este un document ce conține patru componente mari:

cheie public;

informația ce leagă cheia publică de deținătorul ei;

informația de validitate a certificatului;

semnatura digitală.

Din cele prezentate putem să observăm că: integritatea, confidențialitatea și nerepudierea sunt asigurate prin criptografia cheilor publice. Pentru aceasta trebuie însă să se știe cine generează certificatul, unde este stocată cheia și unde se găsesc certificatele. Un certificat digital bazat pe infrastructura cheilor publice asigură rezolvarea tuturor problemelor.

Componentele unei infrastructuri cu chei publice

Aceste componente sunt următoarele:

Autoritatea Certificatoare (CA): responsabilă cu generarea și revocarea certificatelor

Autoritatea Registratoare (RA): responsabilă cu verificarea construcției generate de cheile publice și identitatea deținătorilor.

Deținătorii de Certificate: oameni, mașini sau agenți software care dețin certificate și le pot utiliza la semnarea documentelor.

Clienții: ei validează semnătura digitală și certificarea de la o autoritate certificatoare.

Depozitele: stochează și fac accesibile certificatele și listele de revocare a certificatelor.

Politicile de securitate: definesc procesele și principiile de utilizare a criptografiei.

Dintre funcțiile realizate cu ajutorul infrastructurii cu cheie publică se poate menționa:

Înregistrarea: este un proces în care cel ce dorește să obțină un certificat de la CA își prezintă atributele sale. Acestea sunt verificate iar apoi se eliberează certificatul.

Certificarea: este procesul în care CA eliberează certificatul ce conține cheia publică subiectului apoi îl depune într-un depozit public.

Generarea Cheilor: în multe cazuri subiectul generează o pereche de chei în mediul său, înainte de a transmite cheia publică la CA pentru certificare. Dacă CA răspunde pentru generarea cheilor, acestea sunt oferite subiectului ca un fișier criptat.

Recuperarea Cheilor: în unele implementări ale infrastructurii cu chei publice necesită ca toate cheile schimbate și/sau criptate să fie depuse într-un depozit securizat. Ele sunt recuperabile dacă subiectul pierde cheia, acest lucru revenind lui CA sau sistemului de recuperare.

Actualizarea Cheilor: toate cheile perechi și certificatele lor asociate trebuie actualizate la un interval regulat. În acest sens există două situații care necesită acest lucru:

Data care este specificată în certificat ca dată de expirare este depășită și se actualizează.

Cheia privată a uneia din entități din PKI este compromisă. În acest caz PKI trebuie să anunțe că vechiul certificat nu mai este valid și urmează să-l înlocuiască. Una din căi este de pre-generare și stocare securizată a perechilor de chei pentru astfel de situații, acțiune ce duce la informarea fiecărui utilizator de acest lucru. Altă cale este metoda "out-of-band" unde cu ajutorul telefonului, faxului, scrisorii se transmite acea cheie.

Certificarea încrucișată: permite utilizatorilor dintr-un domeniu administrativ să utilizeze certificate generate de un CA operațional în alt domeniu. Procesul implică un CA (CA_1) ce oferă o certificare pentru alt CA (CA_2). Acest certificat conține cheia publică CA asociată cu cea privată pe care CA_1 o utilizează, lucru ce permite subiecților certificați prin CA_2 să accepte certificatele generate de CA_1 sau orice CA subordonat.

Revocarea: apare în momentul expirării perioadei de validitate care poate apărea când: subiectul își schimbă numele, angajatul părăsește compania, cheia privată este compromisă. În cadrul standardului X.509, pentru a revoca un certificat se utilizează lista revocărilor certificatelor. Această listă identifică certificate și sunt semnate de CA.

Avantajele infrastructurii cu cheie publică

În continuare sunt prezentate câteva din avantajele imediate pe care le aduce o implementare a unei infrastructuri cu cheie publică la nivel organizațional:

Securizarea mesageriei electronice. Cea mai mare parte a interacțiunilor derulate prin Internet se realizează prin intermediul mesageriei electronice. Această activitate presupune însă acceptarea unui grad ridicat de risc, prin expunerea unor informații confidențiale și prin posibilitatea substituirii autorului unui mesaj sau chiar alterarea voită a conținutului mesajului.

Sistem de administrare a documentelor și semnătură digitală. O parte importantă a aplicațiilor software se referă la procesarea și arhivarea documentelor în format electronic. Deși aceste sisteme contribuie la diminuarea dificultăților în prelucrarea și arhivarea unui volum mare de documente, ele nu rezolvă complet trecerea de la documente în format tradițional la documente electronice. Ceea ce lipsește este posibilitatea de a semna aceste documente electronice și de a asigura în acest fel non-repudierea acestora.

Securizarea aplicațiilor Intranet și Extranet. Din ce în ce mai multe companii și organizații tind să-și transfere procesele de interacțiune către aplicații care rulează în mediul Internet. Indiferent dacă acestea se referă la relația cu proprii angajați și procesele interne ale organizației (aplicații Intranet), sau sprijină interacțiunea cu partenerii și clienții (aplicații Extranet), aceste aplicații își demonstrează din plin eficiența prin reducerea masivă a costurilor și îmbunătățirea eficienței. Pe măsură însă ce aceste informații sunt transferate către sistemele și aplicațiile Intranet/Extranet, riscul de securitate informațională crește semnificativ, în primul rând datorită faptului că Internetul reprezintă prin natura sa un mediu public.

Criptarea datelor și a documentelor. Securitatea datelor nu se referă numai la momentul în care acestea sunt utilizate într-un proces informațional, ci și la stocarea lor. Păstrarea confidențialității și integrității acestora îmbracă numeroase aspecte, care se referă atât la autentificarea accesului cât și la criptarea lor astfel încât să nu poată fi utilizate în cazul unui acces neautorizat.

Autentificare la nivelul sistemului de operare și al aplicațiilor. Autentificarea prin nume și parolă este soluția cea mai vulnerabilă și în plus, obligă utilizatorul la memorarea unei astfel de combinații pentru fiecare aplicație folosită. Folosirea certificatului digital stocat pe „smartcard” contribuie nu numai la creșterea gradului de siguranță dar și la o utilizare mai facilă, prin folosirea unui mijloc unic de autentificare pentru toate aplicațiile folosite.

2.2. Criptării cu cheie publică

Prin definiție, un criptosistem cu cheie publică are proprietatea că o persoană care știe doar să cifreze nu poate folosi numai cheia de cifrare pentru a găsi cheia de decifrare în timp util. Denumirea de „cheie publică" provine din faptul că informația necesară trimiterii de mesaje secrete (cheia de cifrare) poate deveni informație cunoscută de oricine fără ca să se permită citirea mesajelor secrete de către persoane neautorizate.

De remarcat este faptul că, folosind un sistem cu cheie publică, este posibilă realizarea unei comunicații secrete între două părți fără a avea un contact inițial, fără a stabili la început dacă au încredere unul în altul, fără să schimbe informații priorii.

În sistemele de criptare clasice, Alice și Bob își aleg o cheie secretă K care definește regulile de criptare eK și decriptare dK. În aproape toate cazurile, eK și dK coincideau sau se puteau deduce imediat una din alta. Astfel de sisteme sunt cele cu cheie privată (sau sisteme simetrice) deoarece publicarea lui eK face sistemul extrem de vulnerabil.

Un punct slab al sistemelor cu cheie privată este acela că necesită o comunicare prealabilă a cheii între Alice și Bob printr-un canal sigur, înainte de transmiterea mesajului criptat. Practic, în condițiile cererii tot mai mari de securizare a comunicațiilor, acest lucru este din ce în ce mai dificil de realizat.

Obiectivul sistemelor de criptare cu cheie publică este acela de a face imposibil de obținut cheia dK plecând de la eK. Astfel, regula de criptare eK poate fi publicată într-un „registru public” (de unde și numele sistemelor). Avantajul constă în faptul că Alice (sau oricare altă persoană) poate trimite lui Bob un mesaj criptat cu eK fără a intra în prealabil în contact. Bob este singura persoană capabilă să decripteze textul, utilizând cheia sa secretă dK.

Ideea de sistem de criptare cu cheie publică apare în 1976 și este prezentată de Difne și Hellman . De atunci au apărut diverse astfel de sisteme, a căror securitate este bazată pe probleme calculatorii. Cele mai cunoscute în acest moment sunt:

Sistemul RSA: se bazează pe dificultatea descompunerii în factori primi a numerelor mari (de sute de cifre). Este sistemul cel mai larg utilizat în acest moment.

Sistemul El Gamal: se bazează pe dificultatea calculului logaritmului discret într-un corp finit.

Sistemul Merkle-Hellman: primul sistem definit cu cheie publică, bazat pe problema {0,1} a rucsacului, problemă NP-completă.

Sistemul McEliece: este bazat pe teoria algebrică a codurilor, decodificarea unui cod liniar fiind de asemenea problemă NP-completă.

Curbe eliptice: sunt sisteme de criptare care își desfășoară calculele pe mulțimea punctelor unei curbe eliptice (în locul unui inel finit ).

Se știe că toate problemele din clasa P care se pot rezolva în timp polinomial, sunt de asemenea în clasa NP, adică există metode pentru a verifica corectitudinea unei ipotetice soluții în timp polinomial. Pe de alta parte nu se știe dacă există probleme în NP care nu sunt în P , adică dacă partea hașurată din figura de mai jos este vidă sau nu.

Figura 2.2.1

2.3. Funcții neinversabile

O observație importantă este aceea că un sistem cu cheie publică nu este sigur necondiționat, adică oricine, putând să efectueze criptări, nu este exclus să găsească anumite puncte slabe care să îi permită să și decripteze mesajele. Ideea de bază folosită este aceea de funcție neinversabilă. În continuare este clarificat puțin acest aspect.

Exemplul 2.3.1:

Se poate imagina ușor străzile cu sens unic dintr-un oraș. Astfel, este ușor ca mergând pe astfel de străzi să se ajungă de la punctul A la punctul B, dar este imposibil de ajuns de la B la A. În acest mod, criptarea este privită ca direcția A —> B. Deși este foarte ușor de parcurs drumul în această direcție, nu este posibilă întoarce înapoi spre A (adică să decriptezi mesajul).

Exemplul 2.3.2:

Să considerăm cartea de telefon a unui oraș mare, cu ajutorul căreia este foarte ușor de găsit numărul de telefon al unei anumite persoane. În schimb, este extrem de greu, practic imposibil, să se afle persoana care are un anumit număr de telefon. Este ca și situația parcurgerii secvențiale a cel puțin unui volum gros, ceea ce conduce la o creștere exagerată a timpului.

Aceasta dă o sugestie de construcție a unui sistem de criptare cu cheie publică. Criptarea se face independent de context, literă cu literă. Pentru fiecare literă a textului clar se alege un nume care începe cu acest caracter și numărul de telefon al persoanei respective va constitui criptarea. Sistemul este homofonic, adică două apariții diferite ale aceleiași litere vor fi codificate foarte probabil cu numere diferite.

De exemplu, textul clar SOLIST se poate cripta astfel:

S Simion Pavel 6394502

Olaru Ștefan 7781594

L Lambru Stelian 6300037

I Ilie Romeo 3134971

S Solovean Raluca 6281142

T Tecuceanu Paul 3359962

Deci, textul criptat va fi: 639450 277815 946300 037313 497162 811423 359962.

Este de remarcat că metoda este nedeterministă, adică din același text clar se pot obține enorm de multe texte criptate. Pe de altă parte, orice text criptat conduce la un text clar unic.

Bob va avea la dispoziție pentru decriptare o carte de telefon scrisă în ordinea crescătoare a numerelor. Aceasta îi va permite să decripteze mesajele cu un algoritm de complexitate O(log n).

Deci, o funcție neinversabilă f trebuie să verifice două condiții:

Fiind dat x, f (x) este ușor de calculat;

Calculul lui x din f (x) este imposibil.

Este de remarcat că, din punct de vedere strict matematic, nu se cunosc astfel de funcții. A demonstra că există funcții neinversabile este echivalent cu a demonstra relația P ≠ NP, conjunctură care stă la baza întregii teorii criptografice. De aceea, termenii folosiți sunt relativi la complexitatea calculului. Astfel, o problemă este:

ușoară dacă se poate rezolva cu un algoritm cel mult liniar;

grea dacă se poate rezolva cu un algoritm polinomial neliniar;

imposibilă dacă este o problemă NP-completă.

Exemplul 2.3.3:

Se consideră „problema rucsacului”. Ea constă dintr-un vector de dimensiune n, A = (a1, a2, … an) cu elemente numere întregi pozitive distincte, și un număr întreg pozitiv k. Trebuiesc aflați acei ai din A ,dacă există, a căror sumă este k. Numele intuitiv dat problemei este evident.

De exemplu, fie

A= (43, 129, 215, 473, 903, 302, 561, 1165, 696, 1523) și k = 3231.

Se determină

3231 = 129 + 473 + 903 + 561 + 1165,

care este o astfel de soluție.

În principiu o soluție se poate găsi parcurgând sistematic toate submulțimile lui A și verificând dacă suma elementelor lor este k. În cazul de sus, aceasta înseamnă 210 − 1 = 1023 submulțimi, fără mulțimea vidă, dimensiune acceptabilă ca timp de lucru.

Ce se întâmplă însă dacă A are câteva sute de componente? În acest caz se cunoaște faptul că problema rucsacului este NP-completă.

Cu ajutorul lui A se poate defini o funcție f astfel:

Fie x[0, 2n − 1], x poate fi reprezentat în binar ca un cuvânt de lungime n, adăugând eventual zero-uri în față, și f(x) va fi numărul obținut din A prin însumarea tuturor numerelor ai aflate pe pozițiile marcate cu 1 în reprezentarea binară a lui x.

Formal, f(x) = A ∙ BTx

unde Bx este reprezentarea binară a lui x, scrisă ca un vector coloană.

Se definește acum un sistem de criptare bazat pe problema rucsacului. Textul clar este codificat inițial în binar și segmentat apoi în blocuri de câte n biți, ultimul bloc fiind eventual completat la sfârșit cu zerouri. Fiecare bloc rezultat este apoi criptat calculând valoarea corespunzătoare a funcției f.

Pentru alfabetul latin sunt suficienți 5 biți pentru codificarea binară a literelor și a spațiului. Mai exact, dacă asociem literelor A…Z reprezentările binare ale numerelor 1…26, vom avea:

Tabel 2.3.1

Se consideră un text clar, FLOARE DE COLT de exemplu. Cum fiecare caracter se codifică în 5 biți, în fiecare bloc intră două caractere:

FL OA RE _D E_ CO LT.

Codificând, se obțin șapte blocuri de câte 10 biți: 0011001100 0111100001 1001000101 0000000100 0000000101 0001101111 0110010100

care conduc la textul criptat: (1814,3243,3204,1165,1118,5321,1811).

Se consideră sistemul de criptare definit în Exemplul 3.3. Dacă este privit ca un sistem clasic, cu cheie privată atunci criptanalistul trebuie să afle vectorul de bază A și apoi să rezolve problema rucsacului.

Dacă el folosește metoda textelor clare alese, îl va afla ușor pe A. Este suficient să trimită n texte clare cu câte un singur 1 iar restul 0. Problema apare în momentul rezolvării problemei rucsacului. Aici atât Bob cât și Oscar sunt puși în fața aceleiași probleme NP-complete. Ori, practic, doar Oscar trebuie să rezolve o problemă dificilă, nu și Bob.

O altă problemă ridicată de acest sistem de criptare este aceea că este obligatoriu ca un text criptat să determine în mod unic un text clar. Aceasta înseamnă că nu trebuie să existe două submulțimi ale lui A care să aibă aceeași sumă. Astfel, dacă se ia A = (17, 103, 50, 81, 33), textul criptat (131, 33,100, 234, 33) poate fi decriptat în două moduri: SAUNA și FAUNA.

2.4. Trapa secretă

Pentru ca Bob să nu fie pus în aceiași situație ca și Oscar, el trebuie să dispună de un procedeu care să îi permită să transforme problema NP-completă publică, într-o problemă ușoară. Acest procedeu este numit trapă secretă. În primul exemplu, trapa secretă era cartea de telefon ordonată după numerele de telefon, și nu după abonați. Se va determina trapa secretă în sistemul de criptare din Exemplul 3.3.

Exemplul 2.4.1:

Sunt clase de probleme ale rucsacului ușor de rezolvat, iar una din ele o formează vectorii cu creștere mare.

Se spune că vectorul rucsac A = (a1, a2, … an) este cu creștere mare dacă

j ≥ 2, aj ≥

În acest caz, pentru a rezolva problema rucsacului este suficient să parcurgem vectorul A de la dreapta spre stânga. Cunoscând valoarea k, cercetăm întâi valoarea de adevăr a relației k ≥ an. Dacă răspunsul este FALSE, an nu poate aparține sumei pe care o căutăm. Dacă însă se obține TRUE, atunci an trebuie să fie în sumă, deoarece toate elementele ai rămase nu pot depăși în sumă pe k. Se definește

și se repetă procedeul pentru k și ai. Algoritmul se va opri la valoarea ai. Se presupune că există vectorul rucsac cu creștere mare

A = (l, 3, 5, 11, 21, 44, 87, 175, 349, 701)

și vrem să decodificăm mesajul 278. Se va parcurge 10 pași, reprezentați în tabelul:

Tabel 2.4.1:

Deci se obține secvența binară 00110 01100 care, conform codificării din Exemplul 2.4.1. corespunde perechii de litere FL.

Dacă se folosește însă public o astfel de informație, orice utilizator, inclusiv Oscar poate decripta mesajele folosind un algoritm liniar.

Exemplul 2.4.2:

Pentru sistemul bazat pe problema rucsacului, Bob va proceda astfel: va alege un număr m, unde m > , numit modul și un număr t, (m, t) = 1 numit multiplicator. Există atunci un număr s astfel ca ms = l (mod m).

Plecând de la vectorul cu creștere mare A = (a1, a2, … an) Bob generează vectorul B = ( b1, b2, … bn ) unde bi = tai (mod m).

Vectorul B este declarat public pentru criptare, iar m, t și s vor forma trapa secretă a lui Bob.

Astfel, dacă se ia m = 1590 și t = 43, vectorul cu creștere mare

A = (l, 3, 5, 11, 21, 44, 87, 175, 349, 701)

devine

B = (43, 129, 215, 473, 903, 302, 561, 1165, 697,1523),

adică cel prezentat în Exemplul 3.3. În plus, s = t−1 = 373.

Cum se va proceda? Cel care dorește să trimită lui Bob un mesaj criptat va folosi vectorul rucsac B și va cripta mesajul x în y = B ∙ BTx, conform Exemplului 3.3.

La recepție, Bob va calcula întâi z = s ∙ y(mod m), după care va decripta mesajul z folosind vectorul cu creștere mare A. Se poate arăta ușor că soluția este chiar x.

Astfel, de exemplu Alice poate cripta mesajul FL în 2414, conform Exemplului 3.3. La primirea acestui număr, Bob va determina întâi

s ∙ 2414 = 37 ∙ 2414(mod 1590) = 278.

În Exemplul 3.4 s-a văzut că decriptarea mesajului 278 cu vectorul A conduce la textul clar FL.

Se pot trasa acum câteva principii generale de construire a unui sistem de criptare cu cheie publică:

Se începe cu o problemă dificilă P. Rezolvarea lui P este imposibilă în conformitate cu teoria complexității deoarece nu se cunoaște nici un algoritm de complexitate polinomială care să rezolve P.

Se selectează o subproblemă P1 a lui P, rezolvabilă în timp polinomial, preferabil liniar.

Se aplică o transformare problemei P1 astfel încât să se obțină o problemă P2 care să nu semene cu P dar să fie foarte apropiată de problema P.

Se face publică problema P2 și se descrie algoritmul de criptare bazat pe aceasta. Informația referitoare la modul în care se obține P1 din P2 este o trapă secretă.

Se construiesc detaliile sistemului de criptare, astfel încât principiile de lucru să difere esențial pentru destinatar față de criptanalist. Astfel, în timp ce primul va folosi trapa secretă și va rezolva problema P1, al doilea va trebui să rezolve problema P2, imposibilă datorită asemănării ei cu problema P.

În funcție de aceste principii generale, apar în detalii de construcție multe alte probleme pe care constructorii sistemelor de criptare trebuie să le rezolve.

2.5. Securitatea sistemelor de criptare cu cheie publică

În majoritatea sistemelor de criptare, aparatul matematic folosit este bazat pe teoria numerelor, teoria funcțiilor recursive și teoria probabilităților. Pe o scară mult mai restrânsă apar funcțiile eliptice, teoria automatelor, calcul neconvențional (cuantic, molecular etc.).

Sistemele de criptare cu cheie publică au un avantaj major față de sistemele simetrice și anume aici nu mai este necesar efortul transmiterii cheii. Un contact prealabil între Alice și Bob pentru a pune la punct detaliile sistemului de criptare este inutil.

Un sistem de criptare cu cheie publică nu oferă însă o securitate absolută. Aceasta se datorează faptului că Oscar poate oricând să dispună de atacuri pasive sau active și anume:

Dacă cript-analistul dispune de un text criptat y, el poate căuta exhaustiv un text clar x astfel încât eK (x) = y. Singura apărare contra unui astfel de atac constă în gradul de complexitate al sistemului.

Un criptanalist activ poate efectua cu succes un atac de tipul meet in the middle. Se presupune că Alice și Bob doresc să stabilească un contact. Ei fac publice cheile de criptare eA respectiv eB .Dacă contactul este nepersonalizat, Oscar poate controla mesajele schimbate între cei doi, în felul următor:

Figura 2.5.1.

Oscar opacizează printr-un mijloc oarecare aceste chei, și trimite lui Alice cheia ca din partea lui Bob. Substituie, similar, pentru Bob cheia eA cu .

Fie m mesajul pe care Alice vrea să îl trimită lui Bob. Ea va cripta și va trimite.

Oscar interceptează mesajul, reamintind că toate canalele sunt nesigure și află .

Oscar recriptează și trimite y lui Bob.

Bineînțeles, Oscar poate modifica sau întârzia mesajul m dacă dorește. Din această cauză, aproape în toate sistemele de criptare cu cheie publică apare necesitatea autentificării mesajului sau a expeditorului, precum și aceea a confidențialității.

Metodele prin care un expeditor uman se poate autentifica sunt clasificate în:

„ceva ce utilizatorul este" (de exemplu amprente digitale, de retină, de voce, recunoașterea semnăturii, identificatori biometrici).

„ceva de utilizatorul are” (de exemplu card de identitate, date de securitate soft pe calculator sau telefon).

„ceva ce utilizatorul știe” (de exemplu o parola, un număr de identificare PIN).

Orice combinație între metodele anterioare (de exemplu un card bancar cu PIN asigură o dublă autentificare).

Deasemenea integritatea, care se referă la validitatea datelor poate fi compromisă în două moduli:

Prin alterare intenționată (de exemplu modificarea unui cont bancar, a unei adrese de e-mail, a unui document de identitate).

În mod accidental (transmisii perturbate de zgomote de canal, zgârierea hard-discului).

Se presupune că Alice și Bob sunt doi utilizatori cu posibile conflicte de interese. Când Alice trimite un mesaj lui Bob, ambele părți trebuie să se asigure că:

Mesajul nu este trimis de o terță persoană care pretinde a fi Alice.

Bob să nu poată obliga pe Alice să țină cont de mesaje care nu-i aparțin, iar Alice să poată recunoaște public propriile mesaje.

Într-o oarecare măsură, cele două condiții sunt contradictorii. Conform primei condiții, Bob trebuie să știe ceva despre modul de criptare al lui Alice, care îi va permite să autentifice mesajul, iar conform celei de-a doua condiții, el nu trebuie să știe prea mult. O modalitate frecvent utilizată pentru autentificarea mesajelor este folosirea codurilor de autentificare.

De exemplul MAC-ul (Message Authentication Code) definit în cadrul sistemului de criptare DES este o variantă prin care se poate asigura atât autenticitatea cât și integritatea mesajului. Dacă se solicită și autentificarea partenerilor, atunci se folosește de obicei semnătura electronică.

Exemplul 2.5.2.: Se presupune că Alice vrea să trimită lui Bob mesajul m. Dacă se folosește un sistem de criptare cu cheie publică în care funcțiile de criptare sau de decriptare sunt comutative, iar (eA , dA), ( eB , dB) sunt perechile (cheie publică,cheie privată) ale celor doi, ei pot urma următorul protocol:

Alice trimite lui Bob y1 = eA (m);

Bob trimite lui Alice y = eB (y1);

Alice trimite lui Bob dA (y) = eB (m);

Bob calculează dB (eB (m)) = m și află mesajul.

Se observă că sunt verificate cele două condiții de autentificare și, în plus protocolul rezistă unui atac de tip meet in the middle.

Dacă dorim să folosim un singur contact, Alice poate trimite mesajul

y = eB (dA (m)).

La recepție, Bob va folosi propria sa cheie pentru decriptare, împreună cu cheia publică a lui Alice. Metoda merge și pentru sisteme de criptare necomutative.

2.6. Teste probabilistice de primalitate

Există multe situații în care dorim să știm dacă un număr foarte mare este prim sau nu. De exemplu, în sistemul de criptare cu cheie publică RSA (prezentat în capitolul următor) avem nevoie de numere prime mari.

Un test de primalitate este un criteriu folosit pentru a arăta că un număr n nu este prim. Dacă n trece un test de primalitate, el poate fi prim. Dacă el trece mai multe teste de primalitate, el este foarte probabil prim, iar dacă nu trece un test este sigur compus. În acest ultim caz apare o problemă foarte complicată, aceea de a-i găsi descompunerea în factori primi. De obicei, procedeul de a determina factorii primi ai unui număr foarte mare n (odată ce se cunoaște că este compus) este mult mai îndelungat decât cel de a găsi un număr prim de mărimea lui n .

Acest capitol are ca scop prezentarea unor astfel de teste de primalitate. Majoritatea testelor eficiente de primalitate au forma generală asemănătoare cu următorul.

Conform micii teoreme a lui Fermat, dacă n este număr prim atunci, pentru orice b cu (b, n) = 1 avem bn-1 ≡ 1 (mod n). Sub o formă echivalentă, rezultă că dacă există un întreg b care nu este congruent cu bn mod n, atunci n este compus. De exemplu, există b = 2 astfel încât pentru n = 63 obținem 263 = 26023 = (26)10∙8 = (64)10∙8 ≡ 1(mod 63).

O observație importantă este aceea că reciproca micii teoreme a lui Fermat nu este adevărată. Pentru aceasta să observăm că pentru n = 341 = 11∙31 și b = 2 obținem 210 ≡ 1(mod11) de unde

2340 = (210)34 ≡ 1(mod11)

și

2340 = (25)68 = (32)68 ≡ 1(mod31).

Din cele două, obținem dar n nu este prim.

Definiție: Fie b număr natural. Dacă n este număr natural compus și bn ≡ b(mod n) atunci n se numește număr pseudoprim cu baza b.

Ca exemplu, am arătat deja că 341 este pseudoprim cu baza 2.

Observăm că, dacă (b, n) = 1 congruența bn ≡ b(mod n) este echivalentă cu

bn−1 ≡ 1(mod n) .

În continuare prezentăm o metodă rapidă de a calcula bn(mod m) unde b, n, m sunt numere naturale. Algoritmul presupune ridicări la pătrat și înmulțiri repetate și este deosebit de eficient și de aceea foarte des folosit în multe protocoale criptografice.

Pentru început se scrie n in baza 2. Fie n = (ak ak−1 … a1 a0 )2. Observăm că

bn = = ….

Ținând cont de acest lucru, calculăm întâi resturile modulo m ale lui b, b2, b4,…,ridicând succesiv la pătrat și reducând modulo m. După aceea, înmulțim resturile modulo m ale lui cu aj = 1 și reducem modulo m.

Algoritm 3.1:

INPUT: b, n, m.

OUTPUT: bn(mod m).

1. x ← 1. Dacă n = 0 returnează x.

2. A←b.

3. Dacă a0 = 1 atunci x ← b.

4. Pentru j = 1, …, k calculează:

4.1 A ← A2(mod m).

4.2 Dacă aj = 1 atunci x ← A ∙ x(mod m).

5. Returnează x .

Spre exemplu, în tabelul următor se evidențiază pe pași calculul lui 5596( mod 1234).

Tabel 2.6.1.

Teoremă: Există o infinitate de numere pseudoprime cu baza 2.

Demonstrație: Observăm mai întâi că d | n => (2d −1) | (2n −1). Vom arăta că dacă n este pseudoprim cu baza 2 atunci, m = 2n −1 este tot pseudoprim cu baza 2. Cum există cel puțin un pseudoprim cu baza 2, fie el n0 = 341, de exemplu, putem construi o infinitate de numere impare diferite nk+1 =−1, k > 0 pseudoprime cu baza 2. Consider n impar, pseudoprim cu baza 2 adică n este compus și 2n-1≡ 1(mod n). Fie d un divizor propriu al lui n. Atunci, (2d −1) | (2n −1) adică m este compus. Din 2n ≡ 2(mod n) rezultă 2n − 2 = kn pentru un k întreg. Atunci, 2m−1 = 2kn. Cum (2n −1) | (2kn −1) obținem m | (2m−1 −1) adică 2m−1 ≡ 1(mod m).

Un prim test de primalitate prezentat este datorat micii teoreme a lui Fermat și constă în a stabili dacă pentru un număr n există un întreg b cu (b, n) = 1 pentru care bn−1 nu este congruent cu l mod n. Astfel, se testează pentru diferite valori ale lui b dacă bn−1 ≡ 1(mod n). Dacă n nu trece testul pentru un b atunci, n este compus. Dacă însă, n trece testul pentru toate valorile considerate pentru b nu putem preciza dacă n este prim sau nu.

Exemplu 2.6.1.: Știm că 341 este pseudoprim cu baza 2. Din 73 = 343 ≡2(mod341), 210 = 1024 ≡ 1(mod341) rezultă 7340 = (73)113∙7 ≡ 2113 ∙7 ≡ (210)11∙8∙7 ≡ 56(mod 341). Deci există b = 7pentru care 341 nu trece testul adică 341 este compus.

Algoritm 3.2: Testul de primalitate Fermat.

INPUT: n > 2, impar, un parametru de securitate t > 1.

OUTPUT: un răspuns relativ la primalitatea lui n.

1. Pentru i de la l la t:

1.l Alege aleator un întreg a, 2 ≤ a ≤ n − 2.

1.2 Calculează folosind algoritmul 3.1.

1.3 Dacă r ≠ 1 atunci returnează compus.

2. Returnează prim.

Din păcate, există numere care sunt pseudoprime cu orice bază b unde (b, n) =1, deci numere compuse care trec testul Fermat indiferent ce astfel de baze am considera. Pentru astfel de numere, sunt importante valorile lui a, 1 ≤ a ≤ n − 1, cu (a, n) > 1. Dar, dacă factorii primi ai lui n sunt toți mari, probabilitatea ca testul Fermat să concluzioneze că n este prim este foarte ridicată, chiar dacă numărul de iterații t este mare.

Un exemplu de un astfel de număr este n = 561 =3∙11∙17. Considerăm un întreg b cu (b, 561) = 1. Atunci, (b, 3) = 1, (b, 11) = 1, (b, 17) = 1. Rezultă

b2 ≡ 1(mod 3),

b10 ≡ 1(mod 11),

b16 ≡ 1(mod 17).

Astfel,

b560 = (b2)280 ≡ 1(mod3),

b560 = (b10)56 ≡ 1(mod11),

b560 = (b16)35 ≡ 1(mod17),

de unde b560 ≡ 1(mod561).

Definiție: Un număr Carmichael este un număr compus n pentru care bn−1 ≡ 1(mod n), oricare ar fi b întreg relativ prim cu n.

Dacă se cunoaște descompunerea în factori primi a unui număr, se poate preciza dacă acesta este un număr Carmichael sau nu pe baza următoarei teoreme:

Teorema 2.6.2.: Un număr natural n este număr Carmichael dacă și numai dacă verifică următoarele condiții:

n este liber de pătrate, adică nu este divizibil cu pătratul nici unui număr prim, pentru orice divizor prim p al lui n, (p−1) | (n−1).

Cel mai des folosit test probabilistic de primalitate este testul Miller – Rabin sau testul numerelor tari pseudoprime. Pentru prezentarea acestuia avem nevoie de câteva rezultate pregătitoare.

Definiție: Fie n cu n −1 = 2s ∙ t unde s, t și t este impar. Spunem că n trece testul Miller pentru baza b dacă bt ≡ 1(mod n) sau există un j, 0 ≤ j ≤ s − 1 pentru care ≡ −1(mod n).

Se remarcă următorul fapt:

Teorema 2.6.3: Dacă n este prim și b este un număr natural care nu divide pe n, atunci, n trece testul Miller pentru baza b.

Dar, putem observa că nu numai numerele prime au această proprietate. De exemplu, pentru n = 2047 = 23∙89 și b = 2, (n −1 = 21∙1023 ) obținem că el trece testul Miller pentru baza 2 pentru că = 21023 = (211)93 = (2048)93 ≡ 1(mod 2047). Astfel, este necesară studierea acestor numere.

Definiție: Dacă n este compus și trece testul Miller pentru baza b, spunem că n este tare pseudoprim cu baza b.

Observație: Dacă n trece testul Miller pentru baza b atunci, n −1 = 2s ∙ t și bt ≡ 1(mod n) sau ≡ −1(mod n) pentru un j. Dar, bn−1 = ; bn−1 = . Din cele două scrieri obținem că, indiferent de congruența care se verifică, bn−1 ≡ 1(mod n) adică n este pseudoprim cu baza b. Obținem astfel că orice număr tare pseudoprim cu baza b este pseudoprim cu baza b.

Dar, există numere pseudoprime cu baza b care nu sunt tari pseudoprime cu acea bază. De exemplu, n = 341 este pseudoprim cu baza 2. n − 1 = 22∙85, s = 2, t = 85.

Din 210 = 1024 ≡ 1(mod 341) obținem

bt = 285 = (210)8 ∙ 25 ≡ 32(mod 341),

și

b2t = 2170 = (210)17 ≡ 1(mod 341).

Cum nu se verifică nici una din condițiile definiției de mai sus, 341 nu este tare pseudoprim cu baza 2.

Observație: Am remarcat că numerele care trec testul Miller pentru o bază b sunt cele prime sau cele tari pseudoprime cu baza b. Pentru verificarea primalitații unor numere relativ mici putem folosi testul Miller ținând cont de câteva rezultate cunoscute cum ar fi:

Cel mai mic număr impar tare pseudoprim cu baza 2 este 2047. Astfel, dacă n impar trece testul Miller pentru baza 2 și n < 2047, atunci el este prim. Analog vom proceda și în cazul afirmațiilor următoare.

Cel mai mic număr impar tare pseudoprim cu bazele 2 și 3 este 1373653.

Cel mai mic număr impar tare pseudoprim cu bazele 2, 3 și 5 este 25326001.

Cel mai mic număr impar tare pseudoprim cu bazele 2, 3, 5 și 7 este 3215031751.

Singurul număr impar mai mic decât care este tare pseudoprim cu bazele 2, 3, 5 și 7 este 3215031751.

Teorema 2.6.4. (Testul probabilistic al lui Rabin): Fie n număr natural. Considerăm k numere naturale diferite, și realizăm testul Miller pentru n și toate aceste k baze. Dacă n este compus, probabilitatea ca n să treacă toate testele este mai mică decât .

De exemplu, dacă n este compus, probabilitatea ca el să treacă testul Miller pentru 100 de baze diferite < n este mai mică decât 10−60. De aceea testul Miller-Rabin nu dovedește cu exactitate că numărul n este prim dar, datorită probabilității extrem de mici, furnizează un motiv puternic de a presupune că el este prim.

Algoritm 3.3: Test probabilistic de primalitate Miller-Rabin.

IMPUT: n >2, impar și un parametru de securitate r > 1.

OUTPUT: un răspuns relativ la primalitatea lui n.

1. Determină s și t astfel încât n −1 = 2s ∙ t cu t impar.

2. Pentru i de la l la r :

2.1 Alege un a, 2 ≤ a ≤ n − 2.

2.2 Calculează y = at(mod n) folosind algoritmul 3.1

2.3 Dacă y ≠ 1 și y ≠ n−1 atunci:

j ← 1

Cât timp j ≤ s −1 și y ≠ n−1 execută:

y ← y2(mod n)

Dacă y = 1 atunci returnează compus.

j ← j + 1

Dacă y ≠ n−1 returnează compus.

Returnează prim.

În încheierea acestui capitol să studiem o clasă specială de numere care are o deosebită importanță în furnizarea celor mai mari numere prime cunoscute până în prezent.

Definiție: Un număr de forma Ms = 2s −1 cu s natural, s >2 se numește număr Mersenne. Dacă Ms este prim, el se numește număr prim Mersenne

Dacă Ms este număr prim se arată că s trebuie să fie prim. Dar dacă s este prim nu rezultă că Ms este și el prim. De exemplu, pentru s = 11, M11 = 211 − 1 = 2047 = 23 ∙ 89 este compus.

Se poate da o caracterizare a divizorilor unui număr Mersenne dacă acesta nu e prim.

Teorema 3.5: Dacă s este număr prim impar, orice divizor prim al numărului Mersenne Ms dacă există, este de forma 2ks + 1, pentru un k natural.

Spre exemplu, fie M13 = 213 − 1 = 8191. Pentru a vedea dacă este prim sau nu vedem dacă există un divizor prim < = 90,504… de forma 26k + 1. Singurele numere prime de această formă < 90 sunt 53 și 79. Prin verificare directă obținem că ele nu divid M13 și astfel M13 este prim.

Dacă facem același lucru pentru M23 = 223 − 1 = 8388607 vom căuta divizori primi de forma 46k + 1 care sunt < 2896. Găsim pe 47 și cum M23 = 47 ∙ 178481 acesta este compus.

Teorema 3.6 (Testul Lucas-Lehmer): Fie s ≥ 3. Numărul Mersenne Ms = 2s − 1 este prim dacă și numai dacă sunt verificate condițiile:

1) s este prim,

2) șirul de numere întregi (uk)k≥0 definit prin u0 = 4, uk+1 ≡ uk2 − 2(mod Ms), k ≥ 0 verifică us−2 ≡ 0(mod Ms).

De exemplu: pentru M5 = 25 − 1 = 31 șirul este dat de u0 = 4, u1 ≡ 14(mod 31), u2 ≡ 142 −2 ≡ 8(mod 31) și u3 ≡ 182 −2 ≡ 0(mod 31). Deci, este prim.

Algoritm 2.3: Testul de primalitate Lucas-Lehmer pentru numere Mersenne.

INPUT: un număr Mersenne n = Ms = 2s − 1, cu s ≥ 3

OUTPUT: un răspuns referitor la primalitatea numărului n.

1. Se verifică prin metoda obișnuită dacă s are un divizor cuprins între 2 și []. Dacă are, returnează compus.

2. u ← 4

3. Pentru k de la l la s − 2 efectuează

3.1. u ← (u2 − 2)(mod n)

4. Dacă u = 0 returnează prim. Altfel, returnează compus.

Observație: Până în prezent se cunosc doar 39 de numere Mersenne prime. Pentru toate numerele prime s < 103000 s-au găsit 31 de numerele prime Mersenne Ms. Cel mai mare număr prim Mersenne este corespunzător lui s = 13466917 iar dimensiunea lui depășește 4 milioane de cifre.

In lucrarea de fata am ales sa implementez un software capabil sa realizeaza criptarea si decriptarea unei imagini si a unui fisier text. Datorita implementarii , algoritmul criptare cat si de decriptare poate fi schimbat foarte usor.

Pentru implementare , am ales doi algoritmi diferiti, cu proprietati diferite, si anume algoritmul AES si algoritmul Blowfish.

AES

AES(Advanced Encryption Standard) este un algoritm de criptare asimetric initial adoptat de guvernul SUA .AES este un algoritm standardizat pentru criptarea simetrica, pe blocuri, folosit astazi pe scara larga in aplicatii si adoptat ca standard de organizatia guvernamentala americana NIST. Standardul oficializeaza algoritmul dezvoltat de doi criptografi belgieni, Joan Daemen si Vincent Rijmen si trimis la NIST pentru selectie sub numele Rijndael.

AES a devenit succesorul oficial al standardului DES începând cu sfârșitul anului 2001.

AES folosește chei de 128, 192 si 256 de biți, fiind eficient la atacurile criptanalitice prelungite. Algoritmul Rijndael are performanțeremarcabile. Dacă sistemul DES ar putea fi

spart cu un calculator capabil să genereze 256 chei într-o secundă, atunci acelașicalculator ar trebui să calculeze 149 * 1013 ani pentru ca să poată sparge codul noului sistem.

Specificația AES standardizează dimensiunile de 128, 192 si 256 de biți pentru lungimea cheii, dar restricționează lungimea blocului la 128 de biți.

Standardul AES a fost adoptat deoarece suportul complet pentru criptografie este acum parte din J2SE (Java 2 Standard Edition). JCE are o arhitectură de tip furnizor care permite conectarea mai multor furnizori de securitate sub același cadru de dezvoltare.Suportul pentru AES în versiunea 6 a platformei Java Standard Edition este asigurat de furnizorul Sun, cunoscut ca SunJCE.

Blowfish

Blowfish a fost propus in 1993 , fiind foarte folosit in multe produse care necesita cifruri.A fost propus in 1993 de catre Bruce Schneier.Aceasta se datoreaza faptului ca Bruce Schneier nu a patentat algoritmul si a permis ca acesta sa devina open-source , si sa fie folosit de oricine doreste.

Blowfish a fost creat pentru a inlocui algoritmul DES si pentru ca se doreste inlocuirea problemelor aduse de alti algoritmi.Nu se cunoaste nicio metoda capabila sa sparga algoritmul , singura variant fiind metoda finite brute.Este un algoritm rapid in executie care ocupa in memorie un spatiu de 4 kb.

Acest lucru il face neutilizabil in sistemele embedded.Blowfish lucreaza pe blocuri de 64 biti si are o cheie cu lungimea intre 32 si 448 biti.

Lucrarea de fata prezinta 2 functii principale, una encrypt si una decrypt.Aceste functii primesc ca parametru adresa variabilelor care urmeaza sa fie criptate si adresa variabilelor unde se vor salva variabilele criptate.

CONCLUZII

Istoria criptografiei este deci lungă si pitorească. Evident, dezvoltarea tehnicilor de criptare a constituit o prioritate pentru organizațiile militare, care utilizau frecvent asemenea procedee. Înainte de apariția calculatoarelor, volumul mare de mesaje criptate sau transmise a fost gestionat de un număr mare de funcționari „codori”. Evident, tehnicile folosite erau limitate de capacitatea codorilor de realizare a transformărilor necesare și de însușirea de către aceștia a unor tehnici criptografice noi. Totuși, pericolul de capturare a codurilor de către „inamici” făcea necesară schimbarea periodică a metodei de criptare.

Necesitatea protecțiilor informațiilor a reprezentat un deziderat mereu actual al omenirii. Tehnici secrete de codificare a mesajelor au fost utilizate încă din antichitate și au prezentat o evoluție continuă de-a lungul timpului, afectând în multe cazuri chiar istoria.

Criptarea mesajelor și trimiterea lor sub aceasta forma este utilizată de foarte mult timp. Unul dintre primii care au folosit tehnici de criptare pentru trimiterea mesajelor a fost celebrul împărat Cezar si dacă ar trebui ales un singur exemplu al criptografiei „clasice”, acesta ar fi cifrul lui Cezar, nu atât datorită celebrității împăratului roman de care se leagă folosirea lui, ci pentru că principiul său de bază s-a menținut nealterat aproape două milenii. În comunicarea privată cu o persoană folosirea unui cod secret poate preveni citirea intenționată sau neintenționată a mesajelor de către cei care intră în posesia acestora, fie că trebuie să le transporte până la destinatar, fie că le interceptează în timp ce mesajul este transmis.

Încă din cele mai vechi timpuri tehnologia în ceea ce privește domeniul criptografic a cunoscut progrese majore, și tocmai de aceea se poate spune că în momentul de față se asistă la o informatizare pe scară largă a mai multor instituții, lucru datorat avantajelor aduse de sistemele informatice: colectarea, transmiterea, procesarea și regăsirea datelor se face mai rapid, mai ieftin, mai ușor, cu o economie mai mare de spațiu. Astfel se face o economie semnificativă de timp și de efort care pot fi investite pentru realizarea altor acte de mai bună calitate. Cu toate acestea există însă și un dezavantaj major, și anume securitatea datelor devine mai greu de asigurat. Se poate spune că unul din cele mai studiate domenii din zilele noastre este criptarea mesajelor. Complexitatea tehnicilor de criptare și de trimitere a mesajelor crește permanent pentru a obține o securitate cât mai ridicată a comunicațiilor.

Puține sunt persoanele care să nu fi încercat, măcar o dată, transmiterea cifrată a unor mesaje personale foarte importante. Și mai puține sunt, probabil, cele care nu s-au amuzat niciodată rezolvând jocuri rebus unde, pe baza unor frânturi de mesaj trebuie descoperită regula de reconstituire a mesajului. Explicația este atracția firească pe care o prezintă un astfel de exercițiu intelectual și satisfacția pe care ți-o dă reușita rezolvării. Criptografia sau știința codificării informației în vederea împiedicării acceselor neautorizate are o lungă istorie, confidențialitatea comunicării fiind o cerință a tuturor timpurilor.

Criptarea sau cifrarea definită și ca un mecanism puternic de asigurare a confidențialității asigura confidențialitatea datelor atunci când mecanismele de împiedicare a accesului la date au eșuat. Este un lucru înțelept să se folosească și criptarea, deoarece sistemele informatice sunt foarte complexe, atât din punct de vedere hard, cât și soft, așa că întotdeauna vor exista breșe în sistemele de restricționare a accesului. Dacă mecanismul de criptare a datelor este puternic și aplicat în mod corect, atacatorul va avea în față niște date pe care nu va putea să le folosească.

Criptografia este știința care folosește matematica pentru a codifica si decodifica informațiile. Cu ajutorul criptografiei se pot stoca ușor informațiile sau se pot transmite de-a lungul unor rețele nesigure, de exemplu Internetul, și nu pot fi citite decât de aceia care posedă cheia pentru decriptare. În timp ce criptografia este știința securizării informațiilor, criptanaliza este știința analizării și verificării securității comunicației. Criptanaliza clasică implică combinații interesante de judecăți analitice, aplicații ale metodelor matematice, căutarea șabloanelor, determinare si noroc. Criptologia le include pe ambele, criptografia și criptanaliza.

Criptografia poate fi puternică sau slabă. Puterea procesului de criptografie este măsurată în timp și în resurse informatice necesare pentru a cripta un text. Rezultatul unei criptografii avansate este un text criptat, foarte greu de descifrat fără a fi în posesia unui instrument de decriptare. Cât de dificil? Dată fiind toată puterea de calcul din momentul de față și tot timpul disponibil, luând în considerare un miliard de calculatoare care fac un miliard de operații pe secundă, este practic imposibil de descifrat rezultatul unei criptografii avansate înainte de sfârșitul Universului. Unii s-ar putea gândi deci, că criptografia avansată poate fi folosită foarte bine chiar împotriva unui criptanalist extrem de bine motivat. Cine spune asta? Nimeni n-a dovedit că este posibil ca folosind cea mai avansată tehnică de criptografie posibilă astăzi poate fi considerat la fel mâine, la puterea de calcul a zilei de mâine. Oricum, criptografia avansată este cea mai bună dintre cele disponibile astăzi. Vigilența si dorința de a păstra informațiile intacte vor proteja mai bine oricum decât tendința de a proteja prin impenetrabilitatea sistemelor informatice.

BIBLIOGRAFIE

„Algoritmi de criptare pentru securizarea datelor”, Editura Orizonturi Universitare Timișoara (iunie 2001) – Colecția Calculatoare – Informatică 12;

Ernest Scheiber Programare concurenta si paralel-distribuita in JAVA, Editura Albastra;

Marina Gorunescu, S. Belciug, Data Mining: Modelele predictive și de clasificare – Implementare in MATLAB și Java;

Menezes, P. van Oorschot, S. Vanstone, „Handbook of Applied Cryptography”, CRC Press, 1996;

Mike Mcgrath, Java In Easy Steps 5th Ed, Editura: Computer Step 2014;

Rogers Cadenhead, Java In 24 Hours Sams Teach Yourself, Editura: Pearson Education Limited 2014;

Stefan-Gheorghe Pentiuc, Java. Structuri de date si algoritmi, Editura Matrixrom;

Thomas Cormen, Charles Leiserson, Ronald Rivest, „Introducere în algoritmi”, Editura Libris Agora, Cluj-Napoca, 2000.

www.e-learn.ro

www.ibm.com

www.oracle.com

www.scientia.ro

www.securitatea-informatiilor.ro