Armadillo ECDSA-113

[contextrax]

I did a more accurate calculation and I see now we have a 18% change of solving.
Here is the formula based on the wiki birthday page:
100*(1-exp(-((0xAD87E3B2BA1AE)**2)/(2*(2**112/(2*113)))))

Put this into google and it should print out ~18.36
0xAD87E3B2BA1AE is the current iteration of today

When we hit 2^52 iterations we have a ~35.69% chance of solving.
100*(1-exp(-((2**52)**2)/(2*(2**112/(2*113)))))

2^53 would give ~83% so I don't think we need to go this far

Need more CPU's

[contextrax]

Originally Posted by SKiLLa

No I simply meant an update to the solver .exe it self
I get that the status and data itself will be updated through the Server-stats.

For example if you would encounter a bug (i.e. want to push a fix) or have some improved attack algorithm.

Ofcourse for this specific EC-113 Arma curve it's not very likely (since most crunching already has been done); but perhaps for a future version attacking a different curve or using different (non Arma) Crypto-constraints. ECC is everywhere nowadays, so I can imagine another iteration some day ...

Ah I see now.
Well if I started to push new exe files then I guess none would dare running it
Of course they needed to be digitally signed so no one could just hack my server and send out new updates but then everyone must trust me
The solver exe file I have made public was uploaded to virus total so you could check it before you run it. I think asking more from any one running it would be a bit to much.

Anyone else would like to comment on this? Would you run a self up gradable exe from someone you don't know?

[SKiLLa]

It doesn't have to be an auto-update feature; it could just advertise it as in 'There is a new version x.xx; download here: ...'. Great stuff on adding the probability btw; is that like a hardcoded message or does it use the mentioned formula in (semi-) real-time ?

[Abaddon]

Under different circumstances i would have joined the project. Unfortunately a power surge about 9 months ago has fried up my windows machine, leaving me with a macbook air with the processing power of a potato-powered flashlight.

However, i find the coordinated effort and the explanations given to this thread to be of much more value than the final product of this specific project. Could I entice you guys (especially contextrax, who seems to be the initiator and coordinator of the venture) to release (apart from the obvious final product, the private key) a paper describing the chronicle of the effort, explaining the methods used, and perhaps suggesting pointers for future collaborative efforts on similar projects (with emphasis on how a distributive attack system should be designed?).

[contextrax]

Originally Posted by SKiLLa

It doesn't have to be an auto-update feature; it could just advertise it as in 'There is a new version x.xx; download here: ...'. Great stuff on adding the probability btw; is that like a hardcoded message or does it use the mentioned formula in (semi-) real-time ?

For now it's hard coded manually.

[SKiLLa]

@Abaddon: Much of the theory & math behind attacking a 113 bit Koblitz curve it can be found in the whitepaper contextrax already linked (and others; there's quite a lot of research on it actually). But I certainly second your suggestion about the implementation optimalisation & distributed coordination details.

Would love to see this project turn into an open source framework for future alike distributed projects, but I do realize that it would take some serious effort by contextrax (and hopefully others) to get there (plugin architecture, accounting, redundancy, result verification distribution algorithms, etc) ...

[SKiLLa]

Hi guys,

I convinced a friend of mine to join sieving; but he's running Linux Mint 18.x and using Wine to run the solver tool; which is running just fine and reporting works as well (I can see his points in my solver stats-screen just fine), but when he tries the [Get Server Statistics], he always get a 'Server Error' (and the error-log holds no additional data).

Anyone a clue ? His machine is reported as Win64 in the local-statsfile ...

[contextrax]

Originally Posted by SKiLLa

Hi guys,

I convinced a friend of mine to join sieving; but he's running Linux Mint 18.x and using Wine to run the solver tool; which is running just fine and reporting works as well (I can see his points in my solver stats-screen just fine), but when he tries the [Get Server Statistics], he always get a 'Server Error' (and the error-log holds no additional data).

Anyone a clue ? His machine is reported as Win64 in the local-statsfile ...

It's a bit strange that reading server stats wont work while posting points do.
You could ask him to try again coz I just moved my server to a different provider.
Also the Win64 is a hard coded value in the solver so there is no OS detection there.
If I make a linux version then this field will be updated.

[contextrax]

ECDLP Solved

Start date 2017.08.22
Solution found on 2018.01.19

The two colliding points was both found on my own computers.
Number of points collected is 11.423.593
Total number of iteration used is 0x1AE3F1`AE655476 (7 568 976 546 976 886)
The probability for solving at this point was 71.2% (Using both negation and frobenius map). This is a bit on the unlucky side. I was really hoping to get a solution before this.
The average number of iteration to find a distinguish point is 0x277E13F9. If I was to do this again I would lower this value.
Fastest point was found after only 0x2D iterations and the longest run to find one was 0x2`9F20FA67 iterations
Loading all points into memory required 348 Meg of RAM and it took about 3.5 min to load them and to calculate the solution.


Different CPU speeds running the solver v1.47:
Intel Core i7-6700 @ 3.40 GHz was able to get 52 million iterations/sec. (4 cores + HT)
Intel Core i5-4590 @ 3.30 GHz got 31 million iterations/sec
Intel Core i5-4250U @ 1.30 GHz got 14 million iterations/sec. (2 cores + HT)

Target: "Armadillo v9.64 Public"

Optimal Normal Base Type II
BasepointInit: 1570789295 (0x5DA057AF)
ONB2 Base.X  : 4089747062247003654720736468506441
ONB2 Base.Y  : 10111618751385367037406972360317044
ONB2 Pub.X   : 2127081270816270912006137526418476
ONB2 Pub.Y   : 7206819234412870204027887633390168
Secret       : 1984557253727814641989266002264698

Pub = Secret*Base

---- Start Keygen -----
Using HK symmetric key: BDA4FA1C
Key bytes before encryption: 1B 2E BD A4 FA 1C
Basepointinit set to : 0x5DA057AF (1570789295)
seed128 string  : "PVTKEYECCRND1516390685"
Using secret key: 1984557253727814641989266002264698
Curve SEED      : 1570789295
Base Point x    : 4089747062247003654720736468506441
Base Point y    : 10111618751385367037406972360317044
Public Point x  : 2127081270816270912006137526418476
Public Point y  : 7206819234412870204027887633390168
Private key     : 1984557253727814641989266002264698
key bytes       : 0A 84 04 23 16 01 48 41 43 4B 45 52 4D 41 4E 40 48 41 43 4B 2E 4E 45 54
prng string     : MAODAFJOEACPMLOJOOPPNDFIDKGJIIIENBJECGKF

User : hackerman@hack.net
Key : 000014-588113-2R0T9R-E9YFYX-45W1QA-Z7X7WV-A36KAY-8CDJZF-WP5JUM-8PBHCB

[tonyweb]

Thank you contextrax for your work (and the math!) and for sharing the results.
Great job!

Just want to add this statement (IMHO it was missing from the post above ) ... forgive me if it's inappropriate:

Thank you also to all who, in the shadows or in a gray area (lol ), helped with running the tool and seeding results

Best Regards,
Tony

[bolo2002]

Originally Posted by tonyweb

Thank you also to all who, in the shadows or in a gray area (lol ), helped with running the tool and seeding results [/U]

Best Regards,
Tony

glad to provide many cpu's times to help with it.

[contextrax]

Originally Posted by bolo2002

not even a thank you,i expected a bit more from you.
i let run run many hours your solver to help.
well,it's a world and it's like that,i learn every day..

Isn't it against the forum rule to write thanks?

Anyway. Thanks for joining in on this.

[Stingered]

Originally Posted by contextrax

Isn't it against the forum rule to write thanks?

Anyway. Thanks for joining in on this.

Indeed it is, lol!

I do appreciate your hard work and I sincerely hope that mr.exodia adds this functionality to his AKT!

Cheers mate!

[MrScotc]

Hi, is it possible to write down all your discovery and translate into a PDF ?

[contextrax]

Here is the link to a stripped down source code if anyone wants to have a look.
A GPU version and or Linux version would be great

If any questions then just shoot

ECC Source