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

今回は、公開鍵暗号方式の1つであるRSA暗号の攻撃について書いてみたいと思います

RSA暗号のアルゴリズムがどんなものか知ってるよ！という前提で書いていきますので、ご存じない方は下記URLなどでRSA暗号のアルゴリズムを知ってからお読みいただくと良いかと思います

qiita.com

RSA暗号では、２つの素数の組から下記３つのパラメータを作ります

n(公開鍵), e(公開鍵), d(秘密鍵)

３番目の秘密鍵は他の人には見せないですが、公開鍵の２つからｄが分かれば暗号化された文章を読むことできることになります。

ではどうやって秘密鍵の数値を求めていきましょう？

まず思いつく手法は公開鍵の n から２つの素数の組を求めてしまう方法かと思います。n は２つの素数の組の積であり、頑張って何の素数の積なのかが調べられれば、そこから秘密鍵が求められそうです。

ここで、実際にコードで確かめるべく、シンプルなRSA暗号の実装コードを作りました。

from math import gcd


def rsa_generate_keys(p, q):
    """与えられた 2 つの素数の組 p, q から秘密鍵と公開鍵を生成する。
    """
    n = p * q
    fai = ((p - 1) * (q - 1)) // gcd((p - 1), (q - 1))
    e, d = 2, 2

    while e == fai or gcd(e, fai) != 1:
        e += 1

    while d == fai or (e * d) % fai != 1:
        d += 1

    return n, e, d


def rsa_encrypt(text, e, n):
    """ text を、パラメータ e, n を用いて暗号化／復号化を行う
    Note:
        RSA 暗号はパラメータが違うだけで処理内容は暗号化／復号化同じためまとめた
    """
    ret = ''.join(chr(pow(ord(char), e, n)) for char in text)

    return ret


if __name__ == '__main__':
    # 素数の組から公開鍵(rsa_n, rsa_e)と秘密鍵(rsa_d)を生成する
    print("set param of RSA")
    rsa_n, rsa_e, rsa_d = rsa_generate_keys(101, 103)
    print("rsa_n(pub):", rsa_n, ", rsa_e(pub):", rsa_e, ", rsa_d(pri):", rsa_d)

    # 暗号／復号が出来ているかのテスト
    print("\nencrypt/decrypt test!!")
    plain = "Hello World!"
    encrypted = rsa_encrypt(plain, rsa_e, rsa_n)
    decrypted = rsa_encrypt(encrypted, rsa_d, rsa_n)
    print(plain, "→(enc)→ ", encrypted, "→(dec)→ ", decrypted)

このコードでは、素数の組を(101, 103)としてパラメータを計算すると、n, e, d はそれぞれ n: 10403, e: 7, d: 3643 という値が得られます。

さて、では n の値から２つの素数を気合で探す関数を作りましょう。

def attacker_calc(n, e):
    """RSA暗号のパラメータを、素数をしらみつぶしに調べる方法で推測する
    Note:
        n = p * q
    """
    prime_0 = 0
    prime_1 = 0
    for i in range(2, n):
        if n % i == 0:
            prime_0 = i
            break
    prime_1 = n // prime_0

    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

2から順番に割ってみて、割り切れたらそれが素数の組の1つとして探索を止めます。（ここは、数が素数ということが分かっているのでもっと高速化はできるかと思います。）

片方が分かってしまえば、そこからは難なく他のパラメータは求められるので、RSA暗号の攻撃に成功したと言えます。

この結果から分かるコトは、「素数は"両方とも"できるだけ大きな数にしよう」ということです。RSA暗号の安全性の拠り所が「桁数が大きい合成数の素因数分解問題が困難であること」ですので、当たり前のことといえば当たり前ですね。

また、片方だけが大きな数でも、もう片方が小さい数だと先ほどの計算処理を見てわかる通り、すぐに小さい方の数がばれてしまいますので、ちゃんと両方とも、大きな数にしないといけません。

ではどのくらい大きい数なのかというと、2017年の時点で n が1024bit 以下は非推奨とされているようですので、1025bit以上になるように、素数を選ぶ必要があります（この辺りが公開鍵暗号の難点の1つですね）

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