1.\" $OpenBSD: BN_mod_mul_montgomery.3,v 1.14 2021/12/21 11:14:07 schwarze Exp $ 2.\" full merge up to: OpenSSL 6859cf74 Sep 25 13:33:28 2002 +0000 3.\" selective merge up to: OpenSSL 24a535ea Sep 22 13:14:20 2020 +0100 4.\" 5.\" This file is a derived work. 6.\" The changes are covered by the following Copyright and license: 7.\" 8.\" Copyright (c) 2021 Ingo Schwarze <schwarze@openbsd.org> 9.\" 10.\" Permission to use, copy, modify, and distribute this software for any 11.\" purpose with or without fee is hereby granted, provided that the above 12.\" copyright notice and this permission notice appear in all copies. 13.\" 14.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 15.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 16.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 17.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 18.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 19.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 20.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 21.\" 22.\" The original file was written by Ulf Moeller <ulf@openssl.org>. 23.\" Copyright (c) 2000 The OpenSSL Project. All rights reserved. 24.\" 25.\" Redistribution and use in source and binary forms, with or without 26.\" modification, are permitted provided that the following conditions 27.\" are met: 28.\" 29.\" 1. Redistributions of source code must retain the above copyright 30.\" notice, this list of conditions and the following disclaimer. 31.\" 32.\" 2. Redistributions in binary form must reproduce the above copyright 33.\" notice, this list of conditions and the following disclaimer in 34.\" the documentation and/or other materials provided with the 35.\" distribution. 36.\" 37.\" 3. All advertising materials mentioning features or use of this 38.\" software must display the following acknowledgment: 39.\" "This product includes software developed by the OpenSSL Project 40.\" for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 41.\" 42.\" 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 43.\" endorse or promote products derived from this software without 44.\" prior written permission. For written permission, please contact 45.\" openssl-core@openssl.org. 46.\" 47.\" 5. Products derived from this software may not be called "OpenSSL" 48.\" nor may "OpenSSL" appear in their names without prior written 49.\" permission of the OpenSSL Project. 50.\" 51.\" 6. Redistributions of any form whatsoever must retain the following 52.\" acknowledgment: 53.\" "This product includes software developed by the OpenSSL Project 54.\" for use in the OpenSSL Toolkit (http://www.openssl.org/)" 55.\" 56.\" THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 57.\" EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 58.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 59.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 60.\" ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 61.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 62.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 63.\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 64.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 65.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 66.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 67.\" OF THE POSSIBILITY OF SUCH DAMAGE. 68.\" 69.Dd $Mdocdate: December 21 2021 $ 70.Dt BN_MOD_MUL_MONTGOMERY 3 71.Os 72.Sh NAME 73.Nm BN_MONT_CTX_new , 74.Nm BN_MONT_CTX_init , 75.Nm BN_MONT_CTX_free , 76.Nm BN_MONT_CTX_set , 77.Nm BN_MONT_CTX_set_locked , 78.Nm BN_MONT_CTX_copy , 79.Nm BN_mod_mul_montgomery , 80.Nm BN_from_montgomery , 81.Nm BN_to_montgomery 82.Nd Montgomery multiplication 83.Sh SYNOPSIS 84.In openssl/bn.h 85.Ft BN_MONT_CTX * 86.Fo BN_MONT_CTX_new 87.Fa void 88.Fc 89.Ft void 90.Fo BN_MONT_CTX_init 91.Fa "BN_MONT_CTX *ctx" 92.Fc 93.Ft void 94.Fo BN_MONT_CTX_free 95.Fa "BN_MONT_CTX *mont" 96.Fc 97.Ft int 98.Fo BN_MONT_CTX_set 99.Fa "BN_MONT_CTX *mont" 100.Fa "const BIGNUM *m" 101.Fa "BN_CTX *ctx" 102.Fc 103.Ft BN_MONT_CTX * 104.Fo BN_MONT_CTX_set_locked 105.Fa "BN_MONT_CTX **pmont" 106.Fa "int lock" 107.Fa "const BIGNUM *m" 108.Fa "BN_CTX *ctx" 109.Fc 110.Ft BN_MONT_CTX * 111.Fo BN_MONT_CTX_copy 112.Fa "BN_MONT_CTX *to" 113.Fa "BN_MONT_CTX *from" 114.Fc 115.Ft int 116.Fo BN_mod_mul_montgomery 117.Fa "BIGNUM *r" 118.Fa "const BIGNUM *a" 119.Fa "const BIGNUM *b" 120.Fa "BN_MONT_CTX *mont" 121.Fa "BN_CTX *ctx" 122.Fc 123.Ft int 124.Fo BN_from_montgomery 125.Fa "BIGNUM *r" 126.Fa "const BIGNUM *a" 127.Fa "BN_MONT_CTX *mont" 128.Fa "BN_CTX *ctx" 129.Fc 130.Ft int 131.Fo BN_to_montgomery 132.Fa "BIGNUM *r" 133.Fa "const BIGNUM *a" 134.Fa "BN_MONT_CTX *mont" 135.Fa "BN_CTX *ctx" 136.Fc 137.Sh DESCRIPTION 138These functions implement Montgomery multiplication. 139They are used automatically when 140.Xr BN_mod_exp 3 141is called with suitable input, but they may be useful when several 142operations are to be performed using the same modulus. 143.Pp 144.Fn BN_MONT_CTX_new 145allocates and initializes a 146.Vt BN_MONT_CTX 147structure. 148.Pp 149.Fn BN_MONT_CTX_init 150initializes an existing uninitialized 151.Vt BN_MONT_CTX . 152It is deprecated and dangerous: see 153.Sx CAVEATS . 154.Pp 155.Fn BN_MONT_CTX_set 156sets up the 157.Fa mont 158structure from the modulus 159.Fa m 160by precomputing its inverse and a value R. 161.Pp 162.Fn BN_MONT_CTX_set_locked 163is a wrapper around 164.Fn BN_MONT_CTX_new 165and 166.Fn BN_MONT_CTX_set 167that is useful if more than one thread intends to use the same 168.Vt BN_MONT_CTX 169and none of these threads is exclusively responsible for creating 170and initializing the context. 171.Fn BN_MONT_CTX_set_locked 172first acquires the specified 173.Fa lock 174using 175.Xr CRYPTO_lock 3 . 176If 177.Pf * Fa pmont 178already differs from 179.Dv NULL , 180no action occurs. 181Otherwise, a new 182.Vt BN_MONT_CTX 183is allocated with 184.Fn BN_MONT_CTX_new , 185set up with 186.Fn BN_MONT_CTX_set , 187and a pointer to it is stored in 188.Pf * Fa pmont . 189Finally, the 190.Fa lock 191is released. 192.Pp 193.Fn BN_MONT_CTX_copy 194copies the 195.Vt BN_MONT_CTX 196.Fa from 197to 198.Fa to . 199.Pp 200.Fn BN_MONT_CTX_free 201frees the components of the 202.Vt BN_MONT_CTX , 203and, if it was created by 204.Fn BN_MONT_CTX_new , 205also the structure itself. 206If 207.Fa mont 208is a 209.Dv NULL 210pointer, no action occurs. 211.Pp 212.Fn BN_mod_mul_montgomery 213computes 214.Pp 215.D1 Mont Ns Po Fa a , Fa b Pc := Fa a No * Fa b No * R^-1 216.Pp 217and places the result in 218.Fa r . 219.Pp 220.Fn BN_from_montgomery 221performs the Montgomery reduction 222.Pp 223.D1 Fa r No = Fa a No * R^-1 224.Pp 225.Fn BN_to_montgomery 226computes 227.Pp 228.D1 Mont Ns Po Fa a , No R^2 Pc = Fa a No * R 229.Pp 230Note that 231.Fa a 232must be non-negative and smaller than the modulus. 233.Pp 234For all functions, 235.Fa ctx 236is a previously allocated 237.Vt BN_CTX 238used for temporary variables. 239.Pp 240The 241.Vt BN_MONT_CTX 242structure is defined as follows: 243.Bd -literal 244typedef struct bn_mont_ctx_st { 245 int ri; /* number of bits in R */ 246 BIGNUM RR; /* R^2 (used to convert to Montgomery form) */ 247 BIGNUM N; /* The modulus */ 248 BIGNUM Ni; /* R*(1/R mod N) - N*Ni = 1 249 * (Ni is only stored for bignum algorithm) */ 250 BN_ULONG n0; /* least significant word of Ni */ 251 int flags; 252} BN_MONT_CTX; 253.Ed 254.Pp 255.Sy Warning : 256The inputs must be reduced modulo 257.Fa m , 258otherwise the result will be outside the expected range. 259.Sh RETURN VALUES 260.Fn BN_MONT_CTX_new 261returns the newly allocated 262.Vt BN_MONT_CTX 263or 264.Dv NULL 265on error. 266.Pp 267.Fn BN_MONT_CTX_set_locked 268returns a pointer to the existing or newly created context or 269.Dv NULL 270on error. 271.Pp 272For the other functions, 1 is returned for success or 0 on error. 273The error codes can be obtained by 274.Xr ERR_get_error 3 . 275.Sh SEE ALSO 276.Xr BN_add 3 , 277.Xr BN_CTX_new 3 , 278.Xr BN_new 3 , 279.Xr CRYPTO_lock 3 280.Sh HISTORY 281.Fn BN_MONT_CTX_new , 282.Fn BN_MONT_CTX_free , 283.Fn BN_MONT_CTX_set , 284.Fn BN_mod_mul_montgomery , 285.Fn BN_from_montgomery , 286and 287.Fn BN_to_montgomery 288first appeared in SSLeay 0.6.1 and have been available since 289.Ox 2.4 . 290.Pp 291.Fn BN_MONT_CTX_init 292and 293.Fn BN_MONT_CTX_copy 294first appeared in SSLeay 0.9.1 and have been available since 295.Ox 2.6 . 296.Pp 297.Fn BN_MONT_CTX_set_locked 298first appeared in OpenSSL 0.9.8 and has been available since 299.Ox 4.0 . 300.Sh CAVEATS 301.Fn BN_MONT_CTX_init 302must not be called on a context that was used previously, or 303memory used by the embedded 304.Vt BIGNUM 305structures is leaked immediately. 306Besides, it must not be called on a context created with 307.Fn BN_MONT_CTX_new , 308or the context itself will likely be leaked later. 309It can only be used on a static 310.Vt BN_MONT_CTX 311structure, on one located on the stack, or on one 312.Xr malloc 3 Ap ed 313manually, but all these options are discouraged because they 314will no longer work once 315.Vt BN_MONT_CTX 316is made opaque. 317