1 .\" Automatically generated by Pod::Man 2.16 (Pod::Simple 3.05)
4 .\" ========================================================================
5 .de Sh \" Subsection heading
13 .de Sp \" Vertical space (when we can't use .PP)
17 .de Vb \" Begin verbatim text
22 .de Ve \" End verbatim text
26 .\" Set up some character translations and predefined strings. \*(-- will
27 .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
28 .\" double quote, and \*(R" will give a right double quote. \*(C+ will
29 .\" give a nicer C++. Capital omega is used to do unbreakable dashes and
30 .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff,
31 .\" nothing in troff, for use with C<>.
33 .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
37 . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
38 . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch
51 .\" Escape single quotes in literal strings from groff's Unicode transform.
55 .\" If the F register is turned on, we'll generate index entries on stderr for
56 .\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index
57 .\" entries marked with X<> in POD. Of course, you'll have to process the
58 .\" output yourself in some meaningful fashion.
61 . tm Index:\\$1\t\\n%\t"\\$2"
71 .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
72 .\" Fear. Run. Save yourself. No user-serviceable parts.
73 . \" fudge factors for nroff and troff
82 . ds #H ((1u-(\\\\n(.fu%2u))*.13m)
88 . \" simple accents for nroff and troff
98 . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
99 . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
100 . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
101 . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
102 . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
103 . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
105 . \" troff and (daisy-wheel) nroff accents
106 .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
107 .ds 8 \h'\*(#H'\(*b\h'-\*(#H'
108 .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
109 .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
110 .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
111 .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
112 .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
113 .ds ae a\h'-(\w'a'u*4/10)'e
114 .ds Ae A\h'-(\w'A'u*4/10)'E
115 . \" corrections for vroff
116 .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
117 .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
118 . \" for low resolution devices (crt and lpr)
119 .if \n(.H>23 .if \n(.V>19 \
132 .\" ========================================================================
134 .IX Title "bn_internal 3"
135 .TH bn_internal 3 "2009-04-11" "0.9.8k" "OpenSSL"
136 .\" For nroff, turn off justification. Always turn off hyphenation; it makes
137 .\" way too many mistakes in technical documents.
141 bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words,
142 bn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8,
143 bn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal,
144 bn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive,
145 bn_mul_low_recursive, bn_mul_high, bn_sqr_normal, bn_sqr_recursive,
146 bn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top,
147 bn_print, bn_dump, bn_set_max, bn_set_high, bn_set_low \- BIGNUM
148 library internal functions
150 .IX Header "SYNOPSIS"
152 \& BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
153 \& BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num,
155 \& void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num);
156 \& BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
157 \& BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
159 \& BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
162 \& void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
163 \& void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
164 \& void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a);
165 \& void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a);
167 \& int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n);
169 \& void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b,
171 \& void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
172 \& void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
173 \& int dna,int dnb,BN_ULONG *tmp);
174 \& void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
175 \& int n, int tna,int tnb, BN_ULONG *tmp);
176 \& void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
177 \& int n2, BN_ULONG *tmp);
178 \& void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l,
179 \& int n2, BN_ULONG *tmp);
181 \& void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp);
182 \& void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp);
184 \& void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
185 \& void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
186 \& void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a);
188 \& BIGNUM *bn_expand(BIGNUM *a, int bits);
189 \& BIGNUM *bn_wexpand(BIGNUM *a, int n);
190 \& BIGNUM *bn_expand2(BIGNUM *a, int n);
191 \& void bn_fix_top(BIGNUM *a);
193 \& void bn_check_top(BIGNUM *a);
194 \& void bn_print(BIGNUM *a);
195 \& void bn_dump(BN_ULONG *d, int n);
196 \& void bn_set_max(BIGNUM *a);
197 \& void bn_set_high(BIGNUM *r, BIGNUM *a, int n);
198 \& void bn_set_low(BIGNUM *r, BIGNUM *a, int n);
201 .IX Header "DESCRIPTION"
202 This page documents the internal functions used by the OpenSSL
203 \&\fB\s-1BIGNUM\s0\fR implementation. They are described here to facilitate
204 debugging and extending the library. They are \fInot\fR to be used by
206 .Sh "The \s-1BIGNUM\s0 structure"
207 .IX Subsection "The BIGNUM structure"
209 \& typedef struct bignum_st
211 \& int top; /* number of words used in d */
212 \& BN_ULONG *d; /* pointer to an array containing the integer value */
213 \& int max; /* size of the d array */
214 \& int neg; /* sign */
218 The integer value is stored in \fBd\fR, a \fImalloc()\fRed array of words (\fB\s-1BN_ULONG\s0\fR),
219 least significant word first. A \fB\s-1BN_ULONG\s0\fR can be either 16, 32 or 64 bits
220 in size, depending on the 'number of bits' (\fB\s-1BITS2\s0\fR) specified in
221 \&\f(CW\*(C`openssl/bn.h\*(C'\fR.
223 \&\fBmax\fR is the size of the \fBd\fR array that has been allocated. \fBtop\fR
224 is the number of words being used, so for a value of 4, bn.d[0]=4 and
225 bn.top=1. \fBneg\fR is 1 if the number is negative. When a \fB\s-1BIGNUM\s0\fR is
226 \&\fB0\fR, the \fBd\fR field can be \fB\s-1NULL\s0\fR and \fBtop\fR == \fB0\fR.
228 Various routines in this library require the use of temporary
229 \&\fB\s-1BIGNUM\s0\fR variables during their execution. Since dynamic memory
230 allocation to create \fB\s-1BIGNUM\s0\fRs is rather expensive when used in
231 conjunction with repeated subroutine calls, the \fB\s-1BN_CTX\s0\fR structure is
232 used. This structure contains \fB\s-1BN_CTX_NUM\s0\fR \fB\s-1BIGNUM\s0\fRs, see
233 \&\fIBN_CTX_start\fR\|(3).
234 .Sh "Low-level arithmetic operations"
235 .IX Subsection "Low-level arithmetic operations"
236 These functions are implemented in C and for several platforms in
239 bn_mul_words(\fBrp\fR, \fBap\fR, \fBnum\fR, \fBw\fR) operates on the \fBnum\fR word
240 arrays \fBrp\fR and \fBap\fR. It computes \fBap\fR * \fBw\fR, places the result
241 in \fBrp\fR, and returns the high word (carry).
243 bn_mul_add_words(\fBrp\fR, \fBap\fR, \fBnum\fR, \fBw\fR) operates on the \fBnum\fR
244 word arrays \fBrp\fR and \fBap\fR. It computes \fBap\fR * \fBw\fR + \fBrp\fR, places
245 the result in \fBrp\fR, and returns the high word (carry).
247 bn_sqr_words(\fBrp\fR, \fBap\fR, \fBn\fR) operates on the \fBnum\fR word array
248 \&\fBap\fR and the 2*\fBnum\fR word array \fBap\fR. It computes \fBap\fR * \fBap\fR
249 word-wise, and places the low and high bytes of the result in \fBrp\fR.
251 bn_div_words(\fBh\fR, \fBl\fR, \fBd\fR) divides the two word number (\fBh\fR,\fBl\fR)
252 by \fBd\fR and returns the result.
254 bn_add_words(\fBrp\fR, \fBap\fR, \fBbp\fR, \fBnum\fR) operates on the \fBnum\fR word
255 arrays \fBap\fR, \fBbp\fR and \fBrp\fR. It computes \fBap\fR + \fBbp\fR, places the
256 result in \fBrp\fR, and returns the high word (carry).
258 bn_sub_words(\fBrp\fR, \fBap\fR, \fBbp\fR, \fBnum\fR) operates on the \fBnum\fR word
259 arrays \fBap\fR, \fBbp\fR and \fBrp\fR. It computes \fBap\fR \- \fBbp\fR, places the
260 result in \fBrp\fR, and returns the carry (1 if \fBbp\fR > \fBap\fR, 0
263 bn_mul_comba4(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 4 word arrays \fBa\fR and
264 \&\fBb\fR and the 8 word array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the
267 bn_mul_comba8(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 8 word arrays \fBa\fR and
268 \&\fBb\fR and the 16 word array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the
271 bn_sqr_comba4(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 4 word arrays \fBa\fR and
272 \&\fBb\fR and the 8 word array \fBr\fR.
274 bn_sqr_comba8(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 8 word arrays \fBa\fR and
275 \&\fBb\fR and the 16 word array \fBr\fR.
277 The following functions are implemented in C:
279 bn_cmp_words(\fBa\fR, \fBb\fR, \fBn\fR) operates on the \fBn\fR word arrays \fBa\fR
280 and \fBb\fR. It returns 1, 0 and \-1 if \fBa\fR is greater than, equal and
283 bn_mul_normal(\fBr\fR, \fBa\fR, \fBna\fR, \fBb\fR, \fBnb\fR) operates on the \fBna\fR
284 word array \fBa\fR, the \fBnb\fR word array \fBb\fR and the \fBna\fR+\fBnb\fR word
285 array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the result in \fBr\fR.
287 bn_mul_low_normal(\fBr\fR, \fBa\fR, \fBb\fR, \fBn\fR) operates on the \fBn\fR word
288 arrays \fBr\fR, \fBa\fR and \fBb\fR. It computes the \fBn\fR low words of
289 \&\fBa\fR*\fBb\fR and places the result in \fBr\fR.
291 bn_mul_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn2\fR, \fBdna\fR, \fBdnb\fR, \fBt\fR) operates
292 on the word arrays \fBa\fR and \fBb\fR of length \fBn2\fR+\fBdna\fR and \fBn2\fR+\fBdnb\fR
293 (\fBdna\fR and \fBdnb\fR are currently allowed to be 0 or negative) and the 2*\fBn2\fR
294 word arrays \fBr\fR and \fBt\fR. \fBn2\fR must be a power of 2. It computes
295 \&\fBa\fR*\fBb\fR and places the result in \fBr\fR.
297 bn_mul_part_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn\fR, \fBtna\fR, \fBtnb\fR, \fBtmp\fR)
298 operates on the word arrays \fBa\fR and \fBb\fR of length \fBn\fR+\fBtna\fR and
299 \&\fBn\fR+\fBtnb\fR and the 4*\fBn\fR word arrays \fBr\fR and \fBtmp\fR.
301 bn_mul_low_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn2\fR, \fBtmp\fR) operates on the
302 \&\fBn2\fR word arrays \fBr\fR and \fBtmp\fR and the \fBn2\fR/2 word arrays \fBa\fR
305 bn_mul_high(\fBr\fR, \fBa\fR, \fBb\fR, \fBl\fR, \fBn2\fR, \fBtmp\fR) operates on the
306 \&\fBn2\fR word arrays \fBr\fR, \fBa\fR, \fBb\fR and \fBl\fR (?) and the 3*\fBn2\fR word
309 \&\fIBN_mul()\fR calls \fIbn_mul_normal()\fR, or an optimized implementation if the
310 factors have the same size: \fIbn_mul_comba8()\fR is used if they are 8
311 words long, \fIbn_mul_recursive()\fR if they are larger than
312 \&\fB\s-1BN_MULL_SIZE_NORMAL\s0\fR and the size is an exact multiple of the word
313 size, and \fIbn_mul_part_recursive()\fR for others that are larger than
314 \&\fB\s-1BN_MULL_SIZE_NORMAL\s0\fR.
316 bn_sqr_normal(\fBr\fR, \fBa\fR, \fBn\fR, \fBtmp\fR) operates on the \fBn\fR word array
317 \&\fBa\fR and the 2*\fBn\fR word arrays \fBtmp\fR and \fBr\fR.
319 The implementations use the following macros which, depending on the
320 architecture, may use \*(L"long long\*(R" C operations or inline assembler.
321 They are defined in \f(CW\*(C`bn_lcl.h\*(C'\fR.
323 mul(\fBr\fR, \fBa\fR, \fBw\fR, \fBc\fR) computes \fBw\fR*\fBa\fR+\fBc\fR and places the
324 low word of the result in \fBr\fR and the high word in \fBc\fR.
326 mul_add(\fBr\fR, \fBa\fR, \fBw\fR, \fBc\fR) computes \fBw\fR*\fBa\fR+\fBr\fR+\fBc\fR and
327 places the low word of the result in \fBr\fR and the high word in \fBc\fR.
329 sqr(\fBr0\fR, \fBr1\fR, \fBa\fR) computes \fBa\fR*\fBa\fR and places the low word
330 of the result in \fBr0\fR and the high word in \fBr1\fR.
332 .IX Subsection "Size changes"
333 \&\fIbn_expand()\fR ensures that \fBb\fR has enough space for a \fBbits\fR bit
334 number. \fIbn_wexpand()\fR ensures that \fBb\fR has enough space for an
335 \&\fBn\fR word number. If the number has to be expanded, both macros
336 call \fIbn_expand2()\fR, which allocates a new \fBd\fR array and copies the
337 data. They return \fB\s-1NULL\s0\fR on error, \fBb\fR otherwise.
339 The \fIbn_fix_top()\fR macro reduces \fBa\->top\fR to point to the most
340 significant non-zero word plus one when \fBa\fR has shrunk.
342 .IX Subsection "Debugging"
343 \&\fIbn_check_top()\fR verifies that \f(CW\*(C`((a)\->top >= 0 && (a)\->top
344 <= (a)\->max)\*(C'\fR. A violation will cause the program to abort.
346 \&\fIbn_print()\fR prints \fBa\fR to stderr. \fIbn_dump()\fR prints \fBn\fR words at \fBd\fR
347 (in reverse order, i.e. most significant word first) to stderr.
349 \&\fIbn_set_max()\fR makes \fBa\fR a static number with a \fBmax\fR of its current size.
350 This is used by \fIbn_set_low()\fR and \fIbn_set_high()\fR to make \fBr\fR a read-only
351 \&\fB\s-1BIGNUM\s0\fR that contains the \fBn\fR low or high words of \fBa\fR.
353 If \fB\s-1BN_DEBUG\s0\fR is not defined, \fIbn_check_top()\fR, \fIbn_print()\fR, \fIbn_dump()\fR
354 and \fIbn_set_max()\fR are defined as empty macros.
356 .IX Header "SEE ALSO"