Algoritmul de criptare rsa

[hozarares]

Criptografia este ?tiin?a scrierilor secrete. Ea folose?te metode matematice pentru transformarea datelor, în inten?ia de a ascunde con?inutul lor sau de a le proteja împotriva modific?rii. Criptografia are o lung? istorie, confiden?ialitatea comunic?rii fiind o cerin?? a tuturor timpurilor. Drept dovad?, întâlnim texte codificate înc? din antichitate. Astfel, în 1900 î.e.n., un scrib egiptean utiliza simboluri în locul literelor obi?nuite, pentru a ascunde de priviri nedorite scrierile sale. În 500 î.e.n., scribii evrei cripteaz? mesaje prin permutarea literelor alfabetului (A devine Z, B devine Y, etc.), dând na?tere limbajului atbash. În 50 î.e.n., Iulius Cezar creeaz? metoda ce-i poart? numele; aceasta const? în a înlocui fiecare liter? din alfabet cu cea de peste trei pozi?ii spre dreapta, cu reluarea alfabetului de la cap?t, acolo unde este cazul. Astfel, litera A devine D, B devine E ?i a?a mai departe. De fapt, el cripteaz? textul utilizând func?ia afin? xax+3. Fiabilitatea acestei metode ara asigurat? în principal de noutatea ei, nimeni necunoscând "trucul".

În zilele de azi astfel de metode nu mai sunt sigure, algoritmii de acest tip fiind spar?i cu destul de mult? u?urin??.

Orice criptare con?ine dou? etape: mai întâi, codarea mesajului pe care dorim s?-l transmitem, etap? în care atribuim un num?r fiec?rei litere din mesaj (?i transmiterea mesajului revine la transmiterea unui ?ir de cifre, numit ?i cod), ?i criptarea codului, etap? în care modific?m codul astfel încât acesta s? nu poat? fi reconstituit decât de persoana sau persoanele autorizate în acest sens.

Ast?zi se cunosc dou? tipuri de algoritmi de criptare: algoritmi simetrici (sau cu cheie secret?), ?i algoritmi asimetrici (sau cu cheie public?). Algoritmii simetrici au la baz? acela?i principiu ca ?i codul lui Cezar ?i anume substitu?ia. Puterea lor const? îns? în faptul c? se lucreaz? cu secven?e de numere din ce în ce mai lungi, ghicirea combina?iei fiind astfel din ce în ce mai grea, necesitând foarte mult timp. La cifrarea ?i descifrarea unui cod simetric se folose?te aceea?i cheie, cunoscut? doar de cel care trimite mesajul ?i cel care trebuie s?-l primeasc?.

Algoritmul reprezentativ pentru algoritmii de criptare cu cheie secret? este DES, creat în anii 1970. Textul este mai întâi transcris într-o secven?? de 0 ?i 1, secven?? transmis? mai departe în blocuri de câte 64, care se cifreaz? utilizând o permutare cunoscut? doar de cel care trimite mesajul ?i de c?tre destinatar. Singura metod? de a sparge un text criptat cu DES este for?a brut?, adic? încercarea tuturor permut?rilor posibile. Îns? acest algoritm are ?i câteva dezavantaje: dac? se pierde cheia sau dac? este aflat? de ter?e persoane, textul se pierde sau este decriptat de persoane indezirabile; în plus, persoana care trimite mesajul, are cheia pentru a-l decripta.

Aceste dou? neajunsuri au fost rezolvate în 1976 de Whitfield Diffie ?i Martin Hellman, care propun o nou? metod? de criptare: utilizarea unei func?ii P definite pe mul?imea numerelor întregi ?i inversa acesteia S. Dac? cele dou? func?ii P ?i S sunt cunoscute, este u?or de decriptat orice mesaj codificat cu ajutorul func?iei P. Dac? îns? nu cunoa?tem decât func?ia P, de?i putem cripta mesajul, nu-l putem decripta, fiind foarte greu de aflat func?ia S. Ceea ce îns? nu au reu?it cei doi matematicieni a fost s? g?seasc? o astfel de pereche de func?ii (P, S). Dar acest obstacol a fost dep??it destul de repede: în 1977, D. Rivest, A. Shamin ?i L. Adleman g?sesc o solu?ie, cea mai bun? ?i cea mai utilizat? ast?zi: criptografia RSA. RSA se bazeaz? pe urm?toarele dou? adev?ruri:

• este u?or de fabricat dou? numere prime p ?i q foarte mari (de exemplu, de 100 de cifre);

• dat un num?r n=pq , unde p ?i q sunt numere prime suficient de mari, este foarte greu de reg?sit p ?i q.

Principiul algoritmului RSA

Fie num?rul întreg x mesajul pe care vrem s?-l transmitem ?i fie n=pq , unde p ?i q sunt dou? numere prime suficient de mari (n este un num?r care poate fi f?cut public, îns? nu p ?i q). Se d? de asemenea cheia de criptare, e. RSA se bazeaz? pe congruen?ele modulo n, astfel:

• Expeditorul construie?te y=x3 (mod n), num?r care va fi f?cut public (criptarea mesajului x).

• Destinatarul, care este singurul ce cunoa?te d cu proprietatea x=yd(modn), reconstruie?te mesajul ini?ial x. (decriptarea mesajului).

Suportul matematic al algoritmului RSA

Avem de ar?tat c? exist? numerele e ?i d pe care le-am folosit în paragraful anterior. S? observ?m c? a face opera?iile modulo n este acela?i lucru cu a lucra în inelul In, deci ne vom folosi de propriet??ile sale algebrice. Dac? j este func?ia indicatoare a lui Euler, atunci In este un inel cu j(n) elemente inversabile, adic?, în cazul nostru particular, cu (p-1)(q-1) elemente inversabile. Dac? alegem e astfel încât (e, j(n))=1, atunci, conform algoritmului lui Euclid, va exista un num?r întreg d ?i un num?r k astfel încât de+k?(n)=1, de unde va rezulta c? xed=x , deci e ?i d îndeplinesc propriet??ile necesare pentru a putea fi folosite drept cheie public? ?i cheie secret? în algoritmul RSA.

Mai facem observa?ia c? a afla d (care ar trebui s? nu fie cunoscut decât de destinatar) este totuna cu a factoriza n, lucru care am stabilit deja c? este foarte dificil.

Dezavantajul algoritmului RSA, ?i în general al algoritmilor cu chei publice, este c? sunt destul de len?i, în sensul c? pentru a cripta ?i a decripta un mesaj (în condi?iile în care avem cheile public? ?i secret?) consum?m o cantitate mare de timp. Din acest motiv, de multe ori, se folosesc algoritmi combina?i: cu chei secrete ?i chei publice.

Aplica?ii ale algoritmului RSA

Un prim domeniu unde întâlnim algoritmi de criptare, ?i în special RSA, este cel al telecomunica?iilor: telefoane publice, cu cartele electronice, sau telefoanele mobile (protocoale de autentificare a persoanei apelate). De asemenea, în domeniul s?n?t??ii, prin intermediul cardurilor electronice care s? con?in? istoricul medical al unui individ. Securitatea na?ional?: c?r?i de identitate, pa?apoarte, legitima?ii magnetice. ?i s? nu uit?m economia: cardurile bancare, comer?ul electronic, sau informatica: confiden?ialitatea po?tei electronice, a informa?iilor de pe o pagin? de web, pe scurt, dreptul la intimitate.

Unde vom întâlni nevoia de semn?tur? ?i identificare electronic?, vom întâlni criptarea prin RSA.

Ca o concluzie a acestui material, a? dori s? precizez c? se poate face o introducere în algoritmii de criptare la sfâr?itul clasei a XII-a. În acest fel, putem integra câteva teoreme de aritmetic? (teorema lui Fermat, teorema lui Bezout, algoritmul lui Euclid), la prima vedere aride pentru elevi ?i f?r? leg?tur? cu via?a real?, într-un context actual ?i de mare interes, r?spunzând par?ial la eterna întrebare a elevilor: "Care este aplicabilitatea practic? a cuno?tin?elor de matematic? dobândite la or??"

Prof. M?d?lina DUMINIC?,

Colegiul Militar Liceal "?tefan cel Mare"