Question

Suppose two users Alice and Bob have the same RSA modulus n and suppose that their encryption exponents EA and eg are relatively prime. Charles wants to send the message m to Alice and Bob, so he encrypts to get CA = me and cg = m² (mod n). Show how Eve can find m if she intercepts ca and cg.

Answer 1

Eve can find the original message m by using the Extended Euclidean Algorithm to obtain coefficients x and y, then applying modular arithmetic to the encrypted messages CA and CG, ultimately revealing m.

Step-by-step explanation:

The question involves the RSA encryption algorithm and modular arithmetic, which is a topic in number theory within mathematics. The intercepter, Eve, can find the message m by exploiting the properties of modular arithmetic and the fact that Alice's and Bob's encryption exponents are relatively prime.

Given the intercepted encryption results CA = mEA mod n and CG = mEG mod n, and knowing that EA and EG are relatively prime, Eve can use the Extended Euclidean Algorithm to find integers x and y such that x * EA + y * EG = 1. Eve can then compute (CA)x * (CG)y mod n, which due to the properties of modular exponentiation and the fact that x*EA + y*EG is equal to 1, simplifies to m itself.