security/nss/lib/freebl/ecl/ec_naf.c@b8a032363ba2 (annotated)
security/nss/lib/freebl/ecl/ec_naf.c
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
| michael@0 | 1 | /* This Source Code Form is subject to the terms of the Mozilla Public |
| michael@0 | 2 | * License, v. 2.0. If a copy of the MPL was not distributed with this |
| michael@0 | 3 | * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
| michael@0 | 4 | |
| michael@0 | 5 | #include "ecl-priv.h" |
| michael@0 | 6 | |
| michael@0 | 7 | /* Returns 2^e as an integer. This is meant to be used for small powers of |
| michael@0 | 8 | * two. */ |
| michael@0 | 9 | int |
| michael@0 | 10 | ec_twoTo(int e) |
| michael@0 | 11 | { |
| michael@0 | 12 | int a = 1; |
| michael@0 | 13 | int i; |
| michael@0 | 14 | |
| michael@0 | 15 | for (i = 0; i < e; i++) { |
| michael@0 | 16 | a *= 2; |
| michael@0 | 17 | } |
| michael@0 | 18 | return a; |
| michael@0 | 19 | } |
| michael@0 | 20 | |
| michael@0 | 21 | /* Computes the windowed non-adjacent-form (NAF) of a scalar. Out should |
| michael@0 | 22 | * be an array of signed char's to output to, bitsize should be the number |
| michael@0 | 23 | * of bits of out, in is the original scalar, and w is the window size. |
| michael@0 | 24 | * NAF is discussed in the paper: D. Hankerson, J. Hernandez and A. |
| michael@0 | 25 | * Menezes, "Software implementation of elliptic curve cryptography over |
| michael@0 | 26 | * binary fields", Proc. CHES 2000. */ |
| michael@0 | 27 | mp_err |
| michael@0 | 28 | ec_compute_wNAF(signed char *out, int bitsize, const mp_int *in, int w) |
| michael@0 | 29 | { |
| michael@0 | 30 | mp_int k; |
| michael@0 | 31 | mp_err res = MP_OKAY; |
| michael@0 | 32 | int i, twowm1, mask; |
| michael@0 | 33 | |
| michael@0 | 34 | twowm1 = ec_twoTo(w - 1); |
| michael@0 | 35 | mask = 2 * twowm1 - 1; |
| michael@0 | 36 | |
| michael@0 | 37 | MP_DIGITS(&k) = 0; |
| michael@0 | 38 | MP_CHECKOK(mp_init_copy(&k, in)); |
| michael@0 | 39 | |
| michael@0 | 40 | i = 0; |
| michael@0 | 41 | /* Compute wNAF form */ |
| michael@0 | 42 | while (mp_cmp_z(&k) > 0) { |
| michael@0 | 43 | if (mp_isodd(&k)) { |
| michael@0 | 44 | out[i] = MP_DIGIT(&k, 0) & mask; |
| michael@0 | 45 | if (out[i] >= twowm1) |
| michael@0 | 46 | out[i] -= 2 * twowm1; |
| michael@0 | 47 | |
| michael@0 | 48 | /* Subtract off out[i]. Note mp_sub_d only works with |
| michael@0 | 49 | * unsigned digits */ |
| michael@0 | 50 | if (out[i] >= 0) { |
| michael@0 | 51 | mp_sub_d(&k, out[i], &k); |
| michael@0 | 52 | } else { |
| michael@0 | 53 | mp_add_d(&k, -(out[i]), &k); |
| michael@0 | 54 | } |
| michael@0 | 55 | } else { |
| michael@0 | 56 | out[i] = 0; |
| michael@0 | 57 | } |
| michael@0 | 58 | mp_div_2(&k, &k); |
| michael@0 | 59 | i++; |
| michael@0 | 60 | } |
| michael@0 | 61 | /* Zero out the remaining elements of the out array. */ |
| michael@0 | 62 | for (; i < bitsize + 1; i++) { |
| michael@0 | 63 | out[i] = 0; |
| michael@0 | 64 | } |
| michael@0 | 65 | CLEANUP: |
| michael@0 | 66 | mp_clear(&k); |
| michael@0 | 67 | return res; |
| michael@0 | 68 | |
| michael@0 | 69 | } |
