Created ntru_poly class for sparse trinary polynomials
[strongswan.git] / src / libstrongswan / plugins / ntru / ntru_poly.c
1 /*
2 * Copyright (C) 2014 Andreas Steffen
3 * HSR Hochschule fuer Technik Rapperswil
4 *
5 * Copyright (C) 2009-2013 Security Innovation
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2 of the License, or (at your
10 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * for more details.
16 */
17
18 #include "ntru_poly.h"
19 #include "ntru_mgf1.h"
20
21 #include <utils/debug.h>
22 #include <utils/test.h>
23
24 typedef struct private_ntru_poly_t private_ntru_poly_t;
25
26 /**
27 * Private data of an ntru_poly_t object.
28 */
29 struct private_ntru_poly_t {
30
31 /**
32 * Public ntru_poly_t interface.
33 */
34 ntru_poly_t public;
35
36 /**
37 * Array containing the indices of the non-zero coefficients
38 */
39 uint16_t *indices;
40
41 /**
42 * Number of non-zero coefficients
43 */
44 uint32_t indices_len;
45
46 };
47
48 METHOD(ntru_poly_t, get_size, size_t,
49 private_ntru_poly_t *this)
50 {
51 return this->indices_len;
52 }
53
54 METHOD(ntru_poly_t, get_indices, uint16_t*,
55 private_ntru_poly_t *this)
56 {
57 return this->indices;
58 }
59
60 METHOD(ntru_poly_t, destroy, void,
61 private_ntru_poly_t *this)
62 {
63 memwipe(this->indices, this->indices_len);
64 free(this->indices);
65 free(this);
66 }
67
68 /*
69 * Described in header.
70 */
71 ntru_poly_t *ntru_poly_create(hash_algorithm_t alg, chunk_t seed,
72 uint8_t c_bits, uint16_t limit,
73 uint16_t poly_len, uint32_t indices_count,
74 bool is_product_form)
75 {
76 private_ntru_poly_t *this;
77 size_t hash_len, octet_count = 0, i, num_polys, num_indices[3], indices_len;
78 uint8_t octets[HASH_SIZE_SHA512], *used, num_left = 0, num_needed;
79 uint16_t index, left = 0;
80 int poly_i = 0, index_i = 0;
81 ntru_mgf1_t *mgf1;
82
83 DBG2(DBG_LIB, "MGF1 is seeded with %u bytes", seed.len);
84 mgf1 = ntru_mgf1_create(alg, seed, TRUE);
85 if (!mgf1)
86 {
87 return NULL;
88 }
89 i = hash_len = mgf1->get_hash_size(mgf1);
90
91 if (is_product_form)
92 {
93 num_polys = 3;
94 num_indices[0] = 0xff & indices_count;
95 num_indices[1] = 0xff & (indices_count >> 8);
96 num_indices[2] = 0xff & (indices_count >> 16);
97 indices_len = num_indices[0] + num_indices[1] + num_indices[2];
98 }
99 else
100 {
101 num_polys = 1;
102 num_indices[0] = indices_count;
103 indices_len = indices_count;
104 }
105 used = malloc(poly_len);
106
107 INIT(this,
108 .public = {
109 .get_size = _get_size,
110 .get_indices = _get_indices,
111 .destroy = _destroy,
112 },
113 .indices_len = indices_len,
114 .indices = malloc(indices_len * sizeof(uint16_t)),
115 );
116
117 /* generate indices for all polynomials */
118 while (poly_i < num_polys)
119 {
120 memset(used, 0, poly_len);
121
122 /* generate indices for a single polynomial */
123 while (num_indices[poly_i])
124 {
125 /* generate a random candidate index with a size of c_bits */
126 do
127 {
128 /* use any leftover bits first */
129 index = num_left ? left << (c_bits - num_left) : 0;
130
131 /* get the rest of the bits needed from new octets */
132 num_needed = c_bits - num_left;
133
134 while (num_needed)
135 {
136 if (i == hash_len)
137 {
138 /* get another block from MGF1 */
139 if (!mgf1->get_mask(mgf1, hash_len, octets))
140 {
141 mgf1->destroy(mgf1);
142 destroy(this);
143 free(used);
144 return NULL;
145 }
146 octet_count += hash_len;
147 i = 0;
148 }
149 left = octets[i++];
150
151 if (num_needed <= 8)
152 {
153 /* all bits needed to fill the index are in this octet */
154 index |= left >> (8 - num_needed);
155 num_left = 8 - num_needed;
156 num_needed = 0;
157 left &= 0xff >> (8 - num_left);
158 }
159 else
160 {
161 /* more than one octet will be needed */
162 index |= left << (num_needed - 8);
163 num_needed -= 8;
164 }
165 }
166 }
167 while (index >= limit);
168
169 /* form index and check if unique */
170 index %= poly_len;
171 if (!used[index])
172 {
173 used[index] = 1;
174 this->indices[index_i++] = index;
175 num_indices[poly_i]--;
176 }
177 }
178 poly_i++;
179 }
180
181 DBG2(DBG_LIB, "MGF1 generates %u octets to derive %u indices",
182 octet_count, this->indices_len);
183 mgf1->destroy(mgf1);
184 free(used);
185
186 return &this->public;
187 }
188
189 EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create);