Coverage Report

Created: 2022-06-23 06:44

/src/botan/src/lib/pubkey/mce/gf2m_small_m.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
*
8
* Botan is released under the Simplified BSD License (see license.txt)
9
*/
10
11
#include <botan/internal/gf2m_small_m.h>
12
#include <botan/exceptn.h>
13
#include <string>
14
15
namespace Botan {
16
17
0
#define MAX_EXT_DEG 16
18
19
namespace {
20
21
const 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
0
   {
42
   // construct the table gf_exp[i]=alpha^i
43
44
0
   std::vector<gf2m> tab((static_cast<size_t>(1) << deg) + 1);
45
46
0
   tab[0] = 1;
47
0
   for(size_t i = 1; i < tab.size(); ++i)
48
0
      {
49
0
      const gf2m overflow = tab[i-1] >> (deg - 1);
50
0
      tab[i] = (tab[i-1] << 1) ^ (overflow * prime_poly);
51
0
      }
52
53
0
   return tab;
54
0
   }
55
56
const std::vector<gf2m>& exp_table(size_t deg)
57
0
   {
58
0
   static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
59
60
0
   if(deg < 2 || deg > MAX_EXT_DEG)
61
0
      throw Invalid_Argument("GF2m_Field does not support degree " + std::to_string(deg));
62
63
0
   if(tabs[deg].empty())
64
0
      tabs[deg] = gf_exp_table(deg, prim_poly[deg]);
65
66
0
   return tabs[deg];
67
0
   }
68
69
std::vector<gf2m> gf_log_table(size_t deg, const std::vector<gf2m>& exp)
70
0
   {
71
0
   std::vector<gf2m> tab(static_cast<size_t>(1) << deg);
72
73
0
   tab[0] = static_cast<gf2m>((static_cast<gf2m>(1) << deg) - 1); // log of 0 is the order by convention
74
0
   for(size_t i = 0; i < tab.size(); ++i)
75
0
      {
76
0
      tab[exp[i]] = static_cast<gf2m>(i);
77
0
      }
78
0
   return tab;
79
0
   }
80
81
const std::vector<gf2m>& log_table(size_t deg)
82
0
   {
83
0
   static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
84
85
0
   if(deg < 2 || deg > MAX_EXT_DEG)
86
0
      throw Invalid_Argument("GF2m_Field does not support degree " + std::to_string(deg));
87
88
0
   if(tabs[deg].empty())
89
0
      tabs[deg] = gf_log_table(deg, exp_table(deg));
90
91
0
   return tabs[deg];
92
0
   }
93
94
}
95
96
uint32_t encode_gf2m(gf2m to_enc, uint8_t* mem)
97
0
   {
98
0
   mem[0] = to_enc >> 8;
99
0
   mem[1] = to_enc & 0xFF;
100
0
   return sizeof(to_enc);
101
0
   }
102
103
gf2m decode_gf2m(const uint8_t* mem)
104
0
   {
105
0
   gf2m result;
106
0
   result = mem[0] << 8;
107
0
   result |= mem[1];
108
0
   return result;
109
0
   }
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
0
   {
116
0
   }
117
118
gf2m GF2m_Field::gf_div(gf2m x, gf2m y) const
119
0
   {
120
0
   const int32_t sub_res = static_cast<int32_t>(gf_log(x) - static_cast<int32_t>(gf_log(y)));
121
0
   const gf2m modq_res = _gf_modq_1(sub_res);
122
0
   const int32_t div_res = static_cast<int32_t>(x) ? static_cast<int32_t>(gf_exp(modq_res)) : 0;
123
0
   return static_cast<gf2m>(div_res);
124
0
   }
125
126
}