| blob | 6deac4db25cccfbbc8731646367018b9dc65a54f |
1 .\" $OpenBSD: bn_dump.3,v 1.6 2016/12/10 21:32:14 schwarze Exp $
2 .\" OpenSSL crypto/bn/README.pod aebb9aac Jul 19 09:27:53 2016 -0400
3 .\"
4 .\" This file was written by Ulf Moeller <ulf@openssl.org>.
5 .\" Copyright (c) 2000, 2003, 2006, 2009 The OpenSSL Project.
6 .\" All rights reserved.
7 .\"
8 .\" Redistribution and use in source and binary forms, with or without
9 .\" modification, are permitted provided that the following conditions
10 .\" are met:
11 .\"
12 .\" 1. Redistributions of source code must retain the above copyright
13 .\" notice, this list of conditions and the following disclaimer.
14 .\"
15 .\" 2. Redistributions in binary form must reproduce the above copyright
16 .\" notice, this list of conditions and the following disclaimer in
17 .\" the documentation and/or other materials provided with the
18 .\" distribution.
19 .\"
20 .\" 3. All advertising materials mentioning features or use of this
21 .\" software must display the following acknowledgment:
22 .\" "This product includes software developed by the OpenSSL Project
23 .\" for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
24 .\"
25 .\" 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26 .\" endorse or promote products derived from this software without
27 .\" prior written permission. For written permission, please contact
28 .\" openssl-core@openssl.org.
29 .\"
30 .\" 5. Products derived from this software may not be called "OpenSSL"
31 .\" nor may "OpenSSL" appear in their names without prior written
32 .\" permission of the OpenSSL Project.
33 .\"
34 .\" 6. Redistributions of any form whatsoever must retain the following
35 .\" acknowledgment:
36 .\" "This product includes software developed by the OpenSSL Project
37 .\" for use in the OpenSSL Toolkit (http://www.openssl.org/)"
38 .\"
39 .\" THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40 .\" EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42 .\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
43 .\" ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44 .\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45 .\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46 .\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48 .\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
51 .\"
52 .Dd $Mdocdate: December 10 2016 $
53 .Dt BN_DUMP 3
54 .Os
55 .Sh NAME
56 .Nm bn_mul_words ,
57 .Nm bn_mul_add_words ,
58 .Nm bn_sqr_words ,
59 .Nm bn_div_words ,
60 .Nm bn_add_words ,
61 .Nm bn_sub_words ,
62 .Nm bn_mul_comba4 ,
63 .Nm bn_mul_comba8 ,
64 .Nm bn_sqr_comba4 ,
65 .Nm bn_sqr_comba8 ,
66 .Nm bn_cmp_words ,
67 .Nm bn_mul_normal ,
68 .Nm bn_mul_low_normal ,
69 .Nm bn_mul_recursive ,
70 .Nm bn_mul_part_recursive ,
71 .Nm bn_mul_low_recursive ,
72 .Nm bn_mul_high ,
73 .Nm bn_sqr_normal ,
74 .Nm bn_sqr_recursive ,
75 .Nm bn_expand ,
76 .Nm bn_wexpand ,
77 .Nm bn_expand2 ,
78 .Nm bn_fix_top ,
79 .Nm bn_check_top ,
80 .Nm bn_print ,
81 .Nm bn_dump ,
82 .Nm bn_set_max ,
83 .Nm bn_set_high ,
84 .Nm bn_set_low ,
85 .Nm mul ,
86 .Nm mul_add ,
87 .Nm sqr
88 .Nd BIGNUM library internal functions
89 .Sh SYNOPSIS
90 .In openssl/bn.h
91 .Ft BN_ULONG
92 .Fo bn_mul_words
93 .Fa "BN_ULONG *rp"
94 .Fa "BN_ULONG *ap"
95 .Fa "int num"
96 .Fa "BN_ULONG w"
97 .Fc
98 .Ft BN_ULONG
99 .Fo bn_mul_add_words
100 .Fa "BN_ULONG *rp"
101 .Fa "BN_ULONG *ap"
102 .Fa "int num"
103 .Fa "BN_ULONG w"
104 .Fc
105 .Ft void
106 .Fo bn_sqr_words
107 .Fa "BN_ULONG *rp"
108 .Fa "BN_ULONG *ap"
109 .Fa "int num"
110 .Fc
111 .Ft BN_ULONG
112 .Fo bn_div_words
113 .Fa "BN_ULONG h"
114 .Fa "BN_ULONG l"
115 .Fa "BN_ULONG d"
116 .Fc
117 .Ft BN_ULONG
118 .Fo bn_add_words
119 .Fa "BN_ULONG *rp"
120 .Fa "BN_ULONG *ap"
121 .Fa "BN_ULONG *bp"
122 .Fa "int num"
123 .Fc
124 .Ft BN_ULONG
125 .Fo bn_sub_words
126 .Fa "BN_ULONG *rp"
127 .Fa "BN_ULONG *ap"
128 .Fa "BN_ULONG *bp"
129 .Fa "int num"
130 .Fc
131 .Ft void
132 .Fo bn_mul_comba4
133 .Fa "BN_ULONG *r"
134 .Fa "BN_ULONG *a"
135 .Fa "BN_ULONG *b"
136 .Fc
137 .Ft void
138 .Fo bn_mul_comba8
139 .Fa "BN_ULONG *r"
140 .Fa "BN_ULONG *a"
141 .Fa "BN_ULONG *b"
142 .Fc
143 .Ft void
144 .Fo bn_sqr_comba4
145 .Fa "BN_ULONG *r"
146 .Fa "BN_ULONG *a"
147 .Fc
148 .Ft void
149 .Fo bn_sqr_comba8
150 .Fa "BN_ULONG *r"
151 .Fa "BN_ULONG *a"
152 .Fc
153 .Ft int
154 .Fo bn_cmp_words
155 .Fa "BN_ULONG *a"
156 .Fa "BN_ULONG *b"
157 .Fa "int n"
158 .Fc
159 .Ft void
160 .Fo bn_mul_normal
161 .Fa "BN_ULONG *r"
162 .Fa "BN_ULONG *a"
163 .Fa "int na"
164 .Fa "BN_ULONG *b"
165 .Fa "int nb"
166 .Fc
167 .Ft void
168 .Fo bn_mul_low_normal
169 .Fa "BN_ULONG *r"
170 .Fa "BN_ULONG *a"
171 .Fa "BN_ULONG *b"
172 .Fa "int n"
173 .Fc
174 .Ft void
175 .Fo bn_mul_recursive
176 .Fa "BN_ULONG *r"
177 .Fa "BN_ULONG *a"
178 .Fa "BN_ULONG *b"
179 .Fa "int n2"
180 .Fa "int dna"
181 .Fa "int dnb"
182 .Fa "BN_ULONG *tmp"
183 .Fc
184 .Ft void
185 .Fo bn_mul_part_recursive
186 .Fa "BN_ULONG *r"
187 .Fa "BN_ULONG *a"
188 .Fa "BN_ULONG *b"
189 .Fa "int n"
190 .Fa "int tna"
191 .Fa "int tnb"
192 .Fa "BN_ULONG *tmp"
193 .Fc
194 .Ft void
195 .Fo bn_mul_low_recursive
196 .Fa "BN_ULONG *r"
197 .Fa "BN_ULONG *a"
198 .Fa "BN_ULONG *b"
199 .Fa "int n2"
200 .Fa "BN_ULONG *tmp"
201 .Fc
202 .Ft void
203 .Fo bn_mul_high
204 .Fa "BN_ULONG *r"
205 .Fa "BN_ULONG *a"
206 .Fa "BN_ULONG *b"
207 .Fa "BN_ULONG *l"
208 .Fa "int n2"
209 .Fa "BN_ULONG *tmp"
210 .Fc
211 .Ft void
212 .Fo bn_sqr_normal
213 .Fa "BN_ULONG *r"
214 .Fa "BN_ULONG *a"
215 .Fa "int n"
216 .Fa "BN_ULONG *tmp"
217 .Fc
218 .Ft void
219 .Fo bn_sqr_recursive
220 .Fa "BN_ULONG *r"
221 .Fa "BN_ULONG *a"
222 .Fa "int n2"
223 .Fa "BN_ULONG *tmp"
224 .Fc
225 .Ft void
226 .Fo mul
227 .Fa "BN_ULONG r"
228 .Fa "BN_ULONG a"
229 .Fa "BN_ULONG w"
230 .Fa "BN_ULONG c"
231 .Fc
232 .Ft void
233 .Fo mul_add
234 .Fa "BN_ULONG r"
235 .Fa "BN_ULONG a"
236 .Fa "BN_ULONG w"
237 .Fa "BN_ULONG c"
238 .Fc
239 .Ft void
240 .Fo sqr
241 .Fa "BN_ULONG r0"
242 .Fa "BN_ULONG r1"
243 .Fa "BN_ULONG a"
244 .Fc
245 .Ft BIGNUM *
246 .Fo bn_expand
247 .Fa "BIGNUM *a"
248 .Fa "int bits"
249 .Fc
250 .Ft BIGNUM *
251 .Fo bn_wexpand
252 .Fa "BIGNUM *a"
253 .Fa "int n"
254 .Fc
255 .Ft BIGNUM *
256 .Fo bn_expand2
257 .Fa "BIGNUM *a"
258 .Fa "int n"
259 .Fc
260 .Ft void
261 .Fo bn_fix_top
262 .Fa "BIGNUM *a"
263 .Fc
264 .Ft void
265 .Fo bn_check_top
266 .Fa "BIGNUM *a"
267 .Fc
268 .Ft void
269 .Fo bn_print
270 .Fa "BIGNUM *a"
271 .Fc
272 .Ft void
273 .Fo bn_dump
274 .Fa "BN_ULONG *d"
275 .Fa "int n"
276 .Fc
277 .Ft void
278 .Fo bn_set_max
279 .Fa "BIGNUM *a"
280 .Fc
281 .Ft void
282 .Fo bn_set_high
283 .Fa "BIGNUM *r"
284 .Fa "BIGNUM *a"
285 .Fa "int n"
286 .Fc
287 .Ft void
288 .Fo bn_set_low
289 .Fa "BIGNUM *r"
290 .Fa "BIGNUM *a"
291 .Fa "int n"
292 .Fc
293 .Sh DESCRIPTION
294 This page documents the internal functions used by the OpenSSL
295 .Vt BIGNUM
296 implementation.
297 They are described here to facilitate debugging and extending the
298 library.
299 They are
300 .Em not
301 to be used by applications.
302 .Ss The BIGNUM structure
303 .Bd -literal
304 typedef struct bignum_st BIGNUM;
306 struct bignum_st {
307 BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */
308 int top; /* Index of last used d +1. */
309 /* The next are internal book keeping for bn_expand. */
310 int dmax; /* Size of the d array. */
311 int neg; /* one if the number is negative */
312 int flags;
313 };
314 .Ed
315 .Pp
316 The integer value is stored in
317 .Fa d ,
318 a
319 .Xr malloc 3 Ap ed
320 array of words
321 .Pq Vt BN_ULONG ,
322 least significant word first.
323 A
324 .Vt BN_ULONG
325 can be either 16, 32 or 64 bits in size, depending on the 'number of
326 bits'
327 .Pq Dv BITS2
328 specified in
329 .In openssl/bn.h .
330 .Pp
331 .Fa dmax
332 is the size of the
333 .Fa d
334 array that has been allocated.
335 .Fa top
336 is the number of words being used, so for a value of 4, bn.d[0]=4 and
337 bn.top=1.
338 .Fa neg
339 is 1 if the number is negative.
340 When a
341 .Vt BIGNUM
342 is 0, the
343 .Fa d
344 field can be
345 .Dv NULL
346 and
347 .Fa top
348 == 0.
349 .Pp
350 .Fa flags
351 is a bit field of flags which are defined in
352 .In openssl/bn.h .
353 The flags begin with
354 .Dv BN_FLG_ .
355 The macros
356 .Fn BN_set_flags b n
357 and
358 .Fn BN_get_flags b n
359 exist to enable or fetch flag(s)
360 .Fa n
361 from a
362 .Vt BIGNUM
363 structure
364 .Fa b .
365 .Pp
366 Various routines in this library require the use of temporary
367 .Vt BIGNUM
368 variables during their execution.
369 Since dynamic memory allocation to create
370 .Vt BIGNUM Ns s
371 is rather expensive when used in conjunction with repeated subroutine
372 calls, the
373 .Vt BN_CTX
374 structure is used.
375 This structure contains BN_CTX_NUM
376 .Vt BIGNUM Ns s ;
377 see
378 .Xr BN_CTX_start 3 .
379 .Ss Low level arithmetic operations
380 These functions are implemented in C and for several platforms in
381 assembly language:
382 .Pp
383 .Fn bn_mul_words rp ap num w
384 operates on the
385 .Fa num
386 word arrays
387 .Fa rp
388 and
389 .Fa ap .
390 It computes
391 .Fa ap
392 *
393 .Fa w ,
394 places the result in
395 .Fa rp ,
396 and returns the high word (carry).
397 .Pp
398 .Fn bn_mul_add_words rp ap num w
399 operates on the
400 .Fa num
401 word arrays
402 .Fa rp
403 and
404 .Fa ap .
405 It computes
406 .Fa ap
407 *
408 .Fa w
409 +
410 .Fa rp ,
411 places the result in
412 .Fa rp ,
413 and returns the high word (carry).
414 .Pp
415 .Fn bn_sqr_words rp ap num
416 operates on the
417 .Fa num
418 word array
419 .Fa ap
420 and the
421 .Pf 2* Fa num
422 word array
423 .Fa ap .
424 It computes
425 .Fa ap
426 *
427 .Fa ap
428 word-wise, and places the low and high bytes of the result in
429 .Fa rp .
430 .Pp
431 .Fn bn_div_words h l d
432 divides the two word number
433 .Pq Fa h , Fa l
434 by
435 .Fa d
436 and returns the result.
437 .Pp
438 .Fn bn_add_words rp ap bp num
439 operates on the
440 .Fa num
441 word arrays
442 .Fa ap ,
443 .Fa bp
444 and
445 .Fa rp .
446 It computes
447 .Fa ap
448 +
449 .Fa bp ,
450 places the result in
451 .Fa rp ,
452 and returns the high word (carry).
453 .Pp
454 .Fn bn_sub_words rp ap bp num
455 operates on the
456 .Fa num
457 word arrays
458 .Fa ap ,
459 .Fa bp
460 and
461 .Fa rp .
462 It computes
463 .Fa ap
464 -
465 .Fa bp ,
466 places the result in
467 .Fa rp ,
468 and returns the carry (1 if
469 .Fa bp
470 \(ra
471 .Fa ap ,
472 0 otherwise).
473 .Pp
474 .Fn bn_mul_comba4 r a b
475 operates on the 4 word arrays
476 .Fa a
477 and
478 .Fa b
479 and the 8-word array
480 .Fa r .
481 It computes
482 .Fa a Ns * Ns Fa b
483 and places the result in
484 .Fa r .
485 .Pp
486 .Fn bn_mul_comba8 r a b
487 operates on the 8-word arrays
488 .Fa a
489 and
490 .Fa b
491 and the 16-word array
492 .Fa r .
493 It computes
494 .Fa a Ns * Ns Fa b
495 and places the result in
496 .Fa r .
497 .Pp
498 .Fn bn_sqr_comba4 r a b
499 operates on the 4-word arrays
500 .Fa a
501 and
502 .Fa b
503 and the 8-word array
504 .Fa r .
505 .Pp
506 .Fn bn_sqr_comba8 r a b
507 operates on the 8-word arrays
508 .Fa a
509 and
510 .Fa b
511 and the 16 word array
512 .Fa r .
513 .Pp
514 The following functions are implemented in C:
515 .Pp
516 .Fn bn_cmp_words a b n
517 operates on the
518 .Fa n
519 word arrays
520 .Fa a
521 and
522 .Fa b .
523 It returns 1, 0 and -1 if
524 .Fa a
525 is greater than, equal and less than
526 .Fa b .
527 .Pp
528 .Fn bn_mul_normal r a na b nb
529 operates on the
530 .Fa na
531 word array
532 .Fa a ,
533 the
534 .Fa nb
535 word array
536 .Fa b
537 and the
538 .Fa na Ns + Ns Fa nb
539 word array
540 .Fa r .
541 It computes
542 .Fa a Ns * Ns Fa b
543 and places the result in
544 .Fa r .
545 .Pp
546 .Fn bn_mul_low_normal r a b n
547 operates on the
548 .Fa n
549 word arrays
550 .Fa r ,
551 .Fa a
552 and
553 .Fa b .
554 It computes the
555 .Fa n
556 low words of
557 .Fa a Ns * Ns Fa b
558 and places the result in
559 .Fa r .
560 .Pp
561 .Fn bn_mul_recursive r a b n2 dna dnb t
562 operates on the word arrays
563 .Fa a
564 and
565 .Fa b
566 of length
567 .Fa n2 Ns + Ns Fa dna
568 and
569 .Fa n2 Ns + Ns Fa dnb
570 .Pf ( Fa dna
571 and
572 .Fa dnb
573 are currently allowed to be 0 or negative) and the
574 .Pf 2* Fa n2
575 word arrays
576 .Fa r
577 and
578 .Sy t .
579 .Fa n2
580 must be a power of 2.
581 It computes
582 .Fa a Ns * Ns Fa b
583 and places the result in
584 .Fa r .
585 .Pp
586 .Fn bn_mul_part_recursive r a b n tna tnb tmp
587 operates on the word arrays
588 .Fa a
589 and
590 .Fa b
591 of length
592 .Fa n Ns + Ns Fa tna
593 and
594 .Fa n Ns + Ns Fa tnb
595 and the
596 .Pf 4* Fa n
597 word arrays
598 .Fa r
599 and
600 .Fa tmp .
601 .Pp
602 .Fn bn_mul_low_recursive r a b n2 tmp
603 operates on the
604 .Fa n2
605 word arrays
606 .Fa r
607 and
608 .Fa tmp
609 and the
610 .Fa n2 Ns /2
611 word arrays
612 .Fa a
613 and
614 .Fa b .
615 .Pp
616 .Fn bn_mul_high r a b l n2 tmp
617 operates on the
618 .Fa n2
619 word arrays
620 .Fa r ,
621 .Fa a ,
622 .Fa b
623 and
624 .Fa l
625 (?) and the
626 .Pf 3* Fa n2
627 word array
628 .Fa tmp .
629 .Pp
630 .Xr BN_mul 3
631 calls
632 .Fn bn_mul_normal ,
633 or an optimized implementation if the factors have the same size:
634 .Fn bn_mul_comba8
635 is used if they are 8 words long,
636 .Fn bn_mul_recursive
637 if they are larger than
638 .Dv BN_MULL_SIZE_NORMAL
639 and the size is an exact multiple of the word size, and
640 .Fn bn_mul_part_recursive
641 for others that are larger than
642 .Dv BN_MULL_SIZE_NORMAL .
643 .Pp
644 .Fn bn_sqr_normal r a n tmp
645 operates on the
646 .Fa n
647 word array
648 .Fa a
649 and the
650 .Pf 2* Fa n
651 word arrays
652 .Fa tmp
653 and
654 .Fa r .
655 .Pp
656 The implementations use the following macros which, depending on the
657 architecture, may use
658 .Vt long long
659 C operations or inline assembler.
660 They are defined in
661 .Pa bn_lcl.h .
662 .Pp
663 .Fn mul r a w c
664 computes
665 .Fa w Ns * Ns Fa a Ns + Ns Fa c
666 and places the low word of the result in
667 .Fa r
668 and the high word in
669 .Fa c .
670 .Pp
671 .Fn mul_add r a w c
672 computes
673 .Fa w Ns * Ns Fa a Ns + Ns Fa r Ns + Ns Fa c
674 and places the low word of the result in
675 .Fa r
676 and the high word in
677 .Fa c .
678 .Pp
679 .Fn sqr r0 r1 a
680 computes
681 .Fa a Ns * Ns Fa a
682 and places the low word of the result in
683 .Fa r0
684 and the high word in
685 .Fa r1 .
686 .Ss Size changes
687 .Fn bn_expand
688 ensures that
689 .Fa b
690 has enough space for a
691 .Fa bits
692 bit number.
693 .Fn bn_wexpand
694 ensures that
695 .Fa b
696 has enough space for an
697 .Fa n
698 word number.
699 If the number has to be expanded, both macros call
700 .Fn bn_expand2 ,
701 which allocates a new
702 .Fa d
703 array and copies the data.
704 They return
705 .Dv NULL
706 on error,
707 .Fa b
708 otherwise.
709 .Pp
710 The
711 .Fn bn_fix_top
712 macro reduces
713 .Fa a Ns -> Ns Fa top
714 to point to the most significant non-zero word plus one when
715 .Fa a
716 has shrunk.
717 .Ss Debugging
718 .Fn bn_check_top
719 verifies that
720 .Ql ((a)-\(ratop \(ra= 0 && (a)-\(ratop \(la= (a)-\(radmax) .
721 A violation will cause the program to abort.
722 .Pp
723 .Fn bn_print
724 prints
725 .Fa a
726 to
727 .Dv stderr .
728 .Fn bn_dump
729 prints
730 .Fa n
731 words at
732 .Fa d
733 (in reverse order, i.e.\&
734 most significant word first) to
735 .Dv stderr .
736 .Pp
737 .Fn bn_set_max
738 makes
739 .Fa a
740 a static number with a
741 .Fa dmax
742 of its current size.
743 This is used by
744 .Fn bn_set_low
745 and
746 .Fn bn_set_high
747 to make
748 .Fa r
749 a read-only
750 .Vt BIGNUM
751 that contains the
752 .Fa n
753 low or high words of
754 .Fa a .
755 .Pp
756 If
757 .Dv BN_DEBUG
758 is not defined,
759 .Fn bn_check_top ,
760 .Fn bn_print ,
761 .Fn bn_dump
762 and
763 .Fn bn_set_max
764 are defined as empty macros.
765 .Sh SEE ALSO
766 .Xr BN_new 3