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