Parakstu algoritms

Ed25519 matemātiski izskaidrots

Paraksts, kas piesaistīts katrai McGesund atsauksmei — no līknes un atslēgas līdz vienādojumam, ko pārrēķina lasītāja pārlūkprogramma.

Stāvoklis: 2026-09-07

1. Par ko šeit ir runa

Atsauksme McGesund vietnē nav vienkārši teksta lauks datubāzē, kuram jātic uz vārda. Nosūtīšanas brīdī tā tiek digitāli parakstīta, un vēlāk ikviens apmeklētājs var šo parakstu pārrēķināt savā pārlūkprogrammā.

Šim parakstam mēs izmantojam Ed25519. Atšķirībā no FALCON un ML-DSA, kurus papildus var novietot blakus kā zīmogu, Ed25519 nav izvēles iespēja: katra parakstītā atsauksme to nes neatkarīgi no tarifa un iesniegšanas veida.

Svarīgi jau iepriekš:

Ed25519 nav šifrēšana. Atsauksmes tekstam taču ir jābūt lasāmam. Paraksts pierāda nevis slepenību, bet gan izcelsmi un neskartību.

2. Kas tieši tiek parakstīts

Parakstīts tiek nevis pats teksts, bet kompakts datu objekts, kas viennozīmīgi nostiprina gan tekstu, gan visu pārējo:

{
  "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>",
  "kid": "<atslēgas ID>",
  "iat": 1757203200
}

Šis objekts tiek kodēts CBOR formātā. Tieši šī baitu virkne — nevis tās glītais attēlojums iepriekš — ir mūsu ziņojums mm. Paraksts un ziņojums kopā nonāk aploksnē:

Aploksne=MCG1:  ∥  base64url(CBOR[ 3,  m,  σ ])\text{Aploksne} = \texttt{MCG1:} \;\|\; \mathrm{base64url}\bigl(\mathrm{CBOR}[\,3,\; m,\; \sigma\,]\bigr)

Skaitlis 33 ir formāta versija. Vairāk tur nekā nav — jo īpaši nav pēckvantu paraksta: tas, ja tāds ir, atrodas blakus datu ierakstam, nevis aploksnē.

3. Ko parakstam ir jāpaveic

Lasītājs, kas nonāk uzņēmuma profilā, saskaras ar diviem jautājumiem:

  1. Vai šī atsauksme tiešām nāk no McGesund sistēmas?
  2. Vai tā vēlāk ir mainīta?

Tam kalpo atslēgu pāris:

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

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. Tas ir būtiskākais: pārbaude, ko veiktu mēs paši un kuras rezultātu pēc tam paziņotu, nebūtu pārbaude, bet apgalvojums.

4. Kāpēc eliptiskā līkne?

Katram parakstam ir vajadzīgs aprēķins, kas vienā virzienā ir viegls un otrā praktiski neiespējams. Ed25519 gadījumā tā ir skalārā reizināšana uz eliptiskās līknes:

a  ⟼  A=a⋅B.a \;\longmapsto\; A = a\cdot B.

Aprēķināt publisko punktu AA no slepenā skaitļa aa prasa mikrosekundes. Secināt no AA atpakaļ uz aa nozīmē risināt diskrētā logaritma problēmu — tai nav zināma neviena metode, kas šādā izmērā tiktu galā cilvēkam aptveramā laikā.

Praktiskais ieguvums salīdzinājumā ar vecākiem algoritmiem, piemēram, RSA, ir izmērs:

publiskā atslēgaparaksts
RSA-3072384 B384 B
Ed2551932 B64 B

Un tas pie salīdzināma drošības līmeņa. 64 baiti uz vienu atsauksmi arī miljonu atsauksmju gadījumā nav lielums, par kuru būtu jādomā.

5. Līkne edwards25519

Rēķināts tiek pēc moduļa, kas ir pirmskaitlis:

p=2255−19.p = 2^{255}-19.

No tā arī nosaukums. Līkne ir savērpta Edvardsa līkne:

−x2+y2  =  1+d x2y2,d=−121665121666 mod p.-x^2+y^2 \;=\; 1 + d\,x^2y^2, \qquad d = -\frac{121665}{121666} \bmod p.

„Punkts" ir skaitļu pāris (x,y)(x,y) no kopas {0,…,p−1}\{0,\dots,p-1\}, kas apmierina šo vienādojumu. Nekādas līknes tur nav ko redzēt — zīmējums nākamajā sadaļā ir uzskates palīglīdzeklis reālo skaitļu apgabalā, nevis faktiskās rēķinu telpas attēls.

Klāt nāk vēl divi lielumi:

  • fiksēti norunāts bāzes punkts BB,
  • BB ģenerētās apakšgrupas kārta ℓ\ell:
ℓ=2252+27742317777372353535851937790883648493.\ell = 2^{252} + 27742317777372353535851937790883648493.

ℓ\ell ir pirmskaitlis. Tas nozīmē: ja BB atkal un atkal saskaita pašu ar sevi, tiek izieti tieši ℓ\ell dažādi punkti, un tad viss sākas no gala. Tāpēc visi aprēķini ar skalāriem notiek pēc moduļa ℓ\ell, bet visi aprēķini ar koordinātām — pēc moduļa pp. Šo abu skaitļu sajaukšana ir klasiskā iesācēju kļūda.

6. Punktu saskaitīšana

Divi punkti pēc fiksētas formulas tiek pārrēķināti trešajā:

x3=x1y2+y1x21+d x1x2y1y2,y3=y1y2−x1x21−d x1x2y1y2.x_3=\frac{x_1y_2+y_1x_2}{1+d\,x_1x_2y_1y_2}, \qquad y_3=\frac{y_1y_2-x_1x_2}{1-d\,x_1x_2y_1y_2}.

Neitrālais elements ir (0,1)(0,1) — punkts, kurā rēķināšana sākas.

Šai formulai ir īpašība, kas pēc izskata nav nolasāma un kas drošībai ir svarīgāka par jebkuru konstanti: tā ir pilnīga. Tā darbojas visām ievaddatu vērtībām, bez īpašiem gadījumiem „abi punkti sakrīt" vai „rezultāts ir neitrālais elements". Vecākajām Veierštrāsa līknēm šādi īpašie gadījumi pastāv, un katrs no tiem programmā ir atsevišķs zars — zars, kura izpildes laiku var izmērīt. Kas mēra, cik ilgi aizņem paraksta izveide, tāda veida algoritmos uzzina kaut ko par slepeno atslēgu.

Pilnīgas formulas nozīmē: vienmēr viens un tas pats rēķinu ceļš, vienmēr viens un tas pats laiks, nekā mērāma.

7. Skalārā reizināšana — vienvirziena iela

n⋅Bn\cdot B nozīmē: saskaitīt BB ar sevi tieši nn reižu. Ja nn ir 253 bitu garš, tas būtu bezjēdzīgi daudz darba — tāpēc tiek dubultots:

B→2B→4B→8B→…B \to 2B \to 4B \to 8B \to \dots

un no šiem starprezultātiem tiek salikts vajadzīgais nn. Aptuveni 253 dubultojumi pietiek jebkuram nn. Tas ir ceļš uz priekšu.

Atpakaļvirzienā šāda īsceļa nav. Noteikt skaitli aa no punkta AA nozīmē atrisināt diskrētā logaritma problēmu.

(0,1) — neitrālais elementsB2B3B4B5B6B
Edvardsa līkne ar bāzes punkta pirmajiem daudzkārtņiem, aprēķinātiem pēc īstā saskaitīšanas likuma. Reālo skaitļu apgabalā tie pa līkni pārvietojas vēl redzami sakārtoti — ceļu varētu izsekot atpakaļ. Pēc moduļa p tieši šī kārtība pazūd, un uz tā balstās drošība.

Īstajā algoritmā tiek rēķināts pēc moduļa pp. Tur nav ne „pa kreisi", ne „pa labi", nedz arī tuvuma: no 17 B17\,B un 18 B18\,B rodas divi skaitļu pāri bez jebkādas saskatāmas radniecības.

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

Sākumā ir 32 nejauši baiti — sēkla. Viss pārējais tiek atvasināts no tās:

h=SHA-512(seˉkla),h=h0..31⏟→  a  ∥  h32..63⏟prefikss.h = \mathrm{SHA\text{-}512}(\text{sēkla}), \qquad h = \underbrace{h_{0..31}}_{\to\;a}\;\|\;\underbrace{h_{32..63}}_{\text{prefikss}}.

No pirmās puses rodas slepenais skalārs aa, tomēr ne nemainītā veidā. Trīs biti tiek iestatīti vai attiecīgi dzēsti — tā sauktais clamping:

  • trīs zemākie biti tiek iestatīti uz nulli: līdz ar to aa kļūst par 8 daudzkārtni. Iemesls ir līknes kofaktors 8 — pilnā punktu grupa ir astoņreiz lielāka nekā apakšgrupa ar kārtu ℓ\ell. Ar 8 dalāms aa garantēti nonāk pareizajā apakšgrupā un neko neizpauž par maza kārtas punktiem.
  • augstākais bits tiek dzēsts, otrs augstākais iestatīts: tādējādi aa vienmēr ir vienāda bitu garuma. Īsākam aa vajadzētu mazāk dubultojumu — un atkal izpildes laiks kaut ko atklātu.

Publiskā atslēga tad ir vienkārši

A=a⋅B,A = a\cdot B,

saglabāta kā 32 baiti: yy koordināta un augstākajā bitā xx zīme. xx vērtību pārbaudītājs pats atrēķina no līknes vienādojuma — abi risinājumi atšķiras tikai ar zīmi, un tieši šis viens bits pasaka, kurš no tiem ir domāts.

Jaucējvērtības otrā puse, prefikss, atslēgai nav vajadzīga. Tā tiek izmantota nākamajā sadaļā.

9. Kāpēc nejaušība šeit nav nejauša

Katram šāda uzbūves parakstam ir vajadzīga vienreizēja vērtība rr, ko bieži sauc par nonce. Tā nekad nedrīkst atkārtoties: kam ir divi paraksti ar vienu un to pašu rr, tas var izrēķināt slepeno atslēgu ar skolas algebru.

Tieši uz tā ir cietušas reālas sistēmas. Zināmākais gadījums ir kādas spēļu konsoles parakstu pārbaude, kuras ražotājs 2010. gadā izmantoja vienmēr vienu un to pašu nonce vērtību — privātā atslēga tādējādi bija publiski rekonstruējama.

Ed25519 to atrisina, vispār neizmantojot nejaušību:

r=SHA-512(prefikss  ∥  m) mod ℓ.r = \mathrm{SHA\text{-}512}(\text{prefikss}\;\|\;m) \bmod \ell.

Nonce vērtība ir atkarīga no slepenā prefiksa un no ziņojuma. No tā izriet divas lietas:

  • Divas dažādas atsauksmes ar pārliecinošu varbūtību dod dažādas rr vērtības — atkārtošanās gadījums neiestājas.
  • Viena un tā pati atsauksme vienmēr dod vienu un to pašu parakstu. Parakstīšanas gaitu tādējādi var izsekot, un slikts nejaušības ģenerators uz servera neko nevar sabojāt, jo tāds nemaz nav vajadzīgs.

Atsauksmju portālam ar daudziem parakstiem dienā tā nav akadēmiska priekšrocība. Tā ir atšķirība starp „kļūda nejaušības avotā būtu liktenīga" un „nav nekāda nejaušības avota, kas varētu atteikt".

10. Parakstīšana

Trīs rindas, vairāk nav:

r=H(prefikss  ∥  m) mod ℓ,R=r⋅B,r = H(\text{prefikss}\;\|\;m) \bmod \ell, \qquad R = r\cdot B,
k=H(R  ∥  A  ∥  m) mod ℓ,k = H(R \;\|\; A \;\|\; m) \bmod \ell,
S=(r+k a) mod ℓ.S = (r + k\,a) \bmod \ell.

Paraksts ir pāris

σ=(R, S),\sigma = (R,\,S),

32 baiti punktam RR, 32 baiti skaitlim SS — kopā 64 baiti.

Ievērības vērta ir otrā rinda: kk vērtībā ieiet RR, publiskā atslēga AA un ziņojums. Tas, ka AA tiek līdzi jaukts, nav papildinājums — tas novērš uzbrukumus, kuros parakstu mēģina attiecināt uz citu atslēgu.

11. Pārbaude

Lasītāja pārlūkprogramma zina: atsauksmi mm, parakstu (R,S)(R,S) un publisko atslēgu AA. Tā no jauna aprēķina kk un pārbauda vienu vienīgu vienādojumu:

S⋅B  =  R+k⋅A\boxed{S\cdot B \;=\; R + k\cdot A}

Ja tas izpildās, paraksts ir derīgs. RFC 8032 papildus atļauj ar kofaktoru pareizināto versiju 8S⋅B=8R+8k⋅A8S\cdot B = 8R + 8k\cdot A, kas dažus robežgadījumus apstrādā pieļāvīgāk.

Neviens serveris netiek jautāts, nevienam pakalpojumam nav jābūt pieejamam. Pietiek ar publisko atslēgu.

12. Kāpēc vienādojums izpildās

Pietiek ar ievietošanu:

S⋅B=(r+k a)⋅B=r⋅B+k (a⋅B)=R+k⋅A.S\cdot B = (r + k\,a)\cdot B = r\cdot B + k\,(a\cdot B) = R + k\cdot A.

Viss triks slēpjas vidējā pārveidojumā: skalārā reizināšana saskan ar saskaitīšanu. Kas zina aa, var izrēķināt tādu SS, kas apmierina vienādojumu. Kas aa nezina, tam pašam izvēlētai kk vērtībai būtu jāatrod atbilstošs SS — un tas nozīmē atrisināt diskrēto logaritmu.

13. Pilnībā izrēķināts mini piemērs

Ar īstajiem skaitļiem nekas nav pārrēķināms — 253 bitu vērtības prātā pārbaudīt nevar. Tāpēc tas pats algoritms sīkā grupā, kurā katrs solis ir izsekojams ar kalkulatoru.

1. solis: grupa

Mēs rēķinām ar atlikumiem pēc moduļa 2323 un ņemam g=2g = 2. Ir spēkā

211=2048=89⋅23+1≡1(mod23),2^{11} = 2048 = 89\cdot 23 + 1 \equiv 1 \pmod{23},

tātad gg ģenerē apakšgrupu ar kārtu ℓ=11\ell = 11. Pakāpes ir šādas:

nn1234567891011
gng^n248169181336121

gg pārņem bāzes punkta BB lomu, reizināšana — punktu saskaitīšanas lomu. Skalāri tiek rēķināti pēc moduļa 1111, vērtības — pēc moduļa 2323.

2. solis: atslēgu pāris

Lai slepenais lielums ir a=6a = 6. Tad

A=ga=26=64≡18(mod23).A = g^a = 2^6 = 64 \equiv 18 \pmod{23}.

A=18A = 18 drīkst zināt ikviens.

3. solis: nonce vērtība un saistījums

Lai no prefiksa un atsauksmes rodas r=4r = 4. No tā:

R=gr=24=16.R = g^r = 2^4 = 16.

4. solis: izaicinājums

Lai jaucējvērtība pār RR, AA un atsauksmi dod

k=5.k = 5.

5. solis: paraksts

S=(r+k a) mod 11=(4+5⋅6) mod 11=34 mod 11=1.S = (r + k\,a) \bmod 11 = (4 + 5\cdot 6) \bmod 11 = 34 \bmod 11 = 1.

Paraksts ir pāris (R,S)=(16, 1)(R,S) = (16,\,1).

6. solis: pārlūkprogramma pārbauda

Tā aprēķina abas puses. Pa kreisi:

gS=21=2.g^S = 2^1 = 2.

Pa labi, ņemot vērā 185≡3(mod23)18^5 \equiv 3 \pmod{23}:

R⋅Ak=16⋅3=48≡2(mod23).R\cdot A^{k} = 16\cdot 3 = 48 \equiv 2 \pmod{23}.

Abas puses dod 22:

Paraksts derıˉgs\boxed{\text{Paraksts derīgs}}

7. solis: kāds maina atsauksmes tekstu

Teksts nonāk jaucējvērtībā, tātad mainās izaicinājums — teiksim, uz k′=7k' = 7. Paraksts paliek nemainīgs pie (16,1)(16,1), bet labā puse ne. Ņemot vērā 187≡6(mod23)18^7 \equiv 6 \pmod{23}:

R⋅Ak′=16⋅6=96≡4(mod23)  ≠  2=gSR\cdot A^{k'} = 16\cdot 6 = 96 \equiv 4 \pmod{23} \;\neq\; 2 = g^S
Paraksts nederıˉgs\boxed{\text{Paraksts nederīgs}}

Mēs varam atsauksmi izdzēst. Mainīt tā, lai to nepamanītu, mēs to nevaram.

Godīga piezīme par piemēru

Šeit tika rēķināts multiplikatīvajā grupā pēc moduļa 2323, nevis uz līknes: gSg^S apzīmē S⋅BS\cdot B, bet reizinājums R⋅AkR\cdot A^k — punktu saskaitīšanu R+k⋅AR + k\cdot A. Struktūra ir tā pati, un tieši par to ir runa. Atšķiras lielumu kārtas: ℓ=11\ell = 11 pret ℓ≈2252\ell \approx 2^{252}, un tur atslēgu nevar atrast, izmēģinot vienpadsmit iespējas.

14. 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 datu ieraksts un līdz ar to vismaz viena no abām jaucējvērtībām h un rh payload objektā. Tādējādi mainās mm, līdz ar to izaicinājums kk, līdz ar to pārbaudes vienādojuma labā puse. Vecais paraksts vairs neatbilst.

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 to neiztur, vairs neieplūst uzņēmuma vidējā vērtējumā.

15. Kāpēc uzbrucējs neizdodas

Viņš zina publisko atslēgu AA, bāzes punktu BB, līkni un katru līdz šim izsniegto parakstu. Viņam trūkst aa.

Labākajam zināmajam klasiskajam uzbrukumam diskrētā logaritma problēmai grupā ar kārtu ℓ\ell ir vajadzīgi aptuveni ℓ\sqrt{\ell} soļi. Pie ℓ≈2252\ell \approx 2^{252} tie ir aptuveni

21262^{126}

operāciju. Salīdzinājumam: pat mašīnai, kas paveic miljardu miljardu (101810^{18}) soļu sekundē, tam būtu vajadzīgs vairākkārtējs Visuma vecums.

Viltot bez atslēgas nozīmētu pašam izvēlētai kk vērtībai atrast atbilstošu SS — tas pats uzdevums citā izskatā.

16. Kāpēc Ed25519, nevis ECDSA

Abi balstās uz vienu un to pašu problēmu. Atšķirība slēpjas visā, kas notiek apkārt:

ECDSA (NIST līknes)Ed25519
Nonce vērtībavajadzīga svaiga nejaušībadeterministiska no prefiksa un ziņojuma
Formulasīpašie gadījumi, no datiem atkarīgi zaripilnīgas, viens rēķinu ceļš
Līknes parametrikonstanšu izcelsme nekad nav pilnībā izskaidrotaizvēlēti pēc izsekojamiem kritērijiem
Paraksta izmērs64–72 B, mainīgs kodējumsfiksēti 64 B
Pārlūkprogrammāpieejams jau senkopš 2023./2024. gada natīvi, citādi kā JS bibliotēka

Mums izšķirošais arguments bija nonce vērtība. Atsauksmju portāls paraksta bieži un automatizēti; algoritms, kurā viena vienīga vāja nejauša vērtība atklāj atslēgu, tam ir nepareizā izvēle.

17. Ko Ed25519 nespēj

Ed25519 balstās uz diskrēto logaritmu — un tieši šo problēmu pietiekami liels kvantu dators ar Šora algoritmu atrisina efektīvi. Vai un kad šādas mašīnas būs, ir atklāts jautājums. Atsauksmei, kurai pēc desmit gadiem joprojām jābūt pārbaudāmai, tas tomēr ir jautājums, uz kuru jāatbild šodien.

Tāpēc blakus Ed25519 parakstam var nostāties kvantu izturīgs zīmogs:

Neviens no tiem Ed25519 neaizstāj, tie nostājas tam blakus. Ja viens no algoritmiem tiek uzlauzts, otrs turpina nest.

18. Norise attēlā

PARAKSTĪŠANAS DIENESTS (MCGESUND)APMEKLĒTĀJA PĀRLŪKPROGRAMMAprivātais skalārs a + prefikss (no sēklas)Payload m = {uzņēmums, atsauksme, h, rh, iat}r = H(prefikss ‖ m) mod ℓR = r · Bk = H(R ‖ A ‖ m) mod ℓS = (r + k · a) mod ℓparaksts σ = (R, S) + kidatsauksme + σ + publiskā atslēga Ak no jauna aprēķināt no R, A un mS · B = R + k · A ?derīgsnederīgs
No payload objekta līdz ķeksītim pārlūkprogrammā. Virs atdalošās līnijas viss notiek vienreiz nosūtīšanas brīdī, zem tās — no jauna pie katra lasītāja, viņa ierīcē, tikai ar publisko atslēgu.

19. Ko McGesund ar to konkrēti dara

Aploksne. Katra parakstītā atsauksme nes MCG1: aploksni ar formāta versiju, payload objektu un Ed25519 parakstu. kid payload objektā pasaka, kura atslēga ir domāta; attiecīgo publisko atslēgu serveris izsniedz pēc pieprasījuma — tā ir publiska, tur nav nekā aizsargājama.

Pārbaude pārlūkprogrammā. Chrome un Firefox Ed25519 kopš 2023./2024. gada atbalsta natīvi caur WebCrypto saskarni. Safari — nē; tur izsaukums pārbaudes vietā izmet kļūdu. Tāpēc mūsu pārbaudes kods atkāpjas uz tīru JavaScript implementāciju, kas tiek ielādēta tikai tur, kur tā ir vajadzīga. Paraksta pārbaude tādējādi izpildās katrā pārlūkprogrammā, turklāt lasītāja ierīcē.

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 atslēga noteiktā brīdī jau eksistēja — un nevienam nav jātic mūsu laika zīmogam.

Satura piesaiste. Payload objekts nes rh, jaucējvērtību pār visu iesniegto datu ierakstu: tekstu, sirdis, ģeostatusu, ziņas par apmeklējuma iemeslu un izcelsmi. Ed25519 paraksts tādējādi piesaista ne tikai tekstu, bet visu, kas blakus atsauksmei tiek rādīts.

20. Viens teikums līdzņemšanai

Ed25519 paˉrveˉrsˇ slepenu skaitli vienaˉdojumaˉ,ko ikviens var paˉrreˉk¸inaˉt un neviens izdomaˉt.\boxed{ \begin{array}{c} \text{Ed25519 pārvērš slepenu skaitli vienādojumā,}\\ \text{ko ikviens var pārrēķināt un neviens izdomāt.} \end{array}}

Kam pieder slepenais skalārs, tas paraksta mikrosekundēs. Kam tā nav, tam būtu jāatrisina diskrētais logaritms grupā ar aptuveni 22522^{252} elementiem.

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