Parašo algoritmas

Ed25519 paaiškintas matematiškai

Parašas, kuris lydi kiekvieną McGesund atsiliepimą — nuo kreivės ir rakto iki lygybės, kurią perskaičiuoja skaitytojo naršyklė.

Būklė: 2026-09-07

1. Apie ką čia kalbama

Atsiliepimas McGesund sistemoje nėra tiesiog teksto laukas duomenų bazėje, kuriuo tenka patikėti. Išsiunčiamas jis pasirašomas skaitmeniniu būdu, ir kiekvienas lankytojas gali šį parašą vėliau perskaičiuoti savo paties naršyklėje.

Šiam parašui naudojame Ed25519. Kitaip nei FALCON ir ML-DSA, kuriuos galima papildomai pridėti kaip antspaudą, Ed25519 nėra pasirinkimas: jį turi kiekvienas pasirašytas atsiliepimas, nepriklausomai nuo tarifo ir pateikimo būdo.

Svarbu iš karto:

Ed25519 nėra šifravimas. Atsiliepimo tekstas juk skirtas skaityti. Parašas įrodo ne slaptumą, o kilmę ir vientisumą.

2. Kas tiksliai pasirašoma

Pasirašomas ne ištisinis tekstas, o kompaktiškas duomenų objektas, kuris vienareikšmiškai užfiksuoja tekstą ir visa kita:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<įmonės ID>",
  "c":   "<atsiliepimo ID>",
  "h":   "<atsiliepimo teksto SHA-256>",
  "rh":  "<viso pateikimo duomenų rinkinio SHA-256>",
  "rv":  1,
  "qh":  "<QR voko SHA-256, tik QR atsiliepimuose>",
  "kid": "<rakto ID>",
  "iat": 1757203200
}

Šis objektas užkoduojamas CBOR formatu. Ši baitų seka — o ne jos graži išklotinė viršuje — yra mūsų pranešimas mm. Parašas ir pranešimas kartu keliauja į voką:

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

Skaičius 33 yra formato versija. Daugiau nieko jame nėra — ypač jokio postkvantinio parašo: jis, jei egzistuoja, guli šalia duomenų rinkinio, o ne voke.

3. Ką parašas turi užtikrinti

Skaitytojas, atsidūręs įmonės profilyje, turi du klausimus:

  1. Ar šis atsiliepimas tikrai kilęs iš McGesund sistemos?
  2. Ar jis buvo pakeistas vėliau?

Tam naudojama raktų pora:

  • privatusis raktas — lieka parašų tarnyboje
  • viešasis raktas — jį gali turėti bet kas, jis adresuojamas per rakto ID (kid) naudingojoje apkrovoje

Pasirašoma privačiuoju raktu. Tikrinama viešuoju — ir būtent skaitytojo naršyklėje, o ne mūsų serveryje. Čia ir esmė: patikra, kurią atliekame patys ir kurios rezultatą paskelbiame, būtų ne patikra, o tvirtinimas.

4. Kodėl elipsinė kreivė?

Kiekvienam parašui reikia skaičiavimo, kuris viena kryptimi yra lengvas, o kita — praktiškai neįmanomas. Ed25519 atveju tai skaliarinė daugyba elipsinėje kreivėje:

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

Iš slapto skaičiaus aa apskaičiuoti viešąjį tašką AA trunka mikrosekundes. Iš AA atgal nustatyti aa reiškia spręsti diskretinio logaritmo uždavinį — tokio dydžio atveju nėra žinomo metodo, kuris susidorotų su juo per žmogui suvokiamą laiką.

Praktinė nauda, palyginti su senesniais metodais, tokiais kaip RSA, yra dydis:

viešasis raktasparašas
RSA-3072384 B384 B
Ed2551932 B64 B

Ir tai esant panašiam saugumo lygiui. 64 baitai vienam atsiliepimui net ir prie milijonų atsiliepimų nėra dydis, apie kurį reikėtų galvoti.

5. Kreivė edwards25519

Skaičiuojama moduliu, kuris yra pirminis skaičius:

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

Iš čia ir pavadinimas. Kreivė yra pasukta Edwardso kreivė:

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

„Taškas" yra skaičių pora (x,y)(x,y) iš aibės {0,…,p−1}\{0,\dots,p-1\}, tenkinanti šią lygtį. Jokios kreivės čia nepamatysi — piešinys kitame skyriuje yra tik vaizdinė pagalba realiųjų skaičių srityje, o ne tikrosios skaičiavimo erdvės atvaizdas.

Prisideda dar du dydžiai:

  • iš anksto sutartas bazinis taškas BB,
  • taško BB generuojamo pogrupio eilė ℓ\ell:
ℓ=2252+27742317777372353535851937790883648493.\ell = 2^{252} + 27742317777372353535851937790883648493.

ℓ\ell yra pirminis. Tai reiškia: nuolat pridedant BB prie savęs, pereinama lygiai ℓ\ell skirtingų taškų, o paskui vėl atsiduriama pradžioje. Todėl visi skaičiavimai su skaliarais vyksta moduliu ℓ\ell, o visi skaičiavimai su koordinatėmis — moduliu pp. Šių dviejų skaičių supainiojimas yra klasikinė pradedančiojo klaida.

6. Taškų sudėtis

Du taškai pagal fiksuotą formulę suskaičiuojami į trečią:

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

Neutralusis elementas yra (0,1)(0,1) — taškas, nuo kurio skaičiavimas prasideda.

Ši formulė turi savybę, kurios iš jos nematyti ir kuri saugumui svarbesnė už bet kurią konstantą: ji yra pilnoji. Ji veikia su visomis įvestimis, be atskirų atvejų „abu taškai sutampa" ar „rezultatas yra neutralusis elementas". Senesnėse Weierstrasso kreivėse tokie atskiri atvejai yra, ir kiekvienas iš jų — atskira programos šaka, kurios vykdymo trukmę galima išmatuoti. Kas matuoja, kiek trunka parašas, tokiuose metoduose sužino šį tą apie slaptąjį raktą.

Pilnosios formulės reiškia: visada tas pats skaičiavimo kelias, visada ta pati trukmė, nėra ko matuoti.

7. Skaliarinė daugyba — vienpusis eismas

n⋅Bn\cdot B reiškia: pridėti BB prie savęs lygiai nn kartų. Kai nn turi 253 bitus, tai būtų beprasmiškai daug darbo — todėl dvigubinama:

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

ir iš šių tarpinių rezultatų sudėliojamas norimas nn. Maždaug 253 dvigubinimų pakanka bet kuriam nn. Toks yra kelias pirmyn.

Atgal tokio trumpinio nėra. Iš taško AA nustatyti skaičių aa reiškia išspręsti diskretinio logaritmo uždavinį.

(0,1) — neutralusis elementasB2B3B4B5B6B
Edwardso kreivė su pirmaisiais bazinio taško kartotiniais, apskaičiuotais pagal tikrąjį sudėties dėsnį. Realiųjų skaičių srityje jie dar juda kreive matomai tvarkingai — kelią būtų galima atsekti atgal. Moduliu p dingsta būtent ši tvarka, ir tuo remiasi saugumas.

Tikrajame metode skaičiuojama moduliu pp. Ten nėra nei „kairės", nei „dešinės", nei artumo: iš 17 B17\,B ir 18 B18\,B gaunamos dvi skaičių poros be jokios atpažįstamos giminystės.

8. Parašų tarnybos raktų pora

Pradžioje yra 32 atsitiktiniai baitai — sėkla (seed). Visa kita išvedama iš jos:

h=SHA-512(Seed),h=h0..31⏟→  a  ∥  h32..63⏟priesˇde˙lis.h = \mathrm{SHA\text{-}512}(\text{Seed}), \qquad h = \underbrace{h_{0..31}}_{\to\;a}\;\|\;\underbrace{h_{32..63}}_{\text{priešdėlis}}.

Iš pirmosios pusės gaunamas slaptasis skaliaras aa, tačiau ne nepakeistas. Trys bitai nustatomi arba nunulinami — tai vadinamasis clamping:

  • trys žemiausi bitai nustatomi į nulį: taip aa tampa aštuonių kartotiniu. Priežastis — kreivės kofaktorius 8: visa taškų grupė yra aštuonis kartus didesnė už ℓ\ell eilės pogrupį. Iš 8 dalus aa garantuotai patenka į teisingą pogrupį ir nieko neatskleidžia apie mažos eilės taškus.
  • aukščiausias bitas nunulinamas, antrasis iš viršaus nustatomas: taip aa visada turi tą patį bitų ilgį. Trumpesniam aa reikėtų mažiau dvigubinimų — ir vėl iš vykdymo trukmės būtų galima šį tą nuskaityti.

Viešasis raktas tada yra tiesiog

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

saugomas kaip 32 baitai: yy koordinatė, o aukščiausiame bite — xx ženklas. xx tikrintojas pats atgal apskaičiuoja iš kreivės lygties — abu sprendiniai skiriasi tik ženklu, o kuris turimas omenyje, pasako šis vienas bitas.

Antroji maišos reikšmės pusė — priešdėlis — raktui nereikalinga. Ji panaudojama kitame skyriuje.

9. Kodėl atsitiktinumas čia nėra atsitiktinis

Kiekvienam tokios sandaros parašui reikia vienkartinės reikšmės rr, dažnai vadinamos nonce. Ji niekada negali pasikartoti: kas turi du parašus su tuo pačiu rr, gali slaptąjį raktą išvesti mokyklinės algebros priemonėmis.

Būtent dėl to sudužo realios sistemos. Žinomiausias atvejis — vienos žaidimų konsolės parašų patikra, kurios gamintojas 2010 m. visada naudojo tą patį nonce; privatusis raktas tapo viešai atkuriamas.

Ed25519 tai išsprendžia visai nenaudodamas atsitiktinumo:

r=SHA-512(priesˇde˙lis  ∥  m) mod ℓ.r = \mathrm{SHA\text{-}512}(\text{priešdėlis}\;\|\;m) \bmod \ell.

Nonce priklauso nuo slaptojo priešdėlio ir nuo pranešimo. Iš to plaukia du dalykai:

  • Du skirtingi atsiliepimai su didžiule tikimybe duoda skirtingus rr — pasikartojimo atvejis neįvyksta.
  • Tas pats atsiliepimas visada duoda tą patį parašą. Taip pasirašymo veiksmą galima atkartoti, o prastas atsitiktinių skaičių generatorius serveryje nieko sugadinti negali, nes jo tiesiog nereikia.

Atsiliepimų portalui, kuriame per dieną atliekama daug parašų, tai nėra akademinis pranašumas. Tai skirtumas tarp „klaida atsitiktinumo šaltinyje būtų lemtinga" ir „nėra jokio atsitiktinumo šaltinio, kuris galėtų sugesti".

10. Pasirašymas

Trys eilutės, ir viskas:

r=H(priesˇde˙lis  ∥  m) mod ℓ,R=r⋅B,r = H(\text{priešdėlis}\;\|\;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.

Parašas yra pora

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

32 baitai taškui RR, 32 baitai skaičiui SS — iš viso 64 baitai.

Verta atkreipti dėmesį į antrąją eilutę: į kk įeina RR, viešasis raktas AA ir pranešimas. Tai, kad AA taip pat maišomas, nėra priedas — tai užkerta kelią atakoms, kai parašas pertraktuojamas kaip skirtas kitam raktui.

11. Tikrinimas

Skaitytojo naršyklė žino: atsiliepimą mm, parašą (R,S)(R,S) ir viešąjį raktą AA. Ji iš naujo apskaičiuoja kk ir patikrina vienintelę lygybę:

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

Jei ji galioja, parašas yra teisingas. RFC 8032 papildomai leidžia kofaktoriumi padaugintą pavidalą 8S⋅B=8R+8k⋅A8S\cdot B = 8R + 8k\cdot A, kuris kai kuriuos kraštinius atvejus traktuoja dosniau.

Jokio serverio klausti nereikia, joks servisas neturi būti pasiekiamas. Pakanka viešojo rakto.

12. Kodėl lygybė galioja

Pakanka įstatyti:

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.

Visa gudrybė slypi viduriniame pertvarkyme: skaliarinė daugyba dera su sudėtimi. Kas žino aa, gali apskaičiuoti tokį SS, kuris tenkina lygybę. Kas aa nežino, turėtų prie savo pasirinkto kk rasti tinkamą SS — o tai reiškia išspręsti diskretinį logaritmą.

13. Iki galo perskaičiuotas mažas pavyzdys

Su tikrais skaičiais nieko perskaičiuoti nepavyks — 253 bitų reikšmių mintinai nepatikrinsi. Todėl tas pats metodas mažytėje grupėje, kurioje kiekvieną žingsnį galima atsekti skaičiuotuvu.

1 žingsnis: grupė

Skaičiuojame su liekanomis moduliu 2323 ir imame g=2g = 2. Galioja

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

taigi gg generuoja ℓ=11\ell = 11 eilės pogrupį. Laipsniai yra tokie:

nn1234567891011
gng^n248169181336121

gg perima bazinio taško BB vaidmenį, o daugyba — taškų sudėties. Skaliarai skaičiuojami moduliu 1111, reikšmės — moduliu 2323.

2 žingsnis: raktų pora

Tegul slaptas skaičius yra a=6a = 6. Tada

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

A=18A = 18 gali žinoti bet kas.

3 žingsnis: nonce ir įsipareigojimas

Tegul iš priešdėlio ir atsiliepimo gaunasi r=4r = 4. Iš to:

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

4 žingsnis: iššūkis

Tegul maiša per RR, AA ir atsiliepimą duoda

k=5.k = 5.

5 žingsnis: parašas

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.

Parašas yra pora (R,S)=(16, 1)(R,S) = (16,\,1).

6 žingsnis: naršyklė tikrina

Ji apskaičiuoja abi puses. Kairė:

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

Dešinė, kai 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}.

Abi pusės duoda 22:

Parasˇas galioja\boxed{\text{Parašas galioja}}

7 žingsnis: kas nors pakeičia atsiliepimo tekstą

Tekstas patenka į maišą, taigi pasikeičia iššūkis — tarkime, į k′=7k' = 7. Parašas lieka nepakitęs, (16,1)(16,1), o dešinė pusė — ne. Kai 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
Parasˇas negalioja\boxed{\text{Parašas negalioja}}

Atsiliepimą galime ištrinti. Pakeisti jo nepastebimai negalime.

Sąžininga pastaba apie pavyzdį

Čia skaičiuota daugybinėje grupėje moduliu 2323, o ne kreivėje: gSg^S atitinka S⋅BS\cdot B, o sandauga R⋅AkR\cdot A^k — taškų sudėtį R+k⋅AR + k\cdot A. Struktūra yra ta pati, ir būtent apie ją čia kalbama. Skiriasi eilės: ℓ=11\ell = 11 prieš ℓ≈2252\ell \approx 2^{252}, ir ten rakto nerasi perrinkdamas vienuolika galimybių.

14. Kas nutinka, kai kas nors pakeičia atsiliepimą

Tarkime, kažkas, turintis prieigą prie duomenų bazės — taip pat ir kažkas iš mūsų — pakeičia atsiliepimo tekstą arba vieną iš širdelių. Tada pasikeičia duomenų rinkinys, o kartu bent viena iš dviejų maišos reikšmių h ir rh naudingojoje apkrovoje. Kartu pasikeičia mm, kartu iššūkis kk, kartu ir dešinioji patikros lygybės pusė. Senasis parašas nebetinka.

Lemiamas sakinys toks: atsiliepimą galime ištrinti, bet pakeisti jo nepastebimai negalime. McGesund sistemoje ta pati patikra papildomai kas naktį atliekama serveryje visam duomenų kiekiui — atsiliepimas, kuris jos neišlaiko, į įmonės vidurkį nebeįskaitomas.

15. Kodėl užpuolikui nepavyksta

Jis žino viešąjį raktą AA, bazinį tašką BB, kreivę ir kiekvieną iki šiol išduotą parašą. Jam trūksta aa.

Geriausiai žinomai klasikinei atakai prieš diskretinio logaritmo uždavinį ℓ\ell eilės grupėje reikia maždaug ℓ\sqrt{\ell} žingsnių. Kai ℓ≈2252\ell \approx 2^{252}, tai maždaug

21262^{126}

operacijų. Palyginimui: net mašinai, atliekančiai milijardą milijardų (101810^{18}) žingsnių per sekundę, prireiktų daugybės Visatos amžių.

Klastoti be rakto reikštų prie savo pasirinkto kk rasti tinkamą SS — ta pati užduotis kitu pavidalu.

16. Kodėl Ed25519, o ne ECDSA

Abu remiasi ta pačia problema. Skirtumas slypi visame, kas vyksta aplinkui:

ECDSA (NIST kreivės)Ed25519
Noncereikalingas šviežias atsitiktinumasdeterministinis, iš priešdėlio ir pranešimo
Formulėsatskiri atvejai, nuo duomenų priklausančios šakospilnosios, vienas skaičiavimo kelias
Kreivės parametraikonstantų kilmė niekada iki galo nepaaiškintaparinktos pagal atsekamus kriterijus
Parašo dydis64–72 B, kintamas kodavimasfiksuoti 64 B
Naršyklėjeprieinama jau seniainuo 2023–2024 m. natyviai, kitaip kaip JS biblioteka

Mums lemiamas argumentas buvo nonce. Atsiliepimų portalas pasirašo dažnai ir automatiškai; metodas, kuriame viena silpna atsitiktinė reikšmė atskleidžia raktą, tam yra netinkamas pasirinkimas.

17. Ko Ed25519 neužtikrina

Ed25519 remiasi diskretiniu logaritmu — o būtent šį uždavinį pakankamai didelis kvantinis kompiuteris efektyviai išsprendžia Šoro algoritmu. Ar ir kada tokios mašinos atsiras, neaišku. Tačiau atsiliepimui, kuris turi likti patikrinamas ir po dešimties metų, tai vis tiek klausimas, į kurį reikia atsakyti šiandien.

Todėl greta Ed25519 parašo gali atsirasti kvantams atsparus antspaudas:

Nė vienas iš jų Ed25519 nepakeičia, jie guli šalia. Jei vienas metodas bus palaužtas, kitas laikys toliau.

18. Eiga paveiksle

PARAŠŲ TARNYBA (MCGESUND)LANKYTOJO NARŠYKLĖprivatusis skaliaras a + priešdėlis (iš sėklos)Naudingoji apkrova m = {įmonė, atsiliepimas, h, rh, iat}r = H(priešdėlis ‖ m) mod ℓR = r · Bk = H(R ‖ A ‖ m) mod ℓS = (r + k · a) mod ℓParašas σ = (R, S) + kidatsiliepimas + σ + viešasis raktas Ak perskaičiuoti iš R, A ir mS · B = R + k · A ?galiojanegalioja
Nuo naudingosios apkrovos iki varnelės naršyklėje. Virš skiriamosios linijos viskas vyksta vieną kartą išsiunčiant, žemiau — iš naujo pas kiekvieną skaitytoją, jo įrenginyje, vien su viešuoju raktu.

19. Ką konkrečiai su tuo daro McGesund

Vokas. Kiekvienas pasirašytas atsiliepimas turi MCG1: voką su formato versija, naudingąja apkrova ir Ed25519 parašu. kid naudingojoje apkrovoje nurodo, kuris raktas turimas omenyje; atitinkamą viešąjį raktą serveris pateikia paprašius — jis yra viešas, jame nėra ko saugoti.

Patikra naršyklėje. Chrome ir Firefox nuo 2023–2024 m. moka Ed25519 natyviai per WebCrypto sąsają. Safari — ne; ten kvietimas vietoj patikros meta klaidą. Todėl mūsų tikrinimo kodas atsitraukia į gryną JavaScript realizaciją, kuri įkeliama tik ten, kur jos reikia. Taip parašo patikra pavyksta kiekvienoje naršyklėje, ir būtent skaitytojo įrenginyje.

Laiko inkaras. Parašo rakto kontrolinis atspaudas per OpenTimestamps įtvirtinamas Bitcoin bloke. Taip galima įrodyti ne tik tai, kad parašas tikras, bet ir tai, kad raktas tam tikru momentu jau egzistavo — nereikalaujant iš nieko tikėti mūsų laiko žyma.

Turinio susiejimas. Naudingojoje apkrovoje yra rh — viso pateikimo duomenų rinkinio maiša: teksto, širdelių, geo statuso, aplinkybių duomenų ir kilmės. Taip Ed25519 parašas susieja ne tik tekstą, bet ir viską, kas rodoma šalia atsiliepimo.

20. Vienas sakinys įsidėmėti

Ed25519 pavercˇia slaptą skaicˇių lygybe, kurią kiekvienasgali perskaicˇiuoti ir kurios niekas negali isˇgalvoti.\boxed{ \begin{array}{c} \text{Ed25519 paverčia slaptą skaičių lygybe, kurią kiekvienas}\\ \text{gali perskaičiuoti ir kurios niekas negali išgalvoti.} \end{array}}

Kas turi slaptąjį skaliarą, pasirašo per mikrosekundes. Kas jo neturi, turėtų išspręsti diskretinį logaritmą grupėje, turinčioje maždaug 22522^{252} elementų.

Atsiliepimo skaitytojui tai reiškia paprastą dalyką: jam nereikia mumis tikėti. Jis gali perskaičiuoti.