HaskellでRSA暗号の鍵生成器作った

学校の課題でなんか作ってこいって言われたんで

RSA暗号の鍵生成器を作ってみました。

大まかな構造はこんなかんじです

乱数生成 -> 乱数をもとに素数を生成 -> 素数をもとに鍵ペアを生成 -> ファイルに出力

ではモジュールごとにソースコードを解説していきます

まず乱数生成から。

module Random
(genSeed
,genInfiniteRandomList
)where

import System.Entropy
import System.Random
import Data.Time.Clock.POSIX

genSeed :: IO Integer
genSeed = do
    mbstr <- getEntropy 128
	let str' = show mbstr	
	let str = map toEnum $ filter (\x -> 48<=x && x<58) $ map fromEnum $ str':: [Char]
	let randomNum = read str :: Integer
	return randomNum

genInfiniteRandomList :: (Integer, Integer) -> IO [Integer]
genInfiniteRandomList (n1, n2) = do
 g <- getPOSIXTime
 let randNum = randomRs (n1, n2) (mkStdGen (round g)) :: [Integer]
 return $ map toInteger randNum

genSeedはpとqのseedを生成します。getEntropyで取得した文字列から数字だけを抜き出してIntegerに変換するというちょっと強引な方法を使ってます。

getEntropyは/dev/urandomから乱数を取得しているので暗号用の乱数としては脆弱です。誰か/dev/randomから取ってこられるように書きなおしてくださいおねがいします。

genInfiniteRandomListはその名の通り乱数の無限リストを生成します。こちらは素数判定に使うのでセキュリティは考慮する必要がありません。

次は素数判定ですがその前に素数判定と鍵生成に使う計算用モジュールを載せます。ほぼ全部コピペです。extEuclidに至っては動作原理さえよくわかってません。

module CalcAlgorithm
(power
,powMod
,inverse
) where

power :: (Integral a1, Num a) => a -> a1 -> a
power x n
    | n == 0    = 1
    | even n    = power (x*x) (n `div` 2)
    | otherwise = x * power x (n - 1)
 
powMod :: Integer -> Integer -> Integer -> Integer
powMod base ex m
  | ex == 0   = 1
  | even ex   = square (powMod base (ex `div` 2) m) `mod` m
  | otherwise = (base * (powMod base (ex - 1) m)) `mod` m
 where
   square x = x * x

extEuclid :: Integral t => t -> t -> (t, t)
extEuclid a b = recurse a b 1 0 0 1
  where recurse a 0 x0 y0 x1 y1 = (x0, y0)
        recurse a b x0 y0 x1 y1 = let q = a `div` b in 
                                  let r = a `mod` b in
                                  recurse b r x1 y1 (x0 - q * x1) (y0 - q * y1)

inverse :: Integer -> Integer -> Integer
inverse x n = (fst (extEuclid x n)) `mod` n

素数判定です。鍵の素となるpとqを生成します。

module PrimalityTest
(isMillerRabinPrime
,isProbablePrime
,getPrime
) where

import Control.Applicative
import Control.Monad
import System.Random
import Data.Time.Clock.POSIX
import CalcAlgorithm
import Random

factor2 :: (Integral t, Num t1) => t -> (t, t1)
factor2 x = factor2' (x,0)
 where
  factor2' (n,s)
   | even n = factor2' (n `div` 2, s+1)
   | otherwise = (n,s)

isProbablePrime :: Integer -> Integer -> Bool
isProbablePrime n a =
 let (d,s) = factor2 (n-1) in
 let p = powMod a d n /= 1 in
 let q = not $ elem (n-1) $ map (\r -> powMod a ((power 2 r)*d) n) [0..s-1] in
 not (p && q)


isMillerRabinPrime :: Integer -> IO Bool
isMillerRabinPrime n = do
 ns <- genInfiniteRandomList (1,n-1) 
 return . and $ map (isProbablePrime n) (take 12 ns)

getPrime :: Integer -> IO Integer
getPrime s = do
 if odd s then getPrime' s else getPrime (s+1)
  where getPrime' s = do b <- isMillerRabinPrime s
                         if b then return s else getPrime' (s+2)

MillerRabin素数判定法を使っています。こちらとWikipediaの記事を参考にしました。

MillerRabin素数判定法をざっと解説します。

ある数をMillerさんに渡します。

ある数が素数なら、Millerさんは「そいつは素数だね！！」と言います。

ある数が合成数なら、Millerさんは「そいつは合成数だよ」と言います。

でもMillerさんはドジっ子なので、合成数を持っていったときにたまに間違えて「そいつは素数だね！！」と言っちゃうことがあります。

そんなちょっとおっちょこちょいなアルゴリズムです。

Millerさんはたまに間違えるので、

「ねぇ、この数って素数？」

「うん、多分ね」

「ほんとに素数？こいつが合成数だったらどうなるかわかってんでしょうね」

「きっと素数だよ...」

といった感じに、Millerさんに何回も聞くことによって精度を上げています。別にいじめているわけじゃありません。

このコードではMillerさんに12回問い詰めています。Millerさんがかわいそうですね。

最後に、鍵を計算して出力する部分なんですが、はてなブログのエラーのせいでうまく表示できません。すみませんが代わりにGithubを見てください。

鍵のファイルは他のプログラムから読みやすいようにCSV形式にしています。

鍵を読み込んで暗号化・復号化するPython製のプログラムもGithubに上げてあります。Pythonはよくわからないのでググりながら適当に書きました。上記のコードを含めおかしいところがあったら言ってください。

あと、このプログラムを使って暗号化したら解読されて秘密が漏れた！なんてことがあっても僕は責任を負えません。「俺ら今暗号使って通信してんだぜ〜」って感じで遊び程度に使ってくれたら幸いです。

7/23

getEntropyで取ってきた乱数をハッシュ関数に通すようにしました。アップグレード済みのソースコードはGithubにあります。(1行と5文字しか追加してない)