準同型暗号はいいぞ（RSA編）

この記事は？

Pythonで準同型暗号のひとつであるRSA暗号を実装して、準同型暗号で遊んでみます。準同型暗号とは、暗号化した状態で計算した結果が、そのまま平文での計算結果になっている という不思議な性質をもった暗号です！

RSA暗号

RSA暗号は1977年当時にMITにいたRivest,Shamir、Adlemanによって考案された最初の公開鍵暗号です。幅広く普及していて製品にも利用されている公開鍵暗号方式であり、準同型性を持つことも知られています。

実際にアルゴリズムを見てみましょう。公開鍵暗号のアルゴリズムは３つのフェーズに分かれて記述されます。公開鍵、秘密鍵やその他のパラメタを前準備する鍵生成フェーズ、公開鍵で暗号化する暗号化フェーズ、秘密鍵で復号する復号フェーズです。RSA暗号のアルゴリズムを記述します。

なお、平文というのは暗号化されていない素の値のことです。

鍵生成フェーズ

1. 素数$p$と$q$を選ぶ。
2. $n=pq$と$s=lcm(p-1,q-1)$を計算する。
3. $s$と互いに素でかつ$s$より小さい数$e$を選ぶ。
4. $d=(\frac{1}{e}\ mod\ s)$を計算する。
5. 秘密鍵を$d$を公開鍵$e,n$とする。

暗号化フェーズ

$c=m^e\ mod\ n$を計算して、$c$を出力する。

復号フェーズ

$m=c^d\ mod\ n$を計算して、$m$を出力する。

以上がRSA暗号のアルゴリズムです。簡単のため、安全性的に定義が厳密でない部分があります。
次は実際に実装しつつ、確かに準同型性を持っていることを見てみます！

• Note
  $\frac{1}{e}$は$mod\ s$上の値なので、ただの逆数ではなく逆元です。

実装して遊んで見る

まずは、鍵生成フェーズを実装します。組み込み関数powがPython3.8未満だと、pow(x,e,n)で$x^e mod\ n$を計算できる機能を持っていないので、Python3.8以上での動作を想定しています。

簡単のため、素数$p,q$は十分に大きい値を予め選んでおきます。lcmは最小公倍数を求める関数、gen_coprimeは互いに素な数を持ってくる関数^[1]です。以下がプログラムの全体です。

from sympy import prime
from math import gcd

def lcm(x,y):
	return (x*y)//gcd(x,y)		

def gen_coprime(x):
	for i in range(2,x):
		if gcd(x,i)==1:return i

def genkey_rsa(p,q):
	n=p*q # n = p * q
	s=lcm(p-1,q-1) # p-1とq-1の最小公倍数s
	e=gen_coprime(s) #　sと互いに素な数e
	d=pow(e,-1,s) # d = e^-1 mod s
	return (n,e),(d,n) # 公開鍵、秘密鍵
	
def encrypt_rsa(pk,m):
	n,e=pk
	return pow(m,e,n) # c = m ^ e mod n
	
def mult_cipher(pk,x,y):#暗号文で掛け算する関数
	n,e=pk
	return (x*y)%n

if __name__=="__main__":
	p,q=prime(10**6),prime(10**6+1)
	plain_text1=200000
	pk,sk=genkey_rsa(p,q)

	while True:
		print("-"*20)
		print("平文１を入力してください:",end="")
		plain_text1=int(input())
		print("平文２を入力してください:",end="")
		plain_text2=int(input())
		print(f"平文１:{plain_text1}")
		print(f"平文２:{plain_text2}")

		cipher_text1=encrypt_rsa(pk,plain_text1)
		cipher_text2=encrypt_rsa(pk,plain_text2)
		cipher_text3=mult_cipher(pk,cipher_text1,cipher_text2)
		print(f"暗号文１:{cipher_text1}")
		print(f"暗号文２:{cipher_text2}")
		print(f"暗号文１×暗号文２:{cipher_text3}")

		plain_text3=decrypt_rsa(sk,cipher_text3)
		print(f"平文１×平文２:{plain_text3}")

さっそく実行してみましょう。このプログラムのmainでは次の処理をprintしながら繰り返します。

1. 平文の入力を受け付ける。
2. 平文暗号化する。
3. 暗号化された値を乗算する。
4. 復号する。

自分が動かしてみた結果は以下のようになりました。

--------------------
平文１を入力してください:120
平文２を入力してください:90
平文１:120
平文２:90
暗号文１:24883200000
暗号文２:5904900000
暗号文１×暗号文２:226025144791521
平文１×平文２:10800
--------------------

確かに暗号状態での計算結果は意味不明ですが、復号すると確かに平文の積になっていますね！

• Note 対話はCtrl+cで終了できます。また、入力した平文の値が大きすぎる（$pq$以上）だとうまくいきません。今回はコンパクトにするため使っていませんが、暗号文の計算はmodintのようなクラスにラッピングすると使いやすくなると思います。

なぜこんなことが？

数式を変形させながら確認してみましょう。異なる２つの平文の名前を$m_1$、$m_2$とします。
RSAは$c=m^e\ mod\ n$と暗号化されていたことを考えると

$$c_1=m_1^e\ mod\ n ,c_2=m_1^e\ mod\ n$$

このようになります。$c_1$と$c_2$を乗算し、$c_1 \cdot c_2$とします。$c_1 \cdot c_2$を復号すると

$$Dec(c_1 \cdot c_2) = (c_1 \cdot c_2)^d = (m_1^e \cdot m_2^e)^d = (m_1 \cdot m_2)^{e\cdot d} = (m_1 \cdot m_2)^{e \cdot \frac{1}{e}}=m_1 \cdot m_2$$

となります。これは明らかに$m_1$と$m_2$の積になっていることから、RSA暗号は乗法に対して準同型性を持つ暗号といえます。

まとめ

今回はRSA暗号だけの紹介でしたが、他にも準同型性を持つ暗号はたくさんあります。乗算でなく加算に準同型暗号や、両方の性質を持つ完全準同型暗号も存在します。

暗号はとても面白いし、美しい分野なので、ぜひ勉強しろてみてください！

脚注

1. 実際の実装では互いに素な数は小さい数を定数として指定しておくことが多い。例えば$e=3$で固定される場合、$p$と$q$を安全素数する工夫をすれば常に互いに素になる。