RSA kriptoanalízis

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2016. június 26-án áttekintett verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

Ez a cikk leírja az RSA nyilvános kulcsú kriptoalgoritmus használatának feltételeit , amely leegyszerűsíti a kriptoanalitikus támadásokat [1] , és az ilyen feltételek kiküszöbölésének módszereit.

Bevezetés

2009-től az RSA-alapú titkosítási rendszer 1024 bitestől kezdve biztonságosnak tekinthető. $n$

Svájcból, Japánból, Franciaországból, Hollandiából, Németországból és az Egyesült Államokból származó tudósok egy csoportja sikeresen kiszámította a 768 bites RSA kriptográfiai kulccsal titkosított adatokat. [2] A kutatók szerint munkájuk után csak az 1024 bites vagy annál hosszabb RSA kulcsok tekinthetők megbízható titkosítási rendszernek. Ezenkívül a következő három-négy évben fel kell hagyni az 1024 bites kulcsú titkosítással. [3]

Amint az a munka leírásából következik, a kulcsértékek kiszámítása az általános számmezőszita módszerrel történt .

Az első lépés (6-os és 1-es fokú polinompár kiválasztása) 80 processzoron körülbelül fél év számolást vett igénybe, ami körülbelül 3%-a volt az algoritmus fő szakaszában (szitálás) töltött időnek, amelyet számítógépek százait csaknem két évig. Ha ezt az időt interpoláljuk egy AMD Opteron 2,2 GHz-es processzor működésére 2 GB memóriával, akkor ez körülbelül 1500 év lenne. Az adatok feldolgozása a következő erőforrás-igényes lépés (lineáris algebra) szűrése után néhány processzoron több hetet vett igénybe. Az utolsó lépés a nem triviális OSLU-megoldások megtalálása után nem tartott tovább 12 óránál.

Az OSLU megoldást Wiedemann módszerrel több különálló klaszteren hajtották végre, és valamivel kevesebb, mint 4 hónapig tartott. Ugyanakkor a ritka mátrix mérete 192 796 550 x 192 795 550 volt, 27 795 115 920 nem nulla elemmel (azaz átlagosan 144 nem nulla elem soronként). A mátrix merevlemezen való tárolása körülbelül 105 gigabájtot vett igénybe. Ugyanakkor körülbelül 5 terabájt tömörített adatra volt szükség ennek a mátrixnak a felépítéséhez.

Ennek eredményeként a csoport ki tudott számítani egy 232 számjegyű kulcsot, amely hozzáférést nyit a titkosított adatokhoz.

A kutatók biztosak abban, hogy a faktorizációs módszerükkel az 1024 bites RSA-kulcs feltörése lehetséges lesz a következő évtizedben.[ mikor? ] .

A modulus két prím szorzatára való kiterjesztésének ismeretében az ellenfél könnyen megtalálhatja a titkos kitevőt , és ezzel megtörheti az RSA-t. Mindazonáltal a mai napig a leggyorsabb faktorizációs algoritmus a General Number Field Sieve, amelynek sebessége egy k bites egész szám esetén $n$ $d$

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

nem teszi lehetővé egy nagy egész szám ésszerű időn belüli lebontását. Megvizsgáljuk az RSA elleni lehetséges támadásokat, amelyek lehetővé teszik, hogy megtörjük ezt a rendszert anélkül, hogy az n modulust két prímszám szorzatára direkt kiterjesztené.

Elemental Attacks

Nézzünk meg néhány, az RSA algoritmussal való visszaéléshez kapcsolódó támadást.

Prímszám generálás

A következő további korlátozás vonatkozik a véletlen prímszámokra : $p$ $q$

$p$ és ne legyenek túl közel egymáshoz, különben meg lehet őket találni a Fermat-féle faktorizációs módszerrel . Ha azonban mindkét prímszámot egymástól függetlenül generáltuk, akkor ez a megszorítás nagy valószínűséggel automatikusan teljesül. $q$ $p$ $q$

Séma közös modulussal n

Kezdeti adatok: Annak elkerülése érdekében , hogy az egyes felhasználók számára különböző modulokat generáljanak, a biztonságos szerver egyetlen n-t használ az összes üzenet titkosításához. A Party ezt a szervert használja az üzenet fogadására $n=p*q$ $A$ $M$

Feladat: az ellenfél meg akarja fejteni a fél üzenetét . $A$

Úgy tűnik , hogy egy félnek küldött rejtjelezett szöveget a fél nem tudja visszafejteni , hacsak nem rendelkezik a titkos kulccsal . A párt azonban kitevőivel felbonthatja a modulust , majd ismeretében kiszámolhatja a titkos kitevőt . $C=M^{e_{a}}\mod n$ $A$ $B$ $d_{a}$ $B$ ${\displaystyle e_{b},d_{b))$ $n$ $e_{a}$ $d_{a}$

Védelem: minden felhasználónak saját modult kell használnia . $n$

Támadás az RSA aláírása ellen a közjegyzői rendszerben

Kiinduló adatok: - a közjegyző nyilvános kulcsa. Az ellenfél visszautasítást kap, amikor egy üzenetet próbál aláírni egy közjegyző által $(n,e)$ $M\in \mathbb {Z} _{n}$

Feladat: az ellenfél a közjegyző aláírását szeretné kérni az üzeneten . $M\in \mathbb {Z} _{n}$

Az ellenfél kiválaszt egy tetszőleges , kiszámítja és elküldi ezt az üzenetet a közjegyzőnek aláírásra. $r\in \mathbb {Z} _{n}$ $M'=r^{e}M\mod n$

Ha a közjegyző aláírja ezt az üzenetet:

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

akkor az ellenfél a kiszámítása után megkapja az üzenet aláírását . $S=S'/r\mod n$ $M$

Igazán, $S^{e}=(S')^{e}/r^{e}=(M')^{ed}/r^{e}\equiv M'/r^{e}=M (\modn)$

Védelem: aláíráskor adjon hozzá véletlenszerű számot (például időt) az üzenethez.

A titkos kitevő kis értékei

Kiinduló adatok: A visszafejtés (vagy digitális aláírás létrehozása) sebességének növelése érdekében a titkos kitevő bináris reprezentációjának nullától eltérő bitjeinek számát csökkentették (lásd az RSA algoritmus sebességét ). $d$

Feladat: Számítsa ki a titkos kitevőt ! $d$

1990 -ben Michael J. Wiener megmutatta, hogy kis érték esetén megtörhető az RSA rendszer, nevezetesen: $d$

Wiener-tétel:

Legyen , hol Akkor, ha ismert hol ,

n=pq

q<p<2q

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

(n,e)

ed=1\mod \varphi (n)

akkor van egy hatékony módszer a számításra .

d

Védelem: Ha tehát 1024 bites a mérete, akkor legalább 256 bitesnek kell lennie. $n$ $d$

A nyitott kitevő kis értékei

A titkosítás és a digitális aláírások ellenőrzési sebességének növelése érdekében használja a nyílt kitevő kis értékeit . Közülük a legkisebb . Az RSA algoritmus kriptográfiai erősségének növelése érdekében azonban javasolt a használata $e$ $e=3$

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

Khastad támadása

Kezdeti feltételek: A fél titkosított üzenetet küld a felhasználóknak . Minden felhasználónak saját nyilvános kulcsa van , és . A fél titkosítja az üzenetet az egyes felhasználók nyilvános kulcsával, és elküldi a megfelelő címzettnek. Az ellenfél figyeli az átviteli csatornát, és összegyűjti a továbbított titkosított szövegeket. $B$ $M$ ${\displaystyle P_{1},P_{2},...P_{k))$ $(n_{i},e_{i})$ $M<n_{i},\forall i$ $B$ $k$

Feladat: az ellenfél vissza akarja állítani az üzenetet . $M$

Hagyjuk , akkor az ellenfél felépülhet , ha . $e_{i}=3,\forall i$ $M$ $k \geqslant 3$

Bizonyíték

Valóban, ha az ellenfél megkapta , hol ${\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}

Feltételezzük, hogy másodprímek, különben az egytől eltérő legnagyobb közös osztó azt jelentené, hogy az egyik osztóját találjuk meg . A kínai maradéktételt alkalmazva a -ra , azt kapjuk , ${\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))$

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

Azóta _ _ $M<n_{i},\forall i$ $M^{3}<n_{1}n_{2}n_{3},\forall i$

C'=M^{3}

Vagyis az ellenfél vissza tudja állítani az üzenetet a kockagyökér kiszámításával . $M$ $C'$

Általánosságban elmondható, hogy ha minden nyitott kitevő egyenlő , akkor az ellenfél a következőnél helyreállhat . $e$ $M$ $k\geqslant e$

Fontolja meg a legegyszerűbb védekezést ez ellen a támadás ellen. Legyen az egyes felhasználók üzenete az eredeti üzenet valamilyen rögzített permutációja, például $M_{i}$ $M$

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

— üzenet az i-edik felhasználónak.

Hastad (Johan Hastad) megmutatta, hogy az ellenfél még ebben az esetben is képes helyreállítani az üzenetet megfelelő számú felhasználóval. $M$

Védelem: Ez a támadás csak a nyílt kitevő kis értékével lehetséges , ebben az esetben az RSA rendszer kriptográfiai erőssége tetszőleges permutációval érhető el, nem pedig rögzített permutációval, amire fentebb volt példa. $e$

Franklin-Reiter támadás

Kezdeti feltételek :

Két üzenet van , és ${\displaystyle M_{1},M_{2}\in \mathbb {Z} _{n))$

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

hol van valami nyitott polinom.

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

A nyilvános kulccsal rendelkező fél megkapja ezeket az üzeneteket a féltől , amely egyszerűen titkosítja az üzeneteket , és továbbítja a kapott titkosított szövegeket . $A$ $(n,e)$ $B$ $M_{1},M_{2}$ ${\displaystyle C_{1},C_{2))$

Feladat: Az ellenség, tudván , helyre akarja állítani . $(n,e,C_{1},C_{2},f)$ $M_{1},M_{2}$

Matthew K. Franklin és Michael K. Reiter bebizonyította a következő állítást:

Hadd 1) az RSA rendszer nyilvános kulcsa, és 2) és ,

(n,e)

e=3

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

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

valamilyen lineáris polinom esetében , Ekkor a ismeretében az ellenfél felépülhet

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

b\neq 0

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

M_{1},M_{2}

Bizonyíték

Valójában tetszőlegesen : $e$

$C_{1}={M^{e}}_{1}\mod n~~~~\rightarrow ~~~~M_{2}$ , a polinom gyöke

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

hanem a polinom gyöke is $M_{2}$

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

Így osztja mindkét polinomot. És az ellenfél használhatja az Euklidész algoritmust a GCD kiszámításához . Ha az eredmény lineáris polinomnak bizonyul, akkor azt megtaláljuk. ${\megjelenítési stílus (x-M_{2})}$ $(g_{1},g_{2})$ $M_{2}$

Amikor a gcd egy lineáris polinom, ezért az ellenfél hatékonyan tudja kiszámítani az üzeneteket . $e=3$ $(g_{1},g_{2})$ $M_{1},M_{2}$

Védelem: amikor az RSA rendszer feltörésének ideje arányos -val, így ez a támadás csak kis nyitott kitevővel használható. $e>3$ $e^{2}$

Támadás egy részben ismert titkos kitevő ellen

Kezdeti feltételek :

Az ellenfél ismeri a titkos kitevő bináris reprezentációjának egy részét . $d$

Feladat: visszaállítás . $d$

Kiderült, hogy:

Legyen az RSA rendszer titkos kulcsa, ahol a bitek mérete .

{\megjelenítési stílus (n,d)}

n=pq

\eta

Ekkor a szám legkevésbé jelentős bitjeinek ismeretében az ellenfél a -val arányos időn belül helyreállhat

\eta /4

d

d

e\log _{2}e

Az RSA rendszer feltörésének lehetősége abban az esetben, ha a nyitott kitevő kicsi, a következő érvelésből is nyilvánvaló: $e$

a definícióból és :

e

d

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

Mivel ez nyilvánvaló .

d<\varphi (n)

0<k\leqslant e

Adott érték mellett az ellenfél könnyen ki tudja számítani

k

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

Aztán at

q<p<2q

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

Így jó közelítés a .

{\hat {d))

d

Mivel csak elkülönülő értékek lehetségesek , az ellenfél olyan kifejezéseket tartalmazó sorozatot állíthat össze, amelyeknél az egyik elemének bináris reprezentációja megegyezik a titkos kitevő bináris reprezentációjának felső felével .

e

k

e

d

Védelem: nyitott kitevő növelése . $e$

Támadás kvantumszámítógéppel

Egy kvantumszámítógép segítségével , ha megépül, feltörhető lesz az RSA, mivel a Shor -féle kvantum algoritmus nagy számok faktorizálását teszi lehetővé meglehetősen rövid idő alatt. Az n modulust prímtényezőkre bontva (ez O (log n ) logikai Q-bitek segítségével időben megtehető ) kiszámítható a d titkos kitevő. ${\textstyle {O(\log ^{2}n\log ^{3}(\log n))))$

Az RSA rendszer megvalósításával kapcsolatos támadások

Runtime attack

Kezdeti feltételek:

Vegyünk egy olyan intelligens kártyát, amelynek mikroprocesszora egy beágyazott RSA privát kulccsal írja alá az üzeneteket.

Cél: Az ellenség titkos kitevőt akar szerezni . $d$

Paul Kocher olyan támadást javasolt, amely az intelligens kártya kódolójának bizonyos műveletek végrehajtásához szükséges idő nagy pontosságú mérésén alapul . Tekintsük ezt a támadást a gyors hatványozási algoritmust használó RSA rendszer példáján :

Az ellenfél intelligens kártya aláírásokat szerez nagyszámú véletlenszerű üzenethez , és méri az aláírás létrehozásához szükséges időt . ${\displaystyle M_{1},M_{2},\dots ,M_{k}\in \mathbb {Z} _{n))$ $T_{i}$

A támadás során a titkos kitevő értéke bitenként, a legkisebb jelentőségű bittől kezdve visszaáll: $d$

$d$ furcsa tehát . $d_{0}=1$
ha akkor az intelligens kártya mikroprocesszorának három modulo szorzást kell végrehajtania , szemben a kettővel, amikor szükséges (lásd a gyors hatványozási algoritmust ). Jelöljük a processzor számítási idejét az üzenethez . $d_{1}=1$ $n$ $d_{1}=0$ $t_{i}$ $M_{i}$

Kocher megmutatta, hogy amikor két együttes és korrelál . Abban az esetben azonban, ha függetlenek. Így a korrelációs elemzéshez folyamodva az ellenfél meg tudja határozni .

d_{1}=1

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

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

d_{1}=0

d_{1}

hasonlóan definiálható . $d_{2},d_{3},\dots$

Vegye figyelembe, hogy kis nyílt kitevő esetén egy részben nyílt titkos kitevő elleni támadást lehet alkalmazni . Ebben az esetben elegendő a titkos kitevő bitjeinek felét visszaállítani . $e$ $d$

Biztonság: Megfelelő késleltetést kell hozzáadni, hogy a gyors hatványozási algoritmus minden lépése meghatározott ideig tartson.

RSA hardver megvalósítási hiba támadás

Kezdeti feltételek:

Vegyünk egy olyan intelligens kártyát, amelynek mikroprocesszora egy beágyazott RSA privát kulccsal írja alá az üzeneteket. A kártya mikroprocesszora a kínai maradék tételt használja az aláírási folyamat felgyorsítására. Az ellenfél hibás működést próbál okozni a mikroprocesszor számításaiban.

Feladat: az ellenfél ki akarja számítani a modulo . $n$

A kínai maradék tétel használata megnöveli a digitális aláírás létrehozásának sebességét.

Sőt, számítással

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

, ahol

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

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

, ahol

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

aláírást kaphat

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

, ahol

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

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

Nyilvánvaló, hogy a számítások sokkal gyorsabbak, mint a modulo hatványozás .

{\megjelenítési stílus (a), (b)}

n

Hagyja, hogy az ellenség cselekedetei kudarcot okozzanak, ami az aláírás egy bitjének hibáját eredményezi. Ekkor a vagy közül legalább az egyik helytelenül van kiszámítva. Tegyük fel, hogy a hibát a . $\sigma _{p}$ ${\displaystyle \sigma _{q))$ ${\displaystyle {\hat {\sigma _{q))))$

Ebben az esetben

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

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

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

Így az ellenfél megtalálhatja a dekompozíciót a GCD keresés eredményeként . $n$ $(n,{\hat {\sigma _{e))}-m)$

Védelem:

aláíráskor adjon hozzá véletlenszerű számot az üzenethez (például időt).
elküldés előtt ellenőrizze az aláírást.

Sebezhetőség az AMD processzorokban

2021-ben egy kutatócsoport, köztük a Grazi Műszaki Egyetem, a Georgiai Műszaki Intézet és a Lamarr Security Research non-profit kutatóközpont, felhasználta az SMT [4] sebezhetőségét a Zen , Zen 2 és Zen 3 architektúrájú AMD processzorokban , hogy " feltörni" az RSA -4096 titkosítási kulcsot [5] [6] .

Jegyzetek

↑ Yang S. Y. Az RSA kriptoanalízise. - M.-Izhevsk: Kutatóközpont "Szabályos és Kaotikus Dinamika", Izhevszki Számítógépes Kutatóintézet, 2011. - 312 p.
↑ RSA-768 faktorizációs bejelentés archiválva : 2014. április 13. a Wayback Machine -nél
↑ RSA-768 faktorizáció archiválva : 2012. december 13. a Wayback Machine -nél
↑ SQUIP: Az ütemező várólista versenyoldali PDF csatorna kihasználása
↑ Anton Shilov. Új sebezhetőség az összes AMD Zen CPU-t érinti: Lehet, hogy a szálakat le kell tiltani . Tom's Hardware (2022. augusztus 11.). Letöltve: 2022. augusztus 12.
↑ Vlagyimir Fetisov. Kiderült, hogy az SMT technológia a Ryzen és az EPYC processzorokban lehetővé teszi a bizalmas adatok ellopását . 3DNews (2022. augusztus 11.). Letöltve: 2022. augusztus 12. (Orosz)