{VERSION 5 0 "IBM INTEL NT" "5.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 "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 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 "Heading 2" -1 4 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 2 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" -1 18 1 {CSTYLE " " -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 8 "El Gamal" }}{PARA 19 "" 0 "" {TEXT -1 36 "\251Mike May, S.J., 2002, maymk@slu.edu" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 128 "This worksheet walks through the use of \+ El Gamal, both as a public key cryptographic system and as a means of \+ signing documents." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restar t;" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 38 "Basic El Gamal for message encryption." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "To set up El Gamal we want to choose a large prime and a generator." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 33 "p := nextprime(rand(1..10^35)());" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"D(ztIjV.F$p56K\"3p'>u#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "p := 274196690813211106932703436330 73797;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"D(ztIjV.F$p56K\"3p'> u#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "p = " }{XPPEDIT 18 0 "274196 69081321110693270343633073797.;" "6#-%&FloatG6$\"D(ztIjV.F$p56K\"3p'>u #\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "In order to find a gene rator, we want to factor p-1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "ifactor(p-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*()-%!G6#\"\"#F (\"\"\"-F&6#\"#BF)-F&6#\"Bj!H7c^o#\\s2(=8))R!)HF)" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 50 "We see that p-1 has 3 primes in its factorization. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "q1 := 2: q2 := 23: q3 : = 298039881318707724926851561229063:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 114 "To test if x is a generator, we check that the order of x does not divide (p-1)/q for each prime q that factors p." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 100 "gentest := x ->\n [Power(x,(p-1)/q1) m od p, Power(x,(p-1)/q2) mod p, \n Power(x,(p-1)/q3) mod p]:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "gentest(2);\ngentest(3);\nge ntest(5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"D'ztIjV.F$p56K\"3p'>u #\"CLGCZKfKyH,)o_E0T#[\"='*o\\'f*4@:9d,w^\\" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"D'ztIjV.F$p56K\"3p'>u#\"C'>9Q-\"4\"zjc%ps^(=gA(\"D4 )yR4Zcf)f*[cp(3hOZ\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"D'ztIjV.F$ p56K\"3p'>u#\"CY2_JHTWtK$)=Eq-l\"f&\"CcT_L%fRlm4!\\cO[MDa" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "Thus we see that 2, 3, and 5 are generato rs of Z_p. Let alpha = 5." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "alpha := 5;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&alphaG\"\"&" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "Now we choose a secret exponent a, and compute beta = alpha^a. and publish (p, alpha, beta)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "a := rand(10..p-10)();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG\"CAjd\"*\\!4QLpd*4\"=p<7)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "a := 812176918109957693338090499157 6322;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG\"CAjd\"*\\!4QLpd*4\"=p <7)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "beta := Power(alpha, a) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%betaG\"Dm'*fa%e41o<@- `*p+2z\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "We now publish our pu blic key, [p, alpha, beta]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "publicKey := [p, alpha, beta];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%*publicKeyG7%\"D(ztIjV.F$p56K\"3p'>u#\"\"&\"Dm'*fa%e41o<@-`*p+2z\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 137 "To send the message \"fred\", \+ Bob first turns the message into a number. (He uses the simple rule t urning a to 01, b to 02, ..., z to 26.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "message := 6180504;" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%(messageG\"(/0='" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Bob then \+ randomly chooses k1 and computes r1 and t1 which are sent to us" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "k1 := rand(10..p-10)();" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#k1G\"C`,as1E)\\GM'=S/IbUY" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "k1 := 4642553004401863428498 260672540153;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#k1G\"C`,as1E)\\GM' =S/IbUY" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "r1 := Power(alph a,k1) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#r1G\"C&yl?p3/-qE09' )4/=!f" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "t1 := (Power(beta ,k1) mod p)*(message) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#t1G \"CnAX(zk')=\"[yMrq0!o&>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "sent := [r1,t1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%sentG7$\"C&yl? p3/-qE09')4/=!f\"CnAX(zk')=\"[yMrq0!o&>" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "We decrypt in the usual fashon and recogn1ze the message \+ as fred." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "received := sen t[2]*(Power(1/sent[1],a) mod p) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)receivedG\"(/0='" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 31 "El Gamal for digital signatures" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "S uppose instead of receiving the mesage fred in secret, we want to send the message \"fred\" signed." }}{PARA 0 "" 0 "" {TEXT -1 44 "Recall t he public key and the private key a." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "myTotKey := [p, alpha, beta, a];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%)myTotKeyG7&\"D(ztIjV.F$p56K\"3p'>u#\"\"&\"Dm'*fa%e41 o<@-`*p+2z\"\"CAjd\"*\\!4QLpd*4\"=p<7)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 21 "We choose a random k2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "k2 := rand(10..p-10)();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#k2G\"Cn^\\#)>.cVBB)*e8A(*[_" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "k2 := 5248972213589823234356031982495167;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#k2G\"Cn^\\#)>.cVBB)*e8A(*[_" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 79 "We want k2 to be relatively prime to p-1, so we find the gcd and divide it out." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "comFact := igcd(k2, p-1);\nk2 := k2/comFact;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%(comFactG\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#k2G\"Cn^\\#)>.cVBB)*e8A(*[_" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "Compute r2 and s2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "r2 := Power(alpha, k2) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#r2G\"C.7$\\>`>#f'yU`a/(z%R(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "s2 := (message - r2*a)/k2 mod (p-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#s2G\"D%fKZJeRhYQN=:6pJ7C" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "I send (message, r2, s2)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "signed := [message,r2, s2];" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%'signedG7%\"(/0='\"C.7$\\>`>#f'yU`a/ (z%R(\"D%fKZJeRhYQN=:6pJ7C" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "To \+ verify, I compute v1 and v2 and see they are the same." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 84 "v1 := (Power(beta,signed[2]) mod p) *\n (Power(signed[2],signed[3]) mod p) mod p;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%#v1G\"Do4`FH#)H&RaP5'p,N6i#" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 34 "v2 := Power(alpha, message) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G\"Do4`FH#)H&RaP5'p,N6i#" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 30 "Finding elements of high order" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 487 "There is an obvious catch if the use of \+ El Gamal as described above. To find a generator of Z_p, we need to f actor p-1. But for El Gamal to be secure p should be big enough that \+ factoring p-1 is not a tractible problem. To fix this problem, it sho uld be noted that we don't really need a generator, we simply need an \+ element of large order. A solution is to collect the small factors of p-1. Anything raised to that power will have an order diving the rem aining large factor of p-1." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "Co nsider how this works with a prime of 200 digits." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 34 "p := nextprime(rand(1..10^200)());" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"pG\"cwT*4NZXowLH)fnu$*4g(>7)*31gsK(4^Ga_ 4Pn#RHkYj2fb\")>2j[Yh3IN0^*\\t%\\i?zI&RJSkh%>qu`k\"zX?H\"e3M))\\g\\nr0 V)3gTfp\"RqX!\\z" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 205 "p:= 79 4904570391695941600884305716749604988340858129204579164537470194616440 3139530792062494734995105353008614648630719815559076346642939267370952 5428510973272600608981219760099374675982933766845473509941:" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "We first find the product of prime s less than 1000. These will be the small factors we eliminate." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 126 "smallPrimes := 2:\ntest := \+ 2:\nwhile (test < 1000) do\ntest := nextprime(test):\nsmallPrimes := s mallPrimes*test:\nod:\nsmallPrimes;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6 #\"^el!>Vg9i(QkIZ.Mm&QJ%=)G2nG())GZ%H,z?bjj-9h6kS2#Q0\"pH1%f6T\"))*pZ) )R\")p*pfx!Q5aH,vkn8q%f,eM+.m=ET#3j[7A4ML$35P(GeAxv+OHn@\\656Fn5uw'3y\\*GFKJ%Q Hpx[v*y`sY5U\")3RbZQ-*>xqQ9#=vS!3r`mw>" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "Using the gcd, we remove all the small prime factors of p -1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 121 "k := p-1:\ncomFact \+ := igcd(smallPrimes, k):\nwhile (comFact > 1) do\nk := k/comFact;\ncom Fact := igcd(smallPrimes, k):\nod:\nk;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#\"[w*z&\\T!\\s)*>%HJG_R88PV@e_BD1)Rn[c>M&)=$)H73@j)p(fg?X.(>qP,( HiU0uW%p@KXxw!o\"3Y=q\"G@rL\")H[.jk`iC*3a()[nEmwEEf " 0 "" {MPLTEXT 1 0 26 "removedFactors := (p-1)/k;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%/removedFactorsG\"*g!Qm8" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "Now any element x^removedFactors will hav e order dividing k, " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "alp ha := Power(2, removedFactors) mod p;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&alphaG\"cw')QQ080\"ze&Rgdc8*))4a^60NRA!z%fV\"H-S4Fz%fv6,#H\"G)>7 pAm\">7AWG)R3z)G'G$[mT>X4.Ag!))RXkRBZW['HmO2\"\\dov'=ZM0qE@eLq/v'" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "With high probability, alpha has o rder k." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }