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 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 verschlüsselte Nachricht c 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

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 Beispiele für Verfahren zur Faktorisierung von zusammengesetzten 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 Primfaktorzerlegung n = p·q zu berechnen (siehe Äquivalenz zwischen Faktorisierung von n und Berechnung von φ(n)). Dieses ist nach heutiger Kenntnis zu rechenaufwendig. Auch direkt die e-te Wurzel aus c zu berechnen (modulo n) ist zu rechenaufwendig.

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 Primfaktorpotenzen zusammengesetzt 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 Verschlü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) folgendermaßen lauten: (n0, 3), (n1, 3) und (n2, 3), und die entsprechenden 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 verschlüsselten Klartext m darstellen, abgefangen werden. Eine entsprechende Implementierung findet sich unter Low-Exponent-Angriff.

Aufgabe 1:  Ein Klartext m wird mit folgenden öffentlichen Schlüsseln (n, e) verschlüsselt: (1357, 3), (1363, 3), (697, 3). Die entsprechenden 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 Taschenrechner die dritte Wurzel und berechnen Sie so den Klartext m 2).

 

Beispiel

Anhand eines Zahlenbeispiels mit kleinen Zahlen lässt sich der Ablauf der Berechnungen der RSA-Verschlüsselung 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

Lesenswert ist der Originalartikel
[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)
Ansonsten findet sich das RSA-Verfahren in jedem Fachbuch über Kryptografie, so beispielsweise in
[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)
[Ert 12]W. Ertel: Angewandte Kryptographie. 4. Auflage, Hanser (2012)
[KK 10]C. Karpfinger, H. Kiechle: Kryptologie. Vieweg+Teubner (2010)
[PP 10]C. Paar, J. Pelzl: Understanding Crytography. Springer (2010)
[Schm 16]K. Schmeh: Kryptografie. 6. Auflage, dpunkt (2016)
[SSP 08]J. Swoboda, S. Spitz, M. Pramateftakis: Kryptographie und IT-Sicherheit. Vieweg+Teubner (2008)
[Lan 18]H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[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   Datenschutz   ©   Created: 12.06.1997   Updated: 14.03.2019
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