miden-crypto/src/dsa/rpo_falcon512/keys/secret_key.rs
src/dsa/rpo_falcon512/keys/secret_key.rsRaw
1use super::{
2 super::{
3 math::{ffldl, ffsampling, gram, normalize_tree, FalconFelt, FastFft, LdlTree, Polynomial},
4 signature::SignaturePoly,
5 ByteReader, ByteWriter, Deserializable, DeserializationError, Nonce, Serializable,
6 ShortLatticeBasis, Signature, Word, MODULUS, N, SIGMA, SIG_L2_BOUND,
7 },
8 PubKeyPoly, PublicKey,
9};
10use crate::dsa::rpo_falcon512::{
11 hash_to_point::hash_to_point_rpo256, math::ntru_gen, SIG_NONCE_LEN, SK_LEN,
12};
13use alloc::{string::ToString, vec::Vec};
14use num::Complex;
15use num_complex::Complex64;
16use rand::Rng;
17
18#[cfg(not(feature = "std"))]
19use num::Float;
20
21// CONSTANTS
22// ================================================================================================
23
24const WIDTH_BIG_POLY_COEFFICIENT: usize = 8;
25const WIDTH_SMALL_POLY_COEFFICIENT: usize = 6;
26
27// SECRET KEY
28// ================================================================================================
29
30/// The secret key is a quadruple [[g, -f], [G, -F]] of polynomials with integer coefficients. Each
31/// polynomial is of degree at most N = 512 and computations with these polynomials is done modulo
32/// the monic irreducible polynomial ϕ = x^N + 1. The secret key is a basis for a lattice and has
33/// the property of being short with respect to a certain norm and an upper bound appropriate for
34/// a given security parameter. The public key on the other hand is another basis for the same
35/// lattice and can be described by a single polynomial h with integer coefficients modulo ϕ.
36/// The two keys are related by the following relation:
37///
38/// 1. h = g /f [mod ϕ][mod p]
39/// 2. f.G - g.F = p [mod ϕ]
40///
41/// where p = 12289 is the Falcon prime. Equation 2 is called the NTRU equation.
42/// The secret key is generated by first sampling a random pair (f, g) of polynomials using
43/// an appropriate distribution that yields short but not too short polynomials with integer
44/// coefficients modulo ϕ. The NTRU equation is then used to find a matching pair (F, G).
45/// The public key is then derived from the secret key using equation 1.
46///
47/// To allow for fast signature generation, the secret key is pre-processed into a more suitable
48/// form, called the LDL tree, and this allows for fast sampling of short vectors in the lattice
49/// using Fast Fourier sampling during signature generation (ffSampling algorithm 11 in [1]).
50///
51/// [1]: https://falcon-sign.info/falcon.pdf
52#[derive(Debug, Clone)]
53pub struct SecretKey {
54 secret_key: ShortLatticeBasis,
55 tree: LdlTree,
56}
57
58#[allow(clippy::new_without_default)]
59impl SecretKey {
60 // CONSTRUCTORS
61 // --------------------------------------------------------------------------------------------
62
63 /// Generates a secret key from OS-provided randomness.
64 #[cfg(feature = "std")]
65 pub fn new() -> Self {
66 use rand::{rngs::StdRng, SeedableRng};
67
68 let mut rng = StdRng::from_entropy();
69 Self::with_rng(&mut rng)
70 }
71
72 /// Generates a secret_key using the provided random number generator `Rng`.
73 pub fn with_rng<R: Rng>(rng: &mut R) -> Self {
74 let basis = ntru_gen(N, rng);
75 Self::from_short_lattice_basis(basis)
76 }
77
78 /// Given a short basis [[g, -f], [G, -F]], computes the normalized LDL tree i.e., Falcon tree.
79 pub(crate) fn from_short_lattice_basis(basis: ShortLatticeBasis) -> SecretKey {
80 // FFT each polynomial of the short basis.
81 let basis_fft = to_complex_fft(&basis);
82 // compute the Gram matrix.
83 let gram_fft = gram(basis_fft);
84 // construct the LDL tree of the Gram matrix.
85 let mut tree = ffldl(gram_fft);
86 // normalize the leaves of the LDL tree.
87 normalize_tree(&mut tree, SIGMA);
88 Self { secret_key: basis, tree }
89 }
90
91 // PUBLIC ACCESSORS
92 // --------------------------------------------------------------------------------------------
93
94 /// Returns the polynomials of the short lattice basis of this secret key.
95 pub fn short_lattice_basis(&self) -> &ShortLatticeBasis {
96 &self.secret_key
97 }
98
99 /// Returns the public key corresponding to this secret key.
100 pub fn public_key(&self) -> PublicKey {
101 self.compute_pub_key_poly().into()
102 }
103
104 /// Returns the LDL tree associated to this secret key.
105 pub fn tree(&self) -> &LdlTree {
106 &self.tree
107 }
108
109 // SIGNATURE GENERATION
110 // --------------------------------------------------------------------------------------------
111
112 /// Signs a message with this secret key.
113 #[cfg(feature = "std")]
114 pub fn sign(&self, message: Word) -> Signature {
115 use rand::{rngs::StdRng, SeedableRng};
116
117 let mut rng = StdRng::from_entropy();
118 self.sign_with_rng(message, &mut rng)
119 }
120
121 /// Signs a message with the secret key relying on the provided randomness generator.
122 pub fn sign_with_rng<R: Rng>(&self, message: Word, rng: &mut R) -> Signature {
123 let mut nonce_bytes = [0u8; SIG_NONCE_LEN];
124 rng.fill_bytes(&mut nonce_bytes);
125 let nonce = Nonce::new(nonce_bytes);
126
127 let h = self.compute_pub_key_poly();
128 let c = hash_to_point_rpo256(message, &nonce);
129 let s2 = self.sign_helper(c, rng);
130
131 Signature::new(nonce, h, s2)
132 }
133
134 // HELPER METHODS
135 // --------------------------------------------------------------------------------------------
136
137 /// Derives the public key corresponding to this secret key using h = g /f [mod ϕ][mod p].
138 pub fn compute_pub_key_poly(&self) -> PubKeyPoly {
139 let g: Polynomial<FalconFelt> = self.secret_key[0].clone().into();
140 let g_fft = g.fft();
141 let minus_f: Polynomial<FalconFelt> = self.secret_key[1].clone().into();
142 let f = -minus_f;
143 let f_fft = f.fft();
144 let h_fft = g_fft.hadamard_div(&f_fft);
145 h_fft.ifft().into()
146 }
147
148 /// Signs a message polynomial with the secret key.
149 ///
150 /// Takes a randomness generator implementing `Rng` and message polynomial representing `c`
151 /// the hash-to-point of the message to be signed. It outputs a signature polynomial `s2`.
152 fn sign_helper<R: Rng>(&self, c: Polynomial<FalconFelt>, rng: &mut R) -> SignaturePoly {
153 let one_over_q = 1.0 / (MODULUS as f64);
154 let c_over_q_fft = c.map(|cc| Complex::new(one_over_q * cc.value() as f64, 0.0)).fft();
155
156 // B = [[FFT(g), -FFT(f)], [FFT(G), -FFT(F)]]
157 let [g_fft, minus_f_fft, big_g_fft, minus_big_f_fft] = to_complex_fft(&self.secret_key);
158 let t0 = c_over_q_fft.hadamard_mul(&minus_big_f_fft);
159 let t1 = -c_over_q_fft.hadamard_mul(&minus_f_fft);
160
161 loop {
162 let bold_s = loop {
163 let z = ffsampling(&(t0.clone(), t1.clone()), &self.tree, rng);
164 let t0_min_z0 = t0.clone() - z.0;
165 let t1_min_z1 = t1.clone() - z.1;
166
167 // s = (t-z) * B
168 let s0 = t0_min_z0.hadamard_mul(&g_fft) + t1_min_z1.hadamard_mul(&big_g_fft);
169 let s1 =
170 t0_min_z0.hadamard_mul(&minus_f_fft) + t1_min_z1.hadamard_mul(&minus_big_f_fft);
171
172 // compute the norm of (s0||s1) and note that they are in FFT representation
173 let length_squared: f64 =
174 (s0.coefficients.iter().map(|a| (a * a.conj()).re).sum::<f64>()
175 + s1.coefficients.iter().map(|a| (a * a.conj()).re).sum::<f64>())
176 / (N as f64);
177
178 if length_squared > (SIG_L2_BOUND as f64) {
179 continue;
180 }
181
182 break [-s0, s1];
183 };
184
185 let s2 = bold_s[1].ifft();
186 let s2_coef: [i16; N] = s2
187 .coefficients
188 .iter()
189 .map(|a| a.re.round() as i16)
190 .collect::<Vec<i16>>()
191 .try_into()
192 .expect("The number of coefficients should be equal to N");
193
194 if let Ok(s2) = SignaturePoly::try_from(&s2_coef) {
195 return s2;
196 }
197 }
198 }
199
200 // HELPER METHODS FOR TESTING
201 // --------------------------------------------------------------------------------------------
202
203 /// Signs a message with the secret key relying on the provided randomness generator.
204 #[cfg(test)]
205 pub fn sign_with_rng_testing<R: Rng>(
206 &self,
207 message: &[u8],
208 rng: &mut R,
209 skip_bytes: usize,
210 ) -> Signature {
211 use crate::dsa::rpo_falcon512::{
212 hash_to_point::hash_to_point_shake256, tests::ChaCha, CHACHA_SEED_LEN,
213 };
214
215 let mut dummy = vec![0_u8; skip_bytes];
216 rng.fill_bytes(&mut dummy);
217 let mut nonce_bytes = [0u8; SIG_NONCE_LEN];
218 rng.fill_bytes(&mut nonce_bytes);
219 let nonce = Nonce::new(nonce_bytes);
220
221 let h = self.compute_pub_key_poly();
222 let c = hash_to_point_shake256(message, &nonce);
223
224 let s2 = loop {
225 let mut chacha_seed = [0_u8; CHACHA_SEED_LEN];
226 rng.fill_bytes(&mut chacha_seed);
227
228 let mut chacha_prng = ChaCha::new(chacha_seed.to_vec());
229
230 let s2 = self.sign_helper_testing(c.clone(), &mut chacha_prng);
231 if let Some(s2) = s2 {
232 break s2;
233 }
234 };
235
236 Signature::new(nonce, h, s2)
237 }
238
239 /// Signs a message polynomial with the secret key.
240 ///
241 /// Takes a randomness generator implementing `Rng` and message polynomial representing `c`
242 /// the hash-to-point of the message to be signed. It outputs a signature polynomial `s2`.
243 #[cfg(test)]
244 fn sign_helper_testing<R: Rng>(
245 &self,
246 c: Polynomial<FalconFelt>,
247 rng: &mut R,
248 ) -> Option<SignaturePoly> {
249 let one_over_q = 1.0 / (MODULUS as f64);
250 let c_over_q_fft = c.map(|cc| Complex::new(one_over_q * cc.value() as f64, 0.0)).fft();
251
252 // B = [[FFT(g), -FFT(f)], [FFT(G), -FFT(F)]]
253 let [g_fft, minus_f_fft, big_g_fft, minus_big_f_fft] = to_complex_fft(&self.secret_key);
254 let t0 = c_over_q_fft.hadamard_mul(&minus_big_f_fft);
255 let t1 = -c_over_q_fft.hadamard_mul(&minus_f_fft);
256
257 let z = ffsampling(&(t0.clone(), t1.clone()), &self.tree, rng);
258 let t0_min_z0 = t0.clone() - z.0;
259 let t1_min_z1 = t1.clone() - z.1;
260
261 // s = (t-z) * B
262 let s0 = t0_min_z0.hadamard_mul(&g_fft) + t1_min_z1.hadamard_mul(&big_g_fft);
263 let s1 = t0_min_z0.hadamard_mul(&minus_f_fft) + t1_min_z1.hadamard_mul(&minus_big_f_fft);
264
265 // compute the norm of (s0||s1) and note that they are in FFT representation
266 let length_squared: f64 = (s0.coefficients.iter().map(|a| (a * a.conj()).re).sum::<f64>()
267 + s1.coefficients.iter().map(|a| (a * a.conj()).re).sum::<f64>())
268 / (N as f64);
269
270 if length_squared < (SIG_L2_BOUND as f64) {
271 let bold_s = [-s0, s1];
272
273 let s2 = bold_s[1].ifft();
274 let s2_coef: [i16; N] = s2
275 .coefficients
276 .iter()
277 .map(|a| a.re.round() as i16)
278 .collect::<Vec<i16>>()
279 .try_into()
280 .expect("The number of coefficients should be equal to N");
281
282 if let Ok(s2) = SignaturePoly::try_from(&s2_coef) {
283 return Some(s2);
284 } else {
285 return None;
286 }
287 } else {
288 return None;
289 }
290 }
291}
292
293// SERIALIZATION / DESERIALIZATION
294// ================================================================================================
295
296impl Serializable for SecretKey {
297 fn write_into<W: ByteWriter>(&self, target: &mut W) {
298 let basis = &self.secret_key;
299
300 // header
301 let n = basis[0].coefficients.len();
302 let l = n.checked_ilog2().unwrap() as u8;
303 let header: u8 = (5 << 4) | l;
304
305 let neg_f = &basis[1];
306 let g = &basis[0];
307 let neg_big_f = &basis[3];
308
309 let mut buffer = Vec::with_capacity(1281);
310 buffer.push(header);
311
312 let f_i8: Vec<i8> = neg_f.coefficients.iter().map(|&a| -a as i8).collect();
313 let f_i8_encoded = encode_i8(&f_i8, WIDTH_SMALL_POLY_COEFFICIENT).unwrap();
314 buffer.extend_from_slice(&f_i8_encoded);
315
316 let g_i8: Vec<i8> = g.coefficients.iter().map(|&a| a as i8).collect();
317 let g_i8_encoded = encode_i8(&g_i8, WIDTH_SMALL_POLY_COEFFICIENT).unwrap();
318 buffer.extend_from_slice(&g_i8_encoded);
319
320 let big_f_i8: Vec<i8> = neg_big_f.coefficients.iter().map(|&a| -a as i8).collect();
321 let big_f_i8_encoded = encode_i8(&big_f_i8, WIDTH_BIG_POLY_COEFFICIENT).unwrap();
322 buffer.extend_from_slice(&big_f_i8_encoded);
323 target.write_bytes(&buffer);
324 }
325}
326
327impl Deserializable for SecretKey {
328 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
329 let byte_vector: [u8; SK_LEN] = source.read_array()?;
330
331 // check length
332 if byte_vector.len() < 2 {
333 return Err(DeserializationError::InvalidValue("Invalid encoding length: Failed to decode as length is different from the one expected".to_string()));
334 }
335
336 // read fields
337 let header = byte_vector[0];
338
339 // check fixed bits in header
340 if (header >> 4) != 5 {
341 return Err(DeserializationError::InvalidValue("Invalid header format".to_string()));
342 }
343
344 // check log n
345 let logn = (header & 15) as usize;
346 let n = 1 << logn;
347
348 // match against const variant generic parameter
349 if n != N {
350 return Err(DeserializationError::InvalidValue(
351 "Unsupported Falcon DSA variant".to_string(),
352 ));
353 }
354
355 if byte_vector.len() != SK_LEN {
356 return Err(DeserializationError::InvalidValue("Invalid encoding length: Failed to decode as length is different from the one expected".to_string()));
357 }
358
359 let chunk_size_f = ((n * WIDTH_SMALL_POLY_COEFFICIENT) + 7) >> 3;
360 let chunk_size_g = ((n * WIDTH_SMALL_POLY_COEFFICIENT) + 7) >> 3;
361 let chunk_size_big_f = ((n * WIDTH_BIG_POLY_COEFFICIENT) + 7) >> 3;
362
363 let f = decode_i8(&byte_vector[1..chunk_size_f + 1], WIDTH_SMALL_POLY_COEFFICIENT).unwrap();
364 let g = decode_i8(
365 &byte_vector[chunk_size_f + 1..(chunk_size_f + chunk_size_g + 1)],
366 WIDTH_SMALL_POLY_COEFFICIENT,
367 )
368 .unwrap();
369 let big_f = decode_i8(
370 &byte_vector[(chunk_size_f + chunk_size_g + 1)
371 ..(chunk_size_f + chunk_size_g + chunk_size_big_f + 1)],
372 WIDTH_BIG_POLY_COEFFICIENT,
373 )
374 .unwrap();
375
376 let f = Polynomial::new(f.iter().map(|&c| FalconFelt::new(c.into())).collect());
377 let g = Polynomial::new(g.iter().map(|&c| FalconFelt::new(c.into())).collect());
378 let big_f = Polynomial::new(big_f.iter().map(|&c| FalconFelt::new(c.into())).collect());
379
380 // big_g * f - g * big_f = p (mod X^n + 1)
381 let big_g = g.fft().hadamard_div(&f.fft()).hadamard_mul(&big_f.fft()).ifft();
382 let basis = [
383 g.map(|f| f.balanced_value()),
384 -f.map(|f| f.balanced_value()),
385 big_g.map(|f| f.balanced_value()),
386 -big_f.map(|f| f.balanced_value()),
387 ];
388 Ok(Self::from_short_lattice_basis(basis))
389 }
390}
391
392// HELPER FUNCTIONS
393// ================================================================================================
394
395/// Computes the complex FFT of the secret key polynomials.
396fn to_complex_fft(basis: &[Polynomial<i16>; 4]) -> [Polynomial<Complex<f64>>; 4] {
397 let [g, f, big_g, big_f] = basis.clone();
398 let g_fft = g.map(|cc| Complex64::new(*cc as f64, 0.0)).fft();
399 let minus_f_fft = f.map(|cc| Complex64::new(*cc as f64, 0.0)).fft();
400 let big_g_fft = big_g.map(|cc| Complex64::new(*cc as f64, 0.0)).fft();
401 let minus_big_f_fft = big_f.map(|cc| Complex64::new(*cc as f64, 0.0)).fft();
402 [g_fft, minus_f_fft, big_g_fft, minus_big_f_fft]
403}
404
405/// Encodes a sequence of signed integers such that each integer x satisfies |x| < 2^(bits-1)
406/// for a given parameter bits. bits can take either the value 6 or 8.
407pub fn encode_i8(x: &[i8], bits: usize) -> Option<Vec<u8>> {
408 let maxv = (1 << (bits - 1)) - 1_usize;
409 let maxv = maxv as i8;
410 let minv = -maxv;
411
412 for &c in x {
413 if c > maxv || c < minv {
414 return None;
415 }
416 }
417
418 let out_len = ((N * bits) + 7) >> 3;
419 let mut buf = vec![0_u8; out_len];
420
421 let mut acc = 0_u32;
422 let mut acc_len = 0;
423 let mask = ((1_u16 << bits) - 1) as u8;
424
425 let mut input_pos = 0;
426 for &c in x {
427 acc = (acc << bits) | (c as u8 & mask) as u32;
428 acc_len += bits;
429 while acc_len >= 8 {
430 acc_len -= 8;
431 buf[input_pos] = (acc >> acc_len) as u8;
432 input_pos += 1;
433 }
434 }
435 if acc_len > 0 {
436 buf[input_pos] = (acc >> (8 - acc_len)) as u8;
437 }
438
439 Some(buf)
440}
441
442/// Decodes a sequence of bytes into a sequence of signed integers such that each integer x
443/// satisfies |x| < 2^(bits-1) for a given parameter bits. bits can take either the value 6 or 8.
444pub fn decode_i8(buf: &[u8], bits: usize) -> Option<Vec<i8>> {
445 let mut x = [0_i8; N];
446
447 let mut i = 0;
448 let mut j = 0;
449 let mut acc = 0_u32;
450 let mut acc_len = 0;
451 let mask = (1_u32 << bits) - 1;
452 let a = (1 << bits) as u8;
453 let b = ((1 << (bits - 1)) - 1) as u8;
454
455 while i < N {
456 acc = (acc << 8) | (buf[j] as u32);
457 j += 1;
458 acc_len += 8;
459
460 while acc_len >= bits && i < N {
461 acc_len -= bits;
462 let w = (acc >> acc_len) & mask;
463
464 let w = w as u8;
465
466 let z = if w > b { w as i8 - a as i8 } else { w as i8 };
467
468 x[i] = z;
469 i += 1;
470 }
471 }
472
473 if (acc & ((1u32 << acc_len) - 1)) == 0 {
474 Some(x.to_vec())
475 } else {
476 None
477 }
478}