{VERSION 4 0 "HP RISC UNIX" "4.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 2 2 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 }{PSTYLE "Normal " -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "Helvet ica" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 258 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1 -1 "Helvetica" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 260 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 261 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 262 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 263 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 0 264 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 265 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 266 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 267 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 268 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 269 1 {CSTYLE " " -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 270 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT -1 20 "Diskrete Logarithmen" } {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "restart : with(numtheory):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 141 "plot ([seq([i, mlog(i, 55, 101)], i=1..100)], thickness=3,\ntitle=\"Der dis krete Logarithmus mod 101 zur Basis 55\",\ntitlefont=[HELVETICA, 24]); " }}}{EXCHG {PARA 259 "" 0 "" {TEXT -1 26 "Beispiel zu Diffie-Hellman " }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 257 "" 0 "" {TEXT -1 450 "Fuer re alistische Anwendungen sind Primzahlen mit mindestens 1024 Bit erforde rlich. Die Variable N gibt an, mit wieviel Bit wir arbeiten; je nach G eschwindigkeit des verwendeten Rechners kann sie auch gr\366\337er ode r\nkleiner gew\344hlt werden. Bei N=1024 oder 2048 dauert das Warten a uf die Primzahl einige Minuten, ansonsten funktioniert alles immer noc h recht flott. Bei N =512 geht alles ziemlich schnell - es sei denn, I hr Rechner ist schon sehr betagt." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "N := 1024;" }}}{EXCHG {PARA 270 "" 0 "" {TEXT -1 177 "Zufallszahle n werden (obwohl man das bei einer realistischen kryptographischen Anw endung auf keinen Fall so machen d\374rfte) mit dem linearen Kongruenz generator von Maple erzeugt:" }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 110 "### WARNING: persistent store makes one-argument rea dlib obsolete\nreadlib(rand): Zufallszahl := rand(2^(N-1));" }}} {EXCHG {PARA 269 "" 0 "" {TEXT -1 72 "naechstePrimzahl(m) berechnet fu er m > 42 die kleinste Primzahl p mit " }{XPPEDIT 18 0 "m <= p;" "6# 1%\"mG%\"pG" }{TEXT -1 179 ". Fuer gro\337e Werte von m ist diese Funk tion erheblich effizienter als die Standardfunktion nextprime von Mapl e; sie kann allerdings in seltenen Faellen auch ergebnislos abbrechen. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 622 "naechstePrimzahl := proc(m)\nl ocal n, p, a, i, j, Sieblaenge, prim;\nSieblaenge := 10*ceil(ln(m));\n p := 2:\nif (m mod 2) = 0 then n := m+1 else n := m fi;\nfor j from 0 \+ to Sieblaenge do prim[j] := true; od:\nfor i from 1 to Sieblaenge whil e p < Sieblaenge do\n p := nextprime(p):\n a := p - (n mod p); if a = \+ p then a := 0 fi;\n if (a mod 2) = 1 then a := (a+p)/2 else a := a/2; \+ fi;\n for j from a by p while j < Sieblaenge do\n prim[j] := false; \nod: od:\n\nfor j from 0 to Sieblaenge do\n if prim[j] then \n if 1 3 &^(n+2*j-1) mod (n+2*j) = 1 then\n if isprime(n+2*j) then return(n+ 2*j) fi\n else prim[j] := false\n fi: fi:\nod:\nend:" }}}{EXCHG {PARA 258 "" 0 "" {TEXT -1 221 "Wahl einer zuf\344lligen Primzahl p: D ies ist der aufwendigste Schritt, er mu\337 allerdings nur selten durc hgef\374hrt werden, die p bei diesem Verfahren \366ffentlich bekannt s ein darf und somit beliebig oft verwendet werden kann. " }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "p := naechstePrimzahl(2^(N -1) + Zufallszahl());" }}}{EXCHG {PARA 263 "" 0 "" {TEXT -1 63 "Wahl e iner weiteren Zufallszahl a als Basis der Exponentiation:" }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "a := Zufallszahl();" }}} {EXCHG {PARA 260 "" 0 "" {TEXT -1 11 "Teilnehmer " }{TEXT 256 2 "A " } {TEXT -1 43 "w\344hlt eine Zufallszahl u, die nur er kennt:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "u := Zufallszahl(); " }}}{EXCHG {PARA 261 "" 0 "" {TEXT -1 16 "Auch Teilnehmer " }{TEXT 257 2 "B " }{TEXT -1 43 "w\344hlt eine Zufallszahl v, die nur er kennt:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "v := Zufallszahl();" }}}{EXCHG {PARA 262 "" 0 " " {TEXT -1 2 "A " }{TEXT 258 10 "berechnet " }{XPPEDIT 18 0 "`mod`(a^u ,p);" "6#-%$modG6$)%\"aG%\"uG%\"pG" }{TEXT 261 54 " und schickt diese \+ Zahl ueber die unsichere Leitung an" }{TEXT -1 1 " " }{TEXT 260 1 "B" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "x := a &^u mod p;" }}}{EXCHG {PARA 264 "" 0 "" {TEXT -1 2 "B " }{TEXT 259 11 "berechnet " }{XPPEDIT 18 0 "`mod`(a^v,p);" "6#-%$modG6$)%\"aG%\"v G%\"pG" }{TEXT 262 55 " und schickt diese Zahl ueber die unsichere Lei tung an " }{TEXT -1 1 "A" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "y := a \+ &^ v mod p;" }}}{EXCHG {PARA 265 "" 0 "" {TEXT -1 29 "Der gemeinsame S chl\374ssel ist " }{XPPEDIT 18 0 "`mod`(a^(u+v),p);" "6#-%$modG6$)%\"a G,&%\"uG\"\"\"%\"vGF*%\"pG" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "Schlu essel := a &^ (u+v) mod p;" }}}{EXCHG {PARA 266 "" 0 "" {TEXT -1 92 "I n dieser Form kann ihn allerdings niemand berechnen, da niemand sowohl u als auch v kennt. " }{TEXT 263 2 "A " }{TEXT -1 57 "kennt aber u un d y und berechnet den Schl\374ssel daher als " }{XPPEDIT 18 0 "y^u = ( a^v)^u;" "6#/)%\"yG%\"uG))%\"aG%\"vGF&" }{MPLTEXT 1 0 0 "" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 13 "y &^ u mod p;" }}}{EXCHG {PARA 267 "" 0 "" {TEXT -1 2 "B " }{TEXT 264 0 "" }{TEXT 265 0 "" }{TEXT 266 28 "kennt v und x; er berechnet " }{XPPEDIT 18 0 "x^v = (a^u)^v;" "6#/)%\"xG%\"vG ))%\"aG%\"uGF&" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "x &^ v mod p;" }} }{EXCHG {PARA 268 "" 0 "" {TEXT -1 430 "Ein Lauscher kennt a, p, x, y, aber so lange er daraus nicht u oder v berechnen kann, n\374tzt ihm d as nichts. Zur Berechnung von u oder v m\374\337te der den diskreten L ogarithmus von x oder y zur Basis a berechnen, was f\374r hinreichend \+ gro\337e N nach derzeitigem Stand der Dinge nicht realistisch ist. Die folgende Laufanweisung berechnet einige diskrete Logarithmen f\374r i mmer gr\366\337ere Zahlen, um so ein Gef\374hl f\374r den Aufwand zu v ermitteln:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 177 "for i from 5 to 15 d o\np := nextprime(10^i); a := primroot(p);\nprintf(\"Berechne den disk reten Logarithmus von 100 zur Basis %d modulo %d ...\\n\",\na, p);\npr int(mlog(100, a, p))\nod:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "1 0 0" 8 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }