Procedimenti di firma

FALCON spiegato matematicamente

Come una recensione di McGesund viene firmata con FN-DSA (FALCON) — e perché un carattere modificato rompe la firma.

Aggiornato: 2026-09-07

1. Di che cosa si tratta

Una recensione su McGesund non è un campo di testo in una banca dati a cui bisogna semplicemente credere. Al momento dell'invio viene firmata digitalmente, e ogni visitatore può ricalcolare questa firma in seguito nel proprio browser.

Per una parte di queste firme utilizziamo FALCON — più precisamente FN-DSA-512 e FN-DSA-1024. Questo contributo spiega che cosa accade matematicamente.

Una precisazione preliminare:

FALCON non è una cifratura. Il testo della recensione è fatto proprio per essere letto. FALCON non dimostra la riservatezza, bensì origine e integrità.

2. Che cosa viene firmato esattamente

Non viene firmato il testo discorsivo, bensì un oggetto dati compatto che fissa il testo in modo univoco:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID azienda>",
  "c":   "<ID recensione>",
  "h":   "<SHA-256 del testo della recensione>",
  "rh":  "<SHA-256 dell'intero record inviato>",
  "rv":  1,
  "qh":  "<SHA-256 dell'envelope QR, solo per recensioni via QR>",
  "iat": 1757203200
}

Questo è il nostro messaggio mm. Lega insieme:

  1. a quale azienda appartiene la recensione (f),
  2. di quale recensione si tratta (c),
  3. quale testo vi stava dietro — come valore hash (h),
  4. quale record è stato inviato nel suo insieme (rh): testo, cuori, stato geografico e indicazioni sull'occasione, serializzati canonicamente e sottoposti a hash, nella versione di schema rv,
  5. da quale QR code proviene la recensione (qh) — in una recensione senza QR il campo decade,
  6. quando è stata apposta la firma (iat).

Un carattere modificato nel testo della recensione rompe questa catena. È esattamente questo lo scopo — e da quando esiste rh lo stesso vale per un cuore spostato successivamente o per uno stato geografico modificato.

3. Il problema di fondo

Un lettore che arriva sul profilo di un'azienda si trova davanti a due domande:

  1. Questa recensione proviene davvero dal sistema McGesund?
  2. È stata modificata in un secondo momento?

A tal fine esiste una coppia di chiavi:

  • una chiave privata — resta nel servizio di firma
  • una chiave pubblica — può averla chiunque

Si firma con la chiave privata, si verifica con quella pubblica. E precisamente sul dispositivo del lettore, non sul nostro server.

4. Perché FALCON?

Molti procedimenti di firma odierni si fondano su problemi che per i calcolatori classici sono difficili, ma che per computer quantistici sufficientemente grandi potrebbero diventare nettamente più facili.

Per una recensione ciò è più rilevante che per un messaggio effimero: una recensione deve essere verificabile ancora fra cinque o dieci anni. Chi firma oggi, firma per l'intera vita della voce.

FALCON si fonda perciò sulla crittografia su reticoli:

Si costruisce un reticolo descrivibile in modo matematicamente semplice, nel quale un determinato compito di ricerca è estremamente difficile.

5. Che cos'è un reticolo matematico?

Due vettori:

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

Tutte le combinazioni a coefficienti interi

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

danno un reticolo di punti. Per esempio:

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
Due vettori generano un reticolo. Ogni punto è una combinazione a coefficienti interi dei due — quello evidenziato nasce da due volte v₁ e tre volte v₂.

Decisivo è questo:

Il reticolo in sé è facile da descrivere. Trovarvi determinate proprietà è molto difficile.

6. Il segreto sono i vettori corti

Il classico compito difficile recita:

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

Questo è lo Shortest Vector Problem. In due dimensioni si può risolvere per tentativi. FALCON lavora in dimensione 512 o 1024 — lì è senza speranza.

base lungaquasi parallelivettore più corto
Lo stesso reticolo, due descrizioni. Anche i vettori grigi lo generano, ma sono lunghi e quasi paralleli — una base cattiva. Il vettore corto è ciò che è difficile da trovare.

A FALCON non serve però il vettore più corto in assoluto, bensì qualcosa di affine: trovare, per un punto obiettivo dato, un punto reticolare vicino. Anche questo è difficile senza l'informazione aggiuntiva giusta.

punto obiettivo dalla recensionepunto reticolare vicinolontano
Il punto obiettivo ricavato dalla recensione (cerchio vuoto) non giace nel reticolo. Si cerca un punto reticolare lì accanto — il percorso tratteggiato verso un punto lontano è anch'esso una soluzione della prima condizione, ma appunto non è corto.

7. Polinomi invece di numeri

FALCON utilizza un reticolo NTRU e calcola con polinomi. Dunque non con singoli numeri, ma con liste di coefficienti:

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.

Si calcola nell'anello

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

Ciò significa:

  • Zq\mathbb{Z}_q: calcolare modulo qq. Con q=7q=7, per esempio, 10≡310\equiv3, poiché 10−7=310-7=3.
  • xn=−1x^n=-1: mantiene i polinomi a lunghezza fissa.

FALCON usa concretamente:

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

8. Il trucco centrale

La chiave privata è composta da quattro piccoli polinomi

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

con l'equazione NTRU

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

Questi quattro formano insieme una base reticolare segreta e ben condizionata — una descrizione del reticolo fatta di vettori corti.

La chiave pubblica è in sostanza un unico polinomio:

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

Da hh risulta lo stesso reticolo, ma in una base scomoda fatta di vettori lunghi:

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

È questo tutto il nocciolo di FALCON. Entrambe le basi descrivono lo stesso reticolo. Solo che una è utilizzabile per il calcolo e l'altra no.

Ce lo si può immaginare come una pianta della città: pubblica è la mappa completa. Segreta è la conoscenza delle scorciatoie.

9. La recensione diventa un punto

Prima di firmare, l'oggetto payload passa attraverso una funzione hash. FALCON usa a tal fine Hash-to-Point: dal messaggio non si ricava un valore numerico, bensì direttamente un punto nell'anello.

Inoltre il servizio di firma estrae un salt casuale rr (320 bit) e lo include nell'hash:

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

Il salt non è un accessorio. Senza di esso la stessa recensione darebbe sempre la stessa firma, e da molte firme si potrebbe ricostruire la base segreta. Per questo viaggia insieme alla firma.

10. Che cos'è una firma valida

Si cerca una coppia

(s1,s2)(s_1,s_2)

con due proprietà:

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

La prima condizione da sola è banale da soddisfare — basta porre s2=0s_2=0 e s1=cs_1=c. È la seconda condizione a rendere difficile il compito.

La brevitaˋ eˋ la firma.\boxed{\text{La brevità è la firma.}}

11. Un mini-esempio calcolato per intero

Riduciamo tutto a dimensioni giocattolo: polinomi con un solo coefficiente, dunque numeri ordinari, e

q=97.q=97.

La chiave segreta. Due piccoli numeri:

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

La chiave pubblica. Si ha 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, poiché 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Dunque:

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

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

La base pubblica si ricava direttamente da hh:

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

Entrambi giacciono in LL — ed entrambi sono lunghi.

La base segreta la conosce solo il servizio di firma:

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

poiché −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 e −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Il determinante è

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

l'equazione NTRU torna dunque. Entrambi i vettori sono corti.

Passo 1: fare l'hash della recensione

Supponiamo che l'oggetto payload della recensione dia

c=71.c=71.

Passo 2: una prima soluzione, cattiva

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

soddisfa 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Ma la lunghezza è 7171 — troppo lunga.

Passo 3: accorciare con la base segreta

Il servizio di firma esprime il punto obiettivo nella sua base corta:

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

Ciò porta ad a≈−10,25a\approx-10{,}25 e b≈−2,20b\approx-2{,}20. Arrotondando ad a=−10a=-10, b=−2b=-2 si ottiene il punto reticolare

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

Controllo: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, dunque effettivamente in LL. Sottraendo:

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

Lunghezza:

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

Questa è la firma.

Passo 4: lo stesso procedimento con la base pubblica

Chi conosce solo h=34h=34 ha la base {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Lo stesso calcolo di arrotondamento fornisce lì il punto reticolare (97,0)(97,0) e quindi

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

Anche questa è una soluzione valida dell'equazione — ma sette volte più lunga. Se la soglia di accettazione viene posta al di sotto di 26, essa è priva di valore.

Stesso algoritmo, stesso reticolo, stesso punto obiettivo.Cambia solo la base — e con essa il risultato.\boxed{ \begin{array}{c} \text{Stesso algoritmo, stesso reticolo, stesso punto obiettivo.}\\ \text{Cambia solo la base — e con essa il risultato.} \end{array}}

Questa è la trapdoor di FALCON in una riga.

Passo 5: il browser verifica

Il browser riceve la recensione, il salt e s2=2s_2=2. Ricalcola l'hash, ottiene c=71c=71, ricostruisce

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

e verifica la lunghezza:

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

Passo 6: qualcuno modifica il testo della recensione

Se il testo viene modificato in un secondo momento, cambia l'hash del contenuto e con esso il punto, poniamo

c′=40.c'=40.

La vecchia firma resta (3,2)(3,2), ma

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

Possiamo cancellare una recensione. Modificarla senza che si noti, no.

Nota di trasparenza sull'esempio

In due dimensioni un aggressore può semplicemente provare soluzioni corte per tentativi — per c′=40c'=40 per esempio (6,1)(6,1). L'esempio non è sicuro; mostra soltanto il meccanismo. In FALCON-1024 il vettore ha 2048 coefficienti, e lì procedere per tentativi non porta da nessuna parte.

12. Perché non si arrotonda e basta?

Il procedimento del passo 3 si chiama arrotondamento di Babai. Per un esempio didattico basta — per un vero procedimento di firma no.

Il motivo: le firme arrotondate non si distribuiscono in modo uniforme. La loro forma dipende dalla geometria della base segreta. Da un numero sufficiente di firme si potrebbe ricostruire questa geometria — e con essa la chiave privata. È esattamente su questo che sono naufragati precedenti procedimenti di firma basati su reticoli.

FALCON estrae perciò i vettori corti da una distribuzione gaussiana discreta sul reticolo:

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

I valori vicini al punto obiettivo sono più probabili, ma quale venga scelto esattamente è casuale. Il risultato è una distribuzione che non rivela nulla sulla base utilizzata — matematicamente: non è distinguibile da una distribuzione che dipende solo dal reticolo stesso.

Questo sampler è la parte più impegnativa di FALCON. Gira ricorsivamente su una struttura ad albero e lavora con numeri in virgola mobile — il che rende l'implementazione delicata ed è la ragione principale per cui FALCON è più difficile da realizzare correttamente rispetto a ML-DSA.

13. Che cosa viene effettivamente trasmesso

La firma è composta da

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

Solo s2s_2 — non la coppia. s1s_1 se lo calcola il verificatore:

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

Poiché i coefficienti di s2s_2 sono piccoli e si distribuiscono attorno allo zero, si lasciano comprimere fortemente. È questo il motivo delle firme notevolmente compatte di FALCON:

chiave pubblicafirma
FALCON-512897 B~666 B
FALCON-10241.793 B~1.280 B

Per confronto: ML-DSA-87 richiede 4.627 byte. In McGesund, però, nessuna di queste firme sta nel QR code stesso — l'adesivo porta solo l'envelope Ed25519; i timbri PQ si trovano presso il record e vengono caricati al momento della verifica. Qui la dimensione non decide quindi della stampabilità, bensì di memoria e trasmissione: un timbro FALCON è grande poco più di un quarto di un timbro ML-DSA.

14. Perché FALCON verifica in fretta

La moltiplicazione di polinomi in modo ingenuo costa

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

Con la trasformata veloce di Fourier ciò scende a circa

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

Con n=1024n=1024 è la differenza tra un milione e circa diecimila operazioni. Per questo la verifica nel browser di un visitatore gira in millisecondi — ed è per questo che nel nome c'è la F:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Il procedimento in figura

SERVIZIO DI FIRMA (MCGESUND)BROWSER DEL VISITATOREchiave privata (f, g, F, G — base corta)payload m = {azienda, recensione, h, rh, iat}salt r + HashToPoint(r ‖ m) = ccampionamento gaussiano: vettore corto (s₁, s₂)firma σ = (r, s₂) + kidrecensione + σ + chiave pubblica hricalcolare c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?validanon valida
Dal payload al segno di spunta nel browser. Tutto ciò che sta sopra la linea di separazione avviene una sola volta, all'invio; tutto ciò che sta sotto, di nuovo per ogni visitatore — sul suo dispositivo, con la chiave pubblica.

16. Perché un aggressore fallisce

Conosce hh e con esso l'intero reticolo. Conosce anche il punto obiettivo cc, non appena la recensione è pubblica. Ciò che gli manca è la base corta.

Per falsificare una recensione dovrebbe trovare, per un cc scelto da sé, un vettore corto — a partire dalla sola descrizione pubblica. È il compito che il passo 4 dell'esempio ha illustrato: senza i vettori buoni lo stesso calcolo approda a una soluzione troppo lunga.

In dimensione 1024 i migliori procedimenti noti — sia classici sia quantistici — ne sono ben lontani.

Firmare: veloceVerificare: veloceFalsificare: difficile\boxed{\text{Firmare: veloce}\quad \text{Verificare: veloce}\quad \text{Falsificare: difficile}}

17. Che cosa ne fa concretamente McGesund

L'envelope. Ogni recensione firmata porta una firma Ed25519. È la variante obbligatoria — classica, molto piccola, verificabile nativamente in ogni browser.

I timbri post-quantistici. Accanto si trovano una o due firme resistenti ai quanti. Quali, dipende dal piano tariffario:

Pianolivelli di firma disponibili
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, entrambe in parallelo

La variante parallela è ridondante di proposito. FALCON poggia su reticoli NTRU, ML-DSA su reticoli modulari. Se una delle due famiglie dovesse essere più debole di quanto oggi si assuma, l'altra regge.

L'ancoraggio temporale. L'impronta digitale della chiave di firma viene ancorata tramite OpenTimestamps in un blocco Bitcoin. Così è dimostrato non solo che la firma è autentica, ma anche che essa esisteva già in un determinato momento — senza che qualcuno debba credere alla nostra marca temporale.

Tutto questo viene calcolato nel browser del lettore, tramite un modulo WASM. Noi forniamo i dati; la verifica gira sul dispositivo del visitatore. Se domani andassimo offline, una recensione una volta caricata resterebbe verificabile.

Per inquadrare i nomi: FALCON viene attualmente standardizzato come FN-DSA; la bozza è prevista come FIPS 206, ma non è ancora conclusa. Perciò nel codice di McGesund i livelli si chiamano FN-DSA-512 e FN-DSA-1024, anche se nell'uso corrente si continua a parlare di FALCON.

18. L'intuizione più importante

La chiave pubblica è la descrizione completa di un labirinto. Chiunque può guardarla.

La firma è la prova: «Per esattamente questa recensione ho trovato un percorso molto corto».

La chiave privata è la conoscenza delle scorciatoie.

Il lettore non deve conoscere le scorciatoie. Verifica soltanto se il percorso presentato è effettivamente corto e se appartiene effettivamente a questa recensione. Entrambe le cose può farle senza di noi.

FALCON trasforma una recensione in un punto di un reticoloe la firma in un breve percorso fino a esso.\boxed{ \begin{array}{c} \text{FALCON trasforma una recensione in un punto di un reticolo}\\ \text{e la firma in un breve percorso fino a esso.} \end{array}}

Chi modifica il testo sposta il punto — e il vecchio percorso non porta più a nulla.