\mnb150ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fswiss\fprq2 Arial;}{\f4\fswiss\fprq2 Helvetica;}{\f5\fmodern\fprq1 Courier New;}{\f6\fswiss\fprq2\fcharset1 Arial;}{\f7\froman\fcharset1 Times New Roman;}} {\colortbl\red0\green0\blue0;\red0\green128\blue0;\red0\green0\blue255;\red0\green0\blue128;\red255\green0\blue0;\red255\green255\blue255;} \deflang1031\pard\ri4\plain\f5\fs20\cf0\b ________________________________________________________________________________ \par \par \plain\f5\fs20\cf0 Inhalt....: Wiener Attacke \par Kategorie.: Arbeitsblatt \par Mathematik: Kryptographie, Zahlentheorie \par MuPAD.....: 3.0.0 \par Datum.....: 2003-06-23 \par Autoren...: Julia Faflek \par Funktionen: contfrac, numlib::contfrac::rational, random, nextprime, igcd, mod \par ________________________________________________________________________________ \par \plain\f3\fs36\cf0\b \par \plain\f3\fs40\cf0\b Der Angriff von Wiener\plain\f3\fs36\cf0\b \par \plain\f3\fs22\cf0 \par \plain\f3\fs24\cf1 RSA ist weltweiter Standard bei der Ver- und Entschl\'fcsselung von Daten. Hier wird der Angriff \par von Wiener vorgestellt, der auf Kettenbr\'fcchen basiert. Mit diesem Angriff kann RSA erfolgreich \par gebrochen, wenn \par \pard\li4500\ri4\plain\f5\fs22\cf2 {\pict\wmetafile8\picw1794\pich1242\picscalex99\picscaley99\picwgoal1018\pichgoal705 010009000003AC03000009001C0000000000050000000B0200000000050000000C02DA04020703 0000001E00050000000C02DC040507050000000B0200000000030000001E00050000000C02E804 1707050000000B0200000000050000000B0200000000030000001E00050000000C02F6042B0705 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C0203053E07050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C0211055207050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C021F056607050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C022E057A07050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C023C058E07050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00050000000C023D058F0705000000 0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500 00000B0200000000030000001E00030000001E00050000000C02F8024904050000000B02000000 00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C00 0000FB0238FF00000000000090010000000107000000417269616C0000007B0F0A0138E91200D8 9FF177E19FF1772020F377DA0D66C7040000002D01010005000000020101000000050000000102 FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB0210 FF00000000000090010000000107000000417269616C000000DF0D0A6138E91200D89FF177E19F F1772020F377DA0D66C7040000002D0102000B00000026060F000C004D617468547970650000BE 001C000000FB0210FF00000000000090010100000107000000417269616C000000D00C0A4138E9 1200D89FF177E19FF1772020F377DA0D66C7040000002D010300040000002D010200040000002D 0103001C000000FB0210FF000000000000900100000002070000005346204D6174682045787400 38E91200D89FF177E19FF1772020F377DA0D66C7040000002D010400040000002D010200040000 002D010400040000002D010200040000002D010400040000002D010200040000002D0104000400 00002D0102001C000000FB0260FF00000000000090010000000107000000417269616C0000008A 0A0ADD38E91200D89FF177E19FF1772020F377DA0D66C7040000002D010500040000002D010200 1C000000FB0210FF0000000000009001000000020700000053796D626F6C0000B40F0A5E38E912 00D89FF177E19FF1772020F377DA0D66C7040000002D010600040000002D010200050000000902 00800000040000002D010300070000002105010064000A026400040000002D0106000700000021 0501003C000A023D01040000002D010200040000002D010400040000002D010200040000002D01 0400040000002D010200040000002D010400040000002D010200040000002D010400040000002D 010200040000002D010400040000002D010200040000002D010400070000002105010070007300 24020700000021050100C500730014030700000021050100C50073003A03040000002D01030007 000000210501004E0073011403040000002D01050007000000210501003400E800340204000000 2D010200070000002105010033009102B402040000002D0104000700000021050100C500AE0109 020700000021050100C500AE0199020700000021050100C500AE0129030700000021050100C500 AE01550308000000FA0200000000000000000000040000002D0107001C000000FB021000070000 000000BC02000000000102022253797374656D00001C0E0A5F38E91200D89FF177E19FF1772020 F377DA0D66C7040000002D010800040000002701FFFF04000000F001000004000000F001010004 000000F001020004000000F001030004000000F001040004000000F001050004000000F0010600 040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF FF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701 FFFF030000000000 }\plain\f5\fs22\cf2 \par \pard\ri4\plain\f3\fs28\cf0 \par Zun\'e4chst besch\'e4ftigen wir uns mit dem Begriff der \plain\f3\fs28\cf0\i Kettenbruchentwicklung\plain\f3\fs28\cf0 . \par Dieser stellt eine rationale Zahl \plain\f5\fs28\cf4 a\plain\f3\fs28\cf0 dar. Mit dem Befehl \plain\f5\fs28\cf4 contfrac(a)\plain\f3\fs28\cf0 erhalten \par wir die gew\'fcnschte Darstellung: \par \plain\f5\fs22\cf2 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}contfrac(5/3) \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}contfrac(123/1234) \par \pard\ri4\plain\f6\fs28\cf0 \par Folgender Aufruf \par \plain\f5\fs22\cf2 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}op(contfrac(123/1234), 1) \par \pard\ri4\plain\f6\fs28\cf0 \par liefert eine geordnete Liste der Koeffizienten.\plain\f3\fs28\cf0 Damit l\'e4sst sich \plain\f3\fs28\cf0\i m\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 darstell- \par ten als \plain\f3\fs28 [\plain\f3\fs28\i a\plain\f3\fs19\dn5 0\plain\f3\fs28 , \plain\f3\fs28\i a\plain\f3\fs19\dn5 1\plain\f3\fs28 , \'85, \plain\f3\fs28\i a\plain\f3\fs19\dn5 n\plain\f3\fs28 ]. \plain\f3\fs28\cf0 Definieren wir nun die \plain\f3\fs28\cf0\i i-te Konvergente\plain\f3\fs28\cf0 einer Ketten- \par bruchentwicklung: Sei \plain\f3\fs28 [\plain\f3\fs28\i a\plain\f3\fs19\dn5 0\plain\f3\fs28 , \plain\f3\fs28\i a\plain\f3\fs19\dn5 1\plain\f3\fs28 , \'85, \plain\f3\fs28\i a\plain\f3\fs19\dn5 n\plain\f3\fs28 ] = \plain\f3\fs28\cf0\i m\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 , so ist \plain\f3\fs28\cf0\i u\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i v\plain\f3\fs28\cf0 = \plain\f3\fs28 [\plain\f3\fs28\i a\plain\f3\fs19\dn5 0\plain\f3\fs28 , \plain\f3\fs28\i a\plain\f3\fs19\dn5 1\plain\f3\fs28 , \'85, \plain\f3\fs28\i a\plain\f3\fs19\dn5 i\plain\f3\fs28 ] die i-te \par Konvergente der Kettenbruchentwicklung von \plain\f3\fs28\cf0\i m\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 .\plain\f3\fs28 \par \par In MuPAD k\'f6nnen wir das wie folgt umsetzen: Wir berechnen die 3-te Kon- \par vergente der Kettenbruchentwicklung von 123/1234. \par \plain\f3\fs28\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}contfrac(123/1234, 3) \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}numlib::contfrac::rational(contfrac(123/1234), 3) \par \pard\ri4\plain\f3\fs28\cf0 \par F\'fcr \plain\f3\fs28\cf0\i m\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 und \plain\f3\fs28\cf0\i u\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i v\plain\f3\fs28\cf0 gelte \par \pard\li4000\ri4\plain\f5\fs22\cf2 {\pict\wmetafile8\picw3589\pich1375\picscalex98\picscaley99\picwgoal2055\pichgoal786 010009000003C803000009001C0000000000050000000B0200000000050000000C025F05050E03 0000001E00050000000C026B052A0E050000000B0200000000030000001E00050000000C026E05 500E050000000B0200000000050000000B0200000000030000001E00050000000C027C05760E05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C027E059D0E050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C028C05C30E050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C029C05EC0E050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C02AB05130F050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C02AC05150F050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00030000001E00050000000C023703 8D08050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C 000000FB0238FF00000000000090010000000107000000417269616C000000D00C0A4538E91200 D89FF177E19FF1772020F377B40F6662040000002D010100050000000201010000000500000001 02FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB02 E8FE00000000000090010000000107000000417269616C0000008A0A0AE038E91200D89FF177E1 9FF1772020F377B40F6662040000002D0102000B00000026060F000C004D617468547970650000 18011C000000FB02E8FE00000000000090010100000107000000417269616C000000FB090A3138 E91200D89FF177E19FF1772020F377B40F6662040000002D010300040000002D01020004000000 2D010300040000002D010200040000002D010300040000002D010200040000002D010300040000 002D0102001C000000FB02E8FE0000000000009001000000020700000053796D626F6C00001C0E 0A6338E91200D89FF177E19FF1772020F377B40F6662040000002D0104001C000000FB02E8FE00 0000000000900100000002070000005346204D617468204578740038E91200D89FF177E19FF177 2020F377B40F6662040000002D010500040000002D010200040000002D0103001C000000FB023A FF00000000000090010000000107000000417269616C000000DF0D0A6338E91200D89FF177E19F F1772020F377B40F6662040000002D010600040000002D010400040000002D010200040000002D 010400040000002D010200040000002D0105000700000021050100AF0198006400070000002105 0100AF01400164000700000021050100AF01CE016400040000002D010200040000002D01030007 000000210501006D014D01E10007000000210501006E0176020701040000002D01050007000000 21050100C5016D01C1000700000021050100C5016D014201040000002D01040007000000210501 002D01D9013002040000002D010200040000002D010300070000002105010075014A0130030700 000021050100760176023103040000002D0105000700000021050100C5016D0110030700000021 050100C5016D0146030700000021050100AF019800EE030700000021050100AF014001EE030700 000021050100AF01CE01EE03040000002D01040007000000210501003C01D9019F04040000002D 010200070000002105010031014D018D06040000002D010400040000002D010200070000002105 01003201D302AD05040000002D0104000700000021050100D701D3028106040000002D01020004 0000002D01030007000000210501007601D302FF06040000002D01060007000000210501003201 31029B07040000002D0105000700000021050100C5016D018D050700000021050100C5016D0135 060700000021050100C5016D01DD060700000021050100C5016D01810708000000FA0200000000 000000000000040000002D0107001C000000FB021000070000000000BC02000000000102022253 797374656D00007B0F0A0238E91200D89FF177E19FF1772020F377B40F6662040000002D010800 040000002701FFFF04000000F001000004000000F001010004000000F001020004000000F00103 0004000000F001040004000000F001050004000000F0010600040000002701FFFF040000002701 FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400000027 01FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f3\fs28\cf0 \par \pard\ri4\plain\f3\fs28\cf0 Dann ist \plain\f3\fs28\cf0\i u\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i v\plain\f3\fs28\cf0 eine Konvergente der Kettenbruchentwicklung von \plain\f3\fs28\cf0\i m\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i n\plain\f3\fs28\cf0 . \par \plain\f5\fs22\cf4 \par \plain\f3\fs28\cf0 Diese Tatsache wird nun auf den folgenden Satz angewandt: \par \par Sei \plain\f3\fs28\cf0\i N\plain\f3\fs28\cf0 = \plain\f3\fs28\cf0\i pq\plain\f3\fs28\cf0 , wobei \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 und \plain\f3\fs28\cf0\i q\plain\f3\fs28\cf0 Primzahlen mit \plain\f3\fs28\cf0\i q \plain\f3\fs28\cf0 < \plain\f3\fs28\cf0\i p \plain\f3\fs28\cf0 < 2\plain\f3\fs28\cf0\i q\plain\f3\fs28\cf0 . Weiter seien \plain\f3\fs28\cf0\i e\plain\f3\fs28\cf0 , \plain\f3\fs28\cf0\i d\plain\f3\fs28\cf0 \par teilerfremd zu Phi(\plain\f3\fs28\cf0\i N\plain\f3\fs28\cf0 ), wobei Phi die Eulersche Phi-Funktion bezeichnet, \par mit \plain\f3\fs28\cf0\i ed \plain\f3\fs28\cf0 = 1 mod Phi(\plain\f3\fs28\cf0\i N\plain\f3\fs28\cf0 ). Daraus folgt: \plain\f3\fs28\cf0\i ed\plain\f3\fs28\cf0 - 1 = \plain\f3\fs28\cf0\i k\plain\f3\fs28\cf0 Phi(\plain\f3\fs28\cf0\i N\plain\f3\fs28\cf0 ) f\'fcr eine ganze Zahl \plain\f3\fs28\cf0\i k\plain\f3\fs28\cf0 . \par Schlie\'dflich sei \par \pard\li4500\ri4\plain\f5\fs22\cf2 {\pict\wmetafile8\picw2080\pich1380\picscalex99\picscaley98\picwgoal1191\pichgoal791 0100090000036903000009001C0000000000050000000B0200000000050000000C026405200803 0000001E00050000000C0274053508050000000B0200000000030000001E00050000000C028305 3708050000000B0200000000050000000B0200000000030000001E00050000000C0292054C0805 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C0294054F08050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C02A2056408050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C02B3057C08050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C02C2059208050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C02C3059408050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00030000001E00050000000C024403 DD04050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C 000000FB0238FF00000000000090010000000107000000417269616C000000B40F0A6338E91200 D89FF177E19FF1772020F3777B0F6604040000002D010100050000000201010000000500000001 02FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB02 E8FE00000000000090010000000107000000417269616C000000DF0D0A6438E91200D89FF177E1 9FF1772020F3777B0F6604040000002D0102000B00000026060F000C004D617468547970650000 D0001C000000FB02E8FE00000000000090010100000107000000417269616C000000DA0D0ACB38 E91200D89FF177E19FF1772020F3777B0F6604040000002D010300040000002D01020004000000 2D0103001C000000FB02E8FE000000000000900100000002070000005346204D61746820457874 0038E91200D89FF177E19FF1772020F3777B0F6604040000002D010400040000002D0102000400 00002D010400040000002D010200040000002D010400040000002D010200040000002D01040004 0000002D0102001C000000FB0260FF00000000000090010000000107000000417269616C000000 FB090A3238E91200D89FF177E19FF1772020F3777B0F6604040000002D010500040000002D0102 001C000000FB02E8FE0000000000009001000000020700000053796D626F6C00008A0A0AE138E9 1200D89FF177E19FF1772020F3777B0F6604040000002D010600040000002D010200040000002D 0103000700000021050100640240026400040000002D01060007000000210501003C0240026001 040000002D010200040000002D010400040000002D010200040000002D010400040000002D0102 00040000002D010400040000002D010200040000002D010400040000002D010200040000002D01 0400040000002D010200040000002D0104000700000021050100700264006E0207000000210501 00C502640086030700000021050100C5026400B103040000002D01030007000000210501004E02 90018603040000002D01050007000000210501003402EC008802040000002D0102000700000021 0501003302DD021503040000002D0104000700000021050100C502D4014E020700000021050100 C502D401F6020700000021050100C502D4019E030700000021050100C502D401D10308000000FA 0200000000000000000000040000002D0107001C000000FB021000070000000000BC0200000000 0102022253797374656D0000D00C0A4638E91200D89FF177E19FF1772020F3777B0F6604040000 002D010800040000002701FFFF04000000F001000004000000F001010004000000F00102000400 0000F001030004000000F001040004000000F001050004000000F0010600040000002701FFFF04 0000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF 040000002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f3\fs28\cf0 . \par \pard\ri4\plain\f3\fs28\cf0 Dann gilt:\plain\f5\fs22\cf2 \par \pard\li3500\ri4\plain\f5\fs22\cf2 {\pict\wmetafile8\picw3589\pich1351\picscalex98\picscaley98\picwgoal2055\pichgoal773 010009000003DD03000009001C0000000000050000000B0200000000050000000C024705050E03 0000001E00050000000C0255052A0E050000000B0200000000030000001E00050000000C026405 500E050000000B0200000000050000000B0200000000030000001E00050000000C027205760E05 0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000 0C0282059D0E050000000B0200000000050000000B0200000000050000000B0200000000050000 000B0200000000030000001E00050000000C029105C30E050000000B0200000000050000000B02 00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E 00050000000C02A105EC0E050000000B0200000000050000000B0200000000050000000B020000 0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005 0000000C02B005130F050000000B0200000000050000000B0200000000050000000B0200000000 050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000 00030000001E00050000000C02B105150F050000000B0200000000050000000B02000000000500 00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005 0000000B0200000000050000000B0200000000030000001E00030000001E00050000000C023A03 8D08050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200 000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02 00000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C 000000FB0238FF00000000000090010000000107000000417269616C0000007B0F0A0538E91200 D89FF177E19FF1772020F377D00C6648040000002D010100050000000201010000000500000001 02FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB02 E8FE00000000000090010000000107000000417269616C0000008A0A0AE238E91200D89FF177E1 9FF1772020F377D00C6648040000002D0102000B00000026060F000C004D617468547970650000 1A011C000000FB02E8FE00000000000090010100000107000000417269616C000000FB090A3338 E91200D89FF177E19FF1772020F377D00C6648040000002D010300040000002D01020004000000 2D010300040000002D010200040000002D010300040000002D010200040000002D010300040000 002D0102001C000000FB02E8FE0000000000009001000000020700000053796D626F6C00001C0E 0A6538E91200D89FF177E19FF1772020F377D00C6648040000002D0104001C000000FB02E8FE00 0000000000900100000002070000005346204D617468204578740038E91200D89FF177E19FF177 2020F377D00C6648040000002D010500040000002D010200040000002D0103001C000000FB023A FF00000000000090010000000107000000417269616C000000DF0D0A6538E91200D89FF177E19F F1772020F377D00C6648040000002D010600040000002D010400040000002D010200040000002D 010400040000002D010200040000002D0105000700000021050100AF0064006400070000002105 0100AF000C0164000700000021050100AF00B40164000700000021050100AF00D1016400040000 002D010200040000002D010300070000002105010065004A01FC0007000000210501004E007602 E100040000002D0105000700000021050100C5006D01C1000700000021050100C5006D012C0104 0000002D01040007000000210501002D00D9011A02040000002D010200040000002D0103000700 0000210501006B004D0120030700000021050100640076021A03040000002D0105000700000021 050100C5006D01FA020700000021050100C5006D013A030700000021050100AF006400E2030700 000021050100AF000C01E2030700000021050100AF00B401E2030700000021050100AF00D101E2 03040000002D01040007000000210501003C00D9019304040000002D0102000700000021050100 31004D018706040000002D010400040000002D01020007000000210501003200D302A105040000 002D0104000700000021050100D700D3027506040000002D010200040000002D01030007000000 210501006400D302F306040000002D0106000700000021050100320031029B07040000002D0105 000700000021050100C5006D0181050700000021050100C5006D0129060700000021050100C500 6D01D1060700000021050100C5006D0179070700000021050100C5006D01810708000000FA0200 000000000000000000040000002D0107001C000000FB021000070000000000BC02000000000102 022253797374656D0000B40F0A6438E91200D89FF177E19FF1772020F377D00C6648040000002D 010800040000002701FFFF04000000F001000004000000F001010004000000F001020004000000 F001030004000000F001040004000000F001050004000000F0010600040000002701FFFF040000 002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400 00002701FFFF040000002701FFFF040000002701FFFF030000000000 }\plain\f5\fs22\cf2 \par \pard\ri4\plain\f3\fs28\cf0 \par Damit ist \plain\f3\fs28\cf0\i k\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i d\plain\f3\fs28\cf0 eine Konvergente der Kettenbruchentwicklung von \plain\f3\fs28\cf0\i e\plain\f3\fs28\cf0 /\plain\f3\fs28\cf0\i N\plain\f3\fs28\cf0 . \par \par Nun haben wir alles an der Hand, um RSA erfolgreich zu brechen, falls \par der private Schl\'fcssel \plain\f3\fs28\cf0\i d\plain\f3\fs28\cf0 entsprechend klein ist.\plain\f5\fs22\cf2 \par \par \plain\f3\fs28\cf0 Wir erzeugen zun\'e4chst zwei gro\'dfe Primzahlen \plain\f3\fs28\cf0\i p \plain\f3\fs28\cf0 und \plain\f3\fs28\cf0\i q\plain\f3\fs28\cf0 , so dass \plain\f3\fs28\cf0\i q\plain\f3\fs28\cf0 <\plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 <2\plain\f3\fs28\cf0\i q\plain\f3\fs28\cf0 : \par \pard\li600\ri1\fi-300\plain\f5\fs22\cf4 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}q1 := random(10^20..10^21): \par \pard\li600\ri1\fi-300\plain\f5\fs28\cf4 q := nextprime(q1()) \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}p1 := random(q..2*q): \par \pard\li600\ri1\fi-300\plain\f5\fs28\cf4 p := nextprime(p1()) \par \pard\ri4\plain\f5\fs22\cf2 \par \plain\f6\fs28\cf0 Nun berechnen wir den Modul \plain\f6\fs28\cf0\i N\plain\f6\fs28\cf0 und Phi(\plain\f6\fs28\cf0\i N\plain\f6\fs28\cf0 ): \par \plain\f7\fs22\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}N := p * q; \par \pard\li600\ri1\fi-300\plain\f5\fs28\cf4 Phi_N := (p-1) * (q-1); \par \pard\ri4\plain\f6\fs28\cf0 \par Jetzt suchen wir einen geheimen Schl\'fcssel \plain\f6\fs28\cf0\i d\plain\f6\fs28\cf0 im Intervall von 3 bis \par \plain\f3\fs28\cf0 1/3\plain\f3\fs28\cf0\i N\plain\f6\fs28\cf0 ^(1/4): \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}d1 := random(3..floor(float((1/3) * N^(1/4)))): \par \pard\li600\ri1\fi-300\plain\f5\fs28\cf4 for i from 1 to 1000 do \par d := d1(): \par if igcd(d, Phi_N) = 1 then break end_if; \par end_for: \par print(Unquoted, "d = " .expr2text(d)) \par \pard\ri4\plain\f6\fs28\cf0 \par Schlie\'dflich wird der \'f6ffentliche Schl\'fcssel \plain\f6\fs28\cf0\i e\plain\f6\fs28\cf0 berechnet: \par \plain\f7\fs22\cf0 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}e := 1/d mod Phi_N \par \pard\ri4\plain\f6\fs28\cf0 \par und eine zuf\'e4llige Nachricht \plain\f6\fs28\cf0\i x\plain\f6\fs28\cf0 generiert, um nachher den Wert von \plain\f6\fs28\cf0\i d\plain\f6\fs28\cf0 zu \par verifizieren: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}x1 := random(10^30..10^40): \par \pard\li600\ri1\fi-300\plain\f5\fs28\cf4 x := x1() \par \pard\ri4\plain\f6\fs28\cf0 \par Nun machen wir uns Gedanken um den Angriff. Wir benutzen, dazu den \par obigen Satz und berechnen alle Konvergenten der Kettenbruchentwicklung \par von \plain\f6\fs28\cf0\i e\plain\f6\fs28\cf0 /\plain\f6\fs28\cf0\i N\plain\f6\fs28\cf0 . F\'fcr jede Konvergente \'fcberpr\'fcfen wir ob der Nenner das gesuchte \par \plain\f6\fs28\cf0\i d\plain\f6\fs28\cf0 ist, indem wir den Wert \plain\f6\fs28\cf0\i x^e \plain\f6\fs28\cf0 mit dem Nenner potenzieren und \'fcberpr\'fcfen, \par ob das Ergebnis gleich \plain\f6\fs28\cf0\i x\plain\f6\fs28\cf0 ist. \par \plain\f5\fs22\cf4 \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}Wiener := proc(e, N, x) \par \pard\li600\ri1\fi-300\plain\f5\fs28\cf4 local i, d_ber; \par begin \par for i from 1 to nops(op(contfrac(e/N), 1)) do \par d_ber := denom(numlib::contfrac::rational( \par contfrac(e/N), i)): \par if powermod(x, (e * d_ber), N) = x then \par break \par end_if: \par end_for: \par print(Unquoted, "Berechnetes d ist ".expr2text(d_ber)): \par end_proc: \par \pard\ri4\plain\f7\fs22\cf0 \par \plain\f6\fs28\cf0 Wir \'fcberpr\'fcfen, ob die Attacke funktioniert: \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs28\cf4 {\pntext\f1\'b7\tab}Wiener(e, N, x), d \par \pard\ri4\plain\f5\fs22\cf2 \par \plain\f6\fs28\cf0 Es hat geklappt!!! \par \plain\f5\fs22\cf4 \par \plain\f5\fs20\cf0\b _______________________________________________________________________________ \par \plain\f5\fs22\cf2 \par \plain\f3\fs22\cf2\b \'dcbungen: \par \plain\f3\fs20\cf2\b 1. \plain\f3\fs20\cf2 Testen Sie die Wiener Attacke 3mal, wobei jedes Mal neue \plain\f3\fs20\cf2\i p\plain\f3\fs20\cf2 , \plain\f3\fs20\cf2\i q\plain\f3\fs20\cf2 , \plain\f3\fs20\cf2\i d\plain\f3\fs20\cf2 , \plain\f3\fs20\cf2\i e\plain\f3\fs20\cf2 und \plain\f3\fs20\cf2\i x\plain\f3\fs20\cf2 generiert werden.\plain\f3\fs20\cf2\b \par 2.\plain\f3\fs20\cf2 Machen Sie sich mit der Funktion \plain\f5\fs20\cf4 time\plain\f3\fs20\cf2 bekannt (s. ?time) und bestimmen Sie die Laufzeiten des \par \plain\f3\fs20\cf5 ss\plain\f3\fs20\cf2 Angriffes von Wiener. \par \plain\f3\fs20\cf2\b 3.\plain\f3\fs20\cf2 Versuchen Sie \plain\f3\fs20\cf2\i N\plain\f3\fs20\cf2 mit Hilfe der Funktion \plain\f5\fs20\cf4 ifactor\plain\f3\fs20\cf2 zu faktorisieren.\plain\f3\fs20\cf3 \par \plain\f5\fs20\cf0\b _______________________________________________________________________________ \par \plain\f3\fs22\cf0 \par \plain\f3\fs22\cf1\b Anmerkungen:\plain\f3\fs22\cf1 \par \plain\f3\fs20\cf1\b 1. \plain\f3\fs20\cf1 Unter \plain\f3\fs20\cf4 www.mupad.de/schule+studium/material/\plain\f3\fs20\cf1 befinden sich weitere Notebooks, die sich mit dem Thema \par \plain\f3\fs20\cf5 ss\plain\f3\fs20\cf1 RSA besch\'e4ftigen. \par \plain\f3\fs20\cf4 \par \plain\f3\fs20\cf1\b 2.\plain\f3\fs20\cf4 \plain\f3\fs20\cf1 Weitere Anregungen finden Sie in der Buchreihe \plain\f3\fs20\cf4 Mathematik 1 x anders\plain\f3\fs20\cf1 . In dieser Reihe wird eine Vielzahl \par \plain\f3\fs20\cf5 ss\plain\f3\fs20\cf1 unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die B\'fccher k\'f6nnen unter \par \plain\f3\fs20\cf5 ss\plain\f4\fs20\cf2 www.schule.mupad.de/literatur\plain\f3\fs20\cf1 kostenfrei kopiert werden.\plain\f3\fs20\cf4 \par \plain\f5\fs20\cf0\b _______________________________________________________________________________ \par \par \par \plain\f5\fs22\cf4 \par }