Схеми за подпис

FALCON, обяснен математически

Как един отзив в McGesund се подписва с FN-DSA (FALCON) — и защо един променен знак разрушава подписа.

Актуално към: 2026-09-07

1. За какво става дума

Отзивът в McGesund не е текстово поле в база данни, на което човек трябва просто да вярва. При изпращането той се подписва цифрово и всеки посетител може по-късно да преизчисли този подпис в собствения си браузър.

За част от тези подписи използваме FALCON — по-точно FN-DSA-512 и FN-DSA-1024. Тази статия обяснява какво се случва при това математически.

Важно предварително:

FALCON не е криптиране. Текстът на отзива трябва да може да се чете. FALCON не доказва поверителност, а произход и цялост.

2. Какво точно се подписва

Подписва се не свободният текст, а компактен обект от данни, който еднозначно приковава текста:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID на фирмата>",
  "c":   "<ID на отзива>",
  "h":   "<SHA-256 на текста на отзива>",
  "rh":  "<SHA-256 на целия запис от подаването>",
  "rv":  1,
  "qh":  "<SHA-256 на QR плика, само при QR отзиви>",
  "iat": 1757203200
}

Това е нашето съобщение mm. То свързва:

  1. към кое предприятие принадлежи отзивът (f),
  2. за кой отзив става дума (c),
  3. какъв текст е стоял зад него — като хеш-стойност (h),
  4. какъв запис е бил подаден като цяло (rh): текст, сърца, гео статус и данни за повода, канонично сериализирани и хеширани, във версия на схемата rv,
  5. от кой QR код произхожда отзивът (qh) — при отзив без QR полето отпада,
  6. кога е подписано (iat).

Един променен знак в текста на отзива разкъсва тази верига. Точно това е целта — а откакто съществува rh, същото важи и за допълнително преместено сърце или променен гео статус.

3. Основният проблем

Читателят, който попада на профил на предприятие, стои пред два въпроса:

  1. Наистина ли този отзив произхожда от системата на McGesund?
  2. Променян ли е след това?

За целта има двойка ключове:

  • частен ключ — остава в услугата за подписване
  • публичен ключ — може да е у всеки

Подписва се с частния, проверява се с публичния ключ. И то на устройството на читателя, а не на нашия сървър.

4. Защо FALCON?

Много от днешните схеми за подпис почиват на задачи, които за класическите изчислителни машини са трудни, но за достатъчно големи квантови компютри биха могли да станат значително по-лесни.

При един отзив това е по-съществено, отколкото при мимолетно съобщение: отзивът трябва да е проверим и след пет или десет години. Който подписва днес, подписва за целия живот на записа.

Затова FALCON почива на решетъчна криптография:

Изгражда се математически лесно описуема решетка, в която определена задача за търсене е изключително трудна.

5. Какво е математическа решетка?

Два вектора:

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

Всички целочислени комбинации

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

образуват решетка от точки. Например:

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
Два вектора опъват решетка. Всяка точка е целочислена комбинация на двата — отбелязаната възниква от два пъти v₁ и три пъти v₂.

Решаващото е:

Самата решетка се описва лесно. Намирането на определени свойства в нея е много трудно.

6. Тайната са късите вектори

Класическата трудна задача гласи:

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

Това е Shortest Vector Problem — задачата за най-късия вектор. В две измерения тя може да се изпробва. FALCON работи в размерност 512 или 1024 — там това е безнадеждно.

дълга базапочти успореднинай-къс вектор
Същата решетка, две описания. Сивите вектори също я пораждат, но са дълги и почти успоредни — лоша база. Късият вектор е онова, което е трудно за намиране.

FALCON обаче не се нуждае от най-късия вектор изобщо, а от нещо сродно: към предварително зададена целева точка да се намери близка точка от решетката. И това без правилната допълнителна информация е трудно.

целева точка от отзиваблизка точка от решеткатадалеч
Целевата точка от отзива (празно кръгче) не лежи в решетката. Търси се точка от решетката плътно до нея — прекъснатият път до далечна точка също е решение на първото условие, но именно не е къс.

7. Полиноми вместо числа

FALCON използва решетка NTRU и смята с полиноми. Тоест вместо с отделни числа — със списъци от коефициенти:

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.

Смята се в пръстена

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

Това означава:

  • Zq\mathbb{Z}_q: смятане по модул qq. При q=7q=7 например 10≡310\equiv3, тъй като 10−7=310-7=3.
  • xn=−1x^n=-1: държи полиномите с фиксирана дължина.

FALCON използва конкретно:

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

8. Централният трик

Частният ключ се състои от четири малки полинома

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

с уравнението NTRU

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

Тези четири образуват заедно тайна, добронамерена база на решетката — описание на решетката чрез къси вектори.

Публичният ключ е по същество един-единствен полином:

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

От hh се получава същата решетка, но в неудобна база от дълги вектори:

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

Това е цялото ядро на FALCON. Двете бази описват една и съща решетка. Само че едната е годна за смятане, а другата — не.

Може да се мисли като за план на град: публична е пълната карта. Тайно е познаването на преките пътища.

9. Отзивът се превръща в точка

Преди да се подпише, обектът на полезния товар минава през хеш-функция. FALCON използва за целта Hash-to-Point: от съобщението не се получава числова стойност, а направо точка в пръстена.

Допълнително услугата за подписване тегли случайна сол rr (320 бита) и я хешира заедно с него:

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

Солта не е украса. Без нея един и същ отзив би давал винаги един и същ подпис и от много подписи тайната база би могла да бъде възстановена. Затова тя пътува заедно с подписа.

10. Какво представлява валидният подпис

Търси се двойка

(s1,s2)(s_1,s_2)

с две свойства:

s1+s2 h≡c(modq)и∥(s1,s2)∥  малка.s_1+s_2\,h\equiv c \pmod q \qquad\text{и}\qquad \|(s_1,s_2)\|\;\text{малка}.

Първото условие само по себе си е тривиално за изпълнение — задава се s2=0s_2=0 и s1=cs_1=c. Второто условие прави задачата трудна.

Късостта е подписът.\boxed{\text{Късостта е подписът.}}

11. Напълно пресметнат мини пример

Свиваме всичко до размер на играчка: полиноми само с един коефициент, тоест обикновени числа, и

q=97.q=97.

Тайният ключ. Две малки числа:

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

Публичният ключ. В сила е 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, тъй като 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Тоест:

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

Решетката. L={(s1,s2):s1+34 s2≡0(mod97)}L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}.

Публичната база се получава направо от hh:

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

И двата лежат в LL — и двата са дълги.

Тайната база я знае само услугата за подписване:

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

тъй като −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 и −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. Детерминантата е

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

тоест уравнението NTRU излиза. И двата вектора са къси.

Стъпка 1: Хеширане на отзива

Да приемем, че обектът на полезния товар на отзива дава

c=71.c=71.

Стъпка 2: Първо, лошо решение

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

изпълнява 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Но дължината е 7171 — много прекалено дълга.

Стъпка 3: Скъсяване с тайната база

Услугата за подписване изразява целевата точка в своята къса база:

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

Това води до a≈−10,25a\approx-10{,}25 и b≈−2,20b\approx-2{,}20. Закръглено до a=−10a=-10, b=−2b=-2 се получава точката от решетката

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

Проверка: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, тоест наистина в LL. Изваждане:

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

Дължина:

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

Това е подписът.

Стъпка 4: Същият метод с публичната база

Който знае само h=34h=34, разполага с базата {(97,0),(−34,1)}\{(97,0),(-34,1)\}. Същата сметка със закръгляне дава там точката от решетката (97,0)(97,0) и оттам

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

Също валидно решение на уравнението — но седем пъти по-дълго. Ако границата на приемане се постави под 26, то е безполезно.

Същият алгоритъм, същата решетка, същата целева точка.Различава се само базата — а с нея и резултатът.\boxed{ \begin{array}{c} \text{Същият алгоритъм, същата решетка, същата целева точка.}\\ \text{Различава се само базата — а с нея и резултатът.} \end{array}}

Това е капанът на FALCON в един ред.

Стъпка 5: Браузърът проверява

Браузърът получава отзива, солта и s2=2s_2=2. Той изчислява хеша наново, получава c=71c=71, реконструира

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

и проверява дължината:

∥(3,2)∥=13  ≤  β⟹Подписът е валиден\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Подписът е валиден}}

Стъпка 6: Някой променя текста на отзива

Ако текстът бъде променен допълнително, се променя хешът на съдържанието, а с него и точката, да кажем

c′=40.c'=40.

Старият подпис остава (3,2)(3,2), но

3+34⋅2=71≠40⟹Подписът е невалиден3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Подписът е невалиден}}

Можем да изтрием отзив. Не можем да го променим, без това да се забележи.

Бележка за честност към примера

В две измерения нападателят може просто да изпробва къси решения — за c′=40c'=40 например (6,1)(6,1). Примерът не е сигурен; той показва само механизма. При FALCON-1024 векторът има 2048 коефициента и там изпробването не води доникъде.

12. Защо не се закръгля просто?

Методът от стъпка 3 се нарича закръгляне на Бабай. За учебен пример стига — за истинска схема за подпис не.

Причината: закръглените подписи не лежат равномерно разпределени. Формата им зависи от геометрията на тайната база. От достатъчно много подписи тази геометрия би могла да бъде възстановена — а с нея и частният ключ. Точно на това са се провалили по-ранни решетъчни схеми за подпис.

Затова FALCON тегли късите вектори от дискретно гаусово разпределение върху решетката:

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

Стойностите близо до целевата точка са по-вероятни, но коя точно ще бъде избрана, е случайно. Резултатът е разпределение, което не издава нищо за използваната база — математически: то е неразличимо от разпределение, което зависи само от самата решетка.

Този семплер е най-взискателната част на FALCON. Той работи рекурсивно върху дървовидна структура и борави с числа с плаваща запетая — което прави реализацията деликатна и е главната причина FALCON да е по-труден за коректно прилагане от ML-DSA.

13. Какво всъщност се предава

Подписът се състои от

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

Само s2s_2 — не двойката. s1s_1 проверяващият изчислява сам:

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

Тъй като коефициентите на s2s_2 са малки и се разпръскват около нулата, те се компресират силно. Това е причината за подчертано компактните подписи на FALCON:

публичен ключподпис
FALCON-512897 B~666 B
FALCON-10241793 B~1280 B

За сравнение: ML-DSA-87 се нуждае от 4627 байта. При McGesund обаче нито един от тези подписи не стои в самия QR код — стикерът носи само плика Ed25519; постквантовите печати лежат при записа и се дозареждат при проверката. Тук размерът следователно не решава въпроса с отпечатването, а този за съхранението и преноса: печатът FALCON е около една четвърт от размера на печата ML-DSA.

14. Защо FALCON проверява бързо

Наивното умножение на полиноми струва

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

С бързото преобразувание на Фурие това пада до приблизително

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

При n=1024n=1024 това е разликата между един милион и около десет хиляди операции. Затова проверката в браузъра на посетителя минава за милисекунди — и затова в името стои F:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. Процесът в картина

УСЛУГА ЗА ПОДПИСВАНЕ (MCGESUND)БРАУЗЪР НА ПОСЕТИТЕЛЯчастен ключ (f, g, F, G — къса база)полезен товар m = {фирма, отзив, h, rh, iat}сол r + HashToPoint(r ‖ m) = cгаусово семплиране: къс вектор (s₁, s₂)подпис σ = (r, s₂) + kidотзив + σ + публичен ключ hново изчисляване на c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?валиденневалиден
От полезния товар до отметката в браузъра. Всичко над разделителната линия се случва еднократно при изпращането, всичко под нея — наново при всеки посетител, на неговото устройство, с публичния ключ.

16. Защо нападателят се проваля

Той знае hh и с това цялата решетка. Знае и целевата точка cc, щом отзивът е публичен. Липсва му късата база.

За да фалшифицира отзив, той би трябвало към самостоятелно избрано cc да намери къс вектор — само от публичното описание. Това е задачата, която стъпка 4 от примера илюстрира: без добрите вектори същата сметка стига до много прекалено дълго решение.

В размерност 1024 най-добрите известни методи — както класически, така и квантови — са далеч от това.

Подписване: бързоПроверка: бързаФалшифициране: трудно\boxed{\text{Подписване: бързо}\quad \text{Проверка: бърза}\quad \text{Фалшифициране: трудно}}

17. Какво прави McGesund конкретно с това

Пликът. Всеки подписан отзив носи подпис Ed25519. Това е задължителният вариант — класически, съвсем малък, проверим нативно във всеки браузър.

Постквантовите печати. До него лежат един или два квантово устойчиви подписа. Кои — зависи от тарифата:

Тарифаналични нива на подпис
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, и двата успоредно

Успоредният вариант е съзнателно резервиран. FALCON стои върху решетки NTRU, ML-DSA — върху модулни решетки. Ако едно от двете семейства се окаже по-слабо от предполаганото днес, другото продължава да носи.

Времевата котва. Отпечатъкът на ключа за подписване се закотвя чрез OpenTimestamps в блок на Bitcoin. С това е доказано не само че подписът е истински, а и че той вече е съществувал в определен момент — без някой да трябва да вярва на нашия времеви печат.

Всичко това се смята в браузъра на читателя, чрез модул WASM. Ние доставяме данните; проверката върви на устройството на посетителя. Ако утре излезем от мрежата, веднъж зареден отзив би останал проверим.

За подредбата на имената: FALCON понастоящем се стандартизира като FN-DSA; проектът е предвиден като FIPS 206, но още не е завършен. Затова нивата в кода на McGesund се наричат FN-DSA-512 и FN-DSA-1024, макар в разговорната употреба все още да се говори за FALCON.

18. Най-важната интуиция

Публичният ключ е пълното описание на един лабиринт. Всеки има право да го разгледа.

Подписът е доказателството: „Намерих за точно този отзив много кратък път.“

Частният ключ е познаването на преките пътища.

Читателят не е нужно да познава преките пътища. Той само премерва дали представеният път наистина е къс и наистина принадлежи на този отзив. И двете може да направи без нас.

FALCON превръща отзива в точка в решетка,а подписа — в кратък път до нея.\boxed{ \begin{array}{c} \text{FALCON превръща отзива в точка в решетка,}\\ \text{а подписа — в кратък път до нея.} \end{array}}

Който промени текста, размества точката — и старият път води в празното.