Podpisni postopek

Ed25519 matematično pojasnjen

Podpis, ki spremlja vsako oceno na McGesund — od krivulje prek ključa do enačbe, ki jo preračuna brskalnik bralca.

Stanje: 2026-09-07

1. Za kaj gre

Ocena na McGesund ni besedilno polje v podatkovni bazi, ki mu je treba verjeti. Ob oddaji je digitalno podpisana in vsak obiskovalec lahko ta podpis pozneje preračuna v svojem brskalniku.

Za ta podpis uporabljamo Ed25519. Za razliko od FALCON in ML-DSA, ki ju je mogoče dodatno priložiti kot žig, Ed25519 ni izbirna možnost: vsaka podpisana ocena ga nosi, ne glede na paket in način oddaje.

Pomembno takoj na začetku:

Ed25519 ni šifriranje. Besedilo ocene naj bo vendar prebrano. Podpis ne dokazuje tajnosti, temveč izvor in nespremenjenost.

2. Kaj natančno se podpiše

Ne podpiše se tekoče besedilo, temveč kompakten podatkovni objekt, ki besedilo in vse ostalo enolično pribije:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID podjetja>",
  "c":   "<ID ocene>",
  "h":   "<SHA-256 besedila ocene>",
  "rh":  "<SHA-256 celotnega zapisa oddaje>",
  "rv":  1,
  "qh":  "<SHA-256 ovojnice QR, le pri ocenah prek QR>",
  "kid": "<ID ključa>",
  "iat": 1757203200
}

Ta objekt se kodira v CBOR. To zaporedje bajtov — ne njegov lični prikaz zgoraj — je naše sporočilo mm. Podpis in sporočilo skupaj potujeta v ovojnici:

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

Število 33 je različica formata. Več v njej ni — zlasti ne postkvantnega podpisa: ta leži, če obstaja, ob zapisu in ne v ovojnici.

3. Kaj naj podpis doseže

Bralec, ki pride na profil podjetja, stoji pred dvema vprašanjema:

  1. Ali ta ocena res izvira iz sistema McGesund?
  2. Ali je bila naknadno spremenjena?

Za to obstaja par ključev:

  • zasebni ključ — ostane v podpisni storitvi
  • javni ključ — ima ga lahko vsak, naslovi se prek ID ključa (kid) v payloadu

Podpisuje se z zasebnim ključem. Preverja se z javnim — in sicer v brskalniku bralca, ne na našem strežniku. To je bistvo: preverjanje, ki bi ga izvedli sami in katerega rezultat bi sporočili, ne bi bilo preverjanje, temveč trditev.

4. Zakaj eliptična krivulja?

Vsak podpis potrebuje računsko operacijo, ki je v eno smer lahka in v drugo praktično nemogoča. Pri Ed25519 je to skalarno množenje na eliptični krivulji:

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

Izračun javne točke AA iz skrivnega števila aa traja mikrosekunde. Sklepanje iz AA nazaj na aa je problem diskretnega logaritma — zanj ni znanega postopka, ki bi se pri tej velikosti končal v človeških časovnih okvirih.

Praktična prednost pred starejšimi postopki, kot je RSA, je velikost:

javni ključpodpis
RSA-3072384 B384 B
Ed2551932 B64 B

Pri primerljivi ravni varnosti. 64 bajtov na oceno tudi pri milijonih ocen ni velikost, o kateri bi bilo treba razmišljati.

5. Krivulja edwards25519

Računa se po modulu praštevila:

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

Od tod ime. Krivulja je zavita Edwardsova krivulja:

−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.

„Točka" je par števil (x,y)(x,y) iz {0,…,p−1}\{0,\dots,p-1\}, ki izpolnjuje to enačbo. Nobene krivulje ni videti — risba v naslednjem razdelku je nazorni pripomoček nad realnimi števili, ne slika dejanskega računskega prostora.

Dodati je treba še dve količini:

  • trdno dogovorjeno bazno točko BB,
  • red ℓ\ell podgrupe, ki jo generira BB:
ℓ=2252+27742317777372353535851937790883648493.\ell = 2^{252} + 27742317777372353535851937790883648493.

ℓ\ell je praštevilo. To pomeni: če BB vedno znova prištevamo samemu sebi, preidemo natanko ℓ\ell različnih točk in nato spet pristanemo na začetku. Vsi izračuni s skalarji zato tečejo po modulu ℓ\ell, vsi izračuni s koordinatami po modulu pp. Zamenjava teh dveh števil je klasična napaka začetnikov.

6. Seštevanje točk

Dve točki se po ustaljeni formuli združita v tretjo:

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}.

Nevtralni element je (0,1)(0,1) — točka, v kateri se računanje začne.

Ta formula ima lastnost, ki ji ni videti in ki je za varnost pomembnejša od vsake konstante: je popolna. Deluje za vse vhode, brez posebnih primerov za „obe točki sta enaki" ali „rezultat je nevtralni element". Pri starejših Weierstrassovih krivuljah ti posebni primeri obstajajo in vsak od njih je veja v programu — veja, katere čas izvajanja je merljiv. Kdor meri, koliko traja podpis, pri takih postopkih izve nekaj o skrivnem ključu.

Popolne formule pomenijo: vedno ista računska pot, vedno isti čas, nič za merjenje.

7. Skalarno množenje — enosmerna ulica

n⋅Bn\cdot B pomeni: BB natanko nn-krat prišteti samemu sebi. Pri nn z 253 biti bi bilo to nesmiselno veliko dela — zato se podvaja:

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

in iz teh vmesnih rezultatov se sestavi želeni nn. Približno 253 podvojitev zadošča za vsak nn. To je pot naprej.

Nazaj te bližnjice ni. Določiti število aa iz točke AA pomeni rešiti problem diskretnega logaritma.

(0,1) — nevtralni elementB2B3B4B5B6B
Edwardsova krivulja s prvimi večkratniki bazne točke, izračunanimi z resničnim zakonom seštevanja. Nad realnimi števili se še vidno urejeno premikajo po krivulji — pot bi bilo mogoče izslediti nazaj. Po modulu p izgine natanko ta urejenost, in na tem temelji varnost.

V resničnem postopku se računa po modulu pp. Tam ni ne „levo" ne „desno" in ne bližine: iz 17 B17\,B in 18 B18\,B nastaneta dva para števil brez vsakršne prepoznavne sorodnosti.

8. Par ključev podpisne storitve

Na začetku je 32 naključnih bajtov, seme. Vse nadaljnje se izpelje iz njega:

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

Iz prve polovice nastane skrivni skalar aa, vendar ne nespremenjen. Trije biti se postavijo oziroma zbrišejo — tako imenovani clamping:

  • spodnji trije biti se postavijo na nič: aa s tem postane večkratnik števila 8. Razlog je kofaktor 8 krivulje — polna skupina točk je osemkrat večja od podgrupe reda ℓ\ell. Z 8 deljiv aa zanesljivo pristane v pravi podgrupi in o točkah majhnega reda ne izda ničesar.
  • najvišji bit se zbriše, drugi najvišji se postavi: aa ima s tem vedno enako bitno dolžino. Krajši aa bi potreboval manj podvojitev — in spet bi bilo mogoče nekaj razbrati iz časa izvajanja.

Javni ključ je nato preprosto

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

shranjen kot 32 bajtov: koordinata yy in v najvišjem bitu predznak xx. Vrednost xx preveritelj sam izračuna nazaj iz enačbe krivulje — obe rešitvi se razlikujeta le v predznaku, in kateri je mišljena, pove ta en bit.

Druga polovica zgoščene vrednosti, predpona, za ključ ni potrebna. Uporabi se v naslednjem razdelku.

9. Zakaj naključje tu ni naključje

Vsak podpis te vrste potrebuje enkratno vrednost rr, pogosto imenovano nonce. Nikoli se ne sme ponoviti: kdor ima dva podpisa z istim rr, lahko skrivni ključ izračuna s šolsko algebro.

Prav na tem so resnični sistemi propadli. Najbolj znan primer je preverjanje podpisov na igralni konzoli, katere proizvajalec je leta 2010 vedno uporabljal isti nonce — zasebni ključ je bil s tem javno rekonstruktiven.

Ed25519 to reši tako, da sploh ne uporablja naključja:

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

Nonce je odvisen od skrivne predpone in od sporočila. Iz tega sledi dvoje:

  • Dve različni oceni dasta s prevladujočo verjetnostjo različna rr — primer ponovitve ne nastopi.
  • Ista ocena vedno da isti podpis. Postopek podpisovanja je s tem izsledljiv, slab generator naključnih števil na strežniku pa ne more ničesar pokvariti, ker ga ni treba uporabiti.

Za ocenjevalni portal z veliko podpisi na dan to ni akademska prednost. To je razlika med „napaka v viru naključja bi bila usodna" in „vira naključja, ki bi lahko odpovedal, sploh ni".

10. Podpisovanje

Tri vrstice, več ni:

r=H(predpona  ∥  m) mod ℓ,R=r⋅B,r = H(\text{predpona}\;\|\;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.

Podpis je par

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

32 bajtov za točko RR, 32 bajtov za število SS — skupaj 64 bajtov.

Vredna pozornosti je druga vrstica: v kk vstopajo RR, javni ključ AA in sporočilo. Da se AA sozgošča, ni okrasek — preprečuje napade, pri katerih se podpis prevesi na drug ključ.

11. Preverjanje

Brskalnik bralca pozna: oceno mm, podpis (R,S)(R,S) in javni ključ AA. Na novo izračuna kk in preveri eno samo enačbo:

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

Če drži, je podpis veljaven. RFC 8032 dodatno dovoljuje s kofaktorjem pomnoženo različico 8S⋅B=8R+8k⋅A8S\cdot B = 8R + 8k\cdot A, ki nekatere robne primere obravnava velikodušneje.

Nobenega strežnika ni treba vprašati, nobena storitev ne rabi biti dosegljiva. Javni ključ zadošča.

12. Zakaj enačba izide

Vstavljanje zadošča:

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.

Ves trik tiči v srednji preoblikovi: skalarno množenje se ujema s seštevanjem. Kdor pozna aa, lahko izračuna SS, ki enačbo izpolnjuje. Kdor aa ne pozna, bi moral k sam izbranemu kk najti ustrezen SS — in to pomeni rešiti diskretni logaritem.

13. V celoti izračunan mini primer

Z resničnimi števili ni ničesar za preverjanje — 253-bitnih vrednosti ni mogoče preveriti na pamet. Zato isti postopek v drobceni skupini, v kateri je vsak korak izsledljiv z žepnim računalom.

Korak 1: Skupina

Računamo z ostanki po modulu 2323 in vzamemo g=2g = 2. Velja

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

gg torej generira podgrupo reda ℓ=11\ell = 11. Potence so:

nn1234567891011
gng^n248169181336121

gg prevzame vlogo bazne točke BB, množenje pa vlogo seštevanja točk. Skalarji se računajo po modulu 1111, vrednosti po modulu 2323.

Korak 2: Par ključev

Naj bo skrivni a=6a = 6. Potem je

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

A=18A = 18 sme vedeti vsak.

Korak 3: Nonce in commitment

Iz predpone in ocene naj sledi r=4r = 4. Iz tega:

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

Korak 4: Izziv

Naj zgoščena vrednost prek RR, AA in ocene da

k=5.k = 5.

Korak 5: Podpis

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.

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

Korak 6: Brskalnik preverja

Izračuna obe strani. Levo:

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

Desno, z 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}.

Obe strani dasta 22:

Podpis veljaven\boxed{\text{Podpis veljaven}}

Korak 7: Nekdo spremeni besedilo ocene

Besedilo vstopa v zgoščeno vrednost, torej se spremeni izziv — recimo na k′=7k' = 7. Podpis ostane nespremenjen pri (16,1)(16,1), desna stran pa ne. Z 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
Podpis neveljaven\boxed{\text{Podpis neveljaven}}

Oceno lahko izbrišemo. Spremeniti je ne moremo, ne da bi to opazili.

Pošteno opozorilo k primeru

Računali smo v multiplikativni grupi po modulu 2323, ne na krivulji: gSg^S predstavlja S⋅BS\cdot B, produkt R⋅AkR\cdot A^k pa seštevanje točk R+k⋅AR + k\cdot A. Struktura je ista, in prav za to gre. Različni so velikostni razredi: ℓ=11\ell = 11 nasproti ℓ≈2252\ell \approx 2^{252}, in tam ključa ni mogoče najti s preizkušanjem enajstih možnosti.

14. Kaj se zgodi, če nekdo spremeni oceno

Recimo, da nekdo z dostopom do podatkovne baze — tudi nekdo pri nas — spremeni besedilo ocene ali eno od src. Tedaj se spremeni zapis in s tem vsaj ena od zgoščenih vrednosti h in rh v payloadu. S tem se spremeni mm, s tem izziv kk, s tem desna stran preverjalne enačbe. Stari podpis se ne ujema več.

Odločilni stavek k temu: oceno lahko izbrišemo, ne moremo pa je neopazno spremeniti. Pri McGesund isto preverjanje dodatno teče vsako noč na strežniku prek celotnega fonda — ocena, ki ga ne prestane, ne šteje več v povprečje podjetja.

15. Zakaj napadalec propade

Pozna javni ključ AA, bazno točko BB, krivuljo in vsak doslej izdani podpis. Manjka mu aa.

Najboljši znani klasični napad na problem diskretnega logaritma v skupini reda ℓ\ell potrebuje približno ℓ\sqrt{\ell} korakov. Pri ℓ≈2252\ell \approx 2^{252} je to približno

21262^{126}

operacij. Za primerjavo: tudi stroj, ki zmore milijardo milijard (101810^{18}) korakov na sekundo, bi za to potreboval večkratnik starosti vesolja.

Ponarejanje brez ključa bi pomenilo k sam izbranemu kk najti ustrezen SS — ista naloga v drugačni preobleki.

16. Zakaj Ed25519 in ne ECDSA

Oba temeljita na istem problemu. Razlika je v vsem, kar se dogaja okoli:

ECDSA (krivulje NIST)Ed25519
Noncepotrebno sveže naključjedeterminističen iz predpone in sporočila
Formuleposebni primeri, od podatkov odvisne vejepopolne, ena računska pot
Parametri krivuljeizvor konstant nikoli v celoti pojasnjenizbrani po izsledljivih merilih
Velikost podpisa64–72 B, spremenljivo kodiranjefiksno 64 B
V brskalnikuna voljo že dolgood 2023/2024 izvorno, sicer kot knjižnica JS

Za nas je bil nonce odločilni argument. Ocenjevalni portal podpisuje pogosto in avtomatizirano; postopek, pri katerem ena sama šibka naključna vrednost izda ključ, je za to napačna izbira.

17. Česa Ed25519 ne zmore

Ed25519 temelji na diskretnem logaritmu — in prav ta problem dovolj velik kvantni računalnik učinkovito reši s Shorovim algoritmom. Ali in kdaj bodo taki stroji obstajali, je odprto. Za oceno, ki naj bo preverljiva še čez deset let, je to kljub temu vprašanje, na katero je treba odgovoriti danes.

Zato lahko ob podpis Ed25519 stopi kvantno odporen žig:

Nobeden ne nadomešča Ed25519, oba se položita zraven. Če eden od postopkov pade, drugi nosi naprej.

18. Potek v sliki

PODPISNA STORITEV (MCGESUND)BRSKALNIK OBISKOVALCAzasebni skalar a + predpona (iz semena)payload m = {podjetje, ocena, h, rh, iat}r = H(predpona ‖ m) mod ℓR = r · Bk = H(R ‖ A ‖ m) mod ℓS = (r + k · a) mod ℓpodpis σ = (R, S) + kidocena + σ + javni ključ Aponovni izračun k iz R, A in mS · B = R + k · A ?veljavenneveljaven
Od payloada do kljukice v brskalniku. Nad ločnico se vse zgodi enkrat ob oddaji, pod njo pa pri vsakem bralcu na novo — na njegovi napravi, zgolj z javnim ključem.

19. Kaj McGesund konkretno počne s tem

Ovojnica. Vsaka podpisana ocena nosi ovojnico MCG1: z različico formata, payloadom in podpisom Ed25519. Vrednost kid v payloadu pove, kateri ključ je mišljen; pripadajoči javni ključ strežnik izda na zahtevo — je javen, na njem ni ničesar za zaščititi.

Preverjanje v brskalniku. Chrome in Firefox zmoreta Ed25519 od leta 2023/2024 izvorno prek vmesnika WebCrypto. Safari ne — tam klic namesto preverjanja vrže napako. Zato naša preverjalna koda pade nazaj na čisto implementacijo v JavaScriptu, ki se naloži samo tam, kjer je potrebna. Preverjanje podpisa s tem uspe v vsakem brskalniku, in sicer na napravi bralca.

Časovno sidro. Prstni odtis podpisnega ključa se prek OpenTimestamps zasidra v blok Bitcoin. S tem je mogoče dokazati ne le, da je podpis pristen, temveč tudi, da je ključ v določenem trenutku že obstajal — ne da bi moral kdo verjeti našemu časovnemu žigu.

Vezava na vsebino. Payload nosi rh, zgoščeno vrednost celotnega zapisa oddaje: besedila, src, geo statusa, navedb o povodu in izvora. Podpis Ed25519 s tem veže ne le besedilo, temveč vse, kar je prikazano ob oceni.

20. En stavek za s seboj

Ed25519 iz skrivnega sˇtevila naredi enacˇbo,ki jo lahko vsak preveri in nihcˇe izmisli.\boxed{ \begin{array}{c} \text{Ed25519 iz skrivnega števila naredi enačbo,}\\ \text{ki jo lahko vsak preveri in nihče izmisli.} \end{array}}

Kdor ima skrivni skalar, podpiše v mikrosekundah. Kdor ga nima, bi moral rešiti diskretni logaritem v skupini z okoli 22522^{252} elementi.

Za bralca ocene to preprosto pomeni: ni nam treba verjeti. Lahko preračuna sam.