Switch HRSS inversion algorithm.
This algorithm is much simplier and more obvious than the one from the
HRSS paper. Unfortunately it's not immediately any faster (roughly a
no-op on most platforms, +5% on ARM) but it does allow a bunch of
constant-time rotation code to be deleted.
Since it's simplier, however, it's easier to speed-up a little with
future changes.
Change-Id: Ic0e92c77c44ea9aeb6fe35940af9767084fe5f58
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/39084
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/hrss/hrss.c b/crypto/hrss/hrss.c
index 0f66e97..67ff4c1 100644
--- a/crypto/hrss/hrss.c
+++ b/crypto/hrss/hrss.c
@@ -51,8 +51,8 @@
// SXY: https://eprint.iacr.org/2017/1005.pdf
// NTRUTN14:
// https://assets.onboardsecurity.com/static/downloads/NTRU/resources/NTRUTech014.pdf
-// NTRUCOMP:
-// https://eprint.iacr.org/2018/1174
+// NTRUCOMP: https://eprint.iacr.org/2018/1174
+// SAFEGCD: https://gcd.cr.yp.to/papers.html#safegcd
// Vector operations.
@@ -184,13 +184,6 @@
0b01010101);
}
-// vec_broadcast_bit15 duplicates the most-significant bit of the first word in
-// |a| to all bits in a vector and returns the result.
-static inline vec_t vec_broadcast_bit15(vec_t a) {
- return _mm_shuffle_epi32(_mm_srai_epi32(_mm_slli_epi64(a, 63 - 15), 31),
- 0b01010101);
-}
-
// vec_get_word returns the |i|th uint16_t in |v|. (This is a macro because the
// compiler requires that |i| be a compile-time constant.)
#define vec_get_word(v, i) _mm_extract_epi16(v, i)
@@ -246,11 +239,6 @@
return vdupq_lane_u16(vget_low_u16(a), 0);
}
-static inline vec_t vec_broadcast_bit15(vec_t a) {
- a = (vec_t)vshrq_n_s16((int16x8_t)a, 15);
- return vdupq_lane_u16(vget_low_u16(a), 0);
-}
-
static inline void poly3_vec_lshift1(vec_t a_s[6], vec_t a_a[6]) {
vec_t carry_s = {0};
vec_t carry_a = {0};
@@ -324,99 +312,64 @@
OPENSSL_memset(&p->v[0], 0, sizeof(crypto_word_t) * WORDS_PER_POLY);
}
-// poly2_cmov sets |out| to |in| iff |mov| is all ones.
-static void poly2_cmov(struct poly2 *out, const struct poly2 *in,
- crypto_word_t mov) {
+// word_reverse returns |in| with the bits in reverse order.
+static crypto_word_t word_reverse(crypto_word_t in) {
+#if defined(OPENSSL_64_BIT)
+ static const crypto_word_t kMasks[6] = {
+ UINT64_C(0x5555555555555555),
+ UINT64_C(0x3333333333333333),
+ UINT64_C(0x0f0f0f0f0f0f0f0f),
+ UINT64_C(0x00ff00ff00ff00ff),
+ UINT64_C(0x0000ffff0000ffff),
+ UINT64_C(0x00000000ffffffff),
+ };
+#else
+ static const crypto_word_t kMasks[5] = {
+ 0x55555555,
+ 0x33333333,
+ 0x0f0f0f0f,
+ 0x00ff00ff,
+ 0x0000ffff,
+ };
+#endif
+
+ for (size_t i = 0; i < OPENSSL_ARRAY_SIZE(kMasks); i++) {
+ in = ((in >> (1 << i)) & kMasks[i]) | ((in & kMasks[i]) << (1 << i));
+ }
+
+ return in;
+}
+
+// lsb_to_all replicates the least-significant bit of |v| to all bits of the
+// word. This is used in bit-slicing operations to make a vector from a fixed
+// value.
+static crypto_word_t lsb_to_all(crypto_word_t v) { return 0u - (v & 1); }
+
+// poly2_mod_phiN reduces |p| by Φ(N).
+static void poly2_mod_phiN(struct poly2 *p) {
+ // m is the term at x^700, replicated to every bit.
+ const crypto_word_t m =
+ lsb_to_all(p->v[WORDS_PER_POLY - 1] >> (BITS_IN_LAST_WORD - 1));
for (size_t i = 0; i < WORDS_PER_POLY; i++) {
- out->v[i] = (out->v[i] & ~mov) | (in->v[i] & mov);
+ p->v[i] ^= m;
}
+ p->v[WORDS_PER_POLY - 1] &= (UINT64_C(1) << (BITS_IN_LAST_WORD - 1)) - 1;
}
-// poly2_rotr_words performs a right-rotate on |in|, writing the result to
-// |out|. The shift count, |bits|, must be a non-zero multiple of the word size.
-static void poly2_rotr_words(struct poly2 *out, const struct poly2 *in,
- size_t bits) {
- assert(bits >= BITS_PER_WORD && bits % BITS_PER_WORD == 0);
- assert(out != in);
-
- const size_t start = bits / BITS_PER_WORD;
- const size_t n = (N - bits) / BITS_PER_WORD;
-
- // The rotate is by a whole number of words so the first few words are easy:
- // just move them down.
- for (size_t i = 0; i < n; i++) {
- out->v[i] = in->v[start + i];
+// poly2_reverse_700 reverses the order of the first 700 bits of |in| and writes
+// the result to |out|.
+static void poly2_reverse_700(struct poly2 *out, const struct poly2 *in) {
+ struct poly2 t;
+ for (size_t i = 0; i < WORDS_PER_POLY; i++) {
+ t.v[i] = word_reverse(in->v[i]);
}
- // Since the last word is only partially filled, however, the remainder needs
- // shifting and merging of words to take care of that.
- crypto_word_t carry = in->v[WORDS_PER_POLY - 1];
-
- for (size_t i = 0; i < start; i++) {
- out->v[n + i] = carry | in->v[i] << BITS_IN_LAST_WORD;
- carry = in->v[i] >> (BITS_PER_WORD - BITS_IN_LAST_WORD);
+ static const size_t shift = BITS_PER_WORD - ((N-1) % BITS_PER_WORD);
+ for (size_t i = 0; i < WORDS_PER_POLY-1; i++) {
+ out->v[i] = t.v[WORDS_PER_POLY-1-i] >> shift;
+ out->v[i] |= t.v[WORDS_PER_POLY-2-i] << (BITS_PER_WORD - shift);
}
-
- out->v[WORDS_PER_POLY - 1] = carry;
-}
-
-// poly2_rotr_bits performs a right-rotate on |in|, writing the result to |out|.
-// The shift count, |bits|, must be a power of two that is less than
-// |BITS_PER_WORD|.
-static void poly2_rotr_bits(struct poly2 *out, const struct poly2 *in,
- size_t bits) {
- assert(bits <= BITS_PER_WORD / 2);
- assert(bits != 0);
- assert((bits & (bits - 1)) == 0);
- assert(out != in);
-
- // BITS_PER_WORD/2 is the greatest legal value of |bits|. If
- // |BITS_IN_LAST_WORD| is smaller than this then the code below doesn't work
- // because more than the last word needs to carry down in the previous one and
- // so on.
- OPENSSL_STATIC_ASSERT(
- BITS_IN_LAST_WORD >= BITS_PER_WORD / 2,
- "there are more carry bits than fit in BITS_IN_LAST_WORD");
-
- crypto_word_t carry = in->v[WORDS_PER_POLY - 1] << (BITS_PER_WORD - bits);
-
- for (size_t i = WORDS_PER_POLY - 2; i < WORDS_PER_POLY; i--) {
- out->v[i] = carry | in->v[i] >> bits;
- carry = in->v[i] << (BITS_PER_WORD - bits);
- }
-
- crypto_word_t last_word = carry >> (BITS_PER_WORD - BITS_IN_LAST_WORD) |
- in->v[WORDS_PER_POLY - 1] >> bits;
- last_word &= (UINT64_C(1) << BITS_IN_LAST_WORD) - 1;
- out->v[WORDS_PER_POLY - 1] = last_word;
-}
-
-// HRSS_poly2_rotr_consttime right-rotates |p| by |bits| in constant-time.
-void HRSS_poly2_rotr_consttime(struct poly2 *p, size_t bits) {
- assert(bits <= N);
- assert(p->v[WORDS_PER_POLY-1] >> BITS_IN_LAST_WORD == 0);
-
- // Constant-time rotation is implemented by calculating the rotations of
- // powers-of-two bits and throwing away the unneeded values. 2^9 (i.e. 512) is
- // the largest power-of-two shift that we need to consider because 2^10 > N.
-#define HRSS_POLY2_MAX_SHIFT 9
- size_t shift = HRSS_POLY2_MAX_SHIFT;
- OPENSSL_STATIC_ASSERT((1 << (HRSS_POLY2_MAX_SHIFT + 1)) > N,
- "maximum shift is too small");
- OPENSSL_STATIC_ASSERT((1 << HRSS_POLY2_MAX_SHIFT) <= N,
- "maximum shift is too large");
- struct poly2 shifted;
-
- for (; (UINT64_C(1) << shift) >= BITS_PER_WORD; shift--) {
- poly2_rotr_words(&shifted, p, UINT64_C(1) << shift);
- poly2_cmov(p, &shifted, ~((1 & (bits >> shift)) - 1));
- }
-
- for (; shift < HRSS_POLY2_MAX_SHIFT; shift--) {
- poly2_rotr_bits(&shifted, p, UINT64_C(1) << shift);
- poly2_cmov(p, &shifted, ~((1 & (bits >> shift)) - 1));
- }
-#undef HRSS_POLY2_MAX_SHIFT
+ out->v[WORDS_PER_POLY-1] = t.v[0] >> shift;
}
// poly2_cswap exchanges the values of |a| and |b| if |swap| is all ones.
@@ -537,7 +490,14 @@
poly2_zero(&p->a);
}
-// poly3_word_mul sets (|out_s|, |out_a) to (|s1|, |a1|) × (|s2|, |a2|).
+// poly3_reverse_700 reverses the order of the first 700 terms of |in| and
+// writes them to |out|.
+static void poly3_reverse_700(struct poly3 *out, const struct poly3 *in) {
+ poly2_reverse_700(&out->a, &in->a);
+ poly2_reverse_700(&out->s, &in->s);
+}
+
+// poly3_word_mul sets (|out_s|, |out_a|) to (|s1|, |a1|) × (|s2|, |a2|).
static void poly3_word_mul(crypto_word_t *out_s, crypto_word_t *out_a,
const crypto_word_t s1, const crypto_word_t a1,
const crypto_word_t s2, const crypto_word_t a2) {
@@ -563,11 +523,6 @@
*out_a = t | (s1 ^ s2);
}
-// lsb_to_all replicates the least-significant bit of |v| to all bits of the
-// word. This is used in bit-slicing operations to make a vector from a fixed
-// value.
-static crypto_word_t lsb_to_all(crypto_word_t v) { return 0u - (v & 1); }
-
// poly3_mul_const sets |p| to |p|×m, where m = (ms, ma).
static void poly3_mul_const(struct poly3 *p, crypto_word_t ms,
crypto_word_t ma) {
@@ -579,13 +534,6 @@
}
}
-// poly3_rotr_consttime right-rotates |p| by |bits| in constant-time.
-static void poly3_rotr_consttime(struct poly3 *p, size_t bits) {
- assert(bits <= N);
- HRSS_poly2_rotr_consttime(&p->s, bits);
- HRSS_poly2_rotr_consttime(&p->a, bits);
-}
-
// poly3_fmadd sets |out| to |out| - |in|×m, where m is (ms, ma).
static void poly3_fmsub(struct poly3 *RESTRICT out,
const struct poly3 *RESTRICT in, crypto_word_t ms,
@@ -828,83 +776,64 @@
// poly3_invert_vec sets |*out| to |in|^-1, i.e. such that |out|×|in| == 1 mod
// Φ(N).
static void poly3_invert_vec(struct poly3 *out, const struct poly3 *in) {
- // See the comment in |HRSS_poly3_invert| about this algorithm. In addition to
- // the changes described there, this implementation attempts to use vector
- // registers to speed up the computation. Even non-poly3 variables are held in
- // vectors where possible to minimise the amount of data movement between
- // the vector and general-purpose registers.
-
- vec_t b_s[6], b_a[6], c_s[6], c_a[6], f_s[6], f_a[6], g_s[6], g_a[6];
+ // This algorithm is taken from section 7.1 of [SAFEGCD].
const vec_t kZero = {0};
const vec_t kOne = {1};
- static const uint8_t kOneBytes[sizeof(vec_t)] = {1};
static const uint8_t kBottomSixtyOne[sizeof(vec_t)] = {
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x1f};
- memset(b_s, 0, sizeof(b_s));
- memcpy(b_a, kOneBytes, sizeof(kOneBytes));
- memset(&b_a[1], 0, 5 * sizeof(vec_t));
+ vec_t v_s[6], v_a[6], r_s[6], r_a[6], f_s[6], f_a[6], g_s[6], g_a[6];
+ // v = 0
+ memset(&v_s, 0, sizeof(v_s));
+ memset(&v_a, 0, sizeof(v_a));
+ // r = 1
+ memset(&r_s, 0, sizeof(r_s));
+ memset(&r_a, 0, sizeof(r_a));
+ r_a[0] = kOne;
+ // f = all ones.
+ memset(f_s, 0, sizeof(f_s));
+ memset(f_a, 0xff, 5 * sizeof(vec_t));
+ memcpy(&f_a[5], kBottomSixtyOne, sizeof(kBottomSixtyOne));
+ // g is the reversal of |in|.
+ struct poly3 in_reversed;
+ poly3_reverse_700(&in_reversed, in);
+ g_s[5] = kZero;
+ memcpy(&g_s, &in_reversed.s.v, WORDS_PER_POLY * sizeof(crypto_word_t));
+ g_a[5] = kZero;
+ memcpy(&g_a, &in_reversed.a.v, WORDS_PER_POLY * sizeof(crypto_word_t));
- memset(c_s, 0, sizeof(c_s));
- memset(c_a, 0, sizeof(c_a));
+ int delta = 1;
- f_s[5] = kZero;
- memcpy(f_s, in->s.v, WORDS_PER_POLY * sizeof(crypto_word_t));
- f_a[5] = kZero;
- memcpy(f_a, in->a.v, WORDS_PER_POLY * sizeof(crypto_word_t));
+ for (size_t i = 0; i < (2*(N-1)) - 1; i++) {
+ poly3_vec_lshift1(v_s, v_a);
- // Set g to all ones.
- memset(g_s, 0, sizeof(g_s));
- memset(g_a, 0xff, 5 * sizeof(vec_t));
- memcpy(&g_a[5], kBottomSixtyOne, sizeof(kBottomSixtyOne));
+ const crypto_word_t delta_sign_bit = (delta >> (sizeof(delta) * 8 - 1)) & 1;
+ const crypto_word_t delta_is_non_negative = delta_sign_bit - 1;
+ const crypto_word_t delta_is_non_zero = ~constant_time_is_zero_w(delta);
+ const vec_t g_has_constant_term = vec_broadcast_bit(g_a[0]);
+ const vec_t mask_w =
+ {delta_is_non_negative & delta_is_non_zero};
+ const vec_t mask = vec_broadcast_bit(mask_w) & g_has_constant_term;
- vec_t deg_f = {N - 1}, deg_g = {N - 1}, rotation = kZero;
- vec_t k = kOne;
- vec_t f0s = {0}, f0a = {0};
- vec_t still_going;
- memset(&still_going, 0xff, sizeof(still_going));
+ const vec_t c_a = vec_broadcast_bit(f_a[0] & g_a[0]);
+ const vec_t c_s = vec_broadcast_bit((f_s[0] ^ g_s[0]) & c_a);
- for (unsigned i = 0; i < 2 * (N - 1) - 1; i++) {
- const vec_t s_a = vec_broadcast_bit(still_going & (f_a[0] & g_a[0]));
- const vec_t s_s =
- vec_broadcast_bit(still_going & ((f_s[0] ^ g_s[0]) & s_a));
- const vec_t should_swap =
- (s_s | s_a) & vec_broadcast_bit15(deg_f - deg_g);
+ delta = constant_time_select_int(lsb_to_all(mask[0]), -delta, delta);
+ delta++;
- poly3_vec_cswap(f_s, f_a, g_s, g_a, should_swap);
- poly3_vec_fmsub(f_s, f_a, g_s, g_a, s_s, s_a);
- poly3_vec_rshift1(f_s, f_a);
+ poly3_vec_cswap(f_s, f_a, g_s, g_a, mask);
+ poly3_vec_fmsub(g_s, g_a, f_s, f_a, c_s, c_a);
+ poly3_vec_rshift1(g_s, g_a);
- poly3_vec_cswap(b_s, b_a, c_s, c_a, should_swap);
- poly3_vec_fmsub(b_s, b_a, c_s, c_a, s_s, s_a);
- poly3_vec_lshift1(c_s, c_a);
-
- const vec_t deg_sum = should_swap & (deg_f ^ deg_g);
- deg_f ^= deg_sum;
- deg_g ^= deg_sum;
-
- deg_f -= kOne;
- still_going &= ~vec_broadcast_bit15(deg_f - kOne);
-
- const vec_t f0_is_nonzero = vec_broadcast_bit(f_s[0] | f_a[0]);
- // |f0_is_nonzero| implies |still_going|.
- rotation ^= f0_is_nonzero & (k ^ rotation);
- k += kOne;
-
- const vec_t f0s_sum = f0_is_nonzero & (f_s[0] ^ f0s);
- f0s ^= f0s_sum;
- const vec_t f0a_sum = f0_is_nonzero & (f_a[0] ^ f0a);
- f0a ^= f0a_sum;
+ poly3_vec_cswap(v_s, v_a, r_s, r_a, mask);
+ poly3_vec_fmsub(r_s, r_a, v_s, v_a, c_s, c_a);
}
- crypto_word_t rotation_word = vec_get_word(rotation, 0);
- rotation_word -= N & constant_time_lt_w(N, rotation_word);
- memcpy(out->s.v, b_s, WORDS_PER_POLY * sizeof(crypto_word_t));
- memcpy(out->a.v, b_a, WORDS_PER_POLY * sizeof(crypto_word_t));
- assert(poly3_top_bits_are_clear(out));
- poly3_rotr_consttime(out, rotation_word);
- poly3_mul_const(out, vec_get_word(f0s, 0), vec_get_word(f0a, 0));
- poly3_mod_phiN(out);
+ assert(delta == 0);
+ memcpy(out->s.v, v_s, WORDS_PER_POLY * sizeof(crypto_word_t));
+ memcpy(out->a.v, v_a, WORDS_PER_POLY * sizeof(crypto_word_t));
+ poly3_mul_const(out, vec_get_word(f_s[0], 0), vec_get_word(f_a[0], 0));
+ poly3_reverse_700(out, out);
}
#endif // HRSS_HAVE_VECTOR_UNIT
@@ -921,71 +850,50 @@
}
#endif
- // This algorithm mostly follows algorithm 10 in the paper. Some changes:
- // 1) k should start at zero, not one. In the code below k is omitted and
- // the loop counter, |i|, is used instead.
- // 2) The rotation count is conditionally updated to handle trailing zero
- // coefficients.
- // The best explanation for why it works is in the "Why it works" section of
- // [NTRUTN14].
+ // This algorithm is taken from section 7.1 of [SAFEGCD].
+ struct poly3 v, r, f, g;
+ // v = 0
+ poly3_zero(&v);
+ // r = 1
+ poly3_zero(&r);
+ r.a.v[0] = 1;
+ // f = all ones.
+ OPENSSL_memset(&f.s, 0, sizeof(struct poly2));
+ OPENSSL_memset(&f.a, 0xff, sizeof(struct poly2));
+ f.a.v[WORDS_PER_POLY - 1] >>= BITS_PER_WORD - BITS_IN_LAST_WORD;
+ // g is the reversal of |in|.
+ poly3_reverse_700(&g, in);
+ int delta = 1;
- struct poly3 c, f, g;
- OPENSSL_memcpy(&f, in, sizeof(f));
+ for (size_t i = 0; i < (2*(N-1)) - 1; i++) {
+ poly3_lshift1(&v);
- // Set g to all ones.
- OPENSSL_memset(&g.s, 0, sizeof(struct poly2));
- OPENSSL_memset(&g.a, 0xff, sizeof(struct poly2));
- g.a.v[WORDS_PER_POLY - 1] >>= BITS_PER_WORD - BITS_IN_LAST_WORD;
+ const crypto_word_t delta_sign_bit = (delta >> (sizeof(delta) * 8 - 1)) & 1;
+ const crypto_word_t delta_is_non_negative = delta_sign_bit - 1;
+ const crypto_word_t delta_is_non_zero = ~constant_time_is_zero_w(delta);
+ const crypto_word_t g_has_constant_term = lsb_to_all(g.a.v[0]);
+ const crypto_word_t mask =
+ g_has_constant_term & delta_is_non_negative & delta_is_non_zero;
- struct poly3 *b = out;
- poly3_zero(b);
- poly3_zero(&c);
- // Set b to one.
- b->a.v[0] = 1;
+ crypto_word_t c_s, c_a;
+ poly3_word_mul(&c_s, &c_a, f.s.v[0], f.a.v[0], g.s.v[0], g.a.v[0]);
+ c_s = lsb_to_all(c_s);
+ c_a = lsb_to_all(c_a);
- crypto_word_t deg_f = N - 1, deg_g = N - 1, rotation = 0;
- crypto_word_t f0s = 0, f0a = 0;
- crypto_word_t still_going = CONSTTIME_TRUE_W;
+ delta = constant_time_select_int(mask, -delta, delta);
+ delta++;
- for (unsigned i = 0; i < 2 * (N - 1) - 1; i++) {
- const crypto_word_t s_a = lsb_to_all(
- still_going & (f.a.v[0] & g.a.v[0]));
- const crypto_word_t s_s = lsb_to_all(
- still_going & ((f.s.v[0] ^ g.s.v[0]) & s_a));
- const crypto_word_t should_swap =
- (s_s | s_a) & constant_time_lt_w(deg_f, deg_g);
+ poly3_cswap(&f, &g, mask);
+ poly3_fmsub(&g, &f, c_s, c_a);
+ poly3_rshift1(&g);
- poly3_cswap(&f, &g, should_swap);
- poly3_cswap(b, &c, should_swap);
-
- const crypto_word_t deg_sum = should_swap & (deg_f ^ deg_g);
- deg_f ^= deg_sum;
- deg_g ^= deg_sum;
- assert(deg_g >= 1);
-
- poly3_fmsub(&f, &g, s_s, s_a);
- poly3_fmsub(b, &c, s_s, s_a);
- poly3_rshift1(&f);
- poly3_lshift1(&c);
-
- deg_f--;
- const crypto_word_t f0_is_nonzero =
- lsb_to_all(f.s.v[0]) | lsb_to_all(f.a.v[0]);
- // |f0_is_nonzero| implies |still_going|.
- assert(!(f0_is_nonzero && !still_going));
- still_going &= ~constant_time_is_zero_w(deg_f);
-
- rotation = constant_time_select_w(f0_is_nonzero, i, rotation);
- f0s = constant_time_select_w(f0_is_nonzero, f.s.v[0], f0s);
- f0a = constant_time_select_w(f0_is_nonzero, f.a.v[0], f0a);
+ poly3_cswap(&v, &r, mask);
+ poly3_fmsub(&r, &v, c_s, c_a);
}
- rotation++;
- rotation -= N & constant_time_lt_w(N, rotation);
- assert(poly3_top_bits_are_clear(out));
- poly3_rotr_consttime(out, rotation);
- poly3_mul_const(out, f0s, f0a);
- poly3_mod_phiN(out);
+ assert(delta == 0);
+ poly3_mul_const(&v, f.s.v[0], f.a.v[0]);
+ poly3_reverse_700(out, &v);
}
// Polynomials in Q.
@@ -1593,52 +1501,50 @@
// Φ(N)), all mod 2. This isn't useful in itself, but is part of doing inversion
// mod Q.
static void poly_invert_mod2(struct poly *out, const struct poly *in) {
- // This algorithm follows algorithm 10 in the paper. (Although, in contrast to
- // the paper, k should start at zero, not one, and the rotation count is needs
- // to handle trailing zero coefficients.) The best explanation for why it
- // works is in the "Why it works" section of [NTRUTN14].
+ // This algorithm is taken from section 7.1 of [SAFEGCD].
+ struct poly2 v, r, f, g;
- struct poly2 b, c, f, g;
- poly2_from_poly(&f, in);
- OPENSSL_memset(&b, 0, sizeof(b));
- b.v[0] = 1;
- OPENSSL_memset(&c, 0, sizeof(c));
+ // v = 0
+ poly2_zero(&v);
+ // r = 1
+ poly2_zero(&r);
+ r.v[0] = 1;
+ // f = all ones.
+ OPENSSL_memset(&f, 0xff, sizeof(struct poly2));
+ f.v[WORDS_PER_POLY - 1] >>= BITS_PER_WORD - BITS_IN_LAST_WORD;
+ // g is the reversal of |in|.
+ poly2_from_poly(&g, in);
+ poly2_mod_phiN(&g);
+ poly2_reverse_700(&g, &g);
+ int delta = 1;
- // Set g to all ones.
- OPENSSL_memset(&g, 0xff, sizeof(struct poly2));
- g.v[WORDS_PER_POLY - 1] >>= BITS_PER_WORD - BITS_IN_LAST_WORD;
+ for (size_t i = 0; i < (2*(N-1)) - 1; i++) {
+ poly2_lshift1(&v);
- crypto_word_t deg_f = N - 1, deg_g = N - 1, rotation = 0;
- crypto_word_t still_going = CONSTTIME_TRUE_W;
+ const crypto_word_t delta_sign_bit = (delta >> (sizeof(delta) * 8 - 1)) & 1;
+ const crypto_word_t delta_is_non_negative = delta_sign_bit - 1;
+ const crypto_word_t delta_is_non_zero = ~constant_time_is_zero_w(delta);
+ const crypto_word_t g_has_constant_term = lsb_to_all(g.v[0]);
+ const crypto_word_t mask =
+ g_has_constant_term & delta_is_non_negative & delta_is_non_zero;
- for (unsigned i = 0; i < 2 * (N - 1) - 1; i++) {
- const crypto_word_t s = still_going & lsb_to_all(f.v[0]);
- const crypto_word_t should_swap = s & constant_time_lt_w(deg_f, deg_g);
- poly2_cswap(&f, &g, should_swap);
- poly2_cswap(&b, &c, should_swap);
- const crypto_word_t deg_sum = should_swap & (deg_f ^ deg_g);
- deg_f ^= deg_sum;
- deg_g ^= deg_sum;
- assert(deg_g >= 1);
- poly2_fmadd(&f, &g, s);
- poly2_fmadd(&b, &c, s);
+ const crypto_word_t c = lsb_to_all(f.v[0] & g.v[0]);
- poly2_rshift1(&f);
- poly2_lshift1(&c);
+ delta = constant_time_select_int(mask, -delta, delta);
+ delta++;
- deg_f--;
- const crypto_word_t f0_is_nonzero = lsb_to_all(f.v[0]);
- // |f0_is_nonzero| implies |still_going|.
- assert(!(f0_is_nonzero && !still_going));
- rotation = constant_time_select_w(f0_is_nonzero, i, rotation);
- still_going &= ~constant_time_is_zero_w(deg_f);
+ poly2_cswap(&f, &g, mask);
+ poly2_fmadd(&g, &f, c);
+ poly2_rshift1(&g);
+
+ poly2_cswap(&v, &r, mask);
+ poly2_fmadd(&r, &v, c);
}
- rotation++;
- rotation -= N & constant_time_lt_w(N, rotation);
- assert(poly2_top_bits_are_clear(&b));
- HRSS_poly2_rotr_consttime(&b, rotation);
- poly_from_poly2(out, &b);
+ assert(delta == 0);
+ assert(f.v[0] & 1);
+ poly2_reverse_700(&v, &v);
+ poly_from_poly2(out, &v);
}
// poly_invert sets |*out| to |in^-1| (i.e. such that |*out|×|in| = 1 mod Φ(N)).
diff --git a/crypto/hrss/hrss_test.cc b/crypto/hrss/hrss_test.cc
index 493255d..66b9047 100644
--- a/crypto/hrss/hrss_test.cc
+++ b/crypto/hrss/hrss_test.cc
@@ -22,59 +22,6 @@
#include "../test/test_util.h"
#include "internal.h"
-// poly2_from_bits takes the least-significant bit from each byte of |in| and
-// sets the bits of |*out| to match.
-static void poly2_from_bits(struct poly2 *out, const uint8_t in[N]) {
- crypto_word_t *words = out->v;
- unsigned shift = 0;
- crypto_word_t word = 0;
-
- for (unsigned i = 0; i < N; i++) {
- word >>= 1;
- word |= (crypto_word_t)(in[i] & 1) << (BITS_PER_WORD - 1);
- shift++;
-
- if (shift == BITS_PER_WORD) {
- *words = word;
- words++;
- word = 0;
- shift = 0;
- }
- }
-
- word >>= BITS_PER_WORD - shift;
- *words = word;
-}
-
-TEST(HRSS, Poly2RotateRight) {
- uint8_t bits[N];
- RAND_bytes(bits, sizeof(bits));
- for (size_t i = 0; i < N; i++) {
- bits[i] &= 1;
- };
-
- struct poly2 p, orig, shifted;
- poly2_from_bits(&p, bits);
- OPENSSL_memcpy(&orig, &p, sizeof(orig));
-
- // Test |HRSS_poly2_rotr_consttime| by manually rotating |bits| step-by-step
- // and testing every possible shift to ensure that it produces the correct
- // answer.
- for (size_t shift = 0; shift <= N; shift++) {
- SCOPED_TRACE(shift);
-
- OPENSSL_memcpy(&p, &orig, sizeof(orig));
- HRSS_poly2_rotr_consttime(&p, shift);
- poly2_from_bits(&shifted, bits);
- ASSERT_EQ(
- Bytes(reinterpret_cast<const uint8_t *>(&shifted), sizeof(shifted)),
- Bytes(reinterpret_cast<const uint8_t *>(&p), sizeof(p)));
-
- const uint8_t least_significant_bit = bits[0];
- OPENSSL_memmove(bits, &bits[1], N-1);
- bits[N-1] = least_significant_bit;
- }
-}
// poly3_rand sets |r| to a random value (albeit with bias).
static void poly3_rand(poly3 *p) {
@@ -101,6 +48,21 @@
memset(&inverse, 0, sizeof(inverse));
memset(&result, 0, sizeof(result));
+ p.s.v[0] = 0;
+ p.a.v[0] = 1;
+ for (size_t i = 0; i < N - 1; i++) {
+ SCOPED_TRACE(i);
+ poly3 r;
+ OPENSSL_memset(&r, 0, sizeof(r));
+ r.a.v[i / BITS_PER_WORD] = (UINT64_C(1) << (i % BITS_PER_WORD));
+ HRSS_poly3_invert(&inverse, &r);
+ HRSS_poly3_mul(&result, &inverse, &r);
+ // r×r⁻¹ = 1, and |p| contains 1.
+ EXPECT_EQ(
+ Bytes(reinterpret_cast<const uint8_t *>(&p), sizeof(p)),
+ Bytes(reinterpret_cast<const uint8_t *>(&result), sizeof(result)));
+ }
+
// The inverse of -1 is -1.
p.s.v[0] = 1;
p.a.v[0] = 1;
@@ -118,6 +80,10 @@
for (size_t i = 0; i < 500; i++) {
poly3 r;
poly3_rand(&r);
+ // Drop the term at x^700 because |HRSS_poly3_invert| only handles reduced
+ // inputs.
+ r.s.v[WORDS_PER_POLY - 1] &= (UINT64_C(1) << (BITS_IN_LAST_WORD - 1)) - 1;
+ r.a.v[WORDS_PER_POLY - 1] &= (UINT64_C(1) << (BITS_IN_LAST_WORD - 1)) - 1;
HRSS_poly3_invert(&inverse, &r);
HRSS_poly3_mul(&result, &inverse, &r);
// r×r⁻¹ = 1, and |p| contains 1.
@@ -132,6 +98,10 @@
// Φ(N).
poly3 r, inverse, result, one;
poly3_rand(&r);
+ // Drop the term at x^700 because |HRSS_poly3_invert| only handles reduced
+ // inputs.
+ r.s.v[WORDS_PER_POLY - 1] &= (UINT64_C(1) << (BITS_IN_LAST_WORD - 1)) - 1;
+ r.a.v[WORDS_PER_POLY - 1] &= (UINT64_C(1) << (BITS_IN_LAST_WORD - 1)) - 1;
HRSS_poly3_invert(&inverse, &r);
HRSS_poly3_mul(&result, &inverse, &r);
@@ -140,9 +110,8 @@
EXPECT_EQ(Bytes(reinterpret_cast<const uint8_t *>(&one), sizeof(one)),
Bytes(reinterpret_cast<const uint8_t *>(&result), sizeof(result)));
- // |r| is probably already not reduced mod Φ(N), but add x^701 - 1 and
- // recompute to ensure that we get the same answer. (Since (x^701 - 1) ≡ 0 mod
- // Φ(N).)
+ // |r| is reduced mod Φ(N), so add x^701 - 1 and recompute to ensure that we
+ // get the same answer. (Since (x^701 - 1) ≡ 0 mod Φ(N).)
poly3_word_add(&r.s.v[0], &r.a.v[0], 1, 1);
poly3_word_add(&r.s.v[WORDS_PER_POLY - 1], &r.a.v[WORDS_PER_POLY - 1], 0,
UINT64_C(1) << BITS_IN_LAST_WORD);
diff --git a/crypto/hrss/internal.h b/crypto/hrss/internal.h
index 7cfe010..c0d9bd2 100644
--- a/crypto/hrss/internal.h
+++ b/crypto/hrss/internal.h
@@ -36,7 +36,6 @@
struct poly2 s, a;
};
-OPENSSL_EXPORT void HRSS_poly2_rotr_consttime(struct poly2 *p, size_t bits);
OPENSSL_EXPORT void HRSS_poly3_mul(struct poly3 *out, const struct poly3 *x,
const struct poly3 *y);
OPENSSL_EXPORT void HRSS_poly3_invert(struct poly3 *out,
