/* Some common helpers useful for many algorithms */
#ifndef __COMMON_H__
#define __COMMON_H__
/* Include our arithmetic layer */
#include <libecc/libarith.h>
/* I2OSP and OS2IP internal primitives */
ATTRIBUTE_WARN_UNUSED_RET static inline int _i2osp(nn_src_t x, u8 *buf, u16 buflen)
{
int ret;
bitcnt_t blen;
/* Sanity checks */
MUST_HAVE((buf != NULL), ret, err);
ret = nn_check_initialized(x); EG(ret, err);
/* If x >= 256^xLen (the integer does not fit in the buffer),
* return an error.
*/
ret = nn_bitlen(x, &blen); EG(ret, err);
MUST_HAVE(((8 * buflen) >= blen), ret, err);
/* Export to the buffer */
ret = nn_export_to_buf(buf, buflen, x);
err:
return ret;
}
ATTRIBUTE_WARN_UNUSED_RET static inline int _os2ip(nn_t x, const u8 *buf, u16 buflen)
{
int ret;
/* We do not want to exceed our computation compatible
* size.
*/
MUST_HAVE((buflen <= NN_USABLE_MAX_BYTE_LEN), ret, err);
/* Import the NN */
ret = nn_init_from_buf(x, buf, buflen);
err:
return ret;
}
/* Reverses the endiannes of a buffer in place */
ATTRIBUTE_WARN_UNUSED_RET static inline int _reverse_endianness(u8 *buf, u16 buf_size)
{
u16 i;
u8 tmp;
int ret;
MUST_HAVE((buf != NULL), ret, err);
if(buf_size > 1){
for(i = 0; i < (buf_size / 2); i++){
tmp = buf[i];
buf[i] = buf[buf_size - 1 - i];
buf[buf_size - 1 - i] = tmp;
}
}
ret = 0;
err:
return ret;
}
/* Helper to fix the MSB of a scalar using the trick in
* https://eprint.iacr.org/2011/232.pdf
*
* We distinguish three situations:
* - The scalar m is < q (the order), in this case we compute:
* -
* | m' = m + (2 * q) if [log(k + q)] == [log(q)],
* | m' = m + q otherwise.
* -
* - The scalar m is >= q and < q**2, in this case we compute:
* -
* | m' = m + (2 * (q**2)) if [log(k + (q**2))] == [log(q**2)],
* | m' = m + (q**2) otherwise.
* -
* - The scalar m is >= (q**2), in this case m == m'
* We only deal with 0 <= m < (q**2) using the countermeasure. When m >= (q**2),
* we stick with m' = m, accepting MSB issues (not much can be done in this case
* anyways).
*/
ATTRIBUTE_WARN_UNUSED_RET static inline int _fix_scalar_msb(nn_src_t m, nn_src_t q, nn_t m_msb_fixed)
{
int ret, cmp;
/* _m_msb_fixed to handle aliasing */
nn q_square, _m_msb_fixed;
q_square.magic = _m_msb_fixed.magic = WORD(0);
/* Sanity checks */
ret = nn_check_initialized(m); EG(ret, err);
ret = nn_check_initialized(q); EG(ret, err);
ret = nn_check_initialized(m_msb_fixed); EG(ret, err);
ret = nn_init(&q_square, 0); EG(ret, err);
ret = nn_init(&_m_msb_fixed, 0); EG(ret, err);
/* First compute q**2 */
ret = nn_sqr(&q_square, q); EG(ret, err);
/* Then compute m' depending on m size */
ret = nn_cmp(m, q, &cmp); EG(ret, err);
if (cmp < 0){
bitcnt_t msb_bit_len, q_bitlen;
/* Case where m < q */
ret = nn_add(&_m_msb_fixed, m, q); EG(ret, err);
ret = nn_bitlen(&_m_msb_fixed, &msb_bit_len); EG(ret, err);
ret = nn_bitlen(q, &q_bitlen); EG(ret, err);
ret = nn_cnd_add((msb_bit_len == q_bitlen), m_msb_fixed,
&_m_msb_fixed, q); EG(ret, err);
} else {
ret = nn_cmp(m, &q_square, &cmp); EG(ret, err);
if (cmp < 0) {
bitcnt_t msb_bit_len, q_square_bitlen;
/* Case where m >= q and m < (q**2) */
ret = nn_add(&_m_msb_fixed, m, &q_square); EG(ret, err);
ret = nn_bitlen(&_m_msb_fixed, &msb_bit_len); EG(ret, err);
ret = nn_bitlen(&q_square, &q_square_bitlen); EG(ret, err);
ret = nn_cnd_add((msb_bit_len == q_square_bitlen),
m_msb_fixed, &_m_msb_fixed, &q_square); EG(ret, err);
} else {
/* Case where m >= (q**2) */
ret = nn_copy(m_msb_fixed, m); EG(ret, err);
}
}
err:
nn_uninit(&q_square);
nn_uninit(&_m_msb_fixed);
return ret;
}
/* Helper to blind the scalar.
* Compute m_blind = m + (b * q) where b is a random value modulo q.
* Aliasing is supported.
*/
ATTRIBUTE_WARN_UNUSED_RET static inline int _blind_scalar(nn_src_t m, nn_src_t q, nn_t m_blind)
{
int ret;
nn tmp;
tmp.magic = WORD(0);
/* Sanity checks */
ret = nn_check_initialized(m); EG(ret, err);
ret = nn_check_initialized(q); EG(ret, err);
ret = nn_check_initialized(m_blind); EG(ret, err);
ret = nn_get_random_mod(&tmp, q); EG(ret, err);
ret = nn_mul(&tmp, &tmp, q); EG(ret, err);
ret = nn_add(m_blind, &tmp, m);
err:
nn_uninit(&tmp);
return ret;
}
/*
* NOT constant time at all and not secure against side-channels. This is
* an internal function only used for DSA verification on public data.
*
* Compute (base ** exp) mod (mod) using a square and multiply algorithm.
* Internally, this computes Montgomery coefficients and uses the redc
* function.
*
* Returns 0 on success, -1 on error.
*/
ATTRIBUTE_WARN_UNUSED_RET static inline int _nn_mod_pow_insecure(nn_t out, nn_src_t base,
nn_src_t exp, nn_src_t mod)
{
int ret, isodd, cmp;
bitcnt_t explen;
u8 expbit;
nn r, r_square, _base, one;
word_t mpinv;
r.magic = r_square.magic = _base.magic = one.magic = WORD(0);
/* Aliasing is not supported for this internal helper */
MUST_HAVE((out != base) && (out != exp) && (out != mod), ret, err);
/* Check initializations */
ret = nn_check_initialized(base); EG(ret, err);
ret = nn_check_initialized(exp); EG(ret, err);
ret = nn_check_initialized(mod); EG(ret, err);
ret = nn_bitlen(exp, &explen); EG(ret, err);
/* Sanity check */
MUST_HAVE((explen > 0), ret, err);
/* Check that the modulo is indeed odd */
ret = nn_isodd(mod, &isodd); EG(ret, err);
MUST_HAVE(isodd, ret, err);
/* Compute the Montgomery coefficients */
ret = nn_compute_redc1_coefs(&r, &r_square, mod, &mpinv); EG(ret, err);
/* Reduce the base if necessary */
ret = nn_cmp(base, mod, &cmp); EG(ret, err);
if(cmp >= 0){
ret = nn_mod(&_base, base, mod); EG(ret, err);
}
else{
ret = nn_copy(&_base, base); EG(ret, err);
}
ret = nn_mul_redc1(&_base, &_base, &r_square, mod, mpinv); EG(ret, err);
ret = nn_copy(out, &r); EG(ret, err);
ret = nn_init(&one, 0); EG(ret, err);
ret = nn_one(&one); EG(ret, err);
while (explen > 0) {
explen = (bitcnt_t)(explen - 1);
/* Get the bit */
ret = nn_getbit(exp, explen, &expbit); EG(ret, err);
/* Square */
ret = nn_mul_redc1(out, out, out, mod, mpinv); EG(ret, err);
if(expbit){
/* Multiply */
ret = nn_mul_redc1(out, out, &_base, mod, mpinv); EG(ret, err);
}
}
/* Unredcify the output */
ret = nn_mul_redc1(out, out, &one, mod, mpinv);
err:
nn_uninit(&r);
nn_uninit(&r_square);
nn_uninit(&_base);
nn_uninit(&one);
return ret;
}
#endif /* __COMMON_H__ */