1*de0e0e4dSAntonio Huete Jimenez /* $OpenBSD: bn_mont.c,v 1.28 2022/02/07 19:44:23 tb Exp $ */
2f5b1c8a1SJohn Marino /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3f5b1c8a1SJohn Marino * All rights reserved.
4f5b1c8a1SJohn Marino *
5f5b1c8a1SJohn Marino * This package is an SSL implementation written
6f5b1c8a1SJohn Marino * by Eric Young (eay@cryptsoft.com).
7f5b1c8a1SJohn Marino * The implementation was written so as to conform with Netscapes SSL.
8f5b1c8a1SJohn Marino *
9f5b1c8a1SJohn Marino * This library is free for commercial and non-commercial use as long as
10f5b1c8a1SJohn Marino * the following conditions are aheared to. The following conditions
11f5b1c8a1SJohn Marino * apply to all code found in this distribution, be it the RC4, RSA,
12f5b1c8a1SJohn Marino * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13f5b1c8a1SJohn Marino * included with this distribution is covered by the same copyright terms
14f5b1c8a1SJohn Marino * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15f5b1c8a1SJohn Marino *
16f5b1c8a1SJohn Marino * Copyright remains Eric Young's, and as such any Copyright notices in
17f5b1c8a1SJohn Marino * the code are not to be removed.
18f5b1c8a1SJohn Marino * If this package is used in a product, Eric Young should be given attribution
19f5b1c8a1SJohn Marino * as the author of the parts of the library used.
20f5b1c8a1SJohn Marino * This can be in the form of a textual message at program startup or
21f5b1c8a1SJohn Marino * in documentation (online or textual) provided with the package.
22f5b1c8a1SJohn Marino *
23f5b1c8a1SJohn Marino * Redistribution and use in source and binary forms, with or without
24f5b1c8a1SJohn Marino * modification, are permitted provided that the following conditions
25f5b1c8a1SJohn Marino * are met:
26f5b1c8a1SJohn Marino * 1. Redistributions of source code must retain the copyright
27f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer.
28f5b1c8a1SJohn Marino * 2. Redistributions in binary form must reproduce the above copyright
29f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer in the
30f5b1c8a1SJohn Marino * documentation and/or other materials provided with the distribution.
31f5b1c8a1SJohn Marino * 3. All advertising materials mentioning features or use of this software
32f5b1c8a1SJohn Marino * must display the following acknowledgement:
33f5b1c8a1SJohn Marino * "This product includes cryptographic software written by
34f5b1c8a1SJohn Marino * Eric Young (eay@cryptsoft.com)"
35f5b1c8a1SJohn Marino * The word 'cryptographic' can be left out if the rouines from the library
36f5b1c8a1SJohn Marino * being used are not cryptographic related :-).
37f5b1c8a1SJohn Marino * 4. If you include any Windows specific code (or a derivative thereof) from
38f5b1c8a1SJohn Marino * the apps directory (application code) you must include an acknowledgement:
39f5b1c8a1SJohn Marino * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40f5b1c8a1SJohn Marino *
41f5b1c8a1SJohn Marino * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42f5b1c8a1SJohn Marino * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43f5b1c8a1SJohn Marino * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44f5b1c8a1SJohn Marino * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45f5b1c8a1SJohn Marino * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46f5b1c8a1SJohn Marino * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47f5b1c8a1SJohn Marino * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48f5b1c8a1SJohn Marino * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49f5b1c8a1SJohn Marino * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50f5b1c8a1SJohn Marino * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51f5b1c8a1SJohn Marino * SUCH DAMAGE.
52f5b1c8a1SJohn Marino *
53f5b1c8a1SJohn Marino * The licence and distribution terms for any publically available version or
54f5b1c8a1SJohn Marino * derivative of this code cannot be changed. i.e. this code cannot simply be
55f5b1c8a1SJohn Marino * copied and put under another distribution licence
56f5b1c8a1SJohn Marino * [including the GNU Public Licence.]
57f5b1c8a1SJohn Marino */
58f5b1c8a1SJohn Marino /* ====================================================================
59f5b1c8a1SJohn Marino * Copyright (c) 1998-2006 The OpenSSL Project. All rights reserved.
60f5b1c8a1SJohn Marino *
61f5b1c8a1SJohn Marino * Redistribution and use in source and binary forms, with or without
62f5b1c8a1SJohn Marino * modification, are permitted provided that the following conditions
63f5b1c8a1SJohn Marino * are met:
64f5b1c8a1SJohn Marino *
65f5b1c8a1SJohn Marino * 1. Redistributions of source code must retain the above copyright
66f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer.
67f5b1c8a1SJohn Marino *
68f5b1c8a1SJohn Marino * 2. Redistributions in binary form must reproduce the above copyright
69f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer in
70f5b1c8a1SJohn Marino * the documentation and/or other materials provided with the
71f5b1c8a1SJohn Marino * distribution.
72f5b1c8a1SJohn Marino *
73f5b1c8a1SJohn Marino * 3. All advertising materials mentioning features or use of this
74f5b1c8a1SJohn Marino * software must display the following acknowledgment:
75f5b1c8a1SJohn Marino * "This product includes software developed by the OpenSSL Project
76f5b1c8a1SJohn Marino * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
77f5b1c8a1SJohn Marino *
78f5b1c8a1SJohn Marino * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
79f5b1c8a1SJohn Marino * endorse or promote products derived from this software without
80f5b1c8a1SJohn Marino * prior written permission. For written permission, please contact
81f5b1c8a1SJohn Marino * openssl-core@openssl.org.
82f5b1c8a1SJohn Marino *
83f5b1c8a1SJohn Marino * 5. Products derived from this software may not be called "OpenSSL"
84f5b1c8a1SJohn Marino * nor may "OpenSSL" appear in their names without prior written
85f5b1c8a1SJohn Marino * permission of the OpenSSL Project.
86f5b1c8a1SJohn Marino *
87f5b1c8a1SJohn Marino * 6. Redistributions of any form whatsoever must retain the following
88f5b1c8a1SJohn Marino * acknowledgment:
89f5b1c8a1SJohn Marino * "This product includes software developed by the OpenSSL Project
90f5b1c8a1SJohn Marino * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
91f5b1c8a1SJohn Marino *
92f5b1c8a1SJohn Marino * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
93f5b1c8a1SJohn Marino * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
94f5b1c8a1SJohn Marino * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
95f5b1c8a1SJohn Marino * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
96f5b1c8a1SJohn Marino * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
97f5b1c8a1SJohn Marino * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
98f5b1c8a1SJohn Marino * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
99f5b1c8a1SJohn Marino * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
100f5b1c8a1SJohn Marino * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
101f5b1c8a1SJohn Marino * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
102f5b1c8a1SJohn Marino * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
103f5b1c8a1SJohn Marino * OF THE POSSIBILITY OF SUCH DAMAGE.
104f5b1c8a1SJohn Marino * ====================================================================
105f5b1c8a1SJohn Marino *
106f5b1c8a1SJohn Marino * This product includes cryptographic software written by Eric Young
107f5b1c8a1SJohn Marino * (eay@cryptsoft.com). This product includes software written by Tim
108f5b1c8a1SJohn Marino * Hudson (tjh@cryptsoft.com).
109f5b1c8a1SJohn Marino *
110f5b1c8a1SJohn Marino */
111f5b1c8a1SJohn Marino
112f5b1c8a1SJohn Marino /*
113f5b1c8a1SJohn Marino * Details about Montgomery multiplication algorithms can be found at
114f5b1c8a1SJohn Marino * http://security.ece.orst.edu/publications.html, e.g.
115f5b1c8a1SJohn Marino * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
116f5b1c8a1SJohn Marino * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
117f5b1c8a1SJohn Marino */
118f5b1c8a1SJohn Marino
119f5b1c8a1SJohn Marino #include <stdio.h>
120f5b1c8a1SJohn Marino #include <stdint.h>
121f5b1c8a1SJohn Marino
122f5b1c8a1SJohn Marino #include "bn_lcl.h"
123f5b1c8a1SJohn Marino
124f5b1c8a1SJohn Marino #define MONT_WORD /* use the faster word-based algorithm */
125f5b1c8a1SJohn Marino
126f5b1c8a1SJohn Marino #ifdef MONT_WORD
127f5b1c8a1SJohn Marino static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
128f5b1c8a1SJohn Marino #endif
129f5b1c8a1SJohn Marino
130f5b1c8a1SJohn Marino int
BN_mod_mul_montgomery(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_MONT_CTX * mont,BN_CTX * ctx)131f5b1c8a1SJohn Marino BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
132f5b1c8a1SJohn Marino BN_MONT_CTX *mont, BN_CTX *ctx)
133f5b1c8a1SJohn Marino {
134f5b1c8a1SJohn Marino BIGNUM *tmp;
135f5b1c8a1SJohn Marino int ret = 0;
136f5b1c8a1SJohn Marino #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
137f5b1c8a1SJohn Marino int num = mont->N.top;
138f5b1c8a1SJohn Marino
139f5b1c8a1SJohn Marino if (num > 1 && a->top == num && b->top == num) {
140f5b1c8a1SJohn Marino if (bn_wexpand(r, num) == NULL)
141f5b1c8a1SJohn Marino return (0);
142f5b1c8a1SJohn Marino if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {
143f5b1c8a1SJohn Marino r->neg = a->neg^b->neg;
144f5b1c8a1SJohn Marino r->top = num;
145f5b1c8a1SJohn Marino bn_correct_top(r);
146f5b1c8a1SJohn Marino return (1);
147f5b1c8a1SJohn Marino }
148f5b1c8a1SJohn Marino }
149f5b1c8a1SJohn Marino #endif
150f5b1c8a1SJohn Marino
151f5b1c8a1SJohn Marino BN_CTX_start(ctx);
152f5b1c8a1SJohn Marino if ((tmp = BN_CTX_get(ctx)) == NULL)
153f5b1c8a1SJohn Marino goto err;
154f5b1c8a1SJohn Marino
155f5b1c8a1SJohn Marino bn_check_top(tmp);
156f5b1c8a1SJohn Marino if (a == b) {
157f5b1c8a1SJohn Marino if (!BN_sqr(tmp, a, ctx))
158f5b1c8a1SJohn Marino goto err;
159f5b1c8a1SJohn Marino } else {
160f5b1c8a1SJohn Marino if (!BN_mul(tmp, a,b, ctx))
161f5b1c8a1SJohn Marino goto err;
162f5b1c8a1SJohn Marino }
163f5b1c8a1SJohn Marino /* reduce from aRR to aR */
164f5b1c8a1SJohn Marino #ifdef MONT_WORD
165f5b1c8a1SJohn Marino if (!BN_from_montgomery_word(r, tmp, mont))
166f5b1c8a1SJohn Marino goto err;
167f5b1c8a1SJohn Marino #else
168f5b1c8a1SJohn Marino if (!BN_from_montgomery(r, tmp, mont, ctx))
169f5b1c8a1SJohn Marino goto err;
170f5b1c8a1SJohn Marino #endif
171f5b1c8a1SJohn Marino bn_check_top(r);
172f5b1c8a1SJohn Marino ret = 1;
173f5b1c8a1SJohn Marino err:
174f5b1c8a1SJohn Marino BN_CTX_end(ctx);
175f5b1c8a1SJohn Marino return (ret);
176f5b1c8a1SJohn Marino }
177f5b1c8a1SJohn Marino
178*de0e0e4dSAntonio Huete Jimenez int
BN_to_montgomery(BIGNUM * r,const BIGNUM * a,BN_MONT_CTX * mont,BN_CTX * ctx)179*de0e0e4dSAntonio Huete Jimenez BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx)
180*de0e0e4dSAntonio Huete Jimenez {
181*de0e0e4dSAntonio Huete Jimenez return BN_mod_mul_montgomery(r, a, &mont->RR, mont, ctx);
182*de0e0e4dSAntonio Huete Jimenez }
183*de0e0e4dSAntonio Huete Jimenez
184f5b1c8a1SJohn Marino #ifdef MONT_WORD
185f5b1c8a1SJohn Marino static int
BN_from_montgomery_word(BIGNUM * ret,BIGNUM * r,BN_MONT_CTX * mont)186f5b1c8a1SJohn Marino BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
187f5b1c8a1SJohn Marino {
188f5b1c8a1SJohn Marino BIGNUM *n;
189f5b1c8a1SJohn Marino BN_ULONG *ap, *np, *rp, n0, v, carry;
190f5b1c8a1SJohn Marino int nl, max, i;
191f5b1c8a1SJohn Marino
192f5b1c8a1SJohn Marino n = &(mont->N);
193f5b1c8a1SJohn Marino nl = n->top;
194f5b1c8a1SJohn Marino if (nl == 0) {
195f5b1c8a1SJohn Marino ret->top = 0;
196f5b1c8a1SJohn Marino return (1);
197f5b1c8a1SJohn Marino }
198f5b1c8a1SJohn Marino
199f5b1c8a1SJohn Marino max = (2 * nl); /* carry is stored separately */
200f5b1c8a1SJohn Marino if (bn_wexpand(r, max) == NULL)
201f5b1c8a1SJohn Marino return (0);
202f5b1c8a1SJohn Marino
203f5b1c8a1SJohn Marino r->neg ^= n->neg;
204f5b1c8a1SJohn Marino np = n->d;
205f5b1c8a1SJohn Marino rp = r->d;
206f5b1c8a1SJohn Marino
207f5b1c8a1SJohn Marino /* clear the top words of T */
208f5b1c8a1SJohn Marino #if 1
209f5b1c8a1SJohn Marino for (i=r->top; i<max; i++) /* memset? XXX */
210f5b1c8a1SJohn Marino rp[i] = 0;
211f5b1c8a1SJohn Marino #else
212f5b1c8a1SJohn Marino memset(&(rp[r->top]), 0, (max - r->top) * sizeof(BN_ULONG));
213f5b1c8a1SJohn Marino #endif
214f5b1c8a1SJohn Marino
215f5b1c8a1SJohn Marino r->top = max;
216f5b1c8a1SJohn Marino n0 = mont->n0[0];
217f5b1c8a1SJohn Marino
218f5b1c8a1SJohn Marino #ifdef BN_COUNT
219f5b1c8a1SJohn Marino fprintf(stderr, "word BN_from_montgomery_word %d * %d\n", nl, nl);
220f5b1c8a1SJohn Marino #endif
221f5b1c8a1SJohn Marino for (carry = 0, i = 0; i < nl; i++, rp++) {
222f5b1c8a1SJohn Marino v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2);
223f5b1c8a1SJohn Marino v = (v + carry + rp[nl]) & BN_MASK2;
224f5b1c8a1SJohn Marino carry |= (v != rp[nl]);
225f5b1c8a1SJohn Marino carry &= (v <= rp[nl]);
226f5b1c8a1SJohn Marino rp[nl] = v;
227f5b1c8a1SJohn Marino }
228f5b1c8a1SJohn Marino
229f5b1c8a1SJohn Marino if (bn_wexpand(ret, nl) == NULL)
230f5b1c8a1SJohn Marino return (0);
231f5b1c8a1SJohn Marino ret->top = nl;
232f5b1c8a1SJohn Marino ret->neg = r->neg;
233f5b1c8a1SJohn Marino
234f5b1c8a1SJohn Marino rp = ret->d;
235f5b1c8a1SJohn Marino ap = &(r->d[nl]);
236f5b1c8a1SJohn Marino
237f5b1c8a1SJohn Marino #define BRANCH_FREE 1
238f5b1c8a1SJohn Marino #if BRANCH_FREE
239f5b1c8a1SJohn Marino {
240f5b1c8a1SJohn Marino BN_ULONG *nrp;
241f5b1c8a1SJohn Marino size_t m;
242f5b1c8a1SJohn Marino
243f5b1c8a1SJohn Marino v = bn_sub_words(rp, ap, np, nl) - carry;
244f5b1c8a1SJohn Marino /* if subtraction result is real, then
245f5b1c8a1SJohn Marino * trick unconditional memcpy below to perform in-place
246f5b1c8a1SJohn Marino * "refresh" instead of actual copy. */
247f5b1c8a1SJohn Marino m = (0 - (size_t)v);
248f5b1c8a1SJohn Marino nrp = (BN_ULONG *)(((uintptr_t)rp & ~m)|((uintptr_t)ap & m));
249f5b1c8a1SJohn Marino
250f5b1c8a1SJohn Marino for (i = 0, nl -= 4; i < nl; i += 4) {
251f5b1c8a1SJohn Marino BN_ULONG t1, t2, t3, t4;
252f5b1c8a1SJohn Marino
253f5b1c8a1SJohn Marino t1 = nrp[i + 0];
254f5b1c8a1SJohn Marino t2 = nrp[i + 1];
255f5b1c8a1SJohn Marino t3 = nrp[i + 2];
256f5b1c8a1SJohn Marino ap[i + 0] = 0;
257f5b1c8a1SJohn Marino t4 = nrp[i + 3];
258f5b1c8a1SJohn Marino ap[i + 1] = 0;
259f5b1c8a1SJohn Marino rp[i + 0] = t1;
260f5b1c8a1SJohn Marino ap[i + 2] = 0;
261f5b1c8a1SJohn Marino rp[i + 1] = t2;
262f5b1c8a1SJohn Marino ap[i + 3] = 0;
263f5b1c8a1SJohn Marino rp[i + 2] = t3;
264f5b1c8a1SJohn Marino rp[i + 3] = t4;
265f5b1c8a1SJohn Marino }
266f5b1c8a1SJohn Marino for (nl += 4; i < nl; i++)
267f5b1c8a1SJohn Marino rp[i] = nrp[i], ap[i] = 0;
268f5b1c8a1SJohn Marino }
269f5b1c8a1SJohn Marino #else
270f5b1c8a1SJohn Marino if (bn_sub_words (rp, ap, np, nl) - carry)
271f5b1c8a1SJohn Marino memcpy(rp, ap, nl*sizeof(BN_ULONG));
272f5b1c8a1SJohn Marino #endif
273f5b1c8a1SJohn Marino bn_correct_top(r);
274f5b1c8a1SJohn Marino bn_correct_top(ret);
275f5b1c8a1SJohn Marino bn_check_top(ret);
276f5b1c8a1SJohn Marino
277f5b1c8a1SJohn Marino return (1);
278f5b1c8a1SJohn Marino }
279f5b1c8a1SJohn Marino #endif /* MONT_WORD */
280f5b1c8a1SJohn Marino
281f5b1c8a1SJohn Marino int
BN_from_montgomery(BIGNUM * ret,const BIGNUM * a,BN_MONT_CTX * mont,BN_CTX * ctx)282f5b1c8a1SJohn Marino BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx)
283f5b1c8a1SJohn Marino {
284f5b1c8a1SJohn Marino int retn = 0;
285f5b1c8a1SJohn Marino #ifdef MONT_WORD
286f5b1c8a1SJohn Marino BIGNUM *t;
287f5b1c8a1SJohn Marino
288f5b1c8a1SJohn Marino BN_CTX_start(ctx);
289f5b1c8a1SJohn Marino if ((t = BN_CTX_get(ctx)) && BN_copy(t, a))
290f5b1c8a1SJohn Marino retn = BN_from_montgomery_word(ret, t, mont);
291f5b1c8a1SJohn Marino BN_CTX_end(ctx);
292f5b1c8a1SJohn Marino #else /* !MONT_WORD */
293f5b1c8a1SJohn Marino BIGNUM *t1, *t2;
294f5b1c8a1SJohn Marino
295f5b1c8a1SJohn Marino BN_CTX_start(ctx);
296f5b1c8a1SJohn Marino if ((t1 = BN_CTX_get(ctx)) == NULL)
297f5b1c8a1SJohn Marino goto err;
298f5b1c8a1SJohn Marino if ((t2 = BN_CTX_get(ctx)) == NULL)
299f5b1c8a1SJohn Marino goto err;
300f5b1c8a1SJohn Marino
301f5b1c8a1SJohn Marino if (!BN_copy(t1, a))
302f5b1c8a1SJohn Marino goto err;
303f5b1c8a1SJohn Marino BN_mask_bits(t1, mont->ri);
304f5b1c8a1SJohn Marino
305f5b1c8a1SJohn Marino if (!BN_mul(t2, t1, &mont->Ni, ctx))
306f5b1c8a1SJohn Marino goto err;
307f5b1c8a1SJohn Marino BN_mask_bits(t2, mont->ri);
308f5b1c8a1SJohn Marino
309f5b1c8a1SJohn Marino if (!BN_mul(t1, t2, &mont->N, ctx))
310f5b1c8a1SJohn Marino goto err;
311f5b1c8a1SJohn Marino if (!BN_add(t2, a, t1))
312f5b1c8a1SJohn Marino goto err;
313f5b1c8a1SJohn Marino if (!BN_rshift(ret, t2, mont->ri))
314f5b1c8a1SJohn Marino goto err;
315f5b1c8a1SJohn Marino
316f5b1c8a1SJohn Marino if (BN_ucmp(ret, &(mont->N)) >= 0) {
317f5b1c8a1SJohn Marino if (!BN_usub(ret, ret, &(mont->N)))
318f5b1c8a1SJohn Marino goto err;
319f5b1c8a1SJohn Marino }
320f5b1c8a1SJohn Marino retn = 1;
321f5b1c8a1SJohn Marino bn_check_top(ret);
322f5b1c8a1SJohn Marino
323f5b1c8a1SJohn Marino err:
324f5b1c8a1SJohn Marino BN_CTX_end(ctx);
325f5b1c8a1SJohn Marino #endif /* MONT_WORD */
326f5b1c8a1SJohn Marino return (retn);
327f5b1c8a1SJohn Marino }
328f5b1c8a1SJohn Marino
329f5b1c8a1SJohn Marino BN_MONT_CTX *
BN_MONT_CTX_new(void)330f5b1c8a1SJohn Marino BN_MONT_CTX_new(void)
331f5b1c8a1SJohn Marino {
332f5b1c8a1SJohn Marino BN_MONT_CTX *ret;
333f5b1c8a1SJohn Marino
334f5b1c8a1SJohn Marino if ((ret = malloc(sizeof(BN_MONT_CTX))) == NULL)
335f5b1c8a1SJohn Marino return (NULL);
336f5b1c8a1SJohn Marino
337f5b1c8a1SJohn Marino BN_MONT_CTX_init(ret);
338f5b1c8a1SJohn Marino ret->flags = BN_FLG_MALLOCED;
339f5b1c8a1SJohn Marino return (ret);
340f5b1c8a1SJohn Marino }
341f5b1c8a1SJohn Marino
342f5b1c8a1SJohn Marino void
BN_MONT_CTX_init(BN_MONT_CTX * ctx)343f5b1c8a1SJohn Marino BN_MONT_CTX_init(BN_MONT_CTX *ctx)
344f5b1c8a1SJohn Marino {
345f5b1c8a1SJohn Marino ctx->ri = 0;
346f5b1c8a1SJohn Marino BN_init(&(ctx->RR));
347f5b1c8a1SJohn Marino BN_init(&(ctx->N));
348f5b1c8a1SJohn Marino BN_init(&(ctx->Ni));
349f5b1c8a1SJohn Marino ctx->n0[0] = ctx->n0[1] = 0;
350f5b1c8a1SJohn Marino ctx->flags = 0;
351f5b1c8a1SJohn Marino }
352f5b1c8a1SJohn Marino
353f5b1c8a1SJohn Marino void
BN_MONT_CTX_free(BN_MONT_CTX * mont)354f5b1c8a1SJohn Marino BN_MONT_CTX_free(BN_MONT_CTX *mont)
355f5b1c8a1SJohn Marino {
356f5b1c8a1SJohn Marino if (mont == NULL)
357f5b1c8a1SJohn Marino return;
358f5b1c8a1SJohn Marino
359f5b1c8a1SJohn Marino BN_clear_free(&(mont->RR));
360f5b1c8a1SJohn Marino BN_clear_free(&(mont->N));
361f5b1c8a1SJohn Marino BN_clear_free(&(mont->Ni));
362f5b1c8a1SJohn Marino if (mont->flags & BN_FLG_MALLOCED)
363f5b1c8a1SJohn Marino free(mont);
364f5b1c8a1SJohn Marino }
365f5b1c8a1SJohn Marino
366f5b1c8a1SJohn Marino int
BN_MONT_CTX_set(BN_MONT_CTX * mont,const BIGNUM * mod,BN_CTX * ctx)367f5b1c8a1SJohn Marino BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
368f5b1c8a1SJohn Marino {
369f5b1c8a1SJohn Marino int ret = 0;
370f5b1c8a1SJohn Marino BIGNUM *Ri, *R;
371f5b1c8a1SJohn Marino
372*de0e0e4dSAntonio Huete Jimenez if (BN_is_zero(mod))
373*de0e0e4dSAntonio Huete Jimenez return 0;
374*de0e0e4dSAntonio Huete Jimenez
375f5b1c8a1SJohn Marino BN_CTX_start(ctx);
376f5b1c8a1SJohn Marino if ((Ri = BN_CTX_get(ctx)) == NULL)
377f5b1c8a1SJohn Marino goto err;
378f5b1c8a1SJohn Marino R = &(mont->RR); /* grab RR as a temp */
379f5b1c8a1SJohn Marino if (!BN_copy(&(mont->N), mod))
380f5b1c8a1SJohn Marino goto err; /* Set N */
381f5b1c8a1SJohn Marino mont->N.neg = 0;
382f5b1c8a1SJohn Marino
383f5b1c8a1SJohn Marino #ifdef MONT_WORD
384f5b1c8a1SJohn Marino {
385f5b1c8a1SJohn Marino BIGNUM tmod;
386f5b1c8a1SJohn Marino BN_ULONG buf[2];
387f5b1c8a1SJohn Marino
388f5b1c8a1SJohn Marino BN_init(&tmod);
389f5b1c8a1SJohn Marino tmod.d = buf;
390f5b1c8a1SJohn Marino tmod.dmax = 2;
391f5b1c8a1SJohn Marino tmod.neg = 0;
392f5b1c8a1SJohn Marino
393f5b1c8a1SJohn Marino mont->ri = (BN_num_bits(mod) +
394f5b1c8a1SJohn Marino (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;
395f5b1c8a1SJohn Marino
396f5b1c8a1SJohn Marino #if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
397f5b1c8a1SJohn Marino /* Only certain BN_BITS2<=32 platforms actually make use of
398f5b1c8a1SJohn Marino * n0[1], and we could use the #else case (with a shorter R
399f5b1c8a1SJohn Marino * value) for the others. However, currently only the assembler
400f5b1c8a1SJohn Marino * files do know which is which. */
401f5b1c8a1SJohn Marino
402f5b1c8a1SJohn Marino BN_zero(R);
403f5b1c8a1SJohn Marino if (!(BN_set_bit(R, 2 * BN_BITS2)))
404f5b1c8a1SJohn Marino goto err;
405f5b1c8a1SJohn Marino
406f5b1c8a1SJohn Marino tmod.top = 0;
407f5b1c8a1SJohn Marino if ((buf[0] = mod->d[0]))
408f5b1c8a1SJohn Marino tmod.top = 1;
409f5b1c8a1SJohn Marino if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
410f5b1c8a1SJohn Marino tmod.top = 2;
411f5b1c8a1SJohn Marino
41272c33676SMaxim Ag if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
413f5b1c8a1SJohn Marino goto err;
414f5b1c8a1SJohn Marino if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
415f5b1c8a1SJohn Marino goto err; /* R*Ri */
416f5b1c8a1SJohn Marino if (!BN_is_zero(Ri)) {
417f5b1c8a1SJohn Marino if (!BN_sub_word(Ri, 1))
418f5b1c8a1SJohn Marino goto err;
419f5b1c8a1SJohn Marino }
420f5b1c8a1SJohn Marino else /* if N mod word size == 1 */
421f5b1c8a1SJohn Marino {
422f5b1c8a1SJohn Marino if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL)
423f5b1c8a1SJohn Marino goto err;
424f5b1c8a1SJohn Marino /* Ri-- (mod double word size) */
425f5b1c8a1SJohn Marino Ri->neg = 0;
426f5b1c8a1SJohn Marino Ri->d[0] = BN_MASK2;
427f5b1c8a1SJohn Marino Ri->d[1] = BN_MASK2;
428f5b1c8a1SJohn Marino Ri->top = 2;
429f5b1c8a1SJohn Marino }
43072c33676SMaxim Ag if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
431f5b1c8a1SJohn Marino goto err;
432f5b1c8a1SJohn Marino /* Ni = (R*Ri-1)/N,
433f5b1c8a1SJohn Marino * keep only couple of least significant words: */
434f5b1c8a1SJohn Marino mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
435f5b1c8a1SJohn Marino mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
436f5b1c8a1SJohn Marino #else
437f5b1c8a1SJohn Marino BN_zero(R);
438f5b1c8a1SJohn Marino if (!(BN_set_bit(R, BN_BITS2)))
439f5b1c8a1SJohn Marino goto err; /* R */
440f5b1c8a1SJohn Marino
441f5b1c8a1SJohn Marino buf[0] = mod->d[0]; /* tmod = N mod word size */
442f5b1c8a1SJohn Marino buf[1] = 0;
443f5b1c8a1SJohn Marino tmod.top = buf[0] != 0 ? 1 : 0;
444f5b1c8a1SJohn Marino /* Ri = R^-1 mod N*/
44572c33676SMaxim Ag if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
446f5b1c8a1SJohn Marino goto err;
447f5b1c8a1SJohn Marino if (!BN_lshift(Ri, Ri, BN_BITS2))
448f5b1c8a1SJohn Marino goto err; /* R*Ri */
449f5b1c8a1SJohn Marino if (!BN_is_zero(Ri)) {
450f5b1c8a1SJohn Marino if (!BN_sub_word(Ri, 1))
451f5b1c8a1SJohn Marino goto err;
452f5b1c8a1SJohn Marino }
453f5b1c8a1SJohn Marino else /* if N mod word size == 1 */
454f5b1c8a1SJohn Marino {
455f5b1c8a1SJohn Marino if (!BN_set_word(Ri, BN_MASK2))
456f5b1c8a1SJohn Marino goto err; /* Ri-- (mod word size) */
457f5b1c8a1SJohn Marino }
45872c33676SMaxim Ag if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
459f5b1c8a1SJohn Marino goto err;
460f5b1c8a1SJohn Marino /* Ni = (R*Ri-1)/N,
461f5b1c8a1SJohn Marino * keep only least significant word: */
462f5b1c8a1SJohn Marino mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
463f5b1c8a1SJohn Marino mont->n0[1] = 0;
464f5b1c8a1SJohn Marino #endif
465f5b1c8a1SJohn Marino }
466f5b1c8a1SJohn Marino #else /* !MONT_WORD */
467f5b1c8a1SJohn Marino { /* bignum version */
468f5b1c8a1SJohn Marino mont->ri = BN_num_bits(&mont->N);
469f5b1c8a1SJohn Marino BN_zero(R);
470f5b1c8a1SJohn Marino if (!BN_set_bit(R, mont->ri))
471f5b1c8a1SJohn Marino goto err; /* R = 2^ri */
472f5b1c8a1SJohn Marino /* Ri = R^-1 mod N*/
47372c33676SMaxim Ag if ((BN_mod_inverse_ct(Ri, R, &mont->N, ctx)) == NULL)
474f5b1c8a1SJohn Marino goto err;
475f5b1c8a1SJohn Marino if (!BN_lshift(Ri, Ri, mont->ri))
476f5b1c8a1SJohn Marino goto err; /* R*Ri */
477f5b1c8a1SJohn Marino if (!BN_sub_word(Ri, 1))
478f5b1c8a1SJohn Marino goto err;
479f5b1c8a1SJohn Marino /* Ni = (R*Ri-1) / N */
48072c33676SMaxim Ag if (!BN_div_ct(&(mont->Ni), NULL, Ri, &mont->N, ctx))
481f5b1c8a1SJohn Marino goto err;
482f5b1c8a1SJohn Marino }
483f5b1c8a1SJohn Marino #endif
484f5b1c8a1SJohn Marino
485f5b1c8a1SJohn Marino /* setup RR for conversions */
486f5b1c8a1SJohn Marino BN_zero(&(mont->RR));
487f5b1c8a1SJohn Marino if (!BN_set_bit(&(mont->RR), mont->ri*2))
488f5b1c8a1SJohn Marino goto err;
48972c33676SMaxim Ag if (!BN_mod_ct(&(mont->RR), &(mont->RR), &(mont->N), ctx))
490f5b1c8a1SJohn Marino goto err;
491f5b1c8a1SJohn Marino
492f5b1c8a1SJohn Marino ret = 1;
493f5b1c8a1SJohn Marino
494f5b1c8a1SJohn Marino err:
495f5b1c8a1SJohn Marino BN_CTX_end(ctx);
496f5b1c8a1SJohn Marino return ret;
497f5b1c8a1SJohn Marino }
498f5b1c8a1SJohn Marino
499f5b1c8a1SJohn Marino BN_MONT_CTX *
BN_MONT_CTX_copy(BN_MONT_CTX * to,BN_MONT_CTX * from)500f5b1c8a1SJohn Marino BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
501f5b1c8a1SJohn Marino {
502f5b1c8a1SJohn Marino if (to == from)
503f5b1c8a1SJohn Marino return (to);
504f5b1c8a1SJohn Marino
505f5b1c8a1SJohn Marino if (!BN_copy(&(to->RR), &(from->RR)))
506f5b1c8a1SJohn Marino return NULL;
507f5b1c8a1SJohn Marino if (!BN_copy(&(to->N), &(from->N)))
508f5b1c8a1SJohn Marino return NULL;
509f5b1c8a1SJohn Marino if (!BN_copy(&(to->Ni), &(from->Ni)))
510f5b1c8a1SJohn Marino return NULL;
511f5b1c8a1SJohn Marino to->ri = from->ri;
512f5b1c8a1SJohn Marino to->n0[0] = from->n0[0];
513f5b1c8a1SJohn Marino to->n0[1] = from->n0[1];
514f5b1c8a1SJohn Marino return (to);
515f5b1c8a1SJohn Marino }
516f5b1c8a1SJohn Marino
517f5b1c8a1SJohn Marino BN_MONT_CTX *
BN_MONT_CTX_set_locked(BN_MONT_CTX ** pmont,int lock,const BIGNUM * mod,BN_CTX * ctx)518f5b1c8a1SJohn Marino BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, const BIGNUM *mod,
519f5b1c8a1SJohn Marino BN_CTX *ctx)
520f5b1c8a1SJohn Marino {
521f5b1c8a1SJohn Marino int got_write_lock = 0;
522f5b1c8a1SJohn Marino BN_MONT_CTX *ret;
523f5b1c8a1SJohn Marino
524f5b1c8a1SJohn Marino CRYPTO_r_lock(lock);
525f5b1c8a1SJohn Marino if (!*pmont) {
526f5b1c8a1SJohn Marino CRYPTO_r_unlock(lock);
527f5b1c8a1SJohn Marino CRYPTO_w_lock(lock);
528f5b1c8a1SJohn Marino got_write_lock = 1;
529f5b1c8a1SJohn Marino
530f5b1c8a1SJohn Marino if (!*pmont) {
531f5b1c8a1SJohn Marino ret = BN_MONT_CTX_new();
532f5b1c8a1SJohn Marino if (ret && !BN_MONT_CTX_set(ret, mod, ctx))
533f5b1c8a1SJohn Marino BN_MONT_CTX_free(ret);
534f5b1c8a1SJohn Marino else
535f5b1c8a1SJohn Marino *pmont = ret;
536f5b1c8a1SJohn Marino }
537f5b1c8a1SJohn Marino }
538f5b1c8a1SJohn Marino
539f5b1c8a1SJohn Marino ret = *pmont;
540f5b1c8a1SJohn Marino
541f5b1c8a1SJohn Marino if (got_write_lock)
542f5b1c8a1SJohn Marino CRYPTO_w_unlock(lock);
543f5b1c8a1SJohn Marino else
544f5b1c8a1SJohn Marino CRYPTO_r_unlock(lock);
545f5b1c8a1SJohn Marino
546f5b1c8a1SJohn Marino return ret;
547f5b1c8a1SJohn Marino }
548