{VERSION 4 0 "IBM INTEL LINUX" "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 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 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 8 2 0 0 0 0 0 0 -1 0 }{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 }} {SECT 0 {SECT 0 {PARA 3 "" 0 "" {TEXT -1 12 "Prime Fields" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 99 "Basic arithmetic operations work as usual , except that exponentiation should be written as follows " }}{PARA 0 "" 0 "" {TEXT -1 65 "to make it more efficient. (This only matters fo r large primes.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "2&^63 mod 71;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 100 "The function Prim itive(a(x)) mod p checks whether the polynomial a(x) is primitive. Th at is whether" }}{PARA 0 "" 0 "" {TEXT -1 102 "it is irreducible and a lso if you take Z_p[x]/a(x) the image of x is a primitive element of t he field." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 71 "In order to tell whether an integer a mod p is primitive use a(x) =x-a." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Primitive(x-2) mod 71;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Primitive (x-7) mod 71;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 39 "Creating an extension of a Prime Field" }}{PARA 3 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 197 "In this section we define the functions used to create \+ a finite field with p^d elements. We will use the Maple function GF w hich creates an array of functions and constants relevant to the field ." }}{PARA 0 "" 0 "" {TEXT -1 98 "I will illustrate them below. GF(p, d) chooses an irreducile polynomial, but I had trouble making " }} {PARA 0 "" 0 "" {TEXT -1 92 "the arithmetic work. So I use the versio n GF(p,d,f) where I choose f to be irreducible and " }}{PARA 0 "" 0 " " {TEXT -1 10 "primitive." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 86 "So we need to find a polynomial, f(T), which is i rreducible and of degree d over F_p." }}{PARA 0 "" 0 "" {TEXT -1 135 " We will also insist that the polynomial be primitive. That is, in the multiplicative group of F_p[T]/f(T), the order of T is p^d - 1." }} {PARA 0 "" 0 "" {TEXT -1 213 "You'll notice I check that degree(f)=d. \+ Randpoly(d,t) should produce a polynomial of degree d, but for some r eason when d>40 it sometimes returns a polynomial of lower degree. So I inserted the check to be sure." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 224 "GetIrrPoly := proc(p,d)\nlo cal bool, f;\n\nbool:=false;\nwhile bool = false do\n f:= Randpoly(d, T) mod p;\n if Irreduc(f) mod p and Primitive(f) mod p \n a nd (degree(f)= d) then bool :=true fi;\nod;\nRETURN(f);\nend proc;\n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%+GetIrrPolyGR6$%\"pG%\"dG6$%%boolG %\"fG6\"F,C%>8$%&falseG?(F,\"\"\"F2F,/F/F0C$>8%-%$modG6$-%)RandpolyG6$ 9%%\"TG9$@$33-F86$-%(IrreducG6#F6F?-F86$-%*PrimitiveGFGF?/-%'degreeGFG F=>F/%%trueG-%'RETURNGFGF,F,F," }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 18 "The field GF(2^50)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "p: =2; d:= 50;p := 2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "f := G etIrrPoly(p,d);\n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"fG,X\"\"\"F&* $)%\"TG\"#JF&F&*$)F)\"#MF&F&*$)F)\"#PF&F&*$)F)\"#SF&F&*$)F)\"#TF&F&*$) F)\"#YF&F&*$)F)\"#ZF&F&*$)F)\"#[F&F&*$)F)\"#@F&F&*$)F)\"#EF&F&*$)F)\"# FF&F&*$)F)\"#HF&F&*$)F)\"#AF&F&*$)F)\"#F&F&*$)F)\"\"$F&F&*$)F)\"#BF&F&*$ )F)\"#UF&F&*$)F)\"#=F&F&*$)F)\"#LF&F&*$)F)\"#8F&F&F)F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 155 "Next we use the Maple function GF to cre ate the field. GF returns an array of constants and functions that d o most of what we want with the finite field." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "FF:= GF(p,d ,f);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#FFG`69%\"+G%\"-G%\"*G%\"/G%\"^G%&inputG%'outputG%(in verseG%*extensionG%)variableG%(factorsG%%normG%&traceG%&orderG%'random G%%sizeG%3isPrimitiveElementG%1PrimitiveElementG%*ConvertInG%+ConvertO utG%%zeroG%$oneG%%initGb6#%+thismoduleG6\"FA69F'F(F)F*F+F,F-F.F/F0F1F2 F3F4F5F6F7F8F9F:F;F " 0 "" {MPLTEXT 1 0 23 "al := FF [ConvertIn](T);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#alGd&%\"TG\"\"#! \"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 96 "I find the Maple syntax for the field operations tedious to typ e, so I made pseudonyms for them." }}{PARA 0 "" 0 "" {TEXT -1 120 "I c hose to set Fzero := FF[zero] instead of using an alias. If you use a n alias Fmul(Fzero,al) will return Fzero not 0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 89 "alias( Fad d=FF[`+`], Fmul=FF[`*`], Fexp = FF[`^`] );\nFzero := FF[zero]; Fone := FF[one];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%%FaddG%%FmulG%%FexpG" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%&FzeroGd$%\"TG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%FoneGd%%\"TG\"\"#\"" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 15 "Fadd(Fzero,al);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# d&%\"TG\"\"#!\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "Fadd(Fon e,al);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#d&%\"TG\"\"#\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Fmul(Fzero, al);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#d$%\"TG\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 " Wow, it really works! And it does the following computation quickly, \+ so it thinks before it acts." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Fexp(al,2^50-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#d%%\"TG\"\"# \"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Fexp(al,111342347);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#dU%\"TG\"\"#!!\"!\"\"!\"\"!\"!!!!!\" \"\"!\"\"\"!\"\"!!\"!!!!!\"!!\"\"!!\"\"\"!!!!\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 7 "Amazing" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 94 "The next two concern primitive elements. The fir st produces a primitive element randomly. " }}{PARA 0 "" 0 "" {TEXT -1 61 "The second checks whether a given field element is primitive." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "FF[PrimitiveElement]();" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#dT%\"TG\"\"#\"\"!!\"\"!!\"!!!\"!!\"! \"\"!\"!!\"!\"!\"\"\"\"\"!!!\"!!!!!\"!\"\"\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "h:= Fadd(Fone,al);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"hGd&%\"TG\"\"#\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "FF[isPrimitiveElement](h);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 24 "The finite field GF(5^2)" } {MPLTEXT 1 0 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "H:= GF(5 ,2,T^2+T+1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"HG`69%\"+G%\"-G%\" *G%\"/G%\"^G%&inputG%'outputG%(inverseG%*extensionG%)variableG%(factor sG%%normG%&traceG%&orderG%'randomG%%sizeG%3isPrimitiveElementG%1Primit iveElementG%*ConvertInG%+ConvertOutG%%zeroG%$oneG%%initGb6#%+thismodul eG6\"FA69F'F(F)F*F+F,F-F.F/F0F1F2F3F4F5F6F7F8F9F:F;F " 0 "" {MPLTEXT 1 0 22 "gam:= H[ConvertIn](T);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$gamGd&%\"TG\"\"&!\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "alias (Hadd=H[`+`], Hmul=H[`*`], Hexp = H[`^`] );\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%%HaddG%%HmulG%%HexpG" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 95 "Unfortunately, it is a bit clumsy to write elements of \+ our field H. For example this is how we" }}{PARA 0 "" 0 "" {TEXT -1 42 "have to write the elements 3 and 3 +4T. " }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 25 "H[input](3);H[input](23);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#d%%\"TG\"\"&$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#d&%\"T G\"\"&$%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "In general, the integ er a+b5 for a, b =0,1,2,3,or 4" }}{PARA 0 "" 0 "" {TEXT -1 38 "corresp onds to the field element a+bT." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 21 "Here is (4+ gam)*gam." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "Hmul(Hadd(gam,H[input](4)),gam);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#d&%\"TG\"\"&%$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "We could alias H[input] and it's inverse H[output] and, w hile we're at it...." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 99 "alias( Hin = H[input], Hout = H[output], \+ HPrim=H[PrimitiveElement], HisPrim=H[isPrimitiveElement]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%%HaddG%%HmulG%%HexpG%$HinG%%HoutG%&HPrimG%( HisPrimG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "HisPrim(Hin(23) );" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 37 "No w you can write your cryptosystems." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 21 "El Gamal Cryptosystem" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 25 "Massey-Omura Cryptosystem" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 27 "Diffie-Hellman Key Excha nge" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "7 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }