1/*
2 * Copyright (c) 2000-2001,2011,2014 Apple Inc. All Rights Reserved.
3 *
4 * The contents of this file constitute Original Code as defined in and are
5 * subject to the Apple Public Source License Version 1.2 (the 'License').
6 * You may not use this file except in compliance with the License. Please obtain
7 * a copy of the License at http://www.apple.com/publicsource and read it before
8 * using this file.
9 *
10 * This Original Code and all software distributed under the License are
11 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
12 * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
13 * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
14 * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
15 * specific language governing rights and limitations under the License.
16 */
17
18
19/* crypto/bn/bn_mont.c */
20/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
21 * All rights reserved.
22 *
23 * This package is an SSL implementation written
24 * by Eric Young (eay@cryptsoft.com).
25 * The implementation was written so as to conform with Netscapes SSL.
26 *
27 * This library is free for commercial and non-commercial use as long as
28 * the following conditions are aheared to.  The following conditions
29 * apply to all code found in this distribution, be it the RC4, RSA,
30 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
31 * included with this distribution is covered by the same copyright terms
32 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
33 *
34 * Copyright remains Eric Young's, and as such any Copyright notices in
35 * the code are not to be removed.
36 * If this package is used in a product, Eric Young should be given attribution
37 * as the author of the parts of the library used.
38 * This can be in the form of a textual message at program startup or
39 * in documentation (online or textual) provided with the package.
40 *
41 * Redistribution and use in source and binary forms, with or without
42 * modification, are permitted provided that the following conditions
43 * are met:
44 * 1. Redistributions of source code must retain the copyright
45 *    notice, this list of conditions and the following disclaimer.
46 * 2. Redistributions in binary form must reproduce the above copyright
47 *    notice, this list of conditions and the following disclaimer in the
48 *    documentation and/or other materials provided with the distribution.
49 * 3. All advertising materials mentioning features or use of this software
50 *    must display the following acknowledgement:
51 *    "This product includes cryptographic software written by
52 *     Eric Young (eay@cryptsoft.com)"
53 *    The word 'cryptographic' can be left out if the rouines from the library
54 *    being used are not cryptographic related :-).
55 * 4. If you include any Windows specific code (or a derivative thereof) from
56 *    the apps directory (application code) you must include an acknowledgement:
57 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
58 *
59 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
60 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
61 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
62 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
63 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
64 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
65 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
66 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
67 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
68 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
69 * SUCH DAMAGE.
70 *
71 * The licence and distribution terms for any publically available version or
72 * derivative of this code cannot be changed.  i.e. this code cannot simply be
73 * copied and put under another distribution licence
74 * [including the GNU Public Licence.]
75 */
76
77/*
78 * Details about Montgomery multiplication algorithms can be found at
79 * http://security.ece.orst.edu/publications.html, e.g.
80 * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
81 * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
82 */
83
84#include <stdio.h>
85#include "cryptlib.h"
86#include "bn_lcl.h"
87
88#define MONT_WORD /* use the faster word-based algorithm */
89
90int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
91			  BN_MONT_CTX *mont, BN_CTX *ctx)
92	{
93	BIGNUM *tmp,*tmp2;
94	int ret=0;
95
96	BN_CTX_start(ctx);
97	tmp = BN_CTX_get(ctx);
98	tmp2 = BN_CTX_get(ctx);
99	if (tmp == NULL || tmp2 == NULL) goto err;
100
101	bn_check_top(tmp);
102	bn_check_top(tmp2);
103
104	if (a == b)
105		{
106#if 0
107		bn_wexpand(tmp,a->top*2);
108		bn_wexpand(tmp2,a->top*4);
109		bn_sqr_recursive(tmp->d,a->d,a->top,tmp2->d);
110		tmp->top=a->top*2;
111		if (tmp->d[tmp->top-1] == 0)
112			tmp->top--;
113#else
114		if (!BN_sqr(tmp,a,ctx)) goto err;
115#endif
116		}
117	else
118		{
119		if (!BN_mul(tmp,a,b,ctx)) goto err;
120		}
121	/* reduce from aRR to aR */
122	if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
123	ret=1;
124err:
125	BN_CTX_end(ctx);
126	return(ret);
127	}
128
129int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont,
130	     BN_CTX *ctx)
131	{
132	int retn=0;
133
134#ifdef MONT_WORD
135	BIGNUM *n,*r;
136	BN_ULONG *ap,*np,*rp,n0,v,*nrp;
137	int al,nl,max,i,x,ri;
138
139	BN_CTX_start(ctx);
140	if ((r = BN_CTX_get(ctx)) == NULL) goto err;
141
142	if (!BN_copy(r,a)) goto err;
143	n= &(mont->N);
144
145	ap=a->d;
146	/* mont->ri is the size of mont->N in bits (rounded up
147	   to the word size) */
148	al=ri=mont->ri/BN_BITS2;
149
150	nl=n->top;
151	if ((al == 0) || (nl == 0)) { r->top=0; return(1); }
152
153	max=(nl+al+1); /* allow for overflow (no?) XXX */
154	if (bn_wexpand(r,max) == NULL) goto err;
155	if (bn_wexpand(ret,max) == NULL) goto err;
156
157	r->neg=a->neg^n->neg;
158	np=n->d;
159	rp=r->d;
160	nrp= &(r->d[nl]);
161
162	/* clear the top words of T */
163#if 1
164	for (i=r->top; i<max; i++) /* memset? XXX */
165		r->d[i]=0;
166#else
167	memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG));
168#endif
169
170	r->top=max;
171	n0=mont->n0;
172
173#ifdef BN_COUNT
174	printf("word BN_from_montgomery %d * %d\n",nl,nl);
175#endif
176	for (i=0; i<nl; i++)
177		{
178		v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
179		nrp++;
180		rp++;
181		if (((nrp[-1]+=v)&BN_MASK2) >= v)
182			continue;
183		else
184			{
185			if (((++nrp[0])&BN_MASK2) != 0) continue;
186			if (((++nrp[1])&BN_MASK2) != 0) continue;
187			for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ;
188			}
189		}
190	bn_fix_top(r);
191
192	/* mont->ri will be a multiple of the word size */
193#if 0
194	BN_rshift(ret,r,mont->ri);
195#else
196	x=ri;
197	rp=ret->d;
198	ap= &(r->d[x]);
199	if (r->top < x)
200		al=0;
201	else
202		al=r->top-x;
203	ret->top=al;
204	al-=4;
205	for (i=0; i<al; i+=4)
206		{
207		BN_ULONG t1,t2,t3,t4;
208
209		t1=ap[i+0];
210		t2=ap[i+1];
211		t3=ap[i+2];
212		t4=ap[i+3];
213		rp[i+0]=t1;
214		rp[i+1]=t2;
215		rp[i+2]=t3;
216		rp[i+3]=t4;
217		}
218	al+=4;
219	for (; i<al; i++)
220		rp[i]=ap[i];
221#endif
222#else /* !MONT_WORD */
223	BIGNUM *t1,*t2;
224
225	BN_CTX_start(ctx);
226	t1 = BN_CTX_get(ctx);
227	t2 = BN_CTX_get(ctx);
228	if (t1 == NULL || t2 == NULL) goto err;
229
230	if (!BN_copy(t1,a)) goto err;
231	BN_mask_bits(t1,mont->ri);
232
233	if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err;
234	BN_mask_bits(t2,mont->ri);
235
236	if (!BN_mul(t1,t2,&mont->N,ctx)) goto err;
237	if (!BN_add(t2,a,t1)) goto err;
238	BN_rshift(ret,t2,mont->ri);
239#endif /* MONT_WORD */
240
241	if (BN_ucmp(ret, &(mont->N)) >= 0)
242		{
243		BN_usub(ret,ret,&(mont->N));
244		}
245	retn=1;
246 err:
247	BN_CTX_end(ctx);
248	return(retn);
249	}
250
251BN_MONT_CTX *BN_MONT_CTX_new(void)
252	{
253	BN_MONT_CTX *ret;
254
255	if ((ret=(BN_MONT_CTX *)Malloc(sizeof(BN_MONT_CTX))) == NULL)
256		return(NULL);
257
258	BN_MONT_CTX_init(ret);
259	ret->flags=BN_FLG_MALLOCED;
260	return(ret);
261	}
262
263void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
264	{
265	ctx->ri=0;
266	BN_init(&(ctx->RR));
267	BN_init(&(ctx->N));
268	BN_init(&(ctx->Ni));
269	ctx->flags=0;
270	}
271
272void BN_MONT_CTX_free(BN_MONT_CTX *mont)
273	{
274	if(mont == NULL)
275	    return;
276
277	BN_free(&(mont->RR));
278	BN_free(&(mont->N));
279	BN_free(&(mont->Ni));
280	if (mont->flags & BN_FLG_MALLOCED)
281		Free(mont);
282	}
283
284int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
285	{
286	BIGNUM Ri,*R;
287
288	BN_init(&Ri);
289	R= &(mont->RR);					/* grab RR as a temp */
290	BN_copy(&(mont->N),mod);			/* Set N */
291
292#ifdef MONT_WORD
293		{
294		BIGNUM tmod;
295		BN_ULONG buf[2];
296
297		mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
298		BN_zero(R);
299		BN_set_bit(R,BN_BITS2);			/* R */
300
301		buf[0]=mod->d[0]; /* tmod = N mod word size */
302		buf[1]=0;
303		tmod.d=buf;
304		tmod.top=1;
305		tmod.max=2;
306		tmod.neg=mod->neg;
307							/* Ri = R^-1 mod N*/
308		if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL)
309			goto err;
310		BN_lshift(&Ri,&Ri,BN_BITS2);		/* R*Ri */
311		if (!BN_is_zero(&Ri))
312			BN_sub_word(&Ri,1);
313		else /* if N mod word size == 1 */
314			BN_set_word(&Ri,BN_MASK2);  /* Ri-- (mod word size) */
315		BN_div(&Ri,NULL,&Ri,&tmod,ctx);	/* Ni = (R*Ri-1)/N,
316		                                 * keep only least significant word: */
317		mont->n0=Ri.d[0];
318		BN_free(&Ri);
319		}
320#else /* !MONT_WORD */
321		{ /* bignum version */
322		mont->ri=BN_num_bits(mod);
323		BN_zero(R);
324		BN_set_bit(R,mont->ri);			/* R = 2^ri */
325							/* Ri = R^-1 mod N*/
326		if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL)
327			goto err;
328		BN_lshift(&Ri,&Ri,mont->ri);		/* R*Ri */
329		BN_sub_word(&Ri,1);
330							/* Ni = (R*Ri-1) / N */
331		BN_div(&(mont->Ni),NULL,&Ri,mod,ctx);
332		BN_free(&Ri);
333		}
334#endif
335
336	/* setup RR for conversions */
337	BN_zero(&(mont->RR));
338	BN_set_bit(&(mont->RR),mont->ri*2);
339	BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx);
340
341	return(1);
342err:
343	return(0);
344	}
345
346BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
347	{
348	if (to == from) return(to);
349
350	BN_copy(&(to->RR),&(from->RR));
351	BN_copy(&(to->N),&(from->N));
352	BN_copy(&(to->Ni),&(from->Ni));
353	to->ri=from->ri;
354	to->n0=from->n0;
355	return(to);
356	}
357
358