[prev in list] [next in list] [prev in thread] [next in thread] 

List:       nettle-bugs
Subject:    Re: [PATCH 0/8] Implement Curve448 ECDH and Ed448
From:       nisse () lysator ! liu ! se (Niels =?utf-8?Q?M=C3=B6ller?=)
Date:       2017-09-09 20:21:32
Message-ID: nn1snfpqr7.fsf () armitage ! lysator ! liu ! se
[Download RAW message or body]

Daiki Ueno <ueno@gnu.org> writes:

> This patch series implements the Curve448 Diffie-Hellman protocol (RFC
> 7748) and the Ed448 signature scheme (RFC 8032).  Although I tried to
> make it as close as possible to the Curve25519 and Ed25519
> implementations, I had to add a few special cases, namely:

Thanks a lot for this work. I've started by applying the first 4 easy
patches (currently on the master-updates branch).

> - for Curve448, eccdata directly calculates points on the Edwards
>   curve instead of the equivalent Montgomery curve

It would be nice to do it the same way. Are Montgomery computations the
same, regardless of twist/no-twist?

> - untwisted versions of ecc_add_eh* and ecc_dup_eh are added

Just a note that the twisted versions should at some point be updated to
use more effficient formulas.

> - the point decoding for Ed448 uses a different formula to recover u and v

Does it have to be done differently? I'll have to read up to find out.
Efficient sqrt is going to be tailored for this prime to be most
efficient.

> Also, optimized implementation of modular reduction is currently
> missing, which is beyond my expertise.  I would appreciate any
> suggestions regarding that.

If we do Euclidean reduction, we should use the property that

  2^448 = 2^224 + 1 (mod)

And we'd need to use this twice to reduce a 896-bit product to 448 bits.
On 64-bit machines, we'll get some shifting since 224 isn't a multiple
of 64.

Redc might be slightly more efficient than the above reduction. Due to
the structure, it might also work nicely to do a "half redc", reducing
from both ends, and they might share the shift. I'll have to think
through the details. But unlikely to be a big win over Euclidean.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.

[prev in list] [next in list] [prev in thread] [next in thread]