Botan  2.11.0
Crypto and TLS for C++11
goppa_code.cpp
Go to the documentation of this file.
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  *
8  * Botan is released under the Simplified BSD License (see license.txt)
9  *
10  */
11 
12 #include <botan/internal/mce_internal.h>
13 #include <botan/internal/code_based_util.h>
14 
15 namespace Botan {
16 
17 namespace {
18 
19 void matrix_arr_mul(std::vector<uint32_t> matrix,
20  uint32_t numo_rows,
21  uint32_t words_per_row,
22  const uint8_t* input_vec,
23  uint32_t* output_vec, uint32_t output_vec_len)
24  {
25  for(size_t j = 0; j < numo_rows; j++)
26  {
27  if((input_vec[j / 8] >> (j % 8)) & 1)
28  {
29  for(size_t i = 0; i < output_vec_len; i ++)
30  {
31  output_vec[i] ^= matrix[ j * (words_per_row) + i];
32  }
33  }
34  }
35  }
36 
37 /**
38 * returns the error vector to the syndrome
39 */
40 secure_vector<gf2m> goppa_decode(const polyn_gf2m & syndrom_polyn,
41  const polyn_gf2m & g,
42  const std::vector<polyn_gf2m> & sqrtmod,
43  const std::vector<gf2m> & Linv)
44  {
45  gf2m a;
46  uint32_t code_length = Linv.size();
47  uint32_t t = g.get_degree();
48 
49  std::shared_ptr<GF2m_Field> sp_field = g.get_sp_field();
50 
51  std::pair<polyn_gf2m, polyn_gf2m> h_aux = polyn_gf2m::eea_with_coefficients( syndrom_polyn, g, 1);
52  polyn_gf2m & h = h_aux.first;
53  polyn_gf2m & aux = h_aux.second;
54  a = sp_field->gf_inv(aux.get_coef(0));
55  gf2m log_a = sp_field->gf_log(a);
56  for(int i = 0; i <= h.get_degree(); ++i)
57  {
58  h.set_coef(i,sp_field->gf_mul_zrz(log_a,h.get_coef(i)));
59  }
60 
61  // compute h(z) += z
62  h.add_to_coef( 1, 1);
63  // compute S square root of h (using sqrtmod)
64  polyn_gf2m S(t - 1, g.get_sp_field());
65 
66  for(uint32_t i=0;i<t;i++)
67  {
68  a = sp_field->gf_sqrt(h.get_coef(i));
69 
70  if(i & 1)
71  {
72  for(uint32_t j=0;j<t;j++)
73  {
74  S.add_to_coef( j, sp_field->gf_mul(a, sqrtmod[i/2].get_coef(j)));
75  }
76  }
77  else
78  {
79  S.add_to_coef( i/2, a);
80  }
81  } /* end for loop (i) */
82 
83 
84  S.get_degree();
85 
86  std::pair<polyn_gf2m, polyn_gf2m> v_u = polyn_gf2m::eea_with_coefficients(S, g, t/2+1);
87  polyn_gf2m & u = v_u.second;
88  polyn_gf2m & v = v_u.first;
89 
90  // sigma = u^2+z*v^2
91  polyn_gf2m sigma ( t , g.get_sp_field());
92 
93  const int u_deg = u.get_degree();
94  BOTAN_ASSERT(u_deg >= 0, "Valid degree");
95  for(int i = 0; i <= u_deg; ++i)
96  {
97  sigma.set_coef(2*i, sp_field->gf_square(u.get_coef(i)));
98  }
99 
100  const int v_deg = v.get_degree();
101  BOTAN_ASSERT(v_deg >= 0, "Valid degree");
102  for(int i = 0; i <= v_deg; ++i)
103  {
104  sigma.set_coef(2*i+1, sp_field->gf_square(v.get_coef(i)));
105  }
106 
107  secure_vector<gf2m> res = find_roots_gf2m_decomp(sigma, code_length);
108  size_t d = res.size();
109 
110  secure_vector<gf2m> result(d);
111  for(uint32_t i = 0; i < d; ++i)
112  {
113  gf2m current = res[i];
114 
115  gf2m tmp;
116  tmp = gray_to_lex(current);
117  /// XXX double assignment, possible bug?
118  if(tmp >= code_length) /* invalid root */
119  {
120  result[i] = static_cast<gf2m>(i);
121  }
122  result[i] = Linv[tmp];
123  }
124 
125  return result;
126  }
127 }
128 
130  secure_vector<uint8_t>& error_mask_out,
131  const secure_vector<uint8_t>& ciphertext,
132  const McEliece_PrivateKey& key)
133  {
134  mceliece_decrypt(plaintext_out, error_mask_out, ciphertext.data(), ciphertext.size(), key);
135  }
136 
138  secure_vector<uint8_t>& plaintext,
139  secure_vector<uint8_t> & error_mask,
140  const uint8_t ciphertext[],
141  size_t ciphertext_len,
142  const McEliece_PrivateKey & key)
143  {
144  secure_vector<gf2m> error_pos;
145  plaintext = mceliece_decrypt(error_pos, ciphertext, ciphertext_len, key);
146 
147  const size_t code_length = key.get_code_length();
148  secure_vector<uint8_t> result((code_length+7)/8);
149  for(auto&& pos : error_pos)
150  {
151  if(pos > code_length)
152  {
153  throw Invalid_Argument("error position larger than code size");
154  }
155  result[pos / 8] |= (1 << (pos % 8));
156  }
157 
158  error_mask = result;
159  }
160 
161 /**
162 * @p p_err_pos_len must point to the available length of @p error_pos on input, the
163 * function will set it to the actual number of errors returned in the @p error_pos
164 * array */
166  secure_vector<gf2m> & error_pos,
167  const uint8_t *ciphertext, uint32_t ciphertext_len,
168  const McEliece_PrivateKey & key)
169  {
170 
171  uint32_t dimension = key.get_dimension();
172  uint32_t codimension = key.get_codimension();
173  uint32_t t = key.get_goppa_polyn().get_degree();
174  polyn_gf2m syndrome_polyn(key.get_goppa_polyn().get_sp_field()); // init as zero polyn
175  const unsigned unused_pt_bits = dimension % 8;
176  const uint8_t unused_pt_bits_mask = (1 << unused_pt_bits) - 1;
177 
178  if(ciphertext_len != (key.get_code_length()+7)/8)
179  {
180  throw Invalid_Argument("wrong size of McEliece ciphertext");
181  }
182  uint32_t cleartext_len = (key.get_message_word_bit_length()+7)/8;
183 
184  if(cleartext_len != bit_size_to_byte_size(dimension))
185  {
186  throw Invalid_Argument("mce-decryption: wrong length of cleartext buffer");
187  }
188 
189  secure_vector<uint32_t> syndrome_vec(bit_size_to_32bit_size(codimension));
190  matrix_arr_mul(key.get_H_coeffs(),
191  key.get_code_length(),
192  bit_size_to_32bit_size(codimension),
193  ciphertext,
194  syndrome_vec.data(), syndrome_vec.size());
195 
196  secure_vector<uint8_t> syndrome_byte_vec(bit_size_to_byte_size(codimension));
197  uint32_t syndrome_byte_vec_size = syndrome_byte_vec.size();
198  for(uint32_t i = 0; i < syndrome_byte_vec_size; i++)
199  {
200  syndrome_byte_vec[i] = static_cast<uint8_t>(syndrome_vec[i/4] >> (8* (i % 4)));
201  }
202 
203  syndrome_polyn = polyn_gf2m(t-1, syndrome_byte_vec.data(), bit_size_to_byte_size(codimension), key.get_goppa_polyn().get_sp_field());
204 
205  syndrome_polyn.get_degree();
206  error_pos = goppa_decode(syndrome_polyn, key.get_goppa_polyn(), key.get_sqrtmod(), key.get_Linv());
207 
208  uint32_t nb_err = error_pos.size();
209 
210  secure_vector<uint8_t> cleartext(cleartext_len);
211  copy_mem(cleartext.data(), ciphertext, cleartext_len);
212 
213  for(uint32_t i = 0; i < nb_err; i++)
214  {
215  gf2m current = error_pos[i];
216 
217  if(current >= cleartext_len * 8)
218  {
219  // an invalid position, this shouldn't happen
220  continue;
221  }
222  cleartext[current / 8] ^= (1 << (current % 8));
223  }
224 
225  if(unused_pt_bits)
226  {
227  cleartext[cleartext_len - 1] &= unused_pt_bits_mask;
228  }
229 
230  return cleartext;
231  }
232 
233 }
std::vector< polyn_gf2m > const & get_sqrtmod() const
Definition: mceliece.h:102
void mceliece_decrypt(secure_vector< uint8_t > &plaintext_out, secure_vector< uint8_t > &error_mask_out, const secure_vector< uint8_t > &ciphertext, const McEliece_PrivateKey &key)
Definition: goppa_code.cpp:129
int get_degree() const
Definition: polyn_gf2m.cpp:228
uint32_t get_dimension() const
Definition: mceliece.h:104
polyn_gf2m const & get_goppa_polyn() const
Definition: mceliece.h:99
size_t bit_size_to_32bit_size(uint32_t bit_size)
std::vector< uint32_t > const & get_H_coeffs() const
Definition: mceliece.h:100
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
uint32_t get_codimension() const
Definition: mceliece.h:106
size_t bit_size_to_byte_size(uint32_t bit_size)
gf2m gray_to_lex(gf2m gray)
std::vector< gf2m > const & get_Linv() const
Definition: mceliece.h:101
uint16_t gf2m
Definition: gf2m_small_m.h:20
secure_vector< gf2m > find_roots_gf2m_decomp(const polyn_gf2m &polyn, uint32_t code_length)
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:122
Definition: alg_id.cpp:13
uint32_t get_code_length() const
Definition: mceliece.h:50
uint32_t code_length
static std::pair< polyn_gf2m, polyn_gf2m > eea_with_coefficients(const polyn_gf2m &p, const polyn_gf2m &g, int break_deg)
Definition: polyn_gf2m.cpp:448
uint32_t get_message_word_bit_length() const
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
std::shared_ptr< GF2m_Field > get_sp_field() const
Definition: polyn_gf2m.h:75