Benutzer:Didia/RSA

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Didia auf.

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 $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 Körper

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 $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 )$. So ist beispielsweise das multiplikativ Inverse von $7$ die rationale Zahl $1/7$ (in den ganzen Zahlen hat $7$ dagegen kein multiplikativ Inverses).

Die Modulo-Addition entspricht der Addition in $\mathbb {N}$, wobei man beim Ergabnis $\geq n$ anschliessend den Rest der Ganzzahldivision durch $n$ nimmt (also modulo n rechnet). Definiert man nun auf der Menge $\mathbb {Z} _{n}:=\{0,1,2,...,n-1\}$ eine Modula-Addition bezüglich des Moduls $n$, so entsteht eine (abelsche) Gruppe.

So gilt beispielsweise in $\mathbb {Z} _{8}$

$1+2=3$

$3+5=8\ {\bmod {\ }}8=0$

$5+5=10\ {\bmod {\ }}8=2$.

Bezüglich der Multiplikation modulo $8$ als Verknüpfung bildet die Menge $\mathbb {Z} _{8}$ jedoch keine Gruppe, selbst wenn die $0$ ausgenommen wird. Es gibt noch weitere Zahlen, die kein inverses Element haben, nämlich $2$, $4$ und $6$. Dies sind genau die Zahlen, die einen echten Teiler mit $8$ gemeinsam haben. Die verbleibenden Elemente bilden schließlich die Multiplikative Gruppe $\mathbb {Z} _{8}^{*}$.

Die prime Restklassengruppe ist somit die Gruppe der primen Restklassen bezüglich eines Moduls $n$. Sie wird als $\mathbb {Z} _{n}^{*}$ oder $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ notiert. Sie sind genau die multiplikativ invertierbaren Restklassen und sind daher endliche abelsche Gruppen bezüglich der Multiplikation. In der Kryptographie sind vor allem jene Zahlen $n$ von Interesse, für die alle Zahlen zwischen $1$ und $n-1$ ein inverses Element modulo $n$ haben. Dies ist genau dann der Fall, wenn $n$ eine Primzahl ist (weshalb man $p$ statt $n$ schreibt). Die Zahlen zwischen $1$ und $p-1$ bilden also zusammen mit der Modulo-Multiplikation die Gruppe $Z_{p}^{*}$.

Ein Körper ist eine Menge $K$ versehen mit zwei inneren zweistelligen Verknüpfungen „$+$“ und „$\cdot$“, die meist „Addition“ und „Multiplikation“ genannt werden. Ein Körper ist bezüglich der Addition und der Multiplikation ohne Null eine Gruppe und es gelten die Distributivgesetze. Der bekannteste Körper ist die Menge der reellen Zahlen $\mathbb {R}$, auf der Addition und Multiplikation in üblicher Weise definiert sind. Für eine Primzahl $p$ bildet die Menge der Zahlen zwischen $0$ und $p-1$ sowohl mit der Modulo-Addition also auch mit der Modulo-Multiplikation ohne Null eine Gruppe. Die Restklassen ganzer Zahlen modulo $p$, geschrieben $\mathbb {F} _{p}$ oder $\operatorname {GF} (p)$, bilden somit einen endlichen Körper (auch Galoiskörper, engl. Galois field).

Berechnung des multiplikativ Inversen modulo n

Mit dem erweiterten euklidischen Algorithmus

Die multiplikative Gruppe $\mathbb {Z} _{n}^{*}$ besteht aus den Elementen von $\mathbb {Z} _{n}$, die teilerfremd zu $n$ sind. Für jedes $a\in \mathbb {Z} _{n}$ gilt also

$\operatorname {ggT} (a,n)=1$.

Das multiplikativ inverse Element $a^{-1}$ zu einer Zahl $a$ in $\mathbb {Z} _{n}$ erfüllt die Bedingung

$a\cdot a^{-1}=1\ ({\bmod {\ }}n)$.

Das Lemma von Bézout besagt, dass sich der größte gemeinsame Teiler $\operatorname {ggT} (a,n)$ zweier ganzer Zahlen $a$ und $n$ als Linearkombination von $a$ und $n$ mit ganzzahligen Koeffizienten darstellen lässt:

Sei $\operatorname {ggT} (a,n)=g$: Dann gibt es ganze Zahlen $s$ und $t$ mit $g=s\cdot a+t\cdot n$.

Sind $a$ und $b$ teilerfremd (also $g=1$), dann existieren offensichtlich$s,t\in \mathbb {Z}$, sodass

$1=s\cdot a+t\cdot n$

gilt. Modulo $n$ gerechnet ergibt sich nun

$1=s\cdot a\ ({\bmod {\ }}n)$,

da der zweite Summand den Faktor $n$ enthält und somit „wegfällt“. Die Multiplikation mit $a^{-1}$ ergibt

$a^{-1}=s\ ({\bmod {\ }}n)$.

Somit ist also $s\ {\bmod {\ }}n$ das inverse Element von $a$ in $\mathbb {Z} _{n}^{*}$.

Die Koeffizienten $s$ und $t$ können mit dem erweiterten euklidischen Algorithmus effizient berechnet werden und damit auch das Inverse $a^{-1}=s\ {\bmod {\ }}n$.

Beispiel:

Gesucht sei das Inverse von $a=25$ in $\mathbb {Z} _{29}^{*}$. Da $\operatorname {ggT} (25,29)=1$ gilt, existiert dieses. Des weiteren existieren $s$ und $t$, die die Bedinung

$1=s\cdot 25+t\cdot 29$

erfüllen. Der erweiterte euklidische Algorithmus liefert nun die Zahlen $s=7$ und $t=-6$. Es lässt sich nun leicht überprüfen, dass gilt

$1=s\cdot a+t\cdot n=7\cdot 25+(-6)\cdot 29$.

Damit ist auch das Inverse $a^{-1}=s\ {\bmod {\ }}29=7\ ({\bmod {\ }}29)$ gefunden. Auch dies lässt sich überprüfen:

$a\cdot a^{-1}=25\cdot 7\ {\bmod {\ }}29=175\ {\bmod {\ }}29=1\ ({\bmod {\ }}29)$.

Durch modulare Exponentiation

TBD