1 .\" Automatically generated by Pod::Man 2.12 (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 .\" 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 .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
64 .\" Fear. Run. Save yourself. No user-serviceable parts.
65 . \" fudge factors for nroff and troff
74 . ds #H ((1u-(\\\\n(.fu%2u))*.13m)
80 . \" simple accents for nroff and troff
90 . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
91 . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
92 . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
93 . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
94 . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
95 . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
97 . \" troff and (daisy-wheel) nroff accents
98 .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
99 .ds 8 \h'\*(#H'\(*b\h'-\*(#H'
100 .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
101 .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
102 .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
103 .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
104 .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
105 .ds ae a\h'-(\w'a'u*4/10)'e
106 .ds Ae A\h'-(\w'A'u*4/10)'E
107 . \" corrections for vroff
108 .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
109 .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
110 . \" for low resolution devices (crt and lpr)
111 .if \n(.H>23 .if \n(.V>19 \
124 .\" ========================================================================
126 .IX Title "bn_internal 3"
127 .TH bn_internal 3 "2007-10-24" "0.9.8g" "OpenSSL"
128 .\" For nroff, turn off justification. Always turn off hyphenation; it makes
129 .\" way too many mistakes in technical documents.
133 bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words,
134 bn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8,
135 bn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal,
136 bn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive,
137 bn_mul_low_recursive, bn_mul_high, bn_sqr_normal, bn_sqr_recursive,
138 bn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top,
139 bn_print, bn_dump, bn_set_max, bn_set_high, bn_set_low \- BIGNUM
140 library internal functions
142 .IX Header "SYNOPSIS"
144 \& BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
145 \& BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num,
147 \& void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num);
148 \& BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
149 \& BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
151 \& BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
154 \& void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
155 \& void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
156 \& void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a);
157 \& void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a);
159 \& int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n);
161 \& void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b,
163 \& void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
164 \& void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
165 \& int dna,int dnb,BN_ULONG *tmp);
166 \& void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
167 \& int n, int tna,int tnb, BN_ULONG *tmp);
168 \& void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
169 \& int n2, BN_ULONG *tmp);
170 \& void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l,
171 \& int n2, BN_ULONG *tmp);
173 \& void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp);
174 \& void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp);
176 \& void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
177 \& void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
178 \& void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a);
180 \& BIGNUM *bn_expand(BIGNUM *a, int bits);
181 \& BIGNUM *bn_wexpand(BIGNUM *a, int n);
182 \& BIGNUM *bn_expand2(BIGNUM *a, int n);
183 \& void bn_fix_top(BIGNUM *a);
185 \& void bn_check_top(BIGNUM *a);
186 \& void bn_print(BIGNUM *a);
187 \& void bn_dump(BN_ULONG *d, int n);
188 \& void bn_set_max(BIGNUM *a);
189 \& void bn_set_high(BIGNUM *r, BIGNUM *a, int n);
190 \& void bn_set_low(BIGNUM *r, BIGNUM *a, int n);
193 .IX Header "DESCRIPTION"
194 This page documents the internal functions used by the OpenSSL
195 \&\fB\s-1BIGNUM\s0\fR implementation. They are described here to facilitate
196 debugging and extending the library. They are \fInot\fR to be used by
198 .Sh "The \s-1BIGNUM\s0 structure"
199 .IX Subsection "The BIGNUM structure"
201 \& typedef struct bignum_st
203 \& int top; /* number of words used in d */
204 \& BN_ULONG *d; /* pointer to an array containing the integer value */
205 \& int max; /* size of the d array */
206 \& int neg; /* sign */
210 The integer value is stored in \fBd\fR, a \fImalloc()\fRed array of words (\fB\s-1BN_ULONG\s0\fR),
211 least significant word first. A \fB\s-1BN_ULONG\s0\fR can be either 16, 32 or 64 bits
212 in size, depending on the 'number of bits' (\fB\s-1BITS2\s0\fR) specified in
213 \&\f(CW\*(C`openssl/bn.h\*(C'\fR.
215 \&\fBmax\fR is the size of the \fBd\fR array that has been allocated. \fBtop\fR
216 is the number of words being used, so for a value of 4, bn.d[0]=4 and
217 bn.top=1. \fBneg\fR is 1 if the number is negative. When a \fB\s-1BIGNUM\s0\fR is
218 \&\fB0\fR, the \fBd\fR field can be \fB\s-1NULL\s0\fR and \fBtop\fR == \fB0\fR.
220 Various routines in this library require the use of temporary
221 \&\fB\s-1BIGNUM\s0\fR variables during their execution. Since dynamic memory
222 allocation to create \fB\s-1BIGNUM\s0\fRs is rather expensive when used in
223 conjunction with repeated subroutine calls, the \fB\s-1BN_CTX\s0\fR structure is
224 used. This structure contains \fB\s-1BN_CTX_NUM\s0\fR \fB\s-1BIGNUM\s0\fRs, see
225 \&\fIBN_CTX_start\fR\|(3).
226 .Sh "Low-level arithmetic operations"
227 .IX Subsection "Low-level arithmetic operations"
228 These functions are implemented in C and for several platforms in
231 bn_mul_words(\fBrp\fR, \fBap\fR, \fBnum\fR, \fBw\fR) operates on the \fBnum\fR word
232 arrays \fBrp\fR and \fBap\fR. It computes \fBap\fR * \fBw\fR, places the result
233 in \fBrp\fR, and returns the high word (carry).
235 bn_mul_add_words(\fBrp\fR, \fBap\fR, \fBnum\fR, \fBw\fR) operates on the \fBnum\fR
236 word arrays \fBrp\fR and \fBap\fR. It computes \fBap\fR * \fBw\fR + \fBrp\fR, places
237 the result in \fBrp\fR, and returns the high word (carry).
239 bn_sqr_words(\fBrp\fR, \fBap\fR, \fBn\fR) operates on the \fBnum\fR word array
240 \&\fBap\fR and the 2*\fBnum\fR word array \fBap\fR. It computes \fBap\fR * \fBap\fR
241 word-wise, and places the low and high bytes of the result in \fBrp\fR.
243 bn_div_words(\fBh\fR, \fBl\fR, \fBd\fR) divides the two word number (\fBh\fR,\fBl\fR)
244 by \fBd\fR and returns the result.
246 bn_add_words(\fBrp\fR, \fBap\fR, \fBbp\fR, \fBnum\fR) operates on the \fBnum\fR word
247 arrays \fBap\fR, \fBbp\fR and \fBrp\fR. It computes \fBap\fR + \fBbp\fR, places the
248 result in \fBrp\fR, and returns the high word (carry).
250 bn_sub_words(\fBrp\fR, \fBap\fR, \fBbp\fR, \fBnum\fR) operates on the \fBnum\fR word
251 arrays \fBap\fR, \fBbp\fR and \fBrp\fR. It computes \fBap\fR \- \fBbp\fR, places the
252 result in \fBrp\fR, and returns the carry (1 if \fBbp\fR > \fBap\fR, 0
255 bn_mul_comba4(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 4 word arrays \fBa\fR and
256 \&\fBb\fR and the 8 word array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the
259 bn_mul_comba8(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 8 word arrays \fBa\fR and
260 \&\fBb\fR and the 16 word array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the
263 bn_sqr_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.
266 bn_sqr_comba8(\fBr\fR, \fBa\fR, \fBb\fR) operates on the 8 word arrays \fBa\fR and
267 \&\fBb\fR and the 16 word array \fBr\fR.
269 The following functions are implemented in C:
271 bn_cmp_words(\fBa\fR, \fBb\fR, \fBn\fR) operates on the \fBn\fR word arrays \fBa\fR
272 and \fBb\fR. It returns 1, 0 and \-1 if \fBa\fR is greater than, equal and
275 bn_mul_normal(\fBr\fR, \fBa\fR, \fBna\fR, \fBb\fR, \fBnb\fR) operates on the \fBna\fR
276 word array \fBa\fR, the \fBnb\fR word array \fBb\fR and the \fBna\fR+\fBnb\fR word
277 array \fBr\fR. It computes \fBa\fR*\fBb\fR and places the result in \fBr\fR.
279 bn_mul_low_normal(\fBr\fR, \fBa\fR, \fBb\fR, \fBn\fR) operates on the \fBn\fR word
280 arrays \fBr\fR, \fBa\fR and \fBb\fR. It computes the \fBn\fR low words of
281 \&\fBa\fR*\fBb\fR and places the result in \fBr\fR.
283 bn_mul_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn2\fR, \fBdna\fR, \fBdnb\fR, \fBt\fR) operates
284 on the word arrays \fBa\fR and \fBb\fR of length \fBn2\fR+\fBdna\fR and \fBn2\fR+\fBdnb\fR
285 (\fBdna\fR and \fBdnb\fR are currently allowed to be 0 or negative) and the 2*\fBn2\fR
286 word arrays \fBr\fR and \fBt\fR. \fBn2\fR must be a power of 2. It computes
287 \&\fBa\fR*\fBb\fR and places the result in \fBr\fR.
289 bn_mul_part_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn\fR, \fBtna\fR, \fBtnb\fR, \fBtmp\fR)
290 operates on the word arrays \fBa\fR and \fBb\fR of length \fBn\fR+\fBtna\fR and
291 \&\fBn\fR+\fBtnb\fR and the 4*\fBn\fR word arrays \fBr\fR and \fBtmp\fR.
293 bn_mul_low_recursive(\fBr\fR, \fBa\fR, \fBb\fR, \fBn2\fR, \fBtmp\fR) operates on the
294 \&\fBn2\fR word arrays \fBr\fR and \fBtmp\fR and the \fBn2\fR/2 word arrays \fBa\fR
297 bn_mul_high(\fBr\fR, \fBa\fR, \fBb\fR, \fBl\fR, \fBn2\fR, \fBtmp\fR) operates on the
298 \&\fBn2\fR word arrays \fBr\fR, \fBa\fR, \fBb\fR and \fBl\fR (?) and the 3*\fBn2\fR word
301 \&\fIBN_mul()\fR calls \fIbn_mul_normal()\fR, or an optimized implementation if the
302 factors have the same size: \fIbn_mul_comba8()\fR is used if they are 8
303 words long, \fIbn_mul_recursive()\fR if they are larger than
304 \&\fB\s-1BN_MULL_SIZE_NORMAL\s0\fR and the size is an exact multiple of the word
305 size, and \fIbn_mul_part_recursive()\fR for others that are larger than
306 \&\fB\s-1BN_MULL_SIZE_NORMAL\s0\fR.
308 bn_sqr_normal(\fBr\fR, \fBa\fR, \fBn\fR, \fBtmp\fR) operates on the \fBn\fR word array
309 \&\fBa\fR and the 2*\fBn\fR word arrays \fBtmp\fR and \fBr\fR.
311 The implementations use the following macros which, depending on the
312 architecture, may use \*(L"long long\*(R" C operations or inline assembler.
313 They are defined in \f(CW\*(C`bn_lcl.h\*(C'\fR.
315 mul(\fBr\fR, \fBa\fR, \fBw\fR, \fBc\fR) computes \fBw\fR*\fBa\fR+\fBc\fR and places the
316 low word of the result in \fBr\fR and the high word in \fBc\fR.
318 mul_add(\fBr\fR, \fBa\fR, \fBw\fR, \fBc\fR) computes \fBw\fR*\fBa\fR+\fBr\fR+\fBc\fR and
319 places the low word of the result in \fBr\fR and the high word in \fBc\fR.
321 sqr(\fBr0\fR, \fBr1\fR, \fBa\fR) computes \fBa\fR*\fBa\fR and places the low word
322 of the result in \fBr0\fR and the high word in \fBr1\fR.
324 .IX Subsection "Size changes"
325 \&\fIbn_expand()\fR ensures that \fBb\fR has enough space for a \fBbits\fR bit
326 number. \fIbn_wexpand()\fR ensures that \fBb\fR has enough space for an
327 \&\fBn\fR word number. If the number has to be expanded, both macros
328 call \fIbn_expand2()\fR, which allocates a new \fBd\fR array and copies the
329 data. They return \fB\s-1NULL\s0\fR on error, \fBb\fR otherwise.
331 The \fIbn_fix_top()\fR macro reduces \fBa\->top\fR to point to the most
332 significant non-zero word plus one when \fBa\fR has shrunk.
334 .IX Subsection "Debugging"
335 \&\fIbn_check_top()\fR verifies that \f(CW\*(C`((a)\->top >= 0 && (a)\->top
336 <= (a)\->max)\*(C'\fR. A violation will cause the program to abort.
338 \&\fIbn_print()\fR prints \fBa\fR to stderr. \fIbn_dump()\fR prints \fBn\fR words at \fBd\fR
339 (in reverse order, i.e. most significant word first) to stderr.
341 \&\fIbn_set_max()\fR makes \fBa\fR a static number with a \fBmax\fR of its current size.
342 This is used by \fIbn_set_low()\fR and \fIbn_set_high()\fR to make \fBr\fR a read-only
343 \&\fB\s-1BIGNUM\s0\fR that contains the \fBn\fR low or high words of \fBa\fR.
345 If \fB\s-1BN_DEBUG\s0\fR is not defined, \fIbn_check_top()\fR, \fIbn_print()\fR, \fIbn_dump()\fR
346 and \fIbn_set_max()\fR are defined as empty macros.
348 .IX Header "SEE ALSO"