Skip to content

RSA: Ist es einfach, den öffentlichen Schlüssel aus dem geheimen Schlüssel zu finden?

Lösung:

Für Standardanwendungen von RSA ist der geheime Schlüssel schwer zu finden und der öffentliche Schlüssel ist trivial. Dies liegt daran, dass die meisten Implementierungen 65537 als öffentlichen Schlüssel verwenden (der Grund hat mit seiner Primalität und der Effizienz der wiederholten Quadrierung für $e=65537=2^{16}+1$ zu tun).

Viele Systeme wählen $p$ und $q$ neu, wenn $phi(pq)$ nicht mit 65537 identisch ist, was bedeutet, dass der öffentliche Exponent niemals etwas anderes ist.

Mehrere andere Antworten weisen darauf hin, dass $e$ und $d$ austauschbar sind, aber dies ignoriert sowohl die Praxis als auch einige wichtige kryptanalytische Ergebnisse. Auch wenn $e$ variieren kann, kann es immer noch mit $d$ gefunden werden, wenn es klein genug ist. Dies liegt an der Tatsache, dass der Algorithmus von Coppersmith kleine Wurzeln von Polynomen modulo einer Zusammensetzung aus unbekannter Faktorisierung unter Verwendung von LLL und einiger zusätzlicher Klugheit finden kann. Die Schranke nimmt weiter zu, aber (aus dem Gedächtnis) glaube ich, wenn $e < n^{.33}$ sie aus $n$ und $d$ (hier $n=pq$) gefunden werden kann. Es ist also falsch (und gefährlich), zu sagen, dass $e$ und $d$ gleichwertig sind. Es gibt eine Vermutung, dass die "wahre" Grenze $n^{.5}$ ist, was bedeutet, dass der geheime Exponent aus Sicherheitsgründen über $sqrt{n}$ liegen müsste.

Notiz: Für wirklich Interessierte hat Boneh eine schöne Übersicht über diese Ergebnisse (und viele andere). Und es ist gut lesbar für Nicht-Kryptographen, die einen mäßig starken mathematischen Hintergrund haben.

Nein, das Auffinden des geheimen Schlüssels aus dem öffentlichen Schlüssel ist abstrakt gesehen genauso schwierig wie das Auffinden des geheimen Schlüssels aus dem öffentlichen Schlüssel.

Was Sie vorschlagen, ist in der Tat die Standardmethode, in der RSA zum "Signieren" von Nachrichten verwendet wird. Um eine Nachricht zu authentifizieren (um sicherzustellen, dass die Nachricht von mir gesendet wurde), kodiere ich sie mit my Privatgelände key, was bedeutet, dass jeder den öffentlichen Schlüssel verwenden kann, um ihn zu entschlüsseln und herauszufinden, dass er wirklich von mir gesendet wurde (weil vermutlich niemand außer mir meinen privaten Schlüssel kennt).

Das hat aber nichts damit zu tun, ob man aus dem geheimen Schlüssel den öffentlichen Schlüssel gewinnen kann; es hat mit der Funktionsweise von RSA zu tun (die Rollen des öffentlichen und des privaten Schlüssels sind symmetrisch).

Nein - sie sind ebenso schwer zu finden. Insbesondere sind der Verschlüsselungsschlüssel und der Entschlüsselungsschlüssel modulare Inverse. Die Schwierigkeit, den Entschlüsselungsschlüssel aus dem öffentlichen Schlüssel zu finden, liegt in der Tatsache, dass sie invers sind ... mod $varphi (n)$, und man muss also faktorisieren oder unglaublich witzig sein, um das Inverse zu finden.

Wenn man rückwärts wählte und stattdessen den 'Entschlüsselungsschlüssel' verteilte und den 'Verschlüsselungs'-Schlüssel für sich selbst behielt, wäre die Sicherheit genau dieselbe. (Ich habe sie in Anführungszeichen gesetzt, um zu zeigen, dass es sich um die ursprünglichen Entschlüsselungs- und Verschlüsselungsschlüssel handelt).

Aber zu Ihrer zweiten Frage gibt es eine RSA-ähnliche Methode namens digitale Signatur, bei der nur die Person, die den geheimen Schlüssel kennt, eine Nachricht verbreiten kann, die jeder in der Öffentlichkeit entschlüsseln kann. Es heißt Signatur, weil es die Authentizität garantiert

Click to rate this post!
[Total: 0 Average: 0]



Anderer Beitrag

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.