1.\"	$OpenBSD: BN_mod_mul_montgomery.3,v 1.11 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_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
112These functions implement Montgomery multiplication.
113They are used automatically when
114.Xr BN_mod_exp 3
115is called with suitable input, but they may be useful when several
116operations are to be performed using the same modulus.
117.Pp
118.Fn BN_MONT_CTX_new
119allocates and initializes a
120.Vt BN_MONT_CTX
121structure.
122.Pp
123.Fn BN_MONT_CTX_init
124initializes an existing uninitialized
125.Vt BN_MONT_CTX .
126It is deprecated and dangerous: see
127.Sx CAVEATS .
128.Pp
129.Fn BN_MONT_CTX_set
130sets up the
131.Fa mont
132structure from the modulus
133.Fa m
134by precomputing its inverse and a value R.
135.Pp
136.Fn BN_MONT_CTX_copy
137copies the
138.Vt BN_MONT_CTX
139.Fa from
140to
141.Fa to .
142.Pp
143.Fn BN_MONT_CTX_free
144frees the components of the
145.Vt BN_MONT_CTX ,
146and, if it was created by
147.Fn BN_MONT_CTX_new ,
148also the structure itself.
149If
150.Fa mont
151is a
152.Dv NULL
153pointer, no action occurs.
154.Pp
155.Fn BN_mod_mul_montgomery
156computes
157.Pp
158.D1 Mont Ns Po Fa a , Fa b Pc := Fa a No * Fa b No * R^-1
159.Pp
160and places the result in
161.Fa r .
162.Pp
163.Fn BN_from_montgomery
164performs the Montgomery reduction
165.Pp
166.D1 Fa r No = Fa a No * R^-1
167.Pp
168.Fn BN_to_montgomery
169computes
170.Pp
171.D1 Mont Ns Po Fa a , No R^2 Pc = Fa a No * R
172.Pp
173Note that
174.Fa a
175must be non-negative and smaller than the modulus.
176.Pp
177For all functions,
178.Fa ctx
179is a previously allocated
180.Vt BN_CTX
181used for temporary variables.
182.Pp
183The
184.Vt BN_MONT_CTX
185structure is defined as follows:
186.Bd -literal
187typedef 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
199is a macro.
200.Pp
201.Sy Warning :
202The inputs must be reduced modulo
203.Fa m ,
204otherwise the result will be outside the expected range.
205.Sh RETURN VALUES
206.Fn BN_MONT_CTX_new
207returns the newly allocated
208.Vt BN_MONT_CTX
209or
210.Dv NULL
211on error.
212.Pp
213For the other functions, 1 is returned for success or 0 on error.
214The 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 ,
226and
227.Fn BN_to_montgomery
228first appeared in SSLeay 0.6.1 and have been available since
229.Ox 2.4 .
230.Pp
231.Fn BN_MONT_CTX_init
232and
233.Fn BN_MONT_CTX_copy
234first appeared in SSLeay 0.9.1 and have been available since
235.Ox 2.6 .
236.Sh CAVEATS
237.Fn BN_MONT_CTX_init
238must not be called on a context that was used previously, or
239memory used by the embedded
240.Vt BIGNUM
241structures is leaked immediately.
242Besides, it must not be called on a context created with
243.Fn BN_MONT_CTX_new ,
244or the context itself will likely be leaked later.
245It can only be used on a static
246.Vt BN_MONT_CTX
247structure, on one located on the stack, or on one
248.Xr malloc 3 Ap ed
249manually, but all these options are discouraged because they
250will no longer work once
251.Vt BN_MONT_CTX
252is made opaque.
253