0

私は RSA 暗号化システムの復号化関数を書こうとしていますが、すべてが非常に小さい数値に対しては正常に機能しているように見えましたが、出力が正しくない場合があります (原因は浮動小数点エラーまたは何らかの種類のエラーである可能性があると思います)。スタックオーバーフロー）。

問題を引き起こしているプロセスは (11^23) mod 187 に単純化できますが、誰かが見たい場合に備えて完全なコードを含めます。サイモン・シン博士による「コードブック」の付録Jで使用されている例であるため、答えは88になるはずです（Wolfram Alphaも使用して確認しました）。ただし、149 という結果が得られます。ただし、数値が小さいほど、Wolfram Alpha と一致します。

私の考えでは、次の知識を使用して累乗剰余を単純化する必要があります。

a^b = a^c * a^d [c + d = b]

ただし、これがこの問題であるかどうかはまだ 100% 確信が持てません。これは初めてのスタック オーバーフローですか? （それが何を意味するのかはまだ100％わかりません）。誰かが私に挑戦する前に、いいえ、これは宿題ではありません。この質問が些細なことのように思えたら申し訳ありません。gmp.h を使用するのは難しすぎると誰もが思うなら、私は gmp.h を使用することにオープンです。私のコードは以下のとおりです（前半は秘密鍵を計算するためのもので、私が抱えている問題とは無関係だと思いますが、私が間違っている場合に備えてそれを含めました）、皆さんが助けてくれることを本当に願っています、ありがとうあなたは非常に前もって。

#include <iostream>
#include <math.h>

using namespace std;

unsigned int modinv(unsigned int u, unsigned int v)
{
    unsigned int inv, u1, u3, v1, v3, t1, t3, q;
    int iter;

    u1 = 1;
    u3 = u;
    v1 = 0;
    v3 = v;

    iter = 1;

    while (v3 != 0)
    {

        q = u3 / v3;
        t3 = u3 % v3;
        t1 = u1 + q * v1;

        u1 = v1; v1 = t1; u3 = v3; v3 = t3;
        iter = -iter;
    }

    if (u3 != 1)
        return 0;
    if (iter < 0)
        inv = v - u1;
    else
        inv = u1;
    return inv;
}

int main()
{ long unsigned int p = 17;
long unsigned int q = 11;
long unsigned int phi = (p-1)*(q-1);
long unsigned int e = 7;
long unsigned int c = 11;
long unsigned int n = p*q;
long unsigned int d = modinv (e,phi);
    {
         cout << fmod (pow (c, d), n);
    }
    return 0;
}
4

2 に答える 2

2

11^23 は約 2^80 です。倍精度浮動小数点数として正確に表現できるのは、2^53 までの整数のみです。したがって、fmod(pow(c, d), n)) は近似値を返します。これは暗号化には適していません。

追加された二乗を繰り返し使用して累乗剰余を行うことができます。ウィキペディアの「二乗による累乗」に関する記事を確認してください

于 2014-02-26T22:45:10.527 に答える
0

RSA に関するこの wiki 記事のセクションが役立ちます。

RSA 復号化の動作例

この記事には、Euclid アルゴリズムへのリンクが含まれている中国剰余アルゴリズムへのリンクが含まれていることに注意してください。2 つの素数 p と q が与えられた場合、2 つの整数 a と b を見つけて、ap + bq = 1 となり、(ap) mod q == 1 および (bq) mod p == 1. 明確でないのは、a または b のいずれかが負になることであり、負の値は剰余アルゴリズムの最初の部分で使用されることです (記事では、 Euclid アルゴリズムの値を使用します)。たとえば、a が負の場合、(ap) mod q == 1 ですが、((a+q) p) mod q も == 1 であるため、a と a+q の両方が p の逆数であると見なすことができます。 q を法とする数学の場合。

于 2014-02-27T03:03:25.800 に答える