RSA-Verfahren in der gymnasialen Oberstufe Niedersachsen

Im Kerncurriculum Informatik für die gymnasiale Oberstufe in Niedersachsen ist das Modul "Kryptologie" im Lernfeld "Informationen und Daten" in den inhaltsbezogenen Kompetenzen vorgegeben. "Die Schülerinnen und Schüler beschreiben und unterscheiden die Prinzipien der symmetrischen und asymmetrischen Verschlüsselung." Symmetrische Verschlüsselungen sind Verschlüsselungen, bei denen die Kommunikationspartner denselben Schlüssel verwenden. Dieses Prinzip ist einleuchtend und bedarf kaum einer weiteren Erläuterung. Das Prinzip der asymmetrischen Verschlüsselung hingegen ist intuitiv kaum zu erfassen. Da es eine wichtige Grundlage für die verschlüsselte Kommunikation im Internet darstellt, lohnt es sich, über das pure Prinzip hinaus, als Beispiel für dieses Verschlüsselungsprinzip das RSA-Verfahren im Unterricht zu behandeln. Eine alleinige Auseinandersetzung nur mit dem Prinzip der asymmetrischen Verschlüsselung ist für die Schülerinnen und Schüler wie "Stricken ohne Wolle". Damit die Behandlung des Themas nicht einer Mathematikvorlesung gleicht, kann man z.B. folgende Vorgehensweise wählen:

  • Zur Vorentlastung eine (kurze) Einführung in modulare Arithmetik, wobei deutlich werden muss, dass das modulare Potenzieren sich nicht, wie in der normalen Arithmetik, monoton verhält.
  • Lesen der Kurzgeschichte "Der Dialog der Schwestern" von Carsten Elsner aus c't 25/1999. Hier wird das RSA-Verfahren im Rahmen einer Geschichte zweier Schwestern die in einer psychatrischen Anstalt nur mit Zahlen kommunizieren, dargestellt.
  • Die geheime Botschaft am Ende der Geschichte müssen die Schülerinnen und Schüler anschließend entschlüsseln (wegen der relativ kleinen Zahlen ist der hierfür benötigte private Schlüssel aus dem öffentlichen leicht zu ermitteln).
  • Anschließend stellen die Schülerinnen und Schüler das RSA-Verfahren an den zwei Beispielen aus der Geschichte in strukturierter Form dar: Öffentlicher Schlüssel, privater Schlüssel, Ablauf der Kommunikation.
  • Im Anschluss kann im Kurs der mathematische Hintergrund mit dem Satz von Euler und der Eulerschen Phi-Funktion besprochen werden. Dabei ist es wichtig nochmals herauszuarbeiten, dass der private Schlüssel von einem Angreifer nur ermittelt werden kann, wenn die Semiprimzahl des Moduls in die beiden Primfaktoren zerlegt wird. Dies ist bei den in der Praxis verwendeten sehr großen Zahlen allerdings nicht effektiv möglich.
    Außerdem ist es noch nötig klarzustellen, dass tatsächlich nicht einzelne Buchstaben codiert und verschlüsselt werden wie in der Geschichte dargestellt (dann wäre das Verfahren im Kern nur eine monoalphabetische Substitution), sondern das Blöcke von Buchstaben codiert und verschlüsselt werden.

Die inhaltliche Fortsetzung kann dann mit der Fortsetzung der Geschichte "Neues von den Schwestern" aus c't 3/2019 erfolgen, in der die Authentizität und Integrität einer Nachricht thematisiert wird.

Vielen Dank an dieser Stelle an Carsten Elsner für die schönen Geschichten mit den Schwestern.

 

Das RSA-Verfahren

Das RSA-Verfahren ist eine asymmetrisches Verschlüsselungsverfahren. Der mathematische Hintergrund ist erstaunlich einfach zu verstehen und basiert auf dem Satz von Euler. Der Kern des Verfahrens ist zweimaliges modulares Potenzieren für das Verschlüsseln und das Entschlüsseln mit geeigneten Zahlen.

Der erste Teil des öffentlichen Schlüssels ist eine Semiprimzahl, also ein Produkt zweier Primzahlen. Diese Zahl dient als Modul bei den modularen Operationen des Verfahrens. Aus dieser Zahl werden zwei weitere Zahlen bestimmt, von denen die erste den zweiten Teil des öffentlichen Schlüssels und die zweite den privaten Schlüssel bilden.

Die Bestimmung der beiden Zahlen folgt aus dem Satz von Euler:

aphi(n)+1 = a mod n, wobei ggT(a,n) = 1.

Phi(n) ist dabei der Wert der Eulerschen Phifunktion, die die Anzahl der zu  n teilerfremden Zahlen (also mit größtem gemeinsamen Teiler 1) kleiner n angibt. Bei einer Semiprimzahl

n = p1 * p2

gilt

phi(n) = (p1-1)*(p2-1).

Der Wert ist also aus der Primfaktorzerlegung von n einfach zu bestimmen.

Nun müssen nur zwei Zahlen d und e bestimmt werden, deren Produkt dem Wert phi(n) +1 entsprechen bzw. für die gilt d*e = 1 mod phi(n). Dann gilt nach dem Satz von Euler

ad*e = ade = a mod n.

Durch ad mod n wird also verschlüsselt. Anschließend kann durch den privaten Teil des Schlüssels e durch modulares Potenzieren modulo n wieder entschlüsselt werden. Die Sicherheit basiert auf der zeitaufwändigen Zerlegung der (sehr großen) Semiprimzahl n in Primfaktoren. Es ist hingegen einfach n als Produkt zweier Primzahlen zu erzeugen, da für die Bestimmung sehr großer Primzahlen effektive (stochastische) Verfahren existieren.