[PATCH] ecc: Improve Montgomery curve implementation

[NIIBE Yutaka]

Pushed.

On 11/19/2014 11:46 PM, Werner Koch wrote:
> However, I doubt that the condition
> 
>    if (sk->E.dialect == ECC_DIALECT_ED25519)
> 
> will ever be asserted.

Err... let me explain.  It would be abuse to put another meaning
on ECC_DIALECT_ED25519, but I wanted to say something like:

	"If it's computation for DJB's curve,..."

It corresponds to the condition in the function nist_generate_key.

I thought that (ab)using ECC_DIALECT_ED25519, the Montgomery curve
could be defined as:

diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index fd47c1d..5d855bd 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -40,7 +40,7 @@ static const struct
   const char *other; /* Other name. */
 } curve_aliases[] =
   {
-  /*{ "Curve25519", "1.3.6.1.4.1.3029.1.5.1" },*/
+    { "Curve25519", "1.3.6.1.4.1.3029.1.5.1" },
     { "Ed25519",    "1.3.6.1.4.1.11591.15.1" },

     { "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID  */
@@ -129,6 +129,18 @@ static const ecc_domain_parms_t domain_parms[] =
       "0x6666666666666666666666666666666666666666666666666666666666666658",
       "0x08"
     },
+    {
+      /* (y^2 = x^3 + 486662*x^2 + x) */
+      "Curve25519", 256, 0,
+      MPI_EC_MONTGOMERY, ECC_DIALECT_ED25519,
+      "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
+      "0x01DB41",
+      "0x01",
+      "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED",
+      "0x0000000000000000000000000000000000000000000000000000000000000009",
+      "0x20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9",
+      "0x08"
+    },
 #if 0 /* No real specs yet found.  */
     {
       /* x^2 + y^2 = 1 + 3617x^2y^2 mod 2^414 - 17 */
=================================

When the cofactor h != 1, we computes hkdG for shared point, according
to 'cofactor Elliptic Curve Diffie-Hellman' defined in SP800-56A.

On the other hand, for the computation of Curve25519, we make sure the
value of k (in the variable test in test_ecdh_only_keys) is multiple
of 8 (== cofactor), in advance.

Should we have another ECC_DIALECT_??? ?

Well, for completeness, we should implement 'cofactor Elliptic Curve
Diffie-Hellman' in ecc_encrypt_raw/ecc_decrypt_raw to handle cofactor
correctly, but this is another story.  Currently, since the curve with
h != 1 is only Curve25519, there is no problem.
--