Botan  1.11.15
src/lib/pubkey/mce/polyn_gf2m.h
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 #ifndef BOTAN_POLYN_GF2M_H__
00013 #define BOTAN_POLYN_GF2M_H__
00014 
00015 #include <botan/gf2m_small_m.h>
00016 #include <botan/rng.h>
00017 #include <memory>
00018 #include <utility>
00019 
00020 namespace Botan {
00021 
00022 using namespace gf2m_small_m;
00023 
00024 struct polyn_gf2m
00025    {
00026    public:
00027       /**
00028       * create a zero polynomial:
00029       */
00030       polyn_gf2m( std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field );
00031 
00032       polyn_gf2m()
00033          :m_deg(-1)
00034          {};
00035 
00036       polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field );
00037 
00038       polyn_gf2m& operator=(const polyn_gf2m&) = default;
00039 
00040       bool operator==(const polyn_gf2m & other) const ;
00041 
00042       bool operator!=(const polyn_gf2m & other) const { return !(*this == other); };
00043 
00044       polyn_gf2m(polyn_gf2m&& other)
00045          {
00046          this->swap(other);
00047          };
00048 
00049       polyn_gf2m & operator=(polyn_gf2m&& other)
00050          {
00051          if(this != &other)
00052             {
00053             this->swap(other);
00054             }
00055          return *this;
00056          }
00057 
00058       void swap(polyn_gf2m& other);
00059 
00060       secure_vector<byte> encode() const;
00061       /**
00062       * create zero polynomial with reservation of space for a degree d polynomial
00063       */
00064       polyn_gf2m(int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field);
00065 
00066       polyn_gf2m(polyn_gf2m const& other);
00067       /**
00068       * create zero polynomial with allocated size determined by specified degree d:
00069       */
00070 
00071       /**
00072       * random irreducible polynomial of degree t
00073       */
00074       polyn_gf2m(int t, RandomNumberGenerator& rng, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field);
00075 
00076       std::shared_ptr<gf2m_small_m::Gf2m_Field> get_sp_field() const
00077          { return msp_field; };
00078 
00079       gf2m& operator[](size_t i) { return coeff[i]; };
00080 
00081       gf2m operator[](size_t i) const { return coeff[i]; }
00082 
00083       gf2m get_lead_coef() const { return coeff[m_deg]; }
00084 
00085       gf2m get_coef(u32bit i) const { return coeff[i]; }
00086 
00087       inline void set_coef(u32bit i, gf2m v)
00088          {
00089          coeff[i] = v;
00090          };
00091 
00092       inline void add_to_coef(u32bit i, gf2m v)
00093          {
00094          coeff[i] = coeff[i] ^ v;
00095          }
00096 
00097       std::string to_string() const;
00098 
00099       /** decode a polynomial from memory: **/
00100       polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field);
00101       // remove one! ^v!
00102       /**
00103       *  create a polynomial from memory area (encoded)
00104       */
00105       polyn_gf2m(int degree, const unsigned  char* mem, u32bit mem_byte_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field);
00106 
00107       void encode(u32bit min_numo_coeffs, byte* mem, u32bit mem_len) const;
00108 
00109       int get_degree() const;
00110 
00111       /**
00112       * determine the degree in a timing secure manner. the timing of this function
00113       * only depends on the number of allocated coefficients, not on the actual
00114       * degree
00115       */
00116       int calc_degree_secure() const;
00117 
00118       void degppf(const polyn_gf2m & g, int* p_result);
00119 
00120       static std::vector<polyn_gf2m> sqmod_init(const polyn_gf2m & g);
00121 
00122       static std::vector<polyn_gf2m> sqrt_mod_init(const polyn_gf2m & g);
00123 
00124 
00125       polyn_gf2m sqmod(const std::vector<polyn_gf2m> & sq, int d);
00126       void set_to_zero();
00127       gf2m eval(gf2m a);
00128 
00129       static std::pair<polyn_gf2m, polyn_gf2m> eea_with_coefficients(const polyn_gf2m & p,
00130                                                                      const polyn_gf2m & g,
00131                                                                      int break_deg);
00132 
00133       void patchup_deg_secure( u32bit trgt_deg, volatile gf2m patch_elem);
00134 
00135    private:
00136 
00137       void set_degree(int d) { m_deg = d; }
00138 
00139       void poly_shiftmod( const polyn_gf2m & g);
00140       void realloc(u32bit new_size);
00141       static polyn_gf2m gcd(polyn_gf2m const& p1, polyn_gf2m const& p2);
00142 
00143       /**
00144       * destructive:
00145       */
00146       static void remainder(polyn_gf2m & p, const polyn_gf2m & g);
00147 
00148       static polyn_gf2m gcd_aux(polyn_gf2m& p1, polyn_gf2m& p2);
00149    public:
00150       int m_deg;
00151       secure_vector<gf2m> coeff;
00152       std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field;
00153    };
00154 
00155 gf2m random_code_element(unsigned code_length, RandomNumberGenerator& rng);
00156 
00157 std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n);
00158 
00159 }
00160 
00161 #endif