From 9835e2ae736235810b4ea1c162ca5e65c547e770 Mon Sep 17 00:00:00 2001
From: Daniel Baumann <daniel.baumann@progress-linux.org>
Date: Sat, 18 May 2024 04:49:50 +0200
Subject: Merging upstream version 1.71.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
---
 vendor/crypto-bigint/src/uint/modular.rs | 163 +++++++++++++++++++++++++++++++
 1 file changed, 163 insertions(+)
 create mode 100644 vendor/crypto-bigint/src/uint/modular.rs

(limited to 'vendor/crypto-bigint/src/uint/modular.rs')

diff --git a/vendor/crypto-bigint/src/uint/modular.rs b/vendor/crypto-bigint/src/uint/modular.rs
new file mode 100644
index 000000000..ff20f443d
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular.rs
@@ -0,0 +1,163 @@
+mod reduction;
+
+/// Implements `Residue`s, supporting modular arithmetic with a constant modulus.
+pub mod constant_mod;
+/// Implements `DynResidue`s, supporting modular arithmetic with a modulus set at runtime.
+pub mod runtime_mod;
+
+mod add;
+mod inv;
+mod mul;
+mod pow;
+mod sub;
+
+pub use reduction::montgomery_reduction;
+
+/// A generalization for numbers kept in optimized representations (e.g. Montgomery)
+/// that can be converted back to the original form.
+pub trait Retrieve {
+    /// The original type.
+    type Output;
+
+    /// Convert the number back from the optimized representation.
+    fn retrieve(&self) -> Self::Output;
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{
+        const_residue, impl_modulus,
+        modular::{
+            constant_mod::Residue, constant_mod::ResidueParams, reduction::montgomery_reduction,
+        },
+        NonZero, Uint, U256, U64,
+    };
+
+    impl_modulus!(
+        Modulus1,
+        U256,
+        "73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001"
+    );
+
+    #[test]
+    fn test_montgomery_params() {
+        assert_eq!(
+            Modulus1::R,
+            U256::from_be_hex("1824b159acc5056f998c4fefecbc4ff55884b7fa0003480200000001fffffffe")
+        );
+        assert_eq!(
+            Modulus1::R2,
+            U256::from_be_hex("0748d9d99f59ff1105d314967254398f2b6cedcb87925c23c999e990f3f29c6d")
+        );
+        assert_eq!(
+            Modulus1::MOD_NEG_INV,
+            U64::from_be_hex("fffffffeffffffff").limbs[0]
+        );
+    }
+
+    impl_modulus!(
+        Modulus2,
+        U256,
+        "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"
+    );
+
+    #[test]
+    fn test_reducing_r() {
+        // Divide the value R by R, which should equal 1
+        assert_eq!(
+            montgomery_reduction::<{ Modulus2::LIMBS }>(
+                &(Modulus2::R, Uint::ZERO),
+                &Modulus2::MODULUS,
+                Modulus2::MOD_NEG_INV
+            ),
+            Uint::ONE
+        );
+    }
+
+    #[test]
+    fn test_reducing_r2() {
+        // Divide the value R^2 by R, which should equal R
+        assert_eq!(
+            montgomery_reduction::<{ Modulus2::LIMBS }>(
+                &(Modulus2::R2, Uint::ZERO),
+                &Modulus2::MODULUS,
+                Modulus2::MOD_NEG_INV
+            ),
+            Modulus2::R
+        );
+    }
+
+    #[test]
+    fn test_reducing_r2_wide() {
+        // Divide the value R^2 by R, which should equal R
+        let (hi, lo) = Modulus2::R.square().split();
+        assert_eq!(
+            montgomery_reduction::<{ Modulus2::LIMBS }>(
+                &(lo, hi),
+                &Modulus2::MODULUS,
+                Modulus2::MOD_NEG_INV
+            ),
+            Modulus2::R
+        );
+    }
+
+    #[test]
+    fn test_reducing_xr_wide() {
+        // Reducing xR should return x
+        let x =
+            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
+        let product = x.mul_wide(&Modulus2::R);
+        assert_eq!(
+            montgomery_reduction::<{ Modulus2::LIMBS }>(
+                &product,
+                &Modulus2::MODULUS,
+                Modulus2::MOD_NEG_INV
+            ),
+            x
+        );
+    }
+
+    #[test]
+    fn test_reducing_xr2_wide() {
+        // Reducing xR^2 should return xR
+        let x =
+            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
+        let product = x.mul_wide(&Modulus2::R2);
+
+        // Computing xR mod modulus without Montgomery reduction
+        let (lo, hi) = x.mul_wide(&Modulus2::R);
+        let c = hi.concat(&lo);
+        let red = c.rem(&NonZero::new(U256::ZERO.concat(&Modulus2::MODULUS)).unwrap());
+        let (hi, lo) = red.split();
+        assert_eq!(hi, Uint::ZERO);
+
+        assert_eq!(
+            montgomery_reduction::<{ Modulus2::LIMBS }>(
+                &product,
+                &Modulus2::MODULUS,
+                Modulus2::MOD_NEG_INV
+            ),
+            lo
+        );
+    }
+
+    #[test]
+    fn test_new_retrieve() {
+        let x =
+            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
+        let x_mod = Residue::<Modulus2, { Modulus2::LIMBS }>::new(&x);
+
+        // Confirm that when creating a Modular and retrieving the value, that it equals the original
+        assert_eq!(x, x_mod.retrieve());
+    }
+
+    #[test]
+    fn test_residue_macro() {
+        let x =
+            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
+        assert_eq!(
+            Residue::<Modulus2, { Modulus2::LIMBS }>::new(&x),
+            const_residue!(x, Modulus2)
+        );
+    }
+}
-- 
cgit v1.2.3