準同型暗号はいいぞ(RSA編)
この記事は?
Pythonで準同型暗号のひとつであるRSA暗号を実装して、準同型暗号で遊んでみます。準同型暗号とは、暗号化した状態で計算した結果が、そのまま平文での計算結果になっている という不思議な性質をもった暗号です!
RSA暗号
RSA暗号は1977年当時にMITにいたRivest,Shamir、Adlemanによって考案された最初の公開鍵暗号です。幅広く普及していて製品にも利用されている公開鍵暗号方式であり、準同型性を持つことも知られています。
実際にアルゴリズムを見てみましょう。公開鍵暗号のアルゴリズムは3つのフェーズに分かれて記述されます。公開鍵、秘密鍵やその他のパラメタを前準備する鍵生成フェーズ、公開鍵で暗号化する暗号化フェーズ、秘密鍵で復号する復号フェーズです。RSA暗号のアルゴリズムを記述します。
なお、平文というのは暗号化されていない素の値のことです。
鍵生成フェーズ
- 素数
とp を選ぶ。q -
とn=pq を計算する。s=lcm(p-1,q-1) -
と互いに素でかつs より小さい数s を選ぶ。e -
を計算する。d=(\frac{1}{e}\ mod\ s) - 秘密鍵を
を公開鍵d とする。e,n
暗号化フェーズ
復号フェーズ
以上がRSA暗号のアルゴリズムです。簡単のため、安全性的に定義が厳密でない部分があります。
次は実際に実装しつつ、確かに準同型性を持っていることを見てみます!
- Note
は\frac{1}{e} 上の値なので、ただの逆数ではなく逆元です。mod\ s
実装して遊んで見る
まずは、鍵生成フェーズを実装します。組み込み関数pow
がPython3.8未満だと、pow(x,e,n)
で
簡単のため、素数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を入力してください:120
平文2を入力してください:90
平文1:120
平文2:90
暗号文1:24883200000
暗号文2:5904900000
暗号文1×暗号文2:226025144791521
平文1×平文2:10800
--------------------
確かに暗号状態での計算結果は意味不明ですが、復号すると確かに平文の積になっていますね!
- Note 対話は
Ctrl+c
で終了できます。また、入力した平文の値が大きすぎる( 以上)だとうまくいきません。今回はコンパクトにするため使っていませんが、暗号文の計算はpq modint
のようなクラスにラッピングすると使いやすくなると思います。
なぜこんなことが?
数式を変形させながら確認してみましょう。異なる2つの平文の名前を
RSAは
このようになります。
となります。これは明らかに
まとめ
今回はRSA暗号だけの紹介でしたが、他にも準同型性を持つ暗号はたくさんあります。乗算でなく加算に準同型暗号や、両方の性質を持つ完全準同型暗号も存在します。
暗号はとても面白いし、美しい分野なので、ぜひ勉強しろてみてください!
-
実際の実装では互いに素な数は小さい数を定数として指定しておくことが多い。例えば
で固定される場合、e=3 とp を安全素数する工夫をすれば常に互いに素になる。 ↩︎q
Discussion
暗号文1 x暗号文2 mod n
とされるべきではないでしょうか?
公開鍵 pk と n がいくつか分からないのですが,単純に積を取ると暗号文空間を超えてしまう気がします.
暗号文は法Nの空間で計算されるべきなので、全くそのとおりです。修正しておきます!
ご指摘ありがとうございます!