Metodi ta' firma

FALCON spjegat matematikament

Kif reċensjoni ta' McGesund tiġi ffirmata b'FN-DSA (FALCON) — u għaliex karattru wieħed mibdul ikisser il-firma.

Aġġornat: 2026-09-07

1. Dwar xiex jitkellem dan l-artiklu

Reċensjoni fuq McGesund mhijiex kaxxa ta' test f'bażi tad-data li wieħed sempliċement irid jemminha. Meta tintbagħat tiġi iffirmata diġitalment, u kull viżitatur jista' aktar tard jerġa' jikkalkula din il-firma fil-browser tiegħu stess.

Għal parti minn dawn il-firem nużaw FALCON — b'mod aktar preċiż FN-DSA-512 u FN-DSA-1024. Dan l-artiklu jispjega x'jiġri matematikament waqt dan.

Nota importanti minn qabel:

FALCON mhuwiex kriptaġġ. It-test tar-reċensjoni suppost jinqara. FALCON ma jipprovax is-segretezza, iżda l-oriġini u l-integrità.

2. X'jiġi ffirmat eżattament

Dak li jiġi ffirmat mhuwiex it-test kurrenti, iżda oġġett ta' data kompatt li jissiġilla b'mod univoku t-test:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID tal-kumpanija>",
  "c":   "<ID tar-reċensjoni>",
  "h":   "<SHA-256 tat-test tar-reċensjoni>",
  "rh":  "<SHA-256 tar-rekord sħiħ tas-sottomissjoni>",
  "rv":  1,
  "qh":  "<SHA-256 tal-envelope QR, biss għal reċensjonijiet bil-QR>",
  "iat": 1757203200
}

Dan huwa l-messaġġ tagħna mm. Jorbot flimkien:

  1. ma' liema kumpanija tappartjeni r-reċensjoni (f),
  2. dwar liema reċensjoni qed nitkellmu (c),
  3. liema test kien warajha — bħala valur hash (h),
  4. liema rekord ġie sottomess kollu kemm hu (rh): it-test, il-qlub, l-istat ġeografiku u d-dettalji tal-okkażjoni, serjalizzati b'mod kanoniku u hashjati, fil-verżjoni tal-iskema rv,
  5. minn liema kodiċi QR ġejja r-reċensjoni (qh) — f'reċensjoni bla QR il-qasam jaqa',
  6. meta saret il-firma (iat).

Karattru wieħed mibdul fit-test tar-reċensjoni jkisser din il-katina. Dan hu eżattament l-iskop — u minn meta daħal rh l-istess jgħodd għal qalb imċaqilqa wara jew għal stat ġeografiku mibdul.

3. Il-problema bażika

Qarrej li jasal fuq profil ta' kumpanija jkollu quddiemu żewġ mistoqsijiet:

  1. Din ir-reċensjoni tabilħaqq ġejja mis-sistema ta' McGesund?
  2. Ġiet mibdula wara?

Għal dan jeżisti par ta' ċwievet:

  • ċavetta privata — tibqa' fis-servizz tal-firma
  • ċavetta pubblika — jista' jkollu kulħadd

L-iffirmar isir bil-privata, il-verifika bil-pubblika. U dan fuq l-apparat tal-qarrej, mhux fuq is-server tagħna.

4. Għaliex FALCON?

Ħafna metodi ta' firma tal-lum jistrieħu fuq problemi li għall-kompjuters klassiċi huma diffiċli, iżda li għal kompjuters kwantistiċi kbar biżżejjed jistgħu jsiru ferm eħfef.

Fil-każ ta' reċensjoni dan huwa aktar rilevanti milli fil-każ ta' messaġġ li jgħaddi malajr: reċensjoni għandha tibqa' verifikabbli fi ħames jew għaxar snin oħra. Min jiffirma llum, jiffirma għall-ħajja kollha tal-entrata.

Għalhekk FALCON jistrieħ fuq il-kriptografija tal-lattiċi:

Wieħed jibni lattiċe li jista' jiġi deskritt matematikament b'mod sempliċi, imma li fih kompitu partikolari ta' tiftix huwa diffiċli ħafna.

5. X'inhu lattiċe matematiku?

Żewġ vetturi:

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

Il-kombinazzjonijiet kollha b'numri sħaħ

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

jagħtu lattiċe ta' punti. Pereżempju:

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
Żewġ vetturi jiftħu lattiċe. Kull punt huwa kombinazzjoni b'numri sħaħ tat-tnejn — dak immarkat joħroġ minn darbtejn v₁ u tliet darbiet v₂.

Dak li jgħodd huwa:

Il-lattiċe nnifsu huwa faċli biex tiddeskrivih. Li ssib ċerti proprjetajiet ġo fih huwa diffiċli ħafna.

6. Is-sigriet huma l-vetturi qosra

Il-kompitu diffiċli klassiku jgħid:

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

Dan huwa l-Shortest Vector Problem. F'żewġ dimensjonijiet wieħed jista' jipprova l-possibbiltajiet kollha. FALCON jaħdem f'dimensjoni 512 jew 1024 — hemmhekk dan huwa bla tama.

bażi twilakważi parallelil-iqsar vettur
L-istess lattiċe, żewġ deskrizzjonijiet. Il-vetturi griżi jiġġenerawh ukoll, imma huma twal u kważi paralleli — bażi ħażina. Il-vettur qasir huwa dak li huwa diffiċli ssibu.

Madankollu FALCON ma jeħtieġx l-iqsar vettur fih innifsu, iżda xi ħaġa relatata: għal punt mira mogħti irid isib punt tal-lattiċe qrib tiegħu. Anki dan huwa diffiċli mingħajr l-informazzjoni addizzjonali t-tajba.

punt mira mir-reċensjonipunt tal-lattiċe qribimbiegħed
Il-punt mira mir-reċensjoni (ċirku vojt) ma jinsabx fil-lattiċe. Qed jitfittex punt tal-lattiċe eżatt maġenbu — it-triq mitquba lejn punt imbiegħed hija wkoll soluzzjoni tal-ewwel kundizzjoni, imma sempliċement mhijiex qasira.

7. Polinomji minflok numri

FALCON juża lattiċe NTRU u jaħdem bil-polinomji. Mela minflok numri singoli, b'listi ta' koeffiċjenti:

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.

Il-kalkolu jsir fl-anell

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

Dan ifisser:

  • Zq\mathbb{Z}_q: kalkolu modulo qq. B'q=7q=7 pereżempju 10≡310\equiv3, għax 10−7=310-7=3.
  • xn=−1x^n=-1: iżomm il-polinomji f'tul fiss.

FALCON juża konkretament:

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

8. It-trikk ċentrali

Iċ-ċavetta privata tikkonsisti f'erba' polinomji żgħar

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

bl-ekwazzjoni NTRU

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

Dawn l-erbgħa jiffurmaw flimkien bażi sigrieta u tajba tal-lattiċe — deskrizzjoni tal-lattiċe magħmula minn vetturi qosra.

Iċ-ċavetta pubblika hija essenzjalment polinomju wieħed:

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

Minn hh joħroġ l-istess lattiċe, imma f'bażi goffa magħmula minn vetturi twal:

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

Dan hu l-qalba kollha ta' FALCON. Iż-żewġ bażijiet jiddeskrivu l-istess lattiċe. Waħda biss minnhom hija tajba għall-kalkolu, u l-oħra le.

Wieħed jista' jimmaġina dan bħal pjanta ta' belt: pubblika hija l-mappa sħiħa. Sigriet huwa l-għarfien tal-mogħdijiet qosra.

9. Ir-reċensjoni ssir punt

Qabel ma ssir il-firma, l-oġġett tal-payload jgħaddi minn funzjoni hash. Għal dan FALCON juża Hash-to-Point: mill-messaġġ ma joħroġx valur numeriku, iżda direttament punt fl-anell.

Barra minn hekk is-servizz tal-firma jiġbed salt każwali rr (320 bit) u jħalltu fil-hash:

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

Is-salt mhuwiex żejjed. Mingħajru l-istess reċensjoni kienet tagħti dejjem l-istess firma, u minn ħafna firem kienet tista' tinbena mill-ġdid il-bażi sigrieta. Għalhekk jissieħeb ukoll mal-firma.

10. X'inhi firma valida

Qed jitfittex par

(s1,s2)(s_1,s_2)

b'żewġ proprjetajiet:

s1+s2 h≡c(modq)u∥(s1,s2)∥  z˙għira.s_1+s_2\,h\equiv c \pmod q \qquad\text{u}\qquad \|(s_1,s_2)\|\;\text{żgħira}.

L-ewwel kundizzjoni waħedha hija triviali biex tiġi sodisfatta — tissetja s2=0s_2=0 u s1=cs_1=c. It-tieni kundizzjoni hija dik li tagħmel il-kompitu diffiċli.

Il-qosor huwa l-firma.\boxed{\text{Il-qosor huwa l-firma.}}

11. Eżempju żgħir kalkulat kollu kemm hu

Inċekknu kollox għal daqs ta' logħba: polinomji b'koeffiċjent wieħed biss, mela numri ordinarji, u

q=97.q=97.

Iċ-ċavetta sigrieta. Żewġ numri żgħar:

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

Iċ-ċavetta pubblika. Jgħodd 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, għax 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Mela:

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

Il-lattiċe. L={(s1,s2):s1+34 s2≡0(mod97)}L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}.

Il-bażi pubblika toħroġ direttament minn hh:

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

It-tnejn jinsabu f'LL — u t-tnejn huma twal.

Il-bażi sigrieta jafha biss is-servizz tal-firma:

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

għax −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 u −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Id-determinant huwa

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

allura l-ekwazzjoni NTRU toħroġ. Iż-żewġ vetturi huma qosra.

Pass 1: Il-hash tar-reċensjoni

Ejja nassumu li l-oġġett tal-payload tar-reċensjoni jagħti

c=71.c=71.

Pass 2: L-ewwel soluzzjoni, ħażina

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

tissodisfa 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Imma t-tul huwa 7171 — twil wisq.

Pass 3: Tqassir bil-bażi sigrieta

Is-servizz tal-firma jesprimi l-punt mira fil-bażi qasira tiegħu:

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

Dan iwassal għal a≈−10.25a\approx-10.25 u b≈−2.20b\approx-2.20. Arrotondat għal a=−10a=-10, b=−2b=-2, joħroġ il-punt tal-lattiċe

−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, allura tabilħaqq f'LL. Innaqqsu:

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

Tul:

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

Din hija l-firma.

Pass 4: L-istess metodu bil-bażi pubblika

Min jaf biss h=34h=34 għandu l-bażi {(97,0),(−34,1)}\{(97,0),(-34,1)\}. L-istess kalkolu ta' arrotondament jagħti hemmhekk il-punt tal-lattiċe (97,0)(97,0) u b'hekk

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

Ukoll soluzzjoni valida tal-ekwazzjoni — imma seba' darbiet itwal. Jekk il-limitu tal-aċċettazzjoni jiġi ssettjat taħt 26, hija bla valur.

L-istess algoritmu, l-istess lattic˙e, l-istess punt mira.Tvarja biss il-baz˙i — u magħha r-riz˙ultat.\boxed{ \begin{array}{c} \text{L-istess algoritmu, l-istess lattiċe, l-istess punt mira.}\\ \text{Tvarja biss il-bażi — u magħha r-riżultat.} \end{array}}

Din hija l-bieba moħbija ta' FALCON f'linja waħda.

Pass 5: Il-browser jivverifika

Il-browser jirċievi r-reċensjoni, is-salt u s2=2s_2=2. Jerġa' jikkalkula l-hash, jikseb c=71c=71, jirrikostruwixxi

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

u jivverifika t-tul:

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

Pass 6: Xi ħadd ibiddel it-test tar-reċensjoni

Jekk it-test jinbidel wara, jinbidel il-hash tal-kontenut u miegħu l-punt, ejja ngħidu

c′=40.c'=40.

Il-firma l-qadima tibqa' (3,2)(3,2), imma

3+34⋅2=71≠40⟹Firma mhux valida3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Firma mhux valida}}

Nistgħu nħassru reċensjoni. Ma nistgħux nibdluha mingħajr ma jinduna ħadd.

Nota ta' onestà dwar l-eżempju

F'żewġ dimensjonijiet attakkant jista' sempliċement jipprova soluzzjonijiet qosra waħda waħda — għal c′=40c'=40 pereżempju (6,1)(6,1). L-eżempju mhuwiex sigur; juri biss il-mekkaniżmu. F'FALCON-1024 il-vettur għandu 2048 koeffiċjent, u hemmhekk il-provi wieħed wieħed ma jwasslu mkien.

12. Għaliex ma jsirx sempliċement arrotondament?

Il-metodu tal-Pass 3 jissejjaħ arrotondament ta' Babai. Għal eżempju ta' ktieb tal-iskola huwa biżżejjed — għal metodu ta' firma veru le.

Ir-raġuni: il-firem arrotondati ma jinfirxux b'mod uniformi. Il-forma tagħhom tiddependi mill-ġeometrija tal-bażi sigrieta. Minn firem biżżejjed din il-ġeometrija tista' tinbena mill-ġdid — u magħha ċ-ċavetta privata. Eżattament fuq dan waqgħu metodi ta' firma bbażati fuq lattiċi ta' qabel.

Għalhekk FALCON jiġbed il-vetturi qosra minn distribuzzjoni Gawssjana diskreta fuq il-lattiċe:

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

Valuri qrib il-punt mira huma aktar probabbli, imma liema wieħed eżattament jintgħażel huwa każwali. Ir-riżultat huwa distribuzzjoni li ma tikxef xejn dwar il-bażi użata — matematikament: ma tistax tingħaraf minn distribuzzjoni li tiddependi biss mil-lattiċe nnifsu.

Dan is-sampler huwa l-aktar parti eżiġenti ta' FALCON. Jaħdem b'mod rikorsiv fuq struttura ta' siġra u juża numri f'virgola mobbli — u dan jagħmel l-implimentazzjoni delikata u huwa r-raġuni prinċipali għaliex FALCON huwa aktar diffiċli biex jiġi implimentat b'mod korrett minn ML-DSA.

13. X'jiġi tabilħaqq trażmess

Il-firma tikkonsisti f'

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

Biss s2s_2 — mhux il-par. s1s_1 jikkalkulah il-verifikatur stess:

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

Billi l-koeffiċjenti ta' s2s_2 huma żgħar u jinfirxu madwar iż-żero, jistgħu jiġu kkompressati bil-kbir. Din hija r-raġuni għall-firem notevolment kompatti ta' FALCON:

ċavetta pubblikafirma
FALCON-512897 B~666 B
FALCON-10241,793 B~1,280 B

Bħala paragun: ML-DSA-87 jeħtieġ 4,627 byte. F'McGesund, madankollu, l-ebda waħda minn dawn il-firem ma tinsab fil-kodiċi QR innifsu — l-istikka ġġorr biss l-envelope Ed25519; it-timbri post-kwantistiċi jinsabu mar-rekord u jinġiebu waqt il-verifika. Mela hawnhekk id-daqs ma jiddeċidix dwar il-possibbiltà tal-istampar, iżda dwar il-ħżin u t-trażmissjoni: timbru FALCON huwa madwar kwart tad-daqs ta' timbru ML-DSA.

14. Għaliex FALCON jivverifika malajr

Il-multiplikazzjoni ta' polinomji b'mod naïv tiswa

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

Bit-trasformazzjoni ta' Fourier mgħaġġla dan jinżel għal bejn wieħed u ieħor

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

B'n=1024n=1024 din hija d-differenza bejn miljun u madwar għaxart elef operazzjoni. Għalhekk il-verifika fil-browser ta' viżitatur tgħaddi f'millisekondi — u għalhekk hemm l-F fl-isem:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Il-proċess f'stampa

SERVIZZ TAL-FIRMA (MCGESUND)BROWSER TAL-VIŻITATURċavetta privata (f, g, F, G — bażi qasira)Payload m = {Kumpanija, Reċensjoni, h, rh, iat}Salt r + HashToPoint(r ‖ m) = cKampjunar Gawssjan: vettur qasir (s₁, s₂)Firma σ = (r, s₂) + kidReċensjoni + σ + ċavetta pubblika hikkalkula c mill-ġdid, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?validamhux valida
Mill-payload sal-marka tal-approvazzjoni fil-browser. Kollox fuq il-linja diviżorja jiġri darba waħda meta tintbagħat ir-reċensjoni; kollox taħtha jiġri mill-ġdid għal kull viżitatur — fuq l-apparat tiegħu, biċ-ċavetta pubblika.

16. Għaliex attakkant ifalli

Huwa jaf hh u b'hekk il-lattiċe kollu. Jaf ukoll il-punt mira cc, hekk kif ir-reċensjoni tkun pubblika. Dak li jonqsu hija l-bażi qasira.

Biex jiffalsifika reċensjoni, ikollu jsib vettur qasir għal cc magħżul minnu stess — u dan mid-deskrizzjoni pubblika biss. Dan huwa l-kompitu li llustra l-Pass 4 tal-eżempju: mingħajr il-vetturi t-tajbin, l-istess kalkolu jispiċċa f'soluzzjoni twila wisq.

F'dimensjoni 1024 l-aħjar metodi magħrufa — kemm klassiċi kif ukoll kwantistiċi — huma 'l bogħod ħafna minn dan.

Iffirmar: malajrVerifika: malajrFalsifikazzjoni: diffic˙li\boxed{\text{Iffirmar: malajr}\quad \text{Verifika: malajr}\quad \text{Falsifikazzjoni: diffiċli}}

17. X'tagħmel McGesund konkretament b'dan

L-envelope. Kull reċensjoni ffirmata ġġorr firma Ed25519. Din hija l-varjant obbligatorju — klassiku, żgħir ħafna, u verifikabbli b'mod nattiv f'kull browser.

It-timbri post-kwantistiċi. Maġenbu jinsabu firma waħda jew tnejn reżistenti għall-kwanti. Liema minnhom jiddependi mill-pjan:

Pjanlivelli ta' firma disponibbli
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, it-tnejn f'parallel

Il-varjant parallel huwa ridondanti apposta. FALCON jistrieħ fuq lattiċi NTRU, ML-DSA fuq lattiċi ta' moduli. Jekk waħda miż-żewġ familji tirriżulta aktar dgħajfa milli maħsub illum, l-oħra tkompli żżomm.

L-ankra taż-żmien. Il-marka tas-swaba' taċ-ċavetta tal-firma tiġi ankrata permezz ta' OpenTimestamps ġo blokk ta' Bitcoin. B'hekk mhux biss huwa ppruvat li l-firma hija ġenwina, iżda wkoll li kienet diġà teżisti f'mument partikolari — mingħajr ma xi ħadd irid jemmen it-timbru taż-żmien tagħna.

Dan kollu jiġi kkalkulat fil-browser tal-qarrej, permezz ta' modulu WASM. Aħna nfornu d-data; il-verifika ssir fuq l-apparat tal-viżitatur. Li kieku għada nitilqu mill-internet, reċensjoni li tkun diġà tniżżlet tibqa' verifikabbli.

Dwar l-ismijiet: FALCON bħalissa qed jiġi standardizzat bħala FN-DSA; l-abbozz huwa maħsub bħala FIPS 206, imma għadu ma ġiex konkluż. Għalhekk fil-kodiċi ta' McGesund il-livelli jissejħu FN-DSA-512 u FN-DSA-1024, anki jekk fl-użu komuni għadu jissemma FALCON.

18. L-aktar intwizzjoni importanti

Iċ-ċavetta pubblika hija d-deskrizzjoni sħiħa ta' labirint. Kulħadd jista' jaraha.

Il-firma hija l-prova: “Sibt triq qasira ħafna għal eżattament din ir-reċensjoni.”

Iċ-ċavetta privata hija l-għarfien tal-mogħdijiet qosra.

Il-qarrej m'għandux għalfejn jaf il-mogħdijiet qosra. Huwa jkejjel biss jekk it-triq imressqa hijiex tabilħaqq qasira u jekk tappartjenix tabilħaqq lil din ir-reċensjoni. It-tnejn jista' jagħmilhom mingħajrna.

FALCON idawwar rec˙ensjoni f’punt g˙o lattic˙eu l-firma fi triq qasira lejh.\boxed{ \begin{array}{c} \text{FALCON idawwar reċensjoni f'punt ġo lattiċe}\\ \text{u l-firma fi triq qasira lejh.} \end{array}}

Min ibiddel it-test, iċaqlaq il-punt — u t-triq il-qadima twassal fix-xejn.