Home >Documents >curs3 cap1-12.pdf

curs3 cap1-12.pdf

Date post:03-Feb-2018
Category:
View:229 times
Download:0 times
Share this document with a friend
Transcript:
  • 7/21/2019 curs3 cap1-12.pdf

    1/177

    Prelegerea 1

    Notiuni de baza ale criptografiei

    1.1 Definitii si notatii preliminare

    Criptografia este o componenta a unui domeniu mult mai larg, numit securitatea informatiei.Obiectivele urmarite de acesta pot fi sumarizate n:

    1. Confidentialitate (privacy): proprietatea de a pastra secretul informatiei, pentru caaceasta sa fie folosita numai de persoanele autorizate.

    2. Integritatea datelor: proprietatea de a evita orice modificare (inserare, stergere,

    substitutie) neautorizata a informatiei.

    3. Autentificare: Proprietatea de a identifica o entitate conform anumitor standarde.Este compusa din

    (a) Autentificarea unei entitati;

    (b) Autentificarea sursei informatiei;

    4. Non - repudierea: Proprietatea care previne negarea unor evenimente anterioare.

    Celelalte obiective legate de securitatea informatiei (autentificarea mesajelor, semnaturi,

    autorizare, validare, controlul accesului, certificare, timestamping, confirmarea receptiei,anonimitate, revocare) pot fi derivate din acestea.

    Definitia 1.1 Criptografia este studiul metodelor matematice legate de securitatea infor-matiei, capabile sa asigure confidentialitatea, autentificarea si non-repudierea mesajelor,precum si integritatea datelor vehiculate ([1].

    Termenul criptografie nseamna scriere secreta1. Domeniul cuprinde atat operatia decriptare (cifrare) a unui text, cat si eventualele ncercari de descifrare si de aflare a cheii

    1Cuvantul este format din cuvintele grecesti cryptos ascuns si grafie scriere

    1

  • 7/21/2019 curs3 cap1-12.pdf

    2/177

    2 PRELEGEREA 1. NOTIUNI DE BAZ A ALE CRIPTOGRAFIEI

    de criptare. In unele lucrari, cadrul general de lucru este numit criptologie, termenul decriptografiedesemnand numai operatia de cifrare si descifrare legala.

    Situatia generala de care se ocupa criptografia este urmatoarea:

    Criptanalist

    Expeditor Destinatar

    Expeditorul (personalizat n majoritatea lucrarilor cu apelativulAlice) doreste sa trimita

    destinatarului (numit Bob) un mesaj printr-un canal de comunicat ie, canal cu un gradridicat de nesiguranta2. Aceasta insecuritate o prezinta un adversar criptanalist (Oscar)care doreste din diverse motive sa cunoasca si eventual sa modifice continutulmesajului, desi acesta nu i este destinat.

    Aceasta confidentialitate solicitata de Alice si Bob se rezolva de obicei prin transfor-marea mesajului n asa fel ncat el sa nu poata fi nteles de nici o persoana care l-ar puteaintercepta. Transformarea respectiva se numeste criptare.

    In general, hackerul Oscarpoate avea doua tipuri de comportament:

    Pasiv: el se multumeste sa intercepteze mesajele si sa le citeasca, folosindu-le n

    scop personal;

    Activ: doreste sa modifice mesajele, sa le schimbe ordinea sau sa introduca propriilesale mesaje, n intentia de a fi acceptat deBob dreptAlice. In acest caz, mesajul vatrebui sa verifice nafara de conditia de confidentialitate si pe cea de autenticitate:Bobtrebuie sa fie sigur ca mesajul primit a fost de la Alice.

    In unele cazuri, problema se poate complica prin faptul c a exista anumite mesaje pecareAliceneaga ca i apartin, desi le-a trimis chiar ea. In acest caz trebuie prevazuteanumite protocoale care sa ntareasca proprietatile de autentificare; proprietati caresa o sileasca pe Alicesa si recunoasca propriile mesaje (non-repudiere).

    In toate aceste scenarii nu exista personaje pozitive sau negative. Orice serviciu decriptare/decriptare are si o sectie de criptanaliza. Se pot da numeroase exemple dinistorie care sa arate rolul pozitiv al lui Oscar n anumite situatii. In general, ntr-untriplet (expeditor, destinatar, criptanalist) nimeni nu are ncredere n nimeni. Variantelestudiate n care Aliceare ncredere n Bobsau invers, sunt mult mai simple si de aceea extrem de rare.

    2Canalul de comunicatie poate suferi si perturbari de ordin fizic: zgomote, stergeri, demodulari etc;

    studiul detectarii si corectarii erorilor de de transmitere a informatiei constituie tema altui domeniu,

    numitTeoria Codurilor.

  • 7/21/2019 curs3 cap1-12.pdf

    3/177

    1.1. DEFINITII SI NOTATII PRELIMINARE 3

    Pentru a ncepe un studiu sistematic al domeniului, sa stabilim ntai terminologiafolosita uzual:

    Un mesaj n forma sa originara este numit text clar. Expeditorul rescrie acest mesajfolosind o metoda cunoscuta numai de el (eventual si de destinatar); spunem ca elcripteaza(sau cifreaza) mesajul, obtinand un text criptat. Destinatarul primeste textul cifrat si ldecripteaza stiind metoda folosita pentru criptare; deciAlice siBob trebuie sa stabileascantr-o etapa preliminara detaliile modalitatii de criptare si de decriptare.

    Algoritmul care realizeaza operatiile descrise se numeste sistem de criptare. Formal,

    Definitia 1.2 Un sistem de criptare este o structura(P, C, K, E, D), unde:

    P= {w | w V} este multimea textelor clare, scrise peste un alfabet nevidV

    (uzualV = {0, 1}).

    C= {w | w W} este multimea textelor criptate, scrise peste un alfabet nevidW (uzualW =V).

    K este o multime de elemente numite chei.

    Fiecare cheie K K determina o metoda de criptare eK E si o metoda dedecriptare dK D. eK : P C si dK : C P sunt functii cu proprietateadK(eK(w)) =w, w P.

    In general se consideraC= {| a P, k K, = eK(a)}.FunctiaeKeste evident injectiva3; daca eKeste bijectiva (si deci dK=e1K), sistemul

    de criptare se numeste simetric.Pentru ca un sistem de criptare sa fie considerat bun, trebuie ndeplinite trei criterii

    (enuntate de Francis Bacon n sec. X V I I ):

    1. Fiind date eK si P, este usor de determinat eK();

    2. Fiind date dK si w C, este usor de determinat dK(w);

    3. este imposibil de determinat din w, fara a cunoaste dK.

    Ultimul criteriu defineste sub o forma vaga ideea de securitate a sistemului.

    La aceste criterii, Bacon adauga si o a patra regula:

    4 Textul criptat trebuie sa fie un text banal, fara suspiciuni.

    Aceasta conditie este utilizata astazi doar de un subdomeniu strict al criptografiei, numitsteganografie.

    In termeni de complexitate, prin usor se ntelege folosirea unui algoritm polinomialde grad mic preferabil algoritm liniar; o problema se considera imposibila daca pentrurezolvarea ei nu se cunosc decat algoritmi de complexitate exponentiala.

    3Conditia de injectivitate nu este obligatorie pentru functia de decriptare dK.

  • 7/21/2019 curs3 cap1-12.pdf

    4/177

    4 PRELEGEREA 1. NOTIUNI DE BAZ A ALE CRIPTOGRAFIEI

    Observatia 1.1 Intreaga disciplina numita criptografie se bazeaza pe o conjectura no-tata prescurtatP= N P 4(pentru detalii a se vedea [5]). P reprezinta clasa problemelorrezolvabile prin algoritmi a caror complexitate este marginita superior de o functie poli-nomiala n lungimea datelor de intrare. Modelul standard de calculabilitate este masinaTuring. N Peste clasa problemelor rezolvabile prin algoritmi nedeterministic polinomiali(care sunt inclusi n algoritmii de complexitate cel putin exponentiala). Evident,P N P ,dar se pare ca problema egalitatii este nedecidabila (n termeni matematici). Oricum,pentru cei interesati, site-ul [4] este dedicat unei informari actualizate permanent a rezul-tatelor si ncerc arilor de rezolvare a acestei probleme.

    Exemplul 1.1 Unul din primele sisteme de criptare cunoscute este sistemul de criptareCezar. Conform istoricului Suetoniu, el a fost folosit de Cezar n corespondenta sa.

    Sa consideram alfabetul latin scris, n ordineA B C D E F G H I J K L M N O P Q R S T U V W X Y Z

    Fiek un numar ntreg din intervalul [0, 25]. El se va numi cheie de criptare. Re-scriem alfabetul latin permutat ciclic, ncepand ns a cu litera avand numarul de ordinek (literaA are numarul de ordine0). Aceasta noua scriere o asezam sub prima scriere,astfel (am presupusk= 2):

    A B C D E F G H I J K L M N O P Q R S T U V W X Y ZC D E F G H I J K L M N O P Q R S T U V W X Y Z A B

    Daca Alice are un text clar pe care vrea sa-l cripteze cu sistemul Cezar, ea va proceda

    astfel:Sa presupunem ca acest text clar este NIMIC NOU. Alice va aseza sub fiecare litera a

    acestui text, litera aflata pe linia a doua din tabelul de sus, astfel:N I M I C N O U

    P K O K E P Q W

    Textul criptat obtinut este PKOKEPQW (din motive suplimentare de securitate,spatiile dintre cuvinte se ignora de obicei).

    La primirea textului, Bob care stie ca este vorba de sistemul de criptare Cezar va proceda astfel: el cunoaste (fiind destinatar legal) cheia de criptare ek. Cheia sa dedecriptare estee26k. Pe baza ei Bob va putea construi cele doua linii ale tabelului, dupa

    care va proceda ca Alice: scrie textul criptat pe prima linie, iar pe a doua linie determinaliterele corespunzatoare, conform tabelului.

    In cazul k = 2, Bob va folosi drept cheie numarul e262 = e24, iar tabelul (litera 24corespunde lui Y) este

    A B C D E F G H I J K L M N O P Q R S T U V W X Y ZY Z A B C D E F G H I J K L M N O P Q R S T U V W X

    LiterelePKOKEPQW determina pe a doua linie textulNIMICNOU.

    4Aceasta este prima din cele cinci probleme ale mileniului, pentru rezolvarea c arora se acorda premii

    de cate un milion dolari.

  • 7/21/2019 curs3 cap1-12.pdf

    5/177

    1.1. DEFINITII SI NOTATII PRELIMINARE 5

    Sa rescriem sistemul Cezar n termenii Definitiei 1.2. Deoarece textele clare si celecriptate folosesc alfabetul latin, vom efectua n prima etapa o operatie de codificare:asociem literelor numere ntregi din intervalul [0, 25]:

    A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25

    In acest fel putem opera matematic pe un inel finit foarte simplu: Z26. Vom aveaP= C= K=Z26. Pentru unK K ales arbitrar,

    eK(m) =m + K(mod26)

    sidK() = K(mod26)

    Definitia 1.3 Procesul de determinare a unei cheiKfolosind un text criptat (asociateventual cu alte informatii auxiliare) se numeste criptanaliza.

    Decidecriptareasicriptanalizaau n final acelasi scop: aflarea textului clar. Diferentaconsta n faptul ca n criptanaliza el trebuie aflat fara a sti cheia de decriptare. Exista o

    regula de aur a creatorilor de sisteme de criptare:Nu subestimati niciodata pe criptanalist.

    care s-a verificat din punct de vedere istoric pentru toate sistemele create pana nprezent: acestea sau au fost sparte sau trebuie sa se revizuiasca periodic pentru a rezistaatacurilor permanente ale intrusilor.

    Sa studiem putin pozitia unui criptanalist (Oscar). Se presupune ntotdeauna ca elare la dispozitie facilitati de calcul excelente, adesea superioare celor de care dispun ceidoi parteneri Alice siBob.

    Mai mult, se poate considera ca Oscarcunoaste sistemul de criptare. S-a constatatca practic acest lucru se ntampla totdeauna. Ce nu cunoaste nsa criptanalistul este

    cheiaK K.Cel mai simplu atac consta n parcurgerea tuturor cheilor posibile si verificarea textuluicriptat, pana se gaseste cheia corecta. Este atacul prinfort a brutasi el reuseste totdeauna,pentru ca exista ntotdeauna o cheie n K, care a folosit la criptare. Deci, n cazul candnumarul cheilor posibile este mic (n Exemplul 1.1 sunt numai 26 chei), aceasta cheie sepoate afla foarte usor dupa un numar finit de ncercari. De aceea sunt folosite obligatoriusisteme de criptare cucard(K) foarte mare. Pentru o cheie care ocupanbiti sunt necesaren general 2n cautari (daca nu exista nici o informatie suplimentara). O extindere alungimii cheii lan + 1 biti dubleaza deci spatiul de cautare. In momentul de fata, tehnicade calcul ofera atacuri prin forta bruta eficiente pentru cheile de lungimi mai mici de 128

  • 7/21/2019 curs3 cap1-12.pdf

    6/177

    6 PRELEGEREA 1. NOTIUNI DE BAZ A ALE CRIPTOGRAFIEI

    biti; asa ca sistemele de criptare actuale folosesc n general chei de 1024 biti sau chiar maimult5.

    In general, un criptanalist este pus n fata urmatoarelor situatii, care i solicita strategiidiverse de urmat:

    1. Stie numai textul criptat w; n acest caz atacurile sunt direct legate de lungimeatextului.

    In sisteme simple cum este Cezar sunt suficiente texte scurte, pentru ca osingura potrivire produce textul - clar. Pentru sistemele mai evoluate, este necesarao lungime mai mare a textului criptat. Metodele de criptanaliza folosesc diverseconjecturi si informatii statistice relative la alfabetul textului - clar, la frecventaaparitiei caracterelor etc.

    2. Stie cel putin o pereche de caractere(text clar, text criptat); din cunoasterea catorvaperechi (x, eK(x)) cu x V criptanalistul va ncearca sa decripteze ntregul textcriptat interceptat.

    Exemplul 1.2 La sistemul de criptare Cezar, o singura pereche(a, eK(a)), dezvaluieimediat cheia si implicit duce la decriptare.

    Exemplul 1.3 Aceasta a fost situatia n care s-a aflat orientalistul francez Cham-

    pollion cand a descifrat hieroglifele,folosind piatra de la Rosetta (vezi [6]).

    3. Criptanalistul cunoaste criptarea unor texte clare selectate de el; esteatacul cu textclar ales, considerat n majoritatea studiilor de criptanaliza. Aceasta situatie esteadesea superioara celei din cazul precedent; sa exemplificam acest lucru.

    Exemplul 1.4 Fie sistemul de criptare Hil l, creat n1929de Lester Hill. Fied 2un numar ntreg fixat. Se definesc

    P= C= (Z26)d, K= {M | M Md(Z26), det(M) = 0}.

    Deci o cheie de criptare este o matriceM patrata nesingulara de dimensiuned, cu

    elemente dinZ26, iarM1 formeaza cheia de decriptare.

    Textul clar w se mparte n blocuri de lungime d : w = 12 . . . n, |i| = d(ultimul bloc se completeaza eventual pana ajunge la lungimead). Textul criptat vafix= 12 . . . n undei=eM(i) =i M(mod26), (1 i n).

    Pentru decriptare se foloseste relatiadM(i) =i M1 (mod26).

    Sa luam de exemplud= 2 si cheiaM=

    3 32 5

    , cu inversaM1 =

    15 1720 9

    .

    5O exceptie o constituie sistemele bazate pe curbe eliptice, datorita aparatului matematic special.

  • 7/21/2019 curs3 cap1-12.pdf

    7/177

    1.1. DEFINITII SI NOTATII PRELIMINARE 7

    Daca textul clar estew= F RAC, vom avea1 = (F R) = (5 17), 2 = (A C) = (0 2)

    Din relatiile

    1 = 1 M(mod26) = (5 17)

    3 32 5

    = (23 22) = (X W)

    2 = 2 M (mod26) = (0 2)

    3 32 5

    = (4 10) = (E K)

    se obtine textul criptatx= XWEK.

    Sa ne situam acum pe pozitia lui Oscar: presupunem ca am gasit dimensiunead = 2

    si ncerc am sa aflam matricea M (sau echivalent M1), stiind perechea (textclar, text criptat)=(FRAC, XWEG).

    Deci Oscar se afla acum n fata urmatoarei probleme: care este matricea M = a bc d

    cua, b, c, d {0, 1, . . . , 25}, astfel ca

    5 170 2

    a bc d

    =

    23 22

    4 10

    .

    Pentru a putea afla aceasta matrice, Oscar trebuie sa afle inversa luiA=

    5 170 2

    .

    Cumdet(A) = 10 sicmmdc(10, 26) > 1 = 101 (mod26) nu exista; deciA nueste inversabila.

    Sa presupunem acum ca Oscar lucreaza n ipoteza(3); alege un text clar a carui ma-trice este inversabila si i afl a criptarea. FieBRAD acest text clar, a carui matrice

    asociata esteA=

    1 170 3

    . Oscar solicita criptarea luiBRADsi primesteLKGP

    de matriceB=

    11 10

    6 15

    . Deci el dispune de perechea(BRAD, LKGP).

    Oscar detemina nt aiA1 =

    1 30 9

    . Apoi, din ecuatiaA M=B, va gasi solutia

    M=A1 B = 1 3

    0 9

    11 10

    6 15 =

    3 3

    2 5

    4. Stie cheia de criptare; acumOscarva cunoaste cheiaeK si ncearca sa determinedKnainte de interceptarea mesajelor criptate.

    Aceasta este situatia tipica sistemelor de criptare cu cheie publica: cheia de criptareeK este cunoscuta public cu mult nainte de a fi folosita pentru criptare. Decicriptanalistul are la dispozitie destul de mult timp pentru prelucrarea ei si oriceclarificare n perioada cand timpul este ieftin are o valoare deosebita; dupa ce seprimesc mesaje criptate, timpul devine scump, si el trebuie sa fie scurtat cat maimult.

  • 7/21/2019 curs3 cap1-12.pdf

    8/177

    8 PRELEGEREA 1. NOTIUNI DE BAZ A ALE CRIPTOGRAFIEI

    1.2 Sisteme simetrice de criptare

    In general, sistemele de criptare clasice se numesc sisisteme simetrice. Motivul este acelaca odata cu aflarea cheii de criptare eK, cheia de decriptare dK se obtine imediat, fiindfunctia inversa.

    Exemplul 1.5 In Exemplul 1.1, la sistemul CezardK = e26Keste cheia de decriptarepentru cheia de criptareeK.

    Sistemele de criptare simetrice se mpart n doua clase mari: cifruri de permutaresicifruricu substitutie.

    1.2.1 Cifruri de permutare

    La aceste sisteme de criptare, textul clar se mparte n blocuri de n (n 2) caractere,dupa care fiecarui bloc i se aplica o permutare fixata.

    Exemplul 1.6 Sa presupunem ca vom lua drept cheie de criptare permutarea

    1 2 32 1 3

    .

    Atunci un text clar, de exemplu FLOARE ALBASTRA se mparte n grupuri de cate treicaractere (s-a considerat si caracterul spatiu, notat )

    FLO ARE AL BAS TRATextul criptat va fi

    LFO RAE A L ABS RTAsau eliminand gruparile, LFORAEA LABSRTA.

    Exemplul 1.7 Un sistem celebru de criptare cu permut ari este sistemul Richelieu, prezen-tat si n literatur a de Jules Verne, n romanul Mathias Sandorf. Dam un exemplu deutilizare a unui astfel de sistem.

    Fie cartonul6 6, n care zonele hasurate constituie gauri.

    Vrem sa criptam textulEMINESCU A FOST UN MARE POET NATIONAL

    Vom scrie acest text sub forma unui tabel cu sase linii si sase coloane, astfel:

  • 7/21/2019 curs3 cap1-12.pdf

    9/177

    1.2. SISTEME SIMETRICE DE CRIPTARE 9

    E M I N E S C U A F O S T U N

    M A R E P O E T N AT I O N A L

    Aplicand cartonul peste acest text, vor ramane vizibile9 caractere: MNS TA AN (cititede la stanga la dreapta si de sus n jos).

    Vom roti acum cartonul cu90o n sensul acelor de ceasornic. El va arata

    Asez and acum peste text, raman vizibile caracterele F MPTNIL (primul caracter a fostun spatiu si l-am marcat cu pentru a-l face vizibil).

    La a treia rotire a cartonului se obtine similar textul ICSUEETOA, iar la a patra EEUAOURO

    Deci textul criptat esteMNS TA AN F MPTNILICSUEETOAEEUAOURO

    Operatia de decriptare se realizeaza similar.

    Sa formalizam aceste informatii.

    Definitia 1.4 Fie n un numar natural nenul. Un cifru de permutare este un sistem(P, C, K, E, D) undeP= C= (Z26)

    n, K=Pn (multimea permutarilor den elemente).Pentru o cheie (permutare)

    e(a1a2 . . . an) =a(1)a(2) . . . a(n)

    d(b1b2 . . . bn) =b1(1)b1(2) . . . b1(n)

    Lema 1.1 Un cifru de permutare este un sistem de criptare Hill.

    Demonstratie: Pentru fiecare permutare Pn putem construi o matrice de permutareM = (mi,j) definita

    mi,j = 1 i= (j)

    Se verifica usor faptul ca sistemul de criptare Hill cu matricea M este echivalent cu uncifru de permutare bazat pe cheia . Mai mult, M1 =M1 .

  • 7/21/2019 curs3 cap1-12.pdf

    10/177

    10 PRELEGEREA 1. NOTIUNI DE BAZ A ALE CRIPTOGRAFIEI

    Exemplul 1.8 Sa reluam Exemplul 1.6. Permutarii 1 2 32 1 3

    i corespunde matriceade permutare

    0 1 01 0 0

    0 0 1

    .

    Operatia de criptare este imediata. De exemplu, criptarea textuluiF LO este

    (5 11 14)

    0 1 01 0 0

    0 0 1

    = (11 5 14)

    adicaLF O.

    1.3 Exercitii

    1.1 Textul clar NUMAR este criptat n Orice vant nu bate seara. Sa se descrie sistemulde criptare.

    1.2 Folosind atacul prin fort a bruta, decriptati mesajul WYPTBSJBYZ criptat cu unsistem Cezar.

    1.3 O cheieKeste auto-cheie dacadK = eK. Gasiti toate auto-cheile sistemului de

    criptare Cezar.

    1.4 Fiep un numar prim. Aratati ca numarul matricilor2 2 inversabile pesteZp este(p2 1)(p2 p).

    1.5 Cate matrici2 2 sunt inversabile pesteZn pentrun= 6, 9, 26 ?

    1.6 Sa se cripteze textul clar INAINTE SI LA DREAPTA folosind sistemul de xriptareHill cu matricea

    M= 17 17 521 18 21

    2 2 19

    sau M= 11 2 19

    5 23 2520 7 1

    1.7 Cate auto-chei sunt ntr-un sistem de criptare Hill cud= 2 ?

    1.8 Determinati inversele matricilor (modulo 26):

    2 59 5

    ,

    11 8

    3 7

    ,

    10 5 123 14 21

    8 9 11

    ,

    1 11 124 23 2

    17 15 9

  • 7/21/2019 curs3 cap1-12.pdf

    11/177

    1.3. EXERCITII 11

    1.9 Demonstrati ca ntr-un cifru de permutare, este o auto-cheie daca si numai daca

    (i, j) [(i) =j = (j) =i]

    Gasiti toate auto-cheile unui cifru de permutare cun= 2, 3, 4, 5, 6.

    1.10 Consideram urmatorul cifru de permutare: Se fixeaza numerele naturalep, q. Tex-tul clar se mparte n blocuri de catep qcaractere. Fiecare astfel de bloc se scrie pe liniileunei matrici deplinii siqcoloane. Criptarea blocului se realizeaza scriind aceste matricipe coloane.

    De exemplu, pentrup= 3, q= 4, textul clar MAINI CURATE se scrie

    M A I N

    I C U RA T E X (textul s-a completat cu literaX). Textul criptat va fi MIAACTIUENRX.

    Decriptati urmatorul text DJNOUDNAINPAPANONZ criptat ntr-un mod similar.

    1.11 Sa se decripteze mesajulN T I N I I I D D N R I R T E E A D U M I I G R A D V O B E M C I I I E Z S R U A U C M L T A I T U I T N I D A A L E A R A C R I A S Z T E E E I G P S A D E A P R E Z S T C A O

    A E R I D R E D D E I E S E E P E Lstiind c a a fost criptat cu matricea Richelieu definita n Exemplul 1.7.

  • 7/21/2019 curs3 cap1-12.pdf

    12/177

    12 PRELEGEREA 1. NOTIUNI DE BAZ A ALE CRIPTOGRAFIEI

  • 7/21/2019 curs3 cap1-12.pdf

    13/177

    Bibliografie

    [1] A. Menezes, P. Oorschot, S. Vanstome,Handbook of Applied Cryptography

    [2] D. Stinton,Cryptography, Theory and Practice, Chapman & Hall/CRC, 2002

    [3] A. Salomaa, Criptografie cu chei publice, Ed. Militara, 1996

    [4] http://www.win.tue.nl/ gwoegi/P-versus-NP.htm

    [5] S. Cook,http: //www.claymath.org/millennium/P vs NP/Official Problem Description.pdf

    [6] http://en.wikipedia.org/wiki/Rosetta stone

    13

  • 7/21/2019 curs3 cap1-12.pdf

    14/177

    Prelegerea 2

    Cifruri de substitutie

    Cifrurile de substitutie sunt cele mai utilizate sisteme de criptare simetrice; ele se ntalnescsi azi, exemple fiind sistemele DES si AES.

    Un astfel de cifru consta n nlocuirea fiecarui caracter dinVcu alt caracter (din W).Exista doua clase mari de cifruri de substitutie: sisteme monoalfabetice si polialfabetice.

    2.1 Sisteme de criptare monoalfabetice

    Un astfel de sistem substituie fiecare caracter cu alt caracter totdeauna acelasi, indiferent

    de pozitie. Atunci cand cele doua alfabete coincid (V = W), sistemele monoalfabeticesunt cazuri particulare de cifruri de permutare.

    Vom trece n revista cateva astfel de sisteme.

    2.1.1 Sistemul de criptare Cezar

    Sistemul de criptare Cezar este un sistem monoalfabetic: odata stabilita cheia de criptareeK, fiecare caracter cod x se nlocuieste prin caracterul cod x+k (mod 26) (a se vedeaPrelegerea I). Decriptarea se realizeaza dupa formula dK(x) =x k (mod26).

    Observatia 2.1 In cartea sa De bello gallico, Cezar aminteste de un sistem de criptare,

    fara sa dea detalii. Mai tarziu, Suetoniu n Viata lui Iuliu Cezar descrie sistemul.Cezar folosea sistemul nlocuind literele romane cu cele grecesti si folosea deplasareak = 3.Nepotul lui Cezar, mparatul Augustus a utlizat acelasi sistem, cuk = 1. Sistemul Cezara fost utilizat mult timp. Armata rusa apela frecvent la el n 1915, ca nlocuitor pentrusistemele sale proprii de criptare, prea sofisticate la nivelul trupelor de camp. Un sistemCezar cuk= 13 este inclus nROT13, implementat pe sistemele UNIX ([5],[3])

    Evident, Cezar este un sistem generat de permutarile ciclice din P26. Fiind numai 26 cheiposibile, el este extrem de vulnerabil la atacul prin forta bruta. Pentru a-i mari rezistenta,s-a utilizat si o varianta, numita sistem Cezar cu cheie, definita astfel:

    1

  • 7/21/2019 curs3 cap1-12.pdf

    15/177

    2 PRELEGEREA 2. CIFRURI DE SUBSTITUTIE

    Se considera un cuvant (cheie), preferabil cu toate caracterele distincte (n caz contrar,literele identice se folosesc doar la prima aparitie). Acest cuvant se aseaza la nceputul al-fabetului. Dupa ce se termina, sirul de completeaza cu literele care nu existau n cuvantulcheie, n ordine alfabetica.

    De exemplu, sa presupunem ca s-a ales cuvantul cheie M ARTOR. Scriem

    A B C D E F G H I J K L M N O P Q R S T U V W X Y ZM A R T O B C D E F G H I J K L N P Q S U V W X Y Z

    Pentru textul clar se vor folosi caracterele de pe primul r and, iar pentru criptare caracterele corespondente de pe randul al doilea. Astfel, STUDENT se cripteaza nQSUTOJS, ARGINT n MPCEJS etc.

    Sistemul Cezar cu cheie rezista mai bine la atacul cu forta bruta, numarul cheilor fiind

    acum card(P26= 26!.

    2.1.2 Sistemul de criptare afin

    Sistemul de criptare afin este o generalizare a sistemului Cezar. Vom aveaP=C= Z26,K={(a, b)| a, b Z26, cmmdc(a, 26) = 1}, iar functiile de criptare si decriptare (pentruo cheie K= (a, b)) sunt

    eK(x) =ax + b(mod26), dK(y) =a1y+ a1(26 b) (mod26)

    Conditia ca a sa fie prim cu 26 asigura existenta lui a1 n Z26.

    De exemplu, pentru a= 3, b= 5 functia de criptare este eK(x) = 3x+ 5, care poatefi reprezentata prin tabelul:

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 255 8 11 14 17 20 23 0 3 6 9 12 15 18 21 24 1 4 7 10 13 16 19 22 25 2

    sau scris direct pentru caractere

    A B C D E F G H I J K L M N O P Q R S T U V W X Y ZF I L O R U X A D G J M P S V Y B E H K N Q T W Z C

    Astfel, textul clar PRIMAVARA TARZIE se cripteaza n YEDPFQFEF KDECDR.Deoarece 31 = 9 (mod 26), decriptarea se realizeaza matematic folosind functia

    dK(x) = 9x + 7 (sau practic inversand cele doua linii ale tabelului de mai sus).Conditiacmmdc(a, 26) = 1 asigura de asemenea injectivitatea aplicatiei e

    K.

    De exemplu, pentru eK(x) = 10x + 1, A siNse transforma ambele n B, iar O nu apareca imagine n alfabetul substitutiei.

    Sa studiem spatiul cheilorK. Orice cheie K K este determinata complet de valorilentregi (a, b) cu (a, 26) = 1. Sunt posibile 12 valori1 pentrua : 1, 3, 5, 7, 9, 11, 15, 19, 21, 23,25. Pentru b sunt posibile 26 valori, care se iau independent de a, cu singura exceptiea= 1, b= 0 (care se exclude deoarece nu conduce la nici o criptare). Deci card(K) = 311,numar suficient de mic pentru reusita unui atac prin forta bruta.

    1Pentru un numar dat n exista (n) numere mai mici decat n si prime cu n, unde phi este functiaEuler. In particular (26) = 12.

  • 7/21/2019 curs3 cap1-12.pdf

    16/177

    2.1. SISTEME DE CRIPTARE MONOALFABETICE 3

    2.1.3 Alte sisteme de criptare monoalfabetice

    Sistemul de criptare Polybios

    Sistemul Cezar nu este cel mai vechi de criptare. Se pare c a primul astfel de sistem a fostPolybios (istoric grec mort cu 30 ani naintea nasterii lui Cezar). Initial acesta a fost doarun sistem maritim de semnalizare cu torte; ulterior i s-a dat o semnificatie criptografica.

    Sa consideram alfabetul latin, din care eliminam o litera de frecventa cat mai redusa2;fie aceastaW. Cele 25 litere ramase le asezam ntr-un patrat 5 5 (numit careu Polybios)n felul urmator:

    A B C D E A A B C D E B F G H I J C K L M N OD P Q R S T E U V X Y Z

    In operatia de criptare, fiecare caracter a va fi reprezentat printr-o pereche (x, y) (x, y{A,B,C,D,E}) care dau linia respectiv coloana pe care se afla a.

    Astfel, textul clar MERGEM ACASA este criptat nCCAEDCBBAECCAAACAADDAA.

    Deci sistemul de criptare Polybios este o substitutie monoalfabetica cu alfabetulW =

    {AA,AB,AC,.. . ,EE} de 25 caractere.Sunt diverse variante ale sistemului Polybios. Astfel, daca se folosesc drept coordonate

    cifrele 1, 2, 3, 4, 5 n loc de A,B,C,D,E, sistemul a fost folosit n penitenciarele rusesti3

    si de catre prizonierii americani din Vietnam. Este foarte simplu de nvatat si poate fiaplicat folosind diverse semne drept coordonate (cifre, puncte, figuri, batai de toba etc).A fost utilizat de asemenea n cadrul altor sisteme de criptare, cum ar fi sistemul nihilist,cifrul ADFGVX (utilizat de armata germana n primul razboi mondial) sau sistemul Bifid,inventat de Dellastell n 1901 (pentru detalii, se vedea [6]).

    Sistemul cavalerilor de Malta

    Ordinul cavalerilor de Malta folosea un sistem de criptare monoalfabetic bazat pe stilizareaunei cruci. Astfel, sa consideram careurile:

    A: B: C :D: E : F :G: H : I :

    J. K. L.M. N. O.P. Q. R.

    S T UV W XY Z

    2In limba engleza litera eliminata este de obicei J.3Alfabetul cirilic are 33 litere, deci n acest caz s-a utilizat un careu 6 6.

  • 7/21/2019 curs3 cap1-12.pdf

    17/177

    4 PRELEGEREA 2. CIFRURI DE SUBSTITUTIE

    Liniile care ncadreaza fiecare caracter (inclusiv spatiul), mpreuna cu punctele (doua, unulsau zero) indica substitutia caracterului respectiv. Astfel, textul clar DUPA DOUAZECIDE ANI se cripteaza n

    : . : : . : : : : : : : . :

    2.1.4 Criptanaliza sistemelor de criptare monoalfabetice

    Punctul slab al sistemelor de criptare monoalfabetice consta n frecventa de aparitie acaracterelor n text. Daca un text criptat este suficient de lung si se cunoaste limba

    n care este scris textul clar, sistemul poate fi spart printr-un atac bazat pe frecventaaparitiei literelor ntr-o limba.

    Sunt construite diverse structuri de ordine relative la frecventa aparitiei literelor nfiecare limba europeana. De obicei, cu cat un text criptat este mai lung, cu atat frecventaliterelor folosite se apropie de aceasta ordonare generala. O comparare ntre cele douarelatii de ordine (cea a caracterelor din textul criptat si cea a lterelor din alfabetul limbiicurente) conduce la realizarea catorva corespondente (litera text clar litera text criptat),ceea ce stabileste n mod univoc cheia de criptare. Pentru sistemul Cezar este suficientastabilirea unei singure perechi; pentru sistemul afin trebuiesc doua perechi etc.

    Pentru limba romana, un tabel al literelor cele mai frecvent ntalnite este

    Litera FrecventaA 13, 04 %I 12, 89 %E 11, 75 %R 7, 39 %T 6, 62 %N 6, 44 %U 6, 44 %S 5, 50 %C 5, 47 %

    Litera FrecventaL 4, 58 %O 3, 85 %D 3, 68 %M 3, 33 %P 2, 91 %F 1, 50 %V 1, 26%

    (restul caracterelor au o n mod normal o frecventa de aparitie sub 1 %).

    Exemplul 2.1 Sa consideram ca s-a interceptat urmatorul text, criptat cu un sistemmonoalfabetic (nu se stie exact ce sistem a fost utilizat).

    lqakc sp gcxk aca pcmgqb kq kxc pkersmpqsb vk vsmgxkbc mkacpc tcacpbqlqs

    vk cgele cmtxq ms nocxgsb mbxcsp vk exsgk oxcbqsbcbk texbslk spclbk gcxk

    cmgqpvkcq bxkgcbexslk gqxbslk xktxknkpbcq tkpbxq mbxcsps qp cfkxbsmakpb

    mqtcxcbex vcx lsatkvk pq bxkrqscq mc zsk txkc gqxsems psgs mc mk cmbktbk

    mc czlk acxk lqgxq vk lc gkl gq gcxk fkpkcq sp gepbcgb

  • 7/21/2019 curs3 cap1-12.pdf

    18/177

    2.1. SISTEME DE CRIPTARE MONOALFABETICE 5

    In prima etapa, vom numara de cate ori apare n text fiecare caracter. se obtine tabelul

    Caracter c k x b s q g p m l e p a v b n o f z

    Frecvent a 39 38 27 25 23 20 19 18 18 11 9 8 7 7 2 2 2 2 2

    Deci caracterele cele mai frecvente sunt c si k. Pe de-alta parte, cele mai frecventecaractere din limba romana sunt a, i sie (textul nu este destul de mare pentru a puteaface o distinctie neta). In mod cert, a {c, k}. Sunt patru optiuni posibile, din care treise elimina rapid. Ramane de abordatca, ke.

    Vom nota cu litere mari caracterele din textul clar; prin nlocuirea luic cuA, a luikcuE, textul devine

    lqaEA sp gAxE aAa pAmgqb Eq ExA pEersmpqsb vE vsmgxEbA mEaApA tAaApbqlqs

    vE Agele Amtxq ms noAxgsb mbxAsp vE exsgE oxAbqsbAbE texbslE spAlbE gAxE

    AmgqpvEAq bxEgAbexslk gqxbslE xEtxEnEpbAq tEpbxq mbxAsps qp AfExbsmaEpb

    mqtAxAbex vAx lsatEvE pq bxErqsAq mA zsE txEA gqxsems psgs mA mE AmbEtbE

    mA AzlE aAxE lqgxq vE lA gEs gq gAxE fEpEAq sp gepbAgb

    CuvantulExA de pe primul rand are caracterul din mijloc (x) de frecvent a ridicata (27aparitii); deci el trebuie sa corespunda unei litere frecvente din limba romana si n plus sa aiba semnificatie semantica. Concluzie: acest cuvant este ERA. DecixR. Facemsubstitutia s se obtine textul

    lqaEA sp gARE aAa pAmgqb Eq ERA pEersmpqsb vE vsmgREbA mEaApA tAaApbqlqsvE Agele AmtRq ms noARgsb mbRAsp vE eRsgE oRAbqsbAbE teRbslE spAlbE gARE

    AmgqpvEAq bREgAbeRsleR gqRbslE REtREnEpbAq tEpbRq mbRAsps qp AfERbsmaEpb

    mqtARAbeR vAR lsatEvE pq bRErqsAq mA zsE tREA gqRsems psgs mA mE AmbEtbE

    mA AzlE aARE lqgRq vE lA gEs gq gARE fEpEAq sp gepbAgb

    In acest text, cuvantul REtREnEpbAq are corespondent n limba romana numai peREPREZENTA{I , M , U }. De aici se obtin decriptarile tP, nZ, pN sibT (pentru ultimul caracter - q, nu facem deocamdata nici o optiune). Noul text vafi

    lqaEA sp gARE aAa NAmgqT Eq ERA NEersmNqsT vE vsmgRETA mEaANA PAaANTqlqs

    vE Agele AmPRq ms ZoARgsT mTRAsN vE eRsgE oRATqsTATE PeRTslE sNAlTE gARE

    AmgqNvEAq TREgATeRsleR gqRTslE REPREZENTAq PENTRq mTRAsNs qN AfERTsmaENT

    mqPARATeR vAR lsaPEvE Nq bRErqsAq mA zsE PREA gqRsems Nsgs mA mE AmTEPTE

    mA AzlE aARE lqgRq vE lA gEs gq gARE fENEAq sN geNTAgT

    Lucrurile ncep acum sa se simplifice: PENTRq este corect numai pentru q U,AmTEPTE pentrumS. Apoi NASgUT dag C, SUPARATeR dae O,iar dinfEN EAU deducemfV. Facand aceste nlcuiri, se obtine textul

  • 7/21/2019 curs3 cap1-12.pdf

    19/177

    6 PRELEGEREA 2. CIFRURI DE SUBSTITUTIE

    lUaEA sp CARE MAM NASCUT EU ERA NEOrsSNUsT DE vsSCRETA SEaANA PAaANTUlUs

    DE ACOlO ASPRU Ss ZoARCsT STRAsN vE ORsCE oRATUsTATE PORTslE sNAlTE CARE

    ASCUNvEAU TRECATORslOR CURTslE REPREZENTAU PENTRU STRAsNs UN AfERTsSaENT

    SUPARATOR vAR lsaPEvE NU bRErqsAU SA zsE PREA CURsOms NsCs SA SE ASTEPTE

    mA AzlE aARE lUCRU vE lA CEs CU CARE VENEAU sN CONTACT

    Ultimele caractere se deduc imediat: l L, a M, r B, s I, v D.Textul clar final este:

    LUMEA IN CARE MAM NASCUT EU ERA NEOBISNUIT DE DISCRETA SEMANA PAMANTULUI

    DE ACOLO ASPRU SI ZGARCIT STRAIN DE ORICE GRATUITATE PORTILE INALTE CARE

    ASCUNDEAU TRECATORILOR CURTILE REPREZENTAU PENTRU STRAINI UN AVERTISMENT

    SUPARATOR DAR LIMPEDE NU TREBUIAU SA FIE PREA CURIOSI NICI SA SE ASTEPTE

    SA AFLE MARE lUCRU DE LA CEI CU CARE VENEAU IN CONTACT

    (textul provine din romanul Viata ca o corida de Octavian Paler).

    Evident, daca se stia sistemul de criptare (afin, Cezar etc) criptanaliza se simplificamult.

    Pentru alte aplicatii, oferim tabelele de frecventa a literelor pentru principalele limbi

    europene4 (am retinut din fiecare limba numai cele mai frecvente noua litere):

    Engleza FrecventaE 12, 31 %T 9, 59 %A 8, 05 %O 7, 94 %N 7, 19 %I 7, 18 %

    S 6, 59 %R 6, 03 %H 5, 14 %

    Germana FrecventaE 18, 46 %N 11, 42 %I 8, 02 %R 7, 14 %S 7, 04 %A 5, 38 %

    T 5, 22%U 5, 01%D 4, 94%

    Franceza FrecventaE 15, 87 %A 9, 42 %I 8, 41 %S 7, 90 %T 7, 26 %N 7, 15 %

    R 6, 46 %U 6, 24 %L 5, 34 %

    Spaniola FrecventaE 13, 15 %A 12, 69 %O 9, 49 %S 7, 60 %N 6, 95 %R 6, 25 %

    I 6, 25 %L 5, 94 %D 5, 58 %

    Exista o situatie ipotetica n care criptanaliza unui sistem monoalfabetic este imposibila:atunci cand P=V si nu dispunem de nici o alta informatie (decat eventual sistemul decriptare). Acest caz corespunde nsa unei codificari; adevarata criptare a avut loc atuncicand mesajele inteligibile au fost translatate n cuvinte dinV.

    4Datele statistice pentru toate tabelele inclusiv limba romana sunt din anul 1994.

  • 7/21/2019 curs3 cap1-12.pdf

    20/177

    2.2. SISTEME DE CRIPTARE POLIALFABETICE 7

    2.2 Sisteme de criptare polialfabetice

    Diferenta dintre aceste sisteme de criptare si cele monoalfabetice consta n faptul casubstitutia unui caracter variaza n text, n functie de diversi parametri (pozitie, contextetc.). Aceasta conduce binenteles la un numar mult mai mare de chei posibile. Seconsidera ca primul sistem de criptare polialfabetic a fost creat de Leon Battista n 1568([3]). Unele aplicatii actuale folosesc nca pentru anumite sectiuni asyfel de sisteme decriptare.

    2.2.1 Sistemul homofonic

    Sistemul de criptare homofonic este un sistem intermediar ntre sistemele mono si celepolialfabetice. Principalul lui scop este de a evita atacul prin frecventa de aparitie acaracterelor. Se pare ca a fost utilizat prima oara n 1401 de catre ducele de Mantua.

    Fiecarui caracter a Pi se asociaza o multime H(a) Castfel ncat:

    1. H(a) H(b) = a=b;

    2. Daca aapare mai frecvent n textele clare, atunci card((H(a)) card(H(b)).

    Criptarea unui caracter a P se face cu un element ales aleator din H(a). Pentrudecriptarea lui y Cse cauta o multime H(a) astfel ca y H(a).

    Exemplul 2.2 Sa consideramP={a, b} siH(a) ={001, 010}, H(b) ={000, 011, 101,111}. Pentru criptarea textuluiab se poate folosi oricare din secventele

    001000, 001011, 001101, 001111, 010000, 010011, 010101, 010111.

    Sistemul homofonic este mult mai rezistent la un atac doar pe baza textului criptat, darcedeaza usor la un atac cu text clar ales.

    2.2.2 Sistemul de criptare Playfair

    Sistemul a fost inventat 1854 de Sir Charles Wheatstone. Cel care l promoveaza si lsustine pentru a fi adoptat ca cifru oficial al Marii Britanii este baronul Lyon Palyfayr deSt. Andrews. Guvernul prefera alta varianta, dar acest sistem de criptare capata numelebaronului.

    Ideea de baza este urmatoarea:

    Din cele 26 litere ale alfabetului se elimina una de frecventa minima; sa spunem Q.Restul literelor se aranjeaza arbitrar sub forma unui patrat 55. Sa exemplificam sistemulpentru tabloul

  • 7/21/2019 curs3 cap1-12.pdf

    21/177

    8 PRELEGEREA 2. CIFRURI DE SUBSTITUTIE

    S Y D W ZR I P U LH C A X FT N O G EB K M J V

    Acest tabel va forma atat cheia de criptare cat si cea de decriptare.Regulile de criptare/de-criptare sunt:

    Textul clar este separat n blocuri de cate doua caractere (ignorand spatiile). Condi-tia este ca nici un bloc sa nu contina aceiasi litera, iar textul sa fie de lungime para.Aceste deziderate se realizeaza usor modificand putin textul clar (se introduce olitera de frecventa mica ntre cele doua litere egale, respectiv ca ultim caracter).

    Fiecare bloc se cripteaza astfel: daca cele doua litere nu sunt plasate n tabel peaceiasi linie sau coloana (de exempluA siE), se cerceteaza colturile dreptunghiuluideterminat de cele doua litere (n cazul nostru A, F, O, E). Perechea AEeste crip-tata n F O. Ordinea este determinata de ordinea liniilor pe care se afla literele dintextul clar. Astfel,EA se cripteaza n OF,SF n ZB etc.

    Daca cele doua litere se gasesc pe aceasi linie (coloana), se merge ciclic cu o pozit iela dreapta (respectiv jos). Deci CA se cripteaza n AX, W X n U G, CA n AXetc.

    De exemplu, textul clar AFARA PLOUA se cripteaza n XHHPPDPEPX. Se observa cacele patru aparitii ale caracterului A au fost criptate cu X, H, P si din nou X.

    O permutare ciclica a liniilor si coloanelor tabloului nu modifica criptarea. De exemplu,patratul

    P U L R IA X F H CO G E T NM J V B KD W Z S Y

    obtinut prin deplasarea cu doua pozitii spre stanga si o pozitie n sus, este echivalent cucel initial (ambele asigura aceeasi cheie de criptare).

    Regulile de baza pot fi modificate sau completate dupa necesitati. Astfel, se poateadauga din loc n loc cate o litera falsa (cu frecventa foarte redusa, cum ar fi X, Y) caresa modifice textul criptat. Patratul 5 5 poate fi nlocuit cu un dreptunghi 4 6 sau3 8, cu schimbarile corespunzatoare n alegerea literelor care se elimina.

    Pentru a pastra cheia n siguranta, se recomanda memorarea acesteia. Cum o astfelde cheie este extrem de greu de memorat, se foloseste un cuvant cheie sau o propozitie cutoate literele distincte. Acesta cuvant este scris la nceputul tabloului. Spatiile ramasesunt completate cu restul literelor alfabetului, scrise n ordinea aparitiei lor5.

    5In definitia initiala a sistemului, Wheatstone pleca de la cuvantul Holmes.

  • 7/21/2019 curs3 cap1-12.pdf

    22/177

    2.2. SISTEME DE CRIPTARE POLIALFABETICE 9

    Astfel, n preajma primului razboi mondial, armata romana folosea un dreptunghi3 8 din care lipseau literele Q si K. Cuvantul cheie era ROMANESC. Un astfel detablou putea avea de exemplu forma

    R O M A N E S CB D F G H I J LP T U V W X Y Z

    Ca si sistemul anterior, Palyfair rezista la atacuri bazate pe frecventa aparitiei, darnu si la cele prin text clar ales.

    Implementari actuale folosesc reprezentarea binara a literelor si fac un pas suplimentar:dupa ce s-a obtinut o pereche criptata, aceasta se combina printr-un XOR (adunare

    modulo 2) cu perechea criptata anterior.

    2.2.3 Sistemul de criptare Vigenere

    Numele sistemului6 vine de la baronul francez Blaise de Vigenere (1523 1596) diplomatla curtea regelui Henry III. A fost considerat mult timp unul din cele mai bune sistemede criptare.

    Prezentarea sistemului

    Consideram ca si la sistemele anterioare cele 26 litere ale alfabetului, numerotate dela 0 (pentru A) pana la 25 (pentru Z), conform tabelului:

    A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25

    Definim P=C=Z26, K=Z+26.

    O cheie K K este un cuvant avand codificarea numerica k0k1 . . . kp1.Fie a= a0a1 . . . an codificarea textului clar care trebuie transmis. Textul criptat va fi

    eK

    (a) =x = x0x

    1. . . x

    n, unde

    xi=ai+ ki(mod p) (mod26) ()

    Exemplul 2.3 Sa consideram cuvantul cheieFOCAR; decip= 5 siK= 5 14 2 0 17.Daca vrem sa criptam cu aceasta cheie textul clar NU POT VENI AZI, vom proceda

    astfel:Codificarea textului estea= 13 20 15 14 19 21 4 13 8 0 25 8.Sub fiecare numar din a se aseaz a cate un numar dinK; cand cheia se termina, ea

    se reia ciclic, pana se terminaa. Deci vom avea

    6Sursa [7] indica drept real inventator al sistemului pe Giovan Batista Belaso n 1553.

  • 7/21/2019 curs3 cap1-12.pdf

    23/177

    10 PRELEGEREA 2. CIFRURI DE SUBSTITUTIE

    13 20 15 14 19 21 4 13 8 0 25 85 14 2 0 17 5 14 2 0 17 5 14

    18 8 17 14 10 0 18 15 8 17 4 22S I R O K A S P I R E W

    Linia a treia contine suma modulo 26 a numerelor de pe primele doua linii, iar pe ultimalinie s-a scris textul criptat rezultat.

    Decriptarea se realizeaza similar, scazand (modulo 26) din codul caracterului criptat,codul caracterului corespunzator din cheie.

    O varianta a sistemul Vigenere este sistemul Beaufort (amiral englez, autorul si a uneiscale a vanturilor care i poarta numele); aici relatia de criptare () este nlocuita cu

    xi=ki(mod p) ai (mod26), (i 0)Avantajul sistemului Beaufort consta n faptul ca ecuatia de criptare se aplica si la

    decriptare (ai=ki(mod p) xi).Alta varianta este sistemul Autoclave, atribuit matematicianului Cardano (autorul

    formulelor de rezolvare pentru ecuatiile de gradul 3 si 4). Aici cheia se foloseste o singuradata, la nceput, dupa care este utilizat drept cheie textul clar.

    Exemplul 2.4 Sa luam cuvantul cheie COV OR si textul clar A VENIT TOAMNA.Putem aranja sistemul de criptare sub forma unui tabel (s-au trecut doar caracterele, nusi codific arile lor):

    Text clar: A V E N I T T O A M N ACheie: C O V O R A V E N I T T

    Text criptat C J Z B Z T O S N U G T

    Sistemul Vigenere a fost utilizat secole de-a randul, fiind considerat ca fiind unul dincele mai sigure sisteme de criptare. In 1917 de exemplu, prestigioasa revista ScientificAmerican l considera imposibil de atacat. Numai ca acest sistem a fost spart de Kasiskinca din 1863 (si independent de Babbage n 1854).

    Criptanaliza sistemului Vigenere

    Fie x=x0x1 . . . xn1 textul criptat cu cheia K=k0k1 . . . kp1. Putem aranja acest textsub forma unei matrici cu plinii si n/p coloane, astfel

    x0 xp x2p . . .x1 xp+1 x2p+1 . . .

    ...xp1 x2p1 x3p1 . . .

    Elementele de pe prima linie au fost criptate dupa formula

    xpr =apr+ k0(mod26), (k 0)

  • 7/21/2019 curs3 cap1-12.pdf

    24/177

    2.2. SISTEME DE CRIPTARE POLIALFABETICE 11

    adica cu un sistem Cezar (k0 fiind o valoare fixata din Z26). In mod similar si celelaltelinii.

    Deci, daca s-ar cunoaste lungimea p a cheii, problema s-ar reduce la criptanaliza a ptexte criptate cu Cezar sistem de criptare monoalfabetic.

    Sunt cunoscute doua metode pentru aflarea lungimii cheii: testul lui Kasiskisiindexulde coincidente.

    Prima metoda consta n studiul textului criptat si aflarea de perechi de segmente decel putin 3 caractere (aceasta lungime este propusa de Kasiski) identice. Pentru fiecareastfel de pereche, se determina distanta dintre segmente.

    Dupa ce s-au gasit mai multe astfel de distante, valoarea luipva fi cel mai mare divizorcomun al lor (sau eventual un divizor al acestuia).

    Exemplul 2.5 Oscar intercepteaza urmatorul text criptat, despre care banuie ca s-afolosit Vigenere:

    D V L O E G O G L C G I W W A F R S C K A R V S S R A A K R S T U H D A

    Q L N C J T S R U J V C W E A W K O H Z T I E U A R I Q L N C J C I K A

    Q V A G K A S J T S G R W D A G K R C W A O L N S Z P C V Z W Z C S C E

    P I E R V M W Y A W V M W E E G T U

    Textul este destul de scurt (146 litere) si nu se mai stie nici un text trimis anterior.Folosind metoda Kasiski, Oscar gaseste secventaQLNC Jcare apare pe randul al doilea.

    Distanta dintre cele doua aparitii este27. De asemenea, apar doua cuvinte foarte asema-natoare: AQLN siAOLN, avand ntre ele distanta57.

    Deci putem banui ca avem de-a face cu un cuvant cheie de lungimecmmdc(27, 57) = 3.Rescriem textul pe coloane, fiecare coloana avand trei elemente. Anume:

    D O O C W F C R S A S H Q C S J W W H I A Q C I Q G S S W G C O S C W S P R W W W G

    V E G G W R K V R K T D L J R V E K Z E R L J K V K J G D K W L Z V Z C I V Y V E T

    L G L I A S A S A R U A N T U C A O T U I N C A A A T R A R A N P Z C E E M A M E U

    Numarand frecventa aparitiei literelor pe fiecare linie, obtinem tabelul

    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

    Linia1 2 0 6 1 0 1 3 2 2 1 0 0 0 0 3 1 3 2 7 0 0 1 8 0 0 0Linia2 0 0 1 2 4 0 3 0 1 3 6 3 0 0 0 0 0 4 0 2 0 6 2 0 1 3Linia3 11 0 3 0 3 0 1 0 2 0 0 2 2 3 1 1 0 3 2 3 4 0 0 0 0 1

    In limba romana, primele litere ca frecvent a suntA EI, aflate la distant a egala unade alta. Deci vom cauta pe fiecare linie tripletele de litere situate pe pozitiile(k, k+4, k+8)avand frecvent a semnificativ de mare (maxima n cazul unui text lung). Pentru linia3,alegerea este simpla: ea este chiarA E I (16 aparitii din49posibile), deci o deplasare0 n codul Cezar.

    Pentru prima linie, sunt doua posibilitati: O S W (deplasare14) sauS W A(deplasare18), ambele cu cate18 aparitii.

  • 7/21/2019 curs3 cap1-12.pdf

    25/177

    12 PRELEGEREA 2. CIFRURI DE SUBSTITUTIE

    Tot doua variante apar si pentru a doua linie: C G K(deplasare2) cu10 aparitii,sauR V Z(deplasare14) cu13 aparitii.

    Deplasarile dau exact codificarile cheii. Deci trebuie luate n considerare patru vari-ante de cuvant cheie: OCA, ORA,SCA sau SRA. Cum de obicei cuvantul cheie areo semnificatie semantica (pentru a putea fi retinut mental usor), putem presupune ca elesteOC A sauORA.

    O simpla verificare retine drept cuvant cheieORA, care conduce la decriptarea corectaa textului (spatiile si semnele de punctuatie se pun corespunzator):

    PELANGAPLOPIIFARASOTADESEAAMTRECUTMACUNOSTEAUVECINIITOTITUNUMAICUNOSCUT

    ACEASTAESTEPRIMASTROFAAUNEINPOEZIICELEBREDEMIHAIEMINESCU

    A doua metoda de aflare a lungimii cheii de criptare ntr-un sistem Vigenere se bazeazape un concept definit n 1920 de Wolfe Friedman n 1920: indexul de coincidente([4]).

    Definitia 2.1 Daca x = x1x2 . . . xn este o secvent ae n caractere alfabetice, se numesteindex de coincidente al luixprobabilitatea ca doua caractere dinx, alese aleator, sa fieidentice. Aceasta valoare se noteazaIc(x).

    Sa notam cu fi frecventa de aparitie n x a caracterului literal codificat i (0 i 25).Doua litere din x pot fi alese n C2n moduri. Din acestea, sunt C

    2fi

    moduri ca ambele saaiba aceiasi codificare i(0 i 25). De aici se poate deduce formula

    Ic(x) =

    25i=0

    C2fi

    C2n=

    25i=0

    fi(fi 1)

    n(n 1)

    Sa presupunem cax este un text n limba romana. Din tabelul frecventelor de aparitie aleliterelor, notand pi probabilitatea de aparitie a caracterului codificat cu i (0 i 25),valoarea pe care o putem estima pentru indxul de coincidente este

    Ic(x)25

    i=0

    p2i = 0, 0788

    Motivatie: Probabilitatea ca doua elemente aleatoare sa fie ambele egale cu caracterul decod i este p2i (0 i 25). Afirmatia este valabila pentru orice criptare cu un sistemmonoalfabetic.

    Sa presupunem acum ca am aranjat textul criptat x = x0x1 . . . xn1 ntr-o matrice cup linii si n/p coloane (unde peste un numar ntreg pozitiv arbitrar), astfel

    x0= x0 xp x2p . . .x1= x1 xp+1 x2p+1 . . .

    ...xp1= xp1 x2p1 x3p1 . . .

  • 7/21/2019 curs3 cap1-12.pdf

    26/177

    2.3. EXERCITII 13

    Daca p este chiar lungimea cheii, atunci fiecare valoare Ic(xi) trebuie sa fie apropiata de0, 0788. In caz contrar, sirul xi va arata mult mai aleator, fiind obtinut prin amesteculunei secvente de caractere criptate cu chei diferite. Pentru o secventa complet aleatoare,valoarea indexului de coincidente este

    Ic 26

    1

    26

    2=

    1

    26= 0, 0384

    Valorile 0, 0788 si 0, 0384 vor constitui punctele de extrem pe care le poate lua Ic. Vom luadeci diverse valori pentru p, pana vom gasi una care sa se apropie cat mai mult de 0, 788si nu de 0, 384. Aceea poate fi considerata cu suficienta siguranta ca este lungimeacheii.

    In etapa a doua, vom ncerca sa aflam efectiv cheia K=k0k1 . . . kp1.Daca notamn1=n/p lungimea secventeixi, atunci distributia de probabilitate ale

    celor 26 litere n xi estef0n1

    , f1n1

    , . . . , f25

    n1Secventaxia fost obtinuta printr-o criptare Cezar cu o deplasareki. Deci, situatia idealaeste cand distributia de probabilitate a deplasarii

    fkin1

    , fki+1 (mod26)

    n1, . . . ,

    fki+25 (mod26)n1

    este cat mai apropiata de distributia de probabilitate p0, p1, . . . , p25 a limbii romane.Fie un ntreg m(0 m 25); definim expresia

    Fm =25

    i=0

    pi fi+mn1

    Daca m= kj (0 j p 1), ne putem astepta ca Fm25

    i=0

    p2i = 0, 0788.

    Daca m=kj, atunci Fm va fi semnificativ mai mic decat aceasta valoare. Deci, dupacel mult 25 ncercari, se poate afla deplasarea kj si deci a j-a litera din cheie.

    2.3 Exercitii

    2.1 Demonstrati ca functia de criptare afinaeK(x) =ax +b(mod26) este injectiva dacasi numai dacacmmdc(a, 26) = 1.

    2.2 Textul clar este scris peste alfabetul V = {a,b,c,d}. Se foloseste un sistem decriptare monoalfabetic dat de regulile a bb, b aab, c bab, d a. Sa searate ca functia de criptare este injectiva.

    Dar pentru: aab, bba, ca, dc ?

  • 7/21/2019 curs3 cap1-12.pdf

    27/177

    14 PRELEGEREA 2. CIFRURI DE SUBSTITUTIE

    2.3 Se definesc doua sisteme de criptare cuP={a, b}, C={c, d} si regulileaccd, bc pentru primul sistem,ac, bdcc la al doilea sistem.Ce cuvinte sunt criptate la fel n cele doua sisteme ?

    2.4 S-a receptionat mesajulARAU RIRU ITAA URIR EESU URAP IUTE IRI

    Despre el, criptanalistul are urmatoarele informatii: s-a folosit un careu de criptaretip Polybios, precum si cuvantul cheieSTROP.

    Sa se decripteze mesajul.

    2.5 In sistemele de criptare simple, orice cheie de criptare poate fi reprezentata ca ocompunere de cateva chei generatoare. La sistemul Cezar, o astfel de cheie estee1. Aratatica la sistemul afin sunt necesare cel putn doua chei generatoare.

    2.6 Decriptati urmatorul mesaj

    TKLCP OCTLE TSSZC XCMEB CVKMK CCSBX KGQBA CGQPE MBKCQ FKGSP

    SSBEB SBQPQ ACSGQ PEMGQ BLCOK CAQLB CQGKM BXCLQ GKCTX SFKCA

    CBCBV KVKME LQAKP BXXCO CPBKL KOKCB QPQAC SSPBK LKM

    criptat cu un sistem afin.

    2.7 O varianta a sistemului AUTOCLAVE este utilizarea textului criptat (n loc de textclar) dupa prima aplicare a cheii. La care din cele doua variante de AUTOCLAVE estecriptanaliza mai usoara ?

    2.8 Cate chei are un sistem de criptare afin n carecard(V) = 30, 100 sau1225 ?

    2.9 Sa presupunem caK= (5, 21) este o cheie ntr-un sistem de criptare afin pesteZ29.(a) Exprimati functia de decriptare sub formadK(y) =ay + b undea, b Z29;(b) Aratati caeK(dK(x)) =x, x Z29.

    2.10 FieK= (a, b) o cheie ntr-un sistem afin pesteZn. Aratati caK este auto-cheiedaca si numai dacaa1 a (mod n) sib (a + 1) 0 (mod n).

    Aflati toate auto-cheile dintr-un sistem afin pesteZ15.Sa presupunem can = pqundepsiqsunt numere prime distincte. Aratati ca numarul

    auto-cheilor din sistemul afin pesteZn esten +p + q+ 1.

  • 7/21/2019 curs3 cap1-12.pdf

    28/177

    Bibliografie

    [1] A. Menezes, P. Oorschot, S. Vanstome,Handbook pf Applied Cryptography

    [2] A. Salomaa, Criptografie cu chei publice, Ed. Militara, Bucuresti 1994

    [3] B. Schneier,Applied Cryptography, John Wiley and Sons, 1995

    [4] D. Stinton,Cryptography, Theory and Practice, Chapman& Hall/CRC, 2002

    [5] http://en.wikipedia.org/wiki/Caesar cipher# History and usage

    [6] http://psychcentral.com/psypsych/Polybius square

    [7] http://www.answers.com/topic/vigen-re-cipher

    15

  • 7/21/2019 curs3 cap1-12.pdf

    29/177

    Prelegerea 3

    Sisteme mecanice de criptare

    Sistemele de criptare pot fi aduse la un grad mai mare de complexitate si securitate dacase folosesc mijloace mecanice de criptare. Astfel de mecanisme special construite vor usura pe de-o parte operatiile de criptare/decriptare, iar pe de-alta parte vor fi capabile sacreeze un numar mult mai mare de chei posibile.

    3.1 Sistemul antic Skitala

    Skitala (baston n greceste) este o unealta folosita pentru realizarea unui sistem de

    criptare cu permutari. El este sub forma aproximativ cilindrica, n jurul lui fiind nfasuratao banda de hartie. Mesajul se scrie n mod normal pe aceasta banda, dupa care hartia estedesfacuta. La primire se foloseste un bat asemanator pe care se nfasoara sulul de hartie,mesajul devenind din nou inteligibil (pentru detalii, a se vedea [6], [3]). Conform istoricilorgreci, spartanii foloseau acest mod de comunicare n timpul campaniilor militare. 1 Elavea avantajul de a fi rapid si nu comporta erori de transmitere. Dezavantajul este acelaca este usor de spart.

    Exemplul 3.1 Sa presupunem ca dimensiunile batului permit scrierea a 4 randuri, cu5 caractere pe fiecare rand. Fie VINO MAINE LA INTALNIRE textul care trebuie

    criptat. Ignorand spatiile, mesajul va apare scris sub forma

    1Skitala a fost mentionata prima oara de poetul grec Archilochus (sec. VII .H). Desi apare ulteriorsi n alte texte, abia la mijlocul secolului III .H. Apollonius din Rhodos specifica limpede utilizarea luica mijloc de criptare. De remarcat ca pentru perioada respectiva, sistemele de criptare folosite de grecierau de tip steganografic. O descriere a modului de operare este dat a apoi de Plutarh (50-120 A.D.).

    1

  • 7/21/2019 curs3 cap1-12.pdf

    30/177

    2 PRELEGEREA 3. SISTEME MECANICE DE CRIPTARE

    ________________________

    | | V | I | N | O | M |

    | _ _ | A | I | N | E | L | _ _

    | A | I | N | T | A | |

    | L | N | I | R | E | |

    |___|___|___|___|___|__|

    Dupa derularea de pe skitala, mesajul scris pe banda de hartie este:VAALIIINNNNIOETRMLAE.

    La decriptare, banda va fi rulata din nou si fiecare a patra litera va fi pe aceeasi linie.Criptanaliza este foarte simpla. Se iau pe rand valorilen = 2, 3, 4, . . .. Pentru o astfel

    de valoare fixata, se formeazan randuri de tipuln+ i, 2n+ i, 3n+ i , . . . (i= 1, 2, . . . , n)

    care ulterior se concateneaza. Exista o valoare a luin pentru care textul astfel format esteinteligibil.

    3.2 Cilindrul Jefferson

    Ideea de masina de criptare apare clar prima data la Thomas Jefferson, primul secretarde Stat al Statelor Unite; acesta a inventat un aparat de criptat numit roata de criptare,

    folosit pentru securitatea corespondentei cu aliatii n special cei francezi. 2Un cilindru Jefferson este format din n discuri de dimensiuni egale (initial n = 26

    sau n= 36, dar valoarea este nerelevanta pentru descrierea sistemului) asezate pe un ax.Discurile se pot roti independent pe ax, iar pe muchea fiecaruia sunt inscrise cele 26 litereale alfabetului, ntr-o ordine aleatoare (dar diferita pentru fiecare disc).

    La criptare, textul clar se mparte n blocuri de n caractere. Fiecare astfel de blocse scrie pe o linie (generatoare) a cilindrului, rotind corespunzator fiecare disc pentru aaduce pe linie caracterul cautat. Oricare din celelalte 25 linii va constitui blocul de textcriptat.

    Pentru decriptare este necesar un cilindru identic, n care se scrie pe o linie textul

    criptat (de n caractere) si apoi se cauta printre celelalte 25 linii un text cu semnificatiesemantica. Probabilitatea de a avea un singur astfel de text creste cu numarul de discuridin cilindru.

    O mica diferenta apare daca textul clar nu are nici o semnificatie semantica (s-afolosit o dubla criptare). Atunci trebuie convenita dinainte o anumita distanta de criptares(1 s 25).

    2Thomas Jefferson a folosit acest aparat n perioada 1790 1802, dupa care se pare ca ideea s-apierdut. Devenit presedinte, Jefferson a fost atras de sistemul Vigenere, pe care l considera mai sigursi-l recomanda secretarului sau de stat James Madison ca nlocuitor al sistemului pe care l inventaseanterior.

  • 7/21/2019 curs3 cap1-12.pdf

    31/177

    3.2. CILINDRUL JEFFERSON 3

    Ordinea discurilor poate fi de asemenea schimbata. De exemplu, un cilindru cu n = 10discuri poate realiza 10! = 3.628.800 texte criptate diferite pentru acelasi text clar.

    Cilindrul Jefferson realizeaza o substitutie polialfabetica de perioada n. Daca ar fiprivit ca un sistem de criptare Vigenere, lungimea cheii este enorm a (de multe ori nn, nfunctie de modalitatile de aranjare a alfabetelor pe discuri), si deci metoda de atac a luiKasiski este inaplicabila.

    Exemplul 3.2 Sa consideramn = 10 si fie cilindrul, n care am desfasurat literele de pecele10 discuri:

    1 2 3 4 5 6 7 8 9 10 1 A A A A A A A A A A2 R R P N V S P E I I 3 I O S I O O U S R H 4 E S Y M T R H U E E 5 K U L O Y P I P S T 6 O V U C L M S B L O 7 B I K U E U E L B M 8 C J B L B B N C C U 9 U L R T C D R D D C

    10 D B C Y D Y Y H F D 11 J V D B G E D I N F 12 T C T F F C B J Y G 13 L G F G K V F F T J 14 N K G S N H G O G P 15 P N O H H F V G H Q 16 W P N J U K J K J B 17 Q Q E D P L K M K N 18 M T H E Q Q M N M V 19 S H M K R I T Q P W

    20 V E Q P S J O R Q X 21 X D V Q W N L V V L22 Z Y W V X G W W W Y 23 G W X X M T Q Y O K 24 H X Z R I W X X U R25 Y Z I Z J X Z T X S 26 F M J W Z Z C Z Z Z

    Cu ajutorul lui, textul clar TREI CULORI construit pe una din liniile generatoare alecilindrului va genera urmatoarele linii (oricare din ele putand fi folosit drept text criptat):

  • 7/21/2019 curs3 cap1-12.pdf

    32/177

    4 PRELEGEREA 3. SISTEME MECANICE DE CRIPTARE

    T R E I C U L O R I L O H M D B W G E H N S M O G D Q K S E

    P U Q C F Y X M L T W V V U K E Z N B O Q I W L N C C Q C M M J X T H V A R D U S L Z Y U H P V F C V B I B P F U W N D X F J F Q K H Y Y F Z C A G R L I X T G G G P S S Q S T G J H K S H W I E Z H P

    Y N Y J X J N A J Q F P L D M N R E K B A Q U E I G Y S M N R T K K J T D U P V I H B P Z W B P Q W E E R Q A X F B V X K D C V V Z G L W LO Y D X O A V C O Y B W T R T S J D U K C XX F Z Y O K H X R

    U Z G W L R M I Z S D M O A E P T J A Z J A N N B M O F I A

    Daca se considera o dubla criptare cu distantas= 3, atunci textul clar AAAAAAAAAAva fi criptat cu cilindrul anterior n ESYMTRHUEE.

    Cilindrul Jefferson a fost reinventat ulterior de mai multe ori, cea mai notabila fiindse pare masina de criptat M94, care a fost n serviciu pana pana n al doilea razboimondial.

    3.3 Masini de criptat

    Prima jumatate a sec. XX este dominata de masinile de criptat, o combinatie ntremasinile de scris si sisteme de criptare mecanice bazate pe discuri.

    3.3.1 C36 (M209C)

    Masina C36 este conceputa de inginerul suedez Boris Hagelin, la solicitarea armateiamericane de a avea o masina de criptat portabila, usor de manuit, care sa poata fi folosita

  • 7/21/2019 curs3 cap1-12.pdf

    33/177

    3.3. MASINI DE CRIPTAT 5

    dupa un instructaj sumar. Este cunoscuta si sub numele de M209 C, la baza fiindun model creat de Hagelin n Suedia la sfarsitul anilor 30. Ea ncepe sa fie produsa dupa cateva modificari legate de design n 1940 si nlocuieste treptat masina de criptatM94. Se apreciaza ca n timpul razboiului au fost produse circa 140.000 masini decriptat C36.

    Nu au fost specificate masuri speciale de securitate;C36 nu a fost realizata pentrua fi criptografic sigura, ea fiind destinata zonelor militare tactice, unde era nevoie doar deo siguranta de cateva ore fata de o eventuala criptanaliza.

    Vom da o prezentare matematica a principiilor sale de constructie; pentru alte detalii,a se vedea [1] si [5].

    Definitia 3.1 Se numeste matricelug o matrice binaraM627 n care fiecare din cele27coloane contine cel mult doi de1.

    Exemplul 3.3 ([4]). Toate exemplificarile referitoare la M209 vor fi facute pentrumatricea

    M=

    0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 11 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 10 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0

    Fie v un vector binar de dimensiune 6. Atunci c M este un vector cu 27 componenteavand elemente din multimea{0, 1, 2}. Numarul de elemente nenule din v Mse numesteponderea luiv n raport cuM.

    O configuratie de nceputse obtine prin asezarea unul sub altul (aliniati la stanga) asase vectori binari de lungimi 17, 19, 21, 23, 25, 26.

    Exemplul 3.4 Structura0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 00 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0

    0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 11 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1

    formeaza o posibila configuratie de nceput.Spre deosebire de matricea lug, la configuratia de nceput nu exista restrictii privind

    numarul de1.

    Plecand de la o configuratie de nceput se pot genera o infinitate de vectori de dimensiune6 n felul urmator:

  • 7/21/2019 curs3 cap1-12.pdf

    34/177

    6 PRELEGEREA 3. SISTEME MECANICE DE CRIPTARE

    1. Primii 17 vectori sunt coloanele complete ale configuratiei de nceput.

    2. Fiecare vector linie se repeta ciclic din momentul cand s-a terminat.

    Pe baza acestor elemente se poate descrie sistemul de criptare al masiniiC 36. Ream-intim, codificarea numerica a literelor este de la A0 pana la Z 25; toate calculele sevor face modulo 26.

    Fie x codul celui de-al i-lea caracter din textul clar si h ponderea celui de-al i-leavector generat de configuratia de nceput n raport cu matrica lug. Atunci

    y= h x1.

    Exemplul 3.5 Sa consideram textul clarNU PUTEM REUSI DECAT IMPREUNA

    mpreun a cu matricea lug si configuratia de nceput din exemplele anterioare. Codifi-carea numerica a textului este

    13 20 15 20 19 4 12 17 4 20 18 8 3 4 2 0 19 8 12 15 17 4 20 13 0 .Dupa ignorarea spatiilor libere3, lungimea textului clar este25.Vom calcula ponderile primilor25 vectori si vom aranja totul sub forma unui tablou:

    h 10 17 16 9 9 9 7 0 0 0 0 12 0x 13 20 15 20 19 4 12 17 4 20 18 8 3

    h x1 22 20 0 14 15 4 20 8 21 5 7 3 22W W A O P E U I V F H D W

    h 0 18 7 0 0 18 7 9 9 19 14 9x 4 2 0 19 8 12 15 17 4 20 13 0

    h x1 21 15 6 6 17 5 17 17 4 24 0 8V P G G R F R R E Y A I

    Deci textul criptat esteWWAOPEUIVFHDWVPGGRFRREYAI

    Matricea lug si configuratia de nceput formeaza cheia pentru masina C36. De fapt,

    masina nsasi este o realizare fizica a acestui sistem: ea opereaza conform cu o cheiestabilita anterior prin fixarea unor roti dintate si a unui disc (pentru detalii vezi [5]).

    Observatia 3.1 Ecuatia de decriptare este identica cu cea de criptare:

    x= h y1.

    Deci din acest punct de vedere sistemul de criptare este de tip Beaufort si masinaC 36poate fi folosita atat pentru criptare cat si pentru decriptare.

    3In aplicatiile practice, spatiul se nlocuieste uneori cu o litera de frecventa redusa.

  • 7/21/2019 curs3 cap1-12.pdf

    35/177

    3.3. MASINI DE CRIPTAT 7

    Deoarece liniile din configuratia de nceput au lungimi numere prime ntre ele, vectoriigenerati ncep sa se repete sigur dupa 17 1921232526 = 101.405.850 pasi; deci cuvantulcheie poate fi considerat mai lung decat orice text clar. Sunt nsa cazuri cand aceastaperioada poate fi mai scurta. De exemplu, daca configuratia de nceput contine numai 1,se va genera un singur vector, deci perioada este 1. De asemenea se obtin perioade scurtepentru matrici lugcu foarte putini 1 sau configuratii de nceput n care raportul dintrenumarul de 0 si 1 este disproportionat.

    Nu exista o conditie matematica pentru existenta a exact 6 linii n configuratia denceput. Acest numar a fost ales ca un compromis ntre securitatea criptografica siusurint a de a cripta. In general perioada creste cu numarul de linii.

    Masina de criptatM 209 avea si ea o serie de slabiciuni (un atac cu texte clare alese

    care au anumite componente comune poate duce la informat ii asupra matricii lug), astfelca n 1943 criptanalistii germani puteau decripta mesajele. Totusi din punct de vederemilitar tactic ea a fost considerata perfect adaptata necesitatilor si a fost folosita dearmata americana pana dupa razboiul din Coreea (19531956).

    Ulterior, Hagelin a elaborat un model mbunatatit: masina C52. Aceasta avea operioada de 2.756.205.443; discurile puteau si scoase si reinserate n alta ordine; existaun disc al carui alfabet putea fi permutat. C52 a facut parte din ultima generatiede masini de criptat clasice, noua tehnologie (cea a computerelor) permitand dezvoltareaaltor mecanisme cu o putere de calcul mult mai mare.

    3.3.2 Enigma

    Poate cea mai celebra masina de criptat a fost masina germanaEnigma. Sub acest numese afla o varietate larga de modele de masini de criptat electro-mecanice, care asigura ocriptare polialfabetica de tip Vigenere sau Beaufort.

    Ea a fost proiectata la Berlin n 1918, de inginerul german Arthur Scherbius. Primulmodel (A) este prezentat la Congresele Uniunii Postale Internationale din 1923 si 1924.Modele ulterioare sunt folosite n mai multe tari europene si asiatice (Suedia, Olanda,Marea Britanie, Japonia, Italia, Spania, SUA, Polonia, Elvetia) n scopuri comerciale,militare sau diplomatice. Din 1926 ncepe sa fie preluata si de armata germana, caredupa 1928 si defineste propriile modele (G, I, K).

    In total au fost construite circa 100.000 masini Enigma, din care 40.000 n timpulrazboiului. Dupa 1945 aliatii au capturat toate masinile de pe teritoriul german, acesteafiind nca mult timp considerate sigure. Abia n 1970 au aparut primele informatii despredecriptarea de catre aliati (Biuro Szyfrow - Polonia si Bletchley Park - Anglia) a unuimare numar de mesaje criptate prin modelul militar Enigma si transmise prin radio ntimpul razboiului.

    O descriere completa a masinii este destul de lunga; recomand pentru detalii [2], [3].In linii mari, ea are urmatoarele componente:

    Tastatura: Este o componenta mecanica formata din:

  • 7/21/2019 curs3 cap1-12.pdf

    36/177

    8 PRELEGEREA 3. SISTEME MECANICE DE CRIPTARE

    Un pupitru de taste (similar unei masini de scris);

    n discuri adiacente, care se rotesc n jurul unui ax. La marea majoritate amodelelor Enigma n = 3; sunt nsa si versiuni cu n = 5, 6 sau n = 7 discuri.Pe fiecare disc sunt scrise cele 26 caractere alfabetice (la care uneori se maiadauga trei caractere speciale);

    Un mecanism de avans (similar ceasurilor mecanice) care permite la apasareaunei taste rotirea unuia sau mai multor discuri cu un numar de pozitii. Suntfolosite mai multe variante; cea mai frecventa consta n rotirea cu o pozit ie adiscului din dreapta, la fiecare apasare a unei taste, acompaniata n anumitesituatii de rotirea discurilor vecine.

    Circuite electrice: Criptarea unui caracter se realizeaza electric. Componenta meca-nica este conceputa n asa fel ncat sa formeze un circuit electric. La apasarea uneitaste circuitul se nchide si lumineaza una sau mai multe lampi, indicand litera deiesire.

    Reflector (Umkehrwalze): Este o componenta specifica masinilor de criptat Enigma(introdusa n 1926 la sugestia lui Willy Korn). Scopul ei este de a realiza o criptareBeaufort (masina sa poata cripta sau decripta mesajele n acelasi timp). In ma-joritatea variantelor, reflectorul este asezat pe ax dupa ultimul disc (din stanga); elrealizeaza o substitutie (fixata), dupa care reintroduce noul caracter prin discuri n

    sens invers, dar pe alt drum. Deci o masina Enigma cun discuri va realiza criptareaunui caracter prin 2n+ 1 substitutii.

    O consecinta a acestei proprietati este aceea ca un caracter nu va fi niciodata criptatn el nsusi, lucru exploatat cu succes de criptanalisti.

    Tabela de conexiuni (Steckerbrett)4: Este o componenta (pozitionata n fata, subtastele literelor) n care se pot face conexiuni ntre perechi de litere, prin intermediulunor cabluri (similar centralelor telefonice vechi). Deci la un mesaj sunt posibilemaxim 13 conexiuni. De exemplu, daca printr-un cablu sunt conectate literele Ssi W, de cate ori este tastat S, semnalul este comutat pe W nainte de a intra pe

    discuri.

    Introdusa n 1930, aceasta componenta asigura un plus de securitate si a fost prin-cipalul obstacol n criptanaliza.

    Starea initiala a unei masini Enigma se refera la:

    Ordinea discurilor (Walzenlage): alegerea numarului de discuri si ordinea lor deutilizare;

    4plugboard n engleza.

  • 7/21/2019 curs3 cap1-12.pdf

    37/177

    3.3. MASINI DE CRIPTAT 9

    Pozitia initiala a discurilor: pozitionarea n mod independent a fiecarui disc, diferitapentru fiecare mesaj;

    Initializarea inelului de caractere (Ringstellung): pozitionarea alfabetului relativ laprimul disc.

    Initializarea conexiunilor (Steckerverbindungen): conexiunile dintre litere n cadrultabelei de conexiuni.

    Matematic, Enigma cripteaza fiecare litera dupa o procedura care poate fi exprimata prinprodus de permutari. Sa presupunem ca avem o masina Enigma cu 3 discuri si fie Ptransformarea tabelei de conexiuni, U reflectorul, S, M, D actiunile celor 3 discuri

    (din stanga, mijloc si respectiv dreapta). Atunci criptarea e poate fi scrisa sub forma:

    e= P DMSUS1M1D1P1

    Dupa fiecare apasare a unei taste, discurile se rotesc schimband transformarea. De exem-plu, daca discul din dreapta se roteste cu i pozitii, atunci transformarea devine iRi,where este permutarea ciclica stanga a vectorului (A , B , C , . . . , Z ). Similar, discuriledin mijloc si stanga pot fi reprezentate prin j respectivk rotiri ale lui Mrespectiv S.

    Atunci functia de criptare poate fi descrisa astfel:

    e= P(iDi)(jMj)(jSk)U(jS1k)(jM1j)(iD1i)P1

    Sa calculam numarul de variante posibile pentru criptarea unui mesaj. Vom considerao masina Enigma cu 3 discuri. Atunci numarul de situatii initiale posibile este 262626 =17.576. Cum cele 3 discuri pot fi permutate n 6 moduri, numarul variantelor se ridica la617.576 = 105.456.

    Pentru fiecare din acestea, o tabela de conexiuni cu 10 perechi de litere conectateridica numarul variantelor la 150.738.274.937.250.

    La acestea se adauga si modul de pozitionare al inelului de caractere la mecanismuldiscurilor, care mai ridica ordinul de marime al variantelor cu aproximativ 105. Acesteestimari arata ca Enigma era cea mai sigura masina de criptat a momentului respectiv.

  • 7/21/2019 curs3 cap1-12.pdf

    38/177

    10 PRELEGEREA 3. SISTEME MECANICE DE CRIPTARE

  • 7/21/2019 curs3 cap1-12.pdf

    39/177

    Bibliografie

    [1] Kahn, David -The Codebreakers, MacMillan Publishing Co, New York, 1967

    [2] http: //en.wikipedia.org/wiki/Enigma machine

    [3] Thomas Kelly - The myth of the skytale, Cryptologia, Iulie 1998, pp. 244 - 260.

    [4] Salomaa, Aarto - Criptografie cu chei publice, Ed. Militara, 1994

    [5] http: //en.wikipedia.org/wiki/M209

    [6] Collard Brigitte - Secret Language in Graeco-Roman antiquity(teza de doctorat)http: //bcs.fltr.ucl.ac.be/FE/07/CRY P T /Intro.html

    11

  • 7/21/2019 curs3 cap1-12.pdf

    40/177

    Prelegerea 4

    Sisteme de criptare fluide

    4.1 Sisteme sincronizabile si auto-sincronizabile

    In sistemele de criptare prezentate pana acum, elementele succesive ale textului clar eraucriptate folosind aceeasi cheie K. Deci, daca

    x= x1x2x3 . . .

    este textul clar, textul criptat este

    y= y1y2y3 . . .= eK(x1)eK(x2)eK(x3) . . .

    Sistemele de criptare de acest tip se numesc sisteme de criptare bloc (block cyphers).Alta maniera utilizata este aceea a sistemelor de criptare fluide (stream cyphers).

    Definitia 4.1 Fie M= (P, C, K, E, D) un sistem de criptare. O secventa de simbolurik1k2k3 . . . K

    + se numeste cheie fluida.

    Definitia 4.2 M= (P, C, K, E, D) este un sistem fluid daca cripteaza un text clar

    x= x1x2x3 . . .

    n

    y= y1y2y3 . . .= ek1(x1)ek2(x2)ek3(x3) . . .unde

    k= k1k2k3 . . .

    este o cheie fluida dinK+.

    Problema principala este aceea de a genera o astfel de cheie de criptare (teoretic infinit).Aceasta se poate realiza fie aleator, fie pe baza unui algoritm care pleaca de la o secventamica de chei de criptare. Un astfel de algoritm se numeste generator de chei fluide.Mai multe detalii vor fi prezentate n cadrul prelegerii dedicate generatorilor de numerepseudo-aleatoare.

    1

  • 7/21/2019 curs3 cap1-12.pdf

    41/177

    2 PRELEGEREA 4. SISTEME DE CRIPTARE FLUIDE

    Exemplul 4.1 (sistemul de criptare Vernam):In acest sistemxi, ki, yi {0, 1}. Criptarea se realizeaza conform formulei

    yi=xi ki, (i 1)

    Daca cheia fluida este aleasa aleator si nu mai este folosita ulterior, sistemul decriptare Vernam se numeste one - time pad.

    Un sistem de criptare one-time pad este teoretic imposibil de spart. 1 Intr-adevar,fiind dat un text criptat cu un astfel de sistem, Oscar nu are nici o informatie privindcheia fluida sau textul clar. Dificultatea consta ns a atat n lungimea cheii (egala cu ceaa textului clar), cat si n modalitatea de transmitere a ei ntre Alice si Bob.

    Pentru sistemul Vernam exista o modalitate de atac cunoscuta sub numele de crip-tanaliza diferentiala (prezentata mai tarziu, n cadrul sistemului de criptare DES).Anume:

    Dacay1y2 . . . yn siy

    1y

    2 . . . y

    nsunt doua texte criptate cu aceiasi chee fluidak1k2 . . . kn,atunci

    yi=xi ki, y

    i = x

    i ki (1i n)

    deciyi yi==xi x

    i, si cheia nu mai este necesara, ci doar informatia privind lungimeasa; redundanta ultimei relatii va permite criptanaliza.

    Sistemele de criptare fluide sunt clasificate nsisteme sincrone siauto-sincronizabile.

    Definitia 4.3 Un sistem de criptare fluid sincron este o structura (P, C, K, L, E, D),unde:

    P, C, Ksunt multimi finite nevide ale caror elemente se numesc texte clare, textecriptate si respectiv chei;

    L este o multime finita nevida numita alfabet sir de chei;

    g: K L+ este un generator de chei fluide: pentruk K, g(k) =k1k2k3 . . . L

    +

    este o cheie fluida (teoretic infinita);

    z L exista o regula de criptareez E si o regul a de decriptaredz D astfel cax P, dk(ek(x)) =x

    Exemplul 4.2 Sistemul de criptare Vigenere poate fi definit ca un sistem de criptarefluid sincron. Fiem lungimea cuvantului cheie din sistemul Vigenere. Definim

    1In anii 90 comunicarea ntre Moscova si Washington era securizata n acest mod, transportul cheiide criptare fiind asigurat de curieri.

  • 7/21/2019 curs3 cap1-12.pdf

    42/177

    4.1. SISTEME SINCRONIZABILE SI AUTO-SINCRONIZABILE 3

    P=C=L =Z26, K=(Z26)m ,

    ez(x) =x + z(mod26), dz(y) =y z(mod26)

    Cheiaz1z2z3 . . . este definita

    zi=

    ki daca 1i mzim daca im + 1

    Ea va genera din cheia fixaK= (k1, k2, . . . , km), cheia fluidak1k2 . . . kmk1k2 . . . kmk1k2 . . .

    Procesul de criptare cu un sistem fluid sincron poate fi reprezentat ca un automatdescris de relatiile

    qi+1=(qi, k), zi=g(qi, k), yi=h(zi, xi)

    unde q0 este starea initiala care poate fi determinata din cheia k, este functia detranzitie a starilor, g este functia care produce cheia fluidazi, iar h este functia de iesirecare produce textul criptat yi pe baza textului clar xi si a cheii fluide zi.

    qi

    g hk

    qi+1

    zi

    xi

    yi

    qi

    g h1k

    qi+1

    zi

    yi

    xi

    (a) Criptare (b) Decriptare

    Observatia 4.1

    Un sistem de criptare bloc poate fi privit ca un caz particular de sistem de criptarefluid, n carei1, zi=K.

    (sincronizare): In sistemele de criptare fluide sincrone, Alice si Bob trebuie sa-sisincronizeze cheia fluida pentru a putea obtine o criptare/decriptare corecta. Daca ntimpul transmisiei sunt inserati sau eliminati biti n textul criptat, atunci decriptareaesueaz a si ea poate fi reluata numai pe baza unor tehnici de resincronizare (cum ar fide exemplu reinitializarea sau plasarea unor marcatori speciali la intervale regulaten textul transmis).

    Modificarea unui bit din textul criptat (faa a se elimina sau adauga nimic) nu vaafecta decriptarea altor caractere (nepropagarea erorii).

  • 7/21/2019 curs3 cap1-12.pdf

    43/177

    4 PRELEGEREA 4. SISTEME DE CRIPTARE FLUIDE

    Un adversar activ care elimina, insereaza sau retrimite componente ale mesajuluicriptat, va provoca desincronizari si va fi deci detectat la receptie. De asemenea, elpoate face modificari n textul criptat si sa observe cum vor afecta ele textul clar.Deci un text criptat cu un sistem fluid sincron necesita meca-nisme separate deautentificare si de garantare a integritatii datelor.

    Definitia 4.4 Un sistem aditiv fluid binar de criptare este un sistem fluid sincron n careP=C=L=Z2 iarh este functia (XOR).

    Un astfel de sistem este reprezentat mai jos:

    Generatorchei fluide

    k

    zi

    xi

    yiGeneratorchei fluide

    k

    zi

    yi

    xi

    (a) Criptare (b) Decriptare

    Definitia 4.5 Un sistem de criptare fluid este auto-sincronizabil (sau asincron) dacafunctia de generare a cheii fluide depinde de un numar fixat de caractere criptate anterior.

    Deci comportamentul unui astfel de sistem poate fi descris de ecuatiile

    qi= (yit, yit+1, . . . , yi1), zi=g(qi, k), yi=h(zi, xi)

    unde q0= (yt, yt+1, . . . , y1) estestarea initiala(cunoscuta),k este cheia,g este functiade generare a cheii fluide, iar h este functia de iesirecare cripteaza textul clar xi. Celemai cunoscute sisteme auto-sincronizabile sunt registrii liniari cu feedback, utilizati lagenerarea secventelor de numere pseudo-aleatoare (n criptografie) si la generarea codurilorciclice (n teoria codurilor).

    Exemplul 4.3 (Criptare cu auto-cheie)2:FieP=C=L =Z26. Se defineste cheia fluida astfel:

    z1=K, zi = yi1, (i 2)

    Pentru un element oarecare al cheiiz Z26, se definesteez(x) =x + z(mod26)dz(y) =y z(mod26)

    Sa consideramK= 13 si s a criptam textul clarBUCU RESTI.

    2Se pare ca sistemul este atribuit lui Vigenere.

  • 7/21/2019 curs3 cap1-12.pdf

    44/177

    4.1. SISTEME SINCRONIZABILE SI AUTO-SINCRONIZABILE 5

    Transformat n secvent a numerica vom avea

    (x1, x2, x3, x4, x5, x6, x7, x8, x9) = (1, 20, 2, 20, 17, 4, 18, 19, 8)

    In faza de criptare, vom calcula pe rand:y1=e13(x1) = 1 + 13 (mod26) = 14; y2 =e14(x2) = 20 + 14 (mod26) = 8;y3=e8(x3) = 2 + 8 (mod26) = 10; y4 = e10(x4) = 20 + 10 (mod26) = 4;y5=e4(x5) = 17 + 4 (mod26) = 21; y6 = e21(x6) = 4 + 21 (mod26) = 25;y7=e25(x7) = 18 + 25 (mod26) = 17; y8=e17(x8) = 19 + 17 (mod26) = 10;y9=e10(x9) = 8 + 10 (mod26) = 18;

    Deci textul criptat este(14, 8, 10, 4, 21, 25, 17, 10, 18) sau n litere: OIKEV ZRKS.Pentru decriptare, vom avea:x1=d13(y1) = 14 13 (mod26) = 1; x2=d14(y2) = 8 14 (mod26) = 20; s.a.m.d.Se observa ca textul decriptat poate fi obtinut de oricine, aproape n totalitate, fara a

    cunoaste nici o cheie (aceasta fiind necesara doar pentru decriptarea primului caracter).Deci gradul sau de securitate este nul.

    Ceva mai dificil este sistemul n care generarea cheii fluide se realizeaza cu ecuatiazi= xi1(i 2).

    In acest caz, BUCU RESTI se cripteaza nO V W W LV W LB (pentruK= 13).Nici acest sistem de criptare cu auto-cheie nu este sigur, deoarece evident sunt

    posibile doar26 chei.

    Proprietati:1. Auto-sincronizare: Deoarece functia de decriptare h1 depinde numai de un numar

    fixat de caractere criptate anterior, desincronizarea rezultata eventual prin in-serarea sau stergerea de caractere criptate se poate evita. Astfel de sisteme decriptare pot restabili proprietatea de sincronizare afectand doar un numar finit decaractere din textul clar.

    2. Propagarea limitata a erorii: Daca starea unui sistem fluid auto-sincronizabil de-pinde de t caractere anterioare, atunci modificarea (eventual stergerea sau inser-area) unui caracter din textul criptat poate duce la decriptarea incorecta a maximt caractere; dupa aceea decriptarea redevine corecta.

    3. Raspandirea textelor clare: Deoarece fiecare caracter din textul clar influenteazantregul text criptat care urmeaza, eventualele proprietati statistice ale textului clarsunt dispersate prin textul criptat. Deci, din acest punct de vedere, sistemele decriptare auto-sincronizabile sunt mai rezistente decat cele sincronizabile la atacurilebazate pe redondanta textului clar.

    4. Rezistenta la criptanaliza activa: Din proprietatile de mai sus rezulta ca este destulde dificil de depistat un atac venit din partea unui adversar activ (care poate mod-ifica, insera sau sterge caractere) auto-sincronizarea readucand decriptarea n faza

  • 7/21/2019 curs3 cap1-12.pdf

    45/177

    6 PRELEGEREA 4. SISTEME DE CRIPTARE FLUIDE

    normala. De aceea sunt necesare mecanisme suplimentare pentru a asigura auten-tificarea si integritatea datelor.

    4.2 Exemple de sisteme fluide de criptare

    4.2.1 SEAL

    SEAL (Software - optimized Encryption ALgorithm) este un sistem de criptare aditivbinar (Definitia 4.4), definit n 1993 de Coppersmith si Rogaway. Este unul din cele maieficiente sisteme implementabile pe procesoare de 32 biti.

    La un astfel de sistem este importanta descrierea generatorului de chei fluide (care seaduna modulo 2 cu textul clar). SEALeste o functie pseudo-aleatoare care scoate o cheiefluida de L biti folosind un numar n de 32 biti si o cheie secreta ade 160 biti.

    Fie A, B,C,D,Xi, Yj cuvinte de 32 biti. Vom folosi urmatoarele notatii:

    1. A: complementul lui A(pe biti);

    2. A B, A B, A B: operatiile OR,AND siXOR (pe biti);

    3. A > s: rotirea ciclica a lui Aspre dreapta cu spozitii;

    5. A + B(mod232): suma luiA siB (considerate ca numere ntregi fara semn);

    6. f(B , C , D) = (B C) (B D);g(B , C , D) = (B C) (B D) (C D); h(B , C , D) =B C D.

    7. A||B: concatenarea luiAcu B ;

    8. (X1, X2, . . . , X n)(Y1, , , , , Y 2, . . . , Y n): atribuire simultana.

  • 7/21/2019 curs3 cap1-12.pdf

    46/177

    4.2. EXEMPLE DE SISTEME FLUIDE DE CRIPTARE 7

    Algoritmul de generare a tabelei G pentru SEAL 2.0: 3

    Intrare: Un sir ade 160 biti si un ntreg i (0 i

  • 7/21/2019 curs3 cap1-12.pdf

    47/177

    8 PRELEGEREA 4. SISTEME DE CRIPTARE FLUIDE

    Intrare: a cheia secreta (160 biti), n [0, 232) ntreg, L - lungimea solicitata pentrucheia fluida.Iesire: cheia fluida y, |y|= L, unde L este primul multiplu de 128 din [L, ).

    1. Se genereaza tabelele T, S , R avand ca elemente cuvinte de 32 biti.

    Fie functiaFa(i) =Hii(mod5) unde H

    i0H

    i1H

    i2H

    i3H

    i4=Ga(i/5).

    a. fori0 to 511 doT[i]Fa(i);

    b. forj 0 to255 doS[j]Fa(0x00001000 +j);

    c. for k0 to4 (L 1)/8192 1 doR[k]Fa(0x00002000 + k);

    2. Descrierea procedurii Initialize(n,l,A,B,C,D,n1, n2, n3, n4) cu intrarile n (cuvant)sil (ntreg). Iesirile sunt A, B,C,D,n1, n2, n3, n4 (cuvinte).

    a. An R[4 l], B(n >>8) R[4 l+ 1],

    C(n >>16) R[4 l+ 2], D(n >>24) R[4 l+ 3].

    b. forj 1 to2 do

    P A 0x000007f c, BB + T[P/4], A(A >>9),

    P B 0x000007f c, C C+ T[P/4], B(B >>9),

    P C 0x000007f c, DD + T[P/4], C(C >>9),

    P D 0x000007f c, AA + T[P/4], D(D >>9),(n1, n2, n3, n4)(D,A,B,C);

    P A 0x000007f c, BB + T[P/4], A(A >>9),

    P B 0x000007f c, C C+ T[P/4], B(B >>9),

    P C 0x000007f c, DD + T[P/4], C(C >>9),

    P D 0x000007f c, AA + T[P/4], D(D >>9),

    3. l0, y (sirul vid);

    4. repeata. Initialize(n,l,A,B,C,D,n1, n2, n3, n4);

    b. fori1 to64 do

    P A 0x000007fc, BB + T[P/4], A(A >>9), BB A;

    QB 0x000007fc, CC+ T[Q/4], B(B >>9), CC B;

    P (P+ C) 0x000007fc, DD + T[P/4], C(C >>9), DD C;

    Q(Q + D) 0x000007fc, AA + T[Q/4], D(D >>9), AA D;

    P (P+ A) 0x000007fc, BB + T[P/4], A(A >>9);

    Q(Q + B) 0x000007fc, CC+ T[Q/4], B(B >>9);

  • 7/21/2019 curs3 cap1-12.pdf

    48/177

    4.2. EXEMPLE DE SISTEME FLUIDE DE CRIPTARE 9

    P (P+ C) 0x000007fc, DD + T[P/4], C(C >>9);Q(Q + D) 0x000007fc, AA + T[Q/4], D(D >>9);yy||(B+ S[4 i 4])||(C S[4 i 3])||(D+ S[4 i 2])||(A S[i 1]).

    if|y| L then return(y) STOPelse ifi(mod2) = 1 then(A, C)(A + n1, C+ n2)

    else (A, C)(A + n3, C+ n4)c. ll+ 1.

    Observatia 4.2 ([1]) In majoritatea aplicatiilor pentru SEAL 2.0 se folosesteL 219.Algoritmul functio

of 177/177
7/21/2019 curs3 cap1-12.pdf http://slidepdf.com/reader/full/curs3-cap1-12pdf 1/177 Prelegerea 1 Not ¸iuni de baz˘a ale criptografiei 1.1 Definit ¸ii ¸ si notat ¸ii preliminare Criptografia este o component˘a a unui domeniu mult mai larg, numit securitatea informat ¸iei. Obiectivele urm˘ arite de acesta pot fi sumarizate ˆ ın: 1.  Confident ¸ialitate (privacy): proprietatea de a p˘astra secretul informat ¸iei, pentru ca aceasta s˘ a fie folosit˘a numai de persoanele autorizate. 2.  Integritatea datelor : proprietatea de a evita orice modificare (inserare, ¸ stergere, substitut ¸ie) neautorizat˘ a a informat ¸iei. 3.  Autentificare : Proprietatea de a identifica o entitate conform anumitor standarde. Este compus˘ a din (a)  Autentificarea unei entit˘ at ¸i ; (b)  Autentificarea sursei informat ¸iei ; 4.  Non - repudierea : Proprietatea care previne negarea unor evenimente anterioare. Celelalte obiective legate de securitatea informat ¸iei (autentificarea mesajelor, semn˘aturi, autorizare, validare, controlul accesului, certificare, timestamping, confirmarea recept ¸iei, anonimitate, revocare) pot fi derivate din acestea. Definit ¸ia 1.1  Criptografia este studiul metodelor matematice legate de securitatea infor- mat ¸iei, capabile s˘ a asigure confident ¸ialitatea, autentificarea ¸si non-repudierea mesajelor, precum ¸si integritatea datelor vehiculate ([1]. Termenul  criptografie  ˆ ınseamn˘a  scriere secret˘ 1 . Domeniul cuprinde atˆ at operat ¸ia de criptare (cifrare) a unui text, cˆat ¸ si eventualele ˆ ıncerc˘ ari de descifrare ¸ si de aflare a cheii 1 Cuvˆ antul este format din cuvintele grece¸ sti  cryptos  – ascuns ¸ si  grafie  – scriere 1
Embed Size (px)
Recommended