RSA Verschlüsselung Problem

Also ich hab da ein Problem:

Es geht um die RSA Verschlüsselung und das Beispiel aus der MacLife. Es ist wie folgt:

Primzahlen:

p=7
q=17

Das Produkt n ist:

n=7*17=119


Danach werden die zwei Natürlichen Zahlen e und d bestimmt.

e*d = s*(p-1)(q-1)+1
e*d = s* (7-1)(17-1)+1
e*d = s*6*16+1
e*d = s*96+1
5*77 = 4*96+1
5*77 = 385

Daraus folgt:

e = 5
d = 77
n = 119

Öffentlicher Schlüssel: d und n
Privater Schlüssel: e und n

Soweit ist auch alles kein Problem. Das kommt jetzt. die folgende Nachricht soll verschlüsselt werden, wobei festgelegt ist was welche Zahle bekommt:

A = 3
B = 4
C = 5

Am Beispiel A wird dann folgendes berechnet:

x = 3e MOD n
x = 35 MOD 119
x = 243 MOD 119 (ÄH?)
x = 5 (Nochmal ÄH?)

MOD soll hierbei bedeuten das quasi solange 119 abgezogen wird bis ein Rest bleibt, der kleiner als 119 ist.(wieder ÄH?)

So kommt dann für die werte ABC folgendes raus(wenn der schritt wiederholt wird):

A = 3 ergibt 5
B = 4 ergibt 72
C = 5 ergibt 31

Es geht noch weiter. aber das lass ich erstmal weg. Überall wo ÄH? steht komm ich nicht weiter.

Wenn mir das jemand erklärt kommt die Entschlüsselung.



B

 

Hallo,

ich hab den MacLife Artikel nicht gelesen. Ich kann aber trotzdem versuchen, dir den RSA zu erklären.

Du möchtest also an X eine Nachricht verschicken.
Dazu brauchst du den öffnetlichen Schlüssel von X
c und n.

Diese berechnet X folgendermasen:

Er wählt zwei Primzahlen. Du sagtest ja p = 7 und q=17
=> n =7*17 = 119
dann mach er die Faktorzerlegung nach
f=(7-1)*(17-1)=96 => zerlegung: 2*2*2*2*2*3
und sieht, dass er als öffentlichen Schlüssel c z.B. 5 verwenden kann, da teilerfremd zu f=96.

er schickt dir also n=119 und c = 5

damit kannst du jetzt verschlüsseln nach der Formel:
VerschlüsseltesZeichen = Zeichen^c mod n

Du möchtest also verschlüsseln: A=3 B=4 und C=5
also rechnest du:
3^5mod119 = 5
4^5mod119 = 72
5^5mod119 = 31 (5^3 = 3125, 3125mod119 = 31)
(Modulo (mod) ist übrigens der Rest, den erhältst, wenn du durch eine Zahl teilst
also 5mod2 = 2 Ganze, Rest 1
5mod2 = 1
20mod4 = 5 Ganze, Rest 0
20mod4 = 0
)
also schickst du an X die Zeichenfolge: 5,72,31

Verschlüsselung ist fertig!!!

---
Rauchen die Köpfe? Dann geht's jetzt weiter:

X möchte jetzt die Nachricht 5,72,31 entschlüsseln.
Er kennt seine privaten Primzahlen p = 7, q=17 und n=119 und natürlich seinen öffentlichen Schlüssel c = 5

Jetzt muss er als erstes seinen privaten Schlüssel d ausrechnen!!!!!! d=(k*f+1)/c mit f ist (p-1)*(q-1) = 96 und c =5
d=(k*96+1)/5 =Ganzzahl; da muss man nen bisserl probieren (kann ein Computer ja ganz gut) und man erhält z.B. mit Hilfe von Excel: d=77 bei k=4
(man erhält aber auch noch andere Lösungen, z.B mit k=9 ehält man d = 173 usw.)

und jetzt rechnet X einfach aus 5,72,31 mit Hilfe von d:

Zeichendecodiert = Zeichencodiert^d mod n

also:
5^77mod 119= 3
72^77mod119 =4
31^77mod119=5

> ABC

Nachricht decodiert.

Achja, 5^77mod119 kann man nicht ganz so einfach ausrechnen. Man muss erst zerlegen: z.B. 5^77mod119=(5^35mod119)*(5^35mod119) usw. bis genügend kleine Zahlen herauskommen.

Das ganze wird in der praxis noch ziemlich komplex. Man verwendet für p und q übrigens ab 150 Stellen große Primzahlen!!! Der RSA Code wäre also einfach zu knacken, es fehlt halt nur an ausreichender Rechenpower!!!

 

tsts....

Hätten die auch gleich so schreiben sollen. So versteht man den Kram.

Dank

B

PS: Für die, die immer noch Bahnhof verstehen:

3125-(119*26)=31

 

Mein Texas Instruments 92 (TI-92) kann das aber !!



B