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