1
$\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$
6
  • 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, 2014 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, 2014 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, 2014 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, 2014 at 23:58
  • $\begingroup$ If you use a reference stating that signing a document amounts to "use the private key to encrypt the hash of the document" without a ton of caveats about that improper use of encrypt, do yourself a favor and dump that reference. $\endgroup$
    – fgrieu
    Mar 21, 2020 at 7:38

1 Answer 1

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 and acknowledge you have read our privacy policy.

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