Remove a strict aliasing issue with pre-computed curve448 constants
[openssl.git] / crypto / ec / curve448 / curve448.c
index e2c5770..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 DECAF_WNAF_FIXED_TABLE_BITS 5
-#define DECAF_WNAF_VAR_TABLE_BITS 3
+#define C448_WNAF_FIXED_TABLE_BITS 5
+#define C448_WNAF_VAR_TABLE_BITS 3
 
 static const int EDWARDS_D = -39081;
 static const curve448_scalar_t precomputed_scalarmul_adjustment = {
@@ -38,25 +34,9 @@ static const curve448_scalar_t precomputed_scalarmul_adjustment = {
 
 #define TWISTED_D ((EDWARDS_D)-1)
 
-#define WBITS DECAF_WORD_BITS   /* NB this may be different from ARCH_WORD_BITS */
+#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 */
@@ -203,13 +184,13 @@ static void sub_pniels_from_pt(curve448_point_t p, const pniels_t pn,
     sub_niels_from_pt(p, pn->n, before_double);
 }
 
-decaf_bool_t curve448_point_eq(const curve448_point_t p,
-                               const curve448_point_t q)
+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);
@@ -217,11 +198,11 @@ decaf_bool_t curve448_point_eq(const curve448_point_t p,
     return mask_to_bool(succ);
 }
 
-decaf_bool_t curve448_point_valid(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 @@ decaf_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,8 +246,9 @@ 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);
-                if (bit < DECAF_448_SCALAR_BITS) {
+                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);
             }
@@ -294,13 +275,13 @@ void curve448_precomputed_scalarmul(curve448_point_t out,
 }
 
 void curve448_point_mul_by_ratio_and_encode_like_eddsa(
-                                    uint8_t enc[DECAF_EDDSA_448_PUBLIC_BYTES],
+                                    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);
 
     {
@@ -329,9 +310,9 @@ void curve448_point_mul_by_ratio_and_encode_like_eddsa(
     gf_mul(x, y, z);
 
     /* Encode */
-    enc[DECAF_EDDSA_448_PRIVATE_BYTES - 1] = 0;
+    enc[EDDSA_448_PRIVATE_BYTES - 1] = 0;
     gf_serialize(enc, x, 1);
-    enc[DECAF_EDDSA_448_PRIVATE_BYTES - 1] |= 0x80 & gf_lobit(t);
+    enc[EDDSA_448_PRIVATE_BYTES - 1] |= 0x80 & gf_lobit(t);
 
     OPENSSL_cleanse(x, sizeof(x));
     OPENSSL_cleanse(y, sizeof(y));
@@ -340,23 +321,21 @@ void curve448_point_mul_by_ratio_and_encode_like_eddsa(
     curve448_point_destroy(q);
 }
 
-decaf_error_t curve448_point_decode_like_eddsa_and_mul_by_ratio(
+c448_error_t curve448_point_decode_like_eddsa_and_mul_by_ratio(
                                 curve448_point_t p,
-                                const uint8_t enc[DECAF_EDDSA_448_PUBLIC_BYTES])
+                                const uint8_t enc[EDDSA_448_PUBLIC_BYTES])
 {
-    uint8_t enc2[DECAF_EDDSA_448_PUBLIC_BYTES];
+    uint8_t enc2[EDDSA_448_PUBLIC_BYTES];
     mask_t low;
     mask_t succ;
 
     memcpy(enc2, enc, sizeof(enc2));
 
-    low = ~word_is_zero(enc2[DECAF_EDDSA_448_PRIVATE_BYTES - 1] & 0x80);
-    enc2[DECAF_EDDSA_448_PRIVATE_BYTES - 1] &= ~0x80;
+    low = ~word_is_zero(enc2[EDDSA_448_PRIVATE_BYTES - 1] & 0x80);
+    enc2[EDDSA_448_PRIVATE_BYTES - 1] &= ~0x80;
 
     succ = gf_deserialize(p->y, enc2, 1, 0);
-#if 0 == 0
-    succ &= word_is_zero(enc2[DECAF_EDDSA_448_PRIVATE_BYTES - 1]);
-#endif
+    succ &= word_is_zero(enc2[EDDSA_448_PRIVATE_BYTES - 1]);
 
     gf_sqr(p->x, p->y);
     gf_sub(p->z, ONE, p->x);    /* num = 1-y^2 */
@@ -371,8 +350,9 @@ decaf_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);
@@ -396,12 +376,12 @@ decaf_error_t curve448_point_decode_like_eddsa_and_mul_by_ratio(
     OPENSSL_cleanse(enc2, sizeof(enc2));
     assert(curve448_point_valid(p) || ~succ);
 
-    return decaf_succeed_if(mask_to_bool(succ));
+    return c448_succeed_if(mask_to_bool(succ));
 }
 
-decaf_error_t decaf_x448(uint8_t out[X_PUBLIC_BYTES],
-                         const uint8_t base[X_PUBLIC_BYTES],
-                         const uint8_t scalar[X_PRIVATE_BYTES])
+c448_error_t x448_int(uint8_t out[X_PUBLIC_BYTES],
+                      const uint8_t base[X_PUBLIC_BYTES],
+                      const uint8_t scalar[X_PRIVATE_BYTES])
 {
     gf x1, x2, z2, x3, z3, t1, t2;
     int t;
@@ -425,7 +405,7 @@ decaf_error_t decaf_x448(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);
@@ -470,7 +450,7 @@ decaf_error_t decaf_x448(uint8_t out[X_PUBLIC_BYTES],
     OPENSSL_cleanse(t1, sizeof(t1));
     OPENSSL_cleanse(t2, sizeof(t2));
 
-    return decaf_succeed_if(mask_to_bool(nz));
+    return c448_succeed_if(mask_to_bool(nz));
 }
 
 void curve448_point_mul_by_ratio_and_encode_like_x448(uint8_t
@@ -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 */
@@ -486,8 +467,8 @@ void curve448_point_mul_by_ratio_and_encode_like_x448(uint8_t
     curve448_point_destroy(q);
 }
 
-void decaf_x448_derive_public_key(uint8_t out[X_PUBLIC_BYTES],
-                                  const uint8_t scalar[X_PRIVATE_BYTES])
+void x448_derive_public_key(uint8_t out[X_PUBLIC_BYTES],
+                            const uint8_t scalar[X_PRIVATE_BYTES])
 {
     /* Scalar conditioning */
     uint8_t scalar2[X_PRIVATE_BYTES];
@@ -498,13 +479,13 @@ void decaf_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));
 
     /* Compensate for the encoding ratio */
-    for (i = 1; i < DECAF_X448_ENCODE_RATIO; i <<= 1) {
+    for (i = 1; i < X448_ENCODE_RATIO; i <<= 1) {
         curve448_scalar_halve(the_scalar, the_scalar);
     }
     curve448_precomputed_scalarmul(p, curve448_precomputed_base, the_scalar);
@@ -517,12 +498,52 @@ 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,
                        unsigned int table_bits)
 {
-    unsigned int table_size = DECAF_448_SCALAR_BITS / (table_bits + 1) + 3;
+    unsigned int table_size = C448_SCALAR_BITS / (table_bits + 1) + 3;
     int position = table_size - 1; /* at the end */
     uint64_t current = scalar->limb[0] & 0xFFFF;
     uint32_t mask = (1 << (table_bits + 1)) - 1;
@@ -541,20 +562,20 @@ static int recode_wnaf(struct smvt_control *control,
      * 1/5 op. Probably not worth it.
      */
 
-    for (w = 1; w < (DECAF_448_SCALAR_BITS - 1) / 16 + 3; w++) {
-        if (w < (DECAF_448_SCALAR_BITS - 1) / 16 + 1) {
+    for (w = 1; w < (C448_SCALAR_BITS - 1) / 16 + 3; w++) {
+        if (w < (C448_SCALAR_BITS - 1) / 16 + 1) {
             /* Refill the 16 high bits of current */
             current += (uint32_t)((scalar->limb[w / B_OVER_16]
                        >> (16 * (w %  B_OVER_16))) << 16);
         }
 
         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,24 +622,22 @@ 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 = DECAF_WNAF_VAR_TABLE_BITS,
-        table_bits_pre = DECAF_WNAF_FIXED_TABLE_BITS;
-    struct smvt_control control_var[DECAF_448_SCALAR_BITS /
-                                    (DECAF_WNAF_VAR_TABLE_BITS + 1) + 3];
-    struct smvt_control control_pre[DECAF_448_SCALAR_BITS /
-                                    (DECAF_WNAF_FIXED_TABLE_BITS + 1) + 3];
+    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 /
+                                    (C448_WNAF_FIXED_TABLE_BITS + 1) + 3];
     int ncb_pre = recode_wnaf(control_pre, scalar1, table_bits_pre);
     int ncb_var = recode_wnaf(control_var, scalar2, table_bits_var);
-    pniels_t precmp_var[1 << DECAF_WNAF_VAR_TABLE_BITS];
+    pniels_t precmp_var[1 << C448_WNAF_VAR_TABLE_BITS];
     int contp = 0, contv = 0, i;
 
     prepare_wnaf_table(precmp_var, base2, table_bits_var);
@@ -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++;
         }
     }
@@ -697,12 +715,12 @@ void curve448_point_destroy(curve448_point_t point)
 int X448(uint8_t out_shared_key[56], const uint8_t private_key[56],
          const uint8_t peer_public_value[56])
 {
-    return decaf_x448(out_shared_key, peer_public_value, private_key)
-        == DECAF_SUCCESS;
+    return x448_int(out_shared_key, peer_public_value, private_key)
+           == C448_SUCCESS;
 }
 
 void X448_public_from_private(uint8_t out_public_value[56],
                               const uint8_t private_key[56])
 {
-    decaf_x448_derive_public_key(out_public_value, private_key);
+    x448_derive_public_key(out_public_value, private_key);
 }