Quote from: math09183 on June 20, 2020, 09:37:43 AM

Quote from: pooya87 on June 20, 2020, 05:45:05 AM

Quote from: math09183 on June 19, 2020, 09:07:55 PM

You mean that reduction is purely theoretical because of 'birthday paradox', right?

i am trying to point out that the reduction happened because this is a puzzle not a truly random private key.

I agree, but MrFreeDragon wrote "Do the weakness #2 (revealed public key) no need to brute all 116 bits (2^116), and only square root of total length is enough --> 58 bits (2^58)."
and this is part I do not understand.

BabyStep-GiantStep method allows to perform square root of the total length operations. The puzzle address search range was reduced by border and "special non touching requirement" down to 116 bits (2^116). So to find any key (symmetrical or not) withing this range only 2^58 operations are required (but also you should prepare a hashtable before search). To be honest you will not have enough RAM to prepare the hashtable for 116 bit key.

Here the code for BSGS you can use to find keys with specific ranges: https://github.com/JeanLucPons/BSGS

I did not mention in puzzle rules that the hidden monster was symmetric. So, it could be only the assumption (but reasonable assumption). Assuming that the "monster" could be symmetrical means that only 116/2=58 bits are unknown, because the 2nd part of the monster is just a mirrored from the 1st part. Symmetry could be vertical or horizontal - so you should try both, but more probable symmetry is vertical.

Now for 58 bits with BSGS you need only 2^29 operations - this is easy just for 1 CPU to calculate.

Quote from: sukbir on June 19, 2020, 01:31:48 PM

Hi MrFreeDragon, I did google search about Baby-step, Giant-step and Pollard method but I can't figure out how it works.
Do I need to have programming skills to learn about these thing Huh

-snip-

Google for "Discrete Logarithm Problem" and you can find a lot of researches and presentations. For better understanding try to start with available presentations, some of them contain all the methods and compare them with each other.

Also in order to understand how Pollard/BSGS methods work, start with elliptic curve understanding (private key --> public key; scalar additions/multiplication if public keys - these knowledge is important to understand DLP solving methods.