Secret modular exponentiation with chosen modulus

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$$.

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)}$$ ?

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 ). 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.

 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]$$