Wiener angreb

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. februar 2019; checks kræver 8 redigeringer .

Wiener-angrebet , opkaldt efter kryptolog Michael J. Wiener, er en form for kryptografisk angreb mod RSA-algoritmen . Angrebet bruger den fortsatte fraktionmetode til at bryde systemet med en lille lukket eksponent . $d$

Kort om RSA

Før du starter en beskrivelse af, hvordan Wieners angreb fungerer, er det værd at introducere nogle begreber, der bruges i RSA [1] . Se RSA- hovedartiklen for flere detaljer .

For at kryptere beskeder i henhold til RSA -skemaet bruges en offentlig nøgle - et par numre , til dekryptering - en privat nøgle . Tal kaldes henholdsvis åbne og lukkede eksponenter, tallet kaldes modulet. Modulus , hvor og er to primtal . Forbindelsen mellem den lukkede, åbne eksponent og modulet er givet som , hvor er Euler-funktionen . $(e,N)$ $(d,N)$ $e,d$ $N$ $N=pq$ $s$ $q$ $ed=1{\bmod {\varphi }}(N)$ $\varphi (N)=(p-1)(q-1)$

Hvis den offentlige nøgle kan gendannes på kort tid , så er nøglen sårbar: Efter at have modtaget information om den private nøgle , har angribere mulighed for at dekryptere beskeden. $(e,N)$ $d$ $(d,N)$

Algoritmens historie

RSA-kryptosystemet blev opfundet af Ronald Rivest , Adi Shamir og Leonard Adleman og først udgivet i 1977 [1] . Siden publiceringen af artiklen er RSA-kryptosystemet blevet undersøgt for sårbarheder af mange forskere. [2] De fleste af disse angreb bruger potentielt farlige implementeringer af algoritmen og bruger eksplicitte betingelser for en eller anden fejl i algoritmen: fælles modul, lille offentlig nøgle, lille privat nøgle [3] . En kryptografisk angrebsalgoritme mod RSA-algoritmen med en lille privat nøgle blev således foreslået af kryptolog Michael J. Wiener i en artikel, der først blev offentliggjort i 1990. [4] Wieners sætning siger, at hvis nøglen er lille, så kan den private nøgle findes i lineær tid .

Lille privat nøgle

I RSA -krypteringssystemet kan Bob bruge en mindre værdi i stedet for et stort tilfældigt tal for at forbedre RSA -dekrypteringsydelsen . Wieners angreb viser dog, at valg af en lille værdi for for vil resultere i en usikker kryptering, hvor en angriber kan gendanne alle de hemmelige oplysninger, altså bryde RSA -systemet . Dette hack er baseret på Wieners sætning, som er gyldig for små værdier på . Wiener beviste, at en angriber effektivt kan finde hvornår . $d$ $d$ $d$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

Wiener indførte også nogle modforanstaltninger mod sit angreb. De to metoder er beskrevet nedenfor: [5]

1. Valg af en stor offentlig nøgle :

Erstat med , hvor for nogle store . Når det er stort nok, dvs. , så er Wieners angreb uanvendeligt, uanset hvor lille .

e

e'

e'=e+k\cdot \varphi (N)

k

e'

e'>N^{\frac {3}{2))

d

2. Brug af den kinesiske restsætning :

Vælg så, at og , og er små, men ikke sig selv, så kan hurtig beskeddekryptering udføres som følger:

d

d_{p}=d{\bmod {(}}p-1)

d_{q}=d{\bmod {(}}q-1)

d

C

Først beregner den $M_{p}=C^{d_{p}}{\bmod {p}}$ $M_{q}=C^{d_{q}}{\bmod {q}}$
Brug af den kinesiske restsætning til at beregne en unik værdi , der opfylder og . Resultatet opfylder efter behov. Pointen er, at Wieners angreb ikke er anvendeligt her, fordi værdien kan være stor. $M\in \mathbb {Z_{N}}$ $M=M_{p}{\bmod {p))$ $M=M_{q}{\bmod {q}}$ $M$ $M=C^{d}{\bmod {N))$ $d{\bmod {\varphi ))(N)$

Sådan fungerer Wiener-angrebet

Fordi

ed=1{\pmod {\operatørnavn {lcm} (p-1,q-1)))))

så er der et heltal , sådan at: $K$

ed=K\times \operatørnavn {lcm} (p-1,q-1)+1

Det er værd at bestemme og erstatte i den foregående ligning : $G=\gcd(p-1,q-1)$

ed={\frac {K}{G}}(p-1)(q-1)+1

Hvis vi betegner og , vil substitution i den foregående ligning give: $k={\frac {K}{\gcd(K,G)))$ $g={\frac {G}{\gcd(K,G)))$

ed={\frac {k}{g}}(p-1)(q-1)+1

Ved at dividere begge sider af ligningen med , viser det sig, at: $dpq$

{\frac {e}{pq}}={\frac {k}{dg}}(1-\delta )

, hvor .

\delta ={\frac {p+q-1-{\frac {g}{k}}}{pq}}

Som et resultat, lidt mindre end , og den første fraktion består udelukkende af offentlig information . Der er dog stadig behov for en metode til at teste en sådan antagelse. Mens den sidste ligning kan skrives som: ${\frac {e}{pq))$ ${\frac {k}{dg))$ $ed>pq$

edg=k(p-1)(q-1)+g

Ved hjælp af simple algebraiske operationer og identiteter kan man fastslå nøjagtigheden af en sådan antagelse. [6]

Wieners sætning

Lad , hvor . Lad . $N=pq$ $q<p<2q$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

At have hvor , kan en kiks komme sig . [7] $\left\langle N,e\right\rangle$ $ed=1{\bmod {\varphi }}(N)$ $d$

Bevis for Wieners sætning

Beviset er baseret på tilnærmelser ved hjælp af fortsatte brøker . [otte]

Siden , så eksisterer for hvilke . Følgelig: $ed=1{\bmod {\varphi }}(N)$ ${\mathit {k))$ $ed-k\varphi (N)=1$

\left\vert {\frac {e}{\varphi (N)))-{\frac {k}{d}}\right\vert ={\frac {1}{d\varphi (N) } }}

Så dette er en tilnærmelse . Selvom kikseren ikke ved det, kan han bruge den til at tilnærme det. Faktisk fordi: ${\frac {k}{d))$ ${\frac {e}{\varphi (N)))$ $\varphi (N)$ $N$

$\varphi (N)=Np-q+1$ og , vi har: og $p+q-1<3{\sqrt {N))$ $\left\vert p+q-1\right\vert <3{\sqrt {N))$ $\left\vert N+1-\varphi (N)-1\right\vert <3{\sqrt {N))$

Ved at bruge i stedet for får vi: $N$ $\varphi (N)$

\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert =\left\vert {\frac {ed-kn}{Nd}}\ højre\vert =\venstre\vert {\frac {ed-k\varphi (N)-kN+k\varphi (N)}{Nd))\right\vert

=\left\vert {\frac {1-k(N-\varphi (N))}{Nd))\right\vert \leq \left\vert {\frac {3k{\sqrt {N} }}{Nd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}d}}={\frac {3k}{ d{\sqrt {N}}}}}

Nu betyder det . Da , betyder , og i sidste ende viser det sig: $k\varphi (N)=ed-1<ed$ $k\varphi (N)<ed$ $e<\varphi (N)$ $k\varphi (N)<ed<\varphi (N)d$

k\varphi (N)<\varphi (N)d

hvor

k<d

Siden og derfor: $k<d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

(1)\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert <{\frac {1}{dN^{\frac {1 }{fire}}}}

Da , da , og baseret på dette , betyder: $d<{\frac {1}{3}}N^{\frac {1}{4)),2d<3d$ $2d<3d<N^{\frac {1}{4))$ $2d<N^{\frac {1}{4))$

(2){\frac {1}{2d}}>{\frac {1}{N^{\frac {1}{4}}}}

Fra (1) og (2) kan vi konkludere, at:

{\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert <{\frac {3k}{d{\sqrt {N}}}} <{\frac {1}{d\cdot 2d}}={\frac {1}{2d^{2))))

Betydningen af sætningen er, at hvis betingelsen ovenfor er opfyldt, så vises blandt konvergenterne for den fortsatte brøkdel af tallet . ${\frac {k}{d))$ ${\frac {e}{N))$

Derfor vil algoritmen med tiden finde sådanne [9] . ${\frac {k}{d))$

Beskrivelse af algoritmen

En offentlig RSA-nøgle tages i betragtning , hvorved det er nødvendigt at bestemme den private eksponent . Hvis det er kendt at , så kan det gøres i henhold til følgende algoritme [10] : $(e,N)$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

1. Udvid fraktionen til en fortsat fraktion .

{\frac {e}{N))

[a_{1},a_{2}...]

2. For en fortsat brøk , find mængden af alle mulige konvergenter .

[a_{1},a_{2}...]

{\frac {k_{n}}{d_{n}}}

3. Udforsk passende fraktion :

{\frac {k_{n}}{d_{n}}}

3.1. Bestem den mulige værdi ved at beregne .

\varphi (N)

{\displaystyle f_{n}={\frac {ed_{n}-1}{k_{n))))

3.2. Efter at have løst ligningen , få et par rødder .

x^{2}-((N-f_{n})+1)x+N=0

(p_{n},q_{n})

4. Hvis lighed er sand for et par rødder , så findes den lukkede eksponent .

(p_{n},q_{n})

{\displaystyle N=p_{n}\cdot q_{n))

{\displaystyle d=d_{n))

Hvis betingelsen ikke er opfyldt, eller det ikke var muligt at finde et par rødder , er det nødvendigt at undersøge den næste passende fraktion , og vende tilbage til trin 3.

(p_{n},q_{n})

{\frac {k_{n+1}}{d_{n+1}}}

Et eksempel på, hvordan algoritmen fungerer

Disse to eksempler [10] viser tydeligt at finde den private eksponent , hvis den offentlige RSA- nøgle er kendt . $d$ $(e,N)$

For en offentlig RSA- nøgle : $(e,N)=(1073780833.1220275921)$

Tabel: finde den lukkede eksponent d

e / N = [0, 1, 7, 3, 31, 5, 2, 12, 1, 28, 13, 2, 1, 2, 3]
n	k n / d n	phi n	p n	q n	p n q n
0	0/1	-	-	-	-
en	1/1	1073780832	-	-	-
2	7/8	1227178094	-	-	-
3	22/25	1220205492	30763	39667	1220275921

Det viser sig at . I dette eksempel kan du se, at lillehedsbetingelsen er opfyldt . $d=25$ $d<{\frac {1}{3}}N^{\frac {1}{4}}\ca. 62.30074...$

For en offentlig RSA- nøgle : $(e,N)=(1779399043.2796304957)$