Question

7.2.10 Alice and Bob have RSA setupe with the same modulus n 15251, with eneryption keys ex - i and ea 503, and Alice has (secret) decryption key d 4091. Alice wants to break into Bob's stuff. Without knowing the prime factorization of 15251, how does she easily ind Bob's encryption exponent, or something Js (This is a common modulus attack.)

Answer 1

Alice knows that 103, 157,... can be, for factors p and q of the RSA modulus, (p−1)(q−1) divides

e · d−1 for anyone’s encryption exponent e and decryption exponent d. Thus,

  (p−1)(q−1) divides e_A.d_A - 1

Now, Alice can compute a multiplicative inverse

D = e⁻¹_B mod (e_A · d_A − 1) = 503⁻¹ mod (11 · 4091 − 1)

Now (p − 1)(q − 1) is 22500 by euclid.Compare the decryption exponent D.

Alice computed to Bob’s actual to be D - 22500

D = (D - 22500) mod 22500

Thus, Alice can use D to decrypt messages sent to Bob. The fact that Alice is using a needlessly large exponent does not impede her very much at all.