Parakstu algoritms

ML-DSA-87 matemātiski izskaidrots

Kā ML-DSA-87 (FIPS 204) paraksta McGesund atsauksmi — no Module-LWE pār Rejection Sampling līdz pārbaudei pārlūkprogrammā.

Stāvoklis: 2026-09-07

1. Par ko šeit ir runa

Kad kāds McGesund vietnē iesniedz atsauksmi, fonā notiek vairāk, nekā ļauj nojaust teksts. Nosūtīšanas brīdī atsauksme tiek digitāli parakstīta. Šo parakstu vēlāk ikviens apmeklētājs var pārrēķināt savā pārlūkprogrammā — bez uzticēšanās mums un bez jautāšanas mums.

Klientiem, sākot no tarifa Pro, tas cita starpā notiek ar ML-DSA-87. Šis raksts skaidro, kas tur matemātiski notiek.

Svarīgi jau iepriekš:

ML-DSA nav šifrēšana. Atsauksmes teksts paliek publiski lasāms — tāda taču ir atsauksmes jēga. ML-DSA pierāda nevis slepenību, bet gan izcelsmi un neskartību.

ML-DSA ir izstrādāts no CRYSTALS-Dilithium un ir standartizēts kā FIPS 204. Skaitlis 87 apzīmē parametru līmeni. To ir trīs:

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

ML-DSA-87 ir augstākais un atrodas NIST drošības kategorijā 5.

2. Kas tieši tiek parakstīts?

Parakstā nonāk nevis pats atsauksmes teksts, bet kompakts datu objekts, kas viennozīmīgi nostiprina tekstu. McGesund vietnē tas pēc būtības izskatās šādi:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<uzņēmuma ID>",
  "c":   "<atsauksmes ID>",
  "h":   "<atsauksmes teksta SHA-256>",
  "rh":  "<visa iesniegtā datu ieraksta SHA-256>",
  "rv":  1,
  "qh":  "<QR aploksnes SHA-256, tikai QR atsauksmēm>",
  "iat": 1757203200
}

Šis objekts ir mūsu ziņojums mm. Tas sasaista kopā sešus apgalvojumus:

  1. Kuram uzņēmumam atsauksme pieder (f)
  2. Kura atsauksme ir domāta (c)
  3. Kāds teksts aiz tās stāvēja — kā jaucējvērtība (h)
  4. Kāds datu ieraksts kopumā tika iesniegts (rh): teksts, sirdis, ģeostatuss un ziņas par apmeklējuma iemeslu, kanoniski serializēti un sajaukti — shēmas versijā rv
  5. No kura QR koda atsauksme nāk (qh); bez QR šis lauks atkrīt
  6. Kad tika parakstīts (iat)

Ja kāds vēlāk maina kaut vienu rakstzīmi atsauksmes tekstā, h vairs neatbilst — un rh arī ne. Kas turpretī pagroza tikai sirdis, tas h atstāj neskartu, bet salauž rh. Ja kāds maina vienu no šīm jaucējvērtībām, paraksts vairs neatbilst. Tieši šī ķēde ir būtība.

3. Ko parakstam ir jāpaveic

Apmeklētājam, kas atsauksmi lasa, ir jāspēj pašam pārbaudīt trīs lietas:

  1. Atsauksmi tiešām ir izsniedzis McGesund.
  2. Teksts kopš nosūtīšanas nav mainīts.
  3. Neviens nevar izdomāt jaunu atsauksmi, kas izskatītos derīga.

Tam kalpo atslēgu pāris:

  • privātā atslēga — atrodas vienīgi parakstīšanas dienestā
  • publiskā atslēga — to drīkst zināt ikviens, un tā tiek adresēta ar atslēgas ID (kid) aploksnē

Parakstīts tiek ar privāto atslēgu. Pārbaudīts — ar publisko, turklāt lasītāja pārlūkprogrammā, nevis uz mūsu servera.

4. Kāpēc vispār pēckvantu algoritms?

Daudzi šodien izplatītie parakstu algoritmi balstās uz lielu skaitļu faktorizāciju vai uz diskrētajiem logaritmiem. Pietiekami jaudīgs kvantu dators tieši šīs problēmas ar zināmiem algoritmiem varētu atrisināt ievērojami ātrāk.

Atsauksmei tas nav akadēmisks jautājums. Atsauksmei arī pēc desmit gadiem jābūt pārbaudāmai. Kas paraksta šodien, paraksta uz visu ieraksta dzīves laiku.

Tāpēc ML-DSA izmanto citu pamatu:

Rezˇg¸u probleˉmas\boxed{\text{Režģu problēmas}}

Precīzāk: Module-LWE un Module-SIS.

5. Kas ir režģis?

Sākumā tikai punkti telpā. Ņemsim divus vektorus:

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

Visas veselo skaitļu kombinācijas

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

veido režģi. Piemēram:

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
Divi vektori, visas veselo skaitļu kombinācijas no tiem: režģis. Atzīmētais punkts rodas no divkārša b₁ un vienkārša b₂.

Izšķirošais:

Mazās dimensijās režģu problēmas ir vieglas. Ļoti augstās dimensijās noteikti uzdevumi kļūst ārkārtīgi grūti.

6. Polinomi atsevišķu skaitļu vietā

ML-DSA rēķina nevis ar 2D vektoriem, bet ar polinomiem un polinomu vektoriem.

Polinomu, piemēram,

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

var pierakstīt kā koeficientu virkni:

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

Rēķināts tiek gredzenā:

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

Tas nozīmē divas lietas:

  • Zq\mathbb{Z}_q: rēķināšana pēc moduļa qq
  • xn=−1x^n=-1: papildu likums, kas nofiksē polinoma garumu

Visiem trim ML-DSA līmeņiem ir spēkā:

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

Polinomam tātad ir 256 koeficienti, aplūkoti pēc moduļa 8 380 417. Starp līmeņiem mainās nevis nn vai qq, bet matricu izmērs — par to vēlāk.

Starp citu: polinomu reizināšana šajā gredzenā praksē notiek caur NTT, ātrās Furjē transformācijas skaitļu teorijas variantu. ML-DSA tātad nebūt neiztiek bez FFT idejām; tās vienkārši slēpjas aritmētikā, nevis paraksta principā.

7. Galvenais triks: Module-LWE

Pamatideja ir Module Learning With Errors:

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

Tajā ir:

  • A\mathbf{A} — publiska, šķietami nejauša matrica no polinomiem
  • s1,s2\mathbf{s}_1,\mathbf{s}_2 — mazi slepenie vektori
  • t\mathbf{t} — publiskā vērtība

Uzbrucējs zina A\mathbf{A} un t\mathbf{t}, bet ne s1,s2\mathbf{s}_1,\mathbf{s}_2. Vienādojums viņam izskatās pēc nejauša vienādojuma ar troksni. Mazos noslēpumus viņam no tā nav jāspēj efektīvi atrēķināt atpakaļ.

8. Sīks skaitlisks piemērs

Mēs apzināti ņemam smieklīgi mazu variantu — parastus skaitļus polinomu vietā, 2. dimensiju 256. vietā, un

q=17.q=17.

Lai

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}.

Tad:

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}.

Šādā mini formātā varētu izmēģināt visas iespējas. ML-DSA-87 gadījumā A\mathbf{A} ir 8×78\times 7 matrica no polinomiem, katram ar 256 koeficientiem — tie ir vairāk nekā 14 000 nezināmo režģa struktūrā.

9. Parakstīšanas dienesta atslēgu pāris

Privātā atslēga cita starpā satur mazos vektorus s1,s2\mathbf{s}_1,\mathbf{s}_2. ML-DSA-87 gadījumā to koeficienti nāk no intervāla

[−η,η]arη=2,[-\eta,\eta] \quad\text{ar}\quad \eta=2,

tātad no kopas {−2,−1,0,1,2}\{-2,-1,0,1,2\}. Šis mazums nav sīkums, bet gan pati būtība: tikai tāpēc, ka noslēpumi ir mazi, vispār rodas grūta režģa problēma.

Publiskā atslēga vienkāršoti ir

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

ρ\rho ir sēkla, no kuras A\mathbf{A} var deterministiski rekonstruēt — matrica tātad nav jāpārraida. t1\mathbf{t}_1 ir t\mathbf{t} augstākie biti; apakšējie d=13d=13 biti tiek nomesti, kas atslēgu ievērojami samazina. Šis izlaidums vēlāk ir iemesls tā sauktajām norādēm (hints).

Tā rodas vēlamā asimetrija:

publiski paˉrbaudıˉt  ≠  slepeni parakstıˉt\boxed{\text{publiski pārbaudīt}\;\neq\;\text{slepeni parakstīt}}

10. Atsauksme kļūst par skaitli

Parakstīšanas dienests vispirms sajauc 2. sadaļas payload objektu:

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

Mūsu rotaļlietas piemērā mēs ņemam mākslīgu mini jaucējvērtību. Īstajā sistēmā μ\mu ir 512 bitu gara un papildus piesaista publisko atslēgu — tādējādi parakstu nevar attiecināt uz citu atslēgu.

11. Saistījums

Parakstīšanas dienests izlozē nejaušu mazu vektoru y\mathbf{y}. Mūsu piemērā:

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

No tā rodas starpvērtība — saistījums:

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}.

Tas vēl nav paraksts.

12. No atsauksmes rodas izaicinājums

Ziņojums un saistījums tiek sajaukti kopā:

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

ML-DSA-87 gadījumā cc ir polinoms ar tieši τ=60\tau=60 koeficientiem no kopas {−1,+1}\{-1,+1\}, visi pārējie 196 ir nulle. Šī struktūra ir apzināta: tā notur c⋅s1c\cdot\mathbf{s}_1 mazu.

Mūsu rotaļlietas piemērā mēs vienkārši pieņemam

c=2.c=2.

13. Pats paraksts

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

Ar mūsu vērtībām:

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. Solis, kuru viegli pārskatīt: Rejection Sampling

Šeit ir vieta, kurā ML-DSA atšķiras no naivas konstrukcijas — un tā nav izvēles iespēja.

z=y+c s1\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1 satur noslēpumu s1\mathbf{s}_1. Ja z\mathbf{z} vienkārši vienmēr izsniegtu, tad s1\mathbf{s}_1 no pietiekami daudziem parakstiem varētu statistiski atrēķināt. Atsauksmju portālam ar ļoti daudziem parakstiem dienā tas nav teorētisks risks.

Tāpēc parakstīšanas dienests pirms izsniegšanas pārbauda, vai z\mathbf{z} neizpauž par daudz, un pretējā gadījumā parakstu atmet — tad viss sākas no jauna ar jaunu nejaušu y\mathbf{y}. To sauc par Fiat-Shamir with Aborts.

Nosacījums pēc būtības ir šāds:

∥z∥∞<γ1−β.\|\mathbf{z}\|_\infty < \gamma_1-\beta.
saistījums w = Ayizaicinājums c = H(μ, w)atbilde z = y + c · s₁‖z‖∞ < γ₁ − β ?jāparaksts tiek izsniegtsnē — jauns y
Trīs soļi un cikls. Ja z izrādās pārāk liels, tas netiek pielabots — viss caurlaidiens tiek atmests un sākts no jauna ar svaigu nejaušu y. Tāpēc parakstīšana šeit ir cikliska procedūra.

ML-DSA-87 gadījumā ir spēkā γ1=219\gamma_1=2^{19} un β=τ⋅η=60⋅2=120\beta=\tau\cdot\eta=60\cdot2=120. Klāt nāk otra robeža apakšējiem bitiem. Praksē vairāki caurlaidieni ir normāli — parakstīšana tātad ir cikliska procedūra, nevis viens vienreizējs solis.

Verifikācijai svarīgi ir tas, ka tieši šo robežu pārlūkprogramma vēlāk pārbauda līdzi. Paraksts ar pārāk lieliem koeficientiem tiek noraidīts pat tad, ja vienādojums izpildās.

15. Kāpēc pārlūkprogramma to var pārbaudīt

Lasītāja pārlūkprogramma zina:

  • atsauksmi un līdz ar to mm
  • publisko atslēgu (ρ,t1)(\rho,\mathbf{t}_1)
  • parakstu (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h})

Tā nezina s1\mathbf{s}_1. Sakarība, kas tai tomēr palīdz tikt uz priekšu:

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.

Un tā kā ir spēkā

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

nezināmo As1A\mathbf{s}_1 var aizstāt ar publisko vērtību:

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

Tas ir centrālais vienādojums — un tas pasaka kaut ko svarīgu: pārlūkprogramma rekonstruē AyA\mathbf{y} nevis precīzi, bet tikai līdz mazajam loceklim c s2c\,\mathbf{s}_2.

16. Mini piemērs līdz galam

Mums bija:

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}.

Pārrēķinām:

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}.

Sākotnējais saistījums bija

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

Starpība ir

(−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.

Tātad tieši paredzētais mazais kļūdas loceklis. Verificētājs saņem nevis w\mathbf{w}, bet kaut ko, kas atrodas tuvu pie w\mathbf{w}.

Tieši tāpēc ML-DSA salīdzina nevis pašas vērtības, bet to augstākos bitus. Un tieši tāpēc paraksts papildus satur norāžu vektoru h\mathbf{h}: tas kompakti pavēsta, kurās vietās noapaļošana mazā kļūdas locekļa dēļ ir pārsviedusies pāri robežai. ML-DSA-87 gadījumā atļauts ir ne vairāk kā ω=75\omega=75 šādu norāžu. Tās neizpauž noslēpumu — tās tikai izlabo noapaļošanu.

Beigās pārlūkprogramma no jauna aprēķina izaicinājumu. Ja tas sakrīt,

cjaun=c,c_{\text{jaun}}=c,

un ja visas normas iekļaujas robežās, paraksts ir derīgs.

17. Kas notiek, ja kāds atsauksmi maina?

Pieņemsim, ka kāds ar piekļuvi datubāzei — arī kāds no mūsējiem — maina atsauksmes tekstu vai kādu no sirdīm. Tad mainās vismaz viena no abām jaucējvērtībām payload objektā (h teksta gadījumā, rh jebkura datu ieraksta lauka gadījumā):

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

Līdz ar to mainās izaicinājums:

c≠c′.c\neq c'.

Esošais paraksts tomēr ir radīts vecajam izaicinājumam. Pārlūkprogramma pārrēķina un konstatē:

cjaun≠cparaksts⟹Paraksts nederıˉgsc_{\text{jaun}}\neq c_{\text{paraksts}} \quad\Longrightarrow\quad \boxed{\text{Paraksts nederīgs}}

Izšķirošais teikums šeit: mēs varam atsauksmi izdzēst, bet nevaram to nemanāmi mainīt. McGesund vietnē tā pati pārbaude papildus katru nakti tiek veikta servera pusē pār visu kopumu — atsauksme, kas šo pārbaudi neiztur, vairs neieplūst uzņēmuma vidējā vērtējumā.

18. Kāpēc neviens nevar izdomāt parakstu?

Uzbrucējs zina A\mathbf{A} un t\mathbf{t}, bet ne s1,s2\mathbf{s}_1,\mathbf{s}_2. Lai uzbūvētu derīgu parakstu, viņam būtu jāatrod trijnieks (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h}), kas

  • apmierina verifikācijas vienādojumu un
  • ievēro normas robežas un
  • atbilst tam izaicinājumam, kas izriet tieši no šīm pašām vērtībām.

Tas pēc būtības noved pie grūtas režģa problēmas — konkrēti pie Module-SIS: atrast īsus risinājumus homogēnam vienādojumam pēc moduļa qq. Mazuma nosacījums šeit nav papildinājums, bet gan pati grūtības pakāpe. Bez tā risinājums būtu triviāls.

publiskie dati  →  gruˉta rezˇg¸a probleˉma\boxed{\text{publiskie dati}\;\rightarrow\;\text{grūta režģa problēma}}

19. Kāpēc „Module"?

Šis vārds apraksta struktūru starp vienkāršiem vektoriem un vispārīgiem režģiem. Tā vietā, lai rēķinātu ar atsevišķiem skaitļiem, ML-DSA strādā ar polinomu vektoriem:

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

un ar matricām no tiem:

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}.

Priekšrocība: tiek iegūta režģa augstā dimensija, taču saglabāts kompakts, efektīvi rēķināms attēlojums. Drošību var smalki noregulēt ar matricas izmēru, nemainot gredzenu.

20. Kāpēc tieši 87?

Trīs līmeņi atšķiras nevis gredzenā, bet dimensijās:

ParametrsML-DSA-44ML-DSA-65ML-DSA-87
Matricas izmērs (k,ℓ)(k,\ell)4×44\times46×56\times58×78\times7
Noslēpuma diapazons η\eta242
Izaicinājuma svars τ\tau394960
Publiskā atslēga1312 B1952 B2592 B
Paraksts2420 B3309 B4627 B
NIST kategorija235

Ievērības vērts: ML-DSA-87 nav vienkārši „ML-DSA-65, tikai lielāks". Noslēpuma diapazons η\eta no 4 atgriežas atpakaļ uz 2; drošība šeit nāk no lielākas matricas, nevis no lielākiem koeficientiem. Tā ir patstāvīga, standartizēta parametru izvēle.

lielaˉka matemaˉtiskaˉ struktuˉra→lielaˉka drosˇıˉbas rezerve\boxed{\text{lielāka matemātiskā struktūra}\rightarrow\text{lielāka drošības rezerve}}

Cena: 4627 baiti uz vienu parakstu — uz vienu zīmogu, kas tiek glabāts un pārbaudes brīdī nogādāts pārlūkprogrammai. Tāpēc McGesund vietnē blakus ML-DSA-87 ir pieejams arī FALCON, kam pietiek ar 1280 baitiem.

21. Fiat-Shamir: kāpēc tas darbojas bez sarunu partnera

Interaktīvs pierādījums noritētu šādi:

  1. Parakstīšanas dienests nosūta saistījumu.
  2. Pārbaudītājs nosūta nejaušu izaicinājumu.
  3. Parakstīšanas dienests atbild.
  4. Pārbaudītājs pārrēķina.

Atsauksmes gadījumā šāda dialoga nav — lasītājs ierodas mēnešus vēlāk. Risinājums ir Fiat-Shamir transformācija: izaicinājums netiek izmests ar kauliņu, bet sajaukts no pašiem datiem:

c=H(publiskaˉ atsleˉga,  zin¸ojums,  saistıˉjums).c=H(\text{publiskā atslēga},\;\text{ziņojums},\;\text{saistījums}).

Tādējādi no dialoga rodas dokuments. Parakstīšanas dienests izaicinājumu nevar izvēlēties, jo tam vajadzētu kontrolēt jaucējvērtību.

22. Visa norise

PARAKSTĪŠANAS DIENESTS (MCGESUND)APMEKLĒTĀJA PĀRLŪKPROGRAMMAprivātā atslēga s₁, s₂Payload m = {uzņēmums, atsauksme, h, rh, iat}jaucējvērtība μnejaušs vektors ysaistījums w = Ayizaicinājums c = H(μ, w)z = y + c · s₁paraksts (c, z, norādes) + kidatsauksme + paraksts + publ. atslēgaAz − c·t → augstākie biti + norādesizaicinājumu aprēķināt no jaunano jauna aprēķinātais izaicinājums = līdzi sūtītais?derīgsnederīgsatmest, ja z ir pārāk liels(Rejection Sampling)
Viss atsauksmes ceļš. Punktētais atpakaļlēciens ir Rejection Sampling — tas tiek izmantots tik reižu, līdz z ir pietiekami mazs, lai neko neizpaustu par slepeno atslēgu.

23. Ko McGesund ar to konkrēti dara

Trīs līmeņi darbojas kopā:

Aploksne. Katra parakstītā atsauksme nes Ed25519 parakstu. Tas ir obligātais variants — klasisks, sīks, katrā pārlūkprogrammā natīvi pārbaudāms.

Pēckvantu zīmogi. Papildus blakus var tikt novietoti viens vai divi kvantu izturīgi paraksti. Kuri — atkarīgs no tarifa:

Tarifspieejamie parakstu līmeņi
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, abi paralēli

Paralēlais variants ir apzināti dublējošs. Ja viena no abām matemātiskajām saimēm — NTRU režģi FALCON gadījumā, moduļu režģi ML-DSA gadījumā — izrādītos vājāka, nekā šodien pieņemts, otra turpina nest.

Laika enkurs. Parakstīšanas atslēgas nospiedums caur OpenTimestamps tiek noenkurots Bitcoin blokā. Tādējādi var pierādīt ne tikai to, ka paraksts ir īsts, bet arī to, ka tas noteiktā brīdī jau eksistēja — un nevienam nav jātic mūsu laika zīmogam.

Viss šis tiek pārbaudīts lasītāja pārlūkprogrammā, caur WASM moduli. Mēs piegādājam datus; pārrēķināts tiek apmeklētāja ierīcē. Ja mēs rīt pazustu no tīkla, vienreiz lejupielādēta atsauksme paliktu pārbaudāma.

24. ML-DSA un FALCON blakus

ĪpašībaFALCON (FN-DSA)ML-DSA
Veidsciparparakstsciparparaksts
Režģu saimeNTRUModule-LWE / Module-SIS
GredzensZq[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
Pamatmehānismsīss vektors ar Gausa izlasiizaicinājums-atbilde ar pārtraukumiem
FFT / NTTpeldošā komata FFT, drošībai kritiskaNTT, tikai aritmētika
Paraksta izmērs (augstākais līmenis)1280 B4627 B
Implementācijaprasīga (peldošais komats)salīdzinoši tiešāka
Standartizācijaparedzēta kā FIPS 206 (FN-DSA), vēl nav pabeigtaFIPS 204, pabeigta

Īsi sakot: ML-DSA ir vieglāk pareizi implementēt un pārbaudīt, FALCON dod ievērojami kompaktākus parakstus. QR kodā neatrodas neviens no abiem — tur ir vienīgi Ed25519 aploksne. Paraksta izmērs tāpēc svarīgs ir glabāšanā un piegādē, bet robustums — implementācijā. Tāpēc mēs piedāvājam abus.

25. Viens teikums līdzņemšanai

ML-DSA no ıˉsa slepena vektora rada atbildi uz izaicinaˉjumu,kas sajaukts no pasˇas atsauksmes — paˉrbaudaˉmu ikvienam,kam ir publiskaˉ atsleˉga.\boxed{ \begin{array}{c} \text{ML-DSA no īsa slepena vektora rada atbildi uz izaicinājumu,}\\ \text{kas sajaukts no pašas atsauksmes — pārbaudāmu ikvienam,}\\ \text{kam ir publiskā atslēga.} \end{array}}

Kam pieder slepenais vektors, tas paraksta milisekundēs. Kam tā nav, tam būtu jāatrisina režģa problēma vairāk nekā 14 000 dimensijās — arī ar kvantu datoru.

Atsauksmes lasītājam tas vienkārši nozīmē: viņam mums nav jātic. Viņš var pārrēķināt.