RSA: unknown public exponents Suppose I intercept the same message m sent to 2 friends. I know what the message is and I know the used modulus n, as well as the ciphertexts but I don't know the respective public exponents. I.e. my system of equations is:


$c_1 = m^{e_1} \ mod \ n$ 
$c_2 = m^{e_2} \ mod \ n$


Is there a way to retrieve the public exponents, without using bruteforce?

A practical example:


$n = 221$
$m = 127$
$c_1 = 155$
$c_2 = 43$
Hint: seen as a discrete logarithm problem, there's an attack of cost $O(\sqrt{\min(e_1,e_2)})$.

I see no improvement on the asymptotic cost without factoring $n$.

Update: I think it is rigorously provable that if one could solve this problem in polynomial time with sizable probability for proper choice of $n$ and random other parameters, then we could factor $n$. Proof is left as an exercise to the reader by the usual method: invoke the hypothetical algorithm solving the problem in a polynomial-time algorithm that factors $n$.