1*e7be843bSPierre Pronchery=pod 2*e7be843bSPierre Pronchery 3*e7be843bSPierre Pronchery=head1 NAME 4*e7be843bSPierre Pronchery 5*e7be843bSPierre Proncherybn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words, 6*e7be843bSPierre Proncherybn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8, 7*e7be843bSPierre Proncherybn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal, 8*e7be843bSPierre Proncherybn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive, 9*e7be843bSPierre Proncherybn_mul_low_recursive, bn_sqr_normal, bn_sqr_recursive, 10*e7be843bSPierre Proncherybn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top, 11*e7be843bSPierre Proncherymul, mul_add, sqr - BIGNUM 12*e7be843bSPierre Proncherylibrary internal functions 13*e7be843bSPierre Pronchery 14*e7be843bSPierre Pronchery=head1 SYNOPSIS 15*e7be843bSPierre Pronchery 16*e7be843bSPierre Pronchery #include <openssl/bn.h> 17*e7be843bSPierre Pronchery 18*e7be843bSPierre Pronchery BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w); 19*e7be843bSPierre Pronchery BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, 20*e7be843bSPierre Pronchery BN_ULONG w); 21*e7be843bSPierre Pronchery void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num); 22*e7be843bSPierre Pronchery BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d); 23*e7be843bSPierre Pronchery BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp, 24*e7be843bSPierre Pronchery int num); 25*e7be843bSPierre Pronchery BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp, 26*e7be843bSPierre Pronchery int num); 27*e7be843bSPierre Pronchery 28*e7be843bSPierre Pronchery void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); 29*e7be843bSPierre Pronchery void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); 30*e7be843bSPierre Pronchery void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a); 31*e7be843bSPierre Pronchery void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a); 32*e7be843bSPierre Pronchery 33*e7be843bSPierre Pronchery int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n); 34*e7be843bSPierre Pronchery 35*e7be843bSPierre Pronchery void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, 36*e7be843bSPierre Pronchery int nb); 37*e7be843bSPierre Pronchery void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n); 38*e7be843bSPierre Pronchery void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 39*e7be843bSPierre Pronchery int dna, int dnb, BN_ULONG *tmp); 40*e7be843bSPierre Pronchery void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, 41*e7be843bSPierre Pronchery int n, int tna, int tnb, BN_ULONG *tmp); 42*e7be843bSPierre Pronchery void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, 43*e7be843bSPierre Pronchery int n2, BN_ULONG *tmp); 44*e7be843bSPierre Pronchery 45*e7be843bSPierre Pronchery void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp); 46*e7be843bSPierre Pronchery void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp); 47*e7be843bSPierre Pronchery 48*e7be843bSPierre Pronchery BIGNUM *bn_expand(BIGNUM *a, int bits); 49*e7be843bSPierre Pronchery BIGNUM *bn_wexpand(BIGNUM *a, int n); 50*e7be843bSPierre Pronchery BIGNUM *bn_expand2(BIGNUM *a, int n); 51*e7be843bSPierre Pronchery void bn_fix_top(BIGNUM *a); 52*e7be843bSPierre Pronchery 53*e7be843bSPierre ProncheryThe following are macros: 54*e7be843bSPierre Pronchery 55*e7be843bSPierre Pronchery void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c); 56*e7be843bSPierre Pronchery void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c); 57*e7be843bSPierre Pronchery void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a); 58*e7be843bSPierre Pronchery 59*e7be843bSPierre Pronchery void bn_check_top(BIGNUM *a); 60*e7be843bSPierre Pronchery 61*e7be843bSPierre Pronchery=head1 DESCRIPTION 62*e7be843bSPierre Pronchery 63*e7be843bSPierre ProncheryThis page documents the internal functions used by the OpenSSL 64*e7be843bSPierre ProncheryB<BIGNUM> implementation. They are described here to facilitate 65*e7be843bSPierre Proncherydebugging and extending the library. They are I<not> to be used by 66*e7be843bSPierre Proncheryapplications. 67*e7be843bSPierre Pronchery 68*e7be843bSPierre Pronchery=head2 The BIGNUM structure 69*e7be843bSPierre Pronchery 70*e7be843bSPierre Pronchery typedef struct bignum_st BIGNUM; 71*e7be843bSPierre Pronchery 72*e7be843bSPierre Pronchery struct bignum_st 73*e7be843bSPierre Pronchery { 74*e7be843bSPierre Pronchery BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */ 75*e7be843bSPierre Pronchery int top; /* Index of last used d +1. */ 76*e7be843bSPierre Pronchery /* The next are internal book keeping for bn_expand. */ 77*e7be843bSPierre Pronchery int dmax; /* Size of the d array. */ 78*e7be843bSPierre Pronchery int neg; /* one if the number is negative */ 79*e7be843bSPierre Pronchery int flags; 80*e7be843bSPierre Pronchery }; 81*e7be843bSPierre Pronchery 82*e7be843bSPierre Pronchery 83*e7be843bSPierre ProncheryThe integer value is stored in B<d>, a malloc()ed array of words (B<BN_ULONG>), 84*e7be843bSPierre Proncheryleast significant word first. A B<BN_ULONG> can be either 16, 32 or 64 bits 85*e7be843bSPierre Proncheryin size, depending on the 'number of bits' (B<BITS2>) specified in 86*e7be843bSPierre ProncheryC<openssl/bn.h>. 87*e7be843bSPierre Pronchery 88*e7be843bSPierre ProncheryB<dmax> is the size of the B<d> array that has been allocated. B<top> 89*e7be843bSPierre Proncheryis the number of words being used, so for a value of 4, bn.d[0]=4 and 90*e7be843bSPierre Proncherybn.top=1. B<neg> is 1 if the number is negative. When a B<BIGNUM> is 91*e7be843bSPierre ProncheryB<0>, the B<d> field can be B<NULL> and B<top> == B<0>. 92*e7be843bSPierre Pronchery 93*e7be843bSPierre ProncheryB<flags> is a bit field of flags which are defined in C<openssl/bn.h>. The 94*e7be843bSPierre Proncheryflags begin with B<BN_FLG_>. The macros BN_set_flags(b, n) and 95*e7be843bSPierre ProncheryBN_get_flags(b, n) exist to enable or fetch flag(s) B<n> from B<BIGNUM> 96*e7be843bSPierre Proncherystructure B<b>. 97*e7be843bSPierre Pronchery 98*e7be843bSPierre ProncheryVarious routines in this library require the use of temporary 99*e7be843bSPierre ProncheryB<BIGNUM> variables during their execution. Since dynamic memory 100*e7be843bSPierre Proncheryallocation to create B<BIGNUM>s is rather expensive when used in 101*e7be843bSPierre Proncheryconjunction with repeated subroutine calls, the B<BN_CTX> structure is 102*e7be843bSPierre Proncheryused. This structure contains B<BN_CTX_NUM> B<BIGNUM>s, see 103*e7be843bSPierre ProncheryL<BN_CTX_start(3)>. 104*e7be843bSPierre Pronchery 105*e7be843bSPierre Pronchery=head2 Low-level arithmetic operations 106*e7be843bSPierre Pronchery 107*e7be843bSPierre ProncheryThese functions are implemented in C and for several platforms in 108*e7be843bSPierre Proncheryassembly language: 109*e7be843bSPierre Pronchery 110*e7be843bSPierre Proncherybn_mul_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num> word 111*e7be843bSPierre Proncheryarrays B<rp> and B<ap>. It computes B<ap> * B<w>, places the result 112*e7be843bSPierre Proncheryin B<rp>, and returns the high word (carry). 113*e7be843bSPierre Pronchery 114*e7be843bSPierre Proncherybn_mul_add_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num> 115*e7be843bSPierre Proncheryword arrays B<rp> and B<ap>. It computes B<ap> * B<w> + B<rp>, places 116*e7be843bSPierre Proncherythe result in B<rp>, and returns the high word (carry). 117*e7be843bSPierre Pronchery 118*e7be843bSPierre Proncherybn_sqr_words(B<rp>, B<ap>, B<n>) operates on the B<num> word array 119*e7be843bSPierre ProncheryB<ap> and the 2*B<num> word array B<ap>. It computes B<ap> * B<ap> 120*e7be843bSPierre Proncheryword-wise, and places the low and high bytes of the result in B<rp>. 121*e7be843bSPierre Pronchery 122*e7be843bSPierre Proncherybn_div_words(B<h>, B<l>, B<d>) divides the two word number (B<h>, B<l>) 123*e7be843bSPierre Proncheryby B<d> and returns the result. 124*e7be843bSPierre Pronchery 125*e7be843bSPierre Proncherybn_add_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word 126*e7be843bSPierre Proncheryarrays B<ap>, B<bp> and B<rp>. It computes B<ap> + B<bp>, places the 127*e7be843bSPierre Proncheryresult in B<rp>, and returns the high word (carry). 128*e7be843bSPierre Pronchery 129*e7be843bSPierre Proncherybn_sub_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word 130*e7be843bSPierre Proncheryarrays B<ap>, B<bp> and B<rp>. It computes B<ap> - B<bp>, places the 131*e7be843bSPierre Proncheryresult in B<rp>, and returns the carry (1 if B<bp> E<gt> B<ap>, 0 132*e7be843bSPierre Proncheryotherwise). 133*e7be843bSPierre Pronchery 134*e7be843bSPierre Proncherybn_mul_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and 135*e7be843bSPierre ProncheryB<b> and the 8 word array B<r>. It computes B<a>*B<b> and places the 136*e7be843bSPierre Proncheryresult in B<r>. 137*e7be843bSPierre Pronchery 138*e7be843bSPierre Proncherybn_mul_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and 139*e7be843bSPierre ProncheryB<b> and the 16 word array B<r>. It computes B<a>*B<b> and places the 140*e7be843bSPierre Proncheryresult in B<r>. 141*e7be843bSPierre Pronchery 142*e7be843bSPierre Proncherybn_sqr_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and 143*e7be843bSPierre ProncheryB<b> and the 8 word array B<r>. 144*e7be843bSPierre Pronchery 145*e7be843bSPierre Proncherybn_sqr_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and 146*e7be843bSPierre ProncheryB<b> and the 16 word array B<r>. 147*e7be843bSPierre Pronchery 148*e7be843bSPierre ProncheryThe following functions are implemented in C: 149*e7be843bSPierre Pronchery 150*e7be843bSPierre Proncherybn_cmp_words(B<a>, B<b>, B<n>) operates on the B<n> word arrays B<a> 151*e7be843bSPierre Proncheryand B<b>. It returns 1, 0 and -1 if B<a> is greater than, equal and 152*e7be843bSPierre Proncheryless than B<b>. 153*e7be843bSPierre Pronchery 154*e7be843bSPierre Proncherybn_mul_normal(B<r>, B<a>, B<na>, B<b>, B<nb>) operates on the B<na> 155*e7be843bSPierre Proncheryword array B<a>, the B<nb> word array B<b> and the B<na>+B<nb> word 156*e7be843bSPierre Proncheryarray B<r>. It computes B<a>*B<b> and places the result in B<r>. 157*e7be843bSPierre Pronchery 158*e7be843bSPierre Proncherybn_mul_low_normal(B<r>, B<a>, B<b>, B<n>) operates on the B<n> word 159*e7be843bSPierre Proncheryarrays B<r>, B<a> and B<b>. It computes the B<n> low words of 160*e7be843bSPierre ProncheryB<a>*B<b> and places the result in B<r>. 161*e7be843bSPierre Pronchery 162*e7be843bSPierre Proncherybn_mul_recursive(B<r>, B<a>, B<b>, B<n2>, B<dna>, B<dnb>, B<t>) operates 163*e7be843bSPierre Proncheryon the word arrays B<a> and B<b> of length B<n2>+B<dna> and B<n2>+B<dnb> 164*e7be843bSPierre Pronchery(B<dna> and B<dnb> are currently allowed to be 0 or negative) and the 2*B<n2> 165*e7be843bSPierre Proncheryword arrays B<r> and B<t>. B<n2> must be a power of 2. It computes 166*e7be843bSPierre ProncheryB<a>*B<b> and places the result in B<r>. 167*e7be843bSPierre Pronchery 168*e7be843bSPierre Proncherybn_mul_part_recursive(B<r>, B<a>, B<b>, B<n>, B<tna>, B<tnb>, B<tmp>) 169*e7be843bSPierre Proncheryoperates on the word arrays B<a> and B<b> of length B<n>+B<tna> and 170*e7be843bSPierre ProncheryB<n>+B<tnb> and the 4*B<n> word arrays B<r> and B<tmp>. 171*e7be843bSPierre Pronchery 172*e7be843bSPierre Proncherybn_mul_low_recursive(B<r>, B<a>, B<b>, B<n2>, B<tmp>) operates on the 173*e7be843bSPierre ProncheryB<n2> word arrays B<r> and B<tmp> and the B<n2>/2 word arrays B<a> 174*e7be843bSPierre Proncheryand B<b>. 175*e7be843bSPierre Pronchery 176*e7be843bSPierre ProncheryBN_mul() calls bn_mul_normal(), or an optimized implementation if the 177*e7be843bSPierre Proncheryfactors have the same size: bn_mul_comba8() is used if they are 8 178*e7be843bSPierre Proncherywords long, bn_mul_recursive() if they are larger than 179*e7be843bSPierre ProncheryB<BN_MULL_SIZE_NORMAL> and the size is an exact multiple of the word 180*e7be843bSPierre Proncherysize, and bn_mul_part_recursive() for others that are larger than 181*e7be843bSPierre ProncheryB<BN_MULL_SIZE_NORMAL>. 182*e7be843bSPierre Pronchery 183*e7be843bSPierre Proncherybn_sqr_normal(B<r>, B<a>, B<n>, B<tmp>) operates on the B<n> word array 184*e7be843bSPierre ProncheryB<a> and the 2*B<n> word arrays B<tmp> and B<r>. 185*e7be843bSPierre Pronchery 186*e7be843bSPierre ProncheryThe implementations use the following macros which, depending on the 187*e7be843bSPierre Proncheryarchitecture, may use "long long" C operations or inline assembler. 188*e7be843bSPierre ProncheryThey are defined in C<bn_local.h>. 189*e7be843bSPierre Pronchery 190*e7be843bSPierre Proncherymul(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<c> and places the 191*e7be843bSPierre Proncherylow word of the result in B<r> and the high word in B<c>. 192*e7be843bSPierre Pronchery 193*e7be843bSPierre Proncherymul_add(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<r>+B<c> and 194*e7be843bSPierre Proncheryplaces the low word of the result in B<r> and the high word in B<c>. 195*e7be843bSPierre Pronchery 196*e7be843bSPierre Proncherysqr(B<r0>, B<r1>, B<a>) computes B<a>*B<a> and places the low word 197*e7be843bSPierre Proncheryof the result in B<r0> and the high word in B<r1>. 198*e7be843bSPierre Pronchery 199*e7be843bSPierre Pronchery=head2 Size changes 200*e7be843bSPierre Pronchery 201*e7be843bSPierre Proncherybn_expand() ensures that B<b> has enough space for a B<bits> bit 202*e7be843bSPierre Proncherynumber. bn_wexpand() ensures that B<b> has enough space for an 203*e7be843bSPierre ProncheryB<n> word number. If the number has to be expanded, both macros 204*e7be843bSPierre Proncherycall bn_expand2(), which allocates a new B<d> array and copies the 205*e7be843bSPierre Proncherydata. They return B<NULL> on error, B<b> otherwise. 206*e7be843bSPierre Pronchery 207*e7be843bSPierre ProncheryThe bn_fix_top() macro reduces B<a-E<gt>top> to point to the most 208*e7be843bSPierre Proncherysignificant nonzero word plus one when B<a> has shrunk. 209*e7be843bSPierre Pronchery 210*e7be843bSPierre Pronchery=head2 Debugging 211*e7be843bSPierre Pronchery 212*e7be843bSPierre Proncherybn_check_top() verifies that C<((a)-E<gt>top E<gt>= 0 && (a)-E<gt>top 213*e7be843bSPierre ProncheryE<lt>= (a)-E<gt>dmax)>. A violation will cause the program to abort. 214*e7be843bSPierre Pronchery 215*e7be843bSPierre ProncheryIf B<BN_DEBUG> is not defined, bn_check_top() is 216*e7be843bSPierre Proncherydefined as an empty macro. 217*e7be843bSPierre Pronchery 218*e7be843bSPierre Pronchery=head1 RETURN VALUES 219*e7be843bSPierre Pronchery 220*e7be843bSPierre ProncheryDescribed above. 221*e7be843bSPierre Pronchery 222*e7be843bSPierre Pronchery=head1 COPYRIGHT 223*e7be843bSPierre Pronchery 224*e7be843bSPierre ProncheryCopyright 2000-2025 The OpenSSL Project Authors. All Rights Reserved. 225*e7be843bSPierre Pronchery 226*e7be843bSPierre ProncheryLicensed under the Apache License 2.0 (the "License"). You may not use 227*e7be843bSPierre Proncherythis file except in compliance with the License. You can obtain a copy 228*e7be843bSPierre Proncheryin the file LICENSE in the source distribution or at 229*e7be843bSPierre ProncheryL<https://www.openssl.org/source/license.html>. 230*e7be843bSPierre Pronchery 231*e7be843bSPierre Pronchery=cut 232