security/nss/lib/freebl/ecl/tests/ec_naft.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.
  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 #include "mpi.h"
  40 #include "mplogic.h"
  41 #include "ecl.h"
  42 #include "ecp.h"
  43 #include "ecl-priv.h"
  44
  45 #include <sys/types.h>
  46 #include <stdio.h>
  47 #include <time.h>
  48 #include <sys/time.h>
  49 #include <sys/resource.h>
  50
  51 /* Returns 2^e as an integer. This is meant to be used for small powers of
  52  * two. */
  53 int ec_twoTo(int e);
  54
  55 /* Number of bits of scalar to test */
  56 #define BITSIZE 160
  57
  58 /* Time k repetitions of operation op. */
  59 #define M_TimeOperation(op, k) { \
  60         double dStart, dNow, dUserTime; \
  61         struct rusage ru; \
  62         int i; \
  63         getrusage(RUSAGE_SELF, &ru); \
  64         dStart = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
  65         for (i = 0; i < k; i++) { \
  66                 { op; } \
  67         }; \
  68         getrusage(RUSAGE_SELF, &ru); \
  69         dNow = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
  70         dUserTime = dNow-dStart; \
  71         if (dUserTime) printf("    %-45s\n      k: %6i, t: %6.2f sec\n", #op, k, dUserTime); \
  72 }
  73
  74 /* Tests wNAF computation. Non-adjacent-form is discussed in the paper: D.
  75  * Hankerson, J. Hernandez and A. Menezes, "Software implementation of
  76  * elliptic curve cryptography over binary fields", Proc. CHES 2000. */
  77
  78 mp_err
  79 main(void)
  80 {
  81         signed char naf[BITSIZE + 1];
  82         ECGroup *group = NULL;
  83         mp_int k;
  84         mp_int *scalar;
  85         int i, count;
  86         int res;
  87         int w = 5;
  88         char s[1000];
  89
  90         /* Get a 160 bit scalar to compute wNAF from */
  91         group = ECGroup_fromName(ECCurve_SECG_PRIME_160R1);
  92         scalar = &group->genx;
  93
  94         /* Compute wNAF representation of scalar */
  95         ec_compute_wNAF(naf, BITSIZE, scalar, w);
  96
  97         /* Verify correctness of representation */
  98         mp_init(&k);                            /* init k to 0 */
  99
 100         for (i = BITSIZE; i >= 0; i--) {
 101                 mp_add(&k, &k, &k);
 102                 /* digits in mp_???_d are unsigned */
 103                 if (naf[i] >= 0) {
 104                         mp_add_d(&k, naf[i], &k);
 105                 } else {
 106                         mp_sub_d(&k, -naf[i], &k);
 107                 }
 108         }
 109
 110         if (mp_cmp(&k, scalar) != 0) {
 111                 printf("Error:  incorrect NAF value.\n");
 112                 MP_CHECKOK(mp_toradix(&k, s, 16));
 113                 printf("NAF value   %s\n", s);
 114                 MP_CHECKOK(mp_toradix(scalar, s, 16));
 115                 printf("original value   %s\n", s);
 116                 goto CLEANUP;
 117         }
 118
 119         /* Verify digits of representation are valid */
 120         for (i = 0; i <= BITSIZE; i++) {
 121                 if (naf[i] % 2 == 0 && naf[i] != 0) {
 122                         printf("Error:  Even non-zero digit found.\n");
 123                         goto CLEANUP;
 124                 }
 125                 if (naf[i] < -(ec_twoTo(w - 1)) || naf[i] >= ec_twoTo(w - 1)) {
 126                         printf("Error:  Magnitude of naf digit too large.\n");
 127                         goto CLEANUP;
 128                 }
 129         }
 130
 131         /* Verify sparsity of representation */
 132         count = w - 1;
 133         for (i = 0; i <= BITSIZE; i++) {
 134                 if (naf[i] != 0) {
 135                         if (count < w - 1) {
 136                                 printf("Error:  Sparsity failed.\n");
 137                                 goto CLEANUP;
 138                         }
 139                         count = 0;
 140                 } else
 141                         count++;
 142         }
 143
 144         /* Check timing */
 145         M_TimeOperation(ec_compute_wNAF(naf, BITSIZE, scalar, w), 10000);
 146
 147         printf("Test passed.\n");
 148   CLEANUP:
 149         ECGroup_free(group);
 150         return MP_OKAY;
 151 }