tecdsa_core/
transcript.rs

1//! Fiat–Shamir transcript with domain separation (spec §10.1) and challenge derivation (§10.3).
2use alloc::{string::String, vec::Vec};
3use crypto_bigint::{BoxedUint, Gcd, NonZero};
4use k256::{
5    Scalar,
6    elliptic_curve::{bigint::U512, ops::Reduce},
7};
8use sha2::{Digest, Sha256};
9
10use crate::{
11    arith::{
12        monty::{Modulus, Residue},
13        sbig::{SBig, SRange, resized},
14    },
15    error::{Error, Result},
16};
17
18const PREFIX: &str = "tecdsa-1ole/v1/";
19
20/// Incremental transcript. `Clone` yields an independent fork, so a caller can seed a base
21/// transcript with the ssid and public parameters and fork it for every proof.
22#[derive(Clone)]
23pub struct Transcript {
24    hasher: Sha256,
25}
26
27impl Transcript {
28    /// Starts a transcript for `domain`, e.g. `zk/sig` (the version prefix is added here).
29    pub fn new(domain: &str) -> Self {
30        let mut t = Self {
31            hasher: Sha256::new(),
32        };
33        let full: String = [PREFIX, domain].concat();
34        t.hasher.update([0x00]);
35        t.hasher.update((full.len() as u32).to_be_bytes());
36        t.hasher.update(full.as_bytes());
37        t
38    }
39
40    /// `0x01 ‖ u32be(len(label)) ‖ label ‖ u64be(len(bytes)) ‖ bytes`.
41    pub fn append(&mut self, label: &str, bytes: &[u8]) -> &mut Self {
42        self.hasher.update([0x01]);
43        self.hasher.update((label.len() as u32).to_be_bytes());
44        self.hasher.update(label.as_bytes());
45        self.hasher.update((bytes.len() as u64).to_be_bytes());
46        self.hasher.update(bytes);
47        self
48    }
49
50    pub fn append_u64(&mut self, label: &str, v: u64) -> &mut Self {
51        self.append(label, &v.to_be_bytes())
52    }
53
54    /// Big-endian, left-padded to `len` bytes; fails if the value does not fit.
55    pub fn append_uint(&mut self, label: &str, x: &BoxedUint, len: usize) -> Result<&mut Self> {
56        let bytes = uint_to_be(x, len)?;
57        Ok(self.append(label, &bytes))
58    }
59
60    /// Residue of `m`, encoded with the fixed width of the modulus.
61    pub fn append_residue(&mut self, label: &str, m: &Modulus, x: &Residue) -> Result<&mut Self> {
62        let _ = m;
63        let len = (x.params().modulus().bits() as usize).div_ceil(8);
64        self.append_uint(label, &x.retrieve(), len)
65    }
66
67    /// Signed value in the §10.2 format for the interval `range`.
68    pub fn append_sbig(&mut self, label: &str, x: &SBig, range: SRange) -> Result<&mut Self> {
69        let bytes = x.to_bytes(range)?;
70        Ok(self.append(label, &bytes))
71    }
72
73    /// Forks the state and derives a challenge stream; the transcript itself is unchanged.
74    pub fn challenge(&self, label: &str) -> Challenge {
75        let mut h = self.hasher.clone();
76        h.update([0x02]);
77        h.update((label.len() as u32).to_be_bytes());
78        h.update(label.as_bytes());
79        let seed: [u8; 32] = h.finalize().into();
80        Challenge {
81            seed,
82            ctr: 0,
83            buf: Vec::new(),
84            pos: 0,
85        }
86    }
87}
88
89/// Deterministic byte stream `SHA-256(seed ‖ u32be(ctr))`, consumed sequentially.
90pub struct Challenge {
91    seed: [u8; 32],
92    ctr: u32,
93    buf: Vec<u8>,
94    pos: usize,
95}
96
97impl Challenge {
98    /// The 32-byte seed (e.g. the commitment `B` of `ro/kg-commit`).
99    pub fn seed(&self) -> [u8; 32] {
100        self.seed
101    }
102
103    pub fn bytes(&mut self, n: usize) -> Vec<u8> {
104        let mut out = Vec::with_capacity(n);
105        while out.len() < n {
106            if self.pos == self.buf.len() {
107                let mut h = Sha256::new();
108                h.update(self.seed);
109                h.update(self.ctr.to_be_bytes());
110                self.ctr = self.ctr.wrapping_add(1);
111                self.buf = h.finalize().to_vec();
112                self.pos = 0;
113            }
114            let take = (n - out.len()).min(self.buf.len() - self.pos);
115            out.extend_from_slice(&self.buf[self.pos..self.pos + take]);
116            self.pos += take;
117        }
118        out
119    }
120
121    /// Uniform integer below `2^n` (precision `n` rounded up to whole limbs, at least 64).
122    pub fn bits(&mut self, n: u32) -> BoxedUint {
123        let nbytes = (n as usize).div_ceil(8).max(1);
124        let mut b = self.bytes(nbytes);
125        let extra = nbytes as u32 * 8 - n;
126        if extra > 0 {
127            b[0] &= 0xff >> extra;
128        }
129        let prec = (nbytes as u32 * 8).next_multiple_of(64);
130        BoxedUint::from_be_slice(&b, prec).unwrap_or_else(|_| BoxedUint::zero_with_precision(prec))
131    }
132
133    /// `e ∈ ±2^ℓ`: `u − 2^{ℓ−1} + 1` for an `ℓ`-bit `u` (§10.3).
134    pub fn pm_pow2(&mut self, ell: u32) -> SBig {
135        let u = SBig::from_uint(self.bits(ell));
136        let shift = SBig::from_uint(
137            BoxedUint::one_with_precision(ell.next_multiple_of(64) + 64).shl(ell.saturating_sub(1)),
138        );
139        u.sub(&shift).add(&SBig::from_i64(1))
140    }
141
142    /// `ℓ0`-bit unsigned challenge as a small integer.
143    pub fn small(&mut self, n: u32) -> u64 {
144        debug_assert!(n <= 64);
145        let b = self.bits(n);
146        b.as_words()[0]
147    }
148
149    /// Scalar of `F_q`: 64 bytes reduced modulo `q`.
150    pub fn scalar(&mut self) -> Scalar {
151        let b = self.bytes(64);
152        <Scalar as Reduce<U512>>::reduce(&U512::from_be_slice(&b))
153    }
154
155    /// `y ∈ Z*_M`: `bits(M)+128` bits reduced mod `M`, next block while `gcd(y, M) ≠ 1`.
156    pub fn unit_mod(&mut self, m: &Modulus) -> Result<Residue> {
157        let nbits = m.modulus().bits();
158        for _ in 0..64 {
159            let y = self.bits(nbits + 128);
160            let mm = resized(m.modulus().as_ref(), y.bits_precision());
161            let nz = Option::<NonZero<BoxedUint>>::from(mm.to_nz()).ok_or(Error::InvalidModulus)?;
162            let r = y.rem_vartime(&nz);
163            let g = r.gcd_vartime(&mm);
164            if bool::from(g.is_one()) {
165                return Ok(m.residue(&r));
166            }
167        }
168        Err(Error::OutOfRange)
169    }
170
171    /// `g ∈ QR_d \ {0, 1}`: value mod `d` from the stream, squared.
172    pub fn qr_mod(&mut self, m: &Modulus) -> Result<Residue> {
173        let nbits = m.modulus().bits();
174        for _ in 0..64 {
175            let y = self.bits(nbits + 128);
176            let r = m.residue(&y);
177            let sq = r.square();
178            if !bool::from(sq.is_zero())
179                && sq.retrieve() != BoxedUint::one_with_precision(sq.bits_precision())
180            {
181                return Ok(sq);
182            }
183        }
184        Err(Error::OutOfRange)
185    }
186}
187
188/// Fixed-length big-endian encoding of a non-negative integer.
189pub fn uint_to_be(x: &BoxedUint, len: usize) -> Result<Vec<u8>> {
190    let be = x.to_be_bytes();
191    if be.len() >= len {
192        let (hi, lo) = be.split_at(be.len() - len);
193        if hi.iter().any(|b| *b != 0) {
194            return Err(Error::OutOfRange);
195        }
196        Ok(lo.to_vec())
197    } else {
198        let mut out = alloc::vec![0u8; len - be.len()];
199        out.extend_from_slice(&be);
200        Ok(out)
201    }
202}
203
204/// Decodes a fixed-length big-endian integer with at least `bits` of precision.
205pub fn uint_from_be(bytes: &[u8], bits: u32) -> Result<BoxedUint> {
206    let prec = bits.max(bytes.len() as u32 * 8).next_multiple_of(64);
207    BoxedUint::from_be_slice(&pad_left(bytes, prec as usize / 8), prec)
208        .map_err(|_| Error::InvalidEncoding)
209}
210
211fn pad_left(b: &[u8], len: usize) -> Vec<u8> {
212    let mut v = alloc::vec![0u8; len.saturating_sub(b.len())];
213    v.extend_from_slice(b);
214    v
215}
tecdsa_core/transcript.rs

tecdsa_core/
transcript.rs
