Elemente de criptografie / criptologie3.1Scurt istoricInformaia (religioas, militar, economic, etc.) a insemnat intotdeauna putere, prin urmare dorina de a o proteja, de a o face accesibil doar unor elite, unor iniiai, s-a pus din cele mai vechi timpuri. Primele texte cifrate descoperite pan in prezent dateaz de circa 4000 de ani i provin din Egiptul antic, dar existena acestora probabil c dateaz de la apariia scrierii in toate civilizaiile umane.Exist date privind utilizarea scrierii cifrate in Grecia antic inc din secolul al V-lea i.e.n. Pentru cifrare se folosea un baston in jurul cruia se infura, spiral lang spiral, o panglic ingust de piele, papirus sau pergament pe care, paralel cu axa, se scriau literele mesajului.Dup scriere panglica era derulat, mesajul devenind indescifrabil. El putea fi reconstituit numai de ctre persoana care avea un baston identic cu cel utilizat la cifrare. In secolul al IV-lea i.e.n. in Grecia se cunoteau 16 scrieri cifrate. Istoricul grec Polybius (sec II i.e.n.) este inventatorul unui tabel de cifrare ptrat de dimensiune 5x5, tabel aflat la baza elaborrii unui numr mare de sisteme de cifrare utilizate i azi.In Roma antic secretul informaiilor politice i militare se fcea utilizand scrierea secret.Amintim cifrul lui Cesar, utilizat inc din timpul rzboiului galic.Exist documente ce atest existena scrierilor secrete in Asia inc din antichitate. Astfel, literatura indian d o serie de referine dintre care Artha-sstra (321-300 i.e.n.), Lalita-Vistara i Kamasutra sunt exemplele cele mai cunoscute. In China antic, documentele militare i diplomatice de mare importan erau scrise pe faii inguste de mtase sau hartie; acestea erau rulate formand mici bile care apoi se acopereau cu cear i se introduceau in rectul mesagerilor.[Deavours]Steganografia, tiina scrierilor secrete insesizabile camuflate in texte in clar, constituie o form particular de secretizare i este prezentat in detaliu in capitolul 8.Contribuia arab ([Deavours] - Al Kadif) la dezvoltarea criptologiei, mai puin cunoscut i mediatizat este de o remarcabil importan. David Kahn, unul dintre cei mai de seam istoriografi ai domeniului, subliniaz in cartea saThe Codebreakersc criptologia s-a nscut in lumea arab. Primele trei secole ale civilizaiei islamice (700-1000 e.n.) au constituit, pe lang o mare extindere politic i militar i o epoc de intense traduceri in limba arab ale principalelor opere ale antichitii greceti, romane, indiene, armene, ebraice, siriene. Unele cri surs erau scrise in limbi deja moarte, deci reprezentau in fapt texte cifrate, astfel incat traducerea lor constituie primii pai in criptanaliz, deci originile criptologiei pot fi atribuite arabilor. Cartea lui Ahmad ibn Wahshiyyah (cca. 900 e.n.) conine 93 de alfabete ale diferitelor limbi, moarte sau vii.Nou secole mai tarziu, cartea a fost tradus in limba englez i a fost publicat la Londra de ctre orientalistul Joseph von Hammer sub denumireaAncient Alfabets and Hieroglyphic Caracters Explained, iar aceasta din urm a fost tradus i publicat la Paris in 1810 i este posibil s-l fi ajutat pe celebrul arheolog J. F. Champollion in descifrarea hieroglifelor (scrierea de la Rosseta, aflat la British Museum). Dezvoltrile criptanalizei au fost mult sprijinite de studiile lingvistice ale limbii arabe care in primele patru secole ale imperiului islamic a constituit limba oficial unificatoare pentru un imperiu de o uria intindere i in acelai timp i limba tiinific.Arabii au preluat cunotinele matematice ale civilizaiilor greceti i indiene. Arabii sunt cei care au introdus sistemul zecimal de numeraie i cifrele"arabe". Termenii"zero","cifru","algoritm","algebr"li se datorez tot lor. Manuscrise recent descoperite arat c primele scrieri in domeniul probabilitilor i statisticii dateaz cu 800 de ani inaintea celor corespunztoare ale lui Pascal i Fermat. Insui termenul de"cifru"ne vine de la arabi. El provine de la cuvantul arab"ifr"care reprezint traducerea in arab a cifrei zero din sanscrit. Conceptul de zero a fost deosebit de ambigu la inceputurile introducerii lui in Europa, in care sistemul de numeraie folosit era cel roman. De aceea se obinuia s se spun despre cineva care vorbeaneclar c vorbete ambigu, ca un cifru. Acest ineles de ambiguitate a unui mesaj poart i azi denumirea de cifru.In perioada Renaterii, odat cu trezirea interesului pentru civilizaia antic,s-au redescoperit lucrrile criptografiei din antichitate.Extinderea relaiilor diplomatice dintre diferitele state feudale a determinat o puternic dezvoltare a secretizrii informaiei. Curile regale i in special statul papal dispuneau de criptologi de mare valoare dintre care amintim pe Giambattista della Porta, Vignre, Cardan (secolul XIV) i Rossignol (secolul XVIII), cel mai abil criptolog din Europa regilor Ludovic al XIII-lea i Ludovic al XIV-lea.In fapt istoria criptografiei / criptologiei urmrete indeaproape creterea i descreterea marilor imperii i civilizaii.Ea nu apare i nu se dezvolt decat acolo unde este putere ce trebuie protejat.Apariia telegrafului i a radioului in secolul al XIX-lea precum i cele dou rzboaie mondiale din secolul XX au fost stimulente puternice in dezvoltarea metodelor i tehnicilor de criptare.Apariia i dezvoltarea continu a utilizrii calculatoarelor practic in toate domeniile vieii, existena i evoluia puternic a reelelor teleinformatice la nivel naional i internaional,globalizarea comunicaiilor, existena unor baze de date puternice, apariia i dezvoltarea comerului electronic, a potei electronice, constituie premisele societii informaionale in care pim. Toate acestea indic o cretere extraordinar a volumului i importanei datelor transmise sau stocate i implicit a vulnerabilitii acestora. Protecia in aceste sisteme vizeaz:eliminarea posibilitilor de distrugere voit sau accidentalasigurarea caracterului secret al comunicrii pentru a preveni posibilitatea ca persoane neautorizate s extrag informaiiautentificarea informaiei in scopul prevenirii posibilitii ca persoane neautorizate s introduc informaii in sistemin anumite situaii, cum ar fi transferurile electronice de fonduri, negocierile contractuale, este important existena unor semnturi electronice pentru a evita dispute intre emitor i receptor cu privire la mesajul transmis.Toate aceste obiective arat o lrgire puternic a domeniului de aplicare al criptografiei de la domeniul diplomatic, militar, politic, la cel civil cu caracter economic i social. La ora actual, 99% din criptografie nu este utilizat pentru protejarea secretelor militare ci pentru carduri bancare, pli de taxe radio / TV, taxe de drumuri, acces autorizat in cldiri sau la calculatoare, terminale de loterie, instrumente electronice de pli anticipate. In aceste aplicaii rolul criptografiei este acela de a face furturile mai greu de realizat.3.2Terminologie de bazCriptografia (cryptography)este tiina creerii i meninerii mesajelor secrete, in sensul imposibilitii citirii lor de ctre neautorizai (tiina mesajelor secrete).Mesaj (text) in clar (M) (plain / clear text)este mesajul ce urmeaz a fi secretizat; in criptografie M se mai numete scriere chiar dac este un document de alt natur, de exemplu voce, imagine, date.Mesaj cifrat (criptogram) (C) (cipher text)este mesajul secretizat, inaccesibil neavizailor.Criptare / cifrare (E) (encryption / enciphering)este procedeul de"ascundere"a unui mesaj in clar in mesajul secretizat.(3.1)Decriptare / descifrare (D) (decryption / deciphering)este procedeul de regsire a mesajului in clar M din mesajul cifrat C.(3.2)Observaii:decriptarea este operaia invers criptrii;ISO 7498-2 folosete termenii de cifrare / descifrare (encipher / decipher), socotete Schneier [Scheneier], probabil pentru c primul set de termeni amintete de mori (cript).Criptograf (cryptographer)este persoana ce se ocup cu criptografia.Algoritm criptografic / cifru (cryptographic algorithm / cipher)este funcia sau funciile matematice utilizate pentru criptare / decriptare; in general exist dou funcii: una pentru criptare (E) i alta pentru decriptare (D).Cheia criptografic (K) (key)este mrimea (in majoritatea cazurilor secret) necesar realizrii criptrii i decriptrii.Criptosistem (cryptosystem)este sistemul format din:-algoritm-toate mesajele in clar (M)-toate textele cifrate (C)-toate cheile (K).Criptanaliz (cryptanalysis)este tiina spargerii cifrurilor, deci a obinerii mesajelor in clar (M) sau a cheii (K) din mesajul cifrat (C).Criptanalist (cryptanalyst)este persoana care se ocup cu criptanaliza.Atac (attack)este incercarea / tentativa criptanalitic.Criptologie (cryptology)este tiina care se ocup atat de criptografie cat i de criptanaliz.Criptolog (cryptologist)este persoana care se ocup cu criptologia.Steganografia (steganography)este tehnica ascunderii mesajelor secrete in alte mesaje, in aa fel incat existena mesajelor secrete s fie invizibil.3.3Criptosisteme i rolul acestoraSchema bloc a unui criptosistem este prezentat inFig3.1.Fig.3.1- Schema bloc a unui criptosistemA, B - entiti ce emit, recepioneaz sau manipuleaz informaiaE - funcia de criptare (cifrare)D - funcia de decriptare (descifrare)M - spaiul mesajelor in clarC - spaiul criptogramelor (text cifrat)K - spaiul cheilorKe - spaiul cheilor de criptareKd - spaiul cheilor de decriptare3.3.1Rolul unui criptosistemRolul unui criptosistem este de a preveni sau detecta activitile nepermise dintr-un sistem informatic, cum ar fi:-consultarea neavizat a datelor transmise sau stocate-inserarea de mesaje false-modificarea, tergerea sau distrugerea mesajelor existente-analiza traficului-conectrile neautorizate.deci, aa cum se precizeaz in capitolul 1, acela de"poliie informatic".Indeplinirea acestui rol presupune ca un criptosistem s realizeze:Confidenialitatea / secretul / protecia datelor (confidentiality / secrecy / privacy)asigur inaccesibilitatea coninutului informaiei transmise / stocate pentru un utilizator neavizat (in cazul canalelor / mediilor nesigure in care pot aprea intrui)Autentificarea (autentication)se aplic [Menezes] la:-entiti (persoane, terminale, cri de credit, etc.) i in acest caz se numeteautentificarea entitilor / identificare (entity autentication / identification)-informaie: informaia trasmis / stocat trebuie s fie autentificat in sensul originii, coninutului datelor, timpului de transmisiune / stocare i defineteautentificarea originii datelor / integritatea datelor (data origin autentication / data integrity)Semntura digital (digital signature)[Scheneier] reprezint autentificarea reciproc a datelor i en 252e44c titilor i se refer la faptul c un utilizator B este sigur c mesajul recepionat vine de la A prin semnarea mesajelor sale (SA), iar A este sigur c nimeni nu-i poate atribui un mesaj fals deoarece mesajul transmis de ctre el ii poart semntura.Observaie:Aceste trei cerine sunt vitale pentru interaciunea"social"in calculatoare i sunt echivalente cu interaciunile umane fa in fa.Pe lang cele trei obiective principale anterior enumerate, anumite criptosisteme pot asigura i alte obiective printre care amintim:nerepudierea (non-repudiation), autorizarea (authorization), validarea (validation),controlul accesului (acces control), certificarea (certification), certificarea temporal (time-stamping), mrturia (witnessing), confirmarea (confirmation), dreptul de proprietate (ownership), anonimatul (anonimity), revocarea (revocation).Obiectivele pe care le poate realiza un criptosistem sunt cuprinse intabelul 3.1.Observaii:toate aceste obiective exist natural in interaciunile umane fa in fa;apariia reelelor de calculatoare prin care au loc interaciunile interumane pune o serie de probleme in plus: hartia se inlocuiete cu discul, unda radio, firul; scrisul are un format electronic i anume"bii"cu posibilitate extrem de uoar de copiere (copiile digitale sunt identice); utilizatorii se afl la distan, nu se pot vedea fa in fa i deci se lucreaz in condiii de neincrederecriptografia este chemat astfel s soluioneze o diversitate extrem de probleme, multe de mare dificultateNr. crt.ObiectivulDefinirea

1confidenialitateapstrarea secretului pentru neavizai

2autentificareaentitilor / identificarelegat de identitatea unei entiti (persoan, terminal, carte de credit, etc.)

originii datelorlegat de sursa de informaie (sursainformaiei)

integritii datelorasigur c informaia nu a fost modificatde surse neautorizate

3semnturamijlocul de a lega informaia de entitate

4nerepudiereaprevenirea nerecunoaterii unor aciuni comise anterior

5autorizareatransferul ctre alt entitate a uneiimputerniciri oficiale de a fi sau de a faceceva

6validareamijlocul de a permite (pentru o anumitperioad de timp)autorizarea de a folosisau manipula informaia sau resursele

7revocarearetragerea certificatului sau autorizaiei

8controlul accesuluirestricionarea accesului la resurse pentruentiti privilegiate (cu drept de acces)

9certificareinformaia de aprobare dat de o entitatede incredere (arbitru)

10certificare temporalinregistrarea timpului de creere sau deexisten a informaiei

11mrturiaverificarea creerii sau existenei uneiinformaii de ctre o entitate diferit decatcea creatoare

12confirmarearecunoaterea faptului c serviciile au fostefectuate

13dreptul de proprietatemijlocul de a inzestra o entitate cu dreptullegal de a utiliza sau transfera o surs laalii

14anonimatulascunderea (tinuirea) identitii unei entiti implicate intr-un anumit proces

Tabelul 3.1- Obiectivele unui criptosistem ce realizeaz securitatea informaiei3.3.2Clasificarea criptosistemelorDup tipul cheilor folosite pentru criptare / decriptare, criptosistemele se clasific in dou categorii i anume in sisteme: cu chei simetrice i cu chei publice.3.3.2.1Criptosistemele cu chei simetrice / cu cheie secret / criptosistemele convenionaleCriptosistemele cu chei simetricesunt criptosistemele pentru care cheile folosite la criptare i decriptare sunt identice, de unde i denumirea de criptosisteme cu chei simetrice.(3.3)Cheia K este secret, fapt ce conduce la denumirea desisteme cu cheie secret. Criptarea i decriptarea se realizeaz extrem de simplu dac se cunoate K:(3.4)(3.5)Problema ce se pune in cazul acestor sisteme este distribuia cheii K, care necesit un canal sigur.Dup tipul algoritmului folosit, criptosistemele cu chei simetrice se clasific in dou categorii:cu cifruri bloc (block ciphers)sunt cifrurile care acioneaz asupra unei diviziuni a textului in clar; blocurile de la intrare se cifreaz independent, lungimea tipic a blocurilor fiindbii. Transformrile de baz folosite pentru criptare i decriptare sunt substituiile i transpoziiile, repetate iterativ [Angheloiu et al. (1986)] [Scheneier].cu cifruri secveniale (stream ciphers):mesajul de la intrare este considerat ca o succesiune (ir) de simboluri. Criptarea opereaz asupra textului in clar simbol cu simbol. Cheia K este generat de un registru de deplasare cu reacie (RDR) avand starea iniialcontrolat de o cheie compact [Angheloiu et al. (1986)][Scheneier].3.3.2.2Criptosisteme cu chei publice (asimetrice)Criptosistemele cu chei publicesunt criptosistemele pentru care cheile folosite la criptare i decriptare difer, de unde deriv i denumirea de sisteme asimetrice:.(3.6)Cheia public - aa cum ii spune i numele - poate fi accesat public (asemntor unei cri de telefon), iar cheia privataeste secret. Caracteristic acestor sisteme este c funcia de criptare i cea de decriptare se realizeaz uor dac se cunosci:(3.7)daraflarea lui M,dac se cunosc C ieste computational nefezabil.Observaie: E este o funcie neinversabil cu trap [Angheloiu et al. (1986)], [Patriciu (1994)], [Menezes].este trapa care furnizeaz informaia necesar calculrii funciei inverse D. Dintre funciile neinversabile cu trap amintim: factorizarea unui produs de numere prime mari cu peste 100 de cifre zecimale (folosit in algoritmul RSA), gsirea logaritmului modulo un numr prim intr-un camp Galois GF(q) cuqfoarte mare (folosit in algoritmii Rabin i Diffie-Hellman), problema rucsacului (folosit in algoritmul Merkle-Hellman).3.4Atacuri i modele de securitatein sisteme informatice3.4.1Atacuri asupra securitii sistemelor criptograficeAtaculasupra securitii unui sistem criptografic definete orice aciune ce compromite securitatea acelui sistem.O ilustrare sugestiv a principalelor tipuri de atacuri asupra unui sistem informatic este fcut infig 3.2[Stallings]

Fig. 3.2- Ilustrarea principalelor tipuri de atacuri la securitatea unui sistem criptograficAtacurile criptografice pot fi indreptate impotriva:-algoritmilor criptografici-tehnicilor utilizate pentru implementarea algoritmilor i protocoalelor-protocoalelor.Dup modul de atacare al unuiatacator / intrus / persoan neautorizat / pirat(attacker / introuder / pirat), aceste atacuri se pot clasifica dup cum urmeaz:atacuri pasive (de intercepie):-de inregistrare a coninutului mesajelor-de analiz de trafic;atacuriactive:-de intrerupere (atac la disponibilitate)-de modificare (atac la integritate)-de fabricare (atac la autenticitate).Atacurile pasivesunt atacuri in care intrusul (persoan, calculator, program) doar ascult, monitorizeaz transmisia, deci suntatacuri de intercepie. Ele pot fi de dou feluri:deinregistrare a coninutului mesajelor (release of message contents), de exemplu in convorbirile telefonice, in pota electronic, fapt pentru care dac mesajele nu sunt criptate, se violeaz caracterul confidenial al comunicaiei.de analiz a traficului (traffic analysis): in cazul in care mesajele sunt criptate i nu se poate face rapid criptanaliza, prin analiza traficului se pot afla o serie de date utile criptanalizei precum identitatea prilor ce comunic intre ele, frecvena i lungimea mesajelor.Caracteristicile atacurilor pasive:-sunt greu de detectat pentru c datele nu sunt alterate;-msurile ce pot fi luate pentru evitarea acestor atacuri sunt acelea care fac criptanaliza extrem de grea dac nu imposibil;-este necesar prevenirea i nu detecia lor.Atacurile activesunt atacuri in care intrusul are o intervenie activ atat in desfurarea normal a traficului, cat i in configuraia datelor (modificarea datelor, creearea unor date false). Dintre atacurile active amintim [Stallings],[Menezes]:intreruperea[Stallings]/ refuzul serviciului (denial of service)[Menezes]: un bloc funcional este distrus, sau se inhib funcionarea normal sau managementul facilitilor de comunicaie; acest tip de atac este unatac la disponibilitate (attack on availability)modificarea: mesajul iniial este intarziat, alterat, reordonat pentru a produce efecte neautorizate ca de exemplu:-schimbare de valori in fiiere de date;-modificri in program astfel incat acesta va lucra diferit;-modificarea coninutului mesajelor transmise in reeafabricarea: un neavizat insereaz informaii false in sistem; acest atac este unatac la autenticitate. Din aceast categorie fac parte i:-mascarea (masquerade): o entitate pretinde a fi alt entitate.Exemplu: secvenele de autentificare pot fi capturate i dup validarea unei autentificri se inlocuiesc, permiand astfel unei entiti s obin privilegii pe care nu le are de drept.-reluarea (replay)const in capturarea prin atac pasiv a unei cantiti de informaie i transmiterea sa ulterioar pentru a produce efecte neautorizate.Caracteristicile atacurilor active:-dei pot fi detectate, prevenirea lor este foarte grea, deoarece ar insemna protecie fizic permanent a intregului sistem.3.4.2Atacuri criptanaliticeAtacurile criptanalitice[Scheneier] sunt atacuri asupra textelor cifrate in vederea obinerii textului in clar sau a cheilor folosite pentru decriptare.Exist mai multe tipuri de asemenea atacuri dintre care amintim:1)Atac asupra textului cifrat (cipher text-only attack): criptanalistul are criptogramai trebuie s obin mesajul in clar () sau cheiak.2)Atac asupra unui text cunoscut (known plain-text attack): criptanalistul are criptogramelei mesajele in clarcorespunztoare i trebuie s determine cheiaksau algoritmul de determinarea luidin.3)Atac cu text in clar ales (chosen plain-text attack): se pot alege o serie de mesajedup dorin i se cunosc criptogramele corespondente:. Criptanalistul trebuie s determine cheiaksau algoritmul de determinare al luidin.4)Atac cu text in clar ales adaptiv (adaptive chosen plain-text attack):mesajele in clarse pot alege dup dorin i sunt adaptabile in funcie de rezultatele criptanalizelor anterioare, iar criptogramelese cunosc. Se cere cheiaksau algoritmul de determinare al luidin.Aceste patru atacuri constituie atacurile criptanalitice de baz. In afara acestora mai putem aminti:5)Atac cu text cifrat la alegere (chosen cipher-text attack)in care se alegi, sarcina criptanalistului fiind determinarea cheiik. Acest atac se aplic mai ales algoritmilor cu chei publice.6)Atacul de"cumprare"a cheii (rubber-hose cryptanalysis / purchase-key attack),in care aflarea cheii se face fr mijloace criptanalitice (se apeleaz la antaj, furt, etc.) i este unul dintre cele mai puternice atacuri.Observaie:Atacurile 3) i 5) se numescatacuri cu text ales (chosen text attack)i au fost folosite cu succes in cel de-al doilea rzboi mondial pentru spargerea codurilor german i japonez [Deavours].3.4.3Securitatea algoritmilor[Scheneier]In secolul al XIX-lea, olandezul A. Kerckhoff a enunat conceptul fundamental al criptanalizei:secretul se rezum in intregime la cheie,algoritmul criptografic i implementarea considerandu-se cunoscute.Diferiii algoritmi pot asigura diferite grade de securitate, funcie de dificultatea cu care pot fi spari [Menezes], [Scheneier]:dac costul spargerii unui algoritm este mai mare decat valoarea datelor criptate, algoritmul esteprobabil sigur (PS);dac timpul necesar spargerii este mai mare decat valabilitatea datelor criptate, algoritmul estePS;dac mulimea datelor necesare spargerii este mai mare decat mulimea datelor criptate la un moment dat de o cheie, algoritmul estePS.Lars Knudsen - in teza de doctorat susinut in 1994 [Menezes] - a clasificat diferitele categorii de spargere a unui algoritm in ordine descresctoare a securitii:1)Spargere total (total break) / securitate zero: un criptanalist gsete cheia, deci orice criptogram va fi decriptat:.2)Deducie global (global deduction): criptanalistul gsete un algoritm alternativ echivalent cufr a cunoate cheiak.3)Deducie local (local deduction):un criptanalist gsete textul in clar al unui text cifrat interceptat.4)Deducia informaional (information deduction): criptanalistul capt unele informaii privitor la cheie sau la textul in clar (de exemplu caiva bii ai cheii, anumite informaii privitoare la M, etc.).5)Algoritm computaional puternic (computational strong)este algoritmul care nu poate fi spart cu resursele existente, atat la momentul curent, cat i intr-un viitor predictibil.6)Algoritm necondiionat sigur (unconditional secure)este algoritmul pentru care indiferent cat text cifrat are criptanalistul, informaia nu este suficient pentru a deduce textul in clar. Privitor la aceti din urm termeni trebuie atenionat c sunt extrem de expui interpretrilor.Observaii:Doarcheia de unic folosin (one time pad), inventat in 1917 de Major J. Maubergue i Gilbert Vernon, avand aceeai lungime cu a textului in clar, estede nespart.Toi ceilali algoritmi pot fi spari cu ajutorul unui atac cu text cifrat, prin incercarea tuturor cheilor, pan cand textul descifrat are sens. Acest atac se numeteatac prin for brut (brute force attack).Complexitatea unui atac (complexity)se manifest in mai multe feluri:a)Complexitatea datelor (data complexity)este volumul de date necesar pentru atac;b)Complexitatea procesrii / factorul de lucru (processing complexity / work factor)este timpul necesar realizrii atacului;c)Complexitatea stocrii (storage complexity)este cantitatea de memorie necesar atacului.Regul:Complexitatea unui atac = max .Exemplu:complexitatea deindicoperaii necesare spargerii cifrului (de obicei aceasta reprezint complexitatea atacului prin for brut, deci in cazul unui algoritm necondiionat sigur, 128 indicand lungimea cheii in bii).Observaie:Multe atacuri se preteaz paralelismului, deci complexitatea scade fa de regula anterior enunat.3.5Criptografie clasic (precomputaional)Criptografia clasiceste criptografia dinaintea calculatorului, de unde i denumirea decriptografieprecomputaional.In criptografia clasic, algoritmii erau bazai pe caracter i constau dintr-o serie de transformri elementare (substituii, transpoziii) ale caracterelor textului in clar. Unii algoritmi aplicau aceste transformri in mod repetat, imbuntind in acest mod securitatea algoritmului.In criptografia modern bazat pe calculator (criptografie computaional), lucrurile s-au complicat, dar multe dintre ideile criptografiei clasice au rmas nemodificate.Criptografia clasic se incadreaz in clasa criptografiei cu chei simetrice.3.5.1Cifruri de substituieCifrul de substituie (substitution cipher)este cifrul bloc la care fiecare caracter sau grup de caractere ale textului in clar (M) este substituit cu un alt caracter sau grup de caractere in textul cifrat (C), descifrarea facandu-se prin aplicarea substituiei inverse asupra textului cifrat.In criptografia clasic exist patru tipuri de cifruri de substituie:1)Cifruri de substituie monoalfabetic (monoalphabetic ciphers)sunt cifrurile in care fiecare caracter al textului in clar (M) este inlocuit cu un caracter corespondent in textul cifrat (C). Vom aminti cateva dintre cifrurile de substituie cele mai cunoscute:A. Cifrul lui CesarEste un cifru cu substituie monoalfabetic:fiecare liter a textului in clar este inlocuit cu o nou liter obinut printr-o deplasare alfabeticcheia (aceeai la criptare cat i la decriptare) const in numrul care indic deplasarea alfabetic(3.8)undease numete factor de amplificare, iarbcoeficient de deplasare.Fcand corespondena biunivoc intre literele alfabetului latin (N= 26) i echivalentele lor numerice, cifrul lui Cesar se poate scrie conformtabelului 3.2.(3.9)TextclarABCDEFGHIJKLMNOPQRSTUVWXYZ

TextcifratDEFGHIJKLMNOPQRSTUVWXYZABC

Tabelul 3.2- Cifrul lui CesarExemplu:CelebrulVENI VIDI VICI, devine prin criptare :YHQL YLGL YLFL.Ulterior, cifrul lui Cesar, a fost generalizat prin alegerea in calitate de cheie a oricrei litere din alfabet.B. Cifrul lui PolybiusEste un cifru substituie. Literele alfabetului latin sunt aezate intr-un ptrat de dimensiune 5x5. Literele I i J sunt combinate pentru a forma un singur caracter, deoarece alegerea final (intre I i J) poate fi uor decis din contextul mesajului. Rezult 25 de caractere aezate intr-un ptrat 5x5. Cifrarea oricrui caracter se face alegand perechea potrivit de numere (intersecia liniei i coloanei) corespunztoare dispunerii caracterului in ptrat.12345

1ABCDE

2FGHIJK

3LMNOP

4QRSTU

5VWXYZ

Tabelul 3.3- Ptratul lui PolybiusExemplu:Mesajul:"A SOSIT TIMPUL", se transform dup cifrare in:"11 3443344244444223535413".Observaie:Codul poate fi schimbat prin rearanjarea literelorin ptratul 5x5.In sistemele UNIX, programul de criptareROT 13este un cifru de substituie monoalfabetic; fiecare liter, in textul cifrat se rotete cu 13 caractere, de unde i denumirea de ROT 13:(3.10)iar decriptarea se face aplicand de dou ori ROT 13, dat fiind c alfabetul latin conine N = 26 litere:(3.11)Acest cifru nu este in realitate un cifru de securitate; el se utilizeaz adesea in posturile de utilizatori de reea pentru a ascunde texte potenial ofensive [Scheneier].Concluzie: Cifrurile de substituie monoalfabetic pot fi sparte cu uurin deoarece frecvenele literelor alfabetului nu se schimb in textul cifrat fa de textul in clar.2)Cifruri de substituie omofonic (homophonic substitution ciphers)[Angheloiu et al. (1986)][Patriciu (1994)] sunt cifrurile de substituie in care un caracter al alfabetului mesajului in clar (alfabet primar) poate s aib mai multe reprezentri.Ideea utilizat in aceste cifruri este uniformizarea frecvenelor de apariie a caracterelor alfabetului textului cifrat (alfabet secundar), pentru a ingreuna atacurile criptanalitice.Astfel, litera A - cu cea mai mare frecven de apariie in alfabetul primar - poate fi inlocuit cu F, * sau K.Concluzii:dei mai greu de spart decat cifrurile de substituie simple (monoalfabetice), ele nu mascheaz total proprietile statistice ale mesajului in clar.in cazul unui atac cu text in clar cunoscut, cifrul se sparge extrem de uor.atacul cu text cifrat este mai dificil, dar unui calculator ii va lua doar cateva secunde pentru a-l sparge.3)Cifruri de substituie poligramic (polygram substitution ciphers)[Patriciu (1994)][Scheneier] se obin substituind blocuri de caractere ale alfabetului primar- numite poligrame - cu alte blocuri de caractere, de exemplu:ABARTQSLLABBUtilizri:Cifrul Playfair, inventat in 1854 [Stallings], a fost utilizat in Anglia, in timpul primului rzboi mondialCodul de compresie Huffman, bazat pe acelai principiu, poate fi utilizat dar estenesigur.4)Cifruri de substituie polialfabetice[Patriciu (1994)][Scheneier][Patriciu (1998)] sunt formate din mai multe cifruri de substituie simple. Au fost inventate de Leon Battista, in 1568. Dintre acestea vom aminti pe dou dintre cele mai celebre i anume cele ale lui Trithemius i Vignre.A. Cifrul lui TrithemiusEste un cifru polialfabetic. Alfabetul este dispus pe 26 de linii numerotate de la 0 la 25, unde numrul de ordine al liniei indic numrul de caractere cu care se deplaseaz ciclic alfabetul spre dreapta. Linia numerotat cu 0 constituie tocmai alfabetul in ordinea iniial. Acest cifru poate fi utilizat astfel: primul caracter se cifreaz selectandu-l din linia 1, al doilea din linia a 2-a i aa mai departe [Borda (1999)].Exemplu:123456789101112Mesajul:AS O SITTIMPUL, se cifreaz:B URWNZ AQVZFX.B. Cifrul lui VignreAcest cifru utilizeaz cifrul Trithemius i un anumit cuvant cheie. Cheia dicteaz alegerea liniilor in criptarea i decriptarea fiecrui caracter din mesaj.Exemplu:121413012141301214130

Cuvant cheieMONAMONAMONA

Text in clarASOSITTIMPUL

Text cifratMGBSUHGIYDHL

O variant a acestui cifru estecifrul Vignre cu cheie in clar (cheie de incercare). Cheia de incercare indic linia (sau liniile) de inceput pentru primul (sau primele caractere) ale textului in clar ca in exemplul urmtor. Apoi caracterele textului in clar sunt folosite drept chei pentru alegerea liniilor in criptare.Exemplu:Relum exemplul anterior, dar alegem litera M drept cheie de incercare.Obinem:Cuvant cheieMASOSITTIMPU

Text n clarASOSITTIMPUL

Text cifratMSGGABMBUBJF

Observaie:Se remarc introducerea unei reacii in procesul de criptare, textul cifrat fiind condiionat de coninutul mesajului.O alt variant a cifrului Vignre estecifrul Vignre cu autocheie (cheie cifrat).Dup criptarea cu cheie de incercare, fiecare caracter succesiv al cheii in secven se obine de la caracterul cifrat al mesajului i nu de la textul in clar.Exemplu:Cuvant cheieMMESKSLEMYNH

Text n clarASOSITTIMPUL

Text cifratMESKSLEMYNHS

Observaie:Dei fiecare caracter utilizat drept cheie poate fi gsit din caracterul anterior al textului cifrat, el este funcional dependent de toate caracterele anterioare ale mesajului, inclusiv de cheia de incercare.Urmare a acestui fapt este efectul de difuziune a proprietilor statistice ale textului in clar asupra textului cifrat, ceea ce face ca analizele statistice s devin foarte grele pentru un criptanalist.In baza standardelor actuale, schemele de cifrare Vignre nu sunt foarte sigure; contribuia important a lui Vignre const in faptul c a descoperit c pot fi generate secvene nerepetitive drept cheie, prin utilizarea a insui mesajului sau a unor pri ale acestuia.3.5.2Cifruri de transpoziie (transposition ciphers)[Patriciu (1994)]Cifrurile de transpoziiese caracterizeaz prin faptul c textul in clar rmane acelai, doar ordinea caracterelor se schimb.Exemplu:Cifrul simplu cu transpunere in coloane: textul in clar se scrie orizontal intr-o anumit form, ca la Polybius sau ceva asemntor, iar textul cifrat se citete pe vertical (coloane):"VVVEIINDCIII"

VENI

VIDI

VICI

O simpl transpoziie permite pstrarea proprietilor statistice ale textului in clar i in textului cifrat; o nou transpoziie a textului cifrat mrete securitatea cifrului.Utilizri:ADFGVX [Scheneier], utilizat de germani in timpul primului rzboi mondial are un cifru substituie combinat cuo alt substituie; dei pentru acea vreme a fost foarte complex, el a fost spart de criptanalistul francez Georges Painvin.Muli algoritmi moderni folosesc transpoziia, dar consumul de memorie este mare comparativ cu substituia, care din acest punct de vedere este mai convenabil.3.5.3Maini rotorIn vederea mecanizrii complicatelor metode de substituie i permutrilor repetate, in anul 1920 au fost inventate o serie de echipamente mecanice de criptare bazate pe principiul de rotor.Omain rotor (rotor machine)are o tastatur i o serie de rotoare ce permit implementarea unei versiuni a cifrului Vigenere.Fiecare rotor face o permutare arbitrar a alfabetului, are 26 de poziii i realizeaz o simpl substituie.Deoarece rotoarele se mic cu viteze de rotaie diferite, perioada unei maini cunrotoare este.Cel mai celebru cifru bazat pe o main rotor este Enigma, utilizat de germani in cel de-al doilea rzboi mondial. El a fost inventat de Arthur Scherbius i Arvid Gerhard Damm in Europa i a fost patentat in SUA. Germanii au imbuntit considerabil proiectul inventatorilor si, dar a fost spart de criptanalitii polonezi care au explicat atacul lor englezilor.3.6Protocoale criptografice3.6.1GeneralitiProtocolul criptograficeste un protocol in care este implicat cel puin un algoritm criptografic.Scopulunui protocol criptografic este de a nu permite s se fac sau s se invee mai mult decat este specificat in protocol.Protocoale in care intervin probleme de securitate i incredere se aplic in viaa de zi cu zi aproape pentru orice situaie: cumprturi, vot, joc, etc. Forma lor este foarte simpl pentru c presupune prezena oamenilor.In momentul in care activitile de zi cu zi se transpun pe reele de calculatoare, interaciunile umane fa in fa se reduc i trebuie luate in considerare o serie de probleme noi ce complic protocolul in vederea realizrii unei anumite sarcini.Observaie:In analiza unui protocol nu intereseaz modul de implementare, el trebuind s rman acelai in orice condiii de implementare.Principalele tipuri de protocoaleProtocoalele se pot clasifica in trei categorii mari: arbitrate, adjudecate i liber consimite.1)Protocoalele arbitrate (arbitrated protocols)- caz in care comunicaia intre cei doi corespondeni A i B se desfoar prin intermediul unuiarbitru (TTP- trusted third part).Arbitrul reprezint o a treia parte implicat in protocol, constituind o persoan de incredere notat de acum inainte cu I in desfurarea protocolului.Noiunea de incredere se refer la faptul c toi partenerii din protocol accept ca adevr verdictul dat de acesta.In lumea real arbitrii sunt: bancheri, judectori, notari publici. Intr-un protocol realizat intr-un sistem informatic, un arbitru este un banal program de calculator. Arbitrii sunt necesari cand apar tranzacii intre parteneri care nu se cunosc i/sau nu au incredere unul in altul.Exemplu:Realizarea unui act de vanzare de la A la B se face conformfig 3.3unde:A, B - partenerii tranzacieiI - arbitru (persoan de incredere).

Figura 3.3- Protocol arbitratProtocolul se desfoar dup cum urmeaz:(1)A d titlul de proprietate lui I;(2)B d cecul lui A;(3)A depune cecul lui B pentru operare;(4)Dup un timp specificat, I d lui B titlul de proprietate al lui A.Dac operaiunea (3) nu se efectueaz (cecul nu are acoperire) in timpul de ateptare specificat, A ii arat arbitrului probe de neefectuare a plii i I ii restituie lui A titlul de proprietate, deci (4) nu se efectueaz.Prezena unui arbitru intr-o reea de calculatoare are o serie de implicaii:-costuri suplimentare;-intarzieri inerente in protocol;-arbitrul constituie un punct de"gatuire"a comunicaiei in cazul unui numr mare de utilizatori; pentru a evita acest dezavantaj s-ar putea crete numrul arbitrilor implicai in protocol, cu creterea evident a costurilor;-faptul c arbitrul este unicul partener din reea in care trebuie avut incredere, face ca el s devin un punct vulnerabil ("coruptibil") pentru oricine dorete s distrug reeaua.2)Protocoale adjudecate (adjudecated protocols)Pentru a reduce costurile unui protocol arbitrat care necesit prezena permanent a unui arbitru. Se pot imagina protocoale in care prezena arbitrului este necesar doar in caz de disput, in rest protocolul desfurandu-se fr arbitru. In consecin, un asemenea protocol va conine dou subprotocoale: unulnearbitrat -executat de fiecare dat cand prile doresc executarea lui - i al doileaadjudecat, executat doar in condiiile unei dispute intre parteneri. Acest arbitru are rolul unui judector care in cazul unei dispute, in baza probelor prezentate de parteneri, va da un verdict rezolvand astfel disputa.Infig 3.4. este reprezentat un protocol adjudecat impreun cu partenerii implicai in acesta:A, B - partenerii tranzaciei;I - arbitru (numai in caz de disput);PAi PB- probe ale partenerilor A i B necesare a fi prezentate arbitrului in caz de disput.

Fig. 3.4- Protocol adjudecatUn protocol adjudecat se desfoar dup cum urmeaz:subprotocolul nearbitrat(1)A i B negociaz termenii contractului;(2)A semneaz contractul;(3)B semneaz contractul.subprotocolul arbitrat(in caz de dispute)(4)A i B apar in faa arbitrului I;(5)A prezint probele PA;(6)B prezint probele PB;(7)din analiza probelor, I hotrte verdictul.In calculatoare, protocoalele adjudecate se utilizeaz atunci cand intre parteneri relaiile se bazeaz pe cinste; dac un partener are suspiciuni de inelciune, exist posibilitatea ca o a treia parte (arbitrul I) s determine dac i cum a inelat. Deci protocoalele adjudecate nu previn inelciunea, dar o detecteaz; inevitabilitatea deteciei acioneaz ca o prevenie i descurajeaz inelciunile (ca in cazul magazinelor cu autoservire i sistem de monitorizare: nu se controleaz sacoa clientului decat in caz de inelciune).3)Protocoale autoimpuse(self - enforcing protocols)Sunt cele mai simple i mai eficiente dintre protocoale.Fig 3.5prezint o schem a funcionrii unui astfel de protocol.

Fig. 3.5- Protocol autoimpusNu exist arbitru i nici dispute pentru c protocolul insui garanteaz cinstea. Dac unul dintre parteneri incearc s inele, ceilali pot detecta inelciunea i protocolul se oprete.In [Scheneier], autorul afirm c"in cea mai bun dintre toate lumile posibile toate protocoalele ar fi autoimpuse". Rmane de vzut dac o asemenea lume este posibil i - in caz afirmativ -cand va fi aceasta.3.6.2Protocoale pentru comunicaii criptografice simetriceUn sistem criptografic simetric - care evideniaz i principalele atacuri - este dat infig. 3.6i are ca i participanti pe:A, B - parteneri ai protocolului;F, H - atacator pasiv (filaj) respectiv activ (hot);

Fig 3.6- Criptosistem simetric cu evidenierea atacurilor posibileUn protocol de comunicaie confidenial intre A i B se desfoar dup cum urmeaz:(1)A i B cad de comun acord asupra unui criptosistem simetric;(2)A i B aleg cheia k (secret), cea mai bun fiind cheia de unic folosin (one time pad) pentru o comunicaie;(3)A trimite lui B mesajul M criptat cu cheia k:(3.12)(4)B decripteaz mesajul criptat primit de la A, utilizand aceeai cheie k:.(3.13)Se pune intrebarea: ce pot face atacatorii in acest caz?Rolul atacatorului pasiv (F):el urmrete derularea pasului (3), in vederea criptanalizei (este un atac asupra textului cifrat); dac algoritmul rezist la acest atac, F nu poate face criptanaliz decat prin"atacul forei brute", deci cu o cheie bine aleas i ca lungime, F nu va afla nimic.Rolul atacatorului activ (H):poate incerca intreruperea comunicaiei in pasul (3);poate inlocui mesajul lui A (M) cu mesajul su M'dac afl cheia k prin criptanaliz;dac nu afl cheia k, va putea inlocui C cu,(3.14)ceea ce va face ca B s decripteze un mesaj lipsit de sens i-l va determina pe B s trag concluzia c A (sau sistemul) are probleme serioase de comunicare.Din examinarea de mai sus, putem trage concluzia cpentru sisteme criptografice simetrice problemele sunt:cheiaktrebuie distribuit in secret, ceea ce pentru sisteme mari constituie o problem deosebit;in cazul compromiterii cheii prin furt sau criptanaliz, sistemul este compromis;dac se utilizeaz chei diferite pentru fiecare pereche de utilizatori, numrul cheilor crete rapid cu numrul utilizatorilor (n):.(3.15)3.6.3Protocoale pentru comunicaii criptografice asimetrice (cu chei publice) i hibrideIn cazul criptosistemelor cu chei publice, fiecare utilizator are o pereche de transformri (chei):- transformarea (cheia) public, accesibil public;- transformarea (cheia) privat, inut secret.In consecin, doi parteneri A i B ai unui protocol care utilizeaz un criptosistem cu chei publice vor aveai, undeisunt chei publice, putand fi luate dintr-un fiier public asemntor unei cri de telefon.Protocolul de comunicare intre A i B are urmtorii pai:(1)A i B cad de comun acord asupra unui criptosistem cu chei publice i selecteaz dintr-o banc de date cheile publice ale partenerilor de comunicaie, respectiv.(2)A cripteaz mesajul sucu cheia public a lui B(3.16)i il trimite lui B.(3)B decripteazutilizand cheia sa privati afl pe:.(3.17)(4)B cripteaz mesajul sucu cheia public a lui A:(3.18)i-l transmite lui A.(5)A decripteazutilizand cheia sa privat i afl pe:(3.19)Observaii:Managementul cheilor este mult mai simplu in cazul criptosistemelor cu chei publice, numrul perechilor de chei fiind egal cu cel al utilizatorilor, iar in vederea comunicrii nu este necesar transmiterea cheii secrete intre utilizatori, ci doar a cheii publice a corespondentului care se citete uor dintr-o banc de date accesabil public.Criptosistemele cu chei publice sunt vulnerabile la atacul cu text in clar la alegere (dat fiind c cheia de criptare este public), dar atacurile sunt dificile pentru c E i D sunt funcii neinversabile cu trap [deci necunoaterea trapei face aproape imposibil deducerea lui M din E(M)].Criptosistemele cu chei publice nu sunt un inlocuitor al criptosistemelor simetrice, in primul rand deoarece primele sunt de circa 1000 de ori mai lente.Sisteme cu chei publice se folosesc doar la transmiterea secret acheii de sesiunefolosite pentru comunicaie in sisteme cu chei simetrice.Un asemenea sistem se numetecriptosistem hibrid (hybrid cryptosistem).Protocolul de comunicaie intr-un criptosistem hibrid este alcatuit din urmatorii pasi:(1)A i B convin asupra unui criptosistem cu chei publice i obin cheile publice ale parteneruluirespectiv;(2)A genereaz o cheie aleatoare de sesiunekpe care o cripteaz cu:(3.20)i o transmite lui B;(3)B decripteaz pecu cheia sa privati obine cheia de sesiune:(3.21)(4)In comunicaiile ulterioare, pentru confidenialitate, A i B vor folosi aceeai cheie de sesiuneki un criptosistem simetric.Concluzie:Generarea cheii de sesiunekdoar cand se dorete comunicarea i distrugerea ei dup incheierea comunicrii face ca atacurile pasive s fie mult mai puin eficiente.Observaie: In cadrul acestui paragrafsi in continuare, pentru a comprima scrierea s-au folosit denumirile improprii de cheie public respectiv privat pentru transformrile respective care includ cele dou tipuri de chei; avem convingerea c aceast notaie"neortodox"nu va produce confuzii de inelegere cititorului.3.6.4.Protocoale pentru semnturi digitale3.6.4.1Ce este o semntur digital ?Semntura olografeste o prob a calitii de autor al unui document, sau cel puin de acord cu coninutul documentului.Proprietile unei semnturi olografe sunt:1)Semntura s fie autentic, adic s aib calitatea de a convinge destinatarul c semnatarul a semnat documentul in mod deliberat.2)Semntura s nu poat fi refolosit, ceea ce inseamn c semntura este parte a documentului.3)Documentul semnat nu poate fi modificat.4)Semntura nu poate fi repudiat.Semnturile digitale trebuie s pstreze cerinele 1)4), transpuse in comunicaia din reele de calculatoare.Observaie:Exist destule situaii in care cerinele 1)4) nu se respect pentru o semntur olograf, dar aceste nerespectri sunt mult mai greu de realizat decat in cazul calculatorului, la carecopyipastesunt comenzi atat de uzuale.Cele patru cerine, transpuse in mediul digital se rezum la dou cerine de baz pentru o semntur:(1)s depind de mesaj pentru a nu fi mutat de pe un mesaj pe altul (aceast cerin nu apare in cazul semnturii olograf pentru c nu este cazul);(2)s depind de emitor pentru a nu putea fi falsificat.Semntura digital S[Menezes] este o succesiune de bii obinut din transformarea mesajului (M) i a unei informaii secrete, tiute doar de emitor.Orice semntur digital trebuie s poat fi verificat, rezultatul acestei funcii putand fi doar"adevrat"sau"fals".In cele ce urmeaz vom folosi notaiile:- transformarea de semnare pentru entitatea A (ea este secret);- transformarea de verificare pentru entitatea A (ea este public);- perechea de transformri care definete schema (mecanismul) de semntur digital.v- rezultatul verificrii .Protocolul de semnare este:(1)A calculeaz(3.22)care este semntura mesajului M (folosind o cheie secret);(2)A transmite perechea .Protocolul de verificare:(1)Verificatorul (B) obine funcia de verificare a lui A:, care este public;(2)B calculeaz funcia de verificare;(3.23)(3)B accept c S apartine lui A dac v = adevrat i o refuz dacv= fals.Observaie:Transformateleisunt tipic caracterizate de cate o cheie (secret, respectiv public).Pentru funciile de semnare, respectiv de verificare, se cer proprietile:(a)S este o semntur valid a lui A asupra mesajului M dac i numai dac:adevrat;(3.24)(b)este imposibil de determinat pentru altcineva decat A un M i S astfel incat:adevrat.(3.25)

Fig.3.7- Reprezentarea grafic a procedurii de semnare a) i verificare b)Observaie:Semnturile trebuie s fie verificabilepentru cain caz de conflict s nu poat fi repudiate sau reclamate in mod fraudulos; un arbitru trebuie s poat rezolva disputa fr a avea nevoie de cheia privat a lui A.Aplicaii:autentificareintegritatea datelornerepudierecertificarea datelor publice in reele mariRealizri:exist numeroi algoritmi pentru semnturi digitale, toi necesitand informaie secret pentru semnare i informaie public pentru verificare;in cazul algoritmilor cu chei publice, cheia privat folosit la criptare:poate fi folosit la semnare, iar cheia public folosit la criptare:poate fi folosit pentru verificare (acesta este cazul algoritmului RSA);in cazul altor algoritmi, implementrile pot fi diferite; de exemplu, pentru algoritmii bazai pe funciihash(de rezumare) i cu certificare temporal (TS) se adaug pai suplimentari pentru semnare i verificare;3.6.4.2Protocol de semnare cu criptografie simetricFiesituaia 1in care A semneaz un mesaj digital pe care vrea s-l trimit lui B. Protocolul se desfoar astfel:(1)A trimite arbitrului I mesajulcriptat cu cheia sa:(3.26)(2)I decripteaz, deci obine pe, la care adaug o declaraie de autentificare () a primirii mesajului de la A i le trimite lui B, cripate cu cheia lui B:(3.27)(3)B decripteazi poate citi pecat i certificarea lui I:(3.28)Fiesituaia 2in care B vrea s-i arate lui C mesajul lui A. Paii algoritmului sunt:(1)B ii trimite arbitrului I mesajul lui A i certificarea sa, criptate cu cheia sa proprie:(3.29)(2)I decripteazi gsete pe(3.30)(3)I verific in baza de date dac il are pe(4)I cripteaz cu cheia lui C mesajulprecum i certificarea sai il trimite lui C:(3.31)(5)C decripteazi citete peprecum i certificarea(3.32)Concluzii:Aceste protocoale sunt bune, dar extrem de laborioase, totul tranzitandprin II trebuie s in o baz de date cu cheile tuturor utilizatorilor cat i a mesajelor certificate, astfel incat devine un punct de"strangulare"a traficului i in acelai timp extrem de vulnerabil la atac, deoarece el deine practic toate informaiile. In plus, ca orice protocol arbitrat este mai costisitor decat unul nearbitrat.Propunem cititorului, ca exerciiu, s analizeze indeplinirea cerinelor unei semnturi digitale in cele dou cazuri prezentate.O ilustrare grafic a acestor dou situaii este prezentat infig. 3.8.

Fig 3.8- Ilustrarea grafic a protocolului de semnare utilizand criptosisteme simetrice3.6.4.3Protocol de semnare utilizand criptografie cu chei publiceProtocol de semnare (fr criptare)parcurge urmatorii pai:(1)A semneaz mesajul M cu cheia sa privat;(3.33)(2)A transmiteluiB (necriptat);(3)B verificfolosind cheia public a lui A:.(3.34)Observaie:Acest protocol este superior celui cu chei simetrice pentru c nu necesit arbitraj.Protocol de semnare cu criptareObservaii:Exist algoritmi cu chei publice care pot fi utilizai atat pentru semnturi digitale (S) cat i pentru criptare: de exemplu RSA poate fi folosit la semntur i confidenialitate, in acest caz fiind indeplinite condiiile:i.(3.35)Ali algoritmi cu chei publice, de exemplu DSA [Scheneier][Patriciu (1994)], se utilizeaz doar pentru semntur, neputand fi utilizai pentru criptare.Protocolul de semnare cu criptare se desfaoar astfel:(1)A semneaz mesajul M cu cheia privat;(3.36)(2)A cripteaz mesajul criptat cu cheia public a lui B i il trimite acestuia;(3.37)(3)B decripteazC1cu cheia privat;(3.38)(4)B verific semntura lui A cu cheia sa public.(3.39)Observaii:A semna inainte de a cripta este natural. Cand A scrie o scrisoare, semneaz inainte de a pune scrisoarea in plic.Utilizarea aceleiai perechi de chei (E, D) pentru semntur i criptare nu este obligatorie (cheile pot avea dimensiuni diferite i pot expira la date diferite).Retransmiterea mesajului,ca o confirmare de primire(resending the message as a receipt)se face parcurgand urmtorii pai:(5)B, dup verificarea lui, retransmite M semnat () la A cu o confirmare de primire:;(3.40)(6)A decripteazcu cheia sa privat, verificcu cheia public a lui B i dac M este acelai cu cel transmis de el, A tie c B a primit mesajul:(3.41), identic cu cel transmis de A.(3.42)Atacul de retransmitere(confirmare de primire)Ipotez: H (atacatorul) este un utilizator legitim al sistemului deci are o pereche de chei public-privat.Atacul const din urmtorii pai:(1)H inregistreaz mesajul lui A ctre B in pasul (2);(3.43)(2)Dup un anumit timp, H trimite acest mesaj lui B pretinzand c vine de la H (dar nesemnat);(3.44)(3)B decripteaz mesajul(3.45)i verific semntura lui H;(3.46)(4)B continu protocolul i retransmite mesajul lui H(3.47);(3.48)(5)H decripteaz mesajul:;(3.49)(6)H aplic cheia public a lui B;(3.50)(7)H decripteaz inc o dat cu cheia sa privat;(3.51)(8)H aplic cheia public a lui A i obine pe M(3.52)i aa H poate citi corespondena.Atenie:dei semnalul decriptat de ctre B la pasul (3) este fr sens, el a continuat protocolul, generand astfel insecuritate; dac B ar fi verificat mesajul inainte de a-l retransmite, acest atac nu era posibil;nu semnai niciodat mesaje arbitrare de la alte persoane, nu decriptai mesaje arbitrare i nu difuzai rezultatele obinute de alii.Contracararea atacului de retransmiterese poate face prin utilizarea de:operaii distincte (chiar dac apropiate) pentru criptare respectiv semntur;chei diferite pentru criptare i semntur;algoritmi diferii pentru criptare i semntur;certificare temporal care fac ca semntura de intrare s fie diferit de cea de ieire;semnturi digitale cu funciihash.Pentru a preveni atacurile in criptografia cu chei publice, cheia public trebuie s fie protejet la accesul la scriere iar pentru a prevenii inlocuirea ei in timpul transmisiei, I(autoritate de certificare a cheilor- KDC) trebuie s semneze fiecare cheie public cu cheia sa privat.Cand A primete cheia lui B, verific semntura lui I, ceea ce impiedic posibilitatea inlocuirii ei in transmisie.3.6.4.4Protocol de semnare i certificare temporal (TS - time stamping)Dac A a semnat un cec ctre B, acesta poate incasa banii i apoi reutiliza o copie a contractului semnat. Prevenirea acestei situaii se poate face prin certificare temporal (TS):.(3.53)3.6.4.5Protocol de semnare cu sisteme cu chei publice i funcii hashFuncii de dispersie (hash)Funciilehash- cunoscute i sub denumirea defuncii de compresie(compression),contracie(contraction) sau derezumat al mesajului(message digest) oriamprent digital(fingerprint) - sunt funcii care au la intrare un ir de date de lungime variabiln- numitpreimagine- i la ieire dau un ir de lungime fixm(uzual 128 sau 160 de bii) numitvaloarea funcieihash h(hash value- HV).

Fig. 3.9- Ilustrarea grafic a conceptului de funciehashObservaie:In [Patriciu (1994)] funciahasheste denumit funcie de dispersie.Proprieti:valoareahashconstituie o amprent digital a intrrii; dac dou iruri de la intrare dau aceeai valoarehash(h) nu se poate spune cu certitudine c cele dou iruri sunt identice, dar probabilitatea ca ele sa fie diferite este extrem de mic:, deci funciilehashpot fi utilizate pentru a indica un grad destul de mare de asemnare;valoareahash(h) se calculeaz extrem de uor;irul de intrare (preimaginea) se determin destul de greu cand se cunoateh; aceast proprietate impreun cu cea precendent justific incadrarea funciilorhashin categoria funciilor neinversabile (one-way hash);functiahasheste ofuncie"fr ciocnire"(collision-free) in sensul c este greu de determinat dou preimagini care s aib aceeai valoarehash(h);funciahasheste public.Aplicaii:in tranzacii financiare;heste oamprent digital a fiierelor; dac vrei s verifici c cineva are acelai fiier pe care il ai i tu, fr s-l transmit, ii ceri valoareahash. Dac valoareahashtransmis este identicacu cea calculatade tine atunci esteaproape sigurc acea persoan are acel fiier;coduri de autentificare a mesajelor[Scheneier] care constau din calcularea luihi semnarea acesteia cu o cheie secret astfel incat doar cel care deine cheia secret k poate verifica peh:MAC -message autentication codeDAC -data autentication codeObservaie:Dac documentele semnate M sunt mari, semnarea lor utiulizand chei publice este ineficient. Pentru a reduce timpul, nu se semneaz M cih(valoareahasha lui M).Pasii protocolului de semnare sunt:(1)A i B convin asupra algoritmului de semntur digital i a funcieihashfolosite.(2)A calculeaz valoareahasha lui M:h= H(M);(3.54)(3)A semneaz pehcu cheia sa privat:(3.55)(4)A trimite M ictre B, criptat cu cheia public a lui B:(3.56)(5)B decripteazi gsete M idup care determin pehi il compar cu cel decriptat.(3.57)(a)(3.58)(b)(3.59)dac (a) este echivalent cu (b) atuncieste validat.Avantaje:vitez mare;securitate sporit: probabilitatea de a avea douavalorihashidentice este, undenreprezint lungimea valoriihashin bii;poate fi pstrat separat de documentul M, ocupand o memorie mult mai mic.Utilizri:sisteme de arhivare fr citirea documentelor;obinerea dreptului de autor prin pstrarea secretului documentului.3.6.4.6Protocoale pentru semnturi multipleFr funcii hashA i B semneaz cate o copie (separat) a documentului M, deci mesajul rezultat, avand ambele copii, este dublu ca dimensiune.Un astfel de protocol are doi pasi:(1)A semneaz primul documentul M:;(3.60)(2)B semneaz al doilea:.(3.61)Verificarea semnturii lui A:,(3.62)este imposibil fr verificarea semnturii lui B.Cu funcii hashIn acest caz protocolul va arata astfel:(1)A semneaz valoareahasha lui M:(3.63)(2)B semneaz valoarehasha lui M:(3.64)(3)B trimitelui A(4)A trimite catre C pe(5)C verifici3.6.4.7Protocol de semnturi digitale i nerepudiereA poate inela semnand un document i apoi pretinzand c nu l-a semnat; invoc pierderea sau furtul cheii private deci repudiaz pe. Certificarea temporal limiteaz acest efect, dar el exist dac A dateaz documentul dup dorin. Asemenea situaii sunt evitate cu protocolul:(1)A semneaz mesajul:;(2)A genereaz un antet de identificare (AI), concateneaz antetul cu, semneaz totul:(3.65)i trimite arbitrului I;(3)ArbitrulI verifici confirm informaiile de identificare AI. I adaug o certificare temporal (TS) la, semneaz totul(3.66)i trimite la A i B;(4)B verific, identificand pe AI i;(5)A verific, deci mesajul trimis de I lui B. Dac nu-i gsete propria semnturapare o disput.Observaie:Aceast problem poate fi soluionat i de protocoale adjudecate; propunem cititorului ca exerciiu aceast a doua cale.3.6.4.8Semnturi in alb (blind signatures) [Scheneier]O trstur esenial a protocoalelor cu semnturi digitale este c semnatarul cunoate ceea ce a semnat. Exist situaii in care anumite persoane semneaz documente fr s fi vzut niciodat coninutul acestora. Sunt ci prin care semnatarul poate cunoate aproximativ, dar nu exact, ceea ce semneaz.Semnturi complet in alb(completely blind signatures)Fie exemplul:B - notar publicA - dorete ca B s semneze un document, dar nu dorete ca B s tie coninutul documentului; pe B nu-l intereseaz coninutul documentului, doar certific c acesta a fost notarizat.Protocolul de semnare se desfoar astfel:(1)A ia documentul i il aleatorizeaz; aceast valoare aleatoare se numetefactor de ascundere(blinding factor);(2)A trimite documentul"ascuns"(blinded) lui B;(3)B semneaz documentul"ascuns";(4)A inltur factorul de ascundere (dezaleatorizeaz documentul), obinand documentul original semnat de B.Proprietile unei semnturi complet in alb:1)semntura lui B pe document este valid; semntura este dovada c B a semnat documentul i are toate proprietile unei semnturi digitale.2)B nu poate corela documentul semnat cu actul de semnare propriu-zis; chiar dac el ar ine o copie a tuturor semnturilor in alb acordate, el nu ar putea determina cand anume a semnat un anumit document.Risculsemnturilor complet in alb:A il poate face pe B s semneze orice, de exemplu"B datoreaz lui A 1.000.000 $".Semnturi in alb (blind signatures)Pentru a evita riscul menionat anterior, se va cuta o cale in care B s tie ce semneaz, meninand in acelai timp i proprietile utile ale semnturii in alb.Principiulfolosit este:taie i alege(cut and choose), ilustrat de exemplul controlului vamal. Controlul se face utilizand o soluie probabilisticaadic se controleaz o persoan din 10 [Scheneier] celelalte 9 nefiind controlate. Pedeapsa in cazul unei fraude este atat de mare incat s descurajeze tentativa de fraud.Semntura in alb lucreaz ca in exemplul anterior. Lui B i se va da un numar mare de documente"ascunse"la semnat. El va deschide tot, exceptand ultimul document pe care il semneaz fr a-l deschide.Documentul ascuns se afl in plic. Procesul de ascundere echivaleazacu punerea documentului in plic. Procesul de inlturare a factorului de ascundere poate fi comparat cu deschiderea plicului.Un alt exemplu de utilizare de semnturi in alb este agenia de contraspionaj. [Scheneier]Fie un grup de ageni de contra-spionaj; identitatea lor este secret chiar i pentru agenie. Directorul ageniei vrea s dea fiecrui agent un document semnat care s-i ofere imunitate diplomatic. Fiecare agent are propria list cu nume de acoperire i nu dorete ca agenii s o cunoasc de teama spargerii calculatorului ageniei. Pe de alt parte agenia nu dorete s semneze in alb absolut orice document pentru a preintampina situaii de genul:"Agentul X a fost pensionat i pensia anual este de 1.000.000 $".Presupunem c fiecare agent are 10 nume de acoperire cunoscute doar de el.Fie:A - computerul agenieiB - agentul sub acoperireProtocolul de semnare in alb decurge astfel:(1)B pregtetennume, fiecare cu alt nume de acoperire, care ii confer imunitate diplomatic.(2)B aleatorizeaz fiecare document cu un factor de ascundere diferit.(3)B trimite celendocumente ascunse lui A.(4)A alege (n-1) documente la intamplare i ii solicit lui B factorii de ascundere.(5)B trimite lui A cei (n-1) factori de ascundere solicitai.(6)A deschide cele (n-1) plicuri, deci inltura factorul de ascundere i se asigur de coninutul acestora.(7)A semneaz ultimul document nedeschis i-l trimite lui B.(8)B inltur factorul de ascundere i citete noul nume de acoperire ce-i asigur imunitate diplomatic: Ion Ionescu.3.6.5Protocoale pentru schimbul de cheiIn tehnica criptografic uzana este de a utiliza o singur cheie pentru fiecare comunicaie criptat numitcheie de sesiune(key session).3.6.5.1Schimb de chei cu criptografie simetricPasii protocolului pentru schimb de chei in criptografia simetricasunt:(1)A cere arbitrului I ocheie de sesiune pentru a putea comunica confidenial cu B;(2)I genereaz o cheie de sesiune k i cripteaz douacopii cu cheile secrete ale lui A, respectiv Bii le trimite lui A:;(3)A decripteaz cu cheia sa secret i gsetek:;(3.67)(4)A trimite lui B copia cheii de sesiunek, criptat cu cheia secret a lui B ();(5)B decripteaz cu cheia sa secret i gsetek:;(3.68)Atat A cat i B pot comunica confidenial utilizandk.

Fig. 3.10- Protocol de schimb de chei in criptografia simetricObservaii:A i B au fiecare de la I (centrul de distribuie a cheilor CDC)i;acest protocol presupuneabsoluta securitate a lui I, chiar dac acesta este un program de calculator;I are copia tuturor cheilor k, deci poate citi tot traficul din reea, fiind un punct foarte vulnerabil pentru atacuripotenial I este un punct de"strangulare"a traficului in reea.3.6.5.2Schimb de chei cu criptografie cu chei publicePrincipiul:A i B utilizeaz criptografia cu chei publice pentru a stabili cheia de sesiunekComunicaia confidenial intre A i B se face cu criptografie simetric.Protocolul este:(1)A i B ii procur de la I (CDC - centru de distribuie a cheilor, KDC -key distribution center) cheile publicei;(2)A genereaz o cheie de sesiune aleatoarekpe care o cripteaz utilizand cheia public a lui B i o trimite la B:;(3)B decripteaz mesajul primit de la A utilizand cheia sa privat:;(3.69)(4)A i B comunic confidenial intre ei folosind cheia cheia secretk.

Fig 3.11- Protocol de schimb de chei in criptografia asimetricn cazul acestui protocol poate avea loc:Atacul"om la mijloc"(man in the middle attack), ce const in:(1)H - atacatorul activ, inlocuiete cheia public a lui A sau B cu cheia sa public:(in timpul transmiterii de la A la B i invers, fieintr-o baz de date a CDC);(2)toate mesajele criptate in acest caz de A i B vor trece pe la H care le va decripta cu uurin;Protocolul de interblocare(interlock protocol)Pentru a contracara atacul de"om la mijloc", Ron Rivest i Adi Shamir au inventat protocolul de interblocare.Paii acestuia sunt:(1)A i B intr in posesia cheilor publiceifie de la CDC fie transmiandu-le direct unul altuia;(2)A cripteazcui transmite jumtate din criptograma:;(3.70)(3)B cripteazcui transmite jumtate din criptograma:;(3.71)(4)A trimite lui B cealalt jumtate din;(5)B pune impreun cele dou jumti recepionate de la A i le cripteaz cu cheia sa privat:(3.72);(3.73)(6)A procedeaz identic i obine.Observaii:H nu mai poate face nimic deoarece jumatate dinsaunu are utilitate deoarece jumatate din mesaj poate reprezenta, de exemplu, tot al doilea bitpentru un algoritm de tip bloc;decriptarea poate depinde de vectorul de iniializare, care se poate transmite in a doua jumtate a mesajului;prima jumtate a mesajului poate fi o funciehasha mesajului criptat, iar cea de-a doua parte poate fi chiar mesajul criptat.3.6.5.3Schimb de chei cu semnturi digitaleDac in schimbul de chei se utilizeaz semnturile digitale, se poate preveni atacul"om la mijloc".Exist unarbitru I (CDC)care semneazi. Cand A i B primesc cheile, fiecare verific semntura lui I, dup care protocolul se desfoar ca in subcapitolul 3.6.5.2.Observaii:H este in imposibilitate de atac;si in acest caz exist riscul compromiterii lui I (CDC), dar acesta este mai mic decat in sectiunea 3.6.5.2; obinerea lui(cheia privat a lui I) este folosit doar pentru semnarea cheilor, nepermiand acestuia decriptarea cheilor de sesiune precum i a traficului din reea;atacul poate fi reuit dac H inlocuiete pecu, dar aceasta inseamn c H interceptez i modific datele din CDC, ceea ce este mult mai greu decat a sta pasiv intr-o reea i a privi mesajele;intr-un canal de difuziune (reea radio) este aproape imposibil de a inlocui un mesaj cu altul fr blocarea intregii reele, in reele de calculatoare acest lucru este din ce in ce mai uor.3.6.5.4Transmiterea cheilor i mesajelorPrincipiul:transmiterea criptat de mesaje, fr existena prealabil a unui protocol de schimb de chei.Pasii ce trebuie parcursi sunt:(1)A genereaz o cheie aleatoare de sesiuneki o folosete la criptarea lui M:;(2)A selecteaz dintr-o baz de date public cheia lui B:;(3)A cripteaz pekcu cheia public a lui B:;(4)A transmite lui B atat mesajul criptat:cat i cheia criptat:;(5)B decripteaz pek:(3.74)(6)B obine pe M folosind la criptare un algoritm simetricsi cheiak:.(3.75)Observaii:acest algoritm hibrid este cel mai folosit in sistemele de comunicaie;pentru mrirea securitii in cazul atacului"om la mijloc",A poate semna transmisiunea in pasul (4);algoritmul poate fi combinat cu:-semntura digital-certificarea temporal-alte protocoale de securitateceea ce conduce la imbuntirea securitii acestuia.3.6.5.5Difuzarea cheilor i a mesajelorProtocolul de difuzare a cheilorsi mesajelor constain:(1)A genereaz o cheie de sesiuneki cripteaz pe M:;(2)A selecteaz dintr-o baz de date cheile publice:,,i cripteaz cheiak:,,;(3)A difuzeazi,,;(4)Doar B, C i D pot decriptaki apoi pot obine pe M.Observaie:Un server central poate distribui,,; el ins nu trebuie s fie de incredere, deoarece el nu este capabil s decripteze nici un mesaj.3.6.6 Protocoale de autentificare[Scheneier]Problema: dac A intr intr-un calculator (ex: sistemul bancar telefonic) cum tie calculatorul cine este acesta? De unde are calculatorul garania c nu este H care incearc s foloseasc identitatea lui A?Problema anterioar se rezolv tradiional prin"parole"P. A introduce parola i calculatorul verific dac este corect. Parola se cere de fiecare dat cand A dorete s acceseze calculatorul.3.6.6.1Autentificare cu funcii neinversabile (f)Roger Needham i Mike Guy au artat c calculatorul nu trebuie s cunoasc parola.El trebuie doar s fac distincie intre parolele corecte i cele incorecte.Acest lucru se realizeaz uor cu funcii neinversabilef. In loc de memorarea parolelor, calculatorul memoreaz.Modul de lucru este urmatorul:(1)A trimite calculatorului parola P;(2)Calculatorul calculeaz;(3)Calculatorul compar de fiecare datcu valoarea memorat;Observaii:acest algoritm atenueaz atacul la bnci de date in care sunt memorate parolele.nu sunt utile deoareceeste extrem de greu de calculat.Atacul de tip dicionarUn fiier de parole criptat cu o funcie neinversabil:este inc vulnerabil:-H poate incerca de exempluparole (cele mai uzuale) pentru care calculeazi memoreaz rezultatele; dac fiecarerezultacafiierul are 8 MB (deci nu este exagerat de mare).-H fur din calculator listai o compar cu lista calculat de el pentru a vedea potrivirile.Acesta esteatacul de tip dicionari este surprinztor de eficient.Sufixul (salt)Sufixul(salt)este - prin definiie - un ir aleatorcare se concateneaz cuinaintea calcularii luif;se memoreaz. Prezena luidiminueaz ansele unui atac de tip dicionar.Observaii:mulimeaeste mare;majoritatea sistemelor UNIX utilizeaz pentruunsir de 12 bii;exist programe de"ghicit parola"(password guessing program) care sparg i pe;nu este un panaceu universal; creterea lungimii luiprotejeaz la atacurile de tip dicionar asupra fiierelor parolate, nu ins asupra unui atac concentrat asupra unei singure parole;protejeaz persoanele care au aceeai parolpe maini multiple, dar nu sunt cu nimic mai bune decat parolele slab alese.3.6.6.2Autentificare cu chei publice[Scheneier]Problema:i in cazul folosirii sufixelor,este vulnerabil. In pasul (1) oricine are acces pe canal poate aflai, iar dac F are acces la memoriacalculatorului, poate vedeaiinainte de a se calcula.Soluiaar fi:-utilizarea criptografiei cu chei simetrice: calculatorul are un fiier cu toate cheile publiceiar utilizatorii ii in acas cheile private.Protocolul folosit in acest caz este:(1)Calculatorul trimite lui A un ir aleator X;(2)A cripteaz pe X cu cheia sa privati il trimite calculatorului;;(3.76)(3)Calculatorul, utilizand cheia public a lui A decripteaz;;(3.77)(4)Dac X decriptat la (3) este echivalent cu X transmis la (2), A are acces la sistem.Observaii:nimeni nu cunoate, deci nu se poate falsifica identitatea lui A;A nu transmite niciodatpe canal, deci nu sunt posibile atacuri pasive;cheia privattrebuie s fie lung i nenumeric i se calculeaz automat in hardul calculatorului sau in softul de comunicaie de unde necesitatea unui terminal inteligent de comunicaie in care A s aib incredere, in acest caz canalul i calculatorul gazd nu trebuie s fie sigure;pasul (1) este neobinuit: nimeni nu va cripta un ir arbitrar venit de nu se tie unde (calculatorul nu trebuie s fie sigur); pentru mrirea siguranei, algoritmul se modific dup cum urmeaz:(1)A genereaz un ir aleator, il cripteaz cu cheia sa secret i-l trimite calculatorului.(2)Calculatorul ii trimite lui A un ir aleator diferit: X.(3)A face o serie de calcule bazate pe numerele aleatoare (X i) i cheia privati trimite rezultatul calculatorului.(4)Calculatorul face o serie de calcule asupra numerelor primite de la A pentru a verifica dac A ii cunoate cheia privat.(5)Identitatea lui A este verificat, testand dac A ii cunoate cheia.3.6.6.3Autentificarea mesajelorProblema:Cand B primete un mesaj de la A, de unde tie c este autentic?Soluia:semnarea mesajuluide ctre A.Observaii:criptografia simetric furnizeaz o anumit autentificare cand B primete de la A un mesaj criptat cu cheia comun secretk, el tie c vine de la A, deoarece numai A cunoate cheia;B nu poate convinge o a treia parte de identitatea lui A; el nu poate convinge un arbitru (I) c mesajul vine de la A, dat fiind c atat A cat i B dein aceeai cheie, deci nu exist posibilitatea identificrii emitorului.3.7Algoritmi criptografici (cifruri)Algoritmul criptograficeste prin definitie funcia (funciile) matematic(e) utilizat(e) pentru criptare / decriptare.in general exist dou funcii destinate pentru:-criptare (E)-decriptare (D)atat criptarea cat i decriptarea sunt controlate de una sau mai multe chei criptografice.3.7.1Algoritmi simetriciAlgoritmii simetrici (dup cum s-a artat in seciunea 3.1.2)se clasific in dou categorii mari: algoritmi secveniali i algoritmi bloc.3.7.1.1Algoritmi secvenialiCaracteristici:textul in clar M este considerat ca un ir de simboluri dintr-un alfabet A; prin cifrare fiecare simbol al textului in clar este transformat intr-un alt simbol al mesajului criptat, deci la ieire se obine un ir de simboluri ale criptogramei.Notm:A - alfabetul mesajului in clar;C - alfabetul mesajului cifrat;S - cifrarea secvenial:.Observaii:dac, nu se recomand criptarea;cifrurile secveniale sunt o variant modern a cifrului Vigenere;cheia folosit in cazul acestor cifruri K este generat de un RDR (starea iniial i polinomul generator pot fi controlate prin chei).Criptarea constain operaia:.(3.78)iar decriptarea se realizeazaastfel:(3.79)undereprezintasuma modulo 2.Observaie:Pentru cifruri secveniale puternice se procedeaz la schimbarea periodic a coeficientilor polinomului generator iar pe timpul pauzelor intre mesaje, se vor transmite valorile aleatoare produse de un generator de zgomot.Recomandm cititorului consultarea bibliografiei: [Angheloiu et al. (1986)] pp. 78-91; [Patriciu (1994)] pp. 85-89 i [Scheneier] cap.16; iar pentruaplicaii[Scheneier] cap.17 : RC-4, SEAL, etc.3.7.1.2Algoritmi (cifruri) blocCaracteristici:mesajul in clar M este imprit in blocuri, de obicei de aceeai dimensiune, fiecare bloc fiind cifrat independent;cifrurile bloc sunt cifruri produs iterate avand la baz substituia i transpoziia;lungimile tipice ale blocurilor sunt: 32128 bii;anii de dezvoltare a cifrurilor bloc sunt anii '70 (la baza acestora stand lucrrile lui Shannon).Componentele de baz ale cifrurilor bloc sunt transformrile de:transpoziie - cutiile P (permutare P - box).substituie- cutiile S(sustituie S - box).Cutia PUn exemplu de cutie P este reprezentat infig. 3.12unde intrarile sunt notate cuiar iesirile cu.

Fig.3.12- Exemplu de cutie Ptransformrile operate de o cutie P sunt liniare, legturile interioare ale unei cutii P putand fi determinate prin punerea unui"1"la fiecare intrare i marcarea ieirii corespondenteCutia SCutia S este reprezentatafig. 3.13si constadin douaconvertoare (unul binar - zecimal (CBZ)si al doilea zecimal - binar (CZB)) precumsi dintr-o cutie P.intr-o cutie S se fac atat transformri liniare (prin P) cat i neliniare (prin CBZ i CZB);Numrul de permutri posibile pentru o cutie S cu n intrri este.Exemple:pentrun= 3 intrari vom aveaiesiri ale CBZ, decipermutri posibile in cutia P;dacn= 128 atunci vom aveaiesiri ceea ce face criptanaliza exhaustiv imposibil din punct de vedre tehnic.

Fig 3.13- Exemplu de cutie SIntrareM0M1M2C0C1C2Ieire

00001103

11001117

20100000

31100116

40010102

51010014

60111015

71111001

Tabelul 3.4- Strile intrrilor i ieirilor pentru cutia S dinfig. 3.13.Un cifru blocreprezintao alternan de cutii P i S. Un astfel de sistem de cifrare este exemplificat infig. 3.14.Caracteristici:cutiile P sunt fixe (fr cheie) i prin permutarea pe care o fac realizeaz"difuzia";cutiile S primesc la intrare atat informaia (4x4) cat i cheia de cifrare, care are rolul s comande substituia liniar; in acest fel cutiile S realizeaz"confuzia":bii; se folosesc cate doi bii pentru fiecare cutie S, ceea ce creaz posibilitatea selectrii uneia din 4 substituii posibile.

K''

Fig.3.14- Sistem de cifrare blocAplicaiile cele mai importrante sunt concretizate incifrurile LUCIFER, IDEA i DES. Dintre aceste aplicatii vom prezenta in continuare cifrul DES, cel mai utilizat; pentru ceilalti algoritmi recomandm consultarea bibliografiei.Sistemul DES(Data Encryption Standard)Caracteristici:lungimea unui bloc este de 64 de biti;cheia este pe 64 de biti dintre care 8 sunt biti de paritate;flexibilitatea implementrii i utilizrii in diferite aplicaii;fiecare bloc cifrat este independent de celelalte;nu este necesar sincronizarea intre operaiile de criptare / decriptare ale unui bloc;pentru creterea securitii se poate aplica algoritmul T-DES (triplu DES) care const in iterarea de trei ori a algoritmului DES.Dei d semne de"btranee"DES-ul s-a comportat excepional timp de 20 de ani la atacuri criptanalitice i este considerat inc sigur in numeroase aplicaii. Considerm c istoria apariiei sale merit a fi amintit [Scheneier], deoarece ea reprezint un model de conlucrare eficient a lumii tiinifice, a productorilor de echipamente, a consumatorilor i- in final - a factorului politic in dezvoltarea unei probleme de mare actualitate.Dezvoltarea standardului[Scheneier]La inceputul anilor70 cercetarea criptografic nemilitar era intampltoare. Aproape c nu erau lucrri publicate in domeniu. Majoritatea oamenilor tiau c militarii utilizau coduri speciale pentru a comunica, dar puini erau cei ce inelegeau tiina criptografiei. NSA (National Security Agency) avea cunotine considerabile, dar nici nu se admitea public existenta ei.Anumite companii mici fceau i livrau echipamente criptografice, in afara SUA, diferitelor guverne. Echipamentele erau total diferite, fr posibilitate de interconectare. Nimeni nu tia mcar dac erau sigure, dat fiind c nu exista un organism independent care s certifice securitatea produselor livrate.In1972, NBS (National Bureau of Standards) astzi NIST (National Institute of Standards and Technology), a iniiat un program pentru protecia calculatoarelor i comunicaiilor de date. Ca parte a acestui program, ei doreau s dezvolte un singur standard pentru un algoritm criptografic. Un singur algoritm ar fi putut fi testat i certificat, iar diferitele echipamente criptografice care l-ar fi folosit ar fi fost compatibile i ar fi fost in acelai timp mai ieftin de implementat i mai rapid disponibile.La data de15 mai 1973NBS a fcut publice cererile pentru propuneri de algoritmi criptografici pentru un standard. Criteriile specificate au fost:-algoritmul trebuie s asigure un nivel ridicat de securitate-algoritmul trebuie complet specificat i uor de ineles-securitatea algoritmului trebuie s fie cuprins in cheie i nu in secretul algoritmului-algoritmul trebuie s fie disponibil tuturor utilizatorilor-algoritmul trebuie s se poat adapta diferitelor aplicaii-algoritmul trebuie s poat fi implementat economic cu circuite electronice-algoritmul trebuie s fie eficient in utilizare-algoritmul trebuie s poat fi evaluat-algoritmul trebuie s poat fi exportabilRspunsul public la prima strigare a artat c interesul pentru un standard criptografic era mare, dar existau puini specialiti (in domeniul public). Nici una dintre propuneri nu a indeplinit cerinele specificate.La data de27 august 1974, NBS a fcut a doua cerere (Federal Register).Primiser promisiunea unei candidaturi: un algoritm descoperit de IBM la inceputul anilor 1970 (LUCIFER).IBM avea un grup de criptografi la Kingston i Yorktown Heights.Algoritmul, dei complicat, era clar. Utiliza doar operaii simple pe grupuri mici de bii i se putea implementa destul de eficient.NBS a cerut ageniei NSA s evalueze securitatea algoritmului i s determine dac poate constitui un standard federal [IBM a patentat algoritmul, dar dorea ca drepturile de autor s fie date altora pentru fabricaie, implementare i utilizare].La data de17 martie 1975, Registrul Federal a publicat algoritmul dat de NBS i cerinele companiei IBM de neexclusivitate i a cerut comentarii. Comentariile au fost multe. Toi erau speriai c NSA a modificat algoritmul instaland o trap. Ei au comentat c NSA a redus cheia de la 128 la 56 de bii.In1976, NBS a inut dou conferine pentru a evalua standardul propus. Prima conferin a discutat matematica algoritmului i posibilitatea unei trape. Cea de-a doua conferin a discutat problema creterii dimensiunii cheii. Au fost invitai: proiectanii algoritmului, evaluatorii, implementatorii, vanztorii, utilizatorii i criticii. Dup toi, conferinele au fost strlucite.La data de26 noiembrie 1976, DES a fost adoptat ca standard federal i autorizat pentru utilizare in comunicaii guvernamentale (unclassified) secrete iar pe15 ianuarie 1977s-a dat o descriere oficial a standardului. In1981s-a publicat ghidul pentru implementarea i utilizarea DES precum i specificaiile DES pentru criptarea parolelori pentru autentificarea datelor.Observaii:Toate aceste publicaii sunt fr precedent.Niciodat pan atunci un algoritm evaluat de NSA nu a fost fcut publicNSA a gandit DES doar ca hardware; standardul DES mandata o implementare hard, dar NBS a publicat suficiente detalii, astfel incat oamenii s poat implementa DES-ul prinsoftware.NSA a apreciat c DES a fost una dintre cele mai mari greeli ale lor; dac ar fi tiut c atatea detalii vor fi date incat oamenii s-l poat implementa soft, nu ar fi acceptat s-l evalueze.DES a fost cel mai puternic catalizator in domeniul criptografiei. Exista un algoritm pentru studiu: unul socotit sigur de NSA.Adoptarea standarduluiANSI -American National Standards Institutea aprobat DES-ul castandard pentru sectorul privatin1981(ANSI X3.92). Ei l-au numitDEA(Data Encryption Algorithm).dou grupuri din ANSI reprezentand tranzaciileen-grosien-dtailau elaborat standarde bazate pe DESgrupul ANSI - grup de lucru pentru securitatea instituiilor financiare pentru vanzrile cu amnuntul (retail)- a dezvoltat un standard pentru managementul i securitatea PIN i un standard DES pentru autentificarea mesajelor in vanzrile cu amnuntul (retail) - ANSI X9.19acelai grup a fcut o propunere de standard pentru distribuia cheilorAlgoritmul DESAlgoritmul DES (Data Encryption Standard) este un algoritm de criptare cu chei simetrice. Structural este constituit ca o combinaie de algoritmi de tip transpoziie i substituie. Iniial sistemul a fost propus s lucreze cu un cuvant cheie de 128 de bii, dar din motive strategice s-a redus lungimea lui la 64 (de fapt la 56) bii. Experii NSA au realizat la acea vreme c o cheiede 128 de bii este prea greu de'spart'chiar i pentru ei.Schema general de criptare a DES este reprezentat infig 3.15. Dup cum era de ateptat, sunt dou intrri in algoritm i anume un bloc de text in clar de 64 de bii i o cheie de 56 de bii.

Fig 3.15- Prezentarea general a algoritmului DESSe poate observa dinfig. 3.15c - in partea dreapt a desenului - avem generarea cheilor iar in stanga se prelucreaz textul. Intrarea in bloc se va supune intai unei permutri iniiale dup care au loc 16 iteraii succesive, o interschimbare pe 32 de bii i - in incheiere- se va aplica inversa permutrii iniiale. In continuare, se vor descrie pe scurt principalii pai care sunt de efectuat pentru a parcurge algoritmul. Toate operaiile descrise in aceast seciune sunt prezentate detaliat in tabelele 3.53.12.Bit ieire12345678910111213141516

Bit intrare585042342618102605244362820124

Bit ieire17181920212223242526272829303132

Bit intrare625446383022146645648403224168

Bit ieire33343536373839404142434445464748

Bit intrare57494133251791595143352719113

Bit ieire49505152535455565758596061626364

Bit intrare615345372921135635547393123157

Tabelul 3.5- Permutarea iniialBit ieire12345678910111213141516

Bit intrare408481656246432397471555236331

Bit ieire17181920212223242526272829303132

Bir intrare386461454226230375451353216129

Bit ieire33343536373839404142434445464748

Bit intrare364441252206028353431151195927

Bit ieire49505152535455565758596061626364

Bit intrare34242105018582633141949175725

Tabelul 3.6- Inversa permutrii iniialeBit ieire12345678910111213141516

Bit intrare3212345456789891011

Bit ieire17181920212223242526272829303132

Bit intrare12131213141516171617181920212021

Bit ieire33343536373839404142434445464748

Bit intrare2223242524252627282928293031321

Tabelul 3.7- Permutarea cu expansiuneBit ieire12345678910111213141516

Bit intrare16720212912281711523265183110

Bit ieire17181920212223242526272829303132

Bit intrare28241432273919133062211425

Tabelul 3.8-PermutareaPBit ieire1234567891011121314

Bit intrare57494133251791585042342618

Bit ieire1516171819202122232425262728

Bit intrare10259514335271911360524436

Bit ieire2930313233343536373839404142

Bit intrare635547393123157625446383022

Bit ieire4344454647484950515253545556

Bit intrare1466153453729211352820124

Tabelul 3.9- Permutarea de tipul 1Iteraia12345678910111213141516

Nr. bii1122222212222221

Tabelul 3.10- Programul deplasrilor spre stanga pe paiBit ieire12345678910111213141516

Bit intrare141711241532815621102319124

Bit ieire17181920212223242526272829303132

Bit intrare26816727201324152313747553040

Bit ieire33343536373839404142434445464748

Bit intrare51453348444939563453464250362932

Tabelul 3.11- Permutarea de tipul 2Urmrind aceste tabele, se poate dovedi uor c intr-adevr permutarea final este inversa celei iniiale.Interschimbarea pe 32 de bii de care am pomenit infig.3.15, efectueaz trecerea blocului de 32 de bii aflai pe primele poziii in blocul de intrare de 64 de bii pe ultimele poziii i invers.Detalii despre o iteraie oarecare se pot gsi infig. 3.16.CutieRand0123456789101112131415

S101441312151183106125907

10157414213110612119538

24114813621115129731050

31512824917511314100613

S201518146113497213120510

13134715281412011069115

20147111041315812693215

31381013154211671205149

S301009146315511312711428

11370934610285141211151

21364981530111212510147

31101306987415143115212

S407131430691012851112415

11381156150347212110149

21069012117131513145284

33150610113894511127214

S502124171011685315130149

11411212471315015103986

24211110137815912563014

31181271142136150910453

S601211015926801334147511

11015427129561131401138

29141552812370410113116

34321295151011141760813

S704112141508133129751061

11301174911014351221586

21411131237141015680592

36111381410795015142312

S801328461511110931450127

11151381037412561101492

27114191214206101315358

32114741081315129035611

Tabelul 3.12- Cutiile S din algoritmul DES

Fig 3.16- Descrierea unei singure iteraii a algoritmului DESInfig 3.16de mai sus se poate observa c algoritmul imparte blocul de 64 de bii in dou blocuri de 32 de bii pe care le denumetestangidrepti cu care va lucra in continuare separat. Chiar din schem se poate observa c bloculstangcare va fi regsit la ieirea dintr-o iteraie va fi identic cu celdreptde la intrare deciSi= Di-1. Blocul iniialdreptva fi supus intai unei permutaii cu rol i de expandare care ii va mri dimensiunea de la 32 la 48 de bii pentru ca apoi s poate s fie supus unei operaii de SAU EXCLUSIV cheia intermediar corespunztoare iteraiei. Rezultatul obinut in urma acestor calcule va fi introdus in cutiile S de unde se va obine un bloc de 32 de bii care la randul su va fi supus unei permutri P i apoi unei operaii de SAU EXCLUSIV cu bloculstanginiial obinandu-se bloculdreptfinal al iteraiei. Toate operaiile de mai sus se pot rezuma in formula Di= Si-1f(Di-1,Si) unde modul de calculare al funciei f se poate observa infig 3.17.

Fig 3.17- Operaiile care se efectueaz pentru calcularea funciei fDinfig 3.15se poate observa c in cazul algoritmului DES, i cheia de 56 de bii va fi supus unei permutri de tipul 1 dup care va fi imprit in dou blocuri de 28 de bii iniial. Dup aceasta, asupra ambelor pri astfel obinute se va efectua o rotaie circular spre stanga cu un numr de bii corespunztor numrului iteraiei, numr ce se poate gsi intabelul 3.10prezentat anterior in aceast seciune. Cele dou blocuri care s-au obinut anterior se vor introduce ca i blocuri de intrare in viitoarea iteraie dar i intr-un bloc de permutare de tip 2 din care se va obine de altfel i cheia intermediar a iteraiei curente.Observaie:La ora actual o cheie de 56 de bii nu mai este considerat sigur in multe aplicaii, fapt pentru care in aceste cazuri se utilizeaz ali algoritmi cum ar T-DES sau IDEA.3.7.2Algoritmi asimetrici (cu chei publice)Principiul:utilizarea a dou chei diferite:-E - cheia public pentru criptare-D - cheia secret / privat pentru decriptarecele dou funcii E i D sunt funcii greu inversabile cu trap.Conceptul a fost inventat deWhitfieldDiffieiMartinHellmanin 1976 (cand au prezentat o lucrare laNational Computer Conferencepublicatacateva luni mai tarziu in lucrareaNew Directions in Cryptography).Ralph Merklea inventat - independent -acelai principiu, dar lucrarea i-a aprut doar in1978(datorit unui proces prelungit de publicare).NSA a susinut c deine principiul din 1976, dar nu a putut aduce probe ca urmare paternitatea criptografiei cu chei asimetrice este atribuitalui Diffiesi lui Hellman.Dintre numeroii algoritmi propui, numai trei lucreaz bine atat pentru criptare cat i pentru semnturi digitale: RSA, El Gamal i Rabin. [Schneier]Utilizareacea mai mare o au in sisteme hibride pentru transmiterea cheilor de sesiune.Dezavantajulesenial al algoritmilor asimetrici este c sunt de circa 1000 de ori mai leni decat algoritmii simetrici.Diffie i Hellman au propus ca cele dou funcii E i D s indeplineasc i urmtoarele proprieti adiionale:i,,de unde posibilitatea utilizrii acestora in semnturi digitale.Principiulalgoritmilor asimetrici const in folosirea unor funcii greu inversabile. Pentru acestea calculul funciei directeftrebuie s se fac uor, iar inversa functieif () se va calcula uor doar dac exist o trap (informaie secret). Perecheaeste echivalentacu perecheaunde E este functia de criptare iar D cea de decriptare.Dintre funciile greu inversabile folosite in algoritmii cu chei publice amintim:factorizarea unui produs de numere prime mari (100 de cifre zecimale)utilizatain cazul algoritmului RSAgsirea logaritmului modulo numr prim dintr-un GF(q) cu q foarte marefolosit la algoritmuluiRabin (logaritmi discrei)problema rucsaculuicare stala baza algoritmuluiMerkle-Hellman (MH).Exemplu:Fiequn numr prim, un intreg x,i campul Galois [Angheloiu(1972)] [Borda] generat de acesta:, undeeste un element primitiv al campului GF(q)Funciase calculeaz uor .Utilizatorul A alege in mod aleator un numrcare constituie astfel cheia sa privat;A calculeaz(3.80)i o face public;Dac A i B doresc s comunice intre ei, se utilizeaz:;(3.81)In consecin, A i B pot calculapornind de la cheia privati de la cheia public a partenerului yB/ yA.Comunicaia este confidenial, dat fiind cnu se poate calcula dac nu se cunoate cheia privat xB/xA.Calcularea lui KAB:(3.82)este computaional imposibil.Avantajele algoritmilor cu cheie public:nu este necesar stabilirea unei chei secrete de comunicare (K).A i B pot comunica direct pe baza cheilor publice i a cheii private a fiecruia.Dintre algoritmii cu chei publice vom prezenta pe scurt pe cel mai popular i anume RSA (Rivest-Shamir-Adleman).Algoritmul Rivest Shamir Adleman (RSA)Acest algoritm apare publicat pentru prima dat in 1978. Securitatea acestui algoritm se bazeaz pe faptul c - dei gsirea unor numere prime mari este din punct de vedere computaional uoar - factorizarea produsului a dou astfel de numere este in prezent foarte greu de rezolvat intr-un timp acceptabil. Problema de factorizare este o problem veche in matematic, Fermat i Legendre dezvoltand o serie de algoritmi de factorizare, cei mai eficieni folosii la ora actual bazandu-se pe cei elaborai de Legendre.Metoda de criptare implic calculul exponenial intr-un camp finit (modulon). Mesajul cifrat se obine din mesajul in clar printr-o transformare (codare) bloc. Fie unul din aceste blocuri din mesajul M, bloc care are proprietatea cM(0,n-1) (proprietate ce se obine prin modul de imprire a mesajului in blocuri). Blocul criptat C corespunztor blocului in clar se obine calculand exponenialaCME(modn), E inreprezentand astfel cheia public de criptare.Decriptarea se face prin operaia MCD(modn), D fiind cheia secret de decriptare.Cele dou chei E i D trebuie s satisfac relaia:MCD(modn)MED(modn),(3.83)pentru ca algoritmul s poat fi intr-adevr folosit.Pentru aceasta vom pleca de la:Teorema Euler-Fermat:peste un numr prim dacap-11(modp) oricare ar fia,a1,p].Astfel dac am alesnun numr prim, pentru orice bloc M(0, n-1) avem proprietatea de la care vom porni:M(n)mod (n)1,(3.84)unde(n)n1(3.85)este numit indicatorul lui EulerDac E si D satisfac relaia:ED(mod(n))1(3.86)putem scrie:EDk(n)1(n)(n)(n)(n)1,(3.87)MEDM(n)(n)(n)(n)1M(n)M(n)M(n).M(modn),(3.88)deci:ED(mod(n))1MEDM(modn).(3.89)Astfel