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