Botan 3.9.0
Crypto and TLS for C&
Botan::CRYSTALS Namespace Reference

Namespaces

namespace  detail

Classes

struct  BitPackingTrait
class  Polynomial
class  PolynomialMatrix
class  PolynomialVector
class  Trait_Base

Concepts

concept  crystals_constants
concept  crystals_trait
concept  byte_source
concept  coeff_map_fn
concept  coeff_unmap_fn

Enumerations

enum class  Domain : uint8_t { Normal , NTT }

Functions

template<crystals_trait Trait>
Polynomial< Trait, Domain::Normalinverse_ntt (Polynomial< Trait, Domain::NTT > p_ntt)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::Normalinverse_ntt (PolynomialVector< Trait, Domain::NTT > polyvec_ntt)
template<crystals_trait Trait, Domain D>
Polynomial< Trait, D > montgomery (Polynomial< Trait, D > p)
template<crystals_trait Trait, Domain D>
PolynomialVector< Trait, D > montgomery (PolynomialVector< Trait, D > polyvec)
template<crystals_trait Trait>
Polynomial< Trait, Domain::NTTntt (Polynomial< Trait, Domain::Normal > p)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::NTTntt (PolynomialVector< Trait, Domain::Normal > polyvec)
template<crystals_trait Trait>
Polynomial< Trait, Domain::NTToperator* (const Polynomial< Trait, Domain::NTT > &a, const Polynomial< Trait, Domain::NTT > &b)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::NTToperator* (const Polynomial< Trait, Domain::NTT > &p, const PolynomialVector< Trait, Domain::NTT > &pv)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::NTToperator* (const PolynomialMatrix< Trait > &mat, const PolynomialVector< Trait, Domain::NTT > &vec)
template<crystals_trait Trait>
Polynomial< Trait, Domain::NTToperator* (const PolynomialVector< Trait, Domain::NTT > &a, const PolynomialVector< Trait, Domain::NTT > &b)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::Normaloperator+ (const PolynomialVector< Trait, Domain::Normal > &a, const PolynomialVector< Trait, Domain::Normal > &b)
template<crystals_trait Trait>
PolynomialVector< Trait, Domain::Normaloperator<< (const PolynomialVector< Trait, Domain::Normal > &pv, size_t shift)
template<int32_t range, crystals_trait PolyTrait, Domain D>
constexpr void pack (const Polynomial< PolyTrait, D > &p, BufferStuffer &stuffer)
 Overload for packing polynomials with a NOOP map function.
template<int32_t range, crystals_trait PolyTrait, Domain D, coeff_map_fn< typename PolyTrait::T > MapFnT>
constexpr void pack (const Polynomial< PolyTrait, D > &p, BufferStuffer &stuffer, MapFnT map)
template<int32_t range, byte_source ByteSourceT, crystals_trait PolyTrait, Domain D>
constexpr void unpack (Polynomial< PolyTrait, D > &p, ByteSourceT &byte_source)
 Overload for unpacking polynomials with a NOOP unmap function.
template<int32_t range, byte_source ByteSourceT, crystals_trait PolyTrait, Domain D, coeff_unmap_fn< typename PolyTrait::T > UnmapFnT>
constexpr void unpack (Polynomial< PolyTrait, D > &p, ByteSourceT &byte_source, UnmapFnT unmap)

Enumeration Type Documentation

◆ Domain

enum class Botan::CRYSTALS::Domain : uint8_t
strong
Enumerator
Normal 
NTT 

Definition at line 28 of file pqcrystals.h.

Function Documentation

◆ inverse_ntt() [1/2]

template<crystals_trait Trait>
Polynomial< Trait, Domain::Normal > Botan::CRYSTALS::inverse_ntt ( Polynomial< Trait, Domain::NTT > p_ntt)

Definition at line 567 of file pqcrystals.h.

567 {
568 auto p = detail::domain_cast<Domain::Normal>(std::move(p_ntt));
569 Trait::inverse_ntt(p.coefficients());
570 return p;
571}
StructureT< Trait, To > domain_cast(StructureT< Trait, From > &&p)
Definition pqcrystals.h:163

References Botan::CRYSTALS::detail::domain_cast().

◆ inverse_ntt() [2/2]

template<crystals_trait Trait>
PolynomialVector< Trait, Domain::Normal > Botan::CRYSTALS::inverse_ntt ( PolynomialVector< Trait, Domain::NTT > polyvec_ntt)

Definition at line 583 of file pqcrystals.h.

583 {
584 auto polyvec = detail::domain_cast<Domain::Normal>(std::move(polyvec_ntt));
585 for(auto& poly : polyvec) {
586 Trait::inverse_ntt(poly.coefficients());
587 }
588 return polyvec;
589}

References Botan::CRYSTALS::detail::domain_cast().

◆ montgomery() [1/2]

template<crystals_trait Trait, Domain D>
Polynomial< Trait, D > Botan::CRYSTALS::montgomery ( Polynomial< Trait, D > p)

Definition at line 592 of file pqcrystals.h.

592 {
594 return p;
595}
void montgomery(Polynomial< Trait, D > &p)
Definition pqcrystals.h:540

References Botan::CRYSTALS::detail::montgomery().

◆ montgomery() [2/2]

template<crystals_trait Trait, Domain D>
PolynomialVector< Trait, D > Botan::CRYSTALS::montgomery ( PolynomialVector< Trait, D > polyvec)

Definition at line 598 of file pqcrystals.h.

598 {
599 for(auto& p : polyvec) {
601 }
602 return polyvec;
603}

References Botan::CRYSTALS::detail::montgomery().

◆ ntt() [1/2]

template<crystals_trait Trait>
Polynomial< Trait, Domain::NTT > Botan::CRYSTALS::ntt ( Polynomial< Trait, Domain::Normal > p)

Definition at line 560 of file pqcrystals.h.

560 {
561 auto p_ntt = detail::domain_cast<Domain::NTT>(std::move(p));
562 Trait::ntt(p_ntt.coefficients());
563 return p_ntt;
564}

References Botan::CRYSTALS::detail::domain_cast().

◆ ntt() [2/2]

template<crystals_trait Trait>
PolynomialVector< Trait, Domain::NTT > Botan::CRYSTALS::ntt ( PolynomialVector< Trait, Domain::Normal > polyvec)

Definition at line 574 of file pqcrystals.h.

574 {
575 auto polyvec_ntt = detail::domain_cast<Domain::NTT>(std::move(polyvec));
576 for(auto& poly : polyvec_ntt) {
577 Trait::ntt(poly.coefficients());
578 }
579 return polyvec_ntt;
580}

References Botan::CRYSTALS::detail::domain_cast().

◆ operator*() [1/4]

template<crystals_trait Trait>
Polynomial< Trait, Domain::NTT > Botan::CRYSTALS::operator* ( const Polynomial< Trait, Domain::NTT > & a,
const Polynomial< Trait, Domain::NTT > & b )

Definition at line 645 of file pqcrystals.h.

646 {
648 Trait::poly_pointwise_montgomery(result.coefficients(), a.coefficients(), b.coefficients());
649 return result;
650}
std::span< T, Trait::N > coefficients()
Definition pqcrystals.h:302

References Botan::CRYSTALS::Polynomial< Trait, D >::coefficients().

◆ operator*() [2/4]

template<crystals_trait Trait>
PolynomialVector< Trait, Domain::NTT > Botan::CRYSTALS::operator* ( const Polynomial< Trait, Domain::NTT > & p,
const PolynomialVector< Trait, Domain::NTT > & pv )

Definition at line 635 of file pqcrystals.h.

636 {
638 for(size_t i = 0; i < pv.size(); ++i) {
639 Trait::poly_pointwise_montgomery(result[i].coefficients(), p.coefficients(), pv[i].coefficients());
640 }
641 return result;
642}

References Botan::CRYSTALS::Polynomial< Trait, D >::coefficients(), Botan::CRYSTALS::PolynomialVector< Trait, D >::coefficients(), and Botan::CRYSTALS::PolynomialVector< Trait, D >::size().

◆ operator*() [3/4]

template<crystals_trait Trait>
PolynomialVector< Trait, Domain::NTT > Botan::CRYSTALS::operator* ( const PolynomialMatrix< Trait > & mat,
const PolynomialVector< Trait, Domain::NTT > & vec )

Definition at line 617 of file pqcrystals.h.

618 {
620 for(size_t i = 0; i < mat.size(); ++i) {
621 Trait::polyvec_pointwise_acc_montgomery(result[i].coefficients(), mat[i].coefficients(), vec.coefficients());
622 }
623 return result;
624}

References Botan::CRYSTALS::PolynomialVector< Trait, D >::coefficients(), and Botan::CRYSTALS::PolynomialMatrix< Trait >::size().

◆ operator*() [4/4]

template<crystals_trait Trait>
Polynomial< Trait, Domain::NTT > Botan::CRYSTALS::operator* ( const PolynomialVector< Trait, Domain::NTT > & a,
const PolynomialVector< Trait, Domain::NTT > & b )

Definition at line 627 of file pqcrystals.h.

628 {
630 detail::dot_product(result, a, b);
631 return result;
632}
void dot_product(Polynomial< Trait, Domain::NTT > &out, const PolynomialVector< Trait, Domain::NTT > &a, const PolynomialVector< Trait, Domain::NTT > &b)
Definition pqcrystals.h:547

References Botan::CRYSTALS::detail::dot_product().

◆ operator+()

template<crystals_trait Trait>
PolynomialVector< Trait, Domain::Normal > Botan::CRYSTALS::operator+ ( const PolynomialVector< Trait, Domain::Normal > & a,
const PolynomialVector< Trait, Domain::Normal > & b )

Definition at line 606 of file pqcrystals.h.

607 {
608 BOTAN_DEBUG_ASSERT(a.size() == b.size());
610 for(size_t i = 0; i < a.size(); ++i) {
611 Trait::poly_add(result[i].coefficients(), a[i].coefficients(), b[i].coefficients());
612 }
613 return result;
614}
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:129

References BOTAN_DEBUG_ASSERT, and Botan::CRYSTALS::PolynomialVector< Trait, D >::size().

◆ operator<<()

template<crystals_trait Trait>
PolynomialVector< Trait, Domain::Normal > Botan::CRYSTALS::operator<< ( const PolynomialVector< Trait, Domain::Normal > & pv,
size_t shift )

Definition at line 645 of file pqcrystals.h.

653 {
654 BOTAN_ASSERT_NOMSG(shift < sizeof(typename Trait::T) * 8);
656 for(size_t i = 0; i < pv.size(); ++i) {
657 for(size_t j = 0; j < Trait::N; ++j) {
658 result[i][j] = pv[i][j] << shift;
659 }
660 }
661 return result;
662}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75

◆ pack() [1/2]

template<int32_t range, crystals_trait PolyTrait, Domain D>
void Botan::CRYSTALS::pack ( const Polynomial< PolyTrait, D > & p,
BufferStuffer & stuffer )
constexpr

Overload for packing polynomials with a NOOP map function.

Definition at line 222 of file pqcrystals_encoding.h.

222 {
223 using unsigned_T = std::make_unsigned_t<typename PolyTrait::T>;
224 pack<range>(p, stuffer, [](typename PolyTrait::T x) { return static_cast<unsigned_T>(x); });
225}
constexpr void pack(const Polynomial< PolyTrait, D > &p, BufferStuffer &stuffer, MapFnT map)

References pack().

◆ pack() [2/2]

template<int32_t range, crystals_trait PolyTrait, Domain D, coeff_map_fn< typename PolyTrait::T > MapFnT>
void Botan::CRYSTALS::pack ( const Polynomial< PolyTrait, D > & p,
BufferStuffer & stuffer,
MapFnT map )
constexpr

Base implementation of NIST FIPS 203 Algorithm 5 (ByteEncode) and NIST FIPS 204 Algorithms 16 (SimpleBitPack) and 17 (BitPack).

This takes a polynomial p and packs its coefficients into the buffer represented by stuffer. Optionally, the coefficients can be transformed using the map function before packing them. Kyber uses map to compress the coefficients as needed, Dilithium to transform coefficients to unsigned.

The implementation assumes that the values returned from the custom map transformation are in the range [0, range]. No assumption is made about the value range of the coefficients in the polynomial p.

Note that this bit-packing algorithm is inefficient if the bit-length of the coefficients is a multiple of 8. In that case, a byte-level encoding (that might need to take endianess into account) would be more efficient. However, neither Kyber nor Dilithium instantiate bit-packings with such a value range.

Template Parameters
rangethe upper bound of the coefficient range.

Definition at line 116 of file pqcrystals_encoding.h.

116 {
118
119 BOTAN_DEBUG_ASSERT(stuffer.remaining_capacity() >= p.size() * trait::bits_per_coeff / 8);
120
121 // Bit-packing example that shows a coefficients' bit-pack that spills across
122 // more than one 64-bit collectors. This illustrates the algorithm below.
123 //
124 // 0 64 128
125 // Collectors (64 bits): | collectors[0] | collectors[1] |
126 // | | |
127 // Coefficients (11 bits): | c[0] | c[1] | c[2] | c[3] | c[4] | c[5] | c[6] | c[7] | | | | | ...
128 // | | |
129 // | < byte-aligned coefficient pack > | < byte-aligned pad. > |
130 // | (one inner loop iteration) |
131 // 0 88 (divisible by 8)
132
133 for(size_t i = 0; i < p.size(); i += trait::coeffs_per_pack) {
134 // The collectors array is filled with bit-packed coefficients to produce
135 // a byte-aligned pack of coefficients. When coefficients fall onto the
136 // boundary of two collectors, their bits must be split.
137 typename trait::collector_array collectors = {0};
138 for(size_t j = 0, bit_offset = 0, c = 0; j < trait::coeffs_per_pack; ++j) {
139 // Transform p[i] via a custom map function (that may be a NOOP).
140 const typename trait::unsigned_T mapped_coeff = map(p[i + j]);
141 const auto coeff_value = static_cast<typename trait::sink_t>(mapped_coeff);
142
143 // pack() is called only on data produced by us. If the values returned
144 // by the map function are not in the range [0, range] we have a bug.
145 BOTAN_DEBUG_ASSERT(coeff_value <= range);
146
147 // Bit-pack the coefficient into the collectors array and keep track of
148 // the bit-offset within the current collector. Note that this might
149 // shift some high-bits of the coefficient out of the current collector.
150 collectors[c] |= coeff_value << bit_offset;
151 bit_offset += trait::bits_per_coeff;
152
153 // If the bit-offset now exceeds the collector's bit-width, we fill the
154 // next collector with the high-bits that didn't fit into the previous.
155 // The bit-offset is adjusted to now point into the new collector.
156 if(bit_offset > trait::bits_in_collector) {
157 bit_offset = bit_offset - trait::bits_in_collector;
158 collectors[++c] = coeff_value >> (trait::bits_per_coeff - bit_offset);
159 }
160 }
161
162 // One byte-aligned pack of bit-packed coefficients is now stored in the
163 // collectors and can be written to an output buffer. Note that we might
164 // have to remove some padding bytes of unused collector space.
165 const auto bytes = store_le(collectors);
166 stuffer.append(std::span{bytes}.template first<trait::bytes_per_pack>());
167 }
168}
constexpr void append(std::span< const uint8_t > buffer)
Definition stl_util.h:169
constexpr size_t remaining_capacity() const
Definition stl_util.h:181
constexpr size_t size() const
Definition pqcrystals.h:276
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736

References Botan::BufferStuffer::append(), BOTAN_DEBUG_ASSERT, Botan::BufferStuffer::remaining_capacity(), Botan::CRYSTALS::Polynomial< Trait, D >::size(), and Botan::store_le().

Referenced by pack().

◆ unpack() [1/2]

template<int32_t range, byte_source ByteSourceT, crystals_trait PolyTrait, Domain D>
void Botan::CRYSTALS::unpack ( Polynomial< PolyTrait, D > & p,
ByteSourceT & byte_source )
constexpr

Overload for unpacking polynomials with a NOOP unmap function.

Definition at line 229 of file pqcrystals_encoding.h.

229 {
230 using unsigned_T = std::make_unsigned_t<typename PolyTrait::T>;
231 unpack<range>(p, byte_source, [](unsigned_T x) { return static_cast<typename PolyTrait::T>(x); });
232}
constexpr void unpack(Polynomial< PolyTrait, D > &p, ByteSourceT &byte_source, UnmapFnT unmap)

References unpack().

◆ unpack() [2/2]

template<int32_t range, byte_source ByteSourceT, crystals_trait PolyTrait, Domain D, coeff_unmap_fn< typename PolyTrait::T > UnmapFnT>
void Botan::CRYSTALS::unpack ( Polynomial< PolyTrait, D > & p,
ByteSourceT & byte_source,
UnmapFnT unmap )
constexpr

Base implementation of NIST FIPS 203 Algorithm 6 (ByteDecode) and NIST FIPS 204 Algorithms 18 (SimpleBitUnpack) and 19 (BitUnpack).

This takes a byte sequence represented by byte_source and unpacks its coefficients into the polynomial p. Optionally, the coefficients can be transformed using the unmap function after unpacking them. Note that the unmap function must be able to deal with out-of-range values, as the input to unpack() may be untrusted data.

Kyber uses unmap to decompress the coefficients as needed, Dilithium uses it to convert the coefficients back to signed integers.

Template Parameters
rangethe upper bound of the coefficient range.

Definition at line 190 of file pqcrystals_encoding.h.

190 {
192
193 auto get_bytes = detail::as_byte_source(byte_source);
194 typename trait::collector_bytearray bytes = {0};
195
196 // This is the inverse operation of the bit-packing algorithm above. Please
197 // refer to the comments there for a detailed explanation of the algorithm.
198 for(size_t i = 0; i < p.size(); i += trait::coeffs_per_pack) {
199 get_bytes(std::span{bytes}.template first<trait::bytes_per_pack>());
200 const auto collectors = load_le<typename trait::collector_array>(bytes);
201
202 for(size_t j = 0, bit_offset = 0, c = 0; j < trait::coeffs_per_pack; ++j) {
203 typename trait::sink_t coeff_value = collectors[c] >> bit_offset;
204 bit_offset += trait::bits_per_coeff;
205 if(bit_offset > trait::bits_in_collector) {
206 bit_offset = bit_offset - trait::bits_in_collector;
207 coeff_value |= collectors[++c] << (trait::bits_per_coeff - bit_offset);
208 }
209
210 // unpack() may be called on data produced by an untrusted party.
211 // The values passed into the unmap function may be out of range, hence
212 // it is acceptable for unmap to return an out-of-range value then.
213 //
214 // For that reason we cannot use BOTAN_ASSERT[_DEBUG] on the values.
215 p[i + j] = unmap(static_cast<typename trait::unsigned_T>(coeff_value & trait::value_mask));
216 }
217 }
218}
constexpr auto as_byte_source(BufferSlicer &slicer)
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495

References Botan::CRYSTALS::detail::as_byte_source(), Botan::load_le(), and Botan::CRYSTALS::Polynomial< Trait, D >::size().

Referenced by unpack().