Botan 3.14.1
Crypto and TLS for C&
ed25519_scalar.cpp
Go to the documentation of this file.
1/*
2* Ed25519 scalar
3* (C) 2017 Ribose Inc
4* 2026 Jack Lloyd
5*
6* Botan is released under the Simplified BSD License (see license.txt)
7*/
8
9#include <botan/internal/ed25519_scalar.h>
10
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/loadstor.h>
13#include <botan/internal/mp_core.h>
14
15namespace Botan {
16
17/*
18* Multiplications use Montgomery reduction with R = 2^256; the required
19* power of R is folded into one of the multiplicands via the precomputed
20* R and R^2 mod l.
21*/
22namespace {
23
24constexpr size_t SC_WORDS = 256 / WordInfo<word>::bits;
25
26consteval std::array<word, SC_WORDS> sc_l_words() {
27 const std::array<uint8_t, 32> l_bytes{0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7,
28 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
29 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10};
31}
32
33constexpr std::array<word, SC_WORDS> SC_L = sc_l_words();
34
35/*
36* -l^-1 mod 2^W (the Montgomery p_dash value)
37*/
38consteval word sc_l_dash() {
39 // Each Newton iteration doubles the number of correct low bits
40 word y = 1;
41 for(size_t i = 0; i != 6; ++i) {
42 y = static_cast<word>(y * (static_cast<word>(2) - SC_L[0] * y));
43 }
44 return static_cast<word>(0) - y;
45}
46
47constexpr word SC_L_DASH = sc_l_dash();
48
49/*
50* Return 2^k mod l, computed by repeated doubling
51*/
52consteval std::array<word, SC_WORDS> sc_2_pow_mod_l(size_t k) {
53 std::array<word, SC_WORDS> r{};
54 r[0] = 1;
55 for(size_t i = 0; i != k; ++i) {
56 word carry = 0;
57 for(size_t j = 0; j != SC_WORDS; ++j) {
58 const word w = r[j];
59 r[j] = static_cast<word>(w << 1) | carry;
60 carry = w >> (WordInfo<word>::bits - 1);
61 }
62
63 std::array<word, SC_WORDS> t{};
64 word borrow = 0;
65 for(size_t j = 0; j != SC_WORDS; ++j) {
66 t[j] = word_sub(r[j], SC_L[j], &borrow);
67 }
68 if(borrow == 0) {
69 r = t;
70 }
71 }
72 return r;
73}
74
75constexpr std::array<word, SC_WORDS> SC_R1 = sc_2_pow_mod_l(256);
76constexpr std::array<word, SC_WORDS> SC_R2 = sc_2_pow_mod_l(512);
77
78/*
79* Montgomery multiplication; requires x * y < l * 2^256 (which holds
80* whenever either operand is below l), returns x * y * 2^-256 mod l
81*/
82std::array<word, SC_WORDS> sc_mont_mul(const std::array<word, SC_WORDS>& x, const std::array<word, SC_WORDS>& y) {
83 std::array<word, 2 * SC_WORDS> z; // NOLINT(*-member-init)
84 comba_mul<SC_WORDS>(z.data(), x.data(), y.data());
85
86 std::array<word, SC_WORDS> r; // NOLINT(*-member-init)
87 std::array<word, SC_WORDS> ws; // NOLINT(*-member-init)
88 bigint_monty_redc(r.data(), z.data(), SC_L.data(), SC_WORDS, SC_L_DASH, ws.data(), ws.size());
89 return r;
90}
91
92/*
93* Given x, y < l return x + y mod l
94*/
95std::array<word, SC_WORDS> sc_add(const std::array<word, SC_WORDS>& x, const std::array<word, SC_WORDS>& y) {
96 // Since both inputs are below l < 2^253 the sum cannot carry out
97 std::array<word, SC_WORDS> r; // NOLINT(*-member-init)
98 word carry = 0;
99 for(size_t i = 0; i != SC_WORDS; ++i) {
100 r[i] = word_add(x[i], y[i], &carry);
101 }
102
103 std::array<word, SC_WORDS> t; // NOLINT(*-member-init)
104 word borrow = 0;
105 for(size_t i = 0; i != SC_WORDS; ++i) {
106 t[i] = word_sub(r[i], SC_L[i], &borrow);
107 }
108 CT::conditional_assign_mem(static_cast<word>(1) - borrow, r.data(), t.data(), SC_WORDS);
109 return r;
110}
111
112std::array<word, SC_WORDS> sc_load(std::span<const uint8_t, 32> b) {
113 std::array<word, SC_WORDS> r; // NOLINT(*-member-init)
114 for(size_t i = 0; i != SC_WORDS; ++i) {
115 r[i] = load_le<word>(b.data(), i);
116 }
117 return r;
118}
119
120} // namespace
121
122Ed25519_Scalar Ed25519_Scalar::from_bytes(std::span<const uint8_t, BYTES> b) {
123 // x mod l == mont_mul(x, R)
124 return Ed25519_Scalar(sc_mont_mul(sc_load(b), SC_R1));
125}
126
127Ed25519_Scalar Ed25519_Scalar::from_wide_bytes(std::span<const uint8_t, 2 * BYTES> b) {
128 const auto lo = sc_load(b.first<BYTES>());
129 const auto hi = sc_load(b.last<BYTES>());
130
131 // (hi * 2^256 + lo) == mont_mul(hi, R^2) + mont_mul(lo, R) (mod l)
132 return Ed25519_Scalar(sc_add(sc_mont_mul(hi, SC_R2), sc_mont_mul(lo, SC_R1)));
133}
134
135std::optional<Ed25519_Scalar> Ed25519_Scalar::from_canonical_bytes(std::span<const uint8_t, BYTES> b) {
136 const auto w = sc_load(b);
137
138 std::array<word, WORDS> t; // NOLINT(*-member-init)
139 word borrow = 0;
140 for(size_t i = 0; i != WORDS; ++i) {
141 t[i] = word_sub(w[i], SC_L[i], &borrow);
142 }
143
144 // If subtracting l did not borrow then the value was not reduced
145 if(borrow == 0) {
146 return std::nullopt;
147 }
148 return Ed25519_Scalar(w);
149}
150
151void Ed25519_Scalar::serialize_to(std::span<uint8_t, BYTES> b) const {
152 for(size_t i = 0; i != WORDS; ++i) {
153 store_le(m_val[i], b.data() + sizeof(word) * i);
154 }
155}
156
157Ed25519_Scalar Ed25519_Scalar::operator+(const Ed25519_Scalar& other) const {
158 return Ed25519_Scalar(sc_add(m_val, other.m_val));
159}
160
161Ed25519_Scalar Ed25519_Scalar::operator-() const {
162 // Compute l - x, then use zero instead if x was zero
163 std::array<word, WORDS> t; // NOLINT(*-member-init)
164 word borrow = 0;
165 for(size_t i = 0; i != WORDS; ++i) {
166 t[i] = word_sub(SC_L[i], m_val[i], &borrow);
167 }
168
169 const std::array<word, WORDS> zeros{};
170 const auto x_is_zero = CT::all_zeros(m_val.data(), WORDS).value();
171 CT::conditional_assign_mem(x_is_zero, t.data(), zeros.data(), WORDS);
172 return Ed25519_Scalar(t);
173}
174
175Ed25519_Scalar Ed25519_Scalar::operator*(const Ed25519_Scalar& other) const {
176 // (a*b) == mont_mul(mont_mul(a, R^2), b) (mod l)
177 return Ed25519_Scalar(sc_mont_mul(sc_mont_mul(m_val, SC_R2), other.m_val));
178}
179
180} // namespace Botan
static constexpr size_t BYTES
static Ed25519_Scalar from_wide_bytes(std::span< const uint8_t, 2 *BYTES > b)
static std::optional< Ed25519_Scalar > from_canonical_bytes(std::span< const uint8_t, BYTES > b)
Ed25519_Scalar operator*(const Ed25519_Scalar &other) const
Ed25519_Scalar operator+(const Ed25519_Scalar &other) const
static Ed25519_Scalar from_bytes(std::span< const uint8_t, BYTES > b)
void serialize_to(std::span< uint8_t, BYTES > b) const
Ed25519_Scalar operator-() const
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:790
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
Definition ct_utils.h:754
constexpr auto word_sub(W x, W y, W *carry) -> W
Definition mp_asmi.h:355
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:260
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:981
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
void bigint_monty_redc(word r[], const word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:1086
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131