在Python中实现模幂的蒙哥马利梯子方法

Question

我正在尝试在 python 中实现 RSA 的模幂运算的 mongomery-ladder 方法（因此 N=p•q，p,q 是素数），如下论文所示：

我的代码如下所示：

• x 代表底数，k 代表指数，N 代表模数

# uses montgomery-ladder method for modular exponentiation
def montgomery_ladder(x, k, N):
    x %= N
    k %= N
    # getting the binary representation of k
    bin_k = list(map(int, bin(k)[2:]))
    # Initialize two variables to hold the intermediate results
    r0 = 1
    r1 = x

    # Loop through each bit of the binary exponent from most significant to the least significant
    for i in range(len(bin_k)):
        if bin_k[i] == 0:
            r1 = (r1 * r0) % N
            r0 = (r0 ** 2) % N
        else:
            r0 = (r0 * r1) % N
            r1 = (r1 ** 2) % N

    # The final result is in r0
    return r0

它不适用于非常大的数字，例如以下测试：

def main():
    x = 412432421343242134234233
    k = 62243535235312321213254235
    N = 10423451524353243462
    print(montgomery_ladder(x, k, N))
    print(pow(x, k, N))


if __name__ == '__main__':
    main()

产量：

7564492758006795519
179467895766154563

pow(x, k, n) 返回正确的答案，但我的函数没有。 有什么想法吗？

Answer 1

删除开头的

k %= N

。

Answer 2

使用

k %= N

是不正确的，因为它是模数的幂。应使用

k = k % phi(N)

，其中

phi(n)

是 欧拉 totient 函数。

欧拉定理所说的

a^phi(N) = 1 mod N

（= 是等价而不是相等）。 python symPhy 为您提供。

需要存储Euler Totient以降低成本。

除了在RSA计算中一开始人们学习Euler Totient，然而，实际上在标准中使用了Carmichael lambda。

k = k % lambda(N)

。 Carmichael lambda 总是给出与 1 同余的最小幂。 python symPhy 也有它； 减少_totient。

请注意，totient 和 phi 必须保密，否则分解 RSA 模数很容易。

from sympy.ntheory.factor_ import totient
from sympy.ntheory.factor_ import reduced_totient

# uses montgomery-ladder method for modular exponentiation
def montgomery_ladder(x, k, N):

    x %= N

    #k %= totient(N)
    k %= reduced_totient(N)

    # getting the binary representation of k
    bin_k = list(map(int, bin(k)[2:]))
    # Initialize two variables to hold the intermediate results
    r0 = 1
    r1 = x

    # Loop through each bit of the binary exponent from most significant to the least significant
    for i in range(len(bin_k)):
        if bin_k[i] == 0:
            r1 = (r1 * r0) % N
            r0 = (r0 ** 2) % N
        else:
            r0 = (r0 * r1) % N
            r1 = (r1 ** 2) % N

    # The final result is in r0
    return r0



def main():
    x = 412432421343242134234233
    k = 62243535235312321213254235
    N = 10423451524353243462
    print(montgomery_ladder(x, k, N))
    print(pow(x, k, N))


if __name__ == '__main__':
    main()

输出

179467895766154563
179467895766154563