it-swarm-eu.dev

Sollte sich der öffentliche RSA-Exponent aus Sicherheitsgründen nur in {3, 5, 17, 257 oder 65537} befinden?

In meinem Projekt verwende ich den Wert des öffentlichen Exponenten von 4451h. Ich dachte, es ist 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 Exponentenwert auf {3, 5, 17, 257 oder 65537} begrenzt ist. Das Deaktivieren dieser Prüfung ist wird noch untersucht, da die Risiken groß sein können. "

Es ist das erste Mal in meinem Leben, dass ich höre, dass andere Werte als {3, 5, 17, 257 oder 65537} verwendet werden, um RSA zu brechen. Ich wusste nur, dass ich 3 verwenden sollte, wenn eine 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.

70

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

If Sie verwenden einen kleinen Exponenten und Sie verwenden kein Padding für die Verschlüsselung und Sie verschlüsseln genau dieselbe Nachricht mit Bei mehreren unterschiedlichen öffentlichen Schlüsseln ist Ihre Nachricht gefährdet: if e = 3 und Sie verschlüsseln die Nachricht m mit öffentlichen Schlüsseln n1, n2 und n3, dann hast du cich = m3 mod nich für i = 1 bis 3. Mit dem chinesischer Restsatz können Sie dann m3 mod n1n2n3, was sich als m herausstellt3 (ohne Modulo) weil n1n2n3 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ß Exponenten umgewandelt wird (da es sich um einen Mythos handelt, ist der umgekehrte Mythos auch ein Mythos und nicht mehr - und nein 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 Public-Key-Operationen).

  • Es gibt Sicherheitsprobleme, wenn ein kleiner Exponent privat vorhanden ist. 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). Die Forderung, dass der öffentliche Exponent kurz sein muss, 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 einzelnen 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 allgemeine Rechtfertigung aus ("dies ist ein Sicherheitsproblem" ist die übliche Art zu sagen "wir haben es nicht implementiert, aber wir wollen keine Art von Faulheit zugeben").

64
Thomas Pornin

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, kleine Exponenten seien ein Problem, weil Thomas Pornin einen Angriff 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 Salz 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.)

21
D.W.

Diese fünf Zahlen sind Fermat-Primzahlen .

Da sie von der Form 2 sind k  + 1, Verschlüsselung ist m e  = m · (( m 2)2... k mal...)2Dies ist einfacher und schneller als die Exponentiation mit einem Exponenten ähnlicher Größe im allgemeiner Fall .

Da es sich um Primzahlen handelt, ist der Test, dass e Coprime zu ( p ist. - 1) ( q - 1) ist nur ein Test, der e teilt es nicht.

Es geht also eher um Geschwindigkeit oder Konvention als um Sicherheit. Nicht, dass etwas falsch daran ist, effizient zu sein. Bitten Sie jedoch um eine Referenz, wie in andere Antwort vorgeschlagen.

Siehe auch dieser Beitrag .

19
aaz

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 von Ihnen verwendeten Bibliothek nicht zufrieden sein und nach einer konkreten Referenz fragen. 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. 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 GnuPG-Algorithmus zur Schlüsselgenerierung dies könnte verbessert werden, aber nicht, dass 65539 ein schlechter öffentlicher Schlüssel ist.

8
Accipitridae

Ich konnte keinen Hinweis darauf finden, dass andere Werte für den öffentlichen Exponenten anfällig sind. Laut RSA.com-Anleitung zum RSA-Algorithmus ist es aus Leistungsgründen ratsam, einen öffentlichen Exponenten nahe einer Potenz von 2 zu verwenden

Laut Wikipedia erlaubt NIST keinen öffentlichen Exponenten kleiner als 65537, da kleinere Exponenten ein Problem darstellen, wenn sie nicht richtig aufgefüllt sind.

7
Andreas Arnold