Kryptografische Protokolle

RSA-Verschlüsselung

 aufwärts

Das RSA-Verfahren ist nach seinen Urhebern Rivest, Shamir und Adleman [RSA 78] benannt. Es handelt sich um ein asymmetrisches Verschlüsselungs­verfahren: Der Sender verschlüsselt den Klartext m mit dem öffentlichen Schlüssel (public key) e des Empfängers; der Empfänger entschlüsselt das Ergebnis, den Geheimtext c, mit seinem zugehörigen privaten Schlüssel (private key) d.

Asymmetrische Verfahren beruhen auf dem Begriff der Einbahn­funktion oder Einweg­funktion (one way function) – hier realisiert dadurch, dass es leicht ist, c  =  me mod n zu berechnen, aber praktisch unmöglich, die Umkehrfunktion zu berechnen. Nur durch Kenntnis einer Hintertür (trapdoor) d lässt sich die Funktion wieder umkehren, d.h. der Geheimtext c wieder entschlüsseln.

 

Verschlüsselung

Der Klartext wird als Binärzahl m Element {0, ..., n-1} aufgefasst. Ist der Klartext zu lang, so wird er in mehrere Stücke zerlegt, die jeweils für sich verschlüsselt werden.

Es sind

n öffentliche Zahl
e öffentlicher Schlüssel des Empfängers
d privater Schlüssel des Empfängers
m < n   Klartext
c Geheimtext

Zur Verschlüsselung berechnet der Sender

c = me mod n

und erhält damit den Geheimtext c. 1)

 

Die Zahl n ist das Produkt von zwei verschiedenen Primzahlen p und q, diese sind geheim. Wie können p und q geheim sein, wenn doch n = pq öffentlich bekannt ist? Dies beruht nur darauf, dass die Prim­faktor­zerlegung von n zu rechen­aufwendig ist, da n sehr groß ist (z.B. 512 Bit lang).

Für die Zahl e muss gelten

ggt(e, φ(n)) = 1

Hierbei ist

φ(n)  =  (p-1)(q-1)

die Anzahl der zu n teilerfremden Zahlen, die kleiner als n sind.

 

Entschlüsselung

Der Empfänger hat als privaten Schlüssel eine Zahl d mit

d·e mod φ(n)  =  1 ,   d.h.

d·e  =  k·φ(n) + 1   für irgendein k Element natürliche Zahlen0

 

Ist n = pq, so gilt nach einem Satz von Euler für alle Zahlen m mit m < n und alle natürlichen Zahlen k :

mk·φ(n)+1 mod n  =  m

 

Zur Entschlüsselung berechnet der Empfänger

cd mod n   =  md·e mod n
   =  mk·φ(n) + 1 mod n
   =  m

und erhält damit den Klartext m.

 

Protokoll

Das folgende Bild 1 zeigt die Abfolge der Berechnungen und Daten­übermittlungen. A erzeugt zunächst die Zahl n sowie den öffentlichen Schlüssel e und den zugehörigen privaten Schlüssel d und veröffentlicht n und e.

Von diesem Zeitpunkt an kann ein beliebiger Sender B einen Klartext m verschlüsseln und an A als Empfänger schicken. Nur A kann mithilfe seines privaten Schlüssels d den Geheimtext c wieder entschlüsseln und den Klartext m zurückgewinnen. Ein Dritter C kennt zwar n und e, kann aber dennoch c nicht entschlüsseln (außer mit undurchführbar hohem Aufwand).

 

         AC          B
  
Schlüssel
erzeugen
 
wählt
   Primzahlen p und q
 
berechnet
   n = p·q   und
   φ(n) = (p-1)·(q-1)
 
wählt
   e mit ggt(e, φ(n)) = 1
 
berechnet
   d mit
   d·e mod φ(n) = 1
 
 
Schlüssel
veröffentlichen
 
n, e 
 Verschlüsseln
 berechnet
   c = me mod n
Geheimtext c 
Entschlüsseln 
berechnet
   m = cd mod n
 
Bild 1:  Verschlüsseln und Entschlüsseln mit dem RSA-Verfahren

 

Sicherheit

Um RSA zu knacken, müsste ein unbefugter Dritter versuchen, den privaten Schlüssel d aus dem öffentlichen Schlüssel e zu berechnen oder φ(n) irgendwie zu bestimmen. Es lässt sich zeigen, dass beides mindestens so schwer ist, wie die Prim­faktor­zerlegung n = p·q zu berechnen. Dieses ist nach heutiger Kenntnis zu rechen­aufwendig. Auch direkt die e-te Wurzel aus c zu berechnen (modulo n) ist zu rechen­aufwendig.

 

Effizienz

Für das Verständnis der Korrektheit und Effizienz des RSA-Verfahrens werden einige zahlen­theoretische Grundlagen und Berechnungs­verfahren gebraucht.

Zu diesen Berechnungs­verfahren gehört ein Algorithmus für die modulare Exponentiation (um etwa me mod n zu berechnen), der erweiterte euklidische Algorithmus (um einen privaten Schlüssel d mit d·e mod φ(n) = 1 zu berechnen) sowie ein Algorithmus zur Berechnung von großen Primzahlen (um p und q zu erhalten). Als Beispiel für ein Verfahren zur Faktorisierung einer zusammen­gesetzten Zahl folgt anschließend noch der Algorithmus Quadratisches Sieb.

 

Beispiel

Anhand eines Zahlen­beispiels mit kleinen Zahlen lässt sich der Ablauf der Berechnungen noch einmal nachvollziehen.

Schlüssel erzeugen

Der Empfänger A veröffentlicht als öffentlichen Schlüssel zwei Zahlen n und e. Hierbei ist n das Produkt von zwei verschiedenen Primzahlen p und q:

p:       

q:       

n:  

   φ(n):  

Für e wählt A eine Zahl mit ggt(e, φ(n)) = 1:

e:       

Hieraus ergibt sich der private Schlüssel d mit d·e mod φ(n)  =  1:

d:  

 

Als öffentlichen Schlüssel veröffentlicht A also (n, e) = (55, 3); den privaten Schlüssel d hält A geheim.

 

Verschlüsseln

Der Sender B möchte eine Nachricht m an A schicken:

m     

und berechnet c  =  m e mod n:

c:  

 

Somit sendet B den Geheimtext c = 9 an A.

 

Entschlüsseln

Der Empfänger A berechnet m  =  c d mod n:

m

und erhält somit den Klartext m = 4 zurück.

 

Literatur

[BNS 05]A. Beutelspacher, H.B. Neumann, T. Schwarzpaul: Kryptografie in Theorie und Praxis. Vieweg (2005)
[Bu 00]J.A. Buchmann: Introduction to Cryptography. Springer (2000)
[RSA 78]R.L. Rivest, A. Shamir, L.M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21, 2, 120-126 (1978)
[Lan 06]H.W. Lang: Algorithmen in Java. 2. Auflage, Oldenbourg (2006)

Das RSA-Verfahren finden Sie auch in meinem Buch über Algorithmen.
Weiterevertikaler Abstand Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphen­algorithmen, Arithmetik, Codierung, parallele Sortier­algorithmen.
[Weitere Informationen]   [Bestellen]

Buch  

 


1)  Die Funktion mod liefert den Rest bei ganzzahliger Division

 

Weiter mit:   [Diffie-Hellman-Schlüsselvereinbarung]   oder   up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 12.06.1997   Updated: 02.05.2012
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik