Botan 3.7.1
Crypto and TLS for C&
ec_inner_bn.cpp
Go to the documentation of this file.
1/*
2* (C) 2024 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/ec_inner_bn.h>
8
9#include <botan/internal/mod_inv.h>
10
11namespace Botan {
12
14 const auto* p = dynamic_cast<const EC_Scalar_Data_BN*>(&data);
15 if(!p) {
16 throw Invalid_State("Failed conversion to EC_Scalar_Data_BN");
17 }
18 return *p;
19}
20
21const std::shared_ptr<const EC_Group_Data>& EC_Scalar_Data_BN::group() const {
22 return m_group;
23}
24
26 return this->group()->order_bytes();
27}
28
29std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::clone() const {
30 return std::make_unique<EC_Scalar_Data_BN>(this->group(), this->value());
31}
32
34 return this->value().is_zero();
35}
36
37bool EC_Scalar_Data_BN::is_eq(const EC_Scalar_Data& other) const {
38 return (value() == checked_ref(other).value());
39}
40
42 m_v = checked_ref(other).value();
43}
44
46 m_group->mod_order().square(m_v);
47}
48
49std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::negate() const {
50 return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order().reduce(-m_v));
51}
52
53std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::invert() const {
54 return std::make_unique<EC_Scalar_Data_BN>(m_group, inverse_mod_public_prime(m_v, m_group->order()));
55}
56
57std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::invert_vartime() const {
58 return std::make_unique<EC_Scalar_Data_BN>(m_group, inverse_mod_public_prime(m_v, m_group->order()));
59}
60
61std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::add(const EC_Scalar_Data& other) const {
62 return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order().reduce(m_v + checked_ref(other).value()));
63}
64
65std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::sub(const EC_Scalar_Data& other) const {
66 return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order().reduce(m_v - checked_ref(other).value()));
67}
68
69std::unique_ptr<EC_Scalar_Data> EC_Scalar_Data_BN::mul(const EC_Scalar_Data& other) const {
70 return std::make_unique<EC_Scalar_Data_BN>(m_group, m_group->mod_order().multiply(m_v, checked_ref(other).value()));
71}
72
73void EC_Scalar_Data_BN::serialize_to(std::span<uint8_t> bytes) const {
74 BOTAN_ARG_CHECK(bytes.size() == m_group->order_bytes(), "Invalid output length");
76}
77
78EC_AffinePoint_Data_BN::EC_AffinePoint_Data_BN(std::shared_ptr<const EC_Group_Data> group, EC_Point pt) :
79 m_group(std::move(group)), m_pt(std::move(pt)) {
80 if(!m_pt.is_zero()) {
81 m_pt.force_affine();
82 m_xy = m_pt.xy_bytes();
83 }
84}
85
86EC_AffinePoint_Data_BN::EC_AffinePoint_Data_BN(std::shared_ptr<const EC_Group_Data> group,
87 std::span<const uint8_t> pt) :
88 m_group(std::move(group)) {
89 BOTAN_ASSERT_NONNULL(m_group);
90 m_pt = Botan::OS2ECP(pt, m_group->curve());
91 if(!m_pt.is_zero()) {
92 m_xy = m_pt.xy_bytes();
93 }
94}
95
96std::unique_ptr<EC_AffinePoint_Data> EC_AffinePoint_Data_BN::clone() const {
97 return std::make_unique<EC_AffinePoint_Data_BN>(m_group, m_pt);
98}
99
100const std::shared_ptr<const EC_Group_Data>& EC_AffinePoint_Data_BN::group() const {
101 return m_group;
102}
103
104std::unique_ptr<EC_AffinePoint_Data> EC_AffinePoint_Data_BN::mul(const EC_Scalar_Data& scalar,
106 std::vector<BigInt>& ws) const {
107 BOTAN_ARG_CHECK(scalar.group() == m_group, "Curve mismatch");
108 const auto& bn = EC_Scalar_Data_BN::checked_ref(scalar);
109
110 EC_Point_Var_Point_Precompute mul(m_pt, rng, ws);
111
112 // We pass order*cofactor here to "correctly" handle the case where the
113 // point is on the curve but not in the prime order subgroup. This only
114 // matters for groups with cofactor > 1
115 // See https://github.com/randombit/botan/issues/3800
116
117 const auto order = m_group->order() * m_group->cofactor();
118 auto pt = mul.mul(bn.value(), rng, order, ws);
119 return std::make_unique<EC_AffinePoint_Data_BN>(m_group, std::move(pt));
120}
121
124 std::vector<BigInt>& ws) const {
125 BOTAN_ARG_CHECK(scalar.group() == m_group, "Curve mismatch");
126 const auto& bn = EC_Scalar_Data_BN::checked_ref(scalar);
127
128 EC_Point_Var_Point_Precompute mul(m_pt, rng, ws);
129
130 // We pass order*cofactor here to "correctly" handle the case where the
131 // point is on the curve but not in the prime order subgroup. This only
132 // matters for groups with cofactor > 1
133 // See https://github.com/randombit/botan/issues/3800
134
135 const auto order = m_group->order() * m_group->cofactor();
136 auto pt = mul.mul(bn.value(), rng, order, ws);
137 return pt.x_bytes();
138}
139
141 return m_group->p_bytes();
142}
143
145 return m_xy.empty();
146}
147
148void EC_AffinePoint_Data_BN::serialize_x_to(std::span<uint8_t> bytes) const {
150 const size_t fe_bytes = this->field_element_bytes();
151 BOTAN_ARG_CHECK(bytes.size() == fe_bytes, "Invalid output size");
152 copy_mem(bytes, std::span{m_xy}.first(fe_bytes));
153}
154
155void EC_AffinePoint_Data_BN::serialize_y_to(std::span<uint8_t> bytes) const {
157 const size_t fe_bytes = this->field_element_bytes();
158 BOTAN_ARG_CHECK(bytes.size() == fe_bytes, "Invalid output size");
159 copy_mem(bytes, std::span{m_xy}.last(fe_bytes));
160}
161
162void EC_AffinePoint_Data_BN::serialize_xy_to(std::span<uint8_t> bytes) const {
164 const size_t fe_bytes = this->field_element_bytes();
165 BOTAN_ARG_CHECK(bytes.size() == 2 * fe_bytes, "Invalid output size");
166 copy_mem(bytes, m_xy);
167}
168
169void EC_AffinePoint_Data_BN::serialize_compressed_to(std::span<uint8_t> bytes) const {
171 const size_t fe_bytes = this->field_element_bytes();
172 BOTAN_ARG_CHECK(bytes.size() == 1 + fe_bytes, "Invalid output size");
173 const bool y_is_odd = (m_xy[m_xy.size() - 1] & 0x01) == 0x01;
174
175 BufferStuffer stuffer(bytes);
176 stuffer.append(y_is_odd ? 0x03 : 0x02);
177 serialize_x_to(stuffer.next(fe_bytes));
178}
179
180void EC_AffinePoint_Data_BN::serialize_uncompressed_to(std::span<uint8_t> bytes) const {
182 const size_t fe_bytes = this->field_element_bytes();
183 BOTAN_ARG_CHECK(bytes.size() == 1 + 2 * fe_bytes, "Invalid output size");
184 BufferStuffer stuffer(bytes);
185 stuffer.append(0x04);
186 stuffer.append(m_xy);
187}
188
190 m_group(g.group()), m_tbl(g.to_legacy_point(), h.to_legacy_point()) {
191 BOTAN_ARG_CHECK(h.group() == m_group, "Curve mismatch");
192}
193
194std::unique_ptr<EC_AffinePoint_Data> EC_Mul2Table_Data_BN::mul2_vartime(const EC_Scalar_Data& x,
195 const EC_Scalar_Data& y) const {
196 BOTAN_ARG_CHECK(x.group() == m_group && y.group() == m_group, "Curve mismatch");
197
198 const auto& bn_x = EC_Scalar_Data_BN::checked_ref(x);
199 const auto& bn_y = EC_Scalar_Data_BN::checked_ref(y);
200 auto pt = m_tbl.multi_exp(bn_x.value(), bn_y.value());
201
202 if(pt.is_zero()) {
203 return nullptr;
204 }
205 return std::make_unique<EC_AffinePoint_Data_BN>(m_group, std::move(pt));
206}
207
209 const EC_Scalar_Data& x,
210 const EC_Scalar_Data& y) const {
211 BOTAN_ARG_CHECK(x.group() == m_group && y.group() == m_group && v.group() == m_group, "Curve mismatch");
212
213 const auto& bn_v = EC_Scalar_Data_BN::checked_ref(v);
214 const auto& bn_x = EC_Scalar_Data_BN::checked_ref(x);
215 const auto& bn_y = EC_Scalar_Data_BN::checked_ref(y);
216 const auto pt = m_tbl.multi_exp(bn_x.value(), bn_y.value());
217
218 return pt._is_x_eq_to_v_mod_order(bn_v.value());
219}
220
221} // namespace Botan
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:41
#define BOTAN_ASSERT_NONNULL(ptr)
Definition assert.h:86
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
void serialize_to(std::span< uint8_t > out) const
Definition bigint.cpp:383
bool is_zero() const
Definition bigint.h:458
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 std::span< uint8_t > next(size_t bytes)
Definition stl_util.h:150
void serialize_x_to(std::span< uint8_t > bytes) const override
const std::shared_ptr< const EC_Group_Data > & group() const override
secure_vector< uint8_t > mul_x_only(const EC_Scalar_Data &scalar, RandomNumberGenerator &rng, std::vector< BigInt > &ws) const override
EC_AffinePoint_Data_BN(std::shared_ptr< const EC_Group_Data > group, EC_Point pt)
void serialize_compressed_to(std::span< uint8_t > bytes) const override
std::unique_ptr< EC_AffinePoint_Data > mul(const EC_Scalar_Data &scalar, RandomNumberGenerator &rng, std::vector< BigInt > &ws) const override
std::unique_ptr< EC_AffinePoint_Data > clone() const override
size_t field_element_bytes() const override
bool is_identity() const override
void serialize_y_to(std::span< uint8_t > bytes) const override
void serialize_xy_to(std::span< uint8_t > bytes) const override
void serialize_uncompressed_to(std::span< uint8_t > bytes) const override
virtual const std::shared_ptr< const EC_Group_Data > & group() const =0
EC_Mul2Table_Data_BN(const EC_AffinePoint_Data &g, const EC_AffinePoint_Data &h)
bool mul2_vartime_x_mod_order_eq(const EC_Scalar_Data &v, const EC_Scalar_Data &x, const EC_Scalar_Data &y) const override
std::unique_ptr< EC_AffinePoint_Data > mul2_vartime(const EC_Scalar_Data &x, const EC_Scalar_Data &y) const override
EC_Point multi_exp(const BigInt &k1, const BigInt &k2) const
secure_vector< uint8_t > xy_bytes() const
Definition ec_point.cpp:583
bool is_zero() const
Definition ec_point.h:162
bool _is_x_eq_to_v_mod_order(const BigInt &v) const
Definition ec_point.cpp:675
std::unique_ptr< EC_Scalar_Data > invert() const override
std::unique_ptr< EC_Scalar_Data > clone() const override
std::unique_ptr< EC_Scalar_Data > negate() const override
const std::shared_ptr< const EC_Group_Data > & group() const override
bool is_zero() const override
std::unique_ptr< EC_Scalar_Data > sub(const EC_Scalar_Data &other) const override
void square_self() override
std::unique_ptr< EC_Scalar_Data > add(const EC_Scalar_Data &other) const override
std::unique_ptr< EC_Scalar_Data > mul(const EC_Scalar_Data &other) const override
const BigInt & value() const
Definition ec_inner_bn.h:50
void serialize_to(std::span< uint8_t > bytes) const override
static const EC_Scalar_Data_BN & checked_ref(const EC_Scalar_Data &data)
bool is_eq(const EC_Scalar_Data &y) const override
std::unique_ptr< EC_Scalar_Data > invert_vartime() const override
void assign(const EC_Scalar_Data &y) override
size_t bytes() const override
virtual const std::shared_ptr< const EC_Group_Data > & group() const =0
BigInt inverse_mod_public_prime(const BigInt &x, const BigInt &p)
Definition mod_inv.cpp:291
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:147
EC_Point OS2ECP(std::span< const uint8_t > data, const CurveGFp &curve)
Definition ec_point.cpp:815