Handtekeningmethode

FALCON wiskundig uitgelegd

Hoe een McGesund-beoordeling met FN-DSA (FALCON) wordt ondertekend — en waarom één gewijzigd teken de handtekening breekt.

Stand: 2026-09-07

1. Waar het hier over gaat

Een beoordeling bij McGesund is geen tekstveld in een database dat u maar moet geloven. Zij wordt bij het verzenden digitaal ondertekend, en elke bezoeker kan die handtekening later in de eigen browser narekenen.

Voor een deel van deze handtekeningen gebruiken wij FALCON — preciezer FN-DSA-512 en FN-DSA-1024. Deze bijdrage legt uit wat daarbij wiskundig gebeurt.

Vooraf van belang:

FALCON is geen versleuteling. De beoordelingstekst is immers bedoeld om gelezen te worden. FALCON bewijst geen geheimhouding, maar herkomst en integriteit.

2. Wat er precies wordt ondertekend

Ondertekend wordt niet de lopende tekst, maar een compact gegevensobject dat de tekst eenduidig vastlegt:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<bedrijfs-ID>",
  "c":   "<beoordelings-ID>",
  "h":   "<SHA-256 van de beoordelingstekst>",
  "rh":  "<SHA-256 van het volledige ingediende record>",
  "rv":  1,
  "qh":  "<SHA-256 van de QR-envelop, alleen bij QR-beoordelingen>",
  "iat": 1757203200
}

Dat is ons bericht mm. Het bindt samen:

  1. bij welke onderneming de beoordeling hoort (f),
  2. om welke beoordeling het gaat (c),
  3. welke tekst erachter stond — als hashwaarde (h),
  4. welk record in totaal is ingediend (rh): tekst, hartjes, geostatus en gegevens over de aanleiding, canoniek geserialiseerd en gehasht, in schemaversie rv,
  5. uit welke QR-code de beoordeling afkomstig is (qh) — bij een beoordeling zonder QR vervalt het veld,
  6. wanneer er is ondertekend (iat).

Eén gewijzigd teken in de beoordelingstekst breekt deze keten. Precies dat is het doel — en sinds rh geldt hetzelfde voor een achteraf verschoven hartje of een gewijzigde geostatus.

3. Het grondprobleem

Een lezer die op een ondernemingsprofiel terechtkomt, staat voor twee vragen:

  1. Komt deze beoordeling werkelijk uit het McGesund-systeem?
  2. Is zij achteraf gewijzigd?

Daarvoor bestaat een sleutelpaar:

  • een private sleutel — blijft in de ondertekeningsdienst
  • een openbare sleutel — mag iedereen hebben

Ondertekend wordt met de private, gecontroleerd met de openbare sleutel. En wel op het apparaat van de lezer, niet op onze server.

4. Waarom FALCON?

Veel van de huidige handtekeningmethoden berusten op problemen die voor klassieke computers moeilijk zijn, maar voor voldoende grote quantumcomputers duidelijk eenvoudiger zouden kunnen worden.

Bij een beoordeling is dat relevanter dan bij een vluchtig bericht: een beoordeling moet over vijf of tien jaar nog controleerbaar zijn. Wie vandaag ondertekent, ondertekent voor de volledige levensduur van de vermelding.

FALCON berust daarom op roostercryptografie:

Men bouwt een wiskundig eenvoudig te beschrijven rooster waarin een bepaalde zoekopgave extreem moeilijk is.

5. Wat is een wiskundig rooster?

Twee vectoren:

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

Alle geheeltallige combinaties

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

vormen een rooster van punten. Bijvoorbeeld:

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
Twee vectoren spannen een rooster op. Elk punt is een geheeltallige combinatie van de twee — het gemarkeerde ontstaat uit tweemaal v₁ en driemaal v₂.

Doorslaggevend is:

Het rooster zelf is eenvoudig te beschrijven. Bepaalde eigenschappen daarin vinden is zeer moeilijk.

6. Het geheim zijn korte vectoren

De klassieke moeilijke opgave luidt:

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

Dat is het Shortest Vector Problem. In twee dimensies kunt u het uitproberen. FALCON werkt in dimensie 512 of 1024 — daar is het kansloos.

lange basisbijna evenwijdigkortste vector
Hetzelfde rooster, twee beschrijvingen. De grijze vectoren brengen het eveneens voort, maar zijn lang en bijna evenwijdig — een slechte basis. De korte vector is wat moeilijk te vinden is.

FALCON heeft echter niet de kortste vector als zodanig nodig, maar iets verwants: bij een gegeven doelpunt een nabijgelegen roosterpunt vinden. Ook dat is zonder de juiste extra informatie moeilijk.

doelpunt uit de beoordelingnabijgelegen roosterpuntver verwijderd
Het doelpunt uit de beoordeling (open cirkel) ligt niet in het rooster. Gezocht wordt een roosterpunt er vlak naast — de gestippelde weg naar een ver verwijderd punt is eveneens een oplossing van de eerste voorwaarde, maar juist geen korte.

7. Polynomen in plaats van getallen

FALCON gebruikt een NTRU-rooster en rekent met polynomen. Dus niet met losse getallen, maar met coëfficiëntenlijsten:

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.

Er wordt gerekend in de ring

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

Dat betekent:

  • Zq\mathbb{Z}_q: rekenen modulo qq. Bij q=7q=7 bijvoorbeeld 10≡310\equiv3, want 10−7=310-7=3.
  • xn=−1x^n=-1: houdt de polynomen op vaste lengte.

FALCON gebruikt concreet:

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

8. De centrale truc

De private sleutel bestaat uit vier kleine polynomen

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

met de NTRU-vergelijking

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

Deze vier vormen samen een geheime, gunstige roosterbasis — een beschrijving van het rooster uit korte vectoren.

De openbare sleutel is in wezen één enkel polynoom:

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

Uit hh volgt hetzelfde rooster, maar in een onhandige basis van lange vectoren:

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

Dat is de hele kern van FALCON. Beide bases beschrijven hetzelfde rooster. Alleen is de ene bruikbaar om mee te rekenen en de andere niet.

U kunt zich dat voorstellen als een stadsplattegrond: openbaar is de volledige kaart. Geheim is de kennis van de sluiproutes.

9. De beoordeling wordt een punt

Voordat er wordt ondertekend, gaat het payload-object door een hashfunctie. FALCON gebruikt daarvoor hash-to-point: uit het bericht ontstaat geen getalswaarde, maar rechtstreeks een punt in de ring.

Daarnaast trekt de ondertekeningsdienst een willekeurig salt rr (320 bit) en hasht dat mee:

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

Het salt is geen bijzaak. Zonder salt zou dezelfde beoordeling altijd dezelfde handtekening opleveren, en uit veel handtekeningen zou de geheime basis te reconstrueren zijn. Het gaat daarom mee in de handtekening.

10. Wat een geldige handtekening is

Gezocht wordt een paar

(s1,s2)(s_1,s_2)

met twee eigenschappen:

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

Aan de eerste voorwaarde alleen is triviaal te voldoen — u neemt s2=0s_2=0 en s1=cs_1=c. De tweede voorwaarde maakt de opgave moeilijk.

De kortheid is de handtekening.\boxed{\text{De kortheid is de handtekening.}}

11. Een volledig doorgerekend minivoorbeeld

Wij krimpen alles tot speelgoedformaat: polynomen met slechts één coëfficiënt, dus gewone getallen, en

q=97.q=97.

De geheime sleutel. Twee kleine getallen:

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

De openbare sleutel. Er geldt 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, want 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Dus:

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

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

De openbare basis volgt rechtstreeks uit hh:

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

Beide liggen in LL — en beide zijn lang.

De geheime basis kent alleen de ondertekeningsdienst:

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

want −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 en −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. De determinant is

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

de NTRU-vergelijking klopt dus. Beide vectoren zijn kort.

Stap 1: De beoordeling hashen

Laten wij aannemen dat het payload-object van de beoordeling oplevert

c=71.c=71.

Stap 2: Een eerste, slechte oplossing

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

voldoet aan 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Maar de lengte is 7171 — veel te lang.

Stap 3: Met de geheime basis inkorten

De ondertekeningsdienst drukt het doelpunt uit in zijn korte basis:

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

Dat leidt tot a≈−10,25a\approx-10{,}25 en b≈−2,20b\approx-2{,}20. Afgerond op a=−10a=-10, b=−2b=-2 ontstaat het roosterpunt

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

Controle: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, dus inderdaad in LL. Aftrekken:

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

Lengte:

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

Dat is de handtekening.

Stap 4: Dezelfde methode met de openbare basis

Wie alleen h=34h=34 kent, heeft de basis {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Dezelfde afrondingsberekening levert daar het roosterpunt (97,0)(97,0) op en daarmee

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

Eveneens een geldige oplossing van de vergelijking — maar zevenmaal langer. Wordt de acceptatiegrens onder 26 gelegd, dan is zij waardeloos.

Zelfde algoritme, zelfde rooster, zelfde doelpunt.Alleen de basis verschilt — en daarmee het resultaat.\boxed{ \begin{array}{c} \text{Zelfde algoritme, zelfde rooster, zelfde doelpunt.}\\ \text{Alleen de basis verschilt — en daarmee het resultaat.} \end{array}}

Dat is het valluik van FALCON in één regel.

Stap 5: De browser controleert

De browser krijgt de beoordeling, het salt en s2=2s_2=2. Hij berekent de hash opnieuw, verkrijgt c=71c=71, reconstrueert

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

en controleert de lengte:

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

Stap 6: Iemand wijzigt de beoordelingstekst

Wordt de tekst achteraf gewijzigd, dan verandert de content-hash en daarmee het punt, zeg

c′=40.c'=40.

De oude handtekening blijft (3,2)(3,2), maar

3+34⋅2=71≠40⟹Handtekening ongeldig3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Handtekening ongeldig}}

Wij kunnen een beoordeling verwijderen. Veranderen kunnen wij haar niet zonder dat het opvalt.

Eerlijkheidshalve over dit voorbeeld

In twee dimensies kan een aanvaller korte oplossingen eenvoudig uitproberen — voor c′=40c'=40 bijvoorbeeld (6,1)(6,1). Het voorbeeld is niet veilig; het toont alleen het mechanisme. Bij FALCON-1024 heeft de vector 2048 coëfficiënten, en daar leidt uitproberen nergens toe.

12. Waarom wordt er niet gewoon afgerond?

De methode uit stap 3 heet Babai-afronding. Voor een leerboekvoorbeeld volstaat zij — voor een echte handtekeningmethode niet.

De reden: de afgeronde handtekeningen liggen niet gelijkmatig verdeeld. Hun vorm hangt af van de meetkunde van de geheime basis. Uit voldoende veel handtekeningen zou die meetkunde te reconstrueren zijn — en daarmee de private sleutel. Precies daarop zijn eerdere roostergebaseerde handtekeningmethoden gestrand.

FALCON trekt de korte vectoren daarom uit een discrete gaussverdeling over het rooster:

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

Waarden dicht bij het doelpunt zijn waarschijnlijker, maar welke precies wordt gekozen, is willekeurig. Het resultaat is een verdeling die niets over de gebruikte basis verraadt — wiskundig: zij is niet te onderscheiden van een verdeling die alleen van het rooster zelf afhangt.

Deze sampler is het veeleisendste onderdeel van FALCON. Hij loopt recursief over een boomstructuur en werkt met drijvendekommagetallen — wat de implementatie hachelijk maakt en de belangrijkste reden is dat FALCON moeilijker correct te realiseren is dan ML-DSA.

13. Wat er daadwerkelijk wordt overgedragen

De handtekening bestaat uit

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

Alleen s2s_2 — niet het paar. s1s_1 rekent de controleur zelf uit:

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

Doordat de coëfficiënten van s2s_2 klein zijn en rond nul spreiden, laten zij zich sterk comprimeren. Dat is de reden voor FALCONs opvallend compacte handtekeningen:

openbare sleutelhandtekening
FALCON-512897 B~666 B
FALCON-10241.793 B~1.280 B

Ter vergelijking: ML-DSA-87 heeft 4.627 byte nodig. Bij McGesund zit overigens geen van deze handtekeningen in de QR-code zelf — de sticker draagt alleen de Ed25519-envelop; de PQ-stempels liggen bij het record en worden bij het controleren nageladen. De omvang beslist hier dus niet over de afdrukbaarheid, maar over opslag en overdracht: een FALCON-stempel is ruim een kwart zo groot als een ML-DSA-stempel.

14. Waarom FALCON snel controleert

Naïeve polynoomvermenigvuldiging kost

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

Met de snelle fouriertransformatie daalt dat tot ongeveer

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

Bij n=1024n=1024 is dat het verschil tussen een miljoen en ongeveer tienduizend bewerkingen. Daarom loopt de controle in de browser van een bezoeker in milliseconden — en daarom zit de F in de naam:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Het verloop in beeld

ONDERTEKENINGSDIENST (MCGESUND)BROWSER VAN DE BEZOEKERprivate sleutel (f, g, F, G — korte basis)payload m = {bedrijf, beoordeling, h, rh, iat}salt r + HashToPoint(r ‖ m) = cgauss-sampling: korte vector (s₁, s₂)handtekening σ = (r, s₂) + kidbeoordeling + σ + openbare sleutel hc opnieuw berekenen, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?geldigongeldig
Van payload tot het vinkje in de browser. Alles boven de scheidingslijn gebeurt eenmalig bij het verzenden, alles daaronder bij elke bezoeker opnieuw — op zijn apparaat, met de openbare sleutel.

16. Waarom een aanvaller strandt

Hij kent hh en daarmee het volledige rooster. Hij kent ook het doelpunt cc, zodra de beoordeling openbaar is. Wat hem ontbreekt, is de korte basis.

Om een beoordeling te vervalsen zou hij bij een zelfgekozen cc een korte vector moeten vinden — alleen uit de openbare beschrijving. Dat is de opgave die stap 4 van het voorbeeld heeft geïllustreerd: zonder de goede vectoren belandt dezelfde berekening bij een veel te lange oplossing.

In dimensie 1024 zijn de beste bekende methoden — zowel klassiek als quantumgebaseerd — daar ver van verwijderd.

Ondertekenen: snelControleren: snelVervalsen: moeilijk\boxed{\text{Ondertekenen: snel}\quad \text{Controleren: snel}\quad \text{Vervalsen: moeilijk}}

17. Wat McGesund er concreet mee doet

De envelop. Elke ondertekende beoordeling draagt een Ed25519-handtekening. Dat is de verplichte variant — klassiek, zeer klein, in elke browser natief controleerbaar.

De post-quantumstempels. Daarnaast liggen een of twee quantumresistente handtekeningen. Welke, hangt af van het tarief:

Tariefbeschikbare handtekeningniveaus
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, beide parallel

De parallelle variant is bewust redundant. FALCON staat op NTRU-roosters, ML-DSA op module-roosters. Mocht een van beide families zwakker zijn dan vandaag wordt aangenomen, dan draagt de andere verder.

Het tijdanker. De vingerafdruk van de ondertekeningssleutel wordt via OpenTimestamps in een Bitcoin-blok verankerd. Daarmee is niet alleen aangetoond dat de handtekening echt is, maar ook dat zij op een bepaald tijdstip al bestond — zonder dat iemand ons tijdstempel hoeft te geloven.

Dat alles wordt berekend in de browser van de lezer, via een WASM-module. Wij leveren de gegevens; de controle loopt op het apparaat van de bezoeker. Zouden wij morgen offline gaan, dan bleef een eenmaal geladen beoordeling controleerbaar.

Ter duiding van de namen: FALCON wordt momenteel als FN-DSA gestandaardiseerd; het ontwerp is als FIPS 206 voorzien, maar nog niet afgerond. Daarom heten de niveaus in de McGesund-code FN-DSA-512 en FN-DSA-1024, ook al wordt er in het spraakgebruik nog steeds over FALCON gesproken.

18. De belangrijkste intuïtie

De openbare sleutel is de volledige beschrijving van een doolhof. Iedereen mag haar bekijken.

De handtekening is het bewijs: „Ik heb voor precies deze beoordeling een zeer korte weg gevonden."

De private sleutel is de kennis van de sluiproutes.

De lezer hoeft de sluiproutes niet te kennen. Hij meet alleen na of de voorgelegde weg werkelijk kort is en werkelijk bij deze beoordeling hoort. Beide kan hij zonder ons.

FALCON maakt van een beoordeling een punt in een roosteren van de handtekening een korte weg daarheen.\boxed{ \begin{array}{c} \text{FALCON maakt van een beoordeling een punt in een rooster}\\ \text{en van de handtekening een korte weg daarheen.} \end{array}}

Wie de tekst wijzigt, verschuift het punt — en de oude weg loopt dood.