Botan 3.14.1
Crypto and TLS for C&
cmce_poly.cpp
Go to the documentation of this file.
1/*
2 * Classic McEliece Polynomials
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
12#include <botan/internal/cmce_poly.h>
13
14#include <botan/exceptn.h>
15#include <botan/internal/buffer_stuffer.h>
16#include <botan/internal/concat_util.h>
17#include <botan/internal/ct_utils.h>
18#include <algorithm>
19
20namespace Botan {
21
23 BOTAN_DEBUG_ASSERT(a.modulus() == coef_at(0).modulus());
24
26 // TODO(Botan4) use std::ranges::reverse_view here once available (need newer Clang)
27 // NOLINTNEXTLINE(modernize-loop-convert)
28 for(auto it = m_coef.rbegin(); it != m_coef.rend(); ++it) {
29 r *= a;
30 r += *it;
31 }
32
33 return r;
34}
35
37 const Classic_McEliece_Polynomial& b) const {
38 std::vector<Classic_McEliece_GF> prod(m_t * 2 - 1, {CmceGfElem(0), m_poly_f});
39
40 for(size_t i = 0; i < m_t; ++i) {
41 for(size_t j = 0; j < m_t; ++j) {
42 prod.at(i + j) += (a.coef_at(i) * b.coef_at(j));
43 }
44 }
45
46 for(size_t i = (m_t - 1) * 2; i >= m_t; --i) {
47 for(const auto& [idx, coef] : m_position_map) {
48 prod.at(i - m_t + idx) += coef * prod.at(i);
49 }
50 }
51
52 prod.erase(prod.begin() + m_t, prod.end());
53
54 return Classic_McEliece_Polynomial(std::move(prod));
55}
56
57Classic_McEliece_Polynomial Classic_McEliece_Polynomial_Ring::create_element_from_bytes(
58 std::span<const uint8_t> bytes) const {
59 BOTAN_ARG_CHECK(bytes.size() == m_t * 2, "Correct input size");
60 return create_element_from_coef(load_le<std::vector<CmceGfElem>>(bytes));
61}
62
63Classic_McEliece_Polynomial Classic_McEliece_Polynomial_Ring::create_element_from_coef(
64 const std::vector<CmceGfElem>& coeff_vec) const {
65 std::vector<Classic_McEliece_GF> coeff_vec_gf;
66 CmceGfElem coeff_mask = CmceGfElem((uint16_t(1) << Classic_McEliece_GF::log_q_from_mod(m_poly_f)) - 1);
67 std::transform(coeff_vec.begin(), coeff_vec.end(), std::back_inserter(coeff_vec_gf), [&](auto& coeff) {
68 return Classic_McEliece_GF(coeff & coeff_mask, m_poly_f);
69 });
70 return Classic_McEliece_Polynomial(coeff_vec_gf);
71}
72
77
78std::optional<Classic_McEliece_Minimal_Polynomial> Classic_McEliece_Polynomial_Ring::compute_minimal_polynomial(
80 const auto polynomial = create_element_from_bytes(seed);
81 std::vector<Classic_McEliece_Polynomial> mat;
82
83 mat.push_back(create_element_from_coef(concat<std::vector<CmceGfElem>>(
84 std::vector<CmceGfElem>{CmceGfElem(1)}, std::vector<CmceGfElem>(degree() - 1, CmceGfElem(0)))));
85
86 mat.push_back(polynomial);
87
88 for(size_t j = 2; j <= degree(); ++j) {
89 mat.push_back(multiply(mat.at(j - 1), polynomial));
90 }
91
92 // Gaussian
93 for(size_t j = 0; j < degree(); ++j) {
94 for(size_t k = j + 1; k < degree(); ++k) {
95 const auto cond = GF_Mask::is_zero(mat.at(j).coef_at(j));
96
97 for(size_t c = j; c < degree() + 1; ++c) {
98 mat.at(c).coef_at(j) += cond.if_set_return(mat.at(c).coef_at(k));
99 }
100 }
101
102 const bool is_zero_at_diagonal = mat.at(j).coef_at(j).is_zero();
103 CT::unpoison(is_zero_at_diagonal);
104 if(is_zero_at_diagonal) {
105 // Fail if not systematic. New rejection sampling iteration starts.
106 return std::nullopt;
107 }
108
109 const auto inv = mat.at(j).coef_at(j).inv();
110
111 for(size_t c = j; c < degree() + 1; ++c) {
112 mat.at(c).coef_at(j) *= inv;
113 }
114
115 for(size_t k = 0; k < degree(); ++k) {
116 if(k != j) {
117 const auto t = mat.at(j).coef_at(k);
118
119 for(size_t c = j; c < degree() + 1; ++c) {
120 mat.at(c).coef_at(k) += mat.at(c).coef_at(j) * t;
121 }
122 }
123 }
124 }
125
126 auto minimal_poly_coeffs = mat.at(degree()).coef();
127 // Add coefficient 1 since polynomial is monic
128 minimal_poly_coeffs.emplace_back(CmceGfElem(1), poly_f());
129
130 return Classic_McEliece_Minimal_Polynomial(std::move(minimal_poly_coeffs));
131}
132
134 BOTAN_ASSERT_NOMSG(!coef().empty());
135 const auto& all_coeffs = coef();
136 // Store all except coef for monomial x^t since polynomial is monic (ISO Spec Section 9.2.9)
137 const auto coeffs_to_store = std::span(all_coeffs).first(all_coeffs.size() - 1);
138 secure_vector<uint8_t> bytes(sizeof(uint16_t) * coeffs_to_store.size());
139 BufferStuffer bytes_stuf(bytes);
140 for(const auto& coef : coeffs_to_store) {
141 store_le(bytes_stuf.next<sizeof(CmceGfElem)>(), coef.elem().get());
142 }
143 BOTAN_ASSERT_NOMSG(bytes_stuf.full());
144 return bytes;
145}
146
148 CmceGfMod poly_f) {
149 BOTAN_ASSERT_NOMSG(bytes.size() % 2 == 0);
150 const auto coef_vec = load_le<std::vector<CmceGfElem>>(bytes);
151
152 // Each coefficient is an element of GF(2^m); the unused high bits must be clear
153 const auto q_minus_1 = static_cast<uint16_t>((uint16_t(1) << Classic_McEliece_GF::log_q_from_mod(poly_f)) - 1);
154 auto in_range = CT::Mask<uint16_t>::set();
155 for(const auto& coeff : coef_vec) {
156 in_range &= CT::Mask<uint16_t>::is_lte(coeff.get(), q_minus_1);
157 }
158 if(!in_range.as_bool()) {
159 throw Decoding_Error("Classic McEliece polynomial coefficient is out of range");
160 }
161
162 std::vector<Classic_McEliece_GF> coeff_vec_gf;
163 std::transform(coef_vec.begin(), coef_vec.end(), std::back_inserter(coeff_vec_gf), [poly_f](auto& coeff) {
164 return Classic_McEliece_GF(coeff, poly_f);
165 });
166
167 coeff_vec_gf.emplace_back(CmceGfElem(1), poly_f); // x^t as polynomial is monic
168
169 return Classic_McEliece_Minimal_Polynomial(coeff_vec_gf);
170}
171
172} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
Helper class to ease in-place marshalling of concatenated fixed-length values.
constexpr std::span< uint8_t > next(size_t bytes)
constexpr bool full() const
static constexpr Mask< T > is_lte(T x, T y)
Definition ct_utils.h:468
static constexpr Mask< T > set()
Definition ct_utils.h:387
Represents an element of the finite field GF(q) for q = 2^m.
Definition cmce_gf.h:29
static size_t log_q_from_mod(CmceGfMod modulus)
Get m.
Definition cmce_gf.h:53
CmceGfMod modulus() const
Get the modulus f(z) of GF(q) as a GF_Mod.
Definition cmce_gf.h:74
Representation of a minimal polynomial in GF(q)[y].
Definition cmce_poly.h:80
secure_vector< uint8_t > serialize() const
Serialize the polynomial to bytes according to ISO Section 9.2.9.
static Classic_McEliece_Minimal_Polynomial from_bytes(std::span< const uint8_t > bytes, CmceGfMod poly_f)
Create a polynomial from bytes according to ISO Section 9.2.9.
Classic_McEliece_Minimal_Polynomial(std::vector< Classic_McEliece_GF > coef)
Definition cmce_poly.h:82
Classic_McEliece_Polynomial multiply(const Classic_McEliece_Polynomial &a, const Classic_McEliece_Polynomial &b) const
Definition cmce_poly.cpp:36
size_t degree() const
The degree of polynomials in this ring (and of F(y)).
Definition cmce_poly.h:134
std::optional< Classic_McEliece_Minimal_Polynomial > compute_minimal_polynomial(StrongSpan< const CmceIrreducibleBits > seed) const
Compute the minimal polynomial g of polynomial created from a seed.
Definition cmce_poly.cpp:78
Representation of a Classic McEliece polynomial.
Definition cmce_poly.h:31
const std::vector< Classic_McEliece_GF > & coef() const
Get the entire coefficients vector of the polynomial.
Definition cmce_poly.h:58
Classic_McEliece_GF operator()(Classic_McEliece_GF a) const
Evaluate the polynomial P(x) at a given point a, i.e., compute P(a).
Definition cmce_poly.cpp:22
Classic_McEliece_GF & coef_at(size_t i)
Get the coefficient of the i-th monomial as a reference (from low to high degree).
Definition cmce_poly.h:48
static GF_Mask is_zero(Classic_McEliece_GF v)
Definition cmce_gf.h:163
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
Strong< uint16_t, struct CmceGfMod_ > CmceGfMod
Represents a GF(q) modulus.
Definition cmce_types.h:22
Strong< uint16_t, struct CmceGfElem_ > CmceGfElem
Represents a GF(q) element.
Definition cmce_types.h:19
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
constexpr auto concat(Rs &&... ranges)
Definition concat_util.h:95
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
bool operator==(const AlgorithmIdentifier &x, const AlgorithmIdentifier &y)
Definition alg_id.cpp:54
Represents a non-zero coefficient of the modulus F(y) (which is in GF(q)[y]).
Definition cmce_poly.h:110