[curves] Curve448 implementation questions

[Nicholas Wilson]

Hi Mike and Watson,

Thank you very much for your feedback, and clarification of the point
validation.

On 13 November 2015 at 19:49, Michael Hamburg <mike at shiftleft.org> wrote:
> Right.  If you already have an engine that does all the NIST primes in a
> modular way (eg in hardware), then you can use the NIST approach, but
> otherwise reduced radix is the way to go.

> This is the expected reduction formula.  However, I believe it’s easier to
> implement Ed448 using reduced radix, where you store 8, 56-bit limbs as 8,
> 64-bit words with some headroom, and only do the exact reduction at the very
> end.  Maybe this isn’t true in your case because you already have a bignum
> engine, but it might be worth taking a look.

> The simpler multiplication algorithm in x448.c is not especially easy to
> turn into a dedicated squaring algorithm.  But if you want the performance
> increase of a dedicated squarer, then you probably want Karatsuba too.

That's useful to know, but since we have a bignum library already, I
think it's simpler to use as many general-purpose functions as
possible, rather than using specific functions. To be honest, mbedTLS
doesn't use dedicated addition or multiplication formulas for new
curves, or a special-purpose limb representation. The performance is
reasonable (good enough to use), and lets the library support a wide
variety of curves without devoting much effort to each one.

I'm sure mbedTLS will be one of the first crypto libraries to support
Curve448 key exchange in TLS, as soon as the RFC is published with the
final NamedCurve values.

All the best,
Nicholas