Botan 3.14.1
Crypto and TLS for C&
ed25519_ge.cpp
Go to the documentation of this file.
1/*
2* Ed25519 group operations
3* (C) 2017 Ribose Inc
4* 2025 Jack Lloyd
5*
6* Based on the public domain code from SUPERCOP ref10 by
7* Peter Schwabe, Daniel J. Bernstein, Niels Duif, Tanja Lange, Bo-Yin Yang
8*
9* Botan is released under the Simplified BSD License (see license.txt)
10*/
11
12#include <botan/internal/ed25519_internal.h>
13
14#include <botan/internal/ed25519_fe.h>
15#include <array>
16#include <memory>
17#include <span>
18
19namespace Botan {
20
21namespace {
22
23/**
24Here the group is the set of pairs (x,y) of field elements (see ed5519_fe.h)
25satisfying -x^2 + y^2 = 1 + d x^2y^2 where d = -121665/121666.
26
27Several different point representations are used in this implementation
28*/
29
30constexpr Ed25519_FieldElement ED25519_D = []() consteval {
31 // d = -121665/121666
32 const auto n = Ed25519_FieldElement::from_word(121665);
33 const auto m = Ed25519_FieldElement::from_word(121666);
34 return -(n * m.invert());
35}();
36
37constexpr Ed25519_FieldElement ED25519_D2 = ED25519_D + ED25519_D;
38
39/*
40* sqrt(-1), computed as 2^((p-1)/4); 2 is a nonresidue since p == 5 (mod 8).
41* Since (p-1)/4 = 2*((p-5)/8) + 1 this can reuse the (p-5)/8 addition chain.
42*/
43constexpr Ed25519_FieldElement ED25519_SQRTM1 = []() consteval {
44 const auto two = Ed25519_FieldElement::from_word(2);
45 return two.pow_22523().sqr() * two;
46}();
47
48/**
49* Ed25519_Point_Completed
50*
51* ((X:Z),(Y:T)) satisfying x=X/Z, y=Y/T
52*/
53class Ed25519_Point_Completed final {
54 public:
55 Ed25519_FieldElement X; // NOLINT(misc-non-private-member-variables-in-classes)
56 Ed25519_FieldElement Y; // NOLINT(misc-non-private-member-variables-in-classes)
57 Ed25519_FieldElement Z; // NOLINT(misc-non-private-member-variables-in-classes)
58 Ed25519_FieldElement T; // NOLINT(misc-non-private-member-variables-in-classes)
59};
60
61/**
62* Ed25519_Point_Projective
63*
64* (X:Y:Z) satisfying x=X/Z, y=Y/Z
65*/
66class Ed25519_Point_Projective final {
67 public:
68 Ed25519_FieldElement X; // NOLINT(misc-non-private-member-variables-in-classes)
69 Ed25519_FieldElement Y; // NOLINT(misc-non-private-member-variables-in-classes)
70 Ed25519_FieldElement Z; // NOLINT(misc-non-private-member-variables-in-classes)
71
72 /*
73 * Point conversion
74 */
75 static constexpr Ed25519_Point_Projective from(const Ed25519_Point_Completed& p) {
76 Ed25519_Point_Projective r;
77 r.X = p.X * p.T;
78 r.Y = p.Y * p.Z;
79 r.Z = p.Z * p.T;
80 return r;
81 }
82
83 static constexpr Ed25519_Point_Projective identity() {
84 Ed25519_Point_Projective h;
88 return h;
89 }
90
91 void serialize_to(std::span<uint8_t, 32> s) const {
92 const auto recip = this->Z.invert();
93 const auto x = this->X * recip;
94 const auto y = this->Y * recip;
95 y.serialize_to(s);
96 s[31] ^= x.is_negative() ? 0x80 : 0x00;
97 }
98
99 constexpr Ed25519_Point_Completed dbl() const;
100};
101
102constexpr Ed25519_Point_Completed Ed25519_Point_Projective::dbl() const {
103 Ed25519_Point_Completed r;
104 r.X = X.sqr(); // XX=X1^2
105 r.Z = Y.sqr(); // YY=Y1^2
106 r.T = Z.sqr2(); // B=2*Z1^2
107 r.Y = X + Y; // A=X1+Y1
108 const auto t0 = r.Y.sqr(); // AA=A^2
109 r.Y = r.Z + r.X; // Y3=YY+XX
110 r.Z = r.Z - r.X; // Z3=YY-XX
111 r.X = t0 - r.Y; // X3=AA-Y3
112 r.T = r.T - r.Z; // T3=B-Z3
113 return r;
114}
115
116/**
117* Ed25519_Point_Extended
118*
119* (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT
120*/
121class Ed25519_Point_Extended final {
122 public:
123 Ed25519_FieldElement X; // NOLINT(misc-non-private-member-variables-in-classes)
124 Ed25519_FieldElement Y; // NOLINT(misc-non-private-member-variables-in-classes)
125 Ed25519_FieldElement Z; // NOLINT(misc-non-private-member-variables-in-classes)
126 Ed25519_FieldElement T; // NOLINT(misc-non-private-member-variables-in-classes)
127
128 static constexpr Ed25519_Point_Extended identity() {
129 Ed25519_Point_Extended h;
130 h.X = Ed25519_FieldElement::zero();
131 h.Y = Ed25519_FieldElement::one();
132 h.Z = Ed25519_FieldElement::one();
133 h.T = Ed25519_FieldElement::zero();
134 return h;
135 }
136
137 constexpr Ed25519_Point_Completed dbl() const {
138 Ed25519_Point_Projective q;
139 q.X = X;
140 q.Y = Y;
141 q.Z = Z;
142 return q.dbl();
143 }
144
145 /**
146 * Point conversion
147 */
148 static constexpr Ed25519_Point_Extended from(const Ed25519_Point_Completed& p) {
149 Ed25519_Point_Extended r;
150 r.X = p.X * p.T;
151 r.Y = p.Y * p.Z;
152 r.Z = p.Z * p.T;
153 r.T = p.X * p.Y;
154 return r;
155 }
156
157 void serialize_to(std::span<uint8_t, 32> out) const {
158 const auto recip = this->Z.invert();
159 const auto x = this->X * recip;
160 const auto y = this->Y * recip;
161 y.serialize_to(out);
162 out[31] ^= x.is_negative() ? 0x80 : 0x00;
163 }
164};
165
166/**
167* Ed25519 Point in "Niels" coordinates
168*
169* y + x, y - x, 2d * x * y
170*
171* where d is the Edwards curve constant.
172*/
173class Ed25519_Point_Niels final {
174 public:
175 Ed25519_FieldElement yplusx; // NOLINT(misc-non-private-member-variables-in-classes)
176 Ed25519_FieldElement yminusx; // NOLINT(misc-non-private-member-variables-in-classes)
177 Ed25519_FieldElement xy2d; // NOLINT(misc-non-private-member-variables-in-classes)
178
179 static constexpr Ed25519_Point_Niels identity() {
180 Ed25519_Point_Niels h;
181 h.yplusx = Ed25519_FieldElement::one();
182 h.yminusx = Ed25519_FieldElement::one();
183 h.xy2d = Ed25519_FieldElement::zero();
184 return h;
185 }
186};
187
188class Ed25519_Point_Cached final {
189 public:
190 Ed25519_FieldElement YplusX; // NOLINT(misc-non-private-member-variables-in-classes)
191 Ed25519_FieldElement YminusX; // NOLINT(misc-non-private-member-variables-in-classes)
192 Ed25519_FieldElement Z; // NOLINT(misc-non-private-member-variables-in-classes)
193 Ed25519_FieldElement T2d; // NOLINT(misc-non-private-member-variables-in-classes)
194
195 /**
196 * Point conversion
197 */
198 static constexpr Ed25519_Point_Cached from(const Ed25519_Point_Extended& p) {
199 Ed25519_Point_Cached r;
200 r.YplusX = p.Y + p.X;
201 r.YminusX = p.Y - p.X;
202 r.Z = p.Z;
203 r.T2d = p.T * ED25519_D2;
204 return r;
205 }
206
207 /**
208 * Point conversion
209 */
210 static constexpr Ed25519_Point_Cached from(const Ed25519_Point_Completed& p) {
211 return Ed25519_Point_Cached::from(Ed25519_Point_Extended::from(p));
212 }
213};
214
215/*
216* Point addition
217*/
218inline constexpr Ed25519_Point_Completed operator+(const Ed25519_Point_Extended& p, const Ed25519_Point_Cached& q) {
219 Ed25519_Point_Completed r;
220 r.X = p.Y + p.X; // YpX1 = Y1+X1
221 r.Y = p.Y - p.X; // YmX1 = Y1-X1
222 r.Z = r.X * q.YplusX; // A = YpX1*YpX2
223 r.Y = r.Y * q.YminusX; // B = YmX1*YmX2
224 r.T = q.T2d * p.T; // C = T2d2*T1
225 r.X = p.Z * q.Z; // ZZ = Z1*Z2
226 const auto t0 = r.X + r.X; // D = 2*ZZ
227 r.X = r.Z - r.Y; // X3 = A-B
228 r.Y = r.Z + r.Y; // Y3 = A+B
229 r.Z = t0 + r.T; // Z3 = D+C
230 r.T = t0 - r.T; // T3 = D-C
231 return r;
232}
233
234/*
235* Point addition
236*/
237inline constexpr Ed25519_Point_Completed operator+(const Ed25519_Point_Extended& p, const Ed25519_Point_Niels& q) {
238 Ed25519_Point_Completed r;
239 r.X = p.Y + p.X; // YpX1 = Y1+X1
240 r.Y = p.Y - p.X; // YmX1 = Y1-X1
241 r.Z = r.X * q.yplusx; // A = YpX1*ypx2
242 r.Y = r.Y * q.yminusx; // B = YmX1*ymx2
243 r.T = q.xy2d * p.T; // C = xy2d2*T1
244 const auto t0 = p.Z + p.Z; // D = 2*Z1
245 r.X = r.Z - r.Y; // X3 = A-B
246 r.Y = r.Z + r.Y; // Y3 = A+B
247 r.Z = t0 + r.T; // Z3 = D+C
248 r.T = t0 - r.T; // T3 = D-C
249 return r;
250}
251
252/*
253* Point subtraction
254*/
255inline constexpr Ed25519_Point_Completed operator-(const Ed25519_Point_Extended& p, const Ed25519_Point_Niels& q) {
256 Ed25519_Point_Completed r;
257 r.X = p.Y + p.X; // YpX1 = Y1+X1
258 r.Y = p.Y - p.X; // YmX1 = Y1-X1
259 r.Z = r.X * q.yminusx; // A = YpX1*ymx2
260 r.Y = r.Y * q.yplusx; // B = YmX1*ypx2
261 r.T = q.xy2d * p.T; // C = xy2d2*T1
262 const auto t0 = p.Z + p.Z; // D = 2*Z1
263 r.X = r.Z - r.Y; // X3 = A-B
264 r.Y = r.Z + r.Y; // Y3 = A+B
265 r.Z = t0 - r.T; // Z3 = D-C
266 r.T = t0 + r.T; // T3 = D+C
267 return r;
268}
269
270/*
271* Point subtraction
272*/
273inline constexpr Ed25519_Point_Completed operator-(const Ed25519_Point_Extended& p, const Ed25519_Point_Cached& q) {
274 Ed25519_Point_Completed r;
275 r.X = p.Y + p.X; // YpX1 = Y1+X1
276 r.Y = p.Y - p.X; // YmX1 = Y1-X1
277 r.Z = r.X * q.YminusX; // A = YpX1*YmX2
278 r.Y = r.Y * q.YplusX; // B = YmX1*YpX2
279 r.T = q.T2d * p.T; // C = T2d2*T1
280 r.X = p.Z * q.Z; // ZZ = Z1*Z2
281 const auto t0 = r.X + r.X; // D = 2*ZZ
282 r.X = r.Z - r.Y; // X3 = A-B
283 r.Y = r.Z + r.Y; // Y3 = A+B
284 r.Z = t0 - r.T; // Z3 = D-C
285 r.T = t0 + r.T; // T3 = D+C
286 return r;
287}
288
289std::array<int8_t, 256> slide(std::span<const uint8_t, 32> a) {
290 std::array<int8_t, 256> r{};
291 for(size_t i = 0; i < 256; ++i) {
292 r[i] = 1 & (a[i >> 3] >> (i & 7));
293 }
294
295 for(size_t i = 0; i < 256; ++i) {
296 if(r[i] != 0) {
297 for(size_t b = 1; b <= 6 && i + b < 256; ++b) {
298 if(r[i + b] != 0) {
299 if(r[i] + (r[i + b] << b) <= 15) {
300 r[i] += r[i + b] << b;
301 r[i + b] = 0;
302 } else if(r[i] - (r[i + b] << b) >= -15) {
303 r[i] -= r[i + b] << b;
304 for(size_t k = i + b; k < 256; ++k) {
305 if(r[k] == 0) {
306 r[k] = 1;
307 break;
308 }
309 r[k] = 0;
310 }
311 } else {
312 break;
313 }
314 }
315 }
316 }
317 }
318
319 return r;
320}
321
322/*
323* The base point B = (x, 4/5) with x even (RFC 8032 Section 5.1)
324*/
325Ed25519_Point_Extended ed25519_derive_basepoint() {
327
328 // Recover x = sqrt((y^2-1)/(d*y^2+1)) as in point decoding
329 const auto yy = y.sqr();
330 const auto u = yy - Ed25519_FieldElement::one();
331 const auto v = ED25519_D * yy + Ed25519_FieldElement::one();
332 const auto v3 = v.sqr() * v;
333 const auto v7 = v3.sqr() * v;
334 auto x = (u * v3) * (u * v7).pow_22523();
335
336 if(!(x.sqr() * v - u).is_zero()) {
337 x = x * ED25519_SQRTM1;
338 }
339 if(x.is_negative()) {
340 x = -x;
341 }
342
343 Ed25519_Point_Extended b;
344 b.X = x;
345 b.Y = y;
347 b.T = x * y;
348 return b;
349}
350
351const Ed25519_Point_Extended& ed25519_basepoint() {
352 static const Ed25519_Point_Extended b = ed25519_derive_basepoint();
353 return b;
354}
355
356/*
357* Compute B_precomp[i][j] = (j+1)*256^i*B in Niels form, sharing a single
358* field inversion across the entire table (Montgomery's trick)
359*/
360std::array<std::array<Ed25519_Point_Niels, 8>, 32> ed25519_base_precomp() {
361 constexpr size_t PTS = 32 * 8;
362
363 auto pts_storage = std::make_unique<std::array<Ed25519_Point_Extended, PTS>>();
364 auto& pts = *pts_storage;
365
366 auto base = ed25519_basepoint();
367 for(size_t i = 0; i != 32; ++i) {
368 pts[8 * i] = base;
369 const auto base_c = Ed25519_Point_Cached::from(base);
370 for(size_t j = 1; j != 8; ++j) {
371 pts[8 * i + j] = Ed25519_Point_Extended::from(pts[8 * i + j - 1] + base_c);
372 }
373
374 // The next row base is 256*base; the row ends with 8*base already
375 base = pts[8 * i + 7];
376 for(size_t k = 0; k != 5; ++k) {
377 base = Ed25519_Point_Extended::from(base.dbl());
378 }
379 }
380
381 auto prod_storage = std::make_unique<std::array<Ed25519_FieldElement, PTS>>();
382 auto& prod = *prod_storage;
383
384 prod[0] = pts[0].Z;
385 for(size_t i = 1; i != PTS; ++i) {
386 prod[i] = prod[i - 1] * pts[i].Z;
387 }
388
389 auto inv = prod[PTS - 1].invert();
390
391 std::array<std::array<Ed25519_Point_Niels, 8>, 32> table;
392 for(size_t i = PTS; i-- > 0;) {
393 const auto z_inv = (i == 0) ? inv : inv * prod[i - 1];
394 inv = inv * pts[i].Z;
395
396 const auto x = pts[i].X * z_inv;
397 const auto y = pts[i].Y * z_inv;
398 auto& n = table[i / 8][i % 8];
399 n.yplusx = y + x;
400 n.yminusx = y - x;
401 n.xy2d = ED25519_D2 * (x * y);
402 }
403
404 return table;
405}
406
407/*
408* Compute Bi[i] = (2*i+1)*B in Niels form
409*/
410std::array<Ed25519_Point_Niels, 8> ed25519_base_odd_multiples() {
411 std::array<Ed25519_Point_Extended, 8> m;
412 m[0] = ed25519_basepoint();
413 const auto base_2 = Ed25519_Point_Cached::from(Ed25519_Point_Extended::from(m[0].dbl()));
414 for(size_t i = 1; i != 8; ++i) {
415 m[i] = Ed25519_Point_Extended::from(m[i - 1] + base_2);
416 }
417
418 std::array<Ed25519_FieldElement, 8> prod;
419 prod[0] = m[0].Z;
420 for(size_t i = 1; i != 8; ++i) {
421 prod[i] = prod[i - 1] * m[i].Z;
422 }
423
424 auto inv = prod[7].invert();
425
426 std::array<Ed25519_Point_Niels, 8> r;
427 for(size_t i = 8; i-- > 0;) {
428 const auto z_inv = (i == 0) ? inv : inv * prod[i - 1];
429 inv = inv * m[i].Z;
430
431 const auto x = m[i].X * z_inv;
432 const auto y = m[i].Y * z_inv;
433 r[i].yplusx = y + x;
434 r[i].yminusx = y - x;
435 r[i].xy2d = ED25519_D2 * (x * y);
436 }
437 return r;
438}
439
440std::optional<Ed25519_Point_Extended> frombytes_negate_vartime(std::span<const uint8_t, 32> s) {
441 // RFC 8032 5.1.3: reject a y coordinate that is not already reduced
442 auto y = Ed25519_FieldElement::deserialize(s.data());
443 if(!y) {
444 return {};
445 }
446
447 auto h = Ed25519_Point_Extended::identity();
448 h.Y = *y;
450 auto u = h.Y.sqr();
451 auto v = u * ED25519_D;
452 u = u - h.Z; /* u = y^2-1 */
453 v = v + h.Z; /* v = dy^2+1 */
454
455 const auto v3 = v.sqr() * v;
456 h.X = v3.sqr();
457 h.X = h.X * v;
458 h.X = h.X * u; /* x = uv^7 */
459
460 h.X = h.X.pow_22523();
461 h.X = h.X * v3;
462 h.X = h.X * u; /* x = uv^3(uv^7)^((q-5)/8) */
463
464 auto vxx = h.X.sqr();
465 vxx = vxx * v;
466 auto check = vxx - u; /* vx^2-u */
467 if(!check.is_zero()) {
468 check = vxx + u; /* vx^2+u */
469 if(!check.is_zero()) {
470 return {};
471 }
472 h.X = h.X * ED25519_SQRTM1;
473 }
474
475 if(h.X.is_negative() == bool(s[31] >> 7)) {
476 h.X = -h.X;
477 }
478
479 // RFC 8032 Section 5.1.3: "If x = 0, and x_0 = 1, decoding fails."
480 // x = 0 is invariant under the negation above, and x_0 is the encoded sign
481 // bit s[31] >> 7. This rejects the non-canonical identity encoding
482 // {0x01, 0x00 ..., 0x00, 0x80} during decoding, which otherwise decodes to
483 // the identity and slips past the canonical-only identity check in
484 // ed25519_verify(). (Ed25519_PublicKey::check_key() also relies on this
485 // rejection.)
486 if(h.X.is_zero() && bool(s[31] >> 7)) {
487 return {};
488 }
489
490 h.T = h.X * h.Y;
491 return h;
492}
493
494/*
495r = a * A + b * B
496where a = a[0]+256*a[1]+...+256^31 a[31].
497and b = b[0]+256*b[1]+...+256^31 b[31].
498B is the Ed25519 base point (x,4/5) with x positive.
499*/
500
501void ge_double_scalarmult_vartime(std::span<uint8_t, 32> out,
502 const Ed25519_Scalar& a,
503 const Ed25519_Point_Extended& A,
504 const Ed25519_Scalar& b) {
505 static const std::array<Ed25519_Point_Niels, 8> Bi = ed25519_base_odd_multiples();
506
507 auto aslide = slide(a.to_bytes());
508 auto bslide = slide(b.to_bytes());
509
510 Ed25519_Point_Cached Ai[8]; /* A,3A,5A,7A,9A,11A,13A,15A */
511 Ai[0] = Ed25519_Point_Cached::from(A);
512 const auto A2 = Ed25519_Point_Extended::from(A.dbl());
513
514 for(size_t i = 1; i != 8; ++i) {
515 Ai[i] = Ed25519_Point_Cached::from(A2 + Ai[i - 1]);
516 }
517
518 auto r = Ed25519_Point_Projective::identity();
519
520 int i = [&]() -> int {
521 int w = 255;
522 while(w >= 0) {
523 if(aslide[w] != 0 || bslide[w] != 0) {
524 return w;
525 } else {
526 w--;
527 }
528 }
529 return 0;
530 }();
531
532 for(; i >= 0; --i) {
533 auto t = r.dbl();
534
535 if(aslide[i] > 0) {
536 t = Ed25519_Point_Extended::from(t) + Ai[aslide[i] >> 1];
537 } else if(aslide[i] < 0) {
538 t = Ed25519_Point_Extended::from(t) - Ai[(-aslide[i]) >> 1];
539 }
540
541 if(bslide[i] > 0) {
542 t = Ed25519_Point_Extended::from(t) + Bi[bslide[i] >> 1];
543 } else if(bslide[i] < 0) {
544 t = Ed25519_Point_Extended::from(t) - Bi[(-bslide[i]) >> 1];
545 }
546
547 r = Ed25519_Point_Projective::from(t);
548 }
549
550 r.serialize_to(std::span<uint8_t, 32>{out});
551}
552
553Ed25519_Point_Niels select(const Ed25519_Point_Niels base[8], int8_t b) {
554 const uint8_t bnegative = static_cast<uint8_t>(b) >> 7;
555 const uint8_t babs = b - ((-static_cast<int>(bnegative) & b) * 2);
556
557 auto t = Ed25519_Point_Niels::identity();
558
559 for(size_t i = 0; i != 8; ++i) {
560 const auto b_is_i1 = CT::Mask<uint8_t>::is_equal(babs, static_cast<uint8_t>(i + 1)).as_choice();
561 t.yplusx.conditional_assign(b_is_i1, base[i].yplusx);
562 t.yminusx.conditional_assign(b_is_i1, base[i].yminusx);
563 t.xy2d.conditional_assign(b_is_i1, base[i].xy2d);
564 }
565
566 // If negative have to swap yminusx and yplusx, and negate xy2d
567 const auto is_negative = CT::Mask<uint8_t>::expand(bnegative).as_choice();
568 Ed25519_FieldElement::conditional_swap(is_negative, t.yplusx, t.yminusx);
569 t.xy2d.conditional_assign(is_negative, -t.xy2d);
570
571 return t;
572}
573
574/*
575h = a * B
576where a = a[0]+256*a[1]+...+256^31 a[31]
577B is the Ed25519 base point (x,4/5) with x positive.
578
579Preconditions:
580 a[31] <= 127
581*/
582Ed25519_Point_Extended basepoint_mul(const Ed25519_Scalar& scalar) {
583 static const std::array<std::array<Ed25519_Point_Niels, 8>, 32> B_precomp = ed25519_base_precomp();
584
585 const auto a = scalar.to_bytes();
586
587 std::array<int8_t, 64> e{};
588
589 // each e[i] is between 0 and 15 except e[63] which is between 0 and 7
590 for(size_t i = 0; i != 32; ++i) {
591 e[2 * i + 0] = (a[i] >> 0) & 0x0F;
592 e[2 * i + 1] = (a[i] >> 4) & 0x0F;
593 }
594
595 int8_t carry = 0;
596 for(size_t i = 0; i < 63; ++i) {
597 e[i] += carry;
598 carry = e[i] + 8;
599 carry >>= 4;
600 e[i] -= carry << 4;
601 }
602 e[63] += carry;
603 /* each e[i] is between -8 and 8 */
604
605 auto h = Ed25519_Point_Extended::identity();
606 for(size_t i = 1; i < 64; i += 2) {
607 h = Ed25519_Point_Extended::from(h + select(B_precomp[i / 2].data(), e[i]));
608 }
609
610 auto s = Ed25519_Point_Projective::from(h.dbl());
611 s = Ed25519_Point_Projective::from(s.dbl());
612 s = Ed25519_Point_Projective::from(s.dbl());
613 h = Ed25519_Point_Extended::from(s.dbl());
614
615 for(size_t i = 0; i != 64; i += 2) {
616 h = Ed25519_Point_Extended::from(h + select(B_precomp[i / 2].data(), e[i]));
617 }
618
619 return h;
620}
621
622} // namespace
623
624void ed25519_basepoint_mul(std::span<uint8_t, 32> out, const Ed25519_Scalar& scalar) {
625 const auto h = basepoint_mul(scalar);
626 h.serialize_to(out);
627}
628
629void ed25519_basepoint_mul_to_x25519(std::span<uint8_t, 32> out, const Ed25519_Scalar& scalar) {
630 const auto h = basepoint_mul(scalar);
631
632 /*
633 * The birational map from the twisted Edwards curve to Curve25519 sends
634 * (x, y) to u = (1 + y) / (1 - y) (RFC 7748 Section 4.1), which for a
635 * projective point (X : Y : Z) is (Z + Y) / (Z - Y). The map sends the
636 * Ed25519 base point to u = 9, so this is the X25519 public key for the
637 * scalar.
638 *
639 * The only point with Z == Y is the identity, where the inversion of zero
640 * returns zero and so u == 0, matching what the Montgomery ladder produces
641 * for the identity. A clamped X25519 scalar is never zero mod l so this
642 * cannot happen for X25519 anyway.
643 */
644 const auto u = (h.Z + h.Y) * (h.Z - h.Y).invert();
645 u.serialize_to(out);
646}
647
648bool ed25519_check_signature(std::span<const uint8_t, 32> pk,
649 const Ed25519_Scalar& h,
650 const uint8_t r[32],
651 const Ed25519_Scalar& s) {
652 if(auto A = frombytes_negate_vartime(pk)) {
653 std::array<uint8_t, 32> rcheck{};
654 ge_double_scalarmult_vartime(rcheck, h, *A, s);
655 return CT::is_equal(rcheck.data(), r, 32).as_bool();
656 }
657 return false;
658}
659
660bool ed25519_valid_public_key_point(std::span<const uint8_t, 32> pk) {
661 if(auto A = frombytes_negate_vartime(pk)) {
662 // Points with x == 0 are the identity and the point of order 2;
663 // neither is a valid public key
664 if(A->X.is_zero()) {
665 return false;
666 }
667
668 /*
669 * Check that the point is in the prime order subgroup, ie that
670 * [l]A == O, by checking that [l-1]A + A == O, or equivalently that
671 * [l-1]A == -A. Since l-1 == -1 (mod l) the scalar is just -1, and
672 * since frombytes_negate_vartime returned -A the final comparison is
673 * against the encoding of A, ie of the negation of what it returned.
674 */
675 auto neg_A = *A;
676 neg_A.X = -A->X;
677 neg_A.T = -A->T;
678
679 std::array<uint8_t, 32> acheck{};
680 neg_A.serialize_to(acheck);
681
682 std::array<uint8_t, 32> rcheck{};
683 ge_double_scalarmult_vartime(rcheck, -Ed25519_Scalar::one(), *A, Ed25519_Scalar::zero());
684
685 return CT::is_equal(rcheck.data(), acheck.data(), 32).as_bool();
686 }
687 return false;
688}
689
690} // namespace Botan
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
static constexpr Ed25519_FieldElement from_word(word x)
Definition ed25519_fe.h:154
static std::optional< Ed25519_FieldElement > deserialize(const uint8_t b[32])
Definition ed25519_fe.h:167
constexpr Ed25519_FieldElement invert() const
Definition ed25519_fe.h:321
constexpr Ed25519_FieldElement sqr() const
Definition ed25519_fe.h:250
static constexpr void conditional_swap(CT::Choice cond, Ed25519_FieldElement &x, Ed25519_FieldElement &y)
Definition ed25519_fe.h:291
static constexpr Ed25519_FieldElement one()
Definition ed25519_fe.h:148
static constexpr Ed25519_FieldElement zero()
Definition ed25519_fe.h:146
static Ed25519_Scalar zero()
static Ed25519_Scalar one()
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:803
void ed25519_basepoint_mul_to_x25519(std::span< uint8_t, 32 > out, const Ed25519_Scalar &scalar)
bool ed25519_valid_public_key_point(std::span< const uint8_t, 32 > pk)
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition symkey.cpp:99
bool ed25519_check_signature(std::span< const uint8_t, 32 > pk, const Ed25519_Scalar &h, const uint8_t r[32], const Ed25519_Scalar &s)
BigInt operator-(const BigInt &x, const BigInt &y)
Definition bigint.h:1216
void ed25519_basepoint_mul(std::span< uint8_t, 32 > out, const Ed25519_Scalar &scalar)