Warum wissen wir bei RSA nicht, ob eine Verschlüsselung mit öffentlichen Schlüsseln möglich ist?

23

Ich war auf Wikipedia auf der Liste der ungelösten Informatikprobleme und fand Folgendes: Ist Kryptographie mit öffentlichen Schlüsseln möglich?

Ich dachte, RSA-Verschlüsselung sei eine Form der Kryptografie mit öffentlichen Schlüsseln? Warum ist das ein Problem?

Namster
quelle
5
Wir wissen nicht einmal, ob symmetrische Kryptografie sicher sein kann, und das ist eine viel schwächere Vermutung, als dass die Verschlüsselung mit öffentlichen Schlüsseln sicher ist.
CodesInChaos
@CodesInChaos Das stimmt, solange wir über Sicherheit sprechen, die auf der Komplexität der Berechnungen basiert. Wenn Sie jedoch informationstheoretische Sicherheit in Betracht ziehen, gibt es nachweislich sichere Konstruktionen wie das One-Time-Pad für die Verschlüsselung und Wegman-Carter für die Nachrichtenauthentifizierung.
Kasperd,

Antworten:

31

Wir wissen nicht genau, ob RSA sicher ist. Es könnte sein, dass RSA in der Polynomzeit gebrochen werden kann, zum Beispiel wenn Factoring effizient durchgeführt werden kann. Offen ist die Existenz eines nachweislich sicheren Kryptosystems mit öffentlichem Schlüssel. Wir wissen nicht genau, ob ein solches Kryptosystem überhaupt existiert. Nach allem, was wir wissen, könnte jedes Kryptosystem effizient zerstört werden.

Ein anderes, nicht verwandtes Problem bei RSA ist, dass es von Quantencomputern zerstört werden kann. Dies ist ein nicht verwandtes Problem, da die Definition eines sicheren Kryptosystems mit öffentlichem Schlüssel nur erfordert, dass das Kryptosystem nicht durch klassische (Nicht-Quanten-) Computer zerbrechlich ist.

In der Praxis scheint RSA jedoch sicher zu sein und wird ständig verwendet. Dies liegt an der Kluft zwischen Theorie und Praxis. Während wir theoretisch nicht sicher sind, ob RSA sicher ist, müssen wir in der Praxis ein Public-Key-Kryptosystem verwenden, und RSA ist eine gute Wahl, da die Leute versucht haben, es zu knacken und fehlgeschlagen sind. Im Allgemeinen ist ein bekanntes Kryptosystem, um das sich die Menschen kümmern, sicherer als ein obskures, da es den Versuchen von Kryptographen widerstanden hat. Dies ist kein Beweis dafür, dass es sicher ist - vielleicht auch nicht -, aber es ist das Beste, was wir tun können.

Yuval Filmus
quelle
4
In wenigen Worten: Sicher bis kaputt.
Ismael Miguel
2
Gute Antwort. Ich möchte auch hinzufügen, dass jede Kryptographie nur mit einem Zeitrahmen geliefert wird, in dem die Wahrscheinlichkeit eines Bruchs gering ist. Niemand liefert ein Kryptosystem aus und gibt an, dass es sicher ist. Sie sagen immer, dass es in den nächsten 5 Jahren wahrscheinlich überhaupt nicht kaputt gehen wird. Dies ist ein kleines Problem für den Vertrieb, da häufig nicht-technische Kunden dies als eine festgestellte Schwäche ansehen.
RSinohara,
Dies ist eigentlich ein allgemeiner Mangel in der Informatik: CS ist sehr gut darin zu beweisen, wie lange ein Algorithmus dauern wird, aber sehr schwach darin, zu beweisen, dass es keine schnelleren Algorithmen gibt.
RBarryYoung
3

Hier sind einige andere Blickwinkel / Details zu dieser Frage, genauer und allgemeiner. Wie YF in einem Kommentar schreibt, ist RSA nicht mindestens so hart wie Factoring. Das Brechen von RSA ist mit dem Problem des diskreten Protokolls verbunden , das natürlich eng mit der Berücksichtigung der Komplexität zusammenhängt, sich jedoch nicht als dieselbe Komplexität erwiesen hat. Es hat sich jedoch (wie bereits erwähnt) nicht einmal das Factoring als schwierig erwiesen.

YF erwähnt auch die Quantenberechnung. Wie Insider wissen, ist RSA nicht sicher gegen Quantenberechnungen, die nachweislich in der Lage sind, die P-Zeit mit dem Shors-Algorithmus zu berücksichtigen . Der Shors-Algorithmus galt damals als Durchbruch. Ein weiterer Durchbruch, der in einem "nahen" Gebiet zu erwähnen ist, ist der AKS-Primalitätsalgorithmus, der bewies, dass es sich bei Primalitätstests um P handelt. Theoretische Durchbrüche in der Komplexitätstheorie sind selten, aber nicht ungewöhnlich.

YF erwähnt nicht, lauert aber immer im Hintergrund dieser Fragen, die "große Frage" von P =? NP ist noch offen. Es wird allgemein angenommen, dass "algorithmische Kryptographie unmöglich sein könnte" (mit Ausnahme von einmaligen Pads), wenn P = NP, was von Experten im Allgemeinen nicht geglaubt wird.

Impagliazzos 5 Welten , ein Überblick von Kabanets, sind eine hervorragende Möglichkeit, dies wissenschaftlich zu konzipieren . Bemerkenswerterweise wissen Komplexitätstheoretiker nicht, "in welcher der 5 Welten wir leben", obwohl es Indizien gibt, die sich in gewisser Weise lehnen. In welcher Welt wir leben, hängt von den Vermutungen der offenen Komplexitätstheorie ab. Sie beziehen sich auch auf offene Probleme bei Vorhandensein von Falltürfunktionen und Einwegfunktionen . (Es wird vermutet , dass RSA beides ist.) Im Jahr 2009 fand eine Forschungskonferenz zu Impagliazzos-Welten mit den neuesten Erkenntnissen statt.

vzn
quelle
1
siehe auch Stand der Impagliazzos-Welten / Theoretische Informatik . Kurz gesagt, RSA wird von Experten als plausibel oder wahrscheinlich sicher, aber nicht als sicher eingestuft, und diese Lücke schneidet viele der größten offenen Fragen auf diesem Gebiet.
vzn
2

Eine Sache, die hier definiert werden muss, ist die Definition des Möglichen. Es gibt zwei Möglichkeiten, dies zu beantworten. Die erste ist, kann ein Kryptosystem mit öffentlichem Schlüssel als informationstheoretisch sicher angesehen werden? Im weitesten Sinne erfordert dies, dass der Algorithmus auch dann sicher ist, wenn er einem Angriff mit unendlicher Rechenleistung ausgesetzt ist. Es gibt ein bekanntes System, das dies erreicht hat, das One Time Pad. Dies ist jedoch nur theoretisch, da wir die wirklich erforderlichen Zufallszahlen nicht erstellen können und es sich um einen privaten Schlüssel handelt. Die zweite Möglichkeit, die Frage zu beantworten, ist, ob ein Kryptosystem mit öffentlichem Schlüssel als bedingungslos sicher angesehen werden kann. Diese zweite Definition ist lockerer. Wenn im Fall von RSA jemand beweisen würde, dass die Faktorisierung ganzer Zahlen so schwierig ist, wie wir es derzeit glauben, und keine anderen Annahmen oder Mängel im System vorliegen, dann wäre RSA bedingungslos sicher. Die bedingungslose Sicherheit beseitigt den Bedarf an unendlicher Rechenleistung und lockert ihn im physischen Universum auf das Unmögliche. Da unsere Public-Key-Algorithmen alle auf massiven Annahmen zur Berechenbarkeit beruhen, erfüllen sie nicht die zweite Definition.

lAnlage
quelle
RSA zu brechen ist nicht gleichzusetzen mit Factoring. es ist möglicherweise einfacher.
Yuval Filmus
Diese Antwort ist verwirrt. Das One-Time-Pad ist kein Kryptosystem mit öffentlichem Schlüssel, daher ist es nicht korrekt, dass das One-Time-Pad dies erreicht hat. Die Antwort auf "Kann ein Kryptosystem mit öffentlichem Schlüssel als informationstheoretisch sicher angesehen werden?" ist "Nein". Es ist auch kein Beweis dafür bekannt, dass "Factoring ist hart" impliziert, dass "RSA sicher ist". In der Tat gibt es Gründe zu vermuten, dass diese Form möglicherweise nicht reduziert wird.
DW