13063690544

Committed 31 Jan 2025 12:13AM UTC coverage: 91.229% (-0.004%) from 91.233%

Build # 13063690544

Build Type

Pull #4616

github

Committed by

web-flow

Commit Message

Merge 2222759d3 into 63746e757

Pull Request Pull Request #4616: Document the EC support situation in 3.7.0

Run Details

94110 of 103158 relevant lines covered (91.23%)

11255755.28 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.59

/src/lib/pubkey/classic_mceliece/cmce_field_ordering.cpp

/*
 * Classic McEliece Field Ordering Generation
 * Based on the public domain reference implementation by the designers
 * (https://classic.mceliece.org/impl.html - released in Oct 2022 for NISTPQC-R4)
 *
 * (C) 2023 Jack Lloyd
 *     2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 **/
#include <botan/internal/cmce_field_ordering.h>

#include <botan/cmce.h>
#include <botan/mem_ops.h>
#include <botan/internal/loadstor.h>

#include <numeric>
#include <utility>
#include <vector>

namespace Botan {

namespace CMCE_CT {

namespace {

template <std::unsigned_integral T1, std::unsigned_integral T2>
   requires(sizeof(T1) <= 8 && sizeof(T2) <= 8)
void cond_swap_pair(CT::Mask<uint64_t> cond_mask, std::pair<T1, T2>& a, std::pair<T1, T2>& b) {
   cond_mask.conditional_swap(a.first, b.first);
   cond_mask.conditional_swap(a.second, b.second);
}

template <std::unsigned_integral T1, std::unsigned_integral T2>
void compare_and_swap_pair(std::span<std::pair<T1, T2>> a, size_t i, size_t k, size_t l) {
   static_assert(sizeof(T1) <= sizeof(uint64_t) && sizeof(T2) <= sizeof(uint64_t),
                 "Types T1 and T2 must be at most 64 bits wide");
   if((i & k) == 0) {  // i and k do not depend on secret data
      auto swap_required_mask = CT::Mask<uint64_t>::is_lt(a[l].first, a[i].first);
      cond_swap_pair(swap_required_mask, a[i], a[l]);
   } else {
      auto swap_required_mask = CT::Mask<uint64_t>::is_gt(a[l].first, a[i].first);
      cond_swap_pair(swap_required_mask, a[i], a[l]);
   }
}

// Sorts a vector of pairs after the first element
template <std::unsigned_integral T1, std::unsigned_integral T2>
void bitonic_sort_pair(std::span<std::pair<T1, T2>> a) {
   const size_t n = a.size();
   BOTAN_ARG_CHECK(is_power_of_2(n), "Input vector size must be a power of 2");

   for(size_t k = 2; k <= n; k *= 2) {
      for(size_t j = k / 2; j > 0; j /= 2) {
         for(size_t i = 0; i < n; ++i) {
            const size_t l = i ^ j;
            if(l > i) {
               compare_and_swap_pair(a, i, k, l);
            }
         }
      }
   }
}

template <std::unsigned_integral T>
T min(const T& a, const T& b) {
   auto mask = CT::Mask<T>::is_lt(a, b);
   return mask.select(a, b);
}

}  // namespace

}  // namespace CMCE_CT

namespace {
template <std::unsigned_integral T1, std::unsigned_integral T2>
std::vector<std::pair<T1, T2>> zip(std::span<const T1> vec_1, std::span<const T2> vec_2) {
   BOTAN_ARG_CHECK(vec_1.size() == vec_2.size(), "Vectors' dimensions do not match");
   std::vector<std::pair<T1, T2>> vec_zipped;
   vec_zipped.reserve(vec_1.size());
   for(size_t i = 0; i < vec_1.size(); ++i) {
      vec_zipped.push_back(std::make_pair(vec_1[i], vec_2[i]));
   }
   return vec_zipped;
}

template <std::unsigned_integral T1, std::unsigned_integral T2>
std::pair<secure_vector<T1>, secure_vector<T2>> unzip(const std::span<std::pair<T1, T2>>& vec_zipped) {
   std::pair<secure_vector<T1>, secure_vector<T2>> res;

   res.first.reserve(vec_zipped.size());
   res.second.reserve(vec_zipped.size());

   for(const auto& [elem1, elem2] : vec_zipped) {
      res.first.push_back(elem1);
      res.second.push_back(elem2);
   }
   return res;
}

/// @returns (vec[0],0), ..., (vec[n-1],n-1)
std::vector<std::pair<uint32_t, uint16_t>> enumerate(std::span<const uint32_t> vec) {
   BOTAN_DEBUG_ASSERT(vec.size() < std::numeric_limits<uint16_t>::max());

   std::vector<std::pair<uint32_t, uint16_t>> enumerated;

   std::transform(vec.begin(), vec.end(), std::back_inserter(enumerated), [ctr = uint16_t(0)](uint32_t elem) mutable {
      return std::make_pair(elem, ctr++);
   });

   return enumerated;
}

/**
 * @brief Create permutation pi as in (Section 8.2, Step 3).
 *
 * @param a The vector that is sorted
 *
 * @return (pi sorted after a, a sorted after pi)
 */
std::pair<secure_vector<uint32_t>, CmcePermutation> create_pi(secure_vector<uint32_t> a) {
   auto a_pi_zipped = enumerate(a);
   CMCE_CT::bitonic_sort_pair(std::span(a_pi_zipped));

   CmcePermutation pi_sorted;
   std::tie(a, pi_sorted.get()) = unzip(std::span(a_pi_zipped));

   return std::make_pair(a, pi_sorted);
}

/**
* @brief Create a GF element from pi as in (Section 8.2, Step 4).
* Corresponds to the reverse bits of pi.
*/
Classic_McEliece_GF from_pi(CmcePermutationElement pi_elem, CmceGfMod modulus, size_t m) {
   auto reversed_bits = ct_reverse_bits(pi_elem.get());
   reversed_bits >>= (sizeof(uint16_t) * 8 - m);
   return Classic_McEliece_GF(CmceGfElem(reversed_bits), modulus);
}

/**
 * @brief Part of field ordering generation according to ISO 9.2.10
 */
secure_vector<uint16_t> composeinv(std::span<const uint16_t> c, std::span<const uint16_t> pi) {
   auto pi_c_zipped = zip(pi, c);
   CMCE_CT::bitonic_sort_pair(std::span(pi_c_zipped));
   // Extract c from the sorted vector
   secure_vector<uint16_t> c_sorted;
   std::transform(pi_c_zipped.begin(), pi_c_zipped.end(), std::back_inserter(c_sorted), [](const auto& pair) {
      return pair.second;
   });

   return c_sorted;
}

// p,q = composeinv(p,q),composeinv(q,p)
void simultaneous_composeinv(secure_vector<uint16_t>& p, secure_vector<uint16_t>& q) {
   auto p_new = composeinv(p, q);
   q = composeinv(q, p);
   p = std::move(p_new);
}

/**
 * @brief Generate control bits as in ISO 9.2.10.
 *
 * TODO: This function can be optimized (see Classic McEliece reference implementation)
 */
secure_vector<uint16_t> generate_control_bits_internal(const secure_vector<uint16_t>& pi) {
   const auto n = pi.size();
   BOTAN_ASSERT_NOMSG(is_power_of_2(n));
   const size_t m = ceil_log2(n);

   if(m == 1) {
      return secure_vector<uint16_t>({pi.at(0)});
   }
   secure_vector<uint16_t> p(n);
   for(size_t x = 0; x < n; ++x) {
      p.at(x) = pi.at(x ^ 1);
   }
   secure_vector<uint16_t> q(n);
   for(size_t x = 0; x < n; ++x) {
      q.at(x) = pi.at(x) ^ 1;
   }

   secure_vector<uint16_t> range_n(n);
   std::iota(range_n.begin(), range_n.end(), static_cast<uint16_t>(0));
   auto piinv = composeinv(range_n, pi);

   simultaneous_composeinv(p, q);

   secure_vector<uint16_t> c(n);
   for(uint16_t x = 0; static_cast<size_t>(x) < n; ++x) {
      c.at(x) = CMCE_CT::min(x, p.at(x));
   }

   simultaneous_composeinv(p, q);

   for(size_t i = 1; i < m - 1; ++i) {
      auto cp = composeinv(c, q);
      simultaneous_composeinv(p, q);
      for(size_t x = 0; x < n; ++x) {
         c.at(x) = CMCE_CT::min(c.at(x), cp.at(x));
      }
   }

   secure_vector<uint16_t> f(n / 2);
   for(size_t j = 0; j < n / 2; ++j) {
      f.at(j) = c.at(2 * j) % 2;
   }

   secure_vector<uint16_t> big_f(n);
   for(uint16_t x = 0; size_t(x) < n; ++x) {
      big_f.at(x) = x ^ f.at(x / 2);
   }

   auto fpi = composeinv(big_f, piinv);

   secure_vector<uint16_t> l(n / 2);
   for(size_t k = 0; k < n / 2; ++k) {
      l.at(k) = fpi.at(2 * k) % 2;
   }

   secure_vector<uint16_t> big_l(n);
   for(uint16_t y = 0; size_t(y) < n; ++y) {
      big_l.at(y) = y ^ l.at(y / 2);
   }

   auto big_m = composeinv(fpi, big_l);

   secure_vector<uint16_t> subm0(n / 2);
   secure_vector<uint16_t> subm1(n / 2);
   for(size_t j = 0; j < n / 2; ++j) {
      subm0.at(j) = big_m.at(2 * j) / 2;
      subm1.at(j) = big_m.at(2 * j + 1) / 2;
   }

   auto subz0 = generate_control_bits_internal(subm0);
   auto subz1 = generate_control_bits_internal(subm1);

   secure_vector<uint16_t> z(subz0.size() + subz1.size());
   for(size_t j = 0; j < subz0.size(); ++j) {
      z.at(2 * j) = subz0.at(j);
      z.at(2 * j + 1) = subz1.at(j);
   }

   return concat(f, z, l);
}

CT::Choice ct_has_adjacent_duplicates(std::span<const uint32_t> vec) {
   CT::Mask<uint32_t> mask = CT::Mask<uint32_t>::cleared();
   for(size_t i = 0; i < vec.size() - 1; ++i) {
      mask |= CT::Mask<uint32_t>::is_equal(vec[i], vec[i + 1]);
   }
   return mask.as_choice();
}

}  // anonymous namespace

std::optional<Classic_McEliece_Field_Ordering> Classic_McEliece_Field_Ordering::create_field_ordering(
   const Classic_McEliece_Parameters& params, StrongSpan<const CmceOrderingBits> random_bits) {
   BOTAN_ARG_CHECK(random_bits.size() == (params.sigma2() * params.q()) / 8, "Wrong random bits size");

   auto a = load_le<secure_vector<uint32_t>>(random_bits);  // contains a_0, a_1, ...
   auto [sorted_a, pi] = create_pi(std::move(a));
   if(ct_has_adjacent_duplicates(sorted_a).as_bool()) {
      return std::nullopt;
   }

   return Classic_McEliece_Field_Ordering(std::move(pi), params.poly_f());
}

std::vector<Classic_McEliece_GF> Classic_McEliece_Field_Ordering::alphas(size_t n) const {
   BOTAN_ASSERT_NOMSG(m_poly_f.get() != 0);
   BOTAN_ASSERT_NOMSG(m_pi.size() >= n);

   std::vector<Classic_McEliece_GF> n_alphas_vec;

   std::transform(m_pi.begin(), m_pi.begin() + n, std::back_inserter(n_alphas_vec), [this](uint16_t pi_elem) {
      return from_pi(CmcePermutationElement(pi_elem), m_poly_f, Classic_McEliece_GF::log_q_from_mod(m_poly_f));
   });

   return n_alphas_vec;
}

secure_bitvector Classic_McEliece_Field_Ordering::alphas_control_bits() const {
   // Each vector element contains one bit of the control bits
   const auto control_bits_as_words = generate_control_bits_internal(m_pi.get());
   auto control_bits = secure_bitvector(control_bits_as_words.size());
   for(size_t i = 0; i < control_bits.size(); ++i) {
      control_bits.at(i) = control_bits_as_words.at(i);
   }

   return control_bits;
}

// Based on the Python code "permutation(c)" from Bernstein
// "Verified fast formulas for control bits for permutation networks"
Classic_McEliece_Field_Ordering Classic_McEliece_Field_Ordering::create_from_control_bits(
   const Classic_McEliece_Parameters& params, const secure_bitvector& control_bits) {
   BOTAN_ASSERT_NOMSG(control_bits.size() == (2 * params.m() - 1) << (params.m() - 1));
   const uint16_t n = uint16_t(1) << params.m();
   CmcePermutation pi(n);
   std::iota(pi.begin(), pi.end(), static_cast<uint16_t>(0));
   for(size_t i = 0; i < 2 * params.m() - 1; ++i) {
      const size_t gap = size_t(1) << std::min(i, 2 * params.m() - 2 - i);
      for(size_t j = 0; j < size_t(n / 2); ++j) {
         const size_t pos = (j % gap) + 2 * gap * (j / gap);
         auto mask = CT::Mask<uint16_t>::expand(control_bits[i * n / 2 + j]);
         mask.conditional_swap(pi[pos], pi[pos + gap]);
      }
   }

   return Classic_McEliece_Field_Ordering(std::move(pi), params.poly_f());
}

void Classic_McEliece_Field_Ordering::permute_with_pivots(const Classic_McEliece_Parameters& params,
                                                          const CmceColumnSelection& pivots) {
   auto col_offset = params.pk_no_rows() - Classic_McEliece_Parameters::mu();

   for(size_t p_idx = 1; p_idx <= Classic_McEliece_Parameters::mu(); ++p_idx) {
      size_t p_counter = 0;
      for(size_t col = 0; col < Classic_McEliece_Parameters::nu(); ++col) {
         auto mask_is_pivot_set = CT::Mask<size_t>::expand(pivots.at(col));
         p_counter += CT::Mask<size_t>::expand(pivots.at(col)).if_set_return(1);
         auto mask_is_current_pivot = CT::Mask<size_t>::is_equal(p_idx, p_counter);
         (mask_is_pivot_set & mask_is_current_pivot)
            .conditional_swap(m_pi.get().at(col_offset + col), m_pi.get().at(col_offset + p_idx - 1));
      }
   }
}

}  // namespace Botan

1	/*
2	* Classic McEliece Field Ordering Generation
3	* Based on the public domain reference implementation by the designers
4	* (https://classic.mceliece.org/impl.html - released in Oct 2022 for NISTPQC-R4)
5	*
6	* (C) 2023 Jack Lloyd
7	* 2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
8	*
9	* Botan is released under the Simplified BSD License (see license.txt)
10	**/
11	#include <botan/internal/cmce_field_ordering.h>
12
13	#include <botan/cmce.h>
14	#include <botan/mem_ops.h>
15	#include <botan/internal/loadstor.h>
16
17	#include <numeric>
18	#include <utility>
19	#include <vector>
20
21	namespace Botan {
22
23	namespace CMCE_CT {
24
25	namespace {
26
27	template <std::unsigned_integral T1, std::unsigned_integral T2>
28	requires(sizeof(T1) <= 8 && sizeof(T2) <= 8)
29	void cond_swap_pair(CT::Mask<uint64_t> cond_mask, std::pair<T1, T2>& a, std::pair<T1, T2>& b) {	2,147,483,647✔
30	cond_mask.conditional_swap(a.first, b.first);	2,147,483,647✔
31	cond_mask.conditional_swap(a.second, b.second);	2,147,483,647✔
32	}	2,147,483,647✔
33
34	template <std::unsigned_integral T1, std::unsigned_integral T2>
35	void compare_and_swap_pair(std::span<std::pair<T1, T2>> a, size_t i, size_t k, size_t l) {	2,147,483,647✔
36	static_assert(sizeof(T1) <= sizeof(uint64_t) && sizeof(T2) <= sizeof(uint64_t),
37	"Types T1 and T2 must be at most 64 bits wide");
38	if((i & k) == 0) { // i and k do not depend on secret data	2,147,483,647✔
39	auto swap_required_mask = CT::Mask<uint64_t>::is_lt(a[l].first, a[i].first);	2,147,483,647✔
40	cond_swap_pair(swap_required_mask, a[i], a[l]);	2,147,483,647✔
41	} else {
42	auto swap_required_mask = CT::Mask<uint64_t>::is_gt(a[l].first, a[i].first);	1,908,767,744✔
43	cond_swap_pair(swap_required_mask, a[i], a[l]);	1,908,767,744✔
44	}
45	}	2,147,483,647✔
46
47	// Sorts a vector of pairs after the first element
48	template <std::unsigned_integral T1, std::unsigned_integral T2>
49	void bitonic_sort_pair(std::span<std::pair<T1, T2>> a) {	3,415,911✔
50	const size_t n = a.size();	3,415,911✔
51	BOTAN_ARG_CHECK(is_power_of_2(n), "Input vector size must be a power of 2");	×
52
53	for(size_t k = 2; k <= n; k *= 2) {	15,665,041✔
54	for(size_t j = k / 2; j > 0; j /= 2) {	45,939,986✔
55	for(size_t i = 0; i < n; ++i) {	2,147,483,647✔
56	const size_t l = i ^ j;	2,147,483,647✔
57	if(l > i) {	2,147,483,647✔
58	compare_and_swap_pair(a, i, k, l);	2,147,483,647✔
59	}
60	}
61	}
62	}
63	}	3,415,911✔
64
65	template <std::unsigned_integral T>
66	T min(const T& a, const T& b) {	52,125,696✔
67	auto mask = CT::Mask<T>::is_lt(a, b);	52,125,696✔
68	return mask.select(a, b);	52,125,696✔
69	}
70
71	} // namespace
72
73	} // namespace CMCE_CT
74
75	namespace {
76	template <std::unsigned_integral T1, std::unsigned_integral T2>
77	std::vector<std::pair<T1, T2>> zip(std::span<const T1> vec_1, std::span<const T2> vec_2) {	3,415,819✔
78	BOTAN_ARG_CHECK(vec_1.size() == vec_2.size(), "Vectors' dimensions do not match");	3,415,819✔
79	std::vector<std::pair<T1, T2>> vec_zipped;	3,415,819✔
80	vec_zipped.reserve(vec_1.size());	3,415,819✔
81	for(size_t i = 0; i < vec_1.size(); ++i) {	192,216,843✔
82	vec_zipped.push_back(std::make_pair(vec_1[i], vec_2[i]));	188,801,024✔
83	}
84	return vec_zipped;	3,415,819✔
85	}	×
86
87	template <std::unsigned_integral T1, std::unsigned_integral T2>
88	std::pair<secure_vector<T1>, secure_vector<T2>> unzip(const std::span<std::pair<T1, T2>>& vec_zipped) {	92✔
89	std::pair<secure_vector<T1>, secure_vector<T2>> res;	92✔
90
91	res.first.reserve(vec_zipped.size());	92✔
92	res.second.reserve(vec_zipped.size());	92✔
93
94	for(const auto& [elem1, elem2] : vec_zipped) {	647,260✔
95	res.first.push_back(elem1);	647,168✔
96	res.second.push_back(elem2);	647,168✔
97	}
98	return res;	92✔
99	}	×
100
101	/// @returns (vec[0],0), ..., (vec[n-1],n-1)
102	std::vector<std::pair<uint32_t, uint16_t>> enumerate(std::span<const uint32_t> vec) {	92✔
103	BOTAN_DEBUG_ASSERT(vec.size() < std::numeric_limits<uint16_t>::max());	92✔
104
105	std::vector<std::pair<uint32_t, uint16_t>> enumerated;	92✔
106
107	std::transform(vec.begin(), vec.end(), std::back_inserter(enumerated), [ctr = uint16_t(0)](uint32_t elem) mutable {	92✔
108	return std::make_pair(elem, ctr++);	647,168✔
109	});
110
111	return enumerated;	92✔
112	}	×
113
114	/**
115	* @brief Create permutation pi as in (Section 8.2, Step 3).
116	*
117	* @param a The vector that is sorted
118	*
119	* @return (pi sorted after a, a sorted after pi)
120	*/
121	std::pair<secure_vector<uint32_t>, CmcePermutation> create_pi(secure_vector<uint32_t> a) {	92✔
122	auto a_pi_zipped = enumerate(a);	92✔
123	CMCE_CT::bitonic_sort_pair(std::span(a_pi_zipped));	92✔
124
125	CmcePermutation pi_sorted;	92✔
126	std::tie(a, pi_sorted.get()) = unzip(std::span(a_pi_zipped));	92✔
127
128	return std::make_pair(a, pi_sorted);	184✔
129	}	92✔
130
131	/**
132	* @brief Create a GF element from pi as in (Section 8.2, Step 4).
133	* Corresponds to the reverse bits of pi.
134	*/
135	Classic_McEliece_GF from_pi(CmcePermutationElement pi_elem, CmceGfMod modulus, size_t m) {	1,776,784✔
136	auto reversed_bits = ct_reverse_bits(pi_elem.get());	1,776,784✔
137	reversed_bits >>= (sizeof(uint16_t) * 8 - m);	1,776,784✔
138	return Classic_McEliece_GF(CmceGfElem(reversed_bits), modulus);	1,776,784✔
139	}
140
141	/**
142	* @brief Part of field ordering generation according to ISO 9.2.10
143	*/
144	secure_vector<uint16_t> composeinv(std::span<const uint16_t> c, std::span<const uint16_t> pi) {	3,415,819✔
145	auto pi_c_zipped = zip(pi, c);	3,415,819✔
146	CMCE_CT::bitonic_sort_pair(std::span(pi_c_zipped));	3,415,819✔
147	// Extract c from the sorted vector
148	secure_vector<uint16_t> c_sorted;	3,415,819✔
149	std::transform(pi_c_zipped.begin(), pi_c_zipped.end(), std::back_inserter(c_sorted), [](const auto& pair) {	3,415,819✔
150	return pair.second;	188,801,024✔
151	});
152
153	return c_sorted;	3,415,819✔
154	}	3,415,819✔
155
156	// p,q = composeinv(p,q),composeinv(q,p)
157	void simultaneous_composeinv(secure_vector<uint16_t>& p, secure_vector<uint16_t>& q) {	1,024,633✔
158	auto p_new = composeinv(p, q);	1,024,633✔
159	q = composeinv(q, p);	2,049,266✔
160	p = std::move(p_new);	1,024,633✔
161	}	1,024,633✔
162
163	/**
164	* @brief Generate control bits as in ISO 9.2.10.
165	*
166	* TODO: This function can be optimized (see Classic McEliece reference implementation)
167	*/
168	secure_vector<uint16_t> generate_control_bits_internal(const secure_vector<uint16_t>& pi) {	683,936✔
169	const auto n = pi.size();	683,936✔
170	BOTAN_ASSERT_NOMSG(is_power_of_2(n));	683,936✔
171	const size_t m = ceil_log2(n);	683,936✔
172
173	if(m == 1) {	683,936✔
174	return secure_vector<uint16_t>({pi.at(0)});	342,016✔
175	}
176	secure_vector<uint16_t> p(n);	341,920✔
177	for(size_t x = 0; x < n; ++x) {	8,447,904✔
178	p.at(x) = pi.at(x ^ 1);	8,105,984✔
179	}
180	secure_vector<uint16_t> q(n);	341,920✔
181	for(size_t x = 0; x < n; ++x) {	8,447,904✔
182	q.at(x) = pi.at(x) ^ 1;	8,105,984✔
183	}
184
185	secure_vector<uint16_t> range_n(n);	341,920✔
186	std::iota(range_n.begin(), range_n.end(), static_cast<uint16_t>(0));	341,920✔
187	auto piinv = composeinv(range_n, pi);	341,920✔
188
189	simultaneous_composeinv(p, q);	341,920✔
190
191	secure_vector<uint16_t> c(n);	341,920✔
192	for(uint16_t x = 0; static_cast<size_t>(x) < n; ++x) {	8,447,904✔
193	c.at(x) = CMCE_CT::min(x, p.at(x));	8,105,984✔
194	}
195
196	simultaneous_composeinv(p, q);	341,920✔
197
198	for(size_t i = 1; i < m - 1; ++i) {	682,713✔
199	auto cp = composeinv(c, q);	340,793✔
200	simultaneous_composeinv(p, q);	340,793✔
201	for(size_t x = 0; x < n; ++x) {	44,360,505✔
202	c.at(x) = CMCE_CT::min(c.at(x), cp.at(x));	44,019,712✔
203	}
204	}	340,793✔
205
206	secure_vector<uint16_t> f(n / 2);	341,920✔
207	for(size_t j = 0; j < n / 2; ++j) {	4,394,912✔
208	f.at(j) = c.at(2 * j) % 2;	4,052,992✔
209	}
210
211	secure_vector<uint16_t> big_f(n);	341,920✔
212	for(uint16_t x = 0; size_t(x) < n; ++x) {	8,447,904✔
213	big_f.at(x) = x ^ f.at(x / 2);	8,105,984✔
214	}
215
216	auto fpi = composeinv(big_f, piinv);	341,920✔
217
218	secure_vector<uint16_t> l(n / 2);	341,920✔
219	for(size_t k = 0; k < n / 2; ++k) {	4,394,912✔
220	l.at(k) = fpi.at(2 * k) % 2;	4,052,992✔
221	}
222
223	secure_vector<uint16_t> big_l(n);	341,920✔
224	for(uint16_t y = 0; size_t(y) < n; ++y) {	8,447,904✔
225	big_l.at(y) = y ^ l.at(y / 2);	8,105,984✔
226	}
227
228	auto big_m = composeinv(fpi, big_l);	341,920✔
229
230	secure_vector<uint16_t> subm0(n / 2);	341,920✔
231	secure_vector<uint16_t> subm1(n / 2);	341,920✔
232	for(size_t j = 0; j < n / 2; ++j) {	4,394,912✔
233	subm0.at(j) = big_m.at(2 * j) / 2;	4,052,992✔
234	subm1.at(j) = big_m.at(2 * j + 1) / 2;	4,052,992✔
235	}
236
237	auto subz0 = generate_control_bits_internal(subm0);	341,920✔
238	auto subz1 = generate_control_bits_internal(subm1);	341,920✔
239
240	secure_vector<uint16_t> z(subz0.size() + subz1.size());	341,920✔
241	for(size_t j = 0; j < subz0.size(); ++j) {	24,378,272✔
242	z.at(2 * j) = subz0.at(j);	24,036,352✔
243	z.at(2 * j + 1) = subz1.at(j);	24,036,352✔
244	}
245
246	return concat(f, z, l);	341,920✔
247	}	5,470,720✔
248
249	CT::Choice ct_has_adjacent_duplicates(std::span<const uint32_t> vec) {	92✔
250	CT::Mask<uint32_t> mask = CT::Mask<uint32_t>::cleared();	92✔
251	for(size_t i = 0; i < vec.size() - 1; ++i) {	647,168✔
252	mask \|= CT::Mask<uint32_t>::is_equal(vec[i], vec[i + 1]);	647,076✔
253	}
254	return mask.as_choice();	92✔
255	}
256
257	} // anonymous namespace
258
259	std::optional<Classic_McEliece_Field_Ordering> Classic_McEliece_Field_Ordering::create_field_ordering(	92✔
260	const Classic_McEliece_Parameters& params, StrongSpan<const CmceOrderingBits> random_bits) {
261	BOTAN_ARG_CHECK(random_bits.size() == (params.sigma2() * params.q()) / 8, "Wrong random bits size");	92✔
262
263	auto a = load_le<secure_vector<uint32_t>>(random_bits); // contains a_0, a_1, ...	92✔
264	auto [sorted_a, pi] = create_pi(std::move(a));	184✔
265	if(ct_has_adjacent_duplicates(sorted_a).as_bool()) {	92✔
266	return std::nullopt;	×
267	}
268
269	return Classic_McEliece_Field_Ordering(std::move(pi), params.poly_f());	92✔
270	}	92✔
271
272	std::vector<Classic_McEliece_GF> Classic_McEliece_Field_Ordering::alphas(size_t n) const {	288✔
273	BOTAN_ASSERT_NOMSG(m_poly_f.get() != 0);	288✔
274	BOTAN_ASSERT_NOMSG(m_pi.size() >= n);	288✔
275
276	std::vector<Classic_McEliece_GF> n_alphas_vec;	288✔
277
278	std::transform(m_pi.begin(), m_pi.begin() + n, std::back_inserter(n_alphas_vec), [this](uint16_t pi_elem) {	288✔
279	return from_pi(CmcePermutationElement(pi_elem), m_poly_f, Classic_McEliece_GF::log_q_from_mod(m_poly_f));	1,776,784✔
280	});
281
282	return n_alphas_vec;	288✔
283	}	×
284
285	secure_bitvector Classic_McEliece_Field_Ordering::alphas_control_bits() const {	96✔
286	// Each vector element contains one bit of the control bits
287	const auto control_bits_as_words = generate_control_bits_internal(m_pi.get());	96✔
288	auto control_bits = secure_bitvector(control_bits_as_words.size());	96✔
289	for(size_t i = 0; i < control_bits.size(); ++i) {	8,448,096✔
290	control_bits.at(i) = control_bits_as_words.at(i);	8,448,000✔
291	}
292
293	return control_bits;	96✔
294	}	96✔
295
296	// Based on the Python code "permutation(c)" from Bernstein
297	// "Verified fast formulas for control bits for permutation networks"
298	Classic_McEliece_Field_Ordering Classic_McEliece_Field_Ordering::create_from_control_bits(	141✔
299	const Classic_McEliece_Parameters& params, const secure_bitvector& control_bits) {
300	BOTAN_ASSERT_NOMSG(control_bits.size() == (2 * params.m() - 1) << (params.m() - 1));	141✔
301	const uint16_t n = uint16_t(1) << params.m();	141✔
302	CmcePermutation pi(n);	141✔
303	std::iota(pi.begin(), pi.end(), static_cast<uint16_t>(0));	141✔
304	for(size_t i = 0; i < 2 * params.m() - 1; ++i) {	3,594✔
305	const size_t gap = size_t(1) << std::min(i, 2 * params.m() - 2 - i);	3,453✔
306	for(size_t j = 0; j < size_t(n / 2); ++j) {	12,451,197✔
307	const size_t pos = (j % gap) + 2 * gap * (j / gap);	12,447,744✔
308	auto mask = CT::Mask<uint16_t>::expand(control_bits[i * n / 2 + j]);	12,447,744✔
309	mask.conditional_swap(pi[pos], pi[pos + gap]);	12,447,744✔
310	}
311	}
312
313	return Classic_McEliece_Field_Ordering(std::move(pi), params.poly_f());	141✔
314	}	141✔
315
316	void Classic_McEliece_Field_Ordering::permute_with_pivots(const Classic_McEliece_Parameters& params,	25✔
317	const CmceColumnSelection& pivots) {
318	auto col_offset = params.pk_no_rows() - Classic_McEliece_Parameters::mu();	25✔
319
320	for(size_t p_idx = 1; p_idx <= Classic_McEliece_Parameters::mu(); ++p_idx) {	825✔
321	size_t p_counter = 0;
322	for(size_t col = 0; col < Classic_McEliece_Parameters::nu(); ++col) {	52,000✔
323	auto mask_is_pivot_set = CT::Mask<size_t>::expand(pivots.at(col));	51,200✔
324	p_counter += CT::Mask<size_t>::expand(pivots.at(col)).if_set_return(1);	51,200✔
325	auto mask_is_current_pivot = CT::Mask<size_t>::is_equal(p_idx, p_counter);	51,200✔
326	(mask_is_pivot_set & mask_is_current_pivot)	51,200✔
327	.conditional_swap(m_pi.get().at(col_offset + col), m_pi.get().at(col_offset + p_idx - 1));	51,200✔
328	}
329	}
330	}	25✔
331
332	} // namespace Botan

randombit / botan / 13063690544

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous