1 #include <stdint.h>
2 #include "kyber512r3_params.h"
3 #include "kyber512r3_poly.h"
4 #include "kyber512r3_ntt.h"
5 #include "kyber512r3_reduce.h"
6 #include "kyber512r3_cbd.h"
7 #include "kyber512r3_symmetric.h"
8
9 /*************************************************
10 * Name: poly_compress
11 *
12 * Description: Compression and subsequent serialization of a polynomial
13 *
14 * Arguments: - uint8_t *r: pointer to output byte array
15 * (of length S2N_KYBER_512_R3_POLYCOMPRESSEDBYTES)
16 * - poly *a: pointer to input polynomial
17 **************************************************/
poly_compress(uint8_t r[S2N_KYBER_512_R3_POLYCOMPRESSEDBYTES],poly * a)18 void poly_compress(uint8_t r[S2N_KYBER_512_R3_POLYCOMPRESSEDBYTES], poly *a) {
19 unsigned int i, j;
20 uint8_t t[8];
21
22 poly_csubq(a);
23
24 for (i = 0; i < S2N_KYBER_512_R3_N / 8; i++) {
25 for (j = 0; j < 8; j++) {
26 t[j] = ((((uint16_t)a->coeffs[8 * i + j] << 4) + S2N_KYBER_512_R3_Q / 2) / S2N_KYBER_512_R3_Q) & 15;
27 }
28
29 r[0] = t[0] | (t[1] << 4);
30 r[1] = t[2] | (t[3] << 4);
31 r[2] = t[4] | (t[5] << 4);
32 r[3] = t[6] | (t[7] << 4);
33 r += 4;
34 }
35 }
36
37 /*************************************************
38 * Name: poly_decompress
39 *
40 * Description: De-serialization and subsequent decompression of a polynomial;
41 * approximate inverse of poly_compress
42 *
43 * Arguments: - poly *r: pointer to output polynomial
44 * - const uint8_t *a: pointer to input byte array
45 * (of length S2N_KYBER_512_R3_POLYCOMPRESSEDBYTES bytes)
46 **************************************************/
poly_decompress(poly * r,const uint8_t a[S2N_KYBER_512_R3_POLYCOMPRESSEDBYTES])47 void poly_decompress(poly *r, const uint8_t a[S2N_KYBER_512_R3_POLYCOMPRESSEDBYTES]) {
48 unsigned int i;
49
50 for (i = 0; i < S2N_KYBER_512_R3_N / 2; i++) {
51 r->coeffs[2 * i + 0] = (((uint16_t)(a[0] & 15) * S2N_KYBER_512_R3_Q) + 8) >> 4;
52 r->coeffs[2 * i + 1] = (((uint16_t)(a[0] >> 4) * S2N_KYBER_512_R3_Q) + 8) >> 4;
53 a += 1;
54 }
55 }
56
57 /*************************************************
58 * Name: poly_tobytes
59 *
60 * Description: Serialization of a polynomial
61 *
62 * Arguments: - uint8_t *r: pointer to output byte array
63 * (needs space for S2N_KYBER_512_R3_POLYBYTES bytes)
64 * - poly *a: pointer to input polynomial
65 **************************************************/
poly_tobytes(uint8_t r[S2N_KYBER_512_R3_POLYBYTES],poly * a)66 void poly_tobytes(uint8_t r[S2N_KYBER_512_R3_POLYBYTES], poly *a) {
67 unsigned int i;
68
69 poly_csubq(a);
70
71 for (i = 0; i < S2N_KYBER_512_R3_N / 2; i++) {
72 uint16_t t0 = a->coeffs[2 * i];
73 uint16_t t1 = a->coeffs[2 * i + 1];
74 r[3 * i + 0] = (t0 >> 0);
75 r[3 * i + 1] = (t0 >> 8) | (t1 << 4);
76 r[3 * i + 2] = (t1 >> 4);
77 }
78 }
79
80 /*************************************************
81 * Name: poly_frombytes
82 *
83 * Description: De-serialization of a polynomial;
84 * inverse of poly_tobytes
85 *
86 * Arguments: - poly *r: pointer to output polynomial
87 * - const uint8_t *a: pointer to input byte array
88 * (of S2N_KYBER_512_R3_POLYBYTES bytes)
89 **************************************************/
poly_frombytes(poly * r,const uint8_t a[S2N_KYBER_512_R3_POLYBYTES])90 void poly_frombytes(poly *r, const uint8_t a[S2N_KYBER_512_R3_POLYBYTES]) {
91 unsigned int i;
92 for (i = 0; i < S2N_KYBER_512_R3_N / 2; i++) {
93 r->coeffs[2 * i] = ((a[3 * i + 0] >> 0) | ((uint16_t)a[3 * i + 1] << 8)) & 0xFFF;
94 r->coeffs[2 * i + 1] = ((a[3 * i + 1] >> 4) | ((uint16_t)a[3 * i + 2] << 4)) & 0xFFF;
95 }
96 }
97
98 /*************************************************
99 * Name: poly_frommsg
100 *
101 * Description: Convert 32-byte message to polynomial
102 *
103 * Arguments: - poly *r: pointer to output polynomial
104 * - const uint8_t *msg: pointer to input message
105 **************************************************/
poly_frommsg(poly * r,const uint8_t msg[S2N_KYBER_512_R3_INDCPA_MSGBYTES])106 void poly_frommsg(poly *r, const uint8_t msg[S2N_KYBER_512_R3_INDCPA_MSGBYTES]) {
107 unsigned int i, j;
108 int16_t mask;
109
110 for (i = 0; i < S2N_KYBER_512_R3_N / 8; i++) {
111 for (j = 0; j < 8; j++) {
112 mask = -(int16_t)((msg[i] >> j) & 1);
113 r->coeffs[8 * i + j] = mask & ((S2N_KYBER_512_R3_Q + 1) / 2);
114 }
115 }
116 }
117
118 /*************************************************
119 * Name: poly_tomsg
120 *
121 * Description: Convert polynomial to 32-byte message
122 *
123 * Arguments: - uint8_t *msg: pointer to output message
124 * - poly *a: pointer to input polynomial
125 **************************************************/
poly_tomsg(uint8_t msg[S2N_KYBER_512_R3_INDCPA_MSGBYTES],poly * a)126 void poly_tomsg(uint8_t msg[S2N_KYBER_512_R3_INDCPA_MSGBYTES], poly *a) {
127 unsigned int i, j;
128 uint16_t t;
129
130 poly_csubq(a);
131
132 for (i = 0; i < S2N_KYBER_512_R3_N / 8; i++) {
133 msg[i] = 0;
134 for (j = 0; j < 8; j++) {
135 t = ((((uint16_t)a->coeffs[8 * i + j] << 1) + S2N_KYBER_512_R3_Q / 2) / S2N_KYBER_512_R3_Q) & 1;
136 msg[i] |= t << j;
137 }
138 }
139 }
140
141 /*************************************************
142 * Name: poly_getnoise_eta1
143 *
144 * Description: Sample a polynomial deterministically from a seed and a nonce,
145 * with output polynomial close to centered binomial distribution
146 * with parameter S2N_KYBER_512_R3_ETA1
147 *
148 * Arguments: - poly *r: pointer to output polynomial
149 * - const uint8_t *seed: pointer to input seed
150 * (of length S2N_KYBER_512_R3_SYMBYTES bytes)
151 * - uint8_t nonce: one-byte input nonce
152 **************************************************/
poly_getnoise_eta1(poly * r,const uint8_t seed[S2N_KYBER_512_R3_SYMBYTES],uint8_t nonce)153 void poly_getnoise_eta1(poly *r, const uint8_t seed[S2N_KYBER_512_R3_SYMBYTES], uint8_t nonce) {
154 uint8_t buf[S2N_KYBER_512_R3_ETA1 * S2N_KYBER_512_R3_N / 4];
155 shake256_prf(buf, sizeof(buf), seed, nonce);
156 cbd_eta1(r, buf);
157 }
158
159 /*************************************************
160 * Name: poly_getnoise_eta2
161 *
162 * Description: Sample a polynomial deterministically from a seed and a nonce,
163 * with output polynomial close to centered binomial distribution
164 * with parameter S2N_KYBER_512_R3_ETA2
165 *
166 * Arguments: - poly *r: pointer to output polynomial
167 * - const uint8_t *seed: pointer to input seed
168 * (of length S2N_KYBER_512_R3_SYMBYTES bytes)
169 * - uint8_t nonce: one-byte input nonce
170 **************************************************/
poly_getnoise_eta2(poly * r,const uint8_t seed[S2N_KYBER_512_R3_SYMBYTES],uint8_t nonce)171 void poly_getnoise_eta2(poly *r, const uint8_t seed[S2N_KYBER_512_R3_SYMBYTES], uint8_t nonce) {
172 uint8_t buf[S2N_KYBER_512_R3_ETA2 * S2N_KYBER_512_R3_N / 4];
173 shake256_prf(buf, sizeof(buf), seed, nonce);
174 cbd_eta2(r, buf);
175 }
176
177
178 /*************************************************
179 * Name: poly_ntt
180 *
181 * Description: Computes negacyclic number-theoretic transform (NTT) of
182 * a polynomial in place;
183 * inputs assumed to be in normal order, output in bitreversed order
184 *
185 * Arguments: - uint16_t *r: pointer to in/output polynomial
186 **************************************************/
poly_ntt(poly * r)187 void poly_ntt(poly *r) {
188 ntt(r->coeffs);
189 poly_reduce(r);
190 }
191
192 /*************************************************
193 * Name: poly_invntt_tomont
194 *
195 * Description: Computes inverse of negacyclic number-theoretic transform (NTT)
196 * of a polynomial in place;
197 * inputs assumed to be in bitreversed order, output in normal order
198 *
199 * Arguments: - uint16_t *a: pointer to in/output polynomial
200 **************************************************/
poly_invntt_tomont(poly * r)201 void poly_invntt_tomont(poly *r) {
202 invntt(r->coeffs);
203 }
204
205 /*************************************************
206 * Name: poly_basemul_montgomery
207 *
208 * Description: Multiplication of two polynomials in NTT domain
209 *
210 * Arguments: - poly *r: pointer to output polynomial
211 * - const poly *a: pointer to first input polynomial
212 * - const poly *b: pointer to second input polynomial
213 **************************************************/
poly_basemul_montgomery(poly * r,const poly * a,const poly * b)214 void poly_basemul_montgomery(poly *r, const poly *a, const poly *b) {
215 unsigned int i;
216 for (i = 0; i < S2N_KYBER_512_R3_N / 4; i++) {
217 basemul(&r->coeffs[4 * i], &a->coeffs[4 * i], &b->coeffs[4 * i], zetas[64 + i]);
218 basemul(&r->coeffs[4 * i + 2], &a->coeffs[4 * i + 2], &b->coeffs[4 * i + 2],
219 -zetas[64 + i]);
220 }
221 }
222
223 /*************************************************
224 * Name: poly_tomont
225 *
226 * Description: Inplace conversion of all coefficients of a polynomial
227 * from normal domain to Montgomery domain
228 *
229 * Arguments: - poly *r: pointer to input/output polynomial
230 **************************************************/
poly_tomont(poly * r)231 void poly_tomont(poly *r) {
232 unsigned int i;
233 const int16_t f = (1ULL << 32) % S2N_KYBER_512_R3_Q;
234 for (i = 0; i < S2N_KYBER_512_R3_N; i++) {
235 r->coeffs[i] = montgomery_reduce((int32_t)r->coeffs[i] * f);
236 }
237 }
238
239 /*************************************************
240 * Name: poly_reduce
241 *
242 * Description: Applies Barrett reduction to all coefficients of a polynomial
243 * for details of the Barrett reduction see comments in reduce.c
244 *
245 * Arguments: - poly *r: pointer to input/output polynomial
246 **************************************************/
poly_reduce(poly * r)247 void poly_reduce(poly *r) {
248 unsigned int i;
249 for (i = 0; i < S2N_KYBER_512_R3_N; i++) {
250 r->coeffs[i] = barrett_reduce(r->coeffs[i]);
251 }
252 }
253
254 /*************************************************
255 * Name: poly_csubq
256 *
257 * Description: Applies conditional subtraction of q to each coefficient
258 * of a polynomial. For details of conditional subtraction
259 * of q see comments in reduce.c
260 *
261 * Arguments: - poly *r: pointer to input/output polynomial
262 **************************************************/
poly_csubq(poly * r)263 void poly_csubq(poly *r) {
264 unsigned int i;
265 for (i = 0; i < S2N_KYBER_512_R3_N; i++) {
266 r->coeffs[i] = csubq(r->coeffs[i]);
267 }
268 }
269
270 /*************************************************
271 * Name: poly_add
272 *
273 * Description: Add two polynomials
274 *
275 * Arguments: - poly *r: pointer to output polynomial
276 * - const poly *a: pointer to first input polynomial
277 * - const poly *b: pointer to second input polynomial
278 **************************************************/
poly_add(poly * r,const poly * a,const poly * b)279 void poly_add(poly *r, const poly *a, const poly *b) {
280 unsigned int i;
281 for (i = 0; i < S2N_KYBER_512_R3_N; i++) {
282 r->coeffs[i] = a->coeffs[i] + b->coeffs[i];
283 }
284 }
285
286 /*************************************************
287 * Name: poly_sub
288 *
289 * Description: Subtract two polynomials
290 *
291 * Arguments: - poly *r: pointer to output polynomial
292 * - const poly *a: pointer to first input polynomial
293 * - const poly *b: pointer to second input polynomial
294 **************************************************/
poly_sub(poly * r,const poly * a,const poly * b)295 void poly_sub(poly *r, const poly *a, const poly *b) {
296 unsigned int i;
297 for (i = 0; i < S2N_KYBER_512_R3_N; i++) {
298 r->coeffs[i] = a->coeffs[i] - b->coeffs[i];
299 }
300 }
301