← Back to branch summary

~ubuntu-branches/debian/sid/botan/sid

« back to all changes in this revision

Viewing changes to src/lib/pubkey/mce/gf2m_small_m.cpp

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2018-03-01 22:23:25 UTC
  • mfrom: (1.2.2)
  • Revision ID: package-import@ubuntu.com-20180301222325-7p7vc45gu3hta34d
Tags: 2.4.0-2
* Don't remove .doctrees from the manual if it doesn't exist.
* Don't specify parallel to debhelper.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/lib/pubkey/mce/gf2m_small_m.cpp
 
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
}