RSA: Privaten Schlüssel schneller berechnen

[Bjoerk]

Du kennst dich da mit Sicherheit besser aus als ich, ein Vorteil dabei ist m. E. jedoch nicht von der Hand zu weisen: Es gibt dann mehrere Möglichkeiten, aus denen sich N zusammensetzen kann, was den Hackeraufwand erheblich verlängern dürfte.

[negaH]

Zitat von Bjoerk:

Du kennst dich da mit Sicherheit besser aus als ich, ein Vorteil dabei ist m. E. jedoch nicht von der Hand zu weisen: Es gibt dann mehrere Möglichkeiten, aus denen sich N zusammensetzen kann, was den Hackeraufwand erheblich verlängern dürfte.

Ne eben nicht, das Gegenteil wäre der Fall. Je zusammengestzter N ist desto kleiner werden seine Primzahlpotenzen der Faktorisation und das würde bedeuten das umgekehrt exponentiell die Geschwindigkeit des Knackens wächst. Es erleichtert also das Knakcen von RSA da es gerade an dem Punkt wodurch RSA erst sicher wird eine Schwäche einbaut.

Es gibt/gab Versuche mit RSA in dieser Richtung weil man damals wollte das die RSA Operationen schneller ablaufen. Das ist auch der Fall da man mit solchen RSA Schlüssel und dem CRT (Chinese Remainder Theorem) besonders die Entschlüsselung beschleunigen kann. Bei RSA mit 2 Primzahlen im N kann man mit dem CRT (Garner Algorithmus) die Entschlüsselung um Faktor 4 beschleunigen. Das steigert sich je mehr Primzahlen man im Modul N benutzt.

Und es gibt tatsächlich Algorithmen die die sich ergebenden Schwächen bei der Benutzung vom mehr als 2 Primzahlen so ausgleichen können das dieser RSA Schlüssel nicht ganz so unsicher ist als wenn man wahlfrei mit mehr als 2 Primzahlen arbeitet. Denoch sind solche Schlüssel eben weniger stark als diejenigen die mit 2 etwa gleichgroßen, zufällig gewählten Primzahlen arbeiten. Da die Rechentechnik aber fortgeschiritten ist, der Schlüsselerzeugungprozess offline und nicht zeitkritisch ist, man heute ohne Probleme im Millisekundenbereich 512 Bit Primzahlen erzeugen kann, sind diese speziellen RSA Varianten überflüssig geworden.

Gruß hagen

[Bjoerk]

Okay. Aber mal was anderes. Wenn man mit mehr als 2 Primzahlen arbeiten möchte, ist das Procedere dann analog, also N=P*Q*R M:=(P-1)*(Q-1)*(R-1) usw. ?

[gammatester]

Der Standard RFC 3447 - PKCS #1: RSA Encryption Version 2.1 (Abschnitt 3.2) nimmt hier die Carmichaelfunktion M = lambda(N), wobei in Deinem Fall, wenn P,Q,R paarweise verschiedene Primzahlen sind, lambda(N) = LCM(P-1,Q-1,R-1) das kleinste gemeinsame Vielfache ist.

[negaH]

Zitat von Bjoerk:

Okay. Aber mal was anderes. Wenn man mit mehr als 2 Primzahlen arbeiten möchte, ist das Procedere dann analog, also N=P*Q*R M:=(P-1)*(Q-1)*(R-1) usw. ?

Ja genauso aber man muß sicherstellen das alle drei Primzahlen unterschiedlich sind. Angenommen zwei Primzahlen wären gleich dann ergibt sich N = P^2 * Q, und das wäre wiederum eine sehr schlechte Idee Es gäbe dann wieder bessere Faktorisierungsverfahren. Letzendlich ist das exakt das was Gammatester meinte.

Gruß Hagen