| 1 | /*
|
|---|
| 2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
|
|---|
| 3 | *
|
|---|
| 4 | * Licensed under the OpenSSL license (the "License"). You may not use
|
|---|
| 5 | * this file except in compliance with the License. You can obtain a copy
|
|---|
| 6 | * in the file LICENSE in the source distribution or at
|
|---|
| 7 | * https://www.openssl.org/source/license.html
|
|---|
| 8 | */
|
|---|
| 9 |
|
|---|
| 10 | #include <assert.h>
|
|---|
| 11 | #include "internal/cryptlib.h"
|
|---|
| 12 | #include "bn_local.h"
|
|---|
| 13 |
|
|---|
| 14 | #if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS)
|
|---|
| 15 | /*
|
|---|
| 16 | * Here follows specialised variants of bn_add_words() and bn_sub_words().
|
|---|
| 17 | * They have the property performing operations on arrays of different sizes.
|
|---|
| 18 | * The sizes of those arrays is expressed through cl, which is the common
|
|---|
| 19 | * length ( basically, min(len(a),len(b)) ), and dl, which is the delta
|
|---|
| 20 | * between the two lengths, calculated as len(a)-len(b). All lengths are the
|
|---|
| 21 | * number of BN_ULONGs... For the operations that require a result array as
|
|---|
| 22 | * parameter, it must have the length cl+abs(dl). These functions should
|
|---|
| 23 | * probably end up in bn_asm.c as soon as there are assembler counterparts
|
|---|
| 24 | * for the systems that use assembler files.
|
|---|
| 25 | */
|
|---|
| 26 |
|
|---|
| 27 | BN_ULONG bn_sub_part_words(BN_ULONG *r,
|
|---|
| 28 | const BN_ULONG *a, const BN_ULONG *b,
|
|---|
| 29 | int cl, int dl)
|
|---|
| 30 | {
|
|---|
| 31 | BN_ULONG c, t;
|
|---|
| 32 |
|
|---|
| 33 | assert(cl >= 0);
|
|---|
| 34 | c = bn_sub_words(r, a, b, cl);
|
|---|
| 35 |
|
|---|
| 36 | if (dl == 0)
|
|---|
| 37 | return c;
|
|---|
| 38 |
|
|---|
| 39 | r += cl;
|
|---|
| 40 | a += cl;
|
|---|
| 41 | b += cl;
|
|---|
| 42 |
|
|---|
| 43 | if (dl < 0) {
|
|---|
| 44 | for (;;) {
|
|---|
| 45 | t = b[0];
|
|---|
| 46 | r[0] = (0 - t - c) & BN_MASK2;
|
|---|
| 47 | if (t != 0)
|
|---|
| 48 | c = 1;
|
|---|
| 49 | if (++dl >= 0)
|
|---|
| 50 | break;
|
|---|
| 51 |
|
|---|
| 52 | t = b[1];
|
|---|
| 53 | r[1] = (0 - t - c) & BN_MASK2;
|
|---|
| 54 | if (t != 0)
|
|---|
| 55 | c = 1;
|
|---|
| 56 | if (++dl >= 0)
|
|---|
| 57 | break;
|
|---|
| 58 |
|
|---|
| 59 | t = b[2];
|
|---|
| 60 | r[2] = (0 - t - c) & BN_MASK2;
|
|---|
| 61 | if (t != 0)
|
|---|
| 62 | c = 1;
|
|---|
| 63 | if (++dl >= 0)
|
|---|
| 64 | break;
|
|---|
| 65 |
|
|---|
| 66 | t = b[3];
|
|---|
| 67 | r[3] = (0 - t - c) & BN_MASK2;
|
|---|
| 68 | if (t != 0)
|
|---|
| 69 | c = 1;
|
|---|
| 70 | if (++dl >= 0)
|
|---|
| 71 | break;
|
|---|
| 72 |
|
|---|
| 73 | b += 4;
|
|---|
| 74 | r += 4;
|
|---|
| 75 | }
|
|---|
| 76 | } else {
|
|---|
| 77 | int save_dl = dl;
|
|---|
| 78 | while (c) {
|
|---|
| 79 | t = a[0];
|
|---|
| 80 | r[0] = (t - c) & BN_MASK2;
|
|---|
| 81 | if (t != 0)
|
|---|
| 82 | c = 0;
|
|---|
| 83 | if (--dl <= 0)
|
|---|
| 84 | break;
|
|---|
| 85 |
|
|---|
| 86 | t = a[1];
|
|---|
| 87 | r[1] = (t - c) & BN_MASK2;
|
|---|
| 88 | if (t != 0)
|
|---|
| 89 | c = 0;
|
|---|
| 90 | if (--dl <= 0)
|
|---|
| 91 | break;
|
|---|
| 92 |
|
|---|
| 93 | t = a[2];
|
|---|
| 94 | r[2] = (t - c) & BN_MASK2;
|
|---|
| 95 | if (t != 0)
|
|---|
| 96 | c = 0;
|
|---|
| 97 | if (--dl <= 0)
|
|---|
| 98 | break;
|
|---|
| 99 |
|
|---|
| 100 | t = a[3];
|
|---|
| 101 | r[3] = (t - c) & BN_MASK2;
|
|---|
| 102 | if (t != 0)
|
|---|
| 103 | c = 0;
|
|---|
| 104 | if (--dl <= 0)
|
|---|
| 105 | break;
|
|---|
| 106 |
|
|---|
| 107 | save_dl = dl;
|
|---|
| 108 | a += 4;
|
|---|
| 109 | r += 4;
|
|---|
| 110 | }
|
|---|
| 111 | if (dl > 0) {
|
|---|
| 112 | if (save_dl > dl) {
|
|---|
| 113 | switch (save_dl - dl) {
|
|---|
| 114 | case 1:
|
|---|
| 115 | r[1] = a[1];
|
|---|
| 116 | if (--dl <= 0)
|
|---|
| 117 | break;
|
|---|
| 118 | /* fall thru */
|
|---|
| 119 | case 2:
|
|---|
| 120 | r[2] = a[2];
|
|---|
| 121 | if (--dl <= 0)
|
|---|
| 122 | break;
|
|---|
| 123 | /* fall thru */
|
|---|
| 124 | case 3:
|
|---|
| 125 | r[3] = a[3];
|
|---|
| 126 | if (--dl <= 0)
|
|---|
| 127 | break;
|
|---|
| 128 | }
|
|---|
| 129 | a += 4;
|
|---|
| 130 | r += 4;
|
|---|
| 131 | }
|
|---|
| 132 | }
|
|---|
| 133 | if (dl > 0) {
|
|---|
| 134 | for (;;) {
|
|---|
| 135 | r[0] = a[0];
|
|---|
| 136 | if (--dl <= 0)
|
|---|
| 137 | break;
|
|---|
| 138 | r[1] = a[1];
|
|---|
| 139 | if (--dl <= 0)
|
|---|
| 140 | break;
|
|---|
| 141 | r[2] = a[2];
|
|---|
| 142 | if (--dl <= 0)
|
|---|
| 143 | break;
|
|---|
| 144 | r[3] = a[3];
|
|---|
| 145 | if (--dl <= 0)
|
|---|
| 146 | break;
|
|---|
| 147 |
|
|---|
| 148 | a += 4;
|
|---|
| 149 | r += 4;
|
|---|
| 150 | }
|
|---|
| 151 | }
|
|---|
| 152 | }
|
|---|
| 153 | return c;
|
|---|
| 154 | }
|
|---|
| 155 | #endif
|
|---|
| 156 |
|
|---|
| 157 | #ifdef BN_RECURSION
|
|---|
| 158 | /*
|
|---|
| 159 | * Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of
|
|---|
| 160 | * Computer Programming, Vol. 2)
|
|---|
| 161 | */
|
|---|
| 162 |
|
|---|
| 163 | /*-
|
|---|
| 164 | * r is 2*n2 words in size,
|
|---|
| 165 | * a and b are both n2 words in size.
|
|---|
| 166 | * n2 must be a power of 2.
|
|---|
| 167 | * We multiply and return the result.
|
|---|
| 168 | * t must be 2*n2 words in size
|
|---|
| 169 | * We calculate
|
|---|
| 170 | * a[0]*b[0]
|
|---|
| 171 | * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
|
|---|
| 172 | * a[1]*b[1]
|
|---|
| 173 | */
|
|---|
| 174 | /* dnX may not be positive, but n2/2+dnX has to be */
|
|---|
| 175 | void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
|
|---|
| 176 | int dna, int dnb, BN_ULONG *t)
|
|---|
| 177 | {
|
|---|
| 178 | int n = n2 / 2, c1, c2;
|
|---|
| 179 | int tna = n + dna, tnb = n + dnb;
|
|---|
| 180 | unsigned int neg, zero;
|
|---|
| 181 | BN_ULONG ln, lo, *p;
|
|---|
| 182 |
|
|---|
| 183 | # ifdef BN_MUL_COMBA
|
|---|
| 184 | # if 0
|
|---|
| 185 | if (n2 == 4) {
|
|---|
| 186 | bn_mul_comba4(r, a, b);
|
|---|
| 187 | return;
|
|---|
| 188 | }
|
|---|
| 189 | # endif
|
|---|
| 190 | /*
|
|---|
| 191 | * Only call bn_mul_comba 8 if n2 == 8 and the two arrays are complete
|
|---|
| 192 | * [steve]
|
|---|
| 193 | */
|
|---|
| 194 | if (n2 == 8 && dna == 0 && dnb == 0) {
|
|---|
| 195 | bn_mul_comba8(r, a, b);
|
|---|
| 196 | return;
|
|---|
| 197 | }
|
|---|
| 198 | # endif /* BN_MUL_COMBA */
|
|---|
| 199 | /* Else do normal multiply */
|
|---|
| 200 | if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
|
|---|
| 201 | bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
|
|---|
| 202 | if ((dna + dnb) < 0)
|
|---|
| 203 | memset(&r[2 * n2 + dna + dnb], 0,
|
|---|
| 204 | sizeof(BN_ULONG) * -(dna + dnb));
|
|---|
| 205 | return;
|
|---|
| 206 | }
|
|---|
| 207 | /* r=(a[0]-a[1])*(b[1]-b[0]) */
|
|---|
| 208 | c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
|
|---|
| 209 | c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
|
|---|
| 210 | zero = neg = 0;
|
|---|
| 211 | switch (c1 * 3 + c2) {
|
|---|
| 212 | case -4:
|
|---|
| 213 | bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
|
|---|
| 214 | bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
|
|---|
| 215 | break;
|
|---|
| 216 | case -3:
|
|---|
| 217 | zero = 1;
|
|---|
| 218 | break;
|
|---|
| 219 | case -2:
|
|---|
| 220 | bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
|
|---|
| 221 | bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
|
|---|
| 222 | neg = 1;
|
|---|
| 223 | break;
|
|---|
| 224 | case -1:
|
|---|
| 225 | case 0:
|
|---|
| 226 | case 1:
|
|---|
| 227 | zero = 1;
|
|---|
| 228 | break;
|
|---|
| 229 | case 2:
|
|---|
| 230 | bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
|
|---|
| 231 | bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
|
|---|
| 232 | neg = 1;
|
|---|
| 233 | break;
|
|---|
| 234 | case 3:
|
|---|
| 235 | zero = 1;
|
|---|
| 236 | break;
|
|---|
| 237 | case 4:
|
|---|
| 238 | bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
|
|---|
| 239 | bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
|
|---|
| 240 | break;
|
|---|
| 241 | }
|
|---|
| 242 |
|
|---|
| 243 | # ifdef BN_MUL_COMBA
|
|---|
| 244 | if (n == 4 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba4 could take
|
|---|
| 245 | * extra args to do this well */
|
|---|
| 246 | if (!zero)
|
|---|
| 247 | bn_mul_comba4(&(t[n2]), t, &(t[n]));
|
|---|
| 248 | else
|
|---|
| 249 | memset(&t[n2], 0, sizeof(*t) * 8);
|
|---|
| 250 |
|
|---|
| 251 | bn_mul_comba4(r, a, b);
|
|---|
| 252 | bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
|
|---|
| 253 | } else if (n == 8 && dna == 0 && dnb == 0) { /* XXX: bn_mul_comba8 could
|
|---|
| 254 | * take extra args to do
|
|---|
| 255 | * this well */
|
|---|
| 256 | if (!zero)
|
|---|
| 257 | bn_mul_comba8(&(t[n2]), t, &(t[n]));
|
|---|
| 258 | else
|
|---|
| 259 | memset(&t[n2], 0, sizeof(*t) * 16);
|
|---|
| 260 |
|
|---|
| 261 | bn_mul_comba8(r, a, b);
|
|---|
| 262 | bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
|
|---|
| 263 | } else
|
|---|
| 264 | # endif /* BN_MUL_COMBA */
|
|---|
| 265 | {
|
|---|
| 266 | p = &(t[n2 * 2]);
|
|---|
| 267 | if (!zero)
|
|---|
| 268 | bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
|
|---|
| 269 | else
|
|---|
| 270 | memset(&t[n2], 0, sizeof(*t) * n2);
|
|---|
| 271 | bn_mul_recursive(r, a, b, n, 0, 0, p);
|
|---|
| 272 | bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
|
|---|
| 273 | }
|
|---|
| 274 |
|
|---|
| 275 | /*-
|
|---|
| 276 | * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
|
|---|
| 277 | * r[10] holds (a[0]*b[0])
|
|---|
| 278 | * r[32] holds (b[1]*b[1])
|
|---|
| 279 | */
|
|---|
| 280 |
|
|---|
| 281 | c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
|
|---|
| 282 |
|
|---|
| 283 | if (neg) { /* if t[32] is negative */
|
|---|
| 284 | c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
|
|---|
| 285 | } else {
|
|---|
| 286 | /* Might have a carry */
|
|---|
| 287 | c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
|
|---|
| 288 | }
|
|---|
| 289 |
|
|---|
| 290 | /*-
|
|---|
| 291 | * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
|
|---|
| 292 | * r[10] holds (a[0]*b[0])
|
|---|
| 293 | * r[32] holds (b[1]*b[1])
|
|---|
| 294 | * c1 holds the carry bits
|
|---|
| 295 | */
|
|---|
| 296 | c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
|
|---|
| 297 | if (c1) {
|
|---|
| 298 | p = &(r[n + n2]);
|
|---|
| 299 | lo = *p;
|
|---|
| 300 | ln = (lo + c1) & BN_MASK2;
|
|---|
| 301 | *p = ln;
|
|---|
| 302 |
|
|---|
| 303 | /*
|
|---|
| 304 | * The overflow will stop before we over write words we should not
|
|---|
| 305 | * overwrite
|
|---|
| 306 | */
|
|---|
| 307 | if (ln < (BN_ULONG)c1) {
|
|---|
| 308 | do {
|
|---|
| 309 | p++;
|
|---|
| 310 | lo = *p;
|
|---|
| 311 | ln = (lo + 1) & BN_MASK2;
|
|---|
| 312 | *p = ln;
|
|---|
| 313 | } while (ln == 0);
|
|---|
| 314 | }
|
|---|
| 315 | }
|
|---|
| 316 | }
|
|---|
| 317 |
|
|---|
| 318 | /*
|
|---|
| 319 | * n+tn is the word length t needs to be n*4 is size, as does r
|
|---|
| 320 | */
|
|---|
| 321 | /* tnX may not be negative but less than n */
|
|---|
| 322 | void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
|
|---|
| 323 | int tna, int tnb, BN_ULONG *t)
|
|---|
| 324 | {
|
|---|
| 325 | int i, j, n2 = n * 2;
|
|---|
| 326 | int c1, c2, neg;
|
|---|
| 327 | BN_ULONG ln, lo, *p;
|
|---|
| 328 |
|
|---|
| 329 | if (n < 8) {
|
|---|
| 330 | bn_mul_normal(r, a, n + tna, b, n + tnb);
|
|---|
| 331 | return;
|
|---|
| 332 | }
|
|---|
| 333 |
|
|---|
| 334 | /* r=(a[0]-a[1])*(b[1]-b[0]) */
|
|---|
| 335 | c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
|
|---|
| 336 | c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
|
|---|
| 337 | neg = 0;
|
|---|
| 338 | switch (c1 * 3 + c2) {
|
|---|
| 339 | case -4:
|
|---|
| 340 | bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
|
|---|
| 341 | bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
|
|---|
| 342 | break;
|
|---|
| 343 | case -3:
|
|---|
| 344 | case -2:
|
|---|
| 345 | bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */
|
|---|
| 346 | bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */
|
|---|
| 347 | neg = 1;
|
|---|
| 348 | break;
|
|---|
| 349 | case -1:
|
|---|
| 350 | case 0:
|
|---|
| 351 | case 1:
|
|---|
| 352 | case 2:
|
|---|
| 353 | bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */
|
|---|
| 354 | bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */
|
|---|
| 355 | neg = 1;
|
|---|
| 356 | break;
|
|---|
| 357 | case 3:
|
|---|
| 358 | case 4:
|
|---|
| 359 | bn_sub_part_words(t, a, &(a[n]), tna, n - tna);
|
|---|
| 360 | bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);
|
|---|
| 361 | break;
|
|---|
| 362 | }
|
|---|
| 363 | /*
|
|---|
| 364 | * The zero case isn't yet implemented here. The speedup would probably
|
|---|
| 365 | * be negligible.
|
|---|
| 366 | */
|
|---|
| 367 | # if 0
|
|---|
| 368 | if (n == 4) {
|
|---|
| 369 | bn_mul_comba4(&(t[n2]), t, &(t[n]));
|
|---|
| 370 | bn_mul_comba4(r, a, b);
|
|---|
| 371 | bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
|
|---|
| 372 | memset(&r[n2 + tn * 2], 0, sizeof(*r) * (n2 - tn * 2));
|
|---|
| 373 | } else
|
|---|
| 374 | # endif
|
|---|
| 375 | if (n == 8) {
|
|---|
| 376 | bn_mul_comba8(&(t[n2]), t, &(t[n]));
|
|---|
| 377 | bn_mul_comba8(r, a, b);
|
|---|
| 378 | bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
|
|---|
| 379 | memset(&r[n2 + tna + tnb], 0, sizeof(*r) * (n2 - tna - tnb));
|
|---|
| 380 | } else {
|
|---|
| 381 | p = &(t[n2 * 2]);
|
|---|
| 382 | bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
|
|---|
| 383 | bn_mul_recursive(r, a, b, n, 0, 0, p);
|
|---|
| 384 | i = n / 2;
|
|---|
| 385 | /*
|
|---|
| 386 | * If there is only a bottom half to the number, just do it
|
|---|
| 387 | */
|
|---|
| 388 | if (tna > tnb)
|
|---|
| 389 | j = tna - i;
|
|---|
| 390 | else
|
|---|
| 391 | j = tnb - i;
|
|---|
| 392 | if (j == 0) {
|
|---|
| 393 | bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
|
|---|
| 394 | i, tna - i, tnb - i, p);
|
|---|
| 395 | memset(&r[n2 + i * 2], 0, sizeof(*r) * (n2 - i * 2));
|
|---|
| 396 | } else if (j > 0) { /* eg, n == 16, i == 8 and tn == 11 */
|
|---|
| 397 | bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
|
|---|
| 398 | i, tna - i, tnb - i, p);
|
|---|
| 399 | memset(&(r[n2 + tna + tnb]), 0,
|
|---|
| 400 | sizeof(BN_ULONG) * (n2 - tna - tnb));
|
|---|
| 401 | } else { /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
|
|---|
| 402 |
|
|---|
| 403 | memset(&r[n2], 0, sizeof(*r) * n2);
|
|---|
| 404 | if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL
|
|---|
| 405 | && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
|
|---|
| 406 | bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
|
|---|
| 407 | } else {
|
|---|
| 408 | for (;;) {
|
|---|
| 409 | i /= 2;
|
|---|
| 410 | /*
|
|---|
| 411 | * these simplified conditions work exclusively because
|
|---|
| 412 | * difference between tna and tnb is 1 or 0
|
|---|
| 413 | */
|
|---|
| 414 | if (i < tna || i < tnb) {
|
|---|
| 415 | bn_mul_part_recursive(&(r[n2]),
|
|---|
| 416 | &(a[n]), &(b[n]),
|
|---|
| 417 | i, tna - i, tnb - i, p);
|
|---|
| 418 | break;
|
|---|
| 419 | } else if (i == tna || i == tnb) {
|
|---|
| 420 | bn_mul_recursive(&(r[n2]),
|
|---|
| 421 | &(a[n]), &(b[n]),
|
|---|
| 422 | i, tna - i, tnb - i, p);
|
|---|
| 423 | break;
|
|---|
| 424 | }
|
|---|
| 425 | }
|
|---|
| 426 | }
|
|---|
| 427 | }
|
|---|
| 428 | }
|
|---|
| 429 |
|
|---|
| 430 | /*-
|
|---|
| 431 | * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
|
|---|
| 432 | * r[10] holds (a[0]*b[0])
|
|---|
| 433 | * r[32] holds (b[1]*b[1])
|
|---|
| 434 | */
|
|---|
| 435 |
|
|---|
| 436 | c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
|
|---|
| 437 |
|
|---|
| 438 | if (neg) { /* if t[32] is negative */
|
|---|
| 439 | c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
|
|---|
| 440 | } else {
|
|---|
| 441 | /* Might have a carry */
|
|---|
| 442 | c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
|
|---|
| 443 | }
|
|---|
| 444 |
|
|---|
| 445 | /*-
|
|---|
| 446 | * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
|
|---|
| 447 | * r[10] holds (a[0]*b[0])
|
|---|
| 448 | * r[32] holds (b[1]*b[1])
|
|---|
| 449 | * c1 holds the carry bits
|
|---|
| 450 | */
|
|---|
| 451 | c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
|
|---|
| 452 | if (c1) {
|
|---|
| 453 | p = &(r[n + n2]);
|
|---|
| 454 | lo = *p;
|
|---|
| 455 | ln = (lo + c1) & BN_MASK2;
|
|---|
| 456 | *p = ln;
|
|---|
| 457 |
|
|---|
| 458 | /*
|
|---|
| 459 | * The overflow will stop before we over write words we should not
|
|---|
| 460 | * overwrite
|
|---|
| 461 | */
|
|---|
| 462 | if (ln < (BN_ULONG)c1) {
|
|---|
| 463 | do {
|
|---|
| 464 | p++;
|
|---|
| 465 | lo = *p;
|
|---|
| 466 | ln = (lo + 1) & BN_MASK2;
|
|---|
| 467 | *p = ln;
|
|---|
| 468 | } while (ln == 0);
|
|---|
| 469 | }
|
|---|
| 470 | }
|
|---|
| 471 | }
|
|---|
| 472 |
|
|---|
| 473 | /*-
|
|---|
| 474 | * a and b must be the same size, which is n2.
|
|---|
| 475 | * r needs to be n2 words and t needs to be n2*2
|
|---|
| 476 | */
|
|---|
| 477 | void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
|
|---|
| 478 | BN_ULONG *t)
|
|---|
| 479 | {
|
|---|
| 480 | int n = n2 / 2;
|
|---|
| 481 |
|
|---|
| 482 | bn_mul_recursive(r, a, b, n, 0, 0, &(t[0]));
|
|---|
| 483 | if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) {
|
|---|
| 484 | bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2]));
|
|---|
| 485 | bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
|
|---|
| 486 | bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2]));
|
|---|
| 487 | bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
|
|---|
| 488 | } else {
|
|---|
| 489 | bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n);
|
|---|
| 490 | bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n);
|
|---|
| 491 | bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
|
|---|
| 492 | bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
|
|---|
| 493 | }
|
|---|
| 494 | }
|
|---|
| 495 | #endif /* BN_RECURSION */
|
|---|
| 496 |
|
|---|
| 497 | int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
|
|---|
| 498 | {
|
|---|
| 499 | int ret = bn_mul_fixed_top(r, a, b, ctx);
|
|---|
| 500 |
|
|---|
| 501 | bn_correct_top(r);
|
|---|
| 502 | bn_check_top(r);
|
|---|
| 503 |
|
|---|
| 504 | return ret;
|
|---|
| 505 | }
|
|---|
| 506 |
|
|---|
| 507 | int bn_mul_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
|
|---|
| 508 | {
|
|---|
| 509 | int ret = 0;
|
|---|
| 510 | int top, al, bl;
|
|---|
| 511 | BIGNUM *rr;
|
|---|
| 512 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
|
|---|
| 513 | int i;
|
|---|
| 514 | #endif
|
|---|
| 515 | #ifdef BN_RECURSION
|
|---|
| 516 | BIGNUM *t = NULL;
|
|---|
| 517 | int j = 0, k;
|
|---|
| 518 | #endif
|
|---|
| 519 |
|
|---|
| 520 | bn_check_top(a);
|
|---|
| 521 | bn_check_top(b);
|
|---|
| 522 | bn_check_top(r);
|
|---|
| 523 |
|
|---|
| 524 | al = a->top;
|
|---|
| 525 | bl = b->top;
|
|---|
| 526 |
|
|---|
| 527 | if ((al == 0) || (bl == 0)) {
|
|---|
| 528 | BN_zero(r);
|
|---|
| 529 | return 1;
|
|---|
| 530 | }
|
|---|
| 531 | top = al + bl;
|
|---|
| 532 |
|
|---|
| 533 | BN_CTX_start(ctx);
|
|---|
| 534 | if ((r == a) || (r == b)) {
|
|---|
| 535 | if ((rr = BN_CTX_get(ctx)) == NULL)
|
|---|
| 536 | goto err;
|
|---|
| 537 | } else
|
|---|
| 538 | rr = r;
|
|---|
| 539 |
|
|---|
| 540 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
|
|---|
| 541 | i = al - bl;
|
|---|
| 542 | #endif
|
|---|
| 543 | #ifdef BN_MUL_COMBA
|
|---|
| 544 | if (i == 0) {
|
|---|
| 545 | # if 0
|
|---|
| 546 | if (al == 4) {
|
|---|
| 547 | if (bn_wexpand(rr, 8) == NULL)
|
|---|
| 548 | goto err;
|
|---|
| 549 | rr->top = 8;
|
|---|
| 550 | bn_mul_comba4(rr->d, a->d, b->d);
|
|---|
| 551 | goto end;
|
|---|
| 552 | }
|
|---|
| 553 | # endif
|
|---|
| 554 | if (al == 8) {
|
|---|
| 555 | if (bn_wexpand(rr, 16) == NULL)
|
|---|
| 556 | goto err;
|
|---|
| 557 | rr->top = 16;
|
|---|
| 558 | bn_mul_comba8(rr->d, a->d, b->d);
|
|---|
| 559 | goto end;
|
|---|
| 560 | }
|
|---|
| 561 | }
|
|---|
| 562 | #endif /* BN_MUL_COMBA */
|
|---|
| 563 | #ifdef BN_RECURSION
|
|---|
| 564 | if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
|
|---|
| 565 | if (i >= -1 && i <= 1) {
|
|---|
| 566 | /*
|
|---|
| 567 | * Find out the power of two lower or equal to the longest of the
|
|---|
| 568 | * two numbers
|
|---|
| 569 | */
|
|---|
| 570 | if (i >= 0) {
|
|---|
| 571 | j = BN_num_bits_word((BN_ULONG)al);
|
|---|
| 572 | }
|
|---|
| 573 | if (i == -1) {
|
|---|
| 574 | j = BN_num_bits_word((BN_ULONG)bl);
|
|---|
| 575 | }
|
|---|
| 576 | j = 1 << (j - 1);
|
|---|
| 577 | assert(j <= al || j <= bl);
|
|---|
| 578 | k = j + j;
|
|---|
| 579 | t = BN_CTX_get(ctx);
|
|---|
| 580 | if (t == NULL)
|
|---|
| 581 | goto err;
|
|---|
| 582 | if (al > j || bl > j) {
|
|---|
| 583 | if (bn_wexpand(t, k * 4) == NULL)
|
|---|
| 584 | goto err;
|
|---|
| 585 | if (bn_wexpand(rr, k * 4) == NULL)
|
|---|
| 586 | goto err;
|
|---|
| 587 | bn_mul_part_recursive(rr->d, a->d, b->d,
|
|---|
| 588 | j, al - j, bl - j, t->d);
|
|---|
| 589 | } else { /* al <= j || bl <= j */
|
|---|
| 590 |
|
|---|
| 591 | if (bn_wexpand(t, k * 2) == NULL)
|
|---|
| 592 | goto err;
|
|---|
| 593 | if (bn_wexpand(rr, k * 2) == NULL)
|
|---|
| 594 | goto err;
|
|---|
| 595 | bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d);
|
|---|
| 596 | }
|
|---|
| 597 | rr->top = top;
|
|---|
| 598 | goto end;
|
|---|
| 599 | }
|
|---|
| 600 | }
|
|---|
| 601 | #endif /* BN_RECURSION */
|
|---|
| 602 | if (bn_wexpand(rr, top) == NULL)
|
|---|
| 603 | goto err;
|
|---|
| 604 | rr->top = top;
|
|---|
| 605 | bn_mul_normal(rr->d, a->d, al, b->d, bl);
|
|---|
| 606 |
|
|---|
| 607 | #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
|
|---|
| 608 | end:
|
|---|
| 609 | #endif
|
|---|
| 610 | rr->neg = a->neg ^ b->neg;
|
|---|
| 611 | rr->flags |= BN_FLG_FIXED_TOP;
|
|---|
| 612 | if (r != rr && BN_copy(r, rr) == NULL)
|
|---|
| 613 | goto err;
|
|---|
| 614 |
|
|---|
| 615 | ret = 1;
|
|---|
| 616 | err:
|
|---|
| 617 | bn_check_top(r);
|
|---|
| 618 | BN_CTX_end(ctx);
|
|---|
| 619 | return ret;
|
|---|
| 620 | }
|
|---|
| 621 |
|
|---|
| 622 | void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
|
|---|
| 623 | {
|
|---|
| 624 | BN_ULONG *rr;
|
|---|
| 625 |
|
|---|
| 626 | if (na < nb) {
|
|---|
| 627 | int itmp;
|
|---|
| 628 | BN_ULONG *ltmp;
|
|---|
| 629 |
|
|---|
| 630 | itmp = na;
|
|---|
| 631 | na = nb;
|
|---|
| 632 | nb = itmp;
|
|---|
| 633 | ltmp = a;
|
|---|
| 634 | a = b;
|
|---|
| 635 | b = ltmp;
|
|---|
| 636 |
|
|---|
| 637 | }
|
|---|
| 638 | rr = &(r[na]);
|
|---|
| 639 | if (nb <= 0) {
|
|---|
| 640 | (void)bn_mul_words(r, a, na, 0);
|
|---|
| 641 | return;
|
|---|
| 642 | } else
|
|---|
| 643 | rr[0] = bn_mul_words(r, a, na, b[0]);
|
|---|
| 644 |
|
|---|
| 645 | for (;;) {
|
|---|
| 646 | if (--nb <= 0)
|
|---|
| 647 | return;
|
|---|
| 648 | rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
|
|---|
| 649 | if (--nb <= 0)
|
|---|
| 650 | return;
|
|---|
| 651 | rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
|
|---|
| 652 | if (--nb <= 0)
|
|---|
| 653 | return;
|
|---|
| 654 | rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
|
|---|
| 655 | if (--nb <= 0)
|
|---|
| 656 | return;
|
|---|
| 657 | rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
|
|---|
| 658 | rr += 4;
|
|---|
| 659 | r += 4;
|
|---|
| 660 | b += 4;
|
|---|
| 661 | }
|
|---|
| 662 | }
|
|---|
| 663 |
|
|---|
| 664 | void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
|
|---|
| 665 | {
|
|---|
| 666 | bn_mul_words(r, a, n, b[0]);
|
|---|
| 667 |
|
|---|
| 668 | for (;;) {
|
|---|
| 669 | if (--n <= 0)
|
|---|
| 670 | return;
|
|---|
| 671 | bn_mul_add_words(&(r[1]), a, n, b[1]);
|
|---|
| 672 | if (--n <= 0)
|
|---|
| 673 | return;
|
|---|
| 674 | bn_mul_add_words(&(r[2]), a, n, b[2]);
|
|---|
| 675 | if (--n <= 0)
|
|---|
| 676 | return;
|
|---|
| 677 | bn_mul_add_words(&(r[3]), a, n, b[3]);
|
|---|
| 678 | if (--n <= 0)
|
|---|
| 679 | return;
|
|---|
| 680 | bn_mul_add_words(&(r[4]), a, n, b[4]);
|
|---|
| 681 | r += 4;
|
|---|
| 682 | b += 4;
|
|---|
| 683 | }
|
|---|
| 684 | }
|
|---|
