/src/botan/build/include/internal/botan/internal/pqcrystals_helpers.h

Source (jump to first uncovered line)
/*
 * PQ CRYSTALS Common Helpers
 *
 * Further changes
 * (C) 2024 Jack Lloyd
 * (C) 2024 René Meusel, Fabian Albert, Rohde & Schwarz Cybersecurity
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */

#ifndef BOTAN_PQ_CRYSTALS_HELPERS_H_
#define BOTAN_PQ_CRYSTALS_HELPERS_H_

#include <concepts>
#include <cstdint>
#include <span>
#include <tuple>

#include <botan/exceptn.h>
#include <botan/internal/bit_ops.h>

namespace Botan {

// clang-format off

template <std::unsigned_integral T>
   requires(sizeof(T) <= 4)
using next_longer_uint_t =
   std::conditional_t<sizeof(T) == 1, uint16_t,
   std::conditional_t<sizeof(T) == 2, uint32_t,
   std::conditional_t<sizeof(T) == 4, uint64_t, void>>>;

template <std::signed_integral T>
   requires(sizeof(T) <= 4)
using next_longer_int_t =
   std::conditional_t<sizeof(T) == 1, int16_t,
   std::conditional_t<sizeof(T) == 2, int32_t,
   std::conditional_t<sizeof(T) == 4, int64_t, void>>>;

// clang-format on

template <std::integral T>
   requires(size_t(sizeof(T)) <= 4)
consteval T montgomery_R(T q) {
   using T_unsigned = std::make_unsigned_t<T>;
   using T2 = next_longer_uint_t<T_unsigned>;
   return (T2(1) << (sizeof(T) * 8)) % q;
}

template <std::integral T>
   requires(size_t(sizeof(T)) <= 4)
consteval T montgomery_R2(T q) {
   using T2 = next_longer_int_t<T>;
   return (static_cast<T2>(montgomery_R(q)) * static_cast<T2>(montgomery_R(q))) % q;
}

template <std::integral T>
struct eea_result {
      T gcd;
      T u;
      T v;
};

/**
 * Run the extended Euclidean algorithm to find the greatest common divisor of a
 * and b and the Bézout coefficients, u and v.
 */
template <std::integral T>
consteval eea_result<T> extended_euclidean_algorithm(T a, T b) {
   if(a > b) {
      std::swap(a, b);
   }

   T u1 = 0, v1 = 1, u2 = 1, v2 = 0;

   if(a != b) {
      while(a != 0) {
         const T q = b / a;
         std::tie(a, b) = std::make_tuple(static_cast<T>(b - q * a), a);
         std::tie(u1, v1, u2, v2) = std::make_tuple(u2, v2, static_cast<T>(u1 - q * u2), static_cast<T>(v1 - q * v2));
      }
   }

   return {.gcd = b, .u = u1, .v = v1};
}

/**
 * Calculate the modular multiplacative inverse of q modulo m.
 * By default, this assumes m to be 2^bitlength of T for application in a
 * Montgomery reduction.
 */
template <std::integral T, std::integral T2 = next_longer_int_t<T>>
   requires(sizeof(T) <= 4)
consteval T modular_inverse(T q, T2 m = T2(1) << sizeof(T) * 8) {
   return static_cast<T>(extended_euclidean_algorithm<T2>(q, m).u);
}

constexpr auto bitlen(size_t x) {
   return ceil_log2(x + 1);
}

/**
 * Precompute the zeta-values for the NTT. Note that the pre-computed values
 * contain the Montgomery factor for either Kyber or Dilithium.
 */
template <size_t degree, std::integral T>
consteval static auto precompute_zetas(T q, T monty, T root_of_unity) {
   using T2 = next_longer_int_t<T>;

   std::array<T, degree> result = {0};

   auto bitreverse = [](size_t k) -> size_t {
      size_t r = 0;
      const auto l = ceil_log2(degree);
      for(size_t i = 0; i < l; ++i) {
         r |= ((k >> i) & 1) << (l - 1 - i);
      }
      return r;
   };

   auto pow = [q](T base, size_t exp) -> T2 {
      T2 res = 1;
      for(size_t i = 0; i < exp; ++i) {
         res = (res * base) % q;
      }
      return res;
   };

   auto csubq = [q](T a) -> T { return a <= q / 2 ? a : a - q; };

   for(size_t i = 0; i < result.size(); ++i) {
      result[i] = csubq(pow(root_of_unity, bitreverse(i)) * monty % q);
   }

   return result;
}

namespace detail {

/**
 * Wraps any XOF to limit the number of bytes that can be produced to @p bound.
 * When the bound is reached, the XOF will throw an Internal_Error.
 */
template <typename XofT, size_t bound>
   requires requires(XofT xof) {
      { xof.template output<1>() } -> std::convertible_to<std::span<const uint8_t, 1>>;
      { xof.template output<42>() } -> std::convertible_to<std::span<const uint8_t, 42>>;
   }
class Bounded_XOF final {
   private:
      template <size_t bytes, typename MapFnT>
      using MappedValueT = std::invoke_result_t<MapFnT, std::array<uint8_t, bytes>>;

   public:
      template <size_t bytes>
      constexpr static auto default_transformer(std::array<uint8_t, bytes> x) {
         return x;
      }

      template <size_t bytes, typename T>
      constexpr static bool default_predicate(T) {
         return true;
      }

   public:
      Bounded_XOF()
         requires std::default_initializable<XofT>
            : m_bytes_consumed(0) {}

      explicit Bounded_XOF(XofT xof) : m_xof(xof), m_bytes_consumed(0) {}

      /**
       * @returns the next byte from the XOF that fulfills @p predicate.
       */
      template <typename PredicateFnT = decltype(default_predicate<1, uint8_t>)>
         requires std::invocable<PredicateFnT, uint8_t>
      constexpr auto next_byte(PredicateFnT&& predicate = default_predicate<1, uint8_t>) {
         return next<1>([](const auto bytes) { return bytes[0]; }, std::forward<PredicateFnT>(predicate));
      }

      /**
       * Pulls the next @p bytes from the XOF and applies @p transformer to the
       * output. The result is returned if @p predicate is fulfilled.
       * @returns the transformed output of the XOF that fulfills @p predicate.
       */
      template <size_t bytes,
                typename MapFnT = decltype(default_transformer<bytes>),
                typename PredicateFnT = decltype(default_predicate<bytes, MappedValueT<bytes, MapFnT>>)>
         requires std::invocable<MapFnT, std::array<uint8_t, bytes>> &&
                  std::invocable<PredicateFnT, MappedValueT<bytes, MapFnT>>
      constexpr auto next(MapFnT&& transformer = default_transformer<bytes>,
                          PredicateFnT&& predicate = default_predicate<bytes, MappedValueT<bytes, MapFnT>>) {
         while(true) {
            auto output = transformer(take<bytes>());
            if(predicate(output)) {
               return output;
            }
         }
      }

   private:
      template <size_t bytes>
      constexpr std::array<uint8_t, bytes> take() {
         m_bytes_consumed += bytes;
         if(m_bytes_consumed > bound) {
            throw Internal_Error("XOF consumed more bytes than allowed");
         }
         return m_xof.template output<bytes>();
      }

   private:
      XofT m_xof;
      size_t m_bytes_consumed;
};

}  // namespace detail

class XOF;

template <size_t bound>
using Bounded_XOF = detail::Bounded_XOF<XOF&, bound>;

}  // namespace Botan

#endif

Coverage Report

Created: 2025-04-11 06:34

Line	Count	Source (jump to first uncovered line)
1		/*
2		* PQ CRYSTALS Common Helpers
3		*
4		* Further changes
5		* (C) 2024 Jack Lloyd
6		* (C) 2024 René Meusel, Fabian Albert, Rohde & Schwarz Cybersecurity
7		*
8		* Botan is released under the Simplified BSD License (see license.txt)
9		*/
10
11		#ifndef BOTAN_PQ_CRYSTALS_HELPERS_H_
12		#define BOTAN_PQ_CRYSTALS_HELPERS_H_
13
14		#include <concepts>
15		#include <cstdint>
16		#include <span>
17		#include <tuple>
18
19		#include <botan/exceptn.h>
20		#include <botan/internal/bit_ops.h>
21
22		namespace Botan {
23
24		// clang-format off
25
26		template <std::unsigned_integral T>
27		requires(sizeof(T) <= 4)
28		using next_longer_uint_t =
29		std::conditional_t<sizeof(T) == 1, uint16_t,
30		std::conditional_t<sizeof(T) == 2, uint32_t,
31		std::conditional_t<sizeof(T) == 4, uint64_t, void>>>;
32
33		template <std::signed_integral T>
34		requires(sizeof(T) <= 4)
35		using next_longer_int_t =
36		std::conditional_t<sizeof(T) == 1, int16_t,
37		std::conditional_t<sizeof(T) == 2, int32_t,
38		std::conditional_t<sizeof(T) == 4, int64_t, void>>>;
39
40		// clang-format on
41
42		template <std::integral T>
43		requires(size_t(sizeof(T)) <= 4)
44		consteval T montgomery_R(T q) {
45		using T_unsigned = std::make_unsigned_t<T>;
46		using T2 = next_longer_uint_t<T_unsigned>;
47		return (T2(1) << (sizeof(T) * 8)) % q;
48		}
49
50		template <std::integral T>
51		requires(size_t(sizeof(T)) <= 4)
52		consteval T montgomery_R2(T q) {
53		using T2 = next_longer_int_t<T>;
54		return (static_cast<T2>(montgomery_R(q)) * static_cast<T2>(montgomery_R(q))) % q;
55		}
56
57		template <std::integral T>
58		struct eea_result {
59		T gcd;
60		T u;
61		T v;
62		};
63
64		/**
65		* Run the extended Euclidean algorithm to find the greatest common divisor of a
66		* and b and the Bézout coefficients, u and v.
67		*/
68		template <std::integral T>
69		consteval eea_result<T> extended_euclidean_algorithm(T a, T b) {
70		if(a > b) {
71		std::swap(a, b);
72		}
73
74		T u1 = 0, v1 = 1, u2 = 1, v2 = 0;
75
76		if(a != b) {
77		while(a != 0) {
78		const T q = b / a;
79		std::tie(a, b) = std::make_tuple(static_cast<T>(b - q * a), a);
80		std::tie(u1, v1, u2, v2) = std::make_tuple(u2, v2, static_cast<T>(u1 - q * u2), static_cast<T>(v1 - q * v2));
81		}
82		}
83
84		return {.gcd = b, .u = u1, .v = v1};
85		}
86
87		/**
88		* Calculate the modular multiplacative inverse of q modulo m.
89		* By default, this assumes m to be 2^bitlength of T for application in a
90		* Montgomery reduction.
91		*/
92		template <std::integral T, std::integral T2 = next_longer_int_t<T>>
93		requires(sizeof(T) <= 4)
94		consteval T modular_inverse(T q, T2 m = T2(1) << sizeof(T) * 8) {
95		return static_cast<T>(extended_euclidean_algorithm<T2>(q, m).u);
96		}
97
98	106	constexpr auto bitlen(size_t x) {
99	106	return ceil_log2(x + 1);
100	106	}
101
102		/**
103		* Precompute the zeta-values for the NTT. Note that the pre-computed values
104		* contain the Montgomery factor for either Kyber or Dilithium.
105		*/
106		template <size_t degree, std::integral T>
107		consteval static auto precompute_zetas(T q, T monty, T root_of_unity) {
108		using T2 = next_longer_int_t<T>;
109
110		std::array<T, degree> result = {0};
111
112		auto bitreverse = [](size_t k) -> size_t {
113		size_t r = 0;
114		const auto l = ceil_log2(degree);
115		for(size_t i = 0; i < l; ++i) {
116		r \|= ((k >> i) & 1) << (l - 1 - i);
117		}
118		return r;
119		};
120
121		auto pow = [q](T base, size_t exp) -> T2 {
122		T2 res = 1;
123		for(size_t i = 0; i < exp; ++i) {
124		res = (res * base) % q;
125		}
126		return res;
127		};
128
129		auto csubq = [q](T a) -> T { return a <= q / 2 ? a : a - q; };
130
131		for(size_t i = 0; i < result.size(); ++i) {
132		result[i] = csubq(pow(root_of_unity, bitreverse(i)) * monty % q);
133		}
134
135		return result;
136		}
137
138		namespace detail {
139
140		/**
141		* Wraps any XOF to limit the number of bytes that can be produced to @p bound.
142		* When the bound is reached, the XOF will throw an Internal_Error.
143		*/
144		template <typename XofT, size_t bound>
145		requires requires(XofT xof) {
146		{ xof.template output<1>() } -> std::convertible_to<std::span<const uint8_t, 1>>;
147		{ xof.template output<42>() } -> std::convertible_to<std::span<const uint8_t, 42>>;
148		}
149		class Bounded_XOF final {
150		private:
151		template <size_t bytes, typename MapFnT>
152		using MappedValueT = std::invoke_result_t<MapFnT, std::array<uint8_t, bytes>>;
153
154		public:
155		template <size_t bytes>
156	0	constexpr static auto default_transformer(std::array<uint8_t, bytes> x) {
157	0	return x;
158	0	}
159
160		template <size_t bytes, typename T>
161	0	constexpr static bool default_predicate(T) {
162	0	return true;
163	0	} Unexecuted instantiation: bool Botan::detail::Bounded_XOF<Botan::XOF&, 229ul>::default_predicate<8ul, std::__1::array<unsigned char, 8ul> >(std::__1::array<unsigned char, 8ul>) Unexecuted instantiation: bool Botan::detail::Bounded_XOF<Botan::XOF&, 481ul>::default_predicate<1ul, unsigned char>(unsigned char) Unexecuted instantiation: bool Botan::detail::Bounded_XOF<Botan::XOF&, 229ul>::default_predicate<1ul, unsigned char>(unsigned char) Unexecuted instantiation: bool Botan::detail::Bounded_XOF<Botan::XOF&, 894ul>::default_predicate<1ul, unsigned char>(unsigned char) Unexecuted instantiation: bool Botan::detail::Bounded_XOF<Botan::XOF&, 840ul>::default_predicate<3ul, std::__1::pair<std::__1::optional<unsigned short>, std::__1::optional<unsigned short> > >(std::__1::pair<std::__1::optional<unsigned short>, std::__1::optional<unsigned short> >) Unexecuted instantiation: bool Botan::detail::Bounded_XOF<Botan::XOF&, 840ul>::default_predicate<1ul, unsigned char>(unsigned char)
164
165		public:
166		Bounded_XOF()
167		requires std::default_initializable<XofT>
168		: m_bytes_consumed(0) {}
169
170	0	explicit Bounded_XOF(XofT xof) : m_xof(xof), m_bytes_consumed(0) {} Unexecuted instantiation: Botan::detail::Bounded_XOF<Botan::XOF&, 894ul>::Bounded_XOF(Botan::XOF&) Unexecuted instantiation: Botan::detail::Bounded_XOF<Botan::XOF&, 481ul>::Bounded_XOF(Botan::XOF&) Unexecuted instantiation: Botan::detail::Bounded_XOF<Botan::XOF&, 229ul>::Bounded_XOF(Botan::XOF&) Unexecuted instantiation: Botan::detail::Bounded_XOF<Botan::XOF&, 840ul>::Bounded_XOF(Botan::XOF&)
171
172		/**
173		* @returns the next byte from the XOF that fulfills @p predicate.
174		*/
175		template <typename PredicateFnT = decltype(default_predicate<1, uint8_t>)>
176		requires std::invocable<PredicateFnT, uint8_t>
177	0	constexpr auto next_byte(PredicateFnT&& predicate = default_predicate<1, uint8_t>) {
178	0	return next<1>([](const auto bytes) { return bytes[0]; }, std::forward<PredicateFnT>(predicate)); Unexecuted instantiation: dilithium_algos.cpp:_ZZN5Botan6detail11Bounded_XOFIRNS_3XOFELm229EE9next_byteIZNS_15Dilithium_Algos14sample_in_ballENS_10StrongSpanIKNS_6StrongINSt3__16vectorIhNS9_9allocatorIhEEEENS_24DilithiumCommitmentHash_EJEEEEERKNS_18DilithiumConstantsEE3$_0Qsr3stdE9invocableITL0__hEEEDaOT_ENKUlSN_E_clINS9_5arrayIhLm1EEEEEDaSN_ Unexecuted instantiation: _ZZN5Botan6detail11Bounded_XOFIRNS_3XOFELm481EE9next_byteIFbhEQsr3stdE9invocableITL0__hEEEDaOT_ENKUlS8_E_clINSt3__15arrayIhLm1EEEEEDaS8_
179	0	} Unexecuted instantiation: dilithium_algos.cpp:_ZN5Botan6detail11Bounded_XOFIRNS_3XOFELm229EE9next_byteIZNS_15Dilithium_Algos14sample_in_ballENS_10StrongSpanIKNS_6StrongINSt3__16vectorIhNS9_9allocatorIhEEEENS_24DilithiumCommitmentHash_EJEEEEERKNS_18DilithiumConstantsEE3$_0Qsr3stdE9invocableITL0__hEEEDaOT_ Unexecuted instantiation: _ZN5Botan6detail11Bounded_XOFIRNS_3XOFELm481EE9next_byteIFbhEQsr3stdE9invocableITL0__hEEEDaOT_
180
181		/**
182		* Pulls the next @p bytes from the XOF and applies @p transformer to the
183		* output. The result is returned if @p predicate is fulfilled.
184		* @returns the transformed output of the XOF that fulfills @p predicate.
185		*/
186		template <size_t bytes,
187		typename MapFnT = decltype(default_transformer<bytes>),
188		typename PredicateFnT = decltype(default_predicate<bytes, MappedValueT<bytes, MapFnT>>)>
189		requires std::invocable<MapFnT, std::array<uint8_t, bytes>> &&
190		std::invocable<PredicateFnT, MappedValueT<bytes, MapFnT>>
191		constexpr auto next(MapFnT&& transformer = default_transformer<bytes>,
192	0	PredicateFnT&& predicate = default_predicate<bytes, MappedValueT<bytes, MapFnT>>) {
193	0	while(true) {
194	0	auto output = transformer(take<bytes>());
195	0	if(predicate(output)) {
196	0	return output;
197	0	}
198	0	}
199	0	} Unexecuted instantiation: _ZN5Botan6detail11Bounded_XOFIRNS_3XOFELm229EE4nextILm8EFNSt3__15arrayIhLm8EEES8_EFbS8_EQaasr3stdE9invocableITL0_0_NS7_IhXTL0__EEEEsr3stdE9invocableITL0_1_NS6_13invoke_resultISB_JSC_EE4typeEEEEDaOT0_OT1_ Unexecuted instantiation: dilithium_algos.cpp:_ZN5Botan6detail11Bounded_XOFIRNS_3XOFELm229EE4nextILm1EZNS4_9next_byteIZNS_15Dilithium_Algos14sample_in_ballENS_10StrongSpanIKNS_6StrongINSt3__16vectorIhNSA_9allocatorIhEEEENS_24DilithiumCommitmentHash_EJEEEEERKNS_18DilithiumConstantsEE3$_0Qsr3stdE9invocableITL0__hEEEDaOT_EUlSO_E_SM_Qaasr3stdE9invocableITL0_0_NSA_5arrayIhXTL0__EEEEsr3stdE9invocableITL0_1_NSA_13invoke_resultISR_JST_EE4typeEEEEDaOT0_OT1_ Unexecuted instantiation: dilithium_algos.cpp:_ZN5Botan6detail11Bounded_XOFIRNS_3XOFELm894EE4nextILm3EZNS_15Dilithium_Algos12_GLOBAL__N_118sample_ntt_uniformENS_10StrongSpanIKNS_6StrongINSt3__16vectorIhNSA_9allocatorIhEEEENS_20DilithiumPublicSeed_EJEEEEERNS_8CRYSTALS10PolynomialINS_19DilithiumPolyTraitsELNSJ_6DomainE1EEEtRKNS_18DilithiumConstantsEE3$_0ZNS7_18sample_ntt_uniformESI_SO_tSR_E3$_1Qaasr3stdE9invocableITL0_0_NSA_5arrayIhXTL0__EEEEsr3stdE9invocableITL0_1_NSA_13invoke_resultISU_JSW_EE4typeEEEEDaOT0_OT1_ Unexecuted instantiation: _ZN5Botan6detail11Bounded_XOFIRNS_3XOFELm481EE4nextILm1EZNS4_9next_byteIFbhEQsr3stdE9invocableITL0__hEEEDaOT_EUlS9_E_RS7_Qaasr3stdE9invocableITL0_0_NSt3__15arrayIhXTL0__EEEEsr3stdE9invocableITL0_1_NSE_13invoke_resultISD_JSG_EE4typeEEEEDaOT0_OT1_ Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan6detail11Bounded_XOFIRNS_3XOFELm840EE4nextILm3EZZNS_11Kyber_Algos12_GLOBAL__N_118sample_ntt_uniformERNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS8_6DomainE1EEES3_EN3$_0clEvEUlT_E_FbNSt3__14pairINSH_8optionalItEESK_EEEQaasr3stdE9invocableITL0_0_NSH_5arrayIhXTL0__EEEEsr3stdE9invocableITL0_1_NSH_13invoke_resultISN_JSP_EE4typeEEEEDaOT0_OT1_
200
201		private:
202		template <size_t bytes>
203	0	constexpr std::array<uint8_t, bytes> take() {
204	0	m_bytes_consumed += bytes;
205	0	if(m_bytes_consumed > bound) {
206	0	throw Internal_Error("XOF consumed more bytes than allowed");
207	0	}
208	0	return m_xof.template output<bytes>();
209	0	} Unexecuted instantiation: std::__1::array<unsigned char, 8ul> Botan::detail::Bounded_XOF<Botan::XOF&, 229ul>::take<8ul>() Unexecuted instantiation: std::__1::array<unsigned char, 1ul> Botan::detail::Bounded_XOF<Botan::XOF&, 229ul>::take<1ul>() Unexecuted instantiation: std::__1::array<unsigned char, 3ul> Botan::detail::Bounded_XOF<Botan::XOF&, 894ul>::take<3ul>() Unexecuted instantiation: std::__1::array<unsigned char, 1ul> Botan::detail::Bounded_XOF<Botan::XOF&, 481ul>::take<1ul>() Unexecuted instantiation: std::__1::array<unsigned char, 3ul> Botan::detail::Bounded_XOF<Botan::XOF&, 840ul>::take<3ul>()
210
211		private:
212		XofT m_xof;
213		size_t m_bytes_consumed;
214		};
215
216		} // namespace detail
217
218		class XOF;
219
220		template <size_t bound>
221		using Bounded_XOF = detail::Bounded_XOF<XOF&, bound>;
222
223		} // namespace Botan
224
225		#endif