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