Criptare Rsa. Un exemplu de algoritm de criptare rsa. EDS și cheie publică

În a doua parte, ne vom uita la popularul algoritm RSA, în care o cheie publică este utilizată pentru criptare. Dar mai întâi vreau să te avertizez din nou. Codul furnizat în acest articol are doar scop informativ. Criptografia este o zonă foarte vastă și complexă și, pentru a nu avea probleme, nu recomand criptarea informațiilor folosind ambarcațiunile mele.

În a doua parte, ne vom uita la popularul algoritm RSA, în care o cheie publică este utilizată pentru criptare. Dar mai întâi vreau să te avertizez din nou. Codul furnizat în acest articol are doar scop informativ. Criptografia este un domeniu foarte vast și complex și, pentru a nu avea probleme, nu recomand criptarea informațiilor folosind meșteșugul meu.

algoritm RSA

Criptare cu chei publice

Criptarea cu chei publice este folosită peste tot. Dacă ați plătit vreodată ceva online, ați folosit deja această metodă (sper!). Se pune imediat întrebarea cum funcționează această protecție. Dacă introduc numărul cardului meu de credit pentru a cumpăra ceva, de ce nimeni altul decât destinatarul nu poate vedea aceste informații? Îți dau o metaforă. Pentru a deschide seiful, ai nevoie de o cheie (sau de un ciocan, dar din fericire, seifurile și încuietorile sunt protejate de astfel de lucruri). În criptarea folosind o cheie publică, se întâmplă același lucru. Arată încuietoarea pentru ca toată lumea să o vadă, dar doar câțiva aleși au cheia acestei încuietori și este aproape imposibil să deschizi ușa prin alte metode.

RSA este unul dintre algoritmii care implementează schema de mai sus. În plus, putem folosi acest algoritm pentru a verifica autenticitatea identității noastre. Dacă folosiți cheia privată pentru a trimite cuiva un mesaj criptat, destinatarul poate folosi cheia publică pentru a vă decripta mesajul. Această tehnologie vă permite să semnați mesaje și, prin urmare, să confirmați autenticitatea expeditorului.

Program demonstrativ bazat pe algoritmul RSA

Schema Rivest-Shamir-Adleman (RSA) este în prezent singura schemă de criptare a cheii publice acceptată pe scară largă în practică.

Schema RSA este un cifru bloc în care atât textul simplu, cât și textul cifrat sunt numere întregi între 0 și P- 1 pentru unii P.

Textul simplu este criptat în blocuri, fiecare dintre acestea conținând o valoare binară mai mică decât un anumit număr dat P. Aceasta înseamnă că lungimea blocului nu trebuie să depășească log2(“). În practică, lungimea blocului este aleasă egală cu 2 k biţi unde 2k Schema dezvoltată de Rivest, Shamir și Adleman se bazează pe expresii de putere. Criptarea și decriptarea pentru blocul de text simplu M și pentru blocul de text cifrat C pot fi reprezentate prin următoarele formule:

Atât expeditorul cât și destinatarul trebuie să cunoască valoarea P. Expeditorul cunoaște semnificația e,și numai receptorul cunoaște valoarea d. Astfel, această schemă este un algoritm de criptare cu cheie publică KU= (e, p),și cheia privată KR = (d, p).

Pentru ca acest algoritm să fie utilizat pentru criptarea cheii publice, trebuie îndeplinite următoarele cerințe:

Trebuie să existe valori e, dȘi P, ce M ed = M(mod P) pentru toate M n.

Ar trebui să fie relativ ușor de calculat IVT și Din c1 pentru toate valorile lui M p.

Trebuie să fie aproape imposibil de determinat d disponibil ea p.

Vom analiza mai întâi prima cerință și vom lua în considerare restul mai târziu. Este necesar să se găsească o relație a formei

Aici, corolarul din teorema lui Euler se potrivește perfect: pentru oricare două astfel de numere prime RȘi qși astfel de orice două numere întregi Pete, ce n=pqn0 și un număr întreg arbitrar la sunt valabile urmatoarele relatii:

unde φ(n) este funcția Euler a cărei valoare este egală cu numărul de numere întregi pozitive mai mici decât P si coprime cu P.

În cazul simplu RȘi q avem f (pq) - (pag - 1 )(q - unu). Prin urmare, raportul necesar este obținut în condiție

Aceasta este echivalentă cu următoarele relații:

acestea. ea d sunt reciproc inverse modulo φ(n). Rețineți că, conform regulilor de aritmetică din clasele de reziduuri, acest lucru poate fi doar cazul când d(prin urmare e) este coprim cu φ(u). În notație echivalentă (f(/7), d)=.

Acum avem totul pentru a reprezenta schema RSA. Componentele circuitului sunt:

RȘi q- două numere prime (secrete, alese);

p-pq(deschis, calculat);

astfel de e, că (f(i), e)= 1,1 e

d = e l(mod f(/?)) (secret, calculat).

Cheia privată este formată din (d,n), si deschis de la (e, p). Să presupunem că utilizatorul A și-a publicat cheia publică, iar acum utilizatorul B îi va trimite un mesaj M.

Apoi utilizatorul B calculează mesajul criptat

După ce a primit acest text cifrat, utilizatorul A îl decriptează prin calcul

Este logic să oferim aici rațiunea acestui algoritm. Au fost aleși ea d astfel încât

Deci, se pare că kc>(n)+. Dar după corolarul teoremei lui Euler, pentru oricare două astfel de numere prime RȘi qu numere întregi n = pqn M că O relaţiile sunt îndeplinite

De aceea

Acum avem

Tabelul 10.1 rezumă algoritmul RSA, iar în fig. 10.1 prezintă un exemplu de aplicare a acestuia. În acest exemplu, cheile sunt calculate după cum urmează:

1. Se aleg două numere prime: p-7 wq- 17.
2. Calculat p =pq= 7 x 17=119.
3. Calculați f (n) - (p -) (q - 1) = 96.
4. Selectabil e, coprim cu φ (P)= 96 și mai mic decât f(i); în acest caz = 5.
5. Aceasta este definită d, ce de= 1 (mod 96) și d 96. Valoarea corespunzătoare ar fi d= 77, deoarece 77 x 5 = 385 = 4 x 96 + 1.
6. Rezultatul este o cheie publică KU= (5, 119) și o cheie privată KR = (77, 119).

Acest exemplu arată utilizarea acestor chei cu intrarea de text simplu M = 19. Pentru criptare, 19 este ridicat la a cincea putere, rezultând 2 476 099. Împărțirea la 119 are ca rezultat un rest de 66. Prin urmare, 19 119), și astfel textul cifrat va fi 66. După decriptare, se dovedește că

Orez. 10.1.

Tabelul 10.1

Criptarea RSA este unul dintre primele criptosisteme practice cu chei publice care este utilizat pe scară largă pentru transmiterea securizată a datelor. Principala sa diferență față de serviciile similare este că cheia de criptare este publică și diferă de cheia de decriptare, care este ținută secretă. În tehnologie, RSA se bazează pe dificultatea practică a reproducerii factoring a două numere prime mari (problema factoring).

Istoria creației

Numele RSA provine de la literele inițiale ale numelor Rivest, Shamir și Adleman, oamenii de știință care au descris pentru prima dată public numele de familie în 1977. Clifford Cox, un matematician englez care a lucrat pentru serviciile britanice de informații, a dezvoltat pentru prima dată un sistem echivalent în 1973, dar nu a fost desecretizat până în 1997.

Utilizatorul RSA creează și apoi publică o cheie publică bazată pe două numere prime mari împreună cu o valoare auxiliară. trebuie ținut secret. Oricine poate folosi cheia publică pentru a cripta un mesaj, dar dacă este suficient de mare, atunci numai cineva care cunoaște numerele prime poate decoda mesajul. Dezvăluirea criptării RSA este cunoscută a fi o problemă majoră: astăzi există o discuție deschisă despre cât de fiabil este acest mecanism.

RSA este un algoritm relativ lent, motiv pentru care nu este utilizat pe scară largă pentru utilizatorul direct. Cea mai obișnuită utilizare a acestei metode este transmiterea în formă criptată a cheilor publice pentru o cheie de criptare simetrică, care la rândul său poate efectua operațiuni de criptare și decriptare în bloc la o viteză mult mai mare.

Când a apărut criptosistemul în forma sa modernă?

Ideea unui criptosistem cu cheie asimetrică este atribuită lui Diffie și Hellman, care au publicat conceptul în 1976, introducând semnături digitale și încercând să aplice teoria numerelor. Formularea lor folosește un secret comun creat din exponențiarea unui număr modulo un număr prim. Cu toate acestea, au lăsat deschisă problema implementării acestei caracteristici, deoarece principiile factoringului nu erau bine înțelese la momentul respectiv.

Rivest, Adi Shamir și Adleman de la MIT au făcut mai multe încercări de-a lungul unui an de a crea o funcție unidirecțională care este dificil de decodat. Rivest și Shamir (ca informaticieni) au propus multe caracteristici potențiale, în timp ce Adleman (ca matematician) a căutat „puncte slabe” în algoritm. Au luat multe abordări și în cele din urmă au dezvoltat sistemul final în aprilie 1977, astăzi cunoscut sub numele de RSA.

EDS și cheie publică

O semnătură digitală electronică, sau EDS, este parte integrantă a documentelor electronice. Se formează cu o anumită modificare criptografică a datelor. Folosind acest atribut, este posibil să se verifice integritatea documentului, confidențialitatea acestuia și, de asemenea, să se stabilească cine îl deține. De fapt, aceasta este o alternativă la semnătura standard obișnuită.

Acest criptosistem (criptare RSA) oferă o cheie publică, care este diferită de cele simetrice. Principiul funcționării sale este că sunt utilizate două chei diferite - una privată (criptată), precum și una publică. Primul este folosit pentru a genera un EDS și, ulterior, pentru a putea decripta textul. Al doilea este pentru criptarea efectivă și verificarea semnăturii digitale.

Utilizarea unei semnături permite o mai bună înțelegere a criptării RSA, un exemplu al căruia poate fi dat ca un document secret normal „ascuns de privirile indiscrete”.

Care este esența algoritmului?

Algoritmul RSA constă din patru pași: generarea cheilor, distribuirea cheilor, criptarea și decriptarea. După cum sa menționat deja, criptarea RSA include o cheie publică și o cheie privată. Open poate fi cunoscut de toată lumea și este folosit pentru a cripta mesajele. Esența sa constă în faptul că mesajele criptate folosind cheia publică pot fi decriptate doar într-o anumită perioadă de timp folosind cheia secretă.

Din motive de securitate, numerele întregi ar trebui să fie alese aleatoriu și să aibă aceeași mărime, dar să difere în lungime cu câteva cifre pentru a face factorizarea mai dificilă. Numerele identice pot fi găsite eficient folosind un test pentru simplitatea lor, așa că criptarea informațiilor trebuie neapărat să devină mai complicată.

Cheia publică este formată dintr-un modul și un exponent public. Private constă dintr-un modul și un indicator privat, care trebuie ținut secret.

Criptarea fișierelor RSA și punctele slabe

Cu toate acestea, există o serie de mecanisme pentru a sparge RSA simplu. Cu criptare de valoare mică și numere mici, cifrul poate fi spart cu ușurință prin alegerea rădăcinii textului cifrat peste numere întregi.

Deoarece criptarea RSA este un algoritm determinist (adică nu are o componentă aleatorie), un atacator poate lansa cu succes un atac de text simplu ales împotriva unui sistem criptografic prin criptarea textului simplu probabil cu cheia publică și verificând dacă acestea sunt egale cu textul cifrat. Un criptosistem se numește semantic sigur dacă un atacator nu poate distinge două criptări unul de celălalt, chiar dacă cunoaște textele corespunzătoare în forma deschisă. După cum s-a descris mai sus, RSA fără adăugarea altor servicii nu este sigură din punct de vedere semantic.

Algoritmi suplimentari de criptare și protecție

Pentru a evita problemele de mai sus, implementările practice ale RSA includ de obicei o formă de umplutură structurată, randomizată înainte de criptare. Acest lucru asigură că conținutul nu se încadrează în gama de texte clare nesigure și că mesajul nu poate fi descoperit prin selecție aleatorie.

Securitatea criptosistemului RSA și criptarea informațiilor se bazează pe două probleme matematice: problema factorizării numerelor mari și problema RSA în sine. Dezvăluirea completă a textului cifrat și a semnăturii digitale în RSA este considerată inacceptabilă, presupunând că ambele probleme nu pot fi rezolvate împreună.

Cu toate acestea, datorită capacității de a recupera factorii primi, un atacator poate calcula indicatorul secret din cheia publică și apoi poate decripta textul utilizând procedura standard. Deși nu s-a găsit nicio metodă existentă de factorizare a numerelor mari pe un computer clasic astăzi, nu s-a dovedit că nu există.

Automatizare

Un instrument numit Yafu poate fi folosit pentru a eficientiza acest proces. Automatizarea în YAFU este o caracteristică de ultimă generație care combină algoritmii de factorizare într-o metodologie inteligentă și adaptivă care minimizează timpul necesar pentru găsirea factorilor de numere de intrare arbitrare. Cele mai multe implementări ale algoritmului sunt multi-threaded, permițând lui Yafu să profite din plin de multi-sau mai multe (inclusiv SNFS, SIQS și ECM). În primul rând, este un instrument de linie de comandă gestionat. Timpul petrecut căutând un factor de criptare folosind Yafu pe un computer obișnuit poate fi redus la 103,1746 secunde. Instrumentul produce procesare cu o capacitate de 320 de biți sau mai mult. Este un software foarte complex care necesită o anumită cantitate de abilități tehnice pentru a instala și configura. Astfel, criptarea RSA C poate fi vulnerabilă.

Încercările de hacking în timpurile moderne

În 2009, Benjamin Moody, folosind o cheie RSA-512 biți, a lucrat la decriptarea criptotextului timp de 73 de zile folosind doar un software binecunoscut (GGNFS) și un computer desktop mediu (Athlon64 dual-core la 1900 MHz). După cum a arătat această experiență, a fost nevoie de puțin mai puțin de 5 gigaocteți de disc și aproximativ 2,5 gigaocteți de memorie RAM pentru procesul de „cernere”.

Începând cu 2010, cel mai mare număr RSA factorizat avea 768 de biți (232 de cifre zecimale sau RSA-768). Dezvăluirea sa a durat doi ani pe câteva sute de computere în același timp.

În practică, cheile RSA sunt mai lungi, de obicei între 1024 și 4096 de biți. Unii experți cred că cheile pe 1024 de biți pot deveni nesigure în viitorul apropiat sau pot fi chiar sparte de un atacator bine finanțat. Cu toate acestea, puțini ar susține că cheile pe 4096 de biți ar putea fi, de asemenea, expuse în viitorul apropiat.

perspective

Prin urmare, se presupune în general că RSA este sigură dacă numerele sunt suficient de mari. Dacă numărul de bază este de 300 de biți sau mai scurt, textul cifrat și semnătura digitală pot fi descompuse în câteva ore pe un computer personal utilizând un software care este deja disponibil gratuit. S-a demonstrat că cheile pe 512 biți pot fi sparte încă din 1999 folosind câteva sute de computere. În zilele noastre, acest lucru este posibil în câteva săptămâni folosind hardware-ul disponibil în mod obișnuit. Astfel, este foarte posibil ca criptarea RSA de pe degete să fie ușor expusă în viitor, iar sistemul să devină iremediabil depășit.

Oficial, în 2003, securitatea cheilor pe 1024 de biți a fost pusă la îndoială. În prezent, se recomandă să aibă o lungime de cel puțin 2048 de biți.

RSA folosește două tipuri de chei - e și d , unde e este public și d este secret. Să presupunem că P este textul simplu și C este textul cifrat. Alice folosește C = P e mod n pentru a crea textul cifrat C din textul simplu P; Bob folosește P = C d mod n pentru a extrage textul sursă (fișierul) furnizat de Alice. Un număr foarte mare de module n sunt create folosind procesul de generare a cheilor, despre care vom discuta mai târziu.

Exponentiarea modul este folosita pentru criptare si decriptare. După cum am discutat deja în cursurile 12-13, atunci când se utilizează algoritmul rapid, modul de exponențiere este fezabil în timp polinomial. Totuși, găsirea logaritmului modulo este la fel de dificilă ca factorizarea unui număr modulo. Nu există un algoritm de timp polinomial pentru acesta. Aceasta înseamnă că Alice poate cripta mesajul cu cheia publică (e) în timp polinomial. Bob îl poate descifra și în timp polinomial (pentru că știe d ). Dar Eve nu poate descifra acest mesaj, deoarece ar trebui să calculeze rădăcina e-a a lui C folosind aritmetica modulară. Figura 14.5 arată ideea din spatele RSA.

Orez. 14.5.

Cu alte cuvinte, folosește Alice funcţie unidirecţională(modulo de exponențiere) cu o lacună cunoscută numai de Bob. Eve nu cunoaște lacuna, așa că nu poate descifra mesajul. Dacă cineva găsește vreodată un algoritm polinomial pentru modulul e-lea al rădăcinii lui n, atunci exponențiația modulo n nu va mai fi o funcție unidirecțională.

Procedură

Figura 14.6 prezintă ideea generală a procedurii utilizate în RSA.

RSA utilizează modulo de exponențiere pentru criptare/decriptare. Pentru a ataca textul privat, Eve trebuie să calculeze

Orez. 14.6.

Două structuri algebrice

RSA folosește două structuri algebrice: inel și grup.

Inele de criptare/decriptare. Criptarea și decriptarea se fac folosind un inel comutativ cu două operații aritmetice: adunarea și înmulțirea. În RSA, acest inel este public deoarece modulo n este public. Oricine poate trimite un mesaj lui Bob folosind acest inel de criptare.

Grupuri de generare cheie. RSA folosește grupul multiplicativ pentru a genera chei. Grupul acceptă doar înmulțirea și împărțirea (inversiunea multiplicativă), care sunt necesare pentru a genera chei publice și private. Acest grup trebuie ascuns deoarece modulul său este secret. Vom vedea că dacă Eve găsește acest modul, poate ataca cu ușurință sistemul criptografic.

RSA folosește două structuri algebrice: inel deschis R =< Z n , +, x > și grupul secret G =< Z (n)* , x >.

Generarea cheilor

Bob folosește pașii indicați în algoritmul 14.2 pentru a-și genera cheile publice și private. După generarea cheilor, Bob declară tuplu (e, n) ca cheie publică de acces: Bob stochează d ca cheie privată. Bob poate refuza p, q și ; nu își pot schimba cheia privată fără a schimba modulul. Pentru siguranță, dimensiunea recomandată pentru fiecare p sau q simplu este de 512 biți (aproape 154 de cifre zecimale). Aceasta specifică dimensiunea unității, n este de 1024 de biți (309 de cifre).

14.2. Generarea cheii RSA

În RSA, un tuplu (e, n) este o cheie publică de acces; întreg d - cheie secretă.

Criptare

Oricine îi poate trimite un mesaj lui Bob folosind cheia sa de acces public. Criptarea în RSA se poate face folosind un algoritm de timp polinomial, așa cum se arată în algoritmul 14.3. Algoritmul de exponențiere rapidă a fost discutat în prelegerile 12-13. Dimensiunea textului sursă trebuie să fie mai mică decât n ; dacă dimensiunea textului original este mai mare, atunci acesta trebuie împărțit în blocuri.

Sub tăietură, sunt descrise exemple de alegere a parametrilor de criptare RSA „răi”.

„Trebuie subliniat faptul că trebuie avută grijă în alegerea modulului RSA (numerele n) pentru fiecare corespondent al rețelei. În acest sens, se pot spune următoarele. Cititorul poate verifica independent acest lucru, cunoscând una dintre cele trei cantități p, q sau φ(n), se poate găsi cu ușurință cheia secretă RSA...”.

Să adăugăm acest text. Dacă alegerea modulului de criptare RSA nu reușește, așa cum se face în exemplul tutorial de mai jos, este posibilă decriptarea textului fără prezența unei chei secrete, de ex. fără să cunoască vreuna din cele trei cantităţi numite.

Pentru a face acest lucru, este suficient să aveți textul cifrat dat de modulul de cifrare n, cheie publică e cifrează și efectuează doar trei pași ai unui atac „citire fără cheie”. După al patrulea pas de atac, se stabilește că textul sursă a fost primit la pasul anterior, acesta poate fi citit. Să arătăm cât de ușor este de făcut.

Mai întâi, să dăm exemplul în sine de la pp. 313-315 din manualul menționat.

Exemplu

Criptare scurt mesaj text original: RSA.
Destinatarul stabilește cifrul cu caracteristicile n=pq=527, Unde p=17, q=31Și φ(n)=(р –1)(q – 1)=480. Ca cheie publică e se alege un număr care este copprim cu φ(n), e=7. Pentru acest număr, folosind algoritmul Euclid extins, se găsesc numere întregi uȘi v, satisfacand relatia e∙u+φ(n)∙v=1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

În măsura în care –137≡343(mod480), apoi d=343.

Examinare: 7∙343=2401≡1(mod480).

Un mesaj text este prezentat ca o secvență de numere conținute în interval . Pentru aceasta scrisoare R, SȘi A codificate ca numere binare pe 5 biți. Numerele de serie ale acestor litere din alfabetul englez sunt folosite în reprezentarea lor binară:

R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.

Apoi RSA=(100101001100001) 2. Împărțirea textului în blocuri de lungime limitată oferă o reprezentare a două blocuri: RSA=(100101001), (100001)=(M1 =297, M2 =33).

Blocuri criptate secvenţial de text sursă M 1 \u003d 297, M 2 \u003d 33:
y 1 \u003d E k (M 1) \u003d M 1 e ≡297 7 (mod527) \u003d 474.

Aici am folosit:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 \u003d E k (M 2) \u003d M 2 e ≡33 7 (mod527) \u003d 407.

Textul cifrat, ca și cel original, se obține sub forma a două blocuri: y 1 =474; y 2 =407.

Decriptare pare a fi o succesiune de acțiuni D k (y i)=(y i) d =(y i) 343 (mod 527), i=1,2.

Calcule de exponentiare d este mai convenabil să se efectueze, reprezentând preliminar exponentul ca sumă de puteri ale unui număr 2 , și anume: 343=256+64+16+4+2+1 .

Folosind această reprezentare exponentă d=343, primim:

474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
și, în sfârșit 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Valoarea este calculată în mod similar 407 343 (mod527)=33.

Trecerea la reprezentarea literală a mesajului decriptat oferă: RSA.

După examinarea exemplului, manualul discută puterea sistemului RSA. Nevoia de prudență în alegerea modulului de criptare RSA (numerele n) pentru fiecare corespondent al rețelei. Se subliniază că este inacceptabil să se ignore cerințele pentru caracteristicile selectate ale sistemului de criptare. Printre aceste cerințe, din păcate, nu este indicată cea a cărei încălcare este ilustrată de exemplul dat.

Atacul asupra cifrului RSA

Luați în considerare un exemplu de atac asupra cifrului RSA. Să folosim datele exemplului dat la paginile 313-315 în manualul „Fundamentals of Criptography” de A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheremushkin, Moscova. „Helios ARV”, 2001.

Eșecul (inadmisibilitatea) parametrilor de sistem selectați în acest exemplu este ușor de arătat prin calcule care implementează atacul citirii fără cheie a textului sursă. Esența unui astfel de atac este următoarea. Este dată cheia publică a cifrului RSA ( e=7, n=527) și text cifrat. În exemplu, textul cifrat este reprezentat de două blocuri
y \u003d (y 1 \u003d 474, y 2 \u003d 407).

Fiecare bloc criptat este atacat individual, mai întâi atacăm y 1 =474, după ce îl decriptăm, atacăm un alt bloc y 2 =407.

Apoi se formează prin criptare repetată cu salvarea rezultatelor a doi pași succesivi ai algoritmului de atac și folosind cheia publică o secvență de valori numerice i, y 1 = y text cifrat disponibil.

În algoritmul de atac al textului cifrat, se determină următorul număr de pas j, pentru care y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1. Din ultima relatie vedem ca la ridicarea la o putere e valorile (y i e j–1 (mod n)) se dovedește shiforttext inițial y i = y 1.

Dar asta înseamnă că textul simplu a fost criptat la acest pas. Prin calcule directe (sunt foarte puține) folosind calculatorul de pe ecran, găsim acea valoare j, la care ciclul de criptare se încheie cu valoarea y 1 de la care a început ciclul.

Atacul asupra primului bloc y 1 =474 text cifrat.
Pasul 1: 474 7 (mod527)=382;
Pasul 2: 382 7 (mod527)=423;
Pasul 3: 423 7 (mod527)=297;
Pasul 4: Acest pas criptează textul sursă deja găsit, dar trebuie executat deoarece atacatorul nu cunoaște textul sursă. Semnul finalizării atacului este coincidența valorii inițiale a textului cifrat ( 474 ) și rezultatul celui de-al 4-lea pas de criptare. Acesta este exact genul de coincidență care are loc.

297 7 (mod527)=474 a primit primul (primul) bloc de text cifrat. Atacul asupra primului bloc a fost finalizat cu succes y 1 =474. Rezultatul anterior al pasului 3 este text simplu M 1 \u003d 297.

n=527 r=297 modulo n=527. Este scris așa y i \u003d y 1 \u003d 297. Formăm reziduuri de putere
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Atacul asupra celui de-al doilea bloc y 2 =407 text cifrat.
Pasul 1: 407 7 (mod527)=16;
Pasul 2: 16 7 (mod527)=101;
Pasul 3: 101 7 (mod527)=33;
Pasul 4: 33 7 (mod527)=407.

Din nou, la al treilea pas, se obține blocul de text sursă ( M 2 \u003d 33), dar atacatorul nu știe acest lucru și efectuează următorul (al patrulea pas), al cărui rezultat este ( 407 ) se potrivește cu textul cifrat inițial y 2 =407.

În esență, în inelul de reziduuri modulo n=527 implementat un ciclu scurt de procesare a deducerii r=33 modulo n=527. Este scris așa y i \u003d y 2 \u003d 33.
Formăm reziduuri de putere ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Rezultatul atacului (textul original M 1 \u003d 297, M 2 \u003d 33) se obține prin criptarea triplă a textului cifrat dat. Un succes mai mare pentru textul cifrat atacator este greu de imaginat.

Continuând discuția despre alegerea modulului și a altor parametri de criptare, putem adăuga că modulul de criptare ( n=527) unele texte sursă nu permit deloc criptarea. În acest caz, alegerea valorii cheii publice e nu joacă un rol important. Există valori de text simplu care nu pot fi criptate deloc cu cifrul ales cu modulo n=527.

Niciunul dintre e-urile date nu este capabil să cripteze textele simple reprezentate prin numere
187 , 341 , 154 Și 373 .

Exemplu (incapacitatea de a cripta valorile unor texte sursă)

Textele sursă să fie reprezentate de patru blocuri y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373). Expozant e cheia publică a cifrului poate fi orice număr relativ prim cu funcția Euler φ(n)=φ(527)=480. Cu toate acestea, pentru cazul în cauză, cheia publică e poate fi setat arbitrar. Într-adevăr, să e=2, 4, 7, 9, 17, 111 apoi:

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

Din exemplul luat în considerare rezultă o concluzie simplă. Într-adevăr, alegerea parametrilor procesului de criptare trebuie abordată cu mare atenție și ar trebui efectuată o analiză preliminară amănunțită a acestor parametri. Cum se face acest lucru este o problemă separată și nu este luată în considerare în cadrul acestei lucrări.