1.\" $OpenBSD: BN_mod_mul_montgomery.3,v 1.15 2023/04/21 06:34:37 tb 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: April 21 2023 $ 70.Dt BN_MOD_MUL_MONTGOMERY 3 71.Os 72.Sh NAME 73.Nm BN_MONT_CTX_new , 74.Nm BN_MONT_CTX_free , 75.Nm BN_MONT_CTX_set , 76.Nm BN_MONT_CTX_set_locked , 77.Nm BN_MONT_CTX_copy , 78.Nm BN_mod_mul_montgomery , 79.Nm BN_from_montgomery , 80.Nm BN_to_montgomery 81.Nd Montgomery multiplication 82.Sh SYNOPSIS 83.In openssl/bn.h 84.Ft BN_MONT_CTX * 85.Fo BN_MONT_CTX_new 86.Fa void 87.Fc 88.Ft void 89.Fo BN_MONT_CTX_free 90.Fa "BN_MONT_CTX *mont" 91.Fc 92.Ft int 93.Fo BN_MONT_CTX_set 94.Fa "BN_MONT_CTX *mont" 95.Fa "const BIGNUM *m" 96.Fa "BN_CTX *ctx" 97.Fc 98.Ft BN_MONT_CTX * 99.Fo BN_MONT_CTX_set_locked 100.Fa "BN_MONT_CTX **pmont" 101.Fa "int lock" 102.Fa "const BIGNUM *m" 103.Fa "BN_CTX *ctx" 104.Fc 105.Ft BN_MONT_CTX * 106.Fo BN_MONT_CTX_copy 107.Fa "BN_MONT_CTX *to" 108.Fa "BN_MONT_CTX *from" 109.Fc 110.Ft int 111.Fo BN_mod_mul_montgomery 112.Fa "BIGNUM *r" 113.Fa "const BIGNUM *a" 114.Fa "const BIGNUM *b" 115.Fa "BN_MONT_CTX *mont" 116.Fa "BN_CTX *ctx" 117.Fc 118.Ft int 119.Fo BN_from_montgomery 120.Fa "BIGNUM *r" 121.Fa "const BIGNUM *a" 122.Fa "BN_MONT_CTX *mont" 123.Fa "BN_CTX *ctx" 124.Fc 125.Ft int 126.Fo BN_to_montgomery 127.Fa "BIGNUM *r" 128.Fa "const BIGNUM *a" 129.Fa "BN_MONT_CTX *mont" 130.Fa "BN_CTX *ctx" 131.Fc 132.Sh DESCRIPTION 133These functions implement Montgomery multiplication. 134They are used automatically when 135.Xr BN_mod_exp 3 136is called with suitable input, but they may be useful when several 137operations are to be performed using the same modulus. 138.Pp 139.Fn BN_MONT_CTX_new 140allocates and initializes a 141.Vt BN_MONT_CTX 142structure. 143.Pp 144.Fn BN_MONT_CTX_set 145sets up the 146.Fa mont 147structure from the modulus 148.Fa m 149by precomputing its inverse and a value R. 150.Pp 151.Fn BN_MONT_CTX_set_locked 152is a wrapper around 153.Fn BN_MONT_CTX_new 154and 155.Fn BN_MONT_CTX_set 156that is useful if more than one thread intends to use the same 157.Vt BN_MONT_CTX 158and none of these threads is exclusively responsible for creating 159and initializing the context. 160.Fn BN_MONT_CTX_set_locked 161first acquires the specified 162.Fa lock 163using 164.Xr CRYPTO_lock 3 . 165If 166.Pf * Fa pmont 167already differs from 168.Dv NULL , 169no action occurs. 170Otherwise, a new 171.Vt BN_MONT_CTX 172is allocated with 173.Fn BN_MONT_CTX_new , 174set up with 175.Fn BN_MONT_CTX_set , 176and a pointer to it is stored in 177.Pf * Fa pmont . 178Finally, the 179.Fa lock 180is released. 181.Pp 182.Fn BN_MONT_CTX_copy 183copies the 184.Vt BN_MONT_CTX 185.Fa from 186to 187.Fa to . 188.Pp 189.Fn BN_MONT_CTX_free 190frees the components of the 191.Vt BN_MONT_CTX , 192and, if it was created by 193.Fn BN_MONT_CTX_new , 194also the structure itself. 195If 196.Fa mont 197is a 198.Dv NULL 199pointer, no action occurs. 200.Pp 201.Fn BN_mod_mul_montgomery 202computes 203.Pp 204.D1 Mont Ns Po Fa a , Fa b Pc := Fa a No * Fa b No * R^-1 205.Pp 206and places the result in 207.Fa r . 208.Pp 209.Fn BN_from_montgomery 210performs the Montgomery reduction 211.Pp 212.D1 Fa r No = Fa a No * R^-1 213.Pp 214.Fn BN_to_montgomery 215computes 216.Pp 217.D1 Mont Ns Po Fa a , No R^2 Pc = Fa a No * R 218.Pp 219Note that 220.Fa a 221must be non-negative and smaller than the modulus. 222.Pp 223For all functions, 224.Fa ctx 225is a previously allocated 226.Vt BN_CTX 227used for temporary variables. 228.Pp 229.Sy Warning : 230The inputs must be reduced modulo 231.Fa m , 232otherwise the result will be outside the expected range. 233.Sh RETURN VALUES 234.Fn BN_MONT_CTX_new 235returns the newly allocated 236.Vt BN_MONT_CTX 237or 238.Dv NULL 239on error. 240.Pp 241.Fn BN_MONT_CTX_set_locked 242returns a pointer to the existing or newly created context or 243.Dv NULL 244on error. 245.Pp 246For the other functions, 1 is returned for success or 0 on error. 247The error codes can be obtained by 248.Xr ERR_get_error 3 . 249.Sh SEE ALSO 250.Xr BN_add 3 , 251.Xr BN_CTX_new 3 , 252.Xr BN_new 3 , 253.Xr CRYPTO_lock 3 254.Sh HISTORY 255.Fn BN_MONT_CTX_new , 256.Fn BN_MONT_CTX_free , 257.Fn BN_MONT_CTX_set , 258.Fn BN_mod_mul_montgomery , 259.Fn BN_from_montgomery , 260and 261.Fn BN_to_montgomery 262first appeared in SSLeay 0.6.1 and have been available since 263.Ox 2.4 . 264.Pp 265.Fn BN_MONT_CTX_copy 266first appeared in SSLeay 0.9.1 and has been available since 267.Ox 2.6 . 268.Pp 269.Fn BN_MONT_CTX_set_locked 270first appeared in OpenSSL 0.9.8 and has been available since 271.Ox 4.0 . 272