Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 unsigned int 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 0210013 /* extension degree 16 */
39 };
40
41 std::vector<gf2m> gf_exp_table(size_t deg, gf2m prime_poly)
42 {
43 // construct the table gf_exp[i]=alpha^i
44
45 std::vector<gf2m> tab((1 << deg) + 1);
46
47 tab[0] = 1;
48 for(size_t i = 1; i < tab.size(); ++i)
49 {
50 const bool overflow = tab[i - 1] >> (deg - 1);
51 tab[i] = (tab[i-1] << 1) ^ (overflow ? prime_poly : 0);
52 }
53
54 return tab;
55 }
56
57 const std::vector<gf2m>& exp_table(size_t deg)
58 {
59 static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
60
61 if(deg < 2 || deg > MAX_EXT_DEG)
62 throw Exception("GF2m_Field does not support degree " + std::to_string(deg));
63
64 if(tabs[deg].empty())
65 tabs[deg] = gf_exp_table(deg, prim_poly[deg]);
66
67 return tabs[deg];
68 }
69
70 std::vector<gf2m> gf_log_table(size_t deg, const std::vector<gf2m>& exp)
71 {
72 std::vector<gf2m> tab(1 << deg);
73
74 tab[0] = (1 << deg) - 1; // log of 0 is the order by convention
75 for (size_t i = 0; i < tab.size(); ++i)
76 {
77 tab[exp[i]] = i;
78 }
79 return tab;
80 }
81
82 const std::vector<gf2m>& log_table(size_t deg)
83 {
84 static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
85
86 if(deg < 2 || deg > MAX_EXT_DEG)
87 throw Exception("GF2m_Field does not support degree " + std::to_string(deg));
88
89 if(tabs[deg].empty())
90 tabs[deg] = gf_log_table(deg, exp_table(deg));
91
92 return tabs[deg];
93 }
94
95 }
96
97 uint32_t encode_gf2m(gf2m to_enc, uint8_t* mem)
98 {
99 mem[0] = to_enc >> 8;
100 mem[1] = to_enc & 0xFF;
101 return sizeof(to_enc);
102 }
103
104 gf2m decode_gf2m(const uint8_t* mem)
105 {
106 gf2m result;
107 result = mem[0] << 8;
108 result |= mem[1];
109 return result;
110 }
111
112 GF2m_Field::GF2m_Field(size_t extdeg) : m_gf_extension_degree(extdeg),
113 m_gf_multiplicative_order((1 << extdeg) - 1),
114 m_gf_log_table(log_table(m_gf_extension_degree)),
115 m_gf_exp_table(exp_table(m_gf_extension_degree))
116 {
117 }
118
119 gf2m GF2m_Field::gf_div(gf2m x, gf2m y) const
120 {
121 const int32_t sub_res = static_cast<int32_t>(gf_log(x) - static_cast<int32_t>(gf_log(y)));
122 const int32_t modq_res = static_cast<int32_t>(_gf_modq_1(sub_res));
123 const int32_t div_res = static_cast<int32_t>(x) ? static_cast<int32_t>(gf_exp(modq_res)) : 0;
124 return static_cast<gf2m>(div_res);
125 }
126
127 // we suppose i >= 0. Par convention 0^0 = 1
128 gf2m GF2m_Field::gf_pow(gf2m x, int i) const
129 {
130 if (i == 0)
131 return 1;
132 else if (x == 0)
133 return 0;
134 else
135 {
136 // i mod (q-1)
137 while (i >> get_extension_degree())
138 i = (i & (gf_ord())) + (i >> get_extension_degree());
139 i *= gf_log(x);
140 while (i >> get_extension_degree())
141 i = (i & (gf_ord())) + (i >> get_extension_degree());
142 return gf_exp(i);
143 }
144 }
145
146 }
Botan::GF2m_Field::GF2m_Field
GF2m_Field(size_t extdeg)
Definition: gf2m_small_m.cpp:112
Botan::GF2m_Field::get_extension_degree
gf2m get_extension_degree() const
Definition: gf2m_small_m.h:188
Botan::decode_gf2m
gf2m decode_gf2m(const uint8_t *mem)
Definition: gf2m_small_m.cpp:104
Botan::ASN1::to_string
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:47
Botan::GF2m_Field::gf_log
gf2m gf_log(gf2m i) const
Definition: gf2m_small_m.h:178
MAX_EXT_DEG
#define MAX_EXT_DEG
Definition: gf2m_small_m.cpp:17
Botan::GF2m_Field::gf_pow
gf2m gf_pow(gf2m x, int i) const
Definition: gf2m_small_m.cpp:128
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:20
Botan
Definition: alg_id.cpp:13
Botan::encode_gf2m
uint32_t encode_gf2m(gf2m to_enc, uint8_t *mem)
Definition: gf2m_small_m.cpp:97
Botan::GF2m_Field::gf_ord
gf2m gf_ord() const
Definition: gf2m_small_m.h:183
Botan::GF2m_Field::gf_exp
gf2m gf_exp(gf2m i) const
Definition: gf2m_small_m.h:173
Botan::GF2m_Field::gf_div
gf2m gf_div(gf2m x, gf2m y) const
Definition: gf2m_small_m.cpp:119