diff options
Diffstat (limited to 'lib/liboqs/src/sig/falcon/pqclean_falcon-1024_clean/codec.c')
| -rw-r--r-- | lib/liboqs/src/sig/falcon/pqclean_falcon-1024_clean/codec.c | 555 |
1 files changed, 0 insertions, 555 deletions
diff --git a/lib/liboqs/src/sig/falcon/pqclean_falcon-1024_clean/codec.c b/lib/liboqs/src/sig/falcon/pqclean_falcon-1024_clean/codec.c deleted file mode 100644 index c5ab4938b..000000000 --- a/lib/liboqs/src/sig/falcon/pqclean_falcon-1024_clean/codec.c +++ /dev/null @@ -1,555 +0,0 @@ -#include "inner.h" - -/* - * Encoding/decoding of keys and signatures. - * - * ==========================(LICENSE BEGIN)============================ - * - * Copyright (c) 2017-2019 Falcon Project - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. - * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY - * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, - * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE - * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - * - * ===========================(LICENSE END)============================= - * - * @author Thomas Pornin <thomas.pornin@nccgroup.com> - */ - - -/* see inner.h */ -size_t -PQCLEAN_FALCON1024_CLEAN_modq_encode( - void *out, size_t max_out_len, - const uint16_t *x, unsigned logn) { - size_t n, out_len, u; - uint8_t *buf; - uint32_t acc; - int acc_len; - - n = (size_t)1 << logn; - for (u = 0; u < n; u ++) { - if (x[u] >= 12289) { - return 0; - } - } - out_len = ((n * 14) + 7) >> 3; - if (out == NULL) { - return out_len; - } - if (out_len > max_out_len) { - return 0; - } - buf = out; - acc = 0; - acc_len = 0; - for (u = 0; u < n; u ++) { - acc = (acc << 14) | x[u]; - acc_len += 14; - while (acc_len >= 8) { - acc_len -= 8; - *buf ++ = (uint8_t)(acc >> acc_len); - } - } - if (acc_len > 0) { - *buf = (uint8_t)(acc << (8 - acc_len)); - } - return out_len; -} - -/* see inner.h */ -size_t -PQCLEAN_FALCON1024_CLEAN_modq_decode( - uint16_t *x, unsigned logn, - const void *in, size_t max_in_len) { - size_t n, in_len, u; - const uint8_t *buf; - uint32_t acc; - int acc_len; - - n = (size_t)1 << logn; - in_len = ((n * 14) + 7) >> 3; - if (in_len > max_in_len) { - return 0; - } - buf = in; - acc = 0; - acc_len = 0; - u = 0; - while (u < n) { - acc = (acc << 8) | (*buf ++); - acc_len += 8; - if (acc_len >= 14) { - unsigned w; - - acc_len -= 14; - w = (acc >> acc_len) & 0x3FFF; - if (w >= 12289) { - return 0; - } - x[u ++] = (uint16_t)w; - } - } - if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) { - return 0; - } - return in_len; -} - -/* see inner.h */ -size_t -PQCLEAN_FALCON1024_CLEAN_trim_i16_encode( - void *out, size_t max_out_len, - const int16_t *x, unsigned logn, unsigned bits) { - size_t n, u, out_len; - int minv, maxv; - uint8_t *buf; - uint32_t acc, mask; - unsigned acc_len; - - n = (size_t)1 << logn; - maxv = (1 << (bits - 1)) - 1; - minv = -maxv; - for (u = 0; u < n; u ++) { - if (x[u] < minv || x[u] > maxv) { - return 0; - } - } - out_len = ((n * bits) + 7) >> 3; - if (out == NULL) { - return out_len; - } - if (out_len > max_out_len) { - return 0; - } - buf = out; - acc = 0; - acc_len = 0; - mask = ((uint32_t)1 << bits) - 1; - for (u = 0; u < n; u ++) { - acc = (acc << bits) | ((uint16_t)x[u] & mask); - acc_len += bits; - while (acc_len >= 8) { - acc_len -= 8; - *buf ++ = (uint8_t)(acc >> acc_len); - } - } - if (acc_len > 0) { - *buf ++ = (uint8_t)(acc << (8 - acc_len)); - } - return out_len; -} - -/* see inner.h */ -size_t -PQCLEAN_FALCON1024_CLEAN_trim_i16_decode( - int16_t *x, unsigned logn, unsigned bits, - const void *in, size_t max_in_len) { - size_t n, in_len; - const uint8_t *buf; - size_t u; - uint32_t acc, mask1, mask2; - unsigned acc_len; - - n = (size_t)1 << logn; - in_len = ((n * bits) + 7) >> 3; - if (in_len > max_in_len) { - return 0; - } - buf = in; - u = 0; - acc = 0; - acc_len = 0; - mask1 = ((uint32_t)1 << bits) - 1; - mask2 = (uint32_t)1 << (bits - 1); - while (u < n) { - acc = (acc << 8) | *buf ++; - acc_len += 8; - while (acc_len >= bits && u < n) { - uint32_t w; - - acc_len -= bits; - w = (acc >> acc_len) & mask1; - w |= -(w & mask2); - if (w == -mask2) { - /* - * The -2^(bits-1) value is forbidden. - */ - return 0; - } - w |= -(w & mask2); - x[u ++] = (int16_t) * (int32_t *)&w; - } - } - if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) { - /* - * Extra bits in the last byte must be zero. - */ - return 0; - } - return in_len; -} - -/* see inner.h */ -size_t -PQCLEAN_FALCON1024_CLEAN_trim_i8_encode( - void *out, size_t max_out_len, - const int8_t *x, unsigned logn, unsigned bits) { - size_t n, u, out_len; - int minv, maxv; - uint8_t *buf; - uint32_t acc, mask; - unsigned acc_len; - - n = (size_t)1 << logn; - maxv = (1 << (bits - 1)) - 1; - minv = -maxv; - for (u = 0; u < n; u ++) { - if (x[u] < minv || x[u] > maxv) { - return 0; - } - } - out_len = ((n * bits) + 7) >> 3; - if (out == NULL) { - return out_len; - } - if (out_len > max_out_len) { - return 0; - } - buf = out; - acc = 0; - acc_len = 0; - mask = ((uint32_t)1 << bits) - 1; - for (u = 0; u < n; u ++) { - acc = (acc << bits) | ((uint8_t)x[u] & mask); - acc_len += bits; - while (acc_len >= 8) { - acc_len -= 8; - *buf ++ = (uint8_t)(acc >> acc_len); - } - } - if (acc_len > 0) { - *buf ++ = (uint8_t)(acc << (8 - acc_len)); - } - return out_len; -} - -/* see inner.h */ -size_t -PQCLEAN_FALCON1024_CLEAN_trim_i8_decode( - int8_t *x, unsigned logn, unsigned bits, - const void *in, size_t max_in_len) { - size_t n, in_len; - const uint8_t *buf; - size_t u; - uint32_t acc, mask1, mask2; - unsigned acc_len; - - n = (size_t)1 << logn; - in_len = ((n * bits) + 7) >> 3; - if (in_len > max_in_len) { - return 0; - } - buf = in; - u = 0; - acc = 0; - acc_len = 0; - mask1 = ((uint32_t)1 << bits) - 1; - mask2 = (uint32_t)1 << (bits - 1); - while (u < n) { - acc = (acc << 8) | *buf ++; - acc_len += 8; - while (acc_len >= bits && u < n) { - uint32_t w; - - acc_len -= bits; - w = (acc >> acc_len) & mask1; - w |= -(w & mask2); - if (w == -mask2) { - /* - * The -2^(bits-1) value is forbidden. - */ - return 0; - } - x[u ++] = (int8_t) * (int32_t *)&w; - } - } - if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) { - /* - * Extra bits in the last byte must be zero. - */ - return 0; - } - return in_len; -} - -/* see inner.h */ -size_t -PQCLEAN_FALCON1024_CLEAN_comp_encode( - void *out, size_t max_out_len, - const int16_t *x, unsigned logn) { - uint8_t *buf; - size_t n, u, v; - uint32_t acc; - unsigned acc_len; - - n = (size_t)1 << logn; - buf = out; - - /* - * Make sure that all values are within the -2047..+2047 range. - */ - for (u = 0; u < n; u ++) { - if (x[u] < -2047 || x[u] > +2047) { - return 0; - } - } - - acc = 0; - acc_len = 0; - v = 0; - for (u = 0; u < n; u ++) { - int t; - unsigned w; - - /* - * Get sign and absolute value of next integer; push the - * sign bit. - */ - acc <<= 1; - t = x[u]; - if (t < 0) { - t = -t; - acc |= 1; - } - w = (unsigned)t; - - /* - * Push the low 7 bits of the absolute value. - */ - acc <<= 7; - acc |= w & 127u; - w >>= 7; - - /* - * We pushed exactly 8 bits. - */ - acc_len += 8; - - /* - * Push as many zeros as necessary, then a one. Since the - * absolute value is at most 2047, w can only range up to - * 15 at this point, thus we will add at most 16 bits - * here. With the 8 bits above and possibly up to 7 bits - * from previous iterations, we may go up to 31 bits, which - * will fit in the accumulator, which is an uint32_t. - */ - acc <<= (w + 1); - acc |= 1; - acc_len += w + 1; - - /* - * Produce all full bytes. - */ - while (acc_len >= 8) { - acc_len -= 8; - if (buf != NULL) { - if (v >= max_out_len) { - return 0; - } - buf[v] = (uint8_t)(acc >> acc_len); - } - v ++; - } - } - - /* - * Flush remaining bits (if any). - */ - if (acc_len > 0) { - if (buf != NULL) { - if (v >= max_out_len) { - return 0; - } - buf[v] = (uint8_t)(acc << (8 - acc_len)); - } - v ++; - } - - return v; -} - -/* see inner.h */ -size_t -PQCLEAN_FALCON1024_CLEAN_comp_decode( - int16_t *x, unsigned logn, - const void *in, size_t max_in_len) { - const uint8_t *buf; - size_t n, u, v; - uint32_t acc; - unsigned acc_len; - - n = (size_t)1 << logn; - buf = in; - acc = 0; - acc_len = 0; - v = 0; - for (u = 0; u < n; u ++) { - unsigned b, s, m; - - /* - * Get next eight bits: sign and low seven bits of the - * absolute value. - */ - if (v >= max_in_len) { - return 0; - } - acc = (acc << 8) | (uint32_t)buf[v ++]; - b = acc >> acc_len; - s = b & 128; - m = b & 127; - - /* - * Get next bits until a 1 is reached. - */ - for (;;) { - if (acc_len == 0) { - if (v >= max_in_len) { - return 0; - } - acc = (acc << 8) | (uint32_t)buf[v ++]; - acc_len = 8; - } - acc_len --; - if (((acc >> acc_len) & 1) != 0) { - break; - } - m += 128; - if (m > 2047) { - return 0; - } - } - x[u] = (int16_t) m; - if (s) { - x[u] = (int16_t) - x[u]; - } - } - return v; -} - -/* - * Key elements and signatures are polynomials with small integer - * coefficients. Here are some statistics gathered over many - * generated key pairs (10000 or more for each degree): - * - * log(n) n max(f,g) std(f,g) max(F,G) std(F,G) - * 1 2 129 56.31 143 60.02 - * 2 4 123 40.93 160 46.52 - * 3 8 97 28.97 159 38.01 - * 4 16 100 21.48 154 32.50 - * 5 32 71 15.41 151 29.36 - * 6 64 59 11.07 138 27.77 - * 7 128 39 7.91 144 27.00 - * 8 256 32 5.63 148 26.61 - * 9 512 22 4.00 137 26.46 - * 10 1024 15 2.84 146 26.41 - * - * We want a compact storage format for private key, and, as part of - * key generation, we are allowed to reject some keys which would - * otherwise be fine (this does not induce any noticeable vulnerability - * as long as we reject only a small proportion of possible keys). - * Hence, we enforce at key generation time maximum values for the - * elements of f, g, F and G, so that their encoding can be expressed - * in fixed-width values. Limits have been chosen so that generated - * keys are almost always within bounds, thus not impacting neither - * security or performance. - * - * IMPORTANT: the code assumes that all coefficients of f, g, F and G - * ultimately fit in the -127..+127 range. Thus, none of the elements - * of max_fg_bits[] and max_FG_bits[] shall be greater than 8. - */ - -const uint8_t PQCLEAN_FALCON1024_CLEAN_max_fg_bits[] = { - 0, /* unused */ - 8, - 8, - 8, - 8, - 8, - 7, - 7, - 6, - 6, - 5 -}; - -const uint8_t PQCLEAN_FALCON1024_CLEAN_max_FG_bits[] = { - 0, /* unused */ - 8, - 8, - 8, - 8, - 8, - 8, - 8, - 8, - 8, - 8 -}; - -/* - * When generating a new key pair, we can always reject keys which - * feature an abnormally large coefficient. This can also be done for - * signatures, albeit with some care: in case the signature process is - * used in a derandomized setup (explicitly seeded with the message and - * private key), we have to follow the specification faithfully, and the - * specification only enforces a limit on the L2 norm of the signature - * vector. The limit on the L2 norm implies that the absolute value of - * a coefficient of the signature cannot be more than the following: - * - * log(n) n max sig coeff (theoretical) - * 1 2 412 - * 2 4 583 - * 3 8 824 - * 4 16 1166 - * 5 32 1649 - * 6 64 2332 - * 7 128 3299 - * 8 256 4665 - * 9 512 6598 - * 10 1024 9331 - * - * However, the largest observed signature coefficients during our - * experiments was 1077 (in absolute value), hence we can assume that, - * with overwhelming probability, signature coefficients will fit - * in -2047..2047, i.e. 12 bits. - */ - -const uint8_t PQCLEAN_FALCON1024_CLEAN_max_sig_bits[] = { - 0, /* unused */ - 10, - 11, - 11, - 12, - 12, - 12, - 12, - 12, - 12, - 12 -}; |