simple RSA implementation

rsa.hs

module RSA where

-- extendedGcd(a,b) = (x,y), such that a*x + b*y = gcd(a,b)
extendedGcd :: Integral a => (a, a) -> (a, a)
extendedGcd (a, b) = if b == 0 then (1, 0) else (x, y)
  where
    (q, r) = divMod a b
    (s, t) = extendedGcd (b, r)
    (x, y) = (t, s - q * t)

-- moduloInverse a n = b, such that a*b = 1 [mod n]
moduloInverse :: Integral a => a -> a -> a
moduloInverse a n = mod (fst (extendedGcd (a, n))) n

-- RSA routines.

-- A legal public exponent e is between
-- 1 and (p-1)*(q-1) and gcd(e, (p-1)*(q-1)) = 1
isLegalExponent :: Integral a => a -> a -> a -> Bool
isLegalExponent e p q = (e > 1) && (e < n) && (gcd e n == 1)
  where n = (p-1)*(q-1)

-- The private exponent is the inverse of the public exponent, mod n
privateExponent :: Integral a => a -> a -> a -> a
privateExponent e p q = if isLegalExponent e p q
                            then moduloInverse e n
                            else error "Not a legal public exponent"
  where
    n = (p-1)*(q-1)

-- An encrypt message is c = m^e [mod n]
encrypt :: Integral a => a -> a -> a -> a
encrypt m e n = if m > n
                    then error "The modulus is too small"
                    else mod (m^e) n

-- An decrypt message is m = c^d [mod n]
decrypt :: Integral a => a -> a -> a -> a
decrypt c d n = mod (c^d) n

-- RSA example

p = 41 -- A "large" prime
q = 47 -- Another "large" prime
n = p*q -- public modulus

e = 7 -- the public exponent
d = privateExponent e p q -- the private exponent

plaintext = 42
ciphertext = encrypt plaintext e n
decryptedCiphertext = decrypt ciphertext d n

main = do
    putStrLn "The plaintext is:"
    print plaintext
    putStrLn ""
    putStrLn "The ciphertext is:"
    print ciphertext
    putStrLn ""
    putStrLn "The decrypted ciphertext is:"
    print decryptedCiphertext
    putStrLn ""