La matematica dietro il protocollo Bitcoin

ONE dei motivi per cui i Bitcoin possono risultare fonte di confusione per i principianti è che la Tecnologie alla base di essi ridefinisce il concetto di proprietà.

Possedere qualcosa in senso tradizionale, che si tratti di una casa o di una somma di denaro, significa averne la custodia personale o affidarla a un ente di fiducia, come una banca.

Protocollo Bitcoin

Con Bitcoin il caso è diverso. I bitcoin stessi non sono archiviati né centralmente né localmente e quindi ONE entità è il loro custode. Esistono come registrazioni su un registro distribuito chiamato blockchain, le cui copie sono condivise da una rete volontaria di computer connessi. "Possedere" un Bitcoin significa semplicemente avere la possibilità di trasferirne il controllo a qualcun altro creando una registrazione del trasferimento nella blockchain. Cosa garantisce questa capacità? L'accesso a un ECDSA coppia di chiavi privata e pubblica. Cosa significa e come protegge Bitcoin?

Diamo un'occhiata sotto il cofano.

ECDSAè l'abbreviazione di Elliptic Curve Digital Signature Algorithm. È un processo che utilizza uncurva ellitticae uncampo finito per "firmare" i dati in modo tale che terze parti possano verificare l'autenticità della firma mentre il firmatario mantiene la capacità esclusiva di creare la firma. Con Bitcoin, i dati che vengono firmati sono la transazione che trasferisce la proprietà.

ECDSA ha procedure separate per la firma e la verifica. Ogni procedura è un algoritmo composto da poche operazioni aritmetiche. L'algoritmo di firma utilizza la chiave privata e il processo di verifica utilizza la chiave pubblica. Più avanti ne mostreremo un esempio.

Ma prima, un corso accelerato sulle curve ellittiche e sui campi finiti.

Curve ellittiche

Una curva ellittica è rappresentata algebricamente come un'equazione della forma:

y2 = x3 + ax + b

Per un = 0 E e = 7 (la versione utilizzata da Bitcoin), si LOOKS così:

Le curve ellittiche hanno proprietà utili. Ad esempio, una linea non verticale che interseca due punti non tangenti sulla curva intersecherà sempre un terzo punto sulla curva. Un'ulteriore proprietà è che una linea non verticale tangente alla curva in ONE punto intersecherà esattamente ONE altro punto sulla curva.

Possiamo usare queste proprietà per definire due operazioni: l'addizione di punti e il raddoppio di punti.

Aggiunta di punti,P + Q = R,è definita come la riflessione attraverso l'asse x del terzo punto di intersezioneR'su una linea che includeP E QÈ più facile capirlo usando un diagramma:

Allo stesso modo,raddoppio dei punti,P + P = Rè definito trovando la retta tangente al punto da raddoppiare,P, e prendendo la riflessione attraverso l'asse x del punto di intersezioneR'sulla curva per arrivareREcco un esempio di come apparirebbe:

Insieme, queste due operazioni vengono utilizzate permoltiplicazione scalare,R = una P,definito aggiungendo il puntoPa se stessoUNvolte. Per esempio:

R = 7P

R = P + (P + (P + (P + (P + (P + (P + P)))))

Il processo di moltiplicazione scalare è normalmente semplificato utilizzando una combinazione di operazioni di addizione e raddoppio di punti. Ad esempio:

R = 7P

R = P + 6P

R = P + 2 (3P)

R = P + 2 (P + 2P)

Qui, ore 7Pè stato suddiviso in due fasi di raddoppio dei punti e due fasi di aggiunta dei punti.

Campi finiti

Un campo finito, nel contesto di ECDSA, può essere pensato come un intervallo predefinito di numeri positivi entro cui ogni calcolo deve rientrare. Qualsiasi numero al di fuori di questo intervallo "si avvolge" in modo da rientrare nell'intervallo.

Il modo più semplice per pensarci è calcolare i resti, come rappresentato dall'operatore modulo (mod). Ad esempio, 9/7 dà 1 con un resto di 2:

9 modulo 7 = 2

Qui il nostro campo finito è modulo 7 e tutte le operazioni mod su questo campo producono un risultato compreso in un intervallo da 0 a 6.

Mettendolo insieme

ECDSA usa curve ellittiche nel contesto di un campo finito, il che ne modifica notevolmente l'aspetto ma non le equazioni sottostanti o le proprietà speciali. La stessa equazione tracciata sopra, in un campo finito di modulo 67, LOOKS così:

Ora è un insieme di punti, in cui tutti iX E ei valori sono numeri interi compresi tra 0 e 66. Si noti che la "curva" mantiene ancora la sua simmetria orizzontale.

L'addizione e il raddoppio dei punti sono ora leggermente diversi visivamente. Le linee tracciate su questo grafico si avvolgeranno attorno alle direzioni orizzontale e verticale, proprio come in un gioco di Asteroids, mantenendo la stessa pendenza. Quindi l'aggiunta dei punti (2, 22) e (6, 25) LOOKS così:

Il terzo punto di intersezione è (47, 39) e il suo punto di riflessione è (47, 28).

Torna a ECDSA e Bitcoin

Un protocollo come Bitcoin seleziona un set di parametri per la curva ellittica e la sua rappresentazione di campo finito che è fissa per tutti gli utenti del protocollo. I parametri includono equazioneusato, ilmodulo PRIMEdel campo, e unpunto baseche cade sulla curva. Ilordine del punto base, che non è selezionato indipendentemente ma è una funzione degli altri parametri, può essere pensato graficamente come il numero di volte in cui il punto può essere aggiunto a se stesso finché la sua pendenza non è infinita, o una linea verticale. Il punto base è selezionato in modo tale che l'ordine sia un numero PRIME grande.

Bitcoin usa numeri molto grandi per il suo punto base, modulo PRIME e ordine. Infatti, tutte le applicazioni pratiche di ECDSA usano valori enormi. La sicurezza dell'algoritmo si basa sul fatto che questi valori siano grandi e quindi poco pratici per la forza bruta o il reverse engineering.

Nel caso del Bitcoin:

Equazione della curva ellittica: y2 = x3 + 7

Modulo PRIME = 2256 – 232 – 29 – 28 – 27 – 26 – 24 - 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Punto base = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Ordine = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Chi ha scelto questi numeri e perché? Una grande quantità diricerca, e una discreta quantità diintrigo, circonda la selezione di parametri appropriati. Dopo tutto, un numero grande, apparentemente casuale, potrebbe nascondere un metodo backdoor per ricostruire la chiave privata. In breve, questa particolare realizzazione è chiamata secp256k1 e fa parte di una famiglia di soluzioni di curve ellittiche su campi finiti proposte per l'uso in crittografia.

Chiavi private e chiavi pubbliche

Con queste formalità fuori dai piedi, siamo ora in grado di comprendere le chiavi private e pubbliche e come sono correlate. Ecco in sintesi: in ECDSA, la chiave privata è un numero scelto in modo imprevedibile tra 1 e l'ordine. La chiave pubblica è derivata dalla chiave privata tramite moltiplicazione scalare del punto base per un numero di volte uguale al valore della chiave privata. Espresso come un'equazione:

chiave pubblica = chiave privata * punto base

Ciò dimostra che il numero massimo possibile di chiavi private (e quindi di indirizzi Bitcoin ) è uguale all'ordine.

In un campo continuo potremmo tracciare la linea tangente e individuare la chiave pubblica sul The Graph, ma ce ne sono alcuni equazioniche realizzano la stessa cosa nel contesto dei campi finiti. Aggiunta di punti dip + qtrovareRè definito componente per componente come segue:

c = (qy - py) / (qx - px)

rx = c2 - px - qx

ry = c (px - rx) - py

E il punto raddoppia per trovareR è il seguente:

c = (3px2 + a) / 2py

rx = c2 - 2px

ry = c (px - rx) - py

In pratica, il calcolo della chiave pubblica si suddivide in una serie di operazioni di raddoppio e addizione di punti a partire dal punto base.

Facciamo un esempio approssimativo usando numeri piccoli, per avere un'idea di come le chiavi sono costruite e utilizzate nella firma e nella verifica. I parametri che utilizzeremo sono:

Equazione: y2 = x3 + 7 (vale a dire, a = 0 e b = 7)

Modulo PRIME : 67

Punto base: (2, 22)

Ordine: 79

Chiave privata: 2

Per prima cosa, troviamo la chiave pubblica. Poiché abbiamo selezionato la chiave privata più semplice possibile con valore = 2, sarà necessaria solo un'operazione di raddoppio di un singolo punto dal punto base. Il calcolo LOOKS il seguente:

c = (3 * 22 + 0) / (2 * 22) mod 67

c = (3 * 4) / (44) mod 67

c = 12 / 44 mod 67

Qui dobbiamo fermarci per un BIT' di gioco di prestigio: come si esegue la divisione nel contesto di un campo finito, dove il risultato deve sempre essere un numero intero? Dobbiamo moltiplicare per l'inverso, che lo spazio non ci consente di definire qui (vi rimandiamo a Qui E Quise interessati). Nel caso in questione, dovrete fidarvi per il momento di noi che:

44-1 = 32

Andiamo avanti:

c = 12 * 32 mod 67

c = 384 modo 67

c = 49

rx = (492 - 2 * 2) mod 67

rx = (2401 - 4) modificato 67

risposta = 2397 mod 67

risposta = 52

ry = (49 * (2 - 52) - 22) mod 67

ry = (49 * (-50) - 22) mod 67

ry = (-2450 - 22) mod 67

ry = -2472 mod 67

ry = 7

La nostra chiave pubblica corrisponde quindi al punto (52, 7). Tutto questo lavoro per una chiave privata di 2!

Questa operazione, ovvero il passaggio dalla chiave privata a quella pubblica, è computazionalmente semplice rispetto al tentativo di procedere a ritroso per dedurre la chiave privata da quella pubblica, il che, sebbene teoricamente possibile, è computazionalmente irrealizzabile a causa degli ampi parametri utilizzati nella crittografia ellittica effettiva.

Pertanto, il passaggio dalla chiave privata a quella pubblica è, per definizione, un viaggio di sola andata.

Come per la chiave privata, la chiave pubblica è normalmente rappresentata da una stringa esadecimale. Ma aspetta, come si fa ad arrivare da un punto su un piano, descritto da due numeri, a un singolo numero? In una chiave pubblica non compressa, i due numeri a 256 BIT che rappresentano il X E ele coordinate sono semplicemente attaccate insieme in ONE lunga stringa. Possiamo anche sfruttare la simmetria della curva ellittica per produrre una chiave pubblica compressa, mantenendo solo la X valore e annotando su quale metà della curva si trova il punto. Da questa informazione parziale possiamo recuperare entrambe le coordinate.

Firma dei dati con la chiave privata

Ora che abbiamo una coppia di chiavi privata e pubblica, firmiamo alcuni dati!

I dati possono essere di qualsiasi lunghezza. Il primo passaggio usuale è quello di eseguire l'hashing dei dati per generare un numero contenente lo stesso numero di bit (256) dell'ordine della curva. Qui, per semplicità, salteremo il passaggio di hashing e firmeremo solo i dati grezzilo. ChiameremoGil punto base, l'ordine eDla chiave privata. La ricetta per la firma è la seguente:

• Scegli un numero intero k compreso tra 1 e n - 1.
• Calcola il punto (x, y) = k * G, utilizzando la moltiplicazione scalare.
• Trova r = x mod n. Se r = 0, torna al passaggio 1.
• Trova s = (z + r * d) / k mod n. Se s = 0, torna al passaggio 1.
• La firma è la coppia (r, s)

Come promemoria, nel passaggio 4, se i numeri danno come risultato una frazione (cosa che nella vita reale succede quasi sempre), il numeratore deve essere moltiplicato per l'inverso del denominatore. Nel passaggio 1, è importante cheionon essere ripetuto in firme diverse e che non sia indovinabile da terzi. Cioè,io dovrebbe essere casuale o generato da mezzi deterministici che sono tenuti Secret da terze parti. Altrimenti sarebbe possibile estrarre la chiave privata dal passaggio 4, poiché, lo,R,ioe sono tutti noti. Puoi leggere di un exploit passato di questo tipoQui.

Scegliamo come dati il ​​numero 17 e Seguici la ricetta. Le nostre variabili:

z = 17 (dati)

n = 79 (ordine)

G = (2, 22) (punto base)

d = 2 (chiave privata)

• Scegli un numero casuale:

k = variabile(1, n - 1)

k = rand(1, 79 - 1)

k = 3 (è davvero casuale? Ok, ci hai beccato, ma renderà il nostro esempio più semplice!)

1. Calcola il punto. Questo viene fatto nello stesso modo in cui si determina la chiave pubblica, ma per brevità omettiamo l'aritmetica per l'addizione e il raddoppio dei punti.

(x, y) = 3G

(x, y) = G + 2G

(x, y) = (2, 22) + (52, 7)

(x, y) = (62, 63)

x = 62

e = 63

1. Trovare R:

r = x modulo n

r = 62 modulo 79

r = 62

1. Trovare :

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 47 modulo 79

e = 47

Nota che sopra siamo stati in grado di dividere per 3 poiché il risultato era un numero intero. Nei casi reali useremmo l'inverso diio(come prima, abbiamo nascosto alcuni dettagli cruenti calcolandoli altrove):

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 141 * 3-1 mod 79

s = 141 * 53 mod 79

s = 7473 modulo 79

e = 47

1. La nostra firma è la coppia (R, ) = (62, 47).

Come per le chiavi privata e pubblica, questa firma è normalmente rappresentata da una stringa esadecimale.

Verifica della firma con la chiave pubblica

Ora abbiamo alcuni dati e una firma per quei dati. Una terza parte che ha la nostra chiave pubblica può ricevere i nostri dati e la nostra firma e verificare che siamo noi i mittenti. Vediamo come funziona.

Con Qessendo la chiave pubblica e le altre variabili definite come prima, i passaggi per verificare una firma sono i seguenti:

• Verificare che r e s siano compresi tra 1 e n - 1.
• Calcola w = s-1 mod n
• Calcola u = z * w mod n
• Calcola v = r * w mod n
• Calcola il punto (x, y) = uG + vQ
• Verificare che r = x mod n. In caso contrario, la firma non è valida.

Perché questi passaggi funzionano? Stiamo saltando la dimostrazione, ma puoi leggere i dettagliQui. Seguici la ricetta e vediamo come funziona. Le nostre variabili, ancora una volta:

z = 17 (dati)

(r, s) = (62, 47) (firma)

n = 79 (ordine)

G = (2, 22) (punto base)

Q = (52, 7) (chiave pubblica)

• Verificare cheRe sono compresi tra 1 e - 1. Controlla e controlla.

numero: 1 <= 62 < 79

numero: 1 <= 47 < 79

1. Calcolareio:

w = s-1 mod n

la = 47-1 mod 79

la = 37

1. Calcolareio:

u = zw mod n

u = 17 * 37 mod 79

u = 629 mod 79

tu = 76

1. Calcolarela:

v = rw mod n

v = 62 * 37 mod 79

v = 2294 mod 79

in = 3

1. Calcola il punto (X,e):

(x, y) = uG + vQ

Analizziamo il raddoppio e l'addizione dei punti intuG E VQ-qualitàseparatamente.

µG = 76G

μG = 2(38G)

μG = 2( 2(19G) )

uG = 2( 2(G + 18G) )

uG = 2( 2(G + 2(9G) ) )

uG = 2( 2(G + 2(G + 8G) ) )

uG = 2( 2(SOL + 2(SOL + 2(4G) ) ) )

uG = 2( 2(G + 2(G + 2( 2(2G) ) ) ) )

Sedetevi un attimo per apprezzare il fatto che usando il trucco del raggruppamento riduciamo 75 operazioni di addizione successive a sole sei operazioni di raddoppio dei punti e due operazioni di addizione dei punti. Questi trucchi torneranno utili quando i numeri diventeranno davvero grandi.

Procediamo dall'interno verso l'esterno:

uG = 2( 2(SOL + 2(SOL + 2( 2( 2(2, 22) ) ) ) ) )

uG = 2( 2(SOL + 2(SOL + 2( 2(52, 7) ) ) ) )

uG = 2( 2(Sol + 2(Sol + 2(25, 17) ) ) )

uG = 2( 2(SOL + 2( (2, 22) + (21, 42) ) ) )

µG = 2( 2(G + 2(13, 44) ) )

uG = 2( 2( (2, 22) + (66, 26) ) )

µG = 2( 2(38, 26) )

μG = 2(27, 40)

μG = (62, 4)

E ora perVQ-qualità:

vQ = 3Q

vQ = Q + 2Q

vQ = Q + 2(52, 7)

vQ = (52, 7) + (25, 17)

vQ = (11, 20)

Mettendoli insieme:

(x, y) = uG + vQ

(x, y) = (62, 4) + (11, 20)

(x, y) = (62, 63)

Chiaramente il passaggio 5 è il grosso del lavoro. Per il passaggio finale,

1. Verificare che r = x mod n

r = x modulo n

62 = 62 mod 79

62 = 62

La nostra firma è valida!

Conclusione

Per coloro che hanno visto tutte le equazioni e sono andati direttamente in fondo, cosa abbiamo appena imparato?

Abbiamo sviluppato una certa intuizione sulla profonda relazione matematica che esiste tra chiavi pubbliche e private. Abbiamo visto come anche negli esempi più semplici la matematica dietro le firme e la verifica diventa rapidamente complicata, e possiamo apprezzare l'enorme complessità che deve essere coinvolta quando i parametri coinvolti sono numeri a 256 BIT . Abbiamo visto come l'applicazione intelligente delle più semplici procedure matematiche può creare le funzioni "trappola" unidirezionali necessarie per preservare l'asimmetria informativa che definisce la proprietà di un Bitcoin. E abbiamo una nuova fiducia nella robustezza del sistema, a condizione che tuteliamo attentamente la conoscenza delle nostre chiavi private.

In altre parole, questo è il motivo per cui si dice comunemente che il Bitcoin è "sostenuto dalla matematica".

Se hai resistito alle parti complicate, speriamo che ti abbia dato la sicurezza di fare il passo successivo e provare la matematica da solo (aCalcolatore aritmetica modularerende la matematica dei campi finiti molto più semplice). Abbiamo scoperto che seguire i passaggi della firma e della verifica dei dati manualmente fornisce una comprensione più approfondita della crittografia che consente la forma unica di proprietà di bitcoin.

Questo articolo è stato ripubblicato qui con il permesso dell'autore. Pubblicato originariamente suCatena.comL'autore ringrazia in modo particolare Steven Phelps per l'aiuto fornito con questo articolo.

Eric Rykwalder è un ingegnere informatico e ONE dei Catena.comfondatori di.