lib/libcrypto/man/BN_mod_mul_montgomery.3

   1 .\"     $OpenBSD: BN_mod_mul_montgomery.3,v 1.7 2017/01/30 07:51:27 jmc 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: January 30 2017 $
  52 .Dt BN_MOD_MUL_MONTGOMERY 3
  53 .Os
  54 .Sh NAME
  55 .Nm BN_MONT_CTX_new ,
  56 .Nm BN_MONT_CTX_init ,
  57 .Nm BN_MONT_CTX_free ,
  58 .Nm BN_MONT_CTX_set ,
  59 .Nm BN_MONT_CTX_copy ,
  60 .Nm BN_mod_mul_montgomery ,
  61 .Nm BN_from_montgomery ,
  62 .Nm BN_to_montgomery
  63 .Nd Montgomery multiplication
  64 .Sh SYNOPSIS
  65 .In openssl/bn.h
  66 .Ft BN_MONT_CTX *
  67 .Fo BN_MONT_CTX_new
  68 .Fa void
  69 .Fc
  70 .Ft void
  71 .Fo BN_MONT_CTX_init
  72 .Fa "BN_MONT_CTX *ctx"
  73 .Fc
  74 .Ft void
  75 .Fo BN_MONT_CTX_free
  76 .Fa "BN_MONT_CTX *mont"
  77 .Fc
  78 .Ft int
  79 .Fo BN_MONT_CTX_set
  80 .Fa "BN_MONT_CTX *mont"
  81 .Fa "const BIGNUM *m"
  82 .Fa "BN_CTX *ctx"
  83 .Fc
  84 .Ft BN_MONT_CTX *
  85 .Fo BN_MONT_CTX_copy
  86 .Fa "BN_MONT_CTX *to"
  87 .Fa "BN_MONT_CTX *from"
  88 .Fc
  89 .Ft int
  90 .Fo BN_mod_mul_montgomery
  91 .Fa "BIGNUM *r"
  92 .Fa "BIGNUM *a"
  93 .Fa "BIGNUM *b"
  94 .Fa "BN_MONT_CTX *mont"
  95 .Fa "BN_CTX *ctx"
  96 .Fc
  97 .Ft int
  98 .Fo BN_from_montgomery
  99 .Fa "BIGNUM *r"
 100 .Fa "BIGNUM *a"
 101 .Fa "BN_MONT_CTX *mont"
 102 .Fa "BN_CTX *ctx"
 103 .Fc
 104 .Ft int
 105 .Fo BN_to_montgomery
 106 .Fa "BIGNUM *r"
 107 .Fa "BIGNUM *a"
 108 .Fa "BN_MONT_CTX *mont"
 109 .Fa "BN_CTX *ctx"
 110 .Fc
 111 .Sh DESCRIPTION
 112 These functions implement Montgomery multiplication.
 113 They are used automatically when
 114 .Xr BN_mod_exp 3
 115 is called with suitable input, but they may be useful when several
 116 operations are to be performed using the same modulus.
 117 .Pp
 118 .Fn BN_MONT_CTX_new
 119 allocates and initializes a
 120 .Vt BN_MONT_CTX
 121 structure.
 122 .Pp
 123 .Fn BN_MONT_CTX_init
 124 initializes an existing uninitialized
 125 .Vt BN_MONT_CTX .
 126 It is deprecated and dangerous: see
 127 .Sx CAVEATS .
 128 .Pp
 129 .Fn BN_MONT_CTX_set
 130 sets up the
 131 .Fa mont
 132 structure from the modulus
 133 .Fa m
 134 by precomputing its inverse and a value R.
 135 .Pp
 136 .Fn BN_MONT_CTX_copy
 137 copies the
 138 .Vt BN_MONT_CTX
 139 .Fa from
 140 to
 141 .Fa to .
 142 .Pp
 143 .Fn BN_MONT_CTX_free
 144 frees the components of the
 145 .Vt BN_MONT_CTX ,
 146 and, if it was created by
 147 .Fn BN_MONT_CTX_new ,
 148 also the structure itself.
 149 If
 150 .Fa mont
 151 is a
 152 .Dv NULL
 153 pointer, no action occurs.
 154 .Pp
 155 .Fn BN_mod_mul_montgomery
 156 computes
 157 .Pp
 158 .D1 Mont Ns Po Fa a , Fa b Pc := Fa a No * Fa b No * R^-1
 159 .Pp
 160 and places the result in
 161 .Fa r .
 162 .Pp
 163 .Fn BN_from_montgomery
 164 performs the Montgomery reduction
 165 .Pp
 166 .D1 Fa r No = Fa a No * R^-1
 167 .Pp
 168 .Fn BN_to_montgomery
 169 computes
 170 .Pp
 171 .D1 Mont Ns Po Fa a , No R^2 Pc = Fa a No * R
 172 .Pp
 173 Note that
 174 .Fa a
 175 must be non-negative and smaller than the modulus.
 176 .Pp
 177 For all functions,
 178 .Fa ctx
 179 is a previously allocated
 180 .Vt BN_CTX
 181 used for temporary variables.
 182 .Pp
 183 The
 184 .Vt BN_MONT_CTX
 185 structure is defined as follows:
 186 .Bd -literal
 187 typedef struct bn_mont_ctx_st {
 188         int ri;         /* number of bits in R */
 189         BIGNUM RR;      /* R^2 (used to convert to Montgomery form) */
 190         BIGNUM N;       /* The modulus */
 191         BIGNUM Ni;      /* R*(1/R mod N) - N*Ni = 1
 192                          * (Ni is only stored for bignum algorithm) */
 193         BN_ULONG n0;    /* least significant word of Ni */
 194         int flags;
 195 } BN_MONT_CTX;
 196 .Ed
 197 .Pp
 198 .Fn BN_to_montgomery
 199 is a macro.
 200 .Pp
 201 .Sy Warning :
 202 The inputs must be reduced modulo
 203 .Fa m ,
 204 otherwise the result will be outside the expected range.
 205 .Sh RETURN VALUES
 206 .Fn BN_MONT_CTX_new
 207 returns the newly allocated
 208 .Vt BN_MONT_CTX
 209 or
 210 .Dv NULL
 211 on error.
 212 .Pp
 213 For the other functions, 1 is returned for success or 0 on error.
 214 The error codes can be obtained by
 215 .Xr ERR_get_error 3 .
 216 .Sh SEE ALSO
 217 .Xr BN_add 3 ,
 218 .Xr BN_CTX_new 3 ,
 219 .Xr BN_new 3
 220 .Sh HISTORY
 221 .Fn BN_MONT_CTX_new ,
 222 .Fn BN_MONT_CTX_free ,
 223 .Fn BN_MONT_CTX_set ,
 224 .Fn BN_mod_mul_montgomery ,
 225 .Fn BN_from_montgomery
 226 and
 227 .Fn BN_to_montgomery
 228 are available in all versions of SSLeay and OpenSSL.
 229 .Pp
 230 .Fn BN_MONT_CTX_init
 231 and
 232 .Fn BN_MONT_CTX_copy
 233 were added in SSLeay 0.9.1b.
 234 .Sh CAVEATS
 235 .Fn BN_MONT_CTX_init
 236 must not be called on a context that was used previously, or
 237 memory used by the embedded
 238 .Vt BIGNUM
 239 structures is leaked immediately.
 240 Besides, it must not be called on a context created with
 241 .Fn BN_MONT_CTX_new ,
 242 or the context itself will likely be leaked later.
 243 It can only be used on a static
 244 .Vt BN_MONT_CTX
 245 structure, on one located on the stack, or on one
 246 .Xr malloc 3 Ap ed
 247 manually, but all these options are discouraged because they
 248 will no longer work once
 249 .Vt BN_MONT_CTX
 250 is made opaque.