Az Ed25519 matematikai magyarázata

1. Miről van szó

A McGesundnál egy értékelés nem pusztán egy szövegmező az adatbázisban, amelynek hinni kell. Beküldéskor digitálisan aláírjuk, és ezt az aláírást később bármelyik látogató újraszámolhatja a saját böngészőjében.

Ehhez az aláíráshoz az Ed25519 eljárást használjuk. A FALCON-nal és az ML-DSA-val ellentétben, amelyek további bélyegzőként helyezhetők mellé, az Ed25519 nem opció: minden aláírt értékelés hordozza, függetlenül a csomagtól és a beküldés módjától.

Fontos előrebocsátani:

Az Ed25519 nem titkosítás. Az értékelés szövegét éppen hogy el kell tudni olvasni. Az aláírás nem a titkosságot bizonyítja, hanem az eredetet és a sértetlenséget.

---

2. Mit írunk alá pontosan

Nem a folyószöveget írjuk alá, hanem egy tömör adatobjektumot, amely a szöveget és minden továbbit egyértelműen rögzít:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<cégazonosító>",
  "c":   "<értékelésazonosító>",
  "h":   "<az értékelés szövegének SHA-256 hasítóértéke>",
  "rh":  "<a teljes beküldött adatrekord SHA-256 hasítóértéke>",
  "rv":  1,
  "qh":  "<a QR-envelope SHA-256 hasítóértéke, csak QR-értékeléseknél>",
  "kid": "<kulcsazonosító>",
  "iat": 1757203200
}

Ezt az objektumot CBOR formátumba kódoljuk. Ez a bájtsorozat — nem a fenti szép megjelenítése — a mi $m$ üzenetünk. Az aláírás és az üzenet együtt kerül egy borítékba:

A $3$ a formátum verziószáma. Több nincs benne — különösen nincs benne poszt-kvantum aláírás: az, ha van ilyen, az adatrekord mellett található, nem a borítékban.

---

3. Mit kell teljesítenie az aláírásnak

Az olvasó, aki egy cégprofilra érkezik, két kérdés előtt áll:

1. Valóban a McGesund rendszeréből származik ez az értékelés?
2. Módosították-e utólag?

Ehhez egy kulcspár tartozik:

• egy titkos kulcs — az aláíró szolgáltatásban marad
• egy nyilvános kulcs — bárkinél lehet, a payloadban lévő kulcsazonosítón (kid) keresztül címezhető

Az aláírás a titkos kulccsal készül. Az ellenőrzés a nyilvánossal — méghozzá az olvasó böngészőjében, nem a mi szerverünkön. Éppen ez a lényeg: az az ellenőrzés, amelyet mi magunk végzünk el, és amelynek eredményét közöljük, nem ellenőrzés volna, hanem állítás.

---

4. Miért elliptikus görbe?

Minden aláíráshoz olyan számítás kell, amely az egyik irányban könnyű, a másikban gyakorlatilag lehetetlen. Az Ed25519 esetében ez a skalárszorzás egy elliptikus görbén:

A titkos $a$ számból kiszámolni az $A$ nyilvános pontot mikromásodpercekbe kerül. Az $A$-ból visszakövetkeztetni $a$-ra a diszkrét logaritmus problémája — erre nem ismert olyan eljárás, amely ekkora méretnél emberi időtávon belül végezne.

Az RSA-hoz hasonló régebbi eljárásokkal szembeni gyakorlati nyereség a méret:

Összehasonlítható biztonsági szint mellett. Az értékelésenkénti 64 bájt még milliónyi értékelés esetén sem olyan méret, amelyen gondolkodni kellene.

---

5. Az edwards25519 görbe

A számítás egy prímszám szerinti maradékokkal történik:

Innen a név. A görbe egy csavart Edwards-görbe:

Egy „pont" egy $(x,y)$ számpár a $\{0,\dots,p-1\}$ halmazból, amely kielégíti ezt az egyenletet. Nincs látható görbe — a következő szakasz rajza szemléltetés a valós számok fölött, nem a tényleges számítási tér képe.

Két mennyiség jön még hozzá:

• egy rögzített megállapodás szerinti bázispont, $B$,
• a $B$ által generált részcsoport rendje, $\ell$:

Az $\ell$ prím. Ez azt jelenti: ha $B$-t újra és újra önmagához adjuk, pontosan $\ell$ különböző ponton haladunk végig, majd ismét a kiindulóponton kötünk ki. Ezért a skalárokkal végzett minden számítás modulo $\ell$, a koordinátákkal végzett minden számítás pedig modulo $p$ történik. E két szám összekeverése a klasszikus kezdő hiba.

---

6. Pontok összeadása

Két pontot egy rögzített képlet szerint számolunk össze egy harmadikká:

A semleges elem a $(0,1)$ — az a pont, ahol a számolás kezdődik.

Ennek a képletnek van egy olyan tulajdonsága, amely nem látszik rajta, és amely a biztonság szempontjából minden konstansnál fontosabb: teljes. Minden bemenetre működik, különleges esetek nélkül, tehát nincs külön ág arra, hogy „a két pont azonos" vagy „az eredmény a semleges elem". A régebbi Weierstrass-görbéknél léteznek ezek a különleges esetek, és mindegyikük egy-egy elágazás a programban — olyan elágazás, amelynek futásideje megmérhető. Aki megméri, mennyi ideig tart egy aláírás, ilyen eljárásoknál megtud valamit a titkos kulcsról.

A teljes képletek azt jelentik: mindig ugyanaz a számítási út, mindig ugyanannyi idő, nincs mit mérni.

---

7. Skalárszorzás — az egyirányú utca

Az $n\cdot B$ azt jelenti: $B$-t pontosan $n$-szer önmagához adni. Egy 253 bites $n$ esetén ez értelmetlenül sok munka lenne — ezért duplázunk:

és ezekből a részeredményekből állítjuk össze a kívánt $n$-t. Nagyjából 253 duplázás elegendő bármely $n$-hez. Ez az előrefelé vezető út.

Visszafelé nincs ilyen rövidítés. Az $A$ pontból meghatározni az $a$ számot annyit tesz, mint megoldani a diszkrét logaritmus problémáját.

A valódi eljárásban modulo $p$ számolunk. Ott nincs „bal", nincs „jobb" és nincs közelség: a $17\,B$-ből és a $18\,B$-ből két olyan számpár lesz, amelyek között semmiféle felismerhető rokonság nincs.

---

8. Az aláíró szolgáltatás kulcspárja

Az elején 32 véletlen bájt áll, a seed. Minden továbbit ebből vezetünk le:

Az első félből keletkezik az $a$ titkos skalár, de nem változatlanul. Három bitet beállítunk, illetve törlünk — ez az úgynevezett clamping:

• a legalsó három bitet nullára állítjuk: ezáltal $a$ a 8 többszöröse lesz. Az ok a görbe 8-as kofaktora — a teljes pontcsoport nyolcszor akkora, mint az $\ell$ rendű részcsoport. A 8-cal osztható $a$ garantáltan a megfelelő részcsoportba kerül, és nem árul el semmit a kis rendű pontokról.
• a legfelső bitet töröljük, az alatta lévőt beállítjuk: ezzel $a$ bithossza mindig azonos. Egy rövidebb $a$ kevesebb duplázást igényelne — és megint le lehetne olvasni valamit a futásidőből.

A nyilvános kulcs ezután egyszerűen

32 bájton tárolva: az $y$-koordináta, a legmagasabb bitben pedig az $x$ előjele. Az $x$-et az ellenőrző maga számolja vissza a görbeegyenletből — a két megoldás csak előjelben tér el, és hogy melyikről van szó, azt ez az egyetlen bit mondja meg.

A hasítóérték második fele, a prefix, nem kell a kulcshoz. A következő szakaszban kerül sorra.

---

9. Miért nem véletlen itt a véletlen

Minden ilyen felépítésű aláíráshoz kell egy egyszer használatos érték, $r$, amelyet gyakran nonce-nak neveznek. Soha nem ismétlődhet: akinek két aláírása van ugyanazzal az $r$-rel, az középiskolás algebrával kiszámolhatja a titkos kulcsot.

Pontosan ezen buktak el valós rendszerek. A legismertebb eset egy játékkonzol aláírás-ellenőrzése, amelynek gyártója 2010-ben mindig ugyanazt a nonce-ot használta — a titkos kulcs ezzel nyilvánosan rekonstruálható volt.

Az Ed25519 úgy oldja meg ezt, hogy egyáltalán nem használ véletlent:

A nonce a titkos prefixtől és az üzenettől függ. Ebből kettő következik:

• Két különböző értékelés elsöprő valószínűséggel különböző $r$-t ad — az ismétlődés esete nem áll elő.
• Ugyanaz az értékelés mindig ugyanazt az aláírást adja. Egy aláírási művelet így utólag reprodukálható, és egy rossz véletlenszám-generátor a szerveren nem tehet kárt, mert nincs is rá szükség.

Egy naponta sok aláírást előállító értékelőportál esetében ez nem elméleti előny. Ez a különbség aközött, hogy „a véletlenforrás hibája végzetes volna" és aközött, hogy „nincs olyan véletlenforrás, amely kieshetne".

---

10. Aláírás

Három sor, nem több:

Az aláírás a pár

32 bájt az $R$ pontnak, 32 bájt az $S$ számnak — együtt 64 bájt.

Figyelemre méltó a második sor: a $k$-ba beleszámít $R$, az $A$ nyilvános kulcs és az üzenet. Az, hogy $A$-t is hasheljük, nem mellékes díszítés — megakadályozza azokat a támadásokat, amelyekben egy aláírást egy másik kulcsra értelmeznek át.

---

11. Ellenőrzés

Az olvasó böngészője ismeri: az $m$ értékelést, az $(R,S)$ aláírást és az $A$ nyilvános kulcsot. Újraszámolja a $k$-t, és egyetlen egyenletet ellenőriz:

Ha teljesül, az aláírás érvényes. Az RFC 8032 megengedi ezenkívül a kofaktorral szorzott változatot is, $8S\cdot B = 8R + 8k\cdot A$, amely néhány határesetet nagyvonalúbban kezel.

Semmilyen szervert nem kérdezünk meg, semmilyen szolgáltatásnak nem kell elérhetőnek lennie. A nyilvános kulcs elegendő.

---

12. Miért jön ki az egyenlet

Elég behelyettesíteni:

Az egész trükk a középső átalakításban rejlik: a skalárszorzás összefér az összeadással. Aki ismeri $a$-t, ki tud számolni olyan $S$-t, amely kielégíti az egyenletet. Aki nem ismeri $a$-t, annak egy maga választotta $k$-hoz kellene megfelelő $S$-t találnia — ez pedig azt jelenti, hogy meg kell oldania a diszkrét logaritmust.

---

13. Egy teljesen végigszámolt minipélda

A valódi számokkal nincs mit utánaszámolni — a 253 bites értékek fejben nem ellenőrizhetők. Ezért ugyanaz az eljárás egy parányi csoportban, ahol minden lépés zsebszámológéppel követhető.

1. lépés: A csoport

A $23$ szerinti maradékokkal számolunk, és $g = 2$-t választunk. Fennáll, hogy

tehát $g$ egy $\ell = 11$ rendű részcsoportot generál. A hatványok a következők:

A $g$ veszi át a $B$ bázispont szerepét, a szorzás pedig a pontösszeadásét. A skalárok modulo $11$, az értékek modulo $23$ számolódnak.

2. lépés: A kulcspár

Legyen a titok $a = 6$. Ekkor

Az $A = 18$ bárki tudhatja.

3. lépés: Nonce és commitment

A prefixből és az értékelésből adódjon $r = 4$. Ebből:

4. lépés: A challenge

Az $R$-re, $A$-ra és az értékelésre vett hasítóérték adjon

5. lépés: Az aláírás

Az aláírás a $(R,S) = (16,\,1)$ pár.

6. lépés: A böngésző ellenőriz

Mindkét oldalt kiszámolja. Bal oldal:

Jobb oldal, $18^5 \equiv 3 \pmod{23}$ felhasználásával:

Mindkét oldal $2$-t ad:

7. lépés: Valaki megváltoztatja az értékelés szövegét

A szöveg bekerül a hasításba, tehát megváltozik a challenge — mondjuk $k' = 7$ lesz. Az aláírás változatlanul $(16,1)$ marad, a jobb oldal viszont nem. A $18^7 \equiv 6 \pmod{23}$ felhasználásával:

Egy értékelést törölni tudunk. Megváltoztatni viszont nem tudjuk anélkül, hogy az feltűnne.

Őszinte megjegyzés a példához

Itt a $23$ szerinti multiplikatív csoportban számoltunk, nem görbén: a $g^S$ áll az $S\cdot B$ helyett, az $R\cdot A^k$ szorzat pedig az $R + k\cdot A$ pontösszeadás helyett. A struktúra ugyanaz, és éppen erről van szó. A nagyságrendek különböznek: $\ell = 11$ szemben azzal, hogy $\ell \approx 2^{252}$, és ott a kulcs nem található meg tizenegy lehetőség végigpróbálásával.

---

14. Mi történik, ha valaki megváltoztatja az értékelést

Tegyük fel, hogy valaki adatbázis-hozzáféréssel — akár nálunk valaki — megváltoztatja az értékelés szövegét vagy az egyik szívet. Ekkor megváltozik az adatrekord, és ezzel a payloadban lévő h és rh hasítóértékek közül legalább az egyik. Ezzel megváltozik $m$, ezzel a $k$ challenge, ezzel az ellenőrző egyenlet jobb oldala. A régi aláírás már nem illeszkedik.

A döntő mondat ehhez: egy értékelést törölni tudunk, de észrevétlenül megváltoztatni nem. A McGesundnál ugyanez az ellenőrzés éjszakánként a szerveroldalon is végigfut az állományon — az az értékelés, amely nem felel meg neki, többé nem számít bele a cég átlagába.

---

15. Miért bukik el a támadó

Ismeri az $A$ nyilvános kulcsot, a $B$ bázispontot, a görbét és minden eddig kiállított aláírást. Ami hiányzik neki, az az $a$.

A diszkrét logaritmus problémája elleni legjobb ismert klasszikus támadás egy $\ell$ rendű csoportban körülbelül $\sqrt{\ell}$ lépést igényel. $\ell \approx 2^{252}$ esetén ez nagyjából

művelet. Összehasonlításképpen: még egy olyan gépnek is, amely másodpercenként milliárdszor milliárd ($10^{18}$) lépést hajt végre, az univerzum korának többszörösére volna szüksége hozzá.

Hamisítani a kulcs nélkül azt jelentené, hogy egy maga választotta $k$-hoz kell megfelelő $S$-t találni — ugyanaz a feladat más álruhában.

---

16. Miért az Ed25519 és nem az ECDSA

Mindkettő ugyanazon a problémán alapul. A különbség mindabban rejlik, ami körülötte történik:

Számunkra a nonce volt a döntő érv. Egy értékelőportál gyakran és automatizáltan ír alá; az az eljárás, amelynél egyetlen gyenge véletlen érték kiadja a kulcsot, erre rossz választás.

---

17. Amit az Ed25519 nem nyújt

Az Ed25519 a diszkrét logaritmuson alapul — és pontosan ezt a problémát oldja meg hatékonyan egy kellően nagy kvantumszámítógép Shor algoritmusával. Hogy léteznek-e és mikor ilyen gépek, nyitott kérdés. Egy olyan értékelésnél viszont, amelynek tíz év múlva is ellenőrizhetőnek kell lennie, ez mégis olyan kérdés, amelyre ma kell választ adni.

Ezért az Ed25519-aláírás mellé kvantumrezisztens bélyegző kerülhet:

• FALCON (FN-DSA) — tömör aláírások NTRU-rácsokból
• ML-DSA-87 (FIPS 204) — a lezárt NIST-szabvány

Egyik sem váltja ki az Ed25519-et, hanem mellé kerül. Ha az egyik eljárás megtörik, a másik tovább visz.

---

18. A folyamat képben

---

19. Mit kezd ezzel konkrétan a McGesund

A boríték. Minden aláírt értékelés hordoz egy MCG1: borítékot a formátumverzióval, a payloaddal és az Ed25519-aláírással. A payloadban lévő kid megmondja, melyik kulcsról van szó; a hozzá tartozó nyilvános kulcsot a szerver kérésre kiadja — nyilvános, nincs rajta mit védeni.

Az ellenőrzés a böngészőben. A Chrome és a Firefox 2023/2024 óta natívan tudja az Ed25519-et a WebCrypto felületen keresztül. A Safari nem — ott a hívás ellenőrzés helyett kivételt dob. Ezért az ellenőrző kódunk visszaesik egy tiszta JavaScript-implementációra, amelyet csak ott töltünk be, ahol szükség van rá. Az aláírás-ellenőrzés így minden böngészőben lefut, méghozzá az olvasó eszközén.

Az időhorgony. Az aláírókulcs ujjlenyomatát az OpenTimestamps segítségével egy Bitcoin-blokkban rögzítjük. Ezzel nemcsak az igazolható, hogy az aláírás valódi, hanem az is, hogy a kulcs egy adott időpontban már létezett — anélkül, hogy bárkinek hinnie kellene a mi időbélyegünknek.

A tartalomhoz kötés. A payload hordozza az rh értéket, a teljes beküldött adatrekord hasítóértékét: szöveg, szívek, geostátusz, alkalomra vonatkozó adatok és eredet. Az Ed25519-aláírás így nemcsak a szöveget köti meg, hanem mindent, ami az értékelés mellett megjelenik.

---

20. Egy mondat, amit érdemes megjegyezni

Aki birtokolja a titkos skalárt, mikromásodpercek alatt ír alá. Aki nem birtokolja, annak diszkrét logaritmust kellene megoldania egy nagyjából $2^{252}$ elemű csoportban.

Egy értékelés olvasója számára ez egyszerűen azt jelenti: nem kell hinnie nekünk. Utánaszámolhat.