RSA: Privaten Schlüssel schneller berechnen

[Micha88]

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

[Namenloser]

Zitat von Micha88:

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

Ich bin wirklich kein Krypto-Experte, aber eins weiß ich mit Sicherheit: Man kann den Private Key nicht aus dem Public Key errechnen, denn das ist ja gerade der Sinn der Sache.

[Micha88]

Möglich ist es, "soll" es aber nicht. So habe ich es gelesen.

Mhh.. Demnach kann man RSA-verschlüsselte Texte ja niemals einsehen, wenn man den private key nicht weiß.

Das Problem sind die riesen (Prim)zahlen.

[Namenloser]

Zitat von Micha88:

Möglich ist es, "soll" es aber nicht.

Also zumindest mit unseren heutigen Computern geht es wohl nicht in absehbarer Zeit.

[Bjoerk]

Zitat von NamenLozer:

Zitat von Micha88:

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

Ich bin wirklich kein Krypto-Experte, aber eins weiß ich mit Sicherheit: Man kann den Private Key nicht aus dem Public Key errechnen, denn das ist ja gerade der Sinn der Sache.

Das ist leider nicht richtig.

RSA-Encryption:
2 Prime P, Q
P <> Q
N = P*Q
M = (P-1)*(Q-1)
Find an E and a D so that is:
S * M + 1 = E * D, E <> D, E relatively prime to M, D 1..M, E 1..M, S > 0
Encrypt: J = I^E mod N, I 0..N
Decrypt: I = J^D mod N

N, E = Public
M, P, Q, D = Private

Der Private Schlüssel D lässt sich sogar direkt aus N und E berechnen.
Guckst du hier:

Delphi-Quellcode:

procedure TRSAEncryption.FindD(const N, E: int64); // get the private Key D
var
  P, Q, M: int64;
begin
  FE:= 0;
  FD:= 0;
  FN:= 0;
  FM:= 0;
  FP:= 0;
  FQ:= 0;
  P:= 2;
  while P < N do
  begin
    if IsPrimeNumber(P) then
    begin
      Q:= N div P;
      if IsPrimeNumber(Q) then
      begin
        if P*Q = N then
        begin
          M:= (P-1)*(Q-1);
          if GreatestCommonDivisor(M, E) = 1 then
          begin
            FD:= InversMod(E, M);
            FE:= E;
            FN:= N;
            FM:= M;
            FP:= P;
            FQ:= Q;
            Break;
          end;
        end;
      end;
    end;
    P:= P+1;
  end;
end;

Fazit: Der einzige Schutz, den man bei der RSA Verschlüsselung hat, ist, das bei großen Zahlen, empfohlen sind 155 Stellen (int512), diese Procedure Jahre dauert. Für Zahlen im int64 Bereich ist die RSA Verschlüsselung nicht geeignet.

[Bummi]

Dann sind wir alle jetzt beruhigter...

[negaH]

Zitat von Bjoerk:

Das ist leider nicht richtig.

Leider ist das was du als Beispiel bringst ebenfalls nicht richtig. Du berechnest nicht direkt aus dem öffentlichen Schlüssel den privaten sondern du testest alle Kandidaten durch bis es stimmt. Das ist ein Unterschied.

Man kann N faktorisieren und das wird letzendlich, nach meinem Wissenstand, immer ein Such-Algorithmus sein der letzendlich per Trial&Error funktioniert.

Ich kenne kein praktisches Verfahren um eine zusammengesetzte Zahl, wie beim RSA notwendig, direkt in ihre Primzahlfaktoren zu zerlegen.

Gruß Hagen

[negaH]

Zitat von Micha88:

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

Ja kann man. Die Sicherheit von RSA, bzw. jeder Kryptographie kannst du dir so vorstellen:

Ich baue einen riesigen Sandhaufen und setze mich drauf. Vorher berechne ich das ich 100 Jahre leben möchte und das mich keiner in dieser Zeit vom Haufen stoßen kann. Ergo berechne ich wie lange ein Angreifer benötigen würde um meinen Sandhaufen zu erklimmen. Dann schütte ich den Sandhaufen so hoch das man 200 Jahre benötigen würde um ihn zu erklettern.

Von vornherein ist klar das man den Sandhaufen erklimmen kann, es gibt also ein schon bekanntes Verfahren. Aber ich stelle nur sicher das man mit allen bekannten Verfahren während meiner 100 Lebensjahre nicht auf meinen Sandhaufen hinauf kommt.

Das einzige was einen Strich durch meine Rechnung machen könnte ist neues Wissen. Zb. die Erfindung des Helikopters der nun in Minuten Leute auf meinen Sandhaufen rauffliegen kann. Und exakt darum geht es wenn die Kryptographen fordern das alles an einem Kryptosystem öffentlich sein muß (also die Formeln etc.pp nicht die Passwörter . Denn unser zukünftiges Wissen ist es das unsere heutige Kryptographie brechen wird.

Als potentielle Faktorisierungsalgos. gelten das Quadratische Sieb QS, Elliptische Kurven Methode ECM, Field Number Sieve GNFS -> SNFS usw.

Allerdings gilt: heute sichere RSA Schlüssel können mit keinem der bekannten Verfahren in erträglicher Zeit mit erträglichen Aufwand geknackt werden.

Wenn dann sehe ich eher die Chance das die neusten Entwicklungen bei den Quantencomputern das ändern könnten. Aber nur dann wenn die Verfügbarkeit dieser Technologie eingeschränkt ist. Dh. der Angreifer hat diese Technologie und das Opfer muß weiterhin mit unserer heutigen Rechentechnik arbeiten. Sollten beide Seiten die gleiche Rechenpower haben dann egalisiert sich das wieder da nun der Komplexitätsfaktor der Trapdoorfunktion wieder wirkt. Also mit Quantencomputern auf beiden Seiten wird RSA wieder "unknackbar" der einzige Unterschied zu heuten RSA dürften die viel größeren Zahlengrößen, mit denen man dann rechnet, sein.

Gruß Hagen

[Bjoerk]

Gut, Programmtechnisch habe ich das so gemacht. Man könnte aber auch eine Tabelle erstellen und hieraus P und Q ablesen. Eine direkte Berechnung dafür gibt es nicht, da hast du völlig Recht.

[himitsu]

Zitat von Bjoerk:

Eine direkte Berechnung dafür gibt es nicht, da hast du völlig Recht.

Quasi eine Rainbowtable?

Sowas gibt's z.B. (teilweise) schon für MD5 und Co. wo man schon viele fertige "Passwörter" vorberechnet hat und man dann nur noch den MD5 Wert als Suchmuster, in dieser Tabelle nutzen muß.

Das Problem dabei sind aber die Datenmengen und die Zeit.
- man braucht etwas Zeit, um diese Tabellen zu erstellen
- und man braucht genügend Platz, um dieses zu speichern

Und bei den Unmassen an Primzahlen/Schlüsselgrößen kommt da so Einiges zusammen, wenn man "alle" möglichen Kombinationen berechnen und speichern will.