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

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:$p$$q$

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?

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.

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.

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$

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 , $pq$$e,$$v,$$m$$v \equiv m^e \mod pq$

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

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.)$d$$m \equiv v^d$

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.

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.$\log_e C$$\mathbb{Z}_{m}$$e$$m$$C$

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.