Does an adversary require the public key to perform operations when RSA or ECC is broken?

Question

If we had a way to break signature or encryption schemes (e.g. recover the key, recover plaintexts from ciphertexts, forge signatures), e.g. a quantum computer that was powerful enough to break discrete log, would the attacker still need to know the public key used to make the encryption or verify the signature in order to decrypt or forge a signature?

That is, given merely the ciphertext or a signature without the public key, could such an attacker decrypt the ciphertext or forge other signatures?

I'm mostly interested in RSA and ECDSA, but if the situation is different for other schemes, I'd love to hear that.

Answer 1

TL;DR: yes, no, or maybe. Knowing the public key can only help an attacker. How much? It depends.

---

Usually, the public key is assumed known to all, hence its name; we'll assume it is not.

The answer depends on a lot of things: the cryptosystem, whether it is randomized or deterministic, if more than the ciphertext or signature is known (for example, if it is known matching plaintext/ciphertext pairs; if the message going with the known signature is also known; in the case of encryption, if something about the plaintext is known, like some redundancy ..). In general, the more is known, the easier it would be for the hypothetical attacker to break the cryptosystem even without the public key.

Also, the ability of the attacker matters: if s/he can break the cryptosystem with the public key, when by design of the cryptosystem s/he should not be able to do so, then perhaps she has resources not taken into account by standard security hypothesis, re-purposable for other tasks which could help towards breaking the cryptosystem without the public key: like a general-purpose quantum computer, or means of observing the internals of a supposedly impenetrable device.

---

Sometime, we can answer conclusively that the public key (or some other extra information) is required. For textbook RSA encryption $M\to C=M^e\bmod N$, a single ciphertext $C$, and unknown random plaintext $M$, the plaintext $M$ demonstrably can't be recovered from the ciphertext $C$, even by an arbitrarily powerful attacker, and even if s/he knows (a single) one of $N$ or $e$.

• If we suppose the attacker has $C$, $N$, and its factorization as $N=p\cdot q$ with $p$ and $q$ odd primes, $p<q$, the set of possible plaintexts $M$ is all the $C^{j^{-1}\bmod\operatorname{lcm}(p-1,q-1)}\bmod N$ for $j$ such that this is well-defined. Typically, there are many such odd $j$ in $[3,\operatorname{lcm}(p-1,q-1)[$, and although some lead to duplicates, the set of possible plaintexts is very large (proof welcome); and the attacker has no way to chose among theses.
• Similarly, if we suppose the attacker has $C$ and $e$, the set of possible plaintexts $M$ includes all the $C^{e^{-1}\bmod\operatorname{lcm}(p-1,q-1)}\bmod(p\cdot q)$ for odd primes $p$ and $q$ such that this is well-defined, $p<q$, and $M<p\cdot q<2^n$ where $n$ is the number of bits in the actual $N$. Typically, there are many such $(p,q)$ , and although some lead to duplicates, the set of possible plaintexts is very large (proof welcome); and the attacker has no way to chose among theses.

---

Sometime, we can answer conclusively that the public key is not required, because the attacker can find it anyway. For textbook RSA encryption restricted to small public exponent $e$ (say $3\le e\le65537$) and modulus $N$ not unusually oversize, given just three known plaintext/ciphertext pairs $(M_i,C_i)$ for arbitrary $M_i$ (much larger than $N^{1/e}$, which is necessary for security), it is quite easy to compute $N$ with high likelihood by computing $\gcd_i({M_i}^e-C_i)$ until that's not 1, for the few candidates $e$ (a classical result, proof welcome). Therefore, an attacker able to break the cryptosystem with the public key can obtain it under the usual assumption of a few known plaintext/ciphertext pairs, then break the cryptosystem.