Created libnttfft

This makes Number Theoretic Transforms (NTT) based on the efficient
Fast-Fourier-Transform (FFT) available to multiple plugins.

19 files changed, 258 insertions, 121 deletions

diff --git a/src/libstrongswan/Makefile.am b/src/libstrongswan/Makefile.am
index 965bf7a59..45468786f 100644
--- a/src/libstrongswan/Makefile.am
+++ b/src/libstrongswan/Makefile.am
@@ -221,16 +221,22 @@ $(srcdir)/crypto/proposal/proposal_keywords_static.c:	$(srcdir)/crypto/proposal/
 		$(GPERF) -N proposal_get_token_static -m 10 -C -G -c -t -D < \
 												$(srcdir)/crypto/proposal/proposal_keywords_static.txt > $@
 
-
-# build plugins with their own Makefile
-#######################################
-
 if MONOLITHIC
 SUBDIRS =
 else
 SUBDIRS = .
 endif
 
+# build libnttfft used by some plugins
+######################################
+
+if USE_LIBNTTFFT
+  SUBDIRS += math/libnttfft
+endif
+
+# build plugins with their own Makefile
+#######################################
+
 if USE_AF_ALG
   SUBDIRS += plugins/af_alg
 if MONOLITHIC
@@ -605,7 +611,16 @@ endif
 if MONOLITHIC
   SUBDIRS += .
 endif
+
+# build unit tests
+##################
+
 SUBDIRS += tests
+
+if USE_LIBNTTFFT
+  SUBDIRS += math/libnttfft/tests
+endif
+
 if USE_BLISS
   SUBDIRS += plugins/bliss/tests
 endif
diff --git a/src/libstrongswan/math/libnttfft/Makefile.am b/src/libstrongswan/math/libnttfft/Makefile.am
new file mode 100644
index 000000000..ec98abead
--- /dev/null
+++ b/src/libstrongswan/math/libnttfft/Makefile.am
@@ -0,0 +1,15 @@
+AM_CPPFLAGS = \
+	-I$(top_srcdir)/src/libstrongswan
+
+AM_CFLAGS = \
+	@COVERAGE_CFLAGS@
+
+AM_LDFLAGS = \
+	-no-undefined
+
+ipseclib_LTLIBRARIES = libnttfft.la
+
+libnttfft_la_SOURCES = \
+	ntt_fft_reduce.h ntt_fft.h ntt_fft.c \
+	ntt_fft_params.h ntt_fft_params.c
+
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft.c b/src/libstrongswan/math/libnttfft/ntt_fft.c
index 2355a9f4c..d742c0ac4 100644
--- a/src/libstrongswan/plugins/bliss/bliss_fft.c
+++ b/src/libstrongswan/math/libnttfft/ntt_fft.c
@@ -13,36 +13,36 @@
  * for more details.
  */
 
-#include "bliss_fft.h"
-#include "bliss_reduce.h"
+#include "ntt_fft.h"
+#include "ntt_fft_reduce.h"
 
-typedef struct private_bliss_fft_t private_bliss_fft_t;
+typedef struct private_ntt_fft_t private_ntt_fft_t;
 
 /**
- * Private data structure for bliss_fft_t object
+ * Private data structure for ntt_fft_t object
  */
-struct private_bliss_fft_t {
+struct private_ntt_fft_t {
 
 	/**
 	 * Public interface.
 	 */
-	bliss_fft_t public;
+	ntt_fft_t public;
 
 	/**
 	 * FFT parameter set used as constants
 	 */
-	bliss_fft_params_t *p;
+	ntt_fft_params_t *p;
 
 };
 
-METHOD(bliss_fft_t, get_size, uint16_t,
-	private_bliss_fft_t *this)
+METHOD(ntt_fft_t, get_size, uint16_t,
+	private_ntt_fft_t *this)
 {
 	return this->p->n;
 }
 
-METHOD(bliss_fft_t, get_modulus, uint16_t,
-	private_bliss_fft_t *this)
+METHOD(ntt_fft_t, get_modulus, uint16_t,
+	private_ntt_fft_t *this)
 {
 	return this->p->q;
 }
@@ -56,8 +56,7 @@ METHOD(bliss_fft_t, get_modulus, uint16_t,
  * x[i2] ---|-|--|*|-- x[i2]
  *
  */
-static void butterfly(private_bliss_fft_t *this, uint32_t *x, int i1,int i2,
-															  int iw)
+static void butterfly(private_ntt_fft_t *this, uint32_t *x, int i1,int i2, int iw)
 {
 	uint32_t xp, xm;
 
@@ -68,13 +67,13 @@ static void butterfly(private_bliss_fft_t *this, uint32_t *x, int i1,int i2,
 		xp -= this->p->q;
 	}
 	x[i1] = xp;
-	x[i2] = bliss_mreduce(xm * this->p->wr[iw], this->p);
+	x[i2] = ntt_fft_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)
+static void butterfly_last(private_ntt_fft_t *this, uint32_t *x, int i1)
 {
 	uint32_t xp, xm;
 	int i2 = i1 + 1;
@@ -93,8 +92,8 @@ static void butterfly_last(private_bliss_fft_t *this, uint32_t *x, int i1)
 	x[i2] = xm;
 }
 
-METHOD(bliss_fft_t, transform, void,
-	private_bliss_fft_t *this, uint32_t *a, uint32_t *b, bool inverse)
+METHOD(ntt_fft_t, transform, void,
+	private_ntt_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;
@@ -108,7 +107,7 @@ METHOD(bliss_fft_t, transform, void,
 		/* 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);
+			b[i] = ntt_fft_mreduce(a[i] * this->p->wf[s*i], this->p);
 		}
 	}
 	else if (a != b)
@@ -168,13 +167,13 @@ METHOD(bliss_fft_t, transform, void,
 	{
 		for (i = 0; i < n; i++)
 		{
-			b[i] = bliss_mreduce(b[i] * this->p->wi[i], this->p);
+			b[i] = ntt_fft_mreduce(b[i] * this->p->wi[i], this->p);
 		}
 	}
 }
 
-METHOD(bliss_fft_t, destroy, void,
-	private_bliss_fft_t *this)
+METHOD(ntt_fft_t, destroy, void,
+	private_ntt_fft_t *this)
 {
 	free(this);
 }
@@ -182,9 +181,9 @@ METHOD(bliss_fft_t, destroy, void,
 /**
  * See header.
  */
-bliss_fft_t *bliss_fft_create(bliss_fft_params_t *params)
+ntt_fft_t *ntt_fft_create(ntt_fft_params_t *params)
 {
-	private_bliss_fft_t *this;
+	private_ntt_fft_t *this;
 
 	INIT(this,
 		.public = {
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft.h b/src/libstrongswan/math/libnttfft/ntt_fft.h
index a79edd2be..0054a6c4e 100644
--- a/src/libstrongswan/plugins/bliss/bliss_fft.h
+++ b/src/libstrongswan/math/libnttfft/ntt_fft.h
@@ -14,37 +14,37 @@
  */
 
 /**
- * @defgroup bliss_fft bliss_fft
+ * @defgroup ntt_fft ntt_fft
  * @{ @ingroup bliss_p
  */
 
-#ifndef BLISS_FFT_H_
-#define BLISS_FFT_H_
+#ifndef NTT_FFT_H_
+#define NTT_FFT_H_
 
-#include "bliss_fft_params.h"
+#include "ntt_fft_params.h"
 
 #include <library.h>
 
-typedef struct bliss_fft_t bliss_fft_t;
+typedef struct ntt_fft_t ntt_fft_t;
 
 /**
  * Implements a Number Theoretic Transform (NTT) via the FFT algorithm
  */
-struct bliss_fft_t {
+struct ntt_fft_t {
 
 	/**
 	 * Get the size of the Number Theoretic Transform
 	 *
 	 * @result			Transform size
 	 */
-	uint16_t (*get_size)(bliss_fft_t *this);
+	uint16_t (*get_size)(ntt_fft_t *this);
 
 	/**
 	 * Get the prime modulus of the Number Theoretic Transform
 	 *
 	 * @result			Prime modulus
 	 */
-	uint16_t (*get_modulus)(bliss_fft_t *this);
+	uint16_t (*get_modulus)(ntt_fft_t *this);
 
 	/**
 	 * Compute the [inverse] NTT of a polynomial
@@ -53,19 +53,19 @@ struct bliss_fft_t {
 	 * @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);
+	void (*transform)(ntt_fft_t *this, uint32_t *a, uint32_t *b, bool inverse);
 
 	/**
-	 * Destroy bliss_fft_t object
+	 * Destroy ntt_fft_t object
 	 */
-	void (*destroy)(bliss_fft_t *this);
+	void (*destroy)(ntt_fft_t *this);
 };
 
 /**
- * Create a bliss_fft_t object for a given FFT parameter set
+ * Create a ntt_fft_t object for a given FFT parameter set
  *
  * @param params		FFT parameters
  */
-bliss_fft_t *bliss_fft_create(bliss_fft_params_t *params);
+ntt_fft_t *ntt_fft_create(ntt_fft_params_t *params);
 
-#endif /** BLISS_FFT_H_ @}*/
+#endif /** NTT_FFT_H_ @}*/
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft_params.c b/src/libstrongswan/math/libnttfft/ntt_fft_params.c
index db6abea33..33e78c594 100644
--- a/src/libstrongswan/plugins/bliss/bliss_fft_params.c
+++ b/src/libstrongswan/math/libnttfft/ntt_fft_params.c
@@ -13,7 +13,7 @@
  * for more details.
  */
 
-#include "bliss_fft_params.h"
+#include "ntt_fft_params.h"
 
 /**
  * FFT twiddle factors in Montgomery form for q = 12289 and n = 1024
@@ -491,7 +491,7 @@ static uint16_t rev_1024[] = {
 	 255,  767,  511, 1023
 };
 
-bliss_fft_params_t bliss_fft_12289_1024 = {
+ntt_fft_params_t ntt_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
 };
@@ -622,7 +622,7 @@ static uint16_t rev_512[] = {
 	255, 511
 };
 
-bliss_fft_params_t bliss_fft_12289_512 = {
+ntt_fft_params_t ntt_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
 };
@@ -647,6 +647,6 @@ static uint16_t wi_17_8[] = { 15, 5, 13, 10, 9, 3, 1, 6 };
  */
 static uint16_t rev_8[] = { 0, 4, 2, 6, 1, 5, 3, 7 };
 
-bliss_fft_params_t bliss_fft_17_8 = {
+ntt_fft_params_t ntt_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/math/libnttfft/ntt_fft_params.h
index 0ed49b2cc..1fefac424 100644
--- a/src/libstrongswan/plugins/bliss/bliss_fft_params.h
+++ b/src/libstrongswan/math/libnttfft/ntt_fft_params.h
@@ -14,21 +14,21 @@
  */
 
 /**
- * @defgroup bliss_fft_params bliss_fft_params
- * @{ @ingroup bliss_p
+ * @defgroup ntt_fft_params ntt_fft_params
+ * @{ @ingroup ntt_p
  */
 
-#ifndef BLISS_FFT_PARAMS_H_
-#define BLISS_FFT_PARAMS_H_
+#ifndef NTT_FFT_PARAMS_H_
+#define NTT_FFT_PARAMS_H_
 
 #include <library.h>
 
-typedef struct bliss_fft_params_t bliss_fft_params_t;
+typedef struct ntt_fft_params_t ntt_fft_params_t;
 
 /**
  * Defines the parameters for an NTT computed via the FFT algorithm
  */
-struct bliss_fft_params_t {
+struct ntt_fft_params_t {
 
 	/**
 	 * Prime modulus
@@ -100,16 +100,16 @@ struct bliss_fft_params_t {
 /**
  * FFT parameters for q = 12289 and n = 1024
  */
-extern bliss_fft_params_t bliss_fft_12289_1024;
+extern ntt_fft_params_t ntt_fft_12289_1024;
 
 /**
  * FFT parameters for q = 12289 and n = 512
  */
-extern bliss_fft_params_t bliss_fft_12289_512;
+extern ntt_fft_params_t ntt_fft_12289_512;
 
 /**
  * FFT parameters for q = 17 and n = 8
  */
-extern bliss_fft_params_t bliss_fft_17_8;
+extern ntt_fft_params_t ntt_fft_17_8;
 
-#endif /** BLISS_FFT_PARAMS_H_ @}*/
+#endif /** NTT_FFT_PARAMS_H_ @}*/
diff --git a/src/libstrongswan/plugins/bliss/bliss_reduce.h b/src/libstrongswan/math/libnttfft/ntt_fft_reduce.h
index 2a53d9a7a..76a726033 100644
--- a/src/libstrongswan/plugins/bliss/bliss_reduce.h
+++ b/src/libstrongswan/math/libnttfft/ntt_fft_reduce.h
@@ -14,14 +14,14 @@
  */
 
 /**
- * @defgroup bliss_fft bliss_fft
- * @{ @ingroup bliss_p
+ * @defgroup ntt_fft ntt_fft
+ * @{ @ingroup ntt_p
  */
 
-#ifndef BLISS_REDUCE_H_
-#define BLISS_REDUCE_H_
+#ifndef NTT_REDUCE_H_
+#define NTT_REDUCE_H_
 
-#include "bliss_fft_params.h"
+#include "ntt_fft_params.h"
 
 /**
  * Montgomery Reduction
@@ -29,7 +29,7 @@
  * 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)
+static inline uint32_t ntt_fft_mreduce(uint32_t x, ntt_fft_params_t *p)
 {
 	uint32_t m, t;
 	
@@ -39,4 +39,4 @@ static inline uint32_t bliss_mreduce(uint32_t x, bliss_fft_params_t *p)
 	return (t < p->q) ? t : t - p->q;
 }
 
-#endif /** BLISS_REDUCE_H_ @}*/
+#endif /** NTT_REDUCE_H_ @}*/
diff --git a/src/libstrongswan/math/libnttfft/tests/.gitignore b/src/libstrongswan/math/libnttfft/tests/.gitignore
new file mode 100644
index 000000000..da0c7d56d
--- /dev/null
+++ b/src/libstrongswan/math/libnttfft/tests/.gitignore
@@ -0,0 +1 @@
+ntt_fft_tests
diff --git a/src/libstrongswan/math/libnttfft/tests/Makefile.am b/src/libstrongswan/math/libnttfft/tests/Makefile.am
new file mode 100644
index 000000000..55e6fff94
--- /dev/null
+++ b/src/libstrongswan/math/libnttfft/tests/Makefile.am
@@ -0,0 +1,21 @@
+TESTS = ntt_fft_tests
+
+check_PROGRAMS = $(TESTS)
+
+ntt_fft_tests_SOURCES = \
+	suites/test_ntt_fft.c \
+	ntt_fft_tests.h ntt_fft_tests.c
+
+ntt_fft_tests_CFLAGS = \
+	-I$(top_srcdir)/src/libstrongswan \
+	-I$(top_srcdir)/src/libstrongswan/tests \
+	-I$(top_srcdir)/src/libstrongswan/math/libnttfft \
+	-DPLUGINDIR=\""$(abs_top_builddir)/src/libstrongswan/plugins\"" \
+	-DPLUGINS=\""${s_plugins}\"" \
+	@COVERAGE_CFLAGS@
+
+ntt_fft_tests_LDFLAGS = @COVERAGE_LDFLAGS@
+ntt_fft_tests_LDADD = \
+	$(top_builddir)/src/libstrongswan/libstrongswan.la \
+	$(top_builddir)/src/libstrongswan/tests/libtest.la \
+	../libnttfft.la
diff --git a/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.c b/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.c
new file mode 100644
index 000000000..71f566426
--- /dev/null
+++ b/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.c
@@ -0,0 +1,60 @@
+/*
+ * 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.
+ */
+
+#include <test_runner.h>
+
+#include <library.h>
+
+/* declare test suite constructors */
+#define TEST_SUITE(x) test_suite_t* x();
+#include "ntt_fft_tests.h"
+#undef TEST_SUITE
+
+static test_configuration_t tests[] = {
+#define TEST_SUITE(x) \
+	{ .suite = x, },
+#include "ntt_fft_tests.h"
+	{ .suite = NULL, }
+};
+
+static bool test_runner_init(bool init)
+{
+	if (init)
+	{
+		char *plugins, *plugindir;
+
+		plugins = lib->settings->get_str(lib->settings,
+										"tests.load", PLUGINS);
+		plugindir = lib->settings->get_str(lib->settings,
+										"tests.plugindir", PLUGINDIR);
+		plugin_loader_add_plugindirs(plugindir, plugins);
+		if (!lib->plugins->load(lib->plugins, plugins))
+		{
+			return FALSE;
+		}
+	}
+	else
+	{
+		lib->processor->set_threads(lib->processor, 0);
+		lib->processor->cancel(lib->processor);
+		lib->plugins->unload(lib->plugins);
+	}
+	return TRUE;
+}
+
+int main(int argc, char *argv[])
+{
+	return test_runner_run("ntt_fft", tests, test_runner_init);
+}
diff --git a/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.h b/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.h
new file mode 100644
index 000000000..200b5b087
--- /dev/null
+++ b/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.h
@@ -0,0 +1,17 @@
+/*
+ * 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.
+ */
+
+TEST_SUITE(ntt_fft_suite_create)
+
diff --git a/src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c b/src/libstrongswan/math/libnttfft/tests/suites/test_ntt_fft.c
index d1328cbdc..3a8b02087 100644
--- a/src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c
+++ b/src/libstrongswan/math/libnttfft/tests/suites/test_ntt_fft.c
@@ -15,20 +15,20 @@
 
 #include "test_suite.h"
 
-#include <bliss_fft.h>
-#include <bliss_reduce.h>
+#include <ntt_fft.h>
+#include <ntt_fft_reduce.h>
 
 #include <time.h>
 
-static bliss_fft_params_t *fft_params[] = {
-	&bliss_fft_17_8,
-	&bliss_fft_12289_512,
-	&bliss_fft_12289_1024
+static ntt_fft_params_t *fft_params[] = {
+	&ntt_fft_17_8,
+	&ntt_fft_12289_512,
+	&ntt_fft_12289_1024
 };
 
-START_TEST(test_bliss_fft_impulse)
+START_TEST(test_ntt_fft_impulse)
 {
-	bliss_fft_t *fft;
+	ntt_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];
@@ -40,7 +40,7 @@ START_TEST(test_bliss_fft_impulse)
 	}
 	x[0] = 1;
  
-	fft = bliss_fft_create(fft_params[_i]);
+	fft = ntt_fft_create(fft_params[_i]);
 	fft->transform(fft, x, X, FALSE);
 
 	for (i = 0; i < n; i++)
@@ -57,9 +57,9 @@ START_TEST(test_bliss_fft_impulse)
 }
 END_TEST
 
-START_TEST(test_bliss_fft_wrap)
+START_TEST(test_ntt_fft_wrap)
 {
-	bliss_fft_t *fft;
+	ntt_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];
@@ -70,7 +70,7 @@ START_TEST(test_bliss_fft_wrap)
 		x[i] = i;
 		y[i] = 0;
 	}
-	fft = bliss_fft_create(fft_params[_i]);
+	fft = ntt_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);
@@ -82,7 +82,7 @@ START_TEST(test_bliss_fft_wrap)
 
 		for (i = 0; i < n; i++)
 		{
-			Y[i] = bliss_mreduce(X[i] * Y[i], fft_params[_i]);
+			Y[i] = ntt_fft_mreduce(X[i] * Y[i], fft_params[_i]);
 		}
 		fft->transform(fft, Y, Y, TRUE);
 
@@ -96,9 +96,9 @@ START_TEST(test_bliss_fft_wrap)
 }
 END_TEST
 
-START_TEST(test_bliss_fft_speed)
+START_TEST(test_ntt_fft_speed)
 {
-	bliss_fft_t *fft;
+	ntt_fft_t *fft;
 	struct timespec start, stop;
 	int i, m, count = 10000;
 	int n = fft_params[_i]->n;
@@ -108,7 +108,7 @@ START_TEST(test_bliss_fft_speed)
 	{
 		x[i] = i;
 	}
-	fft = bliss_fft_create(fft_params[_i]);
+	fft = ntt_fft_create(fft_params[_i]);
 
 	clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
 	for (m = 0; m < count; m++)
@@ -130,24 +130,24 @@ START_TEST(test_bliss_fft_speed)
 }
 END_TEST
 
-Suite *bliss_fft_suite_create()
+Suite *ntt_fft_suite_create()
 {
 	Suite *s;
 	TCase *tc;
 
-	s = suite_create("bliss_fft");
+	s = suite_create("ntt_fft");
 
 	tc = tcase_create("impulse");
-	tcase_add_loop_test(tc, test_bliss_fft_impulse, 0, countof(fft_params));
+	tcase_add_loop_test(tc, test_ntt_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));
+	tcase_add_loop_test(tc, test_ntt_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));
+	tcase_add_loop_test(tc, test_ntt_fft_speed, 1, countof(fft_params));
 	suite_add_tcase(s, tc);
 
 	return s;
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_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/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)