RSA-krypteringsanalyse

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 26. juni 2016; checks kræver 8 redigeringer .

Denne artikel beskriver betingelserne for at bruge den offentlige RSA -kryptoalgoritme , som forenkler kryptoanalytiske angreb [1] og metoder til at eliminere sådanne forhold.

Introduktion

Fra 2009 anses et RSA-baseret krypteringssystem for at være sikkert startende ved 1024 bit. $n$

En gruppe videnskabsmænd fra Schweiz, Japan, Frankrig, Holland, Tyskland og USA har med succes beregnet data krypteret ved hjælp af en 768-bit RSA kryptografisk nøgle. [2] Ifølge forskerne er det efter deres arbejde kun RSA-nøgler med en længde på 1024 bit eller mere, der kan betragtes som et pålideligt krypteringssystem. Desuden bør kryptering med en nøgle på 1024 bit opgives i løbet af de næste tre til fire år. [3]

Som det følger af beskrivelsen af arbejdet, blev beregningen af nøgleværdier udført ved den generelle talfeltsigtemetode .

Det første trin (valg af et par polynomier af grad 6 og 1) tog omkring et halvt års beregninger på 80 processorer, hvilket var omkring 3 % af tiden brugt på hovedstadiet af algoritmen (sigtning), som blev udført på hundredvis af computere i næsten to år. Hvis vi interpolerer denne gang for driften af en AMD Opteron 2,2 GHz-processor med 2 GB hukommelse, så ville det være omkring 1500 år. Behandling af data efter sigtning til det næste ressourcekrævende trin (lineær algebra) tog flere uger på et lille antal processorer. Det sidste trin efter at have fundet ikke-trivielle OSLU-løsninger tog ikke mere end 12 timer.

OSLU-løsningen blev udført ved hjælp af Wiedemann-metoden på flere separate klynger og varede lidt mindre end 4 måneder. Samtidig var størrelsen af den sparsomme matrix 192.796.550x192.795.550 med 27.795.115.920 ikke-nul-elementer (det vil sige et gennemsnit på 144 ikke-nul-elementer pr. række). Det tog omkring 105 gigabyte at gemme matrixen på harddisken. Samtidig tog det omkring 5 terabyte komprimerede data at bygge denne matrix.

Som et resultat var gruppen i stand til at beregne en 232-cifret nøgle, der åbner adgang til krypterede data.

Forskere er overbeviste om, at det vil være muligt at knække en 1024-bit RSA-nøgle ved at bruge deres faktoriseringsmetode inden for det næste årti.[ hvornår? ] .

Ved at kende udvidelsen af modulet til produktet af to primtal, kan modstanderen nemt finde den hemmelige eksponent og dermed bryde RSA. Men til dato er den hurtigste faktoriseringsalgoritme General Number Field Sieve, hvis hastighed for et k-bit heltal er $n$ $d$

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

tillader ikke nedbrydning af et stort heltal inden for rimelig tid. Vi vil overveje mulige angreb på RSA, der giver os mulighed for at bryde dette system uden at bruge en direkte udvidelse af modulet n til produktet af to primtal.

Elementære angreb

Lad os overveje flere angreb relateret til misbrug af RSA-algoritmen.

Generering af primtal

Følgende yderligere begrænsning er pålagt tilfældige primtal : $s$ $q$

$s$ og bør ikke være for tæt på hinanden, ellers vil det være muligt at finde dem ved hjælp af Fermats faktoriseringsmetode . Men hvis begge primtal blev genereret uafhængigt, så er denne begrænsning automatisk opfyldt med en enorm sandsynlighed. $q$ $s$ $q$

Skema med fælles modul n

Indledende data: For at undgå at generere forskellige moduler for hver bruger, bruger den sikre server et enkelt n til at kryptere alle meddelelser. Part bruger denne server til at modtage beskeden $n=p*q$ $EN$ $M$

Opgave: modstanderen ønsker at dekryptere partiets budskab . $EN$

Det ser ud til, at en chiffertekst sendt til en part ikke kan dekrypteres af parten, medmindre den har den hemmelige nøgle . Partiet kan dog bruge sine eksponenter til at nedbryde modulet , og derefter, vel vidende , beregne den hemmelige eksponent . $C=M^{e_{a}}\mod n$ $EN$ $B$ $d_{a}$ $B$ ${\displaystyle e_{b},d_{b))$ $n$ $e_{a}$ $d_{a}$

Beskyttelse: hver bruger skal bruge deres eget modul . $n$

Angreb på RSA-signaturen i notarordningen

Indledende data: - notarens offentlige nøgle. Modstanderen modtager et afslag, når han forsøger at underskrive en meddelelse fra en notar $(n, e)$ $M\in \mathbb {Z} _{n}$

Opgave: modstanderen ønsker at få notarens underskrift på beskeden . $M\in \mathbb {Z} _{n}$

Modstanderen vælger en vilkårlig , beregner og sender denne besked til notaren til underskrift. $r\in \mathbb {Z} _{n}$ $M'=r^{e}M\mod n$

Hvis notaren underskriver denne meddelelse:

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

derefter modtager modstanderen, efter at have beregnet , beskedsignaturen . $S=S'/r\mod n$ $M$

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

Beskyttelse: Når du underskriver, skal du tilføje et tilfældigt tal (f.eks. tid) til beskeden.

Små værdier af den hemmelige eksponent

Indledende data: For at øge dekrypteringshastigheden (eller oprettelse af en digital signatur) er antallet af bits, der ikke er nul, af den binære repræsentation af den hemmelige eksponent blevet reduceret (se hastigheden af RSA-algoritmen ). $d$

Opgave: Beregn den hemmelige eksponent . $d$

I 1990 viste Michael J. Wiener, at i tilfælde af en lille værdi , er det muligt at bryde RSA-systemet, nemlig: $d$

Wieners sætning:

Lad , hvor Så, hvis det vides hvor ,

n=pq

q<p<2q

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

(n, e)

ed=1\mod \varphi (n)

så er der en effektiv måde at beregne på .

d

Beskyttelse: Hvis det er 1024 bit i størrelse, skal det være mindst 256 bit langt. $n$ $d$

Små værdier af den åbne eksponent

For at øge hastigheden på kryptering og verifikation af digitale signaturer skal du bruge små værdier af den åbne eksponent . Den mindste af dem . For at øge den kryptografiske styrke af RSA-algoritmen anbefales det dog at bruge $e$ $e=3$

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

Angreb af Khastad

Indledende betingelser: Part sender en krypteret besked til brugere . Hver bruger har sin egen offentlige nøgle og . Parten krypterer beskeden ved hjælp af hver brugers offentlige nøgle på skift og sender den til den relevante modtager. Modstanderen lytter til transmissionskanalen og indsamler de transmitterede chiffertekster. $B$ $M$ ${\displaystyle P_{1},P_{2},...P_{k))$ $(n_{i},e_{i})$ $M<n_{i},\forall i$ $B$ $k$

Opgave: modstanderen ønsker at gendanne beskeden . $M$

Lad , så kan modstanderen komme sig hvis . $e_{i}=3,\forall i$ $M$ $k \geqslant 3$

Bevis

Faktisk, hvis modstanderen modtog , hvor ${\displaystyle C_{1},C_{2},C_{3))$

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

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

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

Vi antager, at de er coprime, ellers ville den største fælles divisor bortset fra én betyde at finde en divisor af en af . Ved at anvende den kinesiske restsætning på , får vi , ${\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))

Siden da _ $M<n_{i},\forall i$ $M^{3}<n_{1}n_{2}n_{3},\forall i$

C'=M^{3}

Det vil sige, at modstanderen kan gendanne beskeden ved at beregne terningsroden af . $M$ $C'$

Generelt, hvis alle åbne eksponenter er ens , kan modstanderen komme sig ved . $e$ $M$ $k\geqslant e$

Overvej det enkleste forsvar mod dette angreb. Lad meddelelsen for hver bruger være en fast permutation af den oprindelige meddelelse $M_{i}$ $M$

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

— besked til i-te bruger.

Hastad (Johan Hastad) viste, at selv i dette tilfælde kan modstanderen gendanne beskeden med et tilstrækkeligt antal brugere. $M$

Beskyttelse: Dette angreb er kun muligt med en lille værdi af den åbne eksponent , i hvilket tilfælde den kryptografiske styrke af RSA-systemet kan opnås ved hjælp af en vilkårlig permutation, og ikke en fast, som eksemplet er givet ovenfor. $e$

Franklin-Reiter angreb

Oprindelige forhold :

Der er to beskeder , og ${\displaystyle M_{1},M_{2}\in \mathbb {Z} _{n))$

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

hvor er et åbent polynomium.

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

Parten med den offentlige nøgle modtager disse beskeder fra parten , som blot krypterer beskederne og transmitterer de modtagne chiffertekster . $EN$ $(n, e)$ $B$ $M_{1},M_{2}$ ${\displaystyle C_{1},C_{2))$

Opgave: Fjenden, vel vidende , ønsker at genoprette . $(n,e,C_{1},C_{2},f)$ $M_{1},M_{2}$

Matthew K. Franklin og Michael K. Reiter beviste følgende udsagn:

Lade 1) er den offentlige nøgle til RSA-systemet, og 2) og ,

(n, e)

e=3

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

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

for nogle lineære polynomium , Så, vel vidende , kan modstanderen komme sig

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

b\neq 0

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

M_{1},M_{2}

Bevis

Faktisk, for en vilkårlig : $e$

$C_{1}={M^{e}}_{1}\mod n~~~~\rightarrow ~~~~M_{2}$ , er roden af polynomiet

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

men er også en rod af polynomiet $M_{2}$

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

Således deler begge polynomier. Og modstanderen kan bruge Euclid-algoritmen til at beregne GCD . Hvis resultatet viser sig at være et lineært polynomium, vil det blive fundet. $(x-M_{2})$ $(g_{1},g_{2})$ $M_{2}$

Når , gcd er et lineært polynomium, og derfor kan modstanderen effektivt beregne meddelelser . $e=3$ $(g_{1},g_{2})$ $M_{1},M_{2}$

Beskyttelse: når tiden til at knække RSA-systemet er proportional med , så dette angreb kan kun bruges med små værdier af den åbne eksponent. $e>3$ $e^{2}$

Angreb på en delvis kendt hemmelig eksponent

Oprindelige forhold :

Modstanderen kender en del af den binære repræsentation af den hemmelige eksponent . $d$

Opgave: Gendan . $d$

Det viser sig at:

Lad være den hemmelige nøgle til RSA-systemet, hvor er størrelsen af bits.

(n,d)

n=pq

\eta

Så ved at kende de mindst signifikante bits af tallet , kan modstanderen komme sig på en tid proportional med

\eta /4

d

d

e\log _{2}e

Muligheden for at knække RSA-systemet i tilfælde af, at den åbne eksponent er lille, er også indlysende ud fra følgende ræsonnement: $e$

fra definitionen og :

e

d

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

Siden er det indlysende .

d<\varphi (n)

0<k\leqslant e

Givet en given værdi , kan modstanderen nemt beregne

k

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

Så kl

q<p<2q

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

Det er således en god tilnærmelse til .

{\hat {d))

d

Da kun distinkte værdier er mulige , kan modstanderen konstruere en række, der indeholder termer, for hvilke den binære repræsentation af et af dets elementer er den samme som den høje halvdel af den hemmelige eksponents binære repræsentation .

e

k

e

d

Beskyttelse: åben eksponentforøgelse . $e$

Angreb med en kvantecomputer

Ved hjælp af en kvantecomputer , hvis den bygges, vil det være muligt at knække RSA, da Shors kvantealgoritme tillader faktorisering af store tal på ret kort tid. Ved at dekomponere modulet n i primfaktorer (dette kan gøres i tid ved hjælp af O (log n ) logiske Q-bits ), kan den hemmelige eksponent d beregnes. ${\tekststil {O(\log ^{2}n\log ^{3}(\log n)))))$

Angreb relateret til implementeringen af RSA-systemet

Runtime angreb

Indledende betingelser:

Overvej et smartkort, hvis mikroprocessor signerer beskeder ved hjælp af en indlejret RSA privat nøgle.

Mål: Fjenden ønsker at få en hemmelig eksponent . $d$

Paul Kocher foreslog et angreb baseret på højpræcisionsmålinger af den tid, det tager smartkortkoderen at udføre visse operationer. Lad os overveje dette angreb på eksemplet med RSA-systemet ved hjælp af den hurtige eksponentieringsalgoritme :

Modstanderen opnår smart card-signaturer for et stort antal tilfældige beskeder og måler den tid, det tager at generere deres signaturer . ${\displaystyle M_{1},M_{2},\dots ,M_{k}\in \mathbb {Z} _{n))$ $T_{i}$

Under angrebet gendannes værdien af den hemmelige eksponent bit for bit, startende fra den mindst signifikante bit: $d$

$d$ mærkeligt, derfor . $d_{0}=1$
hvis så chipkortets mikroprocessor skal udføre tre modulo multiplikationer , i modsætning til de to nødvendige når (se hurtig eksponentieringsalgoritme ). Lad os angive processorberegningstiden for meddelelsen . $d_{1}=1$ $n$ $d_{1}=0$ $t_{i}$ $M_{i}$

Kocher viste, at når to ensembler og korrelerer . Dog i tilfælde af at de er uafhængige. Ved at ty til korrelationsanalyse kan modstanderen således bestemme .

d_{1}=1

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

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

d_{1}=0

d_{1}

kan defineres på samme måde . $d_{2},d_{3},\dots$

Bemærk, at i tilfælde af en lille åben eksponent , kan et angreb på en delvis åben hemmelig eksponent anvendes . I dette tilfælde er det tilstrækkeligt at genvinde halvdelen af bits af den hemmelige eksponent . $e$ $d$

Sikkerhed: Der skal tilføjes en passende forsinkelse, så hvert trin i den hurtige eksponentieringsalgoritme tager en fast tidsperiode.

RSA-hardwareimplementeringsfejl angreb

Indledende betingelser:

Overvej et smartkort, hvis mikroprocessor signerer beskeder ved hjælp af en indlejret RSA privat nøgle. Kortets mikroprocessor bruger Chinese Remainder Theorem til at fremskynde underskriftsprocessen. Modstanderen forsøger at forårsage en funktionsfejl i mikroprocessorens beregninger.

Opgave: modstanderen ønsker at beregne modulo . $n$

Brugen af den kinesiske restsætning øger hastigheden for at skabe en digital signatur.

Faktisk ved at beregne

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

, hvor

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

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

, hvor

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

du kan få en underskrift

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

, hvor

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

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

Det er klart, at beregninger er meget hurtigere end eksponentieringsmodulo .

(a),(b)

n

Lad fjendens handlinger forårsage en fiasko, hvilket resulterer i en defekt i en bit af signaturen. Så er mindst én af eller beregnet forkert. Antag, at defekten er indeholdt i . $\sigma _{p}$ ${\displaystyle \sigma _{q))$ ${\displaystyle {\hat {\sigma _{q))))$

I dette tilfælde

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

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

men

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

Således kan modstanderen finde nedbrydningen som et resultat af GCD-søgningen . $n$ $(n,{\hat {\sigma _{e))}-m)$

Beskyttelse:

Når du underskriver, skal du tilføje et tilfældigt tal til beskeden (f.eks. tid).
tjek signaturen før du sender den.

Sårbarhed i AMD-processorer

I 2021 brugte et team af forskere, herunder Graz University of Technology, Georgia Institute of Technology og Lamarr Security Research, et non-profit forskningscenter, SMT [4] sårbarheden i AMD - processorer med Zen , Zen 2 og Zen 3 arkitekturer til at " knække" krypteringsnøglen RSA -4096 [5] [6] .

Noter

↑ Yang S. Y. Krypteringsanalyse af RSA. - M.-Izhevsk: Forskningscenter "Regular and Chaotic Dynamics", Izhevsk Institute of Computer Research, 2011. - 312 s.
↑ RSA-768 faktoriseringsmeddelelse Arkiveret 13. april 2014 på Wayback Machine
↑ RSA-768 faktorisering Arkiveret 13. december 2012 på Wayback Machine
↑ SQUIP: Udnyttelse af planlægningskøens sidekanal PDF
↑ Anton Shilov. Ny sårbarhed påvirker alle AMD Zen CPU'er: Threading skal muligvis deaktiveres . Toms hardware (11. august 2022). Hentet: 12. august 2022.
↑ Vladimir Fetisov. Det viste sig, at SMT-teknologi i Ryzen- og EPYC-processorer giver dig mulighed for at stjæle fortrolige data . 3DNews (11. august 2022). Hentet: 12. august 2022. (Russisk)

RSA-krypteringsanalyse

Introduktion

Elementære angreb

Generering af primtal

Angreb på RSA-signaturen i notarordningen

Små værdier af den hemmelige eksponent

Små værdier af den åbne eksponent

Angreb af Khastad

Franklin-Reiter angreb

Angreb på en delvis kendt hemmelig eksponent

Angreb med en kvantecomputer

Angreb relateret til implementeringen af ​​RSA-systemet

Runtime angreb

RSA-hardwareimplementeringsfejl angreb

Sårbarhed i AMD-processorer

Noter

Angreb relateret til implementeringen af RSA-systemet