Allekirjoitusmenetelmä

Ed25519 matemaattisesti selitettynä

Allekirjoitus, joka liittyy jokaiseen McGesund-arvioon — käyrästä avaimeen ja siihen yhtälöön, jonka lukijan selain laskee uudelleen.

Päivitetty: 2026-09-07

1. Mistä tässä on kyse

Arvio McGesundissa ei ole tietokannan tekstikenttä, johon on vain uskottava. Se allekirjoitetaan digitaalisesti lähetyshetkellä, ja jokainen kävijä voi myöhemmin laskea allekirjoituksen uudelleen omassa selaimessaan.

Tähän allekirjoitukseen käytämme Ed25519-menetelmää. Toisin kuin FALCON ja ML-DSA, jotka voidaan asettaa sen rinnalle lisäleimoiksi, Ed25519 ei ole valinnainen: jokainen allekirjoitettu arvio kantaa sitä pakettitasosta ja lähetystavasta riippumatta.

Tärkeä huomautus aluksi:

Ed25519 ei ole salausmenetelmä. Arviotekstihän on tarkoitettu luettavaksi. Allekirjoitus ei todista salassapitoa vaan alkuperän ja eheyden.

2. Mitä tarkalleen allekirjoitetaan

Allekirjoitettavana ei ole leipäteksti vaan tiivis tietokohde, joka naulaa tekstin ja kaiken muun yksikäsitteisesti kiinni:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<yritystunnus>",
  "c":   "<arviotunnus>",
  "h":   "<arviotekstin SHA-256>",
  "rh":  "<koko lähetystietueen SHA-256>",
  "rv":  1,
  "qh":  "<QR-Envelopen SHA-256, vain QR-arvioissa>",
  "kid": "<avaintunnus>",
  "iat": 1757203200
}

Tämä kohde koodataan CBOR-muotoon. Juuri tämä tavujono — eikä sen yllä oleva siisti esitys — on viestimme mm. Allekirjoitus ja viesti kulkevat yhdessä kuoreen:

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

Luku 33 on muotoversio. Enempää siinä ei ole — ei etenkään post-kvanttiallekirjoitusta: se on, mikäli sellainen on olemassa, tietueen yhteydessä eikä kuoressa.

3. Mitä allekirjoituksen on määrä saada aikaan

Yritysprofiilille saapuva lukija kohtaa kaksi kysymystä:

  1. Onko tämä arvio todella peräisin McGesund-järjestelmästä?
  2. Onko sitä muutettu jälkikäteen?

Sitä varten on avainpari:

  • yksityinen avain — pysyy allekirjoituspalvelussa
  • julkinen avain — saa olla kenellä tahansa, ja se osoitetaan payloadissa olevalla avaintunnuksella (kid)

Allekirjoittaminen tapahtuu yksityisellä avaimella. Todentaminen tapahtuu julkisella — ja nimenomaan lukijan selaimessa, ei meidän palvelimellamme. Juuri tässä on ydin: tarkistus, jonka suoritamme itse ja jonka tuloksen ilmoitamme, ei olisi tarkistus vaan väite.

4. Miksi elliptinen käyrä?

Jokainen allekirjoitus tarvitsee laskutoimituksen, joka on yhteen suuntaan helppo ja toiseen käytännössä mahdoton. Ed25519:ssä se on skalaarikertolasku elliptisellä käyrällä:

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

Julkisen pisteen AA laskeminen salaisesta luvusta aa vie mikrosekunteja. Päättely pisteestä AA takaisin lukuun aa on diskreetin logaritmin ongelma — siihen ei tunneta menetelmää, joka tämän kokoluokan tapauksessa valmistuisi inhimillisessä ajassa.

Käytännön hyöty vanhempiin menetelmiin kuten RSA:han verrattuna on koko:

julkinen avainallekirjoitus
RSA-3072384 B384 B
Ed2551932 B64 B

Ja tämä vertailukelpoisella turvallisuustasolla. 64 tavua arviota kohti ei ole miljoonienkaan arvioiden kohdalla kokoluokka, jota tarvitsisi pohtia.

5. Käyrä edwards25519

Laskutoimitukset tehdään modulo alkuluvun:

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

Siitä nimi. Käyrä on kierretty Edwardsin käyrä:

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

”Piste” on lukupari (x,y)(x,y) joukosta {0,…,p−1}\{0,\dots,p-1\}, joka toteuttaa tämän yhtälön. Käyrää ei ole näkyvissä — seuraavan luvun piirros on havainnollistus reaalilukujen yli, ei kuva todellisesta laskuavaruudesta.

Mukaan tulee vielä kaksi suuretta:

  • kiinteästi sovittu kantapiste BB,
  • pisteen BB virittämän aliryhmän kertaluku ℓ\ell:
ℓ=2252+27742317777372353535851937790883648493.\ell = 2^{252} + 27742317777372353535851937790883648493.

ℓ\ell on alkuluku. Se tarkoittaa: kun pistettä BB lasketaan yhä uudelleen itseensä, käydään läpi täsmälleen ℓ\ell eri pistettä ja päädytään sitten takaisin alkuun. Kaikki skalaarien laskutoimitukset tehdään siksi modulo ℓ\ell ja kaikki koordinaattien laskutoimitukset modulo pp. Näiden kahden luvun sekoittaminen on klassinen aloittelijan virhe.

6. Pisteiden yhteenlasku

Kaksi pistettä yhdistetään kiinteällä kaavalla kolmanneksi:

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

Neutraalialkio on (0,1)(0,1) — piste, josta laskeminen alkaa.

Tällä kaavalla on ominaisuus, jota siitä ei näe ja joka on turvallisuuden kannalta tärkeämpi kuin mikään vakio: se on täydellinen. Se toimii kaikilla syötteillä ilman erikoistapauksia tilanteille ”molemmat pisteet samat” tai ”tulos on neutraalialkio”. Vanhemmilla Weierstrassin käyrillä nämä erikoistapaukset ovat olemassa, ja jokainen niistä on ohjelmassa oma haaransa — haara, jonka suoritusaika on mitattavissa. Se, joka mittaa allekirjoituksen keston, saa tällaisissa menetelmissä tietoa salaisesta avaimesta.

Täydelliset kaavat tarkoittavat: aina sama laskureitti, aina sama aika, ei mitään mitattavaa.

7. Skalaarikertolasku — yksisuuntainen katu

n⋅Bn\cdot B tarkoittaa: pisteen BB lisääminen itseensä täsmälleen nn kertaa. Kun nn on 253-bittinen, se olisi järjettömän paljon työtä — siksi kahdennetaan:

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

ja näistä välituloksista kootaan haluttu nn. Noin 253 kahdennusta riittää mille tahansa nn:lle. Se on tie eteenpäin.

Taaksepäin tätä oikotietä ei ole. Luvun aa määrittäminen pisteestä AA tarkoittaa diskreetin logaritmin ongelman ratkaisemista.

(0,1) — neutraalialkioB2B3B4B5B6B
Edwardsin käyrä ja kantapisteen ensimmäiset monikerrat, laskettuna todellisella yhteenlaskusäännöllä. Reaalilukujen yli ne vaeltavat käyrää pitkin vielä näkyvästi järjestyneinä — reitin voisi jäljittää takaisin. Modulo p juuri tämä järjestys katoaa, ja siihen turvallisuus perustuu.

Todellisessa menetelmässä lasketaan modulo pp. Siellä ei ole ”vasenta” eikä ”oikeaa” eikä läheisyyttä: pisteistä 17 B17\,B ja 18 B18\,B tulee kaksi lukuparia, joilla ei ole mitään havaittavaa sukulaisuutta.

8. Allekirjoituspalvelun avainpari

Alussa on 32 satunnaista tavua, siemen (seed). Kaikki muu johdetaan siitä:

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

Ensimmäisestä puoliskosta syntyy salainen skalaari aa, ei kuitenkaan muuttumattomana. Kolme bittiä asetetaan tai nollataan — niin sanottu clamping:

  • alimmat kolme bittiä nollataan: aa:sta tulee siten kahdeksan monikerta. Syynä on käyrän kofaktori 8 — koko pisteryhmä on kahdeksan kertaa niin suuri kuin kertalukua ℓ\ell oleva aliryhmä. Kahdeksalla jaollinen aa päätyy taatusti oikeaan aliryhmään eikä paljasta mitään pienen kertaluvun pisteistä.
  • ylin bitti nollataan ja toiseksi ylin asetetaan: aa:lla on siten aina sama bittipituus. Lyhyempi aa vaatisi vähemmän kahdennuksia — ja jälleen suoritusajasta olisi luettavissa jotakin.

Julkinen avain on tämän jälkeen yksinkertaisesti

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

tallennettuna 32 tavuna: yy-koordinaatti ja ylimmässä bitissä xx:n etumerkki. Todentaja laskee xx:n itse takaisin käyrän yhtälöstä — molemmat ratkaisut eroavat vain etumerkiltään, ja kumpaa tarkoitetaan, kertoo tuo yksi bitti.

Tiivistearvon toista puoliskoa, etuliitettä, ei tarvita avaimeen. Se otetaan käyttöön seuraavassa luvussa.

9. Miksi satunnaisuus ei tässä ole satunnaista

Jokainen tämän rakenteen allekirjoitus tarvitsee kertakäyttöisen arvon rr, jota kutsutaan usein nonceksi. Se ei saa koskaan toistua: se, jolla on kaksi allekirjoitusta samalla rr:llä, voi laskea salaisen avaimen ulos koulualgebralla.

Juuri tähän todelliset järjestelmät ovat kaatuneet. Tunnetuin tapaus on erään pelikonsolin allekirjoitusten todennus, jonka valmistaja käytti vuonna 2010 aina samaa noncea — yksityinen avain oli siten julkisesti rekonstruoitavissa.

Ed25519 ratkaisee asian siten, että se ei käytä satunnaisuutta lainkaan:

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

Nonce riippuu salaisesta etuliitteestä ja viestistä. Siitä seuraa kaksi asiaa:

  • Kaksi eri arviota tuottavat ylivoimaisella todennäköisyydellä eri rr:t — toistotapausta ei synny.
  • Sama arvio tuottaa aina saman allekirjoituksen. Allekirjoitustapahtuma on siten jäljitettävissä, eikä huono satunnaislukugeneraattori palvelimella voi rikkoa mitään, koska sellaista ei tarvita.

Arviointiportaalille, joka tekee paljon allekirjoituksia päivässä, tämä ei ole akateeminen etu. Se on ero toteamusten ”virhe satunnaisuuden lähteessä olisi kohtalokas” ja ”ei ole satunnaisuuden lähdettä, joka voisi pettää” välillä.

10. Allekirjoittaminen

Kolme riviä, ei enempää:

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

Allekirjoitus on pari

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

32 tavua pisteelle RR ja 32 tavua luvulle SS — yhteensä 64 tavua.

Huomionarvoinen on toinen rivi: lukuun kk menevät RR, julkinen avain AA ja viesti. Se, että AA tiivistetään mukaan, ei ole koriste — se estää hyökkäykset, joissa allekirjoitus tulkitaan uudelleen toiselle avaimelle.

11. Todentaminen

Lukijan selain tuntee arvion mm, allekirjoituksen (R,S)(R,S) ja julkisen avaimen AA. Se laskee kk:n uudelleen ja tarkistaa yhden ainoan yhtälön:

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

Jos se pitää paikkansa, allekirjoitus on kelvollinen. RFC 8032 sallii lisäksi kofaktorilla kerrotun muodon 8S⋅B=8R+8k⋅A8S\cdot B = 8R + 8k\cdot A, joka käsittelee joitakin reunatapauksia sallivammin.

Yhdeltäkään palvelimelta ei kysytä mitään, minkään palvelun ei tarvitse olla käytettävissä. Julkinen avain riittää.

12. Miksi yhtälö menee tasan

Sijoittaminen riittää:

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.

Koko temppu on keskimmäisessä muunnoksessa: skalaarikertolasku sopii yhteen yhteenlaskun kanssa. Se, joka tuntee aa:n, voi laskea SS:n, joka toteuttaa yhtälön. Sen, joka ei tunne aa:ta, pitäisi löytää itse valitsemalleen kk:lle sopiva SS — ja se tarkoittaa diskreetin logaritmin ratkaisemista.

13. Täysin läpi laskettu miniesimerkki

Todellisilla luvuilla ei ole mitään laskettavaa — 253-bittisiä arvoja ei voi tarkistaa päässä. Siksi sama menetelmä pienenpienessä ryhmässä, jossa jokainen askel on seurattavissa taskulaskimella.

Askel 1: Ryhmä

Laskemme jakojäännöksillä modulo 2323 ja otamme g=2g = 2. Pätee

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

joten gg virittää kertalukua ℓ=11\ell = 11 olevan aliryhmän. Potenssit ovat:

nn1234567891011
gng^n248169181336121

gg ottaa kantapisteen BB roolin ja kertolasku pisteiden yhteenlaskun roolin. Skalaarit lasketaan modulo 1111, arvot modulo 2323.

Askel 2: Avainpari

Olkoon salainen a=6a = 6. Silloin

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

A=18A = 18 saa olla kaikkien tiedossa.

Askel 3: Nonce ja commitment

Olkoon etuliitteestä ja arviosta tuloksena r=4r = 4. Siitä:

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

Askel 4: Haaste

Olkoon tiiviste RR:stä, AA:sta ja arviosta

k=5.k = 5.

Askel 5: Allekirjoitus

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.

Allekirjoitus on pari (R,S)=(16, 1)(R,S) = (16,\,1).

Askel 6: Selain tarkistaa

Se laskee molemmat puolet. Vasen:

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

Oikea, kun 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}.

Molemmat puolet antavat 22:

Allekirjoitus kelvollinen\boxed{\text{Allekirjoitus kelvollinen}}

Askel 7: Joku muuttaa arviotekstiä

Teksti menee tiivisteeseen, joten haaste muuttuu — sanotaan arvoon k′=7k' = 7. Allekirjoitus pysyy muuttumattomana arvossa (16,1)(16,1), mutta oikea puoli ei. Kun 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
Allekirjoitus virheellinen\boxed{\text{Allekirjoitus virheellinen}}

Voimme poistaa arvion. Muuttaa emme voi sitä ilman, että se huomataan.

Rehellisyyshuomautus esimerkistä

Tässä laskettiin multiplikatiivisessa ryhmässä modulo 2323, ei käyrällä: gSg^S vastaa lauseketta S⋅BS\cdot B ja tulo R⋅AkR\cdot A^k pisteiden yhteenlaskua R+k⋅AR + k\cdot A. Rakenne on sama, ja juuri siitä on kyse. Erilaisia ovat suuruusluokat: ℓ=11\ell = 11 verrattuna arvoon ℓ≈2252\ell \approx 2^{252}, eikä siellä avainta löydä kokeilemalla yhtätoista vaihtoehtoa.

14. Mitä tapahtuu, jos joku muuttaa arviota

Oletetaan, että joku, jolla on pääsy tietokantaan — myös joku meiltä — muuttaa arviotekstiä tai yhtä sydämistä. Silloin tietue muuttuu ja sen myötä vähintään toinen payloadin tiivistearvoista h ja rh. Siten muuttuu mm, siten haaste kk ja siten todennusyhtälön oikea puoli. Vanha allekirjoitus ei enää sovi.

Ratkaiseva lause tähän: voimme poistaa arvion, mutta emme voi muuttaa sitä huomaamatta. McGesundissa sama tarkistus ajetaan lisäksi öisin palvelinpuolella koko aineistolle — arvio, joka ei sitä läpäise, ei enää vaikuta yrityksen keskiarvoon.

15. Miksi hyökkääjä epäonnistuu

Hän tuntee julkisen avaimen AA, kantapisteen BB, käyrän ja jokaisen tähän mennessä annetun allekirjoituksen. Häneltä puuttuu aa.

Paras tunnettu klassinen hyökkäys diskreetin logaritmin ongelmaan kertalukua ℓ\ell olevassa ryhmässä vaatii noin ℓ\sqrt{\ell} askelta. Arvolla ℓ≈2252\ell \approx 2^{252} se on noin

21262^{126}

operaatiota. Vertailun vuoksi: jopa kone, joka suoriutuu miljardista miljardista (101810^{18}) askeleesta sekunnissa, tarvitsisi siihen moninkertaisen ajan universumin ikään verrattuna.

Väärentäminen ilman avainta tarkoittaisi sopivan SS:n löytämistä itse valitulle kk:lle — sama tehtävä toisessa valeasussa.

16. Miksi Ed25519 eikä ECDSA

Molemmat perustuvat samaan ongelmaan. Ero on kaikessa siinä, mitä ympärillä tapahtuu:

ECDSA (NIST-käyrät)Ed25519
Noncevaatii tuoretta satunnaisuuttadeterministinen etuliitteestä ja viestistä
Kaavaterikoistapauksia, datasta riippuvia haarojatäydelliset, yksi laskureitti
Käyrän parametritvakioiden alkuperää ei ole koskaan täysin selitettyvalittu jäljitettävin perustein
Allekirjoituksen koko64–72 B, vaihteleva koodauskiinteä 64 B
Selaimessasaatavilla jo pitkäännatiivisti vuodesta 2023/2024, muutoin JS-kirjastona

Meille nonce oli ratkaiseva peruste. Arviointiportaali allekirjoittaa usein ja automatisoidusti; menetelmä, jossa yksi ainoa heikko satunnaisarvo paljastaa avaimen, on siihen väärä valinta.

17. Mitä Ed25519 ei tee

Ed25519 perustuu diskreettiin logaritmiin — ja juuri tämän ongelman riittävän suuri kvanttitietokone ratkaisee tehokkaasti Shorin algoritmilla. Onko sellaisia koneita ja milloin, on avoin kysymys. Arviolle, jonka on määrä olla vielä kymmenen vuoden kuluttua todennettavissa, se on siitä huolimatta kysymys, johon on vastattava tänään.

Siksi Ed25519-allekirjoituksen rinnalle voi tulla kvanttiresistentti leima:

Kumpikaan ei korvaa Ed25519:ää, vaan asettuu sen rinnalle. Jos toinen menetelmistä murtuu, toinen kantaa edelleen.

18. Kulku kuvana

ALLEKIRJOITUSPALVELU (MCGESUND)KÄVIJÄN SELAINyksityinen skalaari a + etuliite (siemenestä)payload m = {yritys, arvio, h, rh, iat}r = H(etuliite ‖ m) mod ℓR = r · Bk = H(R ‖ A ‖ m) mod ℓS = (r + k · a) mod ℓallekirjoitus σ = (R, S) + kidarvio + σ + julkinen avain Ak lasketaan uudelleen R:stä, A:sta ja m:stäS · B = R + k · A ?kelvollinenvirheellinen
Payloadista selaimen valintamerkkiin. Erotusviivan yläpuolella kaikki tapahtuu kerran lähetettäessä, sen alapuolella jokaisen lukijan kohdalla uudelleen — hänen laitteellaan, pelkän julkisen avaimen turvin.

19. Mitä McGesund tekee tällä käytännössä

Envelope. Jokainen allekirjoitettu arvio kantaa MCG1:-kuorta, jossa ovat muotoversio, payload ja Ed25519-allekirjoitus. Payloadin kid kertoo, mistä avaimesta on kyse; vastaavan julkisen avaimen palvelin luovuttaa pyynnöstä — se on julkinen, siinä ei ole mitään suojattavaa.

Todennus selaimessa. Chrome ja Firefox osaavat Ed25519:n natiivisti WebCrypto-rajapinnan kautta vuodesta 2023/2024. Safari ei — siellä kutsu heittää poikkeuksen sen sijaan, että se todentaisi. Siksi todennuskoodimme turvautuu puhtaaseen JavaScript-toteutukseen, joka ladataan vain sinne, missä sitä tarvitaan. Allekirjoituksen todennus menee siten läpi jokaisessa selaimessa, ja nimenomaan lukijan laitteella.

Aikaankkuri. Allekirjoitusavaimen sormenjälki ankkuroidaan OpenTimestampsin kautta Bitcoin-lohkoon. Siten voidaan osoittaa paitsi se, että allekirjoitus on aito, myös se, että avain oli olemassa jo tiettynä ajankohtana — ilman että kenenkään täytyisi uskoa meidän aikaleimaamme.

Sisällön sitominen. Payload kantaa kenttää rh, tiivistettä koko lähetystietueesta: teksti, sydämet, sijaintitila, käynnin syytä koskevat tiedot ja alkuperä. Ed25519-allekirjoitus sitoo siten paitsi tekstin, myös kaiken sen, mitä arvion vieressä näytetään.

20. Yksi lause mukaan otettavaksi

Ed25519 muuttaa salaisen luvun yhta¨lo¨ksi, jonkajokainen voi tarkistaa eika¨ kukaan keksia¨.\boxed{ \begin{array}{c} \text{Ed25519 muuttaa salaisen luvun yhtälöksi, jonka}\\ \text{jokainen voi tarkistaa eikä kukaan keksiä.} \end{array}}

Se, jolla on salainen skalaari, allekirjoittaa mikrosekunneissa. Sen, jolla sitä ei ole, olisi ratkaistava diskreetti logaritmi ryhmässä, jossa on noin 22522^{252} alkiota.

Arvion lukijalle se tarkoittaa yksinkertaisesti: hänen ei tarvitse uskoa meitä. Hän voi laskea itse.