RSA: Privaten Schlüssel schneller berechnen

[negaH]

Zitat:

aus E^-1? Aber E^-1 ist ja meist keine natürliche Zahl.

Falsch bzw. richtig

Also nochmal

1 = D * E mod Phi(N) -> D = E^-1 mod Phi(N).

Wir arbeiten hier immer in Modularen Ringen und somit sind alle Resultate ganze Zahlen. Da das Modul Phi(N) und N positive Zahlen sind könnte man das sogar einschränken auf die natürlichen Zahlen, sprich ganze positive Zahlen.

Das was dich nun stört ist die separate Betrachtung von E^-1. Als einfache Operation betrachtet ist es richtig was du sagst, eine reelle Zahl. Aber wir arbeiten ja modular mod Phi(N) und somit muß D = E^-1 mod Phi(N) dann ebenfalls eine postive ganze Zahl zwischen 0 und Phi(N) -1.

Die Inversion einer Zahl in einem Modularen Ring ist dabei aber nur unter bestimmten Umständen definiert. Wenn das Modul N oder Phi(N) teilerfremd zu E ist so können wir definitiv das modulare multiplikative Inverse berechnen.

Mit Hilfe des erweiteren ggT() können wir nun direkt aus E,Phi(N) dessen inverses E^-1 berechnen und dies alles im Zahlenbereich der ganzen Zahlen.

Gruß Hagen