Implementing RSA encryption/decryption

Question

I'm trying to implement RSA encryption/decryption (a simple implementation of course, so there's no need for nitpicking) and it seems like the numbers (i.e. the keys) are fine, yet the final result is wrong.

Here's the problematic function:

def square_and_mult(base, k, mod):
    b = 1
    for ki in reversed(k):
        if ki == '0':
            b = (b**2) % mod
        else:
            b = ((b**2) * base) % mod
    return b

Hey OliOliver... to prevent potential downvotes or close-votes here at StackOverflow, it might be a good idea to drop a relevant snippet of your sourcecode into your question with an edit. That way, others having the same problem like you might (or might not) find it easier to detect this Q&A via search engines et al. Cheers! — Mike Edward Moras
– Mike Edward Moras, Commented Mar 24, 2017 at 0:24

puzzlepalace · Accepted Answer · 2017-03-23 17:45:30Z

3

I suspect something is wrong with your modular exponentiation algorithm. As you're using python you can use the builtin pow(base, exp, mod) to do this, no need to implement it yourself.

In [1]: n = 48961353722289327881

In [2]: e = 7

In [3]: d = 6994479101184233143

In [4]: x = 12345678

In [5]: c = pow(x, e, n)

In [6]: c
Out[6]: 32225547235202030473

In [7]: m = pow(c, d, n)

In [8]: m
Out[8]: 12345678

answered Mar 23, 2017 at 17:45

puzzlepalace

6605 silver badges13 bronze badges

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

2 Comments

Christian Matt Over a year ago

More concretely, the issue is in the line for ki in reversed(k): Simply removing the reversed makes it work.

OliOliver Over a year ago

Thanks puzzlepalace!

Collectives™ on Stack Overflow

Implementing RSA encryption/decryption

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related