MulMod not implemented and not properly documented

[haslersn]

It would be nice if the trait MulMod could be implemented.

Furthermore, the current documentation (v0.3.2) states that mul_mod

Requires p_inv = -(p^{-1} mod 2^{BITS}) mod 2^{BITS} to be provided for efficiency.

However, any even p is not invertible. An even p might be used e.g. when computing over a ring rather than a prime field. So, how should p_inv be set if p is even?

[tarcieri]

It would be nice if the trait MulMod could be implemented.

We attempted to, and the trait still being around is a vestige of that. See:

• experimental: add modulo operations to UInt utils#510
• crypto-bigint: add modulo operations to UInt utils#561

The attempted implementation was incorrect, so it did not land with the rest of the modular arithmetic. It would be beneficial for quite a few projects if we could get it working, though.

So, how should p_inv be set if p is even?

The trait in its current form is specialized to a Montgomery reduction, where typically the modulus is odd.

I'm not terribly familiar with how to do a Montgomery reduction with an even modulus (in all of the @RustCrypto project's applications which could benefit from a generic MulMod the modulus is prime).

Here's a paper I found on Montgomery reductions with an even modulus: http://www.people.vcu.edu/~jwang3/CMSC691/j34monex.pdf

[haslersn]

For an even modulus m one can probably do the following: Decompose m =: 2^k * n such that n is odd. Then perform the multiplication separately mod 2^k and mod n, and combine the results using CRT. But maybe it doesn't work, because the recombination again requires multiplication mod m?

[haslersn]

The trait in its current form is specialized to a Montgomery reduction

@tarcieri Wikipedia says:

The need to convert a and b into Montgomery form and their product out of Montgomery form means that computing a single product by Montgomery multiplication is slower than the conventional or Barrett reduction algorithms.

Did you take this into account when chosing Montgomery multiplication?

[haslersn]

Looking at the old implementation, it looks like it doesn't bring the number into Montgomery form before calling mont_reduce. Maybe that's the reason why it didn't work back then?

[tarcieri]

Yes, that is definitely why it didn't work.

We use both Montgomery and Barrett reductions in the https://github.com/rustcrypto/elliptic-curves crates (for base and scalar field elements respectively, although the latter only for p256) and the fact we have modular multiplication implemented already on a base/scalar field-by-field basis means we haven't been particularly motivated to implement a generic solution in crypto-bigint yet, although it would hypothetically be useful for migrating the dsa and rsa crates off of num-bigint-dig.

For the elliptic curve crates specifically we generally perform a sequence of operations on field elements in Montgomery form, and thus the overhead of converting to/from Montgomery form is ammortized.

There's a question of how to expose values in Montgomery form. There have been various problems with using the same type for both, namely confusing which form a particular value/field element is in. As such I've largely moved the crates to where the crypto-bigint::UInt is used to represent canonical form, and the respective FieldElement types (which are UInt internally) are always in Montgomery form. This makes the conversions type safe.

I'd love to add a generic FieldElement type to crypto-bigint, which similarly could always be in Montgomery form, but I was considering using const generics to represent the modulus (so field elements with a particular modulus are inherently type safe). Unforutnately that requires const generic features (valtrees) which haven't been implemented yet. Using const generics for this could also select optimized algorithms based on properties of the modulus at compile time, which would hypothetically provide efficiency gains.

We've considered porting over @cronokirby's implementation of modexp using Montgomery multiplication here: https://github.com/cronokirby/saferith/blob/08ff755fd8f7e060d9756857368435c53540d83b/num.go#L1361

...but I'd agree there's a case to be made for using a Barrett reduction instead in the event the inputs and outputs are all in canonical form.

[haslersn]

I was considering using const generics to represent the modulus

That's also what I'm doing in my project.

Unforutnately that requires const generic features (valtrees)

For what exactly do you need them? I'm on stable rustc 1.60.0 and do it like this:

pub trait ResidueParameters<const L: usize>: PartialEq + Debug {
    const MODULUS: Option<UInt<L>>;
}

#[derive(PartialEq)]
pub struct Residue<P, const L: usize>
where
    P: ResidueParameters<L>,
{
    repr: UInt<L>,
    phantom: PhantomData<P>,
}

I call it Residue instead of FieldElement, because the modulus doesn't need to be prime, so it's not necessarily a field. A modulus of None represents UInt::<L>::MAX + 1 where the native wrapping of the UInt type is used.

[tarcieri]

There's various ways to work within the limits of what's available on stable now.

For what exactly do you need them?

That works but is a bit clunky as you have to crate a ZST and impl ResidueParameters for it, versus just being able to pass the modulus as a const generic parameter:

pub struct Residue<const LIMBS: usize, const MODULUS: UInt<LIMBS>> { ... }

This will be possible after valtrees are implemented.

[tarcieri]

I think for starters we can implement MulMod (with breaking changes) using a Barrett reduction, and then circle back on FieldElement/Residue when adt_const_params are stable.

[ycscaly]

Now that it seems that valtrees have been implemented, where is this standing?

[ycscaly]

Also, can't the *Mod (esp. MulMod) traits be implemented with DynResidue ?

And why isn't there a PowMod trait? There is a pow() function for DynResidue.

[tarcieri]

Now that it seems that rust-lang/rust#95174, where is this standing?

As that issue notes, implementing valtrees is step 1 of 5. We target stable Rust, so we need all of those steps complete to make use of the feature.

Also, can't the *Mod (esp. MulMod) traits be implemented with DynResidue ?

All *Residue ops are definitionally modular, except the rhs is stored in self, so it doesn't match the signature of the trait.

And why isn't there a PowMod trait? There is a pow() function for DynResidue.

That is a notable API gap in the traits.

[ycscaly]

Now that it seems that rust-lang/rust#95174, where is this standing?

As that issue notes, implementing valtrees is step 1 of 5. We target stable Rust, so we need all of those steps complete to make use of the feature.

It seems that they also closed the issue after this step, and from my understanding that's because what has been implemented should suffice at least partially?

Also, can't the *Mod (esp. MulMod) traits be implemented with DynResidue ?

All *Residue ops are definitionally modular, except the rhs is stored in self, so it doesn't match the signature of the trait.

I'm not sure I understand what "rhs is stored in self" means. The signature is that a Uint gets an rhs of the same type, and a modulo of the same type and returns the same type right?

So if I:

1. create a DynResidueParams from p, use that to create a DynResidue of both self and rhs, add them, and then retrieve() and return the result - why wouldn't this match the signature of the trait ?

And why isn't there a PowMod trait? There is a pow() function for DynResidue.

That is a notable API gap in the traits.

Can't such an API be easily added?
Should I open a new issue for that?

[tarcieri]

It seems that they also closed the issue after this step

Huh? rust-lang/rust#95174 is still open and only the first checkbox of 5 is checked.

Though the feature exists on nightly that doesn't help us, because we target stable.

why wouldn't this match the signature of the trait ?

Because the modulus is stored in self, as opposed to being an explicit rhs parameter, which is what the trait expects.

Unless you're proposing there's a second modulus, which doesn't make sense to me?

Can't such an API be easily added?
Should I open a new issue for that?

Yes

[ycscaly]

It seems that they also closed the issue after this step

Huh? rust-lang/rust#95174 is still open and only the first checkbox of 5 is checked.

Though the feature exists on nightly that doesn't help us, because we target stable.

It is locked for discussion, which made me assume it is closed, sorry.

why wouldn't this match the signature of the trait ?

Because the modulus is stored in self, as opposed to being an explicit rhs parameter, which is what the trait expects.

Unless you're proposing there's a second modulus, which doesn't make sense to me?

I'm not sure I get it. E.g. for AddMod there's three prams there, one of them is the Modulus:
fn add_mod(&self, rhs: &Rhs, p: &Self) -> Self::Output;
what do you mean by it being stored in Self?

Can't such an API be easily added?
Should I open a new issue for that?

Yes

Will do. Should this also address traits for AddMod, MulMod etc that we could implement using DynResidue ?

[tarcieri]

what do you mean by it being stored in Self?

DynResidue stores its own modulus: https://github.com/RustCrypto/crypto-bigint/blob/master/src/uint/modular/runtime_mod.rs#L22

So it doesn't need AddMod, because Add is modular addition, with the modulus already known a priori, so it doesn't need to be passed as an explicit parameter: https://github.com/RustCrypto/crypto-bigint/blob/master/src/uint/modular/runtime_mod/runtime_add.rs#L21

Should this also address traits for AddMod, MulMod etc that we could implement using DynResidue ?

Again, I don't think it makes sense to implement those traits for DynResidue

[ycscaly]

what do you mean by it being stored in Self?

DynResidue stores its own modulus: https://github.com/RustCrypto/crypto-bigint/blob/master/src/uint/modular/runtime_mod.rs#L22

So it doesn't need AddMod, because Add is modular addition, with the modulus already known a priori, so it doesn't need to be passed as an explicit parameter: https://github.com/RustCrypto/crypto-bigint/blob/master/src/uint/modular/runtime_mod/runtime_add.rs#L21

Should this also address traits for AddMod, MulMod etc that we could implement using DynResidue ?

Again, I don't think it makes sense to implement those traits for DynResidue

Yeah I know how DynResidue works, but I need a type that has both normal "over the intigers" bigint operations and modular operations.

This is why I think it does make sense to implement these traits.

Because now we have either-or. Either you're using an e.g. U2048 with over the integers operations, or you're using a DynResidue that allows you finite field operations. But e.g. for Paillier I need both.

[tarcieri]

But what would you be passing as the modulus? self.modulus? And what is it supposed to do if you pass a different modulus? Reduce twice? It doesn't make sense.

Also why are you doing modular arithmetic with both DynResidue and Uint? Why not do all of your modular arithmetic with one or the other, especially in generic code?

[tarcieri]

Because now we have either-or. Either you're using an e.g. U2048 with over the integers operations, or you're using a DynResidue that allows you finite field operations. But e.g. for Paillier I need both.

Why do you need the exact same set of traits on both, especially when those traits don't make sense to implement?

[ycscaly]

Let me rephrase.

I'd like to write a decrypt<T>(decryption_key: &T, encryption_key: &T, ciphetext: &T) -> T function that does Paillier decryption.

Paillier decryption first raises the ciphertext c to the power of the decryption key d modulo the sqaure of the encryption key n^2. For this, I would need a trait bound for T that allows me to exponentiate given a specific modulus.

Next, we switch to work over the integers to perform L which takes the above result and decrease one from it and divides by n. So I need a trait bound for T that satisfies division over the integers.

Now, we need to think of that result again as in a finite field but this time mod n and not n^2, and do modular multiplication with the inverse of the decryption key d^-1. So again, we need a trait bound that allows modular multiplication (and the modulus shouldn't be fixed).

I can and have written such code using crypto-bigint directly, but want to decouple myself and work over traits instead, and have crypto-bigint implement these traits e.g. for U4096.

I think that's possible, maybe the current traits aren't the ones to satisfy it tho.

let me know if this makes sense now, and I'll open an issue for this.

[fjarri]

I actually have written Paillier encryption working via traits for a library at work. It is possible, but it is not pleasant (in part because Rust can be quite daft about trait bounds sometimes). I have two traits, UintLike and UintModLike with different sets of methods, one convertible to another. Also there is a HasWide trait to convert integers to double-size (to deal with N^2 moduli).

[tarcieri]

@fjarri what's does UintLike add beyond the Integer trait?

We could potentially add an Unsigned trait.

[fjarri]

Currently it's

pub trait UintLike:
    Integer
    + JacobiSymbolTrait
    + Hashable
    + RandomPrimeWithRng
    + RandomMod
{
    // TODO: do we really need this? Or can we just use a simple RNG and `random_mod()`?
    fn hash_into_mod(reader: &mut impl XofReader, modulus: &NonZero<Self>) -> Self;
    fn add_mod(&self, rhs: &Self, modulus: &NonZero<Self>) -> Self;
    fn trailing_zeros(&self) -> usize;
    fn inv_odd_mod(&self, modulus: &Self) -> CtOption<Self>;
    fn inv_mod2k(&self, k: usize) -> Self;
    fn wrapping_sub(&self, other: &Self) -> Self;
    fn wrapping_mul(&self, other: &Self) -> Self;
    fn wrapping_add(&self, other: &Self) -> Self;
    fn bits(&self) -> usize;
    fn bit(&self, index: usize) -> Choice;
    fn neg(&self) -> Self;
    fn neg_mod(&self, modulus: &Self) -> Self;
}

(JacobiSymbolTrait and Hashable are internal)

Edit: now that I look at Integer, I can remove some of the bounds.
Edit: removed quite a few. Still, I need access to some methods (see the trait) that are not in any trrait in crypto-bigint, so I have to implement them manually or via a macro.

[fjarri]

These are the other two traits I mentioned:

pub trait UintModLike:
    Pow<Self::RawUint>
    + core::fmt::Debug
    + Add<Output = Self>
    + Neg<Output = Self>
    + Copy
    + Clone
    + PartialEq
    + Eq
    + Retrieve<Output = Self::RawUint>
    + Invert<Output = CtOption<Self>>
    + Mul<Output = Self>
    + Sub<Output = Self>
    + for<'a> Mul<&'a Self, Output = Self>
{
    type RawUint: UintLike;
    fn new(value: &Self::RawUint, modulus: &NonZero<Self::RawUint>) -> Self;
}

pub trait HasWide: Sized + Zero {
    type Wide: UintLike;
    fn mul_wide(&self, other: &Self) -> Self::Wide;
    fn square_wide(&self) -> Self::Wide;
    fn into_wide(self) -> Self::Wide;
    fn from_wide(value: Self::Wide) -> (Self, Self);
    fn try_from_wide(value: Self::Wide) -> Option<Self> {
        let (hi, lo) = Self::from_wide(value);
        if hi.is_zero().into() {
            return Some(lo);
        }
        None
    }
}

Edit: I am planning to add a generic method to create Montgomery params separately instead of doing it internally; this is just scaffolding for now.

[tarcieri]

Yeah, definitely some gaps in what is possible via traits right now.

Perhaps we should look into what is available in num-traits as far as that goes.