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 步骤结束时转换回正常世界。我很想知道是否有另一种方法可以以不同的方式计算操作 m^e%n，而不仅仅是在 for 循环中循环？截至目前，我相信这是计算的瓶颈，但我很可能是错的。

实际的蒙哥马利乘法步骤发生在下面的函数中。

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

不，您不想自己进行e乘法运算m来计算 RSA。

你通常想通过重复平方来做 m e mod n （还有其他可能性，但这是一个简单的，足以满足许多典型目的）。

在上一篇关于 RSA的文章中，我包含了一个使用pow_mod函数的实现。反过来，它使用了一个mul_mod函数。蒙哥马利乘法（基本上）是该mul_mod函数的一种实现，它更适合处理大数。然而，为了使它有用，你至少需要pow_mod函数的一般顺序，而不仅仅是一个循环来e调用mul_mod.

考虑到实际使用 RSA 所涉及的数字量，尝试仅使用重复乘法计算 m e mod n 可能需要数年（很可能是相当长的数年）才能完成甚至一次加密。换句话说，一个不同的算法不仅仅是一个很好的优化——它是绝对必要的，因为它是实用的。

用算法术语来说，使用普通乘法来提高 A B基本上是 O(B)。使用那里显示的重复平方算法进行操作，基本上是 O(log B)。如果 B 非常大，那么两者之间的差异是巨大的。

于 2016-03-03T01:59:47.850 回答