{"id":6164,"date":"2014-08-09T17:37:43","date_gmt":"2014-08-09T15:37:43","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=6164"},"modified":"2023-05-29T22:12:19","modified_gmt":"2023-05-29T20:12:19","slug":"verschluesselung-auf-zeit","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2014\/08\/verschluesselung-auf-zeit.htm","title":{"rendered":"Verschl\u00fcsselung auf Zeit"},"content":{"rendered":"
(5 Kommentare.<\/a>)<\/small> <\/div>\n

Vor ein paar Wochen stellte Klaus Schmeh in Klausis Krypto Kolumne ein Time-Lock-Verschl\u00fcsselungsverfahren vor.<\/a> Um das Prinzip richtig zu begreifen, habe ich das alles nachprogrammiert, und wenn ich mir so viel M\u00fche mache, dann soll auch ein Blogeintrag dabei herauskommen. Ich bin kein Mathematiker oder Kryptologe und es ist nicht unwahrscheinlich, dass ich irgendwo Fehler drin habe; \u00fcber Berichtigungen freue ich mich.<\/p>\n\n\n\n

1. Wie man mit einem One-Time-Pad verschl\u00fcsselt<\/h3>\n\n\n\n

C\u00e4sarische Schl\u00fcssel<\/h4>\n\n\n\n

Man verschiebt bei diesem Verfahren den Klartext zum Beispiel um eins nach rechts im Alphabet. Aus A wird B, aus B wird C, aus Z wird wieder A. So wird HALLO zu IBMMP.<\/p>\n\n\n\n

Nat\u00fcrlich kann man auch um zwei nach rechts verschieben, dann wird aus HALLO: JCNNQ.
Es gibt, wenn wir von 26 Buchstaben ausgehen, 26 solche C\u00e4sarsischen Schl\u00fcssel, einschlie\u00dflich der Verschiebung um 0. Man sagt auch, der A-Schl\u00fcssel verschiebt um 0 (weil A zu A wird), der B-Schl\u00fcssel um 1 (weil A zu B wird), der C-Schl\u00fcssel um 2 (weil A zu C wird), der Z-Schl\u00fcssel um 25 (weil A zu Z wird).<\/p>\n\n\n\n

Diese einfache Verschl\u00fcsselung ist \u00fcberhaupt nicht sicher. Der h\u00e4ufigste Buchstabe im Deutschen ist „e“, und der h\u00e4ufigste Buchstabe in dem derart verschl\u00fcsselten Text wird dann wohl dem „e“ entsprechen, und das gilt f\u00fcr die restlichen Buchstaben ebenso.<\/p>\n\n\n\n

Vigen\u00e8re-Verschl\u00fcsselung<\/h4>\n\n\n\n

Sicherer ist das Verfahren, wenn man nicht jeden Buchstaben um den gleichen Wert verschiebt. Das geht am einfach mit einem geheimen Schl\u00fcsselwort, sagen wir: HALLO. Dabei entspricht H dem C\u00e4sarischen H-Schl\u00fcssel, A dem A-Schl\u00fcssel, und so weiter. Man schreibt das Schl\u00fcsselwort wiederholt unter den Klartext und verschiebt dann den Buchstaben des Klartexts jeweils so, wie es dem entsprechenden C\u00e4sar-Schl\u00fcssel darunter entspricht.<\/p>\n\n\n\n

Klartext:  ICHBINGEHEIM\nSchl\u00fcssel: HALLOHALLOHA\nGeheim:    PCSMWUGPSSPM\n<\/pre>\n\n\n\n
Das ist schon schwerer zu knacken, aber auch l\u00f6sbar. Wenn man erst einmal herausgefunden hat, wie lang das Schl\u00fcsselwort ist, geht das dann wie oben durch H\u00e4ufigkeitsanalyse.<\/p>\n\n\n\n
Das One-Time-Pad<\/h4>\n\n\n\n
Ganz sicher, und prinzipiell nicht zu knacken, ist diese Art der Verschl\u00fcsselung dann, wenn das Schl\u00fcsselwort genau so lang wie der Klartext ist, oder auch noch l\u00e4nger. Au\u00dferdem muss es aus wirklich zuf\u00e4lligen Zeichen bestehen, darf also sicher kein Wort oder Text der deutschen Sprache sein, und darf nat\u00fcrlich nur ein einziges Mal benutzt werden. F\u00fcr die n\u00e4chste Nachricht rei\u00dft man dann den n\u00e4chsten langen Schl\u00fcssel von seinem Block.
Dann hei\u00dft das Verfahren „One-Time-Pad“. Das Problem ist dabei nur, wie bei allen symmetrischen Verschl\u00fcsselungsverfahren, dass Sender und Empf\u00e4nger beide \u00fcber das gleiche One-Time-Pad verf\u00fcgen m\u00fcssen, das auf einem sicheren Weg \u00fcbermittelt werden muss und nicht abgefangen werden darf.<\/p>\n\n\n\n
2. Das gleiche nochmal mit Zahlen<\/h3>\n\n\n\n
Eigentlich machen sie eh alles mit Zahlen und sind nur so nett, diese Zahlen f\u00fcr uns als Buchstaben oder Grafiken auf dem Bildschirm darzustellen. Nach einem standardisierten Codierungsverfahren entspricht dem Buchstaben „H“ etwa die Zahl 72. Und die Zahl 72 wird intern im Computer im Bin\u00e4rsystem als 1001000 dargestellt (8 bit lang) – f\u00fcr Menschen etwas \u00fcbersichtlicher ist die Darstellung im Hexadezimalsystem als 48.<\/p>\n\n\n\n
Das Wort HALLO in verschiedenen Darstellungsformen:<\/p>\n\n\n\n
(1) Text:        H  A  L  L  O\n(2) Dezimal:     72 65 76 76 79\n(3) Hexadezimal: 48 41 4c 4c 4f\n(4) Bin\u00e4r:       1001000 1000001 1001100 1001100 1001111\n<\/code><\/pre>\n\n\n\n
Dabei ist (1) das f\u00fcr den Menschen am leichtesten lesbar und (4) das f\u00fcr den Computer am leichtesten. Man trifft sich oft in der Mitte bei (3) – dabei entsprechen den 8 einzelnen bit im Bin\u00e4rsystem jeweils zwei Ziffern im Hexadezimalsystem (wo es 16 Ziffern gibt, 0-9 und A-F).<\/p>\n\n\n\n
Der Klartext ICHBINGEHEIM sieht dann so aus:<\/p>\n\n\n\n
Klartext:       I  C  H  B  I  N  G  E  H  E  I  M \nKlartext (hex): 49 43 48 42 49 4e 47 45 48 45 49 4d\n<\/code><\/pre>\n\n\n\n
Das Ver- und Entschl\u00fcsseln l\u00e4uft \u00fcber Zahlen, also eigentlich \u00fcber das Bin\u00e4rsystem, aber lesbarer ist das im Hexadezimalsystem. Da sieht die Verschl\u00fcsselung mit einem Schl\u00fcsselwort, das mindestens so lang ist wie der Klartext (also einem One-Time-Pad entspricht), so aus: Der Klartext wird erst in Zahlen umgewandelt, dann wird das Schl\u00fcsselwort – ebenfalls eine Zahl – darauf angewendet, und die entstandene Zahl ist dann der Geheimtext:<\/p>\n\n\n\n
Klartext:       I  C  H  B  I  N  G  E  H  E  I  M \nKlartext (hex): 49 43 48 42 49 4e 47 45 48 45 49 4d\nSchl\u00fcsselwort:  43 c2 43 47 33 32 c1 1f 5d c9 39 e2\nGeheimtext:     0a 81 0b 05 7a 7c 86 5a 15 8c 70 af\n<\/code><\/pre>\n\n\n\n
Dabei funktioniert das Verschieben \u00fcber die XOR-Funktion. Schauen wir uns das erste I an: Aus dem Klartext 49 wird unter Anwendung des Schl\u00fcssels 43 der Geheimtext 0a. Bin\u00e4r ausgedr\u00fcckt:<\/p>\n\n\n\n
    1001001 (\"I\" bin\u00e4r)\n    1000011 (Schl\u00fcssel bin\u00e4r)\n-----------\n    0001010 (Ergebnis der XOR-Funktion, entspricht 0a hexadezimal)\n<\/code><\/pre>\n\n\n\n
Die XOR-Funktion ist hier wie eine Addition ohne \u00dcbertrag: Aus 1 und 1 wird 0, aus 0 und 0 ebenso; aus 1 und 0 (oder 0 und 1) wird 1.<\/p>\n\n\n\n
Zusammengefasst:
Klartext => Umwandlung in Zahl => XOR-Verechnung mit Schl\u00fcsselzahl (ensteht: Geheimtext als Zahl)<\/p>\n\n\n\n
Die Entschl\u00fcsselung l\u00e4uft dann einfach r\u00fcckw\u00e4rts ab:
Geheimtext als Zahl => XOR-Verechnung mit Schl\u00fcsselzahl => Umwandlung in Text (entsteht: Klartext)<\/p>\n\n\n\n
3. Das Time-Lock-Puzzle<\/h3>\n\n\n\n
Die Aufgabe<\/h4>\n\n\n\n
Ron Rivest verschl\u00fcsselte 1999 einen Text, dessen Entschl\u00fcssselung prinzipiell l\u00f6sbar ist, die aber 35 Jahre kontinuierlicher Berechnung braucht, die nach dem Mooreschen Gesetz (Wikipedia<\/a>) zu erwartenden Fortschritte im Bereich der Computerentwicklung inbegriffen. Man kann mit dem Verfahren im Prinzip einstellen, wie lange die Entschl\u00fcsselung eines Textes dauern soll. (Hier ist der urspr\u00fcngliche Beitrag von Ron Rivest,<\/a> in dem dieser das R\u00e4tsel erkl\u00e4rt und Java-Code zu Erzeugen \u00e4hnlicher Aufgaben zur Verf\u00fcgung stellt.)
So ein Time-Lock-R\u00e4tsel ist also quasi das genaue Gegenteil des in Agentenkreisen beliebten „Diese Nachricht zerst\u00f6rt sich in nach einer festgelegten Zeitspanne selber“, n\u00e4mlich ein: „Diese Nachricht wird in einer festgelegten Zeitspanne lesbar (wenn man flei\u00dfig rechnet)“.<\/p>\n\n\n\n
Also: Gegeben ist der verschl\u00fcsselte Geheimtext, als Zahl, so wie oben gezeigt. Gesucht ist das geheime Schl\u00fcsselwort, mindestens so lang wie der Klartext, siehe oben, ebenfalls als Zahl. Wenn man das Schl\u00fcsselwort gefunden hat, wendet man die XOR-Funktion auf die beiden Zahlen an und wandelt das Ergebnis in Text um (nach dem ASCII-Standard, der bestimmt, welche Zahl welchem Buchstaben entspricht).<\/p>\n\n\n\n
Das Schl\u00fcsselwort ist allerdings keine beliebige, v\u00f6llig zuf\u00e4llige Zahl, wie das bei einer echten Einmalverschl\u00fcsselung der Fall w\u00e4re. Sondern man erh\u00e4lt Hinweise, wie man die Schl\u00fcsselwort-Zahl berechnen kann, nur dass das eben 35 Jahre dauert, wenn man 1999 angefangen h\u00e4tte. Diese Angaben bestehen aus einer Zahl t<\/em> und einer Zahl n<\/em>. Dann muss man nur berechnen:<\/p>\n\n\n\n
w = 2(2t<\/sup>)<\/sup> mod n<\/code><\/p>\n\n\n\n
Dabei steht mod<\/em> f\u00fcr „Modulo“ und entspricht dem Rest, der bei der Teilung durch n \u00fcbrig bleibt. Man muss also zuerst das vordere berechnen, dann durch n teilen, und der Rest, der bei der Teilung \u00fcbrig bleibt, ist die gesuchte Zahl w<\/em> – der Schl\u00fcssel.<\/p>\n\n\n\n
Warum das 35 Jahre dauert<\/h4>\n\n\n\n
Wenn die Zahlen t und w klein sind, geht das Berechnen schnell. Sie m\u00fcssen also schon gro\u00df sein. Und wenn die Zahlen bestimmte bekannte Eigenschaften haben, gibt es mathematische Abk\u00fcrzungen, wie man das schnell l\u00f6sen kann, auch wenn die Zahlen gro\u00df sind; dazu sp\u00e4ter mehr.
Allgemein ist das Problem: 2(2t<\/sup>)<\/sup><\/code> kann man mit dem Computer \u00fcberhaupt nicht berechnen, wenn t einigerma\u00dfen gro\u00df ist. Irgendwann reicht der Speicherplatz nicht mehr aus, um die Zahl \u00fcberhaupt nur zu speichern.
Aber uns geht es ja auch nicht um 2(2t<\/sup>)<\/sup><\/code>, sondern um 2(2t<\/sup>)<\/sup> mod n<\/code> – und das l\u00e4sst sich sehr wohl berechnen. Man rechnet 2 * 2 * 2 * 2… und zwischendrin immer wieder mal modulo n<\/em>. So wird die Zahl, mit der der Computer arbeitet, nie gr\u00f6\u00dfer als 2*n. Allerdings muss der Computer das wieder und wieder und wieder machen, es geht um 2t<\/sup>-1 Multiplikationsvorg\u00e4nge jeweils gefolgt von einer Modulo-Division – bei den enstprechenden Werten von n<\/em> und t<\/em> eben 35 Jahre lang.<\/p>\n\n\n\n
In der Originalaufgabe von Rivest werden \u00fcbrigens folgende Werte verwendet:<\/p>\n\n\n\n
n = 631446608307288889379935712613129233236329881833084137558899\n    077270195712892488554730844605575320651361834662884894808866\n    350036848039658817136198766052189726781016228055747539383830\n    826175971321892666861177695452639157012069093997368008972127\n    446466642331918780683055206795125307008202024124623398241073\n    775370512734449416950118097524189066796385875485631980550727\n    370990439711973361466670154390536015254337398252457931357531\n    765364633198906465140213398526580034199190398219284471021246\n    488745938885358207031808428902320971090703239693491996277899\n    532332018406452247646396635593736700936921275809208629319872\n    7008292431243681\n\nt = 79685186856218<\/pre>\n\n\n\n
Damit gilt es, folgenden Geheimtext zu entschl\u00fcsseln (hier in Dezimalschreibweise, nicht hexadezimal):<\/p>\n\n\n\n
z = 427338526681239414707099486152541907807623930474842759553127\n    699575212802021361367225451651600353733949495680760238284875\n    258690199022379638588291839885522498545851997481849074579523\n    880422628363751913235562086585480775061024927773968205036369\n    669785002263076319003533000450157772067087172252728016627835\n    400463807389033342175518988780339070669313124967596962087173\n    533318107116757443584187074039849389081123568362582652760250\n    029401090870231288509578454981440888629750522601069337564316\n    940360631375375394366442662022050529545706707758321979377282\n    989361374561414204719371297211725179287931039547753581030226\n    7611143659071382<\/pre>\n\n\n\n
Man berechnet w<\/em>, wendet dann die XOR-Funktion auf w<\/em> und z<\/em> an, wandelt die entstandene Zahl in eine Hexadezimalzahl um und diese wiederum nach dem ASCII-Standard in Text, wo jeweils zwei Hexadezimalziffern einen Buchstaben ergeben.<\/p>\n\n\n\n
Das Verschl\u00fcsseln und der Trick bei der Sache<\/h3>\n\n\n\n
Die Verschl\u00fcsselung funktioniert dann, wenn n<\/em> das Produkt zweier (sinnvollerweise: hoher) Primzahlen p<\/em> und q<\/em> ist. Wer den verschl\u00fcsselten Text erstellt, w\u00e4hlt zwei hohe Primzahlen aus, multipliziert die, um n<\/em> zu erhalten, berechnet dann w<\/em> und verschl\u00fcsselt den Klartext damit. Dann gibt er sowohl den Geheimtext als auch n<\/em> und t<\/em> weiter.<\/p>\n\n\n\n
Aber Moment – es geht doch gerade darum, dass der Schl\u00fcssel<\/p>\n\n\n\n
w = 2(2t<\/sup>)<\/sup> mod n<\/code><\/p>\n\n\n\n
so schwer zu berechnen ist. Wie macht man das dann beim Verschl\u00fcsseln, da braucht man den Schl\u00fcssel doch auch? Wie gesagt: wenn n<\/em> das Produkt zweier (hoher) Primzahlen p<\/em> und q<\/em> ist, dann l\u00e4sst sich Formel f\u00fcr w auch so schreiben:<\/p>\n\n\n\n
w = 2(2t<\/sup> mod ((p-1)*(q-1)))<\/sup> mod (p*q)<\/code><\/p>\n\n\n\n
(Das ist so wegen Mathematik und ich muss es erst mal glauben.)<\/p>\n\n\n\n
Und w\u00e4hrend die erste Formel schwer zu berechnen ist, weil entweder die Zahlen zu hoch werden oder 2t<\/sup> Schritte daf\u00fcr n\u00f6tig sind, ist die zweite Formel f\u00fcr den Computer ein Klacks. (Allerdings: V\u00f6llig trivial ist das Werkeln mit so hohen Zahlen auch nicht; gl\u00fccklicherweise bringt Java die entsprechenden Funktionen daf\u00fcr gleich mit.)
Das hei\u00dft, wenn man die beiden Faktoren p<\/em> und q<\/em> wei\u00df, aus denen n<\/em> zusammengesetzt ist, dann l\u00e4sst sich w<\/em> leicht berechnen. Sonst nicht.<\/p>\n\n\n\n
M\u00f6gliche Abk\u00fcrzungen<\/h3>\n\n\n\n
1. Kann man das abk\u00fcrzen, indem man mehrere Rechner oder Prozessoren parallel daran arbeiten l\u00e4sst? <\/strong><\/p>\n\n\n\n
Nein. Man muss das wirklich der Reihe nach berechnen.
Aus Rivests Beispiel (mit n<\/em> = 11 * 23 = 254 und t<\/em> = 10):<\/p>\n\n\n\n
              2^(2^1) = 2^2 = 4 (mod 253)\n              2^(2^2) = 4^2 = 16 (mod 253)\n              2^(2^3) = 16^2 = 3 (mod 253)\n              2^(2^4) = 3^2 = 9 (mod 253)\n              2^(2^5) = 9^2 = 81 (mod 253)\n              2^(2^6) = 81^2 = 236 (mod 253)\n              2^(2^7) = 236^2 = 36 (mod 253)\n              2^(2^8) = 36^2 = 31 (mod 253)\n              2^(2^9) = 31^2 = 202 (mod 253)\nw = 2^(2^t) = 2^(2^10) = 202^2 = 71 (mod 253)<\/pre>\n\n\n\n
Da kann einem kein anderer Rechner einen nennenswerten Teil der Arbeit abnehmen.<\/p>\n\n\n\n
2. K\u00f6nnte man nicht einfach n<\/em> faktorisieren, also p<\/em> und q<\/em> herausfinden?<\/strong><\/p>\n\n\n\n
In dem Fall k\u00f6nnte man die schnellere Formel verwenden, ja. Aber diese Faktorisierung ist schwieriger, als man denkt, wenn es um eine Zahl geht, die das Produkt zweier hoher Primzahlen ist. Die Zerlegung einer solche Zahl mit 200 Dezimalstellen dauerte vor zehn Jahren noch anderthalb Jahre, achtzig Rechner waren daran beteiligt (Wikipedia<\/a>). Die Faktorisierung einer Zahl mit 616 Stellen (so viele hat das n<\/em> in Rivests urspr\u00fcnglichem R\u00e4tsel oben) ist zur Zeit noch nicht m\u00f6glich; die Zahl ist ungef\u00e4hr 2048 bit lang und damit noch auf einige Jahre sicher – die Bundesnetzagentur empfiehlt noch bis zum Jahr 2020 Schl\u00fcssel der L\u00e4nge 2048 bit, in Zukunft werden aber wohl 3000 bit verlangt werden (Wikipedia<\/a>).<\/p>\n\n\n\n
Und wenn irgendwann mal Quantencomputer mit gro\u00dfem Speicher kommen sollten, sieht das alles nochmal ganz anders aus, aber davon verstehe ich zu wenig.<\/p>\n\n\n\n
(Anhang: BlueJ-Projekt zum Spielen,<\/a> als Erg\u00e4nzung zu Rivests eigenem Javacode, siehe oben.)<\/p>\n","protected":false},"excerpt":{"rendered":"
(5 Kommentare.) Vor ein paar Wochen stellte Klaus Schmeh in Klausis Krypto Kolumne ein Time-Lock-Verschl\u00fcsselungsverfahren vor. Um das Prinzip richtig zu begreifen, habe ich das alles nachprogrammiert, und wenn ich mir so viel M\u00fche mache, dann soll auch ein Blogeintrag dabei herauskommen. Ich bin kein Mathematiker oder Kryptologe und es ist nicht unwahrscheinlich, dass ich […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[25],"tags":[227],"class_list":["post-6164","post","type-post","status-publish","format-standard","hentry","category-informatik","tag-informatik"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/6164","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/comments?post=6164"}],"version-history":[{"count":3,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/6164\/revisions"}],"predecessor-version":[{"id":58355,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/6164\/revisions\/58355"}],"wp:attachment":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media?parent=6164"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/categories?post=6164"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/tags?post=6164"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}