1 /* *********************************************************************

     2  *

     3  * Sun elects to have this file available under and governed by the

     4  * Mozilla Public License Version 1.1 ("MPL") (see

     5  * http://www.mozilla.org/MPL/ for full license text). For the avoidance

     6  * of doubt and subject to the following, Sun also elects to allow

     7  * licensees to use this file under the MPL, the GNU General Public

     8  * License version 2 only or the Lesser General Public License version

     9  * 2.1 only. Any references to the "GNU General Public License version 2

    10  * or later" or "GPL" in the following shall be construed to mean the

    11  * GNU General Public License version 2 only. Any references to the "GNU

    12  * Lesser General Public License version 2.1 or later" or "LGPL" in the

    13  * following shall be construed to mean the GNU Lesser General Public

    14  * License version 2.1 only. However, the following notice accompanied

    15  * the original version of this file:

    16  *

    17  * Version: MPL 1.1/GPL 2.0/LGPL 2.1

    18  *

    19  * The contents of this file are subject to the Mozilla Public License Version

    20  * 1.1 (the "License"); you may not use this file except in compliance with

    21  * the License. You may obtain a copy of the License at

    22  * http://www.mozilla.org/MPL/

    23  *

    24  * Software distributed under the License is distributed on an "AS IS" basis,

    25  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License

    26  * for the specific language governing rights and limitations under the

    27  * License.

    28  *

    29  * The Original Code is the elliptic curve math library.

    30  *

    31  * The Initial Developer of the Original Code is

    32  * Sun Microsystems, Inc.

    33  * Portions created by the Initial Developer are Copyright (C) 2003

    34  * the Initial Developer. All Rights Reserved.

    35  *

    36  * Contributor(s):

    37  *   Stephen Fung <fungstep@hotmail.com>, Sun Microsystems Laboratories

    38  *

    39  * Alternatively, the contents of this file may be used under the terms of

    40  * either the GNU General Public License Version 2 or later (the "GPL"), or

    41  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),

    42  * in which case the provisions of the GPL or the LGPL are applicable instead

    43  * of those above. If you wish to allow use of your version of this file only

    44  * under the terms of either the GPL or the LGPL, and not to allow others to

    45  * use your version of this file under the terms of the MPL, indicate your

    46  * decision by deleting the provisions above and replace them with the notice

    47  * and other provisions required by the GPL or the LGPL. If you do not delete

    48  * the provisions above, a recipient may use your version of this file under

    49  * the terms of any one of the MPL, the GPL or the LGPL.

    50  *

    51  *********************************************************************** */

    52 /*

    53  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.

    54  * Use is subject to license terms.

    55  */

    56 

    57 #pragma ident   "%Z%%M% %I%     %E% SMI"

    58 

    59 #include "ecl-priv.h"

    60 

    61 /* Returns 2^e as an integer. This is meant to be used for small powers of

    62  * two. */

    63 int

    64 ec_twoTo(int e)

    65 {

    66         int a = 1;

    67         int i;

    68 

    69         for (i = 0; i < e; i++) {

    70                 a *= 2;

    71         }

    72         return a;

    73 }

    74 

    75 /* Computes the windowed non-adjacent-form (NAF) of a scalar. Out should

    76  * be an array of signed char's to output to, bitsize should be the number

    77  * of bits of out, in is the original scalar, and w is the window size.

    78  * NAF is discussed in the paper: D. Hankerson, J. Hernandez and A.

    79  * Menezes, "Software implementation of elliptic curve cryptography over

    80  * binary fields", Proc. CHES 2000. */

    81 mp_err

    82 ec_compute_wNAF(signed char *out, int bitsize, const mp_int *in, int w)

    83 {

    84         mp_int k;

    85         mp_err res = MP_OKAY;

    86         int i, twowm1, mask;

    87 

    88         twowm1 = ec_twoTo(w - 1);

    89         mask = 2 * twowm1 - 1;

    90 

    91         MP_DIGITS(&k) = 0;

    92         MP_CHECKOK(mp_init_copy(&k, in));

    93 

    94         i = 0;

    95         /* Compute wNAF form */

    96         while (mp_cmp_z(&k) > 0) {

    97                 if (mp_isodd(&k)) {

    98                         out[i] = MP_DIGIT(&k, 0) & mask;

    99                         if (out[i] >= twowm1)

   100                                 out[i] -= 2 * twowm1;

   101 

   102                         /* Subtract off out[i].  Note mp_sub_d only works with

   103                          * unsigned digits */

   104                         if (out[i] >= 0) {

   105                                 mp_sub_d(&k, out[i], &k);

   106                         } else {

   107                                 mp_add_d(&k, -(out[i]), &k);

   108                         }

   109                 } else {

   110                         out[i] = 0;

   111                 }

   112                 mp_div_2(&k, &k);

   113                 i++;

   114         }

   115         /* Zero out the remaining elements of the out array. */

   116         for (; i < bitsize + 1; i++) {

   117                 out[i] = 0;

   118         }

   119   CLEANUP:

   120         mp_clear(&k);

   121         return res;

   122 

   123 }