{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 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 "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{PARA 11 "" 1 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 342 " prodFirstPrimes := proc(N)\n # This function returns the product of \+ the primes less than N\n local x,i,myPrime;\n i := 1:\n x := 1: \n myPrime := 2:\n while(myPrime < N) do\n i := 1:\n whi le (myPrime^i <= N) do i := i + 1: od:\n i := i - 1:\n x := \+ x * myPrime^i:\n myPrime := nextprime(myPrime):\n od:\n x\nen d proc;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%0prodFirstPrimesGf*6#%\"N G6%%\"xG%\"iG%(myPrimeG6\"F,C'>8%\"\"\">8$F0>8&\"\"#?(F,F0F0F,2F49$C'> F/F0?(F,F0F0F,1)F4F/F8>F/,&F/F0F0F0>F/,&F/F0F0!\"\">F2*&F2F0F=F0>F4-%* nextprimeG6#F4F2F,F,F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1308 "pollardPMinusOneMethod := proc(n, B1, B2)\n # This function uses th e Pollard P-1 method of factoring to try and factor n\n # This metho d works only when n has a prime factor p such that p-1 has small prime \n # factors\n local a,k,b,d,i,myPrime,testFactor,currentB,t,c,ind ex,gap,randomNumber:\n i := 0:\n d := 1:\n k := prodFirstPrimes( B1):\n randomNumber := rand(2..n-2):\n while ((d = 1) and (i < 10) ) do\n # these first 4 lines are what is called the p-1 first sta ge in the literature\n # relatively simple\n a := randomNumb er():\n b := a&^k mod n:\n d := gcd(b - 1, n):\n i := i + 1:\n # this if block is the second stage p-1 factoring method. A little more\n # complex, yet is a more sophisticated method. \n if (d = 1) then\n myPrime := nextPrime(B1):\n \+ t := 1:\n currentB := (b&^(myPrime)) mod N:\n c := 10 :\n while ((t <= floor(B2/c)*c + 1) and (d = 1)) do\n \+ testFactor := 1:\n for index from 0 to c do\n \+ testFactor := testFactor * (currentB - 1):\n gap := \+ nextPrime(myPrime) - myPrime:\n currentB := (b&^(gap)*cu rrentB) mod N\n od:\n d = igcd(testFactor, N):\n t := t + c:\n od: \n end if:\n od: \n d\nend proc;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 1240 "lucasVFuncti on := proc(P,N,r)\n # this function computes V_r(P) mod N where V_n \+ is the Lucas Function\n # defined by a^n + b^n where a,b are roots o f the polynomial\n # x^2 - px + 1\n\n local i, V_Zero, V_bigtemp, \+ V_smalltemp, V_big, V_small,numBits,binaryR:\n\n # this is initializ ed to v_0\n V_small := 2:\n # this is initialized to v_1\n V_big := P:\n\n # convert r to binary and then to a string so we may acce ss the bits individually\n binaryR := convert(convert(r, binary), st ring);\n numBits := evalf(log(r)/log(2)):\n if (ceil(numBits) > nu mBits) then numBits := numBits + 1: end if:\n\n # this loop calculat es V_r(P) using an algorithm that is polynomial\n # in the number of bits of r, using the following recurrences:\n # V_(2f-1) = V_f*V_(f -1) - P mod N\n # V_(2f) = V_f*V_f - 2 mod N\n # V_(2f-1) = P*V_f^ 2 - V_f*V_(f-1) - P mod N\n for i from 2 to numBits do\n V_smal ltemp := V_small:\n V_bigtemp := V_big:\n if (binaryR[i] = \+ \"1\") then\n V_big := (P*V_bigtemp^2 - V_bigtemp*V_smalltemp \+ - P) mod N:\n V_small := (V_bigtemp^2 - 2) mod N:\n else \n V_big := (V_bigtemp^2 - 2) mod N:\n V_small := (V_b igtemp*V_smalltemp - P) mod N:\n end if:\n od:\n\n V_big\n\ne nd proc;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%7pollardPMinusOneMethodG f*6%%\"nG%#B1G%#B2G6/%\"aG%\"kG%\"bG%\"dG%\"iG%(myPrimeG%+testFactorG% )currentBG%\"tG%\"cG%&indexG%$gapG%-randomNumberG6\"F8C(>8(\"\"!>8'\" \"\">8%-%0prodFirstPrimesG6#9%>80-%%randG6#;\"\"#,&9$F?FL!\"\"?(F8F?F? F83/F>F?2F;\"#5C'>8$-FGF8>8&-%$modG6$-%#&^G6$FWFAFN>F>-%$gcdG6$,&FZF?F ?FOFN>F;,&F;F?F?F?@$FRC'>8)-%*nextPrimeGFD>8,F?>8+-Ffn6$-Fin6$FZFeo%\" NG>8-FT?(F8F?F?F831Fio,&*&-%&floorG6#*&9&F?FbpFOF?FbpF?F?F?F?FRC&>8*F? ?(8.FF_q*&F_qF?,&F[pF?F?FOF?>8/,&-Fgo6#FeoF?FeoFO>F[p- Ffn6$*&-Fin6$FZFhqF?F[pF?F`p/F>-%%igcdG6$F_qF`p>Fio,&FioF?FbpF?F>F8F8F 8" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%/lucasVFunctionGf*6%%\"PG%\"NG% \"rG6*%\"iG%'V_ZeroG%*V_bigtempG%,V_smalltempG%&V_bigG%(V_smallG%(numB itsG%(binaryRG6\"F3C)>8)\"\"#>8(9$>8+-%(convertG6$-F>6$9&%'binaryG%'st ringG>8*-%&evalfG6#*&-%$logG6#FB\"\"\"-FL6#F7!\"\"@$2FF-%%ceilG6#FF>FF ,&FFFNFNFN?(8$F7FNFF%%trueGC%>8'F6>8&F9@%/&F<6#FZQ\"1F3C$>F9-%$modG6$, (*&F:FN)FjnF7FNFN*&FjnFNFhnFNFQF:FQ9%>F6-Fco6$,&*$FgoFNFNF7FQFioC$>F9F [p>F6-Fco6$,&FhoFNF:FQFioF9F3F3F3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 911 "williamsPPlusOneMethod := proc(n,B)\n # This funct ion uses the William's p+1 method of factoring an integer n.\n # Thi s method works when n has a prime divisor p such that p+1 has small\n \+ # prime divisors. This function returns a factor.\n local k,pnot, loopCount, result:\n \n loopCount := 1:\n\n # this finds the pno t such that (pnot^2 - 4) = 1\n pnot := 3;\n while (igcd(pnot^2 - 4 , n) <> 1) do\n pnot := pnot + 1:\n od:\n \n k := prodFirst Primes(B):\n\n result := igcd(lucasVFunction(pnot,n,k) - 2, n):\n \+ # loop until we have found a factor. Don't perform this\n # loop mo re than 10 times though.\n while ((result = 1) and (loopCount < 10)) do\n loopCount := loopCount + 1:\n # get the next pnot\n \+ pnot := pnot + 1:\n while (igcd(pnot^2 - 4, n) <> 1) do\n \+ pnot := pnot + 1:\n od:\n result := igcd(lucasVFunction( pnot,n,k) - 2, n):\n od:\n result\nend proc;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%7williamsPPlusOneMethodGf*6$%\"nG%\"BG6&%\"kG%%pnotG% *loopCountG%'resultG6\"F.C)>8&\"\"\">8%\"\"$?(F.F2F2F.0-%%igcdG6$,&*$) F4\"\"#F2F2\"\"%!\"\"9$F2>F4,&F4F2F2F2>8$-%0prodFirstPrimesG6#9%>8'-F9 6$,&-%/lucasVFunctionG6%F4FAFEF2F>F@FA?(F.F2F2F.3/FKF22F1\"#5C&>F1,&F1 F2F2F2>F4FC?(F.F2F2F.F7>F4FC>FKFLFKF.F.F." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 423 "getKBitPrime := proc(k)\n # This function return s a prime number of at least k bits\n local a,i:\n i := 0:\n a : = rand(2^(k-1)..2^(k-1) + 2^(k-2) - 1)():\n if (type(a, even)) then \+ a := a + 1; end if;\n while (not(isprime(a))) do\n i := i + 1: \n a := a + 2:\n od:\n # note the return value is a pair. i \+ is the number of times isprime() is called\n # and a is the prime of at least k bits\n [i,a]\nend proc;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%-getKBitPrimeGf*6#%\"kG6$%\"aG%\"iG6\"F+C'>8%\"\"!>8$--%%randG6#; )\"\"#,&9$\"\"\"F;!\"\",(F7F;)F8,&F:F;F8FF1,&F1F;F;F;?(F+F;F;F+4-%(isprimeG6#F1C$>F.,&F.F;F;F;>F1,&F1F;F8F;7$ F.F1F+F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1332 "getKBitStro ngPrime := proc(k)\n # This function returns a prime number of at le ast k bits that is deemed\n # a strong prime. This means that p is \+ such that t = p-1 has a large prime\n # factor, p+1 has a large prim e factor, and t's large prime factor has\n # another large prime fac tor.\n local r,s,t,p,pnot,L,i,retList,j:\n # get a large prime s o f at least floor(k/2) bits\n retList := getKBitPrime(floor(k/2)):\n \+ s := retList[2]:\n i := retList[1]:\n # get a large prime t of a t least floor(k/2) bits\n retList := getKBitPrime(floor(k/2)):\n t := retList[2]:\n i := i + retList[1]:\n # this algorithm creates \+ a prime r that is equivalent to 1 mod t(i.e. t divides r-1)\n L := f loor(k/2):\n r := 2*L*t + 1:\n while (not(isprime(r))) do\n i := i + 1:\n L := L + 1;\n r := 2*L*t + 1:\n od:\n # The paper states that a prime that such that p+1 has factor s and p-1 has factor r\n # must be of the form p = pnot + 2*j*r*s where pnot is d efined below.\n pnot := (s&^(r-1) - r&^(s-1)) mod r*s:\n if (type( pnot, even)) then pnot := pnot + r*s end if:\n j := 1;\n p := pnot + 2*j*r*s;\n while (not(isprime(p))) do\n i := i + 1:\n j := j + 1;\n p := pnot + 2*j*r*s;\n od:\n # Note that the ret urn value is again a list, with the last value is the desired prime p \n [i,r,s,t,p]\nend proc;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%3getK BitStrongPrimeGf*6#%\"kG6+%\"rG%\"sG%\"tG%\"pG%%pnotG%\"LG%\"iG%(retLi stG%\"jG6\"F2C1>8+-%-getKBitPrimeG6#-%&floorG6#,$9$#\"\"\"\"\"#>8%&F56 #F@>8*&F56#F?>F5F6>8&FC>FF,&FFF?FGF?>8)F9>8$,&*&FOF?FKF?F@F?F??(F2F?F? F24-%(isprimeG6#FQC%>FF,&FFF?F?F?>FO,&FOF?F?F?>FQFR>8(-%$modG6$,&-%#&^ G6$FB,&FQF?F?!\"\"F?-F`o6$FQ,&FBF?F?FcoFco*&FQF?FBF?@$-%%typeG6$Fjn%%e venG>Fjn,&FjnF?FgoF?>8,F?>8',&FjnF?**F@F?F`pF?FQF?FBF?F??(F2F?F?F24-FW 6#FbpC%>FFFen>F`p,&F`pF?F?F?>FbpFcp7'FFFQFBFKFbpF2F2F2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 239 "getRSA_e_d := proc(phi,start)\n \+ local x,i,e,d:\n for i from start to phi-1 do\n x := i: \n \+ if (igcdex(i,phi,'d','blah') = 1) then \n e := i:\n \+ break: \n end if:\n od:\n [e mod phi,d mod phi]\nend \+ proc;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%+getRSA_e_dGf*6$%$phiG%&sta rtG6&%\"xG%\"iG%\"eG%\"dG6\"F.C$?(8%9%\"\"\",&9$F3F3!\"\"%%trueGC$>8$F 1@$/-%'igcdexG6&F1F5.8'.%%blahGF3C$>8&F1[7$-%$modG6$FFF5-FJ6$FAF5F.F.F ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "encoder := (P,e,n) -> \+ (P&^e) mod n:\ndecoder := (C,d,n) -> (C&^d) mod n:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1186 "e ncodeRSA := proc(e,n,message)\n local blockSize, encMessage, message Length, numBlocks, encMessage2, theBlocks,\n theEncodedBlocks, encodedMessage, i, j, morbledMessage; \n\n blockSize := floor(eval f(log(sqrt(n))/log(256)))-1;\n encMessage := convert(message, bytes) ; messageLength := nops(encMessage);\n numBlocks := ceil(messageLeng th/blockSize);\n encMessage2 := array(1..blockSize*numBlocks);\n \+ \n for i from 1 to messageLength do\n encMessage2[i] := encMess age[i]: \n od:\n for i from messageLength+1 to blockSize*numBlocks do\n encMessage2[i] := 32:\n od:\n\n theBlocks := array(1..n umBlocks);\n for i from 1 to numBlocks do\n theBlocks[i] := enc Message2[(i-1)*blockSize+1]:\n for j from 1 to blockSize-1 do \n theBlocks[i] := theBlocks[i] + (256^j)*encMessage2[(i-1) *blockSize+1+j]:\n od: \n od:\n\n theEncodedBlocks := co nvert(map(encoder, theBlocks,e,n),array);\n encodedMessage := map(co nvert,map(convert,theEncodedBlocks,base,256),bytes);\n \n morbledM essage :=``;\n for i from 1 to numBlocks do\n morbledMessage := cat(morbledMessage, encodedMessage[i]):\n od:\n\n [morbledMessage , theEncodedBlocks]\nend proc;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%*e ncodeRSAGf*6%%\"eG%\"nG%(messageG6-%*blockSizeG%+encMessageG%.messageL engthG%*numBlocksG%,encMessage2G%*theBlocksG%1theEncodedBlocksG%/encod edMessageG%\"iG%\"jG%/morbledMessageG6\"F6C0>8$,&-%&floorG6#-%&evalfG6 #*&-%$logG6#-%%sqrtG6#9%\"\"\"-FC6#\"$c#!\"\"FIFIFM>8%-%(convertG6$9&% &bytesG>8&-%%nopsG6#FO>8'-%%ceilG6#*&FVFIF9FM>8(-%&arrayG6#;FI*&F9FIFe nFI?(8,FIFIFV%%trueG>&F[o6#Fbo&FOFfo?(Fbo,&FVFIFIFIFIF`oFco>Feo\"#K>8) -F]o6#;FIFen?(FboFIFIFenFcoC$>&F]pFfo&F[o6#,&*&,&FboFIFIFMFIF9FIFIFIFI ?(8-FIFI,&F9FIFIFMFco>Fdp,&FdpFI*&)FLF[qFI&F[o6#,(FhpFIFIFIF[qFIFIFI>8 *-FQ6$-%$mapG6&%(encoderGF]p9$FHF]o>8+-Fiq6%FQ-Fiq6&FQFeq%%baseGFLFT>8 .%!G?(FboFIFIFenFco>Fer-%$catG6$Fer&F^rFfo7$FerFeqF6F6F6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 420 "decodeRSA := proc(theEncodedBlocks , d, n)\nlocal blockSize,decodedMessage, demorbledMessage,i; \n\n \+ blockSize := max($op(2,theEncodedBlocks()));\n \n decodedMessage : =\n map(convert,map(convert,map(decoder,theEncodedBlocks,d,n),bas e,256),bytes);\n\n demorbledMessage :=``;\n for i from 1 to blockS ize do\n demorbledMessage := cat(demorbledMessage, decodedMessage [i]):\n od:\n \n demorbledMessage \nend proc;" }}{PARA 12 "" 1 " " {XPPMATH 20 "6#>%*decodeRSAGf*6%%1theEncodedBlocksG%\"dG%\"nG6&%*blo ckSizeG%/decodedMessageG%1demorbledMessageG%\"iG6\"F/C'>8$-%$maxG6#-% \"$G6#-%#opG6$\"\"#-9$F/>8%-%$mapG6%%(convertG-FB6&FD-FB6&%(decoderGF> 9%9&%%baseG\"$c#%&bytesG>8&%!G?(8'\"\"\"FTF2%%trueG>FP-%$catG6$FP&F@6# FSFPF/F/F/" }}}}{MARK "10 0 0" 958 }{VIEWOPTS 1 1 0 1 1 1803 1 1 0 1 } {PAGENUMBERS 0 1 2 33 1 1 }