Podpisni postopek

FALCON matematično pojasnjen

Kako se ocena na McGesund podpiše s FN-DSA (FALCON) — in zakaj spremenjen znak zlomi podpis.

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 del teh podpisov uporabljamo FALCON — natančneje FN-DSA-512 in FN-DSA-1024. Ta prispevek pojasnjuje, kaj se pri tem dogaja matematično.

Pomembno takoj na začetku:

FALCON ni šifriranje. Besedilo ocene naj bo vendar prebrano. FALCON 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 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>",
  "iat": 1757203200
}

To je naše sporočilo mm. Skupaj veže:

  1. h kateremu podjetju ocena spada (f),
  2. za katero oceno gre (c),
  3. katero besedilo je bilo za tem — kot zgoščena vrednost (h),
  4. kateri zapis je bil oddan v celoti (rh): besedilo, srca, geo status in navedbe o povodu, kanonično serializirani in zgoščeni, v shemski različici rv,
  5. iz katere kode QR ocena izvira (qh) — pri oceni brez QR to polje odpade,
  6. kdaj je bil podpis izdan (iat).

Spremenjen znak v besedilu ocene zlomi to verigo. Prav to je namen — in od rh naprej velja isto za naknadno premaknjeno srce ali spremenjen geo status.

3. Temeljni problem

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

Podpisuje se z zasebnim, preverja z javnim ključem. In sicer na napravi bralca, ne na našem strežniku.

4. Zakaj FALCON?

Mnogi današnji podpisni postopki temeljijo na problemih, ki so za klasične računalnike težki, za dovolj velike kvantne računalnike pa bi lahko postali občutno lažji.

Pri oceni je to bolj pomembno kot pri bežnem sporočilu: ocena naj bo preverljiva še čez pet ali deset let. Kdor podpiše danes, podpiše za celotno življenjsko dobo vnosa.

FALCON zato temelji na mrežni kriptografiji:

Zgradi se matematično preprosto opisljiva mreža, v kateri je določena iskalna naloga izjemno težka.

5. Kaj je matematična mreža?

Dva vektorja:

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

Vse celoštevilske kombinacije

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

dajo mrežo točk. Na primer:

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 vektorja razpenjata mrežo. Vsaka točka je celoštevilska kombinacija obeh — označena nastane iz dvakratnega v₁ in trikratnega v₂.

Odločilno je:

Mrežo samo je lahko opisati. Najti v njej določene lastnosti je zelo težko.

6. Skrivnost so kratki vektorji

Klasična težka naloga se glasi:

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

To je problem najkrajšega vektorja. V dveh dimenzijah ga je mogoče rešiti s preizkušanjem. FALCON dela v dimenziji 512 ali 1024 — tam je to brezupno.

dolga bazaskoraj vzporednanajkrajši vektor
Ista mreža, dva opisa. Sivi vektorji jo prav tako generirajo, a so dolgi in skoraj vzporedni — slaba baza. Kratek vektor je tisto, kar je težko najti.

FALCON pa ne potrebuje najkrajšega vektorja kot takega, temveč nekaj sorodnega: k vnaprej dani ciljni točki najti bližnjo točko mreže. Tudi to je brez pravih dodatnih informacij težko.

ciljna točka iz ocenebližnja točka mrežedaleč stran
Ciljna točka iz ocene (votli krog) ne leži v mreži. Iskana je točka mreže tesno ob njej — črtkana pot do daljne točke je prav tako rešitev prvega pogoja, a pač ne kratka.

7. Polinomi namesto števil

FALCON uporablja mrežo NTRU in računa s polinomi. Namesto s posameznimi števili torej s seznami 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.

Računa se v kolobarju

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

To pomeni:

  • Zq\mathbb{Z}_q: računanje po modulu qq. Pri q=7q=7 na primer 10≡310\equiv3, saj je 10−7=310-7=3.
  • xn=−1x^n=-1: ohranja polinome na stalni dolžini.

FALCON konkretno uporablja:

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

8. Osrednji trik

Zasebni ključ sestavljajo štirje majhni polinomi

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

z enačbo NTRU

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

Ti štirje skupaj tvorijo skrivno, dobrohotno bazo mreže — opis mreže iz kratkih vektorjev.

Javni ključ je v bistvu en sam polinom:

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

Iz hh sledi ista mreža, a v neokretni bazi iz dolgih vektorjev:

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

To je celotno jedro FALCON. Obe bazi opisujeta isto mrežo. Le da je ena za računanje uporabna, druga pa ne.

Predstavljati si je mogoče kot mestni načrt: javen je celoten zemljevid. Skrivno je poznavanje bližnjic.

9. Ocena postane točka

Preden se podpiše, gre objekt payload skozi zgoščevalno funkcijo. FALCON za to uporablja hash-to-point: iz sporočila ne nastane številska vrednost, temveč neposredno točka v kolobarju.

Podpisna storitev poleg tega izvleče naključno sol rr (320 bitov) in jo sozgošča:

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

Sol ni okrasek. Brez nje bi ista ocena vedno dala isti podpis in iz mnogih podpisov bi bilo mogoče rekonstruirati skrivno bazo. Zato potuje s podpisom vred.

10. Kaj je veljaven podpis

Iskan je par

(s1,s2)(s_1,s_2)

z dvema lastnostma:

s1+s2 h≡c(modq)in∥(s1,s2)∥  majhna.s_1+s_2\,h\equiv c \pmod q \qquad\text{in}\qquad \|(s_1,s_2)\|\;\text{majhna}.

Prvi pogoj sam je trivialno izpolniti — postavi se s2=0s_2=0 in s1=cs_1=c. Drugi pogoj naredi nalogo težko.

Kratkost je podpis.\boxed{\text{Kratkost je podpis.}}

11. V celoti izračunan mini primer

Vse skrčimo na igračno velikost: polinomi z le enim koeficientom, torej navadna števila, in

q=97.q=97.

Skrivni ključ. Dve majhni števili:

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

Javni ključ. Velja 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, saj je 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Torej:

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

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

Javna baza sledi neposredno iz hh:

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

Oba ležita v LL — in oba sta dolga.

Skrivno bazo pozna le podpisna storitev:

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

saj je −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 in −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Determinanta je

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

enačba NTRU torej izide. Oba vektorja sta kratka.

Korak 1: Zgoščevanje ocene

Recimo, da objekt payload ocene da

c=71.c=71.

Korak 2: Prva, slaba rešitev

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

izpolnjuje 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Toda dolžina je 7171 — daleč predolga.

Korak 3: Krajšanje s skrivno bazo

Podpisna storitev izrazi ciljno točko v svoji kratki bazi:

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

To vodi na a≈−10,25a\approx-10{,}25 in b≈−2,20b\approx-2{,}20. Zaokroženo na a=−10a=-10, b=−2b=-2 sledi točka mreže

−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, torej dejansko v LL. Odštevanje:

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

Dolžina:

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

To je podpis.

Korak 4: Isti postopek z javno bazo

Kdor pozna le h=34h=34, ima bazo {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Isti zaokroževalni račun tam da točko mreže (97,0)(97,0) in s tem

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

Prav tako veljavna rešitev enačbe — a sedemkrat daljša. Če je meja sprejema postavljena pod 26, je brez vrednosti.

Enak algoritem, enaka mrezˇa, enaka ciljna tocˇka.Razlikuje se le baza — in s tem rezultat.\boxed{ \begin{array}{c} \text{Enak algoritem, enaka mreža, enaka ciljna točka.}\\ \text{Razlikuje se le baza — in s tem rezultat.} \end{array}}

To je skrivna vrata FALCON v eni vrstici.

Korak 5: Brskalnik preverja

Brskalnik dobi oceno, sol in s2=2s_2=2. Na novo izračuna zgoščeno vrednost, dobi c=71c=71, rekonstruira

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

in preveri dolžino:

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

Korak 6: Nekdo spremeni besedilo ocene

Če se besedilo naknadno spremeni, se spremeni zgoščena vrednost vsebine in s tem točka, recimo

c′=40.c'=40.

Stari podpis ostane (3,2)(3,2), toda

3+34⋅2=71≠40⟹Podpis neveljaven3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Podpis neveljaven}}

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

Pošteno opozorilo k primeru

V dveh dimenzijah lahko napadalec kratke rešitve preprosto preizkusi — za c′=40c'=40 na primer (6,1)(6,1). Primer ni varen; kaže le mehanizem. Pri FALCON-1024 ima vektor 2048 koeficientov in tam preizkušanje ne vodi nikamor.

12. Zakaj se ne zaokroži kar tako?

Postopek iz koraka 3 se imenuje Babaijevo zaokroževanje. Za učbeniški primer zadošča — za resničen podpisni postopek ne.

Razlog: zaokroženi podpisi niso enakomerno porazdeljeni. Njihova oblika je odvisna od geometrije skrivne baze. Iz dovolj velikega števila podpisov bi bilo to geometrijo mogoče rekonstruirati — in s tem zasebni ključ. Prav na tem so prejšnji mrežni podpisni postopki propadli.

FALCON zato kratke vektorje izvleče iz diskretne Gaussove porazdelitve nad mrežo:

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

Vrednosti blizu ciljne točke so verjetnejše, a katera natanko bo izbrana, je naključno. Rezultat je porazdelitev, ki o uporabljeni bazi ne izda ničesar — matematično: ni razločljiva od porazdelitve, ki je odvisna le od mreže same.

Ta vzorčevalnik je najzahtevnejši del FALCON. Teče rekurzivno po drevesni strukturi in dela s števili s plavajočo vejico — kar naredi implementacijo občutljivo in je glavni razlog, da je FALCON teže pravilno izvesti kot ML-DSA.

13. Kaj se dejansko prenaša

Podpis sestavlja

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

Le s2s_2 — ne par. Vrednost s1s_1 preveritelj izračuna sam:

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

Ker so koeficienti s2s_2 majhni in razpršeni okoli ničle, jih je mogoče močno stisniti. To je razlog za izstopajoče kompaktne podpise FALCON:

javni ključpodpis
FALCON-512897 B~666 B
FALCON-10241.793 B~1.280 B

Za primerjavo: ML-DSA-87 potrebuje 4.627 bajtov. Pri McGesund pa noben od teh podpisov ne tiči v sami kodi QR — nalepka nosi le ovojnico Ed25519; postkvantni žigi ležijo ob zapisu in se ob preverjanju dodatno naložijo. Velikost tu torej ne odloča o možnosti tiskanja, temveč o pomnilniku in prenosu: žig FALCON je dobro četrtino velikosti žiga ML-DSA.

14. Zakaj FALCON hitro preverja

Naivno množenje polinomov stane

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

S hitro Fourierjevo transformacijo to pade na približno

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

Pri n=1024n=1024 je to razlika med milijonom in okoli deset tisoč operacijami. Zato preverjanje v brskalniku obiskovalca teče v milisekundah — in zato tiči F v imenu:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Potek v sliki

PODPISNA STORITEV (MCGESUND)BRSKALNIK OBISKOVALCAzasebni ključ (f, g, F, G — kratka baza)payload m = {podjetje, ocena, h, rh, iat}sol r + HashToPoint(r ‖ m) = cGaussovo vzorčenje: kratek vektor (s₁, s₂)podpis σ = (r, s₂) + kidocena + σ + javni ključ hponovni izračun c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?veljavenneveljaven
Od payloada do kljukice v brskalniku. Vse nad ločnico se zgodi enkrat ob oddaji, vse pod njo pri vsakem obiskovalcu na novo — na njegovi napravi, z javnim ključem.

16. Zakaj napadalec propade

Pozna hh in s tem celotno mrežo. Pozna tudi ciljno točko cc, takoj ko je ocena javna. Manjka mu kratka baza.

Da bi ponaredil oceno, bi moral k sam izbranemu cc najti kratek vektor — zgolj iz javnega opisa. To je naloga, ki jo je ponazoril korak 4 primera: brez dobrih vektorjev isti račun pristane pri veliko predolgi rešitvi.

V dimenziji 1024 so najboljši znani postopki — klasični in kvantni — od tega daleč.

Podpisovanje: hitroPreverjanje: hitroPonarejanje: tezˇko\boxed{\text{Podpisovanje: hitro}\quad \text{Preverjanje: hitro}\quad \text{Ponarejanje: težko}}

17. Kaj McGesund konkretno počne s tem

Ovojnica. Vsaka podpisana ocena nosi podpis Ed25519. To je obvezna različica — klasična, zelo majhna, izvorno preverljiva v vsakem brskalniku.

Postkvantni žigi. Ob njej ležita en ali dva kvantno odporna podpisa. Katera, je odvisno od paketa:

Paketrazpoložljive stopnje podpisa
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 vzporedno

Vzporedna različica je namenoma redundantna. FALCON stoji na mrežah NTRU, ML-DSA na modulnih mrežah. Če bi se ena od obeh družin izkazala za šibkejšo, kot se domneva danes, nosi druga naprej.

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

Vse to se računa v brskalniku bralca, prek modula WASM. Mi dostavimo podatke; preverjanje teče na napravi obiskovalca. Če bi jutri odšli z omrežja, bi enkrat naložena ocena ostala preverljiva.

K umestitvi imen: FALCON se trenutno standardizira kot FN-DSA; osnutek je predviden kot FIPS 206, a še ni dokončan. Zato se stopnje v kodi McGesund imenujejo FN-DSA-512 in FN-DSA-1024, čeprav se v govoru še naprej govori o FALCON.

18. Najpomembnejša intuicija

Javni ključ je celoten opis labirinta. Vsak si ga sme ogledati.

Podpis je dokazilo: „Za natanko to oceno sem našel zelo kratko pot."

Zasebni ključ je poznavanje bližnjic.

Bralcu bližnjic ni treba poznati. Le izmeri, ali je predložena pot dejansko kratka in ali dejansko spada k tej oceni. Oboje zmore brez nas.

FALCON spremeni oceno v tocˇko v mrezˇiin podpis v kratko pot do nje.\boxed{ \begin{array}{c} \text{FALCON spremeni oceno v točko v mreži}\\ \text{in podpis v kratko pot do nje.} \end{array}}

Kdor spremeni besedilo, premakne točko — in stara pot vodi v prazno.