RSA (kryptosystem)

brug af den kinesiske restalgoritmedit

til effektivitet mange populære kryptobiblioteker (såsom OpenSSL, Java og.net) bruger følgende optimering til dekryptering og signering baseret på den kinesiske restteorem. Følgende værdier er precomputed og gemt som en del af den private nøgle:

Disse værdier gør det muligt for modtageren at beregne eksponentiering m = cd (mod pq) mere effektivt som følger:

Dette er mere effektiv end computing potensopløftning ved kvadrering, selvom to modulære exponentiations er nødt til at blive beregnet., Årsagen er, at disse to modulære eksponentieringer både bruger en mindre eksponent og et mindre modul.

Heltal faktorisering og RSA problemEdit

sikkerheden af RSA kryptosystem er baseret på to matematiske problemer: problemet med factoring store tal og RSA problem. Fuld dekryptering af en RSA-ciphertext menes at være umuligt på den antagelse, at begge disse problemer er hårdt, dvs, ingen effektiv algoritme, der eksisterer for at løse dem., Tilvejebringelse af sikkerhed mod delvis dekryptering kan kræve tilsætning af en sikker polstring ordning.

RSA-problemet defineres som opgaven med at tage ETH roots modulo en sammensat n: Gendannelse af en værdi m sådan, at C me me (mod n), hvor (n, e) er en RSA-offentlig nøgle, og c er en RSA-chiffertekst. I øjeblikket er den mest lovende tilgang til løsning af RSA-problemet at faktorere modulet n. med evnen til at gendanne primære faktorer kan en angriber beregne den hemmelige eksponent d fra en offentlig nøgle (n, E) og derefter dekryptere c ved hjælp af standardproceduren., For at opnå dette, kan en hacker faktorer n i p og q, og beregner lcm(p − 1, q − 1), der giver mulighed for bestemmelse af d fra e. Ingen polynomial-time metode til factoring store heltal på en klassisk computer er endnu ikke blevet fundet, men det er ikke blevet bevist, at det ikke findes. Se heltal faktorisering for en diskussion af dette problem.

Multiple polynomial kvadratisk sigte (MP .s) kan bruges til at faktorere det offentlige modul n.,

den første RSA-512-faktorisering i 1999 brugte hundreder af computere og krævede svarende til 8.400 MIPS-år over en forløbet tid på cirka syv måneder. Senest i 2009, Benjamin Moody kunne faktor en RSA-512 bit nøgle i 73 dage, kun ved brug af offentlige software (GGNFS) og hans stationære computer (en dual-core Athlon64 med en 1,900 MHz cpu). Kun mindre end fem gigabyte disklagring var påkrævet og omkring 2, 5 gigabyte RAM til sigtningsprocessen.,

Rivest, Shamir og Adlema bemærkes, at Miller har vist, at der – under forudsætning af sandheden af den Udvidede Riemann Hypotese – at finde d e n og e er så hårdt, som factoring n i p og q (op til et polynomium tidsforskellen). Men Rivest, Shamir, og Adleman bemærkes, i afsnit i./D af deres papir, at de ikke havde fundet et bevis på, at invertere RSA er så hårdt som factoring.fra 2020 var det største offentligt kendte indregnede RSA-tal 829 bit (250 decimaler, RSA-250). Dens faktorisering, ved en state-of-the-art distribueret implementering, tog cirka 2700 CPU år., I praksis er RSA-nøgler typisk 1024 til 4096 bits lange. I 2003 vurderede RSA Security, at 1024-bit nøgler sandsynligvis ville blive knækbare inden 2010. Fra 2020 vides det ikke, om sådanne nøgler kan knækkes, men minimumsanbefalinger er flyttet til mindst 2048 bit. Det antages generelt, at RSA er sikkert, hvis n er tilstrækkelig stor uden for kvanteberegning.

hvis n er 300 bit eller kortere, kan det tages i betragtning på et par timer på en personlig computer ved hjælp af Soft .are, der allerede er frit tilgængelig., Nøgler over 512 bits har vist sig at være praktisk knuses i 1999, da RSA-155 var taget højde for ved brug af flere hundrede computere, og hvis disse ikke er indregnet i et par uger, ved hjælp af fælles hardware. E .ploits ved hjælp af 512-bit kode-signering certifikater, der kan have været indregnet blev rapporteret i 2011. En teoretisk hard .areenhed ved navn T .irl, beskrevet af Shamir og Tromer i 2003, satte spørgsmålstegn ved sikkerheden for 1024 bit nøgler.,

I 1994, Peter Shor viste, at en kvante-computer – hvis man nogensinde kunne være praktisk oprettet til formålet – ville være i stand til at faktor i polynomiel tid, bryde RSA; se Kort”s algoritme.

defekt nøglegenerationrediger

Finde den store primtal p og q er normalt gøres ved at teste tilfældige tal i den rigtige størrelse med probabilistisk oprindelighed test, der hurtigt kan fjerne stort set alle de nonprimes.

tallene p og q bør ikke være “for tæt”, for at Fermatfaktoriseringen for n skal lykkes., Hvis p − q er mindre end 2n1/4 (n = p * q, som selv for små 1024-bit værdier af n er 3×1077) løsning for p og q er trivielt. Endvidere, hvis enten p-1 eller 1-1 har kun små primære faktorer, n kan indregnes hurtigt ved Pollard ” S P-1 algoritme, og dermed sådanne værdier af p eller q bør kasseres.

det er vigtigt, at den private eksponent d er stor nok. Michael J. Wiener viste, at hvis p er mellem q og 2q (som er ganske typisk) og d < n1/4/3, så d kan beregnes effektivt mod n og e.,

Der er intet kendt angreb mod små offentlige eksponenter som e = 3, forudsat at den korrekte polstring anvendes. Coppersmith ” s angreb har mange applikationer i at angribe RSA specifikt, hvis den offentlige eksponent e er lille, og hvis den krypterede meddelelse er kort og ikke polstret. 65537 er en almindeligt anvendt værdi for e; denne værdi kan betragtes som et kompromis mellem at undgå potentielle små eksponentangreb og stadig tillade effektive krypteringer (eller signaturverifikation)., NIST Specialpublikation om computersikkerhed (SP 800-78 Rev 1 fra August 2007) tillader ikke offentlige eksponenter e mindre end 65537, men angiver ikke en grund til denne begrænsning.

I oktober 2017, et team af forskere fra Masaryk Universitet annoncerede ROCA sårbarhed, som påvirker RSA-nøgler genereret af en algoritme, der kommer til udtryk i et bibliotek fra Infineon kendt som RSALib. Et stort antal chipkort og trusted platform modules (TPMs) blev vist at være påvirket. Sårbare RSA-nøgler er let identificeres ved hjælp af et testprogram holdet udgivet.,

Betydningen af stærke tilfældige tal generationEdit

En stærk kryptografisk random number generator, og som er blevet behørigt podet med passende entropi, skal bruges til at generere primtal p og q. En analyse, der sammenligner millioner af offentlige nøgler, der er indsamlet fra Internettet blev foretaget i begyndelsen af 2012 af Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung og Christophe Wachter. De var i stand til faktor 0.2% af nøglerne ved hjælp af kun Euclid”s algoritme.

de udnyttede en svaghed, der er unik for kryptosystemer baseret på heltalfaktorisering., Hvis n = p.er en offentlig nøgle og n’ = p’.’ er en anden, så hvis tilfældigt p = p’ (men is er ikke lig med”), så en simpel beregning af gcd(n,n’) = p faktorer både n og n’, helt kompromitterende begge nøgler. Lenstra et al. bemærk, at dette problem kan minimeres ved at bruge et stærkt tilfældigt frø med bitlængde dobbelt så meget som det tilsigtede sikkerhedsniveau, eller ved at anvende en deterministisk funktion til at vælge given givet p, i stedet for at vælge P og.uafhængigt.Nadia Heninger var en del af en gruppe, der gjorde et lignende eksperiment. De brugte en ID of om Daniel J., Bernstein til at beregne GCD af hver RSA-nøgle n mod produktet af alle de andre nøgler n’, at de havde fundet (en 729 mio cifret nummer), i stedet for computing hver gcd(n,n’), separat, således at der opnås en meget betydelig hastighedsforøgelse siden efter én stor afdeling, GCD problem er af normal størrelse.

Heninger siger i sin blog, at den dårlige nøgler skete næsten udelukkende i indlejrede applikationer, herunder “firewalls, routere, VPN enheder, remote server administration-enheder, printere, projektorer og VOIP-telefoner” fra mere end 30 producenter., Heninger forklarer, at det one-shared-prime-problem, der er afdækket af de to grupper, skyldes situationer, hvor pseudorandom-nummergeneratoren oprindeligt er dårligt podet, og derefter reseeded mellem generationen af den første og anden primes. Brug af frø med tilstrækkelig høj entropi opnået fra nøgleslag eller elektronisk diodestøj eller atmosfærisk støj fra en radiomodtager, der er indstillet mellem stationer, bør løse problemet.

stærk tilfældig talgenerering er vigtig i alle faser af offentlig nøglekryptografi., For eksempel, hvis en svag generator bruges til de symmetriske nøgler, der distribueres af RSA, kan en aflytter omgå RSA og gætte de symmetriske nøgler direkte.

Timing attacksEdit

Kocher, der er beskrevet et nyt angreb på RSA i 1995: hvis angriberen kender Alice Eve”s hardware i tilstrækkelige detaljer, og er i stand til at måle dekryptering gange flere kendte ciphertexts, Eva kan udlede dekrypteringsnøgle d hurtigt. Dette angreb kan også anvendes mod RSA signatur ordning., I 2003, Boneh og Brumley vist en mere praktisk angreb i stand til at inddrive RSA factorizations over en netværksforbindelse (fx fra en Secure Sockets Layer (SSL)-aktiveret webserver) Dette angreb udnytter oplysninger, der er lækket fra den Kinesiske resten sætning optimering, der anvendes af mange RSA-implementeringer.

En måde at forpurre disse angreb er at sikre, at dekryptering operation tager konstant tid for hver maskine. Denne tilgang kan dog reducere ydeevnen betydeligt., I stedet bruger de fleste RSA-implementeringer en alternativ teknik kendt som kryptografisk blændende. RSA blinding gør brug af RSA ‘ s multiplikative egenskab. I stedet for at beregne cd (mod n) vælger Alice først en hemmelig tilfældig værdi r og beregner (rec)d (mod n). Resultatet af denne beregning, efter anvendelse af Euler”s Sætning, er rcd (mod n), og så effekten af r kan fjernes ved at multiplicere med dens inverse. En ny værdi af r er valgt for hver ciphertekst. Med blinding anvendt, er dekryptering tid ikke længere korreleret til værdien af input cipherte .t, og så timingen angreb mislykkes.,

Adaptive valgt ciphertext attacksEdit

I 1998, Daniel Bleichenbacher, der er beskrevet i den første praktiske adaptive valgt ciphertext angreb mod RSA-krypterede meddelelser, der bruger PKCS #1 v1 padding-ordningen (en polstring ordning tilfældig rækkefølge og tilføjer strukturen af en RSA-krypteret besked, så det er muligt at afgøre, om en dekrypteret besked er gyldig). På grund af fejl med PKCS #1-ordningen var Bleichenbacher i stand til at montere et praktisk angreb mod RSA-implementeringer af Secure Socket Layer-protokollen og gendanne sessionsnøgler., Som et resultat af dette arbejde, kryptografer nu anbefaler brug af provably sikker polstring ordninger som Optimal Asymmetrisk Kryptering Polstring, og RSA-Laboratories har frigivet nye versioner af PKCS #1, der ikke er sårbare over for disse angreb.

sidekanalanalyseangrebredit

et sidekanalangreb ved hjælp af grenforudsigelsesanalyse (BPA) er blevet beskrevet. Mange processorer bruger en grenprediktor til at afgøre, om en betinget gren i instruktionsstrømmen af et program sandsynligvis vil blive taget eller ej. Ofte implementerer disse processorer også samtidig multithreading (SMT)., Grenforudsigelsesanalyseangreb bruger en spionproces til at opdage (statistisk) den private nøgle, når den behandles med disse processorer.

Simple Branch Prediction Analysis (SBPA) hævder at forbedre BPA på en ikke-statistisk måde. I deres artikel “Om Magt Simpel Branch Prediction Analyse”, forfatterne af SBPA (Onur Aciicmez og Cetin Kaya Koc) hævder at have opdaget 508 ud over 512 bits af en RSA-nøgle i 10 gentagelser.

et strømfejlangreb på RSA-implementeringer blev beskrevet i 2010., Forfatteren gendannede nøglen ved at variere CPU-strømspændingen uden for grænserne; dette forårsagede flere strømfejl på serveren.