Botan 3.9.0
Crypto and TLS for C&
Botan::Ed25519_FieldElement Class Referencefinal

#include <ed25519_fe.h>

Public Member Functions

constexpr Ed25519_FieldElement ()
constexpr Ed25519_FieldElement (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)
constexpr Ed25519_FieldElement (std::span< int32_t, 10 > fe)
Ed25519_FieldElement invert () const
bool is_negative () const
bool is_zero () const
int32_t & operator[] (size_t i)
int32_t operator[] (size_t i) const
Ed25519_FieldElement pow_22523 () const
void serialize_to (std::span< uint8_t, 32 > b) const
Ed25519_FieldElement sqr () const
Ed25519_FieldElement sqr2 () const
Ed25519_FieldElement sqr_iter (size_t iter) const

Static Public Member Functions

static Ed25519_FieldElement add (const Ed25519_FieldElement &a, const Ed25519_FieldElement &b)
static Ed25519_FieldElement deserialize (const uint8_t b[32])
static Ed25519_FieldElement mul (const Ed25519_FieldElement &a, const Ed25519_FieldElement &b)
static Ed25519_FieldElement negate (const Ed25519_FieldElement &a)
static constexpr Ed25519_FieldElement one ()
static Ed25519_FieldElement sub (const Ed25519_FieldElement &a, const Ed25519_FieldElement &b)
static constexpr Ed25519_FieldElement zero ()

Detailed Description

An element of the field \Z/(2^255-19)

An element t, entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77 t[3]+2^102 t[4]+...+2^230 t[9]. Bounds on each t[i] vary depending on context.

Definition at line 29 of file ed25519_fe.h.

Constructor & Destructor Documentation

◆ Ed25519_FieldElement() [1/3]

Botan::Ed25519_FieldElement::Ed25519_FieldElement ( )
inlineconstexpr

Default zero initialization

Definition at line 34 of file ed25519_fe.h.

34: m_fe{} {}

Referenced by add(), deserialize(), invert(), mul(), negate(), one(), pow_22523(), sqr(), sqr2(), sqr_iter(), sub(), and zero().

◆ Ed25519_FieldElement() [2/3]

Botan::Ed25519_FieldElement::Ed25519_FieldElement ( std::span< int32_t, 10 > fe)
inlineexplicitconstexpr

Definition at line 45 of file ed25519_fe.h.

45{ copy_mem(m_fe.data(), fe.data(), 10); }
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:145

References Botan::copy_mem().

◆ Ed25519_FieldElement() [3/3]

Botan::Ed25519_FieldElement::Ed25519_FieldElement ( 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 )
inlineconstexpr

Definition at line 48 of file ed25519_fe.h.

57 {
58 m_fe[0] = static_cast<int32_t>(h0);
59 m_fe[1] = static_cast<int32_t>(h1);
60 m_fe[2] = static_cast<int32_t>(h2);
61 m_fe[3] = static_cast<int32_t>(h3);
62 m_fe[4] = static_cast<int32_t>(h4);
63 m_fe[5] = static_cast<int32_t>(h5);
64 m_fe[6] = static_cast<int32_t>(h6);
65 m_fe[7] = static_cast<int32_t>(h7);
66 m_fe[8] = static_cast<int32_t>(h8);
67 m_fe[9] = static_cast<int32_t>(h9);
68 }

Member Function Documentation

◆ add()

Ed25519_FieldElement Botan::Ed25519_FieldElement::add ( const Ed25519_FieldElement & a,
const Ed25519_FieldElement & b )
inlinestatic

Definition at line 91 of file ed25519_fe.h.

91 {
93 for(size_t i = 0; i != 10; ++i) {
94 z.m_fe[i] = a.m_fe[i] + b.m_fe[i];
95 }
96 return z;
97 }
constexpr Ed25519_FieldElement()
Definition ed25519_fe.h:34

References Ed25519_FieldElement().

Referenced by Botan::operator+().

◆ deserialize()

Ed25519_FieldElement Botan::Ed25519_FieldElement::deserialize ( const uint8_t b[32])
static

Definition at line 591 of file ed25519_fe.cpp.

591 {
592 int64_t h0 = load_4(s);
593 int64_t h1 = load_3(s + 4) << 6;
594 int64_t h2 = load_3(s + 7) << 5;
595 int64_t h3 = load_3(s + 10) << 3;
596 int64_t h4 = load_3(s + 13) << 2;
597 int64_t h5 = load_4(s + 16);
598 int64_t h6 = load_3(s + 20) << 7;
599 int64_t h7 = load_3(s + 23) << 5;
600 int64_t h8 = load_3(s + 26) << 4;
601 int64_t h9 = (load_3(s + 29) & 0x7fffff) << 2;
602
603 carry<25, 19>(h9, h0);
604 carry<25>(h1, h2);
605 carry<25>(h3, h4);
606 carry<25>(h5, h6);
607 carry<25>(h7, h8);
608
609 carry<26>(h0, h1);
610 carry<26>(h2, h3);
611 carry<26>(h4, h5);
612 carry<26>(h6, h7);
613 carry<26>(h8, h9);
614
615 return Ed25519_FieldElement(h0, h1, h2, h3, h4, h5, h6, h7, h8, h9);
616}
uint32_t load_3(const uint8_t in[3])
void carry(int64_t &h0, int64_t &h1)
uint32_t load_4(const uint8_t *in)

References Botan::carry(), Ed25519_FieldElement(), Botan::load_3(), and Botan::load_4().

◆ invert()

Ed25519_FieldElement Botan::Ed25519_FieldElement::invert ( ) const

Definition at line 18 of file ed25519_fe.cpp.

18 {
19 auto t0 = this->sqr();
20 auto t1 = t0.sqr_iter(2);
21 t1 = *this * t1;
22 t0 = t0 * t1;
23 auto t2 = t0.sqr();
24 t1 = t1 * t2;
25 t2 = t1.sqr_iter(5);
26 t1 = t2 * t1;
27 t2 = t1.sqr_iter(10);
28 t2 = t2 * t1;
29 auto t3 = t2.sqr_iter(20);
30 t2 = t3 * t2;
31 t2 = t2.sqr_iter(10);
32 t1 = t2 * t1;
33 t2 = t1.sqr_iter(50);
34 t2 = t2 * t1;
35 t3 = t2.sqr_iter(100);
36 t2 = t3 * t2;
37 t2 = t2.sqr_iter(50);
38 t1 = t2 * t1;
39 t1 = t1.sqr_iter(5);
40
41 t0 = t1 * t0;
42 return t0;
43}
Ed25519_FieldElement sqr() const
Definition ed25519_fe.h:119

References Ed25519_FieldElement(), and sqr().

◆ is_negative()

bool Botan::Ed25519_FieldElement::is_negative ( ) const
inline

Definition at line 84 of file ed25519_fe.h.

84 {
85 // TODO could avoid most of the serialize computation here
86 std::array<uint8_t, 32> s = {};
87 this->serialize_to(s);
88 return (s[0] & 0x01) == 0x01;
89 }
void serialize_to(std::span< uint8_t, 32 > b) const

References serialize_to().

◆ is_zero()

bool Botan::Ed25519_FieldElement::is_zero ( ) const
inline

Definition at line 74 of file ed25519_fe.h.

74 {
75 std::array<uint8_t, 32> value = {};
76 this->serialize_to(value);
77 return CT::all_zeros(value.data(), value.size()).as_bool();
78 }
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:813

References Botan::CT::all_zeros(), and serialize_to().

◆ mul()

Ed25519_FieldElement Botan::Ed25519_FieldElement::mul ( const Ed25519_FieldElement & a,
const Ed25519_FieldElement & b )
static

Definition at line 105 of file ed25519_fe.cpp.

105 {
106 const int32_t f0 = f.m_fe[0];
107 const int32_t f1 = f.m_fe[1];
108 const int32_t f2 = f.m_fe[2];
109 const int32_t f3 = f.m_fe[3];
110 const int32_t f4 = f.m_fe[4];
111 const int32_t f5 = f.m_fe[5];
112 const int32_t f6 = f.m_fe[6];
113 const int32_t f7 = f.m_fe[7];
114 const int32_t f8 = f.m_fe[8];
115 const int32_t f9 = f.m_fe[9];
116
117 const int32_t g0 = g.m_fe[0];
118 const int32_t g1 = g.m_fe[1];
119 const int32_t g2 = g.m_fe[2];
120 const int32_t g3 = g.m_fe[3];
121 const int32_t g4 = g.m_fe[4];
122 const int32_t g5 = g.m_fe[5];
123 const int32_t g6 = g.m_fe[6];
124 const int32_t g7 = g.m_fe[7];
125 const int32_t g8 = g.m_fe[8];
126 const int32_t g9 = g.m_fe[9];
127
128 const int32_t g1_19 = 19 * g1; /* 1.959375*2^29 */
129 const int32_t g2_19 = 19 * g2; /* 1.959375*2^30; still ok */
130 const int32_t g3_19 = 19 * g3;
131 const int32_t g4_19 = 19 * g4;
132 const int32_t g5_19 = 19 * g5;
133 const int32_t g6_19 = 19 * g6;
134 const int32_t g7_19 = 19 * g7;
135 const int32_t g8_19 = 19 * g8;
136 const int32_t g9_19 = 19 * g9;
137 const int32_t f1_2 = 2 * f1;
138 const int32_t f3_2 = 2 * f3;
139 const int32_t f5_2 = 2 * f5;
140 const int32_t f7_2 = 2 * f7;
141 const int32_t f9_2 = 2 * f9;
142
143 const int64_t f0g0 = f0 * static_cast<int64_t>(g0);
144 const int64_t f0g1 = f0 * static_cast<int64_t>(g1);
145 const int64_t f0g2 = f0 * static_cast<int64_t>(g2);
146 const int64_t f0g3 = f0 * static_cast<int64_t>(g3);
147 const int64_t f0g4 = f0 * static_cast<int64_t>(g4);
148 const int64_t f0g5 = f0 * static_cast<int64_t>(g5);
149 const int64_t f0g6 = f0 * static_cast<int64_t>(g6);
150 const int64_t f0g7 = f0 * static_cast<int64_t>(g7);
151 const int64_t f0g8 = f0 * static_cast<int64_t>(g8);
152 const int64_t f0g9 = f0 * static_cast<int64_t>(g9);
153 const int64_t f1g0 = f1 * static_cast<int64_t>(g0);
154 const int64_t f1g1_2 = f1_2 * static_cast<int64_t>(g1);
155 const int64_t f1g2 = f1 * static_cast<int64_t>(g2);
156 const int64_t f1g3_2 = f1_2 * static_cast<int64_t>(g3);
157 const int64_t f1g4 = f1 * static_cast<int64_t>(g4);
158 const int64_t f1g5_2 = f1_2 * static_cast<int64_t>(g5);
159 const int64_t f1g6 = f1 * static_cast<int64_t>(g6);
160 const int64_t f1g7_2 = f1_2 * static_cast<int64_t>(g7);
161 const int64_t f1g8 = f1 * static_cast<int64_t>(g8);
162 const int64_t f1g9_38 = f1_2 * static_cast<int64_t>(g9_19);
163 const int64_t f2g0 = f2 * static_cast<int64_t>(g0);
164 const int64_t f2g1 = f2 * static_cast<int64_t>(g1);
165 const int64_t f2g2 = f2 * static_cast<int64_t>(g2);
166 const int64_t f2g3 = f2 * static_cast<int64_t>(g3);
167 const int64_t f2g4 = f2 * static_cast<int64_t>(g4);
168 const int64_t f2g5 = f2 * static_cast<int64_t>(g5);
169 const int64_t f2g6 = f2 * static_cast<int64_t>(g6);
170 const int64_t f2g7 = f2 * static_cast<int64_t>(g7);
171 const int64_t f2g8_19 = f2 * static_cast<int64_t>(g8_19);
172 const int64_t f2g9_19 = f2 * static_cast<int64_t>(g9_19);
173 const int64_t f3g0 = f3 * static_cast<int64_t>(g0);
174 const int64_t f3g1_2 = f3_2 * static_cast<int64_t>(g1);
175 const int64_t f3g2 = f3 * static_cast<int64_t>(g2);
176 const int64_t f3g3_2 = f3_2 * static_cast<int64_t>(g3);
177 const int64_t f3g4 = f3 * static_cast<int64_t>(g4);
178 const int64_t f3g5_2 = f3_2 * static_cast<int64_t>(g5);
179 const int64_t f3g6 = f3 * static_cast<int64_t>(g6);
180 const int64_t f3g7_38 = f3_2 * static_cast<int64_t>(g7_19);
181 const int64_t f3g8_19 = f3 * static_cast<int64_t>(g8_19);
182 const int64_t f3g9_38 = f3_2 * static_cast<int64_t>(g9_19);
183 const int64_t f4g0 = f4 * static_cast<int64_t>(g0);
184 const int64_t f4g1 = f4 * static_cast<int64_t>(g1);
185 const int64_t f4g2 = f4 * static_cast<int64_t>(g2);
186 const int64_t f4g3 = f4 * static_cast<int64_t>(g3);
187 const int64_t f4g4 = f4 * static_cast<int64_t>(g4);
188 const int64_t f4g5 = f4 * static_cast<int64_t>(g5);
189 const int64_t f4g6_19 = f4 * static_cast<int64_t>(g6_19);
190 const int64_t f4g7_19 = f4 * static_cast<int64_t>(g7_19);
191 const int64_t f4g8_19 = f4 * static_cast<int64_t>(g8_19);
192 const int64_t f4g9_19 = f4 * static_cast<int64_t>(g9_19);
193 const int64_t f5g0 = f5 * static_cast<int64_t>(g0);
194 const int64_t f5g1_2 = f5_2 * static_cast<int64_t>(g1);
195 const int64_t f5g2 = f5 * static_cast<int64_t>(g2);
196 const int64_t f5g3_2 = f5_2 * static_cast<int64_t>(g3);
197 const int64_t f5g4 = f5 * static_cast<int64_t>(g4);
198 const int64_t f5g5_38 = f5_2 * static_cast<int64_t>(g5_19);
199 const int64_t f5g6_19 = f5 * static_cast<int64_t>(g6_19);
200 const int64_t f5g7_38 = f5_2 * static_cast<int64_t>(g7_19);
201 const int64_t f5g8_19 = f5 * static_cast<int64_t>(g8_19);
202 const int64_t f5g9_38 = f5_2 * static_cast<int64_t>(g9_19);
203 const int64_t f6g0 = f6 * static_cast<int64_t>(g0);
204 const int64_t f6g1 = f6 * static_cast<int64_t>(g1);
205 const int64_t f6g2 = f6 * static_cast<int64_t>(g2);
206 const int64_t f6g3 = f6 * static_cast<int64_t>(g3);
207 const int64_t f6g4_19 = f6 * static_cast<int64_t>(g4_19);
208 const int64_t f6g5_19 = f6 * static_cast<int64_t>(g5_19);
209 const int64_t f6g6_19 = f6 * static_cast<int64_t>(g6_19);
210 const int64_t f6g7_19 = f6 * static_cast<int64_t>(g7_19);
211 const int64_t f6g8_19 = f6 * static_cast<int64_t>(g8_19);
212 const int64_t f6g9_19 = f6 * static_cast<int64_t>(g9_19);
213 const int64_t f7g0 = f7 * static_cast<int64_t>(g0);
214 const int64_t f7g1_2 = f7_2 * static_cast<int64_t>(g1);
215 const int64_t f7g2 = f7 * static_cast<int64_t>(g2);
216 const int64_t f7g3_38 = f7_2 * static_cast<int64_t>(g3_19);
217 const int64_t f7g4_19 = f7 * static_cast<int64_t>(g4_19);
218 const int64_t f7g5_38 = f7_2 * static_cast<int64_t>(g5_19);
219 const int64_t f7g6_19 = f7 * static_cast<int64_t>(g6_19);
220 const int64_t f7g7_38 = f7_2 * static_cast<int64_t>(g7_19);
221 const int64_t f7g8_19 = f7 * static_cast<int64_t>(g8_19);
222 const int64_t f7g9_38 = f7_2 * static_cast<int64_t>(g9_19);
223 const int64_t f8g0 = f8 * static_cast<int64_t>(g0);
224 const int64_t f8g1 = f8 * static_cast<int64_t>(g1);
225 const int64_t f8g2_19 = f8 * static_cast<int64_t>(g2_19);
226 const int64_t f8g3_19 = f8 * static_cast<int64_t>(g3_19);
227 const int64_t f8g4_19 = f8 * static_cast<int64_t>(g4_19);
228 const int64_t f8g5_19 = f8 * static_cast<int64_t>(g5_19);
229 const int64_t f8g6_19 = f8 * static_cast<int64_t>(g6_19);
230 const int64_t f8g7_19 = f8 * static_cast<int64_t>(g7_19);
231 const int64_t f8g8_19 = f8 * static_cast<int64_t>(g8_19);
232 const int64_t f8g9_19 = f8 * static_cast<int64_t>(g9_19);
233 const int64_t f9g0 = f9 * static_cast<int64_t>(g0);
234 const int64_t f9g1_38 = f9_2 * static_cast<int64_t>(g1_19);
235 const int64_t f9g2_19 = f9 * static_cast<int64_t>(g2_19);
236 const int64_t f9g3_38 = f9_2 * static_cast<int64_t>(g3_19);
237 const int64_t f9g4_19 = f9 * static_cast<int64_t>(g4_19);
238 const int64_t f9g5_38 = f9_2 * static_cast<int64_t>(g5_19);
239 const int64_t f9g6_19 = f9 * static_cast<int64_t>(g6_19);
240 const int64_t f9g7_38 = f9_2 * static_cast<int64_t>(g7_19);
241 const int64_t f9g8_19 = f9 * static_cast<int64_t>(g8_19);
242 const int64_t f9g9_38 = f9_2 * static_cast<int64_t>(g9_19);
243
244 int64_t h0 = f0g0 + f1g9_38 + f2g8_19 + f3g7_38 + f4g6_19 + f5g5_38 + f6g4_19 + f7g3_38 + f8g2_19 + f9g1_38;
245 int64_t h1 = f0g1 + f1g0 + f2g9_19 + f3g8_19 + f4g7_19 + f5g6_19 + f6g5_19 + f7g4_19 + f8g3_19 + f9g2_19;
246 int64_t h2 = f0g2 + f1g1_2 + f2g0 + f3g9_38 + f4g8_19 + f5g7_38 + f6g6_19 + f7g5_38 + f8g4_19 + f9g3_38;
247 int64_t h3 = f0g3 + f1g2 + f2g1 + f3g0 + f4g9_19 + f5g8_19 + f6g7_19 + f7g6_19 + f8g5_19 + f9g4_19;
248 int64_t h4 = f0g4 + f1g3_2 + f2g2 + f3g1_2 + f4g0 + f5g9_38 + f6g8_19 + f7g7_38 + f8g6_19 + f9g5_38;
249 int64_t h5 = f0g5 + f1g4 + f2g3 + f3g2 + f4g1 + f5g0 + f6g9_19 + f7g8_19 + f8g7_19 + f9g6_19;
250 int64_t h6 = f0g6 + f1g5_2 + f2g4 + f3g3_2 + f4g2 + f5g1_2 + f6g0 + f7g9_38 + f8g8_19 + f9g7_38;
251 int64_t h7 = f0g7 + f1g6 + f2g5 + f3g4 + f4g3 + f5g2 + f6g1 + f7g0 + f8g9_19 + f9g8_19;
252 int64_t h8 = f0g8 + f1g7_2 + f2g6 + f3g5_2 + f4g4 + f5g3_2 + f6g2 + f7g1_2 + f8g0 + f9g9_38;
253 int64_t h9 = f0g9 + f1g8 + f2g7 + f3g6 + f4g5 + f5g4 + f6g3 + f7g2 + f8g1 + f9g0;
254
255 /*
256 |h0| <= (1.65*1.65*2^52*(1+19+19+19+19)+1.65*1.65*2^50*(38+38+38+38+38))
257 i.e. |h0| <= 1.4*2^60; narrower ranges for h2, h4, h6, h8
258 |h1| <= (1.65*1.65*2^51*(1+1+19+19+19+19+19+19+19+19))
259 i.e. |h1| <= 1.7*2^59; narrower ranges for h3, h5, h7, h9
260 */
261 carry<26>(h0, h1);
262 carry<26>(h4, h5);
263
264 /* |h0| <= 2^25 */
265 /* |h4| <= 2^25 */
266 /* |h1| <= 1.71*2^59 */
267 /* |h5| <= 1.71*2^59 */
268
269 carry<25>(h1, h2);
270 carry<25>(h5, h6);
271
272 /* |h1| <= 2^24; from now on fits into int32 */
273 /* |h5| <= 2^24; from now on fits into int32 */
274 /* |h2| <= 1.41*2^60 */
275 /* |h6| <= 1.41*2^60 */
276
277 carry<26>(h2, h3);
278 carry<26>(h6, h7);
279 /* |h2| <= 2^25; from now on fits into int32 unchanged */
280 /* |h6| <= 2^25; from now on fits into int32 unchanged */
281 /* |h3| <= 1.71*2^59 */
282 /* |h7| <= 1.71*2^59 */
283
284 carry<25>(h3, h4);
285 carry<25>(h7, h8);
286 /* |h3| <= 2^24; from now on fits into int32 unchanged */
287 /* |h7| <= 2^24; from now on fits into int32 unchanged */
288 /* |h4| <= 1.72*2^34 */
289 /* |h8| <= 1.41*2^60 */
290
291 carry<26>(h4, h5);
292 carry<26>(h8, h9);
293 /* |h4| <= 2^25; from now on fits into int32 unchanged */
294 /* |h8| <= 2^25; from now on fits into int32 unchanged */
295 /* |h5| <= 1.01*2^24 */
296 /* |h9| <= 1.71*2^59 */
297
298 carry<25, 19>(h9, h0);
299
300 /* |h9| <= 2^24; from now on fits into int32 unchanged */
301 /* |h0| <= 1.1*2^39 */
302
303 carry<26>(h0, h1);
304 /* |h0| <= 2^25; from now on fits into int32 unchanged */
305 /* |h1| <= 1.01*2^24 */
306
307 return Ed25519_FieldElement(h0, h1, h2, h3, h4, h5, h6, h7, h8, h9);
308}

References Botan::carry(), and Ed25519_FieldElement().

Referenced by Botan::operator*().

◆ negate()

Ed25519_FieldElement Botan::Ed25519_FieldElement::negate ( const Ed25519_FieldElement & a)
inlinestatic

Definition at line 107 of file ed25519_fe.h.

107 {
109 for(size_t i = 0; i != 10; ++i) {
110 z.m_fe[i] = -a.m_fe[i];
111 }
112 return z;
113 }

References Ed25519_FieldElement().

Referenced by Botan::operator-().

◆ one()

constexpr Ed25519_FieldElement Botan::Ed25519_FieldElement::one ( )
inlinestaticconstexpr

Definition at line 38 of file ed25519_fe.h.

38 {
39 auto o = Ed25519_FieldElement();
40 o.m_fe[0] = 1;
41 return o;
42 }

References Ed25519_FieldElement().

◆ operator[]() [1/2]

int32_t & Botan::Ed25519_FieldElement::operator[] ( size_t i)
inline

Definition at line 131 of file ed25519_fe.h.

131{ return m_fe[i]; }

◆ operator[]() [2/2]

int32_t Botan::Ed25519_FieldElement::operator[] ( size_t i) const
inline

Definition at line 129 of file ed25519_fe.h.

129{ return m_fe[i]; }

◆ pow_22523()

Ed25519_FieldElement Botan::Ed25519_FieldElement::pow_22523 ( ) const

Definition at line 45 of file ed25519_fe.cpp.

45 {
46 auto t0 = this->sqr();
47 auto t1 = t0.sqr_iter(2);
48 t1 = (*this) * t1;
49 t0 = t0 * t1;
50 t0 = t0.sqr();
51 t0 = t1 * t0;
52 t1 = t0.sqr_iter(5);
53 t0 = t1 * t0;
54 t1 = t0.sqr_iter(10);
55 t1 = t1 * t0;
56 auto t2 = t1.sqr_iter(20);
57 t1 = t2 * t1;
58 t1 = t1.sqr_iter(10);
59 t0 = t1 * t0;
60 t1 = t0.sqr_iter(50);
61 t1 = t1 * t0;
62 t2 = t1.sqr_iter(100);
63 t1 = t2 * t1;
64 t1 = t1.sqr_iter(50);
65 t0 = t1 * t0;
66 t0 = t0.sqr_iter(2);
67
68 t0 = t0 * (*this);
69 return t0;
70}

References Ed25519_FieldElement(), and sqr().

◆ serialize_to()

void Botan::Ed25519_FieldElement::serialize_to ( std::span< uint8_t, 32 > b) const

Definition at line 643 of file ed25519_fe.cpp.

643 {
644 const int32_t X25 = (1 << 25);
645
646 int32_t h0 = m_fe[0];
647 int32_t h1 = m_fe[1];
648 int32_t h2 = m_fe[2];
649 int32_t h3 = m_fe[3];
650 int32_t h4 = m_fe[4];
651 int32_t h5 = m_fe[5];
652 int32_t h6 = m_fe[6];
653 int32_t h7 = m_fe[7];
654 int32_t h8 = m_fe[8];
655 int32_t h9 = m_fe[9];
656
657 int32_t q = (19 * h9 + ((static_cast<int32_t>(1) << 24))) >> 25;
658 q = (h0 + q) >> 26;
659 q = (h1 + q) >> 25;
660 q = (h2 + q) >> 26;
661 q = (h3 + q) >> 25;
662 q = (h4 + q) >> 26;
663 q = (h5 + q) >> 25;
664 q = (h6 + q) >> 26;
665 q = (h7 + q) >> 25;
666 q = (h8 + q) >> 26;
667 q = (h9 + q) >> 25;
668
669 /* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */
670 h0 += 19 * q;
671 /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */
672
673 carry0<26>(h0, h1);
674 carry0<25>(h1, h2);
675 carry0<26>(h2, h3);
676 carry0<25>(h3, h4);
677 carry0<26>(h4, h5);
678 carry0<25>(h5, h6);
679 carry0<26>(h6, h7);
680 carry0<25>(h7, h8);
681 carry0<26>(h8, h9);
682
683 int32_t carry9 = h9 >> 25;
684 h9 -= carry9 * X25;
685 /* h10 = carry9 */
686
687 /*
688 Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
689 Have h0+...+2^230 h9 between 0 and 2^255-1;
690 evidently 2^255 h10-2^255 q = 0.
691 Goal: Output h0+...+2^230 h9.
692 */
693
694 s[0] = static_cast<uint8_t>(h0 >> 0);
695 s[1] = static_cast<uint8_t>(h0 >> 8);
696 s[2] = static_cast<uint8_t>(h0 >> 16);
697 s[3] = static_cast<uint8_t>((h0 >> 24) | (h1 << 2));
698 s[4] = static_cast<uint8_t>(h1 >> 6);
699 s[5] = static_cast<uint8_t>(h1 >> 14);
700 s[6] = static_cast<uint8_t>((h1 >> 22) | (h2 << 3));
701 s[7] = static_cast<uint8_t>(h2 >> 5);
702 s[8] = static_cast<uint8_t>(h2 >> 13);
703 s[9] = static_cast<uint8_t>((h2 >> 21) | (h3 << 5));
704 s[10] = static_cast<uint8_t>(h3 >> 3);
705 s[11] = static_cast<uint8_t>(h3 >> 11);
706 s[12] = static_cast<uint8_t>((h3 >> 19) | (h4 << 6));
707 s[13] = static_cast<uint8_t>(h4 >> 2);
708 s[14] = static_cast<uint8_t>(h4 >> 10);
709 s[15] = static_cast<uint8_t>(h4 >> 18);
710 s[16] = static_cast<uint8_t>(h5 >> 0);
711 s[17] = static_cast<uint8_t>(h5 >> 8);
712 s[18] = static_cast<uint8_t>(h5 >> 16);
713 s[19] = static_cast<uint8_t>((h5 >> 24) | (h6 << 1));
714 s[20] = static_cast<uint8_t>(h6 >> 7);
715 s[21] = static_cast<uint8_t>(h6 >> 15);
716 s[22] = static_cast<uint8_t>((h6 >> 23) | (h7 << 3));
717 s[23] = static_cast<uint8_t>(h7 >> 5);
718 s[24] = static_cast<uint8_t>(h7 >> 13);
719 s[25] = static_cast<uint8_t>((h7 >> 21) | (h8 << 4));
720 s[26] = static_cast<uint8_t>(h8 >> 4);
721 s[27] = static_cast<uint8_t>(h8 >> 12);
722 s[28] = static_cast<uint8_t>((h8 >> 20) | (h9 << 6));
723 s[29] = static_cast<uint8_t>(h9 >> 2);
724 s[30] = static_cast<uint8_t>(h9 >> 10);
725 s[31] = static_cast<uint8_t>(h9 >> 18);
726}
void carry0(int64_t &h0, int64_t &h1)

References Botan::carry0().

Referenced by is_negative(), and is_zero().

◆ sqr()

Ed25519_FieldElement Botan::Ed25519_FieldElement::sqr ( ) const
inline

Definition at line 119 of file ed25519_fe.h.

119{ return sqr_iter(1); }
Ed25519_FieldElement sqr_iter(size_t iter) const

References Ed25519_FieldElement(), and sqr_iter().

Referenced by invert(), and pow_22523().

◆ sqr2()

Ed25519_FieldElement Botan::Ed25519_FieldElement::sqr2 ( ) const

Definition at line 466 of file ed25519_fe.cpp.

466 {
467 const int32_t f0 = m_fe[0];
468 const int32_t f1 = m_fe[1];
469 const int32_t f2 = m_fe[2];
470 const int32_t f3 = m_fe[3];
471 const int32_t f4 = m_fe[4];
472 const int32_t f5 = m_fe[5];
473 const int32_t f6 = m_fe[6];
474 const int32_t f7 = m_fe[7];
475 const int32_t f8 = m_fe[8];
476 const int32_t f9 = m_fe[9];
477
478 const int32_t f0_2 = 2 * f0;
479 const int32_t f1_2 = 2 * f1;
480 const int32_t f2_2 = 2 * f2;
481 const int32_t f3_2 = 2 * f3;
482 const int32_t f4_2 = 2 * f4;
483 const int32_t f5_2 = 2 * f5;
484 const int32_t f6_2 = 2 * f6;
485 const int32_t f7_2 = 2 * f7;
486 const int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
487 const int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
488 const int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
489 const int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
490 const int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
491 const int64_t f0f0 = f0 * static_cast<int64_t>(f0);
492 const int64_t f0f1_2 = f0_2 * static_cast<int64_t>(f1);
493 const int64_t f0f2_2 = f0_2 * static_cast<int64_t>(f2);
494 const int64_t f0f3_2 = f0_2 * static_cast<int64_t>(f3);
495 const int64_t f0f4_2 = f0_2 * static_cast<int64_t>(f4);
496 const int64_t f0f5_2 = f0_2 * static_cast<int64_t>(f5);
497 const int64_t f0f6_2 = f0_2 * static_cast<int64_t>(f6);
498 const int64_t f0f7_2 = f0_2 * static_cast<int64_t>(f7);
499 const int64_t f0f8_2 = f0_2 * static_cast<int64_t>(f8);
500 const int64_t f0f9_2 = f0_2 * static_cast<int64_t>(f9);
501 const int64_t f1f1_2 = f1_2 * static_cast<int64_t>(f1);
502 const int64_t f1f2_2 = f1_2 * static_cast<int64_t>(f2);
503 const int64_t f1f3_4 = f1_2 * static_cast<int64_t>(f3_2);
504 const int64_t f1f4_2 = f1_2 * static_cast<int64_t>(f4);
505 const int64_t f1f5_4 = f1_2 * static_cast<int64_t>(f5_2);
506 const int64_t f1f6_2 = f1_2 * static_cast<int64_t>(f6);
507 const int64_t f1f7_4 = f1_2 * static_cast<int64_t>(f7_2);
508 const int64_t f1f8_2 = f1_2 * static_cast<int64_t>(f8);
509 const int64_t f1f9_76 = f1_2 * static_cast<int64_t>(f9_38);
510 const int64_t f2f2 = f2 * static_cast<int64_t>(f2);
511 const int64_t f2f3_2 = f2_2 * static_cast<int64_t>(f3);
512 const int64_t f2f4_2 = f2_2 * static_cast<int64_t>(f4);
513 const int64_t f2f5_2 = f2_2 * static_cast<int64_t>(f5);
514 const int64_t f2f6_2 = f2_2 * static_cast<int64_t>(f6);
515 const int64_t f2f7_2 = f2_2 * static_cast<int64_t>(f7);
516 const int64_t f2f8_38 = f2_2 * static_cast<int64_t>(f8_19);
517 const int64_t f2f9_38 = f2 * static_cast<int64_t>(f9_38);
518 const int64_t f3f3_2 = f3_2 * static_cast<int64_t>(f3);
519 const int64_t f3f4_2 = f3_2 * static_cast<int64_t>(f4);
520 const int64_t f3f5_4 = f3_2 * static_cast<int64_t>(f5_2);
521 const int64_t f3f6_2 = f3_2 * static_cast<int64_t>(f6);
522 const int64_t f3f7_76 = f3_2 * static_cast<int64_t>(f7_38);
523 const int64_t f3f8_38 = f3_2 * static_cast<int64_t>(f8_19);
524 const int64_t f3f9_76 = f3_2 * static_cast<int64_t>(f9_38);
525 const int64_t f4f4 = f4 * static_cast<int64_t>(f4);
526 const int64_t f4f5_2 = f4_2 * static_cast<int64_t>(f5);
527 const int64_t f4f6_38 = f4_2 * static_cast<int64_t>(f6_19);
528 const int64_t f4f7_38 = f4 * static_cast<int64_t>(f7_38);
529 const int64_t f4f8_38 = f4_2 * static_cast<int64_t>(f8_19);
530 const int64_t f4f9_38 = f4 * static_cast<int64_t>(f9_38);
531 const int64_t f5f5_38 = f5 * static_cast<int64_t>(f5_38);
532 const int64_t f5f6_38 = f5_2 * static_cast<int64_t>(f6_19);
533 const int64_t f5f7_76 = f5_2 * static_cast<int64_t>(f7_38);
534 const int64_t f5f8_38 = f5_2 * static_cast<int64_t>(f8_19);
535 const int64_t f5f9_76 = f5_2 * static_cast<int64_t>(f9_38);
536 const int64_t f6f6_19 = f6 * static_cast<int64_t>(f6_19);
537 const int64_t f6f7_38 = f6 * static_cast<int64_t>(f7_38);
538 const int64_t f6f8_38 = f6_2 * static_cast<int64_t>(f8_19);
539 const int64_t f6f9_38 = f6 * static_cast<int64_t>(f9_38);
540 const int64_t f7f7_38 = f7 * static_cast<int64_t>(f7_38);
541 const int64_t f7f8_38 = f7_2 * static_cast<int64_t>(f8_19);
542 const int64_t f7f9_76 = f7_2 * static_cast<int64_t>(f9_38);
543 const int64_t f8f8_19 = f8 * static_cast<int64_t>(f8_19);
544 const int64_t f8f9_38 = f8 * static_cast<int64_t>(f9_38);
545 const int64_t f9f9_38 = f9 * static_cast<int64_t>(f9_38);
546
547 int64_t h0 = f0f0 + f1f9_76 + f2f8_38 + f3f7_76 + f4f6_38 + f5f5_38;
548 int64_t h1 = f0f1_2 + f2f9_38 + f3f8_38 + f4f7_38 + f5f6_38;
549 int64_t h2 = f0f2_2 + f1f1_2 + f3f9_76 + f4f8_38 + f5f7_76 + f6f6_19;
550 int64_t h3 = f0f3_2 + f1f2_2 + f4f9_38 + f5f8_38 + f6f7_38;
551 int64_t h4 = f0f4_2 + f1f3_4 + f2f2 + f5f9_76 + f6f8_38 + f7f7_38;
552 int64_t h5 = f0f5_2 + f1f4_2 + f2f3_2 + f6f9_38 + f7f8_38;
553 int64_t h6 = f0f6_2 + f1f5_4 + f2f4_2 + f3f3_2 + f7f9_76 + f8f8_19;
554 int64_t h7 = f0f7_2 + f1f6_2 + f2f5_2 + f3f4_2 + f8f9_38;
555 int64_t h8 = f0f8_2 + f1f7_4 + f2f6_2 + f3f5_4 + f4f4 + f9f9_38;
556 int64_t h9 = f0f9_2 + f1f8_2 + f2f7_2 + f3f6_2 + f4f5_2;
557
558 h0 += h0;
559 h1 += h1;
560 h2 += h2;
561 h3 += h3;
562 h4 += h4;
563 h5 += h5;
564 h6 += h6;
565 h7 += h7;
566 h8 += h8;
567 h9 += h9;
568
569 carry<26>(h0, h1);
570 carry<26>(h4, h5);
571
572 carry<25>(h1, h2);
573 carry<25>(h5, h6);
574
575 carry<26>(h2, h3);
576 carry<26>(h6, h7);
577
578 carry<25>(h3, h4);
579 carry<25>(h7, h8);
580 carry<26>(h4, h5);
581 carry<26>(h8, h9);
582 carry<25, 19>(h9, h0);
583 carry<26>(h0, h1);
584
585 return Ed25519_FieldElement(h0, h1, h2, h3, h4, h5, h6, h7, h8, h9);
586}

References Botan::carry(), and Ed25519_FieldElement().

◆ sqr_iter()

Ed25519_FieldElement Botan::Ed25519_FieldElement::sqr_iter ( size_t iter) const

Definition at line 326 of file ed25519_fe.cpp.

326 {
327 int32_t f0 = m_fe[0];
328 int32_t f1 = m_fe[1];
329 int32_t f2 = m_fe[2];
330 int32_t f3 = m_fe[3];
331 int32_t f4 = m_fe[4];
332 int32_t f5 = m_fe[5];
333 int32_t f6 = m_fe[6];
334 int32_t f7 = m_fe[7];
335 int32_t f8 = m_fe[8];
336 int32_t f9 = m_fe[9];
337
338 for(size_t i = 0; i != iter; ++i) {
339 const int32_t f0_2 = 2 * f0;
340 const int32_t f1_2 = 2 * f1;
341 const int32_t f2_2 = 2 * f2;
342 const int32_t f3_2 = 2 * f3;
343 const int32_t f4_2 = 2 * f4;
344 const int32_t f5_2 = 2 * f5;
345 const int32_t f6_2 = 2 * f6;
346 const int32_t f7_2 = 2 * f7;
347 const int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
348 const int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
349 const int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
350 const int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
351 const int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
352
353 const int64_t f0f0 = f0 * static_cast<int64_t>(f0);
354 const int64_t f0f1_2 = f0_2 * static_cast<int64_t>(f1);
355 const int64_t f0f2_2 = f0_2 * static_cast<int64_t>(f2);
356 const int64_t f0f3_2 = f0_2 * static_cast<int64_t>(f3);
357 const int64_t f0f4_2 = f0_2 * static_cast<int64_t>(f4);
358 const int64_t f0f5_2 = f0_2 * static_cast<int64_t>(f5);
359 const int64_t f0f6_2 = f0_2 * static_cast<int64_t>(f6);
360 const int64_t f0f7_2 = f0_2 * static_cast<int64_t>(f7);
361 const int64_t f0f8_2 = f0_2 * static_cast<int64_t>(f8);
362 const int64_t f0f9_2 = f0_2 * static_cast<int64_t>(f9);
363 const int64_t f1f1_2 = f1_2 * static_cast<int64_t>(f1);
364 const int64_t f1f2_2 = f1_2 * static_cast<int64_t>(f2);
365 const int64_t f1f3_4 = f1_2 * static_cast<int64_t>(f3_2);
366 const int64_t f1f4_2 = f1_2 * static_cast<int64_t>(f4);
367 const int64_t f1f5_4 = f1_2 * static_cast<int64_t>(f5_2);
368 const int64_t f1f6_2 = f1_2 * static_cast<int64_t>(f6);
369 const int64_t f1f7_4 = f1_2 * static_cast<int64_t>(f7_2);
370 const int64_t f1f8_2 = f1_2 * static_cast<int64_t>(f8);
371 const int64_t f1f9_76 = f1_2 * static_cast<int64_t>(f9_38);
372 const int64_t f2f2 = f2 * static_cast<int64_t>(f2);
373 const int64_t f2f3_2 = f2_2 * static_cast<int64_t>(f3);
374 const int64_t f2f4_2 = f2_2 * static_cast<int64_t>(f4);
375 const int64_t f2f5_2 = f2_2 * static_cast<int64_t>(f5);
376 const int64_t f2f6_2 = f2_2 * static_cast<int64_t>(f6);
377 const int64_t f2f7_2 = f2_2 * static_cast<int64_t>(f7);
378 const int64_t f2f8_38 = f2_2 * static_cast<int64_t>(f8_19);
379 const int64_t f2f9_38 = f2 * static_cast<int64_t>(f9_38);
380 const int64_t f3f3_2 = f3_2 * static_cast<int64_t>(f3);
381 const int64_t f3f4_2 = f3_2 * static_cast<int64_t>(f4);
382 const int64_t f3f5_4 = f3_2 * static_cast<int64_t>(f5_2);
383 const int64_t f3f6_2 = f3_2 * static_cast<int64_t>(f6);
384 const int64_t f3f7_76 = f3_2 * static_cast<int64_t>(f7_38);
385 const int64_t f3f8_38 = f3_2 * static_cast<int64_t>(f8_19);
386 const int64_t f3f9_76 = f3_2 * static_cast<int64_t>(f9_38);
387 const int64_t f4f4 = f4 * static_cast<int64_t>(f4);
388 const int64_t f4f5_2 = f4_2 * static_cast<int64_t>(f5);
389 const int64_t f4f6_38 = f4_2 * static_cast<int64_t>(f6_19);
390 const int64_t f4f7_38 = f4 * static_cast<int64_t>(f7_38);
391 const int64_t f4f8_38 = f4_2 * static_cast<int64_t>(f8_19);
392 const int64_t f4f9_38 = f4 * static_cast<int64_t>(f9_38);
393 const int64_t f5f5_38 = f5 * static_cast<int64_t>(f5_38);
394 const int64_t f5f6_38 = f5_2 * static_cast<int64_t>(f6_19);
395 const int64_t f5f7_76 = f5_2 * static_cast<int64_t>(f7_38);
396 const int64_t f5f8_38 = f5_2 * static_cast<int64_t>(f8_19);
397 const int64_t f5f9_76 = f5_2 * static_cast<int64_t>(f9_38);
398 const int64_t f6f6_19 = f6 * static_cast<int64_t>(f6_19);
399 const int64_t f6f7_38 = f6 * static_cast<int64_t>(f7_38);
400 const int64_t f6f8_38 = f6_2 * static_cast<int64_t>(f8_19);
401 const int64_t f6f9_38 = f6 * static_cast<int64_t>(f9_38);
402 const int64_t f7f7_38 = f7 * static_cast<int64_t>(f7_38);
403 const int64_t f7f8_38 = f7_2 * static_cast<int64_t>(f8_19);
404 const int64_t f7f9_76 = f7_2 * static_cast<int64_t>(f9_38);
405 const int64_t f8f8_19 = f8 * static_cast<int64_t>(f8_19);
406 const int64_t f8f9_38 = f8 * static_cast<int64_t>(f9_38);
407 const int64_t f9f9_38 = f9 * static_cast<int64_t>(f9_38);
408
409 int64_t h0 = f0f0 + f1f9_76 + f2f8_38 + f3f7_76 + f4f6_38 + f5f5_38;
410 int64_t h1 = f0f1_2 + f2f9_38 + f3f8_38 + f4f7_38 + f5f6_38;
411 int64_t h2 = f0f2_2 + f1f1_2 + f3f9_76 + f4f8_38 + f5f7_76 + f6f6_19;
412 int64_t h3 = f0f3_2 + f1f2_2 + f4f9_38 + f5f8_38 + f6f7_38;
413 int64_t h4 = f0f4_2 + f1f3_4 + f2f2 + f5f9_76 + f6f8_38 + f7f7_38;
414 int64_t h5 = f0f5_2 + f1f4_2 + f2f3_2 + f6f9_38 + f7f8_38;
415 int64_t h6 = f0f6_2 + f1f5_4 + f2f4_2 + f3f3_2 + f7f9_76 + f8f8_19;
416 int64_t h7 = f0f7_2 + f1f6_2 + f2f5_2 + f3f4_2 + f8f9_38;
417 int64_t h8 = f0f8_2 + f1f7_4 + f2f6_2 + f3f5_4 + f4f4 + f9f9_38;
418 int64_t h9 = f0f9_2 + f1f8_2 + f2f7_2 + f3f6_2 + f4f5_2;
419
420 carry<26>(h0, h1);
421 carry<26>(h4, h5);
422 carry<25>(h1, h2);
423 carry<25>(h5, h6);
424 carry<26>(h2, h3);
425 carry<26>(h6, h7);
426
427 carry<25>(h3, h4);
428 carry<25>(h7, h8);
429
430 carry<26>(h4, h5);
431 carry<26>(h8, h9);
432 carry<25, 19>(h9, h0);
433 carry<26>(h0, h1);
434
435 f0 = static_cast<int32_t>(h0);
436 f1 = static_cast<int32_t>(h1);
437 f2 = static_cast<int32_t>(h2);
438 f3 = static_cast<int32_t>(h3);
439 f4 = static_cast<int32_t>(h4);
440 f5 = static_cast<int32_t>(h5);
441 f6 = static_cast<int32_t>(h6);
442 f7 = static_cast<int32_t>(h7);
443 f8 = static_cast<int32_t>(h8);
444 f9 = static_cast<int32_t>(h9);
445 }
446
447 return Ed25519_FieldElement(f0, f1, f2, f3, f4, f5, f6, f7, f8, f9);
448}

References Botan::carry(), and Ed25519_FieldElement().

Referenced by sqr().

◆ sub()

Ed25519_FieldElement Botan::Ed25519_FieldElement::sub ( const Ed25519_FieldElement & a,
const Ed25519_FieldElement & b )
inlinestatic

Definition at line 99 of file ed25519_fe.h.

99 {
101 for(size_t i = 0; i != 10; ++i) {
102 z.m_fe[i] = a.m_fe[i] - b.m_fe[i];
103 }
104 return z;
105 }

References Ed25519_FieldElement().

Referenced by Botan::operator-().

◆ zero()

constexpr Ed25519_FieldElement Botan::Ed25519_FieldElement::zero ( )
inlinestaticconstexpr

Definition at line 36 of file ed25519_fe.h.

36{ return Ed25519_FieldElement(); }

References Ed25519_FieldElement().


The documentation for this class was generated from the following files: