Support big-endian processors. Eliminate the dependency on the

mozilla/security/nss/lib/freebl/ecl/ecp_256_32.c

 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 /* A 32-bit implementation of the NIST P-256 elliptic curve. */
 
 #include <string.h>
 
 #include "prtypes.h"
 #include "mpi.h"
 #include "mpi-priv.h"
 #include "ecp.h"
+#include "secport.h"
 
 typedef PRUint8 u8;
 typedef PRUint32 u32;
-typedef PRInt32 s32;
 typedef PRUint64 u64;
 
 /* Our field elements are represented as nine, unsigned 32-bit words. Freebl's
  * MPI library calls them digits, but here they are called limbs, which is
  * GMP's terminology.
  *
  * The value of an felem (field element) is:
  *   x[0] + (x[1] * 2**29) + (x[2] * 2**57) + ... + (x[8] * 2**228)
  *
  * That is, each limb is alternately 29 or 28-bits wide in little-endian
@@ skipping 127 matching lines @@
     0xbe73d6f, 0xaa88141, 0xd976c81, 0x7e7a9cc, 0x18beb771, 0xd773cbd, 0x13f51951, 0x9d0c177, 0x1c49a78,
 };
 
 /* Field element operations:
  */
 
 /* NON_ZERO_TO_ALL_ONES returns:
  *   0xffffffff for 0 < x <= 2**31
  *   0 for x == 0 or x > 2**31.
  *
- * This macro assumes that right-shifting a signed number shifts in the MSB on
- * the left. This is not ensured by the C standard, but is true on the CPUs
- * that we're targetting with this code (x86 and ARM).
+ * x must be a u32 or an equivalent type such as limb.
  */
-#define NON_ZERO_TO_ALL_ONES(x) (~((u32) (((s32) ((x)-1)) >> 31)))
+#define NON_ZERO_TO_ALL_ONES(x) ((((u32)(x) - 1) >> 31) - 1)
 
 /* felem_reduce_carry adds a multiple of p in order to cancel |carry|,
  * which is a term at 2**257.
  *
  * On entry: carry < 2**3, inout[0,2,...] < 2**29, inout[1,3,...] < 2**28.
  * On exit: inout[0,2,..] < 2**30, inout[1,3,...] < 2**29.
  */
 static void felem_reduce_carry(felem inout, limb carry)
 {
     const u32 carry_mask = NON_ZERO_TO_ALL_ONES(carry);
@@ skipping 947 matching lines @@
     memset(ny, 0, sizeof(felem));
     memset(nz, 0, sizeof(felem));
 
     /* The loop adds bits at positions 0, 64, 128 and 192, followed by
      * positions 32,96,160 and 224 and does this 32 times.
      */
     for (i = 0; i < 32; i++) {
         if (i) {
             point_double(nx, ny, nz, nx, ny, nz);
         }
+        table_offset = 0;
         for (j = 0; j <= 32; j += 32) {
             char bit0 = get_bit(scalar, 31 - i + j);
             char bit1 = get_bit(scalar, 95 - i + j);
             char bit2 = get_bit(scalar, 159 - i + j);
             char bit3 = get_bit(scalar, 223 - i + j);
             limb index = bit0 | (bit1 << 1) | (bit2 << 2) | (bit3 << 3);
 
-            table_offset = ((((s32)j) << (32-6)) >> 31) & (30*NLIMBS);
             select_affine_point(px, py, kPrecomputed + table_offset, index);
+            table_offset += 30 * NLIMBS;
 
             /* Since scalar is less than the order of the group, we know that
              * {nx,ny,nz} != {px,py,1}, unless both are zero, which we handle
              * below.
              */
             point_add_mixed(tx, ty, tz, nx, ny, nz, px, py);
             /* The result of point_add_mixed is incorrect if {nx,ny,nz} is zero
              * (a.k.a.  the point at infinity). We handle that situation by
              * copying the point from the table.
              */
@@ skipping 67 matching lines @@
         }
 
         index = scalar[31 - i / 2];
         if ((i & 1) == 1) {
             index &= 15;
         } else {
             index >>= 4;
         }
 
         /* See the comments in scalar_base_mult about handling infinities. */
-        select_jacobian_point(px, py, pz, (limb *) precomp, index);
+        select_jacobian_point(px, py, pz, precomp[0][0], index);
         point_add(tx, ty, tz, nx, ny, nz, px, py, pz);
         copy_conditional(nx, px, n_is_infinity_mask);
         copy_conditional(ny, py, n_is_infinity_mask);
         copy_conditional(nz, pz, n_is_infinity_mask);
 
-        p_is_noninfinite_mask = ((s32) ~ (index - 1)) >> 31;
+        p_is_noninfinite_mask = NON_ZERO_TO_ALL_ONES(index);
         mask = p_is_noninfinite_mask & ~n_is_infinity_mask;
         copy_conditional(nx, tx, mask);
         copy_conditional(ny, ty, mask);
         copy_conditional(nz, tz, mask);
         n_is_infinity_mask &= ~p_is_noninfinite_mask;
     }
 }
 
 /* Interface with Freebl: */
 
+/* BYTESWAP_MP_DIGIT_TO_LE swaps the bytes of a mp_digit to
+ * little-endian order.
+ */
 #ifdef IS_BIG_ENDIAN
-#error "This code needs a little-endian processor"
+#ifdef __APPLE__
+#include <libkern/OSByteOrder.h>
+#define BYTESWAP32(x) OSSwapInt32(x)
+#define BYTESWAP64(x) OSSwapInt64(x)
+#else
+#define BYTESWAP32(x) \

[agl, 2013/02/02 20:34:26]

This only works if x is unsigned, but I believe that's ok here.

+    ((x) >> 24 | (x) >> 8 & 0xff00 | ((x) & 0xff00) << 8 | (x) << 24)
+#define BYTESWAP64(x) \
+    ((x) >> 56 | (x) >> 40 & 0xff00 | \
+     (x) >> 24 & 0xff0000 | (x) >> 8 & 0xff000000 | \
+     ((x) & 0xff000000) << 8 | ((x) & 0xff0000) << 24 | \
+     ((x) & 0xff00) << 40 | (x) << 56)
 #endif
 
-static const u32 kRInvDigits[8] = {
+#ifdef MP_USE_UINT_DIGIT
+#define BYTESWAP_MP_DIGIT_TO_LE(x) BYTESWAP32(BYTESWAP32(x))
+#else
+#define BYTESWAP_MP_DIGIT_TO_LE(x) BYTESWAP64(BYTESWAP64(x))
+#endif
+#endif /* IS_BIG_ENDIAN */
+
+#ifdef MP_USE_UINT_DIGIT
+static const mp_digit kRInvDigits[8] = {
     0x80000000, 1, 0xffffffff, 0,
     0x80000001, 0xfffffffe, 1, 0x7fffffff
 };
+#else
+static const mp_digit kRInvDigits[4] = {
+    PR_UINT64(0x180000000),  0xffffffff,
+    PR_UINT64(0xfffffffe80000001), PR_UINT64(0x7fffffff00000001)
+};
+#endif
 #define MP_DIGITS_IN_256_BITS (32/sizeof(mp_digit))
 static const mp_int kRInv = {
     MP_ZPOS,
     MP_DIGITS_IN_256_BITS,
     MP_DIGITS_IN_256_BITS,
-    /* Because we are running on a little-endian processor, this cast works for
-     * both 32 and 64-bit processors.
-     */
     (mp_digit*) kRInvDigits
 };
 
 static const limb kTwo28 = 0x10000000;
 static const limb kTwo29 = 0x20000000;
 
 /* to_montgomery sets out = R*in. */
 static mp_err to_montgomery(felem out, const mp_int *in, const ECGroup *group)
 {
     /* There are no MPI functions for bitshift operations and we wish to shift
@@ skipping 55 matching lines @@
 CLEANUP:
     mp_clear(&result);
     mp_clear(&tmp);
     return res;
 }
 
 /* scalar_from_mp_int sets out_scalar=n, where n < the group order. */
 static void scalar_from_mp_int(u8 out_scalar[32], const mp_int *n)
 {
     /* We require that |n| is less than the order of the group and therefore it
-     * will fit into |scalar|. However, these is a timing side-channel here that
-     * we cannot avoid: if |n| is sufficiently small it may be one or more words
-     * too short and we'll copy less data.
+     * will fit into |out_scalar|. However, these is a timing side-channel here
+     * that we cannot avoid: if |n| is sufficiently small it may be one or more
+     * words too short and we'll copy less data.
      */
+    PORT_Assert(MP_USED(n) * sizeof(mp_digit) <= 32);
     memset(out_scalar, 0, 32);
+#ifdef IS_LITTLE_ENDIAN
     memcpy(out_scalar, MP_DIGITS(n), MP_USED(n) * sizeof(mp_digit));
+#else
+    {
+        mp_size i;
+        mp_digit swapped[MP_DIGITS_IN_256_BITS];
+        for (i = 0; i < MP_USED(n); i++) {
+            swapped[i] = BYTESWAP_MP_DIGIT_TO_LE(MP_DIGIT(n, i));
+        }
+        memcpy(out_scalar, swapped, MP_USED(n) * sizeof(mp_digit));
+    }
+#endif
 }
 
 /* ec_GFp_nistp256_base_point_mul sets {out_x,out_y} = nG, where n is < the
  * order of the group.
  */
 static mp_err ec_GFp_nistp256_base_point_mul(const mp_int *n,
                                              mp_int *out_x, mp_int *out_y,
                                              const ECGroup *group)
 {
     u8 scalar[32];
     felem x, y, z, x_affine, y_affine;
     mp_err res;
 
-    /* FIXME(agl): test that n < order. */

[agl, 2013/02/02 20:34:26]

I think this TODO should remain. I'll write something in a DEBUG section to
ensure this.

-
     scalar_from_mp_int(scalar, n);
     scalar_base_mult(x, y, z, scalar);
     point_to_affine(x_affine, y_affine, x, y, z);
     MP_CHECKOK(from_montgomery(out_x, x_affine, group));
     MP_CHECKOK(from_montgomery(out_y, y_affine, group));
 
 CLEANUP:
     return res;
 }
 
@@ skipping 90 matching lines @@
 /* Wire in fast point multiplication for named curves. */
 mp_err ec_group_set_gfp256_32(ECGroup *group, ECCurveName name)
 {
     if (name == ECCurve_NIST_P256) {
         group->base_point_mul = &ec_GFp_nistp256_base_point_mul;
         group->point_mul = &ec_GFp_nistp256_point_mul;
         group->points_mul = &ec_GFp_nistp256_points_mul_vartime;
     }
     return MP_OKAY;
 }