rmpint.h File Reference

Multi-precision integer arithmetic plus fixed-width Montgomery-form field elements (RMpintFE / RMpintFE_Big). More...

#include <rlib/rtypes.h>
#include <rlib/rrand.h>

Go to the source code of this file.

Data Structures
struct	rmpint
	Heap-backed multi-precision integer. More...
struct	RMpintFE
	Fixed-width inline-storage field element used by the ECC scalar-mul ladder. More...
struct	RMpintFEMontCtx
	Per-modulus Montgomery context. More...
struct	RMpintFE_Big
	RSA-width parallel to RMpintFE. More...
struct	RMpintFE_BigMontCtx
	Per-modulus Montgomery context for RMpintFE_Big. More...

Macros
#define	RMPINT_DEF_DIGITS   64
	Default initial digit capacity for r_mpint_init.
#define	RMPINT_DEF_ISPRIME_T   8
	Default Miller-Rabin round count for r_mpint_isprime.
#define	R_MPINT_FLAG_SECURE_CLEAR   (1u << 0)
	Flag: wipe data via r_memclear_secure on r_mpint_clear.
#define	R_MPINT_INIT   { 0, 0, 0, 0, NULL }
	Static initialiser for an empty (zero-valued) rmpint.
#define	r_mpint_init(mpi)   r_mpint_init_size (mpi, RMPINT_DEF_DIGITS)
	Initialise with the default digit capacity (RMPINT_DEF_DIGITS).
#define	R_MPINT_FE_MAX_DIGITS   18
	Maximum digit width for RMpintFE.
#define	R_MPINT_FE_BIG_MAX_DIGITS   257
	Maximum digit width for RMpintFE_Big.
Inline predicates and metadata accessors
#define	r_mpint_iszero(mpi)   ((mpi)->dig_used == 0)
	TRUE iff mpi is zero.
#define	r_mpint_iseven(mpi)   ((mpi)->dig_used > 0 && (((mpi)->data[0] & 1) == 0))
	TRUE iff the magnitude of mpi is even.
#define	r_mpint_isodd(mpi)   ((mpi)->dig_used > 0 && (((mpi)->data[0] & 1) == 1))
	TRUE iff the magnitude of mpi is odd.
#define	r_mpint_isneg(mpi)   ((mpi)->dig_used > 0 && (mpi)->sign)
	TRUE iff mpi is strictly negative.
#define	r_mpint_digits_used(mpi)   (mpi)->dig_used
	Number of digits mpi's magnitude occupies.
#define	r_mpint_bytes_used(mpi)
	Byte length of mpi's magnitude (without leading zeros).
#define	r_mpint_bits_used(mpi)
	Bit length of mpi's magnitude.
#define	r_mpint_clamp(mpi)
	Shrink dig_used until the leading digit is non-zero; clear sign if the value is zero.

Typedefs
typedef ruint32	rmpint_digit
	Digit machine word backing rmpint storage.
typedef ruint64	rmpint_word
	Double-width word for digit multiplications.

Functions
Initialisation, secure-clear handling and lifecycle
void	r_mpint_init_size (rmpint *mpi, ruint16 digits)
	Initialise mpi with a caller-chosen digit capacity.
void	r_mpint_init_secure (rmpint *mpi)
	Initialise with the secure-clear flag set.
void	r_mpint_init_binary_secure (rmpint *mpi, rconstpointer data, rsize size)
	One-shot init from raw bytes with the secure flag set, so a key imported from a buffer never spends a moment with the secure-clear flag clear.
void	r_mpint_init_copy_secure (rmpint *mpi, const rmpint *b)
	One-shot init-from-copy with the secure flag set, for cloning a key into a fresh secure-clear mpint.
void	r_mpint_set_secure_clear (rmpint *mpi)
	Flip R_MPINT_FLAG_SECURE_CLEAR on an existing mpint.
void	r_mpint_init_from (rmpint *dst, const rmpint *src1,...)
	Initialise dst with the default size and OR in R_MPINT_FLAG_SECURE_CLEAR if any source in the NULL-terminated argument list has it set.
void	r_mpint_init_size_from (rmpint *dst, ruint16 digits, const rmpint *src1,...)
	Same as r_mpint_init_from but with a caller-chosen initial digit capacity, for call sites that allocate a specifically-sized scratch up front.
void	r_mpint_init_binary (rmpint *mpi, rconstpointer data, rsize size)
	Initialise from a big-endian byte buffer.
void	r_mpint_init_str (rmpint *mpi, const rchar *str, const rchar **endptr, ruint base)
	Initialise by parsing str in base.
void	r_mpint_init_copy (rmpint *dst, const rmpint *src)
	Initialise as a copy of src.
void	r_mpint_clear (rmpint *mpi)
	Release mpi's digit storage.
Binary / string conversion
ruint8 *	r_mpint_to_binary_new (const rmpint *mpi, rsize *size)
	Allocate a fresh big-endian byte buffer holding mpi's absolute value.
rboolean	r_mpint_to_binary (const rmpint *mpi, ruint8 *bin, rsize *size)
	Write mpi's absolute value into a caller buffer.
rboolean	r_mpint_to_binary_with_size (const rmpint *mpi, ruint8 *bin, rsize size)
	Write mpi's absolute value left-zero-padded to exactly size bytes.
rchar *	r_mpint_to_str (const rmpint *mpi)
	Allocate a decimal string representation of mpi. Caller frees with r_free.
Value-setting helpers
void	r_mpint_zero (rmpint *mpi)
	Set mpi to zero (preserves capacity and flags).
void	r_mpint_set (rmpint *mpi, const rmpint *b)
	Copy b's value into mpi.
void	r_mpint_set_binary (rmpint *mpi, rconstpointer data, rsize size)
	Set mpi from a big-endian byte buffer.
void	r_mpint_set_i32 (rmpint *mpi, rint32 value)
	Set from a signed 32-bit value.
void	r_mpint_set_u32 (rmpint *mpi, ruint32 value)
	Set from an unsigned 32-bit value.
void	r_mpint_set_i64 (rmpint *mpi, rint64 value)
	Set from a signed 64-bit value.
void	r_mpint_set_u64 (rmpint *mpi, ruint64 value)
	Set from an unsigned 64-bit value.
Comparison
int	r_mpint_cmp (const rmpint *a, const rmpint *b)
	Signed compare: returns <0 / 0 / >0 like memcmp.
int	r_mpint_ucmp (const rmpint *a, const rmpint *b)
	Unsigned (magnitude) compare.
int	r_mpint_cmp_i32 (const rmpint *a, rint32 b)
	Signed compare against a 32-bit value.
int	r_mpint_ucmp_u32 (const rmpint *a, ruint32 b)
	Unsigned compare against a 32-bit value.
Number-theoretic operations
rboolean	r_mpint_invmod (rmpint *dst, const rmpint *a, const rmpint *m)
	Modular inverse: dst = a^-1 mod m.
rboolean	r_mpint_expmod (rmpint *dst, const rmpint *b, const rmpint *e, const rmpint *m)
	Modular exponentiation: dst = b^e mod m.
rboolean	r_mpint_expmod_ct (rmpint *dst, const rmpint *b, const rmpint *e, const rmpint *m, ruint exp_bits)
	Constant-time modular exponentiation.
rboolean	r_mpint_montgomery_setup (rmpint_digit *mp, const rmpint *m)
	Compute the per-modulus Montgomery inverse mp = -m^-1 mod 2^digit_bits.
rboolean	r_mpint_expmod_ct_with_mp (rmpint *dst, const rmpint *b, const rmpint *e, const rmpint *m, rmpint_digit mp, ruint exp_bits)
	Variant of r_mpint_expmod_ct that takes the per-modulus Montgomery inverse mp as input rather than deriving it from m on every call.
rboolean	r_mpint_gcd (rmpint *dst, const rmpint *a, const rmpint *b)
	Greatest common divisor.
rboolean	r_mpint_lcm (rmpint *dst, const rmpint *a, const rmpint *b)
	Least common multiple.
RMpintFE: per-modulus setup
Both helpers are one-time costs paid by the caller before any FE arithmetic; the resulting ctx + mont_r_squared are reusable across as many FE operations as the modulus is in scope for.
rboolean	r_mpint_fe_mont_ctx_init (RMpintFEMontCtx *ctx, const rmpint *m)
	Fill ctx (p, mp, n_digits) from an mpint modulus.
rboolean	r_mpint_fe_compute_r_squared (RMpintFE *out, const rmpint *m, ruint16 n)
	Compute R^2 mod m for the supplied n-digit modulus (R = 2^(32*n)).
RMpintFE: lifecycle / conversion
void	r_mpint_fe_zero (RMpintFE *x)
	Zero x's first R_MPINT_FE_MAX_DIGITS digits.
void	r_mpint_fe_copy (RMpintFE *dst, const RMpintFE *src)
	Copy src -> dst (full width).
void	r_mpint_fe_from_mpint (RMpintFE *fe, const rmpint *mpi, ruint16 n)
	Copy mpi -> fe, zero-padded to n digits. Truncates beyond n.
rboolean	r_mpint_fe_to_mpint (rmpint *mpi, const RMpintFE *fe, ruint16 n)
	Copy fe -> mpi, ending with r_mpint_clamp so the mpint side stays canonical.
RMpintFE: constant-time helpers (no field arithmetic)
rmpint_digit	r_mpint_fe_iszero_ct (const RMpintFE *x, ruint16 n)
	All-ones mask iff x's low n digits are zero; all-zeros otherwise.
void	r_mpint_fe_select_ct (RMpintFE *out, rmpint_digit mask, const RMpintFE *a, const RMpintFE *b, ruint16 n)
	out := (mask == all-ones) ? a : b, digit-wise over n digits.
void	r_mpint_fe_swap_ct (RMpintFE *a, RMpintFE *b, ruint32 bit, ruint16 n)
	Branchless XOR-swap of two FEs gated on bit.
RMpintFE: modular arithmetic mod p
Inputs in [0, p), outputs in [0, p). Add / sub commute with the Montgomery transform, so they work both for normal-form and Mont-form operands.
void	r_mpint_fe_add (RMpintFE *out, const RMpintFE *a, const RMpintFE *b, const RMpintFEMontCtx *ctx)
	Modular addition.
void	r_mpint_fe_sub (RMpintFE *out, const RMpintFE *a, const RMpintFE *b, const RMpintFEMontCtx *ctx)
	Modular subtraction.
void	r_mpint_fe_mul_mont (RMpintFE *out, const RMpintFE *a, const RMpintFE *b, const RMpintFEMontCtx *ctx)
	Montgomery multiplication via CIOS: out := a * b * R^-1 mod p, where R = 2^(32 * n_digits).
void	r_mpint_fe_sqr_mont (RMpintFE *out, const RMpintFE *a, const RMpintFEMontCtx *ctx)
	Montgomery squaring.
void	r_mpint_fe_mont_in (RMpintFE *out, const RMpintFE *a, const RMpintFE *mont_r_squared, const RMpintFEMontCtx *ctx)
	Lift from normal form into Montgomery form.
void	r_mpint_fe_mont_out (RMpintFE *out, const RMpintFE *a, const RMpintFEMontCtx *ctx)
	Lift from Montgomery form back into normal form.
RMpintFE: derived operations
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)
	Fermat-based modular inversion in Mont form: out := a_M^(p-2) mod p (also in Mont form).
RMpintFE: wide (non-modular) primitives
Used by the RSA CRT recombination to assemble the final plaintext outside any single field.
void	r_mpint_fe_mul_ct (RMpintFE *out, const RMpintFE *a, ruint16 a_n, const RMpintFE *b, ruint16 b_n)
	Wide multiply (operands of different digit widths).
void	r_mpint_fe_add_ct (RMpintFE *out, const RMpintFE *a, ruint16 a_n, const RMpintFE *b, ruint16 b_n)
	Wide add.
void	r_mpint_fe_mod_ct (RMpintFE *out, const RMpintFE *a, const RMpintFEMontCtx *ctx)
	Conditional-subtract-once reduce: out = (a < p) ? a : a - p.
RMpintFE_Big: counterparts to the RMpintFE primitives
Function semantics match the RMpintFE primitives above byte-for-byte (they are emitted from the same template); only the storage width and the type / function name spellings differ. The ctx / r-squared / exponent-bits inputs are the same role; consult the RMpintFE comments above for details.
rboolean	r_mpint_fe_big_mont_ctx_init (RMpintFE_BigMontCtx *ctx, const rmpint *m)
	See r_mpint_fe_mont_ctx_init.
rboolean	r_mpint_fe_big_compute_r_squared (RMpintFE_Big *out, const rmpint *m, ruint16 n)
	See r_mpint_fe_compute_r_squared.
void	r_mpint_fe_big_zero (RMpintFE_Big *x)
	See r_mpint_fe_zero.
void	r_mpint_fe_big_copy (RMpintFE_Big *dst, const RMpintFE_Big *src)
	See r_mpint_fe_copy.
void	r_mpint_fe_big_from_mpint (RMpintFE_Big *fe, const rmpint *mpi, ruint16 n)
	See r_mpint_fe_from_mpint.
rboolean	r_mpint_fe_big_to_mpint (rmpint *mpi, const RMpintFE_Big *fe, ruint16 n)
	See r_mpint_fe_to_mpint.
rmpint_digit	r_mpint_fe_big_iszero_ct (const RMpintFE_Big *x, ruint16 n)
	See r_mpint_fe_iszero_ct.
void	r_mpint_fe_big_select_ct (RMpintFE_Big *out, rmpint_digit mask, const RMpintFE_Big *a, const RMpintFE_Big *b, ruint16 n)
	See r_mpint_fe_select_ct.
void	r_mpint_fe_big_swap_ct (RMpintFE_Big *a, RMpintFE_Big *b, ruint32 bit, ruint16 n)
	See r_mpint_fe_swap_ct.
void	r_mpint_fe_big_add (RMpintFE_Big *out, const RMpintFE_Big *a, const RMpintFE_Big *b, const RMpintFE_BigMontCtx *ctx)
	See r_mpint_fe_add.
void	r_mpint_fe_big_sub (RMpintFE_Big *out, const RMpintFE_Big *a, const RMpintFE_Big *b, const RMpintFE_BigMontCtx *ctx)
	See r_mpint_fe_sub.
void	r_mpint_fe_big_mul_mont (RMpintFE_Big *out, const RMpintFE_Big *a, const RMpintFE_Big *b, const RMpintFE_BigMontCtx *ctx)
	See r_mpint_fe_mul_mont.
void	r_mpint_fe_big_sqr_mont (RMpintFE_Big *out, const RMpintFE_Big *a, const RMpintFE_BigMontCtx *ctx)
	See r_mpint_fe_sqr_mont.
void	r_mpint_fe_big_mont_in (RMpintFE_Big *out, const RMpintFE_Big *a, const RMpintFE_Big *mont_r_squared, const RMpintFE_BigMontCtx *ctx)
	See r_mpint_fe_mont_in.
void	r_mpint_fe_big_mont_out (RMpintFE_Big *out, const RMpintFE_Big *a, const RMpintFE_BigMontCtx *ctx)
	See r_mpint_fe_mont_out.
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)
	See r_mpint_fe_invmod_mont.
void	r_mpint_fe_big_mul_ct (RMpintFE_Big *out, const RMpintFE_Big *a, ruint16 a_n, const RMpintFE_Big *b, ruint16 b_n)
	See r_mpint_fe_mul_ct.
void	r_mpint_fe_big_add_ct (RMpintFE_Big *out, const RMpintFE_Big *a, ruint16 a_n, const RMpintFE_Big *b, ruint16 b_n)
	See r_mpint_fe_add_ct.
void	r_mpint_fe_big_mod_ct (RMpintFE_Big *out, const RMpintFE_Big *a, const RMpintFE_BigMontCtx *ctx)
	See r_mpint_fe_mod_ct.
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)
	Modular exponentiation in Z_m: dst = base^exp mod m.

Prime generation and testing
#define	r_mpint_gen_prime(mpi, bits, prng)   r_mpint_gen_prime_full (mpi, bits, FALSE, prng)
	Convenience: generate a (non-safe) prime.
#define	r_mpint_isprime(mpi)   r_mpint_isprime_t (mpi, RMPINT_DEF_ISPRIME_T)
	Convenience: r_mpint_isprime_t with RMPINT_DEF_ISPRIME_T rounds.
enum	RMpintPrimeTest { R_MPINT_ERROR = -1 , R_MPINT_NON_PRIME = 0 , R_MPINT_CERTAIN_PRIME , R_MPINT_POSSIBLE_PRIME }
	Result of a Miller-Rabin primality test. More...
rboolean	r_mpint_gen_prime_full (rmpint *mpi, rsize bits, rboolean safe, RPrng *prng)
	Generate a random prime of bits bits.
RMpintPrimeTest	r_mpint_isprime_t (const rmpint *mpi, ruint t)
	Miller-Rabin primality test with t rounds.

Constant-time helpers
#define	r_mpint_get_digit(mpi, d)    ((d) < (mpi)->dig_used ? (mpi)->data[d] : (rmpint_digit)0)
	Read a digit, treating reads past dig_used as zero.
void	r_mpint_swap_ct (rmpint *a, rmpint *b, ruint32 bit)
	Constant-time conditional swap.
static rmpint_digit	r_mpint_get_digit_ct (const rmpint *mpi, ruint32 d)
	Constant-time digit accessor.
ruint32	r_mpint_ctz (const rmpint *mpi)
	Count trailing zero bits in the magnitude of mpi.

Basic arithmetic
#define	r_mpint_mod(dst, n, d)   r_mpint_div (NULL, dst, n, d)
	Convenience: remainder-only division.
#define	r_mpint_mod_i32(dst, n, d)   r_mpint_div_i32 (NULL, dst, n, d)
	Convenience: remainder-only division by signed 32-bit.
#define	r_mpint_mod_u32(dst, n, d)   r_mpint_div_u32 (NULL, dst, n, d)
	Convenience: remainder-only division by unsigned 32-bit.
#define	r_mpint_mulmod(dst, a, b, d)   (r_mpint_mul (dst, a, b) && r_mpint_mod (dst, dst, d))
	Convenience: dst = (a * b) mod d.
#define	r_mpint_mulmod_i32(dst, a, b, d)   (r_mpint_mul (dst, a, b) && r_mpint_mod_i32 (dst, dst, d))
	Convenience: dst = (a * b) mod d (signed immediate).
#define	r_mpint_mulmod_u32(dst, a, b, d)   (r_mpint_mul (dst, a, b) && r_mpint_mod_u32 (dst, dst, d))
	Convenience: dst = (a * b) mod d (unsigned immediate).
rboolean	r_mpint_add (rmpint *dst, const rmpint *a, const rmpint *b)
	dst = a + b.
rboolean	r_mpint_add_i32 (rmpint *dst, const rmpint *a, rint32 b)
	dst = a + b (b is a signed 32-bit immediate).
rboolean	r_mpint_add_u32 (rmpint *dst, const rmpint *a, ruint32 b)
	dst = a + b (b is an unsigned 32-bit immediate).
rboolean	r_mpint_sub (rmpint *dst, const rmpint *a, const rmpint *b)
	dst = a - b.
rboolean	r_mpint_sub_i32 (rmpint *dst, const rmpint *a, rint32 b)
	dst = a - b (b is a signed 32-bit immediate).
rboolean	r_mpint_sub_u32 (rmpint *dst, const rmpint *a, ruint32 b)
	dst = a - b (b is an unsigned 32-bit immediate).
rboolean	r_mpint_shl (rmpint *dst, const rmpint *a, ruint32 bits)
	dst = a << bits.
rboolean	r_mpint_shr (rmpint *dst, const rmpint *a, ruint32 bits)
	dst = a >> bits.
rboolean	r_mpint_shl_digit (rmpint *dst, const rmpint *a, ruint16 d)
	dst = a shifted left by d whole digits.
rboolean	r_mpint_shr_digit (rmpint *dst, const rmpint *a, ruint16 d)
	dst = a shifted right by d whole digits.
rboolean	r_mpint_mul (rmpint *dst, const rmpint *a, const rmpint *b)
	dst = a * b.
rboolean	r_mpint_mul_i32 (rmpint *dst, const rmpint *a, rint32 b)
	dst = a * b (b is a signed 32-bit immediate).
rboolean	r_mpint_mul_u32 (rmpint *dst, const rmpint *a, ruint32 b)
	dst = a * b (b is an unsigned 32-bit immediate).
rboolean	r_mpint_div (rmpint *q, rmpint *r, const rmpint *n, const rmpint *d)
	Quotient + remainder of n / d.
rboolean	r_mpint_div_i32 (rmpint *q, rmpint *r, const rmpint *n, rint32 d)
	Divide by a signed 32-bit divisor.
rboolean	r_mpint_div_u32 (rmpint *q, rmpint *r, const rmpint *n, ruint32 d)
	Divide by an unsigned 32-bit divisor.
rboolean	r_mpint_exp (rmpint *dst, const rmpint *b, ruint16 e)
	dst = b^e for a small unsigned exponent e.

Detailed Description

Multi-precision integer arithmetic plus fixed-width Montgomery-form field elements (RMpintFE / RMpintFE_Big).