8
$\begingroup$

Given enough RSA ciphertext, is it possible to determine which public key was used to generate the ciphertext?

Presume an unknown public key that was used to generate RSA ciphertext, and we have quite a lot of ciphertext. Would it be possible to determine which key was used to generate the ciphertext?

It seems to me that any ciphertext would be in the range $[0, N)$ where N is the modulus. So if you have enough ciphertext you should be able to estimate a value for N. Now I don't think that this would be enough to establish N even when given enough ciphertext. But I wonder if you could find out which key was used from a set of public keys with some certainty.

Could there be enough information to establish which key is used? Is there a formula that would allow me to calculate the certainty for each key out of a set? Would that formula only consider basic probability over the range or is there anything in the RSA scheme to be more precise?

Only padded RSA with PKCS#1 v1.5 padding or OAEP padding may be considered, not raw/textbook RSA.

$\endgroup$
2
  • $\begingroup$ My guess would be "no" because of the randomized padding preventing many conclusions. Trivial solution though: Look at the size of the ciphertext. If you have a 8kbit key and a 2kbit key, chances are the sizes are different. $\endgroup$
    – SEJPM
    Mar 12, 2016 at 14:58
  • $\begingroup$ @SEJPM Yeah, but it's not just the size of the ciphertext. If the modulus is smaller than the ciphertext then that modulus obviously wasn't used to generate it. And if you have a lot of ciphertext then quite obviously the absence of large values would indicate that a large modulus wasn't used. $\endgroup$
    – Maarten Bodewes
    Mar 12, 2016 at 15:08

2 Answers 2

6
$\begingroup$

Yes, it is possible to determine with some certainty which public key in some known set was used to produce RSA ciphertexts made with the same key in this set, given enough ciphertexts, and if neither the public moduli nor the random padding are made with intend to hide which public key was used.

Assume that the set of $k$ public keys have public moduli $N_i$, ordered in increasing order, and we initially have no clue about which might be the one used. If we chose random padding as in any of the two PKCS#1 encryption paddings (randomly and independently of the RSA key), any of $r$ ciphertexts is essentially uniform on the interval $[0,N_j-1]$ where $N_j$ is the public modulus actually used to produce the ciphertexts. The obvious strategy to guess the public key used is to determine the largest of the ciphertexts $C$; the most likely public key in the set is the one with the $N_i$ immediately superior to $C$, and $i\le j$ holds.

Odds that our guess $N_i$ of the public modulus is right are $1/\sum_{j\ge i}(N_i/N_j)^r$, which depends only on where $C$ falls in-between the public moduli, and the values of these (justification: only $j\ge i$ can hold; for any of these $j$, the odds to get a $C$ not higher than what we actually got were $p(C,N_j)=(C/N_j)^r$ before we knew $C$; all these $j$ were then assumed equally likely; therefore the odd of $i=j$ are the ratio of $p(C,N_i)$ over the sum of the $p(C,N_j)$ for $j\ge i$, which simplifies to the expression given).

Note: it is easy to defeat this guessing; for example, when using 2048-bit $N$, encrypt a given plaintext until the result is 2047-bit or less, before sending it.

$\endgroup$
4
$\begingroup$

Could there be enough information to establish which key is used?

If you know the message being signed, and if the signature method is deterministic (e.g. PKCS #1.5 signature padding), then you can do it with 2 signatures (!).

Here's how that would work; first, you guess $e$ (which is most often 65537). Then, you observe that $S^e \bmod N = Pad(M)$ implies that $S^e - Pad(M)$ is a multiple of $N$; hence if we have two messages $M, M'$ and the two signatures $S, S'$, we can compute $gcd( S^e - Pad(M), S'^e - Pad(M'))$, and that'll be a small multiple of $N$

$\endgroup$
6
  • $\begingroup$ That's a very cool answer and I'll make sure I keep it for posterity. However, this seems to be about signature generation rather than encryption. Should have added the encryption tag as well, sorry for that. $\endgroup$
    – Maarten Bodewes
    Mar 12, 2016 at 15:10
  • $\begingroup$ Well, yes, it won't work for any reasonable pk encryption method, because those invariably have randomized padding. On the other hand, your question isn't strictly about pk encryption; for one, you did mention that "It seems to me that any signature would be in the range..." $\endgroup$
    – poncho
    Mar 12, 2016 at 15:16
  • $\begingroup$ Typo, sorry for that. It seems to me that this warrants another question for signature generation. What if I ask another question so you can use this answer for that? Would that suite you? $\endgroup$
    – Maarten Bodewes
    Mar 12, 2016 at 15:19
  • $\begingroup$ I'm pretty sure it won't be a "small" multiple of $N$. Assume you have a 2048-bit modulus. Then $S^e\approx 2^{134,219,776}$. Related answer of mine (deterministic case only). $\endgroup$
    – SEJPM
    Mar 12, 2016 at 15:20
  • $\begingroup$ Asked a new question here $\endgroup$
    – Maarten Bodewes
    Mar 12, 2016 at 15:25

Your Answer

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

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