Falcon source files (reference implementation)


falcon.c

    1 /*
    2  * Implementation of the external Falcon API.
    3  *
    4  * ==========================(LICENSE BEGIN)============================
    5  *
    6  * Copyright (c) 2017-2019  Falcon Project
    7  *
    8  * Permission is hereby granted, free of charge, to any person obtaining
    9  * a copy of this software and associated documentation files (the
   10  * "Software"), to deal in the Software without restriction, including
   11  * without limitation the rights to use, copy, modify, merge, publish,
   12  * distribute, sublicense, and/or sell copies of the Software, and to
   13  * permit persons to whom the Software is furnished to do so, subject to
   14  * the following conditions:
   15  *
   16  * The above copyright notice and this permission notice shall be
   17  * included in all copies or substantial portions of the Software.
   18  *
   19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   20  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   21  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
   22  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
   23  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
   24  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
   25  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
   26  *
   27  * ===========================(LICENSE END)=============================
   28  *
   29  * @author   Thomas Pornin <thomas.pornin@nccgroup.com>
   30  */
   31 
   32 #include "falcon.h"
   33 #include "inner.h"
   34 
   35 /* see falcon.h */
   36 void
   37 shake256_init(shake256_context *sc)
   38 {
   39         inner_shake256_init((inner_shake256_context *)sc);
   40 }
   41 
   42 /* see falcon.h */
   43 void
   44 shake256_inject(shake256_context *sc, const void *data, size_t len)
   45 {
   46         inner_shake256_inject((inner_shake256_context *)sc, data, len);
   47 }
   48 
   49 /* see falcon.h */
   50 void
   51 shake256_flip(shake256_context *sc)
   52 {
   53         inner_shake256_flip((inner_shake256_context *)sc);
   54 }
   55 
   56 /* see falcon.h */
   57 void
   58 shake256_extract(shake256_context *sc, void *out, size_t len)
   59 {
   60         inner_shake256_extract((inner_shake256_context *)sc, out, len);
   61 }
   62 
   63 /* see falcon.h */
   64 void
   65 shake256_init_prng_from_seed(shake256_context *sc,
   66         const void *seed, size_t seed_len)
   67 {
   68         shake256_init(sc);
   69         shake256_inject(sc, seed, seed_len);
   70 }
   71 
   72 /* see falcon.h */
   73 int
   74 shake256_init_prng_from_system(shake256_context *sc)
   75 {
   76         uint8_t seed[48];
   77 
   78         if (!Zf(get_seed)(seed, sizeof seed)) {
   79                 return FALCON_ERR_RANDOM;
   80         }
   81         shake256_init(sc);
   82         shake256_inject(sc, seed, sizeof seed);
   83         return 0;
   84 }
   85 
   86 static inline uint8_t *
   87 align_u64(void *tmp)
   88 {
   89         uint8_t *atmp;
   90         unsigned off;
   91 
   92         atmp = tmp;
   93         off = (uintptr_t)atmp & 7u;
   94         if (off != 0) {
   95                 atmp += 8u - off;
   96         }
   97         return atmp;
   98 }
   99 
  100 static inline uint8_t *
  101 align_u16(void *tmp)
  102 {
  103         uint8_t *atmp;
  104 
  105         atmp = tmp;
  106         if (((uintptr_t)atmp & 1u) != 0) {
  107                 atmp ++;
  108         }
  109         return atmp;
  110 }
  111 
  112 static inline fpr *
  113 align_fpr(void *tmp)
  114 {
  115         uint8_t *atmp;
  116         unsigned off;
  117 
  118         atmp = tmp;
  119         off = (uintptr_t)atmp & 7u;
  120         if (off != 0) {
  121                 atmp += 8u - off;
  122         }
  123         return (fpr *)atmp;
  124 }
  125 
  126 /* see falcon.h */
  127 int
  128 falcon_keygen_make(
  129         shake256_context *rng,
  130         unsigned logn,
  131         void *privkey, size_t privkey_len,
  132         void *pubkey, size_t pubkey_len,
  133         void *tmp, size_t tmp_len)
  134 {
  135         int8_t *f, *g, *F;
  136         uint16_t *h;
  137         uint8_t *atmp;
  138         size_t n, u, v, sk_len, pk_len;
  139         uint8_t *sk, *pk;
  140         unsigned oldcw;
  141 
  142         /*
  143          * Check parameters.
  144          */
  145         if (logn < 1 || logn > 10) {
  146                 return FALCON_ERR_BADARG;
  147         }
  148         if (privkey_len < FALCON_PRIVKEY_SIZE(logn)
  149                 || (pubkey != NULL && pubkey_len < FALCON_PUBKEY_SIZE(logn))
  150                 || tmp_len < FALCON_TMPSIZE_KEYGEN(logn))
  151         {
  152                 return FALCON_ERR_SIZE;
  153         }
  154 
  155         /*
  156          * Prepare buffers and generate private key.
  157          */
  158         n = (size_t)1 << logn;
  159         f = tmp;
  160         g = f + n;
  161         F = g + n;
  162         atmp = align_u64(F + n);
  163         oldcw = set_fpu_cw(2);
  164         Zf(keygen)((inner_shake256_context *)rng,
  165                 f, g, F, NULL, NULL, logn, atmp);
  166         set_fpu_cw(oldcw);
  167 
  168         /*
  169          * Encode private key.
  170          */
  171         sk = privkey;
  172         sk_len = FALCON_PRIVKEY_SIZE(logn);
  173         sk[0] = 0x50 + logn;
  174         u = 1;
  175         v = Zf(trim_i8_encode)(sk + u, sk_len - u,
  176                 f, logn, Zf(max_fg_bits)[logn]);
  177         if (v == 0) {
  178                 return FALCON_ERR_INTERNAL;
  179         }
  180         u += v;
  181         v = Zf(trim_i8_encode)(sk + u, sk_len - u,
  182                 g, logn, Zf(max_fg_bits)[logn]);
  183         if (v == 0) {
  184                 return FALCON_ERR_INTERNAL;
  185         }
  186         u += v;
  187         v = Zf(trim_i8_encode)(sk + u, sk_len - u,
  188                 F, logn, Zf(max_FG_bits)[logn]);
  189         if (v == 0) {
  190                 return FALCON_ERR_INTERNAL;
  191         }
  192         u += v;
  193         if (u != sk_len) {
  194                 return FALCON_ERR_INTERNAL;
  195         }
  196 
  197         /*
  198          * Recompute public key and encode it.
  199          */
  200         if (pubkey != NULL) {
  201                 h = (uint16_t *)align_u16(g + n);
  202                 atmp = (uint8_t *)(h + n);
  203                 if (!Zf(compute_public)(h, f, g, logn, atmp)) {
  204                         return FALCON_ERR_INTERNAL;
  205                 }
  206                 pk = pubkey;
  207                 pk_len = FALCON_PUBKEY_SIZE(logn);
  208                 pk[0] = 0x00 + logn;
  209                 v = Zf(modq_encode)(pk + 1, pk_len - 1, h, logn);
  210                 if (v != pk_len - 1) {
  211                         return FALCON_ERR_INTERNAL;
  212                 }
  213         }
  214 
  215         return 0;
  216 }
  217 
  218 /* see falcon.h */
  219 int
  220 falcon_make_public(
  221         void *pubkey, size_t pubkey_len,
  222         const void *privkey, size_t privkey_len,
  223         void *tmp, size_t tmp_len)
  224 {
  225         uint8_t *pk, *atmp;
  226         const uint8_t *sk;
  227         unsigned logn;
  228         size_t u, v, n, pk_len;
  229         int8_t *f, *g;
  230         uint16_t *h;
  231 
  232         /*
  233          * Get degree from private key header byte, and check
  234          * parameters.
  235          */
  236         if (privkey_len == 0) {
  237                 return FALCON_ERR_FORMAT;
  238         }
  239         sk = privkey;
  240         if ((sk[0] & 0xF0) != 0x50) {
  241                 return FALCON_ERR_FORMAT;
  242         }
  243         logn = sk[0] & 0x0F;
  244         if (logn < 1 || logn > 10) {
  245                 return FALCON_ERR_FORMAT;
  246         }
  247         if (privkey_len != FALCON_PRIVKEY_SIZE(logn)) {
  248                 return FALCON_ERR_FORMAT;
  249         }
  250         if (pubkey_len < FALCON_PUBKEY_SIZE(logn)
  251                 || tmp_len < FALCON_TMPSIZE_MAKEPUB(logn))
  252         {
  253                 return FALCON_ERR_SIZE;
  254         }
  255 
  256         /*
  257          * Decode private key (f and g).
  258          */
  259         n = (size_t)1 << logn;
  260         f = (int8_t *)tmp;
  261         g = f + n;
  262         u = 1;
  263         v = Zf(trim_i8_decode)(f, logn, Zf(max_fg_bits)[logn],
  264                 sk + u, privkey_len - u);
  265         if (v == 0) {
  266                 return FALCON_ERR_FORMAT;
  267         }
  268         u += v;
  269         v = Zf(trim_i8_decode)(g, logn, Zf(max_fg_bits)[logn],
  270                 sk + u, privkey_len - u);
  271         if (v == 0) {
  272                 return FALCON_ERR_FORMAT;
  273         }
  274 
  275         /*
  276          * Compute public key.
  277          */
  278         h = (uint16_t *)align_u16(g + n);
  279         atmp = (uint8_t *)(h + n);
  280         if (!Zf(compute_public)(h, f, g, logn, atmp)) {
  281                 return FALCON_ERR_FORMAT;
  282         }
  283 
  284         /*
  285          * Encode public key.
  286          */
  287         pk = pubkey;
  288         pk_len = FALCON_PUBKEY_SIZE(logn);
  289         pk[0] = 0x00 + logn;
  290         v = Zf(modq_encode)(pk + 1, pk_len - 1, h, logn);
  291         if (v != pk_len - 1) {
  292                 return FALCON_ERR_INTERNAL;
  293         }
  294         return 0;
  295 }
  296 
  297 /* see falcon.h */
  298 int
  299 falcon_get_logn(void *obj, size_t len)
  300 {
  301         int logn;
  302 
  303         if (len == 0) {
  304                 return FALCON_ERR_FORMAT;
  305         }
  306         logn = *(uint8_t *)obj & 0x0F;
  307         if (logn < 1 || logn > 10) {
  308                 return FALCON_ERR_FORMAT;
  309         }
  310         return logn;
  311 }
  312 
  313 /* see falcon.h */
  314 int
  315 falcon_sign_start(shake256_context *rng,
  316         void *nonce,
  317         shake256_context *hash_data)
  318 {
  319         shake256_extract(rng, nonce, 40);
  320         shake256_init(hash_data);
  321         shake256_inject(hash_data, nonce, 40);
  322         return 0;
  323 }
  324 
  325 /* see falcon.h */
  326 int
  327 falcon_sign_dyn_finish(shake256_context *rng,
  328         void *sig, size_t *sig_len, int sig_type,
  329         const void *privkey, size_t privkey_len,
  330         shake256_context *hash_data, const void *nonce,
  331         void *tmp, size_t tmp_len)
  332 {
  333         unsigned logn;
  334         const uint8_t *sk;
  335         uint8_t *es;
  336         int8_t *f, *g, *F, *G;
  337         uint16_t *hm;
  338         int16_t *sv;
  339         uint8_t *atmp;
  340         size_t u, v, n, es_len;
  341         unsigned oldcw;
  342         inner_shake256_context sav_hash_data;
  343 
  344         /*
  345          * Get degree from private key header byte, and check
  346          * parameters.
  347          */
  348         if (privkey_len == 0) {
  349                 return FALCON_ERR_FORMAT;
  350         }
  351         sk = privkey;
  352         if ((sk[0] & 0xF0) != 0x50) {
  353                 return FALCON_ERR_FORMAT;
  354         }
  355         logn = sk[0] & 0x0F;
  356         if (logn < 1 || logn > 10) {
  357                 return FALCON_ERR_FORMAT;
  358         }
  359         if (privkey_len != FALCON_PRIVKEY_SIZE(logn)) {
  360                 return FALCON_ERR_FORMAT;
  361         }
  362         if (tmp_len < FALCON_TMPSIZE_SIGNDYN(logn)) {
  363                 return FALCON_ERR_SIZE;
  364         }
  365         es_len = *sig_len;
  366         if (es_len < 41) {
  367                 return FALCON_ERR_SIZE;
  368         }
  369         switch (sig_type) {
  370         case FALCON_SIG_COMPRESSED:
  371                 break;
  372         case FALCON_SIG_PADDED:
  373                 if (*sig_len < FALCON_SIG_PADDED_SIZE(logn)) {
  374                         return FALCON_ERR_SIZE;
  375                 }
  376                 break;
  377         case FALCON_SIG_CT:
  378                 if (*sig_len < FALCON_SIG_CT_SIZE(logn)) {
  379                         return FALCON_ERR_SIZE;
  380                 }
  381                 break;
  382         default:
  383                 return FALCON_ERR_BADARG;
  384         }
  385 
  386         /*
  387          * Decode private key elements, and complete private key.
  388          */
  389         n = (size_t)1 << logn;
  390         f = (int8_t *)tmp;
  391         g = f + n;
  392         F = g + n;
  393         G = F + n;
  394         hm = (uint16_t *)(G + n);
  395         sv = (int16_t *)hm;
  396         atmp = align_u64(hm + n);
  397         u = 1;
  398         v = Zf(trim_i8_decode)(f, logn, Zf(max_fg_bits)[logn],
  399                 sk + u, privkey_len - u);
  400         if (v == 0) {
  401                 return FALCON_ERR_FORMAT;
  402         }
  403         u += v;
  404         v = Zf(trim_i8_decode)(g, logn, Zf(max_fg_bits)[logn],
  405                 sk + u, privkey_len - u);
  406         if (v == 0) {
  407                 return FALCON_ERR_FORMAT;
  408         }
  409         u += v;
  410         v = Zf(trim_i8_decode)(F, logn, Zf(max_FG_bits)[logn],
  411                 sk + u, privkey_len - u);
  412         if (v == 0) {
  413                 return FALCON_ERR_FORMAT;
  414         }
  415         u += v;
  416         if (u != privkey_len) {
  417                 return FALCON_ERR_FORMAT;
  418         }
  419         if (!Zf(complete_private)(G, f, g, F, logn, atmp)) {
  420                 return FALCON_ERR_FORMAT;
  421         }
  422 
  423         /*
  424          * Hash message to a point.
  425          */
  426         shake256_flip(hash_data);
  427         sav_hash_data = *(inner_shake256_context *)hash_data;
  428 
  429         /*
  430          * Compute and encode signature.
  431          */
  432         for (;;) {
  433                 /*
  434                  * Hash message to a point. We must redo it when looping
  435                  * (in case of a padded signature format and a failed
  436                  * attempt due to an oversized compressed signature), because
  437                  * we overwrite the hash output with the signature (in order
  438                  * to save some RAM).
  439                  */
  440                 *(inner_shake256_context *)hash_data = sav_hash_data;
  441                 if (sig_type == FALCON_SIG_CT) {
  442                         Zf(hash_to_point_ct)(
  443                                 (inner_shake256_context *)hash_data,
  444                                 hm, logn, atmp);
  445                 } else {
  446                         Zf(hash_to_point_vartime)(
  447                                 (inner_shake256_context *)hash_data,
  448                                 hm, logn);
  449                 }
  450                 oldcw = set_fpu_cw(2);
  451                 Zf(sign_dyn)(sv, (inner_shake256_context *)rng,
  452                         f, g, F, G, hm, logn, atmp);
  453                 set_fpu_cw(oldcw);
  454                 es = sig;
  455                 es_len = *sig_len;
  456                 memcpy(es + 1, nonce, 40);
  457                 u = 41;
  458                 switch (sig_type) {
  459                         size_t tu;
  460 
  461                 case FALCON_SIG_COMPRESSED:
  462                         es[0] = 0x30 + logn;
  463                         v = Zf(comp_encode)(es + u, es_len - u, sv, logn);
  464                         if (v == 0) {
  465                                 return FALCON_ERR_SIZE;
  466                         }
  467                         break;
  468                 case FALCON_SIG_PADDED:
  469                         es[0] = 0x30 + logn;
  470                         tu = FALCON_SIG_PADDED_SIZE(logn);
  471                         v = Zf(comp_encode)(es + u, tu - u, sv, logn);
  472                         if (v == 0) {
  473                                 /*
  474                                  * Signature does not fit, loop.
  475                                  */
  476                                 continue;
  477                         }
  478                         if (u + v < tu) {
  479                                 memset(es + u + v, 0, tu - (u + v));
  480                                 v = tu - u;
  481                         }
  482                         break;
  483                 case FALCON_SIG_CT:
  484                         es[0] = 0x50 + logn;
  485                         v = Zf(trim_i16_encode)(es + u, es_len - u,
  486                                 sv, logn, Zf(max_sig_bits)[logn]);
  487                         if (v == 0) {
  488                                 return FALCON_ERR_SIZE;
  489                         }
  490                         break;
  491                 }
  492                 *sig_len = u + v;
  493                 return 0;
  494         }
  495 }
  496 
  497 /* see falcon.h */
  498 int
  499 falcon_expand_privkey(void *expanded_key, size_t expanded_key_len,
  500         const void *privkey, size_t privkey_len,
  501         void *tmp, size_t tmp_len)
  502 {
  503         unsigned logn;
  504         const uint8_t *sk;
  505         int8_t *f, *g, *F, *G;
  506         uint8_t *atmp;
  507         size_t u, v, n;
  508         fpr *expkey;
  509         unsigned oldcw;
  510 
  511         /*
  512          * Get degree from private key header byte, and check
  513          * parameters.
  514          */
  515         if (privkey_len == 0) {
  516                 return FALCON_ERR_FORMAT;
  517         }
  518         sk = privkey;
  519         if ((sk[0] & 0xF0) != 0x50) {
  520                 return FALCON_ERR_FORMAT;
  521         }
  522         logn = sk[0] & 0x0F;
  523         if (logn < 1 || logn > 10) {
  524                 return FALCON_ERR_FORMAT;
  525         }
  526         if (privkey_len != FALCON_PRIVKEY_SIZE(logn)) {
  527                 return FALCON_ERR_FORMAT;
  528         }
  529         if (expanded_key_len < FALCON_EXPANDEDKEY_SIZE(logn)
  530                 || tmp_len < FALCON_TMPSIZE_EXPANDPRIV(logn))
  531         {
  532                 return FALCON_ERR_SIZE;
  533         }
  534 
  535         /*
  536          * Decode private key elements, and complete private key.
  537          */
  538         n = (size_t)1 << logn;
  539         f = (int8_t *)tmp;
  540         g = f + n;
  541         F = g + n;
  542         G = F + n;
  543         atmp = align_u64(G + n);
  544         u = 1;
  545         v = Zf(trim_i8_decode)(f, logn, Zf(max_fg_bits)[logn],
  546                 sk + u, privkey_len - u);
  547         if (v == 0) {
  548                 return FALCON_ERR_FORMAT;
  549         }
  550         u += v;
  551         v = Zf(trim_i8_decode)(g, logn, Zf(max_fg_bits)[logn],
  552                 sk + u, privkey_len - u);
  553         if (v == 0) {
  554                 return FALCON_ERR_FORMAT;
  555         }
  556         u += v;
  557         v = Zf(trim_i8_decode)(F, logn, Zf(max_FG_bits)[logn],
  558                 sk + u, privkey_len - u);
  559         if (v == 0) {
  560                 return FALCON_ERR_FORMAT;
  561         }
  562         u += v;
  563         if (u != privkey_len) {
  564                 return FALCON_ERR_FORMAT;
  565         }
  566         if (!Zf(complete_private)(G, f, g, F, logn, atmp)) {
  567                 return FALCON_ERR_FORMAT;
  568         }
  569 
  570         /*
  571          * Expand private key.
  572          */
  573         *(uint8_t *)expanded_key = logn;
  574         expkey = align_fpr((uint8_t *)expanded_key + 1);
  575         oldcw = set_fpu_cw(2);
  576         Zf(expand_privkey)(expkey, f, g, F, G, logn, atmp);
  577         set_fpu_cw(oldcw);
  578         return 0;
  579 }
  580 
  581 /* see falcon.h */
  582 int
  583 falcon_sign_tree_finish(shake256_context *rng,
  584         void *sig, size_t *sig_len, int sig_type,
  585         const void *expanded_key,
  586         shake256_context *hash_data, const void *nonce,
  587         void *tmp, size_t tmp_len)
  588 {
  589         unsigned logn;
  590         uint8_t *es;
  591         const fpr *expkey;
  592         uint16_t *hm;
  593         int16_t *sv;
  594         uint8_t *atmp;
  595         size_t u, v, n, es_len;
  596         unsigned oldcw;
  597         inner_shake256_context sav_hash_data;
  598 
  599         /*
  600          * Get degree from private key header byte, and check
  601          * parameters.
  602          */
  603         logn = *(const uint8_t *)expanded_key;
  604         if (logn < 1 || logn > 10) {
  605                 return FALCON_ERR_FORMAT;
  606         }
  607         if (tmp_len < FALCON_TMPSIZE_SIGNTREE(logn)) {
  608                 return FALCON_ERR_SIZE;
  609         }
  610         es_len = *sig_len;
  611         if (es_len < 41) {
  612                 return FALCON_ERR_SIZE;
  613         }
  614         expkey = (const fpr *)align_fpr((uint8_t *)expanded_key + 1);
  615         switch (sig_type) {
  616         case FALCON_SIG_COMPRESSED:
  617                 break;
  618         case FALCON_SIG_PADDED:
  619                 if (*sig_len < FALCON_SIG_PADDED_SIZE(logn)) {
  620                         return FALCON_ERR_SIZE;
  621                 }
  622                 break;
  623         case FALCON_SIG_CT:
  624                 if (*sig_len < FALCON_SIG_CT_SIZE(logn)) {
  625                         return FALCON_ERR_SIZE;
  626                 }
  627                 break;
  628         default:
  629                 return FALCON_ERR_BADARG;
  630         }
  631 
  632         n = (size_t)1 << logn;
  633         hm = (uint16_t *)align_u16(tmp);
  634         sv = (int16_t *)hm;
  635         atmp = align_u64(sv + n);
  636 
  637         /*
  638          * Hash message to a point.
  639          */
  640         shake256_flip(hash_data);
  641         sav_hash_data = *(inner_shake256_context *)hash_data;
  642 
  643         /*
  644          * Compute and encode signature.
  645          */
  646         for (;;) {
  647                 /*
  648                  * Hash message to a point. We must redo it when looping
  649                  * (in case of a padded signature format and a failed
  650                  * attempt due to an oversized compressed signature), because
  651                  * we overwrite the hash output with the signature (in order
  652                  * to save some RAM).
  653                  */
  654                 *(inner_shake256_context *)hash_data = sav_hash_data;
  655                 if (sig_type == FALCON_SIG_CT) {
  656                         Zf(hash_to_point_ct)(
  657                                 (inner_shake256_context *)hash_data,
  658                                 hm, logn, atmp);
  659                 } else {
  660                         Zf(hash_to_point_vartime)(
  661                                 (inner_shake256_context *)hash_data,
  662                                 hm, logn);
  663                 }
  664                 oldcw = set_fpu_cw(2);
  665                 Zf(sign_tree)(sv, (inner_shake256_context *)rng,
  666                         expkey, hm, logn, atmp);
  667                 set_fpu_cw(oldcw);
  668                 es = sig;
  669                 es_len = *sig_len;
  670                 memcpy(es + 1, nonce, 40);
  671                 u = 41;
  672                 switch (sig_type) {
  673                         size_t tu;
  674 
  675                 case FALCON_SIG_COMPRESSED:
  676                         es[0] = 0x30 + logn;
  677                         v = Zf(comp_encode)(es + u, es_len - u, sv, logn);
  678                         if (v == 0) {
  679                                 return FALCON_ERR_SIZE;
  680                         }
  681                         break;
  682                 case FALCON_SIG_PADDED:
  683                         es[0] = 0x30 + logn;
  684                         tu = FALCON_SIG_PADDED_SIZE(logn);
  685                         v = Zf(comp_encode)(es + u, tu - u, sv, logn);
  686                         if (v == 0) {
  687                                 /*
  688                                  * Signature does not fit, loop.
  689                                  */
  690                                 continue;
  691                         }
  692                         if (u + v < tu) {
  693                                 memset(es + u + v, 0, tu - (u + v));
  694                                 v = tu - u;
  695                         }
  696                         break;
  697                 case FALCON_SIG_CT:
  698                         es[0] = 0x50 + logn;
  699                         v = Zf(trim_i16_encode)(es + u, es_len - u,
  700                                 sv, logn, Zf(max_sig_bits)[logn]);
  701                         if (v == 0) {
  702                                 return FALCON_ERR_SIZE;
  703                         }
  704                         break;
  705                 }
  706                 *sig_len = u + v;
  707                 return 0;
  708         }
  709 }
  710 
  711 /* see falcon.h */
  712 int
  713 falcon_sign_dyn(shake256_context *rng,
  714         void *sig, size_t *sig_len, int sig_type,
  715         const void *privkey, size_t privkey_len,
  716         const void *data, size_t data_len,
  717         void *tmp, size_t tmp_len)
  718 {
  719         shake256_context hd;
  720         uint8_t nonce[40];
  721         int r;
  722 
  723         r = falcon_sign_start(rng, nonce, &hd);
  724         if (r != 0) {
  725                 return r;
  726         }
  727         shake256_inject(&hd, data, data_len);
  728         return falcon_sign_dyn_finish(rng, sig, sig_len, sig_type,
  729                 privkey, privkey_len, &hd, nonce, tmp, tmp_len);
  730 }
  731 
  732 /* see falcon.h */
  733 int
  734 falcon_sign_tree(shake256_context *rng,
  735         void *sig, size_t *sig_len, int sig_type,
  736         const void *expanded_key,
  737         const void *data, size_t data_len,
  738         void *tmp, size_t tmp_len)
  739 {
  740         shake256_context hd;
  741         uint8_t nonce[40];
  742         int r;
  743 
  744         r = falcon_sign_start(rng, nonce, &hd);
  745         if (r != 0) {
  746                 return r;
  747         }
  748         shake256_inject(&hd, data, data_len);
  749         return falcon_sign_tree_finish(rng, sig, sig_len, sig_type,
  750                 expanded_key, &hd, nonce, tmp, tmp_len);
  751 }
  752 
  753 /* see falcon.h */
  754 int
  755 falcon_verify_start(shake256_context *hash_data,
  756         const void *sig, size_t sig_len)
  757 {
  758         if (sig_len < 41) {
  759                 return FALCON_ERR_FORMAT;
  760         }
  761         shake256_init(hash_data);
  762         shake256_inject(hash_data, (const uint8_t *)sig + 1, 40);
  763         return 0;
  764 }
  765 
  766 /* see falcon.h */
  767 int
  768 falcon_verify_finish(const void *sig, size_t sig_len, int sig_type,
  769         const void *pubkey, size_t pubkey_len,
  770         shake256_context *hash_data,
  771         void *tmp, size_t tmp_len)
  772 {
  773         unsigned logn;
  774         uint8_t *atmp;
  775         const uint8_t *pk, *es;
  776         size_t u, v, n;
  777         uint16_t *h, *hm;
  778         int16_t *sv;
  779         int ct;
  780 
  781         /*
  782          * Get Falcon degree from public key; verify consistency with
  783          * signature value, and check parameters.
  784          */
  785         if (sig_len < 41 || pubkey_len == 0) {
  786                 return FALCON_ERR_FORMAT;
  787         }
  788         es = sig;
  789         pk = pubkey;
  790         if ((pk[0] & 0xF0) != 0x00) {
  791                 return FALCON_ERR_FORMAT;
  792         }
  793         logn = pk[0] & 0x0F;
  794         if (logn < 1 || logn > 10) {
  795                 return FALCON_ERR_FORMAT;
  796         }
  797         if ((es[0] & 0x0F) != logn) {
  798                 return FALCON_ERR_BADSIG;
  799         }
  800         ct = 0;
  801         switch (sig_type) {
  802         case 0:
  803                 switch (es[0] & 0xF0) {
  804                 case 0x30:
  805                         break;
  806                 case 0x50:
  807                         if (sig_len != FALCON_SIG_CT_SIZE(logn)) {
  808                                 return FALCON_ERR_FORMAT;
  809                         }
  810                         ct = 1;
  811                         break;
  812                 default:
  813                         return FALCON_ERR_BADSIG;
  814                 }
  815                 break;
  816         case FALCON_SIG_COMPRESSED:
  817                 if ((es[0] & 0xF0) != 0x30) {
  818                         return FALCON_ERR_FORMAT;
  819                 }
  820                 break;
  821         case FALCON_SIG_PADDED:
  822                 if ((es[0] & 0xF0) != 0x30) {
  823                         return FALCON_ERR_FORMAT;
  824                 }
  825                 if (sig_len != FALCON_SIG_PADDED_SIZE(logn)) {
  826                         return FALCON_ERR_FORMAT;
  827                 }
  828                 break;
  829         case FALCON_SIG_CT:
  830                 if ((es[0] & 0xF0) != 0x50) {
  831                         return FALCON_ERR_FORMAT;
  832                 }
  833                 if (sig_len != FALCON_SIG_CT_SIZE(logn)) {
  834                         return FALCON_ERR_FORMAT;
  835                 }
  836                 ct = 1;
  837                 break;
  838         default:
  839                 return FALCON_ERR_BADARG;
  840         }
  841         if (pubkey_len != FALCON_PUBKEY_SIZE(logn)) {
  842                 return FALCON_ERR_FORMAT;
  843         }
  844         if (tmp_len < FALCON_TMPSIZE_VERIFY(logn)) {
  845                 return FALCON_ERR_SIZE;
  846         }
  847 
  848         n = (size_t)1 << logn;
  849         h = (uint16_t *)align_u16(tmp);
  850         hm = h + n;
  851         sv = (int16_t *)(hm + n);
  852         atmp = (uint8_t *)(sv + n);
  853 
  854         /*
  855          * Decode public key.
  856          */
  857         if (Zf(modq_decode)(h, logn, pk + 1, pubkey_len - 1)
  858                 != pubkey_len - 1)
  859         {
  860                 return FALCON_ERR_FORMAT;
  861         }
  862 
  863         /*
  864          * Decode signature value.
  865          */
  866         u = 41;
  867         if (ct) {
  868                 v = Zf(trim_i16_decode)(sv, logn,
  869                         Zf(max_sig_bits)[logn], es + u, sig_len - u);
  870         } else {
  871                 v = Zf(comp_decode)(sv, logn, es + u, sig_len - u);
  872         }
  873         if (v == 0) {
  874                 return FALCON_ERR_FORMAT;
  875         }
  876         if ((u + v) != sig_len) {
  877                 /*
  878                  * Extra bytes of value 0 are tolerated only for the
  879                  * "padded" format.
  880                  */
  881                 if ((sig_type == 0 && sig_len == FALCON_SIG_PADDED_SIZE(logn))
  882                         || sig_type == FALCON_SIG_PADDED)
  883                 {
  884                         while (u + v < sig_len) {
  885                                 if (es[u + v] != 0) {
  886                                         return FALCON_ERR_FORMAT;
  887                                 }
  888                                 v ++;
  889                         }
  890                 } else {
  891                         return FALCON_ERR_FORMAT;
  892                 }
  893         }
  894 
  895         /*
  896          * Hash message to point.
  897          */
  898         shake256_flip(hash_data);
  899         if (ct) {
  900                 Zf(hash_to_point_ct)(
  901                         (inner_shake256_context *)hash_data, hm, logn, atmp);
  902         } else {
  903                 Zf(hash_to_point_vartime)(
  904                         (inner_shake256_context *)hash_data, hm, logn);
  905         }
  906 
  907         /*
  908          * Verify signature.
  909          */
  910         Zf(to_ntt_monty)(h, logn);
  911         if (!Zf(verify_raw)(hm, sv, h, logn, atmp)) {
  912                 return FALCON_ERR_BADSIG;
  913         }
  914         return 0;
  915 }
  916 
  917 /* see falcon.h */
  918 int
  919 falcon_verify(const void *sig, size_t sig_len, int sig_type,
  920         const void *pubkey, size_t pubkey_len,
  921         const void *data, size_t data_len,
  922         void *tmp, size_t tmp_len)
  923 {
  924         shake256_context hd;
  925         int r;
  926 
  927         r = falcon_verify_start(&hd, sig, sig_len);
  928         if (r < 0) {
  929                 return r;
  930         }
  931         shake256_inject(&hd, data, data_len);
  932         return falcon_verify_finish(sig, sig_len, sig_type,
  933                 pubkey, pubkey_len, &hd, tmp, tmp_len);
  934 }