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

  • constsgeneric-array
    Type aliases for many constants.
  • Implements modular arithmetic for constant moduli.
  • Import prelude for this crate: includes important traits.

Macros

  • Const-friendly assertion that two values are equal.
  • Const-friendly assertion that two values are NOT equal.
  • 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.
  • 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.
  • Calculate the number of limbs required to represent the given number of bits.

Structs

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

Traits

  • Compute self + rhs mod p.
  • ArrayDecodinggeneric-array
    Support for decoding a GenericArray as a big integer.
  • ArrayEncodinggeneric-array
    Support for encoding a big integer as a GenericArray.
  • Integers whose representation takes a bounded amount of space.
  • Checked addition.
  • Checked multiplication.
  • Checked subtraction.
  • Concatenate two numbers into a “wide” double-width value, using the lo value as the least significant value.
  • Concatenate two numbers into a “wide” combined-width value, using the lo value as the least significant value.
  • Encoding support.
  • Integer type.
  • Constant-time inversion.
  • Compute self * rhs mod p.
  • Performs modular multi-exponentiation using Montgomery’s ladder.
  • Performs modular multi-exponentiation using Montgomery’s ladder. exponent_bits represents the number of bits to take into account for the exponent.
  • Compute -self mod p.
  • Constant-time exponentiation.
  • Constant-time exponentiation with exponent of a bounded bit size.
  • Randomrand_core
    Random number generation support.
  • RandomModrand_core
    Modular random number generation support.
  • Split a number in half, returning the most significant half followed by the least significant.
  • Split a number into parts, returning the most significant part followed by the least significant.
  • Support for optimized squaring
  • Compute self - rhs mod p.
  • Zero values.

Type Aliases

  • ByteArraygeneric-array
    Alias for a byte array whose size is defined by ArrayEncoding::ByteSize.
  • 64-bit unsigned big integer.
  • 128-bit unsigned big integer.
  • 192-bit unsigned big integer.
  • 224-bit unsigned big integer.
  • 256-bit unsigned big integer.
  • 320-bit unsigned big integer.
  • 384-bit unsigned big integer.
  • 448-bit unsigned big integer.
  • 512-bit unsigned big integer.
  • 544-bit unsigned big integer.
  • 576-bit unsigned big integer.
  • 640-bit unsigned big integer.
  • 704-bit unsigned big integer.
  • 768-bit unsigned big integer.
  • 832-bit unsigned big integer.
  • 896-bit unsigned big integer.
  • 960-bit unsigned big integer.
  • 1024-bit unsigned big integer.
  • U1088extra-sizes
    1088-bit unsigned big integer.
  • U1152extra-sizes
    1152-bit unsigned big integer.
  • U1216extra-sizes
    1216-bit unsigned big integer.
  • 1280-bit unsigned big integer.
  • U1344extra-sizes
    1344-bit unsigned big integer.
  • U1408extra-sizes
    1408-bit unsigned big integer.
  • U1472extra-sizes
    1472-bit unsigned big integer.
  • 1536-bit unsigned big integer.
  • U1600extra-sizes
    1600-bit unsigned big integer.
  • U1664extra-sizes
    1664-bit unsigned big integer.
  • U1728extra-sizes
    1728-bit unsigned big integer.
  • 1792-bit unsigned big integer.
  • U1856extra-sizes
    1856-bit unsigned big integer.
  • U1920extra-sizes
    1920-bit unsigned big integer.
  • U1984extra-sizes
    1984-bit unsigned big integer.
  • 2048-bit unsigned big integer.
  • U2112extra-sizes
    2112-bit unsigned big integer.
  • U2176extra-sizes
    2176-bit unsigned big integer.
  • U2240extra-sizes
    2240-bit unsigned big integer.
  • U2304extra-sizes
    2304-bit unsigned big integer.
  • U2368extra-sizes
    2368-bit unsigned big integer.
  • U2432extra-sizes
    2432-bit unsigned big integer.
  • U2496extra-sizes
    2496-bit unsigned big integer.
  • U2560extra-sizes
    2560-bit unsigned big integer.
  • U2624extra-sizes
    2624-bit unsigned big integer.
  • U2688extra-sizes
    2688-bit unsigned big integer.
  • U2752extra-sizes
    2752-bit unsigned big integer.
  • U2816extra-sizes
    2816-bit unsigned big integer.
  • U2880extra-sizes
    2880-bit unsigned big integer.
  • U2944extra-sizes
    2944-bit unsigned big integer.
  • U3008extra-sizes
    3008-bit unsigned big integer.
  • 3072-bit unsigned big integer.
  • U3136extra-sizes
    3136-bit unsigned big integer.
  • U3200extra-sizes
    3200-bit unsigned big integer.
  • U3264extra-sizes
    3264-bit unsigned big integer.
  • U3328extra-sizes
    3328-bit unsigned big integer.
  • U3392extra-sizes
    3392-bit unsigned big integer.
  • U3456extra-sizes
    3456-bit unsigned big integer.
  • U3520extra-sizes
    3520-bit unsigned big integer.
  • 3584-bit unsigned big integer.
  • U3648extra-sizes
    3648-bit unsigned big integer.
  • U3712extra-sizes
    3712-bit unsigned big integer.
  • U3776extra-sizes
    3776-bit unsigned big integer.
  • U3840extra-sizes
    3840-bit unsigned big integer.
  • U3904extra-sizes
    3904-bit unsigned big integer.
  • U3968extra-sizes
    3968-bit unsigned big integer.
  • U4032extra-sizes
    4032-bit unsigned big integer.
  • 4096-bit unsigned big integer.
  • U4160extra-sizes
    4160-bit unsigned big integer.
  • 4224-bit unsigned big integer.
  • U4288extra-sizes
    4288-bit unsigned big integer.
  • 4352-bit unsigned big integer.
  • U4416extra-sizes
    4416-bit unsigned big integer.
  • U4480extra-sizes
    4480-bit unsigned big integer.
  • U4544extra-sizes
    4544-bit unsigned big integer.
  • U4608extra-sizes
    4608-bit unsigned big integer.
  • U4672extra-sizes
    4672-bit unsigned big integer.
  • U4736extra-sizes
    4736-bit unsigned big integer.
  • U4800extra-sizes
    4800-bit unsigned big integer.
  • U4864extra-sizes
    4864-bit unsigned big integer.
  • U4928extra-sizes
    4928-bit unsigned big integer.
  • U4992extra-sizes
    4992-bit unsigned big integer.
  • U5056extra-sizes
    5056-bit unsigned big integer.
  • U5120extra-sizes
    5120-bit unsigned big integer.
  • U5184extra-sizes
    5184-bit unsigned big integer.
  • U5248extra-sizes
    5248-bit unsigned big integer.
  • U5312extra-sizes
    5312-bit unsigned big integer.
  • U5376extra-sizes
    5376-bit unsigned big integer.
  • U5440extra-sizes
    5440-bit unsigned big integer.
  • U5504extra-sizes
    5504-bit unsigned big integer.
  • U5568extra-sizes
    5568-bit unsigned big integer.
  • U5632extra-sizes
    5632-bit unsigned big integer.
  • U5696extra-sizes
    5696-bit unsigned big integer.
  • U5760extra-sizes
    5760-bit unsigned big integer.
  • U5824extra-sizes
    5824-bit unsigned big integer.
  • U5888extra-sizes
    5888-bit unsigned big integer.
  • U5952extra-sizes
    5952-bit unsigned big integer.
  • U6016extra-sizes
    6016-bit unsigned big integer.
  • U6080extra-sizes
    6080-bit unsigned big integer.
  • 6144-bit unsigned big integer.
  • U6208extra-sizes
    6208-bit unsigned big integer.
  • U6272extra-sizes
    6272-bit unsigned big integer.
  • U6336extra-sizes
    6336-bit unsigned big integer.
  • U6400extra-sizes
    6400-bit unsigned big integer.
  • U6464extra-sizes
    6464-bit unsigned big integer.
  • U6528extra-sizes
    6528-bit unsigned big integer.
  • U6592extra-sizes
    6592-bit unsigned big integer.
  • U6656extra-sizes
    6656-bit unsigned big integer.
  • U6720extra-sizes
    6720-bit unsigned big integer.
  • U6784extra-sizes
    6784-bit unsigned big integer.
  • U6848extra-sizes
    6848-bit unsigned big integer.
  • U6912extra-sizes
    6912-bit unsigned big integer.
  • U6976extra-sizes
    6976-bit unsigned big integer.
  • U7040extra-sizes
    7040-bit unsigned big integer.
  • U7104extra-sizes
    7104-bit unsigned big integer.
  • U7168extra-sizes
    7168-bit unsigned big integer.
  • U7232extra-sizes
    7232-bit unsigned big integer.
  • U7296extra-sizes
    7296-bit unsigned big integer.
  • U7360extra-sizes
    7360-bit unsigned big integer.
  • U7424extra-sizes
    7424-bit unsigned big integer.
  • U7488extra-sizes
    7488-bit unsigned big integer.
  • U7552extra-sizes
    7552-bit unsigned big integer.
  • U7616extra-sizes
    7616-bit unsigned big integer.
  • U7680extra-sizes
    7680-bit unsigned big integer.
  • U7744extra-sizes
    7744-bit unsigned big integer.
  • U7808extra-sizes
    7808-bit unsigned big integer.
  • U7872extra-sizes
    7872-bit unsigned big integer.
  • U7936extra-sizes
    7936-bit unsigned big integer.
  • U8000extra-sizes
    8000-bit unsigned big integer.
  • U8064extra-sizes
    8064-bit unsigned big integer.
  • U8128extra-sizes
    8128-bit unsigned big integer.
  • 8192-bit unsigned big integer.
  • 16384-bit unsigned big integer.
  • 32768-bit unsigned big integer.
  • WideWord32-bit
    Unsigned wide integer type: double the width of Word.
  • Word32-bit
    Inner integer type that the Limb newtype wraps.