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. Note that the implementation has diverged significantly since the last 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 (MSRV) Policy

MSRV increases are not considered breaking changes and can happen in patch releases.

The crate MSRV accounts for all supported targets and crate feature combinations, excluding explicitly unstable features.

§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::FixedMontyForm: 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

See the modular module for types which implement Montgomery form modular arithmetic.

This library also has support for performing modular arithmetic on integers 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, NonZero, U256};

// mod 3
let modulus = NonZero::new(U256::from(3u8)).expect("non-zero");

// 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);

§Random number generation

When the rand_core feature 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};

let n = U256::random_from_rng(&mut rng());

§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};

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

§`crypto-primes` crate

This crate contains no prime number related functionality (e.g. random prime generation). Such functionality can be found in the companion crypto-primes crate.

Re-exports§

pub use ctutils;
pub use hybrid_array;
pub use rand_core;
pub use zeroize;

Modules§

bitlen 🔒: Bit calculations.
checked 🔒: Checked arithmetic.
consts
encoding 🔒: Shared encoding support.
int 🔒: Stack-allocated big signed integers.
jacobi 🔒
limb 🔒: Big integers are represented as an array of smaller CPU word-size integers called “limbs”.
modular: Modular arithmetic support.
non_zero 🔒: Wrapper type for non-zero integers.
odd 🔒: Wrapper type for non-zero integers.
prelude: Import prelude for this crate: includes important traits.
primitives 🔒
traits 🔒: Traits provided by this crate
uint 🔒: Stack-allocated big unsigned integers.
word 🔒: Word represents the core integer type we use as the core of Limb, and is typically the same size as a pointer on a particular CPU.
wrapping 🔒: Wrapping arithmetic.

Macros§

const_monty_form: Creates a type alias to ConstMontyForm with the given ConstMontyParams.
const_monty_params: Create a type representing a modulus which impls the ConstMontyParams trait with the given name, type, value (in big endian hex), and optional documentation string.
const_prime_monty_params: Create a type representing a prime modulus which impls the ConstPrimeMontyParams trait with the given name, type, value (in big endian hex), multiplicative generator, and optional documentation string.
cpubits: A macro for defining code based on the optimal word size to use for the target, as chosen heuristically at compile-time using cfg-based predicates.
impl_modulusDeprecated: Deprecated legacy macro which has been replaced by const_monty_form!.

Structs§

BoxedUint: Fixed-precision heap-allocated big unsigned integer.
Checked: Provides intentionally-checked arithmetic on T.
Choice: Constant-time analogue of bool providing a “best effort” optimization barrier.
CtOption: Equivalent of Option but predicated on a Choice with combinators that allow for constant-time operations which always perform the same sequence of instructions regardless of the value of is_some.
EncodedUint: Uint encoded as bytes.
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.
TryFromSliceError: Returned if an object cannot be instantiated from the given byte slice.
Uint: Stack-allocated big unsigned integer.
UintRef: Unsigned integer reference type.
Wrapping: Provides intentionally-wrapped arithmetic on T.

Enums§

ByteOrder: Byte order used when encoding/decoding field elements as bytestrings.
DecodeError: Possible errors in variable-time integer decoding methods.
JacobiSymbol: Possible return values for Jacobi symbol calculations.
RandomBitsError: Possible errors of the methods in RandomBits trait.

Traits§

Add: The addition operator +.
AddAssign: The addition assignment operator +=.
AddMod: Compute self + rhs mod p.
ArrayDecoding: Support for decoding a Array as a big integer.
ArrayEncoding: Support for encoding a big integer as a Array.
BitAnd: The bitwise AND operator &.
BitAndAssign: The bitwise AND assignment operator &=.
BitOps: Bit counting and bit operations.
BitOr: The bitwise OR operator |.
BitOrAssign: The bitwise OR assignment operator |=.
BitXor: The bitwise XOR operator ^.
BitXorAssign: The bitwise XOR assignment operator ^=.
Bounded: Integers whose representation takes a bounded amount of space.
CheckedAdd: Checked addition.
CheckedDiv: Checked division.
CheckedMul: Checked multiplication.
CheckedSquareRoot: Support for calculating checked square roots.
CheckedSub: Checked subtraction.
Concat: Define the result of concatenating two numbers into a “wide” value.
ConcatenatingMul: Widening multiply: returns a value with a number of limbs equal to the sum of the inputs.
ConcatenatingSquare: Widening square: returns a value with a number of limbs equal to double the sum of the input.
ConstOne: Defines an associated constant representing the multiplicative identity element for Self.
ConstZero: Defines an associated constant representing the additive identity element for Self.
Constants: Trait for associating constant values with a type.
CtAssign: Constant-time conditional assignment: assign a given value to another based on a Choice.
CtEq: Constant-time equality: like (Partial)Eq with Choice instead of bool.
CtGt: Constant time greater than.
CtLt: Constant time less than.
CtNeg: Constant-time conditional negation: negates a value when choice is Choice::TRUE.
CtSelect: Constant-time selection: choose between two values based on a given Choice.
Div: The division operator /.
DivAssign: The division assignment operator /=.
DivRemLimb: Support for optimized division by a single limb.
DivVartime: Division in variable time.
EncodedSize: A trait mapping between encoded representations of integers.
Encoding: Encoding support.
FixedInteger: Fixed-width Integers.
FloorSquareRoot: Support for calculating floored square roots.
Gcd: Compute the greatest common divisor of two integers.
Integer: Integer trait: represents common functionality of integer types provided by this crate.
InvModDeprecated: Compute 1 / self mod p.
Invert: Constant-time inversion.
InvertMod: Compute 1 / self mod p.
Lcm: Compute the least common multiple of two integers.
MontyForm: A representation of an integer optimized for the performance of modular operations.
MontyMultiplier: Prepared Montgomery multiplier for tight loops.
Mul: The multiplication operator *.
MulAssign: The multiplication assignment operator *=.
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.
Neg: The unary negation operator -.
NegMod: Compute -self mod p.
Not: The unary logical negation operator !.
One: One values: multiplicative identity element for Self.
Pow: Constant-time exponentiation.
PowBoundedExp: Constant-time exponentiation with exponent of a bounded bit size.
Random: Random number generation support.
RandomBits: Random bits generation support.
RandomMod: Modular random number generation support.
Reduce: Modular reduction from a larger value T.
Rem: The remainder operator %.
RemAssign: The remainder assignment operator %=.
RemLimb: Support for optimized division by a single limb.
RemMixed: Support for calculating the remainder of two differently sized integers.
Resize: Methods for resizing the allocated storage.
Shl: The left shift operator <<. Note that because this trait is implemented for all integer types with multiple right-hand-side types, Rust’s type checker has special handling for _ << _, setting the result type for integer operations to the type of the left-hand-side operand. This means that though a << b and a.shl(b) are one and the same from an evaluation standpoint, they are different when it comes to type inference.
ShlAssign: The left shift assignment operator <<=.
ShlVartime: Left shifts, variable time in shift.
Shr: The right shift operator >>. Note that because this trait is implemented for all integer types with multiple right-hand-side types, Rust’s type checker has special handling for _ >> _, setting the result type for integer operations to the type of the left-hand-side operand. This means that though a >> b and a.shr(b) are one and the same from an evaluation standpoint, they are different when it comes to type inference.
ShrAssign: The right shift assignment operator >>=.
ShrVartime: Right shifts, variable time in shift.
Signed: Signed Integers.
Split: Define the result of splitting a number into two parts, with the first part having the width LO.
SplitEven: Define the result of splitting a number into two parts, with each part having an equal width.
Square: Support for optimized squaring
SquareAssign: Support for optimized squaring in-place
SquareMod: Compute self * self mod p.
Sub: The subtraction operator -.
SubAssign: The subtraction assignment operator -=.
SubMod: Compute self - rhs mod p.
ToUnsigned: Support for upgrading UintRef-compatible references into Unsigned.
Unsigned: Unsigned Integers.
UnsignedWithMontyForm: Unsigned integers with an associated MontyForm.
WideningMulDeprecated: 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.
Xgcd: Compute the extended greatest common divisor of two integers.
Zero: Zero values: additive identity element for Self.

Functions§

nlimbs: Calculate the number of limbs required to represent the given number of bits.

Type Aliases§

ByteArray: Alias for a byte array whose size is defined by ArrayEncoding::ByteSize.
ConstChoiceDeprecated: DEPRECATED: legacy type alias for Choice.
ConstCtOptionDeprecated: DEPRECATED: legacy type alias for CtOption.
I64: Signed bit integer.
I128: Signed bit integer.
I256: Signed bit integer.
I512: Signed bit integer.
I1024: Signed bit integer.
I2048: Signed bit integer.
I4096: Signed bit integer.
NonZeroBoxedUint: Non-zero boxed unsigned integer.
NonZeroInt: Non-zero signed integer.
NonZeroLimb: Non-zero limb.
NonZeroUint: Non-zero unsigned integer.
NonZeroUintRef: Non-zero unsigned integer reference.
OddBoxedUint: Odd boxed unsigned integer.
OddInt: Odd signed integer.
OddUint: Odd unsigned integer.
OddUintRef: Odd unsigned integer reference.
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.