In today’s Programming Praxis exercise, our task is to implement a key generator and encryption/decription functions for RSA cryptography. Let’s get started, shall we?

A few imports:

import Data.Bits
import Data.List
import System.Random
import Data.Numbers.Primes

Like the Scheme solution, we’ll be recycling a few functions from previous solutions.

expm :: Integer -> Integer -> Integer -> Integer
expm b e m = foldl' (\r (b', _) -> mod (r * b') m) 1 .
filter (flip testBit 0 . snd) .
zip (iterate (flip mod m . (^ 2)) b) $
takeWhile (> 0) $ iterate (`shiftR` 1) e
euclid :: Integral a => a -> a -> a
euclid x y = f 1 0 x 0 1 y where
f a b g u v w | w == 0 = mod a y
| otherwise = f u v w (a - q*u) (b - q*v) (g - q*w)
where q = div g w
inv :: Integral a => a -> a -> a
inv x m | gcd x m == 1 = euclid x m
| otherwise = error "divisor must be coprime to modulus"

The keygen returns the modulus and the decryption key.

keygen :: Integer -> Integer -> IO (Integer, Integer)
keygen bits key = do p <- gen (div bits 2)
q <- gen (div bits 2)
let d = inv key ((p - 1) * (q - 1))
return (p * q, d) where
gen k = fmap (until valid succ) $ randomRIO (2 ^ (k - 1), 2 ^ k)
valid v = gcd key (v - 1) == 1 && mod v 4 == 3 && isPrime v

For encrypting and decrypting we could just use expm directly, but we flip the last two arguments to correspond to the Scheme solution.

crypt :: Integer -> Integer -> Integer -> Integer
crypt = flip . expm

Some tests to see if everything’s working correctly:

main :: IO ()
main = do let e = 65537
(m, d) <- keygen 32 e
print $ crypt (crypt 42 m e) m d == 42
print $ crypt 42 1893932189 e == 1118138102

Everything seems to be working fine.

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, cryptography, Haskell, kata, praxis, programming, rsa

This entry was posted on November 16, 2010 at 11:14 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

November 17, 2010 at 7:16 am |

Gee, those one letter variable names…