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

ML-DSA-87, обяснен математически

Как ML-DSA-87 (FIPS 204) подписва един отзив в McGesund — от Module-LWE през rejection sampling до проверката в браузъра.

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

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

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

За клиенти от тарифа Pro нагоре това става наред с останалото и с ML-DSA-87. Тази статия обяснява какво се случва при това математически.

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

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

ML-DSA е разработен от CRYSTALS-Dilithium и е стандартизиран като FIPS 204. Числото 87 обозначава нивото на параметрите. Има три:

  • ML-DSA-44
  • ML-DSA-65
  • ML-DSA-87

ML-DSA-87 е най-високото и попада в категория 5 за сигурност на NIST.

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

В подписа влиза не самият текст на отзива, а компактен обект от данни, който еднозначно приковава текста. При McGesund той изглежда в основата си така:

{
  "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)

Ако някой промени по-късно един-единствен знак в текста на отзива, h вече не пасва — а също и rh. Който вместо това само завърти сърцата, оставя h недокоснат, но разрушава rh. Промени ли някой една от тези хеш-стойности, подписът вече не пасва. Точно тази верига е същественото.

3. Какво трябва да постига подписът

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

  1. Отзивът действително е издаден от McGesund.
  2. Текстът не е променян от изпращането насам.
  3. Никой не може да измисли нов, изглеждащ валиден отзив.

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

  • частен ключ — намира се изключително в услугата за подписване
  • публичен ключ — може да е у всеки, адресира се чрез идентификатора на ключа (kid) в плика

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

4. Защо изобщо постквантов метод?

Много от днес обичайните схеми за подпис почиват на факторизацията на големи числа или на дискретни логаритми. Достатъчно мощен квантов компютър би могъл да решава именно тези задачи значително по-бързо с известни алгоритми.

За един отзив това не е академичен въпрос. Отзивът трябва да е проверим и след десет години. Който подписва днес, подписва за целия живот на записа.

Затова ML-DSA използва друга основа:

Решетъчни задачи\boxed{\text{Решетъчни задачи}}

По-точно: Module-LWE и Module-SIS.

5. Какво е решетка?

Най-напред просто точки в пространството. Да вземем два вектора:

b1=(2,0),b2=(1,2).b_1=(2,0), \qquad b_2=(1,2).

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

a b1+b b2,a,b∈Za\,b_1+b\,b_2, \qquad a,b\in\mathbb{Z}

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

2b1+b2=(4,0)+(1,2)=(5,2).2b_1+b_2 = (4,0)+(1,2) = (5,2).
b₁ = (2,0)b₂ = (1,2)(5,2)0
Два вектора и всички целочислени комбинации от тях: решетка. Отбелязаната точка възниква от два пъти b₁ и веднъж b₂.

Решаващото:

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

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

ML-DSA не смята с двумерни вектори, а с полиноми и вектори от полиноми.

Полином като

a(x)=1+2x+x3a(x)=1+2x+x^3

може да се запише като списък от коефициенти:

a=(1,2,0,1).a=(1,2,0,1).

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

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

Това означава две неща:

  • Zq\mathbb{Z}_q: смятане по модул qq
  • xn=−1x^n=-1: допълнително правило, което фиксира дължината на полинома

За всичките три нива на ML-DSA важи:

n=256,q=8380417.n=256, \qquad q=8380417.

Един полином има следователно 256 коефициента, разглеждани по модул 8 380 417. Онова, което се променя между нивата, не е nn или qq, а размерът на матриците — за това по-нататък.

Между другото: умножението на полиноми в този пръстен на практика минава през NTT, теоретико-числовия вариант на бързото преобразувание на Фурие. Тоест ML-DSA съвсем не минава без идеите на FFT; те просто стоят в аритметиката, а не в принципа на подписа.

7. Централният трик: Module-LWE

Основната идея е Module Learning With Errors:

t=As1+s2(modq).\mathbf{t}=\mathbf{A}\mathbf{s}_1+\mathbf{s}_2 \pmod q.

При това:

  • A\mathbf{A} — публична, привидно случайна матрица от полиноми
  • s1,s2\mathbf{s}_1,\mathbf{s}_2 — малки тайни вектори
  • t\mathbf{t} — публична стойност

Нападателят знае A\mathbf{A} и t\mathbf{t}, но не и s1,s2\mathbf{s}_1,\mathbf{s}_2. За него уравнението изглежда като случайно уравнение с шум. Малките тайни не бива да могат да се пресметнат обратно от него ефикасно.

8. Мъничък числов пример

Нарочно вземаме смехотворно малък вариант — обикновени числа вместо полиноми, размерност 2 вместо 256, и

q=17.q=17.

Нека

A=(3572),s1=(1−1),s2=(10).A=\begin{pmatrix}3&5\\7&2\end{pmatrix}, \qquad \mathbf{s}_1=\begin{pmatrix}1\\-1\end{pmatrix}, \qquad \mathbf{s}_2=\begin{pmatrix}1\\0\end{pmatrix}.

Тогава:

As1=(3−57−2)=(−25),A\mathbf{s}_1=\begin{pmatrix}3-5\\7-2\end{pmatrix}=\begin{pmatrix}-2\\5\end{pmatrix},
t=As1+s2=(−25)+(10)=(−15)  ≡  (165)(mod17).\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2=\begin{pmatrix}-2\\5\end{pmatrix}+\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}-1\\5\end{pmatrix} \;\equiv\; \boxed{\begin{pmatrix}16\\5\end{pmatrix}} \pmod{17}.

В този миниформат всички възможности биха могли да се изпробват. При ML-DSA-87 A\mathbf{A} е матрица 8×78\times 7 от полиноми с по 256 коефициента — това са над 14 000 неизвестни в решетъчната структура.

9. Двойката ключове на услугата за подписване

Частният ключ съдържа наред с останалото малките вектори s1,s2\mathbf{s}_1,\mathbf{s}_2. При ML-DSA-87 техните коефициенти произхождат от интервала

[−η,η]приη=2,[-\eta,\eta] \quad\text{при}\quad \eta=2,

тоест от {−2,−1,0,1,2}\{-2,-1,0,1,2\}. Тази малка големина не е подробност, а самата сърцевина: само защото тайните са малки, изобщо възниква трудна решетъчна задача.

Публичният ключ е опростено

(ρ,t1).(\rho,\mathbf{t}_1).

ρ\rho е seed, от който A\mathbf{A} може да се възстанови детерминирано — тоест матрицата не се налага да бъде предавана. t1\mathbf{t}_1 са горните битове на t\mathbf{t}; долните d=13d=13 бита отпадат, което смалява ключа значително. Точно това изпускане е по-късно причината за така наречените hints.

С това възниква желаната асиметрия:

публична проверка  ≠  тайно подписване\boxed{\text{публична проверка}\;\neq\;\text{тайно подписване}}

10. Отзивът се превръща в число

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

μ=H(m).\mu=H(m).

В нашия пример играчка вземаме изкуствен мини хеш. В истинската система μ\mu е с дължина 512 бита и обвързва допълнително публичния ключ — така подпис не може да бъде преиначен като валиден за друг ключ.

11. Commitment

Услугата за подписване тегли случаен малък вектор y\mathbf{y}. В нашия пример:

y=(2−1).\mathbf{y}=\begin{pmatrix}2\\-1\end{pmatrix}.

От него възниква междинна стойност — commitment:

w=Ay=(3⋅2+5⋅(−1)7⋅2+2⋅(−1))=(112).\mathbf{w}=A\mathbf{y} =\begin{pmatrix}3\cdot2+5\cdot(-1)\\7\cdot2+2\cdot(-1)\end{pmatrix} =\begin{pmatrix}1\\12\end{pmatrix}.

Това още не е подпис.

12. От отзива се получава предизвикателство

Съобщението и commitment се хешират заедно:

c=H(μ,w).c=H(\mu,\mathbf{w}).

При ML-DSA-87 cc е полином с точно τ=60\tau=60 коефициента от {−1,+1}\{-1,+1\}, а всички останали 196 са нула. Тази структура е нарочна: тя държи c⋅s1c\cdot\mathbf{s}_1 малко.

В нашия пример играчка просто задаваме

c=2.c=2.

13. Същинският подпис

z=y+c s1.\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1.

С нашите стойности:

c s1=2(1−1)=(2−2),c\,\mathbf{s}_1=2\begin{pmatrix}1\\-1\end{pmatrix}=\begin{pmatrix}2\\-2\end{pmatrix},
z=(2−1)+(2−2)=(4−3)\mathbf{z}=\begin{pmatrix}2\\-1\end{pmatrix}+\begin{pmatrix}2\\-2\end{pmatrix} =\boxed{\begin{pmatrix}4\\-3\end{pmatrix}}

14. Стъпката, която лесно се пропуска: rejection sampling

Тук е мястото, на което ML-DSA се различава от една наивна конструкция — и то не е по избор.

z=y+c s1\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1 съдържа тайната s1\mathbf{s}_1. Ако z\mathbf{z} просто се издаваше винаги, s1\mathbf{s}_1 би могло да се пресметне статистически от достатъчно много подписи. При портал за отзиви с много подписи на ден това не е теоретичен риск.

Затова услугата за подписване проверява преди издаването дали z\mathbf{z} издава твърде много и в противен случай отхвърля подписа — тогава се започва отначало с ново случайно y\mathbf{y}. Това се нарича Fiat-Shamir with Aborts.

Условието гласи по същество:

∥z∥∞<γ1−β.\|\mathbf{z}\|_\infty < \gamma_1-\beta.
Commitment w = AyПредизвикателство c = H(μ, w)Отговор z = y + c · s₁‖z‖∞ < γ₁ − β ?даподписът се издаване — ново y
Три стъпки и един цикъл. Излезе ли z твърде голямо, то не се доизглажда — целият пробег се отхвърля и се започва наново с прясно случайно y. Затова подписването тук е циклична процедура.

За ML-DSA-87 важи γ1=219\gamma_1=2^{19} и β=τ⋅η=60⋅2=120\beta=\tau\cdot\eta=60\cdot2=120. Към това идва втора граница върху долните битове. На практика няколко пробега са нормални — тоест подписването е циклична процедура, а не еднократна стъпка.

За верификацията е важно: точно тази граница браузърът проверява по-късно също. Подпис с твърде големи коефициенти се отхвърля дори когато уравнението излиза.

15. Защо браузърът може да провери това

Браузърът на читателя знае:

  • отзива и с това mm
  • публичния ключ (ρ,t1)(\rho,\mathbf{t}_1)
  • подписа (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h})

Той не знае s1\mathbf{s}_1. Връзката, която въпреки това го придвижва напред:

z=y+c s1⟹Az=Ay+c As1.\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1 \quad\Longrightarrow\quad A\mathbf{z}=A\mathbf{y}+c\,A\mathbf{s}_1.

И тъй като важи

t=As1+s2\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2

неизвестното As1A\mathbf{s}_1 може да се замести с публичната стойност:

Az−c t=Ay−c s2.A\mathbf{z}-c\,\mathbf{t}=A\mathbf{y}-c\,\mathbf{s}_2.

Това е централното уравнение — и то казва нещо важно: браузърът реконструира AyA\mathbf{y} не точно, а само с точност до малкия член c s2c\,\mathbf{s}_2.

16. Мини примерът докрай

Имахме:

A=(3572),t=(−15),c=2,z=(4−3).A=\begin{pmatrix}3&5\\7&2\end{pmatrix},\quad \mathbf{t}=\begin{pmatrix}-1\\5\end{pmatrix},\quad c=2,\quad \mathbf{z}=\begin{pmatrix}4\\-3\end{pmatrix}.

Да пресметнем:

Az=(12−1528−6)=(−322),c t=2(−15)=(−210),A\mathbf{z}=\begin{pmatrix}12-15\\28-6\end{pmatrix}=\begin{pmatrix}-3\\22\end{pmatrix}, \qquad c\,\mathbf{t}=2\begin{pmatrix}-1\\5\end{pmatrix}=\begin{pmatrix}-2\\10\end{pmatrix},
Az−c t=(−112).A\mathbf{z}-c\,\mathbf{t}=\begin{pmatrix}-1\\12\end{pmatrix}.

Първоначалният commitment беше

w=(112).\mathbf{w}=\begin{pmatrix}1\\12\end{pmatrix}.

Разликата възлиза на

(−112)−(112)=(−20)=−c s2.\begin{pmatrix}-1\\12\end{pmatrix}-\begin{pmatrix}1\\12\end{pmatrix} =\begin{pmatrix}-2\\0\end{pmatrix} =-c\,\mathbf{s}_2.

Тоест точно предсказаният малък член на грешката. Верификаторът получава не w\mathbf{w}, а нещо, което лежи близо до w\mathbf{w}.

Именно затова ML-DSA сравнява не самите стойности, а техните горни битове. И именно затова подписът съдържа допълнително вектор с hints h\mathbf{h}: той съобщава компактно на кои места закръглянето е прескочило граница заради малкия член на грешката. При ML-DSA-87 са позволени най-много ω=75\omega=75 такива указания. Те не издават тайната — само поправят закръглянето.

Накрая браузърът изчислява предизвикателството наново. Ако то съвпадне,

cново=c,c_{\text{ново}}=c,

и всички норми лежат в границите, подписът е валиден.

17. Какво се случва, ако някой промени отзива?

Да допуснем, че някой с достъп до базата данни — включително някой при нас — променя текста на отзива или някое от сърцата. Тогава се променя поне една от двете хеш-стойности в полезния товар (h при текста, rh при всяко поле от записа):

H(m)≠H(m′).H(m)\neq H(m').

С това се променя предизвикателството:

c≠c′.c\neq c'.

Наличният подпис обаче е бил създаден за старото предизвикателство. Браузърът пресмята и установява:

cново≠cподпис⟹Подписът е невалиденc_{\text{ново}}\neq c_{\text{подпис}} \quad\Longrightarrow\quad \boxed{\text{Подписът е невалиден}}

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

18. Защо никой не може да измисли подпис?

Нападателят знае A\mathbf{A} и t\mathbf{t}, но не и s1,s2\mathbf{s}_1,\mathbf{s}_2. За да построи валиден подпис, той би трябвало да намери тройка (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h}), която

  • удовлетворява уравнението за верификация и
  • спазва границите на нормата и
  • пасва на предизвикателството, което се получава от точно тези стойности.

По същество това опира до трудна решетъчна задача — конкретно до Module-SIS: да се намерят къси решения на хомогенно уравнение по модул qq. Условието за малка големина при това не е украса, а самата степен на трудност. Без него решението би било тривиално.

публични данни  →  трудна решетъчна задача\boxed{\text{публични данни}\;\rightarrow\;\text{трудна решетъчна задача}}

19. Защо „Module“?

Думата описва структурата между простите вектори и общите решетки. Вместо с отделни числа, ML-DSA работи с вектори от полиноми:

a=(a1(x),a2(x),…,ak(x)),\mathbf{a}=(a_1(x),a_2(x),\ldots,a_k(x)),

и с матрици от тях:

A=(a1,1(x)a1,2(x)⋯a2,1(x)a2,2(x)⋯⋮⋮⋱).\mathbf{A}= \begin{pmatrix} a_{1,1}(x)&a_{1,2}(x)&\cdots\\ a_{2,1}(x)&a_{2,2}(x)&\cdots\\ \vdots&\vdots&\ddots \end{pmatrix}.

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

20. Защо точно 87?

Трите нива се различават не по пръстена, а по размерностите:

ПараметърML-DSA-44ML-DSA-65ML-DSA-87
Размер на матрицата (k,ℓ)(k,\ell)4×44\times46×56\times58×78\times7
Обхват на тайната η\eta242
Тегло на предизвикателството τ\tau394960
Публичен ключ1312 B1952 B2592 B
Подпис2420 B3309 B4627 B
Категория на NIST235

Забележително: ML-DSA-87 не е просто „ML-DSA-65, само по-голям“. Обхватът на тайната η\eta се връща от 4 обратно на 2; сигурността тук идва от по-голямата матрица, а не от по-големи коефициенти. Става дума за самостоятелен, стандартизиран избор на параметри.

по-голяма математическа структура→по-голям запас по сигурност\boxed{\text{по-голяма математическа структура}\rightarrow\text{по-голям запас по сигурност}}

Цената: 4627 байта на подпис — на всеки печат, който се съхранява и при проверката се доставя до браузъра. Затова при McGesund наред с ML-DSA-87 е достъпен и FALCON, който се справя с 1280 байта.

21. Fiat-Shamir: защо работи без отсрещна страна

Едно интерактивно доказателство би протекло така:

  1. Услугата за подписване изпраща commitment.
  2. Проверяващият изпраща случайно предизвикателство.
  3. Услугата за подписване отговаря.
  4. Проверяващият пресмята.

При един отзив този диалог го няма — читателят идва месеци по-късно. Решението е трансформацията на Фиат-Шамир: предизвикателството не се хвърля на зарове, а се хешира от самите данни:

c=H(публичен ключ,  съобщение,  commitment).c=H(\text{публичен ключ},\;\text{съобщение},\;\text{commitment}).

Така от диалог се получава документ. Услугата за подписване не може да си избере предизвикателството, защото за целта би трябвало да контролира хеша.

22. Целият процес

УСЛУГА ЗА ПОДПИСВАНЕ (MCGESUND)БРАУЗЪР НА ПОСЕТИТЕЛЯчастен ключ s₁, s₂полезен товар m = {фирма, отзив, h, rh, iat}хеш μслучаен вектор yCommitment w = AyПредизвикателство c = H(μ, w)z = y + c · s₁подпис (c, z, hints) + kidотзив + подпис + публ. ключAz − c·t → горни битове + hintsново изчисляване на предизвикателствотоновоизчисленото предизвикателство = доставеното?валиденневалиденотхвърляне, ако z е твърде голямо(rejection sampling)
Целият път на един отзив. Прекъснатият обратен скок е rejection sampling — той се взема толкова пъти, докато z стане достатъчно малко, за да не издава нищо за тайния ключ.

23. Какво прави 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, и двата успоредно

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

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

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

24. ML-DSA и FALCON едно до друго

СвойствоFALCON (FN-DSA)ML-DSA
Типцифров подписцифров подпис
Решетъчно семействоNTRUModule-LWE / Module-SIS
ПръстенZq[x]/(xn+1)\mathbb{Z}_q[x]/(x^n+1), q=12289q=12289Zq[x]/(x256+1)\mathbb{Z}_q[x]/(x^{256}+1), q=8380417q=8380417
Основен механизъмкъс вектор чрез гаусово семплиранепредизвикателство и отговор с прекъсвания
FFT / NTTFFT с плаваща запетая, критична за сигурносттаNTT, само аритметика
Размер на подписа (най-високо ниво)1280 B4627 B
Реализациявзискателна (плаваща запетая)сравнително праволинейна
Стандартизацияпредвиден като FIPS 206 (FN-DSA), още незавършенFIPS 204, завършен

Накратко: ML-DSA е по-лесен за коректна реализация и проверка, FALCON доставя значително по-компактни подписи. В QR кода не стои нито един от двата — там стои единствено пликът Ed25519. Затова размерът на подписа тежи при съхранението и доставката, а устойчивостта — при реализацията. Затова предлагаме и двете.

25. Едно изречение за накрая

ML-DSA създава от кратък таен вектор отговор на еднопредизвикателство, хеширано от самия отзив — проверимот всеки с публичния ключ.\boxed{ \begin{array}{c} \text{ML-DSA създава от кратък таен вектор отговор на едно}\\ \text{предизвикателство, хеширано от самия отзив — проверим}\\ \text{от всеки с публичния ключ.} \end{array}}

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

За читателя на един отзив това означава простичко: той не трябва да ни вярва. Може да провери сам.