Source code
Revision control
Copy as Markdown
Other Tools
/*
* SPDX-License-Identifier: Apache-2.0
*
* This file was generated from
*
* Files from that repository are listed here surrounded by
* "* begin: [file] *" and "* end: [file] *" comments.
*
* The following changes have been made:
* - include guards have been removed,
* - include directives have been removed,
* - "#ifdef KYBER90S" blocks have been evaluated with "KYBER90S" undefined,
* - functions outside of kem.c have been made static.
*/
/** begin: ref/LICENSE **
For Keccak and AES we are using public-domain
code from sources and by authors listed in
comments on top of the respective files.
** end: ref/LICENSE **/
/** begin: ref/AUTHORS **
Joppe Bos,
Léo Ducas,
Eike Kiltz,
Tancrède Lepoint,
Vadim Lyubashevsky,
John Schanck,
Peter Schwabe,
Gregor Seiler,
Damien Stehlé
** end: ref/AUTHORS **/
#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#ifdef FREEBL_NO_DEPEND
#include "stubs.h"
#endif
#include "secport.h"
// We need to provide an implementation of randombytes to avoid an unused
// function warning. We don't use the randomized API in freebl, so we'll make
// calling randombytes an error.
static void
randombytes(uint8_t *out, size_t outlen)
{
// this memset is to avoid "maybe-uninitialized" warnings that gcc-11 issues
// for the (unused) crypto_kem_keypair and crypto_kem_enc functions.
memset(out, 0, outlen);
assert(0);
}
/*************************************************
* Name: verify
*
* Description: Compare two arrays for equality in constant time.
*
* Arguments: const uint8_t *a: pointer to first byte array
* const uint8_t *b: pointer to second byte array
* size_t len: length of the byte arrays
*
* Returns 0 if the byte arrays are equal, 1 otherwise
**************************************************/
static int
verify(const uint8_t *a, const uint8_t *b, size_t len)
{
return NSS_SecureMemcmp(a, b, len);
}
/*************************************************
* Name: cmov
*
* Description: Copy len bytes from x to r if b is 1;
* don't modify x if b is 0. Requires b to be in {0,1};
* assumes two's complement representation of negative integers.
* Runs in constant time.
*
* Arguments: uint8_t *r: pointer to output byte array
* const uint8_t *x: pointer to input byte array
* size_t len: Amount of bytes to be copied
* uint8_t b: Condition bit; has to be in {0,1}
**************************************************/
static void
cmov(uint8_t *r, const uint8_t *x, size_t len, uint8_t b)
{
NSS_SecureSelect(r, r, x, len, b);
}
/** begin: ref/params.h **/
#ifndef KYBER_K
#define KYBER_K 3 /* Change this for different security strengths */
#endif
//#define KYBER_90S /* Uncomment this if you want the 90S variant */
/* Don't change parameters below this line */
#if (KYBER_K == 2)
#define KYBER_NAMESPACE(s) pqcrystals_kyber512_ref_##s
#elif (KYBER_K == 3)
#define KYBER_NAMESPACE(s) pqcrystals_kyber768_ref_##s
#elif (KYBER_K == 4)
#define KYBER_NAMESPACE(s) pqcrystals_kyber1024_ref_##s
#else
#error "KYBER_K must be in {2,3,4}"
#endif
#define KYBER_N 256
#define KYBER_Q 3329
#define KYBER_SYMBYTES 32 /* size in bytes of hashes, and seeds */
#define KYBER_SSBYTES 32 /* size in bytes of shared key */
#define KYBER_POLYBYTES 384
#define KYBER_POLYVECBYTES (KYBER_K * KYBER_POLYBYTES)
#if KYBER_K == 2
#define KYBER_ETA1 3
#define KYBER_POLYCOMPRESSEDBYTES 128
#define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320)
#elif KYBER_K == 3
#define KYBER_ETA1 2
#define KYBER_POLYCOMPRESSEDBYTES 128
#define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320)
#elif KYBER_K == 4
#define KYBER_ETA1 2
#define KYBER_POLYCOMPRESSEDBYTES 160
#define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 352)
#endif
#define KYBER_ETA2 2
#define KYBER_INDCPA_MSGBYTES (KYBER_SYMBYTES)
#define KYBER_INDCPA_PUBLICKEYBYTES (KYBER_POLYVECBYTES + KYBER_SYMBYTES)
#define KYBER_INDCPA_SECRETKEYBYTES (KYBER_POLYVECBYTES)
#define KYBER_INDCPA_BYTES (KYBER_POLYVECCOMPRESSEDBYTES + KYBER_POLYCOMPRESSEDBYTES)
#define KYBER_PUBLICKEYBYTES (KYBER_INDCPA_PUBLICKEYBYTES)
/* 32 bytes of additional space to save H(pk) */
#define KYBER_SECRETKEYBYTES (KYBER_INDCPA_SECRETKEYBYTES + KYBER_INDCPA_PUBLICKEYBYTES + 2 * KYBER_SYMBYTES)
#define KYBER_CIPHERTEXTBYTES (KYBER_INDCPA_BYTES)
/** end: ref/params.h **/
/** begin: ref/reduce.h **/
#define MONT -1044 // 2^16 mod q
#define QINV -3327 // q^-1 mod 2^16
#define montgomery_reduce KYBER_NAMESPACE(montgomery_reduce)
static int16_t montgomery_reduce(int32_t a);
#define barrett_reduce KYBER_NAMESPACE(barrett_reduce)
static int16_t barrett_reduce(int16_t a);
/** end: ref/reduce.h **/
/** begin: ref/ntt.h **/
#define zetas KYBER_NAMESPACE(zetas)
extern const int16_t zetas[128];
#define ntt KYBER_NAMESPACE(ntt)
static void ntt(int16_t poly[256]);
#define invntt KYBER_NAMESPACE(invntt)
static void invntt(int16_t poly[256]);
#define basemul KYBER_NAMESPACE(basemul)
static void basemul(int16_t r[2], const int16_t a[2], const int16_t b[2], int16_t zeta);
/** end: ref/ntt.h **/
/** begin: ref/poly.h **/
/*
* Elements of R_q = Z_q[X]/(X^n + 1). Represents polynomial
* coeffs[0] + X*coeffs[1] + X^2*coeffs[2] + ... + X^{n-1}*coeffs[n-1]
*/
typedef struct {
int16_t coeffs[KYBER_N];
} poly;
#define poly_compress KYBER_NAMESPACE(poly_compress)
static void poly_compress(uint8_t r[KYBER_POLYCOMPRESSEDBYTES], const poly *a);
#define poly_decompress KYBER_NAMESPACE(poly_decompress)
static void poly_decompress(poly *r, const uint8_t a[KYBER_POLYCOMPRESSEDBYTES]);
#define poly_tobytes KYBER_NAMESPACE(poly_tobytes)
static void poly_tobytes(uint8_t r[KYBER_POLYBYTES], const poly *a);
#define poly_frombytes KYBER_NAMESPACE(poly_frombytes)
static void poly_frombytes(poly *r, const uint8_t a[KYBER_POLYBYTES]);
#define poly_frommsg KYBER_NAMESPACE(poly_frommsg)
static void poly_frommsg(poly *r, const uint8_t msg[KYBER_INDCPA_MSGBYTES]);
#define poly_tomsg KYBER_NAMESPACE(poly_tomsg)
static void poly_tomsg(uint8_t msg[KYBER_INDCPA_MSGBYTES], const poly *r);
#define poly_getnoise_eta1 KYBER_NAMESPACE(poly_getnoise_eta1)
static void poly_getnoise_eta1(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce);
#define poly_getnoise_eta2 KYBER_NAMESPACE(poly_getnoise_eta2)
static void poly_getnoise_eta2(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce);
#define poly_ntt KYBER_NAMESPACE(poly_ntt)
static void poly_ntt(poly *r);
#define poly_invntt_tomont KYBER_NAMESPACE(poly_invntt_tomont)
static void poly_invntt_tomont(poly *r);
#define poly_basemul_montgomery KYBER_NAMESPACE(poly_basemul_montgomery)
static void poly_basemul_montgomery(poly *r, const poly *a, const poly *b);
#define poly_tomont KYBER_NAMESPACE(poly_tomont)
static void poly_tomont(poly *r);
#define poly_reduce KYBER_NAMESPACE(poly_reduce)
static void poly_reduce(poly *r);
#define poly_add KYBER_NAMESPACE(poly_add)
static void poly_add(poly *r, const poly *a, const poly *b);
#define poly_sub KYBER_NAMESPACE(poly_sub)
static void poly_sub(poly *r, const poly *a, const poly *b);
/** end: ref/poly.h **/
/** begin: ref/cbd.h **/
#define poly_cbd_eta1 KYBER_NAMESPACE(poly_cbd_eta1)
static void poly_cbd_eta1(poly *r, const uint8_t buf[KYBER_ETA1 * KYBER_N / 4]);
#define poly_cbd_eta2 KYBER_NAMESPACE(poly_cbd_eta2)
static void poly_cbd_eta2(poly *r, const uint8_t buf[KYBER_ETA2 * KYBER_N / 4]);
/** end: ref/cbd.h **/
/** begin: ref/polyvec.h **/
typedef struct {
poly vec[KYBER_K];
} polyvec;
#define polyvec_compress KYBER_NAMESPACE(polyvec_compress)
static void polyvec_compress(uint8_t r[KYBER_POLYVECCOMPRESSEDBYTES], const polyvec *a);
#define polyvec_decompress KYBER_NAMESPACE(polyvec_decompress)
static void polyvec_decompress(polyvec *r, const uint8_t a[KYBER_POLYVECCOMPRESSEDBYTES]);
#define polyvec_tobytes KYBER_NAMESPACE(polyvec_tobytes)
static void polyvec_tobytes(uint8_t r[KYBER_POLYVECBYTES], const polyvec *a);
#define polyvec_frombytes KYBER_NAMESPACE(polyvec_frombytes)
static void polyvec_frombytes(polyvec *r, const uint8_t a[KYBER_POLYVECBYTES]);
#define polyvec_ntt KYBER_NAMESPACE(polyvec_ntt)
static void polyvec_ntt(polyvec *r);
#define polyvec_invntt_tomont KYBER_NAMESPACE(polyvec_invntt_tomont)
static void polyvec_invntt_tomont(polyvec *r);
#define polyvec_basemul_acc_montgomery KYBER_NAMESPACE(polyvec_basemul_acc_montgomery)
static void polyvec_basemul_acc_montgomery(poly *r, const polyvec *a, const polyvec *b);
#define polyvec_reduce KYBER_NAMESPACE(polyvec_reduce)
static void polyvec_reduce(polyvec *r);
#define polyvec_add KYBER_NAMESPACE(polyvec_add)
static void polyvec_add(polyvec *r, const polyvec *a, const polyvec *b);
/** end: ref/polyvec.h **/
/** begin: ref/indcpa.h **/
#define gen_matrix KYBER_NAMESPACE(gen_matrix)
static void gen_matrix(polyvec *a, const uint8_t seed[KYBER_SYMBYTES], int transposed);
#define indcpa_keypair_derand KYBER_NAMESPACE(indcpa_keypair_derand)
static void indcpa_keypair_derand(uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES],
const uint8_t coins[KYBER_SYMBYTES]);
#define indcpa_enc KYBER_NAMESPACE(indcpa_enc)
static void indcpa_enc(uint8_t c[KYBER_INDCPA_BYTES],
const uint8_t m[KYBER_INDCPA_MSGBYTES],
const uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
const uint8_t coins[KYBER_SYMBYTES]);
#define indcpa_dec KYBER_NAMESPACE(indcpa_dec)
static void indcpa_dec(uint8_t m[KYBER_INDCPA_MSGBYTES],
const uint8_t c[KYBER_INDCPA_BYTES],
const uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES]);
/** end: ref/indcpa.h **/
/** begin: ref/fips202.h **/
#define SHAKE128_RATE 168
#define SHAKE256_RATE 136
#define SHA3_256_RATE 136
#define SHA3_512_RATE 72
#define FIPS202_NAMESPACE(s) pqcrystals_kyber_fips202_ref_##s
typedef struct {
uint64_t s[25];
unsigned int pos;
} keccak_state;
#define shake128_init FIPS202_NAMESPACE(shake128_init)
void shake128_init(keccak_state *state);
#define shake128_absorb FIPS202_NAMESPACE(shake128_absorb)
void shake128_absorb(keccak_state *state, const uint8_t *in, size_t inlen);
#define shake128_finalize FIPS202_NAMESPACE(shake128_finalize)
void shake128_finalize(keccak_state *state);
#define shake128_squeeze FIPS202_NAMESPACE(shake128_squeeze)
void shake128_squeeze(uint8_t *out, size_t outlen, keccak_state *state);
#define shake128_absorb_once FIPS202_NAMESPACE(shake128_absorb_once)
void shake128_absorb_once(keccak_state *state, const uint8_t *in, size_t inlen);
#define shake128_squeezeblocks FIPS202_NAMESPACE(shake128_squeezeblocks)
void shake128_squeezeblocks(uint8_t *out, size_t nblocks, keccak_state *state);
#define shake256_init FIPS202_NAMESPACE(shake256_init)
void shake256_init(keccak_state *state);
#define shake256_absorb FIPS202_NAMESPACE(shake256_absorb)
void shake256_absorb(keccak_state *state, const uint8_t *in, size_t inlen);
#define shake256_finalize FIPS202_NAMESPACE(shake256_finalize)
void shake256_finalize(keccak_state *state);
#define shake256_squeeze FIPS202_NAMESPACE(shake256_squeeze)
void shake256_squeeze(uint8_t *out, size_t outlen, keccak_state *state);
#define shake256_absorb_once FIPS202_NAMESPACE(shake256_absorb_once)
void shake256_absorb_once(keccak_state *state, const uint8_t *in, size_t inlen);
#define shake256_squeezeblocks FIPS202_NAMESPACE(shake256_squeezeblocks)
void shake256_squeezeblocks(uint8_t *out, size_t nblocks, keccak_state *state);
#define shake128 FIPS202_NAMESPACE(shake128)
void shake128(uint8_t *out, size_t outlen, const uint8_t *in, size_t inlen);
#define shake256 FIPS202_NAMESPACE(shake256)
void shake256(uint8_t *out, size_t outlen, const uint8_t *in, size_t inlen);
#define sha3_256 FIPS202_NAMESPACE(sha3_256)
void sha3_256(uint8_t h[32], const uint8_t *in, size_t inlen);
#define sha3_512 FIPS202_NAMESPACE(sha3_512)
void sha3_512(uint8_t h[64], const uint8_t *in, size_t inlen);
/** end: ref/fips202.h **/
/** begin: ref/symmetric.h **/
typedef keccak_state xof_state;
#define kyber_shake128_absorb KYBER_NAMESPACE(kyber_shake128_absorb)
static void kyber_shake128_absorb(keccak_state *s,
const uint8_t seed[KYBER_SYMBYTES],
uint8_t x,
uint8_t y);
#define kyber_shake256_prf KYBER_NAMESPACE(kyber_shake256_prf)
static void kyber_shake256_prf(uint8_t *out, size_t outlen, const uint8_t key[KYBER_SYMBYTES], uint8_t nonce);
#define XOF_BLOCKBYTES SHAKE128_RATE
#define hash_h(OUT, IN, INBYTES) sha3_256(OUT, IN, INBYTES)
#define hash_g(OUT, IN, INBYTES) sha3_512(OUT, IN, INBYTES)
#define xof_absorb(STATE, SEED, X, Y) kyber_shake128_absorb(STATE, SEED, X, Y)
#define xof_squeezeblocks(OUT, OUTBLOCKS, STATE) shake128_squeezeblocks(OUT, OUTBLOCKS, STATE)
#define prf(OUT, OUTBYTES, KEY, NONCE) kyber_shake256_prf(OUT, OUTBYTES, KEY, NONCE)
#define kdf(OUT, IN, INBYTES) shake256(OUT, KYBER_SSBYTES, IN, INBYTES)
/** end: ref/symmetric.h **/
/** begin: ref/kem.h **/
#define CRYPTO_SECRETKEYBYTES KYBER_SECRETKEYBYTES
#define CRYPTO_PUBLICKEYBYTES KYBER_PUBLICKEYBYTES
#define CRYPTO_CIPHERTEXTBYTES KYBER_CIPHERTEXTBYTES
#define CRYPTO_BYTES KYBER_SSBYTES
#if (KYBER_K == 2)
#define CRYPTO_ALGNAME "Kyber512"
#elif (KYBER_K == 3)
#define CRYPTO_ALGNAME "Kyber768"
#elif (KYBER_K == 4)
#define CRYPTO_ALGNAME "Kyber1024"
#endif
#define crypto_kem_keypair_derand KYBER_NAMESPACE(keypair_derand)
int crypto_kem_keypair_derand(uint8_t *pk, uint8_t *sk, const uint8_t *coins);
#define crypto_kem_keypair KYBER_NAMESPACE(keypair)
int crypto_kem_keypair(uint8_t *pk, uint8_t *sk);
#define crypto_kem_enc_derand KYBER_NAMESPACE(enc_derand)
int crypto_kem_enc_derand(uint8_t *ct, uint8_t *ss, const uint8_t *pk, const uint8_t *coins);
#define crypto_kem_enc KYBER_NAMESPACE(enc)
int crypto_kem_enc(uint8_t *ct, uint8_t *ss, const uint8_t *pk);
#define crypto_kem_dec KYBER_NAMESPACE(dec)
int crypto_kem_dec(uint8_t *ss, const uint8_t *ct, const uint8_t *sk);
/** end: ref/kem.h **/
/** begin: ref/reduce.c **/
/*************************************************
* Name: montgomery_reduce
*
* Description: Montgomery reduction; given a 32-bit integer a, computes
* 16-bit integer congruent to a * R^-1 mod q, where R=2^16
*
* Arguments: - int32_t a: input integer to be reduced;
* has to be in {-q2^15,...,q2^15-1}
*
* Returns: integer in {-q+1,...,q-1} congruent to a * R^-1 modulo q.
**************************************************/
static int16_t
montgomery_reduce(int32_t a)
{
int16_t t;
t = (int16_t)a * QINV;
t = (a - (int32_t)t * KYBER_Q) >> 16;
return t;
}
/*************************************************
* Name: barrett_reduce
*
* Description: Barrett reduction; given a 16-bit integer a, computes
* centered representative congruent to a mod q in {-(q-1)/2,...,(q-1)/2}
*
* Arguments: - int16_t a: input integer to be reduced
*
* Returns: integer in {-(q-1)/2,...,(q-1)/2} congruent to a modulo q.
**************************************************/
static int16_t
barrett_reduce(int16_t a)
{
int16_t t;
const int16_t v = ((1 << 26) + KYBER_Q / 2) / KYBER_Q;
t = ((int32_t)v * a + (1 << 25)) >> 26;
t *= KYBER_Q;
return a - t;
}
/** end: ref/reduce.c **/
/** begin: ref/cbd.c **/
/*************************************************
* Name: load32_littleendian
*
* Description: load 4 bytes into a 32-bit integer
* in little-endian order
*
* Arguments: - const uint8_t *x: pointer to input byte array
*
* Returns 32-bit unsigned integer loaded from x
**************************************************/
static uint32_t
load32_littleendian(const uint8_t x[4])
{
uint32_t r;
r = (uint32_t)x[0];
r |= (uint32_t)x[1] << 8;
r |= (uint32_t)x[2] << 16;
r |= (uint32_t)x[3] << 24;
return r;
}
/*************************************************
* Name: load24_littleendian
*
* Description: load 3 bytes into a 32-bit integer
* in little-endian order.
* This function is only needed for Kyber-512
*
* Arguments: - const uint8_t *x: pointer to input byte array
*
* Returns 32-bit unsigned integer loaded from x (most significant byte is zero)
**************************************************/
#if KYBER_ETA1 == 3
static uint32_t
load24_littleendian(const uint8_t x[3])
{
uint32_t r;
r = (uint32_t)x[0];
r |= (uint32_t)x[1] << 8;
r |= (uint32_t)x[2] << 16;
return r;
}
#endif
/*************************************************
* Name: cbd2
*
* Description: Given an array of uniformly random bytes, compute
* polynomial with coefficients distributed according to
* a centered binomial distribution with parameter eta=2
*
* Arguments: - poly *r: pointer to output polynomial
* - const uint8_t *buf: pointer to input byte array
**************************************************/
static void
cbd2(poly *r, const uint8_t buf[2 * KYBER_N / 4])
{
unsigned int i, j;
uint32_t t, d;
int16_t a, b;
for (i = 0; i < KYBER_N / 8; i++) {
t = load32_littleendian(buf + 4 * i);
d = t & 0x55555555;
d += (t >> 1) & 0x55555555;
for (j = 0; j < 8; j++) {
a = (d >> (4 * j + 0)) & 0x3;
b = (d >> (4 * j + 2)) & 0x3;
r->coeffs[8 * i + j] = a - b;
}
}
}
/*************************************************
* Name: cbd3
*
* Description: Given an array of uniformly random bytes, compute
* polynomial with coefficients distributed according to
* a centered binomial distribution with parameter eta=3.
* This function is only needed for Kyber-512
*
* Arguments: - poly *r: pointer to output polynomial
* - const uint8_t *buf: pointer to input byte array
**************************************************/
#if KYBER_ETA1 == 3
static void
cbd3(poly *r, const uint8_t buf[3 * KYBER_N / 4])
{
unsigned int i, j;
uint32_t t, d;
int16_t a, b;
for (i = 0; i < KYBER_N / 4; i++) {
t = load24_littleendian(buf + 3 * i);
d = t & 0x00249249;
d += (t >> 1) & 0x00249249;
d += (t >> 2) & 0x00249249;
for (j = 0; j < 4; j++) {
a = (d >> (6 * j + 0)) & 0x7;
b = (d >> (6 * j + 3)) & 0x7;
r->coeffs[4 * i + j] = a - b;
}
}
}
#endif
static void
poly_cbd_eta1(poly *r, const uint8_t buf[KYBER_ETA1 * KYBER_N / 4])
{
#if KYBER_ETA1 == 2
cbd2(r, buf);
#elif KYBER_ETA1 == 3
cbd3(r, buf);
#else
#error "This implementation requires eta1 in {2,3}"
#endif
}
static void
poly_cbd_eta2(poly *r, const uint8_t buf[KYBER_ETA2 * KYBER_N / 4])
{
#if KYBER_ETA2 == 2
cbd2(r, buf);
#else
#error "This implementation requires eta2 = 2"
#endif
}
/** end: ref/cbd.c **/
/** begin: ref/ntt.c **/
/* Code to generate zetas and zetas_inv used in the number-theoretic transform:
#define KYBER_ROOT_OF_UNITY 17
static const uint8_t tree[128] = {
0, 64, 32, 96, 16, 80, 48, 112, 8, 72, 40, 104, 24, 88, 56, 120,
4, 68, 36, 100, 20, 84, 52, 116, 12, 76, 44, 108, 28, 92, 60, 124,
2, 66, 34, 98, 18, 82, 50, 114, 10, 74, 42, 106, 26, 90, 58, 122,
6, 70, 38, 102, 22, 86, 54, 118, 14, 78, 46, 110, 30, 94, 62, 126,
1, 65, 33, 97, 17, 81, 49, 113, 9, 73, 41, 105, 25, 89, 57, 121,
5, 69, 37, 101, 21, 85, 53, 117, 13, 77, 45, 109, 29, 93, 61, 125,
3, 67, 35, 99, 19, 83, 51, 115, 11, 75, 43, 107, 27, 91, 59, 123,
7, 71, 39, 103, 23, 87, 55, 119, 15, 79, 47, 111, 31, 95, 63, 127
};
static void init_ntt() {
unsigned int i;
int16_t tmp[128];
tmp[0] = MONT;
for(i=1;i<128;i++)
tmp[i] = fqmul(tmp[i-1],MONT*KYBER_ROOT_OF_UNITY % KYBER_Q);
for(i=0;i<128;i++) {
zetas[i] = tmp[tree[i]];
if(zetas[i] > KYBER_Q/2)
zetas[i] -= KYBER_Q;
if(zetas[i] < -KYBER_Q/2)
zetas[i] += KYBER_Q;
}
}
*/
const int16_t zetas[128] = {
-1044, -758, -359, -1517, 1493, 1422, 287, 202,
-171, 622, 1577, 182, 962, -1202, -1474, 1468,
573, -1325, 264, 383, -829, 1458, -1602, -130,
-681, 1017, 732, 608, -1542, 411, -205, -1571,
1223, 652, -552, 1015, -1293, 1491, -282, -1544,
516, -8, -320, -666, -1618, -1162, 126, 1469,
-853, -90, -271, 830, 107, -1421, -247, -951,
-398, 961, -1508, -725, 448, -1065, 677, -1275,
-1103, 430, 555, 843, -1251, 871, 1550, 105,
422, 587, 177, -235, -291, -460, 1574, 1653,
-246, 778, 1159, -147, -777, 1483, -602, 1119,
-1590, 644, -872, 349, 418, 329, -156, -75,
817, 1097, 603, 610, 1322, -1285, -1465, 384,
-1215, -136, 1218, -1335, -874, 220, -1187, -1659,
-1185, -1530, -1278, 794, -1510, -854, -870, 478,
-108, -308, 996, 991, 958, -1460, 1522, 1628
};
/*************************************************
* Name: fqmul
*
* Description: Multiplication followed by Montgomery reduction
*
* Arguments: - int16_t a: first factor
* - int16_t b: second factor
*
* Returns 16-bit integer congruent to a*b*R^{-1} mod q
**************************************************/
static int16_t
fqmul(int16_t a, int16_t b)
{
return montgomery_reduce((int32_t)a * b);
}
/*************************************************
* Name: ntt
*
* Description: Inplace number-theoretic transform (NTT) in Rq.
* input is in standard order, output is in bitreversed order
*
* Arguments: - int16_t r[256]: pointer to input/output vector of elements of Zq
**************************************************/
static void
ntt(int16_t r[256])
{
unsigned int len, start, j, k;
int16_t t, zeta;
k = 1;
for (len = 128; len >= 2; len >>= 1) {
for (start = 0; start < 256; start = j + len) {
zeta = zetas[k++];
for (j = start; j < start + len; j++) {
t = fqmul(zeta, r[j + len]);
r[j + len] = r[j] - t;
r[j] = r[j] + t;
}
}
}
}
/*************************************************
* Name: invntt_tomont
*
* Description: Inplace inverse number-theoretic transform in Rq and
* multiplication by Montgomery factor 2^16.
* Input is in bitreversed order, output is in standard order
*
* Arguments: - int16_t r[256]: pointer to input/output vector of elements of Zq
**************************************************/
static void
invntt(int16_t r[256])
{
unsigned int start, len, j, k;
int16_t t, zeta;
const int16_t f = 1441; // mont^2/128
k = 127;
for (len = 2; len <= 128; len <<= 1) {
for (start = 0; start < 256; start = j + len) {
zeta = zetas[k--];
for (j = start; j < start + len; j++) {
t = r[j];
r[j] = barrett_reduce(t + r[j + len]);
r[j + len] = r[j + len] - t;
r[j + len] = fqmul(zeta, r[j + len]);
}
}
}
for (j = 0; j < 256; j++)
r[j] = fqmul(r[j], f);
}
/*************************************************
* Name: basemul
*
* Description: Multiplication of polynomials in Zq[X]/(X^2-zeta)
* used for multiplication of elements in Rq in NTT domain
*
* Arguments: - int16_t r[2]: pointer to the output polynomial
* - const int16_t a[2]: pointer to the first factor
* - const int16_t b[2]: pointer to the second factor
* - int16_t zeta: integer defining the reduction polynomial
**************************************************/
static void
basemul(int16_t r[2], const int16_t a[2], const int16_t b[2], int16_t zeta)
{
r[0] = fqmul(a[1], b[1]);
r[0] = fqmul(r[0], zeta);
r[0] += fqmul(a[0], b[0]);
r[1] = fqmul(a[0], b[1]);
r[1] += fqmul(a[1], b[0]);
}
/** end: ref/ntt.c **/
/** begin: ref/poly.c **/
/*************************************************
* Name: poly_compress
*
* Description: Compression and subsequent serialization of a polynomial
*
* Arguments: - uint8_t *r: pointer to output byte array
* (of length KYBER_POLYCOMPRESSEDBYTES)
* - const poly *a: pointer to input polynomial
**************************************************/
static void
poly_compress(uint8_t r[KYBER_POLYCOMPRESSEDBYTES], const poly *a)
{
unsigned int i, j;
int16_t u;
uint32_t d0;
uint8_t t[8];
#if (KYBER_POLYCOMPRESSEDBYTES == 128)
for (i = 0; i < KYBER_N / 8; i++) {
for (j = 0; j < 8; j++) {
// map to positive standard representatives
u = a->coeffs[8 * i + j];
u += (u >> 15) & KYBER_Q;
/* t[j] = ((((uint16_t)u << 4) + KYBER_Q/2)/KYBER_Q) & 15; */
d0 = u << 4;
d0 += 1665;
d0 *= 80635;
d0 >>= 28;
t[j] = d0 & 0xf;
}
r[0] = t[0] | (t[1] << 4);
r[1] = t[2] | (t[3] << 4);
r[2] = t[4] | (t[5] << 4);
r[3] = t[6] | (t[7] << 4);
r += 4;
}
#elif (KYBER_POLYCOMPRESSEDBYTES == 160)
for (i = 0; i < KYBER_N / 8; i++) {
for (j = 0; j < 8; j++) {
// map to positive standard representatives
u = a->coeffs[8 * i + j];
u += (u >> 15) & KYBER_Q;
/* t[j] = ((((uint32_t)u << 5) + KYBER_Q/2)/KYBER_Q) & 31; */
d0 = u << 5;
d0 += 1664;
d0 *= 40318;
d0 >>= 27;
t[j] = d0 & 0x1f;
}
r[0] = (t[0] >> 0) | (t[1] << 5);
r[1] = (t[1] >> 3) | (t[2] << 2) | (t[3] << 7);
r[2] = (t[3] >> 1) | (t[4] << 4);
r[3] = (t[4] >> 4) | (t[5] << 1) | (t[6] << 6);
r[4] = (t[6] >> 2) | (t[7] << 3);
r += 5;
}
#else
#error "KYBER_POLYCOMPRESSEDBYTES needs to be in {128, 160}"
#endif
}
/*************************************************
* Name: poly_decompress
*
* Description: De-serialization and subsequent decompression of a polynomial;
* approximate inverse of poly_compress
*
* Arguments: - poly *r: pointer to output polynomial
* - const uint8_t *a: pointer to input byte array
* (of length KYBER_POLYCOMPRESSEDBYTES bytes)
**************************************************/
static void
poly_decompress(poly *r, const uint8_t a[KYBER_POLYCOMPRESSEDBYTES])
{
unsigned int i;
#if (KYBER_POLYCOMPRESSEDBYTES == 128)
for (i = 0; i < KYBER_N / 2; i++) {
r->coeffs[2 * i + 0] = (((uint16_t)(a[0] & 15) * KYBER_Q) + 8) >> 4;
r->coeffs[2 * i + 1] = (((uint16_t)(a[0] >> 4) * KYBER_Q) + 8) >> 4;
a += 1;
}
#elif (KYBER_POLYCOMPRESSEDBYTES == 160)
unsigned int j;
uint8_t t[8];
for (i = 0; i < KYBER_N / 8; i++) {
t[0] = (a[0] >> 0);
t[1] = (a[0] >> 5) | (a[1] << 3);
t[2] = (a[1] >> 2);
t[3] = (a[1] >> 7) | (a[2] << 1);
t[4] = (a[2] >> 4) | (a[3] << 4);
t[5] = (a[3] >> 1);
t[6] = (a[3] >> 6) | (a[4] << 2);
t[7] = (a[4] >> 3);
a += 5;
for (j = 0; j < 8; j++)
r->coeffs[8 * i + j] = ((uint32_t)(t[j] & 31) * KYBER_Q + 16) >> 5;
}
#else
#error "KYBER_POLYCOMPRESSEDBYTES needs to be in {128, 160}"
#endif
}
/*************************************************
* Name: poly_tobytes
*
* Description: Serialization of a polynomial
*
* Arguments: - uint8_t *r: pointer to output byte array
* (needs space for KYBER_POLYBYTES bytes)
* - const poly *a: pointer to input polynomial
**************************************************/
static void
poly_tobytes(uint8_t r[KYBER_POLYBYTES], const poly *a)
{
unsigned int i;
uint16_t t0, t1;
for (i = 0; i < KYBER_N / 2; i++) {
// map to positive standard representatives
t0 = a->coeffs[2 * i];
t0 += ((int16_t)t0 >> 15) & KYBER_Q;
t1 = a->coeffs[2 * i + 1];
t1 += ((int16_t)t1 >> 15) & KYBER_Q;
r[3 * i + 0] = (t0 >> 0);
r[3 * i + 1] = (t0 >> 8) | (t1 << 4);
r[3 * i + 2] = (t1 >> 4);
}
}
/*************************************************
* Name: poly_frombytes
*
* Description: De-serialization of a polynomial;
* inverse of poly_tobytes
*
* Arguments: - poly *r: pointer to output polynomial
* - const uint8_t *a: pointer to input byte array
* (of KYBER_POLYBYTES bytes)
**************************************************/
static void
poly_frombytes(poly *r, const uint8_t a[KYBER_POLYBYTES])
{
unsigned int i;
for (i = 0; i < KYBER_N / 2; i++) {
r->coeffs[2 * i] = ((a[3 * i + 0] >> 0) | ((uint16_t)a[3 * i + 1] << 8)) & 0xFFF;
r->coeffs[2 * i + 1] = ((a[3 * i + 1] >> 4) | ((uint16_t)a[3 * i + 2] << 4)) & 0xFFF;
}
}
/*************************************************
* Name: poly_frommsg
*
* Description: Convert 32-byte message to polynomial
*
* Arguments: - poly *r: pointer to output polynomial
* - const uint8_t *msg: pointer to input message
**************************************************/
static void
poly_frommsg(poly *r, const uint8_t msg[KYBER_INDCPA_MSGBYTES])
{
unsigned int i, j;
int16_t mask;
#if (KYBER_INDCPA_MSGBYTES != KYBER_N / 8)
#error "KYBER_INDCPA_MSGBYTES must be equal to KYBER_N/8 bytes!"
#endif
for (i = 0; i < KYBER_N / 8; i++) {
for (j = 0; j < 8; j++) {
mask = -(int16_t)((msg[i] >> j) & 1);
r->coeffs[8 * i + j] = mask & ((KYBER_Q + 1) / 2);
}
}
}
/*************************************************
* Name: poly_tomsg
*
* Description: Convert polynomial to 32-byte message
*
* Arguments: - uint8_t *msg: pointer to output message
* - const poly *a: pointer to input polynomial
**************************************************/
static void
poly_tomsg(uint8_t msg[KYBER_INDCPA_MSGBYTES], const poly *a)
{
unsigned int i, j;
uint32_t t;
for (i = 0; i < KYBER_N / 8; i++) {
msg[i] = 0;
for (j = 0; j < 8; j++) {
t = a->coeffs[8 * i + j];
// t += ((int16_t)t >> 15) & KYBER_Q;
// t = (((t << 1) + KYBER_Q/2)/KYBER_Q) & 1;
t <<= 1;
t += 1665;
t *= 80635;
t >>= 28;
t &= 1;
msg[i] |= t << j;
}
}
}
/*************************************************
* Name: poly_getnoise_eta1
*
* Description: Sample a polynomial deterministically from a seed and a nonce,
* with output polynomial close to centered binomial distribution
* with parameter KYBER_ETA1
*
* Arguments: - poly *r: pointer to output polynomial
* - const uint8_t *seed: pointer to input seed
* (of length KYBER_SYMBYTES bytes)
* - uint8_t nonce: one-byte input nonce
**************************************************/
static void
poly_getnoise_eta1(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce)
{
uint8_t buf[KYBER_ETA1 * KYBER_N / 4];
prf(buf, sizeof(buf), seed, nonce);
poly_cbd_eta1(r, buf);
}
/*************************************************
* Name: poly_getnoise_eta2
*
* Description: Sample a polynomial deterministically from a seed and a nonce,
* with output polynomial close to centered binomial distribution
* with parameter KYBER_ETA2
*
* Arguments: - poly *r: pointer to output polynomial
* - const uint8_t *seed: pointer to input seed
* (of length KYBER_SYMBYTES bytes)
* - uint8_t nonce: one-byte input nonce
**************************************************/
static void
poly_getnoise_eta2(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce)
{
uint8_t buf[KYBER_ETA2 * KYBER_N / 4];
prf(buf, sizeof(buf), seed, nonce);
poly_cbd_eta2(r, buf);
}
/*************************************************
* Name: poly_ntt
*
* Description: Computes negacyclic number-theoretic transform (NTT) of
* a polynomial in place;
* inputs assumed to be in normal order, output in bitreversed order
*
* Arguments: - uint16_t *r: pointer to in/output polynomial
**************************************************/
static void
poly_ntt(poly *r)
{
ntt(r->coeffs);
poly_reduce(r);
}
/*************************************************
* Name: poly_invntt_tomont
*
* Description: Computes inverse of negacyclic number-theoretic transform (NTT)
* of a polynomial in place;
* inputs assumed to be in bitreversed order, output in normal order
*
* Arguments: - uint16_t *a: pointer to in/output polynomial
**************************************************/
static void
poly_invntt_tomont(poly *r)
{
invntt(r->coeffs);
}
/*************************************************
* Name: poly_basemul_montgomery
*
* Description: Multiplication of two polynomials in NTT domain
*
* Arguments: - poly *r: pointer to output polynomial
* - const poly *a: pointer to first input polynomial
* - const poly *b: pointer to second input polynomial
**************************************************/
static void
poly_basemul_montgomery(poly *r, const poly *a, const poly *b)
{
unsigned int i;
for (i = 0; i < KYBER_N / 4; i++) {
basemul(&r->coeffs[4 * i], &a->coeffs[4 * i], &b->coeffs[4 * i], zetas[64 + i]);
basemul(&r->coeffs[4 * i + 2], &a->coeffs[4 * i + 2], &b->coeffs[4 * i + 2], -zetas[64 + i]);
}
}
/*************************************************
* Name: poly_tomont
*
* Description: Inplace conversion of all coefficients of a polynomial
* from normal domain to Montgomery domain
*
* Arguments: - poly *r: pointer to input/output polynomial
**************************************************/
static void
poly_tomont(poly *r)
{
unsigned int i;
const int16_t f = (1ULL << 32) % KYBER_Q;
for (i = 0; i < KYBER_N; i++)
r->coeffs[i] = montgomery_reduce((int32_t)r->coeffs[i] * f);
}
/*************************************************
* Name: poly_reduce
*
* Description: Applies Barrett reduction to all coefficients of a polynomial
* for details of the Barrett reduction see comments in reduce.c
*
* Arguments: - poly *r: pointer to input/output polynomial
**************************************************/
static void
poly_reduce(poly *r)
{
unsigned int i;
for (i = 0; i < KYBER_N; i++)
r->coeffs[i] = barrett_reduce(r->coeffs[i]);
}
/*************************************************
* Name: poly_add
*
* Description: Add two polynomials; no modular reduction is performed
*
* Arguments: - poly *r: pointer to output polynomial
* - const poly *a: pointer to first input polynomial
* - const poly *b: pointer to second input polynomial
**************************************************/
static void
poly_add(poly *r, const poly *a, const poly *b)
{
unsigned int i;
for (i = 0; i < KYBER_N; i++)
r->coeffs[i] = a->coeffs[i] + b->coeffs[i];
}
/*************************************************
* Name: poly_sub
*
* Description: Subtract two polynomials; no modular reduction is performed
*
* Arguments: - poly *r: pointer to output polynomial
* - const poly *a: pointer to first input polynomial
* - const poly *b: pointer to second input polynomial
**************************************************/
static void
poly_sub(poly *r, const poly *a, const poly *b)
{
unsigned int i;
for (i = 0; i < KYBER_N; i++)
r->coeffs[i] = a->coeffs[i] - b->coeffs[i];
}
/** end: ref/poly.c **/
/** begin: ref/polyvec.c **/
/*************************************************
* Name: polyvec_compress
*
* Description: Compress and serialize vector of polynomials
*
* Arguments: - uint8_t *r: pointer to output byte array
* (needs space for KYBER_POLYVECCOMPRESSEDBYTES)
* - const polyvec *a: pointer to input vector of polynomials
**************************************************/
static void
polyvec_compress(uint8_t r[KYBER_POLYVECCOMPRESSEDBYTES], const polyvec *a)
{
unsigned int i, j, k;
uint64_t d0;
#if (KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * 352))
uint16_t t[8];
for (i = 0; i < KYBER_K; i++) {
for (j = 0; j < KYBER_N / 8; j++) {
for (k = 0; k < 8; k++) {
t[k] = a->vec[i].coeffs[8 * j + k];
t[k] += ((int16_t)t[k] >> 15) & KYBER_Q;
/* t[k] = ((((uint32_t)t[k] << 11) + KYBER_Q/2)/KYBER_Q) & 0x7ff; */
d0 = t[k];
d0 <<= 11;
d0 += 1664;
d0 *= 645084;
d0 >>= 31;
t[k] = d0 & 0x7ff;
}
r[0] = (t[0] >> 0);
r[1] = (t[0] >> 8) | (t[1] << 3);
r[2] = (t[1] >> 5) | (t[2] << 6);
r[3] = (t[2] >> 2);
r[4] = (t[2] >> 10) | (t[3] << 1);
r[5] = (t[3] >> 7) | (t[4] << 4);
r[6] = (t[4] >> 4) | (t[5] << 7);
r[7] = (t[5] >> 1);
r[8] = (t[5] >> 9) | (t[6] << 2);
r[9] = (t[6] >> 6) | (t[7] << 5);
r[10] = (t[7] >> 3);
r += 11;
}
}
#elif (KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * 320))
uint16_t t[4];
for (i = 0; i < KYBER_K; i++) {
for (j = 0; j < KYBER_N / 4; j++) {
for (k = 0; k < 4; k++) {
t[k] = a->vec[i].coeffs[4 * j + k];
t[k] += ((int16_t)t[k] >> 15) & KYBER_Q;
/* t[k] = ((((uint32_t)t[k] << 10) + KYBER_Q/2)/ KYBER_Q) & 0x3ff; */
d0 = t[k];
d0 <<= 10;
d0 += 1665;
d0 *= 1290167;
d0 >>= 32;
t[k] = d0 & 0x3ff;
}
r[0] = (t[0] >> 0);
r[1] = (t[0] >> 8) | (t[1] << 2);
r[2] = (t[1] >> 6) | (t[2] << 4);
r[3] = (t[2] >> 4) | (t[3] << 6);
r[4] = (t[3] >> 2);
r += 5;
}
}
#else
#error "KYBER_POLYVECCOMPRESSEDBYTES needs to be in {320*KYBER_K, 352*KYBER_K}"
#endif
}
/*************************************************
* Name: polyvec_decompress
*
* Description: De-serialize and decompress vector of polynomials;
* approximate inverse of polyvec_compress
*
* Arguments: - polyvec *r: pointer to output vector of polynomials
* - const uint8_t *a: pointer to input byte array
* (of length KYBER_POLYVECCOMPRESSEDBYTES)
**************************************************/
static void
polyvec_decompress(polyvec *r, const uint8_t a[KYBER_POLYVECCOMPRESSEDBYTES])
{
unsigned int i, j, k;
#if (KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * 352))
uint16_t t[8];
for (i = 0; i < KYBER_K; i++) {
for (j = 0; j < KYBER_N / 8; j++) {
t[0] = (a[0] >> 0) | ((uint16_t)a[1] << 8);
t[1] = (a[1] >> 3) | ((uint16_t)a[2] << 5);
t[2] = (a[2] >> 6) | ((uint16_t)a[3] << 2) | ((uint16_t)a[4] << 10);
t[3] = (a[4] >> 1) | ((uint16_t)a[5] << 7);
t[4] = (a[5] >> 4) | ((uint16_t)a[6] << 4);
t[5] = (a[6] >> 7) | ((uint16_t)a[7] << 1) | ((uint16_t)a[8] << 9);
t[6] = (a[8] >> 2) | ((uint16_t)a[9] << 6);
t[7] = (a[9] >> 5) | ((uint16_t)a[10] << 3);
a += 11;
for (k = 0; k < 8; k++)
r->vec[i].coeffs[8 * j + k] = ((uint32_t)(t[k] & 0x7FF) * KYBER_Q + 1024) >> 11;
}
}
#elif (KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * 320))
uint16_t t[4];
for (i = 0; i < KYBER_K; i++) {
for (j = 0; j < KYBER_N / 4; j++) {
t[0] = (a[0] >> 0) | ((uint16_t)a[1] << 8);
t[1] = (a[1] >> 2) | ((uint16_t)a[2] << 6);
t[2] = (a[2] >> 4) | ((uint16_t)a[3] << 4);
t[3] = (a[3] >> 6) | ((uint16_t)a[4] << 2);
a += 5;
for (k = 0; k < 4; k++)
r->vec[i].coeffs[4 * j + k] = ((uint32_t)(t[k] & 0x3FF) * KYBER_Q + 512) >> 10;
}
}
#else
#error "KYBER_POLYVECCOMPRESSEDBYTES needs to be in {320*KYBER_K, 352*KYBER_K}"
#endif
}
/*************************************************
* Name: polyvec_tobytes
*
* Description: Serialize vector of polynomials
*
* Arguments: - uint8_t *r: pointer to output byte array
* (needs space for KYBER_POLYVECBYTES)
* - const polyvec *a: pointer to input vector of polynomials
**************************************************/
static void
polyvec_tobytes(uint8_t r[KYBER_POLYVECBYTES], const polyvec *a)
{
unsigned int i;
for (i = 0; i < KYBER_K; i++)
poly_tobytes(r + i * KYBER_POLYBYTES, &a->vec[i]);
}
/*************************************************
* Name: polyvec_frombytes
*
* Description: De-serialize vector of polynomials;
* inverse of polyvec_tobytes
*
* Arguments: - uint8_t *r: pointer to output byte array
* - const polyvec *a: pointer to input vector of polynomials
* (of length KYBER_POLYVECBYTES)
**************************************************/
static void
polyvec_frombytes(polyvec *r, const uint8_t a[KYBER_POLYVECBYTES])
{
unsigned int i;
for (i = 0; i < KYBER_K; i++)
poly_frombytes(&r->vec[i], a + i * KYBER_POLYBYTES);
}
/*************************************************
* Name: polyvec_ntt
*
* Description: Apply forward NTT to all elements of a vector of polynomials
*
* Arguments: - polyvec *r: pointer to in/output vector of polynomials
**************************************************/
static void
polyvec_ntt(polyvec *r)
{
unsigned int i;
for (i = 0; i < KYBER_K; i++)
poly_ntt(&r->vec[i]);
}
/*************************************************
* Name: polyvec_invntt_tomont
*
* Description: Apply inverse NTT to all elements of a vector of polynomials
* and multiply by Montgomery factor 2^16
*
* Arguments: - polyvec *r: pointer to in/output vector of polynomials
**************************************************/
static void
polyvec_invntt_tomont(polyvec *r)
{
unsigned int i;
for (i = 0; i < KYBER_K; i++)
poly_invntt_tomont(&r->vec[i]);
}
/*************************************************
* Name: polyvec_basemul_acc_montgomery
*
* Description: Multiply elements of a and b in NTT domain, accumulate into r,
* and multiply by 2^-16.
*
* Arguments: - poly *r: pointer to output polynomial
* - const polyvec *a: pointer to first input vector of polynomials
* - const polyvec *b: pointer to second input vector of polynomials
**************************************************/
static void
polyvec_basemul_acc_montgomery(poly *r, const polyvec *a, const polyvec *b)
{
unsigned int i;
poly t;
poly_basemul_montgomery(r, &a->vec[0], &b->vec[0]);
for (i = 1; i < KYBER_K; i++) {
poly_basemul_montgomery(&t, &a->vec[i], &b->vec[i]);
poly_add(r, r, &t);
}
poly_reduce(r);
}
/*************************************************
* Name: polyvec_reduce
*
* Description: Applies Barrett reduction to each coefficient
* of each element of a vector of polynomials;
* for details of the Barrett reduction see comments in reduce.c
*
* Arguments: - polyvec *r: pointer to input/output polynomial
**************************************************/
static void
polyvec_reduce(polyvec *r)
{
unsigned int i;
for (i = 0; i < KYBER_K; i++)
poly_reduce(&r->vec[i]);
}
/*************************************************
* Name: polyvec_add
*
* Description: Add vectors of polynomials
*
* Arguments: - polyvec *r: pointer to output vector of polynomials
* - const polyvec *a: pointer to first input vector of polynomials
* - const polyvec *b: pointer to second input vector of polynomials
**************************************************/
static void
polyvec_add(polyvec *r, const polyvec *a, const polyvec *b)
{
unsigned int i;
for (i = 0; i < KYBER_K; i++)
poly_add(&r->vec[i], &a->vec[i], &b->vec[i]);
}
/** end: ref/polyvec.c **/
/** begin: ref/indcpa.c **/
/*************************************************
* 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
* polyvec *pk: pointer to the input public-key polyvec
* const uint8_t *seed: pointer to the input public seed
**************************************************/
static void
pack_pk(uint8_t r[KYBER_INDCPA_PUBLICKEYBYTES],
polyvec *pk,
const uint8_t seed[KYBER_SYMBYTES])
{
size_t i;
polyvec_tobytes(r, pk);
for (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 polynomial vector
* - 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[KYBER_SYMBYTES],
const uint8_t packedpk[KYBER_INDCPA_PUBLICKEYBYTES])
{
size_t i;
polyvec_frombytes(pk, packedpk);
for (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
* - polyvec *sk: pointer to input vector of polynomials (secret key)
**************************************************/
static void
pack_sk(uint8_t r[KYBER_INDCPA_SECRETKEYBYTES], polyvec *sk)
{
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[KYBER_INDCPA_SECRETKEYBYTES])
{
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
* poly *pk: pointer to the input vector of polynomials b
* poly *v: pointer to the input polynomial v
**************************************************/
static void
pack_ciphertext(uint8_t r[KYBER_INDCPA_BYTES], polyvec *b, poly *v)
{
polyvec_compress(r, b);
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[KYBER_INDCPA_BYTES])
{
polyvec_decompress(b, c);
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
* - unsigned int len: requested number of 16-bit integers (uniform mod q)
* - const uint8_t *buf: pointer to input buffer (assumed to be uniformly random bytes)
* - unsigned int buflen: length of input buffer in bytes
*
* Returns number of sampled 16-bit integers (at most len)
**************************************************/
static unsigned int
rej_uniform(int16_t *r,
unsigned int len,
const uint8_t *buf,
unsigned int buflen)
{
unsigned int ctr, pos;
uint16_t val0, val1;
ctr = pos = 0;
while (ctr < len && pos + 3 <= buflen) {
val0 = ((buf[pos + 0] >> 0) | ((uint16_t)buf[pos + 1] << 8)) & 0xFFF;
val1 = ((buf[pos + 1] >> 4) | ((uint16_t)buf[pos + 2] << 4)) & 0xFFF;
pos += 3;
if (val0 < KYBER_Q)
r[ctr++] = val0;
if (ctr < len && val1 < KYBER_Q)
r[ctr++] = val1;
}
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 GEN_MATRIX_NBLOCKS ((12 * KYBER_N / 8 * (1 << 12) / KYBER_Q + XOF_BLOCKBYTES) / XOF_BLOCKBYTES)
// Not static for benchmarking
static void
gen_matrix(polyvec *a, const uint8_t seed[KYBER_SYMBYTES], int transposed)
{
unsigned int ctr, i, j, k;
unsigned int buflen, off;
uint8_t buf[GEN_MATRIX_NBLOCKS * XOF_BLOCKBYTES + 2];
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, GEN_MATRIX_NBLOCKS, &state);
buflen = GEN_MATRIX_NBLOCKS * XOF_BLOCKBYTES;
ctr = rej_uniform(a[i].vec[j].coeffs, KYBER_N, buf, buflen);
while (ctr < KYBER_N) {
off = buflen % 3;
for (k = 0; k < off; k++)
buf[k] = buf[buflen - off + k];
xof_squeezeblocks(buf + off, 1, &state);
buflen = off + XOF_BLOCKBYTES;
ctr += rej_uniform(a[i].vec[j].coeffs + ctr, KYBER_N - ctr, buf, buflen);
}
}
}
}
/*************************************************
* Name: indcpa_keypair_derand
*
* 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)
* - const uint8_t *coins: pointer to input randomness
* (of length KYBER_SYMBYTES bytes)
**************************************************/
static void
indcpa_keypair_derand(uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES],
const uint8_t coins[KYBER_SYMBYTES])
{
unsigned int i;
uint8_t buf[2 * KYBER_SYMBYTES];
const uint8_t *publicseed = buf;
const uint8_t *noiseseed = buf + KYBER_SYMBYTES;
uint8_t nonce = 0;
polyvec a[KYBER_K], e, pkpv, skpv;
hash_g(buf, coins, KYBER_SYMBYTES);
gen_a(a, publicseed);
for (i = 0; i < KYBER_K; i++)
poly_getnoise_eta1(&skpv.vec[i], noiseseed, nonce++);
for (i = 0; i < KYBER_K; i++)
poly_getnoise_eta1(&e.vec[i], noiseseed, nonce++);
polyvec_ntt(&skpv);
polyvec_ntt(&e);
// matrix-vector multiplication
for (i = 0; i < KYBER_K; i++) {
polyvec_basemul_acc_montgomery(&pkpv.vec[i], &a[i], &skpv);
poly_tomont(&pkpv.vec[i]);
}
polyvec_add(&pkpv, &pkpv, &e);
polyvec_reduce(&pkpv);
pack_sk(sk, &skpv);
pack_pk(pk, &pkpv, publicseed);
}
/*************************************************
* 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)
* - const uint8_t *coins: pointer to input random coins used as seed
* (of length KYBER_SYMBYTES) to deterministically
* generate all randomness
**************************************************/
static void
indcpa_enc(uint8_t c[KYBER_INDCPA_BYTES],
const uint8_t m[KYBER_INDCPA_MSGBYTES],
const uint8_t pk[KYBER_INDCPA_PUBLICKEYBYTES],
const uint8_t coins[KYBER_SYMBYTES])
{
unsigned int i;
uint8_t seed[KYBER_SYMBYTES];
uint8_t nonce = 0;
polyvec sp, pkpv, ep, at[KYBER_K], b;
poly v, k, epp;
unpack_pk(&pkpv, seed, pk);
poly_frommsg(&k, m);
gen_at(at, seed);
for (i = 0; i < KYBER_K; i++)
poly_getnoise_eta1(sp.vec + i, coins, nonce++);
for (i = 0; i < KYBER_K; i++)
poly_getnoise_eta2(ep.vec + i, coins, nonce++);
poly_getnoise_eta2(&epp, coins, nonce++);
polyvec_ntt(&sp);
// matrix-vector multiplication
for (i = 0; i < KYBER_K; i++)
polyvec_basemul_acc_montgomery(&b.vec[i], &at[i], &sp);
polyvec_basemul_acc_montgomery(&v, &pkpv, &sp);
polyvec_invntt_tomont(&b);
poly_invntt_tomont(&v);
polyvec_add(&b, &b, &ep);
poly_add(&v, &v, &epp);
poly_add(&v, &v, &k);
polyvec_reduce(&b);
poly_reduce(&v);
pack_ciphertext(c, &b, &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)
**************************************************/
static void
indcpa_dec(uint8_t m[KYBER_INDCPA_MSGBYTES],
const uint8_t c[KYBER_INDCPA_BYTES],
const uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES])
{
polyvec b, skpv;
poly v, mp;
unpack_ciphertext(&b, &v, c);
unpack_sk(&skpv, sk);
polyvec_ntt(&b);
polyvec_basemul_acc_montgomery(&mp, &skpv, &b);
poly_invntt_tomont(&mp);
poly_sub(&mp, &v, &mp);
poly_reduce(&mp);
poly_tomsg(m, &mp);
}
/** end: ref/indcpa.c **/
/** begin: ref/fips202.c **/
/* Based on the public domain implementation in crypto_hash/keccakc512/simple/ from
* and Peter Schwabe */
#define NROUNDS 24
#define ROL(a, offset) ((a << offset) ^ (a >> (64 - offset)))
/*************************************************
* Name: load64
*
* Description: Load 8 bytes into uint64_t in little-endian order
*
* Arguments: - const uint8_t *x: pointer to input byte array
*
* Returns the loaded 64-bit unsigned integer
**************************************************/
static uint64_t
load64(const uint8_t x[8])
{
unsigned int i;
uint64_t r = 0;
for (i = 0; i < 8; i++)
r |= (uint64_t)x[i] << 8 * i;
return r;
}
/*************************************************
* Name: store64
*
* Description: Store a 64-bit integer to array of 8 bytes in little-endian order
*
* Arguments: - uint8_t *x: pointer to the output byte array (allocated)
* - uint64_t u: input 64-bit unsigned integer
**************************************************/
static void
store64(uint8_t x[8], uint64_t u)
{
unsigned int i;
for (i = 0; i < 8; i++)
x[i] = u >> 8 * i;
}
/* Keccak round constants */
static const uint64_t KeccakF_RoundConstants[NROUNDS] = {
(uint64_t)0x0000000000000001ULL,
(uint64_t)0x0000000000008082ULL,
(uint64_t)0x800000000000808aULL,
(uint64_t)0x8000000080008000ULL,
(uint64_t)0x000000000000808bULL,
(uint64_t)0x0000000080000001ULL,
(uint64_t)0x8000000080008081ULL,
(uint64_t)0x8000000000008009ULL,
(uint64_t)0x000000000000008aULL,
(uint64_t)0x0000000000000088ULL,
(uint64_t)0x0000000080008009ULL,
(uint64_t)0x000000008000000aULL,
(uint64_t)0x000000008000808bULL,
(uint64_t)0x800000000000008bULL,
(uint64_t)0x8000000000008089ULL,
(uint64_t)0x8000000000008003ULL,
(uint64_t)0x8000000000008002ULL,
(uint64_t)0x8000000000000080ULL,
(uint64_t)0x000000000000800aULL,
(uint64_t)0x800000008000000aULL,
(uint64_t)0x8000000080008081ULL,
(uint64_t)0x8000000000008080ULL,
(uint64_t)0x0000000080000001ULL,
(uint64_t)0x8000000080008008ULL
};
/*************************************************
* Name: KeccakF1600_StatePermute
*
* Description: The Keccak F1600 Permutation
*
* Arguments: - uint64_t *state: pointer to input/output Keccak state
**************************************************/
static void
KeccakF1600_StatePermute(uint64_t state[25])
{
int round;
uint64_t Aba, Abe, Abi, Abo, Abu;
uint64_t Aga, Age, Agi, Ago, Agu;
uint64_t Aka, Ake, Aki, Ako, Aku;
uint64_t Ama, Ame, Ami, Amo, Amu;
uint64_t Asa, Ase, Asi, Aso, Asu;
uint64_t BCa, BCe, BCi, BCo, BCu;
uint64_t Da, De, Di, Do, Du;
uint64_t Eba, Ebe, Ebi, Ebo, Ebu;
uint64_t Ega, Ege, Egi, Ego, Egu;
uint64_t Eka, Eke, Eki, Eko, Eku;
uint64_t Ema, Eme, Emi, Emo, Emu;
uint64_t Esa, Ese, Esi, Eso, Esu;
//copyFromState(A, state)
Aba = state[0];
Abe = state[1];
Abi = state[2];
Abo = state[3];
Abu = state[4];
Aga = state[5];
Age = state[6];
Agi = state[7];
Ago = state[8];
Agu = state[9];
Aka = state[10];
Ake = state[11];
Aki = state[12];
Ako = state[13];
Aku = state[14];
Ama = state[15];
Ame = state[16];
Ami = state[17];
Amo = state[18];
Amu = state[19];
Asa = state[20];
Ase = state[21];
Asi = state[22];
Aso = state[23];
Asu = state[24];
for (round = 0; round < NROUNDS; round += 2) {
// prepareTheta
BCa = Aba ^ Aga ^ Aka ^ Ama ^ Asa;
BCe = Abe ^ Age ^ Ake ^ Ame ^ Ase;
BCi = Abi ^ Agi ^ Aki ^ Ami ^ Asi;
BCo = Abo ^ Ago ^ Ako ^ Amo ^ Aso;
BCu = Abu ^ Agu ^ Aku ^ Amu ^ Asu;
//thetaRhoPiChiIotaPrepareTheta(round, A, E)
Da = BCu ^ ROL(BCe, 1);
De = BCa ^ ROL(BCi, 1);
Di = BCe ^ ROL(BCo, 1);
Do = BCi ^ ROL(BCu, 1);
Du = BCo ^ ROL(BCa, 1);
Aba ^= Da;
BCa = Aba;
Age ^= De;
BCe = ROL(Age, 44);
Aki ^= Di;
BCi = ROL(Aki, 43);
Amo ^= Do;
BCo = ROL(Amo, 21);
Asu ^= Du;
BCu = ROL(Asu, 14);
Eba = BCa ^ ((~BCe) & BCi);
Eba ^= (uint64_t)KeccakF_RoundConstants[round];
Ebe = BCe ^ ((~BCi) & BCo);
Ebi = BCi ^ ((~BCo) & BCu);
Ebo = BCo ^ ((~BCu) & BCa);
Ebu = BCu ^ ((~BCa) & BCe);
Abo ^= Do;
BCa = ROL(Abo, 28);
Agu ^= Du;
BCe = ROL(Agu, 20);
Aka ^= Da;
BCi = ROL(Aka, 3);
Ame ^= De;
BCo = ROL(Ame, 45);
Asi ^= Di;
BCu = ROL(Asi, 61);
Ega = BCa ^ ((~BCe) & BCi);
Ege = BCe ^ ((~BCi) & BCo);
Egi = BCi ^ ((~BCo) & BCu);
Ego = BCo ^ ((~BCu) & BCa);
Egu = BCu ^ ((~BCa) & BCe);
Abe ^= De;
BCa = ROL(Abe, 1);
Agi ^= Di;
BCe = ROL(Agi, 6);
Ako ^= Do;
BCi = ROL(Ako, 25);
Amu ^= Du;
BCo = ROL(Amu, 8);
Asa ^= Da;
BCu = ROL(Asa, 18);
Eka = BCa ^ ((~BCe) & BCi);
Eke = BCe ^ ((~BCi) & BCo);
Eki = BCi ^ ((~BCo) & BCu);
Eko = BCo ^ ((~BCu) & BCa);
Eku = BCu ^ ((~BCa) & BCe);
Abu ^= Du;
BCa = ROL(Abu, 27);
Aga ^= Da;
BCe = ROL(Aga, 36);
Ake ^= De;
BCi = ROL(Ake, 10);
Ami ^= Di;
BCo = ROL(Ami, 15);
Aso ^= Do;
BCu = ROL(Aso, 56);
Ema = BCa ^ ((~BCe) & BCi);
Eme = BCe ^ ((~BCi) & BCo);
Emi = BCi ^ ((~BCo) & BCu);
Emo = BCo ^ ((~BCu) & BCa);
Emu = BCu ^ ((~BCa) & BCe);
Abi ^= Di;
BCa = ROL(Abi, 62);
Ago ^= Do;
BCe = ROL(Ago, 55);
Aku ^= Du;
BCi = ROL(Aku, 39);
Ama ^= Da;
BCo = ROL(Ama, 41);
Ase ^= De;
BCu = ROL(Ase, 2);
Esa = BCa ^ ((~BCe) & BCi);
Ese = BCe ^ ((~BCi) & BCo);
Esi = BCi ^ ((~BCo) & BCu);
Eso = BCo ^ ((~BCu) & BCa);
Esu = BCu ^ ((~BCa) & BCe);
// prepareTheta
BCa = Eba ^ Ega ^ Eka ^ Ema ^ Esa;
BCe = Ebe ^ Ege ^ Eke ^ Eme ^ Ese;
BCi = Ebi ^ Egi ^ Eki ^ Emi ^ Esi;
BCo = Ebo ^ Ego ^ Eko ^ Emo ^ Eso;
BCu = Ebu ^ Egu ^ Eku ^ Emu ^ Esu;
//thetaRhoPiChiIotaPrepareTheta(round+1, E, A)
Da = BCu ^ ROL(BCe, 1);
De = BCa ^ ROL(BCi, 1);
Di = BCe ^ ROL(BCo, 1);
Do = BCi ^ ROL(BCu, 1);
Du = BCo ^ ROL(BCa, 1);
Eba ^= Da;
BCa = Eba;
Ege ^= De;
BCe = ROL(Ege, 44);
Eki ^= Di;
BCi = ROL(Eki, 43);
Emo ^= Do;
BCo = ROL(Emo, 21);
Esu ^= Du;
BCu = ROL(Esu, 14);
Aba = BCa ^ ((~BCe) & BCi);
Aba ^= (uint64_t)KeccakF_RoundConstants[round + 1];
Abe = BCe ^ ((~BCi) & BCo);
Abi = BCi ^ ((~BCo) & BCu);
Abo = BCo ^ ((~BCu) & BCa);
Abu = BCu ^ ((~BCa) & BCe);
Ebo ^= Do;
BCa = ROL(Ebo, 28);
Egu ^= Du;
BCe = ROL(Egu, 20);
Eka ^= Da;
BCi = ROL(Eka, 3);
Eme ^= De;
BCo = ROL(Eme, 45);
Esi ^= Di;
BCu = ROL(Esi, 61);
Aga = BCa ^ ((~BCe) & BCi);
Age = BCe ^ ((~BCi) & BCo);
Agi = BCi ^ ((~BCo) & BCu);
Ago = BCo ^ ((~BCu) & BCa);
Agu = BCu ^ ((~BCa) & BCe);
Ebe ^= De;
BCa = ROL(Ebe, 1);
Egi ^= Di;
BCe = ROL(Egi, 6);
Eko ^= Do;
BCi = ROL(Eko, 25);
Emu ^= Du;
BCo = ROL(Emu, 8);
Esa ^= Da;
BCu = ROL(Esa, 18);
Aka = BCa ^ ((~BCe) & BCi);
Ake = BCe ^ ((~BCi) & BCo);
Aki = BCi ^ ((~BCo) & BCu);
Ako = BCo ^ ((~BCu) & BCa);
Aku = BCu ^ ((~BCa) & BCe);
Ebu ^= Du;
BCa = ROL(Ebu, 27);
Ega ^= Da;
BCe = ROL(Ega, 36);
Eke ^= De;
BCi = ROL(Eke, 10);
Emi ^= Di;
BCo = ROL(Emi, 15);
Eso ^= Do;
BCu = ROL(Eso, 56);
Ama = BCa ^ ((~BCe) & BCi);
Ame = BCe ^ ((~BCi) & BCo);
Ami = BCi ^ ((~BCo) & BCu);
Amo = BCo ^ ((~BCu) & BCa);
Amu = BCu ^ ((~BCa) & BCe);
Ebi ^= Di;
BCa = ROL(Ebi, 62);
Ego ^= Do;
BCe = ROL(Ego, 55);
Eku ^= Du;
BCi = ROL(Eku, 39);
Ema ^= Da;
BCo = ROL(Ema, 41);
Ese ^= De;
BCu = ROL(Ese, 2);
Asa = BCa ^ ((~BCe) & BCi);
Ase = BCe ^ ((~BCi) & BCo);
Asi = BCi ^ ((~BCo) & BCu);
Aso = BCo ^ ((~BCu) & BCa);
Asu = BCu ^ ((~BCa) & BCe);
}
//copyToState(state, A)
state[0] = Aba;
state[1] = Abe;
state[2] = Abi;
state[3] = Abo;
state[4] = Abu;
state[5] = Aga;
state[6] = Age;
state[7] = Agi;
state[8] = Ago;
state[9] = Agu;
state[10] = Aka;
state[11] = Ake;
state[12] = Aki;
state[13] = Ako;
state[14] = Aku;
state[15] = Ama;
state[16] = Ame;
state[17] = Ami;
state[18] = Amo;
state[19] = Amu;
state[20] = Asa;
state[21] = Ase;
state[22] = Asi;
state[23] = Aso;
state[24] = Asu;
}
/*************************************************
* Name: keccak_init
*
* Description: Initializes the Keccak state.
*
* Arguments: - uint64_t *s: pointer to Keccak state
**************************************************/
static void
keccak_init(uint64_t s[25])
{
unsigned int i;
for (i = 0; i < 25; i++)
s[i] = 0;
}
/*************************************************
* Name: keccak_absorb
*
* Description: Absorb step of Keccak; incremental.
*
* Arguments: - uint64_t *s: pointer to Keccak state
* - unsigned int pos: position in current block to be absorbed
* - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
* - const uint8_t *in: pointer to input to be absorbed into s
* - size_t inlen: length of input in bytes
*
* Returns new position pos in current block
**************************************************/
static unsigned int
keccak_absorb(uint64_t s[25],
unsigned int pos,
unsigned int r,
const uint8_t *in,
size_t inlen)
{
unsigned int i;
while (pos + inlen >= r) {
for (i = pos; i < r; i++)
s[i / 8] ^= (uint64_t)*in++ << 8 * (i % 8);
inlen -= r - pos;
KeccakF1600_StatePermute(s);
pos = 0;
}
for (i = pos; i < pos + inlen; i++)
s[i / 8] ^= (uint64_t)*in++ << 8 * (i % 8);
return i;
}
/*************************************************
* Name: keccak_finalize
*
* Description: Finalize absorb step.
*
* Arguments: - uint64_t *s: pointer to Keccak state
* - unsigned int pos: position in current block to be absorbed
* - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
* - uint8_t p: domain separation byte
**************************************************/
static void
keccak_finalize(uint64_t s[25], unsigned int pos, unsigned int r, uint8_t p)
{
s[pos / 8] ^= (uint64_t)p << 8 * (pos % 8);
s[r / 8 - 1] ^= 1ULL << 63;
}
/*************************************************
* Name: keccak_squeeze
*
* Description: Squeeze step of Keccak. Squeezes arbitratrily many bytes.
* Modifies the state. Can be called multiple times to keep
* squeezing, i.e., is incremental.
*
* Arguments: - uint8_t *out: pointer to output
* - size_t outlen: number of bytes to be squeezed (written to out)
* - uint64_t *s: pointer to input/output Keccak state
* - unsigned int pos: number of bytes in current block already squeezed
* - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
*
* Returns new position pos in current block
**************************************************/
static unsigned int
keccak_squeeze(uint8_t *out,
size_t outlen,
uint64_t s[25],
unsigned int pos,
unsigned int r)
{
unsigned int i;
while (outlen) {
if (pos == r) {
KeccakF1600_StatePermute(s);
pos = 0;
}
for (i = pos; i < r && i < pos + outlen; i++)
*out++ = s[i / 8] >> 8 * (i % 8);
outlen -= i - pos;
pos = i;
}
return pos;
}
/*************************************************
* Name: keccak_absorb_once
*
* Description: Absorb step of Keccak;
* non-incremental, starts by zeroeing the state.
*
* Arguments: - uint64_t *s: pointer to (uninitialized) output Keccak state
* - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
* - const uint8_t *in: pointer to input to be absorbed into s
* - size_t inlen: length of input in bytes
* - uint8_t p: domain-separation byte for different Keccak-derived functions
**************************************************/
static void
keccak_absorb_once(uint64_t s[25],
unsigned int r,
const uint8_t *in,
size_t inlen,
uint8_t p)
{
unsigned int i;
for (i = 0; i < 25; i++)
s[i] = 0;
while (inlen >= r) {
for (i = 0; i < r / 8; i++)
s[i] ^= load64(in + 8 * i);
in += r;
inlen -= r;
KeccakF1600_StatePermute(s);
}
for (i = 0; i < inlen; i++)
s[i / 8] ^= (uint64_t)in[i] << 8 * (i % 8);
s[i / 8] ^= (uint64_t)p << 8 * (i % 8);
s[(r - 1) / 8] ^= 1ULL << 63;
}
/*************************************************
* Name: keccak_squeezeblocks
*
* Description: Squeeze step of Keccak. Squeezes full blocks of r bytes each.
* Modifies the state. Can be called multiple times to keep
* squeezing, i.e., is incremental. Assumes zero bytes of current
* block have already been squeezed.
*
* Arguments: - uint8_t *out: pointer to output blocks
* - size_t nblocks: number of blocks to be squeezed (written to out)
* - uint64_t *s: pointer to input/output Keccak state
* - unsigned int r: rate in bytes (e.g., 168 for SHAKE128)
**************************************************/
static void
keccak_squeezeblocks(uint8_t *out,
size_t nblocks,
uint64_t s[25],
unsigned int r)
{
unsigned int i;
while (nblocks) {
KeccakF1600_StatePermute(s);
for (i = 0; i < r / 8; i++)
store64(out + 8 * i, s[i]);
out += r;
nblocks -= 1;
}
}
/*************************************************
* Name: shake128_init
*
* Description: Initilizes Keccak state for use as SHAKE128 XOF
*
* Arguments: - keccak_state *state: pointer to (uninitialized) Keccak state
**************************************************/
void
shake128_init(keccak_state *state)
{
keccak_init(state->s);
state->pos = 0;
}
/*************************************************
* Name: shake128_absorb
*
* Description: Absorb step of the SHAKE128 XOF; incremental.
*
* Arguments: - keccak_state *state: pointer to (initialized) output Keccak state
* - const uint8_t *in: pointer to input to be absorbed into s
* - size_t inlen: length of input in bytes
**************************************************/
void
shake128_absorb(keccak_state *state, const uint8_t *in, size_t inlen)
{
state->pos = keccak_absorb(state->s, state->pos, SHAKE128_RATE, in, inlen);
}
/*************************************************
* Name: shake128_finalize
*
* Description: Finalize absorb step of the SHAKE128 XOF.
*
* Arguments: - keccak_state *state: pointer to Keccak state
**************************************************/
void
shake128_finalize(keccak_state *state)
{
keccak_finalize(state->s, state->pos, SHAKE128_RATE, 0x1F);
state->pos = SHAKE128_RATE;
}
/*************************************************
* Name: shake128_squeeze
*
* Description: Squeeze step of SHAKE128 XOF. Squeezes arbitraily many
* bytes. Can be called multiple times to keep squeezing.
*
* Arguments: - uint8_t *out: pointer to output blocks
* - size_t outlen : number of bytes to be squeezed (written to output)
* - keccak_state *s: pointer to input/output Keccak state
**************************************************/
void
shake128_squeeze(uint8_t *out, size_t outlen, keccak_state *state)
{
state->pos = keccak_squeeze(out, outlen, state->s, state->pos, SHAKE128_RATE);
}
/*************************************************
* Name: shake128_absorb_once
*
* Description: Initialize, absorb into and finalize SHAKE128 XOF; non-incremental.
*
* Arguments: - keccak_state *state: pointer to (uninitialized) output Keccak state
* - const uint8_t *in: pointer to input to be absorbed into s
* - size_t inlen: length of input in bytes
**************************************************/
void
shake128_absorb_once(keccak_state *state, const uint8_t *in, size_t inlen)
{
keccak_absorb_once(state->s, SHAKE128_RATE, in, inlen, 0x1F);
state->pos = SHAKE128_RATE;
}
/*************************************************
* Name: shake128_squeezeblocks
*
* Description: Squeeze step of SHAKE128 XOF. Squeezes full blocks of
* SHAKE128_RATE bytes each. Can be called multiple times
* to keep squeezing. Assumes new block has not yet been
* started (state->pos = SHAKE128_RATE).
*
* Arguments: - uint8_t *out: pointer to output blocks
* - size_t nblocks: number of blocks to be squeezed (written to output)
* - keccak_state *s: pointer to input/output Keccak state
**************************************************/
void
shake128_squeezeblocks(uint8_t *out, size_t nblocks, keccak_state *state)
{
keccak_squeezeblocks(out, nblocks, state->s, SHAKE128_RATE);
}
/*************************************************
* Name: shake256_init
*
* Description: Initilizes Keccak state for use as SHAKE256 XOF
*
* Arguments: - keccak_state *state: pointer to (uninitialized) Keccak state
**************************************************/
void
shake256_init(keccak_state *state)
{
keccak_init(state->s);
state->pos = 0;
}
/*************************************************
* Name: shake256_absorb
*
* Description: Absorb step of the SHAKE256 XOF; incremental.
*
* Arguments: - keccak_state *state: pointer to (initialized) output Keccak state
* - const uint8_t *in: pointer to input to be absorbed into s
* - size_t inlen: length of input in bytes
**************************************************/
void
shake256_absorb(keccak_state *state, const uint8_t *in, size_t inlen)
{
state->pos = keccak_absorb(state->s, state->pos, SHAKE256_RATE, in, inlen);
}
/*************************************************
* Name: shake256_finalize
*
* Description: Finalize absorb step of the SHAKE256 XOF.
*
* Arguments: - keccak_state *state: pointer to Keccak state
**************************************************/
void
shake256_finalize(keccak_state *state)
{
keccak_finalize(state->s, state->pos, SHAKE256_RATE, 0x1F);
state->pos = SHAKE256_RATE;
}
/*************************************************
* Name: shake256_squeeze
*
* Description: Squeeze step of SHAKE256 XOF. Squeezes arbitraily many
* bytes. Can be called multiple times to keep squeezing.
*
* Arguments: - uint8_t *out: pointer to output blocks
* - size_t outlen : number of bytes to be squeezed (written to output)
* - keccak_state *s: pointer to input/output Keccak state
**************************************************/
void
shake256_squeeze(uint8_t *out, size_t outlen, keccak_state *state)
{
state->pos = keccak_squeeze(out, outlen, state->s, state->pos, SHAKE256_RATE);
}
/*************************************************
* Name: shake256_absorb_once
*
* Description: Initialize, absorb into and finalize SHAKE256 XOF; non-incremental.
*
* Arguments: - keccak_state *state: pointer to (uninitialized) output Keccak state
* - const uint8_t *in: pointer to input to be absorbed into s
* - size_t inlen: length of input in bytes
**************************************************/
void
shake256_absorb_once(keccak_state *state, const uint8_t *in, size_t inlen)
{
keccak_absorb_once(state->s, SHAKE256_RATE, in, inlen, 0x1F);
state->pos = SHAKE256_RATE;
}
/*************************************************
* Name: shake256_squeezeblocks
*
* Description: Squeeze step of SHAKE256 XOF. Squeezes full blocks of
* SHAKE256_RATE bytes each. Can be called multiple times
* to keep squeezing. Assumes next block has not yet been
* started (state->pos = SHAKE256_RATE).
*
* Arguments: - uint8_t *out: pointer to output blocks
* - size_t nblocks: number of blocks to be squeezed (written to output)
* - keccak_state *s: pointer to input/output Keccak state
**************************************************/
void
shake256_squeezeblocks(uint8_t *out, size_t nblocks, keccak_state *state)
{
keccak_squeezeblocks(out, nblocks, state->s, SHAKE256_RATE);
}
/*************************************************
* Name: shake128
*
* Description: SHAKE128 XOF with non-incremental API
*
* Arguments: - uint8_t *out: pointer to output
* - size_t outlen: requested output length in bytes
* - const uint8_t *in: pointer to input
* - size_t inlen: length of input in bytes
**************************************************/
void
shake128(uint8_t *out, size_t outlen, const uint8_t *in, size_t inlen)
{
size_t nblocks;
keccak_state state;
shake128_absorb_once(&state, in, inlen);
nblocks = outlen / SHAKE128_RATE;
shake128_squeezeblocks(out, nblocks, &state);
outlen -= nblocks * SHAKE128_RATE;
out += nblocks * SHAKE128_RATE;
shake128_squeeze(out, outlen, &state);
}
/*************************************************
* Name: shake256
*
* Description: SHAKE256 XOF with non-incremental API
*
* Arguments: - uint8_t *out: pointer to output
* - size_t outlen: requested output length in bytes
* - const uint8_t *in: pointer to input
* - size_t inlen: length of input in bytes
**************************************************/
void
shake256(uint8_t *out, size_t outlen, const uint8_t *in, size_t inlen)
{
size_t nblocks;
keccak_state state;
shake256_absorb_once(&state, in, inlen);
nblocks = outlen / SHAKE256_RATE;
shake256_squeezeblocks(out, nblocks, &state);
outlen -= nblocks * SHAKE256_RATE;
out += nblocks * SHAKE256_RATE;
shake256_squeeze(out, outlen, &state);
}
/*************************************************
* Name: sha3_256
*
* Description: SHA3-256 with non-incremental API
*
* Arguments: - uint8_t *h: pointer to output (32 bytes)
* - const uint8_t *in: pointer to input
* - size_t inlen: length of input in bytes
**************************************************/
void
sha3_256(uint8_t h[32], const uint8_t *in, size_t inlen)
{
unsigned int i;
uint64_t s[25];
keccak_absorb_once(s, SHA3_256_RATE, in, inlen, 0x06);
KeccakF1600_StatePermute(s);
for (i = 0; i < 4; i++)
store64(h + 8 * i, s[i]);
}
/*************************************************
* Name: sha3_512
*
* Description: SHA3-512 with non-incremental API
*
* Arguments: - uint8_t *h: pointer to output (64 bytes)
* - const uint8_t *in: pointer to input
* - size_t inlen: length of input in bytes
**************************************************/
void
sha3_512(uint8_t h[64], const uint8_t *in, size_t inlen)
{
unsigned int i;
uint64_t s[25];
keccak_absorb_once(s, SHA3_512_RATE, in, inlen, 0x06);
KeccakF1600_StatePermute(s);
for (i = 0; i < 8; i++)
store64(h + 8 * i, s[i]);
}
/** end: ref/fips202.c **/
/** begin: ref/symmetric-shake.c **/
/*************************************************
* Name: kyber_shake128_absorb
*
* Description: Absorb step of the SHAKE128 specialized for the Kyber context.
*
* Arguments: - keccak_state *state: pointer to (uninitialized) output Keccak state
* - const uint8_t *seed: pointer to KYBER_SYMBYTES input to be absorbed into state
* - uint8_t i: additional byte of input
* - uint8_t j: additional byte of input
**************************************************/
static void
kyber_shake128_absorb(keccak_state *state,
const uint8_t seed[KYBER_SYMBYTES],
uint8_t x,
uint8_t y)
{
uint8_t extseed[KYBER_SYMBYTES + 2];
memcpy(extseed, seed, KYBER_SYMBYTES);
extseed[KYBER_SYMBYTES + 0] = x;
extseed[KYBER_SYMBYTES + 1] = y;
shake128_absorb_once(state, extseed, sizeof(extseed));
}
/*************************************************
* Name: kyber_shake256_prf
*
* Description: Usage of SHAKE256 as a PRF, concatenates secret and public input
* and then generates outlen bytes of SHAKE256 output
*
* Arguments: - uint8_t *out: pointer to output
* - size_t outlen: number of requested output bytes
* - const uint8_t *key: pointer to the key (of length KYBER_SYMBYTES)
* - uint8_t nonce: single-byte nonce (public PRF input)
**************************************************/
static void
kyber_shake256_prf(uint8_t *out, size_t outlen, const uint8_t key[KYBER_SYMBYTES], uint8_t nonce)
{
uint8_t extkey[KYBER_SYMBYTES + 1];
memcpy(extkey, key, KYBER_SYMBYTES);
extkey[KYBER_SYMBYTES] = nonce;
shake256(out, outlen, extkey, sizeof(extkey));
}
/** end: ref/symmetric-shake.c **/
/** begin: ref/kem.c **/
/*************************************************
* Name: crypto_kem_keypair_derand
*
* Description: Generates public and private key
* for CCA-secure Kyber key encapsulation mechanism
*
* Arguments: - uint8_t *pk: pointer to output public key
* (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
* - uint8_t *sk: pointer to output private key
* (an already allocated array of KYBER_SECRETKEYBYTES bytes)
* - uint8_t *coins: pointer to input randomness
* (an already allocated array filled with 2*KYBER_SYMBYTES random bytes)
**
* Returns 0 (success)
**************************************************/
int
crypto_kem_keypair_derand(uint8_t *pk,
uint8_t *sk,
const uint8_t *coins)
{
size_t i;
indcpa_keypair_derand(pk, sk, coins);
for (i = 0; i < KYBER_INDCPA_PUBLICKEYBYTES; i++)
sk[i + KYBER_INDCPA_SECRETKEYBYTES] = pk[i];
hash_h(sk + KYBER_SECRETKEYBYTES - 2 * KYBER_SYMBYTES, pk, KYBER_PUBLICKEYBYTES);
/* Value z for pseudo-random output on reject */
for (i = 0; i < KYBER_SYMBYTES; i++)
sk[KYBER_SECRETKEYBYTES - KYBER_SYMBYTES + i] = coins[KYBER_SYMBYTES + i];
return 0;
}
/*************************************************
* Name: crypto_kem_keypair
*
* Description: Generates public and private key
* for CCA-secure Kyber key encapsulation mechanism
*
* Arguments: - uint8_t *pk: pointer to output public key
* (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
* - uint8_t *sk: pointer to output private key
* (an already allocated array of KYBER_SECRETKEYBYTES bytes)
*
* Returns 0 (success)
**************************************************/
int
crypto_kem_keypair(uint8_t *pk,
uint8_t *sk)
{
uint8_t coins[2 * KYBER_SYMBYTES];
randombytes(coins, KYBER_SYMBYTES);
randombytes(coins + KYBER_SYMBYTES, KYBER_SYMBYTES);
crypto_kem_keypair_derand(pk, sk, coins);
return 0;
}
/*************************************************
* Name: crypto_kem_enc_derand
*
* Description: Generates cipher text and shared
* secret for given public key
*
* Arguments: - uint8_t *ct: pointer to output cipher text
* (an already allocated array of KYBER_CIPHERTEXTBYTES bytes)
* - uint8_t *ss: pointer to output shared secret
* (an already allocated array of KYBER_SSBYTES bytes)
* - const uint8_t *pk: pointer to input public key
* (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
* - const uint8_t *coins: pointer to input randomness
* (an already allocated array filled with KYBER_SYMBYTES random bytes)
**
* Returns 0 (success)
**************************************************/
int
crypto_kem_enc_derand(uint8_t *ct,
uint8_t *ss,
const uint8_t *pk,
const uint8_t *coins)
{
uint8_t buf[2 * KYBER_SYMBYTES];
/* Will contain key, coins */
uint8_t kr[2 * KYBER_SYMBYTES];
/* Don't release system RNG output */
hash_h(buf, coins, KYBER_SYMBYTES);
/* Multitarget countermeasure for coins + contributory KEM */
hash_h(buf + KYBER_SYMBYTES, pk, KYBER_PUBLICKEYBYTES);
hash_g(kr, buf, 2 * KYBER_SYMBYTES);
/* coins are in kr+KYBER_SYMBYTES */
indcpa_enc(ct, buf, pk, kr + KYBER_SYMBYTES);
/* overwrite coins in kr with H(c) */
hash_h(kr + KYBER_SYMBYTES, ct, KYBER_CIPHERTEXTBYTES);
/* hash concatenation of pre-k and H(c) to k */
kdf(ss, kr, 2 * KYBER_SYMBYTES);
return 0;
}
/*************************************************
* Name: crypto_kem_enc
*
* Description: Generates cipher text and shared
* secret for given public key
*
* Arguments: - uint8_t *ct: pointer to output cipher text
* (an already allocated array of KYBER_CIPHERTEXTBYTES bytes)
* - uint8_t *ss: pointer to output shared secret
* (an already allocated array of KYBER_SSBYTES bytes)
* - const uint8_t *pk: pointer to input public key
* (an already allocated array of KYBER_PUBLICKEYBYTES bytes)
*
* Returns 0 (success)
**************************************************/
int
crypto_kem_enc(uint8_t *ct,
uint8_t *ss,
const uint8_t *pk)
{
uint8_t coins[KYBER_SYMBYTES];
randombytes(coins, KYBER_SYMBYTES);
crypto_kem_enc_derand(ct, ss, pk, coins);
return 0;
}
/*************************************************
* Name: crypto_kem_dec
*
* Description: Generates shared secret for given
* cipher text and private key
*
* Arguments: - uint8_t *ss: pointer to output shared secret
* (an already allocated array of KYBER_SSBYTES bytes)
* - const uint8_t *ct: pointer to input cipher text
* (an already allocated array of KYBER_CIPHERTEXTBYTES bytes)
* - const uint8_t *sk: pointer to input private key
* (an already allocated array of KYBER_SECRETKEYBYTES bytes)
*
* Returns 0.
*
* On failure, ss will contain a pseudo-random value.
**************************************************/
int
crypto_kem_dec(uint8_t *ss,
const uint8_t *ct,
const uint8_t *sk)
{
size_t i;
int fail;
uint8_t buf[2 * KYBER_SYMBYTES];
/* Will contain key, coins */
uint8_t kr[2 * KYBER_SYMBYTES];
uint8_t cmp[KYBER_CIPHERTEXTBYTES];
const uint8_t *pk = sk + KYBER_INDCPA_SECRETKEYBYTES;
indcpa_dec(buf, ct, sk);
/* Multitarget countermeasure for coins + contributory KEM */
for (i = 0; i < KYBER_SYMBYTES; i++)
buf[KYBER_SYMBYTES + i] = sk[KYBER_SECRETKEYBYTES - 2 * KYBER_SYMBYTES + i];
hash_g(kr, buf, 2 * KYBER_SYMBYTES);
/* coins are in kr+KYBER_SYMBYTES */
indcpa_enc(cmp, buf, pk, kr + KYBER_SYMBYTES);
fail = verify(ct, cmp, KYBER_CIPHERTEXTBYTES);
/* overwrite coins in kr with H(c) */
hash_h(kr + KYBER_SYMBYTES, ct, KYBER_CIPHERTEXTBYTES);
/* Overwrite pre-k with z on re-encryption failure */
cmov(kr, sk + KYBER_SECRETKEYBYTES - KYBER_SYMBYTES, KYBER_SYMBYTES, fail);
/* hash concatenation of pre-k and H(c) to k */
kdf(ss, kr, 2 * KYBER_SYMBYTES);
return 0;
}
/** end: ref/kem.c **/