Es gibt keine bekannte, einfache Möglichkeit D, P, oder Q zu errechnen wenn nur PQ und E (also der öffentliche Schlüssel) bekannt sind.
Fangen wir also mal ganz am Anfang an. Wie funktioniert die RSA-Verschlüsselung:
----------------------------------------------------------------------
- Wähle P und Q als Primzahlen.
- Wähle E so, dass E grösser als 1 aber kleiner als PQ ist, wobei E und (p-1)*(Q-1) relativ prim zueinander sein müssen. (E muss ungerade sein da (P-1)*(Q-1) gerade ist)
- Errechne einen Wert D der die Gleichung (DE-1) mod (P-1)(Q-1) = 0 erfüllt. Das kann man auch DE = 1 (mod (P-1)(Q-1)) schreiben. Das macht man indem man sich eine ganze Zahl X sucht mit der die Gleichung D=(X(P-1)(Q-1)+1)/E wahr ist. Schon hat man einen Wert für D.
- Um etwas zu verschlüsseln setzt man in folgende Gleichung ein wobei T der zu verschlüsselnde Wert und C der Verschlüsselte Wert ist: C=(T^E) mod PQ
(das funktioniert natürlich nur wenn der zu verschlüsselnde Wert T kleiner als PQ ist)
- Um etwas zu entschlüsseln setzt man in diese Gleichung ein: T=(C^D) mod PQ
Der öffentliche Schlüssel ist das Paar (PQ, E). PQ wird übrigens auch oft als N bezeichnet.
Der private Schlüssel ist die Zahl D.
----------------------------------------------------------------------
Wenn man sich das so ansieht heisst es also wohl oder übel probieren. Da wir in diesem konstruierten Fall nur drei mögliche Schlüssel zur Auswahl haben würde ich so vorgehen:
Verschlüsseln
--------------------
C = (T ^ E) mod PQ
C = (19 ^5) mod 119
C = 66
Entschlüsseln:
--------------------
T = (C ^ D) mod PQ
19 = (66 ^ D) mod 119
19 != (66 ^ 6) mod 119
19 != (66 ^ 19) mod 119
19 = (66 ^ 77) mod 119
Der gesuchte, private Schlüssel ist also 77.
Wenn wir keine Schlüssel vorgegeben hätten wäre die Sache schon interessanter. Wir bräuchten dann nämlich P und Q. In unserem Fall ist das noch recht einfach. Ich wollte nicht viel denken und habe deshalb in VBA folgendes produziert:
Public Sub SearchPQ()
Const PQ As Integer = 119
For P = 2 To PQ - 1
If 119 Mod P = 0 Then
Debug.Print P & vbTab & 119 / P
End If
Next
End Sub
Das hat mir meine Primzahlen zu P=7 und Q=17 geliefert.
In den Grundlagen ganz zu Beginn hatten wir folgende Formel:
(DE-1) mod (P-1)(Q-1) = 0
Der Modulo stört mich ein wenig beim Umformen. Also schreiben wir die Sache mal als:
(DE-1) = K * (P-1)(Q-1)
oder auch:
DE = K * (P-1)(Q-1) + 1
bzw. nach D aufgelöst:
D = (K * (P-1)(Q-1) + 1) / E
Um mein Hirn zu schonen muss jetzt wieder VB dran glauben:
Public Sub SearchD()
Const P As Integer = 7
Const Q As Integer = 17
Const E As Integer = 5
Phi = (P - 1) * (Q - 1)
K = 1
Do Until K = Phi Or D >= (Phi - 1)
D = (K * Phi + 1) / 5
If D = CInt(D) Then
Debug.Print D
End If
K = K + 1
Loop
End Sub
Damit bekomme ich jetzt alle möglichen Werte für D. Welcher Wert der richtige ist würden dann wieder Versuche mit ver- und entschlüsseln einer kurzen Nachricht erbringen. In unserem Fall bekomme ich aber nur 77. Weiteres überlegen können wir uns also hier schenken.
Falls du dich für die Details der Mathematik im Hintergrund von RSA interessierst, wirst du im Internet haufenweise Infos finden.
Suche zum Beispiel nach der "totient function". Das dürfte einige Ergebnisse bringen da die Eulersche Totient- bzw. auch Phi-Funktion einer der Grundsteine für die RSA-Verschlüsselung ist.
|