Added previous code that was fixed for y^2 = x^3 - 3x + b, because all secg curves have a fixed to -3.

Simplified file naming scheme.

14 files changed, 213 insertions, 77 deletions

diff --git a/lib/nettle/Makefile.am b/lib/nettle/Makefile.am
index 0516800762..a4bd44cfc0 100644
--- a/lib/nettle/Makefile.am
+++ b/lib/nettle/Makefile.am
@@ -36,7 +36,7 @@ noinst_LTLIBRARIES = libcrypto.la
 
 libcrypto_la_SOURCES = pk.c mpi.c mac.c cipher.c rnd.c init.c egd.c egd.h \
 	multi.c ecc_free.c ecc.h ecc_make_key.c ecc_shared_secret.c \
-	ecc_test.c ltc_ecc_map.c \
-	ltc_ecc_mulmod.c ltc_ecc_points.c \
-	ltc_ecc_projective_add_point.c ltc_ecc_projective_dbl_point.c \
+	ecc_test.c ecc_map.c \
+	ecc_mulmod.c ecc_points.c ecc_projective_dbl_point_3.c \
+	ecc_projective_add_point.c ecc_projective_dbl_point.c \
 	mp_unsigned_bin.c ecc_sign_hash.c ecc_verify_hash.c 
diff --git a/lib/nettle/ecc.h b/lib/nettle/ecc.h
index 9024294402..56fafc872d 100644
--- a/lib/nettle/ecc.h
+++ b/lib/nettle/ecc.h
@@ -6,8 +6,12 @@
 #include <string.h>
 #include <assert.h>
 
-#define LTC_MECC
-#define ECC256
+/* assume y^2 = x^3 - 3x + b
+ * instead of the generic y^2 = x^3 + ax + b
+ *
+ * (XXX: the generic case has not been tested)
+ */
+#define ECC_SECP_CURVES_ONLY
 
 #define PK_PRIVATE 1
 #define PK_PUBLIC 2
diff --git a/lib/nettle/ecc_free.c b/lib/nettle/ecc_free.c
index a4bf451c4c..bbf087dfd5 100644
--- a/lib/nettle/ecc_free.c
+++ b/lib/nettle/ecc_free.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -21,8 +21,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#ifdef LTC_MECC
-
 /**
   Free an ECC key from memory
   @param key   The key you wish to free
@@ -35,7 +33,6 @@ ecc_free (ecc_key * key)
                   &key->prime, &key->order, &key->Gx, &key->Gy, NULL);
 }
 
-#endif
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_free.c,v $ */
 /* $Revision: 1.6 $ */
 /* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ecc_make_key.c b/lib/nettle/ecc_make_key.c
index f1e5cde719..aab6fedb6d 100644
--- a/lib/nettle/ecc_make_key.c
+++ b/lib/nettle/ecc_make_key.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -21,8 +21,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#ifdef LTC_MECC
-
 /**
   Make a new ECC key 
   @param prng         An active PRNG state
@@ -146,7 +144,6 @@ cleanup:
   return err;
 }
 
-#endif
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_make_key.c,v $ */
 /* $Revision: 1.13 $ */
 /* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ltc_ecc_map.c b/lib/nettle/ecc_map.c
index dca353b617..bbe99ec790 100644
--- a/lib/nettle/ltc_ecc_map.c
+++ b/lib/nettle/ecc_map.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -21,8 +21,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#ifdef LTC_MECC
-
 /**
   Map a projective jacobian point back to affine space
   @param P        [in/out] The point to map
@@ -67,8 +65,6 @@ ltc_ecc_map (ecc_point * P, mpz_t modulus)
   return err;
 }
 
-#endif
-
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_map.c,v $ */
 /* $Revision: 1.7 $ */
 /* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ltc_ecc_mulmod.c b/lib/nettle/ecc_mulmod.c
index f8c02dca75..1236dc340b 100644
--- a/lib/nettle/ltc_ecc_mulmod.c
+++ b/lib/nettle/ecc_mulmod.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -21,8 +21,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#ifdef LTC_MECC
-
 /**
    Perform a point multiplication  (timing resistant)
    @param k    The scalar to multiply by
@@ -182,7 +180,6 @@ done:
   return err;
 }
 
-#endif
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mulmod_timing.c,v $ */
 /* $Revision: 1.13 $ */
 /* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ltc_ecc_points.c b/lib/nettle/ecc_points.c
index e4e2cd4c2d..fa9b5b5c92 100644
--- a/lib/nettle/ltc_ecc_points.c
+++ b/lib/nettle/ecc_points.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -21,8 +21,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#ifdef LTC_MECC
-
 /**
    Allocate a new ECC point
    @return A newly allocated point or NULL on error 
@@ -58,7 +56,6 @@ ltc_ecc_del_point (ecc_point * p)
     }
 }
 
-#endif
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_points.c,v $ */
 /* $Revision: 1.7 $ */
 /* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ltc_ecc_projective_add_point.c b/lib/nettle/ecc_projective_add_point.c
index 31bd679e59..dd98eb43d8 100644
--- a/lib/nettle/ltc_ecc_projective_add_point.c
+++ b/lib/nettle/ecc_projective_add_point.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -21,8 +21,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#if defined(LTC_MECC) && (!defined(LTC_MECC_ACCEL) || defined(LTM_LTC_DESC))
-
 /**
    Add two ECC points
    @param P        The point to add
@@ -204,8 +202,6 @@ ltc_ecc_projective_add_point (ecc_point * P, ecc_point * Q, ecc_point * R,
   return err;
 }
 
-#endif
-
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_projective_add_point.c,v $ */
 /* $Revision: 1.16 $ */
 /* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ltc_ecc_projective_dbl_point.c b/lib/nettle/ecc_projective_dbl_point.c
index 618f0d94eb..6d446c28a8 100644
--- a/lib/nettle/ltc_ecc_projective_dbl_point.c
+++ b/lib/nettle/ecc_projective_dbl_point.c
@@ -1,27 +1,32 @@
-/* LibTomCrypt, modular cryptographic library -- Tom St Denis
+/*
+ * Copyright (C) 2011 Free Software Foundation, Inc.
  *
- * LibTomCrypt is a library that provides various cryptographic
- * algorithms in a highly modular and flexible manner.
+ * Author: Nikos Mavrogiannopoulos
  *
- * The library is free for all purposes without any express
- * guarantee it works.
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+ * USA
  *
- * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
- *
- * All curves taken from NIST recommendation paper of July 1999
- * Available at http://csrc.nist.gov/cryptval/dss.htm
+/* Implements ECC point doubling over Z/pZ for curve y^2 = x^3 + ax + b
  */
 #include "ecc.h"
 
-/**
-  @file ltc_ecc_projective_dbl_point.c
-  ECC Crypto, Tom St Denis
-*/
-
-#if defined(LTC_MECC) && (!defined(LTC_MECC_ACCEL) || defined(LTM_LTC_DESC))
+#ifndef ECC_SECP_CURVES_ONLY
 
 /**
    Double an ECC point
@@ -42,6 +47,30 @@ ltc_ecc_projective_dbl_point (ecc_point * P, ecc_point * R, mpz_t a,
   assert (R != NULL);
   assert (modulus != NULL);
 
+  /*
+    algorithm used:
+     if (Y == 0)
+       return POINT_AT_INFINITY
+     S = 4*X*Y^2
+     M = 3*X^2 + a*Z^4
+     X' = M^2 - 2*S
+     Y' = M*(S - X') - 8*Y^4
+     Z' = 2*Y*Z
+     return (X', Y', Z')
+   */
+
+  if (mpz_cmp_ui(P->y, 0) == 0)
+    {
+      /* point at infinity 
+       * under jacobian coordinates
+       */
+      mpz_set(R->x, 1);
+      mpz_set(R->y, 1);
+      mpz_set(R->z, 0);
+      
+      return 0;
+    }
+
   if ((err = mp_init_multi (&t1, &m, &s, NULL)) != 0)
     {
       return err;
@@ -54,16 +83,6 @@ ltc_ecc_projective_dbl_point (ecc_point * P, ecc_point * R, mpz_t a,
       mpz_set (R->z, P->z);
     }
 
-  /*
-     if (Y == 0)
-     return POINT_AT_INFINITY
-     S = 4*X*Y^2
-     M = 3*X^2 + a*Z^4
-     X' = M^2 - 2*S
-     Y' = M*(S - X') - 8*Y^4
-     Z' = 2*Y*Z
-     return (X', Y', Z')
-   */
 
   /* m = Z * Z */
   mpz_mul (m, R->z, R->z);
@@ -187,7 +206,5 @@ ltc_ecc_projective_dbl_point (ecc_point * P, ecc_point * R, mpz_t a,
   mp_clear_multi (&t1, &m, &s, NULL);
   return err;
 }
+
 #endif
-/* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_projective_dbl_point.c,v $ */
-/* $Revision: 1.11 $ */
-/* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ecc_projective_dbl_point_3.c b/lib/nettle/ecc_projective_dbl_point_3.c
new file mode 100644
index 0000000000..7c415fe058
--- /dev/null
+++ b/lib/nettle/ecc_projective_dbl_point_3.c
@@ -0,0 +1,148 @@
+/* LibTomCrypt, modular cryptographic library -- Tom St Denis
+ *
+ * LibTomCrypt is a library that provides various cryptographic
+ * algorithms in a highly modular and flexible manner.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
+ */
+
+/* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
+ *
+ * All curves taken from NIST recommendation paper of July 1999
+ * Available at http://csrc.nist.gov/cryptval/dss.htm
+ */
+#include "ecc.h"
+
+/**
+  @file ltc_ecc_projective_dbl_point.c
+  ECC Crypto, Tom St Denis
+*/  
+
+#ifdef ECC_SECP_CURVES_ONLY
+
+/**
+   Double an ECC point
+   @param P   The point to double
+   @param R   [out] The destination of the double
+   @param modulus  The modulus of the field the ECC curve is in
+   @param mp       The "b" value from montgomery_setup()
+   @return 0 on success
+*/
+int
+ltc_ecc_projective_dbl_point (ecc_point * P, ecc_point * R, mpz_t a /* a is -3 */,
+                              mpz_t modulus)
+{
+   mpz_t t1, t2;
+   int   err;
+
+   assert(P       != NULL);
+   assert(R       != NULL);
+   assert(modulus != NULL);
+
+   if ((err = mp_init_multi(&t1, &t2, NULL)) != 0) {
+      return err;
+   }
+
+   if (P != R) {
+      mpz_set(R->x, P->x);
+      mpz_set(R->y, P->y);
+      mpz_set(R->z, P->z);
+   }
+
+   /* t1 = Z * Z */
+   mpz_mul(t1, R->z, R->z);
+   mpz_mod(t1, t1, modulus);
+   /* Z = Y * Z */
+   mpz_mul(R->z, R->y, R->z);
+   mpz_mod(R->z, R->z, modulus);
+   /* Z = 2Z */
+   mpz_add(R->z, R->z, R->z);
+   if (mpz_cmp(R->z, modulus) >= 0) {
+      mpz_sub(R->z, R->z, modulus);
+   }
+   
+   /* T2 = X - T1 */
+   mpz_sub(t2, R->x, t1);
+   if (mpz_cmp_ui(t2, 0) < 0) {
+      mpz_add(t2, t2, modulus);
+   }
+   /* T1 = X + T1 */
+   mpz_add(t1, t1, R->x);
+   if (mpz_cmp(t1, modulus) >= 0) {
+      mpz_sub(t1, t1, modulus);
+   }
+   /* T2 = T1 * T2 */
+   mpz_mul(t2, t1, t2);
+   mpz_mod(t2, t2, modulus);
+   /* T1 = 2T2 */
+   mpz_add(t1, t2, t2);
+   if (mpz_cmp(t1, modulus) >= 0) {
+      mpz_sub(t1, t1, modulus);
+   }
+   /* T1 = T1 + T2 */
+   mpz_add(t1, t1, t2);
+   if (mpz_cmp(t1, modulus) >= 0) {
+      mpz_sub(t1, t1, modulus);
+   }
+
+   /* Y = 2Y */
+   mpz_add(R->y, R->y, R->y);
+   if (mpz_cmp(R->y, modulus) >= 0) {
+      mpz_sub(R->y, R->y, modulus);
+   }
+   /* Y = Y * Y */
+   mpz_mul(R->y, R->y, R->y);
+   mpz_mod(R->y, R->y, modulus);
+   /* T2 = Y * Y */
+   mpz_mul(t2, R->y, R->y);
+   mpz_mod(t2, t2, modulus);
+   /* T2 = T2/2 */
+   if (mp_isodd(t2)) {
+      mpz_add(t2, t2, modulus);
+   }
+   mpz_divexact_ui(t2, t2, 2);
+   /* Y = Y * X */
+   mpz_mul(R->y, R->y, R->x);
+   mpz_mod(R->y, R->y, modulus);
+
+   /* X  = T1 * T1 */
+   mpz_mul(R->x, t1, t1);
+   mpz_mod(R->x, R->x, modulus);
+   /* X = X - Y */
+   mpz_sub(R->x, R->x, R->y);
+   if (mpz_cmp_ui(R->x, 0) < 0) {
+      mpz_add(R->x, R->x, modulus);
+   }
+   /* X = X - Y */
+   mpz_sub(R->x, R->x, R->y);
+   if (mpz_cmp_ui(R->x, 0) < 0) {
+      mpz_add(R->x, R->x, modulus);
+   }
+
+   /* Y = Y - X */     
+   mpz_sub(R->y, R->y, R->x);
+   if (mpz_cmp_ui(R->y, 0) < 0) {
+      mpz_add(R->y, R->y, modulus);
+   }
+   /* Y = Y * T1 */
+   mpz_mul(R->y, R->y, t1);
+   mpz_mod(R->y, R->y, modulus);
+   /* Y = Y - T2 */
+   mpz_sub(R->y, R->y, t2);
+   if (mpz_cmp_ui(R->y, 0) < 0) {
+      mpz_add( R->y, R->y, modulus);
+   }
+ 
+   err = 0;
+
+   mp_clear_multi(&t1, &t2, NULL);
+   return err;
+}
+#endif
+/* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_projective_dbl_point.c,v $ */
+/* $Revision: 1.11 $ */
+/* $Date: 2007/05/12 14:32:35 $ */
+
diff --git a/lib/nettle/ecc_shared_secret.c b/lib/nettle/ecc_shared_secret.c
index a7f5761fa9..61012fd683 100644
--- a/lib/nettle/ecc_shared_secret.c
+++ b/lib/nettle/ecc_shared_secret.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -22,8 +22,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#ifdef LTC_MECC
-
 /**
   Create an ECC shared secret between two keys
   @param private_key      The private ECC key
@@ -88,7 +86,6 @@ done:
   return err;
 }
 
-#endif
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_shared_secret.c,v $ */
 /* $Revision: 1.10 $ */
 /* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ecc_sign_hash.c b/lib/nettle/ecc_sign_hash.c
index 09774cb534..158949ffda 100644
--- a/lib/nettle/ecc_sign_hash.c
+++ b/lib/nettle/ecc_sign_hash.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -22,8 +22,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#ifdef LTC_MECC
-
 /**
   Sign a message digest
   @param in        The message digest to sign
@@ -111,7 +109,6 @@ errnokey:
   return err;
 }
 
-#endif
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_sign_hash.c,v $ */
 /* $Revision: 1.11 $ */
 /* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ecc_test.c b/lib/nettle/ecc_test.c
index 7e854ec9b2..0bdcd35d8f 100644
--- a/lib/nettle/ecc_test.c
+++ b/lib/nettle/ecc_test.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -24,8 +24,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#ifdef LTC_MECC
-
 /**
   Perform on the ECC system
   @return 0 if successful
@@ -139,8 +137,6 @@ done:
   return err;
 }
 
-#endif
-
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_test.c,v $ */
 /* $Revision: 1.12 $ */
 /* $Date: 2007/05/12 14:32:35 $ */
diff --git a/lib/nettle/ecc_verify_hash.c b/lib/nettle/ecc_verify_hash.c
index 7f62d64ca3..b9f6ec0999 100644
--- a/lib/nettle/ecc_verify_hash.c
+++ b/lib/nettle/ecc_verify_hash.c
@@ -9,7 +9,7 @@
  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  */
 
-/* Implements ECC over Z/pZ for curve y^2 = x^3 - ax + b
+/* Implements ECC over Z/pZ for curve y^2 = x^3 + ax + b
  *
  * All curves taken from NIST recommendation paper of July 1999
  * Available at http://csrc.nist.gov/cryptval/dss.htm
@@ -21,8 +21,6 @@
   ECC Crypto, Tom St Denis
 */
 
-#ifdef LTC_MECC
-
 /* verify 
  *
  * w  = s^-1 mod n
@@ -151,7 +149,6 @@ error:
   return err;
 }
 
-#endif
 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_verify_hash.c,v $ */
 /* $Revision: 1.14 $ */
 /* $Date: 2007/05/12 14:32:35 $ */