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, 555 insertions, 0 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 new file mode 100644 index 000000000..c5ab4938b --- /dev/null +++ b/lib/liboqs/src/sig/falcon/pqclean_falcon-1024_clean/codec.c @@ -0,0 +1,555 @@ +#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 +}; |