Ed25519 forklaret matematisk

1. Hvad det handler om

En anmeldelse hos McGesund er ikke et tekstfelt i en database, som man bare må tro på. Den bliver digitalt signeret, når den sendes af sted, og enhver besøgende kan senere regne signaturen efter i sin egen browser.

Til denne underskrift bruger vi Ed25519. I modsætning til FALCON og ML-DSA, der kan lægges ved som ekstra stempler, er Ed25519 ikke valgfri: Hver signeret anmeldelse bærer den, uanset abonnement og indsendelsesvej.

Vigtigt at slå fast først:

Ed25519 er ikke kryptering. Anmeldelsesteksten skal jo kunne læses. Signaturen beviser ikke hemmeligholdelse, men oprindelse og uforanderlighed.

---

2. Hvad der præcist bliver underskrevet

Det er ikke den løbende tekst, der signeres, men et kompakt dataobjekt, som utvetydigt fastnagler teksten og alt det øvrige:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<virksomheds-id>",
  "c":   "<anmeldelses-id>",
  "h":   "<SHA-256 af anmeldelsesteksten>",
  "rh":  "<SHA-256 af hele det indsendte datasæt>",
  "rv":  1,
  "qh":  "<SHA-256 af QR-konvolutten, kun ved QR-anmeldelser>",
  "kid": "<nøgle-id>",
  "iat": 1757203200
}

Dette objekt bliver kodet til CBOR. Denne bytefølge — ikke den pæne visning ovenfor — er vores besked $m$. Signatur og besked rejser sammen i en konvolut:

$3$-tallet er formatversionen. Mere står der ikke i den — og navnlig ingen post-kvantesignatur: Findes den, ligger den ved siden af datasættet og ikke i konvolutten.

---

3. Hvad signaturen skal kunne

En læser, der lander på en virksomhedsprofil, står med to spørgsmål:

1. Stammer denne anmeldelse virkelig fra McGesund-systemet?
2. Er den blevet ændret bagefter?

Til det findes der et nøglepar:

• en privat nøgle — bliver i signaturtjenesten
• en offentlig nøgle — må alle have, adresseres via nøgle-id'et (kid) i payloaden

Der signeres med den private nøgle. Der verificeres med den offentlige — og det sker i læserens browser, ikke på vores server. Det er hele pointen: En kontrol, som vi selv udfører og hvis resultat vi meddeler, ville ikke være en kontrol, men en påstand.

---

4. Hvorfor en elliptisk kurve?

Enhver signatur kræver en beregning, der er let den ene vej og praktisk talt umulig den anden. Ved Ed25519 er det skalarmultiplikationen på en elliptisk kurve:

At beregne det offentlige punkt $A$ ud fra det hemmelige tal $a$ koster mikrosekunder. At slutte fra $A$ tilbage til $a$ er det diskrete logaritmeproblem — og der kendes ingen metode, der ved denne størrelse bliver færdig inden for menneskelige tidsrum.

Den praktiske gevinst i forhold til ældre metoder som RSA er størrelsen:

Ved sammenligneligt sikkerhedsniveau. 64 byte pr. anmeldelse er heller ikke ved millioner af anmeldelser en størrelse, man behøver tænke over.

---

5. Kurven edwards25519

Der regnes modulo et primtal:

Deraf navnet. Kurven er en snoet Edwards-kurve:

Et „punkt" er et talpar $(x,y)$ fra $\{0,\dots,p-1\}$, der opfylder denne ligning. Der er ingen kurve at se — tegningen i næste afsnit er en anskuelseshjælp over de reelle tal, ikke et billede af det faktiske regnerum.

To størrelser kommer til:

• et fast aftalt basispunkt $B$,
• ordenen $\ell$ for den undergruppe, $B$ frembringer:

$\ell$ er et primtal. Det betyder: Lægger man $B$ til sig selv igen og igen, gennemløber man præcis $\ell$ forskellige punkter og lander så igen ved begyndelsen. Alle beregninger med skalarer foregår derfor modulo $\ell$, alle beregninger med koordinater modulo $p$. At forveksle disse to tal er den klassiske begynderfejl.

---

6. At addere punkter

To punkter regnes efter en fast formel sammen til et tredje:

Det neutrale element er $(0,1)$ — punktet, hvor regningen begynder.

Denne formel har en egenskab, man ikke kan se på den, og som betyder mere for sikkerheden end nogen konstant: Den er fuldstændig. Den fungerer for alle input, uden særtilfælde for „begge punkter ens" eller „resultatet er det neutrale element". Ved de ældre Weierstrass-kurver findes disse særtilfælde, og hvert af dem er en forgrening i programmet — en forgrening, hvis køretid kan måles. Den, der måler, hvor lang tid en signatur tager, får ved sådanne metoder noget at vide om den hemmelige nøgle.

Fuldstændige formler betyder: altid den samme beregningsvej, altid den samme tid, intet at måle på.

---

7. Skalarmultiplikation — envejsgaden

$n\cdot B$ betyder: at lægge $B$ til sig selv præcis $n$ gange. Ved et $n$ på 253 bit ville det være meningsløst meget arbejde — derfor fordobles der:

og ud af disse mellemresultater sammensættes det ønskede $n$. Omkring 253 fordoblinger rækker til ethvert $n$. Det er vejen fremad.

Baglæns findes denne genvej ikke. At bestemme tallet $a$ ud fra punktet $A$ betyder at løse det diskrete logaritmeproblem.

I den rigtige metode regnes der modulo $p$. Dér findes hverken „venstre" eller „højre" og ingen nærhed: Af $17\,B$ og $18\,B$ bliver to talpar uden noget genkendeligt slægtskab.

---

8. Signaturtjenestens nøglepar

I begyndelsen står 32 tilfældige byte, seedet. Alt det øvrige udledes deraf:

Af den første halvdel opstår den hemmelige skalar $a$, dog ikke uændret. Tre bit bliver sat eller slettet — den såkaldte clamping:

• de nederste tre bit sættes til nul: $a$ bliver derved et multiplum af 8. Grunden er kurvens kofaktor 8 — den fulde punktgruppe er otte gange så stor som undergruppen af orden $\ell$. Et $a$, der er deleligt med 8, lander garanteret i den rigtige undergruppe og røber intet om punkter af lille orden.
• det øverste bit slettes, det næstøverste sættes: $a$ har dermed altid den samme bitlængde. Et kortere $a$ ville kræve færre fordoblinger — og igen ville køretiden røbe noget.

Den offentlige nøgle er så ganske enkelt

gemt som 32 byte: $y$-koordinaten, og i det højeste bit fortegnet for $x$. $x$ regner den, der verificerer, selv tilbage ud fra kurveligningen — de to løsninger adskiller sig kun i fortegnet, og hvilken der menes, siger netop dette ene bit.

Hashværdiens anden halvdel, præfikset, bruges ikke til nøglen. Den kommer i brug i næste afsnit.

---

9. Hvorfor tilfældigheden her ikke er tilfældig

Enhver signatur af denne type kræver en engangsværdi $r$, ofte kaldet nonce. Den må aldrig gentage sig: Den, der har to signaturer med det samme $r$, kan regne den hemmelige nøgle ud med almindelig skolealgebra.

Netop dét er virkelige systemer strandet på. Det mest kendte tilfælde er signaturkontrollen i en spillekonsol, hvis producent i 2010 altid brugte den samme nonce — den private nøgle kunne derved rekonstrueres offentligt.

Ed25519 løser det ved slet ikke at bruge tilfældighed:

Noncen hænger på det hemmelige præfiks og på beskeden. Deraf følger to ting:

• To forskellige anmeldelser giver med overvældende sandsynlighed forskellige $r$ — gentagelsestilfældet indtræffer ikke.
• Den samme anmeldelse giver altid den samme signatur. En signeringshandling kan dermed efterprøves, og en dårlig tilfældighedsgenerator på serveren kan ikke ødelægge noget, fordi der ikke bruges nogen.

For en anmeldelsesportal med mange signaturer om dagen er det ingen akademisk fordel. Det er forskellen mellem „en fejl i tilfældighedskilden ville være fatal" og „der findes ingen tilfældighedskilde, der kunne svigte".

---

10. At signere

Tre linjer, mere er det ikke:

Signaturen er parret

32 byte til punktet $R$, 32 byte til tallet $S$ — tilsammen 64 byte.

Bemærkelsesværdig er den anden linje: I $k$ indgår $R$, den offentlige nøgle $A$ og beskeden. At $A$ hashes med, er ikke pynt — det forhindrer angreb, hvor en signatur omtolkes til at høre til en anden nøgle.

---

11. At verificere

Læserens browser kender: anmeldelsen $m$, signaturen $(R,S)$ og den offentlige nøgle $A$. Den beregner $k$ på ny og efterprøver en eneste ligning:

Passer den, er signaturen gyldig. RFC 8032 tillader desuden den med kofaktoren multiplicerede udgave $8S\cdot B = 8R + 8k\cdot A$, som behandler enkelte grænsetilfælde mere lempeligt.

Ingen server bliver spurgt, ingen tjeneste skal være tilgængelig. Den offentlige nøgle er nok.

---

12. Hvorfor ligningen går op

Indsættelse er nok:

Hele fidusen ligger i den midterste omskrivning: Skalarmultiplikationen er forenelig med additionen. Den, der kender $a$, kan beregne et $S$, der opfylder ligningen. Den, der ikke kender $a$, skulle til et selvvalgt $k$ finde et passende $S$ — og det betyder at løse den diskrete logaritme.

---

13. Et fuldt gennemregnet minieksempel

Med de rigtige tal er der intet at regne efter — 253-bit-værdier kan ikke efterprøves i hovedet. Derfor den samme metode i en ganske lille gruppe, hvor hvert skridt kan følges med lommeregner.

Trin 1: Gruppen

Vi regner med resterne modulo $23$ og tager $g = 2$. Der gælder

$g$ frembringer altså en undergruppe af orden $\ell = 11$. Potenserne er:

$g$ overtager basispunktet $B$'s rolle, multiplikationen punktadditionens. Skalarer regnes modulo $11$, værdier modulo $23$.

Trin 2: Nøgleparret

Lad det hemmelige være $a = 6$. Så er

$A = 18$ må alle godt vide.

Trin 3: Nonce og commitment

Lad præfiks og anmeldelse give $r = 4$. Deraf:

Trin 4: Challenge

Lad hashen over $R$, $A$ og anmeldelsen give

Trin 5: Signaturen

Signaturen er parret $(R,S) = (16,\,1)$.

Trin 6: Browseren verificerer

Den beregner begge sider. Venstre:

Højre, med $18^5 \equiv 3 \pmod{23}$:

Begge sider giver $2$:

Trin 7: Nogen ændrer anmeldelsesteksten

Teksten indgår i hashen, altså ændrer challengen sig — lad os sige til $k' = 7$. Signaturen forbliver uændret $(16,1)$, men det gør højresiden ikke. Med $18^7 \equiv 6 \pmod{23}$:

Vi kan slette en anmeldelse. Ændre den kan vi ikke, uden at det bliver opdaget.

Ærlighedsbemærkning til eksemplet

Der blev her regnet i den multiplikative gruppe modulo $23$, ikke på en kurve: $g^S$ står for $S\cdot B$, produktet $R\cdot A^k$ for punktadditionen $R + k\cdot A$. Strukturen er den samme, og det er netop pointen. Forskellige er størrelsesordenerne: $\ell = 11$ over for $\ell \approx 2^{252}$, og dér kan nøglen ikke findes ved at prøve de elleve muligheder af.

---

14. Hvad der sker, hvis nogen ændrer anmeldelsen

Antag, at nogen med databaseadgang — også nogen hos os — ændrer anmeldelsesteksten eller et af hjerterne. Så ændrer datasættet sig og dermed mindst en af de to hashværdier h og rh i payloaden. Dermed ændrer $m$ sig, dermed challengen $k$, dermed højresiden af verifikationsligningen. Den gamle signatur passer ikke længere.

Den afgørende sætning hertil: Vi kan slette en anmeldelse, men vi kan ikke ændre den ubemærket. Hos McGesund kører den samme kontrol desuden hver nat serverside hen over hele bestanden — en anmeldelse, der ikke består den, tæller ikke længere med i virksomhedens gennemsnit.

---

15. Hvorfor en angriber ikke kommer igennem

Han kender den offentlige nøgle $A$, basispunktet $B$, kurven og hver eneste hidtil udstedt signatur. Det, han mangler, er $a$.

Det bedste kendte klassiske angreb på det diskrete logaritmeproblem i en gruppe af orden $\ell$ kræver omkring $\sqrt{\ell}$ skridt. Ved $\ell \approx 2^{252}$ er det cirka

operationer. Til sammenligning: Selv en maskine, der klarer en milliard milliarder ($10^{18}$) skridt i sekundet, ville skulle bruge et mangefold af universets alder.

At forfalske uden nøglen ville betyde at finde et passende $S$ til et selvvalgt $k$ — den samme opgave i en anden forklædning.

---

16. Hvorfor Ed25519 og ikke ECDSA

Begge bygger på det samme problem. Forskellen ligger i alt det, der sker rundt om:

For os var noncen det afgørende argument. En anmeldelsesportal signerer ofte og automatiseret; en metode, hvor en enkelt svag tilfældig værdi røber nøglen, er det forkerte valg hertil.

---

17. Hvad Ed25519 ikke kan

Ed25519 bygger på den diskrete logaritme — og netop dette problem løser en tilstrækkelig stor kvantecomputer effektivt med Shors algoritme. Om og hvornår sådanne maskiner findes, er åbent. For en anmeldelse, der skal kunne verificeres om ti år, er det alligevel et spørgsmål, man må besvare i dag.

Derfor kan der ved siden af Ed25519-signaturen komme et kvanteresistent stempel:

• FALCON (FN-DSA) — kompakte signaturer fra NTRU-gitre
• ML-DSA-87 (FIPS 204) — den færdiggjorte NIST-standard

Ingen af dem erstatter Ed25519, de lægger sig ved siden af. Bryder den ene metode sammen, bærer den anden videre.

---

18. Forløbet i billeder

---

19. Hvad McGesund konkret bruger det til

Konvolutten. Hver signeret anmeldelse bærer en MCG1:-konvolut med formatversion, payload og Ed25519-signatur. kid i payloaden siger, hvilken nøgle der menes; den tilhørende offentlige nøgle udleverer serveren på forespørgsel — den er offentlig, der er intet at beskytte ved den.

Verifikationen i browseren. Chrome og Firefox kan Ed25519 nativt via WebCrypto-grænsefladen siden 2023/2024. Safari kan ikke — dér kaster kaldet en fejl i stedet for at verificere. Derfor falder vores verifikationskode tilbage på en ren JavaScript-implementering, som kun hentes ind dér, hvor den er nødvendig. Signaturkontrollen kører dermed igennem i enhver browser, og det på læserens eget udstyr.

Tidsankeret. Signaturnøglens fingeraftryk forankres via OpenTimestamps i en Bitcoin-blok. Dermed kan man ikke bare påvise, at signaturen er ægte, men også at nøglen allerede eksisterede på et bestemt tidspunkt — uden at nogen behøver tro på vores tidsstempel.

Indholdsbindingen. Payloaden bærer rh, hashen over hele det indsendte datasæt: tekst, hjerter, geostatus, anledningsoplysninger og oprindelse. Ed25519-signaturen binder dermed ikke kun teksten, men alt det, der vises ved siden af anmeldelsen.

---

20. En sætning at tage med

Den, der besidder den hemmelige skalar, underskriver på mikrosekunder. Den, der ikke besidder den, skulle løse en diskret logaritme i en gruppe med omkring $2^{252}$ elementer.

For den, der læser en anmeldelse, betyder det ganske enkelt: Han behøver ikke tro på os. Han kan regne efter.