ecc: ec_addm/ec_subm improvement

[NIIBE Yutaka]

On 12/12/2015 10:27 PM, Werner Koch wrote:
> In ec.c we do not use any MPI internals.  I would suggest to move the
> bulk of the code out to a new mpi_add_someothername function.

Yes, I think I share this view.

In the scope of mine, the major targets are improvement of Ed25519 and
possibly introducing Goldilocks.  Although my current changes are not
directly related to them, I'm learning how current implementation
doesn't depend on MPI internals.

Modern ECC design puts enough effort for choosing a finite field.
While MPI gives us the infrastructure for any finite fields, for a
specific finite field (for a modern ECC curve), it would be better to
provide a set of specific dedicated routines.

I think that there are three things (at least).


(1) redundant representation

For a implementation, it's better to relax the condition for
representation (in some cases), and it will have no bad effect.  It's
OK not to represent a number in finite field by an exact single
representation, but to allow multiple representations.

In the example of ec_addm/ec_subm change, number 1 can be represented
by "1" and "p+1".

When we do the changes for this, I'm considering to introduce
fixed-sized-limb computation, so that it will be constant-time.


(2) reduce function (like ec_mod)

Even before modern ECC design, a finite field had been chosen so that
reduction could be done fast.  It would be better to provide each
reduce function for a specific finite field, for better performance.


(3) reduced-radix or full-radix representation

By reduced-radix approach (using more bits to represent a finite field
number), addition and subtraction can be done with no-carry and
multiplication can be simplified; This would be good for some popular
processors.  But it's not always better.  Full-radix approach is
better for some embedded processors, for example.

I'm not sure if it's good for libgcrypt to allow different
internal representations for different processors.

Reduced-radix representation can be considered a variant of redundant
representation, going further.
--