Botan 3.14.1
Crypto and TLS for C&
Botan::X25519_FE Class Referencefinal

#include <x25519_fe.h>

Public Member Functions

BOTAN_FORCE_INLINE void encode (std::span< uint8_t, 32 > out) const
BOTAN_FORCE_INLINE X25519_FE invert () const
BOTAN_FORCE_INLINE X25519_FE mul_a24 () const
BOTAN_FORCE_INLINE X25519_FE sqr () const
BOTAN_FORCE_INLINE X25519_FE sqr_n (size_t n) const
constexpr X25519_FE ()
 The zero element.

Static Public Member Functions

static BOTAN_FORCE_INLINE void conditional_swap (CT::Mask< uint64_t > swap, X25519_FE &a, X25519_FE &b)
static BOTAN_FORCE_INLINE X25519_FE decode (std::span< const uint8_t, 32 > in)
static constexpr X25519_FE one ()

Friends

BOTAN_FORCE_INLINE friend X25519_FE operator* (const X25519_FE &a, const X25519_FE &b)
BOTAN_FORCE_INLINE friend X25519_FE operator+ (const X25519_FE &a, const X25519_FE &b)
BOTAN_FORCE_INLINE friend X25519_FE operator- (const X25519_FE &a, const X25519_FE &b)

Detailed Description

An element of GF(2^255 - 19) in radix 2^51

The value is sum(limb[i] * 2^(51*i)) over the five limbs. Limbs are not reduced below 2^51 between operations; instead the bounds from the original donna analysis are maintained:

  • mul and sqr return limbs below 2^52 (in fact at most 2^51 + 2^13)
  • adding two such results gives limbs below 2^53
  • subtracting two such results adds 8p to avoid underflow, giving limbs below 2^52 + 2^54 < 2^55
  • mul, sqr and mul_a24 accept any such sum or difference as input

The ladder never chains an addition or subtraction into another addition or subtraction without a multiplication or squaring in between.

Definition at line 56 of file x25519_fe.h.

Constructor & Destructor Documentation

◆ X25519_FE()

Botan::X25519_FE::X25519_FE ( )
inlineconstexpr

The zero element.

Definition at line 59 of file x25519_fe.h.

59: m_v{} {}

Referenced by conditional_swap(), decode(), invert(), mul_a24(), one(), operator*, operator+, operator-, sqr(), and sqr_n().

Member Function Documentation

◆ conditional_swap()

BOTAN_FORCE_INLINE void Botan::X25519_FE::conditional_swap ( CT::Mask< uint64_t > swap,
X25519_FE & a,
X25519_FE & b )
inlinestatic

Swap a and b if the mask is set

Definition at line 298 of file x25519_fe.h.

298 {
299 for(size_t i = 0; i != 5; ++i) {
300 const uint64_t x = swap.if_set_return(a.m_v[i] ^ b.m_v[i]);
301 a.m_v[i] ^= x;
302 b.m_v[i] ^= x;
303 }
304 }

References BOTAN_FORCE_INLINE, Botan::CT::Mask< T >::if_set_return(), and X25519_FE().

Referenced by Botan::x25519_ladder().

◆ decode()

BOTAN_FORCE_INLINE X25519_FE Botan::X25519_FE::decode ( std::span< const uint8_t, 32 > in)
inlinestatic

Decode 32 little endian bytes

The high bit of the final byte is ignored (RFC 7748 Section 5); the value is not reduced, which is fine since the inputs are only used as multiplication operands.

Definition at line 74 of file x25519_fe.h.

74 {
75 X25519_FE r;
76 r.m_v[0] = load_le<uint64_t>(in.data(), 0) & MASK_51;
77 r.m_v[1] = (load_le<uint64_t>(in.data() + 6, 0) >> 3) & MASK_51;
78 r.m_v[2] = (load_le<uint64_t>(in.data() + 12, 0) >> 6) & MASK_51;
79 r.m_v[3] = (load_le<uint64_t>(in.data() + 19, 0) >> 1) & MASK_51;
80 r.m_v[4] = (load_le<uint64_t>(in.data() + 24, 0) >> 12) & MASK_51;
81 return r;
82 }
constexpr X25519_FE()
The zero element.
Definition x25519_fe.h:59
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495

References BOTAN_FORCE_INLINE, Botan::load_le(), and X25519_FE().

Referenced by Botan::x25519_ladder().

◆ encode()

BOTAN_FORCE_INLINE void Botan::X25519_FE::encode ( std::span< uint8_t, 32 > out) const
inline

Encode the canonical value in [0,p) as 32 little endian bytes

Definition at line 87 of file x25519_fe.h.

87 {
88 auto t0 = uint128_t(m_v[0]);
89 auto t1 = uint128_t(m_v[1]);
90 auto t2 = uint128_t(m_v[2]);
91 auto t3 = uint128_t(m_v[3]);
92 auto t4 = uint128_t(m_v[4]);
93
94 for(size_t i = 0; i != 2; ++i) {
95 t1 += t0 >> 51U;
96 t0 &= MASK_51;
97 t2 += t1 >> 51U;
98 t1 &= MASK_51;
99 t3 += t2 >> 51U;
100 t2 &= MASK_51;
101 t4 += t3 >> 51U;
102 t3 &= MASK_51;
103 t0 += (t4 >> 51U) * 19;
104 t4 &= MASK_51;
105 }
106
107 /* now t is between 0 and 2^255-1, properly carried. */
108 /* case 1: between 0 and 2^255-20. case 2: between 2^255-19 and 2^255-1. */
109
110 t0 += 19;
111
112 t1 += t0 >> 51U;
113 t0 &= MASK_51;
114 t2 += t1 >> 51U;
115 t1 &= MASK_51;
116 t3 += t2 >> 51U;
117 t2 &= MASK_51;
118 t4 += t3 >> 51U;
119 t3 &= MASK_51;
120 t0 += (t4 >> 51U) * 19;
121 t4 &= MASK_51;
122
123 /* now between 19 and 2^255-1 in both cases, and offset by 19. */
124
125 t0 += 0x8000000000000 - 19;
126 t1 += 0x8000000000000 - 1;
127 t2 += 0x8000000000000 - 1;
128 t3 += 0x8000000000000 - 1;
129 t4 += 0x8000000000000 - 1;
130
131 /* now between 2^255 and 2^256-20, and offset by 2^255. */
132
133 t1 += t0 >> 51U;
134 t0 &= MASK_51;
135 t2 += t1 >> 51U;
136 t1 &= MASK_51;
137 t3 += t2 >> 51U;
138 t2 &= MASK_51;
139 t4 += t3 >> 51U;
140 t3 &= MASK_51;
141 t4 &= MASK_51;
142
143 store_le(out.data(),
144 combine_lower(t0, 0, t1, 51),
145 combine_lower(t1, 13, t2, 38),
146 combine_lower(t2, 26, t3, 25),
147 combine_lower(t3, 39, t4, 12));
148 }
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
donna128 uint128_t
Definition x25519_fe.h:37
constexpr uint64_t combine_lower(const donna128 &a, size_t s1, const donna128 &b, size_t s2)
Definition donna128.h:133

References BOTAN_FORCE_INLINE, Botan::combine_lower(), and Botan::store_le().

◆ invert()

BOTAN_FORCE_INLINE X25519_FE Botan::X25519_FE::invert ( ) const
inline

Inversion via FLT

Returns zero for a zero input, which is what the ladder relies on for the identity (and the all-zero shared secret for low order points).

Definition at line 268 of file x25519_fe.h.

268 {
269 const auto& z = *this;
270
271 auto a = z.sqr(); // 2
272 auto t = a.sqr_n(2); // 8
273 auto b = t * z; // 9
274 a = b * a; // 11
275 t = a.sqr(); // 22
276 b = t * b; // 2^5 - 2^0 = 31
277 t = b.sqr_n(5); // 2^10 - 2^5
278 b = t * b; // 2^10 - 2^0
279 t = b.sqr_n(10); // 2^20 - 2^10
280 auto c = t * b; // 2^20 - 2^0
281 t = c.sqr_n(20); // 2^40 - 2^20
282 t = t * c; // 2^40 - 2^0
283 t = t.sqr_n(10); // 2^50 - 2^10
284 b = t * b; // 2^50 - 2^0
285 t = b.sqr_n(50); // 2^100 - 2^50
286 c = t * b; // 2^100 - 2^0
287 t = c.sqr_n(100); // 2^200 - 2^100
288 t = t * c; // 2^200 - 2^0
289 t = t.sqr_n(50); // 2^250 - 2^50
290 t = t * b; // 2^250 - 2^0
291 t = t.sqr_n(5); // 2^255 - 2^5
292 return t * a; // 2^255 - 21
293 }

References BOTAN_FORCE_INLINE, sqr(), sqr_n(), and X25519_FE().

◆ mul_a24()

BOTAN_FORCE_INLINE X25519_FE Botan::X25519_FE::mul_a24 ( ) const
inline

Multiply by a24 = (A - 2) / 4 = 121665, the ladder constant

Definition at line 237 of file x25519_fe.h.

237 {
238 constexpr uint64_t a24 = 121665;
239
240 X25519_FE r;
241
242 uint128_t t = mul(m_v[0], a24);
243 r.m_v[0] = t & MASK_51;
244
245 t = mul(m_v[1], a24) + carry_shift(t, 51);
246 r.m_v[1] = t & MASK_51;
247
248 t = mul(m_v[2], a24) + carry_shift(t, 51);
249 r.m_v[2] = t & MASK_51;
250
251 t = mul(m_v[3], a24) + carry_shift(t, 51);
252 r.m_v[3] = t & MASK_51;
253
254 t = mul(m_v[4], a24) + carry_shift(t, 51);
255 r.m_v[4] = t & MASK_51;
256
257 r.m_v[0] += carry_shift(t, 51) * 19;
258
259 return r;
260 }
constexpr uint64_t carry_shift(const donna128 &a, size_t shift)
Definition donna128.h:129

References BOTAN_FORCE_INLINE, Botan::carry_shift(), and X25519_FE().

◆ one()

constexpr X25519_FE Botan::X25519_FE::one ( )
inlinestaticconstexpr

Definition at line 61 of file x25519_fe.h.

61 {
62 X25519_FE r;
63 r.m_v[0] = 1;
64 return r;
65 }

References X25519_FE().

Referenced by Botan::x25519_ladder().

◆ sqr()

BOTAN_FORCE_INLINE X25519_FE Botan::X25519_FE::sqr ( ) const
inline

Definition at line 203 of file x25519_fe.h.

203 {
204 const uint64_t a0 = m_v[0];
205 const uint64_t a1 = m_v[1];
206 const uint64_t a2 = m_v[2];
207 const uint64_t a3 = m_v[3];
208 const uint64_t a4 = m_v[4];
209
210 const uint64_t a0_2 = a0 * 2;
211 const uint64_t a1_2 = a1 * 2;
212 const uint64_t a2_38 = a2 * 38;
213 const uint64_t a3_19 = a3 * 19;
214 const uint64_t a4_19 = a4 * 19;
215 const uint64_t a4_38 = a4_19 * 2;
216
217 const uint128_t t0 = mul(a0, a0) + mul(a1, a4_38) + mul(a3, a2_38);
218 const uint128_t t1 = mul(a0_2, a1) + mul(a2, a4_38) + mul(a3, a3_19);
219 const uint128_t t2 = mul(a0_2, a2) + mul(a1, a1) + mul(a3, a4_38);
220 const uint128_t t3 = mul(a0_2, a3) + mul(a1_2, a2) + mul(a4, a4_19);
221 const uint128_t t4 = mul(a0_2, a4) + mul(a1_2, a3) + mul(a2, a2);
222
223 return carry(t0, t1, t2, t3, t4);
224 }

References BOTAN_FORCE_INLINE, and X25519_FE().

Referenced by invert(), and sqr_n().

◆ sqr_n()

BOTAN_FORCE_INLINE X25519_FE Botan::X25519_FE::sqr_n ( size_t n) const
inline

Definition at line 226 of file x25519_fe.h.

226 {
227 X25519_FE r = *this;
228 for(size_t i = 0; i != n; ++i) {
229 r = r.sqr();
230 }
231 return r;
232 }

References BOTAN_FORCE_INLINE, sqr(), and X25519_FE().

Referenced by invert().

◆ operator*

BOTAN_FORCE_INLINE friend X25519_FE operator* ( const X25519_FE & a,
const X25519_FE & b )
friend

Definition at line 175 of file x25519_fe.h.

175 {
176 const uint64_t a0 = a.m_v[0];
177 const uint64_t a1 = a.m_v[1];
178 const uint64_t a2 = a.m_v[2];
179 const uint64_t a3 = a.m_v[3];
180 const uint64_t a4 = a.m_v[4];
181
182 const uint64_t b0 = b.m_v[0];
183 const uint64_t b1 = b.m_v[1];
184 const uint64_t b2 = b.m_v[2];
185 const uint64_t b3 = b.m_v[3];
186 const uint64_t b4 = b.m_v[4];
187
188 // Products that wrap past 2^255 are multiplied by 19 since 2^255 == 19 (mod p)
189 const uint64_t b1_19 = b1 * 19;
190 const uint64_t b2_19 = b2 * 19;
191 const uint64_t b3_19 = b3 * 19;
192 const uint64_t b4_19 = b4 * 19;
193
194 const uint128_t t0 = mul(a0, b0) + mul(a1, b4_19) + mul(a2, b3_19) + mul(a3, b2_19) + mul(a4, b1_19);
195 const uint128_t t1 = mul(a0, b1) + mul(a1, b0) + mul(a2, b4_19) + mul(a3, b3_19) + mul(a4, b2_19);
196 const uint128_t t2 = mul(a0, b2) + mul(a1, b1) + mul(a2, b0) + mul(a3, b4_19) + mul(a4, b3_19);
197 const uint128_t t3 = mul(a0, b3) + mul(a1, b2) + mul(a2, b1) + mul(a3, b0) + mul(a4, b4_19);
198 const uint128_t t4 = mul(a0, b4) + mul(a1, b3) + mul(a2, b2) + mul(a3, b1) + mul(a4, b0);
199
200 return carry(t0, t1, t2, t3, t4);
201 }

References BOTAN_FORCE_INLINE, and X25519_FE().

◆ operator+

BOTAN_FORCE_INLINE friend X25519_FE operator+ ( const X25519_FE & a,
const X25519_FE & b )
friend

Definition at line 150 of file x25519_fe.h.

150 {
151 X25519_FE r;
152 for(size_t i = 0; i != 5; ++i) {
153 r.m_v[i] = a.m_v[i] + b.m_v[i];
154 }
155 return r;
156 }

References BOTAN_FORCE_INLINE, and X25519_FE().

◆ operator-

BOTAN_FORCE_INLINE friend X25519_FE operator- ( const X25519_FE & a,
const X25519_FE & b )
friend

Subtraction, computed as a + 8p - b so that no limb underflows

Definition at line 161 of file x25519_fe.h.

161 {
162 // 8p = 2^258 - 152 in radix 2^51, with each limb biased to be positive
163 constexpr uint64_t two54m152 = (static_cast<uint64_t>(1) << 54) - 152;
164 constexpr uint64_t two54m8 = (static_cast<uint64_t>(1) << 54) - 8;
165
166 X25519_FE r;
167 r.m_v[0] = a.m_v[0] + two54m152 - b.m_v[0];
168 r.m_v[1] = a.m_v[1] + two54m8 - b.m_v[1];
169 r.m_v[2] = a.m_v[2] + two54m8 - b.m_v[2];
170 r.m_v[3] = a.m_v[3] + two54m8 - b.m_v[3];
171 r.m_v[4] = a.m_v[4] + two54m8 - b.m_v[4];
172 return r;
173 }

References BOTAN_FORCE_INLINE, and X25519_FE().


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