> # Notes for M307 = COMPSCI 367/567, Cryptology I
> 
> # What is a cryptosystem?  The formal description we use is that a cryptosystem
> # is determined by a set of keys K, with each key determining functions e[K] and d[K]
> # such that if x is a plaintext (message to be sent) e[K](x) is the corresponding ciphertext
> # (e[K] is an enciphering function for key K) and if y is a ciphertext, d[K](y) will be the
> # corresponding plaintext (d[K](x) is a deciphering function for key K).
> 
> # Clearly, we require e[K] and d[K] to be inverse functions (e[K](d[K](x)) = d[K](e[K](x)) = x)
> # for this to work.
> 
> # Cryptology is all about keeping secrets.  If a hostile party intercepts a ciphertext message
> # y = e[K](x), they should not be able to determine what the message x is.  At a bare minimum,
> # they should have no way of telling what d[K] is.  In the manner of secrecy, we deliberately
> # handicap ourselves by adopting
> 
> # KERCKHOFF'S PRINCIPLE  Assume that opponents know what cryptosystem is being used.
> 
> # Under Kerckhoff's Principle, it is essential that the key K be secret from the opponent,
> # since knowledge of the cryptosystem allows one to determine e[K] and the disastrous d[K]
> # from knowledge of the key K.  In classical cryptosystems, the opponent will not know
> # e[K] either (because knowledge of e[K] is basically equivalent to knowledge of K) but
> # in the public-key cryptosystems we will spend most of our time studying, the encryption
> # function e[K] can be public knowledge:  in these systems, it is apparently impossible (or
> # very difficult) to determine the key K and the decryption function d[K] from knowledge 
> # of the publicly available e[K].
> 
> # We will begin by studying some classical cryptosystems. Most of these are of merely historical
> # interest, as modern techniques allow them to be broken easily.
> 
> #  We'll need some Maple functions.
> 
> with(StringTools);  #this introduces useful tools for dealing with character strings.

  [AndMap, Capitalize, Char, CharacterMap, Chomp, CommonPrefix,

        CommonSuffix, Compare, CompareCI, Drop, Explode,

        FirstFromLeft, FirstFromRight, FormatMessage, Group, Implode,

        IsASCII, IsAlpha, IsAlphaNumeric, IsBinaryDigit,

        IsControlCharacter, IsDigit, IsGraphic, IsHexDigit,

        IsIdentifier, IsIdentifier1, IsLower, IsOctalDigit, IsPrefix,

        IsPrintable, IsPunctuation, IsSpace, IsSuffix, IsUpper, Join,

        LeftFold, Levenshtein, LongestCommonSubSequence,

        LongestCommonSubString, LowerCase, Map, OrMap, Ord, Random,

        RegMatch, RegSub, Remove, Reverse, RightFold, Search,

        SearchAll, Select, SelectRemove, Soundex, Split, Squeeze,

        SubString, Substitute, SubstituteAll, Take, Trim, TrimLeft,

        TrimRight, UpperCase]

> # this function converts lower case letters to numbers.
> alphabet := c -> :-StringTools:-Ord(c) - 97;

             alphabet := c -> :-StringTools:-Ord(c) - 97

> alphabet("a");

                                  0

> alphabet("b");

                                  1

> alphabet("c");

                                  2

> # this function converts numbers to upper case letters.
> alphabetinv := n -> :-StringTools:-Capitalize(Char(n+97));

    alphabetinv := n -> :-StringTools:-Capitalize(:-Char(n + 97))

> alphabetinv(0);

                                 "A"

> alphabetinv(1);

                                 "B"

> alphabetinv(2);

                                 "C"

> save (alphabet,alphabetinv,"alphabetfuns.m");
> # we follow the convention given in the book that plaintext will be given in
> # lowercase letters and ciphertext in upper case.  Actual cryptography will be
> # carried out in arithmetic.  For the moment we assume that plaintext is made
> # up entirely of lower case letters without spaces or punctuation.
> 
> #our first cipher, the Shift Cipher.
> 
> shiftcipher:=(key,text)->Implode(map(alphabetinv,map((x->(x+key) mod 26),map(alphabet,Explode(text)))));

  shiftcipher := (key, text) -> :-Implode(map(alphabetinv,

        map(x -> (x + key) mod 26, map(alphabet, :-Explode(text)))))

> save (shiftcipher,"shiftcipher.m");
> shiftcipher(3,"helloworld");

                             "KHOORZRUOG"

> # Take this step by step.
> text := "helloworld";

                         text := "helloworld"

> Explode(%);

          ["h", "e", "l", "l", "o", "w", "o", "r", "l", "d"]

> map(alphabet,%);

                [7, 4, 11, 11, 14, 22, 14, 17, 11, 3]

> map((x->(x+3) mod 26),%);

                [10, 7, 14, 14, 17, 25, 17, 20, 14, 6]

> map(alphabetinv,%);

          ["K", "H", "O", "O", "R", "Z", "R", "U", "O", "G"]

> Implode(%);

                             "KHOORZRUOG"

> # Julius Caesar is said to have used this cipher with the key 3.
> # deciphering is easy
> shiftdecipher:=(key,text) ->LowerCase(shiftcipher(-key,LowerCase(text)));

  shiftdecipher := (key, text) ->

        :-LowerCase(shiftcipher(-key, :-LowerCase(text)))

> save(shiftdecipher,"shiftdecipher.m");
> shiftdecipher(3,"KHOORZRUOG");

                             "helloworld"

> # Notice that under Kerckhoff's Principle, this cipher is trivially broken, because there
> # are only 26 keys, and we can try each one until the plaintext is revealed.
> 
> # note the use of modular arithmetic to make letters at the end of the alphabet
> # wrap around to the beginning.
> 
> # a very slightly less trivial cipher is the Affine Cipher:
> 
> affinecipher:= (keyx, keyy, text) -> if gcd(keyx,26) = 1 then Implode(map(alphabetinv,map((x->(keyx*x+keyy) mod 26),map(alphabet,Explode(text))))) else "bad key" end if;

  affinecipher := proc(keyx, keyy, text)
option operator, arrow;
    if gcd(keyx, 26) = 1 then :-Implode(map(alphabetinv, map(
        x -> (keyx*x + keyy) mod 26,
        map(alphabet, :-Explode(text)))))
    else "bad key"
    end if
end proc

> affinecipher(3,7,"helloworld");

                             "CTOOXVXGOQ"

> # build this alphabet by hand
> affinecipher(6,8,"helloworld");

                              "bad key"

> # construct the cipher alphabet by hand to see why this is a bad key.  The two numbers
> # making up the key cannot have a common factor, or this will happen.
> 
> #deciphering seems straightforward, except that there's some mysterious
> #modular arithmetic involved.
> 
> affinedecipher:=(key1,key2,text)->if gcd(key1,26) = 1 
> then LowerCase(Implode(map(alphabetinv,map((x->((x-key2)/key1)mod 26),map(alphabet,Explode(LowerCase(text))))))) else "bad key" end if;
> 

  affinedecipher := proc(key1, key2, text)
option operator, arrow;
    if gcd(key1, 26) = 1 then :-LowerCase(:-Implode(map(
        alphabetinv, map(x -> (x - key2)/key1 mod 26,
        map(alphabet, :-Explode(:-LowerCase(text)))))))
    else "bad key"
    end if
end proc

> affinedecipher(3,7,"CTOOXVXGOQ");

                             "helloworld"

> # there are more keys for the Affine Cipher, but not really enough for security against
> # an attack by exhaustive key search.  The number of keys is n*phi(n), where phi is the
> # "Euler phi function" and n is the number of letters in our alphabet.  phi(n) is defined as the number of positive integers m < n which
> # are relatively prime to n.  See Theorem 1.2 in the book for a formula for phi(n);
> # I might discuss the derivation of this formula in class.
> 
> with(numtheory);  # the number theory package, which includes such things as the phi function.

  [GIgcd, bigomega, cfrac, cfracpol, cyclotomic, divisors, factorEQ,

        factorset, fermat, imagunit, index, integral_basis, invcfrac,

        invphi, issqrfree, jacobi, kronecker, lambda, legendre,

        mcombine, mersenne, minkowski, mipolys, mlog, mobius, mroot,

        msqrt, nearestp, nthconver, nthdenom, nthnumer, nthpow, order,

        pdexpand, phi, pi, pprimroot, primroot, quadres, rootsunity,

        safeprime, sigma, sq2factor, sum2sqr, tau, thue]

> phi(3);

                                  2

> phi(21);

                                  12

> # Execute the following line to see what Maple has to say about the Euler phi function.
> ?phi
> 26*phi(26);

                                 312

> # so there are 312 keys for the Affine Cipher over the 26 letter alphabet we are currently
> # using.  It would be straightforward to search through all of these with a computer program.  There are even
> # faster ways to break this cipher, as we will see.
> 
> # Our first nontrivial cipher is the Substitution Cipher, which assigns an arbitrary
> # ciphertext letter to each letter of the plaintext.
> 
> subcipher:= (key,text) -> Implode(map(key,Explode(text)));

   subcipher := (key, text) -> :-Implode(map(key, :-Explode(text)))

> #Here the key is a function from plaintext letters to ciphertext letters.
> 
> f("a") := "B";

                            f("a") := "B"

> f("b") := "D";

                            f("b") := "D"

> f("c") := "Z";

                            f("c") := "Z"

> f("d") := "O";

                            f("d") := "O"

> f("e") := "V";

                            f("e") := "V"

> f("f") := "Q";

                            f("f") := "Q"

> f("g") := "C";

                            f("g") := "C"

> f("h") := "T";

                            f("h") := "T"

> f("i") := "P";

                            f("i") := "P"

> f("j") := "S";

                            f("j") := "S"

> f("k") := "G";

                            f("k") := "G"

> f("l") := "L";

                            f("l") := "L"

> f("m") := "W";

                            f("m") := "W"

> f("n") := "U";

                            f("n") := "U"

> f("o") := "H";

                            f("o") := "H"

> f("p") := "J";

                            f("p") := "J"

> f("q") := "E";

                            f("q") := "E"

> f("r") := "N";

                            f("r") := "N"

> f("s") := "R";

                            f("s") := "R"

> f("t") := "F";

                            f("t") := "F"

> f("u") := "I";

                            f("u") := "I"

> f("v") := "K";

                            f("v") := "K"

> f("w") := "A";

                            f("w") := "A"

> f("x") := "Y";

                            f("x") := "Y"

> f("y") := "X";

                            f("y") := "X"

> f("z") := "M";

                            f("z") := "M"

> subcipher(f,"helloworld");

                             "TVLLHAHNLO"

> # the key is a permutation of the letters of our alphabet, so there are 26!
> 26!;

                     403291461126605635584000000

> #keys, a rather large number for exhaustive key search!  Nonetheless, the
> #Substitution Cipher is easily broken, as we will see.
> 
> #We develop a deciphering utility.
> 
> keyinverseloop := (f,c,n) -> if f(LowerCase(alphabetinv(n))) = c then LowerCase(alphabetinv(n))
> else if n = 26 then "*" else keyinverseloop(f,c,n+1) end if end if;
> 
> 

  keyinverseloop := proc(f, c, n)
option operator, arrow;
    if f(:-LowerCase(alphabetinv(n))) = c then
        :-LowerCase(alphabetinv(n))
    else
        if n = 26 then "*"
        else keyinverseloop(f, c, n + 1)
        end if
    end if
end proc

> keyinverse := (f,c) -> keyinverseloop(f,c,0);

           keyinverse := (f, c) -> keyinverseloop(f, c, 0)

> keyinverse(f,"A");

                                 "w"

> subdecipher:=(key,text) -> Implode(map(subs(K=key,(x->keyinverse(K,x))),(Explode(text))));

  subdecipher := (key, text) -> :-Implode(

        map(subs(K = key, x -> keyinverse(K, x)), :-Explode(text)))

> subdecipher(f,"TVLLHAHNLO");

                             "helloworld"

> # We can develop codes more economically using lists to represent
> # cipher alphabets:
> 
> testalphabet := ["j","c","r","z","g","m","y","u","o","a","i","x","v","s","q","w", "l","f","d","t","b","k","n","p","h","e"];

  testalphabet := ["j", "c", "r", "z", "g", "m", "y", "u", "o", "a",

        "i", "x", "v", "s", "q", "w", "l", "f", "d", "t", "b", "k",

        "n", "p", "h", "e"]

> F:=x->Capitalize(testalphabet[alphabet(x)+1]);

        F := x -> :-Capitalize(testalphabet[alphabet(x) + 1])

> subcipher(F,"helloworld");

                             "UGXXQNQFXZ"

> subdecipher(F,%);

                             "helloworld"

> # The next ciphers we discuss will be "block ciphers"; this means that we
> # encode "blocks" of letters rather than single letters.  
> 
> blocks:=(n,L)-> if nops (L) <= n then [L] else [L[1..n],op(blocks(n,L[(n+1)..nops(L)]))] end if;

  blocks := proc(n, L)
option operator, arrow;
    if nops(L) <= n then [L]
    else [L[1 .. n], op(blocks(n, L[n + 1 .. nops(L)]))]
    end if
end proc

> unblock:=  L -> if nops (L) = 1 then L[1] else [op(L[1]),op(unblock(L[2..nops(L)]))] end if;

  unblock := proc(L)
option operator, arrow;
    if nops(L) = 1 then L[1]
    else [op(L[1]), op(unblock(L[2 .. nops(L)]))]
    end if
end proc

> blocks(3,Explode("helloworld"));

      [["h", "e", "l"], ["l", "o", "w"], ["o", "r", "l"], ["d"]]

> unblock(%);

          ["h", "e", "l", "l", "o", "w", "o", "r", "l", "d"]

> # Our next cipher, the Vigenere cipher, is a block cipher variant of the
> # Shift Cipher.
> encodeblock:=(key,block)->((map(alphabet,Explode(key))[1..nops(block)])+block)mod 26;

  encodeblock := (key, block) ->

        (map(alphabet, :-Explode(key))[1 .. nops(block)] + block) mod

        26

> vigenere:=(key,text)-> Implode(map(alphabetinv,  unblock( map (subs(K=key,(x->encodeblock(K,x))           ) , blocks(  nops(Explode(key))  , map(alphabet,Explode(text))   )  )     )      ));

  vigenere := (key, text) -> :-Implode(map(alphabetinv, unblock(map(

        subs(K = key, x -> encodeblock(K, x)),

        blocks(nops(:-Explode(key)), map(alphabet, :-Explode(text)))))))

> vigenere("hi","helloworld");

                             "OMSTVEVZSL"

> vigenere("cipher","thisisnotreallysoverysecure");

                    "VPXZMJPWIYIRNTNZSMGZNZITWZT"

> save (vigenere ,"vigenere.m");
> # We develop Vigenere decryption
> 
> decodeblock:=(key,block)->(block-(map(alphabet,Explode(key))[1..nops(block)]))mod 26;

  decodeblock := (key, block) ->

        (block - map(alphabet, :-Explode(key))[1 .. nops(block)]) mod

        26

> unvigenere:=(key,text)-> LowerCase(Implode(map(alphabetinv,  unblock( map (subs(K=key,(x->decodeblock(K,x))           ) , blocks(  nops(Explode(key))  , map(alphabet,Explode(LowerCase(text)))   )  )     )      )));

  unvigenere := (key, text) -> :-LowerCase(:-Implode(map(alphabetinv,

        unblock(map(subs(K = key, x -> decodeblock(K, x)), blocks(

        nops(:-Explode(key)),

        map(alphabet, :-Explode(:-LowerCase(text)))))))))

> save (unvigenere,"unvigenere.m");
> unvigenere("cipher","VPXZMJPWIYIRNTNZSMGZNZITWZT");

                    "thisisnotreallysoverysecure"

> #  The Vigenere cipher is much more secure than the ciphers discussed so far,
> #  but we will be able to break it.
> with(linalg);

  [BlockDiagonal, GramSchmidt, JordanBlock, LUdecomp, QRdecomp,

        Wronskian, addcol, addrow, adj, adjoint, angle, augment,

        backsub, band, basis, bezout, blockmatrix, charmat, charpoly,

        cholesky, col, coldim, colspace, colspan, companion, concat,

        cond, copyinto, crossprod, curl, definite, delcols, delrows,

        det, diag, diverge, dotprod, eigenvals, eigenvalues,

        eigenvectors, eigenvects, entermatrix, equal, exponential,

        extend, ffgausselim, fibonacci, forwardsub, frobenius,

        gausselim, gaussjord, geneqns, genmatrix, grad, hadamard,

        hermite, hessian, hilbert, htranspose, ihermite, indexfunc,

        innerprod, intbasis, inverse, ismith, issimilar, iszero,

        jacobian, jordan, kernel, laplacian, leastsqrs, linsolve,

        matadd, matrix, minor, minpoly, mulcol, mulrow, multiply,

        norm, normalize, nullspace, orthog, permanent, pivot,

        potential, randmatrix, randvector, rank, ratform, row, rowdim,

        rowspace, rowspan, rref, scalarmul, singularvals, smith,

        stackmatrix, submatrix, subvector, sumbasis, swapcol, swaprow,

        sylvester, toeplitz, trace, transpose, vandermonde, vecpotent,

        vectdim, vector, wronskian]

> 
> # linear algebra is needed for the development of our next block cipher,
> # the Hill cipher.
> 
> # we need to use matrices
> 
> A:=array(1..3,1..3,[[1,2,3],[3,5,7],[1,0,2]]);

                               [1    2    3]
                               [           ]
                          A := [3    5    7]
                               [           ]
                               [1    0    2]


                                  -3

> modinverse := A -> if gcd(det(A),26) <> 1 then "error" else map((x->x mod 26),inverse(A)) end if;

  modinverse := proc(A)
option operator, arrow;
    if gcd(det(A), 26) <> 1 then "error"
    else map(x -> x mod 26, inverse(A))
    end if
end proc

> modinverse (A);

                           [14    10    9]
                           [             ]
                           [17     9    8]
                           [             ]
                           [19     8    9]

> B:= array(1..4,1..4,[[0,0,0,4],[1,3,5,7],[2,0,8,9],[3,3,3,3]]);

                            [0    0    0    4]
                            [                ]
                            [1    3    5    7]
                       B := [                ]
                            [2    0    8    9]
                            [                ]
                            [3    3    3    3]

> modinverse(B);det(B);

                               "error"


                                 -240

> # our keys will be matrices with inverses mod 26 -- we use the key
> # to encode blocks of characters of length the order of the matrix.
> blocktomatrix := x -> array(1..nops(x),1..1,map((c->[c]),x));

 blocktomatrix := x -> array(1 .. nops(x), 1 .. 1, map(c -> [c], x))

> blocktomatrix([1,2,3]);

                                 [1]
                                 [ ]
                                 [2]
                                 [ ]
                                 [3]

> matrixtoblock:= x-> convert(convert(x,Vector),list);

       matrixtoblock := x -> convert(convert(x, Vector), list)

> matrixtoblock(blocktomatrix([1,2,3]));

                              [1, 2, 3]

> modmultiply:=(A,B) -> map((x->x mod 26),multiply(A,B));

     modmultiply := (A, B) -> map(x -> x mod 26, multiply(A, B))

> modmultiply(A,modinverse(A));

                            [1    0    0]
                            [           ]
                            [0    1    0]
                            [           ]
                            [0    0    1]

> multiply(A,modinverse(A));  #not at all the same thing!

                         [105     52     52]
                         [                 ]
                         [260    131    130]
                         [                 ]
                         [ 52     26     27]

> # this is called zerolist because it originally created a list of zeroes,
> # but a list of random numbers is better.
> zerolist:=n ->if n<=0 then [] else [rand(),op(zerolist(n-1))] end if;zerolist(3);

  zerolist := proc(n)
option operator, arrow;
    if n <= 0 then []
    else [rand(), op(zerolist(n - 1))]
    end if
end proc


               [188302655538, 10818866476, 54310788175]

> fixblock:=(n,block)-> if n>nops(block) then [op(block),op(zerolist(n-nops(block)))] else block end if; fixblock(7,[3,4,5]);

  fixblock := proc(n, block)
option operator, arrow;
    if nops(block) < n then
        [op(block), op(zerolist(n - nops(block)))]
    else block
    end if
end proc


   [3, 4, 5, 542136407374, 106205605523, 687223946800, 25812242019]

> hillblockencode:=(key,block)->matrixtoblock(modmultiply(key,blocktomatrix(fixblock(rank(key),block))));

  hillblockencode := (key, block) -> matrixtoblock(

        modmultiply(key, blocktomatrix(fixblock(rank(key), block))))

> hillencode:=(key,text)-> if modinverse(key) = "error" then "bad key" else Implode(map(alphabetinv,  unblock( map (subs(K=key,(x->hillblockencode(K,x))           ) , blocks(  rank(key)  , map(alphabet,Explode(text))   )  )     )      )) end if;

  hillencode := proc(key, text)
option operator, arrow;
    if modinverse(key) = "error" then "bad key"
    else :-Implode(map(alphabetinv, unblock(map(
        subs(K = key, x -> hillblockencode(K, x)),
        blocks(rank(key), map(alphabet, :-Explode(text)))))))
    end if
end proc

> hillencode(A,"thisisreallyquitesecure");

                      "FSJKMCZTRBWHCWGDVDQGSKKH"

> # develop decoding
> 
> hillblockdecode:=(key,block)->matrixtoblock(modmultiply(modinverse(key),blocktomatrix(fixblock(rank(key),block))));

  hillblockdecode := (key, block) -> matrixtoblock(modmultiply(

        modinverse(key), blocktomatrix(fixblock(rank(key), block))))

> hilldecode:=(key,text)-> if modinverse(key) = "error" then "BAD KEY" else LowerCase(Implode(map(alphabetinv,  unblock( map (subs(K=key,(x->hillblockdecode(K,x))           ) , blocks(  rank(key)  , map(alphabet,Explode(LowerCase(text)))   )  )     )    )  )) end if;

  hilldecode := proc(key, text)
option operator, arrow;
    if modinverse(key) = "error" then "BAD KEY"
    else :-LowerCase(:-Implode(map(alphabetinv, unblock(map(
        subs(K = key, x -> hillblockdecode(K, x)), blocks(
        rank(key),
        map(alphabet, :-Explode(:-LowerCase(text)))))))))
    end if
end proc

> hilldecode(A,"FSJKMCZTRBWHCWGDVDQGSZTR");

                      "thisisreallyquitesecurea"

> # the need to expand text so that the matrix multiplication works leads
> # to the extra "a" at the end.
> 
> hillencode(B,"thisisnotretrievable");

                              "bad key"

> hilldecode(B,"UYEAERMDYPHVGAVUQIUW");

                              "BAD KEY"

> hillencode(A,"thesearethetimesthattrymenssouls");

                 "TQBAWSEWDUSTSIQZQGRUMXVPGVOCEGKCV"

> hilldecode(A,%);

                 "thesearethetimesthattrymenssoulsf"

> C:=array(1..5,1..5,[[1,2,3,4,5],[5,4,4,2,1],[4,6,7,9,2],[4,2,3,4,7],[2,3,4,5,6]]);

                          [1    2    3    4    5]
                          [                     ]
                          [5    4    4    2    1]
                          [                     ]
                     C := [4    6    7    9    2]
                          [                     ]
                          [4    2    3    4    7]
                          [                     ]
                          [2    3    4    5    6]

> modinverse(C);

                     [25     8    16     3     8]
                     [                          ]
                     [ 9     1     3     0    13]
                     [                          ]
                     [ 7     1     0     0    20]
                     [                          ]
                     [ 9    15     5    14    24]
                     [                          ]
                     [ 1     1     2     9    14]

> hillencode(C,"thisisaverysecretmessagethatyouwillhavetroubledeciphering");

    "NROIVARDKIJVYLWCOAYHRLGFMWRPTIFTZJZZQPGYIALDTSISUNTFNCSHQGKN"

> hilldecode(C,%);

    "thisisaverysecretmessagethatyouwillhavetroubledecipheringnfv"

> # the cryptanalysis of this is improved by making fixblock add random letters
> # rather than just a as the first version did.
> # you might also want to add noise letters to hide information about the
> # length of your key!
> 
> 
> 
> 
> 
> 
> 
> 
>