Procedeu de semnătură

FALCON explicat matematic

Cum este semnată o recenzie McGesund cu FN-DSA (FALCON) — și de ce un singur caracter modificat rupe semnătura.

Actualizat: 2026-09-07

1. Despre ce este vorba aici

O recenzie de pe McGesund nu este un câmp de text dintr-o bază de date pe care trebuie să îl crezi pe cuvânt. Ea este semnată digital în momentul trimiterii, iar orice vizitator poate recalcula ulterior această semnătură în propriul browser.

Pentru o parte dintre aceste semnături folosim FALCON — mai exact FN-DSA-512 și FN-DSA-1024. Acest articol explică ce se întâmplă matematic în acest proces.

Un lucru important de la bun început:

FALCON nu este o criptare. Textul recenziei trebuie doar să poată fi citit. FALCON nu dovedește confidențialitatea, ci originea și integritatea.

2. Ce anume se semnează

Nu se semnează textul propriu-zis, ci un obiect de date compact, care fixează fără echivoc textul:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID companie>",
  "c":   "<ID recenzie>",
  "h":   "<SHA-256 al textului recenziei>",
  "rh":  "<SHA-256 al întregului set de date trimis>",
  "rv":  1,
  "qh":  "<SHA-256 al envelope-ului QR, doar la recenziile prin QR>",
  "iat": 1757203200
}

Acesta este mesajul nostru mm. El leagă între ele:

  1. cărei companii îi aparține recenzia (f),
  2. despre ce recenzie este vorba (c),
  3. ce text stătea în spatele ei — ca valoare hash (h),
  4. ce set de date a fost trimis în ansamblu (rh): text, inimi, statusul geo și datele privind ocazia, serializate canonic și trecute prin hash, în versiunea de schemă rv,
  5. din ce cod QR provine recenzia (qh) — la o recenzie fără QR, câmpul lipsește,
  6. când s-a semnat (iat).

Un singur caracter modificat în textul recenziei rupe acest lanț. Exact acesta este scopul — iar de la introducerea lui rh, același lucru este valabil și pentru o inimă mutată ulterior sau pentru un status geo modificat.

3. Problema de bază

Un cititor care ajunge pe profilul unei companii are două întrebări:

  1. Provine această recenzie cu adevărat din sistemul McGesund?
  2. A fost ea modificată ulterior?

Pentru asta există o pereche de chei:

  • o cheie privată — rămâne în serviciul de semnare
  • o cheie publică — o poate avea oricine

Semnarea se face cu cheia privată, verificarea cu cea publică. Și anume pe dispozitivul cititorului, nu pe serverul nostru.

4. De ce FALCON?

Multe dintre procedeele de semnătură actuale se bazează pe probleme dificile pentru calculatoarele clasice, dar care ar putea deveni considerabil mai ușoare pentru calculatoare cuantice suficient de mari.

La o recenzie, acest lucru este mai relevant decât la un mesaj efemer: o recenzie trebuie să fie verificabilă și peste cinci sau zece ani. Cine semnează astăzi semnează pentru întreaga durată de viață a înregistrării.

De aceea, FALCON se bazează pe criptografia pe rețele:

Se construiește o rețea ușor de descris matematic, în care o anumită problemă de căutare este extrem de dificilă.

5. Ce este o rețea matematică?

Doi vectori:

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

Toate combinațiile cu numere întregi

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

formează o rețea de puncte. De exemplu:

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
Doi vectori generează o rețea. Fiecare punct este o combinație cu numere întregi a celor doi — cel marcat rezultă din de două ori v₁ și de trei ori v₂.

Esențial este:

Rețeaua în sine este ușor de descris. Găsirea anumitor proprietăți în interiorul ei este foarte dificilă.

6. Secretul sunt vectorii scurți

Problema dificilă clasică sună astfel:

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

Acesta este Shortest Vector Problem. În două dimensiuni se poate rezolva prin încercări. FALCON lucrează în dimensiunea 512 sau 1024 — acolo este fără speranță.

bază lungăaproape paralelicel mai scurt vector
Aceeași rețea, două descrieri. Vectorii gri o generează la rândul lor, dar sunt lungi și aproape paraleli — o bază proastă. Vectorul scurt este cel greu de găsit.

FALCON nu are însă nevoie de cel mai scurt vector în sine, ci de ceva înrudit: să găsească, pentru un punct țintă dat, un punct apropiat al rețelei. Și asta este dificil fără informația suplimentară potrivită.

punct țintă din recenziepunct apropiat al rețeleiîndepărtat
Punctul țintă provenit din recenzie (cercul gol) nu se află în rețea. Se caută un punct al rețelei aflat imediat lângă el — drumul punctat către un punct îndepărtat este de asemenea o soluție a primei condiții, dar nu una scurtă.

7. Polinoame în loc de numere

FALCON folosește o rețea NTRU și calculează cu polinoame. Așadar, în loc de numere individuale, cu liste de coeficienți:

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.

Calculele se fac în inelul

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

Asta înseamnă:

  • Zq\mathbb{Z}_q: calcul modulo qq. La q=7q=7, de exemplu, 10≡310\equiv3, deoarece 10−7=310-7=3.
  • xn=−1x^n=-1: menține polinoamele la o lungime fixă.

Concret, FALCON folosește:

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

8. Trucul central

Cheia privată constă din patru polinoame mici

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

care satisfac ecuația NTRU

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

Aceste patru formează împreună o bază secretă și binevoitoare a rețelei — o descriere a rețelei prin vectori scurți.

Cheia publică este, în esență, un singur polinom:

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

Din hh rezultă aceeași rețea, dar într-o bază greu de folosit, formată din vectori lungi:

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

Acesta este întreg miezul lui FALCON. Ambele baze descriu aceeași rețea. Doar că una este utilizabilă pentru calcul, iar cealaltă nu.

Ne putem imagina asta ca pe o hartă a orașului: publică este harta completă. Secretă este cunoașterea scurtăturilor.

9. Recenzia devine un punct

Înainte de semnare, obiectul payload trece printr-o funcție hash. FALCON folosește pentru asta Hash-to-Point: din mesaj nu rezultă o valoare numerică, ci direct un punct în inel.

În plus, serviciul de semnare extrage un salt aleatoriu rr (320 de biți) și îl include în hash:

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

Salt-ul nu este un accesoriu. Fără el, aceeași recenzie ar produce mereu aceeași semnătură, iar din multe semnături s-ar putea reconstrui baza secretă. De aceea el călătorește împreună cu semnătura.

10. Ce înseamnă o semnătură validă

Se caută o pereche

(s1,s2)(s_1,s_2)

cu două proprietăți:

s1+s2 h≡c(modq)și∥(s1,s2)∥  mica˘.s_1+s_2\,h\equiv c \pmod q \qquad\text{și}\qquad \|(s_1,s_2)\|\;\text{mică}.

Prima condiție singură este banal de îndeplinit — se ia s2=0s_2=0 și s1=cs_1=c. A doua condiție face problema dificilă.

Scurtimea este semna˘tura.\boxed{\text{Scurtimea este semnătura.}}

11. Un mini-exemplu calculat integral

Reducem totul la dimensiuni de jucărie: polinoame cu un singur coeficient, deci numere obișnuite, și

q=97.q=97.

Cheia secretă. Două numere mici:

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

Cheia publică. Avem 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, deoarece 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Așadar:

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

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

Baza publică rezultă direct din hh:

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

Ambii se află în LL — și ambii sunt lungi.

Baza secretă o cunoaște doar serviciul de semnare:

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

deoarece −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 și −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Determinantul este

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

deci ecuația NTRU se verifică. Ambii vectori sunt scurți.

Pasul 1: Hash-ul recenziei

Să presupunem că obiectul payload al recenziei dă

c=71.c=71.

Pasul 2: O primă soluție, proastă

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

satisface 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Dar lungimea este 7171 — mult prea mare.

Pasul 3: Scurtarea cu baza secretă

Serviciul de semnare exprimă punctul țintă în baza sa scurtă:

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

Asta duce la a≈−10,25a\approx-10{,}25 și b≈−2,20b\approx-2{,}20. Rotunjind la a=−10a=-10, b=−2b=-2, rezultă punctul de rețea

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

Control: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, deci se află într-adevăr în LL. Scădem:

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

Lungimea:

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

Aceasta este semnătura.

Pasul 4: Același procedeu cu baza publică

Cine cunoaște doar h=34h=34 are baza {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Același calcul de rotunjire dă acolo punctul de rețea (97,0)(97,0) și, prin urmare,

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

Tot o soluție validă a ecuației — dar de șapte ori mai lungă. Dacă pragul de acceptare este fixat sub 26, ea este lipsită de valoare.

Același algoritm, aceeași rețea, același punct ținta˘.Difera˘ doar baza — și, odata˘ cu ea, rezultatul.\boxed{ \begin{array}{c} \text{Același algoritm, aceeași rețea, același punct țintă.}\\ \text{Diferă doar baza — și, odată cu ea, rezultatul.} \end{array}}

Aceasta este trapa lui FALCON, într-un singur rând.

Pasul 5: Browserul verifică

Browserul primește recenzia, salt-ul și s2=2s_2=2. El recalculează hash-ul, obține c=71c=71, reconstruiește

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

și verifică lungimea:

∥(3,2)∥=13  ≤  β⟹Semna˘tura˘ valida˘\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Semnătură validă}}

Pasul 6: Cineva modifică textul recenziei

Dacă textul este modificat ulterior, se schimbă hash-ul de conținut și, odată cu el, punctul — să zicem

c′=40.c'=40.

Semnătura veche rămâne (3,2)(3,2), dar

3+34⋅2=71≠40⟹Semna˘tura˘ invalida˘3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Semnătură invalidă}}

Putem șterge o recenzie. Nu o putem modifica fără ca acest lucru să iasă la iveală.

Notă de onestitate privind exemplul

În două dimensiuni, un atacator poate găsi soluții scurte prin simplă încercare — pentru c′=40c'=40, de exemplu, (6,1)(6,1). Exemplul nu este sigur; el arată doar mecanismul. La FALCON-1024, vectorul are 2048 de coeficienți, iar acolo încercările nu duc nicăieri.

12. De ce nu se rotunjește pur și simplu?

Procedeul din pasul 3 se numește rotunjire Babai. Pentru un exemplu didactic este suficient — pentru un procedeu de semnătură real, nu.

Motivul: semnăturile rotunjite nu sunt distribuite uniform. Forma lor depinde de geometria bazei secrete. Din suficient de multe semnături, această geometrie s-ar putea reconstrui — și, odată cu ea, cheia privată. Exact de asta au eșuat procedee de semnătură pe rețele mai vechi.

De aceea, FALCON extrage vectorii scurți dintr-o distribuție gaussiană discretă peste rețea:

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

Valorile apropiate de punctul țintă sunt mai probabile, dar care anume este aleasă rămâne aleatoriu. Rezultatul este o distribuție care nu dezvăluie nimic despre baza folosită — matematic: ea nu se poate distinge de o distribuție care depinde doar de rețeaua însăși.

Acest sampler este partea cea mai pretențioasă din FALCON. El rulează recursiv pe o structură arborescentă și lucrează cu numere în virgulă mobilă — ceea ce face implementarea delicată și este motivul principal pentru care FALCON este mai greu de realizat corect decât ML-DSA.

13. Ce se transmite efectiv

Semnătura constă din

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

Doar s2s_2 — nu perechea. Pe s1s_1 îl calculează verificatorul singur:

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

Deoarece coeficienții lui s2s_2 sunt mici și se împrăștie în jurul lui zero, ei pot fi comprimați puternic. Acesta este motivul semnăturilor remarcabil de compacte ale lui FALCON:

cheie publicăsemnătură
FALCON-512897 B~666 B
FALCON-10241.793 B~1.280 B

Pentru comparație: ML-DSA-87 are nevoie de 4.627 de octeți. La McGesund însă, niciuna dintre aceste semnături nu se află în codul QR propriu-zis — autocolantul poartă doar envelope-ul Ed25519; ștampilele post-cuantice se află lângă setul de date și sunt încărcate suplimentar la verificare. Așadar, dimensiunea nu decide aici asupra tipăribilității, ci asupra stocării și transmiterii: o ștampilă FALCON este de aproximativ patru ori mai mică decât una ML-DSA.

14. De ce verifică FALCON repede

Înmulțirea naivă a polinoamelor costă

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

Cu transformata Fourier rapidă, asta scade la aproximativ

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

La n=1024n=1024, aceasta este diferența dintre un milion și circa zece mii de operații. De aceea verificarea rulează în milisecunde în browserul unui vizitator — și de aceea F-ul se află în nume:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Fluxul în imagine

SERVICIUL DE SEMNARE (MCGESUND)BROWSERUL VIZITATORULUIcheia privată (f, g, F, G — bază scurtă)Payload m = {companie, recenzie, h, rh, iat}Salt r + HashToPoint(r ‖ m) = ceșantionare gaussiană: vector scurt (s₁, s₂)Semnătura σ = (r, s₂) + kidRecenzie + σ + cheia publică hrecalcularea lui c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?validăinvalidă
De la payload până la bifa din browser. Tot ce se află deasupra liniei de separare se întâmplă o singură dată, la trimitere; tot ce se află dedesubt, din nou la fiecare vizitator — pe dispozitivul său, cu cheia publică.

16. De ce eșuează un atacator

El cunoaște hh și, odată cu el, întreaga rețea. Cunoaște și punctul țintă cc, de îndată ce recenzia este publică. Ceea ce îi lipsește este baza scurtă.

Pentru a falsifica o recenzie, ar trebui să găsească, pentru un cc ales de el, un vector scurt — numai pe baza descrierii publice. Aceasta este sarcina pe care a ilustrat-o pasul 4 al exemplului: fără vectorii buni, același calcul ajunge la o soluție mult prea lungă.

În dimensiunea 1024, cele mai bune procedee cunoscute — atât clasice, cât și cuantice — sunt departe de asta.

Semnare: rapida˘Verificare: rapida˘Falsificare: dificila˘\boxed{\text{Semnare: rapidă}\quad \text{Verificare: rapidă}\quad \text{Falsificare: dificilă}}

17. Ce face McGesund concret cu asta

Envelope-ul. Fiecare recenzie semnată poartă o semnătură Ed25519. Aceasta este varianta obligatorie — clasică, foarte mică, verificabilă nativ în orice browser.

Ștampilele post-cuantice. Alături se află una sau două semnături rezistente la calculul cuantic. Care anume depinde de tarif:

Tarifniveluri de semnătură disponibile
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, ambele în paralel

Varianta paralelă este redundantă în mod deliberat. FALCON se sprijină pe rețele NTRU, ML-DSA pe rețele modulare. Dacă una dintre cele două familii s-ar dovedi mai slabă decât se presupune astăzi, cealaltă continuă să susțină.

Ancora temporală. Amprenta cheii de semnare este ancorată printr-un bloc Bitcoin, prin OpenTimestamps. Astfel este dovedit nu doar că semnătura este autentică, ci și că ea exista deja la un anumit moment — fără ca cineva să fie nevoit să creadă marcajul nostru de timp.

Toate acestea sunt calculate în browserul cititorului, printr-un modul WASM. Noi livrăm datele; verificarea rulează pe dispozitivul vizitatorului. Dacă mâine am dispărea de pe internet, o recenzie odată încărcată ar rămâne verificabilă.

Despre încadrarea denumirilor: FALCON este standardizat în prezent sub numele FN-DSA; proiectul este prevăzut ca FIPS 206, dar nu este încă finalizat. De aceea, în codul McGesund nivelurile se numesc FN-DSA-512 și FN-DSA-1024, chiar dacă în vorbirea curentă se folosește în continuare FALCON.

18. Cea mai importantă intuiție

Cheia publică este descrierea completă a unui labirint. Oricine are voie să o vadă.

Semnătura este dovada: „Am găsit, pentru exact această recenzie, un drum foarte scurt.”

Cheia privată este cunoașterea scurtăturilor.

Cititorul nu trebuie să cunoască scurtăturile. El doar măsoară dacă drumul prezentat este într-adevăr scurt și dacă aparține într-adevăr acestei recenzii. Ambele lucruri le poate face fără noi.

FALCON transforma˘ o recenzie ıˆntr-un punct dintr-o rețeași semna˘tura ıˆntr-un drum scurt paˆna˘ acolo.\boxed{ \begin{array}{c} \text{FALCON transformă o recenzie într-un punct dintr-o rețea}\\ \text{și semnătura într-un drum scurt până acolo.} \end{array}}

Cine modifică textul deplasează punctul — iar drumul vechi duce în gol.