Bitcoin Forum
November 14, 2019, 07:25:02 PM *
News: Help collect the most notable posts made over the last 10 years.
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Vanity address mining  (Read 360 times)
Piggy
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1385



View Profile WWW
November 08, 2018, 10:41:53 AM
 #1

Stavo cercando di capire come funziona il mining dei Vanity address per bitcoin, ho provato a cercare un po come funziona, senza addentrarmi troppo nel codice dei vari programmi che ho trovato, visto che non è banale.

Qui ho trovato un post di arulbero, è fuori contesto, ma si parla di sommare le chiavi private e/o pubbliche per arrivare al pattern cercato ("166"): https://bitcointalk.org/index.php?topic=84569.msg17299181#msg17299181

Questo mi fa venire dei dubbi e vorrei porre la seguente domanda (spero non stupida): esiste qualche proprietà che suggerisca, una volta sommate le due chiavi pubbliche, otterrò un indirizzo che comincia con "166"?
Quali sono in generale le strategie o proprietà da sfruttare per minare questi indirizzi in maniera efficiente?
1573759502
Hero Member
*
Offline Offline

Posts: 1573759502

View Profile Personal Message (Offline)

Ignore
1573759502
Reply with quote  #2

1573759502
Report to moderator
1573759502
Hero Member
*
Offline Offline

Posts: 1573759502

View Profile Personal Message (Offline)

Ignore
1573759502
Reply with quote  #2

1573759502
Report to moderator
The Bitcoin Forum is turning 10 years old! Join the community in sharing and exploring the notable posts made over the years.
picchio
Legendary
*
Offline Offline

Activity: 2100
Merit: 1054



View Profile
November 08, 2018, 05:29:09 PM
Last edit: November 11, 2018, 11:19:18 AM by picchio
Merited by Micio (2), arulbero (1), duesoldi (1), Piggy (1), Makkara (1)
 #2

...
Questo mi fa venire dei dubbi e vorrei porre la seguente domanda (spero non stupida): esiste qualche proprietà che suggerisca, una volta sommate le due chiavi pubbliche, otterrò un indirizzo che comincia con "166"?
Quali sono in generale le strategie o proprietà da sfruttare per minare questi indirizzi in maniera efficiente?
Ovviamente no. Nessuno può determinare a priori il valore di un hash, per "minare" vanity puoi fidarti di chi mina e tentare fino a quando arrivi all'address desiderato (brute force). Esiste un sw che lo fa e se lo fai girare tu sei tranquillo ...

(se ho capito ...)

Se vuoi offrire il servizio di mining e non vuoi avere problemi di privacy allora ti fai dare una qualunque chiave pubblica dal cliente (*).
A) Tu generi una chiave privata casuale, calcoli la chiave pubblica, la sommi a quella data dal cliente, calcoli l'address, se l'address rispetta il pattern ti fermi, comunichi la chiave privata al cliente e hai finito. In caso contrario riparti da A)

Il cliente somma la sua chiave privata con quella che gli hai comunicato, calcola la chiave pubblica (che deve venire uguale a quella che hai calcolato tu) e genera l'address desiderato.

In questo modo salvi capra e cavoli.
EDIT: (*) ovviamente il cliente deve conoscere anche la chiave privata corrispondente altrimenti ciccia!
EDIT2: come fatto notare in seguito, prestare ATTENZIONE al fatto che la chiave pubblica è nota al fornitore e questo potrebbe ridurre la sicurezza dell'indirizzo. Soluzione: spostare i fondi ricevuti in modo che non ci siano troppi fondi (NB: spostando i fondi si espone comunque la chiave pubblica).


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

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


║║
.
.

║║
██
║║
.
.

║║
██
║║
.
║║


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

Activity: 784
Merit: 1385



View Profile WWW
November 08, 2018, 05:39:58 PM
Merited by arulbero (1)
 #3

Ok mi sembrava strano infatti visto che mi ero guardato come passare dalla chiave pubblica all indirizzo Smiley, avevo frainteso il significato del perchè sommassero le chiavi pubbliche e mi era venuto il dubbio ci fosse qualche scorciatoia per trovare il pattern.

Quindi tocca continuare a generare chiavi a caso fino a quando non si trova un indirizzo col pattern che ci interessa.

Grazie  Wink
picchio
Legendary
*
Offline Offline

Activity: 2100
Merit: 1054



View Profile
November 08, 2018, 05:43:34 PM
 #4

...
Quindi tocca continuare a generare chiavi a caso fino a quando non si trova un indirizzo col pattern che ci interessa.
..
E meno male Smiley


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

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


║║
.
.

║║
██
║║
.
.

║║
██
║║
.
║║


║║
arulbero
Legendary
*
Offline Offline

Activity: 1290
Merit: 1337


View Profile
November 08, 2018, 06:53:05 PM
Merited by Piggy (1)
 #5

Se vuoi offrire il servizio di mining e non vuoi avere problemi di privacy allora ti fai dare una qualunque chiave pubblica dal cliente (*).
A) Tu generi una chiave privata casuale, calcoli la chiave pubblica, la sommi a quella data dal cliente, calcoli l'address, se l'address rispetta il pattern ti fermi, comunichi la chiave privata al cliente e hai finito. In caso contrario riparti da A)

Il cliente somma la sua chiave privata con quella che gli hai comunicato, calcola la chiave pubblica (che deve venire uguale a quella che hai calcolato tu) e genera l'address desiderato.

In questo modo salvi capra e cavoli.

C'è quindi una piccola diminuzione di sicurezza, chi ti offre il servizio conosce la chiave pubblica relativa al tuo address anche se non fai transazioni in uscita, da 160 bit si passa a 128 bit.

Qui spiega brevemente il concetto di split key per ottenere un vanity address: https://en.bitcoin.it/wiki/Split-key_vanity_address
picchio
Legendary
*
Offline Offline

Activity: 2100
Merit: 1054



View Profile
November 08, 2018, 08:23:29 PM
 #6

...
C'è quindi una piccola diminuzione di sicurezza, chi ti offre il servizio conosce la chiave pubblica relativa al tuo address anche se non fai transazioni in uscita, da 160 bit si passa a 128 bit.
...
Credo sia inevitabile.
Per quello che vale, un conto è avere la public key in blockchain e un conto è sapere che un fornitore l'ha conosciuta, in caso di problemi sapresti a chi rivolgerti (con le dovute considerazioni). Il fornitore potrebbe sempre affermare che la cancellerà una volta consegnata la chiave privata al cliente.
Mi spieghi perché c'è un calo di bit? Io sapevo che esporre la PK metteva a rischio l'address ad attacco di PC quantistici mentre avere solo l'address richiedeva passaggi non risolubili da PC quantistici.
In ogni caso, se temi per la PK nota a qualcuno possa creare problemi, basta svuotare l'address appena ricevi i fondi sul vanity spostandoli su altri address.


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

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


║║
.
.

║║
██
║║
.
.

║║
██
║║
.
║║


║║
arulbero
Legendary
*
Offline Offline

Activity: 1290
Merit: 1337


View Profile
November 08, 2018, 08:30:34 PM
Last edit: November 09, 2018, 11:53:29 AM by arulbero
Merited by Piggy (2)
 #7

Mi spieghi perché c'è un calo di bit? Io sapevo che esporre la PK metteva a rischio l'address ad attacco di PC quantistici mentre avere solo l'address richiedeva passaggi non risolubili da PC quantistici.

Il migliore algoritmo per risolvere il problema del logaritmo discreto nelle curve ellittiche necessita di radice quadrata (n) passi, dove n è la dimensione del numero dei punti della curva, nel nostro caso quindi 2^256 -> 2^128.  Si può fare in teoria anche senza computer quantistici, ma non in tempi accettabili.

Rimane quindi il fatto che la sicurezza diminuisce pur rimanendo alta. Tutti i primi indirizzi di Nakamoto (50 btc) hanno esposta la chiave pubblica pur non avendo tx in uscita, poichè a quei tempi si pagava direttamente alla chiave pubblica (P2PK) e non al suo hash (address, P2PKH).
Quindi nel caso degli indirizzi vanity generati con il metodo split-key si avrebbe la stessa sicurezza degli indirizzi di Satoshi.

EDIT: proprio poche ore fa è stata trovata la chiave privata numero 57 (lunga 57 bit) di questa famosa transazione puzzle: https://www.blockchain.com/btc/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15

2 mesi per trovarla (facendo brute force da qualcuno con gpu), io ho impiegato solo pochi secondi per ricavare dalla chiave pubblica esposta nella blockchain quella privata: https://bitcointalk.org/index.php?topic=1306983.msg47712972#msg47712972 , dimostrazione del fatto che la sicurezza non rimane proprio la stessa quando vieni a conoscenza della chiave pubblica (dai 57 bit dell'address con chiave pubblica sconosciuta si passa in quel caso ai 28 bit con la chiave pubblica esposta in blockchain).
Piggy
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1385



View Profile WWW
November 10, 2018, 01:29:50 PM
 #8

Sto provando un pò a sperimentare con bouncy castle per cercare di capire che genere di prestazioni si possano raggiungere tramite l'utilizzo di linguaggi di alto livello, tipo c# e python, usando solo la CPU.

Arulbero hai già fatto qualche esperimento del genere o mi sai consigliare qualche libreria in particolare?
arulbero
Legendary
*
Offline Offline

Activity: 1290
Merit: 1337


View Profile
November 10, 2018, 01:40:35 PM
Merited by Piggy (1)
 #9

Sto provando un pò a sperimentare con bouncy castle per cercare di capire che genere di prestazioni si possano raggiungere tramite l'utilizzo di linguaggi di alto livello, tipo c# e python, usando solo la CPU.

Arulbero hai già fatto qualche esperimento del genere o mi sai consigliare qualche libreria in particolare?


Tempo fa avevo fatto questa in python (python2)

https://bitcointalk.org/index.php?topic=1573035.msg17685839#msg17685839

ma non so se è molto chiaro il suo utilizzo. Prova a dare un'occhiata (non ricordo le prestazioni, ma non erano pessime)
Piggy
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1385



View Profile WWW
November 13, 2018, 06:48:06 PM
 #10

Ho provato un pò lo script (un'altra versione che hai pibblicato ecc_for_collider5.py, non trovo il link ora dal telefono) in python è parecchio veloce ~60 secondi per 16.4M chiavi pubbliche, non mi sono ancora addentrato nei dettagli del funzionamento e relativa spiegazione.

Magari dipende dalla versione di python che uso 2.7, ma ho notato che alcune coordinate non sono 32 byte, la stringa che le rappresenta ha un carattere in più per qualche motivo. Non ho ancora verificato nel dettaglio con che frequenza capita, magari domani riesco a controllare un pò meglio.

Comunque ottimo lavoro, grazie  Smiley
arulbero
Legendary
*
Offline Offline

Activity: 1290
Merit: 1337


View Profile
November 13, 2018, 07:17:35 PM
Merited by Piggy (5)
 #11

Ho provato un pò lo script (un'altra versione che hai pibblicato ecc_for_collider5.py, non trovo il link ora dal telefono) in python è parecchio veloce ~60 secondi per 16.4M chiavi pubbliche, non mi sono ancora addentrato nei dettagli del funzionamento e relativa spiegazione.

Magari dipende dalla versione di python che uso 2.7, ma ho notato che alcune coordinate non sono 32 byte, la stringa che le rappresenta ha un carattere in più per qualche motivo. Non ho ancora verificato nel dettaglio con che frequenza capita, magari domani riesco a controllare un pò meglio.

Comunque ottimo lavoro, grazie  Smiley

Non offendiamo, la mia libreria migliore in python impiega meno di 6,5 secondi per generare 16.4 milioni di chiavi pubbliche!
Utilizzando gmpy2. Poi mi sono stufato di python e sono passato a C (50 milioni di chiavi in 1 secondo).

Penso che la versione che hai scaricato tu sia più leggibile, comunque ti allego la più veloce (la 08). Per quanto riguarda la stampa, se stampa a video una L finale, L sta per long. Se ci sono altri problemi fammi sapere.


Code:
$ time python2 gen_batches_points08.py
private key: -lambda*(k+m)G
0x2a7fb67883ea214c0a96f75b449fa3cec8e1b0d1f1e65e8aa80c3ef6cffaa1ae
('0x1c98a16eb218925feea48547a41d9d07bbd757d696857b4c2072bd264c827938', '0x49963b55d6a149f0df12d4acd5065e26b3e9d4f7da9c56aab690f44e866afe16')
*******
private key: -lambda*(k-m)G
0x6554827e46f82b9e6c571fdc6ae54b90dfdd38c4a3daf5213f3b4ee41119b8f8
('0x3c8250f180d59f9f1deeb55dbe00deb835de8a774c2fe1e6231b9eb44cdb3148', '0x7fcc26c9d9b58dd0971e87dd475c9d535a393cd5cf2cc62d53d4130cef611b6b')
*******
 
You have just generated 16 Millions of keys!!!

real 0m6,460s
user 0m6,456s



ecc_for_collider08.py
Code:
import gmpy2

from gmpy2 import mpz

#see http://www.secg.org/sec2-v2.pdf at page 9

#Gx=55066263022277343669578718895168534326250603453777594175500187360389116729240
#Gy=32670510020758816978083085130507043184471273380659243275938904335757337482424
#p=115792089237316195423570985008687907853269984665640564039457584007908834671663
#n=115792089237316195423570985008687907852837564279074904382605163141518161494337

Gx=mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy=mpz(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
p=mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F) # Fp
n=mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141) # E(Fp)

#endomorphism
lambd=mpz(0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72) # (lambda^3 = 1 mod n)    
lambd2=mpz(0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce) #(lambda^2)

beta=mpz(0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee) # (beta^3 = 1 mod p)
beta2=mpz(0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40) # (beta^2)
############################################################################################
###Field operations

#a must be a number between 1 and p-1;    input: a  output: 1/a
#see http://www.springer.com/?SGWID=4-102-45-110359-0 page 40 alg. 2.20
def inv(a,p):
u, v = a%p, p
x1, x2 = 1, 0
while u != 1:
#q = v//u
#r = v-q*u
q, r = divmod(v,u)
x = x2-q*x1
v = u
u = r
x2 = x1
x1 = x
return x1%p


#inverse of a batch of x
#input: batch of x : [x1,x2,x3,x4,x5,x6,x7,x8,...,x2048]
#x is known (x of kG)
#output: batch of inverse: 1/(x1-x), 1/(x2-x), 1/(x3-x), ....
#3M for each inverse
def inv_batch(x,batchx,p):

a = (batchx[1]-x) % p
partial= [0]*2049
partial[1]=a

for i in range(2,2049):
a = (a*(batchx[i]-x)) % p #2047M
partial[i]=a

inverse=gmpy2.invert(partial[2048],p) # 1I
#inverse=inv(partial[2048],p) # 1I
batch_inverse=[0]*2049

for i in range(2048,1,-1):
batch_inverse[i-1]=(partial[i-1]*inverse) % p #2047M
inverse=(inverse*(batchx[i]-x)) %p #2047M

batch_inverse[0]=inverse

return batch_inverse

############################################################################################
##Group operations

#  https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition
#'double' addition
#add 2 points P and Q -->  P+Q
#add 2 points P and Q -->  P-Q
#
#(X1,Y1) + (X2,Y2)  -->  (X3,Y3)  (the inverse of (x2-x1) must be known)
#(X1,Y1) + (X2,-Y2) -->  (X4,Y4)  (the inverse of (x2-x1) must be known)
#
#input: (X1,Y1), (X2,Y2), the inverse of (X2 - X1): 5 scalars
#output: (X3,Y3), (X4,Y4) :  4 scalars
#4M + 2S

def double_add_P_Q_inv(x1, y1, batchG, batchinvx2x1):

batch=[0]*2048
for i in range(1,2049):

x2,y2 = batchG[i]
invx2x1 = batchinvx2x1[i]

dy = (y2-y1) #% p
a = dy*invx2x1 % p #1M
a2 = a**2     #1S
x3 = (a2 - x1 -x2) % p
y3 = (a*(x1-x3) -y1) % p #1M


dy = p-(y2+y1) #% p # only the sign of y2 changes, "y of -Q = -y of +Q"
a = dy*invx2x1 % p #1M  x2 and then the inverse invx2x1 are the same
a2 = a**2   #1S
x4 = (a2 - x1 -x2) % p
y4 = (a*(x1-x4) -y1) % p #1M

batch[i-1]=(x3,y3,x4,y4)

return batch


#https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates
#jacobian coordinates
def add_j_j(jax, jay, jaz, jbx, jby, jbz):

u1 = (jax*jbz**2) % p
u2 = (jbx*jaz**2) % p
s1 = (jay*jbz**3) % p
s2 = (jby*jaz**3) % p
h = (u2-u1) % p
r = (s2-s1) % p
jcx = (r**2 -h**3-2*u1*h**2) % p
jcy = (r*(u1*h**2-jcx)-s1*h**3) % p
jcz = (h*jaz*jbz) % p
return jcx, jcy, jcz

def double_j_j(jx, jy, jz):
s = (4*jx*jy**2) % p
m = (3*jx**2) % p
jx2 = (m**2 - 2*s) % p
jy2 = (m*(s-jx2) - 8*jy**4) % p
jz2 = (2*jy*jz) % p
return jx2, jy2, jz2


def mul(k,jx,jy,jz):

jkx, jky, jkz = 0, 0, 1
if (k%2 == 1):
jkx, jky, jkz = jx, jy, jz #only if d is odd
q=k//2
while q>0:
jx, jy, jz = double_j_j(jx,jy,jz)
a=q%2
if (a > jkx):
jkx, jky, jkz = jx, jy, jz  #only if d is even
elif (a):
jkx, jky, jkz = add_j_j(jx, jy, jz, jkx, jky, jkz)  
q=q//2
                                 
return jkx, jky, jkz

############################################################################################
#Coordinates

#from jacobian to affine
def jac_to_aff(jax, jay, jaz, invjaz):

ax, ay = (jax*invjaz**2) % p, (jay*invjaz**3) % p

return ax, ay


gen_batches_points08.py
Code:
#!/usr/bin/env python

#this script computes 6x667 batchs of 4097 points (1 single point + 2048 couples of points -> (kG+mG, kG-mg))
#16,4 millions of points
#3 : 1 batch + 5 endomorphism


from ecc_for_collider08 import *

########################################################################
#in this section the script pre-computes 1G, 2G, 3G, ..., 2048G
mG = [(0,0)]*2049
mGx = [0]*2049
mGy = [0]*2049

mGx[1]=Gx
mGy[1]=Gy
mG[1]=(Gx,Gy) #list of multiples of G,
 #you have to precompute and store these multiples somewhere

mGx[2]=mpz(0xC6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5)
mGy[2]=mpz(0x1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A)
mG[2]=(mGx[2],mGy[2])

for i in range(3,2049):

jx,jy,jz=add_j_j(Gx, Gy, mpz(1), mGx[i-1], mGy[i-1], mpz(1)) #this is not a efficient way, but it is not important
jzinv = inv(jz,p)
(x,y) = jac_to_aff(jx, jy, jz, jzinv)
mG[i] = (x,y)
mGx[i] = x
mGy[i] = y

###########################################################################
lowest_key=2**55+789079076 #put here the lowest key you want to generate
number_of_batches=667 # #put here how many consecutive batches you want to generate
number_of_keys=4097*6*number_of_batches #this is the number of consecutive keys you are going to generate
#this number is always a multiple of 6*4097=24582, because 24582 is the minimum size
#remember: you generate always 6 batches at once, 1 in (1,2^160) and 5 out of this range
#their name are:  main_batch (the main), batch2, batch3, batch_minus
#(these other batches are derived from the main with endomorphism or complement private keys)


id_batch=lowest_key+2048 #id_batch is now the private key of the middle point of the first batch that you want compute
distance_between_successive_batches=4097 #this is the distance from the middle point of the first batch and the middle point
#of the successive batch in (1,2^160)
#4097 means that I'm generating only consecutive batches in (1,2^160), this is the default


start=id_batch #the first key to generate of the the first batch is the lowest key + 2048 -->
#the middle point of the first batch
stop=id_batch + number_of_batches*distance_between_successive_batches #the key of the middle point of the last batch


#k is always the id of the current main batch and the key of the middle point of the current main batch
for k in range(start,stop,distance_between_successive_batches):

jkx,jky,jkz = mul(k,Gx,Gy,mpz(1)) #here we use the slow function mul to generate the middle point
#invjkz = inv(jkz,p)
invjkz=gmpy2.invert(jkz,p) # 1I
(kx,ky) = jac_to_aff(jkx, jky, jkz, invjkz)

kminverse = [0]*2048
kminverse = inv_batch(kx,mGx,p) #you need to compute 2048 inverse, 1 for each couple
#to perform this task you need only the x coordinates of the multiples of G and
#the x coordinate of kG: kx
kminverse = [invjkz]+kminverse
#the element number 0 of the list is the inverse invjkz that you have computed to get kG=(kx,ky)
#the element number 1 of the list is the inverse necessary to perform kG + 1G (and kG-1G)
#--->  1/(x_of_1G - kx)
#the element number 2 of the list is the inverse necessary to perform kG + 2G (and kG-2G)
#--->  1/(x_of_2G - kx)
#...
#the element number m of the list is the inverse necessary to perform kG + mG (and kG-mG)
#--->  1/(x_of_mG - kx)
#then the name: "kminverse", the inverse to get the generic kG+mG
#...
#the element number 2048 of the list is the inverse necessary to perform kG+2048G and kG-2048G
#---> 1/(x_of_2048G - kx)


main_batch=[(0,0,0,0)]*2048
#the element number 0 of the list will be the middle point kG=(kx,ky), you can see it as the couple ((k+0)G, (k-0)G)  
#the element number 1 will be the couple (k+1)G, (k-1)G
#the element number 2 will be the couple (k+2)G, (k-2)G
#...
#the element number 2048 will be the couple (k+2048)G, (k-2048)G
#each element of this list is a couple of points -> 4 scalars: x_(k+m)G,y_(k+m)G,x_(k-m)G,y_(k-m)G,
#but the first element is only a fake couple
main_batch = double_add_P_Q_inv(kx,ky,mG,kminverse)
#_the function double_add_P_Q_inv computes kG +/-mG, it uses the list of the inverse and return a list of couple of points
#each element of this list is a couple of points, 4 scalars, x_(k+m)G,y_(k+m)G,x_(k-m)G,y_(k-m)G
#this list has 2049 elements

main_batch = [(kx,ky,kx,ky)]+main_batch #the element number 0 of the list is now the middle point kG=(kx,ky), you can see it as the fake couple (k+0)G, (k-0)G

batch2=[0] * 2049 #this is the batch2 with lambda*kG, ( lambda*(k+1)G, lambda*(k-1)G ),  ( lambda*(k+2)G, lambda*(k-2)G ), ....,
# (lambda*(k+2048)G, lambda*(k-2048)G)
#this list actually has only the x-cooordinates of the points, because the y-coordinates are the same of main batch
#each element of this list is a couple of x -> 2 scalars: x_lambda*(k+m)G, x_lambda*(k-m)G
#this list has 2049 elements


batch3=[0] * 2049 #this is the batch3 with lambda^2*kG, ( lambda^2*(k+1)G, lambda^2*(k-1)G ),  ( lambda^2*(k+2)G, lambda^2*(k-2)G ), ....,
# (lambda^2*(k+2048)G, lambda^2*(k-2048)G)
#this list actually has only the x-cooordinates of the points, because the y-coordinates are the same of main batch
#each element of this list is a couple of x -> 2 scalars: x_lambda^2*(k+m)G, x_lambda^2*(k-m)G
#this list has 2049 elements


batch_minus=[0] * 2049 #the complement private keys of the other batches

for i in range(0,2049): #endomorphism + the complement private keys

x1,y1,x2,y2=main_batch[i]
 
batch2[i] = [(x1*beta  % p), (x2*beta % p)] #only x coordinates, the first and the third scalar of each element
#of the main batch
#private key: lambda*k mod n,  coordinate x: beta*x mod p
batch3[i] = [(x1*beta2 % p), (x2*beta2 % p)] #only x coordinates, the first and the third scalar of each element
#of the main batch
#private key: lambda^2*k mod n,  coordinate x: beta^2*x mod p

batch_minus[i]=[(-y1 % p), (-y2 % p)] #only y coordinates, the 2^ and the 4^ scalar of each element of all batches



#k in this case is the id of the last batch (or if you prefer, k is the private key of the middle point of the last batch)
m=2048 #a random number between 0 and 2048, you can pick up a couple of points in the last main batch (or in batch2 / batch3)
(kmx1,kmx2)=batch2[m]
(kmy1,kmy2)=batch_minus[m] #in this case the points chosen are in batch3
#the y are from batch_minus
#(kmx1,kmy1,kmx2,kmy2)=main_batch[m]
print ('private key: -lambda*(k+m)G')
print (hex(-lambd*(k+m)%n)) #private key
print (hex(kmx1), hex(kmy1)) #public key (first and second coordinate)
print ('*******')


print ('private key: -lambda*(k-m)G')
print (hex(-lambd*(k-m)%n)) #private key
print (hex(kmx2), hex(kmy2)) #public key (first and second coordinate)
print ('*******')

print (' ')
a=number_of_keys//1000000
print ('You have just generated ' + str(a) + ' Millions of keys!!!')
Piggy
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1385



View Profile WWW
November 14, 2018, 09:35:44 AM
Last edit: November 14, 2018, 10:37:35 AM by Piggy
 #12

Ho fatto una prova veloce sulla mia macchina,impiega 20 secondi, nettamente più veloce dell'altro.  Smiley

No so se usi qualche libreria particolamente ottimizzata in C per fare i calcoli o quale compiler, però potrebbe esserci la possibilità di spingersi oltre a livello di prestazioni implementando il tutto in assembly. Probabilmente lo saprai già comunque, quando compili in C, il compilatore crea un approssimazione del codice in assembly, in base a quanto lo fa intelligentemente ci sarà un calo minimo di prestazioni paragonato ad un implementazione full assembly.

Esistono librerie già pronte ed ottimizzate in Assembly per effettuare operazioni matematiche che sono scontate in altri linguaggi. Detto questo sono 10 anni circa che non metto mano a codice assembly e l'ho utilizzato solo all'università, quindi bisognerebbe capire bene prima se ne vale la pena.


arulbero
Legendary
*
Offline Offline

Activity: 1290
Merit: 1337


View Profile
November 14, 2018, 10:51:50 AM
 #13

Ho fatto una prova veloce sulla mia macchina,impiega 20 secondi, nettamente più veloce dell'altro.  Smiley

No so se usi qualche libreria particolamente ottimizzata in C per fare i calcoli o quale compiler, però potrebbe esserci la possibilità di spingersi oltre a livello di prestazioni implementando il tutto in assembly. Probabilmente lo saprai già comunque, quando compili in C, il compilatore crea un approssimazione del codice in assembly, in base a quanto lo fa intelligentemente ci sarà un calo minimo di prestazioni paragonato ad un implementazione full assembly.

Esistono librerie già pronte ed ottimizzate in Assembly per effettuare operazioni matematiche che sono scontate in altri linguaggi. Detto questo sono 10 anni circa che non metto mano a codice assembly e l'ho utilizzato solo all'università, quindi bisognerebbe capire bene prima se ne vale la pena.



Tutto il codice delle operazioni base come moltiplicazione tra 2 numeri di 64 bit , eccetera è stato scritto da me "a mano" in questa forma:

Quote
#define MultiplyWordsLoHi(low, high, a, b) asm  ( "mulx  %2, %0, %1;" : "=r"(low), "=r"(high) :  "gr" (a), "d" (b) : "cc");

Non so se sia possibile ottenere tanto di più a livello di prestazioni ...
picchio
Legendary
*
Offline Offline

Activity: 2100
Merit: 1054



View Profile
November 14, 2018, 01:52:09 PM
 #14

...
Tutto il codice delle operazioni base come moltiplicazione tra 2 numeri di 64 bit , eccetera è stato scritto da me "a mano" in questa forma:

Quote
#define MultiplyWordsLoHi(low, high, a, b) asm  ( "mulx  %2, %0, %1;" : "=r"(low), "=r"(high) :  "gr" (a), "d" (b) : "cc");

Non so se sia possibile ottenere tanto di più a livello di prestazioni ...
Premetto che sto cercando di capire pertanto non è che io abbia soluzioni ... anzi ... solo domande ...
Non sempre l'asm migliora le prestazioni, vedi: https://stackoverflow.com/questions/9601427/is-inline-assembly-language-slower-than-native-c-code

Per generare altro hash rigeneri casualmente in numero o fai +1 cercando la soluzione tra i vicini?

Bisogna ammettere che ne hai fatta di strada anche nella programmazione ...


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

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


║║
.
.

║║
██
║║
.
.

║║
██
║║
.
║║


║║
arulbero
Legendary
*
Offline Offline

Activity: 1290
Merit: 1337


View Profile
November 14, 2018, 02:34:41 PM
Last edit: November 14, 2018, 02:58:52 PM by arulbero
 #15

Premetto che sto cercando di capire pertanto non è che io abbia soluzioni ... anzi ... solo domande ...
Non sempre l'asm migliora le prestazioni, vedi: https://stackoverflow.com/questions/9601427/is-inline-assembly-language-slower-than-native-c-code

Per generare altro hash rigeneri casualmente in numero o fai +1 cercando la soluzione tra i vicini?

Bisogna ammettere che ne hai fatta di strada anche nella programmazione ...


Quali hash? Sto generando chiavi pubbliche da chiavi private, niente hash (non sto parlando di generazione di indirizzi, ma di chiavi pubbliche).


Per l'aritmetica "multiprecision" è essenziale usare assembly, perchè a livello di C normale il "carry" (il riporto) non è gestito. Sommare o moltiplicare 2 numeri da 256 bit purtroppo è ben diverso da sommare o moltiplicare 2 vettori formati ciascuno da 4 elementi di 64 bit. Nell'aritmetica devi sommare prima le due cifre più a destra, poi verificare se hai fatto overflow, e poi passare alla cifre successive.

Esempio con 2 cifre:  (a1, a0) + (b1,b0) =


c0 = a0+b0

c1 = a1 + b1 + (c0 < a0)  <-- questa condizione, se vera, testimonia che a0 + b0 ha sforato


per esempio: 16 + 27


cifra unità = 6 + 7 = 3

cifra decine = 1 + 2 + (3 < 6) = 4

risultato = 43


ti consiglio di dare una rapida occhiata a questo se ti interessa --> https://cryptojedi.org/peter/data/pairing-20131122.pdf  pagina 8
Piggy
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1385



View Profile WWW
November 15, 2018, 07:12:09 AM
Merited by arulbero (2)
 #16

Se ho capito bene come usare il codice, su 16.396.194 chiavi pubbliche pare calcolarne 331.575 non correttamente.

Il primo caso si trova prendendo le coordinate dei due punti appena calcolati dal ciclo for interno in gen_batches_points08 per:

Code:
k= 36028797808045092L
i=2


in questo modo
Code:
for i in range(0,2049): #endomorphism + the complement private keys
...
(kmx1,kmx2)=batch2[i]
(kmy1,kmy2)=batch_minus[i]

ottengo:

Code:
kmx2=mpz(379959518814287045958648687471962984512966710861088625468824313811360031883L)
kmy2=mpz(92747954983170185218682381260230771573227638080083976457265008071145396556169L)
kmx1=mpz(7201604086710695650663508557402304478547658998818769447222340328578603507969L)
kmy1=mpz(31566297453090183625880834540517108001193318981570045279173760792728274893122L)

in questo caso entrambe le coordinate x non sono corrette

Ho modificato  gen_batches_points08 in modo da calcolare gli indirizzi così dovrebbe essere visibile il problema
Code:
#!/usr/bin/env python

#this script computes 6x667 batchs of 4097 points (1 single point + 2048 couples of points -> (kG+mG, kG-mg))
#16,4 millions of points
#3 : 1 batch + 5 endomorphism

import datetime

from ecc_for_collider05 import *
from KeyHelper import *
from random import randint



def generateConsecutiveAddresses(lowest_key,batches):
    totFaulty=0
    #print("Begin:" + str(datetime.datetime.now()))
    ########################################################################
    #in this section the script pre-computes 1G, 2G, 3G, ..., 2048G
    mG = [(0,0)]*2049
    mGx = [0]*2049
    mGy = [0]*2049

    mGx[1]=Gx
    mGy[1]=Gy
    mG[1]=(Gx,Gy) #list of multiples of G,
                  #you have to precompute and store these multiples somewhere

    mGx[2]=mpz(0xC6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5)
    mGy[2]=mpz(0x1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A)
    mG[2]=(mGx[2],mGy[2])

    for i in range(3,2049):
    
        jx,jy,jz=add_j_j(Gx, Gy, mpz(1), mGx[i-1], mGy[i-1], mpz(1)) #this is not a efficient way, but it is not important
        jzinv = inv(jz,p)
        (x,y) = jac_to_aff(jx, jy, jz, jzinv)
        mG[i] = (x,y)
        mGx[i] = x
        mGy[i] = y

    ###########################################################################
    lowest_key=lowest_key                       #put here the lowest key you want to generate
    number_of_batches=batches #                     #put here how many consecutive batches you want to generate
    number_of_keys=4097*6*number_of_batches     #this is the number of consecutive keys you are going to generate
                                                #this number is always a multiple of 6*4097=24582, because 24582 is the minimum size
                                                #remember: you generate always 6 batches at once, 1 in (1,2^160) and 5 out of this range
                                                #their name are:  main_batch (the main), batch2, batch3, batch_minus
                                                #(these other batches are derived from the main with endomorphism or complement private keys)


    id_batch=lowest_key+2048                    #id_batch is now the private key of the middle point of the first batch that you want compute
    distance_between_successive_batches=4097    #this is the distance from the middle point of the first batch and the middle point
                                                #of the successive batch in (1,2^160)
                                                #4097 means that I'm generating only consecutive batches in (1,2^160), this is the default
                                

    start=id_batch                              #the first key to generate of the the first batch is the lowest key + 2048 -->
                                                #the middle point of the first batch
    stop=id_batch + number_of_batches*distance_between_successive_batches   #the key of the middle point of the last batch


    #k is always the id of the current main batch and the key of the middle point of the current main batch
    for k in range(start,stop,distance_between_successive_batches):

        jkx,jky,jkz = mul(k,Gx,Gy,mpz(1))   #here we use the slow function mul to generate the middle point
        #invjkz = inv(jkz,p)    
        invjkz=gmpy2.invert(jkz,p) # 1I
        (kx,ky) = jac_to_aff(jkx, jky, jkz, invjkz)
                            
        kminverse = [0]*2048
        kminverse = inv_batch(kx,mGx,p) #you need to compute 2048 inverse, 1 for each couple
                                        #to perform this task you need only the x coordinates of the multiples of G and
                                        #the x coordinate of kG: kx
        kminverse = [invjkz]+kminverse
                            #the element number 0 of the list is the inverse invjkz that you have computed to get kG=(kx,ky)
                            #the element number 1 of the list is the inverse necessary to perform kG + 1G (and kG-1G)
                            #--->  1/(x_of_1G - kx)
                            #the element number 2 of the list is the inverse necessary to perform kG + 2G (and kG-2G)
                            #--->  1/(x_of_2G - kx)
                            #...
                            #the element number m of the list is the inverse necessary to perform kG + mG (and kG-mG)
                            #--->  1/(x_of_mG - kx)
                            #then the name: "kminverse", the inverse to get the generic kG+mG
                            #...
                            #the element number 2048 of the list is the inverse necessary to perform kG+2048G and kG-2048G
                            #---> 1/(x_of_2048G - kx)  
        
    
        main_batch=[(0,0,0,0)]*2048
        #the element number 0 of the list will be the middle point kG=(kx,ky), you can see it as the couple ((k+0)G, (k-0)G)  
        #the element number 1 will be the couple (k+1)G, (k-1)G
        #the element number 2 will be the couple (k+2)G, (k-2)G
        #...
        #the element number 2048 will be the couple (k+2048)G, (k-2048)G
        #each element of this list is a couple of points -> 4 scalars: x_(k+m)G,y_(k+m)G,x_(k-m)G,y_(k-m)G,
        #but the first element is only a fake couple
        main_batch = double_add_P_Q_inv(kx,ky,mG,kminverse)    
        #_the function double_add_P_Q_inv computes kG +/-mG, it uses the list of the inverse and return a list of couple of points
        #each element of this list is a couple of points, 4 scalars, x_(k+m)G,y_(k+m)G,x_(k-m)G,y_(k-m)G
        #this list has 2049 elements    
    
        main_batch = [(kx,ky,kx,ky)]+main_batch #the element number 0 of the list is now the middle point kG=(kx,ky), you can see it as the fake couple (k+0)G, (k-0)G
    
        batch2=[0] * 2049   #this is the batch2 with lambda*kG, ( lambda*(k+1)G, lambda*(k-1)G ),  ( lambda*(k+2)G, lambda*(k-2)G ), ....,
                            # (lambda*(k+2048)G, lambda*(k-2048)G)
                            #this list actually has only the x-cooordinates of the points, because the y-coordinates are the same of main batch
                            #each element of this list is a couple of x -> 2 scalars: x_lambda*(k+m)G, x_lambda*(k-m)G                      
                            #this list has 2049 elements
    

        batch3=[0] * 2049   #this is the batch3 with lambda^2*kG, ( lambda^2*(k+1)G, lambda^2*(k-1)G ),  ( lambda^2*(k+2)G, lambda^2*(k-2)G ), ....,
                            # (lambda^2*(k+2048)G, lambda^2*(k-2048)G)
                            #this list actually has only the x-cooordinates of the points, because the y-coordinates are the same of main batch
                            #each element of this list is a couple of x -> 2 scalars: x_lambda^2*(k+m)G, x_lambda^2*(k-m)G                      
                            #this list has 2049 elements
    
                    
        batch_minus=[0] * 2049      #the complement private keys of the other batches
    
        for i in range(0,2049): #endomorphism + the complement private keys
        
            x1,y1,x2,y2=main_batch[i]
 
            batch2[i] = [(x1*beta  % p), (x2*beta % p)]     #only x coordinates, the first and the third scalar of each element
                                                            #of the main batch
                                                            #private key: lambda*k mod n,  coordinate x: beta*x mod p  
            batch3[i] = [(x1*beta2 % p), (x2*beta2 % p)]    #only x coordinates, the first and the third scalar of each element
                                                            #of the main batch
                                                            #private key: lambda^2*k mod n,  coordinate x: beta^2*x mod p

            batch_minus[i]=[(-y1 % p), (-y2 % p)]       #only y coordinates, the 2^ and the 4^ scalar of each element of all batches

            (kmx1,kmx2)=batch2[i]
            (kmy1,kmy2)=batch_minus[i]

            address = generateAddress(uncompressedKey(hex(kmx1), hex(kmy1)))
            if address == "":
                totFaulty = totFaulty+1

            address = generateAddress(uncompressedKey(hex(kmx2), hex(kmy2)))
            if address == "":
                totFaulty = totFaulty+1


    a=number_of_keys//1000000
    #print ('You have just generated ' + str(a) + ' Millions of keys!!!')
    #print("End:" + str(datetime.datetime.now()))
    print ("Faulty coordinates: " + str(totFaulty))


generateConsecutiveAddresses(2**55+789079076,667)

questo è KeyHelper.py  per calcolare l'indirizzo
Code:
import binascii
import hashlib
import base58

def uncompressedKey(xcoord, ycoord):

    #compressedkey="04" + xcoord[2:66] + ycoord[2:66]
    ukey="04" + xcoord[2:66] + ycoord[2:66]
    
    return ukey;

def hash160(hex_str):
    sha = hashlib.sha256()
    rip = hashlib.new('ripemd160')
    sha.update(hex_str)
    rip.update( sha.digest() )
    #print ( "key_hash = \t" + rip.hexdigest() )
    return rip.hexdigest()  # .hexdigest() is hex ASCII

def generateAddress(publicKey):

    #print ( "len " + str(len(publicKey)))
    if(len(publicKey) < 130):
        return ""

    hex_str = bytearray.fromhex(publicKey)
    # Obtain key:

    key_hash = '00' + hash160(hex_str)

    # Obtain signature:

    sha = hashlib.sha256()
    sha.update( bytearray.fromhex(key_hash) )
    checksum = sha.digest()
    sha = hashlib.sha256()
    sha.update(checksum)
    checksum = sha.hexdigest()[0:8]

    address = base58.b58encode( bytes(bytearray.fromhex(key_hash + checksum)) )
    #print ( "bitcoin address = \t" + address )

    return address.decode("utf-8")





arulbero
Legendary
*
Offline Offline

Activity: 1290
Merit: 1337


View Profile
November 15, 2018, 12:36:49 PM
Last edit: January 03, 2019, 08:40:43 AM by arulbero
 #17

Se ho capito bene come usare il codice, su 16.396.194 chiavi pubbliche pare calcolarne 331.575 non correttamente.

Il primo caso si trova prendendo le coordinate dei due punti appena calcolati dal ciclo for interno in gen_batches_points08 per:

Non l'ho mai testata bene quella libreria, era più che altro un proof of concept per realizzare poi quella in C.
Grazie comunque delle osservazioni, quando avrò tempo ci darò un'occhiata, deve trattarsi di qualche bug, 1 chiave sbagliata ogni 50 è una frequenza strana.

Io uso questo script da me creato per controllare gli indirizzi:

Code:
python2 genadd.py 0x03

Private key : 0000000000000000000000000000000000000000000000000000000000000003
Public key  : f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
 
PrKey WIF u.: 5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreB1FQ8BZ
Address u.  : ec7eced2c57ed1292bc4eb9bfd13c9f7603bc338
Address u.  : 1NZUP3JAc9JkmbvmoTv7nVgZGtyJjirKV1

PrKey WIF c.: KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU74sHUHy8S
Address c.  : 7dd65592d0ab2fe0d0257d571abf032cd9db93dc
Address c.  : 1CUNEBjYrCn2y1SdiUMohaKUi4wpP326Lb

genaddy.py
Code:
#!/usr/bin/env python

#genera indirizzo

import hashlib, binascii
import sys


####__ECC COMPUTATION__####################################################

Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F #caratteristica del campo
n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 #ordine della curva


#calcola l'inverso di a modulo p --> a^-1    
#a e' un numero compreso tra 1 e p-1
#p e' un numero primo
#vedi http://www.springer.com/?SGWID=4-102-45-110359-0 pag.40 algoritmo 2.20
def inv(a,p):
u, v = a%p, p
x1, x2 = 1, 0
while u != 1 :
q = v//u
r = v-q*u
x = x2-q*x1
v = u
u = r
x2 = x1
x1 = x
return x1%p

#test: stampa l'inverso di 3 modulo 7
#print inv(3,7)


def aff_to_jac(ax, ay):
jax, jay, jaz = ax, ay, 1
return jax, jay, jaz

def jac_to_aff(jax, jay, jaz):
invjaz=inv(jaz,p)
ax, ay = (jax*invjaz**2) % p, (jay*invjaz**3) % p
return ax, ay


#https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates
#coordinate jacobiane
def add(jax, jay, jaz, jbx, jby, jbz):
u1 = (jax*jbz**2) % p
u2 = (jbx*jaz**2) % p
s1 = (jay*jbz**3) % p
s2 = (jby*jaz**3) % p
h = (u2-u1) % p
r = (s2-s1) % p
jcx = (r**2 -h**3-2*u1*h**2) % p
jcy = (r*(u1*h**2-jcx)-s1*h**3) % p
jcz = (h*jaz*jbz) % p
return jcx, jcy, jcz

def double(jax, jay, jaz):
s = (4*jax*jay**2) % p
m = (3*jax**2) % p
jax2 = (m**2 - 2*s) % p
jay2 = (m*(s-jax2) - 8*jay**4) % p
jaz2 = (2*jay*jaz) % p
return jax2, jay2, jaz2


def mul(d,jax,jay,jaz):

dax, day, daz = 0, 0, 1
if (d%2 == 1):
dax, day, daz = jax, jay, jaz #solo se d e' dispari
q=d//2
while q>0:
jax, jay, jaz = double(jax,jay,jaz)
if (q%2 > dax): #puo' succedere solo se dax=0 e q%2=1 cioe' la prima volta
dax, day, daz = jax, jay, jaz  #solo se d e' pari
elif (q%2):
dax, day, daz = add(jax, jay, jaz, dax, day, daz)  
q=q//2                      
            
return dax, day, daz



########################################################################
# 58 character alphabet used
__b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
__b58base = len(__b58chars)

def b58encode(v): #encode v, which is a string of bytes, to base58.    
long_value = 0

if bytes == str:  # python2
for (i, c) in enumerate(v[::-1]):
long_value += ord(c) << (8*i) # 2x speedup vs. exponentiation
else: # python3
for (i, c) in enumerate(v[::-1]):
long_value += ord(chr(c)) << (8*i) # 2x speedup vs. exponentiation
 
result = ''
while long_value >= __b58base:
     div, mod = divmod(long_value, __b58base)
     result = __b58chars[mod] + result
     long_value = div
result = __b58chars[long_value] + result

 # Bitcoin does a little leading-zero-compression:
 # leading 0-bytes in the input become leading-1s
nPad = 0
if bytes == str:  # python2
for c in v:
if c == '\0': nPad += 1
else: break

else:  # python3
for c in v:
if chr(c) == '\0': nPad += 1
else: break

return (__b58chars[0]*nPad) + result
###########################################################################


######## PRIVATE KEY #####################################
pr=int(sys.argv[1],16)
#print (pr)

if bytes == str:  # python2
if (len(hex(pr)) < 19):
print ('Private key : ' + '0'*(64+2-len(hex(pr))) + hex(pr)[2:])
else:
print ('Private key : ' + '0'*(64+3-len(hex(pr))) + hex(pr)[2:-1])
else: # python3
print ('Private key : ' + '0'*(64+2-len(hex(pr))) + hex(pr)[2:])


######## PUBLIC KEY ######################################
jax, jay, jaz = mul(pr,Gx,Gy,1)
ax, ay = jac_to_aff(jax, jay, jaz)
#print hex(ax)[:-1]
#print hex(ay)[:-1]

if bytes == str:  # python2
if (len(hex(ax)) < 19) and (len(hex(ay)) < 19):
print ('Public key  : ' + '0'*(64+2-len(hex(ax))) + hex(ax)[2:] + ' ' + '0'*(64+2-len(hex(ay))) + hex(ay)[2:])
if (len(hex(ax)) < 19) and (len(hex(ay)) > 19):
print ('Public key  : ' + '0'*(64+2-len(hex(ax))) + hex(ax)[2:] + ' ' + '0'*(64+3-len(hex(ay))) + hex(ay)[2:-1])
if (len(hex(ax)) > 19) and (len(hex(ay)) < 19):
print ('Public key  : ' + '0'*(64+3-len(hex(ax))) + hex(ax)[2:-1] + ' ' + '0'*(64+2-len(hex(ay))) + hex(ay)[2:])
if (len(hex(ax)) > 19) and (len(hex(ay)) > 19):
print ('Public key  : ' + '0'*(64+3-len(hex(ax))) + hex(ax)[2:-1] + ' ' + '0'*(64+3-len(hex(ay))) + hex(ay)[2:-1])
else: # python3
print ('Public key  : ' + '0'*(64+2-len(hex(ax))) + hex(ax)[2:] + ' ' + '0'*(64+2-len(hex(ay))) + hex(ay)[2:])

####################################################################################

#### PRIVATE KEY WIF UNCOMPRESSED (start with 5, 51 car.) ##########################

#pr=int(sys.argv[1],16)
#print ('Private key : ' + '0'*(64+2-len(hex(pr))) + hex(pr)[2:])
if bytes == str:  # python2
if (len(hex(pr)) < 19):
pr_wif='80'+'0'*(64+2-len(hex(pr)))+hex(pr)[2:] #primo passaggio: aggiungi 80
else:
pr_wif='80'+'0'*(64+3-len(hex(pr)))+hex(pr)[2:-1]
else: #python3
pr_wif='80'+'0'*(64+2-len(hex(pr)))+hex(pr)[2:] #primo passaggio: aggiungi 80

#print (pr_wif)

pr1=binascii.unhexlify(pr_wif)
h=hashlib.new('sha256')        #secondo passaggio: sha256 di 80+pr
h.update(pr1)
#print h.hexdigest()

pr2=binascii.unhexlify(h.hexdigest())
h2=hashlib.new('sha256')  
h2.update(pr2)                 #terzo passaggio: sha256(sha256(80+pk))
#print h2.hexdigest()


pr3=pr_wif+h2.hexdigest()[:8]  #quarto passaggio: aggiungere primi 4 byte del terzo passaggio a pr_wif
#print (pr3)


pr_wif=b58encode(binascii.unhexlify(pr3)) #ultimo passaggio: codifica in base 58
print (' ')
print ('PrKey WIF u.: ' + pr_wif)

###############ADDRESS UNCOMPRESSED###########################

if bytes == str:  # python2
if (len(hex(ax)) < 19) and (len(hex(ay)) < 19):
pk='04'+'0'*(64+2  -len(hex(ax))) + hex(ax)[2:]   + '0'*(64+2  -len(hex(ay))) + hex(ay)[2:] #formato non compresso
if (len(hex(ax)) < 19) and (len(hex(ay)) > 19):
pk='04'+'0'*(64+2  -len(hex(ax))) + hex(ax)[2:]   + '0'*(64+2+1-len(hex(ay))) + hex(ay)[2:-1]
if (len(hex(ax)) > 19) and (len(hex(ay)) < 19):
pk='04'+'0'*(64+2+1-len(hex(ax))) + hex(ax)[2:-1] + '0'*(64+2  -len(hex(ay))) + hex(ay)[2:]
if (len(hex(ax)) > 19) and (len(hex(ay)) > 19):
pk='04'+'0'*(64+2+1-len(hex(ax))) + hex(ax)[2:-1] + '0'*(64+2+1-len(hex(ay))) + hex(ay)[2:-1]
else: # python3
pk='04'+'0'*(64+2-len(hex(ax))) + hex(ax)[2:] + '0'*(64+2-len(hex(ay))) + hex(ay)[2:]

#pk = '0400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001'
#pk = 'bitcoin'
pkb=binascii.unhexlify(pk)
#pkb = 'bitcoin'
h=hashlib.new('sha256')       #secondo passaggio: sha256 di pk
h.update(pkb)
#print h.hexdigest()

r=hashlib.new('ripemd160')    #terzo passaggio: ripmed160 di pk
r.update(h.digest())
#print r.hexdigest()

pk4='00'+r.hexdigest()        #quarto passaggio: aggiungere byte 00

pk5=binascii.unhexlify(pk4)   #quinto passaggio: sha256 di pk4
h2=hashlib.new('sha256')
h2.update(pk5)
#print h2.hexdigest()

h3=hashlib.new('sha256')
h3.update(h2.digest())        #sesto passaggio: sha256 di pk
#print h3.hexdigest()

pk7=pk4+h3.hexdigest()[:8]    #settimo/ottavo passaggio: sha256 di pk
#print (pk7)

print ('Address u.  : ' + pk7[2:-8])

address=b58encode(binascii.unhexlify(pk7)) #ultimo passaggio: codifica in base 58
print ('Address u.  : ' + address)

####################################################################################


#### PRIVATE KEY WIF COMPRESSED (start with a, K or L, 52 car.) ##########################

if bytes == str:  # python2
if (len(hex(pr)) < 19):
pr_wif_c='80'+'0'*(64+2-len(hex(pr)))+hex(pr)[2:]+'01' #primo passaggio: aggiungi 80 e 01
else:
pr_wif_c='80'+'0'*(64+3-len(hex(pr)))+hex(pr)[2:-1]+'01' #primo passaggio: aggiungi 80 e 01
else: #python3
pr_wif_c='80'+'0'*(64+2-len(hex(pr)))+hex(pr)[2:]+'01' #primo passaggio: aggiungi 80 e 01

#print (pr_wif_c)

pr1=binascii.unhexlify(pr_wif_c)
h=hashlib.new('sha256')        #secondo passaggio: sha256 di 80+pr
h.update(pr1)
#print h.hexdigest()

pr2=binascii.unhexlify(h.hexdigest())
h2=hashlib.new('sha256')  
h2.update(pr2)                 #terzo passaggio: sha256(sha256(80+pk))
#print h2.hexdigest()


pr3=pr_wif_c+h2.hexdigest()[:8]  #quarto passaggio: aggiungere primi 4 byte del terzo passaggio a pr_wif
#print pr3

pr_wif_c=b58encode(binascii.unhexlify(pr3)) #ultimo passaggio: codifica in base 58
print ('')
print ('PrKey WIF c.: ' + pr_wif_c)

#########ADDRESS COMPRESSED##########################################
if bytes == str:  # python2
if (ay % 2) == 0:
if (len(hex(ax)) < 19):
pk='02' + '0'*(64+2  -len(hex(ax))) + hex(ax)[2:] #formato compresso - caso y pari
else:
pk='02' + '0'*(64+2+1-len(hex(ax))) + hex(ax)[2:-1]
else:
if (len(hex(ax)) < 19):
pk='03' + '0'*(64+2  -len(hex(ax))) + hex(ax)[2:] #formato compresso - caso y dispari
else:
pk='03' + '0'*(64+2+1-len(hex(ax))) + hex(ax)[2:-1]
else: # python3
if (ay % 2) == 0:
pk='02'+ '0'*(64+2-len(hex(ax))) + hex(ax)[2:] #formato compresso - caso y pari
else:
pk='03'+ '0'*(64+2-len(hex(ax))) + hex(ax)[2:] #formato compresso - caso y dispari

#pk = '020000000000000000000000000000000000000000000000000000000000000001'
#pk = '0200000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63'
#pkb =
pkb=binascii.unhexlify(pk)
h=hashlib.new('sha256')       #secondo passaggio: sha256 di pk
h.update(pkb)
#print h.hexdigest()

#print (h.hexdigest())

r=hashlib.new('ripemd160')    #terzo passaggio: ripmed160 di pk
r.update(h.digest())
#print r.hexdigest()

pk4='00'+r.hexdigest()        #quarto passaggio: aggiungere byte 00

pk5=binascii.unhexlify(pk4)   #quinto passaggio: sha256 di pk4
h2=hashlib.new('sha256')
h2.update(pk5)
#print h2.hexdigest()

h3=hashlib.new('sha256')
h3.update(h2.digest())        #sesto passaggio: sha256 di pk
#print h3.hexdigest()

pk7=pk4+h3.hexdigest()[:8]    #settimo/ottavo passaggio: sha256 di pk
#print (pk7)

print ('Address c.  : ' + pk7[2:-8])

address=b58encode(binascii.unhexlify(pk7)) #ultimo passaggio: codifica in base 58
print ('Address c.  : ' + address)
arulbero
Legendary
*
Offline Offline

Activity: 1290
Merit: 1337


View Profile
November 15, 2018, 09:11:58 PM
Last edit: November 16, 2018, 11:40:26 AM by arulbero
Merited by Piggy (1)
 #18

@ Piggy

Ho notato adesso che la tua funzione di generazione di address "controlla" che una chiave pubblica sia corretta guardando solo la lunghezza delle coordinate, non capisco che senso abbia, quindi una chiave pubblica (x,y) che soddisfa l'equazione y^2 = x^3 + 7 mod p ma ha coordinata x con meno di 64 caratteri hex non è valida?

In media è ovvio che 1 chiave ogni 16 sarà lunga 63 caratteri (quindi per te non valida), 1 ogni 16^2 sarà lunga 62 caratteri (sempre non valida) e così via, mi pare normale quindi che molte chiavi ti risultino non valide.

Ma perchè x = 3 (1 sola cifra) dovrebbe essere per forza non valida? In media ogni 2 valori di x (tra quelli possibili da 1 a p) corrisponde a una coordinata di un punto sulla curva. Se tu generassi tutti i 2^256 punti della curva (chiavi pubbliche) con il mio script la tua funzione classificherebbe circa 1/2 dei 2^252 valori possibili (minori di 64 cifre esadecimali) per le coordinate come non valide.

Devi aggiungere degli zeri davanti alla sequenze più corte fino a raggiungere i 64 caratteri, se vuoi dare in pasto a sha256 queste chiavi pubbliche.


EDIT: per chi fosse interessato alla lunghezza delle coordinate dei punti della curva secp256k1 (chiavi pubbliche), questo punto è quello con la coordinata x minore di tutti:

Code:
x = 0000000000000000000000000000000000000000000000000000000000000001
y = 4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee

tempo fa ho provato a generare molte chiavi pubbliche ( 2^48 o giù di lì) e quella con la x minore che ho trovato (e della quale quindi conosco anche la chiave privata) è questa:

Code:
x = 000000000000aeea7a7a5c04504f6e4e45452940431c9a264011686f3b746f92

mentre quella con la x minore tra quelle di cui è nota chiave privata ha la seguente x :
Code:
x = 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

ed è stata trovata da Gregory Maxwell, la storia di quest'ultimo punto è molto interessante ed è legata alla costruzione del punto G, il generatore della curva https://crypto.stackexchange.com/questions/60239/elliptic-curve-and-vanity-public-keys.
Piggy
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1385



View Profile WWW
November 16, 2018, 06:13:58 AM
Last edit: November 16, 2018, 06:33:54 AM by Piggy
 #19

Devi aggiungere degli zeri davanti alla sequenze più corte fino a raggiungere i 64 caratteri, se vuoi dare in pasto a sha256 queste chiavi pubbliche.


EDIT: per chi fosse interessato alla lunghezza delle coordinate dei punti della curva secp256k1 (chiavi pubbliche), questo punto è quello con la coordinata x minore di tutti:

Code:
x = 0000000000000000000000000000000000000000000000000000000000000001
y = 4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee

tempo fa ho provato a generare molte chiavi private ( 2^48 o giù di lì) e quella con la x minore che ho trovato (e della quale quindi conosco anche la chiave privata) è questa:

Code:
x = 000000000000aeea7a7a5c04504f6e4e45452940431c9a264011686f3b746f92

mentre quella con la x minore tra quelle di cui è nota chiave privata ha la seguente x :
Code:
x = 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

ed è stata trovata da Gregory Maxwell, la storia di quest'ultimo punto è molto interessante ed è legata alla costruzione del punto G, il generatore della curva https://crypto.stackexchange.com/questions/60239/elliptic-curve-and-vanity-public-keys.

Ora ho capito, ero cosciente della possibilità che il problema lo stessi creando da solo e capisco anche il perchè nel tuo codice di questo ora:

Code:
'0'*(64+2+1-len(hex(ax)))
in
Code:
print ('Public key  : ' + '0'*(64+2+1-len(hex(ax))) + hex(ax)[2:-1] + ' ' + hex(ay)[2:-1])

Adesso funziona tutto end to end, proverò a leggermi i tuoi commenti per vedere se riesco a capirne un pò di più su come funziona il resto, grazie
arulbero
Legendary
*
Offline Offline

Activity: 1290
Merit: 1337


View Profile
November 16, 2018, 03:32:22 PM
 #20

Adesso funziona tutto end to end, proverò a leggermi i tuoi commenti per vedere se riesco a capirne un pò di più su come funziona il resto, grazie

Ok, e se riesci a trovare un modo per velocizzare il tutto fammi sapere!
Pages: [1]
  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!