読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

RSA暗号の公開鍵を求める

1.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\)を秘密鍵として用いている。

2.プログラム化

まず。上の条件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 ]によって、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