/src/botan/src/lib/pubkey/ec_group/ec_point.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Point arithmetic on elliptic curves over GF(p) |
3 | | * |
4 | | * (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke |
5 | | * 2008-2011,2012,2014,2015,2018 Jack Lloyd |
6 | | * |
7 | | * Botan is released under the Simplified BSD License (see license.txt) |
8 | | */ |
9 | | |
10 | | #include <botan/ec_point.h> |
11 | | |
12 | | #include <botan/numthry.h> |
13 | | #include <botan/rng.h> |
14 | | #include <botan/internal/ct_utils.h> |
15 | | |
16 | | namespace Botan { |
17 | | |
18 | 18.1k | EC_Point::EC_Point(const CurveGFp& curve) : m_curve(curve), m_coord_x(0), m_coord_y(curve.get_1_rep()), m_coord_z(0) { |
19 | | // Assumes Montgomery rep of zero is zero |
20 | 18.1k | } |
21 | | |
22 | | EC_Point::EC_Point(const CurveGFp& curve, const BigInt& x, const BigInt& y) : |
23 | 1.70k | m_curve(curve), m_coord_x(x), m_coord_y(y), m_coord_z(m_curve.get_1_rep()) { |
24 | 1.70k | if(x < 0 || x >= curve.get_p()) { |
25 | 4 | throw Invalid_Argument("Invalid EC_Point affine x"); |
26 | 4 | } |
27 | 1.69k | if(y < 0 || y >= curve.get_p()) { |
28 | 849 | throw Invalid_Argument("Invalid EC_Point affine y"); |
29 | 849 | } |
30 | | |
31 | 850 | secure_vector<word> monty_ws(m_curve.get_ws_size()); |
32 | 850 | m_curve.to_rep(m_coord_x, monty_ws); |
33 | 850 | m_curve.to_rep(m_coord_y, monty_ws); |
34 | 850 | } |
35 | | |
36 | 0 | void EC_Point::randomize_repr(RandomNumberGenerator& rng) { |
37 | 0 | secure_vector<word> ws(m_curve.get_ws_size()); |
38 | 0 | randomize_repr(rng, ws); |
39 | 0 | } |
40 | | |
41 | 9.09k | void EC_Point::randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws) { |
42 | 9.09k | const BigInt mask = BigInt::random_integer(rng, 2, m_curve.get_p()); |
43 | | |
44 | | /* |
45 | | * No reason to convert this to Montgomery representation first, |
46 | | * just pretend the random mask was chosen as Redc(mask) and the |
47 | | * random mask we generated above is in the Montgomery |
48 | | * representation. |
49 | | * //m_curve.to_rep(mask, ws); |
50 | | */ |
51 | 9.09k | const BigInt mask2 = m_curve.sqr_to_tmp(mask, ws); |
52 | 9.09k | const BigInt mask3 = m_curve.mul_to_tmp(mask2, mask, ws); |
53 | | |
54 | 9.09k | m_coord_x = m_curve.mul_to_tmp(m_coord_x, mask2, ws); |
55 | 9.09k | m_coord_y = m_curve.mul_to_tmp(m_coord_y, mask3, ws); |
56 | 9.09k | m_coord_z = m_curve.mul_to_tmp(m_coord_z, mask, ws); |
57 | 9.09k | } |
58 | | |
59 | | namespace { |
60 | | |
61 | 4.76M | inline void resize_ws(std::vector<BigInt>& ws_bn, size_t cap_size) { |
62 | 4.76M | BOTAN_ASSERT(ws_bn.size() >= EC_Point::WORKSPACE_SIZE, "Expected size for EC_Point workspace"); |
63 | | |
64 | 38.1M | for(auto& ws : ws_bn) { |
65 | 38.1M | if(ws.size() < cap_size) { |
66 | 101k | ws.get_word_vector().resize(cap_size); |
67 | 101k | } |
68 | 38.1M | } |
69 | 4.76M | } |
70 | | |
71 | | } // namespace |
72 | | |
73 | | void EC_Point::add_affine( |
74 | 792k | const word x_words[], size_t x_size, const word y_words[], size_t y_size, std::vector<BigInt>& ws_bn) { |
75 | 792k | if((CT::all_zeros(x_words, x_size) & CT::all_zeros(y_words, y_size)).is_set()) { |
76 | 98.1k | return; |
77 | 98.1k | } |
78 | | |
79 | 693k | if(is_zero()) { |
80 | 4.14k | m_coord_x.set_words(x_words, x_size); |
81 | 4.14k | m_coord_y.set_words(y_words, y_size); |
82 | 4.14k | m_coord_z = m_curve.get_1_rep(); |
83 | 4.14k | return; |
84 | 4.14k | } |
85 | | |
86 | 689k | resize_ws(ws_bn, m_curve.get_ws_size()); |
87 | | |
88 | 689k | secure_vector<word>& ws = ws_bn[0].get_word_vector(); |
89 | 689k | secure_vector<word>& sub_ws = ws_bn[1].get_word_vector(); |
90 | | |
91 | 689k | BigInt& T0 = ws_bn[2]; |
92 | 689k | BigInt& T1 = ws_bn[3]; |
93 | 689k | BigInt& T2 = ws_bn[4]; |
94 | 689k | BigInt& T3 = ws_bn[5]; |
95 | 689k | BigInt& T4 = ws_bn[6]; |
96 | | |
97 | | /* |
98 | | https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2 |
99 | | simplified with Z2 = 1 |
100 | | */ |
101 | | |
102 | 689k | const BigInt& p = m_curve.get_p(); |
103 | | |
104 | 689k | m_curve.sqr(T3, m_coord_z, ws); // z1^2 |
105 | 689k | m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2 |
106 | | |
107 | 689k | m_curve.mul(T2, m_coord_z, T3, ws); // z1^3 |
108 | 689k | m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3 |
109 | | |
110 | 689k | T4.mod_sub(m_coord_x, p, sub_ws); // x2*z1^2 - x1*z2^2 |
111 | | |
112 | 689k | T0.mod_sub(m_coord_y, p, sub_ws); |
113 | | |
114 | 689k | if(T4.is_zero()) { |
115 | 195 | if(T0.is_zero()) { |
116 | 8 | mult2(ws_bn); |
117 | 8 | return; |
118 | 8 | } |
119 | | |
120 | | // setting to zero: |
121 | 187 | m_coord_x.clear(); |
122 | 187 | m_coord_y = m_curve.get_1_rep(); |
123 | 187 | m_coord_z.clear(); |
124 | 187 | return; |
125 | 195 | } |
126 | | |
127 | 689k | m_curve.sqr(T2, T4, ws); |
128 | | |
129 | 689k | m_curve.mul(T3, m_coord_x, T2, ws); |
130 | | |
131 | 689k | m_curve.mul(T1, T2, T4, ws); |
132 | | |
133 | 689k | m_curve.sqr(m_coord_x, T0, ws); |
134 | 689k | m_coord_x.mod_sub(T1, p, sub_ws); |
135 | | |
136 | 689k | m_coord_x.mod_sub(T3, p, sub_ws); |
137 | 689k | m_coord_x.mod_sub(T3, p, sub_ws); |
138 | | |
139 | 689k | T3.mod_sub(m_coord_x, p, sub_ws); |
140 | | |
141 | 689k | m_curve.mul(T2, T0, T3, ws); |
142 | 689k | m_curve.mul(T0, m_coord_y, T1, ws); |
143 | 689k | T2.mod_sub(T0, p, sub_ws); |
144 | 689k | m_coord_y.swap(T2); |
145 | | |
146 | 689k | m_curve.mul(T0, m_coord_z, T4, ws); |
147 | 689k | m_coord_z.swap(T0); |
148 | 689k | } |
149 | | |
150 | | void EC_Point::add(const word x_words[], |
151 | | size_t x_size, |
152 | | const word y_words[], |
153 | | size_t y_size, |
154 | | const word z_words[], |
155 | | size_t z_size, |
156 | 1.00M | std::vector<BigInt>& ws_bn) { |
157 | 1.00M | if((CT::all_zeros(x_words, x_size) & CT::all_zeros(z_words, z_size)).is_set()) { |
158 | 44.5k | return; |
159 | 44.5k | } |
160 | | |
161 | 959k | if(is_zero()) { |
162 | 9.44k | m_coord_x.set_words(x_words, x_size); |
163 | 9.44k | m_coord_y.set_words(y_words, y_size); |
164 | 9.44k | m_coord_z.set_words(z_words, z_size); |
165 | 9.44k | return; |
166 | 9.44k | } |
167 | | |
168 | 950k | resize_ws(ws_bn, m_curve.get_ws_size()); |
169 | | |
170 | 950k | secure_vector<word>& ws = ws_bn[0].get_word_vector(); |
171 | 950k | secure_vector<word>& sub_ws = ws_bn[1].get_word_vector(); |
172 | | |
173 | 950k | BigInt& T0 = ws_bn[2]; |
174 | 950k | BigInt& T1 = ws_bn[3]; |
175 | 950k | BigInt& T2 = ws_bn[4]; |
176 | 950k | BigInt& T3 = ws_bn[5]; |
177 | 950k | BigInt& T4 = ws_bn[6]; |
178 | 950k | BigInt& T5 = ws_bn[7]; |
179 | | |
180 | | /* |
181 | | https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2 |
182 | | */ |
183 | | |
184 | 950k | const BigInt& p = m_curve.get_p(); |
185 | | |
186 | 950k | m_curve.sqr(T0, z_words, z_size, ws); // z2^2 |
187 | 950k | m_curve.mul(T1, m_coord_x, T0, ws); // x1*z2^2 |
188 | 950k | m_curve.mul(T3, z_words, z_size, T0, ws); // z2^3 |
189 | 950k | m_curve.mul(T2, m_coord_y, T3, ws); // y1*z2^3 |
190 | | |
191 | 950k | m_curve.sqr(T3, m_coord_z, ws); // z1^2 |
192 | 950k | m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2 |
193 | | |
194 | 950k | m_curve.mul(T5, m_coord_z, T3, ws); // z1^3 |
195 | 950k | m_curve.mul(T0, y_words, y_size, T5, ws); // y2*z1^3 |
196 | | |
197 | 950k | T4.mod_sub(T1, p, sub_ws); // x2*z1^2 - x1*z2^2 |
198 | | |
199 | 950k | T0.mod_sub(T2, p, sub_ws); |
200 | | |
201 | 950k | if(T4.is_zero()) { |
202 | 482 | if(T0.is_zero()) { |
203 | 277 | mult2(ws_bn); |
204 | 277 | return; |
205 | 277 | } |
206 | | |
207 | | // setting to zero: |
208 | 205 | m_coord_x.clear(); |
209 | 205 | m_coord_y = m_curve.get_1_rep(); |
210 | 205 | m_coord_z.clear(); |
211 | 205 | return; |
212 | 482 | } |
213 | | |
214 | 949k | m_curve.sqr(T5, T4, ws); |
215 | | |
216 | 949k | m_curve.mul(T3, T1, T5, ws); |
217 | | |
218 | 949k | m_curve.mul(T1, T5, T4, ws); |
219 | | |
220 | 949k | m_curve.sqr(m_coord_x, T0, ws); |
221 | 949k | m_coord_x.mod_sub(T1, p, sub_ws); |
222 | 949k | m_coord_x.mod_sub(T3, p, sub_ws); |
223 | 949k | m_coord_x.mod_sub(T3, p, sub_ws); |
224 | | |
225 | 949k | T3.mod_sub(m_coord_x, p, sub_ws); |
226 | | |
227 | 949k | m_curve.mul(m_coord_y, T0, T3, ws); |
228 | 949k | m_curve.mul(T3, T2, T1, ws); |
229 | | |
230 | 949k | m_coord_y.mod_sub(T3, p, sub_ws); |
231 | | |
232 | 949k | m_curve.mul(T3, z_words, z_size, m_coord_z, ws); |
233 | 949k | m_curve.mul(m_coord_z, T3, T4, ws); |
234 | 949k | } |
235 | | |
236 | 710k | void EC_Point::mult2i(size_t iterations, std::vector<BigInt>& ws_bn) { |
237 | 710k | if(iterations == 0) { |
238 | 0 | return; |
239 | 0 | } |
240 | | |
241 | 710k | if(m_coord_y.is_zero()) { |
242 | 0 | *this = EC_Point(m_curve); // setting myself to zero |
243 | 0 | return; |
244 | 0 | } |
245 | | |
246 | | /* |
247 | | TODO we can save 2 squarings per iteration by computing |
248 | | a*Z^4 using values cached from previous iteration |
249 | | */ |
250 | 3.55M | for(size_t i = 0; i != iterations; ++i) { |
251 | 2.84M | mult2(ws_bn); |
252 | 2.84M | } |
253 | 710k | } |
254 | | |
255 | | // *this *= 2 |
256 | 3.12M | void EC_Point::mult2(std::vector<BigInt>& ws_bn) { |
257 | 3.12M | if(is_zero()) { |
258 | 104 | return; |
259 | 104 | } |
260 | | |
261 | 3.12M | if(m_coord_y.is_zero()) { |
262 | 0 | *this = EC_Point(m_curve); // setting myself to zero |
263 | 0 | return; |
264 | 0 | } |
265 | | |
266 | 3.12M | resize_ws(ws_bn, m_curve.get_ws_size()); |
267 | | |
268 | 3.12M | secure_vector<word>& ws = ws_bn[0].get_word_vector(); |
269 | 3.12M | secure_vector<word>& sub_ws = ws_bn[1].get_word_vector(); |
270 | | |
271 | 3.12M | BigInt& T0 = ws_bn[2]; |
272 | 3.12M | BigInt& T1 = ws_bn[3]; |
273 | 3.12M | BigInt& T2 = ws_bn[4]; |
274 | 3.12M | BigInt& T3 = ws_bn[5]; |
275 | 3.12M | BigInt& T4 = ws_bn[6]; |
276 | | |
277 | | /* |
278 | | https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc |
279 | | */ |
280 | 3.12M | const BigInt& p = m_curve.get_p(); |
281 | | |
282 | 3.12M | m_curve.sqr(T0, m_coord_y, ws); |
283 | | |
284 | 3.12M | m_curve.mul(T1, m_coord_x, T0, ws); |
285 | 3.12M | T1.mod_mul(4, p, sub_ws); |
286 | | |
287 | 3.12M | if(m_curve.a_is_zero()) { |
288 | | // if a == 0 then 3*x^2 + a*z^4 is just 3*x^2 |
289 | 0 | m_curve.sqr(T4, m_coord_x, ws); // x^2 |
290 | 0 | T4.mod_mul(3, p, sub_ws); // 3*x^2 |
291 | 3.12M | } else if(m_curve.a_is_minus_3()) { |
292 | | /* |
293 | | if a == -3 then |
294 | | 3*x^2 + a*z^4 == 3*x^2 - 3*z^4 == 3*(x^2-z^4) == 3*(x-z^2)*(x+z^2) |
295 | | */ |
296 | 3.12M | m_curve.sqr(T3, m_coord_z, ws); // z^2 |
297 | | |
298 | | // (x-z^2) |
299 | 3.12M | T2 = m_coord_x; |
300 | 3.12M | T2.mod_sub(T3, p, sub_ws); |
301 | | |
302 | | // (x+z^2) |
303 | 3.12M | T3.mod_add(m_coord_x, p, sub_ws); |
304 | | |
305 | 3.12M | m_curve.mul(T4, T2, T3, ws); // (x-z^2)*(x+z^2) |
306 | | |
307 | 3.12M | T4.mod_mul(3, p, sub_ws); // 3*(x-z^2)*(x+z^2) |
308 | 3.12M | } else { |
309 | 0 | m_curve.sqr(T3, m_coord_z, ws); // z^2 |
310 | 0 | m_curve.sqr(T4, T3, ws); // z^4 |
311 | 0 | m_curve.mul(T3, m_curve.get_a_rep(), T4, ws); // a*z^4 |
312 | |
|
313 | 0 | m_curve.sqr(T4, m_coord_x, ws); // x^2 |
314 | 0 | T4.mod_mul(3, p, sub_ws); |
315 | 0 | T4.mod_add(T3, p, sub_ws); // 3*x^2 + a*z^4 |
316 | 0 | } |
317 | | |
318 | 3.12M | m_curve.sqr(T2, T4, ws); |
319 | 3.12M | T2.mod_sub(T1, p, sub_ws); |
320 | 3.12M | T2.mod_sub(T1, p, sub_ws); |
321 | | |
322 | 3.12M | m_curve.sqr(T3, T0, ws); |
323 | 3.12M | T3.mod_mul(8, p, sub_ws); |
324 | | |
325 | 3.12M | T1.mod_sub(T2, p, sub_ws); |
326 | | |
327 | 3.12M | m_curve.mul(T0, T4, T1, ws); |
328 | 3.12M | T0.mod_sub(T3, p, sub_ws); |
329 | | |
330 | 3.12M | m_coord_x.swap(T2); |
331 | | |
332 | 3.12M | m_curve.mul(T2, m_coord_y, m_coord_z, ws); |
333 | 3.12M | T2.mod_mul(2, p, sub_ws); |
334 | | |
335 | 3.12M | m_coord_y.swap(T0); |
336 | 3.12M | m_coord_z.swap(T2); |
337 | 3.12M | } |
338 | | |
339 | | // arithmetic operators |
340 | 8.25k | EC_Point& EC_Point::operator+=(const EC_Point& rhs) { |
341 | 8.25k | std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE); |
342 | 8.25k | add(rhs, ws); |
343 | 8.25k | return *this; |
344 | 8.25k | } |
345 | | |
346 | 0 | EC_Point& EC_Point::operator-=(const EC_Point& rhs) { |
347 | 0 | EC_Point minus_rhs = EC_Point(rhs).negate(); |
348 | |
|
349 | 0 | if(is_zero()) { |
350 | 0 | *this = minus_rhs; |
351 | 0 | } else { |
352 | 0 | *this += minus_rhs; |
353 | 0 | } |
354 | |
|
355 | 0 | return *this; |
356 | 0 | } |
357 | | |
358 | 0 | EC_Point& EC_Point::operator*=(const BigInt& scalar) { |
359 | 0 | *this = scalar * *this; |
360 | 0 | return *this; |
361 | 0 | } |
362 | | |
363 | 4.12k | EC_Point operator*(const BigInt& scalar, const EC_Point& point) { |
364 | 4.12k | BOTAN_DEBUG_ASSERT(point.on_the_curve()); |
365 | | |
366 | 4.12k | const size_t scalar_bits = scalar.bits(); |
367 | | |
368 | 4.12k | std::vector<BigInt> ws(EC_Point::WORKSPACE_SIZE); |
369 | | |
370 | 4.12k | EC_Point R[2] = {point.zero(), point}; |
371 | | |
372 | 248k | for(size_t i = scalar_bits; i > 0; i--) { |
373 | 244k | const size_t b = scalar.get_bit(i - 1); |
374 | 244k | R[b ^ 1].add(R[b], ws); |
375 | 244k | R[b].mult2(ws); |
376 | 244k | } |
377 | | |
378 | 4.12k | if(scalar.is_negative()) { |
379 | 0 | R[0].negate(); |
380 | 0 | } |
381 | | |
382 | 4.12k | BOTAN_DEBUG_ASSERT(R[0].on_the_curve()); |
383 | | |
384 | 4.12k | return R[0]; |
385 | 4.12k | } |
386 | | |
387 | | //static |
388 | 1 | void EC_Point::force_all_affine(std::vector<EC_Point>& points, secure_vector<word>& ws) { |
389 | 1 | if(points.size() <= 1) { |
390 | 0 | for(auto& point : points) { |
391 | 0 | point.force_affine(); |
392 | 0 | } |
393 | 0 | return; |
394 | 0 | } |
395 | | |
396 | 1.35k | for(auto& point : points) { |
397 | 1.35k | if(point.is_zero()) { |
398 | 0 | throw Invalid_State("Cannot convert zero ECC point to affine"); |
399 | 0 | } |
400 | 1.35k | } |
401 | | |
402 | | /* |
403 | | For >= 2 points use Montgomery's trick |
404 | | |
405 | | See Algorithm 2.26 in "Guide to Elliptic Curve Cryptography" |
406 | | (Hankerson, Menezes, Vanstone) |
407 | | |
408 | | TODO is it really necessary to save all k points in c? |
409 | | */ |
410 | | |
411 | 1 | const CurveGFp& curve = points[0].m_curve; |
412 | 1 | const BigInt& rep_1 = curve.get_1_rep(); |
413 | | |
414 | 1 | if(ws.size() < curve.get_ws_size()) { |
415 | 0 | ws.resize(curve.get_ws_size()); |
416 | 0 | } |
417 | | |
418 | 1 | std::vector<BigInt> c(points.size()); |
419 | 1 | c[0] = points[0].m_coord_z; |
420 | | |
421 | 1.35k | for(size_t i = 1; i != points.size(); ++i) { |
422 | 1.35k | curve.mul(c[i], c[i - 1], points[i].m_coord_z, ws); |
423 | 1.35k | } |
424 | | |
425 | 1 | BigInt s_inv = curve.invert_element(c[c.size() - 1], ws); |
426 | | |
427 | 1 | BigInt z_inv, z2_inv, z3_inv; |
428 | | |
429 | 1.35k | for(size_t i = points.size() - 1; i != 0; i--) { |
430 | 1.35k | EC_Point& point = points[i]; |
431 | | |
432 | 1.35k | curve.mul(z_inv, s_inv, c[i - 1], ws); |
433 | | |
434 | 1.35k | s_inv = curve.mul_to_tmp(s_inv, point.m_coord_z, ws); |
435 | | |
436 | 1.35k | curve.sqr(z2_inv, z_inv, ws); |
437 | 1.35k | curve.mul(z3_inv, z2_inv, z_inv, ws); |
438 | 1.35k | point.m_coord_x = curve.mul_to_tmp(point.m_coord_x, z2_inv, ws); |
439 | 1.35k | point.m_coord_y = curve.mul_to_tmp(point.m_coord_y, z3_inv, ws); |
440 | 1.35k | point.m_coord_z = rep_1; |
441 | 1.35k | } |
442 | | |
443 | 1 | curve.sqr(z2_inv, s_inv, ws); |
444 | 1 | curve.mul(z3_inv, z2_inv, s_inv, ws); |
445 | 1 | points[0].m_coord_x = curve.mul_to_tmp(points[0].m_coord_x, z2_inv, ws); |
446 | 1 | points[0].m_coord_y = curve.mul_to_tmp(points[0].m_coord_y, z3_inv, ws); |
447 | 1 | points[0].m_coord_z = rep_1; |
448 | 1 | } |
449 | | |
450 | 0 | void EC_Point::force_affine() { |
451 | 0 | if(is_zero()) { |
452 | 0 | throw Invalid_State("Cannot convert zero ECC point to affine"); |
453 | 0 | } |
454 | | |
455 | 0 | secure_vector<word> ws; |
456 | |
|
457 | 0 | const BigInt z_inv = m_curve.invert_element(m_coord_z, ws); |
458 | 0 | const BigInt z2_inv = m_curve.sqr_to_tmp(z_inv, ws); |
459 | 0 | const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws); |
460 | 0 | m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws); |
461 | 0 | m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws); |
462 | 0 | m_coord_z = m_curve.get_1_rep(); |
463 | 0 | } |
464 | | |
465 | 43.9k | bool EC_Point::is_affine() const { return m_curve.is_one(m_coord_z); } |
466 | | |
467 | 21.9k | BigInt EC_Point::get_affine_x() const { |
468 | 21.9k | if(is_zero()) { |
469 | 0 | throw Invalid_State("Cannot convert zero point to affine"); |
470 | 0 | } |
471 | | |
472 | 21.9k | secure_vector<word> monty_ws; |
473 | | |
474 | 21.9k | if(is_affine()) { |
475 | 41 | return m_curve.from_rep_to_tmp(m_coord_x, monty_ws); |
476 | 41 | } |
477 | | |
478 | 21.9k | BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws); |
479 | 21.9k | z2 = m_curve.invert_element(z2, monty_ws); |
480 | | |
481 | 21.9k | BigInt r; |
482 | 21.9k | m_curve.mul(r, m_coord_x, z2, monty_ws); |
483 | 21.9k | m_curve.from_rep(r, monty_ws); |
484 | 21.9k | return r; |
485 | 21.9k | } |
486 | | |
487 | 21.9k | BigInt EC_Point::get_affine_y() const { |
488 | 21.9k | if(is_zero()) { |
489 | 0 | throw Invalid_State("Cannot convert zero point to affine"); |
490 | 0 | } |
491 | | |
492 | 21.9k | secure_vector<word> monty_ws; |
493 | | |
494 | 21.9k | if(is_affine()) { |
495 | 41 | return m_curve.from_rep_to_tmp(m_coord_y, monty_ws); |
496 | 41 | } |
497 | | |
498 | 21.9k | const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws); |
499 | 21.9k | const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws); |
500 | 21.9k | const BigInt z3_inv = m_curve.invert_element(z3, monty_ws); |
501 | | |
502 | 21.9k | BigInt r; |
503 | 21.9k | m_curve.mul(r, m_coord_y, z3_inv, monty_ws); |
504 | 21.9k | m_curve.from_rep(r, monty_ws); |
505 | 21.9k | return r; |
506 | 21.9k | } |
507 | | |
508 | 0 | bool EC_Point::on_the_curve() const { |
509 | | /* |
510 | | Is the point still on the curve?? (If everything is correct, the |
511 | | point is always on its curve; then the function will return true. |
512 | | If somehow the state is corrupted, which suggests a fault attack |
513 | | (or internal computational error), then return false. |
514 | | */ |
515 | 0 | if(is_zero()) { |
516 | 0 | return true; |
517 | 0 | } |
518 | | |
519 | 0 | secure_vector<word> monty_ws; |
520 | |
|
521 | 0 | const BigInt y2 = m_curve.from_rep_to_tmp(m_curve.sqr_to_tmp(m_coord_y, monty_ws), monty_ws); |
522 | 0 | const BigInt x3 = m_curve.mul_to_tmp(m_coord_x, m_curve.sqr_to_tmp(m_coord_x, monty_ws), monty_ws); |
523 | 0 | const BigInt ax = m_curve.mul_to_tmp(m_coord_x, m_curve.get_a_rep(), monty_ws); |
524 | 0 | const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws); |
525 | |
|
526 | 0 | if(m_coord_z == z2) // Is z equal to 1 (in Montgomery form)? |
527 | 0 | { |
528 | 0 | if(y2 != m_curve.from_rep_to_tmp(x3 + ax + m_curve.get_b_rep(), monty_ws)) { |
529 | 0 | return false; |
530 | 0 | } |
531 | 0 | } |
532 | | |
533 | 0 | const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws); |
534 | 0 | const BigInt ax_z4 = m_curve.mul_to_tmp(ax, m_curve.sqr_to_tmp(z2, monty_ws), monty_ws); |
535 | 0 | const BigInt b_z6 = m_curve.mul_to_tmp(m_curve.get_b_rep(), m_curve.sqr_to_tmp(z3, monty_ws), monty_ws); |
536 | |
|
537 | 0 | if(y2 != m_curve.from_rep_to_tmp(x3 + ax_z4 + b_z6, monty_ws)) { |
538 | 0 | return false; |
539 | 0 | } |
540 | | |
541 | 0 | return true; |
542 | 0 | } |
543 | | |
544 | | // swaps the states of *this and other, does not throw! |
545 | 75.7k | void EC_Point::swap(EC_Point& other) { |
546 | 75.7k | m_curve.swap(other.m_curve); |
547 | 75.7k | m_coord_x.swap(other.m_coord_x); |
548 | 75.7k | m_coord_y.swap(other.m_coord_y); |
549 | 75.7k | m_coord_z.swap(other.m_coord_z); |
550 | 75.7k | } |
551 | | |
552 | 11.0k | bool EC_Point::operator==(const EC_Point& other) const { |
553 | 11.0k | if(m_curve != other.m_curve) { |
554 | 0 | return false; |
555 | 0 | } |
556 | | |
557 | | // If this is zero, only equal if other is also zero |
558 | 11.0k | if(is_zero()) { |
559 | 16 | return other.is_zero(); |
560 | 16 | } |
561 | | |
562 | 10.9k | return (get_affine_x() == other.get_affine_x() && get_affine_y() == other.get_affine_y()); |
563 | 11.0k | } |
564 | | |
565 | | // encoding and decoding |
566 | 0 | std::vector<uint8_t> EC_Point::encode(EC_Point_Format format) const { |
567 | 0 | if(is_zero()) { |
568 | 0 | return std::vector<uint8_t>(1); // single 0 byte |
569 | 0 | } |
570 | | |
571 | 0 | const size_t p_bytes = m_curve.get_p().bytes(); |
572 | |
|
573 | 0 | const BigInt x = get_affine_x(); |
574 | 0 | const BigInt y = get_affine_y(); |
575 | |
|
576 | 0 | std::vector<uint8_t> result; |
577 | |
|
578 | 0 | if(format == EC_Point_Format::Uncompressed) { |
579 | 0 | result.resize(1 + 2 * p_bytes); |
580 | 0 | result[0] = 0x04; |
581 | 0 | BigInt::encode_1363(&result[1], p_bytes, x); |
582 | 0 | BigInt::encode_1363(&result[1 + p_bytes], p_bytes, y); |
583 | 0 | } else if(format == EC_Point_Format::Compressed) { |
584 | 0 | result.resize(1 + p_bytes); |
585 | 0 | result[0] = 0x02 | static_cast<uint8_t>(y.get_bit(0)); |
586 | 0 | BigInt::encode_1363(&result[1], p_bytes, x); |
587 | 0 | } else if(format == EC_Point_Format::Hybrid) { |
588 | 0 | result.resize(1 + 2 * p_bytes); |
589 | 0 | result[0] = 0x06 | static_cast<uint8_t>(y.get_bit(0)); |
590 | 0 | BigInt::encode_1363(&result[1], p_bytes, x); |
591 | 0 | BigInt::encode_1363(&result[1 + p_bytes], p_bytes, y); |
592 | 0 | } else { |
593 | 0 | throw Invalid_Argument("EC2OSP illegal point encoding"); |
594 | 0 | } |
595 | | |
596 | 0 | return result; |
597 | 0 | } |
598 | | |
599 | | namespace { |
600 | | |
601 | | BigInt decompress_point( |
602 | 0 | bool yMod2, const BigInt& x, const BigInt& curve_p, const BigInt& curve_a, const BigInt& curve_b) { |
603 | 0 | BigInt xpow3 = x * x * x; |
604 | |
|
605 | 0 | BigInt g = curve_a * x; |
606 | 0 | g += xpow3; |
607 | 0 | g += curve_b; |
608 | 0 | g = g % curve_p; |
609 | |
|
610 | 0 | BigInt z = sqrt_modulo_prime(g, curve_p); |
611 | |
|
612 | 0 | if(z < 0) { |
613 | 0 | throw Decoding_Error("Error during EC point decompression"); |
614 | 0 | } |
615 | | |
616 | 0 | if(z.get_bit(0) != yMod2) { |
617 | 0 | z = curve_p - z; |
618 | 0 | } |
619 | |
|
620 | 0 | return z; |
621 | 0 | } |
622 | | |
623 | | } // namespace |
624 | | |
625 | 0 | EC_Point OS2ECP(const uint8_t data[], size_t data_len, const CurveGFp& curve) { |
626 | | // Should we really be doing this? |
627 | 0 | if(data_len <= 1) { |
628 | 0 | return EC_Point(curve); // return zero |
629 | 0 | } |
630 | | |
631 | 0 | std::pair<BigInt, BigInt> xy = OS2ECP(data, data_len, curve.get_p(), curve.get_a(), curve.get_b()); |
632 | |
|
633 | 0 | EC_Point point(curve, xy.first, xy.second); |
634 | |
|
635 | 0 | if(!point.on_the_curve()) { |
636 | 0 | throw Decoding_Error("OS2ECP: Decoded point was not on the curve"); |
637 | 0 | } |
638 | | |
639 | 0 | return point; |
640 | 0 | } |
641 | | |
642 | | std::pair<BigInt, BigInt> OS2ECP( |
643 | 0 | const uint8_t data[], size_t data_len, const BigInt& curve_p, const BigInt& curve_a, const BigInt& curve_b) { |
644 | 0 | if(data_len <= 1) { |
645 | 0 | throw Decoding_Error("OS2ECP invalid point"); |
646 | 0 | } |
647 | | |
648 | 0 | const uint8_t pc = data[0]; |
649 | |
|
650 | 0 | BigInt x, y; |
651 | |
|
652 | 0 | if(pc == 2 || pc == 3) { |
653 | | //compressed form |
654 | 0 | x = BigInt::decode(&data[1], data_len - 1); |
655 | |
|
656 | 0 | const bool y_mod_2 = ((pc & 0x01) == 1); |
657 | 0 | y = decompress_point(y_mod_2, x, curve_p, curve_a, curve_b); |
658 | 0 | } else if(pc == 4) { |
659 | 0 | const size_t l = (data_len - 1) / 2; |
660 | | |
661 | | // uncompressed form |
662 | 0 | x = BigInt::decode(&data[1], l); |
663 | 0 | y = BigInt::decode(&data[l + 1], l); |
664 | 0 | } else if(pc == 6 || pc == 7) { |
665 | 0 | const size_t l = (data_len - 1) / 2; |
666 | | |
667 | | // hybrid form |
668 | 0 | x = BigInt::decode(&data[1], l); |
669 | 0 | y = BigInt::decode(&data[l + 1], l); |
670 | |
|
671 | 0 | const bool y_mod_2 = ((pc & 0x01) == 1); |
672 | |
|
673 | 0 | if(decompress_point(y_mod_2, x, curve_p, curve_a, curve_b) != y) { |
674 | 0 | throw Decoding_Error("OS2ECP: Decoding error in hybrid format"); |
675 | 0 | } |
676 | 0 | } else { |
677 | 0 | throw Invalid_Argument("OS2ECP: Unknown format type " + std::to_string(pc)); |
678 | 0 | } |
679 | | |
680 | 0 | return std::make_pair(x, y); |
681 | 0 | } |
682 | | |
683 | | } // namespace Botan |