RSA einfach erklärt – Teil 1

Einführung

Es gibt viele Gründe, warum man sich mit Kryptographie beschäftigen sollte. Sie sollte im Zeitalter der Digitalisierung genauso wie das Lesen und Schreiben zum Allgemeinwissen gehören. Bedauerlicher Weise ist die Kryptographie nicht Bestandteil der Lehrpläne in Schulen.

Die Kryptographie ist ein interdisziplinäres Feld der Mathematik, welche sich der Resultate aus verschiedenen Zweigen der Mathematik (Algebra, Zahlentheorie, Komplexitätstheorie usw.) bedient und einen sicheren Gebrauch des Internets ermöglicht. Daher gehören Grundkenntnisse der Kryptografie zur heutigen digitalen Allgemeinbildung. Ohne dieses Wissen läuft man Gefahr als „digitaler Analphabet“ zu Enden.


In meinem letztem Blogartikel habe ich das Diffie-Hellman-Verfahren beschrieben und erläutert, warum deren Konzept ein neues Zeitalter für die Kryptographie und das Internet einläutete. Sie konnten Beweisen, dass es eine Lösung für das Problem der Schlüsselverteilung existiert. Was noch fehlte, war ein funktionierendes System. Sie hatten zwar ein Konzept aber noch keine praktische Implementierung. Natürlich machten sich Diffie und Hellman auf der Suche nach einer geeignetem asymmetrischen Verschlüsselungsverfahren aber ebenso auch andere Teams von Mathematikern, Informatikern und Kryptographen. Die beiden konnten die Entdeckung jedoch nicht machen.
Sie wurden in diesem Wettlauf von einem anderem Forscher-Trio überholt. Das Trio waren R. Rivest, A. Shamir und L. Adleman im Jahr 1977 und das Verschlüsselungsverfahren nennt sich RSA. Der Name RSA steht für die Anfangsbuchstaben ihrer Familiennamen und wurde 1983 zum Patent angemeldet, welches am 21. September 2000 erlosch. RSA war und ist bis heute ein de facto Standard für sämtliche vertrauliche Nachrichten. Natürlich sind noch weitere asymmetrische Verschlüsselungsverfahren hinzugekommen, aber RSA ist der wichtigste und am verbreiteste von allen. Dieser Blogartikel hat das Ziel, RSA einfach zu erklären.

Wie funktioniert die RSA-Verschlüsserlung?

Ich möchte mit einem einfachen Beispiel anfangen und danach den Algorithmus qualitativ beschreiben. Der Vorteil dieses Vorgehens ist, dass einfacher wird das RSA-Verfahrens zu erklären. Hier das Beispiel:

SchrittAliceÖffentlicher KanalBob
1Alice wählt zwei verschiedene Primzahlen, z.B. p=7 und q=11.  
2Alice berechnet n=p·q=77 und
m=(p-1) · (q-1)=60.
  
3Alice wählt eine Zahl e, welche zu m Teilerfremd ist, z.B. e=13.   
4 Alice veröffentlicht n und a als öffentlichen Schlüssel:
n=77 und e=13
 
5  Bobs Nachricht x ist eine Zahl, welche kleiner sein muss als n, z.B. x=5.
6  Bob verschlüsselt seine Nachricht wie folgt:
y=xa mod n·y=513 mod 77
y=1220703125 mod 77
y=26+15853287·77
y=26 
7 Bob sendet seine geheime Nachricht y=26 an Alice. 
8Alice berechnet aus a und m das multiplikative Inverse a mod m:
b=e-1 mod m·b=13-1 mod 60
b=37weil e·b=37·13 =481=8·60+1 e·b=1 mod 60
  
9Alice kann Bobs Nachricht wie folgt entschlüsseln:
x=yb mod n = 2637 mod 60
x=5
  

Warum funktioniert die RSA-Verschlüsselung?

Wenn man sich die Nachricht  anguckt, würden man im ersten Schritt sofort intuitiv handeln und nach einem d suchen welches  erfüllt. Wo ist also das Problem? Genau das ist das Problem. Dieses d allein aus den gegebenen Informationen  und zu ermitteln ist ein „schwieriges mathematisches Problem“, welches „diskreter Algorithmus“ genannt wird.  Unter einem „schwierigem mathematischen Problem“ versteht man, dass es bisher keinen „schnellen“ Algorithmus gibt, welcher in der Lage wäre, solch eine Zahl allein aus  und  zu ermitteln. Es existieren zwar einige Algorithmen mit denen dies effizienter ermittelt werden kann als nur bloßes ausprobieren von Zahlen (Brute Force) aber selbst diese Algorithmen spielen praktisch keine Rolle, da sie zu langsam sind. Was bedeutet zu langsam? „Langsam“ bedeutet, dass bei geschickt gewählten Schlüssellänge die Berechnung des „diskreten Algorithmus“ genau so lange mit einem Supercomputer dauern würde, wie das Universum alt ist. Warum ist Alice trotzdem in der Lage diesen „diskreten Logarithmus“ effizienter als Bob zu bestimmen? Um dies zu verstehen, muss bewiesen werden, dass wenn Alice  bestimmt (und das kann Alice, wenn ihr die Kenntnis von  bekannt ist), sie dann die Nachricht mittels  schnell berechnen kann. Schnell bedeutet in wenigen Bruchteilen einer Sekunde. Zu beweisen, dass RSA funktioniert, bedeutet nichts Weiteres als die Gültigkeit der Gleichung zu beweisen. Wie immer werde ich den Beweis nur kurz skizzieren. Wer tiefer in die Mathematik einsteigen möchte, empfehle ich die folgende ([1], [2], [3] und [4]) Literatur.

Wir haben folgende Gleichung, die es zu beweisen gilt:

Da d das multiplikativ Inverse zu e ist, folgt dass es ein  geben muss, so dass  bzw. . Daraus ergibt sich:

Wenn jetzt  und  teilfremd sind (also ihr größter gemeinsamer Teiler 1 ist), gilt der Satz von Euler-Fermat:

Satz (Euler-Fermat): Sind  und  teilfremde Zahlen mit , dann gilt

 ist die Anzahl der zu n teilfremden Zahlen. Dabei gilt, dass wenn p und q Primzahlen sind, dann  und  sein muss, so dass  ist. Der Beweis zum Satz vom Euler-Fermat lässt sich hier [] einsehen. 

Nun erhalten wir 

Kennen wir die Primfaktorzerlegung von  (das wären  und ), dann können wir sehr schnell  und damit den zu  gehörenden inversen Exponenten  berechnen. Genial einfach!

Zusammenfassung

Zum Abschluss fassen wir die wichtigsten Eigenschaften des RSA Verfahrens zusammen. Das RSA Verfahren ist ein asymmetrisches Verfahren. Es gibt bis heute noch keinen effizienten Algorithmus, der eine natürliche Zahl N in seine Primfaktoren p und q zerlegen kann. Somit ist die Verschlüsselung mit dem RSA Verfahren sicher. Es ist so gut wie unmöglich eine mit dem RSA Verfahren verschlüsselte Nachricht zu „knacken“.  Es stellen sich jedoch die folgenden Fragen:

  • Wie wählt man zufällige Primzahlen und wie groß müssen diese sein?
  • Wie multipliziert man effizient große Zahlen „modulo“ ?
  • Wie exponenziert man effizient große Zahlen „modulo“ ?
  • Wie berechnet man effizient ?
  • Wie integriert man effizient RSA?
  • Warum und wie sicher ist das Verschlüsselungsverfahren?
  • Wo wird das Verschlüsselungsverfahren benutzt? 
  • Wo finde ich „offizielle“ Informationen zu diesem Verschlüsselungsverfahren?

Ich werde in den kommenden Blogartikeln auf alle diese Fragen eingehen. Würde es irgendwann in der Zukunft gelingen einen Algorithmus zu entwickeln, der eine Zahl effizient in ihre Primfaktoren zerlegen kann, so würde das RSA Verfahren nicht mehr als sicher angesehen werden. Aus diesem Grunde stellt ein Quantencomputer eine kommende Gefahr für das Verschlüsselungsverfahren dar. Solch ein Rechner würden vermutlich alle bis heute bekannten Verschlüsselungsalgorithmen obsolet werden lassen. Quantenalgorithmen werden gesondert in den kommenden Blogartikeln von mir behandelt.

Referenzen

[1] J. A. Buchmann, Introduction to Cryptography, Undergraduate Texts in Mathematics, second edition, Springer-Verlag, 2001 

[2] P. Bundschuh, Einführung in die Zahlentheorie, Springer Lehrbuch, 6. Auflage, Springer-Verlag, 2007

[3] U. Krengel, Einf ̈uhrung in die Wahrscheinlichkeitstheorie und Statistik, Vieweg Studium – Aufbaukurs Mathematik, 5. Auflage, Vieweg Verlag, 2000

[4] A. Beutelspacher, J. Schwenk, K-D. Wolfenstetter, Moderne Verfahren der Kryptographie, 8. Auflage, Springer Spektrum, 2015 

Add a Comment

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.