* work which got its smarts from Daniel J. Bernstein's work on the same.
*/
-#ifdef EC_NISTP_64_GCC_128
+#include <openssl/opensslconf.h>
+#ifndef OPENSSL_NO_EC_NISTP_64_GCC_128
+#ifndef OPENSSL_SYS_VMS
#include <stdint.h>
+#else
+#include <inttypes.h>
+#endif
+
#include <string.h>
#include <openssl/err.h>
#include "ec_lcl.h"
0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5}
};
-/* The representation of field elements.
+/*-
+ * The representation of field elements.
* ------------------------------------
*
* We represent field elements with either four 128-bit values, eight 128-bit
/* This is the value of the prime as four 64-bit words, little-endian. */
static const u64 kPrime[4] = { 0xfffffffffffffffful, 0xffffffff, 0, 0xffffffff00000001ul };
-static const limb bottom32bits = 0xffffffff;
static const u64 bottom63bits = 0x7ffffffffffffffful;
/* bin32_to_felem takes a little-endian byte array and converts it into felem
}
-/* Field operations
- * ---------------- */
+/*-
+ * Field operations
+ * ----------------
+ */
static void smallfelem_one(smallfelem out)
{
/* zero105 is 0 mod p */
static const felem zero105 = { two105m41m9, two105, two105m41p9, two105m41p9 };
-/* smallfelem_neg sets |out| to |-small|
+/*-
+ * smallfelem_neg sets |out| to |-small|
* On exit:
* out[i] < out[i] + 2^105
*/
out[3] = zero105[3] - small[3];
}
-/* felem_diff subtracts |in| from |out|
+/*-
+ * felem_diff subtracts |in| from |out|
* On entry:
* in[i] < 2^104
* On exit:
/* zero107 is 0 mod p */
static const felem zero107 = { two107m43m11, two107, two107m43p11, two107m43p11 };
-/* An alternative felem_diff for larger inputs |in|
+/*-
+ * An alternative felem_diff for larger inputs |in|
* felem_diff_zero107 subtracts |in| from |out|
* On entry:
* in[i] < 2^106
out[3] -= in[3];
}
-/* longfelem_diff subtracts |in| from |out|
+/*-
+ * longfelem_diff subtracts |in| from |out|
* On entry:
* in[i] < 7*2^67
* On exit:
/* zero110 is 0 mod p */
static const felem zero110 = { two64m0, two110p32m0, two64m46, two64m32 };
-/* felem_shrink converts an felem into a smallfelem. The result isn't quite
+/*-
+ * felem_shrink converts an felem into a smallfelem. The result isn't quite
* minimal as the value may be greater than p.
*
* On entry:
static void felem_shrink(smallfelem out, const felem in)
{
felem tmp;
+ u64 a, b, mask;
+ s64 high, low;
+ static const u64 kPrime3Test = 0x7fffffff00000001ul; /* 2^63 - 2^32 + 1 */
+
/* Carry 2->3 */
tmp[3] = zero110[3] + in[3] + ((u64) (in[2] >> 64));
/* tmp[3] < 2^110 */
/* We perform two partial reductions where we eliminate the
* high-word of tmp[3]. We don't update the other words till the end.
*/
- u64 a = tmp[3] >> 64; /* a < 2^46 */
+ a = tmp[3] >> 64; /* a < 2^46 */
tmp[3] = (u64) tmp[3];
tmp[3] -= a;
tmp[3] += ((limb)a) << 32;
/* tmp[3] < 2^79 */
- u64 b = a;
+ b = a;
a = tmp[3] >> 64; /* a < 2^15 */
b += a; /* b < 2^46 + 2^15 < 2^47 */
tmp[3] = (u64) tmp[3];
/* In order to make space in tmp[3] for the carry from 2 -> 3, we
* conditionally subtract kPrime if tmp[3] is large enough. */
- static const u64 kPrime3Test = 0x7fffffff00000001ul; /* 2^63 - 2^32 + 1 */
- s64 high = tmp[3] >> 64;
+ high = tmp[3] >> 64;
/* As tmp[3] < 2^65, high is either 1 or 0 */
high <<= 63;
high >>= 63;
- /* high is:
+ /*-
+ * high is:
* all ones if the high word of tmp[3] is 1
* all zeros if the high word of tmp[3] if 0 */
- s64 low = tmp[3];
- u64 mask = low >> 63;
- /* mask is:
+ low = tmp[3];
+ mask = low >> 63;
+ /*-
+ * mask is:
* all ones if the MSB of low is 1
* all zeros if the MSB of low if 0 */
low &= bottom63bits;
/* if low was greater than kPrime3Test then the MSB is zero */
low = ~low;
low >>= 63;
- /* low is:
+ /*-
+ * low is:
* all ones if low was > kPrime3Test
* all zeros if low was <= kPrime3Test */
mask = (mask & low) | high;
out[3] = in[3];
}
-/* smallfelem_square sets |out| = |small|^2
+/*-
+ * smallfelem_square sets |out| = |small|^2
* On entry:
* small[i] < 2^64
* On exit:
out[7] = high;
}
-/* felem_square sets |out| = |in|^2
+/*-
+ * felem_square sets |out| = |in|^2
* On entry:
* in[i] < 2^109
* On exit:
smallfelem_square(out, small);
}
-/* smallfelem_mul sets |out| = |small1| * |small2|
+/*-
+ * smallfelem_mul sets |out| = |small1| * |small2|
* On entry:
* small1[i] < 2^64
* small2[i] < 2^64
out[7] = high;
}
-/* felem_mul sets |out| = |in1| * |in2|
+/*-
+ * felem_mul sets |out| = |in1| * |in2|
* On entry:
* in1[i] < 2^109
* in2[i] < 2^109
smallfelem_mul(out, small1, small2);
}
-/* felem_small_mul sets |out| = |small1| * |in2|
+/*-
+ * felem_small_mul sets |out| = |small1| * |in2|
* On entry:
* small1[i] < 2^64
* in2[i] < 2^109
/* zero100 is 0 mod p */
static const felem zero100 = { two100m36m4, two100, two100m36p4, two100m36p4 };
-/* Internal function for the different flavours of felem_reduce.
+/*-
+ * Internal function for the different flavours of felem_reduce.
* felem_reduce_ reduces the higher coefficients in[4]-in[7].
* On entry:
* out[0] >= in[6] + 2^32*in[6] + in[7] + 2^32*in[7]
out[3] += (in[7] * 3);
}
-/* felem_reduce converts a longfelem into an felem.
+/*-
+ * felem_reduce converts a longfelem into an felem.
* To be called directly after felem_square or felem_mul.
* On entry:
* in[0] < 2^64, in[1] < 3*2^64, in[2] < 5*2^64, in[3] < 7*2^64
felem_reduce_(out, in);
- /* out[0] > 2^100 - 2^36 - 2^4 - 3*2^64 - 3*2^96 - 2^64 - 2^96 > 0
+ /*-
+ * out[0] > 2^100 - 2^36 - 2^4 - 3*2^64 - 3*2^96 - 2^64 - 2^96 > 0
* out[1] > 2^100 - 2^64 - 7*2^96 > 0
* out[2] > 2^100 - 2^36 + 2^4 - 5*2^64 - 5*2^96 > 0
* out[3] > 2^100 - 2^36 + 2^4 - 7*2^64 - 5*2^96 - 3*2^96 > 0
*/
}
-/* felem_reduce_zero105 converts a larger longfelem into an felem.
+/*-
+ * felem_reduce_zero105 converts a larger longfelem into an felem.
* On entry:
* in[0] < 2^71
* On exit:
felem_reduce_(out, in);
- /* out[0] > 2^105 - 2^41 - 2^9 - 2^71 - 2^103 - 2^71 - 2^103 > 0
+ /*-
+ * out[0] > 2^105 - 2^41 - 2^9 - 2^71 - 2^103 - 2^71 - 2^103 > 0
* out[1] > 2^105 - 2^71 - 2^103 > 0
* out[2] > 2^105 - 2^41 + 2^9 - 2^71 - 2^103 > 0
* out[3] > 2^105 - 2^41 + 2^9 - 2^71 - 2^103 - 2^103 > 0
* compare each u64, from most-significant to least significant. For
* each one, if all words so far have been equal (m is all ones) then a
* non-equal result is the answer. Otherwise we continue. */
- for (i = 3; i < 4; i--) {
+ for (i = 3; i < 4; i--)
+ {
+ u64 equal;
uint128_t a = ((uint128_t) kPrime[i]) - out[i];
/* if out[i] > kPrime[i] then a will underflow and the high
* 64-bits will all be set. */
/* if kPrime[i] == out[i] then |equal| will be all zeros and
* the decrement will make it all ones. */
- u64 equal = kPrime[i] ^ out[i];
+ equal = kPrime[i] ^ out[i];
equal--;
equal &= equal << 32;
equal &= equal << 16;
equal = ((s64) equal) >> 63;
all_equal_so_far &= equal;
- }
+ }
/* if all_equal_so_far is still all ones then the two values are equal
* and so out >= kPrime is true. */
felem_contract(out, tmp);
}
-/* felem_is_zero returns a limb with all bits set if |in| == 0 (mod p) and 0
+/*-
+ * felem_is_zero returns a limb with all bits set if |in| == 0 (mod p) and 0
* otherwise.
* On entry:
* small[i] < 2^64
static limb smallfelem_is_zero(const smallfelem small)
{
limb result;
+ u64 is_p;
u64 is_zero = small[0] | small[1] | small[2] | small[3];
is_zero--;
is_zero &= is_zero << 1;
is_zero = ((s64) is_zero) >> 63;
- u64 is_p = (small[0] ^ kPrime[0]) |
- (small[1] ^ kPrime[1]) |
- (small[2] ^ kPrime[2]) |
- (small[3] ^ kPrime[3]);
+ is_p = (small[0] ^ kPrime[0]) |
+ (small[1] ^ kPrime[1]) |
+ (small[2] ^ kPrime[2]) |
+ (small[3] ^ kPrime[3]);
is_p--;
is_p &= is_p << 32;
is_p &= is_p << 16;
return (int) (smallfelem_is_zero(small) & ((limb)1));
}
-/* felem_inv calculates |out| = |in|^{-1}
+/*-
+ * felem_inv calculates |out| = |in|^{-1}
*
* Based on Fermat's Little Theorem:
* a^p = a (mod p)
felem_contract(out, tmp);
}
-/* Group operations
+/*-
+ * Group operations
* ----------------
*
* Building on top of the field operations we have the operations on the
* elliptic curve group itself. Points on the curve are represented in Jacobian
* coordinates */
-/* point_double calculates 2*(x_in, y_in, z_in)
+/*-
+ * point_double calculates 2*(x_in, y_in, z_in)
*
* The method is taken from:
* http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
}
}
-/* point_add calcuates (x1, y1, z1) + (x2, y2, z2)
+/*-
+ * point_add calcuates (x1, y1, z1) + (x2, y2, z2)
*
* The method is taken from:
* http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl,
felem_shrink(z3, felem_z3);
}
-/* Base point pre computation
+/*-
+ * Base point pre computation
* --------------------------
*
* Two different sorts of precomputed tables are used in the following code.
{0x501e82885bc98cda, 0x41ef80e5d046ac04, 0x557d9f49461210fb, 0x4ab5b6b2b8753f81},
{1, 0, 0, 0}}}};
-/* select_point selects the |index|th point from a precomputation table and
+/* select_point selects the |idx|th point from a precomputation table and
* copies it to out. */
-static void select_point(const u64 index, unsigned int size, const smallfelem pre_comp[16][3], smallfelem out[3])
+static void select_point(const u64 idx, unsigned int size, const smallfelem pre_comp[16][3], smallfelem out[3])
{
unsigned i, j;
u64 *outlimbs = &out[0][0];
for (i = 0; i < size; i++)
{
const u64 *inlimbs = (u64*) &pre_comp[i][0][0];
- u64 mask = i ^ index;
+ u64 mask = i ^ idx;
mask |= mask >> 4;
mask |= mask >> 2;
mask |= mask >> 1;
ec_GFp_simple_get_Jprojective_coordinates_GFp,
ec_GFp_simple_point_set_affine_coordinates,
ec_GFp_nistp256_point_get_affine_coordinates,
- 0 /* point_set_compressed_coordinates */,
- 0 /* point2oct */,
- 0 /* oct2point */,
+ 0 /* point_set_compressed_coordinates */,
+ 0 /* point2oct */,
+ 0 /* oct2point */,
ec_GFp_simple_add,
ec_GFp_simple_dbl,
ec_GFp_simple_invert,
felem_contract(y_out, y_in);
if (y != NULL)
{
- if (!smallfelem_to_BN(y, y_out)) {
- ECerr(EC_F_EC_GFP_NISTP256_POINT_GET_AFFINE_COORDINATES,
- ERR_R_BN_LIB);
- return 0;
- }
+ if (!smallfelem_to_BN(y, y_out))
+ {
+ ECerr(EC_F_EC_GFP_NISTP256_POINT_GET_AFFINE_COORDINATES,
+ ERR_R_BN_LIB);
+ return 0;
+ }
}
return 1;
}
-static void make_points_affine(size_t num, smallfelem points[num][3], smallfelem tmp_smallfelems[num+1])
+static void make_points_affine(size_t num, smallfelem points[/* num */][3], smallfelem tmp_smallfelems[/* num+1 */])
{
/* Runs in constant time, unless an input is the point at infinity
* (which normally shouldn't happen). */
projects / openssl.git / blobdiff