1/* 2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved. 3 * Use is subject to license terms. 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public 7 * License as published by the Free Software Foundation; either 8 * version 2.1 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public License 16 * along with this library; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24/* ********************************************************************* 25 * 26 * The Original Code is the elliptic curve math library. 27 * 28 * The Initial Developer of the Original Code is 29 * Sun Microsystems, Inc. 30 * Portions created by the Initial Developer are Copyright (C) 2003 31 * the Initial Developer. All Rights Reserved. 32 * 33 * Contributor(s): 34 * Stephen Fung <fungstep@hotmail.com>, Sun Microsystems Laboratories 35 * 36 *********************************************************************** */ 37 38#include "ecl-priv.h" 39 40/* Returns 2^e as an integer. This is meant to be used for small powers of 41 * two. */ 42int 43ec_twoTo(int e) 44{ 45 int a = 1; 46 int i; 47 48 for (i = 0; i < e; i++) { 49 a *= 2; 50 } 51 return a; 52} 53 54/* Computes the windowed non-adjacent-form (NAF) of a scalar. Out should 55 * be an array of signed char's to output to, bitsize should be the number 56 * of bits of out, in is the original scalar, and w is the window size. 57 * NAF is discussed in the paper: D. Hankerson, J. Hernandez and A. 58 * Menezes, "Software implementation of elliptic curve cryptography over 59 * binary fields", Proc. CHES 2000. */ 60mp_err 61ec_compute_wNAF(signed char *out, int bitsize, const mp_int *in, int w) 62{ 63 mp_int k; 64 mp_err res = MP_OKAY; 65 int i, twowm1, mask; 66 67 twowm1 = ec_twoTo(w - 1); 68 mask = 2 * twowm1 - 1; 69 70 MP_DIGITS(&k) = 0; 71 MP_CHECKOK(mp_init_copy(&k, in)); 72 73 i = 0; 74 /* Compute wNAF form */ 75 while (mp_cmp_z(&k) > 0) { 76 if (mp_isodd(&k)) { 77 out[i] = MP_DIGIT(&k, 0) & mask; 78 if (out[i] >= twowm1) 79 out[i] -= 2 * twowm1; 80 81 /* Subtract off out[i]. Note mp_sub_d only works with 82 * unsigned digits */ 83 if (out[i] >= 0) { 84 mp_sub_d(&k, out[i], &k); 85 } else { 86 mp_add_d(&k, -(out[i]), &k); 87 } 88 } else { 89 out[i] = 0; 90 } 91 mp_div_2(&k, &k); 92 i++; 93 } 94 /* Zero out the remaining elements of the out array. */ 95 for (; i < bitsize + 1; i++) { 96 out[i] = 0; 97 } 98 CLEANUP: 99 mp_clear(&k); 100 return res; 101 102} 103