Algoritmul rsa al sistemului de criptare cu chei publice. Sistem criptografic RSA. Semnătură digitală și cheie publică

Mecanismul de distribuire a drepturilor în sistemele de operare, dezvoltat încă din anii 70 ai secolului trecut, s-a dovedit a fi atât de reușit încât este încă folosit în sistemele UNIX, adică de mai bine de patruzeci de ani.

Permisiuni 777 - ce este?

Principiul de bază al metodei de distribuire a accesului include existența atributelor obligatorii, cum ar fi numele utilizatorilor sistemului, precum și grupurile acestora. Este aproape evident că în Linux fiecare utilizator poate avea un singur nume, care trebuie să fie unic în cadrul acestui sistem. Folosind o poreclă, utilizatorul se conectează în sistem, adică este supus autorizației. În plus, sistemul de operare conține un număr finit de grupuri de utilizatori. Fiecare dintre ei poate face parte dintr-unul sau mai multe grupuri. Superutilizatorul - root - poate edita proprietăți, poate crea și șterge grupuri. Membrii diferitelor grupuri au drepturi diferite de a opera în sistem. De exemplu, un administrator are mai multe drepturi decât un invitat.

Inodul (pe care îl are fiecare fișier) conține datele de conectare ale proprietarului și numele grupului de utilizatori care are drepturi asupra fișierului.

Când un fișier este creat, proprietarul acestuia devine utilizatorul în numele căruia rulează procesul. Grupul fișierului nou creat este de asemenea determinat folosind identificatorul de grup al procesului curent. În timpul lucrărilor ulterioare, toate aceste valori pot fi modificate folosind comenzile consolei, care vor fi discutate în continuare.

Cum se schimbă permisiunile

Comanda chmod poate schimba modul de acces utilizator al unui fișier. Numai proprietarul sau superutilizatorul acestuia i se permite să modifice aceste drepturi în orice fel. În sistemele Unix, codul este de obicei specificat ca un număr în formă octală sau folosind semne mnemonice speciale (litere). Folosirea fiecărei metode are avantajele și dezavantajele sale. Deci, cu ajutorul indicației digitale a drepturilor de acces, administratorul de sistem va putea configura rapid tipul de acces dorit și, cu ajutorul codurilor mnemonice, va putea face acest lucru mai precis - de exemplu, adăugați sau eliminați dreptul de scriere sau refuzați dreptul de citire.

Primul argument al comenzii consolei chmod este o specificare a permisiunilor utilizatorului, iar aceasta este o notație mnemonică sau un număr octal. Al doilea și următorul argument sunt numele fișierelor la care încercăm să schimbăm drepturile de acces. Când setați drepturi sub formă de trei numere, prima cifră determină drepturile pentru proprietar, a doua pentru grup și a treia pentru toți ceilalți utilizatori.

Mnemonice privind drepturile de acces

Accesul la fișiere din sistemul de drepturi are următoarele variante:

r - acces pentru a citi fisierul;
w - dreptul de a edita datele (dar nu de ștergere);
x - capacitatea de a lansa un fișier pentru execuție.

Următorul sistem de drepturi se aplică directoarelor:

r - utilizatorul poate citi orice fișiere din director;
w - cu aceste drepturi puteți crea și șterge fișiere dintr-un folder, chiar dacă unele dintre ele din director aparțin altui utilizator;
x - indică dreptul de a intra în director. Dacă aveți drepturi w asupra unui subfolder, dar nu aveți drepturi asupra unui folder la un nivel superior, atunci nu veți putea accesa folderul dvs.

Sunt posibile un total de 8 combinații diferite, care sunt prezentate în figura de mai jos.

Folosind tabelul de mai jos, puteți înțelege cum să implementați atribuiri complexe de permisiuni, precum și cum să setați permisiunile 777 folosind specificația mnemonică chmod.

Cum să setați permisiunile la 777 prin SSH

Iată câteva exemple de utilizare a comenzii chmod:

chmod 711 nume_fișier.txt.

Folosind acest scenariu de distribuție a fișierelor, proprietarul va avea drepturi depline asupra fișierului, iar toate celelalte grupuri de utilizatori vor putea doar să-l execute.

Când folosiți codul 775, vom oferi proprietarului și întregului său grup o listă completă de drepturi. Alți utilizatori nu vor putea face modificări fișierului. Trebuie spus că pentru a specifica un fișier doar cu propriul nume, acesta trebuie să fie în directorul în care se află acest fișier. În caz contrar, puteți trece în acest director cu comanda cd nume_director/nume_subdirector sau puteți utiliza următoarea structură:

chmod 775 /var/bin/file_name.txt.

Pentru a modifica recursiv permisiunile tuturor fișierelor dintr-un director și ale tuturor subfolderelor, trebuie să adăugați comutatorul -R la comanda chmod. Comanda rezultată va arăta astfel:

chmod -R 711 nume_fișier.

Ca rezultat, modul de a seta drepturile de acces la 777 pentru un fișier sau director nu va fi o problemă - trebuie doar să vă conectați la serverul dvs. web prin SSH și să rulați comanda:

nume de fișier chmod 777.

Cum să setați drepturile de acces la 777 în panoul de control al serverului

De asemenea, puteți implementa o procedură similară prin interfața vizuală a clientului FileZilla FTP sau a clientului WinSCP SFTP. Pentru a face acest lucru, va trebui să autorizați pe serverul dvs. într-unul dintre aceste programe, să vă selectați fișierul sau folderul în interfața vizuală, apoi să faceți clic dreapta și să bifați casetele de lângă drepturile necesare.

Uneori, în caz de nevoie urgentă, este posibil să nu aveți acces la clientul Windows, așa că puteți modifica drepturile de acces prin panoul de control al serverului web. Pentru a face acest lucru, folosind managerul de fișiere al panoului de control, selectați fișierele necesare și faceți clic pe butonul Modificare permisiuni. Apoi, va trebui, de asemenea, să bifați toate casetele, iar acum întrebarea cum să setați drepturi de acces 777 la un folder nu va mai fi dificilă pentru dvs.

Algoritm de criptare cu cheie publică RSA a fost unul dintre primele propuse la sfârșitul anilor 70 ai secolului XX. Numele său este alcătuit din primele litere ale numelor de familie ale autorilor: R. Rivest, A. Shamir și L. Adleman. Algoritmul RSA este probabil cel mai popular și utilizat pe scară largă algoritm asimetricîn sistemele criptografice.

Algoritmul se bazează pe faptul că problema factorizării unui număr mare în factori primi este dificilă. Sistemul criptografic RSA se bazează pe următoarele două fapte din teoria numerelor:

sarcina de a verifica un număr pentru primalitate este relativ ușoară;
problema descompunerii numerelor de forma n = pq (p și q sunt numere prime); factorizarea este foarte dificilă dacă știm doar că n și p și q sunt numere mari (aceasta este așa-numita problemă de factorizare, pentru mai multe detalii vezi „Fundamentals of number theory used in public key cryptography”).

Algoritmul RSA este un algoritm de criptare bloc în care datele criptate și necriptate trebuie reprezentate ca numere întregi între 0 și n -1 pentru unele n.

Criptare

Deci, să ne uităm la algoritmul în sine. Permiteți abonatului A să dorească să trimită un mesaj criptat abonatului B. În acest caz, abonatul B trebuie să pregătească o pereche (cheie publică; cheie privată) și să trimită cheia sa publică utilizatorului A.

Primul pas este generarea cheilor publice și private. Pentru a face acest lucru, mai întâi selectați două numere prime mari P și Q. Apoi se calculează produsul N:

După aceasta, se determină numărul auxiliar f:

f = (P - l)(Q - 1).

Apoi numărul d este selectat aleatoriu< f и взаимно простое с f .

Numerele d și N vor fi cheia publică a utilizatorului, iar valoarea e va fi cheia privată.

Deci, în acest moment, utilizatorul ar trebui să aibă informațiile enumerate în următorul tabel:

Deoarece utilizatorul B dorește să primească un mesaj criptat de la utilizatorul A, atunci utilizatorul B trebuie să trimită cheia sa publică (d, N) utilizatorului A. Numerele P și Q nu mai sunt necesare, dar nu pot fi partajate cu nimeni; Cel mai bine este să le uiți cu totul.

În acest moment, etapa de pregătire a cheii este finalizată și protocolul RSA principal poate fi utilizat pentru a cripta datele.

A doua etapă – criptarea datelor. Dacă abonatul A dorește să trimită niște date abonatului B, el trebuie să-și reprezinte mesajul în formă digitală și să-l despartă în blocuri m 1, m 2, m 3, ..., unde m i< N . Mesajul criptat va consta din blocuri cu i .

Abonatul A criptează fiecare bloc al mesajului său folosind formula

c i = m i d mod N

folosind parametri publici utilizatorul B și trimite mesajul criptat C=(c 1, c 2, c 3, ...) pe o linie deschisă.

Abonatul B, care a primit un mesaj criptat, decriptează toate blocurile mesajului primit folosind formula

Toate blocurile decriptate vor fi exact aceleași cu cele care vin de la utilizatorul A.

Un atacator care interceptează toate mesajele și cunoaște toate informațiile publice nu va putea găsi mesajul original pentru valori mari de P și Q.

Exemplu de calcule de algoritm

Permiteți utilizatorului A să dorească să trimită un mesaj utilizatorului B. În acest caz, utilizatorul B trebuie mai întâi să pregătească cheile publice și private. Lăsați-i să selecteze, de exemplu, următorii parametri:

P = 3, Q = 11, N = 3x11 = 33.

Apoi f = (P - l)(Q - 1) = (3-1)(11-1) = 20.

Apoi utilizatorul B alege orice număr d care nu are divizori comuni cu f (acest lucru este necesar pentru ca mesajul criptat să poată fi apoi recuperat în mod unic). Fie d = 13. Acest număr va fi una dintre componentele cheii publice.

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

„Trebuie subliniat faptul că trebuie avută grijă în selectarea modulului RSA (număr n) pentru fiecare dintre corespondenții rețelei. În acest sens, se pot spune următoarele. Cititorul poate verifica independent că cunoscând una dintre cele trei cantități p, q sau φ(n), puteți găsi cu ușurință cheia privată RSA...".

Să adăugăm la acest text. Dacă alegerea modulului de criptare RSA nu are succes, așa cum s-a făcut în exemplul manualului de mai jos, puteți decripta textul fără prezența unei chei secrete, de ex. fără a cunoaște vreuna din cele trei cantități numite.

Pentru a face acest lucru, este suficient să aveți textul cifrat specificat de modulul de cifrare n, cheie publică e cifrează și efectuează doar trei pași dintr-un atac de citire fără cheie. După al patrulea pas de atac, se stabilește că textul sursă a fost obținut la pasul anterior și 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 mesaj text inițial scurt: 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 coprim cu φ(n), e=7. Numerele întregi sunt găsite pentru acest număr folosind algoritmul euclidian extins 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.

Deoarece –137≡343(mod480), Acea d=343.

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

Mesajul text este prezentat ca o secvență de numere conținute în interval . Scrisori pentru asta R, SȘi A sunt codificate ca numere binare pe cinci 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ă produce o prezentare în două blocuri: RSA=(100101001), (100001)=(M1 =297, M2 =33).

Blocurile de text sursă sunt criptate secvenţial M1 = 297, M2 =33:
y 1 =E k (M 1)=M 1 e ≡297 7 (mod527)=474.

Aici am profitat de faptul că:

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

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

Decodare 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 mai întâi exponentul ca sumă de puteri a numărului 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ă ce ați analizat exemplul, manualul discută robustețea sistemului RSA. Este subliniată nevoia de precauție în alegerea modulului de cifră RSA (numerele). n) pentru fiecare dintre corespondenții rețelei. Se indică faptul că este inadmisibilă ignorarea cerințelor pentru caracteristicile selectate ale sistemului de criptare. Printre aceste cerințe, din păcate, a căror încălcare este ilustrată de exemplul dat nu este indicată.

Atacul asupra cifrului RSA

Să ne uităm la un exemplu de atac asupra cifrului RSA. Să folosim datele din exemplul 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ă un atac la citirea fără cheie a textului sursă. Esența unui astfel de atac este următoarea. Este specificată cheia publică de cifră RSA ( e=7, n=527) și text cifrat. În exemplu, textul cifrat este reprezentat în două blocuri
y=(y 1 =474, y 2 =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.

În continuare, se formează o secvență de valori numerice prin criptare repetată, stocând rezultatele a doi pași succesivi ai algoritmului de atac și folosind o cheie publică. y eu, 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 relație vedem că atunci când este ridicat la o putere e valorile (y i e j–1 (mod n)) se obţine textul cifrat 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 un calculator 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: la acest pas textul sursă deja găsit este criptat, dar trebuie făcut deoarece atacatorul nu cunoaște textul sursă. Un semn de finalizare a atacului este coincidența valorii inițiale a textului cifrat ( 474 ) și rezultatul celui de-al patrulea pas de criptare. Aceasta este exact coincidența 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 egal cu textul simplu M1 = 297.

n=527 r=297 modulo n=527. Este scris așa y i =у 1 =297. Formarea reziduurilor 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, în al treilea pas, a fost obținut un bloc de text sursă ( M2 =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 a fost implementat un ciclu scurt de procesare a deducerii r=33 modulo n=527. Este scris așa y i =y 2 =33.
Formarea reziduurilor de putere ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Rezultatul atacului (text sursă M1 = 297, M2 =33) se obține prin criptarea textului cifrat dat de trei ori. Este greu de imaginat un succes mai mare pentru un atacator de text cifrat.

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 pot fi deloc criptate. În acest caz, alegerea valorii cheii publice nu joacă un rol important. Există valori de text sursă care sunt în general imposibil de criptat cu cifrul selectat cu modulul n=527.

Niciuna dintre cele date nu poate cripta textele sursă 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 coprim 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 pentru procesul de criptare trebuie abordată cu mare atenție și trebuie 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 scopul acestei lucrări.

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

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

Exemplu

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.

Deoarece –137≡343(mod480), Acea d=343.

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

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ă produce o prezentare în două blocuri: RSA=(100101001), (100001)=(M1 =297, M2 =33).

Blocurile de text sursă sunt criptate secvenţial M1 = 297, M2 =33:
y 1 =E k (M 1)=M 1 e ≡297 7 (mod527)=474.

Aici am profitat de faptul că:

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

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

Decodare 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 mai întâi exponentul ca sumă de puteri a numărului 2 , și anume: 343=256+64+16+4+2+1 .

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

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

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

Atacul asupra cifrului RSA

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.

n=527 r=297 modulo n=527. Este scris așa y i =у 1 =297. Formarea reziduurilor de putere
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Rezultatul atacului (text sursă M1 = 297, M2 =33) se obține prin criptarea textului cifrat dat de trei ori. Este greu de imaginat un succes mai mare pentru un atacator de text cifrat.

Niciuna dintre cele date nu poate cripta textele sursă reprezentate prin numere
187 , 341 , 154 Și 373 .

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

În cele din urmă, a sosit momentul să începem descrierea criptosistemului RSA. Pe lângă explicarea modului în care funcționează, trebuie să discutăm în detaliu despre siguranța acestuia; cu alte cuvinte, de ce este atât de dificil să spargi un mesaj criptat cu criptosistemul RSA?

§ 12.1. Despre început și sfârșit

Pentru a implementa un sistem de criptare RSA pentru un singur utilizator, trebuie să selectați două numere prime diferite p și q și să calculați produsul lor. Primele p și q sunt păstrate secrete în timp ce numărul devine parte a cheii publice. În § 12.5 discutăm în detaliu metoda de selectare a primelor cheie și modul în care această alegere se referă la fiabilitatea sistemului.

Un mesaj (care poate fi considerat un număr întreg) este criptat prin ridicarea lui la o anumită putere modulo.De aceea, mai întâi trebuie să găsim o modalitate de a reprezenta textul mesajului ca o listă de clase modulo.Acesta, de fapt, nu este încă încă procesul de criptare, ci doar pregătirea mesajului astfel încât să poată fi criptat.

Pentru simplitate, să presupunem că textul mesajului conține doar cuvinte scrise cu majuscule. Deci mesajul este în cele din urmă o secvență de litere și spații. Primul pas este să înlocuiți fiecare literă a mesajului cu un număr care este selectat din următorul tabel:

(vezi scanare)

Spațiul dintre cuvinte este înlocuit cu numărul 99. După ce am făcut această procedură, vom obține un număr, eventual foarte mare dacă mesajul a fost lung. Totuși, acesta nu este numărul final pentru care ne străduim, ci doar un set de clase modulo. Și acum trebuie să împărțim reprezentarea numerică a mesajului în bucăți, fiecare dintre acestea fiind un număr natural care nu depășește. Aceste piese sunt de obicei numite blocuri de mesaje.

De exemplu, reprezentarea numerică a motto-ului „CUNOAȘTE-TE” arată astfel:

Alegând cele simple, obținem produsul, prin urmare, reprezentarea numerică a mesajului scris mai sus trebuie împărțită în blocuri mai mici de 23393. Să prezentăm una dintre astfel de diviziuni.

Desigur, alegerea blocurilor nu este clară, dar nici nu este complet arbitrară. De exemplu, pentru a evita ambiguitățile în faza

decriptarea nu ar trebui să evidențieze blocurile care încep cu zero.

La decriptarea unui mesaj criptat cu sistemul de criptare RSA, se obține o secvență de blocuri. Ele sunt apoi conectate împreună pentru a produce o reprezentare numerică a mesajului. Și numai după înlocuirea numerelor cu litere în conformitate cu tabelul de mai sus, va fi posibil să citiți mesajul original.

Vă rugăm să rețineți că fiecare literă din tabel este codificată cu un număr din două cifre. Acest lucru se face pentru a preveni confuzia. Să presupunem că am numerotat literele în ordine, începând cu 1, adică. A corespunde cu 1, B cu 2 și așa mai departe. În acest caz, nu vom putea spune cu siguranță dacă blocul 12 reprezintă o pereche de litere sau doar o literă, a douăsprezecea literă a alfabetului. Desigur, pentru reprezentarea numerică a unui mesaj, puteți utiliza orice corespondență unu-la-unu între litere și numere, de exemplu, -encoding, în care traducerea mesajului în formă digitală este efectuată automat de un computer.

§ 12.2. Criptare și decriptare

Un mesaj pregătit pentru criptare folosind metoda de la § 12.1 constă dintr-o secvență de blocuri, fiecare dintre ele fiind un număr mai mic decât Acum să discutăm cum este criptat fiecare bloc. Pentru a face acest lucru, avem nevoie de un număr egal cu produsul primelor și un număr natural, modulo inversabil, adică. număr care îndeplinește condiția

Să ne amintim că din cunoscutele p și q numărul poate fi calculat ușor. Într-adevăr,

Perechea se numește cheia publică sau de codificare a criptosistemului RSA pe care îl descriem. Fie blocul mesajului, adică un număr întreg care satisface inegalitatea Vom folosi simbolul pentru a desemna blocul mesajului criptat corespunzător lui Se calculează după următoarea regulă:

Rețineți că fiecare bloc de mesaje este criptat separat. Prin urmare, un mesaj criptat constă de fapt din blocuri criptate separate. Mai mult, nu putem combina aceste blocuri într-un număr mare, deoarece acest lucru va face imposibilă decriptarea mesajului. Vom vedea în curând motivul pentru asta.

Să revenim la exemplul pe care am început să-l luăm în considerare în primul paragraf. Am fixat astfel încât Acum trebuie să alegem un număr. Reamintim că acesta trebuie să fie coprim cu Cel mai mic număr prim care nu împarte 23088 este egal cu 5. Să setăm Pentru a codifica primul bloc al mesajului din § 12.1, avem pentru a determina scăderea numărului 25245 modulo 23393. Cu Utilizarea unui program de calcul simbolic (sau a unui calculator, dacă aveți răbdare) obținem că deducerea necesară este 22 752. Deci, mesajul criptat este reprezentat de următoarea secvență de blocuri :

Să vedem cum sunt decodificate blocurile unui mesaj criptat. Pentru a începe decriptarea, trebuie să cunoaștem elementul invers față de modulo. Ultimul dintre ele este un număr natural, pe care îl vom nota prin Perechea se numește secretă sau cheia de decodificare a sistemului de criptare RSA. Dacă a este un bloc al unui mesaj criptat, atunci decriptarea sa corespunzătoare

Rezultatul operației este:

Înainte de a reveni la exemplu, sunt necesare câteva comentarii. În primul rând, este foarte ușor de calculat dacă știți. Într-adevăr, cheia secretă este determinată folosind algoritmul euclidian extins. În al doilea rând, dacă blocul este mesajul original, atunci avem dreptul să ne așteptăm la egalitate.Cu alte cuvinte, atunci când decodăm un bloc dintr-un mesaj criptat, sperăm să aflăm blocul corespunzător celui original. Faptul că așa va fi cazul nu rezultă direct din algoritmul descris mai sus, dar vom discuta totul în detaliu în paragraful următor.

În cele din urmă, așa cum am argumentat în introducere și de-a lungul cărții, pentru a sparge un criptosistem RSA trebuie să-l factorizezi pentru că trebuie să știi să decriptezi mesajul.Totuși, odată ce funcționarea sistemului este descrisă în detaliu, este clar că această din urmă afirmație nu este în întregime exactă. Pentru a citi criptarea, pe lângă elementul în sine, trebuie doar să cunoașteți inversul elementului modulo.De aceea, pentru a pirata sistemul, este suficient să calculați cu cunoscut. Se dovedește că acest calcul este echivalent cu factorizarea unui număr. , după cum vom vedea în § 12.4.

În exemplul în discuție, aplicăm algoritmul euclidian extins numerelor și 5 pentru a determina.

(vezi scanare)

Astfel, Prin urmare, inversul lui 5 modulo ar fi -9235 și

Cel mai mic număr natural comparabil cu -9235 modulo Deci, pentru a decoda un bloc dintr-un mesaj criptat, trebuie să-l ridicăm la puterea de 13853 modulo 23393. În exemplul nostru, primul bloc codificat este 22752. Calcularea scăderii numărului 22 75213853 modulo 23,393, obținem Rețineți că, chiar și cu numere atât de mici, cerințele pentru operarea criptosistemului RSA depășesc capacitățile majorității calculatoarelor de buzunar.

§ 12.3. De ce funcționează?

După cum am observat mai devreme, pașii descriși mai sus conduc la un criptosistem funcțional numai dacă, în urma decodării fiecărui bloc al mesajului criptat, blocul corespunzător celui inițial este restaurat. Să presupunem că avem de-a face cu un sistem RSA care are o cheie publică și o cheie privată Folosind notația din § 12.2, trebuie să arătăm că pentru orice număr întreg care satisface inegalitatea, identitatea este valabilă.

De fapt, este suficient să demonstrăm asta

Într-adevăr, atât numerele întregi 6, cât și cele nenegative sunt mai mici, prin urmare, sunt comparabile în valoare absolută dacă și numai dacă sunt egale. Acest lucru, în special, explică de ce împărțim reprezentarea numerică a mesajului în blocuri mai mici. În plus, se poate observa din aceasta că blochează

Mesajul codificat trebuie notat separat: altfel raționamentul nostru nu va funcționa.

Din rețetele de criptare și decriptare rezultă că

Întrucât elementele sunt reciproc inverse în modul, există un k natural astfel încât În plus, prin condiție, numerele sunt mai mari.De aceea, înlocuind în loc de produsul din ecuația (3.1), obținem

Acum să folosim teorema lui Euler, care afirmă că Prin urmare, i.e.

și am fi obținut complet dovada dacă o mică eroare nu s-ar fi strecurat în ea.

Dacă revizuiți din nou cu atenție raționamentul nostru, veți observa că nu am ținut cont de condițiile teoremei lui Euler. De fapt, înainte de a aplica teorema, este necesar să ne asigurăm că numerele sunt prime reciproc.Acest lucru, se pare, trebuie monitorizat atunci când se pregătește un mesaj pentru criptare, adică. Când împărțiți reprezentarea numerică a unui mesaj în blocuri, trebuie să vă asigurați că toate blocurile rezultate sunt coprime pentru. Din fericire, acest lucru nu este necesar, deoarece de fapt comparația se face pentru orice bloc. Iar eroarea nu constă în rezultatul pe care vrem să-l dovedim, ci doar în proba în sine. Abordarea corectă se bazează pe raționamentul folosit în demonstrarea teoremei lui Corcelt din capitolul 7.

Amintiți-vă că unde sunt numere prime diferite. Să definim resturile unui număr modulo Deoarece

calculele pentru ambele numere prime sunt similare, vom rezolva cazul doar în detaliu.Deci, am văzut deja că

pentru un număr întreg Prin urmare,

Am dori acum să aplicăm teorema lui Fermat, dar avem dreptul să facem acest lucru numai dacă nu împarte Fie ca această cerință să fie satisfăcută. Atunci obținem asta

Înlocuind teorema lui Fermat cu teorema lui Euler, nu am rezolvat problema apărută: comparația este valabilă doar pentru unele, dar nu pentru toate blocurile. Cu toate acestea, acum blocurile pentru care raționamentul nu funcționează trebuie împărțite la Mai departe, dacă împarte, atunci ambele 6 și sunt comparabile cu 0 în modul și, prin urmare, comparabile între ele. Astfel, comparația care se dovedește este valabilă și în acest caz. Prin urmare, comparația este adevărată pentru orice număr întreg. Rețineți că nu. ar fi putut folosi un raționament similar atunci când a aplicat teorema lui Euler într-adevăr, inegalitatea nu înseamnă comparație deoarece numărul este compus.

Deci, am dovedit că Comparația se dovedește în mod similar.Cu alte cuvinte, împărțirea ambelor cu și Dar sunt numere prime diferite, astfel încât. Astfel, lema din § 3.6 ne garantează că împărțim A deoarece avem pentru orice număr întreg Cu alte cuvinte, As am remarcat la începutul paragrafului, acest lucru este suficient pentru a demonstra egalitatea, deoarece ambele părți sunt numere întregi nenegative mai mici decât Pentru a rezuma, putem spune că

algoritmul din paragraful anterior conduce la un criptosistem practic. Acum trebuie să vă asigurați că este fiabil.

§ 12.4. De ce este sistemul fiabil?

Amintiți-vă că RSA este un sistem de criptare cu o cheie publică constând din produsul diferitelor numere prime și un număr natural inversabil modulo. Să ne uităm cu atenție la ce se poate face pentru a sparge RSA dacă tot ceea ce se știe este o pereche

Pentru a decoda un bloc criptat cu RSA, trebuie să cunoaștem inversul modulo k. Problema este că practic singura modalitate cunoscută de a face acest lucru se bazează pe aplicarea algoritmului euclidian extins la. Cu toate acestea, pentru a calcula folosind formula de la § 9.4, trebuie să știm ce confirmă afirmația originală: Ruperea RSA necesită factorizare. Și întrucât dificultățile de descompunere sunt fundamentale, sistemul RSA este sigur.

Se poate presupune, desigur, că într-o zi cineva va descoperi un algoritm care calculează fără informații despre factorii unui număr.Ce se va întâmpla, de exemplu, dacă cineva vine cu o modalitate eficientă de a determina direct prin De fapt, aceasta este doar o metodă mascată de expansiune Mai precis, dacă

sunt cunoscute, atunci putem calcula cu ușurință Într-adevăr,

deci se cunoaște suma divizorilor primi necesari. Mai departe,

de aceea se cunoaşte şi diferenţa. Acum, prin rezolvarea unui sistem simplu de ecuații liniare, putem găsi cu ușurință factorizarea.

Aceasta înseamnă că algoritmul care calculează de fapt descompune numărul în factori, deci este o pasăre de pene. Dar este prea devreme pentru a te calma. Poți să mergi mai departe în fanteziile tale și să presupui că cineva a inventat un algoritm care determină direct prin Dar Deci, dacă știm, atunci știm numărul care este un multiplu al acestuia.Se pare că astfel de informații sunt suficiente și pentru descompunere. Un algoritm probabilistic care duce la o astfel de descompunere poate fi găsit V . Exercițiul 7 arată un algoritm de descompunere similar (dar mai simplu), în ipoteza că criptosistemul Rabin poate fi spart. Vă va oferi o idee despre algoritmul probabilistic din .

Rămâne ultima posibilitate de hacking: o încercare de a restabili blocul direct prin restul modulo.Dacă este suficient de mare, atunci o căutare sistematică a tuturor candidaților posibili pentru căutare este singura cale de ieșire. Nimeni nu a venit încă cu ceva mai bun. Am enumerat principalele argumente care explică de ce ruperea criptosistemului RSA este considerată echivalentă cu factorizarea, deși nu există încă o dovadă riguroasă a acestei afirmații.

§ 12.5. Alegerea celor simple

Din discuția anterioară rezultă că pentru securitatea criptosistemului RSA este important să alegeți numerele prime potrivite.Bineînțeles, dacă sunt mici, sistemul este ușor de piratat. Cu toate acestea, nu este suficient să alegeți unele mari, într-adevăr, chiar dacă p și q sunt uriașe, dar diferența este mică, produsul lor poate fi factorizat cu ușurință folosind algoritmul lui Fermat (vezi § 3.4).

Aceasta nu este o vorbă inutilă. În 1995, doi studenți de la o universitate americană au spart o versiune publică a RSA. Acest lucru a devenit posibil datorită alegerii proaste a factorilor primi ai sistemului.

Pe de altă parte, RSA a fost folosit de mult timp și, dacă factorii primi sunt aleși cu atenție, sistemul se dovedește de fapt a fi destul de fiabil. Astfel, orice programator de criptare RSA are nevoie de o metodă eficientă pentru alegerea cu succes a numerelor prime.

Să presupunem că vrem să creăm un criptosistem RSA cu o cheie publică în care întregul are aproximativ cifre. Mai întâi, să alegem un număr prim al cărui număr de caractere se află între, să-l luăm aproape. În prezent, dimensiunea cheii recomandată pentru uz personal este de 768 de biți, adică. ar trebui să aibă aproximativ 231 de cifre. Pentru a construi un astfel de număr, avem nevoie de două simple, de exemplu, de 104 și 127 de cifre. Vă rugăm să rețineți că numerele prime alese în acest fel sunt destul de departe unele de altele, adică. Utilizarea algoritmului lui Fermat pentru descompunere în această situație este nepractică. În plus, trebuie să ne asigurăm că nu numai factorii mici, ci și cei mari sunt implicați în factorizarea numerelor în factori primi. Într-adevăr, în caz contrar, numărul devine pradă ușoară pentru unii algoritmi de descompunere bine-cunoscuți (vezi). Să considerăm acum o metodă prin care se găsesc numere prime care îndeplinesc condițiile enumerate.

Mai întâi avem nevoie de un rezultat simplu despre distribuția numerelor prime. Să ne amintim ceea ce denotă numărul de prime care nu depășește x. Având în vedere teorema numerelor prime, vedem că pentru x mare numărul este aproximativ egal cu unde este logaritmul natural

pe bază (vezi § 4.5). Să fie un număr foarte mare, ceva pozitiv. Dorim să estimăm numărul de numere prime aflate între ele și să estimăm diferența.Datorită teoremei numerelor prime și proprietăților logaritmului, diferența este aproximativ egală cu

Presupunând că este foarte mic, putem presupune că valoarea este egală cu 0 și obținem o estimare rezonabilă a diferenței. Deci, numărul de numere prime cuprinse între este aproximativ egal. Desigur, estimarea este mai precisă, cu cât x este mai mare și cu atât mai mic.Pentru o introducere mai detaliată a unei asemenea estimări, vezi ([D. 10]).

Să presupunem că trebuie să alegem un număr prim în vecinătatea unui întreg x. Pentru certitudine, vom presupune că x este de ordinul , și căutăm un prim în intervalul de la x la. Ar fi util să știm dinainte câte numere prime sunt în acest interval. Pentru a estima numărul de numere prime, puteți folosi rezultatul tocmai obținut. În exemplul nostru, valoarea este de un ordin de mărime foarte mic: Prin urmare, folosind formula scrisă mai sus, ajungem la concluzia că intervalul dintre se află aproximativ

numere prime. La sfârşitul celui de-al doilea paragraf al capitolului 11, am formulat o strategie menită să demonstreze caracterul prim al unui număr impar dat, care constă din trei etape.