Public keys, private keys, signatures

The starting question

You send 5,000 CFA francs by mobile money. The operator asks for your PIN and checks it is right: to do that, it must know the secret (or hold what is needed to check it). If someone at the operator is dishonest, your secret is at risk.

On an open network there is no trusted operator. You need a way to prove "it is really me" without ever handing the secret to the person who checks. That is the purpose of a key pair.

The concept

A key pair is two linked numbers:

• the private key: a secret number drawn at random. It is 32 bytes (256 bits) for common elliptic curves such as P-256 or Ed25519;
• the public key: computed from the private key by a one-way operation. You can publish it.

"One-way" means: going from private key to public key is fast; going back is, as far as current knowledge goes, infeasible for well-chosen keys. This is not an absolute mathematical proof: it is a hardness assumption (the elliptic-curve discrete logarithm) that experts have been testing for decades. A large enough quantum computer would break that assumption; none exists today, but it is a known limit.

How many private keys are possible?

A 256-bit private key can take about 2^256 ≈ 1.16 × 10^77 values. Two people drawing at random will not land on the same one, provided the randomness is of cryptographic quality. A weak generator (for example a browser's Math.random) makes the key guessable. Your browser uses the operating system's generator for this, not Math.random.

Two algorithm families in this workshop

The course catalogue names ed25519 for the local lab; the browser tool instead uses ECDSA on the P-256 curve because that is what the browser's cryptography API (WebCrypto) offers everywhere. The ideas are the same: a private key signs, a public key verifies. Bitcoin uses another curve (secp256k1); Ethereum too. The concepts transfer, the bytes do not.

Your turn

Open the tool below and generate a key pair. Note that the private key is never displayed: it stays in your browser's memory. Export the public key: it is base64 text you could send to anyone.

What this does NOT guarantee

Owning a key pair says nothing about who you are. Anyone can generate a thousand in a second. A public key is just a number; tying it to a person or a company takes something else (see the next lesson).

Recap

• The private key is a large secret random number; the public key follows from it in one direction only.
• That one-way property is a hardness assumption, not an absolute proof.
• A key pair proves no identity by itself.

The starting question

Aminata receives a message: "Pay 5,000 CFA francs to Didier". A signature is attached. What exactly does she know if verification succeeds?

The concept

There are two operations:

• sign(private_key, message) → a signature (64 bytes in raw form for ECDSA P-256 or Ed25519);
• verify(public_key, message, signature) → true or false, nothing else.

In practice the signature covers the message's digest (see workshop 104): ECDSA signs a digest of the message (the page's tool uses SHA-256; ECDSA itself does not impose it), Ed25519 builds in its own hashing. That is why signing a 1 GB file is as fast as signing an SMS.

A worked example with the tool

In the tool, sign the text Pay 5000 CFA to Didier, then run five verifications:

The last row is the most instructive. Let us see what one can conclude.

What a signature proves (under assumptions)

If verification succeeds, and if the private key has not leaked and the scheme is secure:

1. Key authenticity: the message was signed by someone holding the private key matching this public key.
2. Integrity: the message has not been changed by a single bit since signing.

What a signature does NOT prove

• Not a person's identity. It proves a key was used. Who holds the key? For a website, a certificate authority signs a document tying a domain name to a public key; on a blockchain you simply follow the key as a pseudonym.
• Not the truth of the content. One can sign a lie perfectly well.
• Not freshness. A signature carries no date. Replay (row five) stays valid: that is why transactions on account-based chains (Ethereum, and our practice network) also sign a nonce (a per-account counter) and a chain id, as in the bac-practice|chain=…|nonce=… exercise below. Bitcoin transactions carry neither an account nonce nor a chain id: the signature covers the exact output being spent, and an output already spent cannot be spent again, which plays a comparable anti-replay role.
• Not intent. A key signed; did a human mean to sign? Malware using the key produces perfectly valid signatures.
• Not confidentiality. The message stays readable by everyone.

A difference from HMAC

In workshop 104 you saw that an HMAC authenticates a message with a shared secret. The recipient, who knows that secret, could therefore forge a valid HMAC. With a signature the verifier holds only the public key: it can verify, it cannot sign. That is what lets a third party settle a dispute.

Recap

• verify answers true or false for three objects: message, signature, public key.
• True = "this key signed these bytes", assuming the key stayed secret.
• Not identity, not truth, not freshness, not intent.

The starting question

You often hear: "signing is encrypting with your private key". That is wrong for the schemes in this workshop, and the phrase causes real mistakes. Let us see why.

Two different goals

In a signature the direction is therefore the reverse of encryption: the secret produces, the public part checks.

Why "encrypt with the private key" is misleading

• ECDSA and Ed25519 are not encryption algorithms. They only know how to sign and verify: you cannot "decrypt" a signature to recover the message.
• Even for RSA, where the picture exists historically, safe implementations use a padding specific to signatures, different from the one for encryption. Using one primitive for the other leads to flaws.
• Good practice: one key, one purpose. Do not reuse a signing key for encryption, or the reverse.

A worked example: what an observer sees

Aminata sends to Didier over a public network:

1. Signed, not encrypted: the observer reads "Pay 5000 CFA to Didier"; cannot alter it without breaking the signature; can copy and replay it (previous lesson).
2. Encrypted, not signed: the observer reads nothing; but anyone knows Didier's public key and could have written this message. Didier cannot tell who sent it.
3. Both: you get confidentiality and authenticity, with two operations and preferably two key pairs.

In a public blockchain, transactions are signed but not encrypted: everyone must be able to verify them. Encryption is not the basic mechanism there.

Your turn

In the HMAC tool, compute the HMAC of a message with the key secret1, then check that anyone who knows secret1 can produce the same value. Compare with the signing tool: here, verification does not require knowing the signing secret.

What this does NOT guarantee

Signing hides nothing. Encrypting does not prove who wrote. Neither protects against loss of the private key.

Recap

• Encrypting = confidentiality; signing = authenticity and integrity.
• ECDSA and Ed25519 do not encrypt.
• A signed message stays readable.

The starting question

An employee pastes their private key into a chat group, then deletes the message thirty seconds later. Is the problem solved?

No. To see why, you must see what the network can and cannot tell apart.

Why it is irreversible

Verification tests only one thing: "does this signature match this public key?" It has no way to know who holds the private key. After a leak:

1. The thief produces valid signatures, indistinguishable from yours.
2. On a blockchain, they can empty the account with a single message. Confirmed transactions are not undone.
3. As a rule there is no authority to ask to "revoke" a key: that is the very principle of the system. Your only defence is to move the funds to a new key before the thief does, and it is a race.
4. Signatures already made stay valid. Without a trustworthy timestamp it becomes hard to say whether an old document was signed before or after the leak.

Deleting the message does not erase the copies: a bot may have read it within a second. A key that was ever visible must be treated as compromised forever.

Another way to lose the key: a failed nonce

ECDSA uses, at every signature, a one-time secret number k (an ECDSA "nonce", not to be confused with an account nonce). If two signatures use the same k, the private key d can be computed from the two. Here is the principle on a toy model: a small prime n = 23. In real ECDSA, n is about 2^256 and r comes from a curve computation; here r is simply given, because only the algebra matters.

The signature is: s = k⁻¹ · (z + r·d) mod n, where z is the message digest, r is identical for both signatures (same k) and d is the private key.

Example: d = 9 (secret), k = 5 (reused), r = 7.

• Message 1: z₁ = 10, so s₁ = 5⁻¹ · (10 + 7·9) = 14 · 73 mod 23 = 10 (since 5⁻¹ = 14 mod 23, and 73 mod 23 = 4, 14·4 = 56 = 10 mod 23).
• Message 2: z₂ = 3, so s₂ = 14 · (3 + 63) = 14 · 66 mod 23; 66 mod 23 = 20; 14·20 = 280 mod 23 = 4. So s₂ = 4.

The observer sees only (r, s₁, z₁), (r, s₂, z₂). They compute:

• k = (z₁ − z₂) · (s₁ − s₂)⁻¹ = 7 · 6⁻¹ mod 23 = 7 · 4 = 28 = 5 ✔
• d = (s₁·k − z₁) · r⁻¹ = (50 − 10) · 7⁻¹ = 40 · 10 mod 23 = 400 mod 23 = 9 ✔

Two signatures, one private key. This flaw has been exploited in real products because of faulty random generators; Ed25519 prevents it by deriving k deterministically from the key and the message (a design property of that scheme); deterministic ECDSA (RFC 6979) does the same. In our browser tool, the system's random generator does this job: its quality matters.

What this does NOT guarantee

A backup of the key (a recovery phrase, for example) protects against loss, but increases the risk of leak: each copy is a target. It is a trade-off to weigh, not a box to tick.

Recap

• The network cannot tell the owner from the thief: it only sees valid signatures.
• An exposed key is compromised forever; you move funds, you do not "revoke".
• A reused ECDSA nonce reveals the private key.