Topic: Large Bitcoin Collider (Collision Finders Pool) - page 40. (Read 193404 times)

antonio@ubuntu:~/src/python$ ./gen_couple_points.py 
kG
0xbfcdf2
0xa884186c5d47633c9b58ae542b8b6797230c8e67808ade960793d4bc0e546cd3L
0xd74beb0250afe97f2d1ab66a02e689447b87a2df62383f4717b9452607a9b4ffL
*******
mG
0x1d1
0x87be732373bd4b738627fb63bd4d50bfd6f2bb81f804b52829549fe93fe1ac2eL
0xf6a9186ff147b9b5ffc844b2ec0e255a1ae5537d75624288ce8421f87e94e1a4L
*******
kG+mG
0xbfcfc3
0xc6292537e08b2fcad6e378b1673c446f279bed612ba928ad63d05cf6bbb8165L
0x3a744f5375e3207a53345975fc610cea7fb47dd738307e26d86e5d6bb775197dL
*******
kG-mG
0xbfcc21
0x893c80077fa3d8fcdc1fd6db146a389fec56e312bba27c3f7b3380c636a85e60L
0x6e8da51c1c82ffdbc0073bfcc00463cc50ec9dbf237efbb275503cf64886b5afL
*******

$ python gen_couple_points.py 
kG
0xbfcdf2
0xa884186c5d47633c9b58ae542b8b6797230c8e67808ade960793d4bc0e546cd3
0xd74beb0250afe97f2d1ab66a02e689447b87a2df62383f4717b9452607a9b4ff
*******
mG
0x1d1
0x87be732373bd4b738627fb63bd4d50bfd6f2bb81f804b52829549fe93fe1ac2e
0xf6a9186ff147b9b5ffc844b2ec0e255a1ae5537d75624288ce8421f87e94e1a4
*******
kG+mG
V: 115792089237316195423570985008687907853269984665640564039457584007908834671663
U: 100968868457032376717032254508194871768455479323471896895268685981853755980682
V: 100968868457032376717032254508194871768455479323471896895268685981853755980682
U: 0.0
Traceback (most recent call last):
  File "gen_couple_points.py", line 34, in 
    kmx, kmy = jac_to_aff(jkmx, jkmy, jkmz)  # 3M for the inverse + (1S + 3M) to normalize x and y -> 6M + 1S         
  File "/data/soft/lin/LBC/generator/HRD/arulbero-ECC/ecc_for_collider.py", line 84, in jac_to_aff
    invjaz=inv(jaz,p)       
  File "/data/soft/lin/LBC/generator/HRD/arulbero-ECC/ecc_for_collider.py", line 33, in inv
    q = v/u
ZeroDivisionError: float division by zero

def inv(a,p):   
        u, v = a%p, p
        x1, x2 = 1, 0
        while u != 1 :
                print("V:",v)
                print("U:", u)
                q = v/u
                r = v-q*u 
                x = x2-q*x1
                v = u
                u = r
                x2 = x1 
                x1 = x 
        return x1%p

secp256k1_gej_add_ge_var(r, r, &prec[j*n_values + bits], NULL);

secp256k1_gej_add_ge_var(j,j,a1);
secp256k1_gej_add_ge_var(j,j,a2);

secp256k1_gej_set_ge(ja1,a1);
secp256k1_gej_set_ge(ja2,a2);
secp256k1_gej_add_var(j, ja1, ja2);

secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2);

// hrdec_fe_sub_m1                       r = a - b (1)
SECP256K1_INLINE static void hrdec_fe_sub_m1(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe *b) {
  r->n[0] = 0xFFFFEFFFFFC2FULL * 4 - b->n[0] + a->n[0];
  r->n[1] = 0xFFFFFFFFFFFFFULL * 4 - b->n[1] + a->n[1];
  r->n[2] = 0xFFFFFFFFFFFFFULL * 4 - b->n[2] + a->n[2];
  r->n[3] = 0xFFFFFFFFFFFFFULL * 4 - b->n[3] + a->n[3];
  r->n[4] = 0x0FFFFFFFFFFFFULL * 4 - b->n[4] + a->n[4];
}

....
for (i = 1; i < 4096; i++) {
    secp256k1_fe_mul(&az[i], &az[i - 1], &a[i].z);
  }

  secp256k1_fe_inv_var(&u, &az[--i]);  // sets i to 4095 here  <---- You perform only 1 inverse

  while (--i) {
    secp256k1_fe_mul(&az[i + 1], &az[i], &u);
    secp256k1_fe_mul(&u, &u, &a[i + 1].z);
  }

for (i = 0; i < 4096; i++) {
    r[i].infinity = a[i].infinity;
    secp256k1_ge_set_gej_zinv(&r[i], &a[i], &az[i]);
  }

static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi) { 
75     secp256k1_fe zi2; 
76     secp256k1_fe zi3; 
77     secp256k1_fe_sqr(&zi2, zi);          --> you can compute this only 2048 instead of 4096
78     secp256k1_fe_mul(&zi3, &zi2, zi)  --> you can compute this only 2048 instead of 4096
79     secp256k1_fe_mul(&r->x, &a->x, &zi2); 
80     secp256k1_fe_mul(&r->y, &a->y, &zi3); 
81     r->infinity = a->infinity; 
82 } 

hrdec_mult_gen2(&batchpj[0], start);

for (i = 1; i < 4096; ++i) {
    hrdec_gej_add_ge(&batchpj[i], &batchpj[i-1], &incr_a);             // increment public key
  }

.....

static void hrdec_mult_gen2(secp256k1_gej *r,
                const uchar *seckey) {

  secp256k1_gej o1;
  secp256k1_gej s1, s2, s3, s4, s5, s6, s7, s8,
                s9,s10,s11,s12,s13,s14,s15,s16;


  secp256k1_gej_set_ge(&o1, &prec[      seckey[31]]);
  secp256k1_gej_add_ge_var(&s1, &o1, &prec[ 256 + seckey[30]], NULL);

  secp256k1_gej_set_ge(&o1, &prec[512 + seckey[29]]);
  secp256k1_gej_add_ge_var(&s2, &o1, &prec[ 768 + seckey[28]], NULL);

  secp256k1_gej_set_ge(&o1, &prec[1024 + seckey[27]]);
  secp256k1_gej_add_ge_var(&s3, &o1, &prec[1280 + seckey[26]], NULL);

  secp256k1_gej_set_ge(&o1, &prec[1536 + seckey[25]]);
  secp256k1_gej_add_ge_var(&s4, &o1, &prec[1792 + seckey[24]], NULL);

  secp256k1_gej_set_ge(&o1, &prec[2048 + seckey[23]]);
  secp256k1_gej_add_ge_var(&s5, &o1, &prec[2304 + seckey[22]], NULL);

....
secp256k1_gej t1;
  
  secp256k1_gej_add_var(&t1,  &s1,  &s2, NULL);
  secp256k1_gej_add_var(&s1,  &s3,  &s4, NULL);
  secp256k1_gej_add_var(&s2,  &s5,  &s6, NULL);
  secp256k1_gej_add_var(&s3,  &s7,  &s8, NULL);
  secp256k1_gej_add_var(&s4,  &s9, &s10, NULL);
  secp256k1_gej_add_var(&s5, &s11, &s12, NULL);
  secp256k1_gej_add_var(&s6, &s13, &s14, NULL);
  secp256k1_gej_add_var(&s7, &s15, &s16, NULL);


  secp256k1_gej_add_var(&s8, &t1, &s1, NULL);
  secp256k1_gej_add_var(&s1, &s2, &s3, NULL);
  secp256k1_gej_add_var(&s2, &s4, &s5, NULL);
  secp256k1_gej_add_var(&s3, &s6, &s7, NULL);

  secp256k1_gej x1,x2;

  secp256k1_gej_add_var(&x1, &s1, &s2, NULL);
  secp256k1_gej_add_var(&x2, &s3, &s8, NULL);

  secp256k1_gej_add_var(r, &x1, &x2, NULL);
}

static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr) { 
362     /* Operations: 12 mul, 4 sqr, 2 normalize, 12 mul_int/add/negate */ 
363     secp256k1_fe z22, z12, u1, u2, s1, s2, h, i, i2, h2, h3, t; 
364 
 
.....

414  static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr) { 
415     /* 8 mul, 3 sqr, 4 normalize, 12 mul_int/add/negate */ 
416     secp256k1_fe z12, u1, u2, s1, s2, h, i, i2, h2, h3, t; 

for (i = 1; i < 4096; ++i) {
    hrdec_gej_add_ge(&batchpj[i], &batchpj[i-1], &incr_a);             // increment public key
  }

U1 = X1  (Z2=1)      
U2 = X2*Z1^2    -->  1/2M (you have to compute Z1^2 only once in the batch, X2 is the same in +mG and -mG) 
S1 = Y1     
S2 = Y2*Z1^3     --> 1/2M (you have to compute Z1^3 only once in the batch, and remember that mG ->Y2, -mG -> -Y2) 
        
H = U2 - U1   =   X2*Z1^2 - X1    --> 0 M
R = S2 - S1   =   Y2*Z1^3 - Y1     -->  0 M
X3 = R^2 - H^3 - 2*X1*H^2          -->   (1 + 1/2)S + 2*1/2 M = 1,5S + 1M (H is the same each 2 addition)
Y3 = R*(X1*H^2 - X3) - Y1*H^3.     -->   1M + 1/2M = 1,5M (Y1 is the same,  H is the same each 2 addition )
Z3 = H*Z1  --> 1/2 M               --> (Z3 is the same each 2 addition, then the inverse is the same too!)
return (X3, Y3, Z3)

LBC -u