１．RSA暗号
最近、記事の下に「RSA暗号を生成せよ」という広告がある。この記事の下にもあるのではないかと思うが、そこには次のことが書かれている。
RSA暗号を生成せよ。
適当な素数\(p\)と\(q\)、下の条件を満たす自然数\(e\)
条件1: \(0 < e < (p-1)(q-1) \)
条件2: \(gcd((p-1)(q-1),e) = 1 \)
この時の暗号の公開鍵は\(\{pq,e\}\)となる。
では2から100までの素数から\(p\)と\(q\)を選んだとき、
候補となる\(e\)が\(p+q\)個存在するような\(p\)と\(q\)の組合せを求めてみよう！
今回は、この問題に挑戦する。その前にRSA暗号について簡単に紹介しておく。RSAは発明者のRon Rivest, Adi Shamir, Len Adlemanの名前の頭文字をとったものである（後日談であるが、彼らがこの暗号を発表(1977年)してから20年後にもっと前に発見している人たちがいることが分かった。英国のジェイムス・エリス(1969年に理論を発案)とクリフォード・コックス(1973年に具体的な方法を提示)であったが、国家の機密事項として1997年まで公表されなかった）。
RSA暗号は次のような方式である。公開鍵と秘密鍵とからなる鍵のペアを作成して、公開鍵を公開する。先ほどの問題にあった自然数\(e\)を選択し、大きな二つの素数\(p\)と\(q\)を生成し、\(\{ pq,e\}\)を平文暗号化の公開鍵とする。
平文を\(c\)とし、暗号文を\(m\)とした時、暗号化は\(c = m^e \ mod \ pq \)で、復号は\(m = c^d \ mod \ pq \)で行う。但し、\(d= e^{-1} \ mod \ ( p-1)(q-1)\)である。\(d\)を知ることなしに暗号文から平文を得ることは難しいと信じられている。このため、\(d\)を秘密鍵として用いている。
２．プログラム化
まず。上の条件1,2を満足する公開鍵を求めることとする。100までの素数(25個ある)のリストpsと素数かどうかを判断する関数isPrimeが必要である。そこで、前回の記事で紹介した素数primesを利用して次のものを用意する。
ps = take 25 primes isPrime a = a `elem` ps
次に、\(r = p+q \)であるような公開鍵を求める関数csを作成する。これは、条件1,2を内包表記で記述するばよい。
cs :: Integer -> [(Integer, (Integer, Integer))] cs r = [(e, (p, q)) | p <- filter (< r) ps, let q = r - p, isPrime q && p <= q, e <- [1..(p - 1) * (q - 1) -1 ], gcd ((p - 1) * (q - 1)) e == 1]
上のプログラムでは、rを与えると、公開鍵を構成するeと(p,q)の対のリストが得られる。最初に、p <- filter (< r) ps によって、rよりも小さい素数pを昇順で取出す。つぎに、それぞれのpに対して次の処理を行う。まず、q=r-pとし、isPrime q && p <= qによって、qが素数で、かつ、pより大きいかあるいは等しいかを調べる。これを満たす時、e <- [1..(p - 1) * (q - 1) -1 ]によって、１から(p - 1) * (q - 1) -1までeを順番に取り出し次の処理を行う。gcd ( (p - 1) * (q - 1) ) e == 1によって、(p - 1) * (q - 1)とeの最大公約数(gcd)が1であるかを調べる。そうであるとき、公開鍵となるので、(e, (p, q))をリストの要素として送出する。これで、条件1,2を満たすものについては求めることができた。
次の処理は、\(e\)が\(p+q\)個存在するような\(p\)と\(q\)の組合せを求めることである。このためには、上記で求めた公開鍵のリストに、何種類のeがあるかを調べる必要がる。これには、上で求めたリストを、eの昇順で並べ替え(sortBy)、さらに、同じ値を取るeでグループ分け(groupBy)する必要がある。これは、
groupBy ((==) `Data.Function.on` fst) . sortBy compFst . cs
で実現できる。ここで、compFstはeの値で比較できるようにする関数で、次のようになっている。
compFst a b
| fst a < fst b = LT
| otherwise = GT
全てのrに対して公開鍵のリストを作成するためには、mapを用いればよいので以下のようになる。
rsa' = map (groupBy ((==) `Data.Function.on` fst) . sortBy compFst . cs) [5..2 * 97]
この中から、eの種類とr=p+qが一致するものを選べばよいので、次のようにする。
rsa :: [[[(Integer, (Integer, Integer))]]] rsa = filter (\ls -> let pq = snd $ head $ head ls in length ls == fromIntegral (fst pq) + fromIntegral (snd pq)) $ filter (not . null) rsa'
rの値によっては、公開鍵が存在しない場合があるが、filter (not . null)はそのようなものを取り除くためである。
実行結果は以下のようになる。
*Rsa> rsa [[[(1,(7,7)),(1,(3,11))],[(3,(3,11))],[(5,(7,7))],[(7,(7,7)),(7,(3,11))],[(9,(3,11))],[(11,(7,7)),(11,(3,11))],[(13,(7,7)),(13,(3,11))],[(17,(7,7)),(17,(3,11))],[(19,(7,7)),(19,(3,11))],[(23,(7,7))],[(25,(7,7))],[(29,(7,7))],[(31,(7,7))],[(35,(7,7))]]] *Rsa>
これから、rが14の時、eは、1,3,5,7,9,11,13,17,19,23,25,29,31,35をとることが分かる。また、(p,q)の組合せも上記の結果からわかる。
3．プログラム全体
プログラムの全体を示す。プログラムはRsaとPrimesのモジュールに分割した。モジュールRsaは次のようになる。
module Rsa where import Data.List import Data.Function import Primes rsa :: [[[(Integer, (Integer, Integer))]]] rsa = filter (\ls -> let pq = snd $ head $ head ls in length ls == fromIntegral (fst pq) + fromIntegral (snd pq)) $ filter (not . null) rsa' where rsa' = map (groupBy ((==) `Data.Function.on` fst) . sortBy compFst . cs) [5..2 * 97] compFst a b | fst a < fst b = LT | otherwise = GT cs :: Integer -> [(Integer, (Integer, Integer))] cs r = [(e, (p, q)) | p <- filter (< r) ps, let q = r - p, isPrime q && p <= q, e <- [1..(p - 1) * (q - 1) -1 ], gcd ((p - 1) * (q - 1)) e == 1] ps = take 25 primes isPrime a = a `elem` ps
モジュールPrimesは、前の記事と同じだが、念のために記すと次のようになる。
module Primes where primes :: [Integer] primes = 2 : minus [3..] (foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) [] primes) where minus (x:xs) (y:ys) = case (compare x y) of LT -> x : minus xs (y:ys) EQ -> minus xs ys GT -> minus (x:xs) ys minus xs _ = xs union (x:xs) (y:ys) = case (compare x y) of LT -> x : union xs (y:ys) EQ -> x : union xs ys GT -> y : union (x:xs) ys union xs [] = xs union [] ys = ys
