3
$\begingroup$

As we know about Shor's algorithm on quantum computers it is possible to crack RSA / ECC easily if we have enough qubits.

Is it possible to crack RSA / ECC on a quantum computer if we only have ciphertext and don't have the public key used to encrypt itself?

Does it matter if we have many ciphertexts and corresponding plaintext for some of them that are generated using the same public key?

$\endgroup$
  • $\begingroup$ I've indeed removed your third question and simplified the text in your question for the benefit of future readers. If you see that a question is off topic (and not answered in the accepted answer) then please remove it and possibly ask separately. Generally we assume that multiple ciphertext are available to an attacker, so the second question is not really needed either (but that's only true in hindsight, so I've left it in). $\endgroup$ – Maarten Bodewes May 9 at 10:52
5
$\begingroup$

You asked:

Is it possible to crack RSA / ECC on a quantum computer if we only have ciphertext and don't have the public key used to encrypt itself?

Typically not, with a few exceptions; here are the exceptions:

  • RSA signatures with deterministic padding (eg. PKCS #1.5) and a small to moderate $e$ (e.g. $e = 65537) - with two signatures (and corresponding message), we can recover the public key with a conventional computer (and then use our quantum computer to break it).

  • ECDSA signatures - with one signature (and corresponding message), we can recover the public key (with a few "false hits") with a conventional computer; we can then use our quantum computer to break it.

Things that likely look immune:

  • RSA encryption (which always uses random padding), or randomized RSA signatures (e.g. PSS); the relationships between the plaintexts would appear to be too subtle for the attacker to use them.

  • EdDSA signatures - because of how the public key is stirred in, the key recovery method we used with ECDSA doesn't work (and without the public key, the attacker can't compute $H(R, A, M)$, which you need to know to have a copy of generating a forgery)

  • ECIES - the ciphertext consists of $rG$ (for some random $r$) and a symmetric ciphertext that is keyed based of $rP$; the attacker could recover the value $r$ with his handy quantum computer, however without knowing $P$, there's not much else he can do (and having multiple ciphertexts wouldn't appear to help).

| improve this answer | |
$\endgroup$
  • $\begingroup$ i edited the question to include having plaintext for some of ciphertexts , i'd appreciate if you edit your answer to include answer for that case too (i'll delete this comment when answer is edited by you) $\endgroup$ – emaditaj May 9 at 20:21
  • $\begingroup$ i mean for ecies if we have plaintext, so we can get the key used in symmetric algo , so now we know P (you said "without knowing P, there's not much else "), and with having p break the sytem , am i right or the P is something else , and we can't get it if you have key used for symmetric algo $\endgroup$ – emaditaj May 10 at 21:47
  • $\begingroup$ @emaditaj: "for ecies if we have plaintext, so we can get the key used in symmetric algo"; actually, for the symmetric algorithms we actually use in ECIES, you cannot recover the key with just a single plaintext/ciphertext, even with a quantum computer (I'd argue that'd be the case even if it were a 128 bit key, but that is marginal). In any case, with ECIES, that symmetric key is generated via a KDF, which is itself one-way... $\endgroup$ – poncho May 11 at 3:13

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.