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