質問

公開キーしかない場合、RSA メッセージを復号するにはどうすればよいでしょうか?

たとえば、メッセージ：21556870,12228498公開鍵: (e = 15852553, n = 44331583)

私はこれらの公式が存在することを知っています:

gcd(e, φ(n)) = 1
ed mod φ(n) = 1

そこで私のアイデアは、最初の式に e の値を入れて、秘密鍵の一部である d を導出できるということでした。ただし、数学的にそれを見つけることは不可能だと思います φ(n) ここ。では、公開キーのみを使用して RSA メッセージを復号化するには、他にどのようにすればよいでしょうか?

役に立ちましたか？

解決

「公開鍵しか持っていない場合、どうやって RSA メッセージを復号化できるでしょうか?」

良い、 公開鍵から秘密鍵を見つけなければなりません. 。RSA アルゴリズムはフィールドで実証済みのセキュリティ アルゴリズムであり、一般に十分な長さのビットを使用して慎重に使用されているため、これを実際の状況で実行するのは一般に難しすぎるはずです。

ただし、あなたに割り当てられた演習は、RSA アルゴリズムを練習するために設計されています。使用される数値は、公開キーから秘密キーを取得できないほど大きくはありません。 好みのプログラミング言語とコンピューターを使用して、簡単なプログラミングですべての計算を実行できるはずです。

以下の答えを見る前に、もっと頑張ってください。

公開鍵: (e = 15852553, n = 44331583)

因数分解してみましょう n. 。ここに簡単な Python プログラムを示します。

def factor(n):
    for i in range(2, n-1):
        if n % i == 0:
            print(str(n) + " = " + str(i) + " * " + str(n // i))
            break

ランニング factor(44331583), 、それを取得します 44331583 = 5003 * 8861.

それで φ(n) = (5003 - 1) * (8861 - 1) = 44317720

の逆数を求めます e モジュロ φ(n). 。ここに簡単な Python プログラムを示します。

def inverse(e, phi):
    """ display the inverse of e modulo phi """

    for i in range(1, phi):
        if i * e % phi == 1:
            print(str(e) + " * " + str(i) + " = 1 (mod " + str(phi) + ")")
            break

ランニング inverse(15852553, 44317720), 、それを取得します 15852553 * 1951097 = 1 (mod 44317720). 。つまり、次の逆です。 e モジュロ φ(n) は d=1951097.

したがって、対応する秘密鍵は次のようになります。 (d = 1951097, n = 44331583).

コンピューティング m**d (mod n) RSA メッセージを復号化します (別名:暗号文） m. 。これは人気のあるべき乗剰余関数です。

def modulo_pow(base, exponent, modulus):
    """ display the result of base ** exponent % modulus """

    exp = exponent
    result = 1
    b = base % modulus

    while exp > 0:
        if exp % 2 == 1:
            result = (result * b) % modulus
        exp = exp >> 1
        b = (b * b) % modulus

    print(str(base) + " ** " + str(exponent)
          + " = " + str(result) + " (mod " + str(modulus) + ")")

ランニング modulo_pow(21556870, 1951097, 44331583) そして modulo_pow(71, 15852553, 44331583), 、それぞれ得られました、

21556870 ** 1951097 = 71 (mod 44331583)
12228498 ** 1951097 = 111 (mod 44331583)

したがって、復号化されたメッセージは次のようになります。 71,111. 。それが何を意味するかわかりますか？

他のヒント

復号化できるようにRSA公開鍵の基部を因数分解する必要があります。それが全体の点です：クラッキングRSAは因数分解に相当し、因数分解は非常に硬い（推定されています）。

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top