Let's say there's this blackbox app that has a known modulus $N$, private exponent $e$, and takes ciphertext $C$ encrypted against $N$ and $e$ input and outputs plaintext $M$.

The encryption is done via textbook RSA (i.e. $C=M^e\bmod N$ and $M = C^d\bmod N$). Is there any way, using some form of CCA or whatever the sort, to recover the primes/private exponent of the RSA key? I know CCA is traditionally used to find the plaintext rather than the key, but since the app, in this case, decrypts the message for us, there is no need. Is it even cryptographically possible?

  • 2
    $\begingroup$ I guess it is meant "private exponent $d$". $\endgroup$
    – fgrieu
    Commented May 27, 2020 at 6:30
  • $\begingroup$ Related, simpler question. $\endgroup$
    – fgrieu
    Commented Dec 9, 2020 at 10:49

1 Answer 1


Is there any way, using some form of CCA or whatever the sort, to recover the primes/private exponent of the RSA key?

TLDR: No, save for a breakthrough or a leak.

Whether $N$ can be factored (in time polynomial to $\ln N$ with non-vanishing probability) given $(N,e)$ and an RSA decryption blackbox (assumed free of side-channel leakage) is one of the most thought at open problem in cryptography, and to a lesser degree in number theory.

Proving either yes or no would make the news, even if restricted to an heuristic algorithm, plausible mathematical hypothesis, a polynomial of degree so high that the method is impractical, and a particular choice of $e$. I'm thinking of $e=3$, or $e=N$ (the Clifford Cock's cryptosystem, which predates RSA), or on the contrary random odd $e\in[0,N])$.

A proven fact is that extracting any working private exponent $d$ of size upper-bounded by a polynomial in $\ln N$ allows to extract a factor of $N$, at least heuristically and in heuristic polynomial time, and in practice allows to factor $N$.

Another experimental fact is that if we probe a physical implementation of such a black box, that has a public design, long enough, with sensitive-enough sensors, and pour enough brainpower and a little CPU power on the thing, we manage to extract $N$. This is one of several understandable reasons why such black boxes are not made of public design.

BTW: experimental cryptanalysis with quantum sensors is the one unobstructed way for experimental cryptanalysis to go quantum.

  • 3
    $\begingroup$ This answer is interesting but I fear that it may not be comprehensible to someone who needs to ask. In plain English: “Not unless there's a fundamental breakthrough in cryptography, or unless the black box is not a black box after all due to side channels”. $\endgroup$ Commented May 27, 2020 at 7:27
  • 1
    $\begingroup$ "at least heuristically and in heuristic polynomial time"; actually, there is a known deterministic polynomial algorithm to factor the modulus with $d$ and $e$ (from the "crypto trivia R us" department) $\endgroup$
    – poncho
    Commented Oct 19, 2021 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.