Implementing Montgomery ladder methods for modular exponentiation in python

Question

I'm trying to implement the mongomery-ladder method for modular exponentiation for RSA (so N=p•q, p,q are primes) in python, as followed in this paper:

My code looks like this:

x stands for base, k for exp, and N for modulus

# 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

it doesn't work well for very large numbers, for example the following test:

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


if __name__ == '__main__':
    main()

yields:

7564492758006795519
179467895766154563

pow(x, k, n) returns the correct answer, but my function doesn't. Have any ideas?

So where do you need the higher power than Charmichael lamda? You tagged RSA, however, the RSA powers are not greater than the Charmichael lamda, and determined during the RSA-KeyGen. — kelalaka
– kelalaka, Commented Sep 30, 2023 at 13:06
Also, the tag Montgomery-Multiplication has nothing to do with Montgmomery Ladder. — kelalaka
– kelalaka, Commented Sep 30, 2023 at 13:07

Kelly Bundy · Accepted Answer · 2023-09-29 23:03:04Z

4

Remove the k %= N at the start.

answered Sep 29, 2023 at 23:03

Kelly Bundy

27.9k7 gold badges34 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

MatBailie Over a year ago

Working example; trinket.io/python/ae48dd2263

Kelly Bundy Over a year ago

@kelalaka Makes no sense to say it's bad for performance when with it it's not even correct. You can compare performance of correct codes, but comparing performance of a correct code and an incorrect code is nonsense. And about phi: Can you always compute phi(N) quickly? I doubt it.

kelalaka Over a year ago

Let me write a little more. It really depends on what the size of the power needed and how many times? OP did not say anything about the power size and usage, so I guessed that they somehow needed longer powers than the modulus.

kelalaka Over a year ago

Otherwise, with the RSA tag, this has nothing since the power in the RSA are determined beforehand they are samaller than Charmichael lambda. So, I was even considering to delete my answer since it doesn't fit RSA case.

kelalaka Over a year ago

In RSA case, it quite fast since phi(N) = (p-1)(q-1), even it will be faster than any library. Of course, this requires the knowledge of the factor and not possible if you are encryption, usually small eis used and factorization is not known, or no need in the signature generation and verifier has not access the factor or lambda.

|

Collectives™ on Stack Overflow

Implementing Montgomery ladder methods for modular exponentiation in python

1 Answer 1

8 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Linked

Related