A Public and Private Key generator for RSA I made an RSA encryption public and private key generator and I would like some feedback. In particular, as this is cryptography related I want to know if I have done anything that might be considered insecure.

FYI, the Crypto.Random module is from the crypto-api package.

(Disclaimer, I am not using this for anything serious, just to help understand how the process works.)

import System.Random
import Crypto.Random
import Crypto.Random.DRBG
import Control.Monad.CryptoRandom
import Data.Bits
import qualified Data.ByteString as BS

data PublicKey  = PublicKey Integer Integer deriving (Show,Eq)
data PrivateKey = PrivateKey Integer Integer deriving (Show,Eq)

defaultExp = 65537

modExp :: Integer -&gt; Integer -&gt; Integer -&gt; Integer
modExp b 0 m = 1
modExp b e m = t * modExp ((b * b) `mod` m) (shiftR e 1) m `mod` m
  where t = if testBit e 0 then b `mod` m else 1


fermatPrimeTest :: StdGen -&gt; Int -&gt; Integer -&gt; Bool
fermatPrimeTest g k n = all (\a -&gt; modExp a (n-1) n == 1) as
  where
    as = take k $ randomRs (2,n-2) g

totient :: Integer -&gt; Integer -&gt; Integer
totient p q = lcm (p-1) (q-1)

-- Find GCD of two numbers plus the Coefficients of Bezouts Identity.
-- Used to find modular inverse.
euclideanAlg :: Integer -&gt; Integer -&gt; (Integer, Integer, Integer)
euclideanAlg a b 
  | b &gt; a     = tripFlip $ euclideanAlg2 b 1 0 a 0 1
  | otherwise = euclideanAlg2 a 1 0 b 0 1
  where
    tripFlip (a,b,c) = (a,c,b)
    euclideanAlg2 rk0 sk0 tk0 0 sk1 tk1 = (rk0,sk0,tk0)
    euclideanAlg2 rk0 sk0 tk0 rk1 sk1 tk1 = 
        let qi = rk0 `div` rk1 in
        euclideanAlg2 rk1 sk1 tk1 (rk0 - qi*rk1) (sk0 - qi*sk1) (tk0 - qi*tk1)

-- Modular inverse, d, of a such that a.d = 1 mod m
modMultInv :: Integer -&gt; Integer -&gt; Integer
modMultInv m a = let (r,_,d) = euclideanAlg m a
                 in d `mod` m




-----------------
-- Prime Number Generator using Secure RNG
-----------------


genPrime :: CryptoRandomGen g =&gt; g -&gt; Int -&gt; Integer -&gt; Integer -&gt; Integer
genPrime g k minPrime maxPrime = head $ filter (fermatPrimeTest g' k) ns
  where
    Right (i,g'') = crandom g
    g'            = mkStdGen i
    Right (n,_)   = crandomR (minPrime, maxPrime) g''
    ns            = iterate ((+) 2) (n .|. 1) 


genPQ :: CryptoRandomGen g =&gt; g -&gt; Int -&gt; Integer -&gt; Integer -&gt; (Integer,Integer)
genPQ g k minPrime maxPrime = (p,q)
  where
    Right (g1,g2) = splitGen g
    p = genPrime g1 k minPrime maxPrime
    q = genPrime g2 k minPrime maxPrime

-- genRSAKeys e g k minPrime maxPrime
-- e is public exponent, g is random seed,
-- k is number of iterations to run Rabin-Miller test.
-- minPrime, maxPrime is range to search for primes.
genRSAKeys :: CryptoRandomGen g =&gt; Integer -&gt; g 
           -&gt; Int -&gt; Integer -&gt; Integer 
           -&gt; (PublicKey, PrivateKey)
genRSAKeys e g k minPrime maxPrime = let 
                                        (p,q) = genPQ g k minPrime maxPrime
                                        n    = p*q
                                        t    = lcm (p-1) (q-1)
                                        d    = modMultInv t e
                                     in (PublicKey n e, PrivateKey n d)
I can't really comment on the RSA key generation itself, since I only know the basics. From a layman's perspective it seems fine, but I cannot touch on details. However, there are some other parts that we can focus on.

Good code is hard to write, especially cryptographic one. Whenever we read cryptographic code, it's usually a good idea to have the algorithm or the original paper at hand to follow the steps. Since we're already occupied with the state machine and the mathematics behind the scenes, the code should be easy to read.

Let us have a look at modExp:

modExp :: Integer -&gt; Integer -&gt; Integer -&gt; Integer
modExp b 0 m = 1
modExp b e m = t * modExp ((b * b) `mod` m) (shiftR e 1) m `mod` m
  where t = if testBit e 0 then b `mod` m else 1


That's the usual double-and-add method for b ^ e `mod` m, and it's completely fine. However, testBit and shiftR are misleading. We're not using some intricate bit patterns here and xor values later, nor do we use the number of bits as a seed. We just want to check whether e is currently odd and divide by two:

-- | Returns (b ^ e) `mod` m.
modExp :: Integer -&gt; Integer -&gt; Integer -&gt; Integer
modExp b 0 m = 1
modExp b e m = t * modExp ((b * b) `mod` m) (e `div` 2) m `mod` m
  where t = if odd e then b `mod` m else 1


Note that you want to replace div by quot and mod by rem if all your values are guaranteed to be positive if you focus on performance, since quot/rem is slightly faster than div/mod. However, their result differs for negative values.

Speaking of positive, defaultExp is missing its type signature. Apart from that, it's great that every function has a type signature, although additional documentation wouldn't harm, e.g.

-- | Generates 'k' random numbers to check whether `n` is prime.
fermatPrimeTest :: StdGen -&gt; Int -&gt; Integer -&gt; Bool
fermatPrimeTest g k n = all (\a -&gt; modExp a (n-1) n == 1) as
  where
    as = take k $ randomRs (2,n-2) g


Similarly some bindings are never used. euclideanAlg2 is the greatest offender here:

euclideanAlg2 rk0 sk0 tk0 0 sk1 tk1 = (rk0,sk0,tk0) -- &lt;- sk1 tk1 unused


Note that the worker is usually called go or similar:

euclideanAlg :: Integer -&gt; Integer -&gt; (Integer, Integer, Integer)
euclideanAlg a b 
  | b &gt; a     = tripFlip $ go b 1 0 a 0 1
  | otherwise =            go a 1 0 b 0 1
  where
    tripFlip (a,b,c) = (a,c,b)

    go rk0 sk0 tk0 0   _   _   = (rk0,sk0,tk0)
    go rk0 sk0 tk0 rk1 sk1 tk1 = 
        let qi = rk0 `div` rk1 
        in go rk1 sk1 tk1 (rk0 - qi*rk1) (sk0 - qi*sk1) (tk0 - qi*tk1)


It's easy to get rid of those bindings if we enable all warnings with -Wall. By the way, you defined but never used totient, nor did you use anything from ByteString. You probably intended to use totient it in genRSAKeys but automatically inlined it.

Apart from those nitpicks, your code seems fine. As I said, I cannot comment about the cryptographic details and whether your implementation is prone to side channel attacks or similar. Also, the quality of the random numbers depends heavily on CryptoRandomGen and therefore is out of scope for this review.

Personally, I would use a top-down approach instead of a bottom-up approach in the code, though. That makes it easier to know our goal:

data PublicKey  = PublicKey Integer Integer deriving (Show,Eq)
data PrivateKey = PrivateKey Integer Integer deriving (Show,Eq)

-- genRSAKeys e g k minPrime maxPrime
-- e is public exponent, g is random seed,
-- k is number of iterations to run Rabin-Miller test.
-- minPrime, maxPrime is range to search for primes.
genRSAKeys :: CryptoRandomGen g =&gt; Integer -&gt; g 
           -&gt; Int -&gt; Integer -&gt; Integer 
           -&gt; (PublicKey, PrivateKey)
genRSAKeys e g k minPrime maxPrime = 
  let  (p,q) = genPQ g k minPrime maxPrime
       n    = p*q
       t    = totient p q
       d    = modMultInv t e
  in (PublicKey n e, PrivateKey n d)

-- | Generates a pair of primes in the given range.
genPQ :: CryptoRandomGen g =&gt; g -&gt; Int -&gt; Integer -&gt; Integer -&gt; (Integer,Integer)
genPQ g k minPrime maxPrime = if p /= q 
                                 then (p,q) 
                                 else ...
  where
    Right (g1,g2) = splitGen g
    p = genPrime g1 k minPrime maxPrime
    q = genPrime g2 k minPrime maxPrime

...


That's a matter of preference though.