Crate crypto_bigint

source ·
Expand description

§RustCrypto: Cryptographic Big Integers

crate Docs Build Status Apache2/MIT licensed Rust Version Project Chat

Pure Rust implementation of a big integer library which has been designed from the ground-up for use in cryptographic applications.

Provides constant-time, no_std-friendly implementations of modern formulas using const generics.

Documentation

§Goals

  • Supports no_std-friendly const generic stack-allocated big integers.
  • Constant-time by default. Variable-time functions are explicitly marked as such.
  • Leverage what is possible today with const generics on stable rust.
  • Support const fn as much as possible, including decoding big integers from bytes/hex and performing arithmetic operations on them, with the goal of being able to compute values at compile-time.

§Security Notes

This crate has been audited by NCC Group with no significant findings. We would like to thank Entropy for funding the audit.

All functions contained in the crate are designed to execute in constant time unless explicitly specified otherwise (via a *_vartime name suffix).

This library is not suitable for use on processors with a variable-time multiplication operation (e.g. short circuit on multiply-by-zero / multiply-by-one, such as certain 32-bit PowerPC CPUs and some non-ARM microcontrollers).

§Minimum Supported Rust Version

This crate requires Rust 1.65 at a minimum.

We may change the MSRV in the future, but it will be accompanied by a minor version bump.

§License

Licensed under either of:

at your option.

§Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

§Usage

This crate defines a Uint type which is const generic around an inner Limb array, where a Limb is a newtype for a word-sized integer. Thus large integers are represented as arrays of smaller integers which are sized appropriately for the CPU, giving us some assurances of how arithmetic operations over those smaller integers will behave.

To obtain appropriately sized integers regardless of what a given CPU’s word size happens to be, a number of portable type aliases are provided for integer sizes commonly used in cryptography, for example: U128, U384, U256, U2048, U3072, U4096.

§const fn usage

The Uint type provides a number of const fn inherent methods which can be used for initializing and performing arithmetic on big integers in const contexts:

use crypto_bigint::U256;

// Parse a constant from a big endian hexadecimal string.
pub const MODULUS: U256 =
    U256::from_be_hex("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551");

// Compute `MODULUS` shifted right by 1 at compile time
pub const MODULUS_SHR1: U256 = MODULUS.shr_vartime(1);

Note that large constant computations may accidentally trigger a the const_eval_limit of the compiler. The current way to deal with this problem is to either simplify this computation, or increase the compiler’s limit (currently a nightly feature). One can completely remove the compiler’s limit using:

ⓘ
#![feature(const_eval_limit)]
#![const_eval_limit = "0"]

§Trait-based usage

The Uint type itself does not implement the standard arithmetic traits such as Add, Sub, Mul, and Div.

To use these traits you must first pick a wrapper type which determines overflow behavior: Wrapping or Checked.

§Wrapping arithmetic
use crypto_bigint::{U256, Wrapping};

let a = Wrapping(U256::MAX);
let b = Wrapping(U256::ONE);
let c = a + b;

// `MAX` + 1 wraps back around to zero
assert_eq!(c.0, U256::ZERO);
§Checked arithmetic
use crypto_bigint::{U256, Checked};

let a = Checked::new(U256::ONE);
let b = Checked::new(U256::from(2u8));
let c = a + b;
assert_eq!(c.0.unwrap(), U256::from(3u8))

§Modular arithmetic

This library has initial support for modular arithmetic in the form of the AddMod, SubMod, NegMod, and MulMod traits, as well as the support for the Rem trait when used with a NonZero operand.

use crypto_bigint::{AddMod, U256};

// mod 3
let modulus = U256::from(3u8);

// 1 + 1 mod 3 = 2
let a = U256::ONE.add_mod(&U256::ONE, &modulus);
assert_eq!(a, U256::from(2u8));

// 2 + 1 mod 3 = 0
let b = a.add_mod(&U256::ONE, &modulus);
assert_eq!(b, U256::ZERO);

It also supports modular arithmetic over constant moduli using Residue, and over moduli set at runtime using DynResidue. That includes modular exponentiation and multiplicative inverses. These features are described in the modular module.

§Random number generation

When the rand_core or rand features of this crate are enabled, it’s possible to generate random numbers using any CSRNG by using the [Random] trait:

use crypto_bigint::{Random, U256, rand_core::OsRng};

let n = U256::random(&mut OsRng);
§Modular random number generation

The [RandomMod] trait supports generating random numbers with a uniform distribution around a given NonZero modulus.

use crypto_bigint::{NonZero, RandomMod, U256, rand_core::OsRng};

let modulus = NonZero::new(U256::from(3u8)).unwrap();
let n = U256::random_mod(&mut OsRng, &modulus);

Re-exports§

Modules§

  • modular
    Implements modular arithmetic for constant moduli.
  • prelude
    Import prelude for this crate: includes important traits.

Macros§

  • const_assert_eq
    Const-friendly assertion that two values are equal.
  • const_assert_ne
    Const-friendly assertion that two values are NOT equal.
  • const_residue
    Creates a Residue with the given value for a specific modulus. For example, residue!(U256::from(105u64), MyModulus); creates a Residue for 105 mod MyModulus. The modulus must be odd, or this will panic.
  • impl_modulus
    Implements a modulus with the given name, type, and value, in that specific order. Please use crypto_bigint::traits::Encoding to make this work. For example, impl_modulus!(MyModulus, U256, "73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001"); implements a 256-bit modulus named MyModulus. The modulus must be odd, or this will panic.
  • nlimbs
    Calculate the number of limbs required to represent the given number of bits.

Structs§

  • Checked
    Provides intentionally-checked arithmetic on T.
  • CtChoice
    A boolean value returned by constant-time const fns.
  • Limb
    Big integers are represented as an array of smaller CPU word-size integers called “limbs”.
  • NonZero
    Wrapper type for non-zero integers.
  • Reciprocal
    A pre-calculated reciprocal for division by a single limb.
  • Uint
    Stack-allocated big unsigned integer.
  • Wrapping
    Provides intentionally-wrapped arithmetic on T.

Traits§

  • AddMod
    Compute self + rhs mod p.
  • Bounded
    Integers whose representation takes a bounded amount of space.
  • CheckedAdd
    Checked addition.
  • CheckedMul
    Checked multiplication.
  • CheckedSub
    Checked subtraction.
  • Concat
    Concatenate two numbers into a “wide” double-width value, using the lo value as the least significant value.
  • ConcatMixed
    Concatenate two numbers into a “wide” combined-width value, using the lo value as the least significant value.
  • Encoding
    Encoding support.
  • Integer
    Integer type.
  • Invert
    Constant-time inversion.
  • MulMod
    Compute self * rhs mod p.
  • MultiExponentiate
    Performs modular multi-exponentiation using Montgomery’s ladder.
  • MultiExponentiateBoundedExp
    Performs modular multi-exponentiation using Montgomery’s ladder. exponent_bits represents the number of bits to take into account for the exponent.
  • NegMod
    Compute -self mod p.
  • Pow
    Constant-time exponentiation.
  • PowBoundedExp
    Constant-time exponentiation with exponent of a bounded bit size.
  • Split
    Split a number in half, returning the most significant half followed by the least significant.
  • SplitMixed
    Split a number into parts, returning the most significant part followed by the least significant.
  • Square
    Support for optimized squaring
  • SubMod
    Compute self - rhs mod p.
  • Zero
    Zero values.

Type Aliases§

  • U64
    64-bit unsigned big integer.
  • U128
    128-bit unsigned big integer.
  • U192
    192-bit unsigned big integer.
  • U256
    256-bit unsigned big integer.
  • U320
    320-bit unsigned big integer.
  • U384
    384-bit unsigned big integer.
  • U448
    448-bit unsigned big integer.
  • U512
    512-bit unsigned big integer.
  • U576
    576-bit unsigned big integer.
  • U640
    640-bit unsigned big integer.
  • U704
    704-bit unsigned big integer.
  • U768
    768-bit unsigned big integer.
  • U832
    832-bit unsigned big integer.
  • U896
    896-bit unsigned big integer.
  • U960
    960-bit unsigned big integer.
  • U1024
    1024-bit unsigned big integer.
  • U1280
    1280-bit unsigned big integer.
  • U1536
    1536-bit unsigned big integer.
  • U1792
    1792-bit unsigned big integer.
  • U2048
    2048-bit unsigned big integer.
  • U3072
    3072-bit unsigned big integer.
  • U3584
    3584-bit unsigned big integer.
  • U4096
    4096-bit unsigned big integer.
  • U4224
    4224-bit unsigned big integer.
  • U4352
    4352-bit unsigned big integer.
  • U6144
    6144-bit unsigned big integer.
  • U8192
    8192-bit unsigned big integer.
  • U16384
    16384-bit unsigned big integer.
  • U32768
    32768-bit unsigned big integer.
  • WideWord
    Wide integer type: double the width of Word.
  • Word
    Unsigned integer type that the Limb newtype wraps.