1 /* 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
111 #include <string.h>
112
113 #include <openssl/mem.h>
114 #include <openssl/thread.h>
115
116 #include "internal.h"
117 #include "../internal.h"
118
119
120 #if !defined(OPENSSL_NO_ASM) && \
121 (defined(OPENSSL_X86) || defined(OPENSSL_X86_64))
122 #define OPENSSL_BN_ASM_MONT
123 #endif
124
BN_MONT_CTX_new(void)125 BN_MONT_CTX *BN_MONT_CTX_new(void) {
126 BN_MONT_CTX *ret = OPENSSL_malloc(sizeof(BN_MONT_CTX));
127
128 if (ret == NULL) {
129 return NULL;
130 }
131
132 BN_MONT_CTX_init(ret);
133 ret->flags = BN_FLG_MALLOCED;
134 return ret;
135 }
136
BN_MONT_CTX_init(BN_MONT_CTX * mont)137 void BN_MONT_CTX_init(BN_MONT_CTX *mont) {
138 memset(mont, 0, sizeof(BN_MONT_CTX));
139 BN_init(&mont->RR);
140 BN_init(&mont->N);
141 BN_init(&mont->Ni);
142 }
143
BN_MONT_CTX_free(BN_MONT_CTX * mont)144 void BN_MONT_CTX_free(BN_MONT_CTX *mont) {
145 if (mont == NULL) {
146 return;
147 }
148
149 BN_free(&mont->RR);
150 BN_free(&mont->N);
151 BN_free(&mont->Ni);
152 if (mont->flags & BN_FLG_MALLOCED) {
153 OPENSSL_free(mont);
154 }
155 }
156
BN_MONT_CTX_copy(BN_MONT_CTX * to,BN_MONT_CTX * from)157 BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) {
158 if (to == from) {
159 return to;
160 }
161
162 if (!BN_copy(&to->RR, &from->RR) ||
163 !BN_copy(&to->N, &from->N) ||
164 !BN_copy(&to->Ni, &from->Ni)) {
165 return NULL;
166 }
167 to->ri = from->ri;
168 to->n0[0] = from->n0[0];
169 to->n0[1] = from->n0[1];
170 return to;
171 }
172
BN_MONT_CTX_set(BN_MONT_CTX * mont,const BIGNUM * mod,BN_CTX * ctx)173 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) {
174 int ret = 0;
175 BIGNUM *Ri, *R;
176 BIGNUM tmod;
177 BN_ULONG buf[2];
178
179 BN_CTX_start(ctx);
180 Ri = BN_CTX_get(ctx);
181 if (Ri == NULL) {
182 goto err;
183 }
184 R = &mont->RR; /* grab RR as a temp */
185 if (!BN_copy(&mont->N, mod)) {
186 goto err; /* Set N */
187 }
188 mont->N.neg = 0;
189
190 BN_init(&tmod);
191 tmod.d = buf;
192 tmod.dmax = 2;
193 tmod.neg = 0;
194
195 mont->ri = (BN_num_bits(mod) + (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;
196
197 #if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2 <= 32)
198 /* Only certain BN_BITS2<=32 platforms actually make use of
199 * n0[1], and we could use the #else case (with a shorter R
200 * value) for the others. However, currently only the assembler
201 * files do know which is which. */
202
203 BN_zero(R);
204 if (!BN_set_bit(R, 2 * BN_BITS2)) {
205 goto err;
206 }
207
208 tmod.top = 0;
209 if ((buf[0] = mod->d[0])) {
210 tmod.top = 1;
211 }
212 if ((buf[1] = mod->top > 1 ? mod->d[1] : 0)) {
213 tmod.top = 2;
214 }
215
216 if (BN_mod_inverse(Ri, R, &tmod, ctx) == NULL) {
217 goto err;
218 }
219 if (!BN_lshift(Ri, Ri, 2 * BN_BITS2)) {
220 goto err; /* R*Ri */
221 }
222 if (!BN_is_zero(Ri)) {
223 if (!BN_sub_word(Ri, 1)) {
224 goto err;
225 }
226 } else {
227 /* if N mod word size == 1 */
228 if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL) {
229 goto err;
230 }
231 /* Ri-- (mod double word size) */
232 Ri->neg = 0;
233 Ri->d[0] = BN_MASK2;
234 Ri->d[1] = BN_MASK2;
235 Ri->top = 2;
236 }
237
238 if (!BN_div(Ri, NULL, Ri, &tmod, ctx)) {
239 goto err;
240 }
241 /* Ni = (R*Ri-1)/N,
242 * keep only couple of least significant words: */
243 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
244 mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
245 #else
246 BN_zero(R);
247 if (!BN_set_bit(R, BN_BITS2)) {
248 goto err; /* R */
249 }
250
251 buf[0] = mod->d[0]; /* tmod = N mod word size */
252 buf[1] = 0;
253 tmod.top = buf[0] != 0 ? 1 : 0;
254 /* Ri = R^-1 mod N*/
255 if (BN_mod_inverse(Ri, R, &tmod, ctx) == NULL) {
256 goto err;
257 }
258 if (!BN_lshift(Ri, Ri, BN_BITS2)) {
259 goto err; /* R*Ri */
260 }
261 if (!BN_is_zero(Ri)) {
262 if (!BN_sub_word(Ri, 1)) {
263 goto err;
264 }
265 } else {
266 /* if N mod word size == 1 */
267 if (!BN_set_word(Ri, BN_MASK2)) {
268 goto err; /* Ri-- (mod word size) */
269 }
270 }
271 if (!BN_div(Ri, NULL, Ri, &tmod, ctx)) {
272 goto err;
273 }
274 /* Ni = (R*Ri-1)/N,
275 * keep only least significant word: */
276 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
277 mont->n0[1] = 0;
278 #endif
279
280 /* setup RR for conversions */
281 BN_zero(&(mont->RR));
282 if (!BN_set_bit(&(mont->RR), mont->ri * 2)) {
283 goto err;
284 }
285 if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx)) {
286 goto err;
287 }
288
289 ret = 1;
290
291 err:
292 BN_CTX_end(ctx);
293 return ret;
294 }
295
BN_MONT_CTX_set_locked(BN_MONT_CTX ** pmont,CRYPTO_MUTEX * lock,const BIGNUM * mod,BN_CTX * bn_ctx)296 BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, CRYPTO_MUTEX *lock,
297 const BIGNUM *mod, BN_CTX *bn_ctx) {
298 CRYPTO_MUTEX_lock_read(lock);
299 BN_MONT_CTX *ctx = *pmont;
300 CRYPTO_MUTEX_unlock(lock);
301
302 if (ctx) {
303 return ctx;
304 }
305
306 CRYPTO_MUTEX_lock_write(lock);
307 ctx = *pmont;
308 if (ctx) {
309 goto out;
310 }
311
312 ctx = BN_MONT_CTX_new();
313 if (ctx == NULL) {
314 goto out;
315 }
316 if (!BN_MONT_CTX_set(ctx, mod, bn_ctx)) {
317 BN_MONT_CTX_free(ctx);
318 ctx = NULL;
319 goto out;
320 }
321 *pmont = ctx;
322
323 out:
324 CRYPTO_MUTEX_unlock(lock);
325 return ctx;
326 }
327
BN_to_montgomery(BIGNUM * ret,const BIGNUM * a,const BN_MONT_CTX * mont,BN_CTX * ctx)328 int BN_to_montgomery(BIGNUM *ret, const BIGNUM *a, const BN_MONT_CTX *mont,
329 BN_CTX *ctx) {
330 return BN_mod_mul_montgomery(ret, a, &mont->RR, mont, ctx);
331 }
332
333 #if 0
334 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r,
335 const BN_MONT_CTX *mont) {
336 const BIGNUM *n;
337 BN_ULONG *ap, *np, *rp, n0, v, carry;
338 int nl, max, i;
339
340 n = &mont->N;
341 nl = n->top;
342 if (nl == 0) {
343 ret->top = 0;
344 return 1;
345 }
346
347 max = (2 * nl); /* carry is stored separately */
348 if (bn_wexpand(r, max) == NULL) {
349 return 0;
350 }
351
352 r->neg ^= n->neg;
353 np = n->d;
354 rp = r->d;
355
356 /* clear the top words of T */
357 if (max > r->top) {
358 memset(&rp[r->top], 0, (max - r->top) * sizeof(BN_ULONG));
359 }
360
361 r->top = max;
362 n0 = mont->n0[0];
363
364 for (carry = 0, i = 0; i < nl; i++, rp++) {
365 v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2);
366 v = (v + carry + rp[nl]) & BN_MASK2;
367 carry |= (v != rp[nl]);
368 carry &= (v <= rp[nl]);
369 rp[nl] = v;
370 }
371
372 if (bn_wexpand(ret, nl) == NULL) {
373 return 0;
374 }
375 ret->top = nl;
376 ret->neg = r->neg;
377
378 rp = ret->d;
379 ap = &(r->d[nl]);
380
381 {
382 BN_ULONG *nrp;
383 size_t m;
384
385 v = bn_sub_words(rp, ap, np, nl) - carry;
386 /* if subtraction result is real, then trick unconditional memcpy below to
387 * perform in-place "refresh" instead of actual copy. */
388 m = (0 - (size_t)v);
389 nrp = (BN_ULONG *)(((intptr_t)rp & ~m) | ((intptr_t)ap & m));
390
391 for (i = 0, nl -= 4; i < nl; i += 4) {
392 BN_ULONG t1, t2, t3, t4;
393
394 t1 = nrp[i + 0];
395 t2 = nrp[i + 1];
396 t3 = nrp[i + 2];
397 ap[i + 0] = 0;
398 t4 = nrp[i + 3];
399 ap[i + 1] = 0;
400 rp[i + 0] = t1;
401 ap[i + 2] = 0;
402 rp[i + 1] = t2;
403 ap[i + 3] = 0;
404 rp[i + 2] = t3;
405 rp[i + 3] = t4;
406 }
407
408 for (nl += 4; i < nl; i++) {
409 rp[i] = nrp[i], ap[i] = 0;
410 }
411 }
412
413 bn_correct_top(r);
414 bn_correct_top(ret);
415
416 return 1;
417 }
418 #endif
419
420 #define PTR_SIZE_INT size_t
421
BN_from_montgomery_word(BIGNUM * ret,BIGNUM * r,const BN_MONT_CTX * mont)422 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, const BN_MONT_CTX *mont)
423 {
424 BIGNUM *n;
425 BN_ULONG *ap,*np,*rp,n0,v,carry;
426 int nl,max,i;
427
428 n= (BIGNUM*) &(mont->N);
429 nl=n->top;
430 if (nl == 0) { ret->top=0; return(1); }
431
432 max=(2*nl); /* carry is stored separately */
433 if (bn_wexpand(r,max) == NULL) return(0);
434
435 r->neg^=n->neg;
436 np=n->d;
437 rp=r->d;
438
439 /* clear the top words of T */
440 #if 1
441 for (i=r->top; i<max; i++) /* memset? XXX */
442 rp[i]=0;
443 #else
444 memset(&(rp[r->top]),0,(max-r->top)*sizeof(BN_ULONG));
445 #endif
446
447 r->top=max;
448 n0=mont->n0[0];
449
450 for (carry=0, i=0; i<nl; i++, rp++)
451 {
452 v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);
453 v = (v+carry+rp[nl])&BN_MASK2;
454 carry |= (v != rp[nl]);
455 carry &= (v <= rp[nl]);
456 rp[nl]=v;
457 }
458
459 if (bn_wexpand(ret,nl) == NULL) return(0);
460 ret->top=nl;
461 ret->neg=r->neg;
462
463 rp=ret->d;
464 ap=&(r->d[nl]);
465
466 {
467 BN_ULONG *nrp;
468 size_t m;
469
470 v=bn_sub_words(rp,ap,np,nl)-carry;
471 /* if subtraction result is real, then
472 * trick unconditional memcpy below to perform in-place
473 * "refresh" instead of actual copy. */
474 m=(0-(size_t)v);
475 nrp=(BN_ULONG *)(((PTR_SIZE_INT)rp&~m)|((PTR_SIZE_INT)ap&m));
476
477 for (i=0,nl-=4; i<nl; i+=4)
478 {
479 BN_ULONG t1,t2,t3,t4;
480
481 t1=nrp[i+0];
482 t2=nrp[i+1];
483 t3=nrp[i+2]; ap[i+0]=0;
484 t4=nrp[i+3]; ap[i+1]=0;
485 rp[i+0]=t1; ap[i+2]=0;
486 rp[i+1]=t2; ap[i+3]=0;
487 rp[i+2]=t3;
488 rp[i+3]=t4;
489 }
490 for (nl+=4; i<nl; i++)
491 rp[i]=nrp[i], ap[i]=0;
492 }
493 bn_correct_top(r);
494 bn_correct_top(ret);
495
496 return(1);
497 }
498
BN_from_montgomery(BIGNUM * ret,const BIGNUM * a,const BN_MONT_CTX * mont,BN_CTX * ctx)499 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, const BN_MONT_CTX *mont,
500 BN_CTX *ctx) {
501 int retn = 0;
502 BIGNUM *t;
503
504 BN_CTX_start(ctx);
505 t = BN_CTX_get(ctx);
506 if (t == NULL) {
507 return 0;
508 }
509
510 if (BN_copy(t, a)) {
511 retn = BN_from_montgomery_word(ret, t, mont);
512 }
513 BN_CTX_end(ctx);
514
515 return retn;
516 }
517
BN_mod_mul_montgomery(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,const BN_MONT_CTX * mont,BN_CTX * ctx)518 int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
519 const BN_MONT_CTX *mont, BN_CTX *ctx) {
520 BIGNUM *tmp;
521 int ret = 0;
522
523 #if defined(OPENSSL_BN_ASM_MONT)
524 int num = mont->N.top;
525
526 if (num > 1 && a->top == num && b->top == num) {
527 if (bn_wexpand(r, num) == NULL) {
528 return 0;
529 }
530 if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {
531 r->neg = a->neg ^ b->neg;
532 r->top = num;
533 bn_correct_top(r);
534 return 1;
535 }
536 }
537 #endif
538
539 BN_CTX_start(ctx);
540 tmp = BN_CTX_get(ctx);
541 if (tmp == NULL) {
542 goto err;
543 }
544
545 if (a == b) {
546 if (!BN_sqr(tmp, a, ctx)) {
547 goto err;
548 }
549 } else {
550 if (!BN_mul(tmp, a, b, ctx)) {
551 goto err;
552 }
553 }
554
555 /* reduce from aRR to aR */
556 if (!BN_from_montgomery_word(r, tmp, mont)) {
557 goto err;
558 }
559
560 ret = 1;
561
562 err:
563 BN_CTX_end(ctx);
564 return ret;
565 }
566