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