Coverage Report

Created: 2020-05-23 13:54

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