Criptografia, Metoda Pentru Asigurarea Securitatii Tranzactiilor de Date

Capitolul I :

Sisteme criptografice

I.1 – Evoluția istorica a criptografiei

I.2 – Criptografia în antichitate

I.3 – Criptografia în evul mediu

I.4 – Criptografia în epoca modernã

I.5 – Dispozitive clasice de cifrare

I.6 – Sisteme criptografice

I.7 – Conceptul de semnătură digitală

I.8 – Criptografia in securitatea rețelelor calculatoarelor

Evoluția istorica a criptografiei

Criptografia este știința scrierilor secrete. Un cifru se definește ca transformarea unui mesaj clar sau text clar in mesaj-cifrat ori criptograma. Procesul de transformare a textului clar in text cifrat se numește cifrare sau criptare, iar transformarea inversa, a criptogramei in text clar, are denumirea de descifrare sau decriptare. Atât cifrarea cit si descifrarea sunt controlate de către una sau mai multe chei criptografice.

Criptanaliza studiază metodele de spargere cifrurilor, adică de determinare a textului clar sau a cheii de cifrare din criptograma. Cunoștințele actuale referitoare la începuturile criptografiei ne sunt furnizate de diferite lucrări științifice, religioase sau istorice privind diferite războaie ale unor civilizații de mult apuse.

Pe baza datelor cunoscute astăzi se apreciază ca domeniul criptografiei a apărut in mod independent in mai multe parți ale lumii, la mai multe popoare. In primul rând războaiele si diplomația au impulsionat continua perfecționare si înnoire a metodelor de secretizare si de descifrare a mesajelor.

Devenind tot mai complexa, activitatea in acest domeniu presupune o serioasa pregătire matematica, lingvistica, o gândire logica bine dezvoltata ai, de ce nu, intr-o lume a informaticii ca cea pe care o străbatem azi, o buna cunoaștere a calculatoarelor si a programării acestora.

Criptografia in antichitate

Primele informații referitoare la criptografie datează de acum circa patru mii de ani si provin din EgiptuI antic sub forma unor formule funerare care conțin, intr-o modalitate incipienta, elementele constitutive ale științei de azi. Grecii antici au cunoscut si au practicat in multe variante scrierea secreta, după cum atesta documentele istorice.

Încă din secolul al V-lea I. H. se cunoaște o prima forma a transpoziției, metoda folosita si astăzi. Pentru cifrare se folosea un instrument numit scitală – un baston in jurul căruia se înfășura spiră lângă spiră o panglică foarte îngusta de piele, papirus sau pergament pe care, paralel cu axa, se scriau literele mesajului. După scrierea textului panglica era derulata. mesajul devenind indescifrabil, întrucât literele erau dezasamblate. Mesajul se putea reconstitui numai de persoana care dispunea de un baston de lungime si grosime identice cu dimensiunile inițiale pe care sa fie înfășurată din nou panglica primita.

In alte lucrări antice, din secolul al IV-lea î. C, se prezintă alte variante de scriere secreta. Una din metodele descrise se bazează pe folosirea așa-numitului disc cu orificii care putea sa fie trimis cu ajutorul arcului dintr-o (intr-o) cetate asediata. Dispozitivul era de fapt un disc de lemn cu 24 de orificii pe margine si cu doua orificii in interiorul discului. Poziția celor doua orificii, mai precis raza determinate de acestea, desemna o litera de referința secreta. De la aceasta litera de referința intr-un sens si altul erau puse celelalte litere in ordine alfabetica.

In cartea sa, "Istoria generala", istoricul grec Polibiu, martor ocular si participant la al treilea război punic (149-146 I.H.) acorda o mare importanta păstrării secretului militar. El a inventat un pătrat, cu ajutorul căruia literele se codificau prin numere de doua cifre, in care cifrele reprezintă linia, respectiv coloana pătratului In care se găsea litera. Sistemul lui Polibiu este prima forma concreta de schimb secretizat de mesaje, utilizând in premiera un tabel de cifrare in forma de pătrat. SecretuI era asigurat prin schimbarea cifrelor sau prin amestecarea literelor, obținându-se noi si noi variante. Datorita caracteristicilor lui – conversiunea literelor in numere de doua cifre separabile si reducerea numărului de simboluri utilizate (5 in loc de 26) -, pătratul lui Polibiu se regăsește la baza elaborării unui mare număr de sisteme de cifrare utilizate si astăzi.

Criptografia in evul mediu

Societatea feudala timpurie ce s-a ridicat pe ruinele imperiului roman nu a favorizat dezvoltarea științei si a culturii. Mai târziu, in jurul anului 1440, descoperirea tiparului – eveniment de o însemnătate deosebita pentru progresul omenirii – a dat un nou impuls preocupărilor pentru dezvoltarea criptografiei.

In perioada Renașterii, când limba si cultura greaca au fost din nou studiate, umaniștii, cercetând aproape o mie de manuscrise ale autorilor antici, au redescoperit, printre altele, metodele de cifrare folosite in antichitate. Dezvoltarea criptologiei a luat avânt in strânsa legătura cu extinderea si amplificarea relațiilor diplomatice dintre diferitele state feudale. Curțile regale, ca si statui papal, dispuneau de criptanaliști.

Criptologii care serveau la suveranul pontif se numărau printre cei mai buni specialiști ai vremii.

In anul 1518 a apărut prima carte asupra criptologiei – "Poligraphiae libri sex", in care metoda de cifrare descrisa era denumita tablou de transpoziție. Întocmit sub forma pătratica, tabloul de transpoziție se obținea prin deplasarea ciclica spre stânga a alfabetului normal de atâtea ori cate litere are alfabetul, după care alfabetele astfel rezultate erau scrise unul sub altul. Cu ajutorul metodei de cifrare descrise orice litera clara din prima linie putea fi substituita cu orice litera a alfabetului in funcție de cheia stabilita pentru litera respectiva, motiv pentru care substituția respective se numește polialfabetică.

Giambattista della Porta si-a înscris numele si in istoria criptologiei prin lucrarea sa "De Furtivis Literarum Notis", apărută in 1563. Cele patru cărți componente ale acestei lucrări se remarca atât prin prezentarea riguroasa a drumului parcurs de criptologie, prin observațiile critice asupra metodelor folosite de predecesori, cât si prin contribuțiile autorului la dezvoltarea criptologiei.

Pe baza tabelelor de frecventa a literelor cunoscute pana atunci s-a propus un nou procedeu de cifrare ce a constat intr-o asemenea substituție in care o anumita litera a textului clar poate fi cifrata prin oricare din cele 20 de litere diferite ale textului si invers; un cifru putea sa reprezinte 20 de litere diferite ale textului clar. S-a inventat substituția diagramelor, in care doua litere sunt reprezentate printr-un singur cifru. Ca un inconvenient al procedeului, s-a constatat faptul ca este nevoie de un tabel de chei pentru cifrare si descifrare, ceea ce periclitează păstrarea secretului.

De numele lui Vigenere se leagă dezvoltarea unor metode noi de cifrare. El a scris o carte "TratatuI cifrurilor sau modalităților secrete de a scrie" (1586), mult citata de criptologi. Printre metodele de cifrare descrise in lucrare, multe se bazează pe substituția polialfabetică. Metoda lui Vigenere a fost incorporata in mai multe mașini de cifrat moderne.

Preocupările științifice ale lui Cardan (1501-1576) – matematician italian, naturalist, medic renumit al epocii sale – au influențat si criptografia, aflata pe atunci in reînnoire. in lucrarea sa "De rerum varietate", cunoscuta in toata Europa acelor vremuri, Cardan a conceput întărirea siguranței secretului prin schimbarea cheii la fiecare mesaj. El a dat o soluție ingenioasa, utilizând mesajul însuși drept cheie. Practic aceasta consta dintr-o grila. cu ferestre la intervale neregulate, de înălțimea unui rând de scris si de lungime variabila. După așezarea grilei pe hârtie, se scria mesajul secret in ferestre, iar la descifrare se așeza din nou grila pe textul primit. Completarea mesajului secret, – scris in ferestre, cu un text ascunzător -, fiind o operație greoaie, Cardan a aplicat textului in clar, inserții după o anumita regula in pătratele unui pătrat de aceeași dimensiune ca si grila, o operație de transpoziție prin rotirea grilei, modalitate considerate ca forma primara a metodelor de transpoziție.

Primul criptolog profesionist din Franța. Rosignol, a fost considerat cel mai abil descifrator din Europa. Intervențiile sale au facilitat multe succese diplomatice, au contribuit la obținerea victoriei in multe din bătăliile purtate de Ludovic al Xlll-lea si Ludovic al XIV-lea. Datorita sugestiilor lui s-a organizat așa numitul cabinet negru care, pe parcursul secolului al XVIII-lea. a cunoscut cu regularitate conținutul corespondentei diplomaților străini. Rosignol si-a dovedit competenta nu numai in domeniul criptanalizei, ci si in cel al cifrării. El a reușit să modifice modul de stabilire a corespondentei intre elementele clare ale mesajului si cifruri, introducând doua tipuri de corespondente, denumite tabel de cifrare si tabel de descifrare.

Criptografia in epoca moderna

Dezvoltarea criptografiei a fost mult stimulata datorita inventării telegrafului. Acest dispozitiv de transmitere a informației avea menirea sa satisfacă nevoile crescânde de comunicare in condițiile dezvoltării impetuoase a industriei si comerțului, a vieții sociale in general, telegraful a determinat schimbări substanțiale si in activitatea comandamentelor militare; in consecința au devenit posibile controlul permanent al acțiunilor unităților militare, conducerea operativa a acestora si creșterea numărului mesajelor secrete transmise. Aceasta situație a impus abordarea de pe poziții noi a problemelor referitoare la păstrarea si utilizarea in secret a informațiilor.

A apărut necesitatea sa se facă distincție intre un sistem de scriere cifrata destinat pentru un schimb temporar de scrisori intre câteva persoane izolate si o metoda criptografica pentru un trafic intens de mesaje.

Începând cu perioada premergătoare primului război mondial, radioul a fost folosit intens pentru transmiterea informațiilor secrete de natura militara si diplomatica. In paralel cu creșterea volumului de informație transmisa pe aceasta cale, a luat avânt si activitatea de criptanaliza. Pentru apărarea secretului mesajelor diplomatice, in anii 1920 s-a introdus o noua metoda in criptografie, cunoscuta sub denumirea de bloc cu o singura utilizare. Metoda consta in utilizarea drept cheie a unor blocuri formate din grupuri de cifre alese la întâmplare si tipărite, foile ce conțineau aceste grupuri de cifre fiind legate intr-un volum. Fiecare foaie se folosea o singura data, după care era distrusa. Deși ținuta in cel mai mare secret, metoda s-a răspândit in decurs de 10-15 ani in întreaga lume. Folosita si azi, ea este considerate una din cele mai sigure metode criptografice.

Dispozitive clasice de cifrare

Toți cei care s-au ocupat de-a lungul mileniilor cu scrierea cifrata au putut sa constate ca cifrarea se executa prin multe operații mecanice. Executarea repetata a acestora cere multa precizie si, in plus, necesita un timp îndelungat. De aceea s-au căutat diferite modalități pentru simplificarea si scurtarea duratei cifrării. Ca urmare a cercetărilor întreprinse au rezultat diferite variante mecanizate ale cifrării si cheii. Pe parcursul secolelor au fost inventate mai multe tipuri de dispozitive de cifrare si chei mecanizate: rigIa, cilindru, cadran de ceas, disc rotativ, etc. Aceste dispozitive au construcție variata, la realizarea lor fiind folosite cele mai diverse materiale. După forma lor, dispozitivele de cifrare pot fi grupate in rigle si discuri. Rigla glisanta, asemănătoare riglei de calcul, se compune din doua elemente: corpul riglei si rigleta. Pe corpul riglei se scrie alfabetul in clar, iar pe rigleta unul sau doua alfabete ale semnelor cifrate. O litera in clar se poate înlocui cu unul sau doua cifruri. Dispozitivul sub forma de disc este o soluție tehnica mai buna, dar nu prezintă avantaj din punct de vedere criptografic.

In anii 1800 serviciul de cifrare cel mai dezvoltat aparținea armatei franceze. Printre colaborac.

In anii 1800 serviciul de cifrare cel mai dezvoltat aparținea armatei franceze. Printre colaboratorii secției de cifrare a statului-major se număra si un expert in criptografie, maiorul Bazaries. De numele lui se leagă descifrarea "Marelui Cifru" folosit de Ludovic al XIV-lea, cheie care mult timp a fost pierduta si, de asemenea, inventarea cilindrului de cifrare prin care s-au pus bazele cifrării mecanizate.

Metoda propusa de Bazaries reprezintă, de fapt, o varianta a tabelei lui Vingenere cu alfabete mixate. Pe un disc de metal s-au gravat amestecate cele 26 litere ale alfabetului latin, s-au folosit in total 25 de astfel de discuri numerotate de la 1 la 25, respectiv notate cu literele de la B la Z. Numerotarea discurilor a servit la identificarea poziționării numărului sau cuvântului cheie dat. Discurile fiind găurite la centru, a existat posibilitatea asamblării lor pe un ax obținându-se un cilindru de cifrare. O rigla glisanta a permis citirea literelor de pe o generatoare a cilindrului.

S-a stabilit ca cifrarea cu ajutorul cilindrului lui Bazaries a asigurat secretul mesajului in funcție de pregătirea criptanalistului, de la 6 ore pana la 3 zile. In consecința, ca măsură de protecție a secretului, cuvântuI cheie era schimbat după 6 ore. Perfecționarea mașinilor de cifrat – ca si a altor dispozitive tehnice – este indisolubil legata de nivelul de dezvoltare a științei si tehnicii din epoca respectiva.

Primele mașini de cifrat erau construite din elemente de mașini simple (roti dințate, came, etc.). Constructorii mașinilor de cifrat au urmărit doua scopuri: pe de o parte își propuneau mărirea siguranței in cifrare, iar pe de alta parte, simplificarea si accelerarea activității de cifrare. Realizarea concomitenta a acestor doua obiective nu a fost asigurata de nici un procedeu de cifrare înaintea apariției mașinilor de cifrat.

Ca urmare a dezvoltării mecanizării, au apărut diferite mașini de cifrat, de la cele mai simple pana la cele cu performante ridicate, inventivitatea găsindu-si un teren larg de acțiune. Se cunosc mașini realizate exclusiv pe baza principiilor mecanicii; ele funcționează prin combinarea in diferite moduri a discurilor, roților dințate si a barelor. Punerea lor in funcțiune se făcea manual sau prin intermediul unui arc.

Mașinile de tip telegraf au mărit ritmul cifrării pana la viteza dactilografierii (150-200 litere/minut); totuși aceasta viteza nu era mulțumitoare. Chiar si telegraful Morse corespundea din ce in ce mai puțin din acest punct de vedere. De aceea inventatorii se străduiau sa construiască un aparat al cărui receptor trebuia să tipărească in mod automat literele si alte semne grafice din compunerea mesajelor. Din punct de vedere criptografic, atât codul telegrafic cit si codul Morse reprezintă, in fond, o simpIa substitute de litere prin configurații de puncte si linii, respectiv prin combinații de cinci semne binare (impulsuri pozitive sau negative).

FaptuI ca atât sistemele telegrafice, cat si mașinile de cifrat lucrează cu semnale discrete a favorizat foarte mult asamblarea constructiva a acestor dispozitive.

Mașina Hagelin C-48 a fost utilizata de către armata americana in timpul celui de-al doilea război mondial sub denumirea M-209. Aceasta mașina este unul din putinele dispozitive de cifrare cu descriere completa in literatura de specialitate. Soluțiile folosite pentru realizarea lui M-209 evidențiază câteva tehnici general valabile utilizate in elaborarea dispozitivelor de cifrare. EchipamentuI combină, caracter cu caracter, textul clar cu un sir cheie, care reprezintă o secvența pseudoaleatoare derivata din cheie pentru a produce textul cifrat in mod similar cu metoda lui Vigenere. Textul clar, șirul de chei si textul cifrat sunt scrise in alfabetul latin de 26 litere. După ce se stabilește o corespondenta biunivoca între literele alfabetului si numerele 0, 1, . . ., 25, textul clar, P se scade modulo 26 din șirul cheie, KS, pentru obținerea textului cifrat.

C = KS – P (mod 26)

La recepție. din textul cifrat se obține textul clar pe baza relației:
P = KS – C (mod 26)

Dispozitivul efectuează operația de generare a șirului cheie cu ajutorul unor roti dințate si al unei cutii. Rotile dințate generează o secvență lungă alcătuita din grupuri de sase biți, iar cutia transforma grupurile de sase biți intr-o literă. Cheia mașinii consta in poziționarea atât a roților, cit si a cutiei. Cele sase roti de cheie pot fi considerate roti dințate cu 26, 25, 23, 21. 19 si respectiv 17 dinți. In dreptul fiecărui dinte se afIă un pin care poate fi retras (0) sau împins (1); fiecare bit al cheii este folosit pentru a acționa un pin, poziționându-l fie pe 1 fie pe 0. După fixarea poziției pinilor, rotile se aduc in pozițiile inițiale, fiecare indicând litera A; in consecință, in cele sase ferestre rezulta succesiunea AAAAAA. Cei sase biți care corespund dintelui A de pe fiecare roata determina prima litera din șirul-cheie. După cifrarea primului caracter clar, fiecare roata este rotita cu o poziție, astfel ca in ferestre apare succesiunea BBBBBB. Alți 6 biți ai cheii (pini) generează cel de-al doilea caracter al șirului-cheie, independent de primul. Aceasta independenta realizează 17 generări, când apare in ferestre succesiunea QQQQQQ. Cea de-a 18-a litera a șirului cheie este determinata de dinții care corespund dinților RRRRRA, deoarece ultima roata a făcut deja o poziție completa. Astfel, a 18-a litera a șirului cheie este corelata cu prima litera, a 19-a, SSSSSB, este corelata cu cea de-a doua, iar a douăzecia, TTTTAC, este corelata atât cu prima litera, cit si cu cea de-a treia. Deoarece numerele 26, 25, 23, 21, 19 si 17 nu au factor comun, rotile revin in poziția inițiala, AAAAAA, după generarea a 26*25*23*21*19*17 aprox. egal 101*106 litere.

Cutia are un rol asemănător memoriei programabile (PROM) cu 26 = 64 caractere. Aceste caractere aparțin alfabetului latin si sunt reprezentate prin numere cuprinse intre 0 si 25. Fiecare grup de 6 biți generat de roti este transformat intr-o litera prin adresarea celor sase biți corespunzători unei locații a memoriei, evidențiindu-se, totodată, caracterul conținutului acestuia.

Mașina M-209. realizata la nivelul anului 1940, folosea in locul memoriei PROM un sistem mecanic compus din 27 bare prevăzute fiecare cu cate doua mânere. Aceste mânere pot sa ocupe 8 poziții, dintre care sase sunt alineate cu pinii roților dințate, iar doua sunt "inactive". După ce s-a obținut un grup de sase biți prin rotirea unei roti dințate, fiecare din cele 27 bare trece peste aceștia. Daca unui sau ambele mânere de pe bara lovește un pin împins. bara respectiva este deplasata spre stânga (mânerele fiind oblice) si pune in mișcare un angrenaj pentru imprimarea textului cifrat.

In literatura de specialitate se fac o serie de referiri la posibilitatea de a "sparge" un astfel de sistem de cifrare atât in cazul in care sunt cunoscute textul clar si cel cifrat corespunzător, cat si in lipsa textului clar. Se apreciază ca la un atac cu un text clar si cifrat sunt suficiente 100 caractere, iar in cazul unui atac doar cu text cifrat sunt necesare 1000-2000 caractere.

Mașinile cu rotor au constituit cele mai importante dispozitive criptografice in timpul celui de-al doilea război mondial si până in anii 1950. Modelele cele mai cunoscute sunt: M-134 sau SIGABA (SUA). TYPEX (Anglia) si ENIGMA (Germania).

Componenta centrala a unui asemenea echipament este rotorul sau roata cablata care servește la obținerea cifrului. Pe cele doua fete ale discului. In perimetrul lor, exista M contacte electrice dispuse la distante egale, unde M este numărul caracterelor din alfabet (M=26 in cazul alfabetului latin sau M=128 in cazul utilizării codului ASCII). Fiecare contact de pe o fata a discului este cablat cu un contact pe cealaltă fata . La rotirea unui rotor cu o poziție se produce o permutare a literelor de la intrare. In general aceasta permutare se poate scrie sub forma:

P=CjRC-j

unde R este permutarea realizata de rotor prin cablaj, iar Cj – operatorul de deplasare ciclica cu j poziții. De exemplu dacă R(A)=G, iar rotorul este rotit cu j=3 poziții. Atunci textul clar D se afla in dreptul contactului rotorului care reprezintă textul clar A, iar textul cifrat J este in dreptul contactului rotorului care reprezintă textul cifrat G, deci P(D)=J, daca j=3. Aceasta operate e exprima algebric astfel:

P(D)=C3RC-3(D)=C3R(A)=C3(G)=J

Mai multe rotoare pot fi conectate împreuna. succesiv, formând un sistem. Permutarea realizate de sistemul de rotoare se poate scrie sub forma:

P=Cj1R1C-j1…CjnRnC-jn=Cj1R1Cj2-j1R2Cj3-j2…Cjn-jn-1RnC-jn

Sistemul de rotoare poate realiza o mare varietate de permutări deoarece rotoarele au multe poziții relative. Pentru ca sistemul criptografic sa fie puternic trebuie sa se modifice poziția rotoarelor după fiecare cifrare. Dezvoltarea calculatoarelor electronice din ultimele decenii a schimbat rapid evoluția criptografiei in doua direcții fundamentale: (1) utilizarea criptografiei – numita in acest caz si computaționala – pentru protecția datelor memorate si transmise intre calculatoare si (2) utilizarea calculatoarelor pentru descifrarea unor sisteme criptografice complexe, deci in criptanaliza.

Sisteme criptografice

Obiectivul principal al masurilor de protecție intr-un sistem de calcul îl constituie eliminarea posibilităților de distrugere accidentala sau voita a informațiilor, precum si de consultare neautorizata a acestora. Accesul neautorizat la informații poate provoca serioase daune prin afectarea caracterului privat al transmisiilor, introducerea unor date false sau trunchiate, falsificarea identității unor calculatoare, terminate ori utilizatori.

Dintre obiectivele importante care trebuie avute in vedere la proiectarea unor mecanisme – hardware si software – pentru protecția informațiilor intr-o rețea Ie menționam pe cele de prevenire a dezvăluirii conținutului in clar al mesajelor, a inserării de mesaje false, a analizei traficului de mesaje. precum si pe cele de detectare a modificării, ștergerii sau înlocuirii conținutului mesajelor, a încercărilor de conectare neautorizata in rețea.

Obiectivele de prevenire pot fi atinse prin cifrarea informațiilor, soluție eficienta când memorarea sau transmiterea de date se efectuează pe medii nesigure. Obiectivele de detectare sunt realizate daca se folosesc protocoale specifice, coroborate cu metode criptografice, care asigura schimburile de mesaje intre entitățile rețelei.

Cifrarea conferă protecție informației transmise pentru canalele ce sunt ascultate sau interceptate. in acest scop emițătorul alege un algoritm de cifrare si o cheie, pe care Ie comunica receptorului pe cale sigura, – de exemplu, prin curier. Criptografia modernă protejează datele transmise pe linii de mare viteza si memorate in calculatoare. Ea urmărește doua obiective principale, si anume: protecția sau confidențialitatea (prevenirea dezvăluirii neautorizate a unor informații transmise sau memorate) si autenticitatea sau integritatea (prevenirea unor modificări neautorizate ale datelor). Un sistem criptografic (criptosistem) are cinci componente

spațiul mesajelor in text clar. {M};

spațiul mesajelor in text cifrat, {C};

spațiul cheilor, {K};

familia transformărilor de cifrare, Ek : M C , unde K{K}

familia transformărilor de descifrare. Dk : C M , unde K{K}

Fiecare transformare de cifrare, Ek este definita de un algoritm de cifrare. E comun tuturor transformărilor familiei, si o cheie, K, distincta de la o transformare la alta. In mod similar, fiecare transformare de descifrare, Dk, este definita de un algoritm de descifrare D, si de cheia K. Pentru un K dat, Dk reprezintă inversa lui Ek, adică:

Dk(Ek(M))=M. M{M}

Figura 1 : Sistem criptografic

In figura 1 este ilustrat modul in care transformările de cifrare si descifrare sunt folosite pentru a se asigura protecția unui transfer de informații într-o rețea. Datele trebuie astfel protejate încât utilizatorii neautorizați sa nu poată reconstitui textul clar dintr-un text cifrat interceptat. In acest sens este necesar sa se asigure că:

utilizatorul neautorizat sa nu poată determina sistematic transformarea de descifrare, DK, din textul cifrat interceptat C, chiar dacă se cunoaște textul clar, M corespondent;

utilizatorul neautorizat sa nu poată reconstitui textul clar M din textul cifrat. C, fără cunoașterea transformării DK.

Protecția datelor (confidențialitatea) impune ca transformarea de cifrare Dt (respectiv cheia) sa fie protejata.

Figura 2 : Protecția datelor

Autentificarea datelor cere ca un utilizator neautorizat sa nu fie capabil in mod obiectiv sa substituie textul cifrat, C, cu un text cifrat fals. C', fără ca acest lucru sa fie detectat. Nu trebuie sa i se permită utilizatorului neautorizat:

sa determine sistematic transformarea EK, cunoscând pe C si textul dat corespunzător, M;

Figura 3 : Autentificarea datelor

sa găsească in mod sistematic C astfel ca DK(C') sa fie un text clar valid in M.
Cerințele de autentificare impun doar ca transformarea EK (respectiv, cheia de cifrare) sa fie protejata.

Criptosisteme cu chei publice

ConceptuI de criptosistem cu doua chei (asimetric) a fost introdus de Diffie si Hellman in 1976. Ei propuneau o noua metoda de cifrare, numita cifrare cu cheie publica, in cadrul căreia doi utilizatori (procese) pot comunica cunoscând fiecare doar cheia publica a celuilalt.

In criptosistemele cu chei publice fiecare utilizator A. deține o transformare de cifrare publica, EA, care poate fi memorata intr-un registru (fișier) public si o transformare de descifrare secreta, DA. ce nu este posibil sa fie obținuta din EA.

Figura 4 : Protecția în sistemele cu chei publice

Cheia de descifrare (secreta) este derivata din cheia de cifrare (publica) printr-o transformare greu inversabila (one-way). In sistemele cu chei publice, protecția si autentificarea sunt realizate prin transformări distincte. Sa presupunem ca utilizatorul (procesul) A dorește sa emită un mesaj, M, unui alt utilizator (proces) B. Daca A cunoaște transformarea publica EB, atunci A poate transmite M la B sub forma C=EB(M). asigurându-se astfel funcția de protecție (confidențialitate).

La recepție. B, va descifra criptograma C utilizând transformarea secreta DB,cunoscuta doar de el:

DB(C)=DB(EB(M))=M.

Schema nu furnizează facilitați de autentificare, deoarece orice utilizator (proces) are acces la transformarea publica EB a lui B si ii poate trimite mesaje false M' sub forma C'=EB(M')

Pentru autentificare se aplica lui M transformarea secrete DA a lui A. Ignorând protecția pentru moment, A va emite C=DA(M) la B, care la recepție va aplica transformarea publica EA a lui A:

EA(C)=EA(DA(M))=M

Figura 5 : Autentificarea in sisteme criptografice cu chei publice

Autentificarea este realizata deoarece numai A poate aplica transformarea DA.

Protecția nu este asigurata, întrucât este posibil ca M se fie obținut de oricine aplicând transformarea publica EA. Pentru a se realiza simultan protecția si autentificarea informațiilor spațiului {M} trebuie sa fie echivalent spațiului {C}, așa încât orice pereche (EA, DA) sa fie in măsura sa opereze atât asupra textului clar, cat si asupra textului cifrat; in plus se cere ca EA si DA sa fie mutual inverse, adică :

EA(DA(M))=DA(EA(A))=M.

Figura 6 : Protecția si autentificarea in criptosistemele cu chei publice

Emițătorul de mesaj A va aplica mai întâi transformarea secreta a sa, DA, mesajului M. Apoi A va cifra rezultatul – utilizând transformarea publica a lui B, EB si va emite catre receptor criptograma:

C=EB(DA(M)).

Receptorul B îl obține pe M aplicând la început propria-i funcție de descifrare, DB, iar apoi transformare publica a lui A, ea, cea care furnizează autentificarea :

EA(DB(C))=EA(DB(EB(DA(M))))=EA(DA(M))=M.

Conceptul de semnătură digitală

Semnătura digitala reprezintă un atribut al unui utilizator sau proces, fiind folosita pentru recunoașterea acestuia. Fie B un receptor de mesaj semnat de A.

Semnătura lui A trebuie sa satisfacă următoarele proprietăți:

B sa fie capabil sa valideze semnătura lui A;

sa fie imposibil pentru oricine, inclusiv B, sa falsifice semnătura lui A;

in cazul in care A nu recunoaște semnarea unui mesaj M, trebuie sa existe un "judecător" care sa poată rezolva disputa dintre A si B.

Semnătura digitală rezoIvă atât problema autentificării emițătorului cit si pe cea a autentificării datelor. Sistemele de autentificare cu chei publice permit o implementare simpIa a semnăturilor digitale. Deoarece este deținuta doar de A, transformarea DA poate servi ca semnătura digitală pentru A. Receptorul B al mesajului M semnat (transformat prin DA) este sigur atât de autenticitatea emițătorului, cat si de aceea a datelor. Deoarece transformarea inversa EA este publica, receptorul B va putea valida semnătura. Procesele se desfășoară astfel:

A semnează pe M calculând S=DA(M);

B validează semnătura lui A, verificând daca EA(S)=M;

Un "judecător" rezolva eventuala disputa dintre A si B controlând daca EA(S) conduce la M, in aceeași maniera ca si B.

Serviciul de semnătura digitala trebuie sa asigure originea autentica a unui mesaj, document sau fișier. Pentru aceasta, semnătura trebuie sa satisfacă 2 cerințe:

sa depindă de mesaj (pentru a nu putea fi mutata de la un mesaj la altul);

sa depindă de emițător (pentru a nu putea fi falsificata).

Semnătura olografa din documentele scrise identifica autorul acestora. Ea certifica ca documentul este original si conține acele informații pe care autorul a vrut sa Ie trimită. In sistemele de semnătura digitala bazate pe cifrurile cu chei publice, emițătorul unui document / mesaj / scrisoare va folosi cheia sa secreta pentru crearea semnăturii. Ea se aplica nu mesajului original ci unei valori rezumat (digest) obținuta cu ajutorul unei funcții de dispersie (hash), valoare care are de obicei 128 de biți.

Una din condițiile esențiale pentru algoritmii de dispersie este ca o schimbare de doar un bit al mesajului original sa producă o avalanșa de schimbări la ieșire (aproximativ 50% din biții modificați in valoarea rezumat). Receptorul mesajului semnat poate verifica originea autentica a acestuia (si integritatea) cu ajutorul cheii publice a emițătorului. In scopul realizării acestui tip de serviciu se folosesc criptosisteme D cu chei publice. Deoarece criptosistemele cu chei publice au o mare complexitate si consuma un timp important, semnătura D se aplica unei forme condensate a mesajelor (documente, fișiere) obținute printr-o funcție de dispersie Fhash. Serviciul are 2 funcții diferite: crearea si verificarea semnăturii.

In acest fel receptorul unui mesaj este sigur ca acesta provine de la emițătorul autentic, singurul capabil sa realizeze semnătura in mod direct.

Criptografia in securitatea rețelelor calculatoarelor

Multa lume considera ca securitatea unui PC este prea complicata, prea scumpa si deci nu se justifica luarea unor masuri speciale. Aceste scuze nu sunt valabile întotdeauna. Securitatea pe un PC care nu este conectat in rețea este ușor de instalat, folosit si întreținut. De cele mai multe ori este necesara adăugarea unui (unor) programe de securitate realizate de utilizatori sau, preferabil, cumpărate de la firme specializate. Deși sunt disponibile multe produse program si echipamente pentru a "încuia cabinetul PC", ele se împart in câteva categorii funcționale. Puteți cifra datele pe discul hard, puteți preveni accesul la date sau puteți supraveghea fișierele importante pentru contaminare cu viruși. Care dintre aceste moduri Ie veți adopta (sau combinații ale lor) va depinde de ce fel de securitate se dorește si ce deschidere are calculatorul spre exterior.

Cifrarea fișierelor de date (documente-text, baze de date si spreadsheet-uri) este cea mai simpIa linie de apărare. "spionii" ocazionali nu pot citi ușor fișierele cifrate, dar un hot de date versat poate adesea descifra fișierele daca algoritmul nu este judicios ales.

Anumite produse facilitează transmisia in siguranța a datelor intre doua modemuri, incluzând programe si echipamente integrate.

Securitatea transmisiei de date intre doua puncte ale unei rețele are trei cerințe importante. Prima este sa se garanteze ca ceea ce se recepționează este ce s-a trimis (autenticitatea mesajelor).

Aceasta asigura ca datele nu au fost interceptate si alterate pe parcurs. A doua cerința este sa se determine identitatea autorului mesajelor (autenticitatea emițătorului). Iar a treia cerința este sa va asigurați ca traficul este sigur si confidențial pe parcurs (secretizarea sau confidențialitatea).

Toți experții in securitate sunt de acord ca cel mai bun mod de protejare a datelor rezidente pe calculator este interzicerea accesului la calculator. Cât timp cifrarea datelor reprezintă o anumita măsura de securitate, ea trebuie sa fie parte dintr-un program larg de securitate care include mai multe bariere pentru intruși. Sunt doua cai de ridicare a acestor bariere, folosind programe sau echipamente. Sistemele software proiectate sa împiedice furtul de date sunt cel mai ușor de instalat si folosit dar pot permite intrușilor avizați sa intre "pe ușa din spate".

Totuși, barierele software, puse in calea intrușilor, pot cădea in fata celor îndemânatici si perseverenți. Cea mai buna protecție posibila împotriva tuturor formelor de încălcare a securității este combinarea securității hard cu cea soft.
Azi, când accesul la datele din calculator este aproape universal, informația proprie poate fi furata așa cum copiezi o discheta. Sistemele de securitate au devenit nu tocmai ușor de folosit si întreținut, dar absolut necesare pentru o utilizare sigura a calculatoarelor.

Atât in cazul in care se optează pentru achiziționarea unor produse de securitate informatica, cat si in cazul in care se dorește proiectarea si implementarea de sisteme proprii, va sunt necesare cunoștințe privind algoritmii si protocoalele criptografice.

Capitolul II :

Criptografia clasică

II.1 – Substituții si permutări in criptografia clasica

II.2 – Cifruri transpoziție

II.3 – Cifruri substituție

II.4 – Substituții monoalfabetice

II.5 – Substituția omofonica

II.6 – Substituția polialfabetică

II.7 – Substituția poligramică

II.8 – Cifruri produs

Substituții si permutări in criptografia clasica

La baza cifrurilor simetrice, deci a celor care folosesc pentru cifrare o singura cheie, secreta, stau cifrurile elementare: transpoziția si substituția.

Cifruri transpoziție

Cifrurile transpoziție realizează o permutare a caracterelor din textul clar. Cheia de cifrare este perechea K=(d,f) unde d reprezintă lungimea blocurilor succesive de caractere care vor fi cifrate conform permutării f,

f:Zd->Zd , Zd={1.2…..d}.

de forma:

unde, evident f(i)f(j), ij

Mulțimea funcțiilor astfel definite este d!. In acest fel mesajul clar
M=m1m2…md md+1…md+d…

este cifrat astfel:

Ek(M)=mf(1)…mf(d)md+f(1)…md+f(d)
Descifrarea se obține prin permutarea inversa.

Cifrarea prin transpoziție este o transformare a textului clar prin care se modifica poziția caracterelor in mesaj. Transpozițiile se pot aplica întregului mesaj sau blocurilor de lungime d obținute prin împărțirea mesajului întreg. In metoda de cifrare transpozițională alfabetul textului clar rămâne neschimbat. O metoda des folosita pentru implementarea acestui tip de transformări este scrierea mesajului intr-o anumita matrice după care textul clar se obține prin citirea caracterelor pe linie, pe coloana sau după un anumit traseu in matrice. Cifrurile transpoziție se pot clasifica după numărul lor de aplicare, in transpoziții monofazice, când se aplica o singura data, si transpoziții polifazice, când se aplica de mai multe ori. De asemenea, daca in procesul de transformare elementul unitate este litera, atunci transpoziția se numește monografică, iar daca se transpun grupe de litere (simboluri) transpoziția se numește poligrafică.

Cele mai simple transpoziții monografice se obțin prin împărțirea textului clar in două jumătăți care se scriu una sub alta, după care se citesc coloanele de la stânga la dreapta. De exemplu, cuvântul CALCULATOR se cifrează astfel:

Daca se împarte cuvântul CALCULATOR in doua :

C L U A O

A C L T R

citirea rândurilor de sus in jos. conduce la criptograma: CLUAOACLTR. Acest sistem este ușor de atacat, deoarece frecventa de apariție a literelor rămâne invarianta in procesul cifrării. De asemenea se obține o transpoziție de caractere daca literele textului clar se scriu ca elemente ale unei matrice. Se completează matricea cu literele textului clar, plecând de la un element oarecare al matricei. pe un anumit traseu. Se obține textul cifrat parcurgând întreaga matrice pe un alt traseu. Astfel, textul clar CALCULATOR UNIVERSAL FELIX se poate scrie sub forma matriceala:

CALCU
LATOR
UNIVE

RSALX
FELIX

Mesajul se poate cifra in următoarele moduri:

prin citirea elementelor matricei pe coloane de la stânga la dreapta ceea ce conduce la următoarele criptograme: CLURFAANSELTIALCOVLIUREXX;

prin citirea elementelor matricei pe diagonala de jos in sus începând cu primul element al matricei: CLAUALRNTCFSIOUEAYRLLEIXX,

In practica cifrării, stabilirea traseelor de citire din matrice se face in mod frecvent cu ajutorul unui cuvânt cheie. Cheia are un număr de litere egal cu numărul de coloane din matrice. Literele cheii, numerotate in ordine alfabetica, se scriu deasupra matricei; coloanele matricei. in ordinea stabilita de cheie, fumizează textul cifrat.

O transpoziție ingenioasă a literelor dintr-un text clar se poate realiza prin rotirea cu 90 de grade a unei grile de forma pătratica. Se pot imagina si alte grile (triunghi, pentagon, hexagon etc.) care pot fi folosite la transpoziția literelor din textul clar.

De asemenea trebuie observat ca se pot realiza si alte tipuri de transpoziții, cum ar fi cele operate asupra unor grupuri de litere-transpoziții poligrafice.

Figura 7 : Cutie P pentru transpoziții

In cazul cifrurilor computaționale, adică a celor care se folosesc la protejarea datelor in sistemele informatice. transpoziția se realizează prin cutii P. Cifrurile transpoziție reprezintă componente importante ale criptosistemelor complexe.

Cifruri substituție

Cifrurile substitute înlocuiesc fiecare caracter din alfabetul mesajelor A cu un caracter din alfabetul criptogramelor C. Daca A={a1,a2,…,an} atunci C={f(a1),f(a2)…..f(an)} unde f: A -> C este funcția de substituție, constituind cheia cifrului.

Cifrarea unui mesaj M=m1m2…mn se face astfel:

Ek(M)=f(m1)f(m2)…f(mn)

Deci substituțiile sunt transformări prin care caracterele (literele) sau grupurile de caractere ale alfabetului primar sunt înlocuite cu caracterele sau grupurile de caractere ale alfabetului secundar.

In practica se aplica frecvent substituția care se poate descrie cu ajutorul transformării liniare de forma:

C=aM+b(mod N)

In acest scop se stabilește o corespondenta biunivoca intre literele alfabetului primar si numerele întregi 0,1,…,N-1 care formează un inel, ZN, față de operațiile de adunare modulo N si înmulțire modulo N. In relație, a se numește factor de amplificare, iar b coeficientul de deplasare. Prin particularizarea coeficienților a si b se obțin cazuri particulare de transformări liniare. In cazul cel mai simplu se stabilește o corespondenta între literele miM ale alfabetului primar si elementele alfabetului secundar (eventual alfabetului extins) al criptogramei.

Substituții monoalfabetice

Transformările cu o singura lege de corespondenta intre literele alfabetului primar si cele ale alfabetului secundar se numesc substituții monoalfabetice. Cea mai simplă substituție monoalfabetică este cunoscuta sub denumirea de cifrul lui Cezar. In cifrul lui Cezar atât alfabetul primar, cit si cel secundar coincid cu alfabetul latin de 26 de litere. Corespondenta biunivoca între literele celor două alfabete se stabilește scriind in ordinea alfabetica literele si trecând sub fiecare literă corespondenta acesteia din alfabetul secundar, obținuta prin deplasarea ciclica cu trei poziții la stânga a literelor alfabetului primar. Corespondenta in cifrul Cezar este:

Astfel lui A îi corespunde litera D. lui B litera E s.a.m.d.

Folosind corespondenta biunivoca între literele alfabetului latin (mi) si echivalentele lor numerice (ei) unde ei{0,1,2…,25}, cifrul lui Cezar se poate scrie sub forma:

C(ei)=ei+3(mod 26)

Ulterior, cifrul lui Cezar a fost generalizat, prin alegerea in calitate de cheie a oricărei litere din alfabet. In acest caz corespondenta invariabila este stabilita prin funcția:

C(ei)=ei+b(mod 26),unde ei,bi{0,1.2…,25}.

Prin particularizarea, in continuare, a coeficienților, punând b=0, se obține o substituție de litere de forma:

C(ei)=a*ei(mod 26).

Corespondenta eiC(ei) este biunivoca daca numerele a si 26 sunt relativ prime, deci (a,N)=1. in caz contrar doua sau mai multe litere primare vor fi cifrate prin aceeași litera si funcția de cifrare nu admite o inversa.

Alegând a astfel încât sa fie relativ prim cu N=26, relația stabilește o permutare a alfabetului primar. De exemplu, luând a=3, se obține următoarea corespondentă:

Literele cifrului se pot obține din alfabetul primar si prin următorul proces de selectare: se alege prima litera A si apoi, in ordinea ciclica fiecare a treia litera; deci D, G, …,Y. După Y șirul cifrului se continuă cu B, deoarece, in ordinea ciclica, a treia literă după Y in alfabetul primar este B ș.a.m.d., motiv pentru care factorul de amplificare a=3 se mai numește si factor de selectare.

Se poate obține un alfabet de substitute prin compunerea operației de deplasare cu operația de selectare. Astfel, de exemplu, alegând b=4 si a=3 se obține cifrul: C(ei)=3(ei+4)(mod 26), ceea ce este echivalent cu o transformare liniara generala de forma:

C(ei)=3ei+12(mod26),

Cifrul sau permutarea P a literelor alfabetului primar. Unde :

P=A B C . . . X Y Z

M P S . . . D G J

se poate caracteriza in mod univoc prin perechea de numere (3,4), in care 3 reprezintă factorul de selectare. iar 4 coeficientul de deplasare.

In general, perechea de numere (a,b) care definește in mod univoc o transformare liniara se numește cheia substituției respective. Cifrurile substituție prezentate pana acum – cifrul lui Cezar, cifrul obținut prin operația de selectare si cifrul obținut prin compunerea operației de deplasare ciclica de amplitudine b cu operația de selectare, având intervalul de selectare a – pot fi considerate ca cifruri simple si slabe la atacurile criptanalitice. Ele sunt simple deoarece cheile prin care aceste substituții se definesc sunt numerele a si b. Cifrurile sunt slabe la atacurile criptanalitice, deoarece este suficient pentru criptanalist sa stabilească o cheie simpla, pe baza căreia apoi sa obțină substituția tuturor literelor.

Cifrul de substituție cel mai puternic si cel mai rezistent la atacurile criptanalitice este cifrul aleator de substituție, in care literele alfabetului de substitute se obțin printr-un proces aleator.

Cifrul aleator de substituție, pe lângă avantajele referitoare la dificultățile sporite ale decriptării, întrucât literele alfabetului de substituire sunt statistic independente, prezintă insa un dezavantaj in privința generării, transmiterii si păstrării cheii. Cheia conține, in acest caz, 26 de perechi de numere echivalente de forma (a,b), unde a,b {0,1,…,25}, si ca atare necesita o memorie de 26 de ori mai mare decât cifrul de substituție cu transformare liniara. in plus, memorarea cheii de cifrare de către cifrator si descifrator fiind imposibilă, se recurge la înregistrarea cheii intr-o anumita modalitate ce determina insă apariția pericolului pierderii sau furtului cheii.

Un sistem de cifrare bazat pe substituție se poate obține si prin folosirea unei chei mnemonice. De exemplu, o permutare a alfabetului primar se poate preciza cu ajutorul unei chei mnemonice. Pentru aceasta se alege cheia literală CERNEALA sub care se scrie cheia numerica, care se obține prin numărarea literelor cuvântului-cheie, după așezarea lor in ordinea alfabetica; deci:

Cheia literala: CERNEALA

Cheia numerica: 34875162

In care primul A din cuvântul cheie are numărul de ordine 1, cel de al doilea A numărul 2 s.a.m.d.

In continuare se scriu literele alfabetului primar sub cheia numerica sub forma:
CERNEALA
3 48 75 1 62

ABCDEFGH

I J KLMNOP

QRSTUVWX

YZ.

Corespondenta monoalfabetică, corespunzătoare cuvântului cheie CERNEALA se obține, prin scrierea sub literele alfabetului primar a literelor coloanelor de mai sus in ordinea crescătoare, adică:

P= A B C … X Y Z

F N V … C K S

Cu ajutorul acestei corespondente se poate cifra orice text clar, obținând textul cifrat. In acest caz numărul corespondentelor posibile creste de la 26 la 26! si ca atare aceasta metoda de cifrare implica operații criptanalitice de mare complexitate.

Cifrând încă o dată permutarea P conform cuvântului cheie CERNEALA, se obține permutarea P2(CERNEALA). In acest caz, tabelul pentru a doua substituție este de forma:

CERNEALA

3 48 751 62

FNV HPXAI

QYBJRZEM

UGOWDLTC

KS
de unde rezulta permutarea:

P2(CERNEALA)=A B C . . . X Y Z

X Z L . . . V B O

In mod asemănător se pot construi permutările P3,…,Pn.

Un cifru de substituție se poate obține si cu ajutorul unui tabel sub forma de scara. Pentru aceasta se scriu toate literele alfabetului, in ordinea alfabetica, sub literele cheii, cu condiția ca linia i sa se completeze începând cu coloana i, pentru i=1,2,….

Apoi permutarea fixa sau alfabetul cifrat rezulta din scrierea sub literele alfabetului primar a literelor coloanelor tabelului scara in ordinea crescătoare. Astfel, de exemplu, pentru cheia mnemonica:

care conduce la următoarea permutare:

A B C D E……………W X Y Z

R S Z A T…………….L N Q Y

Un alt procedeu de obținere a unui alfabet cifrat consta in repetarea cuvântului cheie pana rezulta un număr de litere egal cu numărul literelor din alfabetul primar.

Acesta se scrie sub literele alfabetului primar si se numerotează in ordine alfabetica de la 0 pana la 25. Litera A se cifrează prin acea litera care este deasupra lui 0 s.a.m.d.

Substituția omofonica

Cifrurile bazate pe substituție simpla sunt in general ușor de spart prin atac cu text-cifrat, utilizând insa si frecventele de apariție a caracterelor. O varianta de substituție este cea omofonica prin care se înlocuiește fiecare caracter din A cu un

caracter dintr-o mulțime f(A). Funcția f se definește astfel:

f:A2C

Un mesaj clar M=m1m2…mn va fi cifrat sub forma C=c1c2…cn unde fiecare ci este ales aleator din mulțimea f(mi). Cifrurile omofonice sunt mult mai greu de spart decât cele bazate pe substitute simpla, in special atunci când cardinalul mulțimii f(mi) este proporțional cu frecventa caracterului mi. In acest fel se realizează o aplatizare a frecventelor de apariție a diferitelor caractere, îngreunând munca de criptanaliza. In cifrarea omofonica pentru caracterele cu o frecventa de apariție mai mare se creează mai multe posibilități de reprezentare in textul cifrat. De exemplu, in urma unor analize statistice, numărul de apariție a literelor într-un text de limba engleza de 100 000 caractere este: E-12604,T-9042, R-8256, …Q-318, J-198, Z-101.

Pentru literele E ,T si R, având un număr de apariții mai mare, in cifrarea omofonica se creează patru posibilități de reprezentare. Evident, cu cât alfabetul secundar este mai bogat in caractere, cu atât este mai ușoara mascarea caracteristicilor statistice ale textului clar. Fiecare caracter al textului clar poate avea mai multe reprezentări in textul cifrat. Pentru a ilustra acest lucru se considera cazul când alfabetul textului clar este format din 26 de caractere, iar alfabetul secundar conține 210 +1024 de caractere de 10 biți fiecare. Inițial se face ca pentru fiecare litera din alfabetul primar sa corespunda un număr de cifruri direct proporționale cu frecventa de apariție a literei respective in textul considerat. Numărul cuvintelor de cod prin care sunt codificate literele alfabetului primar este:

E-133. I-93, R-85, …,Q-2, J-2, Z-1.

Prin acest sistem de cifrare se realizează ca frecventa de apariție a cuvintelor de cod sa fie aproape constanta.

Substituția polialfabetică

Cifrurile bazate pe substitute polialfabetică constau din utilizarea periodica a unor substituții simple diferite. Fie d alfabete de cifrare C1,C2,…,Cd si d funcții fi care realizează substituția de forma fi:A–>Ci, 1<=i<=d .

Un mesaj clar

M=m1 m2…mdmd+i …m2d…

va fi cifrat prin repetarea secvențelor de funcții f1,…,fd la fiecare al d-lea caracter:

Ek(M)=f1(m1)…fd(md)f1(md+1)

Utilizarea unei secvențe periodice de substituții ale alfabetului, mărește in mod semnificativ securitatea criptogramei prin nivelarea caracteristicilor statistice ale limbii. Aceeași litera din textul cifrat poate reprezenta mai multe litere din textul clar, cu diverse frecvente de apariție. In acest caz numărul cheilor posibile se mărește de la 26!, cate erau la substituția monoalfabetică, la (26!)n

In substituția n-alfabetica caracterul m1 al mesajului clar este înlocuit cu un caracter din alfabetul A1, m2 cu un caracter din alfabetul A2 … mn cu un caracter din alfabetul An. mn+1 din nou printr-un caracter din alfabetul A1 etc., conform tabelului:

CARACTER DE INTRARE: m1 m2 m3 m4 m5 m6 m7 m8 m9 …

ALFABET SUBSTITUTIE: A1 A2 A3 A4 A1 A2 A3 A4 A1 …

O versiune cunoscuta de substitute polialfabetică o constituie cifrul Vigenere, când cheia K este o secvența de litere de forma:

K=k1k2…kd.

Funcțiile fi de substitute se definesc astfel:

fi(a)=(a + ki) (mod n)

unde n este lungimea alfabetului.

Ca un exemplu se considera cheia de opt litere ACADEMIE care va fi utilizata repetitiv pentru cifrarea mesajului SUBSTITUTE POLIALFABETICA.

Folosind o corespondenta biunivoca intre literele alfabetului si elementele inelului claselor de resturi modulo 26 (A=0,B=1,…,Z=25). substituția 8-alfabetica conduce la următorul text cifrat:

TEXT CLAR : SUBSTITUTIA POLIALFABETICA

CHEIA: ACADEMIE

S+A=18+ 0(mod26)=18(mod26)=18=S

U+C=20+ 2(mod26)=22(mod26)=22=W

B+A= 1+0(mod26)=1(mod26)= 1=B

………………………………..

C+E= 2+ 4(mod26)= 6(mod26)= 6=G

A+A=0+ 0(mod26)= 0(mod26)= 0=A

TEXTUL CIFRAT :SWBVXUBYTKESSXQELHAEIFQGA.

Un cifru Vigenere cu o perioada n, deși mult mai puternic decât un cifru bazat pe substituția monoalfabetică, poate fi spart daca criptanalistul dispune de cel puțin 2n caractere din textul cifrat. O varianta mai noua a acestui cifru peste un alfabet binar, este cifrul Vernam care se diferențiază prin cheia de cifrare care este reprezentata de o secvența de caractere aleatoare care nu se repeta.

Fie M=m1m2… un mesaj clar binar si K=k1k2… un sir binar care reprezintă cheia.
Criptograma C=EK(M)=c1c2… se obține determinând fiecare caracter ci astfel:

ci=(mi+ki) (mod n), i=1,2,..

Utilizarea o singura data a cheii ("one time pad") face ca mesajul sa fie foarte rezistent la criptanaliza, practic imposibil de spart; aceste cifruri au o larga utilizare in comunicațiile diplomatice si militare.

Substituția poligramică

Cifrurile bazate pe substitute poligramică realizează substituirea unor blocuri de caractere (poligrame) din textul clar, distrugând astfel semnificația, atât de utila in criptanaliza, a frecventelor diferitelor caractere. Vom considera un mesaj M=m1m2…mdmd+1… si un cifru care prelucrează poligrame de lungime d. Criptograma rezultata este c=c1…cdcd+1…cd+d Fiecare poligrama mi,d+1…mi,d+d va fi prelucrata in poligrama ci,d+1…ci,d+d prin funcția de substitute fi astfel:

ci,d+j=fj(mi,d+1…mi,d+d)

In cazul cifrării literelor singulare frecventa de apariție a literelor in textul cifrat este aceeași cu frecventa de apariție a literelor corespunzătoare din textul clar. Aceasta invarianta a frecventelor furnizează o cantitate de informație suficienta criptanalistului pentru spargerea sistemului de secretizare. Pentru minimizarea informației colaterale furnizate de frecventa de apariție a literelor s-a procedat la cifrarea grupurilor de n litere (N-grame). In cazul când un grup de n litere este substituit printr-un alt grup de N-litere, substituția se numește poligramică. Substituția poligramică cea mai simpIa se obține pentru n=2 când digrama m1m2 din textul clar se substituie cu digrama c1c2 din textul cifrat.

Corespondenta biunivoca dintre digramele m1m2 si c1c2 se poate stabili cu ajutorul unui tabel de forma pătratica. Literele din coloana din stânga pătratului si din rândul dispus deasupra pătratului servesc drept coordonate pentru digrama m1m2 din textul clar, iar digrama cifrata corespunzătoare se scrie la intersecția liniei m1 cu coloana m2 sub forma:

Pentru simplificarea operației de descifrare se poate întocmi "pătratul invers" care in punctul de coordonate c1c2 conține digrama clara m1m2.

Un exemplu clasic pentru substituția digramelor este cifrul lui PLAYFAIR. Metoda consta in dispunerea literelor alfabetului latin de 25 de litere (I=J) intr-un pătrat de cinci linii si cinci coloane de forma:

De regulă, in prima linie a pătratului se scrie un cuvânt cheie si apoi se completează celelalte linii cu literele alfabetului, fără repetarea literelor. Cifrarea se executa după următoarele reguli:

dacă m1m2 sunt dispuse in vârfurile opuse ale unui dreptunghi, atunci c1c2 sunt caracterele din celelalte vârfuri ale dreptunghiului, c2 fiind in aceeași linie cu m1.

De exemplu GS devine MN, deci GS–>MN;

dacă m1 si m2 se găsesc intr-o linie, atunci c1 si c2 se obțin printr-o deplasare ciclică spre dreapta a literelor m1 si m2. De exemplu AD–>BF sau CF–>DA etc.;

dacă m1 si m2 se afIă in aceeași coloana atunci c1 si c2 se obțin printr-o deplasare ciclica a lui m1, m2 de sus in jos. De exemplu UO->BW sau EZ->FE etc.;

pentru separarea liniilor identice alăturate se introduc niște caractere de separare care, de regula, au frecventa de apariție redusa, cum sunt de exemplu literele X,Q in limba romana.

Descifrarea se executa după reguli asemănătoare cu cele de cifrare. O substitute poligramică interesanta este metoda algebrica de cifrare care se bazează pe utilizarea unei transformări liniare de forma:

f(M) = PMT

unde P este o matrice pătratica cu n linii si n coloane, iar M este un vector coloana cu n elemente. Elementele matricei transformării P aparțin inelului Z26, iar elementele lui M sunt echivalente numerice ale n-gramei M=e1.e2,…,en.

In mod analog cu cifrarea si descifrarea digramelor se pot prelucra trigramele, tetragramele sau pentagramele, obținând un spor de securitate prin creșterea rangului matricei de cifrare. Aplicând in mod repetat operația de transformare liniara se obține un cifru-produs definit prin produsul matriceal de forma:

C=P1(P2(…(PkMT)…)

unde matricele Pi,i=1,2….,k sunt matrice inversabile de tipul n x n, iar M=e1,e2…..en este echivalentul numeric al n-gramei.

Cele n litere ale n-gramei-text clar depind de n-grama-cifru, dar daca doua n-grame din textul clar au o litera comuna, de aici nu se poate deduce ca n-gramele-cifru corespunzătoare au o litera comuna si invers. ceea ce conduce la mascarea caracteristicilor statistice ale textului clar.

In cadrul cifrurilor computaționale, folosite in sistemele de securitate ale calculatoarelor, substituția simpIa se realizează prin așa numitele cutii S.

Figura 8 :

Cifruri produs

Un algoritm produs (numit si cifru produs) reprezintă o compoziție a t funcții (cifruri) f1,f2….,ft in care fiecare fi poate fi o substituție sau o permutare. Shannon a propus compunerea in diferite feluri a funcțiilor pentru crearea unor transformări mixte care distribuie in mod uniform mulțimea mesajelor M pe mulțimea tuturor criptogramelor C. Aceste categorii de cifruri-produs se bazează pe rețele de cutii S-P, in care se obține criptograma.

C=EK(M)=StPt-1…S2P1S1(M)
unde fiecare Si este dependenta de o cheie k, parte din cheia cifrului K.

Capitolul III :

Criptografia computațională simetrică

III.1 – Standardul DES

III.2 – Proprietăți ale cifrului DES

III.3 – Critici si slăbiciuni ale standardului DES

III.4 – Alte cifruri simetrice

Standardul DES

Sistemul DES (Data Encryption Standard) este primul standard dedicat protecției criptografice a datelor de calculator. Standardul a fost adoptat in 1977 in SUA si reprezintă o dezvoltare si o perfecționare a sistemului LUCIFER prezentat anterior. DES este un cifru bloc. cu lungimea de 64 biți prelucrați in conjuncție cu o cheie; aceasta este compusa din 56 biți generați aleator si 8 biți folosiți pentru detectarea erorilor de transmisie; fiecare din acești biți reprezintă paritatea impara a celor 8 octeți ai cheii. Prin aceasta modalitate cheia este expandata la lungimea blocului. Aceasta cheie este păstrata de câtre toți membrii unui grup de utilizatori, care astfel pot cifra/descifra datele transmise de la unii la alții.

Cifrarea, prezentata in figura 9 consta din trei categorii de prelucrări care se fac asupra blocului cu text clar de la intrare:

Blocul este mai întâi supus unei permutări inițiale, IP, de forma indicate in tabelul 1. In cazul acestei permutări bitul 58 de la intrare devine primul bit la ieșire, bitul 50 devine al doilea, bitul 42 al treilea s. a. m. d. bitul 7 devine ultimul (al 64-lea).

Tabelul 1 : IP

In continuare blocul permutat trece printr-un calcul complex care depinde de cheie si care consta din 16 iterații funcționale identice. Considerând cei 64 de biți ai unui bloc supus unei iterații i.

Se notează cu Li-1 si Ri-1 cele doua jumătăți de 32 de biți, stânga si dreapta. care-l compun. Fie Ki cheia pentru ciclul i un bloc de 48 de biți aleși din cei 64 de biți ai cheii. Prelucrările unei iterații sunt:

Li=Ri-1

Ri=Li-1+f(Ri-1,Ki).

Cheia Ki corespunzătoare unui ciclu este o funcție de i (numărul iterației) si KEY, șirul de 64 de biți ai cheii inițiale, adică :

Ki = KS(i,KEY)

Cei 48 de biți ai cheii Kj se obțin printr-un procedeu indicat in figura 10.

Figura 9: Sistemul DES de cifrare Figura 10: Generarea cheii pentru iterație

După cum se poate observa, fiecare cheie, supusa unei permutări inițiale P1, este împărțita in doua blocuri de 28 de biți, Ci si Di deplasate la rândul lor cu câte una sau doua poziții la fiecare ciclu.

Tabelul 2 : P1 Tabelul 3 : P2

Intrările Ki sunt supuse din nou unei permutai P2. Cele doua permutări sunt date de tabelele 2 si 3.

Numărul de deplasări la fiecare iterație este cel indicat in tabelul 4.

Tabelul 4

Ultima iterație este puțin diferita de celelalte, fiind definita de ecuațiile:
L16 =R15; R16=L15 + f(R15,K16)

Funcția de cifrare f, "inima schemei", realizează o substitute neliniara printr-un algoritm prezentat in figura 11.

Figura 11 : Schema de realizare a funcției f.

După cum se observa, asupra blocul inițial de 32 de biți se aplica o funcție E care generează 48 de biți la ieșire.

Primii 3 biți sunt cei din pozițiile 32, 1 si 2, iar ultimii sunt cei din pozițiile 32 si 1. Se observa ca biții 4,5,8,9,12,13,16,17,20,21,24,25,28,29,32 se regăsesc de doua ori in expandarea E[R(M)].

Tabelul 6

In continuarea prelucrărilor făcute de funcția f, E(Ri-1) se însumează mod 2 cu cei 48 de biți ai cheii Ki. RezultatuI este partiționat in 8 blocuri de 6 biți care constituie intrările a 8 cutii Sj, j=1,8 care realizează o substitute neliniara cu 6 intrări si 4 ieșiri. Cele 8 cutii a sunt prezentate in tabelul 6.

In cazul unei cutii Sj, daca B este blocul de 6 biți de la intrare, Sj(B) este determinat in felul următor :

Primul si ultimul bit al blocului B reprezintă in binar un număr cuprins intre 0 si 3 (fie acest număr k). Cei 4 biți din mijlocul lui B reprezintă in binar un număr cuprins intre 0 si 15 (fie acest număr I). In tabela Sj, la intersecția rândului k cu coloana I se găsește un număr (cuprins intre 0 si 15) a cărui reprezentare este de 4 biți ce constituie ieșirea cutiei Sj.

Ieșirile celor 8 cutii Sj sunt prelucrate printr-o funcție de permutare, P, cu 32 biți la intrare si 32 la ieșire.

Tabelul 7

Fie S1, S2, … S8 cele opt cutii S, P funcția de permutare si E funcția de expandare prezentate mai sus. Pentru a defini funcția f(Ri-1,Ki) vom preciza mai întâi blocurile B1, B2, … B8, de 6 biți fiecare, ca fiind: B1B2…B8=K+E(Ri-1).
In acest caz blocul f(Ri-1,Ki) poate fi definit ca:

f(Ri-1,Ki) = P(S1(B1) S2(B2) … S8(B8))

După calculul complex format din cele 16 iterații descrise anterior, blocul de 32 de biți este supus unei permutări IP-1, inversa celei inițiale.

Tabelul 8 : IP-1

Descifrarea consta in folosirea aceluiași algoritm, dar cu cheile K, aplicate in sens invers, de la K16 la K1. Primul pas in descifrare este aplicarea permutării IP, care dezleagă ultimul pas IP-1, din operația de cifrare. Apoi se va genera in sens invers:

Ri-1 = Li;

Li-1 = Ri+f(Li,Ki).

Se va pleca de la R16 si L16, generându-se la sfârșit R0 si L0. In final blocul de 64 de biți este supus unei permutări inverse. IP-1.

Proprietăți ale cifrului DES

Efectul de avalanșă :

Daca o mica schimbare a cheii sau a mesajului-clar va produce doar o mica schimbare in textul-cifrat, aceasta ar însemna reducerea efectiva a dimensiunii spațiului cheii sau mesajului ce ar trebui emulate exhaustiv. in consecința una din cerințele de baza ale unui bun algoritm este de a produce mari schimbări in textul cifrat in urma unor mici modificări ale textului clar sau ale cheii. DES satisface aceste proprietăți.

Mayer a arătat ca după cinci iterații, fiecare bit al textului cifrat depinde de toți biții mesajului si ai cheii. Aceasta proprietate poate fi folosita in scopul detectării unor erori sau al autentificării. Efectul poate fi pus in evident folosind 2 mesaje in clar care diferă doar prin prima poziție:

X =(11111111 11111111 …11111111)

X'= (01111111 11111111 … 11111111)

Complementaritatea

DES este invariant la complimentarea mesajului clar, al cheii si a textului cifrat:

DESK(X) = DESK’(x').

unde K' si X' reprezintă complementele fata de 1 ale lui X si K. Aceasta proprietate de complementaritate rezulta din modul in care sunt folosite subcheile interne in fiecare iterație.

Analiza lui DES arata ca versiunea expandata a celor doua parți, dreapta si stânga. ale mesajului clar sunt supuse unui proces complicat împreuna cu cheia Ki a iterației i. marcat de funcția f.

f[Ri,Ki+1]=f[E(Ri)+Ki+1]

unde E reprezintă expandarea lui Ri de la 32 de biți la 48 de biți.

Complementînd atât Ri cat si Ki+1, nu se schimba valoarea lui f:
f[Ri,Ki+1]=f[R'i,K'i+1].

Insa R0 si L0 provin din X iar complementarea lui K înseamnă complementarea tuturor subcheilor K1, K …, K16. Aceasta proprietate de complementaritate reduce spațiul de căutare exhaustiva a unei chei de la 2^56 la 2^55. Daca criptanalistul deține Y1 = DESK(X) si Y2 = DESK(X') pentru un mesaj oarecare X, el va cifra mai întâi pe X cu toate cele 255 chei care încep cu '0'. RezultatuI cifrat se compara cu Y1 si cu Y2.

Daca CY'2 cheia nu este K'. Aceasta simetrie reduce efortul de căutare la jumătate, testându-se simultan 2 chei, K si K'. Complementaritatea ar putea fi înlăturata din algoritm daca s-ar înlocui suma modulo 2 cu cutii S comandate de biți ai cheii.

Critici si slăbiciuni ale standardului DES

Controversele privind standardul DES provin din următoarele considerente:

dimensiunea mica a spațiului cheilor;

nepublicarea principiilor de proiectare a algoritmului;

numărul de iterații;

algoritmul de generare a cheilor.

Alte critici se refera la permutările redundante IP si IP-1

Pentru investigarea acestor critici, NBS (National Bureau of Standards) a organizat 2 congrese. Primul a fost dedicat complexității algoritmului si s-a ajuns la concluzia ca nu exista metode de scurtcircuitare a lui. Al doilea congres a concluzionat ca nu este posibila, construirea unui calculator dedicat căutării cheilor si acesta va costa mai multe sute de milioane de dolari.

Criticile susțin ca lungimea cheii este prea mica astfel încât spațiul cheii este vulnerabil la căutare exhaustiva. Diffie si Hellman au ajuns la concluzia ca încercarea tuturor cheilor posibile nu este economic posibila si estimează costul unei căutări exhaustive la aproximativ 5.000 $ pe calculatoare special destinate – adică mașini care conțin milioane de chip-uri LSI si care pot încerca toate cele 256 chei intr-o zi. Insa costul unei astfel de mașini se estimează la 200,000 de dolari, iar costul unei chei la 50 dolari. De aici concluzia si sugestia exprimata ca se poate defini o securitate sporita doar daca lungimea cheii este mai mare de 128 biți. Vom observa insă ca spațiul cheilor se reduce dramatic daca folosim drept chei șiruri de caractere ASCII (doar 648 testări necesare pentru determinarea cheii). De asemenea spațiul căutării cheii se poate reduce si prin folosirea proprietarii de complementaritate.

Nepublicarea principiilor de proiectare reprezintă o altă critica majora adusa DES-ului. Anumiți parametri, cum ar fi alegerea cutiilor S, permutării P si algoritmul cheii nu sunt justificați de NBS. In aceste circumstanțe exista suspiciunea ca standardul are incorporate in algoritm anumite "trape" care pun proiectantului in avantaj, creându-i posibilitatea spargerii cifrului, s-au descoperit anumite structuri regulate ale algoritmului care par surprinzătoare. La fel ca proprietatea de complementaritate, este posibil sa se reducă pana la 75% din timpul de căutare exhaustiva a cheii cu niște cutii a alese "cu grija". Deocamdată insa, deși s-au găsit unele proprietăți ciudate ale cutiilor S, nu s-a reușit elaborarea unei tehnici criptanalitice evidente.

Numărul de iterații reprezintă un alt motiv de critica la adresa lui DES si se sugerează creșterea la cel puțin 32 a lor. Numărul de iterații duce la creșterea gradului de mixare a variabilelor de intrare si de difuziune introdus de permutări. O creștere a iterațiilor produce un efect crescut de avalanșa si o dispariție a corelațiilor care se pot face intre ieșiri si intrări.

Algoritmul de generare a cheilor pentru iterații este destui de slab, dar tăria criptografica scade in situațiile când 2 sau mai multe subchei sunt identice. O situate critica apare când toți biții blocului C sunt identici si toți biții lui D sunt identici. In acest caz exista 4 astfel de chei slabe care au proprietatea ca nu exista diferența intre operațiile de cifrare si descifrare:

DESK(DESK'(X))=X=DESK'(DESK(X)).

unde K si K' sunt 2 astfel de chei.

Puterea algoritmului de generare poate fi sporita prin incorporarea unor neliniarității in procesul descris. in acest caz este indicate existent unei chei extreme care sa fie introdusa intr-un proces de substituții – permutări in cadrul fiecărei iterații, pentru obținerea cheii interne care apoi sa urmeze algoritmul obișnuit de generare.

Tot in contextul analizei standardului DES se ajunge la concluzia ca in cazul unei chei slabe cifrul nu este pur. Reamintim ca un cifru este pur daca pentru orice chei Ki, Kj. Kk exista o cheie Kl astfel ca DESKiDES-1KjDESKk = DESKl.

Alte cifruri simetrice

FEAL – Japanese Fast Data Encryption Algorithm este un algoritm simetric care cifrează blocuri de 64 de biți, folosind o cheie de 64 de biți. Cele mai importante variante ale acestei propuneri de standard sunt FEAL-1, FEAL-4 si FEAL-8. Extensiile lui FEAL-1 sunt FEAL-4 si FEAL-8 cu 4 respectiv 8 iterații.

PES – Proposed Encryption Standard este un cifru înrudit cu DES compus din 8 iterații. S-a constatat, in urma studiilor de atac diferențial făcute, ca PES, la fel ca DES, este un cifru Markov. Prin estimarea probabilităților diferențiale a r iterații se arata ca 2 iterații PES sunt cel puțin la fel de sigure ca 10 iterații DES la atac diferențial iar 4 iterații PES sunt invulnerabile la un astfel de tip de atac.

TEA – Tiny Encryption Algorithm este unul din cele mai rapide si cele mai eficiente cifruri. A fost creat de David Wheeler si Roger Needham de la Cambridge University. Este un cifru Feistel care criptează blocuri de 64 biți utilizând o cheie de 128 biți. Este foarte rezistent la criptanaliza diferențiala si are o dispersie a biților completa după numai sase iterații. O diferența de un bit in textul clar produce aproximativ 32 diferențe in textul cifrat.

Propuneri pentru AES (Advanced Encription Standard), care va fi noul standard de criptare si care va înlocui DES

MARS – Propus de IBM este opus celorlalți competitori prin noutatea proiectării lui. MARS folosește chei de pana la 448 de biți si consta in 16 iterații, nucleul criptografic constând in 8 straturi de împrăștiere circulara . Scopul straturilor de împrăștiere circulara consta in obținerea difuziei biților, iar nucleul este proiectat sa reziste la cele mai cunoscute tipuri de atacuri. Datorita pretinsei complexități a algoritmului, securitatea cifrului MARS este dificil de estimat.

RC6 – Propus de RSA Laboratories, RC6 e un cifru parametrizat, rapid si simplu bazat pe predecesorul sau, RC5. Propunerea pentru AES consta in 20 iterații care se pretind a fi un pic cam lente si nesigure, deși nu s-au găsit pana acum breșe de securitate. Algoritmul nu poate fi potrivit pe anume platforme datorita folosirii rotației pe 32 de biți a variabilelor si multiplicarea întreaga, dar când aceste operații sunt acceptate, RC6 este cel mai rapid dintre candidați.

Rijndael – Propus de Joan Daemen si Vincent Rijmen, Rijndael se bazează pe algoritmul Square si a primit credit pozitiv in raportul preliminar de la NIST (National Institute of Standards and Technology). Cifrul este rapid, simplu, si sigur. Pentru moment, Rijndael pare a nu avea dezavantaje majore in comparație cu alți candidați. In versiunea de 128 biți, Rijndael consta in 10 iterații si la fiecare iterație biți individuali sunt transformați, liniile matricei sunt rotite si coloanele sunt multiplicate cu diverse constante. Fiecare iterație se termina cu o transformare logica a tabloului rezultat cu o cheie.

Serpent – Propus de Ross Anderson, Eli Biham si Lars Knudsen, consta in 8 cutii S bazate pe cutiile S ale lui DES, si cele 32 de iterații sunt de doua ori mai multe decât necesare pentru a atinge cerințele cifrului AES. Aceasta face din Serpent un cifru puternic, dar prețul pe care algoritmul trebuie sa-l plătească este o performanta mai mica decât celelalte cifruri finaliste pentru AES.

Twofish – Propus de Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, si Niels Ferguson, Twofish se bazează pe algoritmul Blowfish al lui Schneier. Twofish e o rețea Feistel rapida si versatila care nu necesita multa memorie. Structura algoritmului este totuși complexa si greu de analizat, ceea ce face ca cifrul Twofish sa fie similar cu MARS, dar Twofish are avantajul ca se bazeaza pe un algoritm deja studiat.

Capitolul IV :

Criptografia computațională cu chei publice

IV.1 – Sistem criptografic cu chei publice

IV.2 – Teste de primalitate

IV.3 – Sisteme de cifrare cu chei publice exponentiale

IV.4 – Cifrul RIVEST-SHAMIR-ADLEMAN

IV.5 – Aspecte de implementare ale algoritmilor exponențiali

IV.6 – Sisteme de cifrare cu chei publice de tip rucsac

Sistem criptografic cu chei publice

ConceptuI de sistem criptografic cu chei publice (sau cu doua chei) a fost fundamentat teoretic de Diffie si Hellman care au propus o noua metoda de cifrare in care fiecare utilizator deține 2 chei: una publica si una secreta, imposibil de dedus pe baza celei publice. intre oricare doi utilizatori se poate comunica confidențial cunoscându-se de către fiecare doar cheia publica a partenerului.
In sistemele cu chei publice fiecare utilizator A are o transformare publica EA care poate fi înregistrat si intr-un fișier public si o transformare secreta DA, cunoscuta doar de proprietar. Transformarea publica (numita si cheie publica) a destinatarului permite cifrarea mesajelor care-i sunt adresate.

Cu ajutorul transformării secrete (numita si cheie secreta) destinatarul (si numai el) poate descifra mesajul recepționat. Folosirea cheii secrete permite crearea si a unor semnături digitale care sa ne asigure asupra autenticității mesajelor. Aceste criptosisteme cu chei publice se bazează pe o serie de metode matematice de mare complexitate, in aritmetica numerelor mari (de obicei cu 256-512 biți) a căror implementare se face cu dificultate.

Complexitatea deosebita a metodelor criptografice, atât simetrice cat mai ales a celor cu chei publice care cer efectuarea unor operații aritmetice cu un număr mare de biți, operații in câmp finit, calculul unor operatori algebrici (ex. Jacobi sau Legendre), generării de numere prime mari, calculul c.m.m.d.c. si al inversului multiplicativ sau aditiv al unor numere foarte mari duce la implementarea unor funcții speciale si a algoritmilor acestora. Trebuiesc definite funcțiile SUMA (realizează suma a doi operanzi pe 512 biți, returnând valoarea 0 daca nu a existat depășire si 1 in caz contrar), DIF (realizează diferența a doi operanzi pe 512 biți), COMP (realizează compararea a doi operanzi pe 512 biți, returnând valoarea -1 daca Op1 < Op2, 0 daca Op1 = Op2 si 1 daca Op1 > Op2), MODULO (realizează operația modulo prin scăderi repetate. Este utila in cazul când operanzii sunt comparabili ca ordin de mărime), FASTMOD (realizează operația modulo pe baza unui algoritm rapid), AMULB (realizează înmulțirea modulo a doi operanzi de până la 512 biți), înmulțirea modulo 2n-1, exponențierea modulo 2n-1, invers multiplicativ si algoritmi de calcul al c.m.m.d.c., calculul operatorului Jacobi, diverse teste de primalitate si altele.

Teste de primalitate

O mare parte din algoritmii criptografici (in special cei cu chei publice – RSA, EIGamal, Merkle si Hellman) au nevoie de generatoare de numere prime mari (128,256,512 biți) care nu pot fi găsite in tabele matematice. Ca urmare este nevoie sa se implementeze programe de generare de numere prime si de testare a primalității. Testele folosite cel mai adesea pentru generarea unor numere prime mari sunt:

testul Fermat se bazează pe teorema Euler-Fermat. Ea spune ca p este număr prim daca: ap-1 = 1 (mod p), oricare a, a[1, p). In acest fel testul consta in alegerea unui a mai mic ca p si acceptarea ca p este prim daca se satisface condiția de mai sus. in practice este necesara testarea doar a câtorva valori ale lui a si nu toți a din mulțimea (1,p). Este recomandabil ca aproximativ o suta de teste sa fie făcute pentru a fi convinși ca numărul p ales este prim.

Testul Solovay – Strassen identifica numerele Carmichael compozite. Se alege aleator un număr a(1,p-1) si se testează daca: cmmdc (a,p) = 1 si J(a,p) = a^(p-1)/2 (mod p) unde J(a,p) este simbolul Jacobi. Daca p este prim atunci el verifica cele doua condiții iar daca este compozit, verificarea se face doar cu o probabilitate de 1/2. Insa făcând k teste, probabilitatea de apreciere eronata scade la 2-k.

Testul Rubin reprezintă un test probabilist. Pentru ca un număr p sa fie prim, trebuie sa fie un întreg impar, deci poate fi reprezentat ca: p=2r*s+1, unde s este un întreg impar. Testul alege un număr de valori a in mod aleator din intervalul (1,p-1) si accepta ca p este prim daca fie as = 1 (mod p) fie (a2*j)s = -1 (mod p) pentru a<j<r. In celelalte cazuri p este respins.

Testul probabilist : Fiind dat un întreg impar n acest algoritm urmează sa decidă daca n este prim sau nu. Prin repetarea de mai multe ori a algoritmului este posibila o decizie extrem de sigura privind primalitatea lui n. Ideea pe care se bazează algoritmul este ca daca n = 2k*q este prim si Xq (mod n) 1 atunci șirul de valori: Xq (mod n), X2*Q (mod n),…. X2^k*q (mod n) se va sfârși cu 1 iar valoarea care precede imediat prima apariție a lui 1 va fi n-1. Singurele soluții pentru y2 = 1 (mod p) sunt y = 1 si y = -1 daca p este prim, deoarece (y-1)*(y+1) trebuie sa fie multiplu de p. Algoritmul se apelează repetat alegându-se n in mod independent si arbitrar ori de câte ori se intra in primul pas. Daca algoritmul anunța cel puțin o data ca n nu este prim, atunci putem spune sigur ca n nu este prim. Dar daca algoritmul anunța de 25 de ori ca n este probabil prim, putem spune ca n este aproape sigur prim.

Toate cele patru teste determina, cu o anumita probabilitate, daca un număr p este sau nu prim. Sa observam totuși ca verificarea primalității cere un serios efort computațional, de ordinul a*log2(p) operații.

Sisteme de cifrare cu chei publice exponențiale

Sistemele criptografice cu chei publice sunt de tip asimetric. Ele au fost dezvoltate pornind de la lucrările de referința ale lui Diffie si Hellman. Ideea care sta la baza acestui concept consta in faptul ca procedura (cheia) de cifrare este făcuta publica de către fiecare utilizator si poate fi folosita de toți ceilalți utilizatori pentru cifrarea mesajelor ce ii sunt adresate. In schimb procedura (cheia) de descifrare, diferita de prima (de unde atributul de sistem asimetric) este ținuta secreta. Daca notam cu {M} mulțimea mesajelor, {C} mulțimea criptogramelor, E – procedura de cifrare si D – procedura de decifrare, un criptosistem cu chei publice trebuie sa satisfacă următoarele cerințe:

daca C = E(M), atunci M = D(C) sau D(E(M)) = M. M {M}

E si D sunt usor si rapid aplicabile;

dezvăluirea publica a lui E nu trebuie sa compromită pe D, ceea ce înseamnă ca obținerea lui D din E este matematic imposibila sau presupune un consum prohibitiv de resurse.

Metoda propusa permite comunicații sigure intre utilizatori care nu au stabilit contacte prealabile. De exemplu daca utilizatorul A dorește sa transmită un mesaj confidențial utilizatorului B, A va căuta in fișierul public EB si va transmite la B: C=EB(M). Conform proprietății a treia, B este singurul utilizator care știe sa descifreze criptograma C aplicând DB ținuta secreta. In plus, pentru ridicarea gradului de securitate al transmisiei, Diffie si Hellman propun ca E si D sa îndeplinească si următoarea proprietate adiționala:

daca S = D(M), atunci M = E(S) sau E(D(M)) = M pentru oricare M{M}.
Valoarea S este numita semnătura digitala si reprezintă o metoda de autentificare reciproca. In timp ce B poate fi sigur ca mesajul recepționat a venit de la adevăratul A, prin semnarea mesajelor sale, A poate fi sigur ca nimeni nu va putea sa-i atribuie un mesaj fals. Utilizatorul A poate semna mesajul către B astfel: S=DA(M) si apoi trimite criptograma: C = EB(S).

In aceste condiții numai B poate recunoaște pe S din C calculând: DB(C) = DB(EB(S)) = S. Apoi mesajul se obține calculând:

EA(S) = EA(DA(M)) = M.

Diffie si Hellman sugerează o metoda de implementare practica a conceptului propus. Se indica utilizarea unor funcții greu inversabile ("one-way functions"). Ele își au originea in probleme grele din punct de vedere computațional. O funcție este greu inversabila daca este inversabila si ușor de calculat, dar pentru aproape toate valorile y din codomeniu este imposibil computațional sa se calculeze x = f-1 (y). Cu alte cuvinte este imposibil computațional sa se calculeze f-1 daca se dispune de o descriere completa a lui f.

In concluzie, o funcție este greu inversabila daca:

Este ușor sa calculeze y din x, y = f(x);

Exista inversa funcției;

Este computațional imposibila determinarea inversei funcției.

O funcție greu inversabila se spune ca este cu trapa atunci când f-1 este ușor de calculat numai daca se dispune de o informație numită trapă; necunoașterea acestei informații face ca funcția sa fie greu inversabila. O astfel de pereche de funcții (f, f-1) poate constitui perechea (E, D) a unui criptosistem cu chei publice. In general, pentru procedurile E si D se indica scheme bazate pe operații modulo n cu elemente din inelul claselor de resturi modulo n.
Schema propusa își bazează securitatea pe dificultatea calculului logaritmilor modulo număr prim. Fie q un număr prim si un întreg X, X [1, q-1]. Se poate calcula: Y = a x (mod q), unde a este un element primitiv al câmpului Galois GF(q).

După cum se știe, clasele de resturi modulo q formează un inel; daca q este un număr prim acestea formează un câmp Galois GF(q). Intr-un câmp GF(q) exista (q-1) numere a care se numesc elemente primitive ale câmpului. Daca a, a2 , a3 ,…, a(q) sunt puterile lui a, acestea au ca resturi mod q pe 1, 2, …, (q), ceea ce înseamnă ca un element primitiv generează prin ridicare la putere toate elementele nenule ale câmpului. S-a notat cu (q) = indicatorul lui Euler, (q)= q-1. Fiecare utilizator A alege in mod aleator un număr XA , XA{1. 2, …, q-1} si calculează YA = aXA (mod q). Numărul XA este ținut secret, in timp ce YA se face public. Daca utilizatorii A si B doresc sa comunice intre ei se utilizează următoarea cheie de comunicație:

KAB=YAXB=YBXA = aXAXB (mod q).

In timp ce utilizatorii A si B pot calcula cheia KAB pornind de la X propriu (secret) si Y public al partenerului, un criptanalist trebuie sa calculeze pe KAB pornind de la YA si YB , singurele făcute publice procedând astfel:

KAB = YAlogYB (mod q).

Acest lucru face ca sistemul sa fie deosebit de greu de spart datorita imposibilității calcului logaritmului modulo q. Calitatea fundamentala a sistemului este ca nu necesita stabilirea in avans a unei chei secrete de cifrare intre doi utilizatori ai unei rețele care doresc sa comunice date confidențiale; ei fac apel doar la fișierul de chei publice. Descifrarea mesajelor nu se poate face insa pe baza cheilor din fișierul public, ci doar pe baza perechilor lor, ținute secrete de către fiecare utilizator. Criptosistemele cu chei publice fac parte din clasa sistemelor criptografice sigure computațional.

Începând din anul 1979 s-au căutat o serie de funcții care sa satisfacă cerințele impuse de sistemul cu chei publice. Acestea se bazează pe schemele unor probleme foarte greu de rezolvat la nivelul cunoștințelor matematice de azi, cum ar fi factorizarea unui produs de numere prime foarte mari, găsirea logaritmului modulo număr prim intr-un câmp mare, cu respectarea unui element primitiv, problema rucsacului etc.

Cifrul RIVEST-SHAMIR-ADLEMAN

Acest cifru cu chei publice, realizat de cei trei cercetători de la Massachusetts Institute of Technology, reprezintă standardul "de facto" in domeniul semnăturilor digitale si al confidențialității cu chei publice. El se bucura de o foarte mare apreciere atât in mediul guvernamental cit si in cel comercial, fiind susținut prin lucrări si studii de comunitatea academica. Sub diferite forme de implementare, prin programe sau dispozitive hardware speciale, RSA este astăzi recunoscuta ca cea mai sigura metoda de cifrare si autentificare disponibila comercial. O serie de firme producătoare de sisteme de programe si echipamente ca DEC, Lotus, Novell. Motorola precum si o serie de instituții importante (Departamentul Apărării din SUA, National Aeronautics-SUA, Boeing. rețeaua bancara internaționala SWIFT, guvernul Belgiei etc.), folosesc acest algoritm pentru protejarea si autentificarea datelor, parolelor, fișierelor, documentelor memorate sau transmise prin rețele. De exemplu firma Lotus dezvolta Notes, un nou concept de lucru in comun (groupware) intr-o rețea. La o astfel de legătura in comun a numeroase programe si persoane se cere insa o mare încredere in informație cat si o mare confidențialitate; ca urmare Lotus folosește semnătura digitala si secretizarea cu ajutorul criptosistemelor RSA. In sistemul de operare NetWare, pentru rețele locale, al firmei Novell se folosește curent RSA in mecanismele de autentificare care permit utilizatorilor sa acceadă la orice server al rețelei. Motorola comercializează telefoane sigure care incorporează o serie de metode de confidențialitate si autentificare a utilizatorilor cat si a partenerilor de dialog. Toate acestea se bazează pe algoritmul RSA si se regăsesc atât in variante de uz general cat si in variante pentru comunicații militare, fiind destinate atât transmisiilor de voce cit si de fax.

Un alt exemplu semnificativ de utilizare a sistemului RSA este rețeaua de posta electronica a guvernului belgian. Toate protocoalele de asigurare a confidențialității si de autentificare prin semnătura digitala folosesc acest algoritm. Sistemul RSA este de tip exponențial. In cadrul acestei metode modulul n este obținut prin produsul a doua numere prime mari: n=p*q, astfel încât indicatorul lui Euler (n)=(p-1)*(q-1), devine mult mai greu de determinat, iar schema poate fi folosita cu succes intr-un criptosistem cu chei publice; se vor face publice e si n, iar d va fi ținut secret. In privința metodei se recomanda alegerea unui d relativ prim cu (n) in intervalul [max.(p,q)+1, n-1]. In acest caz e se va calcula astfel: e = inv (d, <>FI<>(n)). putându-se utiliza o versiune extinsa a algoritmului lui Euclid.
Securitatea metodei depinde de dificultatea factorizării lui n in p si q. Cel mai rapid algoritm publicat de Schroeppel, cere un număr de pași egal cu: T = exp(sqrt(ln(n)*ln(n)))) același cu cel al calculului logaritmului in câmpul GF(n).
Rivest, Shamir si Adleman sugerează utilizarea unor numere prime p si q de 100 cifre, adică a unui n de 200 de cifre, ceea ce cere pentru factorizare mai multe milioane de ani. Deoarece cifrarea si descifrarea sunt funcții mutual inverse, metoda RSA poate fi utilizata atât la secretizare, cat si la autentificare. Fiecare utilizator A obține modulul nA si exponenții eA si dA. Apoi A va înregistra intr-un fișier public cheia publica (nA, eA), in timp ce va tine secreta pe dA. Un alt utilizator B va putea emite un mesaj secret M utilizând transformarea de cifrare publica a lui A:

EA(M)=MeA mod nA

La recepție A va obtine mesajul m clar:

DA(EA(M))=MeAdA mod nA = M.

Utilizatorul A va putea semna un mesaj M către B calculând:

DA(M) = MdA mod nA,

iar B va autentifica acest mesaj, utilizând cheia publica a lui A:

EA(DA(M))=MdAeA mod nA = M.

Sa consideram un mic exemplu care sa ilustreze acest algoritm:
Fie p=53 si q=61 doua numere prime; produsul acestor doua numere ținute secrete este n=53*61=3233 iar (n)=(p-1)*(q-1)=52*60=3120. Fie d =791 cheia secreta; exponentul e (cheia publica) se calculează ca invers multiplicativ mod 3120 a lui d. Ca urmare e=71. Pentru a cifra mesajul, M=RENAISSANCE, acesta se va împarți in blocuri de 4 biți fiecare. unde A=00, B=01,C=02….Z=25 si blanc=26 M=RE NA IS SA NC E =1704 1300 0818 1800 1302 1426.
Primul bloc se va cifra ca 1704^71 mod 3233 =3106,etc.

Criptograma obținuta devine: C=3106 0100 0931 2691 1984 2927.

La descifrare. fiecare grup de doua litere in clar se obține folosindu-se cheia secreta d: 3106791 mod 3233=1704,etc. 0 dificultate in utilizarea criptosistemelor RSA apare atunci când este nevoie atât de protecție cat si autentificare, deoarece este necesar sa se aplice transformări succesive cu module diferite. De exemplu, pentru ca A sa transmită la B un mesaj semnat si secret, A va calcula: C = EB(DA(M)). Daca nA>nB blocul DA(M) nu mai aparține mulțimii [0, nB-1] corespunzătoare lui EB. Reducerea lui DA(M) mod nB nu rezoIvă problema, nemaiputându-se apoi obține mesajul original. Soluția consta in utilizarea unui prag h (de exemplu h = 1099) astfel încât fiecare utilizator sa execute doua perechi de transformări: (EA1 , DA1 ) pentru semnătura si (EA2,DA2) pentru protecție, respectând condiția: nA1<H<nA2

In acest caz la transmiterea unui mesaj semnat si secretizat la B, A va calcula:

C = EB2 (DA1(M));

deoarece nA1 < h < nB2, problema este rezolvata.

Utilizatorul B va obține pe M verificând si semnătura:

EA(DB(c)) = EA1(DB2(EB2(DA1(M)))=EA1(DA1(M))=M.

O alta soluție in situația in care C = EA(DA(M)) nu este calculabila, deoarece nA >nB, este indicata de Konfelder. El recomanda sa se calculeze C' = DA(EB(M)), observând ca aceasta este calculabila. Utilizatorul, B, care cunoaște atât nA. cat si nB, poate obține pe M in doua moduri:

daca nA < nB EA(DB(C)) = EA(DB(EB(DA(M))))=EA(DA(M))=M.

daca nA > nB DB(EA(C'))= DB(EA(DA(EB(M))))=DB(EB(M))=M.

Când apare o disputa intre A si B asupra autenticității semnăturii lui A un "judecător" va trebui sa fie capabil sa stabilească daca M aparține lui A:

daca nA < nB, B va aplica transformarea sa secreta asupra lui C si va prezenta "judecătorului" X = DB(C) si pe M. "Judecătorul" va calcula M' = EA(X), folosind transformarea publica a lui A si va verifica daca M'=M;

când nA > nB, B se va prezenta la "judecător" cu C' si M. "Judecătorul" va calcula: X = EB(M);
X'= EA(C') = EA(DA(EB(M))) si va verifica daca X=X'.
Se observa ca protocolul nu cere ca A sau B se dea "judecătorului" cheile (transformările lor secrete). Pentru reducerea dimensiunii semnăturii se sugerează comprimarea mesajului printr-o funcție de hashing si apoi semnarea rezultatului.

RSA își capătă securitatea prin presupusa greutate de factorizare a numerelor mari. Deci trebuie găsita o metoda de generare a numerelor prime mari. Cea mai simpla metoda de generare a numerelor prime mari este de a genera numere impare mari si a verifica daca sunt prime. De fapt sunt o infinitate de numere prime mari. Teorema numerelor prime mari da o aproximare folositoare pentru funcția PI(n); care specifica împrăștierea numerelor prime mari

Deci n/ln(n) da o aproximare cu o precizie rezonabila densitatea de numere prime mai mici sau egal cu n Sunt 17 numere prime de la 1 la 60. 60/ln(60)=14,65 Deci exista o eroare de 8%.

Pentru a testa un număr candidat (n) daca este prim se poate încerca o metoda simpla si evidenta, împărțirea prin încercări, in care se încearcă daca n se împarte exact (fără rest) fără rest la întregi intre 2 si √n. Daca n este prim nici un întreg nu s-ar împărți exact. Timpul necesar acestei metode creste exponențial.

Împărțirea prin încercări are avantajul ca ne spune cu certitudine 100% ca n e prim sau nu, dar necesita un timp mare de rulare.

Pentru a testa candidații netriviali se folosește des testele de pseudoprimalitate. Pseudo – primalitatea testează cu un anume grad de acuratețe daca un număr e prim. Pentru testare se folosesc testul celor patru numere ale lui Fermat.

Testul celor patru numere ale lui Fermat se realizează astfel:

Candidatul la testare : n.

Se iau primele 4 numere prime : b{2,3,5,7}

Se ia bn-1 (modulo n) = w

Daca w=1 pentru orice b atunci n e probabil prim, altfel pentru orice alt număr n sigur nu e prim.

Posibilitatea ca un număr declarat prim de algoritmul celor 4 numere ale lui Fermat e foarte mica. După fiecare test posibilitatea ca sa nu fie prim scade dramatic. După un test este de 1 in 1013, după doua de 1 in 1026 iar după cele 4 teste este de 1 in 1056.

Din nefericire exista numere neprime care satisfac ecuația bn-1 (modulo n). Acești întregi sunt cunoscuți ca numerele lui Carmichael, care sunt destul de rare (pentru ca trebuie sa nu fie divizibile cu pătratul niciunui număr prim si sa fie produsul a cel puțin 3 numere prime). Ele sunt doar 255 mai mici ca 109.

Aspecte de implementare a algoritmilor exponențiali

Proiectarea unor criptosisteme RSA pleacă de la alegerea unor numere prime mari p si q pe baza cărora se calculează modulul n. Dimensiunea acestor întregi este esențiala in asigurarea tăriei criptografice a schemei. Următorul tabel da o indicație a legăturii dintre dimensiunea lui n si numărul de operații necesare, in cel mai bun algoritm publicat, pentru factorizarea lui n:

Tabelul 9

Odată aleasa dimensiunea lui n, cei doi întregi p si q trebuie aleși pseudo aleator. Teorema numerelor prime arata insa ca doar (In(n)) întregi pot candida la statutul de numere prime mai mici ca n. Pentru un n de mai multe sute de cifre. numai câteva sute de "candidați" trebuie sa fie testați pentru a găsi un număr prim. Pentru o mai buna protecție împotriva factorizării, trebuie luate si următoarele masuri suplimentare:

p si q trebuie sa difere in lungime prin câțiva biți;

atât (p-1) cat si (q-1) trebuie sa conțină factori primi mari;

c.m.m.d.c (p-1, q-1) trebuie sa fie mic.

Pentru a găsi un număr prim p astfel ca (p-1) sa aibă un factor prim mare, se va genera mai întâi un întreg aleator p'. iar apoi se calculează: p=p'*i+1 .i= 2,4,6,… , pana când p este prim. O protecție suplimentara se poate obține daca alegem p' astfel ca (p'-1) sa aibă un factor prim mare.

O alta problema importanta consta in alegerea exponenților e si d. Având aleși întregii p si q, si deci n=p*q, exponenții e si d trebuie sa satisfacă condiția:

e*d = 1 mod (n).

Se alege întâi un întreg d>max. (p, q) din mulțimea de întregi relativi primi si mai mici ca (n). Este de asemenea necesar ca atât d cat si e sa fie mai mari ca log2(n), deoarece acest lucru ar face ca Xe (mod n) = X si astfel cifrul sa fie ineficient.

Alegerea lui e, 0 < e < (n) se face astfel încât el sa reprezinte inversul multiplicativ mod (n) al lui d. Acest lucru se poate realiza folosind o variație a algoritmului lui Euclid.

Sisteme de cifrare cu chei publice de tip rucsac

Problema rucsacului este următoarea: cunoscând greutatea unui rucsac închis si greutățile mai multor obiecte care s-ar putea afla in interiorul sau, sa se determine setul de obiecte aflate in rucsac, fără a se face deschiderea lui.
Aceasta problema este NP completa. Cel mai bun algoritm cunoscut pentru rezolvarea ei – in cazul in care dimensiunea rucsacului este n – cere 0 (2^n/2) timp si 0 (2^n/2) memorie.

Exista totuși o clasa speciala de probleme de un asemenea tip, numita cu "rucsac simplu" ce pot fi rezolvate intr-un timp linear.

Merkle si Hellman propun o metoda a cărei securitate depinde de dificultatea rezolvării următoarei probleme: Fiind dat un întreg pozitiv C si un vector A=(a1,a2,…,an) de întregi pozitivi, sa se găsească un subset al lui A a cărui suma sa fie C. Cu alte cuvinte este necesar sa se determine un vector binar M=(m1,…,mn), astfel ca C=AM sau: C= aimi.

Algoritmul Merkle Hellman cu trapa aditiva

In proiectarea unui astfel de criptosistem trebuie convertit "rucsacul simplu" intr-un "rucsac cu trapa", care este greu de rezolvat. Mai întâi se selectează un vector "rucsac simplu" A'=(a1',a2',..,an'). Acesta permite o soluție simpla a problemei, C'=A' * M. Apoi se alege un întreg n astfel ca: n > 2an' >ai' , i=1,n.
In continuare se alege un alt întreg w, astfel ca c.m.m.d.c(n,w)=1 si se calculează inversa lui w mod n. In final vectorul A' este transformat intr-un vector "rucsac greu"

A=wA' (mod n): ai = w ai' (mod n)

Acum rezolvarea problemei C=AM este dificila, daca nu se dispune de o informatie "trapa" (inversa lui w si n), cu ajutorul careia calculul se simplifica:

C'=w-1C (mod n)

= w-1AM (mod n)

=w-1(wA')M (mod n)

= A'M (mod n)

=A'M.

Transformarea de cifrare EA (publica) folosește cheia publica care este vectorul "rucsac greu" A.

Se obține criptograma

C = EA(M) = AM

Transformarea de descifrarea DA folosește cheia secreta (A',n,w-1), calculând pe baza funcției "rucsac simplu":

DA(C)=rucsac_simplu(w-1C (mod n) ,A')=M

Pentru a se ilustra algoritmul Merkle-Hellman ,sa consideram următorul exemplu: Fie A'=(1,3,5,10) vectorul rucsac simplu, n=20 si w=7. Ca urmare inversul multiplicativ al lui w este w'^-1=3. Acest rucsac simplu este transformat intr-unul cu trapa A: A=(7*1 mod 20, 7*3 mod 20, 7*5 mod 20, 7*10 mod 20)=(7,1,15,10).

Se considera următorul mesaj M care va fi cifrat: M=13,ceea ce in binar înseamnă M=(1,1,0,1).

Criptograma C este obținuta cu ajutorul vectorului cu trapa A:

C=EA(M)=7+1 +10=18. C=(1,0,0,1,0)

La descifrare se obține mesajul clar cu vectorul simplu A' care este secret:

M=DA(C)=DA(18)=RUCSAC_SIMPLU (3*18 mod 20,A')=

RUCSAC_SIMPLU(14,A')=(1,1,0,1)=13

Pentru a mari securitatea schemei, Merkle si Hellman sugerează in plus sa se adune la a, diferiți multipli ai lui n aleși aleator. Utilizând n=100 sau mai mare, se sugerează sa se aleagă n[2201+1,2202-1], astfel încât ai' sa fie uniform distribuiți:

1<A1

2100+1

3*2100+1

(2i-1-1)*2100+1 < ai < 2i-1*2100,

Algoritmul Merkle Hellman cu trapa multiplicativa

Un rucsac cu trapa multiplicativa este ușor de rezolvat daca elementele vectorului A sunt relativ prime. Fiind date A=(6,11,35,43,169) si M=2838, este ușor de determinat ca M=6*11*43 deoarece 6,11 si 43 divid pe M, in timp ce 35 si 169 nu. Un rucsac multiplicativ este transformat intr-unul aditiv prin folosirea logaritmilor. Pentru ca ambii vectori sa aibă valori rezolvabile, logaritmii sunt luat peste câmpul Galois GF(n) unde n este un număr prim.

Următorul exemplu va ilustra acesta metoda de cifrare. Fie m=4 (numărul de componente ale rucsacului), n=257,A'=(2,3,5,7) si b=131, baza logaritmului.

Informațiile secrete sunt n, A' si b. Rezolvând ecuațiile:

131a1=2 (mod257),

131a2=3 (mod257),

131a3=5 (mod257).

131a4=7 (mod 257),

rezulta: a1=80, a2=183, a3=81, a4=195 si deci A=(80,183,81,195) este vectorul făcut public. Găsirea logaritmilor peste GF(n) este relativ ușoara daca (n-1) are numai factori primi mici d (pe calculator aceasta înseamnă valori de ordinul a 106 pana Ia1012).

Acum, sa presupunem ca avem data criptograma C = 183+81=264 si vrem sa găsim soluția C=AX. Cunoscând informația-trapa n, A' si b putem calcula:
C'=b^C (mod n).

In exemplu, C'=131264 (mod 275)=15=20 31 51 70.

Rezulta ca X =(0,1,1,0), deoarece: bC=baixi=baixi=ai'xi' (mod n)

In acest caz este necesar ca: pentru a se asigura ca ai'xi (mod n) este egala cu ai'xi in mulțimea numerelor întregi.

Algoritmul Merkle Hellman iterativ

Acest algoritm vine sa mărească securitatea metodei bazate pe trapa aditiva. In cadrul acestuia s-a făcut transformarea unui rucsac greu A, intr-unul A', simplu, prin transformări de forma: ai'=w-1ai (mod n).

Se cerea ca vectorul A' sa fie strict dominant. In loc insa de a pune aceasta condiție putem cere ca A' sa fie transformabil in A" prin intermediul produsului:

ai"=w-1ai' (mod n').

Acum, la fel, in loc de a cere lui a" sa fie strict dominant, putem pune condiția ca el sa fie transformabil in A''' prin: ai"'=w"-1ai"(mod n").

Acest proces poate continua după dorința. Cu fiecare transformare succesiva structura vectorului-cheie publica, A, devine din ce in ce mai "obscura". In esența, s-a făcut o cifrare a vectorului-rucsac simplu prin aplicarea repetata a transformării care conserva structura de baza a problemei. RezultatuI final, A, apare ca o mulțime de numere aleatoare. In practica, in proiectarea unei astfel de scheme, se pleacă de la un m stabilit. Apoi se calculează o mulțime de întregi n,n',…,n(P) si una de transformări w,w',…,w(P) cu proprietățile:

w(i)<n(i)

c.m.m.d.c. (w(i),n(i))=1.

Se alege apoi un vector A', cheia secreta de descifrare, cu proprietatea de stricta dominanta a elementelor sale:

Se vor aplica succesiv p+1 transformări w,w',….w(P) pana obținem vectorul public A in felul următor:

A(P) =w’(P)A'(mod n(P)),

A(P-1)=w(P-1)A(P)(mod n(P-1)),

A(1) = w'A(2) (mod n'),

A = wA' (mod n).

Se poate demonstra ca in timp ce substituția, de exemplu, are proprietatea de închidere, adică compunerea a doua cifruri-substituție reprezintă un alt cifru-substituție, transformările (w,n) nu au aceasta proprietate. Acest lucru înseamnă ca aplicarea iterativa a (p+1) transformări (w,n),….,(w(P),n(P)), nu este echivalent cu o singura transformare de tip (w(r),n(r)). Este foarte important sa se aprecieze ritmul de creștere a vectorului A prin transformări iterative deoarece acest lucru determina expandarea datei implicate in transmiterea mesajului M de m biți, intr-un număr mai mare C care reprezintă criptograma.

Capitolul V :

Aplicatii practice

V.1 – Implementarea cifrului DES

Implementarea cifrului DES

Aplicatia este realizata in limbajul de programare Delphi 6. Ecranul principal apare ca in figura:

Sursa fisierului des.dpr

program des;

uses

Forms,

des_u in 'des_u.pas' {Form1};

{$R *.RES}

begin

Application.Initialize;

Application.CreateForm(TForm1, Form1);

Application.Run;

end.

Sursa fisierului des_u.pas

unit des_u;

interface

uses

Windows, Messages, SysUtils, Classes, Graphics, Controls,

Forms, Dialogs, StdCtrls, FileCtrl;

type

TForm1 = class(TForm)

Button2: TButton;

Edit1: TEdit;

Label1: TLabel;

Edit2: TEdit;

Button1: TButton;

OpenDialog1: TOpenDialog;

Label2: TLabel;

Label3: TLabel;

procedure Button3Click(Sender: TObject);

procedure FormActivate(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure FormShow(Sender: TObject);

private

public

end;

str8=string[8];

var

fsmallbuffer:array[1..8]of byte;

fkey:string;

FRoundKeys : Array [1..16,1..48] Of Byte;

FC: Array [1..28] Of Byte;

FD: Array [1..28] Of Byte;

FInputValue : Array [1..64] Of Byte;

FOutputValue : Array [1..64] Of Byte;

FL, FR, FFunctionResult : Array [1..32] Of Byte;

Const

IP : Array [1..64] Of Byte = (58,50,42,34,26,18,10,2,

60,52,44,36,28,20,12,4,

62,54,46,38,30,22,14,6,

64,56,48,40,32,24,16,8,

57,49,41,33,25,17, 9,1,

59,51,43,35,27,19,11,3,

61,53,45,37,29,21,13,5,

63,55,47,39,31,23,15,7);

InvIP : Array [1..64] Of Byte = (40, 8,48,16,56,24,64,32,

39, 7,47,15,55,23,63,31,

38, 6,46,14,54,22,62,30,

37, 5,45,13,53,21,61,29,

36, 4,44,12,52,20,60,28,

35, 3,43,11,51,19,59,27,

34, 2,42,10,50,18,58,26,

33, 1,41, 9,49,17,57,25);

E : Array [1..48] Of Byte = (32, 1, 2, 3, 4, 5,

4, 5, 6, 7, 8, 9,

8, 9,10,11,12,13,

12,13,14,15,16,17,

16,17,18,19,20,21,

20,21,22,23,24,25,

24,25,26,27,28,29,

28,29,30,31,32, 1);

P : Array [1..32] Of Byte = (16, 7,20,21,

29,12,28,17,

1,15,23,26,

5,18,31,10,

2, 8,24,14,

32,27, 3, 9,

19,13,30, 6,

22,11, 4,25);

SBoxes : Array [1..8,0..3,0..15] Of Byte =

(((14, 4,13, 1, 2,15,11, 8, 3,10, 6,12, 5, 9, 0, 7),

( 0,15, 7, 4,14, 2,13, 1,10, 6,12,11, 9, 5, 3, 8),

( 4, 1,14, 8,13, 6, 2,11,15,12, 9, 7, 3,10, 5, 0),

(15,12, 8, 2, 4, 9, 1, 7, 5,11, 3,14,10, 0, 6,13)),

((15, 1, 8,14, 6,11, 3, 4, 9, 7, 2,13,12, 0, 5,10),

( 3,13, 4, 7,15, 2, 8,14,12, 0, 1,10, 6, 9,11, 5),

( 0,14, 7,11,10, 4,13, 1, 5, 8,12, 6, 9, 3, 2,15),

(13, 8,10, 1, 3,15, 4, 2,11, 6, 7,12, 0, 5,14, 9)),

((10, 0, 9,14, 6, 3,15, 5, 1,13,12, 7,11, 4, 2, 8),

(13, 7, 0, 9, 3, 4, 6,10, 2, 8, 5,14,12,11,15, 1),

(13, 6, 4, 9, 8,15, 3, 0,11, 1, 2,12, 5,10,14, 7),

( 1,10,13, 0, 6, 9, 8, 7, 4,15,14, 3,11, 5, 2,12)),

(( 7,13,14, 3, 0, 6, 9,10, 1, 2, 8, 5,11,12, 4,15),

(13, 8,11, 5, 6,15, 0, 3, 4, 7, 2,12, 1,10,14, 9),

(10, 6, 9, 0,12,11, 7,13,15, 1, 3,14, 5, 2, 8, 4),

( 3,15, 0, 6,10, 1,13, 8, 9, 4, 5,11,12, 7, 2,14)),

(( 2,12, 4, 1, 7,10,11, 6, 8, 5, 3,15,13, 0,14, 9),

(14,11, 2,12, 4, 7,13, 1, 5, 0,15,10, 3, 9, 8, 6),

( 4, 2, 1,11,10,13, 7, 8,15, 9,12, 5, 6, 3, 0,14),

(11, 8,12, 7, 1,14, 2,13, 6,15, 0, 9,10, 4, 5, 3)),

((12, 1,10,15, 9, 2, 6, 8, 0,13, 3, 4,14, 7, 5,11),

(10,15, 4, 2, 7,12, 9, 5, 6, 1,13,14, 0,11, 3, 8),

( 9,14,15, 5, 2, 8,12, 3, 7, 0, 4,10, 1,13,11, 6),

( 4, 3, 2,12, 9, 5,15,10,11,14, 1, 7, 6, 0, 8,13)),

(( 4,11, 2,14,15, 0, 8,13, 3,12, 9, 7, 5,10, 6, 1),

(13, 0,11, 7, 4, 9, 1,10,14, 3, 5,12, 2,15, 8, 6),

( 1, 4,11,13,12, 3, 7,14,10,15, 6, 8, 0, 5, 9, 2),

( 6,11,13, 8, 1, 4,10, 7, 9, 5, 0,15,14, 2, 3,12)),

((13, 2, 8, 4, 6,15,11, 1,10, 9, 3,14, 5, 0,12, 7),

( 1,15,13, 8,10, 3, 7, 4,12, 5, 6,11, 0,14, 9, 2),

( 7,11, 4, 1, 9,12,14, 2, 0, 6,10,13,15, 3, 5, 8),

( 2, 1,14, 7, 4,10, 8,13,15,12, 9, 0, 3, 5, 6,11)));

PC_1 : Array [1..56] Of Byte = (57,49,41,33,25,17, 9,

1,58,50,42,34,26,18,

10, 2,59,51,43,35,27,

19,11, 3,60,52,44,36,

63,55,47,39,31,23,15,

7,62,54,46,38,30,22,

14, 6,61,53,45,37,29,

21,13, 5,28,20,12, 4);

PC_2 : Array [1..48] Of Byte = (14,17,11,24, 1, 5,

3,28,15, 6,21,10,

23,19,12, 4,26, 8,

16, 7,27,20,13, 2,

41,52,31,37,47,55,

30,40,51,45,33,48,

44,49,39,56,34,53,

46,42,50,36,29,32);

ShiftTable : Array [1..16] Of Byte =

(1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1);

DESKEYLENGTH = 8;

var

Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Button3Click(Sender: TObject);

begin

form1.Close;

end;

procedure TForm1.FormActivate(Sender: TObject);

begin

Left:=(screen.Width-Width)div 2;

Top:=(screen.Height-Height)div 3;

end;

function cheie(s:string):string;

begin

repeat

s:=s+s;

until length(s)>=8;

cheie:=s;

end;

Function GetBit (Var Data; Index : Byte) : Byte;

Var

Bits : Array [0..7] Of Byte ABSOLUTE Data;

Begin

Dec (Index);

If Bits[Index DIV 8] And (128 SHR (Index MOD 8))>0 then

GetBit:=1 Else GetBit:=0;

End;{GetBit}

Procedure SetBit (Var Data; Index, Value : Byte);

Var

Bits : Array [0..7] Of Byte ABSOLUTE Data;

Bit : Byte;

Begin

Dec (Index);

Bit:=128 SHR (Index MOD 8);

Case Value Of

0 : Bits[Index DIV 8]:=Bits[Index DIV 8] And (Not Bit);

1 : Bits[Index DIV 8]:=Bits[Index DIV 8] Or Bit;

End;

End;{SetBit}

Procedure F (Var FK);

Var

K : Array [1..48] Of Byte ABSOLUTE FK;

Temp1 : Array [1..48] Of Byte;

Temp2 : Array [1..32] Of Byte;

n, h, i, j, Row, Column : Integer;

Begin

For n:=1 to 48 Do Temp1[n]:=FR[E[n]] Xor K[n];

For n:=1 to 8 Do Begin

i:=(n-1)*6; j:=(n-1)*4;

Row:=Temp1[i+1]*2+Temp1[i+6];

Column:=Temp1[i+2]*8 + Temp1[i+3]*4 +

Temp1[i+4]*2 + Temp1[i+5];

For h:=1 to 4 Do Begin

Case h Of

1 : Temp2[j+h]:=(SBoxes[n,Row,Column] And 8) DIV 8;

2 : Temp2[j+h]:=(SBoxes[n,Row,Column] And 4) DIV 4;

3 : Temp2[j+h]:=(SBoxes[n,Row,Column] And 2) DIV 2;

4 : Temp2[j+h]:=(SBoxes[n,Row,Column] And 1);

End;

End;

End;

For n:=1 to 32 Do FFunctionResult[n]:=Temp2[P[n]];

End;

Procedure Shift (Var SubKeyPart);

Var

SKP : Array [1..28] Of Byte ABSOLUTE SubKeyPart;

n, b : Byte;

Begin

b:=SKP[1];

For n:=1 to 27 Do SKP[n]:=SKP[n+1];

SKP[28]:=b;

End;

Procedure SubKey (Round : Byte; Var SubKey);

Var SK : Array [1..48] Of Byte ABSOLUTE SubKey; n, b : Byte;

Begin

For n:=1 to ShiftTable[Round] Do Begin

Shift (FC);

Shift (FD);

End;

For n:=1 to 48 Do Begin

b:=PC_2[n];

If b<=28 then SK[n]:=FC[b] Else SK[n]:= FD[b-28];

End;

End;

Procedure SetKeys;

var

n: BYTE;

Key: Array [0..7] of BYTE;

begin

move(FKey[1], Key, DESKEYLENGTH);

For n:=1 to 28 Do Begin

FC[n]:=GetBit(Key,PC_1[n]);

FD[n]:=GetBit(Key,PC_1[n+28]);

End;

For n:=1 to 16 Do SubKey(n,FRoundKeys[n]);

end;

Procedure EncipherBLOCK;

var n, i, b, Round : Byte;

begin

For n:=1 to 64 Do FInputValue[n]:=GetBit (FSmallBuffer,n);

For n:=1 to 64 Do If n<=32 then FL[n]:=FInputValue[IP[n]] Else FR[n-32]:=FInputValue[IP[n]];

For Round:=1 to 16 Do Begin

F (FRoundKeys[Round]);

For n:=1 to 32 Do

FFunctionResult[n]:=FFunctionResult[n] Xor FL[n];

FL := FR; FR := FFunctionResult;

End;

For n:=1 to 64 Do Begin

b:=InvIP[n];

If b<=32 then FOutputValue[n]:=FR[b]

Else FOutputValue[n]:=FL[b-32];

End;

For n:=1 to 64 Do SetBit (FSmallBuffer,n,FOutputValue[n]);

end;

Procedure DecipherBLOCK;

var n, i, b, Round : Byte;

begin

For n:=1 to 64 Do FInputValue[n]:=GetBit (FSmallBuffer,n);

For n:=1 to 64 Do

If n<=32 then FL[n]:=FInputValue[IP[n]]

Else FR[n-32]:=FInputValue[IP[n]];

For Round:=1 to 16 Do Begin

F (FRoundKeys[17-Round]);

For n:=1 to 32 Do

FFunctionResult[n]:=FFunctionResult[n] Xor FL[n];

FL := FR;

FR := FFunctionResult;

End;

For n:=1 to 64 Do Begin

b:=InvIP[n];

If b<=32 then FOutputValue[n]:=FR[b]

Else FOutputValue[n]:=FL[b-32];

End;

For n:=1 to 64 Do SetBit (FSmallBuffer,n,FOutputValue[n]);

end;

function checksum(s1:string):longint;

var

cs,x:longint;

r:integer;

f:file;

begin

cs:=0;

assignfile(f,s1);

reset(f,4);

while not(eof(f))do

begin

blockread(f,x,1,r);

cs:=cs xor x;

end;

closefile(f);

checksum:=cs;

end;

procedure criptare(s1,s2,s3:string);

var

f1,f2:file;

i,si:byte;nr:integer;

pwd:string;

x,y:str8;

cs:longint;

begin

fkey:=cheie(form1.edit1.text);

setkeys;

cs:=checksum(s1);

assignfile(f1,s1);

reset(f1,1);

si:=filesize(f1);

i:=si mod 8;

if i=0 then i:=8;

assignfile(f2,s2);

rewrite(f2,1);

blockwrite(f2,i,1);

blockwrite(f2,cs,4);

while not(eof(f1))do

begin

blockread(f1,fsmallbuffer,8,nr);

encipherblock;

blockwrite(f2,fsmallbuffer,8);

end;

close(f1);

close(f2);

showmessage('Fisier criptat OK!');

end;

procedure decriptare(s1,s2,s3:string);

var

f1,f2:file;

i,si:byte;

pwd:string;

cs:longint;

x,y:str8;

begin

fkey:=cheie(form1.edit1.text);

setkeys;

assignfile(f1,s1);

reset(f1,1);

blockread(f1,si,1);

assignfile(f2,s2);

rewrite(f2,1);

blockread(f1,cs,4);

while not(eof(f1))do

begin

blockread(f1,fsmallbuffer,8);

decipherblock;

if not(eof(f1))then

begin

blockwrite(f2,fsmallbuffer,8);

end else

blockwrite(f2,fsmallbuffer,si)

end;

close(f1);

close(f2);

if cs=checksum(s2)

then showmessage('Fisier decriptat, suma de control OK')

else showmessage('Suma de control gresita ! '+

'Posibil+ cuvânt cheie eronat !');

end;

procedure TForm1.Button2Click(Sender: TObject);

var

fn1,fn2:string;

begin

if fileexists(edit2.Text) then

begin

fn1:=edit2.Text;

if copy(fn1,length(fn1)-3,4)<>'.des'

then

begin

fn2:=fn1+'.des';

if edit1.Text<>'' then criptare(fn1,fn2,edit1.Text)

else showmessage('Introduceti cuvântul cheie !');

end

else

begin

fn2:=copy(fn1,1,length(fn1)-4);

if edit1.Text<>'' then

decriptare(fn1,fn2,edit1.Text)

else

showmessage('Introduceti cuvântul cheie !');

end;

end else

showmessage('Apasati butonul "…" pentru' +

' a selecta fisierul !');;

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

opendialog1.InitialDir:=extractfilepath(application.ExeName)+

'Fisiere\';

if opendialog1.Execute then

edit2.Text:=opendialog1.FileName;

end;

procedure TForm1.FormShow(Sender: TObject);

begin

top:=(screen.Height-Height)div 3;

left:=(screen.Width-Width)div 2;

end;

end.

Bibliografie