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
4 .\" This file was written by Ulf Moeller <ulf@openssl.org>.
5 .\" Copyright (c) 2000 The OpenSSL Project. All rights reserved.
7 .\" Redistribution and use in source and binary forms, with or without
8 .\" modification, are permitted provided that the following conditions
11 .\" 1. Redistributions of source code must retain the above copyright
12 .\" notice, this list of conditions and the following disclaimer.
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
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/)"
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.
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.
33 .\" 6. Redistributions of any form whatsoever must retain the following
35 .\" "This product includes software developed by the OpenSSL Project
36 .\" for use in the OpenSSL Toolkit (http://www.openssl.org/)"
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.
51 .Dd $Mdocdate: January 30 2017 $
52 .Dt BN_MOD_MUL_MONTGOMERY 3
56 .Nm BN_MONT_CTX_init ,
57 .Nm BN_MONT_CTX_free ,
59 .Nm BN_MONT_CTX_copy ,
60 .Nm BN_mod_mul_montgomery ,
61 .Nm BN_from_montgomery ,
63 .Nd Montgomery multiplication
72 .Fa "BN_MONT_CTX *ctx"
76 .Fa "BN_MONT_CTX *mont"
80 .Fa "BN_MONT_CTX *mont"
87 .Fa "BN_MONT_CTX *from"
90 .Fo BN_mod_mul_montgomery
94 .Fa "BN_MONT_CTX *mont"
98 .Fo BN_from_montgomery
101 .Fa "BN_MONT_CTX *mont"
108 .Fa "BN_MONT_CTX *mont"
112 These functions implement Montgomery multiplication.
113 They are used automatically when
115 is called with suitable input, but they may be useful when several
116 operations are to be performed using the same modulus.
119 allocates and initializes a
124 initializes an existing uninitialized
126 It is deprecated and dangerous: see
132 structure from the modulus
134 by precomputing its inverse and a value R.
144 frees the components of the
146 and, if it was created by
147 .Fn BN_MONT_CTX_new ,
148 also the structure itself.
153 pointer, no action occurs.
155 .Fn BN_mod_mul_montgomery
158 .D1 Mont Ns Po Fa a , Fa b Pc := Fa a No * Fa b No * R^-1
160 and places the result in
163 .Fn BN_from_montgomery
164 performs the Montgomery reduction
166 .D1 Fa r No = Fa a No * R^-1
171 .D1 Mont Ns Po Fa a , No R^2 Pc = Fa a No * R
175 must be non-negative and smaller than the modulus.
179 is a previously allocated
181 used for temporary variables.
185 structure is defined as follows:
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 */
202 The inputs must be reduced modulo
204 otherwise the result will be outside the expected range.
207 returns the newly allocated
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 .
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
228 are available in all versions of SSLeay and OpenSSL.
233 were added in SSLeay 0.9.1b.
236 must not be called on a context that was used previously, or
237 memory used by the embedded
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
245 structure, on one located on the stack, or on one
247 manually, but all these options are discouraged because they
248 will no longer work once