Schematy podpisu

FALCON wyjaśniony matematycznie

Jak opinia w McGesund zostaje podpisana za pomocą FN-DSA (FALCON) — i dlaczego jeden zmieniony znak łamie podpis.

Stan: 2026-09-07

1. O co tutaj chodzi

Opinia w McGesund nie jest polem tekstowym w bazie danych, któremu trzeba wierzyć. Przy wysłaniu zostaje podpisana cyfrowo, a każdy odwiedzający może później przeliczyć ten podpis w swojej własnej przeglądarce.

Do części tych podpisów używamy FALCON — dokładniej FN-DSA-512 i FN-DSA-1024. Ten artykuł wyjaśnia, co przy tym dzieje się matematycznie.

Ważna uwaga na wstępie:

FALCON nie jest szyfrowaniem. Tekst opinii ma przecież być czytany. FALCON nie dowodzi poufności, lecz pochodzenia i nienaruszalności.

2. Co dokładnie jest podpisywane

Podpisywany jest nie tekst ciągły, lecz kompaktowy obiekt danych, który jednoznacznie przybija tekst:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID firmy>",
  "c":   "<ID opinii>",
  "h":   "<SHA-256 tekstu opinii>",
  "rh":  "<SHA-256 całego rekordu przesłanej opinii>",
  "rv":  1,
  "qh":  "<SHA-256 koperty QR, tylko przy opiniach z QR>",
  "iat": 1757203200
}

To jest nasza wiadomość mm. Wiąże ona ze sobą:

  1. do jakiej firmy należy opinia (f),
  2. o którą opinię chodzi (c),
  3. jaki tekst za nią stał — jako wartość skrótu (h),
  4. jaki rekord został przesłany w całości (rh): tekst, serduszka, status geolokalizacji i informacje o okoliczności, kanonicznie zserializowane i zhaszowane, w wersji schematu rv,
  5. z którego kodu QR pochodzi opinia (qh) — przy opinii bez QR pole odpada,
  6. kiedy podpisano (iat).

Jeden zmieniony znak w tekście opinii łamie ten łańcuch. I dokładnie o to chodzi — a od czasu rh to samo dotyczy przesuniętego później serduszka albo zmienionego statusu geolokalizacji.

3. Problem podstawowy

Czytelnik, który trafia na profil firmy, staje przed dwoma pytaniami:

  1. Czy ta opinia rzeczywiście pochodzi z systemu McGesund?
  2. Czy została później zmieniona?

Służy do tego para kluczy:

  • klucz prywatny — pozostaje w usłudze podpisującej
  • klucz publiczny — może go mieć każdy

Podpisuje się kluczem prywatnym, weryfikuje publicznym. I to na urządzeniu czytelnika, a nie na naszym serwerze.

4. Dlaczego FALCON?

Wiele dzisiejszych metod podpisu opiera się na problemach, które dla klasycznych komputerów są trudne, ale dla dostatecznie dużych komputerów kwantowych mogłyby stać się wyraźnie łatwiejsze.

Przy opinii jest to bardziej istotne niż przy ulotnej wiadomości: opinia ma być sprawdzalna jeszcze za pięć albo dziesięć lat. Kto podpisuje dziś, podpisuje na cały okres życia wpisu.

FALCON opiera się dlatego na kryptografii kratowej:

Buduje się kratę, którą łatwo opisać matematycznie, a w której pewne zadanie wyszukiwania jest ekstremalnie trudne.

5. Czym jest krata matematyczna?

Dwa wektory:

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

Wszystkie całkowitoliczbowe kombinacje

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

tworzą kratę złożoną z punktów. Na przykład:

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
Dwa wektory rozpinają kratę. Każdy punkt jest całkowitoliczbową kombinacją obu — zaznaczony powstaje z dwóch v₁ i trzech v₂.

Rozstrzygające jest to, że:

Samą kratę łatwo opisać. Znalezienie w niej pewnych własności jest bardzo trudne.

6. Sekretem są krótkie wektory

Klasyczne trudne zadanie brzmi:

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

To Shortest Vector Problem, problem najkrótszego wektora. W dwóch wymiarach można go rozwiązać metodą prób. FALCON pracuje w wymiarze 512 albo 1024 — tam jest to beznadziejne.

długa bazaprawie równoległenajkrótszy wektor
Ta sama krata, dwa opisy. Szare wektory również ją generują, ale są długie i niemal równoległe — to zła baza. Krótki wektor jest tym, co trudno znaleźć.

FALCON potrzebuje jednak nie najkrótszego wektora jako takiego, lecz czegoś pokrewnego: znalezienia do zadanego punktu docelowego bliskiego punktu kraty. To również jest bez właściwej informacji dodatkowej trudne.

punkt docelowy z opiniibliski punkt kratydaleko
Punkt docelowy z opinii (pusty okrąg) nie leży w kracie. Szukany jest punkt kraty tuż obok — przerywana droga do odległego punktu również spełnia pierwszy warunek, tyle że nie jest krótka.

7. Wielomiany zamiast liczb

FALCON używa kraty NTRU i liczy na wielomianach. Zamiast na pojedynczych liczbach — na listach współczynników:

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.

Obliczenia prowadzone są w pierścieniu

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

To oznacza:

  • Zq\mathbb{Z}_q: liczenie modulo qq. Przy q=7q=7 na przykład 10≡310\equiv3, bo 10−7=310-7=3.
  • xn=−1x^n=-1: utrzymuje wielomiany na stałej długości.

FALCON używa konkretnie:

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

8. Centralna sztuczka

Klucz prywatny składa się z czterech małych wielomianów

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

z równaniem NTRU

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

Te cztery tworzą razem tajną, przyjazną bazę kraty — opis kraty złożony z krótkich wektorów.

Klucz publiczny to w istocie jeden jedyny wielomian:

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

Z hh wynika ta sama krata, ale w nieporęcznej bazie z długich wektorów:

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

To jest cały rdzeń FALCON. Obie bazy opisują tę samą kratę. Tyle że jedna nadaje się do liczenia, a druga nie.

Można to sobie wyobrazić jak plan miasta: publiczna jest pełna mapa. Tajna jest znajomość skrótów.

9. Opinia staje się punktem

Zanim nastąpi podpis, obiekt payload przechodzi przez funkcję skrótu. FALCON używa do tego Hash-to-Point: z wiadomości powstaje nie wartość liczbowa, lecz bezpośrednio punkt w pierścieniu.

Dodatkowo usługa podpisująca losuje sól rr (320 bitów) i haszuje ją razem z wiadomością:

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

Sól nie jest dodatkiem. Bez niej ta sama opinia dawałaby zawsze ten sam podpis, a z wielu podpisów dałoby się zrekonstruować tajną bazę. Dlatego wędruje razem do podpisu.

10. Czym jest ważny podpis

Szukana jest para

(s1,s2)(s_1,s_2)

o dwóch własnościach:

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

Pierwszy warunek sam w sobie jest trywialny do spełnienia — wystarczy przyjąć s2=0s_2=0 i s1=cs_1=c. To drugi warunek czyni zadanie trudnym.

Kroˊtkosˊcˊ jest podpisem.\boxed{\text{Krótkość jest podpisem.}}

11. W pełni przeliczony miniprzykład

Kurczymy wszystko do rozmiaru zabawki: wielomiany z tylko jednym współczynnikiem, czyli zwykłe liczby, oraz

q=97.q=97.

Klucz tajny. Dwie małe liczby:

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

Klucz publiczny. Zachodzi 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, bo 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Zatem:

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

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

Baza publiczna wynika wprost z hh:

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

Oba wektory leżą w LL — i oba są długie.

Bazę tajną zna tylko usługa podpisująca:

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

bo −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 oraz −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Wyznacznik wynosi

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

równanie NTRU jest więc spełnione. Oba wektory są krótkie.

Krok 1: Zhaszowanie opinii

Przyjmijmy, że obiekt payload opinii daje

c=71.c=71.

Krok 2: Pierwsze, złe rozwiązanie

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

spełnia 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Ale długość wynosi 7171 — o wiele za dużo.

Krok 3: Skracanie za pomocą tajnej bazy

Usługa podpisująca wyraża punkt docelowy w swojej krótkiej bazie:

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

Prowadzi to do a≈−10,25a\approx-10{,}25 i b≈−2,20b\approx-2{,}20. Po zaokrągleniu do a=−10a=-10, b=−2b=-2 powstaje punkt kraty

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

Kontrola: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, a więc rzeczywiście w LL. Odejmujemy:

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

Długość:

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

To jest podpis.

Krok 4: Ta sama procedura z bazą publiczną

Kto zna tylko h=34h=34, ma bazę {(97,0),(−34,1)}\{(97,0),(-34,1)\}. To samo zaokrąglanie daje tam punkt kraty (97,0)(97,0), a tym samym

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

Również poprawne rozwiązanie równania — ale siedmiokrotnie dłuższe. Jeśli próg akceptacji ustawić poniżej 26, jest ono bezwartościowe.

Ten sam algorytm, ta sama krata, ten sam punkt docelowy.Roˊz˙ni się tylko baza — a wraz z nią wynik.\boxed{ \begin{array}{c} \text{Ten sam algorytm, ta sama krata, ten sam punkt docelowy.}\\ \text{Różni się tylko baza — a wraz z nią wynik.} \end{array}}

To jest zapadka FALCON w jednej linijce.

Krok 5: Przeglądarka weryfikuje

Przeglądarka dostaje opinię, sól i s2=2s_2=2. Przelicza skrót na nowo, otrzymuje c=71c=71, rekonstruuje

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

i sprawdza długość:

∥(3,2)∥=13  ≤  β⟹Podpis waz˙ny\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Podpis ważny}}

Krok 6: Ktoś zmienia tekst opinii

Jeśli tekst zostanie później zmieniony, zmienia się skrót treści, a wraz z nim punkt, powiedzmy

c′=40.c'=40.

Stary podpis pozostaje (3,2)(3,2), ale

3+34⋅2=71≠40⟹Podpis niewaz˙ny3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Podpis nieważny}}

Opinię możemy usunąć. Zmienić jej nie możemy tak, żeby nikt tego nie zauważył.

Uwaga o rzetelności przykładu

W dwóch wymiarach atakujący może po prostu wypróbować krótkie rozwiązania — dla c′=40c'=40 na przykład (6,1)(6,1). Ten przykład nie jest bezpieczny; pokazuje jedynie mechanizm. Przy FALCON-1024 wektor ma 2048 współczynników i tam metoda prób nie prowadzi donikąd.

12. Dlaczego nie zaokrągla się po prostu?

Metoda z kroku 3 nazywa się zaokrąglaniem Babaia. Do przykładu podręcznikowego wystarcza — do prawdziwego schematu podpisu już nie.

Powód: zaokrąglone podpisy nie są rozłożone równomiernie. Ich kształt zależy od geometrii tajnej bazy. Z dostatecznie wielu podpisów dałoby się tę geometrię zrekonstruować — a wraz z nią klucz prywatny. Właśnie na tym poległy wcześniejsze kratowe schematy podpisu.

FALCON losuje dlatego krótkie wektory z dyskretnego rozkładu Gaussa nad kratą:

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

Wartości blisko punktu docelowego są bardziej prawdopodobne, ale to, która dokładnie zostanie wybrana, jest losowe. Wynikiem jest rozkład, który nie zdradza niczego o użytej bazie — matematycznie: jest nieodróżnialny od rozkładu zależnego wyłącznie od samej kraty.

Ten sampler jest najbardziej wymagającą częścią FALCON. Działa rekurencyjnie na strukturze drzewiastej i pracuje na liczbach zmiennoprzecinkowych — co czyni implementację delikatną i jest głównym powodem, dla którego FALCON trudniej poprawnie zaimplementować niż ML-DSA.

13. Co faktycznie jest przesyłane

Podpis składa się z

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

Tylko s2s_2 — nie cała para. s1s_1 weryfikujący wylicza sam:

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

Ponieważ współczynniki s2s_2 są małe i rozrzucone wokół zera, dają się mocno skompresować. To jest powód rzucająco się w oczy kompaktowych podpisów FALCON:

klucz publicznypodpis
FALCON-512897 B~666 B
FALCON-10241793 B~1280 B

Dla porównania: ML-DSA-87 potrzebuje 4627 bajtów. W McGesund żaden z tych podpisów nie tkwi jednak w samym kodzie QR — naklejka niesie tylko kopertę Ed25519; stemple PQ leżą przy rekordzie danych i są doładowywane przy weryfikacji. Rozmiar nie decyduje więc tutaj o drukowalności, lecz o pamięci i transmisji: stempel FALCON ma dobrą jedną czwartą rozmiaru stempla ML-DSA.

14. Dlaczego FALCON szybko weryfikuje

Naiwne mnożenie wielomianów kosztuje

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

Z szybką transformatą Fouriera spada to do mniej więcej

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

Przy n=1024n=1024 to różnica między milionem a około dziesięcioma tysiącami operacji. Dlatego weryfikacja w przeglądarce odwiedzającego trwa milisekundy — i dlatego w nazwie tkwi F:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Przebieg na rysunku

USŁUGA PODPISUJĄCA (MCGESUND)PRZEGLĄDARKA ODWIEDZAJĄCEGOklucz prywatny (f, g, F, G — krótka baza)payload m = {firma, opinia, h, rh, iat}sól r + HashToPoint(r ‖ m) = cpróbkowanie gaussowskie: krótki wektor (s₁, s₂)podpis σ = (r, s₂) + kidopinia + σ + klucz publiczny hprzeliczenie c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?ważnynieważny
Od payloadu po znacznik potwierdzenia w przeglądarce. Wszystko powyżej linii podziału dzieje się raz, przy wysłaniu, wszystko poniżej — na nowo u każdego odwiedzającego, na jego urządzeniu, z kluczem publicznym.

16. Dlaczego atakujący przegrywa

Zna hh, a tym samym całą kratę. Zna też punkt docelowy cc, gdy tylko opinia jest publiczna. Brakuje mu krótkiej bazy.

Aby sfałszować opinię, musiałby do samodzielnie wybranego cc znaleźć krótki wektor — wyłącznie z opisu publicznego. To jest zadanie, które zilustrował krok 4 przykładu: bez dobrych wektorów to samo obliczenie kończy się o wiele za długim rozwiązaniem.

W wymiarze 1024 najlepsze znane metody — zarówno klasyczne, jak i kwantowe — są od tego dalekie.

Podpisywanie: szybkoWeryfikacja: szybkoFałszowanie: trudno\boxed{\text{Podpisywanie: szybko}\quad \text{Weryfikacja: szybko}\quad \text{Fałszowanie: trudno}}

17. Co konkretnie robi z tym McGesund

Koperta. Każda podpisana opinia niesie podpis Ed25519. To wariant obowiązkowy — klasyczny, bardzo mały, natywnie weryfikowalny w każdej przeglądarce.

Stemple postkwantowe. Obok leżą jeden albo dwa podpisy odporne na ataki kwantowe. Które, zależy od taryfy:

Taryfadostępne poziomy podpisu
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, oba równolegle

Wariant równoległy jest świadomie nadmiarowy. FALCON stoi na kratach NTRU, ML-DSA na kratach modułowych. Gdyby jedna z obu rodzin okazała się słabsza, niż dziś się przyjmuje, druga niesie dowód dalej.

Kotwica czasu. Odcisk klucza podpisującego zostaje zakotwiczony przez OpenTimestamps w bloku Bitcoina. Dowodzi to nie tylko, że podpis jest prawdziwy, lecz także, że istniał już w określonym momencie — bez konieczności wiary komukolwiek w nasz znacznik czasu.

Wszystko to liczone jest w przeglądarce czytelnika, przez moduł WASM. My dostarczamy dane; weryfikacja przebiega na urządzeniu odwiedzającego. Gdybyśmy jutro zniknęli z sieci, raz załadowana opinia pozostałaby sprawdzalna.

Uwaga o nazwach: FALCON jest obecnie standaryzowany jako FN-DSA; projekt przewidziany jest jako FIPS 206, ale nie został jeszcze zamknięty. Dlatego poziomy w kodzie McGesund nazywają się FN-DSA-512 i FN-DSA-1024, nawet jeśli w mowie potocznej nadal mówi się o FALCON.

18. Najważniejsza intuicja

Klucz publiczny to pełny opis labiryntu. Każdy może go obejrzeć.

Podpis to dowód: „Znalazłem dla dokładnie tej opinii bardzo krótką drogę".

Klucz prywatny to znajomość skrótów.

Czytelnik nie musi znać skrótów. Sprawdza tylko, czy przedłożona droga rzeczywiście jest krótka i rzeczywiście należy do tej opinii. Jedno i drugie może zrobić bez nas.

FALCON zamienia opinię w punkt w kracie,a podpis w kroˊtką drogę do niego.\boxed{ \begin{array}{c} \text{FALCON zamienia opinię w punkt w kracie,}\\ \text{a podpis w krótką drogę do niego.} \end{array}}

Kto zmieni tekst, przesuwa punkt — a stara droga prowadzi w pustkę.