Frage:
Sollte sich der öffentliche RSA-Exponent aus Sicherheitsgründen nur in {3, 5, 17, 257 oder 65537} befinden?
Vladislav Rastrusny
2011-03-01 14:59:16 UTC
view on stackexchange narkive permalink

In meinem Projekt verwende ich den Wert des öffentlichen Exponenten von 4451h. Ich fand es sicher und in Ordnung, bis ich anfing, eine kommerzielle RSA-Verschlüsselungsbibliothek zu verwenden. Wenn ich diesen Exponenten mit dieser Bibliothek verwende, wird eine Ausnahme ausgelöst.

Ich habe die Entwickler dieser Bibliothek kontaktiert und die folgende Antwort erhalten: "Diese Funktion soll einige Angriffe auf RSA-Schlüssel verhindern. Die Folge ist, dass der Exponent Der Wert ist auf {3, 5, 17, 257 oder 65537} begrenzt. Die Deaktivierung dieser Prüfung wird noch untersucht, da die Risiken sehr groß sein können. "

Es ist das erste Mal in meinem Leben, dass ich diese Werte höre andere als {3, 5, 17, 257 oder 65537} werden verwendet, um RSA zu brechen. Ich wusste nur, dass ich 3 verwenden kann, wenn falsche Polsterung anfällig ist.

Ist das wirklich so? Sicherlich kann ich eine andere Bibliothek verwenden, aber nach einer solchen Antwort machte ich mir Sorgen um die Sicherheit meiner Lösung.

Sechs antworten:
#1
+69
Thomas Pornin
2011-03-01 18:13:06 UTC
view on stackexchange narkive permalink

Es ist keine Schwäche für einen kurzen oder langen öffentlichen Exponenten für RSA bekannt, solange der öffentliche Exponent "korrekt" ist (dh für alle Primzahlen p relativ prim zu p-1 die den Modul teilen).

Wenn Sie einen kleinen Exponenten und verwenden, verwenden Sie keine Auffüllung für die Verschlüsselung und Sie verschlüsseln genau dieselbe Nachricht mit mehreren unterschiedlichen öffentlichen Schlüsseln, dann ist Ihre Nachricht gefährdet: Wenn e = 3 , und Sie verschlüsseln die Nachricht m mit öffentlichen Schlüsseln n 1 sub> , n 2 sub> und n 3 sub> , dann haben Sie c i sub> = m 3 sup> mod n i sub> für i = 1 bis 3 . Mit dem chinesischen Restsatz können Sie dann m mod n 1 sub> n neu erstellen 2 sub> n 3 sub> , was sich als m sup> (ohne Modulo) herausstellt, weil n 1 sub> n 2 sub> n 3 sub> ist eine größere ganze Zahl. Eine (nicht modulare) Kubikwurzelextraktion reicht dann aus, um m zu extrahieren.

Die Schwäche ist hier nicht der kleine Exponent; Vielmehr ist es die Verwendung einer falschen Auffüllung (nämlich überhaupt keine Auffüllung) für die Verschlüsselung. Das Auffüllen ist für die Sicherheit von RSA sehr wichtig, egal ob Verschlüsselung oder Signatur. Wenn Sie keine ordnungsgemäße Polsterung verwenden (wie die in PKCS # 1 beschriebenen), haben Sie viele Schwächen, und die im obigen Absatz beschriebene ist bei weitem nicht die größte. Wenn sich jemand jedoch auf eine Schwäche im Zusammenhang mit der Exponentengröße bezieht, bezieht er sich mehr oder weniger direkt auf dieses Ereignis. Das ist ein bisschen alte und falsche Überlieferung, die manchmal in ein Verbot gegen große Exponenten umgewandelt wird (da es sich um einen Mythos handelt, ist der umgekehrte Mythos auch ein Mythos und nicht mehr - und nicht weniger - - begründet); Ich glaube, das beobachten Sie hier.

Es gibt jedoch einige Gründe, warum ein großer öffentlicher Exponent vermieden werden sollte:

  • Kleine öffentliche Exponenten fördern die Effizienz (für Operationen mit öffentlichem Schlüssel).

  • Es gibt Sicherheitsprobleme bei einem kleinen privaten Exponenten ;; Ein Schlüsselwiederherstellungsangriff wurde beschrieben, wenn die Länge des privaten Exponenten nicht mehr als 29% der Länge des öffentlichen Exponenten beträgt. Wenn Sie erzwingen möchten, dass der private Exponent kurz ist (z. B. um Operationen mit privaten Schlüsseln zu beschleunigen), müssen Sie mehr oder weniger einen großen öffentlichen Exponenten verwenden (so groß wie der Modul). Das Erfordernis, dass der öffentliche Exponent kurz ist, kann dann als eine Art indirekte Gegenmaßnahme angesehen werden.

  • Einige weit verbreitete RSA-Implementierungen drosseln große öffentliche RSA-Exponenten. Z.B. Der RSA-Code in Windows (CryptoAPI, von Internet Explorer für HTTPS verwendet) besteht darauf, den öffentlichen Exponenten in einem einzigen 32-Bit-Wort zu codieren. Es kann keinen öffentlichen Schlüssel mit einem größeren öffentlichen Exponenten verarbeiten.

Dennoch sieht "Risiken können groß sein" wie die generische Begründung aus ("Dies ist ein Sicherheitsproblem" ist das übliche Art zu sagen "wir haben es nicht implementiert, aber wir wollen keine Art von Faulheit zugeben").

Sehr gut gesagt. IIRC, irgendwann in seinen vielen Inkarnationen, erzeugte PGP während der Schlüsselgenerierung einen zufälligen öffentlichen 16-Bit-Exponenten.
In einer erstaunlichen Entwicklung wird dieser Beitrag jetzt verwendet, um die Verwendung von 1 als öffentlichen Exponenten zu rechtfertigen. Https://github.com/saltstack/salt/commit/5dd304276ba5745ec21fc1e6686a0b28da29e6fc#commitcomment-3525158
Der Nachwelt zuliebe.Der Schlüsselwiederherstellungsangriff, der bei Verwendung eines kleinen privaten Exponenten (oder eines großen öffentlichen Exponenten) angewendet wird, heißt [Wiener-Angriff] (https://en.wikipedia.org/wiki/Wiener's_attack).
#2
+22
D.W.
2011-03-02 12:11:52 UTC
view on stackexchange narkive permalink

Die Entwickler sind einfach falsch. Es ist nichts falsch mit dem Exponenten 0x4451 (dezimal 17489); Es entstehen keine Sicherheitsprobleme.

Vor langer Zeit dachten die Leute, dass kleine Exponenten ein Problem waren, aufgrund eines Angriffs, den Thomas Pornin mit dem Senden derselben Nachricht an mehrere Empfänger erklärte. Aber heute verstehen wir, dass die Exponenten nichts damit zu tun hatten; Das Problem war die falsche Polsterung. Diese Angriffe werden durch die richtige Verwendung der Polsterung verhindert. Jede Kryptobibliothek, die ihr Geld wert ist, sollte verdammt noch mal die richtige Polsterung verwenden (ansonsten haben Sie weitaus schlimmere Probleme).

Es gibt also keinen guten Grund für eine Kryptobibliothek, die Verwendung dieses Exponenten rundweg zu verbieten.

Aus Sicht der Leistung ist die Leistung jedoch umso besser, je kleiner der Exponent ist. Die beste Wahl ist e = 3, da dies die beste Leistung bietet und keine bekannten Sicherheitsprobleme aufweist. (Tatsächlich ist e = 2 sogar ein bisschen besser. Es wird auch als Rabin-Verschlüsselung bezeichnet. Dieses Schema ist jedoch nicht so bekannt und erfordert etwas anderen Code, sodass es nicht weit verbreitet ist.)

Sind Sie sicher, dass "e = 2 ist noch ein bisschen besser" für RSA gilt? Mit e = 2 gibt es keine Inverse, weil phi (N) gerade ist.
@Yifan, können Sie zunächst https://en.wikipedia.org/wiki/Rabin_cryptosystem lesen.
Für Rabin ist die Entschlüsselung: m = sqrt (c) mod N, gegeben c = m ^ 2 mod N. Für RSA ist die Entschlüsselung: m = c ^ d mod N, gegeben c = m ^ e mod N. In dem Fall von e = 2 gibt es kein inverses mod phi (N) (da 2 und phi (N) nicht relativ prim sind), so dass Sie keine Anzeige finden können, so dass e * d = 1 mod phi (N) ist.
@Yifan, ja, ich verstehe das alles. Ich bin mir nicht sicher, wohin du damit gehst. Ich sage, dass Rabin mit e = 2 noch ein bisschen besser ist als RSA mit e = 3. Nein, Rabin mit e = 2 ist nicht dasselbe wie RSA, aber die Unterschiede sind ein Detail, das den Rahmen dieser speziellen Frage sprengt.
Okay, das ist die Klarstellung, die ich wollte. Für das ungeübte Auge bedeutet Ihre Antwort, dass Sie für RSA e = 2 wählen können.
#3
+19
aaz
2011-03-01 00:39:39 UTC
view on stackexchange narkive permalink

Diese fünf Zahlen sind Fermat-Primzahlen.

Da sie die Form 2 k sup> + 1 haben, Verschlüsselung ist m sup> = m · (( m 2 ) sup>) 2 sup> ... k mal sub> ...) 2 sup>, was einfacher und schneller als Exponentiation ist mit einem Exponenten ähnlicher Größe im allgemeinen Fall.

Da es sich um Primzahlen handelt, ist der Test, zu dem e koprime ist ( p - 1) ( q - 1) ist nur ein Test, bei dem e ihn nicht teilt.

Dies ist also wahrscheinlicher über Geschwindigkeit oder Konvention als über Sicherheit. Nicht, dass etwas falsch daran ist, effizient zu sein. Bitten Sie jedoch um eine Referenz, wie in der anderen Antwort vorgeschlagen.

Siehe auch diesen Beitrag.

#4
+8
Accipitridae
2011-02-28 23:56:07 UTC
view on stackexchange narkive permalink

Mir ist kein Grund bekannt, warum der öffentliche Exponent eines RSA-Schlüssels nur in der Menge {3,5,17,257,65537} enthalten sein sollte. Wie Sie bereits erwähnt haben, ist die Verwendung kleiner Exponenten wie 3 oder 5 riskanter, da die negativen Auswirkungen von Implementierungsfehlern (z. B. falsches Auffüllen) größer sein können. NIST erlaubt nur öffentliche Exponenten, die größer als 2 ^ 16 sind, aber ich kenne keinen Grund für ihre Entscheidung.

Sie sollten mit der Antwort der Entwickler der Bibliothek, die Sie verwenden und fragen, nicht zufrieden sein für eine konkrete Referenz. Viel zu oft stellt sich heraus, dass etwas Papier missverstanden wurde. Ich könnte mir zum Beispiel vorstellen, dass ein Entwickler Abschnitt 4 des Papiers "Können wir kryptografischer Software vertrauen? Kryptografische Fehler in GNU Privacy Guard v1.2.3" von Phong Nguyen liest und zu einer falschen Schlussfolgerung kommt, wie oben. In diesem Artikel wird darauf hingewiesen, dass der Angreifer ein wenig Informationen über den geheimen Schlüssel erhält, wenn sich herausstellt, dass der von GnuPG generierte öffentliche Schlüssel ein ungewöhnlicher Wert wie 65539 ist. Die Schlussfolgerung lautet, dass der Algorithmus zur GnuPG-Schlüsselgenerierung verbessert werden könnte, aber nicht 65539 ist ein schlechter öffentlicher Schlüssel.

#5
+7
Andreas Arnold
2011-03-01 15:43:26 UTC
view on stackexchange narkive permalink

Ich konnte keinen Hinweis darauf finden, dass andere Werte für den öffentlichen Exponenten anfällig sind. Laut dem RSA.com-Leitfaden zum RSA-Algorithmus

Laut Wikipedia ist es aus Leistungsgründen ratsam, einen öffentlichen Exponenten nahe einer Potenz von 2 zu verwenden a>, NIST erlaubt keinen öffentlichen Exponenten kleiner als 65537, da kleinere Exponenten ein Problem darstellen, wenn sie nicht richtig aufgefüllt sind.

Es stellt sich heraus, dass der letzte Absatz dieser Antwort völlig falsch ist. (Wikipedia ist falsch; stellen Sie sich das vor!) Das Problem hat nichts mit kleinen Exponenten zu tun. Wenn Sie nicht die richtige Polsterung verwenden, sind Sie so geschraubt (und dies gilt unabhängig davon, welchen Exponenten Sie verwenden). Wenn Sie die richtige Polsterung verwenden, sind kleine Exponenten genauso gut wie große. Es ist also ein Missverständnis zu glauben, dass dies irgendetwas mit der Größe des Exponenten zu tun hat, im Gegensatz zum Vorhandensein / Fehlen einer geeigneten Polsterung.
Wie gesagt, ohne richtige Polsterung. Aber ich habe die Quelle der Wikipedia-Aussage überprüft, und es ist teilweise falsch. Laut SP 800-78-3 (http://csrc.nist.gov/publications/nistpubs/800-78-3/sp800-78-3.pdf), Seite 6: "Diese Spezifikation beschränkt auch die Größe der RSA-Exponent, der PIV-Schlüsseln zugeordnet sein kann. Bei der Implementierung dieser Spezifikation muss ein Exponent ausgewählt werden, der eine ungerade positive Ganzzahl größer oder gleich 65.537 und kleiner als 2256 ist, wie in Tabelle 3-2 angegeben. " Also nur für PIV-Keys (Personal Identity Verification) nach FIPS 201.
#6
-2
FaST4
2018-02-01 15:39:26 UTC
view on stackexchange narkive permalink

Um Don Coppersmiths 1997 erschienene Veröffentlichung "Kleine Lösungen für Polynomgleichungen und RSA-Schwachstellen mit niedrigen Exponenten" zu zitieren:

Die RSA-Verschlüsselung mit Exponent 3 ist anfällig, wenn der Gegner zwei Drittel der Nachricht kennt

Während dies möglicherweise kein Problem darstellt, wenn das RSA-OAEP-Auffüllschema verwendet wird, ist das PKCS # 1-Auffüllschema (das in den folgenden Antworten als geeignetes Auffüllschema angegeben ist) anfällig wenn der öffentliche Exponent 3 verwendet wird.

Dies ist keine richtige Antwort.Sie sprechen nur einen Exponenten an, und es gibt andere Antworten, die Jahre vor Ihnen veröffentlicht wurden und dieses Problem offenbar bereits ausführlicher behandeln.Abstimmungen bedeuten nicht unbedingt, dass Sie falsch liegen.Abstimmungen können einfach bedeuten, dass Ihre Antwort "nicht nützlich" ist (gemäß Tooltip), dem ich in diesem Fall zustimmen würde.
In der vorherigen Antwort heißt es: "Es ist keine Schwäche für einen kurzen oder langen öffentlichen Exponenten für RSA bekannt", was sachlich falsch ist.Darauf möchte meine Antwort hinweisen.
Das ist also eine Antwort auf eine andere Antwort?
Wenn Sie der Meinung sind, dass die akzeptierte Antwort falsch ist, schreiben Sie bitte einen Kommentar zu dieser Antwort.Ich bin sicher, dass Pornin mehr als Experte genug ist, um es zu beurteilen.


Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 2.0-Lizenz, unter der er vertrieben wird.
Loading...