Topic: curve ellittiche e algoritmo ECDSA - page 4. (Read 25659 times)

Non credo sia possibile fare altrimenti. Il problema è tutt'altro che banale! Una trattazione completa richiede sicuramente competenze difficili da spiegare a chi, come me, ha conoscenze lacunose e frammentate, intanto io cerco di capire e ti sfrutto ... ogni volta arrivo ad un livello di comprensione differente ...
Chiamo ZERO il punto ad infinito ...
Appurato che calcoli tipo (5, 0)+(5,0)=ZERO o anche che ad un certo punto io arrivo ad uno zero, ossia n*G=ZERO allora da quel valore di n in avanti ritroveremo la sequenza iniziale e quindi mi sa che il gruppo è inutilizzabile o sbaglio?
in formule, parto da G:
1*G
2*G
...
n*G=ZERO
(n+1)*G=n*G+G=ZERO+G=G
2*G
...
ossia, si ricomincia ...  l'insieme delle chiavi sarebbe pertanto limitato ad "n" e non ad un valore simile alla base del modulo.
Forse la scelta di G deve essere fatta in modo da massimizzare questo valore? Ci deve essere una bella scatola di vermi dentro questo concetto ...

Dovevo specificare che:

Se A diverso da B, e xA = xB allora A+B = 0 (punto all'infinito), quindi in tal caso non si applica la formula della somma di due punti (semplicemente una retta verticale non ha coefficiente angolare, quindi è inutile tentare di dividere per 0)

Se A = B, e yA=0 allora A+B=2A = 0 (punto all'infinito), quindi in tal caso non si applica la formula di duplicazione

Nel caso specifico di D(5,0) siamo nel secondo caso (che è a sua volta un caso particolare del primo caso). Quel punto è anche l'opposto di se stesso - poichè 2 punti sono opposti se e solo se hanno stessa x e y opposta (se (x,y) soddisfa l'equazione di Weierstrass la soddisfa evidentemente anche (x,-y)); nel caso di ordinata nulla se (x,0) soddisfa l'equazione di Weierstrass, se mantengo la x e cambio "segno" alla y trovo ancora (x,0), quindi (x,0)+(x,0) = 0 sempre!

Purtroppo ho saltato diverse precisazioni...

Sto cercando di simulare queste operazioni, subito casini ...
Se devo fare D+D=2D mi trovo a denominatore 2y_D=0 che non ha inverso. Come ci si comporta?
Inoltre, quando sommo due elementi che hanno stessa x, ho lo stesso problema, in questo caso credo si arrivi al punto ad infinito che corrisponde allo zero. Ma nel caso di D(5, 0) non mi pare ricada nello stesso caso altrimenti il gruppo avrebbe 2 zeri differenti e non mi pare sia possibile.

La definizione rigorosa di curva ellittica non è banale, si tratta di una curva proiettiva liscia i cui punti soddisfano una certa equazione detta equazione di Weierstrass generalizzata.

"proiettiva" ha a che fare con il fatto che dobbiamo aggiungere il punto all'infinito, "liscia" vuol dire non singolare, cioè deve essere derivabile in ogni punto, senza spigoli (altrimenti non sarebbe definita la tangente in ogni punto)

Si può dimostrare che quasi ogni curva ellittica può essere descritta da un tipo di equazione più semplice detta equazione di Weierstrass:


ECDSA come dice il nome stesso (Elliptic Curve Digital Signature Algorithm) è solo un algoritmo di firma, quindi serve solo a firmare e a verificare la firma.

Se vuoi però utilizzare le curve ellittiche anche per cifrare i messaggi esistono anche algoritmi di cifratura come ad esempio  l' ECIES (Elliptic Curve Integrated Encryption Scheme) che trovi a pag.99-100 sempre della tesi.

Domanda forse banale ma ... intanto spero di riuscire a spiegarmi ...
ECDSA serve solo per firmare o posso anche crittare messaggi "da" e "verso" le due chiavi in modo "scambiabile"?

Per produrre una firma, oltre alla chiave privata e al messaggio da firmare, è necessario generare ogni volta un numero casuale. Se firmi due messaggi per mezzo della chiave privata utilizzando sempre lo stesso numero "casuale", è banale ricavare dalla firma la chiave privata.
Questo è il motivo per cui è necessario avere un buon generatore di numeri pseudo casuali, non solo per generare buone chiavi private, ma anche per poter firmare in sicurezza senza esporre la chiave privata (che è poi il senso generale della firma).

Per quanto riguarda l'algoritmo ECDSA, sto preparando la spiegazione!

[/quote]
Ti segnalo http://kakaroto.homelinux.net/2012/01/how-the-ecdsa-algorithm-works/ che spiega come hanno hackerato la PS3 sfruttando un baco dell'implementazione da parte di sony ... poi corretto.
Se ho capito sony usava sempre uno stesso numero che dovrebbe essere casuale, assomiglia alla chiave privata, e serve per firmare un documento. Con qualche formula inversa sono arrivati alla chiave privata. Cita i passaggi ma non ho ancora potuto analizzarli meglio. Non so se sono giusti.

Interessante, non solo ci sono molti meno indirizzi bitcoin (2^160) ma addirittura ogni chiave privata ne controlla 2... non hanno pensato di imporre la rappresentazione compressa prima di calcolare l'address BTC?
Esagerazione: Non e' che poi alla fine facciamo la fine degli IPv4 che alla fine non bastano?

Ho migliorato nel post 1 la presentazione di G, aggiungendo anche il controllo che effettivamente appartenga alla curva secp256k1.

Ho anche aggiunto una precisazione alla risposta alla tua domanda sulla corrispondenza biunivoca tra chiavi private e pubbliche nel post 14.

Io intendevo, in maniera ancora più radicale, si potrebbe evitare proprio (a livello teorico, ovviamente sarebbe scomodissimo) di utilizzare il concetto di firma e quindi i comandi tipo OP_CHECKSIG.  
Alla fin dei conti sarebbe sufficiente scrivere uno script con i comandi consentiti dalla sintassi del linguaggio SCRIPT e farne l'hash. Mi riferisco al concetto di P2SH (pay to script hash).


Ad esempio: scrivo uno script del tipo

"fornisci l'hash del blocco 1000 e confrontalo con 0000125...."

oppure

"x + 10 = 30, fornisci x"

poi ne faccio l'hash e ripemd160 e la stringa che ottengo diventa il mio "indirizzo", l'analogo della stringa da 160 bit che ottengo facendo sha256 e poi ripemd160 partendo dalle coordinate di un punto sulla curva ellittica.

Prima della versione 0.9.2 di Bitcoin Core, di fatto si utilizzava questa modalità solo per gli indirizzi multisig, ora è permessa tutta la flessibilità consentita dal linguaggio SCRIPT.

PS: ovviamente vincolare dei fondi a uno script come quello proposto da me sopra non avrebbe senso alcuno, poichè qualora volessi sbloccare quei fondi dovrei trasmettere alla rete una transazione con lo script in chiaro il cui hash256 corrisponde al mio indirizzo + il dato richiesto per lo sblocco, e quindi sarebbe facilissimo sostituire la mia transazione modificando al volo il destinatario prima che essa sia inclusa in un blocco.
Il concetto di firma è proprio quello di poter generare una stringa con la quale dimostrare di avere la chiave privata senza bisogno di renderla pubblica.
Il senso del mio discorso era che il sistema bitcoin fondamentalmente lavora con coppie di stringhe A e B, la stringa/indirizzo B con la funzione di vincolare i btc all'indirizzo/stringa B, la stringa A con la funzione di svincolare i btc dall'indirizzo B. Nel caso delle curve ellittiche, A è la chiave privata, B l'hash della chiave pubblica, ma non è strettamente necessario che sia così.
 

piu' o meno si... nel senso che il merkle tree di bitcoin funzionerebbe con qualsiasi altro sistema di crittografia, pero' fu scelto ECDSA perche
attualmente e' uno di quelli che garantisce alti livelli di sicurezza con chiavi corte... ad esempio con gli algoritmi basati su fattorizzazione tipo  RSA servono 1024 bit o piu' per
avere livelli decenti di sicurezza.... questo sarebbe drammatico per le dimesnioni della blockchain che gia' e' bella pesa...

Inoltre nei client adesso c'e' implementato tutto il codice per la ECDSA

ad esempio la OP_CHECKSIG fa il check presupponendo implicitamente questo particolare modo crittografia,
ossia non ha un parametro che dice "controlla usando  RSA" oppure "controlla usando il sistema di crittografia x"
quindi ci sarebbe da implementare pesantemente sui client .... ma teoricamente e' possibile.

Per quanto riguarda l'algoritmo ECDSA, sto preparando la spiegazione!

Non avevo mai pensato al funzionamento del vanity gen, in effetti dovrebbe essere proprio come lo hai descritto!



Sì, una volta scelto il punto base G, detto per questo anche punto generatore di E(FP), c'è una corrispondenza biunivoca tra l'insieme dei naturali compresi tra 1 e n-1 e i punti della curva

Si fissa G (è stato scelto "Standards for Efficient Cryptography" (SEC), vedi http://www.secg.org/sec2-v2.pdf a pagina 9).
Fissato G, è univoco l'ordine con cui percorrere tutti i punti della curva:

1 --> G
2 --> 2*G
3 --> 3*G
..
..
n-1 --> (n-1)*G


la prima colonna è quella delle chiavi private (scalari)
la seconda colonna è quella delle chiavi pubbliche corrispondenti (punti di E(Fp)) (NB: lo scalare 0 non è considerato una chiave privata accettabile nel protocollo bitcoin, quindi 0*G ( o n*G, che è lo stesso) non lo ho inserito nelle possibilità.)

Per ogni chiave privata c'è un'unica chiave pubblica e viceversa.

Le 2 colonne hanno entrambe n-1 elementi (sono circa 2^256, un po' di meno di p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 che è l'ordine del campo delle coordinate). La corrispondenza biunivoca tra i due insiemi è garantita dalla matematica che ho spiegato nei post precedenti (E(Fp) è un gruppo ciclico, l'elemento G è un generatore che permette di riottenere tutti gli altri punti)

La corrispondenza però non è più biunivoca se aggiungiamo una terza "colonna", quella degli indirizzi, che non c'entrano però con le curve ellittiche.

insieme scalari (fissato G)     <-->    insieme di punti di E(Fp)  -->   indirizzi


L'insieme degli indirizzi ha circa 2^160 elementi distinti possibili. Per passare dall'insieme E(Fp) all'insieme degli indirizzi ci sono 2 operazioni, un hash256 e un ripemd160 che traducono una stringa di 256 bit in una di 160 bit (la quale viene poi rappresentata in base 58, ma questo è solo un problema appunto di rappresentazione del risultato finale).

Quindi ci sono tantissime chiavi private (con relative chiave pubbliche) che producono lo stesso indirizzo.***

***EDIT2: in realtà c'è anche un altro problema quando traduciamo un punto della curva in un indirizzo. Poichè la funzione hash lavora in modo stupido solo sulla rappresentazione del punto, se scriviamo un punto di E(Fp) nella sua forma compressa (cioè con solo la coordinata x e il "segno" della y, aggiungendo come prefisso 02 se y è pari e 03 se y è dispari), avremo che lo stesso punto può essere tradotto in due indirizzi completamente diversi (ma controllati sempre dalla stessa chiave privata)

Riporto qui il passo dedicato alla questione in "Mastering Bitcoin"


EDIT: a voler essere pignoli, per ottenere un indirizzo è sufficiente sostituire nel meccanismo una qualsiasi stringa di 256 bit al posto dell'hash256 delle coordinate di un punto della curva ellittica. Non vorrei dire una stupidaggine ma penso che il sistema bitcoin - blockchain sia del tutto indipendente dalla teoria delle curve ellittiche e dall'algoritmo di firma digitale ECDSA.

Riflettendo ora risulta molto chiaro il funzionamento dei vanity gen che permettono di essere sicuri.
Basta dare chiave pubblica e il miner vanity somma G alla chiave k volte fino ad ottenere l'indirizzo desiderato, comunica k al proprietario della chiave privata "n" e genera un indirizzo privato n+k  che magicamente diventa il vanity richiesto.

Dubbi residui:
- come critto un messaggio? Ossia poi, di fatto, come funziona?
- l'applicazione che porta da "private key" a E(Fp) è iniettiva? (in caso sarebbe anche suriettiva visto che hanno lo stesso numero di elementi).
NB: Gran tread! Grazie.

Scritto cosi' non si capisce bene, magari usa (Gx, Gy) tipo:
G =(79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,  483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8).

CIao
P
EDIT: sto punto G l'ho gia' sentito da qualche parte e mi pare sia anche quello un punto di partenza ma non ricordo dove ...

Avevo copiato da Word e in effetti non si capiva molto. Guarda adesso se si capisce.

Non capisco i simboli 〖 ... 〗si puo' riscrivere senza?

A queste due domande ho tentato di rispondere nei post 4 e 5 di questo thread.



Certo, si basa proprio su n*(a,b), si tratta in sostanza di dividere n in 2^m passi e applicare ricorsivamente la formula di duplicazione 2*(a,b) (però per essere più preciso devo andare a cercarlo)

Vediamo se riesco a comporre una domanda formalmente corretta. Sarebbe già un buon inizio ...
- come viene definita la somma nel gruppo E(K) tra le coppie (a, b) e (c, d) con a, b, c, d in K?
- qual'è l'elemento neutro del gruppo E(K) rispetto alla somma?
- esiste un algoritmo per calcolare n*(a, b) con n, a, b in K, senza fare (a, b) + (a, b) ... + (a, b) n volte?

Intanto grazie del 3d.
Faccio le domande come a scuola ... ne approfitto!
In giro si trova che dipende da solo due parametri, in pratica https://en.wikipedia.org/wiki/Elliptic_curve indica solo i tuoi B=a, C=b mentre A=1, y^2 ha coefficiente 1 in entrambe. Sono equivalenti le trattazioni?

• Crittografia e algoritmo ECDSA
  
  • Generazione di una chiave pubblica da una chiave privata
  • Firma digitale di un messaggio mediante una chiave privata
  • Verifica della firma digitale mediante la chiave pubblica
  • Esempio pratico di firma di un messaggio e verifica utilizzando l'algoritmo ECDSA applicato alla curva secp256k1
  • Libreria micro_ecdsa
  • Esempio pratico di firma di una transazione bitcoin

Crittografia e algoritmo ECDSA

La crittografia viene utilizzata per rendere possibili uno dei due seguenti scenari:

1.   A vuole mandare un messaggio segreto a B, in modo che solo B possa leggerne il contenuto (A deve codificare un messaggio mediante una chiave pubblicata da B e quindi nota a tutti, inviarlo a B che lo decodifica mediante la chiave privata che "inverte" l'azione di quella determinata chiave pubblica; in tutto questo processo il messaggio rimane segreto al resto del mondo)

2.   A  vuole inviare un messaggio pubblico a B; poichè il messaggio è pubblico A deve tutelare se stesso (e B) dal fatto che qualcun altro si interponga tra A e B e possa modificare il nome del mittente del messaggio o qualunque altra parte del messaggio stesso (A firma il messaggio con la sua chiave privata, lo invia a B che verifica a sua volta con la chiave pubblica relativa che il messaggio sia stato effettivamente firmato da chi possiede la chiave privata relativa e non sia stato modificato, in tutto questo processo il messaggio è sempre visibile al resto del mondo)

Nel sistema Bitcoin i messaggi si chiamano transazioni (perchè spostano del valore - rappresentato dalla moneta Bitcoin - da un utente a un altro). Quindi d'ora in poi considereremo i termini "messaggi" e "transazioni" come sinonimi.   Poichè tutte queste transazioni devono essere pubbliche, la crittografia nel sistema Bitcoin viene utilizzata per rispondere alle esigenze evidenziate nello scenario 2, cioè viene utilizzata per certificare di fronte a tutto il mondo che una transazione sia stata effettivamente effettuata dall'autore dichiarato nel messaggio e che la transazione non sia stata manomessa in alcuna sua parte.

Il metodo crittografico scelto per certificare le transazioni nel mondo dei Bitcoin si basa su un algoritmo di firma digitale che lavora con curve ellittiche detto ECDSA (Elliptic Curve Digital Signature Algorithm).

Le curve ellittiche entrano in scena nelle seguenti tre situazioni:

•   GENERAZIONE DI UNA CHIAVE PUBBLICA A PARTIRE DA UNA CHIAVE PRIVATA: quando si genera un indirizzo di un portafoglio; l'algebra delle curve ellittiche è alla base del meccanismo che permette di ricavare da una chiave privata una chiave pubblica; la chiave pubblica viene poi trasformata con un ulteriore passaggio (vedi http://gobittest.appspot.com/Address) in un indirizzo Bitcoin

•   FIRMA DIGITALE DI UNA TRANSAZIONE/MESSAGGIO CON LA CHIAVE PRIVATA: quando A deve effettuare un pagamento; A deve firmare mediante la propria chiave privata la transazione/messaggio di pagamento, per certificare in modo visibile a tutti la validità di questo atto di pagamento; la firma di A è necessaria per muovere dei fondi da un certo indirizzo, questa firma è ottenuta applicando in modo appropriato la chiave privata alla transazione (o meglio: al doppio hash della transazione) da eseguire

•   VERIFICA DELLA FIRMA DIGITALE MEDIANTE LA CHIAVE PUBBLICA: quando un nodo della rete, addetto alla convalida delle transazioni, alla trasmissione di quest'ultime alla rete e alla loro registrazione in un registro pubblico detto "block chain", deve verificare mediante la chiave pubblica che la transazione sia stata firmata effettivamente dalla chiave privata corrispondente (pur senza conoscerla) e che la transazione non sia stata modificata in alcuna sua parte



Generazione di una chiave pubblica a partire da una chiave privata


Si fissa un punto G della curva (che nel caso della secp256k1 è stato fissato dalla SEC), si sceglie un numero casuale d tra 1 e n - 1 (dove n è l'ordine di G), e si ottiene così la chiave pubblica P = d*G.

Facciamo un esempio nel caso semplificato di

E(F_11 )={(2,2),(2,-2),(3,1),(3,-1),(4,4),(4,-4),(5,0),(6,5),(6,-5),(7,3),(7,-3)}  ∪ {O}

Scegliamo un punto base. Proviamo con A = (2,2)

Osserviamo che o(A) = 4  (l'ordine di A) infatti

A+A=2*A=D    (vedi calcolo effettuato in precedenza,  D(5,0) )

A+A+A=3*A=2*A+A=D+A=A'



A+A+A+A= 4*A = 3*A+A = A'+A = O

Poichè A ha ordine un numero non primo, non è un buon candidato per essere scelto come punto base. (NB: in questo caso o(A) = 4, quindi il cofattore o(E) : o(A) sarebbe uguale a 3 )

Proviamo con B = (3,1). Si può verificare che esso ha periodo 12, cioè B genera tutto E(F_11) ( = E(F_11)) (NB: in questo caso il cofattore è 1, così come succede per la curva secp256k1, da ciò si deduce che E(F_11) è un gruppo ciclico, anche se non ha un numero primo di elementi).

Quindi:

E = E(F_11)  

G (il punto base della curva) = B

d (la chiave privata) = 4 (numero scelto a caso tra 1 e 11)

P (la chiave pubblica corrispondente a d=4) = 4*B = 2*(2*B) = (3,-1) .

---

Firma digitale di un messaggio mediante una chiave privata

Che cos'è una firma? E' una coppia di numeri r , s  (entrambi di lunghezza max 256 bit, minori di n) che si ottengono a partire da:

il messaggio m** , la chiave privata d, un numero casuale k

**ciò che si firma realmente non è il messaggio originale, ma una sua "impronta digitale" (detta "message digest", una stringa di 256 bit), impronta che è il risultato di un doppio hash del messaggio originale; nel caso particolare in cui si firma non un messaggio qualunque ma una transazione è da sottolineare come si effettua il doppio sha256 della transazione quando essa è ancora in una forma incompleta e non definitiva (è chiaro che nel momento in cui si firma una transazione la firma stessa non può essere già presente nella transazione stessa! Quindi a rigore in quel caso non si firma neanche tutto il messaggio, messaggio che però deve alla fine contenere anche la firma come sua parte essenziale --> a sottolineare la natura "spuria" della firma rispetto al resto della transazione è recentemente intervenuto il soft fork "segregated witness" (firma separata), dove di fatto la firma viene considerata una parte a se stante della transazione ed è trattata in modo particolare.

Quote from: BurtW on August 10, 2013, 05:53:13 PM

Algoritmo di verifica della firma

Date la coppia di firme (r, s) del messaggio m and la chiave pubblica P:

1.  Controllare che r e s appartengano entrambi all'intervallo [1,n-1]

2.  Calcolare e = hash(m)    

3. Calcolare w = s^-1  mod n
(qui si utilizza la seconda parte della firma)
  
4. Calcolare  u1 = e*w mod n,     u2 = r*w mod n
(qui si utilizza il messaggio m e la seconda parte della firma per u1, entrambe le parti della firma per u2)

5. Calcolare il punto X = (x0,y0) =  u1*G + u2*P  
 (se X è il punto all'infinito rifiuta; questo è il punto dove si utilizza la chiave pubblica P )

6. Convertire x0 in un intero e porre  v = x0 mod n.

7. Confronta v e r, se v = r allora la firma è corretta.

------------------------------------------------------------------------------------------------------------
Dimostriamo perchè questa verifica è corretta:

Notiamo innanzitutto che k = u1+u2*d, infatti:

k = s^-1 * (e + r*d)  (vedi punto 4 dell'algoritmo di firma)
  = s^-1*e + s^-1 * r*d = u1 + u2*d  mod n  (ricordiamo che   u1=s^-1*e ,  u2=s^-1*r )

Quindi X = u1*G + u2*P = u1*G + u2*d*G = (u1+u2*d)*G = k*G = X1  (ricordiamo che P = d*G ,  X1 = k*G),     ovvero X = X1
-------------------------------------------------------------------------------------------------------------

Nota bene: chi verifica non calcola mai esplicitamente nè k nè d, queste due informazioni rimangono sempre ignote;
chi verifica spezza il percorso che lo porta a X in due parti, cioè decompone k che non conosce in due parti:  k = u1 + u2*d  (il verificatore calcola solo u1 e u2, non conosce d e quindi nemmeno k!)

u1 = s^-1*e (termine che usa il contributo del messaggio e serve  per muoversi dal generatore G verso X)
u2 = s^-1 * r (questa parte serve per muoversi da P invece che da G sempre per raggiungere X; in questo modo il risultato corretto è ottenuto pur non conoscendo la chiave privata d)

Il verificatore grazie a s, che condensa diverse informazioni, riesce a determinare i seguenti due punti,
                                                           A = u1*G    e    B = u2*P
la somma di questi due punti deve dare finalmente X

Alla fine si ottiene quindi che il verificatore ha ricostruito con le informazioni in suo possesso l'identità del punto X che coincide con il punto X1 da cui è partito colui che ha fatto la firma, quindi x0 = x1  ( v = r   mod n )

Riassumendo:

chi fa la firma determina un punto X casuale e fornisce pubblicamente la posizione di X (prima parte della firma), il messaggio, la chiave pubblica e un valore s (seconda parte della firma) che dipende dalla posizione di X, dal messaggio e dalla chiave privata d

chi verifica l'autenticità del messaggio, verifica se, partendo dalla seconda parte della firma s, riesce a invertire il processo per riottenere la prima parte della firma r (che corrisponde alla posizione di X, già nota); per invertire questo processo deve utilizzare due informazioni base: il messaggio m e la chiave pubblica P.



Note finali:

1) quando si firma un messaggio vero e proprio (non una transazione) con un client bitcoin tipo Bitcoin Core viene richiesto esplicitamente di inserire l'indirizzo di chi sta firmando. Bitcoin Core infatti provvede a recuperare la chiave privata associata all'indirizzo in automatico (NB: è possibile firmare solo con un indirizzo di cui si possiede la chiave privata!).
Anche nel caso della verifica, però, viene richiesto solo l'indirizzo, non la chiave pubblica. Ma come è possibile recuperare la chiave pubblica dall'indirizzo? In generale non è possibile. Però nel caso in cui si abbiano a disposizione, oltre all'indirizzo, la firma e il messaggio stesso allora si può ricostruire la chiave pubblica, infatti:

               X = u1*G + u2*P -->  X = s^-1*e*G + s^-1*r*P  

in quest'ultima equazione il destinatario del messaggio che deve effettuare la verifica ha a disposizione tutti i valori tranne uno,  P, che costituisce quindi l'incognita dell'equazione e che si ricava quindi in funzione degli altri dati:

s*X = e*G + r*P
r*P = s*X - e*G
                                P = r^-1 (s*X - e*G)

A questo punto chi verifica si limita a trasformare la chiave pubblica P nell'indirizzo corrispondente e a controllare infine se quest'ultimo coincide con l'indirizzo che gli è stato trasmesso.

Quindi nel caso di un messaggio normale firmato con una chiave bitcoin la verifica non consiste più nel ricavare r a partire da s e da P (oltre che da m), ma invece consiste nel ricavare la chiave pubblica P dalla firma r,s (e dal messaggio m) e nel confrontare quindi l'indirizzo che P genera con quello inviato in chiaro dal firmatario.

2) se (r,s) è una firma valida per il messaggio m, lo è anche (r,-s)  (sostanzialmente il verificatore che parte da -s trova -X1, ma due punti opposti X1 e -X1 hanno sempre la stessa ascissa, quindi anche da -s si riottene sempre r).

Questo fatto consentiva, fino a qualche tempo fa, di prendere una transazione che arrivava nella mempool (quindi una transazione non ancora confermata) e modificare il segno di s. Questa modifica non cambiava di una virgola address di partenza, importo e address di arrivo della transazione, ma provocava un cambio del TXID (cioè del codice identificativo della transazione), che è un hash della transazione intera, firma compresa. In questo caso si parla di "Transaction Malleability".

Bitcoin Core dalla versione 0.11.1 non consente più questa flessibilità che poteva portare problemi:

Quote

Inherent ECDSA signature malleability We require that the S value inside ECDSA signatures is at most the curve order divided by 2 (essentially restricting this value to its lower half range). See reference: Low S values in signatures

quindi all'algoritmo della firma, per precisione, va aggiunto adesso un ulteriore passaggio:

se s è maggiore di (n+1)/2 allora sostituisci s con (n - s)

le versioni più recenti di Bitcoin Core non propagano più quindi transazioni nelle quali le firme presentano una s maggiore di (n+1)/2.

---

Esempio pratico di firma e verifica utilizzando l'algoritmo ECDSA applicato alla curva secp256k1