RSA暗号である理由

暗号の勉強。
RSA暗号には乗法準同型性がある。暗号化したまま計算できること生かして、秘密計算の勉強に応用。
比較的アルゴリズムが簡単。

Scalaである理由

関数型言語の考え方を知りたい。
~~Scalaで書いてみたいだけ。~~

RSA暗号に使う計算のプログラム

package enc_utils

object calcs{
    import scala.util.Random
    import scala.math.{sqrt,floor}
    def euclidAlg(m:Int,n:Int):Int = {
            if (n == 0) m else euclidAlg(n,m%n)
    }
    def mod(x:Int,power:Int,modulo:Int):Int = {
        var result:Int = 1
        for (i <- 1 to power){ 
            result = result * ( x % modulo + modulo ) % modulo
        }
        result
    }
    def genPrime(low:Int,high:Int):Int = {
        def notPrime(num:Int):Boolean = {
            for( i <- 2 to floor(sqrt(num)).toInt) if ( num % i == 0 ) return true
            false
        }
        var num = Random.nextInt(high-low)+low 
        while (notPrime(num)) num = Random.nextInt(high-low)+low 
        num
    }
    def genCoprime(x:Int):Int = {
        var num:Int = Random.nextInt(x-1)
        while (euclidAlg(x,num) != 1 || num <= 1) num = Random.nextInt(x-1)
        num
    }
    def modInv(a:Int,modulo:Int) = {
        def extEuclid(a:Int,b:Int):(Int,Int) = {
            if (b==0) {
                (1,0) 
            }else {
                var (y,x)=extEuclid(b,a%b)
                // t = x , y =s =>  calc x = t - qs, y = s
                y = y - a/b * x
                (x,y)
            }
        }
        mod(extEuclid(a,modulo)._1,1,modulo)
    }
}

それぞれ、剰余計算するプログラムmod、ランダムな素数を探すプログラムgenPrime、互いに素な数を探すプログラムであるgenCoprime。素数判定に平方根を使った方法を使っているため、あまり効率が良くないと思われる。（ASK素数判定を使ってみたい）

modInv は拡張ユークリッドの互除法extEuclidを使って、逆元計算するプログラム。参考文献のサイトを参考に作っている。extEuclidは出力を最大公約数ではなく求めた(x,y)にしている。

RSA暗号の鍵生成から暗号化、復号

package enc_utils

object rsaEnc{
    import enc_utils.calcs._
    import scala.util.Random
    def genKey (bit:Int) ={
        def genTwoPrime(low:Int,high:Int):(Int,Int) = {
            val p:Int= genPrime(low,high)  
            var q:Int= genPrime(low,high)  
            while (p == q) q = genPrime(low,high)  
            (p,q)
        }
        val low:Int = 1 << (bit/2).toInt -1
        val high:Int = 1 << (bit/2).toInt

        val (p,q) = genTwoPrime(low,high)
        val n:Int =  p * q
        val o:Int = (p-1) * (q-1) / euclidAlg(p-1,q-1)
        val e:Int = genCoprime(o)

        val d:Int = modInv(e,o)
        val pk = (e,n)
        val sk = (d,n)
        (pk,sk)
    }

    def genPtxt (num:Int):Int = Random.nextInt(num-1)%num
    def encrypt (pk:(Int,Int),ptxt:Int):Int = mod(ptxt,pk._1,pk._2) 
    def decrypt (sk:(Int,Int),ctxt:Int):Int = mod(ctxt,sk._1,sk._2)
}

RSA暗号のスキームに従って鍵の生成、平文空間にあるようなテスト平文生成、暗号化、復号を行っている。

実行結果

object Main extends App{
    import enc_utils.calcs._
    import enc_utils.rsaEnc._

    val (pk,sk) = genKey(10)

    val ptxt1 = genPtxt(pk._2)
    val ctxt1 = encrypt(pk,ptxt1)   

    val ptxt2 = genPtxt(pk._2)
    val ctxt2 = encrypt(pk,ptxt2)   

    val result = decrypt(sk,ctxt1)

    println("------enc and dec test-------")
    println(s"ptxt:$ptxt1")
    println(s"ctxt:$ctxt1")
    println(s"result of dec:$result")

    val addPtxt = mod(ptxt1*ptxt2,1,pk._2)
    val addCtxt = decrypt(sk,mod(ctxt1*ctxt2,1,sk._2))

    println("-----------HE test-----------")
    println(s"result of ptxt:$addPtxt")
    println(s"result of ctxt:$addCtxt")
}

>>scala Main
------enc and dec test-------
ptxt:201
ctxt:329
result of dec:201
-----------HE test-----------
result of ptxt:46
result of ctxt:46
>>

上のように平文＝復号結果となっているので正しく実装できている。
ptxt*ptxtとctxt*ctxtの復号結果が同じことから、乗法準同型性も確認できる。

結び

乱数生成の際にwhile文を用いたが、Scalaだともっと適切な書き方がありそう。
手続き型言語の書き方から頭を切り替えられていないように感じた。

参考文献

結城浩「暗号技術入門　第3版秘密の国のアリス」2015
瀬良和弘、水島宏太、河内崇、麻植泰輔、青山直紀　「実践Scala入門」2018
RSA暗号-Wikipedia
The Scala Programming Language
よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方
拡張ユークリッドの互除法〜一次不定方程式 ax + by = c の解き方〜

ScalaでRSA暗号を実装してみた