Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 43. (Read 60095 times)

legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
August 05, 2021, 07:52:08 AM
cool bro but one issue is appearing

Code:
Traceback (most recent call last):
  File "shiftdown.py", line 47, in
    P = shiftdown(P, factor, outf, convert=False)
  File "shiftdown.py", line 28, in shiftdown
    P = Q - (i * G)
TypeError: unsupported operand type(s) for -: 'NoneType' and 'Point'

There was a small typo, try it now.
jr. member
Activity: 81
Merit: 2
August 04, 2021, 10:21:28 PM
In that case this should do the trick:

Code:
from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)



# This function makes all the downscaled pubkeys obtained from subtracting
# numbers between 0 and divisor, before dividing the pubkeys by divisor.
def shiftdown(pubkey, divisor, file, convert=True):
    if convert:
        Q = pub2point(pubkey)
    else:
        Q = pubkey
    # k = 1/divisor
    k = pow(divisor, N - 2, N)
    for i in range(divisor+1):
        P = Q - (i * G)
        P = k * P
        if (P.y % 2 == 0):
            prefix = "02"
        else:
            prefix = "03"
        hx = hex(P.x)[2:].zfill(64)
        hy = hex(P.y)[2:].zfill(64)
        file.write(prefix+hx+"\n") # Writes compressed key to file

factor = 32

with open("input.txt") as f, open("output.txt", "a") as outf:
    line = f.readline()
    if line:
        P = pub2point(line)
    while line:
          line = f.readline()
          Q = pub2point(line)
          P = shiftdown(P, factor, outf, convert=False)

This is for all keys in one file, I technically *could* script the case of one set of shifted keys per file, but then it requires an argc/argv switch to toggle the one you want and implementing that will bloat the code size Tongue

cool bro but one issue is appearing

Code:
Traceback (most recent call last):
  File "shiftdown.py", line 47, in
    P = shiftdown(P, factor, outf, convert=False)
  File "shiftdown.py", line 28, in shiftdown
    P = Q - (i * G)
TypeError: unsupported operand type(s) for -: 'NoneType' and 'Point'
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
August 04, 2021, 06:30:08 PM
In that case this should do the trick:


EDIT NUMBER 3: THIS VERSION ACTUALLY WORKS USE THIS ONE

Code:
from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)



# This function makes all the downscaled pubkeys obtained from subtracting
# numbers between 0 and divisor, before dividing the pubkeys by divisor.
def shiftdown(pubkey, divisor, file, convert=True):
    Q = pub2point(pubkey) if convert else pubkey
    print(Q, 'QQ')
    # k = 1/divisor
    k = pow(divisor, N - 2, N)
    for i in range(divisor+1):
        P = Q - (i * G)
        P = k * P
        if (P.y % 2 == 0):
            prefix = "02"
        else:
            prefix = "03"
        hx = hex(P.x)[2:].zfill(64)
        hy = hex(P.y)[2:].zfill(64)
        file.write(prefix+hx+"\n") # Writes compressed key to file

factor = 32

with open("input.txt", "r") as f, open("output.txt", "w") as outf:
    line = f.readline().strip()
    while line != '':
          shiftdown(line, factor, outf)
          line = f.readline().strip()

This is for all keys in one file, I technically *could* script the case of one set of shifted keys per file, but then it requires an argc/argv switch to toggle the one you want and implementing that will bloat the code size Tongue



EDIT: I had posted an older version of the script which people complained had a bunch of errors, admittingly I did not test this version with the file input since the base script was already "bug free" I thought these should be straightforward changes... well now I know  Embarrassed

After some proper testing, I got rid of a bunch of artifacts from older script versions that were triggering lint errors, and the result is posted here, above.
jr. member
Activity: 40
Merit: 7
August 04, 2021, 09:42:12 AM
i want to load 300 keys from file line by line and do the divisor calculation on each one 32 time and save output in file.

Again, one file total, or one file for each pubkey?

Printing all the keys in a single file becomes messy to read but is doable.

yes please if you can share such script
jr. member
Activity: 50
Merit: 7
August 04, 2021, 09:24:03 AM
Kangaroo pool up and running if anyone wants to join!

the pool is currently at 2^27/2^35.55 DP in only 4 days! we will be finding this address soon as more people join.

The prize will be split according to the number of kangaroos you supply to the pool as well as your speed. We only want QUALITY kangaroos, which means if you change your gpu grid to supply more kangaroos but decrease your speed to do so these are not quality kangaroos and you be paid on your speed to the pool.

https://github.com/yoyodapro/Kangaroo-Server

The pool is currently at 2^28.081/2^35.55 DP, thank you to all that are joining us!

As has been discussed in our discord, if you are afraid of losing the work youve already put into your own kangaroo search, we are allowing users to contribute their own work files (DP 25 and above) towards their share of the prize.
jr. member
Activity: 81
Merit: 2
August 04, 2021, 07:51:56 AM
i want to load 300 keys from file line by line and do the divisor calculation on each one 32 time and save output in file.

Again, one file total, or one file for each pubkey?

Printing all the keys in a single file becomes messy to read but is doable.

1 file total is fine & if it is easy to script both that would be perfect :p
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
August 04, 2021, 06:34:24 AM
i want to load 300 keys from file line by line and do the divisor calculation on each one 32 time and save output in file.

Again, one file total, or one file for each pubkey?

Printing all the keys in a single file becomes messy to read but is doable.
jr. member
Activity: 81
Merit: 2
August 04, 2021, 05:12:28 AM
@NotATether

i have 300 public keys and loading one by one in this script is painful. can you please modify this script to get a file of public keys and process one by one all.

You mean like compute the sum of all 300 pubkeys? Or shifting down all the keys in a file by a fixed amount? Either way, it's a straightforward change, but for the division script specifically you need to tell me whether the divisor is the same for all numbers and how you want the output to be made (i.e. all "shifted" keys for each public keys, or just some shifted keys, or some public keys?)

Code:
from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

pk1 = '031656894a2e404e652e3a2b368c7df820b0e92fe32529c41931a9f7b234457d5b'
pk2 '022fa21d1cea4bc1f9911a9d501e3d8b3c97d15aaa76a63fecd0d529b9ef2e22f5'

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)

def add(pk1, pk2, convert=True):
    if convert:
        P = pub2point(pk1)
        Q = pub2point(pk2)
    else:
        P = pk1
        Q = pk2
    R = P + Q
    return R

def sub(pk1, pk2, convert=True):
    if convert:
        P = pub2point(pk1)
        Q = pub2point(pk2)
    else:
        P = pk1
        Q = pk2
    R = P - Q
    return R


def point2pub(R):
    # Remove the following code if you are doing multiple additions successively
    # as it brings a speed improvement, and just return R
    if (R.y % 2 == 0):
        prefix = "02"
    else:
        prefix = "03"
    hx = hex(R.x)[2:].zfill(64)
    return hx

with open("input.txt") as f:
    line = f.readline()
    if line:
        P = pub2point(line)
    while line:
          line = f.readline()
          Q = pub2point(line)
          # Replace this with sub() if you want subtraction, as your last
          # post left me confused about what you want.
          P = add(P, Q, convert=False)

print(point2pub(P))


shifting down all the keys in a file by a fixed amount   <===  this one

i want to achieve ~  instead of loading one key here for divisor 32

pubkey = '03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4'

i want to load 300 keys from file line by line and do the divisor calculation on each one 32 time and save output in file.
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
August 04, 2021, 04:16:41 AM
@NotATether

i have 300 public keys and loading one by one in this script is painful. can you please modify this script to get a file of public keys and process one by one all.

You mean like compute the sum of all 300 pubkeys? Or shifting down all the keys in a file by a fixed amount? Either way, it's a straightforward change, but for the division script specifically you need to tell me whether the divisor is the same for all numbers and how you want the output to be made (i.e. all "shifted" keys for each public keys, or just some shifted keys, or some public keys?)

Code:
from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

pk1 = '031656894a2e404e652e3a2b368c7df820b0e92fe32529c41931a9f7b234457d5b'
pk2 '022fa21d1cea4bc1f9911a9d501e3d8b3c97d15aaa76a63fecd0d529b9ef2e22f5'

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)

def add(pk1, pk2, convert=True):
    if convert:
        P = pub2point(pk1)
        Q = pub2point(pk2)
    else:
        P = pk1
        Q = pk2
    R = P + Q
    return R

def sub(pk1, pk2, convert=True):
    if convert:
        P = pub2point(pk1)
        Q = pub2point(pk2)
    else:
        P = pk1
        Q = pk2
    R = P - Q
    return R


def point2pub(R):
    # Remove the following code if you are doing multiple additions successively
    # as it brings a speed improvement, and just return R
    if (R.y % 2 == 0):
        prefix = "02"
    else:
        prefix = "03"
    hx = hex(R.x)[2:].zfill(64)
    return hx

with open("input.txt") as f:
    line = f.readline()
    if line:
        P = pub2point(line)
    while line:
          line = f.readline()
          Q = pub2point(line)
          # Replace this with sub() if you want subtraction, as your last
          # post left me confused about what you want.
          P = add(P, Q, convert=False)

print(point2pub(P))
jr. member
Activity: 81
Merit: 2
August 03, 2021, 11:26:58 PM
Yes, I used the program almost like yours is written below.
But I compared it with yours and noticed a fundamental mistake.
And now everything works.
I am very grateful to you for your help.
I hope that my way of calculation is correct and I can share my work with here.

pk1 = '031656894A2E404E652E3A2B368C7DF820B0E92FE32529C41931A9F7B234457D5B'
pk2 = '022FA21D1CEA4BC1F9911A9D501E3D8B3C97D15AAA76A63FECD0D529B9EF2E22F5'

after addition result should be

02ea31f5d48f0c43969b607d592636e2443539e7a86ef1350dba0d9040a98fc378

how come you are looking for

0297539272d59d6e75488df9a5628e7b0efc03b4fec79de246ac116ae40c05225a  ?
Pretty sure he used subtraction

lol
yes indeed    =>  R = P - Q

0297539272d59d6e75488df9a5628e7b0efc03b4fec79de246ac116ae40c05225a

full member
Activity: 1232
Merit: 242
Shooters Shoot...
August 03, 2021, 11:24:06 PM
Yes, I used the program almost like yours is written below.
But I compared it with yours and noticed a fundamental mistake.
And now everything works.
I am very grateful to you for your help.
I hope that my way of calculation is correct and I can share my work with here.

pk1 = '031656894A2E404E652E3A2B368C7DF820B0E92FE32529C41931A9F7B234457D5B'
pk2 = '022FA21D1CEA4BC1F9911A9D501E3D8B3C97D15AAA76A63FECD0D529B9EF2E22F5'

after addition result should be

02ea31f5d48f0c43969b607d592636e2443539e7a86ef1350dba0d9040a98fc378

how come you are looking for

0297539272d59d6e75488df9a5628e7b0efc03b4fec79de246ac116ae40c05225a  ?
Pretty sure he used subtraction
jr. member
Activity: 81
Merit: 2
August 03, 2021, 11:18:14 PM
Yes, I used the program almost like yours is written below.
But I compared it with yours and noticed a fundamental mistake.
And now everything works.
I am very grateful to you for your help.
I hope that my way of calculation is correct and I can share my work with here.

pk1 = '031656894A2E404E652E3A2B368C7DF820B0E92FE32529C41931A9F7B234457D5B'
pk2 = '022FA21D1CEA4BC1F9911A9D501E3D8B3C97D15AAA76A63FECD0D529B9EF2E22F5'

after addition result should be

02ea31f5d48f0c43969b607d592636e2443539e7a86ef1350dba0d9040a98fc378

how come you are looking for

0297539272d59d6e75488df9a5628e7b0efc03b4fec79de246ac116ae40c05225a  ?
jr. member
Activity: 81
Merit: 2
August 03, 2021, 10:45:38 PM
@NotATether

i have 300 public keys and loading one by one in this script is painful. can you please modify this script to get a file of public keys and process one by one all.

Code:
from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

pubkey = '03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4'

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)



# This function makes all the downscaled pubkeys obtained from subtracting
# numbers between 0 and divisor, before dividing the pubkeys by divisor.
def shiftdown(pubkey, divisor):
    Q = pub2point(pubkey)
    # k = 1/divisor
    k = pow(divisor, N - 2, N)
    for i in range(divisor+1):
        P = Q - (i * G)
        P = k * P
        if (P.y % 2 == 0):
            prefix = "02"
        else:
            prefix = "03"
        hx = hex(P.x)[2:].zfill(64)
        hy = hex(P.y)[2:].zfill(64)
        print(prefix+hx, "04"+hx+hy)

shiftdown(pubkey, 32)

jr. member
Activity: 50
Merit: 7
August 03, 2021, 04:26:27 PM
Kangaroo pool up and running if anyone wants to join!

the pool is currently at 2^27/2^35.55 DP in only 4 days! we will be finding this address soon as more people join.

The prize will be split according to the number of kangaroos you supply to the pool as well as your speed. We only want QUALITY kangaroos, which means if you change your gpu grid to supply more kangaroos but decrease your speed to do so these are not quality kangaroos and you be paid on your speed to the pool.

https://github.com/yoyodapro/Kangaroo-Server
jr. member
Activity: 38
Merit: 1
August 03, 2021, 02:04:57 PM
Yes, I used the program almost like yours is written below.
But I compared it with yours and noticed a fundamental mistake.
And now everything works.
I am very grateful to you for your help.
I hope that my way of calculation is correct and I can share my work with here.
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
August 03, 2021, 11:12:37 AM
Hello .
Someone can suggest.
How to write a program in python for taking away and adding the Public key from the public key.

You mean something like this?

Code:
from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

pk1 = '031656894a2e404e652e3a2b368c7df820b0e92fe32529c41931a9f7b234457d5b'
pk2 '022fa21d1cea4bc1f9911a9d501e3d8b3c97d15aaa76a63fecd0d529b9ef2e22f5'

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)

# This function makes all the downscaled pubkeys obtained from subtracting
# numbers between 0 and divisor, before dividing the pubkeys by divisor.
def add(pk1, pk2):
    P = pub2point(pk1)
    Q = pub2point(pk2)
    R = P + Q
    # Remove the following code if you are doing multiple additions successifly
    # as it brings a speed improvement, and just return R
    if (R.y % 2 == 0):
        prefix = "02"
    else:
        prefix = "03"
    hx = hex(R.x)[2:].zfill(64)
    return hx

add(pk1, pk2)

I get everything, but not this result.
Also, with addition, the result is not correct.

With which program did you do the addition?
jr. member
Activity: 38
Merit: 1
August 03, 2021, 09:51:06 AM
Hello .
Someone can suggest.
How to write a program in python for taking away and adding the Public key from the public key.
An example.
031656894a2e404e652e3a2b368c7df820b0e92fe32529c41931a9f7b234457d5b (d456ba310f)   - 022fa21d1cea4bc1f9911a9d501e3d8b3c97d15aaa76a63fecd0d529b9ef2e22f5    (23fa540bcd)


result
0297539272d59d6e75488df9a5628e7b0efc03b4fec79de246ac116ae40c05225a (B05C662542)


I get everything, but not this result.
Also, with addition, the result is not correct.

I would be grateful if you indicate where to find the corresponding sketch in python.
Sincerely .
full member
Activity: 706
Merit: 111
August 02, 2021, 08:26:14 AM
maybe your all calc wrong, giving you example
generate 70 bit random key, and use kanagroo to find it, note the time
then split 70 bit 65 bit with 32 keys and try to find one by one in 65 bit and note time,
then split 70 bit 65 bit with 32 keys and try to find 32 keys parallel in 65 bit and note time,
you will have time calc result


Jean_Luc planned to release a new version (after solved #115), where it will be possible to use the saved file (they got 300GB file) for other keys in the same range. I think that would speed up checking a lot of keys.  No news about this?

Who said that was going to happen, Jean_Luc was last active on here last week and still hasn't said a word about anything.
member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
August 02, 2021, 04:55:39 AM
Guys, take a look at this: https://link.springer.com/content/pdf/10.1007/s11227-020-03441-5.pdf

A faster modular multiplication implementation for the P-192 curve.

Granted this is the wrong curve, but it has the same general formula y2 = x3+ax+b, so all that theoretically has to be done is to extend the summations to a few extra terms (they'll just be 32 words instead of 24, which means a 32x32 word multiplication size instead of 24x24) and accommodate for the missing ax.

E.g. where it defines range shifted representation (RSR) of a large number, which it uses in the algorithm:

Code:
X = ∑ i=0,i=23 xiWi−12 = x0W−12 + x1W−11 + ⋯ + x23W11,
Y = ∑i=0,i=23 yiWi−12 = y0W−12 + y1W−11 + ⋯ + y23W11,
Z = X ⋅ Y = ∑i=0,i=47 ziWi−24 = z0W−24 + z1W−23 + ⋯ + z47W23

We can just replace it with this:

Code:
X = ∑ i=0,i=31 xiWi−16 = x0W−16 + x1W−15 + ⋯ + x31W15,
Y = ∑i=0,i=31 yiWi−16 = y0W−16 + y1W−15 + ⋯ + y31W15,
Z = X ⋅ Y = ∑i=0,i=63 ziWi−32 = z0W−32 + z1W−31 + ⋯ + z63W31

(x, y, z summation terms are all between 0 and 255 inclusive)

Then the rest of the modular multiplication follows suit.

They say it's 26% faster than the usual ECC multiplication algorithm. I wonder if this representation also handles modular addition well. If it does, then we got ourselves a faster way to do modular arithmetic.

The study was carried out on some 8-bit embedded machine. Modern pipelines stuff 64 bits in a register so we may even be able to reduce the number of RSR words by a factor of 8 i.e. only 2 x and y words and 4 z words (and ovbiously the maximum range of each word increases proportionally).

I think all modern methods about speed up SECP operation include point addition and multiplication etc in this article(codes included) https://paulmillr.com/posts/noble-secp256k1-fast-ecc/ if use a Jacobian coordinates with a endomorphism  and windows method/

I think this is an interesting method, if we do not forget that brute forse is jast addition of points, multiplication and comparison of the result with the target pubkey is an endomorphism and a splitting point into 2 parts, and the brute 2 parts separately.... but due to the fact that many people here, like me, are a bit lazy, all the methods are being implemented too slowly.
jr. member
Activity: 48
Merit: 11
August 02, 2021, 04:26:51 AM
maybe your all calc wrong, giving you example
generate 70 bit random key, and use kanagroo to find it, note the time
then split 70 bit 65 bit with 32 keys and try to find one by one in 65 bit and note time,
then split 70 bit 65 bit with 32 keys and try to find 32 keys parallel in 65 bit and note time,
you will have time calc result


Jean_Luc planned to release a new version (after solved #115), where it will be possible to use the saved file (they got 300GB file) for other keys in the same range. I think that would speed up checking a lot of keys.  No news about this?
Pages:
Jump to: