% Copyright (C) 2004 Brian Alliet \documentclass[11pt]{article} \usepackage{palatino} \usepackage{fullpage} \usepackage{parskip} \usepackage{lhs} \usepackage{amsmath} \def\base{{\tt base}} \begin{document} \title{Simple Ciphers} \author{Brian Alliet} \maketitle \section{Introduction} This is a Haskell implementation of some simple cryptographic ciphers. Encryption, decryption, and cryptanalysis/breaking functions are provided for the following ciphers: \begin{itemize} \item{Shift Cipher} - $x \rightarrow (x+\kappa)$ (mod 26) \item{Substitution Cipher} - map based on a permutation of the alphabet \item{Affine Cipher} - $x \rightarrow \alpha x + \beta$ (mod 26) \item{Vigen\`{e}re Cipher} - shift based on a repeating vector \item{The Playfair Cipher} - substitute based on a matrix \item{The ADFGX Cipher} - substitute and transform based on a matrix and a keyword \item{The Hill Cipher} - multiply the message by a matrix \item{The Homework 2 Cipher} - a hacked up Vigen\`{e}re cipher \end{itemize} A simple command line user interface is also provided for all the above functions. \ignore{ \begin{code} module SimpleCiphers ( toNumbers,fromNumbers, languages, ciphers, shiftEncrypt,shiftDecrypt,shiftBreak,shiftValidKey, substEncrypt,substDecrypt,substValidKey, affineEncrypt,affineDecrypt,affineBreak,affineValidKey, vigenereEncrypt,vigenereDecrypt,vigenereBreak,vigenereValidKey, playfairEncrypt,playfairDecrypt,playfairValidKey, adfgxEncrypt,adfgxDecrypt,adfgxValidKey, hillEncrypt,hillDecrypt,hillPBreak,hillValidKey, CipherFunctions, Cipher, Break, PBreak ) where import Maybe import List import Char (isAlpha,toLower,ord,chr) import Array (accumArray,elems) import Brianweb.Math import Brianweb.Math.NumberTheory import Brianweb.Math.Matrix import Brianweb.Misc import Brianweb.List \end{code} } \section{Data Types} \begin{code} type Language = [Double] type Cipher a = a -> [Int] -> [Int] type Break a = [Int] -> Language -> [(a,[Int])] type PBreak a = [Int] -> Break a type ValidKey a = a -> Bool \end{code} The the three major functions of this program are encrypting messages, decrypting cypher-text, and performing cryptanalysis and breaking cypher-texts. Both encryption and decryption take a key and an input (as a string of integers) then mutate the data somehow, and return a new string of integers. This is represented by the Cipher type. Breaking the encryption on a piece of cypher-text requires two pieces of information, a list of frequencies for each possible value in the cypher-text, and the cypher-text itself. The break function takes these inputs and returns a list of possible plain-text possibilities including the key used to generate it. A known plaintext attack requires the known plaintext in addition to the language and ciphertext. \begin{code} base :: Int base = 26 \end{code} All the ciphers functions below operate on Ints mod \base \begin{code} padding :: Int padding | base == 26 = head $ toNumbers ['x'] | otherwise = error "padding needs to be specialized for this base" \end{code} Many block ciphers require the plaintext to be padded to fit evenly into a block. {\tt padding} is the value to use as the padding. {\tt padding} {\bf must} be within [0..\base-1]. \begin{code} toNumbers :: [Char] -> [Int] toNumbers | base == 26 = map ((subtract $ ord 'a') . ord . toLower) . filter isAlpha | otherwise = error "toNumbers needs to be specialized for this base" fromNumbers :: [Int] -> [Char] fromNumbers | base == 26 = map $ chr . (+ord 'a') | otherwise = error "fromNumbers needs to be specialized for this base" \end{code} It is much easier to deal with messages as lists of numbers internally, however, most messages originate as strings. {\tt toNumbers} converts a string to a list of integers representing the string. This strips out non-alphabetic characters to fit them into the (mod \base) system. {\tt fromNumbers} converts the list of integers back into text. \section{Stream Ciphers} \subsection{The Shift Cipher} \begin{code} shiftEncrypt :: Cipher Int shiftEncrypt = map . (addMod base) \end{code} The shift cypher encrypts messages by shifting each character in the message by a fixed amount. (a $\rightarrow$ D, b $\rightarrow$ E, c $\rightarrow$ F, etc). This shifting wraps around (so the result is always in (mod \base)) so x $\rightarrow$ A, etc. \begin{code} shiftDecrypt :: Cipher Int shiftDecrypt = shiftEncrypt . negate \end{code} Decrypting these messages is simply a matter of shifting the characters back in the other direction (D $\rightarrow$ a, etc). It can be though of as ``encrypting'' the message using the additive inverse of the key used to encrypt the message originally. \begin{code} shiftBreak :: Break Int shiftBreak = bruteForceBreak shiftDecrypt [0..base-1] \end{code} The shift cipher can easily be broken using a brute force attack. More sophisticated attacks are possible but the key space is so small using brute force is perfectly adequate. The key space is simply [0..\base-1]. \begin{code} shiftValidKey :: ValidKey Int shiftValidKey = const True \end{code} Any integer is a valid key for the shift cipher. \subsection{The Substitution Cipher} \begin{code} substEncrypt :: Cipher [Int] substEncrypt = map . (!!) \end{code} The substitution cipher maps each character of the original plain-text to a new character using a permutation of the alphabet (the key). \begin{code} substDecrypt :: Cipher [Int] substDecrypt key = substEncrypt $ map (fromJust.flip elemIndex key) [0..base-1] \end{code} Decryption these messages is simply a matter of ``encrypting'' them using the inverse of the original key. If the original key was BCA the inverse would be CAB. The inverse is obtained by mapping each possible element to its position in the original key. The substitution cipher cannot easily be broken by brute force, but with a little knowledge of the characteristics of the message`s original language breaking it is pretty straightforward. The process, however, does need a good deal of human interaction and would be fairly difficult to code. Therefor, a break function is not provided for the substitution cipher. \begin{code} substValidKey :: ValidKey [Int] substValidKey = and . map (==1) . letterCounts \end{code} A set of integers containing exactly one of every letter is a valid subsitiution key. \subsection{Affine Cipher} \begin{code} affineEncrypt :: Cipher (Int,Int) affineEncrypt (a,b) = map $ \x -> (a*x+b) `mod` base \end{code} The affine cipher maps each character of the original plain-text to a new character using an affine function ($\alpha x + \beta$). To ensure multiple plain-text characters aren`t mapped to the same ciphertext character $\gcd(\alpha,26)$ must equals 1. \begin{code} affineDecrypt :: Cipher (Int,Int) affineDecrypt (a,b) = map $ \x -> (multInvMod base a * (x-b)) `mod` base \end{code} Decrypting these messages is simply a matter of inverting the affine function. The inversion of $\alpha x + \beta$ is $\frac{1}{\alpha}(x-\beta)$. However, $\frac{1}{\alpha}$ cannot be represented in (mod \base) so we need to find another number to represent the same thing. The multiplicative inverse of $\alpha$ is a number that when multiplied by $\alpha$ (mod \base) results in 1. After the multiplicative inverse is found (using {\tt multInvMod}) we can simply use it in place of $\frac{1}{\alpha}$. \begin{code} affineBreak :: Break (Int,Int) affineBreak = bruteForceBreak affineDecrypt [(a,b) | b <- [0..base-1], a <- [x | x <- [0..base-1], gcd base x == 1]] \end{code} Brute force can be used to break the affine cipher over $Z_m$ for small values of $m$. When $m = 26$ there are only 312 possible keys. Even with larger values of $m$ brute force is still a viable method of attack, it just takes longer. The possible keys for the brute force attack consist of every possible combination of $\alpha$ and $\beta$ drawing $\beta$ from [0..\base-1] and $\alpha$ from every element of [0..\base-1] where $\gcd(n,26)=1$. \begin{code} affineValidKey :: ValidKey (Int,Int) affineValidKey (a,_) = gcd a base == 1 \end{code} Any ($\alpha$,$\beta$) pair where alpha is relativly prime is a valid affine cipher key. \subsection{Vigen\`{e}re Cipher} \begin{code} vigenereEncrypt :: Cipher [Int] vigenereEncrypt = zipWith (addMod base) . cycle \end{code} The Vigen\`{e}re Cipher uses a vector to shift each plain-text character. The first character of the message is shifted by the value of the first element of the vector, the second shifted by the second element of the vector, etc. The vector is repeated as necessary to accommodate the entire message (the vector can be though of an infinitely long repetition of the key). \begin{code} vigenereDecrypt :: Cipher [Int] vigenereDecrypt = vigenereEncrypt . map negate \end{code} Decrypting these messages is simply a matter of ``encrypting'' the ciphertext with a vector that contains the additive inverse of each of the original keys. This reverses all the shifts done by the encryption yielding the original message. Breaking the Vigen\`{e}re cipher is significantly more complicated that breaking the affine and substitution ciphers. A brute force attack is not possible because of the huge key size. Instead, educated guesses are made about the key size and the key values using character frequency statistics of the language of the clear-text. The first step to breaking the Vigen\`{e}re cipher is finding the most probable key length. \begin{code} vigenereCoincidences :: (Int -> [Int] -> [Int]) -> [Int] -> [Int] vigenereCoincidences pp m = keySortRev $ map (\x -> (shiftOverlap x,x)) [1..10] where overlap = ((length . filter id).) . zipWith (==) shiftOverlap n = overlap m' (drop n m') where m' = pp n m \end{code} The most probable key length is the displacement of the ciphertext that when compared to the original ciphertext yields the most overlap. This is calculated by shifting the ciphertext to the left by various different amounts, finding the amount of overlap for each shift, and sorting the shifts by the amount of overlap. This works because certain letters show up more frequently than others. Once you shift by the same amount as the length of the key ``Es'' start matching up with other ``Es'', etc. Once the most probable key length is found the actual values of the key must be found. This is done by a series of calculations based on the frequency distribution of the letters in the ciphertext. The values of each element of the key are each found individually. \begin{code} vigenereShifts :: Language -> [Int] -> [Int] vigenereShifts lang text = keySortRev $ map (\x -> (langScore (a x) text,x)) [0..base-1] where a x = e ++ s where (s,e) = splitAt (length lang - x) lang \end{code} Calculating the shift at a given position (which is the value of this key element) is simply a matter of finding how much we have to shift the frequency distribution for the language to best fit the frequency distribution of the elements of ciphertext effected by this key element. The frequency distribution off all the characters in the expected language for the plaintext is $A_0$. This distribution shifted to the left by $n$ is $A_n$. Finding the best shift is simply a matter if calculating the ``score'' for how well the plaintext matches up to each possible shifted frequency distribution. This score is calculated by {\tt langScore} (see Section~\ref{langScore}). \begin{code} vigenereKeys :: (Int -> [Int] -> [Int]) -> [Int] -> Language -> [[Int]] vigenereKeys preproc text lang = concat $ map keysOfLen $ take 3 $ vigenereCoincidences preproc text where keysOfLen len = positionPerms $ map (elements len) [0..len-1] elements len pos = take 3 $ vigenereShifts lang $ takeEvery len (drop pos text') where text' = preproc len text vigenereBreak :: Break [Int] vigenereBreak text = map (\x -> (x,vigenereDecrypt x text)) . vigenereKeys (const id) text \end{code} Finally, combining everything above together we get the final {\tt vigenereKeys} function. We find the most likely few key lengths, then find the most likely keys of that length. To find the most likely keys of a given length we find the most likely few shifts at each position then take every possible permutation of those shifts. {\tt preproc} is a hack for the Homework 2 cipher. It modifies the ciphertext based on the key length. \begin{code} vigenereValidKey :: ValidKey [Int] vigenereValidKey = (/=[]) \end{code} Any non-empty string of integers is a valid Vigen\`{e}re cipher key. \subsection{Homework 2 Cipher \bf{FIXME - Find the real name}} The homework 2 cipher is a hacked up Vigen\`{e}re cipher. The only difference between the two is that instead of simply repeating the key (``abcabcabc\ldots'') the homework2 cipher increments each element of the key by 1 every time it is repeated (``abcbcdcde\ldots''). \begin{code} hw2Transform :: (Int -> Int -> Int) -> Int -> [Int] -> [Int] hw2Transform op n = concat . map (\(a,b) -> map (op a) b) . zip [0..] . chunkify n \end{code} Ciphertexts encoded using the homework2 cipher can be made to look like text encoded with the standard Vigen\`{e}re cipher by simply preprocessing the text to take into account the additional shifts. First we break up the text into chunks of length $n$ (where n is the key length, or a possible key length in the case of the break function), then we add or subtract 1 to all the elements of the second chunk, 2 to all the elements of the third chunk, etc. This essentially reverses the damange done by the homework2 cipher and allows use the resulting text with an unmodified Vigen\`{e}re cipher. The same transformation could also be applied to the key (after it has been run through {\tt cycle}) for the encrypt and decrypt function. This would better match the process decribed in the homework assignment, however, for consistency with the break function, we opt to apply it to the text. \begin{code} hw2Encrypt :: Cipher [Int] hw2Encrypt k = vigenereEncrypt k . hw2Transform (addMod base) (length k) \end{code} {\tt hw2Encrypt} simply hacks up the plaintext and passes it on to the Vigen\`{e}re encrypt function. \begin{code} hw2Decrypt :: Cipher [Int] hw2Decrypt k = vigenereDecrypt k . hw2Transform (addMod base . negate) (length k) \end{code} {\tt hw2Decrypt} simple de-hacks up the ciphertext and passes it on to the Vigen\`{e}re decrypt function. \begin{code} hw2Break :: Break [Int] hw2Break text = map (\x -> (x,hw2Decrypt x text)) . vigenereKeys (hw2Transform (addMod base . negate)) text \end{code} {\tt hw2Break} works exactly like {\tt vigenereBreak} except the {\tt hw2Transform} function is used to preprocess the text. {\tt vigenereKeys} takes a ``preprocessor'' function that will be applied to the key length and ciphertext before doing any operations on the ciphertext. {\tt hw2Transform} is used to de-hack up the ciphertext before processing. \begin{code} hw2ValidKey :: ValidKey [Int] hw2ValidKey = (/=[]) \end{code} Any non-empty string of integers is a valid homework2 cipher key. \section{Block Ciphers} \begin{code} keywordMatrix :: [Int] -> [[Int]] keywordMatrix kw | base == 26 = toMatrix 5 5 $ keywordMatrixFilter $ (nub kw) ++ [x | x <- [0..base-1], not (x `elem` kw)] | otherwise = error "need to specialize keywordMatrix for this base" \end{code} {\tt keywordMatrix} turns a keyword into a matrix (a 5x5 matrix when \base == 26). \begin{code} keywordMatrixFilter :: [Int] -> [Int] keywordMatrixFilter | base == 26 = filter (/=9) | otherwise = error "need to specialize keywordMatrixFilter for this base" \end{code} {\tt keywordMatrixFilter} filters out characters from a message that cannot be encoded with the keywordMatrix above (j in the \base == 26 case). \subsection{Playfair Cipher} \begin{code} playfairOp :: Bool -> Cipher [Int] playfairOp rev key = playfairOp' . keywordMatrixFilter where m = keywordMatrix key next = (flip mod $ length m).(if rev then pred else succ) playfairOp' [] = [] playfairOp' [a] = playfairOp' [a,padding] playfairOp' (a:b:xs) | a==b = if rev then playfairOp' xs -- invalid, skip it else playfairOp' (a:padding:b:xs) | ya==yb = m!!ya!!next xa : m!!yb!!next xb : rest | xa==xb = m!!next ya!!xa : m!!next yb!!xb : rest | otherwise = m!!ya!!xb : m!!yb!!xa : rest where (xa,ya) = fromJust $ matrixIndex a m (xb,yb) = fromJust $ matrixIndex b m rest = playfairOp' xs \end{code} The playfair cipher. {\bf FIXME - Document} \begin{code} playfairEncrypt :: Cipher [Int] playfairEncrypt = playfairOp False . filter (/=padding) playfairDecrypt :: Cipher [Int] playfairDecrypt = (filter (/=padding).) . playfairOp True \end{code} The playfair encoding and decoding functions simply run {\tt playfairOp} after doing the appropriate padding filtering. \begin{code} playfairValidKey :: ValidKey [Int] playfairValidKey = const True \end{code} Any string of integers is a valid playfair cipher key. \subsection{ADFGX Cipher} \begin{code} adfgxElements :: [Int] adfgxElements = toNumbers "ADFGX" \end{code} {\tt afgfxElements} are the values to use to label the rows and columns of of the ADFGX matrix. \begin{code} adfgxEncrypt :: Cipher ([Int],[Int]) adfgxEncrypt (matrixKey, key') = step2 . step1 where m = keywordMatrix matrixKey key = nub key' kl = length key step1 = map (adfgxElements!!) . foldr (\(x,y) r -> y:x:r) [] . (map $ fromJust.flip matrixIndex m) step2 i = concat $ map snd $ (sortBy $ \(a,_) (b,_) -> compare a b) $ zip key $ map (\x -> takeEvery kl $ drop x i) [0..kl-1] \end{code} {\tt adfgxEncrypt} is the ADFGX encryption function. {\bf FIXME - Document}. \begin{code} adfgxDecrypt :: Cipher ([Int],[Int]) adfgxDecrypt (matrixKey,key') = step1 . step2 where m = keywordMatrix matrixKey key = nub key' kl = length key step1 (a':b':xs) = case (toIndex a',toIndex b') of (Just a,Just b) -> m!!a!!b : rest _ -> rest where rest = step1 xs toIndex = flip elemIndex adfgxElements step1 _ = [] step2 i = concat $ transpose $ map snd $ (sortBy $ \(a,_) (b,_) -> compare a b) $ getcols (sort key) i where (mincolsize,extra) = quotRem (length i) kl getcols [] [] = [] getcols _ [] = error "should never happen" getcols [] _ = error "should never happen" getcols (x:xs) i' = (n,take consume i') : getcols xs (drop consume i') where n = fromJust $ elemIndex x key consume = mincolsize + (if n < extra then 1 else 0) \end{code} {\tt adfgxDecrypt} is the ADFGX decryption function. {\bf FIXME - Document}. \begin{code} adfgxValidKey :: ValidKey ([Int],[Int]) adfgxValidKey (_,k) = (k/=[]) \end{code} Any matrix/keyword pair with a non-empty keyword is a valid ADFGX key. \subsection{Hill Cipher} \begin{code} hillEncrypt :: Cipher [[Int]] hillEncrypt m = map (flip mod base) . concat.concat . map (flip matrixMul m . (:[])) . chunkify size . pad padding size where size = length m \end{code} The Hill cipher is a block cipher that encrypts messages by multiplying chunks of a message by a square matrix. The message is first broken up into chunks that are the same size as the matrix used to encode the message (padding as necessary). Each chunk is then turned into 1 row matrix and multiplied by the key (a $n$x$n$ square matrix). The resulting 1x$n$ matrix is the encoded value for that chunk. \begin{code} hillDecrypt :: Cipher [[Int]] hillDecrypt = hillEncrypt . matrixInvMod base \end{code} To decrypt messages encoded with the Hill Cipher we just have to ``encrypt'' them with the inverse of the original matrix. This will yield the original message. Unlike most of the previous ciphers the hill cipher cannot easily be broken by using a ciphertext-only attack. It can, however, be broken pretty easily using a known plaintext attack. {\tt hillPBreak} implements a reliable known plaintext attack. \begin{code} hillPBreak :: PBreak [[Int]] hillPBreak pt ct = bruteForceBreak hillDecrypt keys ct where maxn = intSqrt $ min (length pt) (length ct) keys = filter (matrixInvertableMod base) $ map calcKey $ catMaybes $ map possible [1..maxn] possible n = find (matrixInvertableMod base . fst) $ map unzip $ listPerms n $ zip (chunkifyExact n pt) (chunkifyExact n ct) calcKey (p,c) = matrixMulMod base (matrixInvMod base p) c \end{code} When the plaintext is known and of sufficient length we can use it to derrive the plaintext. First we break the plaintext and cipher text up into chunks of size $n$ where $n$ is a guess at the size of the key matrix. Next we find every possible combination of $n$ matrices from the chunks. This results in a set of pairs $n$x$n$ matrices where the rows of each of the two matrices correspond to eachother. For example. If the plaintext was ``abcdefghi'' and the ciphertext was ``jklmnopqr'' then one possible set could be: \[ \left[ \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array} \right] and \left[ \begin{array}{ccc} j & k & l \\ m & n & o \\ p & q & r \end{array} \right] \] These two matrices have an interesting property. If $k$ denotes the key matrix, $p$ denotes the plaintext matrix, and $c$ denotes the ciphertext matrix then $p \times k = c$. This works because multiplying a matrix by another matrix is the same as multiplying each row individually by a matrix and then stacking the results. We're just encrypting $n$ chunks at a time rather than one at a time. Now, given $p \times k = c$ we just need to solve for $k$ to find the key. Multiplying both sides by $p^{-1}$ gets us $p^{-1} \times p \times k = p^{-1} \times c$. This can be simplified to $k = p^{-1} \times c$. Now we have a formula for $k$. Next we simply have to find a plaintext matrix that is invertable (one where the determinant isn't 0 and the gcd of the determinant and \base is 1) and multiply by the ciphertext matrix. This will get us a possible key. We do this for every possible key size to get a list of keys. Finally all the possible keys (0 or 1 for each possible key size) are run though {\tt bruteForceBreak} to sort the keys in order of the meaningfulness of the plaintext they produce. \begin{code} hillValidKey :: ValidKey [[Int]] hillValidKey m = matrixInvertableMod base m && matrixSquare m && length m /= 0 \end{code} Any matrix that is invertable (mod \base) is a valid hill cipher key. \section{Language Statistical Functions} Given a vector, $A_0$, containing a the frequency distribution on all the possible values in the ciphertext a ``score'' can be given to a given string of plaintext that indicates the likelihood of it being meaningful plaintext. \begin{code} letterCounts :: [Int] -> [Int] letterCounts t = elems $ accumArray (+) 0 (0,base-1) [(x,1)|x<-t] \end{code} The first step in performing this calculation is finding a vector, $v$, containing number of times each possible character occurs in the given text. \begin{code} letterFrequency :: [Int] -> [Double] letterFrequency text = map (\x -> (fromIntegral x)/(fromIntegral $ length text)) v where v = letterCounts text \end{code} Next, a vector, $w$ is calculated by dividing each element of $v$ by the total number of elements in the text. This results in a frequency distribution vector similar to the frequency distribution for the whole language ($A_0$). If the given text is in fact meaningful in the given language these two vectors should be very similar. \label{langScore} \begin{code} langScore :: Language -> [Int] -> Double langScore a0 = dotProd a0 . letterFrequency \end{code} Finally, with these two pieces of information in mind ($A_0$ and $w$) we can give the text a ``score'' based on how well it fits the predicted frequency distribution for letters in the given language. This score is calculated by finding the dot product of $w$ and $A_0$. As long as letters that appear frequently in the whole language match up with letters that appear frequently in the text the dot product will be high. \section{Brute Force Breaking Functions} When breaking ciphertexts using brute force every possible key in used to decrypt the ciphertext in the hopes that only one key will yield a meaningful message. Although manually locating this message in the sea of nonsense should be fairly simple, it is tedious. \begin{code} probableKeys :: Cipher a -> Language -> [Int] -> [a] -> [a] probableKeys c l ct = keySortRev . map (\k -> (langScore l (c k ct),k)) \end{code} To make this process a little easier each possible message is given a ``score'' based on the language it is expected to be in. This score is calculated by {\tt langScore} (see Section~\ref{langScore}). {\tt probableBreaks} sorts a list of possible decryptions of a message by their score. \begin{code} bruteForceBreak :: Cipher a -> [a] -> Break a bruteForceBreak c ks ct l = map (\k -> (k,c k ct)) $ probableKeys c l ct ks \end{code} The brute force method of breaking the cypher-text follows the same pattern for every cipher. {\tt bruteForceBreak} takes a decryption function, a list of possible keys, a language, and a piece of cypher-text and returns all possible plain texts for that cypher-text along with the key used to generate it sorted by the likelihood that is a meaningful message. \section{Frequency Distributions for Various Languages} \begin{code} anyLang :: Language anyLang = map average $ transpose $ [snd x | x <- languages,fst x /= "any"] languages :: [(String,Language)] languages = [ -- Obtained from _Introduction to Cryptography with Coding Theory_ -- by Trappe and Washington ("english",[ 0.082,0.015,0.028,0.043,0.127,0.022,0.020,0.061,0.070,0.002, 0.008,0.040,0.024,0.067,0.075,0.019,0.001,0.060,0.063,0.091, 0.028,0.010,0.023,0.001,0.020,0.001]), -- Obtained from http://linguistlist.org/issues/5/5-641.html ("dutch",[ 0.081,0.016,0.000,0.058,0.202,0.000,0.035,0.024,0.072,0.000, 0.025,0.041,0.024,0.107,0.064,0.016,0.000,0.070,0.045,0.072, 0.021,0.027,0.000,0.000,0.000,0.000]), ("any",anyLang)] \end{code} {\tt languages} contains the frequency distribution for letters in various languages. \input{Brianweb/Math.lhs} \section{Cipher Function Lookup Table} \begin{code} type CipherFunctions a = ( String -> a ([Int] -> [Int]), String -> a ([Int] -> [Int]), a (Break String), a (PBreak String), String) ciphers :: Monad a => [(String,CipherFunctions a)] ciphers = [ \end{code} \begin{code} ("shift",( cf shiftEncrypt shiftValidKey readIntegral, cf shiftDecrypt shiftValidKey readIntegral, return $ bf shiftBreak show, fail "This function is not available for this cipher", "An integer between 0 and " ++ (show base))), \end{code} \begin{code} ("subst",( cf substEncrypt substValidKey (return.toNumbers), cf substDecrypt substValidKey (return.toNumbers), fail "This function is not available for this cipher", fail "This function is not available for this cipher", "A list of " ++ (show base) ++ " unique characters")), \end{code} \begin{code} ("affine",( cf affineEncrypt affineValidKey $ tupleMapM readIntegral . splitOn(==','), cf affineDecrypt affineValidKey $ tupleMapM readIntegral . splitOn(==','), return $ bf affineBreak $ \(a,b) -> concat $ [show a,",",show b], fail "This function is not available for this cipher", "A pair of integers in the format alpha,beta")), \end{code} \begin{code} ("vigenere",( cf vigenereEncrypt vigenereValidKey (return.toNumbers), cf vigenereEncrypt vigenereValidKey (return.toNumbers), return $ bf vigenereBreak fromNumbers, fail "This function is not available for this cipher", "A word or string")), \end{code} \begin{code} ("playfair",( cf playfairEncrypt playfairValidKey (return.toNumbers), cf playfairDecrypt playfairValidKey (return.toNumbers), fail "This function is not available for this cipher", fail "This function is not available for this cipher", "A word or string")), \end{code} \begin{code} ("adfgx",( cf adfgxEncrypt adfgxValidKey $ return . tupleMap toNumbers . splitOn (==','), cf adfgxDecrypt adfgxValidKey $ return . tupleMap toNumbers . splitOn (==','), fail "This function is not available for this cipher", fail "This function is not available for this cipher", "A pair of words in the format matrix_letters,keyword")), \end{code} \begin{code} ("hill",( cf hillEncrypt hillValidKey readIntegralMatrix, cf hillDecrypt hillValidKey readIntegralMatrix, fail "This function is not available for this cipher", return $ pf hillPBreak showMatrix, "A square matrix in the format [[1,2,3],[4,5,6],[7,8,9]]")), \end{code} \begin{code} ("hw2",( cf hw2Encrypt hw2ValidKey (return.toNumbers), cf hw2Encrypt hw2ValidKey (return.toNumbers), return $ bf hw2Break fromNumbers, fail "This function is not available for this cipher", "A word or string")) \end{code} \begin{code} ] where cf c v rf s = do x <- rf s if v x then return $ c x else fail $ s ++ " is not a valid key" -- FEATURE: These are sort of ugly bf b t c l = map (\(k,p') -> (t k,p')) (b c l) pf b t p c l = map (\(k,p') -> (t k,p')) (b p c l) \end{code} {\tt ciphers} maps cipher names to their function. These functions wrap the real functions with functions that map the key values to and from strings and do error checking. \input{SimpleCiphersMain.lhs} \input{Brianweb/List.lhs} \input{Brianweb/Misc.lhs} \input{Brianweb/IO.lhs} \section{Availability} The latest version of SimpleCiphers.lhs (which contains this document and the Haskell souce) is available under an open souce license from: \begin{verbatim} http://darcs.brianweb.net/ritcrypto \end{verbatim} \end{document}