Hacken bei RSA-Verfahren

[negaH]

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.

[Meisterschmied]

Hi Hagen,

also, ich hab mal alle Berechnungen von D mal zusammengetragen, und es ist in keinem Fall irgendetwas sinnvolles herausgekommen. Wie muss ich denn den Erweiterten Euklidischen Algorithmus umschreiben, damit er mir die richtigen Zahlen rausgibt. Hab dazu schon einmal einen Thread angelegt:

http://www.delphipraxis.net/internal...ct.php?t=13410

Hast du eine Idee, bzw. wie hast du es implementiert :?:

Thanks,

Wieland

PS: Vergiss die Library nicht :-D

[negaH]

Zitat:

PS: Vergiss die Library nicht

Jay, bin gerade wieder online, nachdem ich in den letzten zwei Tagen mein System reparieren durfte (unfreiwillig). Nachdem ich SP4 drauf installiert hatte konnte mein RAS Dienst nicht mehr hochfahren, also auch kein Internett. Jetzt bin ich erstmal glücklich und werde meine CPU/CD-ROM's abkühlen lassen. Soll heissen bis morgen, eventuell übermorgen musst du dich noch gedulden müssen, sorry.

Gruß Hagen