# Sign without Knowing the Private Key in ECDSA

We demonstrate how to generate a valid signature, **without** knowing the private key, using Elliptic Curve Digital Signature Algorithm (ECDSA).

# ECDSA Signing

Alice thus has a private key (*d*) and a public key (*Q = dG*). She signs a message (*m*) with the following steps:

- Hash the message:
*h = HASH(m)*. - Create a random number
*k*and calculate*R = kG*. Find*R*’s x-coordinate*r*. - Calculate
*s = (h + rd)/k*.

The signature is the pair (*r, s*). Both *r* and *s* are just scalar numbers.

# Sign without Knowing the Private Key

Conventionally, Alice has to know a private key to generate a valid signature against its public key. Remarkably, a valid signature can be generated without knowing the private key as follows:

- Generate a random number
*r*. If there is no point*R*on the curve with*r*as its x-coordinate, simply try another value of*r*. - Generate a random number
*s*. - Solve for the public key as
*Q = (sR - hG)/r*.

(*r, s*) is a valid signature for public key Q and message m. To see why, we can derive *Q* as follows:

s = (h + rd)/k

sk = h + rd

skG = hG + rdG

sR = hG + rQ

Q = (sR - hG)/r

We call *Q* a ** keyless** public key, as it is not derived from a known private key. In contract, let us call a public key

**if it is derived from a known private key, as typically done.**

*keyed*Note signature is generated first **before** a public key is derived, which is the opposite of a regular ECDSA signing.

# Implications

If a public key is generated keylessly, only the person who generates it can produce a valid signature against it, *with the signature*** and the message with hash h**. The signature and the message jointly act as the private key here, which exists but is

**unknown**. Note message hash

*h*is used and thus committed in calculating

*Q*, meaning the signature is

**only valid for m**, but not for any other message. Both the signature and the message are needed for the signature to verify against the public key.

## Keyless vs keyed key

The private key of a keyed public key is known, while that of a keyless one unknown. In a keyed scenario, the public key is known before the signature; while it is the opposite in a keyless one.

By looking at a public key **alone**, it cannot be determined if it is keyless or keyed.

Even one signature is revealed for **one** message, it is impossible to decide if the public key is keyless or not, since the signature can come from a private key, or generated in advance.

However, if Alice can sign against a message chosen by Bob, it is overwhelmingly likely she knows the private key, since she does not know the message committed in the public key in advance and cannot generate a valid signature.

If there are signatures for two different messages, even both chosen by Alice, we can be sure the public key is keyed.

## Use in Bitcoin

It is alleged that the public key (denote as *Q₀*) in Bitcoin’s Genesis coinbase transaction is keyless. If so, whoever possesses the signature can sign one message, the one used when calculating *Q₀*. He cannot sign any other message.

**However, the signature is only valid off chain, but not on chain**. Coins sent to that Q₀ cannot be spent with such a signature, including ones sent after the Genesis block¹. Too see why, we have to look at what message *m* is signed when creating a transaction. It basically includes the current spending transaction, plus the output being spent. The output contains *Q₀* in its script part, meaning m depends on *Q₀*. However, *Q₀* itself depends on *h*, *m*’s hash. This circular dependency (to get *Q₀*, you need *m* first; but to get *m*, you need *Q₀* first), similar to a signature cannot sign itself in Bitcoin, prevents generating *Q₀*.

Note this applies to any public key in bitcoin, not only *Q₀*.

# Implementation

Below is a full working example, where a signature is generated without knowing the private key.

Anyone can run and independently verify it. A test run is shown below.

# References

- Blake, I.F., Seroussi, G. and Smart, N.P. (eds.) (2005)
*Advances in Elliptic Curve Cryptography*. Cambridge: Cambridge University Press (London Mathematical Society Lecture Note Series). - Graph credit: Buchanan, William J (2024). Elliptic Curve Digital Signature Algorithm (ECDSA). Asecuritysite.com. https://asecuritysite.com/ecdsa/ecdsa2

[1] Coinbase output in the Genesis block cannot be spent even if the public key in it is keyed, since it is not included in the UTXO set. https://gist.github.com/msinkec/5eaf5aa97ed0f5e8d66e7e32fd8b1a0a