Allkirjastamismeetod

Ed25519 matemaatiliselt selgitatud

Allkiri, mis on iga McGesundi arvustuse küljes — kõverast üle võtme kuni võrrandini, mille lugeja brauser järele arvutab.

Seisuga: 2026-09-07

1. Millest siin jutt käib

McGesundi arvustus ei ole andmebaasi tekstiväli, mida tuleb lihtsalt uskuda. See allkirjastatakse digitaalselt juba saatmisel ja iga külastaja saab selle allkirja hiljem oma brauseris järele arvutada.

Selle allkirja jaoks kasutame Ed25519. Erinevalt FALCONist ja ML-DSA-st, mida saab lisatempliteks kõrvale panna, ei ole Ed25519 valikuvõimalus: iga allkirjastatud arvustus kannab seda, sõltumata paketist ja esitusviisist.

Kõigepealt oluline:

Ed25519 ei ole krüpteerimine. Arvustuse teksti ju peabki saama lugeda. Allkiri ei tõenda salastatust, vaid päritolu ja terviklikkust.

2. Mida täpselt allkirjastatakse

Allkirjastatakse mitte jooksvat teksti, vaid kompaktne andmeobjekt, mis naelutab teksti ja kõik ülejäänu üheselt kinni:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ettevõtte ID>",
  "c":   "<arvustuse ID>",
  "h":   "<arvustuse teksti SHA-256>",
  "rh":  "<kogu esitatud andmekirje SHA-256>",
  "rv":  1,
  "qh":  "<QR-Envelope'i SHA-256, ainult QR-arvustuste puhul>",
  "kid": "<võtme ID>",
  "iat": 1757203200
}

See objekt kodeeritakse CBOR-vormingusse. Just see baidijada — mitte selle kena esitus ülal — on meie sõnum mm. Allkiri ja sõnum rändavad koos ümbrikusse:

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

Number 33 on vorminguversioon. Rohkem seal ei ole — eelkõige mitte kvantijärgset allkirja: see asub, kui see on olemas, andmekirje juures kõrval, mitte ümbrikus.

3. Mida allkiri peab tagama

Lugeja, kes satub ettevõtte profiilile, seisab kahe küsimuse ees:

  1. Kas see arvustus pärineb tõesti McGesundi süsteemist?
  2. Kas seda on tagantjärele muudetud?

Selleks on olemas võtmepaar:

  • privaatvõti — jääb allkirjastamisteenusesse
  • avalik võti — tohib olla igaühel, seda adresseeritakse andmeosas oleva võtme-ID (kid) kaudu

Allkirjastatakse privaatvõtmega. Kontrollitakse avalikuga — ja nimelt lugeja brauseris, mitte meie serveris. Selles ongi mõte: kontroll, mille viime läbi ise ja mille tulemuse me ise teatame, ei oleks kontroll, vaid väide.

4. Miks elliptiline kõver?

Iga allkiri vajab arvutust, mis on ühes suunas lihtne ja teises praktiliselt võimatu. Ed25519 puhul on selleks skalaarkorrutamine elliptilisel kõveral:

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

Salajasest arvust aa avaliku punkti AA arvutamine võtab mikrosekundeid. Punktist AA tagasi arvule aa jõudmine on diskreetse logaritmi ülesanne — selle jaoks ei ole teada ühtki meetodit, mis sellise suuruse juures inimlikus ajavahemikus valmis saaks.

Praktiline võit vanemate meetodite, näiteks RSA ees, on suurus:

avalik võtiallkiri
RSA-3072384 B384 B
Ed2551932 B64 B

Ja seda võrreldava turvataseme juures. 64 baiti arvustuse kohta ei ole ka miljonite arvustuste puhul suurus, mille üle peaks mõtlema.

5. Kõver edwards25519

Arvutused käivad mooduli järgi, milleks on algarv:

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

Sellest ka nimi. Kõver on väänatud Edwardsi kõver:

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

„Punkt" on arvupaar (x,y)(x,y) hulgast {0,…,p−1}\{0,\dots,p-1\}, mis seda võrrandit rahuldab. Kõverat ei ole siin näha — järgmise jao joonis on näitlik abivahend reaalarvude kohal, mitte pilt tegelikust arvutusruumist.

Lisaks tuleb veel kaks suurust:

  • kindlaks määratud baaspunkt BB,
  • punktist BB tekitatud alamrühma järk ℓ\ell:
ℓ=2252+27742317777372353535851937790883648493.\ell = 2^{252} + 27742317777372353535851937790883648493.

ℓ\ell on algarv. See tähendab: kui liita BB ikka ja jälle iseendale, läbitakse täpselt ℓ\ell erinevat punkti ja jõutakse siis taas algusse. Kõik skalaaridega tehtavad arvutused käivad seetõttu mooduli ℓ\ell järgi, kõik koordinaatidega tehtavad mooduli pp järgi. Nende kahe arvu segiajamine on klassikaline algaja viga.

6. Punktide liitmine

Kaks punkti liidetakse kindla valemi järgi kolmandaks:

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

Neutraalne element on (0,1)(0,1) — punkt, kust arvutamine algab.

Sellel valemil on omadus, mida talle otsa vaadates ei märka ja mis on turvalisuse jaoks tähtsam kui ükskõik milline konstant: ta on täielik. Ta töötab kõigi sisendite korral, ilma erijuhtudeta „mõlemad punktid võrdsed" või „tulemus on neutraalne element". Vanematel Weierstrassi kõveratel need erijuhud on ja igaüks neist on programmis eraldi haru — haru, mille kestust saab mõõta. Kes mõõdab, kui kaua allkirjastamine kestab, saab selliste meetodite puhul salajase võtme kohta midagi teada.

Täielikud valemid tähendavad: alati sama arvutuskäik, alati sama aeg, midagi pole mõõta.

7. Skalaarkorrutamine — ühesuunaline tänav

n⋅Bn\cdot B tähendab: liita BB täpselt nn korda iseendale. 253-bitise nn puhul oleks see mõttetult palju tööd — seetõttu kahekordistatakse:

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

ja neist vahetulemustest pannakse soovitud nn kokku. Umbes 253 kahekordistamisest piisab iga nn jaoks. See on tee edasi.

Tagasisuunas sellist otseteed ei ole. Punktist AA arvu aa määramine tähendab diskreetse logaritmi ülesande lahendamist.

(0,1) — neutraalne elementB2B3B4B5B6B
Edwardsi kõver baaspunkti esimeste kordsetega, arvutatud tõelise liitmisreegli järgi. Reaalarvude kohal liiguvad nad mööda kõverat veel nähtavalt korrapäraselt — teed saaks tagasi jälgida. Mooduli p järgi kaob just see korrapära, ja sellel põhinebki turvalisus.

Tegelikus meetodis arvutatakse mooduli pp järgi. Seal ei ole „vasakut", „paremat" ega lähedust: 17 B17\,B-st ja 18 B18\,B-st saavad kaks arvupaari ilma igasuguse äratuntava suguluseta.

8. Allkirjastamisteenuse võtmepaar

Alguses on 32 juhuslikku baiti, seeme. Kõik ülejäänu tuletatakse sellest:

h=SHA-512(seeme),h=h0..31⏟→  a  ∥  h32..63⏟prefiks.h = \mathrm{SHA\text{-}512}(\text{seeme}), \qquad h = \underbrace{h_{0..31}}_{\to\;a}\;\|\;\underbrace{h_{32..63}}_{\text{prefiks}}.

Esimesest poolest tekib salajane skalaar aa, kuid mitte muutmata kujul. Kolm bitti seatakse või kustutatakse — nn clamping:

  • kolm kõige alumist bitti seatakse nulliks: aa muutub seeläbi 8 kordseks. Põhjuseks on kõvera kofaktor 8 — täielik punktirühm on kaheksa korda suurem kui järku ℓ\ell alamrühm. 8-ga jaguv aa satub garanteeritult õigesse alamrühma ega reeda väikest järku punktide kohta midagi.
  • kõige ülemine bitt kustutatakse, ülemuselt teine seatakse: aa-l on nii alati sama bitipikkus. Lühem aa vajaks vähem kahekordistamisi — ja jälle saaks kestusest midagi välja lugeda.

Avalik võti on siis lihtsalt

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

salvestatuna 32 baidina: yy-koordinaat ja kõige ülemises bitis xx-i märk. xx-i arvutab kontrollija ise kõvera võrrandist tagasi — mõlemad lahendid erinevad ainult märgi poolest ja seda, kumb on mõeldud, ütleb see üksainus bitt.

Räsiväärtuse teist poolt, prefiksit, võtme jaoks ei vajata. See tuleb kasutusele järgmises jaos.

9. Miks juhuslikkus siin juhuslik ei ole

Iga seda tüüpi allkiri vajab ühekordset väärtust rr, mida sageli nimetatakse nonsiks. See ei tohi kunagi korduda: kellel on kaks allkirja sama rr-iga, arvutab salajase võtme välja koolialgebraga.

Just selle peale on tegelikud süsteemid komistanud. Tuntuim juhtum on ühe mängukonsooli allkirjakontroll, mille tootja kasutas 2010. aastal alati sama nonssi — privaatvõti oli seega avalikult taastatav.

Ed25519 lahendab selle nii, et ei kasuta juhuslikkust üldse:

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

Nonss sõltub salajasest prefiksist ja sõnumist. Sellest järeldub kaks asja:

  • Kaks erinevat arvustust annavad ülekaaluka tõenäosusega erinevad rr-id — kordumise juhtu ei teki.
  • Sama arvustus annab alati sama allkirja. Allkirjastamist saab seega järele teha ja halb juhuarvugeneraator serveris ei saa midagi rikkuda, sest seda ei olegi vaja.

Arvustusportaali jaoks, kus tehakse päevas palju allkirju, ei ole see akadeemiline eelis. See on vahe „viga juhuslikkuse allikas oleks saatuslik" ja „ei olegi juhuslikkuse allikat, mis võiks tõrkuda" vahel.

10. Allkirjastamine

Kolm rida, rohkem seda ei ole:

r=H(prefiks  ∥  m) mod ℓ,R=r⋅B,r = H(\text{prefiks}\;\|\;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.

Allkiri on paar

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

32 baiti punkti RR jaoks, 32 baiti arvu SS jaoks — kokku 64 baiti.

Tähelepanuväärne on teine rida: kk-sse lähevad RR, avalik võti AA ja sõnum. See, et AA kaasa räsitakse, ei ole kaunistus — see väldib rünnakuid, mille käigus allkiri tõlgendatakse ümber teisele võtmele.

11. Kontrollimine

Lugeja brauser teab: arvustust mm, allkirja (R,S)(R,S) ja avalikku võtit AA. Ta arvutab kk uuesti välja ja kontrollib üht ainsat võrrandit:

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

Kui see kehtib, on allkiri kehtiv. RFC 8032 lubab lisaks kofaktoriga läbi korrutatud kuju 8S⋅B=8R+8k⋅A8S\cdot B = 8R + 8k\cdot A, mis käsitleb mõnda äärejuhtu leebemalt.

Ühtki serverit ei küsita, ükski teenus ei pea kättesaadav olema. Avalikust võtmest piisab.

12. Miks võrrand kehtib

Piisab asendamisest:

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.

Kogu trikk peitub keskmises teisenduses: skalaarkorrutamine sobib kokku liitmisega. Kes teab aa-d, saab välja arvutada SS-i, mis võrrandit rahuldab. Kes aa-d ei tea, peaks ise valitud kk jaoks leidma sobiva SS-i — ja see tähendab diskreetse logaritmi lahendamist.

13. Täielikult läbi arvutatud minimaalne näide

Tegelike arvudega ei ole midagi järele arvutada — 253-bitiseid väärtusi peast kontrollida ei saa. Seepärast sama meetod tillukeses rühmas, kus iga sammu saab taskuarvutiga järele teha.

1. samm: rühm

Arvutame jääkidega mooduli 2323 järgi ja võtame g=2g = 2. Kehtib

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

gg tekitab seega järku ℓ=11\ell = 11 alamrühma. Astmed on:

nn1234567891011
gng^n248169181336121

gg võtab üle baaspunkti BB rolli, korrutamine punktiliitmise oma. Skalaarid arvutatakse mooduli 1111, väärtused mooduli 2323 järgi.

2. samm: võtmepaar

Olgu salajane a=6a = 6. Siis on

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

A=18A = 18 tohib teada igaüks.

3. samm: nonss ja commitment

Olgu prefiksist ja arvustusest tulemuseks r=4r = 4. Sellest:

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

4. samm: väljakutse

Räsi RR-i, AA ja arvustuse üle andku

k=5.k = 5.

5. samm: allkiri

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.

Allkiri on paar (R,S)=(16, 1)(R,S) = (16,\,1).

6. samm: brauser kontrollib

Ta arvutab välja mõlemad pooled. Vasakul:

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

Paremal, kus 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}.

Mõlemad pooled annavad 22:

Allkiri kehtib\boxed{\text{Allkiri kehtib}}

7. samm: keegi muudab arvustuse teksti

Tekst läheb räsisse, seega muutub väljakutse — ütleme, et k′=7k' = 7. Allkiri jääb muutumatuna (16,1)(16,1)-ks, parem pool aga mitte. Kuna 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
Allkiri ei kehti\boxed{\text{Allkiri ei kehti}}

Me võime arvustuse kustutada. Muuta me seda märkamatult ei saa.

Aus märkus näite kohta

Siin arvutati multiplikatiivses rühmas mooduli 2323 järgi, mitte kõveral: gSg^S tähistab S⋅BS\cdot B-d, korrutis R⋅AkR\cdot A^k punktiliitmist R+k⋅AR + k\cdot A. Struktuur on sama ja just see ongi oluline. Erinevad on suurusjärgud: ℓ=11\ell = 11 versus ℓ≈2252\ell \approx 2^{252}, ja seal ei leia võtit üheteistkümne võimaluse läbiproovimisega.

14. Mis juhtub, kui keegi arvustust muudab

Oletame, et keegi, kellel on ligipääs andmebaasile — ka keegi meie juurest — muudab arvustuse teksti või üht südametest. Siis muutub andmekirje ja sellega vähemalt üks kahest räsiväärtusest h ja rh andmeosas. Sellega muutub mm, sellega väljakutse kk, sellega kontrollvõrrandi parem pool. Vana allkiri enam ei sobi.

Otsustav lause selle kohta: me võime arvustuse kustutada, aga me ei saa seda märkamatult muuta. McGesundis käib sama kontroll lisaks igal ööl serveripoolselt üle kogu andmestiku — arvustus, mis seda ei läbi, ei lähe enam ettevõtte keskmisesse arvesse.

15. Miks ründaja läbi kukub

Ta teab avalikku võtit AA, baaspunkti BB, kõverat ja iga seni väljastatud allkirja. Puudu on tal aa.

Parim teadaolev klassikaline rünnak diskreetse logaritmi ülesandele järku ℓ\ell rühmas vajab umbes ℓ\sqrt{\ell} sammu. ℓ≈2252\ell \approx 2^{252} korral on see ligikaudu

21262^{126}

operatsiooni. Võrdluseks: isegi masin, mis suudab miljard miljardit (101810^{18}) sammu sekundis, vajaks selleks mitmekordset universumi vanust.

Võltsimine ilma võtmeta tähendaks ise valitud kk jaoks sobiva SS-i leidmist — sama ülesanne teises kuues.

16. Miks Ed25519 ja mitte ECDSA

Mõlemad põhinevad samal ülesandel. Erinevus peitub kõiges, mis toimub selle ümber:

ECDSA (NISTi kõverad)Ed25519
Nonssvajab värsket juhuslikkustdeterministlik prefiksist ja sõnumist
Valemiderijuhud, andmesõltuvad harudtäielikud, üks arvutuskäik
Kõvera parameetridkonstantide päritolu ei ole kunagi täielikult selgitatudvalitud jälgitavate kriteeriumide järgi
Allkirja suurus64–72 B, muutuv kodeeringpüsivalt 64 B
Brauserisammu saadavalalates 2023/2024 natiivselt, muidu JS-teegina

Meie jaoks oli nonss otsustav argument. Arvustusportaal allkirjastab tihti ja automaatselt; meetod, mille puhul üksainus nõrk juhuväärtus võtme reedab, on selleks vale valik.

17. Mida Ed25519 ei suuda

Ed25519 põhineb diskreetsel logaritmil — ja just selle ülesande lahendab piisavalt suur kvantarvuti Shori algoritmiga tõhusalt. Kas ja millal selliseid masinaid on, on lahtine. Arvustuse jaoks, mis peab kümne aasta pärast veel kontrollitav olema, on see sellegipoolest küsimus, millele tuleb vastata täna.

Seepärast võib Ed25519 allkirja kõrvale astuda kvantiresistentne tempel:

Kumbki ei asenda Ed25519, vaid asub selle kõrvale. Kui üks meetoditest murtakse, kannab teine edasi.

18. Kulg pildis

ALLKIRJASTAMISTEENUS (MCGESUND)KÜLASTAJA BRAUSERprivaatne skalaar a + prefiks (seemnest)andmeosa m = {ettevõte, arvustus, h, rh, iat}r = H(prefiks ‖ m) mod ℓR = r · Bk = H(R ‖ A ‖ m) mod ℓS = (r + k · a) mod ℓallkiri σ = (R, S) + kidarvustus + σ + avalik võti Ak arvutatakse uuesti R-ist, A-st ja m-istS · B = R + k · A ?kehtibei kehti
Andmeosast kuni linnukeseni brauseris. Eraldusjoonest ülalpool toimub kõik korra saatmise ajal, allpool iga lugeja jaoks uuesti — tema seadmes, üksnes avaliku võtmega.

19. Mida McGesund sellega konkreetselt teeb

Envelope. Iga allkirjastatud arvustus kannab MCG1:-ümbrikku, milles on vorminguversioon, andmeosa ja Ed25519 allkiri. Andmeosas olev kid ütleb, millist võtit mõeldakse; vastava avaliku võtme väljastab server päringu peale — see on avalik, seal ei ole midagi kaitsta.

Kontroll brauseris. Chrome ja Firefox oskavad Ed25519 alates 2023/2024 natiivselt WebCrypto liidese kaudu. Safari mitte — seal lõpeb vastav funktsioonikutse veaga, selle asemel et kontrollida. Seepärast langeb meie kontrollikood tagasi puhtale JavaScripti teostusele, mis laaditakse juurde ainult seal, kus seda vaja on. Allkirjakontroll läheb nii läbi igas brauseris, ja nimelt lugeja seadmes.

Ajaankur. Allkirjastamisvõtme sõrmejälg ankurdatakse OpenTimestampsi kaudu Bitcoini plokki. Sellega ei saa tõendada mitte üksnes seda, et allkiri on ehtne, vaid ka seda, et võti oli teataval ajahetkel juba olemas — ilma et keegi peaks uskuma meie ajatemplit.

Sisu sidumine. Andmeosa kannab välja rh, räsi kogu esitatud andmekirje üle: tekst, südamed, geostaatus, ajendi andmed ja päritolu. Ed25519 allkiri seob seega mitte ainult teksti, vaid kõik, mida arvustuse kõrval kuvatakse.

20. Üks lause kaasavõtmiseks

Ed25519 muudab salajase arvu vo˜rrandiks, midaigau¨ks saab kontrollida ja keegi ei saa va¨lja mo˜elda.\boxed{ \begin{array}{c} \text{Ed25519 muudab salajase arvu võrrandiks, mida}\\ \text{igaüks saab kontrollida ja keegi ei saa välja mõelda.} \end{array}}

Kellel on salajane skalaar, allkirjastab mikrosekunditega. Kellel seda ei ole, peaks lahendama diskreetse logaritmi rühmas, kus on umbes 22522^{252} elementi.

Arvustuse lugeja jaoks tähendab see lihtsalt: ta ei pea meid uskuma. Ta saab järele arvutada.