Topic: Pollard's kangaroo ECDLP solver - page 17. (Read 56355 times)
Guys Quick question, since I can't get my head around how Kangaroo works in terms of Maths, i was wondering if Kangaroo would still consider a private key within the range, a valid key even if it turns out to be just another colliding key of the 2^96 possible keys that resolve to an address on average .. actually thinking of this while writing, I don't see a reason why not .. but would like if someone could confirm
Sure you can: R of the signature is the X coordinate of the curve point nonce*G. So you can use kangaroo to search for (R, y) and (R, -y). Then you would have the nonce k and could solve for privatekey.
Well yeah, but you'd still need to figure out the Y coordinate for the nonce*G point - using only raw tx data on the blockchain - before you can run it through Kangaroo [and something tells me that it's not S or Z].
Quote
And it usually is a sha256 hash for the message but I don't think ECDSA specifies a hashing algorithm so you can use whatever you want for the hash as long as the other side knows what algorithm you have been using if they want to rebuild the hash from the message.
So I think you should refresh your knowledge of ECDSA
.
So I think you should refresh your knowledge of ECDSA
.I was assuming fxsniper was talking specifically about Bitcoin tx signatures (which use ECDSA with sha256 hash) so I made my post around that idea.
Of course, an ECDSA signature based on an MD5 or CRC32 hash wouldn't be too hard to break ;-)
I mean, How to know ECDSA has collisions like that?
I don't think Pollard's Kangaroo will work against ECDSA sigs because there is a SHA512 hash of the message bytes which forms a second line of defence against brute-force.
So even if you cook up a Kangaroo iteration that takes you from R,S to the origional message, it's still hashed, so you'd have to find a different way around that.
Sure you can: R of the signature is the X coordinate of the curve point nonce*G. So you can use kangaroo to search for (R, y) and (R, -y). Then you would have the nonce k and could solve for privatekey.
And it usually is a sha256 hash for the message but I don't think ECDSA specifies a hashing algorithm so you can use whatever you want for the hash as long as the other side knows what algorithm you have been using if they want to rebuild the hash from the message.
So I think you should refresh your knowledge of ECDSA
. I mean, How to know ECDSA has collisions like that?
I don't think Pollard's Kangaroo will work against ECDSA sigs because there is a SHA512 hash of the message bytes which forms a second line of defence against brute-force.
So even if you cook up a Kangaroo iteration that takes you from R,S to the origional message, it's still hashed, so you'd have to find a different way around that.
I'm not sure what you mean by who can find out they have a collision...the program lets you know when a collision has occurred and the key has been solved.
I mean, How to know ECDSA has collisions like that?
know from any report/research? or who find out
just would like to know step by step develop on this forum before Pollard's kangaroo ECDLP release
the first version is that python script right and then develop c++ for use GPU with high speed calculate
Ummmm the theory has been around since the 1970s; some smart people were just able to program it into a modern day programming language to speed it up/incorporate the use of GPUs.
More info:
https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm
I'm not sure what you mean by who can find out they have a collision...the program lets you know when a collision has occurred and the key has been solved.
I mean, How to know ECDSA has collisions like that?
know from any report/research? or who find out
just would like to know step by step develop on this forum before Pollard's kangaroo ECDLP release
the first version is that python script right and then develop c++ for use GPU with high speed calculate
Code:
if both results is the same X that is collision right?
yesThank you WanderingPhilospher
Who can find out they have a collision? How did they find from some testing?
I had not been here when started the puzzle
Code:
if both results is the same X that is collision right?
yesThank you WanderingPhilospher
Who can find out they have a collision? How did they find from some testing?
I had not been here when started the puzzle
Well, Collisions work from DPs and as on wikipedia "the similarity between a visualisation of the algorithm and the Greek letter lambda ( λ ). The shorter stroke of the letter lambda corresponds to the sequence { x i }, since it starts from the position b to the right of x. Accordingly, the longer stroke corresponds to the sequence { y i }, which "collides with" the first sequence (just like the strokes of a lambda intersect) and then follows it subsequently. "
You know you have a collision if two different kangaroos start to output the same value. Say K1 output 1,3,5,8,9 and K2 output 2,4,5,8,9 we know that between K1 and K2 after 3 or 2 they collide. We then can then refer to the tame kangaroo and correlate the input value of the wild one or as JeanLucPons put it himself "The program uses 2 herds of kangaroos, a tame herd and a wild herd. When 2 kangoroos (a wild one and a tame one) collide, the key can be solved". the actual outputs are valid public keys and the inputs are valid private keys.
Code:
if both results is the same X that is collision right?
yesThank you WanderingPhilospher
Who can find out they have a collision? How did they find from some testing?
I had not been here when started the puzzle
https://github.com/JeanLucPons/Kangaroo
kangaroo calculate random both tame and wild right?
tame is multiplied with a random number with G
wild is multiplied by ADD PUBKEY(target) with a random number
if both results is the same X that is collision right?
How can control range random of tame?
How can control range random of the wild?
control on Kangaroo 2.2 (use GPU)
(in python kangaroo script I can modify it)
distinguished point (DP)
-d: Specify the number of leading zeros for the DP method (default is auto)
-d dpBit
What mean if use -d ?
-d 32 = distinguished point 32 bit
-d 64 = distinguished point 64 bit
-d 128 = distinguished point 128 bit
(I did not yet understand it)
kangaroo calculate random both tame and wild right?
tame is multiplied with a random number with G
wild is multiplied by ADD PUBKEY(target) with a random number
if both results is the same X that is collision right?
How can control range random of tame?
How can control range random of the wild?
control on Kangaroo 2.2 (use GPU)
(in python kangaroo script I can modify it)
distinguished point (DP)
-d: Specify the number of leading zeros for the DP method (default is auto)
-d dpBit
What mean if use -d ?
-d 32 = distinguished point 32 bit
-d 64 = distinguished point 64 bit
-d 128 = distinguished point 128 bit
(I did not yet understand it)
Code:
kangaroo calculate random both tame and wild right?
It assigns a random starting point (basically a private key value) within the user defined start and end range; after that, the kangaroos jump forward/positive based on average jump size; usually range width / 2 + 1.Code:
tame is multiplied with a random number with G
tame is calculating the point/key it landed on and generating the corresponding pubkeyCode:
wild is multiplied by ADD PUBKEY(target) with a random number
wild is calculating the point/key it landed on and generating the corresponding pubkey AND now adds the target pubkey Code:
if both results is the same X that is collision right?
yesCode:
What mean if use -d ?
-d 32 = distinguished point 32 bit
to keep it easy to understand, each character in the pubkey is equal to 4 bits. Each pubkey has 64 characters times 4 bits = 256 bits-d 32 = distinguished point 32 bit
so for a dp of 32, the pubkey has to start with 8 zeros (leading zeros); 8 x 4 = 32. for dp 28, 7 leading zeros, for dp 64, 16 leading zeros, etc.
https://github.com/JeanLucPons/Kangaroo
kangaroo calculate random both tame and wild right?
tame is multiplied with a random number with G
wild is multiplied by ADD PUBKEY(target) with a random number
if both results is the same X that is collision right?
How can control range random of tame?
How can control range random of the wild?
control on Kangaroo 2.2 (use GPU)
(in python kangaroo script I can modify it)
distinguished point (DP)
-d: Specify the number of leading zeros for the DP method (default is auto)
-d dpBit
What mean if use -d ?
-d 32 = distinguished point 32 bit
-d 64 = distinguished point 64 bit
-d 128 = distinguished point 128 bit
(I did not yet understand it)
kangaroo calculate random both tame and wild right?
tame is multiplied with a random number with G
wild is multiplied by ADD PUBKEY(target) with a random number
if both results is the same X that is collision right?
How can control range random of tame?
How can control range random of the wild?
control on Kangaroo 2.2 (use GPU)
(in python kangaroo script I can modify it)
distinguished point (DP)
-d: Specify the number of leading zeros for the DP method (default is auto)
-d dpBit
What mean if use -d ?
-d 32 = distinguished point 32 bit
-d 64 = distinguished point 64 bit
-d 128 = distinguished point 128 bit
(I did not yet understand it)
Someone try making sach scrypt ? Share code pls ?
Br
What is sach scrypt ?
Did you mean search script or scrypt hash algorithms ?
They meant "such a script"
Someone try making sach scrypt ? Share code pls ?
Br
What is sach scrypt ?
Did you mean search script or scrypt hash algorithms ?
1048576 and 1073741824 pubkeys with each other addition and mutiplication
Someone try making sach scrypt ? Share code pls ?
Br
What is sach scrypt ?
Did you mean search script or scrypt hash algorithms ?
" 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
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
can you share script to do these calculations or explain a way please
Someone try making sach scrypt ? Share code pls ?
Br
Now kangaroo found problem same BitCrack both range search is very large
kangaroo method still works but is stuck with a very large range of search
I do simple easy tests on both 120 bit and 160 bit (and 256) with keyspace (under 32 bit wide) nearby it is still found key
but when used with a very large rank and nowhere is key store, so kangaroo is stunned
Kangaroo and BSGS are both O root n complexity
root 120 is 2^60
2^60 is 1,152,921,504,606,846,976.
Can the discrete logarithm be computed in polynomial time on a classical computer? someday, but not tomorrow.
Now kangaroo found problem same BitCrack both range search is very large
kangaroo method still works but is stuck with a very large range of search
I do simple easy tests on both 120 bit and 160 bit (and 256) with keyspace (under 32 bit wide) nearby it is still found key
but when used with a very large rank and nowhere is key store, so kangaroo is stunned
Hi, is there a way to find private key range from the public key, (Start and Stop range) ? Can someone point me to the right direction
For any random private key this is not (yet?) possible, in the case of the puzzle the creator initially put an amount of btc correlating to the bit length of the corresponding key.
Like 0.64 btc to puzzle 64 (16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN)
it can possible to calculate rollback to know the sample tame and wild?
just idea would like to test check how far tame and wild on 120 bit
just idea would like to test check how far tame and wild on 120 bit
Hi, is there a way to find private key range from the public key, (Start and Stop range) ? Can someone point me to the right direction
Jump to: