> restart; Dieses gesamte Dokument ist mit'MAPLE', der 'Computer-Algebra-Software' produziert worden, die auf Computern in St.Patrick's Computerlabor installiert wird. Jedermann, der daran interessiert ist, ist willkommen, mich zu fragen. ___________________________ ALLGEMEINER VORTRAG. WED. 6. NOVEMBER 1996. STR. PATRICKS HOCHSCHULE, DRUMCONDRA, DUBLIN 9. Primzahlen und PUBLIC-KEY KRYPTOGRAPHIE Dr. JOHN COSGRAVE, MATHEMATIK-ABTEILUNG, STR. PATRICKS HOCHSCHULE, DRUMCONDRA, DUBLIN 9, IRLAND. E-mail: johnbcos@iol.ie (Haus) ___________________________________________ ZIEL DES VORTRAGS: Das grundlegende Konzept'Public-Key Kryptographie'(eine revolutionŠre Entwicklung der letzten zwanzig Jahre) erklŠren und zeigen, wie Primzahlen eine integrale Rolle in seiner Entwicklung gespielt haben. PLAN DES VORTRAGS: 1. Was ist'Kryptographie'? Eine sehr kurze Geschichte bis in s Jahr 1976. 2. Die grundlegende Idee von Public-Key Kryptographie (Diffie und Hellman, 1976). 3. Ein kurzes mathematisches Zwischenspiel ('modulare Exponentiation'). 4. Die Realisierung von Public-Key Kryptographie (Rivest, Shamir und Adleman, 1977). 5. Grundlegende mathematische Ideen fŸr Public-Key. ___________________________________________ 1. Was ist Kryptographie? Eine kurze Geschichte. [ Etymologie: aus dem Griechischen 'kryptos logos' was soviel wie 'verstecktes Wort' bedeuted. Also ist 'Kryptographie' 'Geheimnis' oder 'verstecktes Schreiben' ] Ich spreche Ÿber dieses (und morgens, das es Teil nicht von meinem Text bildet, das ich nur als der'Knochen meines GesprŠches ansehe), fŸr ungefŠhr fŸnf bis zehn Minuten. Am Ende dieses Teils meines Vortrags sind die SchlŸsselbegriffe (kein Wortspiel beabsichtigt): a. Klartext (der gewšhnliche Text) b. VerschlŸsselung SchlŸssel (was jemand auf Klartext anwendet, um ihn zu verschlŸsseln) c. verschlŸsselter Text (das verschlŸsselte Formular des Textes) d. DekodierungschlŸssel (was man auf verschlŸsselten Text anwendet, um den Klartext wieder herzustellen) 2. Die grundlegende Idee von Public-Key Kryptographie (Diffie und Hellman, Stanford UniversitŠt, 1976) Ihr grundlegendes Papier: 'New Directions in Cryptography', IEEE Transactions on Information Theory, Vol. IT-22, No. 6, November 1976, 644-654. (IEEE ist das Institut von elektronischen und Elektroingenieure.) Der …ffnungsatz von ihrem Papier hei§t: "Wir stehen heute am Rand einer Revolution in Kryptographie." ("We stand today on the brink of a revolution in cryptography.") In diesem Papier stellten sie die IDEE (und au§erdem viel, viel mehr) von Public-Key Kryptographie (im Vergleich zur klassischen Kryptographie) vor. Ich befasse mich damit in meinem Vortrag. 3. Ein kurzes mathematisches Zwischenspiel ('modulare Exponentiation') siehe "http://de.wikipedia.org/wiki/BinŠre_Exponentiation" Frage: Welcher Rest bleibt, wenn 34 durch 13 geteilt wird? Das ist einfach. 34 = 13*2 + 8 und liefert die Division von 34 durch 13 den Rest 8. Wenn Zahlen durch 13 geteilt werden und man sich nur fŸr den Rest interessiert, hei§ das'modularen Arithmetik mit dem Modul 13'. Und so sieht es aus, wenn man es (in MAPLE) mit dem oben genannten Beispiel tut, gefolgt von anderen Beispielen (die ich SIE bitte, in Ihrem Kopf zu rechnen, bevor ich MAPLE benutze): > 35 mod 13; > 123437652596959161941949 mod 5461385845; >100000000000000 mod 100000000; > 10000000000000000018 mod 100000000000; Eine andere Frage: Welchen Rest lŠ§t die Potenz 3^5 bei der Division durch 13? Das ist auch einfach. 3^5 = 243 = 13*18 + 9 und deshalb bleibt der Rest 9 bei der Division von 3^5 durch 13. Das Teilen von Zahlen durch 13 hei§t - wie Sie wissen -'modulare Arithmetik mit dem Modul 13'; wenn man Potenzen durch 13 teilt, wird es'modulare Exponentiation mit Modul 13'genannt, nd diese Rechnung kann MAPLE selbstverstŠndlich auch, wie Sie sehen: > 3^5 mod 13; > 5^3 mod 13; > 12321^3 mod 873; Aber wie findet man - zum Beispiel - den Rest bei der Division von 123456789123456781234567^ 987654321987654321987654321 durch 122333444455555? Lassen Sie es uns versuchen: > 123456789123456781234567 ^ 987654321987654321987654321 mod 122333444455555; Was bedeutet der Fehler'numeric exception: overflow'? Er bedeutet, da§ die Zahl 123456789123456781234567 ^ 987654321987654321987654321 zu gro§ ist und MAPLE nicht mehr damit umgehen kann. Aber sie ist nicht nur zu gro§, weil MAPLE damit nicht umgehen kann, sie ist tatsŠchlich SO gro§, da§ selbst wenn man sie errechnen kšnnte, es Jahre dauern wŸrde, sie auszudrucken bei einer Druckrate von Milliarden Zeichen pro Sekunde. Aber wie Sie spŠter sehen, ist das Finden des Restes genau die Art der Berechnung, die man kšnnen muss, um Public-Key Kryptographie zu machen. Zahlentheoretiker beherrschen seit vielen Jahren diese Art der Berechnung. Sie wird durch eine Kombination von zwei einfachen Rechenarten getan: gewšhnliche modulare Arithmetik, zusammen mit dem was ma Quadrieren und Multiplizieren nennt. Die Details dieses Verfahrens sprengt diesen Vortrag und so mŸssen Sie mir erlauben, die ErlŠuterung zu Ÿberspringen (die Details sind wirklich ziemlich einfach, ich unterrichte sie meinen Kursteilnehmern). MAPLE hat eine eingebaute Funktion fŸr die modulare Exponentiation, und hier veranschauliche ich es mit einigen Beispielen, beginnend mit den, mit denen Sie bereits vertraut sind, und dann bis dahin, das zu dem Fehler'numeric exception: overflow'fŸhrte: > 3&^5 mod 13; > 5&^3 mod 13; > 12321&^3 mod 873; Und jetzt der Ausdruck, der den Fehler produzierte: > 123456789123456781234567&^987654321987654321987654321 mod 122333444455555; Sofort das Ergebnis!!! Sie sehen den Unterschied bezŸglich der'Schreibweise'? Die frŸhere Schreibweise war a^b mod m. Dadurch, da§ MAPLE ZUERST a^b errechnet hat und dann erste den Rest durch m berechnen sollte, gab es den Fehler. Die letzte Schreibweise war a&^b mod m. In dieser Form hat MAPLE die modulare Arithmetik zusammen mit der (UNGLAUBLICH SCHNELLEN) Quadrieren-und-Multiplizieren Methode amgewandt. Ein weiteres Beispiel: > 2086822056296502560265&^3548276254987776266 mod 931987294968252720194941649999; SpŠter werden Sie sehen, warum wir solche Berechnungen brauchen. 4. Die Realisierung von Public-Key Kryptographie durch (MIT = Massachusetts Institute of Technology) Rivest, Shamir und Adleman von MIT, 1977. Ihr grundlegendes Papier: 'A method for obtaining digital signatures and public-key cryptosystems', Communications of the ACM (Association for Computing Machines), Vol. 21, (1978), 120-126. 'Eine Methode zur Erzeugung von digitalen Unterschriften und der Public-Key Kryptographie) Ihr Papier fing an: "Die VerschlŸsselungmethode wird durch die neue Eigenschaft ermšglicht, nŠmlich da§ ein šffentlicher SchlŸssel nicht die EntschlŸsselung der Nachricht ermšglicht. Dieses hat zwei wichtige Konsequenzen: (1) Eilboten oder andere sichere †bertragungswege werden nicht benštigt, um SchlŸssel zu Ÿbertragen.... (2) Es kann eine Meldung "unterzeichnet werden" mit einem privat erzeugten SchlŸssel. Jedermann kann diese Unterschrift mit entsprechend šffentlich bereitgestellten SchlŸssel ŸberprŸfen. Unterschriften kšnnen nicht gefŠlscht werden, und ein Unterzeichner kann nicht die GŸltigkeit seiner Unterschrift spŠter verweigern. Dieses hat offensichtliche Anwendungen in den Systemen "der elektronischen Post" und "des Zahlungsverkehrssystems".... ___________________________________________ Die Arbeit von Rivest, Shamir und Adleman gewann zuerst weitverbreitete allgemeine Aufmerksamkeit, als sie glŠnzend durch Martin Gardner in seiner mathematischen Spielspalte in der August-Ausgabe 1977 von'Scientific American'erklŠrt wurde. Der Vorsatz fŸr diesen Artikel hie§: "Eine neue Art der VerschlŸsselung, die Millionen von Jahre zum Entziffern brauchen wŸrde" In diesem Artikel wurde der berŸhmte RSA_129 Wettbewerb zum ersten Mal der …ffentlichkeit vorgestellt. Ich werde einige Dinge darŸber spŠter sagen.... ___________________________________________ UND WIE GEHTS NUN WEITER?. Ich werde in aller KŸrze versuchen,Ihnen alles zu erklŠren: Sie wissen, was eine Primzahl ist (2, 3, 5, 7, 11, 13...)?. Es gibt unendlich viele von ihnen (Euklid hat das schon bewiesen siehe: "http://de.wikipedia.org/wiki/Euklids_Primzahlbeweis"). Wenn ich zwei KLEINE wŠhle und Ihnen das Produkt verrate, DANN wŸrden Sie KEINE Schwierigkeit haben, mir die beiden Faktoren zu bestimmen. Sagen wir z.B. das Produkt ist 91. Dann wŸrden Sie nach einem Moment der †berlegung sagen, ich habe die Faktoren 7 und 13 gewŠhlt. ABER, wenn ich zwei wŠhlen wŸrde, die GROSS sind, wird es Ihnen und nicht nur Ihnen -sondern auch der NSA ( US Staatssicherheit Agentur -National Security Agency)- PRAKTISCH UNM…GLICH sein, aus der Kenntnis des Produkts, die Fakoren zu ermitteln. Es ist diese (momentane) VIRTUELLE UNM…GLICHKEIT, die Rivest, Shamir und Adleman ausgenutzt haben, um ein "nichtknackbares kryptographisches Protokoll" zu erstellen. So denken Sie im Folgenden immer an das PRODUKT von ZWEI Primzahlen ... _______________________________ Die erste Sache, die ich (und diese ist grundlegend) erklŠre, ist, wie Sie Klartext in numerische Information umwandeln: a wird zu 1, b wird zu 2..., z wird zu 26, A wird zu 27, B wird zu 28..., Z wird zu 52, ` (das Zeichen'des rŸckwŠrtigen AnfŸhrungsstriches') wird zu 53, 1 wird zu 54, 2 wird zu 55..., 9 wird zu 62, 0 wird zu 63, - (das Minuszeichen) wird zu 64..., (- runde Klammer auf - wird zu 75..., Leerzeichen wird zu 79... und so weiter. [ diese Anweisungen wurden mir - Ÿber das Internet - von Joe Riel, einem Ingenieur mitgeteilt, der in Kalifornien arbeitet.] Im Folgenden wird MAPLE einfach angewiesen, diese'†bersetzung'durchzufŸhren. Als Alfabeth verwende ich: > `crypt/alphabet` := `abcdefghijklmnopqrstuvwxyz` ||`ABCDEFGHIJKLMNOPQRSTUVWXYZ` ||```1234567890-=~!@#$£%^&*()_+` ||` ,./<>?;':"[]{}|`: Die folgende Funktion verknŸpft die Bezeichnungen des'crypt/alphabet' mit den Zahlen von 1 bis 95: > ### WARNING: semantics of type `string` have changed to_number := proc(st, string) local ll, nn, ss, ii; global `crypt/alphabet`; ll := length(st); if ll = 0 then RETURN(0) fi; nn := 1; for ii to ll do ss := SearchText(substring(st, ii .. ii), `crypt/alphabet`); if not type(ss, numeric) or ss = 0 then ERROR(`the letter `||(substring(st, ii .. ii)) ||` is not in the alphabet`) fi; nn := 100*nn + ss od; nn - 10^(2*ll) end: Einige Beispiele: > to_number(`Welcome zu Str. Patricks College`); Und viel lŠnger das: [ danach hinzugefŸgt fŸr Leute, denen ich dieses worksheet schicke: Das folgende kann zu einer Fehlermeldung ('Strings') fŸhren, und Sie mŸssen es eventuell Šndern. Ich wollte gerade einen Text mit einer gro§en Vielzahl von Zeichen schreiben. ] > to_number(`There are - at the moment - US$1.60 to IR£1 (the Irish'punt'). In one of George Orwell's letters (in the 4-volume Penguin edition) you may read that at one time the rate was US$5 to St£1. Do you remember the term'half a dollar'?It was two shillings and sixpence!!`); Das'6767'am Ende der Ausgabe sind die beiden'!!'Ausrufezeichen. Und jetzt einige Anweisungen, einen Text aus der numerischen Schreibweise zurŸckzuŸbersetzen: > from_number := proc(nn, integer) local ss, mm, ll, pp, ii, ans; global `crypt/alphabet`; mm := nn; ll := floor(1/2*trunc(evalf(log10(mm))))+1; ans := ``; for ii to ll do mm := mm/100; pp := 100*frac(mm); if pp > length(`crypt/alphabet`) then ERROR #(`there is no letter in the alphabet corresponding ` #.`to the number `.(convert(pp, string))) fi; (`there is NO meaningful text corresponding` ||` to the number you have inputted`) fi; ss := substring(`crypt/alphabet`, pp..pp); ans := cat(ss, ans); mm := trunc(mm) od; ans end: einige Beispiele: > from_number(95010203049595); Und jetzt nehme ich die Zahl, die Sie gerade gesehen haben und ergŠnze am Ende 96: > from_number(95010203049596); > from_number(30050118803615081481805115211880120503202118058023011980191580828282); > from_number(460805180580011805806480012080200805801315130514208064804745705482596380201580354471548076200805803518091908881621142088778280351480151405801506803305151807058041182305121288198012052020051819807609148020080580576422151221130580420514072109148005040920091514778025152180130125801805010480200801208001208015140580200913058020080580180120058023011980474570588020158045207154828030158025152180180513051302051880200805802005181380880801120680018004151212011888863520802301198020231580190809121209140719800114048019092416051403056767); Soviel fŸr jetzt um eine Text in eine Zahl und zurŸck zu verwandeln. Nun zum realen GeschŠft des Sendens einer mit Public-Key Kryptographie verschlŸsselten Meldung und ihrer Dekodierung: Ein Kochbuch fŸr Public-Key Kryptographie und Dekodierung. Ich werde Ihnen zeigen, wie SIE MIR eine Meldung schicken kšnnen, die SIE durch das'RSA VerschlŸsselungsprotokoll'verschlŸsseln (wie es nach seinen Schšpfern, Rivest, Shamir und Adleman benannt wird), und welches JEDER ANDERE nicht lesen kann, und ich werde Ihnen zeigen, was ich dann tue, um IHRE Meldung zu entschlŸsseln. Die obigen †bersetzungen von Zeichen zu Zahlen soll im Folgenden vereinbart sein. BEVOR irgendjemand mir eine RSA-verschlŸsselte Meldung schicken kann, mŸssen er wissen, wie mein public-key lautet. Meine public-key ist ein Zahlenpaar (n, e). Das'n'wird šffentlicher Modul (public modulus ) genannt und das'e'ist meine'allgemeine VerschlŸsselungenergie'(public encryption power). Diese beiden Zahlen werden wie folgt gebildet: Der erste Schritt ist, eine recht gro§e Primzahl (recht gro§ - mehr davon spŠter) zu wŠhlen: p:=nextprime(56782894997592526946596965999565948474734464644); und dann wŠhlen Sie Šhnlich gro§e Primzahl: q:=nextprime(75296587628568265828284485625547494384373773574447); DIESE 2 PRIMZAHLEN M†SSEN GEHEIMGEHALTEN WERDEN. Und dann multipliziere ich diese zwei Primzahlen: n:=p*q; Diese Zahl 'n'ist mein …FFENTLICHER MODUL ('…ffentlich' hei§t, da§ ich mich NICHT drum kŸmmern muss, wer seinen Wert kennt). Als nŠchstes bilde ich die Zahl 'e', meinen 'šffentlichen VerschlŸsselungsexponenten' (public encryption power). Der wird wie folgt gebildet: Zuerst bilde ich eine GANZ SPEZIELLE Zahl, die 'phi_n' genannt wird, die, wie p und q oben, AUCH GEHEIM GEHALTEN WERDEN MUSS: > phi_n:=(p - 1)*(q - 1); Nachdem ich phi_n gebildet habe, bilden Sie dann meinen 'šffentlichen VerschlŸsselungsexponenten' 'e'. Der wird besonders ausgewŠhlt, so, dass e UND phi_n teilerfremd sind. [ und so - zum Beispiel - WENN p und q 19 und 23 gewesen waren, dann wŸrde man NICHT fŸr e 15 wŠhlen, weil 3 ein Faktor von BEIDEN 15 ist UND (19 - 1)*(23 - 1). Wenn man jedoch e=7 (z.B.) wŠhlt, dann ist das richtig ] In der Praxis wird e als zufŠllige gro§e Primzahl gewŠhlt: > e:=nextprime(75859825925924926296969); Ich mu§ SICHER stellen, da§ es KEINE natŸrliche Zahl grš§er als 1 gibt, die ein Faktor von e und von phi_n ist. Mit etwas Standardmathematik (genannt den 'euklidischen Algorithmus' ) - die Details brauchen Sie nicht zu wissen - wird das ŸberprŸft: > igcd(e, phi_n); #'igcd' steht fŸr 'integer greatest common divisor' (grš§ter gemeinsamer Teiler -ggt). Die '1' als Ergebnis bedeutet, da§ der EINZIGE Faktor von e und von phi_n 1 ist, und so bin ich hier im Beispiel sicher. [ nebenbei: hier zwei Beispiele, damit Sie sehen, wie das mit kleineren Zahlen geht: ] > igcd(15, 22); > igcd(15, 21); Wenn ich nun meinen …FFENTLICHEN VerschlŸsselungsexponenten e gewŠhlt habe, dann fahre ich fort, meinen 'PRIVATEN VerschlŸsselungsexponenten d' zu errechnen. Diese Zahl d ist die EINDEUTIGE Zahl zwischen 1 und phi_n so, da§ das Produkt von e und d den Rest 1 bei der Division durch phi_n hat. Von GRUNDLEGENDER mathematischer Bedeutung ist hier, da§ d nur durch jemand bestimmt werden kann, der den Wert von phi_n , oder was dasselbe ist, die Werte von p und q KENNT. Wenn ich nun d kenne und meinen 'RSA public-key' (n, e) bekanntgegeben habe, ich bin betriebsbereit, RSA-verschlŸsselte Nachrichten zu empfangen. Nehmen wir an, da§ jemand (SIE z.B.), MIR eine RSA-verschlŸsselte Nachricht schicken wŸrde, deren Klartext "The money is now in your Swiss account" ist. Folgendes mu§ten SIE dann tun: Zuerst wŸrden Sie Ihren Text in Zahlen mit den oben vereinbarten Anweisungen umformen: > numerical_form_of_text:=to_number(`The money is now in your Swiss account`); und dann mŸssen Sie wissen, wieviele Ziffern in der Zahlendarstellung Ihres Textes sind: > length(numerical_form_of_text); Stellen Sie auch fest, wieviele Ziffern meiner'…ffentlicher Modul n' hat: > length(n); Mit der Zahl, die das Zahlenformat Ihres Textes hat, der KLEINER ist, als mein šffentlicher Modul n sind Sie jetzt bereit, mir Ihre Meldung zu schicken. Folgendes muŸssen Sie tun: Sie nehmen die Zahl, die das Zahlenformat Ihres Textes ist, und wenden 'modularen Exponentiation' an mit MEINEM VER…FFENTLICHTEN VERSCHL†SSELUNG-EXPONENTEN (e) mit MEINEM VER…FFENTLICHTEN MODUL (n) an: > numerical_form_of_cipher_text:=numerical_form_of_text&^e mod n; Schicken Sie mir diese Zahl numerical_form_of_cipher_text dann, die den verschlŸsselten Text darstellt. Nach dem Empfang beginne ich, Ihre verschlŸsselten Meldung folgenderma§en zu entschlŸsseln: Vorher habe ich bereits meinen'Dekodierungexponenten d' berechnet. Diese Zahl d ist die EINDEUTIGE Zahl zwischen 1 und phi_n (das SEHR GROSS ist, wenn p und q gro§ sind), so, da§ das PRODUKT von e und d den Rest 1 bei der Division durch phi_n lŠ§t. Der Wert von 'd' wird errechnet, indem man eine Methode verwendet, die den 'erweiterten euklidischen Algorithmus', eine einfaches, aber bemerkenswert leistungsfŠhiges Verfahren, das von Euclid (300 vor Chr.) stammt. (dieses ist auch etwas, das ich meinen Kursteilnehmern lehre) > igcdex(e, phi_n, x, y); # das 'ex' ist das 'erweiterte euklidische ...' Was 'x'und'y' ist, braucht man hier nicht zu wissen. (NatŸrlich werde ich es jedem, der danach fragt, erklŠren!) Hier genŸgt es zu wissen, dass dieser Algorithmus fŸr mich (der ich die beiden Primzahlen p und q gewŠhlt habe) den Dekodierungexponenten d bestimmt: > d:=x mod phi_n; Nun da ich den Wert von 'd' habe, wird die Zahlenform des URSPR†NGLICHEN Textes durch Anwendung der modularen Exponentiation auf empfangenen numerical_form_of_cipher_text mit meinem …FFENTLICHEN Modul n, zusammen mit meinem GEHEIMEN Dekodierungexponenten d wieder hergestellt: > numerical_form_of_decoded_text:=numerical_form_of_cipher_text&^d mod n; Den Text ihrer Meldung, die SIE MIR schickten, bekomme ich, indem ich vorbei die letzte Zahlendarstellung in Text umwandele: > original_text:=from_number(numerical_form_of_decoded_text); Nehmen Sie an, das irgendjemand die oben genannte Meldung heimlich mitgehšrt hat. Kšnnte er sie entschlŸsseln? Er kšnnte, wenn er meinen PRIVATEN Dekodierungexponenten d kennen wŸrde. Lassen Sie uns sehen, was man versucht, mein PRIVATES d ZU ERRATEN: > d_guess:=682569569269; Dieser geratene Wert von d wŸrde die folgende versuchte Dekodierung ergeben: > numerical_form_of_attempted_decryption:=numerical_form_of_cipher_text&^d_guess mod n; und das wŸrde den folgenden Versuch am Wiederherstellen des ursprŸnglichen Textes ergeben: > attempted_original_text:=from_number(numerical_form_of_attempted_decryption); SelbstverstŠndlich wŸrde jemand den Text wiederherstellen kšnnen, WENN er meinen PRIVATEN Dekodierungexponenten d richtig rŠt. Ich mšchte Sie daran erinnern, da§ es einen EINDEUTIGEN Wert fŸr d im Intervall von 1 bis phi_n gibt, aber, wenn p und q gro§e Zahlen sind, dann ist phi_n (= (p - 1)*(q - 1)) erst recht gro§, und somit sind die Wahrscheinlichkeiten, d richtig zu raten, sehr gering. Und es ist auch nicht so, dass jemand der nahe am richtigen Wert von d geraten hat, eine Chance habe, das als Vorteil zu nutzen. Ich veranschauliche das, indem ich einen geratenenen Dekodierungexponenten wŠhle, der 1 weniger und dann 1 mehr ist als der korrekte Wert von d : > d - 1; > numerical_form_of_another_attempted_decryption:= numerical_form_of_cipher_text&^(d - 1) mod n; > another_attempted_original_text:=from_number(numerical_form_of_attempted_decryption); Und lassen Sie uns jetzt die andere Seite von d versuchen: > d + 1; > numerical_form_of_yet_another_attempted_decryption: = numerical_form_of_cipher_text&^(d + 1) mod n; > yet_another_attempted_original_text: = from_number(numerical_form_of_yet_another_attempted_decryption); FRAGE: Ist eine Dekodierung mšglich, wenn jemand die Werte von p und von q KENNT? ANTWORT: SelbstverstŠndlich. Jedermann, der p und q kennt (und mit der Mathematik vertraut ist), wŸrde sofort d aus phi_n (nŠmlich (p - 1)*(q - 1)) berechnen kšnnen. FRAGE: Ist es also nur eine Frage des Bestimmens von p und q aus dem Wert von n? [ danach hinzugefŸgt: Als ich diesen Vortrag plante, hatte ich geistlich, da§ ich nur mich ungefŠhr fŸnf Minuten Kapitel 1 widmen wŸrde - die 'Privattaste' Periode zugegeben. Zu meiner Grausigkeit fand ich, da§ ich fast Zwanzig Minuten auf ihr aufwendete und infolgedessen ich nur an diesen Punkt nach fast einer Stunde gelangte. Ich entschied, die Geduld meiner Publikum nicht zuviel zu versuchen und holte meinen Vortrag zu einem Ende an diesem Punkt. Da ich den Text gedruckt und ungefŠhr fŸnfzig Photokopien gebildet hatte, konnte ich, aus Texten zu geben jeder, das interessiert war (alle meine Exemplare gingen, und ich mu§te spŠter bekanntgeben). Folgten einer Periode von ungefŠhr vierzig Minuten Fragen und Antworten. ] > > > 5. Grundlegende mathematische Gedanken fŸr Public-Key Systeme. Es ist nur mšglich, kurz darauf einzugehen. Au§er der Vertrautheit mit 'modularer Arithmetik' (alias 'Uhr-Arithmetik' oder 'Kongruenzen') und dem euklidische Algorithmus und seine 'Erweiterung', beziehen die SchlŸsselideen die Arbeiten von zwei berŸhmten Mathematikern mit ein: Pierre de Fermat (1601-1667) und Leonhard Euler (1707-1783). Eine der sehr vielen wundervollen Entdeckungen, die Fermat machte, war diese: 'Kleiner Fermatsche Satz': Wenn p irgendeine Primzahl und a eine ganze Zahl ist, die NICHT durch p teilbar ist, dann bleibt ein Rest 1, wenn man die Zahl a ^ (p-1) durch p teilt. ______________________________ Einige Beispiele zum VerstŠndnis: (1) Sei p = 5 und a = 2, dann (p-1) = 5-1 = 4 und es gilt: 2^4 = 16 = 5*3 + 1. Also ist der Rest 1. (2) Sei p = 7 und a = 10, dann (p-1) = 7-1 = 6 und es gilt: 10^6 = 1000000 = 7*142857 + 1. Also ist der Rest 1. Sie sollten einige Beispiele fŸr sich selbst ŸberprŸfen. Lassen Sie uns gerade schnell einige Beispiele mit viel grš§eren Zahlen ansehen: > p:=nextprime(1234564264327); und jetzt wŠhle ich ein'a', das NICHT durch p teilbar ist: > a:=8675645534; Und lassen Sie uns jetzt ŸberprŸfen, um zu sehen, welcher Rest bei der Division von a^(p-1) durch p entsteht: > a&^(p - 1) mod p; Der Nachfolger von a ist (a+1): > (a+1)&^(p-1) mod p; Aber lassen Sie mich das gerade zeigen: > 30&^10 mod 11; # hier ist p = 11 und a = 30. > 31&^10 mod 11; # ist p noch 11, aber ich habe a auf 31 geŠndert. > 32&^10 mod 11; # ist p noch 11, aber ich habe a auf 32 geŠndert. > 33&^10 mod 11; # ist p noch 11, aber ich habe a auf 33 geŠndert. Der Rest ist jetzt 0, weil - wie Sie sehen - der Wert von (33) IST jetzt durch 11 teilbar. Fermat entdeckte diesen schšne Satz in Zusammenhang mit seiner Arbeit an Primzahlen der Form (2^n - 1) (ein Thema eines anderen Vortrags von mir Ÿber die vor kurzem entdeckten Rekordprimzahl 2^1257787 - 1), aber er war nicht imstande, diesen Satz zu beweisen. (siehe: http://www.arndt-bruenner.de/mathe/Allgemein/fermatklein.htm) Der erste Beweis wurde von Euler gegeben (es gab viele folgende - einschlie§lich einen von mir selbst 1966 fŸr den speziellen Fall a = 2) und er war es, der eine 'Verallgemeinerung' von Fermats Satz gab: Verallgemeinerung Eulers von 'kleinen Fermatschen Satz': Wenn n irgendeine ganze Zahl gršsser als 1 ist (prim oder nicht) und a ganze Zahl ist, soda§ a und n teilerfremd sind, dann gibt es eine ganze Zahl, DEREN WERT NUR VON DER ZAHL n selbst ABH€NGT (die Euler phi_n nannte), derart, da§ die Zahl a^ phi_n den Rest 1 lŠ§t, wenn sie durch n geteilt wird. _________________________________ Wenn n selbst prim ist (der Fermat Fall), dann ist phi_n = n - 1. Aber, wenn n KEINE Primzahl ist, gilt nicht mehr phi_n = n - 1. Z.B.: Sei n = 4 (das allererste Beispiel einer Nicht-Primzahl gršsser als 1) dann n - 1 = 3. Wenn man jetzt a = 7 wŠhlt, dann sind a und n teilerfremd. Und nun bestimmen wir 7 (nŠmlich a) hoch n - 1 (3) und sehen, welcher Rest die Division durch n ŸbriglŠ§t: 7^3 = 7*7*7 = 49*7 = 343 = 4*85 + 3, also bleibt 3 (und NICHT 1) als Rest, wenn Sie durch 4 teilen. Ich kšnnte unendlich viele Šhnliche Beispiele geben.... ____________________________________ FRAGE: WAS ist der Wert von phi_n, wenn n NICHT prim ist? Euler konnte eine KOMPLETTE Antwort zu dieser Frage geben, aber ich werde mich auf das Folgende beschrŠnken TEILWEISE ANTWORT: Wenn eine Zahl NICHT prim ist, gibt es eine UNENDLICHE Anzahl von unterschiedlichen mšglichen Formen, die sie haben kšnnte. Es kšnnte das Produkt von zwei Primzahlen sein(die unterschiedlich sein kšnnten oder nicht: 15 = 3*5, 49 = 7*7, usw.); es kšnnte das Produkt von drei Primzahlen sein (unterschiedlich oder nicht: 42 = 2*3*7, 12 = 2*2*3, 125 = 5*5*5, usw.); es kšnnte das Produkt von vier Primzahlen sein (fŸnf, sechs...) .... Im einfachsten mšglichen Fall - wenn n das Produkt von zwei UNTERSCHIEDLICHEN Prinzahlen p und q ist - hat Euler entdeckt und konnte beweisen, da§ der Wert von phi_n gerade (p - 1)*(q - 1) ist. Also haben wir: Der einfachste Fall von der Verallgemeinerung Eulers vom 'Kleinen Fermatschen Satz': Seien p und q zwei verschiedene Primzahlen, n=p*q und sei phi_n = (p - 1)*(q - 1). Sei a eine ganze Zahl so, da§ a und n teilerfremd sind (ist GLEICHWERTIG zu: p teilt nich a und q teilt nicht a). Dann hat a^phi_n den Rest 1 bei der Division durch n. ________________________________ Ein Beispiel zum besseren VerstŠndnis: Sei p = 3 und q = 5, dann ist n = p*q = 3*5 = 15 ein. Dann phi_n = phi_15 = (3 - 1)*(5 - 1) = 2*4 = 8. WŠhlen wir a = 4. Dann sind (4) und n (15) teilerfremd und wir haben: a^phi_n = 4^8 = 4*4*4*4*4*4*4*4 = 65536 = 15*4369 + 1. Also bleibt der Rest 1 bei der Division durch 15 (nŠmlich n). Sie sollten einige Šhnliche Beispiele fŸr selbst durchrechnen. ____________________________________ Es ist dieser spezielle Fall vom Theorem Eulers (der Fall der beiden nterschiedlichen Primzahlen), der das kryptographische Protokoll von Rivest, Shamir und Adleman... untermauert. Entsprechend einem Artikel in der April Ausgabe 1995 von 'Math Horizons' (Mathematical Association of America at: 1529 Eighteenth Street, N.W., Washington, D.C., 20036), begannen Rivest und Shamir (von MIT) nach dem Lesen des Diffie-Hellman Papiers mit Versuchen zur Realisierung der Public-Key Idee. Zu dieser Zeit hatten sie einen neuen Kollegen: Adleman. Rivest und Shamir kamen mit einem Vorschlag an Adleman ... aber er fand einen Fehler in ihm. Erst ihr 43. Versuch war das jetzt berŸhmte RSA kryptographische Protokoll.... EMPFOHLENE ARTIKEL Au§er den Papieren, die oben erwŠhnt wurden (die eine gute Bibliothek kšnnte fŸr Sie erhalten), wŸrde eine grundlegende Liste betrŠchtlich sein, und so begrenze ich meine Liste auf gerade zwei BŸcher: 1. Titel: Kryptologie Autor: Albrecht Beutelspacher Verleger: Die mathematische Verbindung von Amerika (1994) ISBN: 0-88385-504-6 [ dieses ist ein grundlegender Text und umfa§t die Geschichte von Caesar bis zu den modernen Zeiten ] 2. Titel: PGP: Pretty Good Privacy (HŸbsches Gutes Privatleben) Autor: Simson Garfinkel Verleger: O'Reilly U. Teilnehmer, Inc.. (1995) ISBN: 1-56592-098-8 [ die beste Empfehlung fŸr dieses Buch ist sicher die von Phil Zimmerman (des Schšpfers von PGP), das von ihm sagte: "Ich erlernte sogar einige neue Sachen Ÿber PGP vom informativen Buch von Simson." ] Beide diese BŸcher haben umfangreiche Bibliographien, und das Buch Garfinkels schlie§t viele nŸtzliche E-mail Adressen ein (z.B. fŸr das Electronic Privacy Information Center (US Rechtschreibung) und die Electronic Frontier Foundation. Beide Institutionen geben regelmŠ§ig freie Dokumente in bezug auf Kryptographie heraus. Au§erdem sind sie durch E-mail Subskription, Web-Adressen von Usenet-Usegroups und Web-Adressen fŸr Freiexemplare 'ftp-ing' von PGP-Software erreichbar.