Parašo algoritmas

FALCON paaiškintas matematiškai

Kaip McGesund atsiliepimas pasirašomas FN-DSA (FALCON) algoritmu — ir kodėl vienas pakeistas ženklas sulaužo parašą.

Būklė: 2026-09-07

1. Apie ką čia kalbama

Atsiliepimas McGesund sistemoje nėra tiesiog teksto laukas duomenų bazėje, kuriuo tenka patikėti. Išsiunčiamas jis pasirašomas skaitmeniniu būdu, ir kiekvienas lankytojas gali šį parašą vėliau perskaičiuoti savo paties naršyklėje.

Daliai šių parašų naudojame FALCON — tiksliau, FN-DSA-512 ir FN-DSA-1024. Šis straipsnis paaiškina, kas tuo metu vyksta matematiškai.

Svarbu iš karto:

FALCON nėra šifravimas. Atsiliepimo tekstas juk skirtas skaityti. FALCON įrodo ne slaptumą, o kilmę ir vientisumą.

2. Kas tiksliai pasirašoma

Pasirašomas ne ištisinis tekstas, o kompaktiškas duomenų objektas, kuris vienareikšmiškai užfiksuoja tekstą:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<įmonės ID>",
  "c":   "<atsiliepimo ID>",
  "h":   "<atsiliepimo teksto SHA-256>",
  "rh":  "<viso pateikimo duomenų rinkinio SHA-256>",
  "rv":  1,
  "qh":  "<QR voko SHA-256, tik QR atsiliepimuose>",
  "iat": 1757203200
}

Tai yra mūsų pranešimas mm. Jis susieja:

  1. kuriai įmonei atsiliepimas priklauso (f),
  2. apie kurį atsiliepimą kalbama (c),
  3. koks tekstas už jo stovėjo — kaip maišos reikšmė (h),
  4. koks duomenų rinkinys iš viso buvo pateiktas (rh): tekstas, širdelės, geo statusas ir aplinkybių duomenys, kanoniškai serializuoti ir sumaišyti, schemos versijoje rv,
  5. iš kurio QR kodo atsiliepimas kilęs (qh) — atsiliepimui be QR šio lauko nėra,
  6. kada buvo pasirašyta (iat).

Vienas pakeistas ženklas atsiliepimo tekste nutraukia šią grandinę. Būtent tai ir yra tikslas — o nuo rh tas pats galioja ir vėliau perstumtai širdelei ar pakeistam geo statusui.

3. Pagrindinis uždavinys

Skaitytojas, atsidūręs įmonės profilyje, turi du klausimus:

  1. Ar šis atsiliepimas tikrai kilęs iš McGesund sistemos?
  2. Ar jis buvo pakeistas vėliau?

Tam naudojama raktų pora:

  • privatusis raktas — lieka parašų tarnyboje
  • viešasis raktas — jį gali turėti bet kas

Pasirašoma privačiuoju, tikrinama viešuoju raktu. Ir būtent skaitytojo įrenginyje, o ne mūsų serveryje.

4. Kodėl FALCON?

Daugelis šiandieninių parašo algoritmų remiasi uždaviniais, kurie klasikiniams kompiuteriams yra sunkūs, o pakankamai dideliems kvantiniams kompiuteriams galėtų tapti gerokai lengvesni.

Atsiliepimo atveju tai aktualiau nei trumpalaikiam pranešimui: atsiliepimas turi likti patikrinamas ir po penkerių ar dešimties metų. Kas pasirašo šiandien, pasirašo visam įrašo gyvavimo laikui.

Todėl FALCON remiasi gardelių kriptografija:

Sukuriama matematiškai paprastai aprašoma gardelė, kurioje viena konkreti paieškos užduotis yra ypač sunki.

5. Kas yra matematinė gardelė?

Du vektoriai:

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

Visos sveikaskaitinės kombinacijos

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

sudaro taškų gardelę. Pavyzdžiui:

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
Du vektoriai išskleidžia gardelę. Kiekvienas taškas yra sveikaskaitinė jų kombinacija — pažymėtasis gaunamas iš dviejų v₁ ir trijų v₂.

Lemiama yra štai kas:

Pačią gardelę aprašyti lengva. Rasti joje tam tikras savybes labai sunku.

6. Paslaptis — trumpi vektoriai

Klasikinė sunki užduotis skamba taip:

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

Tai Shortest Vector Problem. Dviejuose matmenyse jį galima išspręsti perrinkimu. FALCON dirba 512 arba 1024 matmenų erdvėje — ten tai beviltiška.

ilga bazėbeveik lygiagretūstrumpiausias vektorius
Ta pati gardelė, du aprašymai. Pilki vektoriai ją taip pat generuoja, tačiau yra ilgi ir beveik lygiagretūs — prasta bazė. Trumpasis vektorius kaip tik ir yra tai, ką sunku rasti.

Tiesa, FALCON reikia ne paties trumpiausio vektoriaus, o kai ko giminingo: prie iš anksto duoto tikslo taško rasti artimą gardelės tašką. Ir tai be teisingos papildomos informacijos yra sunku.

tikslo taškas iš atsiliepimoartimas gardelės taškastoli
Tikslo taškas iš atsiliepimo (tuščiaviduris apskritimas) gardelėje nėra. Ieškoma gardelės taško visai šalia — brūkšninis kelias iki tolimo taško taip pat tenkina pirmąją sąlygą, tik jis nėra trumpas.

7. Daugianariai vietoj skaičių

FALCON naudoja NTRU gardelę ir skaičiuoja su daugianariais. Vietoj pavienių skaičių — su koeficientų sąrašais:

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.

Skaičiuojama žiede

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

Tai reiškia:

  • Zq\mathbb{Z}_q: skaičiavimas moduliu qq. Kai q=7q=7, pavyzdžiui, 10≡310\equiv3, nes 10−7=310-7=3.
  • xn=−1x^n=-1: išlaiko daugianarius fiksuoto ilgio.

Konkrečiai FALCON naudoja:

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

8. Pagrindinė gudrybė

Privatųjį raktą sudaro keturi maži daugianariai

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

su NTRU lygtimi

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

Šie keturi kartu sudaro slaptą, patogią gardelės bazę — gardelės aprašymą trumpais vektoriais.

Viešasis raktas iš esmės yra vienas vienintelis daugianaris:

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

Iš hh gaunama ta pati gardelė, tik nepatogia baze iš ilgų vektorių:

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

Tai ir yra visa FALCON esmė. Abi bazės aprašo tą pačią gardelę. Tik viena tinka skaičiuoti, o kita — ne.

Tai galima įsivaizduoti kaip miesto planą: viešas yra visas žemėlapis. Slapta yra trumpiausių kelių išmanymas.

9. Atsiliepimas virsta tašku

Prieš pasirašant, naudingosios apkrovos objektas praleidžiamas per maišos funkciją. FALCON tam naudoja Hash-to-Point: iš pranešimo gaunama ne skaitinė reikšmė, o tiesiogiai taškas žiede.

Papildomai parašų tarnyba ištraukia atsitiktinę druską (salt) rr (320 bitų) ir sumaišo ją kartu:

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

Druska nėra priedas. Be jos tas pats atsiliepimas visada duotų tą patį parašą, ir iš daugelio parašų būtų galima atkurti slaptąją bazę. Todėl ji keliauja kartu su parašu.

10. Kas yra galiojantis parašas

Ieškoma poros

(s1,s2)(s_1,s_2)

su dviem savybėmis:

s1+s2 h≡c(modq)ir∥(s1,s2)∥  mazˇas.s_1+s_2\,h\equiv c \pmod q \qquad\text{ir}\qquad \|(s_1,s_2)\|\;\text{mažas}.

Vien pirmąją sąlygą patenkinti trivialu — imame s2=0s_2=0 ir s1=cs_1=c. Antroji sąlyga padaro užduotį sunkią.

Trumpumas ir yra parasˇas.\boxed{\text{Trumpumas ir yra parašas.}}

11. Iki galo perskaičiuotas mažas pavyzdys

Viską sutraukiame iki žaislinio dydžio: daugianariai su vieninteliu koeficientu, tai yra paprasti skaičiai, ir

q=97.q=97.

Slaptasis raktas. Du maži skaičiai:

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

Viešasis raktas. Galioja 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, nes 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Taigi:

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

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

Viešoji bazė gaunama tiesiai iš hh:

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

Abu vektoriai priklauso LL — ir abu yra ilgi.

Slaptąją bazę žino tik parašų tarnyba:

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

nes −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 ir −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Determinantas yra

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

taigi NTRU lygtis tenkinama. Abu vektoriai yra trumpi.

1 žingsnis: apskaičiuoti atsiliepimo maišą

Tarkime, atsiliepimo naudingosios apkrovos objektas duoda

c=71.c=71.

2 žingsnis: pirmas, prastas sprendinys

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

tenkina 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Bet ilgis yra 7171 — gerokai per ilgas.

3 žingsnis: sutrumpinti slaptąja baze

Parašų tarnyba išreiškia tikslo tašką savo trumpąja baze:

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

Iš to gaunama a≈−10,25a\approx-10{,}25 ir b≈−2,20b\approx-2{,}20. Suapvalinus iki a=−10a=-10, b=−2b=-2, gaunamas gardelės taškas

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

Patikra: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, taigi tikrai priklauso LL. Atimame:

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

Ilgis:

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

Tai ir yra parašas.

4 žingsnis: tas pats metodas su viešąja baze

Kas žino tik h=34h=34, turi bazę {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Tas pats apvalinimo skaičiavimas ten duoda gardelės tašką (97,0)(97,0) ir kartu

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

Taip pat galiojantis lygties sprendinys — bet septynis kartus ilgesnis. Jei priėmimo riba nustatyta žemiau 26, jis bevertis.

Tas pats algoritmas, ta pati gardele˙, tas pats tikslo tasˇkas.Skiriasi tik baze˙ — o kartu ir rezultatas.\boxed{ \begin{array}{c} \text{Tas pats algoritmas, ta pati gardelė, tas pats tikslo taškas.}\\ \text{Skiriasi tik bazė — o kartu ir rezultatas.} \end{array}}

Tai FALCON slaptųjų durų principas vienoje eilutėje.

5 žingsnis: naršyklė tikrina

Naršyklė gauna atsiliepimą, druską ir s2=2s_2=2. Ji iš naujo apskaičiuoja maišą, gauna c=71c=71, atkuria

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

ir patikrina ilgį:

∥(3,2)∥=13  ≤  β⟹Parasˇas galioja\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Parašas galioja}}

6 žingsnis: kas nors pakeičia atsiliepimo tekstą

Jei tekstas vėliau pakeičiamas, pasikeičia turinio maiša, o kartu ir taškas, tarkime, į

c′=40.c'=40.

Senasis parašas lieka (3,2)(3,2), bet

3+34⋅2=71≠40⟹Parasˇas negalioja3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Parašas negalioja}}

Atsiliepimą galime ištrinti. Pakeisti jo nepastebimai negalime.

Sąžininga pastaba apie pavyzdį

Dviejuose matmenyse užpuolikas gali trumpus sprendinius tiesiog perrinkti — kai c′=40c'=40, pavyzdžiui, (6,1)(6,1). Šis pavyzdys nėra saugus; jis tik parodo mechanizmą. FALCON-1024 atveju vektorius turi 2048 koeficientus, ir ten perrinkimas nieko neduoda.

12. Kodėl tiesiog neapvalinama?

3 žingsnio metodas vadinamas Babai apvalinimu. Mokomajam pavyzdžiui jo pakanka — tikram parašo algoritmui ne.

Priežastis: suapvalinti parašai pasiskirstę netolygiai. Jų forma priklauso nuo slaptosios bazės geometrijos. Iš pakankamai daug parašų šią geometriją būtų galima atkurti — o kartu ir privatųjį raktą. Būtent dėl to sudužo ankstesni gardelėmis grįsti parašo algoritmai.

Todėl FALCON trumpus vektorius traukia iš diskretaus Gauso skirstinio gardelėje:

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

Reikšmės arti tikslo taško yra labiau tikėtinos, bet kuri būtent bus parinkta — atsitiktina. Rezultatas yra skirstinys, kuris nieko neatskleidžia apie naudotą bazę — matematiškai: jis neatskiriamas nuo skirstinio, priklausančio tik nuo pačios gardelės.

Šis atrankos generatorius yra sudėtingiausia FALCON dalis. Jis veikia rekursiškai medžio struktūroje ir dirba su slankiojo kablelio skaičiais — tai daro realizaciją jautrią ir yra pagrindinė priežastis, kodėl FALCON teisingai įgyvendinti sunkiau nei ML-DSA.

13. Kas iš tikrųjų perduodama

Parašą sudaro

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

Tik s2s_2 — ne pora. s1s_1 tikrintojas apskaičiuoja pats:

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

Kadangi s2s_2 koeficientai yra maži ir sklaidosi apie nulį, juos galima stipriai suspausti. Todėl FALCON parašai yra tokie akivaizdžiai kompaktiški:

viešasis raktasparašas
FALCON-512897 B~666 B
FALCON-10241 793 B~1 280 B

Palyginimui: ML-DSA-87 reikia 4 627 baitų. Tiesa, McGesund sistemoje nė vienas iš šių parašų nėra pačiame QR kode — lipdukas neša tik Ed25519 voką; postkvantiniai antspaudai guli prie duomenų rinkinio ir tikrinant įkeliami papildomai. Taigi dydis čia lemia ne spausdinamumą, o saugojimą ir perdavimą: FALCON antspaudas yra maždaug ketvirtadaliu ML-DSA antspaudo dydžio.

14. Kodėl FALCON greitai tikrina

Naivi daugianarių daugyba kainuoja

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

Su greitąja Furjė transformacija tai nukrenta maždaug iki

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

Kai n=1024n=1024, tai skirtumas tarp milijono ir maždaug dešimties tūkstančių operacijų. Todėl patikra lankytojo naršyklėje trunka milisekundes — ir todėl pavadinime yra F:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Eiga paveiksle

PARAŠŲ TARNYBA (MCGESUND)LANKYTOJO NARŠYKLĖprivatusis raktas (f, g, F, G — trumpa bazė)Naudingoji apkrova m = {įmonė, atsiliepimas, h, rh, iat}Druska r + HashToPoint(r ‖ m) = cGauso atranka: trumpas vektorius (s₁, s₂)Parašas σ = (r, s₂) + kidatsiliepimas + σ + viešasis raktas hc perskaičiuoti, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?galiojanegalioja
Nuo naudingosios apkrovos iki varnelės naršyklėje. Viskas virš skiriamosios linijos vyksta vieną kartą išsiunčiant, viskas žemiau — iš naujo pas kiekvieną lankytoją, jo įrenginyje, su viešuoju raktu.

16. Kodėl užpuolikui nepavyksta

Jis žino hh, taigi ir visą gardelę. Jis žino ir tikslo tašką cc, vos tik atsiliepimas tampa viešas. Jam trūksta trumposios bazės.

Kad suklastotų atsiliepimą, jis turėtų prie savo pasirinkto cc rasti trumpą vektorių — vien iš viešojo aprašymo. Tai ta pati užduotis, kurią iliustravo 4 pavyzdžio žingsnis: be gerų vektorių tas pats skaičiavimas baigiasi gerokai per ilgu sprendiniu.

1024 matmenų erdvėje geriausi žinomi metodai — tiek klasikiniai, tiek kvantiniai — nuo to yra labai toli.

Pasirasˇyti: greitaPatikrinti: greitaSuklastoti: sunku\boxed{\text{Pasirašyti: greita}\quad \text{Patikrinti: greita}\quad \text{Suklastoti: sunku}}

17. Ką konkrečiai su tuo daro McGesund

Vokas. Kiekvienas pasirašytas atsiliepimas turi Ed25519 parašą. Tai privaloma dalis — klasikinė, labai maža, natyviai patikrinama kiekvienoje naršyklėje.

Postkvantiniai antspaudai. Šalia guli vienas ar du kvantams atsparūs parašai. Kurie — priklauso nuo tarifo:

Tarifasgalimi parašų lygiai
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, abu lygiagrečiai

Lygiagretus variantas sąmoningai perteklinis. FALCON remiasi NTRU gardelėmis, ML-DSA — modulinėmis gardelėmis. Jei viena iš šių dviejų šeimų pasirodytų silpnesnė, nei manoma šiandien, kita laikytų toliau.

Laiko inkaras. Parašo rakto kontrolinis atspaudas per OpenTimestamps įtvirtinamas Bitcoin bloke. Taip įrodoma ne tik tai, kad parašas tikras, bet ir tai, kad jis tam tikru momentu jau egzistavo — nereikalaujant iš nieko tikėti mūsų laiko žyma.

Visa tai skaičiuojama skaitytojo naršyklėje per WASM modulį. Mes pateikiame duomenis; patikra vyksta lankytojo įrenginyje. Jei rytoj dingtume iš tinklo, kartą įkeltas atsiliepimas liktų patikrinamas.

Dėl pavadinimų: FALCON šiuo metu standartizuojamas kaip FN-DSA; projektas numatytas kaip FIPS 206, bet dar nebaigtas. Todėl McGesund kode lygiai vadinami FN-DSA-512 ir FN-DSA-1024, net jei kalboje ir toliau kalbama apie FALCON.

18. Svarbiausia intuicija

Viešasis raktas yra pilnas labirinto aprašymas. Jį gali apžiūrėti bet kas.

Parašas yra įrodymas: „Būtent šiam atsiliepimui radau labai trumpą kelią."

Privatusis raktas yra trumpiausių kelių išmanymas.

Skaitytojui trumpiausių kelių žinoti nereikia. Jis tik patikrina, ar pateiktas kelias iš tikrųjų trumpas ir ar jis iš tikrųjų priklauso šiam atsiliepimui. Abu dalykus jis gali padaryti be mūsų.

FALCON pavercˇia atsiliepimą tasˇku gardele˙je,o parasˇą — trumpu keliu iki to tasˇko.\boxed{ \begin{array}{c} \text{FALCON paverčia atsiliepimą tašku gardelėje,}\\ \text{o parašą — trumpu keliu iki to taško.} \end{array}}

Kas pakeičia tekstą, perstumia tašką — ir senasis kelias veda į tuštumą.