私が15年前はじめて作成したプログラムがRSA暗号だったので、振り返りの意味もこめて記述します。
なお、当時はpythonではなく、Excel VBAやjavascriptを使って書いていました。
RSA暗号は、公開鍵と秘密鍵のペアで構成されるもので、名前のとおり、公開鍵は公開されたもので、秘密鍵は自分しか知らないものです。
公開鍵は、{e,n }、秘密鍵はdで表される数字で、
暗号計算は、平文aに対して、
aをe乗してnで割ったあまりを求める
というものです。
同様に、復号計算は、暗号文bに対して、
bをd乗してnで割ったあまりを求める
というものです。
たとえば、
{e,n } = {3, 15}
で、
d = 35
とします。これらの数字がどこから出てきたかは、後で説明します。
甲さんが機密事項として、"3"という数字を入手し、それを乙さんに伝えようとします。しかし、通信は傍受されています。この時、甲さんは、乙さんの公開鍵で暗号化し、"12"という数字に変換して伝えます。
この通信を傍受した人は、"12"という数字の元が何なのかを知る事ができません。
唯一、乙さんだけが、秘密鍵"35"で、元の数字"3"という情報を得る事ができるのです。
数学的には、
a = 3
b = a^3 mod 15 = 27 mod 15 = 12
復号すると、
b = 12
a = b^35 mod 15 = b^2 * b^33 mod 15
= (b^2 mod 15) * b^33 mod 15
= 9 * b^33 mod 15
= (9 * b mod 15) * b^32 mod 15
= 3 * b^32 mod 15
= 6 * b^31 mod 15
= 12 * b^30 mod 15
= ...
= 9 * b^1 mod 15
= 3 mod 15
= 3
となります。
普通に 12^35を計算すると数字が発散するので、剰余を途中で求めながら計算しています。
たとえば、12^3 mod 15 = (12^2 mod 15) * 12 mod 15
となります。
これは、12^3 = 12^2 * 12 = (15 * 9 + 9) * 12
となる事を利用しています。
なお、この式をPythonで書くと、
b = 12
a = 1
for i in range(d):
a *= b
a = a % n
print(a)
3
となります。
bをnで割って余りを求めながらd回乗算する、という意味です。
一般的に書くとすると、
def decrypt_RSA(b,d,n):
a = 1
for i in range(d):
a *= b
a %= n
return a
なお、暗号化の方も、
def encrypt_RSA(a,e,n):
b = 1
for i in range(e):
b *= a
b %= n
return b
となり、復号化と同一の処理内容となります。
なお、元の文（平文）が"0"や"1"であると、暗号化しても同一の値となり、暗号化の意味がなく、"2"は、2^3 < 15 となり、暗号文 "8" が 公開鍵{3, 15}より簡単に復号されるので、意味がなくなります(i.e. "8"の3乗根が"2")。また、偶然なのか、暗号化しても平文と同一の数になるのが"4","5","6"などです。
鍵の求め方
RSA暗号の鍵の求め方は、Wikipediaをはじめ、多数解説されているので、それらを参考にしてください。実務上は、
「素数p, qを求め、phi(n) = (p-1) * (q-1)を計算し、これと互いに素である数eを適当に決め、そこから、 d * e = phi(n) * x + 1 を満たすdを求め、最後にn = p * qを計算する」事を行います。
Pythonで書いてみましょう。
p = 3
q = 5
n = p * q
phi = (p-1) * (q-1)
print(n,phi)
15 8
e = 3
d = 0
for x in range(0,n):
if (phi * x + 1) % e == 0:
d = int((phi * x + 1) / e)
print(d,x)
35 14
見事、d = 35, e = 3, n = 15が見つかりました。
この原則により、 n = 15 = (3 * 5)などと素因数分解されたら、たちまち d = 35 が解析されるため、暗号が破られた事になります。簡単に素因数分解されないものを見つける必要がありそうです。
素数を見つける
RSA暗号の鍵は素数から成るため、大きな桁の素数を見つける必要があります。
数が大きくなると、直感で素数か否かを判定することができないため、素数の定義に従って見つける事となります。
素数の定義は、「１と自分自身以外に約数がない」事なので、原始的には、１から自分自身に至るまで割り切れるかどうかを判定していく事となります。
もちろん、平方根より大きい数で判定しても意味はないですし、素数以外の数で割り切れるか否かを判定する事に意味はありません。(i.e. "15"で割り切れるのであれば、"3"でも"5"でも割り切れるので、"N"が"15"で割り切れる事を確かめる意味がない）
他にも、色々な計算上の工夫があるかもしれません。
まずは、原始的に判定する事にしましょう。
def is_prime_primitive(N):
i_max = int(N*(1/2))
for i in range(2,i_max + 1):
if N % i == 0:
return False
return True
この関数を使って、例えば、３桁なら、10^2 < N < 10^3のNについてひたすら判定していく事になります。
def find_prime(min_N,max_N):
for N in range(min_N, max_N+1):
if is_prime_primitive(N):
return N
return 0
大きな数の使用例
import time
start = time.time()
print(find_prime(4 * 10**8,10**9))
end = time.time()
print(end - start)
400000009
16.155174255371094
9桁の数で16秒(google colabのCPU環境）かけて見つけました。
pythonの場合、べき乗は^ではなく、**を使う事に注意しましょう。