/src/openssl/crypto/bn/bn_intern.c

Source
/*
 * Copyright 2014-2025 The OpenSSL Project Authors. All Rights Reserved.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

#include "internal/cryptlib.h"
#include "bn_local.h"
#include "internal/constant_time.h"

/*
 * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
 * This is an array  r[]  of values that are either zero or odd with an
 * absolute value less than  2^w  satisfying
 *     scalar = \sum_j r[j]*2^j
 * where at most one of any  w+1  consecutive digits is non-zero
 * with the exception that the most significant digit may be only
 * w-1 zeros away from that next non-zero digit.
 */
signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
{
    int window_val;
    signed char *r = NULL;
    int sign = 1;
    int bit, next_bit, mask;
    size_t len = 0, j;

    if (BN_is_zero(scalar)) {
        r = OPENSSL_malloc(1);
        if (r == NULL)
            goto err;
        r[0] = 0;
        *ret_len = 1;
        return r;
    }

    if (w <= 0 || w > 7) { /* 'signed char' can represent integers with
                            * absolute values less than 2^7 */
        ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
        goto err;
    }
    bit = 1 << w; /* at most 128 */
    next_bit = bit << 1; /* at most 256 */
    mask = next_bit - 1; /* at most 255 */

    if (BN_is_negative(scalar)) {
        sign = -1;
    }

    if (scalar->d == NULL || scalar->top == 0) {
        ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
        goto err;
    }

    len = BN_num_bits(scalar);
    r = OPENSSL_malloc(len + 1); /*
                                  * Modified wNAF may be one digit longer than binary representation
                                  * (*ret_len will be set to the actual length, i.e. at most
                                  * BN_num_bits(scalar) + 1)
                                  */
    if (r == NULL)
        goto err;
    window_val = scalar->d[0] & mask;
    j = 0;
    while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
                                                      * window_val will not
                                                      * increase */
        int digit = 0;

        /* 0 <= window_val <= 2^(w+1) */

        if (window_val & 1) {
            /* 0 < window_val < 2^(w+1) */

            if (window_val & bit) {
                digit = window_val - next_bit; /* -2^w < digit < 0 */

#if 1 /* modified wNAF */
                if (j + w + 1 >= len) {
                    /*
                     * Special case for generating modified wNAFs:
                     * no new bits will be added into window_val,
                     * so using a positive digit here will decrease
                     * the total length of the representation
                     */

                    digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
                }
#endif
            } else {
                digit = window_val; /* 0 < digit < 2^w */
            }

            if (digit <= -bit || digit >= bit || !(digit & 1)) {
                ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
                goto err;
            }

            window_val -= digit;

            /*
             * now window_val is 0 or 2^(w+1) in standard wNAF generation;
             * for modified window NAFs, it may also be 2^w
             */
            if (window_val != 0 && window_val != next_bit
                && window_val != bit) {
                ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
                goto err;
            }
        }

        r[j++] = sign * digit;

        window_val >>= 1;
        window_val += bit * BN_is_bit_set(scalar, (int)(j + w));

        if (window_val > next_bit) {
            ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
            goto err;
        }
    }

    if (j > len + 1) {
        ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
        goto err;
    }
    *ret_len = j;
    return r;

err:
    OPENSSL_free(r);
    return NULL;
}

int bn_get_top(const BIGNUM *a)
{
    return a->top;
}

int bn_get_dmax(const BIGNUM *a)
{
    return a->dmax;
}

void bn_set_all_zero(BIGNUM *a)
{
    int i;

    for (i = a->top; i < a->dmax; i++)
        a->d[i] = 0;
}

/*
 * Zero-extend |a| so that it occupies exactly |words| words, flag it
 * BN_FLG_FIXED_TOP and leave its numeric value unchanged.
 *
 * This is a companion to bn_correct_top(): where the latter minimises the top
 * of a BIGNUM, this one pins the top to a caller-chosen, value-independent
 * width.  Constant-time code uses it to make the cost of subsequent word-wise
 * operations (e.g. BN_uadd()/BN_add()) independent of the magnitude of a
 * secret value.  |words| must be greater than or equal to the current top.
 *
 * The routine is itself constant time with respect to the current a->top: it
 * always sweeps a fixed |words| iterations and selects value-or-zero per word
 * with an arithmetic mask, rather than looping over the (possibly secret)
 * a->top..words range.  Masking the high words with zero also launders any
 * uninitialised padding, so it is safe for the memory sanitiser.
 */
int bn_set_top_fixed(BIGNUM *a, int words)
{
    size_t i, n = (size_t)words;
    BN_ULONG mask;

    if (words < a->top)
        return 0;
    if (bn_wexpand(a, words) == NULL) {
        ERR_raise(ERR_LIB_BN, ERR_R_BN_LIB);
        return 0;
    }
    for (i = 0; i < n; i++) {
        /* mask = all ones iff i < a->top, else all zeros */
        mask = value_barrier_bn((BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)));
        a->d[i] &= mask;
    }
    a->top = words;
    a->flags |= BN_FLG_FIXED_TOP;
    return 1;
}

int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
{
    if (in->top > size)
        return 0;

    memset(out, 0, sizeof(*out) * size);
    if (in->d != NULL)
        memcpy(out, in->d, sizeof(*out) * in->top);
    return 1;
}

BN_ULONG *bn_get_words(const BIGNUM *a)
{
    return a->d;
}

void bn_set_static_words(BIGNUM *a, const BN_ULONG *words, int size)
{
    /*
     * |const| qualifier omission is compensated by BN_FLG_STATIC_DATA
     * flag, which effectively means "read-only data".
     */
    a->d = (BN_ULONG *)words;
    a->dmax = a->top = size;
    a->neg = 0;
    a->flags |= BN_FLG_STATIC_DATA;
    bn_correct_top(a);
}

int bn_set_words(BIGNUM *a, const BN_ULONG *words, int num_words)
{
    if (bn_wexpand(a, num_words) == NULL) {
        ERR_raise(ERR_LIB_BN, ERR_R_BN_LIB);
        return 0;
    }

    memcpy(a->d, words, sizeof(BN_ULONG) * num_words);
    a->top = num_words;
    bn_correct_top(a);
    return 1;
}

Coverage Report

Created: 2026-10-16 07:31

Line	Count	Source
1		/*
2		* Copyright 2014-2025 The OpenSSL Project Authors. All Rights Reserved.
3		*
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
8		*/
9
10		#include "internal/cryptlib.h"
11		#include "bn_local.h"
12		#include "internal/constant_time.h"
13
14		/*
15		* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
16		* This is an array r[] of values that are either zero or odd with an
17		* absolute value less than 2^w satisfying
18		* scalar = \sum_j r[j]*2^j
19		* where at most one of any w+1 consecutive digits is non-zero
20		* with the exception that the most significant digit may be only
21		* w-1 zeros away from that next non-zero digit.
22		*/
23		signed char bn_compute_wNAF(const BIGNUM scalar, int w, size_t *ret_len)
24	0	{
25	0	int window_val;
26	0	signed char *r = NULL;
27	0	int sign = 1;
28	0	int bit, next_bit, mask;
29	0	size_t len = 0, j;
30
31	0	if (BN_is_zero(scalar)) {
32	0	r = OPENSSL_malloc(1);
33	0	if (r == NULL)
34	0	goto err;
35	0	r[0] = 0;
36	0	*ret_len = 1;
37	0	return r;
38	0	}
39
40	0	if (w <= 0 \|\| w > 7) { /* 'signed char' can represent integers with
41		* absolute values less than 2^7 */
42	0	ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
43	0	goto err;
44	0	}
45	0	bit = 1 << w; /* at most 128 */
46	0	next_bit = bit << 1; /* at most 256 */
47	0	mask = next_bit - 1; /* at most 255 */
48
49	0	if (BN_is_negative(scalar)) {
50	0	sign = -1;
51	0	}
52
53	0	if (scalar->d == NULL \|\| scalar->top == 0) {
54	0	ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
55	0	goto err;
56	0	}
57
58	0	len = BN_num_bits(scalar);
59	0	r = OPENSSL_malloc(len + 1); /*
60		* Modified wNAF may be one digit longer than binary representation
61		* (*ret_len will be set to the actual length, i.e. at most
62		* BN_num_bits(scalar) + 1)
63		*/
64	0	if (r == NULL)
65	0	goto err;
66	0	window_val = scalar->d[0] & mask;
67	0	j = 0;
68	0	while ((window_val != 0) \|\| (j + w + 1 < len)) { /* if j+w+1 >= len,
69		* window_val will not
70		* increase */
71	0	int digit = 0;
72
73		/* 0 <= window_val <= 2^(w+1) */
74
75	0	if (window_val & 1) {
76		/* 0 < window_val < 2^(w+1) */
77
78	0	if (window_val & bit) {
79	0	digit = window_val - next_bit; /* -2^w < digit < 0 */
80
81	0	#if 1 /* modified wNAF */
82	0	if (j + w + 1 >= len) {
83		/*
84		* Special case for generating modified wNAFs:
85		* no new bits will be added into window_val,
86		* so using a positive digit here will decrease
87		* the total length of the representation
88		*/
89
90	0	digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
91	0	}
92	0	#endif
93	0	} else {
94	0	digit = window_val; /* 0 < digit < 2^w */
95	0	}
96
97	0	if (digit <= -bit \|\| digit >= bit \|\| !(digit & 1)) {
98	0	ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
99	0	goto err;
100	0	}
101
102	0	window_val -= digit;
103
104		/*
105		* now window_val is 0 or 2^(w+1) in standard wNAF generation;
106		* for modified window NAFs, it may also be 2^w
107		*/
108	0	if (window_val != 0 && window_val != next_bit
109	0	&& window_val != bit) {
110	0	ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
111	0	goto err;
112	0	}
113	0	}
114
115	0	r[j++] = sign * digit;
116
117	0	window_val >>= 1;
118	0	window_val += bit * BN_is_bit_set(scalar, (int)(j + w));
119
120	0	if (window_val > next_bit) {
121	0	ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
122	0	goto err;
123	0	}
124	0	}
125
126	0	if (j > len + 1) {
127	0	ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
128	0	goto err;
129	0	}
130	0	*ret_len = j;
131	0	return r;
132
133	0	err:
134	0	OPENSSL_free(r);
135	0	return NULL;
136	0	}
137
138		int bn_get_top(const BIGNUM *a)
139	0	{
140	0	return a->top;
141	0	}
142
143		int bn_get_dmax(const BIGNUM *a)
144	0	{
145	0	return a->dmax;
146	0	}
147
148		void bn_set_all_zero(BIGNUM *a)
149	0	{
150	0	int i;
151
152	0	for (i = a->top; i < a->dmax; i++)
153	0	a->d[i] = 0;
154	0	}
155
156		/*
157		* Zero-extend \|a\| so that it occupies exactly \|words\| words, flag it
158		* BN_FLG_FIXED_TOP and leave its numeric value unchanged.
159		*
160		* This is a companion to bn_correct_top(): where the latter minimises the top
161		* of a BIGNUM, this one pins the top to a caller-chosen, value-independent
162		* width. Constant-time code uses it to make the cost of subsequent word-wise
163		* operations (e.g. BN_uadd()/BN_add()) independent of the magnitude of a
164		* secret value. \|words\| must be greater than or equal to the current top.
165		*
166		* The routine is itself constant time with respect to the current a->top: it
167		* always sweeps a fixed \|words\| iterations and selects value-or-zero per word
168		* with an arithmetic mask, rather than looping over the (possibly secret)
169		* a->top..words range. Masking the high words with zero also launders any
170		* uninitialised padding, so it is safe for the memory sanitiser.
171		*/
172		int bn_set_top_fixed(BIGNUM *a, int words)
173	0	{
174	0	size_t i, n = (size_t)words;
175	0	BN_ULONG mask;
176
177	0	if (words < a->top)
178	0	return 0;
179	0	if (bn_wexpand(a, words) == NULL) {
180	0	ERR_raise(ERR_LIB_BN, ERR_R_BN_LIB);
181	0	return 0;
182	0	}
183	0	for (i = 0; i < n; i++) {
184		/* mask = all ones iff i < a->top, else all zeros */
185	0	mask = value_barrier_bn((BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)));
186	0	a->d[i] &= mask;
187	0	}
188	0	a->top = words;
189	0	a->flags \|= BN_FLG_FIXED_TOP;
190	0	return 1;
191	0	}
192
193		int bn_copy_words(BN_ULONG out, const BIGNUM in, int size)
194	0	{
195	0	if (in->top > size)
196	0	return 0;
197
198	0	memset(out, 0, sizeof(out) size);
199	0	if (in->d != NULL)
200	0	memcpy(out, in->d, sizeof(out) in->top);
201	0	return 1;
202	0	}
203
204		BN_ULONG bn_get_words(const BIGNUM a)
205	0	{
206	0	return a->d;
207	0	}
208
209		void bn_set_static_words(BIGNUM a, const BN_ULONG words, int size)
210	0	{
211		/*
212		* \|const\| qualifier omission is compensated by BN_FLG_STATIC_DATA
213		* flag, which effectively means "read-only data".
214		*/
215	0	a->d = (BN_ULONG *)words;
216	0	a->dmax = a->top = size;
217	0	a->neg = 0;
218	0	a->flags \|= BN_FLG_STATIC_DATA;
219	0	bn_correct_top(a);
220	0	}
221
222		int bn_set_words(BIGNUM a, const BN_ULONG words, int num_words)
223	0	{
224	0	if (bn_wexpand(a, num_words) == NULL) {
225	0	ERR_raise(ERR_LIB_BN, ERR_R_BN_LIB);
226	0	return 0;
227	0	}
228
229	0	memcpy(a->d, words, sizeof(BN_ULONG) * num_words);
230	0	a->top = num_words;
231	0	bn_correct_top(a);
232	0	return 1;
233	0	}