OpenSSL  1.0.1c
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Macros
bn_mont.c
Go to the documentation of this file.
1 /* crypto/bn/bn_mont.c */
2 /* Copyright (C) 1995-1998 Eric Young ([email protected])
3  * All rights reserved.
4  *
5  * This package is an SSL implementation written
6  * by Eric Young ([email protected]).
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 ([email protected]).
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 ([email protected])"
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 ([email protected])"
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  * [email protected].
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  * ([email protected]). This product includes software written by Tim
108  * Hudson ([email protected]).
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 "cryptlib.h"
121 #include "bn_lcl.h"
122 
123 #define MONT_WORD /* use the faster word-based algorithm */
124 
125 #ifdef MONT_WORD
126 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
127 #endif
128 
129 int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
130  BN_MONT_CTX *mont, BN_CTX *ctx)
131  {
132  BIGNUM *tmp;
133  int ret=0;
134 #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
135  int num = mont->N.top;
136 
137  if (num>1 && a->top==num && b->top==num)
138  {
139  if (bn_wexpand(r,num) == NULL) return(0);
140  if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,mont->n0,num))
141  {
142  r->neg = a->neg^b->neg;
143  r->top = num;
144  bn_correct_top(r);
145  return(1);
146  }
147  }
148 #endif
149 
150  BN_CTX_start(ctx);
151  tmp = BN_CTX_get(ctx);
152  if (tmp == NULL) goto err;
153 
154  bn_check_top(tmp);
155  if (a == b)
156  {
157  if (!BN_sqr(tmp,a,ctx)) goto err;
158  }
159  else
160  {
161  if (!BN_mul(tmp,a,b,ctx)) goto err;
162  }
163  /* reduce from aRR to aR */
164 #ifdef MONT_WORD
165  if (!BN_from_montgomery_word(r,tmp,mont)) goto err;
166 #else
167  if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
168 #endif
169  bn_check_top(r);
170  ret=1;
171 err:
172  BN_CTX_end(ctx);
173  return(ret);
174  }
175 
176 #ifdef MONT_WORD
177 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
178  {
179  BIGNUM *n;
180  BN_ULONG *ap,*np,*rp,n0,v,carry;
181  int nl,max,i;
182 
183  n= &(mont->N);
184  nl=n->top;
185  if (nl == 0) { ret->top=0; return(1); }
186 
187  max=(2*nl); /* carry is stored separately */
188  if (bn_wexpand(r,max) == NULL) return(0);
189 
190  r->neg^=n->neg;
191  np=n->d;
192  rp=r->d;
193 
194  /* clear the top words of T */
195 #if 1
196  for (i=r->top; i<max; i++) /* memset? XXX */
197  rp[i]=0;
198 #else
199  memset(&(rp[r->top]),0,(max-r->top)*sizeof(BN_ULONG));
200 #endif
201 
202  r->top=max;
203  n0=mont->n0[0];
204 
205 #ifdef BN_COUNT
206  fprintf(stderr,"word BN_from_montgomery_word %d * %d\n",nl,nl);
207 #endif
208  for (carry=0, i=0; i<nl; i++, rp++)
209  {
210 #ifdef __TANDEM
211  {
212  long long t1;
213  long long t2;
214  long long t3;
215  t1 = rp[0] * (n0 & 0177777);
216  t2 = 037777600000l;
217  t2 = n0 & t2;
218  t3 = rp[0] & 0177777;
219  t2 = (t3 * t2) & BN_MASK2;
220  t1 = t1 + t2;
221  v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1);
222  }
223 #else
224  v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
225 #endif
226  v = (v+carry+rp[nl])&BN_MASK2;
227  carry |= (v != rp[nl]);
228  carry &= (v <= rp[nl]);
229  rp[nl]=v;
230  }
231 
232  if (bn_wexpand(ret,nl) == NULL) return(0);
233  ret->top=nl;
234  ret->neg=r->neg;
235 
236  rp=ret->d;
237  ap=&(r->d[nl]);
238 
239 #define BRANCH_FREE 1
240 #if BRANCH_FREE
241  {
242  BN_ULONG *nrp;
243  size_t m;
244 
245  v=bn_sub_words(rp,ap,np,nl)-carry;
246  /* if subtraction result is real, then
247  * trick unconditional memcpy below to perform in-place
248  * "refresh" instead of actual copy. */
249  m=(0-(size_t)v);
250  nrp=(BN_ULONG *)(((PTR_SIZE_INT)rp&~m)|((PTR_SIZE_INT)ap&m));
251 
252  for (i=0,nl-=4; i<nl; i+=4)
253  {
254  BN_ULONG t1,t2,t3,t4;
255 
256  t1=nrp[i+0];
257  t2=nrp[i+1];
258  t3=nrp[i+2]; ap[i+0]=0;
259  t4=nrp[i+3]; ap[i+1]=0;
260  rp[i+0]=t1; ap[i+2]=0;
261  rp[i+1]=t2; ap[i+3]=0;
262  rp[i+2]=t3;
263  rp[i+3]=t4;
264  }
265  for (nl+=4; i<nl; i++)
266  rp[i]=nrp[i], ap[i]=0;
267  }
268 #else
269  if (bn_sub_words (rp,ap,np,nl)-carry)
270  memcpy(rp,ap,nl*sizeof(BN_ULONG));
271 #endif
272  bn_correct_top(r);
273  bn_correct_top(ret);
274  bn_check_top(ret);
275 
276  return(1);
277  }
278 #endif /* MONT_WORD */
279 
280 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
281  BN_CTX *ctx)
282  {
283  int retn=0;
284 #ifdef MONT_WORD
285  BIGNUM *t;
286 
287  BN_CTX_start(ctx);
288  if ((t = BN_CTX_get(ctx)) && BN_copy(t,a))
289  retn = BN_from_montgomery_word(ret,t,mont);
290  BN_CTX_end(ctx);
291 #else /* !MONT_WORD */
292  BIGNUM *t1,*t2;
293 
294  BN_CTX_start(ctx);
295  t1 = BN_CTX_get(ctx);
296  t2 = BN_CTX_get(ctx);
297  if (t1 == NULL || t2 == NULL) goto err;
298 
299  if (!BN_copy(t1,a)) goto err;
300  BN_mask_bits(t1,mont->ri);
301 
302  if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err;
303  BN_mask_bits(t2,mont->ri);
304 
305  if (!BN_mul(t1,t2,&mont->N,ctx)) goto err;
306  if (!BN_add(t2,a,t1)) goto err;
307  if (!BN_rshift(ret,t2,mont->ri)) goto err;
308 
309  if (BN_ucmp(ret, &(mont->N)) >= 0)
310  {
311  if (!BN_usub(ret,ret,&(mont->N))) goto err;
312  }
313  retn=1;
314  bn_check_top(ret);
315  err:
316  BN_CTX_end(ctx);
317 #endif /* MONT_WORD */
318  return(retn);
319  }
320 
321 BN_MONT_CTX *BN_MONT_CTX_new(void)
322  {
323  BN_MONT_CTX *ret;
324 
325  if ((ret=(BN_MONT_CTX *)OPENSSL_malloc(sizeof(BN_MONT_CTX))) == NULL)
326  return(NULL);
327 
328  BN_MONT_CTX_init(ret);
329  ret->flags=BN_FLG_MALLOCED;
330  return(ret);
331  }
332 
333 void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
334  {
335  ctx->ri=0;
336  BN_init(&(ctx->RR));
337  BN_init(&(ctx->N));
338  BN_init(&(ctx->Ni));
339  ctx->n0[0] = ctx->n0[1] = 0;
340  ctx->flags=0;
341  }
342 
343 void BN_MONT_CTX_free(BN_MONT_CTX *mont)
344  {
345  if(mont == NULL)
346  return;
347 
348  BN_free(&(mont->RR));
349  BN_free(&(mont->N));
350  BN_free(&(mont->Ni));
351  if (mont->flags & BN_FLG_MALLOCED)
352  OPENSSL_free(mont);
353  }
354 
355 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
356  {
357  int ret = 0;
358  BIGNUM *Ri,*R;
359 
360  BN_CTX_start(ctx);
361  if((Ri = BN_CTX_get(ctx)) == NULL) goto err;
362  R= &(mont->RR); /* grab RR as a temp */
363  if (!BN_copy(&(mont->N),mod)) goto err; /* Set N */
364  mont->N.neg = 0;
365 
366 #ifdef MONT_WORD
367  {
368  BIGNUM tmod;
369  BN_ULONG buf[2];
370 
371  BN_init(&tmod);
372  tmod.d=buf;
373  tmod.dmax=2;
374  tmod.neg=0;
375 
376  mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
377 
378 #if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
379  /* Only certain BN_BITS2<=32 platforms actually make use of
380  * n0[1], and we could use the #else case (with a shorter R
381  * value) for the others. However, currently only the assembler
382  * files do know which is which. */
383 
384  BN_zero(R);
385  if (!(BN_set_bit(R,2*BN_BITS2))) goto err;
386 
387  tmod.top=0;
388  if ((buf[0] = mod->d[0])) tmod.top=1;
389  if ((buf[1] = mod->top>1 ? mod->d[1] : 0)) tmod.top=2;
390 
391  if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL)
392  goto err;
393  if (!BN_lshift(Ri,Ri,2*BN_BITS2)) goto err; /* R*Ri */
394  if (!BN_is_zero(Ri))
395  {
396  if (!BN_sub_word(Ri,1)) goto err;
397  }
398  else /* if N mod word size == 1 */
399  {
400  if (bn_expand(Ri,(int)sizeof(BN_ULONG)*2) == NULL)
401  goto err;
402  /* Ri-- (mod double word size) */
403  Ri->neg=0;
404  Ri->d[0]=BN_MASK2;
405  Ri->d[1]=BN_MASK2;
406  Ri->top=2;
407  }
408  if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err;
409  /* Ni = (R*Ri-1)/N,
410  * keep only couple of least significant words: */
411  mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
412  mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
413 #else
414  BN_zero(R);
415  if (!(BN_set_bit(R,BN_BITS2))) goto err; /* R */
416 
417  buf[0]=mod->d[0]; /* tmod = N mod word size */
418  buf[1]=0;
419  tmod.top = buf[0] != 0 ? 1 : 0;
420  /* Ri = R^-1 mod N*/
421  if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL)
422  goto err;
423  if (!BN_lshift(Ri,Ri,BN_BITS2)) goto err; /* R*Ri */
424  if (!BN_is_zero(Ri))
425  {
426  if (!BN_sub_word(Ri,1)) goto err;
427  }
428  else /* if N mod word size == 1 */
429  {
430  if (!BN_set_word(Ri,BN_MASK2)) goto err; /* Ri-- (mod word size) */
431  }
432  if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err;
433  /* Ni = (R*Ri-1)/N,
434  * keep only least significant word: */
435  mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
436  mont->n0[1] = 0;
437 #endif
438  }
439 #else /* !MONT_WORD */
440  { /* bignum version */
441  mont->ri=BN_num_bits(&mont->N);
442  BN_zero(R);
443  if (!BN_set_bit(R,mont->ri)) goto err; /* R = 2^ri */
444  /* Ri = R^-1 mod N*/
445  if ((BN_mod_inverse(Ri,R,&mont->N,ctx)) == NULL)
446  goto err;
447  if (!BN_lshift(Ri,Ri,mont->ri)) goto err; /* R*Ri */
448  if (!BN_sub_word(Ri,1)) goto err;
449  /* Ni = (R*Ri-1) / N */
450  if (!BN_div(&(mont->Ni),NULL,Ri,&mont->N,ctx)) goto err;
451  }
452 #endif
453 
454  /* setup RR for conversions */
455  BN_zero(&(mont->RR));
456  if (!BN_set_bit(&(mont->RR),mont->ri*2)) goto err;
457  if (!BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx)) goto err;
458 
459  ret = 1;
460 err:
461  BN_CTX_end(ctx);
462  return ret;
463  }
464 
465 BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
466  {
467  if (to == from) return(to);
468 
469  if (!BN_copy(&(to->RR),&(from->RR))) return NULL;
470  if (!BN_copy(&(to->N),&(from->N))) return NULL;
471  if (!BN_copy(&(to->Ni),&(from->Ni))) return NULL;
472  to->ri=from->ri;
473  to->n0[0]=from->n0[0];
474  to->n0[1]=from->n0[1];
475  return(to);
476  }
477 
478 BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock,
479  const BIGNUM *mod, BN_CTX *ctx)
480  {
481  int got_write_lock = 0;
482  BN_MONT_CTX *ret;
483 
484  CRYPTO_r_lock(lock);
485  if (!*pmont)
486  {
487  CRYPTO_r_unlock(lock);
488  CRYPTO_w_lock(lock);
489  got_write_lock = 1;
490 
491  if (!*pmont)
492  {
493  ret = BN_MONT_CTX_new();
494  if (ret && !BN_MONT_CTX_set(ret, mod, ctx))
495  BN_MONT_CTX_free(ret);
496  else
497  *pmont = ret;
498  }
499  }
500 
501  ret = *pmont;
502 
503  if (got_write_lock)
504  CRYPTO_w_unlock(lock);
505  else
506  CRYPTO_r_unlock(lock);
507 
508  return ret;
509  }
Generated on Thu Jan 10 2013 09:53:34 for OpenSSL by   doxygen 1.8.2