Secret modular exponentiation with chosen modulus

Question

Let $e$ be a secret value and $n$ a public 2048-bit RSA modulus. Consider the RSA encryption under the key $(e, n)$ with unknown $e$.

The goal is to decrypt a given ciphertext $c=m^e \pmod{n}$ to recover $m$.

The adversary is assumed to have oracle access to:

1. the encryption function $x\mapsto x^e\pmod{n}$ for chosen $x$.
2. the function $x\mapsto x^e\pmod{n'}$ for chosen $x$ and $n'$.

Is it possible to recover the following values

• $m$ ?
• $e$ ?
• $d = e^{-1}\pmod{\varphi(n)}$ ?

Answer 1

Is it possible to recover the following values

$\cdot$ e

Yes, using the oracle access 2.

He can pick values $x$ and $n'$ which have small orders (and computing such values for arbitrary orders can be done efficiently [1]). If he selects a value $x, n'$ such that $x$ has order $q$ and learn $x^e \bmod n'$, he can recover the value $e \bmod q$ in $O(\sqrt q)$ time.

So, he learns $e \bmod q_1$, $e \bmod q_2$, …, $e \bmod q_n$ are a large number of distinct small primes $q_1, q_2, …, q_n$; he then can compute the value $e \bmod q_1q_2...q_n$; if the number of small primes is sufficient, this is the value $e$

$\cdot$ m

$\cdot$ d

No; oracle 2 is of no further use (as we have recovered all the secrets it holds), and oracle 1 is the standard RSA oracle; neither the plaintext nor the private key is recoverable.

[1] Here is an efficient way to generate a pair $x, n'$ such that $x$ has order $q$

1. Find a prime of the form $n' = qs + 1$, for some integer $s$, and which is the size you're looking form.

2. Select an arbitrary value $r$, and compute $x = r^s \bmod n'$

3. If $x = 1$ or $x = 0$, go back to step2

4. [Needed only if $q$ is not prime] for every prime factor $t$ of $q$, verify that $x^{q/t} \ne 1 \pmod {n'}$; if $x^{q/t} = 1 \pmod{n'}$ for any prime factor $t$, then go back to step 2.

TA-DA! You're done; the order of $x$ modulo $n'$ is $q$; that is, $x^q = 1 \bmod{n'}$ and $x^i \ne 1 \bmod{n'}$ for all $i \in [1,...,q-1]$