/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/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 | | 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 | 0 |
|
44 | 0 | std::vector<gf2m> tab((static_cast<size_t>(1) << deg) + 1); |
45 | 0 |
|
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 | 0 |
|
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 | 0 |
|
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 | 0 | |
63 | 0 | if(tabs[deg].empty()) |
64 | 0 | tabs[deg] = gf_exp_table(deg, prim_poly[deg]); |
65 | 0 |
|
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 | 0 |
|
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 | 0 |
|
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 | 0 | |
88 | 0 | if(tabs[deg].empty()) |
89 | 0 | tabs[deg] = gf_log_table(deg, exp_table(deg)); |
90 | 0 |
|
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 | | } |