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