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 /* C = A - px, D = B - py */ 176 MP_CHECKOK(group->meth->field_sub(A, px, C, group->meth)); 177 MP_CHECKOK(group->meth->field_sub(B, py, D, group->meth)); 178 179 /* C2 = C^2, C3 = C^3 */ 180 MP_CHECKOK(group->meth->field_sqr(C, C2, group->meth)); 181 MP_CHECKOK(group->meth->field_mul(C, C2, C3, group->meth)); 182 183 /* rz = pz * C */ 184 MP_CHECKOK(group->meth->field_mul(pz, C, rz, group->meth)); 185 186 /* C = px * C^2 */ 187 MP_CHECKOK(group->meth->field_mul(px, C2, C, group->meth)); 188 /* A = D^2 */ 189 MP_CHECKOK(group->meth->field_sqr(D, A, group->meth)); 190 191 /* rx = D^2 - (C^3 + 2 * (px * C^2)) */ 192 MP_CHECKOK(group->meth->field_add(C, C, rx, group->meth)); 193 MP_CHECKOK(group->meth->field_add(C3, rx, rx, group->meth)); 194 MP_CHECKOK(group->meth->field_sub(A, rx, rx, group->meth)); 195 196 /* C3 = py * C^3 */ 197 MP_CHECKOK(group->meth->field_mul(py, C3, C3, group->meth)); 198 199 /* ry = D * (px * C^2 - rx) - py * C^3 */ 200 MP_CHECKOK(group->meth->field_sub(C, rx, ry, group->meth)); 201 MP_CHECKOK(group->meth->field_mul(D, ry, ry, group->meth)); 202 MP_CHECKOK(group->meth->field_sub(ry, C3, ry, group->meth)); 203 204 /* raz4 = a * rz^4 */ 205 MP_CHECKOK(group->meth->field_sqr(rz, raz4, group->meth)); 206 MP_CHECKOK(group->meth->field_sqr(raz4, raz4, group->meth)); 207 MP_CHECKOK(group->meth-> 208 field_mul(raz4, &group->curvea, raz4, group->meth)); 209 CLEANUP: 210 return res; 211 } 212 213 /* Computes R = nP where R is (rx, ry) and P is the base point. Elliptic 214 * curve points P and R can be identical. Uses mixed Modified-Jacobian 215 * co-ordinates for doubling and Chudnovsky Jacobian coordinates for 216 * additions. Assumes input is already field-encoded using field_enc, and 217 * returns output that is still field-encoded. Uses 5-bit window NAF 218 * method (algorithm 11) for scalar-point multiplication from Brown, 219 * Hankerson, Lopez, Menezes. Software Implementation of the NIST Elliptic 220 * Curves Over Prime Fields. */ 221 mp_err 222 ec_GFp_pt_mul_jm_wNAF(const mp_int *n, const mp_int *px, const mp_int *py, 223 mp_int *rx, mp_int *ry, const ECGroup *group) 224 { 225 mp_err res = MP_OKAY; 226 mp_int precomp[16][2], rz, tpx, tpy; 227 mp_int raz4; 228 mp_int scratch[MAX_SCRATCH]; 229 signed char *naf = NULL; 230 int i, orderBitSize; 231 232 MP_DIGITS(&rz) = 0; 233 MP_DIGITS(&raz4) = 0; 234 MP_DIGITS(&tpx) = 0; 235 MP_DIGITS(&tpy) = 0; 236 for (i = 0; i < 16; i++) { 237 MP_DIGITS(&precomp[i][0]) = 0; 238 MP_DIGITS(&precomp[i][1]) = 0; 239 } 240 for (i = 0; i < MAX_SCRATCH; i++) { 241 MP_DIGITS(&scratch[i]) = 0; 242 } 243 244 ARGCHK(group != NULL, MP_BADARG); 245 ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG); 246 247 /* initialize precomputation table */ 248 MP_CHECKOK(mp_init(&tpx, FLAG(n))); 249 MP_CHECKOK(mp_init(&tpy, FLAG(n)));; 250 MP_CHECKOK(mp_init(&rz, FLAG(n))); 251 MP_CHECKOK(mp_init(&raz4, FLAG(n))); 252 253 for (i = 0; i < 16; i++) { 254 MP_CHECKOK(mp_init(&precomp[i][0], FLAG(n))); 255 MP_CHECKOK(mp_init(&precomp[i][1], FLAG(n))); 256 } 257 for (i = 0; i < MAX_SCRATCH; i++) { 258 MP_CHECKOK(mp_init(&scratch[i], FLAG(n))); 259 } 260 261 /* Set out[8] = P */ 262 MP_CHECKOK(mp_copy(px, &precomp[8][0])); 263 MP_CHECKOK(mp_copy(py, &precomp[8][1])); 264 265 /* Set (tpx, tpy) = 2P */ 266 MP_CHECKOK(group-> 267 point_dbl(&precomp[8][0], &precomp[8][1], &tpx, &tpy, 268 group)); 269 270 /* Set 3P, 5P, ..., 15P */ 271 for (i = 8; i < 15; i++) { 272 MP_CHECKOK(group-> 273 point_add(&precomp[i][0], &precomp[i][1], &tpx, &tpy, 274 &precomp[i + 1][0], &precomp[i + 1][1], 275 group)); 276 } 277 278 /* Set -15P, -13P, ..., -P */ 279 for (i = 0; i < 8; i++) { 280 MP_CHECKOK(mp_copy(&precomp[15 - i][0], &precomp[i][0])); 281 MP_CHECKOK(group->meth-> 282 field_neg(&precomp[15 - i][1], &precomp[i][1], 283 group->meth)); 284 } 285 286 /* R = inf */ 287 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, &rz)); 288 289 orderBitSize = mpl_significant_bits(&group->order); 290 291 /* Allocate memory for NAF */ 292 #ifdef _KERNEL 293 naf = (signed char *) kmem_alloc((orderBitSize + 1), FLAG(n)); 294 #else 295 naf = (signed char *) malloc(sizeof(signed char) * (orderBitSize + 1)); 296 if (naf == NULL) { 297 res = MP_MEM; 298 goto CLEANUP; 299 } 300 #endif 301 302 /* Compute 5NAF */ 303 ec_compute_wNAF(naf, orderBitSize, n, 5); 304 305 /* wNAF method */ 306 for (i = orderBitSize; i >= 0; i--) { 307 /* R = 2R */ 308 ec_GFp_pt_dbl_jm(rx, ry, &rz, &raz4, rx, ry, &rz, 309 &raz4, scratch, group); 310 if (naf[i] != 0) { 311 ec_GFp_pt_add_jm_aff(rx, ry, &rz, &raz4, 312 &precomp[(naf[i] + 15) / 2][0], 313 &precomp[(naf[i] + 15) / 2][1], rx, ry, 314 &rz, &raz4, scratch, group); 315 } 316 } 317 318 /* convert result S to affine coordinates */ 319 MP_CHECKOK(ec_GFp_pt_jac2aff(rx, ry, &rz, rx, ry, group)); 320 321 CLEANUP: 322 for (i = 0; i < MAX_SCRATCH; i++) { 323 mp_clear(&scratch[i]); 324 } 325 for (i = 0; i < 16; i++) { 326 mp_clear(&precomp[i][0]); 327 mp_clear(&precomp[i][1]); 328 } 329 mp_clear(&tpx); 330 mp_clear(&tpy); 331 mp_clear(&rz); 332 mp_clear(&raz4); 333 #ifdef _KERNEL 334 kmem_free(naf, (orderBitSize + 1)); 335 #else 336 free(naf); 337 #endif 338 return res; 339 } 340