RSA (cryptosystem) (Svenska)

använda den kinesiska återstoden algoritmedit

för effektivitet använder många populära krypto-bibliotek (som OpenSSL, Java och.Net) följande optimering för dekryptering och signering baserat på den kinesiska återstoden teorem. Följande värden är förkomputerade och lagras som en del av den privata nyckeln:

dessa värden gör det möjligt för mottagaren att beräkna exponentiationen m = cd (mod PQ) mer effektivt enligt följande:

detta är effektivare än att beräkna exponentiering genom kvadrering även om två modulära exponentiationer måste beräknas., Anledningen är att dessa två modulära exponentiationer både använder en mindre exponent och en mindre modul.

heltal faktorisering och RSA problemEdit

säkerheten för RSA cryptosystem bygger på två matematiska problem: problemet med factoring stort antal och RSA problemet. Full dekryptering av en RSA-ciphertext anses vara ofelbar med antagandet att båda dessa problem är svåra, dvs det finns ingen effektiv algoritm för att lösa dem., Att tillhandahålla säkerhet mot partiell dekryptering kan kräva tillägg av ett säkert stoppningssystem.

RSA-problemet definieras som uppgiften att ta ETH roots modulo a composite n: återvinna ett värde m som c me (mod n), där (n, e) är en RSA public key och c är en RSA ciphertext. För närvarande är det mest lovande sättet att lösa RSA-problemet att faktor modulen n.med förmågan att återställa primära faktorer kan en angripare beräkna den hemliga exponenten d från en offentlig nyckel (n, e) och dekryptera sedan C med standardproceduren., För att uppnå detta, en angripare faktorer n i p och q, och beräknar lcm (p-1, q-1) som gör det möjligt att bestämma d Från e. ingen polynomialtid metod för factoring stora heltal på en klassisk dator har ännu hittats, men det har inte bevisats att ingen existerar. Se heltal faktorisering för en diskussion om detta problem.

flera polynomiala kvadratiska sikt (MPQS) kan användas för att faktor den offentliga modulen n.,

den första RSA-512-faktoriseringen 1999 använde hundratals datorer och krävde motsvarande 8 400 MIPS-år, under en förfluten tid på cirka sju månader. Senast 2009, Benjamin Moody ’ kunde faktor ett RSA-512-bitars nyckel i 73 dagar med endast offentliga programvara (GGNFS) och hans stationära dator (en dual-core Athlon64 med en på 1 900 MHz cpu). Bara mindre än fem gigabyte disklagring krävdes och cirka 2,5 gigabyte RAM för siktprocessen.,

Rivest, Shamir och Adleman noterade att Miller har visat att – om man antar sanningen om den utökade Riemannhypotesen – är det lika svårt att hitta d från n och e som factoring n i p och q (upp till en polynom tidsskillnad). Rivest, Shamir och Adleman noterade dock i avsnitt IX/D i deras papper att de inte hade hittat ett bevis på att invertering av RSA är lika svår som factoring.

från och med 2020 var det största allmänt kända faktorerade RSA-numret 829 bitar (250 decimaler, RSA-250). Dess faktorisering, genom en toppmodern distribuerad implementering, tog cirka 2700 CPU-år., I praktiken är RSA-nycklar typiskt 1024 till 4096 bitar långa. År 2003 uppskattade RSA Security att 1024-bitars nycklar sannolikt skulle bli crackbara 2010. Från och med 2020 är det inte känt om sådana nycklar kan knäckas, men minsta rekommendationer har flyttats till minst 2048 bitar. Det antas allmänt att RSA är säkert om n är tillräckligt stor, utanför kvantberäkningen.

om n är 300 bitar eller kortare, det kan vägas i ett par timmar i en persondator, med hjälp av programvara redan fritt tillgängliga., Nycklar på 512 bitar har visat sig vara praktiskt taget brytbara 1999 när RSA-155 var factored genom att använda flera hundra datorer, och dessa är nu factored om några veckor med hjälp av vanlig hårdvara. Exploits använder 512-bitars kod signering certifikat som kan ha räknats rapporterades i 2011. En teoretisk maskinvaruenhet som heter TWIRL, beskriven av Shamir och Tromer 2003, ifrågasatte säkerheten för 1024 bitnycklar.,

i 1994 visade Peter Shor att en kvantdator-om man någonsin kunde skapas praktiskt för ändamålet – skulle kunna faktor i polynomialtid, bryta RSA; se Shor ” s algoritm.

felaktig nyckelgenerationedit

att Hitta stora primtal p och q är vanligtvis görs genom att testa random nummer av rätt storlek med probabilistisk primality tester som snabbt eliminerar praktiskt taget alla nonprimes.

siffrorna p och q bör inte vara ”för nära”, så att Fermat factorization för n lyckas., Om P-q är mindre än 2n1/4 (n = P * q, som även för små 1024-bitarsvärden av n är 3×1077) är lösningen för p och q trivial. Dessutom, om antingen p − 1 eller q − 1 har endast små primära faktorer, n kan vägas snabbt av Pollard”s p − 1 algoritm, och därmed sådana värden av p eller q bör kasseras.

det är viktigt att den privata exponenten d är tillräckligt stor. Michael J. Wiener visade att om p är mellan q och 2q (vilket är ganska typiskt) och d < n1/4/3, då d kan beräknas på ett effektivt från n och e.,

det finns ingen känd attack mot små offentliga exponenter som e = 3, förutsatt att korrekt stoppning används. Coppersmith ” s Attack har många applikationer i att attackera RSA specifikt om den offentliga exponenten e är liten och om det krypterade meddelandet är kort och inte vadderat. 65537 är ett vanligt använt värde för e; detta värde kan betraktas som en kompromiss mellan att undvika potentiella små exponentattacker och fortfarande tillåta effektiva krypteringar (eller signaturverifiering)., NIST: s särskilda publikation om datasäkerhet (SP 800-78 Rev 1 från augusti 2007) tillåter inte offentliga exponenter e mindre än 65537, men anger ingen anledning till denna begränsning.

i oktober 2017 meddelade ett team av forskare från Masaryk University Roca-sårbarheten, vilket påverkar RSA-nycklar som genereras av en algoritm som är belägen i ett bibliotek från Infineon som kallas rsalib. Ett stort antal smartkort och trusted platform modules (TPMs) visades påverkas. Sårbara RSA-nycklar identifieras enkelt med hjälp av ett testprogram som laget släppte.,

Betydelsen av starka slumpmässiga nummer generationEdit

En kryptografiskt stark slumptalsgenerator som har blivit ordentligt sås med tillräcklig entropi, måste användas för att generera primtal p och q. En analys jämför miljontals offentliga nycklar som samlats in från Internet genomfördes i början av 2012 av Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bim, Thorsten Kleinjung och Christophe Wachter. De kunde faktor 0,2% av nycklarna med endast Euclid ” s algoritm.

de utnyttjade en svaghet som är unik för cryptosystems baserat på heltalsfaktorisering., Om n = pq är en offentlig nyckel och n’ = p’ q ’ är en annan, då om av en slump p= p ’( men q är inte lika med q’), då en enkel beräkning av gcd(n, n’) = p faktorer både n och n’, helt äventyra båda tangenterna. Lenstra et al. Observera att detta problem kan minimeras genom att använda ett starkt slumpmässigt frö av bitlängd två gånger den avsedda säkerhetsnivån, eller genom att använda en deterministisk funktion för att välja q given p, istället för att välja p och q självständigt.

Nadia Heninger var en del av en grupp som gjorde ett liknande experiment. De använde en idé om Daniel J., Bernstein för att beräkna GCD för varje RSA-nyckel n mot produkten av alla andra nycklar n ’de hade hittat(ett 729 miljoner siffrigt nummer), istället för att beräkna varje GCD (n,n’) separat, och därigenom uppnå en mycket signifikant speedup eftersom efter en stor division är GCD-problemet av normal storlek.

Heninger säger i sin blogg att de dåliga nycklarna inträffade nästan helt i inbäddade applikationer ,inklusive ”brandväggar, routrar, VPN-enheter, fjärradministrationsenheter, skrivare, projektorer och VOIP-telefoner” från mer än 30 tillverkare., Heninger förklarar att det one-shared-prime-problemet som avslöjas av de två grupperna beror på situationer där pseudorandom-nummergeneratorn är dåligt seedad i början och sedan återställs mellan generationen av första och andra primerna. Att använda frön av tillräckligt hög entropi som erhållits från nyckelslagstider eller elektroniskt diodbrus eller Atmosfäriskt brus från en radiomottagare som är inställd mellan stationer bör lösa problemet.

stark slumptalsgenerering är viktig under varje fas av kryptering av offentliga nyckel., Till exempel, om en svag generator används för de symmetriska tangenterna som distribueras av RSA, kan en avlyssnare kringgå RSA och gissa de symmetriska tangenterna direkt.

Timing attacksEdit

Kocher beskrev en ny attack på RSA 1995: om angriparen Eve känner Alice”s hårdvara i tillräcklig detalj och kan mäta dekryptering gånger för flera kända chiffertexts, Eve kan härleda dekrypteringsnyckeln D snabbt. Denna attack kan också tillämpas mot RSA-signaturschemat., I 2003 demonstrerade Boneh och Brumley en mer praktisk attack som kunde återställa RSA-faktoriseringar över en nätverksanslutning (t.ex. från en SSL-aktiverad webbserver (Secure Sockets Layer)). denna attack utnyttjar information som läckt ut av den kinesiska återstående teoremoptimeringen som används av många RSA-implementeringar.

ett sätt att omintetgöra dessa attacker är att säkerställa att dekrypteringsoperationen tar en konstant tid för varje ciphertext. Detta tillvägagångssätt kan dock avsevärt minska prestanda., I stället använder de flesta RSA-implementeringar en alternativ teknik som kallas kryptografisk bländande. RSA bländande använder sig av den multiplikativa egenskapen hos RSA. Istället för att beräkna cd (mod n) väljer Alice först ett hemligt slumpmässigt värde r och beräknar (rec)d (mod n). Resultatet av denna beräkning, efter applicering av Euler ” s teorem, är rcd (mod n) och så kan effekten av r avlägsnas genom att multiplicera med dess inversa. Ett nytt värde på r väljs för varje ciphertext. Med bländande applicerad är dekrypteringstiden inte längre korrelerad till värdet av ingångskryptexten, och så misslyckas tidsattacken.,

Adaptiv valt chiffertext attacksEdit

I 1998, Daniel Bleichenbacher beskrivs den första praktiska adaptive valt chiffertext attack mot RSA-krypterade meddelanden med hjälp av PKCS #1 v1 padding system (en utfyllnad ordningen slumpmässig och ger struktur till ett RSA-krypterat meddelande, så det är möjligt att avgöra om en dekrypterade meddelandet är giltigt). På grund av brister med PKCS #1-systemet kunde Bleichenbacher montera en praktisk attack mot RSA-implementeringar av Secure Socket Layer-protokollet och återställa sessionsnycklar., Som ett resultat av detta arbete rekommenderar kryptografer nu användningen av bevisligen säkra stoppning system som Optimal asymmetrisk kryptering stoppning, och RSA Laboratories har släppt nya versioner av PKCS #1 som inte är sårbara för dessa attacker.

sidokanalsanalysattacksedit

en sidokanalsattack med hjälp av branch prediction analysis (BPA) har beskrivits. Många processorer använder en grensprediktor för att avgöra om en villkorlig gren i instruktionsflödet av ett program sannolikt kommer att tas eller inte. Ofta implementerar dessa processorer också samtidig multithreading (SMT)., Branch prediction analysis attacks använd en spionprocess för att upptäcka (statistiskt) den privata nyckeln när den bearbetas med dessa processorer.

simple Branch Prediction Analysis (SBPA) hävdar att BPA förbättras på ett icke-statistiskt sätt. I sin uppsats, ”På Kraften i en Enkel hoppgissning Analys”, författarna av SBPA (Onur Aciicmez och Cetin Kaya Koc) hävdar att de har upptäckt 508 ut 512 bitar av en RSA-nyckel på 10 iterationer.

en power fault attack på RSA-implementeringar beskrevs 2010., Författaren återhämtade nyckeln genom att variera CPU-strömspänningen utanför gränserna; detta orsakade flera strömavbrott på servern.