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

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

# Scalaである理由
- 関数型言語の考え方を知りたい。
- ~~Scalaで書いてみたいだけ。~~

# RSA暗号に使う計算のプログラム
```scala
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暗号の鍵生成から暗号化、復号
```scala
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暗号のスキームに従って鍵の生成、平文空間にあるようなテスト平文生成、暗号化、復号を行っている。

#実行結果
```scala
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](https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7)
- [The Scala Programming Language](https://www.scala-lang.org/)
- [よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方](http://drken1215.hatenablog.com/entry/2018/06/08/210000)
- [拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜](https://qiita.com/drken/items/b97ff231e43bce50199a)