{"id":9643,"date":"2020-03-23T13:37:50","date_gmt":"2020-03-23T11:37:50","guid":{"rendered":"http:\/\/www.soeren-in-norwegen.net\/blog\/?p=9643"},"modified":"2024-08-26T09:04:12","modified_gmt":"2024-08-26T07:04:12","slug":"crypto-puzzles","status":"publish","type":"post","link":"http:\/\/www.soeren-in-norwegen.net\/blog\/2020\/03\/crypto-puzzles\/","title":{"rendered":"Crypto Puzzles"},"content":{"rendered":"

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<\/a>“ von Ralph C.\u00a0 Merkle in Communications of the ACM<\/em>, volume 21, number 4, p. 294–299.
\nZum 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 \u00f8ffentlich die Idee der Publc-Key Kryptographie diskutiert wird.<\/cite><\/p>\n

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.<\/p>\n

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.
\nDiese 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\u00f8nnen, muss ich den Schluessel pers\u00f8nlich abgeliefert haben. Das ist ein bisschen komplizierter, wenn ich in Norwegen, und die zweite Person in Kanada ist.<\/p>\n

Die revolutionaere (und wahrlich geniale) von Merkle war nun, dass man den Schluessel in der Zeitung ver\u00f8ffentlicht und dass trotzdem sichere Kommunikation m\u00f8glich ist. Wie geht das?<\/p>\n

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\u00f8nnte bspw. in Puzzle #23017 verborgen sein.<\/p>\n

Das Puzzle zu l\u00f8sen 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.<\/p>\n

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<\/a> benutzt.<\/p>\n

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\u00f8ffentlicht. Der richtige Gespraechspartner nimmt sich davon EIN EINZIGES Puzzle heraus und l\u00f8st es. Man nehme an, dass die L\u00f8sung 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\u00f8nnen wir verschluesselt kommunizeren. Denn ich habe ja alle Schluessel unverpuzzelt bei mir rumliegen und mein Gespraechsteilnehmer hat den gleichen Schluessel eben gerade entpuzzelt.<\/p>\n

Falls ein b\u00f8swillig Teilnehmer die Nummer „abfaengt“ tut das nichts zur Sache, denn die Nummer ist ja nicht der Schluessel selber. Der b\u00f8swillige Teilnehmer hat zwar auch alle Puzzle aber im Schnitt muss die Haelfte davon gel\u00f8st werden um die richtige Information zu erhalten. Das waeren dann fuenfhunderttausend Stunden oder ca. 57 Jahre.<\/p>\n

Obercool wa! Aber wie gesagt, das ist nur das Grundprinzip an und fuer sich und in der Praxis ist das alles viel krasser.<\/p>\n

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:<\/p>\n

\"\"<\/a>*lacht* \u2026 allein dafuer lohnt sich das zu lesen :)<\/p>\n","protected":false},"excerpt":{"rendered":"

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.\u00a0 Merkle in Communications of the ACM, volume 21, number 4, p. 294–299. Zum Einen ist der Artikel ganz vorzueglich geschrieben. Ich habe das […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts\/9643"}],"collection":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/comments?post=9643"}],"version-history":[{"count":3,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts\/9643\/revisions"}],"predecessor-version":[{"id":14011,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts\/9643\/revisions\/14011"}],"wp:attachment":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/media?parent=9643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/categories?post=9643"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/tags?post=9643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}