Allkirjastamismeetod

FALCON matemaatiliselt selgitatud

Kuidas McGesundi arvustus FN-DSA-ga (FALCON) allkirjastatakse — ja miks üksainus muudetud märk allkirja murrab.

Seisuga: 2026-09-07

1. Millest siin jutt käib

McGesundi arvustus ei ole andmebaasi tekstiväli, mida tuleb lihtsalt uskuda. See allkirjastatakse digitaalselt juba saatmisel ja iga külastaja saab selle allkirja hiljem oma brauseris järele arvutada.

Osa neist allkirjadest teeme FALCONiga — täpsemalt FN-DSA-512 ja FN-DSA-1024-ga. See artikkel selgitab, mis seejuures matemaatiliselt toimub.

Kõigepealt oluline:

FALCON ei ole krüpteerimine. Arvustuse teksti ju peabki saama lugeda. FALCON ei tõenda salastatust, vaid päritolu ja terviklikkust.

2. Mida täpselt allkirjastatakse

Allkirjastatakse mitte jooksvat teksti, vaid kompaktne andmeobjekt, mis naelutab teksti üheselt kinni:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ettevõtte ID>",
  "c":   "<arvustuse ID>",
  "h":   "<arvustuse teksti SHA-256>",
  "rh":  "<kogu esitatud andmekirje SHA-256>",
  "rv":  1,
  "qh":  "<QR-Envelope'i SHA-256, ainult QR-arvustuste puhul>",
  "iat": 1757203200
}

See on meie sõnum mm. See seob kokku:

  1. millisele ettevõttele arvustus kuulub (f),
  2. millisest arvustusest on jutt (c),
  3. milline tekst selle taga oli — räsiväärtusena (h),
  4. milline andmekirje tervikuna esitati (rh): tekst, südamed, geostaatus ja ajendi andmed, kanooniliselt serialiseeritud ja räsitud, skeemiversioonis rv,
  5. millisest QR-koodist arvustus pärineb (qh) — QR-ita arvustuse puhul see väli puudub,
  6. millal allkirjastati (iat).

Üksainus muudetud märk arvustuse tekstis murrab selle ahela. Just see ongi eesmärk — ja alates välja rh lisandumisest kehtib sama tagantjärele nihutatud südame või muudetud geostaatuse kohta.

3. Põhiülesanne

Lugeja, kes satub ettevõtte profiilile, seisab kahe küsimuse ees:

  1. Kas see arvustus pärineb tõesti McGesundi süsteemist?
  2. Kas seda on tagantjärele muudetud?

Selleks on olemas võtmepaar:

  • privaatvõti — jääb allkirjastamisteenusesse
  • avalik võti — tohib olla igaühel

Allkirjastatakse privaatvõtmega, kontrollitakse avalikuga. Ja nimelt lugeja seadmes, mitte meie serveris.

4. Miks FALCON?

Paljud tänased allkirjastamismeetodid põhinevad ülesannetel, mis on klassikaliste arvutite jaoks rasked, kuid võivad piisavalt suurte kvantarvutite jaoks tunduvalt kergemaks muutuda.

Arvustuse puhul on see olulisem kui põgusa sõnumi puhul: arvustus peab olema kontrollitav ka viie või kümne aasta pärast. Kes allkirjastab täna, allkirjastab kirje kogu eluea jaoks.

FALCON põhineb seetõttu võrekrüptograafial:

Ehitatakse matemaatiliselt lihtsalt kirjeldatav võre, milles üks kindel otsinguülesanne on ülimalt raske.

5. Mis on matemaatiline võre?

Kaks vektorit:

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

Kõik täisarvulised kombinatsioonid

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

annavad punktidest koosneva võre. Näiteks:

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
Kaks vektorit tekitavad võre. Iga punkt on nende kahe täisarvuline kombinatsioon — märgitud punkt tekib kahekordsest v₁-st ja kolmekordsest v₂-st.

Otsustav on:

Võret ennast on lihtne kirjeldada. Kindlate omaduste leidmine selle sees on väga raske.

6. Saladus on lühikesed vektorid

Klassikaline raske ülesanne on:

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

See on Shortest Vector Problem ehk lühima vektori ülesanne. Kahes mõõtmes saab selle läbi proovida. FALCON töötab mõõtmes 512 või 1024 — seal on see lootusetu.

pikk baaspeaaegu paralleelnelühim vektor
Sama võre, kaks kirjeldust. Hallid vektorid tekitavad selle samuti, kuid on pikad ja peaaegu paralleelsed — halb baas. Lühike vektor on see, mida on raske leida.

FALCON ei vaja siiski kõige lühemat vektorit kui sellist, vaid midagi sellega sugulast: etteantud sihtpunktile lähedase võrepunkti leidmist. Ka see on ilma õige lisateabeta raske.

arvustusest tulenev sihtpunktlähedane võrepunktkaugel
Arvustusest tulenev sihtpunkt (õõnes ring) ei asu võres. Otsitakse võrepunkti, mis on sellele lähedal — kriipsjoonega tee kaugel asuvasse punkti on samuti esimese tingimuse lahend, aga just mitte lühike.

7. Polünoomid arvude asemel

FALCON kasutab NTRU-võret ja arvutab polünoomidega. Üksikute arvude asemel siis kordajate loenditega:

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.

Arvutatakse ringis

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

See tähendab:

  • Zq\mathbb{Z}_q: arvutamine mooduli qq järgi. q=7q=7 korral näiteks 10≡310\equiv3, sest 10−7=310-7=3.
  • xn=−1x^n=-1: hoiab polünoomid kindla pikkusega.

FALCON kasutab konkreetselt:

q=12289,n=512  vo˜i  1024.q=12289, \qquad n=512 \;\text{või}\; 1024.

8. Keskne trikk

Privaatvõti koosneb neljast väikesest polünoomist

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

koos NTRU-võrrandiga

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

Need neli moodustavad koos salajase, hästi käituva võrebaasi — võre kirjelduse lühikeste vektorite kaudu.

Avalik võti on sisuliselt üksainus polünoom:

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

hh-st tuleneb sama võre, kuid kohmakas baasis, mis koosneb pikkadest vektoritest:

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

Selles ongi FALCONi kogu tuum. Mõlemad baasid kirjeldavad sama võret. Ainult et üks neist kõlbab arvutamiseks ja teine mitte.

Seda võib ette kujutada linnaplaanina: avalik on täielik kaart. Salajane on otseteede tundmine.

9. Arvustusest saab punkt

Enne allkirjastamist läbib andmeobjekt räsifunktsiooni. FALCON kasutab selleks Hash-to-Pointi: sõnumist ei saa arvväärtus, vaid otse punkt ringis.

Lisaks tõmbab allkirjastamisteenus juhusliku soola rr (320 bitti) ja räsib selle kaasa:

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

Sool ei ole kaunistus. Ilma selleta annaks sama arvustus alati sama allkirja ja paljudest allkirjadest saaks salajase baasi taastada. Seetõttu rändab ta koos allkirjaga kaasa.

10. Milline on kehtiv allkiri

Otsitakse paari

(s1,s2)(s_1,s_2)

kahe omadusega:

s1+s2 h≡c(modq)ja∥(s1,s2)∥  va¨ike.s_1+s_2\,h\equiv c \pmod q \qquad\text{ja}\qquad \|(s_1,s_2)\|\;\text{väike}.

Esimest tingimust üksi on triviaalne täita — võtame s2=0s_2=0 ja s1=cs_1=c. Teine tingimus teeb ülesande raskeks.

Lu¨hidus ongi allkiri.\boxed{\text{Lühidus ongi allkiri.}}

11. Täielikult läbi arvutatud minimaalne näide

Kahandame kõik mängusuuruseks: polünoomid ainult ühe kordajaga, seega tavalised arvud, ja

q=97.q=97.

Salajane võti. Kaks väikest arvu:

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

Avalik võti. Kehtib 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, sest 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Seega:

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

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

Avalik baas tuleneb otse hh-st:

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

Mõlemad asuvad hulgas LL — ja mõlemad on pikad.

Salajast baasi teab ainult allkirjastamisteenus:

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

sest −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 ja −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Determinant on

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

NTRU-võrrand seega kehtib. Mõlemad vektorid on lühikesed.

1. samm: arvustuse räsimine

Oletame, et arvustuse andmeobjekt annab

c=71.c=71.

2. samm: esimene, halb lahend

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

rahuldab tingimust 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Kuid pikkus on 7171 — palju liiga pikk.

3. samm: salajase baasiga lühendamine

Allkirjastamisteenus väljendab sihtpunkti oma lühikeses baasis:

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

Sellest tuleb a≈−10,25a\approx-10{,}25 ja b≈−2,20b\approx-2{,}20. Ümardatuna a=−10a=-10, b=−2b=-2 annab võrepunkti

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

Kontroll: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, seega tõepoolest hulgas LL. Lahutame:

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

Pikkus:

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

See ongi allkiri.

4. samm: sama menetlus avaliku baasiga

Kellel on teada ainult h=34h=34, sellel on baas {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Sama ümardamisarvutus annab seal võrepunkti (97,0)(97,0) ja seega

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

Samuti võrrandi kehtiv lahend — aga seitse korda pikem. Kui vastuvõtupiir seatakse allapoole 26, on see väärtusetu.

Sama algoritm, sama vo˜re, sama sihtpunkt.Erineb ainult baas — ja sellega tulemus.\boxed{ \begin{array}{c} \text{Sama algoritm, sama võre, sama sihtpunkt.}\\ \text{Erineb ainult baas — ja sellega tulemus.} \end{array}}

See on FALCONi peiduluuk ühes reas.

5. samm: brauser kontrollib

Brauser saab arvustuse, soola ja s2=2s_2=2. Ta arvutab räsi uuesti, saab c=71c=71, taastab

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

ja kontrollib pikkust:

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

6. samm: keegi muudab arvustuse teksti

Kui teksti tagantjärele muudetakse, muutub sisuräsi ja sellega punkt, ütleme

c′=40.c'=40.

Vana allkiri jääb (3,2)(3,2)-ks, aga

3+34⋅2=71≠40⟹Allkiri ei kehti3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Allkiri ei kehti}}

Me võime arvustuse kustutada. Muuta me seda märkamatult ei saa.

Aus märkus näite kohta

Kahes mõõtmes saab ründaja lühikesi lahendeid lihtsalt läbi proovida — c′=40c'=40 jaoks näiteks (6,1)(6,1). See näide ei ole turvaline; ta näitab ainult mehhanismi. FALCON-1024 puhul on vektoril 2048 kordajat ja seal ei vii läbiproovimine kuhugi.

12. Miks lihtsalt ei ümardata?

  1. sammu menetlust nimetatakse Babai ümardamiseks. Õppenäite jaoks piisab sellest — tõelise allkirjastamismeetodi jaoks mitte.

Põhjus: ümardatud allkirjad ei jaotu ühtlaselt. Nende kuju sõltub salajase baasi geomeetriast. Piisavalt paljudest allkirjadest saaks selle geomeetria taastada — ja sellega privaatvõtme. Just selle peale on varasemad võrepõhised allkirjastamismeetodid komistanud.

FALCON tõmbab lühikesed vektorid seetõttu diskreetsest Gaussi jaotusest üle võre:

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

Sihtpunkti lähedal olevad väärtused on tõenäolisemad, aga see, milline neist täpselt valitakse, on juhuslik. Tulemuseks on jaotus, mis ei reeda kasutatud baasi kohta midagi — matemaatiliselt: seda ei saa eristada jaotusest, mis sõltub ainult võrest endast.

See sämpler on FALCONi kõige nõudlikum osa. Ta töötab rekursiivselt üle puustruktuuri ja kasutab ujukomaarve — mis teeb teostuse tundlikuks ja on peamine põhjus, miks FALCONit on raskem korrektselt teostada kui ML-DSA-d.

13. Mida tegelikult edastatakse

Allkiri koosneb osadest

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

Ainult s2s_2 — mitte paar. s1s_1 arvutab kontrollija ise:

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

Kuna s2s_2 kordajad on väikesed ja hajuvad nulli ümber, saab neid tugevalt kokku pakkida. See on FALCONi silmatorkavalt kompaktsete allkirjade põhjus:

avalik võtiallkiri
FALCON-512897 B~666 B
FALCON-10241 793 B~1 280 B

Võrdluseks: ML-DSA-87 vajab 4 627 baiti. McGesundis ei ole kumbki neist allkirjadest siiski QR-koodis endas — kleebis kannab ainult Ed25519 Envelope'i; kvantijärgsed templid asuvad andmekirje juures ja laaditakse kontrollimisel juurde. Suurus ei otsusta siin seega prinditavuse, vaid salvestusruumi ja edastuse üle: FALCONi tempel on umbes veerand ML-DSA templi suurusest.

14. Miks FALCON kiiresti kontrollib

Naiivne polünoomide korrutamine maksab

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

Kiire Fourier' teisendusega langeb see umbes tasemele

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

n=1024n=1024 korral on see vahe miljoni ja umbes kümne tuhande operatsiooni vahel. Seepärast käib kontroll külastaja brauseris millisekunditega — ja seepärast on nimes F:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Kulg pildis

ALLKIRJASTAMISTEENUS (MCGESUND)KÜLASTAJA BRAUSERprivaatvõti (f, g, F, G — lühike baas)andmeosa m = {ettevõte, arvustus, h, rh, iat}sool r + HashToPoint(r ‖ m) = cGaussi sämplimine: lühike vektor (s₁, s₂)allkiri σ = (r, s₂) + kidarvustus + σ + avalik võti hc arvutatakse uuesti, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?kehtibei kehti
Andmeosast kuni linnukeseni brauseris. Kõik eraldusjoonest ülalpool toimub korra saatmise ajal, kõik allpool iga külastaja jaoks uuesti — tema seadmes, avaliku võtmega.

16. Miks ründaja läbi kukub

Ta teab hh-d ja sellega kogu võret. Ta teab ka sihtpunkti cc, niipea kui arvustus on avalik. Puudu on tal lühike baas.

Arvustuse võltsimiseks peaks ta ise valitud cc jaoks leidma lühikese vektori — üksnes avaliku kirjelduse põhjal. See on ülesanne, mida näite 4. samm illustreeris: ilma heade vektoriteta jõuab sama arvutus palju liiga pika lahendini.

Mõõtmes 1024 on parimad teadaolevad meetodid — nii klassikalised kui ka kvantpõhised — sellest kaugel.

Allkirjastamine: kiireKontroll: kiireVo˜ltsimine: raske\boxed{\text{Allkirjastamine: kiire}\quad \text{Kontroll: kiire}\quad \text{Võltsimine: raske}}

17. Mida McGesund sellega konkreetselt teeb

Envelope. Iga allkirjastatud arvustus kannab Ed25519 allkirja. See on kohustuslik variant — klassikaline, väga väike, igas brauseris natiivselt kontrollitav.

Kvantijärgsed templid. Nende kõrval asub üks või kaks kvantiresistentset allkirja. Millised, sõltub paketist:

Pakettsaadaolevad allkirjatasemed
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, mõlemad paralleelselt

Paralleelne variant on teadlikult üleliigne. FALCON toetub NTRU-võredele, ML-DSA moodulvõredele. Kui üks neist kahest perekonnast peaks osutuma nõrgemaks, kui täna eeldatakse, kannab teine edasi.

Ajaankur. Allkirjastamisvõtme sõrmejälg ankurdatakse OpenTimestampsi kaudu Bitcoini plokki. Sellega ei ole tõendatud üksnes see, et allkiri on ehtne, vaid ka see, et ta oli teataval ajahetkel juba olemas — ilma et keegi peaks uskuma meie ajatemplit.

Kõik see arvutatakse lugeja brauseris WASM-mooduli abil. Meie tarnime andmed; kontroll käib külastaja seadmes. Kui me homme võrgust kaoksime, jääks juba korra laaditud arvustus kontrollitavaks.

Nimede kohta: FALCONit standarditakse praegu nimega FN-DSA; kavand on ette nähtud FIPS 206-na, kuid ei ole veel lõpetatud. Seepärast kannavad tasemed McGesundi koodis nimesid FN-DSA-512 ja FN-DSA-1024, isegi kui kõnepruugis räägitakse endiselt FALCONist.

18. Kõige tähtsam intuitsioon

Avalik võti on labürindi täielik kirjeldus. Igaüks tohib seda vaadata.

Allkiri on tõend: „Ma leidsin just selle arvustuse jaoks väga lühikese tee."

Privaatvõti on otseteede tundmine.

Lugeja ei pea otseteid teadma. Ta üksnes mõõdab järele, kas esitatud tee on tõepoolest lühike ja kuulub tõepoolest selle arvustuse juurde. Mõlemat saab ta teha ilma meieta.

FALCON muudab arvustuse punktiks vo˜resja allkirja lu¨hikeseks teeks selle punktini.\boxed{ \begin{array}{c} \text{FALCON muudab arvustuse punktiks võres}\\ \text{ja allkirja lühikeseks teeks selle punktini.} \end{array}}

Kes teksti muudab, nihutab punkti — ja vana tee viib tühjusesse.