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