# Python. RSA common modulus attack problem

I have:

N = /*500 decimal numbers*/

E1 = 3740453

E2 = 4226171

M^E1 = /*500 decimal numbers*/

M^E2 = /*500 decimal numbers*/


I must use RSA common modulus attack on it.

Using gmpy2.gcdext() i have:

a = 624366
b = -552607


So E1*a+E2*b == 1 is True.

Now i need to know M. For this i must to do follow things:

M = ((M^E1)^a) * ((M^E2)^b) #Just a formula...


In python 2.7 i do like that:

M = pow(ME1,a) * pow(ME2, b) #Where ME1 = M^E1, and ME2 = M^E2


And i have a problem here! Function pow() can't work with negative "b".

How can i calculate last expression ?

• Use Extended Euclidian to compute modular inverse. That maybe what gmpy.invert does.
– fgrieu
Commented Nov 21, 2014 at 17:55
• There are a couple of problems here (and I don't know Python well enough to give you the answers, hence this comment): a) to compute a 'negative power', you need to compute the modular inverse (and then apply the positive power); Python might provide such a utility, or as fgrieu said, you could do it on your own. b) you are using pow to compute the exponents; that is highly unlikely to work, as ME1^a is going to be huge (perhaps one trillion digits long); instead, you need to compute it modulo N (and again, Python might have a built-it to do that) Commented Nov 21, 2014 at 18:01
• I am familiar with python and can give you a few pointers. First, with pow, pow supports a third parameter to compute modular exponentiation. So doing pow(a,b,n) computes, $a^b\bmod{n}$. For computing inverses, I typically use pycrypto (Crypto.Util.number.inverse). Commented Nov 21, 2014 at 19:38

I have solved this problem. @fgrieu was right! Thanks for him and other!

Calculating modular inverse

if a < 0:
_, eM1, __ = gmpy2.gcdext(eM1, N)
elif b < 0:
_, eM2, __ = gmpy2.gcdext(eM2, N)


Calculating source message M

M1 = pow(eM1, abs(a), N) #I just realized, that always i need to use modulus pow(a,b,n)
M2 = pow(eM2, abs(b), N) #In this way all calculations are really fast!
M = (M1 * M2) % N # And final multiplication uses modulus same as previous expression