\mnb150<nb wrap="0" txtwidth="80" autowidth="0" pprint="1" typeset="1" xface="Times New Roman" xsize="280" xbold="0" xitalic="0" xcolor="#0000FF" slidents="1" sizemult="71" minsize="160" ifont="0 280 255 0 49 Courier New" ofont="0 280 16711680 0 49 Courier New" tfont="0 280 0 0 18 Times New Roman"></nb>ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fswiss\fprq2 Arial;}{\f4\fmodern\fprq1 Courier New;}{\f5\froman\fcharset1 Times New Roman;}{\f6\fswiss\fprq2\fcharset1 Arial;}{\f7\fmodern\fprq1\fcharset1 Courier New;}{\f8\fswiss\fprq2 Helvetica;}}
{\colortbl\red0\green0\blue0;\red255\green255\blue255;\red255\green0\blue0;\red0\green0\blue255;\red0\green128\blue0;}
\deflang1031\pard\ri4\plain\f4\fs20\cf0\b ________________________________________________________________________________
\par 
\par \plain\f4\fs20\cf0 Inhalt....: Diffie-Hellman-Algorithmus
\par Kategorie.: Arbeitsblatt
\par Mathematik: Kryptographie, Zahlentheorie
\par MuPAD.....: 3.0.0
\par Datum.....: 2003-06-23
\par Autoren...: Julia Faflek <faflek@mupad.de>
\par Funktionen: nextprime, ithprime, factor, numlib::primroot, numlib::order, 
\par Funktionen: powermod, igcd, random, plot::Point2d
\par \plain\f4\fs20\cf0\b ________________________________________________________________________________
\par \plain\f3\fs36\cf0\b 
\par \plain\f3\fs40\cf0\b Schl\'fcsselerzeugung mittels des Diffie-Hellman-
\par Algorithmus\plain\f3\fs36\cf0\b 
\par \plain\f3\fs22\cf0 
\par \plain\f3\fs24\cf4 Zum Ver- und Entschl\'fcsseln von Daten braucht man Schl\'fcssel. Mit dem hier vorgestellten 
\par Algorithmus werden Schl\'fcssel auf sicherem Wege generiert, um sp\'e4ter z.B. ein sym-
\par metrisches Kryptosystem zu verwenden.
\par \plain\f4\fs22\cf3 
\par 
\par \plain\f3\fs28\cf0 Wir wollen einen gemeinsamen Schl\'fcssel mit einer anderen Person ver-
\par einbaren. Dazu legen wir zun\'e4chst eine Primzahl p fest und eine Basis g
\par aller Elemente aus \plain\f3\fs28\cf0\i Z_p\plain\f3\fs28\cf0 , die ungleich 0 sind. Die Ordnung dieser Gruppe 
\par ist \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1 und ein Element erzeugt die Gruppe, wenn dessen Ordnung \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1 ist. 
\par \plain\f3\fs22\cf0 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab} p := nextprime(10)\plain\f3\fs28\cf2 
\par \pard\ri4\plain\f6\fs28\cf0 Das Problem, dass sich nun stellt ist: Wie finden wir einen Erzeuger dieser 
\par Gruppe? Falls \plain\f6\fs28\cf0\i p\plain\f6\fs28\cf0  klein genug ist, findet man das gew\'fcnschte Element \plain\f6\fs28\cf0\i x\plain\f6\fs28\cf0  fol-
\par genderweise: 
\par 
\par Man w\'e4hlt ein zuf\'e4lliges \plain\f6\fs28\cf0\i x\plain\f6\fs28\cf0  und \'fcberpr\'fcft, ob die Ordnung von \plain\f6\fs28\cf0\i x\plain\f6\fs28\cf0  nicht (\plain\f6\fs28\cf0\i p\plain\f6\fs28\cf0 -1)/\plain\f6\fs28\cf0\i q\plain\f6\fs28\cf0  
\par teilt f\'fcr jeden Primfaktor \plain\f6\fs28\cf0\i q\plain\f6\fs28\cf0  von \plain\f6\fs28\cf0\i p\plain\f6\fs28\cf0 -1, indem man \plain\f6\fs28\cf0\i x\plain\f6\fs28\cf0  mit (\plain\f6\fs28\cf0\i p\plain\f6\fs28\cf0 -1)/\plain\f6\fs28\cf0\i q\plain\f6\fs28\cf0  potenziert. Das 
\par Ergebnis muss immer ungleich 1 sein.
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}factor(p-1)
\par \pard\ri4\plain\f6\fs28\cf0 Wir versuchen es mit der 3:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}powermod(3, (p-1)/2, p);
\par \pard\li600\ri1\fi-300\plain\f4\fs28\cf2 powermod(3, (p-1)/5, p);
\par \pard\ri4\plain\f6\fs28\cf0 3 ist also kein erzeugendes Element. Zur Veranschaulichung lassen wir
\par alle Potenzen von 3 ausgeben:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}powermod(3, i, p) $ i = 1..p
\par \pard\ri4\plain\f6\fs28\cf0 
\par Die Ordnung von 3 modulo \plain\f6\fs28\cf0\i p\plain\f6\fs28\cf0  ist also 5. Man \'fcberpr\'fcft:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}numlib::order(3, p)
\par \pard\ri4\plain\f6\fs28\cf0 
\par Es ist also nicht so einfach ein erzeugendes Element zu finden. MuPAD
\par bietet mit der Funktion \plain\f7\fs28\cf2 numlib::primroot\plain\f6\fs28\cf0  ein Hilfsmittel an:
\par \plain\f4\fs22\cf3 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}numlib::primroot(p)
\par \pard\ri4\plain\f3\fs28\cf0 
\par Dieser Befehl liefert uns das kleinste Element mit Ordnung \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}numlib::order(2, p)
\par \pard\ri4\plain\f3\fs28\cf0 
\par Wir k\'f6nnen aber auch ein anderes Element w\'e4hlen, eins das gr\'f6\'dfer ist
\par als 2:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}numlib::primroot(3, p)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}numlib::order(6, p)
\par \pard\ri4\plain\f3\fs28\cf0 
\par Es gibt also meistens mehrere Kandidaten f\'fcr den Erzeuger.
\par 
\par Wenn aber \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0  zu gro\'df ist, dann versagt unsere bisherige Vorgehensweise.
\par Denn in der Praxis ist \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1 so gro\'df, dass das Faktorisieren von \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1 schwer 
\par ist. In diesem Fall muss man sich damit zufrieden geben, ein Element mit 
\par gro\'dfer Ordnung zu bekommen. Wir sammeln also zun\'e4chst alle kleinen 
\par Primfaktoren von \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1 und dividieren \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1 durch diese. \'dcbrig bleibt ein gro\'dfer 
\par Faktor von \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1. Nun wird jedes Element \plain\f3\fs28\cf0\i x\plain\f3\fs28\cf0  ^(Produkt entfernter Primfaktoren) 
\par mit gro\'dfer Wahrscheinlichkeit eine Ordnung haben, die den gro\'dfen Faktor 
\par teilt. Als erstes bilden wir das Produkt der ersten n Primzahlen: 
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}kleinePrim := proc(n)
\par \pard\li600\ri1\fi-300\plain\f4\fs28\cf2 begin
\par   _mult(ithprime(i) $ i = 1..n)
\par end_proc:
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}kleinePrim(10) = factor(kleinePrim(10));
\par \pard\li600\ri1\fi-300\plain\f4\fs28\cf2 
\par \pard\ri4\plain\f3\fs28\cf0 Mittels des ggT entfernen wir nun alle kleinen Primfaktoren von \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1 und 
\par lassen uns den \'fcbrig gebliebenen gro\'dfen Faktor sowie das Produkt der
\par entfernten Primfaktoren zur\'fcckgeben:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}entferneFaktoren := proc(p, n)
\par \pard\li600\ri1\fi-300\plain\f4\fs28\cf2    local grFaktor, gemFaktor, ProdFaktoren;
\par begin
\par    grFaktor := p-1:
\par    gemFaktor := igcd(kleinePrim(n), grFaktor):
\par    while (gemFaktor > 1) do
\par       grFaktor := grFaktor/gemFaktor:
\par       gemFaktor := igcd(kleinePrim(n), grFaktor):
\par    end_while:
\par    ProdFaktoren := (p-1)/grFaktor:
\par    return(grFaktor, ProdFaktoren):
\par end_proc:
\par \pard\ri4\plain\f6\fs28\cf0 
\par Wir erzeugen eine gro\'dfe Primzahl:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}p := nextprime(random(2^500..2^550)());
\par \pard\li600\ri1\fi-300\plain\f4\fs28\cf2 
\par \pard\ri4\plain\f6\fs28\cf0 
\par Nun wenden wir die obige Prozedur an und berechnen einen Erzeuger von der
\par Form \plain\f6\fs28\cf0\i x\plain\f6\fs28\cf0 ^(Produkt entfernter Faktoren), wobei \plain\f6\fs28\cf0\i x\plain\f6\fs28\cf0  beliebig gew\'e4hlt wird:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}Ergebnis := entferneFaktoren(p,100)
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}x := random(1..p)();
\par \pard\li600\ri1\fi-300\plain\f4\fs28\cf2 g := powermod(x, Ergebnis[2], p)
\par \pard\ri4\plain\f6\fs28\cf0 Wir \'fcberpr\'fcfen, ob \plain\f6\fs28\cf0\i g\plain\f6\fs28\cf0  die gew\'fcnschte Ordnung hat:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}powermod(g, Ergebnis[1], p)\plain\f4\fs22\cf2 
\par \pard\ri4\plain\f3\fs28\cf0 Nun haben wir alles zur Hand um mit dem eigentlichen Protokoll zu beginnen:
\par 1) \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0  und \plain\f3\fs28\cf0\i g\plain\f3\fs28\cf0  sind jeder Partei bekannt
\par 2) Wir w\'e4hlen einen geheimen Schl\'fcssel \plain\f3\fs28\cf0\i a\plain\f3\fs28\cf0  < \plain\f3\fs28\cf0\i p\plain\f3\fs28\cf0 -1
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}a := random(1..p-1)();
\par \pard\ri4\plain\f6\fs28\cf0 
\par 3) Wir berechnen Alpha und schicken dies an die andere Partei
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}Alpha := powermod(g, a, p)
\par \pard\ri4\plain\f3\fs28\cf0 
\par 4) Von  der anderen Partei erhalten wir ein Beta, das auf die gleiche Weise 
\par \plain\f3\fs28\cf1 ss\plain\f3\fs28\cf0 erzeugt wurde
\par \plain\f4\fs22\cf2 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}b := random(1..p-1)()
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}Beta := powermod(g, b, p)
\par \pard\ri4\plain\f3\fs28\cf0 
\par 5) Nun berechnen wir mit der Exponentialfunktion einen gemeinsamen Schl\'fcssel 
\par \plain\f3\fs28\cf1\i ss\plain\f3\fs28\cf0\i k\plain\f3\fs28\cf0  wie folgt:
\par \plain\f4\fs22\cf3 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}k1 := powermod(Beta, a, p)
\par \pard\ri4\plain\f4\fs20\cf0\b 
\par \plain\f3\fs28\cf0 
\par 6) Die andere Partei geht wie folgt vor:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}k2 := powermod(Alpha, b, p)
\par \pard\ri4\plain\f6\fs28\cf0 Schon hier sehen wir, dass beide Parteien wirklich gleiche Schl\'fcssel erzeugt
\par haben. Warum ist das so? Wir erinnern uns daran wie Beta erzeugt wurde:
\par \pard\li2500\ri4\plain\f4\fs22\cf3 {\pict\wmetafile8\picw6223\pich974\picscaley99\picwgoal3528\pichgoal553
010009000003F403000009001C0000000000050000000B0200000000050000000C02CE034F1803
0000001E00050000000C02D1034F18050000000B0200000000030000001E00050000000C02DA03
4F18050000000B0200000000050000000B0200000000030000001E00050000000C02DC034F1805
0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000
0C02E5034F18050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000030000001E00050000000C02E8034F18050000000B0200000000050000000B02
00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E
00050000000C02F2034F18050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005
0000000C02FE034F18050000000B0200000000050000000B0200000000050000000B0200000000
050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000
00030000001E00050000000C0209044F18050000000B0200000000050000000B02000000000500
00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005
0000000B0200000000050000000B0200000000030000001E00050000000C020B044F1805000000
0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500
00000B0200000000030000001E00030000001E00050000000C024B02C80D050000000B02000000
00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200
000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C00
0000FB0238FF00000000000090010000000107000000417269616C000000840D0A0B7CE81200D8
9FF177E19FF1772020F377160E6677040000002D01010005000000020101000000050000000102
FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB02E8
FE00000000000090010000000107000000417269616C0000001C0C0ACE7CE81200D89FF177E19F
F1772020F377160E6677040000002D0102000B00000026060F000C004D6174685479706500007F
001C000000FB023AFF00000000000090010100000107000000417269616C000000CF0C0A727CE8
1200D89FF177E19FF1772020F377160E6677040000002D0103001C000000FB02E8FE0000000000
0090010100000107000000417269616C000000390E0A407CE81200D89FF177E19FF1772020F377
160E6677040000002D010400040000002D010200040000002D010400040000002D0103001C0000
00FB02E8FE000000000000900100000002070000005346204D61746820457874007CE81200D89F
F177E19FF1772020F377160E6677040000002D010500040000002D010200040000002D01050004
0000002D010200040000002D010500040000002D010300040000002D010400040000002D010200
1C000000FB02E8FE0000000000009001000000020700000053796D626F6C0000D00D0AB97CE812
00D89FF177E19FF1772020F377160E6677040000002D010600040000002D010200070000002105
01004200AC01640007000000210501006500AC011F0107000000210501007400AC01BB01070000
00210501006100AC010902040000002D010300070000002105010061000801A502040000002D01
020007000000210501006D00AC01590307000000210501006F00AC014204070000002105010064
00AC01DE04040000002D01040007000000210501007000AC01C205040000002D01060007000000
210501003D00AC01B206040000002D010200040000002D010500040000002D010200040000002D
010500040000002D010200040000002D010500040000002D010200040000002D01050004000000
2D010200040000002D01050007000000210501002800AC01A007040000002D010200040000002D
01040007000000210501006700AC012008040000002D010300070000002105010062000801BD08
040000002D010500040000002D010200040000002D010500040000002D010200040000002D0105
0007000000210501002900AC012B09040000002D01030007000000210501006100E300AB090400
00002D01020007000000210501006D00AC015F0A07000000210501006F00AC01480B0700000021
0501006400AC01E40B040000002D01040007000000210501007000AC01C80C08000000FA020000
0000000000000000040000002D0107001C000000FB021000070000000000BC0200000000010202
2253797374656D0000A10B0A2E7CE81200D89FF177E19FF1772020F377160E6677040000002D01
0800040000002701FFFF04000000F001000004000000F001010004000000F001020004000000F0
01030004000000F001040004000000F001050004000000F0010600040000002701FFFF04000000
2701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000
002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF030000000000
}\plain\f4\fs22\cf3 
\par \pard\ri4\plain\f6\fs28\cf0 Mit einfachen Rechenregeln folgt:
\par \pard\li2500\ri4\plain\f4\fs22\cf3 {\pict\wmetafile8\picw5334\pich974\picscalex98\picscaley99\picwgoal3054\pichgoal553
0100090000030E0400000A001C0000000000050000000B0200000000050000000C02CE03D61403
0000001E00050000000C02D1030C15050000000B0200000000030000001E00050000000C02DA03
4415050000000B0200000000050000000B0200000000030000001E00050000000C02DC03451505
0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000
0C02E5037C15050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000030000001E00050000000C02E8037F15050000000B0200000000050000000B02
00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E
00050000000C02F203B615050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005
0000000C02FE03F115050000000B0200000000050000000B0200000000050000000B0200000000
050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000
00030000001E00050000000C0209042A16050000000B0200000000050000000B02000000000500
00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005
0000000B0200000000050000000B0200000000030000001E00050000000C020B042C1605000000
0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500
00000B0200000000030000001E00030000001E00050000000C024B02920C050000000B02000000
00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200
000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C00
0000FB0238FF00000000000090010000000107000000417269616C000000160E0A787CE81200D8
9FF177E19FF1772020F377A10B6630040000002D01010005000000020101000000050000000102
FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB02E8
FE00000000000090010000000107000000417269616C000000D00D0ABA7CE81200D89FF177E19F
F1772020F377A10B6630040000002D0102000B00000026060F000C004D6174685479706500007F
001C000000FB02E8FE00000000000090010100000107000000417269616C00000045070A517CE8
1200D89FF177E19FF1772020F377A10B6630040000002D0103001C000000FB023AFF0000000000
0090010100000107000000417269616C000000390E0A417CE81200D89FF177E19FF1772020F377
A10B6630040000002D0104001C000000FB02E8FE00000000000090010000000207000000534620
4D61746820457874007CE81200D89FF177E19FF1772020F377A10B6630040000002D0105000400
00002D010200040000002D010500040000002D010200040000002D010500040000002D01040004
0000002D010300040000002D010200040000002D0103001C000000FB023AFF0000000000009001
0000000107000000417269616C0000001C0C0ACF7CE81200D89FF177E19FF1772020F377A10B66
30040000002D010600040000002D010300040000002D0102001C000000FB02E8FE000000000000
9001000000020700000053796D626F6C0000840D0A0C7CE81200D89FF177E19FF1772020F377A1
0B6630040000002D010700040000002D010200040000002D010500040000002D01020004000000
2D010500040000002D010200040000002D010500040000002D010200040000002D010500040000
002D010200040000002D01050007000000210501002800AC016400040000002D01020004000000
2D01030007000000210501006700AC01E400040000002D01040007000000210501006200080181
01040000002D010500040000002D010200040000002D010500040000002D010200040000002D01
050007000000210501002900AC01EF01040000002D01040007000000210501006100E3006F0204
0000002D01020007000000210501006D00AC01230307000000210501006F00AC010C0407000000
210501006400AC01A804040000002D01030007000000210501007000AC018C05040000002D0107
0007000000210501003D00AC017C06040000002D010200040000002D0103000700000021050100
6700AC016A07040000002D01060007000000210501006100080107080700000021050100620008
017508040000002D01020007000000210501006D00AC01290907000000210501006F00AC01120A
07000000210501006400AC01AE0A040000002D01030007000000210501007000AC01920B080000
00FA0200000000000000000000040000002D0108001C000000FB021000070000000000BC020000
00000102022253797374656D00001A0B0A627CE81200D89FF177E19FF1772020F377A10B663004
0000002D010900040000002701FFFF04000000F001000004000000F001010004000000F0010200
04000000F001030004000000F001040004000000F001050004000000F001060004000000F00107
00040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701
FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400000027
01FFFF030000000000
}\plain\f5\fs22\cf0 
\par \plain\f4\fs22\cf3 {\pict\wmetafile8\picw5270\pich974\picscalex98\picscaley99\picwgoal3018\pichgoal553
0100090000030A0400000A001C0000000000050000000B0200000000050000000C02CE03961403
0000001E00050000000C02D103CD14050000000B0200000000030000001E00050000000C02DA03
0315050000000B0200000000050000000B0200000000030000001E00050000000C02DC03051505
0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000
0C02E5033B15050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000030000001E00050000000C02E8033E15050000000B0200000000050000000B02
00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E
00050000000C02F2037415050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005
0000000C02FE03AE15050000000B0200000000050000000B0200000000050000000B0200000000
050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000
00030000001E00050000000C020904E715050000000B0200000000050000000B02000000000500
00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005
0000000B0200000000050000000B0200000000030000001E00050000000C020B04E91505000000
0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500
00000B0200000000030000001E00030000001E00050000000C024B026C0C050000000B02000000
00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200
000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C00
0000FB0238FF00000000000090010000000107000000417269616C000000A10B0A317CE81200D8
9FF177E19FF1772020F3771A0B6664040000002D01010005000000020101000000050000000102
FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB02E8
FE00000000000090010000000107000000417269616C000000840D0A0D7CE81200D89FF177E19F
F1772020F3771A0B6664040000002D0102000B00000026060F000C004D6174685479706500007F
001C000000FB02E8FE00000000000090010100000107000000417269616C0000001C0C0AD07CE8
1200D89FF177E19FF1772020F3771A0B6664040000002D0103001C000000FB023AFF0000000000
0090010000000107000000417269616C000000CF0C0A747CE81200D89FF177E19FF1772020F377
1A0B6664040000002D010400040000002D010300040000002D010200040000002D0103001C0000
00FB023AFF00000000000090010100000107000000417269616C000000390E0A427CE81200D89F
F177E19FF1772020F3771A0B6664040000002D0105001C000000FB02E8FE000000000000900100
000002070000005346204D61746820457874007CE81200D89FF177E19FF1772020F3771A0B6664
040000002D010600040000002D010200040000002D010600040000002D010200040000002D0105
00040000002D010300040000002D0102001C000000FB02E8FE0000000000009001000000020700
000053796D626F6C0000D00D0ABB7CE81200D89FF177E19FF1772020F3771A0B6664040000002D
010700040000002D010200040000002D01030007000000210501006700AC016400040000002D01
040007000000210501006100080101010700000021050100620008016F01040000002D01020007
000000210501006D00AC01230207000000210501006F00AC010C0307000000210501006400AC01
A803040000002D01030007000000210501007000AC018C04040000002D01070007000000210501
003D00AC017C05040000002D010200040000002D010600040000002D010200040000002D010600
040000002D010200040000002D010600040000002D010200040000002D010600040000002D0102
00040000002D01060007000000210501002800AC016A06040000002D010200040000002D010300
07000000210501006700AC01D706040000002D0105000700000021050100610008017407040000
002D010600040000002D010200040000002D010600040000002D010200040000002D0106000700
0000210501002900AC01E207040000002D0105000700000021050100620008014F08040000002D
01020007000000210501006D00AC01030907000000210501006F00AC01EC090700000021050100
6400AC01880A040000002D01030007000000210501007000AC016C0B08000000FA020000000000
0000000000040000002D0108001C000000FB021000070000000000BC0200000000010202225379
7374656D0000160E0A797CE81200D89FF177E19FF1772020F3771A0B6664040000002D01090004
0000002701FFFF04000000F001000004000000F001010004000000F001020004000000F0010300
04000000F001040004000000F001050004000000F001060004000000F0010700040000002701FF
FF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701
FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0300000000
00
}\plain\f4\fs22\cf3 
\par \pard\ri4\plain\f6\fs28\cf0 Nun wissen wir:
\par \pard\li2500\ri4\plain\f4\fs22\cf3 {\pict\wmetafile8\picw5900\pich974\picscalex99\picscaley99\picwgoal3378\pichgoal553
010009000003F703000009001C0000000000050000000B0200000000050000000C02CE030C1703
0000001E00050000000C02D1034717050000000B0200000000030000001E00050000000C02DA03
8617050000000B0200000000050000000B0200000000030000001E00050000000C02DC03C31705
0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000
0C02E5030218050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000030000001E00050000000C02E8034218050000000B0200000000050000000B02
00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E
00050000000C02F2038118050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005
0000000C02FE03C318050000000B0200000000050000000B0200000000050000000B0200000000
050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000
00030000001E00050000000C0209040419050000000B0200000000050000000B02000000000500
00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005
0000000B0200000000050000000B0200000000030000001E00050000000C020B04051905000000
0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500
00000B0200000000030000001E00030000001E00050000000C024B022F0E050000000B02000000
00050000000B0200000000050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000050000000B0200
000000050000000B020000000008000000FA0200000000000000000000040000002D0100001C00
0000FB0238FF00000000000090010000000107000000417269616C0000001A0B0A657CE81200D8
9FF177E19FF1772020F377160E667B040000002D01010005000000020101000000050000000102
FFFFFF00050000002E01180000000500000009020000000004000000080100001C000000FB02E8
FE00000000000090010000000107000000417269616C000000D00D0ABC7CE81200D89FF177E19F
F1772020F377160E667B040000002D0102000B00000026060F000C004D6174685479706500007F
001C000000FB02E8FE00000000000090010100000107000000417269616C00000045070A537CE8
1200D89FF177E19FF1772020F377160E667B040000002D0103001C000000FB023AFF0000000000
0090010100000107000000417269616C000000390E0A437CE81200D89FF177E19FF1772020F377
160E667B040000002D0104001C000000FB02E8FE00000000000090010000000207000000534620
4D61746820457874007CE81200D89FF177E19FF1772020F377160E667B040000002D0105000400
00002D010200040000002D010500040000002D010200040000002D010400040000002D01030004
0000002D010200040000002D010400040000002D010300040000002D0102001C000000FB02E8FE
0000000000009001000000020700000053796D626F6C00001C0C0AD17CE81200D89FF177E19FF1
772020F377160E667B040000002D010600040000002D010200040000002D010500040000002D01
0200040000002D010500040000002D010200040000002D010500040000002D010200040000002D
010500040000002D010200040000002D01050007000000210501002800AC016400040000002D01
0200040000002D01030007000000210501006700AC01D100040000002D01040007000000210501
00610008016E01040000002D010500040000002D010200040000002D010500040000002D010200
040000002D01050007000000210501002900AC01DC01040000002D010400070000002105010062
0008014902040000002D01020007000000210501006D00AC01FD0207000000210501006F00AC01
E60307000000210501006400AC018204040000002D01030007000000210501007000AC01660504
0000002D01060007000000210501003D00AC015606040000002D01020007000000210501004100
AC01450707000000210501006C00AC01000807000000210501007000AC013E0807000000210501
006800AC01DA0807000000210501006100AC017609040000002D01040007000000210501006200
0801120A040000002D01020007000000210501006D00AC01C60A07000000210501006F00AC01AF
0B07000000210501006400AC014B0C040000002D01030007000000210501007000AC012F0D0800
0000FA0200000000000000000000040000002D0107001C000000FB021000070000000000BC0200
0000000102022253797374656D0000840D0A0E7CE81200D89FF177E19FF1772020F377160E667B
040000002D010800040000002701FFFF04000000F001000004000000F001010004000000F00102
0004000000F001030004000000F001040004000000F001050004000000F0010600040000002701
FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF0400000027
01FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF03000000
0000
}\plain\f4\fs22\cf2 
\par \pard\ri4\plain\f6\fs28\cf0 Die Frage ist, wie geheim ist denn der geheime Schl\'fcssel? Kann ein Angreifer 
\par den geheimen Schl\'fcssel berechnen? Kann dieser bei Kenntnis von Alpha bzw. 
\par Beta den Wert von \plain\f6\fs28\cf0\i a\plain\f6\fs28\cf0  bzw. \plain\f6\fs28\cf0\i b\plain\f6\fs28\cf0  herausfinden? Dazu m\'fcsste der Angreifer den 
\par diskreten Logarithmus von Alpha bzw. Beta zur Basis \plain\f6\fs28\cf0\i g\plain\f6\fs28\cf0  berechnen. Dies ist 
\par gl\'fccklicherweise nicht leicht m\'f6glich bei gro\'dfen Zahlen. Die Sicherheit dieses 
\par Protokolls basiert also auf der Eigenschaft, dass die diskrete Exponentialfunkt-
\par ion eine Einwegfunktion ist, d.h. leicht zu berechnen, aber schwer zu invertieren.
\par 
\par Um dies zu verdeutlichen schauen wir uns die Funktionswerte von \plain\f6\fs28\cf0\i g\plain\f6\fs28\cf0 ^\plain\f6\fs28\cf0\i x\plain\f6\fs28\cf0  mod \plain\f6\fs28\cf0\i p\plain\f6\fs28\cf0  an.
\par Dazu w\'e4hlen wir ein nicht zu gro\'dfes \plain\f6\fs28\cf0\i p\plain\f6\fs28\cf0  und einen Erzeuger \plain\f6\fs28\cf0\i g\plain\f6\fs28\cf0 :
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}p := nextprime(random(1000..2000)());
\par \pard\li600\ri1\fi-300\plain\f4\fs28\cf2 g := numlib::primroot(p)
\par 
\par \pard\ri4\plain\f3\fs28\cf0 
\par Nun wollen wir das ganze visualisieren:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f4\fs28\cf2 {\pntext\f1\'b7\tab}plot(plot::Point2d(i, powermod(g, i, p)) $ i = 1..p)
\par \pard\ri4\plain\f3\fs28\cf0 
\par In dieser Grafik k\'f6nnen wir keinerlei Muster erkennen. Es scheint als w\'fcrde 
\par sich die diskrete Exponentialfunktion zuf\'e4llig verhalten. Dies macht es be-
\par sonders schwer auf das Urbild zur\'fcck zu schlie\'dfen.
\par \plain\f4\fs22\cf3 
\par \plain\f4\fs20\cf0\b _____________________________________________________________________________________\plain\f4\fs22\cf2 
\par \plain\f4\fs22\cf3 
\par \plain\f3\fs22\cf3\b \'dcbungen: 
\par \plain\f3\fs20\cf3\b 1.\plain\f3\fs20\cf3  Machen Sie sich mit den Funktionen \plain\f4\fs20\cf2 numlib::order\plain\f3\fs20\cf3  und \plain\f4\fs20\cf2 numlib::primroot\plain\f3\fs20\cf3  vertraut. Besuchen Sie 
\par \plain\f3\fs20\cf1 ss\plain\f3\fs20\cf3 dazu die Hilfeseiten \plain\f4\fs20\cf2 ?numlib::order\plain\f3\fs20\cf3  und \plain\f4\fs20\cf2 ?numlib::primroot\plain\f3\fs20\cf3 .
\par \plain\f4\fs20\cf0\b _____________________________________________________________________________________
\par \plain\f3\fs22\cf0 
\par \plain\f3\fs22\cf4\b Anmerkungen:\plain\f3\fs22\cf4 
\par \plain\f3\fs20\cf4\b 1. \plain\f3\fs20\cf4 Unter \plain\f3\fs20\cf4\b\i www.schule.mupad.de/material/\plain\f3\fs20\cf4  befinden sich Notebooks, die sich ebenfalls mit 
\par \plain\f3\fs20\cf1 ss\plain\f3\fs20\cf4 Kryptographie besch\'e4ftigen. 
\par 
\par \plain\f3\fs20\cf4\b 2. \plain\f3\fs20\cf4 Weitere Anregungen finden Sie in der Buchreihe \plain\f3\fs20\cf2 Mathematik 1 x anders\plain\f3\fs20\cf4 . In dieser Reihe wird eine Vielzahl 
\par \plain\f3\fs20\cf1 ss\plain\f3\fs20\cf4 unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die B\'fccher k\'f6nnen unter 
\par \plain\f3\fs20\cf1 ss\plain\f8\fs20\cf3 www.schule.mupad.de/literatur\plain\f3\fs20\cf4  kostenfrei kopiert werden.
\par \plain\f3\fs20\cf2 
\par \plain\f4\fs20\cf0\b _____________________________________________________________________________________
\par 
\par 
\par }