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?

  • 1
    $\begingroup$ I guess it is meant "private exponent $d$". $\endgroup$ – fgrieu May 27 at 6:30

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.

| improve this answer | |
  • 1
    $\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$ – Gilles 'SO- stop being evil' May 27 at 7:27

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.