0
$\begingroup$

I am starting to learn more about cryptography and I just read more about how asymmetric keys can make a digital certificate, and I would like if someone could explain me why the following case can't be applied:

Since asymmetric keys rely on a pair of keys, and you use the private key to encrypt the hash of the document you want to sign so someone later can read the encrypted hash using your public key, to look for a match with the document's hash...why can't someone generate another private key that will match your public key and fool the whole process?

Usually every text about asymmetric cryptography focus on how difficult it is to find the original private key or to break the cypher-text, but my point is, in order to make someone believe your document/code/website is legit and certificated, you don't need to find the original private key, any new "malicious" private key that matches the well known public key of the CA (certification Authority) will be able to sign everything you want with this new key, so the public key will match and decrypt it.

I don't know very well the asymmetry keys math, so there might be "something" there that also prevents this, but so far I haven't seen any information, like how unique is the connection between the keys and how difficult it is to generate a key ('A') that will match a previously given key ('B').

$\endgroup$
  • 1
    $\begingroup$ In RSA each public key $(n, e)$ corresponds to exactly one private key $(n, d)$, so there are no other private keys to find. I think there was recently a duplicate question but can't find it now. $\endgroup$ – otus Sep 30 '14 at 6:20
  • 4
    $\begingroup$ Someone can't "generate another private key that will match your public key" because known ways to do that with currently existing technology would take too long to have a non-negligible probability of success. $\endgroup$ – user991 Sep 30 '14 at 8:07
  • $\begingroup$ This sentence in a White Paper made me a little confuse about it: "The secure boot mechanism cannot detect the new software upgrade, because the comparison was applied with the public key paired with the hacker’s private key." Maybe it's better if you post it as an answer instead of a comment? $\endgroup$ – mFeinstein Sep 30 '14 at 17:31
  • $\begingroup$ @mFeinstein It's no wonder that that sentence in the white paper (which one?) left you a little confused. Better forget about it. $\endgroup$ – Maarten Bodewes Oct 1 '14 at 23:58
3
$\begingroup$

why can't someone generate another private key that will match your public key and fool the whole process?

Because in most schemes, this is equivalent to recovering the private key from the public key (this can be somewhat easily seen for RSA and trivially for ECC-based schemes). And as we assume that recovering the private key from the public key is hard, finding a secondary private key that matches a given public key can be considered hard as well.

$\endgroup$

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.