Signaturmetoder

FALCON forklaret matematisk

Sådan bliver en McGesund-anmeldelse underskrevet med FN-DSA (FALCON) — og derfor bryder et ændret tegn underskriften.

Opdateret: 2026-09-07

1. Hvad det handler om

En anmeldelse hos McGesund er ikke et tekstfelt i en database, som man bare må tro på. Den bliver digitalt signeret, når den sendes af sted, og enhver besøgende kan senere regne signaturen efter i sin egen browser.

Til en del af disse signaturer bruger vi FALCON — nærmere bestemt FN-DSA-512 og FN-DSA-1024. Dette indlæg forklarer, hvad der matematisk sker undervejs.

Vigtigt at slå fast først:

FALCON er ikke kryptering. Anmeldelsesteksten skal jo kunne læses. FALCON beviser ikke hemmeligholdelse, men oprindelse og uforanderlighed.

2. Hvad der præcist bliver underskrevet

Det er ikke den løbende tekst, der signeres, men et kompakt dataobjekt, som utvetydigt fastnagler teksten:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<virksomheds-id>",
  "c":   "<anmeldelses-id>",
  "h":   "<SHA-256 af anmeldelsesteksten>",
  "rh":  "<SHA-256 af hele det indsendte datasæt>",
  "rv":  1,
  "qh":  "<SHA-256 af QR-konvolutten, kun ved QR-anmeldelser>",
  "iat": 1757203200
}

Det er vores besked mm. Den binder følgende sammen:

  1. hvilken virksomhed anmeldelsen hører til (f),
  2. hvilken anmeldelse det drejer sig om (c),
  3. hvilken tekst der stod bag — som hashværdi (h),
  4. hvilket datasæt der samlet blev indsendt (rh): tekst, hjerter, geostatus og anledningsoplysninger, kanonisk serialiseret og hashet, i skemaversionen rv,
  5. hvilken QR-kode anmeldelsen stammer fra (qh) — ved en anmeldelse uden QR udgår feltet,
  6. hvornår der blev signeret (iat).

Et ændret tegn i anmeldelsesteksten bryder denne kæde. Netop det er formålet — og siden rh gælder det samme for et efterfølgende flyttet hjerte eller en ændret geostatus.

3. Grundproblemet

En læser, der lander på en virksomhedsprofil, står med to spørgsmål:

  1. Stammer denne anmeldelse virkelig fra McGesund-systemet?
  2. Er den blevet ændret bagefter?

Til det findes der et nøglepar:

  • en privat nøgle — bliver i signaturtjenesten
  • en offentlig nøgle — må alle have

Der signeres med den private og verificeres med den offentlige nøgle. Og det sker på læserens eget udstyr, ikke på vores server.

4. Hvorfor FALCON?

Mange af nutidens signaturmetoder bygger på problemer, der er svære for klassiske computere, men som kunne blive betydeligt lettere for tilstrækkelig store kvantecomputere.

Ved en anmeldelse er det mere relevant end ved en flygtig besked: En anmeldelse skal stadig kunne verificeres om fem eller ti år. Den, der underskriver i dag, underskriver for hele opslagets levetid.

FALCON bygger derfor på gitterkryptografi:

Man bygger et gitter, der er matematisk enkelt at beskrive, og hvor en bestemt søgeopgave er ekstremt svær.

5. Hvad er et matematisk gitter?

To vektorer:

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

Alle heltallige kombinationer

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

giver et gitter af punkter. For eksempel:

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
To vektorer udspænder et gitter. Hvert punkt er en heltallig kombination af de to — det markerede opstår af to gange v₁ og tre gange v₂.

Det afgørende er:

Selve gitteret er let at beskrive. At finde bestemte egenskaber i det er meget svært.

6. Hemmeligheden er korte vektorer

Den klassiske svære opgave lyder:

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

Det er Shortest Vector Problem. I to dimensioner kan man prøve sig frem. FALCON arbejder i dimension 512 eller 1024 — dér er det håbløst.

lang basisnæsten parallellekorteste vektor
Samme gitter, to beskrivelser. De grå vektorer frembringer det også, men de er lange og næsten parallelle — en dårlig basis. Den korte vektor er dét, der er svært at finde.

FALCON har dog ikke brug for den korteste vektor som sådan, men for noget beslægtet: at finde et gitterpunkt tæt på et givet målpunkt. Også det er svært uden den rette ekstra viden.

målpunkt fra anmeldelsennært gitterpunktlangt væk
Målpunktet fra anmeldelsen (den åbne cirkel) ligger ikke i gitteret. Der søges et gitterpunkt tæt ved siden af — den stiplede vej til et fjernt punkt er også en løsning på den første betingelse, men netop ikke en kort en.

7. Polynomier i stedet for tal

FALCON bruger et NTRU-gitter og regner med polynomier. Altså med koefficientlister i stedet for enkelttal:

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.

Der regnes i ringen

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

Det betyder:

  • Zq\mathbb{Z}_q: regning modulo qq. Ved q=7q=7 er for eksempel 10≡310\equiv3, for 10−7=310-7=3.
  • xn=−1x^n=-1: holder polynomierne på fast længde.

FALCON bruger konkret:

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

8. Det centrale kneb

Den private nøgle består af fire små polynomier

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

med NTRU-ligningen

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

Disse fire udgør tilsammen en hemmelig, velformet gitterbasis — en beskrivelse af gitteret ud fra korte vektorer.

Den offentlige nøgle er i det væsentlige et enkelt polynomium:

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

Ud af hh fremgår det samme gitter, men i en uhåndterlig basis af lange vektorer:

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

Det er hele kernen i FALCON. Begge baser beskriver det samme gitter. Kun er den ene brugbar at regne med, og den anden ikke.

Man kan forestille sig det som et bykort: Offentligt er hele kortet. Hemmelig er kendskabet til genvejene.

9. Anmeldelsen bliver til et punkt

Før der signeres, går payload-objektet gennem en hashfunktion. FALCON bruger dertil Hash-to-Point: Ud af beskeden kommer ikke en talværdi, men direkte et punkt i ringen.

Desuden trækker signaturtjenesten et tilfældigt salt rr (320 bit) og hasher det med:

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

Saltet er ikke pynt. Uden det ville den samme anmeldelse altid give den samme signatur, og ud af mange signaturer kunne den hemmelige basis rekonstrueres. Det rejser derfor med ind i signaturen.

10. Hvad en gyldig signatur er

Der søges et par

(s1,s2)(s_1,s_2)

med to egenskaber:

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

Den første betingelse alene er triviel at opfylde — man sætter s2=0s_2=0 og s1=cs_1=c. Den anden betingelse gør opgaven svær.

Kortheden er signaturen.\boxed{\text{Kortheden er signaturen.}}

11. Et fuldt gennemregnet minieksempel

Vi skrumper alt til legetøjsstørrelse: polynomier med kun én koefficient, altså almindelige tal, og

q=97.q=97.

Den hemmelige nøgle. To små tal:

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

Den offentlige nøgle. Der gælder 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, for 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Altså:

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

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

Den offentlige basis følger direkte af hh:

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

Begge ligger i LL — og begge er lange.

Den hemmelige basis kender kun signaturtjenesten:

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

for −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 og −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Determinanten er

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

NTRU-ligningen går altså op. Begge vektorer er korte.

Trin 1: Hash anmeldelsen

Lad os antage, at anmeldelsens payload-objekt giver

c=71.c=71.

Trin 2: En første, dårlig løsning

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

opfylder 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Men længden er 7171 — alt for lang.

Trin 3: Forkort med den hemmelige basis

Signaturtjenesten udtrykker målpunktet i sin korte basis:

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

Det fører til a≈−10,25a\approx-10{,}25 og b≈−2,20b\approx-2{,}20. Afrundet til a=−10a=-10, b=−2b=-2 fås gitterpunktet

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

Kontrol: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, altså faktisk i LL. Træk fra:

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

Længde:

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

Det er signaturen.

Trin 4: Samme metode med den offentlige basis

Den, der kun kender h=34h=34, har basen {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Den samme afrundingsberegning giver dér gitterpunktet (97,0)(97,0) og dermed

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

Også en gyldig løsning på ligningen — men syv gange længere. Sættes acceptgrænsen under 26, er den værdiløs.

Samme algoritme, samme gitter, samme ma˚lpunkt.Kun basen er forskellig — og dermed resultatet.\boxed{ \begin{array}{c} \text{Samme algoritme, samme gitter, samme målpunkt.}\\ \text{Kun basen er forskellig — og dermed resultatet.} \end{array}}

Det er FALCONs faldlem på én linje.

Trin 5: Browseren verificerer

Browseren får anmeldelsen, saltet og s2=2s_2=2. Den beregner hashen på ny, får c=71c=71, rekonstruerer

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

og efterprøver længden:

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

Trin 6: Nogen ændrer anmeldelsesteksten

Ændres teksten bagefter, ændrer indholdshashen sig og dermed punktet, lad os sige

c′=40.c'=40.

Den gamle signatur er stadig (3,2)(3,2), men

3+34⋅2=71≠40⟹Signatur ugyldig3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Signatur ugyldig}}

Vi kan slette en anmeldelse. Ændre den kan vi ikke, uden at det bliver opdaget.

Ærlighedsbemærkning til eksemplet

I to dimensioner kan en angriber uden videre prøve sig frem til korte løsninger — for c′=40c'=40 for eksempel (6,1)(6,1). Eksemplet er ikke sikkert; det viser kun mekanismen. Ved FALCON-1024 har vektoren 2048 koefficienter, og dér fører det ingen steder hen at prøve sig frem.

12. Hvorfor afrunder man ikke bare?

Metoden fra trin 3 hedder Babai-afrunding. Til et lærebogseksempel rækker den — til en rigtig signaturmetode ikke.

Grunden: De afrundede signaturer ligger ikke jævnt fordelt. Deres form afhænger af den hemmelige basis' geometri. Ud af tilstrækkeligt mange signaturer kunne denne geometri rekonstrueres — og dermed den private nøgle. Netop det er tidligere gitterbaserede signaturmetoder strandet på.

FALCON trækker derfor de korte vektorer fra en diskret gaussisk fordeling over gitteret:

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

Værdier tæt på målpunktet er mere sandsynlige, men hvilken der præcis vælges, er tilfældigt. Resultatet er en fordeling, der intet røber om den anvendte basis — matematisk: Den kan ikke skelnes fra en fordeling, der kun afhænger af gitteret selv.

Denne sampler er den mest krævende del af FALCON. Den kører rekursivt over en træstruktur og arbejder med flydende-komma-tal — hvilket gør implementeringen vanskelig og er hovedgrunden til, at FALCON er sværere at få korrekt end ML-DSA.

13. Hvad der faktisk bliver overført

Signaturen består af

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

Kun s2s_2 — ikke parret. s1s_1 beregner den, der verificerer, selv:

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

Da koefficienterne i s2s_2 er små og spreder sig omkring nul, kan de komprimeres kraftigt. Det er grunden til FALCONs påfaldende kompakte signaturer:

offentlig nøglesignatur
FALCON-512897 B~666 B
FALCON-10241.793 B~1.280 B

Til sammenligning: ML-DSA-87 kræver 4.627 byte. Hos McGesund sidder ingen af disse signaturer dog i selve QR-koden — klistermærket bærer kun Ed25519-konvolutten; PQ-stemplerne ligger ved datasættet og hentes ind ved verifikationen. Størrelsen afgør altså ikke her, om det kan trykkes, men lagring og overførsel: Et FALCON-stempel er godt en fjerdedel så stort som et ML-DSA-stempel.

14. Hvorfor FALCON verificerer hurtigt

Naiv polynomiemultiplikation koster

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

Med den hurtige fouriertransformation falder det til omtrent

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

Ved n=1024n=1024 er det forskellen mellem en million og omkring ti tusind operationer. Derfor kører verifikationen i en besøgendes browser på millisekunder — og derfor sidder F'et i navnet:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Forløbet i billeder

SIGNATURTJENESTE (MCGESUND)DEN BESØGENDES BROWSERprivat nøgle (f, g, F, G — kort basis)payload m = {virksomhed, anmeldelse, h, rh, iat}salt r + HashToPoint(r ‖ m) = cgaussisk sampling: kort vektor (s₁, s₂)signatur σ = (r, s₂) + kidanmeldelse + σ + offentlig nøgle hberegn c på ny, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?gyldigugyldig
Fra payload til fluebenet i browseren. Alt over skillelinjen sker én gang ved indsendelsen, alt under den på ny hos hver besøgende — på hans eget udstyr, med den offentlige nøgle.

16. Hvorfor en angriber ikke kommer igennem

Han kender hh og dermed hele gitteret. Han kender også målpunktet cc, så snart anmeldelsen er offentlig. Det, han mangler, er den korte basis.

For at forfalske en anmeldelse skulle han finde en kort vektor til et selvvalgt cc — alene ud fra den offentlige beskrivelse. Det er den opgave, som trin 4 i eksemplet illustrerede: Uden de gode vektorer ender den samme beregning ved en alt for lang løsning.

I dimension 1024 er de bedste kendte metoder — klassiske såvel som kvantebaserede — langt fra det.

Signering: hurtigVerifikation: hurtigForfalskning: svær\boxed{\text{Signering: hurtig}\quad \text{Verifikation: hurtig}\quad \text{Forfalskning: svær}}

17. Hvad McGesund konkret bruger det til

Konvolutten. Hver signeret anmeldelse bærer en Ed25519-signatur. Det er den obligatoriske variant — klassisk, meget lille, nativt verificerbar i enhver browser.

Post-kvantestemplerne. Ved siden af ligger en eller to kvanteresistente signaturer. Hvilke, afhænger af abonnementet:

Abonnementtilgængelige signaturniveauer
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, begge parallelt

Den parallelle variant er bevidst redundant. FALCON står på NTRU-gitre, ML-DSA på module-gitre. Skulle en af de to familier være svagere end antaget i dag, bærer den anden videre.

Tidsankeret. Signaturnøglens fingeraftryk forankres via OpenTimestamps i en Bitcoin-blok. Dermed er det ikke kun påvist, at signaturen er ægte, men også at den allerede eksisterede på et bestemt tidspunkt — uden at nogen behøver tro på vores tidsstempel.

Alt dette bliver beregnet i læserens browser via et WASM-modul. Vi leverer data; verifikationen kører på den besøgendes eget udstyr. Gik vi af nettet i morgen, ville en allerede indlæst anmeldelse stadig kunne verificeres.

Om navnene: FALCON standardiseres i øjeblikket som FN-DSA; udkastet er tiltænkt som FIPS 206, men er endnu ikke færdiggjort. Derfor hedder niveauerne i McGesund-koden FN-DSA-512 og FN-DSA-1024, selv om man i daglig tale fortsat taler om FALCON.

18. Den vigtigste intuition

Den offentlige nøgle er den fuldstændige beskrivelse af en labyrint. Alle må gerne se den.

Signaturen er beviset: „Jeg har fundet en meget kort vej for præcis denne anmeldelse."

Den private nøgle er kendskabet til genvejene.

Læseren behøver ikke kende genvejene. Han måler kun efter, om den fremlagte vej faktisk er kort og faktisk hører til denne anmeldelse. Begge dele kan han uden os.

FALCON forvandler en anmeldelse til et punkt i et gitterog underskriften til en kort vej derhen.\boxed{ \begin{array}{c} \text{FALCON forvandler en anmeldelse til et punkt i et gitter}\\ \text{og underskriften til en kort vej derhen.} \end{array}}

Den, der ændrer teksten, flytter punktet — og den gamle vej fører ud i ingenting.