84

Revista Informatica Economic, nr.3(31)/2004

Classic Cryptography (Pre-computational)

Alin Titus PRCALAB The information (religious, military, economic, etc.) always meant power, therefore the need to protect it, to make it accessible only for elite persons/groups, for initiated persons/group, was debated even from old times. In fact the history of cryptology/cryptographic follows closely the increase and decrease of large empires and civilizations. It doesnt occur and it doesnt develop only where the power is and it must be protected. Keywords: cryptography, substitution cipher, rotor machine. riptografia clasic este criptografia dinaintea calculatorului, de unde i denumirea de criptografie pre-computaional. n criptografia clasic, algoritmii erau bazai pe caracter i constau dintr-o serie de transformri elementare (substituii, transpoziii) ale caracterelor textului n clar. Unii algoritmi aplicau aceste transformri n mod repetat, mbuntind n acest mod securitatea algoritmului. n criptografia modern bazat pe calculator (criptografie computaional), lucrurile s-au complicat, dar multe dintre ideile criptografiei clasice au rmas nemodificate. Criptografia clasic se ncadreaz n clasa criptografiei cu chei simetrice. Cifrul de substituie (substitution cipher) este cifrul bloc la care fiecare caracter sau grup de caractere ale textului n clar (M) este substituit cu un alt caracter sau grup de caractere n textul cifrat (C), descifrarea fcndu-se prin aplicarea substituiei inverse asupra textului cifrat. n criptografia clasic exist patru tipuri de cifruri de substituie. Tabelul 1 - Cifrul lui Cesar
Text clar Text cifrat A D B E C F D G E H F I G J H K I L J M K N L O M P N Q O R P S Q T R U S V T W U X V Y W Z X A Y B Z C

1) Cifruri de substituie monoalfabetic (monoalphabetic ciphers) sunt cifrurile n care fiecare caracter al textului n clar (M) este nlocuit cu un caracter corespondent n textul cifrat (C). Vom aminti cteva dintre cifrurile de substituie cele mai cunoscute: A. Cifrul lui Cesar este un cifru cu substituie monoalfabetic: fiecare liter a textului n clar este nlocuit cu o nou liter obinut printr-o deplasare alfabetic; cheia (aceeai la criptare ct i la decriptare) const n numrul care indic deplasarea alfabetic C = aM + b (mod N) unde a se numete factor de amplificare, iar b coeficient de deplasare. Fcnd corespondena biunivoc ntre literele alfabetului latin (N=26) i echivalentele lor numerice ni{0, 1, 2, ., 25}, cifrul lui Cesar se poate scrie conform tabelului 1: C(ni)= ni +3(mod26)

Exemplu: Celebrul VENI VIDI VICI, devine prin criptare : YHQL YLGL YLFL. Ulterior, cifrul lui Cesar, a fost generalizat prin alegerea n calitate de cheie a oricrei litere din alfabet. B. Cifrul lui Polybius este un cifru substituie. Literele alfabetului latin sunt aezate ntrun ptrat de dimensiune 5x5. Literele I si J sunt combinate pentru a forma un singur ca-

racter, deoarece alegerea final (ntre I si J) poate fi uor decis din contextul mesajului. Rezult 25 de caractere aezate ntr-un ptrat 5x5. Cifrarea oricrui caracter se face alegnd perechea potrivit de numere (intersecia liniei i coloanei) corespunztoare dispunerii caracterului n ptrat.

Revista Informatica Economic, nr.3(31)/2004

85

Ptratul lui Polybius

1 2 3 4 5 1 A F L Q V 2 B G M R W 3 C H N S X 4 D IJ O T Y 5 E K P U Z

n cazul unui atac cu text n clar cunoscut, cifrul se sparge extrem de uor ; atacul cu text cifrat este mai dificil, dar unui calculator i va lua doar cteva secunde pentru a-l sparge. 3) Cifruri de substituie poligramic (polygram substitution ciphers) se obin substituind blocuri de caractere ale alfabetului primar - numite poligrame - cu alte blocuri de caractere, de exemplu: ABA RTQ SLL ABB Utilizri: Cifrul Playfair, inventat in 1854, a fost utilizat n Anglia, n timpul primului rzboi mondial; Codul de compresie Huffman, bazat pe acelai principiu, poate fi utilizat dar este nesigur. 4) Cifruri de substituie polialfabetice sunt formate din mai multe cifruri de substituie simple. Au fost inventate de Leon Battista, in 1568. Dintre acestea vom aminti pe dou dintre cele mai celebre i anume cele ale lui Trithemius i Vigenere. A. Cifrul lui Trithemius este un cifru polialfabetic. Alfabetul este dispus pe 26 de linii numerotate de la 0 la 25, unde numrul de ordine al liniei indic numrul de caractere cu care se deplaseaz ciclic alfabetul spre dreapta. Linia numerotat cu 0 constituie tocmai alfabetul n ordinea iniial. Acest cifru poate fi utilizat astfel: primul caracter se cifreaz selectndu-l din linia 1, al doilea din linia a 2-a i aa mai departe. Exemplu: 1 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 URWNZAQVZFX. B. Cifrul lui Vigenere. Acest cifru utilizeaz cifrul Trithemius i un anumit cuvnt cheie. Cheia dicteaz alegerea liniilor n criptarea i decriptarea fiecrui caracter din mesaj.
12 M I U 14 O T H 13 N T G 0 A I I 12 M M Y 14 O P D 13 N U H 0 A L L

Exemplu: Mesajul: A SOSIT TIMPUL se transform dup cifrare n: 11 3443344244 444223535413. Observaie: Codul poate fi schimbat prin rearanjarea literelor n ptratul 5x5. n sistemele UNIX, programul de criptare ROT 13 este un cifru de substituie monoalfabetic; fiecare liter, n textul cifrat se rotete cu 13 caractere, de unde i denumirea de ROT 13: C= ROT13(M), iar decriptarea se face aplicnd de dou ori ROT 13, dat fiind c alfabetul latin conine N = 26 litere: M = ROT I3(ROTI3(C)). Acest cifru nu este n realitate un cifru de securitate; el se utilizeaz adesea n posturile de utilizatori de reea pentru a ascunde texte potenial ofensive. Concluzie: Cifrurile de substituie monoalfabetic pot fi sparte cu uurin deoarece frecvenele literelor alfabetului nu se schimb n textul cifrat fa de textul n clar. 2) Cifruri de substituie omofonic (homophonic substitution ciphers) sunt cifrurile de substituie n care un caracter al alfabetului mesajului n clar (alfabet primar) poate s aib mai multe reprezentri. Ideea utilizat n aceste cifruri este uniformizarea frecvenelor de apariie a caracterelor alfabetului textului cifrat (alfabet secundar), pentru a ngreuna atacurile criptanalitice. Astfel, litera A - cu cea mai mare frecven de apariie n alfabetul primar - poate fi nlocuit cu F, * sau K. Concluzii: dei mai greu de spart dect cifrurile de substituie simple (monoalfabetice), ele nu mascheaz total proprietile statistice ale mesajului n clar ; Exemplu:
Cuvnt cheie Text n clar Text cifrat 12 M A M 14 O S G 13 N O B 0 A S S

86

Revista Informatica Economic, nr.3(31)/2004

O variant a acestui cifru este cifrul Vigenere cu cheie n clar (cheie de ncercare). Cheia de ncercare indic linia (sau liniile) de nceput pentru primul (sau primele caractere) ale textului n clar ca n exemplul urmtor. Apoi
Cuvnt cheie Text n clar Text cifrat M A M A S S S O G O S G S I A

caracterele textului n clar sunt folosite drept chei pentru alegerea liniilor n criptare. Exemplu: Relum exemplul anterior, dar alegem litera M drept cheie de ncercare. Obinem:
I T B T T M T I B I M U M P B P U J U L F

Observaie: Se remarc introducerea unei reacii n procesul de criptare, textul cifrat fiind condiionat de coninutul mesajului. O alt variant a cifrului Vigenere este cifrul Vigenere cu autocheie (cheie cifrat). Dup
Cuvnt cheie Text n clar Text cifrat M A M M S E E O S S S K

criptarea cu cheie de ncercare, fiecare caracter succesiv al cheii n secven se obine de la caracterul cifrat al mesajului i nu de la textul n clar. Exemplu:
K I S S T L L T E E I M M M Y Y P N N U H H L S

Observaie: Dei fiecare caracter utilizat drept cheie poate fi gsit din caracterul anterior al textului cifrat, el este funcional dependent de toate caracterele anterioare ale mesajului, inclusiv de cheia de ncercare. Urmare a acestui fapt este efectul de difuziune a proprietilor statistice ale textului n clar asupra textului cifrat, ceea ce face ca analizele statistice s devin foarte grele pentru un criptanalist. n baza standardelor actuale, schemele de cifrare Vigenere nu sunt foarte sigure; contribuia important a lui Vigenere const n fapV V V E I I N D C I I I

tul c a descoperit c pot fi generate secvene nerepetitive drept cheie, prin utilizarea a nsui mesajului sau a unor pri ale acestuia. Cifrurile de transpoziie se caracterizeaz prin faptul c textul n clar rmne acelai, doar ordinea caracterelor se schimb. Exemplu: Cifrul simplu cu transpunere n coloane: textul n clar se scrie orizontal ntr-o anumit form, ca la Polybius sau ceva asemntor, iar textul cifrat se citete pe vertical (coloane):
V V E I I N D C I I I

O simpl transpoziie permite pstrarea proprietilor statistice ale textului n clar i textului cifrat; o nou transpoziie a textului cifrat mrete securitatea cifrului. Utilizri: ADFGVX, utilizat de germani n timpul primului rzboi mondial are un cifru substituie combinat cu o alt substituie; dei pentru acea vreme a fost foarte complex, el a fost spart de criptanalistul francez Georges Painvin. Muli algoritmi moderni folosesc transpoziia, dar consumul de memorie este mare comparativ cu substituia, care din acest punct de vedere este mai convenabil. Maini rotor n vederea mecanizrii complicatelor metode de substituie si permutrilor repetate, n anul 1920 au fost inventate o serie de echipamente

mecanice de criptare bazate pe principiul de rotor. 0 main rotor (rotor machine) are o tastatur i o serie de rotoare ce permit implementarea unei versiuni a cifrului Vigenere. Fiecare rotor face o permutare arbitrar a alfabetului, are 26 de poziii i realizeaz o simpl substituie. Deoarece rotoarele se mic cu viteze de rotaie diferite, perioada unei maini cu n rotoare este 26n. Cel mai celebru cifru bazat pe o main rotor este Enigma, utilizat de germani n cel de-al doilea rzboi mondial. El a fost inventat de Arthur Scherbius i Arvid Gerhard Damm n Europa i a fost patentat n SUA. Germanii au mbuntit considerabil proiectul inventatorilor si, dar a fost spart de criptanalitii polonezi care au explicat atacul lor englezilor.

Revista Informatica Economic, nr.3(31)/2004

87

Bibliografie 1) Angheloiu, I., Gyorfi, E., Patriciu, V.V. (1986): Securitatea i protecia informaiei n sistemele electronice de calcul, Ed. Militar, Bucureti 2) Angheloiu, I.(1972): Teoria codurilor, Ed. Militar, Bucureti 3) Borda, M. (1999): Teoria transmiterii informaiei, Dacia, Cluj-Napoca 4) Deavours, C.A., Kahn, D. (1998): Selections from Cryptologia, Artech House 5) Hankerson, D. R., Hoffman, D. G., Leonard, D. A., Lnder, C.(2000): Coding Theory and Cryptographv: The Essentials (Pure and Applied Mathematics, Vol 234), Marcel Dekker, Rev&ex, 2nd edition, Sep. 6) 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. 7) McCurley, K. S., Ziegler, C. D. (1999): Advances in Cryptology, 1981-1997 Elec-

tronic Proceedings and index of the Crypto and Eurocrypt Conferences 1981 -1997 (Lecture Notes in Computer Science), Springer Verlag, Jun. 8) Patriciu V.V. (1998): Securitatea informatic n UNIX si Internet, Ed. Tehnic, Bucureti 9) Patriciu, V.V. (1994): Criptografia i securitatea reelelor de calculatoare, Ed. Tehnic, Bucureti 10) Stallings, W. (1999): Cryptography and Network Security Principles and Practice, Prentice Hall, Second Edition 11) [Link], [Link] Securitatea n informatic i telecomunicaii; Ed. Dacia, Cluj Napoca, 2001 12) V.V. Patriciu, [Link]-Pietroanu Securitatea Comerului Electronic Ed. All, Bucureti, 2001 13) [Link], [Link]-Pietroanu Securitatea n Informatic n UNIX i Internet Ed. Tehnic, Bucureti, 1998