RSA (Cryptosystem) (Deutsch)

Verwendung des chinesischen Restalgorithmus

Für die Effizienz Viele gängige Kryptobibliotheken (wie OpenSSL, Java und.NET) verwenden die folgende Optimierung für die Entschlüsselung und Signierung basierend auf dem chinesischen Restsatz. Die folgenden Werte werden vorberechnet und als Teil des privaten Schlüssels gespeichert:

Mit diesen Werten kann der Empfänger die Exponentiation m = cd (mod pq) wie folgt effizienter berechnen:

Dies ist effizienter als die Berechnung der Exponentiation durch Quadrieren, obwohl zwei modulare Exponentiationen berechnet werden müssen., Der Grund dafür ist, dass diese beiden modularen Exponentiationen sowohl einen kleineren Exponenten als auch einen kleineren Modul verwenden.

Integer-Faktorisierung und RSA problemEdit

Die Sicherheit des RSA-Verfahren basiert auf zwei mathematische Probleme: das problem der factoring-große zahlen und das RSA-problem. Es wird angenommen, dass die vollständige Entschlüsselung eines RSA-Chiffretextes unter der Annahme, dass beide Probleme schwer sind, nicht durchführbar ist, dh es gibt keinen effizienten Algorithmus, um sie zu lösen., Die Bereitstellung von Sicherheit gegen teilweise Entschlüsselung kann die Hinzufügung eines sicheren Polsterschemas erfordern.

Das RSA-Problem ist definiert als die Aufgabe, eth-Wurzeln modulo a composite n zu nehmen: Wiederherstellen eines Werts m, so dass c me me (mod n), wobei (n, e) ein öffentlicher RSA-Schlüssel und c ein RSA-Chiffretext ist. Derzeit besteht der vielversprechendste Ansatz zur Lösung des RSA-Problems darin, den Modul n zu berücksichtigen. Mit der Fähigkeit, Primfaktoren wiederherzustellen, kann ein Angreifer den geheimen Exponenten d aus einem öffentlichen Schlüssel (n, e) berechnen und dann c mit dem Standardverfahren entschlüsseln., Um dies zu erreichen, Ein Angreifer Faktoren n in p und q, und berechnet lcm(p − 1, q − 1) das ermöglicht die Bestimmung von d von e. Es wurde noch keine Polynomzeitmethode zum Faktorisieren großer Ganzzahlen auf einem klassischen Computer gefunden, aber es wurde nicht nachgewiesen, dass keine existiert. Siehe integer factorization für eine Diskussion dieses Problems.

Multiples polynomiales quadratisches Sieb (MPQS)kann verwendet werden, um den öffentlichen Modul n zu berücksichtigen.,

Die erste RSA-512-Faktorisierung im Jahr 1999 verwendete Hunderte von Computern und erforderte das Äquivalent von 8.400 MIPS-Jahren über eine verstrichene Zeit von ungefähr sieben Monaten. Bis 2009 konnte Benjamin Moody einen RSA-512-Bit-Schlüssel in 73-Tagen nur mit öffentlicher Software (GGNFS) und seinem Desktop-Computer (einem Dual-Core-Athlon64 mit einer 1,900-MHz-CPU) verwenden. Für den Siebvorgang wurden nur weniger als fünf Gigabyte Festplattenspeicher und etwa 2,5 Gigabyte RAM benötigt.,

Rivest, Shamir und Adleman hingewiesen, dass Miller hat gezeigt, dass – unter der Annahme der Wahrheit der Erweiterten Riemann-Hypothese – die Suche nach d aus n und e ist so hart wie das factoring n in p und q (bis auf ein Polynom der Zeit Unterschied). Rivest, Shamir und Adleman stellten jedoch in Abschnitt IX/D ihres Papiers fest, dass sie keinen Beweis dafür gefunden hatten, dass das Invertieren von RSA so schwierig ist wie das Factoring.

Ab 2020 betrug die größte öffentlich bekannte faktorisierte RSA-Zahl 829 Bit (250 Dezimalstellen, RSA-250). Die Faktorisierung durch eine hochmoderne verteilte Implementierung dauerte ungefähr 2700 CPU-Jahre., In der Praxis sind RSA-Schlüssel normalerweise 1024 bis 4096 Bit lang. Im Jahr 2003 schätzte RSA Security, dass 1024-Bit-Schlüssel wahrscheinlich bis 2010 knackbar werden würden. Ab 2020 ist nicht bekannt, ob solche Schlüssel geknackt werden können, aber die Mindestanforderungen sind auf mindestens 2048 Bit gestiegen. Es wird allgemein angenommen, dass RSA sicher ist, wenn n außerhalb des Quantencomputers ausreichend groß ist.

Wenn n 300 Bit oder kürzer ist, kann es in wenigen Stunden in einem PC mit bereits frei verfügbarer Software berücksichtigt werden., Schlüssel mit 512 Bit sind nachweislich 1999 praktisch zerbrechlich, als RSA-155 unter Verwendung von mehreren hundert Computern faktorisiert wurde, und diese werden jetzt in einigen Wochen mit üblicher Hardware faktorisiert. Exploits mit 512-Bit-Code-Signaturzertifikaten, die möglicherweise berücksichtigt wurden, wurden 2011 gemeldet. Ein theoretisches Hardwaregerät namens TWIRL, das 2003 von Shamir und Tromer beschrieben wurde, stellte die Sicherheit von 1024-Bit-Schlüsseln in Frage.,

Im Jahr 1994 zeigte Peter Shor, dass ein Quantencomputer – wenn man jemals praktisch für diesen Zweck geschaffen werden könnte – in der Lage wäre, Polynomzeit zu berücksichtigen und RSA zu brechen; siehe Shor ‚ s Algorithmus.

Fehlerhafte Schlüsselgenerierungedit

Das Finden der großen Primzahlen p und q wird in der Regel durch Testen von Zufallszahlen der richtigen Größe mit probabilistischen Primalitätstests, die schnell praktisch alle der nonprimes beseitigen getan.

Die Zahlen p und q sollten nicht „zu nahe“ sein, damit die Fermat-Faktorisierung für n nicht erfolgreich ist., Wenn p-q kleiner als 2n1 / 4 ist (n = p * q, was selbst für kleine 1024-Bit-Werte von n 3×1077 ist), ist das Lösen für p und q trivial. Außerdem, wenn entweder p-1 oder q-1 hat nur kleine Primfaktoren, n kann durch Pollards p − 1-Algorithmus schnell faktorisiert werden, und daher sollten solche Werte von p oder q verworfen werden.

Es ist wichtig, dass der private exponent d groß genug sein. Michael J. Wiener zeigte, dass, wenn p zwischen q und 2q (was ziemlich typisch ist) und d < n1/4/3, d effizient aus n und e berechnet werden kann.,

Es ist kein Angriff auf kleine öffentliche Exponenten wie e = 3 bekannt, sofern das richtige Auffüllen verwendet wird. Coppersmith Angriff hat viele Anwendungen in RSA angreifen speziell, wenn der öffentliche Exponent e klein ist und wenn die verschlüsselte Nachricht kurz ist und nicht aufgefüllt. 65537 ist ein häufig verwendeter Wert für e; Dieser Wert kann als Kompromiss zwischen der Vermeidung potenzieller kleiner Exponentenangriffe und der effizienten Verschlüsselung (oder Signaturüberprüfung) angesehen werden., Die NIST-Sonderpublikation zur Computersicherheit (SP 800-78 Rev 1 vom August 2007) erlaubt keine öffentlichen Exponenten e kleiner als 65537, gibt jedoch keinen Grund für diese Einschränkung an.

Im Oktober 2017 kündigte ein Forscherteam der Masaryk University die ROCA-Sicherheitsanfälligkeit an, die sich auf RSA-Schlüssel auswirkt, die von einem Algorithmus generiert werden, der in einer Bibliothek von Infineon namens RSALib enthalten ist. Es wurde gezeigt, dass eine große Anzahl von Smartcards und Trusted Platform Modules (TPMs) betroffen ist. Anfällige RSA-Schlüssel können leicht mit einem Testprogramm identifiziert werden, das das Team veröffentlicht hat.,

Bedeutung starker Zufallszahlengenerationedit

Ein kryptographisch starker Zufallszahlengenerator, der ordnungsgemäß mit adäquater Entropie ausgesät wurde, muss verwendet werden, um die Primzahlen p und q zu generieren. Eine Analyse zum Vergleich von Millionen öffentlicher Schlüssel, die aus dem Internet gesammelt wurden, wurde Anfang 2012 von Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung und Christophe Wachter durchgeführt. Sie waren in der Lage, 0,2% der Schlüssel Faktor nur Euklid Algorithmus.

Sie nutzten eine Schwäche, die für Kryptosysteme einzigartig ist, basierend auf ganzzahliger Faktorisierung., Wenn n = pq ein öffentlicher Schlüssel ist und n‘ = p‘ q‘ ein anderer ist, dann, wenn zufällig p = p‘ (aber q ist nicht gleich q‘), dann eine einfache Berechnung von gcd(n, n‘) = p Faktoren sowohl n als auch n‘, beide Schlüssel völlig kompromittierend. Lenstra et al. beachten Sie, dass dieses Problem minimiert werden kann, indem ein starker zufälliger Seed der Bitlänge verwendet wird, der doppelt so hoch ist wie die beabsichtigte Sicherheitsstufe, oder indem eine deterministische Funktion verwendet wird, um q und p auszuwählen, anstatt p und q unabhängig voneinander zu wählen.

Nadia Heninger war Teil einer Gruppe, die hat ein ähnliches experiment. Sie benutzten eine Idee von Daniel J., Bernstein, um die GCD jedes RSA-Schlüssels n gegen das Produkt aller anderen Schlüssel n‘ zu berechnen, die sie gefunden hatten (eine 729-Millionen-stellige Zahl), anstatt jede gcd(n, n‘) separat zu berechnen, wodurch eine sehr signifikante Beschleunigung erreicht wird, da das GCD-Problem nach einer großen Teilung von normaler Größe ist.

Heninger sagt in ihrem Blog, dass die schlechten Schlüssel fast ausschließlich in eingebetteten Anwendungen aufgetreten sind, einschließlich „Firewalls, Routern, VPN-Geräten, Remote-Server-Verwaltungsgeräten, Druckern, Projektoren und VOIP-Telefonen“ von mehr als 30 Herstellern., Heninger erklärt, dass das von den beiden Gruppen aufgedeckte One-Shared-Prime-Problem auf Situationen zurückzuführen ist, in denen der Pseudorandom-Zahlengenerator anfänglich schlecht ausgesät wird und dann zwischen der Erzeugung des ersten und zweiten Primwerts zurückgesetzt wird. Die Verwendung von Samen mit ausreichend hoher Entropie, die aus Schlüsselhubzeiten oder elektronischem Diodenrauschen oder atmosphärischem Rauschen eines zwischen Stationen abgestimmten Funkempfängers erhalten werden, sollte das Problem lösen.

Eine starke Zufallszahlengenerierung ist in jeder Phase der Kryptographie mit öffentlichen Schlüsseln wichtig., Wenn beispielsweise ein schwacher Generator für die symmetrischen Schlüssel verwendet wird, die von RSA verteilt werden, kann ein Lauscher RSA umgehen und die symmetrischen Schlüssel direkt erraten.

Timing attacksEdit

Kocher beschrieb 1995 einen neuen Angriff auf RSA: Wenn der Angreifer Eve die Hardware von Alice ausreichend genau kennt und die Entschlüsselungszeiten für mehrere bekannte Chiffretexte messen kann, kann er den Entschlüsselungsschlüssel d schnell ableiten. Dieser Angriff kann auch gegen das RSA-Signaturschema angewendet werden., Im Jahr 2003 demonstrierten Boneh und Brumley einen praktischeren Angriff, mit dem RSA-Faktorisierungen über eine Netzwerkverbindung wiederhergestellt werden können (z. B. von einem SSL-fähigen Webserver (Secure Sockets Layer)) Dieser Angriff nutzt Informationen aus, die durch die chinesische resttheoretische Optimierung durchgesickert wurden, die von vielen RSA-Implementierungen verwendet wird.

Eine Möglichkeit, diese Angriffe zu vereiteln, besteht darin, sicherzustellen, dass die Entschlüsselungsoperation für jeden Chiffretext eine konstante Zeit in Anspruch nimmt. Dieser Ansatz kann jedoch die Leistung erheblich reduzieren., Stattdessen verwenden die meisten RSA-Implementierungen eine alternative Technik, die als kryptografische Blendung bekannt ist. RSA Blending nutzt die multiplikative Eigenschaft von RSA. Anstatt cd (mod n) zu berechnen, wählt Alice zuerst einen geheimen Zufallswert r und berechnet (rec)d (mod n). Das Ergebnis dieser Berechnung ist nach Anwendung des Euler-Theorems rcd (mod n) und so kann der Effekt von r durch Multiplikation mit seiner Umkehrung entfernt werden. Für jeden Chiffretext wird ein neuer Wert von r gewählt. Wenn die Blendung angewendet wird, korreliert die Entschlüsselungszeit nicht mehr mit dem Wert des Eingabe-Chiffretexts, und der Timing-Angriff schlägt fehl.,

Adaptive chosen ciphertext attacksEdit

1998 beschrieb Daniel Bleichenbacher den ersten praktischen adaptive chosen Ciphertext Attack gegen RSA-verschlüsselte Nachrichten mit dem PKCS #1 v1 Padding Scheme (ein Padding-Schema randomisiert und fügt einer RSA-verschlüsselten Nachricht Struktur hinzu, sodass festgestellt werden kann, ob eine entschlüsselte Nachricht gültig ist). Aufgrund von Fehlern mit dem PKCS #1-Schema konnte Bleichenbacher einen praktischen Angriff auf RSA-Implementierungen des Secure Socket Layer-Protokolls durchführen und Sitzungsschlüssel wiederherstellen., Als Ergebnis dieser Arbeit empfehlen Kryptographen jetzt die Verwendung von nachweislich sicheren Auffüllschemata wie optimalem asymmetrischem Verschlüsselungspolster, und RSA Laboratories hat neue Versionen von PKCS #1 veröffentlicht, die für diese Angriffe nicht anfällig sind.

Side-Channel Analysis attacksEdit

Ein Side-Channel-Angriff mittels Branch Prediction Analysis (BPA) wurde beschrieben. Viele Prozessoren verwenden einen Verzweigungsprädiktor, um zu bestimmen, ob ein bedingter Zweig im Befehlsfluss eines Programms wahrscheinlich verwendet wird oder nicht. Oft implementieren diese Prozessoren auch simultanes Multithreading (SMT)., Angriffe auf Zweigvorhersageanalysen verwenden einen Spionageprozess, um den privaten Schlüssel (statistisch) zu ermitteln, wenn er mit diesen Prozessoren verarbeitet wird.

Die Simple Branch Prediction Analysis (SBPA) behauptet, BPA nicht statistisch zu verbessern. In ihrem Artikel „On the Power of Simple Branch Prediction Analysis“ behaupten die Autoren von SBPA (Onur Aciicmez und Cetin Kaya Koc), 508 von 512 Bits eines RSA-Schlüssels in 10 Iterationen entdeckt zu haben.

2010 wurde ein Power Fault-Angriff auf RSA-Implementierungen beschrieben., Der Autor stellte den Schlüssel wieder her, indem er die CPU-Leistungsspannung außerhalb der Grenzen variierte; Dies verursachte mehrere Stromfehler auf dem Server.