1 .\" Automatically generated by Pod::Man v1.37, Pod::Parser v1.37
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 "2010-03-24" "0.9.8n" "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 BIGNUM;
222 \& BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */
223 \& int top; /* Index of last used d +1. */
224 \& /* The next are internal book keeping for bn_expand. */
225 \& int dmax; /* Size of the d array. */
226 \& int neg; /* one if the number is negative */
231 The integer value is stored in \fBd\fR, a \fImalloc()\fRed array of words (\fB\s-1BN_ULONG\s0\fR),
232 least significant word first. A \fB\s-1BN_ULONG\s0\fR can be either 16, 32 or 64 bits
233 in size, depending on the 'number of bits' (\fB\s-1BITS2\s0\fR) specified in
234 \&\f(CW\*(C`openssl/bn.h\*(C'\fR.
236 \&\fBdmax\fR is the size of the \fBd\fR array that has been allocated. \fBtop\fR
237 is the number of words being used, so for a value of 4, bn.d[0]=4 and
238 bn.top=1. \fBneg\fR is 1 if the number is negative. When a \fB\s-1BIGNUM\s0\fR is
239 \&\fB0\fR, the \fBd\fR field can be \fB\s-1NULL\s0\fR and \fBtop\fR == \fB0\fR.
241 \&\fBflags\fR is a bit field of flags which are defined in \f(CW\*(C`openssl/bn.h\*(C'\fR. The
242 flags begin with \fB\s-1BN_FLG_\s0\fR. The macros BN_set_flags(b,n) and
243 BN_get_flags(b,n) exist to enable or fetch flag(s) \fBn\fR from \fB\s-1BIGNUM\s0\fR
246 Various routines in this library require the use of temporary
247 \&\fB\s-1BIGNUM\s0\fR variables during their execution. Since dynamic memory
248 allocation to create \fB\s-1BIGNUM\s0\fRs is rather expensive when used in
249 conjunction with repeated subroutine calls, the \fB\s-1BN_CTX\s0\fR structure is
250 used. This structure contains \fB\s-1BN_CTX_NUM\s0\fR \fB\s-1BIGNUM\s0\fRs, see
251 \&\fIBN_CTX_start\fR\|(3).
252 .Sh "Low-level arithmetic operations"
253 .IX Subsection "Low-level arithmetic operations"
254 These functions are implemented in C and for several platforms in
257 bn_mul_words(\fBrp\fR, \fBap\fR, \fBnum\fR, \fBw\fR) operates on the \fBnum\fR word
258 arrays \fBrp\fR and \fBap\fR. It computes \fBap\fR * \fBw\fR, places the result
259 in \fBrp\fR, and returns the high word (carry).
261 bn_mul_add_words(\fBrp\fR, \fBap\fR, \fBnum\fR, \fBw\fR) operates on the \fBnum\fR
262 word arrays \fBrp\fR and \fBap\fR. It computes \fBap\fR * \fBw\fR + \fBrp\fR, places
263 the result in \fBrp\fR, and returns the high word (carry).
265 bn_sqr_words(\fBrp\fR, \fBap\fR, \fBn\fR) operates on the \fBnum\fR word array
266 \&\fBap\fR and the 2*\fBnum\fR word array \fBap\fR. It computes \fBap\fR * \fBap\fR
267 word\-wise, and places the low and high bytes of the result in \fBrp\fR.
269 bn_div_words(\fBh\fR, \fBl\fR, \fBd\fR) divides the two word number (\fBh\fR,\fBl\fR)
270 by \fBd\fR and returns the result.
272 bn_add_words(\fBrp\fR, \fBap\fR, \fBbp\fR, \fBnum\fR) operates on the \fBnum\fR word
273 arrays \fBap\fR, \fBbp\fR and \fBrp\fR. It computes \fBap\fR + \fBbp\fR, places the
274 result in \fBrp\fR, and returns the high word (carry).
276 bn_sub_words(\fBrp\fR, \fBap\fR, \fBbp\fR, \fBnum\fR) operates on the \fBnum\fR word
277 arrays \fBap\fR, \fBbp\fR and \fBrp\fR. It computes \fBap\fR \- \fBbp\fR, places the
278 result in \fBrp\fR, and returns the carry (1 if \fBbp\fR > \fBap\fR, 0
281 bn_mul_comba4(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 4 word arrays \fBa\fR and
282 \&\fBb\fR and the 8 word array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the
285 bn_mul_comba8(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 8 word arrays \fBa\fR and
286 \&\fBb\fR and the 16 word array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the
289 bn_sqr_comba4(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 4 word arrays \fBa\fR and
290 \&\fBb\fR and the 8 word array \fBr\fR.
292 bn_sqr_comba8(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 8 word arrays \fBa\fR and
293 \&\fBb\fR and the 16 word array \fBr\fR.
295 The following functions are implemented in C:
297 bn_cmp_words(\fBa\fR, \fBb\fR, \fBn\fR) operates on the \fBn\fR word arrays \fBa\fR
298 and \fBb\fR. It returns 1, 0 and \-1 if \fBa\fR is greater than, equal and
301 bn_mul_normal(\fBr\fR, \fBa\fR, \fBna\fR, \fBb\fR, \fBnb\fR) operates on the \fBna\fR
302 word array \fBa\fR, the \fBnb\fR word array \fBb\fR and the \fBna\fR+\fBnb\fR word
303 array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the result in \fBr\fR.
305 bn_mul_low_normal(\fBr\fR, \fBa\fR, \fBb\fR, \fBn\fR) operates on the \fBn\fR word
306 arrays \fBr\fR, \fBa\fR and \fBb\fR. It computes the \fBn\fR low words of
307 \&\fBa\fR*\fBb\fR and places the result in \fBr\fR.
309 bn_mul_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn2\fR, \fBdna\fR, \fBdnb\fR, \fBt\fR) operates
310 on the word arrays \fBa\fR and \fBb\fR of length \fBn2\fR+\fBdna\fR and \fBn2\fR+\fBdnb\fR
311 (\fBdna\fR and \fBdnb\fR are currently allowed to be 0 or negative) and the 2*\fBn2\fR
312 word arrays \fBr\fR and \fBt\fR. \fBn2\fR must be a power of 2. It computes
313 \&\fBa\fR*\fBb\fR and places the result in \fBr\fR.
315 bn_mul_part_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn\fR, \fBtna\fR, \fBtnb\fR, \fBtmp\fR)
316 operates on the word arrays \fBa\fR and \fBb\fR of length \fBn\fR+\fBtna\fR and
317 \&\fBn\fR+\fBtnb\fR and the 4*\fBn\fR word arrays \fBr\fR and \fBtmp\fR.
319 bn_mul_low_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn2\fR, \fBtmp\fR) operates on the
320 \&\fBn2\fR word arrays \fBr\fR and \fBtmp\fR and the \fBn2\fR/2 word arrays \fBa\fR
323 bn_mul_high(\fBr\fR, \fBa\fR, \fBb\fR, \fBl\fR, \fBn2\fR, \fBtmp\fR) operates on the
324 \&\fBn2\fR word arrays \fBr\fR, \fBa\fR, \fBb\fR and \fBl\fR (?) and the 3*\fBn2\fR word
327 \&\fIBN_mul()\fR calls \fIbn_mul_normal()\fR, or an optimized implementation if the
328 factors have the same size: \fIbn_mul_comba8()\fR is used if they are 8
329 words long, \fIbn_mul_recursive()\fR if they are larger than
330 \&\fB\s-1BN_MULL_SIZE_NORMAL\s0\fR and the size is an exact multiple of the word
331 size, and \fIbn_mul_part_recursive()\fR for others that are larger than
332 \&\fB\s-1BN_MULL_SIZE_NORMAL\s0\fR.
334 bn_sqr_normal(\fBr\fR, \fBa\fR, \fBn\fR, \fBtmp\fR) operates on the \fBn\fR word array
335 \&\fBa\fR and the 2*\fBn\fR word arrays \fBtmp\fR and \fBr\fR.
337 The implementations use the following macros which, depending on the
338 architecture, may use \*(L"long long\*(R" C operations or inline assembler.
339 They are defined in \f(CW\*(C`bn_lcl.h\*(C'\fR.
341 mul(\fBr\fR, \fBa\fR, \fBw\fR, \fBc\fR) computes \fBw\fR*\fBa\fR+\fBc\fR and places the
342 low word of the result in \fBr\fR and the high word in \fBc\fR.
344 mul_add(\fBr\fR, \fBa\fR, \fBw\fR, \fBc\fR) computes \fBw\fR*\fBa\fR+\fBr\fR+\fBc\fR and
345 places the low word of the result in \fBr\fR and the high word in \fBc\fR.
347 sqr(\fBr0\fR, \fBr1\fR, \fBa\fR) computes \fBa\fR*\fBa\fR and places the low word
348 of the result in \fBr0\fR and the high word in \fBr1\fR.
350 .IX Subsection "Size changes"
351 \&\fIbn_expand()\fR ensures that \fBb\fR has enough space for a \fBbits\fR bit
352 number. \fIbn_wexpand()\fR ensures that \fBb\fR has enough space for an
353 \&\fBn\fR word number. If the number has to be expanded, both macros
354 call \fIbn_expand2()\fR, which allocates a new \fBd\fR array and copies the
355 data. They return \fB\s-1NULL\s0\fR on error, \fBb\fR otherwise.
357 The \fIbn_fix_top()\fR macro reduces \fBa\->top\fR to point to the most
358 significant non-zero word plus one when \fBa\fR has shrunk.
360 .IX Subsection "Debugging"
361 \&\fIbn_check_top()\fR verifies that \f(CW\*(C`((a)\->top >= 0 && (a)\->top
362 <= (a)\->dmax)\*(C'\fR. A violation will cause the program to abort.
364 \&\fIbn_print()\fR prints \fBa\fR to stderr. \fIbn_dump()\fR prints \fBn\fR words at \fBd\fR
365 (in reverse order, i.e. most significant word first) to stderr.
367 \&\fIbn_set_max()\fR makes \fBa\fR a static number with a \fBdmax\fR of its current size.
368 This is used by \fIbn_set_low()\fR and \fIbn_set_high()\fR to make \fBr\fR a read-only
369 \&\fB\s-1BIGNUM\s0\fR that contains the \fBn\fR low or high words of \fBa\fR.
371 If \fB\s-1BN_DEBUG\s0\fR is not defined, \fIbn_check_top()\fR, \fIbn_print()\fR, \fIbn_dump()\fR
372 and \fIbn_set_max()\fR are defined as empty macros.
374 .IX Header "SEE ALSO"