rmpint.h

Go to the documentation of this file.

/* RLIB - Convenience library for useful things
 * Copyright (C) 2015-2016  Haakon Sporsheim <haakon.sporsheim@gmail.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 3.0 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library.
 * See the COPYING file at the root of the source repository.
 */
#ifndef __R_MPINT_H__
#define __R_MPINT_H__
 
#if !defined(__RLIB_H_INCLUDE_GUARD__) && !defined(RLIB_COMPILATION)
#error "#include <rlib.h> only please."
#endif
 
#include <rlib/rtypes.h>
 
#include <rlib/rrand.h>
 
R_BEGIN_DECLS
 
#define RMPINT_DEF_DIGITS     64
#define RMPINT_DEF_ISPRIME_T  8
 
typedef ruint32         rmpint_digit;
typedef ruint64         rmpint_word;
 
typedef struct {
  ruint16         dig_alloc;  
  ruint16         dig_used;   
  ruint32         sign;       
  ruint32         flags;
  rmpint_digit *  data;       
} rmpint;
 
#define R_MPINT_FLAG_SECURE_CLEAR (1u << 0)
 
#define R_MPINT_INIT            { 0, 0, 0, 0, NULL }
#define r_mpint_init(mpi)       r_mpint_init_size (mpi, RMPINT_DEF_DIGITS)
 
R_API void r_mpint_init_size (rmpint * mpi, ruint16 digits);
R_API void r_mpint_init_secure (rmpint * mpi);
R_API void r_mpint_init_binary_secure (rmpint * mpi, rconstpointer data, rsize size);
R_API void r_mpint_init_copy_secure (rmpint * mpi, const rmpint * b);
R_API void r_mpint_set_secure_clear (rmpint * mpi);
R_API void r_mpint_init_from (rmpint * dst, const rmpint * src1, ...)
    R_ATTR_NULL_TERMINATED;
R_API void r_mpint_init_size_from (rmpint * dst, ruint16 digits,
    const rmpint * src1, ...) R_ATTR_NULL_TERMINATED;
R_API void r_mpint_init_binary (rmpint * mpi, rconstpointer data, rsize size);
R_API void r_mpint_init_str (rmpint * mpi, const rchar * str,
    const rchar ** endptr, ruint base);
R_API void r_mpint_init_copy (rmpint * dst, const rmpint * src);
R_API void r_mpint_clear (rmpint * mpi);
 
R_API ruint8 * r_mpint_to_binary_new (const rmpint * mpi, rsize * size) R_ATTR_MALLOC;
R_API rboolean r_mpint_to_binary (const rmpint * mpi, ruint8 * bin, rsize * size);
R_API rboolean r_mpint_to_binary_with_size (const rmpint * mpi, ruint8 * bin, rsize size);
R_API rchar * r_mpint_to_str (const rmpint * mpi);
 
#define r_mpint_iszero(mpi)       ((mpi)->dig_used == 0)
#define r_mpint_iseven(mpi)       ((mpi)->dig_used > 0 && (((mpi)->data[0] & 1) == 0))
#define r_mpint_isodd(mpi)        ((mpi)->dig_used > 0 && (((mpi)->data[0] & 1) == 1))
#define r_mpint_isneg(mpi)        ((mpi)->dig_used > 0 && (mpi)->sign)
 
#define r_mpint_digits_used(mpi)  (mpi)->dig_used
#define r_mpint_bytes_used(mpi)   ((ruint)((mpi)->dig_used > 0 ?              \
    (ruint)(((ruint)(mpi)->dig_used * sizeof (rmpint_digit)) -                \
    (ruint)RUINT32_CLZ (r_mpint_get_digit (mpi, (mpi)->dig_used - 1)) / 8) :  \
    ((ruint)0)))
#define r_mpint_bits_used(mpi)    ((ruint)((mpi)->dig_used > 0 ?              \
    (ruint)(((ruint)(mpi)->dig_used * sizeof (rmpint_digit) * 8) -            \
    (ruint)RUINT32_CLZ (r_mpint_get_digit (mpi, (mpi)->dig_used - 1))) :      \
    ((ruint)0)))
#define r_mpint_clamp(mpi)   R_STMT_START {                           \
  while ((mpi)->dig_used > 0 && (mpi)->data[(mpi)->dig_used-1] == 0)  \
    (mpi)->dig_used--;                                                \
  (mpi)->sign = (mpi)->dig_used > 0 ? (mpi)->sign : 0;                \
} R_STMT_END
 
R_API rboolean r_mpint_gen_prime_full (rmpint * mpi, rsize bits, rboolean safe,
    RPrng * prng);
#define r_mpint_gen_prime(mpi, bits, prng) r_mpint_gen_prime_full (mpi, bits, FALSE, prng)
 
typedef enum {
  R_MPINT_ERROR = -1,           
  R_MPINT_NON_PRIME = 0,        
  R_MPINT_CERTAIN_PRIME,        
  R_MPINT_POSSIBLE_PRIME,       
} RMpintPrimeTest;
 
R_API RMpintPrimeTest r_mpint_isprime_t (const rmpint * mpi, ruint t);
#define r_mpint_isprime(mpi) r_mpint_isprime_t (mpi, RMPINT_DEF_ISPRIME_T)
 
R_API void r_mpint_zero (rmpint * mpi);
R_API void r_mpint_set (rmpint * mpi, const rmpint * b);
R_API void r_mpint_set_binary (rmpint * mpi, rconstpointer data, rsize size);
R_API void r_mpint_set_i32 (rmpint * mpi, rint32 value);
R_API void r_mpint_set_u32 (rmpint * mpi, ruint32 value);
R_API void r_mpint_set_i64 (rmpint * mpi, rint64 value);
R_API void r_mpint_set_u64 (rmpint * mpi, ruint64 value);
 
R_API void r_mpint_swap_ct (rmpint * a, rmpint * b, ruint32 bit);
 
#define r_mpint_get_digit(mpi, d) \
  ((d) < (mpi)->dig_used ? (mpi)->data[d] : (rmpint_digit)0)
 
static inline rmpint_digit
r_mpint_get_digit_ct (const rmpint * mpi, ruint32 d)
{
  rmpint_digit value = (d < mpi->dig_alloc) ? mpi->data[d] : (rmpint_digit)0;
  ruint32 below = ((ruint32)d - (ruint32)mpi->dig_used) >> 31;
  rmpint_digit mask = (rmpint_digit)0 - (rmpint_digit)below;
  return value & mask;
}
 
R_API ruint32 r_mpint_ctz (const rmpint * mpi);
 
R_API int r_mpint_cmp (const rmpint * a, const rmpint * b);
R_API int r_mpint_ucmp (const rmpint * a, const rmpint * b);
R_API int r_mpint_cmp_i32 (const rmpint * a, rint32 b);
R_API int r_mpint_ucmp_u32 (const rmpint * a, ruint32 b);
 
R_API rboolean r_mpint_add (rmpint * dst, const rmpint * a, const rmpint * b);
R_API rboolean r_mpint_add_i32 (rmpint * dst, const rmpint * a, rint32 b);
R_API rboolean r_mpint_add_u32 (rmpint * dst, const rmpint * a, ruint32 b);
 
R_API rboolean r_mpint_sub (rmpint * dst, const rmpint * a, const rmpint * b);
R_API rboolean r_mpint_sub_i32 (rmpint * dst, const rmpint * a, rint32 b);
R_API rboolean r_mpint_sub_u32 (rmpint * dst, const rmpint * a, ruint32 b);
 
R_API rboolean r_mpint_shl (rmpint * dst, const rmpint * a, ruint32 bits);
R_API rboolean r_mpint_shr (rmpint * dst, const rmpint * a, ruint32 bits);
R_API rboolean r_mpint_shl_digit (rmpint * dst, const rmpint * a, ruint16 d);
R_API rboolean r_mpint_shr_digit (rmpint * dst, const rmpint * a, ruint16 d);
 
R_API rboolean r_mpint_mul (rmpint * dst, const rmpint * a, const rmpint * b);
R_API rboolean r_mpint_mul_i32 (rmpint * dst, const rmpint * a, rint32 b);
R_API rboolean r_mpint_mul_u32 (rmpint * dst, const rmpint * a, ruint32 b);
 
R_API rboolean r_mpint_div (rmpint * q, rmpint * r, const rmpint * n, const rmpint * d);
R_API rboolean r_mpint_div_i32 (rmpint * q, rmpint * r, const rmpint * n, rint32 d);
R_API rboolean r_mpint_div_u32 (rmpint * q, rmpint * r, const rmpint * n, ruint32 d);
 
R_API rboolean r_mpint_exp (rmpint * dst, const rmpint * b, ruint16 e);
 
#define r_mpint_mod(dst, n, d)            r_mpint_div (NULL, dst, n, d)
#define r_mpint_mod_i32(dst, n, d)        r_mpint_div_i32 (NULL, dst, n, d)
#define r_mpint_mod_u32(dst, n, d)        r_mpint_div_u32 (NULL, dst, n, d)
 
#define r_mpint_mulmod(dst, a, b, d)      (r_mpint_mul (dst, a, b) && r_mpint_mod (dst, dst, d))
#define r_mpint_mulmod_i32(dst, a, b, d)  (r_mpint_mul (dst, a, b) && r_mpint_mod_i32 (dst, dst, d))
#define r_mpint_mulmod_u32(dst, a, b, d)  (r_mpint_mul (dst, a, b) && r_mpint_mod_u32 (dst, dst, d))
 
R_API rboolean r_mpint_invmod (rmpint * dst, const rmpint * a, const rmpint * m);
 
R_API rboolean r_mpint_expmod (rmpint * dst, const rmpint * b, const rmpint * e, const rmpint * m);
R_API rboolean r_mpint_expmod_ct (rmpint * dst, const rmpint * b,
    const rmpint * e, const rmpint * m, ruint exp_bits);
R_API rboolean r_mpint_montgomery_setup (rmpint_digit * mp, const rmpint * m);
 
R_API rboolean r_mpint_expmod_ct_with_mp (rmpint * dst, const rmpint * b,
    const rmpint * e, const rmpint * m, rmpint_digit mp, ruint exp_bits);
 
R_API rboolean r_mpint_gcd (rmpint * dst, const rmpint * a, const rmpint * b);
R_API rboolean r_mpint_lcm (rmpint * dst, const rmpint * a, const rmpint * b);
 
/* =================================================================
 * Fixed-width Montgomery-form field elements (RMpintFE)
 *
 * Unlike rmpint, RMpintFE stores its digits inline in the struct
 * (no heap, no dig_used field) and every primitive iterates exactly
 * the modulus's digit count regardless of operand value. That gives
 * genuinely constant-time arithmetic at the cycle-count level - no
 * residual leak through r_mpint_clamp shrinking dig_used to the
 * value's bit length.
 *
 * Used by the ECC scalar-mul ladder (rlib/crypto/recurve.c). DSA
 * signing and RSA private operations want the same primitives. The
 * type is public so consumers outside rlib can reuse the same
 * audited implementation - same reason r_mpint_swap_ct and the rest
 * of the CT primitives live in this header.
 * =================================================================
 */
 
#define R_MPINT_FE_MAX_DIGITS  18
 
typedef struct {
  rmpint_digit d[R_MPINT_FE_MAX_DIGITS];
} RMpintFE;
 
typedef struct {
  RMpintFE p;                 
  rmpint_digit mp;            
  ruint16 n_digits;           
} RMpintFEMontCtx;
 
#define R_MPINT_FE_BIG_MAX_DIGITS  257
 
typedef struct {
  rmpint_digit d[R_MPINT_FE_BIG_MAX_DIGITS];
} RMpintFE_Big;
 
typedef struct {
  RMpintFE_Big p;             
  rmpint_digit mp;            
  ruint16 n_digits;           
} RMpintFE_BigMontCtx;
 
R_API rboolean r_mpint_fe_mont_ctx_init (RMpintFEMontCtx * ctx, const rmpint * m);
 
R_API rboolean r_mpint_fe_compute_r_squared (RMpintFE * out, const rmpint * m,
    ruint16 n);
 
R_API void r_mpint_fe_zero (RMpintFE * x);
R_API void r_mpint_fe_copy (RMpintFE * dst, const RMpintFE * src);
R_API void r_mpint_fe_from_mpint (RMpintFE * fe, const rmpint * mpi, ruint16 n);
R_API rboolean r_mpint_fe_to_mpint (rmpint * mpi, const RMpintFE * fe, ruint16 n);
 
R_API rmpint_digit r_mpint_fe_iszero_ct (const RMpintFE * x, ruint16 n);
R_API void r_mpint_fe_select_ct (RMpintFE * out, rmpint_digit mask,
    const RMpintFE * a, const RMpintFE * b, ruint16 n);
R_API void r_mpint_fe_swap_ct (RMpintFE * a, RMpintFE * b,
    ruint32 bit, ruint16 n);
 
R_API void r_mpint_fe_add (RMpintFE * out, const RMpintFE * a,
    const RMpintFE * b, const RMpintFEMontCtx * ctx);
R_API void r_mpint_fe_sub (RMpintFE * out, const RMpintFE * a,
    const RMpintFE * b, const RMpintFEMontCtx * ctx);
 
R_API void r_mpint_fe_mul_mont (RMpintFE * out, const RMpintFE * a,
    const RMpintFE * b, const RMpintFEMontCtx * ctx);
R_API void r_mpint_fe_sqr_mont (RMpintFE * out, const RMpintFE * a,
    const RMpintFEMontCtx * ctx);
 
R_API void r_mpint_fe_mont_in (RMpintFE * out, const RMpintFE * a,
    const RMpintFE * mont_r_squared, const RMpintFEMontCtx * ctx);
R_API void r_mpint_fe_mont_out (RMpintFE * out, const RMpintFE * a,
    const RMpintFEMontCtx * ctx);
 
R_API void r_mpint_fe_invmod_mont (RMpintFE * out, const RMpintFE * a_M,
    const RMpintFE * p_minus_2, ruint p_minus_2_bits,
    const RMpintFE * mont_r_squared, const RMpintFEMontCtx * ctx);
 
R_API void r_mpint_fe_mul_ct (RMpintFE * out, const RMpintFE * a, ruint16 a_n,
    const RMpintFE * b, ruint16 b_n);
R_API void r_mpint_fe_add_ct (RMpintFE * out, const RMpintFE * a, ruint16 a_n,
    const RMpintFE * b, ruint16 b_n);
R_API void r_mpint_fe_mod_ct (RMpintFE * out, const RMpintFE * a,
    const RMpintFEMontCtx * ctx);
 
R_API rboolean r_mpint_fe_big_mont_ctx_init (RMpintFE_BigMontCtx * ctx,
    const rmpint * m);
R_API rboolean r_mpint_fe_big_compute_r_squared (RMpintFE_Big * out,
    const rmpint * m, ruint16 n);
 
R_API void r_mpint_fe_big_zero (RMpintFE_Big * x);
R_API void r_mpint_fe_big_copy (RMpintFE_Big * dst, const RMpintFE_Big * src);
R_API void r_mpint_fe_big_from_mpint (RMpintFE_Big * fe, const rmpint * mpi,
    ruint16 n);
R_API rboolean r_mpint_fe_big_to_mpint (rmpint * mpi, const RMpintFE_Big * fe,
    ruint16 n);
 
R_API rmpint_digit r_mpint_fe_big_iszero_ct (const RMpintFE_Big * x, ruint16 n);
R_API void r_mpint_fe_big_select_ct (RMpintFE_Big * out, rmpint_digit mask,
    const RMpintFE_Big * a, const RMpintFE_Big * b, ruint16 n);
R_API void r_mpint_fe_big_swap_ct (RMpintFE_Big * a, RMpintFE_Big * b,
    ruint32 bit, ruint16 n);
 
R_API void r_mpint_fe_big_add (RMpintFE_Big * out, const RMpintFE_Big * a,
    const RMpintFE_Big * b, const RMpintFE_BigMontCtx * ctx);
R_API void r_mpint_fe_big_sub (RMpintFE_Big * out, const RMpintFE_Big * a,
    const RMpintFE_Big * b, const RMpintFE_BigMontCtx * ctx);
 
R_API void r_mpint_fe_big_mul_mont (RMpintFE_Big * out, const RMpintFE_Big * a,
    const RMpintFE_Big * b, const RMpintFE_BigMontCtx * ctx);
R_API void r_mpint_fe_big_sqr_mont (RMpintFE_Big * out, const RMpintFE_Big * a,
    const RMpintFE_BigMontCtx * ctx);
 
R_API void r_mpint_fe_big_mont_in (RMpintFE_Big * out, const RMpintFE_Big * a,
    const RMpintFE_Big * mont_r_squared, const RMpintFE_BigMontCtx * ctx);
R_API void r_mpint_fe_big_mont_out (RMpintFE_Big * out, const RMpintFE_Big * a,
    const RMpintFE_BigMontCtx * ctx);
 
R_API void r_mpint_fe_big_invmod_mont (RMpintFE_Big * out,
    const RMpintFE_Big * a_M,
    const RMpintFE_Big * p_minus_2, ruint p_minus_2_bits,
    const RMpintFE_Big * mont_r_squared, const RMpintFE_BigMontCtx * ctx);
 
R_API void r_mpint_fe_big_mul_ct (RMpintFE_Big * out,
    const RMpintFE_Big * a, ruint16 a_n,
    const RMpintFE_Big * b, ruint16 b_n);
R_API void r_mpint_fe_big_add_ct (RMpintFE_Big * out,
    const RMpintFE_Big * a, ruint16 a_n,
    const RMpintFE_Big * b, ruint16 b_n);
R_API void r_mpint_fe_big_mod_ct (RMpintFE_Big * out, const RMpintFE_Big * a,
    const RMpintFE_BigMontCtx * ctx);
 
R_API rboolean r_mpint_fe_big_expmod_ct (rmpint * dst,
    const rmpint * base, const rmpint * exp, const rmpint * m,
    const RMpintFE_BigMontCtx * ctx,
    const RMpintFE_Big * mont_r_squared, ruint exp_bits);
 
R_END_DECLS
 
#endif /* __R_MPINT_H__ */