Elliptic Curve Discrete Logarithms


Web sites:
Europe:
http://pauillac.inria.fr/~harley/ecdl/
United States mirror:
ftp://ftp.mac-guru.com/pub/ecdl/


Latest updates:

(click reload or you might not see them)

Dec. 19th, 10pm:
We started on ECCp-89. It's over here.

Dec. 17th, 10am:
The weather sucks but I managed to get to the office and am hard at work on ECCp-89.

Dec. 16th, 12:47:
The 1618th point is a duplicate. Success!!!
Read our ECC2-79 submission.

Dec. 16th, midday:
Passed 1600 points. Getting into "unlucky" territory :-O

Dec. 15th, midday:
Passed 1300 points and still going.

Dec. 14th, midday:
Passed 1080 points, but no luck yet...

Dec. 13th, midday:
Passed 840 points (with some help from Jay's EV6 machine :)

Dec. 12th, midday:
Passed 550 points. We'll be done in no time!

Dec. 11th, midday:
Passed 300 points. Is this cool or what?

Dec. 10th, 10am:
Passed 100 distinguished points already!

Dec. 9th, 5:30pm:
Had put the email address as ecdl@[128.93.11.35], changed to ecdl@pauillac.inria.fr to placate fussy sendmails.

Dec. 9th, 5pm:
Changed fclose() to pclose(). Doh!

Dec. 9th, 1pm:
Updated the program to use "distinguished points" as suggested to me by Michael Wiener. The new version is faster and much simpler to use. Anyone running the old version with 'wget' should upgrade A.S.A.P.!

Dec. 8th, 4pm:
Start.


Alpha Linuxers everywhere!

Roar! We're a fairly small community but we've got some awesome machines and are capable of solving big problems if a large enough percentage of us are mobilised.

The first Certicom challenge, ECCp-79, is finished. The solution was found by Wayne Baisley and yours truly, using nothing but Alphas. See our ECCp-79 submission and Certicom's response.

The second one, ECC2-79, it just finished too using Alphas running Linux. See our ECC2-79 submission and Certicom's response.

We had about 30 machines; this counter counted the distinguished points every 10 minutes... Contributors included:

Andries Brouwer ....... Andries.Brouwer@cwi.nl
Christopher Brown ..... cbrown@alaska.net
Zach Brown ............ zab@zabbo.net
Jay Estabrook ......... Jay.Estabrook@digital.com
Rick Gorton ........... gorton@amt.tay1.dec.com
Oleg Gusev ............ oleg@usm.uni-muenchen.de
Robert Harley ......... Robert.Harley@inria.fr
Richard Holmes ........ holmes@lanl.gov
Andy Isaacson ......... adi@acm.org
Greg Lindahl .......... lindahl@cs.virginia.edu
Jon Nathan ............ jon@blading.com
Dennis Opacki ......... dopacki@mac-guru.com
Vance Petree .......... vwp@vancpower.com
Tim Rowley ............ tor@cs.brown.edu
Michael Sandfort ...... sandfort@post.cis.smu.edu
Jason Shiffer ......... jshiffer@home.com
Aaron Spink ........... spink@pa.dec.com
B.T. Labs Team ........ jcs@zoo.bt.co.uk
Bart-Jan Vrielink ..... bjv@de-boulevard.nl
Marinos Yannikos ...... nino@complang.tuwien.ac.at
Xiaoguang Zhang ....... xgz@mn.ms.ornl.gov

and anonymous others...

Apart from Rob (who obviously had a head-start :) the first to join were Oleg and Dennis. The top contributors were Rob, Xiaoguang, Vance and British Telecom Labs.

If you, yes you reading this right now, want to join too then you had better wait until we start ECCp-89!

Thanks!
-- Rob.

PS: Constructive comments on the code are very welcome.


How to contribute:

* Get your hands on an Alpha running Linux.

* mkdir /tmp/ecdl

* cd /tmp/ecdl

* Get ecdl.c.gz and f2Mul.s.gz from:
http://pauillac.inria.fr/~harley/ecdl1/
or:
ftp://ftp.mac-guru.com/pub/ecdl/

In case of difficulty getting them, I can send them by email.

* Unzip 'em:
gunzip ecdl.c.gz
gunzip f2Mul.s.gz

* Compile:
gcc -O4 ecdl.c f2Mul.s -o ecdl
or:
gcc -O4 ecdl.c f2Mul.s -DBATCH -o ecdl
If your machine is permanently connected to the Net, choose the default mode, otherwise the batch mode.

* Run:
nice +10 ./ecdl > log &

That's it!

* If you chose batch mode, email the log file to ecdl@nospam.pauillac.inria.fr once per day or so.


Extra notes:

* If you want your name on the list of contributors, send me email to that effect with your name and the name of your machine. My email address is:

Robert.Harley@nospam.inria.fr

* The code uses CPU time but almost no other resources, so if you run it 'nice' you'll hardly notice it except when it shows up in 'ps'.

* If you run into any problems, please let me know so we can fix them. It's quite possible that I've done something stupid and if you don't tell me I'll never find out!

* No work is lost if you stop the process and restart it, except of course for the reduced CPU time. So if you want to run it only at night and weekends for instance, that will work fine.

* If the default (non-batch) mode fails to open a pipe to sendmail, it outputs "Warning: couldn't pipe to sendmail, send by hand!" to the log file. If closing the pipe returns status other than EX_OK, it outputs "Warning: sendmail returned status xxx". If these happen a lot, you should switch to batch mode.

* Due to anti-spam meaures, the mail server at this end will refuse mail unless the one at your end has ptr and mx records known to DNS. No I don't know what that means either.

* If you compile the default mode on Digital Unix with 'cc -non_shared' or 'gcc -static' and run on Linux, you are likely to get:
Warning: sendmail returned status 32512

This is because D.U. is looking for /sbin/sh whereas Linux has /bin/sh.
Solutions:
1) For sane people:
compile on Linux.
2) For speed-demons who *need* the extra 10%:
use batch mode.
2) For lazy speed-demons with root access:
make a link from /sbin/sh to /bin/sh on the Linux machine.
3) For way-cool h4CK3R5:
open a buffer onto the ecdl binary with emacs
search for /sbin/sh
replace it with //bin/sh (yes, spelled exactly that way)
save it
run it.


Difference between default and batch modes

Both the default and batch modes output a line to stdout (i.e., the log file) every few hours. The default mode also does popen("/usr/sbin/sendmail ...") to report the line back to base.

For the batch mode you have to do a bit of work, transferring the lines manually. That could be by dialling in, or by carrying a floppy disc over to a Net-connected machine or whatever.

Email the log file (or just the new lines that have been appended since the previous time you sent some in) to ecdl@pauillac.inria.fr roughly daily, for instance by:
egrep ECC log | mail ecdl@pauillac.inria.fr

It can't hurt to do this even in default mode, or to send things twice. In doubt, err on the safe side!

Finally the machine name(s) you send for the list of contributors should correspond to the one(s) that results are posted from so that I can match you up with your results!

Merci beaucoup,
Rob.