Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libcrypto/bn/bn_mont.c	Lines:	144	160	90.0 %
Date:	2017-11-07	Branches:	78	113	69.0 %


/* $OpenBSD: bn_mont.c,v 1.26 2017/01/21 11:00:46 beck Exp $ */
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
 * All rights reserved.
 *
 * This package is an SSL implementation written
 * by Eric Young (eay@cryptsoft.com).
 * The implementation was written so as to conform with Netscapes SSL.
 *
 * This library is free for commercial and non-commercial use as long as
 * the following conditions are aheared to.  The following conditions
 * apply to all code found in this distribution, be it the RC4, RSA,
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 * included with this distribution is covered by the same copyright terms
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
 *
 * Copyright remains Eric Young's, and as such any Copyright notices in
 * the code are not to be removed.
 * If this package is used in a product, Eric Young should be given attribution
 * as the author of the parts of the library used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    "This product includes cryptographic software written by
 *     Eric Young (eay@cryptsoft.com)"
 *    The word 'cryptographic' can be left out if the rouines from the library
 *    being used are not cryptographic related :-).
 * 4. If you include any Windows specific code (or a derivative thereof) from
 *    the apps directory (application code) you must include an acknowledgement:
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
 *
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */
/* ====================================================================
 * Copyright (c) 1998-2006 The OpenSSL Project.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. All advertising materials mentioning features or use of this
 *    software must display the following acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
 *
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
 *    endorse or promote products derived from this software without
 *    prior written permission. For written permission, please contact
 *    openssl-core@openssl.org.
 *
 * 5. Products derived from this software may not be called "OpenSSL"
 *    nor may "OpenSSL" appear in their names without prior written
 *    permission of the OpenSSL Project.
 *
 * 6. Redistributions of any form whatsoever must retain the following
 *    acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
 *
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 * ====================================================================
 *
 * This product includes cryptographic software written by Eric Young
 * (eay@cryptsoft.com).  This product includes software written by Tim
 * Hudson (tjh@cryptsoft.com).
 *
 */

/*
 * Details about Montgomery multiplication algorithms can be found at
 * http://security.ece.orst.edu/publications.html, e.g.
 * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
 * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
 */

#include <stdio.h>
#include <stdint.h>

#include "bn_lcl.h"

#define MONT_WORD /* use the faster word-based algorithm */

#ifdef MONT_WORD
static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
#endif

int
BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
    BN_MONT_CTX *mont, BN_CTX *ctx)
{
	BIGNUM *tmp;
	int ret = 0;
#if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
	int num = mont->N.top;

	if (num > 1 && a->top == num && b->top == num) {
		if (bn_wexpand(r, num) == NULL)
			return (0);
		if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {
			r->neg = a->neg^b->neg;
			r->top = num;
			bn_correct_top(r);
			return (1);
		}
	}
#endif

	BN_CTX_start(ctx);
	if ((tmp = BN_CTX_get(ctx)) == NULL)
		goto err;

	bn_check_top(tmp);
	if (a == b) {
		if (!BN_sqr(tmp, a, ctx))
			goto err;
	} else {
		if (!BN_mul(tmp, a,b, ctx))
			goto err;
	}
	/* reduce from aRR to aR */
#ifdef MONT_WORD
	if (!BN_from_montgomery_word(r, tmp, mont))
		goto err;
#else
	if (!BN_from_montgomery(r, tmp, mont, ctx))
		goto err;
#endif
	bn_check_top(r);
	ret = 1;
err:
	BN_CTX_end(ctx);
	return (ret);
}

#ifdef MONT_WORD
static int
BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
{
	BIGNUM *n;
	BN_ULONG *ap, *np, *rp, n0, v, carry;
	int nl, max, i;

	n = &(mont->N);
	nl = n->top;
	if (nl == 0) {
		ret->top = 0;
		return (1);
	}

	max = (2 * nl); /* carry is stored separately */
	if (bn_wexpand(r, max) == NULL)
		return (0);

	r->neg ^= n->neg;
	np = n->d;
	rp = r->d;

	/* clear the top words of T */
#if 1
	for (i=r->top; i<max; i++) /* memset? XXX */
		rp[i] = 0;
#else
	memset(&(rp[r->top]), 0, (max - r->top) * sizeof(BN_ULONG));
#endif

	r->top = max;
	n0 = mont->n0[0];

#ifdef BN_COUNT
	fprintf(stderr, "word BN_from_montgomery_word %d * %d\n", nl, nl);
#endif
	for (carry = 0, i = 0; i < nl; i++, rp++) {
		v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2);
		v = (v + carry + rp[nl]) & BN_MASK2;
		carry |= (v != rp[nl]);
		carry &= (v <= rp[nl]);
		rp[nl] = v;
	}

	if (bn_wexpand(ret, nl) == NULL)
		return (0);
	ret->top = nl;
	ret->neg = r->neg;

	rp = ret->d;
	ap = &(r->d[nl]);

#define BRANCH_FREE 1
#if BRANCH_FREE
	{
		BN_ULONG *nrp;
		size_t m;

		v = bn_sub_words(rp, ap, np, nl) - carry;
		/* if subtraction result is real, then
		 * trick unconditional memcpy below to perform in-place
		 * "refresh" instead of actual copy. */
		m = (0 - (size_t)v);
		nrp = (BN_ULONG *)(((uintptr_t)rp & ~m)|((uintptr_t)ap & m));

		for (i = 0, nl -= 4; i < nl; i += 4) {
			BN_ULONG t1, t2, t3, t4;

			t1 = nrp[i + 0];
			t2 = nrp[i + 1];
			t3 = nrp[i + 2];
			ap[i + 0] = 0;
			t4 = nrp[i + 3];
			ap[i + 1] = 0;
			rp[i + 0] = t1;
			ap[i + 2] = 0;
			rp[i + 1] = t2;
			ap[i + 3] = 0;
			rp[i + 2] = t3;
			rp[i + 3] = t4;
		}
		for (nl += 4; i < nl; i++)
			rp[i] = nrp[i], ap[i] = 0;
	}
#else
	if (bn_sub_words (rp, ap, np, nl) - carry)
		memcpy(rp, ap, nl*sizeof(BN_ULONG));
#endif
	bn_correct_top(r);
	bn_correct_top(ret);
	bn_check_top(ret);

	return (1);
}
#endif	/* MONT_WORD */

int
BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx)
{
	int retn = 0;
#ifdef MONT_WORD
	BIGNUM *t;

	BN_CTX_start(ctx);
	if ((t = BN_CTX_get(ctx)) && BN_copy(t, a))
		retn = BN_from_montgomery_word(ret, t, mont);
	BN_CTX_end(ctx);
#else /* !MONT_WORD */
	BIGNUM *t1, *t2;

	BN_CTX_start(ctx);
	if ((t1 = BN_CTX_get(ctx)) == NULL)
		goto err;
	if ((t2 = BN_CTX_get(ctx)) == NULL)
		goto err;

	if (!BN_copy(t1, a))
		goto err;
	BN_mask_bits(t1, mont->ri);

	if (!BN_mul(t2, t1, &mont->Ni, ctx))
		goto err;
	BN_mask_bits(t2, mont->ri);

	if (!BN_mul(t1, t2, &mont->N, ctx))
		goto err;
	if (!BN_add(t2, a, t1))
		goto err;
	if (!BN_rshift(ret, t2, mont->ri))
		goto err;

	if (BN_ucmp(ret, &(mont->N)) >= 0) {
		if (!BN_usub(ret, ret, &(mont->N)))
			goto err;
	}
	retn = 1;
	bn_check_top(ret);

err:
	BN_CTX_end(ctx);
#endif /* MONT_WORD */
	return (retn);
}

BN_MONT_CTX *
BN_MONT_CTX_new(void)
{
	BN_MONT_CTX *ret;

	if ((ret = malloc(sizeof(BN_MONT_CTX))) == NULL)
		return (NULL);

	BN_MONT_CTX_init(ret);
	ret->flags = BN_FLG_MALLOCED;
	return (ret);
}

void
BN_MONT_CTX_init(BN_MONT_CTX *ctx)
{
	ctx->ri = 0;
	BN_init(&(ctx->RR));
	BN_init(&(ctx->N));
	BN_init(&(ctx->Ni));
	ctx->n0[0] = ctx->n0[1] = 0;
	ctx->flags = 0;
}

void
BN_MONT_CTX_free(BN_MONT_CTX *mont)
{
	if (mont == NULL)
		return;

	BN_clear_free(&(mont->RR));
	BN_clear_free(&(mont->N));
	BN_clear_free(&(mont->Ni));
	if (mont->flags & BN_FLG_MALLOCED)
		free(mont);
}

int
BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
{
	int ret = 0;
	BIGNUM *Ri, *R;

	BN_CTX_start(ctx);
	if ((Ri = BN_CTX_get(ctx)) == NULL)
		goto err;
	R = &(mont->RR);				/* grab RR as a temp */
	if (!BN_copy(&(mont->N), mod))
		 goto err;				/* Set N */
	mont->N.neg = 0;

#ifdef MONT_WORD
	{
		BIGNUM tmod;
		BN_ULONG buf[2];

		BN_init(&tmod);
		tmod.d = buf;
		tmod.dmax = 2;
		tmod.neg = 0;

		mont->ri = (BN_num_bits(mod) +
		    (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;

#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
		/* Only certain BN_BITS2<=32 platforms actually make use of
		 * n0[1], and we could use the #else case (with a shorter R
		 * value) for the others.  However, currently only the assembler
		 * files do know which is which. */

		BN_zero(R);
		if (!(BN_set_bit(R, 2 * BN_BITS2)))
			goto err;

		tmod.top = 0;
		if ((buf[0] = mod->d[0]))
			tmod.top = 1;
		if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
			tmod.top = 2;

		if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
			goto err;
		if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
			goto err; /* R*Ri */
		if (!BN_is_zero(Ri)) {
			if (!BN_sub_word(Ri, 1))
				goto err;
		}
		else /* if N mod word size == 1 */
		{
			if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL)
				goto err;
			/* Ri-- (mod double word size) */
			Ri->neg = 0;
			Ri->d[0] = BN_MASK2;
			Ri->d[1] = BN_MASK2;
			Ri->top = 2;
		}
		if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
			goto err;
		/* Ni = (R*Ri-1)/N,
		 * keep only couple of least significant words: */
		mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
		mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
#else
		BN_zero(R);
		if (!(BN_set_bit(R, BN_BITS2)))
			goto err;	/* R */

		buf[0] = mod->d[0]; /* tmod = N mod word size */
		buf[1] = 0;
		tmod.top = buf[0] != 0 ? 1 : 0;
		/* Ri = R^-1 mod N*/
		if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
			goto err;
		if (!BN_lshift(Ri, Ri, BN_BITS2))
			goto err; /* R*Ri */
		if (!BN_is_zero(Ri)) {
			if (!BN_sub_word(Ri, 1))
				goto err;
		}
		else /* if N mod word size == 1 */
		{
			if (!BN_set_word(Ri, BN_MASK2))
				goto err;  /* Ri-- (mod word size) */
		}
		if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
			goto err;
		/* Ni = (R*Ri-1)/N,
		 * keep only least significant word: */
		mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
		mont->n0[1] = 0;
#endif
	}
#else /* !MONT_WORD */
	{ /* bignum version */
		mont->ri = BN_num_bits(&mont->N);
		BN_zero(R);
		if (!BN_set_bit(R, mont->ri))
			goto err;  /* R = 2^ri */
		/* Ri = R^-1 mod N*/
		if ((BN_mod_inverse_ct(Ri, R, &mont->N, ctx)) == NULL)
			goto err;
		if (!BN_lshift(Ri, Ri, mont->ri))
			goto err; /* R*Ri */
		if (!BN_sub_word(Ri, 1))
			goto err;
		/* Ni = (R*Ri-1) / N */
		if (!BN_div_ct(&(mont->Ni), NULL, Ri, &mont->N, ctx))
			goto err;
	}
#endif

	/* setup RR for conversions */
	BN_zero(&(mont->RR));
	if (!BN_set_bit(&(mont->RR), mont->ri*2))
		goto err;
	if (!BN_mod_ct(&(mont->RR), &(mont->RR), &(mont->N), ctx))
		goto err;

	ret = 1;

err:
	BN_CTX_end(ctx);
	return ret;
}

BN_MONT_CTX *
BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
{
	if (to == from)
		return (to);

	if (!BN_copy(&(to->RR), &(from->RR)))
		return NULL;
	if (!BN_copy(&(to->N), &(from->N)))
		return NULL;
	if (!BN_copy(&(to->Ni), &(from->Ni)))
		return NULL;
	to->ri = from->ri;
	to->n0[0] = from->n0[0];
	to->n0[1] = from->n0[1];
	return (to);
}

BN_MONT_CTX *
BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, const BIGNUM *mod,
    BN_CTX *ctx)
{
	int got_write_lock = 0;
	BN_MONT_CTX *ret;

	CRYPTO_r_lock(lock);
	if (!*pmont) {
		CRYPTO_r_unlock(lock);
		CRYPTO_w_lock(lock);
		got_write_lock = 1;

		if (!*pmont) {
			ret = BN_MONT_CTX_new();
			if (ret && !BN_MONT_CTX_set(ret, mod, ctx))
				BN_MONT_CTX_free(ret);
			else
				*pmont = ret;
		}
	}

	ret = *pmont;

	if (got_write_lock)
		CRYPTO_w_unlock(lock);
	else
		CRYPTO_r_unlock(lock);

	return ret;
}


Generated by: GCOVR (Version 3.3)

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