1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * CDDL HEADER START 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*0Sstevel@tonic-gate * with the License. 8*0Sstevel@tonic-gate * 9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*0Sstevel@tonic-gate * See the License for the specific language governing permissions 12*0Sstevel@tonic-gate * and limitations under the License. 13*0Sstevel@tonic-gate * 14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*0Sstevel@tonic-gate * 20*0Sstevel@tonic-gate * CDDL HEADER END 21*0Sstevel@tonic-gate */ 22*0Sstevel@tonic-gate /* 23*0Sstevel@tonic-gate * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24*0Sstevel@tonic-gate * Use is subject to license terms. 25*0Sstevel@tonic-gate */ 26*0Sstevel@tonic-gate 27*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 28*0Sstevel@tonic-gate 29*0Sstevel@tonic-gate #define big_div_pos_fast big_div_pos 30*0Sstevel@tonic-gate 31*0Sstevel@tonic-gate #include "bignum.h" 32*0Sstevel@tonic-gate 33*0Sstevel@tonic-gate /* 34*0Sstevel@tonic-gate * Configuration guide 35*0Sstevel@tonic-gate * ------------------- 36*0Sstevel@tonic-gate * 37*0Sstevel@tonic-gate * There are 4 preprocessor symbols used to configure the bignum 38*0Sstevel@tonic-gate * implementation. This file contains no logic to configure based on 39*0Sstevel@tonic-gate * processor; we leave that to the Makefiles to specify. 40*0Sstevel@tonic-gate * 41*0Sstevel@tonic-gate * USE_FLOATING_POINT 42*0Sstevel@tonic-gate * Meaning: There is support for a fast floating-point implementation of 43*0Sstevel@tonic-gate * Montgomery multiply. 44*0Sstevel@tonic-gate * 45*0Sstevel@tonic-gate * PSR_MUL 46*0Sstevel@tonic-gate * Meaning: There are processor-specific versions of the low level 47*0Sstevel@tonic-gate * functions to implement big_mul. Those functions are: big_mul_set_vec, 48*0Sstevel@tonic-gate * big_mul_add_vec, big_mul_vec, and big_sqr_vec. PSR_MUL implies support 49*0Sstevel@tonic-gate * for all 4 functions. You cannot pick and choose which subset of these 50*0Sstevel@tonic-gate * functions to support; that would lead to a rat's nest of #ifdefs. 51*0Sstevel@tonic-gate * 52*0Sstevel@tonic-gate * HWCAP 53*0Sstevel@tonic-gate * Meaning: Call multiply support functions through a function pointer. 54*0Sstevel@tonic-gate * On x86, there are multiple implementations for differnt hardware 55*0Sstevel@tonic-gate * capabilities, such as MMX, SSE2, etc. Tests are made at run-time, when 56*0Sstevel@tonic-gate * a function is first used. So, the support functions are called through 57*0Sstevel@tonic-gate * a function pointer. There is no need for that on Sparc, because there 58*0Sstevel@tonic-gate * is only one implementation; support functions are called directly. 59*0Sstevel@tonic-gate * Later, if there were some new VIS instruction, or something, and a 60*0Sstevel@tonic-gate * run-time test were needed, rather than variant kernel modules and 61*0Sstevel@tonic-gate * libraries, then HWCAP would be defined for Sparc, as well. 62*0Sstevel@tonic-gate * 63*0Sstevel@tonic-gate * UMUL64 64*0Sstevel@tonic-gate * Meaning: It is safe to use generic C code that assumes the existence 65*0Sstevel@tonic-gate * of a 32 x 32 --> 64 bit unsigned multiply. If this is not defined, 66*0Sstevel@tonic-gate * then the generic code for big_mul_add_vec() must necessarily be very slow, 67*0Sstevel@tonic-gate * because it must fall back to using 16 x 16 --> 32 bit multiplication. 68*0Sstevel@tonic-gate * 69*0Sstevel@tonic-gate */ 70*0Sstevel@tonic-gate 71*0Sstevel@tonic-gate 72*0Sstevel@tonic-gate #ifdef _KERNEL 73*0Sstevel@tonic-gate 74*0Sstevel@tonic-gate #include <sys/types.h> 75*0Sstevel@tonic-gate #include <sys/kmem.h> 76*0Sstevel@tonic-gate #include <sys/param.h> 77*0Sstevel@tonic-gate #include <sys/sunddi.h> 78*0Sstevel@tonic-gate 79*0Sstevel@tonic-gate #define big_malloc(size) kmem_alloc(size, KM_NOSLEEP) 80*0Sstevel@tonic-gate #define big_free(ptr, size) kmem_free(ptr, size) 81*0Sstevel@tonic-gate 82*0Sstevel@tonic-gate void * 83*0Sstevel@tonic-gate big_realloc(void *from, size_t oldsize, size_t newsize) 84*0Sstevel@tonic-gate { 85*0Sstevel@tonic-gate void *rv; 86*0Sstevel@tonic-gate 87*0Sstevel@tonic-gate rv = kmem_alloc(newsize, KM_NOSLEEP); 88*0Sstevel@tonic-gate if (rv != NULL) 89*0Sstevel@tonic-gate bcopy(from, rv, oldsize); 90*0Sstevel@tonic-gate kmem_free(from, oldsize); 91*0Sstevel@tonic-gate return (rv); 92*0Sstevel@tonic-gate } 93*0Sstevel@tonic-gate 94*0Sstevel@tonic-gate #else /* _KERNEL */ 95*0Sstevel@tonic-gate 96*0Sstevel@tonic-gate #include <stdlib.h> 97*0Sstevel@tonic-gate #include <stdio.h> 98*0Sstevel@tonic-gate 99*0Sstevel@tonic-gate #ifndef MALLOC_DEBUG 100*0Sstevel@tonic-gate 101*0Sstevel@tonic-gate #define big_malloc(size) malloc(size) 102*0Sstevel@tonic-gate #define big_free(ptr, size) free(ptr) 103*0Sstevel@tonic-gate 104*0Sstevel@tonic-gate #else 105*0Sstevel@tonic-gate 106*0Sstevel@tonic-gate void 107*0Sstevel@tonic-gate big_free(void *ptr, size_t size) 108*0Sstevel@tonic-gate { 109*0Sstevel@tonic-gate printf("freed %d bytes at %p\n", size, ptr); 110*0Sstevel@tonic-gate free(ptr); 111*0Sstevel@tonic-gate } 112*0Sstevel@tonic-gate 113*0Sstevel@tonic-gate void * 114*0Sstevel@tonic-gate big_malloc(size_t size) 115*0Sstevel@tonic-gate { 116*0Sstevel@tonic-gate void *rv; 117*0Sstevel@tonic-gate rv = malloc(size); 118*0Sstevel@tonic-gate printf("malloced %d bytes, addr:%p\n", size, rv); 119*0Sstevel@tonic-gate return (rv); 120*0Sstevel@tonic-gate } 121*0Sstevel@tonic-gate #endif /* MALLOC_DEBUG */ 122*0Sstevel@tonic-gate 123*0Sstevel@tonic-gate #define big_realloc(x, y, z) realloc((x), (z)) 124*0Sstevel@tonic-gate 125*0Sstevel@tonic-gate void 126*0Sstevel@tonic-gate printbignum(char *aname, BIGNUM *a) 127*0Sstevel@tonic-gate { 128*0Sstevel@tonic-gate int i; 129*0Sstevel@tonic-gate 130*0Sstevel@tonic-gate (void) printf("\n%s\n%d\n", aname, a->sign*a->len); 131*0Sstevel@tonic-gate for (i = a->len - 1; i >= 0; i--) { 132*0Sstevel@tonic-gate (void) printf("%08x ", a->value[i]); 133*0Sstevel@tonic-gate if ((i % 8 == 0) && (i != 0)) 134*0Sstevel@tonic-gate (void) printf("\n"); 135*0Sstevel@tonic-gate } 136*0Sstevel@tonic-gate (void) printf("\n"); 137*0Sstevel@tonic-gate } 138*0Sstevel@tonic-gate 139*0Sstevel@tonic-gate #endif /* _KERNEL */ 140*0Sstevel@tonic-gate 141*0Sstevel@tonic-gate 142*0Sstevel@tonic-gate /* size in 32-bit words */ 143*0Sstevel@tonic-gate BIG_ERR_CODE 144*0Sstevel@tonic-gate big_init(BIGNUM *number, int size) 145*0Sstevel@tonic-gate { 146*0Sstevel@tonic-gate number->value = big_malloc(sizeof (uint32_t) * size); 147*0Sstevel@tonic-gate if (number->value == NULL) { 148*0Sstevel@tonic-gate return (BIG_NO_MEM); 149*0Sstevel@tonic-gate } 150*0Sstevel@tonic-gate number->size = size; 151*0Sstevel@tonic-gate number->len = 0; 152*0Sstevel@tonic-gate number->sign = 1; 153*0Sstevel@tonic-gate number->malloced = 1; 154*0Sstevel@tonic-gate return (BIG_OK); 155*0Sstevel@tonic-gate } 156*0Sstevel@tonic-gate 157*0Sstevel@tonic-gate /* size in 32-bit words */ 158*0Sstevel@tonic-gate BIG_ERR_CODE 159*0Sstevel@tonic-gate big_init1(BIGNUM *number, int size, uint32_t *buf, int bufsize) 160*0Sstevel@tonic-gate { 161*0Sstevel@tonic-gate if ((buf == NULL) || (size > bufsize)) { 162*0Sstevel@tonic-gate number->value = big_malloc(sizeof (uint32_t) * size); 163*0Sstevel@tonic-gate if (number->value == NULL) { 164*0Sstevel@tonic-gate return (BIG_NO_MEM); 165*0Sstevel@tonic-gate } 166*0Sstevel@tonic-gate number->size = size; 167*0Sstevel@tonic-gate number->malloced = 1; 168*0Sstevel@tonic-gate } else { 169*0Sstevel@tonic-gate number->value = buf; 170*0Sstevel@tonic-gate number->size = bufsize; 171*0Sstevel@tonic-gate number->malloced = 0; 172*0Sstevel@tonic-gate } 173*0Sstevel@tonic-gate number->len = 0; 174*0Sstevel@tonic-gate number->sign = 1; 175*0Sstevel@tonic-gate 176*0Sstevel@tonic-gate return (BIG_OK); 177*0Sstevel@tonic-gate } 178*0Sstevel@tonic-gate 179*0Sstevel@tonic-gate void 180*0Sstevel@tonic-gate big_finish(BIGNUM *number) 181*0Sstevel@tonic-gate { 182*0Sstevel@tonic-gate if (number->malloced == 1) { 183*0Sstevel@tonic-gate big_free(number->value, sizeof (uint32_t) * number->size); 184*0Sstevel@tonic-gate number->malloced = 0; 185*0Sstevel@tonic-gate } 186*0Sstevel@tonic-gate } 187*0Sstevel@tonic-gate 188*0Sstevel@tonic-gate /* 189*0Sstevel@tonic-gate * bn->size should be at least (len + 3) / 4 190*0Sstevel@tonic-gate * converts from byte-big-endian format to bignum format (words in 191*0Sstevel@tonic-gate * little endian order, but bytes within the words big endian) 192*0Sstevel@tonic-gate */ 193*0Sstevel@tonic-gate void 194*0Sstevel@tonic-gate bytestring2bignum(BIGNUM *bn, uchar_t *kn, size_t len) 195*0Sstevel@tonic-gate { 196*0Sstevel@tonic-gate int i, j, offs; 197*0Sstevel@tonic-gate uint32_t word; 198*0Sstevel@tonic-gate uchar_t *knwordp; 199*0Sstevel@tonic-gate 200*0Sstevel@tonic-gate #ifdef _LP64 201*0Sstevel@tonic-gate /* LINTED */ 202*0Sstevel@tonic-gate offs = (uint32_t)len % sizeof (uint32_t); 203*0Sstevel@tonic-gate /* LINTED */ 204*0Sstevel@tonic-gate bn->len = (uint32_t)len / sizeof (uint32_t); 205*0Sstevel@tonic-gate /* LINTED */ 206*0Sstevel@tonic-gate for (i = 0; i < (uint32_t)len / sizeof (uint32_t); i++) { 207*0Sstevel@tonic-gate #else /* !_LP64 */ 208*0Sstevel@tonic-gate offs = len % sizeof (uint32_t); 209*0Sstevel@tonic-gate bn->len = len / sizeof (uint32_t); 210*0Sstevel@tonic-gate for (i = 0; i < len / sizeof (uint32_t); i++) { 211*0Sstevel@tonic-gate #endif /* _LP64 */ 212*0Sstevel@tonic-gate knwordp = &(kn[len - sizeof (uint32_t) * (i + 1)]); 213*0Sstevel@tonic-gate word = knwordp[0]; 214*0Sstevel@tonic-gate for (j = 1; j < sizeof (uint32_t); j++) { 215*0Sstevel@tonic-gate word = (word << 8)+ knwordp[j]; 216*0Sstevel@tonic-gate } 217*0Sstevel@tonic-gate bn->value[i] = word; 218*0Sstevel@tonic-gate } 219*0Sstevel@tonic-gate if (offs > 0) { 220*0Sstevel@tonic-gate word = kn[0]; 221*0Sstevel@tonic-gate for (i = 1; i < offs; i++) word = (word << 8) + kn[i]; 222*0Sstevel@tonic-gate bn->value[bn->len++] = word; 223*0Sstevel@tonic-gate } 224*0Sstevel@tonic-gate while ((bn->len > 1) && (bn->value[bn->len-1] == 0)) { 225*0Sstevel@tonic-gate bn->len --; 226*0Sstevel@tonic-gate } 227*0Sstevel@tonic-gate } 228*0Sstevel@tonic-gate 229*0Sstevel@tonic-gate /* 230*0Sstevel@tonic-gate * copies the least significant len bytes if 231*0Sstevel@tonic-gate * len < bn->len * sizeof (uint32_t) 232*0Sstevel@tonic-gate * converts from bignum format to byte-big-endian format. 233*0Sstevel@tonic-gate * bignum format is words in little endian order, 234*0Sstevel@tonic-gate * but bytes within words in native byte order. 235*0Sstevel@tonic-gate */ 236*0Sstevel@tonic-gate void 237*0Sstevel@tonic-gate bignum2bytestring(uchar_t *kn, BIGNUM *bn, size_t len) 238*0Sstevel@tonic-gate { 239*0Sstevel@tonic-gate int i, j, offs; 240*0Sstevel@tonic-gate uint32_t word; 241*0Sstevel@tonic-gate 242*0Sstevel@tonic-gate if (len < sizeof (uint32_t) * bn->len) { 243*0Sstevel@tonic-gate #ifdef _LP64 244*0Sstevel@tonic-gate /* LINTED */ 245*0Sstevel@tonic-gate for (i = 0; i < (uint32_t)len / sizeof (uint32_t); i++) { 246*0Sstevel@tonic-gate #else /* !_LP64 */ 247*0Sstevel@tonic-gate for (i = 0; i < len / sizeof (uint32_t); i++) { 248*0Sstevel@tonic-gate #endif /* _LP64 */ 249*0Sstevel@tonic-gate word = bn->value[i]; 250*0Sstevel@tonic-gate for (j = 0; j < sizeof (uint32_t); j++) { 251*0Sstevel@tonic-gate kn[len - sizeof (uint32_t) * i - j - 1] = 252*0Sstevel@tonic-gate word & 0xff; 253*0Sstevel@tonic-gate word = word >> 8; 254*0Sstevel@tonic-gate } 255*0Sstevel@tonic-gate } 256*0Sstevel@tonic-gate #ifdef _LP64 257*0Sstevel@tonic-gate /* LINTED */ 258*0Sstevel@tonic-gate offs = (uint32_t)len % sizeof (uint32_t); 259*0Sstevel@tonic-gate #else /* !_LP64 */ 260*0Sstevel@tonic-gate offs = len % sizeof (uint32_t); 261*0Sstevel@tonic-gate #endif /* _LP64 */ 262*0Sstevel@tonic-gate if (offs > 0) { 263*0Sstevel@tonic-gate word = bn->value[len / sizeof (uint32_t)]; 264*0Sstevel@tonic-gate #ifdef _LP64 265*0Sstevel@tonic-gate /* LINTED */ 266*0Sstevel@tonic-gate for (i = (uint32_t)len % sizeof (uint32_t); 267*0Sstevel@tonic-gate i > 0; i --) { 268*0Sstevel@tonic-gate #else /* !_LP64 */ 269*0Sstevel@tonic-gate for (i = len % sizeof (uint32_t); i > 0; i --) { 270*0Sstevel@tonic-gate #endif /* _LP64 */ 271*0Sstevel@tonic-gate kn[i - 1] = word & 0xff; 272*0Sstevel@tonic-gate word = word >> 8; 273*0Sstevel@tonic-gate } 274*0Sstevel@tonic-gate } 275*0Sstevel@tonic-gate } else { 276*0Sstevel@tonic-gate for (i = 0; i < bn->len; i++) { 277*0Sstevel@tonic-gate word = bn->value[i]; 278*0Sstevel@tonic-gate for (j = 0; j < sizeof (uint32_t); j++) { 279*0Sstevel@tonic-gate kn[len - sizeof (uint32_t) * i - j - 1] = 280*0Sstevel@tonic-gate word & 0xff; 281*0Sstevel@tonic-gate word = word >> 8; 282*0Sstevel@tonic-gate } 283*0Sstevel@tonic-gate } 284*0Sstevel@tonic-gate #ifdef _LP64 285*0Sstevel@tonic-gate /* LINTED */ 286*0Sstevel@tonic-gate for (i = 0; i < (uint32_t)len - sizeof (uint32_t) * bn->len; 287*0Sstevel@tonic-gate i++) { 288*0Sstevel@tonic-gate #else /* !_LP64 */ 289*0Sstevel@tonic-gate for (i = 0; i < len - sizeof (uint32_t) * bn->len; i++) { 290*0Sstevel@tonic-gate #endif /* _LP64 */ 291*0Sstevel@tonic-gate kn[i] = 0; 292*0Sstevel@tonic-gate } 293*0Sstevel@tonic-gate } 294*0Sstevel@tonic-gate } 295*0Sstevel@tonic-gate 296*0Sstevel@tonic-gate 297*0Sstevel@tonic-gate int 298*0Sstevel@tonic-gate big_bitlength(BIGNUM *a) 299*0Sstevel@tonic-gate { 300*0Sstevel@tonic-gate int l, b; 301*0Sstevel@tonic-gate uint32_t c; 302*0Sstevel@tonic-gate 303*0Sstevel@tonic-gate l = a->len - 1; 304*0Sstevel@tonic-gate while ((l > 0) && (a->value[l] == 0)) { 305*0Sstevel@tonic-gate l--; 306*0Sstevel@tonic-gate } 307*0Sstevel@tonic-gate b = sizeof (uint32_t) * 8; 308*0Sstevel@tonic-gate c = a->value[l]; 309*0Sstevel@tonic-gate while ((b > 1) && ((c & 0x80000000) == 0)) { 310*0Sstevel@tonic-gate c = c << 1; 311*0Sstevel@tonic-gate b--; 312*0Sstevel@tonic-gate } 313*0Sstevel@tonic-gate return (l * (int)sizeof (uint32_t) * 8 + b); 314*0Sstevel@tonic-gate } 315*0Sstevel@tonic-gate 316*0Sstevel@tonic-gate 317*0Sstevel@tonic-gate BIG_ERR_CODE 318*0Sstevel@tonic-gate big_copy(BIGNUM *dest, BIGNUM *src) 319*0Sstevel@tonic-gate { 320*0Sstevel@tonic-gate uint32_t *newptr; 321*0Sstevel@tonic-gate int i, len; 322*0Sstevel@tonic-gate 323*0Sstevel@tonic-gate len = src->len; 324*0Sstevel@tonic-gate while ((len > 1) && (src->value[len - 1] == 0)) 325*0Sstevel@tonic-gate len--; 326*0Sstevel@tonic-gate src->len = len; 327*0Sstevel@tonic-gate if (dest->size < len) { 328*0Sstevel@tonic-gate if (dest->malloced == 1) { 329*0Sstevel@tonic-gate newptr = (uint32_t *)big_realloc(dest->value, 330*0Sstevel@tonic-gate sizeof (uint32_t) * dest->size, 331*0Sstevel@tonic-gate sizeof (uint32_t) * len); 332*0Sstevel@tonic-gate } else { 333*0Sstevel@tonic-gate newptr = (uint32_t *) 334*0Sstevel@tonic-gate big_malloc(sizeof (uint32_t) * len); 335*0Sstevel@tonic-gate if (newptr != NULL) dest->malloced = 1; 336*0Sstevel@tonic-gate } 337*0Sstevel@tonic-gate if (newptr == NULL) 338*0Sstevel@tonic-gate return (BIG_NO_MEM); 339*0Sstevel@tonic-gate dest->value = newptr; 340*0Sstevel@tonic-gate dest->size = len; 341*0Sstevel@tonic-gate } 342*0Sstevel@tonic-gate dest->len = len; 343*0Sstevel@tonic-gate dest->sign = src->sign; 344*0Sstevel@tonic-gate for (i = 0; i < len; i++) dest->value[i] = src->value[i]; 345*0Sstevel@tonic-gate 346*0Sstevel@tonic-gate return (BIG_OK); 347*0Sstevel@tonic-gate } 348*0Sstevel@tonic-gate 349*0Sstevel@tonic-gate 350*0Sstevel@tonic-gate BIG_ERR_CODE 351*0Sstevel@tonic-gate big_extend(BIGNUM *number, int size) 352*0Sstevel@tonic-gate { 353*0Sstevel@tonic-gate uint32_t *newptr; 354*0Sstevel@tonic-gate int i; 355*0Sstevel@tonic-gate 356*0Sstevel@tonic-gate if (number->size >= size) 357*0Sstevel@tonic-gate return (BIG_OK); 358*0Sstevel@tonic-gate if (number->malloced) { 359*0Sstevel@tonic-gate number->value = 360*0Sstevel@tonic-gate big_realloc(number->value, 361*0Sstevel@tonic-gate sizeof (uint32_t) * number->size, 362*0Sstevel@tonic-gate sizeof (uint32_t) * size); 363*0Sstevel@tonic-gate } else { 364*0Sstevel@tonic-gate newptr = big_malloc(sizeof (uint32_t) * size); 365*0Sstevel@tonic-gate if (newptr != NULL) { 366*0Sstevel@tonic-gate for (i = 0; i < number->size; i++) { 367*0Sstevel@tonic-gate newptr[i] = number->value[i]; 368*0Sstevel@tonic-gate } 369*0Sstevel@tonic-gate } 370*0Sstevel@tonic-gate number->value = newptr; 371*0Sstevel@tonic-gate } 372*0Sstevel@tonic-gate 373*0Sstevel@tonic-gate if (number->value == NULL) 374*0Sstevel@tonic-gate return (BIG_NO_MEM); 375*0Sstevel@tonic-gate 376*0Sstevel@tonic-gate number->size = size; 377*0Sstevel@tonic-gate number->malloced = 1; 378*0Sstevel@tonic-gate return (BIG_OK); 379*0Sstevel@tonic-gate } 380*0Sstevel@tonic-gate 381*0Sstevel@tonic-gate 382*0Sstevel@tonic-gate int 383*0Sstevel@tonic-gate big_is_zero(BIGNUM *n) 384*0Sstevel@tonic-gate { 385*0Sstevel@tonic-gate int i, result; 386*0Sstevel@tonic-gate 387*0Sstevel@tonic-gate result = 1; 388*0Sstevel@tonic-gate for (i = 0; i < n->len; i++) 389*0Sstevel@tonic-gate if (n->value[i] != 0) result = 0; 390*0Sstevel@tonic-gate return (result); 391*0Sstevel@tonic-gate } 392*0Sstevel@tonic-gate 393*0Sstevel@tonic-gate 394*0Sstevel@tonic-gate BIG_ERR_CODE 395*0Sstevel@tonic-gate big_add_abs(BIGNUM *result, BIGNUM *aa, BIGNUM *bb) 396*0Sstevel@tonic-gate { 397*0Sstevel@tonic-gate int i, shorter, longer; 398*0Sstevel@tonic-gate uint32_t cy, ai; 399*0Sstevel@tonic-gate uint32_t *r, *a, *b, *c; 400*0Sstevel@tonic-gate BIG_ERR_CODE err; 401*0Sstevel@tonic-gate 402*0Sstevel@tonic-gate if (aa->len > bb->len) { 403*0Sstevel@tonic-gate shorter = bb->len; 404*0Sstevel@tonic-gate longer = aa->len; 405*0Sstevel@tonic-gate c = aa->value; 406*0Sstevel@tonic-gate } else { 407*0Sstevel@tonic-gate shorter = aa->len; 408*0Sstevel@tonic-gate longer = bb->len; 409*0Sstevel@tonic-gate c = bb->value; 410*0Sstevel@tonic-gate } 411*0Sstevel@tonic-gate if (result->size < longer + 1) { 412*0Sstevel@tonic-gate err = big_extend(result, longer + 1); 413*0Sstevel@tonic-gate if (err != BIG_OK) 414*0Sstevel@tonic-gate return (err); 415*0Sstevel@tonic-gate } 416*0Sstevel@tonic-gate 417*0Sstevel@tonic-gate r = result->value; 418*0Sstevel@tonic-gate a = aa->value; 419*0Sstevel@tonic-gate b = bb->value; 420*0Sstevel@tonic-gate cy = 0; 421*0Sstevel@tonic-gate for (i = 0; i < shorter; i++) { 422*0Sstevel@tonic-gate ai = a[i]; 423*0Sstevel@tonic-gate r[i] = ai + b[i] + cy; 424*0Sstevel@tonic-gate if (r[i] > ai) cy = 0; 425*0Sstevel@tonic-gate else if (r[i] < ai) cy = 1; 426*0Sstevel@tonic-gate } 427*0Sstevel@tonic-gate for (; i < longer; i++) { 428*0Sstevel@tonic-gate ai = c[i]; 429*0Sstevel@tonic-gate r[i] = ai + cy; 430*0Sstevel@tonic-gate if (r[i] >= ai) cy = 0; 431*0Sstevel@tonic-gate } 432*0Sstevel@tonic-gate if (cy == 1) { 433*0Sstevel@tonic-gate r[i] = cy; 434*0Sstevel@tonic-gate result->len = longer + 1; 435*0Sstevel@tonic-gate } else { 436*0Sstevel@tonic-gate result->len = longer; 437*0Sstevel@tonic-gate } 438*0Sstevel@tonic-gate result->sign = 1; 439*0Sstevel@tonic-gate return (BIG_OK); 440*0Sstevel@tonic-gate } 441*0Sstevel@tonic-gate 442*0Sstevel@tonic-gate 443*0Sstevel@tonic-gate /* caller must make sure that result has at least len words allocated */ 444*0Sstevel@tonic-gate void 445*0Sstevel@tonic-gate big_sub_vec(uint32_t *r, uint32_t *a, uint32_t *b, int len) 446*0Sstevel@tonic-gate { 447*0Sstevel@tonic-gate int i; 448*0Sstevel@tonic-gate uint32_t cy, ai; 449*0Sstevel@tonic-gate 450*0Sstevel@tonic-gate cy = 1; 451*0Sstevel@tonic-gate for (i = 0; i < len; i++) { 452*0Sstevel@tonic-gate ai = a[i]; 453*0Sstevel@tonic-gate r[i] = ai + (~b[i]) + cy; 454*0Sstevel@tonic-gate if (r[i] > ai) cy = 0; 455*0Sstevel@tonic-gate else if (r[i] < ai) cy = 1; 456*0Sstevel@tonic-gate } 457*0Sstevel@tonic-gate } 458*0Sstevel@tonic-gate 459*0Sstevel@tonic-gate 460*0Sstevel@tonic-gate /* result=aa-bb it is assumed that aa>=bb */ 461*0Sstevel@tonic-gate BIG_ERR_CODE 462*0Sstevel@tonic-gate big_sub_pos(BIGNUM *result, BIGNUM *aa, BIGNUM *bb) 463*0Sstevel@tonic-gate { 464*0Sstevel@tonic-gate int i, shorter; 465*0Sstevel@tonic-gate uint32_t cy, ai; 466*0Sstevel@tonic-gate uint32_t *r, *a, *b; 467*0Sstevel@tonic-gate BIG_ERR_CODE err; 468*0Sstevel@tonic-gate 469*0Sstevel@tonic-gate if (aa->len > bb->len) shorter = bb->len; 470*0Sstevel@tonic-gate else shorter = aa->len; 471*0Sstevel@tonic-gate if (result->size < aa->len) { 472*0Sstevel@tonic-gate err = big_extend(result, aa->len); 473*0Sstevel@tonic-gate if (err != BIG_OK) 474*0Sstevel@tonic-gate return (err); 475*0Sstevel@tonic-gate } 476*0Sstevel@tonic-gate 477*0Sstevel@tonic-gate r = result->value; 478*0Sstevel@tonic-gate a = aa->value; 479*0Sstevel@tonic-gate b = bb->value; 480*0Sstevel@tonic-gate result->len = aa->len; 481*0Sstevel@tonic-gate cy = 1; 482*0Sstevel@tonic-gate for (i = 0; i < shorter; i++) { 483*0Sstevel@tonic-gate ai = a[i]; 484*0Sstevel@tonic-gate r[i] = ai + (~b[i]) + cy; 485*0Sstevel@tonic-gate if (r[i] > ai) cy = 0; 486*0Sstevel@tonic-gate else if (r[i] < ai) cy = 1; 487*0Sstevel@tonic-gate } 488*0Sstevel@tonic-gate for (; i < aa->len; i++) { 489*0Sstevel@tonic-gate ai = a[i]; 490*0Sstevel@tonic-gate r[i] = ai + (~0) + cy; 491*0Sstevel@tonic-gate if (r[i] < ai) cy = 1; 492*0Sstevel@tonic-gate } 493*0Sstevel@tonic-gate result->sign = 1; 494*0Sstevel@tonic-gate if (cy == 0) 495*0Sstevel@tonic-gate return (BIG_INVALID_ARGS); 496*0Sstevel@tonic-gate else 497*0Sstevel@tonic-gate return (BIG_OK); 498*0Sstevel@tonic-gate } 499*0Sstevel@tonic-gate 500*0Sstevel@tonic-gate 501*0Sstevel@tonic-gate /* returns -1 if |aa|<|bb|, 0 if |aa|==|bb| 1 if |aa|>|bb| */ 502*0Sstevel@tonic-gate int 503*0Sstevel@tonic-gate big_cmp_abs(BIGNUM *aa, BIGNUM *bb) 504*0Sstevel@tonic-gate { 505*0Sstevel@tonic-gate int i; 506*0Sstevel@tonic-gate 507*0Sstevel@tonic-gate if (aa->len > bb->len) { 508*0Sstevel@tonic-gate for (i = aa->len - 1; i > bb->len - 1; i--) { 509*0Sstevel@tonic-gate if (aa->value[i] > 0) 510*0Sstevel@tonic-gate return (1); 511*0Sstevel@tonic-gate } 512*0Sstevel@tonic-gate } else if (aa->len < bb->len) { 513*0Sstevel@tonic-gate for (i = bb->len - 1; i > aa->len - 1; i--) { 514*0Sstevel@tonic-gate if (bb->value[i] > 0) 515*0Sstevel@tonic-gate return (-1); 516*0Sstevel@tonic-gate } 517*0Sstevel@tonic-gate } else i = aa->len-1; 518*0Sstevel@tonic-gate for (; i >= 0; i--) { 519*0Sstevel@tonic-gate if (aa->value[i] > bb->value[i]) 520*0Sstevel@tonic-gate return (1); 521*0Sstevel@tonic-gate else if (aa->value[i] < bb->value[i]) 522*0Sstevel@tonic-gate return (-1); 523*0Sstevel@tonic-gate } 524*0Sstevel@tonic-gate 525*0Sstevel@tonic-gate return (0); 526*0Sstevel@tonic-gate } 527*0Sstevel@tonic-gate 528*0Sstevel@tonic-gate 529*0Sstevel@tonic-gate BIG_ERR_CODE 530*0Sstevel@tonic-gate big_sub(BIGNUM *result, BIGNUM *aa, BIGNUM *bb) 531*0Sstevel@tonic-gate { 532*0Sstevel@tonic-gate BIG_ERR_CODE err; 533*0Sstevel@tonic-gate 534*0Sstevel@tonic-gate if ((bb->sign == -1) && (aa->sign == 1)) { 535*0Sstevel@tonic-gate if ((err = big_add_abs(result, aa, bb)) != BIG_OK) 536*0Sstevel@tonic-gate return (err); 537*0Sstevel@tonic-gate result->sign = 1; 538*0Sstevel@tonic-gate } else if ((aa->sign == -1) && (bb->sign == 1)) { 539*0Sstevel@tonic-gate if ((err = big_add_abs(result, aa, bb)) != BIG_OK) 540*0Sstevel@tonic-gate return (err); 541*0Sstevel@tonic-gate result->sign = -1; 542*0Sstevel@tonic-gate } else if ((aa->sign == 1) && (bb->sign == 1)) { 543*0Sstevel@tonic-gate if (big_cmp_abs(aa, bb) >= 0) { 544*0Sstevel@tonic-gate if ((err = big_sub_pos(result, aa, bb)) != BIG_OK) 545*0Sstevel@tonic-gate return (err); 546*0Sstevel@tonic-gate result->sign = 1; 547*0Sstevel@tonic-gate } else { 548*0Sstevel@tonic-gate if ((err = big_sub_pos(result, bb, aa)) != BIG_OK) 549*0Sstevel@tonic-gate return (err); 550*0Sstevel@tonic-gate result->sign = -1; 551*0Sstevel@tonic-gate } 552*0Sstevel@tonic-gate } else { 553*0Sstevel@tonic-gate if (big_cmp_abs(aa, bb) >= 0) { 554*0Sstevel@tonic-gate if ((err = big_sub_pos(result, aa, bb)) != BIG_OK) 555*0Sstevel@tonic-gate return (err); 556*0Sstevel@tonic-gate result->sign = -1; 557*0Sstevel@tonic-gate } else { 558*0Sstevel@tonic-gate if ((err = big_sub_pos(result, bb, aa)) != BIG_OK) 559*0Sstevel@tonic-gate return (err); 560*0Sstevel@tonic-gate result->sign = 1; 561*0Sstevel@tonic-gate } 562*0Sstevel@tonic-gate } 563*0Sstevel@tonic-gate return (BIG_OK); 564*0Sstevel@tonic-gate } 565*0Sstevel@tonic-gate 566*0Sstevel@tonic-gate 567*0Sstevel@tonic-gate 568*0Sstevel@tonic-gate BIG_ERR_CODE 569*0Sstevel@tonic-gate big_add(BIGNUM *result, BIGNUM *aa, BIGNUM *bb) 570*0Sstevel@tonic-gate { 571*0Sstevel@tonic-gate BIG_ERR_CODE err; 572*0Sstevel@tonic-gate 573*0Sstevel@tonic-gate if ((bb->sign == -1) && (aa->sign == -1)) { 574*0Sstevel@tonic-gate if ((err = big_add_abs(result, aa, bb)) != BIG_OK) 575*0Sstevel@tonic-gate return (err); 576*0Sstevel@tonic-gate result->sign = -1; 577*0Sstevel@tonic-gate } else if ((aa->sign == 1) && (bb->sign == 1)) { 578*0Sstevel@tonic-gate if ((err = big_add_abs(result, aa, bb)) != BIG_OK) 579*0Sstevel@tonic-gate return (err); 580*0Sstevel@tonic-gate result->sign = 1; 581*0Sstevel@tonic-gate } else if ((aa->sign == 1) && (bb->sign == -1)) { 582*0Sstevel@tonic-gate if (big_cmp_abs(aa, bb) >= 0) { 583*0Sstevel@tonic-gate if ((err = big_sub_pos(result, aa, bb)) != BIG_OK) 584*0Sstevel@tonic-gate return (err); 585*0Sstevel@tonic-gate result->sign = 1; 586*0Sstevel@tonic-gate } else { 587*0Sstevel@tonic-gate if ((err = big_sub_pos(result, bb, aa)) != BIG_OK) 588*0Sstevel@tonic-gate return (err); 589*0Sstevel@tonic-gate result->sign = -1; 590*0Sstevel@tonic-gate } 591*0Sstevel@tonic-gate } else { 592*0Sstevel@tonic-gate if (big_cmp_abs(aa, bb) >= 0) { 593*0Sstevel@tonic-gate if ((err = big_sub_pos(result, aa, bb)) != BIG_OK) 594*0Sstevel@tonic-gate return (err); 595*0Sstevel@tonic-gate result->sign = -1; 596*0Sstevel@tonic-gate } else { 597*0Sstevel@tonic-gate if ((err = big_sub_pos(result, bb, aa)) != BIG_OK) 598*0Sstevel@tonic-gate return (err); 599*0Sstevel@tonic-gate result->sign = 1; 600*0Sstevel@tonic-gate } 601*0Sstevel@tonic-gate } 602*0Sstevel@tonic-gate return (BIG_OK); 603*0Sstevel@tonic-gate } 604*0Sstevel@tonic-gate 605*0Sstevel@tonic-gate 606*0Sstevel@tonic-gate /* result = aa/2 aa must be positive */ 607*0Sstevel@tonic-gate BIG_ERR_CODE 608*0Sstevel@tonic-gate big_half_pos(BIGNUM *result, BIGNUM *aa) 609*0Sstevel@tonic-gate { 610*0Sstevel@tonic-gate BIG_ERR_CODE err; 611*0Sstevel@tonic-gate int i; 612*0Sstevel@tonic-gate uint32_t cy, cy1; 613*0Sstevel@tonic-gate uint32_t *a, *r; 614*0Sstevel@tonic-gate 615*0Sstevel@tonic-gate if (result->size < aa->len) { 616*0Sstevel@tonic-gate err = big_extend(result, aa->len); 617*0Sstevel@tonic-gate if (err != BIG_OK) 618*0Sstevel@tonic-gate return (err); 619*0Sstevel@tonic-gate } 620*0Sstevel@tonic-gate 621*0Sstevel@tonic-gate result->len = aa->len; 622*0Sstevel@tonic-gate a = aa->value; 623*0Sstevel@tonic-gate r = result->value; 624*0Sstevel@tonic-gate cy = 0; 625*0Sstevel@tonic-gate for (i = aa->len-1; i >= 0; i--) { 626*0Sstevel@tonic-gate cy1 = a[i] << 31; 627*0Sstevel@tonic-gate r[i] = (cy|(a[i] >> 1)); 628*0Sstevel@tonic-gate cy = cy1; 629*0Sstevel@tonic-gate } 630*0Sstevel@tonic-gate if (r[result->len-1] == 0) result->len--; 631*0Sstevel@tonic-gate return (BIG_OK); 632*0Sstevel@tonic-gate } 633*0Sstevel@tonic-gate 634*0Sstevel@tonic-gate /* result = aa*2 aa must be positive */ 635*0Sstevel@tonic-gate BIG_ERR_CODE 636*0Sstevel@tonic-gate big_double(BIGNUM *result, BIGNUM *aa) 637*0Sstevel@tonic-gate { 638*0Sstevel@tonic-gate BIG_ERR_CODE err; 639*0Sstevel@tonic-gate int i, rsize; 640*0Sstevel@tonic-gate uint32_t cy, cy1; 641*0Sstevel@tonic-gate uint32_t *a, *r; 642*0Sstevel@tonic-gate 643*0Sstevel@tonic-gate if ((aa->len > 0) && ((aa->value[aa->len - 1] & 0x80000000) != 0)) 644*0Sstevel@tonic-gate rsize = aa->len + 1; 645*0Sstevel@tonic-gate else rsize = aa->len; 646*0Sstevel@tonic-gate 647*0Sstevel@tonic-gate if (result->size < rsize) { 648*0Sstevel@tonic-gate err = big_extend(result, rsize); 649*0Sstevel@tonic-gate if (err != BIG_OK) 650*0Sstevel@tonic-gate return (err); 651*0Sstevel@tonic-gate } 652*0Sstevel@tonic-gate 653*0Sstevel@tonic-gate a = aa->value; 654*0Sstevel@tonic-gate r = result->value; 655*0Sstevel@tonic-gate if (rsize == aa->len + 1) r[rsize - 1] = 1; 656*0Sstevel@tonic-gate cy = 0; 657*0Sstevel@tonic-gate for (i = 0; i < aa->len; i++) { 658*0Sstevel@tonic-gate cy1 = a[i] >> 31; 659*0Sstevel@tonic-gate r[i] = (cy | (a[i] << 1)); 660*0Sstevel@tonic-gate cy = cy1; 661*0Sstevel@tonic-gate } 662*0Sstevel@tonic-gate result->len = rsize; 663*0Sstevel@tonic-gate return (BIG_OK); 664*0Sstevel@tonic-gate } 665*0Sstevel@tonic-gate 666*0Sstevel@tonic-gate /* returns aa mod b, aa must be nonneg, b must be a max 16-bit integer */ 667*0Sstevel@tonic-gate uint32_t 668*0Sstevel@tonic-gate big_mod16_pos(BIGNUM *aa, uint32_t b) 669*0Sstevel@tonic-gate { 670*0Sstevel@tonic-gate int i; 671*0Sstevel@tonic-gate uint32_t rem; 672*0Sstevel@tonic-gate 673*0Sstevel@tonic-gate if (aa->len == 0) 674*0Sstevel@tonic-gate return (0); 675*0Sstevel@tonic-gate rem = aa->value[aa->len - 1] % b; 676*0Sstevel@tonic-gate for (i = aa->len - 2; i >= 0; i--) { 677*0Sstevel@tonic-gate rem = ((rem << 16) | (aa->value[i] >> 16)) % b; 678*0Sstevel@tonic-gate rem = ((rem << 16) | (aa->value[i] & 0xffff)) % b; 679*0Sstevel@tonic-gate } 680*0Sstevel@tonic-gate return (rem); 681*0Sstevel@tonic-gate } 682*0Sstevel@tonic-gate 683*0Sstevel@tonic-gate 684*0Sstevel@tonic-gate /* 685*0Sstevel@tonic-gate * result = aa - (2^32)^lendiff * bb 686*0Sstevel@tonic-gate * result->size should be at least aa->len at entry 687*0Sstevel@tonic-gate * aa, bb, and result should be positive 688*0Sstevel@tonic-gate */ 689*0Sstevel@tonic-gate void 690*0Sstevel@tonic-gate big_sub_pos_high(BIGNUM *result, BIGNUM *aa, BIGNUM *bb) 691*0Sstevel@tonic-gate { 692*0Sstevel@tonic-gate int i, lendiff; 693*0Sstevel@tonic-gate BIGNUM res1, aa1; 694*0Sstevel@tonic-gate 695*0Sstevel@tonic-gate lendiff = aa->len - bb->len; 696*0Sstevel@tonic-gate res1.size = result->size - lendiff; 697*0Sstevel@tonic-gate res1.malloced = 0; 698*0Sstevel@tonic-gate res1.value = result->value + lendiff; 699*0Sstevel@tonic-gate aa1.size = aa->size - lendiff; 700*0Sstevel@tonic-gate aa1.value = aa->value + lendiff; 701*0Sstevel@tonic-gate aa1.len = bb->len; 702*0Sstevel@tonic-gate aa1.sign = 1; 703*0Sstevel@tonic-gate (void) big_sub_pos(&res1, &aa1, bb); 704*0Sstevel@tonic-gate if (result->value != aa->value) { 705*0Sstevel@tonic-gate for (i = 0; i < lendiff; i++) { 706*0Sstevel@tonic-gate result->value[i] = aa->value[i]; 707*0Sstevel@tonic-gate } 708*0Sstevel@tonic-gate } 709*0Sstevel@tonic-gate result->len = aa->len; 710*0Sstevel@tonic-gate } 711*0Sstevel@tonic-gate 712*0Sstevel@tonic-gate 713*0Sstevel@tonic-gate /* 714*0Sstevel@tonic-gate * returns 1, 0, or -1 depending on whether |aa| > , ==, or < 715*0Sstevel@tonic-gate * (2^32)^lendiff * |bb| 716*0Sstevel@tonic-gate * aa->len should be >= bb->len 717*0Sstevel@tonic-gate */ 718*0Sstevel@tonic-gate int 719*0Sstevel@tonic-gate big_cmp_abs_high(BIGNUM *aa, BIGNUM *bb) 720*0Sstevel@tonic-gate { 721*0Sstevel@tonic-gate int lendiff; 722*0Sstevel@tonic-gate BIGNUM aa1; 723*0Sstevel@tonic-gate 724*0Sstevel@tonic-gate lendiff = aa->len - bb->len; 725*0Sstevel@tonic-gate aa1.len = bb->len; 726*0Sstevel@tonic-gate aa1.size = aa->size - lendiff; 727*0Sstevel@tonic-gate aa1.malloced = 0; 728*0Sstevel@tonic-gate aa1.value = aa->value + lendiff; 729*0Sstevel@tonic-gate return (big_cmp_abs(&aa1, bb)); 730*0Sstevel@tonic-gate } 731*0Sstevel@tonic-gate 732*0Sstevel@tonic-gate 733*0Sstevel@tonic-gate /* 734*0Sstevel@tonic-gate * result = aa * b where b is a max. 16-bit positive integer. 735*0Sstevel@tonic-gate * result should have enough space allocated. 736*0Sstevel@tonic-gate */ 737*0Sstevel@tonic-gate void 738*0Sstevel@tonic-gate big_mul16_low(BIGNUM *result, BIGNUM *aa, uint32_t b) 739*0Sstevel@tonic-gate { 740*0Sstevel@tonic-gate int i; 741*0Sstevel@tonic-gate uint32_t t1, t2, ai, cy; 742*0Sstevel@tonic-gate uint32_t *a, *r; 743*0Sstevel@tonic-gate 744*0Sstevel@tonic-gate a = aa->value; 745*0Sstevel@tonic-gate r = result->value; 746*0Sstevel@tonic-gate cy = 0; 747*0Sstevel@tonic-gate for (i = 0; i < aa->len; i++) { 748*0Sstevel@tonic-gate ai = a[i]; 749*0Sstevel@tonic-gate t1 = (ai & 0xffff) * b + cy; 750*0Sstevel@tonic-gate t2 = (ai >> 16) * b + (t1 >> 16); 751*0Sstevel@tonic-gate r[i] = (t1 & 0xffff) | (t2 << 16); 752*0Sstevel@tonic-gate cy = t2 >> 16; 753*0Sstevel@tonic-gate } 754*0Sstevel@tonic-gate r[i] = cy; 755*0Sstevel@tonic-gate result->len = aa->len + 1; 756*0Sstevel@tonic-gate result->sign = aa->sign; 757*0Sstevel@tonic-gate } 758*0Sstevel@tonic-gate 759*0Sstevel@tonic-gate 760*0Sstevel@tonic-gate /* 761*0Sstevel@tonic-gate * result = aa * b * 2^16 where b is a max. 16-bit positive integer. 762*0Sstevel@tonic-gate * result should have enough space allocated. 763*0Sstevel@tonic-gate */ 764*0Sstevel@tonic-gate void 765*0Sstevel@tonic-gate big_mul16_high(BIGNUM *result, BIGNUM *aa, uint32_t b) 766*0Sstevel@tonic-gate { 767*0Sstevel@tonic-gate int i; 768*0Sstevel@tonic-gate uint32_t t1, t2, ai, cy, ri; 769*0Sstevel@tonic-gate uint32_t *a, *r; 770*0Sstevel@tonic-gate 771*0Sstevel@tonic-gate a = aa->value; 772*0Sstevel@tonic-gate r = result->value; 773*0Sstevel@tonic-gate cy = 0; 774*0Sstevel@tonic-gate ri = 0; 775*0Sstevel@tonic-gate for (i = 0; i < aa->len; i++) { 776*0Sstevel@tonic-gate ai = a[i]; 777*0Sstevel@tonic-gate t1 = (ai & 0xffff) * b + cy; 778*0Sstevel@tonic-gate t2 = (ai >> 16) * b + (t1 >> 16); 779*0Sstevel@tonic-gate r[i] = (t1 << 16) + ri; 780*0Sstevel@tonic-gate ri = t2 & 0xffff; 781*0Sstevel@tonic-gate cy = t2 >> 16; 782*0Sstevel@tonic-gate } 783*0Sstevel@tonic-gate r[i] = (cy << 16) + ri; 784*0Sstevel@tonic-gate result->len = aa->len + 1; 785*0Sstevel@tonic-gate result->sign = aa->sign; 786*0Sstevel@tonic-gate } 787*0Sstevel@tonic-gate 788*0Sstevel@tonic-gate /* it is assumed that result->size is big enough */ 789*0Sstevel@tonic-gate void 790*0Sstevel@tonic-gate big_shiftleft(BIGNUM *result, BIGNUM *aa, int offs) 791*0Sstevel@tonic-gate { 792*0Sstevel@tonic-gate int i; 793*0Sstevel@tonic-gate uint32_t cy, ai; 794*0Sstevel@tonic-gate 795*0Sstevel@tonic-gate if (offs == 0) { 796*0Sstevel@tonic-gate if (result != aa) { 797*0Sstevel@tonic-gate (void) big_copy(result, aa); 798*0Sstevel@tonic-gate } 799*0Sstevel@tonic-gate return; 800*0Sstevel@tonic-gate } 801*0Sstevel@tonic-gate cy = 0; 802*0Sstevel@tonic-gate for (i = 0; i < aa->len; i++) { 803*0Sstevel@tonic-gate ai = aa->value[i]; 804*0Sstevel@tonic-gate result->value[i] = (ai << offs) | cy; 805*0Sstevel@tonic-gate cy = ai >> (32 - offs); 806*0Sstevel@tonic-gate } 807*0Sstevel@tonic-gate if (cy != 0) { 808*0Sstevel@tonic-gate result->len = aa->len + 1; 809*0Sstevel@tonic-gate result->value[result->len - 1] = cy; 810*0Sstevel@tonic-gate } else { 811*0Sstevel@tonic-gate result->len = aa->len; 812*0Sstevel@tonic-gate } 813*0Sstevel@tonic-gate result->sign = aa->sign; 814*0Sstevel@tonic-gate } 815*0Sstevel@tonic-gate 816*0Sstevel@tonic-gate /* it is assumed that result->size is big enough */ 817*0Sstevel@tonic-gate void 818*0Sstevel@tonic-gate big_shiftright(BIGNUM *result, BIGNUM *aa, int offs) 819*0Sstevel@tonic-gate { 820*0Sstevel@tonic-gate int i; 821*0Sstevel@tonic-gate uint32_t cy, ai; 822*0Sstevel@tonic-gate 823*0Sstevel@tonic-gate if (offs == 0) { 824*0Sstevel@tonic-gate if (result != aa) { 825*0Sstevel@tonic-gate (void) big_copy(result, aa); 826*0Sstevel@tonic-gate } 827*0Sstevel@tonic-gate return; 828*0Sstevel@tonic-gate } 829*0Sstevel@tonic-gate cy = aa->value[0] >> offs; 830*0Sstevel@tonic-gate for (i = 1; i < aa->len; i++) { 831*0Sstevel@tonic-gate ai = aa->value[i]; 832*0Sstevel@tonic-gate result->value[i-1] = (ai << (32 - offs)) | cy; 833*0Sstevel@tonic-gate cy = ai >> offs; 834*0Sstevel@tonic-gate } 835*0Sstevel@tonic-gate result->len = aa->len; 836*0Sstevel@tonic-gate result->value[result->len - 1] = cy; 837*0Sstevel@tonic-gate result->sign = aa->sign; 838*0Sstevel@tonic-gate } 839*0Sstevel@tonic-gate 840*0Sstevel@tonic-gate 841*0Sstevel@tonic-gate /* 842*0Sstevel@tonic-gate * result = aa/bb remainder = aa mod bb 843*0Sstevel@tonic-gate * it is assumed that aa and bb are positive 844*0Sstevel@tonic-gate */ 845*0Sstevel@tonic-gate BIG_ERR_CODE 846*0Sstevel@tonic-gate big_div_pos_fast(BIGNUM *result, BIGNUM *remainder, BIGNUM *aa, BIGNUM *bb) 847*0Sstevel@tonic-gate { 848*0Sstevel@tonic-gate BIG_ERR_CODE err; 849*0Sstevel@tonic-gate int i, alen, blen, tlen, rlen, offs; 850*0Sstevel@tonic-gate uint32_t higha, highb, coeff; 851*0Sstevel@tonic-gate uint64_t highb64; 852*0Sstevel@tonic-gate uint32_t *a, *b; 853*0Sstevel@tonic-gate BIGNUM bbhigh, bblow, tresult, tmp1, tmp2; 854*0Sstevel@tonic-gate uint32_t tmp1value[BIGTMPSIZE]; 855*0Sstevel@tonic-gate uint32_t tmp2value[BIGTMPSIZE]; 856*0Sstevel@tonic-gate uint32_t tresultvalue[BIGTMPSIZE]; 857*0Sstevel@tonic-gate uint32_t bblowvalue[BIGTMPSIZE]; 858*0Sstevel@tonic-gate uint32_t bbhighvalue[BIGTMPSIZE]; 859*0Sstevel@tonic-gate 860*0Sstevel@tonic-gate a = aa->value; 861*0Sstevel@tonic-gate b = bb->value; 862*0Sstevel@tonic-gate alen = aa->len; 863*0Sstevel@tonic-gate blen = bb->len; 864*0Sstevel@tonic-gate while ((alen > 1) && (a[alen - 1] == 0)) alen = alen - 1; 865*0Sstevel@tonic-gate aa->len = alen; 866*0Sstevel@tonic-gate while ((blen > 1) && (b[blen - 1] == 0)) blen = blen - 1; 867*0Sstevel@tonic-gate bb->len = blen; 868*0Sstevel@tonic-gate if ((blen == 1) && (b[0] == 0)) 869*0Sstevel@tonic-gate return (BIG_DIV_BY_0); 870*0Sstevel@tonic-gate 871*0Sstevel@tonic-gate if (big_cmp_abs(aa, bb) < 0) { 872*0Sstevel@tonic-gate if ((remainder != NULL) && 873*0Sstevel@tonic-gate ((err = big_copy(remainder, aa)) != BIG_OK)) 874*0Sstevel@tonic-gate return (err); 875*0Sstevel@tonic-gate if (result != NULL) { 876*0Sstevel@tonic-gate result->len = 1; 877*0Sstevel@tonic-gate result->sign = 1; 878*0Sstevel@tonic-gate result->value[0] = 0; 879*0Sstevel@tonic-gate } 880*0Sstevel@tonic-gate return (BIG_OK); 881*0Sstevel@tonic-gate } 882*0Sstevel@tonic-gate 883*0Sstevel@tonic-gate if ((err = big_init1(&bblow, blen + 1, 884*0Sstevel@tonic-gate bblowvalue, arraysize(bblowvalue))) != BIG_OK) 885*0Sstevel@tonic-gate return (err); 886*0Sstevel@tonic-gate 887*0Sstevel@tonic-gate if ((err = big_init1(&bbhigh, blen + 1, 888*0Sstevel@tonic-gate bbhighvalue, arraysize(bbhighvalue))) != BIG_OK) 889*0Sstevel@tonic-gate goto ret1; 890*0Sstevel@tonic-gate 891*0Sstevel@tonic-gate if ((err = big_init1(&tmp1, alen + 2, 892*0Sstevel@tonic-gate tmp1value, arraysize(tmp1value))) != BIG_OK) 893*0Sstevel@tonic-gate goto ret2; 894*0Sstevel@tonic-gate 895*0Sstevel@tonic-gate if ((err = big_init1(&tmp2, blen + 2, 896*0Sstevel@tonic-gate tmp2value, arraysize(tmp2value))) != BIG_OK) 897*0Sstevel@tonic-gate goto ret3; 898*0Sstevel@tonic-gate 899*0Sstevel@tonic-gate if ((err = big_init1(&tresult, alen - blen + 2, 900*0Sstevel@tonic-gate tresultvalue, arraysize(tresultvalue))) != BIG_OK) 901*0Sstevel@tonic-gate goto ret4; 902*0Sstevel@tonic-gate 903*0Sstevel@tonic-gate offs = 0; 904*0Sstevel@tonic-gate if (blen > 1) { 905*0Sstevel@tonic-gate highb64 = (((uint64_t)(b[blen - 1])) << 32) | 906*0Sstevel@tonic-gate ((uint64_t)(b[blen - 2])); 907*0Sstevel@tonic-gate } else { 908*0Sstevel@tonic-gate highb64 = (((uint64_t)(b[blen - 1])) << 32); 909*0Sstevel@tonic-gate } 910*0Sstevel@tonic-gate if (highb64 >= 0x1000000000000ull) { 911*0Sstevel@tonic-gate highb64 = highb64 >> 16; 912*0Sstevel@tonic-gate offs = 16; 913*0Sstevel@tonic-gate } 914*0Sstevel@tonic-gate while ((highb64 & 0x800000000000ull) == 0) { 915*0Sstevel@tonic-gate highb64 = highb64 << 1; 916*0Sstevel@tonic-gate offs++; 917*0Sstevel@tonic-gate } 918*0Sstevel@tonic-gate #ifdef _LP64 919*0Sstevel@tonic-gate /* LINTED */ 920*0Sstevel@tonic-gate highb = (highb64 >> 32) & 0xffffffff; 921*0Sstevel@tonic-gate #else /* !_LP64 */ 922*0Sstevel@tonic-gate highb = highb64 >> 32; 923*0Sstevel@tonic-gate #endif /* _LP64 */ 924*0Sstevel@tonic-gate 925*0Sstevel@tonic-gate big_shiftleft(&bblow, bb, offs); 926*0Sstevel@tonic-gate if (offs <= 15) { 927*0Sstevel@tonic-gate big_shiftleft(&bbhigh, &bblow, 16); 928*0Sstevel@tonic-gate } else { 929*0Sstevel@tonic-gate big_shiftright(&bbhigh, &bblow, 16); 930*0Sstevel@tonic-gate } 931*0Sstevel@tonic-gate if (bbhigh.value[bbhigh.len - 1] == 0) { 932*0Sstevel@tonic-gate bbhigh.len--; 933*0Sstevel@tonic-gate } else { 934*0Sstevel@tonic-gate bbhigh.value[bbhigh.len] = 0; 935*0Sstevel@tonic-gate } 936*0Sstevel@tonic-gate 937*0Sstevel@tonic-gate big_shiftleft(&tmp1, aa, offs); 938*0Sstevel@tonic-gate rlen = tmp1.len - bblow.len + 1; 939*0Sstevel@tonic-gate tresult.len = rlen; 940*0Sstevel@tonic-gate 941*0Sstevel@tonic-gate tmp1.len++; 942*0Sstevel@tonic-gate tlen = tmp1.len; 943*0Sstevel@tonic-gate tmp1.value[tmp1.len - 1] = 0; 944*0Sstevel@tonic-gate for (i = 0; i < rlen; i++) { 945*0Sstevel@tonic-gate higha = (tmp1.value[tlen - 1] << 16) + 946*0Sstevel@tonic-gate (tmp1.value[tlen - 2] >> 16); 947*0Sstevel@tonic-gate coeff = higha / (highb + 1); 948*0Sstevel@tonic-gate big_mul16_high(&tmp2, &bblow, coeff); 949*0Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &tmp2); 950*0Sstevel@tonic-gate bbhigh.len++; 951*0Sstevel@tonic-gate while (tmp1.value[tlen - 1] > 0) { 952*0Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &bbhigh); 953*0Sstevel@tonic-gate coeff++; 954*0Sstevel@tonic-gate } 955*0Sstevel@tonic-gate bbhigh.len--; 956*0Sstevel@tonic-gate tlen--; 957*0Sstevel@tonic-gate tmp1.len--; 958*0Sstevel@tonic-gate while (big_cmp_abs_high(&tmp1, &bbhigh) >= 0) { 959*0Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &bbhigh); 960*0Sstevel@tonic-gate coeff++; 961*0Sstevel@tonic-gate } 962*0Sstevel@tonic-gate tresult.value[rlen - i - 1] = coeff << 16; 963*0Sstevel@tonic-gate higha = tmp1.value[tlen - 1]; 964*0Sstevel@tonic-gate coeff = higha / (highb + 1); 965*0Sstevel@tonic-gate big_mul16_low(&tmp2, &bblow, coeff); 966*0Sstevel@tonic-gate tmp2.len--; 967*0Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &tmp2); 968*0Sstevel@tonic-gate while (big_cmp_abs_high(&tmp1, &bblow) >= 0) { 969*0Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &bblow); 970*0Sstevel@tonic-gate coeff++; 971*0Sstevel@tonic-gate } 972*0Sstevel@tonic-gate tresult.value[rlen - i - 1] = 973*0Sstevel@tonic-gate tresult.value[rlen - i - 1] + coeff; 974*0Sstevel@tonic-gate } 975*0Sstevel@tonic-gate 976*0Sstevel@tonic-gate big_shiftright(&tmp1, &tmp1, offs); 977*0Sstevel@tonic-gate 978*0Sstevel@tonic-gate err = BIG_OK; 979*0Sstevel@tonic-gate 980*0Sstevel@tonic-gate if ((remainder != NULL) && 981*0Sstevel@tonic-gate ((err = big_copy(remainder, &tmp1)) != BIG_OK)) 982*0Sstevel@tonic-gate goto ret; 983*0Sstevel@tonic-gate 984*0Sstevel@tonic-gate if (result != NULL) 985*0Sstevel@tonic-gate err = big_copy(result, &tresult); 986*0Sstevel@tonic-gate 987*0Sstevel@tonic-gate ret: 988*0Sstevel@tonic-gate big_finish(&tresult); 989*0Sstevel@tonic-gate ret4: 990*0Sstevel@tonic-gate big_finish(&tmp1); 991*0Sstevel@tonic-gate ret3: 992*0Sstevel@tonic-gate big_finish(&tmp2); 993*0Sstevel@tonic-gate ret2: 994*0Sstevel@tonic-gate big_finish(&bbhigh); 995*0Sstevel@tonic-gate ret1: 996*0Sstevel@tonic-gate big_finish(&bblow); 997*0Sstevel@tonic-gate return (err); 998*0Sstevel@tonic-gate } 999*0Sstevel@tonic-gate 1000*0Sstevel@tonic-gate /* 1001*0Sstevel@tonic-gate * If there is no processor-specific integer implementation of 1002*0Sstevel@tonic-gate * the lower level multiply functions, then this code is provided 1003*0Sstevel@tonic-gate * for big_mul_set_vec(), big_mul_add_vec(), big_mul_vec() and 1004*0Sstevel@tonic-gate * big_sqr_vec(). 1005*0Sstevel@tonic-gate * 1006*0Sstevel@tonic-gate * There are two generic implementations. One that assumes that 1007*0Sstevel@tonic-gate * there is hardware and C compiler support for a 32 x 32 --> 64 1008*0Sstevel@tonic-gate * bit unsigned multiply, but otherwise is not specific to any 1009*0Sstevel@tonic-gate * processor, platform, or ISA. 1010*0Sstevel@tonic-gate * 1011*0Sstevel@tonic-gate * The other makes very few assumptions about hardware capabilities. 1012*0Sstevel@tonic-gate * It does not even assume that there is any implementation of a 1013*0Sstevel@tonic-gate * 32 x 32 --> 64 bit multiply that is accessible to C code and 1014*0Sstevel@tonic-gate * appropriate to use. It falls constructs 32 x 32 --> 64 bit 1015*0Sstevel@tonic-gate * multiplies from 16 x 16 --> 32 bit multiplies. 1016*0Sstevel@tonic-gate * 1017*0Sstevel@tonic-gate */ 1018*0Sstevel@tonic-gate 1019*0Sstevel@tonic-gate #if !defined(PSR_MUL) 1020*0Sstevel@tonic-gate 1021*0Sstevel@tonic-gate #ifdef UMUL64 1022*0Sstevel@tonic-gate 1023*0Sstevel@tonic-gate #define UNROLL8 1024*0Sstevel@tonic-gate 1025*0Sstevel@tonic-gate #define MUL_SET_VEC_ROUND_PREFETCH(R) \ 1026*0Sstevel@tonic-gate p = pf * d; \ 1027*0Sstevel@tonic-gate pf = (uint64_t)a[R+1]; \ 1028*0Sstevel@tonic-gate t = p + cy; \ 1029*0Sstevel@tonic-gate r[R] = (uint32_t)t; \ 1030*0Sstevel@tonic-gate cy = t >> 32 1031*0Sstevel@tonic-gate 1032*0Sstevel@tonic-gate #define MUL_SET_VEC_ROUND_NOPREFETCH(R) \ 1033*0Sstevel@tonic-gate p = pf * d; \ 1034*0Sstevel@tonic-gate t = p + cy; \ 1035*0Sstevel@tonic-gate r[R] = (uint32_t)t; \ 1036*0Sstevel@tonic-gate cy = t >> 32 1037*0Sstevel@tonic-gate 1038*0Sstevel@tonic-gate #define MUL_ADD_VEC_ROUND_PREFETCH(R) \ 1039*0Sstevel@tonic-gate t = (uint64_t)r[R]; \ 1040*0Sstevel@tonic-gate p = pf * d; \ 1041*0Sstevel@tonic-gate pf = (uint64_t)a[R+1]; \ 1042*0Sstevel@tonic-gate t = p + t + cy; \ 1043*0Sstevel@tonic-gate r[R] = (uint32_t)t; \ 1044*0Sstevel@tonic-gate cy = t >> 32 1045*0Sstevel@tonic-gate 1046*0Sstevel@tonic-gate #define MUL_ADD_VEC_ROUND_NOPREFETCH(R) \ 1047*0Sstevel@tonic-gate t = (uint64_t)r[R]; \ 1048*0Sstevel@tonic-gate p = pf * d; \ 1049*0Sstevel@tonic-gate t = p + t + cy; \ 1050*0Sstevel@tonic-gate r[R] = (uint32_t)t; \ 1051*0Sstevel@tonic-gate cy = t >> 32 1052*0Sstevel@tonic-gate 1053*0Sstevel@tonic-gate #ifdef UNROLL8 1054*0Sstevel@tonic-gate 1055*0Sstevel@tonic-gate #define UNROLL 8 1056*0Sstevel@tonic-gate 1057*0Sstevel@tonic-gate /* 1058*0Sstevel@tonic-gate * r = a * b 1059*0Sstevel@tonic-gate * where r and a are vectors; b is a single 32-bit digit 1060*0Sstevel@tonic-gate */ 1061*0Sstevel@tonic-gate 1062*0Sstevel@tonic-gate uint32_t 1063*0Sstevel@tonic-gate big_mul_set_vec(uint32_t *r, uint32_t *a, int len, uint32_t b) 1064*0Sstevel@tonic-gate { 1065*0Sstevel@tonic-gate uint64_t d, pf, p, t, cy; 1066*0Sstevel@tonic-gate 1067*0Sstevel@tonic-gate if (len == 0) 1068*0Sstevel@tonic-gate return (0); 1069*0Sstevel@tonic-gate cy = 0; 1070*0Sstevel@tonic-gate d = (uint64_t)b; 1071*0Sstevel@tonic-gate pf = (uint64_t)a[0]; 1072*0Sstevel@tonic-gate while (len > UNROLL) { 1073*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(0); 1074*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(1); 1075*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(2); 1076*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(3); 1077*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(4); 1078*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(5); 1079*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(6); 1080*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(7); 1081*0Sstevel@tonic-gate r += UNROLL; 1082*0Sstevel@tonic-gate a += UNROLL; 1083*0Sstevel@tonic-gate len -= UNROLL; 1084*0Sstevel@tonic-gate } 1085*0Sstevel@tonic-gate if (len == UNROLL) { 1086*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(0); 1087*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(1); 1088*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(2); 1089*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(3); 1090*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(4); 1091*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(5); 1092*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(6); 1093*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_NOPREFETCH(7); 1094*0Sstevel@tonic-gate return ((uint32_t)cy); 1095*0Sstevel@tonic-gate } 1096*0Sstevel@tonic-gate while (len > 1) { 1097*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(0); 1098*0Sstevel@tonic-gate ++r; 1099*0Sstevel@tonic-gate ++a; 1100*0Sstevel@tonic-gate --len; 1101*0Sstevel@tonic-gate } 1102*0Sstevel@tonic-gate if (len > 0) { 1103*0Sstevel@tonic-gate MUL_SET_VEC_ROUND_NOPREFETCH(0); 1104*0Sstevel@tonic-gate } 1105*0Sstevel@tonic-gate return ((uint32_t)cy); 1106*0Sstevel@tonic-gate } 1107*0Sstevel@tonic-gate 1108*0Sstevel@tonic-gate /* 1109*0Sstevel@tonic-gate * r += a * b 1110*0Sstevel@tonic-gate * where r and a are vectors; b is a single 32-bit digit 1111*0Sstevel@tonic-gate */ 1112*0Sstevel@tonic-gate 1113*0Sstevel@tonic-gate uint32_t 1114*0Sstevel@tonic-gate big_mul_add_vec(uint32_t *r, uint32_t *a, int len, uint32_t b) 1115*0Sstevel@tonic-gate { 1116*0Sstevel@tonic-gate uint64_t d, pf, p, t, cy; 1117*0Sstevel@tonic-gate 1118*0Sstevel@tonic-gate if (len == 0) 1119*0Sstevel@tonic-gate return (0); 1120*0Sstevel@tonic-gate cy = 0; 1121*0Sstevel@tonic-gate d = (uint64_t)b; 1122*0Sstevel@tonic-gate pf = (uint64_t)a[0]; 1123*0Sstevel@tonic-gate while (len > 8) { 1124*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(0); 1125*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(1); 1126*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(2); 1127*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(3); 1128*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(4); 1129*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(5); 1130*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(6); 1131*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(7); 1132*0Sstevel@tonic-gate r += 8; 1133*0Sstevel@tonic-gate a += 8; 1134*0Sstevel@tonic-gate len -= 8; 1135*0Sstevel@tonic-gate } 1136*0Sstevel@tonic-gate if (len == 8) { 1137*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(0); 1138*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(1); 1139*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(2); 1140*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(3); 1141*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(4); 1142*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(5); 1143*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(6); 1144*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_NOPREFETCH(7); 1145*0Sstevel@tonic-gate return ((uint32_t)cy); 1146*0Sstevel@tonic-gate } 1147*0Sstevel@tonic-gate while (len > 1) { 1148*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(0); 1149*0Sstevel@tonic-gate ++r; 1150*0Sstevel@tonic-gate ++a; 1151*0Sstevel@tonic-gate --len; 1152*0Sstevel@tonic-gate } 1153*0Sstevel@tonic-gate if (len > 0) { 1154*0Sstevel@tonic-gate MUL_ADD_VEC_ROUND_NOPREFETCH(0); 1155*0Sstevel@tonic-gate } 1156*0Sstevel@tonic-gate return ((uint32_t)cy); 1157*0Sstevel@tonic-gate } 1158*0Sstevel@tonic-gate #endif /* UNROLL8 */ 1159*0Sstevel@tonic-gate 1160*0Sstevel@tonic-gate void 1161*0Sstevel@tonic-gate big_sqr_vec(uint32_t *r, uint32_t *a, int len) 1162*0Sstevel@tonic-gate { 1163*0Sstevel@tonic-gate uint32_t *tr, *ta; 1164*0Sstevel@tonic-gate int tlen, row, col; 1165*0Sstevel@tonic-gate uint64_t p, s, t, t2, cy; 1166*0Sstevel@tonic-gate uint32_t d; 1167*0Sstevel@tonic-gate 1168*0Sstevel@tonic-gate tr = r + 1; 1169*0Sstevel@tonic-gate ta = a; 1170*0Sstevel@tonic-gate tlen = len - 1; 1171*0Sstevel@tonic-gate tr[tlen] = big_mul_set_vec(tr, ta + 1, tlen, ta[0]); 1172*0Sstevel@tonic-gate while (--tlen > 0) { 1173*0Sstevel@tonic-gate tr += 2; 1174*0Sstevel@tonic-gate ++ta; 1175*0Sstevel@tonic-gate tr[tlen] = big_mul_add_vec(tr, ta + 1, tlen, ta[0]); 1176*0Sstevel@tonic-gate } 1177*0Sstevel@tonic-gate s = (uint64_t)a[0]; 1178*0Sstevel@tonic-gate s = s * s; 1179*0Sstevel@tonic-gate r[0] = (uint32_t)s; 1180*0Sstevel@tonic-gate cy = s >> 32; 1181*0Sstevel@tonic-gate p = ((uint64_t)r[1] << 1) + cy; 1182*0Sstevel@tonic-gate r[1] = (uint32_t)p; 1183*0Sstevel@tonic-gate cy = p >> 32; 1184*0Sstevel@tonic-gate row = 1; 1185*0Sstevel@tonic-gate col = 2; 1186*0Sstevel@tonic-gate while (row < len) { 1187*0Sstevel@tonic-gate s = (uint64_t)a[row]; 1188*0Sstevel@tonic-gate s = s * s; 1189*0Sstevel@tonic-gate p = (uint64_t)r[col] << 1; 1190*0Sstevel@tonic-gate t = p + s; 1191*0Sstevel@tonic-gate d = (uint32_t)t; 1192*0Sstevel@tonic-gate t2 = (uint64_t)d + cy; 1193*0Sstevel@tonic-gate r[col] = (uint32_t)t2; 1194*0Sstevel@tonic-gate cy = (t >> 32) + (t2 >> 32); 1195*0Sstevel@tonic-gate if (row == len - 1) 1196*0Sstevel@tonic-gate break; 1197*0Sstevel@tonic-gate p = ((uint64_t)r[col+1] << 1) + cy; 1198*0Sstevel@tonic-gate r[col+1] = (uint32_t)p; 1199*0Sstevel@tonic-gate cy = p >> 32; 1200*0Sstevel@tonic-gate ++row; 1201*0Sstevel@tonic-gate col += 2; 1202*0Sstevel@tonic-gate } 1203*0Sstevel@tonic-gate r[col+1] = (uint32_t)cy; 1204*0Sstevel@tonic-gate } 1205*0Sstevel@tonic-gate 1206*0Sstevel@tonic-gate #else /* ! UMUL64 */ 1207*0Sstevel@tonic-gate 1208*0Sstevel@tonic-gate /* 1209*0Sstevel@tonic-gate * r = r + a * digit, r and a are vectors of length len 1210*0Sstevel@tonic-gate * returns the carry digit 1211*0Sstevel@tonic-gate */ 1212*0Sstevel@tonic-gate uint32_t 1213*0Sstevel@tonic-gate big_mul_add_vec(uint32_t *r, uint32_t *a, int len, uint32_t digit) 1214*0Sstevel@tonic-gate { 1215*0Sstevel@tonic-gate uint32_t cy, cy1, retcy, dlow, dhigh; 1216*0Sstevel@tonic-gate int i; 1217*0Sstevel@tonic-gate 1218*0Sstevel@tonic-gate cy1 = 0; 1219*0Sstevel@tonic-gate dlow = digit & 0xffff; 1220*0Sstevel@tonic-gate dhigh = digit >> 16; 1221*0Sstevel@tonic-gate for (i = 0; i < len; i++) { 1222*0Sstevel@tonic-gate cy = (cy1 >> 16) + dlow * (a[i] & 0xffff) + (r[i] & 0xffff); 1223*0Sstevel@tonic-gate cy1 = (cy >> 16) + dlow * (a[i]>>16) + (r[i] >> 16); 1224*0Sstevel@tonic-gate r[i] = (cy & 0xffff) | (cy1 << 16); 1225*0Sstevel@tonic-gate } 1226*0Sstevel@tonic-gate retcy = cy1 >> 16; 1227*0Sstevel@tonic-gate 1228*0Sstevel@tonic-gate cy1 = r[0] & 0xffff; 1229*0Sstevel@tonic-gate for (i = 0; i < len - 1; i++) { 1230*0Sstevel@tonic-gate cy = (cy1 >> 16) + dhigh * (a[i] & 0xffff) + (r[i] >> 16); 1231*0Sstevel@tonic-gate r[i] = (cy1 & 0xffff) | (cy << 16); 1232*0Sstevel@tonic-gate cy1 = (cy >> 16) + dhigh * (a[i] >> 16) + (r[i + 1] & 0xffff); 1233*0Sstevel@tonic-gate } 1234*0Sstevel@tonic-gate cy = (cy1 >> 16) + dhigh * (a[len - 1] & 0xffff) + (r[len - 1] >> 16); 1235*0Sstevel@tonic-gate r[len - 1] = (cy1 & 0xffff) | (cy << 16); 1236*0Sstevel@tonic-gate retcy = (cy >> 16) + dhigh * (a[len - 1] >> 16) + retcy; 1237*0Sstevel@tonic-gate 1238*0Sstevel@tonic-gate return (retcy); 1239*0Sstevel@tonic-gate } 1240*0Sstevel@tonic-gate 1241*0Sstevel@tonic-gate /* 1242*0Sstevel@tonic-gate * r = a * digit, r and a are vectors of length len 1243*0Sstevel@tonic-gate * returns the carry digit 1244*0Sstevel@tonic-gate */ 1245*0Sstevel@tonic-gate uint32_t 1246*0Sstevel@tonic-gate big_mul_set_vec(uint32_t *r, uint32_t *a, int len, uint32_t digit) 1247*0Sstevel@tonic-gate { 1248*0Sstevel@tonic-gate return (big_mul_add_vec(r, a, len, digit)); 1249*0Sstevel@tonic-gate } 1250*0Sstevel@tonic-gate 1251*0Sstevel@tonic-gate void 1252*0Sstevel@tonic-gate big_sqr_vec(uint32_t *r, uint32_t *a, int len) 1253*0Sstevel@tonic-gate { 1254*0Sstevel@tonic-gate int i; 1255*0Sstevel@tonic-gate 1256*0Sstevel@tonic-gate r[len] = big_mul_set_vec(r, a, len, a[0]); 1257*0Sstevel@tonic-gate for (i = 1; i < len; ++i) 1258*0Sstevel@tonic-gate r[len + i] = big_mul_add_vec(r+i, a, len, a[i]); 1259*0Sstevel@tonic-gate } 1260*0Sstevel@tonic-gate 1261*0Sstevel@tonic-gate #endif /* UMUL64 */ 1262*0Sstevel@tonic-gate 1263*0Sstevel@tonic-gate void 1264*0Sstevel@tonic-gate big_mul_vec(uint32_t *r, uint32_t *a, int alen, uint32_t *b, int blen) 1265*0Sstevel@tonic-gate { 1266*0Sstevel@tonic-gate int i; 1267*0Sstevel@tonic-gate 1268*0Sstevel@tonic-gate r[alen] = big_mul_set_vec(r, a, alen, b[0]); 1269*0Sstevel@tonic-gate for (i = 1; i < blen; ++i) 1270*0Sstevel@tonic-gate r[alen + i] = big_mul_add_vec(r+i, a, alen, b[i]); 1271*0Sstevel@tonic-gate } 1272*0Sstevel@tonic-gate 1273*0Sstevel@tonic-gate 1274*0Sstevel@tonic-gate #endif /* ! PSR_MUL */ 1275*0Sstevel@tonic-gate 1276*0Sstevel@tonic-gate 1277*0Sstevel@tonic-gate /* 1278*0Sstevel@tonic-gate * result = aa * bb result->value should be big enough to hold the result 1279*0Sstevel@tonic-gate * 1280*0Sstevel@tonic-gate * Implementation: Standard grammar school algorithm 1281*0Sstevel@tonic-gate * 1282*0Sstevel@tonic-gate */ 1283*0Sstevel@tonic-gate 1284*0Sstevel@tonic-gate BIG_ERR_CODE 1285*0Sstevel@tonic-gate big_mul(BIGNUM *result, BIGNUM *aa, BIGNUM *bb) 1286*0Sstevel@tonic-gate { 1287*0Sstevel@tonic-gate BIGNUM tmp1; 1288*0Sstevel@tonic-gate uint32_t tmp1value[BIGTMPSIZE]; 1289*0Sstevel@tonic-gate uint32_t *r, *t, *a, *b; 1290*0Sstevel@tonic-gate BIG_ERR_CODE err; 1291*0Sstevel@tonic-gate int i, alen, blen, rsize, sign, diff; 1292*0Sstevel@tonic-gate 1293*0Sstevel@tonic-gate if (aa == bb) { 1294*0Sstevel@tonic-gate diff = 0; 1295*0Sstevel@tonic-gate } else { 1296*0Sstevel@tonic-gate diff = big_cmp_abs(aa, bb); 1297*0Sstevel@tonic-gate if (diff < 0) { 1298*0Sstevel@tonic-gate BIGNUM *tt; 1299*0Sstevel@tonic-gate tt = aa; 1300*0Sstevel@tonic-gate aa = bb; 1301*0Sstevel@tonic-gate bb = tt; 1302*0Sstevel@tonic-gate } 1303*0Sstevel@tonic-gate } 1304*0Sstevel@tonic-gate a = aa->value; 1305*0Sstevel@tonic-gate b = bb->value; 1306*0Sstevel@tonic-gate alen = aa->len; 1307*0Sstevel@tonic-gate blen = bb->len; 1308*0Sstevel@tonic-gate while ((alen > 1) && (a[alen - 1] == 0)) alen--; 1309*0Sstevel@tonic-gate aa->len = alen; 1310*0Sstevel@tonic-gate while ((blen > 1) && (b[blen - 1] == 0)) blen--; 1311*0Sstevel@tonic-gate bb->len = blen; 1312*0Sstevel@tonic-gate 1313*0Sstevel@tonic-gate rsize = alen + blen; 1314*0Sstevel@tonic-gate if (result->size < rsize) { 1315*0Sstevel@tonic-gate err = big_extend(result, rsize); 1316*0Sstevel@tonic-gate if (err != BIG_OK) 1317*0Sstevel@tonic-gate return (err); 1318*0Sstevel@tonic-gate /* aa or bb might be an alias to result */ 1319*0Sstevel@tonic-gate a = aa->value; 1320*0Sstevel@tonic-gate b = bb->value; 1321*0Sstevel@tonic-gate } 1322*0Sstevel@tonic-gate r = result->value; 1323*0Sstevel@tonic-gate 1324*0Sstevel@tonic-gate if (((alen == 1) && (a[0] == 0)) || ((blen == 1) && (b[0] == 0))) { 1325*0Sstevel@tonic-gate result->len = 1; 1326*0Sstevel@tonic-gate result->sign = 1; 1327*0Sstevel@tonic-gate r[0] = 0; 1328*0Sstevel@tonic-gate return (BIG_OK); 1329*0Sstevel@tonic-gate } 1330*0Sstevel@tonic-gate sign = aa->sign * bb->sign; 1331*0Sstevel@tonic-gate if ((alen == 1) && (a[0] == 1)) { 1332*0Sstevel@tonic-gate for (i = 0; i < blen; i++) r[i] = b[i]; 1333*0Sstevel@tonic-gate result->len = blen; 1334*0Sstevel@tonic-gate result->sign = sign; 1335*0Sstevel@tonic-gate return (BIG_OK); 1336*0Sstevel@tonic-gate } 1337*0Sstevel@tonic-gate if ((blen == 1) && (b[0] == 1)) { 1338*0Sstevel@tonic-gate for (i = 0; i < alen; i++) r[i] = a[i]; 1339*0Sstevel@tonic-gate result->len = alen; 1340*0Sstevel@tonic-gate result->sign = sign; 1341*0Sstevel@tonic-gate return (BIG_OK); 1342*0Sstevel@tonic-gate } 1343*0Sstevel@tonic-gate 1344*0Sstevel@tonic-gate err = big_init1(&tmp1, rsize, tmp1value, arraysize(tmp1value)); 1345*0Sstevel@tonic-gate if (err != BIG_OK) 1346*0Sstevel@tonic-gate return (err); 1347*0Sstevel@tonic-gate t = tmp1.value; 1348*0Sstevel@tonic-gate for (i = 0; i < rsize; i++) t[i] = 0; 1349*0Sstevel@tonic-gate 1350*0Sstevel@tonic-gate if (diff == 0 && alen > 2) 1351*0Sstevel@tonic-gate BIG_SQR_VEC(t, a, alen); 1352*0Sstevel@tonic-gate else if (blen > 0) 1353*0Sstevel@tonic-gate BIG_MUL_VEC(t, a, alen, b, blen); 1354*0Sstevel@tonic-gate if (t[rsize - 1] == 0) 1355*0Sstevel@tonic-gate --rsize; 1356*0Sstevel@tonic-gate tmp1.len = rsize; 1357*0Sstevel@tonic-gate if ((err = big_copy(result, &tmp1)) != BIG_OK) 1358*0Sstevel@tonic-gate return (err); 1359*0Sstevel@tonic-gate 1360*0Sstevel@tonic-gate result->sign = sign; 1361*0Sstevel@tonic-gate 1362*0Sstevel@tonic-gate if (tmp1.malloced) big_finish(&tmp1); 1363*0Sstevel@tonic-gate 1364*0Sstevel@tonic-gate return (BIG_OK); 1365*0Sstevel@tonic-gate } 1366*0Sstevel@tonic-gate 1367*0Sstevel@tonic-gate 1368*0Sstevel@tonic-gate /* 1369*0Sstevel@tonic-gate * caller must ensure that a < n, b < n and ret->size >= 2 * n->len + 1 1370*0Sstevel@tonic-gate * and that ret is not n 1371*0Sstevel@tonic-gate */ 1372*0Sstevel@tonic-gate BIG_ERR_CODE 1373*0Sstevel@tonic-gate big_mont_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, BIGNUM *n, uint32_t n0) 1374*0Sstevel@tonic-gate { 1375*0Sstevel@tonic-gate int i, j, nlen, needsubtract; 1376*0Sstevel@tonic-gate uint32_t *nn, *rr; 1377*0Sstevel@tonic-gate uint32_t digit, c; 1378*0Sstevel@tonic-gate BIG_ERR_CODE err; 1379*0Sstevel@tonic-gate 1380*0Sstevel@tonic-gate nlen = n->len; 1381*0Sstevel@tonic-gate nn = n->value; 1382*0Sstevel@tonic-gate 1383*0Sstevel@tonic-gate rr = ret->value; 1384*0Sstevel@tonic-gate 1385*0Sstevel@tonic-gate if ((err = big_mul(ret, a, b)) != BIG_OK) 1386*0Sstevel@tonic-gate return (err); 1387*0Sstevel@tonic-gate 1388*0Sstevel@tonic-gate rr = ret->value; 1389*0Sstevel@tonic-gate for (i = ret->len; i < 2 * nlen + 1; i++) rr[i] = 0; 1390*0Sstevel@tonic-gate for (i = 0; i < nlen; i++) { 1391*0Sstevel@tonic-gate digit = rr[i]; 1392*0Sstevel@tonic-gate digit = digit * n0; 1393*0Sstevel@tonic-gate 1394*0Sstevel@tonic-gate c = BIG_MUL_ADD_VEC(rr + i, nn, nlen, digit); 1395*0Sstevel@tonic-gate j = i + nlen; 1396*0Sstevel@tonic-gate rr[j] += c; 1397*0Sstevel@tonic-gate while (rr[j] < c) { 1398*0Sstevel@tonic-gate rr[j + 1] += 1; 1399*0Sstevel@tonic-gate j++; 1400*0Sstevel@tonic-gate c = 1; 1401*0Sstevel@tonic-gate } 1402*0Sstevel@tonic-gate } 1403*0Sstevel@tonic-gate 1404*0Sstevel@tonic-gate needsubtract = 0; 1405*0Sstevel@tonic-gate if ((rr[2 * nlen] != 0)) 1406*0Sstevel@tonic-gate needsubtract = 1; 1407*0Sstevel@tonic-gate else { 1408*0Sstevel@tonic-gate for (i = 2 * nlen - 1; i >= nlen; i--) { 1409*0Sstevel@tonic-gate if (rr[i] > nn[i - nlen]) { 1410*0Sstevel@tonic-gate needsubtract = 1; 1411*0Sstevel@tonic-gate break; 1412*0Sstevel@tonic-gate } else if (rr[i] < nn[i - nlen]) break; 1413*0Sstevel@tonic-gate } 1414*0Sstevel@tonic-gate } 1415*0Sstevel@tonic-gate if (needsubtract) 1416*0Sstevel@tonic-gate big_sub_vec(rr, rr + nlen, nn, nlen); 1417*0Sstevel@tonic-gate else { 1418*0Sstevel@tonic-gate for (i = 0; i < nlen; i++) 1419*0Sstevel@tonic-gate rr[i] = rr[i + nlen]; 1420*0Sstevel@tonic-gate } 1421*0Sstevel@tonic-gate for (i = nlen - 1; (i >= 0) && (rr[i] == 0); i--); 1422*0Sstevel@tonic-gate ret->len = i+1; 1423*0Sstevel@tonic-gate 1424*0Sstevel@tonic-gate return (BIG_OK); 1425*0Sstevel@tonic-gate } 1426*0Sstevel@tonic-gate 1427*0Sstevel@tonic-gate uint32_t 1428*0Sstevel@tonic-gate big_n0(uint32_t n) 1429*0Sstevel@tonic-gate { 1430*0Sstevel@tonic-gate int i; 1431*0Sstevel@tonic-gate uint32_t result, tmp; 1432*0Sstevel@tonic-gate 1433*0Sstevel@tonic-gate result = 0; 1434*0Sstevel@tonic-gate tmp = 0xffffffff; 1435*0Sstevel@tonic-gate for (i = 0; i < 32; i++) { 1436*0Sstevel@tonic-gate if ((tmp & 1) == 1) { 1437*0Sstevel@tonic-gate result = (result >> 1) | 0x80000000; 1438*0Sstevel@tonic-gate tmp = tmp - n; 1439*0Sstevel@tonic-gate } else result = (result>>1); 1440*0Sstevel@tonic-gate tmp = tmp >> 1; 1441*0Sstevel@tonic-gate } 1442*0Sstevel@tonic-gate 1443*0Sstevel@tonic-gate return (result); 1444*0Sstevel@tonic-gate } 1445*0Sstevel@tonic-gate 1446*0Sstevel@tonic-gate 1447*0Sstevel@tonic-gate int 1448*0Sstevel@tonic-gate big_numbits(BIGNUM *n) 1449*0Sstevel@tonic-gate { 1450*0Sstevel@tonic-gate int i, j; 1451*0Sstevel@tonic-gate uint32_t t; 1452*0Sstevel@tonic-gate 1453*0Sstevel@tonic-gate for (i = n->len - 1; i > 0; i--) 1454*0Sstevel@tonic-gate if (n->value[i] != 0) break; 1455*0Sstevel@tonic-gate t = n->value[i]; 1456*0Sstevel@tonic-gate for (j = 32; j > 0; j--) { 1457*0Sstevel@tonic-gate if ((t & 0x80000000) == 0) 1458*0Sstevel@tonic-gate t = t << 1; 1459*0Sstevel@tonic-gate else 1460*0Sstevel@tonic-gate return (32 * i + j); 1461*0Sstevel@tonic-gate } 1462*0Sstevel@tonic-gate return (0); 1463*0Sstevel@tonic-gate } 1464*0Sstevel@tonic-gate 1465*0Sstevel@tonic-gate /* caller must make sure that a < n */ 1466*0Sstevel@tonic-gate BIG_ERR_CODE 1467*0Sstevel@tonic-gate big_mont_rr(BIGNUM *result, BIGNUM *n) 1468*0Sstevel@tonic-gate { 1469*0Sstevel@tonic-gate BIGNUM rr; 1470*0Sstevel@tonic-gate uint32_t rrvalue[BIGTMPSIZE]; 1471*0Sstevel@tonic-gate int len, i; 1472*0Sstevel@tonic-gate BIG_ERR_CODE err; 1473*0Sstevel@tonic-gate 1474*0Sstevel@tonic-gate rr.malloced = 0; 1475*0Sstevel@tonic-gate len = n->len; 1476*0Sstevel@tonic-gate 1477*0Sstevel@tonic-gate if ((err = big_init1(&rr, 2 * len + 1, 1478*0Sstevel@tonic-gate rrvalue, arraysize(rrvalue))) != BIG_OK) 1479*0Sstevel@tonic-gate return (err); 1480*0Sstevel@tonic-gate 1481*0Sstevel@tonic-gate for (i = 0; i < 2 * len; i++) rr.value[i] = 0; 1482*0Sstevel@tonic-gate rr.value[2 * len] = 1; 1483*0Sstevel@tonic-gate rr.len = 2 * len + 1; 1484*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &rr, &rr, n)) != BIG_OK) 1485*0Sstevel@tonic-gate goto ret; 1486*0Sstevel@tonic-gate err = big_copy(result, &rr); 1487*0Sstevel@tonic-gate ret: 1488*0Sstevel@tonic-gate if (rr.malloced) big_finish(&rr); 1489*0Sstevel@tonic-gate return (err); 1490*0Sstevel@tonic-gate } 1491*0Sstevel@tonic-gate 1492*0Sstevel@tonic-gate /* caller must make sure that a < n */ 1493*0Sstevel@tonic-gate BIG_ERR_CODE 1494*0Sstevel@tonic-gate big_mont_conv(BIGNUM *result, BIGNUM *a, BIGNUM *n, uint32_t n0, BIGNUM *n_rr) 1495*0Sstevel@tonic-gate { 1496*0Sstevel@tonic-gate BIGNUM rr; 1497*0Sstevel@tonic-gate uint32_t rrvalue[BIGTMPSIZE]; 1498*0Sstevel@tonic-gate int len, i; 1499*0Sstevel@tonic-gate BIG_ERR_CODE err; 1500*0Sstevel@tonic-gate 1501*0Sstevel@tonic-gate rr.malloced = 0; 1502*0Sstevel@tonic-gate len = n->len; 1503*0Sstevel@tonic-gate 1504*0Sstevel@tonic-gate if ((err = big_init1(&rr, 2 * len + 1, rrvalue, arraysize(rrvalue))) 1505*0Sstevel@tonic-gate != BIG_OK) 1506*0Sstevel@tonic-gate return (err); 1507*0Sstevel@tonic-gate 1508*0Sstevel@tonic-gate if (n_rr == NULL) { 1509*0Sstevel@tonic-gate for (i = 0; i < 2 * len; i++) rr.value[i] = 0; 1510*0Sstevel@tonic-gate rr.value[2 * len] = 1; 1511*0Sstevel@tonic-gate rr.len = 2 * len + 1; 1512*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &rr, &rr, n)) != BIG_OK) 1513*0Sstevel@tonic-gate goto ret; 1514*0Sstevel@tonic-gate n_rr = &rr; 1515*0Sstevel@tonic-gate } 1516*0Sstevel@tonic-gate 1517*0Sstevel@tonic-gate if ((err = big_mont_mul(&rr, n_rr, a, n, n0)) != BIG_OK) 1518*0Sstevel@tonic-gate goto ret; 1519*0Sstevel@tonic-gate err = big_copy(result, &rr); 1520*0Sstevel@tonic-gate ret: 1521*0Sstevel@tonic-gate if (rr.malloced) big_finish(&rr); 1522*0Sstevel@tonic-gate return (err); 1523*0Sstevel@tonic-gate } 1524*0Sstevel@tonic-gate 1525*0Sstevel@tonic-gate 1526*0Sstevel@tonic-gate #define MAX_EXP_BIT_GROUP_SIZE 6 1527*0Sstevel@tonic-gate #define APOWERS_MAX_SIZE (1 << (MAX_EXP_BIT_GROUP_SIZE - 1)) 1528*0Sstevel@tonic-gate 1529*0Sstevel@tonic-gate #ifdef USE_FLOATING_POINT 1530*0Sstevel@tonic-gate 1531*0Sstevel@tonic-gate /* 1532*0Sstevel@tonic-gate * This version makes use of floating point for performance. 1533*0Sstevel@tonic-gate */ 1534*0Sstevel@tonic-gate static BIG_ERR_CODE 1535*0Sstevel@tonic-gate _big_modexp(BIGNUM *result, BIGNUM *a, BIGNUM *e, BIGNUM *n, BIGNUM *n_rr) 1536*0Sstevel@tonic-gate { 1537*0Sstevel@tonic-gate BIGNUM ma, tmp, rr; 1538*0Sstevel@tonic-gate uint32_t mavalue[BIGTMPSIZE]; 1539*0Sstevel@tonic-gate uint32_t tmpvalue[BIGTMPSIZE]; 1540*0Sstevel@tonic-gate uint32_t rrvalue[BIGTMPSIZE]; 1541*0Sstevel@tonic-gate int i, j, k, l, m, p, bit, bitind, bitcount, nlen; 1542*0Sstevel@tonic-gate BIG_ERR_CODE err; 1543*0Sstevel@tonic-gate uint32_t n0; 1544*0Sstevel@tonic-gate double dn0; 1545*0Sstevel@tonic-gate double *dn, *dt, *d16r, *d32r; 1546*0Sstevel@tonic-gate uint32_t *nint, *prod; 1547*0Sstevel@tonic-gate double *apowers[APOWERS_MAX_SIZE]; 1548*0Sstevel@tonic-gate int nbits, groupbits, apowerssize; 1549*0Sstevel@tonic-gate 1550*0Sstevel@tonic-gate nbits = big_numbits(e); 1551*0Sstevel@tonic-gate if (nbits < 50) { 1552*0Sstevel@tonic-gate groupbits = 1; 1553*0Sstevel@tonic-gate apowerssize = 1; 1554*0Sstevel@tonic-gate } else { 1555*0Sstevel@tonic-gate groupbits = MAX_EXP_BIT_GROUP_SIZE; 1556*0Sstevel@tonic-gate apowerssize = 1 << (groupbits - 1); 1557*0Sstevel@tonic-gate } 1558*0Sstevel@tonic-gate 1559*0Sstevel@tonic-gate if ((err = big_init1(&ma, n->len, mavalue, arraysize(mavalue))) != 1560*0Sstevel@tonic-gate BIG_OK) 1561*0Sstevel@tonic-gate return (err); 1562*0Sstevel@tonic-gate ma.len = 1; 1563*0Sstevel@tonic-gate ma.value[0] = 0; 1564*0Sstevel@tonic-gate 1565*0Sstevel@tonic-gate if ((err = big_init1(&tmp, 2 * n->len + 1, 1566*0Sstevel@tonic-gate tmpvalue, arraysize(tmpvalue))) != BIG_OK) 1567*0Sstevel@tonic-gate goto ret1; 1568*0Sstevel@tonic-gate tmp.len = 1; 1569*0Sstevel@tonic-gate tmp.value[0] = 0; 1570*0Sstevel@tonic-gate 1571*0Sstevel@tonic-gate rr.malloced = 0; 1572*0Sstevel@tonic-gate if (n_rr == NULL) { 1573*0Sstevel@tonic-gate if ((err = big_init1(&rr, 2 * n->len + 1, 1574*0Sstevel@tonic-gate rrvalue, arraysize(rrvalue))) != BIG_OK) 1575*0Sstevel@tonic-gate goto ret2; 1576*0Sstevel@tonic-gate if (big_mont_rr(&rr, n) != BIG_OK) 1577*0Sstevel@tonic-gate goto ret2; 1578*0Sstevel@tonic-gate n_rr = &rr; 1579*0Sstevel@tonic-gate } 1580*0Sstevel@tonic-gate 1581*0Sstevel@tonic-gate n0 = big_n0(n->value[0]); 1582*0Sstevel@tonic-gate 1583*0Sstevel@tonic-gate if (big_cmp_abs(a, n) > 0) { 1584*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &ma, a, n)) != BIG_OK) 1585*0Sstevel@tonic-gate goto ret2; 1586*0Sstevel@tonic-gate err = big_mont_conv(&ma, &ma, n, n0, n_rr); 1587*0Sstevel@tonic-gate } else { 1588*0Sstevel@tonic-gate err = big_mont_conv(&ma, a, n, n0, n_rr); 1589*0Sstevel@tonic-gate } 1590*0Sstevel@tonic-gate if (err != BIG_OK) 1591*0Sstevel@tonic-gate goto ret3; 1592*0Sstevel@tonic-gate 1593*0Sstevel@tonic-gate tmp.len = 1; 1594*0Sstevel@tonic-gate tmp.value[0] = 1; 1595*0Sstevel@tonic-gate if ((err = big_mont_conv(&tmp, &tmp, n, n0, n_rr)) != BIG_OK) 1596*0Sstevel@tonic-gate goto ret3; 1597*0Sstevel@tonic-gate 1598*0Sstevel@tonic-gate nlen = n->len; 1599*0Sstevel@tonic-gate dn0 = (double)(n0 & 0xffff); 1600*0Sstevel@tonic-gate 1601*0Sstevel@tonic-gate dn = dt = d16r = d32r = NULL; 1602*0Sstevel@tonic-gate nint = prod = NULL; 1603*0Sstevel@tonic-gate for (i = 0; i < apowerssize; i++) { 1604*0Sstevel@tonic-gate apowers[i] = NULL; 1605*0Sstevel@tonic-gate } 1606*0Sstevel@tonic-gate 1607*0Sstevel@tonic-gate if ((dn = big_malloc(nlen * sizeof (double))) == NULL) { 1608*0Sstevel@tonic-gate err = BIG_NO_MEM; 1609*0Sstevel@tonic-gate goto ret; 1610*0Sstevel@tonic-gate } 1611*0Sstevel@tonic-gate if ((dt = big_malloc((4 * nlen + 2) * sizeof (double))) == NULL) { 1612*0Sstevel@tonic-gate err = BIG_NO_MEM; 1613*0Sstevel@tonic-gate goto ret; 1614*0Sstevel@tonic-gate } 1615*0Sstevel@tonic-gate if ((nint = big_malloc(nlen * sizeof (uint32_t))) == NULL) { 1616*0Sstevel@tonic-gate err = BIG_NO_MEM; 1617*0Sstevel@tonic-gate goto ret; 1618*0Sstevel@tonic-gate } 1619*0Sstevel@tonic-gate if ((prod = big_malloc((nlen + 1) * sizeof (uint32_t))) == NULL) { 1620*0Sstevel@tonic-gate err = BIG_NO_MEM; 1621*0Sstevel@tonic-gate goto ret; 1622*0Sstevel@tonic-gate } 1623*0Sstevel@tonic-gate if ((d16r = big_malloc((2 * nlen + 1) * sizeof (double))) == NULL) { 1624*0Sstevel@tonic-gate err = BIG_NO_MEM; 1625*0Sstevel@tonic-gate goto ret; 1626*0Sstevel@tonic-gate } 1627*0Sstevel@tonic-gate if ((d32r = big_malloc(nlen * sizeof (double))) == NULL) { 1628*0Sstevel@tonic-gate err = BIG_NO_MEM; 1629*0Sstevel@tonic-gate goto ret; 1630*0Sstevel@tonic-gate } 1631*0Sstevel@tonic-gate for (i = 0; i < apowerssize; i++) { 1632*0Sstevel@tonic-gate if ((apowers[i] = big_malloc((2 * nlen + 1) * 1633*0Sstevel@tonic-gate sizeof (double))) == NULL) { 1634*0Sstevel@tonic-gate err = BIG_NO_MEM; 1635*0Sstevel@tonic-gate goto ret; 1636*0Sstevel@tonic-gate } 1637*0Sstevel@tonic-gate } 1638*0Sstevel@tonic-gate 1639*0Sstevel@tonic-gate for (i = 0; i < ma.len; i++) nint[i] = ma.value[i]; 1640*0Sstevel@tonic-gate for (; i < nlen; i++) nint[i] = 0; 1641*0Sstevel@tonic-gate conv_i32_to_d32_and_d16(d32r, apowers[0], nint, nlen); 1642*0Sstevel@tonic-gate 1643*0Sstevel@tonic-gate for (i = 0; i < n->len; i++) nint[i] = n->value[i]; 1644*0Sstevel@tonic-gate for (; i < nlen; i++) nint[i] = 0; 1645*0Sstevel@tonic-gate conv_i32_to_d32(dn, nint, nlen); 1646*0Sstevel@tonic-gate 1647*0Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, apowers[0], dt, dn, nint, nlen, dn0); 1648*0Sstevel@tonic-gate conv_i32_to_d32(d32r, prod, nlen); 1649*0Sstevel@tonic-gate for (i = 1; i < apowerssize; i++) { 1650*0Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, apowers[i - 1], 1651*0Sstevel@tonic-gate dt, dn, nint, nlen, dn0); 1652*0Sstevel@tonic-gate conv_i32_to_d16(apowers[i], prod, nlen); 1653*0Sstevel@tonic-gate } 1654*0Sstevel@tonic-gate 1655*0Sstevel@tonic-gate for (i = 0; i < tmp.len; i++) prod[i] = tmp.value[i]; 1656*0Sstevel@tonic-gate for (; i < nlen + 1; i++) prod[i] = 0; 1657*0Sstevel@tonic-gate 1658*0Sstevel@tonic-gate bitind = nbits % 32; 1659*0Sstevel@tonic-gate k = 0; 1660*0Sstevel@tonic-gate l = 0; 1661*0Sstevel@tonic-gate p = 0; 1662*0Sstevel@tonic-gate bitcount = 0; 1663*0Sstevel@tonic-gate for (i = nbits / 32; i >= 0; i--) { 1664*0Sstevel@tonic-gate for (j = bitind - 1; j >= 0; j--) { 1665*0Sstevel@tonic-gate bit = (e->value[i] >> j) & 1; 1666*0Sstevel@tonic-gate if ((bitcount == 0) && (bit == 0)) { 1667*0Sstevel@tonic-gate conv_i32_to_d32_and_d16(d32r, d16r, 1668*0Sstevel@tonic-gate prod, nlen); 1669*0Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, d16r, 1670*0Sstevel@tonic-gate dt, dn, nint, nlen, dn0); 1671*0Sstevel@tonic-gate } else { 1672*0Sstevel@tonic-gate bitcount++; 1673*0Sstevel@tonic-gate p = p * 2 + bit; 1674*0Sstevel@tonic-gate if (bit == 1) { 1675*0Sstevel@tonic-gate k = k + l + 1; 1676*0Sstevel@tonic-gate l = 0; 1677*0Sstevel@tonic-gate } else { 1678*0Sstevel@tonic-gate l++; 1679*0Sstevel@tonic-gate } 1680*0Sstevel@tonic-gate if (bitcount == groupbits) { 1681*0Sstevel@tonic-gate for (m = 0; m < k; m++) { 1682*0Sstevel@tonic-gate conv_i32_to_d32_and_d16( 1683*0Sstevel@tonic-gate d32r, d16r, 1684*0Sstevel@tonic-gate prod, nlen); 1685*0Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, 1686*0Sstevel@tonic-gate d16r, dt, dn, nint, 1687*0Sstevel@tonic-gate nlen, dn0); 1688*0Sstevel@tonic-gate } 1689*0Sstevel@tonic-gate conv_i32_to_d32(d32r, prod, nlen); 1690*0Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, 1691*0Sstevel@tonic-gate apowers[p >> (l+1)], 1692*0Sstevel@tonic-gate dt, dn, nint, nlen, dn0); 1693*0Sstevel@tonic-gate for (m = 0; m < l; m++) { 1694*0Sstevel@tonic-gate conv_i32_to_d32_and_d16( 1695*0Sstevel@tonic-gate d32r, d16r, 1696*0Sstevel@tonic-gate prod, nlen); 1697*0Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, 1698*0Sstevel@tonic-gate d16r, dt, dn, nint, 1699*0Sstevel@tonic-gate nlen, dn0); 1700*0Sstevel@tonic-gate } 1701*0Sstevel@tonic-gate k = 0; 1702*0Sstevel@tonic-gate l = 0; 1703*0Sstevel@tonic-gate p = 0; 1704*0Sstevel@tonic-gate bitcount = 0; 1705*0Sstevel@tonic-gate } 1706*0Sstevel@tonic-gate } 1707*0Sstevel@tonic-gate } 1708*0Sstevel@tonic-gate bitind = 32; 1709*0Sstevel@tonic-gate } 1710*0Sstevel@tonic-gate 1711*0Sstevel@tonic-gate for (m = 0; m < k; m++) { 1712*0Sstevel@tonic-gate conv_i32_to_d32_and_d16(d32r, d16r, prod, nlen); 1713*0Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, d16r, dt, dn, nint, nlen, dn0); 1714*0Sstevel@tonic-gate } 1715*0Sstevel@tonic-gate if (p != 0) { 1716*0Sstevel@tonic-gate conv_i32_to_d32(d32r, prod, nlen); 1717*0Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, apowers[p >> (l + 1)], 1718*0Sstevel@tonic-gate dt, dn, nint, nlen, dn0); 1719*0Sstevel@tonic-gate } 1720*0Sstevel@tonic-gate for (m = 0; m < l; m++) { 1721*0Sstevel@tonic-gate conv_i32_to_d32_and_d16(d32r, d16r, prod, nlen); 1722*0Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, d16r, dt, dn, nint, nlen, dn0); 1723*0Sstevel@tonic-gate } 1724*0Sstevel@tonic-gate 1725*0Sstevel@tonic-gate ma.value[0] = 1; 1726*0Sstevel@tonic-gate ma.len = 1; 1727*0Sstevel@tonic-gate for (i = 0; i < nlen; i++) tmp.value[i] = prod[i]; 1728*0Sstevel@tonic-gate for (i = nlen - 1; (i > 0) && (prod[i] == 0); i--); 1729*0Sstevel@tonic-gate tmp.len = i + 1; 1730*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, &tmp, &ma, n, n0)) != BIG_OK) 1731*0Sstevel@tonic-gate goto ret; 1732*0Sstevel@tonic-gate err = big_copy(result, &tmp); 1733*0Sstevel@tonic-gate ret: 1734*0Sstevel@tonic-gate for (i = apowerssize - 1; i >= 0; i--) { 1735*0Sstevel@tonic-gate if (apowers[i] != NULL) 1736*0Sstevel@tonic-gate big_free(apowers[i], (2 * nlen + 1) * sizeof (double)); 1737*0Sstevel@tonic-gate } 1738*0Sstevel@tonic-gate if (d32r != NULL) 1739*0Sstevel@tonic-gate big_free(d32r, nlen * sizeof (double)); 1740*0Sstevel@tonic-gate if (d16r != NULL) 1741*0Sstevel@tonic-gate big_free(d16r, (2 * nlen + 1) * sizeof (double)); 1742*0Sstevel@tonic-gate if (prod != NULL) 1743*0Sstevel@tonic-gate big_free(prod, (nlen + 1) * sizeof (uint32_t)); 1744*0Sstevel@tonic-gate if (nint != NULL) 1745*0Sstevel@tonic-gate big_free(nint, nlen * sizeof (uint32_t)); 1746*0Sstevel@tonic-gate if (dt != NULL) 1747*0Sstevel@tonic-gate big_free(dt, (4 * nlen + 2) * sizeof (double)); 1748*0Sstevel@tonic-gate if (dn != NULL) 1749*0Sstevel@tonic-gate big_free(dn, nlen * sizeof (double)); 1750*0Sstevel@tonic-gate 1751*0Sstevel@tonic-gate ret3: 1752*0Sstevel@tonic-gate big_finish(&rr); 1753*0Sstevel@tonic-gate ret2: 1754*0Sstevel@tonic-gate big_finish(&tmp); 1755*0Sstevel@tonic-gate ret1: 1756*0Sstevel@tonic-gate big_finish(&ma); 1757*0Sstevel@tonic-gate return (err); 1758*0Sstevel@tonic-gate 1759*0Sstevel@tonic-gate } 1760*0Sstevel@tonic-gate 1761*0Sstevel@tonic-gate #ifdef _KERNEL 1762*0Sstevel@tonic-gate 1763*0Sstevel@tonic-gate #include <sys/sysmacros.h> 1764*0Sstevel@tonic-gate #include <sys/regset.h> 1765*0Sstevel@tonic-gate #include <sys/fpu/fpusystm.h> 1766*0Sstevel@tonic-gate 1767*0Sstevel@tonic-gate /* the alignment for block stores to save fp registers */ 1768*0Sstevel@tonic-gate #define FPR_ALIGN (64) 1769*0Sstevel@tonic-gate 1770*0Sstevel@tonic-gate extern void big_savefp(kfpu_t *); 1771*0Sstevel@tonic-gate extern void big_restorefp(kfpu_t *); 1772*0Sstevel@tonic-gate 1773*0Sstevel@tonic-gate #endif /* _KERNEL */ 1774*0Sstevel@tonic-gate 1775*0Sstevel@tonic-gate BIG_ERR_CODE 1776*0Sstevel@tonic-gate big_modexp(BIGNUM *result, BIGNUM *a, BIGNUM *e, BIGNUM *n, BIGNUM *n_rr) 1777*0Sstevel@tonic-gate { 1778*0Sstevel@tonic-gate #ifdef _KERNEL 1779*0Sstevel@tonic-gate BIG_ERR_CODE rv; 1780*0Sstevel@tonic-gate uint8_t fpua[sizeof (kfpu_t) + FPR_ALIGN]; 1781*0Sstevel@tonic-gate kfpu_t *fpu; 1782*0Sstevel@tonic-gate 1783*0Sstevel@tonic-gate #ifdef DEBUG 1784*0Sstevel@tonic-gate if (!fpu_exists) 1785*0Sstevel@tonic-gate return (BIG_GENERAL_ERR); 1786*0Sstevel@tonic-gate #endif 1787*0Sstevel@tonic-gate 1788*0Sstevel@tonic-gate fpu = (kfpu_t *)P2ROUNDUP((uintptr_t)fpua, FPR_ALIGN); 1789*0Sstevel@tonic-gate big_savefp(fpu); 1790*0Sstevel@tonic-gate 1791*0Sstevel@tonic-gate rv = _big_modexp(result, a, e, n, n_rr); 1792*0Sstevel@tonic-gate 1793*0Sstevel@tonic-gate big_restorefp(fpu); 1794*0Sstevel@tonic-gate 1795*0Sstevel@tonic-gate return (rv); 1796*0Sstevel@tonic-gate #else 1797*0Sstevel@tonic-gate return (_big_modexp(result, a, e, n, n_rr)); 1798*0Sstevel@tonic-gate #endif /* _KERNEL */ 1799*0Sstevel@tonic-gate } 1800*0Sstevel@tonic-gate 1801*0Sstevel@tonic-gate #else /* ! USE_FLOATING_POINT */ 1802*0Sstevel@tonic-gate 1803*0Sstevel@tonic-gate /* 1804*0Sstevel@tonic-gate * This version uses strictly integer math and is safe in the kernel 1805*0Sstevel@tonic-gate * for all platforms. 1806*0Sstevel@tonic-gate */ 1807*0Sstevel@tonic-gate 1808*0Sstevel@tonic-gate /* 1809*0Sstevel@tonic-gate * computes a^e mod n 1810*0Sstevel@tonic-gate * assumes a < n, n odd, result->value at least as long as n->value 1811*0Sstevel@tonic-gate */ 1812*0Sstevel@tonic-gate BIG_ERR_CODE 1813*0Sstevel@tonic-gate big_modexp(BIGNUM *result, BIGNUM *a, BIGNUM *e, BIGNUM *n, BIGNUM *n_rr) 1814*0Sstevel@tonic-gate { 1815*0Sstevel@tonic-gate BIGNUM ma, tmp, rr; 1816*0Sstevel@tonic-gate uint32_t mavalue[BIGTMPSIZE]; 1817*0Sstevel@tonic-gate uint32_t tmpvalue[BIGTMPSIZE]; 1818*0Sstevel@tonic-gate uint32_t rrvalue[BIGTMPSIZE]; 1819*0Sstevel@tonic-gate BIGNUM apowers[APOWERS_MAX_SIZE]; 1820*0Sstevel@tonic-gate int i, j, k, l, m, p, 1821*0Sstevel@tonic-gate bit, bitind, bitcount, groupbits, apowerssize; 1822*0Sstevel@tonic-gate BIG_ERR_CODE err; 1823*0Sstevel@tonic-gate uint32_t n0; 1824*0Sstevel@tonic-gate 1825*0Sstevel@tonic-gate int nbits; 1826*0Sstevel@tonic-gate 1827*0Sstevel@tonic-gate nbits = big_numbits(e); 1828*0Sstevel@tonic-gate if (nbits < 50) { 1829*0Sstevel@tonic-gate groupbits = 1; 1830*0Sstevel@tonic-gate apowerssize = 1; 1831*0Sstevel@tonic-gate } else { 1832*0Sstevel@tonic-gate groupbits = MAX_EXP_BIT_GROUP_SIZE; 1833*0Sstevel@tonic-gate apowerssize = 1 << (groupbits - 1); 1834*0Sstevel@tonic-gate } 1835*0Sstevel@tonic-gate 1836*0Sstevel@tonic-gate if ((err = big_init1(&ma, n->len, 1837*0Sstevel@tonic-gate mavalue, arraysize(mavalue))) != BIG_OK) 1838*0Sstevel@tonic-gate return (err); 1839*0Sstevel@tonic-gate ma.len = 1; 1840*0Sstevel@tonic-gate ma.value[0] = 0; 1841*0Sstevel@tonic-gate 1842*0Sstevel@tonic-gate if ((err = big_init1(&tmp, 2 * n->len + 1, 1843*0Sstevel@tonic-gate tmpvalue, arraysize(tmpvalue))) != BIG_OK) 1844*0Sstevel@tonic-gate goto ret1; 1845*0Sstevel@tonic-gate tmp.len = 1; 1846*0Sstevel@tonic-gate tmp.value[0] = 1; 1847*0Sstevel@tonic-gate 1848*0Sstevel@tonic-gate n0 = big_n0(n->value[0]); 1849*0Sstevel@tonic-gate 1850*0Sstevel@tonic-gate rr.malloced = 0; 1851*0Sstevel@tonic-gate if (n_rr == NULL) { 1852*0Sstevel@tonic-gate if ((err = big_init1(&rr, 2 * n->len + 1, 1853*0Sstevel@tonic-gate rrvalue, arraysize(rrvalue))) != BIG_OK) 1854*0Sstevel@tonic-gate goto ret2; 1855*0Sstevel@tonic-gate 1856*0Sstevel@tonic-gate if (big_mont_rr(&rr, n) != BIG_OK) 1857*0Sstevel@tonic-gate goto ret3; 1858*0Sstevel@tonic-gate n_rr = &rr; 1859*0Sstevel@tonic-gate } 1860*0Sstevel@tonic-gate 1861*0Sstevel@tonic-gate for (i = 0; i < apowerssize; i++) apowers[i].malloced = 0; 1862*0Sstevel@tonic-gate for (i = 0; i < apowerssize; i++) { 1863*0Sstevel@tonic-gate if ((err = big_init1(&(apowers[i]), n->len, NULL, 0)) != 1864*0Sstevel@tonic-gate BIG_OK) 1865*0Sstevel@tonic-gate goto ret; 1866*0Sstevel@tonic-gate } 1867*0Sstevel@tonic-gate 1868*0Sstevel@tonic-gate if (big_cmp_abs(a, n) > 0) { 1869*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &ma, a, n)) != BIG_OK) 1870*0Sstevel@tonic-gate goto ret; 1871*0Sstevel@tonic-gate err = big_mont_conv(&ma, &ma, n, n0, n_rr); 1872*0Sstevel@tonic-gate } else { 1873*0Sstevel@tonic-gate err = big_mont_conv(&ma, a, n, n0, n_rr); 1874*0Sstevel@tonic-gate } 1875*0Sstevel@tonic-gate if (err != BIG_OK) goto ret; 1876*0Sstevel@tonic-gate 1877*0Sstevel@tonic-gate (void) big_copy(&(apowers[0]), &ma); 1878*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, &ma, &ma, n, n0)) != BIG_OK) 1879*0Sstevel@tonic-gate goto ret; 1880*0Sstevel@tonic-gate (void) big_copy(&ma, &tmp); 1881*0Sstevel@tonic-gate 1882*0Sstevel@tonic-gate for (i = 1; i < apowerssize; i++) { 1883*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, &ma, 1884*0Sstevel@tonic-gate &(apowers[i-1]), n, n0)) != BIG_OK) 1885*0Sstevel@tonic-gate goto ret; 1886*0Sstevel@tonic-gate (void) big_copy(&apowers[i], &tmp); 1887*0Sstevel@tonic-gate } 1888*0Sstevel@tonic-gate 1889*0Sstevel@tonic-gate tmp.len = 1; 1890*0Sstevel@tonic-gate tmp.value[0] = 1; 1891*0Sstevel@tonic-gate if ((err = big_mont_conv(&tmp, &tmp, n, n0, n_rr)) != BIG_OK) 1892*0Sstevel@tonic-gate goto ret; 1893*0Sstevel@tonic-gate 1894*0Sstevel@tonic-gate bitind = nbits % 32; 1895*0Sstevel@tonic-gate k = 0; 1896*0Sstevel@tonic-gate l = 0; 1897*0Sstevel@tonic-gate p = 0; 1898*0Sstevel@tonic-gate bitcount = 0; 1899*0Sstevel@tonic-gate for (i = nbits / 32; i >= 0; i--) { 1900*0Sstevel@tonic-gate for (j = bitind - 1; j >= 0; j--) { 1901*0Sstevel@tonic-gate bit = (e->value[i] >> j) & 1; 1902*0Sstevel@tonic-gate if ((bitcount == 0) && (bit == 0)) { 1903*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, 1904*0Sstevel@tonic-gate &tmp, &tmp, n, n0)) != BIG_OK) 1905*0Sstevel@tonic-gate goto ret; 1906*0Sstevel@tonic-gate } else { 1907*0Sstevel@tonic-gate bitcount++; 1908*0Sstevel@tonic-gate p = p * 2 + bit; 1909*0Sstevel@tonic-gate if (bit == 1) { 1910*0Sstevel@tonic-gate k = k + l + 1; 1911*0Sstevel@tonic-gate l = 0; 1912*0Sstevel@tonic-gate } else { 1913*0Sstevel@tonic-gate l++; 1914*0Sstevel@tonic-gate } 1915*0Sstevel@tonic-gate if (bitcount == groupbits) { 1916*0Sstevel@tonic-gate for (m = 0; m < k; m++) { 1917*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, 1918*0Sstevel@tonic-gate &tmp, &tmp, n, n0)) != 1919*0Sstevel@tonic-gate BIG_OK) 1920*0Sstevel@tonic-gate goto ret; 1921*0Sstevel@tonic-gate } 1922*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, &tmp, 1923*0Sstevel@tonic-gate &(apowers[p >> (l + 1)]), 1924*0Sstevel@tonic-gate n, n0)) != BIG_OK) 1925*0Sstevel@tonic-gate goto ret; 1926*0Sstevel@tonic-gate for (m = 0; m < l; m++) { 1927*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, 1928*0Sstevel@tonic-gate &tmp, &tmp, n, n0)) != 1929*0Sstevel@tonic-gate BIG_OK) 1930*0Sstevel@tonic-gate goto ret; 1931*0Sstevel@tonic-gate } 1932*0Sstevel@tonic-gate k = 0; 1933*0Sstevel@tonic-gate l = 0; 1934*0Sstevel@tonic-gate p = 0; 1935*0Sstevel@tonic-gate bitcount = 0; 1936*0Sstevel@tonic-gate } 1937*0Sstevel@tonic-gate } 1938*0Sstevel@tonic-gate } 1939*0Sstevel@tonic-gate bitind = 32; 1940*0Sstevel@tonic-gate } 1941*0Sstevel@tonic-gate 1942*0Sstevel@tonic-gate for (m = 0; m < k; m++) { 1943*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, &tmp, &tmp, n, n0)) != BIG_OK) 1944*0Sstevel@tonic-gate goto ret; 1945*0Sstevel@tonic-gate } 1946*0Sstevel@tonic-gate if (p != 0) { 1947*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, &tmp, 1948*0Sstevel@tonic-gate &(apowers[p >> (l + 1)]), n, n0)) != BIG_OK) 1949*0Sstevel@tonic-gate goto ret; 1950*0Sstevel@tonic-gate } 1951*0Sstevel@tonic-gate for (m = 0; m < l; m++) { 1952*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, &tmp, &tmp, n, n0)) != BIG_OK) 1953*0Sstevel@tonic-gate goto ret; 1954*0Sstevel@tonic-gate } 1955*0Sstevel@tonic-gate 1956*0Sstevel@tonic-gate ma.value[0] = 1; 1957*0Sstevel@tonic-gate ma.len = 1; 1958*0Sstevel@tonic-gate if ((err = big_mont_mul(&tmp, &tmp, &ma, n, n0)) != BIG_OK) 1959*0Sstevel@tonic-gate goto ret; 1960*0Sstevel@tonic-gate err = big_copy(result, &tmp); 1961*0Sstevel@tonic-gate ret: 1962*0Sstevel@tonic-gate for (i = apowerssize - 1; i >= 0; i--) { 1963*0Sstevel@tonic-gate big_finish(&(apowers[i])); 1964*0Sstevel@tonic-gate } 1965*0Sstevel@tonic-gate ret3: 1966*0Sstevel@tonic-gate if (rr.malloced) big_finish(&rr); 1967*0Sstevel@tonic-gate ret2: 1968*0Sstevel@tonic-gate if (tmp.malloced) big_finish(&tmp); 1969*0Sstevel@tonic-gate ret1: 1970*0Sstevel@tonic-gate if (ma.malloced) big_finish(&ma); 1971*0Sstevel@tonic-gate return (err); 1972*0Sstevel@tonic-gate } 1973*0Sstevel@tonic-gate 1974*0Sstevel@tonic-gate #endif /* USE_FLOATING_POINT */ 1975*0Sstevel@tonic-gate 1976*0Sstevel@tonic-gate 1977*0Sstevel@tonic-gate BIG_ERR_CODE 1978*0Sstevel@tonic-gate big_modexp_crt(BIGNUM *result, BIGNUM *a, BIGNUM *dmodpminus1, 1979*0Sstevel@tonic-gate BIGNUM *dmodqminus1, BIGNUM *p, BIGNUM *q, BIGNUM *pinvmodq, 1980*0Sstevel@tonic-gate BIGNUM *p_rr, BIGNUM *q_rr) 1981*0Sstevel@tonic-gate { 1982*0Sstevel@tonic-gate BIGNUM ap, aq, tmp; 1983*0Sstevel@tonic-gate int alen, biglen, sign; 1984*0Sstevel@tonic-gate BIG_ERR_CODE err; 1985*0Sstevel@tonic-gate 1986*0Sstevel@tonic-gate if (p->len > q->len) biglen = p->len; 1987*0Sstevel@tonic-gate else biglen = q->len; 1988*0Sstevel@tonic-gate 1989*0Sstevel@tonic-gate if ((err = big_init1(&ap, p->len, NULL, 0)) != BIG_OK) 1990*0Sstevel@tonic-gate return (err); 1991*0Sstevel@tonic-gate if ((err = big_init1(&aq, q->len, NULL, 0)) != BIG_OK) 1992*0Sstevel@tonic-gate goto ret1; 1993*0Sstevel@tonic-gate if ((err = big_init1(&tmp, biglen + q->len + 1, NULL, 0)) != BIG_OK) 1994*0Sstevel@tonic-gate goto ret2; 1995*0Sstevel@tonic-gate 1996*0Sstevel@tonic-gate /* 1997*0Sstevel@tonic-gate * check whether a is too short - to avoid timing attacks 1998*0Sstevel@tonic-gate */ 1999*0Sstevel@tonic-gate alen = a->len; 2000*0Sstevel@tonic-gate while ((alen > p->len) && (a->value[alen - 1] == 0)) { 2001*0Sstevel@tonic-gate alen--; 2002*0Sstevel@tonic-gate } 2003*0Sstevel@tonic-gate if (alen < p->len + q->len) { 2004*0Sstevel@tonic-gate /* 2005*0Sstevel@tonic-gate * a is too short, add p*q to it before 2006*0Sstevel@tonic-gate * taking it modulo p and q 2007*0Sstevel@tonic-gate * this will also affect timing, but this difference 2008*0Sstevel@tonic-gate * does not depend on p or q, only on a 2009*0Sstevel@tonic-gate * (in "normal" operation, this path will never be 2010*0Sstevel@tonic-gate * taken, so it is not a performance penalty 2011*0Sstevel@tonic-gate */ 2012*0Sstevel@tonic-gate if ((err = big_mul(&tmp, p, q)) != BIG_OK) 2013*0Sstevel@tonic-gate goto ret; 2014*0Sstevel@tonic-gate if ((err = big_add(&tmp, &tmp, a)) != BIG_OK) 2015*0Sstevel@tonic-gate goto ret; 2016*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &ap, &tmp, p)) != BIG_OK) 2017*0Sstevel@tonic-gate goto ret; 2018*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &aq, &tmp, q)) != BIG_OK) 2019*0Sstevel@tonic-gate goto ret; 2020*0Sstevel@tonic-gate } else { 2021*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &ap, a, p)) != BIG_OK) 2022*0Sstevel@tonic-gate goto ret; 2023*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &aq, a, q)) != BIG_OK) 2024*0Sstevel@tonic-gate goto ret; 2025*0Sstevel@tonic-gate } 2026*0Sstevel@tonic-gate 2027*0Sstevel@tonic-gate if ((err = big_modexp(&ap, &ap, dmodpminus1, p, p_rr)) != BIG_OK) 2028*0Sstevel@tonic-gate goto ret; 2029*0Sstevel@tonic-gate if ((err = big_modexp(&aq, &aq, dmodqminus1, q, q_rr)) != BIG_OK) 2030*0Sstevel@tonic-gate goto ret; 2031*0Sstevel@tonic-gate if ((err = big_sub(&tmp, &aq, &ap)) != BIG_OK) 2032*0Sstevel@tonic-gate goto ret; 2033*0Sstevel@tonic-gate if ((err = big_mul(&tmp, &tmp, pinvmodq)) != BIG_OK) 2034*0Sstevel@tonic-gate goto ret; 2035*0Sstevel@tonic-gate sign = tmp.sign; 2036*0Sstevel@tonic-gate tmp.sign = 1; 2037*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &aq, &tmp, q)) != BIG_OK) 2038*0Sstevel@tonic-gate goto ret; 2039*0Sstevel@tonic-gate if ((sign == -1) && (!big_is_zero(&aq))) { 2040*0Sstevel@tonic-gate (void) big_sub_pos(&aq, q, &aq); 2041*0Sstevel@tonic-gate } 2042*0Sstevel@tonic-gate if ((err = big_mul(&tmp, &aq, p)) != BIG_OK) 2043*0Sstevel@tonic-gate goto ret; 2044*0Sstevel@tonic-gate err = big_add_abs(result, &ap, &tmp); 2045*0Sstevel@tonic-gate 2046*0Sstevel@tonic-gate ret: 2047*0Sstevel@tonic-gate big_finish(&tmp); 2048*0Sstevel@tonic-gate ret2: 2049*0Sstevel@tonic-gate big_finish(&aq); 2050*0Sstevel@tonic-gate ret1: 2051*0Sstevel@tonic-gate big_finish(&ap); 2052*0Sstevel@tonic-gate 2053*0Sstevel@tonic-gate return (err); 2054*0Sstevel@tonic-gate } 2055*0Sstevel@tonic-gate 2056*0Sstevel@tonic-gate 2057*0Sstevel@tonic-gate uint32_t onearr[1] = {1}; 2058*0Sstevel@tonic-gate BIGNUM One = {1, 1, 1, 0, onearr}; 2059*0Sstevel@tonic-gate 2060*0Sstevel@tonic-gate uint32_t twoarr[1] = {2}; 2061*0Sstevel@tonic-gate BIGNUM Two = {1, 1, 1, 0, twoarr}; 2062*0Sstevel@tonic-gate 2063*0Sstevel@tonic-gate uint32_t fourarr[1] = {4}; 2064*0Sstevel@tonic-gate BIGNUM Four = {1, 1, 1, 0, fourarr}; 2065*0Sstevel@tonic-gate 2066*0Sstevel@tonic-gate BIG_ERR_CODE 2067*0Sstevel@tonic-gate big_sqrt_pos(BIGNUM *result, BIGNUM *n) 2068*0Sstevel@tonic-gate { 2069*0Sstevel@tonic-gate BIGNUM *high, *low, *mid, *t; 2070*0Sstevel@tonic-gate BIGNUM t1, t2, t3, prod; 2071*0Sstevel@tonic-gate uint32_t t1value[BIGTMPSIZE]; 2072*0Sstevel@tonic-gate uint32_t t2value[BIGTMPSIZE]; 2073*0Sstevel@tonic-gate uint32_t t3value[BIGTMPSIZE]; 2074*0Sstevel@tonic-gate uint32_t prodvalue[BIGTMPSIZE]; 2075*0Sstevel@tonic-gate int i, nbits, diff, nrootbits, highbits; 2076*0Sstevel@tonic-gate BIG_ERR_CODE err; 2077*0Sstevel@tonic-gate 2078*0Sstevel@tonic-gate nbits = big_numbits(n); 2079*0Sstevel@tonic-gate 2080*0Sstevel@tonic-gate if ((err = big_init1(&t1, n->len + 1, 2081*0Sstevel@tonic-gate t1value, arraysize(t1value))) != BIG_OK) 2082*0Sstevel@tonic-gate return (err); 2083*0Sstevel@tonic-gate if ((err = big_init1(&t2, n->len + 1, 2084*0Sstevel@tonic-gate t2value, arraysize(t2value))) != BIG_OK) 2085*0Sstevel@tonic-gate goto ret1; 2086*0Sstevel@tonic-gate if ((err = big_init1(&t3, n->len + 1, 2087*0Sstevel@tonic-gate t3value, arraysize(t3value))) != BIG_OK) 2088*0Sstevel@tonic-gate goto ret2; 2089*0Sstevel@tonic-gate if ((err = big_init1(&prod, n->len + 1, 2090*0Sstevel@tonic-gate prodvalue, arraysize(prodvalue))) != BIG_OK) 2091*0Sstevel@tonic-gate goto ret3; 2092*0Sstevel@tonic-gate 2093*0Sstevel@tonic-gate nrootbits = (nbits + 1) / 2; 2094*0Sstevel@tonic-gate t1.len = t2.len = t3.len = (nrootbits - 1) / 32 + 1; 2095*0Sstevel@tonic-gate for (i = 0; i < t1.len; i++) { 2096*0Sstevel@tonic-gate t1.value[i] = 0; 2097*0Sstevel@tonic-gate t2.value[i] = 0xffffffff; 2098*0Sstevel@tonic-gate } 2099*0Sstevel@tonic-gate highbits = nrootbits - 32 * (t1.len - 1); 2100*0Sstevel@tonic-gate if (highbits == 32) { 2101*0Sstevel@tonic-gate t1.value[t1.len - 1] = 0x80000000; 2102*0Sstevel@tonic-gate t2.value[t2.len - 1] = 0xffffffff; 2103*0Sstevel@tonic-gate } else { 2104*0Sstevel@tonic-gate t1.value[t1.len - 1] = 1 << (highbits - 1); 2105*0Sstevel@tonic-gate t2.value[t2.len - 1] = 2 * t1.value[t1.len - 1] - 1; 2106*0Sstevel@tonic-gate } 2107*0Sstevel@tonic-gate high = &t2; 2108*0Sstevel@tonic-gate low = &t1; 2109*0Sstevel@tonic-gate mid = &t3; 2110*0Sstevel@tonic-gate 2111*0Sstevel@tonic-gate if ((err = big_mul(&prod, high, high)) != BIG_OK) 2112*0Sstevel@tonic-gate goto ret; 2113*0Sstevel@tonic-gate diff = big_cmp_abs(&prod, n); 2114*0Sstevel@tonic-gate if (diff <= 0) { 2115*0Sstevel@tonic-gate err = big_copy(result, high); 2116*0Sstevel@tonic-gate goto ret; 2117*0Sstevel@tonic-gate } 2118*0Sstevel@tonic-gate 2119*0Sstevel@tonic-gate (void) big_sub_pos(mid, high, low); 2120*0Sstevel@tonic-gate while (big_cmp_abs(&One, mid) != 0) { 2121*0Sstevel@tonic-gate (void) big_add_abs(mid, high, low); 2122*0Sstevel@tonic-gate (void) big_half_pos(mid, mid); 2123*0Sstevel@tonic-gate if ((err = big_mul(&prod, mid, mid)) != BIG_OK) 2124*0Sstevel@tonic-gate goto ret; 2125*0Sstevel@tonic-gate diff = big_cmp_abs(&prod, n); 2126*0Sstevel@tonic-gate if (diff > 0) { 2127*0Sstevel@tonic-gate t = high; 2128*0Sstevel@tonic-gate high = mid; 2129*0Sstevel@tonic-gate mid = t; 2130*0Sstevel@tonic-gate } else if (diff < 0) { 2131*0Sstevel@tonic-gate t = low; 2132*0Sstevel@tonic-gate low = mid; 2133*0Sstevel@tonic-gate mid = t; 2134*0Sstevel@tonic-gate } else { 2135*0Sstevel@tonic-gate err = big_copy(result, low); 2136*0Sstevel@tonic-gate goto ret; 2137*0Sstevel@tonic-gate } 2138*0Sstevel@tonic-gate (void) big_sub_pos(mid, high, low); 2139*0Sstevel@tonic-gate } 2140*0Sstevel@tonic-gate 2141*0Sstevel@tonic-gate err = big_copy(result, low); 2142*0Sstevel@tonic-gate ret: 2143*0Sstevel@tonic-gate if (prod.malloced) big_finish(&prod); 2144*0Sstevel@tonic-gate ret3: 2145*0Sstevel@tonic-gate if (t3.malloced) big_finish(&t3); 2146*0Sstevel@tonic-gate ret2: 2147*0Sstevel@tonic-gate if (t2.malloced) big_finish(&t2); 2148*0Sstevel@tonic-gate ret1: 2149*0Sstevel@tonic-gate if (t1.malloced) big_finish(&t1); 2150*0Sstevel@tonic-gate 2151*0Sstevel@tonic-gate return (err); 2152*0Sstevel@tonic-gate } 2153*0Sstevel@tonic-gate 2154*0Sstevel@tonic-gate 2155*0Sstevel@tonic-gate BIG_ERR_CODE 2156*0Sstevel@tonic-gate big_Jacobi_pos(int *jac, BIGNUM *nn, BIGNUM *mm) 2157*0Sstevel@tonic-gate { 2158*0Sstevel@tonic-gate BIGNUM *t, *tmp2, *m, *n; 2159*0Sstevel@tonic-gate BIGNUM t1, t2, t3; 2160*0Sstevel@tonic-gate uint32_t t1value[BIGTMPSIZE]; 2161*0Sstevel@tonic-gate uint32_t t2value[BIGTMPSIZE]; 2162*0Sstevel@tonic-gate uint32_t t3value[BIGTMPSIZE]; 2163*0Sstevel@tonic-gate int len, err; 2164*0Sstevel@tonic-gate 2165*0Sstevel@tonic-gate if (big_is_zero(nn) || 2166*0Sstevel@tonic-gate (((nn->value[0] & 1) | (mm->value[0] & 1)) == 0)) { 2167*0Sstevel@tonic-gate *jac = 0; 2168*0Sstevel@tonic-gate return (BIG_OK); 2169*0Sstevel@tonic-gate } 2170*0Sstevel@tonic-gate 2171*0Sstevel@tonic-gate if (nn->len > mm->len) len = nn->len; 2172*0Sstevel@tonic-gate else len = mm->len; 2173*0Sstevel@tonic-gate 2174*0Sstevel@tonic-gate if ((err = big_init1(&t1, len, 2175*0Sstevel@tonic-gate t1value, arraysize(t1value))) != BIG_OK) 2176*0Sstevel@tonic-gate return (err); 2177*0Sstevel@tonic-gate if ((err = big_init1(&t2, len, 2178*0Sstevel@tonic-gate t2value, arraysize(t2value))) != BIG_OK) 2179*0Sstevel@tonic-gate goto ret1; 2180*0Sstevel@tonic-gate if ((err = big_init1(&t3, len, 2181*0Sstevel@tonic-gate t3value, arraysize(t3value))) != BIG_OK) 2182*0Sstevel@tonic-gate goto ret2; 2183*0Sstevel@tonic-gate 2184*0Sstevel@tonic-gate n = &t1; 2185*0Sstevel@tonic-gate m = &t2; 2186*0Sstevel@tonic-gate tmp2 = &t3; 2187*0Sstevel@tonic-gate 2188*0Sstevel@tonic-gate (void) big_copy(n, nn); 2189*0Sstevel@tonic-gate (void) big_copy(m, mm); 2190*0Sstevel@tonic-gate 2191*0Sstevel@tonic-gate *jac = 1; 2192*0Sstevel@tonic-gate while (big_cmp_abs(&One, m) != 0) { 2193*0Sstevel@tonic-gate if (big_is_zero(n)) { 2194*0Sstevel@tonic-gate *jac = 0; 2195*0Sstevel@tonic-gate goto ret; 2196*0Sstevel@tonic-gate } 2197*0Sstevel@tonic-gate if ((m->value[0] & 1) == 0) { 2198*0Sstevel@tonic-gate if (((n->value[0] & 7) == 3) || 2199*0Sstevel@tonic-gate ((n->value[0] & 7) == 5)) *jac = -*jac; 2200*0Sstevel@tonic-gate (void) big_half_pos(m, m); 2201*0Sstevel@tonic-gate } else if ((n->value[0] & 1) == 0) { 2202*0Sstevel@tonic-gate if (((m->value[0] & 7) == 3) || 2203*0Sstevel@tonic-gate ((m->value[0] & 7) == 5)) *jac = -*jac; 2204*0Sstevel@tonic-gate (void) big_half_pos(n, n); 2205*0Sstevel@tonic-gate } else { 2206*0Sstevel@tonic-gate if (((m->value[0] & 3) == 3) && 2207*0Sstevel@tonic-gate ((n->value[0] & 3) == 3)) { 2208*0Sstevel@tonic-gate *jac = -*jac; 2209*0Sstevel@tonic-gate } 2210*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, tmp2, m, n)) != BIG_OK) 2211*0Sstevel@tonic-gate goto ret; 2212*0Sstevel@tonic-gate t = tmp2; 2213*0Sstevel@tonic-gate tmp2 = m; 2214*0Sstevel@tonic-gate m = n; 2215*0Sstevel@tonic-gate n = t; 2216*0Sstevel@tonic-gate } 2217*0Sstevel@tonic-gate } 2218*0Sstevel@tonic-gate err = BIG_OK; 2219*0Sstevel@tonic-gate 2220*0Sstevel@tonic-gate ret: 2221*0Sstevel@tonic-gate if (t3.malloced) big_finish(&t3); 2222*0Sstevel@tonic-gate ret2: 2223*0Sstevel@tonic-gate if (t2.malloced) big_finish(&t2); 2224*0Sstevel@tonic-gate ret1: 2225*0Sstevel@tonic-gate if (t1.malloced) big_finish(&t1); 2226*0Sstevel@tonic-gate 2227*0Sstevel@tonic-gate return (err); 2228*0Sstevel@tonic-gate } 2229*0Sstevel@tonic-gate 2230*0Sstevel@tonic-gate 2231*0Sstevel@tonic-gate BIG_ERR_CODE 2232*0Sstevel@tonic-gate big_Lucas(BIGNUM *Lkminus1, BIGNUM *Lk, BIGNUM *p, BIGNUM *k, BIGNUM *n) 2233*0Sstevel@tonic-gate { 2234*0Sstevel@tonic-gate int m, w, i; 2235*0Sstevel@tonic-gate uint32_t bit; 2236*0Sstevel@tonic-gate BIGNUM ki, tmp, tmp2; 2237*0Sstevel@tonic-gate uint32_t kivalue[BIGTMPSIZE]; 2238*0Sstevel@tonic-gate uint32_t tmpvalue[BIGTMPSIZE]; 2239*0Sstevel@tonic-gate uint32_t tmp2value[BIGTMPSIZE]; 2240*0Sstevel@tonic-gate BIG_ERR_CODE err; 2241*0Sstevel@tonic-gate 2242*0Sstevel@tonic-gate if (big_cmp_abs(k, &One) == 0) { 2243*0Sstevel@tonic-gate (void) big_copy(Lk, p); 2244*0Sstevel@tonic-gate (void) big_copy(Lkminus1, &Two); 2245*0Sstevel@tonic-gate return (BIG_OK); 2246*0Sstevel@tonic-gate } 2247*0Sstevel@tonic-gate 2248*0Sstevel@tonic-gate if ((err = big_init1(&ki, k->len + 1, 2249*0Sstevel@tonic-gate kivalue, arraysize(kivalue))) != BIG_OK) 2250*0Sstevel@tonic-gate return (err); 2251*0Sstevel@tonic-gate 2252*0Sstevel@tonic-gate if ((err = big_init1(&tmp, 2 * n->len +1, 2253*0Sstevel@tonic-gate tmpvalue, arraysize(tmpvalue))) != BIG_OK) 2254*0Sstevel@tonic-gate goto ret1; 2255*0Sstevel@tonic-gate 2256*0Sstevel@tonic-gate if ((err = big_init1(&tmp2, n->len, 2257*0Sstevel@tonic-gate tmp2value, arraysize(tmp2value))) != BIG_OK) 2258*0Sstevel@tonic-gate goto ret2; 2259*0Sstevel@tonic-gate 2260*0Sstevel@tonic-gate m = big_numbits(k); 2261*0Sstevel@tonic-gate ki.len = (m - 1) / 32 + 1; 2262*0Sstevel@tonic-gate w = (m - 1) / 32; 2263*0Sstevel@tonic-gate bit = 1 << ((m - 1) % 32); 2264*0Sstevel@tonic-gate for (i = 0; i < ki.len; i++) ki.value[i] = 0; 2265*0Sstevel@tonic-gate ki.value[ki.len - 1] = bit; 2266*0Sstevel@tonic-gate if (big_cmp_abs(k, &ki) != 0) 2267*0Sstevel@tonic-gate (void) big_double(&ki, &ki); 2268*0Sstevel@tonic-gate (void) big_sub_pos(&ki, &ki, k); 2269*0Sstevel@tonic-gate 2270*0Sstevel@tonic-gate (void) big_copy(Lk, p); 2271*0Sstevel@tonic-gate (void) big_copy(Lkminus1, &Two); 2272*0Sstevel@tonic-gate 2273*0Sstevel@tonic-gate for (i = 0; i < m; i++) { 2274*0Sstevel@tonic-gate if ((err = big_mul(&tmp, Lk, Lkminus1)) != BIG_OK) 2275*0Sstevel@tonic-gate goto ret; 2276*0Sstevel@tonic-gate (void) big_add_abs(&tmp, &tmp, n); 2277*0Sstevel@tonic-gate (void) big_sub_pos(&tmp, &tmp, p); 2278*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, &tmp2, &tmp, n)) != BIG_OK) 2279*0Sstevel@tonic-gate goto ret; 2280*0Sstevel@tonic-gate 2281*0Sstevel@tonic-gate if ((ki.value[w] & bit) != 0) { 2282*0Sstevel@tonic-gate if ((err = big_mul(&tmp, Lkminus1, Lkminus1)) != 2283*0Sstevel@tonic-gate BIG_OK) 2284*0Sstevel@tonic-gate goto ret; 2285*0Sstevel@tonic-gate (void) big_add_abs(&tmp, &tmp, n); 2286*0Sstevel@tonic-gate (void) big_sub_pos(&tmp, &tmp, &Two); 2287*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, Lkminus1, &tmp, n)) != 2288*0Sstevel@tonic-gate BIG_OK) 2289*0Sstevel@tonic-gate goto ret; 2290*0Sstevel@tonic-gate (void) big_copy(Lk, &tmp2); 2291*0Sstevel@tonic-gate } else { 2292*0Sstevel@tonic-gate if ((err = big_mul(&tmp, Lk, Lk)) != BIG_OK) 2293*0Sstevel@tonic-gate goto ret; 2294*0Sstevel@tonic-gate (void) big_add_abs(&tmp, &tmp, n); 2295*0Sstevel@tonic-gate (void) big_sub_pos(&tmp, &tmp, &Two); 2296*0Sstevel@tonic-gate if ((err = big_div_pos(NULL, Lk, &tmp, n)) != BIG_OK) 2297*0Sstevel@tonic-gate goto ret; 2298*0Sstevel@tonic-gate (void) big_copy(Lkminus1, &tmp2); 2299*0Sstevel@tonic-gate } 2300*0Sstevel@tonic-gate bit = bit >> 1; 2301*0Sstevel@tonic-gate if (bit == 0) { 2302*0Sstevel@tonic-gate bit = 0x80000000; 2303*0Sstevel@tonic-gate w--; 2304*0Sstevel@tonic-gate } 2305*0Sstevel@tonic-gate } 2306*0Sstevel@tonic-gate 2307*0Sstevel@tonic-gate err = BIG_OK; 2308*0Sstevel@tonic-gate 2309*0Sstevel@tonic-gate ret: 2310*0Sstevel@tonic-gate if (tmp2.malloced) big_finish(&tmp2); 2311*0Sstevel@tonic-gate ret2: 2312*0Sstevel@tonic-gate if (tmp.malloced) big_finish(&tmp); 2313*0Sstevel@tonic-gate ret1: 2314*0Sstevel@tonic-gate if (ki.malloced) big_finish(&ki); 2315*0Sstevel@tonic-gate 2316*0Sstevel@tonic-gate return (err); 2317*0Sstevel@tonic-gate } 2318*0Sstevel@tonic-gate 2319*0Sstevel@tonic-gate 2320*0Sstevel@tonic-gate BIG_ERR_CODE 2321*0Sstevel@tonic-gate big_isprime_pos(BIGNUM *n) 2322*0Sstevel@tonic-gate { 2323*0Sstevel@tonic-gate BIGNUM o, nminus1, tmp, Lkminus1, Lk; 2324*0Sstevel@tonic-gate uint32_t ovalue[BIGTMPSIZE]; 2325*0Sstevel@tonic-gate uint32_t nminus1value[BIGTMPSIZE]; 2326*0Sstevel@tonic-gate uint32_t tmpvalue[BIGTMPSIZE]; 2327*0Sstevel@tonic-gate uint32_t Lkminus1value[BIGTMPSIZE]; 2328*0Sstevel@tonic-gate uint32_t Lkvalue[BIGTMPSIZE]; 2329*0Sstevel@tonic-gate BIG_ERR_CODE err; 2330*0Sstevel@tonic-gate int e, i, jac; 2331*0Sstevel@tonic-gate 2332*0Sstevel@tonic-gate if (big_cmp_abs(n, &One) == 0) 2333*0Sstevel@tonic-gate return (BIG_FALSE); 2334*0Sstevel@tonic-gate if (big_cmp_abs(n, &Two) == 0) 2335*0Sstevel@tonic-gate return (BIG_TRUE); 2336*0Sstevel@tonic-gate if ((n->value[0] & 1) == 0) 2337*0Sstevel@tonic-gate return (BIG_FALSE); 2338*0Sstevel@tonic-gate 2339*0Sstevel@tonic-gate if ((err = big_init1(&o, n->len, ovalue, arraysize(ovalue))) != BIG_OK) 2340*0Sstevel@tonic-gate return (err); 2341*0Sstevel@tonic-gate 2342*0Sstevel@tonic-gate if ((err = big_init1(&nminus1, n->len, 2343*0Sstevel@tonic-gate nminus1value, arraysize(nminus1value))) != BIG_OK) 2344*0Sstevel@tonic-gate goto ret1; 2345*0Sstevel@tonic-gate 2346*0Sstevel@tonic-gate if ((err = big_init1(&tmp, 2 * n->len, 2347*0Sstevel@tonic-gate tmpvalue, arraysize(tmpvalue))) != BIG_OK) 2348*0Sstevel@tonic-gate goto ret2; 2349*0Sstevel@tonic-gate 2350*0Sstevel@tonic-gate if ((err = big_init1(&Lkminus1, n->len, 2351*0Sstevel@tonic-gate Lkminus1value, arraysize(Lkminus1value))) != BIG_OK) 2352*0Sstevel@tonic-gate goto ret3; 2353*0Sstevel@tonic-gate 2354*0Sstevel@tonic-gate if ((err = big_init1(&Lk, n->len, 2355*0Sstevel@tonic-gate Lkvalue, arraysize(Lkvalue))) != BIG_OK) 2356*0Sstevel@tonic-gate goto ret4; 2357*0Sstevel@tonic-gate 2358*0Sstevel@tonic-gate (void) big_sub_pos(&o, n, &One); /* cannot fail */ 2359*0Sstevel@tonic-gate (void) big_copy(&nminus1, &o); /* cannot fail */ 2360*0Sstevel@tonic-gate e = 0; 2361*0Sstevel@tonic-gate while ((o.value[0] & 1) == 0) { 2362*0Sstevel@tonic-gate e++; 2363*0Sstevel@tonic-gate (void) big_half_pos(&o, &o); /* cannot fail */ 2364*0Sstevel@tonic-gate } 2365*0Sstevel@tonic-gate if ((err = big_modexp(&tmp, &Two, &o, n, NULL)) != BIG_OK) 2366*0Sstevel@tonic-gate goto ret; 2367*0Sstevel@tonic-gate i = 0; 2368*0Sstevel@tonic-gate while ((i < e) && 2369*0Sstevel@tonic-gate (big_cmp_abs(&tmp, &One) != 0) && 2370*0Sstevel@tonic-gate (big_cmp_abs(&tmp, &nminus1) != 0)) { 2371*0Sstevel@tonic-gate if ((err = big_modexp(&tmp, &tmp, &Two, n, NULL)) != BIG_OK) 2372*0Sstevel@tonic-gate goto ret; 2373*0Sstevel@tonic-gate i++; 2374*0Sstevel@tonic-gate } 2375*0Sstevel@tonic-gate if (!((big_cmp_abs(&tmp, &nminus1) == 0) || 2376*0Sstevel@tonic-gate ((i == 0) && (big_cmp_abs(&tmp, &One) == 0)))) { 2377*0Sstevel@tonic-gate err = BIG_FALSE; 2378*0Sstevel@tonic-gate goto ret; 2379*0Sstevel@tonic-gate } 2380*0Sstevel@tonic-gate 2381*0Sstevel@tonic-gate if ((err = big_sqrt_pos(&tmp, n)) != BIG_OK) 2382*0Sstevel@tonic-gate goto ret; 2383*0Sstevel@tonic-gate if ((err = big_mul(&tmp, &tmp, &tmp)) != BIG_OK) 2384*0Sstevel@tonic-gate goto ret; 2385*0Sstevel@tonic-gate if (big_cmp_abs(&tmp, n) == 0) { 2386*0Sstevel@tonic-gate err = BIG_FALSE; 2387*0Sstevel@tonic-gate goto ret; 2388*0Sstevel@tonic-gate } 2389*0Sstevel@tonic-gate 2390*0Sstevel@tonic-gate (void) big_copy(&o, &Two); 2391*0Sstevel@tonic-gate do { 2392*0Sstevel@tonic-gate (void) big_add_abs(&o, &o, &One); 2393*0Sstevel@tonic-gate if ((err = big_mul(&tmp, &o, &o)) != BIG_OK) 2394*0Sstevel@tonic-gate goto ret; 2395*0Sstevel@tonic-gate (void) big_sub_pos(&tmp, &tmp, &Four); 2396*0Sstevel@tonic-gate if ((err = big_Jacobi_pos(&jac, &tmp, n)) != BIG_OK) 2397*0Sstevel@tonic-gate goto ret; 2398*0Sstevel@tonic-gate } while (jac != -1); 2399*0Sstevel@tonic-gate 2400*0Sstevel@tonic-gate (void) big_add_abs(&tmp, n, &One); 2401*0Sstevel@tonic-gate if ((err = big_Lucas(&Lkminus1, &Lk, &o, &tmp, n)) != BIG_OK) 2402*0Sstevel@tonic-gate goto ret; 2403*0Sstevel@tonic-gate if ((big_cmp_abs(&Lkminus1, &o) == 0) && (big_cmp_abs(&Lk, &Two) == 0)) 2404*0Sstevel@tonic-gate err = BIG_TRUE; 2405*0Sstevel@tonic-gate else err = BIG_FALSE; 2406*0Sstevel@tonic-gate 2407*0Sstevel@tonic-gate ret: 2408*0Sstevel@tonic-gate if (Lk.malloced) big_finish(&Lk); 2409*0Sstevel@tonic-gate ret4: 2410*0Sstevel@tonic-gate if (Lkminus1.malloced) big_finish(&Lkminus1); 2411*0Sstevel@tonic-gate ret3: 2412*0Sstevel@tonic-gate if (tmp.malloced) big_finish(&tmp); 2413*0Sstevel@tonic-gate ret2: 2414*0Sstevel@tonic-gate if (nminus1.malloced) big_finish(&nminus1); 2415*0Sstevel@tonic-gate ret1: 2416*0Sstevel@tonic-gate if (o.malloced) big_finish(&o); 2417*0Sstevel@tonic-gate 2418*0Sstevel@tonic-gate return (err); 2419*0Sstevel@tonic-gate } 2420*0Sstevel@tonic-gate 2421*0Sstevel@tonic-gate 2422*0Sstevel@tonic-gate #define SIEVESIZE 1000 2423*0Sstevel@tonic-gate 2424*0Sstevel@tonic-gate uint32_t smallprimes[] = 2425*0Sstevel@tonic-gate { 2426*0Sstevel@tonic-gate 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 2427*0Sstevel@tonic-gate 51, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97 2428*0Sstevel@tonic-gate }; 2429*0Sstevel@tonic-gate 2430*0Sstevel@tonic-gate 2431*0Sstevel@tonic-gate BIG_ERR_CODE 2432*0Sstevel@tonic-gate big_nextprime_pos(BIGNUM *result, BIGNUM *n) 2433*0Sstevel@tonic-gate { 2434*0Sstevel@tonic-gate BIG_ERR_CODE err; 2435*0Sstevel@tonic-gate int sieve[SIEVESIZE]; 2436*0Sstevel@tonic-gate int i; 2437*0Sstevel@tonic-gate uint32_t off, p; 2438*0Sstevel@tonic-gate 2439*0Sstevel@tonic-gate if ((err = big_copy(result, n)) != BIG_OK) 2440*0Sstevel@tonic-gate return (err); 2441*0Sstevel@tonic-gate result->value[0] |= 1; 2442*0Sstevel@tonic-gate /* LINTED */ 2443*0Sstevel@tonic-gate while (1) { 2444*0Sstevel@tonic-gate for (i = 0; i < SIEVESIZE; i++) sieve[i] = 0; 2445*0Sstevel@tonic-gate for (i = 0; 2446*0Sstevel@tonic-gate i < sizeof (smallprimes) / sizeof (uint32_t); i++) { 2447*0Sstevel@tonic-gate p = smallprimes[i]; 2448*0Sstevel@tonic-gate off = big_mod16_pos(result, p); 2449*0Sstevel@tonic-gate off = p - off; 2450*0Sstevel@tonic-gate if ((off % 2) == 1) off = off + p; 2451*0Sstevel@tonic-gate off = off/2; 2452*0Sstevel@tonic-gate while (off < SIEVESIZE) { 2453*0Sstevel@tonic-gate sieve[off] = 1; 2454*0Sstevel@tonic-gate off = off + p; 2455*0Sstevel@tonic-gate } 2456*0Sstevel@tonic-gate } 2457*0Sstevel@tonic-gate 2458*0Sstevel@tonic-gate for (i = 0; i < SIEVESIZE; i++) { 2459*0Sstevel@tonic-gate if (sieve[i] == 0) { 2460*0Sstevel@tonic-gate err = big_isprime_pos(result); 2461*0Sstevel@tonic-gate if (err != BIG_FALSE) { 2462*0Sstevel@tonic-gate if (err != BIG_TRUE) 2463*0Sstevel@tonic-gate return (err); 2464*0Sstevel@tonic-gate else 2465*0Sstevel@tonic-gate return (BIG_OK); 2466*0Sstevel@tonic-gate } 2467*0Sstevel@tonic-gate 2468*0Sstevel@tonic-gate } 2469*0Sstevel@tonic-gate if ((err = big_add_abs(result, result, &Two)) != 2470*0Sstevel@tonic-gate BIG_OK) 2471*0Sstevel@tonic-gate return (err); 2472*0Sstevel@tonic-gate } 2473*0Sstevel@tonic-gate } 2474*0Sstevel@tonic-gate return (BIG_OK); 2475*0Sstevel@tonic-gate } 2476*0Sstevel@tonic-gate 2477*0Sstevel@tonic-gate 2478*0Sstevel@tonic-gate BIG_ERR_CODE 2479*0Sstevel@tonic-gate big_nextprime_pos_slow(BIGNUM *result, BIGNUM *n) 2480*0Sstevel@tonic-gate { 2481*0Sstevel@tonic-gate BIG_ERR_CODE err; 2482*0Sstevel@tonic-gate 2483*0Sstevel@tonic-gate 2484*0Sstevel@tonic-gate if ((err = big_copy(result, n)) != BIG_OK) 2485*0Sstevel@tonic-gate return (err); 2486*0Sstevel@tonic-gate result->value[0] |= 1; 2487*0Sstevel@tonic-gate while ((err = big_isprime_pos(result)) != BIG_TRUE) { 2488*0Sstevel@tonic-gate if (err != BIG_FALSE) 2489*0Sstevel@tonic-gate return (err); 2490*0Sstevel@tonic-gate if ((err = big_add_abs(result, result, &Two)) != BIG_OK) 2491*0Sstevel@tonic-gate return (err); 2492*0Sstevel@tonic-gate } 2493*0Sstevel@tonic-gate return (BIG_OK); 2494*0Sstevel@tonic-gate } 2495*0Sstevel@tonic-gate 2496*0Sstevel@tonic-gate 2497*0Sstevel@tonic-gate /* 2498*0Sstevel@tonic-gate * given m and e, computes the rest in the equation 2499*0Sstevel@tonic-gate * gcd(m, e) = cm * m + ce * e 2500*0Sstevel@tonic-gate */ 2501*0Sstevel@tonic-gate BIG_ERR_CODE 2502*0Sstevel@tonic-gate big_ext_gcd_pos(BIGNUM *gcd, BIGNUM *cm, BIGNUM *ce, BIGNUM *m, BIGNUM *e) 2503*0Sstevel@tonic-gate { 2504*0Sstevel@tonic-gate BIGNUM *xi, *ri, *riminus1, *riminus2, *t, 2505*0Sstevel@tonic-gate *vmi, *vei, *vmiminus1, *veiminus1; 2506*0Sstevel@tonic-gate BIGNUM t1, t2, t3, t4, t5, t6, t7, t8, tmp; 2507*0Sstevel@tonic-gate uint32_t t1value[BIGTMPSIZE]; 2508*0Sstevel@tonic-gate uint32_t t2value[BIGTMPSIZE]; 2509*0Sstevel@tonic-gate uint32_t t3value[BIGTMPSIZE]; 2510*0Sstevel@tonic-gate uint32_t t4value[BIGTMPSIZE]; 2511*0Sstevel@tonic-gate uint32_t t5value[BIGTMPSIZE]; 2512*0Sstevel@tonic-gate uint32_t t6value[BIGTMPSIZE]; 2513*0Sstevel@tonic-gate uint32_t t7value[BIGTMPSIZE]; 2514*0Sstevel@tonic-gate uint32_t t8value[BIGTMPSIZE]; 2515*0Sstevel@tonic-gate uint32_t tmpvalue[BIGTMPSIZE]; 2516*0Sstevel@tonic-gate BIG_ERR_CODE err; 2517*0Sstevel@tonic-gate int len; 2518*0Sstevel@tonic-gate 2519*0Sstevel@tonic-gate if (big_cmp_abs(m, e) >= 0) len = m->len; 2520*0Sstevel@tonic-gate else len = e->len; 2521*0Sstevel@tonic-gate 2522*0Sstevel@tonic-gate if ((err = big_init1(&t1, len, 2523*0Sstevel@tonic-gate t1value, arraysize(t1value))) != BIG_OK) 2524*0Sstevel@tonic-gate return (err); 2525*0Sstevel@tonic-gate if ((err = big_init1(&t2, len, 2526*0Sstevel@tonic-gate t2value, arraysize(t2value))) != BIG_OK) 2527*0Sstevel@tonic-gate goto ret1; 2528*0Sstevel@tonic-gate if ((err = big_init1(&t3, len, 2529*0Sstevel@tonic-gate t3value, arraysize(t3value))) != BIG_OK) 2530*0Sstevel@tonic-gate goto ret2; 2531*0Sstevel@tonic-gate if ((err = big_init1(&t4, len, 2532*0Sstevel@tonic-gate t4value, arraysize(t3value))) != BIG_OK) 2533*0Sstevel@tonic-gate goto ret3; 2534*0Sstevel@tonic-gate if ((err = big_init1(&t5, len, 2535*0Sstevel@tonic-gate t5value, arraysize(t5value))) != BIG_OK) 2536*0Sstevel@tonic-gate goto ret4; 2537*0Sstevel@tonic-gate if ((err = big_init1(&t6, len, 2538*0Sstevel@tonic-gate t6value, arraysize(t6value))) != BIG_OK) 2539*0Sstevel@tonic-gate goto ret5; 2540*0Sstevel@tonic-gate if ((err = big_init1(&t7, len, 2541*0Sstevel@tonic-gate t7value, arraysize(t7value))) != BIG_OK) 2542*0Sstevel@tonic-gate goto ret6; 2543*0Sstevel@tonic-gate if ((err = big_init1(&t8, len, 2544*0Sstevel@tonic-gate t8value, arraysize(t8value))) != BIG_OK) 2545*0Sstevel@tonic-gate goto ret7; 2546*0Sstevel@tonic-gate 2547*0Sstevel@tonic-gate if ((err = big_init1(&tmp, 2 * len, 2548*0Sstevel@tonic-gate tmpvalue, arraysize(tmpvalue))) != BIG_OK) 2549*0Sstevel@tonic-gate goto ret8; 2550*0Sstevel@tonic-gate 2551*0Sstevel@tonic-gate ri = &t1; 2552*0Sstevel@tonic-gate ri->value[0] = 1; 2553*0Sstevel@tonic-gate ri->len = 1; 2554*0Sstevel@tonic-gate xi = &t2; 2555*0Sstevel@tonic-gate riminus1 = &t3; 2556*0Sstevel@tonic-gate riminus2 = &t4; 2557*0Sstevel@tonic-gate vmi = &t5; 2558*0Sstevel@tonic-gate vei = &t6; 2559*0Sstevel@tonic-gate vmiminus1 = &t7; 2560*0Sstevel@tonic-gate veiminus1 = &t8; 2561*0Sstevel@tonic-gate 2562*0Sstevel@tonic-gate (void) big_copy(vmiminus1, &One); 2563*0Sstevel@tonic-gate (void) big_copy(vmi, &One); 2564*0Sstevel@tonic-gate (void) big_copy(veiminus1, &One); 2565*0Sstevel@tonic-gate (void) big_copy(xi, &One); 2566*0Sstevel@tonic-gate vei->len = 1; 2567*0Sstevel@tonic-gate vei->value[0] = 0; 2568*0Sstevel@tonic-gate 2569*0Sstevel@tonic-gate (void) big_copy(riminus1, m); 2570*0Sstevel@tonic-gate (void) big_copy(ri, e); 2571*0Sstevel@tonic-gate 2572*0Sstevel@tonic-gate while (!big_is_zero(ri)) { 2573*0Sstevel@tonic-gate t = riminus2; 2574*0Sstevel@tonic-gate riminus2 = riminus1; 2575*0Sstevel@tonic-gate riminus1 = ri; 2576*0Sstevel@tonic-gate ri = t; 2577*0Sstevel@tonic-gate if ((err = big_mul(&tmp, vmi, xi)) != BIG_OK) 2578*0Sstevel@tonic-gate goto ret; 2579*0Sstevel@tonic-gate if ((err = big_sub(vmiminus1, vmiminus1, &tmp)) != BIG_OK) 2580*0Sstevel@tonic-gate goto ret; 2581*0Sstevel@tonic-gate t = vmiminus1; 2582*0Sstevel@tonic-gate vmiminus1 = vmi; 2583*0Sstevel@tonic-gate vmi = t; 2584*0Sstevel@tonic-gate if ((err = big_mul(&tmp, vei, xi)) != BIG_OK) 2585*0Sstevel@tonic-gate goto ret; 2586*0Sstevel@tonic-gate if ((err = big_sub(veiminus1, veiminus1, &tmp)) != BIG_OK) 2587*0Sstevel@tonic-gate goto ret; 2588*0Sstevel@tonic-gate t = veiminus1; 2589*0Sstevel@tonic-gate veiminus1 = vei; 2590*0Sstevel@tonic-gate vei = t; 2591*0Sstevel@tonic-gate if ((err = big_div_pos(xi, ri, riminus2, riminus1)) != BIG_OK) 2592*0Sstevel@tonic-gate goto ret; 2593*0Sstevel@tonic-gate } 2594*0Sstevel@tonic-gate if ((gcd != NULL) && ((err = big_copy(gcd, riminus1)) != BIG_OK)) 2595*0Sstevel@tonic-gate goto ret; 2596*0Sstevel@tonic-gate if ((cm != NULL) && ((err = big_copy(cm, vmi)) != BIG_OK)) 2597*0Sstevel@tonic-gate goto ret; 2598*0Sstevel@tonic-gate if (ce != NULL) 2599*0Sstevel@tonic-gate err = big_copy(ce, vei); 2600*0Sstevel@tonic-gate ret: 2601*0Sstevel@tonic-gate if (tmp.malloced) big_finish(&tmp); 2602*0Sstevel@tonic-gate ret8: 2603*0Sstevel@tonic-gate if (t8.malloced) big_finish(&t8); 2604*0Sstevel@tonic-gate ret7: 2605*0Sstevel@tonic-gate if (t7.malloced) big_finish(&t7); 2606*0Sstevel@tonic-gate ret6: 2607*0Sstevel@tonic-gate if (t6.malloced) big_finish(&t6); 2608*0Sstevel@tonic-gate ret5: 2609*0Sstevel@tonic-gate if (t5.malloced) big_finish(&t5); 2610*0Sstevel@tonic-gate ret4: 2611*0Sstevel@tonic-gate if (t4.malloced) big_finish(&t4); 2612*0Sstevel@tonic-gate ret3: 2613*0Sstevel@tonic-gate if (t3.malloced) big_finish(&t3); 2614*0Sstevel@tonic-gate ret2: 2615*0Sstevel@tonic-gate if (t2.malloced) big_finish(&t2); 2616*0Sstevel@tonic-gate ret1: 2617*0Sstevel@tonic-gate if (t1.malloced) big_finish(&t1); 2618*0Sstevel@tonic-gate 2619*0Sstevel@tonic-gate return (err); 2620*0Sstevel@tonic-gate } 2621