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 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 rand_core;rand_core
pub use rlp;rlp
pub use subtle;
pub use zeroize;zeroize
pub use hybrid_array;hybrid-array

Modules§

constshybrid-array
Type aliases for many constants.
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§

BoxedUintalloc
Fixed-precision heap-allocated big unsigned integer.
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.
RandomBitsErrorrand_core
Possible errors of the methods in RandomBits trait.

Traits§

AddMod
Compute self + rhs mod p.
ArrayDecodinghybrid-array
Support for decoding a Array as a big integer.
ArrayEncodinghybrid-array
Support for encoding a big integer as a Array.
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.
Randomrand_core
Random number generation support.
RandomBitsrand_core
Random bits generation support.
RandomModrand_core
Modular random number generation support.
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§

ByteArrayhybrid-array
Alias for a byte array whose size is defined by ArrayEncoding::ByteSize.
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.
U1088extra-sizes
1088-bit unsigned big integer.
U1152extra-sizes
1152-bit unsigned big integer.
U1216extra-sizes
1216-bit unsigned big integer.
U1280
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.
U1536
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.
U1792
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.
U2048
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.
U3072
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.
U3584
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.
U4096
4096-bit unsigned big integer.
U4160extra-sizes
4160-bit unsigned big integer.
U4224
4224-bit unsigned big integer.
U4288extra-sizes
4288-bit unsigned big integer.
U4352
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.
U6144
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.
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.