Kapitel 5
Ungelöste Rätsel und weitere Themen

9   Kryptographie -- die Kunst der Verschlüsselung

Zwei große Zahlen miteinander zu multiplizieren ist relativ einfach, zumindest für einen handelsüblichen Computer mit passender Software. Aus dem Ergebnis umgekehrt diese beiden Faktoren wieder herauszulesen, ist schwierig. Bei großen Zahlen mit mehreren Hundert Dezimalstellen ist es so schwierig, dass heutige Computer auch nach Jahren Rechenzeit daran scheitern. Lediglich Quantencomputer könnten dieses Problem noch einigermaßen effektiv lösen, wie wir aus dem vorherigen Kapitel wissen.

Diese Eigenschaft der Multiplikation nutzt man heute, um mit dem gängigen RSA-Verfahren wichtige Daten zu verschlüsseln, beispielsweise im Internet. Vielleicht haben Sie sich an dieser Stelle auch schon gefragt: Wie soll das gehen? Was hat die Faktorisierung großer Zahlen mit Verschlüsselung zu tun? Dieser Frage wollen wir im aktuellen Kapitel genauer nachgehen. Dabei wollen wir uns allerdings auch etwas allgemeiner mit dem Thema Verschlüsselung beschäftigen, um einen besseren Überblick zu gewinnen und damit das RSA-Verfahren besser einordnen zu können.


Eine kleine Geschichte der Kryptographie:

Wie kann man eine Nachricht so verschlüsseln, dass möglichst nur der beabsichtigte Empfänger diese verstehen kann? Schon Kinder sind von dieser Frage begeistert und basteln an eigenen Geheimschriften. Auch unsere Vorfahren standen oft vor dieser Frage, beispielsweise wenn es darum ging, militärische Botschaften vor dem Zugriff Fremder zu schützen.

Die einfachste Methode ist natürlich, die Nachricht zu verstecken: Zettel im Schuhabsatz, Tätowierung auf die Kopfhaut und dann Haare wachsen lassen, Zitronensaft als Tinte und vieles mehr. Auf solche Ideen sind unsere Vorfahren natürlich schon vor langer Zeit gekommen.

Will man sich nicht darauf verlassen, dass die Nachricht unentdeckt bleibt, dann muss man sie für einen zufälligen Entdecker unverständlich machen. Eine einfache Möglichkeit besteht darin, die Schriftzeichen (Buchstaben) nach einem bestimmten System durch andere Schriftzeichen zu ersetzen (Substitution) oder sie anders anzuordnen (Transposition). So verwendete der spartanische General Pasanius etwa 475 v.Chr. eine sogenannte Skytale, also einen Holzstab mit einem darum gewickelten Papyrusstreifen. Der Papyrusstreifen erscheint erst dann lesbar, wenn man ihn um eine Skytale gleichen Durchmessers wickelt:


Transposition durch eine spartanische Skytale
Quelle: Wikimedia Commons File:Skytale.png, dort lizensiert unter der GNU Free Documentation License, Version 1.2.


Julius Caesar verwendete um 50 v.Chr. eine einfache Substitutionsvorschrift zur Verschlüsselung: Verschiebe das Alphabet um n Zeichen, nimm also statt dem A beispielsweise ein D, statt dem B ein E usw., wobei nach dem Z wieder das A kommt. Hier gibt es sogar schon einen Schlüssel, den man zum Entziffern braucht, nämlich die Zahl n, um die verschoben wird.

Statt nur um n Stellen zu verschieben, kann man auch eine Übersetzungstabelle angeben, bei dem das Alphabet vollkommen willkürlich durcheinandergewirbelt wird. Wenn man diese Übersetzungstabelle (also den Schlüssel) nicht kennt, dann hat man schon große Mühe, gleichsam von Hand einen entsprechend verschlüsselten Text zu entziffern. Einen Ansatzpunkt zum Knacken dieses Codes liefert der Umstand, dass die Buchstaben in jeder Sprache eine bestimmte statistische Häufigkeitsverteilung haben, wie jeder Scrabble-Spieler weiß. Ist der verschlüsselte Text lang genug, so kann man damit die Übersetzungstabelle erraten. Enthält der Text beispielsweise sehr viele X-e, so könnte das X für das häufige E stehen. Im neunten Jahrhundert wurden bereits Texte nach diesem Verfahren entschlüsselt.



Häufigkeitsverteilung der verschiedenen Buchstaben in einem längeren deutschen Text.
Quelle: Wikipedia Datei:Alphabet haufigkeit.png, Urheber: Arbeitsgruppe EBUSS (Potsdam, Mosbach) 2004,
dort unter der GNU-Lizenz für freie Dokumentation Version 1.2 oder einer späteren Version veröffentlicht.


Um dieser Entschlüsselungsmethode zu entgehen, kann man versuchen, die Übersetzungstabelle komplizierter zu gestalten und beispielsweise statt Buchstaben Zahlen verwenden, wobei man die überflüssigen Zahlen zufällig als Dummy-Zeichen im Text einstreut. Hier gibt es noch viele weitere Möglichkeiten, die alle ihre Vor- und Nachteile haben. Aber mit dem entsprechenden Aufwand lassen sich doch viele von ihnen über Häufigkeitsanalysen entschlüsseln.

Um statistischen Häufigkeitsanalysen zu entgehen, kann man die Übersetzungstabelle während der Verschlüsselung nach einigen Buchstaben immer wieder ändern. Etwas Ähnliches wurde beispielsweise von Leon Battista Alberti im Jahr 1466 vorgeschlagen. Als Übersetzungstabelle diente dabei die folgende Scheibe, bei der sich die Ringe gegeneinander verdrehen lassen, so dass sich die Buchstabenzuordnung leicht verändern lässt:



Alberti-Scheibe
Quelle: Wikimedia Commons File:UnionCipherDisk.nsa.jpg, Foto von Austin Mills,
dort lizenziert unter der Creative Commons-Lizenz Attribution ShareAlike 2.0.


Zum Entschlüsseln muss man jetzt also wissen, wie die Scheibe aussieht und wann sie wie verdreht wurde -- das ist der Schlüssel. Die abgebildete Scheibe ist allerdings nur eine Form von Caesars Buchstabenverschiebung, bei der die Verschiebezahl n flexibel verändert werden kann. Man könnte die Buchstaben auf einem der Ringe jedoch auch in anderer Reihenfolge anordnen und so eine Übersetzungstabelle mit Caesars Verschiebezahl kombinieren.

Noch geschickter ist es, mehrere komplette Übersetzungstabellen zu haben und immer wieder zwischen diesen zu wechseln. So könnte man im Text versteckt angeben, wann man zu welcher Tabelle wechseln muss. Solche Ideen kamen bereits um das Jahr 1500 herum auf. Verfeinert wurden diese Ideen im Jahre 1585 von Blaise de Vigenere (siehe Wikipedia: Vigenere-Chiffre ). Er verwendete 26 Übersetzungstabellen, durchnummeriert mit den Buchstaben des Alphabetes, wobei die Übersetzungstabellen meist einfache Verschiebetabellen nach dem Vorbild Caesars waren. Ein Schlüsselwort legt nun für jede Buchstabenposition im Ursprungstext fest, mit welcher Tabelle er zu verschlüsseln ist. Ist das Schlüsselwort beispielsweise   QUARK   , so ist der erste Buchstabe des Ursprungstextes mit Tabelle Nummer Q zu verschlüsseln, der zweite Buchstabe mit Tabelle Nummer U usw.. Beim sechsten Buchstaben des Ursprungstextes fangen wir wieder mit Tabelle Q an und so fort. Natürlich sollte man möglichst lange Schlüsselwörter verwenden -- QUARK wäre doch etwas zu kurz. Damit erreicht man recht wirkungsvolle Verschlüsselungen, die allerdings oft auch recht fehleranfällig sind, wenn man sich mal vertut.

Allerdings ist auch die obige Verschlüsselung nach Vigenere nicht absolut sicher. Wenn man nämlich die Länge des Schlüsselwortes kennt, dann weiß man, welche Buchstaben nach derselben Übersetzungstabelle verschlüsselt wurden, und kann dann wieder eine Häufigkeitsanalyse durchführen. Um die Länge des Schlüsselwortes zu erraten, kann man verschiedene statistische Untersuchungen am verschlüsselten Text vornehmen. Man kann beispielsweise nach Wiederholungen identischer Buchstabenfolgen suchen.

Man müsste also ein Schlüsselwort haben, das so lang wie der zu verschlüsselnde Text selbst ist, und das idealerweise aus einer zufälligen Buchstabenkombination besteht. Dann wäre die Suche nach Wiederholungen sinnlos. Dabei braucht man bei einem so langen zufälligen Schlüsselwort komplizierte Übersetzungstabellen gar nicht mehr, sondern es genügt, für jeden Buchstaben des Ursprungstextes Caesars Verschiebe-Regel anzuwenden. Ein A im Schlüsselwort sagt dann: verschiebe um 1, ein B sagt: verschiebe um 2 usw.. Für jeden Buchstaben des Ursprungstextes gibt es dabei einen eigenen Buchstaben des Schlüsselwortes, der angibt, um wieviel der Buchstabe im Alphabet verschoben werden muss. Da das Schlüsselwort zufällig ist, wird jeder Buchstabe des Ursprungstextes zufällig verändert, so dass es keine Angriffspunkte für eine Entschlüsselung gibt, wenn man das Schlüsselwort nur ein einziges Mal zum Verschlüsseln eines Textes verwendet. Dieses Verschlüsselungssystem ist daher so perfekt, wie eine Verschlüsselung nur sein kann. Wegen der Einmal-Verwendung nennt man das Schlüsselwort auch ein One Time Pad.

Das One Time Pad -Verschlüsselungssystem ist zwar theoretisch das sicherste denkbare Verschlüsselungssystem, aber es hat auch offensichtiliche Nachteile. Sehr lange Schlüsselwörter (so lang wie der Text selbst) müssen sowohl dem Sender als auch dem Empfänger bekannt sein und ggf. sicher zwischen diesen übertragen werden, und man braucht ständig neue Schlüsselwörter, die auch noch zufällig sein sollen. Damit ist klar, dass sich das System eher für kurze Nachrichten und sehr hohe Sicherheitsansprüche eignet.

Viele weitere Verschlüsselungssysteme wurden im Laufe der Zeit erfunden, die zumeist Variationen der obigen Ideen waren. Eines der Berühmtesten ist sicher die ENIGMA, die von den Deutschen im zweiten Weltkrieg verwendet wurde.



Eine ENIGMA (Imperial War Museum, London).
Quelle: Wikimedia Commons File:EnigmaMachineLabeled.jpg, fotografiert von Karsten Sperling (2004), dort Public Domain.


Diese Maschine substituiert über mehrere drehbare Walzen Buchstaben, wobei wegen der Walzendrehung für jeden Buchstaben eine eigene Übersetzungstabelle realisiert wird. Trotz ihrer scheinbaren Sicherheit konnte der Code im Jahre 1940 von den Alliierten geknackt werden, wobei auch der uns mittlerweile gut bekannte Alan Turing eine wichtige Rolle spielte. Mehr dazu findet man in Wikipedia: Enigma (Maschine).

Nach dem zweiten Weltkrieg spielten Computer eine immer stärkere Rolle. Es entstand u.a. der Lucifer-Verschlüsselungsstandard, der im Jahr 1976 in den Data Encryption Standard (DES) mündete. Da dieser später den Anforderungen nicht mehr genügte, wurde er im Jahr 2001 durch den Advanced Encryption Standard (AES) ersetzt. DES und AES sind Block-Substitutionsverfahren, d.h. es werden nicht einzelne Buchstaben ersetzt, sondern ganze Buchstabengruppen bzw. ganze Bit-Blöcke (beispielsweise Blöcke von 64 Bit Länge bei DES). Da es bei 64 Bit bis zu 264 verschiedene Blöcke gibt, wird es nur sehr wenige Blöcke geben, die in einem Ursprungstext sowie in dem verschlüsselten Text mehrfach vorkommen. Eine statistische Häufigkeitsanalyse wie bei Buchstaben-Ersetzungen wird bei Blöcken daher scheitern. Allerdings kann man für das Ersetzen der Blöcke keine Übersetzungstabelle wie bei Buchstaben verwenden -- eine solche Tabelle wäre viel zu groß. Statt dessen wendet man einen komplizierten Ersetzungs-Algorithmus an, der seinerseits einen Schlüssel benötigt. Zum Entschlüsseln kehrt man diesen Algorithmus um, wobei derselbe Schlüssel verwendet wird (symmetrisches Verfahren). Der Schlüssel muss also zwischen Sender und allen Empfängern ausgetauscht werden -- eine potentielle Schwachstelle. Abgesehen davon gilt zumindest AES mit hinreichend langem Schlüssel heute (2008) als sicher und wird weltweit überall eingesetzt.

Wie lässt sich nun aber die Schwachstelle mit der Schlüsselübertragung ausschalten? Das ist genau die Stelle, bei der das Faktorisierungsproblem ins Spiel kommt. Schauen wir uns die Details an.


Das RSA-Verfahren:

Die Idee ist folgende: Der Empfänger besitzt einen privaten Schlüssel, den nur er kennt und den er zum Entschlüsseln verwendet. Außerdem besitzt er einen dazu passenden öffentlichen Schlüssel, den er jedem öffentlich zur Verfügung stellt, der ihm eine verschlüsselte Nachricht übersenden möchte. Er ruft also gleichsam in die Welt hinaus:
"Hallo Leute -- wer mir eine verschlüsselte Nachricht schicken möchte, die keiner außer mir wieder entschlüsseln kann, der verwende bitte zum Verschlüsseln den folgenden öffentlichen Schlüssel ..."
Jeder kann also mit dem öffentlichen Schlüssel eine Nachricht verschlüsseln, und nur der Besitzer des dazu passenden privaten Schlüssels kann diese Nachricht wieder entziffern. Zum Entschlüsseln ist der öffentliche Schlüssel also nutzlos. Daher ist keine Schlüsselübertragung notwendig, denn der öffentliche Schlüssel zum Verschlüsseln ist allgemein bekannt, während der geheime private Schlüssel zum Entschlüsseln nur dem Empfänger bekannt sein muss. Man bezeichnet solche Verfahren als asymmetrische Verfahren oder auch als Public-Key-Verfahren.

Das bekannteste Verfahren zur Umsetzung dieser Idee ist das RSA-Verfahren, das 1977 entwickelt wurde und bis heute (2008) breite Anwendung findet. Das Verfahren erfordert ein gewisses mathematisches Verständnis. Daher wollen wir schrittweise vorgehen und uns das Verfahren an einem vereinfachten Beispiel anschauen (das Beispiel stammt aus Wikipedia: RSA-Kryptosystem ).

Wir wollen also einen Text verschlüsseln. Da es sich bei dem RSA-Verfahren um einen Rechenalgorithmus handelt, müssen wir Teile des Textes zunächst in Zahlen umwandeln. In unserem Beispiel nehmen wir einfach die Position im Alphabet: A = 01, B = 02, ..., Z = 26 . In der Realität wird man analog zum DES- und AES-Verfahren (siehe oben) ganze Textblöcke durch Zahlen darstellen und so mit größeren Zahlen arbeiten. Das verringert die Gefahr, das der Code durch Häufigkeitsanalysen geknackt werden kann.

Um eine solche Zahl (nennen wir sie K für Klartext) zu verschlüsseln, brauchen wir den öffentlichen Schlüssel, den uns der Empfänger zur Verfügung stellt. Dieser Schlüssel besteht aus zwei natürlichen Zahlen:

öffentlicher Schlüssel:
  • RSA-Modul   N   , z.B.   N = 143
  • Verschlüsselungsexponent   e   , z.B.   e = 23

In der Realität verwendet man natürlich weit größere Zahlen, beispielsweise einen 5-stelligen Exponenten   e   und ein Modul   N   mit mehreren Hundert Stellen (d.h. N ist größer als die Zahl der Atome im sichtbaren Universum). Wie man auf ein passendes N und e kommt, sehen wir uns später an. Jedenfalls ist e deutlich kleiner als N. Damit können wir nun die Klartextzahl nach der folgenden Formel verschlüsseln:

Verschlüsselung:
  • Die Klartext-Zahl   K   wird mit Hilfe der öffentlichen Schlüsselzahlen   e   und   N   nach der folgenden Formel in die verschlüsselte Zahl   C   umgerechnet:

      C   =   Ke   mod   N

    d.h.   K   wird e-mal mit sich selbst multipliziert und dann wird ein möglichst großes Vielfaches von N abgezogen, d.h. es wird der Rest ermittelt, der bei der Division durch   N   übrig bleibt (das ist die Bedeutung von "mod"). Das Verschlüsselungsergebnis   C   kann demnach nur Werte zwischen   0   und   N − 1   annehmen, d.h. N darf für eine Verschlüsselung nicht zu klein sein.

In unserem Beispiel ergibt die Verschlüsselung des Buchstabens "G" (also 07 ):   C   =   723 mod 143   . Dabei müssen wir glücklicherweise die riesige Zahl   723   nicht wirklich berechnen, sondern es gibt dazu ein effizientes Rechenverfahren, das wir anwenden wollen (siehe Wikipedia: Diskrete Exponentialfunktion sowie Wikipedia: Schnelles Potenzieren ). Insbesondere muss man nicht zuerst die komplette Potenz bilden, sondern man kann zwischendurch auch   mod N   anwenden, um die Zahl wieder zu verkleinern, bevor man weitere Faktoren K heranmultipliziert. Man kann nämlich jedes zu potenzierende Zwischenergebnis x schreiben als   x   =   (x mod N)   +   ein passendes Vielfaches von N   und erhält beim Potenzieren dann

  xm mod N   =  
  =   ( (x mod N)   +   ein passendes Vielfaches von N )m   mod N   =  
  =   ( (x mod N)m   +   ein anderes Vielfaches von N )   mod N   =  
  =   (x mod N)m   mod N

Analog ist es auch beim Multiplizieren:

  (a * b * c) mod N   =   ( [(a * b) mod N] * c) mod N   =   (a * [(b * c) mod N] ) mod N

denn Vielfache von N werden durch das Multiplizieren mit anderen natürlichen Zahlen immer nur zu anderen Vielfachen von N, die am Schluss sowieso alle abgezogen werden. Man kann sie also auch vorher jederzeit in den Klammern schon wegnehmen. Die Multiplikation modulo N erfüllt demnach das Assoziativgesetz (und natürlich auch das Kommutativgesetz). Wir werden unten noch sehen, dass man das nutzen kann, um eine endliche Gruppe aufzubauen, die diese Multiplikation modulo N als Gruppenoperation enthält. Die Elemente dieser Gruppe werden alle Zahlen von 1 bis N sein, die teilerfremd zu N sind. Man spricht von der multiplikativen Gruppe modulo N und schreibt sie als   ZN*   . Die Eigenschaften dieser Gruppe sind letztlich der Grund dafür, dass das RSA-Verfahren funktioniert -- schließlich ist die Verschlüsselung ja gerade die e-fache Gruppenmultiplikation von K mit sich selbst. Mehr dazu weiter unten.

Man kann also bei der zu potenzierenden Zahl jederzeit ein möglichst großes Vielfaches des Moduls N abziehen, denn dieses würde beim Potenzieren oder Multiplizieren seinerseits nur ein anderes Vielfaches von N ergeben, das am Schluss wegen   mod N   sowieso wieder abgezogen wird.
Das Potenzieren geht am schnellsten, wenn wir es durch mehrfaches Quadrieren geeignet ersetzen und nach jedem Quadrieren   mod N   anwenden, um ein möglichst großes Vielfaches von N loszuwerden. In unserem Beispiel (Verschlüsselung des Buchstabens   "G" = 07   über die Formel   C   =   723 mod 143   ) sieht das so aus (wer will, kann diese Details gerne überspringen -- ich wollte es aber selber einmal explizit durchrechnen): Den Exponenten 23 können wir schreiben als   23   =   16 + 4 + 2 + 1   . Das entspricht der Binärzahl   10111   . Entsprechend können wir 23 auch schreiben als   23   =   ((( 1*2 + 0 )*2 + 1 )*2 + 1 )*2 + 1   =   (( 2*2 + 1 )*2 + 1 )*2 + 1   . Bei Potenzieren mit 23 entsteht so (durch Anwenden der Potenzgesetze von links nach rechts):

  723   =  
  =   7 (( 2*2 + 1 )*2 + 1 )*2 + 1   =  
  =   7 (( 2*2 + 1 )*2 + 1 )*2   * 7   =  
  =   ( 7 ( 2*2 + 1 )*2 + 1 )2   * 7   =  
  =   ( 7 ( 2*2 + 1 )*2   * 7 )2   * 7   =  
  =   (( 7 2*2 + 1 )2   * 7 )2   * 7   =  
  =   (( 7 2*2   * 7 )2   * 7 )2   * 7   =  
  =   (( (72)2   * 7 )2   * 7 )2   * 7

(Gott sei Dank -- so steht es auch in Wikipedia: RSA-Kryptosystem drin). Rechnen wir das nun modulo N = 143 aus, wobei wir in jedem Schritt versuchen, ein möglichst großes Vielfaches von N = 143 abzuziehen (kann man natürlich gerne beim Lesen überspringen -- solche Rechnungen macht normalerweise ein kleines Computerprogramm):

  723   mod 143   =  
  =   (( (72)2   * 7 )2   * 7 )2   * 7   mod 143   =  
  =   (( 2401   * 7 )2   * 7 )2   * 7   mod 143   =  
  =   (( (2401 − 16*143)   * 7 )2   * 7 )2   * 7   mod 143   =  
  =   (( 113   * 7 )2   * 7 )2   * 7   mod 143   =  
  =   ( 7912   * 7 )2   * 7   mod 143   =  
  =   ( (791 − 5*143)2   * 7 )2   * 7   mod 143   =  
  =   ( 762   * 7 )2   * 7   mod 143   =  
  =   ( 5776   * 7 )2   * 7   mod 143   =  
  =   ( (5776 − 40*143)   * 7 )2   * 7   mod 143   =  
  =   ( 56 * 7 )2   * 7   mod 143   =  
  =   3922   * 7   mod 143   =  
  =   (392 − 2*143)2   * 7   mod 143   =  
  =   1062   * 7   mod 143   =  
  =   11236   * 7   mod 143   =  
  =   (11236 − 78*143)   * 7   mod 143   =  
  =   (11236 − 78*143)   * 7   mod 143   =  
  =   82   * 7   mod 143   =  
  =   574   mod 143   =  
  =   (574 − 4*143)   =  
  =   2

Uff -- ich kann es kaum glauben, dass ich mich nicht verrechnet habe, aber dieses Ergebnis steht auch in Wikipedia: RSA-Kryptosystem so drin! Man kann die obige Verschlüsselungsrechnung also tatsächlich auch von Hand mit einem Taschenrechner und etwas Geduld durchziehen.

Da man in die Verschlüsselungsformel   C   =   Ke   mod N   die Basis K hineinsteckt und dazu das Ergebnis C berechnet, spricht man von einer Potenzierung modulo N. Dabei handelt es sich um eine sogenannte Einwegfunktion, d.h. bei gegebenem Exponenten e und Modul N kann man aus der Basis K mit einem Computer relativ leicht das Ergebnis C ausrechnen, aber es gibt (bei größeren e und N) kein effektives Verfahren, um aus dem Ergebnis C wieder die ursprüngliche Basis K zu berechnen, selbst wenn wir den Exponenten e und das Modul N kennen. Wir haben es also tatsächlich mit einer Verschlüsselung zu tun, die sich selbst bei Kenntnis des öffentlichen Schlüssels (e und N) nicht mit heutigen Computern umkehren lässt. Das hat damit zu tun, dass die Potenzierung modulo N fast chaotische Sprünge macht -- die Ergebnisse für C sehen für verschiedene Eingabewerte K wie zufällig aus, und genau das soll eine Verschlüsselung ja auch tun. Die Verschlüsselung wirkt also wie eine fast zufällige Verwürfelung, wie die folgende Beispielgrafik für   e = 7   und   N = 15   zeigt:



Die Verschlüsselungsfunktion (Übersetzungstabelle) für den Verschlüsselungs-Exponenten   e = 7   und das Modul   N = 15   (also   C = K7 mod 15   ). Die Funktion macht fast zufällige Sprünge, wobei wegen der kleinen Werte für e und N noch gewisse Regelmäßigkeiten erkennbar sind. Die Ergebniswerte für C wiederholen sich, sobald das zu verschlüsselnde K größer als N wird. Bei einer realistischen Verschlüsselung braucht man daher ein sehr großes N und ein nicht allzu kleines e. Das Modul N sollte größer sein als alle Werte von K, die man verschlüsseln will. Die Ergebnisse für C sind sowieso alle kleiner als N (wegen   mod N ).


Man kann sich die Potenzierung modulo N auch gut an einem Rad mit N Speichen voranschaulichen, wobei wir die Speichen wie bei einer Uhr von 0 bis N − 1 durchnummerieren (die N-te Speiche ist dann wieder identisch mit der 0-ten Speiche). Die Nummern der Speichen schreiben zusätzlich auf ein Gummiband, das wir einmal um das Rad wickeln, so dass die Nummern über den passenden Speichen liegen. Bei einer Multiplikation mit K modulo N geschieht nun Folgendes: Wir nehmen das Gummiband ab, strecken es um das K-fache (das entspricht der Multiplikation mit K) und wickeln es K-mal um das Rad (das entspricht der Operation modulo N). Die Zahlen auf dem Gummiband landen dann an neuen Speichenpositionen, die genau das Ergebnis der Multiplikation dieser Zahlen mit K modulo N angeben. Wenn wir das Ganze e mal wiederholen, landet die Zahl 1 des Gummibandes genau bei Speichenposition   C = Ke mod N   . Das Gummiband wird dabei e mal um das K-fache gestreckt und nach jeder Streckung (oder alternativ am Schluss) wieder komplett um das Rad gewickelt. Das wirkt wie wiederholtes Ausrollen und Falten bei einem Knet-Kuchenteig: Nummern, die nahe beieinander lagen, entfernen sich durch das Strecken voneinander und landen durch das Aufwickeln fast wie zufällig an neuen Orten. Letztlich werden die Zahlen auf dem Gummiband dabei kräftig durchgemischt. Da bei einer realen Verschlüsselung e eine fünfstellige Zahl ist und das Rad extrem viele Speichen hat (mehr als es Atome im sichtbaren Universum gibt), wird man nach den vielen tausend Streckungen und Wiederaufwicklungen aus der Endposition C der 1-Speiche kaum noch ermitteln können, um welches K man bei jeder Drehung dehnen muss, um gerade diese Endposition zu erreichen. Man kann höchstens noch verschiedene K ausprobieren, und das ist bei der großen Zahl der Speichen und damit den extrem vielen möglichen K-Werten (die zwischen 2 bis N − 1 liegen können) aussichtslos. Dieses Bild eines Rades wird uns weiter unten bei der multiplikativen Gruppe modulo N noch einmal wiederbegegnen.



So sieht das Rad für das Modul   N = 15   aus. Was bei einer Multiplikation mit 4 geschieht, zeigen die äußeren Zahlen: Die 1 landet über Speiche 4, die 2 über Speiche 8, die 3 über Speiche 12, die 4 über Speiche 1 (denn 4 mal 4 ist 16, was nach Abzug von 15 dann 1 ergibt), die 5 über Speiche 5 und so weiter. Man läuft gleichsam im Uhrzeigersinn um das Rad herum und lässt alle 4 Speichen die nächste Zahl fallen. Die Farben sollen dabei darstellen, in welchem Umlauf man sich gerade befindet. Interessant ist, dass keine Speiche doppelt getroffen wird. Das liegt daran, dass 4 teilerfremd zu 15 ist -- mehr dazu unten bei der multiplikativen Gruppe modulo N.


Wie aber soll der Empfänger nun die Nachricht entschlüsseln, also aus C wieder K berechnen? Alleine mit der Kenntnis des öffentlichen Schlüssels N und e geht das nicht mit realen Mitteln, denn sonst wäre die Verschlüsselung ja unsicher. Das Entschlüsseln geht, weil die obige Einwegfunktion eine Hintertür (Falltür, Trapdoor) bereithält -- zumindest wenn man bestimmte Module N und dazu passende Exponenten e wählt und eine Zusatzinformation zu N und e besitzt. Und das tut der Empfänger, der e und N als öffentlichen Schlüssel zur Verfügung gestellt hat. Er wählt nämlich N und e nicht zufällig, sondern er startet mit zwei großen Primzahlen p und q und multipliziert diese, um das Modul N zu berechnen (zum öffentlichen Exponenten e kommen wir gleich):

  N   :=   p q

Im Gegensatz zu N und e werden p und q aber nicht veröffentlicht, sondern vom Empfänger geheim gehalten -- mit ihrer Hilfe kann er nämlich die verschlüsselte Nachricht wieder entschlüsseln (wie, kommt gleich). Und hier genau schlägt das Faktorisierungsproblem zu: Wäre es einfach, auch ein großes N in seine Primfaktoren zu zerlegen, so könnte jeder aus dem öffentlichen Schlüssel N die beiden geheimen Primfaktoren p und q errechnen und so ebenfalls die Nachricht entschlüsseln. Nach heutigem Wissen ist aber das Berechnen der Primfaktoren p und q bei großen Zahlen zu aufwändig für normale Computer, so dass nur der Empfänger die Nachricht entschlüsseln kann (er hat ja p und q), nicht aber alle anderen, die nur das Produkt   N   :=   p q   kennen.

Bleibt noch der zweite öffentliche Schlüssel, der Exponent e. Diesen muss der Empfänger passend zu den beiden geheimen Primzahlen p und q wählen. Dazu braucht er zunächst eine Hilfsgröße, nämlich das Produkt der beiden Zahlen unterhalb von p und q, also   (p − 1) (q − 1)   . Dieses Produkt nennt man auch Eulers Phi-Funktion und schreibt

  φ(N)   :=   (p − 1) (q − 1)

Diese Größe hat auch eine wichtige anschauliche Bedeutung: φ(N) ist die Anzahl Zahlen von 1 bis N, die teilerfremd zu N sind, d.h. deren Primfaktorzerlegung für unser spezielles N weder die Primzahl p noch die Primzahl q enthält. Dass das so ist, kann man so sehen: Als gemeinsame Teiler mit   N   :=   p q   kommen nur die beiden Primzahlen p und q in Frage (denn N hat keine anderen Teiler). Folgende Zahlen bis N haben den gemeinsamen Teiler p mit N :   1*p, 2*p, 3*p, ... , q*p   . Das sind p Zahlen. Analog haben folgende Zahlen bis N den gemeinsamen Teiler q mit N :   1*q, 2*q, 3*q, ... , p*q   . Das sind q Zahlen. Allerdings haben wir p*q = q*p doppelt gezählt -- es gibt also insgesamt   p + q − 1   Zahlen bis N, die nicht teilerfremd zu N sind. Ziehen wir das von N ab, so haben wir die Anzahl der Zahlen bis N, die teilerfremd zu N sind, also
  N − (p + q − 1)   =   p q − p − q + 1   =   (p − 1) (q − 1)   =   φ(N)  

Für den öffentlichen Exponenten   e   nimmt der Empfänger nun irgendeine Zahl unterhalb von φ(N), die keinen gemeinsamen Teiler mit φ(N) haben darf. Die Primfaktorzerlegung von   e   muss also aus komplett anderen Primzahlen bestehen als die von φ(N) . Das brauchen wir gleich für den sogenannten Entschlüsselungsexponenten. Meist nimmt man für   e   einfach eine nicht allzu große Primzahl, die in der Primfaktorzerlegung von φ(N) nicht vorkommt.

Wie geht nun die Entschlüsselung mit Hilfe der geheimen Primzahlen p und q vor sich? Wäre die Verschlüsselungsfunktion einfach die normale Exponentialfunktion   C   =   Ke   (also ohne dass ein möglichst großes Vielfaches von N abgezogen wird), dann könnte man einfach einen Entschlüsselungsexponenten   d = 1/e   wählen (also   e d = 1   ) und hätte die Entschlüsselung   K   =   Cd   =   C1/e   . Das wäre natürlich keine besonders sinnvolle Verschlüsselung gewesen, denn zum Entschlüsseln bräuchten wir nur den Kehrwert des öffentlichen Exponenten e zu bilden. Daher wird beim Verschlüsseln noch ein möglichst großes Vielfaches von N abgezogen, was beim obigen Rad dem Aufwickeln des Gummibandes entspricht. Statt   C   =   Ke   wird also   C   =   Ke mod N   zum Verschlüsseln verwendet. Das Interessante ist nun, dass man auch die anderen Formeln ähnlich modifizieren kann, so dass alles zusammenpasst (warum das so geht, kommt später): Aus   e d = 1   und   K   =   Cd   wird:

Entschlüsselung:

  K   =   Cd   mod   N

wobei der geheime Entschlüsselungsexponent   d   (wie e ebenfalls eine natürliche Zahl) die folgende Formel erfüllen muss:

  (e d)   mod   φ(N)   =   1

Das Produkt der Exponenten e mal d muss also gleich Eins plus einem Vielfachen von φ(N) sein. Wie die Verschlüsselung erfolgt also auch die Entschlüsselung durch Potenzierung modulo N, wobei man für die Bestimmung des Entschlüsselungsexponenten d die Zahl   φ(N)   :=   (p − 1) (q − 1)   braucht. Dafür braucht man aber die beiden Primfaktoren p und q. Der Empfänger kennt diese und hat deshalb keine Probleme beim Entschlüsseln, aber alle anderen, die nur die öffentlichen Schlüssel e und N kennen, müssen dafür das Faktorisierungsproblem für N lösen, also p und q berechnen. Da das auf heutigen Computern bei großen Zahlen aussichtslos ist, scheitern sie und können den Entschlüsselungsexponenten d nicht berechnen.

Nun wird auch klar, warum der Verschlüsselungsexponent e teilerfremd zu φ(N) sein muss. Würde e einen gemeinsamen Teiler mit φ(N) haben (nennen wir ihn g), dann wäre e ein Vielfaches von g und auch das Produkt   e d   wäre ein Vielfaches von g. Die "mod φ(N)"-Operation zieht davon dann ein anderes Vielfaches von g ab (denn φ(N) ist ja auch ein Vielfaches von g), so dass am Schluss irgendein Vielfaches von g oder aber Null übrig bleibt. Nun ist g aber größer als Eins (es soll kein trivialer Teiler sein) und somit kann am Schluss nie genau Eins übrig bleiben, was aber gefordert ist. Diese Argumentation wird uns unten beim Thema inverses Element noch einmal begegnen.

Schauen wir uns nochmal unser obiges Beispiel aus Wikipedia: RSA-Kryptosystem an. Wie hat der Empfänger den öffentlichen Schlüssel   N = 143   und   e = 23   hergestellt? Das ist bei so kleinen Zahlen nicht schwer herauszufinden: Er hat die beiden Primzahlen   p = 11   und   q = 13   verwendet, so dass   N   =   11 * 13   =   143   ist.
Für den öffentlichen Verschlüsselungsexponenten   e   brauchen wir Eulers Phi-Funktion   φ(143)   =   10 * 12   =   120   . Die Zahl   e   muss nun kleiner als φ(143) und teilerfremd zu φ(143) sein. Die Primfaktorzerlegung von φ(143) ist   φ(143)   =   120   =   2 * 2 * 2 * 3 * 5   . Die Primzahl   e = 23   erfüllt also die Bedingungen (natürlich gibt es noch mehr Möglichkeiten).
Oben ergab die Verschlüsselung des Beispiel-Buchstabens "G" (also 07 ) den Wert   C   =   723 mod 143   =   2   . Zum Entschlüsseln brauchen wir den Entschlüsselungsexponenten d, der die Formel   (e d)   mod   120   =   1   erfüllen muss. Das kann man effektiv mit dem erweiterten euklidischen Algorithmus auswerten -- Details lassen wir hier weg (mehr dazu siehe unten beim Thema inverses Element der Gruppe ZN* und im Anhang ganz unten). Als Ergebnis erhält man   d = 47   (wir verzichten auf eine Überprüfung). Die Entschlüsselung lautet dann also   K   =   247 mod 143   =   7   , was man mit dem oben bei der Verschlüsselung beschriebenen Rechenverfahren nachrechnen kann.

Dass die Ver- und Entschlüsselung funktioniert, können wir noch einmal an dem sehr einfachen Beispiel mit   e = 7   und   N = 15   von oben nachvollziehen. Hier sieht man noch leicht, dass zu   N = 15   die beiden Primfaktoren   p = 5   und   q = 3   gehören. Dann ist   φ(15) = 4*2 = 8   . Der Verschlüsselungsexponent   e = 7   ist dann wie verlangt kleiner als φ(15) und außerdem teilerfremd dazu. Wie sieht dann ein passender Entschlüsselungsexponent d aus? Er muss   (7 * d)   mod   8   =   1   erfüllen. Der Wert   d = 7   erfüllt den Zweck, denn   7*7 = 49 = 6*8 + 1   . Zufällig ist also hier   e = d   . Die folgende mit einem Tabellenkalkulationsprogramm berechnete Tabelle zeigt, dass diese Entschlüsselung in diesem Beispiel funktioniert, solange man mit dem Startwert K unterhalb von N bleibt (danach wiederholt sich die Verschlüsselungsfunktion ja, so dass die Entschlüsselung nur unterhalb von N funktionieren kann):



Bleibt dennoch die Frage: Warum funktionieren die obigen Ver- und Entschlüsselungs-Formeln eigentlich? Auf Anhieb ist das nämlich keineswegs zu sehen! Tasten wir uns also schrittweise heran: Verschlüsseln ging mit   C   =   Ke   mod   N   . Setzen wir dies in die Entschlüsselungsformel   K   =   Cd   mod   N   ein, so folgt

  K   =   Cd   mod   N   =   (Ke mod N)d   mod   N   =   Ke d   mod   N

wobei wir im letzten Schritt wieder die Eigenschaften der Multiplikation modulo N verwendet haben, die wir von oben schon kennen: Es ist egal, ob man in Zwischenprodukten oder erst am Schluss ein möglichst großes Vielfaches von N abzieht, denn beim Multiplizieren erzeugen Vielfache von N nur andere Vielfache von N, die aber am Schluss sowieso alle wegfallen. So sind wir oben auf die Formel   xm mod N   =   (x mod N)m   mod N   gekommen, in die wir nur noch   x = Ke   und   m = d   einsetzen müssen, um den letzten Schritt zu reproduzieren.

Das obige Verfahren funktioniert also, wenn die Formel

  K   =   Ke d   mod   N

gilt. Schreiben wir auch diese Formel noch etwas um, indem wir die Bedingung   (e d)   mod   φ(N)   =   1   schreiben als   (e d)   =   b φ(N) + 1   für eine passende natürliche Zahl b (inclusive Null). Damit ist

  Ke d   mod   N   =   Kb φ(N) + 1   mod   N   =   (K * ( Kφ(N) )b )   mod   N   =:   (*)

Nun kommt der entscheidende Schritt: Nach dem Satz von Euler gilt für teilerfremde Zahlen K und N die Beziehung

Satz von Euler:

  Kφ(N)   mod N   =   1  

Die Beweisskizze dazu kommt gleich. Man kann sich sogar überlegen, dass K nicht unbedingt teilerfremd zu N sein muss, damit das RSA-Verfahren funktioniert -- wir lassen diese Bedingung trotzdem hier stehen, denn man kann die Primzahlen p und q immer groß genug wählen, so dass jedes zu kodierende K kleiner als p und q und somit teilerfremd zu N = p*q ist.

Anders ausgedrückt sagt der Satz von Euler:   Kφ(N)   =   a' N + 1   mit passendem a'. Potenzieren mit b ergibt dann   ( Kφ(N) )b   =   (a' N + 1)b   =   1 + Vielfache von N   . Multipliziert mit K ergibt das   K + (andere) Vielfache von N   . Also haben wir:

  (*)   =   (K + Vielfache von N)   mod   N   =   K

Die Formel   K   =   Ke d mod N   ist damit bewiesen, d.h. das RSA-Verfahren funktioniert. Und nun kommen wir wie versprochen zur


Beweisskizze des Satzes von Euler:

(die hier vorgestellte Beweisskizze findet man verkürzt in Wikipedia: Satz von Euler). Schauen wir uns die sogenannte multiplikative Gruppe modulo N an, die wir oben bereits kurz erwähnt und mit   ZN*   bezeichnet hatten. Diese Gruppe besteht aus allen natürlichen Zahlen von 1 bis N, die teilerfremd zu N sind (wobei 1 als teilerfremd zu N zählt). Von oben wissen wir bereits, dass es   φ(N)   solcher Zahlen gibt. Beim Beispiel   N = 15 = 3 * 5   hätten wir also

  Z15*   =   { 1, 2, 4, 7, 8, 11, 13, 14 }

d.h. alle Vielfachen von 3 und 5 lassen wir weg. Damit enthält   Z15*   insgesamt 8 Elemente, so wie es   φ(15) = 2 * 4   angibt.

Wir können diese Gruppe wieder mit unserem Rad von oben darstellen. Dabei lassen wir jetzt aber alle Speichen weg, die nicht teilerfremd zu N = 15 sind:



Die Gruppe   Z15*   , dargestellt als Rad. Die hellblauen Speichen gehören nicht zur Gruppe, da die entsprechenden Speichenpositionen einen gemeinsamen Teiler mit   N = 15   haben (entweder 3 oder 5). Die Null ist ebenfalls nicht dabei, da sie kein inverses Element bei der Multiplikation besitzt.


Als Gruppenoperation (nennen wir sie   ο   ) nehmen wir die übliche Multiplikation, aber Modulo N, d.h. es wird noch ein möglichst großes Vielfaches von N abgezogen:

  a ο b   :=   (a * b)   mod N

Nun müssen wir natürlich zunächst nachweisen, dass diese Gruppenoperation die Eigenschaften aufweist, die sie haben muss (siehe z.B. Wikipedia: Gruppentheorie ; kann man auch gerne einfach glauben und überspringen):

Wir wissen also jetzt, dass   ZN*   eine endliche Gruppe ist, und können das beim Beweis verwenden. Dazu nehmen wir irgendein festes   K   aus   ZN*   heraus und multiplizieren alle Elemente von   ZN*   mit diesem K (wobei wir natürlich noch "mod N" anwenden). Da das genau die Gruppenoperation ist, entsteht so jeweils wieder ein Element von   ZN*   . Es entsteht sogar für jedes Startelement ein anderes Ergebniselement, denn wenn zwei Ergebniselemente   K ο a   und   K ο b   gleich wären, so kann man mit dem inversen Element von K multiplizieren (mod N) und erhält   a = b   , d.h. nur gleiche Startelemente ergeben auch gleiche Ergebniselemente. Die Multiplikation mit K (mod N) vertauscht also lediglich die Elemente von   ZN*   . Schauen wir uns das an unserem Beispiel   Z15*   mit   K = 2   an:

  vorher:              { 1, 2, 4, 7, 8, 11, 13, 14 }  
  mal 2 mod 15:   { 2, 4, 8, 14, 1, 7, 11, 13 }  

Das kann man auch sehr schön an unserem ersten Rad-Bild weiter oben erkennen, bei dem die Multiplikation mit 4 (mod 15) zu einer Umsortierung der Speichennummern führt.
Was geschieht nun, wenn wir alle Ergebniselemente der unteren Zeile miteinander multiplizieren? Nun, dann enthält dieses Produkt alle Startelemente von   ZN*   (obere Zeile), nur in anderer Reihenfolge. Bezeichnen wir die Elemente von   ZN*   mit   ri   , wobei   i   von   1   bis   φ(N)   läuft (denn die Menge enthält ja   φ(N)   Elemente). Die mit K multiplizierten Elemente (mod N) sind dann   K ο ri   und für das Produkt gilt:

  r1 * r2 * ... * rφ(N)   =   (K ο r1) * (K ο r2) * ... * (K ο rφ(N))

denn die Faktoren   K ο ri   rechts umfassen zusammen alle Elemente   rj   , nur in anderer Reihenfolge. Nun können wir auf beiden Seiten "mod N" anwenden und so aus der normalen Multiplikation die Gruppenoperation machen. Da diese kommutativ ist, dürfen wir die Faktoren rechts vertauschen und so die Faktoren K nach rechts ziehen. Da K insgesamt φ(N) mal im Produkt vorkommt, entsteht so:

  r1 ο r2 ο ... ο rφ(N)   =   (K ο r1) ο (K ο r2) ο ... ο (K ο rφ(N))   =   r1 ο r2 ο ... ο rφ(N)   ο   (Kφ(N) mod N)

Da es zu jedem   ri   ein inverses Element gibt, können wir auf beiden Seiten mit dem Produkt aller inversen Elemente multiplizieren (mod N) und so das Produkt der   ri   entfernen. Übrig bleibt:

  1   =   Kφ(N)   mod N

Das ist genau der Satz von Euler. Der Beweis war gar nicht so schwer, wenn man die Gruppenstruktur von   ZN*   verwendet, wobei der entscheidende Punkt die Existenz der inversen Elemente ist. Letztlich haben wir in dem obigen Beweis gezeigt, dass bei einer endlichen Gruppe mit m Elementen das m-fache Gruppenprodukt eines Elementes mit sich selbst gleich 1 (dem neutralen Element) ist. Das ist ein allgemeiner Satz aus der Theorie endlicher Gruppen, und der Satz von Euler ist lediglich die Anwendung dieses Satzes auf die Gruppe   ZN*   , wobei dann   m = φ(N)   ist.


Wie steht es mit der Sicherheit des RSA-Verfahrens? Das RSA-Verfahren ist sicher, solange es mit den verfügbaren Computern und Algorithmen in der Praxis aussichtslos ist, aus der Kenntnis des öffentlichen Schlüssels N die beiden Primfaktoren p und q zu berechnen, also N in p mal q zu zerlegen und damit das Faktorisierungsproblem für große N zu lösen. Damit hatten wir uns bereits in Kapitel 5.8 genauer beschäftigt. Bis heute ist kein Algorithmus bekannt, der das Faktorisierungsproblem auf einem gewöhnlichen Computer in polynomialer Zeit löst, so dass die Lösungszeit nur polynomial mit der Größe von N wächst. Daher gilt das RSA-Verfahren als sicher, wenn man für die Primzahlen p und q Zahlen mit mehreren hundert Dezimalstellen verwendet. Für den Verschlüsselungsexponenten e verwendet man häufig die Primzahl   e = 216 + 1 = 65537   . Im Normalfall ist diese Primzahl dann kein Teiler von φ(N), so wie verlangt. Diese Zahl für e ist groß genug, um ein Knacken der Verschlüsselung zu verhindern, aber zugleich klein genug, um eine noch relativ effiziente Verschlüsselung zu erlauben.

Auf einem Quantencomputer gibt es dagegen einen polynomialen Faktorisierungs-Algorithmus: den Shor-Algorithmus (siehe Kapitel 5.8 ). Wenn es also eines Tages gelingt, brauchbare Quantencomputer zu bauen, die große Zahlen in vernünftiger Zeit faktorisieren können, dann wäre das RSA-Verfahren für die Verschlüsselung damit unbrauchbar geworden. Dasselbe gilt, falls doch noch jemand einen polynomialen Faktorisierungsalgorithmus für heutige Computer findet -- es ist nämlich nicht bewiesen, dass es keinen solchen Algorithmus gibt, auch wenn heute fast jeder davon ausgeht.

Im realen Leben verwendet man das RSA-Verfahren meist nicht für die Verschlüsselung längerer Texte, denn es ist etwa 1000 mal langsamer als die weiter oben beschriebenen DES und AES-Verfahren, die aber als symmetrische Verfahren einen geheimen Schlüsselaustausch brauchen. Genau für diesen Schlüsselaustausch kann man aber nun das RSA-Verfahren verwenden und dann anschließend mit dem schnelleren AES-Verfahren längere Texte ver- und entschlüsseln. Auch komplexere Mischverfahren werden in der Praxis angewendet. Ein Beispiel ist das Pretty-Good-Privacy-Verschlüsselungsverfahren, das man beispielsweise für Emails anwenden kann.


Quantenkryptographie:

Gibt es ein absolut sicheres Verfahren, um einen geheimen Schlüssel (oder gar ein komplettes One-Time-Pad, siehe oben) zwischen zwei Parteien auszutauschen? Die Natur selbst könnte ein solches Verfahren zur Verfügung stellen, wenn man sich ihre Quanteneigenschaften zu Nutze macht. Schauen wir uns das am Beispiel verschränkter Teilchenpaare genauer an (es gibt hier auch andere Vorgehensweisen):

Aus Kapitel 5.8 wissen wir, wie ein Quantensystem aus zwei Teilchen beschrieben werden kann: mit Hilfe einer Tabelle, die die möglichen Messwerte für beide Teilchen gemeinsam auflistet und die zu jeder Messwertkombination einen Pfeil enthält. Dieser Pfeil ist die Wahrscheinlichkeitsamplitude für die jeweilige Messwertkombination. Seine quadrierte Länge gibt die Wahrscheinlichkeit dafür an, die zugehörige Messwertkombination für beide Teilchen bei einer Messung vorzufinden. Die Pfeilorientierungen für die verschiedenen Messwertkombinationen relativ zueinander werden bei sogenannten Interferenzen wichtig, d.h. wenn mehrere Messwertkombinationen als ununterscheidbare Möglichkeiten zu einem anderen Messergebnis beitragen (man denke an das berühmte Doppelspalt-Experiment).

Verschränkung bedeutet nun, dass es Korrelationen im Verhalten der beiden Teilchen gibt: das Verhalten des einen Teilchens hängt vom Verhalten des anderen Teilchens ab und umgekehrt. Es gibt sogar die Möglichkeit, dass sich beide Teilchen genau entgegengesetzt zueinander verhalten, wie die folgende Tabelle zeigt (die uns schon öfter begegnet ist):



Quantenzustand eines Teilchenpaars mit Gesamtspin Null. Die beiden Teilchen verhalten sich genau entgegengesetzt zueinander, d.h. wenn man für das eine Teilchen den Spinwert   Spin(1) = +1/2   in einer vorgegebenen Richtung findet, so muss das andere Teilchen den Spinwert   Spin(2) = − 1/2   in diese Richtung haben und umgekehrt. Dagegen gibt es für die erste und vierte Spalte überhaupt keinen Pfeil, d.h. die entsprechende Wahrscheinlichkeit ist Null -- die beiden Teilchen haben nie gleiche Spinwerte. Mehr zu diesem merkwürdigen Verhalten verschränkter Teilchen siehe in Das Unteilbare, Kapitel 3.8 (John Steward Bell und die Suche nach verborgenen Informationen).


Man kann nun dieses entgegengesetzte Verhalten von Teilchenpaaren dazu verwenden, um einen geheimen Schlüssel für zwei Partner zu erzeugen (es gibt auch andere Verfahren, die mit nur einem Teilchen arbeiten, aber die wir wollen wir hier nicht betrachten). Nehmen wir dazu eine Teilchenquelle, die solche entgegengesetzten Teilchenpaare erzeugt, wobei das eine Teilchen jeweils vom ersten Partner und das zweite Teilchen vom zweiten Partner aufgefangen und sein Spin von beiden Partnern in derselben Richtung gemessen wird (sagen wir in z-Richtung). Das kann man beispielsweise durch ein Magnetfeld in diese Richtung machen, wobei das Teilchen dann je nach Spinwert entweder nach oben oder nach unten abgelenkt wird, wie das folgende Bild zeigt:



Man kann eine Teilchenquelle aufbauen, die zwei Teilchen in jeweils entgegengesetzte Richtungen aussendet, so dass sich die Teilchen beim Durchgang durch ein inhomogenes Magnetfeld entgegengesetzt zueinander verhalten.

Statt Teilchen mit Spin 1/2 und Magnetfelder kann man auch Photonen und Polarisationsfilter verwenden. Das wäre nur eine andere technische Umsetzung -- das dahinterstehende Prinzip bleibt dasselbe. Übrigens kann auch durchaus einer der beiden Partner die Teilchenquelle überwachen, d.h. es wird keine dritte Partei zum Erzeugen der Teilchenpaare benötigt.

Jeder Partner notiert sich nun für eine Reihe von Teilchenpaaren, ob das Teilchen nach oben oder nach unten abgelenkt wurde. Partner A notiert eine 1 bei Ablenkung nach oben und eine 0 bei Ablenkung nach unten, Partner B macht es umgekehrt. Auf diese Weise entsteht bei beiden Partnern dieselbe zufällige Bitfolge, die beide dann als Schlüssel oder als One-Time-Pad verwenden können. Die Bitfolge ist deshalb zufällig, weil das Verhalten des einzelnen Teilchens quantenmechanisch nicht festliegt: es wird rein zufällig nach oben oder unten abgelenkt. Das ist genau die prinzipielle Zufälligkeit in der Quantenmechanik. Mehr dazu siehe in Das Unteilbare, Kapitel 3.8 (John Steward Bell und die Suche nach verborgenen Informationen).

Ist dieser Zufallsschlüssel nun wirklich geheim, also nur den beiden Partnern bekannt, die auch die Messung durchführen, oder kann eine dritte Person ebenfalls versteckt eine Messung an den Teilchenpaaren durchführen und so den Schlüssel mitschreiben, ohne dass die beiden Partner etwas davon merken?

Wenn ein Spion heimlich mithören will, so muss er eine Messung an mindestens einem der beiden Teilchen durchführen. Er kann dabei ebenfalls den Spin in z-Richtung messen und das Teilchen dann an den entsprechenden Partner weiterleiten. Dieser merkt bei seiner Spinmessung in z-Richtung dann nichts davon, dass da jemand heimlich diesen Spin bereits vorher gemessen hat.

Allerdings wird durch die heimliche Messung durch den Spion der Quantenzustand der beiden Teilchen unvermeidbar verändert, denn dieser Quantenzustand muss nun die Information wiederspiegeln, die durch die Messung gewonnen wurde. Die obige Quantentabelle ist ungültig geworden. Bei Spin-Messungen in z-Richtung merken das die beiden Partner A und B allerdings nicht. Messbar wird die Spionage und damit der veränderte Quantenzustand erst, wenn die beiden Partner die Messrichtung gegeneinander verdrehen, ohne dass der Spion das bei seiner Messung schon weiß. So könnte Partner A weiter in z-Richtung messen, während Partner B zufällig bei jedem neuen Teilchenpaar zwischen den folgenden drei Messrichtungen wechselt:



Messung des Teilchenspins in drei verschiedenen Richtungen, dargestellt durch drei Magnetfeldorientierungen (dier Teilchenbahn ist in blau dargestellt).

Nachdem beide Partner nun viele Teilchenpaare so gemessen haben, teilt Partner B seinem Partner A mit, wann er welche Messrichtung verwendet hat. Das kann er sogar öffentlich tun, denn der Spion kann sich nun nicht mehr mit seiner Messrichtung darauf einstellen -- die Messungen sind vorbei. Damit können die beiden Partner nun ihre Messungen statistisch analysieren und die sogenannte Bellsche Ungleichung überprüfen (Details dazu siehe in Das Unteilbare, Kapitel 3.8 ). Wenn nun ein Spion mitgemessen hat, so kann er den ursprünglichen Quantenzustand der beiden Teilchen nicht mehr rekonstruieren (würde er das tun, so wäre der Spin in seiner Messrichtung wieder ungewiss und er würde damit seine Messung wertlos machen). Der Spion kann zwar sicherstellen, dass die Teilchen sich in der von ihm gewählten Messrichtung weiter so verhalten, wie auch er es gemessen hat, so dass die beiden Partner in dieser Messrichtung dasselbe Ergebnis messen würden wie er. Er kann aber nicht sicherstellen, dass sich die Teilchen nach seinem Mitlauschen auch in allen anderen Messrichtungen noch statistisch so verhalten, wie sie es ohne sein Mitlauschen tun würden. Würde er beispielsweise versuchen, den Teilchen passende Informationen aufzuprägen, so würden diese Teilchen dann statistisch die Bellsche Ungleichung verletzen und sich somit anders verhalten als ohne sein Mitlauschen. Der Spion schafft es also prinzipiell nicht, dass seine Information nützlich bleibt und zugleich sich die Teilchen so verhalten, als hätte er nicht gelauscht. Mit anderen Worten: Der Lauschangriff des Spions verändert die Mess-Statistik in verschiedene Raumrichtungen zwangsläufig so, dass die beiden Partner das bemerken. Er hinterlässt einen unvermeidlichen Fingerabdruck im statistischen Verhalten der Teilchen. Bei Messungen in zufällig gegeneinander verdrehte Messrichtungen verhalten sich unbelauschte Teilchenpaare statistisch anders als belauschte.

Wenn die beiden Partner nun nach der statistischen Analyse ihrer Messungen sicher sind, dass die Bellsche Ungleichung erfüllt ist und demnach niemand mitgehört haben kann, dann verwenden sie zur Schlüsselgenerierung einfach nur noch die Messergebnisse, bei denen sie beide zugleich in z-Richtung gemessen haben (über die verwendeten die Messrichtungen haben sie sich ja nach der Messung bereits gegenseitig informiert). Bei diesen Messungen in z-Richtung verhalten sich die beiden Teilchen dann entgegengesetzt zueinander, so dass beide Partner denselben Schlüssel generieren können.

Quantenkryptographie besitzt also Eigenschaften, die sie inhärent sicher machen können. Tatsächlich gibt es schon einige praktische Beispiele, in denen sie real angewendet wurde, auch wenn sie sicher noch in den Kinderschuhen steckt. Mehr dazu findet man beispielsweise in Wikipedia: Quantenkryptografie.


Anhang: Der erweiterte euklidische Algorithmus und das inverse Element

Der euklidische Algorithmus ist ein uralter Algorithmus, um den größten gemeinsamen Teiler zweier Zahlen zu bestimmen. Er war bereits im antiken Griechenland bekannt. Schauen wir uns dazu das folgende Beispiel an (stammt aus dem obigen Wikipedia-Link):

Wir wollen den größten gemeinsamen Teiler der beiden Zahlen 44 und 12 finden. Wenn wir uns beide Zahlen als Streckenlängen vorstellen, geht es also darum, eine (möglichst große) Strecke zu finden, die n- bzw. m- mal in beide Streckenlängen hineinpasst. Nennen wir sie die ggT-Strecke (wobei ggT für größter gemeinsamer Teiler steht).

Schauen wir uns zunächst an, ob die kürzere der beiden Strecken (die 12) vielleicht schon die gesuchte ggT-Strecke ist, d.h. wie oft die kleinere Strecke 12 in die größere Strecke 44 hineinpasst und ob dabei ein Rest übrig bleibt. Das Ergebnis ist
  44   =   3 * 12   +   8
(siehe die zweite Zeile in der Grafik etwas weiter unten). Also passt die 12 nicht ohne Rest in die 44 hinein, und wir haben damit neben den beiden bisherigen Strecken 44 und 12 eine weitere Strecke hinzubekommen, nämlich die 8. Diese neue Strecke ist garantiert kleiner als die zuvor kürzeste Strecke (die 12), denn sie entstand ja als Rest beim Einfügen von möglichst vielen 12-er-Strecken. Die gesuchte ggT-Strecke (nennen wir sie   g   ) muss auch Teiler dieser neuen Rest-Strecke sein, denn nur dann kann sie zugleich Teiler von 44 und 12 sein. Das sieht man schon optisch in der Grafik etwas weiter unten, kann man aber auch leicht nachrechnen, denn wenn   44 = n*g   und   12 = m*g   ist, so folgt aus der obigen Gleichung   n*g   =   3 * m*g   +   8   und freigestellt nach dem Rest   8   =   n*g   −   3 * m*g   =   (n − 3*m) * g   .

Schauen wir uns daher analog zu oben wieder an, ob die neue Rest-Strecke (die 8) vielleicht schon die gesuchte ggT-Strecke ist. Dazu reicht es, nachzusehen, ob sie Teiler der zuvor kürzesten Strecke 12 ist, denn dann wäre sie automatisch auch Teiler der längeren Strecke 44 (sie war ja gerade der Rest beim Auffüllen der 44 mit 12-er-Strecken, siehe Bild unten). Rechnen wir nach:
  12   =   1 * 8   +   4
(siehe dritte Zeile in der gleich folgenden Grafik). Es bleibt also wieder ein noch kleinerer Rest übrig: die 4. Mit dieser neuen Reststrecke können wir die obige Argumentation nun wiederholen: Passt sie in die bisher kürzeste Strecke (die 8) mehrfach hinein, oder bleibt wieder ein Rest übrig? Wir haben Glück, denn   8 = 2*4   ohne Rest. Die bisher kürzeste Reststrecke 4 teilt also die 8 und teilt damit auch die 12 und teilt damit auch die 44 (wie die obigen Gleichungen zeigen). Damit haben wir den größten gemeinsamen Teiler von 44 und 12 gefunden: die 4.

Das Verfahren funktioniert analog auch bei anderen Zahlen. Da die Reststrecken in jedem Schritt garantiert immer kürzer werden, endet das Verfahren spätestens bei der kürzest-möglichen Reststrecke 1 (in diesem Fall wären die beiden Startzahlen teilerfremd). Hier die versprochene Grafik, die das Verfahren noch einmal darstellt:


So ermittelt der euklidische Algorithmus den größten gemeinsamen Teiler der Zahlen 44 und 12. Man schaut immer, ob die jeweils kürzeste Strecke in die zweitkürzeste Strecke mehrfach hineinpasst. Bleibt ein Rest, versucht man mit dieser noch kürzeren Rest-Strecke die bis dahin kürzeste Strecke aufzufüllen. Bleibt wieder ein Rest, so wiederholt man das ganze, bis kein Rest mehr bleibt (das ist spätestens dann der Fall, wenn die kürzeste Strecke die Länge 1 besitzt). Die so gefundene kürzeste Strecke passt dann in alle zuvor konstruierten Strecken hinein, insbesondere auch in die beiden Ausgangsstrecken 44 und 12.


Nun zum erweiterten euklidischen Algorithmus. Dieser beruht darauf, dass man im obigen euklidischen Algorithmus jede der dabei konstruierten Strecken als ganzzahlige Linearkombination der beiden Ausgangsstrecken 44 und 12 schreiben kann. So war die nächstkürzere Strecke (die 8) als Rest beim Einfügen von 12-en in die 44 entstanden:   44   =   3 * 12   +   8   (siehe zweite Zeile in der Grafik). Das können wir natürlich nach dem Rest 8 freistellen:
  8   =   44   −   3 * 12
Analog ist es bei der nächstkürzeren Strecke 4, die als Rest beim Einfügen von 8-en in die 12 entstand:   12   =   1 * 8   +   4   , was wir nach dem Rest 4 freistellen können:
  4   =   12   −   1 * 8
Die 8 rechts hatten wir gerade als Linearkombination der beiden Ausgangsstrecken 44 und 12 dargestellt und können dies hier einsetzen:
  4   =   12   −   1 * (44   −   3 * 12)   =   12   −   1 * 44   +   1 * 3 * 12   =   4 * 12   −   1 * 44
Insbesondere die kleinste Strecke, also der größte gemeinsame Teiler, lässt sich demnach als Linearkombnination der beiden Ausgangsstrecken schreiben. Nennen wir die beiden Ausgangsstrecken allgemein a und b, so lässt sich deren größter gemeinsamer Teiler   ggT(a,b)   also schreiben als

  ggT(a,b)   =   s * a   +   t * b

mit passenden ganzen Zahlen s und t, die wir wie gerade gezeigt schrittweise berechnen können (wobei eine der beiden Zahlen negativ ist).

Was hat das nun mit dem inversen Element in unserer multiplikativen Gruppe   ZN*   zu tun? Nehmen wir dazu ein Element a aus dieser Gruppe und wenden den gerade gezeigten erweiterten euklidischen Algorithmus auf dieses Element a und den Gruppenmodul N an. Als Ergebnis erhalten wir den größten gemeinsamen Teiler   ggT(a,N)   von a und N sowie die beiden ganzen Zahlen s und t, so dass   ggT(a,N)   =   s * a   +   t * N   ist. Nun wissen wir aber bereits, dass a und N teilerfremd sind, denn so war die Gruppe   ZN*   gerade definiert. Die beiden Zahlen a und N haben also außer der 1 keinen gemeinsamen Teiler, d.h.   ggT(a,N) = 1   und somit gilt

  1   =   s * a   +   t * N  

Wir hätten nun gerne, dass   s   aus der Gruppe   ZN*   ist, aber das muss in unserer Rechnung nicht unbedingt so herauskommen. Wir verschieben es daher um ein passendes Vielfaches von N, bis es zwischen 1 und N liegt. Wir bilden also ein neues   a' := s + k*N   mit einem passenden k, so dass a' im gewünschten Zahlenbereich von 1 bis N liegt (k darf auch Null sein, falls nicht verschoben werden muss). Oben eingesetzt ergibt sich

  1   =   (a' − k*N) * a   +   t * N   =   a' * a   +   (t − k*a) * N   =:   a' * a   −   t' * N

Da a' in den positiven Zahlenbereich gelegt wurde, muss t' positiv (oder Null) sein, d.h. es wird ein passendes Vielfaches von N abgezogen, so dass   a' * a   danach 1 ergibt. Das ist genau die Gruppenoperation, d.h.

  a' ο a   =   1

Jetzt müssen wir nur noch überprüfen, ob a' auch wirklich in der Gruppe   ZN*   liegt. Durch das Verschieben liegt es irgendwo von 1 bis N, d.h. wir müssen nur noch sichergehen, dass a' teilerfremd zu N ist. Das aber wissen wir bereits von oben: Wenn a' einen gemeinsamen Teiler p (größer als Eins) mit N hätte, so wäre a' und damit auch   a' * a   ein Vielfaches dieses Teilers p, und auch N und damit   t' * N   wäre ein Vielfaches von p, so dass die Differenz   a' * a   −   t' * N   ebenfalls ein Vielfaches des Teilers p wäre. Dann kann diese Differenz aber nicht gleich 1 sein, wie gefordert. Also ist a' teilerfremd zu N und liegt zudem im Bereich von 1 bis N, ist also damit Element unserer Gruppe   ZN*   . Damit ist a' das gesuchte inverse Element zu a , womit seine Existenz bewiesen ist.


Literatur:


zurück zum Inhaltsverzeichnis

last modified on 13 March 2009