Benutzer:Didia/RSA

RSA-Kryptosystem

Mathematische Grundlagen

Einwegfunktionen mit Falltür

Funktion und Umkehrfunktion

Eine Einwegfunktion ist eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist. Eine mathematische Einwegfunktion $f:X\to Y$ muss folgende Eigenschaften aufweisen:

• Die Berechnung des Funktionswerts $y=f(x)$ ist „einfach“, d. h. es existiert ein Algorithmus, der ihn in Polynomialzeit berechnen kann.
• Die Berechnung der Umkehrfunktion zu einem gegebenen Funktionswert Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle y} , d. h. einem $x$, sodass $f^{-1}(y)=x$, ist allerdings „schwer“, d. h. es existiert kein „schneller“ Algorithmus für dieses Problem. „Schnell“ meint hier einen probabilistischen Algorithmus, der in Polynomialzeit läuft.

Einen anschaulichen Vergleich bietet ein klassisches Papier-Telefonbuch einer größeren Stadt: Die auszuführende Funktion ist die, einem Namen die entsprechende Telefonnummer zuzuordnen. Da die Namen alphabetisch geordnet sind, lässt sich dies ziemlich schnell durchführen. Aber ihre Invertierung, also die Zuordnung eines Namens zu einer gegebenen Telefonnummer, ist offensichtlich viel schwieriger.

Man kann zeigen, dass Einwegfunktionen genau dann existieren, wenn P ≠ NP, die berühmte Vermutung aus der Komplexitätstheorie, gilt (siehe P-NP-Problem). Obwohl die Einwegfunktionen in der Kryptographie eine wichtige Rolle spielen, ist also bis heute nicht bekannt, ob sie im streng mathematischen Sinne überhaupt existieren.

Eine Variante der Einwegfunktionen sind Trapdoor-Einwegfunktionen, auch Falltürfunktionen genannt. Diese lassen sich nur dann effizient umkehren, wenn man eine gewisse Zusatzinformation besitzt. Eine Metapher für Falltürfunktionen ist die Funktion eines Briefkastens: Jeder kann einen Brief einwerfen. Das Herausholen ist dagegen sehr schwierig – es sei denn, man ist im Besitz des Schlüssels.

Der Diffie-Hellman-Merkle-Schlüsselaustausch verwendet beispielsweise die diskrete Exponentialfunktion als Einwegfunktion (mit dem diskreten Logarithmus als schwer zu berechnende Umkehrfunktion). Zu dieser existiert keine Falltür. Im Gegensatz dazu verwendet das RSA-Kryptosystem mit der Faktorisierung eine Einwegfunktion mit Falltür.

Primzahl-Multiplikation und Faktorisierung

Das RSA-Kryptosystem basiert darauf, dass das Multiplizieren zweier Primzahlen eine Einwegfunktion ist. Sei also eine Funktion $f$ mit zwei Primzahlen $p$ und $q$ als Argumente gegeben, die eine Multiplikation durchführt:

$f(p,q)=p\cdot q$

Diese Primzahl-Multiplikation ist mit moderner Computerunterstützung auch bei „grösseren“ Zahlen „einfach“ durchführbar.

Die Umkehrfunktion $f^{-1}$ entspricht der Faktorisierung. Für eine gegebene Zahl $n$ sollen die Faktoren $p$ und $q$ berechnet werden:

$f^{-1}(n)=(p,q)$

Es ist bis heute kein effizientes Verfahren bekannt, mit dem aus dem Produkt zweier Primzahlen die beiden Faktoren bestimmt werden können. In diesem Zusammenhang spricht man auch vom Faktorisierungsproblem. Auch wenn sich nicht beweisen lässt, dass die Primzahl-Multiplikation eine Einwegfunktion ist, so spricht doch alles dafür.

Klaus Schmeh macht zur Veranschaulichung das folgende kleine Experiment: „Berechnen Sie im Kopf das Resultat der Multiplikation $13\cdot 17$. Dann bestimmen Sie zum Vergleich die beiden Primzahlen, die miteinander multipliziert 217 ergeben (natürlich auch im Kopf). Damit können Sie sich in etwa vorstellen, warum die Primzahl-Multiplikation als Einwegfunktion gilt.“

Der nächste entscheidende Schritt besteht darin, zur Primzahl-Multiplikation als Einwegfunktion eine Falltürfunktion zu „basteln“.

Phi-Funktion

Die Eulersche φ-Funktion (Eulersche Phi-Funktion) gibt für jede natürliche Zahl $n$ an, wie viele zu $n$ teilerfremde natürliche Zahlen es gibt, die nicht größer als $n$ sind. Zur Zahl $6$ sind beispielsweise genau die Zahlen $1$ und $5$ teilerfremd, also ist $\operatorname {\varphi } (6)=2$. Zur Primzahl $13$ ist jede der $12$ Zahlen von $1$ bis $12$ teilerfremd, also ist $\operatorname {\varphi } (13)=12$.

Da eine Primzahl $p$ nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis $p-1$ teilerfremd. Weil sie größer als 1 ist, ist sie außerdem nicht zu sich selbst teilerfremd. Es gilt daher

$\varphi (p)=p-1$.

Die Phi-Funktion ist eine multiplikative zahlentheoretische Funktion, sodass für teilerfremde Zahlen $m$ und $n$

$\varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)$

gilt. Zum Beispiel ist $\varphi (18)=\varphi (2)\cdot \varphi (9)=1\cdot 6=6$

Man geht davon aus, dass die Berechnung der $\varphi$-Funktion mindestens so aufwändig ist wie die Faktorisierung. Allerdings kann man $\operatorname {\varphi } (n)$ einfach berechnen, wenn es sich dabei um das Produkt zweier Primzahlen $p$ und $q$ handelt. Dann gilt nämlich

$\operatorname {\varphi } (n)=\operatorname {\varphi } (p)\cdot \operatorname {\varphi } (q)=(p-1)\cdot (q-1)$.

Allerdings muss man für diese Berechnung $p$ und $q$ tatsächlich kennen, denn es ist wiederum schwierig, zwei Primzahlen $p$ und $q$ zu bestimmen, von denen man nur das Produkt $n$ kennt (siehe Abschnitt „Primzahl-Multiplikation und Faktorisierung“).

Satz von Fermat-Euler

Eine wichtige Anwendung findet die Phi-Funktion im Satz von Fermat-Euler:

Wenn zwei natürliche Zahlen a und m teilerfremd sind, ist m ein Teiler von $a^{\varphi (m)}-1:$

$\operatorname {ggT} (a,m)=1\Rightarrow m\mid a^{\varphi (m)}-1$

Etwas anders formuliert:

$\operatorname {ggT} (a,m)=1\Rightarrow a^{\varphi (m)}\equiv 1{\pmod {m}}$

Da für prime Moduli $p$ gilt $\operatorname {\varphi } (p)=p-1$, geht für sie der Satz von Fermat-Euler in den kleinen Satz von Fermat über:

$a^{p-1}\equiv 1{\pmod {p}}$

Gruppen und Ringe

Eine Gruppe ist ein Paar $(G,*)$, bestehend aus einer Menge $G$ und einer assoziativen Verknüpfung $*$ auf $G$, die ein neutrales Element hat und für die jedes Element von $G$ ein inverses Element besitzt. Beispielsweise bildet die Menge der ganzen Zahlen mit der Addition als Verknüpfung die (abelsche) Gruppe $(\mathbb {Z} ,+)$. Das neutrale Element der Addition ist die $0$ (Null) und das additiv Inverse einer Zahl Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle a} ist ihre Gegenzahl $-a$. Die ganzen Zahlen $\mathbb {Z}$ sind bezüglich der Addition wiederum eine Untergruppe der rationalen Zahlen $\mathbb {Q}$. Demgegenüber bilden die rationalen (und ganzen) Zahlen zusammen mit der Multiplikation keine Gruppe, weil die Zahl $0$ kein inverses Element bezüglich der Multiplikation besitzt. Wenn man jedoch $0$ aus $\mathbb {R}$ entfernt, erhält man die (abelsche) Gruppe $(\mathbb {R} -\{0\},\cdot )$.