search

RustCrypto / crypto-bigint

Cryptography-oriented big integer library with constant-time, stack-allocated (no_std-friendly) implementations of modern formulas
Apache License 2.0
183 stars 52 forks source link

Feature wishlist tracking ticket #1

Open tarcieri opened 3 years ago

tarcieri commented 3 years ago

This is a ticket for tracking desired new features for crypto-bigint and which algorithms should be used in order to implement particular features.

Unless otherwise stated, these features are implied to be for the UInt type.

NOTE: for prime number support, see the crypto-primes crate

mikelodder7 commented 3 years ago
tarcieri commented 3 years ago

@mikelodder7 added to the list

random < n implemented in RustCrypto/utils#508. Will cut a release with that fairly soon.

Re: signed integers, yes that's definitely planned but not on this list yet, so thanks. Tentatively the idea is composing in terms of a UInt using two's complement.

Edit: released in v0.2.2 (#509)

mikelodder7 commented 3 years ago

How about bit tests? Check if bit at position i is set or cleared?

tarcieri commented 3 years ago

@mikelodder7 what kind of API are you looking for there?

Would a Choice suffice, or are you looking for a secret-dependent/vartime API?

mikelodder7 commented 3 years ago

Choice will suffice. Vartime not necessary.

ggutoski commented 3 years ago

Fast generation of safe primes would be great for RSA applications.

mikelodder7 commented 3 years ago

It’s also great for applications that require groups of unknown order based on prime factoring like accumulator, paillier, camenisch-shoup verifiable encryption

complexspaces commented 3 years ago

I'd like to add a +1 for implementingmodpow. It's useful in older protocols such as SRP.

tarcieri commented 3 years ago

@mikelodder7 it looks like it might be interesting to adapt the code in glass_pumpkin for (safe) prime generation, that is if we could get your blessing to license the resulting code as Apache 2.0+MIT

mikelodder7 commented 3 years ago

Of course. Glass pumpkin is already licensed as Apache 2 so adapting to be dual licensed is fine too. Consider this post my legal binding statement to authorize that work.

mikelodder7 commented 3 years ago

It will be nice to have it integrated directly into the big int library vs a bolt-on. Many operations can be simplified since the underlying int rep is accessible. We'll need modpow and reduce at a minimum.

tarcieri commented 3 years ago

Absolutely, that'd be the goal.

Generic modpow seems a bit tricky, or at least our last attempt at it didn't work.

One option would be to have a trait for it, and implement it for specific moduli.

mikelodder7 commented 3 years ago

What about using modular square and modular multiply and using conditional_select if the exponent bit is 1? Does that not work?

tarcieri commented 3 years ago

To be clear @dignifiedquire tried to add generic mulmod in RustCrypto/utils#510 but it was buggy so we backed it out.

It would be great to have a generic implementation.

Sc00bz commented 3 years ago

Doing a "better random < n" with https://github.com/apple/swift/pull/39143 in bigint is expensive compared to correct bigint rejection sampling (see RustCrypto/utils#618). As that requires multiplication of the modulus and a random number about 128 bits larger than the modulus. Basically that's O(N^2) vs O(N).

dignifiedquire commented 3 years ago

To be clear @dignifiedquire tried to add generic mulmod in RustCrypto/utils#510 but it was buggy so we backed it out.

I'll get there, soon (TM)

mikelodder7 commented 3 years ago

Need to update this list with completed features @tarcieri

tarcieri commented 3 years ago

@mikelodder7 should be updated now

newpavlov commented 3 years ago

Modular exponentiation?

Sc00bz commented 3 years ago

It's under "modular arithmetic" as "pow". Hmm "sqrt" and "inversions" should be under the "modular arithmetic" section.

tarcieri commented 3 years ago

Sorry, I reorganized the modular arithmetic section, and missed a few things along the way.

Note there is sqrt under modular arithmetic. However, I'll move inversions there.

Sc00bz commented 3 years ago

Oh I missed that. Is the other "sqrt" for floor(sqrt(n))?

P.S. I just re-found the edit history button and "pow" was added after @newpavlov's question. I thought there was edit history but it wasn't in the "…" menu.

mikelodder7 commented 3 years ago

The other sqrt is for generic number sqrt versus modular sqrt which can take some optimizations.

mikelodder7 commented 3 years ago

Both are important. Integer sqrt is used in the Lucas test for prime numbers for example.

tarcieri commented 3 years ago

Modular sqrt could potentially be helpful for the elliptic curve crates, although we're presently using an algorithm (Tonelli-Shank) specialized to the modulus (q mod 16 = 1).

I'm not sure what the best algorithm to use which isn't specialized to the modulus, or if it would make sense to select an algorithm based on the modulus size. The latter might make more sense if the modulus were a const generic parameter so the best algorithm could be selected at compile time.

dignifiedquire commented 3 years ago

I would suggest having the different algorithms behind specific methods, such that downstream implementors can choose the algorithm, eg fn sqrt_tonelli_shank().

kaidokert commented 3 years ago

Would completing full num_traits::PrimInt implementation to be a good goal ? I made a test branch with stubbed out functions here, it's not too hard to complete - with an optional num_traits dependency.

The main reason is it allows easily writing generic algos that take T: PrimInt as either bignum or builtin integers.

tarcieri commented 3 years ago

Optional num_traits support sounds great.

I would suggest following the same pattern as all the other functions that can presently support it which are currently impl'd on UInt (and Limb) though: add that functionality as const fn inherent methods, then add a trait wrapper for the inherent methods.

Based on a cursory survey of Primint, it looks like that should be possible for most if not all of those methods.

Edit: opened #158 to track num-traits support.

fjarri commented 1 year ago

Seems like it can be updated, all the modular arithmetic is done, and random primes are implemented by crypto-primes.

pinkforest commented 6 months ago

Should there be regular pow for Uint and BoxedUint types - like

tarcieri commented 6 months ago

@pinkforest all of the functionality in this crate is directly motivated by a specific cryptographic algorithm the functionality is intended to implement. What would be the purpose? Modular exponentiation is useful for DSA and RSA, but to my knowledge we have no use case for a non-modular pow.

We also implement fixed, not arbitrary, precision, and a non-modular pow can quickly overflow fixed-precision integers.

pinkforest commented 6 months ago

Thanks - Yeah my naive use-case was 1:1 porting existing use of vartime bigint and now think I should have skipped that -

Specifically deterministic RSA prime factor recovery as described by NIST.SP.800-56Br2 Appendix C.2 as was in rsa crate.

I should have re-evaluated it given the type for e is already below maximum size two.pow(256) and I can just simply do X::from(65536) to check minimum instead of ad-hoc two.pow(16) as you noted correctly - thanks!