Botan 3.5.0
Crypto and TLS for C&
ed448_internal.cpp
Go to the documentation of this file.
1
2/*
3 * Ed448 Internals
4 * (C) 2024 Jack Lloyd
5 * 2024 Fabian Albert - Rohde & Schwarz Cybersecurity
6 *
7 * Botan is released under the Simplified BSD License (see license.txt)
8 */
9#include <botan/internal/ed448_internal.h>
10
11#include <botan/exceptn.h>
12#include <botan/types.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/loadstor.h>
15#include <botan/internal/shake_xof.h>
16#include <botan/internal/stl_util.h>
17
18namespace Botan {
19namespace {
20
21constexpr uint64_t MINUS_D = 39081;
22
23std::vector<uint8_t> dom4(uint8_t x, std::span<const uint8_t> y) {
24 // RFC 8032 2. Notation and Conventions
25 // dom4(x, y) The octet string "SigEd448" || octet(x) ||
26 // octet(OLEN(y)) || y, where x is in range 0-255 and y
27 // is an octet string of at most 255 octets. "SigEd448"
28 // is in ASCII (8 octets).
29 BOTAN_ARG_CHECK(y.size() < 256, "y is too long");
30 return concat<std::vector<uint8_t>>(std::array<uint8_t, 8>{'S', 'i', 'g', 'E', 'd', '4', '4', '8'},
31 store_le(x),
32 store_le(static_cast<uint8_t>(y.size())),
33 y);
34}
35
36template <ranges::spanable_range... Ts>
37std::array<uint8_t, 2 * ED448_LEN> shake(bool f, std::span<const uint8_t> context, Ts... xs) {
38 auto shake_xof = SHAKE_256_XOF();
39 shake_xof.update(dom4(static_cast<uint8_t>(f), context));
40 (shake_xof.update(std::span(xs)), ...);
41 std::array<uint8_t, 2 * ED448_LEN> res;
42 shake_xof.output(res);
43 return res;
44}
45
46std::pair<std::span<const uint8_t, 57>, std::span<const uint8_t, 57>> split(std::span<const uint8_t, 114> arr) {
47 BufferSlicer bs(arr);
48 auto lhs = bs.take<57>();
49 auto rhs = bs.take<57>();
50 return {lhs, rhs};
51}
52
53Scalar448 scalar_from_xof(XOF& shake_xof) {
54 // 5.2.5. Key Generation
55 // The 57-byte public key is generated by the following steps:
56 // 1. Hash the 57-byte private key using SHAKE256(x, 114), storing the
57 // digest in a 114-octet large buffer, denoted h. Only the lower 57
58 // bytes are used for generating the public key.
59 std::array<uint8_t, ED448_LEN> raw_s;
60 shake_xof.output(raw_s);
61 // 2. Prune the buffer: The two least significant bits of the first
62 // octet are cleared, all eight bits the last octet are cleared, and
63 // the highest bit of the second to last octet is set.
64 raw_s[0] &= 0xFC;
65 raw_s[55] |= 0x80;
66 raw_s[56] = 0;
67
68 return Scalar448(raw_s);
69}
70
71} // namespace
72
73Ed448Point Ed448Point::decode(std::span<const uint8_t, ED448_LEN> enc) {
74 // RFC 8032 5.2.3 Decoding
75 // 1. First, interpret the string as an integer in little-endian
76 // representation. Bit 455 of this number is the least significant
77 // bit of the x-coordinate, and denote this value x_0. The
78 // y-coordinate is recovered simply by clearing this bit. If the
79 // resulting value is >= p, decoding fails.
80 if((enc.back() & 0x7F) != 0) { // last byte is either 0x00 or 0x80
81 throw Decoding_Error("Ed448 point has unacceptable x-distinguisher");
82 }
83 const bool x_distinguisher = enc.back() != 0;
84 const auto y_data = std::span(enc).first<56>();
86 throw Decoding_Error("Ed448 y-coordinate is not smaller than p");
87 }
88 const auto y = Gf448Elem(y_data);
89
90 // 2. To recover the x-coordinate, the curve equation implies
91 // x^2 = (y^2 - 1) / (d y^2 - 1) (mod p). The denominator is always
92 // non-zero mod p. Let u = y^2 - 1 and v = d y^2 - 1. To compute
93 // the square root of (u/v), the first step is to compute the
94 // candidate root x = (u/v)^((p+1)/4). This can be done using the
95 // following trick, to use a single modular powering for both the
96 // inversion of v and the square root:
97 // (p+1)/4 3 (p-3)/4
98 // x = (u/v) = u v (u^5 v^3) (mod p)
99 const auto d = -Gf448Elem(MINUS_D);
100 const auto u = square(Gf448Elem(y)) - 1;
101 const auto v = d * square(Gf448Elem(y)) - 1;
102 const auto maybe_x = (u * square(u)) * v * root((square(square(u)) * u) * square(v) * v);
103
104 // 3. If v * x^2 = u, the recovered x-coordinate is x. Otherwise, no
105 // square root exists, and the decoding fails.
106 if(v * square(maybe_x) != u) {
107 throw Decoding_Error("Square root does not exist");
108 }
109 // 4. Finally, use the x_0 bit to select the right square root. If
110 // x = 0, and x_0 = 1, decoding fails. Otherwise, if x_0 != x mod
111 // 2, set x <-- p - x. Return the decoded point (x,y).
112 if(maybe_x.is_zero() && x_distinguisher) {
113 throw Decoding_Error("Square root of zero cannot be odd");
114 }
115 bool maybe_x_parity = maybe_x.is_odd();
116 std::array<uint64_t, WORDS_448> x_data;
117 CT::Mask<uint64_t>::expand(maybe_x_parity == x_distinguisher)
118 .select_n(x_data.data(), maybe_x.words().data(), (-maybe_x).words().data(), 7);
119
120 return {Gf448Elem(x_data), y};
121}
122
124 constexpr std::array<const uint64_t, WORDS_448> x = {0x2626a82bc70cc05e,
125 0x433b80e18b00938e,
126 0x12ae1af72ab66511,
127 0xea6de324a3d3a464,
128 0x9e146570470f1767,
129 0x221d15a622bf36da,
130 0x4f1970c66bed0ded};
131 constexpr std::array<const uint64_t, WORDS_448> y = {0x9808795bf230fa14,
132 0xfdbd132c4ed7c8ad,
133 0x3ad3ff1ce67c39c4,
134 0x87789c1e05a0c2d7,
135 0x4bea73736ca39840,
136 0x8876203756c9c762,
137 0x693f46716eb6bc24};
138 return Ed448Point(Gf448Elem(x), Gf448Elem(y));
139}
140
141std::array<uint8_t, ED448_LEN> Ed448Point::encode() const {
142 std::array<uint8_t, ED448_LEN> res_buf = {0};
143
144 // RFC 8032 5.2.2
145 // All values are coded as octet strings, and integers are coded using
146 // little-endian convention. [...]
147 // First, encode the y-coordinate as a little-endian string of 57 octets.
148 // The final octet is always zero.
149 y().to_bytes(std::span(res_buf).first<56>());
150
151 // To form the encoding of the point, copy the least significant bit of
152 // the x-coordinate to the most significant bit of the final octet.
153 res_buf.back() = (static_cast<uint8_t>(x().is_odd()) << 7);
154
155 return res_buf;
156}
157
159 // RFC 8032 5.2.4. - Point Addition (Add)
160 const Gf448Elem A = m_z * other.m_z;
161 const Gf448Elem B = square(A);
162 const Gf448Elem C = m_x * other.m_x;
163 const Gf448Elem D = m_y * other.m_y;
164 const Gf448Elem E = (-Gf448Elem(MINUS_D)) * C * D;
165 const Gf448Elem F = B - E;
166 const Gf448Elem G = B + E;
167 const Gf448Elem H = (m_x + m_y) * (other.m_x + other.m_y);
168 const Gf448Elem X3 = A * F * (H - C - D);
169 const Gf448Elem Y3 = A * G * (D - C);
170 const Gf448Elem Z3 = F * G;
171
172 return Ed448Point(X3, Y3, Z3);
173}
174
176 // RFC 8032 5.2.4. - Point Addition (Double)
177 const Gf448Elem B = square(m_x + m_y);
178 const Gf448Elem C = square(m_x);
179 const Gf448Elem D = square(m_y);
180 const Gf448Elem E = C + D;
181 const Gf448Elem H = square(m_z);
182 const Gf448Elem J = E - (H + H);
183 const Gf448Elem X3 = (B - E) * J;
184 const Gf448Elem Y3 = E * (C - D);
185 const Gf448Elem Z3 = E * J;
186
187 return Ed448Point(X3, Y3, Z3);
188}
189
191 Ed448Point res(0, 1);
192
193 // Square and multiply (double and add) in constant time.
194 // TODO: Optimization potential. E.g. for a = *this precompute
195 // 0, a, 2a, 3a, ..., 15a and ct select and add the right one for
196 // each 4 bit window instead of conditional add.
197 for(int16_t i = 445; i >= 0; --i) {
198 res = res.double_point();
199 // Conditional add if bit is set
200 auto add_sum = res + *this;
201 res.ct_conditional_assign(s.get_bit(i), add_sum);
202 }
203 return res;
204}
205
206bool Ed448Point::operator==(const Ed448Point& other) const {
207 // Note that the operator== of of Gf448Elem is constant time
208 const auto mask_x = CT::Mask<uint8_t>::expand(x() == other.x());
209 const auto mask_y = CT::Mask<uint8_t>::expand(y() == other.y());
210
211 return (mask_x & mask_y).as_bool();
212}
213
214void Ed448Point::ct_conditional_assign(bool cond, const Ed448Point& other) {
215 m_x.ct_cond_assign(cond, other.m_x);
216 m_y.ct_cond_assign(cond, other.m_y);
217 m_z.ct_cond_assign(cond, other.m_z);
218}
219
220Ed448Point operator*(const Scalar448& lhs, const Ed448Point& rhs) {
221 return rhs.scalar_mul(lhs);
222}
223
224std::array<uint8_t, ED448_LEN> create_pk_from_sk(std::span<const uint8_t, ED448_LEN> sk) {
225 // 5.2.5. Key Generation
226 // The 57-byte public key is generated by the following steps:
227 auto shake_xof = SHAKE_256_XOF();
228 shake_xof.update(sk);
229
230 const Scalar448 s = scalar_from_xof(shake_xof);
231 // 3. Interpret the buffer as the little-endian integer, forming a
232 // secret scalar s. Perform a known-base-point scalar
233 // multiplication [s]B.
234 return (s * Ed448Point::base_point()).encode();
235}
236
237std::array<uint8_t, 2 * ED448_LEN> sign_message(std::span<const uint8_t, ED448_LEN> sk,
238 std::span<const uint8_t, ED448_LEN> pk,
239 bool pgflag,
240 std::span<const uint8_t> context,
241 std::span<const uint8_t> msg) {
242 // 5.2.6. Signature Generation
243 // The inputs to the signing procedure is the private key, a 57-octet
244 // string, a flag F, which is 0 for Ed448, 1 for Ed448ph, context C of
245 // at most 255 octets, and a message M of arbitrary size.
246 // 1. Hash the private key, 57 octets, using SHAKE256(x, 114). Let h
247 // denote the resulting digest. Construct the secret scalar s from
248 // the first half of the digest, and the corresponding public key A,
249 // as described in the previous section. Let prefix denote the
250 // second half of the hash digest, h[57],...,h[113].
251 auto shake_xof = SHAKE_256_XOF();
252 shake_xof.update(sk);
253 const Scalar448 s = scalar_from_xof(shake_xof);
254 std::array<uint8_t, ED448_LEN> prefix;
255 shake_xof.output(prefix);
256 // 2. Compute SHAKE256(dom4(F, C) || prefix || PH(M), 114), where M is
257 // the message to be signed, F is 1 for Ed448ph, 0 for Ed448, and C
258 // is the context to use. Interpret the 114-octet digest as a
259 // little-endian integer r.
260 const Scalar448 r(shake(pgflag, context, prefix, msg));
261 // 3. Compute the point [r]B. For efficiency, do this by first
262 // reducing r modulo L, the group order of B. Let the string R be
263 // the encoding of this point.
264 const auto big_r = (r * Ed448Point::base_point()).encode();
265 // 4. Compute SHAKE256(dom4(F, C) || R || A || PH(M), 114), and
266 // interpret the 114-octet digest as a little-endian integer k.
267 const Scalar448 k(shake(pgflag, context, big_r, pk, msg));
268 // 5. Compute S = (r + k * s) mod L. For efficiency, again reduce k
269 // modulo L first.
270 const auto big_s = r + k * s; //r_plus_ks_mod_L(r, k, s);
271 // 6. Form the signature of the concatenation of R (57 octets) and the
272 // little-endian encoding of S (57 octets; the ten most significant
273 // bits of the final octets are always zero).
274 std::array<uint8_t, 2 * ED448_LEN> sig;
275 BufferStuffer stuf(sig);
276 stuf.append(big_r);
277 stuf.append(big_s.to_bytes<ED448_LEN>());
278 BOTAN_ASSERT(stuf.full(), "Buffer is full");
279
280 return sig;
281}
282
283bool verify_signature(std::span<const uint8_t, ED448_LEN> pk,
284 bool phflag,
285 std::span<const uint8_t> context,
286 std::span<const uint8_t> sig,
287 std::span<const uint8_t> msg) {
288 // RFC 8032 5.2.7. Verify
289 // 1. To verify a signature on a message M using context C and public
290 // key A, with F being 0 for Ed448 and 1 for Ed448ph, first split
291 // the signature into two 57-octet halves. Decode the first half as
292 // a point R, and the second half as an integer S, in the range 0 <=
293 // s < L. Decode the public key A as point A’. If any of the
294 // decodings fail (including S being out of range), the signature is
295 // invalid.
296 if(sig.size() != 2 * ED448_LEN) {
297 // Wrong signature size
298 throw Decoding_Error("Ed448 signature has wrong size");
299 }
300 const auto [big_r_bytes, big_s_bytes] = split(sig.first<2 * ED448_LEN>());
301 const auto big_r = Ed448Point::decode(big_r_bytes);
302 if(!Scalar448::bytes_are_reduced(big_s_bytes)) {
303 // S not in range 0 <= s < L
304 throw Decoding_Error("Ed448 signature has invalid S");
305 }
306 const Scalar448 big_s(big_s_bytes);
307 // 2. Compute SHAKE256(dom4(F, C) || R || A || PH(M), 114), and
308 // interpret the 114-octet digest as a little-endian integer k.
309 const Scalar448 k(shake(phflag, context, big_r_bytes, pk, msg));
310 // 3. Check the group equation [4][S]B = [4]R + [4][k]A’. It’s
311 // sufficient, but not required, to instead check [S]B = R + [k]A’.
312 return (big_s * Ed448Point::base_point()) == (big_r + k * Ed448Point::decode(pk));
313}
314
315} // namespace Botan
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:50
Helper class to ease in-place marshalling of concatenated fixed-length values.
Definition stl_util.h:142
constexpr void append(std::span< const uint8_t > buffer)
Definition stl_util.h:177
constexpr bool full() const
Definition stl_util.h:187
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:213
Representation of a point on the Ed448 curve.
Gf448Elem y() const
Getter for point coordinate y.
Ed448Point(const Gf448Elem &x, const Gf448Elem &y, const Gf448Elem &z)
Create a point from its projective coordinates X, Y, Z.
static Ed448Point decode(std::span< const uint8_t, ED448_LEN > enc)
Decode a point from its 57-byte encoding (RFC 8032 5.2.3)
Ed448Point scalar_mul(const Scalar448 &scalar) const
Scalar multiplication.
Ed448Point double_point() const
Double a point (RFC 8032 5.2.4)
void ct_conditional_assign(bool cond, const Ed448Point &other)
Assign other to this if cond is true (constant time)
static Ed448Point base_point()
Create the curve's base point ('B' in RFC 8032 5.2)
bool operator==(const Ed448Point &other) const
Check if two points are equal (constant time)
Ed448Point operator+(const Ed448Point &other) const
Add two points (RFC 8032 5.2.4)
Gf448Elem x() const
Getter for point coordinate x.
std::array< uint8_t, ED448_LEN > encode() const
Encode the point to its 57-byte representation (RFC 8032 5.2.2)
void to_bytes(std::span< uint8_t, BYTES_448 > out) const
Store the canonical representation of the GF element as 56 bytes in little-endian order.
static bool bytes_are_canonical_representation(std::span< const uint8_t, BYTES_448 > x)
Given 56 bytes, checks that the (little endian) number from this bytes is a valid GF element,...
void ct_cond_assign(bool b, const Gf448Elem &other)
Set this to other if b is true. Constant time for any b.
bool is_odd() const
Return true iff this element is odd. Constant time.
Representation of a scalar for X448.
static bool bytes_are_reduced(std::span< const uint8_t > x)
bool get_bit(size_t i) const
Access the i-th bit of the scalar. From 0 (lsb) to 445 (msb).
Gf448Elem root(const Gf448Elem &elem)
Compute the root of elem in the field.
BigInt operator*(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:46
std::array< uint8_t, ED448_LEN > create_pk_from_sk(std::span< const uint8_t, ED448_LEN > sk)
Create a public key point from a secret key (RFC 8032 5.2.5)
bool verify_signature(std::span< const uint8_t, ED448_LEN > pk, bool phflag, std::span< const uint8_t > context, std::span< const uint8_t > sig, std::span< const uint8_t > msg)
Verify a signature(RFC 8032 5.2.7)
BigInt square(const BigInt &x)
Definition numthry.cpp:157
constexpr size_t ED448_LEN
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:698
constexpr auto concat(Rs &&... ranges)
Definition stl_util.h:262
std::array< uint8_t, 2 *ED448_LEN > sign_message(std::span< const uint8_t, ED448_LEN > sk, std::span< const uint8_t, ED448_LEN > pk, bool pgflag, std::span< const uint8_t > context, std::span< const uint8_t > msg)
Sign a message using a keypair (RFC 8032 5.2.6)