Ed25519 mínithe go matamaiticiúil

1. Cad atá i gceist anseo

Ní réimse téacs i mbunachar sonraí é léirmheas ar McGesund a chaithfeá a chreidiúint. Nuair a sheoltar isteach é sínítear go digiteach é, agus is féidir le gach cuairteoir an síniú sin a athríomh níos déanaí ina bhrabhsálaí féin.

Úsáidimid Ed25519 don síniú seo. Murab ionann agus FALCON agus ML-DSA, ar féidir iad a chur síos taobh leis mar stampaí breise, níl Ed25519 roghnach: iompraíonn gach léirmheas sínithe é, is cuma cén plean ná cén bealach aighneachta.

Rud tábhachtach ar dtús:

Ní criptiú é Ed25519. Is é is aidhm dó go léifear téacs an léirmheasa. Ní rúndacht a chruthaíonn an síniú ach bunús agus sláine.

---

2. Cad go díreach a shínítear

Ní hé an téacs leanúnach a shínítear ach oibiacht sonraí dhlúth a dhaingníonn an téacs agus gach a ghabhann leis gan athbhrí:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<Aitheantas an ghnólachta>",
  "c":   "<Aitheantas an léirmheasa>",
  "h":   "<SHA-256 de théacs an léirmheasa>",
  "rh":  "<SHA-256 den taifead aighneachta iomlán>",
  "rv":  1,
  "qh":  "<SHA-256 den chlúdach QR, léirmheasanna QR amháin>",
  "kid": "<Aitheantas na heochrach>",
  "iat": 1757203200
}

Ionchódaítear an oibiacht seo mar CBOR. Is í an tsraith beart sin — agus ní an léiriú néata thuas — ár dteachtaireacht $m$. Taistealaíonn an síniú agus an teachtaireacht le chéile in aon chlúdach amháin:

Is é an $3$ leagan na formáide. Níl a thuilleadh ann — go háirithe níl aon síniú iar-chandamach ann: má tá a leithéid ann, luíonn sé taobh leis an taifead agus ní istigh sa chlúdach.

---

3. Cad ba cheart don síniú a chruthú

Léitheoir a thagann ar phróifíl gnólachta, bíonn dhá cheist os a chomhair:

1. An as córas McGesund a tháinig an léirmheas seo i ndáiríre?
2. Ar athraíodh ina dhiaidh sin é?

Chuige sin tá péire eochracha ann:

• eochair phríobháideach — fanann sí sa tseirbhís sínithe
• eochair phoiblí — is ceadmhach do chách í a bheith aige; seoltar chuici trí aitheantas na heochrach (kid) sa phálasta

Sínítear leis an eochair phríobháideach. Fíoraítear leis an gceann poiblí — agus sin i mbrabhsálaí an léitheora, ní ar ár bhfreastalaí féin. Sin é an pointe: ní fíorú a bheadh i seiceáil a dhéanaimis féin agus a dtugaimis a toradh le fios, ach maíomh.

---

4. Cén fáth cuar éilipseach?

Teastaíonn ríomh ó gach síniú atá éasca i dtreo amháin agus dodhéanta go praiticiúil sa treo eile. I gcás Ed25519 is é sin an t-iolrú scálach ar chuar éilipseach:

Ní chosnaíonn sé ach micrishoicindí an pointe poiblí $A$ a ríomh as an uimhir rúnda $a$. Ach $a$ a bhaint amach as $A$ arís, sin fadhb an logartaim dhiscréidigh — níl aon mhodh ar eolas a chríochnaíonn í ag an méid seo laistigh de thréimhsí daonna.

Is é an bua praiticiúil i gcomparáid le scéimeanna níos sine ar nós RSA ná an mhéid:

Agus leibhéal slándála inchomparáide. Fiú le milliúin léirmheas, ní méid é 64 beart an léirmheas ar gá machnamh a dhéanamh air.

---

5. An cuar edwards25519

Ríomhtar módúlas uimhir phríomha:

Sin bunús an ainm. Is cuar Edwards casta é an cuar:

Is éard is "pointe" ann ná péire uimhreacha $(x,y)$ as $\{0,\dots,p-1\}$ a shásaíonn an chothromóid seo. Níl aon chuar le feiceáil — is áis léirithe os cionn na n-uimhreacha réadacha í an líníocht sa chéad chuid eile, agus ní pictiúr den spás ríomha iarbhír.

Tagann dhá mhéid eile leis:

• bunphointe $B$ atá socraithe go daingean,
• ord $\ell$ an fhoghrúpa a ghineann $B$:

Is uimhir phríomha é $\ell$. Ciallaíonn sin: má shuimítear $B$ leis féin arís agus arís eile, gabhtar trí $\ell$ pointe éagsúla go beacht agus tagtar ar ais go dtí an tús ansin. Dá bhrí sin ritheann gach ríomh le scálaigh módúlas $\ell$, agus gach ríomh le comhordanáidí módúlas $p$. Is é an dá uimhir sin a mheascadh suas an botún clasaiceach a dhéanann tosaitheoirí.

---

6. Pointí a shuimiú

Cuirtear dhá phointe le chéile de réir foirmle daingne chun tríú pointe a fháil:

Is é $(0,1)$ an dúil neodrach — an pointe ag a dtosaíonn an ríomh.

Tá airí ag an bhfoirmle seo nach léir uirthi agus atá níos tábhachtaí don tslándáil ná aon tairiseach: tá sí iomlán. Oibríonn sí do gach ionchur, gan cásanna speisialta do "tá an dá phointe mar an gcéanna" ná "is é an dúil neodrach an toradh". Bíonn na cásanna speisialta sin ann ar na cuair Weierstrass is sine, agus is brainse sa chlár gach ceann acu — brainse ar féidir a rith-am a thomhas. An té a thomhaiseann cé chomh fada is a mhaireann síniú, foghlaimíonn sé rud éigin faoin eochair rúnda i gcás scéimeanna den sórt sin.

Ciallaíonn foirmlí iomlána: an cosán ríofa céanna i gcónaí, an t-am céanna i gcónaí, faic le tomhas.

---

7. Iolrú scálach — an bóthar aontreo

Is é is brí le $n\cdot B$ ná $B$ a shuimiú leis féin $n$ uair go díreach. Le $n$ a bhfuil 253 giotán ann, ba obair as cuimse gan chiall é sin — mar sin déantar dúbailt:

agus cuirtear an $n$ atá uainn le chéile as na torthaí idirmheánacha sin. Is leor timpeall 253 dúbailt do gach $n$. Sin é an bealach ar aghaidh.

Níl an t-aicearra sin ann ar an mbealach ar ais. An uimhir $a$ a chinneadh as an bpointe $A$, is ionann sin agus fadhb an logartaim dhiscréidigh a réiteach.

Sa scéim iarbhír ríomhtar módúlas $p$. Níl aon "chlé", aon "dheis" ná aon ghaireacht ann: as $17\,B$ agus $18\,B$ tagann dhá phéire uimhreacha gan aon ghaol inaitheanta eatarthu.

---

8. Péire eochracha na seirbhíse sínithe

Ag an tús tá 32 beart randamacha, an síol. Díorthaítear gach a leanann as sin:

Eascraíonn an scálach rúnda $a$ as an gcéad leath, ach ní gan athrú. Socraítear nó glantar trí ghiotán — an rud a dtugtar clampáil air:

• socraítear na trí ghiotán is ísle ar nialas: éiríonn $a$ mar iolraí de 8 dá bharr. Is é an chúis leis sin ná comhfhachtóir 8 an chuair — tá grúpa iomlán na bpointí ocht n-uaire chomh mór le foghrúpa an oird $\ell$. Tagann $a$ atá inroinnte ar 8 i dtír sa cheart-fhoghrúpa go cinnte agus ní sceitheann sé faic faoi phointí de bheagord.
• glantar an giotán is airde agus socraítear an ceann ina dhiaidh: bíonn an fad giotán céanna ag $a$ i gcónaí dá bharr. Theastódh níos lú dúbailtí ó $a$ níos giorra — agus arís bheadh rud éigin le léamh as an rith-am.

Níl san eochair phoiblí ansin ach

stóráilte mar 32 beart: an chomhordanáid $y$, agus sa ghiotán is airde comhartha $x$. Ríomhann an fíoraitheoir féin $x$ ar ais as cothromóid an chuair — níl idirdhealú idir an dá réiteach ach sa chomhartha, agus deir an t-aon ghiotán sin cé acu atá i gceist.

Ní theastaíonn an dara leath den haisluach, an réimír, don eochair. Tagann sí i bhfeidhm sa chéad chuid eile.

---

9. Cén fáth nach randamacht í an randamacht anseo

Teastaíonn luach aonuaire $r$, ar a dtugtar nonce go minic, ó gach síniú den déanamh seo. Ní ceadmhach dó athrá a dhéanamh riamh: an té a bhfuil dhá shíniú aige leis an $r$ céanna, is féidir leis an eochair rúnda a ríomh amach le hailgéabar scoile.

Is air sin go díreach a theip ar chórais fhíordhearfacha. Is é an cás is cáiliúla ná fíorú sínithe consóil chluichí ar úsáid a monaróir an nonce céanna i gcónaí in 2010 — bhí an eochair phríobháideach in-athchruthaithe go poiblí dá bharr.

Réitíonn Ed25519 é sin trí gan aon randamacht a úsáid ar chor ar bith:

Braitheann an nonce ar an réimír rúnda agus ar an teachtaireacht. Leanann dhá rud as sin:

• Tugann dhá léirmheas éagsúla $r$ éagsúla le dóchúlacht as cuimse — ní tharlaíonn cás an athráite.
• Tugann an léirmheas céanna an síniú céanna i gcónaí. Is féidir gníomh sínithe a rianú dá bharr, agus ní féidir le drochghineadóir randamachta ar an bhfreastalaí aon dochar a dhéanamh, mar ní theastaíonn a leithéid ar chor ar bith.

I gcás tairseach léirmheasanna a bhfuil go leor sínithe in aghaidh an lae aici, ní bua acadúil é sin. Is é an difear é idir "bheadh botún sa fhoinse randamachta marfach" agus "níl aon fhoinse randamachta ann a d'fhéadfadh cliseadh".

---

10. Síniú

Trí líne, níl ann ach sin:

Is é an péire an síniú

32 beart don phointe $R$, 32 beart don uimhir $S$ — 64 beart le chéile.

Is fiú aird a thabhairt ar an dara líne: téann $R$, an eochair phoiblí $A$ agus an teachtaireacht isteach in $k$. Ní maisiúchán é go ndéantar $A$ a haiseáil freisin — cuireann sé cosc ar ionsaithe a athmhíníonn síniú mar shíniú ar eochair eile.

---

11. Fíorú

Tá a fhios ag brabhsálaí an léitheora: an léirmheas $m$, an síniú $(R,S)$ agus an eochair phoiblí $A$. Ríomhann sé $k$ as an nua agus seiceálann sé aon chothromóid amháin:

Má tá sí fíor, tá an síniú bailí. Ceadaíonn RFC 8032 an leagan iolraithe faoin gcomhfhachtóir freisin, $8S\cdot B = 8R + 8k\cdot A$, a láimhseálann roinnt corrchásanna go flaithiúlaí.

Ní chuirtear ceist ar aon fhreastalaí, ní gá d'aon seirbhís a bheith ar fáil. Is leor an eochair phoiblí.

---

12. Cén fáth a n-oibríonn an chothromóid

Is leor na luachanna a chur isteach:

Tá an cleas ar fad san athrú lárnach: réitíonn an t-iolrú scálach leis an suimiú. An té a bhfuil eolas aige ar $a$, is féidir leis $S$ a ríomh a shásaíonn an chothromóid. An té nach bhfuil eolas aige ar $a$, chaithfeadh sé $S$ oiriúnach a aimsiú do $k$ a roghnódh sé féin — agus ciallaíonn sin an logartam discréideach a réiteach.

---

13. Mionsampla arna ríomh ina iomláine

Leis na fíoruimhreacha níl aon ní le hathríomh — ní féidir luachanna 253 giotán a sheiceáil i do cheann. Mar sin tá an scéim chéanna anseo i ngrúpa an-bheag ar féidir gach céim de a leanúint le háireamhán.

Céim 1: An grúpa

Ríomhaimid leis na fuílligh módúlas $23$ agus glacaimid $g = 2$. Tá

agus gineann $g$ dá bhrí sin foghrúpa den ord $\ell = 11$. Seo iad na cumhachtaí:

Glacann $g$ ról an bhunphointe $B$, agus glacann an t-iolrú ról an tsuimithe pointí. Ríomhtar scálaigh módúlas $11$, luachanna módúlas $23$.

Céim 2: An péire eochracha

Bíodh $a = 6$ rúnda. Ansin tá

Is ceadmhach do chách $A = 18$ a bheith ar eolas aige.

Céim 3: Nonce agus gealltanas

As an réimír agus as an léirmheas eascraíodh $r = 4$. As sin:

Céim 4: An dúshlán

Tugadh an hais ar $R$, $A$ agus an léirmheas

Céim 5: An síniú

Is é an péire $(R,S) = (16,\,1)$ an síniú.

Céim 6: Fíoraíonn an brabhsálaí

Ríomhann sé an dá thaobh. Ar chlé:

Ar dheis, le $18^5 \equiv 3 \pmod{23}$:

Tugann an dá thaobh $2$:

Céim 7: Athraíonn duine téacs an léirmheasa

Téann an téacs isteach sa hais, mar sin athraíonn an dúshlán — abraimis go $k' = 7$. Fanann an síniú gan athrú ag $(16,1)$, ach ní fhanann an taobh deas. Le $18^7 \equiv 6 \pmod{23}$:

Is féidir linn léirmheas a scriosadh. Ní féidir linn é a athrú gan é a bheith le tabhairt faoi deara.

Nóta ionracais faoin sampla

Ríomhadh anseo sa ghrúpa iolraitheach módúlas $23$, ní ar chuar: seasann $g^S$ do $S\cdot B$, agus seasann an t-iolrach $R\cdot A^k$ do shuimiú na bpointí $R + k\cdot A$. Is í an struchtúr an rud céanna, agus is é sin an pointe. Is iad na hoird mhéide atá éagsúil: $\ell = 11$ i gcomparáid le $\ell \approx 2^{252}$, agus ansin ní féidir an eochair a aimsiú trí na haon fhéidearthacht déag a thriail.

---

14. Cad a tharlaíonn má athraíonn duine an léirmheas

Cuir i gcás go n-athraíonn duine a bhfuil rochtain aige ar an mbunachar sonraí — duine againne san áireamh — téacs an léirmheasa nó ceann de na croíthe. Athraíonn an taifead ansin agus dá bharr sin ceann amháin ar a laghad den dá haisluach h agus rh sa phálasta. Athraíonn $m$ dá bharr, agus an dúshlán $k$ dá bharr, agus taobh deas na cothromóide fíoraithe dá bharr. Ní oireann an seansíniú a thuilleadh.

An abairt chinntitheach faoi sin: is féidir linn léirmheas a scriosadh, ach ní féidir linn é a athrú gan fógra. Ag McGesund ritheann an fíorú céanna gach oíche ar an taobh freastalaí thar an stór iomlán freisin — léirmheas nach n-éiríonn leis, ní théann sé isteach i meán an ghnólachta a thuilleadh.

---

15. Cén fáth a dteipeann ar ionsaitheoir

Tá an eochair phoiblí $A$, an bunphointe $B$, an cuar agus gach síniú a eisíodh go dtí seo ar eolas aige. Is é $a$ atá in easnamh air.

Teastaíonn timpeall $\sqrt{\ell}$ céim ón ionsaí clasaiceach is fearr atá ar eolas ar fhadhb an logartaim dhiscréidigh i ngrúpa den ord $\ell$. Le $\ell \approx 2^{252}$ is ionann sin agus timpeall

oibríocht. Mar chomparáid: fiú meaisín a dhéanann míle milliún milliún ($10^{18}$) céim in aghaidh an tsoicind, theastódh iolraí d'aois na cruinne uaidh chuige sin.

Bheadh brionnú gan an eochair ionann agus $S$ oiriúnach a aimsiú do $k$ a roghnófaí féin — an tasc céanna faoi bhréagriocht eile.

---

16. Cén fáth Ed25519 seachas ECDSA

Tá an dá cheann bunaithe ar an bhfadhb chéanna. Tá an difear i ngach a tharlaíonn ina timpeall:

Ba é an nonce an argóint chinntitheach dúinne. Síníonn tairseach léirmheasanna go minic agus go huathoibríoch; is é an rogha mhícheart chuige sin scéim ina sceitheann aon luach randamach lag amháin an eochair.

---

17. Rud nach ndéanann Ed25519

Tá Ed25519 bunaithe ar an logartam discréideach — agus is í an fhadhb sin go díreach a réitíonn ríomhaire candamach mór go leor go héifeachtach le halgartam Shor. Tá sé oscailte an mbeidh a leithéid de mheaisíní ann agus cathain. I gcás léirmheasa ar cheart a bheith infhíoraithe fós i gceann deich mbliana, is ceist í sin mar sin féin a chaithfear a fhreagairt inniu.

Dá bhrí sin is féidir stampa candam-fhriotaíoch a chur taobh leis an síniú Ed25519:

• FALCON (FN-DSA) — sínithe dlútha as laitísí NTRU
• ML-DSA-87 (FIPS 204) — an caighdeán NIST atá críochnaithe

Ní chuireann ceachtar acu Ed25519 as an áireamh, luíonn siad taobh leis. Má bhristear ceann de na scéimeanna, iompraíonn an ceann eile ar aghaidh.

---

18. An próiseas i bpictiúr

---

19. Cad a dhéanann McGesund leis go praiticiúil

An clúdach. Iompraíonn gach léirmheas sínithe clúdach MCG1: le leagan na formáide, an pálasta agus an síniú Ed25519. Deir an kid sa phálasta cén eochair atá i gceist; soláthraíonn an freastalaí an eochair phoiblí a bhaineann léi ar iarratas — tá sí poiblí, níl faic le cosaint uirthi.

An fíorú sa bhrabhsálaí. Tá Ed25519 ar chumas Chrome agus Firefox ó dhúchas trí chomhéadan WebCrypto ó 2023/2024. Níl ag Safari — teilgeann an glao ansin in ionad fíorú a dhéanamh. Dá bhrí sin titeann ár gcód fíoraithe siar ar fhorfheidhmiú JavaScript amháin nach lódáiltear ach san áit a dteastaíonn sé. Ritheann fíorú an tsínithe dá bharr i ngach brabhsálaí, agus sin ar ghléas an léitheora.

An t-ancaire ama. Ancairítear méarlorg na heochrach sínithe i mbloc Bitcoin trí OpenTimestamps. Is féidir a chruthú leis sin ní hamháin go bhfuil an síniú fíor ach freisin go raibh an eochair ann cheana ag am ar leith — gan gá le duine ar bith ár stampa ama a chreidiúint.

An ceangal leis an ábhar. Iompraíonn an pálasta rh, an hais ar an taifead aighneachta iomlán: téacs, croíthe, geo-stádas, sonraí faoin ócáid agus foinse. Ceanglaíonn an síniú Ed25519 dá bharr sin ní hamháin an téacs ach gach a thaispeántar in aice leis an léirmheas.

---

20. Abairt le tabhairt leat

An té a bhfuil an scálach rúnda aige, síníonn sé i micrishoicindí. An té nach bhfuil sé aige, chaithfeadh sé logartam discréideach a réiteach i ngrúpa a bhfuil timpeall $2^{252}$ dúil ann.

Do léitheoir léirmheasa ciallaíonn sin go simplí: ní gá dó sinne a chreidiúint. Is féidir leis é a ríomh.