25#ifdef HAVE_MLDSA_OPTIMIZATION
37static inline int32_t mldsa_freeze(int32_t a)
49static inline int32_t polyt0_unpack_idx(
const uint8_t *t0, uint32_t idx)
52 const uint8_t *p = t0 + 13U * (idx >> 3U);
53 uint32_t r = idx & 7U;
57 coeff = (int32_t) p[0];
58 coeff |= (int32_t) ((uint32_t) p[1] << 8U);
61 coeff = (int32_t) (p[1] >> 5U);
62 coeff |= (int32_t) ((uint32_t) p[2] << 3U);
63 coeff |= (int32_t) ((uint32_t) p[3] << 11U);
66 coeff = (int32_t) (p[3] >> 2U);
67 coeff |= (int32_t) ((uint32_t) p[4] << 6U);
70 coeff = (int32_t) (p[4] >> 7U);
71 coeff |= (int32_t) ((uint32_t) p[5] << 1U);
72 coeff |= (int32_t) ((uint32_t) p[6] << 9U);
75 coeff = (int32_t) (p[6] >> 4U);
76 coeff |= (int32_t) ((uint32_t) p[7] << 4U);
77 coeff |= (int32_t) ((uint32_t) p[8] << 12U);
80 coeff = (int32_t) (p[8] >> 1U);
81 coeff |= (int32_t) ((uint32_t) p[9] << 7U);
84 coeff = (int32_t) (p[9] >> 6U);
85 coeff |= (int32_t) ((uint32_t) p[10] << 2U);
86 coeff |= (int32_t) ((uint32_t) p[11] << 10U);
89 coeff = (int32_t) (p[11] >> 3U);
90 coeff |= (int32_t) ((uint32_t) p[12] << 5U);
94 return (1 << (
MLDSA_D - 1)) - coeff;
102static inline int32_t polyt1_unpack_idx(
const uint8_t *t1, uint32_t idx)
105 const uint8_t *p = t1 + 5U * (idx >> 2U);
106 uint32_t r = idx & 3U;
110 coeff = (int32_t) p[0];
111 coeff |= (int32_t) ((uint32_t) p[1] << 8U);
114 coeff = (int32_t) (p[1] >> 2U);
115 coeff |= (int32_t) ((uint32_t) p[2] << 6U);
118 coeff = (int32_t) (p[2] >> 4U);
119 coeff |= (int32_t) ((uint32_t) p[3] << 4U);
122 coeff = (int32_t) (p[3] >> 6U);
123 coeff |= (int32_t) ((uint32_t) p[4] << 2U);
134void MLDSA_LOWRAM_polyw_pack(uint8_t buf[MLDSA_WCOMP_BYTES],
const mldsa_poly *w)
136 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
137 int32_t c = mldsa_freeze(w->
coeffs[i]);
138 buf[i * 3U + 0U] = (uint8_t) c;
139 buf[i * 3U + 1U] = (uint8_t) (c >> 8U);
140 buf[i * 3U + 2U] = (uint8_t) (c >> 16U);
144void MLDSA_LOWRAM_polyw_unpack(
mldsa_poly *w,
const uint8_t buf[MLDSA_WCOMP_BYTES])
146 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
147 w->
coeffs[i] = (int32_t) buf[i * 3U + 0U];
148 w->
coeffs[i] |= (int32_t) ((uint32_t) buf[i * 3U + 1U] << 8U);
149 w->
coeffs[i] |= (int32_t) ((uint32_t) buf[i * 3U + 2U] << 16U);
153void MLDSA_LOWRAM_polyw_add_idx(uint8_t buf[MLDSA_WCOMP_BYTES], int32_t a, uint32_t idx)
156 coeff = (int32_t) buf[idx * 3U + 0U];
157 coeff |= (int32_t) ((uint32_t) buf[idx * 3U + 1U] << 8U);
158 coeff |= (int32_t) ((uint32_t) buf[idx * 3U + 2U] << 16U);
161 coeff = mldsa_freeze(coeff);
163 buf[idx * 3U + 0U] = (uint8_t) coeff;
164 buf[idx * 3U + 1U] = (uint8_t) (coeff >> 8U);
165 buf[idx * 3U + 2U] = (uint8_t) (coeff >> 16U);
169 const uint8_t buf[MLDSA_WCOMP_BYTES],
172 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
174 coeff = (int32_t) buf[i * 3U + 0U];
175 coeff |= (int32_t) ((uint32_t) buf[i * 3U + 1U] << 8U);
176 coeff |= (int32_t) ((uint32_t) buf[i * 3U + 2U] << 16U);
185void MLDSA_LOWRAM_challenge_compress(uint8_t ccomp[MLDSA_CCOMP_BYTES],
193 memset(ccomp, 0, MLDSA_CCOMP_BYTES);
195 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
197 ccomp[pos++] = (uint8_t) i;
198 if (cp->
coeffs[i] == -1) {
206 for (uint32_t i = 0U; i < 8U; i++) {
207 ccomp[60U + i] = (uint8_t) (signs >> (8U * i));
211void MLDSA_LOWRAM_challenge_decompress(
mldsa_poly *cp,
212 const uint8_t ccomp[MLDSA_CCOMP_BYTES],
217 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
220 for (uint32_t i = 0U; i < 8U; i++) {
221 signs |= ((uint64_t) ccomp[60U + i]) << (8U * i);
223 for (uint32_t i = 0U; i < tau; i++) {
224 uint32_t pos = ccomp[i];
240 const uint8_t ccomp[MLDSA_CCOMP_BYTES],
246 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
249 for (uint32_t i = 0U; i < 8U; i++) {
250 signs |= ((uint64_t) ccomp[60U + i]) << (8U * i);
253 for (uint32_t idx = 0U; idx < tau; idx++) {
254 uint32_t pos = ccomp[idx];
255 int32_t sign = (signs & 1U) ? -1 : 1;
257 for (uint32_t j = 0U; pos + j <
MLDSA_N; j++) {
258 c->
coeffs[pos + j] += sign * polyt0_unpack_idx(t0, j);
261 c->
coeffs[pos + j -
MLDSA_N] -= sign * polyt0_unpack_idx(t0, j);
268 const uint8_t ccomp[MLDSA_CCOMP_BYTES],
274 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
277 for (uint32_t i = 0U; i < 8U; i++) {
278 signs |= ((uint64_t) ccomp[60U + i]) << (8U * i);
281 for (uint32_t idx = 0U; idx < tau; idx++) {
282 uint32_t pos = ccomp[idx];
283 int32_t sign = (signs & 1U) ? -1 : 1;
285 for (uint32_t j = 0U; pos + j <
MLDSA_N; j++) {
286 c->
coeffs[pos + j] += sign * (polyt1_unpack_idx(t1, j) <<
MLDSA_D);
305#define LOWRAM_AEXPAND_NBLOCKS 5U
306#define LOWRAM_AEXPAND_BUFSIZE (LOWRAM_AEXPAND_NBLOCKS * 168U)
308void MLDSA_LOWRAM_expand_aij_accum(uint8_t wcomp[MLDSA_WCOMP_BYTES],
313 uint8_t buf[LOWRAM_AEXPAND_BUFSIZE] = {0};
319 while ((ctr <
MLDSA_N) && ((pos + 3U) <=
sizeof(buf))) {
321 t = (uint32_t) buf[pos];
322 t |= (uint32_t) buf[pos + 1U] << 8U;
323 t |= (uint32_t) buf[pos + 2U] << 16U;
330 MLDSA_LOWRAM_polyw_add_idx(wcomp, mont_prod, ctr);
335 explicit_bzero(buf,
sizeof(buf));
345 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
352 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
360static int32_t mldsa_lowram_w1_unpack_idx(
const uint8_t *w1_packed, uint32_t i, int32_t gamma2)
363 if (gamma2 == (
MLDSA_Q - 1) / 32) {
365 w1 = (int32_t) ((w1_packed[i >> 1U] >> ((i & 1U) * 4U)) & 0x0FU);
369 const uint8_t *q = &w1_packed[(i >> 2U) * 3U];
372 w1 = (int32_t) (q[0] & 0x3FU);
375 w1 = (int32_t) (((uint32_t) (q[0] >> 6U)) | (((uint32_t) (q[1] & 0x0FU)) << 2U));
378 w1 = (int32_t) (((uint32_t) (q[1] >> 4U)) | (((uint32_t) (q[2] & 0x03U)) << 4U));
381 w1 = (int32_t) (q[2] >> 2U);
389 const uint8_t wcomp[MLDSA_WCOMP_BYTES],
390 const uint8_t *w1_packed,
393 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
395 w_minus_cs2 = (int32_t) wcomp[i * 3U + 0U];
396 w_minus_cs2 |= (int32_t) ((uint32_t) wcomp[i * 3U + 1U] << 8U);
397 w_minus_cs2 |= (int32_t) ((uint32_t) wcomp[i * 3U + 2U] << 16U);
402 int32_t w1 = mldsa_lowram_w1_unpack_idx(w1_packed, i, gamma2);
413 const uint8_t wcomp[MLDSA_WCOMP_BYTES],
414 const uint8_t *w1_packed,
417 uint32_t hints_n = 0U;
418 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
420 w_minus_cs2 = (int32_t) wcomp[i * 3U + 0U];
421 w_minus_cs2 |= (int32_t) ((uint32_t) wcomp[i * 3U + 1U] << 8U);
422 w_minus_cs2 |= (int32_t) ((uint32_t) wcomp[i * 3U + 2U] << 16U);
427 int32_t w1 = mldsa_lowram_w1_unpack_idx(w1_packed, i, gamma2);
442void MLDSA_LOWRAM_use_hint_indices(
mldsa_poly *b,
444 const uint8_t *h_indices,
448 for (uint32_t i = 0U; i <
MLDSA_N; i++) {
449 uint32_t in_list = 0U;
450 for (uint32_t hidx = 0U; hidx < num_hints; hidx++) {
451 if (i == h_indices[hidx]) {
472void MLDSA_LOWRAM_sample_gamma1_add(
mldsa_poly *a,
481 size_t buflen = (gamma1 == (1 << 17)) ? 576U : 640U;
485 if (gamma1 == (1 << 17)) {
486 for (uint32_t i = 0U; i <
MLDSA_N / 4U; i++) {
487 uint32_t t0, t1, t2, t3;
488 t0 = (uint32_t) buf[9U * i + 0U] | ((uint32_t) buf[9U * i + 1U] << 8U)
489 | ((uint32_t) buf[9U * i + 2U] << 16U);
491 t1 = ((uint32_t) buf[9U * i + 2U] >> 2U) | ((uint32_t) buf[9U * i + 3U] << 6U)
492 | ((uint32_t) buf[9U * i + 4U] << 14U);
494 t2 = ((uint32_t) buf[9U * i + 4U] >> 4U) | ((uint32_t) buf[9U * i + 5U] << 4U)
495 | ((uint32_t) buf[9U * i + 6U] << 12U);
497 t3 = ((uint32_t) buf[9U * i + 6U] >> 6U) | ((uint32_t) buf[9U * i + 7U] << 2U)
498 | ((uint32_t) buf[9U * i + 8U] << 10U);
501 a->
coeffs[4U * i + 0U] = b->
coeffs[4U * i + 0U] + gamma1 - (int32_t) t0;
502 a->
coeffs[4U * i + 1U] = b->
coeffs[4U * i + 1U] + gamma1 - (int32_t) t1;
503 a->
coeffs[4U * i + 2U] = b->
coeffs[4U * i + 2U] + gamma1 - (int32_t) t2;
504 a->
coeffs[4U * i + 3U] = b->
coeffs[4U * i + 3U] + gamma1 - (int32_t) t3;
508 for (uint32_t i = 0U; i <
MLDSA_N / 2U; i++) {
510 t0 = (uint32_t) buf[5U * i + 0U] | ((uint32_t) buf[5U * i + 1U] << 8U)
511 | ((uint32_t) buf[5U * i + 2U] << 16U);
513 t1 = ((uint32_t) buf[5U * i + 2U] >> 4U) | ((uint32_t) buf[5U * i + 3U] << 4U)
514 | ((uint32_t) buf[5U * i + 4U] << 12U);
517 a->
coeffs[2U * i + 0U] = b->
coeffs[2U * i + 0U] + gamma1 - (int32_t) t0;
518 a->
coeffs[2U * i + 1U] = b->
coeffs[2U * i + 1U] + gamma1 - (int32_t) t1;
522 explicit_bzero(buf,
sizeof(buf));
ML-DSA low-RAM helper functions.
int32_t MLDSA_POLY_caddq(int32_t a)
Adds q if input is negative.
int32_t MLDSA_POLY_montgomery_reduce(int64_t a)
Montgomery reduction: given a 64-bit integer, compute a*q^{-1} mod 2^32.
int32_t MLDSA_POLY_reduce32(int32_t a)
Reduce coefficient to representative in about (-6283009, 6283009).
int32_t MLDSA_ROUNDING_decompose(int32_t a, int32_t *a0, int32_t gamma2)
For coefficient a, compute high and low bits a0, a1 such that a mod q = a1*ALPHA + a0,...
uint32_t MLDSA_ROUNDING_make_hint(int32_t a0, int32_t a1, int32_t gamma2)
Compute hint bit. Returns 1 if adding ct0 to w - ct0 would change the high bits (i....
int32_t MLDSA_ROUNDING_use_hint(int32_t a, uint32_t hint, int32_t gamma2)
Correct high bits using hint.
void MLDSA_SAMPLE_gamma1(mldsa_poly *a, const uint8_t seed[MLDSA_CRHBYTES], uint16_t nonce, int32_t gamma1)
Sample polynomial with coefficients in [-(gamma1-1), gamma1] from SHAKE256(seed||nonce).
void MLDSA_UTIL_shake256_seed_nonce(uint8_t *out, size_t outlen, const uint8_t *seed, size_t seedlen, uint16_t nonce)
SHAKE256 with seed || uint16_t nonce.
void MLDSA_UTIL_shake128_seed_nonce(uint8_t *out, size_t outlen, const uint8_t *seed, size_t seedlen, uint16_t nonce)
SHAKE128 with seed || uint16_t nonce.
Polynomial with MLDSA_N int32_t coefficients.