Postupak potpisivanja

FALCON matematički objašnjen

Kako se McGesund recenzija potpisuje s FN-DSA (FALCON) — i zašto jedan izmijenjeni znak lomi potpis.

Stanje: 2026-09-07

1. O čemu je riječ

Recenzija na McGesundu nije tekstualno polje u bazi podataka kojemu se mora vjerovati. Pri slanju se digitalno potpisuje, a svaki posjetitelj taj potpis može kasnije preračunati u vlastitom pregledniku.

Za dio tih potpisa koristimo FALCON — točnije FN-DSA-512 i FN-DSA-1024. Ovaj članak objašnjava što se pritom matematički događa.

Važno unaprijed:

FALCON nije šifriranje. Tekst recenzije se ionako treba čitati. FALCON ne dokazuje tajnost, nego podrijetlo i cjelovitost.

2. Što se točno potpisuje

Ne potpisuje se tekući tekst, nego kompaktan podatkovni objekt koji tekst jednoznačno prikiva:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID tvrtke>",
  "c":   "<ID recenzije>",
  "h":   "<SHA-256 teksta recenzije>",
  "rh":  "<SHA-256 cijelog zapisa o predaji>",
  "rv":  1,
  "qh":  "<SHA-256 QR omotnice, samo kod QR recenzija>",
  "iat": 1757203200
}

To je naša poruka mm. Ona zajedno veže:

  1. kojem poduzeću recenzija pripada (f),
  2. o kojoj je recenziji riječ (c),
  3. koji je tekst iza toga stajao — kao hash-vrijednost (h),
  4. koji je zapis ukupno predan (rh): tekst, srca, geo-status i podaci o povodu, kanonski serijalizirani i uhashirani, u verziji sheme rv,
  5. iz kojeg QR koda recenzija potječe (qh) — kod recenzije bez QR-a to polje otpada,
  6. kada je potpisano (iat).

Jedan izmijenjeni znak u tekstu recenzije lomi taj lanac. Upravo je to svrha — a otkad postoji rh, isto vrijedi za naknadno pomaknuto srce ili izmijenjeni geo-status.

3. Osnovni problem

Čitatelj koji dođe na profil poduzeća pred dva je pitanja:

  1. Potječe li ova recenzija doista iz McGesund sustava?
  2. Je li naknadno izmijenjena?

Za to postoji par ključeva:

  • privatni ključ — ostaje u servisu za potpisivanje
  • javni ključ — smije ga imati svatko

Potpisuje se privatnim, provjerava javnim ključem. I to na uređaju čitatelja, a ne na našem poslužitelju.

4. Zašto FALCON?

Mnogi današnji postupci potpisivanja počivaju na problemima koji su za klasična računala teški, ali bi za dovoljno velika kvantna računala mogli postati znatno lakši.

Kod recenzije je to važnije nego kod prolazne poruke: recenzija bi za pet ili deset godina još trebala biti provjerljiva. Tko danas potpisuje, potpisuje za cijeli životni vijek unosa.

FALCON zato počiva na kriptografiji rešetki:

Gradi se matematički jednostavno opisiva rešetka u kojoj je jedan određeni zadatak pretraživanja iznimno težak.

5. Što je matematička rešetka?

Dva vektora:

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

Sve cjelobrojne kombinacije

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

daju rešetku od točaka. Na primjer:

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 vektora razapinju rešetku. Svaka je točka cjelobrojna kombinacija tih dvaju — označena nastaje iz dvaput v₁ i triput v₂.

Bitno je:

Samu rešetku lako je opisati. Naći određena svojstva u njoj vrlo je teško.

6. Tajna su kratki vektori

Klasični teški zadatak glasi:

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

To je Shortest Vector Problem. U dvije se dimenzije može isprobati. FALCON radi u dimenziji 512 ili 1024 — ondje je to bezizgledno.

duga bazagotovo paralelninajkraći vektor
Ista rešetka, dva opisa. Sivi je vektori također generiraju, ali su dugi i gotovo paralelni — loša baza. Kratki je vektor ono što je teško pronaći.

FALCON-u, doduše, ne treba najkraći vektor kao takav, nego nešto srodno: uz zadanu ciljnu točku pronaći blisku točku rešetke. I to je bez prave dodatne informacije teško.

ciljna točka iz recenzijebliska točka rešetkedaleko
Ciljna točka iz recenzije (šuplji krug) ne leži u rešetki. Traži se točka rešetke tik uz nju — isprekidani put do udaljene točke također je rješenje prvog uvjeta, ali nije kratak.

7. Polinomi umjesto brojeva

FALCON koristi NTRU rešetku i računa s polinomima. Dakle ne s pojedinačnim brojevima, nego s listama koeficijenata:

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 u prstenu

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

To znači:

  • Zq\mathbb{Z}_q: računanje modulo qq. Pri q=7q=7 primjerice 10≡310\equiv3, jer je 10−7=310-7=3.
  • xn=−1x^n=-1: drži polinome na čvrstoj duljini.

FALCON konkretno koristi:

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

8. Ključni trik

Privatni se ključ sastoji od četiriju malih polinoma

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

s NTRU jednadžbom

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

Ta četiri zajedno tvore tajnu, dobroćudnu bazu rešetke — opis rešetke sastavljen od kratkih vektora.

Javni je ključ u biti jedan jedini polinom:

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

Iz hh proizlazi ista rešetka, ali u nezgrapnoj bazi od dugih vektora:

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

To je cijela jezgra FALCON-a. Obje baze opisuju istu rešetku. Samo je jedna upotrebljiva za računanje, a druga nije.

Može se to zamisliti kao plan grada: javna je potpuna karta. Tajno je poznavanje prečica.

9. Recenzija postaje točka

Prije potpisivanja objekt payloada prolazi kroz hash-funkciju. FALCON za to koristi Hash-to-Point: iz poruke ne nastaje brojčana vrijednost, nego izravno točka u prstenu.

Servis za potpisivanje dodatno izvlači slučajnu sol rr (320 bitova) i uhashira je zajedno:

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

Sol nije ukras. Bez nje bi ista recenzija uvijek davala isti potpis, a iz mnogo bi se potpisa dala rekonstruirati tajna baza. Zato putuje zajedno u potpisu.

10. Što je valjan potpis

Traži se par

(s1,s2)(s_1,s_2)

s dva svojstva:

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

Prvi je uvjet sam po sebi trivijalno ispuniti — postavi se s2=0s_2=0 i s1=cs_1=c. Drugi uvjet čini zadatak teškim.

Kratkocˊa je potpis.\boxed{\text{Kratkoća je potpis.}}

11. Do kraja izračunat mini-primjer

Sve smanjujemo na igračku veličinu: polinomi sa samo jednim koeficijentom, dakle obični brojevi, i

q=97.q=97.

Tajni ključ. Dva mala broja:

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

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

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

Rešetka. L={(s1,s2):s1+34 s2≡0(mod97)}L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}.

Javna baza proizlazi izravno iz hh:

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

Oba leže u LL — i oba su duga.

Tajnu bazu zna samo servis za potpisivanje:

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

jer je −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 i −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,

NTRU jednadžba dakle vrijedi. Oba su vektora kratka.

Korak 1: Uhashirati recenziju

Pretpostavimo da objekt payloada recenzije daje

c=71.c=71.

Korak 2: Prvo, loše rješenje

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

zadovoljava 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Ali duljina je 7171 — mnogo predugo.

Korak 3: Skratiti tajnom bazom

Servis za potpisivanje izražava ciljnu točku u svojoj kratkoj 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 i b≈−2,20b\approx-2{,}20. Zaokruženo na a=−10a=-10, b=−2b=-2 dobiva se točka rešetke

−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, dakle doista u LL. Oduzimanje:

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

Duljina:

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

To je potpis.

Korak 4: Isti postupak s javnom bazom

Tko zna samo h=34h=34, ima bazu {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Isti račun sa zaokruživanjem ondje daje točku rešetke (97,0)(97,0) i time

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

Također valjano rješenje jednadžbe — ali sedam puta duže. Postavi li se granica prihvaćanja ispod 26, ono je bezvrijedno.

Isti algoritam, ista resˇetka, ista ciljna tocˇka.Razlikuje se samo baza — a time i rezultat.\boxed{ \begin{array}{c} \text{Isti algoritam, ista rešetka, ista ciljna točka.}\\ \text{Razlikuje se samo baza — a time i rezultat.} \end{array}}

To su FALCON-ova skrivena vrata u jednom retku.

Korak 5: Preglednik provjerava

Preglednik dobiva recenziju, sol i s2=2s_2=2. On iznova izračuna hash, dobiva c=71c=71, rekonstruira

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

i provjerava duljinu:

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

Korak 6: Netko mijenja tekst recenzije

Izmijeni li se tekst naknadno, mijenja se hash sadržaja, a time i točka, recimo

c′=40.c'=40.

Stari potpis ostaje (3,2)(3,2), ali

3+34⋅2=71≠40⟹Potpis nije valjan3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Potpis nije valjan}}

Recenziju možemo obrisati. Izmijeniti je ne možemo a da se to ne primijeti.

Iskrena napomena uz primjer

U dvije dimenzije napadač kratka rješenja može naprosto isprobati — za c′=40c'=40 primjerice (6,1)(6,1). Primjer nije siguran; on samo pokazuje mehanizam. Kod FALCON-1024 vektor ima 2048 koeficijenata, a ondje isprobavanje ne vodi nikamo.

12. Zašto se ne zaokružuje jednostavno?

Postupak iz koraka 3 zove se Babaijevo zaokruživanje. Za školski je primjer dovoljan — za pravi postupak potpisivanja nije.

Razlog: zaokruženi potpisi nisu ravnomjerno raspoređeni. Njihov oblik ovisi o geometriji tajne baze. Iz dovoljno bi se potpisa ta geometrija dala rekonstruirati — a time i privatni ključ. Upravo su na tome propali raniji postupci potpisivanja utemeljeni na rešetkama.

FALCON zato kratke vektore izvlači iz diskretne Gaussove razdiobe nad rešetkom:

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

Vrijednosti blizu ciljne točke vjerojatnije su, ali koja se točno odabere, slučajno je. Rezultat je razdioba koja ništa ne odaje o korištenoj bazi — matematički: nije razlučiva od razdiobe koja ovisi samo o samoj rešetki.

Taj je sampler najzahtjevniji dio FALCON-a. Radi rekurzivno nad strukturom stabla i barata brojevima s pomičnim zarezom — što implementaciju čini osjetljivom i glavni je razlog zašto je FALCON teže ispravno izvesti nego ML-DSA.

13. Što se zapravo prenosi

Potpis se sastoji od

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

Samo s2s_2 — ne par. Vrijednost s1s_1 provjeritelj izračuna sam:

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

Budući da su koeficijenti od s2s_2 mali i rasipaju se oko nule, daju se snažno komprimirati. To je razlog FALCON-ovih upadljivo kompaktnih potpisa:

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

Za usporedbu: ML-DSA-87 treba 4.627 bajtova. Na McGesundu, doduše, nijedan od tih potpisa nije u samom QR kodu — naljepnica nosi samo Ed25519 omotnicu; PQ pečati leže uz zapis i dohvaćaju se pri provjeri. Veličina ovdje dakle ne odlučuje o mogućnosti ispisa, nego o pohrani i prijenosu: FALCON pečat velik je otprilike četvrtinu ML-DSA pečata.

14. Zašto FALCON brzo provjerava

Naivno množenje polinoma stoji

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

S brzom Fourierovom transformacijom to pada na otprilike

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

Pri n=1024n=1024 to je razlika između milijun i oko deset tisuća operacija. Zato provjera u pregledniku posjetitelja teče u milisekundama — i zato u imenu stoji slovo F:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Tijek postupka na slici

SERVIS ZA POTPISIVANJE (MCGESUND)PREGLEDNIK POSJETITELJAprivatni ključ (f, g, F, G — kratka baza)Payload m = {tvrtka, recenzija, h, rh, iat}sol r + HashToPoint(r ‖ m) = cGaussovo uzorkovanje: kratki vektor (s₁, s₂)potpis σ = (r, s₂) + kidrecenzija + σ + javni ključ hponovno izračunati c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?valjannevaljan
Od payloada do kvačice u pregledniku. Sve iznad razdjelne crte događa se jednom pri slanju, sve ispod nje kod svakog posjetitelja iznova — na njegovu uređaju, s javnim ključem.

16. Zašto napadač ne uspijeva

On zna hh, a time i cijelu rešetku. Zna i ciljnu točku cc, čim je recenzija javna. Nedostaje mu kratka baza.

Da bi krivotvorio recenziju, morao bi uz samostalno odabrani cc pronaći kratak vektor — i to samo iz javnog opisa. To je zadatak koji je ilustrirao korak 4 primjera: bez dobrih vektora isti račun završava kod predugog rješenja.

U dimenziji 1024 najbolji poznati postupci — klasični kao i kvantni — daleko su od toga.

Potpisivanje: brzoProvjera: brzaKrivotvorenje: tesˇko\boxed{\text{Potpisivanje: brzo}\quad \text{Provjera: brza}\quad \text{Krivotvorenje: teško}}

17. Što McGesund konkretno radi s time

Envelope. Svaka potpisana recenzija nosi Ed25519 potpis. To je obavezna varijanta — klasična, vrlo malena, nativno provjerljiva u svakom pregledniku.

Post-kvantni pečati. Uz nju stoje jedan ili dva kvantno otporna potpisa. Koji, ovisi o tarifi:

Tarifadostupne razine potpisa
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 usporedno

Usporedna je varijanta namjerno redundantna. FALCON stoji na NTRU rešetkama, ML-DSA na Module rešetkama. Pokaže li se jedna od dviju obitelji slabijom nego što se danas pretpostavlja, druga nosi dalje.

Vremensko sidro. Otisak ključa za potpisivanje sidri se preko OpenTimestampsa u jednom Bitcoin bloku. Time je dokazano ne samo da je potpis pravi, nego i da je u određenom trenutku već postojao — a da pritom nitko ne mora vjerovati našem vremenskom žigu.

Sve se to računa u pregledniku čitatelja, preko WASM modula. Mi isporučujemo podatke; provjera teče na uređaju posjetitelja. Kad bismo sutra nestali s mreže, jednom učitana recenzija ostala bi provjerljiva.

O razvrstavanju naziva: FALCON se trenutačno standardizira kao FN-DSA; nacrt je predviđen kao FIPS 206, ali još nije dovršen. Zato se razine u McGesund kodu zovu FN-DSA-512 i FN-DSA-1024, i onda kada se u govoru i dalje spominje FALCON.

18. Najvažnija intuicija

Javni ključ je potpun opis labirinta. Svatko ga smije pogledati.

Potpis je dokaz: „Za točno ovu recenziju pronašao sam vrlo kratak put."

Privatni ključ je poznavanje prečica.

Čitatelj prečice ne mora poznavati. On samo izmjeri je li predočeni put doista kratak i pripada li doista ovoj recenziji. Oboje može bez nas.

FALCON pretvara recenziju u tocˇku u resˇetki,a potpis u kratak put do nje.\boxed{ \begin{array}{c} \text{FALCON pretvara recenziju u točku u rešetki,}\\ \text{a potpis u kratak put do nje.} \end{array}}

Tko izmijeni tekst, pomiče točku — a stari put vodi u prazno.