blob: 70f0585c2e7d95941ac24ae8fc9d5157adf06d4f [file] [log] [blame]
Adam Langleyd9e397b2015-01-22 14:27:53 -08001/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.]
56 */
57/* ====================================================================
58 * Copyright (c) 1998-2006 The OpenSSL Project. All rights reserved.
59 *
60 * Redistribution and use in source and binary forms, with or without
61 * modification, are permitted provided that the following conditions
62 * are met:
63 *
64 * 1. Redistributions of source code must retain the above copyright
65 * notice, this list of conditions and the following disclaimer.
66 *
67 * 2. Redistributions in binary form must reproduce the above copyright
68 * notice, this list of conditions and the following disclaimer in
69 * the documentation and/or other materials provided with the
70 * distribution.
71 *
72 * 3. All advertising materials mentioning features or use of this
73 * software must display the following acknowledgment:
74 * "This product includes software developed by the OpenSSL Project
75 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
76 *
77 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
78 * endorse or promote products derived from this software without
79 * prior written permission. For written permission, please contact
80 * openssl-core@openssl.org.
81 *
82 * 5. Products derived from this software may not be called "OpenSSL"
83 * nor may "OpenSSL" appear in their names without prior written
84 * permission of the OpenSSL Project.
85 *
86 * 6. Redistributions of any form whatsoever must retain the following
87 * acknowledgment:
88 * "This product includes software developed by the OpenSSL Project
89 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
90 *
91 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
92 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
93 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
94 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
95 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
96 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
97 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
98 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
99 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
100 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
101 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
102 * OF THE POSSIBILITY OF SUCH DAMAGE.
103 * ====================================================================
104 *
105 * This product includes cryptographic software written by Eric Young
106 * (eay@cryptsoft.com). This product includes software written by Tim
107 * Hudson (tjh@cryptsoft.com). */
108
109#include <openssl/bn.h>
110
Robert Sloan69939df2017-01-09 10:53:07 -0800111#include <assert.h>
Adam Langleyd9e397b2015-01-22 14:27:53 -0800112#include <string.h>
113
Kenny Rootb8494592015-09-25 02:29:14 +0000114#include <openssl/err.h>
Adam Langleyd9e397b2015-01-22 14:27:53 -0800115#include <openssl/mem.h>
116#include <openssl/thread.h>
117
118#include "internal.h"
Adam Langleye9ada862015-05-11 17:20:37 -0700119#include "../internal.h"
Adam Langleyd9e397b2015-01-22 14:27:53 -0800120
121
Adam Langleyfad63272015-11-12 12:15:39 -0800122#if !defined(OPENSSL_NO_ASM) && \
123 (defined(OPENSSL_X86) || defined(OPENSSL_X86_64) || \
124 defined(OPENSSL_ARM) || defined(OPENSSL_AARCH64))
Adam Langleyd9e397b2015-01-22 14:27:53 -0800125#define OPENSSL_BN_ASM_MONT
126#endif
127
128BN_MONT_CTX *BN_MONT_CTX_new(void) {
129 BN_MONT_CTX *ret = OPENSSL_malloc(sizeof(BN_MONT_CTX));
130
131 if (ret == NULL) {
132 return NULL;
133 }
134
Robert Sloan69939df2017-01-09 10:53:07 -0800135 OPENSSL_memset(ret, 0, sizeof(BN_MONT_CTX));
Kenny Roote99801b2015-11-06 15:31:15 -0800136 BN_init(&ret->RR);
137 BN_init(&ret->N);
Adam Langleyd9e397b2015-01-22 14:27:53 -0800138
Kenny Roote99801b2015-11-06 15:31:15 -0800139 return ret;
Kenny Root03bcf612015-11-05 20:20:27 +0000140}
141
Adam Langleyd9e397b2015-01-22 14:27:53 -0800142void BN_MONT_CTX_free(BN_MONT_CTX *mont) {
143 if (mont == NULL) {
144 return;
145 }
146
147 BN_free(&mont->RR);
148 BN_free(&mont->N);
Kenny Roote99801b2015-11-06 15:31:15 -0800149 OPENSSL_free(mont);
Adam Langleyd9e397b2015-01-22 14:27:53 -0800150}
151
Adam Langleyfad63272015-11-12 12:15:39 -0800152BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, const BN_MONT_CTX *from) {
Adam Langleyd9e397b2015-01-22 14:27:53 -0800153 if (to == from) {
154 return to;
155 }
156
157 if (!BN_copy(&to->RR, &from->RR) ||
Adam Langley4139edb2016-01-13 15:00:54 -0800158 !BN_copy(&to->N, &from->N)) {
Adam Langleyd9e397b2015-01-22 14:27:53 -0800159 return NULL;
160 }
Adam Langleyd9e397b2015-01-22 14:27:53 -0800161 to->n0[0] = from->n0[0];
162 to->n0[1] = from->n0[1];
163 return to;
164}
165
David Benjaminc895d6b2016-08-11 13:26:41 -0400166OPENSSL_COMPILE_ASSERT(BN_MONT_CTX_N0_LIMBS == 1 || BN_MONT_CTX_N0_LIMBS == 2,
167 BN_MONT_CTX_N0_LIMBS_VALUE_INVALID);
168OPENSSL_COMPILE_ASSERT(sizeof(BN_ULONG) * BN_MONT_CTX_N0_LIMBS ==
169 sizeof(uint64_t), BN_MONT_CTX_set_64_bit_mismatch);
Adam Langleyd9e397b2015-01-22 14:27:53 -0800170
David Benjaminc895d6b2016-08-11 13:26:41 -0400171int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) {
Kenny Rootb8494592015-09-25 02:29:14 +0000172 if (BN_is_zero(mod)) {
173 OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO);
174 return 0;
175 }
David Benjaminc895d6b2016-08-11 13:26:41 -0400176 if (!BN_is_odd(mod)) {
177 OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS);
178 return 0;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800179 }
David Benjaminc895d6b2016-08-11 13:26:41 -0400180 if (BN_is_negative(mod)) {
181 OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
182 return 0;
183 }
184
185 /* Save the modulus. */
Adam Langleyd9e397b2015-01-22 14:27:53 -0800186 if (!BN_copy(&mont->N, mod)) {
David Benjaminc895d6b2016-08-11 13:26:41 -0400187 OPENSSL_PUT_ERROR(BN, ERR_R_INTERNAL_ERROR);
188 return 0;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800189 }
David Benjaminc895d6b2016-08-11 13:26:41 -0400190 if (BN_get_flags(mod, BN_FLG_CONSTTIME)) {
191 BN_set_flags(&mont->N, BN_FLG_CONSTTIME);
Adam Langleyd9e397b2015-01-22 14:27:53 -0800192 }
193
David Benjaminc895d6b2016-08-11 13:26:41 -0400194 /* Find n0 such that n0 * N == -1 (mod r).
195 *
196 * Only certain BN_BITS2<=32 platforms actually make use of n0[1]. For the
197 * others, we could use a shorter R value and use faster |BN_ULONG|-based
198 * math instead of |uint64_t|-based math, which would be double-precision.
199 * However, currently only the assembler files know which is which. */
200 uint64_t n0 = bn_mont_n0(mod);
201 mont->n0[0] = (BN_ULONG)n0;
202#if BN_MONT_CTX_N0_LIMBS == 2
203 mont->n0[1] = (BN_ULONG)(n0 >> BN_BITS2);
Adam Langleyd9e397b2015-01-22 14:27:53 -0800204#else
Adam Langleyd9e397b2015-01-22 14:27:53 -0800205 mont->n0[1] = 0;
206#endif
207
David Benjaminc895d6b2016-08-11 13:26:41 -0400208 /* Save RR = R**2 (mod N). R is the smallest power of 2**BN_BITS such that R
209 * > mod. Even though the assembly on some 32-bit platforms works with 64-bit
210 * values, using |BN_BITS2| here, rather than |BN_MONT_CTX_N0_LIMBS *
Robert Sloan69939df2017-01-09 10:53:07 -0800211 * BN_BITS2|, is correct because R**2 will still be a multiple of the latter
212 * as |BN_MONT_CTX_N0_LIMBS| is either one or two.
213 *
214 * XXX: This is not constant time with respect to |mont->N|, but it should
215 * be. */
David Benjaminc895d6b2016-08-11 13:26:41 -0400216 unsigned lgBigR = (BN_num_bits(mod) + (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;
Robert Sloan69939df2017-01-09 10:53:07 -0800217 if (!bn_mod_exp_base_2_vartime(&mont->RR, lgBigR * 2, &mont->N)) {
David Benjaminc895d6b2016-08-11 13:26:41 -0400218 return 0;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800219 }
220
David Benjaminc895d6b2016-08-11 13:26:41 -0400221 return 1;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800222}
223
David Benjamin4969cc92016-04-22 15:02:23 -0400224int BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, CRYPTO_MUTEX *lock,
225 const BIGNUM *mod, BN_CTX *bn_ctx) {
Adam Langleye9ada862015-05-11 17:20:37 -0700226 CRYPTO_MUTEX_lock_read(lock);
227 BN_MONT_CTX *ctx = *pmont;
David Benjamind316cba2016-06-02 16:17:39 -0400228 CRYPTO_MUTEX_unlock_read(lock);
Adam Langleyd9e397b2015-01-22 14:27:53 -0800229
Adam Langleye9ada862015-05-11 17:20:37 -0700230 if (ctx) {
David Benjamin4969cc92016-04-22 15:02:23 -0400231 return 1;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800232 }
233
Adam Langleye9ada862015-05-11 17:20:37 -0700234 CRYPTO_MUTEX_lock_write(lock);
235 ctx = *pmont;
236 if (ctx) {
237 goto out;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800238 }
239
Adam Langleye9ada862015-05-11 17:20:37 -0700240 ctx = BN_MONT_CTX_new();
241 if (ctx == NULL) {
242 goto out;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800243 }
Adam Langleye9ada862015-05-11 17:20:37 -0700244 if (!BN_MONT_CTX_set(ctx, mod, bn_ctx)) {
245 BN_MONT_CTX_free(ctx);
246 ctx = NULL;
247 goto out;
248 }
249 *pmont = ctx;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800250
Adam Langleye9ada862015-05-11 17:20:37 -0700251out:
David Benjamind316cba2016-06-02 16:17:39 -0400252 CRYPTO_MUTEX_unlock_write(lock);
David Benjamin4969cc92016-04-22 15:02:23 -0400253 return ctx != NULL;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800254}
255
256int BN_to_montgomery(BIGNUM *ret, const BIGNUM *a, const BN_MONT_CTX *mont,
257 BN_CTX *ctx) {
258 return BN_mod_mul_montgomery(ret, a, &mont->RR, mont, ctx);
259}
260
Adam Langleyd9e397b2015-01-22 14:27:53 -0800261static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r,
262 const BN_MONT_CTX *mont) {
Adam Langleyd9e397b2015-01-22 14:27:53 -0800263 BN_ULONG *ap, *np, *rp, n0, v, carry;
264 int nl, max, i;
265
David Benjamin4969cc92016-04-22 15:02:23 -0400266 const BIGNUM *n = &mont->N;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800267 nl = n->top;
268 if (nl == 0) {
269 ret->top = 0;
270 return 1;
271 }
272
273 max = (2 * nl); /* carry is stored separately */
274 if (bn_wexpand(r, max) == NULL) {
275 return 0;
276 }
277
278 r->neg ^= n->neg;
279 np = n->d;
280 rp = r->d;
281
282 /* clear the top words of T */
283 if (max > r->top) {
Robert Sloan69939df2017-01-09 10:53:07 -0800284 OPENSSL_memset(&rp[r->top], 0, (max - r->top) * sizeof(BN_ULONG));
Adam Langleyd9e397b2015-01-22 14:27:53 -0800285 }
286
287 r->top = max;
288 n0 = mont->n0[0];
289
290 for (carry = 0, i = 0; i < nl; i++, rp++) {
291 v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2);
292 v = (v + carry + rp[nl]) & BN_MASK2;
293 carry |= (v != rp[nl]);
294 carry &= (v <= rp[nl]);
295 rp[nl] = v;
296 }
297
298 if (bn_wexpand(ret, nl) == NULL) {
299 return 0;
300 }
301 ret->top = nl;
302 ret->neg = r->neg;
303
304 rp = ret->d;
305 ap = &(r->d[nl]);
306
307 {
308 BN_ULONG *nrp;
David Benjamin4969cc92016-04-22 15:02:23 -0400309 uintptr_t m;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800310
311 v = bn_sub_words(rp, ap, np, nl) - carry;
312 /* if subtraction result is real, then trick unconditional memcpy below to
313 * perform in-place "refresh" instead of actual copy. */
David Benjamin4969cc92016-04-22 15:02:23 -0400314 m = (0u - (uintptr_t)v);
315 nrp = (BN_ULONG *)(((uintptr_t)rp & ~m) | ((uintptr_t)ap & m));
Adam Langleyd9e397b2015-01-22 14:27:53 -0800316
317 for (i = 0, nl -= 4; i < nl; i += 4) {
318 BN_ULONG t1, t2, t3, t4;
319
320 t1 = nrp[i + 0];
321 t2 = nrp[i + 1];
322 t3 = nrp[i + 2];
323 ap[i + 0] = 0;
324 t4 = nrp[i + 3];
325 ap[i + 1] = 0;
326 rp[i + 0] = t1;
327 ap[i + 2] = 0;
328 rp[i + 1] = t2;
329 ap[i + 3] = 0;
330 rp[i + 2] = t3;
331 rp[i + 3] = t4;
332 }
333
334 for (nl += 4; i < nl; i++) {
335 rp[i] = nrp[i], ap[i] = 0;
336 }
337 }
338
339 bn_correct_top(r);
340 bn_correct_top(ret);
341
342 return 1;
343}
Adam Langleyd9e397b2015-01-22 14:27:53 -0800344
David Benjamin4969cc92016-04-22 15:02:23 -0400345int BN_from_montgomery(BIGNUM *r, const BIGNUM *a, const BN_MONT_CTX *mont,
Adam Langleyd9e397b2015-01-22 14:27:53 -0800346 BN_CTX *ctx) {
David Benjamin4969cc92016-04-22 15:02:23 -0400347 int ret = 0;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800348 BIGNUM *t;
349
350 BN_CTX_start(ctx);
351 t = BN_CTX_get(ctx);
David Benjamin4969cc92016-04-22 15:02:23 -0400352 if (t == NULL ||
353 !BN_copy(t, a)) {
354 goto err;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800355 }
356
David Benjamin4969cc92016-04-22 15:02:23 -0400357 ret = BN_from_montgomery_word(r, t, mont);
358
359err:
Adam Langleyd9e397b2015-01-22 14:27:53 -0800360 BN_CTX_end(ctx);
361
David Benjamin4969cc92016-04-22 15:02:23 -0400362 return ret;
Adam Langleyd9e397b2015-01-22 14:27:53 -0800363}
364
365int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
366 const BN_MONT_CTX *mont, BN_CTX *ctx) {
367 BIGNUM *tmp;
368 int ret = 0;
369
370#if defined(OPENSSL_BN_ASM_MONT)
371 int num = mont->N.top;
372
373 if (num > 1 && a->top == num && b->top == num) {
374 if (bn_wexpand(r, num) == NULL) {
375 return 0;
376 }
377 if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {
378 r->neg = a->neg ^ b->neg;
379 r->top = num;
380 bn_correct_top(r);
381 return 1;
382 }
383 }
384#endif
385
386 BN_CTX_start(ctx);
387 tmp = BN_CTX_get(ctx);
388 if (tmp == NULL) {
389 goto err;
390 }
391
392 if (a == b) {
393 if (!BN_sqr(tmp, a, ctx)) {
394 goto err;
395 }
396 } else {
397 if (!BN_mul(tmp, a, b, ctx)) {
398 goto err;
399 }
400 }
401
402 /* reduce from aRR to aR */
403 if (!BN_from_montgomery_word(r, tmp, mont)) {
404 goto err;
405 }
406
407 ret = 1;
408
409err:
410 BN_CTX_end(ctx);
411 return ret;
412}