[curves] pure-python Ed25519 library for review

[Brian Warner]

On 4/7/15 3:32 PM, Ron Garret wrote:
> Is there a reason you don’t just use DJB’s reference implementation?
> 
> http://ed25519.cr.yp.to/python/ed25519.py

Yeah, it was painfully slow. This code started from that base, and was
then modified (by you or dholth, I think) to use extended coordinates.
Then I went through and picked off the low-hanging fruit (use python's
native 3-argument pow(), use hexlify/int(s,16) instead of manual
bits-to-int/int-to-bits) to speed it up further.

I just added a copy of that original to my repo (in misc/) for
comparison. The original cr.yp.to version gets:

% PYTHONPATH=misc python misc/speed_orig_ed25519.py
speed_orig
    generate: 860.69ms
        sign: 1.742s
      verify: 2.584s

and the subsequent changes brought that down ~500x to:

% PYTHONPATH=. python pure25519/speed_ed25519.py
speed_ed25519
    generate: 2.84ms
        sign: 2.80ms
      verify: 10.79ms

Two and a half seconds to verify a signature (on a fairly fast machine)
was hard to stomach. 11ms is way easier.

cheers,
 -Brian