bbr_err

OneByteToy: OBT | BBR_TX | BBR_ERR | OBT_suite | BBR

Analýza kryptografického podpisu ESS251

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:

  1. 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.
  2. 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:

  1. 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.
  2. 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).
  3. 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.“

PrvekPůvodVýznam
Rk⋅GGeometrický základ podpisu na křivce.
rRx​(modn)Otisk bodu R v podpisu.
sk+e⋅dLineární kombinace, která „zamyká“ vše dohromady.