aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/restricted/aws/s2n/pq-crypto/kyber_90s_r2/indcpa.c
blob: c37548326d2094a98392cba2ff2e0773cec39472 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
#include "indcpa.h"
#include "ntt.h"
#include "params.h"
#include "poly.h"
#include "polyvec.h"
#include "../s2n_pq_random.h"
#include "utils/s2n_safety.h"
#include "symmetric.h"

#include <stdint.h>

/*************************************************
* Name:        pack_pk
*
* Description: Serialize the public key as concatenation of the
*              serialized vector of polynomials pk
*              and the public seed used to generate the matrix A.
*
* Arguments:   uint8_t *r:          pointer to the output serialized public key
*              const poly *pk:            pointer to the input public-key polynomial
*              const uint8_t *seed: pointer to the input public seed
**************************************************/
static void pack_pk(uint8_t *r, polyvec *pk, const uint8_t *seed) {
    PQCLEAN_KYBER51290S_CLEAN_polyvec_tobytes(r, pk);
    for (size_t i = 0; i < KYBER_SYMBYTES; i++) {
        r[i + KYBER_POLYVECBYTES] = seed[i];
    }
}

/*************************************************
* Name:        unpack_pk
*
* Description: De-serialize public key from a byte array;
*              approximate inverse of pack_pk
*
* Arguments:   - polyvec *pk:                   pointer to output public-key vector of polynomials
*              - uint8_t *seed:           pointer to output seed to generate matrix A
*              - const uint8_t *packedpk: pointer to input serialized public key
**************************************************/
static void unpack_pk(polyvec *pk, uint8_t *seed, const uint8_t *packedpk) {
    PQCLEAN_KYBER51290S_CLEAN_polyvec_frombytes(pk, packedpk);
    for (size_t i = 0; i < KYBER_SYMBYTES; i++) {
        seed[i] = packedpk[i + KYBER_POLYVECBYTES];
    }
}

/*************************************************
* Name:        pack_sk
*
* Description: Serialize the secret key
*
* Arguments:   - uint8_t *r:  pointer to output serialized secret key
*              - const polyvec *sk: pointer to input vector of polynomials (secret key)
**************************************************/
static void pack_sk(uint8_t *r, polyvec *sk) {
    PQCLEAN_KYBER51290S_CLEAN_polyvec_tobytes(r, sk);
}

/*************************************************
* Name:        unpack_sk
*
* Description: De-serialize the secret key;
*              inverse of pack_sk
*
* Arguments:   - polyvec *sk:                   pointer to output vector of polynomials (secret key)
*              - const uint8_t *packedsk: pointer to input serialized secret key
**************************************************/
static void unpack_sk(polyvec *sk, const uint8_t *packedsk) {
    PQCLEAN_KYBER51290S_CLEAN_polyvec_frombytes(sk, packedsk);
}

/*************************************************
* Name:        pack_ciphertext
*
* Description: Serialize the ciphertext as concatenation of the
*              compressed and serialized vector of polynomials b
*              and the compressed and serialized polynomial v
*
* Arguments:   uint8_t *r:          pointer to the output serialized ciphertext
*              const poly *pk:            pointer to the input vector of polynomials b
*              const uint8_t *seed: pointer to the input polynomial v
**************************************************/
static void pack_ciphertext(uint8_t *r, polyvec *b, poly *v) {
    PQCLEAN_KYBER51290S_CLEAN_polyvec_compress(r, b);
    PQCLEAN_KYBER51290S_CLEAN_poly_compress(r + KYBER_POLYVECCOMPRESSEDBYTES, v);
}

/*************************************************
* Name:        unpack_ciphertext
*
* Description: De-serialize and decompress ciphertext from a byte array;
*              approximate inverse of pack_ciphertext
*
* Arguments:   - polyvec *b:             pointer to the output vector of polynomials b
*              - poly *v:                pointer to the output polynomial v
*              - const uint8_t *c: pointer to the input serialized ciphertext
**************************************************/
static void unpack_ciphertext(polyvec *b, poly *v, const uint8_t *c) {
    PQCLEAN_KYBER51290S_CLEAN_polyvec_decompress(b, c);
    PQCLEAN_KYBER51290S_CLEAN_poly_decompress(v, c + KYBER_POLYVECCOMPRESSEDBYTES);
}

/*************************************************
* Name:        rej_uniform
*
* Description: Run rejection sampling on uniform random bytes to generate
*              uniform random integers mod q
*
* Arguments:   - int16_t *r:               pointer to output buffer
*              - size_t len:               requested number of 16-bit integers (uniform mod q)
*              - const uint8_t *buf:       pointer to input buffer (assumed to be uniform random bytes)
*              - size_t buflen:            length of input buffer in bytes
*
* Returns number of sampled 16-bit integers (at most len)
**************************************************/
static size_t rej_uniform(int16_t *r, size_t len, const uint8_t *buf, size_t buflen) {
    size_t ctr, pos;

    ctr = pos = 0;
    while (ctr < len && pos + 2 <= buflen) {
        uint16_t val = (uint16_t)(buf[pos] | ((uint16_t)buf[pos + 1] << 8));
        pos += 2;

        if (val < 19 * KYBER_Q) {
            val -= (uint16_t)((val >> 12) * KYBER_Q); // Barrett reduction
            r[ctr++] = (int16_t)val;
        }
    }

    return ctr;
}

#define gen_a(A,B)  gen_matrix(A,B,0)
#define gen_at(A,B) gen_matrix(A,B,1)

/*************************************************
* Name:        gen_matrix
*
* Description: Deterministically generate matrix A (or the transpose of A)
*              from a seed. Entries of the matrix are polynomials that look
*              uniformly random. Performs rejection sampling on output of
*              a XOF
*
* Arguments:   - polyvec *a:                pointer to ouptput matrix A
*              - const uint8_t *seed: pointer to input seed
*              - int transposed:            boolean deciding whether A or A^T is generated
**************************************************/
#define MAXNBLOCKS ((530+XOF_BLOCKBYTES)/XOF_BLOCKBYTES) /* 530 is expected number of required bytes */
static void gen_matrix(polyvec *a, const uint8_t *seed, int transposed) {
    size_t ctr;
    uint8_t i, j;
    uint8_t buf[XOF_BLOCKBYTES * MAXNBLOCKS + 1];
    xof_state state;

    for (i = 0; i < KYBER_K; i++) {
        for (j = 0; j < KYBER_K; j++) {
            if (transposed) {
                xof_absorb(&state, seed, i, j);
            } else {
                xof_absorb(&state, seed, j, i);
            }

            xof_squeezeblocks(buf, MAXNBLOCKS, &state);
            ctr = rej_uniform(a[i].vec[j].coeffs, KYBER_N, buf, MAXNBLOCKS * XOF_BLOCKBYTES);

            while (ctr < KYBER_N) {
                xof_squeezeblocks(buf, 1, &state);
                ctr += rej_uniform(a[i].vec[j].coeffs + ctr, KYBER_N - ctr, buf, XOF_BLOCKBYTES);
            }
            xof_ctx_release(&state);
        }
    }
}

/*************************************************
* Name:        indcpa_keypair
*
* Description: Generates public and private key for the CPA-secure
*              public-key encryption scheme underlying Kyber
*
* Arguments:   - uint8_t *pk: pointer to output public key (of length KYBER_INDCPA_PUBLICKEYBYTES bytes)
*              - uint8_t *sk: pointer to output private key (of length KYBER_INDCPA_SECRETKEYBYTES bytes)
**************************************************/
int PQCLEAN_KYBER51290S_CLEAN_indcpa_keypair(uint8_t *pk, uint8_t *sk) {
    polyvec a[KYBER_K], e, pkpv, skpv;
    uint8_t buf[2 * KYBER_SYMBYTES];
    uint8_t *publicseed = buf;
    uint8_t *noiseseed = buf + KYBER_SYMBYTES;
    uint8_t nonce = 0;

    GUARD_AS_POSIX(s2n_get_random_bytes(buf, KYBER_SYMBYTES));
    hash_g(buf, buf, KYBER_SYMBYTES);

    gen_a(a, publicseed);

    for (size_t i = 0; i < KYBER_K; i++) {
        PQCLEAN_KYBER51290S_CLEAN_poly_getnoise(skpv.vec + i, noiseseed, nonce++);
    }
    for (size_t i = 0; i < KYBER_K; i++) {
        PQCLEAN_KYBER51290S_CLEAN_poly_getnoise(e.vec + i, noiseseed, nonce++);
    }

    PQCLEAN_KYBER51290S_CLEAN_polyvec_ntt(&skpv);
    PQCLEAN_KYBER51290S_CLEAN_polyvec_ntt(&e);

    // matrix-vector multiplication
    for (size_t i = 0; i < KYBER_K; i++) {
        PQCLEAN_KYBER51290S_CLEAN_polyvec_pointwise_acc(&pkpv.vec[i], &a[i], &skpv);
        PQCLEAN_KYBER51290S_CLEAN_poly_frommont(&pkpv.vec[i]);
    }

    PQCLEAN_KYBER51290S_CLEAN_polyvec_add(&pkpv, &pkpv, &e);
    PQCLEAN_KYBER51290S_CLEAN_polyvec_reduce(&pkpv);

    pack_sk(sk, &skpv);
    pack_pk(pk, &pkpv, publicseed);
    return 0;
}

/*************************************************
* Name:        indcpa_enc
*
* Description: Encryption function of the CPA-secure
*              public-key encryption scheme underlying Kyber.
*
* Arguments:   - uint8_t *c:          pointer to output ciphertext (of length KYBER_INDCPA_BYTES bytes)
*              - const uint8_t *m:    pointer to input message (of length KYBER_INDCPA_MSGBYTES bytes)
*              - const uint8_t *pk:   pointer to input public key (of length KYBER_INDCPA_PUBLICKEYBYTES bytes)
*              - const uint8_t *coin: pointer to input random coins used as seed (of length KYBER_SYMBYTES bytes)
*                                           to deterministically generate all randomness
**************************************************/
void PQCLEAN_KYBER51290S_CLEAN_indcpa_enc(uint8_t *c,
        const uint8_t *m,
        const uint8_t *pk,
        const uint8_t *coins) {
    polyvec sp, pkpv, ep, at[KYBER_K], bp;
    poly v, k, epp;
    uint8_t seed[KYBER_SYMBYTES];
    uint8_t nonce = 0;

    unpack_pk(&pkpv, seed, pk);
    PQCLEAN_KYBER51290S_CLEAN_poly_frommsg(&k, m);
    gen_at(at, seed);

    for (size_t i = 0; i < KYBER_K; i++) {
        PQCLEAN_KYBER51290S_CLEAN_poly_getnoise(sp.vec + i, coins, nonce++);
    }
    for (size_t i = 0; i < KYBER_K; i++) {
        PQCLEAN_KYBER51290S_CLEAN_poly_getnoise(ep.vec + i, coins, nonce++);
    }
    PQCLEAN_KYBER51290S_CLEAN_poly_getnoise(&epp, coins, nonce++);

    PQCLEAN_KYBER51290S_CLEAN_polyvec_ntt(&sp);

    // matrix-vector multiplication
    for (size_t i = 0; i < KYBER_K; i++) {
        PQCLEAN_KYBER51290S_CLEAN_polyvec_pointwise_acc(&bp.vec[i], &at[i], &sp);
    }

    PQCLEAN_KYBER51290S_CLEAN_polyvec_pointwise_acc(&v, &pkpv, &sp);

    PQCLEAN_KYBER51290S_CLEAN_polyvec_invntt(&bp);
    PQCLEAN_KYBER51290S_CLEAN_poly_invntt(&v);

    PQCLEAN_KYBER51290S_CLEAN_polyvec_add(&bp, &bp, &ep);
    PQCLEAN_KYBER51290S_CLEAN_poly_add(&v, &v, &epp);
    PQCLEAN_KYBER51290S_CLEAN_poly_add(&v, &v, &k);
    PQCLEAN_KYBER51290S_CLEAN_polyvec_reduce(&bp);
    PQCLEAN_KYBER51290S_CLEAN_poly_reduce(&v);

    pack_ciphertext(c, &bp, &v);
}

/*************************************************
* Name:        indcpa_dec
*
* Description: Decryption function of the CPA-secure
*              public-key encryption scheme underlying Kyber.
*
* Arguments:   - uint8_t *m:        pointer to output decrypted message (of length KYBER_INDCPA_MSGBYTES)
*              - const uint8_t *c:  pointer to input ciphertext (of length KYBER_INDCPA_BYTES)
*              - const uint8_t *sk: pointer to input secret key (of length KYBER_INDCPA_SECRETKEYBYTES)
**************************************************/
void PQCLEAN_KYBER51290S_CLEAN_indcpa_dec(uint8_t *m,
        const uint8_t *c,
        const uint8_t *sk) {
    polyvec bp, skpv;
    poly v, mp;

    unpack_ciphertext(&bp, &v, c);
    unpack_sk(&skpv, sk);

    PQCLEAN_KYBER51290S_CLEAN_polyvec_ntt(&bp);
    PQCLEAN_KYBER51290S_CLEAN_polyvec_pointwise_acc(&mp, &skpv, &bp);
    PQCLEAN_KYBER51290S_CLEAN_poly_invntt(&mp);

    PQCLEAN_KYBER51290S_CLEAN_poly_sub(&mp, &v, &mp);
    PQCLEAN_KYBER51290S_CLEAN_poly_reduce(&mp);

    PQCLEAN_KYBER51290S_CLEAN_poly_tomsg(m, &mp);
}