Signaturmetoder

FALCON matematiskt förklarat

Hur ett omdöme på McGesund undertecknas med FN-DSA (FALCON) — och varför ett ändrat tecken bryter underskriften.

Uppdaterat: 2026-09-07

1. Vad det handlar om

Ett omdöme på McGesund är inte ett textfält i en databas som man bara får tro på. Det signeras digitalt när det skickas in, och varje besökare kan senare räkna efter signaturen i sin egen webbläsare.

För en del av dessa signaturer använder vi FALCON — närmare bestämt FN-DSA-512 och FN-DSA-1024. Denna artikel förklarar vad som matematiskt sker.

Viktigt att slå fast först:

FALCON är ingen kryptering. Omdömestexten ska ju läsas. FALCON bevisar inte sekretess, utan ursprung och oförändrat innehåll.

2. Vad som exakt signeras

Det som signeras är inte den löpande texten, utan ett kompakt dataobjekt som entydigt spikar fast texten:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<Företags-ID>",
  "c":   "<Omdömes-ID>",
  "h":   "<SHA-256 av omdömestexten>",
  "rh":  "<SHA-256 av hela den inskickade datamängden>",
  "rv":  1,
  "qh":  "<SHA-256 av QR-envelopen, endast vid QR-omdömen>",
  "iat": 1757203200
}

Detta är vårt meddelande mm. Det binder samman:

  1. vilket företag omdömet hör till (f),
  2. vilket omdöme det gäller (c),
  3. vilken text som låg bakom — som hashvärde (h),
  4. vilken datamängd som lämnades in i sin helhet (rh): text, hjärtan, geostatus och uppgifter om anledning, kanoniskt serialiserade och hashade, i schemaversionen rv,
  5. ur vilken QR-kod omdömet kommer (qh) — vid ett omdöme utan QR utgår fältet,
  6. när signeringen skedde (iat).

Ett ändrat tecken i omdömestexten bryter denna kedja. Det är just avsikten — och sedan rh gäller detsamma för ett i efterhand förskjutet hjärta eller en ändrad geostatus.

3. Grundproblemet

En läsare som kommer till en företagsprofil står inför två frågor:

  1. Kommer detta omdöme verkligen från McGesund-systemet?
  2. Har det ändrats i efterhand?

För detta finns ett nyckelpar:

  • en privat nyckel — stannar i signaturtjänsten
  • en offentlig nyckel — får alla ha

Signeringen sker med den privata, verifieringen med den offentliga nyckeln. Och det på läsarens enhet, inte på vår server.

4. Varför FALCON?

Många av dagens signaturmetoder vilar på problem som är svåra för klassiska datorer, men som skulle kunna bli betydligt lättare för tillräckligt stora kvantdatorer.

Vid ett omdöme är det mer relevant än vid ett flyktigt meddelande: ett omdöme ska gå att kontrollera om fem eller tio år. Den som undertecknar i dag undertecknar för hela postens livslängd.

FALCON vilar därför på gitterkryptografi:

Man bygger ett matematiskt enkelt beskrivbart gitter där en bestämd sökuppgift är extremt svår.

5. Vad är ett matematiskt gitter?

Två vektorer:

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

Alla heltalskombinationer

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

ger ett gitter av punkter. Till exempel:

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
Två vektorer spänner upp ett gitter. Varje punkt är en heltalskombination av de båda — den markerade uppstår ur två gånger v₁ och tre gånger v₂.

Det avgörande är:

Gittret självt är lätt att beskriva. Att hitta bestämda egenskaper i det är mycket svårt.

6. Hemligheten är korta vektorer

Den klassiska svåra uppgiften lyder:

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

Det är Shortest Vector Problem. I två dimensioner kan man pröva sig fram. FALCON arbetar i dimension 512 eller 1024 — där är det utsiktslöst.

lång basnästan parallellakortaste vektorn
Samma gitter, två beskrivningar. De grå vektorerna genererar det också, men de är långa och nästan parallella — en dålig bas. Den korta vektorn är det som är svårt att hitta.

FALCON behöver dock inte den kortaste vektorn rakt av, utan något besläktat: att till en given målpunkt hitta en näraliggande gitterpunkt. Även det är svårt utan rätt tilläggsinformation.

målpunkt ur omdömetnära gitterpunktlångt bort
Målpunkten ur omdömet (ihålig cirkel) ligger inte i gittret. Sökt är en gitterpunkt tätt intill — den streckade vägen till en avlägsen punkt är också en lösning på det första villkoret, men inte en kort sådan.

7. Polynom i stället för tal

FALCON använder ett NTRU-gitter och räknar med polynom. Alltså med koefficientlistor i stället för enskilda tal:

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.

Räkningen sker i ringen

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

Det betyder:

  • Zq\mathbb{Z}_q: räkning modulo qq. Vid q=7q=7 till exempel 10≡310\equiv3, eftersom 10−7=310-7=3.
  • xn=−1x^n=-1: håller polynomen på fast längd.

FALCON använder konkret:

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

8. Det centrala knepet

Den privata nyckeln består av fyra små polynom

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

med NTRU-ekvationen

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

Dessa fyra bildar tillsammans en hemlig, välartad gitterbas — en beskrivning av gittret med korta vektorer.

Den offentliga nyckeln är i allt väsentligt ett enda polynom:

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

Ur hh följer samma gitter, men i en ohanterlig bas av långa vektorer:

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

Det är hela kärnan i FALCON. Båda baserna beskriver samma gitter. Bara det att den ena går att räkna med och den andra inte.

Man kan tänka sig det som en stadskarta: offentlig är den fullständiga kartan. Hemlig är kunskapen om genvägarna.

9. Omdömet blir en punkt

Innan signeringen går nyttolastobjektet genom en hashfunktion. FALCON använder för detta Hash-to-Point: ur meddelandet blir inget talvärde, utan direkt en punkt i ringen.

Dessutom drar signaturtjänsten ett slumpmässigt salt rr (320 bitar) och hashar in det:

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

Saltet är ingen utsmyckning. Utan det skulle samma omdöme alltid ge samma signatur, och ur många signaturer skulle den hemliga basen gå att rekonstruera. Det följer därför med in i signaturen.

10. Vad en giltig signatur är

Sökt är ett par

(s1,s2)(s_1,s_2)

med två egenskaper:

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

Det första villkoret ensamt är trivialt att uppfylla — man sätter s2=0s_2=0 och s1=cs_1=c. Det andra villkoret gör uppgiften svår.

Kortheten a¨r signaturen.\boxed{\text{Kortheten är signaturen.}}

11. Ett fullständigt genomräknat miniexempel

Vi krymper allt till leksaksformat: polynom med bara en koefficient, alltså vanliga tal, och

q=97.q=97.

Den hemliga nyckeln. Två små tal:

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

Den offentliga nyckeln. Det gäller 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, eftersom 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Alltså:

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

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

Den offentliga basen följer direkt ur hh:

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

Båda ligger i LL — och båda är långa.

Den hemliga basen känner bara signaturtjänsten:

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

eftersom −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 och −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Determinanten är

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

NTRU-ekvationen går alltså ihop. Båda vektorerna är korta.

Steg 1: Hasha omdömet

Anta att omdömets nyttolastobjekt ger

c=71.c=71.

Steg 2: En första, dålig lösning

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

uppfyller 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Men längden är 7171 — alldeles för lång.

Steg 3: Korta ned med den hemliga basen

Signaturtjänsten uttrycker målpunkten i sin korta bas:

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

Det leder till a≈−10,25a\approx-10{,}25 och b≈−2,20b\approx-2{,}20. Avrundat till a=−10a=-10, b=−2b=-2 ger det gitterpunkten

−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, alltså faktiskt i LL. Subtrahera:

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

Längd:

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

Det är signaturen.

Steg 4: Samma metod med den offentliga basen

Den som bara känner h=34h=34 har basen {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Samma avrundningsberäkning ger där gitterpunkten (97,0)(97,0) och därmed

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

Också en giltig lösning på ekvationen — men sju gånger längre. Sätts acceptansgränsen under 26 är den värdelös.

Samma algoritm, samma gitter, samma ma˚lpunkt.Bara basen skiljer sig — och da¨rmed resultatet.\boxed{ \begin{array}{c} \text{Samma algoritm, samma gitter, samma målpunkt.}\\ \text{Bara basen skiljer sig — och därmed resultatet.} \end{array}}

Det är FALCONs fallucka på en rad.

Steg 5: Webbläsaren verifierar

Webbläsaren får omdömet, saltet och s2=2s_2=2. Den beräknar hashen på nytt, får c=71c=71, rekonstruerar

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

och prövar längden:

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

Steg 6: Någon ändrar omdömestexten

Ändras texten i efterhand ändras innehållshashen och därmed punkten, säg

c′=40.c'=40.

Den gamla signaturen förblir (3,2)(3,2), men

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

Vi kan radera ett omdöme. Ändra det kan vi inte utan att det märks.

Ärlighetsanmärkning om exemplet

I två dimensioner kan en angripare helt enkelt pröva sig fram till korta lösningar — för c′=40c'=40 till exempel (6,1)(6,1). Exemplet är inte säkert; det visar bara mekanismen. Hos FALCON-1024 har vektorn 2048 koefficienter, och där leder prövande ingenstans.

12. Varför avrundar man inte bara?

Metoden ur steg 3 heter Babai-avrundning. För ett läroboksexempel räcker den — för en verklig signaturmetod inte.

Skälet: de avrundade signaturerna ligger inte jämnt fördelade. Deras form beror på den hemliga basens geometri. Ur tillräckligt många signaturer skulle denna geometri gå att rekonstruera — och därmed den privata nyckeln. Just på detta har tidigare gitterbaserade signaturmetoder gått bet.

FALCON drar därför de korta vektorerna ur en diskret gaussfördelning över gittret:

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

Värden nära målpunkten är mer sannolika, men vilket som exakt väljs är slumpmässigt. Resultatet är en fördelning som inte avslöjar något om den använda basen — matematiskt: den går inte att skilja från en fördelning som bara beror på gittret självt.

Denna sampler är den mest krävande delen av FALCON. Den löper rekursivt över en trädstruktur och arbetar med flyttal — vilket gör implementationen känslig och är huvudskälet till att FALCON är svårare att genomföra korrekt än ML-DSA.

13. Vad som faktiskt överförs

Signaturen består av

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

Endast s2s_2 — inte paret. s1s_1 räknar verifieraren fram själv:

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

Eftersom koefficienterna i s2s_2 är små och sprider sig runt noll går de att komprimera kraftigt. Det är skälet till FALCONs påfallande kompakta signaturer:

offentlig nyckelsignatur
FALCON-512897 B~666 B
FALCON-10241 793 B~1 280 B

Som jämförelse: ML-DSA-87 behöver 4 627 byte. Hos McGesund sitter dock ingen av dessa signaturer i själva QR-koden — dekalen bär endast Ed25519-envelopen; PQ-stämplarna ligger vid datamängden och laddas in vid verifieringen. Storleken avgör här alltså inte tryckbarheten, utan lagring och överföring: en FALCON-stämpel är drygt en fjärdedel så stor som en ML-DSA-stämpel.

14. Varför FALCON verifierar snabbt

Naiv polynommultiplikation kostar

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

Med den snabba fouriertransformen sjunker det till ungefär

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

Vid n=1024n=1024 är det skillnaden mellan en miljon och runt tiotusen operationer. Därför löper verifieringen i en besökares webbläsare på millisekunder — och därför sitter F:et i namnet:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Förloppet i bild

SIGNATURTJÄNST (MCGESUND)BESÖKARENS WEBBLÄSAREprivat nyckel (f, g, F, G — kort bas)Nyttolast m = {företag, omdöme, h, rh, iat}Salt r + HashToPoint(r ‖ m) = cGauss-sampling: kort vektor (s₁, s₂)Signatur σ = (r, s₂) + kidOmdöme + σ + offentlig nyckel hräkna om c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?giltigogiltig
Från nyttolast till bocken i webbläsaren. Allt ovanför skiljelinjen sker en gång vid inskickandet, allt därunder på nytt hos varje besökare — på hans enhet, med den offentliga nyckeln.

16. Varför en angripare misslyckas

Han känner till hh och därmed hela gittret. Han känner också målpunkten cc, så snart omdömet är offentligt. Vad han saknar är den korta basen.

För att förfalska ett omdöme skulle han behöva hitta en kort vektor till ett självvalt cc — enbart ur den offentliga beskrivningen. Det är den uppgift som steg 4 i exemplet illustrerade: utan de goda vektorerna landar samma beräkning i en alldeles för lång lösning.

I dimension 1024 är de bästa kända metoderna — såväl klassiska som kvantbaserade — långt ifrån detta.

Signera: snabbtVerifiera: snabbtFo¨rfalska: sva˚rt\boxed{\text{Signera: snabbt}\quad \text{Verifiera: snabbt}\quad \text{Förfalska: svårt}}

17. Vad McGesund konkret gör med detta

Envelopen. Varje signerat omdöme bär en Ed25519-signatur. Det är obligatoriet — klassisk, mycket liten, nativt verifierbar i varje webbläsare.

Post-kvantstämplarna. Bredvid ligger en eller två kvantresistenta signaturer. Vilka beror på abonnemanget:

Abonnemangtillgängliga signaturnivåer
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, båda parallellt

Den parallella varianten är medvetet redundant. FALCON står på NTRU-gitter, ML-DSA på modulgitter. Skulle en av de båda familjerna vara svagare än vad man i dag antar bär den andra vidare.

Tidsankaret. Signaturnyckelns fingeravtryck förankras via OpenTimestamps i ett Bitcoin-block. Därmed är inte bara belagt att signaturen är äkta, utan också att den redan fanns vid en bestämd tidpunkt — utan att någon behöver tro på vår tidsstämpel.

Allt detta räknas i läsarens webbläsare, via en WASM-modul. Vi levererar data; verifieringen löper på besökarens enhet. Gick vi ned från nätet i morgon skulle ett en gång laddat omdöme förbli kontrollerbart.

Om namnen: FALCON standardiseras för närvarande som FN-DSA; utkastet är avsett som FIPS 206, men är ännu inte avslutat. Därför heter nivåerna i McGesund-koden FN-DSA-512 och FN-DSA-1024, även om man i språkbruket fortsatt talar om FALCON.

18. Den viktigaste intuitionen

Den offentliga nyckeln är den fullständiga beskrivningen av en labyrint. Alla får titta på den.

Signaturen är beviset: "Jag har hittat en mycket kort väg för just detta omdöme."

Den privata nyckeln är kunskapen om genvägarna.

Läsaren behöver inte känna genvägarna. Han mäter bara efter om den framlagda vägen verkligen är kort och verkligen hör till detta omdöme. Bådadera kan han göra utan oss.

FALCON fo¨rvandlar ett omdo¨me till en punkt i ett gitteroch underskriften till en kort va¨g dit.\boxed{ \begin{array}{c} \text{FALCON förvandlar ett omdöme till en punkt i ett gitter}\\ \text{och underskriften till en kort väg dit.} \end{array}}

Den som ändrar texten flyttar punkten — och den gamla vägen leder ut i tomma intet.