2
$\begingroup$

When I sign a message with a private key, and I get a message signature, how is it that I'm able to - using the corresponding public key - verify that that message/transaction signature must have been produced by the person holding the private key behind the relevant public key?

My understanding is that with private/public key pairs, the point of the technology is that you cannot reverse engineer the private key from the public key. So how is it possible to do that?

Essentially, what is the difference between reverse engineering a private key from a public key, and verifying that someone must have the private key to produce a message signature that corresponds to a public key? How is one possible but not the other?

$\endgroup$
3
  • $\begingroup$ “I sign a message/transaction with a private key” is unrelated (except perhaps for the method used) to “I get a message/transaction signature”. In particular, it's not used the same public/private key pair in both, and the signature is (likely) different. To make the question simpler/sharper, I suggest "When I get a message/transaction signature, how is it that I'm able to…". The reason itself has to do with the very nature of signature. $\endgroup$
    – fgrieu
    Commented Apr 19, 2022 at 19:39
  • $\begingroup$ How is it unrelated? I think that gets to the crux of what I am asking. $\endgroup$
    – harpomiel
    Commented Apr 19, 2022 at 19:42
  • 2
    $\begingroup$ It's unrelated because in the first you/I sign with your/my private key, and in the second "the person holding the private key" (which is their's, not your's/mine) signs with their private key. The two public/private key pairs are (likely) separate in value, and perhaps in nature: for what the question says, one could be RSA, the other EdDSA, and that's often the situation in practice in web interactions. Remember that signature verification does not require knowledge of a private key, only of the signer's public key matching the private key used for signing (and message, signature). $\endgroup$
    – fgrieu
    Commented Apr 19, 2022 at 19:47

4 Answers 4

5
$\begingroup$

I'll explain how signatures involving elliptic curves work. Cryptocurrencies mostly use elliptic curves due to the smaller size of signatures that need to be published on the blockchain.

When a private key, which is just a large integer, is mapped to a public key (which is a point on a specified elliptic curve), this mapping has certain useful mathematical properties. Note that this mapping is done in such a way that it is "one way". You can easily map from the private key to the public key elliptic curve point, but you can't practically reverse that operation.

Firstly, an elliptic curve is chosen because the points on the elliptic curve will form an Abelian group under an operation that we call "addition". This means you can do what looks like simple algebra with the points. You can take points $A$ and $B$, add them to get point $C$, and you will be able to observe that $A+B==B+A$. Note that we only define addition and subtraction operations, and we can't "multiply" points or "divide" points with other points.

Secondly, the mappings of private key integers to points are "additively homomorphic". This means if you have the private keys $a$ and $b$, which map to the public keys $A$ and $B$, then the public key of $a+b$ will be equal to the point $A+B$.

The mapping of a private key to a public key is simply to take a private key $a$ and calculate the public key $aG$, which means to add the well-known point $G$ to itself $a$ times. It would take forever to calculate this by adding $G$ to itself $a$ times, but there are mathematical shortcuts we can use to do this quickly. Since these shortcuts only exist to perform the multiplication quickly but not to go backwards and determine the private key from whatever the multiplication result is, this mapping is a one-way function.

Now, imagine that I have the private key $a$ and the public key $A=aG$, and you present a challenge to me. You come up with a random private key integer $x$, and you ask me to give you a response integer $y$ such that you can verify that $xA==yG$. I will only be able to pass your challenge if I know the private key $a$, which would allow me to calculate $y=xa$. This would verify because then $xA==xaG==yG$.

What I've described above has two flaws. The first is that once I pass the challenge, you can easily then calculate my private key $a$ as $y/x$.

The second flaw is that I need you to provide me with a challenge, rather than simply being able to provide you with a signature without having to interact with you.

The first flaw is addressed by including a "blinding factor", which allows me to pass the challenge without revealing my private key. For example, with a Schnorr signature, I pick a random private key $k$, reveal only $K=kG$, and then ask you for your challenge $x$. Then I produce a value $y$ such that you can verify that $xA==K+yG$. Now, after I reveal $y$ to pass the challenge, you know that I could have only calculated $y$ with knowledge of my private key $a$, but you can't calculate my private key without knowing my secret blinding factor $k$.

The second flaw is addressed by using the Fiat–Shamir heuristic to create a challenge using a function serving as a "Random Oracle" that allows me to come up with the random challenge without a way to cheat. In the case of the ECDSA signature scheme, this function output is the x-coordinate of a public key mapped from a particular input. In the case of a Schnorr signature, the function is a cryptographically secure hash such as SHA512/256.

$\endgroup$
3
$\begingroup$

When I sign a message/transaction¹ with a private key,
and I get a message/transaction¹ signature,

Critically, it's used different public/private key pairs in these two things. Nothing in the rest of the question is about the first of these two things. Everything is about verifying the signature in the second of these things, against the public key of the public/private key pair used by the signer in said second thing. Said public key is assumed available to the verifier. The matching private key is not.

With private/public key pairs, the point of the technology is that you cannot reverse engineer the private key from the public key

Correct. There's slightly more to it: with the public key it's not possible to perform the things that the private key is intended to perform.

What is the difference between reverse engineering a private key from a public key, and verifying that someone must have the private key to produce a message signature that corresponds to a public key? How is one possible but not the other?

Signature works according to this diagram:

signature and by a modern textbook

  • $1^n$ encodes integer $n$ defining the size of keys. In practice $n$ is fixed and public.
  • $(\mathrm{pk},\mathrm{sk})$ is a public/private key pair output by the key generation algorithm $\mathrm{Gen}$. It's assumed $\mathrm{sk}$ is kept secret by the assigned owner of the key pair, who most often is the one who ran $\mathrm{Gen}$.
  • $m$ is the message to sign (an arbitrary bitstring, save perhaps for size requirements).
  • $\sigma$ is the signature of the message. It's produced from $\mathrm{sk}$ and $m$ by the signature algorithm $\mathrm{Sign}$.
  • $b$ is the integrity indicator, which takes one of two values, Valid or Invalid. It's produced from $\mathrm{pk}$, $m$ and $\sigma$ by the verification algorithm $\mathrm{Vrfy}$.

A signature scheme is correct when, with things as per the drawing, $b$ always is Valid. It's secure² when adversaries given $\mathrm{pk}$ and the ability to obtain $\sigma_i$ for any $m_i$ they see fit, are unable to exhibit an $(m,\sigma)$ pair with $\mathrm{Vrfy}(\mathrm{pk},m,\sigma)$ Valid, and $m\ne m_i$ for any $i$. There are a few more technical details³.

It's surprising that there are correct and secure signature schemes. Devising one was long in the making. But it's no more surprising than the possibility of public key encryption. If one mostly cares for understanding the use of signature, an option is to admit there are such signature schemes.

Another option is to study one. I suggest Schnorr signature (alt. version), which principle is used in some cryptocurrencies, is perhaps the simplest, and has a relatively simple quantitative security reduction to the hardness of the Discrete Logarithm Problem in the group used, under a random oracle model of it's hash. Exposing it would about triple the length of the answer.


¹ In a cryptocurrency context, a message may describe a transaction.

² By the Existentially UnForgeable under Chosen Message Attack criteria, often the only one discussed in modern introductory exposition. There are other useful signature security criteria.

³ $\mathrm{Gen}$, $\mathrm{Sign}$, $\mathrm{Vrfy}$ and adversaries are modeled as probabilistic polynomial time algorithms. Propositions are stated for any fixed $(\mathrm{pk},\mathrm{sk})$ pair output by $\mathrm{Gen}$, and except with negligible probability $p(n)$, that is $p(n)$ such that for any polynomial $Q(n)$ it holds $\displaystyle 0=\lim_{n\to\infty} p(n)\,Q(n)$. In practice $n$ is chosen high enough to make that probability practically negligible.

$\endgroup$
-1
$\begingroup$

Essentially, what is the difference between reverse engineering a private key from a public key, and verifying that someone must have the private key to produce a message signature that corresponds to a public key? How is one possible but not the other?

It is practically impossible to find the private key based on the public key, and this is the whole point of public-private key cryptography. This is pure beauty of math. Your second question is asking how the digital signature works. The digital signature is commonly produced by first compute the digest of the your plain text message (for example using sha256), then encrypt the digest using your private key. Your cipher text alongside the digital signature looks like:

public_announcement, signature=encrypt(sha256(public_annoucement), private_key)

Any receiver can compute the sha256 digest of public_annoucement and compare with decrypt(sha256(public_annoucement), public_key)`. If these two does not match, either the annoucement is tampered or it is not signed with the private key that it claimed to be.

$\endgroup$
1
  • 5
    $\begingroup$ This is not a correct way to describe signature. Decryption with public key is a terminology mistake. Many common signatures systems (EdDSA, ECDSA, DSA) do not at all work in this way. When encrypt and decrypt are textbook RSA encryption and decryption, the signature system described is vulnerable to existential forgery. None of the two RSA signature schemes in wide use can be described in this way with encrypt and decrypt safe encryption schemes. $\endgroup$
    – fgrieu
    Commented Apr 19, 2022 at 20:13
-1
$\begingroup$

The answer without lengthy mathematical formulas to the essential part of your question which is about reverse engineering a private key from a public key is presented here:

A private key cannot be (easily) mathematically generated from a public key (i.e. "one-way function")

Specifically in case of elliptic-curve cryptography, the one-way function is discrete exponential and logarithm (and not a trapdoor mentioned in the referenced original answer which is used by the RSA algorithm).

$\endgroup$
4
  • 2
    $\begingroup$ This is not answering the present question. Also, if by mathematically we imply that we disregard the necessary computing power, a private key (that matches a public key) can be mathematically generated from a public key. Much like, mathematically (understood as above), any number can be decomposed into a product of prime factors. $\endgroup$
    – fgrieu
    Commented Mar 9, 2023 at 15:13
  • $\begingroup$ Not implying anything, but explicitly stating that it's the "magic" of mathematics. $\endgroup$
    – epp
    Commented Mar 10, 2023 at 17:00
  • $\begingroup$ The mapping from a private key to a public key needs to be a one-way function, but not necessarily a trapdoor function. EC public keys, for example, are not mapped from private keys using a trapdoor function. $\endgroup$
    – knaccc
    Commented Mar 10, 2023 at 18:23
  • $\begingroup$ thanks @knaccc, edited to clarify that $\endgroup$
    – epp
    Commented Mar 13, 2023 at 13:30

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.