Kopparsmedens attack

Coppersmiths attack beskriver en klass av kryptografiska attacker på kryptosystemet RSA med offentlig nyckel baserad på Coppersmith-metoden . Särskilda tillämpningar av Coppersmith-metoden för att attackera RSA inkluderar fall när den offentliga exponenten e är liten eller när delvis kunskap om en primfaktor för den hemliga nyckeln är tillgänglig.

RSA grunderna

Huvudartikel: RSA (algoritm)

Den publika nyckeln i RSA-systemet är en tupel av heltal $(N,e)$ , där N är produkten av två primtal p och q . Den hemliga nyckeln ges av ett heltal d som uppfyller $ed\equiv 1{\pmod {(p-1)(q-1)}}$ ; på motsvarande sätt kan den hemliga nyckeln ges av $d_{p}\equiv d{\pmod {p-1}}$ och $d_{q}\equiv d{\pmod {q-1}}$ om den kinesiska restsatsen används för att förbättra dekrypteringshastigheten, se CRT-RSA . Kryptering av ett meddelande M producerar chiffertexten ${\displaystyle C\equiv M^{e}{\pmod {N}}} ,$ som kan dekrypteras med $d$ genom att beräkna $C^{d}\equiv M{\pmod {N}}$ .

Låg offentlig exponentattack

För att minska tiden för kryptering eller signaturverifiering är det användbart att använda en liten offentlig exponent ( $\displaystyle e} )$ { . I praktiken är vanliga val för $e$ 3, 17 och 65537 $(2^{16}+1)$ . Dessa värden för e är Fermat-primtal , ibland kallade $F_{0},F_{2}$ respektive F $\displaystyle F_{4}}$$(F_{x}=2^{2^{x}}+1)$ . De är valda för att de gör den modulära exponentieringsoperationen snabbare. Efter att ha valt sådan $e$ är det enklare att testa om $\gcd(e,p-1)=1$ och $\gcd(e,q-1)=1$ under generering och testning av primtal i steg 1 av nyckelgenereringen . Värden på $p$ eller $q$ som inte klarar detta test kan avvisas där och då. (Ännu bättre: om e är primtal och större än 2, då kan testet $p{\bmod {e}}\neq 1$ ersätta det dyrare testet $\gcd(p-1,e)=1$ .)

Om den offentliga exponenten är liten och klartexten $m$ är mycket kort, kan RSA-funktionen vara lätt att invertera, vilket gör vissa attacker möjliga. Utfyllnadsscheman säkerställer att meddelanden har full längd, men dessutom att välja offentlig exponent $e=2^{16}+1$ rekommenderas. När detta värde används kräver signaturverifiering 17 multiplikationer, till skillnad från cirka 25 när en slumpmässig $e$ av liknande storlek används. Till skillnad från låg privat exponent (se Wieners attack ), är attacker som gäller när ett litet $e$ används långt ifrån en total break , vilket skulle återställa den hemliga nyckeln d . De mest kraftfulla attackerna på låg offentlig exponent RSA är baserade på följande teorem, som beror på Don Coppersmith .

Kopparsmedsmetod

Huvudartikel: Kopparsmedsmetoden

Sats 1 (Coppersmith)

Låt N vara ett heltal och $f\in {\mathbb {Z} [x]$ vara ett moniskt polynom med graden $d$ över heltalen. Ställ in $X=N^{{\frac {1}{d}}-\epsilon }$ för ${\frac {1}{d}} >\epsilon >0$ . Sedan, givet $\left\langle N,f\right\rangle$ , kan angriparen (Eve) effektivt hitta alla heltal $x_{0}<X$ som uppfyller $f(x_{0})\equiv 0{\pmod {N}}$ . Körtiden domineras av tiden det tar att köra LLL-algoritmen på ett gitter med dimensionen O $(w)$ med $\displaystyle w=\ min \left\{{\frac {1}{\epsilon }},\log _{2}N\right\}}$ { .

Denna sats anger att det finns en algoritm som effektivt kan hitta alla rötter till $f$ modulo $N$ som är mindre än $X=N^{\frac {1} {d}}$ . När $X$ blir mindre, minskar algoritmens körtid. Denna sats styrka är förmågan att hitta alla små rötter av polynom modulo a sammansatt $N$ .

Håstads utsända attack

Den enklaste formen av Håstads attack presenteras för att underlätta förståelsen. Det allmänna fallet använder Coppersmith-metoden.

Antag att en avsändare skickar samma meddelande $M$ i krypterad form till ett antal personer ${\displaystyle P_{1};P_{2};\dots ;P_{k}} ,$ var och en använder samma lilla offentliga exponent $e$ , säg $e=3$ , och olika moduler ${\displaystyle \left\langle N_{i},e\right\rangle$ . Ett enkelt argument visar att så snart $k\geq 3$ chiffertexter är kända är meddelandet $M$ inte längre säkert: Antag att Eva skär $C_{1 },C_{2}$ och $C_{3}$ , där $\displaystyle C_{i}\equiv M^{3}{\pmod {N_ {i}}}}$ . Vi kan anta $\gcd(N_{i},N_{j})=1$ för alla $i,j$ (annars är det möjligt att beräkna en faktor av ett av talen $N_{i}$ genom att beräkna $\gcd(N_{i},N_{j})$ .) Genom att Kinesisk restsats , hon kan beräkna $C\in \mathbb {Z} _{N_{1}N_{2}N_{3}}^{*}$ så att $C\equiv C_{i}{\pmod {N_{i}}$ . Sedan $C\equiv M^{3}{\pmod {N_{1}N_{2}N_{3}}}$ ; men eftersom $M<N_{i}$ för alla $i$ , har vi $M^{3}<N_{1} N_{2}N_{3}$ . Således $C=M^{3}$ över heltalen, och Eva kan beräkna kubroten av $C$ för att få $M$ .

För större värden på $e$ behövs fler chiffertexter, speciellt $e$ chiffertexter räcker.

Generaliseringar

Håstad visade också att applicering av en linjär utfyllnad på $M$ före kryptering inte skyddar mot denna attack. Antag att angriparen lär sig att $C_{i}=f_{i}(M)^{e}$ för $1\leq i\leq k$ och någon linjär funktion $f_{i}$ , dvs. Bob applicerar en knapp på meddelandet $M$ innan det krypteras så att mottagarna får lite olika meddelanden. Till exempel, om $M$ är $m$ bitar lång, kan Bob kryptera $M_{i}=i2^{m}+M$ och skicka detta till $i$ -:e mottagaren.

Om en tillräckligt stor grupp människor är inblandade kan angriparen återställa klartexten M $\displaystyle M_{i}}$ från all chiffertext med liknande metoder. Mer allmänt bevisade Håstad att ett system av univariata ekvationer modulo relativt prime kompositer $g_{i}(M)\equiv 0{\pmod {N_{i}}}$ som att tillämpa vilket fast polynom , skulle kunna lösas om tillräckligt många ekvationer tillhandahålls. Denna attack föreslår att randomiserad utfyllnad bör användas i RSA-kryptering .

Sats 2 (Håstad)

Antag att $displaystyle N_{1},\dots ,N_{k}}$$N_{\ text{min}}=\min _{i}\{N_{i}\}$ är relativt primtal heltal och sätter . Låt $g_{i}(x)\in \mathbb {Z} /N_{i}[x]$ vara $k$ polynom med maximum grad $q$ . Anta att det finns en unik $\text{min}}}$$g_{i}(M)\equiv 0{\ pmod {N_{i}}}$ uppfyller för alla $i\in \left\{1,\dots ,k\right\}$ . Antag vidare att $k>q$ . Det finns en effektiv algoritm som, givet $N_{i},g_{i}(x)\right\rangle }$ för alla $i$ , beräknar $M$ .

Bevis

Eftersom $N_{i}$ är relativt primtal $T_$ den kinesiska restsatsen användas för att beräkna koefficienter $T_{i}$ som uppfyller och $T_{i}\equiv 0{\pmod {N_{j}}}$ för alla $i\neq j$ . Inställning $g(x)=\summa T_{i}\cdot g_{i}(x)$ vet vi att $g(M)\equiv 0{\pmod {\prod N_{i}}}$ . Eftersom $T_{i}$ inte är noll, har vi att $g(x)$ också är noll. Graden av $g(x)$ är som mest $q$ . Enligt Coppersmiths teorem kan vi beräkna alla heltalsrötter $\displaystyle x_{0}}$$g(x_{0})\equiv 0{\pmod {\prod N_{i}}}$ som uppfyller ∏ och $\left|x_{0}\right|<\left(\prod N_{i}\right)^{\frac {1}{q}}$ . Vi vet dock att ${\displaystyle M<N_{\text{min}}<\left(\prod N_{i}\right )^{\frac {1}{k}}<\left(\prod N_{i}\right)^{\frac {1}{q}}}, så M {\$ displaystyle $}$ är bland rötterna som hittades av Coppersmiths teorem.

Detta teorem kan appliceras på problemet med sändnings- RSA på följande sätt: Antag att ${\displaystyle f_{i}(x)} ,$$\displaystyle i}$ -th klartexten är utfylld med ett polynom så att $g_{i}={\big (}f_{i}(x){\big )}^{e_{i} }-C_{i}{\bmod {N}}_{i}$ . Då $g_{i}(M)\equiv 0{\bmod {N}}_{i}$ sant, och Coppersmiths metod kan användas. Attacken lyckas en gång ${\displaystyle k>\max _{i}(e_{i}\cdot \deg f_{i})} ,$ där $k$ är antalet meddelanden. Det ursprungliga resultatet använde Håstads variant istället för den fullständiga kopparsmedsmetoden. Som ett resultat krävdes $k=O(q^{2})$ meddelanden, där $q=\max _{i}(e_{i}\cdot \deg f_{i})$ .

Franklin–Reiter-relaterade meddelandeattack

Franklin och Reiter identifierade en attack mot RSA när flera relaterade meddelanden är krypterade: Om två meddelanden skiljer sig endast med en känd fast skillnad mellan de två meddelandena och är RSA - krypterade under samma RSA- modul $N$ , är det möjligt för att återställa dem båda. Attacken beskrevs ursprungligen med offentlig exponent $e=3$ , men den fungerar mer allmänt (med ökande kostnad när $e$ växer).

Låt $\left\langle N;e_{i}\right\rangle$ vara Alices publika nyckel. Antag $M_{1};M_{2}\in \mathbb {Z} _{N}$ är två distinkta meddelanden som uppfyller $M_ {1}\equiv f(M_{2}){\pmod {N}}$ för något allmänt känt polynom $f\in \mathbb {Z} _{N}[x]$ . För att skicka $M_{1}$ och M $\displaystyle M_{2}}$ till Alice, kan Bob naivt kryptera meddelandena och sända de resulterande chiffertexterna $C_{1};C_{2}$ . Eva kan lätt återställa $M_{1};M_{2}$ , given $C_{1};C_{2}$ , genom att använda följande teorem:

Sats 3 (Franklin–Reiter)

Låt $\left\langle N,e\right\rangle$ vara en offentlig RSA-nyckel. Låt $M_{1}\neq M_{2}\in \mathbb {Z} _{N}^{*}$ uppfylla $M_{1}\equiv f(M_{2}){\pmod {N}}$ för något linjärt polynom $f=ax+b \in \mathbb {Z} _{N}[x]$ med $b\neq 0$ . Sedan, givet ${\displaystyle \left\langle N,e,C_{1},C_{2},f\right\rangle } ,$ kan angriparen (Eve) återhämta sig $M_{1},M_{2}$ i tid kvadratisk i $e\cdot \log N$ .

Bevis

Eftersom $C_{1}\equiv M_{1}^{e}{\pmod {N}}$ vet vi att $M_{2}$ är en rot av polynomet $g_{1}(x)=f(x)^{e}-C_{1} \in \mathbb {Z} _{N}[x]$ . På liknande sätt $M_{2}$ en rot av $g_{2}(x)=x^{e}- C_{2}\in \mathbb {Z} _{N}[x]$ . Därför delar den linjära faktorn $x-M_{2}$ båda polynomen . Därför kan Eva beräkna den största gemensamma divisorn $\gcd(g_{1},g_{2})$ av $g_{1}$ och ${\ displaystyle g_{2}}$ , och om $\gcd$ visar sig vara linjär, hittas ${\displaystyle M_{2}} .$ Gcd $\gcd$ kan beräknas i kvadratisk tid i $e$ och $N}$ med hjälp av den euklidiska algoritmen .

Coppersmith's short-pad attack

Liksom Håstads och Franklin–Reiters attacker utnyttjar denna attack en svaghet hos RSA med offentlig exponent $e=3$ . Coppersmith visade att om randomiserad utfyllnad som föreslagits av Håstad används felaktigt, så RSA- kryptering inte säker.

Anta att Bob skickar ett meddelande $M$ till Alice med en liten slumpmässig utfyllnad innan han krypterar det. En angripare, Eva, fångar upp chiffertexten och hindrar den från att nå sin destination. Bob bestämmer sig för att skicka om $M$ till Alice eftersom Alice inte svarade på hans meddelande. Han fyller slumpmässigt på $M$ igen och sänder den resulterande chiffertexten. Eve har nu två chiffertexter som motsvarar två krypteringar av samma meddelande med två olika slumpmässiga block.

Även om Eve inte känner till vilken slumpmässig utfyllnad som används, kan hon fortfarande återställa meddelandet $M$ genom att använda följande sats, om den slumpmässiga utfyllnaden är för kort.

Sats 4 (Coppersmith)

Låt $\left\langle N,e\right\rangle$ vara en offentlig RSA- nyckel, där $N$ är $n$ bitar lång. Ställ in $m=\left\lfloor {\frac {n}{e^{2}}}\right\rfloor$ . Låt $M\in \mathbb {Z} _{N}^{*}$ vara ett meddelande med högst längd $nm$ bitar. Definiera $M_{1}=2^{m}M+r_{1}$ och $M_{2}=2^ {m}M+r_{2}$ , där $r_{1}$ och $r_{2}$ är distinkta heltal med $0 \leq r_{1},r_{2}<2^{m}$ . Om Eva ges $\left\langle N,e\right\rangle$ och krypteringarna $C_{1},C_{2}$ av $M_{1},M_{2}$ (men ges inte $r_{1}$ eller $r_{2}$ ), hon kan effektivt återställa $M$ .

Bevis

Definiera $g_{1}(x,y)=x^{e}-C_{1}$ och $g_{2}(x,y)=(x+y)^{e}-C_{2}$ . Vi vet att när ${\displaystyle y=r_{2}-r_{1}} ,$ har dessa polynom $x=M_{1}$ som en gemensam rot. Med andra ord, $\Delta =r_{2}-r_{1}$ är en rot av den resulterande $h(y)=\operatörsnamn {res} _{x}(g_{1},g_{2})\in \mathbb {Z} _{N}[y]$ . Dessutom, $|\Delta |<2^{m}<N^{\frac {1}{e^{2}}}$ . Därför $\Delta$ en liten rot av $h$ modulo $N$ , och Eva kan effektivt hitta den med Coppersmith-metoden. När $\Delta$ är känd kan Franklin-Reiter-attacken användas för att återställa $M_{2}$ och följaktligen $M$ .

Se även

• ROCA attack