Ed25519 wyjaśniony matematycznie

1. O co tutaj chodzi

Opinia w McGesund nie jest polem tekstowym w bazie danych, któremu trzeba wierzyć. Przy wysłaniu zostaje podpisana cyfrowo, a każdy odwiedzający może później przeliczyć ten podpis w swojej własnej przeglądarce.

Do tego podpisu używamy Ed25519. W przeciwieństwie do FALCON i ML-DSA, które można dodatkowo dołożyć obok jako stemple, Ed25519 nie jest opcją: każda podpisana opinia go niesie, niezależnie od taryfy i drogi przesłania.

Ważna uwaga na wstępie:

Ed25519 nie jest szyfrowaniem. Tekst opinii ma przecież być czytany. Podpis nie dowodzi poufności, lecz pochodzenia i nienaruszalności.

---

2. Co dokładnie jest podpisywane

Podpisywany jest nie tekst ciągły, lecz kompaktowy obiekt danych, który jednoznacznie przybija tekst i całą resztę:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID firmy>",
  "c":   "<ID opinii>",
  "h":   "<SHA-256 tekstu opinii>",
  "rh":  "<SHA-256 całego rekordu przesłanej opinii>",
  "rv":  1,
  "qh":  "<SHA-256 koperty QR, tylko przy opiniach z QR>",
  "kid": "<ID klucza>",
  "iat": 1757203200
}

Ten obiekt zostaje zakodowany do CBOR. Ta sekwencja bajtów — a nie jej ładna postać powyżej — jest naszą wiadomością $m$. Podpis i wiadomość wędrują razem do koperty:

$3$ to wersja formatu. Nic więcej w niej nie ma — w szczególności żadnego podpisu postkwantowego: ten leży, jeśli istnieje, obok rekordu danych, a nie w kopercie.

---

3. Co ma zapewniać podpis

Czytelnik, który trafia na profil firmy, staje przed dwoma pytaniami:

1. Czy ta opinia rzeczywiście pochodzi z systemu McGesund?
2. Czy została później zmieniona?

Służy do tego para kluczy:

• klucz prywatny — pozostaje w usłudze podpisującej
• klucz publiczny — może go mieć każdy, adresowany przez identyfikator klucza (kid) w payloadzie

Podpisuje się kluczem prywatnym. Weryfikuje się publicznym — i to w przeglądarce czytelnika, a nie na naszym serwerze. I o to właśnie chodzi: weryfikacja, którą przeprowadzalibyśmy sami i której wynik jedynie komunikowalibyśmy, nie byłaby weryfikacją, lecz twierdzeniem.

---

4. Dlaczego krzywa eliptyczna?

Każdy podpis potrzebuje działania, które w jedną stronę jest łatwe, a w drugą praktycznie niemożliwe. W Ed25519 jest to mnożenie przez skalar na krzywej eliptycznej:

Obliczenie punktu publicznego $A$ z tajnej liczby $a$ kosztuje mikrosekundy. Wnioskowanie z $A$ z powrotem o $a$ to problem logarytmu dyskretnego — nie jest znana metoda, która przy tym rozmiarze uporałaby się z nim w ludzkich ramach czasowych.

Praktyczna korzyść w porównaniu ze starszymi metodami, takimi jak RSA, to rozmiar:

Przy porównywalnym poziomie bezpieczeństwa. 64 bajty na opinię to nawet przy milionach opinii nie jest rozmiar, nad którym trzeba się zastanawiać.

---

5. Krzywa edwards25519

Obliczenia prowadzone są modulo pewna liczba pierwsza:

Stąd nazwa. Krzywa jest skręconą krzywą Edwardsa:

„Punkt" to para liczb $(x,y)$ ze zbioru $\{0,\dots,p-1\}$, która spełnia to równanie. Nie ma tu żadnej krzywej do oglądania — rysunek w następnym rozdziale jest pomocą poglądową nad liczbami rzeczywistymi, a nie obrazem rzeczywistej przestrzeni obliczeń.

Dochodzą jeszcze dwie wielkości:

• ustalony na stałe punkt bazowy $B$,
• rząd $\ell$ podgrupy generowanej przez $B$:

$\ell$ jest liczbą pierwszą. Oznacza to: dodając $B$ wciąż na nowo do siebie samego, przechodzi się przez dokładnie $\ell$ różnych punktów i wraca na początek. Wszystkie obliczenia na skalarach biegną dlatego modulo $\ell$, a wszystkie obliczenia na współrzędnych modulo $p$. Pomylenie tych dwóch liczb to klasyczny błąd początkującego.

---

6. Dodawanie punktów

Dwa punkty zostają według stałego wzoru przeliczone na trzeci:

Elementem neutralnym jest $(0,1)$ — punkt, w którym liczenie się zaczyna.

Ten wzór ma własność, której po nim nie widać, a która dla bezpieczeństwa jest ważniejsza niż jakakolwiek stała: jest zupełny. Działa dla wszystkich danych wejściowych, bez przypadków szczególnych w rodzaju „oba punkty są równe" albo „wynikiem jest element neutralny". Przy starszych krzywych Weierstrassa takie przypadki szczególne istnieją, a każdy z nich to gałąź w programie — gałąź, której czas wykonania da się zmierzyć. Kto mierzy, jak długo trwa podpisywanie, dowiaduje się przy takich metodach czegoś o kluczu tajnym.

Zupełne wzory oznaczają: zawsze ta sama droga obliczeń, zawsze ten sam czas, nic do zmierzenia.

---

7. Mnożenie przez skalar — droga jednokierunkowa

$n\cdot B$ oznacza: dodać $B$ dokładnie $n$ razy do siebie samego. Przy $n$ o długości 253 bitów byłoby to bezsensownie dużo pracy — dlatego się podwaja:

a z tych wyników pośrednich składa się żądane $n$. Około 253 podwojeń wystarcza dla każdego $n$. To jest droga w przód.

Wstecz takiego skrótu nie ma. Wyznaczenie liczby $a$ z punktu $A$ oznacza rozwiązanie problemu logarytmu dyskretnego.

W rzeczywistej metodzie liczy się modulo $p$. Tam nie ma „lewa", nie ma „prawa" i nie ma bliskości: z $17\,B$ i $18\,B$ powstają dwie pary liczb bez jakiegokolwiek rozpoznawalnego pokrewieństwa.

---

8. Para kluczy usługi podpisującej

Na początku są 32 losowe bajty, seed. Wszystko dalsze zostaje z nich wyprowadzone:

Z pierwszej połowy powstaje tajny skalar $a$, jednak nie w niezmienionej postaci. Trzy bity zostają ustawione względnie wyzerowane — tak zwany clamping:

• trzy najniższe bity zostają wyzerowane: $a$ staje się przez to wielokrotnością 8. Powodem jest kofaktor 8 krzywej — pełna grupa punktów jest ośmiokrotnie większa niż podgrupa rzędu $\ell$. Podzielne przez 8 $a$ trafia z gwarancją do właściwej podgrupy i nie zdradza niczego o punktach małego rzędu.
• najwyższy bit zostaje wyzerowany, a drugi od góry ustawiony: $a$ ma dzięki temu zawsze tę samą długość bitową. Krótsze $a$ wymagałoby mniej podwojeń — i znowu z czasu wykonania dałoby się coś odczytać.

Klucz publiczny to następnie po prostu

zapisany jako 32 bajty: współrzędna $y$, a w najstarszym bicie znak $x$. Wartość $x$ weryfikujący wylicza sobie sam z równania krzywej — oba rozwiązania różnią się tylko znakiem, a o które chodzi, mówi ten jeden bit.

Druga połowa wartości skrótu, prefiks, nie jest potrzebna do klucza. Zostanie użyta w następnym rozdziale.

---

9. Dlaczego losowość nie jest tu losowa

Każdy podpis tej konstrukcji potrzebuje jednorazowej wartości $r$, często zwanej nonce. Nigdy nie może się ona powtórzyć: kto ma dwa podpisy z tym samym $r$, wyliczy klucz tajny szkolną algebrą.

Właśnie na tym poległy realne systemy. Najbardziej znany przypadek to weryfikacja podpisów pewnej konsoli do gier, której producent w 2010 roku używał zawsze tego samego nonce — klucz prywatny dał się przez to publicznie zrekonstruować.

Ed25519 rozwiązuje to, nie używając losowości w ogóle:

Nonce zależy od tajnego prefiksu i od wiadomości. Wynikają z tego dwie rzeczy:

• Dwie różne opinie dają z przytłaczającym prawdopodobieństwem różne $r$ — przypadek powtórzenia nie występuje.
• Ta sama opinia daje zawsze ten sam podpis. Proces podpisywania da się dzięki temu odtworzyć, a zły generator losowy na serwerze nie może niczego zepsuć, bo żaden nie jest potrzebny.

Dla portalu z opiniami, w którym powstaje wiele podpisów dziennie, nie jest to zaleta akademicka. To różnica między „błąd w źródle losowości byłby fatalny" a „nie ma źródła losowości, które mogłoby zawieść".

---

10. Podpisywanie

Trzy wiersze, nic więcej:

Podpisem jest para

32 bajty na punkt $R$, 32 bajty na liczbę $S$ — razem 64 bajty.

Godny uwagi jest drugi wiersz: w $k$ wchodzą $R$, klucz publiczny $A$ oraz wiadomość. To, że $A$ jest współhaszowany, nie jest dodatkiem — zapobiega atakom, w których podpis zostaje przeinterpretowany na inny klucz.

---

11. Weryfikacja

Przeglądarka czytelnika zna: opinię $m$, podpis $(R,S)$ i klucz publiczny $A$. Wylicza $k$ na nowo i sprawdza jedno jedyne równanie:

Jeśli się zgadza, podpis jest ważny. RFC 8032 dopuszcza dodatkowo wersję pomnożoną przez kofaktor, $8S\cdot B = 8R + 8k\cdot A$, która traktuje niektóre przypadki brzegowe łagodniej.

Żaden serwer nie jest pytany, żadna usługa nie musi być dostępna. Klucz publiczny wystarcza.

---

12. Dlaczego równanie się zgadza

Wystarczy podstawić:

Cała sztuczka tkwi w środkowym przekształceniu: mnożenie przez skalar jest zgodne z dodawaniem. Kto zna $a$, wyliczy $S$ spełniające to równanie. Kto $a$ nie zna, musiałby do samodzielnie wybranego $k$ znaleźć pasujące $S$ — a to znaczy rozwiązać logarytm dyskretny.

---

13. W pełni przeliczony miniprzykład

Na prawdziwych liczbach nie da się niczego przeliczyć — wartości 253-bitowych nie sprawdzi się w pamięci. Dlatego ta sama metoda w maleńkiej grupie, w której każdy krok da się odtworzyć kalkulatorem.

Krok 1: Grupa

Liczymy na resztach modulo $23$ i bierzemy $g = 2$. Zachodzi

$g$ generuje więc podgrupę rzędu $\ell = 11$. Potęgi wynoszą:

$g$ przejmuje rolę punktu bazowego $B$, a mnożenie — rolę dodawania punktów. Skalary liczy się modulo $11$, wartości modulo $23$.

Krok 2: Para kluczy

Niech tajne będzie $a = 6$. Wtedy

$A = 18$ może znać każdy.

Krok 3: Nonce i commitment

Niech z prefiksu i opinii wyjdzie $r = 4$. Stąd:

Krok 4: Challenge

Niech skrót z $R$, $A$ i opinii da

Krok 5: Podpis

Podpisem jest para $(R,S) = (16,\,1)$.

Krok 6: Przeglądarka weryfikuje

Wylicza obie strony. Po lewej:

Po prawej, przy $18^5 \equiv 3 \pmod{23}$:

Obie strony dają $2$:

Krok 7: Ktoś zmienia tekst opinii

Tekst wchodzi do skrótu, zmienia się więc challenge — powiedzmy na $k' = 7$. Podpis pozostaje niezmieniony przy $(16,1)$, ale prawa strona już nie. Przy $18^7 \equiv 6 \pmod{23}$:

Opinię możemy usunąć. Zmienić jej nie możemy tak, żeby nikt tego nie zauważył.

Uwaga o rzetelności przykładu

Liczyliśmy tu w grupie multiplikatywnej modulo $23$, a nie na krzywej: $g^S$ odpowiada $S\cdot B$, a iloczyn $R\cdot A^k$ — dodawaniu punktów $R + k\cdot A$. Struktura jest ta sama i właśnie o to chodzi. Różnią się rzędy wielkości: $\ell = 11$ wobec $\ell \approx 2^{252}$, a tam klucza nie znajdzie się przez wypróbowanie jedenastu możliwości.

---

14. Co się dzieje, gdy ktoś zmieni opinię

Załóżmy, że ktoś z dostępem do bazy danych — także ktoś u nas — zmienia tekst opinii albo jedno z serduszek. Wtedy zmienia się rekord danych, a wraz z nim co najmniej jedna z dwóch wartości skrótu h i rh w payloadzie. Tym samym zmienia się $m$, więc challenge $k$, więc prawa strona równania weryfikacyjnego. Stary podpis już nie pasuje.

Rozstrzygające zdanie brzmi: opinię możemy usunąć, ale nie możemy jej zmienić niepostrzeżenie. W McGesund ta sama weryfikacja przebiega dodatkowo co noc po stronie serwera na całym zasobie — opinia, która jej nie przejdzie, nie wlicza się już do średniej firmy.

---

15. Dlaczego atakujący przegrywa

Zna klucz publiczny $A$, punkt bazowy $B$, krzywą i każdy dotąd wystawiony podpis. Brakuje mu $a$.

Najlepszy znany klasyczny atak na problem logarytmu dyskretnego w grupie rzędu $\ell$ potrzebuje około $\sqrt{\ell}$ kroków. Przy $\ell \approx 2^{252}$ to mniej więcej

operacji. Dla porównania: nawet maszyna wykonująca miliard miliardów ($10^{18}$) kroków na sekundę potrzebowałaby na to wielokrotności wieku wszechświata.

Fałszowanie bez klucza oznaczałoby znalezienie do samodzielnie wybranego $k$ pasującego $S$ — to samo zadanie w innym przebraniu.

---

16. Dlaczego Ed25519, a nie ECDSA

Oba opierają się na tym samym problemie. Różnica leży we wszystkim, co dzieje się dookoła:

Dla nas rozstrzygający był nonce. Portal z opiniami podpisuje często i automatycznie; metoda, w której jedna słaba wartość losowa ujawnia klucz, jest do tego złym wyborem.

---

17. Czego Ed25519 nie zapewnia

Ed25519 opiera się na logarytmie dyskretnym — a właśnie ten problem dostatecznie duży komputer kwantowy rozwiązuje efektywnie algorytmem Shora. Czy i kiedy takie maszyny powstaną, pozostaje otwarte. Dla opinii, która ma być sprawdzalna jeszcze za dziesięć lat, jest to mimo wszystko pytanie, na które trzeba odpowiedzieć już dziś.

Dlatego obok podpisu Ed25519 może stanąć stempel odporny na ataki kwantowe:

• FALCON (FN-DSA) — kompaktowe podpisy z krat NTRU
• ML-DSA-87 (FIPS 204) — zamknięty standard NIST

Żaden z nich nie zastępuje Ed25519, kładą się obok. Jeśli jedna z metod padnie, druga niesie dowód dalej.

---

18. Przebieg na rysunku

---

19. Co konkretnie robi z tym McGesund

Koperta. Każda podpisana opinia niesie kopertę MCG1: z wersją formatu, payloadem i podpisem Ed25519. kid w payloadzie mówi, o który klucz chodzi; odpowiadający mu klucz publiczny serwer wydaje na żądanie — jest publiczny, nie ma tam czego chronić.

Weryfikacja w przeglądarce. Chrome i Firefox obsługują Ed25519 natywnie od 2023/2024 przez interfejs WebCrypto. Safari nie — tam wywołanie zgłasza błąd zamiast weryfikować. Dlatego nasz kod weryfikujący sięga po czystą implementację w JavaScripcie, doładowywaną tylko tam, gdzie jest potrzebna. Weryfikacja podpisu przechodzi dzięki temu w każdej przeglądarce, i to na urządzeniu czytelnika.

Kotwica czasu. Odcisk klucza podpisującego zostaje zakotwiczony przez OpenTimestamps w bloku Bitcoina. Pozwala to wykazać nie tylko, że podpis jest prawdziwy, lecz także, że klucz istniał już w określonym momencie — bez konieczności wiary komukolwiek w nasz znacznik czasu.

Powiązanie z treścią. Payload niesie rh, skrót całego rekordu przesłanej opinii: tekstu, serduszek, statusu geolokalizacji, informacji o okoliczności i pochodzenia. Podpis Ed25519 wiąże tym samym nie tylko tekst, lecz wszystko, co wyświetla się obok opinii.

---

20. Jedno zdanie na wynos

Kto posiada tajny skalar, podpisuje w mikrosekundach. Kto go nie posiada, musiałby rozwiązać logarytm dyskretny w grupie o około $2^{252}$ elementach.

Dla czytelnika opinii oznacza to po prostu: nie musi nam wierzyć. Może przeliczyć.