Criptografia cu Cheie Publica

Capitolul I

NOȚIUNI FUNDAMENTALE DESPRE

CRIPTOGRAFIE

1.1 Introducere

Criptografia protejează informația vehiculată prin rețelele moderne de calculatoare. De-a lungul istoriei omenirii, dorința și necesitatea comunicării confidențiale au dus la perfecționarea științei scrierilor secrete, numite azi criptografie. Cunoștințele actuale referitoare la începuturile criptografiei sunt furnizate de diferite lucrări despre științele, religiile, războaiele de pe vremea unor civilizații de mult apuse. Este de apreciat că apariția criptografiei s-a petrecut în mod independent în mai multe părți ale lumii, la mai multe popoare. Dezvoltarea și continua perfecționare a criptografiei se datorează, în primul rând, războaielor și activității diplomatice.

Istoria criptografiei este deci lungă si pitorească. Evident, dezvoltarea tehnicilor de criptare a constituit o prioritate pentru organizațiile militare, care utilizau frecvent asemenea procedee. Înainte de apariția calculatoarelor, volumul mare de mesaje criptate sau transmise a fost gestionat de un număr mare de funcționari „codori”. Evident, tehnicile folosite erau limitate de capacitatea codorilor de realizare a transformărilor necesare și de însușirea de către aceștia a unor tehnici criptografice noi. Totuși, pericolul de capturare a codurilor de către „inamici” făcea necesară schimbarea periodică a metodei de criptare.

Necesitatea protecțiilor informațiilor a reprezentat un deziderat mereu actual al omenirii. Tehnici secrete de codificare a mesajelor au fost utilizate încă din antichitate și au prezentat o evoluție continuă de-a lungul timpului, afectând în multe cazuri chiar istoria.

Criptarea mesajelor și trimiterea lor sub aceasta forma este utilizată de foarte mult timp. Unul dintre primii care au folosit tehnici de criptare pentru trimiterea mesajelor a fost celebrul împărat Cezar si dacă ar trebui ales un singur exemplu al criptografiei „clasice”, acesta ar fi cifrul lui Cezar, nu atât datorită celebrității împăratului roman de care se leagă folosirea lui, ci pentru că principiul său de bază s-a menținut nealterat aproape două milenii. În comunicarea privată cu o persoană folosirea unui cod secret poate preveni citirea intenționată sau neintenționată a mesajelor de către cei care intră în posesia acestora, fie că trebuie să le transporte până la destinatar, fie că le interceptează în timp ce mesajul este transmis.

Încă din cele mai vechi timpuri tehnologia în ceea ce privește domeniul criptografic a cunoscut progrese majore, și tocmai de aceea se poate spune că în momentul de față se asistă la o informatizare pe scară largă a mai multor instituții, lucru datorat avantajelor aduse de sistemele informatice: colectarea, transmiterea, procesarea și regăsirea datelor se face mai rapid, mai ieftin, mai ușor, cu o economie mai mare de spațiu. Astfel se face o economie semnificativă de timp și de efort care pot fi investite pentru realizarea altor acte de mai bună calitate. Cu toate acestea există însă și un dezavantaj major, și anume securitatea datelor devine mai greu de asigurat. Se poate spune că unul din cele mai studiate domenii din zilele noastre este criptarea mesajelor. Complexitatea tehnicilor de criptare și de trimitere a mesajelor crește permanent pentru a obține o securitate cât mai ridicată a comunicațiilor.

Puține sunt persoanele care să nu fi încercat, măcar o dată, transmiterea cifrată a unor mesaje personale foarte importante. Și mai puține sunt, probabil, cele care nu s-au amuzat niciodată rezolvând jocuri rebus unde, pe baza unor frânturi de mesaj trebuie descoperită regula de reconstituire a mesajului. Explicația este atracția firească pe care o prezintă un astfel de exercițiu intelectual și satisfacția pe care ți-o dă reușita rezolvării. Criptografia sau știința codificării informației în vederea împiedicării acceselor neautorizate are o lungă istorie, confidențialitatea comunicării fiind o cerință a tuturor timpurilor.

Când Iulius Cezar trimitea mesaje către generalii lui, el nu avea încredere în loialitatea mesagerilor. Așa că, în cadrul mesajelor scrise el înlocuia toate literele „A” cu „D”, fiecare „B” cu „E” si așa mai departe, în cadrul întregului alfabet. Numai cineva care cunoștea și „saltul cu trei” putea să descifreze mesajul.

Informațiile care pot fi citite și înțelese fără a folosi instrumente speciale, sunt numite „text în clar” sau în limba engleză „plaintext” ori „cleartext”. Metoda de camuflare a textului în clar în așa fel încât substanța să nu sufere modificări semantice, este denumită criptare. Din criptarea unui „plaintext” rezultã un text ilizibil numit criptotext. Se folosește criptarea pentru a fi sigur că informația este inaccesibilă oricărei persoane care nu deține instrumentul necesar decriptării, chiar dacă oricine poate vedea datele în formă criptografică. Oricum nu va înțelege nimic, care să conducă spre descifrarea textului original. Procesul retransformării criptogramei în textul original este numit decriptare.

Criptarea sau cifrarea definită și ca un mecanism puternic de asigurare a confidențialității asigura confidențialitatea datelor atunci când mecanismele de împiedicare a accesului la date au eșuat. Este un lucru înțelept să se folosească și criptarea, deoarece sistemele informatice sunt foarte complexe, atât din punct de vedere hard, cât și soft, așa că întotdeauna vor exista breșe în sistemele de restricționare a accesului. Dacă mecanismul de criptare a datelor este puternic și aplicat în mod corect, atacatorul va avea în față niște date pe care nu va putea să le folosească.

Criptografia este știința care folosește matematica pentru a codifica si decodifica informațiile. Cu ajutorul criptografiei se pot stoca ușor informațiile sau se pot transmite de-a lungul unor rețele nesigure, de exemplu Internetul, și nu pot fi citite decât de aceia care posedă cheia pentru decriptare. În timp ce criptografia este știința securizării informațiilor, criptanaliza este știința analizării și verificării securității comunicației. Criptanaliza clasică implică combinații interesante de judecăți analitice, aplicații ale metodelor matematice, căutarea șabloanelor, determinare si noroc. Criptologia le include pe ambele, criptografia și criptanaliza.

Criptografia poate fi puternică sau slabă. Puterea procesului de criptografie este măsurată în timp și în resurse informatice necesare pentru a cripta un text. Rezultatul unei criptografii avansate este un text criptat, foarte greu de descifrat fără a fi în posesia unui instrument de decriptare. Cât de dificil? Dată fiind toată puterea de calcul din momentul de față și tot timpul disponibil, luând în considerare un miliard de calculatoare care fac un miliard de operații pe secundă, este practic imposibil de descifrat rezultatul unei criptografii avansate înainte de sfârșitul Universului. Unii s-ar putea gândi deci, că criptografia avansată poate fi folosită foarte bine chiar împotriva unui criptanalist extrem de bine motivat. Cine spune asta? Nimeni n-a dovedit că este posibil ca folosind cea mai avansată tehnică de criptografie posibilă astăzi poate fi considerat la fel mâine, la puterea de calcul a zilei de mâine. Oricum, criptografia avansată este cea mai bună dintre cele disponibile astăzi. Vigilența si dorința de a păstra informațiile intacte vor proteja mai bine oricum decât tendința de a proteja prin impenetrabilitatea sistemelor informatice.

În cadrul criptografiei, criptarea se definește ca fiind procesul de aducere a informației din forma ei inițială, inteligibilă, într-o formă neinteligibilă, astfel încât să fie făcută imposibil de citit fără cunoștințe secrete. Deci textul inițial, care se dorește a fi protejat, se numește „text în clar”, iar rezultatul criptării se numește „text cifrat” sau „criptogramă”. Decriptarea sau descifrarea este procesul invers, recuperând textul în clar din textul cifrat.

1.2 Evoluția criptografiei

Criptografia în antichitate

Egiptul antic de acum circa patru mii de ani ne furnizează primele indicii despre criptografie sub forma unor formule funerare care conțin, într-o formă incipientă, elemente constitutive ale științei de astăzi. Grecii au practicat în multe variante scrierea secretă, așa cum atestă documentele istorice.

În lucrări antice din secolele IV-V î.e.n. se prezintă diferite variante de scriere secretă, cum ar fi „discul cu orificii”, „bastonul cu panglica scitală”. Istoricul grec Polibiu, martor ocular la al treilea război punic (149-146 î.e.n.), prezintă în lucrarea sa „Istoria generală” următorul sistem de cifrare: un pătrat conține literele grecești și are numerotate liniile și coloanele. Fiecare literă se codifică prin două cifre date de numerele de linie și coloană ale celulei în care se află. Roma antică a folosit „cifrul lui Cezar” în transmiterea mesajelor. Principiul substituției (fiecare literă este înlocuită cu cea aflată la o distanță de 3 în alfabetul latin), ce stă la baza acestui cifru, s-a menținut nealterat aproape două milenii.

Criptografia clasică

Societatea feudală timpurie, ridicată pe ruinele Imperiului roman, nu a favorizat dezvoltarea științei și culturii. Descoperirea tiparului în jurul anului 1440 a dat un nou impuls preocupărilor umane pentru dezvoltarea criptografiei.

În perioada Renașterii umaniștii au studiat manuscrise ale autorilor antici și au redescoperit, printre altele, metodele de cifrare folosite în antichitate. Extinderea și amplificarea relațiilor diplomatice dintre diferitele state feudale au dat un nou avânt dezvoltării criptologiei. Curțile regale și statul papal dispuneau de criptologi și criptanaliști.

„Poligraphiae libri sex” este prima carte asupra criptologiei, a apărut în anul 1518 și descrie metoda de cifrare numită „tablou de transpoziție”, bazată pe transpoziții și substituții.

Giambattista della Porta scrie în anul 1563 lucrarea „De Furtivis Literarum Notis” în care prezintă drumul parcurs de criptologie, observații critice asupra metodelor folosite de predecesori și aduce contribuții personale la dezvoltarea criptologiei pe baza „tabelelor de frecvență a literelor”, propunând un nou procedeu de cifrare bazat pe transpoziții și substituții.

Vigenère scrie în anul 1586 cartea „Tratatul cifrurilor sau modalități secrete de a scrie” în care prezintă metode noi de cifrare bazate pe substituția polialfabetică.

Cardan (1501-1576), matematician italian, naturalist, medic renumit al epocii sale, a influențat și criptografia. În lucrarea „De rerum varietate” a conceput mărirea siguranței secretului prin schimbarea cheii la fiecare mesaj, utilizând mesajul însuți drept cheie de cifrare prin folosirea „grilei cu ferestre”.

Rossignol a fost primul criptolog profesionist din Franța și printre cei mai abili descifratori din Europa. El a contribuit la multe succese diplomatice și victorii în bătăliile purtate de Ludovic al XIII-lea și Ludovic al XIV-lea. A reușit să modifice modul de stabilire a corespondenței între elementele clare ale mesajului și cifruri, introducând două tipuri de corespondențe, numite „tabel de cifrare” și „tabel de descifrare”.

Maiorul Bazaries a contribuit în anii 1800 la dezvoltarea serviciului de cifrare al armatei franceze, a descifrat „Marele cifru” folosit de Ludovic al XIV-lea (a cărui cheie a fost mult timp pierdută), a inventat dispozitivul numit „cilindru de cifrare” prin care s-au pus bazele cifrării mecanizate. Perfecționarea mașinilor de cifrat este legată de nivelul de dezvoltare al științei și tehnicii din epoca respectivă. Primele mașini de cifrat erau construite din elemente simple, cum ar fi roți dințate, elevatori etc.

Constructorii mașinilor de cifrat au urmărit de-a lungul timpului două scopuri: mărirea siguranței în cifrare și simplificarea activității de cifrare. Dezvoltarea mecanizării a dus la apariția mașinilor de cifrat din ce în ce mai performante construite cu discuri, roți dințate, bare și puse în funcțiune manual sau prin intermediul unui arc.

Telegraful, folosit pvității de cifrare. Dezvoltarea mecanizării a dus la apariția mașinilor de cifrat din ce în ce mai performante construite cu discuri, roți dințate, bare și puse în funcțiune manual sau prin intermediul unui arc.

Telegraful, folosit pentru transmiterea unor volume mari de date în condițiile dezvoltării impetuoase a industriei și comerțului, a stimulat dezvoltarea criptografiei pentru transmiterea în secret a informațiilor în condiția unui trafic intens de mesaje.

Mașinile de tip telegraf au mărit ritmul cifrării până la viteza dactilografierii (150-200 litere/minut).

Radioul, folosit pentru transmiterea informațiilor secrete de natură militară și diplomatică începând cu perioada premergătoare Primului Război Mondial, a impus în anii 1920 introducerea unei metode noi în criptografie numită „bloc cu o singură utilizare”. Mașina Hagelin C-48 a fost construită la nivelul anilor 1940 și a fost utilizată de către armata americană în al doilea război mondial sub numele M-209. Construcția mecanică cu roți dințate, cutii, bare, mânere a mașinii M-209 evidențiază tehnici general valabile pentru elaborarea dispozitivelor de cifrare, combină textul clar, caracter cu caracter, cu un șir cheie (care este o secvență pseudo aleatoare derivată din cheie), obținându-se textul cifrat.

Mașinile cu rotor au fost folosite în perioada 1940-1950. Cele mai cunoscute modele: M-134 sau SIGABA (SUA), TYPEX (Anglia), ENIGMA (Germania). Componenta centrală este rotorul cu contacte electrice sau roata cablată. În perioada celui de-al doilea război mondial s-au produs mari acumulări cantitative în domeniul criptologiei (cifrarea și descifrarea mesajelor).

C. E. Shannon contribuie fundamental la saltul calitativ în dezvoltarea criptologiei prin două lucrări de referință: „The Matematical Theory of Communication” (Bell System Journal, iulie și octombrie 1948) și „Communication Theory of Secrecy Systems” (Bell System Journal, octombrie 1949). El reușește să evidențieze legătura dintre teoria informației și criptologie, dă o definiție abstractă a sistemului secret și-i stabilește structura matematică. Considera că problema decriptării criptogramelor interceptate este asemănătoare cu problema decodificării mesajului în prezența zgomotului. Demonstrează posibilitatea de a construi un sistem secret cu o mulțime finită de chei în care echivocul criptanalistului nu tinde către zero, chiar dacă volumul criptogramei tinde spre infinit.

Criptografia în epoca modernă

Având în vedere faptul că transmisia de date în Internet este neprotejată, a apărut necesitatea dezvoltării tehnicilor de criptare în direcția automatizării acestora si a implementării lor în rețele de calculatoare. Astfel, utilizarea unor algoritmi pentru criptarea informațiilor transmise va deveni principalul mijloc de rezolvare a problemelor de interceptare în rețele.

În descrierea unei transmisii de date prin rețea se obișnuiește să se numească generic "mesaj" un ansamblu de date trimis de un „emițător” unui „receptor”. Printr-o metodă de criptare, mesajele vor fi transformate, pe baza unei chei de criptare, astfel încât să poată fi înțelese doar de destinatar.

Dezvoltarea sistemelor criptografice cunoaște o cotitură semnificativă în epoca modernă, datorită următoarelor patru elemente

a) Utilizarea calculatorului electronic a permis potențarea gamei de instrumente folosite efectiv în execuția algoritmilor de cifrare. Folosirea unor chei de dimensiuni mai mari, au sporit rezistența la atacurile criptanalitice, datorită puterii de calcul mereu sporite Criptografia clasică asigura secretul mesajelor în principal prin nedivulgarea algoritmului (metodei) de criptare și complicarea lui combinând substituții și transpoziții. Criptografia modernă asigură secretul mesajelor prin folosirea unor chei de cifrare de dimensiuni mari frecvent schimbate, chiar dacă se cunoaște algoritmul de cifrare. Pe această idee se bazează Standardul american de cifrare a datelor DES (Data Encryption Standard) adoptat în 1977 și bazat pe criptografia simetrică.

b) Dezvoltarea rețelelor de calculatoare și a Internetului au impus dorința utilizatorilor (persoane, organizații economice și comerciale) pentru păstrarea secretului și siguranței poștei electronice, transferului electronic de fonduri, comunicațiilor și altor aplicații, ceea ce a dus la perfecționarea metodelor și algoritmilor de criptare.

c) Criptografia asimetrică sau cu chei publice aduce un principiu nou prin cercetările din 1976 ale lui Whitfield Diffie și Martin Hellman de la Universitatea Stanford-California.

Criptografia simetrică folosea o singură cheie, atât la cifrarea mesajului cât și la descifrarea lui. Trimiterea cheii de la emițătorul mesajului la receptorul lui, se realiza printr-un canal sigur (clasic: un curier, modern: prin telefon). Criptografia asimetrică folosește două chei diferite, una pentru cifrarea mesajului la emițător, cealaltă pentru descifrarea lui la receptor. Deoarece deducerea unei chei din cealaltă este imposibilă, una din chei poate fi făcută publică și poate fi folosită de către oricine pentru a transmite un mesaj cifrat; doar destinatarul care deține a doua cheie (secretă) poate descifra și utiliza mesajul. Autentificarea mesajelor poate fi asigurată prin tehnica cheilor publice. Datorită acestor avantaje, guvernul SUA dorește schimbarea standardului de cifrare a datelor, orientându-se în 1990 și 1991 spre metodele de cifrare asimetrică RSA (prezentă deja în domeniul industriei) și DSS (dezvoltată de Agenția Națională de Securitate a SUA).

d) Criptografia cu chei în custodie (Key Escrow Systems) este un concept nou pe care au încercat să-l impună în anii ‘90 agențiile statului pentru securitatea națională a SUA. Acest concept ar fi dus către elaborarea unui sistem care permitea agențiilor statului să decripteze legal mesajele transmise în rețelele de calculatoare ale unor firme, corporații și persoane. Conceptul reprezintă nucleul programului guvernamental Clipper (numit și EES – Escrowed Encryption Standard), care este integrat în programul Capstone. Motivațiile legale și sociale ale acestui „drept de ascultare” sunt discutabile și au dus la tensiuni între interesele publice (pentru protecția informațiilor) și interesele guvernamentale (pentru accesul la informațiile adversarilor). În prezent s-a ajuns la concluzia că este nevoie de mecanisme care să permită unei persoane autorizată accesul la informație, dar protejându-se informația în fața altor persoane.

În epoca modernă criptografia a devenit un domeniu de intense cercetări academice și nu numai.

Tradițional, criptografii foloseau algoritmi simpli asociați cu chei de securitate foarte lungi. Azi se urmărește crearea unor algoritmi de criptare atât de complecși încât să fie practic ireversibili, chiar dacă un criptanalist achiziționează cantități foarte mari de text cifrat. O altă caracteristică a criptografiei moderne constă în automatizarea tehnicilor clasice, prin folosirea unor dispozitive special concepute. Transpozițiile si substituțiile vor fi implementate cu circuite simple, de viteză mare, care vor fi conectate în cascadă astfel încât dependenta ieșirii de intrare devine extrem de complicată si dificil de descoperit.

În 1977, guvernul SUA a adoptat ca standard oficial pentru informațiile nesecrete un cifru produs si dezvoltat de IBM, numit DES (Data Encryption System), care a fost larg adoptat în industrie. DES este cel mai popular algoritm cu cheie secretă; el continuă să stea la baza unor sisteme folosite în mod curent. DES folosește (uzual) o cheie de 56 de biți. Aceasta a fost în cele din urmă adoptată în locul uneia de 128 de biți, neagreată de NSA (National Security Agency), agenția „spărgătoare de coduri a guvernului”, care dorea supremația în domeniul criptografic.

Din 1977, cercetătorii în criptografie au încercat să proiecteze mașini pentru a sparge DES. Prima asemenea mașină (1977) a fost concepută de Diffie si Hellman, avea nevoie de mai puțin de o zi iar costul ei a fost estimat la 20 de milioane de dolari. După aproape 2 decenii, costul unei astfel de mașini a ajuns la 1 milion de dolari iar timpul necesar spargerii codului a scăzut la 4 ore. Ulterior, s-au dezvoltat si alte metode, cum ar fi folosirea unui cip DES încorporat (loteria chinezească).

În scopul decriptării s-ar mai putea folosi mecanisme soft specifice (cum ar fi algoritmul asimetric Diffie-Hellman) si resursele libere ale unor calculatoare cu destinație universală. Astfel, s-a demonstrat că rularea pe mai multe calculatoare a unor programe distribuite de criptare (uzual, pe un număr mare de mașini, de ordinul miilor sau chiar zecilor de mii) creste considerabil eficienta procesului de decriptare.

Un alt cifru renumit este IDEA (International Data Encryption Algorithm), realizat de doi cercetători la Politehnica Federală din Zürich (ETHZ). Acest algoritm folosește o cheie de 128 de biți si este inspirat din metodele anterioare – DES si cele imaginate pentru spargerea DES.

Un alt algoritm performant a fost descoperit de un grup de cercetători de la MIT – Ronald Rivest, Adi Shamir, Leonard Adelman, și s-a numit cu inițialele creatorilor lui RSA. Algoritmul de criptare RSA folosește o cheie publică. Se observă că utilizarea unor astfel de algoritmi de criptare a datelor asigură transmisii confidențiale de date în rețele neprotejate, rezolvând problema interceptării. De fapt, riscul de interceptare / modificare nu dispare cu totul, din cauză că orice mesaj criptat poate fi în general decriptat fără a deține cheia corespunzătoare, dacă se dispune de suficiente resurse materiale si de timp.

Evident, dimensiuni variate ale cheii asigură diferite grade de confidențialitate iar perioada de timp necesară pentru decriptare poate fi prevăzută în funcție de mărimea cheii utilizate. Totuși, dacă procesul de decriptare este lent, este posibil ca în momentul în care s-ar obține datele dorite, acestea să nu mai fie actuale sau utile.

Timpul de decriptare depinde în mod natural si de puterea procesoarelor utilizate în acest scop, astfel încât utilizarea distribuită a unui foarte mare număr de procesoare poate duce la o micșorare considerabilă a timpului necesar. Din acest motiv, pentru transmisii de date în care este necesară o confidențialitate strică se utilizează chei de dimensiuni mult mai mari, chiar pentru algoritmul DES (de 256, 512, 1024 si chiar 2048 sau 4096 de biți), știut fiind că timpul necesar decriptării crește exponențial cu dimensiunea cheii de criptare / decriptare.

Pentru utilizatorii obișnuiți ai Internet-ului, cei mai convenabili algoritmi de criptare sunt cei cu cheie publică fiindcă folosirea lor nu implică schimbul preliminar de chei pe canale de transmisie protejate, ca în cazul algoritmilor cu cheie secretă. Cheia publică poate fi distribuită fără restricții pe intranet (rețeaua locală) sau Internet, iar mesajele criptate cu această cheie de un emițător vor putea fi decriptate numai utilizând cheia privată, care este deținută exclusiv de către destinatar. Astfel, nici măcar expeditorul nu ar putea realiza decriptarea mesajului trimis.

1.3 Tipuri de criptografie

Criptografia se folosește pentru securizarea comunicațiilor. Ea ar trebui sa aibă următoarele proprietăți:

Confidențialitate: doar un receptor autorizat al mesajului ar trebui sa fie capabil sa extragă conținutul mesajului din forma sa criptată. Altfel, nu ar trebui sa fie posibil sa se obțină vreo informație semnificativă despre conținutul mesajului.

Integritate: destinatarul ar trebui să poată detecta dacă mesajul a fost modificat în cursul transmisiei.

Autentificare: destinatarul ar trebui să poată să-l identifice pe expeditor, și să verifice că presupusul expeditor într-adevăr a transmis mesajul.

Nerepudiere: expeditorul nu ar trebui să poată nega că a transmis mesajul.

Protecție la trimitere multiplă: mesajului nu ar trebui să-i fie permisă trimiterea multiplă la destinatar fără ca expeditorul să știe acest lucru.

Criptografia poate asigura mecanisme pentru a atinge obiectivele de mai sus. Totuși, unele scopuri nu sunt întotdeauna necesare, practice sau dezirabile în anumite contexte. De exemplu, expeditorul unui mesaj ar vrea sa rămână anonim, și în acest caz, nerepudierea ar fi nepotrivită.

Există două mari categorii de cifruri, una cu cheie simetrică și una cu cheie asimetrică.

Criptografia cu cheie simetrică (privată)

Unul din principiile mai recent apărute în criptanaliză constă în utilizarea unei alte chei pentru decodificarea mesajului decât cea folosită la codificare. Această tehnică este mai eficientă dar complică puțin procedeul general si de aceea se preferă când criptarea / decriptarea se realizează automat. Evident, dimensiunea unei chei de criptare (exprimate în general în biți) este o măsură a nivelului de securitate dat de acea cheie, ea indicând rezistenta mesajului cifrat la încercările de descifrare de către cineva care nu deține cheia de descifrare potrivită.

Principiile de criptare din algoritmii cu cheie secretă au evoluat odată cu apariția calculatoarelor; ele continuă însă să se bazeze pe metodele tradiționale, cum ar fi transpoziția si substituția. Algoritmii cu cheie secretă sunt caracterizați de faptul că folosesc aceeași cheie atât în procesul de criptare, cât si în cel de decriptare, ca in figura de mai jos. Din acest motiv, acești algoritmi mai sunt cunoscuți sub numele de algoritmi simetrici; pentru aplicarea lor este necesar ca înaintea codificării / decodificării, atât emițătorul cât si receptorul să posede deja cheia respectivă. În mod evident, cheia care caracterizează acești algoritmi trebuie să fie secretă.

Principalul dezavantaj al algoritmilor simetrici constă în faptul că impun un schimb de chei private înainte de a se începe transmisia de date. Altfel spus, pentru a putea fi utilizați, este necesar un canal cu transmisie protejată pentru a putea fi transmise cheile de criptare / decriptare.

Figura 1.1

Schema de aplicare a unui algoritm simetric

Cifrurile cu cheie simetrică folosesc aceeași cheie pentru criptare si decriptare (sau cheia pentru decriptare este relativ ușor de calculat din cheia pentru criptare). Mai este numita si criptografie cu cheie privată.

Cifrurile cu cheie simetrică pot fi clasificate în cifruri bloc și cifruri secvențiale. Cifrurile secvențiale criptează informația bit cu bit, spre deosebire de cifrurile bloc, care criptează succesiv din mesaj blocuri de biți de o anumita lungime. Între cele două categorii există o dualitate, în sensul că pot fi făcute să opereze într-o manieră asemănătoare categoriei opuse. Ca exemple de cifruri bloc se cunosc: DES, 3DES, IDEA, AES, iar de cifruri secvențiale: RC4, A5/1, A5/2.

Există de asemenea unele primitive criptografice care pot fi desemnate ca fiind criptografie simetrică.

Un exemplu îl constituie funcțiile hash criptografice, care produc un „rezumat” (hash) al mesajului. În timp ce sunt foarte ușor de calculat, ele sunt foarte greu de inversat (one-way). Astfel, cineva trimite un mesaj și îi calculează hash-ul, apoi trimite mesajul împreuna cu hash-ul către receptor. Receptorul primește mesajul și calculează la rândul lui hash-ul. Dacă cele doua valori diferă, înseamnă ca mesajul a fost modificat. Este practic imposibil ca un intrus care interceptează mesajul să-l modifice astfel încât aplicarea funcției de hash să dea aceeași valoare cu valoarea inițiala. Exemple binecunoscute de astfel de funcții de hash sunt MD5 și SHA-1.

Criptografia cu cheie asimetrică (publică)

Ulterior, vor apărea și algoritmi cu cheie publică, caracterizați prin faptul că criptarea si decriptarea folosesc chei diferite ca în Figura 1.2. Această caracteristică a dat algoritmilor cu cheie publică și numele de algoritmi asimetrici. În acest caz, una dintre chei poate fi publică (general cunoscută – poate fi distribuită oricui) iar cealaltă va trebui să fie privată / secretă (cunoscută doar de cel care o folosește). Fiecare dintre aceste chei poate cripta mesajul, dar un mesaj criptat cu o anumită cheie nu poate fi decriptat decât cu cheia sa pereche.

Astfel, în cazul utilizării unui algoritm asimetric în comunicarea dintre un emițător si un receptor, fiecare dintre aceștia va deține câte o pereche de chei – publică si privată. Emițătorul poate cripta mesajul cu cheia publică a receptorului, astfel încât doar acesta să poată decripta mesajul cu cheia sa privată. În cazul unui răspuns, receptorul va utiliza cheia publică a emițătorului astfel încât decriptarea să se poată face exclusiv de către emițător (cu cheia sa pereche, privată).

Cheile algoritmilor asimetrici sunt obținute pe baza unei formule matematice din algebra numerelor mari, pentru numere prime între ele, iar din valoarea unei chei nu poate fi dedusă valoarea cheii asociate. Remarcăm faptul că aplicarea în informatică a calculelor modulo numere prime s-a dovedit extrem de benefică pentru mulți algoritmi moderni.

Figura 1.2

Schema de aplicare a unui algoritm asimetric

Criptarea cu cheie simetrică are un deficit care provoacă probleme serioase. De exemplu doi oameni care doresc să schimbe între ei mesaje confidențiale trebuie să partajeze o cheie secretă. Cheia trebuie transmisă într-un mod sigur, și nu prin mijloacele prin care ar comunica în mod normal. Acest lucru de obicei nu este convenabil, și criptografia asimetrica sau cu cheie publica asigură o alternativă. În criptografia cu cheie publică se folosesc doua chei, o cheie publică si o cheie privată. Cheia publică este folosită pentru criptare, iar cea privată pentru decriptare.

Trebuie să fie foarte dificil să se deducă cheia privată din cheia publică. Aceasta înseamnă că o persoană poate trimite fără nici o problema cheia publică printr-un canal de comunicații nesigur, și totuși să fie sigură că doar ea va putea decripta mesajele criptate cu ajutorul ei.

Algoritmii cu cheie publică se bazează de obicei pe probleme matematice dificil de rezolvat. RSA, de exemplu, se bazează pe dificultatea factorizării unui număr foarte mare. Mai este folosita si criptografia bazată pe curbe eliptice, care poate fi mai eficientă.

Din rațiuni de eficientă, în practică se folosesc sisteme de criptare hibride. Cu ajutorul unui cifru cu cheie publică se transmite o cheie între cei doi parteneri de comunicație, iar restul comunicației va fi criptat folosind un algoritm cu cheie simetrică, care este de obicei mult mai rapid.

Criptografia asimetrica oferă mecanisme pentru semnăturile digitale, care sunt un mod de a stabili cu un grad mare de încredere ( presupunând ca nu s-a compromis în vre-un fel cheia privata relevantă ) ca mesajul receptionat a fost trimis de utilizatorul care a pretins acest lucru. Aceste semnături sunt văzute adesea, conform legii sau prin deducție, ca fiind echivalentul digital al semnăturilor fizice de pe documentele de hârtie. În sens tehnic, ele nu sunt, deoarece nu există nici contact fizic, nici conexiune fizică între cel care semnează și documentul semnat. Dacă se folosesc în mod adecvat sisteme cu o concepție și implementare de înaltă calitate, se pot obține grade foarte înalte de încredere, depășind probabil semnăturile fizice. Exemple de protocoale de semnături digitale sunt DSA si ElGamal. Semnăturile digitale sunt de baza pentru operarea PKI (Public Key Infrastructure) si a multor scheme de securitate în retea ( Kerberos, cele mai multe VPN-uri, etc). Ca și la criptare, se pot folosi în practica algoritmi hibrizi, se poate semna un hash criptografic al documentului, în locul documentului întreg.

1.4 Comparație între criptarea simetrică și cea cu cheie publică

Avantaje ale sistemelor de criptare cu cheie simetrică

Pot transmite volume mari de date. Există implementări hard care pentru unele sisteme de criptare pot asigura rate de criptare de sute de mega-octeți pe secundă, sunt și implementări soft cu rate de mega-octeți pe secundă, deci are avantajul vitezei.

Cheile sunt relativ scurte.

Pot fi folosite ca bază de construcție a diverselor mecanisme de criptare, cum ar fi generatori de numere pseudo-aleatoare, generatori de funcții de dispersie, scheme de semnătură.

Prin compunere pot conduce la sisteme de criptare puternice.

Au o istorie bogată în evenimente și experiență.

Dezavantaje ale sistemelor de criptare cu cheie simetrică

Cheia trebuie să rămână permanent secretă în cel puțin două locuri distincte.

Cu cât lungimea unui mesaj criptat este mai mare, cu atât el este mai ușor de spart.

În rețele mari, o gestionare a cheilor devine extrem de dificilă.

Necesită un canal sigur de comunicare, cel puțin pentru transmiterea cheii. Acest lucru devine dificil mai ales pentru sistemele care necesită schimbări frecvente ale cehilor de criptare sau de decriptare.

Avantaje ale sistemelor de criptare cu cheie publică:

Sistemul este ideal pentru transmiterea informației prin canale nesigure.

Sistemele cu cheie publică asigură identitatea. Dacă o persoana X criptează un mesaj cu o cheie privată și transmițându-l unei persoane Y, aceasta îl poate decripta cu o cheie publică putem spune că Y are certitudinea că mesajul vine de la X.

Sistemele cu cheie publică sunt simplu de definit și elegante matematic.

Doar cheia de decriptare trebuie ținută secretă, la un singur punct (destinatar).

În funcție de modul de utilizare, o pereche de chei (publică,privată) poate fi păstrată o perioadă mai lungă de timp.

Conduc la aplicații de mare întindere ca semnături electronice, algoritmi de autentificare, componente de comerț electronic etc.

Dezavantaje ale sistemelor de criptare cu cheie publică

Sunt semnificativ mai lente decât sistemele simetrice.

Sunt necesare chei de lungimi mult mai mari.

Nu se poate garanta securitatea absolută a nici unei scheme de criptare cu cheie publică.

Implementarea trebuie realizată cu foarte mare grijă. Sisteme cu grad ridicat teoretic de securitate pot fi sparte ușor printr-o implementare neglijentă.

După cum se observă, cele două clase de sisteme de criptare dispun de o serie de avantaje complementare. Acest lucru face ca ele să fie folosite combinat.

Capitolul II

SISTEME CRIPTOGRAFICE

2.1 Criptosisteme și criptanaliză

Criptografia, știință și artă, servește două lumi diferite: prima este lumea comunicațiilor autorizate cum ar fi cele dintre utilizatorii de drept ai aceleiași baze de date, operații desfășurate legal, și a doua cea a operațiilor ilegale, desfășurate din umbră, în care persoane neautorizate încearcă, prin diferite mijloace, să intercepteze mesaje sau să le altereze. Dezideratul persoanelor autorizate este ca mesajele să fie cât mai puțin inteligibile pentru „inamic”, în timp ce acesta dorește să descifreze aceste mesaje cât mai ușor.

Din acest punct de vedere criptografia reprezintă o luptă continuă între cele două lumi. Un succes al inamicului va conduce, întotdeauna, la întărirea măsurilor de siguranță întreprinse de utilizatorii autorizați. Aceasta constituie, la rândul său, o nouă provocare pentru inamic. Și, în acest fel, lupta continuă, de aceea rezultatele matematice definitive sunt puțin probabile în practica acestui domeniu.

Ori de câte ori se analizează un atac cu succes al inamicului, trebuie admis că metodele corespunzătoare din „lumea legală" nu au fost destul de sigure. Nu se poate pretinde succes din partea ambelor părți.

Un mesaj este transmis de un emițător printr-un canal nesigur, de-a lungul căruia el poate fi interceptat de un receptor neautorizat.

Figura 2.1

Desenul este identic, indiferent dacă e vorba de un curier poștal (diligență) sau de o poștă electronică. Nu se poate asigura securitatea canalului și, de aceea, orice interceptare este posibilă. Scopul esențial al inamicului este să violeze secretul comunicării și să beneficieze de conținutul acesteia. Pot exista și scopuri mai sofisticate. De pildă, inamicul poate dori să modifice mesajul, intoxicând astfel destinatarul cu mesaje false. În acest mod, inamicul poate înșela receptorul chiar și asupra identității emițătorului. De exemplu, emițătorul poate transmite mesajul: „I will give no suport to the Greens” (Nu voi sprijini Verzii). Dacă inamicul alterează acest mesaj și-l transformă în: „I will give Ș10 100 to the Greens” (Voi dărui 10 100$ Verzilor), receptorul nu are nici o idee privind identitatea emițătorului acestui mesaj esențial diferit. De asemenea, inamicul poate deruta emițătorul privind identificarea receptorului prin captarea întregului mesaj și împiedicarea receptării lui de către destinatar.

În toate aceste cazuri, atât pentru emițător cât și pentru receptorul legal este un mare avantaj ca inamicul să nu înțeleagă mesajul după interceptarea lui. În acest scop, vor fi folosite diferite metode de criptare.

Mesajul în forma sa originală, numit text clar sau plaintext din limba engleză, se poate prescurta pt. Deci emițătorul criptează textul clar, iar rezultatul obținut numit criptotext, este prescurtat ct. Acesta este transmis printr-un canal neprotejat. În final, receptorul îl decriptează, obținând textul clar inițial. În cocluzie, activitatea emițătorului este criptarea textului clar în criptotext, iar activitatea receptorului este decriptarea criptotextului în text clar .Se poate folosi următoarea exprimare simbolică scurtă:

E(pt) = ct și D(ct) = pt

În literatură, în loc de „text clar” și „criptotext” sunt adesea utilizați termenii „text inițial” și „text cifrat” și, de asemenea, „cifrare” și „descifrare” în loc de „criptare” și „decriptare”. Și termenul „cod”, cu operațiunile corespunzătoare, „a codifica” și „a decodifica”, a fost destul de mult utilizat, dar nu și în ultimul timp, deoarece cuvântul „cod” este folosit și cu alte semnificații: coduri detectoare de erori, coduri în sensul teoriei automatelor etc. În continuare, se va utiliza cuvântul „cod" într-un context special, dar nu în sensul general de „criptotext”.

Mai departe, se prezintă analiza criptării și decriptării, privite ca operații de translatare în cadrul unui criptosistem. Un criptosistem se compune din următoarele elemente:

Spațiul textului clar, PT, adică mulțimea tuturor textelor clare pi posibile.

Spațiul cheii, K. Fiecare cheie k din K determină o metodă de criptare Ek și una de decriptare Dk. Dacă Ek se aplică unui text clar pt, se obține criptotextul ct, căruia, aplicându-i-se Dk, va rezulta pt .

Spațiul criptotextului, CT, adică mulțimea tuturor criptotextelor ct posibile. Elementele lui CT rezultă din elementele lui PT prin aplicarea metodei de criptare Dk, unde k aparține domeniului K.

Se va folosi în continuare termenii de codificare și decodificare pentru traducerea mesajelor, când nu se urmărește și ascunderea înțelesului acestora. O codificare poate fi necesară, de exemplu, în procesul transmiterii mesajului. Atunci, mesajul este mai întâi codificat si apoi cifrat. Bineînțeles, redundanța limbajului natural nu este afectată de codificare.

În cele ce urmează vor apărea mai multe exemple de criptosisteme. Se începe cu unul foarte vechi și nu prea grozav, criptosistemul CAESAR. Mai multe variante ale acestuia au fost folosite în diferite perioade. Nu este esențială alegerea spațiului textului clar. Sistemul CAESAR se bazează pe substituții, și anume fiecare literă este înlocuită cu o alta, obținută din prima prin avansarea în alfabet cu k pași, sfârșitul alfabetului completându-se ciclic cu literele de la început. Deci, pentru k = 3, substituțiile sunt următoarele:

Vechi: A B C D … W X Y Z

Nou: D E F G … Z A B C

Astfel, textul clar TRY AGAIN devine WUB DJOLQ. Prin urmare, spațiul cheii pentru sistemul CAESAR constă din 26 numere 0, l, 2 …, 25. Metoda de criptare Ek determinată de cheia k este avansarea cu k pași în alfabet. Corespunzător, metoda de decriptare Dk este parcurgerea înapoi cu k pași în alfabet.

Exemplul 2.1:

În textul de bază fiecare literă, notată cu P, este înlocuită cu litera aflată la 3 poziții la dreapta față de aceasta notată cu C. Astfel, litera A devine D, litera X se transformă în A, Y devine B, etc. Transformarea se poate scrie ținând cont de echivalenții numerici ai literelor astfel:

C≡P +3(mod 26), 0 ≤ C ≤ 25

Se presupune că textul de bază este:

THIS MESSAGE IS TOP SECRET

Pentru început, textul de bază se împarte în blocuri de 5 litere

THISM ESSAG EISTO PSECR ET

care apoi sunt înlocuite cu echivalenții lor numerici:

19 7 8 18 12 4 18 18 0 6 4 8 18 19 14 15 18 4 3 17 4 10

Fiecare echivalent numeric este transformat după regula precizată și rezultă:

22 10 11 21 15 7 21 21 3 9 7 11 21 22 17 18 21 7 6 20 7 13

Blocurile nou construite sunt transformate în litere corespunzătoare echivalenților numerici:

WKLVP HWDJ HLVWR SVHGU HW

care formează textul cifrat.

Pentru decifrare, se folosește transformarea inversă

P≡C −3(mod26), 0 ≤ P ≤ 25

și se aplică același procedeu după care se refac din blocuri cuvintele inițiale.

Acest exemplu este un caz particular al criptosistemelor descrise prin transformările de forma

C≡P + k(mod 26), 0 ≤ C ≤ 25

Acestea se numesc transformări de deplasare. Cheia de cifrare este k. Fie acum transformarea definită prin

C≡aP +b(mod 26), 0 ≤ C ≤ 25,

unde a, b sunt numere întregi cu (a,26) =1. Se observă că pentru a exista φ(26) = 12 posibilități de atribuire și pentru b avem 26. Deci există 12 ∙ 26 = 312 astfel de transformări, printre care și transformarea identică, transformări numite transformări afine. Cheia de cifrare este dată de a și b.

(Implementarea se găsește la ANEXĂ).

Se remarcă faptul că transformările de deplasare sunt cazuri particulare ale celor afine obținute pentru a = 1. Procesul de criptare se desfășoară la fel ca în exemplul dat, numai că de această dată echivalenții numerici se modifică după noua relație. Pentru decriptare se folosește transformarea

P≡(C + b)(mod26), 0 ≤ P ≤ 25,

unde este inversul lui a modulo 26.

Cheia de decriptare Dk poate fi obținută imediat din cheia de criptare Ek. Pentru orice criptosistem, Dk se determină, în sens matematic din Ek. Totuși, determinarea lui poate să fie intratabilă.

În orice sistem clasic, Dk se obține imediat dacă se dezvăluie Ek , deci oricine care cunoaște pe Ek poate să-l calculeze pe Dk. Bineînțeles, calculul poate să nu fie atât de ușor ca și în cazul sistemului CAESAR, dar el poate fi de fiecare dată efectuat într-un timp rezonabil. În concluzie, Ek nu poate fi dezvăluit.

O caracteristică a criptosistemelor cu chei publice este faptul că Ek poate fi dezvăluită, fără a se compromite secretul. Cheile sunt abil construite, astfel încât deducerea lui Dk din Ek este o problemă intratabilă și, analog, calculul lui pt pentru Ek și Ek (pt) date.

Persoanele care încearcă să decripteze ilegal criptotextele vor fi numiți criptanaliști. Spre deosebire de situația receptorului autorizat, criptanalistul trebuie să se descurce fără să cunoască cheia Dk, scopul fiind același, adică găsirea textului clar.

Exemplificarea din Figura 2.1 poate fi acum prezentată mai detaliat, așa cum se vede în Figura 2.2.

Figura 2.2

Emițătorul, respectiv receptorul cunoaște dinainte pe Ek, respectiv Dk. De exemplu, este posibil ca cele două părți să fi căzut de acord asupra acestor chestiuni într-o întâlnire anterioară. Detaliile acestui acord depind de criptosistemul folosit.

Procedura este esențial diferită la criptosistemele clasice față de cele cu chei publice. Se observă că, pentru orice cheie k și orice text clar pt, avem:

Dk Ek(pt) = Dk(ct) = pt

Principiu care este și regula de aur pentru proiectanții de criptosisteme este că niciodată nu trebuie subestimați criptanaliștii. Această regulă se referă la toate activitățile de criptanaliză, precum spionarea prealabilă, metodele de atac, calculul efectiv etc. În ce privește cercetarea prealabilă, se va considera ipoteza că criptanalistul, cunoaște criptosistemul folosit. Acest lucru este plauzibil, deoarece, chiar dacă criptanalistul trebuie să încerce câteva criptosisteme, complexitatea procedurii este esențial aceeași ca și pentru un singur criptosistem.

Chiar dacă criptanalistul cunoaște criptosistemul, el nu știe cheia utilizată. Dar, dacă numărul cheilor posibile este mic, ca în cazul sistemului CAESAR, atunci pot fi încercate toate cheile, criptanalistul dispunând de excelente posibilități de calcul. Aceasta înseamnă că, în practică, un criptosistem cu un număr mic de chei este inutilizabil. Asemenea sisteme sunt totuși utile pentru ilustrarea unor aspecte specifice, cum este și cazul de față.

Condiția esențială ca un criptosistem să fie bun este ca el să nu permită obținerea textului clar pt din criptotextul ct, fără cunoașterea metodei de decriptare Dk. În continuare sunt detaliate patru din ipostazele inițiale în care se poate afla criptanalistul, cu mențiunea că ele pot fi modificate sau chiar combinate. De asemenea, nu trebuie uitat că criptanalistul cunoaște criptosistemul folosit.

Cazul 1. Criptanalistul dispune numai de criptotext. În acest caz criptanalistul are la dispoziție doar eșantioane de criptotext, care cu cât sunt mai lungi, cu atât este mai bine. În cazul sistemelor simple, de exemplu, CAESAR, chiar o mostră scurtă va fi suficientă, deoarece o singură cheie va produce un text clar cu semnificație. În sistemele mai complicate sunt necesare eșantioane mai lungi de criptotext. Metode criptanalitice eficiente se bazează pe informații statistice privind limbajul textului clar, de exemplu, informații privind frecvența individuală a literelor din limbă respectivă.

Cazul 2. Criptanalistul dispune și de textul clar. Criptanalistul cunoaște dinainte unele perechi (pt, Ek(pt)). Cunoașterea unor astfel de perechi poate ajuta în mod esențial analiza criptotextului dat, ct. Un exemplu foarte simplu este iarăși CAESAR deoarece orice pereche de orice lungime furnizează imediat cheia.

Cazul 3. Criptanalistul dispune de text clar special ales. Din nou criptanalistul cunoaște dinainte unele perechi (pt, Ek(pt)), numai că de data aceasta pt a fost ales de criptanalist. Atunci când acesta poate emite și verifica unele ipoteze asupra cheii este clar că situația sa este esențial mai bună în acest caz decât în Cazul 2. Pe de altă parte, cazul ecesta este posibil să se realizeze cel puțin atunci când criptanalistul are posibilitatea să pretindă că este un utilizator autorizat al sistemului în discuție.

Cazul 4. Criptanalistul deține cheia de criptare. Cunoscând metoda de criptare Ek, criptanalistul încearcă să găsească metoda de decriptare Dk corespunzătoare, înainte de a primi vreun eșantion de criptotext. Aceasta este situația tipică pentru criptosistemele cu chei publice. Metoda de criptare Ek poate să fie făcută publică cu mult timp înainte de a fi utilizată pentru criptarea unui mesaj important. Deci, criptanalistul dispune de suficient timp pentru preprocesare și orice informație ce se poate obține în intervalul în care „timpul este ieftin" este deosebit de importantă.

În unele criptosisteme cu chei publice nu este posibilă aflarea lui Dk doar prin cunoașterea lui Ek din lipsă de mijloace de recunoaștere a variantei corecte Dk din mai multe posibile. În alte criptosisteme cu chei publice Dk poate fi dedusă din Ek printr-o șansă deosebită, de exemplu, prin ghicirea a două numere prime mari din produsul lor.

2.2 Sisteme monoalfabetice

În acest subcapitol sunt prezentate criptosistemele clasice, sau cu cheie sectretă în contrast cu criptosistemele cu chei publice. Diferența dintre cele două tipuri de criptosisteme este că în criptosistemele clasice, cheia de decriptare Dk poate fi ușor dedusă din cheia de criptare Ek, pe când în criptosistemele cu chei publice, Ek poate fi făcută publică fără grijă, acest lucru necompromițând secretul lui Dk. Din această cauză, sistemele clasice sînt referite adesea drept simetrice sau cu dublu sens, iar cele cu chei publice ca nesimetrice sau cu sens unic.

Cerința din Cazul 3 care spune că pentru ca un criptosistem să fie bun, criptotextul nu trebuie să trezească bănuieli, el trebuie să aibă un aspect cât se poate de inofensiv. Această cerință este vizibil depășită, nu mai este atât de importantă întrucât atât textul clar, cât și criptotextul sunt astăzi o succesiune de biți, care arată cât se poate de inofensiv la prima vedere. Totuși în trecut această cerință a fost adesea luată în considerare. Cea mai bună metodă din acest punct de vedere este „infiltrarea cu impurități". Mesajul, criptat sau nu, este „împănat" cu diferite litere irelevante pentru semnificația mesajului propriu-zis, dar care fac ca întregul ansamblu să arate extrem de inofensiv.

Richelieu utiliza în acest scop foi de carton cu perforații. Numai literele vizibile prin perforații aveau semnificație. Evident, atât expeditorul cât și destinatarul utilizau cartoane identice. O astfel de cartelă este reprezentată în Figura 2.3. Are 7 linii și 10 coloane, acoperind, la o aplicare, o porțiune de text de 70 litere. Prin aplicări succesive se acoperă texte oricât de lungi. Decupările se află deci în pozițiile (l,8) (2,9) (3,6), (4,5), (4,6), (5,1), (5,6), (5,7), (5,9), (6,2), (6,10), (7,9) (7,10).

Figura 2.3

Următorul text arată ca o inocentă scrisoare de dragoste:

Tabel 2.1

Mesajul din tabel se traduce ca „te iubesc, mi-ai pătruns în suflet, dragostea mea va dura pentru totdeauna în hiperspațiu”. Totuși, aplicând cartela de mai sus, citim o comandă sinistră:

YOU KILL AT ONCE

care se treduce ca „omoară-1 imediat”.

Există multe clasificări ale criptosistemelor, iar principiile de clasificare nu se referă atât la calitatea criptosistemelor (bun sau rău), cât mai degrabă la caracteristici intrinsec legate de proiectarea lor.

O foarte veche clasificare le împarte în sisteme cu substituție și sisteme cu permutare sau transpoziție.

În primul tip dintre acestea, literele textului clar sunt înlocuite cu substitute, acestea păstrând în textul criptat aceeași ordine cu corespondentele lor din textul clar. Dacă folosirea substitutelor este uniformă de-a lungul întregului text, atunci criptosistemul se numește monoalfabetic. Acest termen reflectă ideea existenței unei singure secvențe de litere de substituție. Fiecare literă a textului clar este reprezentată peste tot de același substitut. Dacă textul clar face parte dintr-un limbaj natural, criptanaliza poate avea la bază frecvența statistică a literelor din alfabetul respectiv.

În criptosistemele cu permutare (sau transpoziție) literele textului clar sunt rearanjate. Permutarea literelor fiind o metodă simplă și ușor de descifrat, ea trebuie combinată cu alte idei.

Exemplul următor conține un caz de sistem cu permutare. Textul clar este divizat în blocuri de câte trei litere. În fiecare bloc, literele sunt permutate astfel încât prima literă devine a treia, iar a doua și a treia fac un pas înapoi. Pentru edificare să luăm următorul exemplu:

LETUSGOTOFRANCE

Care se traduce „hai în Franța!”. Se reamintește faptul că s-a ignorat spațiile dintre cuvinte. Textul devine

ETLSGUTOORAFCEN.

Abordarea sumară a problemei scapă din vedere câteva chestiuni importante, de fapt, multe sunt de spus despre sistemele monoalfabetice. Problema crucială privește gestiunea cheilor. Totul se prăbușește dacă se cunoaște corespondența dintre litere si substitutele lor, deci cheia. În consecință, cheia nu trebuie să fie disponibilă nicăieri, nici în forma scrisă, nici în memoria unui calculator. Ea trebuie să fie memorată atât de expeditor, cât și de destinatar. Modul în care se realizează gestiunea cheilor determină tipul sistemului monoalfabetic.

Se consideră ca exemplu sistemul CAESAR. Substitutul unei litere se obține prin translatarea sa în față cu k pași în alfabet, în sistemul CAESAR și în alte sisteme similare se folosește codificarea numerică naturală:

A B C D E F G H I J K L M

0 l 2 3 4 5 6 7 8 9 10 11 12

N 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

Numerotând literele de la 0 la 25, în CAESAR fiecare literă α devine α + k, calculele efectuându-se modulo 26. Nici codificarea și nici decodificarea din numere în litere nu au scop să cripteze mesajul.

Numărul cheilor posibile în CAESAR este foarte mic. Un alt mare dezavantaj, din punctul de vedere al securității, este acela că secvența substitutelor păstrează ordinea alfabetică. Doar poziția inițială se schimbă. Criptosistemele afine ce vor fi prezentate mai departe au eliminat acest dezavantaj.

Un criptosistem afin este determinat prin două numere întregi a și b, unde 0 ≤ a, b ≤ 25, și în plus, a și 26 sunt relativ prime între ele. Substitutul unei litere α va fi aα + b. Se lucrează, pentru ușurință, cu codurile numerice ale literelor, calculele făcându-se, evident, modulo 26.

De exemplu, dacă a = 3 și b = 5, atunci codurile numerice vor arăta astfel:

Tabel 2.2

Între litere, corespondența este următoarea:

Tabel 2.3

Textul clar:

NOTEVERYSTEAMBATHISSAUNA,

care se traduce ca „nu orice baie cu aburi este o saună” se criptează astfel:

SVKRQREZHKRFPIFKADHHFNSF.

Restricția ca a să fie relativ prim cu 26 asigură injectivitatea funcției f(α) = aα + b. Practicate acum câteva secole, sistemele afine sunt astăzi utilizate doar pentru ilustrarea metodelor criptografice de bază. O generalizare matematică naturală a lor o constituie criptosistemele polinomiale, care în locul funcției liniare f(α) = aα + b folosesc o funcție polinomială arbitrară. Cu toate acestea, sistemele polinomiale prezintă un interes criptografic foarte mic. Principala motivație sistemelor afine a fost gestiunea cheilor deoarece se dorește reprezentarea atât a cheii de criptare, cât și cea a cheii de decriptare, într-o formă cât mai compactă. Cheia constă întotdeauna dintr-o secvență de 26 litere. Reprezentarea polinomială ar putea fi la fel de complicată ca și reprezentarea secvenței propriu-zise.

În continuare este prezentat un alt sistem monoalfabetic, numit KEYWORD-CAESAR. Se alege mai întâi un număr k, 0 ≤ k ≤ 25, și un cuvânt sau o propoziție scurtă, numită cuvânt cheie. Toate literele cuvântului cheie trebuie să fie distincte.

Să luăm, de exemplu, cuvântul cheie

HOW MANY ELKS (CÂȚI ELANI)

și numărul 8. Cuvântul cheie este scris sub alfabet, începând cu litera al cărei cod numeric a fost ales, în cazul nostru 8.

0 8 25

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

H O W M A N Y E L K S

Restul literelor sunt scrise în ordine alfabetică în continuarea cuvântului cheie:

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

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

Pe baza acestui tabel de corespondență textul:

ERROLFLYNN

se criptează ca

UKKYMVMINN

Nu este necesar ca literele cuvântului cheie să fie distincte, dar se poate pur si simplu să se scrie acest cuvânt și fără repetiții. De exemplu, cuvântul cheie:

ENGLAND EXPECTS EVERY MAN TO DO HIS DUTY

adică „Anglia așteaptă de la fiecare bărbat să-și facă datoria” și numărul 2 generează:

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

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

Numărul cheilor în sistemul KEYWORD-CAESAR este mare. Deși poate fi imposibil să se găsescă cuvinte cheie pentru toate cele 26 permutări posibile ale literelor, acest lucru se poate face pentru subclase semnificativ de largi. În exemplul următor se descrie postura criptanalistului.

Exemplul 2.2:

Sistemul KEYWORD-CAESAR (posibil cu repetiții în cuvântul cheie) a fost utilizat pentru realizarea următorului criptotext, în care spațiile între cuvintele textului clar au fost, de asemenea, păstrate.

Tabel 2.4

Calculul frecvenței conduce la următoarea distribuție a celor 241 de litere folosite:

Tabel 2.5

Comparând numărul aparițiilor lui A cu cele din grupul mijlociu, putem observa că oricare din literele acestui grup poate substitui literele cu frecvență înaltă: E, T, A, O, N, I, S, R, H. Mai mult, literele din grupul cu frecvență mică nu aduc prea multe informații, în special din cauza lungimii scurte a textului.

Este evident că separatorii ușurează foarte mult sarcina criptanalistului. În cazul de față se evidențiază cât de periculoasă este păstrarea în criptotext a spațiilor din textul clar. Criptotextul conține două cuvinte de o singură literă T și Q. Ele trebuie să fie A și I. Cum T apare o singură dată și Q de trei ori, este probabil că T îl substituie pe I și Q pe A.

Aceasta devine aproape sigur după ce sunt privite numărul aparițiilor lui T și Q. Cuvântul de trei litere UPC apare de 7 ori, în timp ce alte cuvinte similare apar o singură dată. Rezultă că UPC este substitutul lui THE, concluzie confirmată de calculul frecvențelor. Din grupul literelor cu număr mare de apariții ne-au mai rămas următoarele: C, P, T, Q, U. Din cuvintele TU și TF care apar de două ori se deduce că F este S, iar din cuvântul UV, că V este O. Cuvântul VI și faptul că I este o literă frecventă probează că I este N. Presupunerea că I este R este respinsă de către cuvântul XVIUQTIF. După decriptarea a opt din cele nouă litere cu frecvență mare, mai avem o mulțime de cuvinte în criptotext doar cu o singură literă necunoscută. Aceasta ne conduce la decriptarea restului de litere una câte una. Tabelul de decriptare este:

Criptotext: 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

Text clar: L V E W P S K M N ? Y ? R U ? H A F ? I T O B C G D

Textul clar utilizând și semnele de punctuație va fi „I now define sauna. It is a closed space neated by a stove sufficiently big with respect to the volume of the space. The stove contains stones, usually on the top. To take a sauna it is also necessary that the stove is properly heated and that you have the facility of throwing water on the stones.”, care se traduce „Să definim sauna. Ea este un spațiu închis, încălzit cu o sobă corespunzătoare volumului încăperii. Soba conține pietre, de obicei în partea superioară. A face saună înseamnă să încălzești corespunzător pietrele și să le stropești cu apă.”

Tabelul de decriptare se transformă într-un tabel de criptare prin așezarea literelor textului clar în ordine alfabetică.

Text clar: 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

Criptotext: Q W X Z C R Y P T ? G A H I V E ? M F U N B D ? K ?

Deci cuvântul cheie este CRIPTOGRAFY GIVES ME FUN (Criptografia mă delectează), începând din poziția a patra. Literele J, Q, X, Z lipsind din textul clar trebuie să fie criptate ca O, S, J, respectiv L. În final, mai notăm că litera R, foarte frecventă în limba engleză, lipsește din grupa literelor cu număr mare de apariții în textul nostru clar.

Cele mai simple mijloace de apărare împotriva atacurilor bazate pe calculul frecvenței, sunt oferite de criptosistemul HOMOPHONES. Acest sistem nu mai este unul monoalfabetic, literele textului clar având mai multe substitute. Numărul substitutelor este proporțional cu frecvența literei. Deci, litera E a alfabetului englez ar trebui să aibă trei substitute pentru fiecare substitut al literei L și 123 pentru fiecare substitut al literei J. Criptarea unei astfel de litere se face atribuindu-i aleator unul dintre substitutele sale.

2.3 Sisteme polialfabetice

Spre deosebire de criptosistemele monoalfabetice, care utilizează aceleași substitute pentru un caracter în întreg textul clar, cele poliolfabetice folosesc substitute diferite în părți diferite ale textului. Dar ramâne de văzut dacă substitutele sunt atribuite literelor individuale sau, perechilor de litere. Evident, a vorbi de. litere sau de perechi de litere substituite este o problemă de convenție. Dacă substitutul unei perechi este același în tot textul, sistemul este monoalfabetic.

În cazul sistemelor momoalfabetice, există exemple în care fiecare literă este considerată împreună cu substitutul său. Există și criptosisteme bazate pe substituirea perechilor de litere, unde substitutul fiecărei perechi de litere rămâne neschimbat pe parcursul întregului text. Un astfel de sistem poate fi privit ca monoalfabetic „în sens larg". Ulterior vom dicuta și sisteme polialfabetice: acestea nu sunt monoalfabetice nici chiar în sens larg.

În continuare este discutat sistemul PLAYFAIR, numit așa după baronul Playfair de St. Andrews. Literele alfabetului englez, fără J, sunt aranjate într-un careu 5 x 5, ca de exemplu:

S Y D W Z

R I P U L

H C A X F

T N O G E

B K M Q V

Careul servește ca bază de criptare și decriptare conform următoarelor reguli:

1) Textul clar este împărțit în blocuri a câte două litere fiecare. Mai mult, următoarele condiții trebuie satisfăcute:

nici un bloc nu conține două apariții ale aceleiași litere

lungimea textului este un număr par

Textul poate fi eventual modificat ca să satisfacă aceste cerințe, chiar dacă astfel vor fi introduse mici erori de ortografie. De exemplu, ALL MEN este un text clar legal cu următoarea diviziune AL LM EN, pe când KISS ME și WHERE ARE YOU nu corespund regulilor noastre. Primul are uri bloc cu literă dublă, iar celălalt are un număr impar de litere.

2) Știm că fiecare bloc al textului clar constă din două litere distincte. Criptarea unui astfel de bloc, utilizând careul, se face în felul următor: dacă cele două litere nu sunt pe aceeași linie sau coloană, de exemplu A și E, vom observa că acestea formează împreună cu F și O un dreptunghi în careul dat. Perechea AE va fi substituită cu FO, adică literele aflate în celelalte două colțuri ale dreptunghiului. Ordinea literelor din FO este determinată de condiția următoare: F și A sunt pe aceeași linie, la fel O și E. Similar, EA este substituit prin OF, OF prin EA, SV prin ZB, RC prin IH și TL prin ER. Dacă cele două litere sunt pe aceeași linie (coloană), corespondentele lor se află mutându-ne cu o poziție spre dreapta (respectiv, în jos) si considerând linia (respectiv, coloana) prelungită ciclic. Deci, HA va fi substituit prin CX, WX prin UG, CA prin AX, DM prin PD și RL prin IR.

De exemplu se dorește criptarea textului CRYPTO ENIGMA. Criptosistemul utilizat de forțele militare germane în cel de-al doilea război mondial a fost bazat pe mașina ENIGMA. Textul clar arată divizat astfel:

CR YP TO EN IG MA

Conform cu regulile stabilite CR trece în HI, YP în DI și IG în UN potrivit regulii dreptunghiului. Perechile TO și EN aflate pe aceeași linie vor trece în NG și respectiv TO. Și, în final, perechea MA aflată pe aceeași coloană trece în DO. Rezultă următorul text criptat

HIDING TO UNDO

care se traduce ca „Ascunzându-ne pentru a dezlega”. Careul este capabil să furnizeze cuvinte cu semnificație.

Se observă că, permutând ciclic liniile sau coloanele între ele, se obțin careuri echivalente. De exemplu, se verifică ușor că următorul careu:

P U L R I

A X F H C

O G E T N

M Q V B K

D W Z S Y

este echivalent cu cel inițial criptând orice text clar în același fel.

Regulile sistemului PLAYFAIR stabilite mai sus nu sunt singurele posibile. De exemplu, literele duble din textul clar pot fi despărțite printr-o literă anume, de exemplu Q. Dimensiunea 5 x 5 a careului poate fi schimbată cu 4 x 6 sau 3 x 9, cu modificarea corespunzătoare a dimensiunii alfabetului. De asemenea, o pereche aflată pe aceeași linie sau coloană poate fi substituită cu o pereche aflată imediat dedesubt, respectiv la dreapta, în mod ciclic.

Motivația esențială pentru sistemele de tip KEYWORD-CAESAR este gestiunea cheilor. În locul unei permutări arbitrare a celor 26 de litere, avem căi mai simple de reprezentare a cheii. Astfel de reprezentări se doresc și pentru sistemele PLAYFAIR, pentru a înlocui memorarea unui careu de 5 x 5 litere cu ceva mai simplu de reținut. Cuvintele cheie sunt utile și pentru sistemele PLAYFAIR. Se alegem un cuvânt cheie în care literele să nu se repete, și se începe constituirea careului folosind literele cuvântului cheie, urmate, în ordine alfabetică, de celelalte litere ale alfabetului, exceptând litera J.

De exemplu, cu cuvântul cheie HOW MANY ELKS vom obține următorul careu:

H O W M A

N Y E L K

S B C D F

G I P Q R

T U V X Z

Principiul ciptosistemelor polialfabetice constă în faptul că prima literă a textului clar este criptată într-un anumit fel, următoarea este criptată în alt principiu, și așa mai departe. Deci litera A de exemplu, poate fi criptată în mai multe feluri. Substitutele literei A și a celorlalte litere provin din mai multe alfabete. Acesta este un mijloc eficient de apărare, A neavând o reprezentare unică în criptotext.

Unul din cele mai vechi și mai cunoscute sisteme polialfabetice este sistemul VIGENÈRE, numit astfel după criptograful francez Blaise de Vigenère. VIGENÈRE este un sistem CAESAR în care cheile variază la fiecare pas. Un careu VIGENÈRE, ca acele din tabelul următor se utilizează frecvent în criptări și decriptări. Fiecare coloană poate fi privită ca un sistem CAESAR cu cheile 0,1,2…25. SE citește textul clar pe liniile careului și cheile CAESAR de pe coloane, acestea din urmă fiind exprimate de obicei sub forma unui cuvânt cheie.

De exemplu se dorește criptarea textul clar PURPLE cu cheia CRYPTO. Privind la intersecția liniei P cu coloana C se găsește R. Întregul text criptat va fi RLPEES. Același criptotext se obține dacă se schimbă rolul liniilor și al coloanelor în procesul de criptare. Pentru decriptare se caută pe coloana lui C linia ce conține litera R, la capătul ei găsindu-se P, litera textului clar, și așa mai departe. Cuvântul cheie se aplică de obicei periodic. De exemplu cheia CRYPTO, aplicată unui text cu 15 litere, va arăta:

CRYPTOCRYPTOCRY.

Tabel 2.5

Pătratul lui Vigenère

Bineînțeles, există și multe alte cazuri ușor de memorat ce pot servi ca bază pentru sistemele polialfabetice în aceeași manieră ca și careul VIGENÈRE. Unul din cele mai cunoscute este careul BEAUFORT, prezentat în tabelul următor, ale cărui linii sunt liniile careului VIGENÈRE scrise în ordine inversă. A primit numele după amiralul Sir Francis Beaufort, creatorul scării vitezei vânturilor. În timp ce în careul VIGENÈRE prima linie și prima coloană furnizează indicii coloanelor și respectiv, indicii liniilor, în cazul careului BEAUFORT, prima linie și ultima coloană servesc aceluiași scop.

Termenul general de periodic se referă la criptosistemele polialfabetice în care alfabetele substitutelor se reiau ciclic.

Tabel 2.6

Pătratul lui Beaufort

Dacă se cunoaște perioada, criptanaliza sistemelor polialfabetice se reduce la criptanaliza sistemelor monoalfabetice în maniera următoare. Se presupune că perioada este 5. Aranjăm literele criptotextului pe cinci coloane ca mai jos, nemerele indicând poziția literei în crtiptotext.

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

. . . . .

. . . . .

Apariția aceleiași litere de două ori în coloană reprezintă o aceiași literă în textul clar. Prin urmare este posibilă decriptarea fiecărei coloane printr-un singur calcul al frecvenței.

Criptosistemele periodice cu perioada necunoscută au fost considerate deosebit de tari până la apariția metodei F. W. Kasiski, în jurul anilor 1860, numele provenind de la criptanalistul german F. W. Kasiski. Această metodă stabilește perioada pe baza apariției aceluiași cuvânt în criptotext. Se consideră următoarea situație:

…PUXUL 15 litere PUXUL.

Apariția poate fi pur accidentală sau datorată faptului că aceeași porțiune de text a fost criptată începând cu aceeași porțiune a cheii. Aceasta înseamnă că distanța dintre doi P, care este de 20, este un multiplu al lungimii cheii. Deci lungimea cheii este 2,4,5,10 sau 20. După ce mai multe asemenea propuneri asupra lungimii cheii au fost formulate, o parte dintre ele putând fi incorecte, lungimea cheii poate fi destul de bine identificată. Cu cât cuvintele care se repetă sunt mai lungi, cu atât este mai bine. De asemenea este și mai avantajoasă apariția repetată a aceluiași cuvânt.

Capitolul III

CRIPTARE CU CHEIE PUBLICĂ

3.1 Infrastructura cheilor publice (PKI)

Electronic, confidențialitatea unui mesaj se asigură prin criptarea acestuia cu o cheie secretă și un algoritm asociat. Versiunea criptată a mesajului poate fi citită de destinatar numai dacă acesta posedă cheia secretă și algoritmul de criptare. Problema esențială a majorității aplicațiilor de criptografie este păstrarea secretului acestor chei. Criptografia bazată pe chei publice rezolvă această problemă înlocuind cheia secretă cu o pereche de chei – una privată iar cealaltă publică.

Infrastructura cheilor publice este o combinație de produse hardware și software, politici și proceduri care asigură securitatea de bază necesară astfel încât doi utilizatori, care nu se cunosc sau se află în puncte diferite de pe glob, să poată comunica în siguranță. La baza ei se află certificatele digitale, un fel de pașapoarte electronice ce mapează semnătura digitală a utilizatorului la cheia publică a acestuia. Aceste obiecte informaționale sunt cărămizile care stau la baza unei implementări cu chei publice și reprezintă mijlocul de identificare digitală a fiecărui subiect participant într-o relație derulată prin mijloace electronice.

O implementare de acest gen conferă o capabilitate, un atribut tehnologic și organizațional, nefiind un produs sau o aplicație în sine. Rolul său este acela de a crește valoarea sistemelor informatice existente, precum și de a crea posibilitatea implementării unor sisteme care să răspundă cerințelor în creștere ale societății informaționale.

Cheia utilizată trebuie să fie secretă ambelor părți, problema reprezentând-o managementul cheilor și menținerea lor secretă. Criptografia are la bază codificarea mesajelor, un bloc fiind substituit prin altul, respectând anumite reguli. Codificarea se poate realiza în mai multe moduri acestea având următoarele proprietăți comune:

atât intrările cât și ieșirile sunt reprezentate ca stream-uri de octeți

criptarea unei date se realizează cu ajutorul unei chei

decriptarea datei se realizează tot cu o cheie

Modul de funcționare

Criptografia bazată pe chei publice trebuie însoțită de un set de politici de definire a regulilor sub care sistemele de criptografie pot opera și de un set de proceduri care specifică modalitățile de generare, distribuție și utilizare a cheilor. Pe scurt, este nevoie de o infrastructură, denumită „infrastructura cheilor publice” , care stabilește cadrul funcțional, bazat pe standarde, pentru o mare varietate de componente, aplicații, politici și practici al căror scop este atingerea celor patru funcționalități principale: confidențialitatea, integritatea, autentificarea, non-repudierea.

Pentru a înțelege modul de funcționare este nevoie de cunoașterea unui alt algoritm și anume funcțiile hash. Acestea, spre deosebire de algoritmii de criptare și decriptare realizează doar funcția de criptare iar mesajul original nu va fi recuperat niciodată. În principiu, un mesaj are întotdeauna aceeași valoare după aplicarea funcției și este imposibil ca două mesaje oarecare să genereze aceeași valoare.

Pentru a putea construi cheia ce se utilizează în timpul transmisiei se apelează la o altă parte de încredere denumită autoritate certificatoare. Ea generează un certificat general ce generează o cheie publică. Cheia nu trebuie să conțină ambiguități, înglobând datele personale care apoi sunt împachetate și semnate.

Un certificat digital este un document ce conține patru componente mari:

cheie publică

informația ce leagă cheia publică de deținătorul ei

informația de validitate a certificatului

semnatura digitală

Din cele prezentate putem să observăm că: integritatea, confidențialitatea și nerepudierea sunt asigurate prin criptografia cheilor publice. Pentru aceasta trebuie însă să se știe cine generează certificatul, unde este stocată cheia și unde se găsesc certificatele. Un certificat digital bazat pe infrastructura cheilor publice asigură rezolvarea tuturor problemelor.

Componentele unei infrastructuri cu chei publice

Aceste componente sunt următoarele:

Autoritatea Certificatoare (CA): responsabilă cu generarea și revocarea certificatelor

Autoritatea Registratoare (RA): responsabilă cu verificarea construcției generate de cheile publice și identitatea deținătorilor.

Deținătorii de Certificate: oameni, mașini sau agenți software care dețin certificate și le pot utiliza la semnarea documentelor.

Clienții: ei validează semnătura digitală și certificarea de la o autoritate certificatoare.

Depozitele: stochează și fac accesibile certificatele și listele de revocare a certificatelor.

Politicile de securitate: definesc procesele și principiile de utilizare a criptografiei.

Dintre funcțiile realizate cu ajutorul infrastructurii cu cheie publică se poate menționa:

Înregistrarea: este un proces în care cel ce dorește să obțină un certificat de la CA își prezintă atributele sale. Acestea sunt verificate iar apoi se eliberează certificatul.

Certificarea: este procesul în care CA eliberează certificatul ce conține cheia publică subiectului apoi îl depune într-un depozit public.

Generarea Cheilor: în multe cazuri subiectul generează o pereche de chei în mediul său, înainte de a transmite cheia publică la CA pentru certificare. Dacă CA răspunde pentru generarea cheilor, acestea sunt oferite subiectului ca un fișier criptat.

Recuperarea Cheilor: în unele implementări ale infrastructurii cu chei publice necesită ca toate cheile schimbate și/sau criptate să fie depuse într-un depozit securizat. Ele sunt recuperabile dacă subiectul pierde cheia, acest lucru revenind lui CA sau sistemului de recuperare.

Actualizarea Cheilor: toate cheile perechi și certificatele lor asociate trebuie actualizate la un interval regulat. În acest sens există două situații care necesită acest lucru:

Data care este specificată în certificat ca dată de expirare este depășită și se actualizează.

Cheia privată a uneia din entități din PKI este compromisă. În acest caz PKI trebuie să anunțe că vechiul certificat nu mai este valid și urmează să-l înlocuiască. Una din căi este de pre-generare și stocare securizată a perechilor de chei pentru astfel de situații, acțiune ce duce la informarea fiecărui utilizator de acest lucru. Altă cale este metoda "out-of-band" unde cu ajutorul telefonului, faxului, scrisorii se transmite acea cheie.

Certificarea încrucișată: permite utilizatorilor dintr-un domeniu administrativ să utilizeze certificate generate de un CA operațional în alt domeniu. Procesul implică un CA (CA_1) ce oferă o certificare pentru alt CA (CA_2). Acest certificat conține cheia publică CA asociată cu cea privată pe care CA_1 o utilizează, lucru ce permite subiecților certificați prin CA_2 să accepte certificatele generate de CA_1 sau orice CA subordonat.

Revocarea: apare în momentul expirării perioadei de validitate care poate apărea când: subiectul își schimbă numele, angajatul părăsește compania, cheia privată este compromisă. În cadrul standardului X.509, pentru a revoca un certificat se utilizează lista revocărilor certificatelor. Această listă identifică certificate și sunt semnate de CA.

Avantajele infrastructurii cu cheie publică

În continuare sunt prezentate câteva din avantajele imediate pe care le aduce o implementare a unei infrastructuri cu cheie publică la nivel organizațional:

Securizarea mesageriei electronice. Cea mai mare parte a interacțiunilor derulate prin Internet se realizează prin intermediul mesageriei electronice. Această activitate presupune însă acceptarea unui grad ridicat de risc, prin expunerea unor informații confidențiale și prin posibilitatea substituirii autorului unui mesaj sau chiar alterarea voită a conținutului mesajului.

Sistem de administrare a documentelor și semnătură digitală. O parte importantă a aplicațiilor software se referă la procesarea și arhivarea documentelor în format electronic. Deși aceste sisteme contribuie la diminuarea dificultăților în prelucrarea și arhivarea unui volum mare de documente, ele nu rezolvă complet trecerea de la documente în format tradițional la documente electronice. Ceea ce lipsește este posibilitatea de a semna aceste documente electronice și de a asigura în acest fel non-repudierea acestora.

Securizarea aplicațiilor Intranet și Extranet. Din ce în ce mai multe companii și organizații tind să-și transfere procesele de interacțiune către aplicații care rulează în mediul Internet. Indiferent dacă acestea se referă la relația cu proprii angajați și procesele interne ale organizației (aplicații Intranet), sau sprijină interacțiunea cu partenerii și clienții (aplicații Extranet), aceste aplicații își demonstrează din plin eficiența prin reducerea masivă a costurilor și îmbunătățirea eficienței. Pe măsură însă ce aceste informații sunt transferate către sistemele și aplicațiile Intranet / Extranet, riscul de securitate informațională crește semnificativ, în primul rând datorită faptului că Internetul reprezintă prin natura sa un mediu public.

Criptarea datelor și a documentelor. Securitatea datelor nu se referă numai la momentul în care acestea sunt utilizate într-un proces informațional, ci și la stocarea lor. Păstrarea confidențialității și integrității acestora îmbracă numeroase aspecte, care se referă atât la autentificarea accesului cât și la criptarea lor astfel încât să nu poată fi utilizate în cazul unui acces neautorizat.

Autentificare la nivelul sistemului de operare și al aplicațiilor. Autentificarea prin nume și parolă este soluția cea mai vulnerabilă și în plus, obligă utilizatorul la memorarea unei astfel de combinații pentru fiecare aplicație folosită. Folosirea certificatului digital stocat pe „smartcard” contribuie nu numai la creșterea gradului de siguranță dar și la o utilizare mai facilă, prin folosirea unui mijloc unic de autentificare pentru toate aplicațiile folosite.

3.2 Considerații generale ale criptării cu cheie publică

Prin definiție, un criptosistem cu cheie publică are proprietatea că o persoană care știe doar să cifreze nu poate folosi numai cheia de cifrare pentru a găsi cheia de decifrare în timp util. Denumirea de „cheie publică" provine din faptul că informația necesară trimiterii de mesaje secrete (cheia de cifrare) poate deveni informație cunoscută de oricine fără ca să se permită citirea mesajelor secrete de către persoane neautorizate.

De remarcat este faptul că, folosind un sistem cu cheie publică, este posibilă realizarea unei comunicații secrete între două părți fără a avea un contact inițial, fără a stabili la început dacă au încredere unul în altul, fără să schimbe informații priorii.

În sistemele de criptare clasice, Alice și Bob își aleg o cheie secretă K care definește regulile de criptare eK și decriptare dK. În aproape toate cazurile, eK și dK coincideau sau se puteau deduce imediat una din alta. Astfel de sisteme sunt cele cu cheie privată (sau sisteme simetrice) deoarece publicarea lui eK face sistemul extrem de vulnerabil.

Un punct slab al sistemelor cu cheie privată este acela că necesită o comunicare prealabilă a cheii între Alice și Bob printr-un canal sigur, înainte de transmiterea mesajului criptat. Practic, în condițiile cererii tot mai mari de securizare a comunicațiilor, acest lucru este din ce în ce mai dificil de realizat.

Obiectivul sistemelor de criptare cu cheie publică este acela de a face imposibil de obținut cheia dK plecând de la eK. Astfel, regula de criptare eK poate fi publicată într-un „registru public” (de unde și numele sistemelor). Avantajul constă în faptul că Alice (sau oricare altă persoană) poate trimite lui Bob un mesaj criptat cu eK fără a intra în prealabil în contact. Bob este singura persoană capabilă să decripteze textul, utilizând cheia sa secretă dK.

Ideea de sistem de criptare cu cheie publică apare în 1976 și este prezentată de Difne și Hellman . De atunci au apărut diverse astfel de sisteme, a căror securitate este bazată pe probleme calculatorii. Cele mai cunoscute în acest moment sunt:

Sistemul RSA: se bazează pe dificultatea descompunerii în factori primi a numerelor mari (de sute de cifre). Este sistemul cel mai larg utilizat în acest moment.

Sistemul El Gamal: se bazează pe dificultatea calculului logaritmului discret într-un corp finit.

Sistemul Merkle-Hellman: primul sistem definit cu cheie publică, bazat pe problema {0,1} a rucsacului, problemă NP-completă.

Sistemul McEliece: este bazat pe teoria algebrică a codurilor, decodificarea unui cod liniar fiind de asemenea problemă NP-completă.

Curbe eliptice: sunt sisteme de criptare care își desfășoară calculele pe mulțimea punctelor unei curbe eliptice (în locul unui inel finit ).

Se știe că toate problemele din clasa P care se pot rezolva în timp polinomial, sunt de asemenea în clasa NP, adică există metode pentru a verifica corectitudinea unei ipotetice soluții în timp polinomial. Pe de alta parte nu se știe dacă există probleme în NP care nu sunt în P , adică dacă partea hașurată din figura de mai jos este vidă sau nu.

Figura 3.1

3.3 Funcții neinversabile

O observație importantă este aceea că un sistem cu cheie publică nu este sigur necondiționat, adică oricine, putând să efectueze criptări, nu este exclus să găsească anumite puncte slabe care să îi permită să și decripteze mesajele. Ideea de bază folosită este aceea de funcție neinversabilă. În continuare este clarificat puțin acest aspect.

Exemplul 3.1:

Se poate imagina ușor străzile cu sens unic dintr-un oraș. Astfel, este ușor ca mergând pe astfel de străzi să se ajungă de la punctul A la punctul B, dar este imposibil de ajuns de la B la A. În acest mod, criptarea este privită ca direcția A —> B. Deși este foarte ușor de parcurs drumul în această direcție, nu este posibilă întoarce înapoi spre A (adică să decriptezi mesajul).

Exemplul 3.2:

Să considerăm cartea de telefon a unui oraș mare, cu ajutorul căreia este foarte ușor de găsit numărul de telefon al unei anumite persoane. În schimb, este extrem de greu, practic imposibil, să se afle persoana care are un anumit număr de telefon. Este ca și situația parcurgerii secvențiale a cel puțin unui volum gros, ceea ce conduce la o creștere exagerată a timpului.

Aceasta dă o sugestie de construcție a unui sistem de criptare cu cheie publică. Criptarea se face independent de context, literă cu literă. Pentru fiecare literă a textului clar se alege un nume care începe cu acest caracter și numărul de telefon al persoanei respective va constitui criptarea. Sistemul este homofonic, adică două apariții diferite ale aceleiași litere vor fi codificate foarte probabil cu numere diferite.

De exemplu, textul clar SOLIST se poate cripta astfel:

S Simion Pavel 6394502

O Olaru Ștefan 7781594

L Lambru Stelian 6300037

I Ilie Romeo 3134971

S Solovean Raluca 6281142

T Tecuceanu Paul 3359962

Deci, textul criptat va fi:

639450 277815 946300 037313 497162 811423 359962.

Este de remarcat că metoda este nedeterministă, adică din același text clar se pot obține enorm de multe texte criptate. Pe de altă parte, orice text criptat conduce la un text clar unic.

Bob va avea la dispoziție pentru decriptare o carte de telefon scrisă în ordinea crescătoare a numerelor. Aceasta îi va permite să decripteze mesajele cu un algoritm de complexitate O(log n).

Deci, o funcție neinversabilă f trebuie să verifice două condiții:

Fiind dat x, f (x) este ușor de calculat;

Calculul lui x din f (x) este imposibil.

Este de remarcat că, din punct de vedere strict matematic, nu se cunosc astfel de funcții. A demonstra că există funcții neinversabile este echivalent cu a demonstra relația P ≠ NP, conjunctură care stă la baza întregii teorii criptografice. De aceea, termenii folosiți sunt relativi la complexitatea calculului. Astfel, o problemă este:

ușoară dacă se poate rezolva cu un algoritm cel mult liniar;

grea dacă se poate rezolva cu un algoritm polinomial neliniar;

imposibilă dacă este o problemă NP-completă.

Exemplul 3.3:

Se consideră „problema rucsacului”. Ea constă dintr-un vector de dimensiune n, A = (a1, a2, … an) cu elemente numere întregi pozitive distincte, și un număr întreg pozitiv k. Trebuiesc aflați acei ai din A ,dacă există, a căror sumă este k. Numele intuitiv dat problemei este evident.

De exemplu, fie

A= (43, 129, 215, 473, 903, 302, 561, 1165, 696, 1523) și k = 3231.

Se determină

3231 = 129 + 473 + 903 + 561 + 1165,

care este o astfel de soluție.

În principiu o soluție se poate găsi parcurgând sistematic toate submulțimile lui A și verificând dacă suma elementelor lor este k. În cazul de sus, aceasta înseamnă 210 − 1 = 1023 submulțimi, fără mulțimea vidă, dimensiune acceptabilă ca timp de lucru.

Ce se întâmplă însă dacă A are câteva sute de componente? În acest caz se cunoaște faptul că problema rucsacului este NP-completă.

Cu ajutorul lui A se poate defini o funcție f astfel:

Fie x[0, 2n − 1], x poate fi reprezentat în binar ca un cuvânt de lungime n, adăugând eventual zero-uri în față, și f(x) va fi numărul obținut din A prin însumarea tuturor numerelor ai aflate pe pozițiile marcate cu 1 în reprezentarea binară a lui x.

Formal,

f(x) = A ∙ BTx

unde Bx este reprezentarea binară a lui x, scrisă ca un vector coloană.

Se definește acum un sistem de criptare bazat pe problema rucsacului. Textul clar este codificat inițial în binar și segmentat apoi în blocuri de câte n biți, ultimul bloc fiind eventual completat la sfârșit cu zerouri. Fiecare bloc rezultat este apoi criptat calculând valoarea corespunzătoare a funcției f.

Pentru alfabetul latin sunt suficienți 5 biți pentru codificarea binară a literelor și a spațiului. Mai exact, dacă asociem literelor A…Z reprezentările binare ale numerelor 1…26, vom avea:

Tabel 3.1

Se consideră un text clar, FLOARE DE COLT de exemplu. Cum fiecare caracter se codifică în 5 biți, în fiecare bloc intră două caractere:

FL OA RE _D E_ CO LT.

Codificând, se obțin șapte blocuri de câte 10 biți:

0011001100 0111100001 1001000101 0000000100 0000000101 0001101111 0110010100

care conduc la textul criptat:

(1814,3243,3204,1165,1118,5321,1811).

Se consideră sistemul de criptare definit în Exemplul 3.3. Dacă este privit ca un sistem clasic, cu cheie privată atunci criptanalistul trebuie să afle vectorul de bază A și apoi să rezolve problema rucsacului.

Dacă el folosește metoda textelor clare alese, îl va afla ușor pe A. Este suficient să trimită n texte clare cu câte un singur 1 iar restul 0. Problema apare în momentul rezolvării problemei rucsacului. Aici atât Bob cât și Oscar sunt puși în fața aceleiași probleme NP-complete. Ori, practic, doar Oscar trebuie să rezolve o problemă dificilă, nu și Bob.

O altă problemă ridicată de acest sistem de criptare este aceea că este obligatoriu ca un text criptat să determine în mod unic un text clar. Aceasta înseamnă că nu trebuie să existe două submulțimi ale lui A care să aibă aceeași sumă. Astfel, dacă se ia A = (17, 103, 50, 81, 33), textul criptat (131, 33,100, 234, 33) poate fi decriptat în două moduri: SAUNA și FAUNA.

3.4 Trapa secretă

Pentru ca Bob să nu fie pus în aceiași situație ca și Oscar, el trebuie să dispună de un procedeu care să îi permită să transforme problema NP-completă publică, într-o problemă ușoară. Acest procedeu este numit trapă secretă. În primul exemplu, trapa secretă era cartea de telefon ordonată după numerele de telefon, și nu după abonați. Se va determina trapa secretă în sistemul de criptare din Exemplul 3.3.

Exemplul 3.4:

Sunt clase de probleme ale rucsacului ușor de rezolvat, iar una din ele o formează vectorii cu creștere mare.

Se spune că vectorul rucsac A = (a1, a2, … an) este cu creștere mare dacă

j ≥ 2, aj ≥

În acest caz, pentru a rezolva problema rucsacului este suficient să parcurgem vectorul A de la dreapta spre stânga. Cunoscând valoarea k, cercetăm întâi valoarea de adevăr a relației k ≥ an. Dacă răspunsul este FALSE, an nu poate aparține sumei pe care o căutăm. Dacă însă se obține TRUE, atunci an trebuie să fie în sumă, deoarece toate elementele ai rămase nu pot depăși în sumă pe k. Se definește

și se repetă procedeul pentru k și ai. Algoritmul se va opri la valoarea ai. Se presupune că există vectorul rucsac cu creștere mare

A = (l, 3, 5, 11, 21, 44, 87, 175, 349, 701)

și vrem să decodificăm mesajul 278. Se va parcurge 10 pași, reprezentați în tabelul:

Tabel 3.2

Număr Componenta lui A Bit rezultat

Deci se obține secvența binară 00110 01100 care, conform codificării din Exemplul 3.3 corespunde perechii de litere FL.

Dacă se folosește însă public o astfel de informație, orice utilizator, inclusiv Oscar poate decripta mesajele folosind un algoritm liniar.

Exemplul 3.5:

Pentru sistemul bazat pe problema rucsacului, Bob va proceda astfel: va alege un număr m, unde m > , numit modul și un număr t, (m, t) = 1 numit multiplicator. Există atunci un număr s astfel ca ms = l (mod m).

Plecând de la vectorul cu creștere mare A = (a1, a2, … an) Bob generează vectorul B = ( b1, b2, … bn ) unde bi = tai (mod m).

Vectorul B este declarat public pentru criptare, iar m, t și s vor forma trapa secretă a lui Bob.

Astfel, dacă se ia m = 1590 și t = 43, vectorul cu creștere mare

A = (l, 3, 5, 11, 21, 44, 87, 175, 349, 701)

devine

B = (43, 129, 215, 473, 903, 302, 561, 1165, 697,1523),

adică cel prezentat în Exemplul 3.3. În plus, s = t−1 = 373.

Cum se va proceda? Cel care dorește să trimită lui Bob un mesaj criptat va folosi vectorul rucsac B și va cripta mesajul x în y = B ∙ BTx, conform Exemplului 3.3.

La recepție, Bob va calcula întâi z = s ∙ y(mod m), după care va decripta mesajul z folosind vectorul cu creștere mare A. Se poate arăta ușor că soluția este chiar x.

Astfel, de exemplu Alice poate cripta mesajul FL în 2414, conform Exemplului 3.3. La primirea acestui număr, Bob va determina întâi

s ∙ 2414 = 37 ∙ 2414(mod 1590) = 278.

În Exemplul 3.4 s-a văzut că decriptarea mesajului 278 cu vectorul A conduce la textul clar FL.

Se pot trasa acum câteva principii generale de construire a unui sistem de criptare cu cheie publică:

Se începe cu o problemă dificilă P. Rezolvarea lui P este imposibilă în conformitate cu teoria complexității deoarece nu se cunoaște nici un algoritm de complexitate polinomială care să rezolve P.

Se selectează o subproblemă P1 a lui P, rezolvabilă în timp polinomial, preferabil liniar.

Se aplică o transformare problemei P1 astfel încât să se obțină o problemă P2 care să nu semene cu P dar să fie foarte apropiată de problema P.

Se face publică problema P2 și se descrie algoritmul de criptare bazat pe aceasta. Informația referitoare la modul în care se obține P1 din P2 este o trapă secretă.

Se construiesc detaliile sistemului de criptare, astfel încât principiile de lucru să difere esențial pentru destinatar față de criptanalist. Astfel, în timp ce primul va folosi trapa secretă și va rezolva problema P1, al doilea va trebui să rezolve problema P2, imposibilă datorită asemănării ei cu problema P.

În funcție de aceste principii generale, apar în detalii de construcție multe alte probleme pe care constructorii sistemelor de criptare trebuie să le rezolve.

3.5 Securitatea sistemelor de criptare cu cheie publică

În majoritatea sistemelor de criptare, aparatul matematic folosit este bazat pe teoria numerelor, teoria funcțiilor recursive și teoria probabilităților. Pe o scară mult mai restrânsă apar funcțiile eliptice, teoria automatelor, calcul neconvențional (cuantic, molecular etc.).

Sistemele de criptare cu cheie publică au un avantaj major față de sistemele simetrice și anume aici nu mai este necesar efortul transmiterii cheii. Un contact prealabil între Alice și Bob pentru a pune la punct detaliile sistemului de criptare este inutil.

Un sistem de criptare cu cheie publică nu oferă însă o securitate absolută. Aceasta se datorează faptului că Oscar poate oricând să dispună de atacuri pasive sau active și anume:

Dacă cript-analistul dispune de un text criptat y, el poate căuta exhaustiv un text clar x astfel încât eK (x) = y. Singura apărare contra unui astfel de atac constă în gradul de complexitate al sistemului.

Un criptanalist activ poate efectua cu succes un atac de tipul meet in the middle. Se presupune că Alice și Bob doresc să stabilească un contact. Ei fac publice cheile de criptare eA respectiv eB .Dacă contactul este nepersonalizat, Oscar poate controla mesajele schimbate între cei doi, în felul următor:

Figura 3.2

Oscar opacizează printr-un mijloc oarecare aceste chei, și trimite lui Alice cheia ca din partea lui Bob. Substituie, similar, pentru Bob cheia eA cu .

Fie m mesajul pe care Alice vrea să îl trimită lui Bob. Ea va cripta și va trimite.

Oscar interceptează mesajul, reamintind că toate canalele sunt nesigure și află .

Oscar recriptează și trimite y lui Bob.

Bineînțeles, Oscar poate modifica sau întârzia mesajul m dacă dorește. Din această cauză, aproape în toate sistemele de criptare cu cheie publică apare necesitatea autentificării mesajului sau a expeditorului, precum și aceea a confidențialității.

Metodele prin care un expeditor uman se poate autentifica sunt clasificate în:

„ceva ce utilizatorul este" (de exemplu amprente digitale, de retină, de voce, recunoașterea semnăturii, identificatori biometrici).

„ceva de utilizatorul are” (de exemplu card de identitate, date de securitate soft pe calculator sau telefon).

„ceva ce utilizatorul știe” (de exemplu o parola, un număr de identificare PIN).

Orice combinație între metodele anterioare (de exemplu un card bancar cu PIN asigură o dublă autentificare).

Deasemenea integritatea, care se referă la validitatea datelor poate fi compromisă în două moduri:

Prin alterare intenționată (de exemplu modificarea unui cont bancar, a unei adrese de e-mail, a unui document de identitate).

În mod accidental (transmisii perturbate de zgomote de canal, zgârierea hard-discului).

Se presupune că Alice și Bob sunt doi utilizatori cu posibile conflicte de interese. Când Alice trimite un mesaj lui Bob, ambele părți trebuie să se asigure că:

Mesajul nu este trimis de o terță persoană care pretinde a fi Alice.

Bob să nu poată obliga pe Alice să țină cont de mesaje care nu-i aparțin, iar Alice să poată recunoaște public propriile mesaje.

Într-o oarecare măsură, cele două condiții sunt contradictorii. Conform primei condiții, Bob trebuie să știe ceva despre modul de criptare al lui Alice, care îi va permite să autentifice mesajul, iar conform celei de-a doua condiții, el nu trebuie să știe prea mult. O modalitate frecvent utilizată pentru autentificarea mesajelor este folosirea codurilor de autentificare.

De exemplul MAC-ul (Message Authentication Code) definit în cadrul sistemului de criptare DES este o variantă prin care se poate asigura atât autenticitatea cât și integritatea mesajului. Dacă se solicită și autentificarea partenerilor, atunci se folosește de obicei semnătura electronică.

Exemplul 3.6: Se presupune că Alice vrea să trimită lui Bob mesajul m. Dacă se folosește un sistem de criptare cu cheie publică în care funcțiile de criptare sau de decriptare sunt comutative, iar (eA , dA), ( eB , dB) sunt perechile (cheie publică,cheie privată) ale celor doi, ei pot urma următorul protocol:

Alice trimite lui Bob y1 = eA (m);

Bob trimite lui Alice y = eB (y1);

Alice trimite lui Bob dA (y) = eB (m);

Bob calculează dB (eB (m)) = m și află mesajul.

Se observă că sunt verificate cele două condiții de autentificare și, în plus protocolul rezistă unui atac de tip meet in the middle.

Dacă dorim să folosim un singur contact, Alice poate trimite mesajul

y = eB (dA (m)).

La recepție, Bob va folosi propria sa cheie pentru decriptare, împreună cu

cheia publică a lui Alice. Metoda merge și pentru sisteme de criptare necomutative.

3.6 Teste probabilistice de primalitate

Există multe situații în care dorim să știm dacă un număr foarte mare este prim sau nu. De exemplu, în sistemul de criptare cu cheie publică RSA (prezentat în capitolul următor) avem nevoie de numere prime mari.

Un test de primalitate este un criteriu folosit pentru a arăta că un număr n nu este prim. Dacă n trece un test de primalitate, el poate fi prim. Dacă el trece mai multe teste de primalitate, el este foarte probabil prim, iar dacă nu trece un test este sigur compus. În acest ultim caz apare o problemă foarte complicată, aceea de a-i găsi descompunerea în factori primi. De obicei, procedeul de a determina factorii primi ai unui număr foarte mare n (odată ce se cunoaște că este compus) este mult mai îndelungat decât cel de a găsi un număr prim de mărimea lui n .

Acest capitol are ca scop prezentarea unor astfel de teste de primalitate.

Majoritatea testelor eficiente de primalitate au forma generală asemănătoare cu următorul.

Conform micii teoreme a lui Fermat, dacă n este număr prim atunci, pentru orice b cu (b, n) = 1 avem bn-1 ≡ 1 (mod n). Sub o formă echivalentă, rezultă că dacă există un întreg b care nu este congruent cu bn mod n, atunci n este compus. De exemplu, există b = 2 astfel încât pentru n = 63 obținem 263 = 26023 = (26)10∙8 = (64)10∙8 ≡ 1(mod 63).

O observație importantă este aceea că reciproca micii teoreme a lui Fermat nu este adevărată. Pentru aceasta să observăm că pentru n = 341 = 11∙31 și b = 2 obținem 210 ≡ 1(mod11) de unde

2340 = (210)34 ≡ 1(mod11)

și

2340 = (25)68 = (32)68 ≡ 1(mod31).

Din cele două, obținem dar n nu este prim.

Definiție: Fie b număr natural. Dacă n este număr natural compus și bn ≡ b(mod n) atunci n se numește număr pseudoprim cu baza b.

Ca exemplu, am arătat deja că 341 este pseudoprim cu baza 2.

Observăm că, dacă (b, n) = 1 congruența bn ≡ b(mod n) este echivalentă cu

bn−1 ≡ 1(mod n) .

În continuare prezentăm o metodă rapidă de a calcula bn(mod m) unde b, n, m sunt numere naturale. Algoritmul presupune ridicări la pătrat și înmulțiri repetate și este deosebit de eficient și de aceea foarte des folosit în multe protocoale criptografice.

Pentru început se scrie n in baza 2. Fie n = (ak ak−1 … a1 a0 )2. Observăm că

bn = = ….

Ținând cont de acest lucru, calculăm întâi resturile modulo m ale lui b, b2, b4,…,ridicând succesiv la pătrat și reducând modulo m. După aceea, înmulțim resturile modulo m ale lui cu aj = 1 și reducem modulo m.

Algoritm 3.1:

INPUT: b, n, m.

OUTPUT: bn(mod m).

1. x ← 1. Dacă n = 0 returnează x.

2. A←b.

3. Dacă a0 = 1 atunci x ← b.

4. Pentru j = 1, …, k calculează:

4.1 A ← A2(mod m).

4.2 Dacă aj = 1 atunci x ← A ∙ x(mod m).

5. Returnează x .

Spre exemplu, în tabelul următor se evidențiază pe pași calculul lui 5596( mod 1234).

Tabel 3.3

Teoremă 3.1: Există o infinitate de numere pseudoprime cu baza 2.

Demonstrație: Observăm mai întâi că d | n => (2d −1) | (2n −1). Vom arăta că dacă n este pseudoprim cu baza 2 atunci, m = 2n −1 este tot pseudoprim cu baza 2. Cum există cel puțin un pseudoprim cu baza 2, fie el n0 = 341, de exemplu, putem construi o infinitate de numere impare diferite nk+1 =−1, k > 0 pseudoprime cu baza 2. Consider n impar, pseudoprim cu baza 2 adică n este compus și 2n-1≡ 1(mod n). Fie d un divizor propriu al lui n. Atunci, (2d −1) | (2n −1) adică m este compus. Din 2n ≡ 2(mod n) rezultă 2n − 2 = kn pentru un k întreg. Atunci, 2m−1 = 2kn. Cum (2n −1) | (2kn −1) obținem m | (2m−1 −1) adică 2m−1 ≡ 1(mod m).

Un prim test de primalitate prezentat este datorat micii teoreme a lui Fermat și constă în a stabili dacă pentru un număr n există un întreg b cu (b, n) = 1 pentru care bn−1 nu este congruent cu l mod n. Astfel, se testează pentru diferite valori ale lui b dacă bn−1 ≡ 1(mod n). Dacă n nu trece testul pentru un b atunci, n este compus. Dacă însă, n trece testul pentru toate valorile considerate pentru b nu putem preciza dacă n este prim sau nu.

Exemplu 3.7: Știm că 341 este pseudoprim cu baza 2. Din 73 = 343 ≡2(mod341), 210 = 1024 ≡ 1(mod341) rezultă 7340 = (73)113∙7 ≡ 2113 ∙7 ≡ (210)11∙8∙7 ≡ 56(mod 341). Deci există b = 7pentru care 341 nu trece testul adică 341 este compus.

Algoritm 3.2: Testul de primalitate Fermat.

INPUT: n > 2, impar, un parametru de securitate t > 1.

OUTPUT: un răspuns relativ la primalitatea lui n.

1. Pentru i de la l la t:

1.l Alege aleator un întreg a, 2 ≤ a ≤ n − 2.

1.2 Calculează folosind algoritmul 3.1.

1.3 Dacă r ≠ 1 atunci returnează compus.

2. Returnează prim.

Din păcate, există numere care sunt pseudoprime cu orice bază b unde (b, n) =1, deci numere compuse care trec testul Fermat indiferent ce astfel de baze am considera. Pentru astfel de numere, sunt importante valorile lui a, 1 ≤ a ≤ n − 1, cu

(a, n) > 1. Dar, dacă factorii primi ai lui n sunt toți mari, probabilitatea ca testul Fermat să concluzioneze că n este prim este foarte ridicată, chiar dacă numărul de iterații t este mare.

Un exemplu de un astfel de număr este n = 561 =3∙11∙17. Considerăm un întreg b cu (b, 561) = 1. Atunci, (b, 3) = 1, (b, 11) = 1, (b, 17) = 1. Rezultă

b2 ≡ 1(mod 3),

b10 ≡ 1(mod 11),

b16 ≡ 1(mod 17).

Astfel,

b560 = (b2)280 ≡ 1(mod3),

b560 = (b10)56 ≡ 1(mod11),

b560 = (b16)35 ≡ 1(mod17),

de unde b560 ≡ 1(mod561).

Definiție: Un număr Carmichael este un număr compus n pentru care bn−1 ≡ 1(mod n), oricare ar fi b întreg relativ prim cu n.

Dacă se cunoaște descompunerea în factori primi a unui număr, se poate preciza dacă acesta este un număr Carmichael sau nu pe baza următoarei teoreme:

Teorema 3.2: Un număr natural n este număr Carmichael dacă și numai dacă verifică următoarele condiții:

n este liber de pătrate, adică nu este divizibil cu pătratul nici unui număr prim,

pentru orice divizor prim p al lui n, (p−1) | (n−1).

Cel mai des folosit test probabilistic de primalitate este testul Miller – Rabin sau testul numerelor tari pseudoprime. Pentru prezentarea acestuia avem nevoie de câteva rezultate pregătitoare.

Definiție: Fie n cu n −1 = 2s ∙ t unde s, t și t este impar. Spunem că n trece testul Miller pentru baza b dacă bt ≡ 1(mod n) sau există un j, 0 ≤ j ≤ s − 1 pentru care ≡ −1(mod n).

Se remarcă următorul fapt:

Teorema 3.3: Dacă n este prim și b este un număr natural care nu divide pe n, atunci, n trece testul Miller pentru baza b.

Dar, putem observa că nu numai numerele prime au această proprietate. De exemplu, pentru n = 2047 = 23∙89 și b = 2, (n −1 = 21∙1023 ) obținem că el trece testul Miller pentru baza 2 pentru că = 21023 = (211)93 = (2048)93 ≡ 1(mod 2047). Astfel, este necesară studierea acestor numere.

Definiție: Dacă n este compus și trece testul Miller pentru baza b, spunem că n este tare pseudoprim cu baza b.

Observație: Dacă n trece testul Miller pentru baza b atunci, n −1 = 2s ∙ t și bt ≡ 1(mod n) sau ≡ −1(mod n) pentru un j. Dar, bn−1 = ; bn−1 = . Din cele două scrieri obținem că, indiferent de congruența care se verifică, bn−1 ≡ 1(mod n) adică n este pseudoprim cu baza b. Obținem astfel că orice număr tare pseudoprim cu baza b este pseudoprim cu baza b.

Dar, există numere pseudoprime cu baza b care nu sunt tari pseudoprime cu acea bază. De exemplu, n = 341 este pseudoprim cu baza 2. n − 1 = 22∙85, s = 2, t = 85.

Din 210 = 1024 ≡ 1(mod 341) obținem

bt = 285 = (210)8 ∙ 25 ≡ 32(mod 341),

și

b2t = 2170 = (210)17 ≡ 1(mod 341).

Cum nu se verifică nici una din condițiile definiției de mai sus, 341 nu este tare pseudoprim cu baza 2.

Observație: Am remarcat că numerele care trec testul Miller pentru o bază b sunt cele prime sau cele tari pseudoprime cu baza b. Pentru verificarea primalitații unor numere relativ mici putem folosi testul Miller ținând cont de câteva rezultate cunoscute cum ar fi:

i) Cel mai mic număr impar tare pseudoprim cu baza 2 este 2047. Astfel, dacă n impar trece testul Miller pentru baza 2 și n < 2047, atunci el este prim. Analog vom proceda și în cazul afirmațiilor următoare.

ii) Cel mai mic număr impar tare pseudoprim cu bazele 2 și 3 este 1373653.

iii) Cel mai mic număr impar tare pseudoprim cu bazele 2, 3 și 5 este 25326001.

iv) Cel mai mic număr impar tare pseudoprim cu bazele 2, 3, 5 și 7 este 3215031751.

v) Singurul număr impar mai mic decât care este tare pseudoprim cu bazele 2, 3, 5 și 7 este 3215031751.

Teorema3.4 (Testul probabilistic al lui Rabin): Fie n număr natural. Considerăm k numere naturale diferite, și realizăm testul Miller pentru n și toate aceste k baze. Dacă n este compus, probabilitatea ca n să treacă toate testele este mai mică decât .

De exemplu, dacă n este compus, probabilitatea ca el să treacă testul Miller pentru 100 de baze diferite < n este mai mică decât 10−60. De aceea testul Miller-Rabin nu dovedește cu exactitate că numărul n este prim dar, datorită probabilității extrem de mici, furnizează un motiv puternic de a presupune că el este prim.

Algoritm 3.3: Test probabilistic de primalitate Miller-Rabin.

IMPUT: n >2, impar și un parametru de securitate r > 1.

OUTPUT: un răspuns relativ la primalitatea lui n.

1. Determină s și t astfel încât n −1 = 2s ∙ t cu t impar.

2. Pentru i de la l la r :

2.1 Alege un a, 2 ≤ a ≤ n − 2.

2.2 Calculează y = at(mod n) folosind algoritmul 3.1

2.3 Dacă y ≠ 1 și y ≠ n−1 atunci:

j ← 1

Cât timp j ≤ s −1 și y ≠ n−1 execută:

y ← y2(mod n)

Dacă y = 1 atunci returnează compus.

j ← j + 1

Dacă y ≠ n−1 returnează compus.

Returnează prim.

În încheierea acestui capitol să studiem o clasă specială de numere care are o deosebită importanță în furnizarea celor mai mari numere prime cunoscute până în prezent.

Definiție: Un număr de forma Ms = 2s −1 cu s natural, s >2 se numește număr Mersenne. Dacă Ms este prim, el se numește număr prim Mersenne

.

Dacă Ms este număr prim se arată că s trebuie să fie prim. Dar dacă s este prim nu rezultă că Ms este și el prim. De exemplu, pentru s = 11, M11 = 211 − 1 = 2047 = 23 ∙ 89 este compus.

Se poate da o caracterizare a divizorilor unui număr Mersenne dacă acesta nu e prim.

Teorema 3.5: Dacă s este număr prim impar, orice divizor prim al numărului Mersenne Ms dacă există, este de forma 2ks + 1, pentru un k natural.

Spre exemplu, fie M13 = 213 − 1 = 8191. Pentru a vedea dacă este prim sau nu vedem dacă există un divizor prim < = 90,504… de forma 26k + 1. Singurele numere prime de această formă < 90 sunt 53 și 79. Prin verificare directă obținem că ele nu divid M13 și astfel M13 este prim.

Dacă facem același lucru pentru M23 = 223 − 1 = 8388607 vom căuta divizori primi de forma 46k + 1 care sunt < 2896. Găsim pe 47 și cum M23 = 47 ∙ 178481 acesta este compus.

Teorema 3.6 (Testul Lucas-Lehmer): Fie s ≥ 3. Numărul Mersenne Ms = 2s − 1 este prim dacă și numai dacă sunt verificate condițiile:

1) s este prim,

2) șirul de numere întregi (uk)k≥0 definit prin u0 = 4, uk+1 ≡ uk2 − 2(mod Ms), k ≥ 0 verifică us−2 ≡ 0(mod Ms).

De exemplu: pentru M5 = 25 − 1 = 31 șirul este dat de u0 = 4, u1 ≡ 14(mod 31), u2 ≡ 142 −2 ≡ 8(mod 31) și u3 ≡ 182 −2 ≡ 0(mod 31). Deci, este prim.

Algoritm 2.3: Testul de primalitate Lucas-Lehmer pentru numere Mersenne.

INPUT: un număr Mersenne n = Ms = 2s − 1, cu s ≥ 3

OUTPUT: un răspuns referitor la primalitatea numărului n.

1. Se verifică prin metoda obișnuită dacă s are un divizor cuprins între 2 și []. Dacă are, returnează compus.

2. u ← 4

3. Pentru k de la l la s − 2 efectuează

3.1. u ← (u2 − 2)(mod n)

4. Dacă u = 0 returnează prim. Altfel, returnează compus.

Observație: Până în prezent se cunosc doar 39 de numere Mersenne prime. Pentru toate numerele prime s < 103000 s-au găsit 31 de numerele prime Mersenne Ms. Cel mai mare număr prim Mersenne este corespunzător lui s = 13466917 iar dimensiunea lui depășește 4 milioane de cifre.

Capitolul IV

ALGORITMUL RSA

4.1 Descrierea algoritmului RSA

Imediat după apariția algoritmului „Rucsacul lui Merkle” apare primul algoritm cu chei publice complet care face criptări și semnături digitale numit RSA. O descriere de început a algoritmului a fost publicată în volumul „Mathematical Games” din seria „Scientific American”. Numit după numele celor trei inventatori care l-au descoperit – Ron Rivest, Adi Shamir, Leonard Adleman – a rezistat de-a lungul anilor atacurilor criptanaliștilor. Cu toate că aceștia nu au verificat securitatea algoritmului RSA se sugerează un nivel confidențial în algoritm.

Tabel 4.1

Evidența din străinătate a problemei „Rucsacul lui Merkle-Hellman”

Țara Numărul Data apariției Belgium 871039 5 aprilie 1979

Netherlands 7810063 10 aprilie 1979

Great Britain 2006580 2 mai 1979

Germany 2843583 10 mai 1979

Sweden 7810478 14 mai 1979

France 2405532 8 iunie 1979

Germany 2843583 3 iunie 1982

Germany 2857905 15 iulie 1982

Canada 1128159 20 iulie 1982

Great Britain 2006580 18 august 1982

Switzerland 63416114 14 ianuarie 1983

Italy 1099780 28 septembrie 1985

Amintim câțiva termeni de informație care sunt implicați:

p, q sunt două numere prime mari, alese de cel care primește mesajul și care sunt ținute secrete (nu sunt spuse nici măcar celui care trimite mesajul);

n este produsul lui p și q și este plasat în domeniul public;

e este un întreg aleator plasat în domeniul public de către cel ce primește mesajul, care mai întâi se asigură că e este relativ prim cu (p–1)(q–1), prin calculul funcției cmmdc, alegând un nou e aleator până când funcția cmmdc este1. Este ușor pentru cel ce primește mesajul deoarece p și q îi sunt cunoscute, iar calculul funcției cmmdc este rapid;

m este mesajul pe care o persoană dorește să-l trimită, privit ca un șir de biți a căror valoare se află între 0 și n–1.

În plus de ceea ce este prezentat anterior, încă un termen de informații este calculat de cel care primește mesajul, și acesta este un număr întreg d care este inversul multiplicativ mod (p–1)(q–1) al lui e, adică

de ≡ 1 (mod (p–1)(q–1))

Deci cum p și q sunt cunoscute, acesta este un mod rapid de a calcula pentru cel ce primește mesajul, la fel cum vom vedea în continuare.

Ca rezumat, se știe că destinatarul sau cel care primește mesajul cunoaște pe p, q și d, expeditorul sau cel ce trimite mesajul îl cunoaște pe m, iar n și e sunt publice și pot fi știute de oricine.

În figura de mai jos sunt prezentate informațiile deținute de fiecare și cele publice.

Figura

Cine știe, ce?

Securitatea RSA se bazează pe dificultatea factorizării numerelor mari.

Cheile publice și cheile private sunt funcții de perechi (de la 100 la 200 de cifre, poate chiar mai mari) de numere prime mari. Restabilirea textului clar pornind de le cheia publică și de la textul criptat este presupusă a fi echivalentă cu factorizarea produsului a două numere prime.

Pentru a genera cele două chei se aleg aleator două numere mari prime p și q, iar pentru securitate maximă se aleg p și q de aceeași lungime, după care se face produsul lor:

n = pq

Apoi se alege aleator cheia de criptare e astfel încât e și (p–1)(q–1) să fie prime între ele, unde (p–1)(q–1)φ(n).

În final, se folosește algoritmul de extindere Euclidian pentru a calcula cheia de decriptare d astfel încât

ed ≡ 1 mod ((p–1)(q–1))

Cu alte cuvinte,

d ≡ e–1 mod ((p–1)(q–1)).

Se observă că d și n sunt de asemenea prime între ele, Numerele e și n formează cheia publică, iar numărul d reprezintă cheia privată.

Pentru a cripta un mesaj m, mai întâi se împarte mesajul în blocuri de lungime mai mică decât n (ca dată binară se poate alege cea mai mare putere a lui doi mai mică decât n). Cu alte cuvinte, dacă ambele numere p și q au 100 de cifre prime atunci n va avea sub 200 de cifre și fiecare bloc de mesaj mi va trebui să aibă sub 200 cifre lungime. Dacă se dorește criptarea unui număr fix de blocuri se poate completa cu zero la stânga pentru a asigura faptul că întotdeauna vor fi mai mici decât n. Mesajul criptat c va fi împărțit similar în blocuri de aceeași lungime.

Formula de criptare este

ci ≡ (mod n)

Pentru a decripta mesajul se ia fiecare bloc criptat ci și se calculează

mi ≡ (mod n)

Astfel

≡(mod n) ≡ (mod n) ≡ (mod n) ≡
≡(mod n) ≡ mi∙1 (mod n) ≡ mi (mod n).

Aceasta este formula care descoperă mesajul și al cărui rezumat este relatat în tabelul următor:

Tabel 4.2

Criptarea RSA

Cheia publică

n produs a două numere prime p și q ( p și q trebuie să rămână secrete)

e relativ prim cu (p–1)(q–1)

Cheia privată

d este e–1 mod ((p–1)(q–1))

Criptarea

c ≡ me (mod n)

Decriptarea

m ≡ cd (mod n)

Mesajul poate fi cu ușurință criptat cu e și decriptat cu d, alegerea lor fiind arbitrară.

În teoria numerelor se dovedește de ce acest algorimt funcționează, cele mai recente texte din criptografie acoperind-o în detaliu.

În continuare va fi prezentat un scurt exemplu în care se aplică criptarea RSA.

Exemplul 4.1:

Dacă p = 47 și q = 71, atunci

n = pq= 3337.

Cheia de criptare e nu trebuie să aibă factori comuni cu

(p–1)(q–1) = 46 ∙ 70 = 3220.

Se alege e aleator ca fiind 79. În acest caz

d = 79–1 mod (3220) = 1019.

Acest număr a fost calculat folosind algoritmul de extindere al lui Euclid. Deci n și e se publică, d se ține secret, iar p și q se uită (se abandonează).

Pentru criptarea mesajului

m = 68823268796666683

mai întâi acesta se împarte în blocuri mai mici. Blocuri de trei cifre se potrivesc foarte bine în acest caz. Mesajul este împărțit în șase blocuri mi după cum urmează:

m1 = 688

m2 = 232

m3 = 687

m4 = 966

m5 = 668

m6 = 003

Primul bloc este criptat ca

68879(mod 3337) = 1570 = c1

Urmărind aceeași metodă pentru fiecare bloc se obține:

23279(mod 3337) = 2756 = c2

68779(mod 3337) = 2091 = c3

96679(mod 3337) = 2276 = c4

66879(mod 3337) = 2423 = c5

00379(mod 3337) = 158 = c6

Astfel se generează mesajul criptat

c = 1570 2756 2091 2276 2423 158

Decriptarea mesajului necesită performanțe, aceeași exponențială folosind cheia de decriptare 1019, deci

15701019 (mod 3337) = 688 = m1

De asemenea și celelalte blocuri ale mesajului pot fi descoperite în aceeași manieră:

27561019 (mod 3337) = 232 = m2

20911019 (mod 3337) = 687 = m3

22761019 (mod 3337) = 966 = m4

24231019 (mod 3337) = 668 = m5

1581019 (mod 3337) = 003 = m6

În acest fel se obține mesajul original m format din blocurile mi .

Viteza algoritmului RSA

Din punct de vedere hardware, algoritmul RSA necesită un timp de o mie de ori mai mic decât algoritmul DES. Implementarea hardware VLSI mai rapidă pentru RSA cu 512 biți în modul, are o scriere directă de 64 kilobiți pe secundă. Există de asemenea cipuri cu performanță de criptare RSA de 1024 biți. Recent cipurile au avansat apropiindu-se de 1 megabit pe secundă folosind 512 biți în modul. De exemplu, întreprinderile au implementat de asemenea algoritmul RSA în card-urile moderne, aceste implementări fiind însă mai încete. În continuare este prezentată o listă cu cele mai recente cipuri.

Tabel 4.3

Existența cipurilor RSA

Compania Viteza Rata de Tehnologie Biți / cip Numărul

transmitere Tranzistorilor

pe 512 biți

Alpha.Techn. 25 MHz 13 K 2 micron 1024 180.000

AT&T 15 MHz 19 K 1,5 micron 298 100.000

British Telecom 10 MHz 5.1 K 2,5 micron 256 ——

Business.Sim.Ltd. 5 MHz 3.8 K Gate Array 32 ——

Calmos.Syst. Inc. 20 MHz 28 2 micron 593 95.000

CNET 25 MHz 5.3 1 micron 1024 100.000

Cryptech 14 MHz 17 Gate Array 120 33.000

Cylink 30 MHz 6.8 1,5 micron 1024 150.000

GEC Marconi 25 MHz 10.2 1,4 micron 512 160.000

Pijnenburg 25 MHz 50 1 micron 1024 400.000

Sandia 8 MHz 10 2 micron 272 86.000

Siemens 5 MHz 8.5 1 micron 512 60.000

Din punct de vedere software algoritmul DES este de aproape o sută de ori mai rapid decât algoritmul RSA. Aceste estimări pot fi schimbate cu ușurință odată cu schimbarea tehnologiei, dar RSA niciodată nu se va apropia de viteza algoritmilor simetrici. Tabelul următor redă mostre de viteză software ale algoritmului RSA.

Tabel 4.4

Viteza RSA pe diferite lungimi

de modul cu cheie publică pe 8 biți

512 bits 768 bits 1, 024 bits

Criptare 0.03 sec 0.05 sec 0.08 sec

Decriptare 0.16 sec 0.48 sec 0.93 sec

Semnare 0.16 sec 0.52 sec 0.97 sec

Verificare 0.02 sec 0.07 sec 0.08 sec

Accelerarea software

Criptarea RSA funcționează mult mai repede dacă alegerea lui e este destul de strategic făcută. Cele mai comune trei alegeri sunt 3, 17 și . Reprezentarea binară a lui 65537 are doar doi de 1, deci se fac numai 17 înmulțiri pentru exponențială. X.509 recomandă pentru alegere lui e pe 65537, PEM recomandă pe 3, iar PKCS#1 recomandă pe 3 sau 65537. Nu sunt probleme de securitate în folosirea vreunuia dintre acestea (siguranța mesajelor asigurându-se prin valorile aleatoare) chiar și dacă un întreg grup de utilizatori folosesc aceeași valoare pentru e.

Operațiile cu chei private pot fi accelerate prin folosirea teoremei resturilor chineze dacă se salvează valorile p și q și valorile suplimentare atât ale lui d(mod(p–1)), d(mod(q–1)) cât și ale lui q–1(mod p). Aceste numere suplimentare pot fi calculate cu ușurință pornind de la cheia privată sau de la cheia publică.

Securitatea algoritmului RSA

Securitatea RSA depinde în întregime de problema factorizării numerelor mari, dar din punct de vedere tehnic acest lucru nu este adevărat. Se presupune că securitatea RSA depinde de problema factorizării numerelor mari și din punct de vedere tehnic. Niciodată nu s-a demonstrat matematic că este necesară existența unui factor n pentru a calcula pe m din c și e. Este de conceput că un întreg mod diferit de a criptanaliza algoritmul RSA poate fi descoperit. Oricum, dacă această nouă cale permite criptanaliștilor să-l deducă pe d, poate fi folosită ca un nou mod de factorizare a numerelor mari, însă acest lucru nu trebuie luat foarte mult în considerare.

De asemenea este posibil un atac asupra algoritmului RSA prin ghicirea valorilor lui (p–1)(q–1), dar acest atac nu este mai ușor decât factorizarea lui n. Pentru câteva variante ale algoritmului s-a dovedit a fi dificilă factorizarea lui n. Fiecare apariție ce restabilește aceiași biți ai informației de le un text criptat RSA se realizează la fel de greu ca și decriptarea întregului mesaj.

Factorizarea lui n este cea mai evidentă cale a atacului. Orice adversar va avea o cheie publică e și modulul n. Pentru a afla cheia de decriptare d, el dispune de factorul n. Cu siguranță este posibil ca un cript-analist să încerce fiecare d posibil până când îl găsește pe cel corect. Acest atac numit și forță brutală este chiar mai puțin eficient decât încercarea de a factoriza pe n.

De la o perioadă de timp la alta oamenii au încercat să găsească căi ușoare pentru a sparge algoritmul RSA, dar până în prezent nici o încercare nu o fost de folos. De exemplu în 1993 un proiect al lui William Payne propunea o metodă bazată pe mica teoremă a lui Fermat. Din nefericire această metodă este de asemenea mai înceată decât factorizarea modulului n.

Sunt și alte motive de îngrijorare. Cei mai comuni algoritmi de calculare a numerelor prime sunt probabilistici. Ce se întâmplă dacă p și q sunt compuși? Poate exista șansa ca acesta să se întâmple mai puțin decât s-ar dori. Și dacă într-adevăr se întâmplă sunt șanse ca procesul de criptare și de decriptare să nu funcționeze, deci se va avea în vedere drumul cel bun.

Există câteva numere, numite numere Carmichael, pe care aceiași algoritmi de primalitate probabilistică le detectează negreșit. Acestea sunt extrem de rare dar sunt nesigure și cu siguranță nu reprezintă un mod de îngrijorare.

Atacul cripto-textului împotriva RSA

Câteva atacuri funcționează împotriva implementării RSA. Nu sunt atacuri împotriva algoritmului de bază, ci împotriva protocolului. Este foarte important să se realizeze, dar nu este suficientă folosirea algoritmului RSA.

Exemplu4.2:

Elena ascultând convorbirile Anei reușește să colecteze un mesaj cifrat c, criptat cu algoritmul RSA cu cheia ei publică. Elena vrea să poată să citească mesajul, deci din punct de vedere matematic ea vrea să afle pe m din

m = cd

Pentru a-l descoperi pe m mai întâi alege un număr aleator r, astfel încât r să fie mai mic decât n. Ea obține cheia publică a Anei, și anume e, iar apoi calculează

x = re(mod n)

y = xc(mod n)

t = r–1(mod n)

Dacă x = re(mod n), atunci r = xd(mod n).

În continuare Elena o face pe Ana să-i indice pe y cu cheia ei privată, astfel decriptând pe y. Trebuie precizat că Ana a semnat mesajul si nu părțile mesajului, și de asemenea trebuie amintit că ea nu l-a mai văzut pe y înainte. În acest mod Ana îi trimite Elenei

u = yd(mod n)

Acum Elena calculează

tu (mod n) = r–1yd(mod n) = r–1ydcd(mod n) = cd(mod n) = m

Deci Elena cunoaște acum mesajul original.

Exemplul 4.3:

Trend este calculatorul unui notariat public. Dacă Alice vrea un document legalizat, ea îl trimite lui Trend. Acesta îl semnează cu o semnătură numerică și îl trimite înapoi. Trebuie specificat că nici aici nu este folosită nici o funcție de împărțire, Trend realizând criptarea întregul mesaj cu cheia privată.

Mallory vrea ca Trend să identifice un mesaj care nu ar trebui. Poate avea un timp de imprimare prefăcut sau poate pretinde a fi de la o altă persoană. Indiferent de motiv Trend nu va semna niciodată dacă va fi pus în situația de a alege. Fie acest mesaj m′. Mai întâi Mellory alege o valoare arbitrară x și calculează

y = xe(mod n)

El îl poate obține ușor pe e, care este de fapt cheia publică a lui Trend și trebuie publicată pentru a-i verifica semnătura.

Apoi calculează

m = ym′ (mod n)

și trimite pe m la Trend pentru a semna. Acesta returnează

(mod n)

Mellory calculează

(md(mod n)) x–1 (mod n)

pe care îl egalează cu

(mod n)

și reprezintă semnătura lui m′.

De fapt Mellory poate folosi mai multe metode pentru a obține rezultate asemănătoare acestora.

(xm)d (mod n) = xdmd (mod n)

Exemplul 4.4:

Eve vrea ca Alice să semneze un mesaj m3. Ea generează două mesaje astfel încât

m3 = m1m2(mod n)

Dacă Eve o poate determina pe Alice să semneze pe m1 și pe m2, atunci ea poate calcula pe m3

Concluzia este că nu trebuie folosit niciodată algoritmul RSA pentru a semna un oarecare document prezentat de un străin. Se folosește totdeauna mai întâi o funcție de împărțire sau divizare a mesajului. Formatul blocului ISO9796 previne acest atac.

Atacul modulului comun asupra algoritmului RSA

O posibilă implementare a algoritmului RSA oferă tuturor același n, dar valori diferite pentru exponenții e și d. Din nefericire însă aceasta metodă nu funcționează. Cea mai evidentă problemă este aceea că dacă același mesaj este vreodată criptat cu doi exponenți diferiți, ambii având același modul, și acești doi exponenți fiind relativ primi atunci textul clar sau plain textul poate fi redescoperit fără oricare dintre exponenții de decriptare.

Fie m textul clar al mesajului inițial. Cele două chei de criptare sunt e1 și e2, iar modulul comun este n. Cele două texte criptate vor fi:

Deci cript-analistul cunoaște pe n, e1, e2, c1 și c2.

În continuare este prezentat felul în care acesta îl descoperă pe m.

Cum e1 și e2 sunt relativ prime, algoritmul de extindere al lui Euclid în poate găsi pe r și s astfel încât

re1 + se2 = 1.

Dacă se presupune că r este negativ, atunci acest algoritm poate fi refolosit pentru a calcula . Apoi

Există alte două atacuri mai ingenioase împotriva acestui tip de sistem. Unul folosește o metodă probabilistică pentru factorizarea lui n, iar celălalt folosește un algoritm deterministic pentru calcularea cheii secrete fără factorizarea modulului. Concluzia este că nu trebuie distribuit un n comun nici unui grup de utilizatori.

Atacul exponentului mic de criptare împotriva RSA

Criptarea RSA și verificarea semnăturii este mai rapidă dacă folosim o valoare mică pentru e, dar aceasta poate fi de asemenea nesigură. Dacă se criptează e(e+1)/2 mesaje dependent liniare cu chei publice diferite având aceeași valoare a lui e, atunci într-adevăr există un atac împotriva sistemului. Dacă sunt mai puține mesaje decât acest număr sau dacă mesajele sunt nerelatate atunci nu există nici o problemă. Dacă mesajele sunt identice atunci e mesaje sunt suficiente. Cea mai simplă soluție este protejarea mesajelor cu valori aleatoare independente care asigură faptul că

Concluzia este că este necesară protejarea mesajelor cu valori aleatoare înainte de criptarea lor și asigurarea că m are același număr de caractere echivalent cu n.

Atacul exponentului mic de decriptare împotriva RSA

Un alt atac va descoperi pe d când acesta reprezintă un sfert din valoarea lui n, iar e este mai mic decât n. Aceasta se întâmplă rar dacă e și d sunt alese aleator, și nu se poate realiza dacă e este o valoare mică. Concluzia este că trebuie aleasă o valoare mare pentru d.

Atacul asupra criptării și semnăturii cu RSA

Are sens semnătura unui mesaj înaintea criptării lui, însă nu toată lumea urmează acest lucru. Cu RSA, există un atac împotriva protocoalelor care face criptare înainte de a semna.

Exemplul 4.5:

Alice vrea să îi trimită un mesaj m lui Bob. Mai întâi ea îl criptează cu cheia publică a lui Bob, după care îl semnează cu cheia ei privată. Mesajul criptat și semnat va apărea în felul următor:

Bob poate afirma că Alice i-a trimis mesajul m′, și nu mesajul m. Se realizează că astfel Bob cunoaște factorizarea modulului său , și poate logaritmi discreți respectând . Deci tot ceea ce trebuie să facă este să găsească un x astfel încât

Dacă poate publica xeB ca și exponentul său public, și dacă poate ține secret pe ca și modulul lui, atunci Bob poate afirma că Alice i-a trimis mesajul m′, criptat cu acest nou exponent.

Este un atac particular neplăcut în unele circumstanțe. Se poate observa că funcțiile de împărțire nu rezolvă probleme, însă oricum se folosește forțarea unui exponent fixat de criptare de către fiecare utilizator.

4.2 Factorizarea și criptografia

Metoda particulară a sistemului RSA depinde pentru succesele ei de gradul de dificultate relativ mare al problemei, de a găsi factori ai unor numere întregi mari. Dacă această problemă poate fi rezolvată într-un timp polinomial, atunci sistemul poate fi „spart”.

În cadrul acestui sistem există trei centri de informații: trimiterea mesajului, primirea mesajului și domeniul public. În continuare vom vedea cum funcționează domeniul public.

Cum se trimite un mesaj?

Cel ce trimite mesaje alege un mesaj m, analizează cheile publice n și e, calculează

c ≡ me(mod n)

și îl trimite pe c către destinatar. Se observă că persoana care trimite mesajul nu are nici un cod privat sau vreun alt secret decât însuși mesajul.

Cum se decriptează un mesaj?

Destinatarul primește mesajul criptat c și calculează cd(mod n). Se observă că
(p–1)(q–1) = φ(n) și vom avea:

cd ≡ mde (mod n) ≡ m(1+tφ(n)) (mod n) ≡ m (mod n),

unde t este un întreg oarecare. Ultima egalitate reprezintă teorema lui Fermat. Astfel persoana căruia i-a fost destinat mesajul descoperă originalul m. Dacă are bănuieli ca și cum codul ar fi spart, adică adversarii (sau criptanaliștii) au descoperit numerele prime p și q atunci persoana care a trimis mesajul poate schimba codul înainte să trimită vreun mesaj secret altcuiva. Doar numerele publice n și e se vor schimba. Expeditorul nu este nevoie să fie informat de orice altă schimbare.

Înaintea folosirii acestui procedeu trebuie relatat un mic exemplu. Mai întâi se creează un scurt, dar foarte scurt mesaj, apoi alegem valorile pentru ceilalți parametrii necesari. Se trimite mesajul așa cum ar proceda un expeditor și de asemenea se decriptează așa cum ar proceda cei care primesc mesaje, iar în cele din urmă se încercă să se intercepteze mesajul așa cum ar face un criptanalist și se va vedea cât de dificil este.

Cum se interceptează un mesaj?

Un criptanalist care primește mesajul c nu-l va putea decripta fără a cunoaște inversa d a lui e (mod (p–1)(q–1)). Criptanalistul oricum nu cunoaște nici măcar modulul (p–1)(q–1) deoarece p și q sunt necunoscute pentru el, doar destinatarul cunoscându-le, iar cunoscând doar produsul n = pq este insuficient. Criptanalistul este forțat să obțină un algoritm de factorizare a numerelor mari într-un timp polinomial, eforturile lui putând avea succes.

Este de remarcat faptul că destinatarul are o mare problemă de calcul în alegerea celor două numere prime p și q, însă dacă reușește ar fi mult mai ușor în procesul de decriptare. Mai întâi p și q va trebui să aibă doar jumătate din biții care îi are n, iar în al doilea rând trebuie știut că există metode care produc numere mari prime.

Eleganța criptosistemului RSA determină câteva remarci care intenționează să pună în evidență diferența între complexitățile timpului exponențial și al celui polinomial de execuție.

Cât de grea poate fi factorizarea unui număr mare întreg? Numerele întregi sau chiar și un cuplu de numere de o sută de zecimale pot fi apropiate cu puțină confidențialitate încât factorizarea va fi realizată în câteva ore de către o mașină de calcul rapidă. Dacă se gândește în termenii mesajului, care ar putea avea lungimea unei pagini, atunci mesajul va avea 8000 de biți, echivalentul a 2400 de numere zecimale.

Cât de grea poate fi depistarea inversei multiplicative, mod (p–1)(q–1)? Dacă p și q sunt cunoscute atunci este foarte ușor să găsim inversa mod n, iar aflarea ei nu este mai dificilă decât realizarea algoritmul lui Euclid extins.

4.3 Factorizarea numerelor mari

Problema determinării divizorilor numerelor mari întregi are mult mai multe condiții decât testarea primalității. De exemplu, nu se cunoaște nici un algoritm probabilistic care să returneze un factor al unui număr mare întreg compus, cu probabilitatea mai mare decât jumătate dintr-un timp polinomial.

În continuare vom prezenta un algoritm probabilistic de factorizare care găsește factori într-un timp mediu moderat doar exponențial, și anume timpul prezent.

Fie n un număr întreg a cărui factorizare dorim să o aflăm.

Definiție: Prin bază de factori B se înțelege o mulțime de numere întregi diferite și nenule {b0, b1,…, bn}.

Definiție: Fie B o bază de factori. Un întreg c se va numi număr-B dacă este definit de condițiile

(a) c ≡ a2 (mod n)

și

(b) –n/2 ≤ c ≤ n/2

poate fi scris ca un produs de factori din B.

Dacă se ia e(a, i) ca exponent pentru bi, atunci vom avea

a2 =

Deci pentru fiecare număr-B vor fi (h+1) exponenți vector e(a).

Se presupune că se pot determina suficiente numere-B și deci mulțimea vectorilor exponenți este liniar dependentă (mod 2). Pentru început mulțimea de (h+2) numere-B va avea cu siguranță această proprietate.

Apoi, se poate reprezenta vectorul zero ca sumă de aceleași mulțimi A de vectori exponenți în felul următor

.

Acum se definesc numerele întregi

, i = 0, 1,…, h.

u = (mod n)

v =

Se deduce că u2 ≡ v2 (mod n). Deci u–v sau u+v au un factor în comun cu n. Rezultă că u ≡ ±v (mod n). Dacă u ≡ v (mod n) sau u ≡ –v (mod n) nu este niciuna adevărată și atunci vom găsi un factor al lui n și anume cmmdc(u–v,n) sau cmmdc(u+v,n).

Exemplul 4.6:

Se consideră baza de factori B = {–2, 5} și trebuie să găsim un factor al lui n = 1729. Se presupune că 186 și 267 sunt numere-B. Cum 1862 = 20∙1729 +
(–2)4 și 2762 = 41∙1729 + (–2)4∙52 rezultă deci că 186 și 267 sunt numere-B.

Vectorii exponenți ai lui 186 și 167 sunt (4,0) și respectiv (4,2), deci se găsește că

u = 186×267 ≡ 1250 (mod n)

r1 = 4, r2 = 1

v = (–2)4∙51 = 80

cmmdc(u-v,n) = cmmdc(1170, 1729) = 13

și am găsit factorul 13 al lui 1729.

Trebuie intuită alegerea lui 186 și 267 ca numere-B. De fapt, precum algoritmul a fost implementat de către autorii săi, se aleg simplu și uniform numere întregi aleator între 1 și n–1 până când suficiente numere-B au fost găsite, deci vectorii exponențiali fiind liniar dependenți mod 2.

Se poate dovedi că dacă n nu este o putere primă cu alegerea corectă a lui h relativă la n, dacă se repetă aleatoriu alegerile până când un factor al lui n este găsit atunci timpul mediu va fi

exp{(2+o(1))ln5(ln(ln n))}.

Nu este un timp polinomial, însă este moderat exponențial.

4.4 Criptanaliza și factorizarea

Nu există rezultate formale care să indice necesitatea factorizării lui n în criptanaliza unui sistem RSA. Este foarte posibil ca activitatea de criptanaliză să fie realizată prin metode complet diferite. Pe de altă parte, dacă aceste metode dezvăluie câteva elemente ale trapei secrete, atunci ele conduc de asemenea spre factorizarea rapidă a lui n. Acest lucru va fi prezentat în continuare.

Lemă: Orice algoritm folosit pentru calcularea lui φ(n) poate fi aplicat fără o creștere a complexității sale, la factorizarea lui n.

Demonstrație: Factorul p poate fi calculat imediat din ecuațiile

p+q = n–φ(n)+1

și

p–q =.

Se presupune că există o metodă pentru a calcula exponentul de decriptare d. Să arătăm cum poate fi folosită această metodă pentru factorizarea lui n. Logaritmul de factorizare va fi probabilistic, iar probabilitatea de eșec va fi făcută arbitrar de mică. Complexitatea noului algoritm nu este mai mică decât cea a algoritmului de calcul al lui d. Desigur, complexitatea noului algoritm depinde de probabilitatea fixată, dar pentru orice probabilitate, noul algoritm lucrează în timp polinomial, dacă algoritmul pentru calculul lui d lucrează în timp polinomial.

Teorema 4.1: Un algoritm pentru căutarea lui d poate fi convertit într-un algoritm probabilistic pentru factorizarea lui n.

Demonstrație: Demonstrația se bazează pe idei despre numere pseudo-prime și respectiv pseudo-prime tari. Vor fi folosite numere w care satisfac condițiile 1≤w<n și (w, n) = 1. Aceste condiții nu vor mai fi repetate, dar trebuie ținute minte. Este evident că dacă o alegere aleatoare a lui w<n satisface (w, n)>1, atunci n se poate factoriza imediat. Acest lucru se poate întâmpla și în cazul în care s-ar găsi o soluție netrivială a lui 1(mod n), adică un număr u cu proprietățile:

u±1 (mod n)

și

u2 ≡ 1(mod n)

Atunci (u+1)(u–1) este divizibil prin n, dar factorii nu sunt, și deci cmmdc(u+1, n) este egal fie cu p fie cu q. Deoarece algoritmul dat calculează pe d, se poate obține imediat ed–1 sub forma

ed–1 = , unde s≥1 și r este impar.

Deoarece ed–1 este un multiplu al lui φ(n), se obține congruența:

≡ 1(mod n), pentru un w oarecare.

În consecință există un număr s′, cu 0 ≤ s ′≤ s, astfel încât s′ este cel mai mic număr pentru care congruența

≡ 1(mod n)

este adevărată.

Dacă

s′>0

și

,

atunci s-a găsit deja o rădăcină pătrată netrivilă a lui 1(mod n) și deci s-a terminat demonstrația.

Se presupune că nu este satisfăcută relația de mai sus, adică se obține

wr ≡ 1(mod n)

sau

≡ –1(mod n)

pentru un număr t, cu 0≤t<s. Prima congruență arată că s-a putut reduce s′ la 0 fără a se întâlni nici o necongruență cu 1, iar a doua, că valoarea s′–1 = t produce ceva congruent cu –1.

Se determină acum o limită superioară pentru numerele w care satisfac relația de mai sus. Astfel de numere w sunt nedorite din punct de vedere al factorizării în timp, dorite fiind numerele w care satisfac relația

s′>0

și

–1 (mod n).

Se pot gândi numerele p–1 și q–1 ca fiind scrise sub forma

p–1 = 2ia

și

q–1 = 2jb, unde a și b sunt impare.

Se presupune că i≤j, fără pierderea generalității. Deoarece este un multiplu al lui φ(n), r este de asemenea un multiplu al lui ab . Deci dacă t ≥ i atunci este un multiplu al lui p–1, și în consecință

≡ 1 (mod n).

Din aceasta se obține apoi

–1 (mod p),

conducând la

–1 (mod n).

Aceasta înseamnă că relația

wr ≡ 1(mod n)

sau

≡ –1(mod n)

nu este satisfăcută niciodată pentru t ≥ i. Deoarece este evident că i<s, putem scrie relația de mai sus sub forma echivalentă

wr ≡ 1(mod n)

sau

≡ –1(mod n),

pentru un t care verifică 0≤t<i.

Se estimează acum numărul valorilor lui w care satisfac congruența wr ≡ 1(mod n). Fie un g astfel încât w ≡ gu(mod p). Trebuie specificat că în această demonstrație se vorbește despre numere care sunt imposibil de calculat. Astfel de numere sunt folosite numai pentru a justifica algoritmul și nu apar în execuție. Evident fiecare din congruențele

wr ≡ 1(mod p)

și

ur ≡ 0(mod p–1)

o implică pe cealaltă. Rezultă că aceste congruențe au același număr de soluții pentru necunoscutele w și u. Numărul soluțiilor pentru a doua congruență este r(p–1) = a. Deci a este numărul soluțiilor și pentru prima congruență.

În același mod se constată că b este numărul soluțiilor pentru congruența
wr ≡ 1(mod q). Rezultă că că ab este numărul soluțiilor congruenței wr ≡ 1(mod n).

Se observă că fiecare pereche de soluții formată dintr-o soluție a congruenței
mod p și o soluție a congruenței mod q, conduce la o soluție pentru congruența mod n, conform Lemei Chineze a Resturilor. Există în total ab astfel de perechi.

Se estimează în al doilea rând, numărul valorilor lui w care satisfac cea de a doua condiție ≡ –1(mod n). Raționând ca mai înainte se deduce că numărul soluțiilor w pentru congruența

≡ 1(mod p) ( respectiv ≡ 1(mod p))

este egal cu cmmdc(2t+1r, p–1) = 2t+1a (respectiv ). Aceasta rezultă din faptul că .

În consecință numărul soluțiilor pentru congruența

≡ –1(mod p)

este cel mult .

În același mod se ajunge la concluzia că numărul soluțiilor pentru congruența

≡ –1(mod q)

este cel mult (acum inegalitatea i ≤ j este necesară: t + 1 ≤ i ≤ j). Aceasta implică faptul că numărul soluțiilor w pentru congruența

≡ –1(mod n)

este cel mult .

În continuare este dată o limită superioară pentru numărul valorilor nedorite ale lui w. O astfel de limită se obține prin adunarea numărului soluțiilor pentru cele două congruențe de mai sus, al doilea număr fiind suma după valorile posibile ale lui t .

S-a folosit aici faptul că 1 ≤ i ≤ j. Deoarece φ(n) este numărul tuturor valorilor posibile pentru w, cel mult 50% din ele sunt nedorite. Aceasta înseamnă că după k testări ale lui w, probabilitatea de a nu găsi numărul w dorit este cel mult și va converge rapid spre 0.

În demonstrația de mai sus se pot considera ca dorite și numerele w pentru care cmmdc(w, n)>1. Rezultă că numărul tuturor valorilor posibile pentru w este n+1, din care φ(n)/2 este mai mic de 50%. Cu toate acestea prezenta îmbunătățire a estimării este neglijabilă, întrucât numerele w cu cmmdc(w, n)>1 sunt excepții rare.

Teorema mai poate fi enunțată și sub forma: orice algoritm determinist în timp polinomial pentru calcularea lui d poate fi convertit într-un algoritm determinist polinomial în timp pentru factorizarea lui n.

Strategia sistemului RSA este de asemenea aplicabilă și în situația în care, atât modulele cât și exponenții de criptare și de decriptare sunt distribuiți de către o agenție în care toate părțile implicare au încredere. Fie agenția publică, un modulo n, comun pentru toată lumea, precum și exponenții de criptare eA, eB,… pentru utilizatorii A, B,…. În plus agenția distribuie utilizatorilor, individual, exponenții secreți de decriptare dA, dB,…. Numerele prime p și q sunt cunoscute numai de către agenție. Această procedură este vulnerabilă în sensul teoremei prezentate în continuare. Metoda este similară cu cea a teoremei precedente, iar rezultatul poate fi privit ca un exemplu de criptanaliză fără factorizarea lui n.

Teorema 4.2: În situația descrisă anterior, orice utilizator poate găsi exponentul secret de decriptare al altui utilizator determinist, printr-o funcție de timp pătratică (fără a factoriza pe n).

Demonstrație: Se va arăta cum B poate să găsească exponentul dA. Pentru un număr k vom avea

B nu îl știe pe k, m, dar cunoaște și n. Fie t cel mai mare număr care divide pe eB dB − 1 și având un factor comun netrivial eA. Se notează

,

unde

.

Nu se poate alege pentru că, de exemplu, pătratul unui factor al lui eA poate divide . Cu toate acestea există un algoritm simplu determinist, care lucrează în timp pătratic pentru calcularea lui t și α. De fapt, se notează

,

și se definește inductiv , pentru

, (gi , eA)=hi .

Pentru hi =1, evident și .

Pentru se obține . Aceasta înseamnă că hi =1 se poate afla într-un număr liniar de pași. La fiecare pas este apelat algoritmul lui Euclid, obținându-se în total un timp pătratic.

B calculează acum, pe baza algoritmului lui Euclid pe a și b astfel încât:

,

unde b este ales ca fiind pozitiv. Se observă că φ(n) divide pe α pentru că , iar k / t este un număr întreg pentru că (t, φ(n))=1. Cea de a doua ecuație rezultă din faptul că (eA, φ(n))=1, iar t este un produs de numere, nici unul din ele neavând un factor comun netrivial cu φ(n). Această observație implică congruența

.

și din acest motiv b (mod n) poate fi folosit ca dA.

4.5 Demonstrarea primalității

Se va considera o problemă care seamănă mult cu un test de primalitate, dar există o diferență în realitate deoarece regulile sunt diferite. Problema care se pune este de a demonstra că un anumit întreg este prim, având nevoie de el pentru a face suma calculelor în ordinea demonstrării lor.

Mai întâi se presupune că sunt scrise o sută de numere întregi zecimale n pe o tablă în fața unui public numeros, și se dorește să se demonstreze că n nu este prim.

Dacă se scriu mai jos două numere întregi mai mici al căror produs este n, demonstrația s-ar încheia. Oricine dorește să fie sigur poate petrece câteva minute înmulțind factorii și verificând dacă produsul lor este n, și astfel toate dubiile vor dispărea.

Într-adevăr un participant la o conferință de matematică în 1903 anunța că 267–1 nu este un număr prim, și pentru a fi total convins de ceea ce a afirmat a scris

267–1 = 193707721 × 761838257287.

Acesta probabil a muncit foarte mult găsească acești factori, dar găsindu-i a devenit complet sigur să-i convingă și pe alții de adevărul rezultatelor afirmate.

O pereche de numere întregi r, s pentru care r≠1, s≠1 și n=rs este o confirmare a descompunerii lui n. Această confirmare se notează cu C(n) și atunci în algoritm se vor urma următorii pași:

(1) se verifică dacă r≠1 și s≠1

(2) se verifică dacă rs=n

Se poate dovedi în timp polinomial că n nu este un număr prim.

Acum urmează ceea ce este mai greu. Cum se poate demonstra că un anumit întreg este număr prim? Regulile spun că trebuie știut să se facă orice sumă mare de calcule dinainte, și rezultatele calculului pot fi scrise ca o funcție de certificare C(n) care însoțește întregul n. Publicul va trebui să facă doar o sumă polinomială a mai multor calcule realizate în ordine pentru a se convinge că n este prim.

În continuare va fi descris un algoritm A de verificare a primalității cu următoarele proprietăți:

în cadrul algoritmului se dau întregul n și funcția sa de certificare C(n)

dacă n este prim, atunci în urma algoritmului datele de intrare (n,C(n)) va avea ca rezultat datele de ieșire „n este prim”

dacă n nu este prim atunci pentru orice C(n) datele de intrare (n,C(n)) vor avea ca rezultat datele de ieșire „primalitatea lui n nu este verificată”

algoritmul A rulează în timp polinomial

Acum întrebarea este dacă există vreo procedură pentru verificarea existenței primalității. Răspunsul este afirmativ și în continuare va fi descris un astfel de caz. Faptul că primalitatea poate fi verificată rapid, dacă nu e descoperită repede, are o mare importanță. Lema următoare este un fel de a discuta „mica teoremă a lui Fermat”.

Lemă: Fie p un număr întreg pozitiv. Se presupune că există un număr întreg pozitiv x astfel încât și pentru toți divizorii d ai lui p–1, d<p-1, se știe că xd nu este congruent cu 1 (mod p). Atunci p este prim.

Demonstrație: Mai întâi se demonstrează că cmmdc(x, p)=g=1. Apoi x=gg’, p=gg″. Deoarece avem și . Membrul din dreapta este multiplu al lui g. Membrul din stânga nu este, deci g=1. Urmează că = grupul unităților lui Zp. Atunci x este un element de ordinul p-1 într-un grup de ordinul . Deci . Dar mereu .Deci =p-1 și p este prim.

Această lemă se bazează pe metoda lui Pratt de construcție a funcției de certificare a primalității. Construcția acestei funcții este de fapt recursivă de la pasul 30 până la apelarea ei pentru numerele mici.

Se presupune că funcția de certificare a numărului mic 2 este un caz trivial și de aceea poate fi verificat imediat.

În continuare este prezentată o listă completă cu informații despre C(p) care însoțește un întreg p a cărui primalitate este atestată la:

10. o listă a numerelor prime pi și a exponenților ai , pentru factorizarea canonică

20. funcția C(pi) a fiecărui număr prim

30. un număr pozitiv întreg x

Pentru a verifica că p este prim se poate executa următorul algoritm B:

(B1) verifică p−1 =

(B2) verifică dacă fiecare pi folosind funcția C(pi), i=1,2,…, r

(B3) pentru fiecare divizor d al lui p-1, d < p-1 verifică xd nu este congruent cu
1 (mod p)

(B4) verific 1(mod p)

Acest algoritm este corect, dar nu se execută în timp polinomial. La pasul (B3) se uită la fiecare divizor al lui p-1, și sunt probabil foarte mulți.

Din fericire nu este necesar să se verifice fiecare divizor al lui p-1. Nu vor exista probleme provenite din faptul că „există un divizor d al lui p-1, d < p-1 pentru fiecare 1(mod p) dacă și numai dacă există un astfel de divizor care are forma specială d=(p-1)/pi” .

Verificarea primalității algoritmului A se face în felul următor:

(A1) se verifică dacă p−1 =

(A2) se verifică dacă fiecare pi este prim , folosind funcția C(pi), i=1,2,…,r.

(A3) pentru fiecare i de la 1 la r se verifică dacă .

(A4) se verifică dacă 1(mod p)

Se va analiza în continuare complexitatea algoritmului A. Pentru aceasta se va defini complexitatea în funcție de timpul necesar realizării unui calcul de genul (a) „este ? ” sau (b) „ este ? ”.

Fie f(p) acest timp. Va rezulta f(p) = 1 + și fiecare dintre cei patru termeni din dreapta corespund celor patru pași din algoritm. Suma începe cu i=2 deoarece numărul prim 2, care este întotdeauna un divizor al lui p-1 este „liber”. Acum relația de mai sus poate fi scrisă ca , unde g(p)=1+f(p). Se afirmă că , pentru toți p. Este cu siguranță adevărat dacă p=2.

Dacă este adevărat pentru numere prime mai mici decât p, atunci va rezulta că

g(p) ≤ 4 += 4 + ≤ 4 + 4 log2((p-1)/2) = 4 log2(p-1) ≤

4 log2 p

Deci f(p) pentru toți p≥2.

Deoarece numărul de biți ai lui p este , numărul f(p) este numărul de execuție al pașilor care este polinomial în lungimea șirului biților de intrare. Există exerciții de verificare pentru fiecare pas pentru care determinarea lui f(p) este executată în timp polinomial, deci întreaga verificare a primalității produce operații în timp polinomial.

ANEXĂ

(Programe C++)

//Testul de primalitate FERMAT

#include<conio.h>

#include<stdio.h>

#include<iostream.h>

#include<iomanip.h>

#include<math.h>

#include<stdlib.h>

int n,i,j,t,r,a[100];

void Baza_10_2(int n, int a[100],int &k)

{

int j,deimp=n,cat,aux;

k=-1;

do

{

cat = deimp/2;

a[++k] = deimp%2;

deimp = cat;

}

while(deimp); //deimp nenul

}

int Alg1(int m,int b, int n)//det b^n (mod m)

{

int j,k,a[100];

unsigned long A[100],x[100];

for(j=0;j<=k;j++)

{

if(n==0) {

x[j]=1;

cout<<"r="<<x[j];

}

else {

Baza_10_2(n,a,k);

cout<<" j: ";

for(j=0;j<=k;j++) cout<<setw(5)<<a[j];

cout<<endl;

A[0]=b;

if(a[0]==1) x[0]=b;

else x[0]=1;

for(j=1;j<=k;j++)

{

A[j]=(A[j-1]*A[j-1])%m;

if(a[j]==1) x[j]=(A[j]*x[j-1])%m;

else x[j]=x[j-1];

}

cout<<"A[j]: ";

for(j=0;j<=k;j++)

cout<<setw(5)<<A[j];

cout<<"\n";

cout<<"x[j]: ";

for(j=0;j<=k;j++)

cout<<setw(5)<<x[j];

cout<<"\n r="<<x[k]<<"\n";

}

}

return x[k];

}

void main()

{

clrscr();

int grup=8;

randomize();

do

{

cout<<"\ndati numarul de itratii t > 1: ";cin>>t;

}

while (t<=1);

do

{

cout<<"\nDati n (impar>2): ";cin>>n;

}

while (n%2==0 || n<=2);

for(i=1;i<=t;i++)

{

if (wherey()+grup>=50) {getch(); clrscr();}

a[i]=random(n-3)+2;

cout<<"\n\nLa iteratia "<<i<<":";

cout<<"\n–––––";

cout<<"\na["<<i<<"]="<<a[i]<<"\n";

r = Alg1(n,a[i],n-1);

if(r!=1) cout<<"Numarul "<<n<<" este COMPUS\n";

else cout<<"Numarul "<<n<<" este PRIM\n";

}

getch();

}

//Test probabilistic de primalitate Miller-Rabin

#include<conio.h>

#include<stdio.h>

#include<iostream.h>

#include<iomanip.h>

#include<math.h>

#include<stdlib.h>

int n,i,j,t,r,s,y[100],a[100];

void Baza_10_2(int n, int a[100],int &k)

{

int j,deimp=n,cat,aux;

k=-1;

do

{

cat = deimp/2;

a[++k] = deimp%2;

deimp = cat;

}

while(deimp); //deimp nenul

}

int Alg1(int m,int b, int n)//det b^n (mod m)

{

int j,k,a[100];

unsigned long A[100],x[100];

for(j=0;j<=k;j++)

{

if(n==0) {

x[j]=1;

cout<<"r="<<x[j];

}

else {

Baza_10_2(n,a,k);

cout<<" j: ";

for(j=0;j<=k;j++) cout<<setw(5)<<a[j];

cout<<endl;

A[0]=b;

if(a[0]==1) x[0]=b;

else x[0]=1;

for(j=1;j<=k;j++)

{

A[j]=(A[j-1]*A[j-1])%m;

if(a[j]==1) x[j]=(A[j]*x[j-1])%m;

else x[j]=x[j-1];

}

cout<<"A[j]: ";

for(j=0;j<=k;j++)

cout<<setw(5)<<A[j];

cout<<"\n";

cout<<"x[j]: ";

for(j=0;j<=k;j++)

cout<<setw(5)<<x[j];

// cout<<"\nr="<<x[k]<<"\n";

}

}

return x[k];

}

void main()

{

int grup=8;

clrscr();

randomize();

do

{

cout<<"\nDati numarul de itertii r>1: ";cin>>r;

}while(r<=1);

do

{

cout<<"\nDati n (impar>2) :";cin>>n;

} while (n%2==0 || n<=2);

s=0;

int aux=n-1; //par > 2

do

{

s++;

aux=aux/2;

}while(aux%2==0);

t=aux; //de ex pt n=13, s=2 si t=3

cout<<"\ns="<<s<<"\n";

cout<<"t= "<<t<<"\n\n";

for(i=1;i<=r;i++)

{

if (wherey()+grup>=50) {getch(); clrscr();}

cout<<"\n\nLa iteratia "<<i<<":\n";

cout<<"–––––\n" ;

a[i]=random(n-3)+2;

cout<<"\na["<<i<<"]="<<a[i]<<"\n\n";

y[i] = Alg1(n,a[i],t);

cout<<"\n\ny["<<i<<"]="<<y[i]<<"\n";

if(y[i]!=1&&y[i]!=(n-1))

{ j=1;

while(j<=(s-1)&&y[i]!=n-1)

{

y[i]=(y[i]*y[i])%n;

if(y[i]==1)

{

cout<<"\n===> n este compus – stop iteratii !";

getch(); return;

}

j++;

}

if(y[i]!=n-1)

{

cout<<"\n===> n este compus – stop iteratii !";

getch(); return;

}

}

}

cout<<"\n\n===> n este prim ";

getch();

}

//Test de primalitate Lucas-Mersenne

#include<stdio.h>

#include<conio.h>

#include<iostream.h>

#include<stdlib.h>

#include<math.h>

int s,i,k,u;

unsigned long n;

void main()

{

clrscr();

do

{

cout<<"\ns=";cin>>s;

}

while (s<3);

n=pow(2,s)-1;

cout<<"\nNumarul Mersenne 2^s-1 este n = "<<n<<"\n";

for(i=2;i<=sqrt(s);i++)

{

if(s%i==0)

{

cout<<"\n"<<i<<" este divizor al lui "<<s;

cout<<"\n\n====> n = "<<n<< " este numar compus ! ";

getch(); return;

}

}

u=4;

for(k=1;k<=s-2;k++)

u=((u*u)-2)%n;

//cout<<"\nu="<<u;

if(u==0) cout<<" \n\n====> n = "<<n<<" numar prim !";

else cout<<"====> n = "<<n<<" compus";

getch();

}

//Criptare si decriptare RSA

//foloseste un alfabet de 10 elemente, numerele de la 0-9

#include<string.h>

#include<conio.h>

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

#include<iomanip.h>

#include<iostream.h>

FILE *f,*g;

int p,q,e,d;

unsigned long n;

int Prim(int n)

{

if (n<=1) return 0;

for (int i=2;i<=sqrt(n);i++)

if(!(n%i)) return 0;

return 1;

}

int PrimeIntreEle(int m, int n)

{

//cmmdc=1;

int deimp=m,imp=n,rest;

do{

rest = deimp%imp;

deimp = imp;

imp = rest;

}

while(imp!=0);

return (deimp==1);

}

void GenerareE(int &e)

{

do { e = random((p-1)*(q-1))+1; } while(!PrimeIntreEle(e,(p-1)*(q-1)));

}

void GenerareDEuclid(int a, int b, int d,int *x, int *y) //dc cmmdc<=1 inversa lui e mod(m) este x, altfel nu exista

{

if (b == 0) {

d = a;

*x = 1;

*y = 0;

}

else {

int x0, y0;

GenerareDEuclid(b, a % b, d, &x0, &y0);

*x = y0;

*y = x0 – (a / b) * y0;

}

}

int imparteMesajul(char * strMesaj, char ** strBloc)

{

const grup = 3; // nr. de caractere in grup

int lungime = strlen(strMesaj); // lungimea stringului

int pozitia = 0; // pozitia caracterului in string

int count = grup;

int element = 0; //indexul elementului din string

char strCompletZero[grup]; // completeaza cu zero

if (lungime > 0) {

memset(strCompletZero, (char)'0', grup -1); // completeaza cu "0"

while (pozitia + count <= lungime)

{

strncpy(strBloc[element], strMesaj, count);

strBloc[element][count] = 0; //zero terminate string

strMesaj += count; //advance the pointer position

pozitia += count; //advance current char index

element ++; //next item

}

count = lungime – pozitia; // nr. de caractere ramase

if (count > 0) // daca ultimul bloc are mr de caractere < 3, completeaza cu "0"

{

strCompletZero[grup – count] = 0; //seteaza lungimea completZero

sprintf(strBloc[element], "%s%s", strCompletZero, strMesaj); //formateaza sirul

strBloc[element][pozitia] = 0; // zero termina sirul

}

}

return element; //returneaza nr de elemente

}

void Baza_10_2(int n, int a[100],int &k)

{

int j,deimp=n,cat,aux;

k=-1;

do {

cat = deimp/2;

a[++k] = deimp%2;

deimp = cat;

}

while(deimp); //deimp nenul

}

int Alg1(int m,int b, int n)//det b^n (mod m)

{

int j,k,a[100];

unsigned long A[100],x[100];

for(j=0;j<=k;j++)

{

if(n==0) {

x[k]=1;

printf("%ld",x[k]);break;

}

else {

Baza_10_2(n,a,k);

for(j=0;j<=k;j++) A[0]=b;

if(a[0]==1) x[0]=b;

else x[0]=1;

for(j=1;j<=k;j++)

{

A[j]=(A[j-1]*A[j-1])%m;

if(a[j]==1) x[j]=(A[j]*x[j-1])%m;

else x[j]=x[j-1];

}

printf("%ld",x[k]);

}

}

return x[k];

}

void main()

{

clrscr();

int x,y;

char strMesaj[500]= "6882326879666683";

char ** strBloc = (char **) new char[500];

char strMesajDecriptat[500],strAuxiliar[10];

int ValoriMD[500];

int nr;

p=47;

q=71;

randomize();

printf(" p = %d",p);

printf("\n q = %d",q);

n=p*q;

printf("\n\n n = p*q = %u \n",n);

printf("\n(p-1)(q-1) = %u",(p-1)*(q-1));

GenerareE(e);

printf("\n\n e = %d (cheie de criptare)",e);

GenerareDEuclid(e,(p-1)*(q-1),1,&x,&y);

printf("\n d = %d (cheie de decriptare)",x);

while(x<=0){

GenerareE(e);

printf(" // d este negativ, generam un elt e\n");

printf("\n e = %d (cheie de criptare)",e);

GenerareDEuclid(e,(p-1)*(q-1),1,&x,&y);

printf("\n d = %d (cheie de decriptare) ",x);

}

printf("\n_______________________________________________________________________ \n ");

printf(" \nMesajul INITIAL este: ");

printf(strMesaj);

printf("\n_______________________________________________________________________ \n ");

printf("\n");

if(strlen(strMesaj)%3==0) nr=(strlen(strMesaj)/3)-1;

else nr=strlen(strMesaj)/3;

strcpy(strMesajDecriptat,"");

for (int i = 0; i <= nr; i++)

{

strBloc[i] = new char[nr]; //strBloc[i][nr] = 0;

imparteMesajul(strMesaj, strBloc);

printf("\n");

printf(" m[%d]=",i);

printf(strBloc[i]);

int val=atoi(strBloc[i]);

printf(" c[%d]=",i);

int c= Alg1(n,val,e);

printf(" md[%d]=",i);

ValoriMD[i] = Alg1(n,c,x);

}

printf("\n");

printf("\n_______________________________________________________________________ \n ");

printf("\nMesajul CRIPTAT este: ");

for( i=0;i<=nr;i++)

{

int val=atoi(strBloc[i]);

printf(" ");

Alg1(n,val,e);

}

printf("\n");

printf("\n_______________________________________________________________________ \n ");

printf("\nMesajul DECRIPTAT este: ");

for( i=0;i<=nr;i++)

{

printf("%d ",ValoriMD[i]);

}

printf("\n");

printf("\n_______________________________________________________________________ \n ");

getch();

}

//Criptare si decriptare RSA

//foloseste un alfalet de 40 elemente, litere A-Z, cifre 0-9,si caracterele: "$"," ","?",".";#include <stdio.h>

#include <string.h>

#include <conio.h>

#define BITS_PER_LONG 32

#define BITS_PER_LONG_1 31

#define SIZE 32

struct factor {long expon, prime;};

long get_bit(long i, long *sita)

{

long b = i % BITS_PER_LONG;

long c = i / BITS_PER_LONG;

return (sita[c] >> (BITS_PER_LONG_1 – b)) & 1;

}

void set_bit(long i, long v, long *sita)

{

long b = i % BITS_PER_LONG;

long c = i / BITS_PER_LONG;

long maska = 1 << (BITS_PER_LONG_1 – b);

if (v == 1)

sita[c] |= maska;

else

sita[c] &= ~maska;

}

void Sita(long n, long *sita)

{

long c, i, inc;

set_bit(0l, 0, sita);

set_bit(1l, 0, sita);

set_bit(2l, 1, sita);

for (i = 3; i <= n; i++)

set_bit(i, i & 1, sita);

c = 3;

do {

i = c * c, inc = c + c;

while (i <= n) {

set_bit(i, 0, sita);

i += inc;

}

c += 2;

while (!get_bit(c, sita)) c++;

} while (c * c <= n);

}

void factor(long n, long *sita, struct factor *f, long *count)

/* factor using trial division */

{

int one = 0;

long e, p = 2;

*count = 0;

while (!one) {

while (!get_bit(p, sita)) p++;

if (n % p == 0) {

e = 0;

do {

e++;

n = n / p;

} while (n % p == 0);

f[*count].expon = e;

f[*count].prime = p;

*count = *count + 1;

one = n == 1;

}

p++;

}

}

long Alg_Euclid_Extins(long b, long n)

{

long b0 = b, n0 = n, t = 1, t0 = 0, temp, q, r;

q = n0 / b0;

r = n0 – q * b0;

while (r > 0) {

temp = t0 – q * t;

if (temp >= 0) temp = temp % n;

else temp = n – (- temp % n);

t0 = t;

t = temp;

n0 = b0;

b0 = r;

q = n0 / b0;

r = n0 – q * b0;

}

if (b0 != 1) return 0;

else return t % n;

}

long exp_mod(long x, long b, long n)

/* returns x ^ b mod n */

{

long a = 1, s = x;

while (b != 0) {

if (b & 1) a = (a * s) % n;

b >>= 1;

if (b != 0) s = (s * s) % n;

}

return a;

}

long gcd(long a, long b)

{

long r;

while (b != 0)

r = a % b, a = b, b = r;

return a;

}

char transformare_mesaj_criptat(long c)

{

if (c < 26) return (char) (c + 'A');

if (c >= 30 && c <= 39) return (char) (c – 30 + '0');

if (c == 26) return ' ';

if (c == 27) return '.';

if (c == 28) return '?';

return '$';

}

long transformare_mesaj_initial(char p)

{

if (p >= 'A' && p <= 'Z') return p – 'A';

if (p >= '0' && p <= '9') return p – '0' + 30;

if (p == ' ') return 26;

if (p == '.') return 27;

if (p == '?') return 28;

else return 29;

}

void main(void)

{

clrscr();

char mesaj_criptat[128];

char mesaj_initial[64] = "REPORTUL LA LOTTO ESTE DE $7500 ";

long N = 40, c, d, e = 179, i, j, n = 2047, p, q;

long count, phi, sita[256];

struct factor f[32];

Sita(n, sita);

for (i = 0, j = 0; i < strlen(mesaj_initial); i += 2, j += 3) {

p = N * transformare_mesaj_initial(mesaj_initial[i])

+ transformare_mesaj_initial(mesaj_initial[i + 1]);

c = exp_mod(p, e, n);

mesaj_criptat[j] = transformare_mesaj_criptat(c / (N * N));

c %= N * N;

mesaj_criptat[j + 1] = transformare_mesaj_criptat(c / N);

mesaj_criptat[j + 2] = transformare_mesaj_criptat(c % N);

mesaj_criptat[j + 3] = '\0';

}

printf("\nCRIPTAREA: \n–––––––––––––––––––––––––-");

printf("\nMesajul initial este: ");

printf("%s\n", mesaj_initial);

printf("\nSe cunosc:\n\n n =%ld (modulul public)\n e =%ld (cheia de criptare) \n\n ",n,e);

printf("\nMesajul criptat este: ");

printf("%s\n", mesaj_criptat);

factor(n, sita, f, &count);

p = f[0].prime;

q = f[1].prime;

printf("\n–––––––––––––––––––––––––\n\n");

printf("\n DECRIPTAREA: \n–––––––––––––––––––––––––");

printf("\n\nSe descompune n=%ld in doi factori primi p si q, n=p*q \n\n",n);

printf("n = %ld = %ld * %ld ", n, p, q);

printf(" ===> p =%ld si q = %ld \n\n",p,q);

phi = n + 1 – p – q;

d = Alg_Euclid_Extins(e, phi);

printf("e = %ld (cheia de criptare)\n", e);

printf("d = %ld (cheia de decriptare)\n\n", d);

for (i = 0, j = 0; i < strlen(mesaj_criptat); i += 3, j += 2) {

p = N * N * transformare_mesaj_initial(mesaj_criptat[i])

+ N * transformare_mesaj_initial(mesaj_criptat[i + 1])

+ transformare_mesaj_initial(mesaj_criptat[i + 2]);

c = exp_mod(p, d, n);

mesaj_initial[j] = transformare_mesaj_criptat(c / N);

mesaj_initial[j + 1] = transformare_mesaj_criptat(c % N);

mesaj_initial[j + 2] = '\0';

}

printf("\nMesajul criptat este: ");

printf("%s", mesaj_criptat);

printf("\n\n\nMesajul decriptat cu cheia d=%ld este: ",d);

printf("%s", mesaj_initial);

printf("\n\n–––––––––––––––––––––––––-\n\n");

getch();

}

//Criptare folosind transformarea afină

#include <stdio.h>

#include <string.h>

#include <conio.h>

void main(void)

{

clrscr();

printf("Mesajul original: ");

char plaintext[32] = "AFARA ESTE PRIMAVARA";

long a = 13, b = 9, c, i, p = 27;

printf("%s\n", plaintext);

printf("\n\nMesajul criptat cu transformarea afina C=a*P+b(mod p),\n\npentru a = %ld, b = %ld este: ",a,b);

for (i = 0; i < strlen(plaintext); i++) {

c = plaintext[i];

if (c == ' ') c = 26; else c -= 'A';

// printf("Mesajul criptat: ");

c = (a * c + b) % p;

printf("%c", c + 'A');

}

printf("\n");

getch();

}

Bibliografie

[1] Herbert S.Wilf, „Algorithms and Complexity”, University of Pennsylvania

Philadelphia, PA 19104-6395

[2] Thomas Cormen, Charles Leiserson, Ronald Rivest, „Introducere în algoritmi”,

Editura Libris Agora, Cluj-Napoca, 2000

[3] Bruce Schneier, „Applied Cryptography”, Second Edition: Protocols, Algorithms, and Source Code in C

[4] A. Menezes, P. van Oorschot, S. Vanstone, „Handbook of Applied Cryptography”, CRC Press, 1996.

[5] Arto Salomaa, „Public Key Cryptography”, Second Edition, Springer 1996

[6] Arto Salomaa, „Criptografie cu chei publice”, Editura Militara, Bucuresti, 1993

[7] Colin Boyd, Anish Mathuria, „Protocols for Authentication and Key Establishment”, Springer 2003

[8] Douglas R. Stinson, „Cryptography Theory and Practice”, Chapman & Hall/CRC 2002

[9] Hans Delfs, Helmut Knebl, „Introduction to Cryptography, Principles and Applications”, Springer 2002

[10] Daniel Ioan Curiac, „Algoritmi de criptare pentru securizarea datelor”, Editura Orizonturi Universitare Timișoara (iunie 2001) – Colecția Calculatoare – Informatică 12

[11] Victor Udrinschi, „Criptografia”, Editura Tipo-Actis, Bucuresti, 1996

[12] Criptare cu chei publice

http://algorex.xhost.ro/articole/No2Art23.pdf

[13] Infrastructura cheilor publice

http://www.dcd.uaic.ro/default.php?t=site&pgid=79

[14] Tehnici de criptare

http://www.ginfo.ro/revista/12_2/serial.pdf

[15] Criptarea cu cheie publică, Cifrul RSA

http://www.ginfo.ro/9_4/07.shtml

[16] Algoritmi criptografici cu cheie publică

http://www.byte.ro/byte95-03/vic.html

[17] Criptografia modernă

http://www.euro.ubbcluj.ro/~alina/cursuri/internet-teorie/5-3.htm

[18] Criptosisteme

http://inf.ucv.ro/~dan/courses/CE2212/tema3.pdf

[19] Algoritmi în teoria numerelor

http://inf.ucv.ro/~dan/courses/I213/I213_CURS.pdf

[20] Algoritmul RSA

http://www.di-mgt.com.au/rsa_alg.html#rsasummary

[21] Descrierea algoritmului RSA

http://pajhome.org.uk/crypt/rsa/rsa.html