2
$\begingroup$

Suppose I have an encryption oracle which can encrypt $m^e \mod n$ for any $m$. I know $n$ and I know $\varphi(n)$. However the public exponent $e$ is secret. Is it possible to figure out it's value when $e$ is not bruteforce-able?

$\endgroup$
6
$\begingroup$

Is it possible to figure out it's value when $e$ is not bruteforce-able?

It depends.
First note that knowing you can easily factor $n$ given that you also know $\varphi(n)$ (2-prime case). Next note that $\mathbb Z_n^*\cong\mathbb Z_p^*\times \mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is a different way of writing an operation in the former group. Finally note that the bit-length of $p,q$ is about half of that of $n$ (usually).

Now that the preparation is through, the first thing to realize is that the given scenario is a standard discrete-logarithm problem with a composite modulus. Also note that the power of being able to choose the base shouldn't make the attacker stronger. Next thanks to the congruence and us knowing $p,q$ we can just map the problem to two smaller problems, finding $e$ given $x\mapsto x^e\bmod p$ and the same for $\bmod q$. Assuming the factors are reasonably small, a standard GNFS attack may work out, but with a standard RSA modulus of two primes of similar length resulting in a 2048-bit modulus this doesn't work.

Otherwise, this is a hard problem because it essentially constitutes a key-recovery attack on the Pohlig-Hellman cipher in a chosen-plaintext scenario.

$\endgroup$
0
$\begingroup$

Assuming you don’t know the private exponent as well; you have to treat $e$ as a random variable, as it can potentially be any number from a very large domain.

Please note that: If the implementation of RSA you’re using is a standard implementation; your encryption exponent is a fixed value, you can try the standard public exponents.

$\endgroup$
  • 2
    $\begingroup$ The note is somewhat unnecessary as the fixed values would be easy to find through brute force, and the question states that brute force is not feasible. $\endgroup$ – Maarten Bodewes Apr 20 at 16:33

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.