miden-crypto/src/dsa/rpo_falcon512/falcon_c/falcon.c
src/dsa/rpo_falcon512/falcon_c/falcon.cRaw
1/*
2 * Wrapper for implementing the PQClean API.
3 */
4
5#include <string.h>
6#include "randombytes.h"
7#include "falcon.h"
8#include "inner.h"
9#include "rpo.h"
10
11#define NONCELEN 40
12
13/*
14 * Encoding formats (nnnn = log of degree, 9 for Falcon-512, 10 for Falcon-1024)
15 *
16 * private key:
17 * header byte: 0101nnnn
18 * private f (6 or 5 bits by element, depending on degree)
19 * private g (6 or 5 bits by element, depending on degree)
20 * private F (8 bits by element)
21 *
22 * public key:
23 * header byte: 0000nnnn
24 * public h (14 bits by element)
25 *
26 * signature:
27 * header byte: 0011nnnn
28 * nonce 40 bytes
29 * value (12 bits by element)
30 *
31 * message + signature:
32 * signature length (2 bytes, big-endian)
33 * nonce 40 bytes
34 * message
35 * header byte: 0010nnnn
36 * value (12 bits by element)
37 * (signature length is 1+len(value), not counting the nonce)
38 */
39
40/* see falcon.h */
41int PQCLEAN_FALCON512_CLEAN_crypto_sign_keypair_from_seed_rpo(
42 uint8_t *pk,
43 uint8_t *sk,
44 unsigned char *seed
45) {
46 union
47 {
48 uint8_t b[FALCON_KEYGEN_TEMP_9];
49 uint64_t dummy_u64;
50 fpr dummy_fpr;
51 } tmp;
52 int8_t f[512], g[512], F[512];
53 uint16_t h[512];
54 inner_shake256_context rng;
55 size_t u, v;
56
57 /*
58 * Generate key pair.
59 */
60 inner_shake256_init(&rng);
61 inner_shake256_inject(&rng, seed, sizeof seed);
62 inner_shake256_flip(&rng);
63 PQCLEAN_FALCON512_CLEAN_keygen(&rng, f, g, F, NULL, h, 9, tmp.b);
64 inner_shake256_ctx_release(&rng);
65
66 /*
67 * Encode private key.
68 */
69 sk[0] = 0x50 + 9;
70 u = 1;
71 v = PQCLEAN_FALCON512_CLEAN_trim_i8_encode(
72 sk + u, PQCLEAN_FALCON512_CLEAN_CRYPTO_SECRETKEYBYTES - u,
73 f, 9, PQCLEAN_FALCON512_CLEAN_max_fg_bits[9]);
74 if (v == 0)
75 {
76 return -1;
77 }
78 u += v;
79 v = PQCLEAN_FALCON512_CLEAN_trim_i8_encode(
80 sk + u, PQCLEAN_FALCON512_CLEAN_CRYPTO_SECRETKEYBYTES - u,
81 g, 9, PQCLEAN_FALCON512_CLEAN_max_fg_bits[9]);
82 if (v == 0)
83 {
84 return -1;
85 }
86 u += v;
87 v = PQCLEAN_FALCON512_CLEAN_trim_i8_encode(
88 sk + u, PQCLEAN_FALCON512_CLEAN_CRYPTO_SECRETKEYBYTES - u,
89 F, 9, PQCLEAN_FALCON512_CLEAN_max_FG_bits[9]);
90 if (v == 0)
91 {
92 return -1;
93 }
94 u += v;
95 if (u != PQCLEAN_FALCON512_CLEAN_CRYPTO_SECRETKEYBYTES)
96 {
97 return -1;
98 }
99
100 /*
101 * Encode public key.
102 */
103 pk[0] = 0x00 + 9;
104 v = PQCLEAN_FALCON512_CLEAN_modq_encode(
105 pk + 1, PQCLEAN_FALCON512_CLEAN_CRYPTO_PUBLICKEYBYTES - 1,
106 h, 9);
107 if (v != PQCLEAN_FALCON512_CLEAN_CRYPTO_PUBLICKEYBYTES - 1)
108 {
109 return -1;
110 }
111
112 return 0;
113}
114
115int PQCLEAN_FALCON512_CLEAN_crypto_sign_keypair_rpo(
116 uint8_t *pk,
117 uint8_t *sk
118) {
119 unsigned char seed[48];
120
121 /*
122 * Generate a random seed.
123 */
124 randombytes(seed, sizeof seed);
125
126 return PQCLEAN_FALCON512_CLEAN_crypto_sign_keypair_from_seed_rpo(pk, sk, seed);
127}
128
129/*
130 * Compute the signature. nonce[] receives the nonce and must have length
131 * NONCELEN bytes. sigbuf[] receives the signature value (without nonce
132 * or header byte), with *sigbuflen providing the maximum value length and
133 * receiving the actual value length.
134 *
135 * If a signature could be computed but not encoded because it would
136 * exceed the output buffer size, then a new signature is computed. If
137 * the provided buffer size is too low, this could loop indefinitely, so
138 * the caller must provide a size that can accommodate signatures with a
139 * large enough probability.
140 *
141 * Return value: 0 on success, -1 on error.
142 */
143static int do_sign(
144 uint8_t *nonce,
145 uint8_t *sigbuf,
146 size_t *sigbuflen,
147 const uint8_t *m,
148 size_t mlen,
149 const uint8_t *sk
150) {
151 union
152 {
153 uint8_t b[72 * 512];
154 uint64_t dummy_u64;
155 fpr dummy_fpr;
156 } tmp;
157 int8_t f[512], g[512], F[512], G[512];
158 struct
159 {
160 int16_t sig[512];
161 uint16_t hm[512];
162 } r;
163 unsigned char seed[48];
164 inner_shake256_context sc;
165 rpo128_context rc;
166 size_t u, v;
167
168 /*
169 * Decode the private key.
170 */
171 if (sk[0] != 0x50 + 9)
172 {
173 return -1;
174 }
175 u = 1;
176 v = PQCLEAN_FALCON512_CLEAN_trim_i8_decode(
177 f, 9, PQCLEAN_FALCON512_CLEAN_max_fg_bits[9],
178 sk + u, PQCLEAN_FALCON512_CLEAN_CRYPTO_SECRETKEYBYTES - u);
179 if (v == 0)
180 {
181 return -1;
182 }
183 u += v;
184 v = PQCLEAN_FALCON512_CLEAN_trim_i8_decode(
185 g, 9, PQCLEAN_FALCON512_CLEAN_max_fg_bits[9],
186 sk + u, PQCLEAN_FALCON512_CLEAN_CRYPTO_SECRETKEYBYTES - u);
187 if (v == 0)
188 {
189 return -1;
190 }
191 u += v;
192 v = PQCLEAN_FALCON512_CLEAN_trim_i8_decode(
193 F, 9, PQCLEAN_FALCON512_CLEAN_max_FG_bits[9],
194 sk + u, PQCLEAN_FALCON512_CLEAN_CRYPTO_SECRETKEYBYTES - u);
195 if (v == 0)
196 {
197 return -1;
198 }
199 u += v;
200 if (u != PQCLEAN_FALCON512_CLEAN_CRYPTO_SECRETKEYBYTES)
201 {
202 return -1;
203 }
204 if (!PQCLEAN_FALCON512_CLEAN_complete_private(G, f, g, F, 9, tmp.b))
205 {
206 return -1;
207 }
208
209 /*
210 * Create a random nonce (40 bytes).
211 */
212 randombytes(nonce, NONCELEN);
213
214 /* ==== Start: Deviation from the reference implementation ================================= */
215
216 // Transform the nonce into 8 chunks each of size 5 bytes. We do this in order to be sure that
217 // the conversion to field elements succeeds
218 uint8_t buffer[64];
219 memset(buffer, 0, 64);
220 for (size_t i = 0; i < 8; i++)
221 {
222 buffer[8 * i] = nonce[5 * i];
223 buffer[8 * i + 1] = nonce[5 * i + 1];
224 buffer[8 * i + 2] = nonce[5 * i + 2];
225 buffer[8 * i + 3] = nonce[5 * i + 3];
226 buffer[8 * i + 4] = nonce[5 * i + 4];
227 }
228
229 /*
230 * Hash message nonce + message into a vector.
231 */
232 rpo128_init(&rc);
233 rpo128_absorb(&rc, buffer, NONCELEN + 24);
234 rpo128_absorb(&rc, m, mlen);
235 rpo128_finalize(&rc);
236 PQCLEAN_FALCON512_CLEAN_hash_to_point_rpo(&rc, r.hm, 9);
237 rpo128_release(&rc);
238
239 /* ==== End: Deviation from the reference implementation =================================== */
240
241 /*
242 * Initialize a RNG.
243 */
244 randombytes(seed, sizeof seed);
245 inner_shake256_init(&sc);
246 inner_shake256_inject(&sc, seed, sizeof seed);
247 inner_shake256_flip(&sc);
248
249 /*
250 * Compute and return the signature. This loops until a signature
251 * value is found that fits in the provided buffer.
252 */
253 for (;;)
254 {
255 PQCLEAN_FALCON512_CLEAN_sign_dyn(r.sig, &sc, f, g, F, G, r.hm, 9, tmp.b);
256 v = PQCLEAN_FALCON512_CLEAN_comp_encode(sigbuf, *sigbuflen, r.sig, 9);
257 if (v != 0)
258 {
259 inner_shake256_ctx_release(&sc);
260 *sigbuflen = v;
261 return 0;
262 }
263 }
264}
265
266/*
267 * Verify a signature. The nonce has size NONCELEN bytes. sigbuf[]
268 * (of size sigbuflen) contains the signature value, not including the
269 * header byte or nonce. Return value is 0 on success, -1 on error.
270 */
271static int do_verify(
272 const uint8_t *nonce,
273 const uint8_t *sigbuf,
274 size_t sigbuflen,
275 const uint8_t *m,
276 size_t mlen,
277 const uint8_t *pk
278) {
279 union
280 {
281 uint8_t b[2 * 512];
282 uint64_t dummy_u64;
283 fpr dummy_fpr;
284 } tmp;
285 uint16_t h[512], hm[512];
286 int16_t sig[512];
287 rpo128_context rc;
288
289 /*
290 * Decode public key.
291 */
292 if (pk[0] != 0x00 + 9)
293 {
294 return -1;
295 }
296 if (PQCLEAN_FALCON512_CLEAN_modq_decode(h, 9,
297 pk + 1, PQCLEAN_FALCON512_CLEAN_CRYPTO_PUBLICKEYBYTES - 1)
298 != PQCLEAN_FALCON512_CLEAN_CRYPTO_PUBLICKEYBYTES - 1)
299 {
300 return -1;
301 }
302 PQCLEAN_FALCON512_CLEAN_to_ntt_monty(h, 9);
303
304 /*
305 * Decode signature.
306 */
307 if (sigbuflen == 0)
308 {
309 return -1;
310 }
311 if (PQCLEAN_FALCON512_CLEAN_comp_decode(sig, 9, sigbuf, sigbuflen) != sigbuflen)
312 {
313 return -1;
314 }
315
316 /* ==== Start: Deviation from the reference implementation ================================= */
317
318 /*
319 * Hash nonce + message into a vector.
320 */
321
322 // Transform the nonce into 8 chunks each of size 5 bytes. We do this in order to be sure that
323 // the conversion to field elements succeeds
324 uint8_t buffer[64];
325 memset(buffer, 0, 64);
326 for (size_t i = 0; i < 8; i++)
327 {
328 buffer[8 * i] = nonce[5 * i];
329 buffer[8 * i + 1] = nonce[5 * i + 1];
330 buffer[8 * i + 2] = nonce[5 * i + 2];
331 buffer[8 * i + 3] = nonce[5 * i + 3];
332 buffer[8 * i + 4] = nonce[5 * i + 4];
333 }
334
335 rpo128_init(&rc);
336 rpo128_absorb(&rc, buffer, NONCELEN + 24);
337 rpo128_absorb(&rc, m, mlen);
338 rpo128_finalize(&rc);
339 PQCLEAN_FALCON512_CLEAN_hash_to_point_rpo(&rc, hm, 9);
340 rpo128_release(&rc);
341
342 /* === End: Deviation from the reference implementation ==================================== */
343
344 /*
345 * Verify signature.
346 */
347 if (!PQCLEAN_FALCON512_CLEAN_verify_raw(hm, sig, h, 9, tmp.b))
348 {
349 return -1;
350 }
351 return 0;
352}
353
354/* see falcon.h */
355int PQCLEAN_FALCON512_CLEAN_crypto_sign_signature_rpo(
356 uint8_t *sig,
357 size_t *siglen,
358 const uint8_t *m,
359 size_t mlen,
360 const uint8_t *sk
361) {
362 /*
363 * The PQCLEAN_FALCON512_CLEAN_CRYPTO_BYTES constant is used for
364 * the signed message object (as produced by crypto_sign())
365 * and includes a two-byte length value, so we take care here
366 * to only generate signatures that are two bytes shorter than
367 * the maximum. This is done to ensure that crypto_sign()
368 * and crypto_sign_signature() produce the exact same signature
369 * value, if used on the same message, with the same private key,
370 * and using the same output from randombytes() (this is for
371 * reproducibility of tests).
372 */
373 size_t vlen;
374
375 vlen = PQCLEAN_FALCON512_CLEAN_CRYPTO_BYTES - NONCELEN - 3;
376 if (do_sign(sig + 1, sig + 1 + NONCELEN, &vlen, m, mlen, sk) < 0)
377 {
378 return -1;
379 }
380 sig[0] = 0x30 + 9;
381 *siglen = 1 + NONCELEN + vlen;
382 return 0;
383}
384
385/* see falcon.h */
386int PQCLEAN_FALCON512_CLEAN_crypto_sign_verify_rpo(
387 const uint8_t *sig,
388 size_t siglen,
389 const uint8_t *m,
390 size_t mlen,
391 const uint8_t *pk
392) {
393 if (siglen < 1 + NONCELEN)
394 {
395 return -1;
396 }
397 if (sig[0] != 0x30 + 9)
398 {
399 return -1;
400 }
401 return do_verify(sig + 1, sig + 1 + NONCELEN, siglen - 1 - NONCELEN, m, mlen, pk);
402}