• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1/*
2 * Copyright 2001-2016 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved.
4 *
5 * Licensed under the OpenSSL license (the "License").  You may not use
6 * this file except in compliance with the License.  You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
9 */
10
11#include <openssl/ec.h>
12
13#include <assert.h>
14#include <string.h>
15
16#include <openssl/bn.h>
17#include <openssl/err.h>
18#include <openssl/mem.h>
19#include <openssl/thread.h>
20
21#include "../../internal.h"
22#include "../bn/internal.h"
23#include "internal.h"
24
25
26// This file implements the wNAF-based interleaving multi-exponentiation method
27// at:
28//   http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13
29//   http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf
30
31void ec_compute_wNAF(const EC_GROUP *group, int8_t *out,
32                     const EC_SCALAR *scalar, size_t bits, int w) {
33  // 'int8_t' can represent integers with absolute values less than 2^7.
34  assert(0 < w && w <= 7);
35  assert(bits != 0);
36  int bit = 1 << w;         // 2^w, at most 128
37  int next_bit = bit << 1;  // 2^(w+1), at most 256
38  int mask = next_bit - 1;  // at most 255
39
40  int window_val = scalar->words[0] & mask;
41  for (size_t j = 0; j < bits + 1; j++) {
42    assert(0 <= window_val && window_val <= next_bit);
43    int digit = 0;
44    if (window_val & 1) {
45      assert(0 < window_val && window_val < next_bit);
46      if (window_val & bit) {
47        digit = window_val - next_bit;
48        // We know -next_bit < digit < 0 and window_val - digit = next_bit.
49
50        // modified wNAF
51        if (j + w + 1 >= bits) {
52          // special case for generating modified wNAFs:
53          // no new bits will be added into window_val,
54          // so using a positive digit here will decrease
55          // the total length of the representation
56
57          digit = window_val & (mask >> 1);
58          // We know 0 < digit < bit and window_val - digit = bit.
59        }
60      } else {
61        digit = window_val;
62        // We know 0 < digit < bit and window_val - digit = 0.
63      }
64
65      window_val -= digit;
66
67      // Now window_val is 0 or 2^(w+1) in standard wNAF generation.
68      // For modified window NAFs, it may also be 2^w.
69      //
70      // See the comments above for the derivation of each of these bounds.
71      assert(window_val == 0 || window_val == next_bit || window_val == bit);
72      assert(-bit < digit && digit < bit);
73
74      // window_val was odd, so digit is also odd.
75      assert(digit & 1);
76    }
77
78    out[j] = digit;
79
80    // Incorporate the next bit. Previously, |window_val| <= |next_bit|, so if
81    // we shift and add at most one copy of |bit|, this will continue to hold
82    // afterwards.
83    window_val >>= 1;
84    window_val += bit * bn_is_bit_set_words(scalar->words, group->order.N.width,
85                                            j + w + 1);
86    assert(window_val <= next_bit);
87  }
88
89  // bits + 1 entries should be sufficient to consume all bits.
90  assert(window_val == 0);
91}
92
93// compute_precomp sets |out[i]| to (2*i+1)*p, for i from 0 to |len|.
94static void compute_precomp(const EC_GROUP *group, EC_JACOBIAN *out,
95                            const EC_JACOBIAN *p, size_t len) {
96  ec_GFp_simple_point_copy(&out[0], p);
97  EC_JACOBIAN two_p;
98  ec_GFp_mont_dbl(group, &two_p, p);
99  for (size_t i = 1; i < len; i++) {
100    ec_GFp_mont_add(group, &out[i], &out[i - 1], &two_p);
101  }
102}
103
104static void lookup_precomp(const EC_GROUP *group, EC_JACOBIAN *out,
105                           const EC_JACOBIAN *precomp, int digit) {
106  if (digit < 0) {
107    digit = -digit;
108    ec_GFp_simple_point_copy(out, &precomp[digit >> 1]);
109    ec_GFp_simple_invert(group, out);
110  } else {
111    ec_GFp_simple_point_copy(out, &precomp[digit >> 1]);
112  }
113}
114
115// EC_WNAF_WINDOW_BITS is the window size to use for |ec_GFp_mont_mul_public|.
116#define EC_WNAF_WINDOW_BITS 4
117
118// EC_WNAF_TABLE_SIZE is the table size to use for |ec_GFp_mont_mul_public|.
119#define EC_WNAF_TABLE_SIZE (1 << (EC_WNAF_WINDOW_BITS - 1))
120
121// EC_WNAF_STACK is the number of points worth of data to stack-allocate and
122// avoid a malloc.
123#define EC_WNAF_STACK 3
124
125int ec_GFp_mont_mul_public_batch(const EC_GROUP *group, EC_JACOBIAN *r,
126                                 const EC_SCALAR *g_scalar,
127                                 const EC_JACOBIAN *points,
128                                 const EC_SCALAR *scalars, size_t num) {
129  size_t bits = EC_GROUP_order_bits(group);
130  size_t wNAF_len = bits + 1;
131
132  // Stack-allocated space, which will be used if the task is small enough.
133  int8_t wNAF_stack[EC_WNAF_STACK][EC_MAX_BYTES * 8 + 1];
134  EC_JACOBIAN precomp_stack[EC_WNAF_STACK][EC_WNAF_TABLE_SIZE];
135
136  // Allocated pointers, which will remain NULL unless needed.
137  EC_JACOBIAN(*precomp_alloc)[EC_WNAF_TABLE_SIZE] = NULL;
138  int8_t(*wNAF_alloc)[EC_MAX_BYTES * 8 + 1] = NULL;
139
140  // These fields point either to the stack or heap buffers of the same name.
141  int8_t(*wNAF)[EC_MAX_BYTES * 8 + 1];
142  EC_JACOBIAN(*precomp)[EC_WNAF_TABLE_SIZE];
143
144  if (num <= EC_WNAF_STACK) {
145    wNAF = wNAF_stack;
146    precomp = precomp_stack;
147  } else {
148    wNAF_alloc = reinterpret_cast<decltype(wNAF_alloc)>(
149        OPENSSL_calloc(num, sizeof(wNAF_alloc[0])));
150    if (wNAF_alloc == NULL) {
151      return 0;
152    }
153    precomp_alloc = reinterpret_cast<decltype(precomp_alloc)>(
154        OPENSSL_calloc(num, sizeof(precomp_alloc[0])));
155    if (precomp_alloc == NULL) {
156      OPENSSL_free(wNAF_alloc);
157      return 0;
158    }
159
160    wNAF = wNAF_alloc;
161    precomp = precomp_alloc;
162  }
163
164  int8_t g_wNAF[EC_MAX_BYTES * 8 + 1];
165  EC_JACOBIAN g_precomp[EC_WNAF_TABLE_SIZE];
166  assert(wNAF_len <= OPENSSL_ARRAY_SIZE(g_wNAF));
167  const EC_JACOBIAN *g = &group->generator.raw;
168  if (g_scalar != NULL) {
169    ec_compute_wNAF(group, g_wNAF, g_scalar, bits, EC_WNAF_WINDOW_BITS);
170    compute_precomp(group, g_precomp, g, EC_WNAF_TABLE_SIZE);
171  }
172
173  for (size_t i = 0; i < num; i++) {
174    assert(wNAF_len <= OPENSSL_ARRAY_SIZE(wNAF[i]));
175    ec_compute_wNAF(group, wNAF[i], &scalars[i], bits, EC_WNAF_WINDOW_BITS);
176    compute_precomp(group, precomp[i], &points[i], EC_WNAF_TABLE_SIZE);
177  }
178
179  EC_JACOBIAN tmp;
180  int r_is_at_infinity = 1;
181  for (size_t k = wNAF_len - 1; k < wNAF_len; k--) {
182    if (!r_is_at_infinity) {
183      ec_GFp_mont_dbl(group, r, r);
184    }
185
186    if (g_scalar != NULL && g_wNAF[k] != 0) {
187      lookup_precomp(group, &tmp, g_precomp, g_wNAF[k]);
188      if (r_is_at_infinity) {
189        ec_GFp_simple_point_copy(r, &tmp);
190        r_is_at_infinity = 0;
191      } else {
192        ec_GFp_mont_add(group, r, r, &tmp);
193      }
194    }
195
196    for (size_t i = 0; i < num; i++) {
197      if (wNAF[i][k] != 0) {
198        lookup_precomp(group, &tmp, precomp[i], wNAF[i][k]);
199        if (r_is_at_infinity) {
200          ec_GFp_simple_point_copy(r, &tmp);
201          r_is_at_infinity = 0;
202        } else {
203          ec_GFp_mont_add(group, r, r, &tmp);
204        }
205      }
206    }
207  }
208
209  if (r_is_at_infinity) {
210    ec_GFp_simple_point_set_to_infinity(group, r);
211  }
212
213  OPENSSL_free(wNAF_alloc);
214  OPENSSL_free(precomp_alloc);
215  return 1;
216}
217