Back to index

lightning-sunbird  0.9+nobinonly
ec_naft.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.
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  *   Stephen Fung <fungstep@hotmail.com>, 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 "ecl.h"
00042 #include "ecp.h"
00043 #include "ecl-priv.h"
00044 
00045 #include <sys/types.h>
00046 #include <stdio.h>
00047 #include <time.h>
00048 #include <sys/time.h>
00049 #include <sys/resource.h>
00050 
00051 /* Returns 2^e as an integer. This is meant to be used for small powers of 
00052  * two. */
00053 int ec_twoTo(int e);
00054 
00055 /* Number of bits of scalar to test */
00056 #define BITSIZE 160
00057 
00058 /* Time k repetitions of operation op. */
00059 #define M_TimeOperation(op, k) { \
00060        double dStart, dNow, dUserTime; \
00061        struct rusage ru; \
00062        int i; \
00063        getrusage(RUSAGE_SELF, &ru); \
00064        dStart = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
00065        for (i = 0; i < k; i++) { \
00066               { op; } \
00067        }; \
00068        getrusage(RUSAGE_SELF, &ru); \
00069        dNow = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
00070        dUserTime = dNow-dStart; \
00071        if (dUserTime) printf("    %-45s\n      k: %6i, t: %6.2f sec\n", #op, k, dUserTime); \
00072 }
00073 
00074 /* Tests wNAF computation. Non-adjacent-form is discussed in the paper: D. 
00075  * Hankerson, J. Hernandez and A. Menezes, "Software implementation of
00076  * elliptic curve cryptography over binary fields", Proc. CHES 2000. */
00077 
00078 mp_err
00079 main(void)
00080 {
00081        signed char naf[BITSIZE + 1];
00082        ECGroup *group = NULL;
00083        mp_int k;
00084        mp_int *scalar;
00085        int i, count;
00086        int res;
00087        int w = 5;
00088        char s[1000];
00089 
00090        /* Get a 160 bit scalar to compute wNAF from */
00091        group = ECGroup_fromName(ECCurve_SECG_PRIME_160R1);
00092        scalar = &group->genx;
00093 
00094        /* Compute wNAF representation of scalar */
00095        ec_compute_wNAF(naf, BITSIZE, scalar, w);
00096 
00097        /* Verify correctness of representation */
00098        mp_init(&k);                       /* init k to 0 */
00099 
00100        for (i = BITSIZE; i >= 0; i--) {
00101               mp_add(&k, &k, &k);
00102               /* digits in mp_???_d are unsigned */
00103               if (naf[i] >= 0) {
00104                      mp_add_d(&k, naf[i], &k);
00105               } else {
00106                      mp_sub_d(&k, -naf[i], &k);
00107               }
00108        }
00109 
00110        if (mp_cmp(&k, scalar) != 0) {
00111               printf("Error:  incorrect NAF value.\n");
00112               MP_CHECKOK(mp_toradix(&k, s, 16));
00113               printf("NAF value   %s\n", s);
00114               MP_CHECKOK(mp_toradix(scalar, s, 16));
00115               printf("original value   %s\n", s);
00116               goto CLEANUP;
00117        }
00118 
00119        /* Verify digits of representation are valid */
00120        for (i = 0; i <= BITSIZE; i++) {
00121               if (naf[i] % 2 == 0 && naf[i] != 0) {
00122                      printf("Error:  Even non-zero digit found.\n");
00123                      goto CLEANUP;
00124               }
00125               if (naf[i] < -(ec_twoTo(w - 1)) || naf[i] >= ec_twoTo(w - 1)) {
00126                      printf("Error:  Magnitude of naf digit too large.\n");
00127                      goto CLEANUP;
00128               }
00129        }
00130 
00131        /* Verify sparsity of representation */
00132        count = w - 1;
00133        for (i = 0; i <= BITSIZE; i++) {
00134               if (naf[i] != 0) {
00135                      if (count < w - 1) {
00136                             printf("Error:  Sparsity failed.\n");
00137                             goto CLEANUP;
00138                      }
00139                      count = 0;
00140               } else
00141                      count++;
00142        }
00143 
00144        /* Check timing */
00145        M_TimeOperation(ec_compute_wNAF(naf, BITSIZE, scalar, w), 10000);
00146 
00147        printf("Test passed.\n");
00148   CLEANUP:
00149        ECGroup_free(group);
00150        return MP_OKAY;
00151 }