Parakstu algoritms

FALCON matemātiski izskaidrots

Kā McGesund atsauksme tiek parakstīta ar FN-DSA (FALCON) — un kāpēc viena mainīta rakstzīme salauž parakstu.

Stāvoklis: 2026-09-07

1. Par ko šeit ir runa

Atsauksme McGesund vietnē nav vienkārši teksta lauks datubāzē, kuram jātic uz vārda. Nosūtīšanas brīdī tā tiek digitāli parakstīta, un vēlāk ikviens apmeklētājs var šo parakstu pārrēķināt savā pārlūkprogrammā.

Daļai šo parakstu mēs izmantojam FALCON — precīzāk, FN-DSA-512 un FN-DSA-1024. Šis raksts skaidro, kas tur matemātiski notiek.

Svarīgi jau iepriekš:

FALCON nav šifrēšana. Atsauksmes tekstam taču ir jābūt lasāmam. FALCON pierāda nevis slepenību, bet gan izcelsmi un neskartību.

2. Kas tieši tiek parakstīts

Parakstīts tiek nevis pats teksts, bet kompakts datu objekts, kas viennozīmīgi nostiprina tekstu:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<uzņēmuma ID>",
  "c":   "<atsauksmes ID>",
  "h":   "<atsauksmes teksta SHA-256>",
  "rh":  "<visa iesniegtā datu ieraksta SHA-256>",
  "rv":  1,
  "qh":  "<QR aploksnes SHA-256, tikai QR atsauksmēm>",
  "iat": 1757203200
}

Tas ir mūsu ziņojums mm. Tas sasaista kopā:

  1. kuram uzņēmumam atsauksme pieder (f),
  2. par kuru atsauksmi ir runa (c),
  3. kāds teksts aiz tās stāvēja — kā jaucējvērtība (h),
  4. kāds datu ieraksts kopumā tika iesniegts (rh): teksts, sirdis, ģeostatuss un ziņas par apmeklējuma iemeslu, kanoniski serializēti un sajaukti, shēmas versijā rv,
  5. no kura QR koda atsauksme nāk (qh) — atsauksmei bez QR šis lauks atkrīt,
  6. kad tika parakstīts (iat).

Viena mainīta rakstzīme atsauksmes tekstā šo ķēdi salauž. Tieši tāds ir nolūks — un kopš rh tas pats attiecas arī uz vēlāk pārbīdītu sirdi vai mainītu ģeostatusu.

3. Pamatproblēma

Lasītājs, kas nonāk uzņēmuma profilā, saskaras ar diviem jautājumiem:

  1. Vai šī atsauksme tiešām nāk no McGesund sistēmas?
  2. Vai tā vēlāk ir mainīta?

Tam kalpo atslēgu pāris:

  • privātā atslēga — paliek parakstīšanas dienestā
  • publiskā atslēga — to drīkst zināt ikviens

Parakstīts tiek ar privāto, pārbaudīts ar publisko atslēgu. Un tas notiek lasītāja ierīcē, nevis uz mūsu servera.

4. Kāpēc FALCON?

Daudzi mūsdienu parakstu algoritmi balstās uz problēmām, kas klasiskiem datoriem ir grūtas, bet pietiekami lieliem kvantu datoriem varētu kļūt ievērojami vieglākas.

Atsauksmei tas ir būtiskāk nekā īslaicīgam ziņojumam: atsauksmei arī pēc pieciem vai desmit gadiem jābūt pārbaudāmai. Kas paraksta šodien, paraksta uz visu ieraksta dzīves laiku.

Tāpēc FALCON balstās uz režģu kriptogrāfiju:

Tiek uzbūvēts matemātiski vienkārši aprakstāms režģis, kurā noteikts meklēšanas uzdevums ir ārkārtīgi grūts.

5. Kas ir matemātisks režģis?

Divi vektori:

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

Visas veselo skaitļu kombinācijas

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

veido punktu režģi. Piemēram:

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
Divi vektori izveido režģi. Katrs punkts ir abu veselo skaitļu kombinācija — atzīmētais rodas no divkārša v₁ un trīskārša v₂.

Izšķirošais ir šis:

Pašu režģi ir viegli aprakstīt. Atrast tajā noteiktas īpašības ir ļoti grūti.

6. Noslēpums ir īsi vektori

Klasiskais grūtais uzdevums skan šādi:

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

Tā ir Shortest Vector Problem. Divās dimensijās to var atrisināt izmēģinot. FALCON strādā 512. vai 1024. dimensijā — tur tas ir bezcerīgi.

gara bāzegandrīz paralēliīsākais vektors
Tas pats režģis, divi apraksti. Pelēkie vektori to arī ģenerē, taču ir gari un gandrīz paralēli — slikta bāze. Īsais vektors ir tas, ko ir grūti atrast.

Tomēr FALCON nav vajadzīgs īsākais vektors kā tāds, bet kaut kas radniecīgs: iepriekš dotam mērķa punktam atrast tuvu režģa punktu. Arī tas bez pareizās papildinformācijas ir grūti.

mērķa punkts no atsauksmestuvs režģa punktstālu prom
Mērķa punkts no atsauksmes (tukšais aplītis) režģī neatrodas. Meklēts ir režģa punkts tam cieši blakus — punktētais ceļš uz tālu punktu arī ir pirmā nosacījuma risinājums, tikai ne īss.

7. Polinomi skaitļu vietā

FALCON izmanto NTRU režģi un rēķina ar polinomiem. Tātad atsevišķu skaitļu vietā — ar koeficientu virknēm:

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.

Rēķināts tiek gredzenā

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

Tas nozīmē:

  • Zq\mathbb{Z}_q: rēķināšana pēc moduļa qq. Piemēram, ja q=7q=7, tad 10≡310\equiv3, jo 10−7=310-7=3.
  • xn=−1x^n=-1: notur polinomus fiksētā garumā.

FALCON konkrēti izmanto:

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

8. Galvenais triks

Privātā atslēga sastāv no četriem maziem polinomiem

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

ar NTRU vienādojumu

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

Šie četri kopā veido slepenu, labvēlīgu režģa bāzi — režģa aprakstu no īsiem vektoriem.

Publiskā atslēga pēc būtības ir viens vienīgs polinoms:

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

No hh izriet tas pats režģis, taču neērtā bāzē no gariem vektoriem:

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

Tā ir visa FALCON būtība. Abas bāzes apraksta vienu un to pašu režģi. Tikai viena ir rēķināšanai noderīga, bet otra nav.

To var iedomāties kā pilsētas plānu: publiska ir pilnā karte. Slepena ir īsceļu zināšana.

9. Atsauksme kļūst par punktu

Pirms parakstīšanas payload objekts iziet cauri jaucējfunkcijai. FALCON tam izmanto Hash-to-Point: no ziņojuma rodas nevis skaitliska vērtība, bet uzreiz punkts gredzenā.

Papildus parakstīšanas dienests izlozē nejaušu sāli rr (320 biti) un jauc to līdzi:

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

Sāls nav papildinājums. Bez tās viena un tā pati atsauksme vienmēr dotu vienu un to pašu parakstu, un no daudziem parakstiem varētu rekonstruēt slepeno bāzi. Tāpēc tā ceļo līdzi parakstā.

10. Kas ir derīgs paraksts

Meklēts ir pāris

(s1,s2)(s_1,s_2)

ar divām īpašībām:

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

Pirmo nosacījumu vien ir triviāli izpildīt — pietiek ņemt s2=0s_2=0 un s1=cs_1=c. Tieši otrais nosacījums padara uzdevumu grūtu.

Iˉsums ir paraksts.\boxed{\text{Īsums ir paraksts.}}

11. Pilnībā izrēķināts mini piemērs

Mēs sarukinām visu līdz rotaļlietas izmēram: polinomi ar tikai vienu koeficientu, tātad parasti skaitļi, un

q=97.q=97.

Slepenā atslēga. Divi mazi skaitļi:

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

Publiskā atslēga. Ir 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, jo 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Tātad:

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

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

Publiskā bāze izriet tieši no hh:

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

Abi pieder LL — un abi ir gari.

Slepeno bāzi zina tikai parakstīšanas dienests:

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

jo −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 un −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Determinants ir

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

tātad NTRU vienādojums izpildās. Abi vektori ir īsi.

1. solis: atsauksmi sajaukt

Pieņemsim, ka atsauksmes payload objekts dod

c=71.c=71.

2. solis: pirmais, sliktais risinājums

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

apmierina 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Bet garums ir 7171 — daudz par garu.

3. solis: saīsināšana ar slepeno bāzi

Parakstīšanas dienests izsaka mērķa punktu savā īsajā bāzē:

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

Tas noved pie a≈−10,25a\approx-10{,}25 un b≈−2,20b\approx-2{,}20. Noapaļojot uz a=−10a=-10, b=−2b=-2, rodas režģa punkts

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

Pārbaude: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, tātad tiešām pieder LL. Atņemam:

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

Garums:

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

Tas ir paraksts.

4. solis: tas pats aprēķins ar publisko bāzi

Kas zina tikai h=34h=34, tam ir bāze {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Tas pats noapaļošanas aprēķins tur dod režģa punktu (97,0)(97,0) un līdz ar to

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

Arī derīgs vienādojuma risinājums — bet septiņreiz garāks. Ja pieņemšanas robeža ir zemāka par 26, tas ir bezvērtīgs.

Tas pats algoritms, tas pats rezˇg¸is, tas pats meˉrk¸a punkts.Atsˇk¸iras tikai baˉze — un lıˉdz ar to arıˉ rezultaˉts.\boxed{ \begin{array}{c} \text{Tas pats algoritms, tas pats režģis, tas pats mērķa punkts.}\\ \text{Atšķiras tikai bāze — un līdz ar to arī rezultāts.} \end{array}}

Tās ir FALCON slēptdurvis vienā rindā.

5. solis: pārlūkprogramma pārbauda

Pārlūkprogramma saņem atsauksmi, sāli un s2=2s_2=2. Tā no jauna aprēķina jaucējvērtību, iegūst c=71c=71, rekonstruē

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

un pārbauda garumu:

∥(3,2)∥=13  ≤  β⟹Paraksts derıˉgs\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Paraksts derīgs}}

6. solis: kāds maina atsauksmes tekstu

Ja tekstu vēlāk maina, mainās satura jaucējvērtība un līdz ar to punkts, teiksim

c′=40.c'=40.

Vecais paraksts paliek (3,2)(3,2), bet

3+34⋅2=71≠40⟹Paraksts nederıˉgs3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Paraksts nederīgs}}

Mēs varam atsauksmi izdzēst. Mainīt tā, lai to nepamanītu, mēs to nevaram.

Godīga piezīme par piemēru

Divās dimensijās uzbrucējs īsus risinājumus var vienkārši izmēģināt — piemēram, c′=40c'=40 gadījumā (6,1)(6,1). Šis piemērs nav drošs; tas tikai parāda mehānismu. FALCON-1024 gadījumā vektoram ir 2048 koeficienti, un tur izmēģināšana neved nekur.

12. Kāpēc netiek vienkārši noapaļots?

  1. soļa metode saucas Babai noapaļošana. Mācību piemēram tā pietiek — īstam parakstu algoritmam ne.

Iemesls: noapaļotie paraksti neizvietojas vienmērīgi. To forma ir atkarīga no slepenās bāzes ģeometrijas. No pietiekami daudziem parakstiem šo ģeometriju varētu rekonstruēt — un līdz ar to arī privāto atslēgu. Tieši uz tā ir cietuši agrākie uz režģiem balstītie parakstu algoritmi.

Tāpēc FALCON īsos vektorus izlozē no diskrēta Gausa sadalījuma pār režģi:

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

Vērtības tuvu mērķa punktam ir varbūtīgākas, taču tas, kura tieši tiek izvēlēta, ir nejauši. Rezultāts ir sadalījums, kas neko neizpauž par izmantoto bāzi — matemātiski: tas nav atšķirams no sadalījuma, kas atkarīgs vienīgi no paša režģa.

Šis izlozes modulis ir prasīgākā FALCON daļa. Tas darbojas rekursīvi pār koka struktūru un strādā ar peldošā komata skaitļiem — kas padara implementāciju delikātu un ir galvenais iemesls, kāpēc FALCON ir grūtāk pareizi realizēt nekā ML-DSA.

13. Kas patiesībā tiek pārraidīts

Paraksts sastāv no

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

Tikai s2s_2 — nevis pāris. s1s_1 pārbaudītājs izrēķina pats:

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

Tā kā s2s_2 koeficienti ir mazi un izkliedēti ap nulli, tos var stipri saspiest. Tas ir iemesls FALCON uzkrītoši kompaktajiem parakstiem:

publiskā atslēgaparaksts
FALCON-512897 B~666 B
FALCON-10241793 B~1280 B

Salīdzinājumam: ML-DSA-87 vajadzīgi 4627 baiti. McGesund gadījumā gan neviens no šiem parakstiem neatrodas pašā QR kodā — uzlīme nes tikai Ed25519 aploksni; pēckvantu zīmogi atrodas pie datu ieraksta un tiek ielādēti pārbaudes brīdī. Izmērs šeit tātad neizšķir drukājamību, bet gan glabāšanu un pārraidi: FALCON zīmogs ir labu ceturtdaļu no ML-DSA zīmoga lieluma.

14. Kāpēc FALCON pārbauda ātri

Naiva polinomu reizināšana maksā

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

Ar ātro Furjē transformāciju tas samazinās aptuveni līdz

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

Pie n=1024n=1024 tā ir atšķirība starp miljonu un aptuveni desmit tūkstošiem operāciju. Tāpēc pārbaude apmeklētāja pārlūkprogrammā notiek milisekundēs — un tāpēc nosaukumā ir burts F:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Norise attēlā

PARAKSTĪŠANAS DIENESTS (MCGESUND)APMEKLĒTĀJA PĀRLŪKPROGRAMMAprivātā atslēga (f, g, F, G — īsā bāze)Payload m = {uzņēmums, atsauksme, h, rh, iat}sāls r + HashToPoint(r ‖ m) = cGausa izlase: īss vektors (s₁, s₂)paraksts σ = (r, s₂) + kidatsauksme + σ + publiskā atslēga hc no jauna aprēķināt, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?derīgsnederīgs
No payload objekta līdz ķeksītim pārlūkprogrammā. Viss virs atdalošās līnijas notiek vienreiz nosūtīšanas brīdī, viss zem tās — no jauna pie katra apmeklētāja, viņa ierīcē, ar publisko atslēgu.

16. Kāpēc uzbrucējs neizdodas

Viņš zina hh un līdz ar to visu režģi. Viņš zina arī mērķa punktu cc, tiklīdz atsauksme ir publiska. Viņam trūkst īsās bāzes.

Lai atsauksmi viltotu, viņam pašam izvēlētai cc vērtībai būtu jāatrod īss vektors — vienīgi no publiskā apraksta. Tas ir tas pats uzdevums, ko ilustrēja piemēra 4. solis: bez labajiem vektoriem tas pats aprēķins nonāk pie krietni par gara risinājuma.

  1. dimensijā labākās zināmās metodes — gan klasiskās, gan uz kvantiem balstītās — no tā ir tālu.
Parakstıˉt: aˉtriPaˉrbaudıˉt: aˉtriViltot: gruˉti\boxed{\text{Parakstīt: ātri}\quad \text{Pārbaudīt: ātri}\quad \text{Viltot: grūti}}

17. Ko McGesund ar to konkrēti dara

Aploksne. Katra parakstītā atsauksme nes Ed25519 parakstu. Tas ir obligātais variants — klasisks, ļoti mazs, katrā pārlūkprogrammā natīvi pārbaudāms.

Pēckvantu zīmogi. Blakus atrodas viens vai divi kvantu izturīgi paraksti. Kuri — atkarīgs no tarifa:

Tarifspieejamie parakstu līmeņi
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, abi paralēli

Paralēlais variants ir apzināti dublējošs. FALCON balstās uz NTRU režģiem, ML-DSA — uz moduļu režģiem. Ja viena no abām saimēm izrādītos vājāka, nekā šodien pieņemts, otra turpina nest.

Laika enkurs. Parakstīšanas atslēgas nospiedums caur OpenTimestamps tiek noenkurots Bitcoin blokā. Tādējādi ir pierādīts ne tikai tas, ka paraksts ir īsts, bet arī tas, ka tas noteiktā brīdī jau eksistēja — un nevienam nav jātic mūsu laika zīmogam.

Viss šis aprēķins notiek lasītāja pārlūkprogrammā, caur WASM moduli. Mēs piegādājam datus; pārbaude notiek apmeklētāja ierīcē. Ja mēs rīt pazustu no tīkla, vienreiz ielādēta atsauksme paliktu pārbaudāma.

Par nosaukumu izpratni: FALCON pašlaik tiek standartizēts kā FN-DSA; projekts ir paredzēts kā FIPS 206, taču vēl nav pabeigts. Tāpēc McGesund kodā līmeņi saucas FN-DSA-512 un FN-DSA-1024, pat ja sarunvalodā joprojām runā par FALCON.

18. Svarīgākā intuīcija

Publiskā atslēga ir pilnīgs labirinta apraksts. To drīkst aplūkot ikviens.

Paraksts ir pierādījums: „Tieši šai atsauksmei es esmu atradis ļoti īsu ceļu."

Privātā atslēga ir īsceļu zināšana.

Lasītājam īsceļi nav jāzina. Viņš tikai pārmēra, vai iesniegtais ceļš tiešām ir īss un tiešām pieder šai atsauksmei. Abas lietas viņš var izdarīt bez mums.

FALCON paˉrveˉrsˇ atsauksmi par punktu rezˇg¸ıˉun parakstu par ıˉsu cel¸u lıˉdz tam.\boxed{ \begin{array}{c} \text{FALCON pārvērš atsauksmi par punktu režģī}\\ \text{un parakstu par īsu ceļu līdz tam.} \end{array}}

Kas maina tekstu, pārbīda punktu — un vecais ceļš ved tukšumā.