Botan  2.12.1
Crypto and TLS for C++11
gf2m_small_m.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 #include <botan/gf2m_small_m.h>
12 #include <botan/exceptn.h>
13 #include <string>
14 
15 namespace Botan {
16 
17 #define MAX_EXT_DEG 16
18 
19 namespace {
20 
21 gf2m prim_poly[MAX_EXT_DEG + 1] = {
22  01, /* extension degree 0 (!) never used */
23  03, /* extension degree 1 (!) never used */
24  07, /* extension degree 2 */
25  013, /* extension degree 3 */
26  023, /* extension degree 4 */
27  045, /* extension degree 5 */
28  0103, /* extension degree 6 */
29  0203, /* extension degree 7 */
30  0435, /* extension degree 8 */
31  01041, /* extension degree 9 */
32  02011, /* extension degree 10 */
33  04005, /* extension degree 11 */
34  010123, /* extension degree 12 */
35  020033, /* extension degree 13 */
36  042103, /* extension degree 14 */
37  0100003, /* extension degree 15 */
38 };
39 
40 std::vector<gf2m> gf_exp_table(size_t deg, gf2m prime_poly)
41  {
42  // construct the table gf_exp[i]=alpha^i
43 
44  std::vector<gf2m> tab((1 << deg) + 1);
45 
46  tab[0] = 1;
47  for(size_t i = 1; i < tab.size(); ++i)
48  {
49  const bool overflow = tab[i - 1] >> (deg - 1);
50  tab[i] = (tab[i-1] << 1) ^ (overflow ? prime_poly : 0);
51  }
52 
53  return tab;
54  }
55 
56 const std::vector<gf2m>& exp_table(size_t deg)
57  {
58  static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
59 
60  if(deg < 2 || deg > MAX_EXT_DEG)
61  throw Invalid_Argument("GF2m_Field does not support degree " + std::to_string(deg));
62 
63  if(tabs[deg].empty())
64  tabs[deg] = gf_exp_table(deg, prim_poly[deg]);
65 
66  return tabs[deg];
67  }
68 
69 std::vector<gf2m> gf_log_table(size_t deg, const std::vector<gf2m>& exp)
70  {
71  std::vector<gf2m> tab(1 << deg);
72 
73  tab[0] = (1 << deg) - 1; // log of 0 is the order by convention
74  for(size_t i = 0; i < tab.size(); ++i)
75  {
76  tab[exp[i]] = static_cast<gf2m>(i);
77  }
78  return tab;
79  }
80 
81 const std::vector<gf2m>& log_table(size_t deg)
82  {
83  static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
84 
85  if(deg < 2 || deg > MAX_EXT_DEG)
86  throw Invalid_Argument("GF2m_Field does not support degree " + std::to_string(deg));
87 
88  if(tabs[deg].empty())
89  tabs[deg] = gf_log_table(deg, exp_table(deg));
90 
91  return tabs[deg];
92  }
93 
94 }
95 
96 uint32_t encode_gf2m(gf2m to_enc, uint8_t* mem)
97  {
98  mem[0] = to_enc >> 8;
99  mem[1] = to_enc & 0xFF;
100  return sizeof(to_enc);
101  }
102 
103 gf2m decode_gf2m(const uint8_t* mem)
104  {
105  gf2m result;
106  result = mem[0] << 8;
107  result |= mem[1];
108  return result;
109  }
110 
111 GF2m_Field::GF2m_Field(size_t extdeg) : m_gf_extension_degree(extdeg),
112  m_gf_multiplicative_order((1 << extdeg) - 1),
113  m_gf_log_table(log_table(m_gf_extension_degree)),
114  m_gf_exp_table(exp_table(m_gf_extension_degree))
115  {
116  }
117 
119  {
120  const int32_t sub_res = static_cast<int32_t>(gf_log(x) - static_cast<int32_t>(gf_log(y)));
121  const int32_t modq_res = static_cast<int32_t>(_gf_modq_1(sub_res));
122  const int32_t div_res = static_cast<int32_t>(x) ? static_cast<int32_t>(gf_exp(modq_res)) : 0;
123  return static_cast<gf2m>(div_res);
124  }
125 
126 // we suppose i >= 0. Par convention 0^0 = 1
127 gf2m GF2m_Field::gf_pow(gf2m x, int i) const
128  {
129  if (i == 0)
130  return 1;
131  else if (x == 0)
132  return 0;
133  else
134  {
135  // i mod (q-1)
136  while (i >> get_extension_degree())
137  i = (i & (gf_ord())) + (i >> get_extension_degree());
138  i *= gf_log(x);
139  while (i >> get_extension_degree())
140  i = (i & (gf_ord())) + (i >> get_extension_degree());
141  return gf_exp(i);
142  }
143  }
144 
145 }
gf2m gf_exp(gf2m i) const
Definition: gf2m_small_m.h:176
gf2m gf_ord() const
Definition: gf2m_small_m.h:186
GF2m_Field(size_t extdeg)
gf2m decode_gf2m(const uint8_t *mem)
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
gf2m gf_pow(gf2m x, int i) const
size_t get_extension_degree() const
Definition: gf2m_small_m.h:191
gf2m gf_log(gf2m i) const
Definition: gf2m_small_m.h:181
#define MAX_EXT_DEG
uint16_t gf2m
Definition: gf2m_small_m.h:23
Definition: alg_id.cpp:13
uint32_t encode_gf2m(gf2m to_enc, uint8_t *mem)
gf2m gf_div(gf2m x, gf2m y) const