1 .\" Automatically generated by Pod::Man v1.37, Pod::Parser v1.32
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. | will give a
29 .\" real vertical bar. \*(C+ will give a nicer C++. Capital omega is used to
30 .\" do unbreakable dashes and therefore won't be available. \*(C` and \*(C'
31 .\" expand to `' in nroff, 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 .\" If the F register is turned on, we'll generate index entries on stderr for
52 .\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index
53 .\" entries marked with X<> in POD. Of course, you'll have to process the
54 .\" output yourself in some meaningful fashion.
57 . tm Index:\\$1\t\\n%\t"\\$2"
63 .\" For nroff, turn off justification. Always turn off hyphenation; it makes
64 .\" way too many mistakes in technical documents.
68 .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
69 .\" Fear. Run. Save yourself. No user-serviceable parts.
70 . \" fudge factors for nroff and troff
79 . ds #H ((1u-(\\\\n(.fu%2u))*.13m)
85 . \" simple accents for nroff and troff
95 . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
96 . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
97 . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
98 . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
99 . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
100 . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
102 . \" troff and (daisy-wheel) nroff accents
103 .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
104 .ds 8 \h'\*(#H'\(*b\h'-\*(#H'
105 .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
106 .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
107 .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
108 .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
109 .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
110 .ds ae a\h'-(\w'a'u*4/10)'e
111 .ds Ae A\h'-(\w'A'u*4/10)'E
112 . \" corrections for vroff
113 .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
114 .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
115 . \" for low resolution devices (crt and lpr)
116 .if \n(.H>23 .if \n(.V>19 \
129 .\" ========================================================================
131 .IX Title "bn_internal 3"
132 .TH bn_internal 3 "2009-07-23" "0.9.8k" "OpenSSL"
134 bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words,
135 bn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8,
136 bn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal,
137 bn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive,
138 bn_mul_low_recursive, bn_mul_high, bn_sqr_normal, bn_sqr_recursive,
139 bn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top,
140 bn_print, bn_dump, bn_set_max, bn_set_high, bn_set_low \- BIGNUM
141 library internal functions
143 .IX Header "SYNOPSIS"
145 \& BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
146 \& BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num,
148 \& void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num);
149 \& BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
150 \& BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
152 \& BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
157 \& void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
158 \& void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
159 \& void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a);
160 \& void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a);
164 \& int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n);
168 \& void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b,
170 \& void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
171 \& void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
172 \& int dna,int dnb,BN_ULONG *tmp);
173 \& void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
174 \& int n, int tna,int tnb, BN_ULONG *tmp);
175 \& void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
176 \& int n2, BN_ULONG *tmp);
177 \& void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l,
178 \& int n2, BN_ULONG *tmp);
182 \& void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp);
183 \& void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp);
187 \& void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
188 \& void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
189 \& void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a);
193 \& BIGNUM *bn_expand(BIGNUM *a, int bits);
194 \& BIGNUM *bn_wexpand(BIGNUM *a, int n);
195 \& BIGNUM *bn_expand2(BIGNUM *a, int n);
196 \& void bn_fix_top(BIGNUM *a);
200 \& void bn_check_top(BIGNUM *a);
201 \& void bn_print(BIGNUM *a);
202 \& void bn_dump(BN_ULONG *d, int n);
203 \& void bn_set_max(BIGNUM *a);
204 \& void bn_set_high(BIGNUM *r, BIGNUM *a, int n);
205 \& void bn_set_low(BIGNUM *r, BIGNUM *a, int n);
208 .IX Header "DESCRIPTION"
209 This page documents the internal functions used by the OpenSSL
210 \&\fB\s-1BIGNUM\s0\fR implementation. They are described here to facilitate
211 debugging and extending the library. They are \fInot\fR to be used by
213 .Sh "The \s-1BIGNUM\s0 structure"
214 .IX Subsection "The BIGNUM structure"
216 \& typedef struct bignum_st
218 \& int top; /* number of words used in d */
219 \& BN_ULONG *d; /* pointer to an array containing the integer value */
220 \& int max; /* size of the d array */
221 \& int neg; /* sign */
225 The integer value is stored in \fBd\fR, a \fImalloc()\fRed array of words (\fB\s-1BN_ULONG\s0\fR),
226 least significant word first. A \fB\s-1BN_ULONG\s0\fR can be either 16, 32 or 64 bits
227 in size, depending on the 'number of bits' (\fB\s-1BITS2\s0\fR) specified in
228 \&\f(CW\*(C`openssl/bn.h\*(C'\fR.
230 \&\fBmax\fR is the size of the \fBd\fR array that has been allocated. \fBtop\fR
231 is the number of words being used, so for a value of 4, bn.d[0]=4 and
232 bn.top=1. \fBneg\fR is 1 if the number is negative. When a \fB\s-1BIGNUM\s0\fR is
233 \&\fB0\fR, the \fBd\fR field can be \fB\s-1NULL\s0\fR and \fBtop\fR == \fB0\fR.
235 Various routines in this library require the use of temporary
236 \&\fB\s-1BIGNUM\s0\fR variables during their execution. Since dynamic memory
237 allocation to create \fB\s-1BIGNUM\s0\fRs is rather expensive when used in
238 conjunction with repeated subroutine calls, the \fB\s-1BN_CTX\s0\fR structure is
239 used. This structure contains \fB\s-1BN_CTX_NUM\s0\fR \fB\s-1BIGNUM\s0\fRs, see
240 \&\fIBN_CTX_start\fR\|(3).
241 .Sh "Low-level arithmetic operations"
242 .IX Subsection "Low-level arithmetic operations"
243 These functions are implemented in C and for several platforms in
246 bn_mul_words(\fBrp\fR, \fBap\fR, \fBnum\fR, \fBw\fR) operates on the \fBnum\fR word
247 arrays \fBrp\fR and \fBap\fR. It computes \fBap\fR * \fBw\fR, places the result
248 in \fBrp\fR, and returns the high word (carry).
250 bn_mul_add_words(\fBrp\fR, \fBap\fR, \fBnum\fR, \fBw\fR) operates on the \fBnum\fR
251 word arrays \fBrp\fR and \fBap\fR. It computes \fBap\fR * \fBw\fR + \fBrp\fR, places
252 the result in \fBrp\fR, and returns the high word (carry).
254 bn_sqr_words(\fBrp\fR, \fBap\fR, \fBn\fR) operates on the \fBnum\fR word array
255 \&\fBap\fR and the 2*\fBnum\fR word array \fBap\fR. It computes \fBap\fR * \fBap\fR
256 word\-wise, and places the low and high bytes of the result in \fBrp\fR.
258 bn_div_words(\fBh\fR, \fBl\fR, \fBd\fR) divides the two word number (\fBh\fR,\fBl\fR)
259 by \fBd\fR and returns the result.
261 bn_add_words(\fBrp\fR, \fBap\fR, \fBbp\fR, \fBnum\fR) operates on the \fBnum\fR word
262 arrays \fBap\fR, \fBbp\fR and \fBrp\fR. It computes \fBap\fR + \fBbp\fR, places the
263 result in \fBrp\fR, and returns the high word (carry).
265 bn_sub_words(\fBrp\fR, \fBap\fR, \fBbp\fR, \fBnum\fR) operates on the \fBnum\fR word
266 arrays \fBap\fR, \fBbp\fR and \fBrp\fR. It computes \fBap\fR \- \fBbp\fR, places the
267 result in \fBrp\fR, and returns the carry (1 if \fBbp\fR > \fBap\fR, 0
270 bn_mul_comba4(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 4 word arrays \fBa\fR and
271 \&\fBb\fR and the 8 word array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the
274 bn_mul_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. It computes \fBa\fR*\fBb\fR and places the
278 bn_sqr_comba4(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 4 word arrays \fBa\fR and
279 \&\fBb\fR and the 8 word array \fBr\fR.
281 bn_sqr_comba8(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 8 word arrays \fBa\fR and
282 \&\fBb\fR and the 16 word array \fBr\fR.
284 The following functions are implemented in C:
286 bn_cmp_words(\fBa\fR, \fBb\fR, \fBn\fR) operates on the \fBn\fR word arrays \fBa\fR
287 and \fBb\fR. It returns 1, 0 and \-1 if \fBa\fR is greater than, equal and
290 bn_mul_normal(\fBr\fR, \fBa\fR, \fBna\fR, \fBb\fR, \fBnb\fR) operates on the \fBna\fR
291 word array \fBa\fR, the \fBnb\fR word array \fBb\fR and the \fBna\fR+\fBnb\fR word
292 array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the result in \fBr\fR.
294 bn_mul_low_normal(\fBr\fR, \fBa\fR, \fBb\fR, \fBn\fR) operates on the \fBn\fR word
295 arrays \fBr\fR, \fBa\fR and \fBb\fR. It computes the \fBn\fR low words of
296 \&\fBa\fR*\fBb\fR and places the result in \fBr\fR.
298 bn_mul_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn2\fR, \fBdna\fR, \fBdnb\fR, \fBt\fR) operates
299 on the word arrays \fBa\fR and \fBb\fR of length \fBn2\fR+\fBdna\fR and \fBn2\fR+\fBdnb\fR
300 (\fBdna\fR and \fBdnb\fR are currently allowed to be 0 or negative) and the 2*\fBn2\fR
301 word arrays \fBr\fR and \fBt\fR. \fBn2\fR must be a power of 2. It computes
302 \&\fBa\fR*\fBb\fR and places the result in \fBr\fR.
304 bn_mul_part_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn\fR, \fBtna\fR, \fBtnb\fR, \fBtmp\fR)
305 operates on the word arrays \fBa\fR and \fBb\fR of length \fBn\fR+\fBtna\fR and
306 \&\fBn\fR+\fBtnb\fR and the 4*\fBn\fR word arrays \fBr\fR and \fBtmp\fR.
308 bn_mul_low_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn2\fR, \fBtmp\fR) operates on the
309 \&\fBn2\fR word arrays \fBr\fR and \fBtmp\fR and the \fBn2\fR/2 word arrays \fBa\fR
312 bn_mul_high(\fBr\fR, \fBa\fR, \fBb\fR, \fBl\fR, \fBn2\fR, \fBtmp\fR) operates on the
313 \&\fBn2\fR word arrays \fBr\fR, \fBa\fR, \fBb\fR and \fBl\fR (?) and the 3*\fBn2\fR word
316 \&\fIBN_mul()\fR calls \fIbn_mul_normal()\fR, or an optimized implementation if the
317 factors have the same size: \fIbn_mul_comba8()\fR is used if they are 8
318 words long, \fIbn_mul_recursive()\fR if they are larger than
319 \&\fB\s-1BN_MULL_SIZE_NORMAL\s0\fR and the size is an exact multiple of the word
320 size, and \fIbn_mul_part_recursive()\fR for others that are larger than
321 \&\fB\s-1BN_MULL_SIZE_NORMAL\s0\fR.
323 bn_sqr_normal(\fBr\fR, \fBa\fR, \fBn\fR, \fBtmp\fR) operates on the \fBn\fR word array
324 \&\fBa\fR and the 2*\fBn\fR word arrays \fBtmp\fR and \fBr\fR.
326 The implementations use the following macros which, depending on the
327 architecture, may use \*(L"long long\*(R" C operations or inline assembler.
328 They are defined in \f(CW\*(C`bn_lcl.h\*(C'\fR.
330 mul(\fBr\fR, \fBa\fR, \fBw\fR, \fBc\fR) computes \fBw\fR*\fBa\fR+\fBc\fR and places the
331 low word of the result in \fBr\fR and the high word in \fBc\fR.
333 mul_add(\fBr\fR, \fBa\fR, \fBw\fR, \fBc\fR) computes \fBw\fR*\fBa\fR+\fBr\fR+\fBc\fR and
334 places the low word of the result in \fBr\fR and the high word in \fBc\fR.
336 sqr(\fBr0\fR, \fBr1\fR, \fBa\fR) computes \fBa\fR*\fBa\fR and places the low word
337 of the result in \fBr0\fR and the high word in \fBr1\fR.
339 .IX Subsection "Size changes"
340 \&\fIbn_expand()\fR ensures that \fBb\fR has enough space for a \fBbits\fR bit
341 number. \fIbn_wexpand()\fR ensures that \fBb\fR has enough space for an
342 \&\fBn\fR word number. If the number has to be expanded, both macros
343 call \fIbn_expand2()\fR, which allocates a new \fBd\fR array and copies the
344 data. They return \fB\s-1NULL\s0\fR on error, \fBb\fR otherwise.
346 The \fIbn_fix_top()\fR macro reduces \fBa\->top\fR to point to the most
347 significant non-zero word plus one when \fBa\fR has shrunk.
349 .IX Subsection "Debugging"
350 \&\fIbn_check_top()\fR verifies that \f(CW\*(C`((a)\->top >= 0 && (a)\->top
351 <= (a)\->max)\*(C'\fR. A violation will cause the program to abort.
353 \&\fIbn_print()\fR prints \fBa\fR to stderr. \fIbn_dump()\fR prints \fBn\fR words at \fBd\fR
354 (in reverse order, i.e. most significant word first) to stderr.
356 \&\fIbn_set_max()\fR makes \fBa\fR a static number with a \fBmax\fR of its current size.
357 This is used by \fIbn_set_low()\fR and \fIbn_set_high()\fR to make \fBr\fR a read-only
358 \&\fB\s-1BIGNUM\s0\fR that contains the \fBn\fR low or high words of \fBa\fR.
360 If \fB\s-1BN_DEBUG\s0\fR is not defined, \fIbn_check_top()\fR, \fIbn_print()\fR, \fIbn_dump()\fR
361 and \fIbn_set_max()\fR are defined as empty macros.
363 .IX Header "SEE ALSO"