0

モンゴメリー乗算は、RSA 暗号化で使用される c=m^e%n を計算するための暗号化プロセスを高速化するためにどのように機能しますか? モンゴメリー乗算は a*b%n を効率的に乗算できることは理解していますが、m^e%n を見つけようとするとき、モンゴメリー乗算を毎回ループして計算するよりも m*me 回を乗算するより効率的な方法はありますか?

mpz_class mod(mpz_class &m, mpz_class &exp, mpz_class &n) {
        //End goal is to return m^exp%n
//      cout << "Begin mod";
        mpz_class orig_m = m; //the original message
        mpz_class loc_m = m;  //local value of m (to be changed as you cycle through)
        cout << "m: " << m << " exp: " << exp << " n: " << n << endl;

        //Conversion to the montgomery world
        mpz_class mm_xp = (loc_m*r)%n;
        mpz_class mm_yp = (orig_m*r)%n;

        for(int i=0; i < exp-1; i++) //Repeat multiplaction "exp" number of times
        {
                 mm(mm_xp, mm_yp, n); //montgomery multiplication algorithm returns m*orig_m%n but in the montgomery world form
        }

        mm_xp = (mm_xp*r_p)%n; //convert from montgomery world to normal numbers
        return mm_xp;
}

ここでより大きな数を扱うことができるように、gmp ライブラリを使用しています。r と r_p は別の関数で事前に計算されており、グローバルです。この例では、10 のべき乗で作業しています (ただし、2 のべき乗で作業する方が効率的であることはわかっています)。

乗算の前にモンゴメリ形式に変換し、for ループで乗算 m*m を繰り返し、m^e ステップの最後で通常の世界に変換します。forループで循環するだけでなく、操作 m^e%n を別の方法で計算する別の方法があるかどうか知りたいです。今のところ、これが計算のボトルネックであると信じていますが、間違っている可能性が非常に高いです。

実際のモンゴメリ乗算ステップは、以下の関数で発生します。

void mm(mpz_class &ret, const mpz_class &y, const mpz_class &n)
{
        mpz_class a = ret*y;

        while(a%r != 0)
        {
                a += n;
        }
        ret = a/r; //ret*y%n in montgomery form
//      cout << ret << endl;
}

これは、モンゴメリー乗算の最適化で RSA 暗号化が機能する方法ですか?

4

1 に答える 1

1

いいえ、 RSA を計算するために単独eで乗算を実行する必要はありません。m

通常、二乗を繰り返して m e mod n を実行します (他にも可能性はありますが、これは多くの典型的な目的に適した単純なものです)。

RSA に関する以前の投稿で、pow_mod関数を使用した実装を含めました。次に、mul_mod関数を使用しました。モンゴメリー乗算は、(基本的に) そのmul_mod関数の実装であり、大きな数を扱うのにより適しています。ただし、それを便利にするには、 を呼び出すためpow_modのループだけでなく、少なくとも関数の一般的な順序に関する何かが必要です。emul_mod

RSA の実際の使用に関係する数値の大きさを考えると、繰り返し乗算を使用して m e mod n を計算しようとすると、単一の暗号化を完了するのにおそらく数年 (かなりの数年) かかるでしょう。言い換えれば、別のアルゴリズムは単に優れた最適化ではありません。実際に使用するには絶対に必要です。

これをアルゴリズム的に言えば、単純な乗算を使用してA Bを上げることは、基本的に O(B) です。そこに示されている繰り返し二乗アルゴリズムでそれを行うと、基本的に O(log B) になります。B が非常に大きい場合、両者の差は計り知れません。

于 2016-03-03T01:59:47.850 に答える