1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/ecl/tests/ec_naft.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,117 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +#include "mpi.h"
1.9 +#include "mplogic.h"
1.10 +#include "ecl.h"
1.11 +#include "ecp.h"
1.12 +#include "ecl-priv.h"
1.13 +
1.14 +#include <sys/types.h>
1.15 +#include <stdio.h>
1.16 +#include <time.h>
1.17 +#include <sys/time.h>
1.18 +#include <sys/resource.h>
1.19 +
1.20 +/* Returns 2^e as an integer. This is meant to be used for small powers of
1.21 + * two. */
1.22 +int ec_twoTo(int e);
1.23 +
1.24 +/* Number of bits of scalar to test */
1.25 +#define BITSIZE 160
1.26 +
1.27 +/* Time k repetitions of operation op. */
1.28 +#define M_TimeOperation(op, k) { \
1.29 + double dStart, dNow, dUserTime; \
1.30 + struct rusage ru; \
1.31 + int i; \
1.32 + getrusage(RUSAGE_SELF, &ru); \
1.33 + dStart = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
1.34 + for (i = 0; i < k; i++) { \
1.35 + { op; } \
1.36 + }; \
1.37 + getrusage(RUSAGE_SELF, &ru); \
1.38 + dNow = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
1.39 + dUserTime = dNow-dStart; \
1.40 + if (dUserTime) printf(" %-45s\n k: %6i, t: %6.2f sec\n", #op, k, dUserTime); \
1.41 +}
1.42 +
1.43 +/* Tests wNAF computation. Non-adjacent-form is discussed in the paper: D.
1.44 + * Hankerson, J. Hernandez and A. Menezes, "Software implementation of
1.45 + * elliptic curve cryptography over binary fields", Proc. CHES 2000. */
1.46 +
1.47 +mp_err
1.48 +main(void)
1.49 +{
1.50 + signed char naf[BITSIZE + 1];
1.51 + ECGroup *group = NULL;
1.52 + mp_int k;
1.53 + mp_int *scalar;
1.54 + int i, count;
1.55 + int res;
1.56 + int w = 5;
1.57 + char s[1000];
1.58 +
1.59 + /* Get a 160 bit scalar to compute wNAF from */
1.60 + group = ECGroup_fromName(ECCurve_SECG_PRIME_160R1);
1.61 + scalar = &group->genx;
1.62 +
1.63 + /* Compute wNAF representation of scalar */
1.64 + ec_compute_wNAF(naf, BITSIZE, scalar, w);
1.65 +
1.66 + /* Verify correctness of representation */
1.67 + mp_init(&k); /* init k to 0 */
1.68 +
1.69 + for (i = BITSIZE; i >= 0; i--) {
1.70 + mp_add(&k, &k, &k);
1.71 + /* digits in mp_???_d are unsigned */
1.72 + if (naf[i] >= 0) {
1.73 + mp_add_d(&k, naf[i], &k);
1.74 + } else {
1.75 + mp_sub_d(&k, -naf[i], &k);
1.76 + }
1.77 + }
1.78 +
1.79 + if (mp_cmp(&k, scalar) != 0) {
1.80 + printf("Error: incorrect NAF value.\n");
1.81 + MP_CHECKOK(mp_toradix(&k, s, 16));
1.82 + printf("NAF value %s\n", s);
1.83 + MP_CHECKOK(mp_toradix(scalar, s, 16));
1.84 + printf("original value %s\n", s);
1.85 + goto CLEANUP;
1.86 + }
1.87 +
1.88 + /* Verify digits of representation are valid */
1.89 + for (i = 0; i <= BITSIZE; i++) {
1.90 + if (naf[i] % 2 == 0 && naf[i] != 0) {
1.91 + printf("Error: Even non-zero digit found.\n");
1.92 + goto CLEANUP;
1.93 + }
1.94 + if (naf[i] < -(ec_twoTo(w - 1)) || naf[i] >= ec_twoTo(w - 1)) {
1.95 + printf("Error: Magnitude of naf digit too large.\n");
1.96 + goto CLEANUP;
1.97 + }
1.98 + }
1.99 +
1.100 + /* Verify sparsity of representation */
1.101 + count = w - 1;
1.102 + for (i = 0; i <= BITSIZE; i++) {
1.103 + if (naf[i] != 0) {
1.104 + if (count < w - 1) {
1.105 + printf("Error: Sparsity failed.\n");
1.106 + goto CLEANUP;
1.107 + }
1.108 + count = 0;
1.109 + } else
1.110 + count++;
1.111 + }
1.112 +
1.113 + /* Check timing */
1.114 + M_TimeOperation(ec_compute_wNAF(naf, BITSIZE, scalar, w), 10000);
1.115 +
1.116 + printf("Test passed.\n");
1.117 + CLEANUP:
1.118 + ECGroup_free(group);
1.119 + return MP_OKAY;
1.120 +}
