Søren in Norwegen

Neulich las ich einen wichtigen wissenschaftlichen Artikel, den ich euch, meinen lieben Leserinnen und Lesern, waermstens ans Herz lege. Dabei handelt es sich um „Secure Communications Over Insecure Channels“ von Ralph C.  Merkle in Communications of the ACM, volume 21, number 4, p. 294–299.
Zum Einen ist der Artikel ganz vorzueglich geschrieben. Ich habe das auf die lange Bank geschoben, aber es war die reinste intellektuelle Freude den zu lesen. Zum Anderen ist das aus historischen Gruenden von Interesse, weil hier zum allerersten Mal øffentlich die Idee der Publc-Key Kryptographie diskutiert wird.

Nun dachte ich jahrelang, dass ich da nicht schlau genug fuer bin. Und fuer die ganz spezifischen Protokolle und Methoden, die heutzutage verwendet werden, ist diese Einschaetzung sicherlich auch weiterhin gueltig. Aber die Grundidee ist ganz einfach.

Ihr, meine lieben Leserinnen und Leser kennt sicher normale Kryptographie. Jeder Buchstabe eines Klartextes wird um eine gewisse Position im Alphabet verschoben. Um es schwerer zu machen kann man sagen, dass bspw. ein „E“ um 14 Stellen nach rechts verschoben wird, ein „M“ um 7 Stellen nach links, ein „V“ um 2 Stellen nach rechts usw. usf. Selbst normale Kryptographie ist deutlich komplizerter als dies, aber als Idee soll das reichen.
Diese Verschiebungsanweisung ist nun (mehr oder weniger) der sogenannte Schluessel. Es ist superwichtig, dass dieser Schluessel geheim gehalten wird. Und darin liegt das Problem. Denn um dem Gespraechsteilnehmer vertrauen zu kønnen, muss ich den Schluessel persønlich abgeliefert haben. Das ist ein bisschen komplizierter, wenn ich in Norwegen, und die zweite Person in Kanada ist.

Die revolutionaere (und wahrlich geniale) von Merkle war nun, dass man den Schluessel in der Zeitung verøffentlicht und dass trotzdem sichere Kommunikation møglich ist. Wie geht das?

Nun, das Prinzip ist ganz einfach. Anstatt eines Schluessels generiere ich 1 Million durchnummerierte Schluessel. Das geht schnell. Dann bringe ich diese Schluessel mittels eines einfachen Algorithmus „durcheinander“. Dabei ist zu beachten, dass die Nummerierung erhalten bleibt. Im Wesentlichen verschluessele ich also den Schluessel (und dessen Nummer); oder wie Merkle es schreibt: die Information (der Schluessel + Nummer) wird „verpuzzelt“. Ach ja, Schluesselnummer und Puzzlenummer haben NIX miteinander zu tun. Schluessel #23 kønnte bspw. in Puzzle #23017 verborgen sein.

Das Puzzle zu løsen dauert nun aber VIEL laenger als besagte Information zu verpuzzeln. Man stelle sich ein ganz normales tausend Teile Puzzle vor. Das dauert ewig um es fertig zu bekommen. Aber erst wenn es fertig ist, liegt das Bild (die Information) vor. Aber es dauert nur die kurze Zeitspanne vom Tisch runter auf den Fuszboden um die Information wieder durcheinander (und somit unleserlich) zu machen.

Soweit das Prinzip. In der Kryptographie sind das natuerlich mathematische Funktionen, die in eine Richtung (Verpuzzelung) leicht und in die andere Richtung (Entpuzzelung) unheimlich schwer sind. Ein Beispiel waeren Exponentialfunktionen. Die gehen schnell zu berechnen. Die Umkehroperation (den Logarithmus berechnen) dauert im Vergleich ewig. In Wahrheit werden nicht Exponentialfunktionen sondern urst krasse mathematische Badonkadonks benutzt.

Nun haben wir aber nicht nur einen verpuzzelten Schluessel + Nummer, sondern eine Million davon. Man nehme an, dass es ca. eine Stunde dauert diese zu erzeugen. Diese 1 Million Puzzle werden in der Zeitung verøffentlicht. Der richtige Gespraechspartner nimmt sich davon EIN EINZIGES Puzzle heraus und løst es. Man nehme an, dass die Løsung eines Puzzles auch eine Stunde dauert. Also 1 Million mal laenger, als es zu erstellen, aber der richtige Gespraechsteilnehmer muss es ja nur ein einziges Mal machen. Damit hat besagter Gespraechsteilnehmer einen Schluessel. Jetzt muss ich nur die Nummer dieses Schluessels wissen und dann kønnen wir verschluesselt kommunizeren. Denn ich habe ja alle Schluessel unverpuzzelt bei mir rumliegen und mein Gespraechsteilnehmer hat den gleichen Schluessel eben gerade entpuzzelt.

Falls ein bøswillig Teilnehmer die Nummer „abfaengt“ tut das nichts zur Sache, denn die Nummer ist ja nicht der Schluessel selber. Der bøswillige Teilnehmer hat zwar auch alle Puzzle aber im Schnitt muss die Haelfte davon geløst werden um die richtige Information zu erhalten. Das waeren dann fuenfhunderttausend Stunden oder ca. 57 Jahre.

Obercool wa! Aber wie gesagt, das ist nur das Grundprinzip an und fuer sich und in der Praxis ist das alles viel krasser.

Damit habe ich zwei Gruende gegeben, warum es sich lohnt diesen Artikel zu lesen. Der dritte Grund ist, dass ich in dem dort gegebenen (Pseudo)Code etwas sah, was heutzutage bestimmt nicht mehr durch den sog. „Review“-prozess gehen wuerde:

*lacht* … allein dafuer lohnt sich das zu lesen :)