Das RSA-Verfahren

 

Abschließend wird als real benutztes Verfahren das RSA-Verfahren im Rahmen des Arbeitsblattes Das RSA-Verfahren vorgestellt.

Bemerkung: Im Zusammenhang mit dem RSA-Verfahren kann auch der Schlüsselaustausch nach Diffie-Hellman als ein weiteres Beispiel für ein asymmetrisches Verfahren behandelt werden. Dies ist auch aus historischer Sicht interessant. Wenn dies im Rahmen der RSA-Einheit thematisiert werden soll (was durchaus sinnvoll ist), so kann hier das Arbeitsblatt 02_iud_ab_asym_RSA aus der Einheit „Informationsgesellschaft und Datensicherheit (iud)“ verwendet werden.

Eine Liste verfügbarer Primzahlen, bei denen noch mit geringen Hilfmitteln gerechnet werden kann, findet man im Internet, z.B. bei Walter Fendt; ebenso ASCII-Tabellen der Buchstaben und Zahlen.

Um die Komplexität zu reduzieren, wird hier in diesem Unterrichtsgang lediglich der Kommunikationsweg A → B betrachtet, nicht die beiderseitige Kommunikation. Nachdem der Unterrichtsgang bis hier verfolgt wurde, kann die Erweiterung auf eine beiderseitige Kommunikation aufgesetzt werden.

Tiefergehende Hintergrundinformationen zu grundlegenden Fragen:

Wie sicher ist RSA?

Um den Algorithmus anwenden zu können, muss der Benutzer das Produkt $(p-1)\cdot (q-1)$ kennen. Der öffentliche Schlüssel informiert aber lediglich über die Zahl $N$ (bestimmt als $N=p\mathrm{·}q$ ) und nicht über die beiden erzeugenden Primfaktoren $p$ und $q$ selbst. Diese müssten eben über Faktorisierung herausgefunden werden, Stichwort „Einwegfunktion“.

In der Praxis setzt man also $N$ aus so großen Primfaktoren zusammen, dass die Zerlegung selbst mit leistungsfähigen Computern Jahre dauern würde (siehe Info in den Arbeitsblättern).

Da das Problem der Faktorisierung prinzipiell gelöst werden kann, bedeutet das, dass RSA theoretisch gesehen nicht sicher ist. Es dauert eben nach derzeitigem Stand der Technik und Mathematik so lange, dass die Information bis zum Zeitpunkt der Lösung nicht mehr relevant ist (diesen generellen Aspekt von „Sicherheit“ lohnt es sich durchaus, im Unterricht zu thematisieren: Auch z.B. Tresore werden mit einer Garantie verkauft, wie lange sie unbefugten Öffnungsversuchen widerstehen können).

In dieser Hinsicht ist also RSA solange sicher, bis ein entsprechend schneller Algorithmus für die Primfaktorzerlegung gefunden ist.

Das RSA-Verfahren durchzuführen ist mit den besprochenen Inhalten nun problemlos möglich. Schwieriger wird es jedoch, wenn man die Frage nach dem grundlegenden mathematischen Fundament des RSA-Verfahrens stellt: Warum funktioniert RSA? Welche Zusammenhänge müssen dazu bewiesen werden? Hierbei stößt man sehr schnell an die Grenzen dessen, was in der Schule machbar ist.

Hier als Anregung einige grundlegenden Sätze und der Beweis zur Korrektheit von RSA:

Grundlegende Sätze

1. Die Euler'sche $\phi$ -Funktion

   Ist $n$ eine natürliche Zahl, so gibt $\phi (n)$ die Anzahl der zu $n$ teilerfremden Zahlen an, die nicht größer als $n$ sind. Damit ist insbesondere klar: Ist $p$ eine Primzahl, so ist $p$ teilerfremd zu den Zahlen $1$ bis $p-1$. Daher gilt für Primzahlen $p: \phi (p)=p\mathrm{–}1$. Für teilerfremde Zahlen $m$ und $n$ gilt: $\phi (n)\cdot \phi (m)=\phi (n\cdot m)$. Daher gilt für Primzahlen $p$ und $q$: $\phi (p\cdot q)=\phi (p)\cdot \phi (q)=(p\mathrm{–}1)\cdot (q\mathrm{–}1)$. Beweise zur Euler'schen $\phi$-Funktion sind sehr langwierig und in diesem Zusammenhang nicht weiterführend. Deshalb sei hier für Interessierte auf die gängige Fachliteratur verwiesen.

2. Der Satz von Fermat-Euler und der kleine Satz des Fermat

   Satz von Fermat-Euler: Für $a,m\in \mathrm{\mathbb{N}}$ gilt: $\text{ggT}(a,m)=1\Rightarrow a^{\phi (m)}\equiv 1\text{ mod }m$

   Einen Spezialfall davon stellt der kleine Fermat'sche Satz dar:

   Ist $p$ eine Primzahl und $a\in \mathrm{\mathbb{N}}$, gilt: $\text{ggT}(a,p)=1\Rightarrow a^{p-1}\equiv 1\text{ mod }p$.

   Bem.: Satz von Fermat-Euler für $m=p$, da $\phi (q)=(p\mathrm{–}1)$

   Der Beweis des Satzes von Fermat-Euler geht über das in Klasse 10 Mögliche hinaus. Eine mögliche kombinatorische Variante (als „Kettenbasteln“) kann evtl. für sehr interessierte SuS thematisiert werden. Diese und einige weitere Beweismöglichkeiten findet man unter https://de.wikibooks.org/wiki/Beweisarchiv:_Zahlentheorie:_Elementare_Zahlentheorie:_Kleiner_Satz_von_Fermat

Der Beweis: Warum funktioniert RSA?

Die Beweise zur theoretischen Begründung der Korrektheit des RSA-Verfahrens sind ebenfalls oft aufwändig und mathematisch in der Schule nicht durchführbar. Hier jedoch eine mögliche Skizze, die man (unter Auslassung der Beweise zur Euler'schen Funktion) schrittweise nachvollziehen kann:

Die Botschaft B wird zum Geheimtext S verschlüsselt durch Berechnung von $B^e\text{ mod }N(=S)$. Die Entschlüsselung wird vorgenommen durch $S^d\text{ mod }N(=B)$. Also gilt: $$S^d\text{ mod }N={(B^e\text{ mod }N)}^d\text{ mod }N=B^{ed}\text{ mod }N.$$

Dabei war $d$ das (modulare) multiplikative Inverse zu $e$ bezüglich $\text{mod }(p\mathrm{–}1)\cdot (q\mathrm{–}1)$ und es gilt: $$(e\cdot d)\text{ mod }\phi (N)=1(\iff (e\cdot d)\text{ mod }\phi (p\cdot q)=(e\cdot d)\text{ mod }(p-1)\cdot (q-1)=1).$$

Mit $N=p\mathrm{·}q$ und $\phi (p\mathrm{·}q)=(p-1)\mathrm{·}(q-1)$ gilt die die Beziehung: $$e\mathrm{·}d=k\mathrm{·}\phi (N)+1=k\mathrm{·}\phi (p\mathrm{·}q)+1=k\mathrm{·}(p-1)\mathrm{·}(q-1)+1$$ und somit: $$e\mathrm{·}d\text{ mod }\phi (N)=(k\mathrm{·}(p-1)\mathrm{·}(q-1)+1)\text{ mod }\phi (N).$$

Wir erinnern uns: Der entschlüsselte Geheimtext war: $$S^d\text{ mod }N={(B^e)}^d=B^{ed}\text{ mod }N.$$

Wenn RSA funktionieren soll, muss also gelten: $$B^{ed}\text{ mod }N=B.$$ Mit der obigen Beziehung: $$e\mathrm{·}d=k\mathrm{·}(p-1)\mathrm{·}(q-1)+1$$ muss also gelten: $$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }N=B.$$

Zusammenfassend die zu beweisende zentrale Aussage (Korrektheit von RSA):

Es seien $p,q$ verschiedene Primzahlen und $B\in \mathrm{\mathbb{N}}\text{ mit }B<p\mathrm{·}q.$ Dann gilt für jede Zahl $k\in \mathrm{\mathbb{N}}:B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }pq=B.$

Beweis¹: Zunächst getrennt nach den Primzahlen $p$ und $q$ (1), (2), dann Zusammenführung (3):

1. $B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }p=B$
2. $B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }q=B$
3. $B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }pq=B$

Zu:

1. Mit den elementare Potenzregel $a^{n+m}=a^n\cdot a^m$ und ${\left(a^m\right)}^n=a^{mn}$ folgt:$$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}=B\mathrm{·}{B}^{k\mathrm{·}(p-1)\mathrm{·}(q-1)}=B\mathrm{·}{\left(B^{(p-1)}\right)}^{k(q-1)}.$$

   Mit den Regeln für modulares Potenzieren, dem kleinen Fermat'schen Satz $\text{ggT}(p,B)=1\Rightarrow B^{p-1}\equiv 1\text{ mod }p$ sowie $\text{ggT}(p,B)=1$ , da $p$ Primzahl und ist, folgt: $$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }p=B\mathrm{·}{\left(B^{p-1}\right)}^{k\mathrm{·}(q-1)}\text{ mod }p=B\mathrm{·}{\left(B^{p-1}\text{ mod }p\right)}^{k\mathrm{·}(q-1)}\text{ mod }p$$ $$=B\mathrm{·}{(1\text{ mod }p)}^{k\mathrm{·}(q-1)}\text{ mod }p=B\mathrm{·}{1}^{k\mathrm{·}(q-1)}\text{ mod }p=B\text{ mod }p.$$

   Zusammenfassend: $$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }p=B\text{ mod }p.$$

2. Für $q$ analog, lediglich mit anderer Sortierung im Exponenten.

   Zusammenfassend: $$B^{k\mathrm{·}(p-1)\mathrm{·}(q-1)+1}\text{ mod }q=B\text{ mod }q.$$

3. $N=pq$: Hierzu führen wir der Übersichtlichkeit halber ein $h:=k\mathrm{·}(p-1)\mathrm{·}(q-1)+1.$

   In den beiden in (1) und (2) erhaltenen Gleichungen $B^h\text{ mod }p=B\text{ mod }p$ und $B^h\text{ mod }q=B\text{ mod }q$ bringen wir jeweils $B$ auf die andere Seite und erhalten: $$B^h\text{ mod }p\mathrm{–}B\text{ mod }p=0$$ und $$B^h\text{ mod }q\mathrm{–}B\text{ mod }q=0.$$

   Mit Anwendung der Regel über modulare Addition folgt: $$(B^h-B)\text{ mod }p=0$$ und $$(B^h-B)\text{ mod }q=0.$$ Sowohl $p$ als auch $q$ teilen also $B^h-B.$

   $p$ und $q$ sind jedoch verschiedene Primzahlen, also muss $(p\mathrm{·}q)$ die Zahl $B^h-B$ teilen.

   Mit den Rechenregel für modulares Addieren und gilt damit: $$(B^h\mathrm{–}B)\text{ mod }(p\mathrm{·}q)=0$$ $$\iff B^h\text{ mod }(p\mathrm{·}q)\mathrm{–}B\text{ mod }(p\mathrm{·}q)=0$$ $$\iff B^h\text{ mod }(p\mathrm{·}q)\mathrm{–}B=0$$ $$\iff B^h\text{ mod }(p\mathrm{·}q)=B\mathrm{■}$$

Die einzelnen Schritte sind so mit den im Verlauf des Unterrichts bewiesenen Gesetzen begründet nachvollziehbar. Allerdings bleibt der Beweis aufwändig.

 

¹ Angelehnt an http://www.mathematik-netz.de/pdf/RSA.pdf.

 

Unterrichtsverlauf: Herunterladen [odt][244 KB]

Unterrichtsverlauf: Herunterladen [pdf][615 KB]

 

Weiter zu Kopiervorlagen