Bedeutung von: "Wenn es schwierig ist, große ganze Zahlen zu berücksichtigen, ist es schwierig, RSA zu brechen."

30

Ich habe CLRS gelesen und es heißt:

Wenn es einfach ist, große ganze Zahlen zu berücksichtigen, ist es einfach, das RSA-Kryptosystem zu beschädigen.

Was für mich Sinn macht, denn mit der Kenntnis von und ist es einfach, den geheimen Schlüssel zu erzeugen, der der Kenntnis des öffentlichen Schlüssels entspricht. Es erklärt jedoch die umgekehrte Aussage, die ich nicht ganz verstehe:pq

Die umgekehrte Aussage, dass es schwierig ist, RSA zu brechen, wenn es schwierig ist, große ganze Zahlen zu berücksichtigen, ist nicht bewiesen.

Was bedeutet die obige Aussage formal? Wenn wir annehmen, dass Factoring (auf irgendeine formale Weise) schwierig ist, warum bedeutet das nicht, dass es schwierig ist, das RSA-Kryptosystem zu beschädigen?

Bedenken Sie nun, dass das RSA-Kryptosystem schwer zu knacken ist, wenn wir davon ausgehen, dass Factoring schwierig ist. Was würde das formal bedeuten?

Charlie Parker
quelle
3
Es könnte bedeuten, dass es schwierig ist, RSA zu brechen, aber es wurde nicht bewiesen .
Tom van der Zanden
2
Das diskrete Logarithmus-Problem, das das Brechen von RSA ausmacht, obwohl es "sehr ähnlich" ist, hat sich nicht als gleichwertig mit Factoring erwiesen.
Dies ist
1
Sollte der zweite nicht einen Bindestrich anstelle von Kommas verwenden? Wird kein Bindestrich verwendet, wenn die abhängige Klausel Kommas enthält? The converse statement -- that if factoring large integers is hard, then breaking RSA is hard -- is unproven.
Czipperz
@ruakh: Hoppla, ja ... Ich habe es sogar noch einmal überprüft, aber ich habe es trotzdem falsch verstanden. Ich vergesse immer wieder, dass Sie sich auf ein Problem reduzieren sollen, von dem Sie wissen, dass es einfach ist, und nicht auf ein Problem, von dem Sie wissen, dass es mindestens so schwer ist wie Ihr derzeitiges. :-) Danke dafür, ich habe es entfernt.
Mehrdad
Mathematisches Argument: "Wenn , dann " bedeutet dasselbe wie "Wenn nicht , dann nicht ". Sie können nichts über "Wenn nicht , dann nicht " sagen . B B A A BABBAAB
Drzbir

Antworten:

50

Der einfachste Weg, darüber nachzudenken, ist, an das Kontrapositive zu denken.

Die Aussage:

Wenn es schwierig ist, große ganze Zahlen zu berücksichtigen, ist es schwierig, RSA zu brechen

ist äquivalent zu:

Wenn es einfach ist, RSA zu brechen, ist es einfach, große ganze Zahlen zu faktorisieren

Diese Aussage wurde nicht bewiesen.

Angenommen, wir haben einen Algorithmus, der das Faktorisieren in der Polynomzeit löst. Dann können wir damit einen Algorithmus konstruieren, der RSA in polynomialer Zeit löst.

Es könnte aber auch eine andere Möglichkeit geben, RSA zu knacken, bei der keine ganzen Zahlen berücksichtigt werden. Es ist möglich, dass wir RSA auf eine Weise knacken können, die es uns nicht erlaubt, ganze Zahlen in der Polynomzeit zu berücksichtigen.

Kurz gesagt, wir wissen, dass RSA mindestens so einfach ist wie Factoring. Es gibt zwei mögliche Ergebnisse: RSA und Factoring sind von gleichem Schwierigkeitsgrad, oder RSA ist ein strikt einfacheres Problem als Factoring. Wir wissen nicht, was der Fall ist.

jmite
quelle
10
"Mindestens genauso einfach" - so interpretieren Sie Reduktionen, die Sie auch andersherum ausdrücklicher lehren sollten.
G. Bach
Du kannst es so oder so machen, wenn X mindestens so hart ist wie Y, Y ist mindestens so einfach wie X.
jmite
2
Das habe ich gemeint - fast jeder hat wahrscheinlich gehört, "X ist mindestens so schwer wie Y", aber "Y ist mindestens so einfach wie X" wird sehr selten erklärt - obwohl es genauso nützlich ist.
G. Bach
1
Ich erinnere mich vage daran, dass Donald Knuth einen Algorithmus erwähnt hat, mit dem eine Maschine, die beliebige RSA-verschlüsselte Nachrichten auf magische Weise knacken kann, Produkte aus zwei großen Primzahlen faktorisieren kann. Ich könnte das falsch haben :-(
gnasher729
31

Die Existenz eines harten Weges bedeutet nicht, dass es keinen einfachen Weg gibt.

Es kann eine Reihe von Möglichkeiten geben, RSA zu brechen, und wir müssen nur eine davon finden.


Eine dieser Möglichkeiten ist das Faktorieren einer großen Ganzzahl. Wenn dies also einfach ist, können wir es auf diese Weise tun und RSA wird gebrochen. Dies ist auch der einzige Weg, den wir noch kennen. Wenn dies nicht möglich ist, können wir immer noch einen anderen, weniger rechenintensiven Weg finden, um unsere Aufgabe auszuführen, ohne p und q explizit aus n berechnen zu müssen .


Um zu beweisen, dass RSA defekt ist, müssen wir beweisen, dass eine Möglichkeit einfach ist.

Um zu beweisen, dass RSA sicher ist, müssen wir beweisen, dass alle Möglichkeiten schwierig sind.


Schließlich ist Ihre Aussage unbewiesen, da unbewiesen ist, dass es keine andere, einfachere Methode gibt, die Informationen aus einem Chiffretext extrahiert.

Rainer P.
quelle
1
Wir könnten beweisen, dass RSA und Factoring gleichermaßen schwierig sind, wenn wir einen Algorithmus entwickeln könnten, der Produkte aus zwei großen Primzahlen faktorisiert, indem wir einige spezielle RSA-verschlüsselte Nachrichten generieren, sie knacken und dann weitere Berechnungen durchführen. Das würde bedeuten, dass RSA nicht einfacher ist als Factoring. Es bedeutet nicht, dass entweder einfach oder schwer ist.
gnasher729
@ gnasher729 Wäre das ausreichend? Wenn der Algorithmus Produkte aus zwei großen Primzahlen, aber keine Produkte mit mehr als zwei Primzahlen oder Produkte mit kleinen Primzahlen faktorisieren könnte?
Otakucode
@ Ich denke, RSA hängt nur von den Faktoren ab, die Coprime sind. Es wäre also einfach, Produkte mit mehreren Faktoren zu umgehen.
Taemyr
10

Eine weitere Sichtweise ist, dass das Brechen von RSA nur einen Sonderfall des Factorings erfordert, der unabhängig von der allgemeinen Frage des Factorings einfach sein kann oder nicht.

Betrachten Sie als einfaches Beispiel den Fall, dass Factoring zwar schwierig ist, aber nur für Zahlen mit verschiedenen Faktoren. Das Faktorisieren von zusammengesetzten Zahlen mit nur zwei verschiedenen Faktoren (wie in RSA verwendet) kann immer noch einfach sein.3

Ran G.
quelle
7

Dies bedeutet, dass das RSA-Problem (zu diesem Zeitpunkt) spezifischer zu sein scheint als Factoring.

Das RSA-Problem lautet also: Wenn Sie ein Semiprime und einen Exponenten und einen Wert finden Sie das so, dass . (Ich habe dies in meiner ursprünglichen Antwort tatsächlich falsch verstanden, sodass meine Formulierung des RSA-Problems mit der Berücksichtigung eines PP-Algorithmus gleichzusetzen war. Hoppla! Sie sind also nicht allein, wenn es darum geht, die Details hier zu verwechseln.)e , v , mpqe,v,mvmemodpq

Das Factoring-Problem ist: Wenn Sie ein Semiprime- finden Sie sowohl als auch .pq,pq

Wenn Sie das Factoring-Problem effizient lösen können, können Sie das RSA-Problem effizient lösen: Nehmen Sie das Semiprime, faktorieren Sie es, und verwenden Sie einige Sätze über Primmodule, um einen inversen Exponenten zu berechnen , der alle Chiffretexte als aufdeckt . (Tatsächlich funktioniert das Setup für RSA nach diesen Theoremen: Wir kennen die beiden Primzahlen während der Setup-Phase.)dmvd

Es ist jedoch nicht bekannt, dass das Lösen dieses obigen Problems für beliebige Nachrichten etwas über die Faktoren des Moduls oder der beteiligten Exponenten aussagt. Es könnte oder es könnte nicht; wir wissen es nicht Viele kluge Köpfe haben sich vermutlich mit dem Problem befasst, aber bei keinem von ihnen ist ein offensichtliches Problem aufgetaucht. Es ist also nicht bekannt, dass das Factoring-Problem durch Lösungen für das RSA-Problem (plus Polynomaufwand) gelöst wird, sondern nur, dass das RSA-Problem durch Lösungen für das Factoring-Problem (plus Polynomaufwand) gelöst wird.m

Tatsächlich haben Boneh und Venkatesan 1998 einen Beweis veröffentlicht, dass eine bestimmte einfache Klasse von Algorithmen (plus, Zeiten, Exponenten, keine XOR / NAND-Typen) nicht verwendet werden kann, um eine RSA-Problemlösung in einen Faktorisierungsalgorithmus umzuwandeln. Das Argument hatte einen einfachen Einfallsreichtum: Indem wir diese arithmetischen Operationen mathematisch manipulieren, können wir herausfinden, dass sich der "Reduktionsalgorithmus" (aus Gründen der Präzision: Dies ist der Algorithmus, der ein RSA "Orakel" für einen Semiprime verwendet, um diesen Semiprime zu faktorisieren) dreht als eigenständiger Faktorisierungsalgorithmus zu betrachten, damit wir ihn in eine Variante umwandeln können, die sein Orakel nicht anruft. Wir haben also eine Trichotomie: Entweder (a) gibt es keinen solchen Reduktionsalgorithmus, oder (b) der Reduktionsalgorithmus hat keine gute arithmetische Interpretation, oder (c) die Faktorisierung ist genau wie der Reduktionsalgorithmus polynomial.

CR Drost
quelle
"Es ist nicht bekannt, dass das Finden dieses inversen Exponenten d zu einem gegebenen e etwas über die Faktoren des Moduls aussagt." Sie können und mit , und berechnenpqned . Der Algorithmus, wie er ausgedrückt wird, ist offensichtlich PP. Ist nicht bekannt, dass er in P ist?
Gilles 'SO- hör auf böse zu sein'
@ Gilles Eigentlich denke ich, dass du recht hast, also habe ich meine Antwort entsprechend korrigiert.
CR Drost
3

RSA hängt von zwei abstrakten mathematischen Aufgaben ab, von denen angenommen wird, dass sie schwierig sind: Integer-Factoring, wie Sie wissen, aber auch das Problem des diskreten Logarithmus . Sie können RSA brechen, wenn Sie eine Zahl, die das Produkt zweier großer unbekannter Primzahlen ist, schnell faktorisieren können. Sie können RSA aber auch wenn Sie in der endlichen Gruppe schnell finden , wobei und der öffentliche RSA-Exponent und -Modul und der Chiffretext sind.logeCZmemC

Diese beiden mathematischen Aufgaben hängen zusammen, aber (wenn ich mich richtig erinnere) wird angenommen, dass eine Lösung für eine keine Lösung für die andere impliziert. Ich weiß nicht, ob dies die einzigen zwei Möglichkeiten sind, RSA mathematisch zu brechen.

zwol
quelle
Ich denke, Sie könnten sich an Dinge erinnern. Das sind nicht wirklich zwei verschiedene Probleme: Wenn Sie das diskrete log modulo , können Sie faktorisieren . Mit anderen Worten, eine Lösung für das Problem des diskreten Protokolls impliziert sicherlich eine Lösung für das Faktorisierungsproblem. mm
DW