Inverse of a pow(a,b,n) function in python decryption code

Question

I am working on a python decryption code using an encryption code which is already available.

In the encrytpion code, I have pow (b, xyz, abc)

A number gets encrypted and is passed onto an array.

Now while decrypting, i need to get the value of "b" (from the pow function above) as i have the value in Array.

Using modulus gives the values in range and not the exact value and that is needed for my decryption logic to work.

How to continue with this?

Do you know about logarithms? This question is really about math, not python nor programming in general — DeepSpace, Apr 16 '18 at 11:29
I'm voting to close this question as off-topic because it's about math, not programming — DeepSpace, Apr 16 '18 at 11:30
Possible duplicate of [How to find reverse of pow(a,b,c) in python?](https://stackoverflow.com/questions/49818392/how-to-find-reverse-of-powa-b-c-in-python) — President James K. Polk, Apr 16 '18 at 14:50

Duncan · Accepted Answer · 2018-04-16T12:36:36.750

First you factorise 928108726777524737. It has 2 prime factors, call them P and Q. Then you need to find a value d such that d * 65539 mod (P-1)(Q-1) == 1 (use the Extended Euclidian Algorithm for this).

Once you have done that then given c = pow (b, 65539, 928108726777524737) you can calculate back to b with pow(c, d, 928108726777524737)

To help you a bit more P=948712711, Q=978282167 giving d=872653594828486879

>>> c = pow(99, 65539, 928108726777524737)
>>> pow(c, 872653594828486879, 928108726777524737)
99

Of course in real life you would start with the prime factors and make them a lot larger than this in which case it would be impractical to reverse the process without already knowing the factors. For small values such as this is it is easy to factorise and calculate the inverse.

Calculation of d:

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

First find the prime factors:

>>> P, Q = 948712711, 978282167
>>> P*Q
928108726777524737
>>> egcd(65539, (P-1)*(Q-1))
(1, -55455130022042981, 3916)

We want the middle value x:

>>> gcd, x, y = egcd(65539, (P-1)*(Q-1))

But we have to make it positive which we can do by adding on the (P-1)*(Q-1) value:

>>> x + (P-1)*(Q-1)
872653594828486879

you can rewrite `q, r = b//a, b%a` as `q, r = divmod(b, a)` which is faster because only one integer division is done on processor level. A modern processor always calculates both, the quotient and the remainder when doing an integer division. — Aemyl, Feb 19 '19 at 08:34
@Aemyl, have you actually timed that and found it to be faster? Sure you only have one division, but you are also adding in one global variable lookup. `python -m timeit -s "a, b = 65529, 928108724850529860" "q, r = b//a, b%a"` 0.116usec per loop, `python -m timeit -s "a, b = 65529, 928108724850529860" "q, r = divmod(b, a)"` 0.136usec per loop — Duncan, Feb 19 '19 at 10:01
That's very interesting. Is there any way to eliminate the global variable lookup? Would it help to compile it? — Aemyl, Feb 19 '19 at 11:57

Inverse of a pow(a,b,n) function in python decryption code

1 Answers1