Podpisová schéma

Ed25519 vysvetlený matematicky

Podpis, ktorý visí na každom hodnotení McGesund — od krivky cez kľúč až po rovnicu, ktorú si prepočíta prehliadač čitateľa.

Stav: 2026-09-07

1. O čo tu ide

Hodnotenie na McGesund nie je textové pole v databáze, ktorému treba veriť. Pri odoslaní sa digitálne podpíše a každý návštevník si tento podpis môže neskôr prepočítať vo vlastnom prehliadači.

Na tento podpis používame Ed25519. Na rozdiel od FALCON a ML-DSA, ktoré sa môžu priložiť navyše ako pečiatka, Ed25519 nie je voliteľný: každé podpísané hodnotenie ho nesie, bez ohľadu na tarif a spôsob odovzdania.

Dôležité na úvod:

Ed25519 nie je šifrovanie. Text hodnotenia sa predsa má čítať. Podpis nedokazuje utajenie, ale pôvod a neporušenosť.

2. Čo presne sa podpisuje

Nepodpisuje sa súvislý text, ale kompaktný dátový objekt, ktorý text a všetko ostatné jednoznačne pribíja:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID firmy>",
  "c":   "<ID hodnotenia>",
  "h":   "<SHA-256 textu hodnotenia>",
  "rh":  "<SHA-256 celého odovzdaného záznamu>",
  "rv":  1,
  "qh":  "<SHA-256 QR obálky, len pri QR hodnoteniach>",
  "kid": "<ID kľúča>",
  "iat": 1757203200
}

Tento objekt sa zakóduje do CBOR. Táto postupnosť bajtov — nie jej pekné zobrazenie vyššie — je naša správa mm. Podpis a správa putujú spoločne do obálky:

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

Trojka 33 je verzia formátu. Viac v nej nie je — predovšetkým žiadny postkvantový podpis: ten leží, ak existuje, vedľa záznamu a nie v obálke.

3. Čo má podpis dokázať

Čitateľ, ktorý príde na profil podniku, stojí pred dvoma otázkami:

  1. Pochádza toto hodnotenie naozaj zo systému McGesund?
  2. Bolo dodatočne zmenené?

Na to slúži pár kľúčov:

  • súkromný kľúč — zostáva v podpisovej službe
  • verejný kľúč — môže ho mať každý, adresuje sa cez ID kľúča (kid) v payloade

Podpisuje sa súkromným kľúčom. Overuje sa verejným — a to v prehliadači čitateľa, nie na našom serveri. To je celá pointa: overenie, ktoré vykonáme sami a ktorého výsledok len oznámime, by nebolo overením, ale tvrdením.

4. Prečo eliptická krivka?

Každý podpis potrebuje výpočet, ktorý je jedným smerom ľahký a druhým prakticky nemožný. Pri Ed25519 je to skalárne násobenie na eliptickej krivke:

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

Vypočítať z tajného čísla aa verejný bod AA stojí mikrosekundy. Usúdiť z AA späť na aa znamená problém diskrétneho logaritmu — na ten nie je známy postup, ktorý by pri tejto veľkosti skončil v ľudských časových horizontoch.

Praktický zisk oproti starším postupom, ako je RSA, je veľkosť:

verejný kľúčpodpis
RSA-3072384 B384 B
Ed2551932 B64 B

Pri porovnateľnej úrovni bezpečnosti. 64 bajtov na jedno hodnotenie nie je ani pri miliónoch hodnotení veličina, nad ktorou by bolo treba rozmýšľať.

5. Krivka edwards25519

Počíta sa modulo prvočíslo:

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

Odtiaľ ten názov. Krivka je skrútená Edwardsova krivka:

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

„Bod" je dvojica čísel (x,y)(x,y) z množiny {0,…,p−1}\{0,\dots,p-1\}, ktorá spĺňa túto rovnicu. Niet tu žiadnu krivku vidieť — nákres v nasledujúcej časti je názorná pomôcka nad reálnymi číslami, nie obrázok skutočného výpočtového priestoru.

Pribúdajú ešte dve veličiny:

  • pevne dohodnutý základný bod BB,
  • rád ℓ\ell podgrupy generovanej bodom BB:
ℓ=2252+27742317777372353535851937790883648493.\ell = 2^{252} + 27742317777372353535851937790883648493.

ℓ\ell je prvočíslo. To znamená: ak sa BB stále dokola pripočítava k sebe samému, prejde sa presne ℓ\ell rôznych bodov a potom sa opäť skončí na začiatku. Všetky výpočty so skalármi preto bežia modulo ℓ\ell, všetky výpočty so súradnicami modulo pp. Zameniť tieto dve čísla je klasická chyba začiatočníka.

6. Sčitovanie bodov

Dva body sa podľa pevného vzorca prepočítajú na tretí:

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

Neutrálnym prvkom je (0,1)(0,1) — bod, v ktorom sa počítanie začína.

Tento vzorec má vlastnosť, ktorá na ňom nie je vidieť a ktorá je pre bezpečnosť dôležitejšia než ktorákoľvek konštanta: je úplný. Funguje pre všetky vstupy, bez osobitných prípadov typu „oba body sú rovnaké" alebo „výsledok je neutrálny prvok". Pri starších Weierstrassových krivkách tieto osobitné prípady existujú a každý z nich je vetva v programe — vetva, ktorej čas behu sa dá odmerať. Kto meria, ako dlho trvá podpis, dozvie sa pri takýchto postupoch niečo o tajnom kľúči.

Úplné vzorce znamenajú: vždy tá istá cesta výpočtu, vždy ten istý čas, niet čo merať.

7. Skalárne násobenie — jednosmerka

n⋅Bn\cdot B znamená: pripočítať BB presne nn-krát k sebe samému. Pri nn s 253 bitmi by to bolo nezmyselne veľa práce — preto sa zdvojnásobuje:

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

a z týchto medzivýsledkov sa poskladá požadované nn. Približne 253 zdvojnásobení stačí na každé nn. To je cesta dopredu.

Naspäť takáto skratka neexistuje. Určiť z bodu AA číslo aa znamená vyriešiť problém diskrétneho logaritmu.

(0,1) — neutrálny prvokB2B3B4B5B6B
Edwardsova krivka s prvými násobkami základného bodu, vypočítanými skutočným zákonom sčitovania. Nad reálnymi číslami putujú po krivke ešte viditeľne usporiadane — cestu by sa dalo vystopovať späť. Modulo p zmizne práve toto usporiadanie a na tom stojí bezpečnosť.

V skutočnom postupe sa počíta modulo pp. Tam neexistuje žiadne „vľavo", žiadne „vpravo" a žiadna blízkosť: z 17 B17\,B a 18 B18\,B sa stanú dve dvojice čísel bez akejkoľvek rozpoznateľnej príbuznosti.

8. Pár kľúčov podpisovej služby

Na začiatku je 32 náhodných bajtov, seed. Všetko ostatné sa z neho odvodí:

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

Z prvej polovice vzniká tajný skalár aa, avšak nie nezmenený. Tri bity sa nastavia, respektíve vynulujú — takzvaný clamping:

  • najspodnejšie tri bity sa nastavia na nulu: aa sa tým stáva násobkom čísla 8. Dôvodom je kofaktor 8 krivky — plná grupa bodov je osemkrát väčšia než podgrupa rádu ℓ\ell. Číslo aa deliteľné ôsmimi zaručene skončí v správnej podgrupe a o bodoch malého rádu nič neprezradí.
  • najvyšší bit sa vynuluje, druhý najvyšší nastaví: aa má tým vždy rovnakú bitovú dĺžku. Kratšie aa by potrebovalo menej zdvojnásobení — a z času behu by sa opäť dalo niečo vyčítať.

Verejný kľúč je potom jednoducho

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

uložený ako 32 bajtov: súradnica yy a v najvyššom bite znamienko xx. Súradnicu xx si overovateľ dopočíta sám z rovnice krivky — obe riešenia sa líšia len znamienkom a ktoré je myslené, hovorí práve tento jeden bit.

Druhá polovica hašovej hodnoty, prefix, sa na kľúč nepotrebuje. Prichádza na rad v nasledujúcej časti.

9. Prečo náhoda tu nie je náhodou

Každý podpis tohto typu potrebuje jednorazovú hodnotu rr, často nazývanú nonce. Nikdy sa nesmie zopakovať: kto má dva podpisy s rovnakým rr, dokáže tajný kľúč vypočítať školskou algebrou.

Práve na tom stroskotali reálne systémy. Najznámejším prípadom je overovanie podpisov hernej konzoly, ktorej výrobca v roku 2010 používal stále rovnakú nonce — súkromný kľúč sa tým dal verejne zrekonštruovať.

Ed25519 to rieši tak, že nepoužíva náhodu vôbec:

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

Nonce visí na tajnom prefixe a na správe. Z toho vyplýva dvojaké:

  • Dve rôzne hodnotenia dávajú s ohromujúcou pravdepodobnosťou rôzne rr — prípad opakovania nenastane.
  • To isté hodnotenie dáva vždy ten istý podpis. Podpisový úkon sa tak dá zopakovať a overiť a zlý generátor náhodných čísel na serveri nemôže nič pokaziť, pretože žiadny nie je potrebný.

Pre hodnotiaci portál s mnohými podpismi denne to nie je akademická výhoda. Je to rozdiel medzi „chyba v zdroji náhody by bola osudná" a „neexistuje zdroj náhody, ktorý by mohol zlyhať".

10. Podpisovanie

Tri riadky, viac to nie je:

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.

Podpisom je dvojica

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

32 bajtov pre bod RR, 32 bajtov pre číslo SS — spolu 64 bajtov.

Pozoruhodný je druhý riadok: do kk vstupuje RR, verejný kľúč AA aj správa. To, že sa spolu hašuje aj AA, nie je ozdoba — bráni to útokom, pri ktorých sa podpis prekladá na iný kľúč.

11. Overovanie

Prehliadač čitateľa pozná: hodnotenie mm, podpis (R,S)(R,S) a verejný kľúč AA. Nanovo si vypočíta kk a overí jedinú rovnicu:

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

Ak platí, podpis je platný. RFC 8032 dodatočne pripúšťa verziu vynásobenú kofaktorom 8S⋅B=8R+8k⋅A8S\cdot B = 8R + 8k\cdot A, ktorá zaobchádza s niektorými okrajovými prípadmi veľkorysejšie.

Nikto sa nepýta servera, žiadna služba nemusí byť dostupná. Verejný kľúč postačuje.

12. Prečo rovnica vychádza

Stačí dosadiť:

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.

Celý trik väzí v strednej úprave: skalárne násobenie sa znáša so sčitovaním. Kto pozná aa, dokáže vypočítať SS, ktoré rovnicu spĺňa. Kto aa nepozná, musel by k vlastnému zvolenému kk nájsť vyhovujúce SS — a to znamená vyriešiť diskrétny logaritmus.

13. Úplne prepočítaný miniatúrny príklad

So skutočnými číslami sa nedá nič prepočítať — 253-bitové hodnoty sa nedajú overiť z hlavy. Preto ten istý postup v maličkej grupe, v ktorej je každý krok overiteľný kalkulačkou.

Krok 1: Grupa

Počítame so zvyškami modulo 2323 a berieme g=2g = 2. Platí

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

gg teda generuje podgrupu rádu ℓ=11\ell = 11. Mocniny sú:

nn1234567891011
gng^n248169181336121

gg preberá úlohu základného bodu BB, násobenie úlohu sčitovania bodov. Skaláry sa počítajú modulo 1111, hodnoty modulo 2323.

Krok 2: Pár kľúčov

Nech je tajné a=6a = 6. Potom je

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

A=18A = 18 smie vedieť každý.

Krok 3: Nonce a commitment

Z prefixu a hodnotenia nech vyjde r=4r = 4. Z toho:

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

Krok 4: Výzva

Nech haš z RR, AA a hodnotenia dá

k=5.k = 5.

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

Podpisom je dvojica (R,S)=(16, 1)(R,S) = (16,\,1).

Krok 6: Prehliadač overuje

Vypočíta obe strany. Vľavo:

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

Vpravo, s 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 strany dávajú 22:

Podpis je platnyˊ\boxed{\text{Podpis je platný}}

Krok 7: Niekto zmení text hodnotenia

Text vstupuje do hašu, takže sa zmení výzva — povedzme na k′=7k' = 7. Podpis zostáva nezmenený na (16,1)(16,1), pravá strana však nie. S 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 je neplatnyˊ\boxed{\text{Podpis je neplatný}}

Hodnotenie môžeme zmazať. Zmeniť ho tak, aby si to nikto nevšimol, nedokážeme.

Poznámka o poctivosti príkladu

Počítalo sa tu v multiplikatívnej grupe modulo 2323, nie na krivke: gSg^S zastupuje S⋅BS\cdot B, súčin R⋅AkR\cdot A^k zastupuje sčítanie bodov R+k⋅AR + k\cdot A. Štruktúra je rovnaká a práve o ňu ide. Rôzne sú rádové veľkosti: ℓ=11\ell = 11 oproti ℓ≈2252\ell \approx 2^{252}, a tam sa kľúč nedá nájsť vyskúšaním jedenástich možností.

14. Čo sa stane, keď niekto hodnotenie zmení

Predpokladajme, že niekto s prístupom do databázy — aj niekto u nás — zmení text hodnotenia alebo jedno zo sŕdc. Potom sa zmení záznam a tým aspoň jedna z dvoch hašových hodnôt h a rh v payloade. Tým sa zmení mm, tým výzva kk, tým pravá strana overovacej rovnice. Starý podpis už nesedí.

Rozhodujúca veta k tomu: hodnotenie môžeme zmazať, ale nemôžeme ho nepozorovane zmeniť. Na McGesund beží to isté overenie navyše každú noc serverovo nad celým fondom — hodnotenie, ktoré ním neprejde, už nevstupuje do priemeru podniku.

15. Prečo útočník neuspeje

Pozná verejný kľúč AA, základný bod BB, krivku a každý doteraz vydaný podpis. Chýba mu aa.

Najlepší známy klasický útok na problém diskrétneho logaritmu v grupe rádu ℓ\ell potrebuje približne ℓ\sqrt{\ell} krokov. Pri ℓ≈2252\ell \approx 2^{252} je to zhruba

21262^{126}

operácií. Pre porovnanie: aj stroj, ktorý zvládne miliardu miliárd (101810^{18}) krokov za sekundu, by na to potreboval mnohonásobok veku vesmíru.

Falšovať bez kľúča by znamenalo nájsť k vlastnému zvolenému kk vyhovujúce SS — tá istá úloha v inom prestrojení.

16. Prečo Ed25519 a nie ECDSA

Obidve stoja na tom istom probléme. Rozdiel je vo všetkom, čo sa deje okolo:

ECDSA (krivky NIST)Ed25519
Noncepotrebná čerstvá náhodadeterministická z prefixu a správy
Vzorceosobitné prípady, vetvy závislé od dátúplné, jediná cesta výpočtu
Parametre krivkypôvod konštánt nikdy úplne vysvetlenýzvolené podľa overiteľných kritérií
Veľkosť podpisu64 – 72 B, premenlivé kódovaniepevných 64 B
V prehliadačidostupné odjakživaod rokov 2023/2024 natívne, inak ako JS knižnica

Pre nás bola rozhodujúcim argumentom nonce. Hodnotiaci portál podpisuje často a automatizovane; postup, pri ktorom jediná slabá náhodná hodnota vyzradí kľúč, je na to nesprávnou voľbou.

17. Čo Ed25519 nedokáže

Ed25519 stojí na diskrétnom logaritme — a práve tento problém rieši dostatočne veľký kvantový počítač efektívne Shorovým algoritmom. Či a kedy takéto stroje budú, je otvorené. Pre hodnotenie, ktoré má byť overiteľné aj o desať rokov, je to napriek tomu otázka, na ktorú treba odpovedať dnes.

Preto môže vedľa podpisu Ed25519 pristúpiť kvantovo odolná pečiatka:

Ani jeden Ed25519 nenahrádza, kladú sa vedľa neho. Ak jeden z postupov padne, druhý nesie ďalej.

18. Priebeh v obraze

PODPISOVÁ SLUŽBA (MCGESUND)PREHLIADAČ NÁVŠTEVNÍKAsúkromný skalár a + prefix (zo seedu)payload m = {firma, hodnotenie, h, rh, iat}r = H(prefix ‖ m) mod ℓR = r · Bk = H(R ‖ A ‖ m) mod ℓS = (r + k · a) mod ℓpodpis σ = (R, S) + kidhodnotenie + σ + verejný kľúč Aprepočítať k z R, A a mS · B = R + k · A ?platnýneplatný
Od payloadu až po potvrdzujúcu fajku v prehliadači. Nad deliacou čiarou sa všetko deje raz pri odoslaní, pod ňou nanovo u každého čitateľa — na jeho zariadení, len s verejným kľúčom.

19. Čo s tým McGesund konkrétne robí

Obálka. Každé podpísané hodnotenie nesie obálku MCG1: s verziou formátu, payloadom a podpisom Ed25519. kid v payloade hovorí, ktorý kľúč je myslený; príslušný verejný kľúč vydá server na požiadanie — je verejný, nie je na ňom čo chrániť.

Overenie v prehliadači. Chrome a Firefox zvládajú Ed25519 od rokov 2023/2024 natívne cez rozhranie WebCrypto. Safari nie — tam volanie namiesto overenia vyhodí chybu. Preto sa náš overovací kód vracia k čisto javascriptovej implementácii, ktorá sa donačíta len tam, kde je potrebná. Overenie podpisu tak prebehne v každom prehliadači, a to na zariadení čitateľa.

Časová kotva. Odtlačok podpisového kľúča sa cez OpenTimestamps ukotví v bloku Bitcoinu. Tým sa dá doložiť nielen to, že podpis je pravý, ale aj to, že kľúč v určitom okamihu už existoval — bez toho, aby musel niekto veriť našej časovej pečiatke.

Väzba na obsah. Payload nesie rh, haš z celého odovzdaného záznamu: text, srdcia, geo-status, údaje o príležitosti a pôvod. Podpis Ed25519 tým viaže nielen text, ale všetko, čo sa vedľa hodnotenia zobrazuje.

20. Jedna veta na záver

Ed25519 robıˊ z tajneˊho cˇıˊsla rovnicu,ktoruˊ si kazˇdyˊ overıˊ a nikto ju nevymyslıˊ.\boxed{ \begin{array}{c} \text{Ed25519 robí z tajného čísla rovnicu,}\\ \text{ktorú si každý overí a nikto ju nevymyslí.} \end{array}}

Kto vlastní tajný skalár, podpisuje za mikrosekundy. Kto ho nevlastní, musel by vyriešiť diskrétny logaritmus v grupe s približne 22522^{252} prvkami.

Pre čitateľa hodnotenia to znamená jednoducho: nemusí nám veriť. Môže si to prepočítať.