Podpisové schéma

FALCON vysvětlený matematicky

Jak se hodnocení na McGesund podepisuje pomocí FN-DSA (FALCON) — a proč jediný změněný znak podpis zlomí.

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 část těchto podpisů používáme FALCON — přesněji FN-DSA-512 a FN-DSA-1024. Tento článek vysvětluje, co se přitom matematicky děje.

Důležité na úvod:

FALCON není šifrování. Text hodnocení se přece má číst. FALCON 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 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í>",
  "iat": 1757203200
}

To je naše zpráva mm. Váže dohromady:

  1. ke kterému podniku hodnocení patří (f),
  2. o které hodnocení jde (c),
  3. jaký text za ním stál — jako hash (h),
  4. jaký datový záznam byl celkově odeslán (rh): text, srdíčka, geostatus a údaje o důvodu, kanonicky serializované a zahashované, ve verzi schématu rv,
  5. z jakého QR kódu hodnocení pochází (qh) — u hodnocení bez QR kódu pole odpadá,
  6. kdy se podepisovalo (iat).

Jediný změněný znak v textu hodnocení tento řetěz zlomí. Přesně to je jeho účel — a od zavedení rh platí totéž pro dodatečně posunuté srdíčko nebo změněný geostatus.

3. Základní problém

Č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ý

Podepisuje se soukromým, ověřuje veřejným klíčem. A to na zařízení čtenáře, ne na našem serveru.

4. Proč FALCON?

Mnohá dnešní podpisová schémata stojí na problémech, které jsou pro klasické počítače těžké, pro dostatečně velké kvantové počítače by se ale mohly stát podstatně lehčími.

U hodnocení je to relevantnější než u prchavé zprávy: hodnocení má být ověřitelné ještě za pět nebo deset let. Kdo podepisuje dnes, podepisuje na celou dobu životnosti záznamu.

FALCON proto stojí na mřížkové kryptografii:

Postaví se matematicky snadno popsatelná mřížka, ve které je určitá vyhledávací úloha extrémně těžká.

5. Co je matematická mřížka?

Dva vektory:

v1=(2,0),v2=(1,2).v_1=(2,0), \qquad v_2=(1,2).

Všechny celočíselné kombinace

a v1+b v2,a,b∈Za\,v_1+b\,v_2, \qquad a,b\in\mathbb{Z}

dávají mřížku bodů. Například:

2v1+3v2=(4,0)+(3,6)=(7,6).2v_1+3v_2=(4,0)+(3,6)=(7,6).
v₁ = (2,0)v₂ = (1,2)(7,6)0
Dva vektory rozepnou mřížku. Každý bod je celočíselná kombinace obou — vyznačený vzniká jako dvakrát v₁ a třikrát v₂.

Rozhodující je:

Samotná mřížka se popíše snadno. Najít v ní určité vlastnosti je velmi těžké.

6. Tajemstvím jsou krátké vektory

Klasická těžká úloha zní:

min⁡v∈L,  v≠0∥v∥.\min_{v\in L,\;v\neq0}\|v\|.

To je Shortest Vector Problem. Ve dvou dimenzích se dá vyzkoušet. FALCON pracuje v dimenzi 512 nebo 1024 — tam je to beznadějné.

dlouhá bázetéměř rovnoběžnénejkratší vektor
Táž mřížka, dva popisy. Šedé vektory ji generují také, jsou ale dlouhé a téměř rovnoběžné — špatná báze. Krátký vektor je to, co je těžké najít.

FALCON ovšem nepotřebuje nejkratší vektor jako takový, nýbrž něco příbuzného: k zadanému cílovému bodu najít blízký bod mřížky. I to je bez správné dodatečné informace těžké.

cílový bod z hodnoceníblízký bod mřížkydaleko
Cílový bod z hodnocení (prázdný kroužek) v mřížce neleží. Hledá se bod mřížky těsně vedle něj — čárkovaná cesta ke vzdálenému bodu je rovněž řešením první podmínky, jenže není krátká.

7. Polynomy místo čísel

FALCON používá NTRU mřížku a počítá s polynomy. Tedy místo s jednotlivými čísly se seznamy koeficientů:

f=(1,0,1,0,0,1)⟷f(x)=1+x2+x5.f=(1,0,1,0,0,1) \quad\longleftrightarrow\quad f(x)=1+x^2+x^5.

Počítá se v okruhu

Rq=Zq[x]/(xn+1).R_q=\mathbb{Z}_q[x]/(x^n+1).

To znamená:

  • Zq\mathbb{Z}_q: počítání modulo qq. Při q=7q=7 třeba 10≡310\equiv3, neboť 10−7=310-7=3.
  • xn=−1x^n=-1: drží polynomy na pevné délce.

FALCON konkrétně používá:

q=12289,n=512  nebo  1024.q=12289, \qquad n=512 \;\text{nebo}\; 1024.

8. Ústřední trik

Soukromý klíč se skládá ze čtyř malých polynomů

f,  g,  F,  Gf,\;g,\;F,\;G

s NTRU rovnicí

fG−gF=q.fG-gF=q.

Tato čtveřice tvoří dohromady tajnou, dobře tvarovanou bázi mřížky — popis mřížky z krátkých vektorů.

Veřejný klíč je v podstatě jediný polynom:

h=gf(modq).h=\frac{g}{f}\pmod q.

Z hh vyplývá táž mřížka, ale v nepohodlné bázi z dlouhých vektorů:

L={(s1,s2)  :  s1+s2 h≡0(modq)}.L=\{(s_1,s_2)\;:\;s_1+s_2\,h\equiv0 \pmod q\}.

To je celé jádro FALCONu. Obě báze popisují tutéž mřížku. Jen jedna je k počítání použitelná a druhá ne.

Lze si to představit jako plán města: veřejně dostupná je úplná mapa. Tajná je znalost zkratek.

9. Z hodnocení se stane bod

Před podepsáním projde objekt payloadu hashovací funkcí. FALCON k tomu používá Hash-to-Point: ze zprávy nevznikne číselná hodnota, nýbrž rovnou bod v okruhu.

Podpisová služba navíc vylosuje náhodnou sůl rr (320 bitů) a zahashuje ji s sebou:

c=HashToPoint(r ∥ m).c=\mathrm{HashToPoint}(r \,\|\, m).

Sůl není ozdoba. Bez ní by totéž hodnocení dávalo vždy tentýž podpis a z mnoha podpisů by šlo rekonstruovat tajnou bázi. Putuje proto s sebou do podpisu.

10. Co je platný podpis

Hledá se dvojice

(s1,s2)(s_1,s_2)

se dvěma vlastnostmi:

s1+s2 h≡c(modq)a∥(s1,s2)∥  malaˊ.s_1+s_2\,h\equiv c \pmod q \qquad\text{a}\qquad \|(s_1,s_2)\|\;\text{malá}.

První podmínku samotnou lze splnit triviálně — položí se s2=0s_2=0 a s1=cs_1=c. Druhá podmínka činí úlohu těžkou.

Podpisem je praˊveˇ ta kraˊtkost.\boxed{\text{Podpisem je právě ta krátkost.}}

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

Vše zmenšíme na hračkovou velikost: polynomy s jediným koeficientem, tedy obyčejná čísla, a

q=97.q=97.

Tajný klíč. Dvě malá čísla:

f=3,g=5.f=3, \qquad g=5.

Veřejný klíč. Platí 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, neboť 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Tedy:

h=g⋅f−1=5⋅65=325≡34(mod97).h=g\cdot f^{-1}=5\cdot65=325\equiv \boxed{34} \pmod{97}.

Mřížka. L={(s1,s2):s1+34 s2≡0(mod97)}L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}.

Veřejná báze vyplývá přímo z hh:

(97,0)a(−34,1).(97,0) \quad\text{a}\quad (-34,1).

Obojí leží v LL — a obojí je dlouhé.

Tajnou bázi zná jen podpisová služba:

(−g,f)=(−5,3)a(−G,F)=(−9,−14),(-g,f)=(-5,3) \quad\text{a}\quad (-G,F)=(-9,-14),

neboť −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 a −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Determinant je

(−5)(−14)−(3)(−9)=70+27=97=q,(-5)(-14)-(3)(-9)=70+27=97=q,

NTRU rovnice tedy vychází. Oba vektory jsou krátké.

Krok 1: Zahashovat hodnocení

Dejme tomu, že objekt payloadu hodnocení dá

c=71.c=71.

Krok 2: První, špatné řešení

(s1,s2)=(71,0)(s_1,s_2)=(71,0)

splňuje 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Ale délka je 7171 — mnohem příliš dlouhá.

Krok 3: Zkrátit tajnou bází

Podpisová služba vyjádří cílový bod ve své krátké bázi:

(71,0)=a (−5,3)+b (−9,−14).(71,0)=a\,(-5,3)+b\,(-9,-14).

To vede na a≈−10,25a\approx-10{,}25 a b≈−2,20b\approx-2{,}20. Po zaokrouhlení na a=−10a=-10, b=−2b=-2 vychází bod mřížky

−10 (−5,3)−2 (−9,−14)=(50,−30)+(18,28)=(68,−2).-10\,(-5,3)-2\,(-9,-14)=(50,-30)+(18,28)=(68,-2).

Kontrola: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, tedy skutečně v LL. Odečteme:

(71,0)−(68,−2)=(3,2)(71,0)-(68,-2)=\boxed{(3,2)}

Délka:

∥(3,2)∥=9+4=13≈3,61.\|(3,2)\|=\sqrt{9+4}=\sqrt{13}\approx3{,}61.

To je podpis.

Krok 4: Týž postup s veřejnou bází

Kdo zná jen h=34h=34, má bázi {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Týž zaokrouhlovací výpočet tam dá bod mřížky (97,0)(97,0) a s ním

(71,0)−(97,0)=(−26,0),∥(−26,0)∥=26.(71,0)-(97,0)=(-26,0), \qquad \|(-26,0)\|=26.

Rovněž platné řešení rovnice — ale sedmkrát delší. Je-li mez pro přijetí nastavena pod 26, je bezcenné.

Stejnyˊ algoritmus, stejnaˊ mrˇıˊzˇka, stejnyˊ cıˊlovyˊ bod.Lisˇıˊ se jen baˊze — a tıˊm i vyˊsledek.\boxed{ \begin{array}{c} \text{Stejný algoritmus, stejná mřížka, stejný cílový bod.}\\ \text{Liší se jen báze — a tím i výsledek.} \end{array}}

To jsou padací dveře FALCONu v jednom řádku.

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

Prohlížeč dostane hodnocení, sůl a s2=2s_2=2. Znovu spočítá hash, obdrží c=71c=71, rekonstruuje

s1=c−s2 h=71−68=3,s_1=c-s_2\,h=71-68=3,

a ověří délku:

∥(3,2)∥=13  ≤  β⟹Podpis je platnyˊ\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Podpis je platný}}

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

Změní-li se text dodatečně, změní se hash obsahu a s ním bod, řekněme

c′=40.c'=40.

Starý podpis zůstává (3,2)(3,2), ale

3+34⋅2=71≠40⟹Podpis je neplatnyˊ3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \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

Ve dvou dimenzích může útočník krátká řešení jednoduše vyzkoušet — pro c′=40c'=40 třeba (6,1)(6,1). Příklad není bezpečný; ukazuje jen mechanismus. U FALCON-1024 má vektor 2048 koeficientů a tam vyzkoušení nevede nikam.

12. Proč se prostě nezaokrouhlí?

Postup z kroku 3 se nazývá Babaiovo zaokrouhlení. Pro učebnicový příklad stačí — pro skutečné podpisové schéma ne.

Důvod: zaokrouhlené podpisy neleží rovnoměrně rozdělené. Jejich tvar závisí na geometrii tajné báze. Z dostatečného množství podpisů by šlo tuto geometrii rekonstruovat — a s ní soukromý klíč. Přesně na tom dřívější mřížková podpisová schémata ztroskotala.

FALCON proto losuje krátké vektory z diskrétního Gaussova rozdělení nad mřížkou:

P(x)∝e−∥x−c∥2/(2σ2).P(x)\propto e^{-\|x-c\|^2/(2\sigma^2)}.

Hodnoty blízko cílového bodu jsou pravděpodobnější, ale která přesně bude zvolena, je náhodné. Výsledkem je rozdělení, které neprozradí nic o použité bázi — matematicky: není odlišitelné od rozdělení, jež závisí jen na samotné mřížce.

Tento sampler je nejnáročnější částí FALCONu. Běží rekurzivně nad stromovou strukturou a pracuje s čísly v plovoucí řádové čárce — což činí implementaci choulostivou a je hlavním důvodem, proč se FALCON správně implementuje hůř než ML-DSA.

13. Co se ve skutečnosti přenáší

Podpis se skládá z

σ=(r,  s2).\sigma=(r,\;s_2).

Jen s2s_2 — ne dvojice. s1s_1 si ověřovatel dopočítá sám:

s1=c−s2 h(modq).s_1=c-s_2\,h \pmod q.

Protože koeficienty s2s_2 jsou malé a rozptylují se kolem nuly, dají se silně komprimovat. To je důvod nápadně kompaktních podpisů FALCONu:

veřejný klíčpodpis
FALCON-512897 B~666 B
FALCON-10241 793 B~1 280 B

Pro srovnání: ML-DSA-87 potřebuje 4 627 bajtů. Na McGesund ovšem žádný z těchto podpisů nevězí v samotném QR kódu — nálepka nese pouze obálku Ed25519; postkvantová razítka leží u datového záznamu a při ověřování se donačtou. Velikost tu tedy nerozhoduje o tisknutelnosti, nýbrž o úložišti a přenosu: razítko FALCON je zhruba čtvrtinové oproti razítku ML-DSA.

14. Proč FALCON ověřuje rychle

Naivní násobení polynomů stojí

O(n2).O(n^2).

S rychlou Fourierovou transformací to klesne přibližně na

O(nlog⁡n).O(n\log n).

Při n=1024n=1024 je to rozdíl mezi milionem a zhruba deseti tisíci operacemi. Proto ověření v prohlížeči návštěvníka proběhne v milisekundách — a proto vězí v názvu ono F:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Průběh v obrázku

PODPISOVÁ SLUŽBA (MCGESUND)PROHLÍŽEČ NÁVŠTĚVNÍKAsoukromý klíč (f, g, F, G — krátká báze)payload m = {firma, hodnocení, h, rh, iat}sůl r + HashToPoint(r ‖ m) = cGaussovo vzorkování: krátký vektor (s₁, s₂)podpis σ = (r, s₂) + kidhodnocení + σ + veřejný klíč hznovu spočítat c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?platnýneplatný
Od payloadu až po zaškrtnutí v prohlížeči. Vše nad dělicí čarou se děje jednou při odeslání, vše pod ní znovu u každého návštěvníka — na jeho zařízení, s veřejným klíčem.

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

Zná hh a s ním celou mřížku. Zná také cílový bod cc, jakmile je hodnocení veřejné. Co mu chybí, je krátká báze.

Aby hodnocení zpadělal, musel by k sebou zvolenému cc najít krátký vektor — jen z veřejného popisu. To je úloha, kterou ilustroval krok 4 příkladu: bez dobrých vektorů skončí týž výpočet u mnohem příliš dlouhého řešení.

V dimenzi 1024 jsou od toho nejlepší známé postupy — klasické i kvantové — daleko.

Podepsaˊnıˊ: rychleˊOveˇrˇenıˊ: rychleˊPadeˇlaˊnıˊ: teˇzˇkeˊ\boxed{\text{Podepsání: rychlé}\quad \text{Ověření: rychlé}\quad \text{Padělání: těžké}}

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

Obálka. Každé podepsané hodnocení nese podpis Ed25519. To je povinná varianta — klasická, velmi malá, nativně ověřitelná v každém prohlížeči.

Postkvantová razítka. Vedle ní leží jeden nebo dva kvantově odolné podpisy. Které, závisí na tarifu:

Tarifdostupné stupně podpisu
BasisEd25519, FN-DSA-512
KlassikEd25519, FN-DSA-512, FN-DSA-1024
ProEd25519, FN-DSA-1024, ML-DSA-87
PremiumEd25519, FN-DSA-1024, ML-DSA-87, obojí souběžně

Souběžná varianta je záměrně redundantní. FALCON stojí na NTRU mřížkách, ML-DSA na modulových mřížkách. Ukázala-li by se jedna z obou rodin slabší, než se dnes předpokládá, nese druhá dál.

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

To vše se počítá v prohlížeči čtenáře, přes modul WASM. My dodáváme data; ověření běží na zařízení návštěvníka. Kdybychom zítra zmizeli ze sítě, jednou načtené hodnocení by zůstalo ověřitelné.

K zařazení názvů: FALCON se v současnosti standardizuje jako FN-DSA; návrh je zamýšlen jako FIPS 206, ale zatím není dokončen. Proto se stupně v kódu McGesund jmenují FN-DSA-512 a FN-DSA-1024, i když se v běžné řeči nadále mluví o FALCONu.

18. Nejdůležitější intuice

Veřejný klíč je úplný popis bludiště. Prohlédnout si ho smí každý.

Podpis je doklad: „Pro přesně toto hodnocení jsem našel velmi krátkou cestu."

Soukromý klíč je znalost zkratek.

Čtenář zkratky znát nemusí. Jen přeměří, zda je předložená cesta skutečně krátká a zda skutečně patří k tomuto hodnocení. Obojí zvládne bez nás.

FALCON promeˇnıˊ hodnocenıˊ v bod v mrˇıˊzˇcea podpis v kraˊtkou cestu k neˇmu.\boxed{ \begin{array}{c} \text{FALCON promění hodnocení v bod v mřížce}\\ \text{a podpis v krátkou cestu k němu.} \end{array}}

Kdo změní text, posune bod — a stará cesta vede do prázdna.