Remove a strict aliasing issue with pre-computed curve448 constants
[openssl.git] / crypto / ec / curve448 / curve448.c
index 920705b..2d91f97 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2017-2018 The OpenSSL Project Authors. All Rights Reserved.
  * Copyright 2015-2016 Cryptography Research, Inc.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
 
 #define COFACTOR 4
 
-/* Comb config: number of combs, n, t, s. */
-#define COMBS_N 5
-#define COMBS_T 5
-#define COMBS_S 18
 #define C448_WNAF_FIXED_TABLE_BITS 5
 #define C448_WNAF_VAR_TABLE_BITS 3
 
@@ -40,23 +36,7 @@ static const curve448_scalar_t precomputed_scalarmul_adjustment = {
 
 #define WBITS C448_WORD_BITS   /* NB this may be different from ARCH_WORD_BITS */
 
-/* Projective Niels coordinates */
-typedef struct {
-    gf a, b, c;
-} niels_s, niels_t[1];
-typedef struct {
-    niels_t n;
-    gf z;
-} VECTOR_ALIGNED pniels_t[1];
-
-/* Precomputed base */
-struct curve448_precomputed_s {
-    niels_t table[COMBS_N << (COMBS_T - 1)];
-};
-
-extern const gf curve448_precomputed_base_as_fe[];
-const curve448_precomputed_s *curve448_precomputed_base =
-    (const curve448_precomputed_s *)&curve448_precomputed_base_as_fe;
+extern const struct curve448_precomputed_s *curve448_precomputed_base;
 
 /* Inverse. */
 static void gf_invert(gf y, const gf x, int assert_nonzero)
@@ -167,6 +147,7 @@ static void sub_niels_from_pt(curve448_point_t d, const niels_t e,
                               int before_double)
 {
     gf a, b, c;
+
     gf_sub_nr(b, d->y, d->x);   /* 3+e */
     gf_mul(a, e->b, b);
     gf_add_nr(b, d->x, d->y);   /* 2+e */
@@ -207,9 +188,9 @@ c448_bool_t curve448_point_eq(const curve448_point_t p,
                               const curve448_point_t q)
 {
     mask_t succ;
+    gf a, b;
 
     /* equality mod 2-torsion compares x/y */
-    gf a, b;
     gf_mul(a, p->y, q->x);
     gf_mul(b, q->y, p->x);
     succ = gf_eq(a, b);
@@ -220,8 +201,8 @@ c448_bool_t curve448_point_eq(const curve448_point_t p,
 c448_bool_t curve448_point_valid(const curve448_point_t p)
 {
     mask_t out;
-
     gf a, b, c;
+
     gf_mul(a, p->x, p->y);
     gf_mul(b, p->z, p->t);
     out = gf_eq(a, b);
@@ -237,7 +218,7 @@ c448_bool_t curve448_point_valid(const curve448_point_t p)
     return mask_to_bool(out);
 }
 
-static ossl_inline void constant_time_lookup_niels(niels_s * __restrict__ ni,
+static ossl_inline void constant_time_lookup_niels(niels_s * RESTRICT ni,
                                                    const niels_t * table,
                                                    int nelts, int idx)
 {
@@ -248,17 +229,16 @@ void curve448_precomputed_scalarmul(curve448_point_t out,
                                     const curve448_precomputed_s * table,
                                     const curve448_scalar_t scalar)
 {
-    int i;
-    unsigned j, k;
+    unsigned int i, j, k;
     const unsigned int n = COMBS_N, t = COMBS_T, s = COMBS_S;
     niels_t ni;
-
     curve448_scalar_t scalar1x;
+
     curve448_scalar_add(scalar1x, scalar, precomputed_scalarmul_adjustment);
     curve448_scalar_halve(scalar1x, scalar1x);
 
-    for (i = s - 1; i >= 0; i--) {
-        if (i != (int)s - 1)
+    for (i = s; i > 0; i--) {
+        if (i != s)
             point_double_internal(out, out, 0);
 
         for (j = 0; j < n; j++) {
@@ -266,7 +246,8 @@ void curve448_precomputed_scalarmul(curve448_point_t out,
             mask_t invert;
 
             for (k = 0; k < t; k++) {
-                unsigned int bit = i + s * (k + j * t);
+                unsigned int bit = (i - 1) + s * (k + j * t);
+
                 if (bit < C448_SCALAR_BITS) {
                     tab |=
                         (scalar1x->limb[bit / WBITS] >> (bit % WBITS) & 1) << k;
@@ -281,8 +262,8 @@ void curve448_precomputed_scalarmul(curve448_point_t out,
                                        1 << (t - 1), tab);
 
             cond_neg_niels(ni, invert);
-            if ((i != (int)s - 1) || j) {
-                add_niels_to_pt(out, ni, j == n - 1 && i);
+            if ((i != s) || j != 0) {
+                add_niels_to_pt(out, ni, j == n - 1 && i != 1);
             } else {
                 niels_to_pt(out, ni);
             }
@@ -297,10 +278,10 @@ void curve448_point_mul_by_ratio_and_encode_like_eddsa(
                                     uint8_t enc[EDDSA_448_PUBLIC_BYTES],
                                     const curve448_point_t p)
 {
-
-    /* The point is now on the twisted curve.  Move it to untwisted. */
     gf x, y, z, t;
     curve448_point_t q;
+
+    /* The point is now on the twisted curve.  Move it to untwisted. */
     curve448_point_copy(q, p);
 
     {
@@ -354,9 +335,7 @@ c448_error_t curve448_point_decode_like_eddsa_and_mul_by_ratio(
     enc2[EDDSA_448_PRIVATE_BYTES - 1] &= ~0x80;
 
     succ = gf_deserialize(p->y, enc2, 1, 0);
-#if 0 == 0
     succ &= word_is_zero(enc2[EDDSA_448_PRIVATE_BYTES - 1]);
-#endif
 
     gf_sqr(p->x, p->y);
     gf_sub(p->z, ONE, p->x);    /* num = 1-y^2 */
@@ -371,8 +350,9 @@ c448_error_t curve448_point_decode_like_eddsa_and_mul_by_ratio(
     gf_copy(p->z, ONE);
 
     {
-        /* 4-isogeny 2xy/(y^2-ax^2), (y^2+ax^2)/(2-y^2-ax^2) */
         gf a, b, c, d;
+
+        /* 4-isogeny 2xy/(y^2-ax^2), (y^2+ax^2)/(2-y^2-ax^2) */
         gf_sqr(c, p->x);
         gf_sqr(a, p->y);
         gf_add(d, c, a);
@@ -425,7 +405,7 @@ c448_error_t x448_int(uint8_t out[X_PUBLIC_BYTES],
             sb = -1;
 
         k_t = (sb >> (t % 8)) & 1;
-        k_t = -k_t;             /* set to all 0s or all 1s */
+        k_t = 0 - k_t;             /* set to all 0s or all 1s */
 
         swap ^= k_t;
         gf_cond_swap(x2, x3, swap);
@@ -478,6 +458,7 @@ void curve448_point_mul_by_ratio_and_encode_like_x448(uint8_t
                                                       const curve448_point_t p)
 {
     curve448_point_t q;
+
     curve448_point_copy(q, p);
     gf_invert(q->t, q->x, 0);   /* 1/x */
     gf_mul(q->z, q->t, q->y);   /* y/x */
@@ -498,7 +479,7 @@ void x448_derive_public_key(uint8_t out[X_PUBLIC_BYTES],
     memcpy(scalar2, scalar, sizeof(scalar2));
     scalar2[0] &= -(uint8_t)COFACTOR;
 
-    scalar2[X_PRIVATE_BYTES - 1] &= ~(-1u << ((X_PRIVATE_BITS + 7) % 8));
+    scalar2[X_PRIVATE_BYTES - 1] &= ~((0u - 1u) << ((X_PRIVATE_BITS + 7) % 8));
     scalar2[X_PRIVATE_BYTES - 1] |= 1 << ((X_PRIVATE_BITS + 7) % 8);
 
     curve448_scalar_decode_long(the_scalar, scalar2, sizeof(scalar2));
@@ -517,6 +498,46 @@ struct smvt_control {
     int power, addend;
 };
 
+#if defined(__GNUC__) || defined(__clang__)
+# define NUMTRAILINGZEROS      __builtin_ctz
+#else
+# define NUMTRAILINGZEROS      numtrailingzeros
+static uint32_t numtrailingzeros(uint32_t i)
+{
+    uint32_t tmp;
+    uint32_t num = 31;
+
+    if (i == 0)
+        return 32;
+
+    tmp = i << 16;
+    if (tmp != 0) {
+        i = tmp;
+        num -= 16;
+    }
+    tmp = i << 8;
+    if (tmp != 0) {
+        i = tmp;
+        num -= 8;
+    }
+    tmp = i << 4;
+    if (tmp != 0) {
+        i = tmp;
+        num -= 4;
+    }
+    tmp = i << 2;
+    if (tmp != 0) {
+        i = tmp;
+        num -= 2;
+    }
+    tmp = i << 1;
+    if (tmp != 0)
+        num--;
+
+    return num;
+}
+#endif
+
 static int recode_wnaf(struct smvt_control *control,
                        /* [nbits/(table_bits + 1) + 3] */
                        const curve448_scalar_t scalar,
@@ -549,12 +570,12 @@ static int recode_wnaf(struct smvt_control *control,
         }
 
         while (current & 0xFFFF) {
-            uint32_t pos = __builtin_ctz((uint32_t)current);
+            uint32_t pos = NUMTRAILINGZEROS((uint32_t)current);
             uint32_t odd = (uint32_t)current >> pos;
             int32_t delta = odd & mask;
 
             assert(position >= 0);
-            if (odd & 1 << (table_bits + 1))
+            if (odd & (1 << (table_bits + 1)))
                 delta -= (1 << (table_bits + 1));
             current -= delta << pos;
             control[position].power = pos + 16 * (w - 1);
@@ -567,9 +588,9 @@ static int recode_wnaf(struct smvt_control *control,
 
     position++;
     n = table_size - position;
-    for (i = 0; i < n; i++) {
+    for (i = 0; i < n; i++)
         control[i] = control[i + position];
-    }
+
     return n - 1;
 }
 
@@ -601,17 +622,15 @@ static void prepare_wnaf_table(pniels_t * output,
     OPENSSL_cleanse(twop, sizeof(twop));
 }
 
-extern const gf curve448_precomputed_wnaf_as_fe[];
-static const niels_t *curve448_wnaf_base =
-    (const niels_t *)curve448_precomputed_wnaf_as_fe;
+extern const niels_t *curve448_wnaf_base;
 
 void curve448_base_double_scalarmul_non_secret(curve448_point_t combo,
                                                const curve448_scalar_t scalar1,
                                                const curve448_point_t base2,
                                                const curve448_scalar_t scalar2)
 {
-    const int table_bits_var = C448_WNAF_VAR_TABLE_BITS,
-        table_bits_pre = C448_WNAF_FIXED_TABLE_BITS;
+    const int table_bits_var = C448_WNAF_VAR_TABLE_BITS;
+    const int table_bits_pre = C448_WNAF_FIXED_TABLE_BITS;
     struct smvt_control control_var[C448_SCALAR_BITS /
                                     (C448_WNAF_VAR_TABLE_BITS + 1) + 3];
     struct smvt_control control_pre[C448_SCALAR_BITS /
@@ -643,37 +662,36 @@ void curve448_base_double_scalarmul_non_secret(curve448_point_t combo,
     }
 
     for (i--; i >= 0; i--) {
-        int cv = (i == control_var[contv].power), cp =
-            (i == control_pre[contp].power);
+        int cv = (i == control_var[contv].power);
+        int cp = (i == control_pre[contp].power);
+
         point_double_internal(combo, combo, i && !(cv || cp));
 
         if (cv) {
             assert(control_var[contv].addend);
 
-            if (control_var[contv].addend > 0) {
+            if (control_var[contv].addend > 0)
                 add_pniels_to_pt(combo,
                                  precmp_var[control_var[contv].addend >> 1],
                                  i && !cp);
-            } else {
+            else
                 sub_pniels_from_pt(combo,
                                    precmp_var[(-control_var[contv].addend)
                                               >> 1], i && !cp);
-            }
             contv++;
         }
 
         if (cp) {
             assert(control_pre[contp].addend);
 
-            if (control_pre[contp].addend > 0) {
+            if (control_pre[contp].addend > 0)
                 add_niels_to_pt(combo,
                                 curve448_wnaf_base[control_pre[contp].addend
                                                    >> 1], i);
-            } else {
+            else
                 sub_niels_from_pt(combo,
                                   curve448_wnaf_base[(-control_pre
                                                       [contp].addend) >> 1], i);
-            }
             contp++;
         }
     }