How can you verify private key ownership using a public key and message signature?

Question

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?

Answer 1

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.

Answer 2

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:

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.

Answer 3

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.

Answer 4

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).