Feature wishlist tracking ticket

[tarcieri]

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.

• signed integers (#700)
• addition/subtraction
• multiplication algorithms
  • "schoolbook"
  • Karatsuba
• sqrt
• modular arithmetic
  • add
  • subtract
  • multiply
  • negate
  • modulus
  • pow
  • sqrt
  • inversions
• bitwise operations (request other ops in comments)
  • shift
  • rotate
  • XOR
• fields mod n (i.e. wrapper newtypes for UInt)
• constant-time division
  • by 2 (useful for elliptic-curve crates)
  • arbitrary
• subtle comparisons
  • ConstantTimeEq
  • ConstantTimeGreater
  • ConstantTimeLess
• CRT (algorithms listed below)
  • Smooth RSA-CRT
  • https://eprint.iacr.org/2020/1507 (note: appears to be covered by patents)
• LCM
• GCD (algorithms listed below)
  • safegcd (a.k.a. Bernstein-Yang)
  • safegcd-bounds (#634)
• RNG
  • random < n
  • better random < n
  • random prime (use crypto-primes instead)
• Hardware acceleration / assembly (see also #572)
  • x86/x86_64
    • ADX
    • MULX
    • AVX2
  • ARM
    • NEON

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

[mikelodder7]

• Prime generation
• Random < n
• Least common multiple
• Negative numbers
• Inverse (available if gcd exists but nice convenience)

[tarcieri]

@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]

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

[tarcieri]

@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]

Choice will suffice. Vartime not necessary.

[ggutoski]

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

[mikelodder7]

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

[complexspaces]

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

[tarcieri]

@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]

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]

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]

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]

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

[tarcieri]

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]

Doing a "better random < n" with swiftlang/swift#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]

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]

Need to update this list with completed features @tarcieri

[tarcieri]

@mikelodder7 should be updated now

[newpavlov]

Modular exponentiation?

[Sc00bz]

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

[tarcieri]

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]

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]

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

[mikelodder7]

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

[tarcieri]

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]

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

[kaidokert]

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]

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]

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

[pinkforest]

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

• https://docs.rs/num-bigint-dig/latest/src/num_bigint_dig/biguint.rs.html#501

[tarcieri]

@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]

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!

[erik-3milabs]

Note: #624 was superseded by #700.