Pollard's kangaroo ECDLP solver

[COBRAS]

propably  the benefit of calculating it in zones could be only with veryfing or and calculating nearest point in the zone.
then substract those pubkey from zone minus pubkey from nearest point , it is difficult to explain (english is not my natural languge), then in looping substracting -still veryfing nearest point you can be sure  when you are "small distance" from power of two. then you can recalculate key.

it is numerical way -> it works , but is slowly.
but it takes time.

Try find a this private key. My public key redused complexity !!!

More info https://bitcointalk.org/index.php?topic=5362587.msg58034486#msg58034486

[wedom]

...
And how is it possible to determine which PubKey is in which Zone?

That's the whole problem.
For example, when we divide it by 32, we get 32 public keys, which will be defined in 32 (predefined zones), including in our zone, where we expect it. One key per zone.
BUT which of the 32 zones the report starts with is not known. If you know at least one key in which zone is located, it is easy to calculate the remaining 31. Since they go "around the circle" in order. The starting point depends on the remainder of the division by 32, which we do not know.

[NotATether]

When openSSL uses /dev/urandom, then even the last 5 digits will be random.

OpenSSL private keys aka. 256-bit random numbers by themselves will not help with reducing the number of keys, however it is estimating the bias (as in - empirically, some bits will appear in a certain state more often than others - when several thousand random numbers are generated) in OpenSSL random numbers this estimation method draws its power from.

Also this doesn't work if your sample only one private key, that's why I mentioned that thousands of random numbers need to be sampled. My calculations get away with just 1000, though.

That's the whole problem.
For example, when we divide it by 32, we get 32 public keys, which will be defined in 32 (predefined zones), including in our zone, where we expect it. One key per zone.
BUT which of the 32 zones the report starts with is not known. If you know at least one key in which zone is located, it is easy to calculate the remaining 31. Since they go "around the circle" in order. The starting point depends on the remainder of the division by 32, which we do not know.

Hence why it's more efficient to just guesstimate the most likely remainders by observing what kind of random bits appear at the end.

[a.a]

This makes actually no sense, because the underlying principle is different.

example:

Puzzle 11
https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000483

038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b

halving the publickey:
03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d

03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 is the result, when the privatekey of puzzle 11 is even and
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d if the the privatekey of puzzle 11 is odd.

02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is the correct one, as the privatekey of puzzle 11 is odd  
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000241

So if you do 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d + 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d, you get 038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b (untested, I guess you need also adding the Generatorpoint for + 1 as we do 241 + 241 + 1 = 483)

So what is 03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 then? It is 241.5.
241.5 + 241.5 = 483

So, where do we find 241.5?

https://privatekeys.pw/key/7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b1e5f

How did I find it? key middle range minus half of our privatekey: 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 - 0x241 => tada

So from complexity of 11 bits, i just needed to check 10 bits now.

If I divide by 32, I actually do what?

2 * 2 * 2 * 2 * 2 = 32

So we are halving the public key 5 times. This means, that when we do this on key 11, we get 32 keys, from where one of them has the correct endsequence of the private key. So we have to check all keys if they are in the range of 2^6. If we get one, than we know how the first 6 bits of the privatekey are. We can from here determine the last 5 bits easily. I am not interested in the other ranges, as i have now a total valid privatekey

[a.a]

It doesnt matter if you know if it is even or odd. If you shiftdown you always get a solution for last bit being even and one for odd.

So if you divide by 32, you will have 31 publickeys which are out of your modified searchrange not leading to the solution and one which will be in the searched range.

[a.a]

You could give me your 40 bit public key. But cracking it is kind of waste of time, as I would need to do alot manually, you know...

But how to crack it:
I would bit shift your public key by 65536 ( 2 ^ 16).  I will then have 65536 pubkeys and one of them is in range 2 ^ 24. I will run it on BitCrack and get the key in 2 ^24. By the position of the publickey in the list, I can determine according to the method of NotATether the privatekey (did not unterstand it actually... lol). Or I just bit shift the input and output 16 times by 2 getting actually generate a "decision tree". Then I only need to follow the decision tree and get the correct private key.

So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.

[a.a]

I added also following to my original post

So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.

Why will we have 31 public keys and not 32?

You will have 32 pubkeys, but from those 32 pubkeys only one will be in the desired range. The other 31 pubkeys will be all over the place, and thus being uninteresting.

[wedom]

...
OpenSSL private keys aka. 256-bit random numbers by themselves will not help with reducing the number of keys, however it is estimating the bias (as in - empirically, some bits will appear in a certain state more often than others - when several thousand random numbers are generated) in OpenSSL random numbers this estimation method draws its power from.

Also this doesn't work if your sample only one private key, that's why I mentioned that thousands of random numbers need to be sampled. My calculations get away with just 1000, though.

...

I recently did a little research on private key generation via /dev/urandom. More than 100 million keys were used for the test. The bit allocation was about the same = 0.5
Maybe the old versions of OpenSSL, which were probably used in the puzzle creation, had some vulnerabilities and gave some deviation?

[wedom]

You will have 32 pubkeys, but from those 32 pubkeys only one will be in the desired range. The other 31 pubkeys will be all over the place, and thus being uninteresting.

Thank you.
I translated it incorrectly at first, then I understood what was talking about and deleted my message.

[a.a]

for 40 bit it is 5 minutes.

With 300 MKey/s it will be for me 1 hour.

2^40 = 1,099511628×10¹²

1,099511628×10¹² keys / 300000000 keys/s = 3665,038759253 s = 61 minutes

I suppose that if you don't know range of public key, you can't nothing.

Well. we are cracking this puzzle currently, right . So as I wrote earlier, this bitshifting is a memory/processing performance tradeoff. The more you bitshift the more keys you have to check, till it is not practical anymore. So e.g. you could store 2^30 pubkeys into a bloom filter and need about 4 GB memory or 2 ^31 pubkeys and about 8 GB RAM or 2 ^32 pubkeys and about ....

So if you would have 65 bits, you would bitshift it by the amount of pubkeys you can effectively  store in your bloom filter. Lets say you can store 2 ^ 31 pubkeys in your bloom filter. Now you have only to generate the pubkeys and store them and crack them. Get the privatekey, shiftup and remove the first bits from the 65 bits of the pubkey and get a new shorter pubkey. Crack again like you did with the first bits. Shift up and remove the next bits. small amount of bits left, crack them. Now add privatekeys from the three rounds and voila you have the privatekey of the 65 bit in about an no time.

Maybe not as fast as BSGS or Kangaroo, but still faster then BruteForce. Also BSGS is possible to crack multiple keys, Kangaroo currently can only crack one pubkey at a time, so totally useless for this bitshifting operation.

because if it works, you are millionaire, and the question what are you doing on forum:D

lets say you want to crack 256 bit publickey. You could bitshift by lets say 30 bits. You would still need to bruteforce 226 bits. 

[WanderingPhilospher]

You could give me your 40 bit public key. But cracking it is kind of waste of time, as I would need to do alot manually, you know...

But how to crack it:
I would bit shift your public key by 65536 ( 2 ^ 16).  I will then have 65536 pubkeys and one of them is in range 2 ^ 24. I will run it on BitCrack and get the key in 2 ^24. By the position of the publickey in the list, I can determine according to the method of NotATether the privatekey (did not unterstand it actually... lol). Or I just bit shift the input and output 16 times by 2 getting actually generate a "decision tree". Then I only need to follow the decision tree and get the correct private key.

So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.

Why would you need a decision tree? Once you find the pubkey/private key in the 24 bit range, you have solved the private key for the original 40 bit public key.

[WanderingPhilospher]

exactly yes.

 you can use after shifting :
https://github.com/iceland2k14/bsgs -> version multiplies pubkeys

Sloooooooooooooooooooooooooow....lol

You can use just about any GPU cracking program to speed up the process versus slowed down multi pub python script.

[WanderingPhilospher]

So if you would have 65 bits, you would bitshift it by the amount of pubkeys you can effectively  store in your bloom filter. Lets say you can store 2 ^ 31 pubkeys in your bloom filter. Now you have only to generate the pubkeys and store them and crack them. Get the privatekey, shiftup and remove the first bits from the 65 bits of the pubkey and get a new shorter pubkey. Crack again like you did with the first bits. Shift up and remove the next bits. small amount of bits left, crack them. Now add privatekeys from the three rounds and voila you have the privatekey of the 65 bit in about an no time.

You just plug it back into your script that help you bitshift and you have the private key to the original 65 bit pub key. All that shifting back up, shorter pub key, etc. is over kill.

[fxsniper]

How can test and proof "subtracted" methods  it is work?
I would like to try and testing.

[fxsniper]

this is just idea think out of box from "subtracted" methods 

I don't know much about in deep of ECDLP
I know only basic, simple and overview about ECDLP

Did have some video or document description for learning ECDLP  from scratch? (include how to multiply private key to ECDLP step by step, I know how to using function but can not calculate by manual?

Can ECDLP can be scale?
y2=x3+0x+7(mod p)
Y^2 = X^3 + ax + b
(what correct formula of algorithm)

Now ECDLP is 256 bit right?
Can ECDLP scale down to 128 bit?
Can ECDLP scale up to 512 bit?

if can not, please ignore.
Just silly question?

if ECDLP can scale
Can possible to test ECDLP 128 bit for fast found then up scan it
or
Can possible to test ECDLP 512 bit for possible hit one and down scale it

I forget knowledge a lot it like brainwasher myself all about crypto (now like a newbies)

[a.a]

@WanderingPhilosopher
If you store it in a file, you can lookup the position. But is there a formula for shifting it up by knowing the position of the pubkey?

@fxsniper

Do you read? It is a memory tradeoff! If you bitshift a 256 bit key 128 bit you will have 2^128 keys to check in a range of 1-2^128. 2^128 is how many petabytes???

Please inform yourself about ECDLP. I invested last few weeks in my freetime to understand how it works and what to do.

[a.a]

Also dont forget:
The Problem we have is, that we don't know if the last bit is even or odd. If you know if the last bit is even or odd, you can crack any public key in no time.

[ssxb]

guys big lol here plus some explanation from my side.

the script shared by NotATether is just doing opposite of divisor it is increasing 5 bit and giving you last key 5 bit uper range. only difference is while doing divisor you will get 1 key from down 5 bit and other all from defined uper bits range on exact same distance from reference value of this formula

Code:

N=115792089237316195423570985008687907852837564279074904382605163141518161494337
for i in range(32):
    print(i, hex((((N-1)//32)*i+1)%N))

lets say we have key 10  and we do divisor of 10 so what we get is like this (just example)

upper reference range
210 ,  200   , 190 , 180 .................. until 10
assume after divisor each key will have 5 bit down from reference ranges based of exact same distance
205  ,  195 ,  185 , 175 .................  until 5

here is problem , position in 32 keys list is not always same so you cant guess which key is in which range at which position. but if you guess one key correctly which range that key is then you can find easily which is correct 5 bit down key at what position as all other keys ranges are always in sequence. if you do increment of one key all the keys will get increment as well and perhaps they will switch position also in divisor output.


now talk about NotATether script,

the script he posted is doing mod inverses and it is just multiplying value until reach 5 uper bit. (no one can get 120 how can they will get 125 lolololo)

exapmle

key is in 120 range and you used his script output will be

120, 121 , 122, 123, 124, 125 thats it . all 32 keys will be from 120 to 125 range and some range will have 2 or more keys. but guaranteed all keys will be between 120 ~ 125 range at known position as 125 bit will be at 32 position and divisor will have only one key from lower 5 bit guaranteed (not known position) and all other keys from exact same distance with upper reference range. hope you get the point.


now talk about brainless theory -


NotATether and brainless are misunderstanding each other brainless maybe joked that he reduced keys 720 by doing multiplication , addition and subtraction bla bla bla until 90 or 100 bit but NotATether  is insisting what he explained inside his posts is not a way & there is also no way to achieve that and perhaps he never achieved that one and just keep lying.

now what i think is brainless have to explain this to community

Code:

" I got it down to 104 bits today, but with 32,000 pubkeys; better than the normal 2^16 normally required, but I can't figure out a way to shrink it down to one key... "
for 10 bit down = 1024 pubkeys
for 20 bit down = 1024*1024 = 1048576 pubkeys
for 30 bit down = 1024*1024*1024 = 1073741824 pubkeys
1048576 and 1073741824 pubkeys with each other addition and mutiplication will return you 260 pubkeys apear where 16 pubkeys sure inside 10 bit down from main pubkey
these 260 pubkeys again played for get 30 bit down for 1/720 pubkeys
now you can start to find with above tip 

as how he claimed this one and plus dont forget he claimed before that he found the 120 key but no plan to cash it but same time he asked .75 bitcoin to provide 115 range one key to buy 3090 (WTF)

well i think i got headache now time to drink coffee 

[a.a]

ssxb

Your post makes not so much sense to me?!

How does brainless approach reduce the amount of public keys? Did you understand what he meant? Can you elaborate it further?

[studyroom1]

ssxb

Your post makes not so much sense to me?!

How does brainless approach reduce the amount of public keys? Did you understand what he meant? Can you elaborate it further?

ok which part doesn't make sense , if you asking about 1/720 keys part ~ that what brainless said in his previous posts. check his last posts and you will find these comments.

and if you ask me this is possible  or not? , yes this is possible but not the way he explained.

but there is one problem with my yes. it is very difficult to guess specific range where you can start searching your calculated keys. perhaps you will guess 10 keys are in 110 range but they are not there.

is that right ssxb?