My RSA algorithm only works for very short words

Question

My RSA algorithm is working fine for 3 letter words like "cat", but once the word gets longer I get an error message: Exception: decipher2.hs:(37,1)-(62,19): Non-exhaustive patterns in function numToLet

My programs works according to the following steps

For enciphering

• Convert a string of letters to a string of numbers, where each letter is assigned to a specific number.
• Combine the string of numbers to form one larger number.
• Using appropriate values of p and q, calculate n and also choose a suitable number e which is co-prime to n (as this is an internal process, keeping p and q secret is unimportant but may be done)
• Perform the RSA algorithm in order to produce the “cipher number”

For deciphering

• Calculate the totient φ(n), using p and q (whereφ(n) = (p-1) * (q-1) )
• Write into code the Euclidean algorithm for finding the greatest common divisor of two numbers.
• Write into code the back substitution portion so it commutatively forms the Extended Euclidean algorithm.
• calculate the private key.
• Include some kind of option of storing the private key so that this function does not need to be carried out every time (in order to improve speed).
• The deciphering Algorithm of the RSA encryption should be carried out.
• The result should be split into a string of numbers (in an opposite process to how it was combined in Stage 2 of the enciphering process).
• The string of numbers should be converted to a string of letters (using the same values that were used in the enciphering process).

I have chosen not to include the calculating key part as it is a separate programme and must be correct (as short words are able to be deciphered). I have tried using smaller values of p and q, but this does not work either, does anybody know why longer words do not work (even for smaller primes) and/or how I could fix it?

My code for encryption is:

import Data.List
letToNum c'' = (let (Just n) = elemIndex c'' ['a'..'z'] in n) + 10

combine = foldl addDigit 0
    where addDigit num i' = (10 ^ (floor $ log (fromIntegral i') / log 10 + 1))*num + i'

firstTwo xs = toInteger (combine (map letToNum xs))

p' = 2^2048 - 1942289
q' = 2^2048 - 2^1056 + 2^736 - 2^320 + 2^128 + 1
n' = p' * q'
e' = 7

newtype ModN = ModN (Integer, Integer) deriving (Eq, Show)
instance Num ModN where
  ModN (x, m) + ModN (y, m') | m == m' = ModN ((x + y) `mod` m, m)
                             | otherwise = undefined
  ModN (x, m) * ModN (y, m') | m == m' = ModN ((x * y) `mod` m, m)
                             | otherwise = undefined
  negate (ModN (x, m)) = ModN ((- x) `mod` m, m)
  abs _ = undefined
  signum _ = undefined
  fromInteger _ = undefined

modPow :: Integer -> Integer -> Integer -> Integer
modPow _ 0 m = 1 `mod` m
modPow a b m = c
  where a' = ModN (a, m)
        ModN (c, _) = a' ^ b

encipherA z' = modPow z' e' n'

encipher xs = encipherA (firstTwo xs)

My code for decryption is:

p' = 2^2048 - 1942289
q' = 2^2048 - 2^1056 + 2^736 - 2^320 + 2^128 + 1
n' = p' * q'
d'=149198411630450358098821815816660626082852035578197682912033354754850558281651065264118115990713936905841443816348466119712510491169399086751890869693052182563708139506244285477194512876340531187775438573122278032339474119913958963667476383477798088213829701243686243438754864105731229873495425397653296705562025639940130672903361904637280085880562426594784029436599468688448179303703337724326069153629191476697420768451884440453280134491448395404958914592441919126201747433884753502442027069825305163272842897505994155682996130741544296475635538035696205346055652365820232813677363525296188331517668300986037331017823989462119054758685224752255850280255541024098528388784743634162996954090230161430468033874779937253936100340449079832503240200984659315256173082971785802328581652375418902448324739292188909509903808503871246982928186837296358844444348158079557757543904495890483033995844854839625810784987612815774450940850973031117459144355531047129541648317845165848539683500066541165782574432790936862217277817101197569391139502130923768985262346549685855947859864917650782062626099395684514986479824104485607000960030713840667632064934158997031779846656288570984548383771118345091911988849410656041321592285731293207858515766711

newtype ModN = ModN (Integer, Integer) deriving (Eq, Show)
instance Num ModN where
  ModN (x, m) + ModN (y, m') | m == m' = ModN ((x + y) `mod` m, m)
                             | otherwise = undefined
  ModN (x, m) * ModN (y, m') | m == m' = ModN ((x * y) `mod` m, m)
                             | otherwise = undefined
  negate (ModN (x, m)) = ModN ((- x) `mod` m, m)
  abs _ = undefined
  signum _ = undefined
  fromInteger _ = undefined

modPow :: Integer -> Integer -> Integer -> Integer
modPow _ 0 m = 1 `mod` m
modPow a b m = c
  where a' = ModN (a, m)
        ModN (c, _) = a' ^ b

decipherA c' = modPow c' d' n'

numToLet "10" = "a"  
numToLet "11" = "b"  
numToLet "12" = "c"
numToLet "13" = "d"
numToLet "14" = "e"
numToLet "15" = "f"
numToLet "16" = "g"
numToLet "17" = "h"
numToLet "18" = "i"
numToLet "19" = "j"
numToLet "20" = "k" 
numToLet "21" = "l"
numToLet "22" = "m"
numToLet "23" = "n"
numToLet "24" = "o"
numToLet "25" = "p"
numToLet "26" = "q"
numToLet "27" = "r"
numToLet "28" = "s"
numToLet "29" = "t"
numToLet "30" = "u"
numToLet "31" = "v"
numToLet "32" = "w"
numToLet "33" = "x"
numToLet "34" = "y"
numToLet "35" = "z"
output xs = putStrLn $ concat (map numToLet xs)

partition :: Int -> [a] -> [[a]]
partition _ [] = []
partition n xs = (take n xs) : (partition n (drop n xs))

decipher j' = map numToLet (partition 2 (show (decipherA j')))

Thanks for any help, I really appreciate it.

Answer 1

Since the RSA algorithm outputs a number smaller than the modulus n, you obviously can't encrypt more than n different messages (the messages 0 to n - 1).

*RSA> decipherA (encipherA (n' - 1)) == n' - 1
True
*RSA> decipherA (encipherA n') == n'
False

For strings longer than a certain lengths, you will pass that threshold.

The typical solution for this is to use RSA only to encrypt a randomly generated session key. This session key is then used to symmetrically encrypt the message (for example, using AES). The other side can use RSA to reconstruct the session key and decrypt the message.

EDIT: I just saw that apart from this unevitable restriction of the RSA algorithm itself, you somewhere introduced another bug in your string encoding. Your encoder and decoder just don't fit together:

*RSA> let encode = firstTwo
*RSA> let decode x = map numToLet (partition 2 (show x))
*RSA> decode (encode "catcatcatcat")
["x","g","f","c","*** Exception: RSA.hs:(41,1)-(66,19): Non-exhaustive patterns in function numToLet

The problem is integer overflow: combine has type [Int] -> Int, but Int can hold only values up to 2^31 - 1, which corresponds to 4 characters in your encoding. You can fix that by using Integer:

letToNum :: Char -> Integer
letToNum c'' = (let (Just n) = fmap toInteger (elemIndex c'' ['a'..'z']) in n) + 10

combine :: [Integer] -> Integer
combine = foldl addDigit 0
    where addDigit num i' = 100*num + i'

firstTwo xs = combine (map letToNum xs)

As you can see, it helps to add type signatures. I also removed the log expression, I don't know what it was meant to do, but I guess it was either unnecessary or even wrong...