Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Determine and document BoxedUint widening arithmetic semantics #312

Open
tarcieri opened this issue Nov 26, 2023 · 2 comments
Open

Determine and document BoxedUint widening arithmetic semantics #312

tarcieri opened this issue Nov 26, 2023 · 2 comments

Comments

@tarcieri
Copy link
Member

Arithmetic with BoxedUint needs to deal with values whose number of limbs don't match. This is true of Uint as well, but there everything is nicely type safe.

So far the internal BoxedUint::chain operation (which addition and subtraction are implemented in terms of) handles widening to the widest of the two inputs.

The wrapping_* and checked_* functions use the self/left-hand side argument as the overflow width.

The mul_wide operation widens to as many limbs as are in the sum of the number of limbs in the operands (though should perhaps be renamed to just BoxedUint::mul for consistency with Uint::mul, which is also a widening multiply.

This seems like a reasonable enough approach, but whatever one we take should be thoroughly documented, both as an overall policy and on the individual functions.

We should also ensure it's consistent with how Uint performs widening, where applicable.

tarcieri added a commit that referenced this issue Nov 28, 2023
Several functions on the `Boxed*` types don't yet support implicit
widening (#312) and will panic if two or more operands are not the same
size (NOTE: we should eventually fix this)

Some of these functions previously had debug asserts that the number of
limbs are equal, however that's less helpful information when trying to
debug these problems than the precision in bits.

This changes all of the assertions for size equality to use
`bits_precision`.
tarcieri added a commit that referenced this issue Nov 28, 2023
Several functions on the `Boxed*` types don't yet support implicit
widening (#312) and will panic if two or more operands are not the same
size (NOTE: we should eventually fix this)

Some of these functions previously had debug asserts that the number of
limbs are equal, however that's less helpful information when trying to
debug these problems than the precision in bits.

This changes all of the assertions for size equality to use
`bits_precision`.
@tarcieri
Copy link
Member Author

I should probably add some context that these semantics are necessarily different from your typical num-bigint-style arbitrary precision library.

Notably in cryptographic cases we want all of the values to be the same precision, or if not that, then known/fixed precisions at every point in the program. In the case of an algorithm like RSA, that would be the number of bits of precision in the RSA modulus. This means preserving leading zero limbs in such cases, so that we don't wind up with value-dependent timing variability with respect to the number of limbs.

@xuganyu96
Copy link
Contributor

Automatic widening when instantiating BoxedMontyForm should also be considered here. BoxedMontyForm::new currently panics if integer and params have different precision, but I think it makes sense to automatically widen the integer if it is less precise than the params. I am not sure if we should consider widening the params since it has more moving parts.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants