bn_internal(3) OpenSSL bn_internal(3) NNAAMMEE bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words, bn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8, bn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal, bn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive, bn_mul_low_recursive, bn_mul_high, bn_sqr_normal, bn_sqr_recursive, bn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top, bn_print, bn_dump, bn_set_max, bn_set_high, bn_set_low - BIGNUM library internal functions SSYYNNOOPPSSIISS #include BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w); BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w); void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num); BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d); BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp, int num); BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp, int num); void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a); void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a); int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n); void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb); void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n); void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, int dna,int dnb,BN_ULONG *tmp); void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, int tna,int tnb, BN_ULONG *tmp); void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, BN_ULONG *tmp); void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, BN_ULONG *tmp); void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp); void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp); void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c); void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c); void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a); BIGNUM *bn_expand(BIGNUM *a, int bits); BIGNUM *bn_wexpand(BIGNUM *a, int n); BIGNUM *bn_expand2(BIGNUM *a, int n); void bn_fix_top(BIGNUM *a); void bn_check_top(BIGNUM *a); void bn_print(BIGNUM *a); void bn_dump(BN_ULONG *d, int n); void bn_set_max(BIGNUM *a); void bn_set_high(BIGNUM *r, BIGNUM *a, int n); void bn_set_low(BIGNUM *r, BIGNUM *a, int n); DDEESSCCRRIIPPTTIIOONN This page documents the internal functions used by the OpenSSL BBIIGGNNUUMM implementation. They are described here to facilitate debugging and extending the library. They are _n_o_t to be used by applications. TThhee BBIIGGNNUUMM ssttrruuccttuurree typedef struct bignum_st BIGNUM; struct bignum_st { BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */ int top; /* Index of last used d +1. */ /* The next are internal book keeping for bn_expand. */ int dmax; /* Size of the d array. */ int neg; /* one if the number is negative */ int flags; }; The integer value is stored in dd, a _m_a_l_l_o_c_(_)ed array of words (BBNN__UULLOONNGG), least significant word first. A BBNN__UULLOONNGG can be either 16, 32 or 64 bits in size, depending on the 'number of bits' (BBIITTSS22) speci- fied in "openssl/bn.h". ddmmaaxx is the size of the dd array that has been allocated. ttoopp is the number of words being used, so for a value of 4, bn.d[0]=4 and bn.top=1. nneegg is 1 if the number is negative. When a BBIIGGNNUUMM is 00, the dd field can be NNUULLLL and ttoopp == 00. ffllaaggss is a bit field of flags which are defined in "openssl/bn.h". The flags begin with BBNN__FFLLGG__. The macros BN_set_flags(b,n) and BN_get_flags(b,n) exist to enable or fetch flag(s) nn from BBIIGGNNUUMM struc- ture bb. Various routines in this library require the use of temporary BBIIGGNNUUMM variables during their execution. Since dynamic memory allocation to create BBIIGGNNUUMMs is rather expensive when used in conjunction with repeated subroutine calls, the BBNN__CCTTXX structure is used. This struc- ture contains BBNN__CCTTXX__NNUUMM BBIIGGNNUUMMs, see _B_N___C_T_X___s_t_a_r_t(3). LLooww--lleevveell aarriitthhmmeettiicc ooppeerraattiioonnss These functions are implemented in C and for several platforms in assembly language: bn_mul_words(rrpp, aapp, nnuumm, ww) operates on the nnuumm word arrays rrpp and aapp. It computes aapp * ww, places the result in rrpp, and returns the high word (carry). bn_mul_add_words(rrpp, aapp, nnuumm, ww) operates on the nnuumm word arrays rrpp and aapp. It computes aapp * ww + rrpp, places the result in rrpp, and returns the high word (carry). bn_sqr_words(rrpp, aapp, nn) operates on the nnuumm word array aapp and the 2*nnuumm word array aapp. It computes aapp * aapp word-wise, and places the low and high bytes of the result in rrpp. bn_div_words(hh, ll, dd) divides the two word number (hh,ll) by dd and returns the result. bn_add_words(rrpp, aapp, bbpp, nnuumm) operates on the nnuumm word arrays aapp, bbpp and rrpp. It computes aapp + bbpp, places the result in rrpp, and returns the high word (carry). bn_sub_words(rrpp, aapp, bbpp, nnuumm) operates on the nnuumm word arrays aapp, bbpp and rrpp. It computes aapp - bbpp, places the result in rrpp, and returns the carry (1 if bbpp > aapp, 0 otherwise). bn_mul_comba4(rr, aa, bb) operates on the 4 word arrays aa and bb and the 8 word array rr. It computes aa*bb and places the result in rr. bn_mul_comba8(rr, aa, bb) operates on the 8 word arrays aa and bb and the 16 word array rr. It computes aa*bb and places the result in rr. bn_sqr_comba4(rr, aa, bb) operates on the 4 word arrays aa and bb and the 8 word array rr. bn_sqr_comba8(rr, aa, bb) operates on the 8 word arrays aa and bb and the 16 word array rr. The following functions are implemented in C: bn_cmp_words(aa, bb, nn) operates on the nn word arrays aa and bb. It returns 1, 0 and -1 if aa is greater than, equal and less than bb. bn_mul_normal(rr, aa, nnaa, bb, nnbb) operates on the nnaa word array aa, the nnbb word array bb and the nnaa+nnbb word array rr. It computes aa*bb and places the result in rr. bn_mul_low_normal(rr, aa, bb, nn) operates on the nn word arrays rr, aa and bb. It computes the nn low words of aa*bb and places the result in rr. bn_mul_recursive(rr, aa, bb, nn22, ddnnaa, ddnnbb, tt) operates on the word arrays aa and bb of length nn22+ddnnaa and nn22+ddnnbb (ddnnaa and ddnnbb are currently allowed to be 0 or negative) and the 2*nn22 word arrays rr and tt. nn22 must be a power of 2. It computes aa*bb and places the result in rr. bn_mul_part_recursive(rr, aa, bb, nn, ttnnaa, ttnnbb, ttmmpp) operates on the word arrays aa and bb of length nn+ttnnaa and nn+ttnnbb and the 4*nn word arrays rr and ttmmpp. bn_mul_low_recursive(rr, aa, bb, nn22, ttmmpp) operates on the nn22 word arrays rr and ttmmpp and the nn22/2 word arrays aa and bb. bn_mul_high(rr, aa, bb, ll, nn22, ttmmpp) operates on the nn22 word arrays rr, aa, bb and ll (?) and the 3*nn22 word array ttmmpp. _B_N___m_u_l_(_) calls _b_n___m_u_l___n_o_r_m_a_l_(_), or an optimized implementation if the factors have the same size: _b_n___m_u_l___c_o_m_b_a_8_(_) is used if they are 8 words long, _b_n___m_u_l___r_e_c_u_r_s_i_v_e_(_) if they are larger than BBNN__MMUULLLL__SSIIZZEE__NNOORRMMAALL and the size is an exact multiple of the word size, and _b_n___m_u_l___p_a_r_t___r_e_c_u_r_s_i_v_e_(_) for others that are larger than BBNN__MMUULLLL__SSIIZZEE__NNOORRMMAALL. bn_sqr_normal(rr, aa, nn, ttmmpp) operates on the nn word array aa and the 2*nn word arrays ttmmpp and rr. The implementations use the following macros which, depending on the architecture, may use "long long" C operations or inline assembler. They are defined in "bn_lcl.h". mul(rr, aa, ww, cc) computes ww*aa+cc and places the low word of the result in rr and the high word in cc. mul_add(rr, aa, ww, cc) computes ww*aa+rr+cc and places the low word of the result in rr and the high word in cc. sqr(rr00, rr11, aa) computes aa*aa and places the low word of the result in rr00 and the high word in rr11. SSiizzee cchhaannggeess _b_n___e_x_p_a_n_d_(_) ensures that bb has enough space for a bbiittss bit number. _b_n___w_e_x_p_a_n_d_(_) ensures that bb has enough space for an nn word number. If the number has to be expanded, both macros call _b_n___e_x_p_a_n_d_2_(_), which allocates a new dd array and copies the data. They return NNUULLLL on error, bb otherwise. The _b_n___f_i_x___t_o_p_(_) macro reduces aa-->>ttoopp to point to the most significant non-zero word plus one when aa has shrunk. DDeebbuuggggiinngg _b_n___c_h_e_c_k___t_o_p_(_) verifies that "((a)->top >= 0 && (a)->top <= (a)->dmax)". A violation will cause the program to abort. _b_n___p_r_i_n_t_(_) prints aa to stderr. _b_n___d_u_m_p_(_) prints nn words at dd (in reverse order, i.e. most significant word first) to stderr. _b_n___s_e_t___m_a_x_(_) makes aa a static number with a ddmmaaxx of its current size. This is used by _b_n___s_e_t___l_o_w_(_) and _b_n___s_e_t___h_i_g_h_(_) to make rr a read-only BBIIGGNNUUMM that contains the nn low or high words of aa. If BBNN__DDEEBBUUGG is not defined, _b_n___c_h_e_c_k___t_o_p_(_), _b_n___p_r_i_n_t_(_), _b_n___d_u_m_p_(_) and _b_n___s_e_t___m_a_x_(_) are defined as empty macros. SSEEEE AALLSSOO _b_n(3) 1.0.2u 2019-12-20 bn_internal(3)