Zitat:
1) Ich verstehe zwar den Sinn nicht so ganz, aber da A und B ja auf jeden Fall keine Primzahlen sind, ist PHI(A) mit Sicherheit nicht A-1, sondern ein sehr viel kleinerer Wert. Bzw. es ist die Anzahl der ganzen Zahlen a, für die gilt, dass gcd(A,a)=1. Jetzt müsste doch PHI(A,B) = PHI(A)*PHI(B), oder?
Nein
Worauf ich hinauswollte ist das man A und B in Primzahlen faktorisieren muss. Nun hat man alle Restklassen Ringe ermittelt. Angenommen A zerfällt in 3 Primzahlen P1,P2,P3 und B zerfällt in 2 Primzahlen P4,P5. Die Potenzen dieser Primzahlen die eventuell in A,B auftreten können spielen dabei keine Rolle. Nun wird Phi(P1, P2, P3, P4, P5) berechnet, und wir bekommen die Anzahl der Elemente im Set zu N = A * B. Wichtig dabei ist aber zu erkennen das GCD(A, B) = 1 sein kann obwohl A und B KEINE Primzahlen sind, sie sind eben NUR teilerfremd zueinander. D.h. PHI() ist NICHT abhänig vom GCD().
Indirekt kommen wir damit zur Frage 2.
Zitat:
2) Weil E*D == 1 mod n nur lösbar ist, wenn gcd(E,D) = 1. Man muss doch aber nicht überprüfen, ob GCD(E, N) = GCD(D, N) = 1, denn das wird ja dadurch impliziert, dass p und q Primzahlen sind. Aber E und D sind ja kleiner als P und Q, also muss GCD(E, N) = GCD(D, N) = 1 gelten
Eben nicht
wenn N = P * Q, und E,D = Q oder P ist dann ist der GCD() = Q oder P !
Wenn Q,P KEINE Primzahlen sind, weil zB. der Primzahl Erzeugungs Algo Rabin Miller ist, dann besteht wenn auch sehr gering die Möglichkeit das N sich in mehr als zwei Primzahlen zerlegen lässt. Eine Überprüfung mit GCD(D, N) = GCD(E, N) = 1 ist also für RSA absolut notwendig. Es sei denn man stellt sicher das E,D <> P,Q sind. Man verbaut sich dann aber die algorithmische doppelte Absicherung das alle Parameter vom RSA sicher sind.
E,D sind Elemente im Ring P*Q bei RSA. Ok, man bevorzugt E möglichst klein, aber D ist echtes Element von N und sollte dies aus Sicherheitsgründen sogar immer sein. D.h. D sollte bei einem 1024 Bit N ebenfalls ca. 1024 Bit groß sein. Bedenke D ist der Entschlüsselungsexponent, und sollte so groß wie möglich sein. Auf sehr kleine D's wären Brute Force Angriffe möglich !!
Gruß Hagen
PS: am Wochenende maile ich dir meine Library. Enhalten sind auch einige RSA Varianten die du durchtesten kannst.