aboutsummaryrefslogtreecommitdiffstats
path: root/src/libstrongswan/plugins
diff options
context:
space:
mode:
Diffstat (limited to 'src/libstrongswan/plugins')
-rw-r--r--src/libstrongswan/plugins/bliss/Makefile.am21
-rw-r--r--src/libstrongswan/plugins/bliss/bliss_fft.c200
-rw-r--r--src/libstrongswan/plugins/bliss/bliss_fft.h71
-rw-r--r--src/libstrongswan/plugins/bliss/bliss_fft_params.c652
-rw-r--r--src/libstrongswan/plugins/bliss/bliss_fft_params.h115
-rw-r--r--src/libstrongswan/plugins/bliss/bliss_param_set.c12
-rw-r--r--src/libstrongswan/plugins/bliss/bliss_param_set.h4
-rw-r--r--src/libstrongswan/plugins/bliss/bliss_private_key.c28
-rw-r--r--src/libstrongswan/plugins/bliss/bliss_public_key.c14
-rw-r--r--src/libstrongswan/plugins/bliss/bliss_reduce.h42
-rw-r--r--src/libstrongswan/plugins/bliss/tests/Makefile.am3
-rw-r--r--src/libstrongswan/plugins/bliss/tests/bliss_tests.h3
-rw-r--r--src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c154
13 files changed, 47 insertions, 1272 deletions
diff --git a/src/libstrongswan/plugins/bliss/Makefile.am b/src/libstrongswan/plugins/bliss/Makefile.am
index 7ce6f3262..b2d09427e 100644
--- a/src/libstrongswan/plugins/bliss/Makefile.am
+++ b/src/libstrongswan/plugins/bliss/Makefile.am
@@ -1,5 +1,6 @@
AM_CPPFLAGS = \
- -I$(top_srcdir)/src/libstrongswan
+ -I$(top_srcdir)/src/libstrongswan \
+ -I$(top_srcdir)/src/libstrongswan/math/libnttfft
AM_CFLAGS = \
$(PLUGIN_CFLAGS) \
@@ -7,9 +8,12 @@ AM_CFLAGS = \
# these file are also used by bliss_huffman
noinst_LTLIBRARIES = libbliss-params.la
+
libbliss_params_la_SOURCES = \
- bliss_param_set.h bliss_param_set.c \
- bliss_fft_params.h bliss_fft_params.c
+ bliss_param_set.h bliss_param_set.c
+
+libbliss_params_la_LIBADD = \
+ $(top_builddir)/src/libstrongswan/math/libnttfft/libnttfft.la
# these files are also used by the tests, we can't directly refer to them
# because of the subdirectory, which would cause distclean to fail
@@ -20,12 +24,14 @@ libbliss_la_SOURCES = \
bliss_signature.h bliss_signature.c \
bliss_utils.h bliss_utils.c \
bliss_bitpacker.h bliss_bitpacker.c \
- bliss_reduce.h bliss_fft.h bliss_fft.c \
bliss_huffman_code.h bliss_huffman_code.c \
bliss_huffman_code_1.c bliss_huffman_code_3.c bliss_huffman_code_4.c \
bliss_huffman_coder.h bliss_huffman_coder.c \
bliss_sampler.h bliss_sampler.c
-libbliss_la_LIBADD = libbliss-params.la
+
+libbliss_la_LIBADD = \
+ $(top_builddir)/src/libstrongswan/math/libnttfft/libnttfft.la \
+ libbliss-params.la
if MONOLITHIC
noinst_LTLIBRARIES += libstrongswan-bliss.la
@@ -43,7 +49,10 @@ libstrongswan_bliss_la_LIBADD = libbliss.la
noinst_PROGRAMS = bliss_huffman
bliss_huffman_SOURCES = bliss_huffman.c
-bliss_huffman_LDADD = -lm libbliss-params.la
+
+bliss_huffman_LDADD = -lm \
+ $(top_builddir)/src/libstrongswan/math/libnttfft/libnttfft.la \
+ libbliss-params.la
recreate-bliss-huffman : bliss_huffman bliss_huffman_code.h
$(AM_V_GEN) \
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft.c b/src/libstrongswan/plugins/bliss/bliss_fft.c
deleted file mode 100644
index 2355a9f4c..000000000
--- a/src/libstrongswan/plugins/bliss/bliss_fft.c
+++ /dev/null
@@ -1,200 +0,0 @@
-/*
- * Copyright (C) 2014-2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
- * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * for more details.
- */
-
-#include "bliss_fft.h"
-#include "bliss_reduce.h"
-
-typedef struct private_bliss_fft_t private_bliss_fft_t;
-
-/**
- * Private data structure for bliss_fft_t object
- */
-struct private_bliss_fft_t {
-
- /**
- * Public interface.
- */
- bliss_fft_t public;
-
- /**
- * FFT parameter set used as constants
- */
- bliss_fft_params_t *p;
-
-};
-
-METHOD(bliss_fft_t, get_size, uint16_t,
- private_bliss_fft_t *this)
-{
- return this->p->n;
-}
-
-METHOD(bliss_fft_t, get_modulus, uint16_t,
- private_bliss_fft_t *this)
-{
- return this->p->q;
-}
-
-/**
- * Do an FFT butterfly operation
- *
- * x[i1] ---|+|------- x[i1]
- * \/
- * /\ w[iw]
- * x[i2] ---|-|--|*|-- x[i2]
- *
- */
-static void butterfly(private_bliss_fft_t *this, uint32_t *x, int i1,int i2,
- int iw)
-{
- uint32_t xp, xm;
-
- xp = x[i1] + x[i2];
- xm = x[i1] + (this->p->q - x[i2]);
- if (xp >= this->p->q)
- {
- xp -= this->p->q;
- }
- x[i1] = xp;
- x[i2] = bliss_mreduce(xm * this->p->wr[iw], this->p);
-}
-
-/**
- * Trivial butterfly operation of last FFT stage
- */
-static void butterfly_last(private_bliss_fft_t *this, uint32_t *x, int i1)
-{
- uint32_t xp, xm;
- int i2 = i1 + 1;
-
- xp = x[i1] + x[i2];
- xm = x[i1] + (this->p->q - x[i2]);
- if (xp >= this->p->q)
- {
- xp -= this->p->q;
- }
- if (xm >= this->p->q)
- {
- xm -= this->p->q;
- }
- x[i1] = xp;
- x[i2] = xm;
-}
-
-METHOD(bliss_fft_t, transform, void,
- private_bliss_fft_t *this, uint32_t *a, uint32_t *b, bool inverse)
-{
- int stage, i, j, k, m, n, s, t, iw, i_rev;
- uint32_t tmp;
-
- /* we are going to use the transform size n a lot */
- n = this->p->n;
- s = this->p->s;
-
- if (!inverse)
- {
- /* apply linear phase needed for negative wrapped convolution */
- for (i = 0; i < n; i++)
- {
- b[i] = bliss_mreduce(a[i] * this->p->wf[s*i], this->p);
- }
- }
- else if (a != b)
- {
- /* copy if input and output array are not the same */
- for (i = 0; i < n; i++)
- {
- b[i] = a[i];
- }
- }
-
- m = n;
- k = 1;
-
- for (stage = this->p->stages; stage > 0; stage--)
- {
- m >>= 1;
- t = 0;
-
- for (j = 0; j < k; j++)
- {
- if (stage == 1)
- {
- butterfly_last(this, b, t);
- }
- else
- {
- for (i = 0; i < m; i++)
- {
- iw = s * (inverse ? (n - i * k) : (i * k));
- butterfly(this, b, t + i, t + i + m, iw);
- }
- }
- t += 2*m;
- }
- k <<= 1;
- }
-
- /* Sort output in bit-reverse order */
- for (i = 0; i < n; i++)
- {
- i_rev = this->p->rev[i];
-
- if (i_rev > i)
- {
- tmp = b[i];
- b[i] = b[i_rev];
- b[i_rev] = tmp;
- }
- }
-
- /**
- * Compensate the linear phase needed for negative wrapped convolution
- * and normalize the output array with 1/n mod q after the inverse FFT.
- */
- if (inverse)
- {
- for (i = 0; i < n; i++)
- {
- b[i] = bliss_mreduce(b[i] * this->p->wi[i], this->p);
- }
- }
-}
-
-METHOD(bliss_fft_t, destroy, void,
- private_bliss_fft_t *this)
-{
- free(this);
-}
-
-/**
- * See header.
- */
-bliss_fft_t *bliss_fft_create(bliss_fft_params_t *params)
-{
- private_bliss_fft_t *this;
-
- INIT(this,
- .public = {
- .get_size = _get_size,
- .get_modulus = _get_modulus,
- .transform = _transform,
- .destroy = _destroy,
- },
- .p = params,
- );
-
- return &this->public;
-}
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft.h b/src/libstrongswan/plugins/bliss/bliss_fft.h
deleted file mode 100644
index a79edd2be..000000000
--- a/src/libstrongswan/plugins/bliss/bliss_fft.h
+++ /dev/null
@@ -1,71 +0,0 @@
-/*
- * Copyright (C) 2014 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
- * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * for more details.
- */
-
-/**
- * @defgroup bliss_fft bliss_fft
- * @{ @ingroup bliss_p
- */
-
-#ifndef BLISS_FFT_H_
-#define BLISS_FFT_H_
-
-#include "bliss_fft_params.h"
-
-#include <library.h>
-
-typedef struct bliss_fft_t bliss_fft_t;
-
-/**
- * Implements a Number Theoretic Transform (NTT) via the FFT algorithm
- */
-struct bliss_fft_t {
-
- /**
- * Get the size of the Number Theoretic Transform
- *
- * @result Transform size
- */
- uint16_t (*get_size)(bliss_fft_t *this);
-
- /**
- * Get the prime modulus of the Number Theoretic Transform
- *
- * @result Prime modulus
- */
- uint16_t (*get_modulus)(bliss_fft_t *this);
-
- /**
- * Compute the [inverse] NTT of a polynomial
- *
- * @param a Coefficient of input polynomial
- * @param b Coefficient of output polynomial
- * @param inverse TRUE if the inverse NTT has to be computed
- */
- void (*transform)(bliss_fft_t *this, uint32_t *a, uint32_t *b, bool inverse);
-
- /**
- * Destroy bliss_fft_t object
- */
- void (*destroy)(bliss_fft_t *this);
-};
-
-/**
- * Create a bliss_fft_t object for a given FFT parameter set
- *
- * @param params FFT parameters
- */
-bliss_fft_t *bliss_fft_create(bliss_fft_params_t *params);
-
-#endif /** BLISS_FFT_H_ @}*/
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft_params.c b/src/libstrongswan/plugins/bliss/bliss_fft_params.c
deleted file mode 100644
index db6abea33..000000000
--- a/src/libstrongswan/plugins/bliss/bliss_fft_params.c
+++ /dev/null
@@ -1,652 +0,0 @@
-/*
- * Copyright (C) 2014-2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
- * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * for more details.
- */
-
-#include "bliss_fft_params.h"
-
-/**
- * FFT twiddle factors in Montgomery form for q = 12289 and n = 1024
- */
-static uint16_t wr_12289_1024[] = {
- 4075, 3051, 2031, 1207, 9987, 10092, 2948, 9273, 11973, 9094,
- 3202, 9430, 7377, 5092, 3728, 10626, 4536, 1062, 2882, 6039,
- 975, 10908, 6065, 2249, 11889, 4978, 10431, 7270, 12138, 4890,
- 6119, 4895, 6364, 4611, 4737, 10911, 6212, 9452, 8455, 8758,
- 11316, 1479, 11026, 11847, 2920, 7901, 6190, 8374, 4789, 1170,
- 8174, 7278, 241, 11809, 1058, 2686, 8724, 9650, 5868, 4885,
- 5874, 5179, 7991, 10600, 3262, 81, 3969, 10146, 5594, 3748,
- 11606, 3400, 6843, 3504, 11939, 7428, 7591, 3289, 1404, 7351,
- 3818, 2747, 11713, 8643, 5681, 8011, 11580, 2126, 5862, 4591,
- 3757, 12047, 431, 8830, 2555, 2305, 2344, 4255, 11871, 4096,
-
- 4080, 3296, 1747, 11869, 3998, 11567, 1489, 11516, 11279, 11955,
- 8212, 9140, 5456, 9275, 12071, 1607, 5009, 11950, 7967, 9424,
- 7083, 2975, 10596, 3066, 2766, 355, 5106, 4414, 7373, 4896,
- 6413, 7012, 11785, 12171, 6507, 11618, 3988, 11077, 2057, 2481,
- 10968, 9005, 11130, 4654, 6844, 3553, 2051, 2187, 8851, 3584,
- 3570, 2884, 6137, 5777, 426, 8585, 2839, 3932, 8333, 2780,
- 1041, 1853, 4774, 435, 9026, 12159, 5919, 7384, 5435, 8246,
- 10806, 1067, 3127, 5755, 11637, 4919, 7540, 790, 1843, 4284,
- 1003, 12280, 11848, 2969, 10302, 949, 9634, 5084, 3336, 3707,
- 9597, 3271, 522, 1000, 12133, 4645, 6403, 6522, 64, 3136,
-
- 6196, 8668, 6906, 6591, 3445, 9048, 948, 9585, 2683, 8577,
- 2447, 9302, 1105, 4989, 10970, 9103, 3643, 6461, 9364, 4143,
- 6383, 5542, 1200, 9644, 5574, 2768, 453, 9908, 6221, 9893,
- 5486, 10745, 10367, 4134, 5942, 8511, 11502, 10593, 2919, 7852,
- 3789, 1326, 3529, 875, 6008, 11745, 10211, 8779, 56, 2744,
- 11566, 1440, 9115, 4231, 10695, 7917, 6974, 9923, 6956, 9041,
- 605, 5067, 2503, 12046, 382, 6429, 7796, 1045, 2049, 2089,
- 4049, 1777, 1050, 2294, 1805, 2422, 8077, 2525, 835, 4048,
- 1728, 10938, 7535, 545, 2127, 5911, 6992, 10805, 1018, 726,
- 10996, 10377, 4624, 5374, 5257, 11813, 1254, 1, 49, 2401,
-
- 7048, 1260, 295, 2166, 7822, 2319, 3030, 1002, 12231, 9447,
- 8210, 9042, 654, 7468, 9551, 1017, 677, 8595, 3329, 3364,
- 5079, 3091, 3991, 11224, 9260, 11336, 2459, 9890, 5339, 3542,
- 1512, 354, 5057, 2013, 325, 3636, 6118, 4846, 3963, 9852,
- 3477, 10616, 4046, 1630, 6136, 5728, 10314, 1537, 1579, 3637,
- 6167, 7247, 11011, 11112, 3772, 493, 11868, 3949, 9166, 6730,
- 10256, 10984, 9789, 390, 6821, 2426, 8273, 12129, 4449, 9088,
- 2908, 7313, 1956, 9821, 1958, 9919, 6760, 11726, 9280, 27,
- 1323, 3382, 5961, 9442, 7965, 9326, 2281, 1168, 8076, 2476,
- 10723, 9289, 468, 10643, 5369, 5012, 12097, 2881, 5990, 10863,
-
- 3860, 4805, 1954, 9723, 9445, 8112, 4240, 11136, 4948, 8961,
- 8974, 9611, 3957, 9558, 1360, 5195, 8775, 12149, 5429, 7952,
- 8689, 7935, 7856, 3985, 10930, 7143, 5915, 7188, 8120, 4632,
- 5766, 12176, 6752, 11334, 2361, 5088, 3532, 1022, 922, 8311,
- 1702, 9664, 6554, 1632, 6234, 10530, 12121, 4057, 2169, 7969,
- 9522, 11885, 4782, 827, 3656, 7098, 3710, 9744, 10474, 9377,
- 4780, 729, 11143, 5291, 1190, 9154, 6142, 6022, 142, 6958,
- 9139, 5407, 6874, 5023, 347, 4714, 9784, 145, 7105, 4053,
- 1973, 10654, 5908, 6845, 3602, 4452, 9235, 10111, 3879, 5736,
- 10706, 8456, 8807, 1428, 8527, 12286, 12142, 5086, 3434, 8509,
-
- 11404, 5791, 1112, 5332, 3199, 9283, 174, 8526, 12237, 9741,
- 10327, 2174, 8214, 9238, 10258, 11082, 2302, 2197, 9341, 3016,
- 316, 3195, 9087, 2859, 4912, 7197, 8561, 1663, 7753, 11227,
- 9407, 6250, 11314, 1381, 6224, 10040, 400, 7311, 1858, 5019,
- 151, 7399, 6170, 7394, 5925, 7678, 7552, 1378, 6077, 2837,
- 3834, 3531, 973, 10810, 1263, 442, 9369, 4388, 6099, 3915,
- 7500, 11119, 4115, 5011, 12048, 480, 11231, 9603, 3565, 2639,
- 6421, 7404, 6415, 7110, 4298, 1689, 9027, 12208, 8320, 2143,
- 6695, 8541, 683, 8889, 5446, 8785, 350, 4861, 4698, 9000,
- 10885, 4938, 8471, 9542, 576, 3646, 6608, 4278, 709, 10163,
-
- 6427, 7698, 8532, 242, 11858, 3459, 9734, 9984, 9945, 8034,
- 418, 8193, 8209, 8993, 10542, 420, 8291, 722, 10800, 773,
- 1010, 334, 4077, 3149, 6833, 3014, 218, 10682, 7280, 339,
- 4322, 2865, 5206, 9314, 1693, 9223, 9523, 11934, 7183, 7875,
- 4916, 7393, 5876, 5277, 504, 118, 5782, 671, 8301, 1212,
- 10232, 9808, 1321, 3284, 1159, 7635, 5445, 8736, 10238, 10102,
- 3438, 8705, 8719, 9405, 6152, 6512, 11863, 3704, 9450, 8357,
- 3956, 9509, 11248, 10436, 7515, 11854, 3263, 130, 6370, 4905,
- 6854, 4043, 1483, 11222, 9162, 6534, 652, 7370, 4749, 11499,
- 10446, 8005, 11286, 9, 441, 9320, 1987, 11340, 2655, 7205,
-
- 8953, 8582, 2692, 9018, 11767, 11289, 156, 7644, 5886, 5767,
- 12225, 9153, 6093, 3621, 5383, 5698, 8844, 3241, 11341, 2704,
- 9606, 3712, 9842, 2987, 11184, 7300, 1319, 3186, 8646, 5828,
- 2925, 8146, 5906, 6747, 11089, 2645, 6715, 9521, 11836, 2381,
- 6068, 2396, 6803, 1544, 1922, 8155, 6347, 3778, 787, 1696,
- 9370, 4437, 8500, 10963, 8760, 11414, 6281, 544, 2078, 3510,
- 12233, 9545, 723, 10849, 3174, 8058, 1594, 4372, 5315, 2366,
- 5333, 3248, 11684, 7222, 9786, 243, 11907, 5860, 4493, 11244,
- 10240, 10200, 8240, 10512, 11239, 9995, 10484, 9867, 4212, 9764,
- 11454, 8241, 10561, 1351, 4754, 11744, 10162, 6378, 5297, 1484,
-
- 11271, 11563, 1293, 1912, 7665, 6915, 7032, 476, 11035, 12288,
- 12240, 9888, 5241, 11029, 11994, 10123, 4467, 9970, 9259, 11287,
- 58, 2842, 4079, 3247, 11635, 4821, 2738, 11272, 11612, 3694,
- 8960, 8925, 7210, 9198, 8298, 1065, 3029, 953, 9830, 2399,
- 6950, 8747, 10777, 11935, 7232, 10276, 11964, 8653, 6171, 7443,
- 8326, 2437, 8812, 1673, 8243, 10659, 6153, 6561, 1975, 10752,
- 10710, 8652, 6122, 5042, 1278, 1177, 8517, 11796, 421, 8340,
- 3123, 5559, 2033, 1305, 2500, 11899, 5468, 9863, 4016, 160,
- 7840, 3201, 9381, 4976, 10333, 2468, 10331, 2370, 5529, 563,
- 3009, 12262, 10966, 8907, 6328, 2847, 4324, 2963, 10008, 11121,
-
- 4213, 9813, 1566, 3000, 11821, 1646, 6920, 7277, 192, 9408,
- 6299, 1426, 8429, 7484, 10335, 2566, 2844, 4177, 8049, 1153,
- 7341, 3328, 3315, 2678, 8332, 2731, 10929, 7094, 3514, 140,
- 6860, 4337, 3600, 4354, 4433, 8304, 1359, 5146, 6374, 5101,
- 4169, 7657, 6523, 113, 5537, 955, 9928, 7201, 8757, 11267,
- 11367, 3978, 10587, 2625, 5735, 10657, 6055, 1759, 168, 8232,
- 10120, 4320, 2767, 404, 7507, 11462, 8633, 5191, 8579, 2545,
- 1815, 2912, 7509, 11560, 1146, 6998, 11099, 3135, 6147, 6267,
- 12147, 5331, 3150, 6882, 5415, 7266, 11942, 7575, 2505, 12144,
- 5184, 8236, 10316, 1635, 6381, 5444, 8687, 7837, 3054, 2178,
-
- 8410, 6553, 1583, 3833, 3482, 10861, 3762, 3, 147, 7203,
- 8855, 3780, 885, 6498, 11177, 6957, 9090, 3006, 12115, 3763,
- 52, 2548, 1962, 10115, 4075
-};
-
-/**
- * FFT phase shift in forward transform for q = 12289 and n = 1024
- */
-static uint16_t wf_12289_1024[] = {
- 3186, 10013, 8646, 11366, 5828, 3929, 2925, 8186, 8146, 7866,
- 5906, 4475, 6747, 10362, 11089, 3889, 2645, 6226, 6715, 10138,
- 9521, 5202, 11836, 9118, 2381, 4378, 6068, 5609, 2396, 4483,
- 6803, 10754, 1544, 10808, 1922, 1165, 8155, 7929, 6347, 7562,
- 3778, 1868, 787, 5509, 1696, 11872, 9370, 4145, 4437, 6481,
- 8500, 10344, 10963, 3007, 8760, 12164, 11414, 6164, 6281, 7100,
- 544, 3808, 2078, 2257, 3510, 12281, 12233, 11897, 9545, 5370,
- 723, 5061, 10849, 2209, 3174, 9929, 8058, 7250, 1594, 11158,
- 4372, 6026, 5315, 338, 2366, 4273, 5333, 464, 3248, 10447,
- 11684, 8054, 7222, 1398, 9786, 7057, 243, 1701, 11907, 9615,
-
- 5860, 4153, 4493, 6873, 11244, 4974, 10240, 10235, 10200, 9955,
- 8240, 8524, 10512, 12139, 11239, 4939, 9995, 8520, 10484, 11943,
- 9867, 7624, 4212, 4906, 9764, 6903, 11454, 6444, 8241, 8531,
- 10561, 193, 1351, 9457, 4754, 8700, 11744, 8474, 10162, 9689,
- 6378, 7779, 5297, 212, 1484, 10388, 11271, 5163, 11563, 7207,
- 1293, 9051, 1912, 1095, 7665, 4499, 6915, 11538, 7032, 68,
- 476, 3332, 11035, 3511, 12288, 12282, 12240, 11946, 9888, 7771,
- 5241, 12109, 11029, 3469, 11994, 10224, 10123, 9416, 4467, 6691,
- 9970, 8345, 9259, 3368, 11287, 5275, 58, 406, 2842, 7605,
- 4079, 3975, 3247, 10440, 11635, 7711, 4821, 9169, 2738, 6877,
-
- 11272, 5170, 11612, 7550, 3694, 1280, 8960, 1275, 8925, 1030,
- 7210, 1314, 9198, 2941, 8298, 8930, 1065, 7455, 3029, 8914,
- 953, 6671, 9830, 7365, 2399, 4504, 6950, 11783, 8747, 12073,
- 10777, 1705, 11935, 9811, 7232, 1468, 10276, 10487, 11964, 10014,
- 8653, 11415, 6171, 6330, 7443, 2945, 8326, 9126, 2437, 4770,
- 8812, 239, 1673, 11711, 8243, 8545, 10659, 879, 6153, 6204,
- 6561, 9060, 1975, 1536, 10752, 1530, 10710, 1236, 8652, 11408,
- 6122, 5987, 5042, 10716, 1278, 8946, 1177, 8239, 8517, 10463,
- 11796, 8838, 421, 2947, 8340, 9224, 3123, 9572, 5559, 2046,
- 2033, 1942, 1305, 9135, 2500, 5211, 11899, 9559, 5468, 1409,
-
- 9863, 7596, 4016, 3534, 160, 1120, 7840, 5724, 3201, 10118,
- 9381, 4222, 4976, 10254, 10333, 10886, 2468, 4987, 10331, 10872,
- 2370, 4301, 5529, 1836, 563, 3941, 3009, 8774, 12262, 12100,
- 10966, 3028, 8907, 904, 6328, 7429, 2847, 7640, 4324, 5690,
- 2963, 8452, 10008, 8611, 11121, 4113, 4213, 4913, 9813, 7246,
- 1566, 10962, 3000, 8711, 11821, 9013, 1646, 11522, 6920, 11573,
- 7277, 1783, 192, 1344, 9408, 4411, 6299, 7226, 1426, 9982,
- 8429, 9847, 7484, 3232, 10335, 10900, 2566, 5673, 2844, 7619,
- 4177, 4661, 8049, 7187, 1153, 8071, 7341, 2231, 3328, 11007,
- 3315, 10916, 2678, 6457, 8332, 9168, 2731, 6828, 10929, 2769,
-
- 7094, 502, 3514, 20, 140, 980, 6860, 11153, 4337, 5781,
- 3600, 622, 4354, 5900, 4433, 6453, 8304, 8972, 1359, 9513,
- 5146, 11444, 6374, 7751, 5101, 11129, 4169, 4605, 7657, 4443,
- 6523, 8794, 113, 791, 5537, 1892, 955, 6685, 9928, 8051,
- 7201, 1251, 8757, 12143, 11267, 5135, 11367, 5835, 3978, 3268,
- 10587, 375, 2625, 6086, 5735, 3278, 10657, 865, 6055, 5518,
- 1759, 24, 168, 1176, 8232, 8468, 10120, 9395, 4320, 5662,
- 2767, 7080, 404, 2828, 7507, 3393, 11462, 6500, 8633, 11275,
- 5191, 11759, 8579, 10897, 2545, 5526, 1815, 416, 2912, 8095,
- 7509, 3407, 11560, 7186, 1146, 8022, 6998, 12119, 11099, 3959,
-
- 3135, 9656, 6147, 6162, 6267, 7002, 12147, 11295, 5331, 450,
- 3150, 9761, 6882, 11307, 5415, 1038, 7266, 1706, 11942, 9860,
- 7575, 3869, 2505, 5246, 12144, 11274, 5184, 11710, 8236, 8496,
- 10316, 10767, 1635, 11445, 6381, 7800, 5444, 1241, 8687, 11653,
- 7837, 5703, 3054, 9089, 2178, 2957, 8410, 9714, 6553, 9004,
- 1583, 11081, 3833, 2253, 3482, 12085, 10861, 2293, 3762, 1756,
- 3, 21, 147, 1029, 7203, 1265, 8855, 540, 3780, 1882,
- 885, 6195, 6498, 8619, 11177, 4505, 6957, 11832, 9090, 2185,
- 3006, 8753, 12115, 11071, 3763, 1763, 52, 364, 2548, 5547,
- 1962, 1445, 10115, 9360, 4075, 3947, 3051, 9068, 2031, 1928,
-
- 1207, 8449, 9987, 8464, 10092, 9199, 2948, 8347, 9273, 3466,
- 11973, 10077, 9094, 2213, 3202, 10125, 9430, 4565, 7377, 2483,
- 5092, 11066, 3728, 1518, 10626, 648, 4536, 7174, 1062, 7434,
- 2882, 7885, 6039, 5406, 975, 6825, 10908, 2622, 6065, 5588,
- 2249, 3454, 11889, 9489, 4978, 10268, 10431, 11572, 7270, 1734,
- 12138, 11232, 4890, 9652, 6119, 5966, 4895, 9687, 6364, 7681,
- 4611, 7699, 4737, 8581, 10911, 2643, 6212, 6617, 9452, 4719,
- 8455, 10029, 8758, 12150, 11316, 5478, 1479, 10353, 11026, 3448,
- 11847, 9195, 2920, 8151, 7901, 6151, 6190, 6463, 8374, 9462,
- 4789, 8945, 1170, 8190, 8174, 8062, 7278, 1790, 241, 1687,
-
- 11809, 8929, 1058, 7406, 2686, 6513, 8724, 11912, 9650, 6105,
- 5868, 4209, 4885, 9617, 5874, 4251, 5179, 11675, 7991, 6781,
- 10600, 466, 3262, 10545, 81, 567, 3969, 3205, 10146, 9577,
- 5594, 2291, 3748, 1658, 11606, 7508, 3400, 11511, 6843, 11034,
- 3504, 12239, 11939, 9839, 7428, 2840, 7591, 3981, 3289, 10734,
- 1404, 9828, 7351, 2301, 3818, 2148, 2747, 6940, 11713, 8257,
- 8643, 11345, 5681, 2900, 8011, 6921, 11580, 7326, 2126, 2593,
- 5862, 4167, 4591, 7559, 3757, 1721, 12047, 10595, 431, 3017,
- 8830, 365, 2555, 5596, 2305, 3846, 2344, 4119, 4255, 5207,
- 11871, 9363, 4096, 4094, 4080, 3982, 3296, 10783, 1747, 12229,
-
- 11869, 9349, 3998, 3408, 11567, 7235, 1489, 10423, 11516, 6878,
- 11279, 5219, 11955, 9951, 8212, 8328, 9140, 2535, 5456, 1325,
- 9275, 3480, 12071, 10763, 1607, 11249, 5009, 10485, 11950, 9916,
- 7967, 6613, 9424, 4523, 7083, 425, 2975, 8536, 10596, 438,
- 3066, 9173, 2766, 7073, 355, 2485, 5106, 11164, 4414, 6320,
- 7373, 2455, 4896, 9694, 6413, 8024, 7012, 12217, 11785, 8761,
- 12171, 11463, 6507, 8682, 11618, 7592, 3988, 3338, 11077, 3805,
- 2057, 2110, 2481, 5078, 10968, 3042, 9005, 1590, 11130, 4176,
- 4654, 8000, 6844, 11041, 3553, 293, 2051, 2068, 2187, 3020,
- 8851, 512, 3584, 510, 3570, 412, 2884, 7899, 6137, 6092,
-
- 5777, 3572, 426, 2982, 8585, 10939, 2839, 7584, 3932, 2946,
- 8333, 9175, 2780, 7171, 1041, 7287, 1853, 682, 4774, 8840,
- 435, 3045, 9026, 1737, 12159, 11379, 5919, 4566, 7384, 2532,
- 5435, 1178, 8246, 8566, 10806, 1908, 1067, 7469, 3127, 9600,
- 5755, 3418, 11637, 7725, 4919, 9855, 7540, 3624, 790, 5530,
- 1843, 612, 4284, 5410, 1003, 7021, 12280, 12226, 11848, 9202,
- 2969, 8494, 10302, 10669, 949, 6643, 9634, 5993, 5084, 11010,
- 3336, 11063, 3707, 1371, 9597, 5734, 3271, 10608, 522, 3654,
- 1000, 7000, 12133, 11197, 4645, 7937, 6403, 7954, 6522, 8787,
- 64, 448, 3136, 9663, 6196, 6505, 8668, 11520, 6906, 11475,
-
- 6591, 9270, 3445, 11826, 9048, 1891, 948, 6636, 9585, 5650,
- 2683, 6492, 8577, 10883, 2447, 4840, 9302, 3669, 1105, 7735,
- 4989, 10345, 10970, 3056
-};
-
-/**
- * FFT phase shift and scaling inverse transform for q = 12289 and n = 1024
- */
-static uint16_t wi_12289_1024[] = {
- 12277, 5265, 9530, 3117, 5712, 816, 10650, 3277, 9246, 4832,
- 5957, 851, 10655, 10300, 3227, 461, 3577, 511, 73, 1766,
- 5519, 2544, 2119, 7325, 2802, 5667, 11343, 3376, 5749, 6088,
- 7892, 2883, 3923, 2316, 3842, 4060, 580, 3594, 2269, 9102,
- 6567, 9716, 1388, 5465, 7803, 8137, 2918, 3928, 9339, 10112,
- 11978, 10489, 3254, 3976, 568, 8859, 11799, 12219, 12279, 10532,
- 12038, 8742, 4760, 680, 8875, 4779, 7705, 8123, 2916, 10950,
- 6831, 4487, 641, 10625, 5029, 2474, 2109, 5568, 2551, 2120,
- 3814, 4056, 2335, 10867, 3308, 11006, 6839, 977, 10673, 8547,
- 1221, 1930, 7298, 11576, 8676, 2995, 3939, 7585, 11617, 12193,
-
- 5253, 2506, 358, 8829, 6528, 11466, 1638, 234, 1789, 10789,
- 6808, 11506, 8666, 1238, 3688, 4038, 4088, 584, 1839, 7285,
- 8063, 4663, 9444, 10127, 8469, 4721, 2430, 9125, 11837, 1691,
- 10775, 6806, 6239, 6158, 7902, 4640, 4174, 5863, 11371, 3380,
- 3994, 11104, 6853, 979, 3651, 11055, 6846, 978, 7162, 9801,
- 10178, 1454, 7230, 4544, 9427, 8369, 11729, 12209, 10522, 10281,
- 8491, 1213, 5440, 9555, 1365, 195, 3539, 11039, 1577, 5492,
- 11318, 5128, 11266, 3365, 7503, 4583, 7677, 8119, 4671, 5934,
- 7870, 6391, 913, 1886, 2025, 5556, 7816, 11650, 6931, 9768,
- 3151, 9228, 6585, 7963, 11671, 6934, 11524, 6913, 11521, 5157,
-
- 7759, 2864, 9187, 3068, 5705, 815, 1872, 2023, 289, 5308,
- 6025, 7883, 9904, 4926, 7726, 8126, 4672, 2423, 9124, 3059,
- 437, 1818, 7282, 6307, 901, 7151, 11555, 8673, 1239, 177,
- 5292, 756, 108, 1771, 253, 8814, 10037, 4945, 2462, 7374,
- 2809, 5668, 7832, 4630, 2417, 5612, 7824, 8140, 4674, 7690,
- 11632, 8684, 11774, 1682, 5507, 7809, 11649, 10442, 8514, 6483,
- 9704, 6653, 2706, 10920, 1560, 3734, 2289, 327, 7069, 4521,
- 4157, 4105, 2342, 10868, 12086, 12260, 3507, 501, 10605, 1515,
- 1972, 7304, 2799, 3911, 7581, 1083, 7177, 6292, 4410, 630,
- 90, 3524, 2259, 7345, 6316, 6169, 6148, 6145, 4389, 627,
-
- 10623, 12051, 12255, 8773, 6520, 2687, 3895, 2312, 5597, 11333,
- 1619, 5498, 2541, 363, 3563, 509, 7095, 11547, 12183, 3496,
- 2255, 9100, 1300, 7208, 8052, 6417, 7939, 9912, 1416, 5469,
- 6048, 864, 1879, 2024, 9067, 6562, 2693, 7407, 9836, 10183,
- 8477, 1211, 173, 7047, 8029, 1147, 3675, 525, 75, 7033,
- 8027, 8169, 1167, 7189, 1027, 7169, 9802, 6667, 2708, 3898,
- 4068, 9359, 1337, 191, 5294, 6023, 2616, 7396, 11590, 8678,
- 8262, 6447, 921, 10665, 12057, 3478, 4008, 11106, 12120, 3487,
- 9276, 10103, 6710, 11492, 8664, 8260, 1180, 10702, 5040, 720,
- 3614, 5783, 9604, 1372, 196, 28, 4, 10534, 5016, 11250,
-
- 10385, 12017, 8739, 3004, 9207, 6582, 6207, 7909, 4641, 663,
- 7117, 8039, 2904, 3926, 4072, 7604, 6353, 11441, 3390, 5751,
- 11355, 10400, 8508, 2971, 2180, 2067, 5562, 11328, 6885, 11517,
- 6912, 2743, 3903, 11091, 3340, 9255, 10100, 4954, 7730, 6371,
- 9688, 1384, 7220, 2787, 9176, 4822, 4200, 600, 7108, 2771,
- 3907, 9336, 8356, 8216, 8196, 4682, 4180, 9375, 6606, 7966,
- 1138, 10696, 1528, 5485, 11317, 8639, 10012, 6697, 7979, 4651,
- 2420, 7368, 11586, 10433, 3246, 7486, 2825, 10937, 3318, 474,
- 7090, 4524, 5913, 7867, 4635, 9440, 11882, 3453, 5760, 4334,
- 9397, 3098, 10976, 1568, 224, 32, 10538, 3261, 3977, 9346,
-
- 10113, 8467, 11743, 12211, 3500, 500, 1827, 261, 5304, 7780,
- 2867, 10943, 6830, 7998, 11676, 1668, 5505, 2542, 9141, 4817,
- 9466, 6619, 11479, 5151, 4247, 7629, 4601, 5924, 6113, 6140,
- 9655, 6646, 2705, 2142, 306, 7066, 2765, 395, 1812, 3770,
- 11072, 8604, 10007, 11963, 1709, 9022, 4800, 7708, 9879, 6678,
- 954, 5403, 4283, 4123, 589, 8862, 1266, 3692, 2283, 9104,
- 11834, 12224, 7013, 4513, 7667, 6362, 4420, 2387, 341, 7071,
- 9788, 6665, 9730, 1390, 10732, 10311, 1473, 1966, 3792, 7564,
- 11614, 10437, 1491, 213, 1786, 9033, 3046, 9213, 10094, 1442,
- 206, 1785, 255, 1792, 256, 10570, 1510, 7238, 1034, 7170,
-
- 6291, 7921, 11665, 3422, 4000, 2327, 2088, 5565, 795, 10647,
- 1521, 5484, 2539, 7385, 1055, 7173, 8047, 11683, 1669, 1994,
- 3796, 5809, 4341, 9398, 11876, 12230, 10525, 12037, 12253, 3506,
- 4012, 9351, 4847, 2448, 7372, 9831, 3160, 2207, 5582, 2553,
- 7387, 6322, 9681, 1383, 10731, 1533, 219, 5298, 4268, 7632,
- 6357, 9686, 8406, 4712, 9451, 10128, 4958, 5975, 11387, 8649,
- 11769, 6948, 11526, 12180, 1740, 10782, 6807, 2728, 7412, 4570,
- 4164, 4106, 11120, 12122, 8754, 11784, 3439, 5758, 11356, 6889,
- 9762, 11928, 1704, 1999, 10819, 12079, 12259, 7018, 11536, 1648,
- 1991, 2040, 2047, 2048, 10826, 12080, 8748, 8272, 8204, 1172,
-
- 1923, 7297, 2798, 7422, 6327, 4415, 7653, 6360, 11442, 12168,
- 7005, 8023, 9924, 8440, 8228, 2931, 7441, 1063, 3663, 5790,
- 9605, 10150, 1450, 8985, 11817, 10466, 10273, 12001, 3470, 7518,
- 1074, 1909, 7295, 9820, 4914, 702, 5367, 7789, 8135, 9940,
- 1420, 3714, 11064, 12114, 12264, 1752, 5517, 9566, 11900, 1700,
- 3754, 5803, 829, 1874, 7290, 2797, 10933, 5073, 7747, 8129,
- 6428, 6185, 11417, 1631, 233, 5300, 9535, 10140, 11982, 8734,
- 8270, 2937, 10953, 8587, 8249, 2934, 9197, 4825, 5956, 4362,
- 9401, 1343, 3703, 529, 10609, 12049, 6988, 6265, 895, 3639,
- 4031, 4087, 4095, 585, 10617, 8539, 4731, 4187, 9376, 3095,
-
- 9220, 10095, 10220, 1460, 10742, 12068, 1724, 5513, 11321, 6884,
- 2739, 5658, 6075, 4379, 11159, 10372, 8504, 4726, 9453, 3106,
- 7466, 11600, 10435, 8513, 9994, 8450, 9985, 3182, 10988, 8592,
- 2983, 9204, 4826, 2445, 5616, 6069, 867, 3635, 5786, 11360,
- 5134, 2489, 10889, 12089, 1727, 7269, 2794, 9177, 1311, 5454,
- 9557, 6632, 2703, 9164, 10087, 1441, 3717, 531, 3587, 2268,
- 324, 5313, 759, 1864, 5533, 2546, 7386, 9833, 8427, 4715,
- 11207, 1601, 7251, 4547, 11183, 12131, 1733, 10781, 10318, 1474,
- 10744, 5046, 4232, 11138, 10369, 6748, 964, 7160, 4534, 7670,
- 8118, 8182, 4680, 11202, 6867, 981, 8918, 1274, 182, 26,
-
- 7026, 8026, 11680, 12202, 10521, 1503, 7237, 4545, 5916, 9623,
- 8397, 11733, 10454, 3249, 9242, 6587, 941, 1890, 270, 10572,
- 6777, 9746, 6659, 6218, 6155, 6146, 878, 1881, 7291, 11575,
- 12187, 1741, 7271, 8061, 11685, 6936, 4502, 9421, 4857, 4205,
- 7623, 1089, 10689, 1527, 8996, 10063, 11971, 10488, 6765, 2722,
- 3900, 9335, 11867, 6962, 11528, 5158, 4248, 4118, 5855, 2592,
- 5637, 6072, 2623, 7397, 8079, 9932, 4930, 5971, 853, 3633,
- 519, 8852, 11798, 3441, 11025, 1575, 225, 8810, 11792, 12218,
- 3501, 9278, 3081, 9218, 4828, 7712, 8124, 11694, 12204, 3499,
- 4011, 573, 3593, 5780, 7848, 9899, 10192, 1456, 208, 7052,
-
- 2763, 7417, 11593, 10434, 12024, 8740, 11782, 10461, 3250, 5731,
- 7841, 9898, 1414, 202, 3540, 7528, 2831, 2160, 10842, 5060,
- 4234, 4116, 588, 84
-};
-
-/**
- * Bit-reversed indices for n = 1024
- */
-static uint16_t rev_1024[] = {
- 0, 512, 256, 768, 128, 640, 384, 896, 64, 576,
- 320, 832, 192, 704, 448, 960, 32, 544, 288, 800,
- 160, 672, 416, 928, 96, 608, 352, 864, 224, 736,
- 480, 992, 16, 528, 272, 784, 144, 656, 400, 912,
- 80, 592, 336, 848, 208, 720, 464, 976, 48, 560,
- 304, 816, 176, 688, 432, 944, 112, 624, 368, 880,
- 240, 752, 496, 1008, 8, 520, 264, 776, 136, 648,
- 392, 904, 72, 584, 328, 840, 200, 712, 456, 968,
- 40, 552, 296, 808, 168, 680, 424, 936, 104, 616,
- 360, 872, 232, 744, 488, 1000, 24, 536, 280, 792,
-
- 152, 664, 408, 920, 88, 600, 344, 856, 216, 728,
- 472, 984, 56, 568, 312, 824, 184, 696, 440, 952,
- 120, 632, 376, 888, 248, 760, 504, 1016, 4, 516,
- 260, 772, 132, 644, 388, 900, 68, 580, 324, 836,
- 196, 708, 452, 964, 36, 548, 292, 804, 164, 676,
- 420, 932, 100, 612, 356, 868, 228, 740, 484, 996,
- 20, 532, 276, 788, 148, 660, 404, 916, 84, 596,
- 340, 852, 212, 724, 468, 980, 52, 564, 308, 820,
- 180, 692, 436, 948, 116, 628, 372, 884, 244, 756,
- 500, 1012, 12, 524, 268, 780, 140, 652, 396, 908,
-
- 76, 588, 332, 844, 204, 716, 460, 972, 44, 556,
- 300, 812, 172, 684, 428, 940, 108, 620, 364, 876,
- 236, 748, 492, 1004, 28, 540, 284, 796, 156, 668,
- 412, 924, 92, 604, 348, 860, 220, 732, 476, 988,
- 60, 572, 316, 828, 188, 700, 444, 956, 124, 636,
- 380, 892, 252, 764, 508, 1020, 2, 514, 258, 770,
- 130, 642, 386, 898, 66, 578, 322, 834, 194, 706,
- 450, 962, 34, 546, 290, 802, 162, 674, 418, 930,
- 98, 610, 354, 866, 226, 738, 482, 994, 18, 530,
- 274, 786, 146, 658, 402, 914, 82, 594, 338, 850,
-
- 210, 722, 466, 978, 50, 562, 306, 818, 178, 690,
- 434, 946, 114, 626, 370, 882, 242, 754, 498, 1010,
- 10, 522, 266, 778, 138, 650, 394, 906, 74, 586,
- 330, 842, 202, 714, 458, 970, 42, 554, 298, 810,
- 170, 682, 426, 938, 106, 618, 362, 874, 234, 746,
- 490, 1002, 26, 538, 282, 794, 154, 666, 410, 922,
- 90, 602, 346, 858, 218, 730, 474, 986, 58, 570,
- 314, 826, 186, 698, 442, 954, 122, 634, 378, 890,
- 250, 762, 506, 1018, 6, 518, 262, 774, 134, 646,
- 390, 902, 70, 582, 326, 838, 198, 710, 454, 966,
-
- 38, 550, 294, 806, 166, 678, 422, 934, 102, 614,
- 358, 870, 230, 742, 486, 998, 22, 534, 278, 790,
- 150, 662, 406, 918, 86, 598, 342, 854, 214, 726,
- 470, 982, 54, 566, 310, 822, 182, 694, 438, 950,
- 118, 630, 374, 886, 246, 758, 502, 1014, 14, 526,
- 270, 782, 142, 654, 398, 910, 78, 590, 334, 846,
- 206, 718, 462, 974, 46, 558, 302, 814, 174, 686,
- 430, 942, 110, 622, 366, 878, 238, 750, 494, 1006,
- 30, 542, 286, 798, 158, 670, 414, 926, 94, 606,
- 350, 862, 222, 734, 478, 990, 62, 574, 318, 830,
-
- 190, 702, 446, 958, 126, 638, 382, 894, 254, 766,
- 510, 1022, 1, 513, 257, 769, 129, 641, 385, 897,
- 65, 577, 321, 833, 193, 705, 449, 961, 33, 545,
- 289, 801, 161, 673, 417, 929, 97, 609, 353, 865,
- 225, 737, 481, 993, 17, 529, 273, 785, 145, 657,
- 401, 913, 81, 593, 337, 849, 209, 721, 465, 977,
- 49, 561, 305, 817, 177, 689, 433, 945, 113, 625,
- 369, 881, 241, 753, 497, 1009, 9, 521, 265, 777,
- 137, 649, 393, 905, 73, 585, 329, 841, 201, 713,
- 457, 969, 41, 553, 297, 809, 169, 681, 425, 937,
-
- 105, 617, 361, 873, 233, 745, 489, 1001, 25, 537,
- 281, 793, 153, 665, 409, 921, 89, 601, 345, 857,
- 217, 729, 473, 985, 57, 569, 313, 825, 185, 697,
- 441, 953, 121, 633, 377, 889, 249, 761, 505, 1017,
- 5, 517, 261, 773, 133, 645, 389, 901, 69, 581,
- 325, 837, 197, 709, 453, 965, 37, 549, 293, 805,
- 165, 677, 421, 933, 101, 613, 357, 869, 229, 741,
- 485, 997, 21, 533, 277, 789, 149, 661, 405, 917,
- 85, 597, 341, 853, 213, 725, 469, 981, 53, 565,
- 309, 821, 181, 693, 437, 949, 117, 629, 373, 885,
-
- 245, 757, 501, 1013, 13, 525, 269, 781, 141, 653,
- 397, 909, 77, 589, 333, 845, 205, 717, 461, 973,
- 45, 557, 301, 813, 173, 685, 429, 941, 109, 621,
- 365, 877, 237, 749, 493, 1005, 29, 541, 285, 797,
- 157, 669, 413, 925, 93, 605, 349, 861, 221, 733,
- 477, 989, 61, 573, 317, 829, 189, 701, 445, 957,
- 125, 637, 381, 893, 253, 765, 509, 1021, 3, 515,
- 259, 771, 131, 643, 387, 899, 67, 579, 323, 835,
- 195, 707, 451, 963, 35, 547, 291, 803, 163, 675,
- 419, 931, 99, 611, 355, 867, 227, 739, 483, 995,
-
- 19, 531, 275, 787, 147, 659, 403, 915, 83, 595,
- 339, 851, 211, 723, 467, 979, 51, 563, 307, 819,
- 179, 691, 435, 947, 115, 627, 371, 883, 243, 755,
- 499, 1011, 11, 523, 267, 779, 139, 651, 395, 907,
- 75, 587, 331, 843, 203, 715, 459, 971, 43, 555,
- 299, 811, 171, 683, 427, 939, 107, 619, 363, 875,
- 235, 747, 491, 1003, 27, 539, 283, 795, 155, 667,
- 411, 923, 91, 603, 347, 859, 219, 731, 475, 987,
- 59, 571, 315, 827, 187, 699, 443, 955, 123, 635,
- 379, 891, 251, 763, 507, 1019, 7, 519, 263, 775,
-
- 135, 647, 391, 903, 71, 583, 327, 839, 199, 711,
- 455, 967, 39, 551, 295, 807, 167, 679, 423, 935,
- 103, 615, 359, 871, 231, 743, 487, 999, 23, 535,
- 279, 791, 151, 663, 407, 919, 87, 599, 343, 855,
- 215, 727, 471, 983, 55, 567, 311, 823, 183, 695,
- 439, 951, 119, 631, 375, 887, 247, 759, 503, 1015,
- 15, 527, 271, 783, 143, 655, 399, 911, 79, 591,
- 335, 847, 207, 719, 463, 975, 47, 559, 303, 815,
- 175, 687, 431, 943, 111, 623, 367, 879, 239, 751,
- 495, 1007, 31, 543, 287, 799, 159, 671, 415, 927,
-
- 95, 607, 351, 863, 223, 735, 479, 991, 63, 575,
- 319, 831, 191, 703, 447, 959, 127, 639, 383, 895,
- 255, 767, 511, 1023
-};
-
-bliss_fft_params_t bliss_fft_12289_1024 = {
- 12289, 12287, 18, 3186, (1<<18)-1, 1024, 12277, 10,
- wr_12289_1024, wf_12289_1024, wi_12289_1024, 1, rev_1024
-};
-
-/**
- * FFT phase shift and scaling inverse transform for q = 12289 and n = 512
- */
-static uint16_t wi_12289_512[] = {
- 12265, 6771, 11424, 9011, 6203, 11914, 9021, 6454, 7154, 146,
- 11038, 4238, 5604, 10397, 11498, 3495, 7846, 7684, 1160, 4538,
- 845, 2776, 3317, 5836, 6389, 11667, 6508, 1136, 11309, 12269,
- 11787, 9520, 5461, 3121, 5832, 1373, 1282, 10058, 4218, 5102,
- 7628, 4670, 6616, 1389, 9057, 2442, 2307, 5063, 7878, 10945,
- 10506, 716, 767, 3276, 3578, 1327, 5043, 7376, 8176, 3678,
- 3837, 6599, 4649, 4860, 11385, 9261, 189, 3515, 8348, 10453,
- 7988, 1417, 7302, 1403, 2035, 8067, 2171, 6565, 11169, 8755,
- 4693, 10880, 2730, 7078, 3154, 10347, 10243, 2717, 3065, 9342,
- 3451, 1826, 4050, 3343, 1573, 6302, 881, 11053, 10759, 10753,
-
- 3229, 6085, 11410, 3744, 578, 12050, 7519, 3163, 9344, 5959,
- 874, 2275, 1802, 10821, 2478, 10584, 216, 506, 7785, 4924,
- 5618, 3375, 4834, 3359, 9348, 10975, 11259, 11014, 11009, 4739,
- 7119, 5412, 3120, 4578, 1849, 8314, 4684, 11883, 7014, 8921,
- 3944, 5598, 2873, 2065, 8820, 180, 4518, 343, 7, 8778,
- 8957, 12221, 751, 7790, 11194, 3238, 5082, 7126, 1901, 12077,
- 4510, 2600, 3815, 3589, 2832, 12096, 3758, 5845, 5386, 7383,
- 4665, 346, 3769, 7350, 150, 3765, 2334, 2054, 7315, 5416,
- 8136, 2674, 10588, 5232, 10891, 4235, 1842, 11825, 8016, 11951,
- 6263, 1131, 5039, 2360, 10080, 7228, 6919, 392, 8, 10032,
-
- 8481, 5189, 6125, 125, 9282, 1945, 5808, 8144, 417, 6780,
- 10421, 4727, 4360, 11124, 1481, 1535, 7806, 6680, 7911, 3171,
- 7087, 2151, 6063, 8400, 1927, 7814, 4423, 4103, 8360, 923,
- 2276, 3056, 10345, 7735, 3669, 4840, 10883, 6492, 5650, 6636,
- 1891, 11826, 9270, 11475, 11520, 6505, 9663, 448, 8787, 7954,
- 7937, 11197, 7000, 3654, 10608, 5734, 1371, 11063, 11010, 5993,
- 6643, 10669, 8494, 9202, 12226, 7021, 5410, 612, 5530, 3624,
- 9855, 7725, 3418, 9600, 7469, 1908, 8566, 1178, 2532, 4566,
- 11379, 1737, 3045, 8840, 682, 7287, 7171, 9175, 2946, 7584,
- 10939, 2982, 3572, 6092, 7899, 412, 510, 512, 3020, 2068,
-
- 293, 11041, 8000, 4176, 1590, 3042, 5078, 2110, 3805, 3338,
- 7592, 8682, 11463, 8761, 12217, 8024, 9694, 2455, 6320, 11164,
- 2485, 7073, 9173, 438, 8536, 425, 4523, 6613, 9916, 10485,
- 11249, 10763, 3480, 1325, 2535, 8328, 9951, 5219, 6878, 10423,
- 7235, 3408, 9349, 12229, 10783, 3982, 4094, 9363, 5207, 4119,
- 3846, 5596, 365, 3017, 10595, 1721, 7559, 4167, 2593, 7326,
- 6921, 2900, 11345, 8257, 6940, 2148, 2301, 9828, 10734, 3981,
- 2840, 9839, 12239, 11034, 11511, 7508, 1658, 2291, 9577, 3205,
- 567, 10545, 466, 6781, 11675, 4251, 9617, 4209, 6105, 11912,
- 6513, 7406, 8929, 1687, 1790, 8062, 8190, 8945, 9462, 6463,
-
- 6151, 8151, 9195, 3448, 10353, 5478, 12150, 10029, 4719, 6617,
- 2643, 8581, 7699, 7681, 9687, 5966, 9652, 11232, 1734, 11572,
- 10268, 9489, 3454, 5588, 2622, 6825, 5406, 7885, 7434, 7174,
- 648, 1518, 11066, 2483, 4565, 10125, 2213, 10077, 3466, 8347,
- 9199, 8464, 8449, 1928, 9068, 3947, 9360, 1445, 5547, 364,
- 1763, 11071, 8753, 2185, 11832, 4505, 8619, 6195, 1882, 540,
- 1265, 1029, 21, 1756, 2293, 12085, 2253, 11081, 9004, 9714,
- 2957, 9089, 5703, 11653, 1241, 7800, 11445, 10767, 8496, 11710,
- 11274, 5246, 3869, 9860, 1706, 1038, 11307, 9761, 450, 11295,
- 7002, 6162, 9656, 3959, 12119, 8022, 7186, 3407, 8095, 416,
-
- 5526, 10897, 11759, 11275, 6500, 3393, 2828, 7080, 5662, 9395,
- 8468, 1176
-};
-
-/**
- * Bit-reversed indices for n = 512
- */
-static uint16_t rev_512[] = {
- 0, 256, 128, 384, 64, 320, 192, 448, 32, 288,
- 160, 416, 96, 352, 224, 480, 16, 272, 144, 400,
- 80, 336, 208, 464, 48, 304, 176, 432, 112, 368,
- 240, 496, 8, 264, 136, 392, 72, 328, 200, 456,
- 40, 296, 168, 424, 104, 360, 232, 488, 24, 280,
- 152, 408, 88, 344, 216, 472, 56, 312, 184, 440,
- 120, 376, 248, 504, 4, 260, 132, 388, 68, 324,
- 196, 452, 36, 292, 164, 420, 100, 356, 228, 484,
- 20, 276, 148, 404, 84, 340, 212, 468, 52, 308,
- 180, 436, 116, 372, 244, 500, 12, 268, 140, 396,
-
- 76, 332, 204, 460, 44, 300, 172, 428, 108, 364,
- 236, 492, 28, 284, 156, 412, 92, 348, 220, 476,
- 60, 316, 188, 444, 124, 380, 252, 508, 2, 258,
- 130, 386, 66, 322, 194, 450, 34, 290, 162, 418,
- 98, 354, 226, 482, 18, 274, 146, 402, 82, 338,
- 210, 466, 50, 306, 178, 434, 114, 370, 242, 498,
- 10, 266, 138, 394, 74, 330, 202, 458, 42, 298,
- 170, 426, 106, 362, 234, 490, 26, 282, 154, 410,
- 90, 346, 218, 474, 58, 314, 186, 442, 122, 378,
- 250, 506, 6, 262, 134, 390, 70, 326, 198, 454,
-
- 38, 294, 166, 422, 102, 358, 230, 486, 22, 278,
- 150, 406, 86, 342, 214, 470, 54, 310, 182, 438,
- 118, 374, 246, 502, 14, 270, 142, 398, 78, 334,
- 206, 462, 46, 302, 174, 430, 110, 366, 238, 494,
- 30, 286, 158, 414, 94, 350, 222, 478, 62, 318,
- 190, 446, 126, 382, 254, 510, 1, 257, 129, 385,
- 65, 321, 193, 449, 33, 289, 161, 417, 97, 353,
- 225, 481, 17, 273, 145, 401, 81, 337, 209, 465,
- 49, 305, 177, 433, 113, 369, 241, 497, 9, 265,
- 137, 393, 73, 329, 201, 457, 41, 297, 169, 425,
-
- 105, 361, 233, 489, 25, 281, 153, 409, 89, 345,
- 217, 473, 57, 313, 185, 441, 121, 377, 249, 505,
- 5, 261, 133, 389, 69, 325, 197, 453, 37, 293,
- 165, 421, 101, 357, 229, 485, 21, 277, 149, 405,
- 85, 341, 213, 469, 53, 309, 181, 437, 117, 373,
- 245, 501, 13, 269, 141, 397, 77, 333, 205, 461,
- 45, 301, 173, 429, 109, 365, 237, 493, 29, 285,
- 157, 413, 93, 349, 221, 477, 61, 317, 189, 445,
- 125, 381, 253, 509, 3, 259, 131, 387, 67, 323,
- 195, 451, 35, 291, 163, 419, 99, 355, 227, 483,
-
- 19, 275, 147, 403, 83, 339, 211, 467, 51, 307,
- 179, 435, 115, 371, 243, 499, 11, 267, 139, 395,
- 75, 331, 203, 459, 43, 299, 171, 427, 107, 363,
- 235, 491, 27, 283, 155, 411, 91, 347, 219, 475,
- 59, 315, 187, 443, 123, 379, 251, 507, 7, 263,
- 135, 391, 71, 327, 199, 455, 39, 295, 167, 423,
- 103, 359, 231, 487, 23, 279, 151, 407, 87, 343,
- 215, 471, 55, 311, 183, 439, 119, 375, 247, 503,
- 15, 271, 143, 399, 79, 335, 207, 463, 47, 303,
- 175, 431, 111, 367, 239, 495, 31, 287, 159, 415,
-
- 95, 351, 223, 479, 63, 319, 191, 447, 127, 383,
- 255, 511
-};
-
-bliss_fft_params_t bliss_fft_12289_512 = {
- 12289, 12287, 18, 3186, (1<<18)-1, 512, 12265, 9,
- wr_12289_1024, wf_12289_1024, wi_12289_512, 2, rev_512
-};
-
-/**
- * FFT twiddle factors in Montgomery form for q = 17 and n = 8
- */
-static uint16_t wr_17_8[] = { 15, 16, 8, 4, 2, 1, 9, 13, 15 };
-
-/**
- * FFT phase shift in forward transform for q = 17 and n = 8
- */
-static uint16_t wf_17_8[] = { 4, 12, 2, 6, 1, 3, 9, 10 };
-
-/**
- * FFT phase shift and scaling inverse transform for q = 17 and n = 8
- */
-static uint16_t wi_17_8[] = { 15, 5, 13, 10, 9, 3, 1, 6 };
-
-/**
- * Bit-reversed indices for n = 8
- */
-static uint16_t rev_8[] = { 0, 4, 2, 6, 1, 5, 3, 7 };
-
-bliss_fft_params_t bliss_fft_17_8 = {
- 17, 15, 5, 4, (1<<5)-1, 8, 15, 3, wr_17_8, wf_17_8, wi_17_8, 1, rev_8
-};
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft_params.h b/src/libstrongswan/plugins/bliss/bliss_fft_params.h
deleted file mode 100644
index 0ed49b2cc..000000000
--- a/src/libstrongswan/plugins/bliss/bliss_fft_params.h
+++ /dev/null
@@ -1,115 +0,0 @@
-/*
- * Copyright (C) 2014-2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
- * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * for more details.
- */
-
-/**
- * @defgroup bliss_fft_params bliss_fft_params
- * @{ @ingroup bliss_p
- */
-
-#ifndef BLISS_FFT_PARAMS_H_
-#define BLISS_FFT_PARAMS_H_
-
-#include <library.h>
-
-typedef struct bliss_fft_params_t bliss_fft_params_t;
-
-/**
- * Defines the parameters for an NTT computed via the FFT algorithm
- */
-struct bliss_fft_params_t {
-
- /**
- * Prime modulus
- */
- uint16_t q;
-
- /**
- * Inverse of Prime modulus (-q_inv * q mod r = 1)
- */
- uint16_t q_inv;
-
- /**
- * Logarithm of Montgomery radix: log2(r)
- */
- uint16_t rlog;
-
- /**
- * Square of Montgomery radix: r^2 mod q
- */
- uint32_t r2;
-
- /**
- * Montgomery radix mask: (1<<rlog) - 1
- */
- uint32_t rmask;
-
- /**
- * Size of the FFT with the condition k * n = q-1
- */
- uint16_t n;
-
- /**
- * Inverse of n mod q used for normalization of the FFT
- */
- uint16_t n_inv;
-
- /**
- * Number of FFT stages stages = log2(n)
- */
- uint16_t stages;
-
- /**
- * FFT twiddle factors (n-th roots of unity) in Montgomery form
- */
- uint16_t *wr;
-
- /**
- * FFT phase shift (2n-th roots of unity) in forward transform
- */
- uint16_t *wf;
-
- /**
- * FFT phase shift (2n-th roots of unity) and scaling in inverse transform
- */
- uint16_t *wi;
-
- /**
- * Subsampling of FFT twiddle factors table
- */
- uint16_t s;
-
- /**
- * FFT bit reversal
- */
- uint16_t *rev;
-
-};
-
-/**
- * FFT parameters for q = 12289 and n = 1024
- */
-extern bliss_fft_params_t bliss_fft_12289_1024;
-
-/**
- * FFT parameters for q = 12289 and n = 512
- */
-extern bliss_fft_params_t bliss_fft_12289_512;
-
-/**
- * FFT parameters for q = 17 and n = 8
- */
-extern bliss_fft_params_t bliss_fft_17_8;
-
-#endif /** BLISS_FFT_PARAMS_H_ @}*/
diff --git a/src/libstrongswan/plugins/bliss/bliss_param_set.c b/src/libstrongswan/plugins/bliss/bliss_param_set.c
index 3781a588f..80a7c0d28 100644
--- a/src/libstrongswan/plugins/bliss/bliss_param_set.c
+++ b/src/libstrongswan/plugins/bliss/bliss_param_set.c
@@ -131,7 +131,7 @@ static bliss_param_set_t bliss_param_sets[] = {
.q2_inv = 6145,
.n = 512,
.n_bits = 9,
- .fft_params = &bliss_fft_12289_512,
+ .fft_params = &ntt_fft_12289_512,
.non_zero1 = 154,
.non_zero2 = 0,
.kappa = 23,
@@ -161,7 +161,7 @@ static bliss_param_set_t bliss_param_sets[] = {
.q2_inv = 6145,
.n = 512,
.n_bits = 9,
- .fft_params = &bliss_fft_12289_512,
+ .fft_params = &ntt_fft_12289_512,
.non_zero1 = 216,
.non_zero2 = 16,
.kappa = 30,
@@ -191,7 +191,7 @@ static bliss_param_set_t bliss_param_sets[] = {
.q2_inv = 6145,
.n = 512,
.n_bits = 9,
- .fft_params = &bliss_fft_12289_512,
+ .fft_params = &ntt_fft_12289_512,
.non_zero1 = 231,
.non_zero2 = 31,
.kappa = 39,
@@ -221,7 +221,7 @@ static bliss_param_set_t bliss_param_sets[] = {
.q2_inv = 6145,
.n = 512,
.n_bits = 9,
- .fft_params = &bliss_fft_12289_512,
+ .fft_params = &ntt_fft_12289_512,
.non_zero1 = 154,
.non_zero2 = 0,
.kappa = 23,
@@ -251,7 +251,7 @@ static bliss_param_set_t bliss_param_sets[] = {
.q2_inv = 6145,
.n = 512,
.n_bits = 9,
- .fft_params = &bliss_fft_12289_512,
+ .fft_params = &ntt_fft_12289_512,
.non_zero1 = 216,
.non_zero2 = 16,
.kappa = 30,
@@ -281,7 +281,7 @@ static bliss_param_set_t bliss_param_sets[] = {
.q2_inv = 6145,
.n = 512,
.n_bits = 9,
- .fft_params = &bliss_fft_12289_512,
+ .fft_params = &ntt_fft_12289_512,
.non_zero1 = 231,
.non_zero2 = 31,
.kappa = 39,
diff --git a/src/libstrongswan/plugins/bliss/bliss_param_set.h b/src/libstrongswan/plugins/bliss/bliss_param_set.h
index 33a8009ff..19fdc4873 100644
--- a/src/libstrongswan/plugins/bliss/bliss_param_set.h
+++ b/src/libstrongswan/plugins/bliss/bliss_param_set.h
@@ -24,7 +24,7 @@
typedef enum bliss_param_set_id_t bliss_param_set_id_t;
typedef struct bliss_param_set_t bliss_param_set_t;
-#include "bliss_fft_params.h"
+#include "ntt_fft_params.h"
#include "bliss_huffman_code.h"
#include <library.h>
@@ -93,7 +93,7 @@ struct bliss_param_set_t {
/**
* FFT parameters
*/
- bliss_fft_params_t *fft_params;
+ ntt_fft_params_t *fft_params;
/**
* Number of [-1, +1] secret key coefficients
diff --git a/src/libstrongswan/plugins/bliss/bliss_private_key.c b/src/libstrongswan/plugins/bliss/bliss_private_key.c
index 68c0ea2fa..d4cc000dd 100644
--- a/src/libstrongswan/plugins/bliss/bliss_private_key.c
+++ b/src/libstrongswan/plugins/bliss/bliss_private_key.c
@@ -20,8 +20,8 @@
#include "bliss_sampler.h"
#include "bliss_signature.h"
#include "bliss_bitpacker.h"
-#include "bliss_fft.h"
-#include "bliss_reduce.h"
+#include "ntt_fft.h"
+#include "ntt_fft_reduce.h"
#include <crypto/mgf1/mgf1_bitspender.h>
#include <asn1/asn1.h>
@@ -169,7 +169,7 @@ static void greedy_sc(int8_t *s1, int8_t *s2, int n, uint16_t *c_indices,
static bool sign_bliss(private_bliss_private_key_t *this, hash_algorithm_t alg,
chunk_t data, chunk_t *signature)
{
- bliss_fft_t *fft;
+ ntt_fft_t *fft;
bliss_signature_t *sig;
bliss_sampler_t *sampler = NULL;
rng_t *rng;
@@ -247,7 +247,7 @@ static bool sign_bliss(private_bliss_private_key_t *this, hash_algorithm_t alg,
y2 = z2;
ud = z2d;
- fft = bliss_fft_create(this->set->fft_params);
+ fft = ntt_fft_create(this->set->fft_params);
/* Use of the enhanced BLISS-B signature algorithm? */
switch (this->set->id)
@@ -343,7 +343,7 @@ static bool sign_bliss(private_bliss_private_key_t *this, hash_algorithm_t alg,
for (i = 0; i < n; i++)
{
- ay[i] = bliss_mreduce(this->Ar[i] * ay[i], this->set->fft_params);
+ ay[i] = ntt_fft_mreduce(this->Ar[i] * ay[i], this->set->fft_params);
}
fft->transform(fft, ay, ay, TRUE);
@@ -819,11 +819,11 @@ static uint32_t invert(private_bliss_private_key_t *this, uint32_t x)
}
for (i = 1; i <= i_max; i++)
{
- x2 = bliss_mreduce(x2 * x2, this->set->fft_params);
+ x2 = ntt_fft_mreduce(x2 * x2, this->set->fft_params);
if (q2 & (1 << i))
{
- x1 = bliss_mreduce(x1 * x2, this->set->fft_params);
+ x1 = ntt_fft_mreduce(x1 * x2, this->set->fft_params);
}
}
@@ -1008,7 +1008,7 @@ bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args)
uint16_t q;
bool success = FALSE;
bliss_param_set_t *set;
- bliss_fft_t *fft;
+ ntt_fft_t *fft;
rng_t *rng;
while (TRUE)
@@ -1069,7 +1069,7 @@ bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args)
this->set = set;
/* We derive the public key from the private key using the FFT */
- fft = bliss_fft_create(set->fft_params);
+ fft = ntt_fft_create(set->fft_params);
/* Some vectors needed to derive the publi key */
S1 = malloc(n * sizeof(uint32_t));
@@ -1113,8 +1113,8 @@ bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args)
break;
}
this->Ar[i] = invert(this, S1[i]);
- this->Ar[i] = bliss_mreduce(S2[i] * this->Ar[i], set->fft_params);
- this->A[i] = bliss_mreduce(this->Ar[i], set->fft_params);
+ this->Ar[i] = ntt_fft_mreduce(S2[i] * this->Ar[i], set->fft_params);
+ this->A[i] = ntt_fft_mreduce(this->Ar[i], set->fft_params);
}
}
while (!success && trials < SECRET_KEY_TRIALS_MAX);
@@ -1131,7 +1131,7 @@ bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args)
{
DBG4(DBG_LIB, "%4d %3d %3d %5u %5u %5u %5u",
i, this->s1[i], this->s2[i],
- bliss_mreduce(a[i], set->fft_params),
+ ntt_fft_mreduce(a[i], set->fft_params),
S1[i], S2[i], this->A[i]);
}
}
@@ -1265,8 +1265,8 @@ bliss_private_key_t *bliss_private_key_load(key_type_t type, va_list args)
for (i = 0; i < this->set->n; i++)
{
- this->Ar[i] = bliss_mreduce(this->A[i] * r2,
- this->set->fft_params);
+ this->Ar[i] = ntt_fft_mreduce(this->A[i] * r2,
+ this->set->fft_params);
}
break;
case PRIV_KEY_SECRET1:
diff --git a/src/libstrongswan/plugins/bliss/bliss_public_key.c b/src/libstrongswan/plugins/bliss/bliss_public_key.c
index 2f63fdb4d..1016aec0d 100644
--- a/src/libstrongswan/plugins/bliss/bliss_public_key.c
+++ b/src/libstrongswan/plugins/bliss/bliss_public_key.c
@@ -16,8 +16,8 @@
#include "bliss_public_key.h"
#include "bliss_signature.h"
#include "bliss_bitpacker.h"
-#include "bliss_fft.h"
-#include "bliss_reduce.h"
+#include "ntt_fft.h"
+#include "ntt_fft_reduce.h"
#include "bliss_utils.h"
#include <asn1/asn1.h>
@@ -77,7 +77,7 @@ static bool verify_bliss(private_bliss_public_key_t *this, hash_algorithm_t alg,
chunk_t data_hash;
hasher_t *hasher;
hash_algorithm_t oracle_alg;
- bliss_fft_t *fft;
+ ntt_fft_t *fft;
bliss_signature_t *sig;
bool success = FALSE;
@@ -126,12 +126,12 @@ static bool verify_bliss(private_bliss_public_key_t *this, hash_algorithm_t alg,
{
az[i] = z1[i] < 0 ? q + z1[i] : z1[i];
}
- fft = bliss_fft_create(this->set->fft_params);
+ fft = ntt_fft_create(this->set->fft_params);
fft->transform(fft, az, az, FALSE);
for (i = 0; i < n; i++)
{
- az[i] = bliss_mreduce(this->Ar[i] * az[i], this->set->fft_params);
+ az[i] = ntt_fft_mreduce(this->Ar[i] * az[i], this->set->fft_params);
}
fft->transform(fft, az, az, TRUE);
@@ -393,8 +393,8 @@ bliss_public_key_t *bliss_public_key_load(key_type_t type, va_list args)
for (i = 0; i < this->set->n; i++)
{
- this->Ar[i] = bliss_mreduce(this->A[i] * r2,
- this->set->fft_params);
+ this->Ar[i] = ntt_fft_mreduce(this->A[i] * r2,
+ this->set->fft_params);
}
break;
}
diff --git a/src/libstrongswan/plugins/bliss/bliss_reduce.h b/src/libstrongswan/plugins/bliss/bliss_reduce.h
deleted file mode 100644
index 2a53d9a7a..000000000
--- a/src/libstrongswan/plugins/bliss/bliss_reduce.h
+++ /dev/null
@@ -1,42 +0,0 @@
-/*
- * Copyright (C) 2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
- * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * for more details.
- */
-
-/**
- * @defgroup bliss_fft bliss_fft
- * @{ @ingroup bliss_p
- */
-
-#ifndef BLISS_REDUCE_H_
-#define BLISS_REDUCE_H_
-
-#include "bliss_fft_params.h"
-
-/**
- * Montgomery Reduction
- *
- * Montgomery, P. L. Modular multiplication without trial division.
- * Mathematics of Computation 44, 170 (1985), 519–521.
- */
-static inline uint32_t bliss_mreduce(uint32_t x, bliss_fft_params_t *p)
-{
- uint32_t m, t;
-
- m = (x * p->q_inv) & p->rmask;
- t = (x + m * p->q) >> p->rlog;
-
- return (t < p->q) ? t : t - p->q;
-}
-
-#endif /** BLISS_REDUCE_H_ @}*/
diff --git a/src/libstrongswan/plugins/bliss/tests/Makefile.am b/src/libstrongswan/plugins/bliss/tests/Makefile.am
index bd87753f5..1ec8d551f 100644
--- a/src/libstrongswan/plugins/bliss/tests/Makefile.am
+++ b/src/libstrongswan/plugins/bliss/tests/Makefile.am
@@ -3,7 +3,6 @@ TESTS = bliss_tests
check_PROGRAMS = $(TESTS)
bliss_tests_SOURCES = \
- suites/test_bliss_fft.c \
suites/test_bliss_bitpacker.c \
suites/test_bliss_huffman.c \
suites/test_bliss_keys.c \
@@ -15,6 +14,7 @@ bliss_tests_SOURCES = \
bliss_tests_CFLAGS = \
-I$(top_srcdir)/src/libstrongswan \
-I$(top_srcdir)/src/libstrongswan/tests \
+ -I$(top_srcdir)/src/libstrongswan/math/libnttfft \
-I$(top_srcdir)/src/libstrongswan/plugins/bliss \
-DPLUGINDIR=\""$(abs_top_builddir)/src/libstrongswan/plugins\"" \
-DPLUGINS=\""${s_plugins}\"" \
@@ -24,4 +24,5 @@ bliss_tests_LDFLAGS = @COVERAGE_LDFLAGS@
bliss_tests_LDADD = \
$(top_builddir)/src/libstrongswan/libstrongswan.la \
$(top_builddir)/src/libstrongswan/tests/libtest.la \
+ $(top_builddir)/src/libstrongswan/math/libnttfft/libnttfft.la \
../libbliss.la
diff --git a/src/libstrongswan/plugins/bliss/tests/bliss_tests.h b/src/libstrongswan/plugins/bliss/tests/bliss_tests.h
index f0959cc08..61f37d5a1 100644
--- a/src/libstrongswan/plugins/bliss/tests/bliss_tests.h
+++ b/src/libstrongswan/plugins/bliss/tests/bliss_tests.h
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014-2015 Andreas Steffen
+ * Copyright (C) 2014-2016 Andreas Steffen
* HSR Hochschule fuer Technik Rapperswil
*
* This program is free software; you can redistribute it and/or modify it
@@ -13,7 +13,6 @@
* for more details.
*/
-TEST_SUITE(bliss_fft_suite_create)
TEST_SUITE(bliss_bitpacker_suite_create)
TEST_SUITE(bliss_huffman_suite_create)
TEST_SUITE(bliss_keys_suite_create)
diff --git a/src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c b/src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c
deleted file mode 100644
index d1328cbdc..000000000
--- a/src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c
+++ /dev/null
@@ -1,154 +0,0 @@
-/*
- * Copyright (C) 2014-2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
- * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * for more details.
- */
-
-#include "test_suite.h"
-
-#include <bliss_fft.h>
-#include <bliss_reduce.h>
-
-#include <time.h>
-
-static bliss_fft_params_t *fft_params[] = {
- &bliss_fft_17_8,
- &bliss_fft_12289_512,
- &bliss_fft_12289_1024
-};
-
-START_TEST(test_bliss_fft_impulse)
-{
- bliss_fft_t *fft;
- uint16_t n = fft_params[_i]->n;
- uint32_t rq = (1 << fft_params[_i]->rlog) % fft_params[_i]->q;
- uint32_t x[n], X[n];
- int i;
-
- for (i = 0; i < n; i++)
- {
- x[i] = 0;
- }
- x[0] = 1;
-
- fft = bliss_fft_create(fft_params[_i]);
- fft->transform(fft, x, X, FALSE);
-
- for (i = 0; i < n; i++)
- {
- ck_assert(X[i] == rq);
- }
- fft->transform(fft, X, x, TRUE);
-
- for (i = 0; i < n; i++)
- {
- ck_assert(x[i] == (i == 0));
- }
- fft->destroy(fft);
-}
-END_TEST
-
-START_TEST(test_bliss_fft_wrap)
-{
- bliss_fft_t *fft;
- uint16_t n = fft_params[_i]->n;
- uint16_t q = fft_params[_i]->q;
- uint32_t x[n],y[n], X[n], Y[n];
- int i, j;
-
- for (i = 0; i < n; i++)
- {
- x[i] = i;
- y[i] = 0;
- }
- fft = bliss_fft_create(fft_params[_i]);
- ck_assert(fft->get_size(fft) == n);
- ck_assert(fft->get_modulus(fft) == q);
- fft->transform(fft, x, X, FALSE);
-
- for (j = 0; j < n; j++)
- {
- y[j] = 1;
- fft->transform(fft, y, Y, FALSE);
-
- for (i = 0; i < n; i++)
- {
- Y[i] = bliss_mreduce(X[i] * Y[i], fft_params[_i]);
- }
- fft->transform(fft, Y, Y, TRUE);
-
- for (i = 0; i < n; i++)
- {
- ck_assert(Y[i] == ( i < j ? q - n - i + j : i - j));
- }
- y[j] = 0;
- }
- fft->destroy(fft);
-}
-END_TEST
-
-START_TEST(test_bliss_fft_speed)
-{
- bliss_fft_t *fft;
- struct timespec start, stop;
- int i, m, count = 10000;
- int n = fft_params[_i]->n;
- uint32_t x[n], X[n];
-
- for (i = 0; i < n; i++)
- {
- x[i] = i;
- }
- fft = bliss_fft_create(fft_params[_i]);
-
- clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
- for (m = 0; m < count; m++)
- {
- fft->transform(fft, x, X, FALSE);
- fft->transform(fft, X, x, TRUE);
- }
- clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stop);
-
- DBG0(DBG_LIB, "%d FFT-%d loops in %d ms\n", count, n,
- (stop.tv_nsec - start.tv_nsec) / 1000000 +
- (stop.tv_sec - start.tv_sec) * 1000);
-
- for (i = 0; i < n; i++)
- {
- ck_assert(x[i] == i);
- }
- fft->destroy(fft);
-}
-END_TEST
-
-Suite *bliss_fft_suite_create()
-{
- Suite *s;
- TCase *tc;
-
- s = suite_create("bliss_fft");
-
- tc = tcase_create("impulse");
- tcase_add_loop_test(tc, test_bliss_fft_impulse, 0, countof(fft_params));
- suite_add_tcase(s, tc);
-
- tc = tcase_create("negative_wrap");
- tcase_add_loop_test(tc, test_bliss_fft_wrap, 0, countof(fft_params));
- suite_add_tcase(s, tc);
-
- tc = tcase_create("speed");
- tcase_set_timeout(tc, 10);
- tcase_add_loop_test(tc, test_bliss_fft_speed, 1, countof(fft_params));
- suite_add_tcase(s, tc);
-
- return s;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2025-09-16 21:49:58 +0000