RSA暗号の例と素因数分解サンプル
■{p, q} = {3, 11}, {e, d} = {7, 3}
公開鍵方式で使われるRSA暗号の方法について、Wikiや他のサイトを見ながら計算例を作ってみた。
素数 p = 3, q = 11とする。
(p-1)*(q-1) = (3-1) * (11-1) = 2 * 10 = 20。これを n とする(n = 20)。
n と互いに素となる数値 e を 7とする(e = 7)。
e の n に対するモジュロ逆数 d を 3 と求める(3 * 7 = 21、21 / 20 = 1余り1となる)。
これにより、{p, q} = {3, 11}, {e, d} = {7, 3}。
暗号化の対象とする平文を例えば 13 にすると、
暗号化: 13 ^ 7 (e) = 62748517、これを20で割ると余り17。
復号化: 17(余り) ^ 3 (d) = 4913、これを20で割ると余り13。
この計算では、n = 20 なので、2進数で 10100 (5 ビット)。
素因数分解に基づく計算の困難性からこの方式が使用されているとのことなので、pythonで素因数分解をするコードを組んで計算の大変さを感じてみる。
コードは下のもの。単純に2から順に余りが出るか調べていく。割り切れれば、割った結果を再度2から順に余りが出るか調べていく。
import time
TARGET_NUM = 4294967296
primefactor = []
start_time = time.time()
dividend = TARGET_NUM
def dividenum(dividend, divisor):
for var in range(2, dividend + 1):
result = dividend % var
if result == 0:
primefactor.append(var)
dividend = int(dividend / var)
break
if dividend == var:
primefactor.append(dividend)
dividend = 1
return dividend
while True:
print(dividend)
dividend = dividenum(dividend, dividend)
if dividend == 1:
break
end_time = time.time()
print("Time", ":", end_time - start_time)
print(primefactor)
32ビットでは、2^32 = 4294967296 となる。少し値を変えて、4294967291(たぶん素数)では、950秒かかった。割り切れるものでは、もっと早く計算ができるけど、RSA暗号では1024ビットから2048ビットが使用されるそうなので、相当な時間がかかりそう。