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!
Topic: Vanity address mining (Read 458 times)
Ok, e se riesci a trovare un modo per velocizzare il tutto fammi sapere!
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:
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:
mentre quella con la x minore tra quelle di cui è nota chiave privata ha la seguente x :
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.
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)))
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
@ 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:
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:
mentre quella con la x minore tra quelle di cui è nota chiave privata ha la seguente x :
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.
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.
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:
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)
print ('Private key : ' + hex(pr)[2:].rstrip('L').rjust(64,'0'))
######## PUBLIC KEY ######################################
jax, jay, jaz = mul(pr,Gx,Gy,1)
ax, ay = jac_to_aff(jax, jay, jaz)
print ('Public key : ' + hex(ax)[2:].rstrip('L').rjust(64,'0') + ' ' + hex(ay)[2:].rstrip('L').rjust(64,'0'))
####################################################################################
#### 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:])
pr_wif = '80' + hex(pr)[2:].rstrip('L').rjust(64,'0') #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###########################
pk = '04' + hex(ax)[2:].rstrip('L').rjust(64,'0') + hex(ay)[2:].rstrip('L').rjust(64,'0')
#pk = '0400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001'
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.) ##########################
pr_wif_c = '80' + hex(pr)[2:].rstrip('L').rjust(64,'0') +'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 (ay % 2) == 0:
pk = '02' + hex(ax)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari
else:
pk = '03'+ hex(ax)[2:].rstrip('L').rjust(64,'0') #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)
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:
in questo modo
ottengo:
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
questo è KeyHelper.py per calcolare l'indirizzo
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")
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 ...
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
...
Tutto il codice delle operazioni base come moltiplicazione tra 2 numeri di 64 bit , eccetera è stato scritto da me "a mano" in questa forma:
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 ...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 ...
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 ...
Ho fatto una prova veloce sulla mia macchina,impiega 20 secondi, nettamente più veloce dell'altro. 
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.
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 ...
Ho fatto una prova veloce sulla mia macchina,impiega 20 secondi, nettamente più veloce dell'altro.
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.
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.
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
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
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!!!')
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
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
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 hai già fatto qualche esperimento del genere o mi sai consigliare qualche libreria in particolare?
Tempo fa avevo fatto questa in python (python2)
https://bitcointalksearch.org/topic/m.17685839
ma non so se è molto chiaro il suo utilizzo. Prova a dare un'occhiata (non ricordo le prestazioni, ma non erano pessime)
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 hai già fatto qualche esperimento del genere o mi sai consigliare qualche libreria in particolare?
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://bitcointalksearch.org/topic/m.47712972 , 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).
...
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.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.
...
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.
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.
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
...
Quindi tocca continuare a generare chiavi a caso fino a quando non si trova un indirizzo col pattern che ci interessa.
..
E meno male Quindi tocca continuare a generare chiavi a caso fino a quando non si trova un indirizzo col pattern che ci interessa.
..
Ok mi sembrava strano infatti visto che mi ero guardato come passare dalla chiave pubblica all indirizzo , 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
, 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
...
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 ...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?
(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).
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://bitcointalksearch.org/topic/m.17299181
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?
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://bitcointalksearch.org/topic/m.17299181
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?
Jump to: