Kryptoanalýza RSA

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. června 2016; kontroly vyžadují 8 úprav .

Tento článek popisuje podmínky pro použití kryptoalgoritmu veřejného klíče RSA , který zjednodušuje kryptoanalytické útoky [1] , a způsoby, jak tyto stavy eliminovat.

Úvod

Od roku 2009 je šifrovací systém založený na RSA považován za bezpečný počínaje 1024 bity. $n$

Skupina vědců ze Švýcarska, Japonska, Francie, Nizozemska, Německa a Spojených států úspěšně vypočítala data zašifrovaná pomocí 768bitového kryptografického klíče RSA. [2] Podle výzkumníků lze po jejich práci za spolehlivý šifrovací systém považovat pouze klíče RSA s délkou 1024 bitů a více. Kromě toho by se v příštích třech až čtyřech letech mělo opustit šifrování s klíčem 1024 bitů. [3]

Jak vyplývá z popisu práce, výpočet klíčových hodnot byl proveden metodou obecného číselného pole síta .

První krok (výběr dvojice polynomů stupně 6 a 1) zabral asi půl roku výpočtů na 80 procesorech, což byla asi 3 % času stráveného na hlavní fázi algoritmu (sifting), která byla provedena na stovky počítačů za téměř dva roky. Pokud bychom tuto dobu interpolovali na provoz jednoho procesoru AMD Opteron 2,2 GHz s pamětí 2 GB, pak by to bylo zhruba 1500 let. Zpracování dat po prosévání pro další krok náročný na zdroje (lineární algebra) trvalo na malém počtu procesorů několik týdnů. Poslední krok po nalezení netriviálních řešení OSLU netrval déle než 12 hodin.

Řešení OSLU bylo provedeno Wiedemannovou metodou na několika samostatných shlucích a trvalo o něco méně než 4 měsíce. Zároveň byla velikost řídké matice 192 796 550x192 795 550 s 27 795 115 920 nenulovými prvky (tj. průměrně 144 nenulových prvků na řádek). Uložení matice na pevný disk trvalo asi 105 gigabajtů. Současně bylo zapotřebí asi 5 terabajtů komprimovaných dat k vytvoření této matice.

Výsledkem bylo, že skupina byla schopna vypočítat 232místný klíč, který otevírá přístup k šifrovaným datům.

Výzkumníci jsou přesvědčeni, že pomocí jejich metody faktorizace bude možné prolomit 1024bitový klíč RSA během příští dekády.[ kdy? ] .

Při znalosti expanze modulu na součin dvou prvočísel může protivník snadno najít tajný exponent a rozbít tak RSA. Dosud je však nejrychlejším faktorizačním algoritmem General Number Field Sieve, jehož rychlost pro k-bitové celé číslo je $n$ $d$

$\exp((c+o(1))k^{\frac {1}{3}}\log ^{\frac {2}{3}}k),$ pro některé , $c<2$

neumožňuje rozklad velkého celého čísla v rozumném čase. Zvážíme možné útoky na RSA, které nám umožní prolomit tento systém bez použití přímé expanze modulu n na součin dvou prvočísel.

Elementární útoky

Podívejme se na několik útoků souvisejících se zneužitím algoritmu RSA.

Generování prvočísel

Pro náhodná prvočísla platí následující dodatečné omezení : $p$ $q$

$p$ a neměly by být příliš blízko u sebe, jinak je bude možné najít pomocí Fermatovy faktorizační metody . Pokud by však byla obě prvočísla generována nezávisle, pak je toto omezení s velkou pravděpodobností automaticky splněno. $q$ $p$ $q$

Schéma se společným modulem n

Počáteční data: Aby se zabránilo generování různých modulů pro každého uživatele, zabezpečený server používá k šifrování všech zpráv jediné n. Party používá tento server k přijetí zprávy $n=p*q$ $A$ $M$

Úkol: protivník chce dešifrovat zprávu strany . $A$

Zdálo by se, že šifrovaný text zaslaný straně nemůže být dešifrován, pokud nemá tajný klíč . Strana však může použít své exponenty k rozkladu modulu a poté, s vědomím , vypočítat tajný exponent . $C=M^{e_{a}}\mod n$ $A$ $B$ $d_{a}$ $B$ ${\displaystyle e_{b},d_{b))$ $n$ $e_{a}$ $d_{a}$

Ochrana: každý uživatel musí používat svůj vlastní modul . $n$

Útok na podpis RSA v notářském schématu

Výchozí údaje: - veřejný klíč notáře. Při pokusu o podepsání zprávy notářem obdrží protivník odmítnutí $(n,e)$ $M\in \mathbb {Z} _{n}$

Úkol: protivník chce získat podpis notáře na zprávě . $M\in \mathbb {Z} _{n}$

Protivník si vybere libovolnou , vypočítá a odešle tuto zprávu notáři k podpisu. $r\in \mathbb {Z} _{n}$ $M'=r^{e}M\mod n$

Pokud notář podepíše tuto zprávu:

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

pak protivník po vypočítání získá podpis zprávy . $S=S'/r\mod n$ $M$

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

Ochrana: při podepisování přidejte do zprávy nějaké náhodné číslo (například čas).

Malé hodnoty tajného exponentu

Počáteční data: Pro zvýšení rychlosti dešifrování (nebo vytvoření digitálního podpisu) byl snížen počet nenulových bitů binární reprezentace tajného exponentu (viz rychlost algoritmu RSA ). $d$

Úkol: Vypočítejte tajný exponent . $d$

V roce 1990 Michael J. Wiener ukázal, že v případě malé hodnoty je možné prolomit systém RSA, a to: $d$

Wienerova věta:

Nechť , kde Pak, pokud je známo , kde ,

n=pq

q<p<2q

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

(n,e)

ed=1\mod \varphi (n)

pak existuje efektivní způsob, jak vypočítat .

d

Ochrana: Pokud má tedy velikost 1024 bitů, musí být alespoň 256 bitů dlouhá. $n$ $d$

Malé hodnoty otevřeného exponentu

Pro zvýšení rychlosti šifrování a ověřování digitálních podpisů používejte malé hodnoty otevřeného exponentu . Nejmenší z nich . Aby se však zvýšila kryptografická síla algoritmu RSA, doporučuje se použít $E$ $e=3$

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

Útok Khastadu

Počáteční podmínky: Strana odešle uživatelům šifrovanou zprávu . Každý uživatel má svůj vlastní veřejný klíč a . Strana zašifruje zprávu pomocí veřejného klíče každého uživatele a odešle ji příslušnému příjemci. Protivník naslouchá přenosovému kanálu a shromažďuje přenášené šifrové texty. $B$ $M$ ${\displaystyle P_{1},P_{2},...P_{k))$ $(n_{i},e_{i})$ $M<n_{i},\forall i$ $B$ $k$

Úkol: protivník chce obnovit zprávu . $M$

Nechte , pak se soupeř může zotavit , pokud . $e_{i}=3,\forall i$ $M$ $k \geqslant 3$

Důkaz

Pokud totiž soupeř obdržel , kde ${\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}

Předpokládáme, že jsou coprime, jinak by největší společný dělitel jiný než jedna znamenal nalezení dělitele jednoho z . Aplikováním čínské věty o zbytku na , dostaneme , ${\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))

Od té doby $M<n_{i},\forall i$ $M^{3}<n_{1}n_{2}n_{3},\forall i$

C'=M^{3}

To znamená, že protivník může obnovit zprávu výpočtem odmocniny z . $M$ $C'$

Obecně platí, že pokud jsou všechny otevřené exponenty stejné , protivník se může zotavit při . $E$ $M$ $k\geqslant e$

Zvažte nejjednodušší obranu proti tomuto útoku. Nechť je zpráva pro každého uživatele nějakou pevnou permutací původní zprávy $M_{i}$ $M$

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

— zpráva pro i-tého uživatele.

Hastad (Johan Hastad) ukázal, že i v tomto případě dokáže protivník obnovit zprávu s dostatečným počtem uživatelů. $M$

Ochrana: Tento útok je možný pouze s malou hodnotou otevřeného exponentu , v takovém případě lze kryptografické síly systému RSA dosáhnout pomocí libovolné permutace, nikoli fixní, jejíž příklad byl uveden výše. $E$

Franklin-Reiterův útok

Počáteční podmínky :

Existují dvě zprávy a ${\displaystyle M_{1},M_{2}\in \mathbb {Z} _{n))$

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

kde je nějaký otevřený polynom.

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

Strana s veřejným klíčem přijímá tyto zprávy od strany , která zprávy jednoduše zašifruje a odešle přijaté šifrované texty . $A$ $(n,e)$ $B$ $M_{1},M_{2}$ ${\displaystyle C_{1},C_{2))$

Úkol: Nepřítel, který ví , chce obnovit . $(n,e,C_{1},C_{2},f)$ $M_{1},M_{2}$

Matthew K. Franklin a Michael K. Reiter dokázali následující tvrzení:

Nechat 1) je veřejný klíč systému RSA a 2) a ,

(n,e)

e=3

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

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

pro nějaký lineární polynom , Pak, když ví , může se protivník zotavit

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

b\neq 0

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

M_{1},M_{2}

Důkaz

Opravdu, pro svévolné : $E$

$C_{1}={M^{e}}_{1}\mod n~~~~\rightarrow ~~~~M_{2}$ , je kořenem polynomu

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

ale je také kořenem polynomu $M_{2}$

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

Rozdělí tedy oba polynomy. A protivník může použít euklidovský algoritmus k výpočtu GCD . Pokud se výsledek ukáže jako lineární polynom, bude nalezen. $(x-M_{2})$ $(g_{1},g_{2})$ $M_{2}$

Když je gcd lineární polynom, a proto může protivník efektivně vypočítat zprávy . $e=3$ $(g_{1},g_{2})$ $M_{1},M_{2}$

Ochrana: když je doba prolomení systému RSA úměrná , tak tento útok lze použít pouze s malými hodnotami otevřeného exponentu. $e>3$ $e^{2}$

Útok na částečně známý tajný exponent

Počáteční podmínky :

Protivník zná část binární reprezentace tajného exponentu . $d$

Úkol: obnovit . $d$

Ukázalo se, že:

Nechť je tajný klíč systému RSA, kde je velikost bitů.

(n,d)

n=pq

\eta

Poté, když zná nejméně významné bity čísla , může se protivník zotavit za čas úměrný tomu

\eta /4

d

d

e\log _{2}e

Možnost cracknutí systému RSA v případě, kdy je otevřený exponent malý, je zřejmá i z následující úvahy: $E$

z definice a :

E

d

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

Vzhledem k tomu , je zřejmé .

d<\varphi (n)

0<k\leqslant e

Vzhledem k dané hodnotě může protivník snadno vypočítat

k

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

Potom v

q<p<2q

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

Je tedy dobrá aproximace pro .

{\hat {d))

d

Protože jsou možné pouze odlišné hodnoty , může protivník sestavit řadu obsahující členy, pro které je binární reprezentace jednoho z jejích prvků stejná jako horní polovina binární reprezentace tajného exponentu .

E

k

E

d

Ochrana: otevřené zvýšení exponentu . $E$

Útok s kvantovým počítačem

S pomocí kvantového počítače , pokud bude postaven, bude možné prolomit RSA, protože Shorův kvantový algoritmus umožňuje faktorizaci velkých čísel v poměrně krátkém čase. Rozložením modulu n na prvočinitele (toto lze provést v čase pomocí O (log n ) logických Q-bitů ) lze vypočítat tajný exponent d. ${\textstyle {O(\log ^{2}n\log ^{3}(\log n))))$

Útoky související s implementací systému RSA

Runtime útok

Počáteční podmínky:

Představte si čipovou kartu , jejíž mikroprocesor podepisuje zprávy pomocí integrovaného soukromého klíče RSA.

Cíl: Nepřítel chce získat tajného exponenta . $d$

Paul Kocher navrhl útok založený na vysoce přesných měřeních času, který kodér čipových karet potřebuje k provedení určitých operací. Uvažujme tento útok na příkladu systému RSA využívajícího rychlý umocňovací algoritmus :

Protivník získává podpisy čipových karet pro velký počet náhodných zpráv a měří čas potřebný k vygenerování jejich podpisů . ${\displaystyle M_{1},M_{2},\tečky ,M_{k}\in \mathbb {Z} _{n))$ $T_{i}$

Během útoku se hodnota tajného exponentu obnovuje bit po bitu, počínaje nejméně významným bitem: $d$

$d$ liché, proto . $d_{0}=1$
pokud pak mikroprocesor čipové karty potřebuje provést tři násobení modulo , na rozdíl od dvou potřebných, když (viz algoritmus rychlého umocňování ). Označme dobu výpočtu procesoru pro zprávu . $d_{1}=1$ $n$ $d_{1}=0$ $t_{i}$ $M_{i}$

Kocher ukázal, že když dva soubory a korelují . Ovšem v případě , že jsou nezávislí. Takže, uchýlit se ke korelační analýze , může protivník určit .

d_{1}=1

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

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

d_{1}=0

d_{1}

lze definovat podobně . $d_{2},d_{3},\dots$

Všimněte si, že v případě malého otevřeného exponentu lze použít útok na částečně otevřený tajný exponent . V tomto případě stačí obnovit polovinu bitů tajného exponentu . $E$ $d$

Zabezpečení: Musí být přidáno odpovídající zpoždění, aby každý krok algoritmu rychlého umocňování trval pevně stanovenou dobu.

Útok selhání implementace hardwaru RSA

Počáteční podmínky:

Představte si čipovou kartu , jejíž mikroprocesor podepisuje zprávy pomocí integrovaného soukromého klíče RSA. Mikroprocesor karty používá čínskou větu o zbytku k urychlení procesu podepisování. Protivník se snaží způsobit poruchu ve výpočtech mikroprocesoru.

Úkol: protivník chce vypočítat modulo . $n$

Použití čínské věty o zbytku zvyšuje rychlost vytváření digitálního podpisu.

Vlastně výpočtem

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

, kde

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

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

, kde

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

můžete získat podpis

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

, kde

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

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

Je zřejmé, že výpočty jsou mnohem rychlejší než umocňování modulo .

(a), (b)

n

Nechte akce nepřítele způsobit selhání, které má za následek defekt v jednom bitu podpisu. Pak je alespoň jeden z nebo vypočítán nesprávně. Předpokládejme, že závada je obsažena v . $\sigma _{p}$ ${\displaystyle \sigma _{q))$ ${\displaystyle {\klobouček {\sigma _{q))))$

V tomto případě

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

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

ale

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

Protivník tak může najít rozklad jako výsledek hledání GCD . $n$ $(n,{\hat {\sigma _{e))}-m)$

Ochrana:

při podepisování přidejte do zprávy nějaké náhodné číslo (například čas).
před odesláním zkontrolujte podpis.

Chyba zabezpečení v procesorech AMD

V roce 2021 tým výzkumníků včetně Technologické univerzity v Grazu , Georgia Institute of Technology a neziskového výzkumného centra Lamarr Security Research použil zranitelnost SMT [4] v procesorech AMD s architekturami Zen , Zen 2 a Zen 3 k „ crack" šifrovací klíč RSA -4096 [5] [6] .

Poznámky

↑ Yang S. Y. Kryptoanalýza RSA. - M.-Iževsk: Výzkumné centrum "Regulární a chaotická dynamika", Iževský institut počítačového výzkumu, 2011. - 312 s.
↑ Oznámení faktorizace RSA-768 Archivováno 13. dubna 2014 na Wayback Machine
↑ Faktorizace RSA-768 Archivováno 13. prosince 2012 na Wayback Machine
↑ SQUIP: Využití PDF postranního kanálu soupeření plánovače
↑ Anton Šilov. Nová chyba zabezpečení se týká všech procesorů AMD Zen: Možná bude nutné zakázat vytváření vláken . Tom's Hardware (11. srpna 2022). Staženo: 12. srpna 2022.
↑ Vladimír Fetisov. Ukázalo se, že technologie SMT v procesorech Ryzen a EPYC umožňuje krást důvěrná data . 3DNews (11. srpna 2022). Staženo: 12. srpna 2022. (Ruština)