AlgoRithm of Bit·Block·(algo)Rithm

How Bitcoin Works: Bitcoin Math Playground

Matematické principy stejné, jako má Bitcoin, jen velmi zjednodušené.
Málá čísla:

ecc251 – má jen 251 privátních klíčů, takže by se daly všechny páry (secret+pubKey naučit zpaměti)

y^2 = x^3 + 7 mod 251

Jen jedna peněženka
Max tři adresy (pro testy já1 to já2… ale stačí jen jednen)
Jen celé jednotky mincí bez fee

Centralizovaná databáze:
jen simulováno na jediném serveru
mempool i blockchain zcela pod kontrolou admina

Tato velká zjednodušení vedou k jistým omezením, ale především se dá demonstrovat obrovská zranitelnost!

těžba
klikání po cca 3-5 sec
obtížnost 1 nebo 2 nuly
max dvě transakce v bloku

registrace nového testovacího uživatele?
možná jen zamčeno pro editaci
a odemykat jen na workshop – schválně, kdy se to zvrhne

ecc251 | ess251

Modulo tělesa p = 251: Určuje „velikost hřiště“. Všechny souřadnice x a y v [x,y] musí být menší než 251.

Řád grupy n = 252: Určuje „počet kroků“, než se po křivce vrátíme na začátek (potažmo do nekonečna).

původní bod G=(15, 13) na křivce vůbec neležel -> Výběrem G=(1, 192) jsme zajistili, že se pohybujeme po „kolejích“ definovaných křivkou.

ECC251_skips

https://www.agamapoint.com/bbr/tests_examples/simple_ecc251ec.html

ukázka zkoumá izomorfní (strukturálně stejné) vztahy mezi eliptickými křivkami v diskrétním a spojitém prostoru. Mapováním skalárních násobení v Galoisově tělese GF(251) na reálnou Weierstrassovu projekci vizualizace odhaluje základní algebraickou symetrii, která řídí moderní kryptografické systémy. Každý krok ukazuje transformaci diskrétních mřížkových bodů na jejich geometrické protějšky pomocí rekonstrukce znaménka založené na paritě.

Vysvětlení pro středoškoláka

Eliptická křivka je speciální typ křivky dané rovnicí, například ve tvaru y2=x3+ax+by^2 = x^3 + ax + by2=x3+ax+b Taková křivka má zajímavé matematické vlastnosti a používá se v kryptografii (např. u Bitcoinu).
Existují dvě prostředí, kde s ní můžeme pracovat:
1. Spojitý (reálný) prostor – klasický graf v souřadnicové rovině s reálnými čísly.
2. Diskrétní prostor – místo reálných čísel používáme konečné těleso, zde GF(251).
  To znamená, že počítáme „modulo 251“ (po dosažení 250 se vracíme na 0).
Izomorfní vztah znamená, že i když vypadají jinak (jednou je to hladká křivka, podruhé jen sada bodů na mřížce), jejich vnitřní struktura a pravidla sčítání bodů jsou si odpovídající.
Skalární násobení znamená opakované sčítání bodu se sebou samým (např. 5·P = P + P + P + P + P).
To je základ operací v kryptografii.
Parita (sudé/liché) se používá k určení správného znaménka u souřadnice yyy, protože rovnice dává dvě možnosti: yyy a −y-y−y.

Shrnutí jednoduše

V experimentu se vezme eliptická křivka počítaná v „modulárním světě“ (jen čísla 0–250) a ukáže se, že její chování odpovídá hladké křivce v běžném grafu. I když jedna verze je jen sada bodů a druhá spojitá čára, jejich matematická struktura je stejná. Tato skrytá symetrie je základem moderní kryptografie.

Galoisovo těleso (finite field) je množina konečného počtu čísel, ve které lze sčítat, odčítat, násobit a dělit (kromě dělení nulou) a vždy zůstáváme uvnitř té množiny.

Typický příklad:
GF(251) znamená, že počítáme s čísly 0–250 a všechny operace děláme modulo 251.

Například v GF(251):

250 + 5 = 4 (protože 255 mod 251 = 4)
3 · 100 = 49 (protože 300 mod 251 = 49)

Když řekneme, že eliptická křivka je „na Galoisově tělese“, znamená to, že:

souřadnice bodů nejsou běžná reálná čísla,
ale čísla modulo 251,
výsledkem není hladká křivka, ale konečný počet bodů v mřížce.

To je klíčové pro kryptografii – pracujeme s konečnou, přesně definovanou strukturou.

„Weierstrassova projekce“

Eliptická křivka se obvykle zapisuje ve tvaru: y2=x3+ax+by^2 = x^3 + ax + by2=x3+ax+b

Tomuto tvaru se říká Weierstrassův tvar (podle matematika Karla Weierstrasse).

„Weierstrassova projekce“ zde znamená:

zobrazení bodů křivky do běžné souřadnicové roviny (x, y),
tedy klasický graf, kde osa x a y jsou reálná čísla.

V reálném prostoru vznikne hladká symetrická křivka.
V konečném tělese (např. GF(251)) vznikne jen sada oddělených bodů.

Podepisování a ověřování

1) GENEROVÁNÍ VEŘEJNÉHO KLÍČE
Funkce: scalar_mult(priv, G_POINT)
Vstup: priv = 111 G_POINT = [1,192]
Výstup: veřejný bod P = [131,193] x = 131 y = 193
Funkce: pubkey_to_addr(pub)
Vstup: pub = [131,193]
Výstup: hex veřejného klíče = 83c1

2) HASH ZPRÁVY
Funkce: ASH24(input_msg) | Vstup: input_msg = „1“ |
Výstup: h_raw = ASH24(msg) = 9366529 | hex24(…) = 0x8eec01

3) PODPIS ZPRÁVY
Funkce: signToy(priv, h_raw) | Vstup: priv = 111 | h_raw = 9366529
Výstup objektu: sig.R_point = [19,198] | sig.r = 19 sig.s = 27
Mezikroky ověřitelné ručně:
L = scalar_mult(s, G) = [230,182]
e*Pub = scalar_mult(h mod n, Pub) = [155,235]
P = R + e*Pub = [230,182]

4) OVĚŘENÍ PODPISU
Funkce: verifyToy(pub, h_raw, sig)
Vstup: pub = [131,193] | h_raw = 9366529 | sig = { r:19, s:27 }
Výstup: valid = true

Proč je podpis validní?
Podpis je validní, pokud platí:
s*G = R + e*Pub
což znamená, že podpis mohl vytvořit pouze držitel privátního klíče.
Zde: L = [230,182] | P = [230,182]
=> L == P → Podpis je VALIDNÍ ✅

hashujeme: „1“

| 0x8eec01 | signed | R=[19,198]
L = s*G: [230,182], P = R + e*PubKey: [230,182], Valid ✅

1. Příprava a výběr vstupu (UTXO)

Předtím, než se začne cokoliv podepisovat, musí systém zjistit, zda má uživatel čím platit.

Identifikace: Ze soukromého klíče uloženého v session (k1) se odvodí veřejný klíč a následně adresa uživatele (myAddr).
Hledání mincí: Skript zavolá backend (get_utxo), aby našel dostupný neutracený výstup (UTXO), který patří dané adrese. Tento záznam obsahuje txid (identifikátor předchozí transakce) a value (kolik mincí je k dispozici).

2. Co se hashuje (The Message)

Aby byla transakce bezpečná, nepodepisuje se jen částka, ale celá struktura, která definuje „kdo, co a komu“. Vytvoří se řetězec msg (zpráva), který obsahuje:

myAddr: Adresa odesílatele.
txid: ID předchozí transakce (tím se zajistí, že odesílatel skutečně „vlastní“ ty mince, které utrácí).
to: Adresa příjemce.
amount: Částka, kterou posílá.

Tento řetězec vypadá například takto: e875|1005|abcd|3.

Následně se na něj aplikuje hashovací funkce ASH24, která vytvoří unikátní číselný otisk (hash) této zprávy.

3. Jakým klíčem se podepisuje

K podpisu se používá soukromý klíč (myPriv), který má uživatel v session.

Používá se funkce signToy(myPriv, h).
Využívá se kryptografie na bázi eliptických křivek (ECC). Výsledkem podpisu jsou dvě čísla: r a s.
Tento podpis dokazuje, že zprávu (obsahující hash) vytvořil držitel soukromého klíče, aniž by tento klíč musel komukoliv ukazovat.

4. Jak se transakce odesílá

Po podepsání se na backend pošle balíček dat:

Odkud, kam, kolik.
Hodnota původního UTXO (val1) a posílaná částka (val2).
Samotný digitální podpis (r, s).
ID původního UTXO, aby ho databáze mohla označit za „utracené“.

5. Jak pak ověříme (Validace)

Ačkoliv to v tomto výřezu kódu není přímo vidět (děje se to na straně příjemce nebo v historii), ověření probíhá takto:

Sestavení zprávy: Vezmou se data uložená v databázi (from, txid, to, amount) a vytvoří se úplně stejný hash jako při podepisování.
Veřejný klíč: Z adresy odesílatele (from_addr) se zrekonstruuje jeho veřejný klíč.
Kryptografický test: Zavolá se funkce verifyToy(pubKey, hash, signature).

Princip ověření: Matematika eliptických křivek umožní ověřit, zda dvojice (r, s) odpovídá danému hashi a veřejnému klíči. Pokud se levá strana rovnice ($L = s \cdot G$) rovná pravé straně ($P = R + h \cdot Pub$), víme s jistotou, že data nebyla změněna a podpis je pravý.

Hodiny? mod 12

Uvažujme strukturu danou množinou zbytků po dělení 12, tedy {0,…,11}, s operací +1 mod 12, což znamená, že opakovaným přičítáním jedničky procházíme všechny prvky jako na hodinách. Tato operace je ve skutečnosti běžné sčítání modulo 12, takže vzniká cyklická grupa generovaná prvkem 1.

Grupa je abelova, protože sčítání modulo 12 je komutativní.

Nejde však o Galoisovo těleso, protože těleso musí mít počet prvků roven mocnině prvočísla, zatímco 12 = 2²·3, takže v této množině nelze zavést násobení tak, aby vzniklo těleso.

Neutrálním prvkem je 0, protože pro každé a platí a+0 ≡ a (mod 12).

Inverzní prvek k prvku a je číslo 12−a (mod 12), tedy takové, které se s a sečte na 0; například k 5 je inverzní 7, protože 5+7 ≡ 0 (mod 12). Celá struktura je tedy konečná abelovská cyklická grupa řádu 12, izomorfní k ℤ₁₂, ale nikoli těleso.

Zde je shrnutí vaší úvahy v jednom uceleném bloku, který můžete snadno zkopírovat:

Analýza struktury $(\mathbb{Z}_{12}, +)$

Uvažovaná struktura na množině zbytků $\{0, 1, \dots, 11\}$ s operací sčítání modulo 12 je konečná abelovská cyklická grupa řádu 12, izomorfní k $\mathbb{Z}_{12}$. Mezi její definující vlastnosti patří:

Grupové vlastnosti: Neutrálním prvkem je $0$, protože $a + 0 \equiv a \pmod{12}$. Ke každému prvku $a$ existuje inverzní prvek $12 – a$ (např. inverze k $5$ je $7$, neboť $5 + 7 \equiv 0 \pmod{12}$).
Cyklikost: Grupa je generována prvkem $1$, jehož opakovaným přičítáním získáme všechny prvky množiny. Dalšími generátory jsou všechna čísla nesoudělná s 12, tedy $\{1, 5, 7, 11\}$.
Absence vlastností tělesa: Tato struktura není tělesem (Galoisovým tělesem). Konečné těleso existuje pouze tehdy, je-li počet jeho prvků roven mocnině prvočísla ($q = p^n$). Jelikož $12 = 2^2 \cdot 3$, tuto podmínku nesplňuje.
Dělitelé nuly: Při pokusu o zavedení násobení modulo 12 narazíme na existenci dělitelů nuly (např. $3 \cdot 4 \equiv 0 \pmod{12}$), což vylučuje strukturu tělesa, kde součin dvou nenulových prvků musí být vždy nenulový.

Celkově vzato je vaše matematická argumentace správná a přesně vystihuje rozdíl mezi aditivní grupou zbytků a strukturou tělesa.

mod 17

Jelikož 17 je prvočíslo, dostáváme se do úplně jiné matematické ligy. Zatímco u 12 jsme měli jen „obyčejnou“ grupu, u 17 získáme plnohodnotné Galoisovo těleso $GF(17)$ neboli $\mathbb{Z}_{17}$.

Hlavní rozdíl je v tom, že v $\mathbb{Z}_{17}$ můžeme nejen sčítat a odčítat, ale i libovolně dělit (kromě dělení nulou). To u čísla 12 nešlo, protože tam existovali „dělitelé nuly“ (např. $3 \cdot 4 = 0$), kteří dělení znemožňovali.

Zde je shrnutí pro číslo 17 v jednom bloku pro vaše potřeby:

Analýza struktury $(\mathbb{Z}_{17}, +, \cdot)$

Množina $\{0, 1, \dots, 16\}$ s operacemi sčítání a násobení modulo 17 tvoří konečné těleso (Galoisovo těleso $GF(17)$). Tato struktura splňuje všechny axiomy tělesa, což ji činí mnohem bohatší než v případě čísla 12.

Aditivní struktura: Stejně jako u $\mathbb{Z}_{12}$ jde o abelovskou cyklickou grupu řádu 17. Neutrálním prvkem je $0$ a ke každému $a$ existuje inverzní prvek $17 – a$.
Multiplikativní struktura: Toto je klíčový rozdíl. Protože 17 je prvočíslo, množina všech nenulových prvků $\{1, \dots, 16\}$ tvoří s operací násobení modulo 17 multiplikativní grupu. To znamená, že ke každému nenulovému prvku existuje multiplikativní inverze (číslo, které po vynásobení s původním dá 1).
- Příklad inverze: Pro prvek $2$ je inverzí $9$, protože $2 \cdot 9 = 18 \equiv 1 \pmod{17}$.
- Příklad inverze: Pro prvek $3$ je inverzí $6$, protože $3 \cdot 6 = 18 \equiv 1 \pmod{17}$.
Absence dělitelů nuly: V $\mathbb{Z}_{17}$ neexistují dvě nenulová čísla, jejichž součin by byl $0 \pmod{17}$. Díky tomu je tato struktura integritním oborem a zároveň tělesem.
Generátory (Primitivní prvky): Multiplikativní grupa je cyklická. Například prvek $3$ je „primitivním kořenem“ modulo 17 – jeho mocninami lze vygenerovat všech 16 nenulových prvků tělesa.

Tato struktura je základním stavebním kamenem moderní kryptografie (např. v algoritmech Diffie-Hellman nebo v eliptických křivkách), kde se často pracuje právě s tělesy o prvočíselném řádu.

Díky tomu, že je 17 prvočíslo, je „matematicky čisté“. Chtěl(a) byste vidět, jak se v takovém tělesě počítají mocniny (např. kolik je $3^{16} \pmod{17}$), což nás dovede k slavné Malé Fermatově větě?

Menu

Nejnovější příspěvky

Nejnovější komentáře

Archivy

Rubriky

Základní informace