minicrypt: add lots of MPI stuff

IanHarvey · May 14, 2014 · 17266cf · 17266cf
1 parent eeecb84
commit 17266cf
Show file tree

Hide file tree

Showing 18 changed files with 3,741 additions and 0 deletions.
diff --git a/host/Makefile b/host/Makefile
@@ -30,6 +30,32 @@ aesccm_mini_test: aesccm_mini.c aes_mini.o
 	$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
 TARGETS += aesccm_mini_test
 
+mpiadd_mini_test: mpiadd_mini.c
+	$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
+TARGETS += mpiadd_mini_test
+
+mpisub_mini_test: mpisub_mini.c
+	$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
+TARGETS += mpisub_mini_test
+
+mpimul_mini_test: mpimul_mini.c
+	$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
+TARGETS += mpimul_mini_test
+
+MPI_OBJS= mpiadd_mini.o mpisub_mini.o mpimul_mini.o mpiutil_mini.o f25519util_mini.o
+
+f25519add_mini_test: f25519add_mini.c $(MPI_OBJS)
+	$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
+TARGETS += f25519add_mini_test
+
+f25519sub_mini_test: f25519sub_mini.c $(MPI_OBJS)
+	$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
+TARGETS += f25519sub_mini_test
+
+f25519mul_mini_test: f25519mul_mini.c $(MPI_OBJS)
+	$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
+TARGETS += f25519mul_mini_test
+
 # -------------------------------------
 
 all: $(TARGETS)
@@ -47,3 +73,10 @@ test: $(TARGETS)
 	./aes_mini_enc_test
 	./aes_mini_enc128_test
 	./aesccm_mini_test
+	./mpimul_mini_test
+	./mpiadd_mini_test
+	./mpisub_mini_test
+	./f25519add_mini_test
+	./f25519sub_mini_test
+	./f25519mul_mini_test
+
diff --git a/python-models/mult.py b/python-models/mult.py
@@ -0,0 +1,43 @@
+
+
+NDIGITS = 8
+MASK = 0xFFFFFFFF
+
+def mul256_rs( wordX, wordY ):
+    res = [0] * (NDIGITS * 2)
+    r64 = 0
+    for r in range(0, NDIGITS*2-1):
+        sX = r if (r < NDIGITS) else NDIGITS-1
+        sY = 0 if (r < NDIGITS) else (r-NDIGITS+1)
+        print "Result Pos", r
+        while sX >= 0 and sY < NDIGITS:
+            print (sX,sY), '->', (sX + sY)
+            r64 += wordX[sX] * wordY[sY]
+            sX -= 1
+            sY += 1
+        res[r] = r64 & MASK
+        r64 = (r64 >> 32)
+    res[NDIGITS*2-1] = r64
+    assert(r64 <= MASK)
+    return res 
+
+def mul(x,y):
+    wX = [ (x >> i) & 0xFFFFFFFF for i in range(0, NDIGITS*32, 32) ]
+    wY = [ (y >> i) & 0xFFFFFFFF for i in range(0, NDIGITS*32, 32) ]
+    wR = mul256_rs(wX, wY)
+
+    return sum([ (wR[i] << (i*32)) for i in range(0, NDIGITS*2) ])
+
+tstlist = [ 0, 1, 0x80000000, 0xFFFFFFFF, (1 << 64)-1, (1 << 64),
+		(1<<128)-1, (1<<256)-1 ]
+
+if __name__ == '__main__':
+    for x in tstlist:
+    	for y in tstlist:
+    	    res = mul(x,y)
+    	    print "x=", hex(x)
+    	    print "y=", hex(y)
+    	    print "x*y=", hex(x*y)
+    	    print "res=", hex(res)
+    	    assert(res == x*y)
+
diff --git a/src/f25519add_mini.c b/src/f25519add_mini.c
@@ -0,0 +1,84 @@
+/*
+ *
+ * F25519 field add from Minicrypt library
+ *
+ * This program is placed into the public domain
+ * by its author, Ian Harvey.
+ * Note there is NO WARRANTY of any kind.
+ */
+
+#define MPIMINI_INTERNAL_API
+#include "mpi_mini.h"
+
+void F25519_add3_mini(F25519_Mini *res, const F25519_Mini *s1, const F25519_Mini *s2)
+{
+    mpiadd_mini(res, s1, s2);
+    F25519_reduce_mini_(res);
+}
+
+/* Test harness ======================================================= */
+#ifdef TEST_HARNESS
+
+#include <stdio.h>
+#include <string.h>
+
+typedef struct
+{
+  F25519_Mini a;
+  F25519_Mini b;
+  F25519_Mini res;
+}
+  F25519Add_TV;
+
+static const F25519Add_TV add_tvs[] =
+{
+#include "testvectors/f25519add.inc"
+};
+
+static const int add_tvs_count = sizeof(add_tvs) / sizeof(F25519Add_TV);
+
+int main(void)
+{
+  int i, errs;
+
+  errs = 0;
+  for (i=0; i < add_tvs_count; i++)
+  {
+    const F25519Add_TV *tv = &add_tvs[i];
+    F25519_Mini res;
+
+    F25519_add3_mini(&res, &tv->a, &tv->b);
+    if ( !F25519_equal_mini(&res, &tv->res) )
+    {
+      printf("Test #%d failed (1)\n", i);
+      errs ++;
+      continue;
+    }
+
+    F25519_copy_mini(&res, &tv->a);
+    F25519_add3_mini(&res, &res, &tv->b);
+
+    if ( !F25519_equal_mini(&res, &tv->res) )
+    {
+      printf("Test #%d failed (2)\n", i);
+      errs ++;
+      continue;
+    }
+
+    F25519_copy_mini(&res, &tv->b);
+    F25519_add3_mini(&res, &tv->a, &res);
+
+    if ( !F25519_equal_mini(&res, &tv->res) )
+    {
+      printf("Test #%d failed (3)\n", i);
+      errs ++;
+      continue;
+    }
+
+  }
+
+  printf("%d errors out of %d\n", errs, add_tvs_count);
+  return (errs==0) ? 0 : 1;
+}
+
+#endif /* TEST_HARNESS */
diff --git a/src/f25519mul_mini.c b/src/f25519mul_mini.c
@@ -0,0 +1,128 @@
+/*
+ *
+ * F25519 field add from Minicrypt library
+ *
+ * This program is placed into the public domain
+ * by its author, Ian Harvey.
+ * Note there is NO WARRANTY of any kind.
+ */
+
+#define MPIMINI_INTERNAL_API
+#include "mpi_mini.h"
+
+
+static void mul_reduce_approx(uint32_t *dst, uint32_t *src)
+// dst is 8 words long
+// src is 16 words long
+// Forms dst = (src % (2^255-19) + {0..1} * (2^255-19)
+{
+   int i;
+
+   // We're aiming for dst = src - N*(2^255-19), s.t. dst < 2^255-19
+   // Each iteration of the loop forms an approximation N~ = src / (2^255)
+
+   for (i=0; i<2; i++)
+   {
+      int j;
+
+      // Do dst <- (src >> 255), which will be our N~
+      for (j=0; j < 8; j++)
+         dst[j] = (src[j+7] >> 31) | (src[j+8] << 1);
+
+      // Do src' -= (N~ * 2^255), i.e. clear all bits > 255
+
+      src[7] &= 0x7FFFFFFF;
+      for (j=8; j < 16; j++)
+        src[j] = 0;
+
+      // Adjust: src'' += (N~ * 19), so src'' == src - (N~ * (2^255-19))
+      mpi_mulrow_mini_ (src, 19, dst);
+      // We can ignore the carry - mulrow will correctly set src[0..8]
+      // and we know the true value of src won't be > 20 * (2^255)
+
+      // Now src = (src - N~ * (2^255-19))
+      // First time round, max value is ~ 19 * (2^255-19)
+   }
+
+   for (i=0; i<8; i++)
+     dst[i] = src[i];
+}
+
+#if MPIMINI_DIGITS != 8
+#error "F25519_mul3_mini assumes MPIMINI_DIGITS==8"
+#endif
+
+void F25519_mul3_mini(F25519_Mini *res, const F25519_Mini *s1, const F25519_Mini *s2)
+{
+    ULong_Mini mr;
+    mpimul_mini(&mr, s1, s2);
+    mul_reduce_approx(res->digits, mr.digits);
+    F25519_reduce_mini_(res);
+}
+
+/* Test harness ======================================================= */
+#ifdef TEST_HARNESS
+
+#include <stdio.h>
+#include <string.h>
+
+typedef struct
+{
+  F25519_Mini a;
+  F25519_Mini b;
+  F25519_Mini res;
+}
+  F25519Mul_TV;
+
+static const F25519Mul_TV mul_tvs[] =
+{
+#include "testvectors/f25519mul.inc"
+};
+
+static const int mul_tvs_count = sizeof(mul_tvs) / sizeof(F25519Mul_TV);
+
+int main(void)
+{
+  int i, errs;
+
+  errs = 0;
+  for (i=0; i < mul_tvs_count; i++)
+  {
+    const F25519Mul_TV *tv = &mul_tvs[i];
+    F25519_Mini res;
+
+    F25519_mul3_mini(&res, &tv->a, &tv->b);
+    if ( !F25519_equal_mini(&res, &tv->res) )
+    {
+      printf("Test #%d failed (1)\n", i);
+      errs ++;
+      continue;
+    }
+
+    F25519_copy_mini(&res, &tv->a);
+    F25519_mul3_mini(&res, &res, &tv->b);
+
+    if ( !F25519_equal_mini(&res, &tv->res) )
+    {
+      printf("Test #%d failed (2)\n", i);
+      errs ++;
+      continue;
+    }
+
+    F25519_copy_mini(&res, &tv->b);
+    F25519_mul3_mini(&res, &tv->a, &res);
+
+    if ( !F25519_equal_mini(&res, &tv->res) )
+    {
+      printf("Test #%d failed (3)\n", i);
+      errs ++;
+      continue;
+    }
+
+  }
+
+  printf("%d errors out of %d\n", errs, mul_tvs_count);
+  return (errs==0) ? 0 : 1;
+}
+
+#endif /* TEST_HARNESS */
diff --git a/src/f25519sub_mini.c b/src/f25519sub_mini.c
@@ -0,0 +1,87 @@
+/*
+ *
+ * F25519 field subtract from Minicrypt library
+ *
+ * This program is placed into the public domain
+ * by its author, Ian Harvey.
+ * Note there is NO WARRANTY of any kind.
+ */
+
+#define MPIMINI_INTERNAL_API
+#include "mpi_mini.h"
+
+void F25519_sub3_mini(F25519_Mini *res, const F25519_Mini *s1, const F25519_Mini *s2)
+{
+    UInt_Mini minus_s2;
+    mpisub_mini(&minus_s2, &F25519_P_mini_, s2);
+    // NB - s2 may be 0, in which case negS2 won't be a valid field element.
+    //    
+    mpiadd_mini(res, s1, &minus_s2);
+    F25519_reduce_mini_(res);
+}
+
+/* Test harness ======================================================= */
+#ifdef TEST_HARNESS
+
+#include <stdio.h>
+#include <string.h>
+
+typedef struct
+{
+  F25519_Mini a;
+  F25519_Mini b;
+  F25519_Mini res;
+}
+  F25519Sub_TV;
+
+static const F25519Sub_TV sub_tvs[] =
+{
+#include "testvectors/f25519sub.inc"
+};
+
+static const int sub_tvs_count = sizeof(sub_tvs) / sizeof(F25519Sub_TV);
+
+int main(void)
+{
+  int i, errs;
+
+  errs = 0;
+  for (i=0; i < sub_tvs_count; i++)
+  {
+    const F25519Sub_TV *tv = &sub_tvs[i];
+    F25519_Mini res;
+
+    F25519_sub3_mini(&res, &tv->a, &tv->b);
+    if ( !F25519_equal_mini(&res, &tv->res) )
+    {
+      printf("Test #%d failed (1)\n", i);
+      errs ++;
+      continue;
+    }
+
+    F25519_copy_mini(&res, &tv->a);
+    F25519_sub3_mini(&res, &res, &tv->b);
+
+    if ( !F25519_equal_mini(&res, &tv->res) )
+    {
+      printf("Test #%d failed (2)\n", i);
+      errs ++;
+      continue;
+    }
+
+    F25519_copy_mini(&res, &tv->b);
+    F25519_sub3_mini(&res, &tv->a, &res);
+
+    if ( !F25519_equal_mini(&res, &tv->res) )
+    {
+      printf("Test #%d failed (3)\n", i);
+      errs ++;
+      continue;
+    }
+  }
+
+  printf("%d errors out of %d\n", errs, sub_tvs_count);
+  return (errs==0) ? 0 : 1;
+}
+
+#endif /* TEST_HARNESS */