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