RSA (nøkkel)

ved Hjelp av den Kinesiske resten algorithmEdit

For effektiviteten mange populære crypto biblioteker (for eksempel OpenSSL, Java og .NETTO) bruk følgende optimalisering for dekryptering og signatur som er basert på det Kinesiske restteoremet. Følgende verdier er precomputed og lagret som en del av den private nøkkelen:

Disse verdiene du vil la mottakeren for å beregne exponentiation m = cd (mod pq) mer effektivt som følger:

Dette er mer effektivt enn computing exponentiation ved å kvadrere selv om to modular exponentiations må beregnes., Grunnen er at disse to modular exponentiations begge bruker en mindre eksponent og en mindre elastisitet.

Heltall primtallsfaktorisering og RSA problemEdit

sikkerheten i RSA-nøkkel er basert på to matematiske problemer: problemet med factoring store tall og RSA problem. Full dekryptering av en RSA ciphertext er tenkt å være umulig på den forutsetning at begge disse problemene er vanskelig, dvs., ingen effektiv algoritme eksisterer for å løse dem., Gi sikkerhet mot delvis dekryptering kan kreve tillegg av en sikker polstring ordningen.

RSA problemet er definert som oppgave å ta eth røtter modulo et sammensatt n: gjenopprette en verdi m slik at c ≡ meg (mod n), hvor (n, e) er en RSA offentlig nøkkel og c er en RSA ciphertext. For tiden de mest lovende tilnærming til å løse RSA-problemet er å faktor modulus n. Med muligheten til å gjenopprette prime faktorer, kan en angriper kan beregne den hemmelige eksponent d fra en offentlig nøkkel (n, e), deretter dekryptere c ved hjelp av standard prosedyre., For å oppnå dette, kan en angriper faktorer n i p og q, og regner ut lcm(s − 1, q − 1) som tillater bestemmelse av d og e. Ingen polynom-tid metode for factoring store heltall på en klassisk datamaskinen er ennå ikke funnet, men det har ikke blitt bevist at det ikke finnes. Se heltall primtallsfaktorisering for en diskusjon av dette problemet.

Flere kvadratiske polynom sil (MPQS) kan brukes til å faktoren offentlig modulus n.,

Den første RSA-512 primtallsfaktorisering i 1999 brukt hundrevis av datamaskiner og krevde tilsvarende 8,400 MIPS år, over en avspillingstid på ca syv måneder. Av 2009, Benjamin Moody kunne faktor en RSA-512 bits nøkkel i 73 dager med kun offentlig programvare (GGNFS) og hans stasjonær datamaskin (en dual-core Athlon64 med en 1900 MHz cpu). Bare mindre enn fem gigabyte disk lagring var nødvendig, og om lag 2,5 gigabyte RAM for sikting prosessen.,

Rivest, Shamir og Adleman bemerket at Miller har vist at – forutsatt sannheten av det Utvidede Riemann-Hypotesen – finne d fra n og e er så vanskelig som factoring n i p og q (opp til en polynomisk tid forskjell). Imidlertid, Rivest, Shamir og Adleman nevnt i kapittel IX/D av sine papir, at de ikke hadde funnet et bevis på at inverterende RSA er så vanskelig som factoring.

Som i 2020, som er den største offentlig kjent priset RSA-tallet var 829 biter (250 desimaler, RSA-250). Dens primtallsfaktorisering, med en state-of-the-art distribuert implementering, tok ca 2700 CPU år., I praksis, RSA-nøkler er vanligvis 1024 4096 bits lang. I 2003, RSA Security anslått at 1024-biters nøkler var sannsynlig å bli crackable av 2010. Som i 2020, det er ikke kjent om slike koder kan knekkes, men minimum anbefalinger har flyttet til minst 2048 bits. Det er generelt antatt at RSA er sikker hvis n er stor nok, utenfor quantum computing.

Hvis n er 300 bits eller kortere, kan det være priset inn i et par timer i en personlig datamaskin, ved hjelp av programvare som allerede er fritt tilgjengelig., Nøkler 512 bits har vist seg å være praktisk talt knuselig i 1999 da RSA-155 var priset ved hjelp av flere hundre datamaskiner, og disse er nå priset inn i et par uker med vanlig maskinvare. Utnytter du bruker 512-bits kode-signering av sertifikater som kan ha blitt priset inn ble rapportert i 2011. En teoretisk maskinvare som heter SNURRE, beskrevet av Shamir og Tromer i 2003, stilt spørsmål ved sikkerheten til 1024 bits nøkler.,

I 1994, Peter Ko viste at en kvante – maskin- hvis man noen gang skal kunne praktisk talt opprettet for formålet, vil være i stand til å faktor i polynomisk tid, bryte RSA, se Ko»s algoritme.

Feil tast generationEdit

Finne den store primtall p og q er vanligvis gjort ved å teste tilfeldige tall av riktig størrelse med probabilistisk primality tester som raskt eliminere nesten alle nonprimes.

tall p og q burde ikke være «for nær», so de Fermat ‘ primtallsfaktorisering for n være vellykket., Hvis p − q er mindre enn 2n1/4 (n = p * q, som selv for små 1024-bits verdier av n er 3×1077) løse for p og q er trivielt. Videre, hvis enten s − 1 eller q − 1 har kun små prime faktorer, n kan være priset raskt av Pollard»s-s − 1-algoritmen, og derfor er slike verdier av p eller q bør bli forkastet.

Det er viktig at de private eksponent d være stort nok. Michael J. Wiener viste at hvis p er mellom q og 2q (som er ganske vanlig) og d < n1/4/3, så d kan bli beregnet effektivt fra n og e.,

Det er ingen kjente angrep mot små offentlig eksponenter for eksempel e = 3, forutsatt at riktig padding er brukt. Coppersmith»s Angrep har mange programmer i å angripe RSA spesielt hvis offentlig eksponent e er liten, og hvis den krypterte meldingen er kort og ikke polstret. 65537 er en vanlig brukt valuta for e; denne verdien kan betraktes som et kompromiss mellom å unngå potensielle liten eksponent angrep og fortsatt tillater effektiv kryptering (eller signatur verifisering)., Den NIST Special Publication på Datamaskinen Sikkerhet (SP 800-78 Rev 1 August 2007) ikke tillater offentlig eksponenter e mindre enn 65537, men ikke staten en grunn for denne begrensningen.

I oktober 2017, et team av forskere fra Masaryk University annonsert ROCA sårbarhet, noe som påvirker RSA-nøkler som genereres av en algoritme er nedfelt i et bibliotek fra Infineon kjent som RSALib. Et stort antall av smarte kort og pålitelige plattform-moduler (TPMs) ble vist å være påvirket. Sårbare RSA-nøkler er lett identifiseres ved hjelp av et test program laget utgitt.,

Viktigheten av sterke tilfeldig nummer generationEdit

En kryptografisk sterk random number generator, som har vært riktig fordelt med tilstrekkelig entropi, må brukes til å generere primtall p og q. En analyse sammenligning av millioner av offentlige nøkler samlet fra Internett ble gjennomført i begynnelsen av 2012 av Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bim, Thorsten Kleinjung og Christophe Wachter. De var i stand til å faktor 0,2% av nøkler ved hjelp av bare Euklids»s algoritme.

De utnyttet en svakhet som er unike for cryptosystems basert på heltall primtallsfaktorisering., Hvis n = pq er en offentlig nøkkel og n’ = p’q’ er en annen, så hvis ved en tilfeldighet p = p’ (men q er ikke lik q’), deretter en enkel beregning av gcd(n,n’) = p faktorer både n-og n’, helt at det går begge tastene. Lenstra et al. merk at dette problemet kan reduseres ved å bruke et sterkt tilfeldig frø av bit-lengde dobbelt hadde til hensikt å sikkerhetsnivå, eller ved å ansette en deterministisk funksjon for å velge q gitt p, i stedet for å velge p og q uavhengig av hverandre.

Nadia Heninger var en del av en gruppe som gjorde et lignende eksperiment. De brukte en idé av Daniel J., Bernstein for å beregne GCD av hver RSA-nøkkel n mot produktet av alle de andre tastene n’ hadde de funnet (a 729 millioner siffer), i stedet for å beregne hvert gcd(n,n’) for seg, og dermed oppnå en meget betydelig fart siden etter å ha ett stort division, GCD problemet er av normal størrelse.

Heninger sier i sin blogg at de dårlige taster skjedde nesten helt i embedded applikasjoner, inkludert «brannmurer, rutere, VPN enheter, remote server administration-enheter, skrivere, projektorer, og VOIP-telefoner» fra mer enn 30 produsenter., Heninger forklarer at en-felles-prime problem som er avdekket av to grupper resultater fra situasjoner der pseudotilfeldig nummer generator er dårlig seedet i utgangspunktet, og da er reseeded mellom den generasjon av den første og andre primtall. Ved hjelp av frø av tilstrekkelig høy entropi innhentet fra sentrale strøk timings eller elektronisk diode støy eller atmosfærisk støy fra en radiomottaker innstilt mellom stasjonene bør løse problemet.

Sterke tilfeldige tall generasjon er viktig gjennom alle faser av offentlig nøkkel kryptografi., For eksempel, hvis en svak generator brukes for symmetriske nøkler som blir distribuert av RSA, og deretter en eavesdropper kunne omgå RSA og gjette symmetriske nøkler direkte.

Timing attacksEdit

Kocher beskrevet et nytt angrep på RSA i 1995: hvis angriperen Eva kjenner Alice»s hardware i tilstrekkelig detalj, og er i stand til å måle dekryptering ganger for flere kjente ciphertexts, Eva kan utlede dekrypteringsnøkkelen d raskt. Dette angrepet kan også bli brukt mot RSA signatur ordningen., I 2003, Boneh og Brumley vist en mer praktisk angrep i stand til å utvinne RSA factorizations via en nettverkstilkobling (for eksempel, fra en Secure Sockets Layer (SSL)-aktivert webserver) Dette angrepet tar nytte av informasjon lekket av det Kinesiske restteoremet optimalisering brukt av mange RSA-implementeringer.

En måte å stoppe disse angrepene er å sikre at dekryptering operasjonen tar en konstant mengde tid for hver ciphertext. Men denne tilnærmingen kan redusere ytelsen., I stedet er de fleste RSA implementeringer bruke en alternativ teknikk kjent som kryptografiske blinding. RSA blinding gjør bruk av multiplicative holderen for RSA. I stedet for å computing cd (mod n), Alice først velger en hemmelig tilfeldig verdi r og regner ut (rec) – d (mod n). Resultatet av denne beregningen, etter bruk av Euler ‘ s Teorem, er rcd (mod n), og så effekten av r kan fjernes ved å multiplisere med sin omvendte. En ny verdien av r er valgt for hver ciphertext. Med blindende anvendt, dekryptering tid er ikke lenger korrelert til verdien av input ciphertext, og så timingen angrepet mislykkes.,

Adaptive valgt ciphertext attacksEdit

I 1998, Daniel Bleichenbacher beskrevet den første praktiske adaptive valgt ciphertext angrepet mot RSA-krypterte meldinger med PKCS #1 v1 padding-ordningen (en padding ordningen randomiserer og gir struktur til en RSA-kryptert melding, slik at det er mulig å avgjøre om en dekrypterte meldingen er gyldig). På grunn av feil med PKCS #1-ordningen, Bleichenbacher var i stand til å montere en praktisk angrepet mot RSA implementeringer av Secure Socket Layer-protokollen, og for å gjenopprette økt tastene., Som et resultat av dette arbeidet, cryptographers nå anbefaler bruk av provably sikre polstring ordninger som Optimal Asymmetrisk Kryptering Polstring, og RSA Laboratorier har gitt ut nye versjoner av PKCS #1 som ikke er utsatt for disse angrepene.

Side-kanal analyse attacksEdit

En side-kanal angrep ved hjelp av grenen prediktiv analyse (BPA) har vært beskrevet. Mange prosessorer bruke en gren prediktor for å avgjøre om en betinget gren i undervisningen flyt av et program som er sannsynlig å bli tatt eller ikke. Ofte er disse prosessorene også gjennomføre samtidige multithreading (SMT)., Branch prediction analyse angrep bruke en spion prosess for å oppdage (statistisk) den private nøkkelen når du behandles med disse prosessorene.

Enkel Gren Prediktiv Analyse (SBPA) krav til å forbedre BPA i en ikke-statistisk måte. I deres avis, «På Strømmen av Enkle Branch Prediction Analyse», forfatterne av SBPA (onur det medisinske Aciicmez og Cetin Kaya Koc) hevder å ha oppdaget 508 ut av 512 biter av en RSA-nøkkel i 10 iterasjoner.

En power fault attack på RSA-implementeringer ble beskrevet i 2010., Forfatteren ble gjenopprettet nøkkel ved varierende CPU-kraft spenning utenfor grensene, og dette forårsaket flere elektriske feil på serveren.