RSA (cryptosystem)

gebruikmakend van de Chinese restalgoritmedit

voor efficiëntie veel populaire cryptobibliotheken (zoals OpenSSL, Java en.net) gebruiken de volgende optimalisatie voor decryptie en ondertekening op basis van de Chinese reststelling. De volgende waarden worden vooraf berekend en opgeslagen als onderdeel van de privésleutel:

deze waarden stellen de ontvanger in staat om de exponentiatie m = cd (mod pq) efficiënter te berekenen als volgt:

Dit is efficiënter dan het berekenen van exponentiatie door squaring, hoewel twee modulaire exponentiaties moeten worden berekend., De reden is dat deze twee modulaire exponentiaties beide een kleinere exponent en een kleinere modulus gebruiken.

Integer factorization and RSA problemEdit

de beveiliging van het RSA-cryptosysteem is gebaseerd op twee wiskundige problemen: het probleem van het factoring van grote getallen en het RSA-probleem. Volledige decryptie van een RSA-versleuteling wordt als ondoenlijk beschouwd in de veronderstelling dat beide problemen moeilijk zijn, d.w.z. dat er geen efficiënt algoritme bestaat om ze op te lossen., Het verstrekken van beveiliging tegen gedeeltelijke decryptie kan de toevoeging van een veilige padding regeling vereisen.

het RSA probleem wordt gedefinieerd als de taak van het nemen van eth roots modulo een samengestelde n: het herstellen van een waarde m zodanig dat c ≡ me (mod n), waar (n, e) is een RSA publieke sleutel en c is een RSA versleuteling. Momenteel is de meest veelbelovende aanpak voor het oplossen van het RSA-probleem om de modulus n te factor. met de mogelijkheid om priemfactoren te herstellen, kan een aanvaller de geheime exponent d berekenen van een publieke sleutel (n, e), dan decoderen c met behulp van de standaardprocedure., Om dit te bereiken, een aanvaller factoren n in p en q, en berekent lcm(p − 1, q − 1) die de bepaling van d uit e. Geen polynoom-tijd methode voor het factoring van grote gehele getallen op een klassieke computer is nog gevonden, maar het is niet bewezen dat er geen bestaat. Zie integer factorization voor een bespreking van dit probleem.

Multiple polynomial quadratic sieve (MPQS) kan worden gebruikt om de openbare modulus n te factor.,

de eerste RSA-512-factorisatie in 1999 maakte gebruik van honderden computers en vereiste het equivalent van 8.400 MIPS-Jaren, over een verstreken tijd van ongeveer zeven maanden. In 2009 kon Benjamin Moody in 73 dagen een RSA-512-bit-sleutel berekenen met alleen publieke software (GGNFS) en zijn desktopcomputer (een dual-core Athlon64 met een 1.900 MHz cpu). Iets minder dan vijf gigabyte aan schijfopslag was nodig en ongeveer 2,5 gigabyte aan RAM voor het zeefproces.,Rivest, Shamir en Adleman merkten op dat Miller heeft aangetoond dat – uitgaande van de waarheid van de uitgebreide Riemann – hypothese-het vinden van d van n en e even moeilijk is als het factoring van n in p en q (tot een veelterm Tijdsverschil). Rivest, Shamir en Adleman merkten echter in sectie IX/D van hun artikel op dat zij geen bewijs hadden gevonden dat het omkeren van RSA zo moeilijk is als factoring.

vanaf 2020 was het grootste publiek bekende gefactoreerde RSA-nummer 829 bits (250 decimale cijfers, RSA-250). De factorisatie, door een state-of-the-art gedistribueerde implementatie, duurde ongeveer 2700 CPU-jaren., In de praktijk zijn RSA-sleutels doorgaans 1024 tot 4096 bits lang. In 2003, RSA Security geschat dat 1024-bit sleutels waren waarschijnlijk crackable in 2010. Met ingang van 2020 is niet bekend of dergelijke sleutels kunnen worden gekraakt, maar minimale aanbevelingen zijn verplaatst naar ten minste 2048 bits. Er wordt algemeen aangenomen dat RSA veilig is als n voldoende groot is, buiten kwantum computing.

als n 300 bits of korter is, kan het binnen enkele uren in een personal computer worden verwerkt met behulp van reeds vrij beschikbare software., Sleutels van 512 bits zijn aangetoond praktisch breekbaar in 1999 toen RSA-155 werd verrekend met behulp van enkele honderden computers,en deze worden nu in een paar weken met behulp van gemeenschappelijke hardware. Exploits met behulp van 512-bit code-signing certificaten die kunnen zijn factored werden gemeld in 2011. Een theoretisch hardware apparaat genaamd TWIRL, beschreven door Shamir en Tromer in 2003, stelde de veiligheid van 1024 bit sleutels in vraag.,

in 1994 toonde Peter Shor aan dat een kwantumcomputer – als men er ooit praktisch voor zou kunnen worden gemaakt – in staat zou zijn om polynomiale tijd te factureren, door RSA te breken; zie Shor ‘ s algoritme.

defecte key generationEdit

het vinden van de grote priemgetallen p en q wordt meestal gedaan door willekeurige getallen van de juiste grootte te testen met probabilistische primaliteitstests die snel vrijwel alle niet-priemgetallen elimineren.

De getallen p en q mogen niet “te dicht” zijn, anders zal de Fermat-factorisatie voor n succesvol zijn., Als p-q kleiner is dan 2n1 / 4 (n = P * q, Wat zelfs voor kleine 1024-bit waarden van n 3×1077 is) is het oplossen van p en q triviaal. Bovendien, als ofwel p − 1 of q − 1 slechts kleine priemfactoren heeft, kan n snel worden gefactoreerd door Pollard ‘ S P − 1 algoritme, en daarom moeten dergelijke waarden van p of q worden weggegooid.

Het is belangrijk dat de particuliere exponent d groot genoeg is. Michael J. Wiener toonde aan dat als p tussen q en 2q ligt (wat vrij typisch is) en d < n1/4/3, dan kan d efficiënt worden berekend uit n en e.,

Er is geen bekende aanval tegen kleine publieke exponenten zoals e = 3, mits de juiste padding wordt gebruikt. Coppersmith ‘ s aanval heeft vele toepassingen in het aanvallen van RSA specifiek als de publieke exponent e is klein en als het versleutelde bericht is kort en niet opgevuld. 65537 is een veelgebruikte waarde voor e; deze waarde kan worden beschouwd als een compromis tussen het vermijden van potentiële kleine exponent aanvallen en nog steeds het toestaan van efficiënte versleuteling (of handtekening verificatie)., De speciale NIST-publicatie over computerbeveiliging (SP 800-78 Rev 1 van augustus 2007) staat geen publieke exponenten e kleiner dan 65537 toe, maar geeft geen reden voor deze beperking.in oktober 2017 kondigde een team van onderzoekers van de Masaryk University de Roca-kwetsbaarheid aan, die RSA-sleutels beïnvloedt die gegenereerd worden door een algoritme dat belichaamd is in een bibliotheek van Infineon die bekend staat als RSALib. Een groot aantal smartcards en trusted platform modules (TPMS) bleek te worden beïnvloed. Kwetsbare RSA-sleutels kunnen gemakkelijk worden geïdentificeerd met behulp van een testprogramma dat het team heeft uitgebracht.,

belang van sterke random number generationEdit

een cryptografisch sterke random number generator, die goed is ingezaaid met adequate entropie, moet worden gebruikt om de priemgetallen p en q te genereren. een analyse van miljoenen publieke sleutels verzameld van het Internet werd begin 2012 uitgevoerd door Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung en Christophe Wachter. Ze waren in staat om een factor 0.2% van de sleutels met behulp van alleen Euclides ‘ algoritme.

ze maakten gebruik van een zwakte die uniek is voor cryptosystemen op basis van integer factorisatie., Als n = pq één publieke sleutel is en n’ = p’ q’ een andere, dan als bij toeval p = p’ (maar q is niet gelijk aan q’), dan een eenvoudige berekening van gcd(n,n’) = p factoren zowel n en n’, totaal compromitterend beide sleutels. Lenstra et al. merk op dat dit probleem kan worden geminimaliseerd door gebruik te maken van een sterke willekeurige zaad van bitlengte tweemaal het beoogde beveiligingsniveau, of door gebruik te maken van een deterministische functie om q gegeven p te kiezen, in plaats van P en q onafhankelijk te kiezen.

Nadia Heninger maakte deel uit van een groep die een soortgelijk experiment uitvoerde. Ze gebruikten een idee van Daniel J., Bernstein om de GCD van elke RSA-sleutel n te berekenen tegen het product van alle andere sleutels n’ die ze hadden gevonden (een 729 miljoen cijferig getal), in plaats van elke GCD(n,n’) afzonderlijk te berekenen, waardoor een zeer significante versnelling wordt bereikt omdat na één grote deling het GCD-probleem van normale grootte is.

Heninger zegt in haar blog dat de slechte sleutels bijna volledig voorkwamen in embedded applicaties, waaronder “firewalls, routers, VPN-apparaten, remote server administration devices, printers, projectors en VOIP phones” van meer dan 30 fabrikanten., Heninger legt uit dat het één-gedeeld-priemprobleem dat door de twee groepen wordt blootgelegd, het gevolg is van situaties waarin de pseudorandomgetalgenerator aanvankelijk slecht wordt gezaaid en vervolgens opnieuw wordt gezaaid tussen de generatie van de eerste en tweede priemgetallen. Het gebruik van zaden met voldoende hoge entropie verkregen uit toetsstreeptijden of elektronische diode ruis of atmosferische ruis van een radio-ontvanger afgestemd tussen stations moet het probleem oplossen.

sterke random number generation is belangrijk in elke fase van public key cryptografie., Bijvoorbeeld, als een zwakke generator wordt gebruikt voor de symmetrische sleutels die worden gedistribueerd door RSA, dan kan een luistervink RSA omzeilen en raden de symmetrische sleutels direct.

Timing attacksEdit

Kocher beschreef een nieuwe aanval op RSA in 1995: als de aanvaller Eve Alice ‘ s hardware voldoende gedetailleerd kent en in staat is om de decryptie tijden te meten voor verschillende bekende cijfers, kan Eve de decryptie sleutel d snel afleiden. Deze aanval kan ook worden toegepast tegen de RSA handtekening schema., In 2003 demonstreerden Boneh en Brumley een meer praktische aanval die RSA-factorisaties kon herstellen via een netwerkverbinding (bijvoorbeeld van een Secure Sockets Layer (SSL)-enabled webserver) deze aanval maakt gebruik van informatie die is gelekt door de optimalisatie van de Chinese reststelling die door veel RSA-implementaties wordt gebruikt.

een manier om deze aanvallen te dwarsbomen is ervoor te zorgen dat de decryptie-operatie een constante hoeveelheid tijd in beslag neemt voor elke versleuteling. Deze aanpak kan echter de prestaties aanzienlijk verminderen., In plaats daarvan gebruiken de meeste RSA-implementaties een alternatieve techniek die bekend staat als cryptografisch verblinden. RSA blinding maakt gebruik van de multiplicatieve eigenschap van RSA. In plaats van CD (mod n) te berekenen, kiest Alice eerst een geheime willekeurige waarde r en berekent (rec)d (mod n). Het resultaat van deze berekening, na toepassing van de Stelling van Euler, is rcd (mod n) en dus kan het effect van r worden verwijderd door te vermenigvuldigen met zijn inverse. Voor elke cijfertekst wordt een nieuwe waarde van r gekozen. Met blinding toegepast, de decryptie tijd is niet langer gecorreleerd aan de waarde van de invoer versleuteling, en dus de timing aanval mislukt.,

adaptief gekozen ciphertext attacksEdit

in 1998 beschreef Daniel Bleichenbacher de eerste praktische adaptief gekozen ciphertext attack, tegen RSA-versleutelde berichten met behulp van het PKCS #1 V1 padding scheme (een padding scheme randomiseert en voegt structuur toe aan een RSA-versleuteld bericht, zodat het mogelijk is om te bepalen of een gedecodeerd bericht geldig is). Als gevolg van gebreken met de PKCS #1 regeling, Bleichenbacher was in staat om een praktische aanval op RSA implementaties van de Secure Socket Layer protocol monteren, en sessiesleutels te herstellen., Als gevolg van dit werk, cryptografen nu raden het gebruik van aantoonbaar veilige padding regelingen zoals optimale asymmetrische encryptie Padding, en RSA Laboratoria heeft nieuwe versies van PKCS #1 die niet kwetsbaar zijn voor deze aanvallen vrijgegeven.

side-channel analysis attacksEdit

een side-channel attack met behulp van branch prediction analysis (BPA) is beschreven. Veel processors gebruiken een branch predictor om te bepalen of een voorwaardelijke branch in de instructie stroom van een programma waarschijnlijk zal worden genomen of niet. Vaak implementeren deze processors ook simultaneous multithreading (SMT)., Branch voorspelling analyse aanvallen gebruiken een spion proces om te ontdekken (statistisch) de private sleutel wanneer verwerkt met deze processors.

Simple Branch Prediction Analysis (Sbpa) beweert BPA op een niet-statistische manier te verbeteren. In hun artikel, “On the Power of Simple Branch Prediction Analysis”, beweren de auteurs van Sbpa (Onur Aciicmez en Cetin Kaya Koc) 508 van de 512 bits van een RSA-sleutel in 10 iteraties te hebben ontdekt.

een stroomstoring aanval op RSA implementaties werd beschreven in 2010., De auteur herstelde de sleutel door de CPU-voedingsspanning buiten de grenzen te variëren; dit veroorzaakte meerdere stroomstoringen op de server.