Quote:
Originally Posted by Abaddon
Sorry to bump. Any progress with the project? A pure keygen would be a nice epitaph for this once popular protector.
|
We have now collected 4.6 million ecc points (expected 6.5 million) which give above 2^51 number of iterations.
I was expecting 2^52 number of iteration to solve but this is based on luck.
The exact number of iterations today is: 0xAD87E`3B2BA1AE
The order of the fixed point on this curve is 2^112 bit and usually to solve we need above sqrt(2^112) number of iterations. That is 2^56.
Because of the frobenius and the negation map we get a speedup of sqrt(113*2) which gives around 2^52.
If anyone wonder why we need ~6.5 million points to solve then that is something i chose when I selected the properties on the distinguished point.
The properties is actually the hamming weight of the ecc points x coordinate in normal base.
If the number of bits is 25 we have a distinguished point. If I have selected a lower bit count we would have needed less points but also needed more iterations to find one. If I have selected a higher bit count we would have needed more points but less iterations to find one.
To many of them would flood my server and increased the offline work load. To few and we might need to search more and the chances of solving drops.
If my calculations are correct then with 25 bit prop I will need about 25gig of RAM on my offline server to solve. On this server I have 32 gig RAM.
If this blow then I need to find a server with more RAM of recode my offline solver to solve on disk and not load everything to memory.
The birthday paradox is explained on this page: https://en.wikipedia.org/wiki/Birthday_problem
And we can see here that the group is 365 and that sqrt(365) is ~19.
To have a 50% chance of solving (find a collision) we need 23 people which is above 19. With 19 we have like a 40% changes of collision.
So since we are a bit below sqrt(2^52) I would guess we are in the area of
25% chance of solving.
That table also shows that that chances of solving increases rapidly the more points we get.
But also you can see that to be 100% sure of solving we need like 365 people which gives us 2^112 iterations. Of course that is the worst worst case scenario and will probably never happen.
These algorithms based on luck is a bitch
Oh and my last attack on this curve (different target) I solved with only 1.5 million points. I guess I was extremely lucky.
Sorry for explaining the obvious but there might be some that is not to familiar with solving DLP / ECDLP.