Cryptography-oriented big integer library with constant-time, stack-allocated (no_std-friendly) implementations of modern formulas

Overview

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

  • No heap allocations. no_std-friendly.
  • 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.

Minimum Supported Rust Version

Rust 1.51 at a minimum.

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.

Comments
  • Implement modular arithmetic

    Implement modular arithmetic

    Hi @tarcieri and the other contributors! For the scicrypt crate I was working on constant-time big integers by wrapping GMP, but the interface was extremely clumsy. I decided to switch to this crate (which looks awesome!) and added the necessary methods for modular arithmetic.

    I implemented the following functionality:

    • Shifting left and right by 1 and returning the overflow as a Choice
    • Neg for Wrapping<Uint<LIMBS>>
    • Modular multiplicative inverse
    • Computing parameters for the Montgomery form (MF)
    • Going to and from MF
    • Modular addition (in MF)
    • Modular multiplication (in MF)
    • Modular exponentiation (in MF)

    In my opinion, there are at least two large issues right now that I would like to hear your opinion on.

    • [x] The Modular interface is not satisfying to me because it copies the MontgomeryParameters and does not assert that two Modular integers indeed share the same modulus.
    • [x] None of the functions are currently const fn.

    Still, I thought it was good to already make a PR to bring this to your attention. I am happy to put in the effort to bring this to a point where it is mergeable! :)

    Edit: The modulus is now a constant and the struct is called Residue rather than Modular.

    opened by jellevos 31
  • dudect: add constant-time test for `UInt::reduce`

    dudect: add constant-time test for `UInt::reduce`

    Uses the dudect-bencher crate, a wrapper for the dudect C library:

    https://github.com/oreparaz/dudect

    Example output:

    running 1 bench
    bench reduce seeded with 0x2311ed8a8b8e6544
    bench reduce ... : n == +0.100M, max t = +1.98296, max tau = +0.00628, (5/tau)^2 = 634328
    
    dudect benches complete
    

    The important part here is max t = +1.98296. If t were to exceed 10, then the code is likely not constant time. Since it's well below 10, reduce appears to be OK.

    cc @andrewwhitehead @mikelodder7 @rozbb

    opened by tarcieri 18
  • Serde implementation

    Serde implementation

    Implemented serde::Deserialize and serde::Serialize for all types. This might be a bit overkill, implementing it for UInt might have been enough.

    As serde currently doesn't support const generics (serde-rs/serde#1937), I used serde-big-array for the UInt implementation. The dependency is quiet minimal, this PR also spawned est31/serde-big-array#14 to make sure that the dependency is as minimal as possible.

    I hope the tests are appropriate enough.

    opened by daxpedda 10
  • `random_mod` can take a very long time

    `random_mod` can take a very long time

    https://github.com/RustCrypto/utils/blob/710abc8c83a13def1c01958909405976f915e5a5/crypto-bigint/src/uint/rand.rs#L34-L42

    If modulus is small compared to the full size ("number of limbs * size of limb") then it can take "forever".

    The correct method is to mask off the top bits of the random number to match the size of modulus. This leads to a worst case of a 50% chance of failing and needing to generate another random number. The average for this worst case is needing to generate 2 random numbers.

    opened by Sc00bz 8
  • Add `SubResidue` trait and impls for `Residue` and `DynResidue`

    Add `SubResidue` trait and impls for `Residue` and `DynResidue`

    Not sure about adding neg():

    • Should there be a separate NegResidue trait, or should it be a part of SubResidue?
    • The default implementation (via SubResidue) would require an access to zero, and therefore an additional trait bound, which DynResidue does not implement.
    opened by fjarri 7
  • Add constant-time division by a single limb

    Add constant-time division by a single limb

    Based on https://gmplib.org/~tege/division-paper.pdf . This works ~100x faster than div_rem() for U256.

    For reviewers:

    • Suggestions on how exactly to expose the API (including the method naming) are welcome.
    • Should div_rem() and related methods take NonZero<Self> too, and this way avoid returning a CtOption?

    Changes:

    • Added public Uint methods: ct_div_rem_limb_with_reciprocal(), div_rem_limb_with_reciprocal(), div_rem_limb().
    • Added Div, Rem, DivAssign, and RemAssign implementations for the division by Limb.
    • Added public Reciprocal type (exported at the root level).
    • Added Limb::ct_lt() and ct_le() (constant time < and <=), with the return value applicable in ct_select().
    • Separated Uint::shl_vartime() into shl_vartime() proper (that only shifts by whole limbs and calls shl_limb()) and shl_limb() (shifts within one limb, constant-time).
    • Added benchmarks (division only for now).
    • Removed Uint<LIMBS>: Integer bound from Div, Rem, DivAssign, and RemAssign of Uint by Uint.
    • Division methods of Uint now take NonZero-wrapped arguments.

    TODO:

    • There are suggestions for implementing schoolbook division in the paper, so I think it may be worth it to try to compare that to the currently used algorithm. But that's better left for another PR.
    opened by fjarri 5
  • Fix constant-time behaviour for ct_reduce/ct_div_rem

    Fix constant-time behaviour for ct_reduce/ct_div_rem

    When using self.bits() instead of the full field width, run time could vary drastically depending on the input, for a modulus significantly smaller than the UInt size.

    opened by andrewwhitehead 5
  • [RFC] Is it possible to be both const generic and dynamic size

    [RFC] Is it possible to be both const generic and dynamic size

    Const generics and no-std are great features, both for performance and for interoperability. The down side is that some protocols require a dynamic moduli, and maybe even dynamic sizes, for example RSA sizes(2048/3072/4096/8192 etc), or DSA moduli sizes, and more.

    This gets more obvious with something like #28, which makes the type generic over the field, then you have to support a dynamic field to be able to support RSA, dynamic DSA moduli, groups with unknown order etc.

    My question is is it possible to win both worlds, and somehow both allow const generics for arrays, but also allow dynamic generation over vectors?

    opened by elichai 5
  • Wrong results for remainder ?

    Wrong results for remainder ?

    Confused about why this isn't working. Am i breaking some assumption?

            for (n, d, q, r) in &[
                (27,13,2,1),
                (26,13,2,0),
                (14,13,1,1),
                (13,13,1,0),
                (12,13,0,12), // reminder returns = 0
                (1,13,0,1), // reminder returns = 0
            ] {
                let lhs = U64::from_u8(*n);
                let rhs = U64::from_u8(*d);
                let expected_q = U64::from_u8(*q);
                let expected_r = U64::from_u8(*r);
                let (quot,rem) = lhs.div_rem(&rhs).unwrap();
                assert_eq!(expected_q, quot);
                assert_eq!(expected_r, rem);
            }
    
    opened by kaidokert 4
  • `UInt::{ct_div_rem, ct_reduce}` are not constant-time

    `UInt::{ct_div_rem, ct_reduce}` are not constant-time

    As noted in #115, both of these functions compute values and then pass them as the rhs to UInt::shl_vartime.

    • https://github.com/RustCrypto/crypto-bigint/blob/ed8d96b/src/uint/div.rs#L24
    • https://github.com/RustCrypto/crypto-bigint/blob/ed8d96b/src/uint/div.rs#L63

    cc @andrewwhitehead @mikelodder7

    opened by tarcieri 3
  • uint: Implement modulo operations for special moduli

    uint: Implement modulo operations for special moduli

    For a project of mine where the modulus can be chosen to be close to UInt::MAX, I created optimized implementations of modular operations. I thought maybe others can benefit from them, too, so I ported my implementation to the crypto-bigint crate.

    This commit implements modulo operations (neg, add, sub, mul) for special moduli that are so close to MAX that the difference to overflow fits in a single Limb. For such moduli, these new implementations are much faster than the existing generic modulus implementations. (For mul there's no comparison since there's no corresponding generic modulus implementation, yet.)

    For U256, I benchmarked the generic against the specialized implementations using criterion-rs on Intel Core i7-8565U @ 1.80GHz and obtained the following average times. Note that I used a const modulus known at compile-time, which enables some compiler optimizations after inlining. With a modulus known only at runtime, times might differ.

    | | U256::add_mod | U256::sub_mod | U256::mul_mod | |-|-|-|-| | generic (after #109 got merged) | 10.857 ns | 9.6262 ns | not implemented | | _special | 3.8276 ns | 4.1339 ns | 20.188 ns |

    opened by haslersn 3
  • Some fixes for modular inversion

    Some fixes for modular inversion

    • Break long lines in comments and tests and fix some hardcoded bit sizes
    • Fix the hardcoded Limb size in inv_odd_mod() - was set to 64 (did not cause errors, just made the inversion twice as slow on 32-bit targets)
    • Added inv_odd_mod_bounded() for cases of argument/modulus known to be small
    • Removed inv_odd_mod_option() - we do not provide such interface for other constant functions

    Tangentially related: what should we return as is_some in constant functions that can fail - Limb or Word? There are cases of both in the codebase.

    opened by fjarri 7
  • `num-traits` support (optional)

    `num-traits` support (optional)

    Currently num-traits is only in dev-dependencies.

    As originally suggested here it would be useful to have some support for traits for abstracting across bignum libraries, which would make it possible for e.g. the rsa crate to use either crypto-bigint or num-bigint-dig.

    Though num-traits probably lacks all of the requisite functionality to do that, it would get us quite a bit of the way there.

    opened by tarcieri 0
  • How to Calculate the Modular Multiplication of Three Specified Numbers?

    How to Calculate the Modular Multiplication of Three Specified Numbers?

    Here I have three numbers

        let p = U256::from_be_hex("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF");
        let a = U256::from_be_hex("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC");
        let b = U256::from_be_hex("28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93");
    
    

    So how to calculate (a * b) mod p?

    I found this function:

    pub const fn mul_mod_special(&self, rhs: &Self, c: Limb) -> Self {
       ... 
    }
    
    

    But I don't know how to determine the value of parameter c

    Could you help me?

    opened by CrayfishGo 1
  • split is implemented for U192 which doesn't seem to be correct on 64-bit platforms

    split is implemented for U192 which doesn't seem to be correct on 64-bit platforms

    Reading through some code, I unrelatedly noticed that pub const fn split(&self) is unconditionally implemented for U192. This doesn't seem to be correct on 64-bit platforms where U192 has an odd number of limbs.

    opened by haslersn 3
  • Is there a reason `random()` and `random_mod()` require `CryptoRng`?

    Is there a reason `random()` and `random_mod()` require `CryptoRng`?

    I would argue that it's the user's decision whether they want a cryptographically safe RNG used or not; there can be applications which do not require that restriction, and CryptoRng is just a marker trait and does not provide any additional functionality.

    opened by fjarri 4
  • Diverging from primitive behavior in overflowing shift

    Diverging from primitive behavior in overflowing shift

    The rust docs say the following about overflowing shift:

    If the shift value is too large, then value is masked (N-1) where N is the number of bits, and this value is then used to perform the shift. (Source: https://doc.rust-lang.org/std/primitive.u64.html#method.overflowing_shl) And you can see this via the following code:

    #[allow(arithmetic_overflow)]
    fn main() {
        let a: u64 = 500;
        let b = a << 119;
        println!("{}", b);
    }
    

    Which prints 18014398509481984000.

    On the other hand in the implementation here zeros will be returned: https://github.com/RustCrypto/crypto-bigint/blob/36dbb69a73cfdba1eef90e10a8424cde39602e3b/src/uint/shl.rs#L18

    opened by elichai 2
Owner
Rust Crypto
Cryptographic algorithms written in pure Rust
Rust Crypto
A crate for working with Ethereum beacon chain light client protocol messages. `no_std` friendly!

eth-lightclient-rs A crate for working with Ethereum beacon chain light client protocol messages. no_std friendly! !! For hacking and experimentation

Willem Olding 12 Jan 6, 2023
Mundane is a Rust cryptography library backed by BoringSSL that is difficult to misuse, ergonomic, and performant (in that order).

Mundane Mundane is a Rust cryptography library backed by BoringSSL that is difficult to misuse, ergonomic, and performant (in that order). Issues and

Google 1.1k Jan 3, 2023
Pairing cryptography library in Rust

bn This is a pairing cryptography library written in pure Rust. It makes use of the Barreto-Naehrig (BN) curve construction from [BCTV2015] to provide

Electric Coin Company Prototypes and Experiments 139 Dec 15, 2022
Pairing cryptography library in Rust

bn This is a pairing cryptography library written in pure Rust. It makes use of the Barreto-Naehrig (BN) curve construction from [BCTV2015] to provide

Parity Technologies 23 Apr 22, 2022
Ursa - Hyperledger Ursa is a shared cryptography library

HYPERLEDGER URSA Introduction Features Libursa Libzmix Dependencies Building from source Contributing Introduction Ursa was created because people in

Hyperledger 307 Dec 20, 2022
Generates a big overview of dependencies between microservices using pact-broker

Pact graph network Generates a schema of dependencies between microservices using pact-broker data. Table of contents Screenshots Tech Stack Features

ManoMano Tech 3 Dec 15, 2022
Example implementation for Biscuit tokens cryptography

example implementation for Biscuit token cryptography To aid in the implementation of Biscuit tokens in various languages, this repository contains an

Clever Cloud 6 May 25, 2021
Manage secret values in-repo via public key cryptography

amber Manage secret values in-repo via public key cryptography. See the announcement blog post for more motivation. Amber provides the ability to secu

FP Complete 82 Nov 10, 2022
Cryptography-related format encoders/decoders: PKCS, PKIX

RustCrypto: Formats Cryptography-related format encoders/decoders: PKCS, PKIX. Crates Name crates.io Docs Description base64ct Constant-time encoder a

Rust Crypto 112 Dec 20, 2022
Implementation of the Web Cryptography specification in Rust.

[wip] webcrypto Implementation of the Web Cryptography specification in Rust. This crate hopes to ease interoperability between WASM and native target

Divy Srivastava 5 Mar 7, 2022
BLS12-381 cryptography using Apache Milagro

BLS12-381 Aggregate Signatures in Rust using Apache Milagro WARNING: This library is a work in progress and has not been audited. Do NOT consider the

Sigma Prime 21 Apr 4, 2022
Traits - Collection of cryptography-related traits

RustCrypto: Traits Collection of traits which describe functionality of cryptographic primitives. Crates Name Algorithm Crates.io Docs MSRV aead Authe

Rust Crypto 401 Dec 27, 2022
Collect libraries and packages about cryptography in Rust.

Awesome Cryptography Rust Collect libraries and packages about cryptography in Rust. Collection Library Symmetric Public-key / Asymmetric One-way Hash

Rust Cryptography Community 282 Dec 25, 2022
A general solution for commonly used crypt in rust, collection of cryptography-related traits and algorithms.

Crypto-rs A general solution for commonly used crypt in rust, collection of cryptography-related traits and algorithms. This is a Rust implementation

houseme 4 Nov 28, 2022
A down-to-the-metal ongoing cryptography challenge designed by Radical Semiconductor.

woodpecker ?? [NOTE: scoreboard will now be updated weekends, starting the weekend of 12/10/2022--sorry for delays! I'll also be merging in pull reque

Radical Semiconductor 16 Dec 15, 2022
Elliptic curve cryptography on Soroban.

Elliptic Curve Cryptography on Soroban Contract examples and reusable primitives. Groth 16 verifier. This crate provides a SorobanGroth16Verifier obje

Xycloo Labs 5 Feb 10, 2023
Making composability with the Zeta DEX a breeze, FuZe provides CPI interfaces and sample implementations for on-chain program integration.

Zeta FuZe ?? Zeta FuZe FuZe is Zeta's cross-program integration ecosystem. This repository contains the Zeta Cross Program Invocation (CPI) interface

Zeta 39 Aug 27, 2022
the official Rust and C implementations of the BLAKE3 cryptographic hash function

BLAKE3 is a cryptographic hash function that is: Much faster than MD5, SHA-1, SHA-2, SHA-3, and BLAKE2. Secure, unlike MD5 and SHA-1. And secure again

BLAKE3 team 3.7k Jan 6, 2023
Elliptic-curves - Collection of pure Rust elliptic curve implementations (e.g. P-256, P-384, secp256k1)

RustCrypto: Elliptic Curves General purpose Elliptic Curve Cryptography (ECC) support, including types and traits for representing various elliptic cu

Rust Crypto 386 Dec 27, 2022