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,
  329         const void *privkey, size_t privkey_len,
  330         shake256_context *hash_data, const void *nonce,
  331         int ct, 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 
  343         /*
  344          * Get degree from private key header byte, and check
  345          * parameters.
  346          */
  347         if (privkey_len == 0) {
  348                 return FALCON_ERR_FORMAT;
  349         }
  350         sk = privkey;
  351         if ((sk[0] & 0xF0) != 0x50) {
  352                 return FALCON_ERR_FORMAT;
  353         }
  354         logn = sk[0] & 0x0F;
  355         if (logn < 1 || logn > 10) {
  356                 return FALCON_ERR_FORMAT;
  357         }
  358         if (privkey_len != FALCON_PRIVKEY_SIZE(logn)) {
  359                 return FALCON_ERR_FORMAT;
  360         }
  361         if (tmp_len < FALCON_TMPSIZE_SIGNDYN(logn)) {
  362                 return FALCON_ERR_SIZE;
  363         }
  364         es_len = *sig_len;
  365         if (es_len < 41) {
  366                 return FALCON_ERR_SIZE;
  367         }
  368 
  369         /*
  370          * Decode private key elements, and complete private key.
  371          */
  372         n = (size_t)1 << logn;
  373         f = (int8_t *)tmp;
  374         g = f + n;
  375         F = g + n;
  376         G = F + n;
  377         hm = (uint16_t *)(G + n);
  378         sv = (int16_t *)hm;
  379         atmp = align_u64(hm + n);
  380         u = 1;
  381         v = Zf(trim_i8_decode)(f, logn, Zf(max_fg_bits)[logn],
  382                 sk + u, privkey_len - u);
  383         if (v == 0) {
  384                 return FALCON_ERR_FORMAT;
  385         }
  386         u += v;
  387         v = Zf(trim_i8_decode)(g, logn, Zf(max_fg_bits)[logn],
  388                 sk + u, privkey_len - u);
  389         if (v == 0) {
  390                 return FALCON_ERR_FORMAT;
  391         }
  392         u += v;
  393         v = Zf(trim_i8_decode)(F, logn, Zf(max_FG_bits)[logn],
  394                 sk + u, privkey_len - u);
  395         if (v == 0) {
  396                 return FALCON_ERR_FORMAT;
  397         }
  398         u += v;
  399         if (u != privkey_len) {
  400                 return FALCON_ERR_FORMAT;
  401         }
  402         if (!Zf(complete_private)(G, f, g, F, logn, atmp)) {
  403                 return FALCON_ERR_FORMAT;
  404         }
  405 
  406         /*
  407          * Hash message to a point.
  408          */
  409         shake256_flip(hash_data);
  410         if (ct) {
  411                 Zf(hash_to_point_ct)(
  412                         (inner_shake256_context *)hash_data, hm, logn, atmp);
  413         } else {
  414                 Zf(hash_to_point_vartime)(
  415                         (inner_shake256_context *)hash_data, hm, logn);
  416         }
  417 
  418         /*
  419          * Compute and encode signature.
  420          */
  421         oldcw = set_fpu_cw(2);
  422         Zf(sign_dyn)(sv, (inner_shake256_context *)rng,
  423                 f, g, F, G, hm, logn, atmp);
  424         set_fpu_cw(oldcw);
  425         es = sig;
  426         es_len = *sig_len;
  427         memcpy(es + 1, nonce, 40);
  428         u = 41;
  429         if (ct) {
  430                 es[0] = 0x50 + logn;
  431                 v = Zf(trim_i16_encode)(es + u, es_len - u,
  432                         sv, logn, Zf(max_sig_bits)[logn]);
  433         } else {
  434                 es[0] = 0x30 + logn;
  435                 v = Zf(comp_encode)(es + u, es_len - u, sv, logn);
  436         }
  437         if (v == 0) {
  438                 return FALCON_ERR_SIZE;
  439         }
  440         *sig_len = u + v;
  441         return 0;
  442 }
  443 
  444 /* see falcon.h */
  445 int
  446 falcon_expand_privkey(void *expanded_key, size_t expanded_key_len,
  447         const void *privkey, size_t privkey_len,
  448         void *tmp, size_t tmp_len)
  449 {
  450         unsigned logn;
  451         const uint8_t *sk;
  452         int8_t *f, *g, *F, *G;
  453         uint8_t *atmp;
  454         size_t u, v, n;
  455         fpr *expkey;
  456         unsigned oldcw;
  457 
  458         /*
  459          * Get degree from private key header byte, and check
  460          * parameters.
  461          */
  462         if (privkey_len == 0) {
  463                 return FALCON_ERR_FORMAT;
  464         }
  465         sk = privkey;
  466         if ((sk[0] & 0xF0) != 0x50) {
  467                 return FALCON_ERR_FORMAT;
  468         }
  469         logn = sk[0] & 0x0F;
  470         if (logn < 1 || logn > 10) {
  471                 return FALCON_ERR_FORMAT;
  472         }
  473         if (privkey_len != FALCON_PRIVKEY_SIZE(logn)) {
  474                 return FALCON_ERR_FORMAT;
  475         }
  476         if (expanded_key_len < FALCON_EXPANDEDKEY_SIZE(logn)
  477                 || tmp_len < FALCON_TMPSIZE_EXPANDPRIV(logn))
  478         {
  479                 return FALCON_ERR_SIZE;
  480         }
  481 
  482         /*
  483          * Decode private key elements, and complete private key.
  484          */
  485         n = (size_t)1 << logn;
  486         f = (int8_t *)tmp;
  487         g = f + n;
  488         F = g + n;
  489         G = F + n;
  490         atmp = align_u64(G + n);
  491         u = 1;
  492         v = Zf(trim_i8_decode)(f, logn, Zf(max_fg_bits)[logn],
  493                 sk + u, privkey_len - u);
  494         if (v == 0) {
  495                 return FALCON_ERR_FORMAT;
  496         }
  497         u += v;
  498         v = Zf(trim_i8_decode)(g, logn, Zf(max_fg_bits)[logn],
  499                 sk + u, privkey_len - u);
  500         if (v == 0) {
  501                 return FALCON_ERR_FORMAT;
  502         }
  503         u += v;
  504         v = Zf(trim_i8_decode)(F, logn, Zf(max_FG_bits)[logn],
  505                 sk + u, privkey_len - u);
  506         if (v == 0) {
  507                 return FALCON_ERR_FORMAT;
  508         }
  509         u += v;
  510         if (u != privkey_len) {
  511                 return FALCON_ERR_FORMAT;
  512         }
  513         if (!Zf(complete_private)(G, f, g, F, logn, atmp)) {
  514                 return FALCON_ERR_FORMAT;
  515         }
  516 
  517         /*
  518          * Expand private key.
  519          */
  520         *(uint8_t *)expanded_key = logn;
  521         expkey = align_fpr((uint8_t *)expanded_key + 1);
  522         oldcw = set_fpu_cw(2);
  523         Zf(expand_privkey)(expkey, f, g, F, G, logn, atmp);
  524         set_fpu_cw(oldcw);
  525         return 0;
  526 }
  527 
  528 /* see falcon.h */
  529 int
  530 falcon_sign_tree_finish(shake256_context *rng,
  531         void *sig, size_t *sig_len,
  532         const void *expanded_key,
  533         shake256_context *hash_data, const void *nonce,
  534         int ct, void *tmp, size_t tmp_len)
  535 {
  536         unsigned logn;
  537         uint8_t *es;
  538         const fpr *expkey;
  539         uint16_t *hm;
  540         int16_t *sv;
  541         uint8_t *atmp;
  542         size_t u, v, n, es_len;
  543         unsigned oldcw;
  544 
  545         /*
  546          * Get degree from private key header byte, and check
  547          * parameters.
  548          */
  549         logn = *(const uint8_t *)expanded_key;
  550         if (logn < 1 || logn > 10) {
  551                 return FALCON_ERR_FORMAT;
  552         }
  553         if (tmp_len < FALCON_TMPSIZE_SIGNTREE(logn)) {
  554                 return FALCON_ERR_SIZE;
  555         }
  556         es_len = *sig_len;
  557         if (es_len < 41) {
  558                 return FALCON_ERR_SIZE;
  559         }
  560         expkey = (const fpr *)align_fpr((uint8_t *)expanded_key + 1);
  561 
  562         n = (size_t)1 << logn;
  563         hm = (uint16_t *)align_u16(tmp);
  564         sv = (int16_t *)hm;
  565         atmp = align_u64(sv + n);
  566 
  567         /*
  568          * Hash message to a point.
  569          */
  570         shake256_flip(hash_data);
  571         if (ct) {
  572                 Zf(hash_to_point_ct)(
  573                         (inner_shake256_context *)hash_data, hm, logn, atmp);
  574         } else {
  575                 Zf(hash_to_point_vartime)(
  576                         (inner_shake256_context *)hash_data, hm, logn);
  577         }
  578 
  579         /*
  580          * Compute and encode signature.
  581          */
  582         oldcw = set_fpu_cw(2);
  583         Zf(sign_tree)(sv, (inner_shake256_context *)rng,
  584                 expkey, hm, logn, atmp);
  585         set_fpu_cw(oldcw);
  586         es = sig;
  587         es_len = *sig_len;
  588         memcpy(es + 1, nonce, 40);
  589         u = 41;
  590         if (ct) {
  591                 es[0] = 0x50 + logn;
  592                 v = Zf(trim_i16_encode)(es + u, es_len - u,
  593                         sv, logn, Zf(max_sig_bits)[logn]);
  594         } else {
  595                 es[0] = 0x30 + logn;
  596                 v = Zf(comp_encode)(es + u, es_len - u, sv, logn);
  597         }
  598         if (v == 0) {
  599                 return FALCON_ERR_SIZE;
  600         }
  601         *sig_len = u + v;
  602         return 0;
  603 }
  604 
  605 /* see falcon.h */
  606 int
  607 falcon_sign_dyn(shake256_context *rng,
  608         void *sig, size_t *sig_len,
  609         const void *privkey, size_t privkey_len,
  610         const void *data, size_t data_len,
  611         int ct, void *tmp, size_t tmp_len)
  612 {
  613         shake256_context hd;
  614         uint8_t nonce[40];
  615         int r;
  616 
  617         r = falcon_sign_start(rng, nonce, &hd);
  618         if (r != 0) {
  619                 return r;
  620         }
  621         shake256_inject(&hd, data, data_len);
  622         return falcon_sign_dyn_finish(rng, sig, sig_len,
  623                 privkey, privkey_len, &hd, nonce, ct, tmp, tmp_len);
  624 }
  625 
  626 /* see falcon.h */
  627 int
  628 falcon_sign_tree(shake256_context *rng,
  629         void *sig, size_t *sig_len,
  630         const void *expanded_key,
  631         const void *data, size_t data_len,
  632         int ct, void *tmp, size_t tmp_len)
  633 {
  634         shake256_context hd;
  635         uint8_t nonce[40];
  636         int r;
  637 
  638         r = falcon_sign_start(rng, nonce, &hd);
  639         if (r != 0) {
  640                 return r;
  641         }
  642         shake256_inject(&hd, data, data_len);
  643         return falcon_sign_tree_finish(rng, sig, sig_len,
  644                 expanded_key, &hd, nonce, ct, tmp, tmp_len);
  645 }
  646 
  647 /* see falcon.h */
  648 int
  649 falcon_verify_start(shake256_context *hash_data,
  650         const void *sig, size_t sig_len)
  651 {
  652         if (sig_len < 41) {
  653                 return FALCON_ERR_FORMAT;
  654         }
  655         shake256_init(hash_data);
  656         shake256_inject(hash_data, (const uint8_t *)sig + 1, 40);
  657         return 0;
  658 }
  659 
  660 /* see falcon.h */
  661 int
  662 falcon_verify_finish(const void *sig, size_t sig_len,
  663         const void *pubkey, size_t pubkey_len,
  664         shake256_context *hash_data,
  665         void *tmp, size_t tmp_len)
  666 {
  667         unsigned logn;
  668         uint8_t *atmp;
  669         const uint8_t *pk, *es;
  670         int ct;
  671         size_t u, v, n;
  672         uint16_t *h, *hm;
  673         int16_t *sv;
  674 
  675         /*
  676          * Get Falcon degree from public key; verify consistency with
  677          * signature value, and check parameters.
  678          */
  679         if (sig_len < 41 || pubkey_len == 0) {
  680                 return FALCON_ERR_FORMAT;
  681         }
  682         es = sig;
  683         pk = pubkey;
  684         if ((pk[0] & 0xF0) != 0x00) {
  685                 return FALCON_ERR_FORMAT;
  686         }
  687         logn = pk[0] & 0x0F;
  688         if (logn < 1 || logn > 10) {
  689                 return FALCON_ERR_FORMAT;
  690         }
  691         switch (es[0] & 0xF0) {
  692         case 0x30:
  693                 ct = 0;
  694                 break;
  695         case 0x50:
  696                 ct = 1;
  697                 break;
  698         default:
  699                 return FALCON_ERR_FORMAT;
  700         }
  701         if ((es[0] & 0x0F) != logn) {
  702                 return FALCON_ERR_BADSIG;
  703         }
  704         if (pubkey_len != FALCON_PUBKEY_SIZE(logn)) {
  705                 return FALCON_ERR_FORMAT;
  706         }
  707         if (tmp_len < FALCON_TMPSIZE_VERIFY(logn)) {
  708                 return FALCON_ERR_SIZE;
  709         }
  710 
  711         n = (size_t)1 << logn;
  712         h = (uint16_t *)align_u16(tmp);
  713         hm = h + n;
  714         sv = (int16_t *)(hm + n);
  715         atmp = (uint8_t *)(sv + n);
  716 
  717         /*
  718          * Decode public key.
  719          */
  720         if (Zf(modq_decode)(h, logn, pk + 1, pubkey_len - 1)
  721                 != pubkey_len - 1)
  722         {
  723                 return FALCON_ERR_FORMAT;
  724         }
  725 
  726         /*
  727          * Decode signature value.
  728          */
  729         u = 41;
  730         if (ct) {
  731                 v = Zf(trim_i16_decode)(sv, logn,
  732                         Zf(max_sig_bits)[logn], es + u, sig_len - u);
  733         } else {
  734                 v = Zf(comp_decode)(sv, logn, es + u, sig_len - u);
  735         }
  736         if (v == 0 || (u + v) != sig_len) {
  737                 return FALCON_ERR_FORMAT;
  738         }
  739 
  740         /*
  741          * Hash message to point.
  742          */
  743         shake256_flip(hash_data);
  744         if (ct) {
  745                 Zf(hash_to_point_ct)(
  746                         (inner_shake256_context *)hash_data, hm, logn, atmp);
  747         } else {
  748                 Zf(hash_to_point_vartime)(
  749                         (inner_shake256_context *)hash_data, hm, logn);
  750         }
  751 
  752         /*
  753          * Verify signature.
  754          */
  755         Zf(to_ntt_monty)(h, logn);
  756         if (!Zf(verify_raw)(hm, sv, h, logn, atmp)) {
  757                 return FALCON_ERR_BADSIG;
  758         }
  759         return 0;
  760 }
  761 
  762 /* see falcon.h */
  763 int
  764 falcon_verify(const void *sig, size_t sig_len,
  765         const void *pubkey, size_t pubkey_len,
  766         const void *data, size_t data_len,
  767         void *tmp, size_t tmp_len)
  768 {
  769         shake256_context hd;
  770         int r;
  771 
  772         r = falcon_verify_start(&hd, sig, sig_len);
  773         if (r < 0) {
  774                 return r;
  775         }
  776         shake256_inject(&hd, data, data_len);
  777         return falcon_verify_finish(sig, sig_len,
  778                 pubkey, pubkey_len, &hd, tmp, tmp_len);
  779 }