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 Ver­schlüsselungsverfahren: Der Sender ver­schlüsselt den Klartext m mit dem öffentlichen Schlüssel (public key) e des Empfängers; der Empfänger ent­schlü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 Umkehr­funktion zu berechnen. Nur durch Kenntnis einer Hintertür (trapdoor) d lässt sich die Funktion wieder umkehren, d.h. der Geheimtext c wieder ent­schlü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 ver­schlü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 Ver­schlüsselung berechnet der Sender

c = me mod n

und erhält damit den Geheimtext c. 1)

 

Die Zahl n ist das Produkt von zwei ver­schiedenen 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 Primfaktor­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 teiler­fremden 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 Ent­schlü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 können beliebige Sender B eine Nachricht m verschlüsseln und an A als Empfänger schicken. Nur A kann mithilfe seines privaten Schlüssels d die ver­schlüsselte Nachricht c wieder ent­schlüsseln. Ein Dritter C kennt zwar n und e, kann aber dennoch c nicht ent­schlüsseln (außer mit undurch­führ­bar 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

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 Beispiele für Verfahren zur Faktorisierung von zusammen­gesetzten Zahlen folgen anschließend noch die Algorithmem Quadratisches Sieb und p-1-Methode.

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 Primfaktor­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.

Dies gilt jedoch nur "im allgemeinen". In speziellen Fällen sind andere Angriffe möglich.

p-1-Faktorisierung

Die Zahl n ist das Produkt zweier Primzahlen p und q. Weder p-1 noch q-1 dürfen aus zu kleinen Primfaktor­potenzen zusammen­gesetzt sein. Denn ansonsten lässt sich n mit der p-1-Methode von Pollard faktorisieren.

Low Exponent Attack

In der Frühzeit des RSA-Verfahrens wurde empfohlen, aus Gründen einer effizienten Ver­schlüsselung einfach den Exponenten e=3 zu wählen. Dies ist jedoch unsicher.

Angenommen, derselbe Klartext m wird an 3 verschiedene Empfänger geschickt, deren öffentliche Schlüssel (n, e) folgender­maßen lauten: (n0, 3), (n1, 3) und (n2, 3), und die ent­sprechenden Geheimtexte c0, c1 und c2 werden abgefangen. Dann lässt sich mithilfe des chinesischen Restsatzes der Klartext m berechnen.

Denn es gilt

m3  kongruent  c0 (mod n0)
m3  kongruent  c1 (mod n1)
m3  kongruent  c2 (mod n2)

Der chinesische Restsatz liefert dann eine eindeutige Lösung modulo n0·n1·n2 für m3. Durch Ziehen der dritten Wurzel ergibt sich der Klartext m.

Das Verfahren funktioniert entsprechend auch für andere kleine Exponenten e=5, e=7 usw. Ist jedoch der Exponent e groß, z.B. e=216+1, so müssten entsprechend viele Geheimtexte, die den gleichen ver­schlüsselten Klartext m darstellen, abgefangen werden. Eine ent­sprechende Implementierung findet sich unter Low-Exponent-Angriff.

Aufgabe 1:  Ein Klartext m wird mit folgenden öffentlichen Schlüsseln (n, e) ver­schlüsselt: (1357, 3), (1363, 3), (697, 3). Die ent­sprechenden Geheimtexte c sind 106, 953 und 101. Tragen Sie die drei Moduln 1357, 1363 und 697 sowie die drei Reste 106, 953 und 101 in das Berechnungsformular unten auf der Seite Chinesischer Restsatz ein und ermitteln Sie auf diese Weise m3. Ziehen Sie mit einem Taschen­rechner die dritte Wurzel und berechnen Sie so den Klartext m 2).

 

Beispiel

Anhand eines Zahlen­beispiels mit kleinen Zahlen lässt sich der Ablauf der Berechnungen der RSA-Ver­schlüsselung noch einmal nach­voll­ziehen.

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 ver­schiedenen 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

2)  Die Lösung m=339 ist richtig.

 

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 12.06.1997   Updated: 15.12.2016
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

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

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik