I am reading Practical Cryptography in Python. I have problem understanding the common_modulus_decrypt() function. I think the prerequisite of RSA Common Modulus Attack is that two public exponents have to be co-prime, meaning $gcd(e_1,e_2)=1$, right? That is what I get from how to use common modulus attack?
If this is true, why does it do the following:
def common_modulus_decrypt(c1, c2, key1, key2): key1_numbers = key1.public_numbers() key2_numbers = key2.public_numbers() if key1_numbers.n != key2_numbers.n: raise ValueError("Common modulus attack requires a common modulus") n = key1_numbers.n if key1_numbers.e == key2_numbers.e: raise ValueError("Common modulus attack requires different public exponents") e1, e2 = key1_numbers.e, key2_numbers.e num1, num2 = min(e1, e2), max(e1, e2) while num2 != 0: num1, num2 = num2, num1 % num2 gcd = num1 a = gmpy2.invert(key1_numbers.e, key2_numbers.e) b = float(gcd - (a*e1))/float(e2) i = gmpy2.invert(c2, n) mx = pow(c1, a, n) my = pow(i, int(-b), n) return mx * my % n
If gcd is always 1, why bothering with the while loop above? Also, I thought it should use the Extended Euclidean algorithm to get
b. Why is it doing invert with
e2? Why is it using float()?
The last 3 steps for
i,mx,my I can understand, as it assumes
b is a minus value.