Score:1

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

in flag

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?

fgrieu avatar
ng flag
“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.
harpomiel avatar
in flag
How is it unrelated? I think that gets to the crux of what I am asking.
fgrieu avatar
ng flag
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).
Score:4
es flag

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 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, 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 both $A+B$ and to $C$.

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. Since it would take forever to actually calculate this by adding G to itself $a$ times, there are mathematical shortcuts available. 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 becomes a one-way "trapdoor" 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.

Score:2
ng flag

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.

Score:-1
ng flag

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.

fgrieu avatar
ng flag
This is not a correct way to describe signature. Decryption with public key is a terminology mistake. Many common signatures systems ([EdDSA](https://en.wikipedia.org/wiki/EdDSA), [ECDSA](https://en.wikipedia.org/wiki/ECDSA), [DSA](https://en.wikipedia.org/wiki/Digital_Signature_Algorithm)) 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.
Score:-1
gh flag
epp

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

fgrieu avatar
ng flag
This is not answering the [present question](https://crypto.stackexchange.com/q/99740/555). 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.
epp avatar
gh flag
epp
Not implying anything, but explicitly stating that it's the "magic" of mathematics.
knaccc avatar
es flag
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.
epp avatar
gh flag
epp
thanks @knaccc, edited to clarify that
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.