Allekirjoitusmenetelmä

FALCON matemaattisesti selitettynä

Miten McGesund-arvio allekirjoitetaan FN-DSA:lla (FALCON) — ja miksi yksi muutettu merkki rikkoo allekirjoituksen.

Päivitetty: 2026-09-07

1. Mistä tässä on kyse

Arvio McGesundissa ei ole tietokannan tekstikenttä, johon on vain uskottava. Se allekirjoitetaan digitaalisesti lähetyshetkellä, ja jokainen kävijä voi myöhemmin laskea allekirjoituksen uudelleen omassa selaimessaan.

Osaan näistä allekirjoituksista käytämme FALCONia — tarkemmin sanottuna menetelmiä FN-DSA-512 ja FN-DSA-1024. Tämä kirjoitus selittää, mitä siinä matemaattisesti tapahtuu.

Tärkeä huomautus aluksi:

FALCON ei ole salausmenetelmä. Arviotekstihän on tarkoitettu luettavaksi. FALCON ei todista salassapitoa vaan alkuperän ja eheyden.

2. Mitä tarkalleen allekirjoitetaan

Allekirjoitettavana ei ole leipäteksti vaan tiivis tietokohde, joka naulaa tekstin yksikäsitteisesti kiinni:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<yritystunnus>",
  "c":   "<arviotunnus>",
  "h":   "<arviotekstin SHA-256>",
  "rh":  "<koko lähetystietueen SHA-256>",
  "rv":  1,
  "qh":  "<QR-Envelopen SHA-256, vain QR-arvioissa>",
  "iat": 1757203200
}

Tämä on viestimme mm. Se sitoo yhteen:

  1. mihin yritykseen arvio kuuluu (f),
  2. mistä arviosta on kyse (c),
  3. mikä teksti sen takana oli — tiivistearvona (h),
  4. mikä tietue kokonaisuudessaan lähetettiin (rh): teksti, sydämet, sijaintitila ja käynnin syytä koskevat tiedot, kanonisesti sarjallistettuina ja tiivistettyinä, skeemaversiossa rv,
  5. mistä QR-koodista arvio on peräisin (qh) — ilman QR-koodia annetussa arviossa kenttä jää pois,
  6. milloin allekirjoitettiin (iat).

Yksi muutettu merkki arviotekstissä rikkoo tämän ketjun. Juuri se on tarkoitus — ja kentän rh myötä sama pätee jälkikäteen siirrettyyn sydämeen tai muutettuun sijaintitilaan.

3. Perusongelma

Yritysprofiilille saapuva lukija kohtaa kaksi kysymystä:

  1. Onko tämä arvio todella peräisin McGesund-järjestelmästä?
  2. Onko sitä muutettu jälkikäteen?

Sitä varten on avainpari:

  • yksityinen avain — pysyy allekirjoituspalvelussa
  • julkinen avain — saa olla kenellä tahansa

Allekirjoittaminen tapahtuu yksityisellä, todentaminen julkisella avaimella. Ja nimenomaan lukijan laitteella, ei meidän palvelimellamme.

4. Miksi FALCON?

Monet nykyiset allekirjoitusmenetelmät perustuvat ongelmiin, jotka ovat klassisille tietokoneille vaikeita mutta voisivat riittävän suurille kvanttitietokoneille muuttua selvästi helpommiksi.

Arvion kohdalla tämä on olennaisempaa kuin ohimenevässä viestissä: arvion on määrä olla todennettavissa vielä viiden tai kymmenen vuoden kuluttua. Se, joka allekirjoittaa tänään, allekirjoittaa merkinnän koko elinkaareksi.

Siksi FALCON perustuu hilakryptografiaan:

Rakennetaan matemaattisesti helposti kuvattava hila, jossa tietty hakutehtävä on äärimmäisen vaikea.

5. Mikä on matemaattinen hila?

Kaksi vektoria:

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

Kaikki kokonaislukukertoimiset yhdistelmät

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

muodostavat pisteistä koostuvan hilan. Esimerkiksi:

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
Kaksi vektoria virittää hilan. Jokainen piste on näiden kahden kokonaislukukertoiminen yhdistelmä — merkitty piste syntyy kahdesta v₁:stä ja kolmesta v₂:sta.

Ratkaisevaa on:

Hila itse on helppo kuvata. Tiettyjen ominaisuuksien löytäminen siitä on hyvin vaikeaa.

6. Salaisuus on lyhyissä vektoreissa

Klassinen vaikea tehtävä kuuluu:

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

Tämä on Shortest Vector Problem. Kahdessa ulottuvuudessa sen voi ratkaista kokeilemalla. FALCON toimii ulottuvuudessa 512 tai 1024 — siellä se on toivotonta.

pitkä kantalähes yhdensuuntainenlyhin vektori
Sama hila, kaksi kuvausta. Harmaat vektorit virittävät sen niin ikään, mutta ovat pitkiä ja lähes yhdensuuntaisia — huono kanta. Lyhyt vektori on se, mitä on vaikea löytää.

FALCON ei kuitenkaan tarvitse kaikkein lyhintä vektoria sinänsä, vaan jotakin siihen liittyvää: ennalta annettua kohdepistettä lähellä olevan hilapisteen löytämistä. Sekin on vaikeaa ilman oikeaa lisätietoa.

arviosta saatu kohdepisteläheinen hilapistekaukana
Arviosta saatu kohdepiste (ontto ympyrä) ei ole hilassa. Etsitään aivan sen vierestä hilapistettä — katkoviivalla merkitty reitti kaukaiseen pisteeseen on niin ikään ensimmäisen ehdon ratkaisu, mutta ei lyhyt.

7. Polynomit lukujen sijaan

FALCON käyttää NTRU-hilaa ja laskee polynomeilla. Yksittäisten lukujen sijaan siis kerroinlistoilla:

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.

Laskutoimitukset tehdään renkaassa

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

Se tarkoittaa:

  • Zq\mathbb{Z}_q: laskeminen modulo qq. Kun q=7q=7, esimerkiksi 10≡310\equiv3, sillä 10−7=310-7=3.
  • xn=−1x^n=-1: pitää polynomit kiinteän mittaisina.

FALCON käyttää konkreettisesti:

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

8. Keskeinen temppu

Yksityinen avain koostuu neljästä pienestä polynomista

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

NTRU-yhtälön mukaisesti

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

Nämä neljä muodostavat yhdessä salaisen, hyväluontoisen hilakannan — hilan kuvauksen lyhyistä vektoreista.

Julkinen avain on olennaisesti yksi ainoa polynomi:

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

Polynomista hh saadaan sama hila, mutta kömpelössä kannassa, joka koostuu pitkistä vektoreista:

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

Tämä on FALCONin koko ydin. Molemmat kannat kuvaavat samaa hilaa. Toinen vain kelpaa laskemiseen ja toinen ei.

Sen voi kuvitella kaupungin karttana: julkista on täydellinen kartta. Salaista on oikoteiden tuntemus.

9. Arviosta tulee piste

Ennen allekirjoittamista payload-kohde kulkee tiivistefunktion läpi. FALCON käyttää siihen hash-to-point-menettelyä: viestistä ei tule lukuarvoa vaan suoraan piste renkaassa.

Lisäksi allekirjoituspalvelu arpoo satunnaisen saltin rr (320 bittiä) ja tiivistää sen mukaan:

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

Salt ei ole koriste. Ilman sitä sama arvio tuottaisi aina saman allekirjoituksen, ja useista allekirjoituksista voitaisiin rekonstruoida salainen kanta. Siksi se kulkee mukana allekirjoitukseen.

10. Mikä on kelvollinen allekirjoitus

Etsitään paria

(s1,s2)(s_1,s_2)

jolla on kaksi ominaisuutta:

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

Pelkkä ensimmäinen ehto on triviaalisti täytettävissä — asetetaan s2=0s_2=0 ja s1=cs_1=c. Toinen ehto tekee tehtävästä vaikean.

Lyhyys on allekirjoitus.\boxed{\text{Lyhyys on allekirjoitus.}}

11. Täysin läpi laskettu miniesimerkki

Kutistamme kaiken lelukokoon: polynomit, joissa on vain yksi kerroin, siis tavallisia lukuja, ja

q=97.q=97.

Yksityinen avain. Kaksi pientä lukua:

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

Julkinen avain. On 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, sillä 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Siis:

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

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

Julkinen kanta saadaan suoraan luvusta hh:

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

Molemmat kuuluvat joukkoon LL — ja molemmat ovat pitkiä.

Salaisen kannan tuntee vain allekirjoituspalvelu:

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

sillä −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 ja −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Determinantti on

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

joten NTRU-yhtälö menee tasan. Molemmat vektorit ovat lyhyitä.

Askel 1: Arvion tiivistäminen

Oletetaan, että arvion payload-kohteesta tulee

c=71.c=71.

Askel 2: Ensimmäinen, huono ratkaisu

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

toteuttaa ehdon 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Mutta pituus on 7171 — aivan liian pitkä.

Askel 3: Lyhentäminen salaisen kannan avulla

Allekirjoituspalvelu ilmaisee kohdepisteen lyhyessä kannassaan:

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

Siitä seuraa a≈−10,25a\approx-10{,}25 ja b≈−2,20b\approx-2{,}20. Pyöristettynä arvoihin a=−10a=-10, b=−2b=-2 saadaan hilapiste

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

Tarkistus: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, siis todella joukossa LL. Vähennetään:

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

Pituus:

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

Tämä on allekirjoitus.

Askel 4: Sama menettely julkisella kannalla

Sillä, joka tuntee vain arvon h=34h=34, on kanta {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Sama pyöristyslasku antaa siellä hilapisteen (97,0)(97,0) ja siten

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

Niin ikään kelvollinen yhtälön ratkaisu — mutta seitsemän kertaa pidempi. Jos hyväksymisraja asetetaan alle 26:n, se on arvoton.

Sama algoritmi, sama hila, sama kohdepiste.Vain kanta on eri — ja sen myo¨ta¨ tulos.\boxed{ \begin{array}{c} \text{Sama algoritmi, sama hila, sama kohdepiste.}\\ \text{Vain kanta on eri — ja sen myötä tulos.} \end{array}}

Tämä on FALCONin salaluukku yhdellä rivillä.

Askel 5: Selain tarkistaa

Selain saa arvion, saltin ja arvon s2=2s_2=2. Se laskee tiivisteen uudelleen, saa c=71c=71, rekonstruoi

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

ja tarkistaa pituuden:

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

Askel 6: Joku muuttaa arviotekstiä

Jos tekstiä muutetaan jälkikäteen, sisältötiiviste muuttuu ja sen myötä piste, sanotaan

c′=40.c'=40.

Vanha allekirjoitus pysyy arvossa (3,2)(3,2), mutta

3+34⋅2=71≠40⟹Allekirjoitus virheellinen3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Allekirjoitus virheellinen}}

Voimme poistaa arvion. Muuttaa emme voi sitä ilman, että se huomataan.

Rehellisyyshuomautus esimerkistä

Kahdessa ulottuvuudessa hyökkääjä voi yksinkertaisesti kokeilla lyhyitä ratkaisuja läpi — arvolle c′=40c'=40 vaikkapa (6,1)(6,1). Esimerkki ei ole turvallinen; se näyttää vain mekanismin. FALCON-1024:ssä vektorilla on 2048 kerrointa, eikä siellä kokeileminen johda mihinkään.

12. Miksei yksinkertaisesti pyöristetä?

Askeleen 3 menettelyä kutsutaan Babain pyöristykseksi. Oppikirjaesimerkkiin se riittää — todelliseen allekirjoitusmenetelmään ei.

Syy: pyöristetyt allekirjoitukset eivät jakaudu tasaisesti. Niiden muoto riippuu salaisen kannan geometriasta. Riittävän monesta allekirjoituksesta tämä geometria olisi rekonstruoitavissa — ja sen myötä yksityinen avain. Juuri tähän aiemmat hilapohjaiset allekirjoitusmenetelmät ovat kaatuneet.

Siksi FALCON arpoo lyhyet vektorit diskreetistä Gaussin jakaumasta hilan yli:

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

Kohdepistettä lähellä olevat arvot ovat todennäköisempiä, mutta se, mikä niistä tarkalleen valitaan, on satunnaista. Tuloksena on jakauma, joka ei paljasta mitään käytetystä kannasta — matemaattisesti: sitä ei voi erottaa jakaumasta, joka riippuu vain hilasta itsestään.

Tämä sampleri on FALCONin vaativin osa. Se etenee rekursiivisesti puurakenteen yli ja käyttää liukulukuja — mikä tekee toteutuksesta arkaluontoisen ja on tärkein syy siihen, että FALCON on vaikeampi toteuttaa oikein kuin ML-DSA.

13. Mitä todella siirretään

Allekirjoitus koostuu osista

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

Vain s2s_2 — ei pari. Osan s1s_1 laskee todentaja itse:

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

Koska s2s_2:n kertoimet ovat pieniä ja hajaantuvat nollan ympärille, ne ovat vahvasti pakattavissa. Se on syy FALCONin silmiinpistävän tiiviisiin allekirjoituksiin:

julkinen avainallekirjoitus
FALCON-512897 B~666 B
FALCON-10241 793 B~1 280 B

Vertailun vuoksi: ML-DSA-87 tarvitsee 4 627 tavua. McGesundissa mikään näistä allekirjoituksista ei kuitenkaan ole itse QR-koodissa — tarrassa on vain Ed25519-Envelope; post-kvanttileimat ovat tietueen yhteydessä ja ladataan todennettaessa. Koko ei siis ratkaise tässä tulostettavuutta vaan muistin ja siirron: FALCON-leima on kooltaan runsas neljäsosa ML-DSA-leimasta.

14. Miksi FALCON todentaa nopeasti

Polynomien kertolasku naiivisti maksaa

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

Nopealla Fourier-muunnoksella se laskee suunnilleen tasolle

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

Kun n=1024n=1024, se on ero miljoonan ja noin kymmenentuhannen operaation välillä. Siksi todennus kävijän selaimessa kestää millisekunteja — ja siksi nimessä on F:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Kulku kuvana

ALLEKIRJOITUSPALVELU (MCGESUND)KÄVIJÄN SELAINyksityinen avain (f, g, F, G — lyhyt kanta)payload m = {yritys, arvio, h, rh, iat}salt r + HashToPoint(r ‖ m) = cGauss-otanta: lyhyt vektori (s₁, s₂)allekirjoitus σ = (r, s₂) + kidarvio + σ + julkinen avain hc lasketaan uudelleen, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?kelvollinenvirheellinen
Payloadista selaimen valintamerkkiin. Kaikki erotusviivan yläpuolella tapahtuu kerran lähetettäessä, kaikki sen alapuolella jokaisen kävijän kohdalla uudelleen — hänen laitteellaan, julkisen avaimen turvin.

16. Miksi hyökkääjä epäonnistuu

Hän tuntee arvon hh ja siten koko hilan. Hän tuntee myös kohdepisteen cc heti, kun arvio on julkinen. Häneltä puuttuu lyhyt kanta.

Väärentääkseen arvion hänen pitäisi löytää itse valitsemalleen cc:lle lyhyt vektori — pelkän julkisen kuvauksen perusteella. Se on tehtävä, jota esimerkin askel 4 havainnollisti: ilman hyviä vektoreita sama lasku päätyy aivan liian pitkään ratkaisuun.

Ulottuvuudessa 1024 parhaat tunnetut menetelmät — sekä klassiset että kvanttipohjaiset — ovat siitä kaukana.

Allekirjoitus: nopeaTodennus: nopeaVa¨a¨renno¨s: vaikea\boxed{\text{Allekirjoitus: nopea}\quad \text{Todennus: nopea}\quad \text{Väärennös: vaikea}}

17. Mitä McGesund tekee tällä käytännössä

Envelope. Jokainen allekirjoitettu arvio kantaa Ed25519-allekirjoitusta. Se on pakollinen variantti — klassinen, hyvin pieni, natiivisti todennettavissa jokaisessa selaimessa.

Post-kvanttileimat. Sen rinnalla on yksi tai kaksi kvanttiresistenttiä allekirjoitusta. Mitkä, riippuu paketista:

Pakettikäytettävissä olevat allekirjoitustasot
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, molemmat rinnakkain

Rinnakkainen variantti on tarkoituksella redundantti. FALCON nojaa NTRU-hiloihin, ML-DSA moduulihiloihin. Jos toinen näistä perheistä osoittautuisi heikommaksi kuin nykyisin oletetaan, toinen kantaa edelleen.

Aikaankkuri. Allekirjoitusavaimen sormenjälki ankkuroidaan OpenTimestampsin kautta Bitcoin-lohkoon. Siten on osoitettu paitsi se, että allekirjoitus on aito, myös se, että se oli olemassa jo tiettynä ajankohtana — ilman että kenenkään täytyisi uskoa meidän aikaleimaamme.

Kaikki tämä lasketaan lukijan selaimessa WASM-moduulin kautta. Me toimitamme tiedot; todennus tapahtuu kävijän laitteella. Jos poistuisimme huomenna verkosta, kerran ladattu arvio pysyisi todennettavissa.

Nimien sijoittamisesta: FALCONia standardoidaan parhaillaan nimellä FN-DSA; luonnos on tarkoitus julkaista standardina FIPS 206, mutta työ ei ole vielä valmis. Siksi tasot ovat McGesundin koodissa nimeltään FN-DSA-512 ja FN-DSA-1024, vaikka kielenkäytössä puhutaan edelleen FALCONista.

18. Tärkein intuitio

Julkinen avain on labyrintin täydellinen kuvaus. Jokainen saa katsoa sitä.

Allekirjoitus on osoitus: ”Olen löytänyt juuri tälle arviolle hyvin lyhyen reitin.”

Yksityinen avain on oikoteiden tuntemus.

Lukijan ei tarvitse tuntea oikoteitä. Hän vain mittaa, onko esitetty reitti todella lyhyt ja kuuluuko se todella tähän arvioon. Molemmat hän voi tehdä ilman meitä.

FALCON muuttaa arvion hilan pisteeksi jaallekirjoituksen lyhyeksi reitiksi sinne.\boxed{ \begin{array}{c} \text{FALCON muuttaa arvion hilan pisteeksi ja}\\ \text{allekirjoituksen lyhyeksi reitiksi sinne.} \end{array}}

Se, joka muuttaa tekstiä, siirtää pistettä — ja vanha reitti johtaa tyhjään.