Kryptologie/Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens

Einleitung

Das RSA-Verschlüsselungsverfahren ist ein asymmetrisches Kryptosystem und benötigt daher zwei Schlüssel: den öffentlichen und den privaten Schlüssel. Der öffentliche Schlüssel besteht aus einem Zahlenpaar $(e,N)$ und der private Schlüssel aus einem Zahlenpaar $(d,N)$. $N$ ist in beiden Schlüsseln identisch und bildet den Modulo des RSA-Verschlüsselungsverfahrens. Außerdem ist $e$ der Verschlüsselungs- und $d$ der Entschlüsselungsexponent.

Schlüsselerzeugungsalgorithmus

Der Algorithmus der Schlüsselgenerierung besteht aus insgesamt fünf Schritten:

Primzahl, (Folgerung) eulersche $\varphi$-Funktion, Teilerfremdheit, multiplikative Inverse, Kongruenz und erweiterter euklidischer Algorithmus
Primzahl
Sei $p\in \mathbb {N}$ mit $p>1$, dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb {N}$, nämlich $1$ und $p$. Andernfalls heißt $p$ zusammengesetzte Zahl.
Eulersche $\varphi$-Funktion
Für die eulersche $\varphi$-Funktion gilt: $\varphi (n)\;:=\mid G_{n}\mid$ mit $G_{n}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}$.
Folgerung aus Satz 1 der eulerschen $\varphi$-Funktion
Für $N=p\cdot q$ mit $p,q$ prim folgt $\varphi (N)=(p-1)\cdot (q-1)$.
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $ggT(a,b)=1$. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind.
Multiplikative Inverse
Die Restklasse $[a]_{m}$ ist genau dann invertierbar in $\mathbb {Z} /m\mathbb {Z}$, wenn gilt $ggT(a,m)=1$ und die Lösung $[s]_{m}$ der Kongruenz $as\equiv 1{\bmod {m}}$ ist eindeutig bestimmt und wir nennen diese multiplikative Inverse von $[a]_{m}$.
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus wird auf zwei Zahlen $a,b\in \mathbb {N}$ angewandt und besteht aus zwei Teilen: Berechnung des $\operatorname {ggT} (a,b)=s\cdot a+t\cdot b$ (auch als euklidischer Algorithmus bekannt), Berechnung zweier ganzer Zahlen $s$ und $t$, welche die Gleichung $\operatorname {ggT} (a,b)=s\cdot a+t\cdot b$ erfüllen.

1. Wahl der Primzahlen
   • Wähle zufällig und mit einheitlicher Wahrscheinlichkeit zwei sehr große Primzahlen $p$ und $q$ mit $p\neq q$
     • Aus Sicherheitsgründen wählt man Primzahlen mit über 300 Dezimalstellen
2. Berechnung des RSA-Modul $N$
   • $N=p\cdot q$
3. Berechnung von $\varphi (N)$
   • Wir nutzen die Folgerung aus Satz 1 der eulerschen $\varphi$-Funktion $\varphi (N)=(p-1)\cdot (q-1)$
4. Wahl des öffentlichen Schlüssels $(e,N)$
   • Wähle eine zu $\varphi (N)$ teilerfremde Zahl $e$, für die gilt $1<e<\varphi (N)$
   • Setze $e$ und $N$ in $(e,N)$ ein
5. Berechnung des privaten Schlüssels $(d,N)$
   • Berechne den Entschlüsselungsexponenten $d$ als multiplikative Inverse von $e$ bezüglich des Moduls $\varphi (N)$. Es soll also die folgende Kongruenz gelten $e\cdot d\equiv 1{\bmod {\varphi (N)}}$
     • Aufgrund der Kongruenz gilt $1=e\cdot d+k\cdot \varphi (N)$ mit $k\in \mathbb {Z}$ und da die in Schritt 4 gewählte Zahl $e$ teilerfremd zu $\varphi ({N})$ ist, gilt $1=\operatorname {ggT} (e,\varphi (N))$
     • $d$ kann mit dem erweiterten euklidischen Algorithmus berechnet werden
   • Setze $d$ und $N$ in $(d,N)$ ein

Beispiel

Bemerkung: Für gewöhnlich verwendet man Primzahlen, die mindestens der Größenordnung $2^{1024}$ entsprechen und mindestens 309 Dezimalstellen aufweisen. Wir verwenden deutliche kleinere Zahlen, um das Verfahren besser veranschaulichen zu können.

Berechnung des privaten Schlüssels $(47,143)$

Sei $t=23$ und $\varphi (N)=120$. Berechnung $\operatorname {ggT} (23,120)$ $120=5\cdot 23+5$ $23=4\cdot 5+3$ $5=1\cdot 3+2$ $3=1\cdot 2+1$ $2=2\cdot 1+0$ Es gilt $\operatorname {ggT} (23,120)=1$. Berechnung der Faktoren $d$ und $k$ mit $\operatorname {ggT} (23,120)=d\cdot 23+k\cdot 120$ $3=1\cdot 2+1$ $\Leftrightarrow 1=3-1\cdot 2$ $\Leftrightarrow 1=3-1\cdot (5-1\cdot 3)$, da $5=1\cdot 3+2\Leftrightarrow 5-1\cdot 3=2$ $\Leftrightarrow 1=2\cdot 3-5$ $\Leftrightarrow 1=2\cdot (23-4\cdot 5)-5$, da $23=4\cdot 5+3\Leftrightarrow 23-4\cdot 5=3$ $\Leftrightarrow 1=2\cdot 23-9\cdot 5$, da $-8\cdot 5-5=-9\cdot 5$ $\Leftrightarrow 1=2\cdot 23-9\cdot (120-5\cdot 23)$, da $120=5\cdot 23+5\Leftrightarrow 120-4\cdot 23=5$ $\Leftrightarrow 1=2\cdot 23-9\cdot 120+45\cdot 23$ $\Leftrightarrow 1=47\cdot 23-9\cdot 120$ $\Rightarrow d=47$ und $k=-9$ Der private Schlüssel ist $(d,N)=(47,143)$

1. Wahl der Primzahlen
   • Wir wählen (zufällig) $p=11$ und $q=13$ als Primzahlen
2. Berechnung des RSA-Modul $N$
   • als Modulo des RSA-Verfahrens erhalten wir $N=p\cdot q=143$
3. Berechnung von $\varphi (N)$
   • die eulersche $\varphi$-Funktion nimmt $\varphi (143)=10\cdot 12=120$ an
4. Wahl des öffentlichen Schlüssels $(e,N)$
   • die Zahl $e$ muss zu $120$ teilerfremd sein. Wir wählen $e=23$. Damit bilden $e=23$ und $N=143$ den öffentlichen Schlüssel $(23,143)$
5. Berechnung des privaten Schlüssels $(d,N)$
   • Berechnung der multiplikativen Inversen $e^{-1}\equiv d{\bmod {\varphi }}(N)$ mit $e\cdot d\equiv 1{\bmod {\varphi (N)}}$
     • Angewandt auf das Beispiel gilt: $23\cdot d+k\cdot 120=1=\operatorname {ggT} (23,120)$
     • Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren $d=47$ und $k=-9$, so dass die Gleichung aus dem Beispiel wie folgt aussieht: $23\cdot 47+(-9)\cdot 120=1$
     • Die Berechnung von $d=47$ und $k=-9$ haben wir bereits in der Lernaufgabe zum erweiterten euklidischen Algorithmus durchgeführt
   • $d=47$ bildet mit $N=143$ den privaten Schlüssel $(47,143)$, während $k$ nicht weiter benötigt wird

Lernaufgabe

Aufgabe

Berechnen Sie ihr eigenes Schlüsselpaar aus privatem und öffentlichem Schlüssel mit dem Schlüsselerzeugungsalgorithmus des RSA-Algorithmus. Eine Liste mit den Primzahlen bis $100.000$ finden Sie hier.

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
6: RSA-Kryptosystem
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
6: RSA-Kryptosystem	7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens	7.2: Verschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens
Grundlagen der aktuellen Lerneinheit
7.1.1: Primzahl(-eigenschaften)	7.1.2: Probedivision (Primzahltest 1)	7.1.3: Fermat-Test (Primzahltest 2)
7.1.4: Miller-Rabin-Test (Primzahltest 3)	7.1.5: Erweiterter euklidischer Algorithmus	7.1.6: Eulersche φ-Funktion