{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 "" -1 256 "Choc ICG" 1 48 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "Helvetica" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 1 12 0 0 0 0 0 2 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 1 12 0 0 0 0 0 2 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "T imes" 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 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 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 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 "jr_title" -1 256 1 {CSTYLE "" -1 -1 "C hoc ICG" 1 48 0 0 255 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 "jr_title" -1 257 1 {CSTYLE "" -1 -1 "Choc ICG" 1 48 0 0 255 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 "Norma l" -1 258 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 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 257 "" 0 "" {TEXT -1 0 "" }{TEXT 256 12 "Cryptogr aphy" }{TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 0 "" }{TEXT 257 9 "J .R. Hass" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 258 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 12 "Introduction" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 966 "Cryptography is the art of secret writing. If one must s end confidential information to some destination, then most likely he \+ does not want others to have access to it. This is where cryptography \+ comes in. If we could somehow manipulate the information, so that it d idn't matter if anyone saw the data besides those who were suppose to \+ in the first place, then we wouldn't have to worry about the sensitive data being compromised.\n\nSome key terms used in this presentation a re:\n\nEncryption: This is the act of hiding the data. There are many \+ methods of manipulating data from one form to another so we will inv estigate a few. \n\nDecryption: This is the act of changing the manipu lated data back to its original form. The whole idea of hiding the inf ormation is so that eventually, someone will be able to see it. \n\nKe y: This is the piece of information that only those who are suppose to view the sensitive data have. It allows them to decrypt the encrypted data. \n" }{MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "restart: with(StringTools): with(numtheory): with(combinat):" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 11 "Encryption " }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 9 "Caes ar " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 679 "Caesar encryption is a relatively si mple one. It involves shifting letters of the alphabet. For example, i f we moved every letter of the alphabet 1 to the right we would get a \+ mapping like:\n\nA -> B\nB -> C\nZ -> A \nEtc.\n\nUsing frequency anal ysis, this encryption becomes quite trivial to break. This should be i ntuitive with a little thought. One could easily calculate the frequen cies of all the letter of a large piece of English text. They could th en look at the cipher text and do the same thing. If they noticed ther e were many 'T's for example, they could then guess that E was mapped \+ to T. We will look at a modification to this cipher next to make it a bit more complex. \n" }}{PARA 0 "" 0 "" {TEXT -1 56 "In my implementa tion, I shift according the ASCII table." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 623 "Caesar := proc(plain Text::string, offset::integer)\n\n# An example of Caesar encryption. T his method just shifts \n# the data according to the ASCII chart by an offset given \n# as a parameter. \n#\n# Params: plainText - The plain text to encrypt.\n# offset - The number to shift the text. \n#\n# Returns: A list of the encrypted text and the offset to use for \n# decryption.\n\nlocal cipher, i ;\n\ncipher := \"\" ; \n\n for i in plainText do\n #\n # Since I use the mod operator, th e offset can be anything!\n #\n cipher := cat(cipher, Char((Ord( i)+offset) mod 128)) ; \n end do ; \n\n[cipher, offset];\n\nend proc; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "Caesar(\"Hello World, I am finally done with Finals!\", 10);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "Caesar(\"We can even make the offset negative :-)\", \+ -50);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 " " {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 8 "Vigenere" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 333 "Vigenere is a slightly more complicated version of Caesar. The idea behind thi s encryption method is that you shift multiple letter of the plain tex t. This is done using a key that is provided by the user. Using this m ultiple shift idea, we can prevent people who try to use letter freque ncies (explained above) to crack our code. \n\n" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1309 "Vigenere : = proc(plaintext::string, codeword::string)\n \n # This is a program to encrypt a message using\n # vigenere encryption. Notice the input restrictions\n #\n # Params: plaintext - The text to encrypt. Notic e that for this \n # I do not use the ASCII table for shifting, \n # just the alphabet. Input must be capitol \n # letters and no numbers or spaces .\n # \n #\n # codeword - The string to shift for each letter, must also be\n # all capitols.. \n #\n \+ # Returns: A list containing the encrypted text and the key word for \+ \n # decryption. \n\n local pLen, cLen, n, cipher, i, shift ;\n\n pLen := length(plaintext); cLen := length(codeword);\n\n # Che ck if the length of the plain text is a multiple of the\n # length of the code word, if its not adjust n by the difference. \n\n if pLen m od cLen <> 0 then\n n := pLen + (cLen - (pLen mod cLen));\n else n := pLen;\n end if;\n\n # Shift each letter of the plain text with a corresponding letter\n # of the code word. \n\n cipher := \"\";\n \+ for i from 1 to n do\n cipher := cat(cipher, Char((Ord(plaintext[(i -1) mod pLen+1]) + \n Ord(codeword[(i-1) mod cLen+1])) mod 26 + 65));\n end do;\n\n [cipher, codeword];\n \n end proc;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "Vigenere(\"A PICTUREISWORTHATHOUSANDWORDS\", \"BREAKME\");" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "Vigenere(\"ITISFINALLYTIMEFORSUMMERTOBEGIN\", \" MATH\");" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "Vigenere(\"EVER YONEATUCSDSHOULDTAKEACOURSEONMAPLE\", \"CARBON\");" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 25 "R ectangular Transposition" }}{PARA 0 "" 0 "" {TEXT -1 452 "Rectangular \+ transposition uses a whole different idea of encoding. The idea here i s to first write your plain text in rectangular form, literally. For e xample consider the plaintext:\n\nH I T H E R E \nH O W A R E U\n\nNow, we have 7 columns of text. If we permuted the numbers 1-7 w e could then pick out random columns to write our message with. Say we picked the permutation of: \n\n1, 3, 5, 7, 2, 4, 6 \205 Then our mess age would be\n\nHHTWEREUIOHARE.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1701 "RectTrans := proc(plainText::string, n::integer)\n \n # This method encrypts the plain text according to the rectangular \n # transposition method. \n #\n # Params: plainText - The text to be encrypted. Plain text is expeted \n # to be a ll capitols. \n # n - The number to permute to genera te the \n # encrypted text.\n # Returns: A list \+ of the encrypted text and the permuted numbers.\n\n local tempSet, pL ist, temp, randGen, i, numRows, strLen,\n j, cipher;\n\n randG en := rand(n);\n tempSet := \{\}; pList := [];\n\n # Generate a rand om permutation of numbers from 1-n. We use the fact\n # that sets in \+ maple contain unique elements to know when to stop adding\n # random \+ numbers. \n \n for i from 1 to n do\n while(nops(tempSet) <> i) do \n temp := randGen() + 1;\n tempSet := \{op(tempSet), temp\} ;\n end do;\n\n pList := [op(pList), temp];\n end do;\n\n # Ch eck to make sure the plaintext can be written as a rectangle.\n\n str Len := length(plainText);\n if(strLen mod n = 0) then numRows := strL en / n;\n else numRows := floor(strLen / n + 1);\n end if;\n\n # Af ter we write the plaintext as a rectangle, we go through the\n # colu mns according to our random permutation and record the letters\n # in that column. If we encounter the end of the plaintext, we just\n # u se the random letter Q, this is obviously arbitrary. \n\n cipher := \+ \"\";\n for i from 1 to n do\n temp := pList[i];\n for j from 1 to numRows do\n if(temp > strLen) then\n cipher := cat(ci pher, \"Q\");\n else\n cipher := cat(cipher, plainText[tem p]);\n end if;\n temp := temp + n;\n end do;\n end do;\n \n [cipher, pList]; \n end proc;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "RectTrans(\"INCITISEASYTOSHOOTYOURSELFINTHEFOOT\", 5) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "RectTrans(\"CPPMAKESIT HARDERTOSHOOTYOURSELFBUTWHENYOUDOYOUBLOWOFFYOURLEG\", 8);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" } }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 6 "ADFGVX" }}{PARA 4 "" 0 "" {TEXT 259 951 "The ADFGVX is quite a complicated system. It begins by having a keyword and an even number that will be permuted. You start by gene rating a matrix which looks like as follows:\n\n A D F G V X\nA k \+ e y w o r\nD d a b c f g\nF h i j l m n\nG p q s t \+ u v\nV x z 0 1 2 3\nX 4 5 6 7 8 9\n\nSo the keyword begins the matrix and then you fill it up with the rest of the alphabet and \+ zero through nine. Now each letter has a coordinate system of the ADF GVX matrix. For example, the letter 'r' would be AX. \n\nNow we can wr ite out our text in columns of N/2, N being the even number that you p assed to this method. For each letter now, we can get a set of coordin ates. We now have N columns of letters after getting two coordinates f or each plain text letter. \n\nUsing rectangular transposition, we can encode the resulting text of A's D's F's G's V's and X's. This will t hen only give us cipher text containing the letters of ADFGVX. \n" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 215 "Index := proc(x, l::list)\n # Helper method that returns the index of the element x in the\n # \+ passed list. \n\n local i, n;\n n := nops(l);\n for i from 1 to n d o if l[i] = x then return i; end if; end do;\nend proc;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 300 "LookUp := proc(x, matrix::list)\n \+ # Helper method to return us the coordinates of the passed element\n \+ # in the ADFGVX matrix. \n\n local i,j;\n for i from 1 to 6 do\n \+ if member(x, matrix[i], 'j') then return [i,j]; end if;\n end do;\n \n error(\"Plain text must be a capitol letter or 0-9\");\nend proc; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 965 "MakeMatrix := proc(cod eword::string)\n# Makes the ADFGVX matrix with the codeword passed to \+ it\n# as explained above. \n \n local i,j, templist, matrix, len, n, l;\n\n templist := [];\n for i from \"A\" to \"Z\" do templist := [ op(templist), i]; end do;\n for i from 1 to 10 do templist := [op(tem plist), convert(i-1, string)]; \n end do;\n\n matrix := []; len := l ength(codeword); n := 1; \n for i from 1 to 6 do\n l := []; \n \+ for j from 1 to 6 do\n if n <= len then\n if member(cod eword[n], templist) then\n l := [op(l), codeword[n]];\n \+ templist := subsop(Index(codeword[n], templist)=NULL, templist);\n n := n+1; \n else \n l := [op(l), templist[1 ]];\n templist := subsop(1=NULL, templist);\n n := n +1; \n end if;\n else\n l := [op(l), templist[1]]; \n templist := subsop(1=NULL, templist);\n end if;\n en d do;\n matrix := [op(matrix), l];\n end do;\n matrix;\nend proc; \n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1097 "ADFGVX := proc(plai nText::string, N::integer, codeword::string)\n \n # This progrm encr ypts the text with the ADFGVX encryption. \n #\n # Param: plainText \+ - The text to encode. \n # N - The integer to permute \+ with the ADFGVX encryption\n # codeword - The word to use to \+ help generate the ADFGVX matrix.\n #\n # Note: This method expexts a ll text to be capitol letters and numbers.\n # \n # Returns: A list \+ of the encrypted text, the codeword, and the permuted set\n # \+ of numbers.\n\n local letter, cipher, matrix, len, n, i, l;\n \n \+ if N mod 2 <> 0 then error(\"N must be an even number!\"); end if;\n \n matrix := MakeMatrix(codeword);\n n:= length(plainText); \n \n \+ if n mod N/2 <> 0 then\n n := n + (N/2- (n mod N/2)); \n end if; \+ \n\n len := length(plainText);\n letter := [\"A\", \"D\", \"F\", \+ \"G\", \"V\", \"X\"];\n cipher := \"\";\n for i from 0 to n-1 do\n \+ l := LookUp(plainText[(i mod len)+1], matrix);\n cipher := cat(ci pher, letter[l[1]]);\n cipher := cat(cipher, letter[l[2]]);\n end \+ do; \n\n l := RectTrans(cipher, N);\n [l[1], l[2], codeword]; \+ \nend proc;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 93 "ADFGVX(\"FEW ARETHOSEWHOSEEWITHTHEIROWNEYSANDFEELWITHTHEIROWNHEARTSQEINSTEIN\", 8, \+ \"SCOOBYDOO\");" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "ADFGVX( \"IDONTKNOWHOWANYONEFIGUREDOUTHOWTOCRACKTHIS\", 12, \"JRHASS\");" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 4 "" 0 " " {TEXT -1 3 "RSA" }}{PARA 4 "" 0 "" {TEXT 260 1268 "The RSA code is s till widely used today. It is also called public key cryptography. Thi s code uses the fact that it is very difficult to factor large numbers as its strength in being unbreakable. Surprisingly, relative to some \+ of the earlier codes, it is quiet easy to explain how this one works. \+ \n\nBegin by picking two primes p1 and p2. These numbers are generally very large. Multiply them together to get an m, so:\nm = p1 * p2 \n\n Now, we know that since m is the product of two primes, then phi(m) is going to equal:\nphi(m) = (p1-1) * (p2-1)\n\nNow we pick any e and d \+ such that \ne*d = 1 mod phi(m) Note that it is integral that the e cho osen is relatively prime to phi(m). The\nreasoning behind this will be explained later.\n\ne is going to be our encrypting key, d is going t o be our decrypting key. \nd is what you want to keep private from the public. \n\nTo generate the code, we need to first take our plain te xt and turn it into a representation of numbers. This can be done in a ny arbitrary way. \n\nTo encode, we simply raise the numbers of our pl ain text to the power of e and take the modulus of m. \nSo E1 = P1 ^ e mod m\n\nThis gives us our encrypted text. To decode we simply raise \+ an encrypted number to the power of d and take the modulus of m\nP1 = \+ E1 ^ d mod m" }{TEXT -1 1 "\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1144 "RSA := proc(plainText::string, m_greaterThan::integer)\n \n \+ # This procedure takes a string an encodes it using the RSA \n # encr yption method. \n #\n # Params: plainTest - The string to encode \n # m_greaterThan - This will ensure that the number we choo se\n # to take phi of will be the product of \+ the\n # next two primes after this number. \n #\n # Returns: This method returns a list of the encrypted text\n \+ # and the 'e', 'd' and 'm' values used to decrypt the text\n \+ \n local phiM, p1, p2, m, e, d, dummy, randGen, cipher, i,\n \+ retVal;\n\n p1 := nextprime(m_greaterThan);\n p2 := nextprime(p1); \n phiM := (p1-1)*(p2-1); \n m := p1*p2;\n\n randGen := rand(phiM); \n e := randGen();\n\n # igcdex conveiently figurs out what 'd' is f or us\n while igcdex(e, phiM, 'd', 'dummy') <> 1 or d < 0 do e := ran dGen(); end do;\n\n cipher := [];\n\n # Now we just raise the plaint ext to the power of e and mod it m. \n # Notice the & operator used f or large numbers. \n\n for i in plainText do\n cipher := [op(cipher ), Ord(i) &^e mod m];\n end do;\n\n [cipher, e, d, m];\n\n end proc ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "RSA(\"ICANTBELIEVEITTA KESSOLITTLECODETOWRITETHISPOWERFULENCRYPTIONMETHOD\", 1000);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 84 "RSA(\"LETSUPTHESIZEOFMALITTL EBITANDSEEHOWLONGITTAKESMAPLETODOTHECOMPUTATIONS\", 2^20);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "Decryption" }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 6 "Caesar " }}{PARA 0 "" 0 "" {TEXT -1 125 "To decrypt the Caesar code, it is ac tually quite trivial. All we have to do is to shift back the text the \+ other way! Example:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 335 "CaesarDecrypt := proc(eText::string, offse t::integer)\n\n # This method decrypts a Caesar encrypted message\n \+ #\n # Params: eText - The encrypted text\n # offset - The o ffset it was encrypted with\n # \n # Returns: The original plain tex t\n\n local n;\n\n # Just shift backwards!\n\n n := Caesar(eText, - offset);\n n[1];\nend proc;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 93 "e := Caesar(\"Gravity cannot be held responsible for people fall ing in love - Einstein\", 100);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "CaesarDecrypt(e[1], e[2]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 8 "Vigenere" }}{PARA 0 "" 0 "" {TEXT -1 174 "The same idea is used for Vigenere, except now we have to shift a different am ount for each letter that is in the key (the codeword that was passed \+ to the original function)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 686 "VigenereDecrypt := proc(eText::str ing, key::string)\n\n # This method decrypts a message that was encry pted with the\n # Vigenere method of encryption\n # \n # Params: eT ext - The encrypted text\n # key - The key to decrypt with \n # \n # Returns: The plain text of the message\n \n local n, i, \+ pText, cl, kLen;\n\n pText := \"\";\n n := length(eText);\n kLen := length(key);\n\n # Now shift according to the letter the plaintext w as mapped to\n # in the encrypting codword.\n\n for i from 1 to n do \n cl := Ord(eText[i]) - 65;\n cl := cl - Ord(key[(i-1) mod kLe n +1]);\n\n while cl < 65 do cl := cl + 26; end do;\n pText := c at(pText, Char(cl));\n end do;\n pText;\nend proc;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "e := Vigenere(\"ICANNOTBELIEVEIAMASENIORI NCOLLEGEWHEREDIDTHETIMEGO\", \"BUGS\");" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "VigenereDecrypt(e[1], e[2]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 25 "Rectangular Transposition" }}{PARA 0 "" 0 "" {TEXT -1 502 "Rectangular transposition is a bit tricky to decryp t. Visually, one would want to make actual columns of text with the en crypted text. Then if they were given the permutation of the number th at it was encrypted with, they can just put the columns in the correct order. \n\nOur method is going to find the position of the column we \+ are looking for in the permutation list. We are then going to search t he string of text and find which letter in a given column we need to a ppend to the plain text string. \n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 559 "RectTransDecrypt := proc(eText::string, key::list)\n \n # This method decrypts a string of text encoded with \n # rectang ular transposition.\n # \n # Params: eText - The encrypted text\n # key - The permutation used to encrypt the text\n # \n # R eturns: The plain text message\n\n local rows, cols, pText, i, j, p; \n\n pText := \"\";\n cols := nops(key);\n rows := length(eText)/co ls;\n\n for i from 1 to rows do\n for j from 1 to cols do\n m ember(j, key, 'p');\n pText := cat(pText, eText[rows*(p-1)+i]);\n end do;\n end do;\n pText;\nend proc;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 145 "e := RectTrans(\"WHENYOUSITWITHANICEGIRLFORTWOHOU RSITSEEMSLIKETWOMINUTEWHENYOUSITONAHOTSTOVEFORTWOMINUTESITSEEMSLIKETWO HOURSTHATSRELATIVITY\", 16);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "RectTransDecrypt(e[1], e[2]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 6 "ADFGVX" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 476 "As with the encryption scheme, the decryption sc heme of ADFGVX is also a bit tricky. ADFGVX uses rectangular transposi tion inside of it. So we must also use the method to decrypt a rectang ular transposition string first, and then continue from there.\n\nWhen we encrypted, we use an alphabet/number matrix to find 'coordinates' \+ for each letter of the plain text. Now we will have to go back words, \+ and for each pair of coordinates, find the corresponding letter to go \+ with it. \n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 791 "ADecrypt := \+ proc(eText::string, pList::list, key::string)\n\n # This method decry pts a string that was encrypted with the\n # ADFGVX method. \n # \n \+ # Params: eText - The encrypted text\n # pList - The permuta tion of an even number used for encryption\n # key - The ke y that was used to make the matrix.\n #\n # Returns: The original pl ain text\n\n local matrix, n, letter, x, y, i, pText, EText;\n \n E Text := RectTransDecrypt(eText, pList);\n\n pText := \"\";\n matrix \+ := MakeMatrix(key);\n n := length(eText);\n letter := [\"A\", \"D\", \"F\", \"G\", \"V\", \"X\"];\n\n # Now just look up the plaintextin \+ the matrix. \n\n for i from 1 to n by 2 do\n member(EText[i], lett er, 'x');\n member(EText[i+1], letter, 'y');\n pText := cat(pTex t, matrix[x][y]);\n end do;\n \n pText;\nend proc;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 90 "e := ADFGVX(\"MYHATGOESOFFTOTHEPERSONTHAT WASABLETOFIGUREOUTHOWTOBREAKTHIS\", 10, \"PROGRAM\");" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "ADecrypt(e[1], e[2], e[3]);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 3 "RSA" }}{PARA 0 "" 0 "" {TEXT -1 128 "RSA makes it very easy to decrypt with. As we noted earl ier, we will need to raise the encrypted text to the inverse of e to g et" }}{PARA 0 "" 0 "" {TEXT -1 23 "the plain text again..." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 111 "Why does this wo rk though? As promised above, a little more in depth explanation of wh y this encrypytion works." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 107 "We know that e and d are inverses of the phi(m). \+ We also know that for some number 'a' (encrypted text say)" }}{PARA 0 "" 0 "" {TEXT -1 42 "that if gcd(a, m) = 1, then\n\nEuler-Fermat:" }} {PARA 0 "" 0 "" {TEXT -1 20 "a ^ phi(m) = 1 mod m" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 63 "Going through the encrypt ion and decryption process looks like:" }}{PARA 0 "" 0 "" {TEXT -1 45 "(a^e)^d = a^(ed) = a^phi(m) * a = 1 * a = a " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "When we encrypt our text, we use a relatively prime number to raise the plaintext to. " }} {PARA 0 "" 0 "" {TEXT -1 90 "However, this does not guarantee that the output (a^e) will also be realtively prime to m." }}{PARA 0 "" 0 "" {TEXT -1 18 "What happens then?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 42 "We also have another theorem which states :" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "For \+ any primes p and q" }}{PARA 0 "" 0 "" {TEXT -1 32 "a ^ ( (p-1) * (q-1) ) = 1 mod pq" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 126 "How conveient! We know that m = pq and phi(m) is just (p -1) * (q-1). So no matter what number we use, raising it to the e and \+ " }}{PARA 0 "" 0 "" {TEXT -1 33 "then to the d to decrypt is like\n" } }{PARA 0 "" 0 "" {TEXT -1 78 "a ^phi(m) * a^1 = 1 * a mod m ....and he nce we have the RSA encryption method!" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 456 "RSADecrypt := proc(eText::list, d::integer, m::integer)\n\n \+ # Decrypts text that was encoded with RSA. \n # \n # Parmas: eText - The encoded text\n # d - The power to raise the the text to. \n # m - The modulus of our original encryption\n # \n # Returns: The plain text\n\n local pText, n, i;\n\n pText := \+ \"\";\n n := nops(eText);\n\n for i from 1 to n do \n pText := ca t(pText, Char(eText[i] &^d mod m));\n end do;\n pText;\nend proc;" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "e := RSA(\"THEWHOLEISMORETHANTHESUMOFITSPARTS\", 100) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "RSADecrypt(e[1], e[3], e[4]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 12 "Breaking RSA" }}{PARA 0 "" 0 "" {TEXT -1 461 " Since RSA is quite a popular method of encryption, I wanted to r un a test on it. I thought it would be interesting to see what values \+ of 'm' would really make Maple stretch its limits. I wanted to write a program that 'breaks' RSA. In other words given the 'e' and the 'm' \+ used to encrypt some text, it would figure out phi of m and compute th e 'd' value to decrypt the text. The user can use this program to test how long certain values of 'm' take to break." }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 583 "RSABreak : = proc(eText::list, m::integer, e::integer)\n \n # Method to break RSA encryption. \n #\n # Params - eText: The encrypted text\n # - \+ m: The 'm' value used to encrypt the text\n # d: The \+ 'e' value used to encrypt. \n #\n # Returns: A list of the amount of t ime it took in seconds to break this\n # code and the plainte xt. \n # \n \n local i, d, phiM, pText, dummy;\n\n i := time(); \n\n \+ # Get phi of m\n phiM := phi(m);\n\n # Calculate 'd'\n igcdex(e, phiM, 'd', 'dummy');\n\n # Just call the decryption method\n \n [time()-i, \+ RSADecrypt(eText, d, m)];\n\nend proc; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "e := RSA(\"LETSSEEJUSTHOWGOODMYRSABREAKPROGRAMWORKS\" , 10^14);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "d := RSABreak( e[1], e[4], e[2]); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} }}{MARK "1 1 0 0" 425 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }