[3181] | 1 | //FIXME Not checked on threadsafety yet; after checking please remove this line
|
---|
[8] | 2 | /* crypto/bn/bn_mul.c */
|
---|
| 3 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
|
---|
| 4 | * All rights reserved.
|
---|
| 5 | *
|
---|
| 6 | * This package is an SSL implementation written
|
---|
| 7 | * by Eric Young (eay@cryptsoft.com).
|
---|
| 8 | * The implementation was written so as to conform with Netscapes SSL.
|
---|
| 9 | *
|
---|
| 10 | * This library is free for commercial and non-commercial use as long as
|
---|
| 11 | * the following conditions are aheared to. The following conditions
|
---|
| 12 | * apply to all code found in this distribution, be it the RC4, RSA,
|
---|
| 13 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation
|
---|
| 14 | * included with this distribution is covered by the same copyright terms
|
---|
| 15 | * except that the holder is Tim Hudson (tjh@cryptsoft.com).
|
---|
| 16 | *
|
---|
| 17 | * Copyright remains Eric Young's, and as such any Copyright notices in
|
---|
| 18 | * the code are not to be removed.
|
---|
| 19 | * If this package is used in a product, Eric Young should be given attribution
|
---|
| 20 | * as the author of the parts of the library used.
|
---|
| 21 | * This can be in the form of a textual message at program startup or
|
---|
| 22 | * in documentation (online or textual) provided with the package.
|
---|
| 23 | *
|
---|
| 24 | * Redistribution and use in source and binary forms, with or without
|
---|
| 25 | * modification, are permitted provided that the following conditions
|
---|
| 26 | * are met:
|
---|
| 27 | * 1. Redistributions of source code must retain the copyright
|
---|
| 28 | * notice, this list of conditions and the following disclaimer.
|
---|
| 29 | * 2. Redistributions in binary form must reproduce the above copyright
|
---|
| 30 | * notice, this list of conditions and the following disclaimer in the
|
---|
| 31 | * documentation and/or other materials provided with the distribution.
|
---|
| 32 | * 3. All advertising materials mentioning features or use of this software
|
---|
| 33 | * must display the following acknowledgement:
|
---|
| 34 | * "This product includes cryptographic software written by
|
---|
| 35 | * Eric Young (eay@cryptsoft.com)"
|
---|
| 36 | * The word 'cryptographic' can be left out if the rouines from the library
|
---|
| 37 | * being used are not cryptographic related :-).
|
---|
| 38 | * 4. If you include any Windows specific code (or a derivative thereof) from
|
---|
| 39 | * the apps directory (application code) you must include an acknowledgement:
|
---|
| 40 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
|
---|
| 41 | *
|
---|
| 42 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
|
---|
| 43 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
---|
| 44 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
---|
| 45 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
|
---|
| 46 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
---|
| 47 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
|
---|
| 48 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
---|
| 49 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
|
---|
| 50 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
|
---|
| 51 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
---|
| 52 | * SUCH DAMAGE.
|
---|
| 53 | *
|
---|
| 54 | * The licence and distribution terms for any publically available version or
|
---|
| 55 | * derivative of this code cannot be changed. i.e. this code cannot simply be
|
---|
| 56 | * copied and put under another distribution licence
|
---|
| 57 | * [including the GNU Public Licence.]
|
---|
| 58 | */
|
---|
| 59 |
|
---|
| 60 | #include <stdio.h>
|
---|
| 61 | #include <string.h>
|
---|
| 62 | #include "bn_lcl.h"
|
---|
| 63 | #include "openssl_mods.h"
|
---|
| 64 |
|
---|
| 65 | #ifdef BN_RECURSION
|
---|
| 66 | /* Karatsuba recursive multiplication algorithm
|
---|
| 67 | * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
|
---|
| 68 |
|
---|
| 69 | /* r is 2*n2 words in size,
|
---|
| 70 | * a and b are both n2 words in size.
|
---|
| 71 | * n2 must be a power of 2.
|
---|
| 72 | * We multiply and return the result.
|
---|
| 73 | * t must be 2*n2 words in size
|
---|
| 74 | * We calculate
|
---|
| 75 | * a[0]*b[0]
|
---|
| 76 | * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
|
---|
| 77 | * a[1]*b[1]
|
---|
| 78 | */
|
---|
| 79 | void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
|
---|
| 80 | BN_ULONG *t)
|
---|
| 81 | {
|
---|
| 82 | int n=n2/2,c1,c2;
|
---|
| 83 | unsigned int neg,zero;
|
---|
| 84 | BN_ULONG ln,lo,*p;
|
---|
| 85 |
|
---|
| 86 | # ifdef BN_COUNT
|
---|
| 87 | printf(" bn_mul_recursive %d * %d\n",n2,n2);
|
---|
| 88 | # endif
|
---|
| 89 | # ifdef BN_MUL_COMBA
|
---|
| 90 | # if 0
|
---|
| 91 | if (n2 == 4)
|
---|
| 92 | {
|
---|
| 93 | bn_mul_comba4(r,a,b);
|
---|
| 94 | return;
|
---|
| 95 | }
|
---|
| 96 | # endif
|
---|
| 97 | if (n2 == 8)
|
---|
| 98 | {
|
---|
| 99 | bn_mul_comba8(r,a,b);
|
---|
| 100 | return;
|
---|
| 101 | }
|
---|
| 102 | # endif /* BN_MUL_COMBA */
|
---|
| 103 | if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
|
---|
| 104 | {
|
---|
| 105 | /* This should not happen */
|
---|
| 106 | bn_mul_normal(r,a,n2,b,n2);
|
---|
| 107 | return;
|
---|
| 108 | }
|
---|
| 109 | /* r=(a[0]-a[1])*(b[1]-b[0]) */
|
---|
| 110 | c1=bn_cmp_words(a,&(a[n]),n);
|
---|
| 111 | c2=bn_cmp_words(&(b[n]),b,n);
|
---|
| 112 | zero=neg=0;
|
---|
| 113 | switch (c1*3+c2)
|
---|
| 114 | {
|
---|
| 115 | case -4:
|
---|
| 116 | bn_sub_words(t, &(a[n]),a, n); /* - */
|
---|
| 117 | bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
|
---|
| 118 | break;
|
---|
| 119 | case -3:
|
---|
| 120 | zero=1;
|
---|
| 121 | break;
|
---|
| 122 | case -2:
|
---|
| 123 | bn_sub_words(t, &(a[n]),a, n); /* - */
|
---|
| 124 | bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
|
---|
| 125 | neg=1;
|
---|
| 126 | break;
|
---|
| 127 | case -1:
|
---|
| 128 | case 0:
|
---|
| 129 | case 1:
|
---|
| 130 | zero=1;
|
---|
| 131 | break;
|
---|
| 132 | case 2:
|
---|
| 133 | bn_sub_words(t, a, &(a[n]),n); /* + */
|
---|
| 134 | bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
|
---|
| 135 | neg=1;
|
---|
| 136 | break;
|
---|
| 137 | case 3:
|
---|
| 138 | zero=1;
|
---|
| 139 | break;
|
---|
| 140 | case 4:
|
---|
| 141 | bn_sub_words(t, a, &(a[n]),n);
|
---|
| 142 | bn_sub_words(&(t[n]),&(b[n]),b, n);
|
---|
| 143 | break;
|
---|
| 144 | }
|
---|
| 145 |
|
---|
| 146 | # ifdef BN_MUL_COMBA
|
---|
| 147 | if (n == 4)
|
---|
| 148 | {
|
---|
| 149 | if (!zero)
|
---|
| 150 | bn_mul_comba4(&(t[n2]),t,&(t[n]));
|
---|
| 151 | else
|
---|
| 152 | memset(&(t[n2]),0,8*sizeof(BN_ULONG));
|
---|
| 153 |
|
---|
| 154 | bn_mul_comba4(r,a,b);
|
---|
| 155 | bn_mul_comba4(&(r[n2]),&(a[n]),&(b[n]));
|
---|
| 156 | }
|
---|
| 157 | else if (n == 8)
|
---|
| 158 | {
|
---|
| 159 | if (!zero)
|
---|
| 160 | bn_mul_comba8(&(t[n2]),t,&(t[n]));
|
---|
| 161 | else
|
---|
| 162 | memset(&(t[n2]),0,16*sizeof(BN_ULONG));
|
---|
| 163 |
|
---|
| 164 | bn_mul_comba8(r,a,b);
|
---|
| 165 | bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
|
---|
| 166 | }
|
---|
| 167 | else
|
---|
| 168 | # endif /* BN_MUL_COMBA */
|
---|
| 169 | {
|
---|
| 170 | p= &(t[n2*2]);
|
---|
| 171 | if (!zero)
|
---|
| 172 | bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
|
---|
| 173 | else
|
---|
| 174 | memset(&(t[n2]),0,n2*sizeof(BN_ULONG));
|
---|
| 175 | bn_mul_recursive(r,a,b,n,p);
|
---|
| 176 | bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,p);
|
---|
| 177 | }
|
---|
| 178 |
|
---|
| 179 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
|
---|
| 180 | * r[10] holds (a[0]*b[0])
|
---|
| 181 | * r[32] holds (b[1]*b[1])
|
---|
| 182 | */
|
---|
| 183 |
|
---|
| 184 | c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
|
---|
| 185 |
|
---|
| 186 | if (neg) /* if t[32] is negative */
|
---|
| 187 | {
|
---|
| 188 | c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
|
---|
| 189 | }
|
---|
| 190 | else
|
---|
| 191 | {
|
---|
| 192 | /* Might have a carry */
|
---|
| 193 | c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
|
---|
| 194 | }
|
---|
| 195 |
|
---|
| 196 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
|
---|
| 197 | * r[10] holds (a[0]*b[0])
|
---|
| 198 | * r[32] holds (b[1]*b[1])
|
---|
| 199 | * c1 holds the carry bits
|
---|
| 200 | */
|
---|
| 201 | c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
|
---|
| 202 | if (c1)
|
---|
| 203 | {
|
---|
| 204 | p= &(r[n+n2]);
|
---|
| 205 | lo= *p;
|
---|
| 206 | ln=(lo+c1)&BN_MASK2;
|
---|
| 207 | *p=ln;
|
---|
| 208 |
|
---|
| 209 | /* The overflow will stop before we over write
|
---|
| 210 | * words we should not overwrite */
|
---|
| 211 | if (ln < (BN_ULONG)c1)
|
---|
| 212 | {
|
---|
| 213 | do {
|
---|
| 214 | p++;
|
---|
| 215 | lo= *p;
|
---|
| 216 | ln=(lo+1)&BN_MASK2;
|
---|
| 217 | *p=ln;
|
---|
| 218 | } while (ln == 0);
|
---|
| 219 | }
|
---|
| 220 | }
|
---|
| 221 | }
|
---|
| 222 |
|
---|
| 223 | /* n+tn is the word length
|
---|
| 224 | * t needs to be n*4 is size, as does r */
|
---|
| 225 | void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
|
---|
| 226 | int n, BN_ULONG *t)
|
---|
| 227 | {
|
---|
[943] | 228 | int c1,c2,i,j,n2=n*2;
|
---|
| 229 | unsigned int neg,zero;
|
---|
[8] | 230 | BN_ULONG ln,lo,*p;
|
---|
| 231 |
|
---|
| 232 | # ifdef BN_COUNT
|
---|
| 233 | printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
|
---|
| 234 | # endif
|
---|
| 235 | if (n < 8)
|
---|
| 236 | {
|
---|
| 237 | i=tn+n;
|
---|
| 238 | bn_mul_normal(r,a,i,b,i);
|
---|
| 239 | return;
|
---|
| 240 | }
|
---|
| 241 |
|
---|
| 242 | /* r=(a[0]-a[1])*(b[1]-b[0]) */
|
---|
| 243 | c1=bn_cmp_words(a,&(a[n]),n);
|
---|
| 244 | c2=bn_cmp_words(&(b[n]),b,n);
|
---|
| 245 | zero=neg=0;
|
---|
| 246 | switch (c1*3+c2)
|
---|
| 247 | {
|
---|
| 248 | case -4:
|
---|
| 249 | bn_sub_words(t, &(a[n]),a, n); /* - */
|
---|
| 250 | bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
|
---|
| 251 | break;
|
---|
| 252 | case -3:
|
---|
| 253 | zero=1;
|
---|
| 254 | /* break; */
|
---|
| 255 | case -2:
|
---|
| 256 | bn_sub_words(t, &(a[n]),a, n); /* - */
|
---|
| 257 | bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
|
---|
| 258 | neg=1;
|
---|
| 259 | break;
|
---|
| 260 | case -1:
|
---|
| 261 | case 0:
|
---|
| 262 | case 1:
|
---|
| 263 | zero=1;
|
---|
| 264 | /* break; */
|
---|
| 265 | case 2:
|
---|
| 266 | bn_sub_words(t, a, &(a[n]),n); /* + */
|
---|
| 267 | bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
|
---|
| 268 | neg=1;
|
---|
| 269 | break;
|
---|
| 270 | case 3:
|
---|
| 271 | zero=1;
|
---|
| 272 | /* break; */
|
---|
| 273 | case 4:
|
---|
| 274 | bn_sub_words(t, a, &(a[n]),n);
|
---|
| 275 | bn_sub_words(&(t[n]),&(b[n]),b, n);
|
---|
| 276 | break;
|
---|
| 277 | }
|
---|
| 278 | /* The zero case isn't yet implemented here. The speedup
|
---|
| 279 | would probably be negligible. */
|
---|
| 280 | # if 0
|
---|
| 281 | if (n == 4)
|
---|
| 282 | {
|
---|
| 283 | bn_mul_comba4(&(t[n2]),t,&(t[n]));
|
---|
| 284 | bn_mul_comba4(r,a,b);
|
---|
| 285 | bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
|
---|
| 286 | memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
|
---|
| 287 | }
|
---|
| 288 | else
|
---|
| 289 | # endif
|
---|
| 290 | if (n == 8)
|
---|
| 291 | {
|
---|
| 292 | bn_mul_comba8(&(t[n2]),t,&(t[n]));
|
---|
| 293 | bn_mul_comba8(r,a,b);
|
---|
| 294 | bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
|
---|
| 295 | memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
|
---|
| 296 | }
|
---|
| 297 | else
|
---|
| 298 | {
|
---|
| 299 | p= &(t[n2*2]);
|
---|
| 300 | bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
|
---|
| 301 | bn_mul_recursive(r,a,b,n,p);
|
---|
| 302 | i=n/2;
|
---|
| 303 | /* If there is only a bottom half to the number,
|
---|
| 304 | * just do it */
|
---|
| 305 | j=tn-i;
|
---|
| 306 | if (j == 0)
|
---|
| 307 | {
|
---|
| 308 | bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p);
|
---|
| 309 | memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2));
|
---|
| 310 | }
|
---|
| 311 | else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
|
---|
| 312 | {
|
---|
| 313 | bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]),
|
---|
| 314 | j,i,p);
|
---|
| 315 | memset(&(r[n2+tn*2]),0,
|
---|
| 316 | sizeof(BN_ULONG)*(n2-tn*2));
|
---|
| 317 | }
|
---|
| 318 | else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
|
---|
| 319 | {
|
---|
| 320 | memset(&(r[n2]),0,sizeof(BN_ULONG)*n2);
|
---|
| 321 | if (tn < BN_MUL_RECURSIVE_SIZE_NORMAL)
|
---|
| 322 | {
|
---|
| 323 | bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
|
---|
| 324 | }
|
---|
| 325 | else
|
---|
| 326 | {
|
---|
| 327 | for (;;)
|
---|
| 328 | {
|
---|
| 329 | i/=2;
|
---|
| 330 | if (i < tn)
|
---|
| 331 | {
|
---|
| 332 | bn_mul_part_recursive(&(r[n2]),
|
---|
| 333 | &(a[n]),&(b[n]),
|
---|
| 334 | tn-i,i,p);
|
---|
| 335 | break;
|
---|
| 336 | }
|
---|
| 337 | else if (i == tn)
|
---|
| 338 | {
|
---|
| 339 | bn_mul_recursive(&(r[n2]),
|
---|
| 340 | &(a[n]),&(b[n]),
|
---|
| 341 | i,p);
|
---|
| 342 | break;
|
---|
| 343 | }
|
---|
| 344 | }
|
---|
| 345 | }
|
---|
| 346 | }
|
---|
| 347 | }
|
---|
| 348 |
|
---|
| 349 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
|
---|
| 350 | * r[10] holds (a[0]*b[0])
|
---|
| 351 | * r[32] holds (b[1]*b[1])
|
---|
| 352 | */
|
---|
| 353 |
|
---|
| 354 | c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
|
---|
| 355 |
|
---|
| 356 | if (neg) /* if t[32] is negative */
|
---|
| 357 | {
|
---|
| 358 | c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
|
---|
| 359 | }
|
---|
| 360 | else
|
---|
| 361 | {
|
---|
| 362 | /* Might have a carry */
|
---|
| 363 | c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
|
---|
| 364 | }
|
---|
| 365 |
|
---|
| 366 | /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
|
---|
| 367 | * r[10] holds (a[0]*b[0])
|
---|
| 368 | * r[32] holds (b[1]*b[1])
|
---|
| 369 | * c1 holds the carry bits
|
---|
| 370 | */
|
---|
| 371 | c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
|
---|
| 372 | if (c1)
|
---|
| 373 | {
|
---|
| 374 | p= &(r[n+n2]);
|
---|
| 375 | lo= *p;
|
---|
| 376 | ln=(lo+c1)&BN_MASK2;
|
---|
| 377 | *p=ln;
|
---|
| 378 |
|
---|
| 379 | /* The overflow will stop before we over write
|
---|
| 380 | * words we should not overwrite */
|
---|
[1137] | 381 | if (ln < (BN_ULONG)c1)
|
---|
[8] | 382 | {
|
---|
| 383 | do {
|
---|
| 384 | p++;
|
---|
| 385 | lo= *p;
|
---|
| 386 | ln=(lo+1)&BN_MASK2;
|
---|
| 387 | *p=ln;
|
---|
| 388 | } while (ln == 0);
|
---|
| 389 | }
|
---|
| 390 | }
|
---|
| 391 | }
|
---|
| 392 |
|
---|
| 393 | /* a and b must be the same size, which is n2.
|
---|
| 394 | * r needs to be n2 words and t needs to be n2*2
|
---|
| 395 | */
|
---|
| 396 | void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
|
---|
| 397 | BN_ULONG *t)
|
---|
| 398 | {
|
---|
| 399 | int n=n2/2;
|
---|
| 400 |
|
---|
| 401 | # ifdef BN_COUNT
|
---|
| 402 | printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
|
---|
| 403 | # endif
|
---|
| 404 |
|
---|
| 405 | bn_mul_recursive(r,a,b,n,&(t[0]));
|
---|
| 406 | if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
|
---|
| 407 | {
|
---|
| 408 | bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2]));
|
---|
| 409 | bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
|
---|
| 410 | bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2]));
|
---|
| 411 | bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
|
---|
| 412 | }
|
---|
| 413 | else
|
---|
| 414 | {
|
---|
| 415 | bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n);
|
---|
| 416 | bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n);
|
---|
| 417 | bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
|
---|
| 418 | bn_add_words(&(r[n]),&(r[n]),&(t[n]),n);
|
---|
| 419 | }
|
---|
| 420 | }
|
---|
| 421 |
|
---|
| 422 | /* a and b must be the same size, which is n2.
|
---|
| 423 | * r needs to be n2 words and t needs to be n2*2
|
---|
| 424 | * l is the low words of the output.
|
---|
| 425 | * t needs to be n2*3
|
---|
| 426 | */
|
---|
| 427 | void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
|
---|
| 428 | BN_ULONG *t)
|
---|
| 429 | {
|
---|
| 430 | int i,n;
|
---|
| 431 | int c1,c2;
|
---|
| 432 | int neg,oneg,zero;
|
---|
| 433 | BN_ULONG ll,lc,*lp,*mp;
|
---|
| 434 |
|
---|
| 435 | # ifdef BN_COUNT
|
---|
| 436 | printf(" bn_mul_high %d * %d\n",n2,n2);
|
---|
| 437 | # endif
|
---|
| 438 | n=n2/2;
|
---|
| 439 |
|
---|
| 440 | /* Calculate (al-ah)*(bh-bl) */
|
---|
| 441 | neg=zero=0;
|
---|
| 442 | c1=bn_cmp_words(&(a[0]),&(a[n]),n);
|
---|
| 443 | c2=bn_cmp_words(&(b[n]),&(b[0]),n);
|
---|
| 444 | switch (c1*3+c2)
|
---|
| 445 | {
|
---|
| 446 | case -4:
|
---|
| 447 | bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
|
---|
| 448 | bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
|
---|
| 449 | break;
|
---|
| 450 | case -3:
|
---|
| 451 | zero=1;
|
---|
| 452 | break;
|
---|
| 453 | case -2:
|
---|
| 454 | bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
|
---|
| 455 | bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
|
---|
| 456 | neg=1;
|
---|
| 457 | break;
|
---|
| 458 | case -1:
|
---|
| 459 | case 0:
|
---|
| 460 | case 1:
|
---|
| 461 | zero=1;
|
---|
| 462 | break;
|
---|
| 463 | case 2:
|
---|
| 464 | bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
|
---|
| 465 | bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
|
---|
| 466 | neg=1;
|
---|
| 467 | break;
|
---|
| 468 | case 3:
|
---|
| 469 | zero=1;
|
---|
| 470 | break;
|
---|
| 471 | case 4:
|
---|
| 472 | bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
|
---|
| 473 | bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
|
---|
| 474 | break;
|
---|
| 475 | }
|
---|
| 476 |
|
---|
| 477 | oneg=neg;
|
---|
| 478 | /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
|
---|
| 479 | /* r[10] = (a[1]*b[1]) */
|
---|
| 480 | # ifdef BN_MUL_COMBA
|
---|
| 481 | if (n == 8)
|
---|
| 482 | {
|
---|
| 483 | bn_mul_comba8(&(t[0]),&(r[0]),&(r[n]));
|
---|
| 484 | bn_mul_comba8(r,&(a[n]),&(b[n]));
|
---|
| 485 | }
|
---|
| 486 | else
|
---|
| 487 | # endif
|
---|
| 488 | {
|
---|
| 489 | bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
|
---|
| 490 | bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
|
---|
| 491 | }
|
---|
| 492 |
|
---|
| 493 | /* s0 == low(al*bl)
|
---|
| 494 | * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
|
---|
| 495 | * We know s0 and s1 so the only unknown is high(al*bl)
|
---|
| 496 | * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
|
---|
| 497 | * high(al*bl) == s1 - (r[0]+l[0]+t[0])
|
---|
| 498 | */
|
---|
| 499 | if (l != NULL)
|
---|
| 500 | {
|
---|
| 501 | lp= &(t[n2+n]);
|
---|
| 502 | c1=(int)(bn_add_words(lp,&(r[0]),&(l[0]),n));
|
---|
| 503 | }
|
---|
| 504 | else
|
---|
| 505 | {
|
---|
| 506 | c1=0;
|
---|
| 507 | lp= &(r[0]);
|
---|
| 508 | }
|
---|
| 509 |
|
---|
| 510 | if (neg)
|
---|
| 511 | neg=(int)(bn_sub_words(&(t[n2]),lp,&(t[0]),n));
|
---|
| 512 | else
|
---|
| 513 | {
|
---|
| 514 | bn_add_words(&(t[n2]),lp,&(t[0]),n);
|
---|
| 515 | neg=0;
|
---|
| 516 | }
|
---|
| 517 |
|
---|
| 518 | if (l != NULL)
|
---|
| 519 | {
|
---|
| 520 | bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n);
|
---|
| 521 | }
|
---|
| 522 | else
|
---|
| 523 | {
|
---|
| 524 | lp= &(t[n2+n]);
|
---|
| 525 | mp= &(t[n2]);
|
---|
| 526 | for (i=0; i<n; i++)
|
---|
| 527 | lp[i]=((~mp[i])+1)&BN_MASK2;
|
---|
| 528 | }
|
---|
| 529 |
|
---|
| 530 | /* s[0] = low(al*bl)
|
---|
| 531 | * t[3] = high(al*bl)
|
---|
| 532 | * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
|
---|
| 533 | * r[10] = (a[1]*b[1])
|
---|
| 534 | */
|
---|
| 535 | /* R[10] = al*bl
|
---|
| 536 | * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
|
---|
| 537 | * R[32] = ah*bh
|
---|
| 538 | */
|
---|
| 539 | /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
|
---|
| 540 | * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
|
---|
| 541 | * R[3]=r[1]+(carry/borrow)
|
---|
| 542 | */
|
---|
| 543 | if (l != NULL)
|
---|
| 544 | {
|
---|
| 545 | lp= &(t[n2]);
|
---|
| 546 | c1= (int)(bn_add_words(lp,&(t[n2+n]),&(l[0]),n));
|
---|
| 547 | }
|
---|
| 548 | else
|
---|
| 549 | {
|
---|
| 550 | lp= &(t[n2+n]);
|
---|
| 551 | c1=0;
|
---|
| 552 | }
|
---|
| 553 | c1+=(int)(bn_add_words(&(t[n2]),lp, &(r[0]),n));
|
---|
| 554 | if (oneg)
|
---|
| 555 | c1-=(int)(bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n));
|
---|
| 556 | else
|
---|
| 557 | c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n));
|
---|
| 558 |
|
---|
| 559 | c2 =(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n));
|
---|
| 560 | c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(r[n]),n));
|
---|
| 561 | if (oneg)
|
---|
| 562 | c2-=(int)(bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n));
|
---|
| 563 | else
|
---|
| 564 | c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n]),n));
|
---|
| 565 |
|
---|
| 566 | if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
|
---|
| 567 | {
|
---|
| 568 | i=0;
|
---|
| 569 | if (c1 > 0)
|
---|
| 570 | {
|
---|
| 571 | lc=c1;
|
---|
| 572 | do {
|
---|
| 573 | ll=(r[i]+lc)&BN_MASK2;
|
---|
| 574 | r[i++]=ll;
|
---|
| 575 | lc=(lc > ll);
|
---|
| 576 | } while (lc);
|
---|
| 577 | }
|
---|
| 578 | else
|
---|
| 579 | {
|
---|
| 580 | lc= -c1;
|
---|
| 581 | do {
|
---|
| 582 | ll=r[i];
|
---|
| 583 | r[i++]=(ll-lc)&BN_MASK2;
|
---|
| 584 | lc=(lc > ll);
|
---|
| 585 | } while (lc);
|
---|
| 586 | }
|
---|
| 587 | }
|
---|
| 588 | if (c2 != 0) /* Add starting at r[1] */
|
---|
| 589 | {
|
---|
| 590 | i=n;
|
---|
| 591 | if (c2 > 0)
|
---|
| 592 | {
|
---|
| 593 | lc=c2;
|
---|
| 594 | do {
|
---|
| 595 | ll=(r[i]+lc)&BN_MASK2;
|
---|
| 596 | r[i++]=ll;
|
---|
| 597 | lc=(lc > ll);
|
---|
| 598 | } while (lc);
|
---|
| 599 | }
|
---|
| 600 | else
|
---|
| 601 | {
|
---|
| 602 | lc= -c2;
|
---|
| 603 | do {
|
---|
| 604 | ll=r[i];
|
---|
| 605 | r[i++]=(ll-lc)&BN_MASK2;
|
---|
| 606 | lc=(lc > ll);
|
---|
| 607 | } while (lc);
|
---|
| 608 | }
|
---|
| 609 | }
|
---|
| 610 | }
|
---|
| 611 | #endif /* BN_RECURSION */
|
---|
| 612 |
|
---|
| 613 | int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
|
---|
| 614 | {
|
---|
| 615 | int top,al,bl;
|
---|
| 616 | BIGNUM *rr;
|
---|
| 617 | int ret = 0;
|
---|
| 618 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
|
---|
| 619 | int i;
|
---|
| 620 | #endif
|
---|
| 621 | #ifdef BN_RECURSION
|
---|
| 622 | BIGNUM *t;
|
---|
| 623 | int j,k;
|
---|
| 624 | #endif
|
---|
| 625 |
|
---|
| 626 | #ifdef BN_COUNT
|
---|
| 627 | printf("BN_mul %d * %d\n",a->top,b->top);
|
---|
| 628 | #endif
|
---|
| 629 |
|
---|
| 630 | bn_check_top(a);
|
---|
| 631 | bn_check_top(b);
|
---|
| 632 | bn_check_top(r);
|
---|
| 633 |
|
---|
| 634 | al=a->top;
|
---|
| 635 | bl=b->top;
|
---|
| 636 |
|
---|
| 637 | if ((al == 0) || (bl == 0))
|
---|
| 638 | {
|
---|
| 639 | BN_zero(r);
|
---|
| 640 | return(1);
|
---|
| 641 | }
|
---|
| 642 | top=al+bl;
|
---|
| 643 |
|
---|
| 644 | BN_CTX_start(ctx);
|
---|
| 645 | if ((r == a) || (r == b))
|
---|
| 646 | {
|
---|
| 647 | if ((rr = BN_CTX_get(ctx)) == NULL) goto err;
|
---|
| 648 | }
|
---|
| 649 | else
|
---|
| 650 | rr = r;
|
---|
| 651 | rr->neg=a->neg^b->neg;
|
---|
| 652 |
|
---|
| 653 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
|
---|
| 654 | i = al-bl;
|
---|
| 655 | #endif
|
---|
| 656 | #ifdef BN_MUL_COMBA
|
---|
| 657 | if (i == 0)
|
---|
| 658 | {
|
---|
| 659 | # if 0
|
---|
| 660 | if (al == 4)
|
---|
| 661 | {
|
---|
| 662 | if (bn_wexpand(rr,8) == NULL) goto err;
|
---|
| 663 | rr->top=8;
|
---|
| 664 | bn_mul_comba4(rr->d,a->d,b->d);
|
---|
| 665 | goto end;
|
---|
| 666 | }
|
---|
| 667 | # endif
|
---|
| 668 | if (al == 8)
|
---|
| 669 | {
|
---|
| 670 | if (bn_wexpand(rr,16) == NULL) goto err;
|
---|
| 671 | rr->top=16;
|
---|
| 672 | bn_mul_comba8(rr->d,a->d,b->d);
|
---|
| 673 | goto end;
|
---|
| 674 | }
|
---|
| 675 | }
|
---|
| 676 | #endif /* BN_MUL_COMBA */
|
---|
| 677 | #ifdef BN_RECURSION
|
---|
| 678 | if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL))
|
---|
| 679 | {
|
---|
| 680 | if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA))
|
---|
| 681 | {
|
---|
[943] | 682 | if (bn_wexpand(b,al) == NULL) goto err;
|
---|
[8] | 683 | b->d[bl]=0;
|
---|
| 684 | bl++;
|
---|
| 685 | i--;
|
---|
| 686 | }
|
---|
| 687 | else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA))
|
---|
| 688 | {
|
---|
[943] | 689 | if (bn_wexpand(a,bl) == NULL) goto err;
|
---|
[8] | 690 | a->d[al]=0;
|
---|
| 691 | al++;
|
---|
| 692 | i++;
|
---|
| 693 | }
|
---|
| 694 | if (i == 0)
|
---|
| 695 | {
|
---|
| 696 | /* symmetric and > 4 */
|
---|
| 697 | /* 16 or larger */
|
---|
| 698 | j=BN_num_bits_word((BN_ULONG)al);
|
---|
| 699 | j=1<<(j-1);
|
---|
| 700 | k=j+j;
|
---|
| 701 | t = BN_CTX_get(ctx);
|
---|
| 702 | if (al == j) /* exact multiple */
|
---|
| 703 | {
|
---|
[943] | 704 | if (bn_wexpand(t,k*2) == NULL) goto err;
|
---|
| 705 | if (bn_wexpand(rr,k*2) == NULL) goto err;
|
---|
[8] | 706 | bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
|
---|
| 707 | }
|
---|
| 708 | else
|
---|
| 709 | {
|
---|
[943] | 710 | if (bn_wexpand(a,k) == NULL) goto err;
|
---|
| 711 | if (bn_wexpand(b,k) == NULL) goto err;
|
---|
| 712 | if (bn_wexpand(t,k*4) == NULL) goto err;
|
---|
| 713 | if (bn_wexpand(rr,k*4) == NULL) goto err;
|
---|
[8] | 714 | for (i=a->top; i<k; i++)
|
---|
| 715 | a->d[i]=0;
|
---|
| 716 | for (i=b->top; i<k; i++)
|
---|
| 717 | b->d[i]=0;
|
---|
| 718 | bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
|
---|
| 719 | }
|
---|
| 720 | rr->top=top;
|
---|
| 721 | goto end;
|
---|
| 722 | }
|
---|
| 723 | }
|
---|
| 724 | #endif /* BN_RECURSION */
|
---|
| 725 | if (bn_wexpand(rr,top) == NULL) goto err;
|
---|
| 726 | rr->top=top;
|
---|
| 727 | bn_mul_normal(rr->d,a->d,al,b->d,bl);
|
---|
| 728 |
|
---|
| 729 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
|
---|
| 730 | end:
|
---|
| 731 | #endif
|
---|
| 732 | bn_fix_top(rr);
|
---|
| 733 | if (r != rr) BN_copy(r,rr);
|
---|
| 734 | ret=1;
|
---|
| 735 | err:
|
---|
| 736 | BN_CTX_end(ctx);
|
---|
| 737 | return(ret);
|
---|
| 738 | }
|
---|
| 739 |
|
---|
| 740 | void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
|
---|
| 741 | {
|
---|
| 742 | BN_ULONG *rr;
|
---|
| 743 |
|
---|
| 744 | #ifdef BN_COUNT
|
---|
| 745 | printf(" bn_mul_normal %d * %d\n",na,nb);
|
---|
| 746 | #endif
|
---|
| 747 |
|
---|
| 748 | if (na < nb)
|
---|
| 749 | {
|
---|
| 750 | int itmp;
|
---|
| 751 | BN_ULONG *ltmp;
|
---|
| 752 |
|
---|
| 753 | itmp=na; na=nb; nb=itmp;
|
---|
| 754 | ltmp=a; a=b; b=ltmp;
|
---|
| 755 |
|
---|
| 756 | }
|
---|
| 757 | rr= &(r[na]);
|
---|
| 758 | rr[0]=bn_mul_words(r,a,na,b[0]);
|
---|
| 759 |
|
---|
| 760 | for (;;)
|
---|
| 761 | {
|
---|
| 762 | if (--nb <= 0) return;
|
---|
| 763 | rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]);
|
---|
| 764 | if (--nb <= 0) return;
|
---|
| 765 | rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]);
|
---|
| 766 | if (--nb <= 0) return;
|
---|
| 767 | rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]);
|
---|
| 768 | if (--nb <= 0) return;
|
---|
| 769 | rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]);
|
---|
| 770 | rr+=4;
|
---|
| 771 | r+=4;
|
---|
| 772 | b+=4;
|
---|
| 773 | }
|
---|
| 774 | }
|
---|
| 775 |
|
---|
| 776 | void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
|
---|
| 777 | {
|
---|
| 778 | #ifdef BN_COUNT
|
---|
| 779 | printf(" bn_mul_low_normal %d * %d\n",n,n);
|
---|
| 780 | #endif
|
---|
| 781 | bn_mul_words(r,a,n,b[0]);
|
---|
| 782 |
|
---|
| 783 | for (;;)
|
---|
| 784 | {
|
---|
| 785 | if (--n <= 0) return;
|
---|
| 786 | bn_mul_add_words(&(r[1]),a,n,b[1]);
|
---|
| 787 | if (--n <= 0) return;
|
---|
| 788 | bn_mul_add_words(&(r[2]),a,n,b[2]);
|
---|
| 789 | if (--n <= 0) return;
|
---|
| 790 | bn_mul_add_words(&(r[3]),a,n,b[3]);
|
---|
| 791 | if (--n <= 0) return;
|
---|
| 792 | bn_mul_add_words(&(r[4]),a,n,b[4]);
|
---|
| 793 | r+=4;
|
---|
| 794 | b+=4;
|
---|
| 795 | }
|
---|
| 796 | }
|
---|