tecdsa_core/zk/
dlog.rs

1//! Π_dlog (paper Protocol 5.13): proof of knowledge of `x` with `X = g^x` on secp256k1.
2//!
3//! Compact Fiat–Shamir form `(e, z)`; the verifier reconstructs `A = g^z · X^{-e}`.
4use alloc::vec::Vec;
5use k256::{ProjectivePoint, Scalar};
6use rand_core::CryptoRng;
7
8use crate::{
9    arith::sbig::{SBig, SRange},
10    curve::{decode_scalar, encode_point, encode_scalar, is_identity, random_nonzero_scalar},
11    error::{Error, Result},
12    params::Params,
13    transcript::{Challenge, Transcript, uint_to_be},
14};
15
16/// Compact proof `(e, z)`.
17#[derive(Clone, Debug, PartialEq, Eq)]
18pub struct DlogProof {
19    pub e: SBig,
20    pub z: Scalar,
21}
22
23/// Signed challenge as a scalar mod q (`|e| ≤ 2^{ℓ−1} < q` is required).
24fn sbig_to_scalar(e: &SBig) -> Result<Scalar> {
25    let bytes = uint_to_be(e.mag(), 32)?;
26    let s = decode_scalar(&bytes)?;
27    Ok(if bool::from(e.is_neg()) { -s } else { s })
28}
29
30fn base(tx: &Transcript, x_pub: &ProjectivePoint) -> Transcript {
31    let mut t = tx.clone();
32    t.append("zk", b"dlog");
33    t.append("X", &encode_point(x_pub));
34    t
35}
36
37fn derive_e(t: &Transcript, a: &ProjectivePoint, params: &Params) -> SBig {
38    let mut t = t.clone();
39    t.append("A", &encode_point(a));
40    let mut ch: Challenge = t.challenge("e");
41    ch.pm_pow2(params.ell)
42}
43
44fn e_range(params: &Params) -> SRange {
45    SRange::pm_pow2(params.ell)
46}
47
48impl DlogProof {
49    /// Proves knowledge of `x` with `X = g^x`.
50    pub fn prove<R: CryptoRng + ?Sized>(
51        rng: &mut R,
52        tx: &Transcript,
53        params: &Params,
54        x_pub: &ProjectivePoint,
55        x: &Scalar,
56    ) -> Result<Self> {
57        if params.ell == 0 || params.ell > 255 || is_identity(x_pub) {
58            return Err(Error::OutOfRange);
59        }
60        let t = base(tx, x_pub);
61        let alpha = random_nonzero_scalar(rng);
62        let a = ProjectivePoint::GENERATOR * alpha;
63        let e = derive_e(&t, &a, params);
64        let z = alpha + sbig_to_scalar(&e)? * x;
65        Ok(Self { e, z })
66    }
67
68    /// Verifies the proof for `X`.
69    pub fn verify(&self, tx: &Transcript, params: &Params, x_pub: &ProjectivePoint) -> Result<()> {
70        if params.ell == 0 || params.ell > 255 || is_identity(x_pub) {
71            return Err(Error::VerificationFailed);
72        }
73        if !self.e.in_range(e_range(params)) {
74            return Err(Error::OutOfRange);
75        }
76        let es = sbig_to_scalar(&self.e)?;
77        // A = g^z · X^{-e}
78        let a = ProjectivePoint::GENERATOR * self.z - *x_pub * es;
79        if is_identity(&a) {
80            return Err(Error::VerificationFailed);
81        }
82        let t = base(tx, x_pub);
83        if derive_e(&t, &a, params) == self.e {
84            Ok(())
85        } else {
86            Err(Error::VerificationFailed)
87        }
88    }
89
90    /// `e` (sign byte + ⌈(ℓ−1)/8⌉ bytes) ‖ `z` (32 bytes).
91    pub fn encode(&self, params: &Params) -> Result<Vec<u8>> {
92        let mut out = self.e.to_bytes(e_range(params))?;
93        out.extend_from_slice(&encode_scalar(&self.z));
94        Ok(out)
95    }
96
97    pub fn encoded_len(params: &Params) -> usize {
98        1 + (params.ell.saturating_sub(1) as usize).div_ceil(8).max(1) + 32
99    }
100
101    pub fn decode(bytes: &[u8], params: &Params) -> Result<Self> {
102        if bytes.len() != Self::encoded_len(params) {
103            return Err(Error::InvalidEncoding);
104        }
105        let (eb, zb) = bytes.split_at(bytes.len() - 32);
106        let e = SBig::from_bytes(eb, e_range(params))?;
107        let z = decode_scalar(zb)?;
108        Ok(Self { e, z })
109    }
110}
111
112#[cfg(test)]
113mod tests {
114    use super::*;
115    use crate::params::PARAMS_128;
116    use rand_chacha::ChaCha8Rng;
117    use rand_core::SeedableRng;
118
119    fn setup() -> (ChaCha8Rng, Transcript, ProjectivePoint, Scalar) {
120        let mut rng = ChaCha8Rng::seed_from_u64(1);
121        let x = random_nonzero_scalar(&mut rng);
122        (
123            rng,
124            Transcript::new("test"),
125            ProjectivePoint::GENERATOR * x,
126            x,
127        )
128    }
129
130    #[test]
131    fn honest_and_roundtrip() {
132        let (mut rng, tx, xp, x) = setup();
133        let p = DlogProof::prove(&mut rng, &tx, &PARAMS_128, &xp, &x).unwrap();
134        p.verify(&tx, &PARAMS_128, &xp).unwrap();
135        let enc = p.encode(&PARAMS_128).unwrap();
136        assert_eq!(enc.len(), 17 + 32);
137        let q = DlogProof::decode(&enc, &PARAMS_128).unwrap();
138        assert_eq!(p, q);
139        q.verify(&tx, &PARAMS_128, &xp).unwrap();
140        assert!(DlogProof::decode(&enc[1..], &PARAMS_128).is_err());
141        let mut longer = enc.clone();
142        longer.push(0);
143        assert!(DlogProof::decode(&longer, &PARAMS_128).is_err());
144    }
145
146    #[test]
147    fn many_seeds() {
148        let (mut rng, tx, xp, x) = setup();
149        for _ in 0..50 {
150            let p = DlogProof::prove(&mut rng, &tx, &PARAMS_128, &xp, &x).unwrap();
151            p.verify(&tx, &PARAMS_128, &xp).unwrap();
152        }
153    }
154
155    #[test]
156    fn tampering_fails() {
157        let (mut rng, tx, xp, x) = setup();
158        let p = DlogProof::prove(&mut rng, &tx, &PARAMS_128, &xp, &x).unwrap();
159        // z
160        let mut b = p.clone();
161        b.z += Scalar::ONE;
162        assert!(b.verify(&tx, &PARAMS_128, &xp).is_err());
163        // e ± 1
164        for d in [1i64, -1] {
165            let mut b = p.clone();
166            b.e = b.e.add(&SBig::from_i64(d));
167            assert!(b.verify(&tx, &PARAMS_128, &xp).is_err());
168        }
169        // e out of range
170        let mut b = p.clone();
171        b.e = SBig::from_i64(1).add(&SBig::from_uint(
172            crypto_bigint::BoxedUint::one_with_precision(192).shl(127),
173        ));
174        assert_eq!(b.verify(&tx, &PARAMS_128, &xp), Err(Error::OutOfRange));
175        // statement
176        let other = xp + ProjectivePoint::GENERATOR;
177        assert!(p.verify(&tx, &PARAMS_128, &other).is_err());
178        assert!(
179            p.verify(&tx, &PARAMS_128, &ProjectivePoint::IDENTITY)
180                .is_err()
181        );
182        // transcript
183        let mut tx2 = Transcript::new("test");
184        tx2.append("x", b"y");
185        assert!(p.verify(&tx2, &PARAMS_128, &xp).is_err());
186    }
187
188    #[test]
189    fn wrong_witness_fails() {
190        let (mut rng, tx, xp, x) = setup();
191        let p = DlogProof::prove(&mut rng, &tx, &PARAMS_128, &xp, &(x + Scalar::ONE)).unwrap();
192        assert!(p.verify(&tx, &PARAMS_128, &xp).is_err());
193    }
194
195    #[test]
196    fn decode_rejects_noncanonical() {
197        let (mut rng, tx, xp, x) = setup();
198        let p = DlogProof::prove(&mut rng, &tx, &PARAMS_128, &xp, &x).unwrap();
199        let enc = p.encode(&PARAMS_128).unwrap();
200        // z ≥ q
201        let mut b = enc.clone();
202        for v in b[17..].iter_mut() {
203            *v = 0xff;
204        }
205        assert!(DlogProof::decode(&b, &PARAMS_128).is_err());
206        // bad sign byte
207        let mut b = enc.clone();
208        b[0] = 2;
209        assert!(DlogProof::decode(&b, &PARAMS_128).is_err());
210        // negative zero
211        let mut b = enc.clone();
212        b[0] = 1;
213        for v in b[1..17].iter_mut() {
214            *v = 0;
215        }
216        assert!(DlogProof::decode(&b, &PARAMS_128).is_err());
217        // e magnitude above 2^{ℓ−1}
218        let mut b = enc.clone();
219        b[0] = 0;
220        b[1] = 0xff;
221        assert!(DlogProof::decode(&b, &PARAMS_128).is_err());
222    }
223}
tecdsa_core/zk/dlog.rs

tecdsa_core/zk/
dlog.rs
