1 /*
2 * Copyright (C) 2017 - This file is part of libecc project
3 *
4 * Authors:
5 * Ryad BENADJILA <ryadbenadjila@gmail.com>
6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
7 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
8 *
9 * Contributors:
10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
12 *
13 * This software is licensed under a dual BSD and GPL v2 license.
14 * See LICENSE file at the root folder of the project.
15 */
16 #include <libecc/curves/aff_pt.h>
17
18 #define AFF_PT_MAGIC ((word_t)(0x4c82a9bcd0d9ffabULL))
19
20 /*
21 * Verify that an affine point has already been initialized. Return 0 on
22 * success, -1 otherwise.
23 */
aff_pt_check_initialized(aff_pt_src_t in)24 int aff_pt_check_initialized(aff_pt_src_t in)
25 {
26 int ret;
27
28 MUST_HAVE(((in != NULL) && (in->magic == AFF_PT_MAGIC)), ret, err);
29 ret = ec_shortw_crv_check_initialized(in->crv);
30
31 err:
32 return ret;
33 }
34
35 /*
36 * Initialize pointed aff_pt structure to make it usable by library
37 * function on given curve. Return 0 on success, -1 on error.
38 */
aff_pt_init(aff_pt_t in,ec_shortw_crv_src_t curve)39 int aff_pt_init(aff_pt_t in, ec_shortw_crv_src_t curve)
40 {
41 int ret;
42
43 MUST_HAVE((in != NULL), ret, err);
44 MUST_HAVE((curve != NULL), ret, err);
45
46 ret = ec_shortw_crv_check_initialized(curve); EG(ret, err);
47 ret = fp_init(&(in->x), curve->a.ctx); EG(ret, err);
48 ret = fp_init(&(in->y), curve->a.ctx); EG(ret, err);
49
50 in->crv = curve;
51 in->magic = AFF_PT_MAGIC;
52
53 err:
54 return ret;
55 }
56
57 /*
58 * Initialize given point 'in' on given curve 'curve' and set its coordinates to
59 * 'xcoord' and 'ycoord'. Return 0 on success, -1 on error.
60 */
aff_pt_init_from_coords(aff_pt_t in,ec_shortw_crv_src_t curve,fp_src_t xcoord,fp_src_t ycoord)61 int aff_pt_init_from_coords(aff_pt_t in,
62 ec_shortw_crv_src_t curve,
63 fp_src_t xcoord, fp_src_t ycoord)
64 {
65 int ret;
66
67 ret = aff_pt_init(in, curve); EG(ret, err);
68 ret = fp_copy(&(in->x), xcoord); EG(ret, err);
69 ret = fp_copy(&(in->y), ycoord);
70
71 err:
72 return ret;
73 }
74
75 /*
76 * Uninitialize pointed affine point 'in' to prevent further use (magic field
77 * in the structure is zeroized) and zeroize associated storage space. Note
78 * that the curve context pointed to by the point element (passed during init)
79 * is left untouched.
80 */
aff_pt_uninit(aff_pt_t in)81 void aff_pt_uninit(aff_pt_t in)
82 {
83 if((in != NULL) && (in->magic == AFF_PT_MAGIC) && (in->crv != NULL)){
84 in->crv = NULL;
85 in->magic = WORD(0);
86
87 fp_uninit(&(in->x));
88 fp_uninit(&(in->y));
89 }
90
91 return;
92 }
93
94 /*
95 * Recover the two possible y coordinates from one x on a given
96 * curve.
97 * The two outputs y1 and y2 are initialized in the function.
98 *
99 * The function returns -1 on error, 0 on success.
100 *
101 */
aff_pt_y_from_x(fp_t y1,fp_t y2,fp_src_t x,ec_shortw_crv_src_t curve)102 int aff_pt_y_from_x(fp_t y1, fp_t y2, fp_src_t x, ec_shortw_crv_src_t curve)
103 {
104 int ret;
105
106 MUST_HAVE((y1 != NULL) && (y2 != NULL), ret, err);
107 ret = ec_shortw_crv_check_initialized(curve); EG(ret, err);
108 ret = fp_check_initialized(x); EG(ret, err);
109 /* Aliasing is not supported */
110 MUST_HAVE((y1 != y2) && (y1 != x), ret, err);
111
112
113 /* Initialize our elements */
114 ret = fp_copy(y1, x); EG(ret, err);
115 ret = fp_copy(y2, x); EG(ret, err);
116
117 /* Compute x^3 + ax + b */
118 ret = fp_sqr(y1, y1); EG(ret, err);
119 ret = fp_mul(y1, y1, x); EG(ret, err);
120 ret = fp_mul(y2, y2, &(curve->a)); EG(ret, err);
121 ret = fp_add(y1, y1, y2); EG(ret, err);
122 ret = fp_add(y1, y1, &(curve->b)); EG(ret, err);
123
124 /* Now compute the two possible square roots
125 * realizing y^2 = x^3 + ax + b
126 */
127 ret = fp_sqrt(y1, y2, y1);
128
129 err:
130 return ret;
131 }
132
133 /*
134 * Check if given point of coordinate ('x', 'y') is on given curve 'curve' (i.e.
135 * if it verifies curve equation y^2 = x^3 + ax + b). On success, the verdict is
136 * given using 'on_curve' out parameter (1 if on curve, 0 if not). On error,
137 * the function returns -1 and 'on_curve' is left unmodified.
138 */
is_on_shortw_curve(fp_src_t x,fp_src_t y,ec_shortw_crv_src_t curve,int * on_curve)139 int is_on_shortw_curve(fp_src_t x, fp_src_t y, ec_shortw_crv_src_t curve, int *on_curve)
140 {
141 fp tmp1, tmp2;
142 int ret, cmp;
143 tmp1.magic = tmp2.magic = WORD(0);
144
145 ret = ec_shortw_crv_check_initialized(curve); EG(ret, err);
146 ret = fp_check_initialized(x); EG(ret, err);
147 ret = fp_check_initialized(y); EG(ret, err);
148 MUST_HAVE((on_curve != NULL), ret, err);
149
150 MUST_HAVE((x->ctx == y->ctx), ret, err);
151 MUST_HAVE((x->ctx == curve->a.ctx), ret, err);
152
153 /* Note: to optimize local variables, we instead check that
154 * (y^2 - b) = (x^2 + a) * x
155 */
156
157 /* Compute y^2 - b */
158 ret = fp_init(&tmp1, x->ctx); EG(ret, err);
159 ret = fp_sqr(&tmp1, y); EG(ret, err);
160 ret = fp_sub(&tmp1, &tmp1, &(curve->b)); EG(ret, err);
161
162 /* Compute (x^2 + a) * x */
163 ret = fp_init(&tmp2, x->ctx); EG(ret, err);
164 ret = fp_sqr(&tmp2, x); EG(ret, err);
165 ret = fp_add(&tmp2, &tmp2, &(curve->a)); EG(ret, err);
166 ret = fp_mul(&tmp2, &tmp2, x); EG(ret, err);
167
168 /* Now check*/
169 ret = fp_cmp(&tmp1, &tmp2, &cmp); EG(ret, err);
170
171 (*on_curve) = (!cmp);
172
173 err:
174 fp_uninit(&tmp1);
175 fp_uninit(&tmp2);
176
177 return ret;
178 }
179
180 /*
181 * Same as previous but using an affine point instead of pair of coordinates
182 * and a curve
183 */
aff_pt_is_on_curve(aff_pt_src_t pt,int * on_curve)184 int aff_pt_is_on_curve(aff_pt_src_t pt, int *on_curve)
185 {
186 int ret;
187
188 MUST_HAVE((on_curve != NULL), ret, err);
189 ret = aff_pt_check_initialized(pt); EG(ret, err);
190 ret = is_on_shortw_curve(&(pt->x), &(pt->y), pt->crv, on_curve);
191
192 err:
193 return ret;
194 }
195
196 /*
197 * Copy 'in' affine point into 'out'. 'out' is initialized by the function.
198 * 0 is returned on success, -1 on error.
199 */
ec_shortw_aff_copy(aff_pt_t out,aff_pt_src_t in)200 int ec_shortw_aff_copy(aff_pt_t out, aff_pt_src_t in)
201 {
202 int ret;
203
204 ret = aff_pt_check_initialized(in); EG(ret, err);
205 ret = aff_pt_init(out, in->crv); EG(ret, err);
206 ret = fp_copy(&(out->x), &(in->x)); EG(ret, err);
207 ret = fp_copy(&(out->y), &(in->y));
208
209 err:
210 return ret;
211 }
212
213 /*
214 * Compare affine points 'in1' and 'in2'. On success, 0 is returned and
215 * comparison value is given using 'cmp' (0 if equal, a non-zero value
216 * if they are different). -1 is returned on error.
217 */
ec_shortw_aff_cmp(aff_pt_src_t in1,aff_pt_src_t in2,int * cmp)218 int ec_shortw_aff_cmp(aff_pt_src_t in1, aff_pt_src_t in2, int *cmp)
219 {
220 int ret, cmp_x, cmp_y;
221
222 MUST_HAVE((cmp != NULL), ret, err);
223
224 ret = aff_pt_check_initialized(in1); EG(ret, err);
225 ret = aff_pt_check_initialized(in2); EG(ret, err);
226
227 MUST_HAVE((in1->crv == in2->crv), ret, err);
228
229 ret = fp_cmp(&(in1->x), &(in2->x), &cmp_x); EG(ret, err);
230 ret = fp_cmp(&(in1->y), &(in2->y), &cmp_y); EG(ret, err);
231
232 (*cmp) = (cmp_x | cmp_y);
233
234 err:
235 return ret;
236 }
237
238 /*
239 * Check if given affine points 'in1' and 'in2' on the same curve are equal
240 * or opposite. On success, 0 is returned and 'aff_is_eq_or_opp' contains:
241 * - 1 if points are equal or opposite
242 * - 0 if not
243 * The function returns -1 on error, in which case 'aff_is_eq_or_opp'
244 * is left untouched.
245 */
ec_shortw_aff_eq_or_opp(aff_pt_src_t in1,aff_pt_src_t in2,int * aff_is_eq_or_opp)246 int ec_shortw_aff_eq_or_opp(aff_pt_src_t in1, aff_pt_src_t in2,
247 int *aff_is_eq_or_opp)
248 {
249 int ret, cmp, eq_or_opp;
250
251 ret = aff_pt_check_initialized(in1); EG(ret, err);
252 ret = aff_pt_check_initialized(in2); EG(ret, err);
253 MUST_HAVE((in1->crv == in2->crv), ret, err);
254 MUST_HAVE((aff_is_eq_or_opp != NULL), ret, err);
255
256 ret = fp_cmp(&(in1->x), &(in2->x), &cmp); EG(ret, err);
257 ret = fp_eq_or_opp(&(in1->y), &(in2->y), &eq_or_opp); EG(ret, err);
258
259 (*aff_is_eq_or_opp) = ((cmp == 0) & eq_or_opp);
260
261 err:
262 return ret;
263 }
264
265 /*
266 * Import an affine point from a buffer with the following layout; the 2
267 * coordinates (elements of Fp) are each encoded on p_len bytes, where p_len
268 * is the size of p in bytes (e.g. 66 for a prime p of 521 bits). Each
269 * coordinate is encoded in big endian. Size of buffer must exactly match
270 * 2 * p_len. The function returns 0 on success, -1 on error.
271 */
aff_pt_import_from_buf(aff_pt_t pt,const u8 * pt_buf,u16 pt_buf_len,ec_shortw_crv_src_t crv)272 int aff_pt_import_from_buf(aff_pt_t pt,
273 const u8 *pt_buf,
274 u16 pt_buf_len, ec_shortw_crv_src_t crv)
275 {
276 fp_ctx_src_t ctx;
277 u16 coord_len;
278 int ret, on_curve;
279
280 MUST_HAVE((pt_buf != NULL), ret, err);
281 MUST_HAVE((pt != NULL), ret, err);
282 ret = ec_shortw_crv_check_initialized(crv); EG(ret, err);
283
284 ctx = crv->a.ctx;
285 coord_len = (u16)BYTECEIL(ctx->p_bitlen);
286
287 MUST_HAVE((pt_buf_len == (2 * coord_len)), ret, err);
288
289 ret = fp_init_from_buf(&(pt->x), ctx, pt_buf, coord_len); EG(ret, err);
290 ret = fp_init_from_buf(&(pt->y), ctx, pt_buf + coord_len, coord_len); EG(ret, err);
291
292 /* Set the curve */
293 pt->crv = crv;
294
295 /* Mark the point as initialized */
296 pt->magic = AFF_PT_MAGIC;
297
298 /*
299 * Check that the point is indeed on provided curve, uninitialize it
300 * if this is not the case.
301 */
302 ret = aff_pt_is_on_curve(pt, &on_curve); EG(ret, err);
303
304 if (!on_curve) {
305 aff_pt_uninit(pt);
306 ret = -1;
307 } else {
308 ret = 0;
309 }
310
311 err:
312 PTR_NULLIFY(ctx);
313
314 return ret;
315 }
316
317
318 /*
319 * Export an affine point 'pt' to a buffer with the following layout; the 2
320 * coordinates (elements of Fp) are each encoded on p_len bytes, where p_len
321 * is the size of p in bytes (e.g. 66 for a prime p of 521 bits). Each
322 * coordinate is encoded in big endian. Size of buffer must exactly match
323 * 2 * p_len.
324 */
aff_pt_export_to_buf(aff_pt_src_t pt,u8 * pt_buf,u32 pt_buf_len)325 int aff_pt_export_to_buf(aff_pt_src_t pt, u8 *pt_buf, u32 pt_buf_len)
326 {
327 u16 coord_len;
328 int ret, on_curve;
329
330 MUST_HAVE((pt_buf != NULL), ret, err);
331
332 /* The point to be exported must be on the curve */
333 ret = aff_pt_is_on_curve(pt, &on_curve); EG(ret, err);
334 MUST_HAVE((on_curve), ret, err);
335
336 /* buffer size must match 2 * p_len */
337 coord_len = (u16)BYTECEIL(pt->crv->a.ctx->p_bitlen);
338 MUST_HAVE((pt_buf_len == (2 * coord_len)), ret, err);
339
340 /* Export the two coordinates */
341 ret = fp_export_to_buf(pt_buf, coord_len, &(pt->x)); EG(ret, err);
342 ret = fp_export_to_buf(pt_buf + coord_len, coord_len, &(pt->y));
343
344 err:
345 return ret;
346 }
347