crypto/openssl-0.9.7e/doc/crypto/bn_internal.pod

   1 =pod
   2
   3 =head1 NAME
   4
   5 bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words,
   6 bn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8,
   7 bn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal,
   8 bn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive,
   9 bn_mul_low_recursive, bn_mul_high, bn_sqr_normal, bn_sqr_recursive,
  10 bn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top,
  11 bn_print, bn_dump, bn_set_max, bn_set_high, bn_set_low - BIGNUM
  12 library internal functions
  13
  14 =head1 SYNOPSIS
  15
  16  BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
  17  BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num,
  18    BN_ULONG w);
  19  void     bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num);
  20  BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
  21  BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
  22    int num);
  23  BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
  24    int num);
  25
  26  void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
  27  void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
  28  void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a);
  29  void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a);
  30
  31  int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n);
  32
  33  void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b,
  34    int nb);
  35  void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
  36  void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
  37    int dna,int dnb,BN_ULONG *tmp);
  38  void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
  39    int n, int tna,int tnb, BN_ULONG *tmp);
  40  void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
  41    int n2, BN_ULONG *tmp);
  42  void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l,
  43    int n2, BN_ULONG *tmp);
  44
  45  void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp);
  46  void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp);
  47
  48  void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
  49  void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
  50  void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a);
  51
  52  BIGNUM *bn_expand(BIGNUM *a, int bits);
  53  BIGNUM *bn_wexpand(BIGNUM *a, int n);
  54  BIGNUM *bn_expand2(BIGNUM *a, int n);
  55  void bn_fix_top(BIGNUM *a);
  56
  57  void bn_check_top(BIGNUM *a);
  58  void bn_print(BIGNUM *a);
  59  void bn_dump(BN_ULONG *d, int n);
  60  void bn_set_max(BIGNUM *a);
  61  void bn_set_high(BIGNUM *r, BIGNUM *a, int n);
  62  void bn_set_low(BIGNUM *r, BIGNUM *a, int n);
  63
  64 =head1 DESCRIPTION
  65
  66 This page documents the internal functions used by the OpenSSL
  67 B<BIGNUM> implementation. They are described here to facilitate
  68 debugging and extending the library. They are I<not> to be used by
  69 applications.
  70
  71 =head2 The BIGNUM structure
  72
  73  typedef struct bignum_st
  74         {
  75         int top;      /* index of last used d (most significant word) */
  76         BN_ULONG *d;  /* pointer to an array of 'BITS2' bit chunks */
  77         int max;      /* size of the d array */
  78         int neg;      /* sign */
  79         } BIGNUM;
  80
  81 The big number is stored in B<d>, a malloc()ed array of B<BN_ULONG>s,
  82 least significant first. A B<BN_ULONG> can be either 16, 32 or 64 bits
  83 in size (B<BITS2>), depending on the 'number of bits' specified in
  84 C<openssl/bn.h>.
  85
  86 B<max> is the size of the B<d> array that has been allocated.  B<top>
  87 is the 'last' entry being used, so for a value of 4, bn.d[0]=4 and
  88 bn.top=1.  B<neg> is 1 if the number is negative.  When a B<BIGNUM> is
  89 B<0>, the B<d> field can be B<NULL> and B<top> == B<0>.
  90
  91 Various routines in this library require the use of temporary
  92 B<BIGNUM> variables during their execution.  Since dynamic memory
  93 allocation to create B<BIGNUM>s is rather expensive when used in
  94 conjunction with repeated subroutine calls, the B<BN_CTX> structure is
  95 used.  This structure contains B<BN_CTX_NUM> B<BIGNUM>s, see
  96 L<BN_CTX_start(3)|BN_CTX_start(3)>.
  97
  98 =head2 Low-level arithmetic operations
  99
 100 These functions are implemented in C and for several platforms in
 101 assembly language:
 102
 103 bn_mul_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num> word
 104 arrays B<rp> and B<ap>.  It computes B<ap> * B<w>, places the result
 105 in B<rp>, and returns the high word (carry).
 106
 107 bn_mul_add_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num>
 108 word arrays B<rp> and B<ap>.  It computes B<ap> * B<w> + B<rp>, places
 109 the result in B<rp>, and returns the high word (carry).
 110
 111 bn_sqr_words(B<rp>, B<ap>, B<n>) operates on the B<num> word array
 112 B<ap> and the 2*B<num> word array B<ap>.  It computes B<ap> * B<ap>
 113 word-wise, and places the low and high bytes of the result in B<rp>.
 114
 115 bn_div_words(B<h>, B<l>, B<d>) divides the two word number (B<h>,B<l>)
 116 by B<d> and returns the result.
 117
 118 bn_add_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word
 119 arrays B<ap>, B<bp> and B<rp>.  It computes B<ap> + B<bp>, places the
 120 result in B<rp>, and returns the high word (carry).
 121
 122 bn_sub_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word
 123 arrays B<ap>, B<bp> and B<rp>.  It computes B<ap> - B<bp>, places the
 124 result in B<rp>, and returns the carry (1 if B<bp> E<gt> B<ap>, 0
 125 otherwise).
 126
 127 bn_mul_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and
 128 B<b> and the 8 word array B<r>.  It computes B<a>*B<b> and places the
 129 result in B<r>.
 130
 131 bn_mul_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and
 132 B<b> and the 16 word array B<r>.  It computes B<a>*B<b> and places the
 133 result in B<r>.
 134
 135 bn_sqr_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and
 136 B<b> and the 8 word array B<r>.
 137
 138 bn_sqr_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and
 139 B<b> and the 16 word array B<r>.
 140
 141 The following functions are implemented in C:
 142
 143 bn_cmp_words(B<a>, B<b>, B<n>) operates on the B<n> word arrays B<a>
 144 and B<b>.  It returns 1, 0 and -1 if B<a> is greater than, equal and
 145 less than B<b>.
 146
 147 bn_mul_normal(B<r>, B<a>, B<na>, B<b>, B<nb>) operates on the B<na>
 148 word array B<a>, the B<nb> word array B<b> and the B<na>+B<nb> word
 149 array B<r>.  It computes B<a>*B<b> and places the result in B<r>.
 150
 151 bn_mul_low_normal(B<r>, B<a>, B<b>, B<n>) operates on the B<n> word
 152 arrays B<r>, B<a> and B<b>.  It computes the B<n> low words of
 153 B<a>*B<b> and places the result in B<r>.
 154
 155 bn_mul_recursive(B<r>, B<a>, B<b>, B<n2>, B<dna>, B<dnb>, B<t>) operates
 156 on the word arrays B<a> and B<b> of length B<n2>+B<dna> and B<n2>+B<dnb>
 157 (B<dna> and B<dnb> are currently allowed to be 0 or negative) and the 2*B<n2>
 158 word arrays B<r> and B<t>.  B<n2> must be a power of 2.  It computes
 159 B<a>*B<b> and places the result in B<r>.
 160
 161 bn_mul_part_recursive(B<r>, B<a>, B<b>, B<n>, B<tna>, B<tnb>, B<tmp>)
 162 operates on the word arrays B<a> and B<b> of length B<n>+B<tna> and
 163 B<n>+B<tnb> and the 4*B<n> word arrays B<r> and B<tmp>.
 164
 165 bn_mul_low_recursive(B<r>, B<a>, B<b>, B<n2>, B<tmp>) operates on the
 166 B<n2> word arrays B<r> and B<tmp> and the B<n2>/2 word arrays B<a>
 167 and B<b>.
 168
 169 bn_mul_high(B<r>, B<a>, B<b>, B<l>, B<n2>, B<tmp>) operates on the
 170 B<n2> word arrays B<r>, B<a>, B<b> and B<l> (?) and the 3*B<n2> word
 171 array B<tmp>.
 172
 173 BN_mul() calls bn_mul_normal(), or an optimized implementation if the
 174 factors have the same size: bn_mul_comba8() is used if they are 8
 175 words long, bn_mul_recursive() if they are larger than
 176 B<BN_MULL_SIZE_NORMAL> and the size is an exact multiple of the word
 177 size, and bn_mul_part_recursive() for others that are larger than
 178 B<BN_MULL_SIZE_NORMAL>.
 179
 180 bn_sqr_normal(B<r>, B<a>, B<n>, B<tmp>) operates on the B<n> word array
 181 B<a> and the 2*B<n> word arrays B<tmp> and B<r>.
 182
 183 The implementations use the following macros which, depending on the
 184 architecture, may use "long long" C operations or inline assembler.
 185 They are defined in C<bn_lcl.h>.
 186
 187 mul(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<c> and places the
 188 low word of the result in B<r> and the high word in B<c>.
 189
 190 mul_add(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<r>+B<c> and
 191 places the low word of the result in B<r> and the high word in B<c>.
 192
 193 sqr(B<r0>, B<r1>, B<a>) computes B<a>*B<a> and places the low word
 194 of the result in B<r0> and the high word in B<r1>.
 195
 196 =head2 Size changes
 197
 198 bn_expand() ensures that B<b> has enough space for a B<bits> bit
 199 number.  bn_wexpand() ensures that B<b> has enough space for an
 200 B<n> word number.  If the number has to be expanded, both macros
 201 call bn_expand2(), which allocates a new B<d> array and copies the
 202 data.  They return B<NULL> on error, B<b> otherwise.
 203
 204 The bn_fix_top() macro reduces B<a-E<gt>top> to point to the most
 205 significant non-zero word when B<a> has shrunk.
 206
 207 =head2 Debugging
 208
 209 bn_check_top() verifies that C<((a)-E<gt>top E<gt>= 0 && (a)-E<gt>top
 210 E<lt>= (a)-E<gt>max)>.  A violation will cause the program to abort.
 211
 212 bn_print() prints B<a> to stderr. bn_dump() prints B<n> words at B<d>
 213 (in reverse order, i.e. most significant word first) to stderr.
 214
 215 bn_set_max() makes B<a> a static number with a B<max> of its current size.
 216 This is used by bn_set_low() and bn_set_high() to make B<r> a read-only
 217 B<BIGNUM> that contains the B<n> low or high words of B<a>.
 218
 219 If B<BN_DEBUG> is not defined, bn_check_top(), bn_print(), bn_dump()
 220 and bn_set_max() are defined as empty macros.
 221
 222 =head1 SEE ALSO
 223
 224 L<bn(3)|bn(3)>
 225
 226 =cut