Botan 3.5.0
Crypto and TLS for C&
curve448_scalar.cpp
Go to the documentation of this file.
1/*
2 * Ed448 Scalar
3 * (C) 2024 Jack Lloyd
4 * 2024 Fabian Albert - Rohde & Schwarz Cybersecurity
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8#include <botan/internal/curve448_scalar.h>
9
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/mp_core.h>
12
13namespace Botan {
14
15namespace {
16constexpr size_t WORDS_REDUCE_SZ = words_for_bits(114 * 8);
17constexpr size_t WORDS_C = words_for_bits(28 * 8);
18
19/// @return (q,r) so that x = q*2^446 + r, r < L
20template <size_t S>
21auto div_mod_2_446(std::span<const word, S> x) {
22 if constexpr(S < Scalar448::WORDS) {
23 std::array<word, Scalar448::WORDS> r = {0};
24 copy_mem(std::span(r).template first<S>(), x);
25 return std::make_pair(std::array<word, 1>({0}), r);
26 } else {
27 std::array<word, Scalar448::WORDS> r;
28 copy_mem(r, std::span(x).template first<Scalar448::WORDS>());
29 // Clear the two most significant bits
30 r[Scalar448::WORDS - 1] &= ~(word(0b11) << (sizeof(word) * 8 - 2));
31
32 std::array<word, S - Scalar448::WORDS + 1> q;
33 bigint_shr2(q.data(), x.data(), x.size(), 446);
34
35 return std::make_pair(q, r);
36 }
37}
38
39/// @return a word array for c = 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
40consteval std::array<word, WORDS_C> c_words() {
41 const std::array<uint8_t, WORDS_C * sizeof(word)> c_bytes{0x0d, 0xbb, 0xa7, 0x54, 0x6d, 0x3d, 0x87, 0xdc, 0xaa, 0x70,
42 0x3a, 0x72, 0x8d, 0x3d, 0x93, 0xde, 0x6f, 0xc9, 0x29, 0x51,
43 0xb6, 0x24, 0xb1, 0x3b, 0x16, 0xdc, 0x35, 0x83};
44 return load_le<std::array<word, WORDS_C>>(c_bytes);
45}
46
47/// @return a word array for L = 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
48consteval std::array<word, Scalar448::WORDS> big_l_words() {
49 const std::array<uint8_t, Scalar448::WORDS * sizeof(word)> big_l_bytes{
50 0xf3, 0x44, 0x58, 0xab, 0x92, 0xc2, 0x78, 0x23, 0x55, 0x8f, 0xc5, 0x8d, 0x72, 0xc2, 0x6c, 0x21, 0x90, 0x36, 0xd6,
51 0xae, 0x49, 0xdb, 0x4e, 0xc4, 0xe9, 0x23, 0xca, 0x7c, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
52 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f};
54}
55
56/// @return c*x, with c = 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
57template <size_t S>
58std::array<word, S + WORDS_C> mul_c(std::span<const word, S> x) {
59 std::array<word, S + WORDS_C> res;
60 std::array<word, S + WORDS_C> ws;
61 constexpr std::array<word, WORDS_C> c = c_words();
62 bigint_mul(res.data(), res.size(), x.data(), x.size(), x.size(), c.data(), c.size(), c.size(), ws.data(), ws.size());
63
64 return res;
65}
66
67/**
68 * @brief Add two numbers. Requires that the result is smaller than 2^448.
69 */
70std::array<word, Scalar448::WORDS> add(std::span<const word, Scalar448::WORDS> x,
71 std::span<const word, Scalar448::WORDS> y) {
72 std::array<word, Scalar448::WORDS> res;
73 copy_mem(res, x);
74 const word carry = bigint_add2_nc(res.data(), res.size(), y.data(), y.size());
75 BOTAN_ASSERT(carry == 0, "Result fits in output");
76 return res;
77}
78
79/**
80 * @brief x = (x >= L) ? x - L : x. Constant time.
81 *
82 * @return true iff a reduction was performed
83 */
84bool ct_subtract_L_if_bigger(std::span<word, Scalar448::WORDS> x) {
85 std::array<word, Scalar448::WORDS> tmp;
86 copy_mem(tmp, x);
87 constexpr auto big_l = big_l_words();
88
89 const word borrow = bigint_sub2(tmp.data(), tmp.size(), big_l.data(), big_l.size());
90 const auto smaller_than_L = CT::Mask<word>::expand(borrow);
91 smaller_than_L.select_n(x.data(), x.data(), tmp.data(), Scalar448::WORDS);
92
93 return !smaller_than_L.as_bool();
94}
95
96template <size_t S>
97std::array<word, words_for_bits(S * 8)> bytes_to_words(std::span<const uint8_t, S> x) {
98 constexpr size_t words = words_for_bits(S * 8);
99 std::array<uint8_t, words * sizeof(word)> x_word_bytes = {0};
100 copy_mem(std::span(x_word_bytes).template first<S>(), x);
101 return load_le<std::array<word, words>>(x_word_bytes);
102}
103
104/**
105 * @brief Reduce a 114 byte number (little endian) modulo L.
106 *
107 * L = 2^446 - 13818066809895115352007386748515426880336692474882178609894547503885
108 * as defined in RFC 8032 5.2. The reduction is performed using the algorithm
109 * described in the "Handbook of Applied Cryptography" Algorithm 14.47. for
110 * m = b^t - c, with b^7 = 2^446 and c = 1381...85
111 */
112std::array<word, Scalar448::WORDS> ct_reduce_mod_L(const std::array<word, WORDS_REDUCE_SZ> x) {
113 const auto [q_0, r_0] = div_mod_2_446(std::span(x));
114
115 auto r = r_0;
116 // Three iterations are required. This is tested using the biggest possible input.
117 // i = 0:
118 const auto q_0_c = mul_c(std::span(q_0));
119 const auto [q_1, r_1] = div_mod_2_446(std::span(q_0_c));
120 r = add(r, r_1);
121
122 // i = 1
123 const auto q_1_c = mul_c(std::span(q_1));
124 const auto [q_2, r_2] = div_mod_2_446(std::span(q_1_c));
125 r = add(r, r_2);
126
127 // i = 2
128 const auto q_2_c = mul_c(std::span(q_2));
129 const auto [q_3, r_3] = div_mod_2_446(std::span(q_2_c));
130 r = add(r, r_3);
131
132 BOTAN_ASSERT_NOMSG(CT::all_zeros(q_3.data(), q_3.size()).as_bool());
133
134 // Note that r is maximal 4*(2^446 - 1) < 2^448. Therefore, the addition did not overflow.
135 // Also, this means that subtracting L 4 times (at most) will bring r into the range [0, L), since
136 // 4*(2^446 - 1) - 4*(2^446 - c) = 4*(c - 1) < L.
137 for(size_t i = 0; i < 4; ++i) {
138 ct_subtract_L_if_bigger(r);
139 }
140
141 return r;
142}
143
144} // namespace
145
146Scalar448::Scalar448(std::span<const uint8_t> in_bytes) {
147 BOTAN_ARG_CHECK(in_bytes.size() <= 114, "Input must be at most 114 bytes long");
148 std::array<uint8_t, 114> max_bytes = {0};
149 copy_mem(std::span(max_bytes).first(in_bytes.size()), in_bytes);
150
151 const auto x_words = bytes_to_words(std::span<const uint8_t, 114>(max_bytes));
152 m_scalar_words = ct_reduce_mod_L(x_words);
153}
154
155bool Scalar448::get_bit(size_t bit_pos) const {
156 BOTAN_ARG_CHECK(bit_pos < 446, "Bit position out of range");
157 constexpr size_t word_sz = sizeof(word) * 8;
158 return (m_scalar_words[bit_pos / word_sz] >> (bit_pos % word_sz)) & 1;
159}
160
162 auto sum = add(m_scalar_words, other.m_scalar_words);
163 ct_subtract_L_if_bigger(sum);
164 return Scalar448(sum);
165}
166
168 std::array<word, WORDS_REDUCE_SZ> product = {0};
169 std::array<word, WORDS_REDUCE_SZ> ws = {0};
170 bigint_mul(product.data(),
171 product.size(),
172 m_scalar_words.data(),
173 m_scalar_words.size(),
174 m_scalar_words.size(),
175 other.m_scalar_words.data(),
176 other.m_scalar_words.size(),
177 other.m_scalar_words.size(),
178 ws.data(),
179 ws.size());
180
181 return Scalar448(ct_reduce_mod_L(product));
182}
183
184bool Scalar448::bytes_are_reduced(std::span<const uint8_t> x) {
185 BOTAN_ARG_CHECK(x.size() >= BYTES, "Input is not long enough (at least 446 bits)");
186 // remember: `x` contains a big int in little-endian
187 const auto leading_zeros = x.subspan(BYTES);
188 const auto leading_zeros_are_zero = CT::all_zeros(leading_zeros.data(), leading_zeros.size());
189 auto x_sig_words = bytes_to_words(x.first<56>());
190 const auto least_56_bytes_smaller_L = CT::Mask<uint8_t>::expand(!ct_subtract_L_if_bigger(x_sig_words));
191 return (leading_zeros_are_zero & least_56_bytes_smaller_L).as_bool();
192}
193
194} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:50
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:213
Representation of a scalar for X448.
Scalar448 operator+(const Scalar448 &other) const
scalar = (scalar + other) mod L
Scalar448(std::span< const uint8_t > x)
Construct a new scalar from (max. 114) bytes. Little endian.
static constexpr size_t WORDS
static bool bytes_are_reduced(std::span< const uint8_t > x)
static constexpr size_t BYTES
bool get_bit(size_t i) const
Access the i-th bit of the scalar. From 0 (lsb) to 445 (msb).
Scalar448 operator*(const Scalar448 &other) const
scalar = (scalar * other) mod L
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:473
constexpr void bigint_shr2(W y[], const W x[], size_t x_size, size_t shift)
Definition mp_core.h:528
constexpr size_t words_for_bits(size_t x)
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:282
void carry(int64_t &h0, int64_t &h1)
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:458
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:291
constexpr auto bigint_add2_nc(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:206
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:146