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