bbr_err
Zde je čistě strukturální HTML verze (bez JavaScriptu, bez CSS a bez WordPress balastu), která slouží jako studijní materiál pro pochopení matematiky a zranitelnosti systému ESS251. HTML
Kryptografický rozbor schématu ESS251
Tento dokument vysvětluje matematické pozadí ověřování podpisu a demonstruje, proč je konkrétní implementace „Toy“ systému zranitelná vůči úplnému odhalení soukromého klíče.
1. Matematický důkaz: Proč $s \cdot G = R + e \cdot Q$?
Ověření podpisu v systému ESS251 (Schnorrova varianta) stojí na distributivním zákoně skalárního násobení nad sčítáním bodů na eliptické křivce.
Definice proměnných:
- G: Generátor (pevný bod na křivce).
- q: Soukromý klíč (utajené číslo).
- Q: Veřejný klíč (bod na křivce, vypočten jako $Q = q \cdot G$).
- k: Nonce (dočasné číslo použité pro jeden podpis).
- R: Nonce-bod (bod na křivce, vypočten jako $R = k \cdot G$).
- e: Hash zprávy (číslo, tzv. „výzva“ neboli challenge).
- s: Výsledný podpis (číslo).
Odvození rovnice:
Podpis se vytváří podle vzorce:
s = k + e * q (vše modulo n)
Pokud obě strany rovnice vynásobíme generátorem G, dostaneme:
s * G = (k + e * q) * G
Díky vlastnostem eliptických křivek můžeme pravou stranu roznásobit:
s * G = (k * G) + (e * q * G)
Nyní dosadíme definice pro R a Q:
s * G = R + e * Q
Tato rovnost musí platit, aby byl podpis označen za validní. Verifikátor zná s, G, R, e a Q, takže může obě strany nezávisle vypočítat a porovnat.
2. Kritická zranitelnost: Extrakce soukromého klíče
V bezpečném systému musí být nonce k naprosto náhodné a tajné. Pokud je však k vypočteno veřejně známým algoritmem (v tomto případě k = hash XOR 0x55), systém se hroutí.
Jak útočník získá klíč:
- Útočník zachytí zprávu a její podpis s.
- Vypočítá hash zprávy, čímž získá hodnotu e.
- Protože zná algoritmus pro výpočet noncu, vypočítá k identicky jako autor podpisu.
- Nyní má útočník rovnici o jedné neznámé (soukromý klíč q):
s = k + e * q
- Jednoduchou algebraickou úpravou získá soukromý klíč:
q = (s - k) * e⁻¹ (modulo n)
Závěr: Stačí jediný zachycený podpis k tomu, aby kdokoli na světě mohl začít podepisovat transakce jménem daného veřejného klíče.
3. Tabulka dat (Ukázka struktury)
| Role | Hodnota (Příklad) | Viditelnost |
|---|---|---|
| Soukromý klíč (q) | 123 | Tajné (v ESS251 kompromitované) |
| Nonce (k) | (Hash ^ 0x55) | Veřejně odvoditelné |
| Podpis (s) | Číslo (např. 142) | Veřejné |
| Verifikační bod L | s * G | Vypočítá verifikátor |
| Verifikační bod R+eQ | R + e * Q | Vypočítá verifikátor |
Poznámka: ESS251 je vzdělávací model. V reálných systémech jako Bitcoin (ECDSA) se k zabránění této zranitelnosti používá deterministické generování noncu podle standardu RFC 6979, které kombinuje hash zprávy se soukromým klíčem, takže k zůstává pro útočníka neznámé.
Celá bezpečnost asymetrické kryptografie (včetně Bitcoinu i našeho ESS251) stojí na tom, že tato rovnost funguje díky distributivitě skalárního násobení nad sčítáním bodů na křivce.
Je to vlastně krásně jednoduchá algebra „převlečená“ do geometrie bodů.
1. Proč tam máme zjednodušení k = hash ^ 0x55?
V reálné kryptografii (jako ECDSA nebo Ed2519) musí být nonce k buď naprosto náhodné, nebo generované pomocí RFC 6979 (deterministicky, ale tajně). My volíme cestu „veřejného determinismu“.
Důvody pro toto zjednodušení v kódu:
- Rekonstrukce bodu R: Ve standardním Schnorr podpisu musíme poslat (r, s). V našemsystému ale posíláme jen 2 bajty. Protože verifikátor zná hash zprávy, může si díky vzorci k = (hash \oplus 0x55) \pmod n vypočítat stejné k a následně zrekonstruovat bod R = k * G. Nemusíme ho tedy přenášet v podpisu.
- Ladění (Debugging): Pro výukové účely je skvělé, když pro stejnou zprávu vyjde vždy stejný podpis. Snadněji se hledá chyba v matematice křivky.
Proč je to v produkci sebevražda?
Pokud útočník zná k (což zná, protože zná hash a vzorec), může okamžitě vypočítat i soukromý klíč d:
d = (s – k) * e^{-1} \p mod n
Stačí mu jeden jediný podpis a naše „banka“ je prázdná.
Jak souvisí r,s s bodem R?
Mají k sobě velmi blízko. Tady je „rodokmen“ podpisu:
- Bod R (Nonce point): Je to bod na křivce, který vznikne jako $R = k \cdot G$. Je to v podstatě „dočasný veřejný klíč“ pro jeden konkrétní podpis.
- Hodnota r: V tvém kódu je to x-ová souřadnice bodu R (osekaná modulo n). V mnoha schématech se r používá jako „výzva“ (challenge).
- Hodnota s: To je ten „důkaz“. Je to skalár (číslo), který v sobě kombinuje tajemství (d), nonce (k), hash zprávy (e) a veřejnou část (r nebo R).
Matematický vztah:
Podpis v podstatě říká: „Znám takové číslo d (soukromý klíč), že když ho vynásobím hashem a přičtu k mému tajnému k, dostanu hodnotu s, která přesně sedí do geometrie křivky vzhledem k mému veřejnému klíči.“
| Prvek | Původ | Význam | |||
| R | k⋅G | Geometrický základ podpisu na křivce. | |||
| r | Rx(modn) | Otisk bodu R v podpisu. | |||
| s | k+e⋅d | Lineární kombinace, která „zamyká“ vše dohromady. |
