\mnb150ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fmodern\fprq1 Courier New;}{\f4\fswiss\fprq2 Arial;}{\f5\fswiss\fprq2\fcharset1 Arial;}{\f6\fmodern\fprq1\fcharset2 Courier New;}{\f7\froman\fprq2\fcharset1 Symbol;}{\f8\froman\fcharset1 Times New Roman;}{\f9\froman\fprq2\fcharset238{\*\fname Times New Roman;}Times New Roman CE;}{\f10\froman Times New Roman;}{\f11\fswiss\fprq2 Helvetica;}} {\colortbl\red0\green0\blue0;\red0\green128\blue0;\red128\green128\blue0;\red128\green128\blue128;\red255\green0\blue0;\red0\green0\blue255;\red0\green128\blue128;} \deflang1031\pard\ri4\plain\f3\fs20\cf0\b _________________________________________________________________________________ \par \par \plain\f3\fs20\cf0 Inhalt....: Einf\'fchrung in das RSA-Krypto-Verfahren \par Kategorie.: Unterrichtsmaterial \par Mathematik: Kryptographie, Zahlentheorie \par MuPAD.....: 3.0.0 \par Datum.....: 2002-06-10 \par Autoren...: Annamaria Pelles \plain\lang2057\f3\fs20\cf0 <\plain\f3\fs20\cf0 pellesa\plain\lang2057\f3\fs20\cf0 @freemail.hu> \par Autoren...: Kai Gehrs \par Funktionen: random, isprime, float, igcd, igcdex, mod, powermod, factor, \par Funktionen: nextprime, time\plain\f3\fs20\cf0 \par \plain\f3\fs20\cf0\b _________________________________________________________________________________ \par \plain\f4\fs20\cf0\b \par \plain\f4\fs36\cf0\b Einf\'fchrung in das RSA-Krypto-Verfahren \par \plain\f4\fs28\cf1\b \par \plain\f4\fs24\cf1 RSA ist derzeit quasi der weltweite Standard f\'fcr public-key-Verfahren. \par Wir werden sehen wie RSA f\'fcr die zwei wesentlichen Aufgaben der Kryptographie benutzt werden \par kann. Hierbei handelt es sich um die \par \par \tab \tab \tab \tab \tab 1. Verschl\'fcsselung von Nachrichten \par \tab \tab \tab \tab \tab 2. Entschl\'fcsselung von Nachrichten \par \par Dieses Notebook pr\'e4sentiert stellenweise mathematische Sachverhalte, die \'fcber den Rahmen \par dessen, was man in der Schule behandelt hinausgehen. Diese komplizierteren Sachverhalte \par kann man jedoch getrost \'fcberlesen, wenn man sich nur daf\'fcr interessiert, wie mit Hilfe des \par RSA-Verfahrens Botschaften ver- oder entschl\'fcsselt werden. Dar\'fcber hinaus kann dieses \par Notebook eventuell als Anreiz f\'fcr eine eventuelle Facharbeit verwendet werden. \par \plain\f5\fs28\cf0 \par \plain\f4\fs28\cf2\b \par Wozu dient das RSA-Krypto-Verfahren? \par \plain\f4\fs28\cf0 \par Wir erkl\'e4ren das Verfahren an einem Beispiel: B\plain\f4\fs28\cf0\i o\plain\f4\fs28\cf0 b m\'f6chte an Alice eine \par Nachricht M senden, ohne dass eine dritte Person, wir nennen sie Eve, diese \par Nachricht lesen kann, obwohl Eve \tab unbeschr\'e4nkten Zugang zum Kommunikations- \par kanal zwischen Alice und Bob hat. \par \par Die L\'f6sung besteht darin die Nachricht M zu verschl\'fcsseln. Das Verfahren kann \par man sich grafisch wie folgt vorstellen: \par \tab \par \par \plain\f3\fs24\cf3\b Kanal \par Bob ----\plain\lang2057\f3\fs24\cf3\b ->\plain\f3\fs24\cf3\b Verschl\'fcsselung -------------\plain\lang2057\f3\fs24\cf3\b -> \plain\f3\fs24\cf3\b Entschl\'fcsselung ----\plain\lang2057\f3\fs24\cf3\b ->\plain\f3\fs24\cf3\b Alice \par \plain\lang1038\f6\fs24\cf3\b \tab \tab \tab \tab \tab \tab | \par \tab \tab \tab \tab \tab \tab | \par \tab \tab \tab \tab \tab \tab | \par \tab \tab \tab \tab \tab \tab | \par \tab \tab \tab \tab \tab Eve \par \plain\f4\fs28\cf2\b \par \par Wie funktioniert dieses Verfahren im Detail? \par \plain\f4\fs28\cf0\i \par \plain\f4\fs28\cf0 Bob m\'f6chte also an Alice eine Nachricht senden, so dass nur Alice diese \par Nachricht lesen kann, und niemand anderes. \par \par Aus diesem Grund erzeugt Alice einen sogenannten \plain\f4\fs28\cf0\b private key\plain\f4\fs28\cf0 \plain\f4\fs28\cf0\b S\plain\f4\fs28\cf0 (privater \par Schl\'fcssel) und einen \plain\f4\fs28\cf0\b public key K \plain\f4\fs28\cf0 (\'f6ffentlicher Schl\'fcssel). Jeder kann \plain\f4\fs28\cf0\b K\plain\f4\fs28\cf0\i \plain\f4\fs28\cf0 lesen, \par aber \plain\f4\fs28\cf0\b S\plain\f4\fs28\cf0\i \plain\f4\fs28\cf0 ist ein Geheimnis. \par \par Auch Bob kennt nur \plain\f4\fs28\cf0\b K\plain\f4\fs28\cf0 . Wenn nun Bob eine Nachricht an Alice schickt, mu\'df er zur \par Verschl\'fcsselung \plain\f4\fs28\cf0\b K \plain\f4\fs28\cf0 verwenden: Bei Empfang der Nachricht kann Alice mit ihrem \par \plain\f4\fs28\cf0\b privaten Schl\'fcssel \plain\f4\fs28\cf0 die Nachricht entschl\'fcsseln. \par \par Die Nachricht kann aus Texten, Bildern, Dateien oder Programfiles etc. bestehen; \par die Nachricht soll aber immer in der oben genannten Form verschl\'fcsselt werden. \par \par Im folgenden werden wir Schritt f\'fcr Schritt das Verfahren der \plain\f4\fs28\cf0\b Verschl\'fcsselung\plain\f4\fs28\cf0 \par (damit niemand anderer die Nachricht lesen kann) und der \plain\f4\fs28\cf0\b Entschl\'fcsselung\plain\f4\fs28\cf0 \par an einem Beispiel verstehen lernen. \par \plain\f4\fs28\cf0\ul \par \plain\f4\fs28\cf6 Schritt (1): \plain\f4\fs28\cf0 Alice w\'e4hlt zuf\'e4llig zwei Primzahlen p und q. \par \plain\f5\fs28\cf4 \par \plain\f5\fs28\cf0 Zur Erinnerung: Eine Primzahl ist eine positive ganze Zahl, die nur durch 1 und sich \par selbst (ganzzahlig) teilbar ist. \par \par Zum Beispiel ist 25 keine Primzahl, denn 5 * 5 ist 25 und damit 5 ein Teiler von 25. \par Dagegen ist 7 eine Primzahl, denn 2,3,4,5 und 6 sind keine Teiler von 7. \par \par Mit MuPAD k\'f6nnen wir Zufallszahlen mit Hilfe der Funktion \plain\f5\fs28\cf4 random() \plain\f5\fs28\cf0 erzeugen. \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}Zufall:= random(1..500) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw4577\pich901\picwgoal2594\pichgoal510 010009000003D301000006001C0000000000050000000B0200000000050000000C028503E11103 0000001E00030000001E00050000000C02FF01230A050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000BD090A15E8EC1200B8A4F177C1A4F1772030F3773A0A664F040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F3773A0A664F040000002D0103000B0000 0026060F000C004D61746854797065000080001C000000FB02E8FE000000000000900100000002 070000005346204D6174682045787400E8EC1200B8A4F177C1A4F1772030F3773A0A664F040000 002D010400040000002D0103000500000009020000FF00070000002105010070015E0165000700 00002105010072015E01F10007000000210501006F015E014E01070000002105010063015E01DA 01070000002105010020015E015602070000002105010072015E019C0207000000210501006101 5E01F90207000000210501006E015E017503070000002105010064015E01010407000000210501 006F015E018D0407000000210501006D015E011905040000002D01040007000000210501002801 5E01F305070000002105010029015E016006040000002D010300070000002105010020015E01CD 0607000000210501002E015E01130707000000210501002E015E01590707000000210501002E01 5E019F07070000002105010020015E01E507070000002105010065015E012B0807000000210501 006E015E01A708070000002105010064015E01330908000000FA02000000000000000000000400 00002D01050004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000DC0A 0A78E8EC1200B8A4F177C1A4F1772030F3773A0A664F040000002D010100040000002701FFFF04 000000F001020004000000F001030004000000F0010400040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 \par Eine Zufallszahl wird nun immer aus der Menge \{1,2,3,...,499,500\} gew\'e4hlt: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}p:= Zufall() \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw847\pich901\picwgoal480\pichgoal510 0100090000031E01000005001C0000000000050000000B0200000000050000000C0285034F0303 0000001E00030000001E00050000000C02FF01E001050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C0000003A0A0A50E8EC1200B8A4F177C1A4F1772030F377A60A6628040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377A60A6628040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003801 5E016400070000002105010032015E01F00008000000FA0200000000000000000000040000002D 01040004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F001 01001C000000FB021000070000000000BC02000000000102022253797374656D0000BD090A16E8 EC1200B8A4F177C1A4F1772030F377A60A6628040000002D010100040000002701FFFF04000000 F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 \par Wie k\'f6nnen wir nun schnell herausfinden, ob die erzeugte Zufallszahl eine Primzahl \par ist? \par \par Die MuPAD Funktion \plain\f5\fs28\cf4 isprime\plain\f5\fs28\cf0 testet, ob p eine Primzahl ist oder nicht, d.h. \par \plain\f5\fs28\cf4 isprime(p)\plain\f5\fs28\cf0 liefert \plain\f5\fs28\cf5 true\plain\f5\fs28\cf0 , wenn p eine Primzahl ist, und \plain\f5\fs28\cf5 false\plain\f5\fs28\cf0 , wenn p eine \par zusammengesetzte Zahl ist. \par \par Wenn p keine Primzahl ist, dann m\'fcssen wir das obige Verfahren nochmals \par wiederholen, bis wir mit p eine Primzahl gefunden haben. \par \plain\f3\fs28\cf5 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}isprime(p) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1863\pich901\picwgoal1056\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503470703 0000001E00030000001E00050000000C02FF012004050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000A60A0A29E8EC1200B8A4F177C1A4F1772030F377100966B1040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966B1040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501004601 5E016400070000002105010041015E01000107000000210501004C015E01CA0107000000210501 0053015E017502070000002105010045015E01110308000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000BD09 0A17E8EC1200B8A4F177C1A4F1772030F377100966B1040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 \par Eine M\'f6glichkeit besteht nun darin, die obige Befehlszeile \plain\f3\fs28\cf4 p:= Zufall() \par \plain\f5\fs28\cf0 so lange auszuf\'fchren, bis p eine Primzahl eine Primzahl ist. \par \par Wir verfahren wie folgt: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}p:= Zufall(): \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf4 while isprime(p) = FALSE do \par p:= Zufall(); \par end_while: \par p; \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1094\pich901\picwgoal620\pichgoal510 0100090000032501000005001C0000000000050000000B0200000000050000000C028503460403 0000001E00030000001E00050000000C02FF016C02050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AB2E8EC1200B8A4F177C1A4F1772030F3773A0A6653040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F3773A0A6653040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003201 5E016400070000002105010037015E01F000070000002105010031015E017C0108000000FA0200 000000000000000000040000002D01040004000000F001000007000000FC020000FFFFFF000000 040000002D01000004000000F00101001C000000FB021000070000000000BC0200000000010202 2253797374656D0000BD090A18E8EC1200B8A4F177C1A4F1772030F3773A0A6653040000002D01 0100040000002701FFFF04000000F001020004000000F0010300040000002701FFFF0300000000 00 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 Dieses Verfahren scheint nicht sehr elegant zu sein, aber es f\'fchrt nach kurzer \par Zeit zum Ziel, denn der sogenannte \plain\f5\fs28\cf0\b Primzahlsatz\plain\f5\fs28\cf0 der Zahlentheorie besagt, \par dass in einem vorgegebenen Intervall stets hinreichend "viele" Primzahlen \par vorhanden sind. \par \par \par \tab \plain\f5\fs28\cf0\b Primzahlsatz.\plain\f5\fs28\cf0 \tab Ist x eine positive Zahl und bezeichnet \plain\f7\fs28\cf0 p\plain\f5\fs28\cf0 (x) die Anzahl der \par \tab Primzahlen, die kleiner oder gleich x sind, so gilt: \par \tab \par \tab \tab {\pict\wmetafile8\picw2830\pich1155\picscalex99\picscaley99\picwgoal1617\pichgoal658 010009000003180C000008001C0000000000050000000B0200000000050000000C0283040E0B03 0000001E00050000000C028A04250B050000000B0200000000030000001E00050000000C029104 2C0B050000000B0200000000050000000B0200000000030000001E00050000000C029704430B05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C029E044B0B050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C02A404630B050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C02AB046A0B050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C02B204830B050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C02B9048A0B050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C02C004A30B05000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C02C704A90B050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C02CE04C30B050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C02D504C90B050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00050000000C02DC04E30B050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000030000001E00050000000C02E304 E80B050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000030000001E00050000000C02EA04 030C050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00050000000C02F104090C050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C02F804250C050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C02FF042A0C050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C020605470C050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C020D054C0C05000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C021405670C050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C021C056E0C050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C0223058A0C050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C022C05910C050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C023305AC0C050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000030000001E00050000000C023C05B30C05 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000030000001E00050000000C024305 CF0C050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000003 0000001E00050000000C024C05D60C050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000030000001E00030000001E00050000000C 0201034707050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B020000000008000000FA020000000000000000000004 0000002D0100001C000000FB0238FF00000000000090010000000107000000417269616C000000 3A0A0A54E8EC1200B8A4F177C1A4F1772030F377A60A662C040000002D01010005000000020101 000000050000000102FFFFFF00050000002E011800000005000000090200000000040000000801 00001C000000FB02C0FE0000000000009001000000010700000054696D6573204E657720526F6D 616E00B8A4F177C1A4F1772030F377A60A662C040000002D0102000B00000026060F000C004D61 746854797065000017011C000000FB02C0FE0000000000009001000000020700000053796D626F 6C0000BD090A19E8EC1200B8A4F177C1A4F1772030F377A60A662C040000002D0103001C000000 FB02C0FE0000000000009001010000010700000054696D6573204E657720526F6D616E00B8A4F1 77C1A4F1772030F377A60A662C040000002D0104001C000000FB02C0FE00000000000090010000 0002070000005346204D6174682045787400E8EC1200B8A4F177C1A4F1772030F377A60A662C04 0000002D010500040000002D010200040000002D010500040000002D010200040000002D010400 040000002D010200040000002D010400040000002D010500040000002D010200040000002D0105 00040000002D010200040000002D010300040000002D010200040000002D010300070000002105 01007001A4016400040000002D010500040000002D010200040000002D010500040000002D0102 00040000002D01050007000000210501002801A4011401040000002D010300040000002D010400 07000000210501007801A4019B01040000002D010500040000002D010200040000002D01050004 0000002D010200040000002D01050007000000210501002901A4012902040000002D0103000700 0000210501003D01A4010503040000002D010200040000002D0104000700000021050100780114 013A05040000002D01020007000000210501006C015D02370407000000210501006E015D029004 040000002D010500040000002D010200040000002D010500040000002D010200040000002D0105 00070000002105010028015D023005040000002D010300040000002D0104000700000021050100 78015D02B705040000002D010500040000002D010200040000002D010500040000002D01020004 0000002D010500070000002105010029015D0245060700000021050100C5013A01150407000000 21050100C5013A01D5040700000021050100C5013A0195050700000021050100C5013A01230608 000000FA0200000000000000000000040000002D0106001C000000FB021000070000000000BC02 000000000102022253797374656D0000F40A0A23E8EC1200B8A4F177C1A4F1772030F377A60A66 2C040000002D010700040000002701FFFF04000000F001000004000000F001010004000000F001 020004000000F001030004000000F001040004000000F0010500040000002701FFFF0400000027 01FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF04000000 2701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000 002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400 00002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF04 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 \par \par \par Was bedeutet dies nun in unserem Beispiel? In unserer Situation gilt x = 1000. \par Also gilt: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}hold(PI(x)) = float(1000/ln(1000)) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw4406\pich901\picwgoal2497\pichgoal510 0100090000033C02000008001C0000000000050000000B0200000000050000000C028503361103 0000001E00030000001E00050000000C02FF01C209050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000A60A0A2DE8EC1200B8A4F177C1A4F1772030F377F40A6625040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A6625040000002D0103000B0000 0026060F000C004D61746854797065000080001C000000FB02E8FE000000000000900100000002 0700000053796D626F6C0000DC0A0A7AE8EC1200B8A4F177C1A4F1772030F377F40A6625040000 002D0104001C000000FB02E8FE0000000000009001010000010700000054696D6573204E657720 526F6D616E00B8A4F177C1A4F1772030F377F40A6625040000002D0105001C000000FB02E8FE00 0000000000900100000002070000005346204D6174682045787400E8EC1200B8A4F177C1A4F177 2030F377F40A6625040000002D010600040000002D010300040000002D010600040000002D0103 00040000002D010400040000002D010300040000002D0104000500000009020000FF0007000000 2105010070015E016400040000002D010600040000002D010300040000002D010600040000002D 010300040000002D010600070000002105010028015E01FE00040000002D010300040000002D01 0500070000002105010078015E017501040000002D010600040000002D010300040000002D0106 00040000002D010300040000002D010600070000002105010029015E01F101040000002D010400 07000000210501003D015E01B202040000002D010300070000002105010031015E01A003070000 002105010034015E012C04070000002105010034015E01B80407000000210501002E015E014405 070000002105010037015E018A05070000002105010036015E011606070000002105010034015E 01A206070000002105010038015E012E07070000002105010032015E01BA070700000021050100 37015E014608070000002105010033015E01D20808000000FA0200000000000000000000040000 002D01070004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000 F00101001C000000FB021000070000000000BC02000000000102022253797374656D00003A0A0A 55E8EC1200B8A4F177C1A4F1772030F377F40A6625040000002D010100040000002701FFFF0400 0000F001020004000000F001030004000000F001040004000000F001050004000000F001060004 0000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 \par Es gibt also n\'e4herungsweise 144 Primzahlen in der Menge \{1,2,3,...,999,1000\}, \par d.h. wiederum, dass die Wahrscheinlichkeit, dass eine gew\'e4hlte Zufallszahl eine \par Primzahl ist, betr\'e4gt n\'e4herungsweise \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}float(144/1000) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1464\pich901\picwgoal829\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503B80503 0000001E00030000001E00050000000C02FF013E03050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A26E8EC1200B8A4F177C1A4F1772030F377100966B6040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966B6040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003001 5E01640007000000210501002E015E01F000070000002105010031015E01360107000000210501 0034015E01C201070000002105010034015E014E0208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000DC0A 0A7BE8EC1200B8A4F177C1A4F1772030F377100966B6040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 \par d.h. 14,4%. Dies bedeutet, dass wir innerhalb von 10 Versuchen in der Regel \par mindestens eine Primzahl finden werden. \par \par Nun zur\'fcck zu Bob und Alice: Jetzt muss Alice nach der gleichen Methode die \par zweite Primzahl q w\'e4hlen.\plain\f8\fs28\cf0 \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}q:= Zufall(): \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf4 while isprime(q) = FALSE do \par q:= Zufall(); \par end_while: \par q; \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1094\pich901\picwgoal620\pichgoal510 0100090000032501000005001C0000000000050000000B0200000000050000000C028503460403 0000001E00030000001E00050000000C02FF016C02050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AB7E8EC1200B8A4F177C1A4F1772030F377BD09661D040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377BD09661D040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003201 5E016400070000002105010036015E01F000070000002105010039015E017C0108000000FA0200 000000000000000000040000002D01040004000000F001000007000000FC020000FFFFFF000000 040000002D01000004000000F00101001C000000FB021000070000000000BC0200000000010202 2253797374656D0000DC0A0A7CE8EC1200B8A4F177C1A4F1772030F377BD09661D040000002D01 0100040000002701FFFF04000000F001020004000000F0010300040000002701FFFF0300000000 00 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 Schon haben wir p und q gefunden, n\'e4mlich \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}p,q \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw2131\pich901\picwgoal1208\pichgoal510 0100090000034101000005001C0000000000050000000B0200000000050000000C028503530803 0000001E00030000001E00050000000C02FF01B804050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000BD090A1EE8EC1200B8A4F177C1A4F1772030F377F40A6629040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A6629040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003201 5E016400070000002105010037015E01F000070000002105010031015E017C0107000000210501 002C015E010802070000002105010032015E01B002070000002105010036015E013C0307000000 2105010039015E01C80308000000FA0200000000000000000000040000002D01040004000000F0 01000007000000FC020000FFFFFF000000040000002D01000004000000F00101001C000000FB02 1000070000000000BC02000000000102022253797374656D0000DC0A0A7DE8EC1200B8A4F177C1 A4F1772030F377F40A6629040000002D010100040000002701FFFF04000000F001020004000000 F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf6 \par Schritt (2):\plain\f5\fs28\cf0 Alice muss N und Phi(N) berechnen, wobei N = p*q und Phi(N) wie \par folgt erkl\'e4rt ist: \par \par \tab F\'fcr eine nat\'fcrliche Zahl k ist \plain\f5\fs28\cf0\b Phi(k)\plain\f5\fs28\cf0 definiert als die Anzahl der zu k \par \tab teilerfremden Zahlen (dazu geh\'f6rt auch die 1), die kleiner sind als k. \par \par Zum Beispiel ist Phi(6) = 2, denn nur 1 und 5 sind kleiner als 6 und teilerfremd \par zu 6. Andererseits ist Phi(7) = 6, denn alle Zahlen 1,2,3,4,5 und 6 sind teilerfremd \par zu 7. \par \par Allgemein gelten die folgenden Rechenregeln f\'fcr die Eulersche Phi-Funktion. \par \par \plain\f5\fs28\cf0\b Rechenregeln f\'fcr die Eulersche Phi Funktion: \tab \par \plain\f5\fs28\cf0 \tab \tab \tab \tab \tab \par \tab \tab Phi(1) = 1 \par \tab \tab Phi(p) = p-1, wenn p eine Primzahl ist. \par \plain\lang1038\f4\fs28 \tab \tab Phi(p\plain\f4\fs28 *q) = (p - 1) * (q - 1), wenn p und q Primzahlen sind.\plain\lang1038\f4\fs28 \par \plain\lang1038\f9\fs28\i\up12 \plain\f8\fs28\cf0\ul \par \plain\lang1038\f4\fs28 Wir werden im folgenden nur die dritte Regel benutzen. Wer die Eulersche \par Phi-Funktion nicht kennt, kann sich daher f\'fcr alles folgende merken: \par Phi(N) ist stets das Produkt (p - 1) * (q - 1). \plain\f8\fs28\cf0 \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}N:=p*q; Phi_N:= (p-1)*(q-1) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1588\pich901\picwgoal900\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503340603 0000001E00030000001E00050000000C02FF018403050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A2AE8EC1200B8A4F177C1A4F1772030F377100966BA040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966BA040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003701 5E016400070000002105010032015E01F000070000002105010038015E017C0107000000210501 0039015E010802070000002105010039015E01940208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000DC0A 0A7EE8EC1200B8A4F177C1A4F1772030F377100966BA040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1588\pich901\picwgoal900\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503340603 0000001E00030000001E00050000000C02FF018403050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090ABBE8EC1200B8A4F177C1A4F1772030F377BD096621040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377BD096621040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003700 5E016400070000002105010032005E01F000070000002105010033005E017C0107000000210501 0036005E010802070000002105010030005E01940208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000DC0A 0A7FE8EC1200B8A4F177C1A4F1772030F377BD096621040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \par \pard\ri4\plain\f5\fs28\cf6 \par Schritt(3):\plain\f5\fs28\cf0 \plain\f4\fs28\cf0 Alice berechnet ihren \'f6ffentlichen Exponenten e auf folgende \par Weise: \plain\f5\fs28\cf0 Sie w\'e4hlt e zuf\'e4llig und teilerfremd zu Phi(N). \par \plain\f8\fs28\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}Zufall:= random(2..Phi_N-2) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw4577\pich901\picwgoal2594\pichgoal510 010009000003D301000006001C0000000000050000000B0200000000050000000C028503E11103 0000001E00030000001E00050000000C02FF01230A050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000BD090A22E8EC1200B8A4F177C1A4F1772030F377F40A662D040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A662D040000002D0103000B0000 0026060F000C004D61746854797065000080001C000000FB02E8FE000000000000900100000002 070000005346204D6174682045787400E8EC1200B8A4F177C1A4F1772030F377F40A662D040000 002D010400040000002D0103000500000009020000FF00070000002105010070005E0165000700 00002105010072005E01F10007000000210501006F005E014E01070000002105010063005E01DA 01070000002105010020005E015602070000002105010072005E019C0207000000210501006100 5E01F90207000000210501006E005E017503070000002105010064005E01010407000000210501 006F005E018D0407000000210501006D005E011905040000002D01040007000000210501002800 5E01F305070000002105010029005E016006040000002D010300070000002105010020005E01CD 0607000000210501002E005E01130707000000210501002E005E01590707000000210501002E00 5E019F07070000002105010020005E01E507070000002105010065005E012B0807000000210501 006E005E01A708070000002105010064005E01330908000000FA02000000000000000000000400 00002D01050004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000A50A 0A1EE8EC1200B8A4F177C1A4F1772030F377F40A662D040000002D010100040000002701FFFF04 000000F001020004000000F001030004000000F0010400040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}e:= Zufall() \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1588\pich901\picwgoal900\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503340603 0000001E00030000001E00050000000C02FF018403050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A2EE8EC1200B8A4F177C1A4F1772030F377DC0A6682040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A6682040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003500 5E016400070000002105010034005E01F000070000002105010036005E017C0107000000210501 0038005E010802070000002105010033005E01940208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000BD09 0A23E8EC1200B8A4F177C1A4F1772030F377DC0A6682040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 \par In MuPAD berechnet \plain\f5\fs28\cf4 igcd \plain\f5\fs28\cf0 (integer greatest common divisor) den gr\'f6\'dften \par gemeinsamen Teiler zweier Zahlen. \par \par Um zu pr\'fcfen, ob e und Phi(N) tats\'e4chlich teilerfremd sind, berechnen wir \par einfach ihren gr\'f6\'dften gemeinsamen Teiler. Ist dieser 1, so haben wir \par ein passendes e gefunden. Ist dieser gr\'f6\'dfer oder gleich 2, so w\'e4hlen wir \par ein neues e. Auch dieses Verfahren liefert beweisbar innerhalb kurzer Zeit \par einen passenden Wert f\'fcr e. \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}igcd(e,Phi_N) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw600\pich901\picwgoal340\pichgoal510 0100090000031701000005001C0000000000050000000B0200000000050000000C028503580203 0000001E00030000001E00050000000C02FF015401050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000DC0A0A83E8EC1200B8A4F177C1A4F1772030F377100966BF040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966BF040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E01640008000000FA0200000000000000000000040000002D01040004000000F0010000070000 00FC020000FFFFFF000000040000002D01000004000000F00101001C000000FB02100007000000 0000BC02000000000102022253797374656D0000BD090A24E8EC1200B8A4F177C1A4F1772030F3 77100966BF040000002D010100040000002701FFFF04000000F001020004000000F00103000400 00002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf6 \par Schritt(4):\plain\f5\fs28\cf0 Alice berechnet ihren privaten Exponenten d als Inverses von e \par modulo Phi(N). \par \par Das \plain\f5\fs28\cf0\b modulare Inverse\plain\f5\fs28\cf0 berechnet man mit Hilfe des Euklidischen Algorithmus. \par \par F\'fcr zwei Zahlen a und m liefert der Euklidische Algorithmus nicht nur den \par gr\'f6\'dften gemeinsamen Teiler g, sondern auch Zahlen k und l, so dass gilt: \par \par g = k * a + l * m \par \par Reduziert man diese Gleichung modulo m (d.h. man rechnet auf beiden \par Seiten modulo m - man nimmt also einfach den Rest, der bei ganzzahliger \par Division der Zahlen durch m verbleibt), so ergibt sich wegen m modulo m = 0: \par \par \tab g modulo m = (k * a) modulo m \par \par Ist nun g = 1, also der gr\'f6\'dfte gemeinsame Teiler von a und m ist 1, so folgt: \par \par \tab 1 modulo m = (k * a) modulo m \par \par d.h. k ist das modulare Inverse zu a (denn k * a ist 1 modulo m). \par \par In unserer Situation setzen wir f\'fcr m die Zahl Phi(N) ein und f\'fcr a die Zahl e. \par Die Zahl k wird dann Alices privater Exponent, d.h. k = d. \par \plain\f8\fs28\cf0 \par \plain\f5\fs28\cf0 Mit der MuPAD Funktion \plain\f5\fs28\cf4 igcdex\plain\f5\fs28\cf0 kann man die Werte g, k und l des Euklidischen \par Algorithmus berechnen. \plain\f8\fs28\cf0 \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}igcdex(e,Phi_N) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw3859\pich901\picwgoal2187\pichgoal510 0100090000039B01000006001C0000000000050000000B0200000000050000000C028503130F03 0000001E00030000001E00050000000C02FF018C08050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AC0E8EC1200B8A4F177C1A4F1772030F377F40A6631040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A6631040000002D0103000B0000 0026060F000C004D61746854797065000080001C000000FB02E8FE000000000000900100000002 0700000053796D626F6C0000BD090A25E8EC1200B8A4F177C1A4F1772030F377F40A6631040000 002D010400040000002D0103000500000009020000FF00070000002105010031005E0164000700 0000210501002C005E01F000040000002D01040007000000210501002D005E01C201040000002D 010300070000002105010031005E019402070000002105010032005E0120030700000021050100 31005E01AC03070000002105010033005E013804070000002105010033005E01C4040700000021 0501002C005E015005070000002105010039005E01F805070000002105010031005E0184060700 00002105010036005E011007070000002105010039005E019C0708000000FA0200000000000000 000000040000002D01050004000000F001000007000000FC020000FFFFFF000000040000002D01 000004000000F00101001C000000FB021000070000000000BC0200000000010202225379737465 6D0000A50A0A1FE8EC1200B8A4F177C1A4F1772030F377F40A6631040000002D01010004000000 2701FFFF04000000F001020004000000F001030004000000F0010400040000002701FFFF030000 000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}dd:= op(igcdex(e,Phi_N),2) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw2032\pich901\picwgoal1152\pichgoal510 0100090000036A01000006001C0000000000050000000B0200000000050000000C028503F00703 0000001E00030000001E00050000000C02FF018004050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A32E8EC1200B8A4F177C1A4F1772030F377BD096627040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377BD096627040000002D0103000B0000 0026060F000C004D61746854797065000080001C000000FB02E8FE000000000000900100000002 0700000053796D626F6C000010090AC1E8EC1200B8A4F177C1A4F1772030F377BD096627040000 002D010400040000002D010300040000002D0104000500000009020000FF000700000021050100 2D005E018E00040000002D010300070000002105010031005E016001070000002105010032005E 01EC01070000002105010031005E017802070000002105010033005E0104030700000021050100 33005E01900308000000FA0200000000000000000000040000002D01050004000000F001000007 000000FC020000FFFFFF000000040000002D01000004000000F00101001C000000FB0210000700 00000000BC02000000000102022253797374656D0000A50A0A20E8EC1200B8A4F177C1A4F17720 30F377BD096627040000002D010100040000002701FFFF04000000F001020004000000F0010300 04000000F0010400040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f4\fs28\cf0 \par Da Alices privater Schl\'fcssel d eine positive Zahl sein muss, m\'fcssen wir zu dem \par Wert dd einmal Phi(N) addieren, falls dd negativ ist. Andernfalls k\'f6nnen wir \par dd als Wert f\'fcr d w\'e4hlen. Dies h\'f6rt sich jetzt unglaublich kompliziert an, aber \par wir m\'fcssen alle F\'e4lle ber\'fccksichtigen, denn wir haben e ja als zuf\'e4lligen Wert \par gew\'e4hlt. \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}if dd < 0 then \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf4 d:= dd + Phi_N; \par else \par d:= dd; \par end_if: \par print(Unquoted, "d = ".d); \par \pard\li50\ri6\plain\f3\fs28\cf5\protect d = 60227 \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f4\fs28\cf0 \par d.h. es gilt \par 1 = (d * e) modulo Phi(N) \par \par Wir k\'f6nnen das Ergebnis \'fcberpr\'fcfen: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}(d * e) mod Phi_N \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw600\pich901\picwgoal340\pichgoal510 0100090000031701000005001C0000000000050000000B0200000000050000000C028503580203 0000001E00030000001E00050000000C02FF015401050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000BD090A28E8EC1200B8A4F177C1A4F1772030F377100966C3040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966C3040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E01640008000000FA0200000000000000000000040000002D01040004000000F0010000070000 00FC020000FFFFFF000000040000002D01000004000000F00101001C000000FB02100007000000 0000BC02000000000102022253797374656D0000F40A0A33E8EC1200B8A4F177C1A4F1772030F3 77100966C3040000002D010100040000002701FFFF04000000F001020004000000F00103000400 00002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f4\fs28\cf0 \par \plain\f4\fs28\cf6 Schritt(5): \plain\f4\fs28\cf0 Alice ver\'f6ffentlicht das Paar (N,e) (\'f6ffentlicher Schl\'fcssel) und beh\'e4lt \par (N,d) als Geheimnis (geheimer Schl\'fcssel). Schauen wir uns die bisher \par berechneten Werte einmal an: \par \plain\f8\fs28\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}N,e \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw3119\pich901\picwgoal1768\pichgoal510 0100090000035D01000005001C0000000000050000000B0200000000050000000C0285032F0C03 0000001E00030000001E00050000000C02FF01E806050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AC4E8EC1200B8A4F177C1A4F1772030F377DC0A6688040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A6688040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003700 5E016400070000002105010032005E01F000070000002105010038005E017C0107000000210501 0039005E010802070000002105010039005E01940207000000210501002C005E01200307000000 2105010035005E01C803070000002105010034005E015404070000002105010036005E01E00407 0000002105010038005E016C05070000002105010033005E01F80508000000FA02000000000000 00000000040000002D01040004000000F001000007000000FC020000FFFFFF000000040000002D 01000004000000F00101001C000000FB021000070000000000BC02000000000102022253797374 656D0000F40A0A34E8EC1200B8A4F177C1A4F1772030F377DC0A6688040000002D010100040000 002701FFFF04000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}N,d \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw3119\pich901\picwgoal1768\pichgoal510 0100090000035D01000005001C0000000000050000000B0200000000050000000C0285032F0C03 0000001E00030000001E00050000000C02FF01E806050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000DC0A0A89E8EC1200B8A4F177C1A4F1772030F377BD09662B040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377BD09662B040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003700 5E016400070000002105010032005E01F000070000002105010038005E017C0107000000210501 0039005E010802070000002105010039005E01940207000000210501002C005E01200307000000 2105010036005E01C803070000002105010030005E015404070000002105010032005E01E00407 0000002105010032005E016C05070000002105010037005E01F80508000000FA02000000000000 00000000040000002D01040004000000F001000007000000FC020000FFFFFF000000040000002D 01000004000000F00101001C000000FB021000070000000000BC02000000000102022253797374 656D0000F40A0A35E8EC1200B8A4F177C1A4F1772030F377BD09662B040000002D010100040000 002701FFFF04000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf6 \par Schritt (6):\plain\f5\fs28\cf0 Alice l\'f6scht p, q und Phi(N) vom Computer - sie ben\'f6tigt diese Zahlen \par nicht mehr. Sie sollte sie auch l\'f6schen, damit diese Eve nicht auf ihrem Computer \par finden kann. \par \par Jetzt m\'f6chte Bob an Alice eine Nachricht senden; was mu\'df er jetzt tun? \par \par \plain\f5\fs28\cf6 Schritt(7):\plain\f5\fs28\cf0 Bob m\'f6chte Alice zum Beispiel eine Zahl x senden, x soll zwischen \par 1 und N sein, also z.B. x = 13 \par \plain\f5\fs28\cf0\ul \par \plain\f5\fs28\cf0 Bob soll x zu einem y verschl\'fcsseln. y ist x^e mod N. Bob berechnet also die \par Zahl y und sendet sie an Alice. Auf diese Weise hat er x zu y verschl\'fcsselt. \par Die folgenden Rechnungen ben\'f6tigen durchaus etwas mehr Zeit. Man \par m\'f6ge sich gedulden. Wir werden uns sp\'e4ter damit besch\'e4ftigen, warum \par diese Rechnung so zeitintensiv ist und wie wir sie effizienter durchf\'fchren \par k\'f6nnen. \par \plain\f8\fs28\cf0\ul \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}x:= 13 \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw847\pich901\picwgoal480\pichgoal510 0100090000031E01000005001C0000000000050000000B0200000000050000000C0285034F0303 0000001E00030000001E00050000000C02FF01E001050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000BD090A2CE8EC1200B8A4F177C1A4F1772030F377100966C7040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966C7040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010033005E01F00008000000FA0200000000000000000000040000002D 01040004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F001 01001C000000FB021000070000000000BC02000000000102022253797374656D0000F40A0A36E8 EC1200B8A4F177C1A4F1772030F377100966C7040000002D010100040000002701FFFF04000000 F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}y:=x^e mod N \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1588\pich901\picwgoal900\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503340603 0000001E00030000001E00050000000C02FF018403050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AC8E8EC1200B8A4F177C1A4F1772030F377DC0A668C040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A668C040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003700 5E016400070000002105010032005E01F000070000002105010037005E017C0107000000210501 0037005E010802070000002105010034005E01940208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000F40A 0A37E8EC1200B8A4F177C1A4F1772030F377DC0A668C040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f4\fs28\cf0 \par \plain\f4\fs28\cf6 Schritt(8): \plain\f4\fs28\cf0 Alice berechnet den Wert xx mit Hilfe ihres eigenen geheimen \par Exponenten d. Dazu bestimmt sie y^d modulo N (dass dieses Verfahren \par bei korrekter Anwendung immer funktioniert und wieder den urspr\'fcnglichen \par Wert von x liefert, kann man mit Mitteln aus der Zahlentheorie beweisen, \par die allerdings den Rahmen dieses Notebooks sprengen). \par \plain\f8\fs28\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}xx:= y^d mod N \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw847\pich901\picwgoal480\pichgoal510 0100090000031E01000005001C0000000000050000000B0200000000050000000C0285034F0303 0000001E00030000001E00050000000C02FF01E001050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000DC0A0A8DE8EC1200B8A4F177C1A4F1772030F377BD09662F040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377BD09662F040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010033005E01F00008000000FA0200000000000000000000040000002D 01040004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F001 01001C000000FB021000070000000000BC02000000000102022253797374656D0000F40A0A38E8 EC1200B8A4F177C1A4F1772030F377BD09662F040000002D010100040000002701FFFF04000000 F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f4\fs28\cf0 \par Probe: Ist x gleich xx?\plain\f10\fs28\cf0 \par \plain\f8\fs28\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}x = xx \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1909\pich901\picwgoal1082\pichgoal510 0100090000036B01000006001C0000000000050000000B0200000000050000000C028503750703 0000001E00030000001E00050000000C02FF013A04050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000BD090A30E8EC1200B8A4F177C1A4F1772030F377100966CB040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966CB040000002D0103000B0000 0026060F000C004D61746854797065000080001C000000FB02E8FE000000000000900100000002 0700000053796D626F6C0000F40A0A39E8EC1200B8A4F177C1A4F1772030F377100966CB040000 002D010400040000002D010300040000002D0104000500000009020000FF00040000002D010300 070000002105010031005E016400070000002105010033005E01F000040000002D010400070000 00210501003D005E01D001040000002D010300070000002105010031005E01BE02070000002105 010033005E014A0308000000FA0200000000000000000000040000002D01050004000000F00100 0007000000FC020000FFFFFF000000040000002D01000004000000F00101001C000000FB021000 070000000000BC02000000000102022253797374656D0000A50A0A21E8EC1200B8A4F177C1A4F1 772030F377100966CB040000002D010100040000002701FFFF04000000F001020004000000F001 030004000000F0010400040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f8\fs28\cf0 \par \plain\f5\fs28\cf0 Das Verfahren hat also funktioniert: Bob konnte seine Nachricht an Alice \par schicken, Alice konnte mit Hilfe ihres eigenen Geheimschl\'fcssels die \par Nachricht entschl\'fcsseln. \par \par Folgende Fragen sind nun offensichtlich: \par \par \tab (1) Warum sollte Eve das Geheimnis nicht entsch\'fcsseln k\'f6nnen, \par \tab wo sie doch N kennt? \par \par \tab (2) Warum ben\'f6tigen die letzten Rechnungen so viel Zeit? \par \par \tab (3) Kann man das Suchen von Primzahlen mit MuPAD nicht \par \tab noch geschickter machen? \par \par \plain\f5\fs28\cf0\b Zu Frage (1):\plain\f5\fs28\cf0 Eve k\'f6nnte bei Kenntnis von N versuchen, die Zahl in ihre Faktoren \par p und q zerlegen. Mit Hilfe von p und q k\'f6nnte Eve Phi(N) = (p-1) * (q-1) berechnen. \par Da sie auch e kennt (e wurde von Alice ver\'f6ffentlicht) k\'f6nnte sie genau wie Alice \par den Wert von d bestimmen (\'fcber den Euklidischen Algorithmus, wie wir es oben \par f\'fcr Alice getan haben). Wenn Eve d kennt, so kann Eve die Nachricht von Bob \par auch genauso leicht entschl\'fcsseln wie Alice. \par \par Wo k\'f6nnte es Probleme f\'fcr Eve geben? Eves gro\'dfes Problem ist es, N zu \par faktorieren, d.h. die Zahlen p und q zu finden. In der Realit\'e4t wird man N als \par Produkt zweier riesig gro\'dfer Primzahlen w\'e4hlen, so dass die Faktorisierung \par von N viel zu lange dauert. \par \par Man kann zeigen, dass alle anderen Operationen auch bei sehr gro\'dfem N \par immer noch schnell genug durchgef\'fchrt werden k\'f6nnen (z.B. der Euklidische \par Algorithmus zur Berechnung des modularen Inversen funktioniert auch bei \par gro\'dfen Zahlen sehr schnell). \par \plain\f8\fs28\cf0 \par \plain\f3\fs28\cf3\b \par \plain\f3\fs24\cf3\b leicht \tab Kanal leicht \par Bob ------\plain\lang2057\f3\fs24\cf3\b ->\plain\f3\fs24\cf3\b Verschl\'fcsselung ------\plain\lang2057\f3\fs24\cf3\b -> \plain\f3\fs24\cf3\b Entschl\'fcsselung ----\plain\lang2057\f3\fs24\cf3\b --->\plain\f3\fs24\cf3\b Alice \par \plain\lang1038\f6\fs24\cf3\b \tab \tab \tab \tab \tab \tab | \par \tab \tab \tab \tab \tab \tab | extrem \par \tab \tab \tab \tab \tab | schwer \par \tab \tab \tab \tab \tab \tab | \par \tab \tab \tab \tab \tab Eve \par \plain\f8\fs28\cf0 \par \par \plain\f5\fs28\cf0 Ein Beispiel: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}NN:= 112589990654654760673 * 112589990654654760791; \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf4 \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw10478\pich901\picwgoal5940\pichgoal510 0100090000032F02000005001C0000000000050000000B0200000000050000000C028503EE2803 0000001E00030000001E00050000000C02FF013417050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090ACCE8EC1200B8A4F177C1A4F1772030F377F40A663B040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A663B040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010032005E01F000070000002105010036005E017C0107000000210501 0037005E010802070000002105010036005E019402070000002105010035005E01200307000000 2105010030005E01AC03070000002105010035005E013804070000002105010039005E01C40407 0000002105010039005E015005070000002105010035005E01DC05070000002105010036005E01 6806070000002105010031005E01F406070000002105010035005E018007070000002105010032 005E010C08070000002105010034005E019808070000002105010036005E012409070000002105 010033005E01B009070000002105010035005E013C0A070000002105010037005E01C80A070000 002105010031005E01540B070000002105010030005E01E00B070000002105010039005E016C0C 070000002105010034005E01F80C070000002105010030005E01840D070000002105010031005E 01100E070000002105010031005E019C0E070000002105010030005E01280F0700000021050100 39005E01B40F070000002105010030005E014010070000002105010037005E01CC100700000021 05010032005E015811070000002105010031005E01E411070000002105010036005E0170120700 00002105010039005E01FC12070000002105010031005E018813070000002105010037005E0114 14070000002105010032005E01A014070000002105010033005E012C1507000000210501003400 5E01B815070000002105010033005E01441608000000FA0200000000000000000000040000002D 01040004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F001 01001C000000FB021000070000000000BC02000000000102022253797374656D0000BD090A31E8 EC1200B8A4F177C1A4F1772030F377F40A663B040000002D010100040000002701FFFF04000000 F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 Die Zahl N kann man in MuPAD mit dem Befehl \plain\f5\fs28\cf4 factor \plain\f5\fs28\cf0 in ihre Faktoren zerlegen: \par Wir kennen das Ergebnis bereits, denn oben stehen die beiden Primfaktoren von \par N. Wie lange ben\'f6tigt MuPAD nun ungef\'e4hr f\'fcr die Faktorisierung? Wir testen dies... \par \par (man kann die Faktorisierung per Mausklick auf das Abbruchsymbol - roter Kreis \par mit wei\'dfem Kreuz in der obigen Befehlsleiste - vorzeitig abbrechen) \par \plain\f3\fs32\cf4 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}time( factor(NN) ) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1588\pich901\picwgoal900\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503340603 0000001E00030000001E00050000000C02FF018403050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A3CE8EC1200B8A4F177C1A4F1772030F377DC0A6691040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A6691040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003200 5E016400070000002105010032005E01F000070000002105010039005E017C0107000000210501 0033005E010802070000002105010037005E01940208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000BD09 0A32E8EC1200B8A4F177C1A4F1772030F377DC0A6691040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}time(igcdex(NN, 112589990654654760673)) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw600\pich901\picwgoal340\pichgoal510 0100090000031701000005001C0000000000050000000B0200000000050000000C028503580203 0000001E00030000001E00050000000C02FF015401050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000DC0A0A92E8EC1200B8A4F177C1A4F1772030F377100966CF040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966CF040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003000 5E01640008000000FA0200000000000000000000040000002D01040004000000F0010000070000 00FC020000FFFFFF000000040000002D01000004000000F00101001C000000FB02100007000000 0000BC02000000000102022253797374656D0000BD090A33E8EC1200B8A4F177C1A4F1772030F3 77100966CF040000002D010100040000002701FFFF04000000F001020004000000F00103000400 00002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f5\fs28\cf0 \par Wie man sieht: Die Berechnung des Euklidischen Algorithmus geht schnell, \par die Faktorisierung dagegen nicht. \par \par \plain\f5\fs28\cf0\b Fazit:\plain\f5\fs28\cf0 Wenn Eve p und q nicht kennt, so hat sie f\'fcr gro\'dfe N keine Chance, die \par Werte von p und q in angemessener Zeit zu berechnen. Dies zeigt die Sicherheit \par des Verfahrens f\'fcr hinreichend gro\'dfe Werte von p, q und N. \par \plain\f8\fs28\cf0 \par \par \plain\f5\fs28\cf0\b Zu Frage (2): \plain\f5\fs28\cf0 Das Potenzieren x^d ist nicht kosteng\'fcnstig und ungeschickt, \par weil erst potenziert und danach erst modulo N gerechnet wird. \par \par Besser ist es, nach jeder berechneten Potenz zun\'e4chst wieder modulo N \par zu reduzieren, da dann die Zahlen viel kleiner sind. Wie wir unten sehen, \par dauern die Berechnungen von oben, die mehrere Sekunden in Anspruch \par genommen hatten, nur noch Sekundenbruchteile: \par \plain\f3\fs22\cf5 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}xx:= powermod(y, d, N) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw847\pich901\picwgoal480\pichgoal510 0100090000031E01000005001C0000000000050000000B0200000000050000000C0285034F0303 0000001E00030000001E00050000000C02FF01E001050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AD0E8EC1200B8A4F177C1A4F1772030F377F40A663F040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A663F040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010033005E01F00008000000FA0200000000000000000000040000002D 01040004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F001 01001C000000FB021000070000000000BC02000000000102022253797374656D0000BD090A34E8 EC1200B8A4F177C1A4F1772030F377F40A663F040000002D010100040000002701FFFF04000000 F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f4\fs28\cf0 \par Dabei berechnet \plain\f4\fs28\cf4 powermod(y, d, N)\plain\f4\fs28\cf0 nichts anderes als y^d modulo N. \par Diesmal allerdings auf die etwas geschicktere, oben angedeutete Weise. \par \plain\f3\fs28\cf0\b \par \plain\f4\fs28\cf0 Auch das modulare Inverse l\'e4\'dft sich leichter berechnen. Wir wissen, \par dass d das modulare Inverse zu e modulo Phi(N) ist. Mit MuPAD k\'f6nnen \par wir dies auch unter Verzicht auf die Funktion igcd \par direkt berechnen: \par \plain\f3\fs28\cf0\b \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}d:= e^-1 mod Phi_N \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1588\pich901\picwgoal900\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503340603 0000001E00030000001E00050000000C02FF018403050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A40E8EC1200B8A4F177C1A4F1772030F377DC0A6695040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A6695040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003600 5E016400070000002105010030005E01F000070000002105010032005E017C0107000000210501 0032005E010802070000002105010037005E01940208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000BD09 0A35E8EC1200B8A4F177C1A4F1772030F377DC0A6695040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f4\fs28\cf0 \par Die Probe zeigt auch dieses Mail wie oben, dass das Ergebnis korrekt ist: \par \plain\f3\fs28\cf0\b \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}d * e mod Phi_N \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw600\pich901\picwgoal340\pichgoal510 0100090000031701000005001C0000000000050000000B0200000000050000000C028503580203 0000001E00030000001E00050000000C02FF015401050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000DC0A0A96E8EC1200B8A4F177C1A4F1772030F377100966D3040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966D3040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E01640008000000FA0200000000000000000000040000002D01040004000000F0010000070000 00FC020000FFFFFF000000040000002D01000004000000F00101001C000000FB02100007000000 0000BC02000000000102022253797374656D0000BD090A36E8EC1200B8A4F177C1A4F1772030F3 77100966D3040000002D010100040000002701FFFF04000000F001020004000000F00103000400 00002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f3\fs28\cf0\b \par \plain\f4\fs28\cf0\b Zu Frage (3):\plain\f4\fs28\cf0 Das Finden von Primzahlen kann mit Hilfe der Funktion \par \plain\f4\fs28\cf4 nextprime\plain\f4\fs28\cf0 verbessert werden. Diese Funktion liefert zu einer gegebenen \par Zahl die n\'e4chst gr\'f6\'dfere Primzahl. Damit ist das Auffinden einer \par zuf\'e4lligen Primzahl aus der Menge \{1,2,...,999,1000\} ganz einfach: \par \par Zuerst w\'e4hlen wir eine Zufallszahl a \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}a:= Zufall() \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1588\pich901\picwgoal900\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503340603 0000001E00030000001E00050000000C02FF018403050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AD4E8EC1200B8A4F177C1A4F1772030F377F40A6643040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A6643040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003300 5E016400070000002105010035005E01F000070000002105010030005E017C0107000000210501 0032005E010802070000002105010037005E01940208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000BD09 0A37E8EC1200B8A4F177C1A4F1772030F377F40A6643040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f4\fs28\cf0 \par Dann setzen wir p auf den Wert \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}pp:= nextprime(a) \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1588\pich901\picwgoal900\pichgoal510 0100090000033301000005001C0000000000050000000B0200000000050000000C028503340603 0000001E00030000001E00050000000C02FF018403050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A44E8EC1200B8A4F177C1A4F1772030F377DC0A6699040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A6699040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003300 5E016400070000002105010035005E01F000070000002105010030005E017C0107000000210501 0032005E010802070000002105010037005E01940208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D0000BD09 0A38E8EC1200B8A4F177C1A4F1772030F377DC0A6699040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect \par \pard\ri4\plain\f4\fs28\cf0 \par Dann ist pp sicherlich eine Primzahl und wir sind fertig. \par \par In der Praxis, wo man mit riesig gro\'dfen Zahlen rechnet, wird man aber \par dennoch nicht \plain\f4\fs28\cf4 nextprime\plain\f4\fs28\cf0 benutzen, sondern eher, wie oben, Zufalls- \par zahlen erzeugen und testen, ob diese Primzahlen sind. Dieses Verfahren \par ist, so unglaublich es klingen mag, schneller. \par \plain\f3\fs28\cf0\b \par \par \plain\f4\fs28\cf0\b Eine weitere Anwendung: \plain\f5\fs28\cf0 Nat\'fcrlich m\'f6chten Alice und Bob nicht nur \par Zahlen aneinander verschicken. Man kann z.B. folgende Vereinbarung treffen: \par \par - Die Buchstaben des Alphabets werden mit 1 bis 26 durchnumeriert. \par - W\'f6rter werden durch 27 getrennt oder separat verschickt. \par \par Eine Codierung des Worter "Hallo" w\'e4re also gegeben durch \par \par \tab \tab \tab \tab \tab 8 01 12 12 15 \par \par Stellen wir uns vor, wir w\'e4ren Alice und Bob h\'e4tte uns die folgende \par Nachricht geschickt: \par \par {\pict\wmetafile8\picw1714\pich837\picscalex99\picscaley99\picwgoal977\pichgoal476 0100090000035603000005001C0000000000050000000B0200000000050000000C024503B20603 0000001E00050000000C024903BC06050000000B0200000000030000001E00050000000C025003 C506050000000B0200000000050000000B0200000000030000001E00050000000C025303D00605 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025A03D806050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C025E03E306050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C026503EC06050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C026803F706050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C0270030007050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C0273030B0705000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C027A031507050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027E031F07050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C0285032A07050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00030000001E00050000000C02FF011004050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000 0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000 00417269616C000000DC0A0A9AE8EC1200B8A4F177C1A4F1772030F377100966D7040000002D01 010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966D7040000002D0102000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010034005E01F000070000002105010033005E017C0107000000210501 0037005E010802070000002105010032005E019402070000002105010033005E01200308000000 FA0200000000000000000000040000002D0103001C000000FB021000070000000000BC02000000 000102022253797374656D0000BD090A39E8EC1200B8A4F177C1A4F1772030F377100966D70400 00002D010400040000002701FFFF04000000F001000004000000F001010004000000F001020004 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 {\pict\wmetafile8\picw1484\pich837\picscalex99\picscaley99\picwgoal846\pichgoal476 0100090000034F03000005001C0000000000050000000B0200000000050000000C024503CC0503 0000001E00050000000C024903D505050000000B0200000000030000001E00050000000C025003 DC05050000000B0200000000050000000B0200000000030000001E00050000000C025303E70505 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025A03EE05050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C025E03F905050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C0265030006050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C0268030A06050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C0270031106050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C0273031C0605000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C027A032306050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027E032E06050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C0285033406050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00030000001E00050000000C02FF018403050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000 0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000 00417269616C00000010090AD8E8EC1200B8A4F177C1A4F1772030F377BD09663B040000002D01 010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377BD09663B040000002D0102000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003200 5E016400070000002105010038005E01F000070000002105010030005E017C0107000000210501 0035005E010802070000002105010037005E01940208000000FA02000000000000000000000400 00002D0103001C000000FB021000070000000000BC02000000000102022253797374656D0000DC 0A0A9BE8EC1200B8A4F177C1A4F1772030F377BD09663B040000002D010400040000002701FFFF 04000000F001000004000000F001010004000000F0010200040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701 FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400000027 01FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 {\pict\wmetafile8\picw1714\pich837\picscalex99\picscaley99\picwgoal977\pichgoal476 0100090000035603000005001C0000000000050000000B0200000000050000000C024503B20603 0000001E00050000000C024903BC06050000000B0200000000030000001E00050000000C025003 C506050000000B0200000000050000000B0200000000030000001E00050000000C025303D00605 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025A03D806050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C025E03E306050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C026503EC06050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C026803F706050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C0270030007050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C0273030B0705000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C027A031507050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027E031F07050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C0285032A07050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00030000001E00050000000C02FF011004050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000 0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000 00417269616C000000BD090A3CE8EC1200B8A4F177C1A4F1772030F377DC0A669D040000002D01 010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A669D040000002D0102000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010036005E01F000070000002105010035005E017C0107000000210501 0038005E010802070000002105010037005E019402070000002105010039005E01200308000000 FA0200000000000000000000040000002D0103001C000000FB021000070000000000BC02000000 000102022253797374656D000010090AD9E8EC1200B8A4F177C1A4F1772030F377DC0A669D0400 00002D010400040000002701FFFF04000000F001000004000000F001010004000000F001020004 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 {\pict\wmetafile8\picw1484\pich837\picscalex99\picscaley99\picwgoal846\pichgoal476 0100090000034F03000005001C0000000000050000000B0200000000050000000C024503CC0503 0000001E00050000000C024903D505050000000B0200000000030000001E00050000000C025003 DC05050000000B0200000000050000000B0200000000030000001E00050000000C025303E70505 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025A03EE05050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C025E03F905050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C0265030006050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C0268030A06050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C0270031106050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C0273031C0605000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C027A032306050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027E032E06050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C0285033406050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00030000001E00050000000C02FF018403050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000 0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000 00417269616C000000DC0A0A9EE8EC1200B8A4F177C1A4F1772030F377100966DB040000002D01 010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966DB040000002D0102000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003300 5E016400070000002105010034005E01F000070000002105010039005E017C0107000000210501 0037005E010802070000002105010038005E01940208000000FA02000000000000000000000400 00002D0103001C000000FB021000070000000000BC02000000000102022253797374656D0000BD 090A3DE8EC1200B8A4F177C1A4F1772030F377100966DB040000002D010400040000002701FFFF 04000000F001000004000000F001010004000000F0010200040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701 FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400000027 01FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 {\pict\wmetafile8\picw1714\pich837\picscalex99\picscaley99\picwgoal977\pichgoal476 0100090000035603000005001C0000000000050000000B0200000000050000000C024503B20603 0000001E00050000000C024903BC06050000000B0200000000030000001E00050000000C025003 C506050000000B0200000000050000000B0200000000030000001E00050000000C025303D00605 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025A03D806050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C025E03E306050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C026503EC06050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C026803F706050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C0270030007050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C0273030B0705000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C027A031507050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027E031F07050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C0285032A07050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00030000001E00050000000C02FF011004050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000 0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000 00417269616C00000010090ADCE8EC1200B8A4F177C1A4F1772030F377BD09663F040000002D01 010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377BD09663F040000002D0102000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010036005E01F000070000002105010039005E017C0107000000210501 0033005E010802070000002105010036005E019402070000002105010033005E01200308000000 FA0200000000000000000000040000002D0103001C000000FB021000070000000000BC02000000 000102022253797374656D0000DC0A0A9FE8EC1200B8A4F177C1A4F1772030F377BD09663F0400 00002D010400040000002701FFFF04000000F001000004000000F001010004000000F001020004 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 {\pict\wmetafile8\picw1714\pich837\picscalex99\picscaley99\picwgoal977\pichgoal476 0100090000035603000005001C0000000000050000000B0200000000050000000C024503B20603 0000001E00050000000C024903BC06050000000B0200000000030000001E00050000000C025003 C506050000000B0200000000050000000B0200000000030000001E00050000000C025303D00605 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025A03D806050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C025E03E306050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C026503EC06050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C026803F706050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C0270030007050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C0273030B0705000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C027A031507050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027E031F07050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C0285032A07050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00030000001E00050000000C02FF011004050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000 0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000 00417269616C000000BD090A40E8EC1200B8A4F177C1A4F1772030F377DC0A66A1040000002D01 010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A66A1040000002D0102000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010035005E01F000070000002105010032005E017C0107000000210501 0035005E010802070000002105010037005E019402070000002105010036005E01200308000000 FA0200000000000000000000040000002D0103001C000000FB021000070000000000BC02000000 000102022253797374656D000010090ADDE8EC1200B8A4F177C1A4F1772030F377DC0A66A10400 00002D010400040000002701FFFF04000000F001000004000000F001010004000000F001020004 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 {\pict\wmetafile8\picw1484\pich837\picscalex99\picscaley99\picwgoal846\pichgoal476 0100090000034F03000005001C0000000000050000000B0200000000050000000C024503CC0503 0000001E00050000000C024903D505050000000B0200000000030000001E00050000000C025003 DC05050000000B0200000000050000000B0200000000030000001E00050000000C025303E70505 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025A03EE05050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C025E03F905050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C0265030006050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C0268030A06050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C0270031106050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C0273031C0605000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C027A032306050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027E032E06050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C0285033406050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00030000001E00050000000C02FF018403050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000 0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000 00417269616C000000DC0A0AA2E8EC1200B8A4F177C1A4F1772030F377100966DF040000002D01 010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966DF040000002D0102000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003200 5E016400070000002105010032005E01F000070000002105010033005E017C0107000000210501 0035005E010802070000002105010030005E01940208000000FA02000000000000000000000400 00002D0103001C000000FB021000070000000000BC02000000000102022253797374656D0000BD 090A41E8EC1200B8A4F177C1A4F1772030F377100966DF040000002D010400040000002701FFFF 04000000F001000004000000F001010004000000F0010200040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701 FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400000027 01FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 {\pict\wmetafile8\picw1714\pich837\picscalex99\picscaley99\picwgoal977\pichgoal476 0100090000035603000005001C0000000000050000000B0200000000050000000C024503B20603 0000001E00050000000C024903BC06050000000B0200000000030000001E00050000000C025003 C506050000000B0200000000050000000B0200000000030000001E00050000000C025303D00605 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025A03D806050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C025E03E306050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C026503EC06050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C026803F706050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C0270030007050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C0273030B0705000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C027A031507050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027E031F07050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C0285032A07050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00030000001E00050000000C02FF011004050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000 0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000 00417269616C00000010090AE0E8EC1200B8A4F177C1A4F1772030F377BD096643040000002D01 010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377BD096643040000002D0102000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010036005E01F000070000002105010039005E017C0107000000210501 0033005E010802070000002105010036005E019402070000002105010033005E01200308000000 FA0200000000000000000000040000002D0103001C000000FB021000070000000000BC02000000 000102022253797374656D0000DC0A0AA3E8EC1200B8A4F177C1A4F1772030F377BD0966430400 00002D010400040000002701FFFF04000000F001000004000000F001010004000000F001020004 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 {\pict\wmetafile8\picw1714\pich837\picscalex99\picscaley99\picwgoal977\pichgoal476 0100090000035603000005001C0000000000050000000B0200000000050000000C024503B20603 0000001E00050000000C024903BC06050000000B0200000000030000001E00050000000C025003 C506050000000B0200000000050000000B0200000000030000001E00050000000C025303D00605 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025A03D806050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C025E03E306050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C026503EC06050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C026803F706050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C0270030007050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C0273030B0705000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00050000000C027A031507050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027E031F07050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000030000001E00050000000C0285032A07050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000 1E00030000001E00050000000C02FF011004050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000 0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000 00417269616C000000BD090A44E8EC1200B8A4F177C1A4F1772030F377DC0A66A5040000002D01 010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A66A5040000002D0102000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010036005E01F000070000002105010034005E017C0107000000210501 0038005E010802070000002105010035005E019402070000002105010030005E01200308000000 FA0200000000000000000000040000002D0103001C000000FB021000070000000000BC02000000 000102022253797374656D000010090AE1E8EC1200B8A4F177C1A4F1772030F377DC0A66A50400 00002D010400040000002701FFFF04000000F001000004000000F001010004000000F001020004 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 \par \par Unser privater Schl\'fcssel ist: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}d:=155731; \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf4 p:=271; q:=977; \par N:=p*q; \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1834\pich901\picwgoal1039\pichgoal510 0100090000033A01000005001C0000000000050000000B0200000000050000000C0285032A0703 0000001E00030000001E00050000000C02FF011004050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000DC0A0AA6E8EC1200B8A4F177C1A4F1772030F377100966E3040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966E3040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010035005E01F000070000002105010035005E017C0107000000210501 0037005E010802070000002105010033005E019402070000002105010031005E01200308000000 FA0200000000000000000000040000002D01040004000000F001000007000000FC020000FFFFFF 000000040000002D01000004000000F00101001C000000FB021000070000000000BC0200000000 0102022253797374656D0000BD090A45E8EC1200B8A4F177C1A4F1772030F377100966E3040000 002D010100040000002701FFFF04000000F001020004000000F0010300040000002701FFFF0300 00000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw1094\pich901\picwgoal620\pichgoal510 0100090000032501000005001C0000000000050000000B0200000000050000000C028503460403 0000001E00030000001E00050000000C02FF016C02050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AE4E8EC1200B8A4F177C1A4F1772030F377F40A6650040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A6650040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003200 5E016400070000002105010037005E01F000070000002105010031005E017C0108000000FA0200 000000000000000000040000002D01040004000000F001000007000000FC020000FFFFFF000000 040000002D01000004000000F00101001C000000FB021000070000000000BC0200000000010202 2253797374656D0000BD090A46E8EC1200B8A4F177C1A4F1772030F377F40A6650040000002D01 0100040000002701FFFF04000000F001020004000000F0010300040000002701FFFF0300000000 00 }\plain\f3\fs28\cf5\protect \par {\pict\wmetafile8\picw1094\pich901\picwgoal620\pichgoal510 0100090000032501000005001C0000000000050000000B0200000000050000000C028503460403 0000001E00030000001E00050000000C02FF016C02050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A51E8EC1200B8A4F177C1A4F1772030F377DC0A66A9040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A66A9040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003900 5E016400070000002105010037005E01F000070000002105010037005E017C0108000000FA0200 000000000000000000040000002D01040004000000F001000007000000FC020000FFFFFF000000 040000002D01000004000000F00101001C000000FB021000070000000000BC0200000000010202 2253797374656D0000BD090A47E8EC1200B8A4F177C1A4F1772030F377DC0A66A9040000002D01 0100040000002701FFFF04000000F001020004000000F0010300040000002701FFFF0300000000 00 }\plain\f3\fs28\cf5\protect \par {\pict\wmetafile8\picw1834\pich901\picwgoal1039\pichgoal510 0100090000033A01000005001C0000000000050000000B0200000000050000000C0285032A0703 0000001E00030000001E00050000000C02FF011004050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000DC0A0AAAE8EC1200B8A4F177C1A4F1772030F377100966E7040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966E7040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003200 5E016400070000002105010036005E01F000070000002105010034005E017C0107000000210501 0037005E010802070000002105010036005E019402070000002105010037005E01200308000000 FA0200000000000000000000040000002D01040004000000F001000007000000FC020000FFFFFF 000000040000002D01000004000000F00101001C000000FB021000070000000000BC0200000000 0102022253797374656D0000BD090A48E8EC1200B8A4F177C1A4F1772030F377100966E7040000 002D010100040000002701FFFF04000000F001020004000000F0010300040000002701FFFF0300 00000000 }\plain\f3\fs28\cf5\protect \par \par \pard\ri4\plain\f5\fs28\cf0 Wir entsch\'fcsseln die Nachricht sukzessiv wie oben: \plain\f3\fs28\cf0\b \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf4 {\pntext\f1\'b7\tab}x1:= powermod(143723, d, N); \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf4 x2:= powermod(28057, d, N); \par x3:= powermod(165879, d, N); \par x4:= powermod(34978, d, N); \par x5:= powermod(169363, d, N); \par x6:= powermod(152576, d, N); \par x7:= powermod(22350, d, N); \par x8:= powermod(169363, d, N); \par x9:= powermod(164850, d, N); \par \plain\f3\fs22\cf4 \par \pard\li50\ri6\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw847\pich901\picwgoal480\pichgoal510 0100090000031E01000005001C0000000000050000000B0200000000050000000C0285034F0303 0000001E00030000001E00050000000C02FF01E001050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AE8E8EC1200B8A4F177C1A4F1772030F377F40A6654040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A6654040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010033005E01F00008000000FA0200000000000000000000040000002D 01040004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F001 01001C000000FB021000070000000000BC02000000000102022253797374656D0000BD090A49E8 EC1200B8A4F177C1A4F1772030F377F40A6654040000002D010100040000002701FFFF04000000 F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par \pard\li50\ri2\plain\f3\fs28\cf5\protect {\pict\wmetafile8\picw847\pich901\picwgoal480\pichgoal510 0100090000031E01000005001C0000000000050000000B0200000000050000000C0285034F0303 0000001E00030000001E00050000000C02FF01E001050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A55E8EC1200B8A4F177C1A4F1772030F377DC0A66AD040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A66AD040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003200 5E016400070000002105010035005E01F00008000000FA0200000000000000000000040000002D 01040004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F001 01001C000000FB021000070000000000BC02000000000102022253797374656D0000BD090A4AE8 EC1200B8A4F177C1A4F1772030F377DC0A66AD040000002D010100040000002701FFFF04000000 F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par {\pict\wmetafile8\picw847\pich901\picwgoal480\pichgoal510 0100090000031E01000005001C0000000000050000000B0200000000050000000C0285034F0303 0000001E00030000001E00050000000C02FF01E001050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000DC0A0AAEE8EC1200B8A4F177C1A4F1772030F377100966EB040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377100966EB040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003200 5E016400070000002105010037005E01F00008000000FA0200000000000000000000040000002D 01040004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F001 01001C000000FB021000070000000000BC02000000000102022253797374656D0000BD090A4BE8 EC1200B8A4F177C1A4F1772030F377100966EB040000002D010100040000002701FFFF04000000 F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par {\pict\wmetafile8\picw847\pich901\picwgoal480\pichgoal510 0100090000031E01000005001C0000000000050000000B0200000000050000000C0285034F0303 0000001E00030000001E00050000000C02FF01E001050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000010090AECE8EC1200B8A4F177C1A4F1772030F377F40A6658040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377F40A6658040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003100 5E016400070000002105010039005E01F00008000000FA0200000000000000000000040000002D 01040004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F001 01001C000000FB021000070000000000BC02000000000102022253797374656D0000BD090A4CE8 EC1200B8A4F177C1A4F1772030F377F40A6658040000002D010100040000002701FFFF04000000 F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs28\cf5\protect \par {\pict\wmetafile8\picw600\pich901\picwgoal340\pichgoal510 0100090000031701000005001C0000000000050000000B0200000000050000000C028503580203 0000001E00030000001E00050000000C02FF015401050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C000000F40A0A59E8EC1200B8A4F177C1A4F1772030F377DC0A66B1040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB02E8FE0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377DC0A66B1040000002D0103000B0000 0026060F000C004D61746854797065000080000500000009020000FF0007000000210501003500 5E01640008000000FA0200000000000000000000040000002D01040004000000F0010000070000 00FC020000FFFFFF000000040000002D01000004000000F00101001C00000