Botan 3.14.1
Crypto and TLS for C&
x25519_fe.h
Go to the documentation of this file.
1/*
2* (C) 2014,2018,2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7/*
8* The field arithmetic is based on curve25519-donna-c64.c from
9* https://github.com/agl/curve25519-donna
10* revision 80ad9b9930c9baef5829dd2a235b6b7646d32a8e
11*
12* Copyright 2008, Google Inc.
13* All rights reserved.
14*
15* Code released into the public domain.
16*/
17
18#ifndef BOTAN_X25519_FE_H_
19#define BOTAN_X25519_FE_H_
20
21#include <botan/types.h>
22#include <botan/internal/ct_utils.h>
23#include <botan/internal/donna128.h>
24#include <botan/internal/loadstor.h>
25#include <array>
26#include <span>
27
28/*
29* Everything here is force inlined so that the whole scalar multiplication
30* compiles into a single function in each translation unit that uses it,
31* without any out of line copies that the linker might merge.
32*/
33
34namespace Botan {
35
36#if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
38#endif
39
40/**
41* An element of GF(2^255 - 19) in radix 2^51
42*
43* The value is sum(limb[i] * 2^(51*i)) over the five limbs. Limbs are not
44* reduced below 2^51 between operations; instead the bounds from the original
45* donna analysis are maintained:
46*
47* - mul and sqr return limbs below 2^52 (in fact at most 2^51 + 2^13)
48* - adding two such results gives limbs below 2^53
49* - subtracting two such results adds 8p to avoid underflow, giving limbs
50* below 2^52 + 2^54 < 2^55
51* - mul, sqr and mul_a24 accept any such sum or difference as input
52*
53* The ladder never chains an addition or subtraction into another addition or
54* subtraction without a multiplication or squaring in between.
55*/
56class X25519_FE final {
57 public:
58 /// The zero element
59 constexpr X25519_FE() : m_v{} {}
60
61 constexpr static X25519_FE one() {
62 X25519_FE r;
63 r.m_v[0] = 1;
64 return r;
65 }
66
67 /**
68 * Decode 32 little endian bytes
69 *
70 * The high bit of the final byte is ignored (RFC 7748 Section 5); the
71 * value is not reduced, which is fine since the inputs are only used as
72 * multiplication operands.
73 */
74 BOTAN_FORCE_INLINE static X25519_FE decode(std::span<const uint8_t, 32> in) {
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 }
83
84 /**
85 * Encode the canonical value in [0,p) as 32 little endian bytes
86 */
87 BOTAN_FORCE_INLINE void encode(std::span<uint8_t, 32> out) const {
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 }
149
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 }
157
158 /**
159 * Subtraction, computed as a + 8p - b so that no limb underflows
160 */
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 }
174
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 }
202
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 }
225
227 X25519_FE r = *this;
228 for(size_t i = 0; i != n; ++i) {
229 r = r.sqr();
230 }
231 return r;
232 }
233
234 /**
235 * Multiply by a24 = (A - 2) / 4 = 121665, the ladder constant
236 */
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 }
261
262 /**
263 * Inversion via FLT
264 *
265 * Returns zero for a zero input, which is what the ladder relies on for
266 * the identity (and the all-zero shared secret for low order points).
267 */
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 }
294
295 /**
296 * Swap a and b if the mask is set
297 */
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 }
305
306 private:
307 static constexpr uint64_t MASK_51 = (static_cast<uint64_t>(1) << 51) - 1;
308
309 BOTAN_FORCE_INLINE static uint128_t mul(uint64_t a, uint64_t b) { return uint128_t(a) * b; }
310
311 /**
312 * Propagate the carries of a product, leaving limbs below 2^52
313 */
314 BOTAN_FORCE_INLINE static X25519_FE carry(
315 const uint128_t& t0, uint128_t t1, uint128_t t2, uint128_t t3, uint128_t t4) {
316 X25519_FE r;
317
318 r.m_v[0] = t0 & MASK_51;
319 t1 += carry_shift(t0, 51);
320 r.m_v[1] = t1 & MASK_51;
321 t2 += carry_shift(t1, 51);
322 r.m_v[2] = t2 & MASK_51;
323 t3 += carry_shift(t2, 51);
324 r.m_v[3] = t3 & MASK_51;
325 t4 += carry_shift(t3, 51);
326 r.m_v[4] = t4 & MASK_51;
327
328 // The carry out of the top limb wraps to 2^255 == 19
329 r.m_v[0] += carry_shift(t4, 51) * 19;
330 r.m_v[1] += r.m_v[0] >> 51;
331 r.m_v[0] &= MASK_51;
332
333 return r;
334 }
335
336 std::array<uint64_t, 5> m_v;
337};
338
339/**
340* The X25519 Montgomery ladder (RFC 7748 Section 5)
341*
342* Computes the u-coordinate of [k]P where P is the point with u-coordinate u.
343* The scalar must already be clamped.
344*/
345BOTAN_FORCE_INLINE void x25519_ladder(std::span<uint8_t, 32> out,
346 std::span<const uint8_t, 32> k,
347 std::span<const uint8_t, 32> u) {
348 const auto x1 = X25519_FE::decode(u);
349
350 auto x2 = X25519_FE::one();
351 auto z2 = X25519_FE();
352 auto x3 = x1;
353 auto z3 = X25519_FE::one();
354
355 auto swap = CT::Mask<uint64_t>::cleared();
356
357 // Bit 255 of a clamped scalar is always zero, so start at bit 254
358 for(size_t t = 255; t-- > 0;) {
359 const auto kt = CT::Mask<uint64_t>::expand_bit(static_cast<uint64_t>(k[t / 8]), t % 8);
360 swap = swap ^ kt;
361 X25519_FE::conditional_swap(swap, x2, x3);
362 X25519_FE::conditional_swap(swap, z2, z3);
363 swap = kt;
364
365 const auto A = x2 + z2;
366 const auto B = x2 - z2;
367 const auto C = x3 + z3;
368 const auto D = x3 - z3;
369 const auto AA = A.sqr();
370 const auto BB = B.sqr();
371 const auto E = AA - BB;
372 const auto DA = D * A;
373 const auto CB = C * B;
374
375 x3 = (DA + CB).sqr();
376 z3 = x1 * (DA - CB).sqr();
377 x2 = AA * BB;
378 z2 = E * (AA + E.mul_a24());
379 }
380
381 X25519_FE::conditional_swap(swap, x2, x3);
382 X25519_FE::conditional_swap(swap, z2, z3);
383
384 const auto result = x2 * z2.invert();
385 result.encode(out);
386}
387
388} // namespace Botan
389
390#endif
static constexpr Mask< T > expand_bit(T v, size_t bit)
Definition ct_utils.h:426
constexpr T if_set_return(T x) const
Definition ct_utils.h:543
static constexpr Mask< T > cleared()
Definition ct_utils.h:392
BOTAN_FORCE_INLINE friend X25519_FE operator-(const X25519_FE &a, const X25519_FE &b)
Definition x25519_fe.h:161
static constexpr X25519_FE one()
Definition x25519_fe.h:61
constexpr X25519_FE()
The zero element.
Definition x25519_fe.h:59
BOTAN_FORCE_INLINE void encode(std::span< uint8_t, 32 > out) const
Definition x25519_fe.h:87
static BOTAN_FORCE_INLINE void conditional_swap(CT::Mask< uint64_t > swap, X25519_FE &a, X25519_FE &b)
Definition x25519_fe.h:298
BOTAN_FORCE_INLINE X25519_FE invert() const
Definition x25519_fe.h:268
BOTAN_FORCE_INLINE friend X25519_FE operator*(const X25519_FE &a, const X25519_FE &b)
Definition x25519_fe.h:175
BOTAN_FORCE_INLINE X25519_FE sqr_n(size_t n) const
Definition x25519_fe.h:226
BOTAN_FORCE_INLINE X25519_FE sqr() const
Definition x25519_fe.h:203
BOTAN_FORCE_INLINE friend X25519_FE operator+(const X25519_FE &a, const X25519_FE &b)
Definition x25519_fe.h:150
static BOTAN_FORCE_INLINE X25519_FE decode(std::span< const uint8_t, 32 > in)
Definition x25519_fe.h:74
BOTAN_FORCE_INLINE X25519_FE mul_a24() const
Definition x25519_fe.h:237
#define BOTAN_FORCE_INLINE
Definition compiler.h:86
constexpr uint64_t carry_shift(const donna128 &a, size_t shift)
Definition donna128.h:129
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
donna128 uint128_t
Definition x25519_fe.h:37
BOTAN_FORCE_INLINE void x25519_ladder(std::span< uint8_t, 32 > out, std::span< const uint8_t, 32 > k, std::span< const uint8_t, 32 > u)
Definition x25519_fe.h:345
constexpr uint64_t combine_lower(const donna128 &a, size_t s1, const donna128 &b, size_t s2)
Definition donna128.h:133