Closed fjarri closed 7 months ago
UintLike
looks a lot like crypto_bigint::Integer
, although it will need changes to be able to support dynamically sized types and because of that isn't yet impl'd for BoxedUint
Almost, yes, save for Copy
, Zero
, associated constants, and a link to the Montgomery representation, which can be a separate trait. I was thinking of finishing up https://github.com/RustCrypto/crypto-bigint/pull/218 while we're at it.
@fjarri aside from a link to the Montgomery representation, this should take care of the other issues: https://github.com/RustCrypto/crypto-bigint/pull/367
It takes care of some of them, but not all - e.g. vartime ops, bit operations, division, etc are still not in traits. Also it would be nice to have *Assign
arithmetic operations and arithmetic operations on &Self
, although it is not critical for the performance.
Feel free to open PRs to add whatever functionality you'd like which has common impls on both types. Or just tell me specifically what you want and I can get them added.
The bit operations should be fine to add (although Uint
could really use a constant-time bits, which I added for BoxedUint
).
Division is present but perhaps you want something more.
The *Assign
ops should be fine.
I don't think there's really a way to bound on impls on the reference type in a trait's bounds itself. You can do that with extra where
bounds as needed (since you'd need to do something like &U: Mul
)
I'd like to help out with the implementation of core functionalities using BoxedUint
! Is there something that I can get started with?
It seems like there are a lot of functions parameterized by <L: usize>
that can be transformed into a function that takes an argument bits_precision: u32
, is that right? I can start implementing them right away.
Thank you!
This PR already includes all the necessary transition to numeric traits instead of const usize
generic parameters, we just need to move all those traits to crypto-bigint
. See uint_traits.rs
for the list of the required functionality.
This PR already includes all the necessary transition to numeric traits instead of
const usize
generic parameters, we just need to move all those traits tocrypto-bigint
. Seeuint_traits.rs
for the list of the required functionality.
After pulling this branch it seems that the trait in uint_traits.rs
is incomplete and this crate will not build. @fjarri @tarcieri if no one else is working on the UintLike
trait and/or implementing these traits for Uint/BoxedUint
, I would love to help out!
Thank you!
@tarcieri has been implementing necessary methods for BoxedUint
, and I have been occupied with other work and haven't been updating this PR for a while. I was planning to do so after the PRs in https://github.com/RustCrypto/crypto-bigint/issues/268 are merged.
@xuganyu96 the relevant trait in crypto-bigint
is Integer
, which is already impl'd for both Uint
and BoxedUint
but needs to be expanded with what's missing from UintLike
: https://docs.rs/crypto-bigint/0.6.0-pre.1/crypto_bigint/trait.Integer.html
@tarcieri has been implementing necessary methods for
BoxedUint
, and I have been occupied with other work and haven't been updating this PR for a while. I was planning to do so after the PRs in RustCrypto/crypto-bigint#268 are merged.
@tarcieri @fjarri I've taken a try and found the scope of work manageable (see #37 for my progress). If you don't mind I can take over the remainder of the transition (I am a grad student currently on winter break and so I'm looking for work to do anyways). Thank you!
All modified and coverable lines are covered by tests :white_check_mark:
Comparison is base (
45152ad
) 99.21% compared to head (265696b
) 99.20%.
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
Ok, finally the tests pass.
Remaining things in UintLike
:
RandomMod
(not included in Integer
, but perhaps it should be?)crypto-bigint
?)crypto-bigint
?)random_bits(rng, bit_length: u32)
method. Currently there's nothing for that in Integer
. What should the API be like (e.g. should it return an Option
or panic when bit_length
is larger than the total bit length in Uint
)?TryInto<u32>
or alternatively TryInto<Limb>
(although I can implement it via as_ref<[Limb]>()
and bit counting). @tarcieri, what's your take on this?
The reason Random
/RandomMod
aren't included in Integer
is because rand_core
is currently an optional dependency. We could make it a hard dependency potentially.
Traits for vartime bitshifts sound OK.
There are already various bit counting methods defined on Integer
, like bits
, bits_vartime
, and trailing_zeros
. Which ones are missing? (e.g. leading_zeros
I guess?)
some random_bits(rng, bit_length: u32) method. Currently there's nothing for that in Integer. What should the API be like (e.g. should it return an Option or panic when bit_length is larger than the total bit length in Uint)?
Something like how BoxedUint::random
is defined I guess?
How would TryInto<Limb>
work?
There are already various bit counting methods defined on Integer, like bits, bits_vartime, and trailing_zeros. Which ones are missing? (e.g. leading_zeros I guess?)
trailing_zeros()
, trailing_ones()
, and bit_vartime()
Something like how BoxedUint::random is defined I guess?
Well, that's the question: in case of Uint
when bits_precision
is too large, what's the behavior?
On a side note, I think bits_precision
in BoxedUint::random()
should be renamed to bit_length
.
How would TryInto
work?
If the number fits in one Limb
, return that limb, otherwise None
.
Well, that's the question: in case of Uint when bits_precision is too large, what's the behavior?
We'd need a fallible trait/method to cover both cases.
On a side note, I think bits_precision in BoxedUint::random() should be renamed to bit_length.
It matches BoxedUint::bits_precision()
. Do you think it should be renamed everywhere?
It matches BoxedUint::bits_precision().
Not really. BoxedUint::bits_precision()
returns the storage size of BoxedUint
. the bits_precision
in random()
denotes how large the actual number will be, which is different from the storage size.
In fact, BoxedUint::random()
could have both bit_length
and (possibly optional) bits_precision
parameters, to avoid reallocation when widening to the required storage size.
There are already various bit counting methods defined on Integer, like bits, bits_vartime, and trailing_zeros. Which ones are missing? (e.g. leading_zeros I guess?)
trailing_zeros()
,trailing_ones()
, andbit_vartime()
Something like how BoxedUint::random is defined I guess?
Well, that's the question: in case of
Uint
whenbits_precision
is too large, what's the behavior?
BoxedUint::trailing_zeros
, BoxedUint::trailing_ones()
, and BoxedUint::bit_varitme()
have all been implemented and merged in https://github.com/RustCrypto/crypto-bigint/pull/489.
It matches BoxedUint::bits_precision().
Not really.
BoxedUint::bits_precision()
returns the storage size ofBoxedUint
. thebits_precision
inrandom()
denotes how large the actual number will be, which is different from the storage size.In fact,
BoxedUint::random()
could have bothbit_length
and (possibly optional)bits_precision
parameters, to avoid reallocation when widening to the required storage size.
In my attempt here, bit_length
and bits_precision
indeed need to be separated out into two arguments. This is entirely understandable for BoxedUint
, but it is a little awkward to use with Uint
since bits_precision
is a piece of redundant information that the user will have to fill in. See the code snippet below:
fn main() {
// with BoxedUint, separating bit_length and bits_precision is entirely understandable
// "I want a random number that takes 128 bits to store and 64 bits to represent
let random_odd = BoxedUint::random(&mut OsRng, 64, 256);
// with Uint, bits_precision is exactly Uint::BITS, which might be a bit confusing
// but with clear documentation and some `assert!` I think we can communicate the idea to the users
let random_odd: U256 = U256::random(&mut OsRng, 64, U256::BITS);
}
In practice this means that functions like generate_prime
will also need to take bit_length
and bits_precision
as separate argument regardless of whether the user is using BoxedUint
or Uint
:
let stacked_prime: U256 = generate_prime(&mut OsRng, 64, U256::BITS);
let heaped_prime: BoxedUint = generate_prime(&mut OsRng, 64, 256);
The two uncovered lines in _is_prime_with_rng()
were uncovered previously. It's hard to find a number that would pass through the first MR test and the Lucas test, but not the second MR test. And the branch that returns Prime
from the Lucas test is inactive because all such numbers were already sieved out at the Sieve
stage.
Potentially fixes #34
In order to add the support for
BoxedUint
we need to make all the methods parametrized by someUintLike
trait instead of the number of limbs inUint
. This PR attempts to see what kind of methods are necessary. Seeuint_traits.rs
for what needs to be implemented incrypto-bigint
.UintLike
andUintModLike
can potentially be split into smaller traits.Notes:
::BITS
anymore, so we need to change the API to getbit_length: usize
instead ofOption<usize>
everywhere&Self
, which means there are some potentially unnecessaryclone()
s involved, especially inlucas()
(unless we want to write down scary trait bounds, which we really don't).