Integrated ECC internals.

1 files changed, 102 insertions, 0 deletions

diff --git a/ecc-mod.c b/ecc-mod.c
new file mode 100644
index 00000000..1d2f4232
--- /dev/null
+++ b/ecc-mod.c
@@ -0,0 +1,102 @@
+/* ecc-mod.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle 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.
+ * 
+ * The nettle 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 the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+/* Computes r mod m, where m is of size mn. bp holds B^mn mod m, as mn
+   limbs, but the upper mn - bn libms are zero. */
+void
+ecc_mod (mp_limb_t *rp, mp_size_t rn, mp_size_t mn,
+	 const mp_limb_t *bp, mp_size_t bn,
+	 const mp_limb_t *b_shifted, unsigned shift)
+{
+  mp_limb_t hi;
+  mp_size_t sn = mn - bn;
+  mp_size_t i;
+
+  assert (sn > 0);
+
+  /* FIXME: Could use mpn_addmul_2. */
+  /* Eliminate sn = mn - bn limbs at a time */
+  if (bp[bn-1] < ((mp_limb_t) 1 << (GMP_NUMB_BITS - 1)))
+    {
+      /* Multiply sn + 1 limbs at a time, so we get a mn+1 limb
+	 product. Then we can absorb the carry in the high limb */
+      while (rn > 2 * mn - bn)
+	{
+	  rn -= sn;
+
+	  for (i = 0; i <= sn; i++)
+	    rp[rn+i-1] = mpn_addmul_1 (rp + rn - mn - 1 + i, bp, bn, rp[rn+i-1]);
+	  rp[rn-1] = rp[rn+sn-1]
+	    + mpn_add_n (rp + rn - sn - 1, rp + rn - sn - 1, rp + rn - 1, sn);
+	}
+      goto final_limbs;
+    }
+  else
+    {
+      while (rn >= 2 * mn - bn)
+	{
+	  rn -= sn;
+
+	  for (i = 0; i < sn; i++)
+	    rp[rn+i] = mpn_addmul_1 (rp + rn - mn + i, bp, bn, rp[rn+i]);
+				     
+	  hi = mpn_add_n (rp + rn - sn, rp + rn - sn, rp + rn, sn);
+	  hi = cnd_add_n (hi, rp + rn - mn, bp, mn);
+	  assert (hi == 0);
+	}
+    }
+
+  if (rn > mn)
+    {
+    final_limbs:
+      sn = rn - mn;
+      
+      for (i = 0; i < sn; i++)
+	rp[mn+i] = mpn_addmul_1 (rp + i, bp, bn, rp[mn+i]);
+
+      hi = mpn_add_n (rp + bn, rp + bn, rp + mn, sn);
+      hi = sec_add_1 (rp + bn + sn, rp + bn + sn, mn - bn - sn, hi);
+    }
+
+  if (shift > 0)
+    {
+      /* Combine hi with top bits, add in */
+      hi = (hi << shift) | (rp[mn-1] >> (GMP_NUMB_BITS - shift));
+      rp[mn-1] = (rp[mn-1] & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
+	+ mpn_addmul_1 (rp, b_shifted, mn-1, hi);
+    }
+  else
+    {
+      hi = cnd_add_n (hi, rp, bp, mn);
+      assert (hi == 0);
+    }
+}