# 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 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 -> Integer -> Integer -> 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 -> Int -> Integer -> Bool
fermatPrimeTest g k n = all (\a -> modExp a (n-1) n == 1) as
where
as = take k $randomRs (2,n-2) g totient :: Integer -> Integer -> 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 -> Integer -> (Integer, Integer, Integer) euclideanAlg a b | b > 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 -> Integer -> Integer
modMultInv m a = let (r,_,d) = euclideanAlg m a
in d mod m

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

genPrime :: CryptoRandomGen g => g -> Int -> Integer -> Integer -> 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 => g -> Int -> Integer -> Integer -> (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 => Integer -> g -> Int -> Integer -> Integer -> (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)  • "Also, I used foldl' not foldl in the actual code, ...." Your code contains neither? – Zeta Nov 2, 2017 at 8:06 • Ha, yeah you're right. I edited the code because I noticed that some code wasn't being used. I'll fix that comment. Nov 2, 2017 at 8:13 ## 1 Answer 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 -> Integer -> Integer -> 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 -> Integer -> Integer -> 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 -> Int -> Integer -> Bool fermatPrimeTest g k n = all (\a -> 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) -- <- sk1 tk1 unused


Note that the worker is usually called go or similar:

euclideanAlg :: Integer -> Integer -> (Integer, Integer, Integer)
euclideanAlg a b
| b > 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 => Integer -> g
-> Int -> Integer -> Integer
-> (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 => g -> Int -> Integer -> Integer -> (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.

• Thanks for the response. I agree that the top down approach looks better. I will keep it in mind. And good idea for separating the prime ranges. The rest of the feedback is also good, mainly coming from different revisions of the code. The euclideanAlg2 unused code mainly comes from making sure that the function works correctly in isolation. Nov 2, 2017 at 9:48
• "Note that you want to replace div by quot and mod by rem if all your values are guaranteed to be positive." Why? If your values are positive, then div and quot behave identically, as do mod and rem. Nov 2, 2017 at 11:50
• @wchargin quot and rem are (slightly) faster. On Integer div and mod are implemented via quot and rem, and divMod is implemented via quotRem. I've added a short explanation to the answer, though.
– Zeta
Nov 2, 2017 at 12:59
• The recommendation in the original RSA paper that $p$ and $q$ should "differ in length by a few digits" is generally considered obsolete. Indeed, as fgrieu's answer to the linked question notes, modern crypto standards like FIPS 186 effectively require $p$ and $q$ to have the same length in binary. While having $p$ and $q$ very close to each other would be bad, the odds of that happening are negligible as long as both are picked randomly from a sufficiently wide range. Nov 2, 2017 at 18:34
• @IlmariKaronen thanks, I've removed that part.
– Zeta
Nov 3, 2017 at 11:32