usr/src/common/crypto/ecc/ecp_test.c

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