Python实现Montgomery Ladder模幂算法（RSA场景）出错求助

我尝试在Python中为RSA（N=p·q，p、q为质数）实现Montgomery Ladder模幂算法，参考了相关论文和伪代码，写出如下代码：

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

# 使用Montgomery Ladder实现模幂运算
def montgomery_ladder(x, k, N):
    x %= N
    k %= N
    # 获取k的二进制表示
    bin_k = list(map(int, bin(k)[2:]))
    # 初始化中间结果变量
    r0 = 1
    r1 = x

    # 从最高位到最低位遍历指数的每一位
    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

    # 最终结果存储在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)返回正确结果，但我的实现结果错误，求解决思路。

1. 核心错误：错误修改指数k #

你的代码中k %= N是完全错误的操作：

• 模幂运算中，指数k不需要对模数N取模。根据欧拉定理，当x和N互质时，x^k mod N = x^(k mod φ(N)) mod N（其中φ(N)是欧拉函数，对于RSA的N=p·q，φ(N)=(p-1)(q-1)），但绝不能直接对N取模。
• 这行代码导致你计算的是x^(k mod N) mod N，而非正确的x^k mod N，直接造成结果与pow函数不一致。必须删除这一行。

2. 优化变量更新顺序（避免潜在错误） #

虽然你的循环中变量更新顺序在逻辑上是对的，但直接原地修改r0/r1容易出现意外覆盖问题。建议先计算新值再赋值，让逻辑更清晰：

修改后的代码：

def montgomery_ladder(x, k, N):
    x %= N
    # 移除错误的k %= N
    bin_k = list(map(int, bin(k)[2:]))
    r0 = 1
    r1 = x

    for bit in bin_k:
        if bit == 0:
            # 先计算两个新值，再同步更新
            new_r0 = (r0 * r0) % N
            new_r1 = (r0 * r1) % N
            r0, r1 = new_r0, new_r1
        else:
            new_r0 = (r0 * r1) % N
            new_r1 = (r1 * r1) % N
            r0, r1 = new_r0, new_r1

    return r0

验证修改 #

运行修改后的代码，结果会与pow(x, k, N)完全一致。Montgomery Ladder的核心逻辑（每一步固定次数的乘法，抗侧信道攻击）在你的原代码中是正确的，仅需修正指数处理和优化变量更新逻辑即可。

内容的提问来源于stack exchange，提问作者YahavB