Consider the following scenario:
The Information Security Department (ISD) of an organization issues each of the organization's employees, domestic and abroad, with an individual RSA key. To simplify the PKI maintenance for the organization, it was decided that a single modulus n will be generated by the ISD and each employee will be issued a personalized public encryption exponent e, and corresponding private decryption exponent d. All key-generating computations will be done by the ISD. This way the organization will also have a copy of each employee's RSA key-set. The reasons for this were given as:
- When an employee loses a key, the ISD can always reissue a key.
- When an internal security leak is suspected, the ISD will have all keys available to investigate the incident.
- When law enforcement obtains a "supina" for a perticular employee's RSA keys, a central office - the ISD - can see to it that the "supina" is honored.
Suppose further that the ISD decides that the encryption exponents will be chosen so that the gcd of any pair is 1; for example, to speed up selecting values of encryption exponent e, the ISD selects from a database of prime numbers.
An eavesdropper can under certain circumstances decrypt messages sent in this system without needing access to any private keys.
Suppose that the CEO dispatches the same message M to two different offcie managers whose encryption exponents respectively are $e_1$ and $e_2$. The encrypted messages are:
$E = M^{e_1} \bmod{n}$ and $F = M^{e_2} \bmod{n}$
An eavesdropper has access to the public keys n, e1 and e2, and the encrypted messages E and F. Since gcd($e_1$, $e_2$)=$1$, the eavesdropper applies the extended Euclidean algorithm to compute integers x and y such that $x \cdot e_1 + y \cdot e_2 = 1$. Then with x and y in hand, the eavesdropper computes
$E^x \cdot F^y \bmod{n} = M$ (original message)
But unfortunately I don't understand why it makes sense that $E^x \cdot F^y \bmod{n} = M$ (original message). Is anyone here able to drop some ideas to me?
