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üsselungsverfahren: 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 Einbahnfunktion oder Einwegfunktion (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 = p·q öffentlich bekannt ist? Dies beruht nur darauf, dass die Primfaktorzerlegung von n zu rechenaufwendig 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. Diese Vorbereitungen sind nur einmalig zu treffen.

Danach kann ein beliebiger Sender B eine Nachricht verschlüsseln und an A als Empfänger schicken. Nur A kann mithilfe seines privaten Schlüssels d die verschlüsselte Nachricht wieder entschlüsseln. Ein Dritter C kennt zwar n und e, kann aber dennoch c nicht entschlüsseln (außer mit undurchführbar hohem Aufwand).

 

             A C              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: Erzeugen der Schlüssel sowie Ver- 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 Primfaktorzerlegung n = p·q zu berechnen. Dieses ist nach heutiger Kenntnis zu rechenaufwendig. Auch direkt die e-te Wurzel aus c zu berechnen (modulo n) ist zu rechenaufwendig.

Effizienz

Für das Verständnis der Korrektheit und Effizienz des RSA-Verfahrens werden einige zahlentheoretische Grundlagen und Berechnungsverfahren gebraucht.

Zu diesen Berechnungsverfahren 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 zusammengesetzten Zahl folgt anschließend noch der Algorithmus Quadratisches Sieb.

Beispiel

Anhand eines Zahlenbeispiels 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 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das RSA-Verfahren finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphenalgorithmen, Arithmetik, Codierung, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

1)  Die Funktion mod liefert den Rest bei ganzzahliger Division

 

Weiter mit:   [Diffie-Hellman-Schlüsselvereinbarung]   oder   up

 

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


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot:

Web- und Softwaretechnologie

Ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien...

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Und ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten IT-Sicherheit, Mobile Computing und Human-Computer Interaction...

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnologie

Wirtschaftsinformatik