Aláírási eljárás

A FALCON matematikai magyarázata

Hogyan írunk alá egy McGesund-értékelést FN-DSA-val (FALCON) — és miért töri meg az aláírást egyetlen megváltoztatott karakter.

Állapot: 2026-09-07

1. Miről van szó

A McGesundnál egy értékelés nem pusztán egy szövegmező az adatbázisban, amelynek hinni kell. Beküldéskor digitálisan aláírjuk, és ezt az aláírást később bármelyik látogató újraszámolhatja a saját böngészőjében.

Ezeknek az aláírásoknak egy részéhez a FALCON eljárást használjuk — pontosabban az FN-DSA-512-t és az FN-DSA-1024-et. Ez a cikk elmagyarázza, mi történik közben matematikailag.

Fontos előrebocsátani:

A FALCON nem titkosítás. Az értékelés szövegét éppen hogy el kell tudni olvasni. A FALCON nem a titkosságot bizonyítja, hanem az eredetet és a sértetlenséget.

2. Mit írunk alá pontosan

Nem a folyószöveget írjuk alá, hanem egy tömör adatobjektumot, amely a szöveget egyértelműen rögzíti:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<cégazonosító>",
  "c":   "<értékelésazonosító>",
  "h":   "<az értékelés szövegének SHA-256 hasítóértéke>",
  "rh":  "<a teljes beküldött adatrekord SHA-256 hasítóértéke>",
  "rv":  1,
  "qh":  "<a QR-envelope SHA-256 hasítóértéke, csak QR-értékeléseknél>",
  "iat": 1757203200
}

Ez a mi mm üzenetünk. A következőket köti össze:

  1. melyik céghez tartozik az értékelés (f),
  2. melyik értékelésről van szó (c),
  3. milyen szöveg állt mögötte — hasítóértékként (h),
  4. összességében milyen adatrekordot küldtek be (rh): szöveg, szívek, geostátusz és az alkalomra vonatkozó adatok, kanonikusan szerializálva és hasítva, az rv sémaverzióban,
  5. melyik QR-kódból származik az értékelés (qh) — QR nélküli értékelésnél ez a mező elmarad,
  6. mikor történt az aláírás (iat).

Egyetlen megváltoztatott karakter az értékelés szövegében megtöri ezt a láncot. Pontosan ez a cél — és az rh bevezetése óta ugyanez érvényes egy utólag áthelyezett szívre vagy egy megváltoztatott geostátuszra is.

3. Az alapprobléma

Az olvasó, aki egy cégprofilra érkezik, két kérdés előtt áll:

  1. Valóban a McGesund rendszeréből származik ez az értékelés?
  2. Módosították-e utólag?

Ehhez egy kulcspár tartozik:

  • egy titkos kulcs — az aláíró szolgáltatásban marad
  • egy nyilvános kulcs — bárkinél lehet

Az aláírás a titkos kulccsal készül, az ellenőrzés a nyilvánossal. Méghozzá az olvasó eszközén, nem a mi szerverünkön.

4. Miért a FALCON?

A mai aláírási eljárások közül sok olyan problémákon alapul, amelyek a klasszikus gépeknek nehezek, a kellően nagy kvantumszámítógépeknek viszont lényegesen könnyebbek lehetnek.

Egy értékelés esetében ez fontosabb, mint egy múlékony üzenetnél: egy értékelésnek öt vagy tíz év múlva is ellenőrizhetőnek kell lennie. Aki ma ír alá, a bejegyzés teljes élettartamára ír alá.

A FALCON ezért rácskriptográfián alapul:

Olyan rácsot építünk, amely matematikailag egyszerűen leírható, de amelyben egy bizonyos keresési feladat rendkívül nehéz.

5. Mi az a matematikai rács?

Két vektor:

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

Az összes egész együtthatós kombináció

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

pontokból álló rácsot ad. Például:

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
Két vektor rácsot feszít ki. Minden pont a kettő egész együtthatós kombinációja — a kijelölt pont kétszer v₁-ből és háromszor v₂-ből keletkezik.

A döntő szempont:

Magát a rácsot könnyű leírni. Bizonyos tulajdonságokat megtalálni benne viszont nagyon nehéz.

6. A titok a rövid vektorokban rejlik

A klasszikus nehéz feladat így hangzik:

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

Ez a legrövidebb vektor problémája. Két dimenzióban végig lehet próbálni. A FALCON 512-es vagy 1024-es dimenzióban dolgozik — ott ez reménytelen.

hosszú bázismajdnem párhuzamoslegrövidebb vektor
Ugyanaz a rács, két leírás. A szürke vektorok is előállítják, de hosszúak és majdnem párhuzamosak — rossz bázis. A rövid vektor az, amit nehéz megtalálni.

A FALCON-nak azonban nem magára a legrövidebb vektorra van szüksége, hanem valami rokon dologra: egy előre adott célponthoz kell közeli rácspontot találnia. Ez is nehéz a megfelelő kiegészítő információ nélkül.

célpont az értékelésbőlközeli rácsponttávoli
Az értékelésből származó célpont (üres kör) nincs rajta a rácson. Egy hozzá közeli rácspontot keresünk — a szaggatott út egy távoli ponthoz szintén megoldása az első feltételnek, csak éppen nem rövid.

7. Polinomok számok helyett

A FALCON NTRU-rácsot használ, és polinomokkal számol. Tehát egyes számok helyett együtthatólistákkal:

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.

A számítás a következő gyűrűben történik:

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

Ez azt jelenti:

  • Zq\mathbb{Z}_q: számolás modulo qq. Például q=7q=7 esetén 10≡310\equiv3, hiszen 10−7=310-7=3.
  • xn=−1x^n=-1: rögzített hosszon tartja a polinomokat.

A FALCON konkrétan a következőket használja:

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

8. A központi trükk

A titkos kulcs négy kis polinomból áll:

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

az NTRU-egyenlettel

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

Ez a négy együtt alkot egy titkos, jól kezelhető rácsbázist — a rács rövid vektorokból álló leírását.

A nyilvános kulcs lényegében egyetlen polinom:

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

A hh-ból ugyanaz a rács adódik, de egy nehézkes bázisban, hosszú vektorokból:

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

Ez a FALCON teljes lényege. Mindkét bázis ugyanazt a rácsot írja le. Csak az egyik használható a számoláshoz, a másik nem.

Elképzelhetjük ezt várostérképként: nyilvános a teljes térkép. Titkos a rövidítések ismerete.

9. Az értékelésből pont lesz

Az aláírás előtt a payload-objektum áthalad egy hasítófüggvényen. A FALCON ehhez a hash-to-point eljárást használja: az üzenetből nem számérték lesz, hanem közvetlenül egy pont a gyűrűben.

Ezenkívül az aláíró szolgáltatás húz egy véletlen saltot, rr-t (320 bit), és azt is belehasítja:

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

A salt nem díszítés. Nélküle ugyanaz az értékelés mindig ugyanazt az aláírást adná, és sok aláírásból rekonstruálható lenne a titkos bázis. Ezért az aláírásba is bekerül.

10. Mi számít érvényes aláírásnak

Egy párt keresünk,

(s1,s2)(s_1,s_2)

két tulajdonsággal:

s1+s2 h≡c(modq)eˊs∥(s1,s2)∥  kicsi.s_1+s_2\,h\equiv c \pmod q \qquad\text{és}\qquad \|(s_1,s_2)\|\;\text{kicsi}.

Az első feltételt önmagában triviális teljesíteni — legyen s2=0s_2=0 és s1=cs_1=c. A második feltétel teszi nehézzé a feladatot.

A ro¨vidseˊg maga az alaˊıˊraˊs.\boxed{\text{A rövidség maga az aláírás.}}

11. Egy teljesen végigszámolt minipélda

Mindent játékméretűre zsugorítunk: csak egyetlen együtthatós polinomokra, azaz közönséges számokra, és

q=97.q=97.

A titkos kulcs. Két kis szám:

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

A nyilvános kulcs. Fennáll, hogy 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, hiszen 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Tehát:

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

A rács. L={(s1,s2):s1+34 s2≡0(mod97)}L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}.

A nyilvános bázis közvetlenül a hh-ból adódik:

(97,0)eˊs(−34,1).(97,0) \quad\text{és}\quad (-34,1).

Mindkettő LL-ben van — és mindkettő hosszú.

A titkos bázist csak az aláíró szolgáltatás ismeri:

(−g,f)=(−5,3)eˊs(−G,F)=(−9,−14),(-g,f)=(-5,3) \quad\text{és}\quad (-G,F)=(-9,-14),

hiszen −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 és −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. A determináns

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

tehát az NTRU-egyenlet teljesül. Mindkét vektor rövid.

1. lépés: Az értékelés hasítása

Tegyük fel, hogy az értékelés payload-objektumából

c=71.c=71.

2. lépés: Egy első, rossz megoldás

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

kielégíti a 71+34⋅0=71≡c71+34\cdot0=71\equiv c összefüggést. A hossza azonban 7171 — sokkal túl hosszú.

3. lépés: Rövidítés a titkos bázissal

Az aláíró szolgáltatás a célpontot a saját rövid bázisában fejezi ki:

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

Ez az a≈−10,25a\approx-10{,}25 és b≈−2,20b\approx-2{,}20 értékekre vezet. Az a=−10a=-10, b=−2b=-2 kerekítéssel a következő rácspont adódik:

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

Ellenőrzés: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, tehát valóban LL-ben van. Kivonva:

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

Hossz:

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

Ez az aláírás.

4. lépés: Ugyanaz az eljárás a nyilvános bázissal

Aki csak a h=34h=34 értéket ismeri, annak a {(97,0),(−34,1)}\{(97,0),(-34,1)\} bázisa van. Ugyanaz a kerekítési számítás ott a (97,0)(97,0) rácspontot adja, és ezzel

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

Ez is érvényes megoldása az egyenletnek — de hétszer hosszabb. Ha az elfogadási korlátot 26 alá állítjuk, akkor értéktelen.

Ugyanaz az algoritmus, ugyanaz a raˊcs, ugyanaz a ceˊlpont.Csak a baˊzis teˊr el — eˊs ezzel az eredmeˊny is.\boxed{ \begin{array}{c} \text{Ugyanaz az algoritmus, ugyanaz a rács, ugyanaz a célpont.}\\ \text{Csak a bázis tér el — és ezzel az eredmény is.} \end{array}}

Ez a FALCON csapóajtaja egyetlen sorban.

5. lépés: A böngésző ellenőriz

A böngésző megkapja az értékelést, a saltot és az s2=2s_2=2 értéket. Újraszámolja a hasítóértéket, c=71c=71-et kap, rekonstruálja

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

és ellenőrzi a hosszt:

∥(3,2)∥=13  ≤  β⟹Az alaˊıˊraˊs eˊrveˊnyes\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Az aláírás érvényes}}

6. lépés: Valaki megváltoztatja az értékelés szövegét

Ha a szöveget utólag megváltoztatják, megváltozik a tartalom hasítóértéke, és ezzel a pont is, mondjuk

c′=40.c'=40.

A régi aláírás (3,2)(3,2) marad, de

3+34⋅2=71≠40⟹Az alaˊıˊraˊs eˊrveˊnytelen3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Az aláírás érvénytelen}}

Egy értékelést törölni tudunk. Megváltoztatni viszont nem tudjuk anélkül, hogy az feltűnne.

Őszinte megjegyzés a példához

Két dimenzióban a támadó egyszerűen végigpróbálhatja a rövid megoldásokat — c′=40c'=40 esetén például a (6,1)(6,1) párt. A példa nem biztonságos; csupán a mechanizmust mutatja meg. A FALCON-1024-nél a vektornak 2048 együtthatója van, és ott a végigpróbálás sehová sem vezet.

12. Miért nem egyszerűen kerekítünk?

A 3. lépésben szereplő eljárás neve Babai-kerekítés. Tankönyvi példához elegendő — valódi aláírási eljáráshoz nem.

Az ok: a kerekített aláírások nem egyenletesen oszlanak el. Az alakjuk a titkos bázis geometriájától függ. Elég sok aláírásból ez a geometria rekonstruálható lenne — és ezzel a titkos kulcs is. Pontosan ezen buktak el korábbi rácsalapú aláírási eljárások.

A FALCON ezért a rövid vektorokat a rács feletti diszkrét Gauss-eloszlásból húzza:

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

A célponthoz közeli értékek valószínűbbek, de hogy pontosan melyiket választja, az véletlenszerű. Az eredmény olyan eloszlás, amely semmit nem árul el a használt bázisról — matematikailag: nem megkülönböztethető egy olyan eloszlástól, amely csak magától a rácstól függ.

Ez a mintavételező a FALCON legigényesebb része. Rekurzívan fut végig egy fastruktúrán, és lebegőpontos számokkal dolgozik — ez teszi kényessé az implementációt, és ez a fő oka annak, hogy a FALCON-t nehezebb helyesen megvalósítani, mint az ML-DSA-t.

13. Mi kerül ténylegesen továbbításra

Az aláírás a következőkből áll:

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

Csak az s2s_2 — nem a pár. Az s1s_1-et az ellenőrző maga számolja ki:

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

Mivel az s2s_2 együtthatói kicsik és nulla körül szóródnak, erősen tömöríthetők. Ez az oka a FALCON feltűnően tömör aláírásainak:

nyilvános kulcsaláírás
FALCON-512897 B~666 B
FALCON-10241793 B~1280 B

Összehasonlításképpen: az ML-DSA-87 4627 bájtot igényel. A McGesundnál viszont egyik ilyen aláírás sem kerül magába a QR-kódba — a matrica csak az Ed25519-borítékot hordozza; a poszt-kvantum bélyegzők az adatrekord mellett vannak, és ellenőrzéskor töltődnek be. A méret tehát itt nem a nyomtathatóságról dönt, hanem a tárolásról és az átvitelről: egy FALCON-bélyegző jó negyedakkora, mint egy ML-DSA-bélyegző.

14. Miért ellenőriz gyorsan a FALCON

A naiv polinomszorzás költsége

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

A gyors Fourier-transzformációval ez körülbelül a következőre csökken:

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

n=1024n=1024 esetén ez az egymillió és a nagyjából tízezer művelet közötti különbség. Ezért fut le az ellenőrzés a látogató böngészőjében ezredmásodpercek alatt — és ezért van benne az F a névben:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. A folyamat képben

ALÁÍRÓ SZOLGÁLTATÁS (MCGESUND)A LÁTOGATÓ BÖNGÉSZŐJEtitkos kulcs (f, g, F, G — rövid bázis)payload m = {cég, értékelés, h, rh, iat}salt r + HashToPoint(r ‖ m) = cGauss-mintavétel: rövid vektor (s₁, s₂)aláírás σ = (r, s₂) + kidértékelés + σ + h nyilvános kulcsc újraszámolása, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?érvényesérvénytelen
A payloadtól a böngészőben megjelenő pipáig. Az elválasztó vonal fölött minden egyszer, a beküldéskor történik, alatta minden látogatónál újra — az ő eszközén, a nyilvános kulccsal.

16. Miért bukik el a támadó

Ismeri a hh-t, és ezzel az egész rácsot. Ismeri a cc célpontot is, amint az értékelés nyilvános. Ami hiányzik neki, az a rövid bázis.

Egy értékelés hamisításához egy maga választotta cc-hez kellene rövid vektort találnia — pusztán a nyilvános leírásból. Ez az a feladat, amelyet a példa 4. lépése szemléltetett: a jó vektorok nélkül ugyanaz a számítás sokkal túl hosszú megoldáshoz vezet.

Az 1024-es dimenzióban a legjobb ismert eljárások — klasszikusak és kvantumalapúak egyaránt — messze vannak ettől.

Alaˊıˊraˊs: gyorsElleno˝rzeˊs: gyorsHamisıˊtaˊs: neheˊz\boxed{\text{Aláírás: gyors}\quad \text{Ellenőrzés: gyors}\quad \text{Hamisítás: nehéz}}

17. Mit kezd ezzel konkrétan a McGesund

A boríték. Minden aláírt értékelés hordoz egy Ed25519-aláírást. Ez a kötelező változat — klasszikus, nagyon kicsi, minden böngészőben natívan ellenőrizhető.

A poszt-kvantum bélyegzők. Emellett egy vagy két kvantumrezisztens aláírás található. Hogy melyik, az a csomagtól függ:

Csomagelérhető aláírási szintek
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, mindkettő párhuzamosan

A párhuzamos változat szándékosan redundáns. A FALCON NTRU-rácsokon áll, az ML-DSA modulrácsokon. Ha a két család egyike gyengébbnek bizonyulna a ma feltételezettnél, a másik tovább visz.

Az időhorgony. Az aláírókulcs ujjlenyomatát az OpenTimestamps segítségével egy Bitcoin-blokkban rögzítjük. Ezzel nemcsak az igazolt, hogy az aláírás valódi, hanem az is, hogy egy adott időpontban már létezett — anélkül, hogy bárkinek hinnie kellene a mi időbélyegünknek.

Mindezt az olvasó böngészőjében számoljuk, egy WASM-modulon keresztül. Mi az adatokat szállítjuk; az ellenőrzés a látogató eszközén fut. Ha holnap lekapcsolnánk a hálózatról, egy egyszer betöltött értékelés akkor is ellenőrizhető maradna.

A nevek elhelyezéséhez: a FALCON-t jelenleg FN-DSA néven szabványosítják; a tervezetet FIPS 206-ként tervezik, de még nem zárult le. Ezért hívjuk a McGesund kódjában a szinteket FN-DSA-512-nek és FN-DSA-1024-nek, még ha a köznyelvben továbbra is FALCON-ról esik szó.

18. A legfontosabb szemlélet

A nyilvános kulcs egy labirintus teljes leírása. Bárki megnézheti.

Az aláírás a bizonyíték: „Pontosan ehhez az értékeléshez találtam egy nagyon rövid utat."

A titkos kulcs a rövidítések ismerete.

Az olvasónak nem kell ismernie a rövidítéseket. Csak azt méri le, hogy a bemutatott út valóban rövid-e, és valóban ehhez az értékeléshez tartozik-e. Mindkettőt meg tudja tenni nélkülünk.

A FALCON az eˊrteˊkeleˊst egy raˊcs pontjaˊvaˊ alakıˊtja,az alaˊıˊraˊst pedig egy odavezeto˝ ro¨vid uˊttaˊ.\boxed{ \begin{array}{c} \text{A FALCON az értékelést egy rács pontjává alakítja,}\\ \text{az aláírást pedig egy odavezető rövid úttá.} \end{array}}

Aki megváltoztatja a szöveget, elmozdítja a pontot — és a régi út a semmibe vezet.