RSA暗号を攻撃してみよう！その２

RSA暗号に関する前回の記事は下のリンク先です

enu23456.hatenablog.com

さて、前回は公開鍵の1つである n がどんな素数の積なのかをしらみつぶしに調べることで攻撃しましたが、今回は前回と違う方法で素数を調べてみようと思います。

どんな方法かというと、 n = x² - y² になるような x, y を調べていきます。（フェルマー法と言うらしいです）。もし、 x と y が分かれば、因数分解して (x + y) * (x - y) になるので、これが n を構成する素数の組ということが分かります。

上の手法を実際のコーディングにしたものが下記です。（RSAのコード自体は以前のものを参照してください）

def attacker_fermat(n, e):
    """フェルマー法により素因数分解を行い、秘密鍵を推定する
    Note:
        引数の n が (x**2) - (y**2) と表せるような x, y を探索する。
        その時、 n の素因数は (x + y), (x - y) と表すことができる。
    """

    init = 1 + floor(sqrt(n))
    prime_0, prime_1 = 0, 0

    for i in range(init, (n + 9) // 6):
        j = round(sqrt((i ** 2) - n))
        if ((i ** 2) - n - (j ** 2) == 0):
            prime_0 = i - j
            prime_1 = i + j
            # print(n, i - init + 1, i ** 2, j ** 2, prime_0, prime_1)
            break

    fai = ((prime_0 - 1) * (prime_1 - 1)) // gcd((prime_0 - 1), (prime_1 - 1))
    d = 4
    while d == fai or (e * d) % fai != 1:
        d += 1
    # print("prime_0, prime_1, d:", prime_0, prime_1, d)
    return d

※ math の sqrt と floor の import が必要です。

この方法の利点は何かというと、素数の組の値が近いと、すぐ見つけられるという点です。

例えば素数の組が（101, 103）とすると、上の関数のforループの一回目で答えが算出できるので、素数を小さい数から順番に見つけるより、素早く素数の組を見つけることが可能になります。

このことから、素数の組はできるだけ近い数にしてはいけないことが分かると思います。（どのくらい離れていればいいかは、、、どうなんでしょう？）

以上、RSA暗号の攻撃手法に関する説明でした。