🤗

準同型暗号はいいぞ(RSA編)

2020/10/02に公開
3

この記事は?

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

RSA暗号

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

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

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

鍵生成フェーズ

  1. 素数pqを選ぶ。
  2. n=pqs=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("平文1を入力してください:",end="")
		plain_text1=int(input())
		print("平文2を入力してください:",end="")
		plain_text2=int(input())
		print(f"平文1:{plain_text1}")
		print(f"平文2:{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"暗号文1:{cipher_text1}")
		print(f"暗号文2:{cipher_text2}")
		print(f"暗号文1×暗号文2:{cipher_text3}")

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

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

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

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

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

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

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

なぜこんなことが?

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

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

このようになります。c_1c_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_1m_2の積になっていることから、RSA暗号は乗法に対して準同型性を持つ暗号といえます。

まとめ

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

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

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

Discussion

Masahiro KusakaMasahiro Kusaka

暗号文1×暗号文2:146932807680000000000

暗号文1 x暗号文2 mod n
とされるべきではないでしょうか?
公開鍵 pk と n がいくつか分からないのですが,単純に積を取ると暗号文空間を超えてしまう気がします.

SenkSenk

暗号文は法Nの空間で計算されるべきなので、全くそのとおりです。修正しておきます!