2
$\begingroup$

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 ?

Improve this question
$\endgroup$
3
  • $\begingroup$ Use Extended Euclidian to compute modular inverse. That maybe what gmpy.invert does. $\endgroup$ – fgrieu♦ Nov 21 '14 at 17:55
  • 2
    $\begingroup$ 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) $\endgroup$ – poncho Nov 21 '14 at 18:01
  • 2
    $\begingroup$ 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). $\endgroup$ – mikeazo Nov 21 '14 at 19:38
1
$\begingroup$

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
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.