Klíče a podpisy

Hash umí zaručit, že se data nezměnila. Neumí ale říct, kdo je poslal. Na to je druhý pilíř: asymetrická kryptografie. Vyrobíš si dvojici čísel, jedno tajné a jedno veřejné, a s tajným umíš vyrobit podpis, který kdokoli ověří veřejným, ale nikdo jím nedokáže podepsat.

Zní to jako magie. Za osmdesát řádků si to napíšeš.

▶ Spustitelné. Ulož jako podpisy.py a pusť python3 podpisy.py. Běží za desetinu sekundy a nepotřebuje žádnou knihovnu. Je to ta samá křivka, jakou používá Bitcoin.

Odkud se ta jednosměrnost bere

Celý trik stojí na jedné operaci, kterou je snadné udělat a nemožné vrátit.

Vezmi bod na křivce a sečti ho se sebou k krát. Sčítání bodů na eliptické křivce je podivná operace (vedeš tečnu nebo sečnu a bereš třetí průsečík), ale je to jen aritmetika v konečném tělese, takže se spočítá rychle. Výsledkem je jiný bod.

A teď zpátky: znáš oba body a máš zjistit, kolikrát se sčítalo. Tomu se říká problém diskrétního logaritmu a nikdo neumí líp než hádat. U čísel velkých 256 bitů to znamená, že by hádání trvalo déle než existuje vesmír.

Privátní klíč je to náhodné číslo. Nic víc. Veřejný klíč je bod, který z něj vznikne.

Celý program

"""Podpis od nuly na křivce secp256k1, té samé, jakou používá Bitcoin.
Žádná knihovna, jen hashlib ze standardní výbavy Pythonu."""
import hashlib, secrets

# --- parametry křivky secp256k1: y² = x³ + 7  (mod p) ---
P  = 2**256 - 2**32 - 977                                    # velikost tělesa
N  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # řád grupy
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G  = (Gx, Gy)

def scitani(a, b):
    """Sečti dva body na křivce. Tady je celá 'magie' eliptických křivek."""
    if a is None: return b
    if b is None: return a
    if a[0] == b[0] and (a[1] + b[1]) % P == 0: return None      # bod v nekonečnu
    if a == b:
        l = 3 * a[0] * a[0] * pow(2 * a[1], -1, P) % P           # tečna
    else:
        l = (b[1] - a[1]) * pow(b[0] - a[0], -1, P) % P          # sečna
    x = (l * l - a[0] - b[0]) % P
    return (x, (l * (a[0] - x) - a[1]) % P)

def nasobeni(k, bod):
    """k-krát sečti bod se sebou. Zpět se to spočítat nedá, a na tom stojí všechno."""
    vysledek, aktualni = None, bod
    while k:
        if k & 1: vysledek = scitani(vysledek, aktualni)
        aktualni = scitani(aktualni, aktualni)
        k >>= 1
    return vysledek

def hash_zpravy(zprava):
    return int.from_bytes(hashlib.sha256(zprava.encode()).digest(), 'big')

# --- klíče ---
def novy_klic():
    priv = secrets.randbelow(N - 1) + 1        # náhodné číslo, to je celý privátní klíč
    return priv, nasobeni(priv, G)             # veřejný klíč = privátní krát G

# --- podpis ---
def podepis(zprava, priv):
    z = hash_zpravy(zprava)
    while True:
        k = secrets.randbelow(N - 1) + 1       # jednorázové náhodné číslo, NIKDY neopakovat
        bod = nasobeni(k, G)
        r = bod[0] % N
        if r == 0: continue
        s = (pow(k, -1, N) * (z + r * priv)) % N
        if s: return (r, s)

def over(zprava, podpis, pub):
    r, s = podpis
    if not (1 <= r < N and 1 <= s < N): return False
    z = hash_zpravy(zprava)
    w = pow(s, -1, N)
    bod = scitani(nasobeni(z * w % N, G), nasobeni(r * w % N, pub))
    return bod is not None and bod[0] % N == r

if __name__ == '__main__':
    priv, pub = novy_klic()
    print(f'privátní klíč: {priv:x}')
    print(f'veřejný klíč:  ({pub[0]:x},\n                {pub[1]:x})')

    zprava = 'Posilam 10 coinu na adresu Bob'
    sig = podepis(zprava, priv)
    print(f'\npodpis: r={sig[0]:x}\n        s={sig[1]:x}')
    print(f'\nověření originálu:        {over(zprava, sig, pub)}')
    print(f'ověření změněné zprávy:   {over("Posilam 100 coinu na adresu Bob", sig, pub)}')
    priv2, pub2 = novy_klic()
    print(f'ověření cizím klíčem:     {over(zprava, sig, pub2)}')

    # kontrola, ze verejny klic lezi na krivce
    x, y = pub
    print(f'\nleží veřejný klíč na křivce y² = x³ + 7?  {(y*y - x*x*x - 7) % P == 0}')

Co z toho vyšlo

privátní klíč: 1afce6be30b2224fb52a614bdd9fca7f066535bbd51be9cfabaf682b0b419e77
veřejný klíč:  (63d5fc2f2973a04c9c67e31afb9fb34211c79a691302503ff028a5abcb79e3fe,
                398305f2662288276173fb8b854ca6f48c6145efcbb976f081be659c6826c253)

podpis: r=ac079014a80cf67c87eb6936183cb90f369212d1b1a99dc3f0481335776629fe
        s=39cbce1117af55a2088c468cbae9fd34cd879433741b022230913026becdf497

ověření originálu:        True
ověření změněné zprávy:   False
ověření cizím klíčem:     False

leží veřejný klíč na křivce y² = x³ + 7?  True

Tři řádky ověření jsou celá podstata. Podpis platí jen pro tuhle zprávu a jen pro tenhle klíč. Změň ve zprávě jedno slovo a podpis přestane platit, protože se podepisuje hash zprávy a ten se změní celý.

Proč je to přesně to, co potřebujeme na peníze

Všimni si, že tady nikde není žádný server. Nikdo nemusí vést seznam, kdo je kdo. Kdo umí podepsat, ten vlastní. Odtud plyne ta věta „not your keys, not your coins", a plyne z ní doslova, ne jako slogan.

Nejnebezpečnější řádek v celém programu

Podívej se ve funkci podepis na tenhle řádek:

k = secrets.randbelow(N - 1) + 1       # jednorázové náhodné číslo, NIKDY neopakovat

To k musí být pokaždé jiné a nepředvídatelné. Pokud stejné k použiješ na dvě různé zprávy, dá se z těch dvou podpisů spočítat privátní klíč. Není to teoretická slabina, je to pár řádků algebry: máš dvě rovnice o dvou neznámých a ta druhá neznámá je tvůj klíč.

Přesně takhle přišla v roce 2010 herní konzole PlayStation 3 o svůj podpisový klíč: výrobce použil konstantu místo náhody. A stejná chyba vybílila několik bitcoinových peněženek na Androidu, kde byl generátor náhody rozbitý.

Proto se dnes doporučuje deterministické k podle RFC 6979, které se počítá z hashe zprávy a klíče. Vyjde vždy jiné pro jinou zprávu a nepotřebuje k tomu generátor náhody.

Cvičení

1. Ve výstupu je hodnota s součástí podpisu. Co se stane, když ji o jednu zvětšíš a zkusíš ověřit? Zkus to.
2. Proč se podepisuje hash zprávy a ne zpráva samotná?
3. Máš dva podpisy od téhož klíče se stejným r. Co ti to prozradí a proč?

Shrnutí

• Privátní klíč je jen náhodné 256bitové číslo, veřejný klíč je bod, který z něj vznikne.
• Zpět to nejde: problém diskrétního logaritmu na eliptické křivce nikdo neumí řešit.
• Podpis platí jen pro jednu konkrétní zprávu a jeden konkrétní klíč.
• Vlastnictví v blockchainu neznamená zápis v evidenci, ale schopnost podepsat.
• Opakované jednorázové číslo k vyzradí privátní klíč. Proto RFC 6979.