27806188297

Committed 18 Jun 2026 04:12PM UTC coverage: 89.37% (-0.03%) from 89.397%

Build # 27806188297

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5677 from randombit/jack/oid-names

Add OID::registered_name

Coverage Stats

111637 of 124915 relevant lines covered (89.37%)

10895907.86 hits per line

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

95.65

/src/lib/pubkey/mce/code_based_key_gen.cpp

/*
 * (C) Copyright Projet SECRET, INRIA, Rocquencourt
 * (C) Bhaskar Biswas and  Nicolas Sendrier
 *
 * (C) 2014 cryptosource GmbH
 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
 * (C) 2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 *
 */

#include <botan/mceliece.h>

#include <botan/internal/code_based_util.h>
#include <botan/internal/loadstor.h>
#include <botan/internal/mce_internal.h>
#include <botan/internal/polyn_gf2m.h>

namespace Botan {

namespace {

class binary_matrix final {
   public:
      binary_matrix(size_t m_rown, size_t m_coln);

      void row_xor(size_t a, size_t b);
      secure_vector<size_t> row_reduced_echelon_form();

      /**
      * return the coefficient out of F_2
      */
      uint32_t coef(size_t i, size_t j) { return (m_elem[(i)*m_rwdcnt + (j) / 32] >> (j % 32)) & 1; }

      void set_coef_to_one(size_t i, size_t j) {
         m_elem[(i)*m_rwdcnt + (j) / 32] |= (static_cast<uint32_t>(1) << ((j) % 32));
      }

      void toggle_coeff(size_t i, size_t j) {
         m_elem[(i)*m_rwdcnt + (j) / 32] ^= (static_cast<uint32_t>(1) << ((j) % 32));
      }

      size_t rows() const { return m_rown; }

      size_t columns() const { return m_coln; }

      const std::vector<uint32_t>& elem() const { return m_elem; }

   private:
      size_t m_rown;    // number of rows.
      size_t m_coln;    // number of columns.
      size_t m_rwdcnt;  // number of words in a row
      std::vector<uint32_t> m_elem;
};

binary_matrix::binary_matrix(size_t rown, size_t coln) : m_rown(rown), m_coln(coln), m_rwdcnt(1 + ((m_coln - 1) / 32)) {
   m_elem = std::vector<uint32_t>(m_rown * m_rwdcnt);
}

void binary_matrix::row_xor(size_t a, size_t b) {
   for(size_t i = 0; i != m_rwdcnt; i++) {
      m_elem[a * m_rwdcnt + i] ^= m_elem[b * m_rwdcnt + i];
   }
}

//the matrix is reduced from LSB...(from right)
secure_vector<size_t> binary_matrix::row_reduced_echelon_form() {
   secure_vector<size_t> perm(m_coln);
   for(size_t i = 0; i != m_coln; i++) {
      perm[i] = i;  // initialize permutation.
   }

   uint32_t failcnt = 0;

   size_t max = m_coln - 1;
   for(size_t i = 0; i != m_rown; i++, max--) {
      bool found_row = false;

      for(size_t j = i; !found_row && j != m_rown; j++) {
         if(coef(j, max) > 0) {
            if(i != j)  //not needed as ith row is 0 and jth row is 1.
            {
               row_xor(i, j);  //xor to the row.(swap)?
            }

            found_row = true;
         }
      }

      //if no row with a 1 found then swap last column and the column with no 1 down.
      if(!found_row) {
         if(failcnt >= m_coln - m_rown) {
            perm.clear();
            return perm;
         }
         perm[m_coln - m_rown - 1 - failcnt] = max;
         failcnt++;
         if(max == 0) {
            perm.clear();
            return perm;
         }
         i--;
      } else {
         perm[i + m_coln - m_rown] = max;
         for(size_t j = i + 1; j < m_rown; j++)  //fill the column downwards with 0's
         {
            if(coef(j, max) > 0) {
               row_xor(j, i);  //check the arg. order.
            }
         }

         //fill the column with 0's upwards too.
         for(size_t j = i; j != 0; --j) {
            if(coef(j - 1, max) > 0) {
               row_xor(j - 1, i);
            }
         }
      }
   }  //end for(i)
   return perm;
}

void randomize_support(std::vector<gf2m>& L, RandomNumberGenerator& rng) {
   for(size_t i = 0; i != L.size(); ++i) {
      const gf2m rnd = random_gf2m(rng);

      // no rejection sampling, but for useful code-based parameters with n <= 13 this seem tolerable
      std::swap(L[i], L[rnd % L.size()]);
   }
}

std::unique_ptr<binary_matrix> generate_R(
   std::vector<gf2m>& L, polyn_gf2m* g, const GF2m_Field& sp_field, size_t code_length, size_t t) {
   //L- Support
   //t- Number of errors
   //n- Length of the Goppa code
   //m- The extension degree of the GF
   //g- The generator polynomial.

   const size_t r = t * sp_field.get_extension_degree();

   binary_matrix H(r, code_length);

   for(size_t i = 0; i != code_length; i++) {
      gf2m x = g->eval(lex_to_gray(L[i]));  //evaluate the polynomial at the point L[i].
      x = sp_field.gf_inv(x);
      gf2m y = x;
      for(size_t j = 0; j < t; j++) {
         for(size_t k = 0; k < sp_field.get_extension_degree(); k++) {
            if((y & (1 << k)) != 0) {
               //the co-eff. are set in 2^0,...,2^11 ; 2^0,...,2^11 format along the rows/cols?
               H.set_coef_to_one(j * sp_field.get_extension_degree() + k, i);
            }
         }
         y = sp_field.gf_mul(y, lex_to_gray(L[i]));
      }
   }  //The H matrix is fed.

   secure_vector<size_t> perm = H.row_reduced_echelon_form();
   if(perm.empty()) {
      throw Invalid_State("McEliece keygen failed - could not bring matrix to row reduced echelon form");
   }

   auto result = std::make_unique<binary_matrix>(code_length - r, r);
   for(size_t i = 0; i < result->rows(); ++i) {
      for(size_t j = 0; j < result->columns(); ++j) {
         if(H.coef(j, perm[i]) > 0) {
            result->toggle_coeff(i, j);
         }
      }
   }

   std::vector<gf2m> Laux(code_length);
   for(size_t i = 0; i < code_length; ++i) {
      Laux[i] = L[perm[i]];
   }

   for(size_t i = 0; i < code_length; ++i) {
      L[i] = Laux[i];
   }
   return result;
}
}  // namespace

McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator& rng, size_t ext_deg, size_t code_length, size_t t) {
   const McEliece_Params params = mceliece_validate_keygen_params(code_length, t);

   if(ext_deg != params.ext_deg) {
      throw Invalid_Argument("inconsistent McEliece extension degree");
   }

   const size_t codimension = params.codimension;
   auto sp_field = std::make_shared<GF2m_Field>(params.ext_deg);

   //pick the support.........
   std::vector<gf2m> L(code_length);

   for(size_t i = 0; i != L.size(); i++) {
      L[i] = static_cast<gf2m>(i);
   }
   randomize_support(L, rng);
   polyn_gf2m g(sp_field);  // create as zero

   bool success = false;
   std::unique_ptr<binary_matrix> R;

   // NOLINTNEXTLINE(*-avoid-do-while)
   do {
      // create a random irreducible polynomial
      g = polyn_gf2m(t, rng, sp_field);

      try {
         R = generate_R(L, &g, *sp_field, code_length, t);
         success = true;
      } catch(const Invalid_State&) {}
   } while(!success);

   const std::vector<polyn_gf2m> sqrtmod = polyn_gf2m::sqrt_mod_init(g);
   std::vector<polyn_gf2m> F = syndrome_init(g, L, static_cast<int>(code_length));

   // Each F[i] is the (precomputed) syndrome of the error vector with
   // a single '1' in i-th position.
   // We do not store the F[i] as polynomials of degree t , but
   // as binary vectors of length ext_deg * t (this will
   // speed up the syndrome computation)
   //
   const size_t co32 = bit_size_to_32bit_size(codimension);
   std::vector<uint32_t> H(co32 * code_length);
   uint32_t* sk = H.data();
   for(size_t i = 0; i < code_length; ++i) {
      for(size_t l = 0; l < t; ++l) {
         const size_t k = (l * ext_deg) / 32;
         const size_t j = (l * ext_deg) % 32;
         sk[k] ^= static_cast<uint32_t>(F[i].get_coef(l)) << j;
         if(j + ext_deg > 32) {
            if(j > 0) {
               sk[k + 1] ^= F[i].get_coef(l) >> (32 - j);
            }
         }
      }
      sk += co32;
   }

   // We need the support L for decoding (decryption). In fact the
   // inverse is needed

   std::vector<gf2m> Linv(code_length);
   for(size_t i = 0; i != Linv.size(); ++i) {
      Linv[L[i]] = static_cast<gf2m>(i);
   }
   std::vector<uint8_t> pubmat(R->elem().size() * 4);
   for(size_t i = 0; i < R->elem().size(); i++) {
      store_le(R->elem()[i], &pubmat[i * 4]);
   }

   return McEliece_PrivateKey(g, H, sqrtmod, Linv, pubmat);
}

}  // namespace Botan

1	/*
2	* (C) Copyright Projet SECRET, INRIA, Rocquencourt
3	* (C) Bhaskar Biswas and Nicolas Sendrier
4	*
5	* (C) 2014 cryptosource GmbH
6	* (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
7	* (C) 2015 Jack Lloyd
8	*
9	* Botan is released under the Simplified BSD License (see license.txt)
10	*
11	*/
12
13	#include <botan/mceliece.h>
14
15	#include <botan/internal/code_based_util.h>
16	#include <botan/internal/loadstor.h>
17	#include <botan/internal/mce_internal.h>
18	#include <botan/internal/polyn_gf2m.h>
19
20	namespace Botan {
21
22	namespace {
23
24	class binary_matrix final {	30✔
25	public:
26	binary_matrix(size_t m_rown, size_t m_coln);
27
28	void row_xor(size_t a, size_t b);
29	secure_vector<size_t> row_reduced_echelon_form();
30
31	/**
32	* return the coefficient out of F_2
33	*/
34	uint32_t coef(size_t i, size_t j) { return (m_elem[(i)*m_rwdcnt + (j) / 32] >> (j % 32)) & 1; }	36,501,912✔
35
36	void set_coef_to_one(size_t i, size_t j) {	23,913,490✔
37	m_elem[(i)*m_rwdcnt + (j) / 32] \|= (static_cast<uint32_t>(1) << ((j) % 32));	23,913,490✔
38	}	23,913,490✔
39
40	void toggle_coeff(size_t i, size_t j) {	18,247,538✔
41	m_elem[(i)*m_rwdcnt + (j) / 32] ^= (static_cast<uint32_t>(1) << ((j) % 32));	18,247,538✔
42	}	18,247,538✔
43
44	size_t rows() const { return m_rown; }	38,043✔
45
46	size_t columns() const { return m_coln; }	36,539,940✔
47
48	const std::vector<uint32_t>& elem() const { return m_elem; }	1,158,994✔
49
50	private:
51	size_t m_rown; // number of rows.
52	size_t m_coln; // number of columns.
53	size_t m_rwdcnt; // number of words in a row
54	std::vector<uint32_t> m_elem;
55	};
56
57	binary_matrix::binary_matrix(size_t rown, size_t coln) : m_rown(rown), m_coln(coln), m_rwdcnt(1 + ((m_coln - 1) / 32)) {	30✔
58	m_elem = std::vector<uint32_t>(m_rown * m_rwdcnt);	30✔
59	}	30✔
60
61	void binary_matrix::row_xor(size_t a, size_t b) {
62	for(size_t i = 0; i != m_rwdcnt; i++) {	860,002,201✔
63	m_elem[a * m_rwdcnt + i] ^= m_elem[b * m_rwdcnt + i];	854,339,213✔
64	}
65	}
66
67	//the matrix is reduced from LSB...(from right)
68	secure_vector<size_t> binary_matrix::row_reduced_echelon_form() {	15✔
69	secure_vector<size_t> perm(m_coln);	15✔
70	for(size_t i = 0; i != m_coln; i++) {	49,695✔
71	perm[i] = i; // initialize permutation.	49,680✔
72	}
73
74	uint32_t failcnt = 0;	15✔
75
76	size_t max = m_coln - 1;	15✔
77	for(size_t i = 0; i != m_rown; i++, max--) {	11,697✔
78	bool found_row = false;
79
80	for(size_t j = i; !found_row && j != m_rown; j++) {	34,668✔
81	if(coef(j, max) > 0) {	22,986✔
82	if(i != j) //not needed as ith row is 0 and jth row is 1.	11,652✔
83	{
84	row_xor(i, j); //xor to the row.(swap)?	22,986✔
85	}
86
87	found_row = true;
88	}
89	}
90
91	//if no row with a 1 found then swap last column and the column with no 1 down.
92	if(!found_row) {	11,682✔
93	if(failcnt >= m_coln - m_rown) {	30✔
94	perm.clear();	×
95	return perm;
96	}
97	perm[m_coln - m_rown - 1 - failcnt] = max;	30✔
98	failcnt++;	30✔
99	if(max == 0) {	30✔
100	perm.clear();	×
101	return perm;
102	}
103	i--;	30✔
104	} else {
105	perm[i + m_coln - m_rown] = max;	11,652✔
106	for(size_t j = i + 1; j < m_rown; j++) //fill the column downwards with 0's	5,669,414✔
107	{
108	if(coef(j, max) > 0) {	5,657,762✔
109	row_xor(j, i); //check the arg. order.	5,657,762✔
110	}
111	}
112
113	//fill the column with 0's upwards too.
114	for(size_t j = i; j != 0; --j) {	5,669,414✔
115	if(coef(j - 1, max) > 0) {	5,657,762✔
116	row_xor(j - 1, i);	5,669,414✔
117	}
118	}
119	}
120	} //end for(i)
121	return perm;
122	}
123
124	void randomize_support(std::vector<gf2m>& L, RandomNumberGenerator& rng) {	15✔
125	for(size_t i = 0; i != L.size(); ++i) {	49,695✔
126	const gf2m rnd = random_gf2m(rng);	49,680✔
127
128	// no rejection sampling, but for useful code-based parameters with n <= 13 this seem tolerable
129	std::swap(L[i], L[rnd % L.size()]);	49,680✔
130	}
131	}	15✔
132
133	std::unique_ptr<binary_matrix> generate_R(	15✔
134	std::vector<gf2m>& L, polyn_gf2m* g, const GF2m_Field& sp_field, size_t code_length, size_t t) {
135	//L- Support
136	//t- Number of errors
137	//n- Length of the Goppa code
138	//m- The extension degree of the GF
139	//g- The generator polynomial.
140
141	const size_t r = t * sp_field.get_extension_degree();	15✔
142
143	binary_matrix H(r, code_length);	15✔
144
145	for(size_t i = 0; i != code_length; i++) {	49,695✔
146	gf2m x = g->eval(lex_to_gray(L[i])); //evaluate the polynomial at the point L[i].	49,680✔
147	x = sp_field.gf_inv(x);	49,680✔
148	gf2m y = x;
149	for(size_t j = 0; j < t; j++) {	3,853,216✔
150	for(size_t k = 0; k < sp_field.get_extension_degree(); k++) {	51,632,624✔
151	if((y & (1 << k)) != 0) {	47,829,088✔
152	//the co-eff. are set in 2^0,...,2^11 ; 2^0,...,2^11 format along the rows/cols?
153	H.set_coef_to_one(j * sp_field.get_extension_degree() + k, i);	23,913,490✔
154	}
155	}
156	y = sp_field.gf_mul(y, lex_to_gray(L[i]));	7,606,140✔
157	}
158	} //The H matrix is fed.
159
160	secure_vector<size_t> perm = H.row_reduced_echelon_form();	15✔
161	if(perm.empty()) {	15✔
162	throw Invalid_State("McEliece keygen failed - could not bring matrix to row reduced echelon form");	×
163	}
164
165	auto result = std::make_unique<binary_matrix>(code_length - r, r);	15✔
166	for(size_t i = 0; i < result->rows(); ++i) {	38,043✔
167	for(size_t j = 0; j < result->columns(); ++j) {	36,539,940✔
168	if(H.coef(j, perm[i]) > 0) {	36,501,912✔
169	result->toggle_coeff(i, j);	18,247,538✔
170	}
171	}
172	}
173
174	std::vector<gf2m> Laux(code_length);	15✔
175	for(size_t i = 0; i < code_length; ++i) {	49,695✔
176	Laux[i] = L[perm[i]];	49,680✔
177	}
178
179	for(size_t i = 0; i < code_length; ++i) {	49,695✔
180	L[i] = Laux[i];	49,680✔
181	}
182	return result;	30✔
183	}	45✔
184	} // namespace
185
186	McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator& rng, size_t ext_deg, size_t code_length, size_t t) {	15✔
187	const McEliece_Params params = mceliece_validate_keygen_params(code_length, t);	15✔
188
189	if(ext_deg != params.ext_deg) {	15✔
190	throw Invalid_Argument("inconsistent McEliece extension degree");	×
191	}
192
193	const size_t codimension = params.codimension;	15✔
194	auto sp_field = std::make_shared<GF2m_Field>(params.ext_deg);	15✔
195
196	//pick the support.........
197	std::vector<gf2m> L(code_length);	15✔
198
199	for(size_t i = 0; i != L.size(); i++) {	49,695✔
200	L[i] = static_cast<gf2m>(i);	49,680✔
201	}
202	randomize_support(L, rng);	15✔
203	polyn_gf2m g(sp_field); // create as zero	15✔
204
205	bool success = false;	15✔
206	std::unique_ptr<binary_matrix> R;	15✔
207
208	// NOLINTNEXTLINE(*-avoid-do-while)
209	do {	15✔
210	// create a random irreducible polynomial
211	g = polyn_gf2m(t, rng, sp_field);	30✔
212
213	try {	15✔
214	R = generate_R(L, &g, *sp_field, code_length, t);	30✔
215	success = true;	15✔
216	} catch(const Invalid_State&) {}	×
217	} while(!success);	15✔
218
219	const std::vector<polyn_gf2m> sqrtmod = polyn_gf2m::sqrt_mod_init(g);	15✔
220	std::vector<polyn_gf2m> F = syndrome_init(g, L, static_cast<int>(code_length));	15✔
221
222	// Each F[i] is the (precomputed) syndrome of the error vector with
223	// a single '1' in i-th position.
224	// We do not store the F[i] as polynomials of degree t , but
225	// as binary vectors of length ext_deg * t (this will
226	// speed up the syndrome computation)
227	//
228	const size_t co32 = bit_size_to_32bit_size(codimension);	15✔
229	std::vector<uint32_t> H(co32 * code_length);	15✔
230	uint32_t* sk = H.data();	15✔
231	for(size_t i = 0; i < code_length; ++i) {	49,695✔
232	for(size_t l = 0; l < t; ++l) {	3,853,216✔
233	const size_t k = (l * ext_deg) / 32;	3,803,536✔
234	const size_t j = (l * ext_deg) % 32;	3,803,536✔
235	sk[k] ^= static_cast<uint32_t>(F[i].get_coef(l)) << j;	3,803,536✔
236	if(j + ext_deg > 32) {	3,803,536✔
237	if(j > 0) {	1,262,624✔
238	sk[k + 1] ^= F[i].get_coef(l) >> (32 - j);	1,262,624✔
239	}
240	}
241	}
242	sk += co32;	49,680✔
243	}
244
245	// We need the support L for decoding (decryption). In fact the
246	// inverse is needed
247
248	std::vector<gf2m> Linv(code_length);	15✔
249	for(size_t i = 0; i != Linv.size(); ++i) {	49,695✔
250	Linv[L[i]] = static_cast<gf2m>(i);	49,680✔
251	}
252	std::vector<uint8_t> pubmat(R->elem().size() * 4);	15✔
253	for(size_t i = 0; i < R->elem().size(); i++) {	1,158,979✔
254	store_le(R->elem()[i], &pubmat[i * 4]);	1,158,964✔
255	}
256
257	return McEliece_PrivateKey(g, H, sqrtmod, Linv, pubmat);	15✔
258	}	45✔
259
260	} // namespace Botan

randombit / botan / 27806188297

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