RSA verschlüsselung (problem mit aufgabe)
 

hallo

hab da eine aufgabe die ich lösen soll, weiß aber nicht
wie ich an die sache am besten rann gehen soll

und zwar:

gegeben ist eine rsa verschlüsseung mit n = 119 und e = 5
Ich soll hiermit die nachricht m = 19 verschlüsseln


danach soll ich prüfen welcher der entschlüsselungsschlüssel
6,19 oder 77 bei der entschlüsselung des gerade berechneten
geheimtextes c wieder die Nachricht m = 19 ergibt.

---Parameter--------Wert
______________________________
-------n--------119
-------e--------5
-------d--------6-----19--77



kann mir vielleicht jemand ein par tipps geben
wie ich das prob. lösen könne
oder wie ich an die schache rann gehen soll ??



gruß
fenster

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.

oder auch

pong

weiter info dazu
 

hallo

habe da noch weitere info zu diesem thema



http://berg.heim.at/anden/421355/rsa_info.gif

gruß
fenster