Botan  2.4.0
Crypto and TLS for C++11
ed25519_fe.h
Go to the documentation of this file.
1 /*
2 * Ed25519 field element
3 * (C) 2017 Ribose Inc
4 *
5 * Based on the public domain code from SUPERCOP ref10 by
6 * Peter Schwabe, Daniel J. Bernstein, Niels Duif, Tanja Lange, Bo-Yin Yang
7 *
8 * Botan is released under the Simplified BSD License (see license.txt)
9 */
10 
11 #ifndef BOTAN_ED25519_FE_H_
12 #define BOTAN_ED25519_FE_H_
13 
14 #include <botan/mem_ops.h>
15 
16 namespace Botan {
17 
18 /**
19 * An element of the field \\Z/(2^255-19)
20 */
21 class FE_25519
22  {
23  public:
24  ~FE_25519() { secure_scrub_memory(m_fe, sizeof(m_fe)); }
25 
26  /**
27  * Zero element
28  */
29  FE_25519(int init = 0)
30  {
31  if(init != 0 && init != 1)
32  { throw std::invalid_argument("Invalid FE_25519 initial value"); }
33  memset(m_fe, 0, 10 * sizeof(int32_t));
34  m_fe[0] = init;
35  }
36 
37  FE_25519(std::initializer_list<int32_t> x)
38  {
39  if(x.size() != 10)
40  { throw std::invalid_argument("Invalid FE_25519 initializer list"); }
41  memcpy(m_fe, x.begin(), 10 * sizeof(int32_t));
42  }
43 
44  FE_25519(int64_t h0, int64_t h1, int64_t h2, int64_t h3, int64_t h4,
45  int64_t h5, int64_t h6, int64_t h7, int64_t h8, int64_t h9)
46  {
47  m_fe[0] = static_cast<int32_t>(h0);
48  m_fe[1] = static_cast<int32_t>(h1);
49  m_fe[2] = static_cast<int32_t>(h2);
50  m_fe[3] = static_cast<int32_t>(h3);
51  m_fe[4] = static_cast<int32_t>(h4);
52  m_fe[5] = static_cast<int32_t>(h5);
53  m_fe[6] = static_cast<int32_t>(h6);
54  m_fe[7] = static_cast<int32_t>(h7);
55  m_fe[8] = static_cast<int32_t>(h8);
56  m_fe[9] = static_cast<int32_t>(h9);
57  }
58 
59  FE_25519(const FE_25519& other) = default;
60  FE_25519& operator=(const FE_25519& other) = default;
61 
62 #if !defined(BOTAN_BUILD_COMPILER_IS_MSVC_2013)
63  FE_25519(FE_25519&& other) = default;
64  FE_25519& operator=(FE_25519&& other) = default;
65 #endif
66 
67  void from_bytes(const uint8_t b[32]);
68  void to_bytes(uint8_t b[32]) const;
69 
70  bool is_zero() const
71  {
72  uint8_t s[32];
73  to_bytes(s);
74 
75  uint8_t sum = 0;
76  for(size_t i = 0; i != 32; ++i)
77  { sum |= s[i]; }
78 
79  // TODO avoid ternary here
80  return (sum == 0) ? 1 : 0;
81  }
82 
83  /*
84  return 1 if f is in {1,3,5,...,q-2}
85  return 0 if f is in {0,2,4,...,q-1}
86  */
87  bool is_negative() const
88  {
89  // TODO could avoid most of the to_bytes computation here
90  uint8_t s[32];
91  to_bytes(s);
92  return s[0] & 1;
93  }
94 
95  static FE_25519 add(const FE_25519& a, const FE_25519& b)
96  {
97  FE_25519 z;
98  for(size_t i = 0; i != 10; ++i)
99  { z[i] = a[i] + b[i]; }
100  return z;
101  }
102 
103  static FE_25519 sub(const FE_25519& a, const FE_25519& b)
104  {
105  FE_25519 z;
106  for(size_t i = 0; i != 10; ++i)
107  { z[i] = a[i] - b[i]; }
108  return z;
109  }
110 
111  static FE_25519 negate(const FE_25519& a)
112  {
113  FE_25519 z;
114  for(size_t i = 0; i != 10; ++i)
115  { z[i] = -a[i]; }
116  return z;
117  }
118 
119  static FE_25519 mul(const FE_25519& a, const FE_25519& b);
120  static FE_25519 sqr_iter(const FE_25519& a, size_t iter);
121  static FE_25519 sqr(const FE_25519& a) { return sqr_iter(a, 1); }
122  static FE_25519 sqr2(const FE_25519& a);
123  static FE_25519 pow_22523(const FE_25519& a);
124  static FE_25519 invert(const FE_25519& a);
125 
126  // TODO remove
127  int32_t operator[](size_t i) const { return m_fe[i]; }
128  int32_t& operator[](size_t i) { return m_fe[i]; }
129 
130  private:
131 
132  int32_t m_fe[10];
133  };
134 
135 typedef FE_25519 fe;
136 
137 /*
138 fe means field element.
139 Here the field is
140 An element t, entries t[0]...t[9], represents the integer
141 t[0]+2^26 t[1]+2^51 t[2]+2^77 t[3]+2^102 t[4]+...+2^230 t[9].
142 Bounds on each t[i] vary depending on context.
143 */
144 
145 inline void fe_frombytes(fe& x, const uint8_t* b)
146  {
147  x.from_bytes(b);
148  }
149 
150 inline void fe_tobytes(uint8_t* b, const fe& x)
151  {
152  x.to_bytes(b);
153  }
154 
155 inline void fe_copy(fe& a, const fe& b)
156  {
157  a = b;
158  }
159 
160 inline int fe_isnonzero(const fe& x)
161  {
162  return x.is_zero() ? 0 : 1;
163  }
164 
165 inline int fe_isnegative(const fe& x)
166  {
167  return x.is_negative();
168  }
169 
170 
171 inline void fe_0(fe& x)
172  {
173  x = FE_25519();
174  }
175 
176 inline void fe_1(fe& x)
177  {
178  x = FE_25519(1);
179  }
180 
181 inline void fe_add(fe& x, const fe& a, const fe& b)
182  {
183  x = FE_25519::add(a, b);
184  }
185 
186 inline void fe_sub(fe& x, const fe& a, const fe& b)
187  {
188  x = FE_25519::sub(a, b);
189  }
190 
191 inline void fe_neg(fe& x, const fe& z)
192  {
193  x = FE_25519::negate(z);
194  }
195 
196 inline void fe_mul(fe& x, const fe& a, const fe& b)
197  {
198  x = FE_25519::mul(a, b);
199  }
200 
201 inline void fe_sq(fe& x, const fe& z)
202  {
203  x = FE_25519::sqr(z);
204  }
205 
206 inline void fe_sq_iter(fe& x, const fe& z, size_t iter)
207  {
208  x = FE_25519::sqr_iter(z, iter);
209  }
210 
211 inline void fe_sq2(fe& x, const fe& z)
212  {
213  x = FE_25519::sqr2(z);
214  }
215 
216 inline void fe_invert(fe& x, const fe& z)
217  {
218  x = FE_25519::invert(z);
219  }
220 
221 inline void fe_pow22523(fe& x, const fe& y)
222  {
223  x = FE_25519::pow_22523(y);
224  }
225 
226 }
227 
228 #endif
FE_25519(int64_t h0, int64_t h1, int64_t h2, int64_t h3, int64_t h4, int64_t h5, int64_t h6, int64_t h7, int64_t h8, int64_t h9)
Definition: ed25519_fe.h:44
static FE_25519 pow_22523(const FE_25519 &a)
Definition: ed25519_fe.cpp:50
static FE_25519 invert(const FE_25519 &a)
Definition: ed25519_fe.cpp:17
static FE_25519 negate(const FE_25519 &a)
Definition: ed25519_fe.h:111
void fe_neg(fe &x, const fe &z)
Definition: ed25519_fe.h:191
void fe_add(fe &x, const fe &a, const fe &b)
Definition: ed25519_fe.h:181
void from_bytes(const uint8_t b[32])
Definition: ed25519_fe.cpp:720
int32_t & operator[](size_t i)
Definition: ed25519_fe.h:128
void fe_0(fe &x)
Definition: ed25519_fe.h:171
void fe_sq(fe &x, const fe &z)
Definition: ed25519_fe.h:201
void to_bytes(uint8_t b[32]) const
Definition: ed25519_fe.cpp:806
void fe_invert(fe &x, const fe &z)
Definition: ed25519_fe.h:216
FE_25519 & operator=(const FE_25519 &other)=default
void fe_1(fe &x)
Definition: ed25519_fe.h:176
int fe_isnegative(const fe &x)
Definition: ed25519_fe.h:165
void fe_sub(fe &x, const fe &a, const fe &b)
Definition: ed25519_fe.h:186
void fe_sq2(fe &x, const fe &z)
Definition: ed25519_fe.h:211
void fe_copy(fe &a, const fe &b)
Definition: ed25519_fe.h:155
static FE_25519 sqr_iter(const FE_25519 &a, size_t iter)
Definition: ed25519_fe.cpp:370
static FE_25519 sqr2(const FE_25519 &a)
Definition: ed25519_fe.cpp:554
void fe_tobytes(uint8_t *b, const fe &x)
Definition: ed25519_fe.h:150
void fe_sq_iter(fe &x, const fe &z, size_t iter)
Definition: ed25519_fe.h:206
static FE_25519 mul(const FE_25519 &a, const FE_25519 &b)
Definition: ed25519_fe.cpp:115
Definition: alg_id.cpp:13
int fe_isnonzero(const fe &x)
Definition: ed25519_fe.h:160
FE_25519(std::initializer_list< int32_t > x)
Definition: ed25519_fe.h:37
FE_25519(int init=0)
Definition: ed25519_fe.h:29
int32_t operator[](size_t i) const
Definition: ed25519_fe.h:127
void secure_scrub_memory(void *ptr, size_t n)
Definition: os_utils.cpp:37
FE_25519 fe
Definition: ed25519_fe.h:135
static FE_25519 add(const FE_25519 &a, const FE_25519 &b)
Definition: ed25519_fe.h:95
static FE_25519 sqr(const FE_25519 &a)
Definition: ed25519_fe.h:121
static FE_25519 sub(const FE_25519 &a, const FE_25519 &b)
Definition: ed25519_fe.h:103
void fe_frombytes(fe &x, const uint8_t *b)
Definition: ed25519_fe.h:145
void fe_pow22523(fe &x, const fe &y)
Definition: ed25519_fe.h:221
bool is_zero() const
Definition: ed25519_fe.h:70
bool is_negative() const
Definition: ed25519_fe.h:87
void fe_mul(fe &x, const fe &a, const fe &b)
Definition: ed25519_fe.h:196