Folgende Überlegungen lassen es nicht aussichtslos erscheinen, mit dem Diffie-Hellman-Hack auch RSA zu entschlüsseln.

\n

Bei der Modulo-Berechnung lässt sich phi schätzen und als Exponent testen zum öffentlichen Schlüssel als Basis.

\n

Bei diesem Verfahren ist es nicht erforderlich, k*m+1 bzw. in der Notation unten phi1*v zu kennen, da der inverse Charakter bei dem korrekten Exponenten injedem Fall sichtbar wird.

\n

Also z.B. auch der aus 9*3588 (phi im Beispiel  modulus 3713, öffentlicher Schlüssel 37) errechnet Wert für phi den öffentlichen Schlüssel bilden kann, z.B.

\n

32292 = 9*3588+1 = 43 *751 = phi1

\n

Es ist dann nicht erforderlich, das Vielfache 9 (k) von m bzw phi1 zu kennen, da mit der Basis 43 oder 751 und phi selbst ohne Vielfaches immer modulo n (3713) das invers - Ergebnis vorliegt (also 1). Dadurch lässt sich immer ein Exponent wählen, der kleiner als der modulus und besser faktorisierbar ist, zudem  geschätzt werden kann über die Quadratdifferenz, wobei gilt, dass die untere Quadratbasis gleich ist, die obere Quadratbasis um 1 oder 2 (je nach gerade oder ungerade) unter der von p liegt.

\n

Bei 3713 zB. 61^2 - 8 = 3713 (ca 61^2 - 3^2) = ca 58* 64 = 3712

\n

; also 60^2 - 8 ca 60^2 - 3^2 = 57 * 63 => phi größer als 56 * 62 =  3472  und kleiner als 3592 (3600 - 8). die Differenz (Summe eines Faktors von phi und eines Faktors von p) ist entsprechend mindestens 121. usw. (das Beispiel ist ohnehin zu klein; Differenz ist hier 125 = 78 + 47 und Faktoren von phi(p) = 46*78 = 3588

\n

Entscheidend ist, dass der öffentliche Faktor (Exponent ) 43 oder (oder 751) aus 32292 = 9*3588+1 auch mit 3588 mod 3713 = 1 ist, auch wenn er kein Teiler von 3589 (phi +1 , quasi k = 0) ist.

\n

z.B. lässt sich mit einem schlichten Pythonprogramm der modulo 3713 Wert von Basis43 mit Exponent 3588 berechnen:

\n

0, z, k, zyp, testz 3588 598 6
gerade aw, ba, z, modz, modzn, x 1082 43 3588 1 1 2

\n

entweder im Standardverfahren oder mit einer Zerlegung des Exponenten in 43^598 mod 3713 als einmalig berechneter Wert W statt 43^3588 dann nur W^6 mod 3713.

\n

Durch die Äquivalenz von a^(i*j) mod c und (a^1 mod c)^j)mod c lassen sich die Exponenten einigermaßen gut testen

\n

Genaueres für angemessen große Zahlen folgt - die Größe des modulus ist entsprechend entscheidend, allerdings muss die Entschlüsselung noch einigermaßen unaufwendig möglich sein, d.h. der geheime Schlüssel kann nicht 'unendlich' viele Stellen haben - die übliche Größe der Exponenten

\n

Die als sicher geltende Länge des geheimen Schlüssels ist 2^64 - also höchstens 19 Stellen- , der öffentliche Schlüssel ist üblicherweise größer/gleich  2^16 +1, also fünf Stellen.

\n