{VERSION 6 0 "IBM INTEL NT" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "MS Sans Serif" 1 8 128 0 128 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "Roter Text" -1 256 "Tahoma" 0 0 255 0 0 1 2 1 1 0 0 2 0 0 0 0 }{CSTYLE "" -1 257 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 10 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "R3 Font 0 " -1 256 1 {CSTYLE "" -1 -1 "Helvetica" 1 9 128 0 128 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "R3 Font 2" -1 257 1 {CSTYLE "" -1 -1 "Courier" 1 8 0 128 128 1 1 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Seitenumbruch" -1 258 1 {CSTYLE "" -1 -1 "Times" 1 10 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 1 2 0 1 }{PSTYLE "Normal" -1 259 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 260 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 3" -1 261 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 1 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 262 1 {CSTYLE "" -1 -1 "Times" 1 10 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 263 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "R3 Font 0" -1 264 1 {CSTYLE "" -1 -1 "Helvetica" 1 10 128 0 128 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "R3 Font 2" -1 265 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 128 128 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "rsa.mws zuletzt aktual isiert: 14. Juni 2004" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 257 81 "Ein Beispiel zur RSA-Verschl\374sselung, wie sie in d er Vorlesung beschrieben wurde." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 89 "Zuerst mu\337 man die Konversion Text - -> Dezimalzahl und umgekehrt \"automatisieren\"." }}{PARA 0 "" 0 "" {TEXT -1 62 "Die geschieht mit Hilfe der Prozeduren Text_Zahl, Za hl_Text." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 43 "Dabei wird das folgende Alfabet benutzt:" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 8 "restart:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 113 "Alphabet := `a\344bcdefghijklmno\366pqrs\337tu\374vwxyzA\304BCDEFGHIJ KLMNO\326PQRSTU\334VWXYZ1234567890-=~!@%^&*()_+,./<'>?;:\"[]\{\}| `;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 " length(Alphabet);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "Das sind 98 Zeichen inklusive der unsicht baren Leestelle am Ende." }}{PARA 0 "" 0 "" {TEXT -1 140 "F\374r einen Computer und f\374r die Mathematik, die wir benutzen wollen, sind Zah len besser geeignet, als so seltsame Buchstaben, wie etwa: @ . " }} {PARA 0 "" 0 "" {TEXT -1 149 "Deswegen bauen wir uns einen Text-Zahl-W andler, der jedem Zeichen des obigen Alphabets in aufsteigender Reihen folge eine Zahl von 01 bis 98 zuordnet." }}{PARA 0 "" 0 "" {TEXT -1 42 "Achten Sie auf die Zahl 98 (=Leerstelle) !" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 "Die folgenden beiden Konv ersionsprozeduren brauchen nur aktiviert zu werden:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 349 "Text_Zahl:=proc (st, string) local ll, n n, ss, ii; global Alphabet; ll := length(st); if ll = 0 then RETURN(0) fi; nn := 1; for ii to ll do ss := SearchText(substring(st,ii .. ii), Alphabet); if not type(ss,numeric) or ss = 0 then ERROR(`Das Zeichen ` ||(substring(st,ii .. ii))||` geh\366rt nicht zum Alphabet`) fi; nn := 100*nn+ss od; nn-10^(2*ll) end:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 340 "Zahl_Text:=proc (nn) local ss, mm, ll, pp, ii, ans; global Alphab et; mm := nn; ll := floor(1/2*trunc(evalf(log10(mm))))+1; ans := ``; f or ii to ll do mm := iquo(mm,100,'pp'); if length(Alphabet) < pp then \+ ERROR(`Der eigegebenen Zahl entspricht kein vern\374nftiger Text`) fi; ss := substring(Alphabet,pp .. pp); ans := cat(ss,ans) od; ans end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 377 "Im Folgenden ist der Modul q :=9991 so gew\344hlt, dass mit obigem Alphabet jeweils Buchstabenpaar e verschl\374sselt werden k\366nnen. Die einem Buchstabenpaar entspre chende Dezimalzahl ist dabei stets < 9899 . Beachte: Obwohl die bei der Verschl\374sselung entstehenden 4-stelligen Dezimalzahlen nicht a lle teilerfremd zu q sind, ist die Verschl\374sselung eindeutig (---> Vorlesung)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "Der zu verschl\374sselnde Text sei: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "Text:=`Treffpunkt um 10 Uhr 15`;Z:=Text_Zahl(Text);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "#Text:=Alphabet;Z:=Text_Z ahl(Text);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "Diese stets gradest ellige Dezimal zahl wird in Viererbl\366cke aufgeteilt:" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 6 "ZZ:=Z:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "lZ :=length(ZZ):ll:=ceil(lZ/4):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "K:=[ ]: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "for ii to ll do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 " ZZ:=ZZ/(10^4): pp:=10 ^4*frac(ZZ): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 50 " \+ K:=[pp,op(K)]; ZZ:=trunc(ZZ): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "'K'=K;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 106 "Der Modul q, seine Primzerlegung, phi(q), \+ der Exponent s und sein Inverses t mod phi(q)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 "\326ffentlich bek annt sind : q und s " }}{PARA 0 "" 0 "" {TEXT -1 72 "s ist hi er im Beispiel so gew\344hlt, dass am Ende t recht klein ist." }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "q:=9991;" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 14 "ifactor(9991);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "phi_q:=numtheory[phi](q);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 28 "#randphi:=rand(1...phi_q-1):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "#s:=randphi();igcd(phi_q,s);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "s:=4451;igcd(phi_q,s);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "t:=s&^(-1) mod phi_q;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "Verschl\374sselung mit s, q :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "Ks:=[]: for i to nops(K) do Ks:=[op(Ks),K[i]&^s mod q ]; od:Ks;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "Entschl\374sselung m it t, q :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "Kst:=[]: for i to n ops(K) do Kst:=[op(Kst),Ks[i]&^t mod q]; od:Kst;" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 51 "Man sieht schon mit blo\337em Auge (?), da\337 \+ Kst=K." }}{PARA 0 "" 0 "" {TEXT -1 50 "Die R\374ck\374bersetzung in l esbaren Text geht z.B. so:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "ZB:=0 :ii:=nops(Kst): for i to ii do ZB:=ZB+Kst[i]*10^(4*(ii-i));od:ZB;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "Zahl_Text(ZB);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 16 "Automatisierung:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 97 "RSA:=proc(q,s,K) local Ks, i;\nKs:=[]: for i to nops( K) do Ks:=[op(Ks),K[i]&^s mod q]; od:Ks;\nend:" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 51 "Zahl_Block:=proc(Z) local ll,K,pp,lZ,ZZ,ii,i;Z Z:=Z:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "lZ:=length(ZZ):ll:=ceil(lZ /4):K:=[ ]: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "for ii to ll do ZZ :=ZZ/(10^4): pp:=10^4*frac(ZZ): K:=[pp,op(K)]; ZZ:=trunc(ZZ): od:end: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 108 "Block_Zahl:=proc(K) local i,ii ,ZB;ZB:=0:ii:=nops(Kst): for i to ii do ZB:=ZB+Kst[i]*10^(4*(ii-i));od :ZB;end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 6 "Probe:" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 15 "Ks:=RSA(q,s,K);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 134 "Damit kann man nun leichter auch mal eine Zweiwegverschl \374sselung ausrechnen, die dazu f\374hrt, dass jeder genau weiss von \+ wem was kommt:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "s2:=2051; igcd(phi_q,s2);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "t2:=s2&^(-1) mod phi_q;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "K;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 137 "Ich verschl\374ssele zuerst mit t2, was \+ nur mir bekannt ist. s2 ist \366ffentlich und jeder kann so fesstellen , ob die Nachricht von mir kommt:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "K_t2:=RSA(q,t2,K);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 69 "Dann ve rschl\374ssele ich mit s, was vom Empf\344nger ver\366ffentlicht wurde :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "K_t2_s:=RSA(q,s,K_t2);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 109 "Nun kann der Empf\344nger sein ei genes t und dann mein \366ffentliches s2 anwenden oder in umgekehrter \+ Reihenfolge:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "RSA(q,s2,RS A(q,t,K_t2_s));" }}{PARA 0 "" 0 "" {TEXT -1 4 "oder" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "RSA(q,t,RSA(q,s2,K_t2_s));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "Das Ergebnis ist in beiden F\344llen gleich:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Zahl_Text(Block_Zahl(%));" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Wie w\344re es, wenn wir verschied ene q benutzt h\344tten ??" }}}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }