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

ok ma qui è invertito l'ordine: è appunto la parte in grassetto che non capisco come si dimostra. Come dimostri che per ogni a < p, esiste b < p t.c. a x b = 1?
Avevo letto da qualche parte che la stessa cosa vale per altri tipi di anelli che non sono campi finiti, ad es. definendo:

Z'n = 0 U {a: 0 < a < n, MCD (a, n) = 1}

cioè anche con n che non è primo, se a ed n sono primi fra loro.

Si può dimostrare che Zn è un campo finito se e solo se n è primo.

Al momento mi ricordo solo come si fa a dimostrare che se n non è primo, allora Zn non è un campo.

Premessa:
in un campo qualsiasi deve valere la legge di annullamento del prodotto, ovvero a x b = 0 implica necessariamente che almeno uno tra a e b sia uguale a 0.

Infatti se per assurdo a x b = 0 con a,b entrambi diversi da 0, posso moltiplicare entrambi i membri per b^-1 (ogni elemento diverso da 0 ha il suo inverso in un campo):

a x b x b^-1 = 0 x b^-1

a x 1 = 0

a = 0 che va contro l'ipotesi che a sia diverso da 0.
 


Tornando a Zn, se n non è primo, allora n = a x b, con a,b diversi da 0.

Ma Zn = {0, 1, 2, ..., n -1} è definito come l'insieme delle classi dei resti modulo n ovvero n = 0 in Zn.

Quindi se n non è primo, è possibile trovare due numeri diversi da 0 il cui prodotto fa 0, ma in un campo la legge di annullamento del prodotto deve valere sempre, quindi si conclude che Zn non è un campo.


EDIT: aggiungo inoltre che ogni campo finito Fq ha necessariamente p^n elementi, dove p è un numero primo. Ogni campo finito contiene un sottocampo finito di p elementi isomorfo a Zp, e tutti i campi finiti di p elementi sono isomorfi a Zp (link)

Ti ringrazio per la guida, anche se in ritardo... purtroppo non so quando riuscirò mai a trovare in tempo per studiarmi per bene l'argomento.

Una cosa però avevo provato a studiarla ma non l'ho mai capita: come fai a dimostrare che l'insieme dei numeri interi non negativi e minori di p (numero primo) sia un campo finito? Ovvero, come dimostri che per ogni elemento di quell'insieme esiste un inverso, anch'esso nello stesso insieme?

Dopo quasi 3 anni mi sono deciso a continuare questo thread, aggiungendo le parti relative alla firma di un messaggio (già fatta) e la firma di una transazione bitcoin (ancora da fare).

Si tratta di una sezione più operativa, con esempi di codice in python funzionanti (tranne casi particolari che non affronterò).

Ricordo comunque che si tratta di materiale a scopo didattico, solo per imparare, non usate questi software per cose serie.

Questo il link al nuovo thread (continuazione di questo):

https://bitcointalksearch.org/topic/ecdsa-parte-2-firma-di-un-messaggio-e-di-una-transazione-bitcoin-5091462

Ho inserito un indice (all'inizio del primo post) per mettere un po' di ordine in questo thread.

Ho aggiunto anche la parte relativa alla firma e alla verifica, più avanti vedo di inserire magari anche qualche esempio specifico.

Ok, grazie. Se ti capita fai presente che potrebbe servire, immagino non saremo i soli con l'esigenza di scrivere in matematichese

@picchio
Non ho modo/poteri io di farlo, e comunque non ci saranno modifiche/aggiunte a questa versione del forum, è da più di un anno che stanno lavorando a creare una versione nuova.

Per quanto riguarda la scelta dei sei parametri che definiscono la curva secp256k1 (tra tutte le curve ellittiche possibili):


n dovrebbe discendere di conseguenza, come h e anche a e b.

Nulla si sa invece del criterio di scelta di G.

Provo a segnalare a HostFat la cosa, immagino sia un plugin da abilitare, dubito lo facciano in quanto ogni aggiunta e' un rischio di attacco ... vediamo se interviene.

Che tu sappia si può inserire latex nei post del forum? Io so per esempio che su mathstackexchange è possibile

http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference

ma dubito che si possa fare anche qui su bitcointalk.

OT: Ogni volta che vedo un documento scritto in LaTex mi viene voglia di re-imparare questo strumento eccezionale.
A mio avviso andrebbe imparato e potrebbe anche risolvere tanti problemi .. ad esempio radunare le idee di questo 3d in latex permetterebbe (credo) un utilizzo delle info contenute in modo comodo e utile. Qualcuno lo conosce?

Letture consigliate:


http://www.math.vt.edu/people/brown/doc/ellip.pdf   (Da dove vengono queste curve ellittiche? Che connessione hanno con l'ellisse? Quale tipo di problemi permettono di affrontare in teoria dei numeri?)

http://www.math.brown.edu/~jhs/Presentations/WyomingEllipticCurve.pdf (Un'ottima presentazione delle curve ellittiche stile PowerPoint di una summer school; vi sono molte rappresentazioni grafiche delle curve)

Certo, ma visto che il nostro problema è definire un'operazione tra punti della curva, delle rette che non intersecano la curva non ci importa nulla.

La retta x=x_1 che passa per il punto di coordinata x_1 è il caso limite, e poichè essa è tangente alla curva in quel punto A, è come se incontrasse in due punti "coincidenti" la curva; in quel caso si ha :


( A in questo caso è opposto a se stesso, tutti i punti che stanno sull'asse x sono opposti a se stessi, come nel caso D(5,0) di E(F11) )


Questo succede perchè in tal caso a e p sono sempre coprimi (hanno MCD = 1 in quanto p appunto è primo). Quindi, poichè per ogni coppia di numeri naturali a,b vale la formula:


segue che per la coppia a,p con a

Inizialmente avevo pensato di moltiplicare tra loro semplicemente gli scalari; cioè, fissato il generatore G, supponiamo A=3*G , B=7*G, definisco A*B=(7*3)*G=21*G

Il problema è che questa operazione dipende dal generatore scelto e quindi dal modo di ordinare i punti rispetto al generatore; per esempio si avrebbe che ogni punto A moltiplicato per G  darebbe come risultato sempre A ( poichè qui G vale come 1, l'elemento neutro della moltiplicazione) ma se scegliessi viceversa A come generatore, si avrebbe allora A*G = G.
Un'operazione per essere ben definita non può produrre risultati diversi a seconda del modo con cui si rappresentano e indicano gli elementi su cui opera.

Ci possono anche essere rette con zero intersezioni e sono quelle del tipo x=k con k minore di x_1 (x_1  lo zero a sinistra dell'equazione x^3 + ax + b=0).
Anche io trovo affascinante il fatto che le proprietà si trasmettano dal reale al discreto e anche che valga la proprietà associativa (A+B)+C=A+(B+C).
Devo ancora analizzare bene quanto hai scritto ... intanto dico (come al solito) quello che mi rifrulla per la capa ...
Aggiungo: non avevo mai pensato al fatto che sommando numeri "a" minori di p in algebra modulo p (a>0) si ottengono tutti i numeri da 1 a (p-1) che poi è quello che succede nelle curve ecdsa "utili".
EDIT: se p è primo!
Il bello/brutto di questa matematica è che è maledettamente astratta e faccio una fatica bestia a starci dietro.

Ho riscritto in gran parte il post precedente dal momento che non ero soddisfatto della risposta che avevo dato a picchio sul perchè si definisce in modo così strano la somma tra due punti.

Mi piacerebbe trovare un modo efficace di "confezionare" questo thread, inizialmente pensavo che lo spazio che mi ero riservato nei primi post fosse sufficiente, in realtà non si è rilevato tale, l'argomento richiede troppe spiegazioni, precisazioni e integrazioni varie che sto aggiungendo qua e là (ma il tutto rischia di diventare un po' dispersivo, grazie comunque a picchio per le sue numerose e puntuali domande e osservazioni)

Forse conviene creare un altro thread che si occupi nello specifico solo dell'algoritmo ECDSA (firma di un messaggio mediante chiave privata e verifica tramite relativa chiave pubblica, magari con esempi pratici che devo ancora preparare)

Questo thread potrebbe continuare ad occuparsi solo della struttura matematica delle curve ellittiche, con l'aggiunta magari del discorso di quantificare l'intrattabilità del problema di risalire dalla chiave pubblica alla chiave privata privata corrispondente (in sostanza il problema del logaritmo discreto), giusto per dare una dimensione della sicurezza su cui si basa tutta la crittografia a cui si affida il sistema Bitcoin.

Discende da una questione geometrico-algebrica; visto che l'equazione di Weierstrass contiene il termine x^3, se metto quella equazione a sistema con una retta si troveranno in genere uno, due o tre punti di intersezione (l'equazione risolvente diventerà polinomiale di terzo grado in x)

y = mx + q
y^2 = x^3 + ax + b

--> (mx + q)^2 = x^3 + ax + b

(escludiamo invece i casi patologici delle curve con nodi o punti angolosi - grazie al concetto di discriminante - altrimenti non potremmo tracciare le tangenti in ogni punto, cioè ci sarebbero punti per i quali non sarebbe possibile definire la somma con se stessi)

Cosa c'entra una retta con il concetto di addizione?

Se dobbiamo definire un'operazione, dobbiamo trovare una regola per associare fra loro 3 elementi della curva, in modo che la relazione (A,B) -> C diventerà la nostra addizione. Il legame è quindi dato dalla retta che collega tra loro i punti della curva.
L'idea di base è che 3 punti allineati devono dare sempre somma "zero".

Se una retta ha in comune 3 punti con la curva, allora si pone semplicemente:

A+B+C= "zero" , cioè si dice che A+B = -C  

Chi è quindi -C ? Per capire chi è -C, l'opposto di C, cioè l'elemento che sommato a C dà "zero" come risultato dobbiamo adesso attribuire a qualcuno il ruolo dello "zero".

Osserviamo 2 fatti:

1) una retta può intersecare la curva anche in solo due punti A e B (qui per intersecare intendo proprio "secare", non essere solo tangente in A o in B), e non necessariamente in 3 punti; come definire allora la somma tra questi due elementi, visto che la retta che li collega non passa per nessun altro punto della curva?

2) le uniche rette che passano solo per 2 punti distinti della curva (senza essere tangenti alla curva in nessuno dei due punti) sono le rette verticali (rette che collegano tra loro quindi 2 punti simmetrici rispetto all'asse x)

Unendo 1) e 2) otteniamo che nel caso di due punti A e B simmetrici rispetto all'asse x dobbiamo aggiungere per forza un terzo punto allineato a loro per definire la loro somma, e questo punto deve essere obbligatoriamente un nuovo punto, lo "zero" appunto (nuovo nel senso che non sta "naturalmente" sulla curva):

A+B+"zero" = "zero"  (quindi 2 punti sono opposti se e solo se sono simmetrici rispetto all'asse x)

dove qui "zero" indica quindi la direzione della retta verticale che passa per A e B e poi si "perde" verso infinito, si attribuisce perciò lo status di punto a una direzione come si è soliti fare in geometria proiettiva

NB: ribadisco che il punto zero non ha coordinate (anche se viene rappresentato nei software con le coordinate fittizie (0,0), coordinate che non soddisfano certo l'equazione di Weierstrass).
Le curve ellittiche vengono perciò definite come l'insieme dei punti che soddisfano Weierstrass + il punto all'infinito (a volte c'è ambiguità nel termine "curva", ma dobbiamo ricordarci che va sempre aggiunto alle soluzioni dell'equazione anche il punto all'infinito!). Questo punto è necessario per dare all'insieme nella sua totalità una configurazione di gruppo. Il punto zero è chiamato in questo modo semplicemente perchè è, per definizione, l'elemento neutro rispetto all'addizione.

Torniamo per un momento alla formula iniziale:

A+B+C=zero   cioè A+B=-C

adesso dovrebbe risultare più chiaro perchè, per sommare A e B, non basta solo tracciare una secante che da A e B raggiunga il punto C, ma dobbiamo passare poi anche al suo opposto (e simmetrico) C'=-C.

Quindi si tratta sì di una regola "strampalata" ma anche ragionata  

Poi il perchè questa regola per definire l'addizione valga anche se prendiamo i coefficienti in un sottocampo finito di R, questo proprio non lo so (ma è proprio questo che rende interessanti le curve ellittiche per le applicazioni pratiche, il fatto che ereditano proprietà normalmente valide solo sul continuo di R come quella dei 3 punti di intersezione tra retta e curva anche in un campo di lavoro finito per le coordinate, fatto veramente notevole per il quale queste curve vengono utilizzate in teoria dei numeri; le curve ellittiche gettano un ponte tra il mondo del continuo e il mondo del discreto e per quanto riguarda quest'ultimo anche tra l'infinito e il finito).



2) non lo so, a occhio direi proprio di no, tra un gruppo e un anello c'è una bella differenza, il prodotto dei punti della curva per gli scalari non è in realtà una vera moltiplicazione, ma semplicemente un modo sintetico di indicare un'addizione ripetuta.

Sempre puo' chiaro e complicato... domande:
1) da dove arriva questo modo strampalato di fare la somma tra due punti?
2) esiste una definizione di prodotto tra due punti che magari porta a qualcosa di simile ad un anello?

E(F11) ha 12 elementi (bisogna contare anche lo zero!)

Il numero n di cui parli tu nel caso della secp256k1 non dipende dal punto iniziale scelto ed è esattamente uguale al numero di punti della curva. Questo vuol dire che E è un gruppo è ciclico, vuol dire che puoi ottenere tutti i suoi elementi a partire da uno solo.

EDIT: anche E(F11) è un gruppo ciclico ma non ha un numero primo di elementi, quindi alcuni suoi elementi hanno un ordine minore di 12. Se riguardi il post lo avevo scritto, se invece un gruppo ha un numero primo di elementi (come nel caso della secp256k1, n è un numero primo in quel caso) allora ogni suo elemento escluso lo 0 genera tutto il gruppo, questo fatto discende dal teorema di Lagrange che ho inserito nel post sulla matematica.

EDIT2: cosa dice il teorema di Lagrange? In soldoni dice che il numero di elementi che puoi generare a partire da un elemento di un gruppo deve essere sempre un divisore del numero degli elementi di tutto il gruppo.

Pensiamo a Z/12Z, che ha 12 elementi, e che può essere visto come un orologio con le 12 ore: ci sono elementi come 4 che hanno ordine 3 (poichè <4>={4, 4+4, 4+4+4} ={4,8,0} cioè ha ordine 3, che è un divisore di 12), elementi come 2 che hanno ordine 6, elementi come 1 che generano tutto il gruppo (che per questo si dice ciclico).
Nell'esempio di E(F11), poichè anch'esso è un gruppo finito di 12 elementi, è normale che tu possa trovare alcuni elementi che non generano tutti gli altri elementi del gruppo ma che al contrario generino solo un sottogruppo di 2 o 3 o 4 o 6 elementi del gruppo di partenza.

Tecnicamente si dice che l'ordine del sottogruppo deve dividere l'ordine del gruppo, e il risultato del rapporto ordine del gruppo / ordine del sottogruppo è un numero intero detto "cofattore". Se vai qui (https://en.bitcoin.it/wiki/Secp256k1 guarda nell'ultima riga il parametro h) vedrai che nella secp256k1 il cofattore di G è 1, cioè l'ordine di G è esattamente uguale all'ordine di E(Fp), entrambi sono n.

Domanda: è un caso fortunato che G generi tutto il gruppo? Oppure è stato trovato dopo un lungo lavoro di ricerca in E(Fp)? Direi proprio di no!

Infatti se un gruppo finito ha un numero primo di elementi, poichè per Lagrange l'ordine di ogni elemento deve dividere l'ordine del gruppo (ordine vuol dire numero di elementi) allora ogni elemento (diverso dallo zero) deve per forza avere ordine "massimo" (non può certo avere ordine 1, visto che almeno se stesso e lo 0 devono sempre esserci in ogni sottogruppo).

Questo è proprio il caso della secp256k1, che avendo un numero primo n di elementi risulta essere quindi non solo un gruppo ciclico ma in più ha anche la caratteristica che ogni suo elemento, a parte lo 0, è in grado di generare tutti gli altri.

Per riassumere: l'esempio che stai implementando non si comporta proprio come la secp256k1, poichè non stai utilizzando un gruppo con un numero primo di elementi.

EDIT3: penso che il termine "ordine di un elemento G" derivi dal fatto che scegliere un punto G di partenza (un generatore) equivalga di fatto a imporre un ordine con cui descrivere tutti gli altri elementi del gruppo: 2G, 3G, ... ordine che dipende quindi dal punto di vista di G)

L'"n" di cui parlo io è ancora minore del numero degli elementi della curva e cambia in funzione del punto di inizio.
Non mi quadra l'info di EDIT2: perche' 12 elementi? A me ne risultano 11:
(2, 2)
(2, 9)
(3, 1)
(3, 10)
(4, 4)
(4, 7)
(5, 0)
(6, 5)
(6, 6)
(7, 3)
(7,
Punti ellittica: 11; modulo 11

Sequenza dei punti
(4, 4)
(6, 6)
(2, 9)
(3, 10)
(7, 3)
(5, 0)
(7,
(3, 1)
(2, 2)
(6, 5)
(4, 7)
Se parto da (2, 2):
Sequenza dei punti
(2, 2)
(5, 0)
(2, 9)
Caso particolare, diversi ma opposti
(2, 9)
(2, 2)
-----------------
(11, 11)
(2, 2)
(5, 0)
(2, 9)
Caso particolare, diversi ma opposti
(2, 9)
(2, 2)
-----------------
(11, 11)
(2, 2)
(5, 0)
(2, 9)

Potrei aver commesso errori nel sw che sto debuggando.

Certo che l'insieme è limitato a n!
Per l'esattezza è compreso tra 1 e n-1 (questo sono sicuro di averlo scritto!)

n è leggermente minore di p (cioè il numero di punti della curva secp256k1 è leggermente minore dei possibili valori che posso provare ad assegnare alla x per vedere se c'è una y corrispondente tale per cui la coppia (x,y) soddisfa l'equazione della curva).

p è a sua volta un po' minore di 2^256.

EDIT: Poichè E è ciclico nel caso della secp256k1 ed è formato da un numero primo di elementi, ogni suo elemento tranne lo 0, compreso G, genera tutto E

EDIT2: nel caso di E(F11), la curva del post 6, E è ciclico ma non ha un numero primo di elementi (ne ha 12), lì quindi bisogna trovare in effetti una G che generi tutto E.  

Se poi mi chiedi con quale criterio allora abbiano scelto G nella secp256k1, sinceramente non lo so