Implemented ntru_trits class

9 files changed, 383 insertions, 293 deletions

diff --git a/src/libstrongswan/plugins/ntru/Makefile.am b/src/libstrongswan/plugins/ntru/Makefile.am
index b1e5fe394..26dca727e 100644
--- a/src/libstrongswan/plugins/ntru/Makefile.am
+++ b/src/libstrongswan/plugins/ntru/Makefile.am
@@ -15,6 +15,7 @@ libstrongswan_ntru_la_SOURCES = \
 	ntru_drbg.h ntru_drbg.c \
 	ntru_ke.h ntru_ke.c \
 	ntru_mgf1.h ntru_mgf1.c \
+	ntru_trits.h ntru_trits.c \
 	ntru_crypto/ntru_crypto.h \
 	ntru_crypto/ntru_crypto_ntru_convert.h \
 	ntru_crypto/ntru_crypto_ntru_convert.c \
@@ -23,8 +24,6 @@ libstrongswan_ntru_la_SOURCES = \
 	ntru_crypto/ntru_crypto_ntru_encrypt_key.c \
 	ntru_crypto/ntru_crypto_ntru_encrypt_param_sets.h \
 	ntru_crypto/ntru_crypto_ntru_encrypt_param_sets.c \
-	ntru_crypto/ntru_crypto_ntru_mgftp1.h \
-	ntru_crypto/ntru_crypto_ntru_mgftp1.c \
 	ntru_crypto/ntru_crypto_ntru_poly.h \
 	ntru_crypto/ntru_crypto_ntru_poly.c
 
diff --git a/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_encrypt.c b/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_encrypt.c
index 5271d7cb3..065460939 100644
--- a/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_encrypt.c
+++ b/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_encrypt.c
@@ -40,7 +40,8 @@
 #include "ntru_crypto_ntru_encrypt_key.h"
 #include "ntru_crypto_ntru_convert.h"
 #include "ntru_crypto_ntru_poly.h"
-#include "ntru_crypto_ntru_mgftp1.h"
+#
+#include "ntru_trits.h"
 
 /* ntru_crypto_ntru_encrypt
  *
@@ -106,6 +107,9 @@ ntru_crypto_ntru_encrypt(
     uint16_t                mprime_len = 0;
     uint16_t                mod_q_mask;
     uint32_t                result = NTRU_OK;
+	ntru_trits_t           *mask;
+	uint8_t                *mask_trits;
+	chunk_t                 seed;
 
     /* check for bad parameters */
 
@@ -198,7 +202,7 @@ ntru_crypto_ntru_encrypt(
         uint8_t *ptr = tmp_buf;
 
         /* get b */
-        if (drbg->generate(drbg, params->sec_strength_len << 3,
+        if (drbg->generate(drbg, params->sec_strength_len * BITS_PER_BYTE,
                                  params->sec_strength_len, b_buf))
 		{
 			result = NTRU_OK;
@@ -255,14 +259,18 @@ ntru_crypto_ntru_encrypt(
                                        r_buf, params->N, params->q,
                                        scratch_buf, ringel_buf);
 
-            /* form R mod 4 */
-            ntru_coeffs_mod4_2_octets(params->N, ringel_buf, tmp_buf);
+			/* form R mod 4 */
+			ntru_coeffs_mod4_2_octets(params->N, ringel_buf, tmp_buf);
+
+			/* form mask */
+			seed = chunk_create(tmp_buf, (params->N + 3)/4);
+			mask = ntru_trits_create(params->N, hash_algid, seed);
+			if (!mask)
+			{
+				result = NTRU_MGF1_FAIL;
+			}
+		}
 
-            /* form mask */
-            result = ntru_mgftp1(hash_algid, params->min_MGF_hash_calls,
-                                 (params->N + 3) / 4, tmp_buf,
-                                 tmp_buf + params->N, params->N, tmp_buf);
-        }
 		if (result == NTRU_OK)
 		{
             uint8_t  *Mtrin_buf = tmp_buf + params->N;
@@ -296,26 +304,40 @@ ntru_crypto_ntru_encrypt(
 			}
 
             ntru_bits_2_trits(M_buf, mprime_len, Mtrin_buf);
+			mask_trits = mask->get_trits(mask);
 
-            /* form the msg representative m' by adding Mtrin to mask, mod p */
-
-            if (params->is_product_form) {
-                for (i = 0; i < mprime_len; i++) {
-                    tmp_buf[i] = tmp_buf[i] + Mtrin_buf[i];
-                    if (tmp_buf[i] >= 3)
-                        tmp_buf[i] -= 3;
-                    if (tmp_buf[i] == 1)
-                        ++m1;
-                    else if (tmp_buf[i] == 2)
-                        --m1;
-                }
-            } else {
-                for (i = 0; i < mprime_len; i++) {
-                    tmp_buf[i] = tmp_buf[i] + Mtrin_buf[i];
-                    if (tmp_buf[i] >= 3)
-                        tmp_buf[i] -= 3;
-                }
-            }
+			/* form the msg representative m' by adding Mtrin to mask, mod p */
+			if (params->is_product_form)
+			{
+				for (i = 0; i < mprime_len; i++)
+				{
+					tmp_buf[i] = mask_trits[i] + Mtrin_buf[i];
+					if (tmp_buf[i] >= 3)
+					{
+						tmp_buf[i] -= 3;
+					}
+					if (tmp_buf[i] == 1)
+					{
+						++m1;
+					}
+					else if (tmp_buf[i] == 2)
+					{
+						--m1;
+					}
+				}
+			}
+			else
+			{
+				for (i = 0; i < mprime_len; i++)
+				{
+					tmp_buf[i] = mask_trits[i] + Mtrin_buf[i];
+					if (tmp_buf[i] >= 3)
+					{
+						tmp_buf[i] -= 3;
+					}
+				}
+			}
+			mask->destroy(mask);
 
             /* check that message representative meets minimum weight
              * requirements
@@ -426,9 +448,11 @@ ntru_crypto_ntru_decrypt(
     uint16_t                i;
     bool                    decryption_ok = TRUE;
     uint32_t                result = NTRU_OK;
+	ntru_trits_t           *mask;
+	uint8_t                *mask_trits;
+	chunk_t                 seed;
 
-    /* check for bad parameters */
-
+	/* check for bad parameters */
 	if (!privkey_blob || !ct || !pt_len)
 	{
 		return NTRU_BAD_PARAMETER;
@@ -588,38 +612,48 @@ ntru_crypto_ntru_decrypt(
 												   params->min_msg_rep_wt);
 	}
 
-    /* form cR = e - cm' mod q */
-
-    for (i = 0; i < cmprime_len; i++) {
-        if (Mtrin_buf[i] == 1)
-            ringel_buf2[i] = (ringel_buf2[i] - 1) & mod_q_mask;
-        else if (Mtrin_buf[i] == 2)
-            ringel_buf2[i] = (ringel_buf2[i] + 1) & mod_q_mask;
-    }
-    if (params->is_product_form)
-        ringel_buf2[i] = (ringel_buf2[i] + m1) & mod_q_mask;
-
-
-    /* form cR mod 4 */
-
-    ntru_coeffs_mod4_2_octets(params->N, ringel_buf2, tmp_buf);
-
-    /* form mask */
+	/* form cR = e - cm' mod q */
+	for (i = 0; i < cmprime_len; i++)
+	{
+		if (Mtrin_buf[i] == 1)
+		{
+			ringel_buf2[i] = (ringel_buf2[i] - 1) & mod_q_mask;
+		}
+		else if (Mtrin_buf[i] == 2)
+		{
+			ringel_buf2[i] = (ringel_buf2[i] + 1) & mod_q_mask;
+		}
+	}
+	if (params->is_product_form)
+	{
+		ringel_buf2[i] = (ringel_buf2[i] + m1) & mod_q_mask;
+	}
 
-    result = ntru_mgftp1(hash_algid, params->min_MGF_hash_calls,
-                         (params->N + 3) / 4, tmp_buf,
-                         tmp_buf + params->N, params->N, tmp_buf);
+	/* form cR mod 4 */
+	ntru_coeffs_mod4_2_octets(params->N, ringel_buf2, tmp_buf);
 
-	if (result == NTRU_OK)
+	/* form mask */
+	seed = chunk_create(tmp_buf, (params->N + 3)/4);
+	mask = ntru_trits_create(params->N, hash_algid, seed);
+	if (!mask)
 	{
+		result = NTRU_MGF1_FAIL;
+	}
+	else
+	{
+		mask_trits = mask->get_trits(mask);
 
-        /* form cMtrin by subtracting mask from cm', mod p */
+		/* form cMtrin by subtracting mask from cm', mod p */
+		for (i = 0; i < cmprime_len; i++)
+		{
+			Mtrin_buf[i] = Mtrin_buf[i] - mask_trits[i];
+			if (Mtrin_buf[i] >= 3)
+			{
+				Mtrin_buf[i] += 3;
+			}
+		}
+		mask->destroy(mask);
 
-        for (i = 0; i < cmprime_len; i++) {
-            Mtrin_buf[i] = Mtrin_buf[i] - tmp_buf[i];
-            if (Mtrin_buf[i] >= 3)
-                Mtrin_buf[i] += 3;
-        }
         if (params->is_product_form)
 
             /* set the last trit to zero since that's what it was, and
@@ -897,7 +931,8 @@ ntru_crypto_ntru_encrypt_keygen(
      * as a list of indices
      */
 
-    if (drbg->generate(drbg, params->sec_strength_len << 3, seed_len, tmp_buf))
+    if (drbg->generate(drbg, params->sec_strength_len * BITS_PER_BYTE,
+							 seed_len, tmp_buf))
 	{
 		result = NTRU_OK;
 	}
@@ -985,8 +1020,8 @@ ntru_crypto_ntru_encrypt_keygen(
         /* get random bytes for seed for generating trinary g
          * as a list of indices
          */
-        if (!drbg->generate(drbg, params->sec_strength_len << 3, seed_len,
-								  tmp_buf))
+        if (!drbg->generate(drbg, params->sec_strength_len * BITS_PER_BYTE,
+								  seed_len, tmp_buf))
 		{
 			result = NTRU_DRBG_FAIL;
 		}
diff --git a/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_mgftp1.c b/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_mgftp1.c
deleted file mode 100644
index 1d3362625..000000000
--- a/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_mgftp1.c
+++ /dev/null
@@ -1,156 +0,0 @@
-/******************************************************************************
- * NTRU Cryptography Reference Source Code
- * Copyright (c) 2009-2013, by Security Innovation, Inc. All rights reserved. 
- *
- * ntru_crypto_ntru_mgftp1.c is a component of ntru-crypto.
- *
- * Copyright (C) 2009-2013  Security Innovation
- * 
- * 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.
- * 
- * 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.
- * 
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
- *
- *****************************************************************************/
- 
-/******************************************************************************
- *
- * File: ntru_crypto_ntru_mgftp1.c
- *
- * Contents: Routines implementing MGF-TP-1.
- *
- *****************************************************************************/
-
-
-#include <stdlib.h>
-#include <string.h>
-#include "ntru_crypto_ntru_mgftp1.h"
-#include "ntru_crypto_ntru_convert.h"
-
-#include "ntru_mgf1.h"
-
-/* ntru_mgftp1
- *
- * Implements a mask-generation function for trinary polynomials,
- * MGF-TP-1, generating an arbitrary number of octets based on hashing
- * a digest-length string concatenated with a 4-octet counter.  From
- * these octets, N trits are derived.
- *
- * The state (string and counter) is initialized when a seed is present.
- *
- * Returns NTRU_OK if successful.
- * Returns NTRU_MGF1_FAIL if the MGF1 mask generator function fails
- *
- */
-
-uint32_t
-ntru_mgftp1(
-	hash_algorithm_t        hash_algid,       /*  in - hash alg ID for
-                                                       MGF-TP-1 */
-	uint8_t                 min_calls,        /*  in - minimum no. of hash
-                                                       calls */
-	uint16_t                seed_len,         /*  in - no. of octets in seed */
-	uint8_t                *seed,             /*  in - pointer to seed */
-	uint8_t                *buf,              /*  in - pointer to working
-                                                       buffer */
-	uint16_t                num_trits_needed, /*  in - no. of trits in mask */
-	uint8_t                *mask)             /* out - address for mask trits */
-{
-	uint8_t   md_len;
-	uint8_t  *octets;
-	uint16_t  octets_available;
-	ntru_mgf1_t *mgf1;
-
-	/* generate minimum MGF1 output */
-	DBG2(DBG_LIB, "MGF1 is seeded with %u octets", seed_len);
-	mgf1 = ntru_mgf1_create(hash_algid, chunk_create(seed, seed_len), TRUE);
-	if (!mgf1)
-	{
-	    return NTRU_MGF1_FAIL;
-	}
-	md_len = mgf1->get_hash_size(mgf1);
-	octets = buf;
-	octets_available = min_calls * md_len;
-
-	DBG2(DBG_LIB, "MGF1 generates %u octets to extract %d trits",
-				   octets_available, num_trits_needed);
-	if (!mgf1->get_mask(mgf1, octets_available, octets))
-	{
-		mgf1->destroy(mgf1);
-		return NTRU_MGF1_FAIL;
-	}
-
-	/* get trits for mask */
-	while (num_trits_needed >= 5)
-	{
-		/* get another octet and convert it to 5 trits */
-		if (octets_available == 0)
-		{
-			octets = buf;
-			octets_available = md_len;
-
-			DBG2(DBG_LIB, "MGF1 generates another %u octets for the remaining "
-						  "%u trits", octets_available, num_trits_needed);
-			if (!mgf1->get_mask(mgf1, octets_available, octets))
-			{
-				mgf1->destroy(mgf1);
-				return NTRU_MGF1_FAIL;
-			}
-		}
-
-		if (*octets < 243)
-		{
-			ntru_octet_2_trits(*octets, mask);
-			mask += 5;
-			num_trits_needed -= 5;
-		}
-		octets++;
-		--octets_available;
-	}
-
-	/* get any remaining trits */
-	while (num_trits_needed)
-	{
-		uint8_t trits[5];
-
-		/* get another octet and convert it to remaining trits */
-		if (octets_available == 0)
-		{
-			octets = buf;
-			octets_available = md_len;
-
-			DBG2(DBG_LIB, "MGF1 generates another %u octets for the remaining "
-						  "%u trits", octets_available, num_trits_needed);
-			if (!mgf1->get_mask(mgf1, octets_available, octets))
-			{
-				mgf1->destroy(mgf1);
-			    return NTRU_MGF1_FAIL;
-			}
-		}
-		if (*octets < 243)
-		{
-			ntru_octet_2_trits(*octets, trits);
-			memcpy(mask, trits, num_trits_needed);
-			num_trits_needed = 0;
-		}
-		else
-		{
-			octets++;
-			--octets_available;
-		}
-	}
-	mgf1->destroy(mgf1);
-
-	return NTRU_OK;
-}
-
-
diff --git a/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_mgftp1.h b/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_mgftp1.h
deleted file mode 100644
index 6f85efc89..000000000
--- a/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_mgftp1.h
+++ /dev/null
@@ -1,70 +0,0 @@
-/******************************************************************************
- * NTRU Cryptography Reference Source Code
- * Copyright (c) 2009-2013, by Security Innovation, Inc. All rights reserved. 
- *
- * ntru_crypto_ntru_mgftp1.h is a component of ntru-crypto.
- *
- * Copyright (C) 2009-2013  Security Innovation
- * 
- * 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.
- * 
- * 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.
- * 
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
- *
- *****************************************************************************/
- 
-/******************************************************************************
- *
- * File:  ntru_crypto_ntru_mgftp1.h
- *
- * Contents: Public header file for MGF-TP-1 in the NTRU algorithm.
- *
- *****************************************************************************/
-
-
-#ifndef NTRU_CRYPTO_NTRU_MGF1_H
-#define NTRU_CRYPTO_NTRU_MGF1_H
-
-
-#include "ntru_crypto.h"
-
-#include <crypto/hashers/hasher.h>
-
-/* ntru_mgftp1
- *
- * Implements a mask-generation function for trinary polynomials,
- * MGF-TP-1, generating an arbitrary number of octets based on hashing
- * a digest-length string concatenated with a 4-octet counter.  From
- * these octets, N trits are derived.
- *
- * The state (string and counter) is initialized when a seed is present.
- *
- * Returns NTRU_OK if successful.
- * Returns NTRU_CRYPTO_HASH_ errors if they occur.
- *
- */
-
-extern uint32_t
-ntru_mgftp1(
-    hash_algorithm_t        hash_algid,       /*  in - hash alg ID for
-                                                       MGF-TP-1 */
-    uint8_t                 min_calls,        /*  in - minimum no. of hash
-                                                       calls */
-    uint16_t                seed_len,         /*  in - no. of octets in seed */
-    uint8_t                *seed,             /*  in - pointer to seed */
-    uint8_t                *buf,              /*  in - pointer to working
-                                                       buffer */
-    uint16_t                num_trits_needed, /*  in - no. of trits in mask */
-    uint8_t                *mask);            /* out - address for mask trits */
-
-
-#endif /* NTRU_CRYPTO_NTRU_MGF1_H */
diff --git a/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_poly.c b/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_poly.c
index e1f4f04a4..6969baaee 100644
--- a/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_poly.c
+++ b/src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_poly.c
@@ -35,7 +35,6 @@
 #include <stdlib.h>
 #include <string.h>
 #include "ntru_crypto_ntru_poly.h"
-#include "ntru_crypto_ntru_mgftp1.h"
 
 #include "ntru_mgf1.h"
 
@@ -93,7 +92,7 @@ ntru_gen_poly(
 	ntru_mgf1_t *mgf1;
 
     /* generate minimum MGF1 output */
-	DBG2(DBG_LIB, "MGF1 is seeded with %u octets", seed_len);
+	DBG2(DBG_LIB, "MGF1 is seeded with %u bytes", seed_len);
 	mgf1 = ntru_mgf1_create(hash_algid, chunk_create(seed, seed_len), TRUE);
 	if (!mgf1)
 	{
diff --git a/src/libstrongswan/plugins/ntru/ntru_drbg.c b/src/libstrongswan/plugins/ntru/ntru_drbg.c
index 0081223c9..6fc13aa0a 100644
--- a/src/libstrongswan/plugins/ntru/ntru_drbg.c
+++ b/src/libstrongswan/plugins/ntru/ntru_drbg.c
@@ -119,7 +119,7 @@ METHOD(ntru_drbg_t, reseed, bool,
 	chunk_t seed;
 
 	seed = chunk_alloc(this->strength / BITS_PER_BYTE);
-	DBG2(DBG_LIB, "DRG requests %u bytes of entropy", seed.len);
+	DBG2(DBG_LIB, "DRBG requests %u bytes of entropy", seed.len);
 
 	if (!this->entropy->get_bytes(this->entropy, seed.len, seed.ptr))
 	{
diff --git a/src/libstrongswan/plugins/ntru/ntru_trits.c b/src/libstrongswan/plugins/ntru/ntru_trits.c
new file mode 100644
index 000000000..f82501629
--- /dev/null
+++ b/src/libstrongswan/plugins/ntru/ntru_trits.c
@@ -0,0 +1,133 @@
+/*
+ * Copyright (C) 2013 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 "ntru_trits.h"
+#include "ntru_mgf1.h"
+
+#include "ntru_crypto/ntru_crypto_ntru_convert.h"
+
+#include <utils/debug.h>
+#include <utils/test.h>
+
+typedef struct private_ntru_trits_t private_ntru_trits_t;
+
+/**
+ * Private data of an ntru_trits_t object.
+ */
+struct private_ntru_trits_t {
+
+	/**
+	 * Public ntru_trits_t interface.
+	 */
+	ntru_trits_t public;
+
+	/**
+	 * Size of the trits array
+	 */
+	size_t trits_len;
+
+	/**
+	 * Array containing a trit per octet
+	 */
+	uint8_t *trits;
+
+};
+
+METHOD(ntru_trits_t, get_size, size_t,
+	private_ntru_trits_t *this)
+{
+	return this->trits_len;
+}
+
+METHOD(ntru_trits_t, get_trits, uint8_t*,
+	private_ntru_trits_t *this)
+{
+	return this->trits;
+}
+
+METHOD(ntru_trits_t, destroy, void,
+	private_ntru_trits_t *this)
+{
+	memwipe(this->trits, this->trits_len);
+	free(this->trits);
+	free(this);
+}
+
+/*
+ * Described in header.
+ */
+ntru_trits_t *ntru_trits_create(size_t len, hash_algorithm_t alg, chunk_t seed)
+{
+	private_ntru_trits_t *this;
+	uint8_t octets[HASH_SIZE_SHA512], buf[5], *trits;
+	size_t hash_len, octet_count = 0, trits_needed, i;
+	ntru_mgf1_t *mgf1;
+
+	DBG2(DBG_LIB, "MGF1 is seeded with %u bytes", seed.len);
+	mgf1 = ntru_mgf1_create(alg, seed, TRUE);
+	if (!mgf1)
+	{
+	    return NULL;
+	}
+	i = hash_len = mgf1->get_hash_size(mgf1);
+
+	INIT(this,
+		.public = {
+			.get_size = _get_size,
+			.get_trits = _get_trits,
+			.destroy = _destroy,
+		},
+		.trits_len = len,
+		.trits = malloc(len),
+	);
+
+	trits = this->trits;
+	trits_needed = this->trits_len;
+
+	while (trits_needed > 0)
+	{
+		if (i == hash_len)
+		{
+			/* get another block from MGF1 */
+			if (!mgf1->get_mask(mgf1, hash_len, octets))
+			{
+				mgf1->destroy(mgf1);
+				destroy(this);
+				return NULL;
+			}
+			octet_count += hash_len;
+			i = 0;
+		}
+		if (octets[i] < 243)  /* 243 = 3^5 */ 
+		{		
+			ntru_octet_2_trits(octets[i], (trits_needed < 5) ? buf : trits);
+			if (trits_needed < 5)
+			{
+				memcpy(trits, buf, trits_needed);
+				break;
+			}
+			trits += 5;
+			trits_needed -= 5;
+		}
+		i++;
+	}
+	DBG2(DBG_LIB, "MGF1 generates %u octets to extract %u trits",
+				   octet_count, len);
+	mgf1->destroy(mgf1);
+
+	return &this->public;
+}
+
+EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_trits_create);
diff --git a/src/libstrongswan/plugins/ntru/ntru_trits.h b/src/libstrongswan/plugins/ntru/ntru_trits.h
new file mode 100644
index 000000000..524c51bac
--- /dev/null
+++ b/src/libstrongswan/plugins/ntru/ntru_trits.h
@@ -0,0 +1,61 @@
+/*
+ * Copyright (C) 2013 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 ntru_trits ntru_trits
+ * @{ @ingroup ntru_p
+ */
+
+#ifndef NTRU_TRITS_H_
+#define NTRU_TRITS_H_
+
+typedef struct ntru_trits_t ntru_trits_t;
+
+#include <library.h>
+
+/**
+ * Implements an array of trinary elements (trits) 
+ */
+struct ntru_trits_t {
+
+	/**
+	 * Get the size of the trits array
+	 *
+	 * @return			number of trinary elements
+	 */
+	size_t (*get_size)(ntru_trits_t *this);
+
+	/**
+	 * @return			octet array containing a trit per octet
+	 */
+	uint8_t* (*get_trits)(ntru_trits_t *this);
+
+	/**
+	 * Destroy ntru_trits_t object
+	 */
+	void (*destroy)(ntru_trits_t *this);
+};
+
+/**
+ * Create a trits array from a seed using MGF1 with a base hash function
+ *
+ * @param size			size of the trits array
+ * @param alg			hash algorithm to be used by MGF1
+ * @param seed			seed used by MGF1 to generate trits from
+ */
+ntru_trits_t *ntru_trits_create(size_t size, hash_algorithm_t alg, chunk_t seed);
+
+#endif /** NTRU_TRITS_H_ @}*/
+
diff --git a/src/libstrongswan/tests/suites/test_ntru.c b/src/libstrongswan/tests/suites/test_ntru.c
index 2548d3134..91aa27c18 100644
--- a/src/libstrongswan/tests/suites/test_ntru.c
+++ b/src/libstrongswan/tests/suites/test_ntru.c
@@ -18,6 +18,7 @@
 #include <tests/utils/test_rng.h>
 #include <plugins/ntru/ntru_drbg.h>
 #include <plugins/ntru/ntru_mgf1.h>
+#include <plugins/ntru/ntru_trits.h>
 #include <utils/test.h>
 
 IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_drbg_create, ntru_drbg_t*,
@@ -26,6 +27,9 @@ IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_drbg_create, ntru_drbg_t*,
 IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_mgf1_create, ntru_mgf1_t*,
 						  hash_algorithm_t alg, chunk_t seed, bool hash_seed)
 
+IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_trits_create, ntru_trits_t*,
+						  size_t len, hash_algorithm_t alg, chunk_t seed)
+
 /**
  * NTRU parameter sets to test
  */
@@ -297,6 +301,7 @@ typedef struct {
 	chunk_t seed;
 	chunk_t hashed_seed;
 	chunk_t mask;
+	chunk_t trits;
 } mgf1_test_t;
 
 /**
@@ -338,7 +343,31 @@ mgf1_test_t mgf1_tests[] = {
 						0x40, 0x4B, 0xE7, 0x22, 0x3A, 0x56, 0x10, 0x6D,
 						0x4D, 0x29, 0x0B, 0xCE, 0xA6, 0x21, 0xB5, 0x5C,
 						0x71, 0x66, 0x2F, 0x70, 0x35, 0xD8, 0x8A, 0x92,
-						0x33, 0xF0, 0x16, 0xD4, 0x0E, 0x43, 0x8A, 0x14) },
+						0x33, 0xF0, 0x16, 0xD4, 0x0E, 0x43, 0x8A, 0x14), 
+		chunk_from_chars(
+				1, 2, 1, 0, 0,  1, 1, 1, 2, 0,  1, 0, 1, 1, 1,  0, 2, 0, 1, 1,
+				0, 0, 0, 1, 1,  0, 2, 0, 2, 2,	1, 2, 2, 2, 1,  2, 1, 1, 0, 0,
+				2, 0, 1, 1, 1,	0, 0, 0, 0, 1,  1, 2, 0, 0, 1,  0, 1, 0, 2, 0,
+				0, 1, 0, 2, 1,  0, 0, 0, 2, 0,  0, 0, 1, 2, 2,	0, 0, 2, 0, 1,
+				1, 2, 1, 1, 0,  0, 1, 1, 1, 2,	2, 1, 2, 0, 0,  2, 1, 0, 0, 1,
+				0, 1, 1, 0, 0,	0, 1, 2, 2, 0,  1, 2, 1, 2, 0,  2, 0, 0, 0, 2,
+				1, 2, 0, 0, 0,  2, 0, 0, 0, 2,  2, 1, 0, 2, 0,	1, 2, 0, 2, 1,
+				0, 2, 2, 1, 0,  2, 1, 2, 2, 0,  2, 0, 2, 1, 2,  2, 0, 2, 0, 1,
+				1, 2, 2, 2, 2,  1, 0, 1, 0, 2,  2, 0, 1, 1, 2,  2, 2, 0, 0, 1,
+				0, 2, 0, 1, 0,  2, 1, 2, 1, 0,  1, 1, 2, 0, 0,  2, 1, 1, 2, 0,
+				1, 2, 1, 1, 0,  1, 0, 2, 1, 1,  1, 2, 1, 0, 2,  0, 2, 0, 0, 2,
+				2, 1, 0, 0, 2,  2, 0, 1, 1, 0,  0, 1, 1, 0, 1,  1, 2, 1, 2, 2,
+				2, 0, 0, 0, 0,  1, 0, 0, 1, 2,  1, 2, 0, 2, 1,  1, 1, 0, 2, 2,
+				1, 2, 2, 1, 0,  1, 0, 2, 2, 2,  1, 2, 1, 0, 0,  1, 0, 1, 1, 1,
+				1, 1, 2, 0, 0,  2, 1, 0, 2, 1,  2, 1, 0, 2, 2,  0, 0, 1, 2, 1,
+				2, 0, 1, 2, 1,  1, 2, 0, 2, 0,  2, 1, 1, 1, 0,  0, 0, 1, 2, 1,
+				2, 2, 1, 2, 1,  1, 2, 1, 2, 0,  2, 2, 1, 0, 0,  1, 2, 0, 1, 1,
+				2, 0, 0, 0, 1,  2, 2, 1, 2, 0,  0, 2, 1, 0, 2,  2, 2, 1, 1, 0,
+				2, 1, 2, 1, 2,  2, 1, 2, 1, 1,  0, 1, 1, 1, 1,  2, 0, 2, 2, 1,
+				0, 1, 1, 2, 1,  2, 0, 2, 1, 0,  1, 0, 1, 0, 1,  2, 0, 1, 1, 0,
+				0, 1, 1, 2, 0,  2, 2, 0, 0, 0,  1, 1, 0, 1, 0,  1, 1, 0, 1, 1,
+				0, 1, 2, 0, 1,  1, 0, 1, 2, 0,  0, 1, 2, 2, 0,  0, 2, 1, 2)
+	},
 	{	HASH_SHA256, 32, 64, 32, 33,
 		chunk_from_chars(
 						0x52, 0xC5, 0xDD, 0x1E, 0xEF, 0x76, 0x1B, 0x53,
@@ -385,7 +414,39 @@ mgf1_test_t mgf1_tests[] = {
 						0x35, 0xD7, 0x06, 0x3F, 0x40, 0x82, 0xDA, 0xC3,
 						0x2B, 0x3C, 0x91, 0x3A, 0x32, 0xF8, 0xB2, 0xC6,
 						0x44, 0x4D, 0xCD, 0xB6, 0x54, 0x5F, 0x81, 0x95,
-						0x59, 0xA1, 0xE5, 0x4E, 0xA5, 0x0A, 0x4A, 0x42) }
+						0x59, 0xA1, 0xE5, 0x4E, 0xA5, 0x0A, 0x4A, 0x42),
+		chunk_from_chars(
+				1, 2, 2, 2, 2,  1, 2, 2, 0, 0,  2, 0, 0, 0, 0,  1, 2, 2, 2, 0,
+				2, 0, 0, 2, 2,  1, 2, 0, 0, 1,  2, 1, 0, 0, 0,  1, 0, 2, 2, 1,
+				1, 2, 0, 0, 0,  1, 2, 0, 2, 2,  1, 2, 1, 0, 1,  0, 1, 2, 1, 1,
+				1, 2, 0, 1, 0,  2, 1, 1, 0, 0,  0, 1, 2, 0, 0,  1, 2, 1, 2, 0,
+				2, 1, 1, 1, 2,  2, 2, 2, 1, 0,  0, 2, 0, 2, 0,  1, 1, 0, 2, 2,
+				2, 0, 1, 0, 2,  2, 1, 0, 1, 0,  1, 0, 0, 2, 2,  0, 0, 1, 2, 0,
+				1, 1, 1, 0, 0,  2, 0, 2, 1, 2,  2, 2, 0, 0, 2,  1, 0, 2, 0, 1,
+				0, 1, 2, 0, 1,  2, 0, 1, 0, 1,  2, 0, 2, 2, 0,  1, 2, 2, 1, 2,
+				2, 2, 0, 2, 1,  1, 1, 0, 0, 1,  0, 2, 0, 0, 1,  0, 1, 2, 0, 0,
+				1, 2, 1, 0, 2,  1, 1, 0, 0, 2,  1, 2, 2, 2, 1,  2, 1, 1, 2, 2,
+				0, 2, 0, 0, 2,  0, 0, 1, 1, 2,  0, 0, 0, 1, 2,  1, 1, 1, 1, 0,
+				0, 0, 2, 0, 2,  0, 2, 2, 1, 2,  2, 0, 0, 1, 1,  1, 0, 1, 0, 1,
+				0, 1, 2, 2, 0,  2, 1, 1, 0, 2,  1, 2, 1, 2, 1,  0, 0, 1, 0, 0,
+				1, 0, 1, 0, 2,  0, 2, 0, 0, 1,  2, 0, 2, 0, 1,  1, 0, 2, 0, 0,
+				1, 2, 1, 2, 1,  2, 1, 0, 1, 1,  2, 2, 1, 1, 0,  0, 2, 1, 2, 0,
+				1, 0, 2, 0, 0,  1, 2, 0, 2, 0,  1, 1, 2, 2, 2,  2, 0, 0, 1, 2,
+				1, 1, 1, 0, 2,  1, 2, 2, 0, 2,  0, 1, 2, 2, 0,  1, 1, 1, 0, 0,
+				2, 0, 1, 0, 1,  0, 2, 1, 2, 0,  2, 1, 2, 1, 2,  2, 0, 2, 1, 0,
+				2, 1, 2, 0, 0,  2, 0, 1, 2, 1,  1, 2, 0, 0, 0,  0, 1, 2, 0, 1,
+				2, 2, 1, 0, 0,  1, 2, 1, 2, 0,  0, 1, 1, 0, 0,  0, 1, 0, 0, 0,
+				2, 0, 1, 2, 1,  2, 0, 0, 0, 2,  1, 0, 0, 0, 1,  2, 2, 0, 0, 0,
+				2, 2, 1, 1, 0,  1, 0, 2, 2, 0,  2, 1, 2, 1, 0,  2, 2, 2, 0, 0,
+				0, 1, 1, 2, 1,  0, 0, 0, 0, 1,  2, 2, 1, 2, 1,  2, 0, 2, 0, 2,
+				1, 1, 1, 2, 1,  2, 1, 2, 1, 1,  0, 1, 0, 2, 0,  0, 0, 2, 1, 2,
+				2, 2, 2, 0, 1,  1, 1, 0, 1, 0,  2, 0, 2, 1, 0,  1, 2, 1, 1, 0,
+				1, 2, 1, 0, 0,  2, 1, 0, 1, 1,  2, 2, 1, 1, 1,  2, 2, 2, 1, 0,
+				0, 0, 0, 1, 1,  0, 0, 2, 2, 2,  2, 2, 0, 1, 2,  0, 1, 2, 0, 1,
+				1, 0, 1, 1, 2,  2, 0, 1, 1, 0,  2, 2, 1, 1, 1,  2, 1, 2, 2, 1,
+				1, 0, 1, 0, 2,  2, 1, 0, 2, 2,  2, 2, 2, 1, 0,  2, 2, 2, 1, 2,
+				0, 2, 0, 0, 0,  0, 0, 1, 2, 0,  1, 0, 1)
+	}
 };
 
 START_TEST(test_ntru_mgf1)
@@ -453,6 +514,30 @@ START_TEST(test_ntru_mgf1)
 }
 END_TEST
 
+START_TEST(test_ntru_trits)
+{
+	ntru_trits_t *mask;
+	chunk_t trits;
+
+	mask = ntru_trits_create(mgf1_tests[_i].trits.len, HASH_UNKNOWN,
+							 mgf1_tests[_i].seed);
+	ck_assert(mask == NULL);
+
+	mask = ntru_trits_create(mgf1_tests[_i].trits.len, mgf1_tests[_i].alg,
+							 chunk_empty);
+	ck_assert(mask == NULL);
+
+	mask = ntru_trits_create(mgf1_tests[_i].trits.len, mgf1_tests[_i].alg,
+							 mgf1_tests[_i].seed);
+	ck_assert(mask);
+
+	trits = chunk_create(mask->get_trits(mask), mask->get_size(mask));
+	ck_assert(chunk_equals(trits, mgf1_tests[_i].trits));
+
+	mask->destroy(mask);
+}
+END_TEST
+
 START_TEST(test_ntru_ke)
 {
 	chunk_t pub_key, cipher_text, i_shared_secret, r_shared_secret;
@@ -659,6 +744,10 @@ Suite *ntru_suite_create()
 	tcase_add_loop_test(tc, test_ntru_mgf1, 0, countof(mgf1_tests));
 	suite_add_tcase(s, tc);
 
+	tc = tcase_create("trits");
+	tcase_add_loop_test(tc, test_ntru_trits, 0, countof(mgf1_tests));
+	suite_add_tcase(s, tc);
+
 	tc = tcase_create("ke");
 	tcase_add_loop_test(tc, test_ntru_ke, 0, countof(params));
 	suite_add_tcase(s, tc);