mpvss_rs/groups/
modp.rs

1// Copyright 2020-2026 MathxH Chen.
2//
3// Code is licensed under MIT Apache Dual License
4
5//! MODP group implementation using RFC 3526 2048-bit safe prime.
6//!
7//! This is the original implementation from the MPVSS library, refactored
8//! to implement the `Group` trait.
9
10use num_bigint::{BigInt, BigUint, RandBigInt, ToBigInt};
11use num_integer::Integer;
12use num_primes::Generator;
13use num_traits::identities::{One, Zero};
14use sha2::{Digest, Sha256};
15use std::sync::Arc;
16
17use crate::group::Group;
18
19/// 2048-bit MODP Group from RFC 3526 (Group ID 14)
20///
21/// # Group Parameters
22/// - `q`: Safe prime (2048-bit)
23/// - `g`: Sophie Germain prime = (q-1)/2 (subgroup order)
24/// - `G`: Generator = 2
25///
26/// The prime is: 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
27#[derive(Debug, Clone)]
28#[allow(non_snake_case)]
29pub struct ModpGroup {
30    /// Safe prime (group modulus)
31    q: BigInt,
32    /// Sophie Germain prime (subgroup order)
33    g: BigInt,
34    /// Main generator (value 2)
35    G: BigInt,
36    /// Cached q - 1 (group order)
37    q_minus_1: BigInt,
38}
39
40impl ModpGroup {
41    /// Create a new MODP group using RFC 3526 2048-bit prime
42    pub fn new() -> Arc<Self> {
43        // RFC 3526 2048-bit MODP group (ID 14)
44        // Prime: 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
45        let q: BigUint = BigUint::parse_bytes(
46            b"ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74\
47              020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1\
48              356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb\
49              5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d\
50              39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d67\
51              0c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a\
52              2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa0\
53              51015728e5a8aacaa68ffffffffffffffff",
54            16,
55        )
56        .unwrap();
57        let g: BigUint = (q.clone() - BigUint::one()) / BigUint::from(2_u64);
58
59        Arc::new(ModpGroup {
60            q: q.to_bigint().unwrap(),
61            g: g.to_bigint().unwrap(),
62            G: BigInt::from(2),
63            q_minus_1: q.to_bigint().unwrap() - BigInt::one(),
64        })
65    }
66
67    /// Initialize a MODP group by generating a safe prime of `length` bits
68    pub fn init(length: u32) -> Arc<Self> {
69        let q: BigUint = Generator::safe_prime(length as usize);
70        let g: BigUint = (q.clone() - BigUint::one()) / BigUint::from(2_u64);
71
72        Arc::new(ModpGroup {
73            q: q.to_bigint().unwrap(),
74            g: g.to_bigint().unwrap(),
75            G: BigInt::from(2),
76            q_minus_1: q.to_bigint().unwrap() - BigInt::one(),
77        })
78    }
79
80    /// Get the safe prime modulus q
81    pub fn modulus(&self) -> &BigInt {
82        &self.q
83    }
84
85    /// Get the subgroup order g (Sophie Germain prime)
86    pub fn subgroup_order_value(&self) -> &BigInt {
87        &self.g
88    }
89}
90
91impl Group for ModpGroup {
92    type Scalar = BigInt;
93    type Element = BigInt;
94
95    fn order(&self) -> &Self::Scalar {
96        &self.q_minus_1
97    }
98
99    fn subgroup_order(&self) -> &Self::Scalar {
100        &self.g
101    }
102
103    fn generator(&self) -> Self::Element {
104        self.G.clone()
105    }
106
107    fn subgroup_generator(&self) -> Self::Element {
108        self.g.clone()
109    }
110
111    fn identity(&self) -> Self::Element {
112        BigInt::one()
113    }
114
115    fn exp(
116        &self,
117        base: &Self::Element,
118        scalar: &Self::Scalar,
119    ) -> Self::Element {
120        base.modpow(scalar, &self.q)
121    }
122
123    fn mul(&self, a: &Self::Element, b: &Self::Element) -> Self::Element {
124        (a * b) % &self.q
125    }
126
127    fn scalar_inverse(&self, x: &Self::Scalar) -> Option<Self::Scalar> {
128        crate::util::Util::mod_inverse(x, &self.q_minus_1)
129    }
130
131    fn element_inverse(&self, x: &Self::Element) -> Option<Self::Element> {
132        crate::util::Util::mod_inverse(x, &self.q)
133    }
134
135    fn hash_to_scalar(&self, data: &[u8]) -> Self::Scalar {
136        let hash = Sha256::digest(data);
137        BigUint::from_bytes_be(&hash[..])
138            .mod_floor(&self.g.to_biguint().unwrap())
139            .to_bigint()
140            .unwrap()
141    }
142
143    fn element_to_bytes(&self, elem: &Self::Element) -> Vec<u8> {
144        elem.to_biguint().unwrap().to_bytes_be()
145    }
146
147    fn bytes_to_element(&self, bytes: &[u8]) -> Option<Self::Element> {
148        Some(BigUint::from_bytes_be(bytes).to_bigint().unwrap())
149    }
150
151    fn scalar_to_bytes(&self, scalar: &Self::Scalar) -> Vec<u8> {
152        scalar.to_biguint().unwrap().to_bytes_be()
153    }
154
155    fn generate_private_key(&self) -> Self::Scalar {
156        let mut rng = rand::thread_rng();
157        loop {
158            let privkey: BigInt = rng
159                .gen_biguint_below(&self.q.to_biguint().unwrap())
160                .to_bigint()
161                .unwrap();
162            // Private key must be coprime to (q-1) for modular inverse during reconstruction
163            if privkey.gcd(&self.q_minus_1) == BigInt::one() {
164                return privkey;
165            }
166        }
167    }
168
169    fn generate_public_key(&self, private_key: &Self::Scalar) -> Self::Element {
170        self.exp(&self.G, private_key)
171    }
172
173    fn scalar_mul(&self, a: &Self::Scalar, b: &Self::Scalar) -> Self::Scalar {
174        (a * b) % self.order()
175    }
176
177    fn scalar_sub(&self, a: &Self::Scalar, b: &Self::Scalar) -> Self::Scalar {
178        let order = self.order();
179        let diff = a - b;
180        if diff < BigInt::zero() {
181            diff + order
182        } else {
183            diff % order
184        }
185    }
186
187    fn modulus(&self) -> Option<&BigInt> {
188        Some(&self.q)
189    }
190}
191
192#[cfg(test)]
193mod tests {
194    use super::*;
195    use num_primes::Verification;
196
197    #[test]
198    fn test_modp_group_new() {
199        let group = ModpGroup::new();
200        assert!(Verification::is_safe_prime(&group.q.to_biguint().unwrap()));
201        assert!(Verification::is_prime(&group.g.to_biguint().unwrap()));
202        assert!(!Verification::is_safe_prime(&group.g.to_biguint().unwrap()));
203    }
204
205    #[test]
206    fn test_modp_group_init() {
207        let group = ModpGroup::init(64);
208        assert!(Verification::is_prime(&group.q.to_biguint().unwrap()));
209        assert!(Verification::is_prime(&group.g.to_biguint().unwrap()));
210        assert_eq!(
211            group.g,
212            ((group.q.clone() - BigInt::one()).to_biguint().unwrap()
213                / BigUint::from(2_u32))
214            .to_bigint()
215            .unwrap()
216        );
217    }
218
219    #[test]
220    fn test_generate_private_key() {
221        let group = ModpGroup::init(64);
222        let privkey = group.generate_private_key();
223        assert_eq!(privkey.gcd(&group.q_minus_1), BigInt::one());
224    }
225
226    #[test]
227    fn test_generate_public_key() {
228        let group = ModpGroup::new();
229        let privkey = group.generate_private_key();
230        let pubkey = group.generate_public_key(&privkey);
231        // Public key should be G^privkey mod q
232        assert_eq!(pubkey, group.G.modpow(&privkey, &group.q));
233    }
234
235    #[test]
236    fn test_exp() {
237        let group = ModpGroup::new();
238        let g = group.generator();
239        // G^1 = G
240        assert_eq!(group.exp(&g, &BigInt::one()), g);
241        // G^0 = 1
242        assert_eq!(group.exp(&g, &BigInt::zero()), group.identity());
243    }
244
245    #[test]
246    fn test_mul() {
247        let group = ModpGroup::new();
248        let a = BigInt::from(5);
249        let b = BigInt::from(3);
250        let result = group.mul(&a, &b);
251        assert_eq!(result, (a * b) % &group.q);
252    }
253
254    #[test]
255    fn test_hash_to_scalar() {
256        let group = ModpGroup::new();
257        let data = b"test data";
258        let scalar = group.hash_to_scalar(data);
259        // Scalar should be less than subgroup order
260        assert!(scalar < group.g);
261    }
262}
mpvss_rs/groups/modp.rs

mpvss_rs/groups/
modp.rs
