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