Elemente de criptografie / criptologie

Scurt istoric

InformaÆia (religioaså, militarå, economicå, etc.) a insemnat intotdeauna putere, prin urmare dorinÆa de a o proteja, de a o face accesibilå doar unor elite, unor iniÆiaÆi, 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 existenÆa acestora probabil cå dateazå de la apariÆia scrierii in toate civilizaÆiile 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 cåruia se infåçura, 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 cåtre persoana care avea un baston identic cu cel utilizat la cifrare. In secolul al IV-lea i.e.n. in Grecia se cunoçteau 16 scrieri cifrate. Istoricul grec Polybius (sec II i.e.n.) este inventatorul unui tabel de cifrare påtrat de dimensiune 5x5, tabel aflat la baza elaborårii unui numår mare de sisteme de cifrare utilizate çi azi.

In Roma anticå secretul informaÆiilor politice çi militare se fåcea utilizand scrierea secretå. Amintim cifrul lui Cesar, utilizat incå din timpul råzboiului galic.

Existå documente ce atestå existenÆa scrierilor secrete in Asia incå din antichitate. Astfel, literatura indianå då o serie de referinÆe dintre care Artha-såstra (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 façii inguste de måtase sau hartie; acestea erau rulate formand mici bile care apoi se acopereau cu cearå çi se introduceau in rectul mesagerilor. [Deavours]

Steganografia, çtiinÆa scrierilor secrete insesizabile camuflate in texte in clar, constituie o formå particularå de secretizare çi este prezentatå in detaliu in capitolul 8.

ContribuÆia arabå ([Deavours] - Al Kadif) la dezvoltarea criptologiei, mai puÆin cunoscutå çi mediatizatå este de o remarcabilå importanÆå. David Kahn, unul dintre cei mai de seamå istoriografi ai domeniului, subliniazå in cartea sa The Codebreakers cå criptologia s-a nåscut in lumea arabå. Primele trei secole ale civilizaÆiei 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 antichitåÆii greceçti, romane, indiene, armene, ebraice, siriene. Unele cårÆi surså erau scrise in limbi deja moarte, deci reprezentau in fapt texte cifrate, astfel incat traducerea lor constituie primii paçi in criptanalizå, deci originile criptologiei pot fi atribuite arabilor. Cartea lui Ahmad ibn Wahshiyyah (cca. 900 e.n.) conÆine 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 cåtre orientalistul Joseph von Hammer sub denumirea Ancient 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). Dezvoltårile 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 acelaçi timp çi limba çtiinÆificå. Arabii au preluat cunoçtinÆele matematice ale civilizaÆiilor greceçti çi indiene. Arabii sunt cei care au introdus sistemul zecimal de numeraÆie çi cifrele arabe . Termenii zero cifru algoritm algebrå li se datorezå tot lor. Manuscrise recent descoperite aratå cå primele scrieri in domeniul probabilitåÆilor çi statisticii dateazå cu 800 de ani inaintea celor corespunzåtoare ale lui Pascal çi Fermat. Insuçi 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 numeraÆie folosit era cel roman. De aceea se obiçnuia så se spunå despre cineva care vorbea neclar cå vorbeçte ambigu, ca un cifru. Acest inÆeles de ambiguitate a unui mesaj poartå çi azi denumirea de cifru.

In perioada Renaçterii, odatå cu trezirea interesului pentru civilizaÆia anticå, s-au redescoperit lucrårile criptografiei din antichitate. Extinderea relaÆiilor diplomatice dintre diferitele state feudale a determinat o puternicå dezvoltare a secretizårii informaÆiei. CurÆile regale çi in special statul papal dispuneau de criptologi de mare valoare dintre care amintim pe Giambattista della Porta, Vigénère, 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 urmåreçte indeaproape creçterea çi descreçterea marilor imperii çi civilizaÆii. Ea nu apare çi nu se dezvoltå decat acolo unde este putere ce trebuie protejatå.

ApariÆia telegrafului çi a radioului in secolul al XIX-lea precum çi cele douå råzboaie mondiale din secolul XX au fost stimulente puternice in dezvoltarea metodelor çi tehnicilor de criptare.

ApariÆia çi dezvoltarea continuå a utilizårii calculatoarelor practic in toate domeniile vieÆii, existenÆa çi evoluÆia puternicå a reÆelelor teleinformatice la nivel naÆional çi internaÆional, globalizarea comunicaÆiilor, existenÆa unor baze de date puternice, apariÆia çi dezvoltarea comerÆului electronic, a poçtei electronice, constituie premisele societåÆii informaÆionale in care påçim. Toate acestea indicå o creçtere extraordinarå a volumului çi importanÆei datelor transmise sau stocate çi implicit a vulnerabilitåÆii acestora. ProtecÆia in aceste sisteme vizeazå:

eliminarea posibilitåÆilor de distrugere voitå sau accidentalå

asigurarea caracterului secret al comunicårii pentru a preveni posibilitatea ca persoane neautorizate så extragå informaÆii

autentificarea informaÆiei in scopul prevenirii posibilitåÆii ca persoane neautorizate så introducå informaÆii in sistem

in anumite situaÆii, cum ar fi transferurile electronice de fonduri, negocierile contractuale, este importantå existenÆa unor semnåturi electronice pentru a evita dispute intre emiÆåtor çi receptor cu privire la mesajul transmis.

Toate aceste obiective aratå o lårgire 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, plåÆi de taxe radio / TV, taxe de drumuri, acces autorizat in clådiri sau la calculatoare, terminale de loterie, instrumente electronice de plåÆi anticipate. In aceste aplicaÆii rolul criptografiei este acela de a face furturile mai greu de realizat.

Terminologie de bazå

Criptografia (cryptography) este çtiinÆa creerii çi menÆinerii mesajelor secrete, in sensul imposibilitåÆii citirii lor de cåtre neautorizaÆi (çtiinÆa mesajelor secrete).

Mesaj (text) in clar (M) (plain / clear text) este mesajul ce urmeazå a fi secretizat; in criptografie M se mai numeçte scriere chiar dacå este un document de altå naturå, de exemplu voce, imagine, date.

Mesaj cifrat (criptogramå) (C) (cipher text) este mesajul secretizat, inaccesibil neavizaÆilor.

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 regåsire a mesajului in clar M din mesajul cifrat C.

(3.2)

ObservaÆii:

decriptarea este operaÆia inverså criptårii;

ISO 7498-2 foloseçte termenii de cifrare / descifrare (encipher / decipher), socoteçte Schneier [Scheneier], probabil pentru cå primul set de termeni aminteçte de morÆi (criptå).

Criptograf (cryptographer) este persoana ce se ocupå cu criptografia.

Algoritm criptografic / cifru (cryptographic algorithm / cipher) este funcÆia sau funcÆiile matematice utilizate pentru criptare / decriptare; in general existå douå funcÆii: una pentru criptare (E) çi alta pentru decriptare (D).

Cheia criptograficå (K) (key) este mårimea (in majoritatea cazurilor secretå) necesarå realizårii criptårii çi decriptårii.

Criptosistem (cryptosystem) este sistemul format din:

algoritm

toate mesajele in clar (M)

toate textele cifrate (C)

toate cheile (K).

Criptanalizå (cryptanalysis) este çtiinÆa spargerii cifrurilor, deci a obÆinerii 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 çtiinÆa 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 aça fel incat existenÆa mesajelor secrete så fie invizibilå.

Criptosisteme çi rolul acestora

Schema bloc a unui criptosistem este prezentatå in Fig 3.1.

Fig. 3.1 - Schema bloc a unui criptosistem

A, B - entitåÆi ce emit, recepÆioneazå sau manipuleazå informaÆia

E - funcÆia de criptare (cifrare)

D - funcÆia de decriptare (descifrare)

M - spaÆiul mesajelor in clar

C - spaÆiul criptogramelor (text cifrat)

K - spaÆiul cheilor

Ke - spaÆiul cheilor de criptare

Kd - spaÆiul cheilor de decriptare

Rolul unui criptosistem

Rolul unui criptosistem este de a preveni sau detecta activitåÆile 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

conectårile neautorizate.

deci, aça cum se precizeazå in capitolul 1, acela de poliÆie informaticå

Indeplinirea acestui rol presupune ca un criptosistem så realizeze:

ConfidenÆialitatea / secretul / protecÆia datelor (confidentiality / secrecy / privacy) asigurå inaccesibilitatea conÆinutului informaÆiei transmise / stocate pentru un utilizator neavizat (in cazul canalelor / mediilor nesigure in care pot apårea intruçi)

Autentificarea (autentication) se aplicå [Menezes] la:

entitåÆi (persoane, terminale, cårÆi de credit, etc.) çi in acest caz se numeçte autentificarea entitåÆilor / identificare (entity autentication / identification)

informaÆie: informaÆia trasmiså / stocatå trebuie så fie autentificatå in sensul originii, conÆinutului datelor, timpului de transmisiune / stocare çi defineçte autentificarea originii datelor / integritatea datelor (data origin autentication / data integrity)

Semnåtura digitalå (digital signature) [Scheneier] reprezintå autentificarea reciprocå a datelor çi en 252e44c titåÆilor çi se referå la faptul cå un utilizator B este sigur cå mesajul recepÆionat vine de la A prin semnarea mesajelor sale (S_A), iar A este sigur cå nimeni nu-i poate atribui un mesaj fals deoarece mesajul transmis de cåtre el ii poartå semnåtura.

ObservaÆie: Aceste trei cerinÆe sunt vitale pentru interacÆiunea socialå in calculatoare çi sunt echivalente cu interacÆiunile 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), mårturia (witnessing), confirmarea (confirmation), dreptul de proprietate (ownership), anonimatul (anonimity), revocarea (revocation).

Obiectivele pe care le poate realiza un criptosistem sunt cuprinse in tabelul 3.1.

ObservaÆii:

toate aceste obiective existå natural in interacÆiunile umane faÆå in faÆå;

apariÆia reÆelelor de calculatoare prin care au loc interacÆiunile interumane pune o serie de probleme in plus: hartia se inlocuieçte cu discul, unda radio, firul; scrisul are un format electronic çi anume biÆi cu posibilitate extrem de uçoarå de copiere (copiile digitale sunt identice); utilizatorii se aflå la distanÆå, nu se pot vedea faÆå in faÆå çi deci se lucreazå in condiÆii de neincredere

criptografia este chematå astfel så soluÆioneze o diversitate extremå de probleme, multe de mare dificultate

Tabelul 3.1 - Obiectivele unui criptosistem ce realizeazå securitatea informaÆiei

Clasificarea criptosistemelor

Dupå tipul cheilor folosite pentru criptare / decriptare, criptosistemele se clasificå in douå categorii çi anume in sisteme: cu chei simetrice çi cu chei publice.

Criptosistemele cu chei simetrice / cu cheie secretå / criptosistemele convenÆionale

Criptosistemele cu chei simetrice sunt 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 de sisteme cu cheie secretå. Criptarea çi decriptarea se realizeazå extrem de simplu dacå se cunoaçte K:

(3.4)

(3.5)

Problema ce se pune in cazul acestor sisteme este distribuÆia 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 acÆioneazå asupra unei diviziuni a textului in clar; blocurile de la intrare se cifreazå independent, lungimea tipicå a blocurilor fiind biÆi. Transformårile de bazå folosite pentru criptare çi decriptare sunt substituÆiile çi transpoziÆiile, repetate iterativ [Angheloiu et al. (1986)] [Scheneier].

cu cifruri secvenÆiale (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 reacÆie (RDR) avand starea iniÆialå controlatå de o cheie compactå [Angheloiu et al. (1986)][Scheneier].

Criptosisteme cu chei publice (asimetrice)

Criptosistemele cu chei publice sunt criptosistemele pentru care cheile folosite la criptare çi decriptare diferå, de unde derivå çi denumirea de sisteme asimetrice:

(3.6)

Cheia publicå - aça cum ii spune çi numele - poate fi accesatå public (asemånåtor unei cårÆi de telefon), iar cheia privata este secretå. Caracteristic acestor sisteme este cå funcÆia de criptare çi cea de decriptare se realizeazå uçor dacå se cunosc çi

(3.7)

dar aflarea lui M, dacå se cunosc C çi este computational nefezabilå.

ObservaÆie: E este o funcÆie neinversabilå cu trapå [Angheloiu et al. (1986)], [Patriciu (1994)], [Menezes]. este trapa care furnizeazå informaÆia necesarå calculårii funcÆiei inverse D. Dintre funcÆiile neinversabile cu trapå amintim: factorizarea unui produs de numere prime mari cu peste 100 de cifre zecimale (folosit in algoritmul RSA), gåsirea logaritmului modulo un numår prim intr-un camp Galois GF(q) cu q foarte mare (folosit in algoritmii Rabin çi Diffie-Hellman), problema rucsacului (folositå in algoritmul Merkle-Hellman).

Atacuri çi modele de securitate in sisteme informatice

Atacuri asupra securitåÆii sistemelor criptografice

Atacul asupra securitåÆii unui sistem criptografic defineçte orice acÆiune ce compromite securitatea acelui sistem.

O ilustrare sugestivå a principalelor tipuri de atacuri asupra unui sistem informatic este fåcutå in fig 3.2 [Stallings]

Fig. 3.2 - Ilustrarea principalelor tipuri de atacuri la securitatea unui sistem criptografic

Atacurile criptografice pot fi indreptate impotriva:

algoritmilor criptografici

tehnicilor utilizate pentru implementarea algoritmilor çi protocoalelor

protocoalelor.

Dupå modul de atacare al unui atacator / intrus / persoanå neautorizatå / pirat (attacker / introuder / pirat), aceste atacuri se pot clasifica dupå cum urmeazå:

atacuri pasive (de intercepÆie) :

de inregistrare a conÆinutului mesajelor

de analizå de trafic;

atacuri active :

de intrerupere (atac la disponibilitate)

de modificare (atac la integritate)

de fabricare (atac la autenticitate).

Atacurile pasive sunt atacuri in care intrusul (persoanå, calculator, program) doar ascultå, monitorizeazå transmisia, deci sunt atacuri de intercepÆie. Ele pot fi de douå feluri:

de inregistrare a conÆinutului mesajelor (release of message contents), de exemplu in convorbirile telefonice, in poçta electronicå, fapt pentru care dacå mesajele nu sunt criptate, se violeazå caracterul confidenÆial al comunicaÆiei.

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 pårÆilor ce comunicå intre ele, frecvenÆa çi lungimea mesajelor.

Caracteristicile atacurilor pasive

sunt greu de detectat pentru cå datele nu sunt alterate;

måsurile ce pot fi luate pentru evitarea acestor atacuri sunt acelea care fac criptanaliza extrem de grea dacå nu imposibilå;

este necesarå prevenirea çi nu detecÆia lor.

Atacurile active sunt atacuri in care intrusul are o intervenÆie activå atat in desfåçurarea normalå a traficului, cat çi in configuraÆia datelor (modificarea datelor, creearea unor date false). Dintre atacurile active amintim [Stallings],[Menezes]:

intreruperea [Stallings] / refuzul serviciului (denial of service) [Menezes]: un bloc funcÆional este distrus, sau se inhibå funcÆionarea normalå sau managementul facilitåÆilor de comunicaÆie; acest tip de atac este un atac la disponibilitate (attack on availability)

modificarea: mesajul iniÆial este intarziat, alterat, reordonat pentru a produce efecte neautorizate ca de exemplu:

schimbare de valori in fiçiere de date;

modificåri in program astfel incat acesta va lucra diferit;

modificarea conÆinutului mesajelor transmise in reÆea

fabricarea: un neavizat insereazå informaÆii false in sistem; acest atac este un atac la autenticitate. Din aceastå categorie fac parte çi:

mascarea (masquerade): o entitate pretinde a fi altå entitate. Exemplu: secvenÆele de autentificare pot fi capturate çi dupå validarea unei autentificåri se inlocuiesc, permiÆand astfel unei entitåÆi så obÆinå privilegii pe care nu le are de drept.

reluarea (replay) constå in capturarea prin atac pasiv a unei cantitåÆi de informaÆie çi transmiterea sa ulterioarå pentru a produce efecte neautorizate.

Caracteristicile atacurilor active:

deçi pot fi detectate, prevenirea lor este foarte grea, deoarece ar insemna protecÆie fizicå permanentå a intregului sistem.

Atacuri criptanalitice

Atacurile criptanalitice [Scheneier] sunt atacuri asupra textelor cifrate in vederea obÆinerii textului in clar sau a cheilor folosite pentru decriptare.

Existå mai multe tipuri de asemenea atacuri dintre care amintim:

Atac asupra textului cifrat (cipher text-only attack): criptanalistul are criptograma çi trebuie så obÆinå mesajul in clar () sau cheia k.

Atac asupra unui text cunoscut (known plain-text attack): criptanalistul are criptogramele çi mesajele in clar corespunzåtoare çi trebuie så determine cheia k sau algoritmul de determinarea lui din

Atac cu text in clar ales (chosen plain-text attack): se pot alege o serie de mesaje dupå dorinÆå çi se cunosc criptogramele corespondente: . Criptanalistul trebuie så determine cheia k sau algoritmul de determinare al lui din

Atac cu text in clar ales adaptiv (adaptive chosen plain-text attack) : mesajele in clar se pot alege dupå dorinÆå çi sunt adaptabile in funcÆie de rezultatele criptanalizelor anterioare, iar criptogramele se cunosc. Se cere cheia k sau algoritmul de determinare al lui din

Aceste patru atacuri constituie atacurile criptanalitice de bazå. In afara acestora mai putem aminti:

Atac cu text cifrat la alegere (chosen cipher-text attack) in care se aleg çi , sarcina criptanalistului fiind determinarea cheii k. Acest atac se aplicå mai ales algoritmilor cu chei publice.

Atacul de cumpårare a cheii (rubber-hose cryptanalysis / purchase-key attack), in care aflarea cheii se face fårå mijloace criptanalitice (se apeleazå la çantaj, furt, etc.) çi este unul dintre cele mai puternice atacuri.

ObservaÆie: Atacurile 3) çi 5) se numesc atacuri cu text ales (chosen text attack) çi au fost folosite cu succes in cel de-al doilea råzboi mondial pentru spargerea codurilor german çi japonez [Deavours].

Securitatea algoritmilor [Scheneier]

In secolul al XIX-lea, olandezul A. Kerckhoff a enunÆat conceptul fundamental al criptanalizei: secretul se rezumå in intregime la cheie, algoritmul criptografic çi implementarea considerandu-se cunoscute.

DiferiÆii algoritmi pot asigura diferite grade de securitate, funcÆie de dificultatea cu care pot fi sparÆi [Menezes], [Scheneier]:

dacå costul spargerii unui algoritm este mai mare decat valoarea datelor criptate, algoritmul este probabil sigur (PS);

dacå timpul necesar spargerii este mai mare decat valabilitatea datelor criptate, algoritmul este PS;

dacå mulÆimea datelor necesare spargerii este mai mare decat mulÆimea datelor criptate la un moment dat de o cheie, algoritmul este PS.

Lars Knudsen - in teza de doctorat susÆinutå in 1994 [Menezes] - a clasificat diferitele categorii de spargere a unui algoritm in ordine descrescåtoare a securitåÆii:

Spargere totalå (total break) / securitate zero: un criptanalist gåseçte cheia, deci orice criptogramå va fi decriptatå:

DeducÆie globalå (global deduction): criptanalistul gåseçte un algoritm alternativ echivalent cu fårå a cunoaçte cheia k.

DeducÆie localå (local deduction): un criptanalist gåseçte textul in clar al unui text cifrat interceptat.

DeducÆia informaÆionalå (information deduction): criptanalistul capåtå unele informaÆii privitor la cheie sau la textul in clar (de exemplu caÆiva biÆi ai cheii, anumite informaÆii privitoare la M, etc.).

Algoritm computaÆional puternic (computational strong) este algoritmul care nu poate fi spart cu resursele existente, atat la momentul curent, cat çi intr-un viitor predictibil.

Algoritm necondiÆionat sigur (unconditional secure) este algoritmul pentru care indiferent cat text cifrat are criptanalistul, informaÆia nu este suficientå pentru a deduce textul in clar. Privitor la aceçti din urmå termeni trebuie atenÆionat cå sunt extrem de expuçi interpretårilor.

ObservaÆii:

Doar cheia de unicå folosinÆå (one time pad), inventatå in 1917 de Major J. Maubergue çi Gilbert Vernon, avand aceeaçi lungime cu a textului in clar, este de nespart.

ToÆi ceilalÆi algoritmi pot fi sparÆi cu ajutorul unui atac cu text cifrat, prin incercarea tuturor cheilor, panå cand textul descifrat are sens. Acest atac se numeçte atac 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 procesårii / factorul de lucru (processing complexity / work factor) este timpul necesar realizårii atacului;

c)         Complexitatea stocårii (storage complexity) este cantitatea de memorie necesarå atacului.

Regulå: Complexitatea unui atac = max .

Exemplu: complexitatea de indicå operaÆii necesare spargerii cifrului (de obicei aceasta reprezintå complexitatea atacului prin forÆå brutå, deci in cazul unui algoritm necondiÆionat sigur, 128 indicand lungimea cheii in biÆi).

ObservaÆie: Multe atacuri se preteazå paralelismului, deci complexitatea scade faÆå de regula anterior enunÆatå.

Criptografie clasicå (precomputaÆionalå)

Criptografia clasicå este criptografia dinaintea calculatorului, de unde çi denumirea de criptografie precomputaÆionalå.

In criptografia clasicå, algoritmii erau bazaÆi pe caracter çi constau dintr-o serie de transformåri elementare (substituÆii, transpoziÆii) ale caracterelor textului in clar. Unii algoritmi aplicau aceste transformåri in mod repetat, imbunåtåÆind in acest mod securitatea algoritmului.

In criptografia modernå bazatå pe calculator (criptografie computaÆionalå), lucrurile s-au complicat, dar multe dintre ideile criptografiei clasice au råmas nemodificate.

Criptografia clasicå se incadreazå in clasa criptografiei cu chei simetrice.

Cifruri de substituÆie

Cifrul de substituÆie (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 substituÆiei inverse asupra textului cifrat.

In criptografia clasicå existå patru tipuri de cifruri de substituÆie:

Cifruri de substituÆie 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 substituÆie cele mai cunoscute:

A. Cifrul lui Cesar

Este un cifru cu substituÆie monoalfabeticå:

fiecare literå a textului in clar este inlocuitå cu o nouå literå obÆinutå printr-o deplasare alfabeticå

cheia (aceeaçi la criptare cat çi la decriptare) constå in numårul care indicå deplasarea alfabeticå

(3.8)

unde a se numeçte factor de amplificare, iar b coeficient de deplasare.

Fåcand corespondenÆa biunivocå intre literele alfabetului latin (N = 26) çi echivalentele lor numerice , cifrul lui Cesar se poate scrie conform tabelului 3.2.

(3.9)

Tabelul 3.2 - Cifrul lui Cesar

Exemplu: Celebrul ²VENI VIDI VICI², devine prin criptare : ²YHQL YLGL YLFL²

Ulterior, cifrul lui Cesar, a fost generalizat prin alegerea in calitate de cheie a oricårei litere din alfabet.

B. Cifrul lui Polybius

Este un cifru substituÆie. Literele alfabetului latin sunt açezate intr-un påtrat de dimensiune 5x5. Literele I çi J sunt combinate pentru a forma un singur caracter, deoarece alegerea finalå (intre I çi J) poate fi uçor deciså din contextul mesajului. Rezultå 25 de caractere açezate intr-un påtrat 5x5. Cifrarea oricårui caracter se face alegand perechea potrivitå de numere (intersecÆia liniei çi coloanei) corespunzåtoare dispunerii caracterului in påtrat.

Tabelul 3.3 - Påtratul lui Polybius

Exemplu: Mesajul: A SOSIT TIMPUL , se transformå dupå cifrare in: 444223535413

ObservaÆie: Codul poate fi schimbat prin rearanjarea literelor in påtratul 5x5.

In sistemele UNIX, programul de criptare ROT 13 este un cifru de substituÆie monoalfabeticå; fiecare literå, in textul cifrat se roteçte 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 conÆine N = 26 litere:

(3.11)

Acest cifru nu este in realitate un cifru de securitate; el se utilizeazå adesea in posturile de utilizatori de reÆea pentru a ascunde texte potenÆial ofensive [Scheneier].

Concluzie: Cifrurile de substituÆie monoalfabeticå pot fi sparte cu uçurinÆå deoarece frecvenÆele literelor alfabetului nu se schimbå in textul cifrat faÆå de textul in clar.

Cifruri de substituÆie omofonicå (homophonic substitution ciphers) [Angheloiu et al. (1986)][Patriciu (1994)] sunt cifrurile de substituÆie in care un caracter al alfabetului mesajului in clar (alfabet primar) poate så aibå mai multe reprezentåri.

Ideea utilizatå in aceste cifruri este uniformizarea frecvenÆelor de apariÆie a caracterelor alfabetului textului cifrat (alfabet secundar), pentru a ingreuna atacurile criptanalitice.

Astfel, litera A - cu cea mai mare frecvenÆå de apariÆie in alfabetul primar - poate fi inlocuitå cu F, * sau K.

Concluzii:

deçi mai greu de spart decat cifrurile de substituÆie simple (monoalfabetice), ele nu mascheazå total proprietåÆile statistice ale mesajului in clar.

in cazul unui atac cu text in clar cunoscut, cifrul se sparge extrem de uçor.

atacul cu text cifrat este mai dificil, dar unui calculator ii va lua doar cateva secunde pentru a-l sparge.

Cifruri de substituÆie poligramicå (polygram substitution ciphers) [Patriciu (1994)][Scheneier] se obÆin substituind blocuri de caractere ale alfabetului primar - numite poligrame - cu alte blocuri de caractere, de exemplu:

ABA  à RTQ

SLL à ABB

Utilizåri:

Cifrul Playfair, inventat in 1854 [Stallings], a fost utilizat in Anglia, in timpul primului råzboi mondial

Codul de compresie Huffman, bazat pe acelaçi principiu, poate fi utilizat dar este nesigur.

Cifruri de substituÆie polialfabetice [Patriciu (1994)][Scheneier][Patriciu (1998)] sunt formate din mai multe cifruri de substituÆie 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 Vigénère.

A. Cifrul lui Trithemius

Este un cifru polialfabetic. Alfabetul este dispus pe 26 de linii numerotate de la 0 la 25, unde numårul de ordine al liniei indicå numårul de caractere cu care se deplaseazå ciclic alfabetul spre dreapta. Linia numerotatå cu 0 constituie tocmai alfabetul in ordinea iniÆialå. Acest cifru poate fi utilizat astfel: primul caracter se cifreazå selectandu-l din linia 1, al doilea din linia a 2-a çi aça mai departe [Borda (1999)].

Exemplu: 2 3 4 5 6 7 8 9 10 11 12

Mesajul: ²A S O S I T T I M P U L² , se cifreazå: ²B URWNZ AQVZFX²

B. Cifrul lui Vigénère

Acest cifru utilizeazå cifrul Trithemius çi un anumit cuvant cheie. Cheia dicteazå alegerea liniilor in criptarea çi decriptarea fiecårui caracter din mesaj.

Exemplu:

O variantå a acestui cifru este cifrul Vigénère 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 urmåtor. Apoi caracterele textului in clar sunt folosite drept chei pentru alegerea liniilor in criptare.

Exemplu:

Reluåm exemplul anterior, dar alegem litera M drept cheie de incercare.

ObÆinem:

ObservaÆie: Se remarcå introducerea unei reacÆii in procesul de criptare, textul cifrat fiind condiÆionat de conÆinutul mesajului.

O altå variantå a cifrului Vigénère este cifrul Vigénère cu autocheie (cheie cifratå). Dupå criptarea cu cheie de incercare, fiecare caracter succesiv al cheii in secvenÆå se obÆine de la caracterul cifrat al mesajului çi nu de la textul in clar.

Exemplu:

ObservaÆie: Deçi fiecare caracter utilizat drept cheie poate fi gåsit din caracterul anterior al textului cifrat, el este funcÆional dependent de toate caracterele anterioare ale mesajului, inclusiv de cheia de incercare. Urmare a acestui fapt este efectul de difuziune a proprietåÆilor 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 Vigénère nu sunt foarte sigure; contribuÆia importantå a lui Vigénère constå in faptul cå a descoperit cå pot fi generate secvenÆe nerepetitive drept cheie, prin utilizarea a insuçi mesajului sau a unor pårÆi ale acestuia.

3.5.2 Cifruri de transpoziÆie (transposition ciphers) [Patriciu (1994)]

Cifrurile de transpoziÆie se caracterizeazå prin faptul cå textul in clar råmane acelaçi, 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 asemånåtor, iar textul cifrat se citeçte pe verticalå (coloane):

à "VVVEIINDCIII   V	E	N	I
V	I	D	I
V	I	C	I

O simplå transpoziÆie permite påstrarea proprietåÆilor statistice ale textului in clar çi in textului cifrat; o nouå transpoziÆie a textului cifrat måreçte securitatea cifrului.

Utilizåri:

ADFGVX [Scheneier], utilizat de germani in timpul primului råzboi mondial are un cifru substituÆie combinat cu o altå substituÆie; deçi pentru acea vreme a fost foarte complex, el a fost spart de criptanalistul francez Georges Painvin.

MulÆi algoritmi moderni folosesc transpoziÆia, dar consumul de memorie este mare comparativ cu substituÆia, care din acest punct de vedere este mai convenabilå.

3.5.3 Maçini rotor

In vederea mecanizårii complicatelor metode de substituÆie çi permutårilor repetate, in anul 1920 au fost inventate o serie de echipamente mecanice de criptare bazate pe principiul de rotor.

O maçinå 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 poziÆii çi realizeazå o simplå substituÆie. Deoarece rotoarele se miçcå cu viteze de rotaÆie diferite, perioada unei maçini cu n rotoare este

Cel mai celebru cifru bazat pe o maçinå rotor este Enigma, utilizatå de germani in cel de-al doilea råzboi mondial. El a fost inventat de Arthur Scherbius çi Arvid Gerhard Damm in Europa çi a fost patentatå in SUA. Germanii au imbunåtåÆit considerabil proiectul inventatorilor såi, dar a fost spart de criptanaliçtii polonezi care au explicat atacul lor englezilor.

3.6 Protocoale criptografice

3.6.1 GeneralitåÆi

Protocolul criptografic este un protocol in care este implicat cel puÆin un algoritm criptografic.

Scopul unui protocol criptografic este de a nu permite så se facå sau så se inveÆe mai mult decat este specificat in protocol.

Protocoale in care intervin probleme de securitate çi incredere se aplicå in viaÆa de zi cu zi aproape pentru orice situaÆie: cumpåråturi, vot, joc, etc. Forma lor este foarte simplå pentru cå presupune prezenÆa oamenilor.

In momentul in care activitåÆile de zi cu zi se transpun pe reÆele de calculatoare, interacÆiunile umane faÆå in faÆå se reduc çi trebuie luate in considerare o serie de probleme noi ce complicå protocolul in vederea realizårii unei anumite sarcini.

ObservaÆie: In analiza unui protocol nu intereseazå modul de implementare, el trebuind så råmanå acelaçi in orice condiÆii de implementare.

Principalele tipuri de protocoale

Protocoalele se pot clasifica in trei categorii mari: arbitrate, adjudecate çi liber consimÆite

Protocoalele arbitrate (arbitrated protocols - caz in care comunicaÆia intre cei doi corespondenÆi A çi B se desfåçoarå prin intermediul unui arbitru (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 desfåçurarea protocolului. NoÆiunea de incredere se referå la faptul cå toÆi partenerii din protocol acceptå ca adevår verdictul dat de acesta.

In lumea realå arbitrii sunt: bancheri, judecåtori, notari publici. Intr-un protocol realizat intr-un sistem informatic, un arbitru este un banal program de calculator. Arbitrii sunt necesari cand apar tranzacÆii 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 conform fig 3.3 unde:

A, B - partenerii tranzacÆiei

I - arbitru (persoanå de incredere).

Figura 3.3 - Protocol arbitrat

Protocolul se desfåçoarå dupå cum urmeazå:

A då titlul de proprietate lui I;

B då cecul lui A;

A depune cecul lui B pentru operare;

Dupå un timp specificat, I då lui B titlul de proprietate al lui A.

Dacå operaÆiunea (3) nu se efectueazå (cecul nu are acoperire) in timpul de açteptare specificat, A ii aratå arbitrului probe de neefectuare a plåÆii çi I ii restituie lui A titlul de proprietate, deci (4) nu se efectueazå.

PrezenÆa unui arbitru intr-o reÆea de calculatoare are o serie de implicaÆii:

costuri suplimentare;

intarzieri inerente in protocol;

arbitrul constituie un punct de gatuire a comunicaÆiei in cazul unui numår mare de utilizatori; pentru a evita acest dezavantaj s-ar putea creçte numårul arbitrilor implicaÆi in protocol, cu creçterea evidentå a costurilor;

faptul cå arbitrul este unicul partener din reÆea in care trebuie avut incredere, face ca el så devinå un punct vulnerabil ( coruptibil ) pentru oricine doreçte så distrugå reÆeaua.

Protocoale adjudecate (adjudecated protocols)

Pentru a reduce costurile unui protocol arbitrat care necesitå prezenÆa permanentå a unui arbitru. Se pot imagina protocoale in care prezenÆa arbitrului este necesarå doar in caz de disputå, in rest protocolul desfåçurandu-se fårå arbitru. In consecinÆå, un asemenea protocol va conÆine douå subprotocoale: unul nearbitrat - executat de fiecare datå cand pårÆile doresc executarea lui - çi al doilea adjudecat, executat doar in condiÆiile unei dispute intre parteneri. Acest arbitru are rolul unui judecåtor care in cazul unei dispute, in baza probelor prezentate de parteneri, va da un verdict rezolvand astfel disputa.

In fig 3.4. este reprezentat un protocol adjudecat impreunå cu partenerii implicaÆi in acesta:

A, B - partenerii tranzacÆiei;

I - arbitru (numai in caz de disputå);

P_A çi P_B - probe ale partenerilor A çi B necesare a fi prezentate arbitrului in caz de disputå.

Fig. 3.4 - Protocol adjudecat

Un protocol adjudecat se desfåçoarå dupå cum urmeazå:

subprotocolul nearbitrat

A çi B negociazå termenii contractului;

A semneazå contractul;

B semneazå contractul.

subprotocolul arbitrat (in caz de dispute)

A çi B apar in faÆa arbitrului I;

A prezintå probele P_A ;

B prezintå probele P_B ;

din analiza probelor, I hotår çte verdictul.

In calculatoare, protocoalele adjudecate se utilizeazå atunci cand intre parteneri relaÆiile se bazeazå pe cinste; dacå un partener are suspiciuni de inçelåciune, existå posibilitatea ca o a treia parte (arbitrul I) så determine dacå çi cum a inçelat. Deci protocoalele adjudecate nu previn inçelåciunea, dar o detecteazå; inevitabilitatea detecÆiei acÆioneazå ca o prevenÆie çi descurajeazå inçelåciunile (ca in cazul magazinelor cu autoservire çi sistem de monitorizare: nu se controleazå sacoça clientului decat in caz de inçelåciune).

Protocoale autoimpuse (self - enforcing protocols)

Sunt cele mai simple çi mai eficiente dintre protocoale. Fig 3.5 prezintå o schemå a funcÆionårii unui astfel de protocol.

Fig. 3.5 - Protocol autoimpus

Nu existå arbitru çi nici dispute pentru cå protocolul insuçi garanteazå cinstea. Dacå unul dintre parteneri incearcå så inçele, ceilalÆi pot detecta inçelåciunea çi protocolul se opreçte.

In [Scheneier], autorul afirmå cå in cea mai bunå dintre toate lumile posibile toate protocoalele ar fi autoimpuse . Råmane de våzut dacå o asemenea lume este posibilå çi - in caz afirmativ - cand va fi aceasta.

3.6.2 Protocoale pentru comunicaÆii criptografice simetrice

Un sistem criptografic simetric - care evidenÆiazå çi principalele atacuri - este dat in fig. 3.6 çi are ca çi participanti pe:

A, B - parteneri ai protocolului;

F, H - atacator pasiv (filaj) respectiv activ (hot

Fig 3.6 - Criptosistem simetric cu evidenÆierea atacurilor posibile

Un protocol de comunicaÆie confidenÆialå intre A çi B se desfåçoarå dupå cum urmeazå:

A çi B cad de comun acord asupra unui criptosistem simetric;

A çi B aleg cheia k (secretå), cea mai bunå fiind cheia de unicå folosinÆå (one time pad) pentru o comunicaÆie;

A trimite lui B mesajul M criptat cu cheia k:

(3.12)

B decripteazå mesajul criptat primit de la A, utilizand aceeaçi cheie k:

(3.13)

Se pune intrebarea: ce pot face atacatorii in acest caz?

Rolul atacatorului pasiv (F):

el urmåreçte 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 forÆei brute , deci cu o cheie bine aleaså çi ca lungime, F nu va afla nimic.

Rolul atacatorului activ (H):

poate incerca intreruperea comunicaÆiei in pasul (3);

poate inlocui mesajul lui A (M) cu mesajul såu 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 cå pentru sisteme criptografice simetrice problemele sunt:

cheia k trebuie 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, numårul cheilor creçte rapid cu numårul utilizatorilor (n):

(3.15)

3.6.3 Protocoale pentru comunicaÆii criptografice asimetrice (cu chei publice) çi hibride

In cazul criptosistemelor cu chei publice, fiecare utilizator are o pereche de transformåri (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 avea çi , unde çi sunt chei publice, putand fi luate dintr-un fiçier public asemånåtor unei cårÆi de telefon.

Protocolul de comunicare intre A çi B are urmåtorii paçi:

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 comunicaÆie , respectiv

A cripteazå mesajul såu cu cheia publicå a lui B

(3.16)

çi il trimite lui B.

B decripteazå utilizand cheia sa privatå çi aflå pe

(3.17)

B cripteazå mesajul såu cu cheia publicå a lui A:

(3.18)

çi-l transmite lui A.

A decripteazå utilizand cheia sa privatå çi aflå pe

(3.19)

ObservaÆii:

Managementul cheilor este mult mai simplu in cazul criptosistemelor cu chei publice, numårul perechilor de chei fiind egal cu cel al utilizatorilor, iar in vederea comunicårii nu este necesarå transmiterea cheii secrete intre utilizatori, ci doar a cheii publice a corespondentului care se citeçte uçor 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 funcÆii neinversabile cu trapå [deci necunoaçterea 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å a cheii de sesiune folosite pentru comunicaÆie in sisteme cu chei simetrice. Un asemenea sistem se numeçte criptosistem hibrid (hybrid cryptosistem).

Protocolul de comunicaÆie intr-un criptosistem hibrid este alcatuit din urmatorii pasi:

A çi B convin asupra unui criptosistem cu chei publice çi obÆin cheile publice ale partenerului respectiv

A genereazå o cheie aleatoare de sesiune k pe care o cripteazå cu

(3.20)

çi o transmite lui B;

B decripteazå pe cu cheia sa privatå çi obÆine cheia de sesiune: 

(3.21)

In comunicaÆiile ulterioare, pentru confidenÆialitate, A çi B vor folosi aceeaçi cheie de sesiune k çi un criptosistem simetric.

Concluzie: Generarea cheii de sesiune k doar cand se doreçte comunicarea çi distrugerea ei dupå incheierea comunicårii face ca atacurile pasive så fie mult mai puÆin eficiente.

ObservaÆie: In cadrul acestui paragraf si in continuare, pentru a comprima scrierea s-au folosit denumirile improprii de cheie publicå respectiv privatå pentru transformårile respective care includ cele douå tipuri de chei; avem convingerea cå aceastå notaÆie neortodoxå nu va produce confuzii de inÆelegere cititorului.

3.6.4. Protocoale pentru semnåturi digitale

3.6.4.1 Ce este o semnåturå digitalå ?

Semnåtura olografå este o probå a calitåÆii de autor al unui document, sau cel puÆin de acord cu conÆinutul documentului.

ProprietåÆile unei semnåturi olografe sunt:

Semnåtura så fie autenticå, adicå så aibå calitatea de a convinge destinatarul cå semnatarul a semnat documentul in mod deliberat.

Semnåtura så nu poatå fi refolositå, ceea ce inseamnå cå semnåtura este parte a documentului.

Documentul semnat nu poate fi modificat.

Semnåtura nu poate fi repudiatå.

Semnåturile digitale trebuie så påstreze cerinÆele 1) 4), transpuse in comunicaÆia din reÆele de calculatoare.

ObservaÆie: Existå destule situaÆii in care cerinÆele 1) 4) nu se respectå pentru o semnåturå olografå, dar aceste nerespectåri sunt mult mai greu de realizat decat in cazul calculatorului, la care copy çi paste sunt comenzi atat de uzuale.

Cele patru cerinÆe, transpuse in mediul digital se rezumå la douå cerinÆe de bazå pentru o semnåturå:

så depindå de mesaj pentru a nu fi mutatå de pe un mesaj pe altul (aceastå cerinÆå nu apare in cazul semnåturii olografå pentru cå nu este cazul);

så depindå de emiÆåtor pentru a nu putea fi falsificatå.

Semnåtura digitalå S [Menezes] este o succesiune de biÆi obÆinutå din transformarea mesajului (M) çi a unei informaÆii secrete, çtiute doar de emiÆåtor.

Orice semnåturå digitalå trebuie så poatå fi verificatå, rezultatul acestei funcÆii putand fi doar adevårat sau fals

In cele ce urmeazå vom folosi notaÆiile:

- transformarea de semnare pentru entitatea A (ea este secretå);

- transformarea de verificare pentru entitatea A (ea este publicå);

- perechea de transformåri care defineçte schema (mecanismul) de semnåturå digitalå.

v - rezultatul verificårii .

Protocolul de semnare este:

A calculeazå

(3.22)

care este semnåtura mesajului M (folosind o cheie secretå);

A transmite perechea .

Protocolul de verificare:

Verificatorul (B) obÆine funcÆia de verificare a lui A: , care este publicå;

B calculeazå funcÆia de verificare

(3.23)

B acceptå cå S apartine lui A dacå v = adevårat çi o refuzå dacå v = fals.

ObservaÆie: Transformatele çi sunt tipic caracterizate de cate o cheie (secretå, respectiv publicå).

Pentru funcÆiile de semnare, respectiv de verificare, se cer proprietåÆile:

(a)      S este o semnåturå validå a lui A asupra mesajului M dacå çi numai dacå:

adevårat;  (3.24)

(b)      este imposibil de determinat pentru altcineva decat A un M çi S astfel incat:

adevårat. (3.25)

Fig.3.7 - Reprezentarea graficå a procedurii de semnare a) çi verificare b)

ObservaÆie: Semnåturile trebuie så fie verificabile pentru ca in caz de conflict så nu poatå fi repudiate sau reclamate in mod fraudulos; un arbitru trebuie så poatå rezolva disputa fårå a avea nevoie de cheia privatå a lui A.

AplicaÆii:

autentificare

integritatea datelor

nerepudiere

certificarea datelor publice in reÆele mari

Realizåri:

existå numeroçi algoritmi pentru semnåturi digitale, toÆi necesitand informaÆie secretå pentru semnare çi informaÆie 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, implementårile pot fi diferite; de exemplu, pentru algoritmii bazaÆi pe funcÆii hash (de rezumare) çi cu certificare temporalå (TS) se adaugå paçi suplimentari pentru semnare çi verificare;

3.6.4.2 Protocol de semnare cu criptografie simetricå

Fie situaÆia 1º in care A semneazå un mesaj digital pe care vrea så-l trimitå lui B. Protocolul se desfåçoarå astfel:

A trimite arbitrului I mesajul criptat cu cheia sa

(3.26)

I decripteazå , deci obÆine pe , la care adaugå o declaraÆie de autentificare () a primirii mesajului de la A çi le trimite lui B, cripate cu cheia lui B:

(3.27)

B decripteazå çi poate citi pe cat çi certificarea lui I:

(3.28)

Fie situaÆia 2º in care B vrea så-i arate lui C mesajul lui A. Paçii algoritmului sunt:

B ii trimite arbitrului I mesajul lui A çi certificarea sa , criptate cu cheia sa proprie:

(3.29)

I decripteazå çi gåseçte pe

(3.30)

I verificå in baza de date dacå il are pe

I cripteazå cu cheia lui C mesajul precum çi certificarea sa çi il trimite lui C:

(3.31)

C decripteazå çi citeçte pe precum çi certificarea

(3.32)

Concluzii:

Aceste protocoale sunt bune, dar extrem de laborioase, totul tranzitand

prin I

I 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 acelaçi timp extrem de vulnerabil la atac, deoarece el deÆine practic toate informaÆiile. In plus, ca orice protocol arbitrat este mai costisitor decat unul nearbitrat.

Propunem cititorului, ca exerciÆiu, så analizeze indeplinirea cerinÆelor unei semnåturi digitale in cele douå cazuri prezentate.

O ilustrare graficå a acestor douå situaÆii este prezentatå in fig. 3.8.

Fig 3.8 - Ilustrarea graficå a protocolului de semnare utilizand criptosisteme simetrice

Protocol de semnare utilizand criptografie cu chei publice

Protocol de semnare (fårå criptare) parcurge urmatorii paçi:

A semneazå mesajul M cu cheia sa privatå

(3.33)

A transmite lui B (necriptat);

B verificå folosind cheia publicå a lui A:

(3.34)

ObservaÆie:

Acest protocol este superior celui cu chei simetrice pentru cå nu necesitå arbitraj.

Protocol de semnare cu criptare

ObservaÆii:

Existå algoritmi cu chei publice care pot fi utilizaÆi atat pentru semnåturi digitale (S) cat çi pentru criptare: de exemplu RSA poate fi folosit la semnåturå çi confidenÆialitate, in acest caz fiind indeplinite condiÆiile: çi (3.35)

AlÆi algoritmi cu chei publice, de exemplu DSA [Scheneier][Patriciu (1994)], se utilizeazå doar pentru semnåturå, neputand fi utilizaÆi pentru criptare.

Protocolul de semnare cu criptare se desfaçoarå astfel:

A semneazå mesajul M cu cheia privatå

(3.36)

A cripteazå mesajul criptat cu cheia publicå a lui B çi il trimite acestuia

(3.37)

B decripteazå C₁ cu cheia privatå

(3.38)

B verificå semnåtura lui A cu cheia sa publicå

(3.39)

ObservaÆii:

A semna inainte de a cripta este natural. Cand A scrie o scrisoare, semneazå inainte de a pune scrisoarea in plic.

Utilizarea aceleiaçi perechi de chei (E, D) pentru semnåturå ç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 urmåtorii paçi:

B, dupå verificarea lui , retransmite M semnat () la A cu o confirmare de primire:

(3.40)

A decripteazå cu cheia sa privatå, verificå cu cheia publicå a lui B çi dacå M este acelaçi 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 urmåtorii paçi:

H inregistreazå mesajul lui A cåtre B in pasul (2)

(3.43)

Dupå un anumit timp, H trimite acest mesaj lui B pretinzand cå vine de la H (dar nesemnat)

; (3.44)

B decripteazå mesajul

(3.45)

çi verificå semnåtura lui H

; (3.46)

B continuå protocolul çi retransmite mesajul lui H

(3.47)

; (3.48)

H decripteazå mesajul:

; (3.49)

H aplicå cheia publicå a lui B

(3.50)

H decripteazå incå o datå cu cheia sa privatå

(3.51)

H aplicå cheia publicå a lui A çi obÆine pe M

(3.52)

çi aça H poate citi corespondenÆa.

AtenÆie:

deçi semnalul decriptat de cåtre B la pasul (3) este fårå 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 semnaÆi niciodatå mesaje arbitrare de la alte persoane, nu decriptaÆi mesaje arbitrare çi nu difuzaÆi rezultatele obÆinute de alÆii.

Contracararea atacului de retransmitere se poate face prin utilizarea de :

operaÆii distincte (chiar dacå apropiate) pentru criptare respectiv semnåturå;

chei diferite pentru criptare çi semnåturå;

algoritmi diferiÆi pentru criptare çi semnåturå;

certificare temporalå care fac ca semnåtura de intrare så fie diferitå de cea de ieçire;

semnåturi digitale cu funcÆii hash.

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 primeçte cheia lui B, verificå semnåtura lui I, ceea ce impiedicå posibilitatea inlocuirii ei in transmisie.

Protocol de semnare çi certificare temporalå (TS - time stamping)

Dacå A a semnat un cec cåtre B, acesta poate incasa banii çi apoi reutiliza o copie a contractului semnat. Prevenirea acestei situaÆii se poate face prin certificare temporalå (TS):

(3.53)

Protocol de semnare cu sisteme cu chei publice çi funcÆii hash

FuncÆii de dispersie (hash)

FuncÆiile hash - cunoscute çi sub denumirea de funcÆii de compresie (compression), contracÆie (contraction) sau de rezumat al mesajului (message digest) ori amprentå digitalå (fingerprint) - sunt funcÆii care au la intrare un çir de date de lungime variabilå n - numit preimagine - çi la ieçire dau un çir de lungime fixå m (uzual 128 sau 160 de biÆi) numit valoarea funcÆiei hash h (hash value - HV).

Fig. 3.9 - Ilustrarea graficå a conceptului de funcÆie hash

ObservaÆie: In [Patriciu (1994)] funcÆia hash este denumitå funcÆie de dispersie.

ProprietåÆi:

valoarea hash constituie o amprentå digitalå a intrårii; dacå douå çiruri de la intrare dau aceeaçi valoare hash (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 funcÆiile hash pot fi utilizate pentru a indica un grad destul de mare de asemånare;

valoarea hash (h) se calculeazå extrem de uçor;

çirul de intrare (preimaginea) se determinå destul de greu cand se cunoaçte h; aceastå proprietate impreunå cu cea precendentå justificå incadrarea funcÆiilor hash in categoria funcÆiilor neinversabile (one-way hash);

functia hash este o funcÆie fårå ciocnire (collision-free) in sensul cå este greu de determinat douå preimagini care så aibå aceeaçi valoare hash (h);

funcÆia hash este publicå.

AplicaÆii:

in tranzacÆii financiare;

h este o amprentå digitalå a fiçierelor; dacå vrei så verifici cå cineva are acelaçi fiçier pe care il ai çi tu, fårå så-l transmitå, ii ceri valoarea hash. Dacå valoarea hash transmiså este identica cu cea calculata de tine atunci este aproape sigur cå acea persoanå are acel fiçier;

coduri de autentificare a mesajelor [Scheneier] care constau din calcularea lui h çi semnarea acesteia cu o cheie secretå astfel incat doar cel care deÆine cheia secretå k poate verifica pe h:

MAC - message autentication code

DAC - data autentication code

ObservaÆie: Dacå documentele semnate M sunt mari, semnarea lor utiulizand chei publice este ineficientå. Pentru a reduce timpul, nu se semneazå M ci h (valoarea hash a lui M).

Pasii protocolului de semnare sunt:

(1) A çi B convin asupra algoritmului de semnåturå digitalå çi a funcÆiei hash folosite.

(2) A calculeazå valoarea hash a lui M:

h = H(M);   (3.54)

A semneazå pe h cu cheia sa privatå:

(3.55)

A trimite M çi cåtre B, criptat cu cheia publicå a lui B:

(3.56)

(5) B decripteazå çi gåseçte M çi dupå care determinå pe h çi il comparå cu cel decriptat

. (3.57)

(a) (3.58)

(b) (3.59)

dacå (a) este echivalent cu (b) atunci este validatå.

Avantaje:

vitezå mare;

securitate sporitå: probabilitatea de a avea doua valori hash identice este , unde n reprezintå lungimea valorii hash in biÆi;

poate fi påstratå separat de documentul M, ocupand o memorie mult mai micå.

Utilizåri:

sisteme de arhivare fårå citirea documentelor;

obÆinerea dreptului de autor prin påstrarea secretului documentului.

Protocoale pentru semnåturi multiple

Fårå funcÆii hash

A ç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 semnåturii lui A:

(3.62)

este imposibilå fårå verificarea semnåturii lui B.

Cu funcÆii hash

In acest caz protocolul va arata astfel:

A semneazå valoarea hash a lui M:

B semneazå valoare hash a lui M:

(3.64)

B trimite lui A

A trimite catre C pe

C verificå çi

Protocol de semnåturi digitale çi nerepudiere

A poate inçela 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 situaÆii sunt evitate cu protocolul:

A semneazå mesajul:

A genereazå un antet de identificare (AI), concateneazå antetul cu , semneazå totul:

(3.65)

çi trimite arbitrului I;

Arbitrul I verificå çi confirmå informaÆiile de identificare AI. I adaugå o certificare temporalå (TS) la , semneazå totul

(3.66)

çi trimite la A çi B;

B verificå , identificand pe AI çi ;

A verificå , deci mesajul trimis de I lui B. Dacå nu-çi gåseçte propria semnåturå apare o disputå.

ObservaÆie: Aceastå problemå poate fi soluÆionatå çi de protocoale adjudecate; propunem cititorului ca exerciÆiu aceastå a doua cale.

3.6.4.8 Semnåturi in alb (blind signatures) [Scheneier]

O tråsåturå esenÆialå a protocoalelor cu semnåturi digitale este cå semnatarul cunoaçte ceea ce a semnat. Existå situaÆii in care anumite persoane semneazå documente fårå så fi våzut niciodatå conÆinutul acestora. Sunt cåi prin care semnatarul poate cunoaçte aproximativ, dar nu exact, ceea ce semneazå.

Semnåturi complet in alb (completely blind signatures)

Fie exemplul:

B - notar public

A - doreçte ca B så semneze un document, dar nu doreçte ca B så çtie conÆinutul documentului; pe B nu-l intereseazå conÆinutul documentului, doar certificå cå acesta a fost notarizat.

Protocolul de semnare se desfåçoarå astfel:

A ia documentul çi il aleatorizeazå; aceastå valoare aleatoare se numeçte factor de ascundere (blinding factor);

A trimite documentul ascuns (blinded) lui B

B semneazå documentul ascuns

A inlåturå factorul de ascundere (dezaleatorizeazå documentul), obÆinand documentul original semnat de B.

ProprietåÆile unei semnåturi complet in alb

semnåtura lui B pe document este validå ; semnåtura este dovada cå B a semnat documentul çi are toate proprietåÆile unei semnåturi digitale.

B nu poate corela documentul semnat cu actul de semnare propriu-zis ; chiar dacå el ar Æine o copie a tuturor semnåturilor in alb acordate, el nu ar putea determina cand anume a semnat un anumit document.

Riscul semnåturilor complet in alb:

A il poate face pe B så semneze orice, de exemplu B datoreazå lui A 1.000.000 $

Semnåturi in alb (blind signatures)

Pentru a evita riscul menÆionat anterior, se va cåuta o cale in care B så çtie ce semneazå, menÆinand in acelaçi timp çi proprietåÆile utile ale semnåturii in alb.

Principiul folosit este: taie çi alege (cut and choose), ilustrat de exemplul controlului vamal. Controlul se face utilizand o soluÆie probabilistica adicå 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å.

Semnåtura 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å fårå a-l deschide.

Documentul ascuns se aflå in plic. Procesul de ascundere echivaleaza cu punerea documentului in plic. Procesul de inlåturare a factorului de ascundere poate fi comparat cu deschiderea plicului.

Un alt exemplu de utilizare de semnåturi in alb este agenÆia de contraspionaj. [Scheneier]

Fie un grup de agenÆi de contra-spionaj; identitatea lor este secretå chiar çi pentru agenÆie. Directorul agenÆiei vrea så dea fiecårui agent un document semnat care så-i ofere imunitate diplomaticå. Fiecare agent are propria listå cu nume de acoperire çi nu doreçte ca agenÆii så o cunoascå de teama spargerii calculatorului agenÆiei. Pe de altå parte agenÆia nu doreçte så semneze in alb absolut orice document pentru a preintampina situaÆii 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 agenÆiei

B - agentul sub acoperire

Protocolul de semnare in alb decurge astfel:

B pregåteçte n nume, fiecare cu alt nume de acoperire, care ii conferå imunitate diplomaticå.

B aleatorizeazå fiecare document cu un factor de ascundere diferit.

B trimite cele n documente ascunse lui A.

A alege (n-1) documente la intamplare çi ii solicitå lui B factorii de ascundere.

B trimite lui A cei (n-1) factori de ascundere solicitaÆi.

A deschide cele (n-1) plicuri, deci inlåtura factorul de ascundere çi se asigurå de conÆinutul acestora.

A semneazå ultimul document nedeschis çi-l trimite lui B.

B inlåturå factorul de ascundere çi citeçte noul nume de acoperire ce-i asigurå imunitate diplomaticå: Ion Ionescu.

3.6.5 Protocoale pentru schimbul de chei

In tehnica criptograficå uzanÆa este de a utiliza o singurå cheie pentru fiecare comunicaÆie criptatå numitå cheie de sesiune (key session).

3.6.5.1 Schimb de chei cu criptografie simetricå

Pasii protocolului pentru schimb de chei in criptografia simetrica sunt:

A cere arbitrului I o cheie de sesiune pentru a putea comunica confidenÆial cu B;

I genereazå o cheie de sesiune k çi cripteazå doua copii cu cheile secrete ale lui A, respectiv B çi çi le trimite lui A:

A decripteazå cu cheia sa secretå çi gåseçte k:

; (3.67)

A trimite lui B copia cheii de sesiune k, criptatå cu cheia secretå a lui B (

B decripteazå cu cheia sa secretå çi gåseçte k:

; (3.68)

Atat A cat çi B pot comunica confidenÆial utilizand k.

Fig. 3.10 - Protocol de schimb de chei in criptografia simetricå

ObservaÆii:

A çi B au fiecare de la I (centrul de distribuÆie a cheilor CDC) çi

acest protocol presupune absoluta securitate a lui I, chiar dacå acesta este un program de calculator;

I are copia tuturor cheilor k, deci poate citi tot traficul din reÆea, fiind un punct foarte vulnerabil pentru atacuri

potenÆial I este un punct de strangulare a traficului in reÆea.

Schimb de chei cu criptografie cu chei publice

Principiul:

A çi B utilizeazå criptografia cu chei publice pentru a stabili cheia de sesiune k

ComunicaÆia confidenÆialå intre A çi B se face cu criptografie simetricå.

Protocolul este:

A çi B içi procurå de la I (CDC - centru de distribuÆie a cheilor, KDC - key distribution center) cheile publice çi

A genereazå o cheie de sesiune aleatoare k pe care o cripteazå utilizand cheia publicå a lui B çi o trimite la B:

B decripteazå mesajul primit de la A utilizand cheia sa privatå

; (3.69)

A çi B comunicå confidenÆial intre ei folosind cheia cheia secretå k.

Fig 3.11 - Protocol de schimb de chei in criptografia asimetricå

Ïn cazul acestui protocol poate avea loc :

Atacul om la mijloc (man in the middle attack), ce constå in:

H - atacatorul activ, inlocuieçte cheia publicå a lui A sau B cu cheia sa publicå: (in timpul transmiterii de la A la B çi invers, fie intr-o bazå de date a CDC);

toate mesajele criptate in acest caz de A çi B vor trece pe la H care le va decripta cu uçurinÆå;

Protocolul de interblocare (interlock protocol)

Pentru a contracara atacul de om la mijloc , Ron Rivest çi Adi Shamir au inventat protocolul de interblocare. Paçii acestuia sunt:

A çi B intrå in posesia cheilor publice çi fie de la CDC fie transmiÆandu-le direct unul altuia;

A cripteazå cu çi transmite jumåtate din criptograma:

; (3.70)

B cripteazå cu çi transmite jumåtate din criptograma:

; (3.71)

A trimite lui B cealaltå jumåtate din

B pune impreunå cele douå jumåtåÆi recepÆionate de la A çi le cripteazå cu cheia sa privatå:

(3.72)

; (3.73)

A procedeazå identic çi obÆine .

ObservaÆii:

H nu mai poate face nimic deoarece jumatate din sau nu are utilitate deoarece jumatate din mesaj poate reprezenta, de exemplu, tot al doilea bit pentru un algoritm de tip bloc;

decriptarea poate depinde de vectorul de iniÆializare, care se poate transmite in a doua jumåtate a mesajului;

prima jumåtate a mesajului poate fi o funcÆie hash a mesajului criptat, iar cea de-a doua parte poate fi chiar mesajul criptat.

Schimb de chei cu semnåturi digitale

Dacå in schimbul de chei se utilizeazå semnåturile digitale, se poate preveni atacul om la mijloc

Existå un arbitru I (CDC) care semneazå çi . Cand A çi B primesc cheile, fiecare verificå semnåtura lui I, dupå care protocolul se desfåçoarå ca in subcapitolul 3.6.5.2.

ObservaÆii:

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; obÆinerea lui (cheia privatå a lui I) este folositå doar pentru semnarea cheilor, nepermiÆand acestuia decriptarea cheilor de sesiune precum çi a traficului din reÆea ;

atacul poate fi reuçit dacå H inlocuieçte pe cu , dar aceasta inseamnå cå H interceptezå çi modificå datele din CDC, ceea ce este mult mai greu decat a sta pasiv intr-o reÆea çi a privi mesajele ;

intr-un canal de difuziune (reÆea radio) este aproape imposibil de a inlocui un mesaj cu altul fårå blocarea intregii reÆele, in reÆele de calculatoare acest lucru este din ce in ce mai uçor.

3.6.5.4 Transmiterea cheilor çi mesajelor

Principiul: transmiterea criptatå de mesaje, fårå existenÆa prealabilå a unui protocol de schimb de chei.

Pasii ce trebuie parcursi sunt:

A genereazå o cheie aleatoare de sesiune k çi o foloseçte la criptarea lui M:

A selecteazå dintr-o bazå de date publicå cheia lui B:

A cripteazå pe k cu cheia publicå a lui B:

A transmite lui B atat mesajul criptat: cat çi cheia criptatå:

B decripteazå pe k:

(3.74)

B obÆine pe M folosind la criptare un algoritm simetric si cheia k:

(3.75)

ObservaÆii:

acest algoritm hibrid este cel mai folosit in sistemele de comunicaÆie;

pentru mårirea securitåÆii in cazul atacului om la mijloc A poate semna transmisiunea in pasul (4);

algoritmul poate fi combinat cu:

semnåtura digitalå

certificarea temporalå

alte protocoale de securitate

ceea ce conduce la imbunåtåÆirea securitåÆii acestuia.

3.6.5.5 Difuzarea cheilor çi a mesajelor

Protocolul de difuzare a cheilor si mesajelor consta in:

A genereazå o cheie de sesiune k çi cripteazå pe M:

A selecteazå dintr-o bazå de date cheile publice: çi cripteazå cheia k:

A difuzeazå çi

Doar B, C çi D pot decripta k çi apoi pot obÆine pe M.

ObservaÆie: 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 garanÆia cå nu este H care incearcå så foloseascå identitatea lui A?

Problema anterioarå se rezolvå tradiÆional prin parole P. A introduce parola çi calculatorul verificå dacå este corectå. Parola se cere de fiecare datå cand A doreçte så acceseze calculatorul.

Autentificare cu funcÆii neinversabile (f)

Roger Needham çi Mike Guy au aråtat cå calculatorul nu trebuie så cunoascå parola. El trebuie doar så facå distincÆie intre parolele corecte çi cele incorecte. Acest lucru se realizeazå uçor cu funcÆii neinversabile f. In loc de memorarea parolelor, calculatorul memoreazå . Modul de lucru este urmatorul:

A trimite calculatorului parola P;

Calculatorul calculeazå ;

(3) Calculatorul comparå de fiecare datå cu valoarea memoratå

ObservaÆii:

acest algoritm atenueazå atacul la bånci de date in care sunt memorate parolele.

nu sunt utile deoarece este extrem de greu de calculat.

Atacul de tip dicÆionar

Un fiçier de parole criptat cu o funcÆie neinversabilå: este incå vulnerabil:

H poate incerca de exemplu parole (cele mai uzuale) pentru care calculeazå çi memoreazå rezultatele; dacå fiecare rezulta ca fiçierul are 8 MB (deci nu este exagerat de mare).

H furå din calculator lista çi o comparå cu lista calculatå de el pentru a vedea potrivirile.

Acesta este atacul de tip dicÆionar çi este surprinzåtor de eficient.

Sufixul (salt)

Sufixul(salt) este - prin definiÆie - un çir aleator care se concateneazå cu inaintea calcularii lui f; se memoreazå. PrezenÆa lui diminueazå çansele unui atac de tip dicÆionar

ObservaÆii:

mulÆimea este mare;

majoritatea sistemelor UNIX utilizeazå pentru un sir de 12 biÆi;

existå programe de ghicit parola (password guessing program) care sparg çi pe

nu este un panaceu universal; creçterea lungimii lui protejeazå la atacurile de tip dicÆionar asupra fiçierelor parolate, nu inså asupra unui atac concentrat asupra unei singure parole;

protejeazå persoanele care au aceeaçi parolå pe maçini multiple, dar nu sunt cu nimic mai bune decat parolele slab alese.

Autentificare cu chei publice [Scheneier]

Problema: Çi in cazul folosirii sufixelor, este vulnerabil. In pasul (1) oricine are acces pe canal poate afla çi , iar dacå F are acces la memoria

calculatorului, poate vedea çi inainte de a se calcula

SoluÆia ar fi:

utilizarea criptografiei cu chei simetrice : calculatorul are un fiçier cu toate cheile publice iar utilizatorii içi Æin acaså cheile private

Protocolul folosit in acest caz este:

Calculatorul trimite lui A un çir aleator X;

A cripteazå pe X cu cheia sa privatå çi il trimite calculatorului;

; (3.76)

Calculatorul, utilizand cheia publicå a lui A decripteazå

(3.77)

Dacå X decriptat la (3) este echivalent cu X transmis la (2), A are acces la sistem.

ObservaÆii:

nimeni nu cunoaçte , deci nu se poate falsifica identitatea lui A;

A nu transmite niciodatå pe canal, deci nu sunt posibile atacuri pasive;

cheia privatå trebuie så fie lungå çi nenumericå çi se calculeazå automat in hardul calculatorului sau in softul de comunicaÆie de unde necesitatea unui terminal inteligent de comunicaÆie in care A så aibå incredere, in acest caz canalul çi calculatorul gazdå nu trebuie så fie sigure;

pasul (1) este neobiçnuit: nimeni nu va cripta un çir arbitrar venit de nu se çtie unde (calculatorul nu trebuie så fie sigur); pentru mårirea siguranÆei, algoritmul se modificå dupå cum urmeazå:

A genereazå un çir aleator , il cripteazå cu cheia sa secretå çi-l trimite calculatorului.

Calculatorul ii trimite lui A un çir aleator diferit: X.

A face o serie de calcule bazate pe numerele aleatoare (X çi ) çi cheia privatå çi trimite rezultatul calculatorului.

Calculatorul face o serie de calcule asupra numerelor primite de la A pentru a verifica dacå A içi cunoaçte cheia privatå.

Identitatea lui A este verificatå, testand dacå A içi cunoaçte cheia

Autentificarea mesajelor

Problema: Cand B primeçte un mesaj de la A, de unde çtie cå este autentic?

SoluÆia: semnarea mesajului de cåtre A.

ObservaÆii:

criptografia simetricå furnizeazå o anumitå autentificare cand B primeçte de la A un mesaj criptat cu cheia comunå secretå k, el çtie cå vine de la A, deoarece numai A cunoaçte 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 deÆin aceeaçi cheie, deci nu existå posibilitatea identificårii emiÆåtorului.

3.7 Algoritmi criptografici (cifruri)

Algoritmul criptografic este prin definitie funcÆia (funcÆiile) matematicå(e) utilizatå(e) pentru criptare / decriptare.

in general existå douå funcÆii destinate pentru:

criptare (E)

decriptare (D)

atat criptarea cat çi decriptarea sunt controlate de una sau mai multe chei criptografice

3.7.1 Algoritmi simetrici

Algoritmii simetrici (dupå cum s-a aråtat in secÆiunea 3.1.2) se clasificå in douå categorii mari: algoritmi secvenÆiali çi algoritmi bloc.

3.7.1.1 Algoritmi secvenÆiali

Caracteristici:

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 ieçire se obÆine un çir de simboluri ale criptogramei.

Notåm :

A - alfabetul mesajului in clar;

C - alfabetul mesajului cifrat;

S - cifrarea secvenÆialå: .

ObservaÆii:

dacå , nu se recomandå criptarea;

cifrurile secvenÆiale sunt o variantå modernå a cifrului Vigenere;

cheia folositå in cazul acestor cifruri K este generatå de un RDR (starea iniÆialå çi polinomul generator pot fi controlate prin chei).

Criptarea consta in operaÆia:

(3.78)

iar decriptarea se realizeaza astfel:

(3.79)

unde reprezinta suma modulo 2.

ObservaÆie: Pentru cifruri secvenÆiale 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.

Recomandåm cititorului consultarea bibliografiei: [Angheloiu et al. (1986)] pp. 78-91; [Patriciu (1994)] pp. 85-89 çi [Scheneier] cap.16; iar pentru aplicaÆii [Scheneier] cap.17 : RC-4, SEAL, etc.

Algoritmi (cifruri) bloc

Caracteristici:

mesajul in clar M este impårÆit in blocuri, de obicei de aceeaçi dimensiune, fiecare bloc fiind cifrat independent;

cifrurile bloc sunt cifruri produs iterate avand la bazå substituÆia çi transpoziÆia;

lungimile tipice ale blocurilor sunt: 32 128 biÆi;

anii de dezvoltare a cifrurilor bloc sunt anii '70 (la baza acestora stand lucrårile lui Shannon).

Componentele de bazå ale cifrurilor bloc sunt transformårile de:

transpoziÆie - cutiile P (permutare P - box).

substituÆie - cutiile S (sustituÆie S - box).

Cutia P

Un exemplu de cutie P este reprezentat in fig. 3.12 unde intrarile sunt notate cu iar iesirile cu

Fig.3.12 - Exemplu de cutie P

transformårile operate de o cutie P sunt liniare, legåturile interioare ale unei cutii P putand fi determinate prin punerea unui la fiecare intrare çi marcarea ieçirii corespondente

Cutia S

Cutia S este reprezentata fig. 3.13 si consta din doua convertoare (unul binar - zecimal (CBZ) si al doilea zecimal - binar (CZB)) precum si dintr-o cutie P.

intr-o cutie S se fac atat transformåri liniare (prin P) cat çi neliniare (prin CBZ çi CZB);

Numårul de permutåri posibile pentru o cutie S cu n intråri este .

Exemple:

pentru n = 3 intrari vom avea iesiri ale CBZ, deci permutåri posibile in cutia P;

dacå n = 128 atunci vom aveaiesiri ceea ce face criptanaliza exhaustivå imposibilå din punct de vedre tehnic.

Fig 3.13 - Exemplu de cutie S

Tabelul 3.4 - Stårile intrårilor çi ieçirilor pentru cutia S din fig. 3.13.

Un cifru bloc reprezinta o alternanÆå de cutii P çi S. Un astfel de sistem de cifrare este exemplificat in fig. 3.14.

Caracteristici:

cutiile P sunt fixe (fårå cheie) çi prin permutarea pe care o fac realizeazå difuzia

cutiile S primesc la intrare atat informaÆia (4x4) cat çi cheia de cifrare , care are rolul så comande substituÆia liniarå; in acest fel cutiile S realizeazå confuzia : biÆi; se folosesc cate doi biÆi pentru fiecare cutie S, ceea ce creazå posibilitatea selectårii uneia din 4 substituÆii posibile.

			K''

Fig.3.14 - Sistem de cifrare bloc

AplicaÆiile cele mai importrante sunt concretizate in cifrurile LUCIFER, IDEA çi DES. Dintre aceste aplicatii vom prezenta in continuare cifrul DES, cel mai utilizat; pentru ceilalti algoritmi recomandåm 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 implementårii çi utilizårii in diferite aplicaÆii;

fiecare bloc cifrat este independent de celelalte;

nu este necesarå sincronizarea intre operaÆiile de criptare / decriptare ale unui bloc;

pentru creçterea securitåÆii se poate aplica algoritmul T-DES (triplu DES) care constå in iterarea de trei ori a algoritmului DES.

Deçi då semne de båtraneÆe DES-ul s-a comportat excepÆional timp de 20 de ani la atacuri criptanalitice çi este considerat incå sigur in numeroase aplicaÆii. Consideråm cå istoria apariÆiei sale meritå a fi amintitå [Scheneier], deoarece ea reprezintå un model de conlucrare eficientå a lumii çtiinÆifice, a producåtorilor de echipamente, a consumatorilor çi - in final - a factorului politic in dezvoltarea unei probleme de mare actualitate.

Dezvoltarea standardului [Scheneier]

La inceputul anilor ¢70 cercetarea criptograficå nemilitarå era intamplåtoare. Aproape cå nu erau lucråri publicate in domeniu. Majoritatea oamenilor çtiau cå militarii utilizau coduri speciale pentru a comunica, dar puÆini erau cei ce inÆelegeau çtiinÆa criptografiei. NSA (National Security Agency) avea cunoçtinÆe considerabile, dar nici nu se admitea public existenta ei.

Anumite companii mici fåceau çi livrau echipamente criptografice, in afara SUA, diferitelor guverne. Echipamentele erau total diferite, fårå posibilitate de interconectare. Nimeni nu çtia måcar dacå erau sigure, dat fiind cå nu exista un organism independent care så certifice securitatea produselor livrate.

In 1972, NBS (National Bureau of Standards) aståzi NIST (National Institute of Standards and Technology), a iniÆiat un program pentru protecÆia calculatoarelor çi comunicaÆiilor 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 acelaçi timp mai ieftin de implementat çi mai rapid disponibile.

La data de 15 mai 1973 NBS a fåcut 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 uçor de inÆeles

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 aplicaÆii

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 exportabil

Råspunsul public la prima strigare a aråtat cå interesul pentru un standard criptografic era mare, dar existau puÆini specialiçti (in domeniul public). Nici una dintre propuneri nu a indeplinit cerinÆele specificate.

La data de 27 august 1974, NBS a fåcut 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, deçi complicat, era clar. Utiliza doar operaÆii simple pe grupuri mici de biÆi çi se putea implementa destul de eficient.

NBS a cerut agenÆiei 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 fabricaÆie, implementare çi utilizare].

La data de 17 martie 1975, Registrul Federal a publicat algoritmul dat de NBS çi cerinÆele companiei IBM de neexclusivitate çi a cerut comentarii. Comentariile au fost multe. ToÆi erau speriaÆi cå NSA a modificat algoritmul instaland o trapå. Ei au comentat cå NSA a redus cheia de la 128 la 56 de biÆi.

In 1976, NBS a Æinut douå conferinÆe pentru a evalua standardul propus. Prima conferinÆå a discutat matematica algoritmului çi posibilitatea unei trape. Cea de-a doua conferinÆå a discutat problema creçterii dimensiunii cheii. Au fost invitaÆi: proiectanÆii algoritmului, evaluatorii, implementatorii, vanzåtorii, utilizatorii çi criticii. Dupå toÆi, conferinÆele au fost strålucite.

La data de 26 noiembrie 1976, DES a fost adoptat ca standard federal çi autorizat pentru utilizare in comunicaÆii guvernamentale (unclassified) secrete iar pe 15 ianuarie 1977 s-a dat o descriere oficialå a standardului. In 1981 s-a publicat ghidul pentru implementarea çi utilizarea DES precum çi specificaÆiile DES pentru criptarea parolelor çi pentru autentificarea datelor.

ObservaÆii:

Toate aceste publicaÆii sunt fårå precedent. Niciodatå panå atunci un algoritm evaluat de NSA nu a fost fåcut public

NSA 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 prin software.

NSA a apreciat cå DES a fost una dintre cele mai mari greçeli 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 standardului

ANSI - American National Standards Institute a aprobat DES-ul ca standard pentru sectorul privat in 1981 (ANSI X3.92). Ei l-au numit DEA (Data Encryption Algorithm).

douå grupuri din ANSI reprezentand tranzacÆiile en-gros çi en-détail au elaborat standarde bazate pe DES

grupul ANSI - grup de lucru pentru securitatea instituÆiilor financiare pentru vanzårile cu amånuntul (retail) - a dezvoltat un standard pentru managementul çi securitatea PIN çi un standard DES pentru autentificarea mesajelor in vanzårile cu amånuntul (retail) - ANSI X9.19

acelaçi grup a fåcut o propunere de standard pentru distribuÆia cheilor

Algoritmul DES

Algoritmul DES (Data Encryption Standard) este un algoritm de criptare cu chei simetrice. Structural este constituit ca o combinaÆie de algoritmi de tip transpoziÆie çi substituÆie. IniÆial sistemul a fost propus så lucreze cu un cuvant cheie de 128 de biÆi, dar din motive strategice s-a redus lungimea lui la 64 (de fapt la 56) biÆi. ExperÆii NSA au realizat la acea vreme cå o cheie de 128 de biÆi este prea greu de spart chiar çi pentru ei.

Schema generalå de criptare a DES este reprezentatå in fig 3.15. Dupå cum era de açteptat, sunt douå intråri in algoritm çi anume un bloc de text in clar de 64 de biÆi çi o cheie de 56 de biÆi.

Fig 3.15 - Prezentarea generalå a algoritmului DES

Se poate observa din fig. 3.15 cå - in partea dreaptå a desenului - avem generarea cheilor iar in stanga se prelucreazå textul. Intrarea in bloc se va supune intai unei permutåri iniÆiale dupå care au loc 16 iteraÆii succesive, o interschimbare pe 32 de biÆi çi - in incheiere - se va aplica inversa permutårii iniÆiale. In continuare, se vor descrie pe scurt principalii paçi care sunt de efectuat pentru a parcurge algoritmul. Toate operaÆiile descrise in aceastå secÆiune sunt prezentate detaliat in tabelele 3.5

Tabelul 3.5 - Permutarea iniÆialå

Tabelul 3.6 - Inversa permutårii iniÆiale

Tabelul 3.7 - Permutarea cu expansiune

Tabelul 3.8 - Permutarea P

Tabelul 3.9 - Permutarea de tipul 1

Tabelul 3.10 - Programul deplasårilor spre stanga pe paçi

Tabelul 3.11 - Permutarea de tipul 2

Urmårind aceste tabele, se poate dovedi uçor cå intr-adevår permutarea finalå este inversa celei iniÆiale. Interschimbarea pe 32 de biÆi de care am pomenit in fig.3.15, efectueazå trecerea blocului de 32 de biÆi aflaÆi pe primele poziÆii in blocul de intrare de 64 de biÆi pe ultimele poziÆii çi invers. Detalii despre o iteraÆie oarecare se pot gåsi in fig. 3.16.

Tabelul 3.12 - Cutiile S din algoritmul DES

Fig 3.16 - Descrierea unei singure iteraÆii a algoritmului DES

In fig 3.16 de mai sus se poate observa cå algoritmul imparte blocul de 64 de biÆi in douå blocuri de 32 de biÆi pe care le denumeçte stang çi drept çi cu care va lucra in continuare separat. Chiar din schemå se poate observa cå blocul stang care va fi regåsit la ieçirea dintr-o iteraÆie va fi identic cu cel drept de la intrare deci  S_i = D_i-1. Blocul iniÆial drept va fi supus intai unei permutaÆii cu rol çi de expandare care ii va måri dimensiunea de la 32 la 48 de biÆi pentru ca apoi så poate så fie supus unei operaÆii de SAU EXCLUSIV cheia intermediarå corespunzåtoare iteraÆiei. Rezultatul obÆinut in urma acestor calcule va fi introdus in cutiile S de unde se va obÆine un bloc de 32 de biÆi care la randul såu va fi supus unei permutåri P çi apoi unei operaÆii de SAU EXCLUSIV cu blocul stang iniÆial obÆinandu-se blocul drept final al iteraÆiei. Toate operaÆiile de mai sus se pot rezuma in formula D_i = S_i-1 Å f(D_i-1,S_i) unde modul de calculare al funcÆiei f se poate observa in fig 3.17.

Fig 3.17 - OperaÆiile care se efectueazå pentru calcularea funcÆiei f

Din fig 3.15 se poate observa cå in cazul algoritmului DES, çi cheia de 56 de biÆi va fi supuså unei permutåri de tipul 1 dupå care va fi impårÆitå in douå blocuri de 28 de biÆi iniÆial. Dupå aceasta, asupra ambelor pårÆi astfel obÆinute se va efectua o rotaÆie circularå spre stanga cu un numår de biÆi corespunzåtor numårului iteraÆiei, numår ce se poate gåsi in tabelul 3.10 prezentat anterior in aceastå secÆiune. Cele douå blocuri care s-au obÆinut anterior se vor introduce ca çi blocuri de intrare in viitoarea iteraÆie dar çi intr-un bloc de permutare de tip 2 din care se va obÆine de altfel çi cheia intermediarå a iteraÆiei curente.

ObservaÆie :

La ora actualå o cheie de 56 de biÆi nu mai este consideratå sigurå in multe aplicaÆii, fapt pentru care in aceste cazuri se utilizeazå alÆi algoritmi cum ar T-DES sau IDEA.

Algoritmi asimetrici (cu chei publice)

Principiul

utilizarea a douå chei diferite:

E - cheia publicå pentru criptare

D - cheia secretå / privatå pentru decriptare

cele douå funcÆii E çi D sunt funcÆii greu inversabile cu trapå.

Conceptul a fost inventat de Whitfield Diffie çi Martin Hellman in 1976 (cand au prezentat o lucrare la National Computer Conference publicata cateva luni mai tarziu in lucrarea New Directions in Cryptography).

Ralph Merkle a inventat - independent - acelaçi principiu, dar lucrarea i-a apårut doar in 1978 (datoritå unui proces prelungit de publicare).

NSA a susÆinut cå deÆine principiul din 1976, dar nu a putut aduce probe ca urmare paternitatea criptografiei cu chei asimetrice este atribuita lui Diffie si lui Hellman.

Dintre numeroçii algoritmi propuçi, numai trei lucreazå bine atat pentru criptare cat çi pentru semnåturi digitale: RSA, El Gamal çi Rabin. [Schneier]

Utilizarea cea mai mare o au in sisteme hibride pentru transmiterea cheilor de sesiune.

Dezavantajul esenÆial al algoritmilor asimetrici este cå sunt de circa 1000 de ori mai lenÆi decat algoritmii simetrici.

Diffie çi Hellman au propus ca cele douå funcÆii E çi D så indeplineascå çi urmåtoarele proprietåÆi adiÆionale:

çi

de unde posibilitatea utilizårii acestora in semnåturi digitale.

Principiul algoritmilor asimetrici constå in folosirea unor funcÆii greu inversabile. Pentru acestea calculul funcÆiei directe f  trebuie så se facå uçor, iar inversa functiei f () se va calcula uçor doar dacå existå o trapå (informaÆie secretå). Perecheaeste echivalenta cu perechea unde E este functia de criptare iar D cea de decriptare.

Dintre funcÆiile greu inversabile folosite in algoritmii cu chei publice amintim :

factorizarea unui produs de numere prime mari (100 de cifre zecimale) utilizata in cazul algoritmului RSA

gåsirea logaritmului modulo numår prim dintr-un GF(q) cu q foarte mare folosit la algoritmului Rabin (logaritmi discreÆi)

problema rucsacului care sta la baza algoritmului Merkle-Hellman (MH).

Exemplu:

Fie q un numår prim, un intreg x, çi campul Galois [Angheloiu(1972)] [Borda] generat de acesta :

, unde a este un element primitiv al campului GF(q)

FuncÆia se calculeazå uçor .

Utilizatorul A alege in mod aleator un numår   care 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 calcula pornind de la cheia privatå çi de la cheia publicå a partenerului y_B / y_A .

ComunicaÆia este confidenÆialå, dat fiind cå nu se poate calcula dacå nu se cunoaçte cheia privatå x_B/x_A.

Calcularea lui K_AB :

(3.82)

este computaÆional 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 fiecåruia.

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å - deçi gåsirea unor numere prime mari este din punct de vedere computaÆional uçoarå - 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 eficienÆi folosiÆi la ora actualå bazandu-se pe cei elaboraÆi de Legendre.

Metoda de criptare implicå calculul exponenÆial intr-un camp finit (modulo n). Mesajul cifrat se obÆine din mesajul in clar printr-o transformare (codare) bloc. Fie unul din aceste blocuri din mesajul M, bloc care are proprietatea cå  MI(0,n-1) (proprietate ce se obÆine prin modul de impårÆire a mesajului in blocuri). Blocul criptat C corespunzåtor blocului in clar se obÆine calculand exponenÆiala C M^E(mod n), E çi n reprezentand astfel cheia publicå de criptare. Decriptarea se face prin operaÆia M C^D(mod n), D fiind cheia secretå de decriptare.

Cele douå chei E çi D trebuie så satisfacå relaÆia:

M C^D(mod n) M^ED(mod n), (3.83)

pentru ca algoritmul så poatå fi intr-adevår folosit.Pentru aceasta vom pleca de la:

Teorema Euler-Fermat : p este un numår prim dacå a^p-1 1(mod p) oricare ar fi a,aI 1,p].

Astfel dacå am ales n un numår prim, pentru orice bloc MI(0, n-1) avem proprietatea de la care vom porni:

M^j(n)mod (n) (3.84)

unde

j(n) n (3.85)

este numit indicatorul lui Euler

Dacå E si D satisfac relaÆia:

ED(modj(n)) (3.86)

putem scrie:

ED kj(n) j(n) j(n) j(n) j(n) (3.87)

M^ED M^{j(n) j(n) j(n) j(n)} M^j(n) M^j(n) M^j(n).M(mod n),  (3.88)

deci:

ED(modj(n)) Þ M^ED M(mod n).  (3.89)

Astfel am asigurat o transformare reversibilå de criptare pe baza unei exponenÆiale intr-un camp finit. Mai råmane så asiguråm securitatea cheii de decriptare. Aceastå cheie D trebuie så fie aproape imposibil de determinat din cheia de criptare, iar in cazul de mai sus este uçor de determinat avand la dispoziÆie E çi n çtiind cå ED(mod j(n)) 1 çi j(n) n

Securitatea se bazeazå pe idea de factorizare a unui numår mare. Pornind de la aceastå idee, numårul n se poate obÆine prin produsul a douå numere prime mari p çi q:

n pq 

astfel incat indicatorul Euler, in acest caz:

j(n) (p-1)(q-1)  (3.91)

devine mult mai greu de determinat avand la dispoziÆie n.

Folosind acestå schemå se poate obÆine un sistem performant de criptare cu chei publice. Un sistem care asigurå confidenÆialitatea va avea ca elemente urmåtoarele perechi:

(E,n) cheia publicå

(D,n) cheia secretå

Un criptanalist care are la dispoziÆie perechea (E,n) va trebui så determine D Æinand cont cå ED(modj(n)) 1. Pentru asta trebuie determinat j(n) = (p-1)(q-1)  - deci implicit p çi q - problemå care se reduce la a factoriza numårul n (problemå practic imposibilå pentru un n mare).

Exemplu:

Vom utiliza un cifru cu p = 47 çi q = 97.

N = pq = 47 x 97 = 3713

alegand D = 97, E va fi 37 pentru a satisface relaÆia ExD mod((p-1)(q-1)) = 1,

E = [(p-1)(q-1)+1]/D,

astfel pentru a coda mesajul: A SOSIT TIMPUL vom coda mai inainte fiecare literå a alfabetului. De exemplu A B

Mesajul va deveni: 0018 1418 0819 1908 1215 2011

In continuare, vom coda fiecare numår de 4 cifre, avand grijå så fie mai mic decat n:

0018^Emod(n) = 0018³⁷mod(3713) = 3091,

1418^Emod(n) = 1418³⁷mod(3713) = 0943,

Astfel mesajul criptat devine: 3091 0943 3366 2545 0107 2965.

La decriptare, se va calcula pe rand:

3091^Dmod(n) = 3091⁹⁷mod(3713) = 0018 obÆinand mesajul iniÆial.

Dacå panå acum ne-am referit doar la secretizare, odatå principial metoda inÆeleaså, se poate intui uçor aplicabilitatea ei  in autentificare çi in domeniul semnåturilor digitale.

Totuçi, o problemå care mai apare in dezvoltarea unui astfel de algoritm este cea a calculului valorilor sistemului: a numårului n, çi a celor douå chei E çi D, calcul care se va face la nivel de zeci de digiÆi pentru a asigura un nivel de scretizare mare. Se poate spune cå lucrand cu operanzi pe 512 biÆi sistemul este deocamdatå imposibil de spart

Sistemul de criptare cu chei publice RSA este cel mai important dintre sistemele cu chei publice oferind un mare nivel de secretizare, fiind standardizat in domeniul semnåturilor digitale. RSA este recunoscutå ca cea mai sigurå metodå de cifrare çi autentificare disponibilå comercial, imposibil de spart, chiar çi de agenÆiile guvernamentale. Metoda are un mare avantaj prin faptul cå nu sunt disponibile cåi furiçate de atac la sistemul de criptare, cum sunt cunoscute la alte metode. Algoritmul este utilizat pentru protejarea çi autentificarea datelor, parolelor, fiçierelor de cåtre o serie de firme producåtoare de sisteme de programare çi echipamente ca DEC, Lotus, Novell, Motorola precum çi o serie de instituÆii importante (Department of Defense SUA, Boeing, reÆeua bancarå SWIFT, guvernul Belgiei) [Patriciu (1994)].

Algoritmi bazaÆi pe funcÆii hash neinversabile [Scheneier]

O funcÆie hash (H) opereazå asupra unui mesaj pre-imagine de lungime variabilå M çi då la ieçire o valoare hash (h) de lungime constantå (128 sau 160 de biÆi).

[m biÆi- lungimea valorii lui h]

O funcÆie hash neinversabilå (one way hash) trebuie så mai indeplineascå urmåtoarele proprietåÆi:

Dacå se då M, se calculeazå uçor.

Dacå se då h, determinarea lui M astfel incat , este foarte dificilå.

Dacå se då M este greu de gåsit un alt mesaj M astfel incat: , deci transformarea este rezistenta la ciocnire (collusion free).

Aceastå ultimå cerinÆå este necesarå pentru a evita atacul zilei de naçtere (birthday attack), bazat pe determinarea a douå mesaje aleatoare M çi M astfel incat .[Scheneier]

Protocol cu atacul zilei de naçtere descris de Gideon Yuval [Schneier]

Pasii protocolului sunt:

A pregåteçte douå versiuni ale unui contract: unul favorabil lui B, al doilea de escrocare.

A face cateva modificåri subtile la fiecare document çi calculeazå pe h (de exemplu: SPACE se inlocuieçte cu SPACE-BACKSPACE-SPACE, ducerea lui SPACE inainte sau dupå intoarcerea carului). In acest fel A poate genera documente diferite dacå in document sunt 32 de linii).

A comparå valoarea h pentru toate modificårile, pentru a vedea douå identice. Dacå h are 64 biÆi, cele modificåri vor conduce la valori h identice.

A face ca B så semneze o versiune a contractului favorabilå lui, utilizand un document de semnare cu valoarea hash (h).

Mai tarziu, A inlocuieçte contractul semnat de B cu altul, defavorabil dar avand aceeaçi valoare h. In acest mod poate convinge un arbitru cå B a semnat noua variantå.

Morala: este bine så se facå intotdeauna unele modificåri cosmetice ale documentelor care se semneazå.

Dintre algoritmii cei mai utilizaÆi la ora actualå bazaÆi pe funcÆii hash amintim : MD (Message Digest) 4 çi 5 çi SHA(Secure Hash Algorithm) utilizat in standardul de semnåturi digitale DSS respectiv SHS. [Schneier] [Stallings]

Utilizarea algoritmilor [Scheneier]

In cele ce urmeazå vom discuta situaÆia aplicaÆiilor criptografice din lumea civilå: carduri bancare, carduri de acces in clådiri çi la calculatoare, plåÆi pentru diferite servicii, taxe de drumuri, etc., care in fapt constituie imensa majoritate a aplicaÆiilor criptografice (cca 99%). In aceste cazuri nu se utilizeazå o criptografie de maximå securitate ca in cazul aplicaÆiilor militare, diplomatice, etc. iar  atacurile care au loc nu sunt atacuri criptanalitice in adevåratul sens al cuvantului, ci sunt mai degrabå cauzate de angajaÆi necinstiÆi, de implementåri deficitare, de gafe çi erori intamplåtoare. Cei mai buni criptologi considerå cå majoritatea cåderilor din criptosisteme se datoresc deficienÆelor de implementare çi inventivitåÆii proçtilor , çi nu sunt cauzate de algoritmi sau protocoale.

Cum alegem un algoritm? [Scheneier]

Pentru lumea civilå care nu deÆine specialiçti çi centre de testare pe måsurå (invitåm cititorul, pentru a-çi face o imagine sumarå despre ceea ce inseamnå un centru profesionist de criptologie så citeascå articolul lui F.D.Parker The Fall and Rise of Cryptanalysis in Canada din [Deavours]), nu sunt prea multe alternative in aceastå alegere.

Acestea se rezumå la:

alegerea unui algoritm fåcut public pe considerentul cå dacå a fost fåcut public çi nu se çtie cå a fost spart, are çanså så fie aproape sigur (pretty good);

increderea intr-un consultant privat pe considerentul cå fiind dezinteresat va face o evaluare imparÆialå a algoritmilor;

increderea intr-un producåtor de marcå, in baza presupunerii cå acesta nu içi riscå reputaÆia vanzand un echipament ce utilizeazå un algoritm deja depåçit;

increderea in sfatul dat de guvern in acest tip de alegere;

increderea doar in forÆele proprii, deci craerea unui algoritm propriu.

Toate aceste variante suportå discuÆii.

MulÆi aça-ziçi consultanÆi in probleme de securitate (chiar de la firme reputate) çtiu in general foarte puÆin despre criptografie çi acelaçi lucru este valabil çi in cazul producåtorilor de echipamente. NSA are unii dintre cei mai buni criptografi din lume, dar ei nu vor spune tot ceea ce çtiu; ei au propriile interese care de multe ori nu sunt in concordanÆå cu cele ale cetåÆenilor[Scheneier]. In aceste condiÆii, chiar dacå eçti un geniu, a scrie propriul algoritm çi a-l utiliza fårå a avea nici o verificare, este dupå cum considerå B.S. Schneier, curatå nebunie. Acelaçi autor afirmå cå organizaÆiile militare de securitate sunt probabil mai bune decat cele academice pentru cå au tradiÆie in domeniu çi sunt mai bine finanÆate.

Se pune intrebarea: ce algoritmi poate sparge NSA? Tot Schneier afirmå cå pentru majoritatea dintre noi nu existå cale realå de a çtii. InformaÆia privitoare la ce algoritmi pot fi sparÆi este una dintre cele mai secrete. O ipotezå bunå de lucru pentru lumea civilå ar fi cå NSA poate citi orice mesaj criptat dar cå ea nu poate citi toate mesajele, fiind necesarå o selecÆie a Æintelor.

In situaÆia descriså, acelaçi autor afirmå cå cea mai bunå alegere este cea a unui algoritm public. Nu trebuie uitat cå SUA este cel mai mare producåtor de produse criptografice, dar acestea, ca çi tehnologia atomicå, sunt supuse unor legi extrem de severe din punct de vedere al exporturilor.

Algoritmii pentru export, deci cei ce pot fi exportaÆi de SUA, trebuie så fie aprobaÆi de guvernul SUA (aståzi NSA). CredinÆa este cå aceçti algoritmi pot fi sparÆi de cåÆre NSA [Scheneier], deci cumpåråtorii de asemenea produse trebuie så aibå grijå in aceste cumpåråturi de riscurile asumate.

ComparaÆie intre criptografia cu chei simetrice çi cea cu chei publice

ComparaÆia intre cele douå tipuri de bazå de algoritmi criptografici poate fi cuprinså in tabelul 3.13.

Tabelul 3.13 - ComparaÆia algoritmilor simetrici çi cu chei publice

ModalitåÆi de criptare a canalelor de comunicaÆie [Scheneier]

Teoretic, criptarea poate fi fåcutå la nivelul oricårui strat OSI (Open System Interface) al modelului de comunicaÆie.

Practic, criptarea se face la nivelul fizic, caz in care se numeçte criptare legåturå la legåturå (link-by-link encryption) sau la nivelele inalte, caz in care poartå denumirea de criptare capåt la capåt (end-to-end encryption).

Criptarea legåturå la legåturå

Fig. 3.18 - Criptarea legåturå la legåturå

Caracteristici:

Criptarea se face la nivel fizic.

Echipamentul de criptare se pune dupå interfaÆa stratului fizic, care este standardizatå; aceste echipamente hard cripteazå toate datele ce trec prin ele: date, informaÆii de rutare, informaÆii corespunzåtoare protocolului. Datoritå acestui fapt se realizeazå o protecÆie a traficului (traffic flow security), ceea ce constituie un avantaj.

Comutatoarele inteligente çi nodurile cu memorie dintre emiÆåtor çi receptor necesitå decriptare inainte de procesare (vezi nodurile 2 çi 3 din fig. 3.18) ceea ce constituie un dezavantaj, nodurile devenind vulnerabile din punct de vedere al securitåÆii.

Managementul cheilor este simplu, numai nodurile terminale ale unei legåturi necesitand o cheie comunå, ele putand så-çi schimbe cheia independent de restul reÆelei.

Securitatea nu depinde de managementul cheilor.

Criptarea este online.

Criptarea capåt la capåt

Fig 3.19 - Criptarea capåt la capåt (end-to-end)

Caracteristici:

criptarea se face la nivelul transport, echipamentul de criptare punandu-se intre nivelul reÆea çi nivelul transport;

informaÆiile de rutare nu sunt criptate, ceea ce permite analiza traficului çi constituie dezavantajul principal al acestui tip de criptare;

managementul cheilor este mai dificil (dezavantaj), deoarece utilizatorii individuali trebuie så fie siguri cå au aceeaçi cheie;

criptarea este offline (dezavantaj);

asigurå un nivel sporit de securitate (avantaj), in noduri semnalele fiind criptate;

criptarea avand loc la nivel inalt, este independentå de tipul reÆelei, de codurile de linie folosite, de sincronizarea dintre modemuri, de interfeÆele fizice, etc. ceea ce constituie un avantaj;

criptarea la nivelele inalte interacÆioneazå cu softul utilizatorului, care poate diferi de la un calculator la altul (dezavantaj);

echipamentul de criptare poate fi realizat soft sau hard.

ModalitåÆi de criptare a datelor pentru stocare [Scheneier]

Criptarea, in cazul stocårii datelor, are cerinÆe diferite faÆå de criptarea in cazul transmisiunii acestora.

Probleme in transmisiune:

Dacå apar erori in transmisiune, acestea pot fi corectate prin retransmisie.

Cheile utilizate sunt valabile doar pentru o singurå transmisiune (cheie de sesiune), dupå care existenÆa lor nu mai este necesarå.

Probleme in stocare

Datele stocate trebuie så fie protejate prin coduri corectoare de erori deoarece retransmisia este imposibilå.

Cheile trebuie så se påstreze atata timp cat se påstreazå datele stocate (ani de zile in multe situaÆii).

Datele in clar trebuie så existe pe alt disc sau alt suport, de exemplu hartie (de aici posibilitatea unor atacuri cu text in clar).

In aplicaÆii cu baze de date, datele pot fi mai mici decat lungimea blocului majoritåÆii algoritmilor, ceea ce face ca textul cifrat så fie mai mare decat textul in clar.

Viteza dispozitivelor de I/O cer criptåri / decriptåri de mare vitezå, deci criptare hard, iar in unele aplicaÆii se cer algoritmi de mare vitezå.

Managementul cheilor este mult mai complicat, deoarece utilizatori diferiÆi necesitå acces la diferite fiçiere sau porÆiuni de fiçiere.

Cand este necesarå criptarea pentru stocare a datelor de pe un suport de date cu o capacitate mare (de exemplu un disc dur) apar niçte probleme suplimentare cum ar fi: problema numårului de chei folosite la criptare çi cea a criptårii datelor la nivel de disc sau la nivel de fiçier.

Caracteristici ale criptårii informaÆiei de pe un disc cu o singurå cheie

este simplå deoarece nu implicå reÆinerea de cåtre utilizatori a unui numår mare de chei de criptare (avantaj);

nivelul de securitate este redus deoarece un eventual criptanalist ar avea la dispoziÆie o cantitate imenså de text criptat (dezavantaj);

nu se poate restricÆiona accesul utilizatorilor doar la anumite fiçiere (dezavantaj).

Caracteristici ale criptårii datelor folosind mai multe chei

este greoaie deoarece fiecare utilizator care doreçte så aibå acces la informaÆia din mai multe fiçiere trebuie så cunoascå cheile cu care

acestea sunt criptate (dezavantaj - deoarece trebuiesc reÆinute un numår mare de chei);

dezavantajul de mai sus poate fi contracarat dacå se copiazå cheile de criptare intr-un fiçier separat care va fi la randul såu cifrat cu o cheie care va fi cunoscutå de toÆi utilizatorii;

utilizatorii au acces doar la acele fiçiere la care cunosc cheia de criptare (avantaj - din punt de vedere al nivelului de securitate).

ComparaÆii dintre criptarea hard çi soft [Scheneier]

Una dintre problemele cele mai importante in implementarea algoritmilor criptografici este aceea care se referå la modul in care aceasta se va face çi anume: prin folosirea de circuite specializate (implementare hardware) sau prin programe (implementare software). Alegerea uneia sau alteia dintre cele douå implementåri se face dacå se cunosc bine avantajele çi dezavantajele pe care acestea le au.

Caracteristici ale implementårii hard

este extrem de avantajoaså din puntul de vedere al vitezei de lucru;

nivelul de securitate este ridicat deoarece circuitele pot fi protejate la modificåri sau se pot folosi cipuri VLSI speciale care nu permite modificåri ale schemei;

din moment ce radiaÆia electromagneticå emiså de un circuit poate da informaÆii nedorite despre ceea ce se intamplå in el, cutiile de criptare specializate pot fi ecranate;

sunt uçor de instalat ele putand fi conectate fårå probleme la diferitele dispozitive care se doresc a fii protejate.

Caracteristici ale implementårii soft

au o vitezå de lucru mult mai micå decat implementårile hard;

sunt mai puÆin sigure deoarece un program de codare sau decodare ce ruleazå pe un calculator nespecializat nu are nici un fel de protecÆie fizicå;

o protejare mai eficientå a unei implementåri soft ar presupune introducerea criptårii la nivelul sistemului de operare;

este avantajoaså din punctul de vedere al portabilitåÆii çi flexibilitåÆii in cazul folosirii de limbaje de programare care au versiuni ce ruleazå sub diferite sisteme de operare;

utilizarea çi upgrade-ul se pot face foarte uçor in cazul unei astfel de implementåri.

Ca o concluzie in acest sens s-ar putea spune cå pentru un sistem criptografic necesar in aplicaÆii militare, diplomatice sau alte domenii cu grad maxim de securitate, sunt indicate clar implementårile hard (NSA de exemplu nu autorizeazå decat acest tip de implementare), pe cand in celelalte aplicaÆii din domeniul civil sau comercial se pot folosi implementårile sub formå de program (soft).

Lungimea cheilor [Scheneier]

Pentru a vedea ce lungime a cheii ar fi de dorit intr-un sistem criptografic, cel care il proiecteazå trebuie så råspundå in prealabil la cateva intrebåri cum ar fi:

Cat valoreazå informaÆiile care trebuie protejate?

Cat timp trebuie så fie aceste informaÆii confidenÆiale?

Care ar fi categoriile de persoane interesate in datele care trebuie protejate?

De ce resurse dispun aceçti oponenÆi?

Prima dintre intrebårile de mai sus se referå la natura datelor de protejat. Astfel, unele date cum ar fi niçte e-mail-uri simple pot valora panå la 100$, o listå a clienÆilor cu adresele lor in jur de 1.000$, situaÆiile financiare ale clienÆilor unei bånci 100.000$ pe cand o cheie care permite accesul liber la conturile unei banci de renume poate valora miliarde de dolari. Aceste detalii sunt bine de cunoscut de cåtre proiectant deoarece este greu de crezut cå un oponent ar folosi resurse in valoare de 100.000$ pentru a sparge un cod care protejeazå informaÆii care pentru el ar valora 1.000$ dar, in mod sigur, acelaçi oponent çi-ar folosi resursele mai sus amintite dacå acele informaÆii ar valora så zicem 10.000.000$.

Tot referitoare la natura datelor este çi intrebarea a doua. Çtirile senzaÆionale ale unui post de televiziune sunt confidenÆiale doar pe un timp foarte scurt (maximum o zi) ele fiind apoi publicate, o listå de invitaÆi la o seratå poate fi de actualitate pe perioada catorva såptamini pe cand diferite documente de la arhivele statului trebuiesc protejate pe perioade mari de timp. In acest sens, dacå dorim så protejåm date pe o perioadå mare de timp trebuie så Æinem seama de faptul cå cheile de criptare de o anumitå lungime care in momentul actual sunt considerate ²extrem de greu de spart² pot deveni ²uçor de spart² in viitor pe måsurå ce se descoperå tehnologii çi metode matematice noi çi se måreçte viteza echipamentelor de lucru.

A-Æi cunoaçte oponenÆii çi anume persoanele sau organizaÆiile care sunt interesate de datele pe care doreçti så le protejezi çi a cunoaçte resursele pe care aceçtia le au çi pe care ar fi dispuçi så le aloce pentru a avea acces la aceste date este de asemenea un aspect pe care orice utilizator sau proiectant al unui sistem criptografic trebuie så-l ia in seamå cand alege lungimea cheii folosite la criptare.

Lungimea cheilor in sisteme cu chei simetrice

Intr-un criptosistem bazat pe chei simetrice, securitatea datelor depinde de doi factori importanÆi çi anume securitatea algoritmului çi lungimea cheii. Dacå primul dintre aceçti doi factori este mai important (este inutilå folosirea unei chei de dimensiuni mari in cazul unui algoritm despre care s-a demonstrat cå este slab), cel de-al doilea este mai uçor de demonstrat.

Un algoritm criptografic simetric, dupå cum s-a aråtat in subcapitolele anterioare, constå intr-o secvenÆå de substituÆii çi permutåri, puterea sa stand in cheie çi nu in secretul algoritmului. Pentru a testa securitatea unui astfel de algoritm, acesta este supus atenÆiei opiniei publice çi specialiçtilor açteptandu-se reacÆiile acestora. Dacå acesta rezistå atacurilor çi criticilor un timp suficient se poate considera cå este puternic. Oricum, nimeni nu poate garanta cå pe viitor nu pot apårea noi tipuri de atacuri criptanalitice care så compromitå securitatea unui algoritm considerat ²sigur² in prezent.

Dacå, dupå cum s-a aråtat mai sus, testarea securitatea unui algoritm este o sarcinå dificilå, calcularea complexitåÆii unui atac bazat pe forÆå brutå dacå se cunoaçte lungimea cheii este extrem de simplå. Så luåm ca çi exemplu pentru aceasta cazul DES-ului: lungimea cheii fiind de 56 de biÆi trebuie så se incerce maximum variante panå la gåsirea celei corecte existand 50% çanse de a reuçi dupå incercåri.

In [Scheneier] sunt amintite cateva atacuri posibile bazate pe forÆå brutå asupra unui sistem protejat de o cheie simetricå. Se aratå cå cele mai de succes atacuri sunt cele hard realizate cu ajutorul unor maçini special concepute pentru a sparge codurile, viteza atacului depinzand de doi factori:

numårul cheilor ce trebuiesc testate

viteza fiecårui test.

Cel mai important dintre acestea este numårul cheilor care este in cazul in care lungimea unei chei este n. Cel de-al doilea factor este mai puÆin important deoarece, chiar dacå testarea unei chei pentru un algoritm se face de 10 ori mai incet decat in cazul altuia, aceastå cifrå este infimå in comparaÆie cu numårul extrem de mare de chei cu care se lucreazå. Complexitatea unui atac prin forÆå brutå este liniarå ea crescand odatå cu creçterea lungimii cheii iar datoritå acestui fapt un astfel de atac se preteazå excelent unei procesåri paralele folosind mai multe procesoare.

Cu cat tehnologia este mai performantå (viteza de lucru a unui procesor este mai mare) çi resursele ce se alocå sunt mai ridicate (se folosesc mai multe procesoare care lucreazå in paralel), cu atat mai mare este necesitatea utilizårii de chei de lungime mai mare. Astfel, in [Scheneier] se aratå cå la tehnologia anului 1995 cu o maçinå care ar costa in jur de 1.000.000$ o cheie de 40 de biÆi s-ar sparge in 0,2 secunde, una de 56 de biÆi in 3,5 ore, una de 64 de biÆi in 37 de zile, una de 80 de biÆi in 7000 de ani pe cand una de 128 de biÆi in ani (de 100 de milioane de ori varsta universului).

Un exemplu concludent in sensul celor aråtate anterior a apårut in literatura de specialitate in anul 1998 çi se referea la un record de spargere a algoritmului DES stabilit de o echipå de criptanaliçti de la Electronic Frontier Foundation din care fåcea parte çi renumitul criptograf Paul Kocher. Echipa mai sus amintitå a reuçit descifrarea unei criptograme care fusese obÆinutå prin criptarea DES unui mesaj-test scris in limba englezå in doar 56 de ore. Ceea ce este de asemenea interesant cu privire la acest record este faptul cå maçina cu care s-a realizat acest lucru este de fabricaÆie proprie çi a fost construitå in mai puÆin de un an, costul ei ridicandu-se la mai puÆin de 250.000$.

Din cele aråtate anterior, cititorul s-ar putea intreba ce rost are så se mai discute amånuntele de mai sus in loc så se foloseascå o cheie de lungime extrem de mare (de exemplu 3 Kb) care ar fi de nespart printr-un atac bazat pe forÆa brutå. Din påcate, lucrurile nu stau atat de simplu, lungimea unei chei nu poate fi oricat de mare deoarece in acest caz apar probleme reale referitoare la viteza de lucru a algoritmilor iar managementul unor chei de asemenea dimensiune este extrem de dificil.

O a doua abordare a problemei atacului prin forÆå brutå pe langå cea hard amintitå anterior este cea soft. O astfel de abordare este cam de 1000 de ori mai lentå ([Scheneier]) dar are totuçi un avantaj çi anume acela cå nu il costå pe atacator nimic. Un program care så ruleze pe un calculator çi care så testeze mulÆimea de chei este extrem de uçor de realizat çi chiar dacå este foarte posibil ca atacatorul så nu poatå sparge codul intr-un timp rezonabil, cel puÆin acesta va çti cå aceastå incercare nu l-a costat altceva dacat timp.

Dacå çansele de reuçitå in cazul unui atac software de pe un calculator sunt foarte mici datoritå vitezei slabe, acestea cresc dacå atacul se ²rafineazå² prin folosirea mai multor staÆii de lucru care vor avea fiecare de verificat o parte din spaÆiul de chei çi care vor lucra in acelaçi timp pentru a sparge codul. Astfel, se poate calcula cå o reÆea de 400 de calculatoare capabile så execute 32.000 de criptåri pe secundå pot finaliza cu succes un atac prin forÆå brutå in mai puÆin de o zi. Dacå numårul de calculatoare ar fi mai mare (de ordinul milioanelor) çi viteza de lucru a acestora ar creçte, rezultatele ar fi mult mai bune. Ca çi un exemplu in acest sens aç aminti tentativa incununatå de succes a proprietarilor site-ului www.distributed.net care au reuçit in februarie 1998 så criptanalizeze un mesaj protejat prin intermediul algoritmului DES in 39 de zile cu ajutorul a peste 22.000 de utilizatori ai Internet-ului din intreaga lume.

Din cele aråtate anterior, s-ar putea deduce cå singurele probleme intr-un atac software eficient bazat pe folosirea mai multor calculatoare care så lucreze in acelaçi timp ar fi cele ale numårului de calculatoare folosite çi a vitezei de lucru a acestora dar, de fapt, cea mai mare dificultate intalnitå este aceea de a convinge pe milioanele de proprietari ai calculatoarelor de care este nevoie så permitå folosirea lor in scopul dorit. Aceastå dificultate se concretizeazå in enormul timp care s-ar pierde cu munca de låmurire çi in posibilele refuzuri care pot apårea iar ea poate fi combåtutå çi prin mijloace ²neortodoxe². Unul dintre acestea ar consta in folosirea unui virus special conceput ([Scheneier]) care så se propage çi så infesteze un numår mare de calculatoare çi care, odatå ajuns pe un calculator gazdå, il va determina pe acesta så lucreze la testarea de chei (muncå de criptanalizå) pe perioada in care este in açteptare.

Lungimea cheilor in sisteme cu chei publice

Aça cum am aråtat çi in secÆiunea 3.3.2.2 in cazul criptosistemelor cu chei publice, cifrarea çi descifrarea nu se bazeazå pe o secvenÆå de substituÆii çi transpoziÆii ci pe folosirea funcÆiilor neinversabile cu trapå. Acestea sunt de fapt funcÆii matematice greu inversabile (a cåror inversare este o problemå consideratå dificilå) dintre care amintim: factorizarea numerelor mari (stå la baza celor mai cunoscuÆi algoritmi asimetrici: RSA, LUC etc.) çi logaritmii discreÆi. In cele ce urmeazå voi avea in vedere doar factorizarea dar cititorul poate face extrapola consideraÆiile mele çi in cazul logaritmilor discreÆi.

Din cele aråtate anterior se poate deduce cå un atac bazat pe forÆå brutå pentru astfel de criptosisteme nu presupune iterarea spaÆiului cheilor posibile (lucru imposibil de altfel datoritå dimensiunii mari ale cheilor) ci incercarea de factorizare a unor numere de dimensiuni foarte mari. Çi in acest caz, avand in vedere cå algoritmul este presupus a fi sigur in lipsa unor dovezi contrare, securitatea se bazeazå extrem de mult pe lungimea cheii. Dacå sistemele criptografice simetrice se folosesc la protejarea datelor pentru un timp relativ scurt (cheia simetricå este folositå ca çi cheie de sesiune dupå care içi pierde valabilitatea), cele asimetrice sunt adeseori folosite pentru a proteja date de mare valoare pe timp indelungat (perechea de chei publicå-privatå se schimbå mult mai rar decat cea secretå) de unde çi necesitatea imperioaså de a alege chei de o lungime suficient de mare pentru a le face sigure atat in prezent cat çi pe un viitor predictibil.

Metodele de factorizare çi tehnologia folositå sunt in plinå dezvoltare in ultimul timp ceea ce face ca dimensiunile necesare pentru o cheie så crescå de la an la an. Totuçi, la fel ca çi in cazul cheilor simetrice, lungimea nu poate nici så fie exagerat de mare din cauza vitezei de calcul slabe çi a faptului cå o cheie prezumptivå de 15 Kb ar fi greu de manipulat. In tabelul 3.14 se prezintå o lungime recomandatå a cheilor intr-un sistem criptografic asimetric prognozatå pe urmåtorii 15 ani([Scheneier]).

Tabelul 3.14 - Lungimi recomandate ale cheilor dintr-un criptosistem asimetric

O altå problemå legatå de lungimea cheilor de criptare se referå la cazul folosirii unui criptosistem hibrid (foloseçte chei asimetrice la distribuÆia cheilor çi o cheie secretå ca çi cheie de sesiune la transmiterea datelor). In acest caz, trebuie så se acorde o atenÆie deosebitå corelårii lungimii cheii secrete cu cea a cheilor asimetrice (folosirea unei perechi de chei asimetrice de o lungime suficientå este inutilå dacå cheia de sesiune are o lungime micå çi invers). Acest lucru este o urmare a faptului cå in orice sistem trebuie så ne açteptåm ca atacul så se efectueze in zona cea mai expuså.

Lungimea rezumatului (valorii) unei funcÆii hash

Avand in vedere utilitatea funcÆiilor hash çi folosirea acestora in aplicaÆii sensibile de genul semnåturilor digitale, este de açteptat cå acestea vor fi supuse atacurilor criptanalitice din partea unor categorii diferite de oponenÆi specialiçti sau nespecialiçti motiv pentru care nivelul de securitate oferit de ele trebuie så fie ridicat.

In mod normal, pentru a se realiza o protecÆie eficientå a informaÆiei in faÆa celor douå atacuri, rezumatul trebuie så fie pe o lungime cat mai mare. Dacå rezumatul este de lungime m atunci efortul calculaÆional trebuie så fie de ordinul 2^m.

Atacurile la securitatea rezumatului pot fi de douå feluri:

atacuri in cazul cårora se porneçte de la un rezumat dat çi se incearcå gåsirea unui alt mesaj astfel incat

atacuri in care se cautå gåsirea a douå mesaje care så aibå acelaçi rezumat.

Atacurile din cea de-a doua categorie sunt cunoscute çi sub numele de ²atacurile zilei de naçtere² iar efortul computaÆional va scådea la doar

Managementul cheilor [Scheneier]

Managementul cheilor constituie cea mai grea parte din criptografie. Astfel, dacå algoritmii çi protocoalele prezentate anterior in aceastå lucrare au la bazå o muncå asiduå de cercetare çi au fost testate impotriva diferitelor atacuri, partea cea mai slabå a unui sistem criptografic este cea legatå de activitatea umanå. De exemplu, este mult mai rentabil din punctul de vedere al resurselor ce se cheltuiesc så mituieçti un funcÆionar sau så obÆii date confidenÆiale cu forÆa de la o persoanå decat så contruieçti o maçinå care så gåseascå o cheie secretå prin forÆå brutå intr-un timp rezonabil. De asemenea, utilizarea unor parole simple sau a unor anumite chei slabe in cazul diferiÆilor algoritmi criptografici pot diminua drastic securitatea acestora.

In continuare vom prezenta cititorului principalele probleme legate de managementul cheilor cum ar fi generarea, transferul, verificare, utilizarea, actualizarea, stocarea, durata de viaÆå çi distrugerea acestora.

Generarea cheilor

Pentru a obÆine o securitate bunå a datelor cu ajutorul unui algoritm criptografic trebuiesc evitate posibilele chei slabe. Primul pas in acest sens il constituie generarea cheilor.

Existå multe aplicaÆii care folosesc un spaÆiu redus al cheilor, de exemplu cheia poate fi alcåtuitå doar din caractere alfanumerice (in cazul DES care are cheie pe 56 de biÆi - 7 octeÆi - dacå se utilizeazå doar 26 de litere mici dimensiunea spaÆiului cheilor ar fi drastic reduså de la la ceea ce l-ar face uçor de spart). Astfel de aplicaÆii, deçi se bazeazå pe algoritmi puternici nu asigurå un grad potrivit de securitate datoritå folosirii improprii a acestora.

O altå problemå apare cand utilizatorii trebuie så-çi aleagå cheia secretå. S-a constatat cå in aceste cazuri, in locuri unor combinaÆii fårå sens de litere mici, mari çi cifre care så poatå fi ²ghicite² mai greu, marea majoritate a utilizatorilor aleg propriul nume sau prenume, data naçterii, adresa sau alte combinaÆii care ei considerå cå sunt fårå sens pentru orice altcineva decat propria persoanå. Astfel de chei pot fi sparte extrem de uçor prin intermediul atacurilor bazate pe dicÆionar. AplicaÆiile specializate bazate pe acest tip de atac testeazå o serie de cuvinte çi combinaÆii uzuale. Motivul pentru care oamenii aleg parole çi chei slabe de genul celor prezentate anterior este acela cå sunt mult mai uçor de reÆinut.

Generarea de chei aleatoare se poate face prin intermediul calculatorului folosind metode criptografice sau necriptografice descrise pe larg in [Stallings] çi [Scheneier]. Dupå generare trebuie Æinut seama de faptul cå existå un numår mic de chei slabe in cazul fiecårui algoritm. Deçi aça cum am aråtat, numårul lor este extrem de mic in comparaÆie cu dimensiunea spaÆiului cheilor çi probabilitatea ca så se genereze aleator tocmai una dintre acestea este foarte micå, este de dorit ca aplicaÆiile så testeze cheia dacå nu este cumva ²slabå². De exemplu, algoritmul DES are mai multe categorii de chei slabe:

chei care determinå dupå prima permutare din algoritm numai biÆi de 1 sau numai biÆi de 0 prin urmare cele 16 chei interne vor fi egale K₁ = K₂ = = K₁₆. De asemenea, aceste chei au proprietatea cå nu existå nici o diferenÆå intre operaÆiile efectuate la criptare çi cele de la decriptare (4 la numår);

chei care au proprietatea cå formeazå doar douå tipuri diferite de chei interne fiecare apårand de cate 8 ori (12 chei);

chei care genereazå doar patru tipuri de chei interne pe parcursul aplicårii algoritmului DES (48 de chei).

Pentru detalii despre cheile slabe din cazul algoritmului DES, cititorul este rugat så consulte [Seberry].

Transferul cheilor

O altå problemå in managementul cheilor este aceea a transferului acestora. Intr-un criptosistem simetric cele douå pårÆi implicate in transmisiune folosesc aceeaçi cheie. Dupå ce una dintre pårÆi genereazå cheia, trebuie så o transfere. A transmite pur çi simplu cheia pe canal ar fi total greçit deoarece un prezumptiv atacator poate avea acces la ea çi dupå aceea ar putea descifra cu ajutorul ei toate mesaje pe care le schimbå pårÆile intre ele. Dacå cele douå pårÆi se pot intalni intr-un loc sigur sau dacå au un canal secret special pentru transmiterea cheii, transferul se face uçor dar in caz contrar apar probleme.

SoluÆia viabilå pentru transferul cheilor ar fi folosirea criptosistemelor cu chei asimetrice dar existå situaÆii cand acestea nu se pot utiliza. O alta tehnicå utilizeazå distribuÆia cheii prin canale paralele. Aceastå metodå presupune impårÆirea cheii in mai multe bucåÆi, transmiterea fiecåreia in parte pe un alt canal çi recompunerea ei la destinaÆie. Avantajul constå in faptul cå atacatorul trebuie så intercepteze toate componentele pentru a gåsi cheia.

Verificarea cheilor

Dupå ce cheia secretå a fost transmiså çi a ajuns la destinaÆie, cel care a recepÆionat-o trebuie så o verifice pentru a se asigura cå aceasta provine de la persoana care trebuie çi cå nu au intervenit erori in transmisie.

Prima dintre cele douå probleme de mai sus se rezolvå uçor dacå transferul s-a efectuat faÆå in faÆå sau printr-un curier sau canal sigur. Dacå s-a folosit un sistem criptografic asimetric, trebuie verificat faptul cå cheia publicå care se va folosi la decriptare aparÆine chiar transmiÆåtorului legitim çi nu unui atacator. Acest lucru se poate face prin telefon sau se poate folosi o autoritate de certificare in care så se aibå incredere.

Pentru a combate erorile care pot apårea in transferul cheii se folosesc coduri detectoare çi corectoare de erori iar pentru verificare se cripteazå cu aceasta o valoare constantå primii 2 sau 4 biÆi ai textului cifrat urmand a fi transmiçi impreunå cu cheia.

Utilizarea cheilor

Utilizarea cheilor in criptarea propriu-ziså prezintå probleme in cazul in care cifrarea se face din soft. Aceasta se datoreazå faptului cå sistemele de operare moderne - fiind multitasking - folosesc discul hard ca çi memorie extinså, salvand datele de fiecare datå cand au nevoie de memorie suplimentarå çi reincårcandu-le cand au nevoie de ele. Dupå astfel de operaÆii, este posibil ca bucåÆi de text in clar sau chiar cheia så fie salvate pe disc de unde ele pot fi recuperate ulterior de cåtre un atacator.

Aceste probleme nu apar inså in cazul unei implementåri hard, folosirea unor cartele care au cheia imprimatå permiÆand chiar distrugerea cheii in cazul unei incercåri de fraudå.

In cazul in care se doreçte utilizarea controlatå a unei chei (de exemplu se doreçte utilizarea ei doar in cazul unei anumite maçini sau doar la anumite momente de timp) se poate folosi un vector de control (VC) care så conÆinå restricÆiile dorite [Scheneier].

Actualizarea cheilor

Actualizarea cheilor se face in sistemele care trebuie så-çi modifice cheia secretå foarte des datoritå problemelor care ar apårea la fiecare distribuÆie a cheilor. Astfel, in loc så se genereze zilnic cate o nouå cheie de cåtre una dintre pårÆi çi så se transfere aceasta, ambele pårÆi implicate vor genera noua cheie pornind de la cea veche printr-un algoritm reciproc convenit. Metoda are avantajul operativitåÆii sporite dar nu este deloc mai sigurå datoritå faptului cå atacatorul poate face çi el actualizarea dacå reuçeçte så obÆinå o cheie.

Stocarea cheilor

Stocarea cheilor este simplå dacå sistemul are un singur utilizator. Intr-o astfel de situaÆie, de multe ori cheia este påstratå doar in mintea respectivei persoane nefiind nevoie ca så existe duplicate ale ei pe disc. Este cazul sistemului IPS [Scheneier] care permite utilizatorului så introducå direct cei 64 de biÆi ai cheii sau un çir mai lung de caractere din care se obÆine cheia prin o tehnicå specialå de generare.

O modalitate practicå de stocare a cheii o constituie inscripÆionarea acestora pe cartele magnetice (smart card). Cand se doreçte criptarea sau decriptarea, se introduce cartela intr-un cititor ataçat calculatorului. Avantajul acestei metode de stocare este acela cå ²materializeazå² cheia prin faptul cå påstrarea ei se poate face ca çi in cazul unei chei obiçnuite ceea ce uçureazå inÆelegerea conceptului de protecÆie a acesteia pentru utilizatori. Dacå se doreçte så nu existe un singur utilizator care så posede cheia se pot folosi douå cartele, fiecare avand inscripÆionatå jumåtate din aceasta. Prin aceasta nici unul dintre cei doi utilizatori nu vor cunoaçte cheia, la criptare trebuind så fie introduse ambele carduri in acelaçi timp.

Copii de siguranÆå (backup)

Så presupunem cå o persoanå X deÆine o cheie secretå pe care o foloseçte la criptarea unor documente importante. Dacå acea persoanå uitå cheia nu va mai fi in stare så mai descifreze conÆinutul acestor documente. Aceeaçi situaÆie apare dacå X este angajatul unei firme çi suferå un accident dupå ce a folosit cheia la criptarea documentele firmei respective. In cazurile de mai sus, problemele pot fi rezolvate doar dacå s-a fåcut iniÆial copii de siguranÆå ale cheilor (back-up).

O primå metodå in acest sens este aceea de a se påstra copii de siguranÆå ale tuturor cheilor salariaÆilor unei firme intr-un seif sub pazå çi in caz de nevoie så se aibå acces la ele. Problema care apare este cå trebuie så se aibå incredere in paznicul care are acces la ele, paznic care poate fi corupt. O imbunåtåÆire a acestei metode constå in existenÆa a mai multor paznici (seifuri) fiecare dintre ei cunoscand sau avand acces la o parte din fiecare cheie. Astfel, prin mituirea unui paznic un atacator nu obÆine suficiente date pentru a periclita securitatea sistemului.

Durata de viaÆå a cheilor

Din motive de securitate, cheile nu trebuie så aibå o perioadå de viaÆå nedefinitå. Cu cat aceastå perioadå este mai mare cu atata sunt mai mari çansele ca un atacator så reuçeascå spargerea ei avand mai mult timp çi text cifrat la dispoziÆie. O cheie folositå pe o perioadå indelungatå in general a fost utilizatå la criptarea mai multor documente, ceea ce creçte puternic costurile care apar in cazul pierderii ei.

Diferitele chei trebuie så aibå durate de viaÆå diferite. Cheile secrete din sistemele simetrice ar trebui så aibå perioada de viaÆå micå (tendinÆa actualå este de folosire a lor sub forma de chei de sesiune). Chiar çi aici s-ar putea face o diferenÆiere dupå viteza de transfer care este caracteristicå canalului de transmisie (cheile folosite pentru criptare in transmisiuni rapide trebuie schimbate mai des cantitatea de date codatå fiind mai mare). Cheile publice sau cele folosite in criptarea cheilor de sesiune vor fi schimbate mai rar datoritå dimensiunii lor çi a faptului cå sunt folosite asupra unor cantitåÆi mici de date.

Distrugerea cheilor

In secÆiunea anterioarå am aråtat cå cheile trebuie så aibå o perioadå de viaÆå limitatå dupå care ele trebuie distruse. Modul de distrugere al acestora depinde de mediul pe care au fost stocate.

Dacå cheia era scriså pe suport de hartie, foaia respectivå trebuie arså sau distruså, dar trebuie avut grijå la aparatul de mårunÆire a hartiei deoarece unele modele din comerÆ sunt de calitate proastå çi existå posibilitatea ca un atacator så poatå recupera conÆinutul ei. Un EEPROM sau un disc conÆinand cheia trebuie rescris de mai multe ori succesiv pentru a fi siguri cå nici un bit din aceasta nu se mai påstreazå pe cand EPROM-urile sau PROM-urile se distrug.

ObservaÆie:

In secÆiunea 3.7.6.4 am prezentat problemele care apar in cazul criptårii çi decriptårii soft sub sisteme de operare moderne care folosesc tehnica de swapping. Dacå totuçi se folosesc implementåri soft, atunci cand se doreçte distrugerea cheii vor trebui çterse toate fiçierele swap de pe discul hard pe care s-a lucrat çi se va folosi un program ce suprascrie date de multiple ori. Nici in acest mod nu va fi eliminate total posibilitatea ca anumite pårÆi ale cheii så mai existe pe undeva pe hard dar cel puÆin probabilitatea de gåsire a ei de cåtre un atacator va scådea.

3.8 Bibliografie

Angheloiu, I., Gyorfi, E., Patriciu, V.V. (1986): Securitatea çi protecÆia informaÆiei in sistemele electronice de calcul, Editura Militarå, Bucureçti

Angheloiu, I.(1972) :Teoria codurilor, Editura Militarå, Bucureçti

Borda, M. (1999): Teoria transmiterii informaÆiei, Dacia, Cluj-Napoca

Deavours, C.A., Kahn, D. (1998): Selections from Cryptologia, Artech House

Deitel, H.M., Deitel, P.J., Nieto, T.R. (2001): E-Business and E-Commerce. How to program, Prentice Hall.

Fc ¹9, Franklin, M. (1999): Financial Cryptography : Proceedings of the Third International Conference, Fc'99, Anguilla, Springer Verlag, Nov.

Hankerson, D. R., Hoffman, D. G., Leonard, D. A., Linder, C.(2000): Coding Theory and Cryptography: The Essentials (Pure and Applied Mathematics, Vol 234), Marcel Dekker, Rev&ex, 2^nd edition, Sep.

India International Conference in Cryptology in India 2000 Calcutta (2000): Progress in Cryptology : Indocrypt 2000 Proceedings of the First International Conference in Cryptology Calcutta, Springer Verlag, Dec.

Jalal, F., Williams, P. (1998): Digital Cerificates: Applied Internet Security, Addison Wesley Pub. Co.

Keyes, J. (1998): Securities Technology Handbook, CRC Press, Dec.

Kranakis, E., Van Oorschot, P. C.(1997) : Selected Areas in Cryptography, Kluwer Academic Publishers, Sep.

McCurley, K. S., Ziegler, C. D. (1999): Advances in Cryptology, 1981-1997 : Electronic Proceedings and Index of the Crypto and Eurocrypt Conferences 1981-1997 (Lecture Notes in Computer Science), Springer Verlag, Jun.

Menezes, A., Orschot, P., van, Vanstone, S. (1997): Handbook of Applied Cryptography, CRC Press Inc.

Patriciu V. V. (1998): Securitatea informaticå in UNIX çi Internet, Editura Tehnicå, Bucureçti

Patriciu, V. V. (1994): Criptografia çi securitatea reÆelelor de calculatoare, Edittura Tehnicå, Bucureçti

Ribenboim, P. (1996): The New Book of Prime Number Records, 3 edition, Springer Verlag, May

Schmied, G. (1998): High Quality Messaging and Electronic Commerce: Technical Foundations, Standards and Protocols, Springer Verlag, Nov.

Schneier, B. (1996): Applied cryptography. Protocols, Algorithms and Source Code in C, J. Willey & Sons, New York

Seberry, J.,Pieprzyk, J. (1993): Cryptography: An Introduction to Computer Security, Prentice Hall, Sydney

Seroussi, G. Smart N. et al. (2000): Eliptic Curve an Cryptography, Cambrige University Press.

Stallings, W. (2001): Business Data Communications, Prentice Hall, 4th edition, Jan.

Stallings, W. (1999): Cryptography and Network Security - Principles and Practice, Prentice Hall, Second Edition

Stallings, W. (1995): Network and Internetwork Security. Principles and Practice, Prentice Hall

Swanson, M.D., Kobayashi, M., Tewfik, A. (1998): Multimedia Data - Embedding and Watermarking Technologies, Proceedings of the IEEE, Vol. 86, No. 6, June

Tilborg, H.C.A, van.: Fundamentals of Cryptology(1999): A Professional Reference and Interactive Tutorial (Kluwer International Series in Engineering and Computer Science, Secs), Kluwer Academic Pub, nov.

Wiener M. (1999): Advances in Cryptology - Crypto '99 : Proceedings of the 19th Annual International Cryptology Conference, Santa Barbara, California, Usa, Springer Verlag, Sep.