Criptanaliza RSA

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 iunie 2016; verificările necesită 8 modificări .

Acest articol descrie condițiile de utilizare a criptoalgoritmului cu cheie publică RSA , care simplifică atacurile criptoanalitice [1] și metodele de eliminare a acestor condiții.

Introducere

Începând cu 2009, un sistem de criptare bazat pe RSA este considerat sigur începând de la 1024 de biți. $n$

Un grup de oameni de știință din Elveția, Japonia, Franța, Țările de Jos, Germania și Statele Unite au calculat cu succes date criptate folosind o cheie criptografică RSA de 768 de biți. [2] Potrivit cercetătorilor, după munca lor, doar cheile RSA cu o lungime de 1024 de biți sau mai mult pot fi considerate un sistem de criptare fiabil. Mai mult, criptarea cu o cheie de 1024 de biți ar trebui abandonată în următorii trei-patru ani. [3]

După cum rezultă din descrierea lucrării, calculul valorilor cheie a fost efectuat prin metoda sită a câmpului cu numere generale .

Primul pas (alegerea unei perechi de polinoame de gradul 6 și 1) a durat aproximativ o jumătate de an de calcule pe 80 de procesoare, ceea ce a reprezentat aproximativ 3% din timpul petrecut pe etapa principală a algoritmului (cernerea), care a fost efectuată pe sute de calculatoare timp de aproape doi ani. Dacă interpolăm de această dată pentru funcționarea unui procesor AMD Opteron 2.2 GHz cu 2 GB memorie, atunci ar fi aproximativ 1500 de ani. Procesarea datelor după cernerea pentru următorul pas care consumă mult resurse (algebră liniară) a durat câteva săptămâni pe un număr mic de procesoare. Pasul final după găsirea unor soluții OSLU non-triviale a durat nu mai mult de 12 ore.

Soluția OSLU a fost realizată folosind metoda Wiedemann pe mai multe clustere separate și a durat puțin mai puțin de 4 luni. În același timp, dimensiunea matricei rare a fost 192.796.550x192.795.550 cu 27.795.115.920 de elemente non-nule (adică o medie de 144 de elemente non-nule pe rând). A fost nevoie de aproximativ 105 gigaocteți pentru a stoca matricea pe hard disk. În același timp, a fost nevoie de aproximativ 5 terabytes de date comprimate pentru a construi această matrice.

Ca rezultat, grupul a putut calcula o cheie de 232 de cifre care deschide accesul la datele criptate.

Cercetătorii sunt încrezători că folosind metoda lor de factorizare, spargerea unei chei RSA pe 1024 de biți va fi posibilă în următorul deceniu.[ când? ] .

Cunoscând extinderea modulului în produsul a două numere prime, adversarul poate găsi cu ușurință exponentul secret și astfel să rupă RSA. Cu toate acestea, până în prezent, cel mai rapid algoritm de factorizare este General Number Field Sieve, a cărui viteză pentru un întreg de k-biți este $n$ $d$

$\exp((c+o(1))k^{\frac {1}{3}}\log ^{\frac {2}{3}}k),$ pentru unii , $c<2$

nu permite descompunerea unui întreg mare într-un timp rezonabil. Vom lua în considerare posibile atacuri asupra RSA care ne permit să spargem acest sistem fără a folosi o expansiune directă a modulului n în produsul a două numere prime.

Atacurile elementare

Să luăm în considerare mai multe atacuri legate de utilizarea greșită a algoritmului RSA.

Generarea numerelor prime

Următoarea restricție suplimentară este impusă numerelor prime aleatorii : $p$ $q$

$p$ și nu ar trebui să fie prea aproape unul de celălalt, altfel va fi posibil să le găsiți folosind metoda de factorizare a lui Fermat . Cu toate acestea, dacă ambele numere prime au fost generate independent, atunci această constrângere este satisfăcută automat cu o probabilitate uriașă. $q$ $p$ $q$

Schema cu modul comun n

Date inițiale: Pentru a evita generarea de module diferite pentru fiecare utilizator, serverul securizat folosește un singur n pentru a cripta toate mesajele. Party folosește acest server pentru a primi mesajul $n=p*q$ $A$ $M$

Sarcină: adversarul dorește să decripteze mesajul părții . $A$

S-ar părea că un text cifrat trimis unei părți nu poate fi decriptat de către parte decât dacă posedă cheia secretă . Cu toate acestea, partea poate folosi exponenții săi pentru a descompune modulul și după aceea, știind , să calculeze exponentul secret . $C=M^{e_{a}}\mod n$ $A$ $B$ $d_{a}$ $B$ $e_{b},d_{b)$ $n$ $e_{a}$ $d_{a}$

Protecție: fiecare utilizator trebuie să folosească propriul modul . $n$

Atacul asupra semnăturii RSA în schema notarială

Date inițiale: - cheia publică a notarului. Adversarul primește un refuz atunci când încearcă să semneze un mesaj de la un notar $(n, e)$ $M\in \mathbb {Z} _{n}$

Sarcină: adversarul dorește să obțină semnătura notarului pe mesaj . $M\in \mathbb {Z} _{n}$

Adversarul alege un arbitrar , calculează și trimite acest mesaj notarului pentru semnare. $r\in \mathbb {Z} _{n}$ $M'=r^{e}M\mod n$

Dacă notarul semnează acest mesaj:

S'=(M')^{d}\mod n

apoi adversarul, după ce a calculat , obține semnătura mesajului . $S=S'/r\mod n$ $M$

Într-adevăr, $S^{e}=(S')^{e}/r^{e}=(M')^{ed}/r^{e}\equiv M'/r^{e}=M (\modn)$

Protecție: atunci când semnați, adăugați un număr aleatoriu (de exemplu, ora) la mesaj.

Valori mici ale exponentului secret

Date inițiale: Pentru a crește viteza de decriptare (sau crearea unei semnături digitale), numărul de biți non-zero ai reprezentării binare a exponentului secret a fost redus (vezi viteza algoritmului RSA ). $d$

Sarcină: Calculați exponentul secret . $d$

În 1990, Michael J. Wiener a arătat că, în cazul unei valori mici , este posibil să rupă sistemul RSA, și anume: $d$

Teorema lui Wiener:

Fie , unde Apoi, dacă se știe unde ,

n=pq

q<p<2q

d<{\frac {1}{3}}n^{{{\frac {1}{4}}}}

(n, e)

ed=1\mod \varphi (n)

atunci există o modalitate eficientă de a calcula .

d

Protecție: Astfel, dacă are o dimensiune de 1024 de biți, trebuie să aibă o lungime de cel puțin 256 de biți. $n$ $d$

Valori mici ale exponentului deschis

Pentru a crește viteza de criptare și verificare a semnăturilor digitale , utilizați valori mici ale exponentului deschis . Cel mai mic dintre ei . Cu toate acestea, pentru a crește puterea criptografică a algoritmului RSA, se recomandă utilizarea $e$ $e=3$

$e=2^{16}+1=65537$ .

Atacul lui Khastad

Condiții inițiale: Partea trimite un mesaj criptat utilizatorilor . Fiecare utilizator are propria sa cheie publică și . Partea criptează mesajul utilizând pe rând cheia publică a fiecărui utilizator și îl trimite destinatarului corespunzător. Adversarul ascultă canalul de transmisie și colectează textele cifrate transmise. $B$ $M$ $P_{1},P_{2},...P_{k)$ $(n_{i},e_{i})$ $M<n_{i},\forall i$ $B$ $k$

Sarcină: adversarul vrea să recupereze mesajul . $M$

Lasa , atunci adversarul se poate recupera daca . $e_{i}=3,\forall i$ $M$ $k \geqslant 3$

Dovada

Într-adevăr, dacă adversarul a primit , unde ${\displaystyle C_{1},C_{2},C_{3))$

C_{1}=M^{3}\mod n_{1}

C_{2}=M^{3}\mod n_{2}

C_{3}=M^{3}\mod n_{3)

Presupunem că sunt coprime, altfel cel mai mare divizor comun altul decât unul ar însemna găsirea unui divizor al unuia dintre . Aplicând teorema chineză a restului la , obținem , ${\displaystyle n_{1},n_{2},n_{3))$ $n$ ${\displaystyle C_{1},C_{2},C_{3))$ $C'\in \mathbb {Z} _{n_{1}n_{2}n_{3))$

C'=M^{3}\mod n_{1}n_{2}n_{3)

De atunci , de atunci $M<n_{i},\forall i$ $M^{3}<n_{1}n_{2}n_{3},\forall i$

C'=M^{3}

Adică, adversarul poate recupera mesajul calculând rădăcina cubă a . $M$ $C'$

În general, dacă toți exponenții deschiși sunt egali , adversarul se poate recupera la . $e$ $M$ $k\geqslant e$

Luați în considerare cea mai simplă apărare împotriva acestui atac. Lăsați mesajul pentru fiecare utilizator să fie o permutare fixă a mesajului original . De exemplu $M_{i}$ $M$

M_{i}=i2^{m}+M

— mesaj pentru al-lea utilizator.

Hastad (Johan Hastad) a arătat că și în acest caz, adversarul poate recupera mesajul cu un număr suficient de utilizatori. $M$

Protecție: Acest atac este posibil doar cu o valoare mică a exponentului deschis , caz în care puterea criptografică a sistemului RSA poate fi atinsă folosind o permutare arbitrară, și nu una fixă, al cărei exemplu a fost dat mai sus. $e$

Atacul Franklin-Reiter

Conditii initiale :

Există două mesaje și $M_{1},M_{2}\in \mathbb {Z} _{n)$

M_{1}=f(M_{2})\mod n,

unde este un polinom deschis.

f\in \mathbb {Z} _{n}[x]

Partea cu cheia publică primește aceste mesaje de la parte , care pur și simplu criptează mesajele și transmite textele cifrate primite . $A$ $(n, e)$ $B$ $M_{1},M_{2}$ ${\displaystyle C_{1},C_{2))$

Sarcină: inamicul, știind , vrea să restaureze . $(n,e,C_{1},C_{2},f)$ $M_{1},M_{2}$

Matthew K. Franklin și Michael K. Reiter au dovedit următoarea afirmație:

Lăsa 1) este cheia publică a sistemului RSA și 2) și ,

(n, e)

e=3

M_{1}\neq M_{2}\in \mathbb {Z} _{n)

M_{1}=f(M_{2})\mod N

pentru un polinom liniar , Apoi, știind , adversarul se poate recupera

f=ax+b\in \mathbb {Z} _{n}[x]

b\neq 0

(n,e,C_{1},C_{2},f)

M_{1},M_{2}

Dovada

Într-adevăr, pentru un arbitrar : $e$

$C_{1}={M^{e}}_{1}\mod n~~~~\rightarrow ~~~~M_{2}$ , este rădăcina polinomului

g_{1}(x)=f(x)^{e}-C_{1}\in \mathbb {Z} _{n}[x]

dar, este și o rădăcină a polinomului $M_{2}$

g_{2}(x)=x^{e}-C_{2}\in \mathbb {Z} _{n}[x]

Astfel se împarte ambele polinoame. Iar adversarul poate folosi algoritmul Euclid pentru a calcula GCD . Dacă rezultatul se dovedește a fi un polinom liniar, atunci acesta va fi găsit. $(x-M_{2})$ $(g_{1},g_{2})$ $M_{2}$

Când , gcd este un polinom liniar și, prin urmare, adversarul poate calcula eficient mesajele . $e=3$ $(g_{1},g_{2})$ $M_{1},M_{2}$

Protecție: atunci când timpul de spargere a sistemului RSA este proporțional cu , astfel încât acest atac poate fi folosit doar cu valori mici ale exponentului deschis. $e>3$ $e^{2}$

Atacul asupra unui exponent secret parțial cunoscut

Conditii initiale :

Adversarul cunoaște o parte din reprezentarea binară a exponentului secret . $d$

Sarcină: restaurare . $d$

Se pare că:

Să fie cheia secretă a sistemului RSA, unde este dimensiunea biților.

(n,d)

n=pq

\eta

Apoi, cunoscând cei mai puțin semnificativi biți ai numărului , adversarul își poate reveni într-un timp proporțional cu

\eta /4

d

d

e\log _{2}e

Posibilitatea de spargere a sistemului RSA în cazul în care exponentul deschis este mic este, de asemenea, evidentă din următorul raționament: $e$

din definiție și :

e

d

ed-k\varphi (n)=ed-k(np-q+1)=1

Din moment ce , este evident .

d<\varphi (n)

0<k\leqslant e

Având în vedere o valoare dată , adversarul poate calcula cu ușurință

k

{\hat {d}}={\mathcal {b}}(kn+1)/e{\mathcal {c}}

Apoi la

q<p<2q

|{\hat {d}}-d|\leqslant k(p+q)/e\leqslant 3k{\sqrt {n}}/e<3{\sqrt {n}}

Astfel, este o bună aproximare pentru .

{\pălărie {d)}

d

Deoarece sunt posibile numai valori distincte , adversarul poate construi o serie care să conțină termeni pentru care reprezentarea binară a unuia dintre elementele sale este aceeași cu jumătatea superioară a reprezentării binare a exponentului secret .

e

k

e

d

Protecție: creșterea exponentului deschis . $e$

Atacul cu un computer cuantic

Cu ajutorul unui computer cuantic , dacă acesta este construit, va fi posibilă spargerea RSA, deoarece algoritmul cuantic al lui Shor permite factorizarea numerelor mari într-un timp destul de scurt. Prin descompunerea modulului n în factori primi (acest lucru se poate face în timp folosind O (log n ) Q-biți logici ), exponentul secret d poate fi calculat. ${\textstyle {O(\log ^{2}n\log ^{3}(\log n)))}$

Atacurile legate de implementarea sistemului RSA

Atacul de rulare

Condiții inițiale:

Luați în considerare un card inteligent al cărui microprocesor semnează mesaje folosind o cheie privată RSA încorporată.

Obiectiv: inamicul vrea să obțină un exponent secret . $d$

Paul Kocher a propus un atac bazat pe măsurători de înaltă precizie ale timpului necesar codificatorului smart cardului pentru a efectua anumite operațiuni. Să luăm în considerare acest atac asupra exemplului sistemului RSA folosind algoritmul de exponențiere rapidă :

Adversarul obține semnături smart card pentru un număr mare de mesaje aleatoare și măsoară timpul necesar pentru a le genera semnăturile . $M_{1},M_{2},\dots,M_{k}\in \mathbb {Z} _{n)$ $T_{i}$

În timpul atacului, valoarea exponentului secret este restabilită bit cu bit, pornind de la bitul cel mai puțin semnificativ: $d$

$d$ ciudat, prin urmare . $d_{0}=1$
dacă atunci microprocesorul cardului inteligent trebuie să efectueze trei înmulțiri modulo , spre deosebire de cele două necesare când (vezi algoritmul de exponențiere rapidă ). Să notăm timpul de calcul al procesorului pentru mesaj . $d_{1}=1$ $n$ $d_{1}=0$ $t_{i}$ $M_{i}$

Kocher a arătat că atunci când două ansambluri și corelează . Cu toate acestea, în cazul în care sunt independenți. Astfel, recurgând la analiza corelației , adversarul poate determina .

d_{1}=1

{\mathcal {f}}t_{i}{\mathcal {g}}

{\mathcal {f}}T_{i}{\mathcal {g}}

d_{1}=0

d_{1}

poate fi definit în mod similar . $d_{2},d_{3},\dots$

Rețineți că, în cazul unui exponent deschis mic , poate fi aplicat un atac asupra unui exponent secret parțial deschis . În acest caz, este suficient să recuperați jumătate din biții exponentului secret . $e$ $d$

Securitate: Trebuie adăugată o întârziere adecvată, astfel încât fiecare pas al algoritmului de exponențiere rapidă să dureze o perioadă fixă de timp.

Atacul de eșec al implementării hardware RSA

Condiții inițiale:

Luați în considerare un card inteligent al cărui microprocesor semnează mesaje folosind o cheie privată RSA încorporată. Microprocesorul cardului folosește teorema chineză a restului pentru a accelera procesul de semnare. Adversarul încearcă să provoace o defecțiune în calculele microprocesorului.

Sarcină: adversarul vrea să calculeze modulo . $n$

Utilizarea teoremei chineze a restului crește viteza de creare a unei semnături digitale.

Într-adevăr, prin calcul

\sigma _{p}=M^{d_{p}}\mod p

, Unde

d_{p}=d\mod (p-1)~~~~(a)

\sigma _{q}=M^{d_{q}}\mod q

, Unde

d_{q}=d\mod (q-1)~~~~(b)

poți obține o semnătură

\sigma =T_{1}\sigma _{p}+T_{2}\sigma _{q}({\bmod {n))}

, Unde

T_{1}={\mathcal {f}}1\mod p,0\mod q{\mathcal {g}}

T_{2}={\mathcal {f}}0\mod p,1\mod q{\mathcal {g}}

Evident, calculele sunt mult mai rapide decât modul de exponențiere .

(a), (b)

n

Lasă acțiunile inamicului să provoace un eșec, ducând la un defect într-un bit al semnăturii. Apoi cel puțin unul dintre sau este calculat incorect. Să presupunem că defectul este cuprins în . $\sigma _{p}$ $\sigma _{q)$ ${\hat {\sigma _{q)}}$

În acest caz

{\hat {\sigma ^{e)}}\neq M\mod n

{\hat {\sigma ^{e)}}\neq M\mod q

dar

{\hat {\sigma ^{e)}}=M\mod p

Astfel, adversarul poate găsi descompunerea ca rezultat al căutării GCD . $n$ $(n,{\hat {\sigma _{e)}} -m)$

Protecţie:

când semnați, adăugați un număr aleatoriu la mesaj (de exemplu, ora).
verificati semnatura inainte de a o trimite.

Vulnerabilitatea procesoarelor AMD

În 2021, o echipă de cercetători, inclusiv Universitatea de Tehnologie din Graz , Institutul de Tehnologie din Georgia și Lamarr Security Research, un centru de cercetare non-profit, a folosit vulnerabilitatea SMT [4] a procesoarelor AMD cu arhitecturi Zen , Zen 2 și Zen 3 pentru a „ crack" cheia de criptare RSA -4096 [5] [6] .

Note

↑ Yang S. Y. Criptanalysis of RSA. - M.-Izhevsk: Centrul de Cercetare „Dinamica obișnuită și haotică”, Institutul de Cercetare Calculatoare Izhevsk, 2011. - 312 p.
↑ Anunț de factorizare RSA-768 Arhivat 13 aprilie 2014 la Wayback Machine
↑ Factorizarea RSA-768 Arhivat 13 decembrie 2012 la Wayback Machine
↑ SQUIP: Exploatarea cozii de planificare Contention Side Channel PDF
↑ Anton Shilov. O nouă vulnerabilitate afectează toate procesoarele AMD Zen: ar putea fi necesar ca threadingul să fie dezactivat . Tom's Hardware (11 august 2022). Preluat: 12 august 2022.
↑ Vladimir Fetisov. S-a dovedit că tehnologia SMT din procesoarele Ryzen și EPYC vă permite să furați date confidențiale . 3DNews (11 august 2022). Preluat: 12 august 2022. (Rusă)