]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/bn/bn_intern.c
2 * Copyright 2014-2018 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
10 #include "internal/cryptlib.h"
14 * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
15 * This is an array r[] of values that are either zero or odd with an
16 * absolute value less than 2^w satisfying
17 * scalar = \sum_j r[j]*2^j
18 * where at most one of any w+1 consecutive digits is non-zero
19 * with the exception that the most significant digit may be only
20 * w-1 zeros away from that next non-zero digit.
22 signed char *bn_compute_wNAF(const BIGNUM
*scalar
, int w
, size_t *ret_len
)
25 signed char *r
= NULL
;
27 int bit
, next_bit
, mask
;
30 if (BN_is_zero(scalar
)) {
31 r
= OPENSSL_malloc(1);
33 BNerr(BN_F_BN_COMPUTE_WNAF
, ERR_R_MALLOC_FAILURE
);
41 if (w
<= 0 || w
> 7) { /* 'signed char' can represent integers with
42 * absolute values less than 2^7 */
43 BNerr(BN_F_BN_COMPUTE_WNAF
, ERR_R_INTERNAL_ERROR
);
46 bit
= 1 << w
; /* at most 128 */
47 next_bit
= bit
<< 1; /* at most 256 */
48 mask
= next_bit
- 1; /* at most 255 */
50 if (BN_is_negative(scalar
)) {
54 if (scalar
->d
== NULL
|| scalar
->top
== 0) {
55 BNerr(BN_F_BN_COMPUTE_WNAF
, ERR_R_INTERNAL_ERROR
);
59 len
= BN_num_bits(scalar
);
60 r
= OPENSSL_malloc(len
+ 1); /*
61 * Modified wNAF may be one digit longer than binary representation
62 * (*ret_len will be set to the actual length, i.e. at most
63 * BN_num_bits(scalar) + 1)
66 BNerr(BN_F_BN_COMPUTE_WNAF
, ERR_R_MALLOC_FAILURE
);
69 window_val
= scalar
->d
[0] & mask
;
71 while ((window_val
!= 0) || (j
+ w
+ 1 < len
)) { /* if j+w+1 >= len,
76 /* 0 <= window_val <= 2^(w+1) */
79 /* 0 < window_val < 2^(w+1) */
81 if (window_val
& bit
) {
82 digit
= window_val
- next_bit
; /* -2^w < digit < 0 */
84 #if 1 /* modified wNAF */
85 if (j
+ w
+ 1 >= len
) {
87 * Special case for generating modified wNAFs:
88 * no new bits will be added into window_val,
89 * so using a positive digit here will decrease
90 * the total length of the representation
93 digit
= window_val
& (mask
>> 1); /* 0 < digit < 2^w */
97 digit
= window_val
; /* 0 < digit < 2^w */
100 if (digit
<= -bit
|| digit
>= bit
|| !(digit
& 1)) {
101 BNerr(BN_F_BN_COMPUTE_WNAF
, ERR_R_INTERNAL_ERROR
);
108 * now window_val is 0 or 2^(w+1) in standard wNAF generation;
109 * for modified window NAFs, it may also be 2^w
111 if (window_val
!= 0 && window_val
!= next_bit
112 && window_val
!= bit
) {
113 BNerr(BN_F_BN_COMPUTE_WNAF
, ERR_R_INTERNAL_ERROR
);
118 r
[j
++] = sign
* digit
;
121 window_val
+= bit
* BN_is_bit_set(scalar
, j
+ w
);
123 if (window_val
> next_bit
) {
124 BNerr(BN_F_BN_COMPUTE_WNAF
, ERR_R_INTERNAL_ERROR
);
130 BNerr(BN_F_BN_COMPUTE_WNAF
, ERR_R_INTERNAL_ERROR
);
141 int bn_get_top(const BIGNUM
*a
)
146 int bn_get_dmax(const BIGNUM
*a
)
151 void bn_set_all_zero(BIGNUM
*a
)
155 for (i
= a
->top
; i
< a
->dmax
; i
++)
159 int bn_copy_words(BN_ULONG
*out
, const BIGNUM
*in
, int size
)
164 memset(out
, 0, sizeof(*out
) * size
);
166 memcpy(out
, in
->d
, sizeof(*out
) * in
->top
);
170 BN_ULONG
*bn_get_words(const BIGNUM
*a
)
175 void bn_set_static_words(BIGNUM
*a
, const BN_ULONG
*words
, int size
)
178 * |const| qualifier omission is compensated by BN_FLG_STATIC_DATA
179 * flag, which effectively means "read-only data".
181 a
->d
= (BN_ULONG
*)words
;
182 a
->dmax
= a
->top
= size
;
184 a
->flags
|= BN_FLG_STATIC_DATA
;
188 int bn_set_words(BIGNUM
*a
, const BN_ULONG
*words
, int num_words
)
190 if (bn_wexpand(a
, num_words
) == NULL
) {
191 BNerr(BN_F_BN_SET_WORDS
, ERR_R_MALLOC_FAILURE
);
195 memcpy(a
->d
, words
, sizeof(BN_ULONG
) * num_words
);