Podpisová schéma

FALCON vysvetlený matematicky

Ako sa hodnotenie McGesund podpisuje pomocou FN-DSA (FALCON) — a prečo jeden zmenený znak podpis zlomí.

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 časť týchto podpisov používame FALCON — presnejšie FN-DSA-512 a FN-DSA-1024. Tento článok vysvetľuje, čo sa pritom matematicky deje.

Dôležité na úvod:

FALCON nie je šifrovanie. Text hodnotenia sa predsa má čítať. FALCON 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 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>",
  "iat": 1757203200
}

To je naša správa mm. Zväzuje dokopy:

  1. ku ktorému podniku hodnotenie patrí (f),
  2. o ktoré hodnotenie ide (c),
  3. aký text za ním stál — ako hašovú hodnotu (h),
  4. aký záznam bol odovzdaný ako celok (rh): text, srdcia, geo-status a údaje o príležitosti, kanonicky serializované a zahašované, vo verzii schémy rv,
  5. z ktorého QR kódu hodnotenie pochádza (qh) — pri hodnotení bez QR toto pole odpadá,
  6. kedy sa podpisovalo (iat).

Jeden zmenený znak v texte hodnotenia túto reťaz zlomí. Presne to je zmyslom — a od zavedenia rh to isté platí pre dodatočne posunuté srdce alebo zmenený geo-status.

3. Základný problém

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

Podpisuje sa súkromným, overuje verejným kľúčom. A to na zariadení čitateľa, nie na našom serveri.

4. Prečo FALCON?

Mnohé dnešné podpisové schémy stoja na problémoch, ktoré sú pre klasické počítače ťažké, pre dostatočne veľké kvantové počítače by sa však mohli stať výrazne ľahšími.

Pri hodnotení je to relevantnejšie než pri prchavej správe: hodnotenie má byť overiteľné aj o päť alebo desať rokov. Kto podpisuje dnes, podpisuje na celú životnosť záznamu.

FALCON preto stojí na mriežkovej kryptografii:

Postaví sa matematicky jednoducho opísateľná mriežka, v ktorej je určitá vyhľadávacia úloha mimoriadne ťažká.

5. Čo je matematická mriežka?

Dva vektory:

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

Všetky celočíselné kombinácie

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

dávajú mriežku bodov. Naprí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 rozopínajú mriežku. Každý bod je celočíselnou kombináciou tých dvoch — vyznačený vzniká z dvojnásobku v₁ a trojnásobku v₂.

Rozhodujúce je:

Samotná mriežka sa opisuje ľahko. Nájsť v nej určité vlastnosti je veľmi ťažké.

6. Tajomstvom sú krátke vektory

Klasická ťažká úloha znie:

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

To je Shortest Vector Problem. V dvoch rozmeroch sa dá vyskúšať všetko. FALCON pracuje v dimenzii 512 alebo 1024 — tam je to beznádejné.

dlhá bázatakmer rovnobežnénajkratší vektor
Tá istá mriežka, dva opisy. Sivé vektory ju generujú tiež, sú však dlhé a takmer rovnobežné — zlá báza. Krátky vektor je to, čo sa hľadá ťažko.

FALCON však nepotrebuje najkratší vektor ako taký, ale niečo príbuzné: k zadanému cieľovému bodu nájsť blízky bod mriežky. Aj to je bez správnej dodatočnej informácie ťažké.

cieľový bod z hodnoteniablízky bod mriežkyďaleko
Cieľový bod z hodnotenia (prázdny krúžok) neleží v mriežke. Hľadá sa bod mriežky tesne vedľa neho — prerušovaná cesta k vzdialenému bodu je tiež riešením prvej podmienky, ale nie je krátka.

7. Polynómy namiesto čísel

FALCON používa NTRU mriežku a počíta s polynómami. Teda namiesto jednotlivých čísel so zoznamami koeficientov:

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číta sa v okruhu

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

To znamená:

  • Zq\mathbb{Z}_q: počítanie modulo qq. Pri q=7q=7 napríklad 10≡310\equiv3, lebo 10−7=310-7=3.
  • xn=−1x^n=-1: udržiava polynómy na pevnej dĺžke.

FALCON konkrétne používa:

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

8. Ústredný trik

Súkromný kľúč pozostáva zo štyroch malých polynómov

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

s NTRU rovnicou

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

Tieto štyri tvoria spolu tajnú, dobromyseľnú bázu mriežky — opis mriežky z krátkych vektorov.

Verejný kľúč je v podstate jediný polynóm:

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

Z hh vyplýva tá istá mriežka, ale v nemotornej báze z dlhých vektorov:

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

To je celé jadro FALCONu. Obe bázy opisujú tú istú mriežku. Len jedna je na počítanie použiteľná a druhá nie.

Dá sa to predstaviť ako plán mesta: verejná je úplná mapa. Tajná je znalosť skratiek.

9. Z hodnotenia sa stáva bod

Skôr než sa podpisuje, prejde objekt payloadu hašovou funkciou. FALCON na to používa hash-to-point: zo správy nevzniká číselná hodnota, ale priamo bod v okruhu.

Podpisová služba navyše ťahá náhodnú soľ rr (320 bitov) a hašuje ju spolu:

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

Soľ nie je ozdoba. Bez nej by to isté hodnotenie dávalo vždy ten istý podpis a z mnohých podpisov by sa dala zrekonštruovať tajná báza. Preto putuje spolu do podpisu.

10. Čo je platný podpis

Hľadá sa dvojica

(s1,s2)(s_1,s_2)

s dvoma vlastnosťami:

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

Prvú podmienku samu osebe je triviálne splniť — stačí položiť s2=0s_2=0 a s1=cs_1=c. Ťažkou robí úlohu až druhá podmienka.

Kraˊtkostˇ je podpisom.\boxed{\text{Krátkosť je podpisom.}}

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

Všetko zmenšíme na hračkársku veľkosť: polynómy s jediným koeficientom, teda obyčajné čísla, a

q=97.q=97.

Tajný kľúč. Dve malé čísla:

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

Verejný kľúč. Platí 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, lebo 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Teda:

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

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

Verejná báza vyplýva priamo z hh:

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

Obe ležia v LL — a obe sú dlhé.

Tajnú bázu pozná len podpisová služba:

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

lebo −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 rovnica teda vychádza. Oba vektory sú krátke.

Krok 1: Zahašovať hodnotenie

Predpokladajme, že objekt payloadu hodnotenia dá

c=71.c=71.

Krok 2: Prvé, zlé riešenie

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

spĺňa 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Dĺžka je však 7171 — priveľa.

Krok 3: Skrátiť pomocou tajnej bázy

Podpisová služba vyjadrí cieľový bod vo svojej krátkej báze:

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

To vedie na a≈−10,25a\approx-10{,}25 a b≈−2,20b\approx-2{,}20. Po zaokrúhlení na a=−10a=-10, b=−2b=-2 vzniká bod mriež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, teda skutočne v LL. Odčítanie:

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

Dĺžka:

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

To je podpis.

Krok 4: Ten istý postup s verejnou bázou

Kto pozná len h=34h=34, má bázu {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Ten istý zaokrúhľovací výpočet dá bod mriežky (97,0)(97,0) a tým

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

Takisto platné riešenie rovnice — ale sedemkrát dlhšie. Ak sa hranica prijatia nastaví pod 26, je bezcenné.

Rovnakyˊ algoritmus, rovnakaˊ mriezˇka, rovnakyˊ cielˇovyˊ bod.Lıˊsˇi sa iba baˊza — a tyˊm aj vyˊsledok.\boxed{ \begin{array}{c} \text{Rovnaký algoritmus, rovnaká mriežka, rovnaký cieľový bod.}\\ \text{Líši sa iba báza — a tým aj výsledok.} \end{array}}

To sú padacie dvierka FALCONu v jednom riadku.

Krok 5: Prehliadač overuje

Prehliadač dostane hodnotenie, soľ a s2=2s_2=2. Nanovo vypočíta haš, dostane c=71c=71, zrekonštruuje

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

a overí dĺžku:

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

Krok 6: Niekto zmení text hodnotenia

Ak sa text dodatočne zmení, zmení sa haš obsahu a tým aj bod, povedzme na

c′=40.c'=40.

Starý podpis zostáva (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ý}}

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

Poznámka o poctivosti príkladu

V dvoch rozmeroch dokáže útočník krátke riešenia jednoducho vyskúšať — pre c′=40c'=40 napríklad (6,1)(6,1). Príklad nie je bezpečný; ukazuje len mechanizmus. Pri FALCON-1024 má vektor 2048 koeficientov a tam skúšanie nevedie nikam.

12. Prečo sa jednoducho nezaokrúhľuje?

Postup z kroku 3 sa nazýva Babaiovo zaokrúhľovanie. Pre učebnicový príklad postačuje — pre skutočnú podpisovú schému nie.

Dôvod: zaokrúhlené podpisy nie sú rozdelené rovnomerne. Ich tvar závisí od geometrie tajnej bázy. Z dostatočného množstva podpisov by sa táto geometria dala zrekonštruovať — a tým aj súkromný kľúč. Práve na tom stroskotali skoršie mriežkové podpisové schémy.

FALCON preto ťahá krátke vektory z diskrétneho Gaussovho rozdelenia nad mriežkou:

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

Hodnoty blízko cieľového bodu sú pravdepodobnejšie, ale ktorá presne sa zvolí, je náhodné. Výsledkom je rozdelenie, ktoré neprezrádza nič o použitej báze — matematicky: nedá sa odlíšiť od rozdelenia, ktoré závisí len od samotnej mriežky.

Tento sampler je najnáročnejšou časťou FALCONu. Beží rekurzívne nad stromovou štruktúrou a pracuje s číslami s pohyblivou rádovou čiarkou — čo robí implementáciu chúlostivou a je hlavným dôvodom, prečo sa FALCON správne implementuje ťažšie než ML-DSA.

13. Čo sa skutočne prenáša

Podpis pozostáva z

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

Len s2s_2 — nie celá dvojica. s1s_1 si overovateľ dopočíta sám:

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

Keďže koeficienty s2s_2 sú malé a rozptýlené okolo nuly, dajú sa silno komprimovať. To je dôvod nápadne kompaktných podpisov FALCONu:

verejný kľúčpodpis
FALCON-512897 B~666 B
FALCON-10241 793 B~1 280 B

Pre porovnanie: ML-DSA-87 potrebuje 4 627 bajtov. Na McGesund však ani jeden z týchto podpisov nie je v samotnom QR kóde — nálepka nesie len obálku Ed25519; postkvantové pečiatky ležia pri zázname a pri overovaní sa donačítajú. Veľkosť tu teda nerozhoduje o tlačiteľnosti, ale o úložisku a prenose: pečiatka FALCON je dobrú štvrtinu veľkosti pečiatky ML-DSA.

14. Prečo FALCON overuje rýchlo

Naivné násobenie polynómov stojí

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

S rýchlou Fourierovou transformáciou to klesá približne na

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

Pri n=1024n=1024 je to rozdiel medzi miliónom a približne desiatimi tisícmi operácií. Preto overenie v prehliadači návštevníka beží v milisekundách — a preto väzí F v názve:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Priebeh v obraze

PODPISOVÁ SLUŽBA (MCGESUND)PREHLIADAČ NÁVŠTEVNÍKAsúkromný kľúč (f, g, F, G — krátka báza)payload m = {firma, hodnotenie, h, rh, iat}soľ r + HashToPoint(r ‖ m) = cGaussovo vzorkovanie: krátky vektor (s₁, s₂)podpis σ = (r, s₂) + kidhodnotenie + σ + verejný kľúč hprepočítať c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?platnýneplatný
Od payloadu až po potvrdzujúcu fajku v prehliadači. Všetko nad deliacou čiarou sa deje raz pri odoslaní, všetko pod ňou nanovo u každého návštevníka — na jeho zariadení, s verejným kľúčom.

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

Pozná hh a tým celú mriežku. Pozná aj cieľový bod cc, len čo je hodnotenie verejné. Chýba mu krátka báza.

Aby hodnotenie sfalšoval, musel by k vlastnému zvolenému cc nájsť krátky vektor — len z verejného opisu. To je úloha, ktorú ilustroval krok 4 príkladu: bez dobrých vektorov skončí ten istý výpočet pri príliš dlhom riešení.

V dimenzii 1024 sú od toho najlepšie známe postupy — klasické aj kvantové — veľmi ďaleko.

Podpis: ryˊchlyOverenie: ryˊchleFalsˇovanie: tˇazˇkeˊ\boxed{\text{Podpis: rýchly}\quad \text{Overenie: rýchle}\quad \text{Falšovanie: ťažké}}

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

Obálka. Každé podpísané hodnotenie nesie podpis Ed25519. To je povinný variant — klasický, veľmi malý, natívne overiteľný v každom prehliadači.

Postkvantové pečiatky. Vedľa neho ležia jeden alebo dva kvantovo odolné podpisy. Ktoré, závisí od tarifu:

Tarifdostupné stupne 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, oba súbežne

Súbežný variant je zámerne redundantný. FALCON stojí na NTRU mriežkach, ML-DSA na modulových mriežkach. Ak by sa jedna z týchto dvoch rodín ukázala slabšia, než sa dnes predpokladá, druhá nesie ďalej.

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

Všetko sa to počíta v prehliadači čitateľa, cez modul WASM. My dodávame údaje; overenie beží na zariadení návštevníka. Keby sme zajtra zmizli zo siete, raz načítané hodnotenie zostane overiteľné.

K zaradeniu názvov: FALCON sa v súčasnosti štandardizuje ako FN-DSA; návrh je plánovaný ako FIPS 206, ale zatiaľ nie je uzavretý. Preto sa stupne v kóde McGesund volajú FN-DSA-512 a FN-DSA-1024, aj keď sa v bežnej reči naďalej hovorí o FALCONe.

18. Najdôležitejšia intuícia

Verejný kľúč je úplný opis labyrintu. Pozrieť si ho smie každý.

Podpis je dôkaz: „Práve pre toto hodnotenie som našiel veľmi krátku cestu."

Súkromný kľúč je znalosť skratiek.

Čitateľ skratky poznať nemusí. Len premeria, či je predložená cesta skutočne krátka a či skutočne patrí k tomuto hodnoteniu. Oboje dokáže bez nás.

FALCON premienˇa hodnotenie na bod v mriezˇkea podpis na kraˊtku cestu k nemu.\boxed{ \begin{array}{c} \text{FALCON premieňa hodnotenie na bod v mriežke}\\ \text{a podpis na krátku cestu k nemu.} \end{array}}

Kto zmení text, posunie bod — a stará cesta vedie do prázdna.