Cracking RSA ciphertext without a public key

Question

I'm looking for some clarification on whether or not I'm correct in how I'm thinking about this.

From my understanding of RSA, the public key gives you the value $n$ (large prime $p$ times large prime $q$) and the value $e$ (a value less than $n$ which is not a factor of $(p-1)(q-1)$).

The way to try to crack a ciphertext according to the RSA problem is by using the values given to you in the public key (demonstrated in this answer). However, if an attacker only has an encrypted message without the private key (an example would be getting into a system and obtaining an encrypted file but the keys were in "Cold Storage"), he/she wouldn't be able to perform this attack.

While it's possible to recover the public key if you know the ciphertext and the plaintext, given only the ciphertext, it is likely much more difficult (if not almost impossible) to find the correct prime numbers, the value $e$, and the value $d$.

Am I correct in this assumption?

Side note: I know that the public key is named "public" for a reason, but for the sake of this scenario, just assume some situation like the one presented above.

Answer 1

It is asked if in RSA, without the public key,

it is likely much more difficult (if not almost impossible) to find the correct prime numbers, the value $e$, and the value $d$.

As first noted by Tylo in comment, if the RSA key was chosen competently, it will be impossible to find the prime numbers and $d$. Argument: if there was a method making that possible, then that method would also break regular RSA (with the public key available to the attacker); and that's a well-studied and unsolved problem, including if RSA is otherwise used incompetently (like, without padding as in textbook RSA).

Wether it will be possible to find $e$ depends on how $e$ was chosen, on the RSA padding, and on if sufficiently many known plaintext-ciphertext pairs are available:

• If $e$ was chosen at random in a large enough set (e.g. as a random odd integer with $2<e<(p-1)(q-1)$ and $\gcd(e,p-1)=1=\gcd(e,q-1)$ ), then it can't be found (argument: that $e$ is also the private exponent in an RSA system with the public exponent $d$, and we just said the adversary can't find the private exponent).
• If $e$ is small, it can be guessed (much more if it is among the usual values $e=2^{(2^k)}+1$ with $0\le k\le4$, and $e=37$ ).
  If additionally there is no random padding (as in textbook RSA), and a number of known plaintext-ciphertext pairs $(m_i,c_i)$ is known, then a guess of $e$ can be verified, and $N=p\;q$ found, by computing the GCD of enough ${m_i}^e-c_i$ (where the exponentiation is not modular). Because $N$ divides ${m_i}^e-c_i$, for enough plaintext-ciphertext pairs, this GCD will be $1$ for an incorrect guess of $e$, and $N$ for a correct guess.

Answer 2

Your linked question is not really an attack, just a silly homework. If the attacker has d and n (and even e), like in the link, he has already won.

But basically, you're right.

The hard part in cracking RSA (if it was done correctly, and OAEP etc.etc.) is finding d.

When a person generates own RSA keys, d is calculated from e, p-1 and q-1. The attacker has e, and n which is p*q, but not p and q alone. With p and q, calculating d wouldn't be a problem; but splitting n into p and q, ie. finding the only two huge prime factors of a number with thousands of digits, just isn't feasible with todays technology.

(Both p and q have to be big numbers. If the key owner uses p=3 or something like that, cracking is easy)

... btw., keys in the cloud? You could stop using encryption if you do that. Even if no government is sniffing around, and even if the provider is not selling your data, hacking into a web server is far, far easier than cracking RSA. And no, there is not a single computer in the internet which is secure against a targeted attack of a skilled person.