lib/libcrypto/man/BN_mod_mul_reciprocal.3

   1 .\"     $OpenBSD: BN_mod_mul_reciprocal.3,v 1.10 2018/03/27 17:35:50 schwarze Exp $
   2 .\"     OpenSSL 6859cf74 Sep 25 13:33:28 2002 +0000
   3 .\"
   4 .\" This file was written by Ulf Moeller <ulf@openssl.org>.
   5 .\" Copyright (c) 2000 The OpenSSL Project.  All rights reserved.
   6 .\"
   7 .\" Redistribution and use in source and binary forms, with or without
   8 .\" modification, are permitted provided that the following conditions
   9 .\" are met:
  10 .\"
  11 .\" 1. Redistributions of source code must retain the above copyright
  12 .\"    notice, this list of conditions and the following disclaimer.
  13 .\"
  14 .\" 2. Redistributions in binary form must reproduce the above copyright
  15 .\"    notice, this list of conditions and the following disclaimer in
  16 .\"    the documentation and/or other materials provided with the
  17 .\"    distribution.
  18 .\"
  19 .\" 3. All advertising materials mentioning features or use of this
  20 .\"    software must display the following acknowledgment:
  21 .\"    "This product includes software developed by the OpenSSL Project
  22 .\"    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  23 .\"
  24 .\" 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  25 .\"    endorse or promote products derived from this software without
  26 .\"    prior written permission. For written permission, please contact
  27 .\"    openssl-core@openssl.org.
  28 .\"
  29 .\" 5. Products derived from this software may not be called "OpenSSL"
  30 .\"    nor may "OpenSSL" appear in their names without prior written
  31 .\"    permission of the OpenSSL Project.
  32 .\"
  33 .\" 6. Redistributions of any form whatsoever must retain the following
  34 .\"    acknowledgment:
  35 .\"    "This product includes software developed by the OpenSSL Project
  36 .\"    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  37 .\"
  38 .\" THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  39 .\" EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  40 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  41 .\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  42 .\" ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  43 .\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  44 .\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  45 .\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  46 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  47 .\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  48 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  49 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
  50 .\"
  51 .Dd $Mdocdate: March 27 2018 $
  52 .Dt BN_MOD_MUL_RECIPROCAL 3
  53 .Os
  54 .Sh NAME
  55 .Nm BN_mod_mul_reciprocal ,
  56 .Nm BN_RECP_CTX_new ,
  57 .Nm BN_RECP_CTX_init ,
  58 .Nm BN_RECP_CTX_free ,
  59 .Nm BN_RECP_CTX_set ,
  60 .Nm BN_div_recp
  61 .Nd modular multiplication using reciprocal
  62 .Sh SYNOPSIS
  63 .In openssl/bn.h
  64 .Ft int
  65 .Fo BN_mod_mul_reciprocal
  66 .Fa "BIGNUM *r"
  67 .Fa "BIGNUM *a"
  68 .Fa "BIGNUM *b"
  69 .Fa "BN_RECP_CTX *recp"
  70 .Fa "BN_CTX *ctx"
  71 .Fc
  72 .Ft BN_RECP_CTX *
  73 .Fo BN_RECP_CTX_new
  74 .Fa void
  75 .Fc
  76 .Ft void
  77 .Fo BN_RECP_CTX_init
  78 .Fa "BN_RECP_CTX *recp"
  79 .Fc
  80 .Ft void
  81 .Fo BN_RECP_CTX_free
  82 .Fa "BN_RECP_CTX *recp"
  83 .Fc
  84 .Ft int
  85 .Fo BN_RECP_CTX_set
  86 .Fa "BN_RECP_CTX *recp"
  87 .Fa "const BIGNUM *m"
  88 .Fa "BN_CTX *ctx"
  89 .Fc
  90 .Ft int
  91 .Fo BN_div_recp
  92 .Fa "BIGNUM *dv"
  93 .Fa "BIGNUM *rem"
  94 .Fa "BIGNUM *a"
  95 .Fa "BN_RECP_CTX *recp"
  96 .Fa "BN_CTX *ctx"
  97 .Fc
  98 .Sh DESCRIPTION
  99 .Fn BN_mod_mul_reciprocal
 100 can be used to perform an efficient
 101 .Xr BN_mod_mul 3
 102 operation when the operation will be performed repeatedly with the same
 103 modulus.
 104 It computes
 105 .Fa r Ns =( Ns Fa a Ns * Ns Fa b Ns )% Ns Fa m
 106 using
 107 .Fa recp Ns =1/ Ns Fa m ,
 108 which is set as described below.
 109 .Fa ctx
 110 is a previously allocated
 111 .Vt BN_CTX
 112 used for temporary variables.
 113 .Pp
 114 .Fn BN_RECP_CTX_new
 115 allocates and initializes a
 116 .Vt BN_RECP_CTX
 117 structure.
 118 .Pp
 119 .Fn BN_RECP_CTX_init
 120 initializes an existing uninitialized
 121 .Vt BN_RECP_CTX .
 122 It is deprecated and dangerous: see
 123 .Sx CAVEATS .
 124 .Pp
 125 .Fn BN_RECP_CTX_free
 126 frees the components of the
 127 .Vt BN_RECP_CTX ,
 128 and, if it was created by
 129 .Fn BN_RECP_CTX_new ,
 130 also the structure itself.
 131 If
 132 .Fa recp
 133 is a
 134 .Dv NULL
 135 pointer, no action occurs.
 136 .Pp
 137 .Fn BN_RECP_CTX_set
 138 stores
 139 .Fa m
 140 in
 141 .Fa recp
 142 and sets it up for computing
 143 .Pf 1/ Fa m
 144 and shifting it left by
 145 .Fn BN_num_bits m Ns +1
 146 to make it an integer.
 147 The result and the number of bits it was shifted left will later be
 148 stored in
 149 .Fa recp .
 150 .Pp
 151 .Fn BN_div_recp
 152 divides
 153 .Fa a
 154 by
 155 .Fa m
 156 using
 157 .Fa recp .
 158 It places the quotient in
 159 .Fa dv
 160 and the remainder in
 161 .Fa rem .
 162 .Pp
 163 The
 164 .Vt BN_RECP_CTX
 165 structure is defined as follows:
 166 .Bd -literal
 167 typedef struct bn_recp_ctx_st {
 168         BIGNUM N;       /* the divisor */
 169         BIGNUM Nr;      /* the reciprocal */
 170         int num_bits;
 171         int shift;
 172         int flags;
 173 } BN_RECP_CTX;
 174 .Ed
 175 .Pp
 176 It cannot be shared between threads.
 177 .Sh RETURN VALUES
 178 .Fn BN_RECP_CTX_new
 179 returns the newly allocated
 180 .Vt BN_RECP_CTX
 181 or
 182 .Dv NULL
 183 on error.
 184 .Pp
 185 For the other functions, 1 is returned for success or 0 on error.
 186 The error codes can be obtained by
 187 .Xr ERR_get_error 3 .
 188 .Sh SEE ALSO
 189 .Xr BN_add 3 ,
 190 .Xr BN_CTX_new 3 ,
 191 .Xr BN_new 3
 192 .Sh HISTORY
 193 .Fn BN_mod_mul_reciprocal
 194 first appeared in SSLeay 0.5.1 and has been available since
 195 .Ox 2.4 .
 196 .Pp
 197 .Vt BN_RECP_CTX
 198 was added in SSLeay 0.9.0.
 199 Before that, a function
 200 .Fn BN_reciprocal
 201 was used instead, and the
 202 .Fn BN_mod_mul_reciprocal
 203 arguments were different.
 204 .Pp
 205 .Fn BN_RECP_CTX_new ,
 206 .Fn BN_RECP_CTX_init ,
 207 .Fn BN_RECP_CTX_free ,
 208 .Fn BN_RECP_CTX_set ,
 209 and
 210 .Fn BN_div_recp
 211 first appeared in SSLeay 0.9.1 and have been available since
 212 .Ox 2.6 .
 213 .Sh CAVEATS
 214 .Fn BN_RECP_CTX_init
 215 must not be called on a context that was used previously, or
 216 memory used by the embedded
 217 .Vt BIGNUM
 218 structures is leaked immediately.
 219 Besides, it must not be called on a context created with
 220 .Fn BN_RECP_CTX_new ,
 221 or the context itself will likely be leaked later.
 222 It can only be used on a static
 223 .Vt BN_RECP_CTX
 224 structure, on one located on the stack, or on one
 225 .Xr malloc 3 Ap ed
 226 manually, but all these options are discouraged because they
 227 will no longer work once
 228 .Vt BN_RECP_CTX
 229 is made opaque.