0
$\begingroup$

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)}$ ?
$\endgroup$
4
$\begingroup$

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

$\endgroup$

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.