Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 size_t u_deg = u.get_degree();
94 for(size_t i = 0; i <= u_deg; ++i)
95 {
96 sigma.set_coef(2*i, sp_field->gf_square(u.get_coef(i)));
97 }
98
99 const int v_deg = v.get_degree();
100 BOTAN_ASSERT(v_deg > 0, "Valid degree");
101 for(int i = 0; i <= v_deg; ++i)
102 {
103 sigma.set_coef(2*i+1, sp_field->gf_square(v.get_coef(i)));
104 }
105
106 secure_vector<gf2m> res = find_roots_gf2m_decomp(sigma, code_length);
107 size_t d = res.size();
108
109 secure_vector<gf2m> result(d);
110 for(uint32_t i = 0; i < d; ++i)
111 {
112 gf2m current = res[i];
113
114 gf2m tmp;
115 tmp = gray_to_lex(current);
116 if(tmp >= code_length) /* invalid root */
117 {
118 result[i] = i;
119 }
120 result[i] = Linv[tmp];
121 }
122
123 return result;
124 }
125 }
126
127 void mceliece_decrypt(secure_vector<uint8_t>& plaintext_out,
128 secure_vector<uint8_t>& error_mask_out,
129 const secure_vector<uint8_t>& ciphertext,
130 const McEliece_PrivateKey& key)
131 {
132 mceliece_decrypt(plaintext_out, error_mask_out, ciphertext.data(), ciphertext.size(), key);
133 }
134
135 void mceliece_decrypt(
136 secure_vector<uint8_t>& plaintext,
137 secure_vector<uint8_t> & error_mask,
138 const uint8_t ciphertext[],
139 size_t ciphertext_len,
140 const McEliece_PrivateKey & key)
141 {
142 secure_vector<gf2m> error_pos;
143 plaintext = mceliece_decrypt(error_pos, ciphertext, ciphertext_len, key);
144
145 const size_t code_length = key.get_code_length();
146 secure_vector<uint8_t> result((code_length+7)/8);
147 for(auto&& pos : error_pos)
148 {
149 if(pos > code_length)
150 {
151 throw Invalid_Argument("error position larger than code size");
152 }
153 result[pos / 8] |= (1 << (pos % 8));
154 }
155
156 error_mask = result;
157 }
158
159 /**
160 * @p p_err_pos_len must point to the available length of @p error_pos on input, the
161 * function will set it to the actual number of errors returned in the @p error_pos
162 * array */
163 secure_vector<uint8_t> mceliece_decrypt(
164 secure_vector<gf2m> & error_pos,
165 const uint8_t *ciphertext, uint32_t ciphertext_len,
166 const McEliece_PrivateKey & key)
167 {
168
169 uint32_t dimension = key.get_dimension();
170 uint32_t codimension = key.get_codimension();
171 uint32_t t = key.get_goppa_polyn().get_degree();
172 polyn_gf2m syndrome_polyn(key.get_goppa_polyn().get_sp_field()); // init as zero polyn
173 const unsigned unused_pt_bits = dimension % 8;
174 const uint8_t unused_pt_bits_mask = (1 << unused_pt_bits) - 1;
175
176 if(ciphertext_len != (key.get_code_length()+7)/8)
177 {
178 throw Invalid_Argument("wrong size of McEliece ciphertext");
179 }
180 uint32_t cleartext_len = (key.get_message_word_bit_length()+7)/8;
181
182 if(cleartext_len != bit_size_to_byte_size(dimension))
183 {
184 throw Invalid_Argument("mce-decryption: wrong length of cleartext buffer");
185 }
186
187 secure_vector<uint32_t> syndrome_vec(bit_size_to_32bit_size(codimension));
188 matrix_arr_mul(key.get_H_coeffs(),
189 key.get_code_length(),
190 bit_size_to_32bit_size(codimension),
191 ciphertext,
192 syndrome_vec.data(), syndrome_vec.size());
193
194 secure_vector<uint8_t> syndrome_byte_vec(bit_size_to_byte_size(codimension));
195 uint32_t syndrome_byte_vec_size = syndrome_byte_vec.size();
196 for(uint32_t i = 0; i < syndrome_byte_vec_size; i++)
197 {
198 syndrome_byte_vec[i] = syndrome_vec[i/4] >> (8* (i % 4));
199 }
200
201 syndrome_polyn = polyn_gf2m(t-1, syndrome_byte_vec.data(), bit_size_to_byte_size(codimension), key.get_goppa_polyn().get_sp_field());
202
203 syndrome_polyn.get_degree();
204 error_pos = goppa_decode(syndrome_polyn, key.get_goppa_polyn(), key.get_sqrtmod(), key.get_Linv());
205
206 uint32_t nb_err = error_pos.size();
207
208 secure_vector<uint8_t> cleartext(cleartext_len);
209 copy_mem(cleartext.data(), ciphertext, cleartext_len);
210
211 for(uint32_t i = 0; i < nb_err; i++)
212 {
213 gf2m current = error_pos[i];
214
215 if(current >= cleartext_len * 8)
216 {
217 // an invalid position, this shouldn't happen
218 continue;
219 }
220 cleartext[current / 8] ^= (1 << (current % 8));
221 }
222
223 if(unused_pt_bits)
224 {
225 cleartext[cleartext_len - 1] &= unused_pt_bits_mask;
226 }
227
228 return cleartext;
229 }
230
231 }
Botan::mceliece_decrypt
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:127
Botan::McEliece_PrivateKey
Definition: mceliece.h:70
Botan::Invalid_Argument
Definition: exceptn.h:34
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:230
Botan::bit_size_to_32bit_size
uint32_t bit_size_to_32bit_size(uint32_t bit_size)
Definition: code_based_util.h:50
Botan::bit_size_to_byte_size
uint32_t bit_size_to_byte_size(uint32_t bit_size)
Definition: code_based_util.h:45
Botan::McEliece_PrivateKey::get_goppa_polyn
polyn_gf2m const & get_goppa_polyn() const
Definition: mceliece.h:99
Botan::McEliece_PrivateKey::get_H_coeffs
std::vector< uint32_t > const & get_H_coeffs() const
Definition: mceliece.h:100
Botan::McEliece_PrivateKey::get_Linv
std::vector< gf2m > const & get_Linv() const
Definition: mceliece.h:101
Botan::McEliece_PrivateKey::get_dimension
uint32_t get_dimension() const
Definition: mceliece.h:104
Botan::McEliece_PublicKey::get_code_length
uint32_t get_code_length() const
Definition: mceliece.h:50
Botan::McEliece_PublicKey::get_message_word_bit_length
uint32_t get_message_word_bit_length() const
Definition: mceliece_key.cpp:44
Botan::polyn_gf2m::get_sp_field
std::shared_ptr< GF2m_Field > get_sp_field() const
Definition: polyn_gf2m.h:75
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:27
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
Botan::gray_to_lex
gf2m gray_to_lex(gf2m gray)
Definition: code_based_util.h:31
Botan::McEliece_PrivateKey::get_sqrtmod
std::vector< polyn_gf2m > const & get_sqrtmod() const
Definition: mceliece.h:102
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:20
Botan::find_roots_gf2m_decomp
secure_vector< gf2m > find_roots_gf2m_decomp(const polyn_gf2m &polyn, uint32_t code_length)
Definition: gf2m_rootfind_dcmp.cpp:311
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:68
Botan
Definition: alg_id.cpp:13
Botan::polyn_gf2m
Definition: polyn_gf2m.h:24
code_length
uint32_t code_length
Definition: gf2m_rootfind_dcmp.cpp:48
Botan::polyn_gf2m::eea_with_coefficients
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:450
Botan::McEliece_PrivateKey::get_codimension
uint32_t get_codimension() const
Definition: mceliece.h:106