RustCrypto
Uint::sub_mod weird behavior (bug?)
I might be wrong but I would expect that any _mod(...) operation would return the Uint in the range of [0, m) (or maybe [-m/2, m/2] for Int) , where m is the modulus.
However this is not the case for sub_mod where the resulting value is way off that range when rhs operand is not in the range.
Not sure is this is expected behavior (if it's not than fixing it would be breaking change), if it is, IMHO it should be documented that arguments must be reduced beforehand.
See example below:
#[test]
fn test_sub_mod() {
let x = U128::from_u128(1);
let y = U128::from_u128(40);
let m = U128::from_u128(35);
let z = x.sub_mod(&y, &m);
println!("z: {}", u128::from(z));
// prints z: 340282366920938463463374607431768211452
}
for comparison this is how sagemath compute this:
> (1 - 40) % 35
31
It does look like a bug where the current implementation doesn’t handle a modulus with a bit length smaller than the capacity of the underlying type
I think it is reasonable to require previously reduced arguments in a library aimed at high performance, because in most situations they would be. But I agree that it certainly should be documented.
It does look like a bug where the current implementation doesn’t handle a modulus with a bit length smaller than the capacity of the underlying type
I don't think the example demonstrates this, if the arguments are not reduced it's pretty much UB.
@fjarri we have the *Monty* types to optimize previously reduced operands.
The solution to this bug shouldn’t impact performance too much. We just need to wrap the initial subtraction at the bit length of the modulus as opposed to the bit length of the underlying type.
I certainly think that’s better than a miscomputation.
The argument may be reduced, or asserted to be smaller than the modulus, by some other code (e.g. during deserialization, or having been reduced with a smaller modulus). I think there's a value in providing a method that does not do additional work.
If you have a solution that does not do division to ensure the argument is reduced, that would be great, but I am not certain what you described above will work in all cases.
I agree with @fjarri. I don't think there is a way to fix that once and for all without doing expensive div/rem. Documenting that arguments must be reduced otherwise it's UB would be viable "fix" for me.
Still feels like a huge footgun to me. If you want to avoid the additional computation, what’s the problem with using the *Monty* types to ensure the inputs are properly Z/nZ to begin with?
If you're worried about safety, maybe we can rename these methods to *_mod_reduced or *_mod_unchecked?
One caviat, MontyForm supports only odd moduli AFAIR, _mod methods don't have this restrictions.
@lleoha that's a good point.
I guess I'd be okay with a fast sub_mod_unchecked that documents its caveats, but IMO sub_mod should never miscompute results.