Botan 3.4.0 Crypto and TLS for C&
dilithium_polynomials.h
Go to the documentation of this file.
1/*
2* Crystals Dilithium Digital Signature Algorithms
3* Based on the public domain reference implementation by the
4* designers (https://github.com/pq-crystals/dilithium)
5*
6* Further changes
7* (C) 2021-2023 Jack Lloyd
8* (C) 2021-2022 Manuel Glaser - Rohde & Schwarz Cybersecurity
9* (C) 2021-2023 Michael Boric, RenĂ© Meusel - Rohde & Schwarz Cybersecurity
10*
12*/
13
14#ifndef BOTAN_DILITHIUM_POLYNOMIAL_H_
15#define BOTAN_DILITHIUM_POLYNOMIAL_H_
16
17#include <botan/dilithium.h>
18
19#include <botan/internal/dilithium_symmetric_primitives.h>
20#include <botan/internal/shake.h>
21
22#include <array>
23#include <span>
24#include <vector>
25
27
29 public:
30 // public member is on purpose
31 std::array<int32_t, Botan::DilithiumModeConstants::N> m_coeffs;
32
33 /**
34 * Adds two polynomials element-wise. Does not perform a reduction after the addition.
35 * Therefore this operation might cause an integer overflow.
36 */
38 for(size_t i = 0; i < this->m_coeffs.size(); ++i) {
39 this->m_coeffs[i] = this->m_coeffs[i] + other.m_coeffs[i];
40 }
41 return *this;
42 }
43
44 /**
45 * Subtracts two polynomials element-wise. Does not perform a reduction after the subtraction.
46 * Therefore this operation might cause an integer underflow.
47 */
49 for(size_t i = 0; i < this->m_coeffs.size(); ++i) {
50 this->m_coeffs[i] = this->m_coeffs[i] - other.m_coeffs[i];
51 }
52 return *this;
53 }
54
55 /***************************************************
56 * Name: rej_uniform
57 *
58 * Description: Sample uniformly random coefficients in [0, Q-1] by
59 * performing rejection sampling on array of random bytes.
60 *
61 * Arguments: - Polynomial& a: reference to output array (allocated)
62 * - size_t position: starting point
63 * - size_t len: number of coefficients to be sampled
64 * - const uint8_t *buf: array of random bytes
65 * - size_t buflen: length of array of random bytes
66 *
67 * Returns number of sampled coefficients. Can be smaller than len if not enough
68 * random bytes were given.
69 **************************************************/
70 static size_t rej_uniform(Polynomial& p, size_t position, size_t len, const uint8_t* buf, size_t buflen) {
71 size_t ctr = 0, pos = 0;
72 while(ctr < len && pos + 3 <= buflen) {
73 uint32_t t = buf[pos++];
74 t |= static_cast<uint32_t>(buf[pos++]) << 8;
75 t |= static_cast<uint32_t>(buf[pos++]) << 16;
76 t &= 0x7FFFFF;
77
79 p.m_coeffs[position + ctr++] = static_cast<int32_t>(t);
80 }
81 }
82 return ctr;
83 }
84
85 /*************************************************
86 * Name: rej_eta
87 *
88 * Description: Sample uniformly random coefficients in [-ETA, ETA] by
89 * performing rejection sampling on array of random bytes.
90 *
91 * Arguments: - Polynomial &a: pointer to output array (allocated)
92 * - size_t offset: starting point for the output polynomial
93 * - size_t len: number of coefficients to be sampled
94 * - const secure_vector<uint8_t>& buf: sv reference of random bytes
95 * - size_t buflen: length of array of random bytes
96 * - const DilithiumModeConstants&
97 *
98 * Returns number of sampled coefficients. Can be smaller than len if not enough
99 * random bytes were given.
100 **************************************************/
101 static size_t rej_eta(Polynomial& a,
102 size_t offset,
103 size_t len,
104 const secure_vector<uint8_t>& buf,
105 size_t buflen,
106 const DilithiumModeConstants& mode) {
107 size_t ctr = 0, pos = 0;
108 while(ctr < len && pos < buflen) {
109 uint32_t t0 = buf[pos] & 0x0F;
110 uint32_t t1 = buf[pos++] >> 4;
111
112 switch(mode.eta()) {
113 case DilithiumEta::Eta2: {
114 if(t0 < 15) {
115 t0 = t0 - (205 * t0 >> 10) * 5;
116 a.m_coeffs[offset + ctr++] = 2 - t0;
117 }
118 if(t1 < 15 && ctr < len) {
119 t1 = t1 - (205 * t1 >> 10) * 5;
120 a.m_coeffs[offset + ctr++] = 2 - t1;
121 }
122 } break;
123 case DilithiumEta::Eta4: {
124 if(t0 < 9) {
125 a.m_coeffs[offset + ctr++] = 4 - t0;
126 }
127 if(t1 < 9 && ctr < len) {
128 a.m_coeffs[offset + ctr++] = 4 - t1;
129 }
130 } break;
131 }
132 }
133 return ctr;
134 }
135
136 /*************************************************
137 * Name: fill_poly_uniform_eta
138 *
139 * Description: Sample polynomial with uniformly random coefficients
140 * in [-ETA,ETA] by performing rejection sampling on the
141 * output stream from SHAKE256(seed|nonce) or AES256CTR(seed,nonce).
142 *
143 * Arguments: - Polynomial& a: reference to output polynomial
144 * - const uint8_t seed[]: byte array with seed of length CRHBYTES
145 * - uint16_t nonce: 2-byte nonce
146 * - const DilithiumModeConstants& mode: Mode dependent values.
147 **************************************************/
149 const secure_vector<uint8_t>& seed,
150 uint16_t nonce,
151 const DilithiumModeConstants& mode) {
153
154 auto xof = mode.XOF_256(seed, nonce);
155
157 xof->output(buf);
158 size_t ctr = Polynomial::rej_eta(a, 0, DilithiumModeConstants::N, buf, buf.size(), mode);
159
160 while(ctr < DilithiumModeConstants::N) {
161 xof->output(std::span(buf).first(mode.stream256_blockbytes()));
162 ctr += Polynomial::rej_eta(a, ctr, DilithiumModeConstants::N - ctr, buf, mode.stream256_blockbytes(), mode);
163 }
164 }
165
166 /*************************************************
167 * Name: power2round
168 *
169 * Description: For finite field element a, compute a0, a1 such that
170 * a mod^+ Q = a1*2^D + a0 with -2^{D-1} < a0 <= 2^{D-1}.
171 * Assumes a to be standard representative.
172 *
173 * Arguments: - int32_t a: input element
174 * - int32_t *a0: pointer to output element a0
175 *
176 * Returns a1.
177 **************************************************/
178 static int32_t power2round(int32_t& a0, int32_t a) {
179 int32_t a1 = (a + (1 << (DilithiumModeConstants::D - 1)) - 1) >> DilithiumModeConstants::D;
180 a0 = a - (a1 << DilithiumModeConstants::D);
181 return a1;
182 }
183
184 /*************************************************
185 * Name: fill_polys_power2round
186 *
187 * Description: For all coefficients c of the input polynomial,
188 * compute c0, c1 such that c mod Q = c1*2^D + c0
189 * with -2^{D-1} < c0 <= 2^{D-1}. Assumes coefficients to be
190 * standard representatives.
191 *
192 * Arguments: - Polynomial& a1: pointer to output polynomial with coefficients c1
193 * - Polynomial& a0: pointer to output polynomial with coefficients c0
194 * - const Polynomial& a: pointer to input polynomial
195 **************************************************/
196 static void fill_polys_power2round(Polynomial& a1, Polynomial& a0, const Polynomial& a) {
197 for(size_t i = 0; i < DilithiumModeConstants::N; ++i) {
199 }
200 }
201
202 /*************************************************
203 * Name: challenge
204 *
205 * Description: Implementation of H. Samples polynomial with TAU nonzero
206 * coefficients in {-1,1} using the output stream of
207 * SHAKE256(seed).
208 *
209 * Arguments: - Polynomial &c: pointer to output polynomial
210 * - const uint8_t mu[]: byte array containing seed of length SEEDBYTES
211 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
212 **************************************************/
213 static Polynomial poly_challenge(const uint8_t* seed, const DilithiumModeConstants& mode) {
214 Polynomial c;
215
217 shake256_hasher.update(seed, DilithiumModeConstants::SEEDBYTES);
218 auto buf = shake256_hasher.final();
219
220 uint64_t signs = 0;
221 for(size_t i = 0; i < 8; ++i) {
222 signs |= static_cast<uint64_t>(buf[i]) << 8 * i;
223 }
224 size_t pos = 8;
225
226 for(size_t i = 0; i < DilithiumModeConstants::N; ++i) {
227 c.m_coeffs[i] = 0;
228 }
229 for(size_t i = DilithiumModeConstants::N - mode.tau(); i < DilithiumModeConstants::N; ++i) {
230 size_t b;
231 do {
232 b = buf[pos++];
233 } while(b > i);
234
235 c.m_coeffs[i] = c.m_coeffs[b];
236 c.m_coeffs[b] = 1 - 2 * (signs & 1);
237 signs >>= 1;
238 }
239 return c;
240 }
241
242 /*************************************************
243 * Name: poly_chknorm
244 *
245 * Description: Check infinity norm of polynomial against given bound.
246 * Assumes input coefficients were reduced by reduce32().
247 *
248 * Arguments: - const Polynomial& a: pointer to polynomial
249 * - size_t B: norm bound
250 *
251 * Returns false if norm is strictly smaller than B <= (Q-1)/8 and true otherwise.
252 **************************************************/
253 static bool poly_chknorm(const Polynomial& a, size_t B) {
254 if(B > (DilithiumModeConstants::Q - 1) / 8) {
255 return true;
256 }
257
258 /* It is ok to leak which coefficient violates the bound since
259 the probability for each coefficient is independent of secret
260 data but we must not leak the sign of the centralized representative. */
261 for(const auto& coeff : a.m_coeffs) {
262 /* Absolute value */
263 size_t t = coeff >> 31;
264 t = coeff - (t & 2 * coeff);
265
266 if(t >= B) {
267 return true;
268 }
269 }
270 return false;
271 }
272
273 /*************************************************
274 * Name: make_hint
275 *
276 * Description: Compute hint bit indicating whether the low bits of the
277 * input element overflow into the high bits. Inputs assumed
278 * to be standard representatives.
279 *
280 * Arguments: - size_t a0: low bits of input element
281 * - size_t a1: high bits of input element
282 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
283 *
284 * Returns 1 if overflow.
285 **************************************************/
286 static int32_t make_hint(size_t a0, size_t a1, const DilithiumModeConstants& mode) {
287 const auto gamma2 = mode.gamma2();
288 const auto Q_gamma2 = DilithiumModeConstants::Q - gamma2;
289 if(a0 <= gamma2 || a0 > Q_gamma2 || (a0 == Q_gamma2 && a1 == 0)) {
290 return 0;
291 }
292 return 1;
293 }
294
295 /*************************************************
296 * Name: generate_hint_polynomial
297 *
298 * Description: Compute hint polynomial. The coefficients of which indicate
299 * whether the low bits of the corresponding coefficient of
300 * the input polynomial overflow into the high bits.
301 *
302 * Arguments: - Polynomial& h: reference to output hint polynomial
303 * - const Polynomial& a0: reference to low part of input polynomial
304 * - const Polynomial& a1: reference to high part of input polynomial
305 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
306 *
307 * Returns number of 1 bits.
308 **************************************************/
310 const Polynomial& a0,
311 const Polynomial& a1,
312 const DilithiumModeConstants& mode) {
313 size_t s = 0;
314
315 for(size_t i = 0; i < DilithiumModeConstants::N; ++i) {
316 h.m_coeffs[i] = Polynomial::make_hint(a0.m_coeffs[i], a1.m_coeffs[i], mode);
317 s += h.m_coeffs[i];
318 }
319
320 return s;
321 }
322
323 /*************************************************
324 * Name: decompose
325 *
326 * Description: For finite field element a, compute high and low bits a0, a1 such
327 * that a mod^+ Q = a1*ALPHA + a0 with -ALPHA/2 < a0 <= ALPHA/2 except
328 * if a1 = (Q-1)/ALPHA where we set a1 = 0 and
329 * -ALPHA/2 <= a0 = a mod^+ Q - Q < 0. Assumes a to be standard
330 * representative.
331 *
332 * Arguments: - int32_t a: input element
333 * - int32_t *a0: pointer to output element a0
334 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
335 *
336 * Returns a1.
337 **************************************************/
338 static int32_t decompose(int32_t* a0, int32_t a, const DilithiumModeConstants& mode) {
339 int32_t a1 = (a + 127) >> 7;
340 if(mode.gamma2() == (DilithiumModeConstants::Q - 1) / 32) {
341 a1 = (a1 * 1025 + (1 << 21)) >> 22;
342 a1 &= 15;
343 } else {
345 a1 = (a1 * 11275 + (1 << 23)) >> 24;
346 a1 ^= ((43 - a1) >> 31) & a1;
347 }
348
349 *a0 = a - a1 * 2 * static_cast<int32_t>(mode.gamma2());
350 *a0 -= (((DilithiumModeConstants::Q - 1) / 2 - *a0) >> 31) & DilithiumModeConstants::Q;
351 return a1;
352 }
353
354 /*************************************************
355 * Name: use_hint
356 *
357 * Description: Correct high bits according to hint.
358 *
359 * Arguments: - int32_t a: input element
360 * - size_t hint: hint bit
361 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
362 *
363 * Returns corrected high bits.
364 **************************************************/
365 static int32_t use_hint(int32_t a, size_t hint, const DilithiumModeConstants& mode) {
366 int32_t a0;
367
368 int32_t a1 = Polynomial::decompose(&a0, a, mode);
369 if(hint == 0) {
370 return a1;
371 }
372
373 if(mode.gamma2() == ((DilithiumModeConstants::Q - 1) / 32)) {
374 if(a0 > 0) {
375 return (a1 + 1) & 15;
376 } else {
377 return (a1 - 1) & 15;
378 }
379 } else {
380 if(a0 > 0) {
381 return (a1 == 43) ? 0 : a1 + 1;
382 } else {
383 return (a1 == 0) ? 43 : a1 - 1;
384 }
385 }
386 }
387
388 /*************************************************
389 * Name: poly_use_hint
390 *
391 * Description: Use hint polynomial to correct the high bits of a polynomial.
392 *
393 * Arguments: - Polynomial& b: reference to output polynomial with corrected high bits
394 * - const Polynomial& a: reference to input polynomial
395 * - const Polynomial& h: reference to input hint polynomial
396 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
397 *
398 **************************************************/
399 static void poly_use_hint(Polynomial& b,
400 const Polynomial& a,
401 const Polynomial& h,
402 const DilithiumModeConstants& mode) {
403 for(size_t i = 0; i < DilithiumModeConstants::N; ++i) {
404 b.m_coeffs[i] = Polynomial::use_hint(a.m_coeffs[i], h.m_coeffs[i], mode);
405 }
406 }
407
408 /*************************************************
409 * Name: montgomery_reduce
410 *
411 * Description: For finite field element a with -2^{31}Q <= a <= Q*2^31,
412 * compute r \equiv a*2^{-32} (mod Q) such that -Q < r < Q.
413 *
414 * Arguments: - int64_t: finite field element a
415 *
416 * Returns r.
417 **************************************************/
418 int32_t montgomery_reduce(int64_t a) const {
419 int32_t t = static_cast<int32_t>(static_cast<int64_t>(static_cast<int32_t>(a)) * DilithiumModeConstants::QINV);
420 t = (a - static_cast<int64_t>(t) * DilithiumModeConstants::Q) >> 32;
421 return t;
422 }
423
424 /*************************************************
425 * Name: poly_pointwise_montgomery
426 *
427 * Description: Pointwise multiplication of polynomials in NTT domain
428 * representation and multiplication of resulting polynomial
429 * by 2^{-32}.
430 * For finite field element a with -2^{31}Q <= a <= Q*2^31,
431 * compute r \equiv a*2^{-32} (mod Q) such that -Q < r < Q.
432 *
433 * Arguments: - Polynomial& c: reference to output polynomial
434 * - const Polynomial& a: reference to first input polynomial
435 * - const Polynomial& b: reference to second input polynomial
436 **************************************************/
437 void poly_pointwise_montgomery(Polynomial& output, const Polynomial& second) const {
438 for(size_t i = 0; i < DilithiumModeConstants::N; ++i) {
439 output.m_coeffs[i] = montgomery_reduce(static_cast<int64_t>(m_coeffs[i]) * second.m_coeffs[i]);
440 }
441 }
442
443 /*************************************************
444 * Name: ntt
445 *
446 * Description: Forward NTT, in-place. No modular reduction is performed after
447 * additions or subtractions. Output vector is in bitreversed order.
448 *
449 * Arguments: - Polynomial& a: input/output coefficient Polynomial
450 **************************************************/
451 void ntt() {
452 size_t j;
453 size_t k = 0;
454
455 for(size_t len = 128; len > 0; len >>= 1) {
456 for(size_t start = 0; start < DilithiumModeConstants::N; start = j + len) {
457 int32_t zeta = DilithiumModeConstants::ZETAS[++k];
458 for(j = start; j < start + len; ++j) {
459 int32_t t = montgomery_reduce(static_cast<int64_t>(zeta) * m_coeffs[j + len]);
460 m_coeffs[j + len] = m_coeffs[j] - t;
461 m_coeffs[j] = m_coeffs[j] + t;
462 }
463 }
464 }
465 }
466
467 /*************************************************
468 * Name: poly_reduce
469 *
470 * Description: Inplace reduction of all coefficients of polynomial to
471 * representative in [-6283009,6283007].
472 * For finite field element a with a <= 2^{31} - 2^{22} - 1,
473 * compute r \equiv a (mod Q) such that -6283009 <= r <= 6283007.
474 *
475 * Arguments: - Polynomial &a: reference to input polynomial
476 **************************************************/
477 void poly_reduce() {
478 for(auto& i : m_coeffs) {
479 int32_t t = (i + (1 << 22)) >> 23;
480 t = i - t * DilithiumModeConstants::Q;
481 i = t;
482 }
483 }
484
485 /*************************************************
486 * Name: invntt_tomont
487 *
488 * Description: Inverse NTT and multiplication by Montgomery factor 2^32.
489 * In-place. No modular reductions after additions or
490 * subtractions; input coefficients need to be smaller than
491 * Q in absolute value. Output coefficient are smaller than Q in
492 * absolute value.
493 **************************************************/
495 size_t j;
496 int32_t f = 41978; // mont^2/256
497 size_t k = 256;
498 for(size_t len = 1; len < DilithiumModeConstants::N; len <<= 1) {
499 for(size_t start = 0; start < DilithiumModeConstants::N; start = j + len) {
500 int32_t zeta = -DilithiumModeConstants::ZETAS[--k];
501 for(j = start; j < start + len; ++j) {
502 int32_t t = m_coeffs[j];
503 m_coeffs[j] = t + m_coeffs[j + len];
504 m_coeffs[j + len] = t - m_coeffs[j + len];
505 m_coeffs[j + len] = montgomery_reduce(static_cast<int64_t>(zeta) * m_coeffs[j + len]);
506 }
507 }
508 }
509
510 for(j = 0; j < DilithiumModeConstants::N; ++j) {
511 m_coeffs[j] = montgomery_reduce(static_cast<int64_t>(f) * m_coeffs[j]);
512 }
513 }
514
515 /*************************************************
516 * Name: poly_invntt_tomont
517 *
518 * Description: Inplace inverse NTT and multiplication by 2^{32}.
519 * Input coefficients need to be less than Q in absolute
520 * value and output coefficients are again bounded by Q.
521 *
522 * Arguments: - Polynomial& a: reference to input/output polynomial
523 **************************************************/
525
526 /*************************************************
528 *
529 * Description: For all coefficients of in/out polynomial add Q if
530 * coefficient is negative.
531 * Add Q if input coefficient is negative.
532 **************************************************/
534 for(auto& i : m_coeffs) {
535 i += (i >> 31) & DilithiumModeConstants::Q;
536 }
537 }
538
539 /*************************************************
540 * Name: poly_uniform_gamma1
541 *
542 * Description: Sample polynomial with uniformly random coefficients
543 * in [-(GAMMA1 - 1), GAMMA1] by unpacking output stream
544 * of SHAKE256(seed|nonce) or AES256CTR(seed,nonce).
545 *
546 * Arguments: - const secure_vector<uint8_t>& seed: vector with seed of length CRHBYTES
547 * - uint16_t nonce: 16-bit nonce
548 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
549 **************************************************/
550 void poly_uniform_gamma1(const secure_vector<uint8_t>& seed, uint16_t nonce, const DilithiumModeConstants& mode) {
551 auto buf = mode.ExpandMask(seed, nonce);
552
553 Polynomial::polyz_unpack(*this, buf.data(), mode);
554 }
555
556 /*************************************************
557 * Name: poly_decompose
558 *
559 * Description: For all coefficients c of the input polynomial,
560 * compute high and low bits c0, c1 such c mod Q = c1*ALPHA + c0
561 * with -ALPHA/2 < c0 <= ALPHA/2 except c1 = (Q-1)/ALPHA where we
562 * set c1 = 0 and -ALPHA/2 <= c0 = c mod Q - Q < 0.
563 * Assumes coefficients to be standard representatives.
564 *
565 * Arguments: - Polynomial& a1: reference to output polynomial with coefficients c1
566 * - Polynomial& a0: reference to output polynomial with coefficients c0
567 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
568 **************************************************/
569 void poly_decompose(Polynomial& a1, Polynomial& a0, const DilithiumModeConstants& mode) const {
570 for(size_t i = 0; i < DilithiumModeConstants::N; ++i) {
571 a1.m_coeffs[i] = Polynomial::decompose(&a0.m_coeffs[i], m_coeffs[i], mode);
572 }
573 }
574
575 /*************************************************
576 * Name: poly_shiftl
577 *
578 * Description: Multiply polynomial by 2^D without modular reduction. Assumes
579 * input coefficients to be less than 2^{31-D} in absolute value.
580 *
581 * Arguments: - Polynomial& a: pointer to input/output polynomial
582 **************************************************/
583 void poly_shiftl() {
584 for(size_t i = 0; i < m_coeffs.size(); ++i) {
586 }
587 }
588
589 /*************************************************
590 * Name: polyw1_pack
591 *
592 * Description: Bit-pack polynomial w1 with coefficients in [0,15] or [0,43].
593 * Input coefficients are assumed to be standard representatives.
594 *
595 * Arguments: - uint8_t *r: pointer to output byte array with at least
596 * POLYW1_PACKEDBYTES bytes
597 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
598 **************************************************/
599 void polyw1_pack(uint8_t* r, const DilithiumModeConstants& mode) {
600 if(mode.gamma2() == (DilithiumModeConstants::Q - 1) / 88) {
601 for(size_t i = 0; i < DilithiumModeConstants::N / 4; ++i) {
602 r[3 * i + 0] = static_cast<uint8_t>(m_coeffs[4 * i + 0]);
603 r[3 * i + 0] |= static_cast<uint8_t>(m_coeffs[4 * i + 1] << 6);
604 r[3 * i + 1] = static_cast<uint8_t>(m_coeffs[4 * i + 1] >> 2);
605 r[3 * i + 1] |= static_cast<uint8_t>(m_coeffs[4 * i + 2] << 4);
606 r[3 * i + 2] = static_cast<uint8_t>(m_coeffs[4 * i + 2] >> 4);
607 r[3 * i + 2] |= static_cast<uint8_t>(m_coeffs[4 * i + 3] << 2);
608 }
609 } else {
611 for(size_t i = 0; i < DilithiumModeConstants::N / 2; ++i) {
612 r[i] = static_cast<uint8_t>(m_coeffs[2 * i + 0] | (m_coeffs[2 * i + 1] << 4));
613 }
614 }
615 }
616
617 /*************************************************
618 * Name: polyeta_unpack
619 *
620 * Description: Unpack polynomial with coefficients in [-ETA,ETA].
621 *
622 * Arguments: - Polynomial& r: reference to output polynomial
623 * - const uint8_t *a: byte array with bit-packed_t1 polynomial
624 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
625 **************************************************/
626 static Polynomial polyeta_unpack(std::span<const uint8_t> a, const DilithiumModeConstants& mode) {
627 Polynomial r;
628
629 switch(mode.eta()) {
630 case DilithiumEta::Eta2: {
631 for(size_t i = 0; i < DilithiumModeConstants::N / 8; ++i) {
632 r.m_coeffs[8 * i + 0] = (a[3 * i + 0] >> 0) & 7;
633 r.m_coeffs[8 * i + 1] = (a[3 * i + 0] >> 3) & 7;
634 r.m_coeffs[8 * i + 2] = ((a[3 * i + 0] >> 6) | (a[3 * i + 1] << 2)) & 7;
635 r.m_coeffs[8 * i + 3] = (a[3 * i + 1] >> 1) & 7;
636 r.m_coeffs[8 * i + 4] = (a[3 * i + 1] >> 4) & 7;
637 r.m_coeffs[8 * i + 5] = ((a[3 * i + 1] >> 7) | (a[3 * i + 2] << 1)) & 7;
638 r.m_coeffs[8 * i + 6] = (a[3 * i + 2] >> 2) & 7;
639 r.m_coeffs[8 * i + 7] = (a[3 * i + 2] >> 5) & 7;
640
641 r.m_coeffs[8 * i + 0] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[8 * i + 0];
642 r.m_coeffs[8 * i + 1] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[8 * i + 1];
643 r.m_coeffs[8 * i + 2] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[8 * i + 2];
644 r.m_coeffs[8 * i + 3] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[8 * i + 3];
645 r.m_coeffs[8 * i + 4] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[8 * i + 4];
646 r.m_coeffs[8 * i + 5] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[8 * i + 5];
647 r.m_coeffs[8 * i + 6] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[8 * i + 6];
648 r.m_coeffs[8 * i + 7] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[8 * i + 7];
649 }
650 } break;
651 case DilithiumEta::Eta4: {
652 for(size_t i = 0; i < DilithiumModeConstants::N / 2; ++i) {
653 r.m_coeffs[2 * i + 0] = a[i] & 0x0F;
654 r.m_coeffs[2 * i + 1] = a[i] >> 4;
655 r.m_coeffs[2 * i + 0] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[2 * i + 0];
656 r.m_coeffs[2 * i + 1] = static_cast<uint8_t>(mode.eta()) - r.m_coeffs[2 * i + 1];
657 }
658 } break;
659 }
660
661 return r;
662 }
663
664 /*************************************************
665 * Name: polyeta_pack
666 *
667 * Description: Bit-pack polynomial with coefficients in [-ETA,ETA].
668 *
669 * Arguments: - uint8_t *r: pointer to output byte array with at least
670 * POLYETA_PACKEDBYTES bytes
671 * - const Polynomial& a: pointer to input polynomial
672 * - const DilithiumModeConstants& mode: reference for dilithium mode values
673 **************************************************/
674 void polyeta_pack(uint8_t* r, const DilithiumModeConstants& mode) const {
675 uint8_t t[8];
676
677 switch(mode.eta()) {
678 case DilithiumEta::Eta2: {
679 for(size_t i = 0; i < DilithiumModeConstants::N / 8; ++i) {
680 t[0] = static_cast<uint8_t>(mode.eta() - m_coeffs[8 * i + 0]);
681 t[1] = static_cast<uint8_t>(mode.eta() - m_coeffs[8 * i + 1]);
682 t[2] = static_cast<uint8_t>(mode.eta() - m_coeffs[8 * i + 2]);
683 t[3] = static_cast<uint8_t>(mode.eta() - m_coeffs[8 * i + 3]);
684 t[4] = static_cast<uint8_t>(mode.eta() - m_coeffs[8 * i + 4]);
685 t[5] = static_cast<uint8_t>(mode.eta() - m_coeffs[8 * i + 5]);
686 t[6] = static_cast<uint8_t>(mode.eta() - m_coeffs[8 * i + 6]);
687 t[7] = static_cast<uint8_t>(mode.eta() - m_coeffs[8 * i + 7]);
688
689 r[3 * i + 0] = (t[0] >> 0) | (t[1] << 3) | (t[2] << 6);
690 r[3 * i + 1] = (t[2] >> 2) | (t[3] << 1) | (t[4] << 4) | (t[5] << 7);
691 r[3 * i + 2] = (t[5] >> 1) | (t[6] << 2) | (t[7] << 5);
692 }
693 } break;
694 case DilithiumEta::Eta4: {
695 for(size_t i = 0; i < DilithiumModeConstants::N / 2; ++i) {
696 t[0] = static_cast<uint8_t>(mode.eta() - m_coeffs[2 * i + 0]);
697 t[1] = static_cast<uint8_t>(mode.eta() - m_coeffs[2 * i + 1]);
698 r[i] = static_cast<uint8_t>(t[0] | (t[1] << 4));
699 }
700 } break;
701 }
702 }
703
704 /*************************************************
705 * Name: polyt0_unpack
706 *
707 * Description: Unpack polynomial t0 with coefficients in ]-2^{D-1}, 2^{D-1}].
708 *
709 * Arguments: - poly *r: pointer to output polynomial
710 * - const uint8_t *a: byte array with bit-packed_t1 polynomial
711 **************************************************/
712 static Polynomial polyt0_unpack(std::span<const uint8_t> a) {
713 Polynomial r;
714
715 for(size_t i = 0; i < DilithiumModeConstants::N / 8; ++i) {
716 r.m_coeffs[8 * i + 0] = a[13 * i + 0];
717 r.m_coeffs[8 * i + 0] |= static_cast<uint32_t>(a[13 * i + 1]) << 8;
718 r.m_coeffs[8 * i + 0] &= 0x1FFF;
719
720 r.m_coeffs[8 * i + 1] = a[13 * i + 1] >> 5;
721 r.m_coeffs[8 * i + 1] |= static_cast<uint32_t>(a[13 * i + 2]) << 3;
722 r.m_coeffs[8 * i + 1] |= static_cast<uint32_t>(a[13 * i + 3]) << 11;
723 r.m_coeffs[8 * i + 1] &= 0x1FFF;
724
725 r.m_coeffs[8 * i + 2] = a[13 * i + 3] >> 2;
726 r.m_coeffs[8 * i + 2] |= static_cast<uint32_t>(a[13 * i + 4]) << 6;
727 r.m_coeffs[8 * i + 2] &= 0x1FFF;
728
729 r.m_coeffs[8 * i + 3] = a[13 * i + 4] >> 7;
730 r.m_coeffs[8 * i + 3] |= static_cast<uint32_t>(a[13 * i + 5]) << 1;
731 r.m_coeffs[8 * i + 3] |= static_cast<uint32_t>(a[13 * i + 6]) << 9;
732 r.m_coeffs[8 * i + 3] &= 0x1FFF;
733
734 r.m_coeffs[8 * i + 4] = a[13 * i + 6] >> 4;
735 r.m_coeffs[8 * i + 4] |= static_cast<uint32_t>(a[13 * i + 7]) << 4;
736 r.m_coeffs[8 * i + 4] |= static_cast<uint32_t>(a[13 * i + 8]) << 12;
737 r.m_coeffs[8 * i + 4] &= 0x1FFF;
738
739 r.m_coeffs[8 * i + 5] = a[13 * i + 8] >> 1;
740 r.m_coeffs[8 * i + 5] |= static_cast<uint32_t>(a[13 * i + 9]) << 7;
741 r.m_coeffs[8 * i + 5] &= 0x1FFF;
742
743 r.m_coeffs[8 * i + 6] = a[13 * i + 9] >> 6;
744 r.m_coeffs[8 * i + 6] |= static_cast<uint32_t>(a[13 * i + 10]) << 2;
745 r.m_coeffs[8 * i + 6] |= static_cast<uint32_t>(a[13 * i + 11]) << 10;
746 r.m_coeffs[8 * i + 6] &= 0x1FFF;
747
748 r.m_coeffs[8 * i + 7] = a[13 * i + 11] >> 3;
749 r.m_coeffs[8 * i + 7] |= static_cast<uint32_t>(a[13 * i + 12]) << 5;
750 r.m_coeffs[8 * i + 7] &= 0x1FFF;
751
752 r.m_coeffs[8 * i + 0] = (1 << (DilithiumModeConstants::D - 1)) - r.m_coeffs[8 * i + 0];
753 r.m_coeffs[8 * i + 1] = (1 << (DilithiumModeConstants::D - 1)) - r.m_coeffs[8 * i + 1];
754 r.m_coeffs[8 * i + 2] = (1 << (DilithiumModeConstants::D - 1)) - r.m_coeffs[8 * i + 2];
755 r.m_coeffs[8 * i + 3] = (1 << (DilithiumModeConstants::D - 1)) - r.m_coeffs[8 * i + 3];
756 r.m_coeffs[8 * i + 4] = (1 << (DilithiumModeConstants::D - 1)) - r.m_coeffs[8 * i + 4];
757 r.m_coeffs[8 * i + 5] = (1 << (DilithiumModeConstants::D - 1)) - r.m_coeffs[8 * i + 5];
758 r.m_coeffs[8 * i + 6] = (1 << (DilithiumModeConstants::D - 1)) - r.m_coeffs[8 * i + 6];
759 r.m_coeffs[8 * i + 7] = (1 << (DilithiumModeConstants::D - 1)) - r.m_coeffs[8 * i + 7];
760 }
761
762 return r;
763 }
764
765 /*************************************************
766 * Name: polyt0_pack
767 *
768 * Description: Bit-pack polynomial t0 with coefficients in ]-2^{D-1}, 2^{D-1}].
769 *
770 * Arguments: - uint8_t *r: pointer to output byte array with at least
771 * POLYT0_PACKEDBYTES bytes
772 * - const Polynomial& a: reference to input polynomial
773 **************************************************/
774 void polyt0_pack(uint8_t* r) const {
775 uint32_t t[8];
776 for(size_t i = 0; i < DilithiumModeConstants::N / 8; ++i) {
777 t[0] = (1 << (DilithiumModeConstants::D - 1)) - m_coeffs[8 * i + 0];
778 t[1] = (1 << (DilithiumModeConstants::D - 1)) - m_coeffs[8 * i + 1];
779 t[2] = (1 << (DilithiumModeConstants::D - 1)) - m_coeffs[8 * i + 2];
780 t[3] = (1 << (DilithiumModeConstants::D - 1)) - m_coeffs[8 * i + 3];
781 t[4] = (1 << (DilithiumModeConstants::D - 1)) - m_coeffs[8 * i + 4];
782 t[5] = (1 << (DilithiumModeConstants::D - 1)) - m_coeffs[8 * i + 5];
783 t[6] = (1 << (DilithiumModeConstants::D - 1)) - m_coeffs[8 * i + 6];
784 t[7] = (1 << (DilithiumModeConstants::D - 1)) - m_coeffs[8 * i + 7];
785
786 r[13 * i + 0] = static_cast<uint8_t>(t[0]);
787 r[13 * i + 1] = static_cast<uint8_t>(t[0] >> 8);
788 r[13 * i + 1] |= static_cast<uint8_t>(t[1] << 5);
789 r[13 * i + 2] = static_cast<uint8_t>(t[1] >> 3);
790 r[13 * i + 3] = static_cast<uint8_t>(t[1] >> 11);
791 r[13 * i + 3] |= static_cast<uint8_t>(t[2] << 2);
792 r[13 * i + 4] = static_cast<uint8_t>(t[2] >> 6);
793 r[13 * i + 4] |= static_cast<uint8_t>(t[3] << 7);
794 r[13 * i + 5] = static_cast<uint8_t>(t[3] >> 1);
795 r[13 * i + 6] = static_cast<uint8_t>(t[3] >> 9);
796 r[13 * i + 6] |= static_cast<uint8_t>(t[4] << 4);
797 r[13 * i + 7] = static_cast<uint8_t>(t[4] >> 4);
798 r[13 * i + 8] = static_cast<uint8_t>(t[4] >> 12);
799 r[13 * i + 8] |= static_cast<uint8_t>(t[5] << 1);
800 r[13 * i + 9] = static_cast<uint8_t>(t[5] >> 7);
801 r[13 * i + 9] |= static_cast<uint8_t>(t[6] << 6);
802 r[13 * i + 10] = static_cast<uint8_t>(t[6] >> 2);
803 r[13 * i + 11] = static_cast<uint8_t>(t[6] >> 10);
804 r[13 * i + 11] |= static_cast<uint8_t>(t[7] << 3);
805 r[13 * i + 12] = static_cast<uint8_t>(t[7] >> 5);
806 }
807 }
808
809 /*************************************************
810 * Name: polyz_unpack
811 *
812 * Description: Unpack polynomial z with coefficients
813 * in [-(GAMMA1 - 1), GAMMA1].
814 *
815 * Arguments: - Polynomial& r: pointer to output polynomial
816 * - const uint8_t *a: byte array with bit-packed_t1 polynomial
817 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
818 **************************************************/
819 static void polyz_unpack(Polynomial& r, const uint8_t* a, const DilithiumModeConstants& mode) {
820 if(mode.gamma1() == (1 << 17)) {
821 for(size_t i = 0; i < DilithiumModeConstants::N / 4; ++i) {
822 r.m_coeffs[4 * i + 0] = a[9 * i + 0];
823 r.m_coeffs[4 * i + 0] |= static_cast<uint32_t>(a[9 * i + 1]) << 8;
824 r.m_coeffs[4 * i + 0] |= static_cast<uint32_t>(a[9 * i + 2]) << 16;
825 r.m_coeffs[4 * i + 0] &= 0x3FFFF;
826
827 r.m_coeffs[4 * i + 1] = a[9 * i + 2] >> 2;
828 r.m_coeffs[4 * i + 1] |= static_cast<uint32_t>(a[9 * i + 3]) << 6;
829 r.m_coeffs[4 * i + 1] |= static_cast<uint32_t>(a[9 * i + 4]) << 14;
830 r.m_coeffs[4 * i + 1] &= 0x3FFFF;
831
832 r.m_coeffs[4 * i + 2] = a[9 * i + 4] >> 4;
833 r.m_coeffs[4 * i + 2] |= static_cast<uint32_t>(a[9 * i + 5]) << 4;
834 r.m_coeffs[4 * i + 2] |= static_cast<uint32_t>(a[9 * i + 6]) << 12;
835 r.m_coeffs[4 * i + 2] &= 0x3FFFF;
836
837 r.m_coeffs[4 * i + 3] = a[9 * i + 6] >> 6;
838 r.m_coeffs[4 * i + 3] |= static_cast<uint32_t>(a[9 * i + 7]) << 2;
839 r.m_coeffs[4 * i + 3] |= static_cast<uint32_t>(a[9 * i + 8]) << 10;
840 r.m_coeffs[4 * i + 3] &= 0x3FFFF;
841
842 r.m_coeffs[4 * i + 0] = static_cast<uint32_t>(mode.gamma1()) - r.m_coeffs[4 * i + 0];
843 r.m_coeffs[4 * i + 1] = static_cast<uint32_t>(mode.gamma1()) - r.m_coeffs[4 * i + 1];
844 r.m_coeffs[4 * i + 2] = static_cast<uint32_t>(mode.gamma1()) - r.m_coeffs[4 * i + 2];
845 r.m_coeffs[4 * i + 3] = static_cast<uint32_t>(mode.gamma1()) - r.m_coeffs[4 * i + 3];
846 }
847 } else if(mode.gamma1() == (1 << 19)) {
848 for(size_t i = 0; i < DilithiumModeConstants::N / 2; ++i) {
849 r.m_coeffs[2 * i + 0] = a[5 * i + 0];
850 r.m_coeffs[2 * i + 0] |= static_cast<uint32_t>(a[5 * i + 1]) << 8;
851 r.m_coeffs[2 * i + 0] |= static_cast<uint32_t>(a[5 * i + 2]) << 16;
852 r.m_coeffs[2 * i + 0] &= 0xFFFFF;
853
854 r.m_coeffs[2 * i + 1] = a[5 * i + 2] >> 4;
855 r.m_coeffs[2 * i + 1] |= static_cast<uint32_t>(a[5 * i + 3]) << 4;
856 r.m_coeffs[2 * i + 1] |= static_cast<uint32_t>(a[5 * i + 4]) << 12;
857 r.m_coeffs[2 * i + 0] &= 0xFFFFF;
858
859 r.m_coeffs[2 * i + 0] = static_cast<uint32_t>(mode.gamma1()) - r.m_coeffs[2 * i + 0];
860 r.m_coeffs[2 * i + 1] = static_cast<uint32_t>(mode.gamma1()) - r.m_coeffs[2 * i + 1];
861 }
862 }
863 }
864
865 /*************************************************
866 * Name: polyz_pack
867 *
868 * Description: Bit-pack polynomial with coefficients
869 * in [-(GAMMA1 - 1), GAMMA1].
870 *
871 * Arguments: - uint8_t *r: pointer to output byte array with at least
872 * POLYZ_PACKEDBYTES bytes
873 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
874 **************************************************/
875 void polyz_pack(uint8_t* r, const DilithiumModeConstants& mode) const {
876 uint32_t t[4];
877 if(mode.gamma1() == (1 << 17)) {
878 for(size_t i = 0; i < DilithiumModeConstants::N / 4; ++i) {
879 t[0] = static_cast<uint32_t>(mode.gamma1()) - m_coeffs[4 * i + 0];
880 t[1] = static_cast<uint32_t>(mode.gamma1()) - m_coeffs[4 * i + 1];
881 t[2] = static_cast<uint32_t>(mode.gamma1()) - m_coeffs[4 * i + 2];
882 t[3] = static_cast<uint32_t>(mode.gamma1()) - m_coeffs[4 * i + 3];
883
884 r[9 * i + 0] = static_cast<uint8_t>(t[0]);
885 r[9 * i + 1] = static_cast<uint8_t>(t[0] >> 8);
886 r[9 * i + 2] = static_cast<uint8_t>(t[0] >> 16);
887 r[9 * i + 2] |= static_cast<uint8_t>(t[1] << 2);
888 r[9 * i + 3] = static_cast<uint8_t>(t[1] >> 6);
889 r[9 * i + 4] = static_cast<uint8_t>(t[1] >> 14);
890 r[9 * i + 4] |= static_cast<uint8_t>(t[2] << 4);
891 r[9 * i + 5] = static_cast<uint8_t>(t[2] >> 4);
892 r[9 * i + 6] = static_cast<uint8_t>(t[2] >> 12);
893 r[9 * i + 6] |= static_cast<uint8_t>(t[3] << 6);
894 r[9 * i + 7] = static_cast<uint8_t>(t[3] >> 2);
895 r[9 * i + 8] = static_cast<uint8_t>(t[3] >> 10);
896 }
897 } else if(mode.gamma1() == (1 << 19)) {
898 for(size_t i = 0; i < DilithiumModeConstants::N / 2; ++i) {
899 t[0] = static_cast<uint32_t>(mode.gamma1()) - m_coeffs[2 * i + 0];
900 t[1] = static_cast<uint32_t>(mode.gamma1()) - m_coeffs[2 * i + 1];
901
902 r[5 * i + 0] = static_cast<uint8_t>(t[0]);
903 r[5 * i + 1] = static_cast<uint8_t>(t[0] >> 8);
904 r[5 * i + 2] = static_cast<uint8_t>(t[0] >> 16);
905 r[5 * i + 2] |= static_cast<uint8_t>(t[1] << 4);
906 r[5 * i + 3] = static_cast<uint8_t>(t[1] >> 4);
907 r[5 * i + 4] = static_cast<uint8_t>(t[1] >> 12);
908 }
909 }
910 }
911
912 /*************************************************
913 * Name: polyt1_unpack
914 *
915 * Description: Unpack polynomial t1 with 10-bit coefficients.
916 * Output coefficients are standard representatives.
917 *
918 * Arguments: - Polynomial& r: pointer to output polynomial
919 * - const uint8_t *a: byte array with bit-packed_t1 polynomial
920 **************************************************/
921 static void polyt1_unpack(Polynomial& r, const uint8_t* a) {
922 for(size_t i = 0; i < DilithiumModeConstants::N / 4; ++i) {
923 r.m_coeffs[4 * i + 0] = ((a[5 * i + 0] >> 0) | (static_cast<uint32_t>(a[5 * i + 1]) << 8)) & 0x3FF;
924 r.m_coeffs[4 * i + 1] = ((a[5 * i + 1] >> 2) | (static_cast<uint32_t>(a[5 * i + 2]) << 6)) & 0x3FF;
925 r.m_coeffs[4 * i + 2] = ((a[5 * i + 2] >> 4) | (static_cast<uint32_t>(a[5 * i + 3]) << 4)) & 0x3FF;
926 r.m_coeffs[4 * i + 3] = ((a[5 * i + 3] >> 6) | (static_cast<uint32_t>(a[5 * i + 4]) << 2)) & 0x3FF;
927 }
928 }
929
930 /*************************************************
931 * Name: polyt1_pack
932 *
933 * Description: Bit-pack polynomial t1 with coefficients fitting in 10 bits.
934 * Input coefficients are assumed to be standard representatives.
935 *
936 * Arguments: - uint8_t *r: pointer to output byte array with at least
937 * POLYT1_PACKEDBYTES bytes
938 **************************************************/
939 void polyt1_pack(uint8_t* r) const {
940 for(size_t i = 0; i < DilithiumModeConstants::N / 4; ++i) {
941 r[5 * i + 0] = static_cast<uint8_t>((m_coeffs[4 * i + 0] >> 0));
942 r[5 * i + 1] = static_cast<uint8_t>((m_coeffs[4 * i + 0] >> 8) | (m_coeffs[4 * i + 1] << 2));
943 r[5 * i + 2] = static_cast<uint8_t>((m_coeffs[4 * i + 1] >> 6) | (m_coeffs[4 * i + 2] << 4));
944 r[5 * i + 3] = static_cast<uint8_t>((m_coeffs[4 * i + 2] >> 4) | (m_coeffs[4 * i + 3] << 6));
945 r[5 * i + 4] = static_cast<uint8_t>((m_coeffs[4 * i + 3] >> 2));
946 }
947 }
948
949 Polynomial() = default;
950};
951
953 public:
954 // public member is on purpose
955 std::vector<Polynomial> m_vec;
956
957 public:
958 PolynomialVector() = default;
959
961 BOTAN_ASSERT_NOMSG(m_vec.size() != other.m_vec.size());
962 for(size_t i = 0; i < m_vec.size(); ++i) {
963 this->m_vec[i] += other.m_vec[i];
964 }
965 return *this;
966 }
967
969 BOTAN_ASSERT_NOMSG(m_vec.size() == other.m_vec.size());
970 for(size_t i = 0; i < this->m_vec.size(); ++i) {
971 this->m_vec[i] -= other.m_vec[i];
972 }
973 return *this;
974 }
975
976 explicit PolynomialVector(size_t size) : m_vec(size) {}
977
978 /*************************************************
979 * Name: poly_uniform
980 *
981 * Description: Sample polynomial with uniformly random coefficients
982 * in [0,Q-1] by performing rejection sampling on the
983 * output stream of SHAKE256(seed|nonce) or AES256CTR(seed,nonce).
984 *
985 * Arguments: - const uint8_t seed[]: secure vector with seed of length SEEDBYTES
986 * - uint16_t nonce: 2-byte nonce
987 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
988 * Return Polynomial
989 **************************************************/
990 static Polynomial poly_uniform(const std::vector<uint8_t>& seed,
991 uint16_t nonce,
992 const DilithiumModeConstants& mode) {
993 Polynomial sample_poly;
994 size_t buflen = mode.poly_uniform_nblocks() * mode.stream128_blockbytes();
995
996 std::vector<uint8_t> buf(buflen + 2);
997
998 auto xof = mode.XOF_128(seed, nonce);
999 xof->output(std::span(buf).first(buflen));
1000
1001 size_t ctr = Polynomial::rej_uniform(sample_poly, 0, DilithiumModeConstants::N, buf.data(), buflen);
1002 size_t off;
1003 while(ctr < DilithiumModeConstants::N) {
1004 off = buflen % 3;
1005 for(size_t i = 0; i < off; ++i) {
1006 buf[i] = buf[buflen - off + i];
1007 }
1008
1009 xof->output(std::span(buf).subspan(off, mode.stream128_blockbytes()));
1010 buflen = mode.stream128_blockbytes() + off;
1011 ctr += Polynomial::rej_uniform(sample_poly, ctr, DilithiumModeConstants::N - ctr, buf.data(), buflen);
1012 }
1013 return sample_poly;
1014 }
1015
1017 const secure_vector<uint8_t>& seed,
1018 uint16_t nonce,
1019 const DilithiumModeConstants& mode) {
1020 for(size_t i = 0; i < v.m_vec.size(); ++i) {
1021 Polynomial::fill_poly_uniform_eta(v.m_vec[i], seed, nonce++, mode);
1022 }
1023 }
1024
1025 /*************************************************
1026 * Name: polyvec_pointwise_acc_montgomery
1027 *
1028 * Description: Pointwise multiply vectors of polynomials of length L, multiply
1029 * resulting vector by 2^{-32} and add (accumulate) polynomials
1030 * in it. Input/output vectors are in NTT domain representation.
1031 *
1032 * Arguments: - Polynomial &w: output polynomial
1033 * - const Polynomial &u: pointer to first input vector
1034 * - const Polynomial &v: pointer to second input vector
1035 **************************************************/
1037 const PolynomialVector& u,
1038 const PolynomialVector& v) {
1039 BOTAN_ASSERT_NOMSG(u.m_vec.size() == v.m_vec.size());
1040 BOTAN_ASSERT_NOMSG(!u.m_vec.empty() && !v.m_vec.empty());
1041
1042 u.m_vec[0].poly_pointwise_montgomery(w, v.m_vec[0]);
1043
1044 for(size_t i = 1; i < v.m_vec.size(); ++i) {
1045 Polynomial t;
1046 u.m_vec[i].poly_pointwise_montgomery(t, v.m_vec[i]);
1047 w += t;
1048 }
1049 }
1050
1051 /*************************************************
1052 * Name: fill_polyvecs_power2round
1053 *
1054 * Description: For all coefficients a of polynomials in vector ,
1055 * compute a0, a1 such that a mod^+ Q = a1*2^D + a0
1056 * with -2^{D-1} < a0 <= 2^{D-1}. Assumes coefficients to be
1057 * standard representatives.
1058 *
1059 * Arguments: - PolynomialVector& v1: reference to output vector of polynomials with
1060 * coefficients a1
1061 * - PolynomialVector& v0: reference to output vector of polynomials with
1062 * coefficients a0
1063 * - const PolynomialVector& v: reference to input vector
1064 **************************************************/
1066 BOTAN_ASSERT((v1.m_vec.size() == v0.m_vec.size()) && (v1.m_vec.size() == v.m_vec.size()),
1067 "possible buffer overflow! Wrong PolynomialVector sizes.");
1068 for(size_t i = 0; i < v1.m_vec.size(); ++i) {
1070 }
1071 }
1072
1073 static bool unpack_sig(std::array<uint8_t, DilithiumModeConstants::SEEDBYTES>& c,
1076 const std::vector<uint8_t>& sig,
1077 const DilithiumModeConstants& mode) {
1078 //const auto& mode = m_pub_key.m_public->mode();
1079 BOTAN_ASSERT(sig.size() == mode.crypto_bytes(), "invalid signature size");
1080 size_t position = 0;
1081
1082 std::copy(sig.begin(), sig.begin() + c.size(), c.begin());
1083
1085
1086 for(size_t i = 0; i < mode.l(); ++i) {
1087 Polynomial::polyz_unpack(z.m_vec[i], sig.data() + position + i * mode.polyz_packedbytes(), mode);
1088 }
1089 position += mode.l() * mode.polyz_packedbytes();
1090
1091 /* Decode h */
1092 size_t k = 0;
1093 for(size_t i = 0; i < mode.k(); ++i) {
1094 for(size_t j = 0; j < DilithiumModeConstants::N; ++j) {
1095 h.m_vec[i].m_coeffs[j] = 0;
1096 }
1097
1098 if(sig[position + mode.omega() + i] < k || sig[position + mode.omega() + i] > mode.omega()) {
1099 return true;
1100 }
1101
1102 for(size_t j = k; j < sig[position + mode.omega() + i]; ++j) {
1103 /* Coefficients are ordered for strong unforgeability */
1104 if(j > k && sig[position + j] <= sig[position + j - 1]) {
1105 return true;
1106 }
1107 h.m_vec[i].m_coeffs[sig[position + j]] = 1;
1108 }
1109
1110 k = sig[position + mode.omega() + i];
1111 }
1112
1113 /* Extra indices are zero for strong unforgeability */
1114 for(size_t j = k; j < mode.omega(); ++j) {
1115 if(sig[position + j]) {
1116 return true;
1117 }
1118 }
1119
1120 return false;
1121 }
1122
1123 /*************************************************
1124 * Name: generate_hint_polyvec
1125 *
1126 * Description: Compute hint vector.
1127 *
1128 * Arguments: - PolynomialVector *h: reference to output vector
1129 * - const PolynomialVector *v0: reference to low part of input vector
1130 * - const PolynomialVector *v1: reference to high part of input vector
1131 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
1132 *
1133 * Returns number of 1 bits.
1134 **************************************************/
1136 const PolynomialVector& v0,
1137 const PolynomialVector& v1,
1138 const DilithiumModeConstants& mode) {
1139 size_t s = 0;
1140
1141 for(size_t i = 0; i < h.m_vec.size(); ++i) {
1142 s += Polynomial::generate_hint_polynomial(h.m_vec[i], v0.m_vec[i], v1.m_vec[i], mode);
1143 }
1144
1145 return s;
1146 }
1147
1148 /*************************************************
1149 * Name: ntt
1150 *
1151 * Description: Forward NTT of all polynomials in vector. Output
1152 * coefficients can be up to 16*Q larger than input coefficients.
1153 **************************************************/
1154 void ntt() {
1155 for(auto& i : m_vec) {
1156 i.ntt();
1157 }
1158 }
1159
1160 /*************************************************
1161 * Name: polyveck_decompose
1162 *
1163 * Description: For all coefficients a of polynomials in vector,
1164 * compute high and low bits a0, a1 such a mod^+ Q = a1*ALPHA + a0
1165 * with -ALPHA/2 < a0 <= ALPHA/2 except a1 = (Q-1)/ALPHA where we
1166 * set a1 = 0 and -ALPHA/2 <= a0 = a mod Q - Q < 0.
1167 * Assumes coefficients to be standard representatives.
1168 *
1169 * Arguments: - PolynomialVector& v1: reference to output vector of polynomials with
1170 * coefficients a1
1171 * - PolynomialVector& v0: reference to output vector of polynomials with
1172 * coefficients a0
1173 * - const PolynomialVector& v: reference to input vector
1174 **************************************************/
1175 std::tuple<PolynomialVector, PolynomialVector> polyvec_decompose(const DilithiumModeConstants& mode) {
1176 PolynomialVector v1(mode.k());
1177 PolynomialVector v0(mode.k());
1178
1179 for(size_t i = 0; i < m_vec.size(); ++i) {
1180 m_vec[i].poly_decompose(v1.m_vec[i], v0.m_vec[i], mode);
1181 }
1182 return std::make_tuple(v1, v0);
1183 }
1184
1185 /*************************************************
1186 * Name: reduce
1187 *
1188 * Description: Reduce coefficients of polynomials in vector
1189 * to representatives in [-6283009,6283007].
1190 **************************************************/
1191 void reduce() {
1192 for(auto& i : m_vec) {
1193 i.poly_reduce();
1194 }
1195 }
1196
1197 /*************************************************
1198 * Name: invntt_tomont
1199 *
1200 * Description: Inverse NTT and multiplication by 2^{32} of polynomials
1201 * in vector. Input coefficients need to be less
1202 * than 2*Q.
1203 **************************************************/
1205 for(auto& i : m_vec) {
1206 i.poly_invntt_tomont();
1207 }
1208 }
1209
1210 /*************************************************
1212 *
1213 * Description: Add vectors of polynomials .
1214 * No modular reduction is performed.
1215 *
1216 * Arguments: - const PolynomialVector *v: pointer to second summand
1217 * - const PolynomialVector *u: pointer to first summand
1218 **************************************************/
1220 BOTAN_ASSERT((m_vec.size() == v.m_vec.size()), "possible buffer overflow! Wrong PolynomialVector sizes.");
1221 for(size_t i = 0; i < m_vec.size(); ++i) {
1222 m_vec[i] += v.m_vec[i];
1223 }
1224 }
1225
1226 /*************************************************
1228 *
1229 * Description: For all coefficients of polynomials in vector
1230 * add Q if coefficient is negative.
1231 **************************************************/
1233 for(auto& i : m_vec) {
1235 }
1236 }
1237
1239 uint16_t nonce,
1240 const DilithiumModeConstants& mode) {
1241 BOTAN_ASSERT_NOMSG(m_vec.size() <= std::numeric_limits<uint16_t>::max());
1242 for(uint16_t i = 0; i < static_cast<uint16_t>(this->m_vec.size()); ++i) {
1243 m_vec[i].poly_uniform_gamma1(seed, mode.l() * nonce + i, mode);
1244 }
1245 }
1246
1248 for(size_t i = 0; i < m_vec.size(); ++i) {
1249 m_vec[i].poly_pointwise_montgomery(r.m_vec[i], a);
1250 }
1251 }
1252
1253 /*************************************************
1254 * Name: polyvecl_chknorm
1255 *
1256 * Description: Check infinity norm of polynomials in vector of length L.
1257 * Assumes input polyvecl to be reduced by polyvecl_reduce().
1258 *
1259 * Arguments: - size_t B: norm bound
1260 *
1261 * Returns false if norm of all polynomials is strictly smaller than B <= (Q-1)/8
1262 * and true otherwise.
1263 **************************************************/
1264 bool polyvec_chknorm(size_t bound) {
1265 for(auto& i : m_vec) {
1266 if(Polynomial::poly_chknorm(i, bound)) {
1267 return true;
1268 }
1269 }
1270 return false;
1271 }
1272
1273 /*************************************************
1274 * Name: polyvec_shiftl
1275 *
1276 * Description: Multiply vector of polynomials by 2^D without modular
1277 * reduction. Assumes input coefficients to be less than 2^{31-D}.
1278 **************************************************/
1280 for(auto& i : m_vec) {
1281 i.poly_shiftl();
1282 }
1283 }
1284
1285 /*************************************************
1286 * Name: polyvec_use_hint
1287 *
1288 * Description: Use hint vector to correct the high bits of input vector.
1289 *
1290 * Arguments: - PolynomialVector& w: reference to output vector of polynomials with
1291 * corrected high bits
1292 * - const PolynomialVector& u: reference to input vector
1293 * - const PolynomialVector& h: reference to input hint vector
1294 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
1295 **************************************************/
1297 for(size_t i = 0; i < w.m_vec.size(); ++i) {
1298 Polynomial::poly_use_hint(w.m_vec[i], m_vec[i], h.m_vec[i], mode);
1299 }
1300 }
1301
1303 secure_vector<uint8_t> packed_eta(mode.polyeta_packedbytes() * m_vec.size());
1304 for(size_t i = 0; i < m_vec.size(); ++i) {
1305 m_vec[i].polyeta_pack(packed_eta.data() + mode.polyeta_packedbytes() * i, mode);
1306 }
1307 return packed_eta;
1308 }
1309
1310 static PolynomialVector unpack_eta(std::span<const uint8_t> buffer,
1311 size_t size,
1312 const DilithiumModeConstants& mode) {
1313 BOTAN_ARG_CHECK(buffer.size() == mode.polyeta_packedbytes() * size, "Invalid buffer size");
1314
1315 PolynomialVector pv(size);
1316 for(size_t i = 0; i < pv.m_vec.size(); ++i) {
1318 buffer.subspan(i * mode.polyeta_packedbytes(), mode.polyeta_packedbytes()), mode);
1319 }
1320 return pv;
1321 }
1322
1325 for(size_t i = 0; i < m_vec.size(); ++i) {
1326 m_vec[i].polyt0_pack(packed_t0.data() + i * DilithiumModeConstants::POLYT0_PACKEDBYTES);
1327 }
1328 return packed_t0;
1329 }
1330
1331 static PolynomialVector unpack_t0(std::span<const uint8_t> buffer, const DilithiumModeConstants& mode) {
1332 BOTAN_ARG_CHECK(static_cast<int32_t>(buffer.size()) == DilithiumModeConstants::POLYT0_PACKEDBYTES * mode.k(),
1333 "Invalid buffer size");
1334
1335 PolynomialVector t0(mode.k());
1336 for(size_t i = 0; i < t0.m_vec.size(); ++i) {
1339 }
1340 return t0;
1341 }
1342
1343 std::vector<uint8_t> polyvec_pack_t1() const {
1344 std::vector<uint8_t> packed_t1(m_vec.size() * DilithiumModeConstants::POLYT1_PACKEDBYTES);
1345 for(size_t i = 0; i < m_vec.size(); ++i) {
1346 m_vec[i].polyt1_pack(packed_t1.data() + i * DilithiumModeConstants::POLYT1_PACKEDBYTES);
1347 }
1348 return packed_t1;
1349 }
1350
1351 static PolynomialVector unpack_t1(std::span<const uint8_t> packed_t1, const DilithiumModeConstants& mode) {
1353 static_cast<int32_t>(packed_t1.size()) == DilithiumModeConstants::POLYT1_PACKEDBYTES * mode.k(),
1354 "Invalid buffer size");
1355
1356 PolynomialVector t1(mode.k());
1357 for(size_t i = 0; i < t1.m_vec.size(); ++i) {
1359 }
1360 return t1;
1361 }
1362
1363 std::vector<uint8_t> polyvec_pack_w1(const DilithiumModeConstants& mode) {
1364 std::vector<uint8_t> packed_w1(mode.polyw1_packedbytes() * m_vec.size());
1365 for(size_t i = 0; i < m_vec.size(); ++i) {
1366 m_vec[i].polyw1_pack(packed_w1.data() + i * mode.polyw1_packedbytes(), mode);
1367 }
1368 return packed_w1;
1369 }
1370
1371 static PolynomialVector polyvec_unpack_z(const uint8_t* packed_z, const DilithiumModeConstants& mode) {
1372 PolynomialVector z(mode.l());
1373 for(size_t i = 0; i < z.m_vec.size(); ++i) {
1374 Polynomial::polyz_unpack(z.m_vec[i], packed_z + i * mode.polyz_packedbytes(), mode);
1375 }
1376 return z;
1377 }
1378
1379 /*************************************************
1380 * Name: generate_polyvec_matrix_pointwise_montgomery
1381 *
1382 * Description: Generates a PolynomialVector based on a matrix using pointwise montgomery acc
1383 *
1384 * Arguments: - const std::vector<uint8_t>& rho[]: byte array containing seed rho
1385 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
1386 * Returns a PolynomialVector
1387 **************************************************/
1388 static PolynomialVector generate_polyvec_matrix_pointwise_montgomery(const std::vector<PolynomialVector>& mat,
1389 const PolynomialVector& v,
1390 const DilithiumModeConstants& mode) {
1391 PolynomialVector t(mode.k());
1392 for(size_t i = 0; i < mode.k(); ++i) {
1394 }
1395 return t;
1396 }
1397};
1398
1400 private:
1401 // Matrix of length k holding a polynomialVector of size l, which has N coeffs
1402 std::vector<PolynomialVector> m_mat;
1403
1404 explicit PolynomialMatrix(const DilithiumModeConstants& mode) : m_mat(mode.k(), PolynomialVector(mode.l())) {}
1405
1406 public:
1408
1409 /*************************************************
1410 * Name: generate_matrix
1411 *
1412 * Description: Implementation of generate_matrix. Generates matrix A with uniformly
1413 * random coefficients a_{i,j} by performing rejection
1414 * sampling on the output stream of SHAKE128(rho|j|i)
1415 * or AES256CTR(rho,j|i).
1416 *
1417 * Arguments: - const std::vector<uint8_t>& rho[]: byte array containing seed rho
1418 * - const DilithiumModeConstants& mode: reference to dilihtium mode values
1419 * Returns the output matrix mat[k]
1420 **************************************************/
1421 static PolynomialMatrix generate_matrix(const std::vector<uint8_t>& rho, const DilithiumModeConstants& mode) {
1422 BOTAN_ASSERT(rho.size() >= DilithiumModeConstants::SEEDBYTES, "wrong byte length for rho/seed");
1423
1424 PolynomialMatrix matrix(mode);
1425 for(uint16_t i = 0; i < mode.k(); ++i) {
1426 for(uint16_t j = 0; j < mode.l(); ++j) {
1427 matrix.m_mat[i].m_vec[j] = PolynomialVector::poly_uniform(rho, (i << 8) + j, mode);
1428 }
1429 }
1430 return matrix;
1431 }
1432
1433 const std::vector<PolynomialVector>& get_matrix() const { return m_mat; }
1434};
1435} // namespace Botan::Dilithium
1436
1437#endif
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
Definition assert.h:50
void update(const uint8_t in[], size_t length)
Definition buf_comp.h:35
void final(uint8_t out[])
Definition buf_comp.h:70
std::unique_ptr< Botan::XOF > XOF_128(std::span< const uint8_t > seed, uint16_t nonce) const
std::unique_ptr< Botan::XOF > XOF_256(std::span< const uint8_t > seed, uint16_t nonce) const
secure_vector< uint8_t > ExpandMask(const secure_vector< uint8_t > &seed, uint16_t nonce) const
static constexpr int32_t ZETAS[DilithiumModeConstants::N]
const std::vector< PolynomialVector > & get_matrix() const
static PolynomialMatrix generate_matrix(const std::vector< uint8_t > &rho, const DilithiumModeConstants &mode)
static PolynomialVector polyvec_unpack_z(const uint8_t *packed_z, const DilithiumModeConstants &mode)
static PolynomialVector unpack_t1(std::span< const uint8_t > packed_t1, const DilithiumModeConstants &mode)
static bool unpack_sig(std::array< uint8_t, DilithiumModeConstants::SEEDBYTES > &c, PolynomialVector &z, PolynomialVector &h, const std::vector< uint8_t > &sig, const DilithiumModeConstants &mode)
secure_vector< uint8_t > polyvec_pack_t0() const
secure_vector< uint8_t > polyvec_pack_eta(const DilithiumModeConstants &mode) const
static PolynomialVector unpack_t0(std::span< const uint8_t > buffer, const DilithiumModeConstants &mode)
static void polyvec_pointwise_acc_montgomery(Polynomial &w, const PolynomialVector &u, const PolynomialVector &v)
void polyvec_use_hint(PolynomialVector &w, const PolynomialVector &h, const DilithiumModeConstants &mode)
PolynomialVector & operator+=(const PolynomialVector &other)
void polyvecl_uniform_gamma1(const secure_vector< uint8_t > &seed, uint16_t nonce, const DilithiumModeConstants &mode)
static void fill_polyvec_uniform_eta(PolynomialVector &v, const secure_vector< uint8_t > &seed, uint16_t nonce, const DilithiumModeConstants &mode)
static void fill_polyvecs_power2round(PolynomialVector &v1, PolynomialVector &v0, const PolynomialVector &v)
static PolynomialVector generate_polyvec_matrix_pointwise_montgomery(const std::vector< PolynomialVector > &mat, const PolynomialVector &v, const DilithiumModeConstants &mode)
static Polynomial poly_uniform(const std::vector< uint8_t > &seed, uint16_t nonce, const DilithiumModeConstants &mode)
std::vector< uint8_t > polyvec_pack_t1() const
std::vector< uint8_t > polyvec_pack_w1(const DilithiumModeConstants &mode)
static PolynomialVector unpack_eta(std::span< const uint8_t > buffer, size_t size, const DilithiumModeConstants &mode)
std::tuple< PolynomialVector, PolynomialVector > polyvec_decompose(const DilithiumModeConstants &mode)
PolynomialVector & operator-=(const PolynomialVector &other)
void polyvec_pointwise_poly_montgomery(PolynomialVector &r, const Polynomial &a)
static size_t generate_hint_polyvec(PolynomialVector &h, const PolynomialVector &v0, const PolynomialVector &v1, const DilithiumModeConstants &mode)
static size_t rej_eta(Polynomial &a, size_t offset, size_t len, const secure_vector< uint8_t > &buf, size_t buflen, const DilithiumModeConstants &mode)
static int32_t power2round(int32_t &a0, int32_t a)
static void polyz_unpack(Polynomial &r, const uint8_t *a, const DilithiumModeConstants &mode)
static void fill_polys_power2round(Polynomial &a1, Polynomial &a0, const Polynomial &a)
static Polynomial polyt0_unpack(std::span< const uint8_t > a)
void polyeta_pack(uint8_t *r, const DilithiumModeConstants &mode) const
void poly_decompose(Polynomial &a1, Polynomial &a0, const DilithiumModeConstants &mode) const
static Polynomial poly_challenge(const uint8_t *seed, const DilithiumModeConstants &mode)
static void polyt1_unpack(Polynomial &r, const uint8_t *a)
static int32_t use_hint(int32_t a, size_t hint, const DilithiumModeConstants &mode)
void poly_uniform_gamma1(const secure_vector< uint8_t > &seed, uint16_t nonce, const DilithiumModeConstants &mode)
void poly_pointwise_montgomery(Polynomial &output, const Polynomial &second) const
Polynomial & operator+=(const Polynomial &other)
static Polynomial polyeta_unpack(std::span< const uint8_t > a, const DilithiumModeConstants &mode)
static void fill_poly_uniform_eta(Polynomial &a, const secure_vector< uint8_t > &seed, uint16_t nonce, const DilithiumModeConstants &mode)
static int32_t make_hint(size_t a0, size_t a1, const DilithiumModeConstants &mode)
void polyz_pack(uint8_t *r, const DilithiumModeConstants &mode) const
int32_t montgomery_reduce(int64_t a) const
std::array< int32_t, Botan::DilithiumModeConstants::N > m_coeffs
void polyw1_pack(uint8_t *r, const DilithiumModeConstants &mode)
static int32_t decompose(int32_t *a0, int32_t a, const DilithiumModeConstants &mode)
static bool poly_chknorm(const Polynomial &a, size_t B)
static size_t generate_hint_polynomial(Polynomial &h, const Polynomial &a0, const Polynomial &a1, const DilithiumModeConstants &mode)
Polynomial & operator-=(const Polynomial &other)
static size_t rej_uniform(Polynomial &p, size_t position, size_t len, const uint8_t *buf, size_t buflen)
static void poly_use_hint(Polynomial &b, const Polynomial &a, const Polynomial &h, const DilithiumModeConstants &mode)
constexpr T rho(T x)
Definition rotate.h:51
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61