crypto/limbs/limbs.c

/* Copyright 2016-2017 Brian Smith.
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */

#include "limbs.h"

#include "../internal.h"
#include "../fipsmodule/bn/internal.h"
#include "limbs.inl"


/* XXX: We assume that the conversion from |Carry| to |Limb| is constant-time,
 * but we haven't verified that assumption. TODO: Fix it so we don't need to
 * make that assumption. */

/* Returns 0xfff..f if |a| is all zero limbs, and zero otherwise. |num_limbs|
 * may be zero. */
Limb LIMBS_are_zero(const Limb a[], size_t num_limbs) {
  Limb is_zero = CONSTTIME_TRUE_W;
  for (size_t i = 0; i < num_limbs; ++i) {
    is_zero = constant_time_select_w(is_zero, constant_time_is_zero_w(a[i]),
                                     is_zero);
  }
  return is_zero;
}

/* Returns 0xffff..f if |a == b|, and zero otherwise. |num_limbs| may be zero. */
Limb LIMBS_equal(const Limb a[], const Limb b[], size_t num_limbs) {
  Limb eq = CONSTTIME_TRUE_W;
  for (size_t i = 0; i < num_limbs; ++i) {
    eq = constant_time_select_w(eq, constant_time_eq_w(a[i], b[i]), eq);
  }
  return eq;
}

/* Returns 0xffff..f if |a == b|, and zero otherwise. |num_limbs| may be zero. */
Limb LIMBS_equal_limb(const Limb a[], Limb b, size_t num_limbs) {
  if (num_limbs == 0) {
    return constant_time_is_zero_w(b);
  }
  debug_assert_nonsecret(num_limbs >= 1);
  Limb lo_equal = constant_time_eq_w(a[0], b);
  Limb hi_zero = LIMBS_are_zero(&a[1], num_limbs - 1);
  return constant_time_select_w(lo_equal, hi_zero, 0);
}

/* Returns 0xfff..f if |a| is all zero limbs, and zero otherwise.
 * |num_limbs| may be zero. */
Limb LIMBS_are_even(const Limb a[], size_t num_limbs) {
  Limb lo;
  if (num_limbs == 0) {
    lo = 0;
  } else {
    lo = a[0];
  }
  return constant_time_is_zero_w(lo & 1);
}

/* Returns 0xffff...f if |a| is less than |b|, and zero otherwise. */
Limb LIMBS_less_than(const Limb a[], const Limb b[], size_t num_limbs) {
  debug_assert_nonsecret(num_limbs >= 1);
  /* There are lots of ways to implement this. It is implemented this way to
   * be consistent with |LIMBS_limbs_reduce_once| and other code that makes such
   * comparisons as part of doing conditional reductions. */
  Limb dummy;
  Carry borrow = limb_sub(&dummy, a[0], b[0]);
  for (size_t i = 1; i < num_limbs; ++i) {
    borrow = limb_sbb(&dummy, a[i], b[i], borrow);
  }
  return constant_time_is_nonzero_w(borrow);
}

Limb LIMBS_less_than_limb(const Limb a[], Limb b, size_t num_limbs) {
  debug_assert_nonsecret(num_limbs >= 1);

  Limb dummy;
  Limb lo = constant_time_is_nonzero_w(limb_sub(&dummy, a[0], b));
  Limb hi = LIMBS_are_zero(&a[1], num_limbs - 1);
  return constant_time_select_w(lo, hi, lo);
}

/* if (r >= m) { r -= m; } */
void LIMBS_reduce_once(Limb r[], const Limb m[], size_t num_limbs) {
  debug_assert_nonsecret(num_limbs >= 1);
  /* This could be done more efficiently if we had |num_limbs| of extra space
   * available, by storing |r - m| and then doing a conditional copy of either
   * |r| or |r - m|. But, in order to operate in constant space, with an eye
   * towards this function being used in RSA in the future, we do things a
   * slightly less efficient way. */
  Limb lt = LIMBS_less_than(r, m, num_limbs);
  Carry borrow =
      limb_sub(&r[0], r[0], constant_time_select_w(lt, 0, m[0]));
  for (size_t i = 1; i < num_limbs; ++i) {
    /* XXX: This is probably particularly inefficient because the operations in
     * constant_time_select affect the carry flag, so there will likely be
     * loads and stores of |borrow|. */
    borrow =
        limb_sbb(&r[i], r[i], constant_time_select_w(lt, 0, m[i]), borrow);
  }
  dev_assert_secret(borrow == 0);
}

void LIMBS_add_mod(Limb r[], const Limb a[], const Limb b[], const Limb m[],
                   size_t num_limbs) {
  Limb overflow1 =
      constant_time_is_nonzero_w(limbs_add(r, a, b, num_limbs));
  Limb overflow2 = ~LIMBS_less_than(r, m, num_limbs);
  Limb overflow = overflow1 | overflow2;
  Carry borrow = limb_sub(&r[0], r[0], m[0] & overflow);
  for (size_t i = 1; i < num_limbs; ++i) {
    borrow = limb_sbb(&r[i], r[i], m[i] & overflow, borrow);
  }
}

void LIMBS_sub_mod(Limb r[], const Limb a[], const Limb b[], const Limb m[],
                   size_t num_limbs) {
  Limb underflow =
      constant_time_is_nonzero_w(limbs_sub(r, a, b, num_limbs));
  Carry carry = limb_add(&r[0], r[0], m[0] & underflow);
  for (size_t i = 1; i < num_limbs; ++i) {
    carry = limb_adc(&r[i], r[i], m[i] & underflow, carry);
  }
}

void LIMBS_shl_mod(Limb r[], const Limb a[], const Limb m[], size_t num_limbs) {
  Limb overflow1 =
      constant_time_is_nonzero_w(a[num_limbs - 1] & LIMB_HIGH_BIT);
  Limb carry = 0;
  for (size_t i = 0; i < num_limbs; ++i) {
    Limb limb = a[i];
    Limb new_carry = limb >> (LIMB_BITS - 1);
    r[i] = (limb << 1) | carry;
    carry = new_carry;
  }
  Limb overflow2 = ~LIMBS_less_than(r, m, num_limbs);
  Limb overflow = overflow1 | overflow2;
  Carry borrow = limb_sub(&r[0], r[0], m[0] & overflow);
  for (size_t i = 1; i < num_limbs; ++i) {
    borrow = limb_sbb(&r[i], r[i], m[i] & overflow, borrow);
  }
}

int LIMBS_select_512_32(Limb r[], const Limb table[], size_t num_limbs,
                        crypto_word index) {
  if (num_limbs % (512 / LIMB_BITS) != 0) {
    return 0;
  }
  limbs_select(r, table, num_limbs, 32, index);
  return 1;
}

static const Limb FIVE_BITS_MASK = 0x1f;

crypto_word LIMBS_window5_split_window(Limb lower_limb, Limb higher_limb, size_t index_within_word) {
  Limb high_bits = (higher_limb << (LIMB_BITS - index_within_word))
    & FIVE_BITS_MASK;
  // There are no bits outside the window above |index_within_word| (if there
  // were then this wouldn't be a split window), so we don't need to mask
  // |low_bits|.
  Limb low_bits = lower_limb >> index_within_word;
  return low_bits | high_bits;
}

crypto_word LIMBS_window5_unsplit_window(Limb limb, size_t index_within_word) {
  return (limb >> index_within_word) & FIVE_BITS_MASK;
}

Limb LIMB_shr(Limb a, size_t shift) {
  return a >> shift;
}

Limb GFp_limbs_mul_add_limb(Limb r[], const Limb a[], Limb b, size_t num_limbs) {
  Limb carried = 0;
  for (size_t i = 0; i < num_limbs; ++i) {
    Limb lo;
    Limb hi;
    bn_umult_lohi(&lo, &hi, a[i], b);
    Limb tmp;
    Carry c = limb_add(&tmp, lo, carried);
    c = limb_adc(&carried, hi, 0, c);
    dev_assert_secret(c == 0);
    c = limb_add(&r[i], r[i], tmp);
    c = limb_adc(&carried, carried, 0, c);
    // (A * B) + C + D never carries.
    dev_assert_secret(c == 0);
  }
  return carried;
}