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