Crate crypto_bigint

Expand description

§RustCrypto: Cryptographic Big Integers

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 with the goal of being able to compute values at compile-time.
Optional heap-allocated Boxed* types gated under an alloc feature.

§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.83 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

The core types of crypto-bigint are as follows:

Uint: stack-allocated big integer type, const generic around a number of Limbs. Type aliases are provided for various sizes, e.g. U128, U384, U256, U2048, U3072, U4096.
[BoxedUint]: heap-allocated big integer type. Requires the alloc crate feature is enabled.

Big integer types in this crate use a 32-bit or 64-bit saturated representation, depending on the underlying CPU’s pointer width.

The following types for modular arithmetic are available under the modular submodule:

modular::ConstMontyForm: stack-allocated type-safe modular arithmetic using Montgomery form suitable for cases where the modulus is known at compile-time.
modular::MontyForm: stack-allocated modular arithmetic using Montgomery form for cases where the modulus is only known at runtime.
[modular::BoxedMontyForm]: heap-allocated modular arithmetic using Montgomery form. Requires the alloc crate feature is enabled.

§`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(1);

§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 ConstMontyForm, and over moduli set at runtime using MontyForm. 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 RNG 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§

pub use subtle;

Modules§

modular: Modular arithmetic support.
prelude: Import prelude for this crate: includes important traits.

Macros§

const_monty_form: Creates a ConstMontyForm with the given value for a specific modulus.
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.
nlimbs: Calculate the number of limbs required to represent the given number of bits.

Structs§

Checked: Provides intentionally-checked arithmetic on T.
ConstChoice: A boolean value returned by constant-time const fns.
ConstCtOption: An equivalent of subtle::CtOption usable in a const fn context.
Int: Stack-allocated big signed integer. See Uint for unsigned integers.
Limb: Big integers are represented as an array/vector of smaller CPU word-size integers called “limbs”.
NonZero: Wrapper type for non-zero integers.
Odd: Wrapper type for odd 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.

Enums§

DecodeError: Possible errors in variable-time integer decoding methods.

Traits§

AddMod: Compute self + rhs mod p.
BitOps: Bit counting and bit operations.
Bounded: Integers whose representation takes a bounded amount of space.
CheckedAdd: Checked addition.
CheckedDiv: Checked division.
CheckedMul: Checked multiplication.
CheckedSub: Checked subtraction.
Concat: Concatenate two numbers into a “wide” double-width value, using the hi value as the most significant portion of the resulting value.
ConcatMixed: Concatenate two numbers into a “wide” combined-width value, using the hi value as the most significant value.
ConstZero: Defines an associated constant representing the additive identity element for Self.
ConstantTimeSelect: Trait for types which are conditionally selectable in constant time.
Constants: Trait for associating constant values with a type.
DivRemLimb: Support for optimized division by a single limb.
Encoding: Encoding support.
FixedInteger: Fixed-width integers.
Gcd: Compute the greatest common divisor of two integers.
Integer: Integer trait: represents common functionality of integer types provided by this crate.
InvMod: Compute 1 / self mod p.
Invert: Constant-time inversion.
Inverter: Trait impl’d by precomputed modular inverters obtained via the PrecomputeInverter trait.
Monty: A representation of an integer optimized for the performance of modular operations.
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.
PrecomputeInverter: Obtain a precomputed inverter for efficiently computing modular inversions for a given modulus.
RemLimb: Support for optimized division by a single limb.
RemMixed: Support for calculating the remainder of two differently sized integers.
ShlVartime: Left shifts, variable time in shift.
ShrVartime: Right shifts, variable time in shift.
Split: Split a number in half, returning the least significant half followed by the most significant.
SplitMixed: Split a number into parts, returning the least significant part followed by the most significant.
Square: Support for optimized squaring
SquareAssign: Support for optimized squaring in-place
SquareRoot: Support for calucaling square roots.
SubMod: Compute self - rhs mod p.
WideningMul: Widening multiply: returns a value with a number of limbs equal to the sum of the inputs.
WrappingAdd: Performs addition that wraps around on overflow.
WrappingMul: Performs multiplication that wraps around on overflow.
WrappingNeg: Performs a negation that does not panic.
WrappingShl: Performs a left shift that does not panic.
WrappingShr: Performs a right shift that does not panic.
WrappingSub: Performs subtraction that wraps around on overflow.
Zero: Zero values.

Type Aliases§

I6464-bit: Signed bit integer.
I12864-bit: Signed bit integer.
I25664-bit: Signed bit integer.
I51264-bit: Signed bit integer.
I102464-bit: Signed bit integer.
I204864-bit: Signed bit integer.
I409664-bit: Signed bit integer.
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.