Got stuck with Ed25519

[Werner Koch]

Hi,

I am trying to implement the ED25519 signature scheme (as a step to
Curve25519 world domination ;-).  The plan is to have a generic
implementation for Twisted Edwards curves and then later optimize it.
Thus the PD code by DJB et al. is not yet usable.  However, I get stuck
with the implementation and would appreciate some help.

I have attached a patch against current master (90fdf25) which implements
the math.  However, something is badly wrong.  Output of the test
program is:

  $ ./t-mpi-point --verbose
  t-mpi-point: checking point setting functions
  t-mpi-point: checking context functions
  t-mpi-point: checking standard curves
  t-mpi-point: checking sample public key
  t-mpi-point: checking basic math functions for EC
  t-mpi-point: checking basic math functions for EC (variant)
  t-mpi-point: checking basic Twisted Edwards math
  t-mpi-point: twistededwards_math: failed assertion: nG == (0,1)
  nG.x: 229171B146DF6E0B7BF69DBB70641CE5893DE9E7D1B5A16F4B9C5B86AD3BBBE4
  nG.y: 40D64B6B3C2B4AA965E6ECC890722DE29C1A03B37255822E18515A214AAB6FBB
  nG.z: 33046B465045AC705194688838033890488E7AD521DCEB534D9D171C4D329D08
    .x: 2746918A09C779B2258698FD5F07F82890CB8209A09660CA31FE9D5E86F74AA7
    .y: 2E29127DF0E0833A0D60EA1E75C5E233217858D573F17348D5319A7F57BD1BA3
  
The expected output is .x=0,.y=1.  I really don't understand what's
going on wrong here.  If I would use 
  
  if (x)
    gcry_mpi_div (x, NULL, point->x, point->z, -1);
  if (y)
    gcry_mpi_div (y, NULL, point->y, point->z, -1);

in mpi/ec.c:_gcry_mpi_ec_get_affine this works but that is of course
wrong, because modular arithmetic is needed.  It works only in this
special case.  The addition on Twisted Edwards curve does not need any
special treatment for the neutral element, thus in theory the code
should be correct.

If someone could point me to another generic implementation for Edwards
curves this might also be helpful.


Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: edwards.diff
Type: text/x-diff
Size: 18597 bytes
Desc: not available
URL: </pipermail/attachments/20130910/e13a4ad1/attachment-0001.diff>