aff_pt.c
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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 }