## 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.

### §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§

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

- Provides intentionally-checked arithmetic on
`T`

. - A boolean value returned by constant-time
`const fn`

s. - 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`

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

- 64-bit unsigned big integer.
- 128-bit unsigned big integer.
- 192-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.
- 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.
- 1280-bit unsigned big integer.
- 1536-bit unsigned big integer.
- 1792-bit unsigned big integer.
- 2048-bit unsigned big integer.
- 3072-bit unsigned big integer.
- 3584-bit unsigned big integer.
- 4096-bit unsigned big integer.
- 4224-bit unsigned big integer.
- 4352-bit unsigned big integer.
- 6144-bit unsigned big integer.
- 8192-bit unsigned big integer.
- 16384-bit unsigned big integer.
- 32768-bit unsigned big integer.
- Wide integer type: double the width of
`Word`

. - Unsigned integer type that the
`Limb`

newtype wraps.