1 /* 2 * ***** BEGIN LICENSE BLOCK ***** 3 * Version: MPL 1.1/GPL 2.0/LGPL 2.1 4 * 5 * The contents of this file are subject to the Mozilla Public License Version 6 * 1.1 (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * http://www.mozilla.org/MPL/ 9 * 10 * Software distributed under the License is distributed on an "AS IS" basis, 11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 12 * for the specific language governing rights and limitations under the 13 * License. 14 * 15 * The Original Code is the elliptic curve math library for prime field curves. 16 * 17 * The Initial Developer of the Original Code is 18 * Sun Microsystems, Inc. 19 * Portions created by the Initial Developer are Copyright (C) 2003 20 * the Initial Developer. All Rights Reserved. 21 * 22 * Contributor(s): 23 * Stephen Fung <fungstep@hotmail.com>, Sun Microsystems Laboratories 24 * 25 * Alternatively, the contents of this file may be used under the terms of 26 * either the GNU General Public License Version 2 or later (the "GPL"), or 27 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), 28 * in which case the provisions of the GPL or the LGPL are applicable instead 29 * of those above. If you wish to allow use of your version of this file only 30 * under the terms of either the GPL or the LGPL, and not to allow others to 31 * use your version of this file under the terms of the MPL, indicate your 32 * decision by deleting the provisions above and replace them with the notice 33 * and other provisions required by the GPL or the LGPL. If you do not delete 34 * the provisions above, a recipient may use your version of this file under 35 * the terms of any one of the MPL, the GPL or the LGPL. 36 * 37 * ***** END LICENSE BLOCK ***** */ 38 /* 39 * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 40 * Use is subject to license terms. 41 * 42 * Sun elects to use this software under the MPL license. 43 */ 44 45 #include "ecp.h" 46 #include "ecl-priv.h" 47 #include "mplogic.h" 48 #ifndef _KERNEL 49 #include <stdlib.h> 50 #endif 51 52 #define MAX_SCRATCH 6 53 54 /* Computes R = 2P. Elliptic curve points P and R can be identical. Uses 55 * Modified Jacobian coordinates. 56 * 57 * Assumes input is already field-encoded using field_enc, and returns 58 * output that is still field-encoded. 59 * 60 */ 61 mp_err 62 ec_GFp_pt_dbl_jm(const mp_int *px, const mp_int *py, const mp_int *pz, 63 const mp_int *paz4, mp_int *rx, mp_int *ry, mp_int *rz, 64 mp_int *raz4, mp_int scratch[], const ECGroup *group) 65 { 66 mp_err res = MP_OKAY; 67 mp_int *t0, *t1, *M, *S; 68 69 t0 = &scratch[0]; 70 t1 = &scratch[1]; 71 M = &scratch[2]; 72 S = &scratch[3]; 73 74 #if MAX_SCRATCH < 4 75 #error "Scratch array defined too small " 76 #endif 77 78 /* Check for point at infinity */ 79 if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) { 80 /* Set r = pt at infinity by setting rz = 0 */ 81 82 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, rz)); 83 goto CLEANUP; 84 } 85 86 /* M = 3 (px^2) + a*(pz^4) */ 87 MP_CHECKOK(group->meth->field_sqr(px, t0, group->meth)); 88 MP_CHECKOK(group->meth->field_add(t0, t0, M, group->meth)); 89 MP_CHECKOK(group->meth->field_add(t0, M, t0, group->meth)); 90 MP_CHECKOK(group->meth->field_add(t0, paz4, M, group->meth)); 91 92 /* rz = 2 * py * pz */ 93 MP_CHECKOK(group->meth->field_mul(py, pz, S, group->meth)); 94 MP_CHECKOK(group->meth->field_add(S, S, rz, group->meth)); 95 96 /* t0 = 2y^2 , t1 = 8y^4 */ 97 MP_CHECKOK(group->meth->field_sqr(py, t0, group->meth)); 98 MP_CHECKOK(group->meth->field_add(t0, t0, t0, group->meth)); 99 MP_CHECKOK(group->meth->field_sqr(t0, t1, group->meth)); 100 MP_CHECKOK(group->meth->field_add(t1, t1, t1, group->meth)); 101 102 /* S = 4 * px * py^2 = 2 * px * t0 */ 103 MP_CHECKOK(group->meth->field_mul(px, t0, S, group->meth)); 104 MP_CHECKOK(group->meth->field_add(S, S, S, group->meth)); 105 106 107 /* rx = M^2 - 2S */ 108 MP_CHECKOK(group->meth->field_sqr(M, rx, group->meth)); 109 MP_CHECKOK(group->meth->field_sub(rx, S, rx, group->meth)); 110 MP_CHECKOK(group->meth->field_sub(rx, S, rx, group->meth)); 111 112 /* ry = M * (S - rx) - t1 */ 113 MP_CHECKOK(group->meth->field_sub(S, rx, S, group->meth)); 114 MP_CHECKOK(group->meth->field_mul(S, M, ry, group->meth)); 115 MP_CHECKOK(group->meth->field_sub(ry, t1, ry, group->meth)); 116 117 /* ra*z^4 = 2*t1*(apz4) */ 118 MP_CHECKOK(group->meth->field_mul(paz4, t1, raz4, group->meth)); 119 MP_CHECKOK(group->meth->field_add(raz4, raz4, raz4, group->meth)); 120 121 122 CLEANUP: 123 return res; 124 } 125 126 /* Computes R = P + Q where R is (rx, ry, rz), P is (px, py, pz) and Q is 127 * (qx, qy, 1). Elliptic curve points P, Q, and R can all be identical. 128 * Uses mixed Modified_Jacobian-affine coordinates. Assumes input is 129 * already field-encoded using field_enc, and returns output that is still 130 * field-encoded. */ 131 mp_err 132 ec_GFp_pt_add_jm_aff(const mp_int *px, const mp_int *py, const mp_int *pz, 133 const mp_int *paz4, const mp_int *qx, 134 const mp_int *qy, mp_int *rx, mp_int *ry, mp_int *rz, 135 mp_int *raz4, mp_int scratch[], const ECGroup *group) 136 { 137 mp_err res = MP_OKAY; 138 mp_int *A, *B, *C, *D, *C2, *C3; 139 140 A = &scratch[0]; 141 B = &scratch[1]; 142 C = &scratch[2]; 143 D = &scratch[3]; 144 C2 = &scratch[4]; 145 C3 = &scratch[5]; 146 147 #if MAX_SCRATCH < 6 148 #error "Scratch array defined too small " 149 #endif 150 151 /* If either P or Q is the point at infinity, then return the other 152 * point */ 153 if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) { 154 MP_CHECKOK(ec_GFp_pt_aff2jac(qx, qy, rx, ry, rz, group)); 155 MP_CHECKOK(group->meth->field_sqr(rz, raz4, group->meth)); 156 MP_CHECKOK(group->meth->field_sqr(raz4, raz4, group->meth)); 157 MP_CHECKOK(group->meth-> 158 field_mul(raz4, &group->curvea, raz4, group->meth)); 159 goto CLEANUP; 160 } 161 if (ec_GFp_pt_is_inf_aff(qx, qy) == MP_YES) { 162 MP_CHECKOK(mp_copy(px, rx)); 163 MP_CHECKOK(mp_copy(py, ry)); 164 MP_CHECKOK(mp_copy(pz, rz)); 165 MP_CHECKOK(mp_copy(paz4, raz4)); 166 goto CLEANUP; 167 } 168 169 /* A = qx * pz^2, B = qy * pz^3 */ 170 MP_CHECKOK(group->meth->field_sqr(pz, A, group->meth)); 171 MP_CHECKOK(group->meth->field_mul(A, pz, B, group->meth)); 172 MP_CHECKOK(group->meth->field_mul(A, qx, A, group->meth)); 173 MP_CHECKOK(group->meth->field_mul(B, qy, B, group->meth)); 174 175 /* Check P == Q */ 176 if (mp_cmp(A, px) == 0) { 177 if (mp_cmp(B, py) == 0) { 178 /* If Px == Qx && Py == Qy, double P. */ 179 return (ec_GFp_pt_dbl_jm(px, py, pz, paz4, rx, ry, rz, 180 raz4, scratch, group)); 181 } 182 /* If Px == Qx && Py != Qy, return point at infinity. */ 183 return (ec_GFp_pt_set_inf_jac(rx, ry, rz)); 184 } 185 186 /* C = A - px, D = B - py */ 187 MP_CHECKOK(group->meth->field_sub(A, px, C, group->meth)); 188 MP_CHECKOK(group->meth->field_sub(B, py, D, group->meth)); 189 190 /* C2 = C^2, C3 = C^3 */ 191 MP_CHECKOK(group->meth->field_sqr(C, C2, group->meth)); 192 MP_CHECKOK(group->meth->field_mul(C, C2, C3, group->meth)); 193 194 /* rz = pz * C */ 195 MP_CHECKOK(group->meth->field_mul(pz, C, rz, group->meth)); 196 197 /* C = px * C^2 */ 198 MP_CHECKOK(group->meth->field_mul(px, C2, C, group->meth)); 199 /* A = D^2 */ 200 MP_CHECKOK(group->meth->field_sqr(D, A, group->meth)); 201 202 /* rx = D^2 - (C^3 + 2 * (px * C^2)) */ 203 MP_CHECKOK(group->meth->field_add(C, C, rx, group->meth)); 204 MP_CHECKOK(group->meth->field_add(C3, rx, rx, group->meth)); 205 MP_CHECKOK(group->meth->field_sub(A, rx, rx, group->meth)); 206 207 /* C3 = py * C^3 */ 208 MP_CHECKOK(group->meth->field_mul(py, C3, C3, group->meth)); 209 210 /* ry = D * (px * C^2 - rx) - py * C^3 */ 211 MP_CHECKOK(group->meth->field_sub(C, rx, ry, group->meth)); 212 MP_CHECKOK(group->meth->field_mul(D, ry, ry, group->meth)); 213 MP_CHECKOK(group->meth->field_sub(ry, C3, ry, group->meth)); 214 215 /* raz4 = a * rz^4 */ 216 MP_CHECKOK(group->meth->field_sqr(rz, raz4, group->meth)); 217 MP_CHECKOK(group->meth->field_sqr(raz4, raz4, group->meth)); 218 MP_CHECKOK(group->meth-> 219 field_mul(raz4, &group->curvea, raz4, group->meth)); 220 CLEANUP: 221 return res; 222 } 223 224 /* Computes R = nP where R is (rx, ry) and P is the base point. Elliptic 225 * curve points P and R can be identical. Uses mixed Modified-Jacobian 226 * co-ordinates for doubling and Chudnovsky Jacobian coordinates for 227 * additions. Assumes input is already field-encoded using field_enc, and 228 * returns output that is still field-encoded. Uses 5-bit window NAF 229 * method (algorithm 11) for scalar-point multiplication from Brown, 230 * Hankerson, Lopez, Menezes. Software Implementation of the NIST Elliptic 231 * Curves Over Prime Fields. */ 232 mp_err 233 ec_GFp_pt_mul_jm_wNAF(const mp_int *n, const mp_int *px, const mp_int *py, 234 mp_int *rx, mp_int *ry, const ECGroup *group) 235 { 236 mp_err res = MP_OKAY; 237 mp_int precomp[16][2], rz, tpx, tpy; 238 mp_int raz4; 239 mp_int scratch[MAX_SCRATCH]; 240 signed char *naf = NULL; 241 int i, orderBitSize; 242 243 MP_DIGITS(&rz) = 0; 244 MP_DIGITS(&raz4) = 0; 245 MP_DIGITS(&tpx) = 0; 246 MP_DIGITS(&tpy) = 0; 247 for (i = 0; i < 16; i++) { 248 MP_DIGITS(&precomp[i][0]) = 0; 249 MP_DIGITS(&precomp[i][1]) = 0; 250 } 251 for (i = 0; i < MAX_SCRATCH; i++) { 252 MP_DIGITS(&scratch[i]) = 0; 253 } 254 255 ARGCHK(group != NULL, MP_BADARG); 256 ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG); 257 258 /* initialize precomputation table */ 259 MP_CHECKOK(mp_init(&tpx, FLAG(n))); 260 MP_CHECKOK(mp_init(&tpy, FLAG(n)));; 261 MP_CHECKOK(mp_init(&rz, FLAG(n))); 262 MP_CHECKOK(mp_init(&raz4, FLAG(n))); 263 264 for (i = 0; i < 16; i++) { 265 MP_CHECKOK(mp_init(&precomp[i][0], FLAG(n))); 266 MP_CHECKOK(mp_init(&precomp[i][1], FLAG(n))); 267 } 268 for (i = 0; i < MAX_SCRATCH; i++) { 269 MP_CHECKOK(mp_init(&scratch[i], FLAG(n))); 270 } 271 272 /* Set out[8] = P */ 273 MP_CHECKOK(mp_copy(px, &precomp[8][0])); 274 MP_CHECKOK(mp_copy(py, &precomp[8][1])); 275 276 /* Set (tpx, tpy) = 2P */ 277 MP_CHECKOK(group-> 278 point_dbl(&precomp[8][0], &precomp[8][1], &tpx, &tpy, 279 group)); 280 281 /* Set 3P, 5P, ..., 15P */ 282 for (i = 8; i < 15; i++) { 283 MP_CHECKOK(group-> 284 point_add(&precomp[i][0], &precomp[i][1], &tpx, &tpy, 285 &precomp[i + 1][0], &precomp[i + 1][1], 286 group)); 287 } 288 289 /* Set -15P, -13P, ..., -P */ 290 for (i = 0; i < 8; i++) { 291 MP_CHECKOK(mp_copy(&precomp[15 - i][0], &precomp[i][0])); 292 MP_CHECKOK(group->meth-> 293 field_neg(&precomp[15 - i][1], &precomp[i][1], 294 group->meth)); 295 } 296 297 /* R = inf */ 298 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, &rz)); 299 300 orderBitSize = mpl_significant_bits(&group->order); 301 302 /* Allocate memory for NAF */ 303 #ifdef _KERNEL 304 naf = (signed char *) kmem_alloc((orderBitSize + 1), FLAG(n)); 305 #else 306 naf = (signed char *) malloc(sizeof(signed char) * (orderBitSize + 1)); 307 if (naf == NULL) { 308 res = MP_MEM; 309 goto CLEANUP; 310 } 311 #endif 312 313 /* Compute 5NAF */ 314 ec_compute_wNAF(naf, orderBitSize, n, 5); 315 316 /* wNAF method */ 317 for (i = orderBitSize; i >= 0; i--) { 318 /* R = 2R */ 319 ec_GFp_pt_dbl_jm(rx, ry, &rz, &raz4, rx, ry, &rz, 320 &raz4, scratch, group); 321 if (naf[i] != 0) { 322 ec_GFp_pt_add_jm_aff(rx, ry, &rz, &raz4, 323 &precomp[(naf[i] + 15) / 2][0], 324 &precomp[(naf[i] + 15) / 2][1], rx, ry, 325 &rz, &raz4, scratch, group); 326 } 327 } 328 329 /* convert result S to affine coordinates */ 330 MP_CHECKOK(ec_GFp_pt_jac2aff(rx, ry, &rz, rx, ry, group)); 331 332 CLEANUP: 333 for (i = 0; i < MAX_SCRATCH; i++) { 334 mp_clear(&scratch[i]); 335 } 336 for (i = 0; i < 16; i++) { 337 mp_clear(&precomp[i][0]); 338 mp_clear(&precomp[i][1]); 339 } 340 mp_clear(&tpx); 341 mp_clear(&tpy); 342 mp_clear(&rz); 343 mp_clear(&raz4); 344 #ifdef _KERNEL 345 kmem_free(naf, (orderBitSize + 1)); 346 #else 347 free(naf); 348 #endif 349 return res; 350 } 351