5
\$\begingroup\$

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 -> 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)
\$\endgroup\$
  • \$\begingroup\$ "Also, I used foldl' not foldl in the actual code, ...." Your code contains neither? \$\endgroup\$ – Zeta Nov 2 '17 at 8:06
  • \$\begingroup\$ Ha, yeah you're right. I edited the code because I noticed that some code wasn't being used. I'll fix that comment. \$\endgroup\$ – user668074 Nov 2 '17 at 8:13
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user668074 Nov 2 '17 at 9:48
  • \$\begingroup\$ "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. \$\endgroup\$ – wchargin Nov 2 '17 at 11:50
  • \$\begingroup\$ @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. \$\endgroup\$ – Zeta Nov 2 '17 at 12:59
  • \$\begingroup\$ 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. \$\endgroup\$ – Ilmari Karonen Nov 2 '17 at 18:34
  • \$\begingroup\$ @IlmariKaronen thanks, I've removed that part. \$\endgroup\$ – Zeta Nov 3 '17 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.