Back to index

lightning-sunbird  0.9+nobinonly
ecp_test.c
Go to the documentation of this file.
00001 /* 
00002  * ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the elliptic curve math library for prime field curves.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Sun Microsystems, Inc.
00019  * Portions created by the Initial Developer are Copyright (C) 2003
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 #include "mpi.h"
00040 #include "mplogic.h"
00041 #include "mpprime.h"
00042 #include "ecl.h"
00043 #include "ecl-curve.h"
00044 #include "ecp.h"
00045 #include <stdio.h>
00046 #include <strings.h>
00047 #include <assert.h>
00048 
00049 #include <time.h>
00050 #include <sys/time.h>
00051 #include <sys/resource.h>
00052 
00053 /* Time k repetitions of operation op. */
00054 #define M_TimeOperation(op, k) { \
00055        double dStart, dNow, dUserTime; \
00056        struct rusage ru; \
00057        int i; \
00058        getrusage(RUSAGE_SELF, &ru); \
00059        dStart = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
00060        for (i = 0; i < k; i++) { \
00061               { op; } \
00062        }; \
00063        getrusage(RUSAGE_SELF, &ru); \
00064        dNow = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
00065        dUserTime = dNow-dStart; \
00066        if (dUserTime) printf("    %-45s k: %6i, t: %6.2f sec\n", #op, k, dUserTime); \
00067 }
00068 
00069 /* Test curve using generic field arithmetic. */
00070 #define ECTEST_GENERIC_GFP(name_c, name) \
00071        printf("Testing %s using generic implementation...\n", name_c); \
00072        params = EC_GetNamedCurveParams(name); \
00073        if (params == NULL) { \
00074                      printf("  Error: could not construct params.\n"); \
00075                      res = MP_NO; \
00076                      goto CLEANUP; \
00077        } \
00078        ECGroup_free(group); \
00079        group = ECGroup_fromHex(params); \
00080        if (group == NULL) { \
00081               printf("  Error: could not construct group.\n"); \
00082               res = MP_NO; \
00083               goto CLEANUP; \
00084        } \
00085        MP_CHECKOK( ectest_curve_GFp(group, ectestPrint, ectestTime, 1) ); \
00086        printf("... okay.\n");
00087 
00088 /* Test curve using specific field arithmetic. */
00089 #define ECTEST_NAMED_GFP(name_c, name) \
00090        printf("Testing %s using specific implementation...\n", name_c); \
00091        ECGroup_free(group); \
00092        group = ECGroup_fromName(name); \
00093        if (group == NULL) { \
00094               printf("  Warning: could not construct group.\n"); \
00095               printf("... failed; continuing with remaining tests.\n"); \
00096        } else { \
00097               MP_CHECKOK( ectest_curve_GFp(group, ectestPrint, ectestTime, 0) ); \
00098               printf("... okay.\n"); \
00099        }
00100 
00101 /* Performs basic tests of elliptic curve cryptography over prime fields.
00102  * If tests fail, then it prints an error message, aborts, and returns an
00103  * error code. Otherwise, returns 0. */
00104 int
00105 ectest_curve_GFp(ECGroup *group, int ectestPrint, int ectestTime,
00106                              int generic)
00107 {
00108 
00109        mp_int one, order_1, gx, gy, rx, ry, n;
00110        int size;
00111        mp_err res;
00112        char s[1000];
00113 
00114        /* initialize values */
00115        MP_CHECKOK(mp_init(&one));
00116        MP_CHECKOK(mp_init(&order_1));
00117        MP_CHECKOK(mp_init(&gx));
00118        MP_CHECKOK(mp_init(&gy));
00119        MP_CHECKOK(mp_init(&rx));
00120        MP_CHECKOK(mp_init(&ry));
00121        MP_CHECKOK(mp_init(&n));
00122 
00123        MP_CHECKOK(mp_set_int(&one, 1));
00124        MP_CHECKOK(mp_sub(&group->order, &one, &order_1));
00125 
00126        /* encode base point */
00127        if (group->meth->field_dec) {
00128               MP_CHECKOK(group->meth->field_dec(&group->genx, &gx, group->meth));
00129               MP_CHECKOK(group->meth->field_dec(&group->geny, &gy, group->meth));
00130        } else {
00131               MP_CHECKOK(mp_copy(&group->genx, &gx));
00132               MP_CHECKOK(mp_copy(&group->geny, &gy));
00133        }
00134        if (ectestPrint) {
00135               /* output base point */
00136               printf("  base point P:\n");
00137               MP_CHECKOK(mp_toradix(&gx, s, 16));
00138               printf("    %s\n", s);
00139               MP_CHECKOK(mp_toradix(&gy, s, 16));
00140               printf("    %s\n", s);
00141               if (group->meth->field_enc) {
00142                      printf("  base point P (encoded):\n");
00143                      MP_CHECKOK(mp_toradix(&group->genx, s, 16));
00144                      printf("    %s\n", s);
00145                      MP_CHECKOK(mp_toradix(&group->geny, s, 16));
00146                      printf("    %s\n", s);
00147               }
00148        }
00149 
00150 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF
00151        /* multiply base point by order - 1 and check for negative of base
00152         * point */
00153        MP_CHECKOK(ec_GFp_pt_mul_aff
00154                         (&order_1, &group->genx, &group->geny, &rx, &ry, group));
00155        if (ectestPrint) {
00156               printf("  (order-1)*P (affine):\n");
00157               MP_CHECKOK(mp_toradix(&rx, s, 16));
00158               printf("    %s\n", s);
00159               MP_CHECKOK(mp_toradix(&ry, s, 16));
00160               printf("    %s\n", s);
00161        }
00162        MP_CHECKOK(group->meth->field_neg(&ry, &ry, group->meth));
00163        if ((mp_cmp(&rx, &group->genx) != 0)
00164               || (mp_cmp(&ry, &group->geny) != 0)) {
00165               printf("  Error: invalid result (expected (- base point)).\n");
00166               res = MP_NO;
00167               goto CLEANUP;
00168        }
00169 #endif
00170 
00171 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF
00172        /* multiply base point by order - 1 and check for negative of base
00173         * point */
00174        MP_CHECKOK(ec_GFp_pt_mul_jac
00175                         (&order_1, &group->genx, &group->geny, &rx, &ry, group));
00176        if (ectestPrint) {
00177               printf("  (order-1)*P (jacobian):\n");
00178               MP_CHECKOK(mp_toradix(&rx, s, 16));
00179               printf("    %s\n", s);
00180               MP_CHECKOK(mp_toradix(&ry, s, 16));
00181               printf("    %s\n", s);
00182        }
00183        MP_CHECKOK(group->meth->field_neg(&ry, &ry, group->meth));
00184        if ((mp_cmp(&rx, &group->genx) != 0)
00185               || (mp_cmp(&ry, &group->geny) != 0)) {
00186               printf("  Error: invalid result (expected (- base point)).\n");
00187               res = MP_NO;
00188               goto CLEANUP;
00189        }
00190 #endif
00191 
00192        /* multiply base point by order - 1 and check for negative of base
00193         * point */
00194        MP_CHECKOK(ECPoint_mul(group, &order_1, NULL, NULL, &rx, &ry));
00195        if (ectestPrint) {
00196               printf("  (order-1)*P (ECPoint_mul):\n");
00197               MP_CHECKOK(mp_toradix(&rx, s, 16));
00198               printf("    %s\n", s);
00199               MP_CHECKOK(mp_toradix(&ry, s, 16));
00200               printf("    %s\n", s);
00201        }
00202        MP_CHECKOK(mp_submod(&group->meth->irr, &ry, &group->meth->irr, &ry));
00203        if ((mp_cmp(&rx, &gx) != 0) || (mp_cmp(&ry, &gy) != 0)) {
00204               printf("  Error: invalid result (expected (- base point)).\n");
00205               res = MP_NO;
00206               goto CLEANUP;
00207        }
00208 
00209        /* multiply base point by order - 1 and check for negative of base
00210         * point */
00211        MP_CHECKOK(ECPoint_mul(group, &order_1, &gx, &gy, &rx, &ry));
00212        if (ectestPrint) {
00213               printf("  (order-1)*P (ECPoint_mul):\n");
00214               MP_CHECKOK(mp_toradix(&rx, s, 16));
00215               printf("    %s\n", s);
00216               MP_CHECKOK(mp_toradix(&ry, s, 16));
00217               printf("    %s\n", s);
00218        }
00219        MP_CHECKOK(mp_submod(&group->meth->irr, &ry, &group->meth->irr, &ry));
00220        if ((mp_cmp(&rx, &gx) != 0) || (mp_cmp(&ry, &gy) != 0)) {
00221               printf("  Error: invalid result (expected (- base point)).\n");
00222               res = MP_NO;
00223               goto CLEANUP;
00224        }
00225 
00226 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF
00227        /* multiply base point by order and check for point at infinity */
00228        MP_CHECKOK(ec_GFp_pt_mul_aff
00229                         (&group->order, &group->genx, &group->geny, &rx, &ry,
00230                             group));
00231        if (ectestPrint) {
00232               printf("  (order)*P (affine):\n");
00233               MP_CHECKOK(mp_toradix(&rx, s, 16));
00234               printf("    %s\n", s);
00235               MP_CHECKOK(mp_toradix(&ry, s, 16));
00236               printf("    %s\n", s);
00237        }
00238        if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
00239               printf("  Error: invalid result (expected point at infinity).\n");
00240               res = MP_NO;
00241               goto CLEANUP;
00242        }
00243 #endif
00244 
00245 #ifdef ECL_ENABLE_GFP_PT_MUL_JAC
00246        /* multiply base point by order and check for point at infinity */
00247        MP_CHECKOK(ec_GFp_pt_mul_jac
00248                         (&group->order, &group->genx, &group->geny, &rx, &ry,
00249                             group));
00250        if (ectestPrint) {
00251               printf("  (order)*P (jacobian):\n");
00252               MP_CHECKOK(mp_toradix(&rx, s, 16));
00253               printf("    %s\n", s);
00254               MP_CHECKOK(mp_toradix(&ry, s, 16));
00255               printf("    %s\n", s);
00256        }
00257        if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
00258               printf("  Error: invalid result (expected point at infinity).\n");
00259               res = MP_NO;
00260               goto CLEANUP;
00261        }
00262 #endif
00263 
00264        /* multiply base point by order and check for point at infinity */
00265        MP_CHECKOK(ECPoint_mul(group, &group->order, NULL, NULL, &rx, &ry));
00266        if (ectestPrint) {
00267               printf("  (order)*P (ECPoint_mul):\n");
00268               MP_CHECKOK(mp_toradix(&rx, s, 16));
00269               printf("    %s\n", s);
00270               MP_CHECKOK(mp_toradix(&ry, s, 16));
00271               printf("    %s\n", s);
00272        }
00273        if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
00274               printf("  Error: invalid result (expected point at infinity).\n");
00275               res = MP_NO;
00276               goto CLEANUP;
00277        }
00278 
00279        /* multiply base point by order and check for point at infinity */
00280        MP_CHECKOK(ECPoint_mul(group, &group->order, &gx, &gy, &rx, &ry));
00281        if (ectestPrint) {
00282               printf("  (order)*P (ECPoint_mul):\n");
00283               MP_CHECKOK(mp_toradix(&rx, s, 16));
00284               printf("    %s\n", s);
00285               MP_CHECKOK(mp_toradix(&ry, s, 16));
00286               printf("    %s\n", s);
00287        }
00288        if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
00289               printf("  Error: invalid result (expected point at infinity).\n");
00290               res = MP_NO;
00291               goto CLEANUP;
00292        }
00293 
00294        /* check that (order-1)P + (order-1)P + P == (order-1)P */
00295        MP_CHECKOK(ECPoints_mul
00296                         (group, &order_1, &order_1, &gx, &gy, &rx, &ry));
00297        MP_CHECKOK(ECPoints_mul(group, &one, &one, &rx, &ry, &rx, &ry));
00298        if (ectestPrint) {
00299               printf
00300                      ("  (order-1)*P + (order-1)*P + P == (order-1)*P (ECPoints_mul):\n");
00301               MP_CHECKOK(mp_toradix(&rx, s, 16));
00302               printf("    %s\n", s);
00303               MP_CHECKOK(mp_toradix(&ry, s, 16));
00304               printf("    %s\n", s);
00305        }
00306        MP_CHECKOK(mp_submod(&group->meth->irr, &ry, &group->meth->irr, &ry));
00307        if ((mp_cmp(&rx, &gx) != 0) || (mp_cmp(&ry, &gy) != 0)) {
00308               printf("  Error: invalid result (expected (- base point)).\n");
00309               res = MP_NO;
00310               goto CLEANUP;
00311        }
00312 
00313        /* test validate_point function */
00314        if (ECPoint_validate(group, &gx, &gy) != MP_YES) {
00315               printf("  Error: validate point on base point failed.\n");
00316               res = MP_NO;
00317               goto CLEANUP;
00318        }
00319        MP_CHECKOK(mp_add_d(&gy, 1, &ry));
00320        if (ECPoint_validate(group, &gx, &ry) != MP_NO) {
00321               printf("  Error: validate point on invalid point passed.\n");
00322               res = MP_NO;
00323               goto CLEANUP;
00324        }
00325 
00326        if (ectestTime) {
00327               /* compute random scalar */
00328               size = mpl_significant_bits(&group->meth->irr);
00329               if (size < MP_OKAY) {
00330                      goto CLEANUP;
00331               }
00332               MP_CHECKOK(mpp_random_size(&n, (size + ECL_BITS - 1) / ECL_BITS));
00333               MP_CHECKOK(group->meth->field_mod(&n, &n, group->meth));
00334               /* timed test */
00335               if (generic) {
00336 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF
00337                      M_TimeOperation(MP_CHECKOK
00338                                                  (ec_GFp_pt_mul_aff
00339                                                   (&n, &group->genx, &group->geny, &rx, &ry,
00340                                                    group)), 100);
00341 #endif
00342                      M_TimeOperation(MP_CHECKOK
00343                                                  (ECPoint_mul(group, &n, NULL, NULL, &rx, &ry)),
00344                                                  100);
00345                      M_TimeOperation(MP_CHECKOK
00346                                                  (ECPoints_mul
00347                                                   (group, &n, &n, &gx, &gy, &rx, &ry)), 100);
00348               } else {
00349                      M_TimeOperation(MP_CHECKOK
00350                                                  (ECPoint_mul(group, &n, NULL, NULL, &rx, &ry)),
00351                                                  100);
00352                      M_TimeOperation(MP_CHECKOK
00353                                                  (ECPoint_mul(group, &n, &gx, &gy, &rx, &ry)),
00354                                                  100);
00355                      M_TimeOperation(MP_CHECKOK
00356                                                  (ECPoints_mul
00357                                                   (group, &n, &n, &gx, &gy, &rx, &ry)), 100);
00358               }
00359        }
00360 
00361   CLEANUP:
00362        mp_clear(&one);
00363        mp_clear(&order_1);
00364        mp_clear(&gx);
00365        mp_clear(&gy);
00366        mp_clear(&rx);
00367        mp_clear(&ry);
00368        mp_clear(&n);
00369        if (res != MP_OKAY) {
00370               printf("  Error: exiting with error value %i\n", res);
00371        }
00372        return res;
00373 }
00374 
00375 /* Prints help information. */
00376 void
00377 printUsage()
00378 {
00379        printf("Usage: ecp_test [--print] [--time]\n");
00380        printf
00381               ("     --print     Print out results of each point arithmetic test.\n");
00382        printf
00383               ("     --time      Benchmark point operations and print results.\n");
00384 }
00385 
00386 /* Performs tests of elliptic curve cryptography over prime fields If
00387  * tests fail, then it prints an error message, aborts, and returns an
00388  * error code. Otherwise, returns 0. */
00389 int
00390 main(int argv, char **argc)
00391 {
00392 
00393        int ectestTime = 0;
00394        int ectestPrint = 0;
00395        int i;
00396        ECGroup *group = NULL;
00397        ECCurveParams *params = NULL;
00398        mp_err res;
00399 
00400        /* read command-line arguments */
00401        for (i = 1; i < argv; i++) {
00402               if ((strcasecmp(argc[i], "time") == 0)
00403                      || (strcasecmp(argc[i], "-time") == 0)
00404                      || (strcasecmp(argc[i], "--time") == 0)) {
00405                      ectestTime = 1;
00406               } else if ((strcasecmp(argc[i], "print") == 0)
00407                                || (strcasecmp(argc[i], "-print") == 0)
00408                                || (strcasecmp(argc[i], "--print") == 0)) {
00409                      ectestPrint = 1;
00410               } else {
00411                      printUsage();
00412                      return 0;
00413               }
00414        }
00415 
00416        /* generic arithmetic tests */
00417        ECTEST_GENERIC_GFP("SECP-160R1", ECCurve_SECG_PRIME_160R1);
00418 
00419        /* specific arithmetic tests */
00420        ECTEST_NAMED_GFP("NIST-P192", ECCurve_NIST_P192);
00421        ECTEST_NAMED_GFP("NIST-P224", ECCurve_NIST_P224);
00422        ECTEST_NAMED_GFP("NIST-P256", ECCurve_NIST_P256);
00423        ECTEST_NAMED_GFP("NIST-P384", ECCurve_NIST_P384);
00424        ECTEST_NAMED_GFP("NIST-P521", ECCurve_NIST_P521);
00425        ECTEST_NAMED_GFP("ANSI X9.62 PRIME192v1", ECCurve_X9_62_PRIME_192V1);
00426        ECTEST_NAMED_GFP("ANSI X9.62 PRIME192v2", ECCurve_X9_62_PRIME_192V2);
00427        ECTEST_NAMED_GFP("ANSI X9.62 PRIME192v3", ECCurve_X9_62_PRIME_192V3);
00428        ECTEST_NAMED_GFP("ANSI X9.62 PRIME239v1", ECCurve_X9_62_PRIME_239V1);
00429        ECTEST_NAMED_GFP("ANSI X9.62 PRIME239v2", ECCurve_X9_62_PRIME_239V2);
00430        ECTEST_NAMED_GFP("ANSI X9.62 PRIME239v3", ECCurve_X9_62_PRIME_239V3);
00431        ECTEST_NAMED_GFP("ANSI X9.62 PRIME256v1", ECCurve_X9_62_PRIME_256V1);
00432        ECTEST_NAMED_GFP("SECP-112R1", ECCurve_SECG_PRIME_112R1);
00433        ECTEST_NAMED_GFP("SECP-112R2", ECCurve_SECG_PRIME_112R2);
00434        ECTEST_NAMED_GFP("SECP-128R1", ECCurve_SECG_PRIME_128R1);
00435        ECTEST_NAMED_GFP("SECP-128R2", ECCurve_SECG_PRIME_128R2);
00436        ECTEST_NAMED_GFP("SECP-160K1", ECCurve_SECG_PRIME_160K1);
00437        ECTEST_NAMED_GFP("SECP-160R1", ECCurve_SECG_PRIME_160R1);
00438        ECTEST_NAMED_GFP("SECP-160R2", ECCurve_SECG_PRIME_160R2);
00439        ECTEST_NAMED_GFP("SECP-192K1", ECCurve_SECG_PRIME_192K1);
00440        ECTEST_NAMED_GFP("SECP-192R1", ECCurve_SECG_PRIME_192R1);
00441        ECTEST_NAMED_GFP("SECP-224K1", ECCurve_SECG_PRIME_224K1);
00442        ECTEST_NAMED_GFP("SECP-224R1", ECCurve_SECG_PRIME_224R1);
00443        ECTEST_NAMED_GFP("SECP-256K1", ECCurve_SECG_PRIME_256K1);
00444        ECTEST_NAMED_GFP("SECP-256R1", ECCurve_SECG_PRIME_256R1);
00445        ECTEST_NAMED_GFP("SECP-384R1", ECCurve_SECG_PRIME_384R1);
00446        ECTEST_NAMED_GFP("SECP-521R1", ECCurve_SECG_PRIME_521R1);
00447        ECTEST_NAMED_GFP("WTLS-6 (112)", ECCurve_WTLS_6);
00448        ECTEST_NAMED_GFP("WTLS-7 (160)", ECCurve_WTLS_7);
00449        ECTEST_NAMED_GFP("WTLS-8 (112)", ECCurve_WTLS_8);
00450        ECTEST_NAMED_GFP("WTLS-9 (160)", ECCurve_WTLS_9);
00451        ECTEST_NAMED_GFP("WTLS-12 (224)", ECCurve_WTLS_12);
00452 
00453   CLEANUP:
00454        EC_FreeCurveParams(params);
00455        ECGroup_free(group);
00456        if (res != MP_OKAY) {
00457               printf("Error: exiting with error value %i\n", res);
00458        }
00459        return res;
00460 }