miden-crypto/src/dsa/rpo_falcon512/signature.rs
src/dsa/rpo_falcon512/signature.rsRaw
1use super::{
2 ByteReader, ByteWriter, Deserializable, DeserializationError, NonceBytes, NonceElements,
3 Polynomial, PublicKeyBytes, Rpo256, Serializable, SignatureBytes, StarkField, Word, MODULUS, N,
4 SIG_L2_BOUND, ZERO,
5};
6use crate::utils::string::ToString;
7
8// FALCON SIGNATURE
9// ================================================================================================
10
11/// An RPO Falcon512 signature over a message.
12///
13/// The signature is a pair of polynomials (s1, s2) in (Z_p[x]/(phi))^2, where:
14/// - p := 12289
15/// - phi := x^512 + 1
16/// - s1 = c - s2 * h
17/// - h is a polynomial representing the public key and c is a polynomial that is the hash-to-point
18/// of the message being signed.
19///
20/// The signature verifies if and only if:
21/// 1. s1 = c - s2 * h
22/// 2. |s1|^2 + |s2|^2 <= SIG_L2_BOUND
23///
24/// where |.| is the norm.
25///
26/// [Signature] also includes the extended public key which is serialized as:
27/// 1. 1 byte representing the log2(512) i.e., 9.
28/// 2. 896 bytes for the public key. This is decoded into the `h` polynomial above.
29///
30/// The actual signature is serialized as:
31/// 1. A header byte specifying the algorithm used to encode the coefficients of the `s2` polynomial
32/// together with the degree of the irreducible polynomial phi.
33/// The general format of this byte is 0b0cc1nnnn where:
34/// a. cc is either 01 when the compressed encoding algorithm is used and 10 when the
35/// uncompressed algorithm is used.
36/// b. nnnn is log2(N) where N is the degree of the irreducible polynomial phi.
37/// The current implementation works always with cc equal to 0b01 and nnnn equal to 0b1001 and
38/// thus the header byte is always equal to 0b00111001.
39/// 2. 40 bytes for the nonce.
40/// 3. 625 bytes encoding the `s2` polynomial above.
41///
42/// The total size of the signature (including the extended public key) is 1563 bytes.
43pub struct Signature {
44 pub(super) pk: PublicKeyBytes,
45 pub(super) sig: SignatureBytes,
46}
47
48impl Signature {
49 // PUBLIC ACCESSORS
50 // --------------------------------------------------------------------------------------------
51
52 /// Returns the public key polynomial h.
53 pub fn pub_key_poly(&self) -> Polynomial {
54 // TODO: memoize
55 // we assume that the signature was constructed with a valid public key, and thus
56 // expect() is OK here.
57 Polynomial::from_pub_key(&self.pk).expect("invalid public key")
58 }
59
60 /// Returns the nonce component of the signature represented as field elements.
61 ///
62 /// Nonce bytes are converted to field elements by taking consecutive 5 byte chunks
63 /// of the nonce and interpreting them as field elements.
64 pub fn nonce(&self) -> NonceElements {
65 // we assume that the signature was constructed with a valid signature, and thus
66 // expect() is OK here.
67 let nonce = self.sig[1..41].try_into().expect("invalid signature");
68 decode_nonce(nonce)
69 }
70
71 // Returns the polynomial representation of the signature in Z_p[x]/(phi).
72 pub fn sig_poly(&self) -> Polynomial {
73 // TODO: memoize
74 // we assume that the signature was constructed with a valid signature, and thus
75 // expect() is OK here.
76 Polynomial::from_signature(&self.sig).expect("invalid signature")
77 }
78
79 // HASH-TO-POINT
80 // --------------------------------------------------------------------------------------------
81
82 /// Returns a polynomial in Z_p[x]/(phi) representing the hash of the provided message.
83 pub fn hash_to_point(&self, message: Word) -> Polynomial {
84 hash_to_point(message, &self.nonce())
85 }
86
87 // SIGNATURE VERIFICATION
88 // --------------------------------------------------------------------------------------------
89 /// Returns true if this signature is a valid signature for the specified message generated
90 /// against key pair matching the specified public key commitment.
91 pub fn verify(&self, message: Word, pubkey_com: Word) -> bool {
92 // Make sure the expanded public key matches the provided public key commitment
93 let h = self.pub_key_poly();
94 let h_digest: Word = Rpo256::hash_elements(&h.to_elements()).into();
95 if h_digest != pubkey_com {
96 return false;
97 }
98
99 // Make sure the signature is valid
100 let s2 = self.sig_poly();
101 let c = self.hash_to_point(message);
102
103 let s1 = c - s2 * h;
104
105 let sq_norm = s1.sq_norm() + s2.sq_norm();
106 sq_norm <= SIG_L2_BOUND
107 }
108}
109
110// SERIALIZATION / DESERIALIZATION
111// ================================================================================================
112
113impl Serializable for Signature {
114 fn write_into<W: ByteWriter>(&self, target: &mut W) {
115 target.write_bytes(&self.pk);
116 target.write_bytes(&self.sig);
117 }
118}
119
120impl Deserializable for Signature {
121 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
122 let pk: PublicKeyBytes = source.read_array()?;
123 let sig: SignatureBytes = source.read_array()?;
124
125 // make sure public key and signature can be decoded correctly
126 Polynomial::from_pub_key(&pk)
127 .map_err(|err| DeserializationError::InvalidValue(err.to_string()))?;
128 Polynomial::from_signature(&sig[41..])
129 .map_err(|err| DeserializationError::InvalidValue(err.to_string()))?;
130
131 Ok(Self { pk, sig })
132 }
133}
134
135// HELPER FUNCTIONS
136// ================================================================================================
137
138/// Returns a polynomial in Z_p[x]/(phi) representing the hash of the provided message and
139/// nonce.
140fn hash_to_point(message: Word, nonce: &NonceElements) -> Polynomial {
141 let mut state = [ZERO; Rpo256::STATE_WIDTH];
142
143 // absorb the nonce into the state
144 for (&n, s) in nonce.iter().zip(state[Rpo256::RATE_RANGE].iter_mut()) {
145 *s = n;
146 }
147 Rpo256::apply_permutation(&mut state);
148
149 // absorb message into the state
150 for (&m, s) in message.iter().zip(state[Rpo256::RATE_RANGE].iter_mut()) {
151 *s = m;
152 }
153
154 // squeeze the coefficients of the polynomial
155 let mut i = 0;
156 let mut res = [0_u16; N];
157 for _ in 0..64 {
158 Rpo256::apply_permutation(&mut state);
159 for a in &state[Rpo256::RATE_RANGE] {
160 res[i] = (a.as_int() % MODULUS as u64) as u16;
161 i += 1;
162 }
163 }
164
165 // using the raw constructor is OK here because we reduce all coefficients by the modulus above
166 unsafe { Polynomial::new(res) }
167}
168
169/// Converts byte representation of the nonce into field element representation.
170fn decode_nonce(nonce: &NonceBytes) -> NonceElements {
171 let mut buffer = [0_u8; 8];
172 let mut result = [ZERO; 8];
173 for (i, bytes) in nonce.chunks(5).enumerate() {
174 buffer[..5].copy_from_slice(bytes);
175 result[i] = u64::from_le_bytes(buffer).into();
176 }
177
178 result
179}
180
181// TESTS
182// ================================================================================================
183
184#[cfg(all(test, feature = "std"))]
185mod tests {
186 use super::{
187 super::{ffi::*, Felt},
188 *,
189 };
190 use libc::c_void;
191 use rand_utils::rand_vector;
192
193 // Wrappers for unsafe functions
194 impl Rpo128Context {
195 /// Initializes the RPO state.
196 pub fn init() -> Self {
197 let mut ctx = Rpo128Context { content: [0u64; 13] };
198 unsafe {
199 rpo128_init(&mut ctx as *mut Rpo128Context);
200 }
201 ctx
202 }
203
204 /// Absorbs data into the RPO state.
205 pub fn absorb(&mut self, data: &[u8]) {
206 unsafe {
207 rpo128_absorb(
208 self as *mut Rpo128Context,
209 data.as_ptr() as *const c_void,
210 data.len(),
211 )
212 }
213 }
214
215 /// Finalizes the RPO state to prepare for squeezing.
216 pub fn finalize(&mut self) {
217 unsafe { rpo128_finalize(self as *mut Rpo128Context) }
218 }
219 }
220
221 #[test]
222 fn test_hash_to_point() {
223 // Create a random message and transform it into a u8 vector
224 let msg_felts: Word = rand_vector::<Felt>(4).try_into().unwrap();
225 let msg_bytes = msg_felts.iter().flat_map(|e| e.as_int().to_le_bytes()).collect::<Vec<_>>();
226
227 // Create a nonce i.e. a [u8; 40] array and pack into a [Felt; 8] array.
228 let nonce: [u8; 40] = rand_vector::<u8>(40).try_into().unwrap();
229
230 let mut buffer = [0_u8; 64];
231 for i in 0..8 {
232 buffer[8 * i] = nonce[5 * i];
233 buffer[8 * i + 1] = nonce[5 * i + 1];
234 buffer[8 * i + 2] = nonce[5 * i + 2];
235 buffer[8 * i + 3] = nonce[5 * i + 3];
236 buffer[8 * i + 4] = nonce[5 * i + 4];
237 }
238
239 // Initialize the RPO state
240 let mut rng = Rpo128Context::init();
241
242 // Absorb the nonce and message into the RPO state
243 rng.absorb(&buffer);
244 rng.absorb(&msg_bytes);
245 rng.finalize();
246
247 // Generate the coefficients of the hash-to-point polynomial.
248 let mut res: [u16; N] = [0; N];
249
250 unsafe {
251 PQCLEAN_FALCON512_CLEAN_hash_to_point_rpo(
252 &mut rng as *mut Rpo128Context,
253 res.as_mut_ptr(),
254 9,
255 );
256 }
257
258 // Check that the coefficients are correct
259 let nonce = decode_nonce(&nonce);
260 assert_eq!(res, hash_to_point(msg_felts, &nonce).inner());
261 }
262}