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 = １余り１となる）。

これにより、{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ビットが使用されるそうなので、相当な時間がかかりそう。