OSZ Handel 1
Informatik

RSA-Verfahren (Rechenbeispiel)

H. Haertl

[Home | Wirtschaftsgymnasium | Informatik | Unterrichtsmaterialien | Kryptographie]

page_dowm


Asymmetrische Verschlüsselung
über so genannte „Public-Key-Verfahren“

Bei diesen Verfahren wird im Gegensatz zum symmetrischen Verfahren mit einem Schlüsselpaar gearbeitet. Der eine bleibt völlig geheim (private key) der andere wird allgemein bekannt gemacht (public key) und steht jedermann zur Verfügung.

Will ein Absender dem Empfänger eine vertrauliche Nachricht senden, so verschlüsselt er diese mit dem public key des Empfängers. Anschließend ist nur dieser in der Lage mit Hilfe seines private key diese Nachricht wieder zu dechiffrieren.[1]

public key
des Empfängers

private key
des Empfängers

 

 

 

Beachte die elektronische Signatur wird dagegen mit dem privaten Schlüssel des Absenders chiffriert und diese kann nur mit dem öffentlichen Schlüssel des Absenders authentifiziert werden.

Das RSA-Verfahren

Diese Methode soll im Folgenden anhand des RSA-Verfahrens[2], das im Internet eine allgemeine Bedeutung erlangt hat, dargestellt werden. Die Sicherheit dieses Verfahrens beruht letztlich darauf, dass die Mathematik - trotz jahrhundertelanger Bemühungen - keine Formel gefunden hat, mit der Primzahlen einfach und schnell berechnet werden können. Nach wie vor stehen hier nur Probiermethoden zur Verfügung. Angesichts der riesigen Anzahl der durchzuprobierenden Zahlenwerte führen diese Probiermethoden bei entsprechend langen Schlüsselwerten nicht in vernünftiger Zeit zum gewünschten Ergebnis. 
(Nach den Abschätzungen der Mathematik gibt es vermutlich 10 mal mehr Primzahlen mit 512 bit Länge, als Atome im Universum.)
RSA-Verfahren Das kann kurz wie folgt beschrieben werden:[3]

Zutaten:
                                                             
öffentlicher Schlüssel zum Chiffrieren
(e : encrypt)


privater Schlüssel zum Dechiffrieren:
(d : decrypt) 

 p, q als zwei große Primzahlen

(e; n)                                                                     wobei n = p q
und e teilerfremd zu (p - 1)∙▪ (q - 1)
                                                                         mit de = 1 mod((p – 1) ▪ (q – 1))

Der Wert der jeweils zu chiffrierenden Zeichen z (z.B. Buchstaben) der Nachricht kann nun wie folgt chiffriert und dechiffriert werden:
Chiffrieren:         z' = ze mod n
Dechiffrieren:      z = z'd mod n

Zum besseren Verständnis ein einfaches Beispiel mit praxisfremden "kleinen" Primzahlen:

Klartext: H A L L O
ISO-Wert: 72 65 76 76 79

 

1. Man wählt zwei Primzahlen p und q Wir nehmen 11 und 17
2.  p und q werden miteinander multipliziert,
um n zu erhalten


n
= 11 x 17 = 187
3. Berechne die eulersche Phi-Funktion
   
phi(n) = (p – 1)(q – 1)

phi(n) = (11 – 1)(17 – 1) = 160
4.
 Berechne phi(n) + 1 phi(n) + 1 = 160 + 1 = 161
5. Der Wert e wird ausgewählt, wobei d ein Teiler aus phi(z)+1 sein muss. Der zweite Teiler aus phi(n)+1 ist d. Es muss gelten: d*e=phi(z)+1 . Unzulässige Werte von d und e (z.B. d=e) werden als unsicher abgelehnt.

da 161 = 7 x 23 (Faktorisierung)

sind 7 und 23 geeignete Kandidaten für e und d

Wir wählen e = 7 für den public key
und             d = 23 für den private key

6. Der Wert e wird zusammen mit n als öffentlicher Schlüssel definiert, der Wert d als privater Schlüssel. Der öffentliche Schlüssel, mit dem verschlüsselt wird, kann nun allgemein bekannt gemacht werden. Der private Schlüssel, muss geheim gehalten werden

der ganze public key besteht also aus zwei Zahlen, nämlich
( e; n), hier also (7; 187)

der ganze private key besteht dann dem entsprechend aus den Zahlen (d; n), hier also (23; 187)



Beim Chiffrieren und Dechiffrieren wird nun wie folgt verfahren:

Chiffrieren:        z‘ = zd mod n Dechiffrieren:     z = z’e mod n z sei der Dezimalwert des jeweiligen Zeichens; so hat z.B. dem Buchstabe „H“ im ISO-Zeichensatz der Wert 72 zugeordnet

 

 

H (72)    727 mod 187 = 30

A (65)    657 mod 187 = 142

L (76)    767 mod 187 = 32

L (76)    767 mod 187 = 32 

O (79)   797 mod 187 = 139

  3023   mod 187 = 72 ( H )

 14223   mod 187 = 65 ( A )

  3223   mod 187 = 76 ( L )

  3223   mod 187 = 76 ( L )

13923   mod 187 = 79 ( O )

 

Sind p und q genügend groß, benötigt nach dem gegenwärtigen Stand der Technik mehr als 1012 Jahre, in denen diese Nachricht wahrscheinlich wertlos geworden ist. Genau auf dieses Verfahren greift auch die digitale Signatur zurück, mit der zukünftig die Authentizität eines Dokumentes gerichtsverwertbar bewiesen werden kann.

[1] Quelle: http://www.oszhdl.be.schule.de/
[2] RSA (entwickelt 1977, von den Mathematikern Ron Rivest, Adi Shamir und Leonard Adleman am MIT)
[3] Quelle: http://www-aix.gsi.de


Letzte Änderung:   09. Januar 2006   
09. Januar 2006    Hartmut Härtl

page_top