/src/botan/src/lib/pubkey/mce/mceliece_key.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 | | * (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 | | #include <botan/internal/polyn_gf2m.h> |
15 | | #include <botan/internal/mce_internal.h> |
16 | | #include <botan/internal/bit_ops.h> |
17 | | #include <botan/internal/code_based_util.h> |
18 | | #include <botan/internal/pk_ops_impl.h> |
19 | | #include <botan/internal/loadstor.h> |
20 | | #include <botan/der_enc.h> |
21 | | #include <botan/ber_dec.h> |
22 | | #include <botan/rng.h> |
23 | | |
24 | | namespace Botan { |
25 | | |
26 | 0 | McEliece_PrivateKey::McEliece_PrivateKey(const McEliece_PrivateKey&) = default; Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::McEliece_PrivateKey const&) Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::McEliece_PrivateKey const&) |
27 | 0 | McEliece_PrivateKey::McEliece_PrivateKey(McEliece_PrivateKey&&) = default; Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::McEliece_PrivateKey&&) Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::McEliece_PrivateKey&&) |
28 | 0 | McEliece_PrivateKey& McEliece_PrivateKey::operator=(const McEliece_PrivateKey&) = default; |
29 | 0 | McEliece_PrivateKey& McEliece_PrivateKey::operator=(McEliece_PrivateKey&&) = default; |
30 | | |
31 | | McEliece_PrivateKey::McEliece_PrivateKey(polyn_gf2m const& goppa_polyn, |
32 | | std::vector<uint32_t> const& parity_check_matrix_coeffs, |
33 | | std::vector<polyn_gf2m> const& square_root_matrix, |
34 | | std::vector<gf2m> const& inverse_support, |
35 | | std::vector<uint8_t> const& public_matrix) : |
36 | | McEliece_PublicKey(public_matrix, goppa_polyn.get_degree(), inverse_support.size()), |
37 | | m_g{goppa_polyn}, |
38 | | m_sqrtmod(square_root_matrix), |
39 | | m_Linv(inverse_support), |
40 | | m_coeffs(parity_check_matrix_coeffs), |
41 | | m_codimension(static_cast<size_t>(ceil_log2(inverse_support.size())) * goppa_polyn.get_degree()), |
42 | | m_dimension(inverse_support.size() - m_codimension) |
43 | 0 | { |
44 | 0 | } Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::polyn_gf2m const&, std::__1::vector<unsigned int, std::__1::allocator<unsigned int> > const&, std::__1::vector<Botan::polyn_gf2m, std::__1::allocator<Botan::polyn_gf2m> > const&, std::__1::vector<unsigned short, std::__1::allocator<unsigned short> > const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::polyn_gf2m const&, std::__1::vector<unsigned int, std::__1::allocator<unsigned int> > const&, std::__1::vector<Botan::polyn_gf2m, std::__1::allocator<Botan::polyn_gf2m> > const&, std::__1::vector<unsigned short, std::__1::allocator<unsigned short> > const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) |
45 | | |
46 | | McEliece_PrivateKey::McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t) |
47 | 0 | { |
48 | 0 | uint32_t ext_deg = ceil_log2(code_length); |
49 | 0 | *this = generate_mceliece_key(rng, ext_deg, code_length, t); |
50 | 0 | } Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::RandomNumberGenerator&, unsigned long, unsigned long) Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::RandomNumberGenerator&, unsigned long, unsigned long) |
51 | | |
52 | 0 | McEliece_PrivateKey::~McEliece_PrivateKey() = default; |
53 | | |
54 | | const polyn_gf2m& McEliece_PrivateKey::get_goppa_polyn() const |
55 | 0 | { |
56 | 0 | return m_g[0]; |
57 | 0 | } |
58 | | |
59 | | size_t McEliece_PublicKey::get_message_word_bit_length() const |
60 | 0 | { |
61 | 0 | size_t codimension = ceil_log2(m_code_length) * m_t; |
62 | 0 | return m_code_length - codimension; |
63 | 0 | } |
64 | | |
65 | | secure_vector<uint8_t> McEliece_PublicKey::random_plaintext_element(RandomNumberGenerator& rng) const |
66 | 0 | { |
67 | 0 | const size_t bits = get_message_word_bit_length(); |
68 | |
|
69 | 0 | secure_vector<uint8_t> plaintext((bits+7)/8); |
70 | 0 | rng.randomize(plaintext.data(), plaintext.size()); |
71 | | |
72 | | // unset unused bits in the last plaintext byte |
73 | 0 | if(uint32_t used = bits % 8) |
74 | 0 | { |
75 | 0 | const uint8_t mask = (1 << used) - 1; |
76 | 0 | plaintext[plaintext.size() - 1] &= mask; |
77 | 0 | } |
78 | |
|
79 | 0 | return plaintext; |
80 | 0 | } |
81 | | |
82 | | AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const |
83 | 0 | { |
84 | 0 | return AlgorithmIdentifier(get_oid(), AlgorithmIdentifier::USE_EMPTY_PARAM); |
85 | 0 | } |
86 | | |
87 | | std::vector<uint8_t> McEliece_PublicKey::public_key_bits() const |
88 | 0 | { |
89 | 0 | std::vector<uint8_t> output; |
90 | 0 | DER_Encoder(output) |
91 | 0 | .start_sequence() |
92 | 0 | .start_sequence() |
93 | 0 | .encode(static_cast<size_t>(get_code_length())) |
94 | 0 | .encode(static_cast<size_t>(get_t())) |
95 | 0 | .end_cons() |
96 | 0 | .encode(m_public_matrix, ASN1_Type::OctetString) |
97 | 0 | .end_cons(); |
98 | 0 | return output; |
99 | 0 | } |
100 | | |
101 | | size_t McEliece_PublicKey::key_length() const |
102 | 0 | { |
103 | 0 | return m_code_length; |
104 | 0 | } |
105 | | |
106 | | size_t McEliece_PublicKey::estimated_strength() const |
107 | 0 | { |
108 | 0 | return mceliece_work_factor(m_code_length, m_t); |
109 | 0 | } |
110 | | |
111 | | McEliece_PublicKey::McEliece_PublicKey(const std::vector<uint8_t>& key_bits) |
112 | 0 | { |
113 | 0 | BER_Decoder dec(key_bits); |
114 | 0 | size_t n; |
115 | 0 | size_t t; |
116 | 0 | dec.start_sequence() |
117 | 0 | .start_sequence() |
118 | 0 | .decode(n) |
119 | 0 | .decode(t) |
120 | 0 | .end_cons() |
121 | 0 | .decode(m_public_matrix, ASN1_Type::OctetString) |
122 | 0 | .end_cons(); |
123 | 0 | m_t = t; |
124 | 0 | m_code_length = n; |
125 | 0 | } Unexecuted instantiation: Botan::McEliece_PublicKey::McEliece_PublicKey(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Unexecuted instantiation: Botan::McEliece_PublicKey::McEliece_PublicKey(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) |
126 | | |
127 | | secure_vector<uint8_t> McEliece_PrivateKey::private_key_bits() const |
128 | 0 | { |
129 | 0 | DER_Encoder enc; |
130 | 0 | enc.start_sequence() |
131 | 0 | .start_sequence() |
132 | 0 | .encode(static_cast<size_t>(get_code_length())) |
133 | 0 | .encode(static_cast<size_t>(get_t())) |
134 | 0 | .end_cons() |
135 | 0 | .encode(m_public_matrix, ASN1_Type::OctetString) |
136 | 0 | .encode(m_g[0].encode(), ASN1_Type::OctetString); // g as octet string |
137 | 0 | enc.start_sequence(); |
138 | 0 | for(size_t i = 0; i < m_sqrtmod.size(); i++) |
139 | 0 | { |
140 | 0 | enc.encode(m_sqrtmod[i].encode(), ASN1_Type::OctetString); |
141 | 0 | } |
142 | 0 | enc.end_cons(); |
143 | 0 | secure_vector<uint8_t> enc_support; |
144 | |
|
145 | 0 | for(uint16_t Linv : m_Linv) |
146 | 0 | { |
147 | 0 | enc_support.push_back(get_byte<0>(Linv)); |
148 | 0 | enc_support.push_back(get_byte<1>(Linv)); |
149 | 0 | } |
150 | 0 | enc.encode(enc_support, ASN1_Type::OctetString); |
151 | 0 | secure_vector<uint8_t> enc_H; |
152 | 0 | for(uint32_t coef : m_coeffs) |
153 | 0 | { |
154 | 0 | enc_H.push_back(get_byte<0>(coef)); |
155 | 0 | enc_H.push_back(get_byte<1>(coef)); |
156 | 0 | enc_H.push_back(get_byte<2>(coef)); |
157 | 0 | enc_H.push_back(get_byte<3>(coef)); |
158 | 0 | } |
159 | 0 | enc.encode(enc_H, ASN1_Type::OctetString); |
160 | 0 | enc.end_cons(); |
161 | 0 | return enc.get_contents(); |
162 | 0 | } |
163 | | |
164 | | bool McEliece_PrivateKey::check_key(RandomNumberGenerator& rng, bool) const |
165 | 0 | { |
166 | 0 | const secure_vector<uint8_t> plaintext = this->random_plaintext_element(rng); |
167 | |
|
168 | 0 | secure_vector<uint8_t> ciphertext; |
169 | 0 | secure_vector<uint8_t> errors; |
170 | 0 | mceliece_encrypt(ciphertext, errors, plaintext, *this, rng); |
171 | |
|
172 | 0 | secure_vector<uint8_t> plaintext_out; |
173 | 0 | secure_vector<uint8_t> errors_out; |
174 | 0 | mceliece_decrypt(plaintext_out, errors_out, ciphertext, *this); |
175 | |
|
176 | 0 | if(errors != errors_out || plaintext != plaintext_out) |
177 | 0 | return false; |
178 | | |
179 | 0 | return true; |
180 | 0 | } |
181 | | |
182 | | McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<uint8_t>& key_bits) |
183 | 0 | { |
184 | 0 | size_t n, t; |
185 | 0 | secure_vector<uint8_t> enc_g; |
186 | 0 | BER_Decoder dec_base(key_bits); |
187 | 0 | BER_Decoder dec = dec_base.start_sequence() |
188 | 0 | .start_sequence() |
189 | 0 | .decode(n) |
190 | 0 | .decode(t) |
191 | 0 | .end_cons() |
192 | 0 | .decode(m_public_matrix, ASN1_Type::OctetString) |
193 | 0 | .decode(enc_g, ASN1_Type::OctetString); |
194 | |
|
195 | 0 | if(t == 0 || n == 0) |
196 | 0 | throw Decoding_Error("invalid McEliece parameters"); |
197 | | |
198 | 0 | uint32_t ext_deg = ceil_log2(n); |
199 | 0 | m_code_length = n; |
200 | 0 | m_t = t; |
201 | 0 | m_codimension = (ext_deg * t); |
202 | 0 | m_dimension = (n - m_codimension); |
203 | |
|
204 | 0 | auto sp_field = std::make_shared<GF2m_Field>(ext_deg); |
205 | 0 | m_g = { polyn_gf2m(enc_g, sp_field) }; |
206 | 0 | if(m_g[0].get_degree() != static_cast<int>(t)) |
207 | 0 | { |
208 | 0 | throw Decoding_Error("degree of decoded Goppa polynomial is incorrect"); |
209 | 0 | } |
210 | 0 | BER_Decoder dec2 = dec.start_sequence(); |
211 | 0 | for(uint32_t i = 0; i < t/2; i++) |
212 | 0 | { |
213 | 0 | secure_vector<uint8_t> sqrt_enc; |
214 | 0 | dec2.decode(sqrt_enc, ASN1_Type::OctetString); |
215 | 0 | while(sqrt_enc.size() < (t*2)) |
216 | 0 | { |
217 | | // ensure that the length is always t |
218 | 0 | sqrt_enc.push_back(0); |
219 | 0 | sqrt_enc.push_back(0); |
220 | 0 | } |
221 | 0 | if(sqrt_enc.size() != t*2) |
222 | 0 | { |
223 | 0 | throw Decoding_Error("length of square root polynomial entry is too large"); |
224 | 0 | } |
225 | 0 | m_sqrtmod.push_back(polyn_gf2m(sqrt_enc, sp_field)); |
226 | 0 | } |
227 | 0 | secure_vector<uint8_t> enc_support; |
228 | 0 | BER_Decoder dec3 = dec2.end_cons() |
229 | 0 | .decode(enc_support, ASN1_Type::OctetString); |
230 | 0 | if(enc_support.size() % 2) |
231 | 0 | { |
232 | 0 | throw Decoding_Error("encoded support has odd length"); |
233 | 0 | } |
234 | 0 | if(enc_support.size() / 2 != n) |
235 | 0 | { |
236 | 0 | throw Decoding_Error("encoded support has length different from code length"); |
237 | 0 | } |
238 | 0 | for(uint32_t i = 0; i < n*2; i+=2) |
239 | 0 | { |
240 | 0 | gf2m el = (enc_support[i] << 8) | enc_support[i+1]; |
241 | 0 | m_Linv.push_back(el); |
242 | 0 | } |
243 | 0 | secure_vector<uint8_t> enc_H; |
244 | 0 | dec3.decode(enc_H, ASN1_Type::OctetString) |
245 | 0 | .end_cons(); |
246 | 0 | if(enc_H.size() % 4) |
247 | 0 | { |
248 | 0 | throw Decoding_Error("encoded parity check matrix has length which is not a multiple of four"); |
249 | 0 | } |
250 | 0 | if(enc_H.size() / 4 != bit_size_to_32bit_size(m_codimension) * m_code_length) |
251 | 0 | { |
252 | 0 | throw Decoding_Error("encoded parity check matrix has wrong length"); |
253 | 0 | } |
254 | | |
255 | 0 | for(uint32_t i = 0; i < enc_H.size(); i+=4) |
256 | 0 | { |
257 | 0 | uint32_t coeff = (enc_H[i] << 24) | (enc_H[i+1] << 16) | (enc_H[i+2] << 8) | enc_H[i+3]; |
258 | 0 | m_coeffs.push_back(coeff); |
259 | 0 | } |
260 | |
|
261 | 0 | } Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) |
262 | | |
263 | | bool McEliece_PrivateKey::operator==(const McEliece_PrivateKey & other) const |
264 | 0 | { |
265 | 0 | if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other)) |
266 | 0 | { |
267 | 0 | return false; |
268 | 0 | } |
269 | 0 | if(m_g != other.m_g) |
270 | 0 | { |
271 | 0 | return false; |
272 | 0 | } |
273 | | |
274 | 0 | if( m_sqrtmod != other.m_sqrtmod) |
275 | 0 | { |
276 | 0 | return false; |
277 | 0 | } |
278 | 0 | if( m_Linv != other.m_Linv) |
279 | 0 | { |
280 | 0 | return false; |
281 | 0 | } |
282 | 0 | if( m_coeffs != other.m_coeffs) |
283 | 0 | { |
284 | 0 | return false; |
285 | 0 | } |
286 | | |
287 | 0 | if(m_codimension != other.m_codimension || m_dimension != other.m_dimension) |
288 | 0 | { |
289 | 0 | return false; |
290 | 0 | } |
291 | | |
292 | 0 | return true; |
293 | 0 | } |
294 | | |
295 | | std::unique_ptr<Public_Key> McEliece_PrivateKey::public_key() const |
296 | 0 | { |
297 | 0 | return std::make_unique<McEliece_PublicKey>( |
298 | 0 | get_public_matrix(), get_t(), get_code_length()); |
299 | 0 | } |
300 | | |
301 | | bool McEliece_PublicKey::operator==(const McEliece_PublicKey& other) const |
302 | 0 | { |
303 | 0 | if(m_public_matrix != other.m_public_matrix) |
304 | 0 | { |
305 | 0 | return false; |
306 | 0 | } |
307 | 0 | if(m_t != other.m_t) |
308 | 0 | { |
309 | 0 | return false; |
310 | 0 | } |
311 | 0 | if( m_code_length != other.m_code_length) |
312 | 0 | { |
313 | 0 | return false; |
314 | 0 | } |
315 | 0 | return true; |
316 | 0 | } |
317 | | |
318 | | namespace { |
319 | | |
320 | | class MCE_KEM_Encryptor final : public PK_Ops::KEM_Encryption_with_KDF |
321 | | { |
322 | | public: |
323 | | |
324 | | MCE_KEM_Encryptor(const McEliece_PublicKey& key, |
325 | | const std::string& kdf) : |
326 | 0 | KEM_Encryption_with_KDF(kdf), m_key(key) {} |
327 | | |
328 | | private: |
329 | | void raw_kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key, |
330 | | secure_vector<uint8_t>& raw_shared_key, |
331 | | Botan::RandomNumberGenerator& rng) override |
332 | 0 | { |
333 | 0 | secure_vector<uint8_t> plaintext = m_key.random_plaintext_element(rng); |
334 | |
|
335 | 0 | secure_vector<uint8_t> ciphertext, error_mask; |
336 | 0 | mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng); |
337 | |
|
338 | 0 | raw_shared_key.clear(); |
339 | 0 | raw_shared_key += plaintext; |
340 | 0 | raw_shared_key += error_mask; |
341 | |
|
342 | 0 | out_encapsulated_key.swap(ciphertext); |
343 | 0 | } |
344 | | |
345 | | const McEliece_PublicKey& m_key; |
346 | | }; |
347 | | |
348 | | class MCE_KEM_Decryptor final : public PK_Ops::KEM_Decryption_with_KDF |
349 | | { |
350 | | public: |
351 | | |
352 | | MCE_KEM_Decryptor(const McEliece_PrivateKey& key, |
353 | | const std::string& kdf) : |
354 | 0 | KEM_Decryption_with_KDF(kdf), m_key(key) {} |
355 | | |
356 | | private: |
357 | | secure_vector<uint8_t> |
358 | | raw_kem_decrypt(const uint8_t encap_key[], size_t len) override |
359 | 0 | { |
360 | 0 | secure_vector<uint8_t> plaintext, error_mask; |
361 | 0 | mceliece_decrypt(plaintext, error_mask, encap_key, len, m_key); |
362 | |
|
363 | 0 | secure_vector<uint8_t> output; |
364 | 0 | output.reserve(plaintext.size() + error_mask.size()); |
365 | 0 | output.insert(output.end(), plaintext.begin(), plaintext.end()); |
366 | 0 | output.insert(output.end(), error_mask.begin(), error_mask.end()); |
367 | 0 | return output; |
368 | 0 | } |
369 | | |
370 | | const McEliece_PrivateKey& m_key; |
371 | | }; |
372 | | |
373 | | } |
374 | | |
375 | | std::unique_ptr<PK_Ops::KEM_Encryption> |
376 | | McEliece_PublicKey::create_kem_encryption_op(RandomNumberGenerator& /*rng*/, |
377 | | const std::string& params, |
378 | | const std::string& provider) const |
379 | 0 | { |
380 | 0 | if(provider == "base" || provider.empty()) |
381 | 0 | return std::make_unique<MCE_KEM_Encryptor>(*this, params); |
382 | 0 | throw Provider_Not_Found(algo_name(), provider); |
383 | 0 | } |
384 | | |
385 | | std::unique_ptr<PK_Ops::KEM_Decryption> |
386 | | McEliece_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& /*rng*/, |
387 | | const std::string& params, |
388 | | const std::string& provider) const |
389 | 0 | { |
390 | 0 | if(provider == "base" || provider.empty()) |
391 | 0 | return std::make_unique<MCE_KEM_Decryptor>(*this, params); |
392 | 0 | throw Provider_Not_Found(algo_name(), provider); |
393 | 0 | } |
394 | | |
395 | | } |
396 | | |
397 | | |