diff options
author | Bodo Möller <bodo@openssl.org> | 2000-11-26 16:42:38 +0000 |
---|---|---|
committer | Bodo Möller <bodo@openssl.org> | 2000-11-26 16:42:38 +0000 |
commit | 78a0c1f18d5a1f0e51b7467ef7b153b8c29fbb03 (patch) | |
tree | 631b1606ee2f90a5fcaf2f141461113d30c7f5a8 /doc | |
parent | 6cc5e19d4710d7d3355bf6fa05c3d7269e48428f (diff) |
modular arithmetics
"make update"
Diffstat (limited to 'doc')
-rw-r--r-- | doc/crypto/BN_add.pod | 88 | ||||
-rw-r--r-- | doc/crypto/BN_mod_mul_montgomery.pod | 15 | ||||
-rw-r--r-- | doc/crypto/bn.pod | 14 |
3 files changed, 76 insertions, 41 deletions
diff --git a/doc/crypto/BN_add.pod b/doc/crypto/BN_add.pod index 0541d45643..4c8db25f70 100644 --- a/doc/crypto/BN_add.pod +++ b/doc/crypto/BN_add.pod @@ -2,8 +2,9 @@ =head1 NAME -BN_add, BN_sub, BN_mul, BN_div, BN_sqr, BN_mod, BN_mod_mul, BN_exp, -BN_mod_exp, BN_gcd - arithmetic operations on BIGNUMs +BN_add, BN_sub, BN_mul, BN_sqr, BN_div, BN_mod, BN_nnmod, BN_mod_add, +BN_mod_sub, BN_mod_mul, BN_mod_sqr, BN_exp, BN_mod_exp, BN_gcd - +arithmetic operations on BIGNUMs =head1 SYNOPSIS @@ -15,16 +16,26 @@ BN_mod_exp, BN_gcd - arithmetic operations on BIGNUMs int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); + int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx); + int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *a, const BIGNUM *d, BN_CTX *ctx); - int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx); - int BN_mod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); - int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + int BN_nnmod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); + + int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + BN_CTX *ctx); + + int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + BN_CTX *ctx); + + int BN_mod_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx); + int BN_mod_sqr(BIGNUM *r, BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); + int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, @@ -34,45 +45,58 @@ BN_mod_exp, BN_gcd - arithmetic operations on BIGNUMs =head1 DESCRIPTION -BN_add() adds B<a> and B<b> and places the result in B<r> (C<r=a+b>). -B<r> may be the same B<BIGNUM> as B<a> or B<b>. +BN_add() adds I<a> and I<b> and places the result in I<r> (C<r=a+b>). +I<r> may be the same B<BIGNUM> as I<a> or I<b>. -BN_sub() subtracts B<b> from B<a> and places the result in B<r> (C<r=a-b>). +BN_sub() subtracts I<b> from I<a> and places the result in I<r> (C<r=a-b>). -BN_mul() multiplies B<a> and B<b> and places the result in B<r> (C<r=a*b>). -B<r> may be the same B<BIGNUM> as B<a> or B<b>. +BN_mul() multiplies I<a> and I<b> and places the result in I<r> (C<r=a*b>). +I<r> may be the same B<BIGNUM> as I<a> or I<b>. For multiplication by powers of 2, use L<BN_lshift(3)|BN_lshift(3)>. -BN_div() divides B<a> by B<d> and places the result in B<dv> and the -remainder in B<rem> (C<dv=a/d, rem=a%d>). Either of B<dv> and B<rem> may -be NULL, in which case the respective value is not returned. +BN_sqr() takes the square of I<a> and places the result in I<r> +(C<r=a^2>). I<r> and I<a> may be the same B<BIGNUM>. +This function is faster than BN_mul(r,a,a). + +BN_div() divides I<a> by I<d> and places the result in I<dv> and the +remainder in I<rem> (C<dv=a/d, rem=a%d>). Either of I<dv> and I<rem> may +be B<NULL>, in which case the respective value is not returned. +The result is rounded towards zero; thus if I<a> is negative, the +remainder will be zero or negative. For division by powers of 2, use BN_rshift(3). -BN_sqr() takes the square of B<a> and places the result in B<r> -(C<r=a^2>). B<r> and B<a> may be the same B<BIGNUM>. -This function is faster than BN_mul(r,a,a). +BN_mod() corresponds to BN_div() with I<dv> set to B<NULL>. + +BN_nnmod() finds the non-negative remainder of I<a> divided by I<m>. + +BN_mod_add() adds I<a> to I<b> modulo I<m> and places the non-negative +result in I<r>. + +BN_mod_sub() substracts I<b> from I<a> modulo I<m> and places the +non-negative result in I<r>. -BN_mod() find the remainder of B<a> divided by B<m> and places it in -B<rem> (C<rem=a%m>). +BN_mod_mul() multiplies I<a> by I<b> and finds the non-negative +remainder respective to modulus I<m> (C<r=(a*b) mod m>). I<r> may be +the same B<BIGNUM> as I<a> or I<b>. For more efficient algorithms for +repeated computations using the same modulus, see +L<BN_mod_mul_montgomery(3)|BN_mod_mul_montgomery(3)> and +L<BN_mod_mul_reciprocal(3)|BN_mod_mul_reciprocal(3)>. -BN_mod_mul() multiplies B<a> by B<b> and finds the remainder when -divided by B<m> (C<r=(a*b)%m>). B<r> may be the same B<BIGNUM> as B<a> -or B<b>. For a more efficient algorithm, see -L<BN_mod_mul_montgomery(3)|BN_mod_mul_montgomery(3)>; for repeated -computations using the same modulus, see L<BN_mod_mul_reciprocal(3)|BN_mod_mul_reciprocal(3)>. +BN_mod_sqr() takes the square of I<a> modulo B<m> and places the +result in I<r>. -BN_exp() raises B<a> to the B<p>-th power and places the result in B<r> +BN_exp() raises I<a> to the I<p>-th power and places the result in I<r> (C<r=a^p>). This function is faster than repeated applications of BN_mul(). -BN_mod_exp() computes B<a> to the B<p>-th power modulo B<m> (C<r=a^p % +BN_mod_exp() computes I<a> to the I<p>-th power modulo I<m> (C<r=a^p % m>). This function uses less time and space than BN_exp(). -BN_gcd() computes the greatest common divisor of B<a> and B<b> and -places the result in B<r>. B<r> may be the same B<BIGNUM> as B<a> or -B<b>. +BN_gcd() computes the greatest common divisor of I<a> and I<b> and +places the result in I<r>. I<r> may be the same B<BIGNUM> as I<a> or +I<b>. -For all functions, B<ctx> is a previously allocated B<BN_CTX> used for +For all functions, I<ctx> is a previously allocated B<BN_CTX> used for temporary variables; see L<BN_CTX_new(3)|BN_CTX_new(3)>. Unless noted otherwise, the result B<BIGNUM> must be different from @@ -91,9 +115,11 @@ L<BN_add_word(3)|BN_add_word(3)>, L<BN_set_bit(3)|BN_set_bit(3)> =head1 HISTORY -BN_add(), BN_sub(), BN_div(), BN_sqr(), BN_mod(), BN_mod_mul(), +BN_add(), BN_sub(), BN_sqr(), BN_div(), BN_mod(), BN_mod_mul(), BN_mod_exp() and BN_gcd() are available in all versions of SSLeay and -OpenSSL. The B<ctx> argument to BN_mul() was added in SSLeay +OpenSSL. The I<ctx> argument to BN_mul() was added in SSLeay 0.9.1b. BN_exp() appeared in SSLeay 0.9.0. +BN_nnmod(), BN_mod_add(), BN_mod_sub(), and BN_mod_sqr() were added in +OpenSSL 0.9.7. =cut diff --git a/doc/crypto/BN_mod_mul_montgomery.pod b/doc/crypto/BN_mod_mul_montgomery.pod index 0b8ab512df..6452470076 100644 --- a/doc/crypto/BN_mod_mul_montgomery.pod +++ b/doc/crypto/BN_mod_mul_montgomery.pod @@ -36,22 +36,23 @@ using the same modulus. BN_MONT_CTX_new() allocates and initializes a B<BN_MONT_CTX> structure. BN_MONT_CTX_init() initializes an existing uninitialized B<BN_MONT_CTX>. -BN_MONT_CTX_set() sets up the B<mont> structure from the modulus B<m> +BN_MONT_CTX_set() sets up the I<mont> structure from the modulus I<m> by precomputing its inverse and a value R. -BN_MONT_CTX_copy() copies the B<BN_MONT_CTX> B<from> to B<to>. +BN_MONT_CTX_copy() copies the B<BN_MONT_CTX> I<from> to I<to>. BN_MONT_CTX_free() frees the components of the B<BN_MONT_CTX>, and, if it was created by BN_MONT_CTX_new(), also the structure itself. -BN_mod_mul_montgomery() computes Mont(B<a>,B<b>):=B<a>*B<b>*R^-1 and places -the result in B<r>. +BN_mod_mul_montgomery() computes Mont(I<a>,I<b>):=I<a>*I<b>*R^-1 and places +the result in I<r>. -BN_from_montgomery() performs the Montgomery reduction B<r> = B<a>*R^-1. +BN_from_montgomery() performs the Montgomery reduction I<r> = I<a>*R^-1. -BN_to_montgomery() computes Mont(B<a>,R^2), i.e. B<a>*R. +BN_to_montgomery() computes Mont(I<a>,R^2), i.e. I<a>*R. +Note that I<a> must be non-negative and smaller than the modulus. -For all functions, B<ctx> is a previously allocated B<BN_CTX> used for +For all functions, I<ctx> is a previously allocated B<BN_CTX> used for temporary variables. The B<BN_MONT_CTX> structure is defined as follows: diff --git a/doc/crypto/bn.pod b/doc/crypto/bn.pod index 1504a1c92d..224dfe166a 100644 --- a/doc/crypto/bn.pod +++ b/doc/crypto/bn.pod @@ -21,19 +21,27 @@ bn - multiprecision integer arithmetics BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b); BIGNUM *BN_dup(const BIGNUM *a); + BIGNUM *BN_swap(BIGNUM *a, BIGNUM *b); + int BN_num_bytes(const BIGNUM *a); int BN_num_bits(const BIGNUM *a); int BN_num_bits_word(BN_ULONG w); - int BN_add(BIGNUM *r, BIGNUM *a, BIGNUM *b); + int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); + int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx); int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *a, const BIGNUM *d, BN_CTX *ctx); - int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx); int BN_mod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); + int BN_nnmod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); + int BN_mod_add(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + BN_CTX *ctx); + int BN_mod_sub(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + BN_CTX *ctx); int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx); + int BN_mod_sqr(BIGNUM *ret, BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx); @@ -137,7 +145,7 @@ of B<BIGNUM>s to external formats is described in L<BN_bn2bin(3)|BN_bn2bin(3)>. L<bn_internal(3)|bn_internal(3)>, L<dh(3)|dh(3)>, L<err(3)|err(3)>, L<rand(3)|rand(3)>, L<rsa(3)|rsa(3)>, L<BN_new(3)|BN_new(3)>, L<BN_CTX_new(3)|BN_CTX_new(3)>, -L<BN_copy(3)|BN_copy(3)>, L<BN_num_bytes(3)|BN_num_bytes(3)>, +L<BN_copy(3)|BN_copy(3)>, L<BN_swap(3)|BN_swap(3)>, L<BN_num_bytes(3)|BN_num_bytes(3)>, L<BN_add(3)|BN_add(3)>, L<BN_add_word(3)|BN_add_word(3)>, L<BN_cmp(3)|BN_cmp(3)>, L<BN_zero(3)|BN_zero(3)>, L<BN_rand(3)|BN_rand(3)>, L<BN_generate_prime(3)|BN_generate_prime(3)>, L<BN_set_bit(3)|BN_set_bit(3)>, |