Bitcoin Forum
September 15, 2019, 07:04:20 PM *
News: Latest Bitcoin Core release: 0.18.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 3 [4]  All
  Print  
Author Topic: curve ellittiche e algoritmo ECDSA  (Read 22754 times)
il_minatore
Sr. Member
****
Offline Offline

Activity: 292
Merit: 250



View Profile
January 17, 2019, 07:39:34 AM
 #61




 sqrt(4) = 2 o 9 (perchè 2*2 = 4 ma anche 9*9=81 = 4 mod 11)

ecco il motivo, scusate ma ho solo qualche reminiscenza universitaria...
1568574260
Hero Member
*
Offline Offline

Posts: 1568574260

View Profile Personal Message (Offline)

Ignore
1568574260
Reply with quote  #2

1568574260
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1568574260
Hero Member
*
Offline Offline

Posts: 1568574260

View Profile Personal Message (Offline)

Ignore
1568574260
Reply with quote  #2

1568574260
Report to moderator
il_minatore
Sr. Member
****
Offline Offline

Activity: 292
Merit: 250



View Profile
January 17, 2019, 09:55:18 AM
 #62

Addizione tra 2 punti in E(F_11): esempio


Vediamo di costruire come esempio il gruppo E(F_11), cioè il gruppo di elementi della curva di equazione y^2=x^3+7 a coordinate in F_11.

Proviamo tutti i casi possibili:

x   x^3+7   x^3+7 mod 11    Sqrt(x^3+7) mod 11   
0   7                   7      
1   8                   8      
2   15                   4                     2 o 9        2 o -2   --> (2,2), (2,-2)
3   34                   1                    1 o 10      1 o -1  -->  (3,1), (3, -1)
4   71                   5                    4 o 7        4 o -4  -->  (4,4),(4,-4)        
5   132                   0                        0               0      -->  (5,0)
6   223                   3                    5 o 6        5 o -5   -->  (6,5),(6,-5)
7   350                   9                    3 o 8        3 o -3   --> (7,3),(7,-3)
8   519                   2      
9   736                  10      
10   1007                  6      




Mi perdo nel passaggio dalla terza alla quarta colonna, il mod11 viene fatto sul sqrt? Non capisco come vengono estrapolati i valori.

mod 11 viene applicato al risultato della radice quadrata (in generale viene applicato al risultato di qualsiasi operazione quando questo risultato supera 11).

Prendiamo per esempio la riga del 2:

x = 2 --> x^3 = 8 --> x^3 + 7 = 8 + 7 = 15 = 4 mod 11 --> sqrt(4) = 2 o 9 (perchè 2*2 = 4 ma anche 9*9=81 = 4 mod 11) lascia perdere i valori negativi (semplicemente 9 = -2 mod 11, li ho inseriti solo per far vedere che le radici quadrate sono sempre opposte, anche in questi insiemi strani; anche con i numeri normali se ti dico x^2 = 4, chi è x? Tu rispondi: 2 o -2)

Ho un'altra domanda... Immagino non sia un caso che il rislutato di "x^3+7 mod 11" siano tutti valori diversi, da cosa dipende?
arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
January 17, 2019, 08:04:47 PM
Last edit: January 31, 2019, 07:23:58 PM by arulbero
Merited by Piggy (2)
 #63

Ho un'altra domanda... Immagino non sia un caso che il rislutato di "x^3+7 mod 11" siano tutti valori diversi, da cosa dipende?
se ho capito bene la tua domanda è:

perchè la funzione f definita da F_11 a F_11 in questo modo:

    F_11  -->   F_11

f:     x     -->   x^3 + 7

è iniettiva?

Risposta: questa funzione è iniettiva a seconda del valore di p in Fp (lo è nel caso di F_11, non lo è nel caso di Fp della secp256k1)



Una funzione f di A in B si dice iniettiva se

x1 != x2  --> f(x1) != f(x2)  per ogni coppia di valori x1, x2 in A

o equivalentemente se:

f(x1) = f(x2) --> x1 = x2  

Osservazione:

Supponiamo che f(x1) = f(x2), e cioè che  (x1)^3 + 7 = (x2)^3 + 7 mod 11, allora (x1)^3 = (x2)^3 mod 11 (per il primo principio di equivalenza delle equazioni).

Quindi ( x1 / x2 ) ^3 = 1 mod 11

Ora consideriamo l'equazione x^3 = 1 mod 11 (dove x = x1/x2). Quante soluzioni può avere?

Sicuramente ha come possibilità x = 1, ovvero x1 = x2. Quindi se l'equazione x^3 = 1 mod 11 ha come unica soluzione x = 1 allora la funzione f(x) = x^3 + 7 è iniettiva, altrimenti no.

Se infatti esistessero altre radici cubiche dell'unità, che chiameremo beta, ci sarebbero altre possibilità:

tipo beta^3 = 1 mod 11 (con beta diverso da 1) e quindi (x1/x2) = beta -->  x1 = beta * x2 mod 11 ed entrambi i valori x1 e x2 alla terza sarebbero uguali!

Ora si può dimostrare che se il numero primo 'p' di Fp è congruente a 1 mod 3 (ovvero se p = 1 mod 3) allora ci sono ben 3 diversi elementi x che vengono mappati nella stessa y (questa proprietà del campo delle coordinate induce una proprietà particolare nel gruppo dei punti che si costruiscono a partire da queste coordinate, si parla di endomorfismi, un legame particolare tra i punti della curva).

Questo è proprio il caso della p della secp256k1, quindi nel campo delle coordinate della curva utilizzata da Bitcoin esistono 3 numeri: 1, beta1, beta2 che elevati alla terza fanno 1 mod p, questo fa sì che per ogni possibile risultato y = x^3 + 7 mod p vi siano ben 3 valori di x possibili, detta in altri termini

se x --> y
allora anche

beta1*x --> y
beta2*x --> y

quindi i punti della curva secp256k1 si suddividono in gruppi da tre punti che condividono la stessa ordinata:

Code:
(x,y), (beta1*x, y), (beta2*x, y)

dove

beta1 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee #  (beta1^3 = 1 mod p)
beta2 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40 #  (beta2 = beta1^2, beta2^3 = 1 mod p)

sfruttare questa proprietà della curva accelera enormemente i calcoli (se l'obiettivo è generare il più velocemente possibile i punti della curva).

Nota bene:

11 non è congruente a 1 mod 3 (11 = 2 mod 3), quindi non può avere sottogruppi di ordine 3, e di sicuro non può avere allora un numero a diverso da 1 tale che a^3 = 1 mod 11.  In sostanza un campo di p elementi è un gruppo ciclico rispetto all'operazione di moltiplicazione di ordine p-1 (ha solo p-1 elementi perchè bisogna togliere lo zero), nel nostro caso 10.

Questo vuol dire che i possibili sottogruppi di {1,2,3,4,5,6,7,8,9,10} (guarda qui per il concetto di ordine e di sottogruppo)  possono avere per il teorema di Lagrange solo ordine un divisore di 10, ovvero o 1 o 2 o 5.  In un sottogruppo di ordine 2, deve esistere un elemento a != 1 tale che a^2 = 1 mod 11, in un sottogruppo di ordine 5 (se c'è) ci devono essere degli elementi b != 0 tali che b^5 = 1 mod 11.
Non potendoci essere un sottogruppo di ordine 3 (perchè 3 non divide 10), non ci può essere quindi un elemento beta diverso da 1 tale che beta^3 = 1 mod 11.

Se provi invece con F_7 (o con F_19 o con altri valori di p primo congruenti a 1 mod 3), poichè 7 = 1 mod 3 (ovvero 7-1 è un multiplo di 3) in F_7 può esserci un sottogruppo di ordine 3 e quindi un paio di elementi diversi da 1 di ordine 3 (ci può essere cioè un sottoinsieme di F_7 formato da 3 elementi = {1, beta1, beta2} che elevati alla terza fanno 1).

Infatti (tutti i calcoli sono fatti modulo 7 in F_7):

x     x^3    x^3 + 7    y=sqrt(x^3 + 7)

0      0            0                        0
1     1            1                     1 o 6
2     1            1                     1 o 6
4     1            1                     1 o 6
3      6            6                 non esiste
5      6            6                 non esiste  
6      6            6                 non esiste

quindi l'insieme E(F_7), ovvero la curva (il gruppo) formata da tutti i punti le cui coordinate nel campo F_7 soddisfano l'equazione y^2 = x^3 + 7 mod 7 é

E(F_7) = { (0,0), (1,1), (2,1), (4,1), (1,6), (2,6), (4,6) } U {punto all'infinito}

notare la doppia "simmetria"di questa curva:

1) rispetto all'asse x  (le y vanno a "coppie", 1 e 6 sono come 1 e -1, sono valori simmetrici rispetto all'asse x, questo deriva dal termine y^2)

2) rispetto ai singoli valori di y (le x associate alla stessa y sono terne di x legate tra loro dalle radici cubiche dell'unità, questo deriva dal termine x^3 dell'equazione e dal particolare valore di p)

Ho aggiunto in fondo a questo post il calcolo del numero distinto dei valori assunti dalle coordinate x e dalle coordinate y dei punti della curva, calcolo che si basa proprio su questa doppia simmetria.
arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
January 18, 2019, 05:26:04 PM
Last edit: January 18, 2019, 08:34:26 PM by arulbero
 #64

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.


Z'p non so neanche se sia corretta come notazione, andavo un po' a memoria.


Trovata, intendevi questo (fonte: https://it.wikipedia.org/wiki/Gruppo_ciclico):

Quote
Gruppo delle unità

Le unità dell'anello Z/nZ  sono i numeri primi con n, ovvero i generatori del gruppo. Formano un gruppo con la moltiplicazione, di φ ( n )  elementi (vedi sopra), indicato generalmente come Zn^* .

Ad esempio, i gruppi Z6^*  = { 1 , 5 }  e Z8^*  = { 1 , 3 , 5 , 7 }  sono isomorfi rispettivamente a Z / 2 Z  e Z / 2 Z × Z / 2 Z.

In generale, Zn^*  è ciclico se e solo se n  è 2, 4 , p^k o 2 p^k  dove p  è un primo dispari e k ≥ 1.

In particolare, il gruppo Zp^* è ciclico con p − 1  elementi per ogni primo p. Più in generale, ogni sottogruppo finito del gruppo moltiplicativo di un campo è ciclico.

Io invece mi sono soffermato nella teoria di questo thread solo sui gruppi di cui si parla nell'ultima riga perchè il campo Fp della secp256k1 è esattamente di quella forma.
arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
January 20, 2019, 08:53:10 AM
Last edit: January 20, 2019, 09:46:13 AM by arulbero
 #65

Preferisco inserire in questo post dedicato tutte le seguenti considerazioni, che si possono considerare un ulteriore approfondimento di questa sezione che ho comunque riveduto e ampliato a sua volta.

In questo post aggiungo qualche dettaglio anche pratico di calcolo sugli elementi di Fp, il campo delle coordinate che può essere visto (come tutti i campi finiti) sia come gruppo additivo che come gruppo moltiplicativo (tolto lo zero).


Poichè nel nostro caso Fp = Zp (campo delle classi dei resti della divisione degli interi per p), si ha che:

a) Fp è un gruppo ciclico di ordine p rispetto all'operazione di addizione
b) Fp - {0} è un gruppo ciclico di ordine p -1 rispetto all'operazione di moltiplicazione (si può dimostrare)

quindi per

a) si ha che a+a+a+a+a+a... = a*p = 0 mod p per ogni a di Fp
b) si ha che a*a*a*a*a ........... = a^(p-1) = 1 mod p per ogni a di Fp - {0}

La seconda relazione è quella che ci interessa.

Già Fermat aveva dimostrato un risultato pressochè equivalente:

per ogni numero primo p è sempre vera la relazione a^p - a = multiplo di k, ovvero a^p = a mod p  (piccolo teorema di Fermat)
 


1) Visto che il campo finito Fp è un gruppo ciclico (rispetto all'operazione di moltiplicazione) di ordine p - 1, si può utilizzare la relazione precedente per calcolare l'inverso di un elemento a diverso da 1:

a^(p-1) = 1   mod p   (a^(ordine) = 1)

quindi

a^(p-1) * a^(-1) = 1 * a^(-1) =  a^(-1) mod p

Quindi a^(p-2) = a^(-1) mod p

Ad esempio per calcolare l'inverso di 4 in F_ 7 basta fare 4^(7-2)  = 2  mod 7  e infatti  4*2 = 1 mod 7 (effettivamente 2 è l'inverso di 4 in F_7).

Sia nella mia prima versione della libreria micro_ecdsa che nella libreria secp256k1 si utilizza questo metodo (ovviamente nella libreria secp256k1 c'è un'ottimizzazione per la quale si è riusciti a minimizzare il numero di moltiplicazioni necessarie per ottenere a^(p-2) ricorrendo agli elevamenti al quadrato, un po' come nel caso della moltiplicazione (addizione ripetuta) per uno scalare si utilizzano i raddoppi dei punti per fare meno addizioni possibili.


2)  E' possibile anche ricavare la radice quadrata di b = a^2.

Infatti se p = 3 mod 4 (come succede effettivamente nella secp256k1), allora p + 1 è un multiplo di 4, e quindi:

a^p = a   mod p
 
a^(p+1) = a^2    mod p

a^((p+1)/4) = a^1/2 = sqrt(a)  mod p

Code:
>>> p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

>>> p % 4
3


>>> a = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

>>> a1 = pow(a, (p+1)/4, p) #sqrt(b)
>>> print(hex(a1))
0xcb6dfbd6cdf31164bbeb3052460c1fa3f827f01d6e7fb5f69580cfb96560c16a

>>> (a1 * a1)-a  % p    #verifica
0

>>> a2 = p-a  #a2 = -a1  trovo l'altra radice
>>> print(hex(a2))
0x34920429320cee9b4414cfadb9f3e05c07d80fe291804a096a7f30459a9f3ac5

>>> (a2 * a2)-a  % p  #verifica
0

Questa è l'implementazione di questa funzione nella libreria secp256k1. In quella libreria quando ci si riferisce a un'operazione definita su un elemento del campo delle coordinate si usa la sillaba 'fe' = field element , quando invece ci si riferisce a un'operazione sui punti della curva si usa la sillaba 'ge' = group element come succede ad esempio qui nell'implementazione della funzione che somma due punti della curva.
jack0m
Legendary
*
Online Online

Activity: 1932
Merit: 1088


View Profile
January 22, 2019, 01:34:44 PM
 #66

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.


Z'p non so neanche se sia corretta come notazione, andavo un po' a memoria.


Trovata, intendevi questo (fonte: https://it.wikipedia.org/wiki/Gruppo_ciclico):

Quote
Gruppo delle unità

Le unità dell'anello Z/nZ  sono i numeri primi con n, ovvero i generatori del gruppo. Formano un gruppo con la moltiplicazione, di φ ( n )  elementi (vedi sopra), indicato generalmente come Zn^* .

Ad esempio, i gruppi Z6^*  = { 1 , 5 }  e Z8^*  = { 1 , 3 , 5 , 7 }  sono isomorfi rispettivamente a Z / 2 Z  e Z / 2 Z × Z / 2 Z.

In generale, Zn^*  è ciclico se e solo se n  è 2, 4 , p^k o 2 p^k  dove p  è un primo dispari e k ≥ 1.

In particolare, il gruppo Zp^* è ciclico con p − 1  elementi per ogni primo p. Più in generale, ogni sottogruppo finito del gruppo moltiplicativo di un campo è ciclico.

Io invece mi sono soffermato nella teoria di questo thread solo sui gruppi di cui si parla nell'ultima riga perchè il campo Fp della secp256k1 è esattamente di quella forma.

ho visto solo ora, grazie del riferimento!

Money is a hoax. Debt is slavery. Consumerism is toxic.
arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
January 31, 2019, 06:35:16 PM
Last edit: February 02, 2019, 04:59:12 PM by arulbero
 #67

Parliamo un po' più a fondo di endomorfismi, vediamo da dove nascono i valori beta di cui ho parlato un paio di post sopra e cerchiamo così di entrare più a fondo nel mondo delle curve ellittiche (sempre privilegiando la nostra curva secp256k1).

ENDOMORFISMI

Una mappa f: E -> E si dice un ENDOMORFISMO (endomorfismo di E sul campo Fp) se

1) manda il punto all'infinito di E nel punto all'infinito di E

2) f(P) = (g(P),h(P)) per tutti i punti P di E, dove g e h sono funzioni razionali (rapporto tra 2 polinomi) i cui coefficienti sono nel campo Fp.

In pratica facendo una serie di operazioni - g - sul punto P (cioè sulla sua x e sulla sua y) si ottiene la x di un nuovo punto, il punto f(P), analogamente facendo un'altra serie di operazioni - h - sulle coordinate x e y di P si ottiene la y di f(P).

Questa mappa quindi consente di passare da un punto P della curva a un punto f(P) sempre della curva, facendo alcune operazioni particolari sulle x e y di P.

Un esempio semplice di mappa che soddisfa il requisito 2) ma non 1) è la mappa che prende P qualsiasi e aggiunge a P sempre lo stesso punto, chiamiamolo G.

f : P  -->  P+G  per ogni P di E

Questa mappa (una sorta di traslazione) è quella che viene usata in programmi tipo vanitygen per generare nella maniera più veloce possibile le chiavi pubbliche (tenendo traccia delle chiavi private, che vengono incrementate di 1 ad ogni iterazione).

Nell'ipotesi che P sia diverso da G e da O (punto all'infinito), questa mappa si compone delle seguenti due parti:

a) la x di f(P) = g(P) = ((yG - yP) / (xG -xP))^2 -xP -xG

b) la y di f(P) = h(P) = ((yG - yP) / (xG -xP)) * (xP - g(P)) - yP

ovvero la solita formule di addizione.

Però questa mappa manda O in O+G = G, e quindi non rispetta il primo criterio e non è un endomorfismo. Vedremo invece che la mappa:

f : P  --> k*P

che associa a ogni punto il suo prodotto per uno scalare k fissato è un endomorfismo.


Nel termine ENDOMORFISMO il prefisso ENDO significa INTERNO, il termine MORFISMO vuol dire che questa mappa rispetta la "forma" (struttura) algebrica di E, nel senso che sommare prima due punti in E e poi applicare la mappa f produce lo stesso risultato che applicare prima f ai due punti separatamente e poi sommare i risultati:

f(P1 + P2) = f(P1) + f(P2) per ogni P1, P2 in E.


Per fare un parallelo con un esempio più noto, la mappa

f : R -> R,  f(x) = ln(x)

si chiama OMOMORFISMO nel senso che traduce la struttura algebrica (operazione) della moltiplicazione in una struttura algebrica analoga, dello stesso tipo, cioè nella addizione:

ln(a*b) = ln(a) + ln(b)


In R se vogliamo costruire un ENDOMORFISMO che rispetti l'operazione di addizione possiamo farlo così:

f : R -> R   f(x) = k*x

k*(a+b) = k*a + k*b

(si noti il parallelismo con k*P delle curve ellittiche, dove k*(P1 + P2) = k*P1 + k*P2)

Nota: possono sembrare cose molto astratte, ma quanti sbagliano trattando la funzione x^2 o la funzione radice come fossero endomorfismi rispetto all'operazione di addizione!

(a + b)^2 = a^2 + b^2

radice (a + b) = radice(a) + radice(b)

mentre ovviamente x^2 e radice(x)  sono endomorfismi solo rispetto all'operazione di moltiplicazione.



Torniamo alle curve ellittiche.

Un endomorfismo f è una mappa da E a E che soddisfa certi requisiti, ovvero che manda punti di E in punti di E con l'unica avvertenza che il punto O va mandato nel punto O.

Si può verificare che un endomorfismo da E in E è sempre un omomorfismo di gruppo, ovvero che:

f(P1 + P2) = f(P1) + f(P2)

Esempi di endomorfismi da E in E

1) la moltiplicazione per uno scalare k fissato

la mappa f: P --> k*P è endomorfismo di E, è immediato verificare infatti che k*(P1 + P2) = k*P1 + k*P2

casi particolari della mappa appena vista si hanno per k = 1 (identità) e k = -1 (la mappa negazione, quella che associa ad ogni punto P il suo opposto -P, nel qual caso f è definita come (x,y) --> (x,-y) ).


2) la mappa f: (x,y) --> (beta*x, y)  dove beta è un elemento di ordine 3 di Fp (è una radice cubica di 1, questo si ha solo se p = 1 mod 3)

in quest'ultimo caso si ha quindi la possibilità di calcolare le coordinate di un nuovo punto in modo rapidissimo, con una sola moltiplicazione nel campo Fp. Se si applica 3 volte di seguito la mappa f appena descritta

P      -->   f(P) = P1  --> f(P1) = P2      --> f(P2) =  P

(x,y) --> (beta*x, y) --> (beta^2*x, y) --> (beta^3*x,y) = (x,y)

si vede che si torna sempre al punto dal quale si era partiti.  Quindi, ragionando senza le coordinate, si ha

P -> lambda * P -> lambda^2 * P -> lambda^3 * P = P   dove lambda è uno scalare di Zn

ovvero che lambda è un elemento di ordine 3 di Fn. Sottolineiamo che, quando si passa da un elemento P a un elemento P1 = f(P), si può sempre scrivere P1 come k*P, poichè ogni punto P diverso dal punto all'infinito genera ogni altro elemento di E, ovvero ogni punto P1 è multiplo di ogni altro punto P, per un opportuno fattore k.

Quindi di fatto la mappa 2) è un caso particolare della mappa 1), dove m = lambda e i calcoli sulle coordinate risultano particolarmente semplici (g(P) = beta*x, h(P) = y)


Piccola osservazione: sia p - 1 che n - 1 sono multipli di 3:

Code:
p - 1 = 115792 089237 316195 423570 985008 687907 853269 984665 640564 039457 584007 908834 671662 (78 digits) = 2 × 3 × 7 × 13441 × 205115 282021 455665 897114 700593 932402 728804 164701 536103 180137 503955 397371 (72 digits)

n - 1 = 115792 089237 316195 423570 985008 687907 852837 564279 074904 382605 163141 518161 494336 (78 digits) = 26 × 3 × 149 × 631 × 107361 793816 595537 × 174 723607 534414 371449 × 341 948486 974166 000522 343609 283189 (33 digits)


Come si fanno a calcolare gli elementi beta e lambda (rispettivamente elementi di ordine 3 di Zp e di Zn)?

Basta prendere un elemento a caso di Zp (Zn) ed elevarlo alla (p-1)/3 ((n-1/3)), si otterrà sicuramente un elemento di ordine 3, se non è uguale a 1 otterremo una delle due radici non banali dell'unità che stiamo cercando:

Code:
>>> hex(pow(19,(p-1)/3,p))  #proviamo prima con 19^((p-1)/3)

'0x1L'     #otteniamo 1, non va bene

>>> hex(pow(20,(p-1)/3,p)) #proviamo allora con 20^((p-1)/3)

'0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501eeL'  --> ok, questo è beta

>>> hex(pow(24,(p-1)/3,p))  #facendo altri tentativi, alla fine otteniamo con 24^((p-1)/3)

'0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40L'  --> questo lo chiamiamo beta2, poichè è = beta^2


Code:
>>> hex(pow(48,(n-1)/3,n))

'0x1L'

>>> hex(pow(49,(n-1)/3,n))  -->

'0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72L'  -->  abbiamo trovato lambda

>>> hex(pow(50,(n-1)/3,n))

'0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ceL'   --> abbiamo trovato lambda2 = lambda^2


Facciamo un rapido controllo che la seguente mappa :

f:        P        --> lambda*P

         (x,y)   --> (beta*x, y)

sia verificata per P = G:

Code:
from micro_ecdsa import mul

>>> Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
>>> Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

>>> lamb = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

>>> (Rx,Ry) = mul(lamb,Gx,Gy)   --> R = lambda * G

>>> hex(Rx)
'0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcbL'

>>> hex(Ry)
'0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L'  --> da notare che Ry = Gy !!!

>>> beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

>>> hex((beta*Gx) % p)
'0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcbL' --> beta * Gx = Rx !!!
Piggy
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1371



View Profile WWW
February 01, 2019, 06:43:06 AM
 #68

Se ti interessa e hai voglia, potresti usare questi tool che creano direttamente immagini dalle varie formule e operazioni (usano Latex come formato) così diventa più facile leggerle, magari non per tutto ma per alcune parti più importanti:

http://rogercortesi.com/eqn/index.php
http://www.sciweavers.org/free-online-latex-equation-editor

Le immagini create poi vanno caricate su qualche image hosting
arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
February 01, 2019, 05:27:11 PM
 #69

Se ti interessa e hai voglia, potresti usare questi tool che creano direttamente immagini dalle varie formule e operazioni (usano Latex come formato) così diventa più facile leggerle, magari non per tutto ma per alcune parti più importanti:

http://rogercortesi.com/eqn/index.php
http://www.sciweavers.org/free-online-latex-equation-editor

Le immagini create poi vanno caricate su qualche image hosting

Grazie per i link, in effetti sarebbe meglio, bisogna solo trovare tempo e voglia Smiley
picchio
Legendary
*
Offline Offline

Activity: 2044
Merit: 1052



View Profile
February 02, 2019, 12:17:08 AM
 #70

Se ti interessa e hai voglia, potresti usare questi tool che creano direttamente immagini dalle varie formule e operazioni (usano Latex come formato) così diventa più facile leggerle, magari non per tutto ma per alcune parti più importanti:

http://rogercortesi.com/eqn/index.php
http://www.sciweavers.org/free-online-latex-equation-editor

Le immagini create poi vanno caricate su qualche image hosting

Grazie per i link, in effetti sarebbe meglio, bisogna solo trovare tempo e voglia Smiley
Si potrebbe chiedere agli admin del forum se possono abilitare qualcosa per scrivere equazioni matematiche.
L'html lo prevede ma nel forum non funzionano ...

https://www.tutorialspoint.com/html5/html5_mathml.htm

Potresti anche scrivere queste perle in un documento LaTex o, anche solo, in writer e pubblicare il pdf.



 
 
           ▄████▄
         ▄████████▄
       ▄████████████▄
     ▄████████████████▄
    ████████████████████      ▄█▄                 ▄███▄                 ▄███▄                 ▄████████████████▀   ▄██████████

  ▄▄▄▀█████▀▄▄▄▄▀█████▀▄▄▄     ▀██▄             ▄██▀ ▀██▄             ▄██▀ ▀██▄             ▄██▀                   ██
▄█████▄▀▀▀▄██████▄▀▀▀▄█████▄     ▀██▄         ▄██▀     ▀██▄         ▄██▀     ▀██▄         ▄██▀        ▄█▄          ▀██████████████▄
████████████████████████████       ▀██▄     ▄██▀         ▀██▄     ▄██▀         ▀██▄     ▄██▀          ▀█▀                        ██
 ▀████████████████████████▀          ▀██▄ ▄██▀             ▀██▄ ▄██▀     ▄█▄     ▀██▄ ▄██▀                                       ██
   ▀████████████████████▀              ▀███▀                 ▀███▀       ▀█▀       ▀███▀      ▄███████████████████████████████████▀
     ▀████████████████▀
       ▀████████████▀
         ▀████████▀
           ▀████▀
║║


║║
.
.

║║
██
║║
.
.

║║
██
║║
.
║║


║║
arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
February 02, 2019, 11:46:40 AM
Last edit: February 03, 2019, 06:49:57 AM by arulbero
 #71

Si potrebbe chiedere agli admin del forum se possono abilitare qualcosa per scrivere equazioni matematiche.
L'html lo prevede ma nel forum non funzionano ...

https://www.tutorialspoint.com/html5/html5_mathml.htm

Potresti anche scrivere queste perle in un documento LaTex o, anche solo, in writer e pubblicare il pdf.

Ringrazio per le "perle" ma non esageriamo.

Ovviamente sarebbe l'ideale riscrivere tutto in LaTeX, ma diventerebbe ai miei occhi tutto troppo professionale, alla fine mi va bene scrivere le cose man mano che mi vengono in mente senza dovermi preoccupare troppo della forma. Si tratta di spunti, voglio buttare giù delle idee che possono tornare utili a me e a chi legge, non voglio scrivere un trattato o qualcosa di livello accademico, certo sarebbe comodo se il forum permettesse di inserire formule matematiche, ma qui hanno pensato solo a come inserire pezzi di codice, pazienza.

picchio
Legendary
*
Offline Offline

Activity: 2044
Merit: 1052



View Profile
February 02, 2019, 04:30:02 PM
 #72

Si potrebbe chiedere agli admin del forum se possono abilitare qualcosa per scrivere equazioni matematiche.
L'html lo prevede ma nel forum non funzionano ...

https://www.tutorialspoint.com/html5/html5_mathml.htm

Potresti anche scrivere queste perle in un documento LaTex o, anche solo, in writer e pubblicare il pdf.

Ringrazio per le "perle" ma non esageriamo.

Ovviamente sarebbe l'ideale riscrivere tutto in LaTex, ma diventerebbe ai miei occhi tutto troppo professionale, alla fine mi va bene scrivere le cose man mano che mi vengono in mente senza dovermi preoccupare troppo della forma. Si tratta di spunti, voglio buttare giù delle idee che possono tornare utili a me e a chi legge, non voglio scrivere un trattato o qualcosa di livello accademico, certo sarebbe comodo se il forum permettesse di inserire formule matematiche, ma qui hanno pensato solo a come inserire pezzi di codice, pazienza.


Ho segnalato al moderatore invitandolo ad intervenire ... vedremo, non credo siano solo gli italiani ad aver bisogno di rigore scientifico.


 
 
           ▄████▄
         ▄████████▄
       ▄████████████▄
     ▄████████████████▄
    ████████████████████      ▄█▄                 ▄███▄                 ▄███▄                 ▄████████████████▀   ▄██████████

  ▄▄▄▀█████▀▄▄▄▄▀█████▀▄▄▄     ▀██▄             ▄██▀ ▀██▄             ▄██▀ ▀██▄             ▄██▀                   ██
▄█████▄▀▀▀▄██████▄▀▀▀▄█████▄     ▀██▄         ▄██▀     ▀██▄         ▄██▀     ▀██▄         ▄██▀        ▄█▄          ▀██████████████▄
████████████████████████████       ▀██▄     ▄██▀         ▀██▄     ▄██▀         ▀██▄     ▄██▀          ▀█▀                        ██
 ▀████████████████████████▀          ▀██▄ ▄██▀             ▀██▄ ▄██▀     ▄█▄     ▀██▄ ▄██▀                                       ██
   ▀████████████████████▀              ▀███▀                 ▀███▀       ▀█▀       ▀███▀      ▄███████████████████████████████████▀
     ▀████████████████▀
       ▀████████████▀
         ▀████████▀
           ▀████▀
║║


║║
.
.

║║
██
║║
.
.

║║
██
║║
.
║║


║║
Piggy
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1371



View Profile WWW
February 03, 2019, 06:43:54 AM
 #73

Ho segnalato al moderatore invitandolo ad intervenire ... vedremo, non credo siano solo gli italiani ad aver bisogno di rigore scientifico.

Sarebbe la cosa migliore, ma temo non sia una priorità o comunque una cosa lunga.

Ad ogni modo viene usata per l'appunto su questo forum (da anni ormai) e funziona perfettamente, esempio: https://www.matematicamente.it/forum/viewtopic.php?f=19&t=197194
Pages: « 1 2 3 [4]  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!