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 * Douglas Stebila <douglas@stebila.ca>, 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 #ifdef _KERNEL 46 #include <sys/types.h> 47 #include <sys/systm.h> 48 #include <sys/param.h> 49 #include <sys/modctl.h> 50 #include <sys/ddi.h> 51 #include <sys/crypto/spi.h> 52 #include <sys/sysmacros.h> 53 #include <sys/strsun.h> 54 #include <sys/md5.h> 55 #include <sys/sha1.h> 56 #include <sys/sha2.h> 57 #include <sys/random.h> 58 #include <sys/conf.h> 59 #include <sys/devops.h> 60 #include <sys/sunddi.h> 61 #include <sys/varargs.h> 62 #include <sys/kmem.h> 63 #include <sys/kstat.h> 64 #include <sys/crypto/common.h> 65 #else 66 #include <stdio.h> 67 #include <string.h> 68 #include <strings.h> 69 #include <assert.h> 70 #include <time.h> 71 #include <sys/time.h> 72 #include <sys/resource.h> 73 #endif /* _KERNEL */ 74 75 #include "mpi.h" 76 #include "mplogic.h" 77 #include "mpprime.h" 78 #include "ecl.h" 79 #include "ecl-curve.h" 80 #include "ecp.h" 81 #include "ecc_impl.h" 82 #include "ec.h" 83 84 #ifndef KM_SLEEP 85 #define KM_SLEEP 0 86 #endif 87 88 #ifndef _KERNEL 89 /* Time k repetitions of operation op. */ 90 #define M_TimeOperation(op, k) { \ 91 double dStart, dNow, dUserTime; \ 92 struct rusage ru; \ 93 int i; \ 94 getrusage(RUSAGE_SELF, &ru); \ 95 dStart = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \ 96 for (i = 0; i < k; i++) { \ 97 { op; } \ 98 }; \ 99 getrusage(RUSAGE_SELF, &ru); \ 100 dNow = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \ 101 dUserTime = dNow-dStart; \ 102 if (dUserTime) printf(" %-45s k: %6i, t: %6.2f sec\n", #op, k, dUserTime); \ 103 } 104 #else 105 #define M_TimeOperation(op, k) 106 #endif 107 108 /* Test curve using generic field arithmetic. */ 109 #define ECTEST_GENERIC_GFP(name_c, name) \ 110 printf("Testing %s using generic implementation...\n", name_c); \ 111 params = EC_GetNamedCurveParams(name, KM_SLEEP); \ 112 if (params == NULL) { \ 113 printf(" Error: could not construct params.\n"); \ 114 res = MP_NO; \ 115 goto CLEANUP; \ 116 } \ 117 ECGroup_free(group); \ 118 group = ECGroup_fromHex(params, KM_SLEEP); \ 119 if (group == NULL) { \ 120 printf(" Error: could not construct group.\n"); \ 121 res = MP_NO; \ 122 goto CLEANUP; \ 123 } \ 124 MP_CHECKOK( ectest_curve_GFp(group, ectestPrint, ectestTime, 1, KM_SLEEP) ); \ 125 printf("... okay.\n"); 126 127 /* Test curve using specific field arithmetic. */ 128 #define ECTEST_NAMED_GFP(name_c, name) \ 129 printf("Testing %s using specific implementation...\n", name_c); \ 130 ECGroup_free(group); \ 131 group = ECGroup_fromName(name, KM_SLEEP); \ 132 if (group == NULL) { \ 133 printf(" Warning: could not construct group.\n"); \ 134 printf("... failed; continuing with remaining tests.\n"); \ 135 } else { \ 136 MP_CHECKOK( ectest_curve_GFp(group, ectestPrint, ectestTime, 0, KM_SLEEP) ); \ 137 printf("... okay.\n"); \ 138 } 139 140 /* Performs basic tests of elliptic curve cryptography over prime fields. 141 * If tests fail, then it prints an error message, aborts, and returns an 142 * error code. Otherwise, returns 0. */ 143 int 144 ectest_curve_GFp(ECGroup *group, int ectestPrint, int ectestTime, 145 int generic, int kmflag) 146 { 147 148 mp_int one, order_1, gx, gy, rx, ry, n; 149 int size; 150 mp_err res; 151 char s[1000]; 152 153 /* initialize values */ 154 MP_CHECKOK(mp_init(&one, kmflag)); 155 MP_CHECKOK(mp_init(&order_1, kmflag)); 156 MP_CHECKOK(mp_init(&gx, kmflag)); 157 MP_CHECKOK(mp_init(&gy, kmflag)); 158 MP_CHECKOK(mp_init(&rx, kmflag)); 159 MP_CHECKOK(mp_init(&ry, kmflag)); 160 MP_CHECKOK(mp_init(&n, kmflag)); 161 162 MP_CHECKOK(mp_set_int(&one, 1)); 163 MP_CHECKOK(mp_sub(&group->order, &one, &order_1)); 164 165 /* encode base point */ 166 if (group->meth->field_dec) { 167 MP_CHECKOK(group->meth->field_dec(&group->genx, &gx, group->meth)); 168 MP_CHECKOK(group->meth->field_dec(&group->geny, &gy, group->meth)); 169 } else { 170 MP_CHECKOK(mp_copy(&group->genx, &gx)); 171 MP_CHECKOK(mp_copy(&group->geny, &gy)); 172 } 173 if (ectestPrint) { 174 /* output base point */ 175 printf(" base point P:\n"); 176 MP_CHECKOK(mp_toradix(&gx, s, 16)); 177 printf(" %s\n", s); 178 MP_CHECKOK(mp_toradix(&gy, s, 16)); 179 printf(" %s\n", s); 180 if (group->meth->field_enc) { 181 printf(" base point P (encoded):\n"); 182 MP_CHECKOK(mp_toradix(&group->genx, s, 16)); 183 printf(" %s\n", s); 184 MP_CHECKOK(mp_toradix(&group->geny, s, 16)); 185 printf(" %s\n", s); 186 } 187 } 188 189 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF 190 /* multiply base point by order - 1 and check for negative of base 191 * point */ 192 MP_CHECKOK(ec_GFp_pt_mul_aff 193 (&order_1, &group->genx, &group->geny, &rx, &ry, group)); 194 if (ectestPrint) { 195 printf(" (order-1)*P (affine):\n"); 196 MP_CHECKOK(mp_toradix(&rx, s, 16)); 197 printf(" %s\n", s); 198 MP_CHECKOK(mp_toradix(&ry, s, 16)); 199 printf(" %s\n", s); 200 } 201 MP_CHECKOK(group->meth->field_neg(&ry, &ry, group->meth)); 202 if ((mp_cmp(&rx, &group->genx) != 0) 203 || (mp_cmp(&ry, &group->geny) != 0)) { 204 printf(" Error: invalid result (expected (- base point)).\n"); 205 res = MP_NO; 206 goto CLEANUP; 207 } 208 #endif 209 210 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF 211 /* multiply base point by order - 1 and check for negative of base 212 * point */ 213 MP_CHECKOK(ec_GFp_pt_mul_jac 214 (&order_1, &group->genx, &group->geny, &rx, &ry, group)); 215 if (ectestPrint) { 216 printf(" (order-1)*P (jacobian):\n"); 217 MP_CHECKOK(mp_toradix(&rx, s, 16)); 218 printf(" %s\n", s); 219 MP_CHECKOK(mp_toradix(&ry, s, 16)); 220 printf(" %s\n", s); 221 } 222 MP_CHECKOK(group->meth->field_neg(&ry, &ry, group->meth)); 223 if ((mp_cmp(&rx, &group->genx) != 0) 224 || (mp_cmp(&ry, &group->geny) != 0)) { 225 printf(" Error: invalid result (expected (- base point)).\n"); 226 res = MP_NO; 227 goto CLEANUP; 228 } 229 #endif 230 231 /* multiply base point by order - 1 and check for negative of base 232 * point */ 233 MP_CHECKOK(ECPoint_mul(group, &order_1, NULL, NULL, &rx, &ry)); 234 if (ectestPrint) { 235 printf(" (order-1)*P (ECPoint_mul):\n"); 236 MP_CHECKOK(mp_toradix(&rx, s, 16)); 237 printf(" %s\n", s); 238 MP_CHECKOK(mp_toradix(&ry, s, 16)); 239 printf(" %s\n", s); 240 } 241 MP_CHECKOK(mp_submod(&group->meth->irr, &ry, &group->meth->irr, &ry)); 242 if ((mp_cmp(&rx, &gx) != 0) || (mp_cmp(&ry, &gy) != 0)) { 243 printf(" Error: invalid result (expected (- base point)).\n"); 244 res = MP_NO; 245 goto CLEANUP; 246 } 247 248 /* multiply base point by order - 1 and check for negative of base 249 * point */ 250 MP_CHECKOK(ECPoint_mul(group, &order_1, &gx, &gy, &rx, &ry)); 251 if (ectestPrint) { 252 printf(" (order-1)*P (ECPoint_mul):\n"); 253 MP_CHECKOK(mp_toradix(&rx, s, 16)); 254 printf(" %s\n", s); 255 MP_CHECKOK(mp_toradix(&ry, s, 16)); 256 printf(" %s\n", s); 257 } 258 MP_CHECKOK(mp_submod(&group->meth->irr, &ry, &group->meth->irr, &ry)); 259 if ((mp_cmp(&rx, &gx) != 0) || (mp_cmp(&ry, &gy) != 0)) { 260 printf(" Error: invalid result (expected (- base point)).\n"); 261 res = MP_NO; 262 goto CLEANUP; 263 } 264 265 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF 266 /* multiply base point by order and check for point at infinity */ 267 MP_CHECKOK(ec_GFp_pt_mul_aff 268 (&group->order, &group->genx, &group->geny, &rx, &ry, 269 group)); 270 if (ectestPrint) { 271 printf(" (order)*P (affine):\n"); 272 MP_CHECKOK(mp_toradix(&rx, s, 16)); 273 printf(" %s\n", s); 274 MP_CHECKOK(mp_toradix(&ry, s, 16)); 275 printf(" %s\n", s); 276 } 277 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) { 278 printf(" Error: invalid result (expected point at infinity).\n"); 279 res = MP_NO; 280 goto CLEANUP; 281 } 282 #endif 283 284 #ifdef ECL_ENABLE_GFP_PT_MUL_JAC 285 /* multiply base point by order and check for point at infinity */ 286 MP_CHECKOK(ec_GFp_pt_mul_jac 287 (&group->order, &group->genx, &group->geny, &rx, &ry, 288 group)); 289 if (ectestPrint) { 290 printf(" (order)*P (jacobian):\n"); 291 MP_CHECKOK(mp_toradix(&rx, s, 16)); 292 printf(" %s\n", s); 293 MP_CHECKOK(mp_toradix(&ry, s, 16)); 294 printf(" %s\n", s); 295 } 296 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) { 297 printf(" Error: invalid result (expected point at infinity).\n"); 298 res = MP_NO; 299 goto CLEANUP; 300 } 301 #endif 302 303 /* multiply base point by order and check for point at infinity */ 304 MP_CHECKOK(ECPoint_mul(group, &group->order, NULL, NULL, &rx, &ry)); 305 if (ectestPrint) { 306 printf(" (order)*P (ECPoint_mul):\n"); 307 MP_CHECKOK(mp_toradix(&rx, s, 16)); 308 printf(" %s\n", s); 309 MP_CHECKOK(mp_toradix(&ry, s, 16)); 310 printf(" %s\n", s); 311 } 312 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) { 313 printf(" Error: invalid result (expected point at infinity).\n"); 314 res = MP_NO; 315 goto CLEANUP; 316 } 317 318 /* multiply base point by order and check for point at infinity */ 319 MP_CHECKOK(ECPoint_mul(group, &group->order, &gx, &gy, &rx, &ry)); 320 if (ectestPrint) { 321 printf(" (order)*P (ECPoint_mul):\n"); 322 MP_CHECKOK(mp_toradix(&rx, s, 16)); 323 printf(" %s\n", s); 324 MP_CHECKOK(mp_toradix(&ry, s, 16)); 325 printf(" %s\n", s); 326 } 327 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) { 328 printf(" Error: invalid result (expected point at infinity).\n"); 329 res = MP_NO; 330 goto CLEANUP; 331 } 332 333 /* check that (order-1)P + (order-1)P + P == (order-1)P */ 334 MP_CHECKOK(ECPoints_mul 335 (group, &order_1, &order_1, &gx, &gy, &rx, &ry)); 336 MP_CHECKOK(ECPoints_mul(group, &one, &one, &rx, &ry, &rx, &ry)); 337 if (ectestPrint) { 338 printf 339 (" (order-1)*P + (order-1)*P + P == (order-1)*P (ECPoints_mul):\n"); 340 MP_CHECKOK(mp_toradix(&rx, s, 16)); 341 printf(" %s\n", s); 342 MP_CHECKOK(mp_toradix(&ry, s, 16)); 343 printf(" %s\n", s); 344 } 345 MP_CHECKOK(mp_submod(&group->meth->irr, &ry, &group->meth->irr, &ry)); 346 if ((mp_cmp(&rx, &gx) != 0) || (mp_cmp(&ry, &gy) != 0)) { 347 printf(" Error: invalid result (expected (- base point)).\n"); 348 res = MP_NO; 349 goto CLEANUP; 350 } 351 352 /* test validate_point function */ 353 if (ECPoint_validate(group, &gx, &gy) != MP_YES) { 354 printf(" Error: validate point on base point failed.\n"); 355 res = MP_NO; 356 goto CLEANUP; 357 } 358 MP_CHECKOK(mp_add_d(&gy, 1, &ry)); 359 if (ECPoint_validate(group, &gx, &ry) != MP_NO) { 360 printf(" Error: validate point on invalid point passed.\n"); 361 res = MP_NO; 362 goto CLEANUP; 363 } 364 365 if (ectestTime) { 366 /* compute random scalar */ 367 size = mpl_significant_bits(&group->meth->irr); 368 if (size < MP_OKAY) { 369 goto CLEANUP; 370 } 371 MP_CHECKOK(mpp_random_size(&n, (size + ECL_BITS - 1) / ECL_BITS)); 372 MP_CHECKOK(group->meth->field_mod(&n, &n, group->meth)); 373 /* timed test */ 374 if (generic) { 375 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF 376 M_TimeOperation(MP_CHECKOK 377 (ec_GFp_pt_mul_aff 378 (&n, &group->genx, &group->geny, &rx, &ry, 379 group)), 100); 380 #endif 381 M_TimeOperation(MP_CHECKOK 382 (ECPoint_mul(group, &n, NULL, NULL, &rx, &ry)), 383 100); 384 M_TimeOperation(MP_CHECKOK 385 (ECPoints_mul 386 (group, &n, &n, &gx, &gy, &rx, &ry)), 100); 387 } else { 388 M_TimeOperation(MP_CHECKOK 389 (ECPoint_mul(group, &n, NULL, NULL, &rx, &ry)), 390 100); 391 M_TimeOperation(MP_CHECKOK 392 (ECPoint_mul(group, &n, &gx, &gy, &rx, &ry)), 393 100); 394 M_TimeOperation(MP_CHECKOK 395 (ECPoints_mul 396 (group, &n, &n, &gx, &gy, &rx, &ry)), 100); 397 } 398 } 399 400 CLEANUP: 401 mp_clear(&one); 402 mp_clear(&order_1); 403 mp_clear(&gx); 404 mp_clear(&gy); 405 mp_clear(&rx); 406 mp_clear(&ry); 407 mp_clear(&n); 408 if (res != MP_OKAY) { 409 #ifdef _KERNEL 410 printf(" Error: exiting with error value 0x%x\n", res); 411 #else 412 printf(" Error: exiting with error value %i\n", res); 413 #endif 414 } 415 return res; 416 } 417 418 /* Performs tests of elliptic curve cryptography over prime fields If 419 * tests fail, then it prints an error message, aborts, and returns an 420 * error code. Otherwise, returns 0. */ 421 int 422 ecp_test() 423 { 424 425 int ectestTime = 0; 426 int ectestPrint = 0; 427 int i; 428 ECGroup *group = NULL; 429 ECCurveParams *params = NULL; 430 mp_err res; 431 432 /* generic arithmetic tests */ 433 ECTEST_GENERIC_GFP("SECP-160R1", ECCurve_SECG_PRIME_160R1); 434 435 /* specific arithmetic tests */ 436 ECTEST_NAMED_GFP("NIST-P192", ECCurve_NIST_P192); 437 ECTEST_NAMED_GFP("NIST-P224", ECCurve_NIST_P224); 438 ECTEST_NAMED_GFP("NIST-P256", ECCurve_NIST_P256); 439 ECTEST_NAMED_GFP("NIST-P384", ECCurve_NIST_P384); 440 ECTEST_NAMED_GFP("NIST-P521", ECCurve_NIST_P521); 441 ECTEST_NAMED_GFP("ANSI X9.62 PRIME192v1", ECCurve_X9_62_PRIME_192V1); 442 ECTEST_NAMED_GFP("ANSI X9.62 PRIME192v2", ECCurve_X9_62_PRIME_192V2); 443 ECTEST_NAMED_GFP("ANSI X9.62 PRIME192v3", ECCurve_X9_62_PRIME_192V3); 444 ECTEST_NAMED_GFP("ANSI X9.62 PRIME239v1", ECCurve_X9_62_PRIME_239V1); 445 ECTEST_NAMED_GFP("ANSI X9.62 PRIME239v2", ECCurve_X9_62_PRIME_239V2); 446 ECTEST_NAMED_GFP("ANSI X9.62 PRIME239v3", ECCurve_X9_62_PRIME_239V3); 447 ECTEST_NAMED_GFP("ANSI X9.62 PRIME256v1", ECCurve_X9_62_PRIME_256V1); 448 ECTEST_NAMED_GFP("SECP-112R1", ECCurve_SECG_PRIME_112R1); 449 ECTEST_NAMED_GFP("SECP-112R2", ECCurve_SECG_PRIME_112R2); 450 ECTEST_NAMED_GFP("SECP-128R1", ECCurve_SECG_PRIME_128R1); 451 ECTEST_NAMED_GFP("SECP-128R2", ECCurve_SECG_PRIME_128R2); 452 ECTEST_NAMED_GFP("SECP-160K1", ECCurve_SECG_PRIME_160K1); 453 ECTEST_NAMED_GFP("SECP-160R1", ECCurve_SECG_PRIME_160R1); 454 ECTEST_NAMED_GFP("SECP-160R2", ECCurve_SECG_PRIME_160R2); 455 ECTEST_NAMED_GFP("SECP-192K1", ECCurve_SECG_PRIME_192K1); 456 ECTEST_NAMED_GFP("SECP-192R1", ECCurve_SECG_PRIME_192R1); 457 ECTEST_NAMED_GFP("SECP-224K1", ECCurve_SECG_PRIME_224K1); 458 ECTEST_NAMED_GFP("SECP-224R1", ECCurve_SECG_PRIME_224R1); 459 ECTEST_NAMED_GFP("SECP-256K1", ECCurve_SECG_PRIME_256K1); 460 ECTEST_NAMED_GFP("SECP-256R1", ECCurve_SECG_PRIME_256R1); 461 ECTEST_NAMED_GFP("SECP-384R1", ECCurve_SECG_PRIME_384R1); 462 ECTEST_NAMED_GFP("SECP-521R1", ECCurve_SECG_PRIME_521R1); 463 ECTEST_NAMED_GFP("WTLS-6 (112)", ECCurve_WTLS_6); 464 ECTEST_NAMED_GFP("WTLS-7 (160)", ECCurve_WTLS_7); 465 ECTEST_NAMED_GFP("WTLS-8 (112)", ECCurve_WTLS_8); 466 ECTEST_NAMED_GFP("WTLS-9 (160)", ECCurve_WTLS_9); 467 ECTEST_NAMED_GFP("WTLS-12 (224)", ECCurve_WTLS_12); 468 469 CLEANUP: 470 EC_FreeCurveParams(params); 471 ECGroup_free(group); 472 if (res != MP_OKAY) { 473 #ifdef _KERNEL 474 printf("Error: exiting with error value 0x%x\n", res); 475 #else 476 printf("Error: exiting with error value %i\n", res); 477 #endif 478 } 479 return res; 480 } 481