Botan 3.14.1
Crypto and TLS for C&
cmce_poly.h
Go to the documentation of this file.
1/*
2 * Classic McEliece Polynomials
3 * (C) 2023 Jack Lloyd
4 * 2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 **/
8
9#ifndef BOTAN_CMCE_POLY_H_
10#define BOTAN_CMCE_POLY_H_
11
12#include <botan/secmem.h>
13#include <botan/internal/cmce_gf.h>
14
15#include <optional>
16
17namespace Botan {
18
19/**
20 * @brief Representation of a Classic McEliece polynomial.
21 *
22 * This class represents a polynomial in the ring GF(q)[y]. E.g an example element of degree 2 could be:
23 * a = (z^3+1)y^2 + (z)y + (z^4+z^3)
24 * The degree of the polynomial is given by the size of the coefficient vector given to
25 * the constructor, even if the leading coefficient is zero. Coefficients are stored from
26 * lowest to highest monomial degree (coef_at(0) = (z^4+z^3) in the example above).
27 *
28 * This class is merely a container. The modulus and the operations with Polynomials (e.g. multiplication)
29 * is handled by the Classic_McEliece_Polynomial_Ring class.
30 */
32 public:
33 /**
34 * @brief Construct a polynomial given its coefficients.
35 *
36 * @param coef The coefficients of the polynomial. The first element is the coefficient of the lowest monomial.
37 */
38 explicit Classic_McEliece_Polynomial(std::vector<Classic_McEliece_GF> coef) : m_coef(std::move(coef)) {}
39
40 /**
41 * @brief Evaluate the polynomial P(x) at a given point a, i.e., compute P(a).
42 */
43 Classic_McEliece_GF operator()(Classic_McEliece_GF a) const;
44
45 /**
46 * @brief Get the coefficient of the i-th monomial as a reference (from low to high degree).
47 */
48 Classic_McEliece_GF& coef_at(size_t i) { return m_coef.at(i); }
49
50 /**
51 * @brief Get the coefficient of the i-th monomial (from low to high degree).
52 */
53 const Classic_McEliece_GF& coef_at(size_t i) const { return m_coef.at(i); }
54
55 /**
56 * @brief Get the entire coefficients vector of the polynomial.
57 */
58 const std::vector<Classic_McEliece_GF>& coef() const { return m_coef; }
59
60 /**
61 * @brief Get the degree of the polynomial.
62 *
63 * Note that the degree is given by the size of the coefficient vector, even if the leading coefficient is zero.
64 */
65 size_t degree() const { return m_coef.size() + 1; }
66
67 void _const_time_poison() const { CT::poison(m_coef); }
68
69 void _const_time_unpoison() const { CT::unpoison(m_coef); }
70
71 private:
72 std::vector<Classic_McEliece_GF> m_coef;
73};
74
75/**
76 * @brief Representation of a minimal polynomial in GF(q)[y].
77 *
78 * It represents the monic irreducible degree-t polynomial of the goppa code.
79 */
81 public:
82 explicit Classic_McEliece_Minimal_Polynomial(std::vector<Classic_McEliece_GF> coef) :
84
85 /**
86 * @brief Serialize the polynomial to bytes according to ISO Section 9.2.9.
87 */
88 secure_vector<uint8_t> serialize() const;
89
90 /**
91 * @brief Create a polynomial from bytes according to ISO Section 9.2.9.
92 */
93 static Classic_McEliece_Minimal_Polynomial from_bytes(std::span<const uint8_t> bytes, CmceGfMod poly_f);
94};
95
96/**
97 * @brief Represents the polynomial ring GF(q)[y]/F(y) where F(y) is the modulus polynomial in
98 * GF(q)[y] of degree t.
99 *
100 * This class contains a modulus polynomial F(y) and the GF(q) modulus f(z). It is used
101 * to create and operate with Classic_McEliece_Polynomials.
102 */
104 public:
105 /**
106 * @brief Represents a non-zero coefficient of the modulus F(y) (which is in GF(q)[y]).
107 *
108 * E.g. {.idx = 4, .coeff = (z+1)} represents the monomial (z+1)y^4.
109 */
114
115 /**
116 * @brief Construct a polynomial ring GF(q)[y]/F(y) by defining the polynomial modulus F(y),
117 * the GF(q) modulus f(z) and the degree of F(y).
118 *
119 * F(y) is given by a vector of Big_F_Coefficients, where each one represents a monomial of F(y).
120 * However, the highest monomial must not be specified, since it is always 1.
121 *
122 * @param poly_big_f_coef The non-zero coefficients of F(y) in GF(q)[y] WITHOUT the highest monomial.
123 * @param poly_f The modulus f(z) of GF(q).
124 * @param t The polynomial degree of the ring (and of F(y)).
125 */
126 Classic_McEliece_Polynomial_Ring(std::vector<Big_F_Coefficient> poly_big_f_coef, CmceGfMod poly_f, size_t t) :
127 m_position_map(std::move(poly_big_f_coef)), m_t(t), m_poly_f(poly_f) {}
128
129 CmceGfMod poly_f() const { return m_poly_f; }
130
131 /**
132 * @brief The degree of polynomials in this ring (and of F(y)).
133 */
134 size_t degree() const { return m_t; }
135
136 /**
137 * @returns a*b over GF(q)[y]/F(y).
138 */
140 const Classic_McEliece_Polynomial& b) const;
141
142 /**
143 * @brief Compute the minimal polynomial g of polynomial created from a @p seed.
144 *
145 * @param seed over the ring GF(q)[y] according to ISO Section 8.1 Step 3.
146 *
147 * @return g or std::nullopt if g has not full degree.
148 */
149 std::optional<Classic_McEliece_Minimal_Polynomial> compute_minimal_polynomial(
151
152 private:
153 // Creates a ring element from a coefficient vector
154 Classic_McEliece_Polynomial create_element_from_coef(const std::vector<CmceGfElem>& coeff_vec) const;
155
156 /**
157 * @brief Create a polynomial from bytes according to ISO Section 8.1 step 1 and 2.
158 */
159 Classic_McEliece_Polynomial create_element_from_bytes(std::span<const uint8_t> bytes) const;
160
161 /// Represents F(y) by storing the non-zero terms
162 std::vector<Big_F_Coefficient> m_position_map;
163
164 /// t in spec, i.e., degree of F(y)
165 size_t m_t;
166
167 // f(z) in spec
168 CmceGfMod m_poly_f;
169};
170
171bool operator==(const Classic_McEliece_Polynomial_Ring::Big_F_Coefficient& lhs,
172 const Classic_McEliece_Polynomial_Ring::Big_F_Coefficient& rhs);
173
174} // namespace Botan
175#endif
#define BOTAN_TEST_API
Definition api.h:41
Represents an element of the finite field GF(q) for q = 2^m.
Definition cmce_gf.h:29
Representation of a minimal polynomial in GF(q)[y].
Definition cmce_poly.h:80
Classic_McEliece_Minimal_Polynomial(std::vector< Classic_McEliece_GF > coef)
Definition cmce_poly.h:82
size_t degree() const
The degree of polynomials in this ring (and of F(y)).
Definition cmce_poly.h:134
Classic_McEliece_Polynomial_Ring(std::vector< Big_F_Coefficient > poly_big_f_coef, CmceGfMod poly_f, size_t t)
Construct a polynomial ring GF(q)[y]/F(y) by defining the polynomial modulus F(y),...
Definition cmce_poly.h:126
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
size_t degree() const
Get the degree of the polynomial.
Definition cmce_poly.h:65
const Classic_McEliece_GF & coef_at(size_t i) const
Get the coefficient of the i-th monomial (from low to high degree).
Definition cmce_poly.h:53
Classic_McEliece_Polynomial(std::vector< Classic_McEliece_GF > coef)
Construct a polynomial given its coefficients.
Definition cmce_poly.h:38
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
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
Strong< uint16_t, struct CmceGfMod_ > CmceGfMod
Represents a GF(q) modulus.
Definition cmce_types.h:22
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