1 #include "indcpa.h"
2 #include "ntt.h"
3 #include "params.h"
4 #include "poly.h"
5 #include "polyvec.h"
6 #include "../s2n_pq_random.h"
7 #include "utils/s2n_safety.h"
8 #include "symmetric.h"
9
10 #include <stdint.h>
11
12 /*************************************************
13 * Name: pack_pk
14 *
15 * Description: Serialize the public key as concatenation of the
16 * serialized vector of polynomials pk
17 * and the public seed used to generate the matrix A.
18 *
19 * Arguments: uint8_t *r: pointer to the output serialized public key
20 * const poly *pk: pointer to the input public-key polynomial
21 * const uint8_t *seed: pointer to the input public seed
22 **************************************************/
pack_pk(uint8_t * r,polyvec * pk,const uint8_t * seed)23 static void pack_pk(uint8_t *r, polyvec *pk, const uint8_t *seed) {
24 PQCLEAN_KYBER512_CLEAN_polyvec_tobytes(r, pk);
25 for (size_t i = 0; i < KYBER_SYMBYTES; i++) {
26 r[i + KYBER_POLYVECBYTES] = seed[i];
27 }
28 }
29
30 /*************************************************
31 * Name: unpack_pk
32 *
33 * Description: De-serialize public key from a byte array;
34 * approximate inverse of pack_pk
35 *
36 * Arguments: - polyvec *pk: pointer to output public-key vector of polynomials
37 * - uint8_t *seed: pointer to output seed to generate matrix A
38 * - const uint8_t *packedpk: pointer to input serialized public key
39 **************************************************/
unpack_pk(polyvec * pk,uint8_t * seed,const uint8_t * packedpk)40 static void unpack_pk(polyvec *pk, uint8_t *seed, const uint8_t *packedpk) {
41 PQCLEAN_KYBER512_CLEAN_polyvec_frombytes(pk, packedpk);
42 for (size_t i = 0; i < KYBER_SYMBYTES; i++) {
43 seed[i] = packedpk[i + KYBER_POLYVECBYTES];
44 }
45 }
46
47 /*************************************************
48 * Name: pack_sk
49 *
50 * Description: Serialize the secret key
51 *
52 * Arguments: - uint8_t *r: pointer to output serialized secret key
53 * - const polyvec *sk: pointer to input vector of polynomials (secret key)
54 **************************************************/
pack_sk(uint8_t * r,polyvec * sk)55 static void pack_sk(uint8_t *r, polyvec *sk) {
56 PQCLEAN_KYBER512_CLEAN_polyvec_tobytes(r, sk);
57 }
58
59 /*************************************************
60 * Name: unpack_sk
61 *
62 * Description: De-serialize the secret key;
63 * inverse of pack_sk
64 *
65 * Arguments: - polyvec *sk: pointer to output vector of polynomials (secret key)
66 * - const uint8_t *packedsk: pointer to input serialized secret key
67 **************************************************/
unpack_sk(polyvec * sk,const uint8_t * packedsk)68 static void unpack_sk(polyvec *sk, const uint8_t *packedsk) {
69 PQCLEAN_KYBER512_CLEAN_polyvec_frombytes(sk, packedsk);
70 }
71
72 /*************************************************
73 * Name: pack_ciphertext
74 *
75 * Description: Serialize the ciphertext as concatenation of the
76 * compressed and serialized vector of polynomials b
77 * and the compressed and serialized polynomial v
78 *
79 * Arguments: uint8_t *r: pointer to the output serialized ciphertext
80 * const poly *pk: pointer to the input vector of polynomials b
81 * const uint8_t *seed: pointer to the input polynomial v
82 **************************************************/
pack_ciphertext(uint8_t * r,polyvec * b,poly * v)83 static void pack_ciphertext(uint8_t *r, polyvec *b, poly *v) {
84 PQCLEAN_KYBER512_CLEAN_polyvec_compress(r, b);
85 PQCLEAN_KYBER512_CLEAN_poly_compress(r + KYBER_POLYVECCOMPRESSEDBYTES, v);
86 }
87
88 /*************************************************
89 * Name: unpack_ciphertext
90 *
91 * Description: De-serialize and decompress ciphertext from a byte array;
92 * approximate inverse of pack_ciphertext
93 *
94 * Arguments: - polyvec *b: pointer to the output vector of polynomials b
95 * - poly *v: pointer to the output polynomial v
96 * - const uint8_t *c: pointer to the input serialized ciphertext
97 **************************************************/
unpack_ciphertext(polyvec * b,poly * v,const uint8_t * c)98 static void unpack_ciphertext(polyvec *b, poly *v, const uint8_t *c) {
99 PQCLEAN_KYBER512_CLEAN_polyvec_decompress(b, c);
100 PQCLEAN_KYBER512_CLEAN_poly_decompress(v, c + KYBER_POLYVECCOMPRESSEDBYTES);
101 }
102
103 /*************************************************
104 * Name: rej_uniform
105 *
106 * Description: Run rejection sampling on uniform random bytes to generate
107 * uniform random integers mod q
108 *
109 * Arguments: - int16_t *r: pointer to output buffer
110 * - size_t len: requested number of 16-bit integers (uniform mod q)
111 * - const uint8_t *buf: pointer to input buffer (assumed to be uniform random bytes)
112 * - size_t buflen: length of input buffer in bytes
113 *
114 * Returns number of sampled 16-bit integers (at most len)
115 **************************************************/
rej_uniform(int16_t * r,size_t len,const uint8_t * buf,size_t buflen)116 static size_t rej_uniform(int16_t *r, size_t len, const uint8_t *buf, size_t buflen) {
117 size_t ctr, pos;
118
119 ctr = pos = 0;
120 while (ctr < len && pos + 2 <= buflen) {
121 uint16_t val = (uint16_t)(buf[pos] | ((uint16_t)buf[pos + 1] << 8));
122 pos += 2;
123
124 if (val < 19 * KYBER_Q) {
125 val -= (uint16_t)((val >> 12) * KYBER_Q); // Barrett reduction
126 r[ctr++] = (int16_t)val;
127 }
128 }
129
130 return ctr;
131 }
132
133 #define gen_a(A,B) gen_matrix(A,B,0)
134 #define gen_at(A,B) gen_matrix(A,B,1)
135
136 /*************************************************
137 * Name: gen_matrix
138 *
139 * Description: Deterministically generate matrix A (or the transpose of A)
140 * from a seed. Entries of the matrix are polynomials that look
141 * uniformly random. Performs rejection sampling on output of
142 * a XOF
143 *
144 * Arguments: - polyvec *a: pointer to ouptput matrix A
145 * - const uint8_t *seed: pointer to input seed
146 * - int transposed: boolean deciding whether A or A^T is generated
147 **************************************************/
148 #define MAXNBLOCKS ((530+XOF_BLOCKBYTES)/XOF_BLOCKBYTES) /* 530 is expected number of required bytes */
gen_matrix(polyvec * a,const uint8_t * seed,int transposed)149 static void gen_matrix(polyvec *a, const uint8_t *seed, int transposed) {
150 size_t ctr;
151 uint8_t i, j;
152 uint8_t buf[XOF_BLOCKBYTES * MAXNBLOCKS + 1];
153 xof_state state;
154
155 for (i = 0; i < KYBER_K; i++) {
156 for (j = 0; j < KYBER_K; j++) {
157 if (transposed) {
158 xof_absorb(&state, seed, i, j);
159 } else {
160 xof_absorb(&state, seed, j, i);
161 }
162
163 xof_squeezeblocks(buf, MAXNBLOCKS, &state);
164 ctr = rej_uniform(a[i].vec[j].coeffs, KYBER_N, buf, MAXNBLOCKS * XOF_BLOCKBYTES);
165
166 while (ctr < KYBER_N) {
167 xof_squeezeblocks(buf, 1, &state);
168 ctr += rej_uniform(a[i].vec[j].coeffs + ctr, KYBER_N - ctr, buf, XOF_BLOCKBYTES);
169 }
170 xof_ctx_release(&state);
171 }
172 }
173 }
174
175 /*************************************************
176 * Name: indcpa_keypair
177 *
178 * Description: Generates public and private key for the CPA-secure
179 * public-key encryption scheme underlying Kyber
180 *
181 * Arguments: - uint8_t *pk: pointer to output public key (of length KYBER_INDCPA_PUBLICKEYBYTES bytes)
182 * - uint8_t *sk: pointer to output private key (of length KYBER_INDCPA_SECRETKEYBYTES bytes)
183 **************************************************/
PQCLEAN_KYBER512_CLEAN_indcpa_keypair(uint8_t * pk,uint8_t * sk)184 int PQCLEAN_KYBER512_CLEAN_indcpa_keypair(uint8_t *pk, uint8_t *sk) {
185 polyvec a[KYBER_K], e, pkpv, skpv;
186 uint8_t buf[2 * KYBER_SYMBYTES];
187 uint8_t *publicseed = buf;
188 uint8_t *noiseseed = buf + KYBER_SYMBYTES;
189 uint8_t nonce = 0;
190
191 POSIX_GUARD_RESULT(s2n_get_random_bytes(buf, KYBER_SYMBYTES));
192 hash_g(buf, buf, KYBER_SYMBYTES);
193
194 gen_a(a, publicseed);
195
196 for (size_t i = 0; i < KYBER_K; i++) {
197 PQCLEAN_KYBER512_CLEAN_poly_getnoise(skpv.vec + i, noiseseed, nonce++);
198 }
199 for (size_t i = 0; i < KYBER_K; i++) {
200 PQCLEAN_KYBER512_CLEAN_poly_getnoise(e.vec + i, noiseseed, nonce++);
201 }
202
203 PQCLEAN_KYBER512_CLEAN_polyvec_ntt(&skpv);
204 PQCLEAN_KYBER512_CLEAN_polyvec_ntt(&e);
205
206 // matrix-vector multiplication
207 for (size_t i = 0; i < KYBER_K; i++) {
208 PQCLEAN_KYBER512_CLEAN_polyvec_pointwise_acc(&pkpv.vec[i], &a[i], &skpv);
209 PQCLEAN_KYBER512_CLEAN_poly_frommont(&pkpv.vec[i]);
210 }
211
212 PQCLEAN_KYBER512_CLEAN_polyvec_add(&pkpv, &pkpv, &e);
213 PQCLEAN_KYBER512_CLEAN_polyvec_reduce(&pkpv);
214
215 pack_sk(sk, &skpv);
216 pack_pk(pk, &pkpv, publicseed);
217 return 0;
218 }
219
220 /*************************************************
221 * Name: indcpa_enc
222 *
223 * Description: Encryption function of the CPA-secure
224 * public-key encryption scheme underlying Kyber.
225 *
226 * Arguments: - uint8_t *c: pointer to output ciphertext (of length KYBER_INDCPA_BYTES bytes)
227 * - const uint8_t *m: pointer to input message (of length KYBER_INDCPA_MSGBYTES bytes)
228 * - const uint8_t *pk: pointer to input public key (of length KYBER_INDCPA_PUBLICKEYBYTES bytes)
229 * - const uint8_t *coin: pointer to input random coins used as seed (of length KYBER_SYMBYTES bytes)
230 * to deterministically generate all randomness
231 **************************************************/
PQCLEAN_KYBER512_CLEAN_indcpa_enc(uint8_t * c,const uint8_t * m,const uint8_t * pk,const uint8_t * coins)232 void PQCLEAN_KYBER512_CLEAN_indcpa_enc(uint8_t *c,
233 const uint8_t *m,
234 const uint8_t *pk,
235 const uint8_t *coins) {
236 polyvec sp, pkpv, ep, at[KYBER_K], bp;
237 poly v, k, epp;
238 uint8_t seed[KYBER_SYMBYTES];
239 uint8_t nonce = 0;
240
241 unpack_pk(&pkpv, seed, pk);
242 PQCLEAN_KYBER512_CLEAN_poly_frommsg(&k, m);
243 gen_at(at, seed);
244
245 for (size_t i = 0; i < KYBER_K; i++) {
246 PQCLEAN_KYBER512_CLEAN_poly_getnoise(sp.vec + i, coins, nonce++);
247 }
248 for (size_t i = 0; i < KYBER_K; i++) {
249 PQCLEAN_KYBER512_CLEAN_poly_getnoise(ep.vec + i, coins, nonce++);
250 }
251 PQCLEAN_KYBER512_CLEAN_poly_getnoise(&epp, coins, nonce++);
252
253 PQCLEAN_KYBER512_CLEAN_polyvec_ntt(&sp);
254
255 // matrix-vector multiplication
256 for (size_t i = 0; i < KYBER_K; i++) {
257 PQCLEAN_KYBER512_CLEAN_polyvec_pointwise_acc(&bp.vec[i], &at[i], &sp);
258 }
259
260 PQCLEAN_KYBER512_CLEAN_polyvec_pointwise_acc(&v, &pkpv, &sp);
261
262 PQCLEAN_KYBER512_CLEAN_polyvec_invntt(&bp);
263 PQCLEAN_KYBER512_CLEAN_poly_invntt(&v);
264
265 PQCLEAN_KYBER512_CLEAN_polyvec_add(&bp, &bp, &ep);
266 PQCLEAN_KYBER512_CLEAN_poly_add(&v, &v, &epp);
267 PQCLEAN_KYBER512_CLEAN_poly_add(&v, &v, &k);
268 PQCLEAN_KYBER512_CLEAN_polyvec_reduce(&bp);
269 PQCLEAN_KYBER512_CLEAN_poly_reduce(&v);
270
271 pack_ciphertext(c, &bp, &v);
272 }
273
274 /*************************************************
275 * Name: indcpa_dec
276 *
277 * Description: Decryption function of the CPA-secure
278 * public-key encryption scheme underlying Kyber.
279 *
280 * Arguments: - uint8_t *m: pointer to output decrypted message (of length KYBER_INDCPA_MSGBYTES)
281 * - const uint8_t *c: pointer to input ciphertext (of length KYBER_INDCPA_BYTES)
282 * - const uint8_t *sk: pointer to input secret key (of length KYBER_INDCPA_SECRETKEYBYTES)
283 **************************************************/
PQCLEAN_KYBER512_CLEAN_indcpa_dec(uint8_t * m,const uint8_t * c,const uint8_t * sk)284 void PQCLEAN_KYBER512_CLEAN_indcpa_dec(uint8_t *m,
285 const uint8_t *c,
286 const uint8_t *sk) {
287 polyvec bp, skpv;
288 poly v, mp;
289
290 unpack_ciphertext(&bp, &v, c);
291 unpack_sk(&skpv, sk);
292
293 PQCLEAN_KYBER512_CLEAN_polyvec_ntt(&bp);
294 PQCLEAN_KYBER512_CLEAN_polyvec_pointwise_acc(&mp, &skpv, &bp);
295 PQCLEAN_KYBER512_CLEAN_poly_invntt(&mp);
296
297 PQCLEAN_KYBER512_CLEAN_poly_sub(&mp, &v, &mp);
298 PQCLEAN_KYBER512_CLEAN_poly_reduce(&mp);
299
300 PQCLEAN_KYBER512_CLEAN_poly_tomsg(m, &mp);
301 }
302