さっさと実装を見たい方はこちら(Github)
こんにちは、キャベツです。
ふと、RSA暗号を実装してみたくなったので、やりました。
RSA暗号って何？
公開鍵暗号の一種です
すでに解説をしている先人がたくさんいらっしゃいますが、軽く説明します
公開鍵暗号
平たくいえば、暗号化する手段と復号する手段が異なる手法です。
暗号を送る側は、誰でも手に入れることのできる公開鍵というものを用いて、元の文（平文）を暗号化します。
一方で、暗号を受け取った側は誰にも公開しない秘密鍵を用いて暗号文を複号します。
公開鍵暗号とは別の概念として、共通鍵暗号という概念があります。
その名の通り、暗号化と復号に用いる鍵が共通であり、両者が同じ鍵をもつ必要があります。
そのため、暗号文の送信のほか、鍵の送信という脆弱性が生まれます。
その点、公開鍵暗号は鍵を輸送しなくてもいいというメリットがあります。
仕組み
素数の性質を用います。
$p$を素数、$a$を$p$と素である整数とすると、
a^{p-1} \equiv 1\ (\text{mod}\ p)
が成り立ちます（フェルマーの小定理）。
さて、RSA暗号の流れをなぞっていきましょう。
鍵の生成
（秘密鍵:$key_p$、公開鍵:$key_n, key_e$）
まず、2種類の素数$p, q$を用意します。
import sympy
p = sympy.randprime(len(dic_c_i)+5, 10**501)
q = sympy.randprime(len(dic_c_i)+5, 10**501)
while p == q:
q = sympy.randprime(len(dic_c_i)+5, 10**501)
この時、$key_n = pq$と定義され、
$key_e$は、$(p-1)(q-1)$と互いに素な正の数と定義されます。
これで、公開鍵が生成されました。
秘密鍵$key_p$の定義は少し複雑で、
$$key_n\times key_p - (p-1)(q-1)\times A = 1$$($A$は任意の整数)
を満たす整数です。
すなわち、
$$key_n\times key_p\equiv 1\ (\text{mod}\ (p-1)(q-1)) $$
を満たします。
実装するとこんな感じ
def gcd(a, b):
while b:
a, b = b, a % b
return a
def key_pub(p, q, div = 3):
key_n = p*q
p_q_ = (p-1)*(q-1)
key_e = 0
for i in reversed(range(int(p_q_//div))):
if (gcd(p_q_, i) == 1):
key_e = i
break
return key_n, key_e
key_n, key_e= key_pub(p, q)
def key_pri(p, q, key_e):
a = key_e
b = (p-1)*(q-1)
x1, y1, _ = sympy.gcdex(a,b)
#a(x-x1) = -b(y-y1)
#x-x1 = bm
#y-y1 = -am
m = 1
x = b*m + x1
while(x > 0):
m-=1
x = b*m + x1
while(x <= 0):
m+=1
x = b*m + x1
return x
key_p = int(key_pri(p, q, key_e))
暗号生成
平文を数値に変換します。
まず、{文字:数字}の辞書を用意します。
今回は、
A-Z, a-z, !（ビックリマーク）?（クエスチョンマーク）,（カンマ）.（ピリオド） （スペース）
を数値に変換する辞書を作りました。
def mkdic(s):
cs = [c for c in s]
dic_c_i = { ch:i for i,ch in enumerate(cs)}
dic_i_c = { i:ch for i,ch in enumerate(cs)}
return dic_c_i, dic_i_c
d = ""
for i in range(65, 65+26):
d += chr(i)
for i in range(97, 97+26):
d += chr(i)
d += chr(33)
d += chr(63)
d += chr(44)
d += chr(46)
d += " "
d
dic_c_i, dic_i_c = mkdic(d)
print(dic_c_i)
print(dic_i_c)
なお、d に適当な文字列を入れることで任意の辞書が自動で生成されます。
この辞書を用いて、平文を変換します。
def plain_to_int(dic_c_i, text):
return [dic_c_i[c] for c in text]
def int_to_plain(dic_i_c, nums):
return [dic_i_c[c] for c in nums]
answer = "" #Text that you want to send using RSA.
if answer == "":
answer = input()
nums = plain_to_int(dic_c_i, answer)
text = int_to_plain(dic_i_c, nums)
print(nums)
print("".join(text))
ここで、変換後の数列を$nums$と呼びます。
$nums$のそれぞれの数$nums_i$に対して、暗号文($nums_d$)は以下のように定義されます。
$$nums_{d_i} \equiv nums_i^{key_e}\ (\text{mod}\ key_n) $$
並列化も含めて実装すると↓
from multiprocessing import Process, Queue
def power_func(num,key_e,key_n, que, itr):
bi = str(format(key_e,"b"))
res = 1
for i in range(len(bi)):
res = (res*res) %key_n
if bi[i] == "1":
res = (res*num) %key_n
que.put((itr, res))
que = Queue()
nums_d = nums.copy()
for i in range(len(nums)):
num = nums[i]
p = Process(target=power_func, args=(num,key_e,key_n, que, i))
p.start()
values = sorted((que.get() for _ in range(len(nums))), key=lambda r: r[0])
for i, v in enumerate(values):
nums_d[i] = v[1]
暗号化が終わりました。
復号
受け取ったそれぞれの数字に対して、復号文（$nums_{test}$）は以下のように定義されます。
$$nums_{test_i} \equiv nums_{d_i}^{key_p}\ (\text{mod}\ key_n) $$
並列化も含めて実装すると↓
def power_func(num,key_e,key_n, que, itr):
bi = str(format(key_e,"b"))#2進表現に
res = 1
for i in range(len(bi)):
res = (res*res) %key_n
if bi[i] == "1":
res = (res*num) %key_n
que.put((itr, res))
nums_test = nums_d.copy()
que = Queue()
for i in range(len(nums_d)):
num = nums_d[i]
p = Process(target=power_func, args=(num,key_p,key_n, que, i))
p.start()
values = sorted((que.get() for _ in range(len(nums_d))), key=lambda r: r[0])
for i, v in enumerate(values):
nums_test[i] = v[1]
復号文ができたので、最初の辞書を用いることでメッセージを受け取ることができました。
def int_to_plain(dic_i_c, nums):
return [dic_i_c[c] for c in nums]
print("".join(int_to_plain(dic_i_c, nums_test)))
どこでフェルマーの小定理を使ったか
フェルマーの小定理は
$$a^{p-1} \equiv 1\ (\text{mod}\ p)$$
暗号文の定義を思い出すと、
$$nums_{d_i} \equiv nums_i^{key_e}\ (\text{mod}\ key_n) $$
復号文の定義を思い出すと、
$$nums_{test_i} \equiv nums_{d_i}^{key_p}\ (\text{mod}\ key_n) $$
すなわち、復号文は
$$nums_{test_i} \equiv nums_{d_i}^{key_p}\equiv nums_i^{key_p\times key_e}\ (\text{mod}\ key_n) $$
$key_n\times key_p - (p-1)(q-1)\times A = 1$($A$は任意の整数)から
$$nums_i^{key_p\times key_e}= nums_i^{(p-1)(q-1)\times A + 1}= nums_i\times nums_i^{(p-1)(q-1)\times A}$$
よって、
$$nums_{test_i} \equiv nums_i\times nums_i^{(p-1)(q-1)\times A}\ (\text{mod}\ key_n)$$
フェルマーの小定理から、
$$nums_i^{\textbf{(p-1)}(q-1)\times A} \equiv 1\ (\text{mod}\ \textbf{p})$$
$$nums_i^{(p-1)\textbf{(q-1)}\times A} \equiv 1\ (\text{mod}\ \textbf{q})$$
が成り立つ。
これは、$p, q$のそれぞれで$nums_i^{(p-1)(q-1)\times A}$を割ったあまりが$1$であることを意味し、
その積である$pq =key_n$で割ってもあまりが1であることを示す。
よって、
$$nums_{test_i} \equiv nums_i\ (\text{mod}\ key_n)$$
こうして、復号がなされる。
オマケの実装
さて、RSA暗号を実装してお手紙を書こうとした時、あることに気づいた。
「辞書をすべて暗号化したら、暗号文を解読できるではないか。」
すなわち、{文字:数字}の辞書を、{文字:暗号}に変換し、暗号文を解読するということである。
実装するとこんな感じ↓
def power_func(num,key_e,key_n, que, itr):
bi = str(format(key_e,"b"))
res = 1
for i in range(len(bi)):
res = (res*res) %key_n
if bi[i] == "1":
res = (res*num) %key_n
que.put((itr, res))
que = Queue()
keys = dic_i_c.keys()
for i, num in enumerate(keys):
p = Process(target=power_func, args=(num,key_e,key_n, que, i))
p.start()
values = sorted((que.get() for _ in range(len(keys))), key=lambda r: r[0])
実際にできる。
すなわち、お手紙を暗号化したところで、ボキャブラリー（辞書）が貧弱だと解読され放題ということである。
（ただ、大きな数字を通信したり、同じ文字に複数の数字が対応するようにすれば辞書を現実的な時間で暗号化することは困難になる。）
よろしくお願いしまぁぁぁす！
記念すべき初投稿なので、温かいコメントお待ちしております。
RSA暗号を実装してみた。
文字 to 数字の辞書が大きければ強固であることを作ってて感じた。
逆にその辞書が小さければ脆弱である（公開鍵だけで現実的な時間で復号できてしまう）。
先人たち
https://qiita.com/akakou/items/700e00a715593966cbfa
https://qiita.com/sashiyama/items/0eba7f0b04a53b6c8b42