2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ If you're looking for extra credit, answer these questions: 1) how could an employee decrypt a message to anyone, and 2) (harder) how could an employee factor n (and thus generate anyone's private key) $\endgroup$ – poncho Apr 23 '15 at 18:07
4
$\begingroup$

You just have to do some simple algebra.

$$E^x \cdot F^y$$ $$(M^{e_1})^x \cdot (M^{e_2})^y$$ $$M^{xe_1} \cdot M^{ye_2}$$ $$M^{xe_1 + ye_2}$$

Well, what is $xe_1+ye_2$?

$\endgroup$
  • 1
    $\begingroup$ @rex don't forget to mark this as the answer by clicking the green check. $\endgroup$ – mikeazo May 24 '15 at 1:22

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.