Ed25519 matematički objašnjen

1. O čemu je riječ

Recenzija na McGesundu nije tekstualno polje u bazi podataka kojemu se mora vjerovati. Pri slanju se digitalno potpisuje, a svaki posjetitelj taj potpis može kasnije preračunati u vlastitom pregledniku.

Za taj potpis koristimo Ed25519. Za razliku od FALCON-a i ML-DSA, koji se dodatno mogu priložiti kao pečat, Ed25519 nije opcija: svaka potpisana recenzija nosi ga, neovisno o tarifi i načinu predaje.

Važno unaprijed:

Ed25519 nije šifriranje. Tekst recenzije se ionako treba čitati. Potpis ne dokazuje tajnost, nego podrijetlo i cjelovitost.

---

2. Što se točno potpisuje

Ne potpisuje se tekući tekst, nego kompaktan podatkovni objekt koji tekst i sve ostalo jednoznačno prikiva:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID tvrtke>",
  "c":   "<ID recenzije>",
  "h":   "<SHA-256 teksta recenzije>",
  "rh":  "<SHA-256 cijelog zapisa o predaji>",
  "rv":  1,
  "qh":  "<SHA-256 QR omotnice, samo kod QR recenzija>",
  "kid": "<ID ključa>",
  "iat": 1757203200
}

Taj se objekt kodira u CBOR. Taj niz bajtova — a ne njegov lijepi prikaz gore — jest naša poruka $m$. Potpis i poruka zajedno putuju u omotnici:

Broj $3$ je verzija formata. Više u njoj nema — posebno nema post-kvantnog potpisa: on, ako postoji, leži uz zapis, a ne u omotnici.

---

3. Što potpis treba postići

Čitatelj koji dođe na profil poduzeća pred dva je pitanja:

1. Potječe li ova recenzija doista iz McGesund sustava?
2. Je li naknadno izmijenjena?

Za to postoji par ključeva:

• privatni ključ — ostaje u servisu za potpisivanje
• javni ključ — smije ga imati svatko, adresira se preko ID-a ključa (kid) u payloadu

Potpisuje se privatnim ključem. Provjerava se javnim — i to u pregledniku čitatelja, a ne na našem poslužitelju. U tome je bit: provjera koju sami provedemo i čiji rezultat objavimo ne bi bila provjera, nego tvrdnja.

---

4. Zašto eliptična krivulja?

Svaki potpis treba račun koji je u jednom smjeru lagan, a u drugom praktički nemoguć. Kod Ed25519 to je skalarno množenje na eliptičnoj krivulji:

Izračunati javnu točku $A$ iz tajnog broja $a$ traje mikrosekunde. Zaključiti iz $A$ natrag na $a$ znači riješiti problem diskretnog logaritma — za njega nije poznat postupak koji bi pri ovoj veličini završio u ljudskim vremenskim okvirima.

Praktična prednost pred starijim postupcima poput RSA jest veličina:

Uz usporedivu razinu sigurnosti. 64 bajta po recenziji ni pri milijunima recenzija nisu veličina o kojoj treba razmišljati.

---

5. Krivulja edwards25519

Računa se modulo prostim brojem:

Otuda i ime. Krivulja je uvrnuta Edwardsova krivulja:

„Točka" je par brojeva $(x,y)$ iz $\{0,\dots,p-1\}$ koji zadovoljava tu jednadžbu. Nema tu krivulje za vidjeti — crtež u sljedećem odjeljku pomoćna je slika nad realnim brojevima, a ne prikaz stvarnog računskog prostora.

Dolaze još dvije veličine:

• čvrsto dogovorena bazna točka $B$,
• red $\ell$ podgrupe koju $B$ generira:

$\ell$ je prost. To znači: zbraja li se $B$ uvijek iznova sa samim sobom, prolazi se točno kroz $\ell$ različitih točaka i zatim se ponovno završava na početku. Svi računi sa skalarima zato teku modulo $\ell$, a svi računi s koordinatama modulo $p$. Zamijeniti ta dva broja klasična je početnička pogreška.

---

6. Zbrajanje točaka

Dvije se točke po čvrstoj formuli spajaju u treću:

Neutralni element je $(0,1)$ — točka u kojoj računanje počinje.

Ta formula ima svojstvo koje se na njoj ne vidi, a za sigurnost je važnije od bilo koje konstante: ona je potpuna. Radi za sve ulaze, bez posebnih slučajeva za „obje su točke jednake" ili „rezultat je neutralni element". Kod starijih Weierstrassovih krivulja ti posebni slučajevi postoje i svaki je od njih grana u programu — grana čije se trajanje da izmjeriti. Tko mjeri koliko potpisivanje traje, kod takvih postupaka doznaje nešto o tajnom ključu.

Potpune formule znače: uvijek isti računski put, uvijek isto vrijeme, ništa za izmjeriti.

---

7. Skalarno množenje — jednosmjerna ulica

$n\cdot B$ znači: zbrojiti $B$ točno $n$ puta sa samim sobom. Pri $n$ od 253 bita to bi bilo besmisleno mnogo posla — zato se udvostručuje:

a iz tih se međurezultata sastavi željeni $n$. Oko 253 udvostručenja dovoljno je za svaki $n$. To je put naprijed.

Unatrag te prečice nema. Odrediti broj $a$ iz točke $A$ znači riješiti problem diskretnog logaritma.

U stvarnom se postupku računa modulo $p$. Ondje nema „lijevo", nema „desno" ni blizine: iz $17\,B$ i $18\,B$ nastaju dva para brojeva bez ikakve prepoznatljive srodnosti.

---

8. Par ključeva servisa za potpisivanje

Na početku stoje 32 slučajna bajta, Seed. Sve ostalo iz njega se izvodi:

Iz prve polovice nastaje tajni skalar $a$, ali ne nepromijenjen. Tri se bita postavljaju odnosno brišu — takozvani clamping:

• donja se tri bita postavljaju na nulu: $a$ time postaje višekratnik broja 8. Razlog je kofaktor 8 krivulje — puna grupa točaka osam je puta veća od podgrupe reda $\ell$. Skalar $a$ djeljiv s 8 zajamčeno završava u ispravnoj podgrupi i ne odaje ništa preko točaka malog reda.
• najviši se bit briše, a drugi po redu postavlja: $a$ time uvijek ima istu duljinu u bitovima. Kraći $a$ trebao bi manje udvostručenja — i opet bi se iz trajanja nešto dalo iščitati.

Javni je ključ tada naprosto

pohranjen kao 32 bajta: $y$-koordinata i, u najvišem bitu, predznak od $x$. Vrijednost $x$ provjeritelj sam izračuna natrag iz jednadžbe krivulje — dva se rješenja razlikuju samo u predznaku, a koje se misli, kaže taj jedan bit.

Druga polovica hash-vrijednosti, prefiks, ne treba za ključ. Ona dolazi na red u sljedećem odjeljku.

---

9. Zašto slučajnost ovdje nije slučajna

Svaki potpis ove izvedbe treba jednokratnu vrijednost $r$, često zvanu nonce. Ona se nikada ne smije ponoviti: tko ima dva potpisa s istim $r$, tajni ključ može izračunati školskom algebrom.

Upravo su na tome stvarni sustavi propali. Najpoznatiji je slučaj provjera potpisa jedne igraće konzole, čiji je proizvođač 2010. uvijek koristio isti nonce — privatni je ključ time bio javno rekonstruirljiv.

Ed25519 to rješava tako da uopće ne koristi slučajnost:

Nonce ovisi o tajnom prefiksu i o poruci. Iz toga slijedi dvoje:

• Dvije različite recenzije daju s golemom vjerojatnošću različite $r$ — do ponavljanja ne dolazi.
• Ista recenzija daje uvijek isti potpis. Postupak potpisivanja time je provjerljiv, a loš generator slučajnih brojeva na poslužitelju ne može ništa pokvariti jer se nijedan ne treba.

Za portal s recenzijama i mnogo potpisa dnevno to nije akademska prednost. To je razlika između „pogreška u izvoru slučajnosti bila bi kobna" i „nema izvora slučajnosti koji bi mogao zakazati".

---

10. Potpisivanje

Tri retka, više od toga nema:

Potpis je par

32 bajta za točku $R$, 32 bajta za broj $S$ — zajedno 64 bajta.

Vrijedi zamijetiti drugi redak: u $k$ ulaze $R$, javni ključ $A$ i poruka. To što se $A$ uhashira nije ukras — sprječava napade u kojima se potpis pripiše drugom ključu.

---

11. Provjera

Preglednik čitatelja zna: recenziju $m$, potpis $(R,S)$ i javni ključ $A$. On iznova izračuna $k$ i provjeri jednu jedinu jednadžbu:

Vrijedi li ona, potpis je valjan. RFC 8032 dopušta dodatno i inačicu pomnoženu kofaktorom, $8S\cdot B = 8R + 8k\cdot A$, koja neke rubne slučajeve tretira velikodušnije.

Nijedan se poslužitelj ne pita, nijedna usluga ne mora biti dostupna. Javni ključ je dovoljan.

---

12. Zašto jednadžba vrijedi

Dovoljno je uvrstiti:

Cijeli je trik u srednjoj preinaci: skalarno se množenje slaže sa zbrajanjem. Tko zna $a$, može izračunati $S$ koji jednadžbu zadovoljava. Tko $a$ ne zna, morao bi uz samostalno odabrani $k$ pronaći odgovarajući $S$ — a to znači riješiti diskretni logaritam.

---

13. Do kraja izračunat mini-primjer

S pravim brojevima nema se što preračunati — vrijednosti od 253 bita ne daju se provjeriti napamet. Zato isti postupak u sićušnoj grupi, u kojoj je svaki korak provjerljiv džepnim računalom.

Korak 1: Grupa

Računamo s ostacima modulo $23$ i uzimamo $g = 2$. Vrijedi

$g$ dakle generira podgrupu reda $\ell = 11$. Potencije su:

$g$ preuzima ulogu bazne točke $B$, a množenje ulogu zbrajanja točaka. Skalari se računaju modulo $11$, vrijednosti modulo $23$.

Korak 2: Par ključeva

Neka je tajno $a = 6$. Tada je

$A = 18$ smije znati svatko.

Korak 3: Nonce i commitment

Iz prefiksa i recenzije neka proizađe $r = 4$. Odatle:

Korak 4: Izazov

Neka hash preko $R$, $A$ i recenzije dade

Korak 5: Potpis

Potpis je par $(R,S) = (16,\,1)$.

Korak 6: Preglednik provjerava

On izračuna obje strane. Lijevo:

Desno, uz $18^5 \equiv 3 \pmod{23}$:

Obje strane daju $2$:

Korak 7: Netko mijenja tekst recenzije

Tekst ulazi u hash, dakle mijenja se izazov — recimo na $k' = 7$. Potpis ostaje nepromijenjen na $(16,1)$, ali desna strana ne. Uz $18^7 \equiv 6 \pmod{23}$:

Recenziju možemo obrisati. Izmijeniti je ne možemo a da se to ne primijeti.

Iskrena napomena uz primjer

Ovdje se računalo u multiplikativnoj grupi modulo $23$, a ne na krivulji: $g^S$ stoji za $S\cdot B$, a umnožak $R\cdot A^k$ za zbrajanje točaka $R + k\cdot A$. Struktura je ista, i upravo je o tome riječ. Različiti su redovi veličine: $\ell = 11$ naspram $\ell \approx 2^{252}$, a ondje se ključ ne nalazi isprobavanjem jedanaest mogućnosti.

---

14. Što se događa ako netko promijeni recenziju

Pretpostavimo da netko s pristupom bazi podataka — pa i netko kod nas — promijeni tekst recenzije ili jedno od srca. Tada se mijenja zapis, a time barem jedna od dviju hash-vrijednosti h i rh u payloadu. Time se mijenja $m$, time izazov $k$, time desna strana jednadžbe provjere. Stari potpis više ne odgovara.

Odlučujuća rečenica uz to: recenziju možemo obrisati, ali je ne možemo neopaženo izmijeniti. Na McGesundu ista provjera dodatno noću teče na poslužitelju preko cijelog fonda — recenzija koja je ne prođe više ne ulazi u prosjek poduzeća.

---

15. Zašto napadač ne uspijeva

On zna javni ključ $A$, baznu točku $B$, krivulju i svaki dosad izdani potpis. Nedostaje mu $a$.

Najbolji poznati klasični napad na problem diskretnog logaritma u grupi reda $\ell$ treba oko $\sqrt{\ell}$ koraka. Pri $\ell \approx 2^{252}$ to je otprilike

operacija. Za usporedbu: čak bi i stroj koji izvede milijardu milijardi ($10^{18}$) koraka u sekundi za to trebao višekratnik starosti svemira.

Krivotvorenje bez ključa značilo bi uz samostalno odabrani $k$ pronaći odgovarajući $S$ — isti zadatak u drugom ruhu.

---

16. Zašto Ed25519, a ne ECDSA

Oba počivaju na istom problemu. Razlika je u svemu što se događa oko njega:

Za nas je nonce bio presudan argument. Portal s recenzijama potpisuje često i automatizirano; postupak kod kojega jedna jedina slaba slučajna vrijednost odaje ključ za to je pogrešan izbor.

---

17. Što Ed25519 ne postiže

Ed25519 počiva na diskretnom logaritmu — a upravo taj problem dovoljno veliko kvantno računalo rješava učinkovito Shorovim algoritmom. Hoće li i kada takvi strojevi postojati, otvoreno je pitanje. Za recenziju koja bi i za deset godina trebala biti provjerljiva to je unatoč tome pitanje na koje se mora odgovoriti danas.

Zato uz Ed25519 potpis može stati kvantno otporan pečat:

• FALCON (FN-DSA) — kompaktni potpisi iz NTRU rešetki
• ML-DSA-87 (FIPS 204) — dovršeni NIST standard

Nijedan ne zamjenjuje Ed25519, nego staje uz njega. Pukne li jedan postupak, drugi nosi dalje.

---

18. Tijek postupka na slici

---

19. Što McGesund konkretno radi s time

Envelope. Svaka potpisana recenzija nosi MCG1: omotnicu s verzijom formata, payloadom i Ed25519 potpisom. kid u payloadu kaže na koji se ključ misli; pripadni javni ključ poslužitelj izdaje na upit — on je javan, na njemu nema što štititi.

Provjera u pregledniku. Chrome i Firefox podržavaju Ed25519 od 2023./2024. nativno preko WebCrypto sučelja. Safari ne — ondje poziv baca pogrešku umjesto da provjeri. Zato se naš kôd za provjeru vraća na čistu JavaScript implementaciju, koja se dohvaća samo ondje gdje je potrebna. Provjera potpisa time prolazi u svakom pregledniku, i to na uređaju čitatelja.

Vremensko sidro. Otisak ključa za potpisivanje sidri se preko OpenTimestampsa u jednom Bitcoin bloku. Time se ne dokazuje samo da je potpis pravi, nego i da je ključ u određenom trenutku već postojao — a da pritom nitko ne mora vjerovati našem vremenskom žigu.

Vezanje sadržaja. Payload nosi rh, hash preko cijelog zapisa o predaji: teksta, srca, geo-statusa, podataka o povodu i podrijetla. Ed25519 potpis time veže ne samo tekst, nego sve što se uz recenziju prikazuje.

---

20. Jedna rečenica za kraj

Tko posjeduje tajni skalar, potpisuje u mikrosekundama. Tko ga ne posjeduje, morao bi riješiti diskretni logaritam u grupi s otprilike $2^{252}$ elemenata.

Za čitatelja recenzije to naprosto znači: ne mora nam vjerovati. Može preračunati.