Схеми за подпис

Ed25519, обяснен математически

Подписът, който стои под всеки отзив в McGesund — от кривата през ключа до уравнението, което браузърът на читателя преизчислява.

Актуално към: 2026-09-07

1. За какво става дума

Отзивът в McGesund не е текстово поле в база данни, на което човек трябва просто да вярва. При изпращането той се подписва цифрово и всеки посетител може по-късно да преизчисли този подпис в собствения си браузър.

За този подпис използваме Ed25519. За разлика от FALCON и ML-DSA, които могат да бъдат положени допълнително като печат отстрани, Ed25519 не е въпрос на избор: всеки подписан отзив го носи, независимо от тарифата и начина на подаване.

Важно предварително:

Ed25519 не е криптиране. Текстът на отзива трябва да може да се чете. Подписът не доказва поверителност, а произход и цялост.

2. Какво точно се подписва

Подписва се не свободният текст, а компактен обект от данни, който еднозначно приковава текста и всичко останало:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID на фирмата>",
  "c":   "<ID на отзива>",
  "h":   "<SHA-256 на текста на отзива>",
  "rh":  "<SHA-256 на целия запис от подаването>",
  "rv":  1,
  "qh":  "<SHA-256 на QR плика, само при QR отзиви>",
  "kid": "<ID на ключа>",
  "iat": 1757203200
}

Този обект се кодира в CBOR. Точно тази последователност от байтове — а не красивото ѝ изображение по-горе — е нашето съобщение mm. Подписът и съобщението пътуват заедно в плик:

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

Тройката 33 е версията на формата. Повече в плика няма — и по-специално няма постквантов подпис: той, ако съществува, стои до записа, а не в плика.

3. Какво трябва да постига подписът

Читателят, който попада на профил на предприятие, стои пред два въпроса:

  1. Наистина ли този отзив произхожда от системата на McGesund?
  2. Променян ли е след това?

За целта има двойка ключове:

  • частен ключ — остава в услугата за подписване
  • публичен ключ — може да е у всеки, адресира се чрез идентификатора на ключа (kid) в полезния товар

Подписва се с частния ключ. Проверява се с публичния — и то в браузъра на читателя, а не на нашия сървър. Точно това е същественото: проверка, която извършваме ние и чийто резултат съобщаваме, не би била проверка, а твърдение.

4. Защо елиптична крива?

Всеки подпис се нуждае от сметка, която в едната посока е лесна, а в другата практически невъзможна. При Ed25519 това е скаларното умножение върху елиптична крива:

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

Изчисляването на публичната точка AA от тайното число aa отнема микросекунди. Обратното заключение от AA към aa е задачата за дискретния логаритъм — за нея не е известен метод, който при този размер да приключи в човешки срокове.

Практическата печалба спрямо по-стари методи като RSA е размерът:

публичен ключподпис
RSA-3072384 B384 B
Ed2551932 B64 B

При съпоставимо ниво на сигурност. 64 байта на отзив не са величина, за която да се мисли, дори при милиони отзиви.

5. Кривата edwards25519

Смята се по модул на просто число:

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

Оттам идва и името. Кривата е усукана крива на Едуардс:

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

Една „точка“ е двойка числа (x,y)(x,y) от {0,…,p−1}\{0,\dots,p-1\}, която удовлетворява това уравнение. Няма крива, която да се види — рисунката в следващия раздел е нагледно помагало над реалните числа, а не изображение на действителното изчислително пространство.

Добавят се още две величини:

  • твърдо уговорена базова точка BB,
  • редът ℓ\ell на породената от BB подгрупа:
ℓ=2252+27742317777372353535851937790883648493.\ell = 2^{252} + 27742317777372353535851937790883648493.

ℓ\ell е просто число. Това означава: ако се събира BB отново и отново със себе си, се пробягват точно ℓ\ell различни точки и се стига пак до началото. Затова всички сметки със скалари вървят по модул ℓ\ell, а всички сметки с координати — по модул pp. Смесването на тези две числа е класическата грешка на начинаещия.

6. Събиране на точки

Две точки се преработват в трета по твърда формула:

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

Неутралният елемент е (0,1)(0,1) — точката, от която започва смятането.

Тази формула има свойство, което по нея не личи и което за сигурността е по-важно от всяка константа: тя е пълна. Работи за всички входове, без специални случаи за „двете точки съвпадат“ или „резултатът е неутралният елемент“. При по-старите криви на Вайерщрас тези специални случаи ги има и всеки от тях е разклонение в програмата — разклонение, чието времетраене може да бъде измерено. Който измерва колко дълго трае един подпис, научава при такива методи нещо за тайния ключ.

Пълни формули означава: винаги един и същ изчислителен път, винаги едно и също време, нищо за измерване.

7. Скаларно умножение — еднопосочната улица

n⋅Bn\cdot B означава: BB да се събере със себе си точно nn пъти. При nn с 253 бита това би било безсмислено много работа — затова се удвоява:

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

и от тези междинни резултати се сглобява желаното nn. Около 253 удвоявания стигат за всяко nn. Това е пътят напред.

Назад тази пряка път няма. Да се определи числото aa от точката AA означава да се реши задачата за дискретния логаритъм.

(0,1) — неутрален елементB2B3B4B5B6B
Крива на Едуардс с първите кратни на базовата точка, изчислени с истинския закон за събиране. Над реалните числа те все още се разхождат видимо подредено по кривата — пътят би могъл да се проследи назад. По модул p изчезва именно тази подредба и точно върху това почива сигурността.

В истинския метод се смята по модул pp. Там няма „наляво“, няма „надясно“ и няма близост: от 17 B17\,B и 18 B18\,B се получават две двойки числа без каквато и да е разпознаваема връзка.

8. Двойката ключове на услугата за подписване

В началото стоят 32 случайни байта — seed. Всичко останало се извежда от тях:

h=SHA-512(seed),h=h0..31⏟→  a  ∥  h32..63⏟префикс.h = \mathrm{SHA\text{-}512}(\text{seed}), \qquad h = \underbrace{h_{0..31}}_{\to\;a}\;\|\;\underbrace{h_{32..63}}_{\text{префикс}}.

От първата половина възниква тайният скалар aa, но не в непроменен вид. Три бита се задават, съответно изчистват — така нареченото clamping:

  • най-долните три бита се нулират: така aa става кратно на 8. Причината е кофакторът 8 на кривата — пълната група от точки е осем пъти по-голяма от подгрупата от ред ℓ\ell. Делящо се на 8 aa попада гарантирано в правилната подгрупа и не издава нищо чрез точки от малък ред.
  • най-горният бит се изчиства, вторият отгоре се задава: така aa има винаги една и съща битова дължина. По-късо aa би изисквало по-малко удвоявания — и пак от времетраенето би могло да се прочете нещо.

Публичният ключ тогава е просто

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

записан като 32 байта: координатата yy, а в най-високия бит — знакът на xx. Самото xx проверяващият пресмята обратно от уравнението на кривата — двете решения се различават само по знак, а кое от тях се има предвид, казва точно този един бит.

Втората половина на хеш-стойността, префиксът, не е нужна за ключа. Тя влиза в употреба в следващия раздел.

9. Защо случайността тук не е случайност

Всеки подпис от този вид се нуждае от еднократна стойност rr, често наричана nonce. Тя никога не бива да се повтаря: който разполага с два подписа със същото rr, може да пресметне тайния ключ с училищна алгебра.

Точно на това са се провалили реални системи. Най-известният случай е проверката на подписи на една игрова конзола, чийто производител през 2010 г. използваше все един и същ nonce — с което частният ключ стана публично възстановим.

Ed25519 решава това, като изобщо не използва случайност:

r=SHA-512(префикс  ∥  m) mod ℓ.r = \mathrm{SHA\text{-}512}(\text{префикс}\;\|\;m) \bmod \ell.

Nonce зависи от тайния префикс и от съобщението. От това следват две неща:

  • Два различни отзива дават с преобладаваща вероятност различни rr — случаят на повторение не настъпва.
  • Един и същ отзив дава винаги един и същ подпис. Така един акт на подписване е проследим, а лош генератор на случайност на сървъра не може да развали нищо, защото такъв изобщо не е нужен.

За портал за отзиви с много подписи на ден това не е академично предимство. То е разликата между „грешка в източника на случайност би била фатална“ и „няма източник на случайност, който да откаже“.

10. Подписване

Три реда, повече не е:

r=H(префикс  ∥  m) mod ℓ,R=r⋅B,r = H(\text{префикс}\;\|\;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.

Подписът е двойката

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

32 байта за точката RR, 32 байта за числото SS — общо 64 байта.

Заслужава внимание вторият ред: в kk влизат RR, публичният ключ AA и съобщението. Това, че AA също се хешира, не е украса — то предотвратява атаки, при които подпис се преиначава като валиден за друг ключ.

11. Проверка

Браузърът на читателя знае: отзива mm, подписа (R,S)(R,S) и публичния ключ AA. Той изчислява kk наново и проверява едно-единствено уравнение:

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

Ако то е вярно, подписът е валиден. RFC 8032 допуска допълнително умножения с кофактора вариант 8S⋅B=8R+8k⋅A8S\cdot B = 8R + 8k\cdot A, който третира някои гранични случаи по-великодушно.

Никакъв сървър не се пита, никаква услуга не трябва да е достъпна. Публичният ключ е достатъчен.

12. Защо уравнението излиза

Достатъчно е да се замести:

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.

Целият трик е в средното преобразуване: скаларното умножение се съгласува със събирането. Който знае aa, може да пресметне SS, което удовлетворява уравнението. Който не знае aa, би трябвало към самостоятелно избрано kk да намери подходящо SS — а това означава да реши дискретния логаритъм.

13. Напълно пресметнат мини пример

С истинските числа няма какво да се проверява — стойности от 253 бита не се проверяват наум. Затова същият метод в мъничка група, в която всяка стъпка е проследима с калкулатор.

Стъпка 1: Групата

Смятаме с остатъците по модул 2323 и вземаме g=2g = 2. В сила е

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

тоест gg поражда подгрупа от ред ℓ=11\ell = 11. Степените са:

nn1234567891011
gng^n248169181336121

gg поема ролята на базовата точка BB, а умножението — тази на събирането на точки. Скаларите се смятат по модул 1111, стойностите — по модул 2323.

Стъпка 2: Двойката ключове

Нека тайното е a=6a = 6. Тогава

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

A=18A = 18 може да го знае всеки.

Стъпка 3: Nonce и commitment

От префикса и отзива нека се получи r=4r = 4. Оттам:

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

Стъпка 4: Предизвикателството

Нека хешът над RR, AA и отзива даде

k=5.k = 5.

Стъпка 5: Подписът

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.

Подписът е двойката (R,S)=(16, 1)(R,S) = (16,\,1).

Стъпка 6: Браузърът проверява

Той изчислява двете страни. Отляво:

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

Отдясно, при 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}.

И двете страни дават 22:

Подписът е валиден\boxed{\text{Подписът е валиден}}

Стъпка 7: Някой променя текста на отзива

Текстът влиза в хеша, тоест предизвикателството се променя — да кажем на k′=7k' = 7. Подписът остава непроменен при (16,1)(16,1), но дясната страна — не. При 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
Подписът е невалиден\boxed{\text{Подписът е невалиден}}

Можем да изтрием отзив. Не можем да го променим, без това да се забележи.

Бележка за честност към примера

Тук се смяташе в мултипликативната група по модул 2323, а не върху крива: gSg^S стои за S⋅BS\cdot B, а произведението R⋅AkR\cdot A^k — за събирането на точки R+k⋅AR + k\cdot A. Структурата е същата и точно за нея става дума. Различни са порядъците: ℓ=11\ell = 11 срещу ℓ≈2252\ell \approx 2^{252}, а там ключът не се намира с изпробване на единайсет възможности.

14. Какво се случва, ако някой промени отзива

Да допуснем, че някой с достъп до базата данни — включително някой при нас — променя текста на отзива или някое от сърцата. Тогава се променя записът, а с него поне една от двете хеш-стойности h и rh в полезния товар. С това се променя mm, с него предизвикателството kk, с него дясната страна на проверочното уравнение. Старият подпис вече не пасва.

Решаващото изречение по темата: можем да изтрием отзив, но не можем да го променим незабелязано. При McGesund същата проверка се извършва допълнително всяка нощ и от страна на сървъра върху целия наличен обем — отзив, който не я издържи, повече не влиза в средната оценка на предприятието.

15. Защо нападателят се проваля

Той знае публичния ключ AA, базовата точка BB, кривата и всеки издаден досега подпис. Липсва му aa.

Най-добрата известна класическа атака срещу задачата за дискретния логаритъм в група от ред ℓ\ell изисква около ℓ\sqrt{\ell} стъпки. При ℓ≈2252\ell \approx 2^{252} това са около

21262^{126}

операции. За сравнение: дори машина, която успява с милиард милиарда (101810^{18}) стъпки в секунда, би се нуждаела за това от многократната възраст на Вселената.

Фалшифициране без ключа би означавало към самостоятелно избрано kk да се намери подходящо SS — същата задача в друга маскировка.

16. Защо Ed25519, а не ECDSA

И двата почиват на един и същ проблем. Разликата е във всичко останало наоколо:

ECDSA (криви на NIST)Ed25519
Nonceнужна е прясна случайностдетерминиран от префикс и съобщение
Формулиспециални случаи, зависещи от данните разклоненияпълни, един изчислителен път
Параметри на криватапроизходът на константите така и не е обяснен докрайизбрани по проследими критерии
Размер на подписа64–72 B, променливо кодиранетвърдо 64 B
В браузъраотдавна наличенот 2023/2024 г. нативно, иначе като JS библиотека

За нас решаващият аргумент беше nonce. Портал за отзиви подписва често и автоматизирано; метод, при който една-единствена слаба случайна стойност издава ключа, е за целта погрешен избор.

17. Какво Ed25519 не постига

Ed25519 почива на дискретния логаритъм — а точно този проблем достатъчно голям квантов компютър решава ефикасно с алгоритъма на Шор. Дали и кога ще съществуват такива машини, е открит въпрос. За отзив, който след десет години все още трябва да е проверим, това въпреки всичко е въпрос, на който трябва да се отговори днес.

Затова до подписа Ed25519 може да застане квантово устойчив печат:

Двата не заместват Ed25519, а лягат до него. Ако единият метод бъде пробит, другият продължава да носи.

18. Процесът в картина

УСЛУГА ЗА ПОДПИСВАНЕ (MCGESUND)БРАУЗЪР НА ПОСЕТИТЕЛЯчастен скалар a + префикс (от seed-а)полезен товар m = {фирма, отзив, h, rh, iat}r = H(префикс ‖ m) mod ℓR = r · Bk = H(R ‖ A ‖ m) mod ℓS = (r + k · a) mod ℓподпис σ = (R, S) + kidотзив + σ + публичен ключ Aново изчисляване на k от R, A и mS · B = R + k · A ?валиденневалиден
От полезния товар до отметката в браузъра. Над разделителната линия всичко се случва еднократно при изпращането, под нея — наново при всеки читател, на неговото устройство, само с публичния ключ.

19. Какво прави McGesund конкретно с това

Пликът. Всеки подписан отзив носи плик MCG1: с версия на формата, полезен товар и подпис Ed25519. Полето kid в полезния товар казва кой ключ се има предвид; съответния публичен ключ сървърът доставя при запитване — той е публичен, там няма какво да се пази.

Проверката в браузъра. Chrome и Firefox могат да работят с Ed25519 нативно от 2023/2024 г. през интерфейса WebCrypto. Safari — не; там извикването хвърля грешка вместо да провери. Затова нашият проверяващ код се връща към чиста реализация на JavaScript, която се дозарежда само там, където е нужна. Така проверката на подписа минава във всеки браузър, и то на устройството на читателя.

Времевата котва. Отпечатъкът на ключа за подписване се закотвя чрез OpenTimestamps в блок на Bitcoin. С това може да се докаже не само че подписът е истински, а и че ключът вече е съществувал в определен момент — без някой да трябва да вярва на нашия времеви печат.

Обвързването със съдържанието. Полезният товар носи rh — хеша над целия запис от подаването: текст, сърца, гео статус, данни за повода и произход. Така подписът Ed25519 обвързва не само текста, а всичко, което се показва до отзива.

20. Едно изречение за накрая

Ed25519 превръща едно тайно число в уравнение,което всеки може да провери и никой да измисли.\boxed{ \begin{array}{c} \text{Ed25519 превръща едно тайно число в уравнение,}\\ \text{което всеки може да провери и никой да измисли.} \end{array}}

Който притежава тайния скалар, подписва за микросекунди. Който не го притежава, би трябвало да реши дискретен логаритъм в група с около 22522^{252} елемента.

За читателя на един отзив това означава простичко: той не трябва да ни вярва. Може да провери сам.