HaskellでRSA - あどけない話

Haskell には Integer があるので、RSA の計算は簡単なのではと思い立ち、作ってみました。RSA の計算方法や、RSA129 を知らない人は、まず「はやわかりRSA」を読んでみましょう。

暗号化と復号化

x^exp (mod n) を高速に計算する関数を実装できれば、暗号化も復号化も簡単です。

rsaEncrypt :: Integer -> Integer -> Integer -> Integer
rsaEncrypt e n plain  = powerMod plain  e n
rsaDecrypt :: Integer -> Integer -> Integer -> Integer
rsaDecrypt d n cipher = powerMod cipher d n

powerMod x exp n = iter exp seq 1
    where
      seq = iterate (\y -> y*y `mod` n) x
      iter 0 _ ret = ret
      iter b (s:ss) ret = let next = if odd b
                                     then ret * s `mod` n
                                     else ret
                          in iter (shiftR b 1) ss next

文字列を数値へ (と、その逆)

RSA129 で使われている符号化(文字列から数値)と復号化(数値から文字列)の実装も、そんなに難しくはありません。

rsa129encode :: String -> Integer
rsa129encode s = foldl multiply100 0 $ map encode s
    where
      encode ' ' = 0
      encode c   = 1 + ord c - ord 'a'
      multiply100 :: Integer -> Int -> Integer
      multiply100 x y = x * 100 + (toInteger y)

rsa129decode :: Integer -> String
rsa129decode n = map decode $ divide100 n
    where
      decode 0 = ' '
      decode x = chr $ x + ord 'a' -1
      divide100 :: Integer -> [Int]
      divide100 n = iter n []
          where
            iter :: Integer -> [Int] -> [Int]
            iter 0 is = is
            iter m is = iter (m `div` 100) $ fromInteger (m `mod` 100) : is

RSA129を試してみる

RSA129のパラーメータを定義します。

--公開鍵
rsa129n = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
rsa129e = 9007
--署名
rsa129signature = 16717861150380844246015271389168398245436901032358311217835038446929062655448792237114490509578608655662496577974840004057020373

署名を検証してみます。

rsa129decode $ rsaEncrypt rsa129e rsa129n rsa129signature 
→ "first solver wins one hundred dollars"

おお！

秘密鍵を求める

rsa129n が rsa129p と rsa129q に素因数分解されたとしましょう。

rsa129p = 3490529510847650949147849619903898133417764638493387843990820577
rsa129q = 32769132993266709549961988190834461413177642967992942539798288533

秘密鍵 d を算出するプログラムは、拡張ユークリッドの互除法になります。

calcD p q e = let l = lcm (p-1) (q-1)
                  d = euclid (1,0,l) (0,1,e) 
              in if d > 0
                 then d
                 else d + l

euclid f@(x1,y1,z1) s@(x2,y2,0) = y1
euclid f@(x1,y1,z1) s@(x2,y2,z2) = euclid s t
    where
      q = z1 `div` z2
      t = (x1 - q*x2, y1 - q*y2, z1 - q*z2)

で、d を計算してみると

calcD rsa129p rsa129q rsa129e
→ 20912395050161373690941936346810195773046184093006090879304842322045608569697121472257875853682203172258717888678557376735780271

となって、Derek が計算した d とは異なる数値になりました。

うーん、Derek は L に lcm(p-1,q-1) ではなく、(p-1)*(q-1) を使ったようです。知らなかったなぁ。

当然、lcm を使った方がいいので、この結果を rsa129d としましょう。

rsa129d = calcD rsa129p rsa129q rsa129e

RSA129 を解く

17年間と解読されなかった暗号文は、こうです。

rsa129cipher = 9686961375462206147714092225435588290575999112457431987469512093081629822514570835693147662288398962801339199055182994515781515418050019172105011309190800151919090618010705

復号化してみましょう。

rsa129decode $ rsaDecrypt rsa129d rsa129n rsa129cipher 
→ "the magic words are squeamish ossifrage"

くー。

ついでに逆演算もやってみます。

 (rsaEncrypt rsa129e rsa129n $ rsa129encode "the magic words are squeamish ossifrage") == rsa129cipher
→ True

追記

以下の記事も読んで下さい。