docker: source checking container
[gnuk/gnuk.git] / src / modp256r1.c
index dc52a73..90518c5 100644 (file)
@@ -1,7 +1,8 @@
 /*
  * modp256r1.c -- modulo arithmetic for p256r1
  *
- * Copyright (C) 2011, 2013, 2014 Free Software Initiative of Japan
+ * Copyright (C) 2011, 2013, 2014, 2016
+ *               Free Software Initiative of Japan
  * Author: NIIBE Yutaka <gniibe@fsij.org>
  *
  * This file is a part of Gnuk, a GnuPG USB Token implementation.
@@ -49,12 +50,12 @@ const bn256 p256r1 = { {0xffffffff, 0xffffffff, 0xffffffff, 0x00000000,
 /*
  * Implementation Note.
  *
- * It's not always modulo p256r1.  The representation is redundant
- * during computation.  For example, when we add the prime - 1 and 1,
- * it won't overflow to 2^256, and the result is represented within
- * 256-bit.
+ * It's always modulo p256r1.
+ *
+ * Once, I tried redundant representation which caused wrong
+ * calculation.  Implementation could be correct with redundant
+ * representation, but it found that it's more expensive.
  *
- * It is guaranteed that modp256r1_reduce reduces to modulo p256r1.
  */
 
 /**
@@ -63,14 +64,16 @@ const bn256 p256r1 = { {0xffffffff, 0xffffffff, 0xffffffff, 0x00000000,
 void
 modp256r1_add (bn256 *X, const bn256 *A, const bn256 *B)
 {
-  uint32_t carry;
+  uint32_t cond;
   bn256 tmp[1];
 
-  carry = bn256_add (X, A, B);
-  if (carry)
-    bn256_sub (X, X, P256R1);
+  cond = (bn256_add (X, A, B) == 0);
+  cond &= bn256_sub (tmp, X, P256R1);
+  if (cond)
+    /* No-carry AND borrow */
+    memcpy (tmp, tmp, sizeof (bn256));
   else
-    bn256_sub (tmp, X, P256R1);
+    memcpy (X, tmp, sizeof (bn256));
 }
 
 /**
@@ -83,10 +86,11 @@ modp256r1_sub (bn256 *X, const bn256 *A, const bn256 *B)
   bn256 tmp[1];
 
   borrow = bn256_sub (X, A, B);
+  bn256_add (tmp, X, P256R1);
   if (borrow)
-    bn256_add (X, X, P256R1);
+    memcpy (X, tmp, sizeof (bn256));
   else
-    bn256_add (tmp, X, P256R1);
+    memcpy (tmp, tmp, sizeof (bn256));
 }
 
 /**
@@ -95,7 +99,7 @@ modp256r1_sub (bn256 *X, const bn256 *A, const bn256 *B)
 void
 modp256r1_reduce (bn256 *X, const bn512 *A)
 {
-  bn256 tmp[1];
+  bn256 tmp[1], tmp0[1];
   uint32_t borrow;
 
 #define S1 X
@@ -116,6 +120,11 @@ modp256r1_reduce (bn256 *X, const bn512 *A)
   S1->word[2] = A->word[2];
   S1->word[1] = A->word[1];
   S1->word[0] = A->word[0];
+  borrow = bn256_sub (tmp0, S1, P256R1);
+  if (borrow)
+    memcpy (tmp0, tmp0, sizeof (bn256));
+  else
+    memcpy (S1, tmp0, sizeof (bn256));
   /* X = S1 */
 
   S2->word[7] = A->word[15];
@@ -155,6 +164,11 @@ modp256r1_reduce (bn256 *X, const bn512 *A)
   S5->word[2] = A->word[11];
   S5->word[1] = A->word[10];
   S5->word[0] = A->word[9];
+  borrow = bn256_sub (tmp0, S5, P256R1);
+  if (borrow)
+    memcpy (tmp0, tmp0, sizeof (bn256));
+  else
+    memcpy (S5, tmp0, sizeof (bn256));
   /* X += S5 */
   modp256r1_add (X, X, S5);
 
@@ -164,6 +178,11 @@ modp256r1_reduce (bn256 *X, const bn512 *A)
   S6->word[2] = A->word[13];
   S6->word[1] = A->word[12];
   S6->word[0] = A->word[11];
+  borrow = bn256_sub (tmp0, S6, P256R1);
+  if (borrow)
+    memcpy (tmp0, tmp0, sizeof (bn256));
+  else
+    memcpy (S6, tmp0, sizeof (bn256));
   /* X -= S6 */
   modp256r1_sub (X, X, S6);
 
@@ -174,6 +193,11 @@ modp256r1_reduce (bn256 *X, const bn512 *A)
   S7->word[2] = A->word[14];
   S7->word[1] = A->word[13];
   S7->word[0] = A->word[12];
+  borrow = bn256_sub (tmp0, S7, P256R1);
+  if (borrow)
+    memcpy (tmp0, tmp0, sizeof (bn256));
+  else
+    memcpy (S7, tmp0, sizeof (bn256));
   /* X -= S7 */
   modp256r1_sub (X, X, S7);
 
@@ -240,187 +264,6 @@ modp256r1_sqr (bn256 *X, const bn256 *A)
   modp256r1_reduce (X, AA);
 }
 
-/**
- * @brief  C = (1 / a)  mod p256r1
- *
- * Return -1 on error.
- * Return 0 on success.
- */
-#define MAX_N_BITS 256
-
-int
-modp256r1_inv (bn256 *C, const bn256 *a)
-{
-  bn256 u[1], v[1], tmp[1];
-  bn256 A[1] = { { { 1, 0, 0, 0, 0, 0, 0, 0 } } };
-  uint32_t carry;
-  int n = MAX_N_BITS * 3;
-
-  if (bn256_is_zero (a))
-    return -1;
-
-  memset (C, 0, sizeof (bn256));
-  memcpy (u, a, sizeof (bn256));
-  memcpy (v, P256R1, sizeof (bn256));
-
-  while (n--)
-    {
-      int c = (bn256_is_even (u) << 1) + bn256_is_even (v);
-
-      switch (c)
-       {
-       case 3:
-         bn256_shift (u, u, -1);
-         if (bn256_is_even (A))
-           {
-             bn256_add (tmp, A, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (A, A, P256R1);
-
-         bn256_shift (A, A, -1);
-         A->word[7] |= carry * 0x80000000;
-
-         bn256_shift (v, v, -1);
-         if (bn256_is_even (C))
-           {
-             bn256_add (tmp, C, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (C, C, P256R1);
-
-         bn256_shift (C, C, -1);
-         C->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (tmp, tmp))
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, tmp);
-           }
-         else
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, A);
-           }
-         break;
-
-       case 1:
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256R1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         bn256_shift (v, v, -1);
-         if (bn256_is_even (C))
-           {
-             bn256_add (tmp, C, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (C, C, P256R1);
-
-         bn256_shift (C, C, -1);
-         C->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (tmp, tmp))
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, tmp);
-           }
-         else
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, A);
-           }
-         break;
-
-       case 2:
-         bn256_shift (u, u, -1);
-         if (bn256_is_even (A))
-           {
-             bn256_add (tmp, A, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (A, A, P256R1);
-
-         bn256_shift (A, A, -1);
-         A->word[7] |= carry * 0x80000000;
-
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256R1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (tmp, tmp))
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, tmp);
-           }
-         else
-           {
-             bn256_sub (tmp, tmp, tmp);
-             modp256r1_sub (tmp, tmp, A);
-           }
-         break;
-
-       case 0:
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256R1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         bn256_shift (tmp, tmp, -1);
-         if (bn256_is_even (tmp))
-           {
-             bn256_add (tmp, tmp, P256R1);
-             carry = 0;
-           }
-         else
-           carry = bn256_add (tmp, tmp, P256R1);
-
-         bn256_shift (tmp, tmp, -1);
-         tmp->word[7] |= carry * 0x80000000;
-
-         if (bn256_is_ge (u, v))
-           {
-             bn256_sub (u, u, v);
-             modp256r1_sub (A, A, C);
-           }
-         else
-           {
-             bn256_sub (v, v, u);
-             modp256r1_sub (C, C, A);
-           }
-         break;
-       }
-    }
-
-  return 0;
-}
 
 /**
  * @brief  X = (A << shift) mod p256r1