Metode i tehnici de protejare a informaiei economice

Capitolul 1 Bazele criptografiei

Capitolul 1 Bazele criptografiei

1. Bazele criptografiei

Definiia criptografiei pleac de la etimologia cuvntului cripto care vine din grecescul kryptos, care nseamn ascuns, obscur, secret, iar grafie de la graphia, adic scriere. O definiie concis a termenului este dat de Yaman Akdeniz, n articolul su Cryptography and Encryption: Criptografia, definit ca , trateaz mijloacele prin care comunicaiile i datele pot fi codificate pentru a preveni descoperirea lor prin interceptare, folosind coduri, cifruri i alte metode, astfel nct numai anumite persoane s poat vizualiza mesajul iniial[VeI04].

Primele menionri despre criptografie apar acum 4000 de ani n Egiptul antic.

n India, nu mult dup ce scrisul a fost inventat, se pomenete de scriere secret; dovada o gsim n Kama Sutra, unde scrisul secret este pe lista lucrurilor pe care trebuie s le tie o femeie. Arabii, n al 7-lea secol .e.n., au fost primii care au scris despre metode de criptanaliz. Istoricii au descoperit un text folosit n magie datat n jurul anului 855 .e.n. Detalii interesante din istoria criptografiei le gsim n cartea lui David Kahn [Kah90].De-a lungul istoriei criptografia a avut un rol fascinant att n diplomaie i spionaj ct i n lumea afacerilor. De la rzboiul galic pn la rzboiul din golful Persic, de la afacerea Dreyfus pn la maina Enigma, criptografia a schimbat nu de puine ori cursul istoriei. nc

de la nceputuri, criptografia a rspuns cererii de a transmite informaii secrete; mult vreme singura preocupare a fost de a crea metode de transformare a informaiei de aa natur nct ea s nu fie accesibil unui potenial intrus. O dat cu apariia metodelor electronice de procesare a informaiei rolul criptografiei a devenit mult mai variat. Aceast perioad care ncepe n 1949 este cunoscut ca i criptografie modern i va fi descris n capitolul 5.

1.1 Terminologie

S presupunem c E dorete s trimit un mesaj lui D; notm cu E expeditorul i cu D destinatarul. E ncredineaz mesajul lui T, care l va livra lui D; T devine mediul de transmitere. Dac o entitate, I, dorete mesajul i ncearc s obin acces la mesaj, o vom numi interceptor sau atacator. De fiecare dat dup ce E trimite mesajul via T, mesajul este expus, astfel c I poate ncerca s acceseze mesajul pe una din urmtoarele ci:

ntreruperea mesajului, prin ncercarea de a-l opri s ajung la D, afectnd deci disponibilitatea mesajului;

interceptarea mesajului, prin abilitatea interceptorului de a citi sau asculta mesajul, afectnd deci confidenialitatea mesajului;

modificarea mesajului, prin capturarea sa i schimbarea sa ntr-un anume mod;

fabricarea unui mesaj asemntor cu cel autentic, care s fie livrat lui D ca i cum ar proveni de la E, afectnd astfel integritatea mesajului.

Criptarea este un proces de codificare a unui mesaj astfel nct nelesul mesajului este ascuns utiliznd un algoritm i o cheie specific; decriptarea este procesul invers: transformarea unui mesaj criptat napoi n forma sa original utiliznd un algoritm i o cheie specific. Cele dou procese sunt complementare. Se mai folosesc termenii codificare, cifrare i decodificare, decifrare pentru criptare, respectiv decriptare (exist diferene minore de semnificaie: codificare se refer la texte, cifrare la litere i criptare la ambele). Un sistem folosit pentru criptare i decriptare se numete sistem criptografic sau criptosistem (o definiie complet se gsete n capitolul 5).

Algoritmi de criptare

Forma original a unui mesaj se numete text clar, iar forma criptat se numete text cifrat. Definim un mesaj de text clar P ca un ir de caractere P=[p1, p2, ..., pn]; textul cifrat corespunztor este C=[c1, c2, ..., cm]. Formal, transformrile ntre textul clar i cel cifrat le notm C=E(P) i P=D(C), unde E este algoritmul de criptare i D este algoritmul de decriptare. Evident, un criptosistem satisface condiia P=D(E(P)).

n general algoritmii folosesc o cheie K, astfel nct textul cifrat depinde att de textul clar ct i de valoarea cheii: C=E(K,P). n anumite cazuri cheile de criptare i decriptare sunt identice (vezi algoritmii simetrici din capitolul 5), astfel nct P=D(K, E(K,P)) iar n alte cazuri, cheile de criptare i de decriptare sunt diferite (vezi algoritmii cu chei publice din capitolul 5). O cheie de decriptare, KD, inverseaz criptarea de cheie KE, astfel nct P=D(KD, E(KE, P)).

O cheie permite criptri diferite a unui text clar prin schimbarea valorii cheii. Folosirea unei chei mrete securitatea. Dac algoritmul de criptare ajunge la cunotina interceptorului, viitoarele mesaje vor rmne secrete, deoarece interceptorul nu va cunoate valoarea cheii. Un cifru care nu necesit folosirea unei chei se numete cifru fr cheie.

Criptanaliza

Criptografie nseamn, etimologic, scriere ascuns, folosirea criptrii pentru a ascunde nelesul unui text. Un criptanalist studiaz criptarea i mesajele criptate, n scopul descoperirii formei de text clar a mesajului. Att un criptograf ct i un criptanalist ncearc s translateze materialul codificat la forma original; ns criptograful lucreaz de partea expeditorului sau destinatarului legitim, n timp ce criptanalistul lucreaz de partea interceptorului neautorizat. Criptologia este studierea criptrii i decriptrii, ea incluznd att criptografia ct i criptanaliza.

Scopul unui criptanalist este de a sparge o criptare; aceasta nseamn ncercarea de a deduce nelesul unui text cifrat sau determinarea unui algoritm de decriptare care se potrivete cu algoritmul de criptare. Analistul poate ncerca una sau toate, din urmtoarele ci:

spargerea unui mesaj individual;

recunoaterea de forme n mesajele criptate, astfel nct s devin capabil s sparg mesajele viitoare prin aplicarea unui algoritm de decriptare;

depistarea de puncte slabe n algoritmul de criptare, chiar fr a intercepta vreun mesaj.

Detalii despre metodele moderne de atac criptografic se gsesc n capitolul 4.

Un algoritm de criptare poate fi fragil, n sensul c un analist care dispune de resurse de timp i date suficiente, poate determina algoritmul. Totui, aspectul practic este de asemenea important. S considerm o schem de cifrare care presupune o schema invers de decifrare care necesit 1030 operaii. Folosind un calculator la nivelul tehnologiei actuale, care execut 1010 operaii pe secund, decifrarea va dura 1020 secunde, adic aproximativ 1012 ani. n acest caz, chiar dac teoretic un algoritm de decifrare exist, el poate fi ignorat ca fiind nepractic n condiiile tehnologiei actuale.

n legtur cu fragilitatea algoritmilor de criptare apar dou observaii. n primul rnd, nu e raional s presupunem c criptanalistul va ncerca chiar calea cea mai grea i cea mai lung. n exemplul de mai sus, un demers mai ingenios poate face ca timpul de decriptare s scad la doar la 1015 operaii, ceea ce, la aceeai vitez de 1010 operaii pe secund, nseamn puin mai mult de o zi.

n al doilea rnd, estimarea fragilitii se bazeaz pe nivelul actual al tehnologiei. innd cont de viteza progresului n tehnologia i tehnica de calcul, este riscant s caracterizm un algoritm ca sigur doar pentru c nu poate fi spart cu tehnologia actual.

Reprezentarea caracterelor

Pentru nceput, s considerm seria mesajelor scrise ntr-un alfabet latin, A ... Z. Codificm numeric fiecare liter astfel: A=0, B=1,..., Z=25.

Aceast codificare permite operaiuni aritmetice ntre litere i coduri numerice. Expresii ca A+3=D sau K-1=J au o interpretare natural. Calculele se fac presupunnd alfabetul ca fiind circular. Astfel Y+3=B i fiecare rezultat este cuprins ntre 0 i 25.

Aceast form de aritmetic se numete aritmetic modulo n, n care orice numr mai mare dect n este nlocuit de restul mpririi la n, cuprins ntre 0 i n-1.

1.2 Cifruri monoalfabetice (substituii)

Cifrul monoalfabetic sau substituia simpl este o tehnic de criptare care folosete o tabel de coresponden conform creia un caracter se nlocuiete cu caracterul sau simbolul corespunztor din tabel.

1.2.1 Cifrul lui Caesar

Dac ar trebui s alegem un singur exemplu al criptografiei clasice, acesta ar fi cifrul lui Caesar, nu att datorit celebritii mpratului roman de care se leag folosirea lui, ci pentru c principiul su de baz s-a meninut nealterat aproape dou milenii.

Cifrul lui Caesar este numit astfel dup Iulius Caesar, care a fost primul care l-a folosit. n cifrul lui Caesar, fiecare liter este translatat la litera care se afl la un numr fix de poziii dup aceasta n alfabet. Caesar folosea o deplasare de 3 poziii, astfel nct litera pi din text clar era criptat ca litera ci din textul cifrat prin regula: ci=E(pi)=pi+3.

O tabel complet de translaie a cifrului Caesar este:

litera din text clar:

ABCDEFGHIJKLMNOPQRSTUVWXYZlitera din text cifrat:

defghijklmnopqrstuvwxyzabcFolosind aceast criptare, mesajul ACESTA ESTE CIFRUL CAESARva fi criptat astfel:

ACESTA ESTE CIFRUL CAESAR

dfhvwd hvwh fliuxo fdhvdu

Avantajele i dezavantajele cifrului Caesar

Primele cifruri trebuiau s fie simple i uor de folosit. Orice cifru care era suficient de complicat nct algoritmul su trebuia s fie transmis n scris, risca s fie descoperit dac interceptorul captura mesagerul cu respectivele instruciuni scrise. Cifrul lui Caesar este un cifru extrem de simplu. Regula pi+3 era uor de memorat; expeditorul putea s-i noteze pe loc tabela de translaie, s codifice mesajul de transmis i apoi s distrug hrtia coninnd cifrul. Aceast regul este ns i cea mai mare slbiciune a cifrului Caesar. O criptare sigur nu trebuie s permit interceptorului ca, dintr-o cantitate mic de informaii s poat s deduc regula de criptare.

Criptanaliza cifrului Caesar

Analiznd textul cifrat, indiciile care provin din textul clar sunt evidente: spaiul dintre dou cuvinte, cuvntul ESTE translatat n hvwh. Aceste indicii fac acest cifru uor de spart.

Spaiul dintre dou cuvinte a fost translatat n el nsui, ceea ce ofer o informaie important despre lungimea cuvintelor; n criptare, spaiile dintre cuvinte sunt adesea terse, presupunnd c destinatarul legitim poate sparge cele mai multe mesaje n cuvinte relativ simplu. Pentru uurina scrierii i decodrii, mesajele sunt adesea sparte n mod arbitrar n blocuri de lungime uniform, astfel nct este evident pentru interceptor c locurile n care mesajul conine spaii nu au nici o semnificaie.

n orice limb, cuvintele de dou sau trei litere sunt relativ puine. Astfel, un atac const n substituirea cuvintelor scurte cunoscute din textul cifrat i ncercarea de a substitui caracterele care mai apar n alte locuri n text. Fcnd mai multe ncercri i verificnd dac textul decodificat are vreun neles se va putea decripta mesajul.

Acest gen de criptanaliz este unul ad hoc, bazat pe deducie i ncercare. O alt abordare este considerarea literelor comune pentru nceputul cuvintelor, sfritul cuvintelor sau care prefixe sau sufixe sunt cele mai folosite n limba respectiv, conform unor liste publicate i folosite de ctre criptanaliti.

1.2.2 Alte substituii monoalfabetice

n substituiile monoalfabetice, alfabetul este amestecat i fiecare liter din textul clar corespunde unei litere unice din textul cifrat. Formal, o permutare este o reordonare a elementelor unei mulimi. Dou exemple de permutri ale mulimii formate din numerele de la 1 la 10 sunt: (={1, 3, 5, 7, 9, 10, 8, 6, 4, 2} i (2={10, 9, 8, 7, 6, 5, 4, 3, 2, 1}. O permutare este o funcie, astfel nct se poate scrie ((3)=5 sau (2(7)=4. Dac a1, a2, ..., ak sunt literele unui alfabet de text clar i ( este o permutare a mulimii {1, 2, ..., k}, ntr-o substituie monoalfabetic avem. De exemplu, ((a) poate fi funcia ((a)= 25-a, astfel nct A va fi codificat ca A, B ca Y, i Z va fi reprezentat ca A. Aceast permutare este uor de memorat i reprodus, i deci uor de folosit. Totui, fiecare pereche de litere text clar text cifrat comunic n ambele sensuri: ((F)=u i ((U)=f. Aceast dubl coresponden ofer un ajutor suplimentar interceptorului.

O alternativ este folosirea unei chei, un cuvnt care controleaz criptarea. Dac acest cuvnt este cifru, expeditorul sau destinatarul mai nti scrie alfabetul i apoi scrie cheia sub primele litere ale alfabetului, continund cu literele rmase ntr-o ordine uor de memorat.

ABCDEFGHIJKLMNOPQRSTUVWXYZ

cifruabdeghjklmnopqstvwxzy

n acest exemplu, deoarece cheia este scurt, majoritatea literelor din textul clar sunt doar la una sau dou poziii distan fa de echivalentele lor din textul cifrat. Cu o cheie mai lung, distana este mai mare i mai greu predictibil. Deoarece ( este o funcie bijectiv, literele care se repet dintr-o cheie cum ar fi endomorfism sunt nlturate.

ABCDEFGHIJKLMNOPQRSTUVWXYZ

endomrfisabcghjklpqtuvwxyz

Spre sfritul alfabetului nlocuirile sunt din ce n ce mai apropiate i ultimele apte caractere i corespund. Cum literele de la sfritul alfabetului sunt dintre cele mai rar folosite, aceast expunere nu este totui de un mare ajutor interceptorului.

E de dorit ns o rearanjare mai puin regulat a literelor. O posibilitate este dat de permutarea ((i)= (3*i) mod 26, ceea ce conduce la

ABCDEFGHIJKLMNOPQRSTUVWXYZ

adgjmpsvzbehknqtwzcfilorux

Complexitatea criptrii i decriptrii monoalfabetice

Criptarea i decriptarea folosind un astfel de algoritm se poate efectua prin consultarea direct a unei tabele ca cele deja prezentate. Durata transformrii unui caracter este constant, deci timpul de criptare a unui mesaj de n caractere este proporional cu n.

Criptanaliza cifrurilor monoalfabetice

Tehnicile descrise pentru spargerea cifrului Caesar pot fi folosite i pentru alte cifruri monoalfabetice. Cuvinte scurte, cuvinte cu forme repetitive i litere iniiale i finale de uz frecvent, toate sunt indicii pentru ghicirea permutrii. Operaiunea seamn cu cuvintele ncruciate: se ncearc o ipotez, se continu pn cnd toate cuvintele sunt la locul lor sau pn se ajunge la o contradicie, dup care procesul se repet. Pentru mesajele lungi aceast abordare este dificil.

1.3 Cifruri de substituie polialfabetice

Slbiciunea cifrurilor monoalfabetice este dat de faptul c distribuia lor de frecven reflect distribuia alfabetului folosit. Un cifru este mai sigur din punct de vedere criptografic dac prezint o distribuie ct mai regulat, care s nu ofere informaii criptanalistului.

O cale de a aplatiza distribuia este combinarea distribuiilor ridicate cu cele sczute. Dac T este criptat cteodat ca a i alt dat ca b, i dac X este de asemenea cteodat criptat ca a i alt dat ca b, frecvena ridicat a lui T se combin cu frecvena sczut a lui X producnd o distribuie mai moderat pentru a i pentru b.

Dou distribuii se pot combina prin folosirea a dou alfabete separate de criptare, primul pentru caracterele aflate pe poziii pare n text clar, al doilea pentru caracterele aflate pe poziii impare rezultnd necesitatea de a folosi alternativ dou tabele de translatare. Exemplu: permutarea ((a)= (3*a) mod 26 i (2(a)= ((5*a)+13) mod 26.

1.3.1 Tabelele Vigenere

Tehnica celor dou permutri poate conduce i la cazul nedorit al unei coliziuni accidentale a dou litere de frecven sczut, sau a dou litere de frecven ridicat. Pentru a evita asemenea situaii, n condiiile n care permutarea ( este aleas arbitrar, permutarea (2 trebuie aleas astfel nct s fie complementar primei permutri; dac ( transform o liter cu frecven ridicat cum este E n x, atunci (2 trebuie s transforme o liter de frecven sczut n x. Aceast tehnic necesit o anumit planificare, dar nu este prea dificil.

O alt abordare este extinderea numrului de permutri. Cu trei permutri, folosite alternativ, ansa unei distribuii plate crete. Extensia maxim este de 26 de permutri, astfel nct o liter din text poate fi criptat ca orice liter din textul cifrat.

Un tablou Vigenere este o colecie de 26 de permutri. Aceste permutri se prezint ca o matrice de dimensiuni 26x26, cu toate cele 26 de litere pe fiecare linie i pe fiecare coloan.

1 2

01234567890123456789012345

abcdefghijklmnopqrstuvwxyz

A abcdefghijklmnopqrstuvwxyz 0

B bcdefghijklmnopqrstuvwxyza 1

C cdefghijklmnopqrstuvwxyzab 2

D defghijklmnopqrstuvwxyzabc 3

E efghijklmnopqrstuvwxyzabcd 4

F fghijklmnopqrstuvwxyzabcde 5

G ghijklmnopqrstuvwxyzabcdef 6

H hijklmnopqrstuvwxyzabcdefg 7

I ijklmnopqrstuvwxyzabcdefgh 8

J jklmnopqrstuvwxyzabcdefghi 9

K klmnopqrstuvwxyzabcdefghij 10

L lmnopqrstuvwxyzabcdefghijk 11

M mnopqrstuvwxyzabcdefghijkl 12

N nopqrstuvwxyzabcdefghijklm 13

O opqrstuvwxyzabcdefghijklmn 14

P pqrstuvwxyzabcdefghijklmno 15

Q qrstuvwxyzabcdefghijklmnop 16

R rstuvwxyzabcdefghijklmnopq 17

S stuvwxyzabcdefghijklmnopqr 18

T tuvwxyzabcdefghijklmnopqrs 19

U uvwxyzabcdefghijklmnopqrst 20

V vwxyzabcdefghijklmnopqrstu 21

W wxyzabcdefghijklmnopqrstuv 22

X xyzabcdefghijklmnopqrstuvw 23

Y yzabcdefghijklmnopqrstuvwx 24

Z zabcdefghijklmnopqrstuvwxy 25A stabili care este coloana care urmeaz a fi folosit este principalul dezavantaj al rotaiei celor 26 de permutri, care poate fi ns evitat prin folosirea unui cuvnt cheie. Literele acestuia vor selecta coloanele pentru criptare.

De exemplu, s criptm mesajul CIFRURILE POLIALFABETICE SUNT MAI SIGURE, folosind cuvntul cheie cripto. mprim mesajul n text clar n blocuri de cte cinci litere i scriem cuvntul cheie, repetndu-l de cte ori e nevoie ca fiecrei litere din text clar s-i corespund o liter din cuvntul cheie.

cript ocrip tocri ptocr iptoc ripto cript o

CIFRU RILEP OLIAL FABET ICESU NTMAI SIGUR E

ezngn fkcme hzkrt utpgk qrxgw ebbtw uzojk s

Pentru a cripta o liter din text clar, alegem linia din tabloul Vigenere corespunztoare acelei litere i coloana corespunztoare literei din cuvntul cheie aflate deasupra. La intersecia liniei cu coloana se afl litera din text cifrat. n limbaj matematic, s notm caracterele din linia cuvintelor cheie cu k1, k2,..., kn, iar literele corespunztoare din text clar cu p1, p2, ..., pn. Fiecare liter pi este convertit n litera cifrat de pe linia pi i coloana ki a tabloului. Cu un cuvnt cheie de ase litere, acest algoritm efectiv mprtie efectul frecvenei fiecrei litere la ase alte litere, ceea ce aplatizeaz substanial distribuia. Se pot folosi cuvinte cheie lungi, dar un cuvnt cheie de trei litere e de obicei suficient pentru a netezi distribuia.

1.3.2 Criptanaliza substituiilor polialfabetice

Substituiile polialfabetice sunt, aparent, mai sigure dect cele monoalfabetice. Mijloacele criptanalitice sunt complicate i nu pot fi aplicate fr ajutorul calculatorului.

Din pcate, nici substituiile polialfabetice nu sunt de neatacat. Metoda de a sparge o astfel de criptare const n determinarea numrului de alfabete folosite, descompunerea textului cifrat n poriunile care au fost criptate cu acelai alfabet urmat de rezolvarea fiecarei poriuni ca o substituie monoalfabetic.

In literatura criptografic sunt prezentate dou metode puternice care pot decripta mesaje scrise chiar folosind un numr mare de alfabete i anume, metoda Kasiski i metoda indexului de coinciden.

Metoda Kasiski pentru forme repetitive

Metoda Kasiski, numit astfel dup ofierul prusac care a dezvoltat-o, este o cale de a gsi numrul alfabetelor care au fost folosite la criptare.

Metoda se bazeaz din nou pe aspectul de regularitate al limbii. n texte se repet nu numai litere, dar de asemenea grupuri de litere sau cuvinte ntregi. De exemplu, n limba romn se folosesc terminaii n ea, -re, -area, -nt, nceputuri de cuvinte ca su-, cu-, che-, forme ca ie-, -chi-, -cea- sau cuvinte ca i, cu, la, mai, sau, este, sunt etc mai frecvent dect alte combinaii de litere.

Metoda Kasiski folosete urmtoarea regul: dac un mesaj este codificat cu n alfabete n rotaie ciclic i un cuvnt particular, sau un grup de litere apare de k ori n textul clar, el va fi codificat de aproximativ k/n ori cu acelai alfabet. De exemplu, dac cuvntul cheie are ase litere, exist doar ase feluri diferite de a poziiona cuvntul cheie deasupra unui cuvnt din text clar. Un cuvnt care apare n text de mai mult de ase ori va fi criptat de cel puin dou ori identic.

Metoda Kasiski folosete fragmentele duplicate n text cifrat. Pentru ca o fraz n text clar s fie criptat n acelai fel de dou ori, cheia trebuie s treac printr-un numr ntreg de rotaii i s se ntoarc napoi n acelai punct. Pentru aceasta, distana dintre formele care se repet trebuie s fie un multiplu al lungimii cheii.

Pentru a folosi metoda Kasiski, se identific n text cifrat toate formele care se repet. Formele repetitive scurte, cum ar fi grupurile de cte dou litere, se ignor. Orice form care conine mai mult de trei litere este luat n considerare (probabilitatea ca dou secvene de cte patru litere s nu aparin aceluiai segment n text clar este de 0,0000021).

Pentru fiecare apariie a formei se marcheaz poziia de start; apoi se calculeaz distana dintre poziiile de start succesive. Aceste distane trebuie s fie un multiplu al lungimii cheii i metoda continu cu descompunerea lor n factori primi. n urma acestei analize se determin cele mai probabile valori pentru lungimea cheii.

Indexul de coinciden

Cunoscnd lungimea cheii, mesajul se mparte n segmente criptate cu acelai alfabet. Dac toate caracterele dintr-un segment au fost criptate cu acelai alfabet, ele trebuie s aib o distribuie de frecven similar cu cea a limbii mesajului n text clar i asemntoare cu a celorlalte segmente.

O alt metod de criptanaliz estimeaz ct de bine se potrivete o anumit distribuie cu distribuia literelor n limba n care a fost scris mesajul n text clar. Indexul de coinciden este o msur a variaiei dintre frecvene ntr-o distribuie.

Numim distribuie de limb, distribuia de frecven a literelor din limba n care a fost scris mesajul n text clar. n cazul unei substituii monoalfabetice, aceeai distribuie apare i n mesajul n text cifrat. Dac s-au folosit dou alfabete, frecvenele joase i cele ridicate se amestec, avnd loc o anumit nivelare a distribuiei. Procesul continu pe msura folosirii unui numr din ce n ce mai mare de alfabete, pn la cazul limit n care toate literele apar cu aceeai frecven.

Indexul de coinciden este o msur pe baza creia se va determina numrul de alfabete care s-au folosit la criptare.

S ncercm s msurm neuniformitatea unei distribuii. Mesajul n text clar este caracterizat de distribuia de limb. Notm cu Proba probabilitatea ca o liter aleas aleator din mesajul n text clar s fie a, Probb s fie b,..., Probz s fie z.

Evident,

Proba + Probb + ... + Probz = Probi = 1.

O distribuie perfect plat, uniform, se caracterizeaz prin faptul c toate literele au aceeai probabilitate de apariie:

Proba = Probb = ... = Probz =

Graficul unei astfel de distribuii este o linie orizontal. Pentru o distribuie oarecare, diferena dintre Proba i 1/26 este variaia sa fa de distribuia uniform.

Sinkov definete n [Sin66] o msur a neuniformitii sau variana, ca fiind:

var = =

= =

==

=- 0,0384

Pentru o distribuie uniform, variana este zero. Probi2 este probabilitatea ca dou caractere alese la ntmplare din text s coincid cu caracterul i. ns probabilitatea de apariie a unei litere nu este cunoscut dect dac se cunoate algoritmul prin care literele au fost generate. Aceast probabilitate va fi aproximat pe baza frecvenelor observate.

ntr-un text de n litere n text cifrat, fie Freci numrul de apariii a literei i. Probabilitatea ca alegnd dou litere ntmpltoare acestea s fie i este Freci * (Freci - 1). Pentru c perechea (a,b) este identic cu perechea (b,a), produsul numr fiecare pereche de dou ori. Deci exist Freci * (Freci - 1)/2 moduri de a alege o pereche (i, i). Numrul de cazuri favorabile supra numrul de cazuri posibile va da probabilitatea: . Dar aceast probabilitatea tim c este aproximativ Probi2.

Indexul de coinciden, notat IC, este un mod de a aproxima variana de la datele observate.

IC=

Indexul de coinciden ia valori ntre 0,0384, pentru o substituie polialfabetic cu o distribuie perfect plat, la 0,068 pentru o substituie monoalfabetic.

Cu ct mesajul n text cifrat este mai lung, iar textul original are o distribuie normal a literelor, indexul de coinciden poate prezice numrul de alfabete.

Alfabete1234510mai multe

IC0,0680,0520,0470,0440,0440,0410,038

Dup cum se observ n tabelul de mai sus IC scade rapid de la un alfabet la trei i constituie o bun predicie pentru numrul de alfabete doar atunci cnd numrul acestora este mic. Pe baza unei prime predicii mesajul n text cifrat se mparte n segmente corespunznd, teoretic, unui singur alfabet. Aceast situaie se verific aplicnd din nou metoda Kasiski; n cazul n care variana nu are valoarea ateptat, se reia ntreg procesul, ncercnd o nou ipotez privind numrul de alfabete folosite la criptare.

Concluzii privind cifrurile polialfabetice

Paii n analiza unui cifru polialfabetic sunt:

1. Se folosete metoda Kasiski pentru a afla numrul probabil al alfabetelor folosite la criptare. Dac nici unul din numerele probabile nu conduce la o mprire n segmente monoalfabetice, atunci metoda de criptare nu este substituia polialfabetic.

2. Se calculeaz indexul de coinciden pentru a valida prediciile de la punctul 1.

3. Cnd pasul 1 i 2 indic o valoare probabil, textul cifrat se mparte n submulimile separate corespunztoare; se calculeaz pentru fiecare indexul de coinciden, care trebuie s confirme ipoteza.

Att metoda Kasiski, ct i indexul de coinciden necesit disponibilitatea unei mari cantiti de text cifrat. Ele dau rezultate cnd alfabetele de criptare sunt aplicate repetat la intervale periodice.

1.3.3 Substituia perfect

Substituia ideal ar trebui s foloseasc un numr mare de alfabete pentru o distribuie de nerecunoscut i pentru a nu prezenta nici o form aparent, care s permit alegerea unui alfabet la un moment dat.

Tabloul Vigenere permite folosirea doar a 26 de alfabete diferite. S presupunem ns c generm un ir infinit de numere ntre 0 i 25. Fiecare termen al acestui ir poate selecta un alfabet (coloan) care s poat fi folosit la criptarea urmtorului caracter n text clar.

Folosirea unui ir infinit nerepetitiv de alfabete contrazice metoda Kasiski. O fraz care se repet n text clar nu va fi criptat niciodat n acelai fel, pentru c nu exist forme repetitive n alegerea alfabetului. Forme care se repet n text cifrat vor apare doar accidental. Indexul de coinciden pentru un astfel de text cifrat va avea o valoare apropiat de 0,038, indicnd un numr mare de alfabete. Dar calcularea frecvenelor pentru caractere aflate pe poziii multiplu de k n text cifrat, k=1, 2, ... nu va conduce la un rezultat conclusiv, deoarece ele nu au fost criptate cu acelai alfabet.

Astfel, o selecie nerepetitiv de alfabete de criptare va face imposibil criptanaliza cu metodele descrise mai sus.

Bloc notes-ul

Ideea care st la baza cifrului perfect este numit bloc notes. Numele vine de la o metod de criptare n care un numr mare de chei nerepetitive se scriu pe cte o foaie de hrtie, lipite mpreun ntr-un bloc notes. Dac aceste chei au lungimea de 20 de caractere i trebuie trimis un mesaj de 300 de caractere, expeditorul va desprinde primele 15 foi din bloc notes, va scrie cheile una dup alta deasupra mesajului n text clar i va cripta folosind o tabel asemntoare cu tabloul Vigenere, dup care va distruge cheile folosite.

Destinatarul va folosi un bloc notes identic cu cel al expeditorului. Dup recepionarea mesajului, destinatarul va folosi numrul necesar de chei i va descifra mesajul ca n cazul unei substituii polialfabetice cu o cheie lung. Algoritmul are acelai efect ca i o cheie de o lungime egal cu numrul de caractere din bloc notes.

Exist dou probleme cu aceast metod: necesitatea unei sincronizri absolute ntre expeditor i destinatar i nevoia unui numr nelimitat de chei. Se pot genera cu uurin un numr mare de chei aleatoare, dar tiprirea, distribuirea, stocarea i gestionarea lor constituie o problem.

iruri de numere aleatoare mari

O aproximare corect a unui bloc notes utilizabil pe calculator este un generator de numere aleatoare. De fapt, numerele aleatoare generate de calculator nu sunt aleatoare: n realitate ele formeaz un ir cu o perioad foarte mare care, n practic, este acceptabil pentru o perioad de timp limitat.

Expeditorul unui mesaj de 300 de caractere va genera pe calculator urmtoarele 300 de numere aleatoare, le va aduce n intervalul 0-25 i va folosi fiecare numr pentru a cripta caracterul corespunztor din mesajul n text clar.

Cele mai multe generatoare de numere aleatoare pe calculator sunt de tip multiplicativ:

, unde

c i b sunt constante, iar w este un numr mare, de obicei cel mai mare ntreg reprezentabil pe un cuvnt de memorie din calculator. Dndu-se suficieni termeni ai irului, este posibil s se determine constantele c i b, dac w este ghicit ca fiind ntregul maxim. Dac irul de numere aleatoare nu este suficient de lung, generatorul nu prezint securitate.

Cifrul Vernam

Cifrul Vernam este un tip de bloc notes dezvoltat la AT&T, imun la majoritatea atacurilor criptanalitice. Criptarea de baz presupune un ir lung de numere aleatoare nerepetitive care sunt combinate cu mesajul n text clar. Invenia lui Vernam folosete o band de hrtie perforat de o lungime arbitrar, montat la un dispozitiv de tip telex. Banda conine numere aleatoare care se combin cu caracterele tastate la telex. irul de numere aleatoare este nerepetitiv i fiecare band este folosit o singur dat. Att timp ct banda nu se repet i nu se refolosete, acest tip de cifru este imun la atacul criptanalitic, deoarece mesajul n text cifrat nu prezint forme ale cheii.

Cifrul Vernam binar

Aceast schem funcioneaz i la criptarea unui mesaj binar, prin folosirea unui ir aleator de cifre binare care poate fi combinat modulo 2 cu biii din mesaj. Rezultatul este un alt ir binar. Combinarea se poate face prin adunare modulo 2, ceea ce se realizeaz prin funcia sau exclusiv sau adunare fr transport. Aceste funcii sunt implementate ca instruciuni main, ceea ce simplific aplicarea algoritmului.

Spargerea generatoarelor de numere aleatoare

Muli algoritmi de criptare folosesc numere aleatoare. Sigurana criptrii depinde de ct de aleatore sunt numerele folosite, n sensul de a nu conine forme repetitive uor de observat. Un contraexemplu este irul binar 01010101... Un exemplu de ir aleator este irul de numere de dou cifre obinut dintr-o carte de telefon (o prezentare in extenso a generatoarelor de numere pseudo-aleatoare se gsete n capitolul 3).

O surs obinuit de numere aleatoare este un program de calculator care genereaz numere pseudo-aleatoare. Un astfel de generator este cel congruenial liniar, care folosete o valoare iniial, r0. Termenii irului se obin prin formula de recuren , unde a, b i n sunt constante i aparin intervalului 0, n-1. Dac r0 i a sunt relativ prime cu n, orice numr dintre 0 i n-1 va fi generat nainte ca secvena s se repete. O dat repetiia nceput, ntreaga secven se repet n aceeai ordine.

Problema care se pune n cazul acestei forme de generator de numere aleatoare este dependena sa. Deoarece fiecare numr depinde doar de precedentul su, constantele se pot determina prin rezolvarea unui sistem de ecuaii n care termenii irului sunt ghicii prin metoda cuvntului probabil.

Secvene lungi luate din cri

O alt surs de numere presupus aleatoare este orice carte, pies muzical sau orice alt obiect a crui structur poate fi analizat. Un posibil bloc notes este cartea de telefon. Expeditorul i destinatarul trebuie s aib cri de telefon identice. Ei pot stabili s nceap cu pagina 35, s foloseasc ultimele dou cifre ale fiecrui numr de telefon, modulo 26 ca o liter cheie pentru un cifru de substituie polialfabetic folosind o form prestabilit a tabloului Vigenere. O idee similar este folosirea oricrei cri de proz, n care cheia este constituit din literele textului.

ntreeserea a dou mesaje

Este posibil s se cripteze dou mesaje o dat, astfel nct interceptorul s nu poat distinge mesajele. Un mesaj este cel real, iar celalalt este un mesaj fals, pe care l cunosc att expeditorul ct i destinatarul. Acest mesaj fals este folosit ca i cheie.

Criptanalistul poate deduce ambele mesaje n text clar, dar nu va putea s disting ntre mesajul real i cheie.

1.4 Transpoziii (permutri)

Scopul unei substituii este confuzia, o ncercare de a face dificil aflarea modului n care mesajul i cheia au fost transformate n text cifrat. O transpoziie este o criptare n care literele mesajului sunt rearanjate. Scopul transpoziiei este difuzia, mprtierea informaiei din mesaj i cheie n textul cifrat. Transpoziiile ncearc s sparg formele constituite. Deoarece transpoziia este o rearanjare a simbolurilor din mesaj, se numete i permutare.

Transpoziii pe coloane

Transpoziia pe coloane const n rearanjarea caracterelor mesajului n text clar pe coloane. Urmtorul exemplu este o transpoziie pe 5 coloane. Caracterele mesajului n text clar se separ n blocuri de cte cinci litere i se scriu unul sub altul:

c1c2c3c4c5c6c7c8c9c10c11c12c13c14c15c16c17c18c19c20c21c22c23c24c25Mesajul n text cifrat se formeaz scriind literele pe coloane:

c1c6c11c16c21c2c7c12c17c22...

Dac lungimea mesajului nu este multiplu al lungimii liniei, ultima coloan va conine mai puine litere. O liter mai puin folosit, cum ar fi X, se folosete pentru a completa ultima coloan.

Complexitatea criptrii/decriptrii

Acest cifru nu presupune alte operaiuni, n afara scrierii literelor ntr-o anumit ordine i citirii lor ntr-o alt ordine, deci timpul necesar aplicrii algoritmului este proporional cu lungimea mesajului. Algoritmul necesit citirea ntregului mesaj n text clar nainte de a-l cripta, ceea ce presupune un spaiu de memorie i o anumit ntrziere care depind direct de lungimea mesajului. Din aceste cauze, algoritmul nu este potrivit pentru mesaje lungi.

Criptanaliza prin analiza digramelor

Aa cum exist frecvene caracteristice anumitor litere, exist de asemenea formaiuni caracteristice de cte dou litere, numite digrame, i de cte trei litere, numite trigrame, a cror frecven este determinat pentru limba n care este scris mesajul.

Atacul de baz asupra transpoziiilor pe coloane nu este la fel de precis ca cel asupra cifrurilor de substituie. Chiar dac transpoziiile par mai puin sigure dect substituiile, pentru c las literele neschimbate, munca criptanalistului este mai dificil, deoarece se bazeaz pe interpretarea uman a ceea ce pare corect.

Primul pas n analiza transpoziiei este calculul frecvenei literelor. Faptul c toate literele apar cu frecvena lor normal indic folosirea unei transpoziii. Decriptarea reuete atunci cnd se determin lungimea coloanei (mesajul n text cifrat se scrie pe coloane i se citete pe linii invers ca la criptare). Acest proces presupune compararea exhaustiv a irurilor din textul cifrat.

Presupunnd lungimea coloanei k, se construiesc digramele c1ck+1, c2ck+2, ... ckc2k, dup care se verific dac apar digramele comune limbii n care este scris mesajul, prin calcularea frecvenelor. La pasul urmtor se verific dac majoritatea digramelor par rezonabile, calculnd variana ntre cele k frecvene al digramelor considerate. Dac se obine o oarecare potrivire, procedeul se repet pentru urmtoarele perechi de coloane. Dac acest lucru nu se ntmpl, se consider o alt valoare pentru k i se ncearc din nou.

Algoritmul dublei transpoziii

Cifrul dublei transpoziii implic dou transpoziii pe coloane, cu un numr diferit de coloane, aplicate una dup alta. Prima transpoziie mut literele adiacente, iar a doua sparge seriile scurte de litere care apar n coloanele adiacente ale primei transpoziii.

Criptanaliza

Notm cu L lungimea mesajului, cu m numrul de coloane i cu k lungimea unei coloane. Cu ajutorul literei de completare avem relaia:

L = m * k.

Aplicnd prima transpoziie, caracterul de pe poziia i se va muta pe poziia

E(i) = k * ([(i-1) mod m] + (i-1)/m + 1)

A doua transpoziie acioneaz similar cu prima, avnd ns alte valori pentru m i k.

Dubla transpoziie este un exemplu de cifru multiplicativ, n care o criptare este aplicat rezultatului unei alte criptri. Cifrurile multiplicative se obin prin compunerea a dou funcii: dac E1 i E2 sunt cele dou transpoziii, compunerea lor E1 o E2 este de asemenea o transpoziie.

Atacurile mpotriva algoritmului dublei transpoziii se bazeaz pe localizarea perechilor de litere n text cifrat care, probabil, sunt adiacente n text clar. Din analiza lor se ncearc descoperirea relaiei matematice responsabil de plasarea literelor n text cifrat. Cu aceeai relaie se verific dac alte litere din text cifrat constituie digrame.

O problem serioas cu care se confrunt acest algoritm de criptare este c, dac criptanalistul descoper relaia dintre un caracter n text clar i poziia sa din text cifrat, aceeai relaie se pstreaz pentru toate caracterele. Complexitatea relaiei o face greu de descoperit, dar un mic rezultat dezvluie ntreaga schem.

1.5 Caracteristicile unui cifru bun

n 1949, Claude Shannon propune urmtoarele caracteristici pentru un cifru bun:

1. Gradul de securitate dorit trebuie s determine cantitatea de munc depus la criptare/decriptare.

Acest principiu este o reiterare a principiului temporal i a observaiei c un cifru simplu poate fi suficient de puternic pentru un interval scurt de timp.

2. Mulimea cheilor sau algoritmul de cifrare trebuie s fie liber de complexitate.

Principiul implic faptul c alegerea cheilor sau a tipurilor de text clar cu care algoritmul va lucra nu trebuie restricionat. De exemplu, un algoritm care poate fi folosit doar pe mesaje care n text clar au un numr egal de A-uri i E-uri sau care necesit chei a cror lungimi sunt numere prime, este prea restrictiv.

3. Implementarea procesului trebuie s fie ct mai simpl.

Principiul 3 este formulat cu gndul la o implementare manual. Odat cu folosirea calculatoarelor, pot fi folosii algoritmi mult mai complicai. Totui complexitatea procesului este important.

4. Erorile n cifrare nu trebuie s se propage i s corup restul informaiei din mesaj.

Acest principiu statuteaz c se pot comite erori la criptare i c efectul acestora trebuie s fie local.

5. Mrimea textului criptat nu trebuie s fie mai mare dect a textului original.

Ideea este c un text criptat de o mrime cu mult mai mare nu poate conine mai mult informaie util dect textul clar, ba chiar poate oferi criptanalistului mai multe indicii. De asemenea, un text cifrat lung implic mai mult spaiu de memorie i crete timpul de comunicare.

Aceste principii au fost formulate nainte ca tehnica de calcul s devin disponibil pe scar larg i anumite aspecte ale implementrii manuale devin fezabile cu calculatorul.

Confuzia i difuzia

Dou concepte suplimentare se leag de cantitatea de munc necesar unei criptri. Un algoritm de criptare trebuie s ia informaia din text clar i s o transforme astfel nct interceptorul s nu poat recunoate mesajul. Interceptorul nu trebuie s poat prezice efectul schimbrii unei litere n text clar asupra textului cifrat. Aceast caracteristic se numete confuzie. Un algoritm care prezint un grad ridicat de confuzie va prezenta o relaie funcional complex ntre perechea text clar/cheie i textul cifrat. De exemplu, cifrul Caesar nu are un grad suficient de ridicat de confuzie, deoarece din descoperirea transformrii a cteva litere, se poate prezice transformarea celorlalte litere, fr informaie suplimentar.

Cifrul trebuie s distribuie informaia din text clar n ntreg textul cifrat. Schimbrile din text clar trebuie s afecteze ct mai multe poriuni din textul cifrat. Acest principiu se numete difuzie, caracteristica distribuirii informaiei de la literele textului clar la textul cifrat n totalitatea sa. O difuzie bun nseamn c interceptorul are nevoie de o cantitate important de text cifrat pentru a descoperi algoritmul. Cifrurile de substituie i permutri nu prezint o bun difuzie, deoarece un caracter din text clar determin doar un singur caracter din text cifrat).

Teste teoretice

Un sistem sigur este acela n care interceptorul nu poate deduce textul clar din textul cifrat, indiferent de cantitatea de criptanaliz desfurat. Securitatea perfect, astfel definit, este greu de obinut. O interpretare mai rezonabil a securitii este sistem suficient de sigur, definit n continuare. Criptanalistul va ncerca s gseasc o transformare h care s converteasc textul cifrat n text clar. Criptograful sper ca transformarea h s nu fie exact, adic s produc mai multe mesaje n text clar posibile. S presupunem c C = E(P) este criptarea i h este posibila transformare de decriptare gsit de criptanalist. Fie h(C) o mulime de posibile mesaje n text clar, h(C)={Pos1, Pos2,...}, care poate conine sau nu adevratul mesaj n text clar, P.

O criptare este efectiv sigur, dac probabilitatea ca h(C) s fie P tinde spre zero, adic:

Prob(h(C)=P)