Botan  1.11.15
src/lib/pubkey/mce/mceliece.cpp
Go to the documentation of this file.
00001 /**
00002  * (C) Copyright Projet SECRET, INRIA, Rocquencourt
00003  * (C) Bhaskar Biswas and  Nicolas Sendrier
00004  *
00005  * (C) 2014 cryptosource GmbH
00006  * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
00007  *
00008  * Botan is released under the Simplified BSD License (see license.txt)
00009  *
00010  */
00011 
00012 #include <botan/mceliece.h>
00013 #include <botan/mceliece_key.h>
00014 #include <botan/internal/code_based_key_gen.h>
00015 #include <botan/polyn_gf2m.h>
00016 #include <botan/code_based_util.h>
00017 #include <botan/goppa_code.h>
00018 #include <botan/internal/bit_ops.h>
00019 #include <botan/internal/xor_buf.h>
00020 
00021 namespace Botan {
00022 
00023 namespace {
00024 
00025 void concat_vectors(byte* x, const byte* a, const byte* b, u32bit dimension, u32bit codimension)
00026    {
00027    if(dimension % 8 == 0)
00028       {
00029       const size_t dim_bytes = bit_size_to_byte_size(dimension);
00030       copy_mem(x, a, dim_bytes);
00031       copy_mem(x + dim_bytes, b, bit_size_to_byte_size(codimension));
00032       }
00033    else
00034       {
00035       u32bit i, j, k, l;
00036       i = dimension - 8 * (dimension/ 8);
00037       j = 8 - i;
00038       l = dimension / 8;
00039       copy_mem(x, a, 1 * (dimension / 8));
00040       x[l] = static_cast<byte>(a[l] & ((1 << i) - 1));
00041 
00042       for(k = 0; k < codimension / 8; ++k)
00043          {
00044          x[l] ^= static_cast<byte>(b[k] << i);
00045          ++l;
00046          x[l] = static_cast<byte>(b[k] >> j);
00047          }
00048       x[l] ^= static_cast<byte>(b[k] << i);
00049       }
00050    }
00051 
00052 std::vector<byte> mult_by_pubkey(const byte *cleartext,
00053                                  std::vector<byte> const& public_matrix,
00054                                  u32bit code_length, u32bit t)
00055    {
00056    std::vector<byte> ciphertext(code_length);
00057    u32bit i, j;
00058    u32bit ext_deg = ceil_log2(code_length);
00059    u32bit codimension = ext_deg * t;
00060    u32bit dimension = code_length - codimension;
00061    std::vector<byte> cR(bit_size_to_32bit_size(codimension)* sizeof(u32bit));
00062 
00063    const byte* pt = &public_matrix[0];
00064 
00065    for(i = 0; i < dimension / 8; ++i)
00066       {
00067       for(j = 0; j < 8; ++j)
00068          {
00069          if(cleartext[i] & (1 << j))
00070             {
00071             xor_buf(&cR[0], pt, cR.size());
00072             }
00073          pt += bit_size_to_32bit_size(codimension) * sizeof(u32bit);
00074          }
00075       }
00076 
00077    for(j = 0; j < dimension % 8 ; ++j)
00078       {
00079       if(cleartext[i] & (1 << j))
00080          {
00081          xor_buf(&cR[0], pt, bit_size_to_byte_size(codimension));
00082          }
00083       pt += bit_size_to_32bit_size(codimension) * sizeof(u32bit);
00084       }
00085 
00086    concat_vectors( &ciphertext[0],  cleartext, &cR[0], dimension, codimension);
00087    return ciphertext;
00088    }
00089 
00090 }
00091 
00092 secure_vector<gf2m> create_random_error_positions(unsigned code_length,
00093                                                   unsigned error_weight,
00094                                                   RandomNumberGenerator& rng)
00095    {
00096    secure_vector<gf2m> result(error_weight);
00097    gf2m i;
00098    for(i = 0; i < result.size(); i++)
00099       {
00100       unsigned j;
00101       char try_again = 0;
00102       do
00103          {
00104          try_again = 0;
00105          gf2m new_pos = random_code_element(code_length, rng);
00106          for(j = 0; j < i; j++)
00107             {
00108             if(new_pos == result[j])
00109                {
00110                try_again = 1;
00111                break;
00112                }
00113             }
00114          result[i] = new_pos;
00115          } while(try_again);
00116       }
00117    return result;
00118    }
00119 
00120 McEliece_Private_Operation::McEliece_Private_Operation(const McEliece_PrivateKey& private_key)
00121    :m_priv_key(private_key)
00122    {
00123    }
00124 
00125 secure_vector<byte> McEliece_Private_Operation::decrypt(const byte msg[], size_t msg_len)
00126    {
00127    secure_vector<gf2m> err_pos;
00128 
00129    secure_vector<byte> plaintext = mceliece_decrypt(
00130       err_pos,
00131       msg, msg_len,
00132       m_priv_key
00133       );
00134 
00135    return mceliece_message_parts(err_pos, plaintext, m_priv_key.get_code_length()).get_concat();
00136    }
00137 
00138 McEliece_Public_Operation::McEliece_Public_Operation(const McEliece_PublicKey& public_key, u32bit the_code_length)
00139    :m_pub_key(public_key),
00140     m_code_length(the_code_length)
00141    {}
00142 
00143 secure_vector<byte> McEliece_Public_Operation::encrypt(const byte msg[], size_t msg_len, RandomNumberGenerator&)
00144    {
00145    mceliece_message_parts parts(msg, msg_len, m_pub_key.get_code_length());
00146    secure_vector<gf2m> err_pos = parts.get_error_positions();
00147    secure_vector<byte> message_word = parts.get_message_word();
00148    secure_vector<byte> ciphertext((m_pub_key.get_code_length()+7)/8);
00149 
00150 
00151    std::vector<byte> ciphertext_tmp = mceliece_encrypt( message_word,  m_pub_key.get_public_matrix(), err_pos, m_code_length);
00152 
00153    copy_mem(&ciphertext[0], &ciphertext_tmp[0], ciphertext.size());
00154    return ciphertext;
00155    }
00156 
00157 std::vector<byte> mceliece_encrypt(const secure_vector<byte> & cleartext,
00158                                    std::vector<byte> const& public_matrix,
00159                                    const secure_vector<gf2m> & err_pos,
00160                                    u32bit code_length)
00161    {
00162    std::vector<byte> ciphertext = mult_by_pubkey(&cleartext[0], public_matrix, code_length, err_pos.size());
00163 
00164    // flip t error positions
00165    for(size_t i = 0; i < err_pos.size(); ++i)
00166       {
00167       ciphertext[err_pos[i] / 8] ^= (1 << (err_pos[i] % 8));
00168       }
00169 
00170    return ciphertext;
00171    }
00172 
00173 }