1*1dcdf01fSchristos /*
2*1dcdf01fSchristos * Copyright 2014-2018 The OpenSSL Project Authors. All Rights Reserved.
3*1dcdf01fSchristos *
4*1dcdf01fSchristos * Licensed under the OpenSSL license (the "License"). You may not use
5*1dcdf01fSchristos * this file except in compliance with the License. You can obtain a copy
6*1dcdf01fSchristos * in the file LICENSE in the source distribution or at
7*1dcdf01fSchristos * https://www.openssl.org/source/license.html
8*1dcdf01fSchristos */
9*1dcdf01fSchristos
10*1dcdf01fSchristos #include "internal/cryptlib.h"
11*1dcdf01fSchristos #include "bn_local.h"
12*1dcdf01fSchristos
13*1dcdf01fSchristos /*
14*1dcdf01fSchristos * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
15*1dcdf01fSchristos * This is an array r[] of values that are either zero or odd with an
16*1dcdf01fSchristos * absolute value less than 2^w satisfying
17*1dcdf01fSchristos * scalar = \sum_j r[j]*2^j
18*1dcdf01fSchristos * where at most one of any w+1 consecutive digits is non-zero
19*1dcdf01fSchristos * with the exception that the most significant digit may be only
20*1dcdf01fSchristos * w-1 zeros away from that next non-zero digit.
21*1dcdf01fSchristos */
bn_compute_wNAF(const BIGNUM * scalar,int w,size_t * ret_len)22*1dcdf01fSchristos signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
23*1dcdf01fSchristos {
24*1dcdf01fSchristos int window_val;
25*1dcdf01fSchristos signed char *r = NULL;
26*1dcdf01fSchristos int sign = 1;
27*1dcdf01fSchristos int bit, next_bit, mask;
28*1dcdf01fSchristos size_t len = 0, j;
29*1dcdf01fSchristos
30*1dcdf01fSchristos if (BN_is_zero(scalar)) {
31*1dcdf01fSchristos r = OPENSSL_malloc(1);
32*1dcdf01fSchristos if (r == NULL) {
33*1dcdf01fSchristos BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
34*1dcdf01fSchristos goto err;
35*1dcdf01fSchristos }
36*1dcdf01fSchristos r[0] = 0;
37*1dcdf01fSchristos *ret_len = 1;
38*1dcdf01fSchristos return r;
39*1dcdf01fSchristos }
40*1dcdf01fSchristos
41*1dcdf01fSchristos if (w <= 0 || w > 7) { /* 'signed char' can represent integers with
42*1dcdf01fSchristos * absolute values less than 2^7 */
43*1dcdf01fSchristos BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
44*1dcdf01fSchristos goto err;
45*1dcdf01fSchristos }
46*1dcdf01fSchristos bit = 1 << w; /* at most 128 */
47*1dcdf01fSchristos next_bit = bit << 1; /* at most 256 */
48*1dcdf01fSchristos mask = next_bit - 1; /* at most 255 */
49*1dcdf01fSchristos
50*1dcdf01fSchristos if (BN_is_negative(scalar)) {
51*1dcdf01fSchristos sign = -1;
52*1dcdf01fSchristos }
53*1dcdf01fSchristos
54*1dcdf01fSchristos if (scalar->d == NULL || scalar->top == 0) {
55*1dcdf01fSchristos BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
56*1dcdf01fSchristos goto err;
57*1dcdf01fSchristos }
58*1dcdf01fSchristos
59*1dcdf01fSchristos len = BN_num_bits(scalar);
60*1dcdf01fSchristos r = OPENSSL_malloc(len + 1); /*
61*1dcdf01fSchristos * Modified wNAF may be one digit longer than binary representation
62*1dcdf01fSchristos * (*ret_len will be set to the actual length, i.e. at most
63*1dcdf01fSchristos * BN_num_bits(scalar) + 1)
64*1dcdf01fSchristos */
65*1dcdf01fSchristos if (r == NULL) {
66*1dcdf01fSchristos BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
67*1dcdf01fSchristos goto err;
68*1dcdf01fSchristos }
69*1dcdf01fSchristos window_val = scalar->d[0] & mask;
70*1dcdf01fSchristos j = 0;
71*1dcdf01fSchristos while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
72*1dcdf01fSchristos * window_val will not
73*1dcdf01fSchristos * increase */
74*1dcdf01fSchristos int digit = 0;
75*1dcdf01fSchristos
76*1dcdf01fSchristos /* 0 <= window_val <= 2^(w+1) */
77*1dcdf01fSchristos
78*1dcdf01fSchristos if (window_val & 1) {
79*1dcdf01fSchristos /* 0 < window_val < 2^(w+1) */
80*1dcdf01fSchristos
81*1dcdf01fSchristos if (window_val & bit) {
82*1dcdf01fSchristos digit = window_val - next_bit; /* -2^w < digit < 0 */
83*1dcdf01fSchristos
84*1dcdf01fSchristos #if 1 /* modified wNAF */
85*1dcdf01fSchristos if (j + w + 1 >= len) {
86*1dcdf01fSchristos /*
87*1dcdf01fSchristos * Special case for generating modified wNAFs:
88*1dcdf01fSchristos * no new bits will be added into window_val,
89*1dcdf01fSchristos * so using a positive digit here will decrease
90*1dcdf01fSchristos * the total length of the representation
91*1dcdf01fSchristos */
92*1dcdf01fSchristos
93*1dcdf01fSchristos digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
94*1dcdf01fSchristos }
95*1dcdf01fSchristos #endif
96*1dcdf01fSchristos } else {
97*1dcdf01fSchristos digit = window_val; /* 0 < digit < 2^w */
98*1dcdf01fSchristos }
99*1dcdf01fSchristos
100*1dcdf01fSchristos if (digit <= -bit || digit >= bit || !(digit & 1)) {
101*1dcdf01fSchristos BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
102*1dcdf01fSchristos goto err;
103*1dcdf01fSchristos }
104*1dcdf01fSchristos
105*1dcdf01fSchristos window_val -= digit;
106*1dcdf01fSchristos
107*1dcdf01fSchristos /*
108*1dcdf01fSchristos * now window_val is 0 or 2^(w+1) in standard wNAF generation;
109*1dcdf01fSchristos * for modified window NAFs, it may also be 2^w
110*1dcdf01fSchristos */
111*1dcdf01fSchristos if (window_val != 0 && window_val != next_bit
112*1dcdf01fSchristos && window_val != bit) {
113*1dcdf01fSchristos BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
114*1dcdf01fSchristos goto err;
115*1dcdf01fSchristos }
116*1dcdf01fSchristos }
117*1dcdf01fSchristos
118*1dcdf01fSchristos r[j++] = sign * digit;
119*1dcdf01fSchristos
120*1dcdf01fSchristos window_val >>= 1;
121*1dcdf01fSchristos window_val += bit * BN_is_bit_set(scalar, j + w);
122*1dcdf01fSchristos
123*1dcdf01fSchristos if (window_val > next_bit) {
124*1dcdf01fSchristos BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
125*1dcdf01fSchristos goto err;
126*1dcdf01fSchristos }
127*1dcdf01fSchristos }
128*1dcdf01fSchristos
129*1dcdf01fSchristos if (j > len + 1) {
130*1dcdf01fSchristos BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
131*1dcdf01fSchristos goto err;
132*1dcdf01fSchristos }
133*1dcdf01fSchristos *ret_len = j;
134*1dcdf01fSchristos return r;
135*1dcdf01fSchristos
136*1dcdf01fSchristos err:
137*1dcdf01fSchristos OPENSSL_free(r);
138*1dcdf01fSchristos return NULL;
139*1dcdf01fSchristos }
140*1dcdf01fSchristos
bn_get_top(const BIGNUM * a)141*1dcdf01fSchristos int bn_get_top(const BIGNUM *a)
142*1dcdf01fSchristos {
143*1dcdf01fSchristos return a->top;
144*1dcdf01fSchristos }
145*1dcdf01fSchristos
bn_get_dmax(const BIGNUM * a)146*1dcdf01fSchristos int bn_get_dmax(const BIGNUM *a)
147*1dcdf01fSchristos {
148*1dcdf01fSchristos return a->dmax;
149*1dcdf01fSchristos }
150*1dcdf01fSchristos
bn_set_all_zero(BIGNUM * a)151*1dcdf01fSchristos void bn_set_all_zero(BIGNUM *a)
152*1dcdf01fSchristos {
153*1dcdf01fSchristos int i;
154*1dcdf01fSchristos
155*1dcdf01fSchristos for (i = a->top; i < a->dmax; i++)
156*1dcdf01fSchristos a->d[i] = 0;
157*1dcdf01fSchristos }
158*1dcdf01fSchristos
bn_copy_words(BN_ULONG * out,const BIGNUM * in,int size)159*1dcdf01fSchristos int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
160*1dcdf01fSchristos {
161*1dcdf01fSchristos if (in->top > size)
162*1dcdf01fSchristos return 0;
163*1dcdf01fSchristos
164*1dcdf01fSchristos memset(out, 0, sizeof(*out) * size);
165*1dcdf01fSchristos if (in->d != NULL)
166*1dcdf01fSchristos memcpy(out, in->d, sizeof(*out) * in->top);
167*1dcdf01fSchristos return 1;
168*1dcdf01fSchristos }
169*1dcdf01fSchristos
bn_get_words(const BIGNUM * a)170*1dcdf01fSchristos BN_ULONG *bn_get_words(const BIGNUM *a)
171*1dcdf01fSchristos {
172*1dcdf01fSchristos return a->d;
173*1dcdf01fSchristos }
174*1dcdf01fSchristos
bn_set_static_words(BIGNUM * a,const BN_ULONG * words,int size)175*1dcdf01fSchristos void bn_set_static_words(BIGNUM *a, const BN_ULONG *words, int size)
176*1dcdf01fSchristos {
177*1dcdf01fSchristos /*
178*1dcdf01fSchristos * |const| qualifier omission is compensated by BN_FLG_STATIC_DATA
179*1dcdf01fSchristos * flag, which effectively means "read-only data".
180*1dcdf01fSchristos */
181*1dcdf01fSchristos a->d = (BN_ULONG *)words;
182*1dcdf01fSchristos a->dmax = a->top = size;
183*1dcdf01fSchristos a->neg = 0;
184*1dcdf01fSchristos a->flags |= BN_FLG_STATIC_DATA;
185*1dcdf01fSchristos bn_correct_top(a);
186*1dcdf01fSchristos }
187*1dcdf01fSchristos
bn_set_words(BIGNUM * a,const BN_ULONG * words,int num_words)188*1dcdf01fSchristos int bn_set_words(BIGNUM *a, const BN_ULONG *words, int num_words)
189*1dcdf01fSchristos {
190*1dcdf01fSchristos if (bn_wexpand(a, num_words) == NULL) {
191*1dcdf01fSchristos BNerr(BN_F_BN_SET_WORDS, ERR_R_MALLOC_FAILURE);
192*1dcdf01fSchristos return 0;
193*1dcdf01fSchristos }
194*1dcdf01fSchristos
195*1dcdf01fSchristos memcpy(a->d, words, sizeof(BN_ULONG) * num_words);
196*1dcdf01fSchristos a->top = num_words;
197*1dcdf01fSchristos bn_correct_top(a);
198*1dcdf01fSchristos return 1;
199*1dcdf01fSchristos }
200