Anzeige
Phänomene

Von Schlüsseln und Potenzfunktionen

Welche Mathematik steckt hinter dem Public-Key-Verfahren?

Zurück zu den Anfängen. Zwei Jahre später, im Jahr 1978, veröffentlichten Ron Rivest, Adi Shamir

und Len Adleman vom Massachusetts Institute of Technology (MIT) den nach ihnen benannten RSA-Algorithmus, den ersten Algorithmus mittels Public Key (PK). Damit war PK-Kryptografie Realität geworden.

Der erste Schritt: Ein Algorithmus erzeugt zwei Schlüssel, den öffentlichen erhält der spätere Absender der Nachricht. © Odder/CC_by-sa 3.0

Prinzipiell besteht ein Public-Key-Verschlüsselungsverfahren aus drei Algorithmen: Der erste erzeugt ein Schlüsselpaar, das aus einem öffentlichen und dem dazugehörigen geheimen Schlüssel besteht. Der zweite verschlüsselt den Klartext unter Verwendung des öffentlichen Schlüssels. Der dritte schließlich entschlüsselt den Text wieder unter Verwendung des geheimen Schlüssels.

Das Geheimnis der modularen Exponentialfunktion

Das mathematische Verfahren, auf dem der RSA-Algorithmus und fast alle anderen Public-Key-Algorithmen beruhen, ist die „modulare Exponentiation“. Diese Exponentialfunktion, also die Funktion f(x) = gx für eine beliebige Basis (g) gehört zu den am besten untersuchten und verstandenen Funktionen der Mathematik. Im Falle des RSA-Algorithmus benutzt man dafür aber nur die natürlichen Zahlen unterhalb einer festen Zahl n, also die Zahlen 0, 1, 2, …, n-1.

Auch mit diesen Zahlen kann man rechnen, das heißt addieren, subtrahieren und multiplizieren, und zwar, indem man zunächst so rechnet wie in den natürlichen Zahlen und dann das Ergebnis durch n teilt und nur den Rest betrachtet. Im Fall n = 10 würde man also 3 x 8 ausrechnen, indem man zunächst 3 x 8 = 24 rechnet und dann als Ergebnis den Rest nimmt, der entsteht, wenn man 24 durch 10 teilt. Das Ergebnis ist also 4. Man spricht von „modularer Arithmetik“.

Anzeige
Der zweite Schritt: Der Absender verschlüsselt die Nachricht mit dem öffentlichen Schlüssel, die Empfängerin entschlüsselt sie mit ihrem geheimen Schlüssel. © Odder/CC_by-sa 3.0

Der große Vorteil daran: Die modulare Exponentialfunktion kann man leicht ausrechnen, aber nur sehr schwer umkehren: Aus f(x) = xe lässt sich nur außerordentlich mühsam das x wieder bestimmen. Daher ist die Potenzfunktion ideal geeignet für die Public-Key-Kryptografie. Denn ein Entschlüsseln geht zwar, aber nur, wenn man den Schlüssel, die geheime Zahl d kennt. Dann ist es einfach, man potenziert das Ergebnis einfach mit d und erhält x.

Primzahlen spielen eine wichtige Rolle

Beim RSA-Algorithmus wird die Nachricht zunächst in eine natürliche Zufallszahl (m) umgewandelt. Dann wendet er auf sie die modulare Potenzfunktion an, und zwar mit dem öffentlichen Exponenten e des Empfängers. Das kann jeder, denn dazu ist keinerlei Geheimnis notwendig. Entschlüsseln kann demgegenüber nur der legitime Empfänger, der seinen privaten Schlüssel d anwendet und damit die erhaltene Geheimbotschaft potenziert.

Jeder Teilnehmer, der eine Nachricht empfangen möchte (oder sein Computer), wählt zwei große verschiedene Primzahlen p und q und bildet ihr Produkt n = pq. Danach bestimmt er natürliche Zahlen e und d mit der Eigenschaft, dass ihr Produkt ed von der Form 1 plus ein Vielfaches von (p-1)(q-1) ist. Die Zahlen e und n werden veröffentlicht („öffentlicher Schlüssel“), die Zahl d dient als privater Schlüssel, den nur der Teilnehmer kennen darf. Die Primzahlen p und q müssen ebenfalls geheim gehalten werden.

Verschlüsselt wird so, dass die als Zahl dargestellte Nachricht m mit e modular potenziert wird: c =me mod n. Entschlüsselt wird mithilfe des privaten Schlüssels d = cd mod n. Ein vergleichsweise elementarer Satz des großen Mathematikers Leonhard Euler (1707–1783) garantiert, dass sich beim Entschlüsseln wieder die Nachricht m ergibt

  1. zurück
  2. |
  3. 1
  4. |
  5. 2
  6. |
  7. 3
  8. |
  9. 4
  10. |
  11. 5
  12. |
  13. weiter

Albrecht Beutelspacher (Universität Gießen / Mathematikum), DFG Forschung
Stand: 12.07.2013

Teilen:
Anzeige

In den Schlagzeilen

Inhalt des Dossiers

Offenes Geheimnis
Die Mathematik hinter der Public-Key-Verschlüsselung

Asymmetrisch statt symmetrisch
Von der klassischen Kryptografie zum Public Key

Von Schlüsseln und Potenzfunktionen
Welche Mathematik steckt hinter dem Public-Key-Verfahren?

Die digitale Signatur
Wie die Public-Key-Kryptografie die Echtheit elektronischer Dokumente sichert

Auf dem Weg zur E-Münze
Auch elektronische Geldsysteme basieren auf PK-Kryptografie

Diaschauen zum Thema

News zum Thema

Quantenschlüssel mit Schwachstellen
Forscher decken Sicherheitslücke bei der Quantenkryptografie auf

Weltrekord bei der Primfaktorzerlegung
Forscher "knacken" 232-stellige Zahl

Erstes Netzwerk mit Quanten-Verschlüsselung
Sichere Kommunikation in handelsüblichen Glasfasernetzen dank Quantenkryptographie

Neuer Codeknacker-Weltrekord
Mathematiker entschlüsseln riesige Zahl

Dossiers zum Thema

Alan Turing - Genialer Computerpionier und tragischer Held