openssl/crypto/bn

=pod

=head1 NAME

bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words,
bn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8,
bn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal,
bn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive,
bn_mul_low_recursive, bn_sqr_normal, bn_sqr_recursive,
bn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top,
bn_print, bn_dump, bn_set_max, bn_set_high, bn_set_low - BIGNUM
library internal functions

=head1 SYNOPSIS

#include

BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num,
BN_ULONG w);
void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num);
BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
int num);
BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
int num);

void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a);
void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a);

int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n);

void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b,
int nb);
void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
int dna, int dnb, BN_ULONG *tmp);
void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
int n, int tna, int tnb, BN_ULONG *tmp);
void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
int n2, BN_ULONG *tmp);

void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp);
void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp);

void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a);

BIGNUM *bn_expand(BIGNUM *a, int bits);
BIGNUM *bn_wexpand(BIGNUM *a, int n);
BIGNUM *bn_expand2(BIGNUM *a, int n);
void bn_fix_top(BIGNUM *a);

void bn_check_top(BIGNUM *a);
void bn_print(BIGNUM *a);
void bn_dump(BN_ULONG *d, int n);
void bn_set_max(BIGNUM *a);
void bn_set_high(BIGNUM *r, BIGNUM *a, int n);
void bn_set_low(BIGNUM *r, BIGNUM *a, int n);

=head1 DESCRIPTION

This page documents the internal functions used by the OpenSSL
B implementation. They are described here to facilitate
debugging and extending the library. They are I to be used by
applications.

=head2 The BIGNUM structure

typedef struct bignum_st BIGNUM;

struct bignum_st
{
BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */
int top; /* Index of last used d +1. */
/* The next are internal book keeping for bn_expand. */
int dmax; /* Size of the d array. */
int neg; /* one if the number is negative */
int flags;
};


The integer value is stored in B, a malloc()ed array of words (B),
least significant word first. A B can be either 16, 32 or 64 bits
in size, depending on the 'number of bits' (B) specified in
C.

B is the size of the B array that has been allocated. B
is the number of words being used, so for a value of 4, bn.d[0]=4 and
bn.top=1. B is 1 if the number is negative. When a B is
B<0>, the B field can be B and B == B<0>.

B is a bit field of flags which are defined in C. The
flags begin with B. The macros BN_set_flags(b, n) and
BN_get_flags(b, n) exist to enable or fetch flag(s) B from B
structure B.

Various routines in this library require the use of temporary
B variables during their execution. Since dynamic memory
allocation to create Bs is rather expensive when used in
conjunction with repeated subroutine calls, the B structure is
used. This structure contains B Bs, see
L.

=head2 Low-level arithmetic operations

These functions are implemented in C and for several platforms in
assembly language:

bn_mul_words(B, B, B, B) operates on the B word
arrays B and B. It computes B * B, places the result
in B, and returns the high word (carry).

bn_mul_add_words(B, B, B, B) operates on the B
word arrays B and B. It computes B * B + B, places
the result in B, and returns the high word (carry).

bn_sqr_words(B, B, B) operates on the B word array
B and the 2*B word array B. It computes B * B
word-wise, and places the low and high bytes of the result in B.

bn_div_words(B, B, B) divides the two word number (B, B)
by B and returns the result.

bn_add_words(B, B, B, B) operates on the B word
arrays B, B and B. It computes B + B, places the
result in B, and returns the high word (carry).

bn_sub_words(B, B, B, B) operates on the B word
arrays B, B and B. It computes B - B, places the
result in B, and returns the carry (1 if B E B, 0
otherwise).

bn_mul_comba4(B, B, B) operates on the 4 word arrays B and
B and the 8 word array B. It computes B*B and places the
result in B.

bn_mul_comba8(B, B, B) operates on the 8 word arrays B and
B and the 16 word array B. It computes B*B and places the
result in B.

bn_sqr_comba4(B, B, B) operates on the 4 word arrays B and
B and the 8 word array B.

bn_sqr_comba8(B, B, B) operates on the 8 word arrays B and
B and the 16 word array B.

The following functions are implemented in C:

bn_cmp_words(B, B, B) operates on the B word arrays B
and B. It returns 1, 0 and -1 if B is greater than, equal and
less than B.

bn_mul_normal(B, B, B, B, B) operates on the B
word array B, the B word array B and the B+B word
array B. It computes B*B and places the result in B.

bn_mul_low_normal(B, B, B, B) operates on the B word
arrays B, B and B. It computes the B low words of
B*B and places the result in B.

bn_mul_recursive(B, B, B, B, B, B, B) operates
on the word arrays B and B of length B+B and B+B
(B and B are currently allowed to be 0 or negative) and the 2*B
word arrays B and B. B must be a power of 2. It computes
B*B and places the result in B.

bn_mul_part_recursive(B, B, B, B, B, B, B)
operates on the word arrays B and B of length B+B and
B+B and the 4*B word arrays B and B.

bn_mul_low_recursive(B, B, B, B, B) operates on the
B word arrays B and B and the B/2 word arrays B
and B.

BN_mul() calls bn_mul_normal(), or an optimized implementation if the
factors have the same size: bn_mul_comba8() is used if they are 8
words long, bn_mul_recursive() if they are larger than
B and the size is an exact multiple of the word
size, and bn_mul_part_recursive() for others that are larger than
B.

bn_sqr_normal(B, B, B, B) operates on the B word array
B and the 2*B word arrays B and B.

The implementations use the following macros which, depending on the
architecture, may use "long long" C operations or inline assembler.
They are defined in C.

mul(B, B, B, B) computes B*B+B and places the
low word of the result in B and the high word in B.

mul_add(B, B, B, B) computes B*B+B+B and
places the low word of the result in B and the high word in B.

sqr(B, B, B) computes B*B and places the low word
of the result in B and the high word in B.

=head2 Size changes

bn_expand() ensures that B has enough space for a B bit
number. bn_wexpand() ensures that B has enough space for an
B word number. If the number has to be expanded, both macros
call bn_expand2(), which allocates a new B array and copies the
data. They return B on error, B otherwise.

The bn_fix_top() macro reduces Btop> to point to the most
significant non-zero word plus one when B has shrunk.

=head2 Debugging

bn_check_top() verifies that C<((a)-Etop E= 0 && (a)-Etop
E= (a)-Edmax)>. A violation will cause the program to abort.

bn_print() prints B to stderr. bn_dump() prints B words at B
(in reverse order, i.e. most significant word first) to stderr.

bn_set_max() makes B a static number with a B of its current size.
This is used by bn_set_low() and bn_set_high() to make B a read-only
B that contains the B low or high words of B.

If B is not defined, bn_check_top(), bn_print(), bn_dump()
and bn_set_max() are defined as empty macros.

=head1 SEE ALSO

L

=head1 COPYRIGHT

Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.

Licensed under the OpenSSL license (the "License"). You may not use
this file except in compliance with the License. You can obtain a copy
in the file LICENSE in the source distribution or at
L.

=cut