Signature schemes

Ed25519 explained mathematically

The signature attached to every McGesund review — from the curve through the key to the equation the reader's browser recomputes.

Last updated: 2026-09-07

1. What this is about

A review on McGesund is not a text field in a database that you have to take on trust. It is signed digitally when it is submitted, and every visitor can recompute that signature later in their own browser.

For this signature we use Ed25519. Unlike FALCON and ML-DSA, which can be added alongside as stamps, Ed25519 is not optional: every signed review carries it, regardless of plan and submission route.

One thing up front:

Ed25519 is not encryption. The review text is meant to be read. The signature does not prove secrecy, it proves origin and integrity.

2. What exactly gets signed

What is signed is not the running text but a compact data object that pins the text — and everything else — down unambiguously:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<company ID>",
  "c":   "<review ID>",
  "h":   "<SHA-256 of the review text>",
  "rh":  "<SHA-256 of the entire submission record>",
  "rv":  1,
  "qh":  "<SHA-256 of the QR envelope, QR reviews only>",
  "kid": "<key ID>",
  "iat": 1757203200
}

This object is encoded as CBOR. That byte sequence — not its tidy rendering above — is our message mm. Signature and message travel together in one envelope:

Envelope=MCG1:  ∥  base64url(CBOR[ 3,  m,  σ ])\text{Envelope} = \texttt{MCG1:} \;\|\; \mathrm{base64url}\bigl(\mathrm{CBOR}[\,3,\; m,\; \sigma\,]\bigr)

The 33 is the format version. Nothing else is in there — in particular no post-quantum signature: if one exists, it sits next to the record, not inside the envelope.

3. What the signature has to achieve

A reader arriving at a company profile faces two questions:

  1. Does this review really come from the McGesund system?
  2. Was it altered afterwards?

That is what the key pair is for:

  • a private key — stays inside the signing service
  • a public key — anyone may have it; it is addressed via the key ID (kid) in the payload

Signing uses the private key. Verifying uses the public one — in the reader's browser, not on our server. That is the whole point: a check we carry out ourselves and whose result we then report would not be a check, it would be a claim.

4. Why an elliptic curve?

Every signature needs a computation that is easy in one direction and practically impossible in the other. For Ed25519 that is scalar multiplication on an elliptic curve:

a  ⟼  A=a⋅B.a \;\longmapsto\; A = a\cdot B.

Computing the public point AA from the secret number aa takes microseconds. Getting from AA back to aa is the discrete logarithm problem — no method is known that finishes at this size within human timescales.

The practical gain over older schemes such as RSA is size:

public keysignature
RSA-3072384 B384 B
Ed2551932 B64 B

At a comparable security level. 64 bytes per review is not a quantity worth thinking about, even with millions of reviews.

5. The edwards25519 curve

Arithmetic happens modulo a prime:

p=2255−19.p = 2^{255}-19.

Hence the name. The curve is a twisted Edwards curve:

−x2+y2  =  1+d x2y2,d=−121665121666 mod p.-x^2+y^2 \;=\; 1 + d\,x^2y^2, \qquad d = -\frac{121665}{121666} \bmod p.

A "point" is a pair of numbers (x,y)(x,y) from {0,…,p−1}\{0,\dots,p-1\} satisfying this equation. There is no curve to look at — the drawing in the next section is a visual aid over the real numbers, not a picture of the actual space being computed in.

Two more quantities come into play:

  • a fixed, agreed-upon base point BB,
  • the order ℓ\ell of the subgroup generated by BB:
ℓ=2252+27742317777372353535851937790883648493.\ell = 2^{252} + 27742317777372353535851937790883648493.

ℓ\ell is prime. That means: adding BB to itself over and over walks through exactly ℓ\ell distinct points and then returns to the start. All arithmetic on scalars therefore runs modulo ℓ\ell, all arithmetic on coordinates modulo pp. Confusing these two numbers is the classic beginner's mistake.

6. Adding points

Two points are combined into a third by a fixed formula:

x3=x1y2+y1x21+d x1x2y1y2,y3=y1y2−x1x21−d x1x2y1y2.x_3=\frac{x_1y_2+y_1x_2}{1+d\,x_1x_2y_1y_2}, \qquad y_3=\frac{y_1y_2-x_1x_2}{1-d\,x_1x_2y_1y_2}.

The neutral element is (0,1)(0,1) — the point where the arithmetic starts.

This formula has one property you cannot see in it and that matters more for security than any constant: it is complete. It works for all inputs, with no special cases for "both points are equal" or "the result is the neutral element". The older Weierstrass curves do have those special cases, and each one is a branch in the program — a branch whose running time can be measured. With such schemes, anyone measuring how long a signature takes learns something about the secret key.

Complete formulas mean: always the same path through the computation, always the same time, nothing to measure.

7. Scalar multiplication — the one-way street

n⋅Bn\cdot B means adding BB to itself exactly nn times. For an nn with 253 bits that would be an absurd amount of work — so instead we double:

B→2B→4B→8B→…B \to 2B \to 4B \to 8B \to \dots

and assemble the desired nn from those intermediate results. Around 253 doublings suffice for any nn. That is the way forward.

Backwards there is no such shortcut. Determining the number aa from the point AA means solving the discrete logarithm problem.

(0,1) — neutral elementB2B3B4B5B6B
An Edwards curve with the first multiples of the base point, computed with the real addition law. Over the real numbers they still move around the curve in visible order — you could trace the way back. Modulo p exactly that order disappears, and the security rests on it.

In the actual scheme the arithmetic is modulo pp. There is no "left", no "right" and no proximity there: 17 B17\,B and 18 B18\,B become two pairs of numbers with no recognisable relationship.

8. The signing service's key pair

It starts with 32 random bytes, the seed. Everything else is derived from it:

h=SHA-512(seed),h=h0..31⏟→  a  ∥  h32..63⏟prefix.h = \mathrm{SHA\text{-}512}(\text{seed}), \qquad h = \underbrace{h_{0..31}}_{\to\;a}\;\|\;\underbrace{h_{32..63}}_{\text{prefix}}.

The first half becomes the secret scalar aa, though not unchanged. Three bits are set or cleared — the so-called clamping:

  • the lowest three bits are set to zero: this makes aa a multiple of 8. The reason is the curve's cofactor 8 — the full point group is eight times the size of the subgroup of order ℓ\ell. An aa divisible by 8 is guaranteed to land in the right subgroup and reveals nothing via small-order points.
  • the highest bit is cleared and the second-highest set: aa therefore always has the same bit length. A shorter aa would need fewer doublings — and once again the running time would give something away.

The public key is then simply

A=a⋅B,A = a\cdot B,

stored as 32 bytes: the yy coordinate, with the sign of xx in the top bit. The verifier recovers xx from the curve equation itself — the two solutions differ only in sign, and that single bit says which one is meant.

The second half of the hash, the prefix, is not needed for the key. It comes into play in the next section.

9. Why the randomness here is not random

Every signature of this construction needs a one-off value rr, often called a nonce. It must never repeat: anyone holding two signatures made with the same rr can work out the secret key with school algebra.

Real systems have failed on exactly this. The best-known case is the signature verification of a games console whose manufacturer used the same nonce every time in 2010 — the private key could be reconstructed publicly as a result.

Ed25519 solves it by using no randomness at all:

r=SHA-512(prefix  ∥  m) mod ℓ.r = \mathrm{SHA\text{-}512}(\text{prefix}\;\|\;m) \bmod \ell.

The nonce depends on the secret prefix and on the message. Two things follow:

  • Two different reviews yield different rr with overwhelming probability — the repetition case does not arise.
  • The same review always yields the same signature. A signing operation can therefore be reproduced, and a poor random generator on the server cannot break anything, because none is needed.

For a review platform with many signatures per day this is not an academic advantage. It is the difference between "a fault in the source of randomness would be fatal" and "there is no source of randomness that could fail".

10. Signing

Three lines, and that is all:

r=H(prefix  ∥  m) mod ℓ,R=r⋅B,r = H(\text{prefix}\;\|\;m) \bmod \ell, \qquad R = r\cdot B,
k=H(R  ∥  A  ∥  m) mod ℓ,k = H(R \;\|\; A \;\|\; m) \bmod \ell,
S=(r+k a) mod ℓ.S = (r + k\,a) \bmod \ell.

The signature is the pair

σ=(R, S),\sigma = (R,\,S),

32 bytes for the point RR, 32 bytes for the number SS — 64 bytes in total.

The second line is worth noting: kk takes in RR, the public key AA and the message. Hashing AA along is not decoration — it prevents attacks in which a signature is reinterpreted as belonging to a different key.

11. Verifying

The reader's browser knows: the review mm, the signature (R,S)(R,S) and the public key AA. It recomputes kk and checks a single equation:

S⋅B  =  R+k⋅A\boxed{S\cdot B \;=\; R + k\cdot A}

If it holds, the signature is valid. RFC 8032 additionally permits the cofactored form 8S⋅B=8R+8k⋅A8S\cdot B = 8R + 8k\cdot A, which is more lenient about a few edge cases.

No server is asked, no service has to be available. The public key is enough.

12. Why the equation works out

Substituting is enough:

S⋅B=(r+k a)⋅B=r⋅B+k (a⋅B)=R+k⋅A.S\cdot B = (r + k\,a)\cdot B = r\cdot B + k\,(a\cdot B) = R + k\cdot A.

The whole trick sits in the middle step: scalar multiplication is compatible with addition. Anyone who knows aa can compute an SS that satisfies the equation. Anyone who does not know aa would have to find a matching SS for a kk they did not choose — and that means solving the discrete logarithm.

13. A fully worked miniature example

With the real numbers there is nothing to check by hand — 253-bit values cannot be verified in your head. So here is the same scheme in a tiny group where every step can be followed with a pocket calculator.

Step 1: The group

We work with the residues modulo 2323 and take g=2g = 2. We have

211=2048=89⋅23+1≡1(mod23),2^{11} = 2048 = 89\cdot 23 + 1 \equiv 1 \pmod{23},

so gg generates a subgroup of order ℓ=11\ell = 11. The powers are:

nn1234567891011
gng^n248169181336121

gg takes the role of the base point BB, multiplication the role of point addition. Scalars are computed modulo 1111, values modulo 2323.

Step 2: The key pair

Let the secret be a=6a = 6. Then

A=ga=26=64≡18(mod23).A = g^a = 2^6 = 64 \equiv 18 \pmod{23}.

A=18A = 18 may be known by anyone.

Step 3: Nonce and commitment

Let prefix and review yield r=4r = 4. From that:

R=gr=24=16.R = g^r = 2^4 = 16.

Step 4: The challenge

Let the hash over RR, AA and the review produce

k=5.k = 5.

Step 5: The signature

S=(r+k a) mod 11=(4+5⋅6) mod 11=34 mod 11=1.S = (r + k\,a) \bmod 11 = (4 + 5\cdot 6) \bmod 11 = 34 \bmod 11 = 1.

The signature is the pair (R,S)=(16, 1)(R,S) = (16,\,1).

Step 6: The browser verifies

It computes both sides. Left:

gS=21=2.g^S = 2^1 = 2.

Right, using 185≡3(mod23)18^5 \equiv 3 \pmod{23}:

R⋅Ak=16⋅3=48≡2(mod23).R\cdot A^{k} = 16\cdot 3 = 48 \equiv 2 \pmod{23}.

Both sides give 22:

Signature valid\boxed{\text{Signature valid}}

Step 7: Someone changes the review text

The text goes into the hash, so the challenge changes — say to k′=7k' = 7. The signature stays at (16,1)(16,1), but the right-hand side does not. With 187≡6(mod23)18^7 \equiv 6 \pmod{23}:

R⋅Ak′=16⋅6=96≡4(mod23)  ≠  2=gSR\cdot A^{k'} = 16\cdot 6 = 96 \equiv 4 \pmod{23} \;\neq\; 2 = g^S
Signature invalid\boxed{\text{Signature invalid}}

We can delete a review. We cannot alter it without it showing.

An honest note about the example

The arithmetic here happened in the multiplicative group modulo 2323, not on a curve: gSg^S stands for S⋅BS\cdot B, the product R⋅AkR\cdot A^k for the point addition R+k⋅AR + k\cdot A. The structure is the same, and that is the point. What differs are the magnitudes: ℓ=11\ell = 11 versus ℓ≈2252\ell \approx 2^{252}, and there the key cannot be found by trying out eleven possibilities.

14. What happens if someone changes the review

Suppose someone with database access — including someone at our company — changes the review text or one of the hearts. Then the record changes and with it at least one of the two hash values h and rh in the payload. That changes mm, hence the challenge kk, hence the right-hand side of the verification equation. The old signature no longer fits.

The decisive sentence: we can delete a review, but we cannot alter it unnoticed. At McGesund the same check additionally runs nightly on the server across the whole stock — a review that fails it no longer counts towards the company's average.

15. Why an attacker fails

They know the public key AA, the base point BB, the curve and every signature issued so far. What they lack is aa.

The best known classical attack on the discrete logarithm problem in a group of order ℓ\ell needs about ℓ\sqrt{\ell} steps. With ℓ≈2252\ell \approx 2^{252} that is roughly

21262^{126}

operations. For comparison: even a machine managing a billion billion (101810^{18}) steps per second would need many times the age of the universe.

Forging without the key would mean finding a matching SS for a kk of one's own choosing — the same task in a different disguise.

16. Why Ed25519 and not ECDSA

Both rest on the same problem. The difference lies in everything around it:

ECDSA (NIST curves)Ed25519
Noncefresh randomness requireddeterministic from prefix and message
Formulasspecial cases, data-dependent branchescomplete, one path
Curve parametersorigin of the constants never fully explainedchosen from comprehensible criteria
Signature size64–72 B, variable encodingfixed 64 B
In the browseravailable for a long timenative since 2023/2024, otherwise a JS library

For us the nonce was the deciding argument. A review platform signs often and automatically; a scheme in which a single weak random value gives away the key is the wrong choice for that.

17. What Ed25519 does not achieve

Ed25519 rests on the discrete logarithm — and a sufficiently large quantum computer solves precisely that problem efficiently with Shor's algorithm. Whether and when such machines will exist is open. For a review that should still be verifiable in ten years, it is nevertheless a question to be answered today.

That is why a quantum-resistant stamp can be placed alongside the Ed25519 signature:

Neither replaces Ed25519, they sit next to it. If one of the schemes breaks, the other carries on.

18. The process in one picture

SIGNING SERVICE (MCGESUND)VISITOR'S BROWSERprivate scalar a + prefix (from the seed)payload m = {company, review, h, rh, iat}r = H(prefix ‖ m) mod ℓR = r · Bk = H(R ‖ A ‖ m) mod ℓS = (r + k · a) mod ℓsignature σ = (R, S) + kidreview + σ + public key Arecompute k from R, A and mS · B = R + k · A ?validinvalid
From the payload to the tick in the browser. Everything above the dividing line happens once on submission, everything below it happens again for every reader — on their device, with the public key alone.

19. What McGesund does with it in practice

The envelope. Every signed review carries an MCG1: envelope containing the format version, the payload and the Ed25519 signature. The kid in the payload says which key is meant; the server hands out the corresponding public key on request — it is public, there is nothing about it to protect.

Verification in the browser. Chrome and Firefox have supported Ed25519 natively via the WebCrypto interface since 2023/2024. Safari does not — there the call throws instead of verifying. Our verification code therefore falls back to a pure JavaScript implementation, loaded only where it is needed. The signature check thus runs in every browser, and it runs on the reader's device.

The time anchor. The fingerprint of the signing key is anchored in a Bitcoin block via OpenTimestamps. That makes it possible to show not only that the signature is genuine but also that the key already existed at a particular point in time — without anyone having to believe our timestamp.

The content binding. The payload carries rh, the hash over the entire submission record: text, hearts, geo status, occasion details and origin. The Ed25519 signature therefore binds not just the text but everything displayed next to the review.

20. One sentence to take away

Ed25519 turns a secret number into an equationanyone can recompute and nobody can invent.\boxed{ \begin{array}{c} \text{Ed25519 turns a secret number into an equation}\\ \text{anyone can recompute and nobody can invent.} \end{array}}

Whoever holds the secret scalar signs in microseconds. Whoever does not would have to solve a discrete logarithm in a group with around 22522^{252} elements.

For the reader of a review this simply means: they do not have to believe us. They can do the arithmetic.