tecdsa_core/zk/
modulus.rs

1//! Π_mod (paper Protocol 5): `N` is a product of two primes `p1 ≡ 3`, `p2 ≡ 7 (mod 8)` with
2//! `gcd(N, φ(N)) = 1`.
3//!
4//! The challenges `y_i ∈ Z*_N` are derived from the transcript (the only input is `N`), so the
5//! proof is just `r_mod` tuples `(a, b, x, z)`:
6//! `x⁴ = (−1)^a · w^b · y (mod N)` with `w = 2^N mod N`, and `z^N = y (mod N)`.
7use alloc::vec::Vec;
8use crypto_bigint::{BoxedUint, ConcatenatingMul, Gcd, NonZero, ctutils::CtSelect};
9use crypto_primes::{Flavor, is_prime};
10use rand_core::CryptoRng;
11
12use crate::{
13    arith::{
14        monty::{Modulus, Residue},
15        sbig::{SBig, resized},
16    },
17    error::{Error, Result},
18    params::Params,
19    transcript::{Transcript, uint_from_be, uint_to_be},
20};
21
22/// Secret input: the two primes (`p1 ≡ 3`, `p2 ≡ 7 mod 8`).
23pub struct ModWitness<'a> {
24    pub p1: &'a BoxedUint,
25    pub p2: &'a BoxedUint,
26}
27
28/// One repetition `(a, b, x, z)`.
29#[derive(Clone, Debug, PartialEq, Eq)]
30pub struct ModRep {
31    pub a: bool,
32    pub b: bool,
33    pub x: BoxedUint,
34    pub z: BoxedUint,
35}
36
37/// Proof: `r_mod` repetitions.
38#[derive(Clone, Debug, PartialEq, Eq)]
39pub struct ModProof {
40    pub reps: Vec<ModRep>,
41}
42
43fn n_bytes(n_bits: u32) -> usize {
44    (n_bits as usize).div_ceil(8)
45}
46
47/// Challenges `y_1..y_r` and `w = 2^N mod N` are public functions of `N`.
48fn challenges(
49    tx: &Transcript,
50    params: &Params,
51    mn: &Modulus,
52    n: &BoxedUint,
53) -> Result<Vec<Residue>> {
54    let mut t = tx.clone();
55    t.append("zk", b"mod");
56    t.append_uint("N", n, n_bytes(n.bits()))?;
57    let mut ch = t.challenge("y");
58    let mut ys = Vec::with_capacity(params.r_mod as usize);
59    for _ in 0..params.r_mod {
60        ys.push(ch.unit_mod(mn)?);
61    }
62    Ok(ys)
63}
64
65fn small_w(mn: &Modulus, n: &BoxedUint) -> Result<Residue> {
66    let two = mn.residue(&BoxedUint::from(2u64));
67    mn.pow_vartime(&two, &SBig::from_uint(n.clone()))
68}
69
70/// `(−1)^a · w^b · y`.
71fn target(y: &Residue, w: &Residue, a: bool, b: bool) -> Residue {
72    let mut v = y.clone();
73    if a {
74        v = v.neg();
75    }
76    if b {
77        v = v.mul(w);
78    }
79    v
80}
81
82/// Per-prime secret data for the prover.
83struct PrimeCtx {
84    ring: Modulus,
85    bits: u32,
86    /// `(p−1)/2`.
87    half: SBig,
88    /// `((p+1)/4)² mod (p−1)/2`: maps a QR to its QR fourth root.
89    root_exp: SBig,
90    /// `N^{-1} mod (p−1)`.
91    n_inv: SBig,
92}
93
94fn rem(x: &BoxedUint, m: &BoxedUint) -> Result<BoxedUint> {
95    let nz = Option::<NonZero<BoxedUint>>::from(m.to_nz()).ok_or(Error::InvalidModulus)?;
96    Ok(SBig::from_uint(x.clone()).rem_euclid(&nz))
97}
98
99impl PrimeCtx {
100    fn new(p: &BoxedUint, n: &BoxedUint) -> Result<Self> {
101        let prec = p.bits_precision();
102        let one = BoxedUint::one_with_precision(prec);
103        let pm1 = p.wrapping_sub(&one);
104        let half = pm1.shr_vartime(1).ok_or(Error::InvalidModulus)?;
105        let wide = resized(p, prec + 64);
106        let t = wide
107            .wrapping_add(BoxedUint::one_with_precision(prec + 64))
108            .shr_vartime(2)
109            .ok_or(Error::InvalidModulus)?;
110        let t2 = t.concatenating_mul(&t);
111        let root_exp = rem(&t2, &half)?;
112        // N^{-1} mod (p−1) (even modulus; fails iff gcd(N, p−1) ≠ 1)
113        let pm1_nz =
114            Option::<NonZero<BoxedUint>>::from(pm1.to_nz()).ok_or(Error::InvalidModulus)?;
115        let n_red = rem(n, &pm1)?;
116        let n_inv =
117            Option::<BoxedUint>::from(n_red.invert_mod(&pm1_nz)).ok_or(Error::NotInvertible)?;
118        Ok(Self {
119            ring: Modulus::new(p.clone())?,
120            bits: p.bits(),
121            half: SBig::from_uint(half),
122            root_exp: SBig::from_uint(root_exp),
123            n_inv: SBig::from_uint(n_inv),
124        })
125    }
126
127    fn residue(&self, y: &Residue) -> Residue {
128        self.ring.residue(&y.retrieve())
129    }
130}
131
132/// CRT combination of `r1 mod p1`, `r2 mod p2` into `Z_N`.
133fn crt(c1: &PrimeCtx, r1: &Residue, p2: &BoxedUint, r2: &Residue, mn: &Modulus) -> Result<Residue> {
134    let x2 = r2.retrieve();
135    let x2_in_1 = c1.ring.residue(&x2);
136    let inv = c1.ring.invert(&c1.ring.residue(p2))?;
137    let t = r1.sub(&x2_in_1).mul(&inv).retrieve();
138    let x = p2
139        .concatenating_mul(&t)
140        .wrapping_add(resized(&x2, p2.bits_precision() + t.bits_precision()));
141    Ok(mn.residue(&x))
142}
143
144fn random_neg<R: CryptoRng + ?Sized>(rng: &mut R, r: &Residue) -> Residue {
145    let n = r.neg();
146    let flip = crypto_bigint::Choice::from_u8_lsb((rng.next_u32() & 1) as u8);
147    Residue::from_montgomery(
148        r.as_montgomery().ct_select(n.as_montgomery(), flip),
149        r.params(),
150    )
151}
152
153impl ModProof {
154    /// Proves that `N = p1·p2` is well formed.
155    pub fn prove<R: CryptoRng + ?Sized>(
156        rng: &mut R,
157        tx: &Transcript,
158        params: &Params,
159        n: &BoxedUint,
160        w: &ModWitness<'_>,
161    ) -> Result<Self> {
162        Self::prove_inner(rng, tx, params, n, w, true)
163    }
164
165    fn prove_inner<R: CryptoRng + ?Sized>(
166        rng: &mut R,
167        tx: &Transcript,
168        params: &Params,
169        n: &BoxedUint,
170        wit: &ModWitness<'_>,
171        check: bool,
172    ) -> Result<Self> {
173        if check {
174            let prod = wit.p1.concatenating_mul(wit.p2);
175            if resized(&prod, n.bits_precision()) != resized(n, prod.bits_precision()) {
176                return Err(Error::InvalidModulus);
177            }
178            if wit.p1.as_words()[0] & 7 != 3 || wit.p2.as_words()[0] & 7 != 7 {
179                return Err(Error::InvalidModulus);
180            }
181        }
182        let mn = Modulus::new(n.clone())?;
183        let c1 = PrimeCtx::new(wit.p1, n)?;
184        let c2 = PrimeCtx::new(wit.p2, n)?;
185        let ys = challenges(tx, params, &mn, n)?;
186        let w = small_w(&mn, n)?;
187        let one = BoxedUint::one_with_precision(64);
188        let is_plus = |r: &Residue| resized(&r.retrieve(), 64) == one;
189
190        let mut reps = Vec::with_capacity(ys.len());
191        for y in &ys {
192            let y1 = c1.residue(y);
193            let y2 = c2.residue(y);
194            // Legendre symbols of y: a, b are public so the branch is harmless.
195            let l1 = c1.ring.pow_ct(&y1, &c1.half, c1.bits)?;
196            let l2 = c2.ring.pow_ct(&y2, &c2.half, c2.bits)?;
197            // −1 has symbols (−1,−1), w = 2^N has symbols (−1,+1) for (p1,p2) ≡ (3,7) mod 8.
198            let a = !is_plus(&l2);
199            let b = !is_plus(&l1) ^ a;
200            let y0 = target(y, &w, a, b);
201            let y01 = c1.residue(&y0);
202            let y02 = c2.residue(&y0);
203            let r1 = random_neg(rng, &c1.ring.pow_ct(&y01, &c1.root_exp, c1.bits)?);
204            let r2 = random_neg(rng, &c2.ring.pow_ct(&y02, &c2.root_exp, c2.bits)?);
205            let x = crt(&c1, &r1, wit.p2, &r2, &mn)?;
206            let z1 = c1.ring.pow_ct(&y1, &c1.n_inv, c1.bits)?;
207            let z2 = c2.ring.pow_ct(&y2, &c2.n_inv, c2.bits)?;
208            let z = crt(&c1, &z1, wit.p2, &z2, &mn)?;
209            reps.push(ModRep {
210                a,
211                b,
212                x: x.retrieve(),
213                z: z.retrieve(),
214            });
215        }
216        Ok(Self { reps })
217    }
218
219    /// Verifies the proof for `N`; `min_bits` is the required bit length of `N`.
220    pub fn verify(
221        &self,
222        tx: &Transcript,
223        params: &Params,
224        n: &BoxedUint,
225        min_bits: u32,
226    ) -> Result<()> {
227        let fail = Error::VerificationFailed;
228        if n.bits() < min_bits || self.reps.len() != params.r_mod as usize {
229            return Err(fail);
230        }
231        if n.as_words()[0] & 3 != 1 {
232            return Err(fail);
233        }
234        let mn = Modulus::new(n.clone()).map_err(|_| fail)?;
235        if mn.jacobi_vartime(&BoxedUint::from(2u64)) != -1 {
236            return Err(fail);
237        }
238        // Cheap per-repetition range checks before any exponentiation.
239        for rep in &self.reps {
240            for v in [&rep.x, &rep.z] {
241                let v = resized(v, n.bits_precision());
242                let nn = resized(n, v.bits_precision());
243                if v.cmp_vartime(&nn) != core::cmp::Ordering::Less {
244                    return Err(fail);
245                }
246                if !bool::from(v.gcd(&nn).is_one()) {
247                    return Err(fail);
248                }
249            }
250        }
251        if is_prime(Flavor::Any, n) {
252            return Err(fail);
253        }
254        let ys = challenges(tx, params, &mn, n)?;
255        let w = small_w(&mn, n)?;
256        for (rep, y) in self.reps.iter().zip(&ys) {
257            let x = mn.residue(&rep.x);
258            let x4 = x.square().square();
259            if x4 != target(y, &w, rep.a, rep.b) {
260                return Err(fail);
261            }
262        }
263        let n_exp = SBig::from_uint(n.clone());
264        for (rep, y) in self.reps.iter().zip(&ys) {
265            let z = mn.residue(&rep.z);
266            if mn.pow_vartime(&z, &n_exp)? != *y {
267                return Err(fail);
268            }
269        }
270        Ok(())
271    }
272
273    /// Encoded length: `r_mod · (1 + 2·⌈bits(N)/8⌉)`.
274    pub fn encoded_len(params: &Params, n_bits: u32) -> usize {
275        params.r_mod as usize * (1 + 2 * n_bytes(n_bits))
276    }
277
278    /// Per repetition: byte `a | b << 1`, then `x` and `z` as fixed-width big-endian.
279    pub fn encode(&self, n_bits: u32) -> Result<Vec<u8>> {
280        let len = n_bytes(n_bits);
281        let mut out = Vec::with_capacity(self.reps.len() * (1 + 2 * len));
282        for r in &self.reps {
283            out.push(u8::from(r.a) | (u8::from(r.b) << 1));
284            out.extend_from_slice(&uint_to_be(&r.x, len)?);
285            out.extend_from_slice(&uint_to_be(&r.z, len)?);
286        }
287        Ok(out)
288    }
289
290    pub fn decode(bytes: &[u8], params: &Params, n_bits: u32) -> Result<Self> {
291        if bytes.len() != Self::encoded_len(params, n_bits) {
292            return Err(Error::InvalidEncoding);
293        }
294        let len = n_bytes(n_bits);
295        let mut reps = Vec::with_capacity(params.r_mod as usize);
296        for chunk in bytes.chunks_exact(1 + 2 * len) {
297            if chunk[0] > 3 {
298                return Err(Error::InvalidEncoding);
299            }
300            reps.push(ModRep {
301                a: chunk[0] & 1 == 1,
302                b: chunk[0] & 2 == 2,
303                x: uint_from_be(&chunk[1..1 + len], n_bits)?,
304                z: uint_from_be(&chunk[1 + len..], n_bits)?,
305            });
306        }
307        Ok(Self { reps })
308    }
309}
310
311#[cfg(test)]
312mod tests {
313    extern crate std;
314    use super::*;
315    use crate::{
316        params::PARAMS_128,
317        rsa::tough::{ToughSpec, sample_rsa_with, sample_tough_prime},
318    };
319    use rand_chacha::ChaCha8Rng;
320    use rand_core::SeedableRng;
321    use std::{sync::OnceLock, time::Instant};
322
323    const SPEC: ToughSpec = ToughSpec { count: 4, bits: 64 };
324
325    fn params() -> Params {
326        Params {
327            r_mod: 8,
328            ..PARAMS_128
329        }
330    }
331
332    struct Fx {
333        n: BoxedUint,
334        p1: BoxedUint,
335        p2: BoxedUint,
336    }
337
338    fn fx() -> &'static Fx {
339        static F: OnceLock<Fx> = OnceLock::new();
340        F.get_or_init(|| {
341            let mut rng = ChaCha8Rng::seed_from_u64(11);
342            let m = sample_rsa_with(&mut rng, 512, SPEC).unwrap();
343            Fx {
344                n: m.n.clone(),
345                p1: m.secret.p1.p().clone(),
346                p2: m.secret.p2.p().clone(),
347            }
348        })
349    }
350
351    fn tx() -> Transcript {
352        Transcript::new("test/mod")
353    }
354
355    fn honest() -> ModProof {
356        let f = fx();
357        let mut rng = ChaCha8Rng::seed_from_u64(5);
358        ModProof::prove(
359            &mut rng,
360            &tx(),
361            &params(),
362            &f.n,
363            &ModWitness {
364                p1: &f.p1,
365                p2: &f.p2,
366            },
367        )
368        .unwrap()
369    }
370
371    #[test]
372    fn honest_passes() {
373        let f = fx();
374        honest().verify(&tx(), &params(), &f.n, 512).unwrap();
375        // a,b take all four values over enough repetitions
376        let p = Params {
377            r_mod: 64,
378            ..PARAMS_128
379        };
380        let mut rng = ChaCha8Rng::seed_from_u64(6);
381        let pr = ModProof::prove(
382            &mut rng,
383            &tx(),
384            &p,
385            &f.n,
386            &ModWitness {
387                p1: &f.p1,
388                p2: &f.p2,
389            },
390        )
391        .unwrap();
392        pr.verify(&tx(), &p, &f.n, 512).unwrap();
393        for ab in 0..4u8 {
394            assert!(
395                pr.reps
396                    .iter()
397                    .any(|r| u8::from(r.a) | (u8::from(r.b) << 1) == ab)
398            );
399        }
400    }
401
402    #[test]
403    fn wrong_transcript_or_min_bits() {
404        let f = fx();
405        let pr = honest();
406        assert!(
407            pr.verify(&Transcript::new("other"), &params(), &f.n, 512)
408                .is_err()
409        );
410        assert!(pr.verify(&tx(), &params(), &f.n, 513).is_err());
411    }
412
413    #[test]
414    fn modified_fields_fail() {
415        let f = fx();
416        let one = BoxedUint::one_with_precision(64);
417        for i in [0usize, 3, 7] {
418            let mut p = honest();
419            p.reps[i].a = !p.reps[i].a;
420            assert!(p.verify(&tx(), &params(), &f.n, 512).is_err());
421            let mut p = honest();
422            p.reps[i].b = !p.reps[i].b;
423            assert!(p.verify(&tx(), &params(), &f.n, 512).is_err());
424            let mut p = honest();
425            p.reps[i].x = resized(&p.reps[i].x, 576).wrapping_add(resized(&one, 576));
426            assert!(p.verify(&tx(), &params(), &f.n, 512).is_err());
427            let mut p = honest();
428            p.reps[i].z = resized(&p.reps[i].z, 576).wrapping_add(resized(&one, 576));
429            assert!(p.verify(&tx(), &params(), &f.n, 512).is_err());
430            // −x is another valid 4th root
431            let mut p = honest();
432            p.reps[i].x = resized(&f.n, 576).wrapping_sub(resized(&p.reps[i].x, 576));
433            p.verify(&tx(), &params(), &f.n, 512).unwrap();
434            // x = N (out of range)
435            let mut p = honest();
436            p.reps[i].x = f.n.clone();
437            assert!(p.verify(&tx(), &params(), &f.n, 512).is_err());
438            let mut p = honest();
439            p.reps[i].z = BoxedUint::zero_with_precision(64);
440            assert!(p.verify(&tx(), &params(), &f.n, 512).is_err());
441        }
442        let mut p = honest();
443        p.reps.pop();
444        assert!(p.verify(&tx(), &params(), &f.n, 512).is_err());
445    }
446
447    #[test]
448    fn bad_moduli_fail() {
449        let f = fx();
450        let pr = honest();
451        let mut rng = ChaCha8Rng::seed_from_u64(9);
452        // N + 2 ≡ 3 mod 4
453        let n3 = f.n.wrapping_add(BoxedUint::from(2u64));
454        assert!(pr.verify(&tx(), &params(), &n3, 512).is_err());
455        // prime N
456        let pm = sample_tough_prime(&mut rng, 512, 3, ToughSpec::SAFE).unwrap();
457        let pn = pm.p().clone();
458        assert!(pr.verify(&tx(), &params(), &pn, 512).is_err());
459        // even N
460        let ne = f.n.wrapping_sub(BoxedUint::one());
461        assert!(pr.verify(&tx(), &params(), &ne, 512).is_err());
462        // prime N ≡ 5 mod 8 passes every check except compositeness
463        let p5 = loop {
464            let c = crypto_primes::random_prime::<BoxedUint, _>(&mut rng, Flavor::Any, 256);
465            if c.as_words()[0] & 7 == 5 {
466                break c;
467            }
468        };
469        assert!(pr.verify(&tx(), &params(), &p5, 256).is_err());
470        // N = p·q with both ≡ 3 mod 8: prover refuses; forged (unchecked) proof fails
471        let a = sample_tough_prime(&mut rng, 256, 3, ToughSpec::SAFE).unwrap();
472        let b = sample_tough_prime(&mut rng, 256, 3, ToughSpec::SAFE).unwrap();
473        let n33 = a.p().concatenating_mul(b.p());
474        let w = ModWitness {
475            p1: a.p(),
476            p2: b.p(),
477        };
478        assert!(ModProof::prove(&mut rng, &tx(), &params(), &n33, &w).is_err());
479        let forged = ModProof::prove_inner(&mut rng, &tx(), &params(), &n33, &w, false).unwrap();
480        assert!(forged.verify(&tx(), &params(), &n33, 512).is_err());
481        // wrong order (7, 3)
482        let w2 = ModWitness {
483            p1: &f.p2,
484            p2: &f.p1,
485        };
486        assert!(ModProof::prove(&mut rng, &tx(), &params(), &f.n, &w2).is_err());
487        // wrong witness product
488        let w3 = ModWitness {
489            p1: &f.p1,
490            p2: a.p(),
491        };
492        assert!(ModProof::prove(&mut rng, &tx(), &params(), &f.n, &w3).is_err());
493    }
494
495    #[test]
496    fn three_factor_modulus_fails() {
497        let mut rng = ChaCha8Rng::seed_from_u64(10);
498        let p1 = sample_tough_prime(&mut rng, 200, 3, ToughSpec::SAFE).unwrap();
499        let p2 = sample_tough_prime(&mut rng, 200, 7, ToughSpec::SAFE).unwrap();
500        // r ≡ 1 mod 8, so N ≡ 1 mod 4 and Jacobi(2/N) = −1 hold
501        let r = loop {
502            let c = crypto_primes::random_prime::<BoxedUint, _>(&mut rng, Flavor::Any, 112);
503            if c.as_words()[0] & 7 == 1 {
504                break c;
505            }
506        };
507        let n = p1.p().concatenating_mul(p2.p()).concatenating_mul(&r);
508        let w = ModWitness {
509            p1: p1.p(),
510            p2: &p2.p().concatenating_mul(&r),
511        };
512        let forged = ModProof::prove_inner(&mut rng, &tx(), &params(), &n, &w, false);
513        if let Ok(f) = forged {
514            assert!(f.verify(&tx(), &params(), &n, 400).is_err());
515        }
516        // random junk proof
517        let junk = ModProof {
518            reps: (0..8)
519                .map(|i| ModRep {
520                    a: false,
521                    b: false,
522                    x: BoxedUint::from(5u64 + i),
523                    z: BoxedUint::from(7u64 + i),
524                })
525                .collect(),
526        };
527        assert!(junk.verify(&tx(), &params(), &n, 400).is_err());
528    }
529
530    #[test]
531    fn encode_decode() {
532        let f = fx();
533        let pr = honest();
534        let bytes = pr.encode(f.n.bits()).unwrap();
535        assert_eq!(bytes.len(), ModProof::encoded_len(&params(), 512));
536        let back = ModProof::decode(&bytes, &params(), 512).unwrap();
537        back.verify(&tx(), &params(), &f.n, 512).unwrap();
538        assert!(ModProof::decode(&bytes[1..], &params(), 512).is_err());
539        let mut long = bytes.clone();
540        long.push(0);
541        assert!(ModProof::decode(&long, &params(), 512).is_err());
542        let mut bad = bytes.clone();
543        bad[0] = 4;
544        assert!(ModProof::decode(&bad, &params(), 512).is_err());
545    }
546
547    #[test]
548    #[ignore]
549    fn full_size_timings() {
550        let mut rng = ChaCha8Rng::seed_from_u64(77);
551        let spec = ToughSpec::from_params(&PARAMS_128);
552        let t0 = Instant::now();
553        let m = sample_rsa_with(&mut rng, PARAMS_128.n_rsa, spec).unwrap();
554        std::println!("sample_rsa: {:?}", t0.elapsed());
555        let (p1, p2) = (m.secret.p1.p().clone(), m.secret.p2.p().clone());
556        let t0 = Instant::now();
557        let pr = ModProof::prove(
558            &mut rng,
559            &tx(),
560            &PARAMS_128,
561            &m.n,
562            &ModWitness { p1: &p1, p2: &p2 },
563        )
564        .unwrap();
565        std::println!("mod prove: {:?}", t0.elapsed());
566        let t0 = Instant::now();
567        pr.verify(&tx(), &PARAMS_128, &m.n, PARAMS_128.n_rsa)
568            .unwrap();
569        std::println!("mod verify: {:?}", t0.elapsed());
570        let bytes = pr.encode(PARAMS_128.n_rsa).unwrap();
571        std::println!("mod proof size: {} bytes", bytes.len());
572        let mut bad = pr.clone();
573        bad.reps[63].a = !bad.reps[63].a;
574        assert!(
575            bad.verify(&tx(), &PARAMS_128, &m.n, PARAMS_128.n_rsa)
576                .is_err()
577        );
578    }
579}
tecdsa_core/zk/modulus.rs

tecdsa_core/zk/
modulus.rs
