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 #pragma ident "%Z%%M% %I% %E% SMI" 46 47 #include "ecp.h" 48 #include "ecl-priv.h" 49 #include "mplogic.h" 50 #ifndef _KERNEL 51 #include <stdlib.h> 52 #endif 53 54 #define MAX_SCRATCH 6 55 56 /* Computes R = 2P. Elliptic curve points P and R can be identical. Uses 57 * Modified Jacobian coordinates. 58 * 59 * Assumes input is already field-encoded using field_enc, and returns 60 * output that is still field-encoded. 61 * 62 */ 63 mp_err 64 ec_GFp_pt_dbl_jm(const mp_int *px, const mp_int *py, const mp_int *pz, 65 const mp_int *paz4, mp_int *rx, mp_int *ry, mp_int *rz, 66 mp_int *raz4, mp_int scratch[], const ECGroup *group) 67 { 68 mp_err res = MP_OKAY; 69 mp_int *t0, *t1, *M, *S; 70 71 t0 = &scratch[0]; 72 t1 = &scratch[1]; 73 M = &scratch[2]; 74 S = &scratch[3]; 75 76 #if MAX_SCRATCH < 4 77 #error "Scratch array defined too small " 78 #endif 79 80 /* Check for point at infinity */ 81 if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) { 82 /* Set r = pt at infinity by setting rz = 0 */ 83 84 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, rz)); 85 goto CLEANUP; 86 } 87 88 /* M = 3 (px^2) + a*(pz^4) */ 89 MP_CHECKOK(group->meth->field_sqr(px, t0, group->meth)); 90 MP_CHECKOK(group->meth->field_add(t0, t0, M, group->meth)); 91 MP_CHECKOK(group->meth->field_add(t0, M, t0, group->meth)); 92 MP_CHECKOK(group->meth->field_add(t0, paz4, M, group->meth)); 93 94 /* rz = 2 * py * pz */ 95 MP_CHECKOK(group->meth->field_mul(py, pz, S, group->meth)); 96 MP_CHECKOK(group->meth->field_add(S, S, rz, group->meth)); 97 98 /* t0 = 2y^2 , t1 = 8y^4 */ 99 MP_CHECKOK(group->meth->field_sqr(py, t0, group->meth)); 100 MP_CHECKOK(group->meth->field_add(t0, t0, t0, group->meth)); 101 MP_CHECKOK(group->meth->field_sqr(t0, t1, group->meth)); 102 MP_CHECKOK(group->meth->field_add(t1, t1, t1, group->meth)); 103 104 /* S = 4 * px * py^2 = 2 * px * t0 */ 105 MP_CHECKOK(group->meth->field_mul(px, t0, S, group->meth)); 106 MP_CHECKOK(group->meth->field_add(S, S, S, group->meth)); 107 108 109 /* rx = M^2 - 2S */ 110 MP_CHECKOK(group->meth->field_sqr(M, rx, group->meth)); 111 MP_CHECKOK(group->meth->field_sub(rx, S, rx, group->meth)); 112 MP_CHECKOK(group->meth->field_sub(rx, S, rx, group->meth)); 113 114 /* ry = M * (S - rx) - t1 */ 115 MP_CHECKOK(group->meth->field_sub(S, rx, S, group->meth)); 116 MP_CHECKOK(group->meth->field_mul(S, M, ry, group->meth)); 117 MP_CHECKOK(group->meth->field_sub(ry, t1, ry, group->meth)); 118 119 /* ra*z^4 = 2*t1*(apz4) */ 120 MP_CHECKOK(group->meth->field_mul(paz4, t1, raz4, group->meth)); 121 MP_CHECKOK(group->meth->field_add(raz4, raz4, raz4, group->meth)); 122 123 124 CLEANUP: 125 return res; 126 } 127 128 /* Computes R = P + Q where R is (rx, ry, rz), P is (px, py, pz) and Q is 129 * (qx, qy, 1). Elliptic curve points P, Q, and R can all be identical. 130 * Uses mixed Modified_Jacobian-affine coordinates. Assumes input is 131 * already field-encoded using field_enc, and returns output that is still 132 * field-encoded. */ 133 mp_err 134 ec_GFp_pt_add_jm_aff(const mp_int *px, const mp_int *py, const mp_int *pz, 135 const mp_int *paz4, const mp_int *qx, 136 const mp_int *qy, mp_int *rx, mp_int *ry, mp_int *rz, 137 mp_int *raz4, mp_int scratch[], const ECGroup *group) 138 { 139 mp_err res = MP_OKAY; 140 mp_int *A, *B, *C, *D, *C2, *C3; 141 142 A = &scratch[0]; 143 B = &scratch[1]; 144 C = &scratch[2]; 145 D = &scratch[3]; 146 C2 = &scratch[4]; 147 C3 = &scratch[5]; 148 149 #if MAX_SCRATCH < 6 150 #error "Scratch array defined too small " 151 #endif 152 153 /* If either P or Q is the point at infinity, then return the other 154 * point */ 155 if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) { 156 MP_CHECKOK(ec_GFp_pt_aff2jac(qx, qy, rx, ry, rz, group)); 157 MP_CHECKOK(group->meth->field_sqr(rz, raz4, group->meth)); 158 MP_CHECKOK(group->meth->field_sqr(raz4, raz4, group->meth)); 159 MP_CHECKOK(group->meth-> 160 field_mul(raz4, &group->curvea, raz4, group->meth)); 161 goto CLEANUP; 162 } 163 if (ec_GFp_pt_is_inf_aff(qx, qy) == MP_YES) { 164 MP_CHECKOK(mp_copy(px, rx)); 165 MP_CHECKOK(mp_copy(py, ry)); 166 MP_CHECKOK(mp_copy(pz, rz)); 167 MP_CHECKOK(mp_copy(paz4, raz4)); 168 goto CLEANUP; 169 } 170 171 /* A = qx * pz^2, B = qy * pz^3 */ 172 MP_CHECKOK(group->meth->field_sqr(pz, A, group->meth)); 173 MP_CHECKOK(group->meth->field_mul(A, pz, B, group->meth)); 174 MP_CHECKOK(group->meth->field_mul(A, qx, A, group->meth)); 175 MP_CHECKOK(group->meth->field_mul(B, qy, B, group->meth)); 176 177 /* C = A - px, D = B - py */ 178 MP_CHECKOK(group->meth->field_sub(A, px, C, group->meth)); 179 MP_CHECKOK(group->meth->field_sub(B, py, D, group->meth)); 180 181 /* C2 = C^2, C3 = C^3 */ 182 MP_CHECKOK(group->meth->field_sqr(C, C2, group->meth)); 183 MP_CHECKOK(group->meth->field_mul(C, C2, C3, group->meth)); 184 185 /* rz = pz * C */ 186 MP_CHECKOK(group->meth->field_mul(pz, C, rz, group->meth)); 187 188 /* C = px * C^2 */ 189 MP_CHECKOK(group->meth->field_mul(px, C2, C, group->meth)); 190 /* A = D^2 */ 191 MP_CHECKOK(group->meth->field_sqr(D, A, group->meth)); 192 193 /* rx = D^2 - (C^3 + 2 * (px * C^2)) */ 194 MP_CHECKOK(group->meth->field_add(C, C, rx, group->meth)); 195 MP_CHECKOK(group->meth->field_add(C3, rx, rx, group->meth)); 196 MP_CHECKOK(group->meth->field_sub(A, rx, rx, group->meth)); 197 198 /* C3 = py * C^3 */ 199 MP_CHECKOK(group->meth->field_mul(py, C3, C3, group->meth)); 200 201 /* ry = D * (px * C^2 - rx) - py * C^3 */ 202 MP_CHECKOK(group->meth->field_sub(C, rx, ry, group->meth)); 203 MP_CHECKOK(group->meth->field_mul(D, ry, ry, group->meth)); 204 MP_CHECKOK(group->meth->field_sub(ry, C3, ry, group->meth)); 205 206 /* raz4 = a * rz^4 */ 207 MP_CHECKOK(group->meth->field_sqr(rz, raz4, group->meth)); 208 MP_CHECKOK(group->meth->field_sqr(raz4, raz4, group->meth)); 209 MP_CHECKOK(group->meth-> 210 field_mul(raz4, &group->curvea, raz4, group->meth)); 211 CLEANUP: 212 return res; 213 } 214 215 /* Computes R = nP where R is (rx, ry) and P is the base point. Elliptic 216 * curve points P and R can be identical. Uses mixed Modified-Jacobian 217 * co-ordinates for doubling and Chudnovsky Jacobian coordinates for 218 * additions. Assumes input is already field-encoded using field_enc, and 219 * returns output that is still field-encoded. Uses 5-bit window NAF 220 * method (algorithm 11) for scalar-point multiplication from Brown, 221 * Hankerson, Lopez, Menezes. Software Implementation of the NIST Elliptic 222 * Curves Over Prime Fields. */ 223 mp_err 224 ec_GFp_pt_mul_jm_wNAF(const mp_int *n, const mp_int *px, const mp_int *py, 225 mp_int *rx, mp_int *ry, const ECGroup *group) 226 { 227 mp_err res = MP_OKAY; 228 mp_int precomp[16][2], rz, tpx, tpy; 229 mp_int raz4; 230 mp_int scratch[MAX_SCRATCH]; 231 signed char *naf = NULL; 232 int i, orderBitSize; 233 234 MP_DIGITS(&rz) = 0; 235 MP_DIGITS(&raz4) = 0; 236 MP_DIGITS(&tpx) = 0; 237 MP_DIGITS(&tpy) = 0; 238 for (i = 0; i < 16; i++) { 239 MP_DIGITS(&precomp[i][0]) = 0; 240 MP_DIGITS(&precomp[i][1]) = 0; 241 } 242 for (i = 0; i < MAX_SCRATCH; i++) { 243 MP_DIGITS(&scratch[i]) = 0; 244 } 245 246 ARGCHK(group != NULL, MP_BADARG); 247 ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG); 248 249 /* initialize precomputation table */ 250 MP_CHECKOK(mp_init(&tpx, FLAG(n))); 251 MP_CHECKOK(mp_init(&tpy, FLAG(n)));; 252 MP_CHECKOK(mp_init(&rz, FLAG(n))); 253 MP_CHECKOK(mp_init(&raz4, FLAG(n))); 254 255 for (i = 0; i < 16; i++) { 256 MP_CHECKOK(mp_init(&precomp[i][0], FLAG(n))); 257 MP_CHECKOK(mp_init(&precomp[i][1], FLAG(n))); 258 } 259 for (i = 0; i < MAX_SCRATCH; i++) { 260 MP_CHECKOK(mp_init(&scratch[i], FLAG(n))); 261 } 262 263 /* Set out[8] = P */ 264 MP_CHECKOK(mp_copy(px, &precomp[8][0])); 265 MP_CHECKOK(mp_copy(py, &precomp[8][1])); 266 267 /* Set (tpx, tpy) = 2P */ 268 MP_CHECKOK(group-> 269 point_dbl(&precomp[8][0], &precomp[8][1], &tpx, &tpy, 270 group)); 271 272 /* Set 3P, 5P, ..., 15P */ 273 for (i = 8; i < 15; i++) { 274 MP_CHECKOK(group-> 275 point_add(&precomp[i][0], &precomp[i][1], &tpx, &tpy, 276 &precomp[i + 1][0], &precomp[i + 1][1], 277 group)); 278 } 279 280 /* Set -15P, -13P, ..., -P */ 281 for (i = 0; i < 8; i++) { 282 MP_CHECKOK(mp_copy(&precomp[15 - i][0], &precomp[i][0])); 283 MP_CHECKOK(group->meth-> 284 field_neg(&precomp[15 - i][1], &precomp[i][1], 285 group->meth)); 286 } 287 288 /* R = inf */ 289 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, &rz)); 290 291 orderBitSize = mpl_significant_bits(&group->order); 292 293 /* Allocate memory for NAF */ 294 #ifdef _KERNEL 295 naf = (signed char *) kmem_alloc((orderBitSize + 1), FLAG(n)); 296 #else 297 naf = (signed char *) malloc(sizeof(signed char) * (orderBitSize + 1)); 298 if (naf == NULL) { 299 res = MP_MEM; 300 goto CLEANUP; 301 } 302 #endif 303 304 /* Compute 5NAF */ 305 ec_compute_wNAF(naf, orderBitSize, n, 5); 306 307 /* wNAF method */ 308 for (i = orderBitSize; i >= 0; i--) { 309 /* R = 2R */ 310 ec_GFp_pt_dbl_jm(rx, ry, &rz, &raz4, rx, ry, &rz, 311 &raz4, scratch, group); 312 if (naf[i] != 0) { 313 ec_GFp_pt_add_jm_aff(rx, ry, &rz, &raz4, 314 &precomp[(naf[i] + 15) / 2][0], 315 &precomp[(naf[i] + 15) / 2][1], rx, ry, 316 &rz, &raz4, scratch, group); 317 } 318 } 319 320 /* convert result S to affine coordinates */ 321 MP_CHECKOK(ec_GFp_pt_jac2aff(rx, ry, &rz, rx, ry, group)); 322 323 CLEANUP: 324 for (i = 0; i < MAX_SCRATCH; i++) { 325 mp_clear(&scratch[i]); 326 } 327 for (i = 0; i < 16; i++) { 328 mp_clear(&precomp[i][0]); 329 mp_clear(&precomp[i][1]); 330 } 331 mp_clear(&tpx); 332 mp_clear(&tpy); 333 mp_clear(&rz); 334 mp_clear(&raz4); 335 #ifdef _KERNEL 336 kmem_free(naf, (orderBitSize + 1)); 337 #else 338 free(naf); 339 #endif 340 return res; 341 } 342