Podpisové schéma

Ed25519 vysvětlený matematicky

Podpis, který visí u každého hodnocení na McGesund — od křivky přes klíč až po rovnici, kterou si přepočítá prohlížeč čtenáře.

Stav: 2026-09-07

1. O co tu jde

Hodnocení na McGesund není textové pole v databázi, kterému se musí věřit. Při odeslání je digitálně podepsáno a každý návštěvník si tento podpis může později přepočítat ve vlastním prohlížeči.

Pro tento podpis používáme Ed25519. Na rozdíl od FALCON a ML-DSA, které lze přiložit navíc jako razítko, není Ed25519 volitelný: každé podepsané hodnocení ho nese, nezávisle na tarifu a způsobu odeslání.

Důležité na úvod:

Ed25519 není šifrování. Text hodnocení se přece má číst. Podpis nedokazuje utajení, nýbrž původ a neporušenost.

2. Co přesně se podepisuje

Nepodepisuje se souvislý text, nýbrž kompaktní datový objekt, který text a vše ostatní jednoznačně přibíjí:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID firmy>",
  "c":   "<ID hodnocení>",
  "h":   "<SHA-256 textu hodnocení>",
  "rh":  "<SHA-256 celého odeslaného datového záznamu>",
  "rv":  1,
  "qh":  "<SHA-256 QR obálky, jen u QR hodnocení>",
  "kid": "<ID klíče>",
  "iat": 1757203200
}

Tento objekt se zakóduje do CBOR. Tato posloupnost bajtů — nikoli její úhledné zobrazení výše — je naše zpráva mm. Podpis a zpráva putují společně do obálky:

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

Trojka 33 je verze formátu. Víc v ní není — zejména žádný postkvantový podpis: ten leží, pokud existuje, vedle datového záznamu, a ne v obálce.

3. Co má podpis dokázat

Čtenář, který přijde na profil podniku, stojí před dvěma otázkami:

  1. Pochází toto hodnocení opravdu ze systému McGesund?
  2. Bylo dodatečně změněno?

K tomu slouží pár klíčů:

  • soukromý klíč — zůstává v podpisové službě
  • veřejný klíč — může mít každý, adresuje se přes ID klíče (kid) v payloadu

Podepisuje se soukromým klíčem. Ověřuje se veřejným — a to v prohlížeči čtenáře, ne na našem serveru. O to jde: ověření, které bychom prováděli sami a jehož výsledek bychom pak sdělovali, by nebylo ověření, nýbrž tvrzení.

4. Proč eliptická křivka?

Každý podpis potřebuje výpočet, který je jedním směrem snadný a druhým prakticky nemožný. U Ed25519 je to skalární násobení na eliptické křivce:

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

Spočítat z tajného čísla aa veřejný bod AA trvá mikrosekundy. Usoudit z AA zpět na aa znamená problém diskrétního logaritmu — pro něj není znám žádný postup, který by při této velikosti skončil v lidsky představitelných časech.

Praktickým ziskem oproti starším schématům, jako je RSA, je velikost:

veřejný klíčpodpis
RSA-3072384 B384 B
Ed2551932 B64 B

Při srovnatelné úrovni bezpečnosti. 64 bajtů na jedno hodnocení není ani při milionech hodnocení velikost, nad kterou by bylo třeba přemýšlet.

5. Křivka edwards25519

Počítá se modulo prvočíslo:

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

Odtud ten název. Křivka je zkroucená Edwardsova křivka:

−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 dvojice čísel (x,y)(x,y) z {0,…,p−1}\{0,\dots,p-1\}, která tuto rovnici splňuje. Žádná křivka tu k vidění není — kresba v následující kapitole je názorná pomůcka nad reálnými čísly, nikoli obraz skutečného výpočetního prostoru.

Přibývají ještě dvě veličiny:

  • pevně dohodnutý bázový bod BB,
  • řád ℓ\ell podgrupy generované bodem BB:
ℓ=2252+27742317777372353535851937790883648493.\ell = 2^{252} + 27742317777372353535851937790883648493.

ℓ\ell je prvočíslo. To znamená: přičítáme-li BB stále znovu k sobě samému, projdeme přesně ℓ\ell různých bodů a pak se vrátíme na začátek. Všechny výpočty se skaláry proto probíhají modulo ℓ\ell, všechny výpočty se souřadnicemi modulo pp. Zaměnit tato dvě čísla je klasická začátečnická chyba.

6. Sčítání bodů

Dva body se podle pevného vzorce spojí do třetího:

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álním prvkem je (0,1)(0,1) — bod, ve kterém výpočet začíná.

Tento vzorec má vlastnost, která na něm není vidět a která je pro bezpečnost důležitější než jakákoli konstanta: je úplný. Funguje pro všechny vstupy, bez zvláštních případů typu „oba body jsou stejné" nebo „výsledkem je neutrální prvek". U starších Weierstrassových křivek tyto zvláštní případy existují a každý z nich je větev v programu — větev, jejíž dobu běhu lze změřit. Kdo měří, jak dlouho podpis trvá, dozví se u takových schémat něco o tajném klíči.

Úplné vzorce znamenají: vždy stejná cesta výpočtu, vždy stejný čas, není co měřit.

7. Skalární násobení — jednosměrka

n⋅Bn\cdot B znamená: přičíst BB přesně nn-krát k sobě samému. U nn o délce 253 bitů by to bylo nesmyslně mnoho práce — proto se zdvojnásobuje:

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

a z těchto mezivýsledků se požadované nn složí. Zhruba 253 zdvojnásobení stačí pro každé nn. To je cesta vpřed.

Zpátky tato zkratka neexistuje. Určit z bodu AA číslo aa znamená vyřešit problém diskrétního logaritmu.

(0,1) — neutrální prvekB2B3B4B5B6B
Edwardsova křivka s prvními násobky bázového bodu, spočítanými skutečným zákonem sčítání. Nad reálnými čísly putují po křivce ještě viditelně uspořádaně — cestu by bylo možné vysledovat zpět. Modulo p právě toto uspořádání mizí, a na tom stojí bezpečnost.

Ve skutečném schématu se počítá modulo pp. Tam neexistuje žádné „vlevo", žádné „vpravo" a žádná blízkost: z 17 B17\,B a 18 B18\,B se stanou dvě dvojice čísel bez jakékoli rozpoznatelné příbuznosti.

8. Pár klíčů podpisové služby

Na začátku stojí 32 náhodných bajtů, seed. Vše ostatní se z něj odvozuje:

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 první poloviny vzniká tajný skalár aa, ovšem ne beze změny. Tři bity se nastaví, respektive vynulují — takzvaný clamping:

  • nejnižší tři bity se nastaví na nulu: aa se tím stane násobkem osmi. Důvodem je kofaktor 8 křivky — celá grupa bodů je osmkrát větší než podgrupa řádu ℓ\ell. Skalár aa dělitelný osmi zaručeně skončí ve správné podgrupě a neprozradí nic o bodech malého řádu.
  • nejvyšší bit se vynuluje, druhý nejvyšší se nastaví: aa má tím vždy stejnou bitovou délku. Kratší aa by potřebovalo méně zdvojnásobení — a z doby běhu by opět šlo něco vyčíst.

Veřejný klíč je pak prostě

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

uložený jako 32 bajtů: souřadnice yy a v nejvyšším bitu znaménko xx. Souřadnici xx si ověřovatel dopočítá sám zpětně z rovnice křivky — obě řešení se liší jen znaménkem a které z nich je míněno, říká právě tento jeden bit.

Druhá polovina hashe, prefix, se pro klíč nepoužije. Přijde na řadu v následující kapitole.

9. Proč zde náhoda není náhodná

Každý podpis této konstrukce potřebuje jednorázovou hodnotu rr, často nazývanou nonce. Nikdy se nesmí opakovat: kdo má dva podpisy se stejným rr, dopočítá tajný klíč středoškolskou algebrou.

Právě na tom reálné systémy ztroskotaly. Nejznámějším případem je ověřování podpisů herní konzole, jejíž výrobce v roce 2010 používal stále stejnou nonce — soukromý klíč tím byl veřejně rekonstruovatelný.

Ed25519 to řeší tak, že nepoužívá vůbec žádnou náhodu:

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

Nonce závisí na tajném prefixu a na zprávě. Z toho plyne dvojí:

  • Dvě různá hodnocení dají s drtivou pravděpodobností různá rr — případ opakování nenastane.
  • Totéž hodnocení dá vždy tentýž podpis. Podepisování je tak zpětně sledovatelné a špatný generátor náhody na serveru nemůže nic pokazit, protože žádný není potřeba.

Pro hodnoticí portál s mnoha podpisy denně to není akademická výhoda. Je to rozdíl mezi „chyba ve zdroji náhody by byla fatální" a „žádný zdroj náhody, který by mohl selhat, tu není".

10. Podepisování

Tři řádky, víc to není:

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.

Podpisem je dvojice

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

32 bajtů pro bod RR, 32 bajtů pro číslo SS — dohromady 64 bajtů.

Pozoruhodný je druhý řádek: do kk vstupuje RR, veřejný klíč AA a zpráva. To, že se AA hashuje s sebou, není ozdoba — brání to útokům, při nichž je podpis vyložen jako podpis pod jiným klíčem.

11. Ověřování

Prohlížeč čtenáře zná: hodnocení mm, podpis (R,S)(R,S) a veřejný klíč AA. Znovu si spočítá kk a ověří jedinou rovnici:

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

Platí-li, je podpis platný. RFC 8032 navíc připouští verzi vynásobenou kofaktorem 8S⋅B=8R+8k⋅A8S\cdot B = 8R + 8k\cdot A, která některé okrajové případy řeší velkoryseji.

Žádný server se neptá, žádná služba nemusí být dostupná. Veřejný klíč stačí.

12. Proč rovnice vychází

Stačí dosadit:

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 prostřední úpravě: skalární násobení se snáší se sčítáním. Kdo zná aa, umí spočítat SS, které rovnici splňuje. Kdo aa nezná, musel by k sebou zvolenému kk najít vyhovující SS — a to znamená vyřešit diskrétní logaritmus.

13. Kompletně propočítaný miniaturní příklad

Se skutečnými čísly není co počítat — 253bitové hodnoty se v hlavě ověřit nedají. Proto totéž schéma v nepatrné grupě, kde je každý krok kontrolovatelný kalkulačkou.

Krok 1: Grupa

Počítáme se zbytky modulo 2323 a bereme g=2g = 2. Platí

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

gg tedy generuje podgrupu řádu ℓ=11\ell = 11. Mocniny jsou:

nn1234567891011
gng^n248169181336121

gg přebírá roli bázového bodu BB, násobení roli sčítání bodů. Skaláry se počítají modulo 1111, hodnoty modulo 2323.

Krok 2: Pár klíčů

Nechť tajné je a=6a = 6. Pak je

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

A=18A = 18 smí vědět každý.

Krok 3: Nonce a commitment

Z prefixu a hodnocení nechť vyjde r=4r = 4. Odtud:

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

Krok 4: Výzva

Hash přes RR, AA a hodnocení nechť 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.

Podpisem je dvojice (R,S)=(16, 1)(R,S) = (16,\,1).

Krok 6: Prohlížeč ověřuje

Spočítá obě strany. Vlevo:

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

Obě strany dávají 22:

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

Krok 7: Někdo změní text hodnocení

Text vstupuje do hashe, takže se změní výzva — řekněme na k′=7k' = 7. Podpis zůstává nezměněn na (16,1)(16,1), pravá strana ale ne. 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ý}}

Hodnocení můžeme smazat. Změnit ho tak, aby si toho nikdo nevšiml, nemůžeme.

Poznámka na rovinu k příkladu

Počítalo se zde v multiplikativní grupě modulo 2323, ne na křivce: gSg^S zastupuje S⋅BS\cdot B, součin R⋅AkR\cdot A^k zastupuje sčítání bodů R+k⋅AR + k\cdot A. Struktura je táž, a přesně o to jde. Liší se řády velikosti: ℓ=11\ell = 11 oproti ℓ≈2252\ell \approx 2^{252}, a tam klíč vyzkoušením jedenácti možností najít nelze.

14. Co se stane, když někdo hodnocení změní

Dejme tomu, že někdo s přístupem k databázi — i někdo u nás — změní text hodnocení nebo jedno ze srdíček. Pak se změní datový záznam a s ním alespoň jeden z obou hashů h a rh v payloadu. Tím se změní mm, tím výzva kk, tím pravá strana ověřovací rovnice. Starý podpis už nesedí.

Rozhodující věta k tomu: hodnocení můžeme smazat, ale nemůžeme ho nepozorovaně změnit. Na McGesund běží totéž ověření navíc každou noc serverově nad celým fondem — hodnocení, které jím neprojde, už do průměru podniku nevstupuje.

15. Proč útočník neuspěje

Zná veřejný klíč AA, bázový bod BB, křivku i každý dosud vystavený podpis. Co mu chybí, je aa.

Nejlepší známý klasický útok na problém diskrétního logaritmu v grupě řádu ℓ\ell potřebuje zhruba ℓ\sqrt{\ell} kroků. Při ℓ≈2252\ell \approx 2^{252} je to přibližně

21262^{126}

operací. Pro srovnání: i stroj, který zvládne miliardu miliard (101810^{18}) kroků za sekundu, by na to potřeboval mnohonásobek stáří vesmíru.

Padělat bez klíče by znamenalo najít k sebou zvolenému kk vyhovující SS — táž úloha v jiném přestrojení.

16. Proč Ed25519 a ne ECDSA

Obojí stojí na témže problému. Rozdíl je ve všem, co se děje okolo:

ECDSA (křivky NIST)Ed25519
Noncenutná čerstvá náhodadeterministická z prefixu a zprávy
Vzorcezvláštní případy, větve závislé na datechúplné, jediná cesta výpočtu
Parametry křivkypůvod konstant nikdy plně vysvětlenzvoleny podle doložitelných kritérií
Velikost podpisu64–72 B, proměnlivé kódovánípevných 64 B
V prohlížečidostupné odedávnaod roku 2023/2024 nativně, jinak jako knihovna v JS

Pro nás byla rozhodujícím argumentem nonce. Hodnoticí portál podepisuje často a automatizovaně; schéma, u něhož jediná slabá náhodná hodnota vyzradí klíč, je pro to špatná volba.

17. Co Ed25519 neumí

Ed25519 stojí na diskrétním logaritmu — a právě tento problém řeší dostatečně velký kvantový počítač efektivně Shorovým algoritmem. Zda a kdy takové stroje budou, je otevřené. Pro hodnocení, které má být ověřitelné ještě za deset let, je to přesto otázka, kterou je nutné zodpovědět dnes.

Proto může vedle podpisu Ed25519 stanout kvantově odolné razítko:

Ani jedno Ed25519 nenahrazuje, obě si k němu lehnou. Zlomí-li se jedno ze schémat, druhé nese dál.

18. Průběh v obrázku

PODPISOVÁ SLUŽBA (MCGESUND)PROHLÍŽEČ NÁVŠTĚVNÍKAsoukromý skalár a + prefix (ze seedu)payload m = {firma, hodnocení, h, rh, iat}r = H(prefix ‖ m) mod ℓR = r · Bk = H(R ‖ A ‖ m) mod ℓS = (r + k · a) mod ℓpodpis σ = (R, S) + kidhodnocení + σ + veřejný klíč Aznovu spočítat k z R, A a mS · B = R + k · A ?platnýneplatný
Od payloadu až po zaškrtnutí v prohlížeči. Nad dělicí čarou se vše děje jednou při odeslání, pod ní znovu u každého čtenáře — na jeho zařízení, jen s veřejným klíčem.

19. Co s tím McGesund konkrétně dělá

Obálka. Každé podepsané hodnocení nese obálku MCG1: s verzí formátu, payloadem a podpisem Ed25519. Hodnota kid v payloadu říká, o který klíč jde; příslušný veřejný klíč vydá server na vyžádání — je veřejný, není na něm co chránit.

Ověření v prohlížeči. Chrome a Firefox umějí Ed25519 od roku 2023/2024 nativně přes rozhraní WebCrypto. Safari ne — tam volání místo ověření vyhodí chybu. Náš ověřovací kód proto přejde na čistě javascriptovou implementaci, která se donačte jen tam, kde je potřeba. Ověření podpisu tak proběhne v každém prohlížeči, a to na zařízení čtenáře.

Časová kotva. Otisk podpisového klíče je přes OpenTimestamps zakotven v bloku Bitcoinu. Tím lze doložit nejen to, že je podpis pravý, ale i to, že klíč v určitém okamžiku již existoval — aniž by někdo musel věřit našemu časovému razítku.

Vazba na obsah. Payload nese rh, hash přes celý odeslaný datový záznam: text, srdíčka, geostatus, údaje o důvodu a původ. Podpis Ed25519 tak neváže jen text, nýbrž vše, co se vedle hodnocení zobrazuje.

20. Jedna věta na závěr

Ed25519 promeˇnıˊ tajneˊ cˇıˊslo v rovnici,kterou si kazˇdyˊ oveˇrˇıˊ a nikdo ji nevymyslıˊ.\boxed{ \begin{array}{c} \text{Ed25519 promění tajné číslo v rovnici,}\\ \text{kterou si každý ověří a nikdo ji nevymyslí.} \end{array}}

Kdo tajný skalár vlastní, podepisuje v mikrosekundách. Kdo ho nevlastní, musel by vyřešit diskrétní logaritmus v grupě s asi 22522^{252} prvky.

Pro čtenáře hodnocení to znamená prostě tohle: nemusí nám věřit. Může si to přepočítat.