Erster Versuch: Addition Wir denken uns eine möglichst krumme 36-stellige Zahl s1 (soll heißen "erster Summand") aus, z.B. s1=342105263157894681708173319868283667. Die addieren wir auf die Zahl, die den Klartext darstellt, um diesen so zu verschlüsseln. Damit man den Klartext K in allen Beispielen wiedererkennt, nehmen wir das regelmäßige Muster K=123456789123456789123456789123456789. Wenn das Ergebnis der Addition mehr als 36 Stellen haben sollte, muss die vorderste Stelle eine 1 sein. Die dürfen wir dann wegwerfen; sie lässt sich beim Entschlüsseln rekonstruieren. Dieses Wegwerfen notieren wir als "mod 10h36" - was das heißen soll, wird gleich im Anschluss erklärt. Also lautet die Formel für die Verschlüsselung f(K) = (K + s1) mod M Im konkreten Beispiel mit M=10^36 und K und s1 wie eben: f(123456789123456789123456789123456789) = = (123456789123456789123456789123456789 + 342105263157894681708173319868283667) mod 10h36 = = 465562052281351470831630108991740456 mod 10h36 = = 465562052281351470831630108991740456 Sieht ganz schön verschlüsselt aus, aber es ist klar, wie man K aus f(K) zurückgewinnt: einfach s1 wieder abziehen, und falls das negativ würde, kommt vorher die 1 davor, die offenbar beim Verschlüsseln weggeworfen wurde. Jetzt wird noch die Notation mit dem "mod" (gelesen "módulo") erläutert. Diese Abkürzung wird in zwei verschiedenen Zusammenhängen verwendet, die sich so ähnlich sind, dass es meistens nichts ausmacht, wenn man sie miteinander verwechselt. Man sollte aber trotzdem wissen, dass es zwei verschiedene Dinge sind, die man ganz ähnlich bezeichnet. In beiden Fällen ergibt es für die Null, also "mod 0", keinen Sinn, was jetzt aber nicht mehr überall dazugeschrieben wird. Zum einen ist "mod" eine ganz normale Rechenoperation auf ganzen Zahlen und bezeichnet den Divisionsrest. "12 mod 5 = 2" bedeutet "12 lässt bei der Division durch 5 den Rest 2". Diese Notation ist durch verschiedene Programmiersprachen in Gebrauch gekommen; sie wird allerdings in den verschiedenen Sprachen immer wieder anders notiert. Zum anderen steht mitunter "mod m" mit einer Zahl m in Klammern hinter einer Gleichung, um anzudeuten, dass die Gleichung nur bis auf ein ganzzahliges Vielfaches von m gilt. Ein Beispiel wäre etwa die solcherart verzierte Gleichung "12 = 2 (mod 5)"; sie bedeutet "12 und 2 unterscheiden sich durch ein ganzzahliges Vielfaches von 5". Diese Notation ist in der Mathematik schon lange üblich, meist mit einem Identitäts- statt Gleichheitszeichen, also drei waagerechten Strichen statt zwei. Sie wird gelesen als "12 ist kongruent 2 modulo 5". Der Zusammenhang zwischen den beiden ist offensichtlich. Hat man die erste Notation gegeben, so könnte man die zweite einführen durch a = b (mod m) wird definiert als a mod m = b mod m Hat man umgekehrt die zweite gegeben, so könnte man die erste einführen als a mod m wird definiert als das eindeutige x im Bereich zwischen 0 und m-1 (für positive m, andernfalls zwischen m+1 und 0), so dass x = a (mod m) Der wesentliche Unterschied besteht darin, dass man bei der ersten Definition mit gewöhnlichen ganzen Zahlen rechnet, während man bei der zweiten solche Zahlen als praktisch gleich (als "äquivalent" oder "kongruent") betrachtet, die sich nur durch ein Vielfaches von m unterscheiden. So wichtig diese Unterscheidung (nämlich zwischen dem Rechnen mit Zahlen und dem mit "Kongruenzklassen") für die Algebra auch ist - hier brauchen wir sie nicht, sondern verwenden nur die Notation, wobei wir mal die eine und mal die andere hernehmen, je nachdem welche gerade praktischer ist. Optisch unterschieden werden sie danach, ob vor "mod" die Klammer aufgeht. Diese Notation gestattet uns, die Entschlüsselung so zu formulieren, dass sie ganz genauso wie die Verschlüsselung abläuft. Statt s1 zu subtrahieren, wird einfach -s1 addiert. Und weil wir vorher keine negativen Zahlen betrachtet haben, addieren wir ein zusätzliches M (also insgesamt M-s1), das wir mit der jetzt schon vertrauten mod-Operation bei Bedarf auch wieder wegwerfen können. Also lautet die Formel für die Entschlüsselung (wir schreiben jetzt S statt K, weil es ja kein Klartext mehr ist): g(S) = (S + s2) mod M wobei s2 = M-s1 Im konkreten Beispiel mit M=10^36 und S=f(K) und s1 wie eben: s2 = 10^36-s1 = = 1000000000000000000000000000000000000 - 342105263157894681708173319868283667 = = 657894736842105318291826680131716333 g(465562052281351470831630108991740456) = = (465562052281351470831630108991740456 + 657894736842105318291826680131716333) mod 10h36 = = 1123456789123456789123456789123456789 mod 10h36 = = 123456789123456789123456789123456789 Siehe da, der Klartext ist wieder zurück. Das war ja nun keine große Überraschung, aber den wesentlichen Trick sehen wir uns doch noch einmal an; der wird nämlich in einem etwas komplizierteren Zusammenhang noch einmal gebraucht. Verschlüsselung: f(K) = (K + s1) mod M Entschlüsselung: g(S) = (S + s2) mod M funktioniert weil: s1 + s2 = 0 (mod M) Dass darüber hinaus sogar s1+s2 = M gilt, davon haben wir keinen Gebrauch gemacht. Dieses lapidare "funktioniert weil" sollte man doch noch ein wenig besser begründen. Man darf nämlich die mod-Operation in eine Addition oder auch in eine Multiplikation hineinziehen, das heißt Aus a = a' (mod M) und b = b' (mod M) folgt a+b = a'+b' (mod M) und a*b = a'*b' (mod M) Ist nämlich a'=a+rM und b'=b+sM mit ganzen Zahlen r und s, so ist a'+b'=a+b+(r+s)M und a'*b'=(a+rM)(b+sM)=ab+(as+rb+rsM)M. Die Ergebnisse für die Variablen mit und ohne Strich unterscheiden sich also nur durch ein Vielfaches von M; das gilt für die Addition wie für die Multiplikation. Damit kann man g(f(x)) unmittelbar ausrechnen, und zwar alles (mod M) gerechnet: g(f(x)) = f(x) + s2 = (K + s1) + s2 = K + (s1 + s2) = K + 0 = K (mod M) Dabei bezieht sich das "(mod M)" am Schluss auf alle Gleichungen in der Zeile. Die Funktion g macht also wirklich die Funktion f rückgängig. Das Ganze war ein symmetrisches Verfahren, denn es war offensichtlich, wie man die Verschlüsselung rückgängig macht, wenn der Schlüssel bekannt ist. Zweiter Versuch: Multiplikation Weil es eben zu einfach war, machen wir es komplizierter. Jetzt wird nicht mehr addiert, sondern multipliziert. Ansonsten bleibt alles beim alten. Sogar die Zahlen im Beispiel bleiben dieselben, nur heißt s1 jetzt f1 (warum wohl?). Allerdings taugt s2 nicht mehr als zweiter Faktor f2. Wir schreiben einfach die Zusammenfassung des Verfahrens ab und ersetzen Additionen durch Multiplikationen, und entsprechend die Null, die bei der Addition wegfällt, durch die Eins, die das bei der Multiplikation tut. Die Begründung, warum es geht, bleibt ebenfalls sie alte - mit denselben analogen Änderungen. Verschlüsselung: f(K) = (K * f1) mod M Entschlüsselung: g(S) = (S * f2) mod M funktioniert weil: f1 * f2 = 1 (mod M) Konkret mit den Zahlen aus dem Beispiel: f1=342105263157894681708173319868283667 f2=651280485888742067030310164788447003 Es ist nämlich f1*f2=222806482014569618602715281918815785000000000000000000000000000000000001, d.h. die letzten 36 Stellen von f1*f2*x sind gerade x, ganz egal was x ist. f(123456789123456789123456789123456789) = = (123456789123456789123456789123456789 * 342105263157894681708173319868283667) mod 10h36 = = 42235217331708894735577007861985212288715257999241580595373467468965263 mod 10h36 = = 288715257999241580595373467468965263 g(288715257999241580595373467468965263) = = (288715257999241580595373467468965263 * 651280485888742067030310164788447003) mod 10h36 = = 188034613513239581419756674466894729123456789123456789123456789123456789 mod 10h36 = = 123456789123456789123456789123456789 und der Klartext ist zurück. Schon ein wenig verblüffender, aber keine Hexerei. Dass wir nach beiden Multiplikationen jeweils die vordere Hälfte des Ergebnisses weggeworfen haben, hat überhaupt nichts ausgemacht. Die beiden Faktoren brauchen dazu auch keine besonderen Zahlen zu sein; sie dürfen lediglich keinen gemeinsamen Primteiler mit M haben, im konkreten Beispiel durften sie also nicht durch 2 oder 5 teilbar sein. War das nun ein symmetrisches oder ein asymmetrisches Verfahren? Das kommt darauf an, ob wir darauf angewiesen sind, dass zu gegebenem f1 das zugehörige f2 fertig vom Himmel fällt wie eben geschehen, oder ob wir aus dem f1 das f2 in einfacher Weise berechnen können. Da es nur endlich viele Möglichkeiten gibt, ist das f2 (so es immer eines gibt) im strengen Sinne berechenbar; man könnte ja alle Kandidaten durchprobieren. Das lassen wir aber nicht gelten; sonst gäbe es überhaupt keine asymmetrischen Verfahren. Vielmehr sprechen wir nur dann von einem symmetrischen Verfahren, wenn der Schlüssel für die eine Richtung aus dem für die andere in praktikabler Zeit ausgerechnet werden kann. Auf diese Diskussion kommen wir am Ende des Artikels noch einmal zurück. Also die Aufgabe lautet: gegeben sind f1 und M, gesucht f2 so dass f1*f2=1 (mod M). Der Trick besteht darin, dass man ständig zwischen den Darstellungen in den ganzen Zahlen und den modulo-Darstellungen wechselt: Es soll sein f1*f2=1 (mod M). In den ganzen Zahlen heißt das f1*f2=yM+1 für eine noch unbekannte ganze Zahl y. Modulo f1 heißt das 0=yM+1 (mod f1) denn f1*f2=0 (mod f1). Das lässt sich auch schreiben als -M*y=1 (mod f1). Das ist aber genau so eine Aufgabe wie die Aufgabe am Anfang, jedoch mit einem kleineren Modul. Das wiederholt man so lange, bis der Modul 1 ist, woraus sich das Ergebnis ergibt. Wenn wir dieses Verfahren programmieren wollen, sollten wir handliche Formeln parat haben. Die entwickelt man wie eben beschrieben: Wir nehmen erst einmal an (und denken später darüber nach, ob es wahr ist), dass es zu zwei teilerfremden Zahlen a und m eine Zahl x gibt, so dass ax=1 (mod m). Die, oder falls es mehrere gibt, eine davon, soll R(a,m) heißen; das R steht für "reziprok". Es gilt also a*R(a,m)=1 (mod m), d.h. für ein geeignetes ganzzahliges y gilt a*R(a,m)=ym+1. Wüssten wir den Wert von y, dann könnten wir R(a,m)=(ym+1)/a berechnen. Auf einen durch m teilbaren Summanden kommt es dabei nicht an; wir rechnen also am Schluss noch mod m, um im Zahlenbereich von 0 bis m-1 zu bleiben. Betrachten wir von der Gleichung a*R(a,m)=ym+1 nur die Divisionreste mod a, so wird die linke Seite 0, also 0=ym+1 (mod a) oder umgeformt 1=-ym (mod a). Nach der Definition von R ist R(-m,a) gerade die Zahl, die diese Gleichung für y erfüllt, also y=-R(m,a). Nimmt man statt m eine andere Zahl m' mit m=m' (mod a), so ändert sich nichts. Damit das Verfahren möglichst rasch zu einem Ende kommt, nehmen wir die betragskleinste ganze Zahl, das ist m mod a selbst, falls das kleiner als a/2 ist, andernfalls (m mod a)-a. In die Gleichung für y eingesetzt ergibt sich: y = { (-R(m mod a, a) falls m mod a < a/2 { R(a - m mod a, a) sonst Das in die obige Formel für R eingesetzt ergibt: R(a,m) = { 1 falls a=1 { ((-m*R(m mod a, a)+1)/a) mod m falls m mod a < a/2 { ((m*R (a-m mod a, a)+1)/a) mod m sonst Der Fall a=1 musste besonders behandelt werden, weil sonst m mod a = 0 und daher R(0,a) nicht definiert wäre. Richtig ist die Formel in diesem Fall jedenfalls, denn in der Tat ist 1*1=1 (mod a). Zum Vorführen ist das Beispiel mit den 36 Stellen doch ein wenig umständlich, deswegen machen wir es mit einem 3-stelligen und suchen die Zahl, mit der man 719 multiplizieren muss, um eine Zahl zu erhalten, die ongruent 1 modulo 1000 ist, die also mit 001 endet. R( 719 , 1000 )= =(- 1000 *R( 1000 mod 719 , 719 )+1)/ 719 mod 1000 = =(- 1000 *R( 281 , 719 )+1)/ 719 mod 1000 R( 281 , 719 )= =( 281 - 719 *R( 719 mod 281 , 281 )+1)/ 281 mod 719 = =( 719 *R( 124 , 281 )+1)/ 281 mod 719 R( 124 , 281 )= =(- 281 *R( 281 mod 124 , 124 )+1)/ 124 mod 281 = =(- 281 *R( 33 , 124 )+1)/ 124 mod 281 R( 33 , 124 )= =( 33 - 124 *R( 124 mod 33 , 33 )+1)/ 33 mod 124 = =( 124 *R( 8 , 33 )+1)/ 33 mod 124 R( 8 , 33 )= =(- 33 *R( 33 mod 8 , 8 )+1)/ 8 mod 33 = =(- 33 *R( 1 , 8 )+1)/ 8 mod 33 R( 1 , 8 )= 1 Jetzt einsetzen: R( 8 , 33 )= (- 33 *1+1)/ 8 mod 33 = 29 R( 33 , 124 )= ( 124 *29+1)/ 33 mod 124 = 109 R( 124 , 281 )=(- 281 *109+1)/ 124 mod 281 =34 R( 281 , 719 )= ( 719 *34+1)/ 281 mod 719=87 R( 719 , 1000 )= (- 1000 *87+1)/ 719 mod 1000 = 879 In der Tat ist 719*879=632001 = 1 (mod 1000) p1= 940772584602761849 p2= 1062956145158339807 N= 999999999999999840843004587837623143 phi= 999999999999999838839275858076521488 psi=499999999999999919419637929038260744 e1= 89 e2= 617977528089887540855732271845041369 modinv=694278426639742737012524890125818729 prod=429048465900964543614787632822775822000000000000000000000000000000000001 klar=123456789123456789123456789123456789 klar^e2 mod N=479527743483501532159734756979867066 hash^89 mod N=klar 75 306666666666666617244044596476799923 110499350162364449708648486807812987 33886467383125092449484580544951162000000000000000000000000000000000001 476931465520256701754882257420368373 123456789123456789123456789123456789 306666666666666617244044596476799923 = 3 * 3 * 3 * 230936959621 * 49182360025862197678069 110499350162364449708648486807812987 is a prime ?modinv(19,psi) 342105263157894681708173319868283667 OK ?10000000000000000000000000000000000000000000/19 526315789473684210526315789473684210526315.789473684 OK ?modinv(342105263157894681708173319868283667,10^36) 651280485888742067030310164788447003 342105263157894681708173319868283667 = 3 * 2801 * 1068889 * 38088404823791849424268201 651280485888742067030310164788447003 = 31 * 21009047931894905388074521444788613 ?modpow(klar, 342105263157894681708173319868283667,n) 965907530027026275818742427316251885 OK ?modpow(965907530027026275818742427316251885,19,n) 123456789123456789123456789123456789 OK