Common Modulus Attack on RSA

In this problem, two users share the same modulus \(N\) but use different public exponents \(e_1\) and \(e_2\) (which are co-prime). Their corresponding ciphertexts are given by:

\[ \begin{aligned} c_1 &\equiv m^{e_1} \pmod{N},\\ c_2 &\equiv m^{e_2} \pmod{N}. \end{aligned} \]

An attacker intercepts \(c_1\), \(c_2\), \(e_1\), \(e_2\), and \(N\). Using the fact that \(\gcd(e_1,e_2) = 1\), one can find integers \(a\) and \(b\) such that:

\[ a\cdot e_1 + b\cdot e_2 = 1. \]

Then, the original message \(m\) can be recovered as:

\[ m \equiv c_1^{a} \cdot c_2^{b} \pmod{N}, \]

where for negative exponents, modular inverses are used.

Your task is to implement this attack and recover the original message \(m\).

inputFormat

The input consists of a single line containing five space-separated integers:

• c1: the first ciphertext,
• c2: the second ciphertext,
• e1: the first public exponent,
• e2: the second public exponent,
• N: the modulus.

You can assume that \(e_1\) and \(e_2\) are co-prime.

outputFormat

Output the recovered plaintext message \(m\) as an integer.

sample

47 88 3 5 101

42