\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\fswiss\fprq2 Helvetica;}} {\colortbl\red0\green0\blue0;\red255\green0\blue0;\red0\green0\blue255;\red255\green255\blue255;\red0\green128\blue0;} \deflang1031\pard\ri4\plain\f3\fs20\cf0\b ________________________________________________________________________________ \par \par \plain\f3\fs20\cf0 Inhalt....: Fiat-Shamir-Algorithmus \par Kategorie.: Arbeitsblatt \par Mathematik: Kryptographie, Zahlentheorie \par MuPAD.....: 3.0.0 \par Datum.....: 2003-06-23 \par Autoren...: Julia Faflek \par Funktionen: nextprime, random, powermod, igcd, is \par \plain\f3\fs20\cf0\b ________________________________________________________________________________ \par \plain\f4\fs36\cf0\b \par \plain\f4\fs40\cf0\b Das Fiat-Shamir-"Nullwissen"-Protokoll\plain\f4\fs36\cf0\b \par \plain\f4\fs22\cf0 \par \plain\f4\fs24\cf4 Wenn man jemanden davon \'fcberzeugen will, dass man ein Geheimnis kennt, dieses aber \par nicht preisgeben will, dann benutzt man Nullwissen-Protokolle. In diesem Notebook wird \par die Methode von Fiat und Shamir vorgestellt. \par \plain\f3\fs22\cf2 \par \par \plain\f4\fs28\cf0 Ein Nullwissen-Protokoll hat zwei bedeutende Eigenschaften. Erstens ist es \par interaktiv und besteht aus mehreren Runden und zweitens h\'e4ngt die Betrugs- \par wahrscheinlichkeit von der Anzahl der durchgef\'fchrten Runden ab. Je mehr \par Runden, desto kleiner ist die Wahrscheinlichkeit, betr\'fcgen zu k\'f6nnen. Die \par charakteristischste Eigenschaft ist jedoch die Nullwisseneigenschaft, d.h. \par man kann bei Beobachtung des Protokollverlaufs nicht unterscheiden, ob \par jemand das Geheimnis kennt oder nicht. \par \par Aber nun genaueres zu dem Fiat-Shamir-Verfahren, welches sich insbesondere \par zum Identit\'e4tsnachweis mittels Chipkarten eignet. Da der Algorithmus stark auf \par RSA beruht, m\'fcssen erst einmal Schl\'fcssel erzeugt werden. Dazu werden zwei \par gro\'dfe Primzahlen gew\'e4hlt und das Produkt dieser gebildet: \par \plain\f4\fs22\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}p := nextprime(2^512); \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf1 q := nextprime(p + 2^16); \par N := p*q\plain\f4\fs28\cf1 \par \pard\ri4\plain\f5\fs28\cf0 \par Nun wird eine beliebige zu \plain\f5\fs28\cf0\i N\plain\f5\fs28\cf0 teilerfremde Zahl \plain\f5\fs28\cf0\i s\plain\f5\fs28\cf0 zwischen 1 und \plain\f5\fs28\cf0\i N\plain\f5\fs28\cf0 gew\'e4hlt: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}s := random(1..N)(): \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf1 while (igcd(s, N) > 1) do \par s := random(1..N)() \par end_while: \par s \par \pard\ri4\plain\f4\fs28\cf0 \par W\'fcrden wir hier einen Teiler von \plain\f4\fs28\cf0\i N\plain\f4\fs28\cf0 finden, so h\'e4tten wir die Primfaktorzerle- \par gung von \plain\f4\fs28\cf0\i N\plain\f4\fs28\cf0 gefunden und k\'f6nnten das Protokoll brechen. Die Wahrschein- \par lichkeit daf\'fcr ist aber sehr gering. Die Zahl \plain\f4\fs28\cf0\i s\plain\f4\fs28\cf0 ist das Geheimnis. Jetzt wird \par eine Zahl \plain\f4\fs28\cf0\i v\plain\f4\fs28\cf0 berechnet, die als eine Art Ausweis fungiert und daher \'f6ffentlich \par ist. \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}v := powermod(s, 2, N) \par \pard\ri4\plain\f4\fs28\cf0 \par Kommen wir zu der Anwendung: Eine andere Person will jetzt \'fcberpr\'fcfen, \par ob wir das Geheimnis \plain\f4\fs28\cf0\i s\plain\f4\fs28\cf0 kennen. Wir werden jedoch nichts von \plain\f4\fs28\cf0\i s\plain\f4\fs28\cf0 preisgeben. \par Zun\'e4chst w\'e4hlen wir eine weitere zuf\'e4llige Zahl \plain\f4\fs28\cf0\i r\plain\f4\fs28\cf0 , teilerfremd zu \plain\f4\fs28\cf0\i N\plain\f4\fs28\cf0 , und be- \par stimmen eine Zahl \plain\f4\fs28\cf0\i x\plain\f4\fs28\cf0 , die wir an die andere Person schicken: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}r := random(1..N)(): \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf1 while (igcd(r, N) > 1 ) do \par r := random(1..N)() \par end_while: \par r; \par x := powermod(r, 2, N) \par \pard\ri4\plain\f5\fs28\cf0 \par Die andere Person w\'e4hlt ein Zufallsbit, also 0 oder 1. Dazu kann sie z.B. eine \par M\'fcnze werfen. Dieses Bit wird an uns geschickt. \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}b := random(0..1)() \par \pard\ri4\plain\f5\fs28\cf0 \par Nun berechnen wir folgendes:\plain\f4\fs28\cf0 \par \plain\f3\fs22\cf1 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}y := (r * powermod(s, b, N)) mod N \par \pard\ri4\plain\f4\fs28\cf0 \par Ist \plain\f4\fs28\cf0\i b\plain\f4\fs28\cf0 = 0, so folgt \plain\f4\fs28\cf0\i y\plain\f4\fs28\cf0 = \plain\f4\fs28\cf0\i r\plain\f4\fs28\cf0 mod \plain\f4\fs28\cf0\i N\plain\f4\fs28\cf0 . Wir schicken \plain\f4\fs28\cf0\i y\plain\f4\fs28\cf0 wieder zur\'fcck. Die andere \par Partei muss nachpr\'fcfen, ob \par \pard\li2500\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw5379\pich988\picscalex98\picscaley99\picwgoal3080\pichgoal565 010009000003F102000009001C0000000000050000000B0200000000050000000C02DC03031503 0000001E00050000000C02E5033A15050000000B0200000000030000001E00050000000C02E803 3C15050000000B0200000000050000000B0200000000030000001E00050000000C02F203721505 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C02FE03AC15050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C020904E515050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C020B04E715050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C024B026B0C050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C000000940C0AEE38E91200D89FF177E19FF1 772020F377180C6674040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C0000000D0B0A3F38E91200D89FF177E19FF1772020F377 180C6674040000002D0102000B00000026060F000C004D6174685479706500007F001C000000FB 02E8FE00000000000090010100000107000000417269616C000000A10A0A6138E91200D89FF177 E19FF1772020F377180C6674040000002D0103001C000000FB023AFF0000000000009001000000 0107000000417269616C000000650C0A2E38E91200D89FF177E19FF1772020F377180C66740400 00002D010400040000002D010300040000002D010200040000002D010300040000002D01020004 0000002D0103001C000000FB023AFF00000000000090010100000107000000417269616C000000 2E0C0A0338E91200D89FF177E19FF1772020F377180C6674040000002D0105001C000000FB02E8 FE0000000000009001000000020700000053796D626F6C0000060A0A2538E91200D89FF177E19F F1772020F377180C6674040000002D010600040000002D010300040000002D010200040000002D 010600040000002D010200040000002D01030007000000210501007901AC016400040000002D01 0400070000002105010032010A010001040000002D01020007000000210501006D01AC01B40107 000000210501006F01AC019D0207000000210501006401AC013903040000002D01030007000000 210501004E01AC011B04040000002D01060007000000210501003D01AC014205040000002D0103 0007000000210501007801AC013006040000002D0106000700000021050100D701AC01FF060400 00002D010200040000002D01030007000000210501007601AC017D07040000002D010500070000 0021050100620108011908040000002D01020007000000210501006D01AC01CD08070000002105 01006F01AC01B60907000000210501006401AC01520A040000002D01030007000000210501004E 01AC01340B08000000FA0200000000000000000000040000002D0107001C000000FB0210000700 00000000BC02000000000102022253797374656D00006D0C0A4B38E91200D89FF177E19FF17720 20F377180C6674040000002D010800040000002701FFFF04000000F001000004000000F0010100 04000000F001020004000000F001030004000000F001040004000000F001050004000000F00106 00040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701 FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f3\fs22\cf2 \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf1 {\pntext\f1\'b7\tab}Erg1 := powermod(y, 2, N): \par \pard\li600\ri1\fi-300\plain\f3\fs28\cf1 Erg2 := (x * powermod(v, b, N)) mod N: \par is (Erg1 - Erg2 = 0) \par \pard\ri4\plain\f4\fs28\cf0 \par Es stimmt also. Aber warum? Dazu m\'fcssen wir uns nur \'fcberlegen, wie \plain\f4\fs28\cf0\i y\plain\f4\fs28\cf0 , \plain\f4\fs28\cf0\i x\plain\f4\fs28\cf0 \par und \plain\f4\fs28\cf0\i v\plain\f4\fs28\cf0 erzeugt wurden: \par \pard\li2500\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw5859\pich992\picscalex98\picscaley99\picwgoal3356\pichgoal564 010009000003820300000A001C0000000000050000000B0200000000050000000C02E003E31603 0000001E00050000000C02E3032017050000000B0200000000030000001E00050000000C02ED03 5D17050000000B0200000000050000000B0200000000030000001E00050000000C02F8039A1705 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C020304DA17050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C020E041818050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C020F041A18050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C024D02AA0D050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C0000006D0C0A4E38E91200D89FF177E19FF1 772020F377060A6628040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C000000180C0A7638E91200D89FF177E19FF1772020F377 060A6628040000002D0102000B00000026060F000C004D6174685479706500007F001C000000FB 02E8FE00000000000090010100000107000000417269616C0000002E0C0A0538E91200D89FF177 E19FF1772020F377060A6628040000002D0103001C000000FB023AFF0000000000009001000000 0107000000417269616C000000650C0A2F38E91200D89FF177E19FF1772020F377060A66280400 00002D010400040000002D010300040000002D010200040000002D010300040000002D01020004 0000002D0103001C000000FB023AFF00000000000090010100000107000000417269616C000000 A10A0A6238E91200D89FF177E19FF1772020F377060A6628040000002D0105001C000000FB02E8 FE0000000000009001000000020700000053796D626F6C00000D0B0A4038E91200D89FF177E19F F1772020F377060A6628040000002D0106001C000000FB02E8FE00000000000090010000000207 0000005346204D617468204578740038E91200D89FF177E19FF1772020F377060A662804000000 2D010700040000002D010200040000002D010700040000002D010200040000002D010700040000 002D010400040000002D010300040000002D010200040000002D010600040000002D0102000400 00002D01030007000000210501007900AE016400040000002D010400070000002105010032000C 010001040000002D01020007000000210501006D00AE01B40107000000210501006F00AE019D02 07000000210501006400AE013903040000002D01030007000000210501004E00AE011B04040000 002D01060007000000210501003D00AE014205040000002D010200040000002D01070004000000 2D010200040000002D010700040000002D010200040000002D010700040000002D010200040000 002D010700040000002D010200040000002D0107000700000021050100A1006400300604000000 2D010600040000002D01030007000000210501007200AE01B006040000002D0106000700000021 050100D700AE016007040000002D010200040000002D01030007000000210501007300AE01DE07 040000002D010500070000002105010062000A016A08040000002D010700040000002D01020004 0000002D010700040000002D010200040000002D0107000700000021050100A2006400D8080400 00002D0104000700000021050100320008015809040000002D01020007000000210501006D00AE 010C0A07000000210501006F00AE01F50A07000000210501006400AE01910B040000002D010300 07000000210501004E00AE01730C08000000FA0200000000000000000000040000002D0108001C 000000FB021000070000000000BC02000000000102022253797374656D0000780C0AA838E91200 D89FF177E19FF1772020F377060A6628040000002D010900040000002701FFFF04000000F00100 0004000000F001010004000000F001020004000000F001030004000000F001040004000000F001 050004000000F001060004000000F0010700040000002701FFFF040000002701FFFF0400000027 01FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF03000000 0000 }\plain\f3\fs22\cf2 \par \pard\li2000\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw6963\pich992\picscalex98\picscaley99\picwgoal3987\pichgoal564 010009000003F90300000B001C0000000000050000000B0200000000050000000C02E003331B03 0000001E00050000000C02E3037A1B050000000B0200000000030000001E00050000000C02ED03 7C1B050000000B0200000000050000000B0200000000030000001E00050000000C02F803C31B05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C0203040D1C050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C020E04561C050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C020F04571C050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C024D021110050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C000000060A0A2938E91200D89FF177E19FF1 772020F377780C66AA040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C000000940C0AF038E91200D89FF177E19FF1772020F377 780C66AA040000002D0102000B00000026060F000C004D6174685479706500007F001C000000FB 02E8FE00000000000090010100000107000000417269616C0000000D0B0A4138E91200D89FF177 E19FF1772020F377780C66AA040000002D010300040000002D010200040000002D0103001C0000 00FB023AFF00000000000090010100000107000000417269616C000000A10A0A6338E91200D89F F177E19FF1772020F377780C66AA040000002D0104001C000000FB02E8FE000000000000900100 0000020700000053796D626F6C0000650C0A3038E91200D89FF177E19FF1772020F377780C66AA 040000002D0105001C000000FB02E8FE000000000000900100000002070000005346204D617468 204578740038E91200D89FF177E19FF1772020F377780C66AA040000002D010600040000002D01 0200040000002D010600040000002D010200040000002D0106001C000000FB023AFF0000000000 0090010000000107000000417269616C000000180C0A7738E91200D89FF177E19FF1772020F377 780C66AA040000002D010700040000002D010300040000002D010200040000002D010300040000 002D010700040000002D010200040000002D010300040000002D010700040000002D0104001C00 0000FB023AFF0000000000009001000000020700000053796D626F6C00006D0C0A4F38E91200D8 9FF177E19FF1772020F377780C66AA040000002D010800040000002D010500040000002D010300 040000002D010200040000002D010500040000002D010200040000002D010600040000002D0102 00040000002D010600040000002D010200040000002D010600040000002D010200040000002D01 0600040000002D010200040000002D0106000700000021050100A10264006400040000002D0105 00040000002D01030007000000210501007202AE01E400040000002D0105000700000021050100 D702AE019401040000002D010200040000002D01030007000000210501007302AE011202040000 002D010400070000002105010062020A019E02040000002D010600040000002D01020004000000 2D010600040000002D010200040000002D0106000700000021050100A20264000C03040000002D 0107000700000021050100320208018C03040000002D01020007000000210501006D02AE014004 07000000210501006F02AE01290507000000210501006402AE01C505040000002D010300070000 00210501004E02AE01A706040000002D01050007000000210501003D02AE01CE07040000002D01 0200040000002D01030007000000210501007202AE01BC08040000002D01070007000000210501 0032020C013409040000002D0105000700000021050100D702AE01DA09040000002D0102000400 00002D01030007000000210501007302AE01580A040000002D010800040000002D010700070000 002105010032020A01E40A040000002D0108000700000021050100D7020A016F0B040000002D01 0400070000002105010062020A01BF0B040000002D01020007000000210501006D02AE01730C07 000000210501006F02AE015C0D07000000210501006402AE01F80D040000002D01030007000000 210501004E02AE01DA0E08000000FA0200000000000000000000040000002D0109001C000000FB 021000070000000000BC02000000000102022253797374656D0000B30B0A3038E91200D89FF177 E19FF1772020F377780C66AA040000002D010A00040000002701FFFF04000000F0010000040000 00F001010004000000F001020004000000F001030004000000F001040004000000F00105000400 0000F001060004000000F001070004000000F0010800040000002701FFFF040000002701FFFF04 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 030000000000 }\plain\f3\fs22\cf2 \par \pard\li2500\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw6201\pich988\picscalex98\picscaley99\picwgoal3551\pichgoal565 0100090000034103000009001C0000000000050000000B0200000000050000000C02DC03391803 0000001E00050000000C02E5037818050000000B0200000000030000001E00050000000C02E803 B918050000000B0200000000050000000B0200000000030000001E00050000000C02F203F91805 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C02FE033C19050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C0209047E19050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C020B048019050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C024B02750E050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C000000780C0AAB38E91200D89FF177E19FF1 772020F377B30B6632040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C0000006D0C0A5038E91200D89FF177E19FF1772020F377 B30B6632040000002D0102000B00000026060F000C004D6174685479706500007F001C000000FB 02E8FE00000000000090010100000107000000417269616C000000180C0A7838E91200D89FF177 E19FF1772020F377B30B6632040000002D0103001C000000FB023AFF0000000000009001000000 0107000000417269616C0000002E0C0A0738E91200D89FF177E19FF1772020F377B30B66320400 00002D010400040000002D010200040000002D0103001C000000FB023AFF000000000000900101 00000107000000417269616C000000650C0A3138E91200D89FF177E19FF1772020F377B30B6632 040000002D0105001C000000FB02E8FE0000000000009001000000020700000053796D626F6C00 00A10A0A6438E91200D89FF177E19FF1772020F377B30B6632040000002D010600040000002D01 0300040000002D010200040000002D010300040000002D010400040000002D010200040000002D 010300040000002D010500040000002D010600040000002D010300040000002D01020004000000 2D010600040000002D010200040000002D010600040000002D010200040000002D010300070000 00210501007201AC016400040000002D010400070000002105010032010A01DC00040000002D01 06000700000021050100D701AC018201040000002D010200040000002D01030007000000210501 007601AC010002040000002D0105000700000021050100620108019C02040000002D0102000700 0000210501006D01AC01500307000000210501006F01AC01390407000000210501006401AC01D5 04040000002D01030007000000210501004E01AC01B705040000002D0106000700000021050100 3D01AC01DE06040000002D010200040000002D01030007000000210501007801AC01CC07040000 002D010400070000002105010032010A016308040000002D0106000700000021050100D701AC01 0909040000002D010200040000002D01030007000000210501007601AC018709040000002D0105 00070000002105010062010801230A040000002D01020007000000210501006D01AC01D70A0700 0000210501006F01AC01C00B07000000210501006401AC015C0C040000002D0103000700000021 0501004E01AC013E0D08000000FA0200000000000000000000040000002D0107001C000000FB02 1000070000000000BC02000000000102022253797374656D00000D0B0A4238E91200D89FF177E1 9FF1772020F377B30B6632040000002D010800040000002701FFFF04000000F001000004000000 F001010004000000F001020004000000F001030004000000F001040004000000F0010500040000 00F0010600040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400 00002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 \par \pard\ri4\plain\f5\fs28\cf0 Stellen wir uns nun vor, jemand wollte betr\'fcgen und der anderen Person weis- \par machen, dass er unser Geheimnis kennt. Wie soll dieser Betr\'fcger vorgehen? \par Es gibt zwei M\'f6glichkeiten: \par \par 1) Wenn ihm das Bit 0 zu geschickt wird, hat er keine Probleme das korrekte \plain\f5\fs28\cf0\i y\plain\f5\fs28\cf0 \par \plain\f5\fs28\cf3 ss\plain\f5\fs28\cf0 zur\'fcck zu schicken, da es sich in diesem Fall ja lediglich um das von ihm \par \plain\f5\fs28\cf3 ss\plain\f5\fs28\cf0 selbstgew\'e4hlte \plain\f5\fs28\cf0\i r\plain\f5\fs28\cf0 handelt. \par \par 2) Ihm wird das Bit 1 zu geschickt. Dann muss er \plain\f5\fs28\cf0\i rs\plain\f5\fs28\cf0 modulo \plain\f5\fs28\cf0\i N\plain\f5\fs28\cf0 abschicken. \par \plain\f5\fs28\cf3 ss\plain\f5\fs28\cf0 Dies ist nicht so einfach m\'f6glich. Denn \par \pard\li2500\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw5060\pich976\picscalex98\picscaley98\picwgoal2898\pichgoal559 010009000003C203000009001C0000000000050000000B0200000000050000000C02D003C41303 0000001E00050000000C02DB03F813050000000B0200000000030000001E00050000000C02E603 2E14050000000B0200000000050000000B0200000000030000001E00050000000C02F103631405 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C02FC039A14050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C020704D014050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C020804D114050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C024902CD0B050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C000000B30B0A3338E91200D89FF177E19FF1 772020F3770D0B6644040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C000000A10A0A6538E91200D89FF177E19FF1772020F377 0D0B6644040000002D0102000B00000026060F000C004D6174685479706500007F001C000000FB 02E8FE00000000000090010100000107000000417269616C000000650C0A3238E91200D89FF177 E19FF1772020F3770D0B6644040000002D0103001C000000FB02E8FE0000000000009001000000 020700000053796D626F6C00002E0C0A0838E91200D89FF177E19FF1772020F3770D0B66440400 00002D0104001C000000FB02E8FE000000000000900100000002070000005346204D6174682045 78740038E91200D89FF177E19FF1772020F3770D0B6644040000002D010500040000002D010200 040000002D010500040000002D0102001C000000FB023AFF000000000000900100000001070000 00417269616C0000006D0C0A5138E91200D89FF177E19FF1772020F3770D0B6644040000002D01 0600040000002D010200040000002D010300040000002D010600040000002D010200040000002D 010300040000002D010600040000002D010400040000002D010500040000002D01020004000000 2D010500040000002D010200040000002D010500040000002D010300040000002D010400040000 002D010200040000002D010500040000002D010200040000002D010500040000002D0102000400 00002D010500040000002D010200040000002D010500040000002D010200040000002D01050004 0000002D010200040000002D010500040000002D010200040000002D0105000700000021050100 2801AA016400040000002D010200040000002D010500040000002D010200040000002D01050004 0000002D010200040000002D010500040000002D010200040000002D010500040000002D010200 040000002D01050007000000210501002801AA01E400040000002D010400040000002D01030007 000000210501007201AA015101040000002D0104000700000021050100D701AA01010204000000 2D01030007000000210501007301AA017F02040000002D010500040000002D010200040000002D 010500040000002D010200040000002D01050007000000210501002901AA010B03040000002D01 06000700000021050100320108017803040000002D01040007000000210501003D01AA013A0404 0000002D010200040000002D01030007000000210501007201AA012805040000002D0106000700 00002105010032010801A005040000002D0104000700000021050100D701AA014606040000002D 010200040000002D01030007000000210501007301AA01C406040000002D010600070000002105 0100320108015007040000002D010500040000002D010200040000002D010500040000002D0102 00040000002D01050007000000210501002901AA01BE07040000002D0104000700000021050100 3D01AA019208040000002D01030007000000210501007601AA018009040000002D010400070000 0021050100D701AA01540A040000002D01030007000000210501007801AA01D20A08000000FA02 00000000000000000000040000002D0107001C000000FB021000070000000000BC020000000001 02022253797374656D0000780C0AAC38E91200D89FF177E19FF1772020F3770D0B664404000000 2D010800040000002701FFFF04000000F001000004000000F001010004000000F0010200040000 00F001030004000000F001040004000000F001050004000000F0010600040000002701FFFF0400 00002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF04 0000002701FFFF030000000000 }\plain\f3\fs22\cf2 \par \pard\ri4\plain\f5\fs28\cf3 aa\plain\f5\fs28\cf0 Er m\'fcsste also die Quadratwurzel modulo \plain\f5\fs28\cf0\i N\plain\f5\fs28\cf0 aus \plain\f5\fs28\cf0\i vx\plain\f5\fs28\cf0 berechnen. Dies ist aller- \par \plain\f5\fs28\cf3 aa\plain\f5\fs28\cf0 dings und gl\'fccklicherweise bei so gro\'dfen Zahlen sehr schwer. Was aber, \par \plain\f5\fs28\cf3 aa\plain\f5\fs28\cf0 wenn er vorher w\'fcsste, dass der Herausforderer ihm eine 1 zuschickt? Dann \par \plain\f5\fs28\cf3 aa\plain\f5\fs28\cf0 k\'f6nnte er sich folgenderweise darauf vorbereiten. Er w\'e4hlt \par \pard\li3000\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw3151\pich1390\picscalex99\picscaley99\picwgoal1803\pichgoal795 010009000003C102000009001C0000000000050000000B0200000000050000000C026E054F0C03 0000001E00050000000C027C056E0C050000000B0200000000030000001E00050000000C027E05 710C050000000B0200000000050000000B0200000000030000001E00050000000C028C05900C05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C029C05B30C050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C02AB05D40C050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C02AC05D60C050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C0237034707050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C0000000D0B0A4538E91200D89FF177E19FF1 772020F377780C66AE040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C0000006D0C0A5238E91200D89FF177E19FF1772020F377 780C66AE040000002D0102000B00000026060F000C004D617468547970650000CD001C000000FB 02E8FE00000000000090010100000107000000417269616C000000180C0A7A38E91200D89FF177 E19FF1772020F377780C66AE040000002D010300040000002D010200040000002D0103001C0000 00FB023AFF00000000000090010000000107000000417269616C0000002E0C0A0938E91200D89F F177E19FF1772020F377780C66AE040000002D010400040000002D010200040000002D01030004 0000002D010200040000002D010300040000002D0102001C000000FB02E8FE0000000000009001 000000020700000053796D626F6C0000650C0A3338E91200D89FF177E19FF1772020F377780C66 AE040000002D010500040000002D010200040000002D0103000700000021050100780036026400 040000002D01050007000000210501003D0036024F01040000002D010200040000002D01030007 000000210501007200AA015D02040000002D010400070000002105010032000801D50204000000 2D01030007000000210501007600D30282021C000000FB02E8FE00000000000090010000000207 0000005346204D617468204578740038E91200D89FF177E19FF1772020F377780C66AE04000000 2D0106000700000021050100C500CA013D020700000021050100C500CA01BB02040000002D0102 0007000000210501006D003602A90307000000210501006F003602920407000000210501006400 36022E05040000002D01030007000000210501004E003602100608000000FA0200000000000000 000000040000002D0107001C000000FB021000070000000000BC02000000000102022253797374 656D0000B30B0A3438E91200D89FF177E19FF1772020F377780C66AE040000002D010800040000 002701FFFF04000000F001000004000000F001010004000000F001020004000000F00103000400 0000F001040004000000F001050004000000F0010600040000002701FFFF040000002701FFFF04 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 030000000000 }\plain\f5\fs28\cf0 \par \pard\ri4\plain\f5\fs28\cf3 aa\plain\f5\fs28\cf0 und\plain\f3\fs22\cf2 \par \pard\li3000\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw2834\pich853\picscalex98\picscaley98\picwgoal1623\pichgoal488 0100090000033902000007001C0000000000050000000B0200000000050000000C025503120B03 0000001E00050000000C025E032F0B050000000B0200000000030000001E00050000000C026803 4E0B050000000B0200000000050000000B0200000000030000001E00050000000C0271036C0B05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C027B038C0B050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C028503AA0B050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C028703AC0B050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C0200029E06050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C000000780C0AAF38E91200D89FF177E19FF1 772020F377B30B6636040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C000000A10A0A6738E91200D89FF177E19FF1772020F377 B30B6636040000002D0102000B00000026060F000C004D6174685479706500007F001C000000FB 02E8FE00000000000090010100000107000000417269616C000000650C0A3438E91200D89FF177 E19FF1772020F377B30B6636040000002D010300040000002D0102001C000000FB02E8FE000000 0000009001000000020700000053796D626F6C00002E0C0A0A38E91200D89FF177E19FF1772020 F377B30B6636040000002D010400040000002D010200040000002D010300070000002105010079 0161016400040000002D01040007000000210501003D0161015401040000002D01030007000000 21050100720161014202040000002D01020007000000210501006D016101000307000000210501 006F016101E9030700000021050100640161018504040000002D01030007000000210501004E01 6101670508000000FA0200000000000000000000040000002D0105001C000000FB021000070000 000000BC02000000000102022253797374656D0000180C0A7B38E91200D89FF177E19FF1772020 F377B30B6636040000002D010600040000002701FFFF04000000F001000004000000F001010004 000000F001020004000000F001030004000000F0010400040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF030000000000 }\plain\f3\fs22\cf2 \par \pard\ri4\plain\f5\fs28\cf0 Demnach kann der Betr\'fcger immer nur in einer der beiden Situation betr\'fcgen. \par Allgemein sieht das Vorgehen folgenderweise aus: \par Er w\'e4hlt zuf\'e4llig ein Bit \plain\f5\fs28\cf0\i c\plain\f5\fs28\cf0 und setzt \par \pard\li4000\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw3893\pich1318\picscalex99\picscaley99\picwgoal2229\pichgoal754 0100090000030A0300000A001C0000000000050000000B0200000000050000000C022605350F03 0000001E00050000000C0233055C0F050000000B0200000000030000001E00050000000C024205 5F0F050000000B0200000000050000000B0200000000030000001E00050000000C025005860F05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025F05B10F050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C026D05DA0F050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C026E05DC0F050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C021403FE08050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C000000B30B0A3738E91200D89FF177E19FF1 772020F377180C667D040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C0000002E0C0A0B38E91200D89FF177E19FF1772020F377 180C667D040000002D0102000B00000026060F000C004D617468547970650000FC001C000000FB 02E8FE00000000000090010100000107000000417269616C000000650C0A3538E91200D89FF177 E19FF1772020F377180C667D040000002D010300040000002D010200040000002D0103001C0000 00FB023AFF00000000000090010000000107000000417269616C000000A10A0A6838E91200D89F F177E19FF1772020F377180C667D040000002D010400040000002D010200040000002D0103001C 000000FB023AFF00000000000090010100000107000000417269616C000000780C0AB038E91200 D89FF177E19FF1772020F377180C667D040000002D010500040000002D0102001C000000FB02E8 FE0000000000009001000000020700000053796D626F6C00006D0C0A5338E91200D89FF177E19F F1772020F377180C667D040000002D010600040000002D010300040000002D010200040000002D 010600040000002D010200040000002D01030007000000210501007801D9016400040000002D01 060007000000210501003D01D9014F01040000002D010200040000002D01030007000000210501 007201D9013D02040000002D010400070000002105010032013701B502040000002D0106000700 000021050100D701D9015B03040000002D010200070000002105010031014D012B04040000002D 01030007000000210501007601B002F903040000002D010500070000002105010063010C029504 1C000000FB02E8FE000000000000900100000002070000005346204D617468204578740038E912 00D89FF177E19FF1772020F377180C667D040000002D0107000700000021050100C5016D01D903 0700000021050100C5016D017204040000002D01020007000000210501006D01D9016005070000 00210501006F01D901490607000000210501006401D901E506040000002D010300070000002105 01004E01D901C70708000000FA0200000000000000000000040000002D0108001C000000FB0210 00070000000000BC02000000000102022253797374656D0000940C0AF138E91200D89FF177E19F F1772020F377180C667D040000002D010900040000002701FFFF04000000F001000004000000F0 01010004000000F001020004000000F001030004000000F001040004000000F001050004000000 F001060004000000F0010700040000002701FFFF040000002701FFFF040000002701FFFF040000 002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f3\fs22\cf2 \par \pard\li4500\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw2804\pich842\picscalex98\picscaley98\picwgoal1606\pichgoal483 0100090000036D02000007001C0000000000050000000B0200000000050000000C024A03F40A03 0000001E00050000000C025503120B050000000B0200000000030000001E00050000000C025E03 2F0B050000000B0200000000050000000B0200000000030000001E00050000000C0268034E0B05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C0271036C0B050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C027B038C0B050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C028503AA0B050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C028703AC0B050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00030000001E00050000000C0200029E06050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B 0200000000050000000B0200000000050000000B020000000008000000FA020000000000000000 0000040000002D0100001C000000FB0238FF00000000000090010000000107000000417269616C 000000180C0A7E38E91200D89FF177E19FF1772020F377940C66F3040000002D01010005000000 020101000000050000000102FFFFFF00050000002E011800000005000000090200000000040000 00080100001C000000FB02E8FE00000000000090010000000107000000417269616C0000000D0B 0A4738E91200D89FF177E19FF1772020F377940C66F3040000002D0102000B00000026060F000C 004D6174685479706500007F001C000000FB02E8FE000000000000900101000001070000004172 69616C0000006D0C0A5438E91200D89FF177E19FF1772020F377940C66F3040000002D01030004 0000002D0102001C000000FB02E8FE0000000000009001000000020700000053796D626F6C0000 780C0AB138E91200D89FF177E19FF1772020F377940C66F3040000002D010400040000002D0102 00040000002D0103000700000021050100790061016400040000002D0104000700000021050100 3D0061015401040000002D0103000700000021050100720061014202040000002D010200070000 00210501006D006101000307000000210501006F006101E9030700000021050100640061018504 040000002D01030007000000210501004E006101670508000000FA020000000000000000000004 0000002D0105001C000000FB021000070000000000BC02000000000102022253797374656D0000 A10A0A6938E91200D89FF177E19FF1772020F377940C66F3040000002D010600040000002701FF FF04000000F001000004000000F001010004000000F001020004000000F001030004000000F001 0400040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400000027 01FFFF040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f3\fs22\cf2 \par \pard\ri4\plain\f5\fs28\cf0 Der Herausforderer verifiziert, dann so: \par \pard\li4000\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw3237\pich976\picscalex99\picscaley98\picwgoal1853\pichgoal559 0100090000038702000008001C0000000000050000000B0200000000050000000C02D003A50C03 0000001E00050000000C02DB03C50C050000000B0200000000030000001E00050000000C02E603 C80C050000000B0200000000050000000B0200000000030000001E00050000000C02F103E80C05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C02FC030C0D050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C0207042E0D050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C020804300D050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C0249027A07050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C000000940C0AF438E91200D89FF177E19FF1 772020F377A10A666B040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C000000780C0AB238E91200D89FF177E19FF1772020F377 A10A666B040000002D0102000B00000026060F000C004D6174685479706500007F001C000000FB 02E8FE00000000000090010100000107000000417269616C0000006D0C0A5538E91200D89FF177 E19FF1772020F377A10A666B040000002D0103001C000000FB023AFF0000000000009001000000 0107000000417269616C0000000D0B0A4838E91200D89FF177E19FF1772020F377A10A666B0400 00002D010400040000002D010200040000002D010300040000002D010400040000002D01030004 0000002D0102001C000000FB02E8FE0000000000009001000000020700000053796D626F6C0000 180C0A7F38E91200D89FF177E19FF1772020F377A10A666B040000002D010500040000002D0102 00040000002D01030007000000210501007900AA016400040000002D0104000700000021050100 320008010001040000002D01050007000000210501003D00AA01C201040000002D010200040000 002D01030007000000210501007200AA01B002040000002D010400070000002105010032000801 2803040000002D01020007000000210501006D00AA01DC0307000000210501006F00AA01C50407 000000210501006400AA016105040000002D01030007000000210501004E00AA01430608000000 FA0200000000000000000000040000002D0106001C000000FB021000070000000000BC02000000 000102022253797374656D0000650C0A3638E91200D89FF177E19FF1772020F377A10A666B0400 00002D010700040000002701FFFF04000000F001000004000000F001010004000000F001020004 000000F001030004000000F001040004000000F0010500040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF030000000000 }\plain\f3\fs22\cf2 \par \pard\li3500\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw5266\pich988\picscalex98\picscaley99\picwgoal3016\pichgoal565 010009000003F102000009001C0000000000050000000B0200000000050000000C02DC03921403 0000001E00050000000C02E503C814050000000B0200000000030000001E00050000000C02E803 FF14050000000B0200000000050000000B0200000000030000001E00050000000C02F203371505 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C02FE036F15050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C020904A715050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C020B04A815050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C024B02470C050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C000000A10A0A6C38E91200D89FF177E19FF1 772020F377650C6638040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C000000180C0A8038E91200D89FF177E19FF1772020F377 650C6638040000002D0102000B00000026060F000C004D6174685479706500007F001C000000FB 02E8FE00000000000090010100000107000000417269616C0000000D0B0A4938E91200D89FF177 E19FF1772020F377650C6638040000002D0103001C000000FB023AFF0000000000009001000000 0107000000417269616C0000006D0C0A5638E91200D89FF177E19FF1772020F377650C66380400 00002D010400040000002D010300040000002D010200040000002D010300040000002D01020004 0000002D0103001C000000FB023AFF00000000000090010100000107000000417269616C000000 780C0AB338E91200D89FF177E19FF1772020F377650C6638040000002D0105001C000000FB02E8 FE0000000000009001000000020700000053796D626F6C0000940C0AF538E91200D89FF177E19F F1772020F377650C6638040000002D010600040000002D010300040000002D010200040000002D 010600040000002D010200040000002D01030007000000210501007201AC016400040000002D01 0400070000002105010032010A01DC00040000002D01020007000000210501006D01AC01900107 000000210501006F01AC01790207000000210501006401AC011503040000002D01030007000000 210501004E01AC01F703040000002D01060007000000210501003D01AC011E05040000002D0103 0007000000210501007801AC010C06040000002D0106000700000021050100D701AC01DB060400 00002D010200040000002D01030007000000210501007601AC015907040000002D010500070000 002105010062010801F507040000002D01020007000000210501006D01AC01A908070000002105 01006F01AC01920907000000210501006401AC012E0A040000002D01030007000000210501004E 01AC01100B08000000FA0200000000000000000000040000002D0107001C000000FB0210000700 00000000BC02000000000102022253797374656D00002E0C0A0C38E91200D89FF177E19FF17720 20F377650C6638040000002D010800040000002701FFFF04000000F001000004000000F0010100 04000000F001020004000000F001030004000000F001040004000000F001050004000000F00106 00040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701 FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 \par \pard\ri4\plain\f5\fs28\cf0 Falls folgende Gleichung gilt, hat der Betr\'fcger es geschafft, zu betr\'fcgen:\plain\f3\fs22\cf2 \par \pard\li3000\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw6305\pich1318\picscalex99\picscaley99\picwgoal3609\pichgoal754 0100090000036E0300000A001C0000000000050000000B0200000000050000000C022605A11803 0000001E00050000000C023305DF18050000000B0200000000030000001E00050000000C024205 E218050000000B0200000000050000000B0200000000030000001E00050000000C025005221905 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C025F056619050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C026D05A819050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C026E05AA19050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C0214038D0E050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C000000650C0A3938E91200D89FF177E19FF1 772020F3772E0C660E040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C000000940C0AF638E91200D89FF177E19FF1772020F377 2E0C660E040000002D0102000B00000026060F000C004D617468547970650000FC001C000000FB 02E8FE00000000000090010100000107000000417269616C000000780C0AB438E91200D89FF177 E19FF1772020F3772E0C660E040000002D0103001C000000FB023AFF0000000000009001000000 0107000000417269616C0000006D0C0A5738E91200D89FF177E19FF1772020F3772E0C660E0400 00002D010400040000002D010300040000002D010200040000002D010300040000002D01040004 0000002D010200040000002D0103001C000000FB023AFF00000000000090010100000107000000 417269616C0000000D0B0A4A38E91200D89FF177E19FF1772020F3772E0C660E040000002D0105 00040000002D010200040000002D010300040000002D0105001C000000FB02E8FE000000000000 9001000000020700000053796D626F6C0000180C0A8138E91200D89FF177E19FF1772020F3772E 0C660E040000002D010600040000002D010300040000002D010200040000002D01060004000000 2D010200040000002D01030007000000210501007201D9016400040000002D0104000700000021 05010032013701DC00040000002D01020007000000210501006D01D90190010700000021050100 6F01D901790207000000210501006401D9011503040000002D01030007000000210501004E01D9 01F703040000002D01060007000000210501003D01D9011E05040000002D010200040000002D01 030007000000210501007201D9010C06040000002D010400070000002105010032013701840604 0000002D0106000700000021050100D701D9012A07040000002D01020007000000210501003101 4D01FA07040000002D01030007000000210501007601B002C807040000002D0105000700000021 05010063010C0264081C000000FB02E8FE000000000000900100000002070000005346204D6174 68204578740038E91200D89FF177E19FF1772020F3772E0C660E040000002D0107000700000021 050100C5016D01A8070700000021050100C5016D014108040000002D0106000700000021050100 D701D9012109040000002D010200040000002D01030007000000210501007601D9019F09040000 002D0105000700000021050100620135013B0A040000002D01020007000000210501006D01D901 EF0A07000000210501006F01D901D80B07000000210501006401D901740C040000002D01030007 000000210501004E01D901560D08000000FA0200000000000000000000040000002D0108001C00 0000FB021000070000000000BC02000000000102022253797374656D0000B30B0A3838E91200D8 9FF177E19FF1772020F3772E0C660E040000002D010900040000002701FFFF04000000F0010000 04000000F001010004000000F001020004000000F001030004000000F001040004000000F00105 0004000000F001060004000000F0010700040000002701FFFF040000002701FFFF040000002701 FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0300000000 00 }\plain\f3\fs22\cf2 \par \pard\ri4\plain\f5\fs28\cf0 Demnach kann man nur betr\'fcgen, wenn \plain\f5\fs28\cf0\i b\plain\f5\fs28\cf0 = \plain\f5\fs28\cf0\i c\plain\f5\fs28\cf0 gilt. Dies gilt aber schon mit einer \par Wahrscheinlichkeit von 1/2. Daher muss das Protokoll mehrmals durchgef\'fchrt \par werden, um die Wahrscheinlichkeit zu verringern. Bei \plain\f5\fs28\cf0\i t\plain\f5\fs28\cf0 Durchf\'fchrungen ergibt \par sich eine Wahrscheinlichkeit von \par \pard\li4500\ri4\plain\f3\fs22\cf2 {\pict\wmetafile8\picw816\pich1390\picscalex99\picscaley99\picwgoal466\pichgoal795 0100090000031702000007001C0000000000050000000B0200000000050000000C026E05300303 0000001E00050000000C027C053703050000000B0200000000030000001E00050000000C027E05 3A03050000000B0200000000050000000B0200000000030000001E00050000000C028C05410305 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C029C054C03050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C02AB055503050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C02AC055603050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0003 0000001E00050000000C023703E401050000000B0200000000050000000B020000000005000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B020000000008000000FA0200000000000000000000040000002D0100001C000000FB0238FF 00000000000090010000000107000000417269616C0000002E0C0A0F38E91200D89FF177E19FF1 772020F377B30B663A040000002D01010005000000020101000000050000000102FFFFFF000500 00002E01180000000500000009020000000004000000080100001C000000FB02E8FE0000000000 0090010000000107000000417269616C000000A10A0A6E38E91200D89FF177E19FF1772020F377 B30B663A040000002D0102000B00000026060F000C004D61746854797065000018011C000000FB 023AFF00000000000090010100000107000000417269616C000000180C0A8238E91200D89FF177 E19FF1772020F377B30B663A040000002D010300040000002D010200070000002105010031014D 01A40007000000210501003201D3028400040000002D010300070000002105010074012F022001 1C000000FB02E8FE000000000000900100000002070000005346204D617468204578740038E912 00D89FF177E19FF1772020F377B30B663A040000002D0104000700000021050100C5016D016400 0700000021050100C5016D01D80008000000FA0200000000000000000000040000002D0105001C 000000FB021000070000000000BC02000000000102022253797374656D00006D0C0A5838E91200 D89FF177E19FF1772020F377B30B663A040000002D010600040000002701FFFF04000000F00100 0004000000F001010004000000F001020004000000F001030004000000F0010400040000002701 FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400000027 01FFFF040000002701FFFF030000000000 }\plain\f5\fs28\cf0 \par \pard\ri4\plain\f4\fs20\cf2 \par \plain\f3\fs20\cf0\b _____________________________________________________________________________________ \par \plain\f4\fs22\cf0 \par \plain\f4\fs22\cf4\b Anmerkungen:\plain\f4\fs22\cf4 \par \plain\f4\fs20\cf4\b 1. \plain\f4\fs20\cf4 Unter \plain\f4\fs20\cf4\b\i www.schule.mupad.de/material/\plain\f4\fs20\cf4 befinden sich Notebooks, die sich ebenfalls mit Kryptographie \par \plain\f4\fs20\cf3 ss\plain\f4\fs20\cf4 besch\'e4ftigen. \par \par \plain\f4\fs20\cf4\b 2. \plain\f4\fs20\cf4 Weitere Anregungen finden Sie in der Buchreihe \plain\f4\fs20\cf1 Mathematik 1 x anders\plain\f4\fs20\cf4 . In dieser Reihe wird eine Vielzahl \par \plain\f4\fs20\cf3 ss\plain\f4\fs20\cf4 unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die B\'fccher k\'f6nnen unter \par \plain\f4\fs20\cf3 ss\plain\f6\fs20\cf2 www.schule.mupad.de/literatur\plain\f4\fs20\cf4 kostenfrei kopiert werden. \par \plain\f4\fs20\cf1 \par \plain\f3\fs20\cf0\b _____________________________________________________________________________________ \par \par \par }