17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5b60f2a0bSfr41279 * Common Development and Distribution License (the "License").
6b60f2a0bSfr41279 * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
21726fad2aSDina K Nimeh
227c478bd9Sstevel@tonic-gate /*
23726fad2aSDina K Nimeh * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
247c478bd9Sstevel@tonic-gate */
257c478bd9Sstevel@tonic-gate
267c478bd9Sstevel@tonic-gate /*
277c478bd9Sstevel@tonic-gate * Configuration guide
287c478bd9Sstevel@tonic-gate * -------------------
297c478bd9Sstevel@tonic-gate *
307c478bd9Sstevel@tonic-gate * There are 4 preprocessor symbols used to configure the bignum
317c478bd9Sstevel@tonic-gate * implementation. This file contains no logic to configure based on
327c478bd9Sstevel@tonic-gate * processor; we leave that to the Makefiles to specify.
337c478bd9Sstevel@tonic-gate *
347c478bd9Sstevel@tonic-gate * USE_FLOATING_POINT
357c478bd9Sstevel@tonic-gate * Meaning: There is support for a fast floating-point implementation of
367c478bd9Sstevel@tonic-gate * Montgomery multiply.
377c478bd9Sstevel@tonic-gate *
387c478bd9Sstevel@tonic-gate * PSR_MUL
397c478bd9Sstevel@tonic-gate * Meaning: There are processor-specific versions of the low level
407c478bd9Sstevel@tonic-gate * functions to implement big_mul. Those functions are: big_mul_set_vec,
417c478bd9Sstevel@tonic-gate * big_mul_add_vec, big_mul_vec, and big_sqr_vec. PSR_MUL implies support
427c478bd9Sstevel@tonic-gate * for all 4 functions. You cannot pick and choose which subset of these
437c478bd9Sstevel@tonic-gate * functions to support; that would lead to a rat's nest of #ifdefs.
447c478bd9Sstevel@tonic-gate *
457c478bd9Sstevel@tonic-gate * HWCAP
467c478bd9Sstevel@tonic-gate * Meaning: Call multiply support functions through a function pointer.
478475e043SDan OpenSolaris Anderson * On x86, there are multiple implementations for different hardware
487c478bd9Sstevel@tonic-gate * capabilities, such as MMX, SSE2, etc. Tests are made at run-time, when
497c478bd9Sstevel@tonic-gate * a function is first used. So, the support functions are called through
507c478bd9Sstevel@tonic-gate * a function pointer. There is no need for that on Sparc, because there
517c478bd9Sstevel@tonic-gate * is only one implementation; support functions are called directly.
527c478bd9Sstevel@tonic-gate * Later, if there were some new VIS instruction, or something, and a
537c478bd9Sstevel@tonic-gate * run-time test were needed, rather than variant kernel modules and
547c478bd9Sstevel@tonic-gate * libraries, then HWCAP would be defined for Sparc, as well.
557c478bd9Sstevel@tonic-gate *
567c478bd9Sstevel@tonic-gate * UMUL64
577c478bd9Sstevel@tonic-gate * Meaning: It is safe to use generic C code that assumes the existence
587c478bd9Sstevel@tonic-gate * of a 32 x 32 --> 64 bit unsigned multiply. If this is not defined,
597c478bd9Sstevel@tonic-gate * then the generic code for big_mul_add_vec() must necessarily be very slow,
607c478bd9Sstevel@tonic-gate * because it must fall back to using 16 x 16 --> 32 bit multiplication.
617c478bd9Sstevel@tonic-gate *
627c478bd9Sstevel@tonic-gate */
637c478bd9Sstevel@tonic-gate
647c478bd9Sstevel@tonic-gate
658475e043SDan OpenSolaris Anderson #include <sys/types.h>
668475e043SDan OpenSolaris Anderson #include "bignum.h"
678475e043SDan OpenSolaris Anderson
687c478bd9Sstevel@tonic-gate #ifdef _KERNEL
69b60f2a0bSfr41279 #include <sys/ddi.h>
70b60f2a0bSfr41279 #include <sys/mdesc.h>
71b60f2a0bSfr41279 #include <sys/crypto/common.h>
727c478bd9Sstevel@tonic-gate
737c478bd9Sstevel@tonic-gate #include <sys/kmem.h>
747c478bd9Sstevel@tonic-gate #include <sys/param.h>
757c478bd9Sstevel@tonic-gate #include <sys/sunddi.h>
767c478bd9Sstevel@tonic-gate
778475e043SDan OpenSolaris Anderson #else
788475e043SDan OpenSolaris Anderson #include <stdlib.h>
798475e043SDan OpenSolaris Anderson #include <stdio.h>
808475e043SDan OpenSolaris Anderson #include <assert.h>
818475e043SDan OpenSolaris Anderson #define ASSERT assert
828475e043SDan OpenSolaris Anderson #endif /* _KERNEL */
838475e043SDan OpenSolaris Anderson
840a1ad920SDan OpenSolaris Anderson #ifdef __amd64
850a1ad920SDan OpenSolaris Anderson #ifdef _KERNEL
860a1ad920SDan OpenSolaris Anderson #include <sys/x86_archext.h> /* cpuid_getvendor() */
870a1ad920SDan OpenSolaris Anderson #include <sys/cpuvar.h>
880a1ad920SDan OpenSolaris Anderson #else
890a1ad920SDan OpenSolaris Anderson #include <sys/auxv.h> /* getisax() */
900a1ad920SDan OpenSolaris Anderson #endif /* _KERNEL */
910a1ad920SDan OpenSolaris Anderson #endif /* __amd64 */
920a1ad920SDan OpenSolaris Anderson
930a1ad920SDan OpenSolaris Anderson
948475e043SDan OpenSolaris Anderson #ifdef _LP64 /* truncate 64-bit size_t to 32-bits */
958475e043SDan OpenSolaris Anderson #define UI32(ui) ((uint32_t)ui)
968475e043SDan OpenSolaris Anderson #else /* size_t already 32-bits */
978475e043SDan OpenSolaris Anderson #define UI32(ui) (ui)
988475e043SDan OpenSolaris Anderson #endif
998475e043SDan OpenSolaris Anderson
1008475e043SDan OpenSolaris Anderson
1018475e043SDan OpenSolaris Anderson #ifdef _KERNEL
1027c478bd9Sstevel@tonic-gate #define big_malloc(size) kmem_alloc(size, KM_NOSLEEP)
1037c478bd9Sstevel@tonic-gate #define big_free(ptr, size) kmem_free(ptr, size)
1047c478bd9Sstevel@tonic-gate
1050a1ad920SDan OpenSolaris Anderson /*
1060a1ad920SDan OpenSolaris Anderson * big_realloc()
1070a1ad920SDan OpenSolaris Anderson * Allocate memory of newsize bytes and copy oldsize bytes
1080a1ad920SDan OpenSolaris Anderson * to the newly-allocated memory, then free the
1090a1ad920SDan OpenSolaris Anderson * previously-allocated memory.
1100a1ad920SDan OpenSolaris Anderson * Note: newsize must be > oldsize
1110a1ad920SDan OpenSolaris Anderson */
1127c478bd9Sstevel@tonic-gate void *
big_realloc(void * from,size_t oldsize,size_t newsize)1137c478bd9Sstevel@tonic-gate big_realloc(void *from, size_t oldsize, size_t newsize)
1147c478bd9Sstevel@tonic-gate {
1157c478bd9Sstevel@tonic-gate void *rv;
1167c478bd9Sstevel@tonic-gate
1177c478bd9Sstevel@tonic-gate rv = kmem_alloc(newsize, KM_NOSLEEP);
1187c478bd9Sstevel@tonic-gate if (rv != NULL)
1197c478bd9Sstevel@tonic-gate bcopy(from, rv, oldsize);
1207c478bd9Sstevel@tonic-gate kmem_free(from, oldsize);
1217c478bd9Sstevel@tonic-gate return (rv);
1227c478bd9Sstevel@tonic-gate }
1237c478bd9Sstevel@tonic-gate
1247c478bd9Sstevel@tonic-gate #else /* _KERNEL */
1257c478bd9Sstevel@tonic-gate
1267c478bd9Sstevel@tonic-gate #ifndef MALLOC_DEBUG
1277c478bd9Sstevel@tonic-gate
1287c478bd9Sstevel@tonic-gate #define big_malloc(size) malloc(size)
1297c478bd9Sstevel@tonic-gate #define big_free(ptr, size) free(ptr)
1307c478bd9Sstevel@tonic-gate
1317c478bd9Sstevel@tonic-gate #else
1327c478bd9Sstevel@tonic-gate
1337c478bd9Sstevel@tonic-gate void
big_free(void * ptr,size_t size)1347c478bd9Sstevel@tonic-gate big_free(void *ptr, size_t size)
1357c478bd9Sstevel@tonic-gate {
1367c478bd9Sstevel@tonic-gate printf("freed %d bytes at %p\n", size, ptr);
1377c478bd9Sstevel@tonic-gate free(ptr);
1387c478bd9Sstevel@tonic-gate }
1397c478bd9Sstevel@tonic-gate
1407c478bd9Sstevel@tonic-gate void *
big_malloc(size_t size)1417c478bd9Sstevel@tonic-gate big_malloc(size_t size)
1427c478bd9Sstevel@tonic-gate {
1437c478bd9Sstevel@tonic-gate void *rv;
1447c478bd9Sstevel@tonic-gate rv = malloc(size);
1457c478bd9Sstevel@tonic-gate printf("malloced %d bytes, addr:%p\n", size, rv);
1467c478bd9Sstevel@tonic-gate return (rv);
1477c478bd9Sstevel@tonic-gate }
1487c478bd9Sstevel@tonic-gate #endif /* MALLOC_DEBUG */
1497c478bd9Sstevel@tonic-gate
1507c478bd9Sstevel@tonic-gate #define big_realloc(x, y, z) realloc((x), (z))
1517c478bd9Sstevel@tonic-gate
1528475e043SDan OpenSolaris Anderson
1538475e043SDan OpenSolaris Anderson /*
1548475e043SDan OpenSolaris Anderson * printbignum()
1558475e043SDan OpenSolaris Anderson * Print a BIGNUM type to stdout.
1568475e043SDan OpenSolaris Anderson */
1577c478bd9Sstevel@tonic-gate void
printbignum(char * aname,BIGNUM * a)1587c478bd9Sstevel@tonic-gate printbignum(char *aname, BIGNUM *a)
1597c478bd9Sstevel@tonic-gate {
1607c478bd9Sstevel@tonic-gate int i;
1617c478bd9Sstevel@tonic-gate
1627c478bd9Sstevel@tonic-gate (void) printf("\n%s\n%d\n", aname, a->sign*a->len);
1637c478bd9Sstevel@tonic-gate for (i = a->len - 1; i >= 0; i--) {
164b60f2a0bSfr41279 #ifdef BIGNUM_CHUNK_32
1657c478bd9Sstevel@tonic-gate (void) printf("%08x ", a->value[i]);
1668475e043SDan OpenSolaris Anderson if (((i & (BITSINBYTE - 1)) == 0) && (i != 0)) {
1677c478bd9Sstevel@tonic-gate (void) printf("\n");
1687c478bd9Sstevel@tonic-gate }
169b60f2a0bSfr41279 #else
170b60f2a0bSfr41279 (void) printf("%08x %08x ", (uint32_t)((a->value[i]) >> 32),
171b60f2a0bSfr41279 (uint32_t)((a->value[i]) & 0xffffffff));
1728475e043SDan OpenSolaris Anderson if (((i & 3) == 0) && (i != 0)) { /* end of this chunk */
173b60f2a0bSfr41279 (void) printf("\n");
174b60f2a0bSfr41279 }
175b60f2a0bSfr41279 #endif
176b60f2a0bSfr41279 }
1777c478bd9Sstevel@tonic-gate (void) printf("\n");
1787c478bd9Sstevel@tonic-gate }
1797c478bd9Sstevel@tonic-gate
1807c478bd9Sstevel@tonic-gate #endif /* _KERNEL */
1817c478bd9Sstevel@tonic-gate
1827c478bd9Sstevel@tonic-gate
1830a1ad920SDan OpenSolaris Anderson #ifdef __amd64
1840a1ad920SDan OpenSolaris Anderson /*
1850a1ad920SDan OpenSolaris Anderson * Return 1 if executing on Intel, otherwise 0 (e.g., AMD64).
1868de5c4f4SDan OpenSolaris Anderson * Cache the result, as the CPU can't change.
1878de5c4f4SDan OpenSolaris Anderson *
1888de5c4f4SDan OpenSolaris Anderson * Note: the userland version uses getisax() and checks for an AMD-64-only
1898de5c4f4SDan OpenSolaris Anderson * feature. The kernel version uses cpuid_getvendor().
1900a1ad920SDan OpenSolaris Anderson */
1910a1ad920SDan OpenSolaris Anderson static int
bignum_on_intel(void)1920a1ad920SDan OpenSolaris Anderson bignum_on_intel(void)
1930a1ad920SDan OpenSolaris Anderson {
1948de5c4f4SDan OpenSolaris Anderson static int cached_result = -1;
1958de5c4f4SDan OpenSolaris Anderson
1968de5c4f4SDan OpenSolaris Anderson if (cached_result == -1) { /* first time */
1970a1ad920SDan OpenSolaris Anderson #ifdef _KERNEL
1988de5c4f4SDan OpenSolaris Anderson cached_result = (cpuid_getvendor(CPU) == X86_VENDOR_Intel);
1990a1ad920SDan OpenSolaris Anderson #else
2000a1ad920SDan OpenSolaris Anderson uint_t ui;
2018de5c4f4SDan OpenSolaris Anderson
2020a1ad920SDan OpenSolaris Anderson (void) getisax(&ui, 1);
2038de5c4f4SDan OpenSolaris Anderson cached_result = ((ui & AV_386_AMD_MMX) == 0);
2040a1ad920SDan OpenSolaris Anderson #endif /* _KERNEL */
2050a1ad920SDan OpenSolaris Anderson }
2068de5c4f4SDan OpenSolaris Anderson
2078de5c4f4SDan OpenSolaris Anderson return (cached_result);
2088de5c4f4SDan OpenSolaris Anderson }
2090a1ad920SDan OpenSolaris Anderson #endif /* __amd64 */
2100a1ad920SDan OpenSolaris Anderson
2110a1ad920SDan OpenSolaris Anderson
2128475e043SDan OpenSolaris Anderson /*
2138475e043SDan OpenSolaris Anderson * big_init()
2148475e043SDan OpenSolaris Anderson * Initialize and allocate memory for a BIGNUM type.
2158475e043SDan OpenSolaris Anderson *
2168475e043SDan OpenSolaris Anderson * big_init(number, size) is equivalent to big_init1(number, size, NULL, 0)
2178475e043SDan OpenSolaris Anderson *
2188475e043SDan OpenSolaris Anderson * Note: call big_finish() to free memory allocated by big_init().
2198475e043SDan OpenSolaris Anderson *
2208475e043SDan OpenSolaris Anderson * Input:
2218475e043SDan OpenSolaris Anderson * number Uninitialized memory for BIGNUM
2228475e043SDan OpenSolaris Anderson * size Minimum size, in BIG_CHUNK_SIZE-bit words, required for BIGNUM
2238475e043SDan OpenSolaris Anderson *
2248475e043SDan OpenSolaris Anderson * Output:
2258475e043SDan OpenSolaris Anderson * number Initialized BIGNUM
2268475e043SDan OpenSolaris Anderson *
2278475e043SDan OpenSolaris Anderson * Return BIG_OK on success or BIG_NO_MEM for an allocation error.
2288475e043SDan OpenSolaris Anderson */
2297c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_init(BIGNUM * number,int size)2307c478bd9Sstevel@tonic-gate big_init(BIGNUM *number, int size)
2317c478bd9Sstevel@tonic-gate {
2328475e043SDan OpenSolaris Anderson number->value = big_malloc(BIGNUM_WORDSIZE * size);
2337c478bd9Sstevel@tonic-gate if (number->value == NULL) {
2347c478bd9Sstevel@tonic-gate return (BIG_NO_MEM);
2357c478bd9Sstevel@tonic-gate }
2367c478bd9Sstevel@tonic-gate number->size = size;
2377c478bd9Sstevel@tonic-gate number->len = 0;
2387c478bd9Sstevel@tonic-gate number->sign = 1;
2397c478bd9Sstevel@tonic-gate number->malloced = 1;
2407c478bd9Sstevel@tonic-gate return (BIG_OK);
2417c478bd9Sstevel@tonic-gate }
2427c478bd9Sstevel@tonic-gate
2438475e043SDan OpenSolaris Anderson
2448475e043SDan OpenSolaris Anderson /*
2458475e043SDan OpenSolaris Anderson * big_init1()
2468475e043SDan OpenSolaris Anderson * Initialize and, if needed, allocate memory for a BIGNUM type.
2478475e043SDan OpenSolaris Anderson * Use the buffer passed, buf, if any, instad of allocating memory
2488475e043SDan OpenSolaris Anderson * if it's at least "size" bytes.
2498475e043SDan OpenSolaris Anderson *
2508475e043SDan OpenSolaris Anderson * Note: call big_finish() to free memory allocated by big_init().
2518475e043SDan OpenSolaris Anderson *
2528475e043SDan OpenSolaris Anderson * Input:
2538475e043SDan OpenSolaris Anderson * number Uninitialized memory for BIGNUM
2548475e043SDan OpenSolaris Anderson * size Minimum size, in BIG_CHUNK_SIZE-bit words, required for BIGNUM
2558475e043SDan OpenSolaris Anderson * buf Buffer for storing a BIGNUM.
2568475e043SDan OpenSolaris Anderson * If NULL, big_init1() will allocate a buffer
2578475e043SDan OpenSolaris Anderson * bufsize Size, in BIG_CHUNK_SIZE_bit words, of buf
2588475e043SDan OpenSolaris Anderson *
2598475e043SDan OpenSolaris Anderson * Output:
2608475e043SDan OpenSolaris Anderson * number Initialized BIGNUM
2618475e043SDan OpenSolaris Anderson *
2628475e043SDan OpenSolaris Anderson * Return BIG_OK on success or BIG_NO_MEM for an allocation error.
2638475e043SDan OpenSolaris Anderson */
2647c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_init1(BIGNUM * number,int size,BIG_CHUNK_TYPE * buf,int bufsize)265b60f2a0bSfr41279 big_init1(BIGNUM *number, int size, BIG_CHUNK_TYPE *buf, int bufsize)
2667c478bd9Sstevel@tonic-gate {
2677c478bd9Sstevel@tonic-gate if ((buf == NULL) || (size > bufsize)) {
2688475e043SDan OpenSolaris Anderson number->value = big_malloc(BIGNUM_WORDSIZE * size);
2697c478bd9Sstevel@tonic-gate if (number->value == NULL) {
2707c478bd9Sstevel@tonic-gate return (BIG_NO_MEM);
2717c478bd9Sstevel@tonic-gate }
2727c478bd9Sstevel@tonic-gate number->size = size;
2737c478bd9Sstevel@tonic-gate number->malloced = 1;
2747c478bd9Sstevel@tonic-gate } else {
2757c478bd9Sstevel@tonic-gate number->value = buf;
2767c478bd9Sstevel@tonic-gate number->size = bufsize;
2777c478bd9Sstevel@tonic-gate number->malloced = 0;
2787c478bd9Sstevel@tonic-gate }
2797c478bd9Sstevel@tonic-gate number->len = 0;
2807c478bd9Sstevel@tonic-gate number->sign = 1;
2817c478bd9Sstevel@tonic-gate
2827c478bd9Sstevel@tonic-gate return (BIG_OK);
2837c478bd9Sstevel@tonic-gate }
2847c478bd9Sstevel@tonic-gate
2858475e043SDan OpenSolaris Anderson
2868475e043SDan OpenSolaris Anderson /*
2878475e043SDan OpenSolaris Anderson * big_finish()
2888475e043SDan OpenSolaris Anderson * Free memory, if any, allocated by big_init() or big_init1().
2898475e043SDan OpenSolaris Anderson */
2907c478bd9Sstevel@tonic-gate void
big_finish(BIGNUM * number)2917c478bd9Sstevel@tonic-gate big_finish(BIGNUM *number)
2927c478bd9Sstevel@tonic-gate {
2937c478bd9Sstevel@tonic-gate if (number->malloced == 1) {
2948475e043SDan OpenSolaris Anderson big_free(number->value, BIGNUM_WORDSIZE * number->size);
2957c478bd9Sstevel@tonic-gate number->malloced = 0;
2967c478bd9Sstevel@tonic-gate }
2977c478bd9Sstevel@tonic-gate }
2987c478bd9Sstevel@tonic-gate
299b60f2a0bSfr41279
3007c478bd9Sstevel@tonic-gate /*
301b60f2a0bSfr41279 * bn->size should be at least
3028475e043SDan OpenSolaris Anderson * (len + BIGNUM_WORDSIZE - 1) / BIGNUM_WORDSIZE bytes
3037c478bd9Sstevel@tonic-gate * converts from byte-big-endian format to bignum format (words in
3047c478bd9Sstevel@tonic-gate * little endian order, but bytes within the words big endian)
3057c478bd9Sstevel@tonic-gate */
3067c478bd9Sstevel@tonic-gate void
bytestring2bignum(BIGNUM * bn,uchar_t * kn,size_t len)3077c478bd9Sstevel@tonic-gate bytestring2bignum(BIGNUM *bn, uchar_t *kn, size_t len)
3087c478bd9Sstevel@tonic-gate {
3098475e043SDan OpenSolaris Anderson int i, j;
3108475e043SDan OpenSolaris Anderson uint32_t offs;
3118475e043SDan OpenSolaris Anderson const uint32_t slen = UI32(len);
312b60f2a0bSfr41279 BIG_CHUNK_TYPE word;
3137c478bd9Sstevel@tonic-gate uchar_t *knwordp;
3147c478bd9Sstevel@tonic-gate
3158475e043SDan OpenSolaris Anderson if (slen == 0) {
3168475e043SDan OpenSolaris Anderson bn->len = 1;
3178475e043SDan OpenSolaris Anderson bn->value[0] = 0;
3188475e043SDan OpenSolaris Anderson return;
3198475e043SDan OpenSolaris Anderson }
320b60f2a0bSfr41279
3218475e043SDan OpenSolaris Anderson offs = slen % BIGNUM_WORDSIZE;
3228475e043SDan OpenSolaris Anderson bn->len = slen / BIGNUM_WORDSIZE;
3238475e043SDan OpenSolaris Anderson
3248475e043SDan OpenSolaris Anderson for (i = 0; i < slen / BIGNUM_WORDSIZE; i++) {
3258475e043SDan OpenSolaris Anderson knwordp = &(kn[slen - BIGNUM_WORDSIZE * (i + 1)]);
3267c478bd9Sstevel@tonic-gate word = knwordp[0];
3278475e043SDan OpenSolaris Anderson for (j = 1; j < BIGNUM_WORDSIZE; j++) {
3288475e043SDan OpenSolaris Anderson word = (word << BITSINBYTE) + knwordp[j];
3297c478bd9Sstevel@tonic-gate }
3307c478bd9Sstevel@tonic-gate bn->value[i] = word;
3317c478bd9Sstevel@tonic-gate }
3327c478bd9Sstevel@tonic-gate if (offs > 0) {
3337c478bd9Sstevel@tonic-gate word = kn[0];
3348475e043SDan OpenSolaris Anderson for (i = 1; i < offs; i++) word = (word << BITSINBYTE) + kn[i];
3357c478bd9Sstevel@tonic-gate bn->value[bn->len++] = word;
3367c478bd9Sstevel@tonic-gate }
3377c478bd9Sstevel@tonic-gate while ((bn->len > 1) && (bn->value[bn->len - 1] == 0)) {
3387c478bd9Sstevel@tonic-gate bn->len --;
3397c478bd9Sstevel@tonic-gate }
3407c478bd9Sstevel@tonic-gate }
3417c478bd9Sstevel@tonic-gate
3428475e043SDan OpenSolaris Anderson
3437c478bd9Sstevel@tonic-gate /*
3447c478bd9Sstevel@tonic-gate * copies the least significant len bytes if
3458475e043SDan OpenSolaris Anderson * len < bn->len * BIGNUM_WORDSIZE
3467c478bd9Sstevel@tonic-gate * converts from bignum format to byte-big-endian format.
347b60f2a0bSfr41279 * bignum format is words of type BIG_CHUNK_TYPE in little endian order.
3487c478bd9Sstevel@tonic-gate */
3497c478bd9Sstevel@tonic-gate void
bignum2bytestring(uchar_t * kn,BIGNUM * bn,size_t len)3507c478bd9Sstevel@tonic-gate bignum2bytestring(uchar_t *kn, BIGNUM *bn, size_t len)
3517c478bd9Sstevel@tonic-gate {
3528475e043SDan OpenSolaris Anderson int i, j;
3538475e043SDan OpenSolaris Anderson uint32_t offs;
3548475e043SDan OpenSolaris Anderson const uint32_t slen = UI32(len);
355b60f2a0bSfr41279 BIG_CHUNK_TYPE word;
3567c478bd9Sstevel@tonic-gate
3578475e043SDan OpenSolaris Anderson if (len < BIGNUM_WORDSIZE * bn->len) {
3588475e043SDan OpenSolaris Anderson for (i = 0; i < slen / BIGNUM_WORDSIZE; i++) {
3597c478bd9Sstevel@tonic-gate word = bn->value[i];
3608475e043SDan OpenSolaris Anderson for (j = 0; j < BIGNUM_WORDSIZE; j++) {
3618475e043SDan OpenSolaris Anderson kn[slen - BIGNUM_WORDSIZE * i - j - 1] =
3627c478bd9Sstevel@tonic-gate word & 0xff;
3638475e043SDan OpenSolaris Anderson word = word >> BITSINBYTE;
3647c478bd9Sstevel@tonic-gate }
3657c478bd9Sstevel@tonic-gate }
3668475e043SDan OpenSolaris Anderson offs = slen % BIGNUM_WORDSIZE;
3677c478bd9Sstevel@tonic-gate if (offs > 0) {
3688475e043SDan OpenSolaris Anderson word = bn->value[slen / BIGNUM_WORDSIZE];
3698475e043SDan OpenSolaris Anderson for (i = slen % BIGNUM_WORDSIZE; i > 0; i --) {
3707c478bd9Sstevel@tonic-gate kn[i - 1] = word & 0xff;
3718475e043SDan OpenSolaris Anderson word = word >> BITSINBYTE;
3727c478bd9Sstevel@tonic-gate }
3737c478bd9Sstevel@tonic-gate }
3747c478bd9Sstevel@tonic-gate } else {
3757c478bd9Sstevel@tonic-gate for (i = 0; i < bn->len; i++) {
3767c478bd9Sstevel@tonic-gate word = bn->value[i];
3778475e043SDan OpenSolaris Anderson for (j = 0; j < BIGNUM_WORDSIZE; j++) {
3788475e043SDan OpenSolaris Anderson kn[slen - BIGNUM_WORDSIZE * i - j - 1] =
3797c478bd9Sstevel@tonic-gate word & 0xff;
3808475e043SDan OpenSolaris Anderson word = word >> BITSINBYTE;
3817c478bd9Sstevel@tonic-gate }
3827c478bd9Sstevel@tonic-gate }
3838475e043SDan OpenSolaris Anderson for (i = 0; i < slen - BIGNUM_WORDSIZE * bn->len; i++) {
3847c478bd9Sstevel@tonic-gate kn[i] = 0;
3857c478bd9Sstevel@tonic-gate }
3867c478bd9Sstevel@tonic-gate }
3877c478bd9Sstevel@tonic-gate }
3887c478bd9Sstevel@tonic-gate
3897c478bd9Sstevel@tonic-gate
3907c478bd9Sstevel@tonic-gate int
big_bitlength(BIGNUM * a)3917c478bd9Sstevel@tonic-gate big_bitlength(BIGNUM *a)
3927c478bd9Sstevel@tonic-gate {
393b60f2a0bSfr41279 int l = 0, b = 0;
394b60f2a0bSfr41279 BIG_CHUNK_TYPE c;
3957c478bd9Sstevel@tonic-gate
3967c478bd9Sstevel@tonic-gate l = a->len - 1;
3977c478bd9Sstevel@tonic-gate while ((l > 0) && (a->value[l] == 0)) {
3987c478bd9Sstevel@tonic-gate l--;
3997c478bd9Sstevel@tonic-gate }
4008475e043SDan OpenSolaris Anderson b = BIG_CHUNK_SIZE;
4017c478bd9Sstevel@tonic-gate c = a->value[l];
402b60f2a0bSfr41279 while ((b > 1) && ((c & BIG_CHUNK_HIGHBIT) == 0)) {
4037c478bd9Sstevel@tonic-gate c = c << 1;
4047c478bd9Sstevel@tonic-gate b--;
4057c478bd9Sstevel@tonic-gate }
406b60f2a0bSfr41279
4078475e043SDan OpenSolaris Anderson return (l * BIG_CHUNK_SIZE + b);
4087c478bd9Sstevel@tonic-gate }
4097c478bd9Sstevel@tonic-gate
4107c478bd9Sstevel@tonic-gate
4110a1ad920SDan OpenSolaris Anderson /*
4120a1ad920SDan OpenSolaris Anderson * big_copy()
4130a1ad920SDan OpenSolaris Anderson * Copy BIGNUM src to dest, allocating memory if needed.
4140a1ad920SDan OpenSolaris Anderson */
4157c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_copy(BIGNUM * dest,BIGNUM * src)4167c478bd9Sstevel@tonic-gate big_copy(BIGNUM *dest, BIGNUM *src)
4177c478bd9Sstevel@tonic-gate {
418b60f2a0bSfr41279 BIG_CHUNK_TYPE *newptr;
4197c478bd9Sstevel@tonic-gate int i, len;
4207c478bd9Sstevel@tonic-gate
4217c478bd9Sstevel@tonic-gate len = src->len;
422b60f2a0bSfr41279 while ((len > 1) && (src->value[len - 1] == 0)) {
4237c478bd9Sstevel@tonic-gate len--;
424b60f2a0bSfr41279 }
4257c478bd9Sstevel@tonic-gate src->len = len;
4267c478bd9Sstevel@tonic-gate if (dest->size < len) {
4277c478bd9Sstevel@tonic-gate if (dest->malloced == 1) {
428b60f2a0bSfr41279 newptr = (BIG_CHUNK_TYPE *)big_realloc(dest->value,
4298475e043SDan OpenSolaris Anderson BIGNUM_WORDSIZE * dest->size,
4308475e043SDan OpenSolaris Anderson BIGNUM_WORDSIZE * len);
4317c478bd9Sstevel@tonic-gate } else {
432b60f2a0bSfr41279 newptr = (BIG_CHUNK_TYPE *)
4338475e043SDan OpenSolaris Anderson big_malloc(BIGNUM_WORDSIZE * len);
434b60f2a0bSfr41279 if (newptr != NULL) {
435b60f2a0bSfr41279 dest->malloced = 1;
4367c478bd9Sstevel@tonic-gate }
437b60f2a0bSfr41279 }
438b60f2a0bSfr41279 if (newptr == NULL) {
4397c478bd9Sstevel@tonic-gate return (BIG_NO_MEM);
440b60f2a0bSfr41279 }
4417c478bd9Sstevel@tonic-gate dest->value = newptr;
4427c478bd9Sstevel@tonic-gate dest->size = len;
4437c478bd9Sstevel@tonic-gate }
4447c478bd9Sstevel@tonic-gate dest->len = len;
4457c478bd9Sstevel@tonic-gate dest->sign = src->sign;
446b60f2a0bSfr41279 for (i = 0; i < len; i++) {
447b60f2a0bSfr41279 dest->value[i] = src->value[i];
448b60f2a0bSfr41279 }
4497c478bd9Sstevel@tonic-gate
4507c478bd9Sstevel@tonic-gate return (BIG_OK);
4517c478bd9Sstevel@tonic-gate }
4527c478bd9Sstevel@tonic-gate
4537c478bd9Sstevel@tonic-gate
4540a1ad920SDan OpenSolaris Anderson /*
4550a1ad920SDan OpenSolaris Anderson * big_extend()
4560a1ad920SDan OpenSolaris Anderson * Allocate memory to extend BIGNUM number to size bignum chunks,
4570a1ad920SDan OpenSolaris Anderson * if not at least that size already.
4580a1ad920SDan OpenSolaris Anderson */
4597c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_extend(BIGNUM * number,int size)4607c478bd9Sstevel@tonic-gate big_extend(BIGNUM *number, int size)
4617c478bd9Sstevel@tonic-gate {
462b60f2a0bSfr41279 BIG_CHUNK_TYPE *newptr;
4637c478bd9Sstevel@tonic-gate int i;
4647c478bd9Sstevel@tonic-gate
4657c478bd9Sstevel@tonic-gate if (number->size >= size)
4667c478bd9Sstevel@tonic-gate return (BIG_OK);
4677c478bd9Sstevel@tonic-gate if (number->malloced) {
468b60f2a0bSfr41279 number->value = big_realloc(number->value,
4698475e043SDan OpenSolaris Anderson BIGNUM_WORDSIZE * number->size,
4708475e043SDan OpenSolaris Anderson BIGNUM_WORDSIZE * size);
4717c478bd9Sstevel@tonic-gate } else {
4728475e043SDan OpenSolaris Anderson newptr = big_malloc(BIGNUM_WORDSIZE * size);
4737c478bd9Sstevel@tonic-gate if (newptr != NULL) {
4747c478bd9Sstevel@tonic-gate for (i = 0; i < number->size; i++) {
4757c478bd9Sstevel@tonic-gate newptr[i] = number->value[i];
4767c478bd9Sstevel@tonic-gate }
4777c478bd9Sstevel@tonic-gate }
4787c478bd9Sstevel@tonic-gate number->value = newptr;
4797c478bd9Sstevel@tonic-gate }
4807c478bd9Sstevel@tonic-gate
481b60f2a0bSfr41279 if (number->value == NULL) {
4827c478bd9Sstevel@tonic-gate return (BIG_NO_MEM);
483b60f2a0bSfr41279 }
4847c478bd9Sstevel@tonic-gate
4857c478bd9Sstevel@tonic-gate number->size = size;
4867c478bd9Sstevel@tonic-gate number->malloced = 1;
4877c478bd9Sstevel@tonic-gate return (BIG_OK);
4887c478bd9Sstevel@tonic-gate }
4897c478bd9Sstevel@tonic-gate
4907c478bd9Sstevel@tonic-gate
491b60f2a0bSfr41279 /* returns 1 if n == 0 */
4927c478bd9Sstevel@tonic-gate int
big_is_zero(BIGNUM * n)4937c478bd9Sstevel@tonic-gate big_is_zero(BIGNUM *n)
4947c478bd9Sstevel@tonic-gate {
4957c478bd9Sstevel@tonic-gate int i, result;
4967c478bd9Sstevel@tonic-gate
4977c478bd9Sstevel@tonic-gate result = 1;
498b60f2a0bSfr41279 for (i = 0; i < n->len; i++) {
499b60f2a0bSfr41279 if (n->value[i] != 0) {
500b60f2a0bSfr41279 result = 0;
501b60f2a0bSfr41279 }
502b60f2a0bSfr41279 }
5037c478bd9Sstevel@tonic-gate return (result);
5047c478bd9Sstevel@tonic-gate }
5057c478bd9Sstevel@tonic-gate
5067c478bd9Sstevel@tonic-gate
5077c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_add_abs(BIGNUM * result,BIGNUM * aa,BIGNUM * bb)5087c478bd9Sstevel@tonic-gate big_add_abs(BIGNUM *result, BIGNUM *aa, BIGNUM *bb)
5097c478bd9Sstevel@tonic-gate {
5107c478bd9Sstevel@tonic-gate int i, shorter, longer;
511b60f2a0bSfr41279 BIG_CHUNK_TYPE cy, ai;
512b60f2a0bSfr41279 BIG_CHUNK_TYPE *r, *a, *b, *c;
5137c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
514b60f2a0bSfr41279 BIGNUM *longerarg;
5157c478bd9Sstevel@tonic-gate
5167c478bd9Sstevel@tonic-gate if (aa->len > bb->len) {
5177c478bd9Sstevel@tonic-gate shorter = bb->len;
5187c478bd9Sstevel@tonic-gate longer = aa->len;
519b60f2a0bSfr41279 longerarg = aa;
5207c478bd9Sstevel@tonic-gate } else {
5217c478bd9Sstevel@tonic-gate shorter = aa->len;
5227c478bd9Sstevel@tonic-gate longer = bb->len;
523b60f2a0bSfr41279 longerarg = bb;
5247c478bd9Sstevel@tonic-gate }
5257c478bd9Sstevel@tonic-gate if (result->size < longer + 1) {
5267c478bd9Sstevel@tonic-gate err = big_extend(result, longer + 1);
527b60f2a0bSfr41279 if (err != BIG_OK) {
5287c478bd9Sstevel@tonic-gate return (err);
5297c478bd9Sstevel@tonic-gate }
530b60f2a0bSfr41279 }
5317c478bd9Sstevel@tonic-gate
5327c478bd9Sstevel@tonic-gate r = result->value;
5337c478bd9Sstevel@tonic-gate a = aa->value;
5347c478bd9Sstevel@tonic-gate b = bb->value;
535b60f2a0bSfr41279 c = longerarg->value;
5367c478bd9Sstevel@tonic-gate cy = 0;
5377c478bd9Sstevel@tonic-gate for (i = 0; i < shorter; i++) {
5387c478bd9Sstevel@tonic-gate ai = a[i];
5397c478bd9Sstevel@tonic-gate r[i] = ai + b[i] + cy;
540b60f2a0bSfr41279 if (r[i] > ai) {
541b60f2a0bSfr41279 cy = 0;
542b60f2a0bSfr41279 } else if (r[i] < ai) {
543b60f2a0bSfr41279 cy = 1;
544b60f2a0bSfr41279 }
5457c478bd9Sstevel@tonic-gate }
5467c478bd9Sstevel@tonic-gate for (; i < longer; i++) {
5477c478bd9Sstevel@tonic-gate ai = c[i];
5487c478bd9Sstevel@tonic-gate r[i] = ai + cy;
549b60f2a0bSfr41279 if (r[i] >= ai) {
550b60f2a0bSfr41279 cy = 0;
551b60f2a0bSfr41279 }
5527c478bd9Sstevel@tonic-gate }
5537c478bd9Sstevel@tonic-gate if (cy == 1) {
5547c478bd9Sstevel@tonic-gate r[i] = cy;
5557c478bd9Sstevel@tonic-gate result->len = longer + 1;
5567c478bd9Sstevel@tonic-gate } else {
5577c478bd9Sstevel@tonic-gate result->len = longer;
5587c478bd9Sstevel@tonic-gate }
5597c478bd9Sstevel@tonic-gate result->sign = 1;
5607c478bd9Sstevel@tonic-gate return (BIG_OK);
5617c478bd9Sstevel@tonic-gate }
5627c478bd9Sstevel@tonic-gate
5637c478bd9Sstevel@tonic-gate
5647c478bd9Sstevel@tonic-gate /* caller must make sure that result has at least len words allocated */
5657c478bd9Sstevel@tonic-gate void
big_sub_vec(BIG_CHUNK_TYPE * r,BIG_CHUNK_TYPE * a,BIG_CHUNK_TYPE * b,int len)566b60f2a0bSfr41279 big_sub_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, BIG_CHUNK_TYPE *b, int len)
5677c478bd9Sstevel@tonic-gate {
5687c478bd9Sstevel@tonic-gate int i;
569b60f2a0bSfr41279 BIG_CHUNK_TYPE cy, ai;
5707c478bd9Sstevel@tonic-gate
5717c478bd9Sstevel@tonic-gate cy = 1;
5727c478bd9Sstevel@tonic-gate for (i = 0; i < len; i++) {
5737c478bd9Sstevel@tonic-gate ai = a[i];
5747c478bd9Sstevel@tonic-gate r[i] = ai + (~b[i]) + cy;
575b60f2a0bSfr41279 if (r[i] > ai) {
576b60f2a0bSfr41279 cy = 0;
577b60f2a0bSfr41279 } else if (r[i] < ai) {
578b60f2a0bSfr41279 cy = 1;
579b60f2a0bSfr41279 }
5807c478bd9Sstevel@tonic-gate }
5817c478bd9Sstevel@tonic-gate }
5827c478bd9Sstevel@tonic-gate
5837c478bd9Sstevel@tonic-gate
5847c478bd9Sstevel@tonic-gate /* result=aa-bb it is assumed that aa>=bb */
5857c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_sub_pos(BIGNUM * result,BIGNUM * aa,BIGNUM * bb)5867c478bd9Sstevel@tonic-gate big_sub_pos(BIGNUM *result, BIGNUM *aa, BIGNUM *bb)
5877c478bd9Sstevel@tonic-gate {
5887c478bd9Sstevel@tonic-gate int i, shorter;
589b60f2a0bSfr41279 BIG_CHUNK_TYPE cy = 1, ai;
590b60f2a0bSfr41279 BIG_CHUNK_TYPE *r, *a, *b;
591b60f2a0bSfr41279 BIG_ERR_CODE err = BIG_OK;
5927c478bd9Sstevel@tonic-gate
593b60f2a0bSfr41279 if (aa->len > bb->len) {
594b60f2a0bSfr41279 shorter = bb->len;
595b60f2a0bSfr41279 } else {
596b60f2a0bSfr41279 shorter = aa->len;
597b60f2a0bSfr41279 }
5987c478bd9Sstevel@tonic-gate if (result->size < aa->len) {
5997c478bd9Sstevel@tonic-gate err = big_extend(result, aa->len);
600b60f2a0bSfr41279 if (err != BIG_OK) {
6017c478bd9Sstevel@tonic-gate return (err);
6027c478bd9Sstevel@tonic-gate }
603b60f2a0bSfr41279 }
6047c478bd9Sstevel@tonic-gate
6057c478bd9Sstevel@tonic-gate r = result->value;
6067c478bd9Sstevel@tonic-gate a = aa->value;
6077c478bd9Sstevel@tonic-gate b = bb->value;
6087c478bd9Sstevel@tonic-gate result->len = aa->len;
6097c478bd9Sstevel@tonic-gate cy = 1;
6107c478bd9Sstevel@tonic-gate for (i = 0; i < shorter; i++) {
6117c478bd9Sstevel@tonic-gate ai = a[i];
6127c478bd9Sstevel@tonic-gate r[i] = ai + (~b[i]) + cy;
613b60f2a0bSfr41279 if (r[i] > ai) {
614b60f2a0bSfr41279 cy = 0;
615b60f2a0bSfr41279 } else if (r[i] < ai) {
616b60f2a0bSfr41279 cy = 1;
617b60f2a0bSfr41279 }
6187c478bd9Sstevel@tonic-gate }
6197c478bd9Sstevel@tonic-gate for (; i < aa->len; i++) {
6207c478bd9Sstevel@tonic-gate ai = a[i];
6217c478bd9Sstevel@tonic-gate r[i] = ai + (~0) + cy;
622b60f2a0bSfr41279 if (r[i] < ai) {
623b60f2a0bSfr41279 cy = 1;
624b60f2a0bSfr41279 }
6257c478bd9Sstevel@tonic-gate }
6267c478bd9Sstevel@tonic-gate result->sign = 1;
627b60f2a0bSfr41279
628b60f2a0bSfr41279 if (cy == 0) {
6297c478bd9Sstevel@tonic-gate return (BIG_INVALID_ARGS);
630b60f2a0bSfr41279 } else {
6317c478bd9Sstevel@tonic-gate return (BIG_OK);
6327c478bd9Sstevel@tonic-gate }
633b60f2a0bSfr41279 }
6347c478bd9Sstevel@tonic-gate
6357c478bd9Sstevel@tonic-gate
6367c478bd9Sstevel@tonic-gate /* returns -1 if |aa|<|bb|, 0 if |aa|==|bb| 1 if |aa|>|bb| */
6377c478bd9Sstevel@tonic-gate int
big_cmp_abs(BIGNUM * aa,BIGNUM * bb)6387c478bd9Sstevel@tonic-gate big_cmp_abs(BIGNUM *aa, BIGNUM *bb)
6397c478bd9Sstevel@tonic-gate {
6407c478bd9Sstevel@tonic-gate int i;
6417c478bd9Sstevel@tonic-gate
6427c478bd9Sstevel@tonic-gate if (aa->len > bb->len) {
6437c478bd9Sstevel@tonic-gate for (i = aa->len - 1; i > bb->len - 1; i--) {
644b60f2a0bSfr41279 if (aa->value[i] > 0) {
6457c478bd9Sstevel@tonic-gate return (1);
6467c478bd9Sstevel@tonic-gate }
647b60f2a0bSfr41279 }
6487c478bd9Sstevel@tonic-gate } else if (aa->len < bb->len) {
6497c478bd9Sstevel@tonic-gate for (i = bb->len - 1; i > aa->len - 1; i--) {
650b60f2a0bSfr41279 if (bb->value[i] > 0) {
6517c478bd9Sstevel@tonic-gate return (-1);
6527c478bd9Sstevel@tonic-gate }
653b60f2a0bSfr41279 }
654b60f2a0bSfr41279 } else {
655b60f2a0bSfr41279 i = aa->len - 1;
656b60f2a0bSfr41279 }
6577c478bd9Sstevel@tonic-gate for (; i >= 0; i--) {
658b60f2a0bSfr41279 if (aa->value[i] > bb->value[i]) {
6597c478bd9Sstevel@tonic-gate return (1);
660b60f2a0bSfr41279 } else if (aa->value[i] < bb->value[i]) {
6617c478bd9Sstevel@tonic-gate return (-1);
6627c478bd9Sstevel@tonic-gate }
663b60f2a0bSfr41279 }
6647c478bd9Sstevel@tonic-gate
6657c478bd9Sstevel@tonic-gate return (0);
6667c478bd9Sstevel@tonic-gate }
6677c478bd9Sstevel@tonic-gate
6687c478bd9Sstevel@tonic-gate
6697c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_sub(BIGNUM * result,BIGNUM * aa,BIGNUM * bb)6707c478bd9Sstevel@tonic-gate big_sub(BIGNUM *result, BIGNUM *aa, BIGNUM *bb)
6717c478bd9Sstevel@tonic-gate {
6727c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
6737c478bd9Sstevel@tonic-gate
6747c478bd9Sstevel@tonic-gate if ((bb->sign == -1) && (aa->sign == 1)) {
675b60f2a0bSfr41279 if ((err = big_add_abs(result, aa, bb)) != BIG_OK) {
6767c478bd9Sstevel@tonic-gate return (err);
677b60f2a0bSfr41279 }
6787c478bd9Sstevel@tonic-gate result->sign = 1;
6797c478bd9Sstevel@tonic-gate } else if ((aa->sign == -1) && (bb->sign == 1)) {
680b60f2a0bSfr41279 if ((err = big_add_abs(result, aa, bb)) != BIG_OK) {
6817c478bd9Sstevel@tonic-gate return (err);
682b60f2a0bSfr41279 }
6837c478bd9Sstevel@tonic-gate result->sign = -1;
6847c478bd9Sstevel@tonic-gate } else if ((aa->sign == 1) && (bb->sign == 1)) {
6857c478bd9Sstevel@tonic-gate if (big_cmp_abs(aa, bb) >= 0) {
686b60f2a0bSfr41279 if ((err = big_sub_pos(result, aa, bb)) != BIG_OK) {
6877c478bd9Sstevel@tonic-gate return (err);
688b60f2a0bSfr41279 }
6897c478bd9Sstevel@tonic-gate result->sign = 1;
6907c478bd9Sstevel@tonic-gate } else {
691b60f2a0bSfr41279 if ((err = big_sub_pos(result, bb, aa)) != BIG_OK) {
6927c478bd9Sstevel@tonic-gate return (err);
693b60f2a0bSfr41279 }
6947c478bd9Sstevel@tonic-gate result->sign = -1;
6957c478bd9Sstevel@tonic-gate }
6967c478bd9Sstevel@tonic-gate } else {
6977c478bd9Sstevel@tonic-gate if (big_cmp_abs(aa, bb) >= 0) {
698b60f2a0bSfr41279 if ((err = big_sub_pos(result, aa, bb)) != BIG_OK) {
6997c478bd9Sstevel@tonic-gate return (err);
700b60f2a0bSfr41279 }
7017c478bd9Sstevel@tonic-gate result->sign = -1;
7027c478bd9Sstevel@tonic-gate } else {
703b60f2a0bSfr41279 if ((err = big_sub_pos(result, bb, aa)) != BIG_OK) {
7047c478bd9Sstevel@tonic-gate return (err);
705b60f2a0bSfr41279 }
7067c478bd9Sstevel@tonic-gate result->sign = 1;
7077c478bd9Sstevel@tonic-gate }
7087c478bd9Sstevel@tonic-gate }
7097c478bd9Sstevel@tonic-gate return (BIG_OK);
7107c478bd9Sstevel@tonic-gate }
7117c478bd9Sstevel@tonic-gate
7127c478bd9Sstevel@tonic-gate
7137c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_add(BIGNUM * result,BIGNUM * aa,BIGNUM * bb)7147c478bd9Sstevel@tonic-gate big_add(BIGNUM *result, BIGNUM *aa, BIGNUM *bb)
7157c478bd9Sstevel@tonic-gate {
7167c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
7177c478bd9Sstevel@tonic-gate
7187c478bd9Sstevel@tonic-gate if ((bb->sign == -1) && (aa->sign == -1)) {
719b60f2a0bSfr41279 if ((err = big_add_abs(result, aa, bb)) != BIG_OK) {
7207c478bd9Sstevel@tonic-gate return (err);
721b60f2a0bSfr41279 }
7227c478bd9Sstevel@tonic-gate result->sign = -1;
7237c478bd9Sstevel@tonic-gate } else if ((aa->sign == 1) && (bb->sign == 1)) {
724b60f2a0bSfr41279 if ((err = big_add_abs(result, aa, bb)) != BIG_OK) {
7257c478bd9Sstevel@tonic-gate return (err);
726b60f2a0bSfr41279 }
7277c478bd9Sstevel@tonic-gate result->sign = 1;
7287c478bd9Sstevel@tonic-gate } else if ((aa->sign == 1) && (bb->sign == -1)) {
7297c478bd9Sstevel@tonic-gate if (big_cmp_abs(aa, bb) >= 0) {
730b60f2a0bSfr41279 if ((err = big_sub_pos(result, aa, bb)) != BIG_OK) {
7317c478bd9Sstevel@tonic-gate return (err);
732b60f2a0bSfr41279 }
7337c478bd9Sstevel@tonic-gate result->sign = 1;
7347c478bd9Sstevel@tonic-gate } else {
735b60f2a0bSfr41279 if ((err = big_sub_pos(result, bb, aa)) != BIG_OK) {
7367c478bd9Sstevel@tonic-gate return (err);
737b60f2a0bSfr41279 }
7387c478bd9Sstevel@tonic-gate result->sign = -1;
7397c478bd9Sstevel@tonic-gate }
7407c478bd9Sstevel@tonic-gate } else {
7417c478bd9Sstevel@tonic-gate if (big_cmp_abs(aa, bb) >= 0) {
742b60f2a0bSfr41279 if ((err = big_sub_pos(result, aa, bb)) != BIG_OK) {
7437c478bd9Sstevel@tonic-gate return (err);
744b60f2a0bSfr41279 }
7457c478bd9Sstevel@tonic-gate result->sign = -1;
7467c478bd9Sstevel@tonic-gate } else {
747b60f2a0bSfr41279 if ((err = big_sub_pos(result, bb, aa)) != BIG_OK) {
7487c478bd9Sstevel@tonic-gate return (err);
749b60f2a0bSfr41279 }
7507c478bd9Sstevel@tonic-gate result->sign = 1;
7517c478bd9Sstevel@tonic-gate }
7527c478bd9Sstevel@tonic-gate }
7537c478bd9Sstevel@tonic-gate return (BIG_OK);
7547c478bd9Sstevel@tonic-gate }
7557c478bd9Sstevel@tonic-gate
7567c478bd9Sstevel@tonic-gate
757b60f2a0bSfr41279 /* result = aa/2 */
7587c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_half_pos(BIGNUM * result,BIGNUM * aa)7597c478bd9Sstevel@tonic-gate big_half_pos(BIGNUM *result, BIGNUM *aa)
7607c478bd9Sstevel@tonic-gate {
7617c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
7627c478bd9Sstevel@tonic-gate int i;
763b60f2a0bSfr41279 BIG_CHUNK_TYPE cy, cy1;
764b60f2a0bSfr41279 BIG_CHUNK_TYPE *a, *r;
7657c478bd9Sstevel@tonic-gate
7667c478bd9Sstevel@tonic-gate if (result->size < aa->len) {
7677c478bd9Sstevel@tonic-gate err = big_extend(result, aa->len);
768b60f2a0bSfr41279 if (err != BIG_OK) {
7697c478bd9Sstevel@tonic-gate return (err);
7707c478bd9Sstevel@tonic-gate }
771b60f2a0bSfr41279 }
7727c478bd9Sstevel@tonic-gate
7737c478bd9Sstevel@tonic-gate result->len = aa->len;
7747c478bd9Sstevel@tonic-gate a = aa->value;
7757c478bd9Sstevel@tonic-gate r = result->value;
7767c478bd9Sstevel@tonic-gate cy = 0;
7777c478bd9Sstevel@tonic-gate for (i = aa->len - 1; i >= 0; i--) {
778b60f2a0bSfr41279 cy1 = a[i] << (BIG_CHUNK_SIZE - 1);
7797c478bd9Sstevel@tonic-gate r[i] = (cy | (a[i] >> 1));
7807c478bd9Sstevel@tonic-gate cy = cy1;
7817c478bd9Sstevel@tonic-gate }
782b60f2a0bSfr41279 if (r[result->len - 1] == 0) {
783b60f2a0bSfr41279 result->len--;
784b60f2a0bSfr41279 }
785b60f2a0bSfr41279
7867c478bd9Sstevel@tonic-gate return (BIG_OK);
7877c478bd9Sstevel@tonic-gate }
7887c478bd9Sstevel@tonic-gate
789b60f2a0bSfr41279 /* result = aa*2 */
7907c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_double(BIGNUM * result,BIGNUM * aa)7917c478bd9Sstevel@tonic-gate big_double(BIGNUM *result, BIGNUM *aa)
7927c478bd9Sstevel@tonic-gate {
7937c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
7947c478bd9Sstevel@tonic-gate int i, rsize;
795b60f2a0bSfr41279 BIG_CHUNK_TYPE cy, cy1;
796b60f2a0bSfr41279 BIG_CHUNK_TYPE *a, *r;
7977c478bd9Sstevel@tonic-gate
798b60f2a0bSfr41279 if ((aa->len > 0) &&
799b60f2a0bSfr41279 ((aa->value[aa->len - 1] & BIG_CHUNK_HIGHBIT) != 0)) {
8007c478bd9Sstevel@tonic-gate rsize = aa->len + 1;
801b60f2a0bSfr41279 } else {
802b60f2a0bSfr41279 rsize = aa->len;
803b60f2a0bSfr41279 }
8047c478bd9Sstevel@tonic-gate
8057c478bd9Sstevel@tonic-gate if (result->size < rsize) {
8067c478bd9Sstevel@tonic-gate err = big_extend(result, rsize);
8077c478bd9Sstevel@tonic-gate if (err != BIG_OK)
8087c478bd9Sstevel@tonic-gate return (err);
8097c478bd9Sstevel@tonic-gate }
8107c478bd9Sstevel@tonic-gate
8117c478bd9Sstevel@tonic-gate a = aa->value;
8127c478bd9Sstevel@tonic-gate r = result->value;
813b60f2a0bSfr41279 if (rsize == aa->len + 1) {
814b60f2a0bSfr41279 r[rsize - 1] = 1;
815b60f2a0bSfr41279 }
8167c478bd9Sstevel@tonic-gate cy = 0;
8177c478bd9Sstevel@tonic-gate for (i = 0; i < aa->len; i++) {
818b60f2a0bSfr41279 cy1 = a[i] >> (BIG_CHUNK_SIZE - 1);
8197c478bd9Sstevel@tonic-gate r[i] = (cy | (a[i] << 1));
8207c478bd9Sstevel@tonic-gate cy = cy1;
8217c478bd9Sstevel@tonic-gate }
8227c478bd9Sstevel@tonic-gate result->len = rsize;
8237c478bd9Sstevel@tonic-gate return (BIG_OK);
8247c478bd9Sstevel@tonic-gate }
8257c478bd9Sstevel@tonic-gate
826b60f2a0bSfr41279
827b60f2a0bSfr41279 /*
828b60f2a0bSfr41279 * returns aa mod b, aa must be nonneg, b must be a max
829b60f2a0bSfr41279 * (BIG_CHUNK_SIZE / 2)-bit integer
830b60f2a0bSfr41279 */
831b60f2a0bSfr41279 static uint32_t
big_modhalf_pos(BIGNUM * aa,uint32_t b)832b60f2a0bSfr41279 big_modhalf_pos(BIGNUM *aa, uint32_t b)
8337c478bd9Sstevel@tonic-gate {
8347c478bd9Sstevel@tonic-gate int i;
835b60f2a0bSfr41279 BIG_CHUNK_TYPE rem;
8367c478bd9Sstevel@tonic-gate
837b60f2a0bSfr41279 if (aa->len == 0) {
8387c478bd9Sstevel@tonic-gate return (0);
839b60f2a0bSfr41279 }
8407c478bd9Sstevel@tonic-gate rem = aa->value[aa->len - 1] % b;
8417c478bd9Sstevel@tonic-gate for (i = aa->len - 2; i >= 0; i--) {
842b60f2a0bSfr41279 rem = ((rem << (BIG_CHUNK_SIZE / 2)) |
843b60f2a0bSfr41279 (aa->value[i] >> (BIG_CHUNK_SIZE / 2))) % b;
844b60f2a0bSfr41279 rem = ((rem << (BIG_CHUNK_SIZE / 2)) |
845b60f2a0bSfr41279 (aa->value[i] & BIG_CHUNK_LOWHALFBITS)) % b;
8467c478bd9Sstevel@tonic-gate }
847b60f2a0bSfr41279
848b60f2a0bSfr41279 return ((uint32_t)rem);
8497c478bd9Sstevel@tonic-gate }
8507c478bd9Sstevel@tonic-gate
8517c478bd9Sstevel@tonic-gate
8527c478bd9Sstevel@tonic-gate /*
853b60f2a0bSfr41279 * result = aa - (2^BIG_CHUNK_SIZE)^lendiff * bb
8547c478bd9Sstevel@tonic-gate * result->size should be at least aa->len at entry
8557c478bd9Sstevel@tonic-gate * aa, bb, and result should be positive
8567c478bd9Sstevel@tonic-gate */
8577c478bd9Sstevel@tonic-gate void
big_sub_pos_high(BIGNUM * result,BIGNUM * aa,BIGNUM * bb)8587c478bd9Sstevel@tonic-gate big_sub_pos_high(BIGNUM *result, BIGNUM *aa, BIGNUM *bb)
8597c478bd9Sstevel@tonic-gate {
8607c478bd9Sstevel@tonic-gate int i, lendiff;
8617c478bd9Sstevel@tonic-gate BIGNUM res1, aa1;
8627c478bd9Sstevel@tonic-gate
8637c478bd9Sstevel@tonic-gate lendiff = aa->len - bb->len;
8647c478bd9Sstevel@tonic-gate res1.size = result->size - lendiff;
8657c478bd9Sstevel@tonic-gate res1.malloced = 0;
8667c478bd9Sstevel@tonic-gate res1.value = result->value + lendiff;
8677c478bd9Sstevel@tonic-gate aa1.size = aa->size - lendiff;
8687c478bd9Sstevel@tonic-gate aa1.value = aa->value + lendiff;
8697c478bd9Sstevel@tonic-gate aa1.len = bb->len;
8707c478bd9Sstevel@tonic-gate aa1.sign = 1;
8717c478bd9Sstevel@tonic-gate (void) big_sub_pos(&res1, &aa1, bb);
8727c478bd9Sstevel@tonic-gate if (result->value != aa->value) {
8737c478bd9Sstevel@tonic-gate for (i = 0; i < lendiff; i++) {
8747c478bd9Sstevel@tonic-gate result->value[i] = aa->value[i];
8757c478bd9Sstevel@tonic-gate }
8767c478bd9Sstevel@tonic-gate }
8777c478bd9Sstevel@tonic-gate result->len = aa->len;
8787c478bd9Sstevel@tonic-gate }
8797c478bd9Sstevel@tonic-gate
8807c478bd9Sstevel@tonic-gate
8817c478bd9Sstevel@tonic-gate /*
8827c478bd9Sstevel@tonic-gate * returns 1, 0, or -1 depending on whether |aa| > , ==, or <
883b60f2a0bSfr41279 * (2^BIG_CHUNK_SIZE)^lendiff * |bb|
8847c478bd9Sstevel@tonic-gate * aa->len should be >= bb->len
8857c478bd9Sstevel@tonic-gate */
8867c478bd9Sstevel@tonic-gate int
big_cmp_abs_high(BIGNUM * aa,BIGNUM * bb)8877c478bd9Sstevel@tonic-gate big_cmp_abs_high(BIGNUM *aa, BIGNUM *bb)
8887c478bd9Sstevel@tonic-gate {
8897c478bd9Sstevel@tonic-gate int lendiff;
8907c478bd9Sstevel@tonic-gate BIGNUM aa1;
8917c478bd9Sstevel@tonic-gate
8927c478bd9Sstevel@tonic-gate lendiff = aa->len - bb->len;
8937c478bd9Sstevel@tonic-gate aa1.len = bb->len;
8947c478bd9Sstevel@tonic-gate aa1.size = aa->size - lendiff;
8957c478bd9Sstevel@tonic-gate aa1.malloced = 0;
8967c478bd9Sstevel@tonic-gate aa1.value = aa->value + lendiff;
8977c478bd9Sstevel@tonic-gate return (big_cmp_abs(&aa1, bb));
8987c478bd9Sstevel@tonic-gate }
8997c478bd9Sstevel@tonic-gate
9007c478bd9Sstevel@tonic-gate
9017c478bd9Sstevel@tonic-gate /*
902b60f2a0bSfr41279 * result = aa * b where b is a max. (BIG_CHUNK_SIZE / 2)-bit positive integer.
9037c478bd9Sstevel@tonic-gate * result should have enough space allocated.
9047c478bd9Sstevel@tonic-gate */
905b60f2a0bSfr41279 static void
big_mulhalf_low(BIGNUM * result,BIGNUM * aa,BIG_CHUNK_TYPE b)906b60f2a0bSfr41279 big_mulhalf_low(BIGNUM *result, BIGNUM *aa, BIG_CHUNK_TYPE b)
9077c478bd9Sstevel@tonic-gate {
9087c478bd9Sstevel@tonic-gate int i;
909b60f2a0bSfr41279 BIG_CHUNK_TYPE t1, t2, ai, cy;
910b60f2a0bSfr41279 BIG_CHUNK_TYPE *a, *r;
9117c478bd9Sstevel@tonic-gate
9127c478bd9Sstevel@tonic-gate a = aa->value;
9137c478bd9Sstevel@tonic-gate r = result->value;
9147c478bd9Sstevel@tonic-gate cy = 0;
9157c478bd9Sstevel@tonic-gate for (i = 0; i < aa->len; i++) {
9167c478bd9Sstevel@tonic-gate ai = a[i];
917b60f2a0bSfr41279 t1 = (ai & BIG_CHUNK_LOWHALFBITS) * b + cy;
918b60f2a0bSfr41279 t2 = (ai >> (BIG_CHUNK_SIZE / 2)) * b +
919b60f2a0bSfr41279 (t1 >> (BIG_CHUNK_SIZE / 2));
920b60f2a0bSfr41279 r[i] = (t1 & BIG_CHUNK_LOWHALFBITS) |
921b60f2a0bSfr41279 (t2 << (BIG_CHUNK_SIZE / 2));
922b60f2a0bSfr41279 cy = t2 >> (BIG_CHUNK_SIZE / 2);
9237c478bd9Sstevel@tonic-gate }
9247c478bd9Sstevel@tonic-gate r[i] = cy;
9257c478bd9Sstevel@tonic-gate result->len = aa->len + 1;
9267c478bd9Sstevel@tonic-gate result->sign = aa->sign;
9277c478bd9Sstevel@tonic-gate }
9287c478bd9Sstevel@tonic-gate
9297c478bd9Sstevel@tonic-gate
9307c478bd9Sstevel@tonic-gate /*
931b60f2a0bSfr41279 * result = aa * b * 2^(BIG_CHUNK_SIZE / 2) where b is a max.
932b60f2a0bSfr41279 * (BIG_CHUNK_SIZE / 2)-bit positive integer.
9337c478bd9Sstevel@tonic-gate * result should have enough space allocated.
9347c478bd9Sstevel@tonic-gate */
935b60f2a0bSfr41279 static void
big_mulhalf_high(BIGNUM * result,BIGNUM * aa,BIG_CHUNK_TYPE b)936b60f2a0bSfr41279 big_mulhalf_high(BIGNUM *result, BIGNUM *aa, BIG_CHUNK_TYPE b)
9377c478bd9Sstevel@tonic-gate {
9387c478bd9Sstevel@tonic-gate int i;
939b60f2a0bSfr41279 BIG_CHUNK_TYPE t1, t2, ai, cy, ri;
940b60f2a0bSfr41279 BIG_CHUNK_TYPE *a, *r;
9417c478bd9Sstevel@tonic-gate
9427c478bd9Sstevel@tonic-gate a = aa->value;
9437c478bd9Sstevel@tonic-gate r = result->value;
9447c478bd9Sstevel@tonic-gate cy = 0;
9457c478bd9Sstevel@tonic-gate ri = 0;
9467c478bd9Sstevel@tonic-gate for (i = 0; i < aa->len; i++) {
9477c478bd9Sstevel@tonic-gate ai = a[i];
948b60f2a0bSfr41279 t1 = (ai & BIG_CHUNK_LOWHALFBITS) * b + cy;
949b60f2a0bSfr41279 t2 = (ai >> (BIG_CHUNK_SIZE / 2)) * b +
950b60f2a0bSfr41279 (t1 >> (BIG_CHUNK_SIZE / 2));
951b60f2a0bSfr41279 r[i] = (t1 << (BIG_CHUNK_SIZE / 2)) + ri;
952b60f2a0bSfr41279 ri = t2 & BIG_CHUNK_LOWHALFBITS;
953b60f2a0bSfr41279 cy = t2 >> (BIG_CHUNK_SIZE / 2);
9547c478bd9Sstevel@tonic-gate }
955b60f2a0bSfr41279 r[i] = (cy << (BIG_CHUNK_SIZE / 2)) + ri;
9567c478bd9Sstevel@tonic-gate result->len = aa->len + 1;
9577c478bd9Sstevel@tonic-gate result->sign = aa->sign;
9587c478bd9Sstevel@tonic-gate }
9597c478bd9Sstevel@tonic-gate
960b60f2a0bSfr41279
9617c478bd9Sstevel@tonic-gate /* it is assumed that result->size is big enough */
9627c478bd9Sstevel@tonic-gate void
big_shiftleft(BIGNUM * result,BIGNUM * aa,int offs)9637c478bd9Sstevel@tonic-gate big_shiftleft(BIGNUM *result, BIGNUM *aa, int offs)
9647c478bd9Sstevel@tonic-gate {
9657c478bd9Sstevel@tonic-gate int i;
966b60f2a0bSfr41279 BIG_CHUNK_TYPE cy, ai;
9677c478bd9Sstevel@tonic-gate
9687c478bd9Sstevel@tonic-gate if (offs == 0) {
9697c478bd9Sstevel@tonic-gate if (result != aa) {
9707c478bd9Sstevel@tonic-gate (void) big_copy(result, aa);
9717c478bd9Sstevel@tonic-gate }
9727c478bd9Sstevel@tonic-gate return;
9737c478bd9Sstevel@tonic-gate }
9747c478bd9Sstevel@tonic-gate cy = 0;
9757c478bd9Sstevel@tonic-gate for (i = 0; i < aa->len; i++) {
9767c478bd9Sstevel@tonic-gate ai = aa->value[i];
9777c478bd9Sstevel@tonic-gate result->value[i] = (ai << offs) | cy;
978b60f2a0bSfr41279 cy = ai >> (BIG_CHUNK_SIZE - offs);
9797c478bd9Sstevel@tonic-gate }
9807c478bd9Sstevel@tonic-gate if (cy != 0) {
9817c478bd9Sstevel@tonic-gate result->len = aa->len + 1;
9827c478bd9Sstevel@tonic-gate result->value[result->len - 1] = cy;
9837c478bd9Sstevel@tonic-gate } else {
9847c478bd9Sstevel@tonic-gate result->len = aa->len;
9857c478bd9Sstevel@tonic-gate }
9867c478bd9Sstevel@tonic-gate result->sign = aa->sign;
9877c478bd9Sstevel@tonic-gate }
9887c478bd9Sstevel@tonic-gate
989b60f2a0bSfr41279
9907c478bd9Sstevel@tonic-gate /* it is assumed that result->size is big enough */
9917c478bd9Sstevel@tonic-gate void
big_shiftright(BIGNUM * result,BIGNUM * aa,int offs)9927c478bd9Sstevel@tonic-gate big_shiftright(BIGNUM *result, BIGNUM *aa, int offs)
9937c478bd9Sstevel@tonic-gate {
9947c478bd9Sstevel@tonic-gate int i;
995b60f2a0bSfr41279 BIG_CHUNK_TYPE cy, ai;
9967c478bd9Sstevel@tonic-gate
9977c478bd9Sstevel@tonic-gate if (offs == 0) {
9987c478bd9Sstevel@tonic-gate if (result != aa) {
9997c478bd9Sstevel@tonic-gate (void) big_copy(result, aa);
10007c478bd9Sstevel@tonic-gate }
10017c478bd9Sstevel@tonic-gate return;
10027c478bd9Sstevel@tonic-gate }
10037c478bd9Sstevel@tonic-gate cy = aa->value[0] >> offs;
10047c478bd9Sstevel@tonic-gate for (i = 1; i < aa->len; i++) {
10057c478bd9Sstevel@tonic-gate ai = aa->value[i];
1006b60f2a0bSfr41279 result->value[i - 1] = (ai << (BIG_CHUNK_SIZE - offs)) | cy;
10077c478bd9Sstevel@tonic-gate cy = ai >> offs;
10087c478bd9Sstevel@tonic-gate }
10097c478bd9Sstevel@tonic-gate result->len = aa->len;
10107c478bd9Sstevel@tonic-gate result->value[result->len - 1] = cy;
10117c478bd9Sstevel@tonic-gate result->sign = aa->sign;
10127c478bd9Sstevel@tonic-gate }
10137c478bd9Sstevel@tonic-gate
10147c478bd9Sstevel@tonic-gate
10157c478bd9Sstevel@tonic-gate /*
10167c478bd9Sstevel@tonic-gate * result = aa/bb remainder = aa mod bb
10177c478bd9Sstevel@tonic-gate * it is assumed that aa and bb are positive
10187c478bd9Sstevel@tonic-gate */
10197c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_div_pos(BIGNUM * result,BIGNUM * remainder,BIGNUM * aa,BIGNUM * bb)10208475e043SDan OpenSolaris Anderson big_div_pos(BIGNUM *result, BIGNUM *remainder, BIGNUM *aa, BIGNUM *bb)
10217c478bd9Sstevel@tonic-gate {
1022b60f2a0bSfr41279 BIG_ERR_CODE err = BIG_OK;
10237c478bd9Sstevel@tonic-gate int i, alen, blen, tlen, rlen, offs;
1024b60f2a0bSfr41279 BIG_CHUNK_TYPE higha, highb, coeff;
1025b60f2a0bSfr41279 BIG_CHUNK_TYPE *a, *b;
10267c478bd9Sstevel@tonic-gate BIGNUM bbhigh, bblow, tresult, tmp1, tmp2;
1027b60f2a0bSfr41279 BIG_CHUNK_TYPE tmp1value[BIGTMPSIZE];
1028b60f2a0bSfr41279 BIG_CHUNK_TYPE tmp2value[BIGTMPSIZE];
1029b60f2a0bSfr41279 BIG_CHUNK_TYPE tresultvalue[BIGTMPSIZE];
1030b60f2a0bSfr41279 BIG_CHUNK_TYPE bblowvalue[BIGTMPSIZE];
1031b60f2a0bSfr41279 BIG_CHUNK_TYPE bbhighvalue[BIGTMPSIZE];
10327c478bd9Sstevel@tonic-gate
10337c478bd9Sstevel@tonic-gate a = aa->value;
10347c478bd9Sstevel@tonic-gate b = bb->value;
10357c478bd9Sstevel@tonic-gate alen = aa->len;
10367c478bd9Sstevel@tonic-gate blen = bb->len;
1037b60f2a0bSfr41279 while ((alen > 1) && (a[alen - 1] == 0)) {
1038b60f2a0bSfr41279 alen = alen - 1;
1039b60f2a0bSfr41279 }
10407c478bd9Sstevel@tonic-gate aa->len = alen;
1041b60f2a0bSfr41279 while ((blen > 1) && (b[blen - 1] == 0)) {
1042b60f2a0bSfr41279 blen = blen - 1;
1043b60f2a0bSfr41279 }
10447c478bd9Sstevel@tonic-gate bb->len = blen;
1045b60f2a0bSfr41279 if ((blen == 1) && (b[0] == 0)) {
10467c478bd9Sstevel@tonic-gate return (BIG_DIV_BY_0);
1047b60f2a0bSfr41279 }
10487c478bd9Sstevel@tonic-gate
10497c478bd9Sstevel@tonic-gate if (big_cmp_abs(aa, bb) < 0) {
10507c478bd9Sstevel@tonic-gate if ((remainder != NULL) &&
1051b60f2a0bSfr41279 ((err = big_copy(remainder, aa)) != BIG_OK)) {
10527c478bd9Sstevel@tonic-gate return (err);
1053b60f2a0bSfr41279 }
10547c478bd9Sstevel@tonic-gate if (result != NULL) {
10557c478bd9Sstevel@tonic-gate result->len = 1;
10567c478bd9Sstevel@tonic-gate result->sign = 1;
10577c478bd9Sstevel@tonic-gate result->value[0] = 0;
10587c478bd9Sstevel@tonic-gate }
10597c478bd9Sstevel@tonic-gate return (BIG_OK);
10607c478bd9Sstevel@tonic-gate }
10617c478bd9Sstevel@tonic-gate
10627c478bd9Sstevel@tonic-gate if ((err = big_init1(&bblow, blen + 1,
10637c478bd9Sstevel@tonic-gate bblowvalue, arraysize(bblowvalue))) != BIG_OK)
10647c478bd9Sstevel@tonic-gate return (err);
10657c478bd9Sstevel@tonic-gate
10667c478bd9Sstevel@tonic-gate if ((err = big_init1(&bbhigh, blen + 1,
10677c478bd9Sstevel@tonic-gate bbhighvalue, arraysize(bbhighvalue))) != BIG_OK)
10687c478bd9Sstevel@tonic-gate goto ret1;
10697c478bd9Sstevel@tonic-gate
10707c478bd9Sstevel@tonic-gate if ((err = big_init1(&tmp1, alen + 2,
10717c478bd9Sstevel@tonic-gate tmp1value, arraysize(tmp1value))) != BIG_OK)
10727c478bd9Sstevel@tonic-gate goto ret2;
10737c478bd9Sstevel@tonic-gate
10747c478bd9Sstevel@tonic-gate if ((err = big_init1(&tmp2, blen + 2,
10757c478bd9Sstevel@tonic-gate tmp2value, arraysize(tmp2value))) != BIG_OK)
10767c478bd9Sstevel@tonic-gate goto ret3;
10777c478bd9Sstevel@tonic-gate
10787c478bd9Sstevel@tonic-gate if ((err = big_init1(&tresult, alen - blen + 2,
10797c478bd9Sstevel@tonic-gate tresultvalue, arraysize(tresultvalue))) != BIG_OK)
10807c478bd9Sstevel@tonic-gate goto ret4;
10817c478bd9Sstevel@tonic-gate
10827c478bd9Sstevel@tonic-gate offs = 0;
1083b60f2a0bSfr41279 highb = b[blen - 1];
1084b60f2a0bSfr41279 if (highb >= (BIG_CHUNK_HALF_HIGHBIT << 1)) {
1085b60f2a0bSfr41279 highb = highb >> (BIG_CHUNK_SIZE / 2);
1086b60f2a0bSfr41279 offs = (BIG_CHUNK_SIZE / 2);
10877c478bd9Sstevel@tonic-gate }
1088b60f2a0bSfr41279 while ((highb & BIG_CHUNK_HALF_HIGHBIT) == 0) {
1089b60f2a0bSfr41279 highb = highb << 1;
10907c478bd9Sstevel@tonic-gate offs++;
10917c478bd9Sstevel@tonic-gate }
10927c478bd9Sstevel@tonic-gate
10937c478bd9Sstevel@tonic-gate big_shiftleft(&bblow, bb, offs);
1094b60f2a0bSfr41279
1095b60f2a0bSfr41279 if (offs <= (BIG_CHUNK_SIZE / 2 - 1)) {
1096b60f2a0bSfr41279 big_shiftleft(&bbhigh, &bblow, BIG_CHUNK_SIZE / 2);
10977c478bd9Sstevel@tonic-gate } else {
1098b60f2a0bSfr41279 big_shiftright(&bbhigh, &bblow, BIG_CHUNK_SIZE / 2);
10997c478bd9Sstevel@tonic-gate }
11007c478bd9Sstevel@tonic-gate if (bbhigh.value[bbhigh.len - 1] == 0) {
11017c478bd9Sstevel@tonic-gate bbhigh.len--;
11027c478bd9Sstevel@tonic-gate } else {
11037c478bd9Sstevel@tonic-gate bbhigh.value[bbhigh.len] = 0;
11047c478bd9Sstevel@tonic-gate }
11057c478bd9Sstevel@tonic-gate
1106b60f2a0bSfr41279 highb = bblow.value[bblow.len - 1];
1107b60f2a0bSfr41279
11087c478bd9Sstevel@tonic-gate big_shiftleft(&tmp1, aa, offs);
11097c478bd9Sstevel@tonic-gate rlen = tmp1.len - bblow.len + 1;
11107c478bd9Sstevel@tonic-gate tresult.len = rlen;
11117c478bd9Sstevel@tonic-gate
11127c478bd9Sstevel@tonic-gate tmp1.len++;
11137c478bd9Sstevel@tonic-gate tlen = tmp1.len;
11147c478bd9Sstevel@tonic-gate tmp1.value[tmp1.len - 1] = 0;
11157c478bd9Sstevel@tonic-gate for (i = 0; i < rlen; i++) {
1116b60f2a0bSfr41279 higha = (tmp1.value[tlen - 1] << (BIG_CHUNK_SIZE / 2)) +
1117b60f2a0bSfr41279 (tmp1.value[tlen - 2] >> (BIG_CHUNK_SIZE / 2));
11187c478bd9Sstevel@tonic-gate coeff = higha / (highb + 1);
1119b60f2a0bSfr41279 big_mulhalf_high(&tmp2, &bblow, coeff);
11207c478bd9Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &tmp2);
11217c478bd9Sstevel@tonic-gate bbhigh.len++;
11227c478bd9Sstevel@tonic-gate while (tmp1.value[tlen - 1] > 0) {
11237c478bd9Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &bbhigh);
11247c478bd9Sstevel@tonic-gate coeff++;
11257c478bd9Sstevel@tonic-gate }
11267c478bd9Sstevel@tonic-gate bbhigh.len--;
11277c478bd9Sstevel@tonic-gate tlen--;
11287c478bd9Sstevel@tonic-gate tmp1.len--;
11297c478bd9Sstevel@tonic-gate while (big_cmp_abs_high(&tmp1, &bbhigh) >= 0) {
11307c478bd9Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &bbhigh);
11317c478bd9Sstevel@tonic-gate coeff++;
11327c478bd9Sstevel@tonic-gate }
1133b60f2a0bSfr41279 tresult.value[rlen - i - 1] = coeff << (BIG_CHUNK_SIZE / 2);
11347c478bd9Sstevel@tonic-gate higha = tmp1.value[tlen - 1];
11357c478bd9Sstevel@tonic-gate coeff = higha / (highb + 1);
1136b60f2a0bSfr41279 big_mulhalf_low(&tmp2, &bblow, coeff);
11377c478bd9Sstevel@tonic-gate tmp2.len--;
11387c478bd9Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &tmp2);
11397c478bd9Sstevel@tonic-gate while (big_cmp_abs_high(&tmp1, &bblow) >= 0) {
11407c478bd9Sstevel@tonic-gate big_sub_pos_high(&tmp1, &tmp1, &bblow);
11417c478bd9Sstevel@tonic-gate coeff++;
11427c478bd9Sstevel@tonic-gate }
11437c478bd9Sstevel@tonic-gate tresult.value[rlen - i - 1] =
11447c478bd9Sstevel@tonic-gate tresult.value[rlen - i - 1] + coeff;
11457c478bd9Sstevel@tonic-gate }
11467c478bd9Sstevel@tonic-gate
11477c478bd9Sstevel@tonic-gate big_shiftright(&tmp1, &tmp1, offs);
11487c478bd9Sstevel@tonic-gate
11497c478bd9Sstevel@tonic-gate err = BIG_OK;
11507c478bd9Sstevel@tonic-gate
11517c478bd9Sstevel@tonic-gate if ((remainder != NULL) &&
11527c478bd9Sstevel@tonic-gate ((err = big_copy(remainder, &tmp1)) != BIG_OK))
11537c478bd9Sstevel@tonic-gate goto ret;
11547c478bd9Sstevel@tonic-gate
11557c478bd9Sstevel@tonic-gate if (result != NULL)
11567c478bd9Sstevel@tonic-gate err = big_copy(result, &tresult);
11577c478bd9Sstevel@tonic-gate
11587c478bd9Sstevel@tonic-gate ret:
11597c478bd9Sstevel@tonic-gate big_finish(&tresult);
11607c478bd9Sstevel@tonic-gate ret4:
11617c478bd9Sstevel@tonic-gate big_finish(&tmp1);
11627c478bd9Sstevel@tonic-gate ret3:
11637c478bd9Sstevel@tonic-gate big_finish(&tmp2);
11647c478bd9Sstevel@tonic-gate ret2:
11657c478bd9Sstevel@tonic-gate big_finish(&bbhigh);
11667c478bd9Sstevel@tonic-gate ret1:
11677c478bd9Sstevel@tonic-gate big_finish(&bblow);
11687c478bd9Sstevel@tonic-gate return (err);
11697c478bd9Sstevel@tonic-gate }
11707c478bd9Sstevel@tonic-gate
11718475e043SDan OpenSolaris Anderson
11727c478bd9Sstevel@tonic-gate /*
11737c478bd9Sstevel@tonic-gate * If there is no processor-specific integer implementation of
11747c478bd9Sstevel@tonic-gate * the lower level multiply functions, then this code is provided
11757c478bd9Sstevel@tonic-gate * for big_mul_set_vec(), big_mul_add_vec(), big_mul_vec() and
11767c478bd9Sstevel@tonic-gate * big_sqr_vec().
11777c478bd9Sstevel@tonic-gate *
11787c478bd9Sstevel@tonic-gate * There are two generic implementations. One that assumes that
11797c478bd9Sstevel@tonic-gate * there is hardware and C compiler support for a 32 x 32 --> 64
11807c478bd9Sstevel@tonic-gate * bit unsigned multiply, but otherwise is not specific to any
11817c478bd9Sstevel@tonic-gate * processor, platform, or ISA.
11827c478bd9Sstevel@tonic-gate *
11837c478bd9Sstevel@tonic-gate * The other makes very few assumptions about hardware capabilities.
11847c478bd9Sstevel@tonic-gate * It does not even assume that there is any implementation of a
11857c478bd9Sstevel@tonic-gate * 32 x 32 --> 64 bit multiply that is accessible to C code and
11867c478bd9Sstevel@tonic-gate * appropriate to use. It falls constructs 32 x 32 --> 64 bit
11877c478bd9Sstevel@tonic-gate * multiplies from 16 x 16 --> 32 bit multiplies.
11887c478bd9Sstevel@tonic-gate *
11897c478bd9Sstevel@tonic-gate */
11907c478bd9Sstevel@tonic-gate
11917c478bd9Sstevel@tonic-gate #if !defined(PSR_MUL)
11927c478bd9Sstevel@tonic-gate
11937c478bd9Sstevel@tonic-gate #ifdef UMUL64
11947c478bd9Sstevel@tonic-gate
1195b60f2a0bSfr41279 #if (BIG_CHUNK_SIZE == 32)
1196b60f2a0bSfr41279
11977c478bd9Sstevel@tonic-gate #define UNROLL8
11987c478bd9Sstevel@tonic-gate
11997c478bd9Sstevel@tonic-gate #define MUL_SET_VEC_ROUND_PREFETCH(R) \
12007c478bd9Sstevel@tonic-gate p = pf * d; \
12017c478bd9Sstevel@tonic-gate pf = (uint64_t)a[R + 1]; \
12027c478bd9Sstevel@tonic-gate t = p + cy; \
12037c478bd9Sstevel@tonic-gate r[R] = (uint32_t)t; \
12047c478bd9Sstevel@tonic-gate cy = t >> 32
12057c478bd9Sstevel@tonic-gate
12067c478bd9Sstevel@tonic-gate #define MUL_SET_VEC_ROUND_NOPREFETCH(R) \
12077c478bd9Sstevel@tonic-gate p = pf * d; \
12087c478bd9Sstevel@tonic-gate t = p + cy; \
12097c478bd9Sstevel@tonic-gate r[R] = (uint32_t)t; \
12107c478bd9Sstevel@tonic-gate cy = t >> 32
12117c478bd9Sstevel@tonic-gate
12127c478bd9Sstevel@tonic-gate #define MUL_ADD_VEC_ROUND_PREFETCH(R) \
12137c478bd9Sstevel@tonic-gate t = (uint64_t)r[R]; \
12147c478bd9Sstevel@tonic-gate p = pf * d; \
12157c478bd9Sstevel@tonic-gate pf = (uint64_t)a[R + 1]; \
12167c478bd9Sstevel@tonic-gate t = p + t + cy; \
12177c478bd9Sstevel@tonic-gate r[R] = (uint32_t)t; \
12187c478bd9Sstevel@tonic-gate cy = t >> 32
12197c478bd9Sstevel@tonic-gate
12207c478bd9Sstevel@tonic-gate #define MUL_ADD_VEC_ROUND_NOPREFETCH(R) \
12217c478bd9Sstevel@tonic-gate t = (uint64_t)r[R]; \
12227c478bd9Sstevel@tonic-gate p = pf * d; \
12237c478bd9Sstevel@tonic-gate t = p + t + cy; \
12247c478bd9Sstevel@tonic-gate r[R] = (uint32_t)t; \
12257c478bd9Sstevel@tonic-gate cy = t >> 32
12267c478bd9Sstevel@tonic-gate
12277c478bd9Sstevel@tonic-gate #ifdef UNROLL8
12287c478bd9Sstevel@tonic-gate
12297c478bd9Sstevel@tonic-gate #define UNROLL 8
12307c478bd9Sstevel@tonic-gate
12317c478bd9Sstevel@tonic-gate /*
12327c478bd9Sstevel@tonic-gate * r = a * b
12337c478bd9Sstevel@tonic-gate * where r and a are vectors; b is a single 32-bit digit
12347c478bd9Sstevel@tonic-gate */
12357c478bd9Sstevel@tonic-gate
12367c478bd9Sstevel@tonic-gate uint32_t
big_mul_set_vec(uint32_t * r,uint32_t * a,int len,uint32_t b)12377c478bd9Sstevel@tonic-gate big_mul_set_vec(uint32_t *r, uint32_t *a, int len, uint32_t b)
12387c478bd9Sstevel@tonic-gate {
12397c478bd9Sstevel@tonic-gate uint64_t d, pf, p, t, cy;
12407c478bd9Sstevel@tonic-gate
12417c478bd9Sstevel@tonic-gate if (len == 0)
12427c478bd9Sstevel@tonic-gate return (0);
12437c478bd9Sstevel@tonic-gate cy = 0;
12447c478bd9Sstevel@tonic-gate d = (uint64_t)b;
12457c478bd9Sstevel@tonic-gate pf = (uint64_t)a[0];
12467c478bd9Sstevel@tonic-gate while (len > UNROLL) {
12477c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(0);
12487c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(1);
12497c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(2);
12507c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(3);
12517c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(4);
12527c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(5);
12537c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(6);
12547c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(7);
12557c478bd9Sstevel@tonic-gate r += UNROLL;
12567c478bd9Sstevel@tonic-gate a += UNROLL;
12577c478bd9Sstevel@tonic-gate len -= UNROLL;
12587c478bd9Sstevel@tonic-gate }
12597c478bd9Sstevel@tonic-gate if (len == UNROLL) {
12607c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(0);
12617c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(1);
12627c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(2);
12637c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(3);
12647c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(4);
12657c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(5);
12667c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(6);
12677c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_NOPREFETCH(7);
12687c478bd9Sstevel@tonic-gate return ((uint32_t)cy);
12697c478bd9Sstevel@tonic-gate }
12707c478bd9Sstevel@tonic-gate while (len > 1) {
12717c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_PREFETCH(0);
12727c478bd9Sstevel@tonic-gate ++r;
12737c478bd9Sstevel@tonic-gate ++a;
12747c478bd9Sstevel@tonic-gate --len;
12757c478bd9Sstevel@tonic-gate }
12767c478bd9Sstevel@tonic-gate if (len > 0) {
12777c478bd9Sstevel@tonic-gate MUL_SET_VEC_ROUND_NOPREFETCH(0);
12787c478bd9Sstevel@tonic-gate }
12797c478bd9Sstevel@tonic-gate return ((uint32_t)cy);
12807c478bd9Sstevel@tonic-gate }
12817c478bd9Sstevel@tonic-gate
12827c478bd9Sstevel@tonic-gate /*
12837c478bd9Sstevel@tonic-gate * r += a * b
12847c478bd9Sstevel@tonic-gate * where r and a are vectors; b is a single 32-bit digit
12857c478bd9Sstevel@tonic-gate */
12867c478bd9Sstevel@tonic-gate
12877c478bd9Sstevel@tonic-gate uint32_t
big_mul_add_vec(uint32_t * r,uint32_t * a,int len,uint32_t b)12887c478bd9Sstevel@tonic-gate big_mul_add_vec(uint32_t *r, uint32_t *a, int len, uint32_t b)
12897c478bd9Sstevel@tonic-gate {
12907c478bd9Sstevel@tonic-gate uint64_t d, pf, p, t, cy;
12917c478bd9Sstevel@tonic-gate
12927c478bd9Sstevel@tonic-gate if (len == 0)
12937c478bd9Sstevel@tonic-gate return (0);
12947c478bd9Sstevel@tonic-gate cy = 0;
12957c478bd9Sstevel@tonic-gate d = (uint64_t)b;
12967c478bd9Sstevel@tonic-gate pf = (uint64_t)a[0];
12977c478bd9Sstevel@tonic-gate while (len > 8) {
12987c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(0);
12997c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(1);
13007c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(2);
13017c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(3);
13027c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(4);
13037c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(5);
13047c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(6);
13057c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(7);
13067c478bd9Sstevel@tonic-gate r += 8;
13077c478bd9Sstevel@tonic-gate a += 8;
13087c478bd9Sstevel@tonic-gate len -= 8;
13097c478bd9Sstevel@tonic-gate }
13107c478bd9Sstevel@tonic-gate if (len == 8) {
13117c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(0);
13127c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(1);
13137c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(2);
13147c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(3);
13157c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(4);
13167c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(5);
13177c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(6);
13187c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_NOPREFETCH(7);
13197c478bd9Sstevel@tonic-gate return ((uint32_t)cy);
13207c478bd9Sstevel@tonic-gate }
13217c478bd9Sstevel@tonic-gate while (len > 1) {
13227c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_PREFETCH(0);
13237c478bd9Sstevel@tonic-gate ++r;
13247c478bd9Sstevel@tonic-gate ++a;
13257c478bd9Sstevel@tonic-gate --len;
13267c478bd9Sstevel@tonic-gate }
13277c478bd9Sstevel@tonic-gate if (len > 0) {
13287c478bd9Sstevel@tonic-gate MUL_ADD_VEC_ROUND_NOPREFETCH(0);
13297c478bd9Sstevel@tonic-gate }
13307c478bd9Sstevel@tonic-gate return ((uint32_t)cy);
13317c478bd9Sstevel@tonic-gate }
13327c478bd9Sstevel@tonic-gate #endif /* UNROLL8 */
13337c478bd9Sstevel@tonic-gate
13347c478bd9Sstevel@tonic-gate void
big_sqr_vec(uint32_t * r,uint32_t * a,int len)13357c478bd9Sstevel@tonic-gate big_sqr_vec(uint32_t *r, uint32_t *a, int len)
13367c478bd9Sstevel@tonic-gate {
13377c478bd9Sstevel@tonic-gate uint32_t *tr, *ta;
13387c478bd9Sstevel@tonic-gate int tlen, row, col;
13397c478bd9Sstevel@tonic-gate uint64_t p, s, t, t2, cy;
13407c478bd9Sstevel@tonic-gate uint32_t d;
13417c478bd9Sstevel@tonic-gate
13427c478bd9Sstevel@tonic-gate tr = r + 1;
13437c478bd9Sstevel@tonic-gate ta = a;
13447c478bd9Sstevel@tonic-gate tlen = len - 1;
13457c478bd9Sstevel@tonic-gate tr[tlen] = big_mul_set_vec(tr, ta + 1, tlen, ta[0]);
13467c478bd9Sstevel@tonic-gate while (--tlen > 0) {
13477c478bd9Sstevel@tonic-gate tr += 2;
13487c478bd9Sstevel@tonic-gate ++ta;
13497c478bd9Sstevel@tonic-gate tr[tlen] = big_mul_add_vec(tr, ta + 1, tlen, ta[0]);
13507c478bd9Sstevel@tonic-gate }
13517c478bd9Sstevel@tonic-gate s = (uint64_t)a[0];
13527c478bd9Sstevel@tonic-gate s = s * s;
13537c478bd9Sstevel@tonic-gate r[0] = (uint32_t)s;
13547c478bd9Sstevel@tonic-gate cy = s >> 32;
13557c478bd9Sstevel@tonic-gate p = ((uint64_t)r[1] << 1) + cy;
13567c478bd9Sstevel@tonic-gate r[1] = (uint32_t)p;
13577c478bd9Sstevel@tonic-gate cy = p >> 32;
13587c478bd9Sstevel@tonic-gate row = 1;
13597c478bd9Sstevel@tonic-gate col = 2;
13607c478bd9Sstevel@tonic-gate while (row < len) {
13617c478bd9Sstevel@tonic-gate s = (uint64_t)a[row];
13627c478bd9Sstevel@tonic-gate s = s * s;
13637c478bd9Sstevel@tonic-gate p = (uint64_t)r[col] << 1;
13647c478bd9Sstevel@tonic-gate t = p + s;
13657c478bd9Sstevel@tonic-gate d = (uint32_t)t;
13667c478bd9Sstevel@tonic-gate t2 = (uint64_t)d + cy;
13677c478bd9Sstevel@tonic-gate r[col] = (uint32_t)t2;
13687c478bd9Sstevel@tonic-gate cy = (t >> 32) + (t2 >> 32);
13697c478bd9Sstevel@tonic-gate if (row == len - 1)
13707c478bd9Sstevel@tonic-gate break;
13717c478bd9Sstevel@tonic-gate p = ((uint64_t)r[col + 1] << 1) + cy;
13727c478bd9Sstevel@tonic-gate r[col + 1] = (uint32_t)p;
13737c478bd9Sstevel@tonic-gate cy = p >> 32;
13747c478bd9Sstevel@tonic-gate ++row;
13757c478bd9Sstevel@tonic-gate col += 2;
13767c478bd9Sstevel@tonic-gate }
13777c478bd9Sstevel@tonic-gate r[col + 1] = (uint32_t)cy;
13787c478bd9Sstevel@tonic-gate }
13797c478bd9Sstevel@tonic-gate
1380b60f2a0bSfr41279 #else /* BIG_CHUNK_SIZE == 64 */
1381b60f2a0bSfr41279
1382b60f2a0bSfr41279 /*
1383b60f2a0bSfr41279 * r = r + a * digit, r and a are vectors of length len
1384b60f2a0bSfr41279 * returns the carry digit
1385b60f2a0bSfr41279 */
1386b60f2a0bSfr41279 BIG_CHUNK_TYPE
big_mul_add_vec(BIG_CHUNK_TYPE * r,BIG_CHUNK_TYPE * a,int len,BIG_CHUNK_TYPE digit)1387b60f2a0bSfr41279 big_mul_add_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len,
1388b60f2a0bSfr41279 BIG_CHUNK_TYPE digit)
1389b60f2a0bSfr41279 {
1390b60f2a0bSfr41279 BIG_CHUNK_TYPE cy, cy1, retcy, dlow, dhigh;
1391b60f2a0bSfr41279 int i;
1392b60f2a0bSfr41279
1393b60f2a0bSfr41279 cy1 = 0;
1394b60f2a0bSfr41279 dlow = digit & BIG_CHUNK_LOWHALFBITS;
1395b60f2a0bSfr41279 dhigh = digit >> (BIG_CHUNK_SIZE / 2);
1396b60f2a0bSfr41279 for (i = 0; i < len; i++) {
1397b60f2a0bSfr41279 cy = (cy1 >> (BIG_CHUNK_SIZE / 2)) +
1398b60f2a0bSfr41279 dlow * (a[i] & BIG_CHUNK_LOWHALFBITS) +
1399b60f2a0bSfr41279 (r[i] & BIG_CHUNK_LOWHALFBITS);
1400b60f2a0bSfr41279 cy1 = (cy >> (BIG_CHUNK_SIZE / 2)) +
1401b60f2a0bSfr41279 dlow * (a[i] >> (BIG_CHUNK_SIZE / 2)) +
1402b60f2a0bSfr41279 (r[i] >> (BIG_CHUNK_SIZE / 2));
1403b60f2a0bSfr41279 r[i] = (cy & BIG_CHUNK_LOWHALFBITS) |
1404b60f2a0bSfr41279 (cy1 << (BIG_CHUNK_SIZE / 2));
1405b60f2a0bSfr41279 }
1406b60f2a0bSfr41279 retcy = cy1 >> (BIG_CHUNK_SIZE / 2);
1407b60f2a0bSfr41279
1408b60f2a0bSfr41279 cy1 = r[0] & BIG_CHUNK_LOWHALFBITS;
1409b60f2a0bSfr41279 for (i = 0; i < len - 1; i++) {
1410b60f2a0bSfr41279 cy = (cy1 >> (BIG_CHUNK_SIZE / 2)) +
1411b60f2a0bSfr41279 dhigh * (a[i] & BIG_CHUNK_LOWHALFBITS) +
1412b60f2a0bSfr41279 (r[i] >> (BIG_CHUNK_SIZE / 2));
1413b60f2a0bSfr41279 r[i] = (cy1 & BIG_CHUNK_LOWHALFBITS) |
1414b60f2a0bSfr41279 (cy << (BIG_CHUNK_SIZE / 2));
1415b60f2a0bSfr41279 cy1 = (cy >> (BIG_CHUNK_SIZE / 2)) +
1416b60f2a0bSfr41279 dhigh * (a[i] >> (BIG_CHUNK_SIZE / 2)) +
1417b60f2a0bSfr41279 (r[i + 1] & BIG_CHUNK_LOWHALFBITS);
1418b60f2a0bSfr41279 }
1419b60f2a0bSfr41279 cy = (cy1 >> (BIG_CHUNK_SIZE / 2)) +
1420b60f2a0bSfr41279 dhigh * (a[len - 1] & BIG_CHUNK_LOWHALFBITS) +
1421b60f2a0bSfr41279 (r[len - 1] >> (BIG_CHUNK_SIZE / 2));
1422b60f2a0bSfr41279 r[len - 1] = (cy1 & BIG_CHUNK_LOWHALFBITS) |
1423b60f2a0bSfr41279 (cy << (BIG_CHUNK_SIZE / 2));
1424b60f2a0bSfr41279 retcy = (cy >> (BIG_CHUNK_SIZE / 2)) +
1425b60f2a0bSfr41279 dhigh * (a[len - 1] >> (BIG_CHUNK_SIZE / 2)) + retcy;
1426b60f2a0bSfr41279
1427b60f2a0bSfr41279 return (retcy);
1428b60f2a0bSfr41279 }
1429b60f2a0bSfr41279
1430b60f2a0bSfr41279
1431b60f2a0bSfr41279 /*
1432b60f2a0bSfr41279 * r = a * digit, r and a are vectors of length len
1433b60f2a0bSfr41279 * returns the carry digit
1434b60f2a0bSfr41279 */
1435b60f2a0bSfr41279 BIG_CHUNK_TYPE
big_mul_set_vec(BIG_CHUNK_TYPE * r,BIG_CHUNK_TYPE * a,int len,BIG_CHUNK_TYPE digit)1436b60f2a0bSfr41279 big_mul_set_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len,
1437b60f2a0bSfr41279 BIG_CHUNK_TYPE digit)
1438b60f2a0bSfr41279 {
1439b60f2a0bSfr41279 int i;
1440b60f2a0bSfr41279
1441b60f2a0bSfr41279 ASSERT(r != a);
1442b60f2a0bSfr41279 for (i = 0; i < len; i++) {
1443b60f2a0bSfr41279 r[i] = 0;
1444b60f2a0bSfr41279 }
1445b60f2a0bSfr41279 return (big_mul_add_vec(r, a, len, digit));
1446b60f2a0bSfr41279 }
1447b60f2a0bSfr41279
1448b60f2a0bSfr41279 void
big_sqr_vec(BIG_CHUNK_TYPE * r,BIG_CHUNK_TYPE * a,int len)1449b60f2a0bSfr41279 big_sqr_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len)
1450b60f2a0bSfr41279 {
1451b60f2a0bSfr41279 int i;
1452b60f2a0bSfr41279
1453b60f2a0bSfr41279 ASSERT(r != a);
1454b60f2a0bSfr41279 r[len] = big_mul_set_vec(r, a, len, a[0]);
1455b60f2a0bSfr41279 for (i = 1; i < len; ++i)
1456b60f2a0bSfr41279 r[len + i] = big_mul_add_vec(r + i, a, len, a[i]);
1457b60f2a0bSfr41279 }
1458b60f2a0bSfr41279
1459b60f2a0bSfr41279 #endif /* BIG_CHUNK_SIZE == 32/64 */
1460b60f2a0bSfr41279
14618475e043SDan OpenSolaris Anderson
14627c478bd9Sstevel@tonic-gate #else /* ! UMUL64 */
14637c478bd9Sstevel@tonic-gate
1464b60f2a0bSfr41279 #if (BIG_CHUNK_SIZE != 32)
1465*f05d7fc8SRichard Lowe #error "Don't use 64-bit chunks without defining UMUL64"
1466b60f2a0bSfr41279 #endif
1467b60f2a0bSfr41279
1468b60f2a0bSfr41279
14697c478bd9Sstevel@tonic-gate /*
14707c478bd9Sstevel@tonic-gate * r = r + a * digit, r and a are vectors of length len
14717c478bd9Sstevel@tonic-gate * returns the carry digit
14727c478bd9Sstevel@tonic-gate */
14737c478bd9Sstevel@tonic-gate uint32_t
big_mul_add_vec(uint32_t * r,uint32_t * a,int len,uint32_t digit)14747c478bd9Sstevel@tonic-gate big_mul_add_vec(uint32_t *r, uint32_t *a, int len, uint32_t digit)
14757c478bd9Sstevel@tonic-gate {
14767c478bd9Sstevel@tonic-gate uint32_t cy, cy1, retcy, dlow, dhigh;
14777c478bd9Sstevel@tonic-gate int i;
14787c478bd9Sstevel@tonic-gate
14797c478bd9Sstevel@tonic-gate cy1 = 0;
14807c478bd9Sstevel@tonic-gate dlow = digit & 0xffff;
14817c478bd9Sstevel@tonic-gate dhigh = digit >> 16;
14827c478bd9Sstevel@tonic-gate for (i = 0; i < len; i++) {
14837c478bd9Sstevel@tonic-gate cy = (cy1 >> 16) + dlow * (a[i] & 0xffff) + (r[i] & 0xffff);
14847c478bd9Sstevel@tonic-gate cy1 = (cy >> 16) + dlow * (a[i]>>16) + (r[i] >> 16);
14857c478bd9Sstevel@tonic-gate r[i] = (cy & 0xffff) | (cy1 << 16);
14867c478bd9Sstevel@tonic-gate }
14877c478bd9Sstevel@tonic-gate retcy = cy1 >> 16;
14887c478bd9Sstevel@tonic-gate
14897c478bd9Sstevel@tonic-gate cy1 = r[0] & 0xffff;
14907c478bd9Sstevel@tonic-gate for (i = 0; i < len - 1; i++) {
14917c478bd9Sstevel@tonic-gate cy = (cy1 >> 16) + dhigh * (a[i] & 0xffff) + (r[i] >> 16);
14927c478bd9Sstevel@tonic-gate r[i] = (cy1 & 0xffff) | (cy << 16);
14937c478bd9Sstevel@tonic-gate cy1 = (cy >> 16) + dhigh * (a[i] >> 16) + (r[i + 1] & 0xffff);
14947c478bd9Sstevel@tonic-gate }
14957c478bd9Sstevel@tonic-gate cy = (cy1 >> 16) + dhigh * (a[len - 1] & 0xffff) + (r[len - 1] >> 16);
14967c478bd9Sstevel@tonic-gate r[len - 1] = (cy1 & 0xffff) | (cy << 16);
14977c478bd9Sstevel@tonic-gate retcy = (cy >> 16) + dhigh * (a[len - 1] >> 16) + retcy;
14987c478bd9Sstevel@tonic-gate
14997c478bd9Sstevel@tonic-gate return (retcy);
15007c478bd9Sstevel@tonic-gate }
15017c478bd9Sstevel@tonic-gate
1502b60f2a0bSfr41279
15037c478bd9Sstevel@tonic-gate /*
15047c478bd9Sstevel@tonic-gate * r = a * digit, r and a are vectors of length len
15057c478bd9Sstevel@tonic-gate * returns the carry digit
15067c478bd9Sstevel@tonic-gate */
15077c478bd9Sstevel@tonic-gate uint32_t
big_mul_set_vec(uint32_t * r,uint32_t * a,int len,uint32_t digit)15087c478bd9Sstevel@tonic-gate big_mul_set_vec(uint32_t *r, uint32_t *a, int len, uint32_t digit)
15097c478bd9Sstevel@tonic-gate {
1510b60f2a0bSfr41279 int i;
1511b60f2a0bSfr41279
1512b60f2a0bSfr41279 ASSERT(r != a);
1513b60f2a0bSfr41279 for (i = 0; i < len; i++) {
1514b60f2a0bSfr41279 r[i] = 0;
1515b60f2a0bSfr41279 }
1516b60f2a0bSfr41279
15177c478bd9Sstevel@tonic-gate return (big_mul_add_vec(r, a, len, digit));
15187c478bd9Sstevel@tonic-gate }
15197c478bd9Sstevel@tonic-gate
15207c478bd9Sstevel@tonic-gate void
big_sqr_vec(uint32_t * r,uint32_t * a,int len)15217c478bd9Sstevel@tonic-gate big_sqr_vec(uint32_t *r, uint32_t *a, int len)
15227c478bd9Sstevel@tonic-gate {
15237c478bd9Sstevel@tonic-gate int i;
15247c478bd9Sstevel@tonic-gate
1525b60f2a0bSfr41279 ASSERT(r != a);
15267c478bd9Sstevel@tonic-gate r[len] = big_mul_set_vec(r, a, len, a[0]);
15277c478bd9Sstevel@tonic-gate for (i = 1; i < len; ++i)
15287c478bd9Sstevel@tonic-gate r[len + i] = big_mul_add_vec(r + i, a, len, a[i]);
15297c478bd9Sstevel@tonic-gate }
15307c478bd9Sstevel@tonic-gate
15317c478bd9Sstevel@tonic-gate #endif /* UMUL64 */
15327c478bd9Sstevel@tonic-gate
15337c478bd9Sstevel@tonic-gate void
big_mul_vec(BIG_CHUNK_TYPE * r,BIG_CHUNK_TYPE * a,int alen,BIG_CHUNK_TYPE * b,int blen)1534b60f2a0bSfr41279 big_mul_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int alen,
1535b60f2a0bSfr41279 BIG_CHUNK_TYPE *b, int blen)
15367c478bd9Sstevel@tonic-gate {
15377c478bd9Sstevel@tonic-gate int i;
15387c478bd9Sstevel@tonic-gate
15397c478bd9Sstevel@tonic-gate r[alen] = big_mul_set_vec(r, a, alen, b[0]);
15407c478bd9Sstevel@tonic-gate for (i = 1; i < blen; ++i)
15417c478bd9Sstevel@tonic-gate r[alen + i] = big_mul_add_vec(r + i, a, alen, b[i]);
15427c478bd9Sstevel@tonic-gate }
15437c478bd9Sstevel@tonic-gate
15447c478bd9Sstevel@tonic-gate
15457c478bd9Sstevel@tonic-gate #endif /* ! PSR_MUL */
15467c478bd9Sstevel@tonic-gate
15477c478bd9Sstevel@tonic-gate
15487c478bd9Sstevel@tonic-gate /*
15497c478bd9Sstevel@tonic-gate * result = aa * bb result->value should be big enough to hold the result
15507c478bd9Sstevel@tonic-gate *
15517c478bd9Sstevel@tonic-gate * Implementation: Standard grammar school algorithm
15527c478bd9Sstevel@tonic-gate *
15537c478bd9Sstevel@tonic-gate */
15547c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_mul(BIGNUM * result,BIGNUM * aa,BIGNUM * bb)15557c478bd9Sstevel@tonic-gate big_mul(BIGNUM *result, BIGNUM *aa, BIGNUM *bb)
15567c478bd9Sstevel@tonic-gate {
15577c478bd9Sstevel@tonic-gate BIGNUM tmp1;
1558b60f2a0bSfr41279 BIG_CHUNK_TYPE tmp1value[BIGTMPSIZE];
1559b60f2a0bSfr41279 BIG_CHUNK_TYPE *r, *t, *a, *b;
15607c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
15617c478bd9Sstevel@tonic-gate int i, alen, blen, rsize, sign, diff;
15627c478bd9Sstevel@tonic-gate
15637c478bd9Sstevel@tonic-gate if (aa == bb) {
15647c478bd9Sstevel@tonic-gate diff = 0;
15657c478bd9Sstevel@tonic-gate } else {
15667c478bd9Sstevel@tonic-gate diff = big_cmp_abs(aa, bb);
15677c478bd9Sstevel@tonic-gate if (diff < 0) {
15687c478bd9Sstevel@tonic-gate BIGNUM *tt;
15697c478bd9Sstevel@tonic-gate tt = aa;
15707c478bd9Sstevel@tonic-gate aa = bb;
15717c478bd9Sstevel@tonic-gate bb = tt;
15727c478bd9Sstevel@tonic-gate }
15737c478bd9Sstevel@tonic-gate }
15747c478bd9Sstevel@tonic-gate a = aa->value;
15757c478bd9Sstevel@tonic-gate b = bb->value;
15767c478bd9Sstevel@tonic-gate alen = aa->len;
15777c478bd9Sstevel@tonic-gate blen = bb->len;
1578b60f2a0bSfr41279 while ((alen > 1) && (a[alen - 1] == 0)) {
1579b60f2a0bSfr41279 alen--;
1580b60f2a0bSfr41279 }
15817c478bd9Sstevel@tonic-gate aa->len = alen;
1582b60f2a0bSfr41279 while ((blen > 1) && (b[blen - 1] == 0)) {
1583b60f2a0bSfr41279 blen--;
1584b60f2a0bSfr41279 }
15857c478bd9Sstevel@tonic-gate bb->len = blen;
15867c478bd9Sstevel@tonic-gate
15877c478bd9Sstevel@tonic-gate rsize = alen + blen;
15888475e043SDan OpenSolaris Anderson ASSERT(rsize > 0);
15897c478bd9Sstevel@tonic-gate if (result->size < rsize) {
15907c478bd9Sstevel@tonic-gate err = big_extend(result, rsize);
1591b60f2a0bSfr41279 if (err != BIG_OK) {
15927c478bd9Sstevel@tonic-gate return (err);
1593b60f2a0bSfr41279 }
15947c478bd9Sstevel@tonic-gate /* aa or bb might be an alias to result */
15957c478bd9Sstevel@tonic-gate a = aa->value;
15967c478bd9Sstevel@tonic-gate b = bb->value;
15977c478bd9Sstevel@tonic-gate }
15987c478bd9Sstevel@tonic-gate r = result->value;
15997c478bd9Sstevel@tonic-gate
16007c478bd9Sstevel@tonic-gate if (((alen == 1) && (a[0] == 0)) || ((blen == 1) && (b[0] == 0))) {
16017c478bd9Sstevel@tonic-gate result->len = 1;
16027c478bd9Sstevel@tonic-gate result->sign = 1;
16037c478bd9Sstevel@tonic-gate r[0] = 0;
16047c478bd9Sstevel@tonic-gate return (BIG_OK);
16057c478bd9Sstevel@tonic-gate }
16067c478bd9Sstevel@tonic-gate sign = aa->sign * bb->sign;
16077c478bd9Sstevel@tonic-gate if ((alen == 1) && (a[0] == 1)) {
1608b60f2a0bSfr41279 for (i = 0; i < blen; i++) {
1609b60f2a0bSfr41279 r[i] = b[i];
1610b60f2a0bSfr41279 }
16117c478bd9Sstevel@tonic-gate result->len = blen;
16127c478bd9Sstevel@tonic-gate result->sign = sign;
16137c478bd9Sstevel@tonic-gate return (BIG_OK);
16147c478bd9Sstevel@tonic-gate }
16157c478bd9Sstevel@tonic-gate if ((blen == 1) && (b[0] == 1)) {
1616b60f2a0bSfr41279 for (i = 0; i < alen; i++) {
1617b60f2a0bSfr41279 r[i] = a[i];
1618b60f2a0bSfr41279 }
16197c478bd9Sstevel@tonic-gate result->len = alen;
16207c478bd9Sstevel@tonic-gate result->sign = sign;
16217c478bd9Sstevel@tonic-gate return (BIG_OK);
16227c478bd9Sstevel@tonic-gate }
16237c478bd9Sstevel@tonic-gate
1624b60f2a0bSfr41279 if ((err = big_init1(&tmp1, rsize,
1625b60f2a0bSfr41279 tmp1value, arraysize(tmp1value))) != BIG_OK) {
16267c478bd9Sstevel@tonic-gate return (err);
1627b60f2a0bSfr41279 }
16287c478bd9Sstevel@tonic-gate t = tmp1.value;
16297c478bd9Sstevel@tonic-gate
1630b60f2a0bSfr41279 for (i = 0; i < rsize; i++) {
1631b60f2a0bSfr41279 t[i] = 0;
1632b60f2a0bSfr41279 }
1633b60f2a0bSfr41279
1634b60f2a0bSfr41279 if (diff == 0 && alen > 2) {
16357c478bd9Sstevel@tonic-gate BIG_SQR_VEC(t, a, alen);
1636b60f2a0bSfr41279 } else if (blen > 0) {
16377c478bd9Sstevel@tonic-gate BIG_MUL_VEC(t, a, alen, b, blen);
1638b60f2a0bSfr41279 }
16397c478bd9Sstevel@tonic-gate
1640b60f2a0bSfr41279 if (t[rsize - 1] == 0) {
1641b60f2a0bSfr41279 tmp1.len = rsize - 1;
1642b60f2a0bSfr41279 } else {
1643b60f2a0bSfr41279 tmp1.len = rsize;
1644b60f2a0bSfr41279 }
16458475e043SDan OpenSolaris Anderson
16468475e043SDan OpenSolaris Anderson err = big_copy(result, &tmp1);
16478475e043SDan OpenSolaris Anderson
16487c478bd9Sstevel@tonic-gate result->sign = sign;
16497c478bd9Sstevel@tonic-gate
1650b60f2a0bSfr41279 big_finish(&tmp1);
16517c478bd9Sstevel@tonic-gate
16528475e043SDan OpenSolaris Anderson return (err);
16537c478bd9Sstevel@tonic-gate }
16547c478bd9Sstevel@tonic-gate
16557c478bd9Sstevel@tonic-gate
16567c478bd9Sstevel@tonic-gate /*
16570a1ad920SDan OpenSolaris Anderson * big_mont_mul()
16580a1ad920SDan OpenSolaris Anderson * Montgomery multiplication.
16590a1ad920SDan OpenSolaris Anderson *
16600a1ad920SDan OpenSolaris Anderson * Caller must ensure that a < n, b < n, ret->size >= 2 * n->len + 1,
16610a1ad920SDan OpenSolaris Anderson * and that ret is not n.
16627c478bd9Sstevel@tonic-gate */
16637c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_mont_mul(BIGNUM * ret,BIGNUM * a,BIGNUM * b,BIGNUM * n,BIG_CHUNK_TYPE n0)1664b60f2a0bSfr41279 big_mont_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, BIGNUM *n, BIG_CHUNK_TYPE n0)
16657c478bd9Sstevel@tonic-gate {
16667c478bd9Sstevel@tonic-gate int i, j, nlen, needsubtract;
16670a1ad920SDan OpenSolaris Anderson BIG_CHUNK_TYPE *nn, *rr, *rrplusi;
1668b60f2a0bSfr41279 BIG_CHUNK_TYPE digit, c;
16697c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
16700a1ad920SDan OpenSolaris Anderson #ifdef __amd64
16710a1ad920SDan OpenSolaris Anderson #define BIG_CPU_UNKNOWN 0
16720a1ad920SDan OpenSolaris Anderson #define BIG_CPU_AMD 1
16730a1ad920SDan OpenSolaris Anderson #define BIG_CPU_INTEL 2
16740a1ad920SDan OpenSolaris Anderson static int big_cpu = BIG_CPU_UNKNOWN;
16750a1ad920SDan OpenSolaris Anderson BIG_CHUNK_TYPE carry[BIGTMPSIZE];
16760a1ad920SDan OpenSolaris Anderson
16770a1ad920SDan OpenSolaris Anderson if (big_cpu == BIG_CPU_UNKNOWN) {
16780a1ad920SDan OpenSolaris Anderson big_cpu = 1 + bignum_on_intel();
16790a1ad920SDan OpenSolaris Anderson }
16800a1ad920SDan OpenSolaris Anderson #endif /* __amd64 */
16817c478bd9Sstevel@tonic-gate
16827c478bd9Sstevel@tonic-gate nlen = n->len;
16837c478bd9Sstevel@tonic-gate nn = n->value;
16847c478bd9Sstevel@tonic-gate
16857c478bd9Sstevel@tonic-gate rr = ret->value;
16867c478bd9Sstevel@tonic-gate
1687b60f2a0bSfr41279 if ((err = big_mul(ret, a, b)) != BIG_OK) {
16887c478bd9Sstevel@tonic-gate return (err);
1689b60f2a0bSfr41279 }
16907c478bd9Sstevel@tonic-gate
16917c478bd9Sstevel@tonic-gate rr = ret->value;
1692b60f2a0bSfr41279 for (i = ret->len; i < 2 * nlen + 1; i++) {
1693b60f2a0bSfr41279 rr[i] = 0;
1694b60f2a0bSfr41279 }
16957c478bd9Sstevel@tonic-gate
16960a1ad920SDan OpenSolaris Anderson #ifdef __amd64 /* pipelining optimization for Intel 64, but not AMD64 */
16970a1ad920SDan OpenSolaris Anderson if ((big_cpu == BIG_CPU_INTEL) && (nlen <= BIGTMPSIZE)) {
16980a1ad920SDan OpenSolaris Anderson /*
16990a1ad920SDan OpenSolaris Anderson * Perform the following in two for loops to reduce the
17000a1ad920SDan OpenSolaris Anderson * dependency between computing the carryover bits with
17010a1ad920SDan OpenSolaris Anderson * BIG_MUL_ADD_VEC() and adding them, thus improving pipelining.
17020a1ad920SDan OpenSolaris Anderson */
17030a1ad920SDan OpenSolaris Anderson for (i = 0; i < nlen; i++) {
17040a1ad920SDan OpenSolaris Anderson rrplusi = rr + i;
17050a1ad920SDan OpenSolaris Anderson digit = *rrplusi * n0;
17060a1ad920SDan OpenSolaris Anderson carry[i] = BIG_MUL_ADD_VEC(rrplusi, nn, nlen, digit);
17070a1ad920SDan OpenSolaris Anderson }
17080a1ad920SDan OpenSolaris Anderson for (i = 0; i < nlen; i++) {
17090a1ad920SDan OpenSolaris Anderson j = i + nlen;
17100a1ad920SDan OpenSolaris Anderson rr[j] += carry[i];
17110a1ad920SDan OpenSolaris Anderson while (rr[j] < carry[i]) {
17120a1ad920SDan OpenSolaris Anderson rr[++j] += 1;
17130a1ad920SDan OpenSolaris Anderson carry[i] = 1;
17140a1ad920SDan OpenSolaris Anderson }
17150a1ad920SDan OpenSolaris Anderson }
17160a1ad920SDan OpenSolaris Anderson } else
17170a1ad920SDan OpenSolaris Anderson #endif /* __amd64 */
17180a1ad920SDan OpenSolaris Anderson { /* no pipelining optimization */
17190a1ad920SDan OpenSolaris Anderson for (i = 0; i < nlen; i++) {
17200a1ad920SDan OpenSolaris Anderson rrplusi = rr + i;
17210a1ad920SDan OpenSolaris Anderson digit = *rrplusi * n0;
17220a1ad920SDan OpenSolaris Anderson c = BIG_MUL_ADD_VEC(rrplusi, nn, nlen, digit);
17237c478bd9Sstevel@tonic-gate j = i + nlen;
17247c478bd9Sstevel@tonic-gate rr[j] += c;
17257c478bd9Sstevel@tonic-gate while (rr[j] < c) {
17260a1ad920SDan OpenSolaris Anderson rr[++j] += 1;
17277c478bd9Sstevel@tonic-gate c = 1;
17287c478bd9Sstevel@tonic-gate }
17297c478bd9Sstevel@tonic-gate }
17300a1ad920SDan OpenSolaris Anderson }
17317c478bd9Sstevel@tonic-gate
17327c478bd9Sstevel@tonic-gate needsubtract = 0;
17337c478bd9Sstevel@tonic-gate if ((rr[2 * nlen] != 0))
17347c478bd9Sstevel@tonic-gate needsubtract = 1;
17357c478bd9Sstevel@tonic-gate else {
17367c478bd9Sstevel@tonic-gate for (i = 2 * nlen - 1; i >= nlen; i--) {
17377c478bd9Sstevel@tonic-gate if (rr[i] > nn[i - nlen]) {
17387c478bd9Sstevel@tonic-gate needsubtract = 1;
17397c478bd9Sstevel@tonic-gate break;
1740b60f2a0bSfr41279 } else if (rr[i] < nn[i - nlen]) {
1741b60f2a0bSfr41279 break;
1742b60f2a0bSfr41279 }
17437c478bd9Sstevel@tonic-gate }
17447c478bd9Sstevel@tonic-gate }
17457c478bd9Sstevel@tonic-gate if (needsubtract)
17467c478bd9Sstevel@tonic-gate big_sub_vec(rr, rr + nlen, nn, nlen);
17477c478bd9Sstevel@tonic-gate else {
1748b60f2a0bSfr41279 for (i = 0; i < nlen; i++) {
17497c478bd9Sstevel@tonic-gate rr[i] = rr[i + nlen];
17507c478bd9Sstevel@tonic-gate }
1751b60f2a0bSfr41279 }
17528475e043SDan OpenSolaris Anderson
17538475e043SDan OpenSolaris Anderson /* Remove leading zeros, but keep at least 1 digit: */
17548475e043SDan OpenSolaris Anderson for (i = nlen - 1; (i > 0) && (rr[i] == 0); i--)
1755b60f2a0bSfr41279 ;
17567c478bd9Sstevel@tonic-gate ret->len = i + 1;
17577c478bd9Sstevel@tonic-gate
17587c478bd9Sstevel@tonic-gate return (BIG_OK);
17597c478bd9Sstevel@tonic-gate }
17607c478bd9Sstevel@tonic-gate
1761b60f2a0bSfr41279
1762b60f2a0bSfr41279 BIG_CHUNK_TYPE
big_n0(BIG_CHUNK_TYPE n)1763b60f2a0bSfr41279 big_n0(BIG_CHUNK_TYPE n)
17647c478bd9Sstevel@tonic-gate {
17657c478bd9Sstevel@tonic-gate int i;
1766b60f2a0bSfr41279 BIG_CHUNK_TYPE result, tmp;
17677c478bd9Sstevel@tonic-gate
17687c478bd9Sstevel@tonic-gate result = 0;
1769b60f2a0bSfr41279 tmp = BIG_CHUNK_ALLBITS;
1770b60f2a0bSfr41279 for (i = 0; i < BIG_CHUNK_SIZE; i++) {
17717c478bd9Sstevel@tonic-gate if ((tmp & 1) == 1) {
1772b60f2a0bSfr41279 result = (result >> 1) | BIG_CHUNK_HIGHBIT;
17737c478bd9Sstevel@tonic-gate tmp = tmp - n;
1774b60f2a0bSfr41279 } else {
1775b60f2a0bSfr41279 result = (result >> 1);
1776b60f2a0bSfr41279 }
17777c478bd9Sstevel@tonic-gate tmp = tmp >> 1;
17787c478bd9Sstevel@tonic-gate }
17797c478bd9Sstevel@tonic-gate
17807c478bd9Sstevel@tonic-gate return (result);
17817c478bd9Sstevel@tonic-gate }
17827c478bd9Sstevel@tonic-gate
17837c478bd9Sstevel@tonic-gate
17847c478bd9Sstevel@tonic-gate int
big_numbits(BIGNUM * n)17857c478bd9Sstevel@tonic-gate big_numbits(BIGNUM *n)
17867c478bd9Sstevel@tonic-gate {
17877c478bd9Sstevel@tonic-gate int i, j;
1788b60f2a0bSfr41279 BIG_CHUNK_TYPE t;
17897c478bd9Sstevel@tonic-gate
1790b60f2a0bSfr41279 for (i = n->len - 1; i > 0; i--) {
1791b60f2a0bSfr41279 if (n->value[i] != 0) {
1792b60f2a0bSfr41279 break;
1793b60f2a0bSfr41279 }
1794b60f2a0bSfr41279 }
17957c478bd9Sstevel@tonic-gate t = n->value[i];
1796b60f2a0bSfr41279 for (j = BIG_CHUNK_SIZE; j > 0; j--) {
1797b60f2a0bSfr41279 if ((t & BIG_CHUNK_HIGHBIT) == 0) {
17987c478bd9Sstevel@tonic-gate t = t << 1;
1799b60f2a0bSfr41279 } else {
1800b60f2a0bSfr41279 return (BIG_CHUNK_SIZE * i + j);
1801b60f2a0bSfr41279 }
18027c478bd9Sstevel@tonic-gate }
18037c478bd9Sstevel@tonic-gate return (0);
18047c478bd9Sstevel@tonic-gate }
18057c478bd9Sstevel@tonic-gate
1806b60f2a0bSfr41279
18077c478bd9Sstevel@tonic-gate /* caller must make sure that a < n */
18087c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_mont_rr(BIGNUM * result,BIGNUM * n)18097c478bd9Sstevel@tonic-gate big_mont_rr(BIGNUM *result, BIGNUM *n)
18107c478bd9Sstevel@tonic-gate {
18117c478bd9Sstevel@tonic-gate BIGNUM rr;
1812b60f2a0bSfr41279 BIG_CHUNK_TYPE rrvalue[BIGTMPSIZE];
18137c478bd9Sstevel@tonic-gate int len, i;
18147c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
18157c478bd9Sstevel@tonic-gate
18167c478bd9Sstevel@tonic-gate rr.malloced = 0;
18177c478bd9Sstevel@tonic-gate len = n->len;
18187c478bd9Sstevel@tonic-gate
18197c478bd9Sstevel@tonic-gate if ((err = big_init1(&rr, 2 * len + 1,
1820b60f2a0bSfr41279 rrvalue, arraysize(rrvalue))) != BIG_OK) {
18217c478bd9Sstevel@tonic-gate return (err);
18227c478bd9Sstevel@tonic-gate }
18237c478bd9Sstevel@tonic-gate
1824b60f2a0bSfr41279 for (i = 0; i < 2 * len; i++) {
1825b60f2a0bSfr41279 rr.value[i] = 0;
1826b60f2a0bSfr41279 }
1827b60f2a0bSfr41279 rr.value[2 * len] = 1;
1828b60f2a0bSfr41279 rr.len = 2 * len + 1;
1829b60f2a0bSfr41279 if ((err = big_div_pos(NULL, &rr, &rr, n)) != BIG_OK) {
1830b60f2a0bSfr41279 goto ret;
1831b60f2a0bSfr41279 }
1832b60f2a0bSfr41279 err = big_copy(result, &rr);
1833b60f2a0bSfr41279 ret:
1834b60f2a0bSfr41279 big_finish(&rr);
1835b60f2a0bSfr41279 return (err);
1836b60f2a0bSfr41279 }
1837b60f2a0bSfr41279
1838b60f2a0bSfr41279
18397c478bd9Sstevel@tonic-gate /* caller must make sure that a < n */
18407c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_mont_conv(BIGNUM * result,BIGNUM * a,BIGNUM * n,BIG_CHUNK_TYPE n0,BIGNUM * n_rr)1841b60f2a0bSfr41279 big_mont_conv(BIGNUM *result, BIGNUM *a, BIGNUM *n, BIG_CHUNK_TYPE n0,
1842b60f2a0bSfr41279 BIGNUM *n_rr)
18437c478bd9Sstevel@tonic-gate {
18447c478bd9Sstevel@tonic-gate BIGNUM rr;
1845b60f2a0bSfr41279 BIG_CHUNK_TYPE rrvalue[BIGTMPSIZE];
18467c478bd9Sstevel@tonic-gate int len, i;
18477c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
18487c478bd9Sstevel@tonic-gate
18497c478bd9Sstevel@tonic-gate rr.malloced = 0;
18507c478bd9Sstevel@tonic-gate len = n->len;
18517c478bd9Sstevel@tonic-gate
18527c478bd9Sstevel@tonic-gate if ((err = big_init1(&rr, 2 * len + 1, rrvalue, arraysize(rrvalue)))
1853b60f2a0bSfr41279 != BIG_OK) {
18547c478bd9Sstevel@tonic-gate return (err);
1855b60f2a0bSfr41279 }
18567c478bd9Sstevel@tonic-gate
18577c478bd9Sstevel@tonic-gate if (n_rr == NULL) {
1858b60f2a0bSfr41279 for (i = 0; i < 2 * len; i++) {
1859b60f2a0bSfr41279 rr.value[i] = 0;
1860b60f2a0bSfr41279 }
18617c478bd9Sstevel@tonic-gate rr.value[2 * len] = 1;
18627c478bd9Sstevel@tonic-gate rr.len = 2 * len + 1;
1863b60f2a0bSfr41279 if ((err = big_div_pos(NULL, &rr, &rr, n)) != BIG_OK) {
18647c478bd9Sstevel@tonic-gate goto ret;
1865b60f2a0bSfr41279 }
18667c478bd9Sstevel@tonic-gate n_rr = &rr;
18677c478bd9Sstevel@tonic-gate }
18687c478bd9Sstevel@tonic-gate
1869b60f2a0bSfr41279 if ((err = big_mont_mul(&rr, n_rr, a, n, n0)) != BIG_OK) {
18707c478bd9Sstevel@tonic-gate goto ret;
1871b60f2a0bSfr41279 }
18727c478bd9Sstevel@tonic-gate err = big_copy(result, &rr);
1873b60f2a0bSfr41279
18747c478bd9Sstevel@tonic-gate ret:
1875b60f2a0bSfr41279 big_finish(&rr);
18767c478bd9Sstevel@tonic-gate return (err);
18777c478bd9Sstevel@tonic-gate }
18787c478bd9Sstevel@tonic-gate
18797c478bd9Sstevel@tonic-gate
1880b60f2a0bSfr41279 #ifdef USE_FLOATING_POINT
1881b60f2a0bSfr41279 #define big_modexp_ncp_float big_modexp_ncp_sw
1882b60f2a0bSfr41279 #else
1883b60f2a0bSfr41279 #define big_modexp_ncp_int big_modexp_ncp_sw
1884b60f2a0bSfr41279 #endif
1885b60f2a0bSfr41279
18867c478bd9Sstevel@tonic-gate #define MAX_EXP_BIT_GROUP_SIZE 6
18877c478bd9Sstevel@tonic-gate #define APOWERS_MAX_SIZE (1 << (MAX_EXP_BIT_GROUP_SIZE - 1))
18887c478bd9Sstevel@tonic-gate
1889b60f2a0bSfr41279 /* ARGSUSED */
18907c478bd9Sstevel@tonic-gate static BIG_ERR_CODE
big_modexp_ncp_int(BIGNUM * result,BIGNUM * ma,BIGNUM * e,BIGNUM * n,BIGNUM * tmp,BIG_CHUNK_TYPE n0)1891b60f2a0bSfr41279 big_modexp_ncp_int(BIGNUM *result, BIGNUM *ma, BIGNUM *e, BIGNUM *n,
1892b60f2a0bSfr41279 BIGNUM *tmp, BIG_CHUNK_TYPE n0)
1893b60f2a0bSfr41279
18947c478bd9Sstevel@tonic-gate {
1895b60f2a0bSfr41279 BIGNUM apowers[APOWERS_MAX_SIZE];
1896b60f2a0bSfr41279 BIGNUM tmp1;
1897b60f2a0bSfr41279 BIG_CHUNK_TYPE tmp1value[BIGTMPSIZE];
1898b60f2a0bSfr41279 int i, j, k, l, m, p;
18998475e043SDan OpenSolaris Anderson uint32_t bit, bitind, bitcount, groupbits, apowerssize;
19008475e043SDan OpenSolaris Anderson uint32_t nbits;
19017c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
19027c478bd9Sstevel@tonic-gate
19037c478bd9Sstevel@tonic-gate nbits = big_numbits(e);
19047c478bd9Sstevel@tonic-gate if (nbits < 50) {
19057c478bd9Sstevel@tonic-gate groupbits = 1;
19067c478bd9Sstevel@tonic-gate apowerssize = 1;
19077c478bd9Sstevel@tonic-gate } else {
19087c478bd9Sstevel@tonic-gate groupbits = MAX_EXP_BIT_GROUP_SIZE;
19097c478bd9Sstevel@tonic-gate apowerssize = 1 << (groupbits - 1);
19107c478bd9Sstevel@tonic-gate }
19117c478bd9Sstevel@tonic-gate
1912b60f2a0bSfr41279
1913b60f2a0bSfr41279 if ((err = big_init1(&tmp1, 2 * n->len + 1,
1914b60f2a0bSfr41279 tmp1value, arraysize(tmp1value))) != BIG_OK) {
19157c478bd9Sstevel@tonic-gate return (err);
19167c478bd9Sstevel@tonic-gate }
19177c478bd9Sstevel@tonic-gate
19188475e043SDan OpenSolaris Anderson /* clear the malloced bit to help cleanup */
1919b60f2a0bSfr41279 for (i = 0; i < apowerssize; i++) {
1920b60f2a0bSfr41279 apowers[i].malloced = 0;
1921b60f2a0bSfr41279 }
19228475e043SDan OpenSolaris Anderson
1923b60f2a0bSfr41279 for (i = 0; i < apowerssize; i++) {
1924b60f2a0bSfr41279 if ((err = big_init1(&(apowers[i]), n->len, NULL, 0)) !=
1925b60f2a0bSfr41279 BIG_OK) {
1926b60f2a0bSfr41279 goto ret;
1927b60f2a0bSfr41279 }
1928b60f2a0bSfr41279 }
19297c478bd9Sstevel@tonic-gate
1930b60f2a0bSfr41279 (void) big_copy(&(apowers[0]), ma);
1931b60f2a0bSfr41279
1932b60f2a0bSfr41279 if ((err = big_mont_mul(&tmp1, ma, ma, n, n0)) != BIG_OK) {
1933b60f2a0bSfr41279 goto ret;
1934b60f2a0bSfr41279 }
1935b60f2a0bSfr41279 (void) big_copy(ma, &tmp1);
1936b60f2a0bSfr41279
1937b60f2a0bSfr41279 for (i = 1; i < apowerssize; i++) {
1938b60f2a0bSfr41279 if ((err = big_mont_mul(&tmp1, ma,
1939b60f2a0bSfr41279 &(apowers[i - 1]), n, n0)) != BIG_OK) {
1940b60f2a0bSfr41279 goto ret;
1941b60f2a0bSfr41279 }
1942b60f2a0bSfr41279 (void) big_copy(&apowers[i], &tmp1);
1943b60f2a0bSfr41279 }
1944b60f2a0bSfr41279
1945b60f2a0bSfr41279 bitind = nbits % BIG_CHUNK_SIZE;
1946b60f2a0bSfr41279 k = 0;
1947b60f2a0bSfr41279 l = 0;
1948b60f2a0bSfr41279 p = 0;
1949b60f2a0bSfr41279 bitcount = 0;
1950b60f2a0bSfr41279 for (i = nbits / BIG_CHUNK_SIZE; i >= 0; i--) {
1951b60f2a0bSfr41279 for (j = bitind - 1; j >= 0; j--) {
1952b60f2a0bSfr41279 bit = (e->value[i] >> j) & 1;
1953b60f2a0bSfr41279 if ((bitcount == 0) && (bit == 0)) {
1954b60f2a0bSfr41279 if ((err = big_mont_mul(tmp,
1955b60f2a0bSfr41279 tmp, tmp, n, n0)) != BIG_OK) {
1956b60f2a0bSfr41279 goto ret;
1957b60f2a0bSfr41279 }
19587c478bd9Sstevel@tonic-gate } else {
1959b60f2a0bSfr41279 bitcount++;
1960b60f2a0bSfr41279 p = p * 2 + bit;
1961b60f2a0bSfr41279 if (bit == 1) {
1962b60f2a0bSfr41279 k = k + l + 1;
1963b60f2a0bSfr41279 l = 0;
1964b60f2a0bSfr41279 } else {
1965b60f2a0bSfr41279 l++;
19667c478bd9Sstevel@tonic-gate }
1967b60f2a0bSfr41279 if (bitcount == groupbits) {
1968b60f2a0bSfr41279 for (m = 0; m < k; m++) {
1969b60f2a0bSfr41279 if ((err = big_mont_mul(tmp,
1970b60f2a0bSfr41279 tmp, tmp, n, n0)) !=
1971b60f2a0bSfr41279 BIG_OK) {
1972b60f2a0bSfr41279 goto ret;
1973b60f2a0bSfr41279 }
1974b60f2a0bSfr41279 }
1975b60f2a0bSfr41279 if ((err = big_mont_mul(tmp, tmp,
1976b60f2a0bSfr41279 &(apowers[p >> (l + 1)]),
1977b60f2a0bSfr41279 n, n0)) != BIG_OK) {
1978b60f2a0bSfr41279 goto ret;
1979b60f2a0bSfr41279 }
1980b60f2a0bSfr41279 for (m = 0; m < l; m++) {
1981b60f2a0bSfr41279 if ((err = big_mont_mul(tmp,
1982b60f2a0bSfr41279 tmp, tmp, n, n0)) !=
1983b60f2a0bSfr41279 BIG_OK) {
1984b60f2a0bSfr41279 goto ret;
1985b60f2a0bSfr41279 }
1986b60f2a0bSfr41279 }
1987b60f2a0bSfr41279 k = 0;
1988b60f2a0bSfr41279 l = 0;
1989b60f2a0bSfr41279 p = 0;
1990b60f2a0bSfr41279 bitcount = 0;
1991b60f2a0bSfr41279 }
1992b60f2a0bSfr41279 }
1993b60f2a0bSfr41279 }
1994b60f2a0bSfr41279 bitind = BIG_CHUNK_SIZE;
1995b60f2a0bSfr41279 }
19967c478bd9Sstevel@tonic-gate
1997b60f2a0bSfr41279 for (m = 0; m < k; m++) {
1998b60f2a0bSfr41279 if ((err = big_mont_mul(tmp, tmp, tmp, n, n0)) != BIG_OK) {
1999b60f2a0bSfr41279 goto ret;
2000b60f2a0bSfr41279 }
2001b60f2a0bSfr41279 }
2002b60f2a0bSfr41279 if (p != 0) {
2003b60f2a0bSfr41279 if ((err = big_mont_mul(tmp, tmp,
2004b60f2a0bSfr41279 &(apowers[p >> (l + 1)]), n, n0)) != BIG_OK) {
2005b60f2a0bSfr41279 goto ret;
2006b60f2a0bSfr41279 }
2007b60f2a0bSfr41279 }
2008b60f2a0bSfr41279 for (m = 0; m < l; m++) {
2009b60f2a0bSfr41279 if ((err = big_mont_mul(result, tmp, tmp, n, n0)) != BIG_OK) {
2010b60f2a0bSfr41279 goto ret;
2011b60f2a0bSfr41279 }
2012b60f2a0bSfr41279 }
20137c478bd9Sstevel@tonic-gate
2014b60f2a0bSfr41279 ret:
2015b60f2a0bSfr41279 for (i = apowerssize - 1; i >= 0; i--) {
2016b60f2a0bSfr41279 big_finish(&(apowers[i]));
2017b60f2a0bSfr41279 }
2018b60f2a0bSfr41279 big_finish(&tmp1);
2019b60f2a0bSfr41279
2020b60f2a0bSfr41279 return (err);
2021b60f2a0bSfr41279 }
2022b60f2a0bSfr41279
2023b60f2a0bSfr41279
2024b60f2a0bSfr41279 #ifdef USE_FLOATING_POINT
2025b60f2a0bSfr41279
2026b60f2a0bSfr41279 #ifdef _KERNEL
2027b60f2a0bSfr41279
2028b60f2a0bSfr41279 #include <sys/sysmacros.h>
2029b60f2a0bSfr41279 #include <sys/regset.h>
2030b60f2a0bSfr41279 #include <sys/fpu/fpusystm.h>
2031b60f2a0bSfr41279
2032b60f2a0bSfr41279 /* the alignment for block stores to save fp registers */
2033b60f2a0bSfr41279 #define FPR_ALIGN (64)
2034b60f2a0bSfr41279
2035b60f2a0bSfr41279 extern void big_savefp(kfpu_t *);
2036b60f2a0bSfr41279 extern void big_restorefp(kfpu_t *);
2037b60f2a0bSfr41279
2038b60f2a0bSfr41279 #endif /* _KERNEL */
2039b60f2a0bSfr41279
2040b60f2a0bSfr41279 /*
2041b60f2a0bSfr41279 * This version makes use of floating point for performance
2042b60f2a0bSfr41279 */
2043b60f2a0bSfr41279 static BIG_ERR_CODE
big_modexp_ncp_float(BIGNUM * result,BIGNUM * ma,BIGNUM * e,BIGNUM * n,BIGNUM * tmp,BIG_CHUNK_TYPE n0)2044b60f2a0bSfr41279 big_modexp_ncp_float(BIGNUM *result, BIGNUM *ma, BIGNUM *e, BIGNUM *n,
2045b60f2a0bSfr41279 BIGNUM *tmp, BIG_CHUNK_TYPE n0)
2046b60f2a0bSfr41279 {
2047b60f2a0bSfr41279
20488475e043SDan OpenSolaris Anderson int i, j, k, l, m, p;
20498475e043SDan OpenSolaris Anderson uint32_t bit, bitind, bitcount, nlen;
2050b60f2a0bSfr41279 double dn0;
2051b60f2a0bSfr41279 double *dn, *dt, *d16r, *d32r;
2052b60f2a0bSfr41279 uint32_t *nint, *prod;
2053b60f2a0bSfr41279 double *apowers[APOWERS_MAX_SIZE];
20548475e043SDan OpenSolaris Anderson uint32_t nbits, groupbits, apowerssize;
2055b60f2a0bSfr41279 BIG_ERR_CODE err = BIG_OK;
2056b60f2a0bSfr41279
2057b60f2a0bSfr41279 #ifdef _KERNEL
2058b60f2a0bSfr41279 uint8_t fpua[sizeof (kfpu_t) + FPR_ALIGN];
2059b60f2a0bSfr41279 kfpu_t *fpu;
2060b60f2a0bSfr41279
2061b60f2a0bSfr41279 #ifdef DEBUG
2062b60f2a0bSfr41279 if (!fpu_exists)
2063b60f2a0bSfr41279 return (BIG_GENERAL_ERR);
2064b60f2a0bSfr41279 #endif
2065b60f2a0bSfr41279
2066b60f2a0bSfr41279 fpu = (kfpu_t *)P2ROUNDUP((uintptr_t)fpua, FPR_ALIGN);
2067b60f2a0bSfr41279 big_savefp(fpu);
2068b60f2a0bSfr41279
2069b60f2a0bSfr41279 #endif /* _KERNEL */
2070b60f2a0bSfr41279
2071b60f2a0bSfr41279 nbits = big_numbits(e);
2072b60f2a0bSfr41279 if (nbits < 50) {
2073b60f2a0bSfr41279 groupbits = 1;
2074b60f2a0bSfr41279 apowerssize = 1;
2075b60f2a0bSfr41279 } else {
2076b60f2a0bSfr41279 groupbits = MAX_EXP_BIT_GROUP_SIZE;
2077b60f2a0bSfr41279 apowerssize = 1 << (groupbits - 1);
2078b60f2a0bSfr41279 }
2079b60f2a0bSfr41279
2080b60f2a0bSfr41279 nlen = (BIG_CHUNK_SIZE / 32) * n->len;
20817c478bd9Sstevel@tonic-gate dn0 = (double)(n0 & 0xffff);
20827c478bd9Sstevel@tonic-gate
20837c478bd9Sstevel@tonic-gate dn = dt = d16r = d32r = NULL;
20847c478bd9Sstevel@tonic-gate nint = prod = NULL;
20857c478bd9Sstevel@tonic-gate for (i = 0; i < apowerssize; i++) {
20867c478bd9Sstevel@tonic-gate apowers[i] = NULL;
20877c478bd9Sstevel@tonic-gate }
20887c478bd9Sstevel@tonic-gate
20897c478bd9Sstevel@tonic-gate if ((dn = big_malloc(nlen * sizeof (double))) == NULL) {
20907c478bd9Sstevel@tonic-gate err = BIG_NO_MEM;
20917c478bd9Sstevel@tonic-gate goto ret;
20927c478bd9Sstevel@tonic-gate }
20937c478bd9Sstevel@tonic-gate if ((dt = big_malloc((4 * nlen + 2) * sizeof (double))) == NULL) {
20947c478bd9Sstevel@tonic-gate err = BIG_NO_MEM;
20957c478bd9Sstevel@tonic-gate goto ret;
20967c478bd9Sstevel@tonic-gate }
20977c478bd9Sstevel@tonic-gate if ((nint = big_malloc(nlen * sizeof (uint32_t))) == NULL) {
20987c478bd9Sstevel@tonic-gate err = BIG_NO_MEM;
20997c478bd9Sstevel@tonic-gate goto ret;
21007c478bd9Sstevel@tonic-gate }
21017c478bd9Sstevel@tonic-gate if ((prod = big_malloc((nlen + 1) * sizeof (uint32_t))) == NULL) {
21027c478bd9Sstevel@tonic-gate err = BIG_NO_MEM;
21037c478bd9Sstevel@tonic-gate goto ret;
21047c478bd9Sstevel@tonic-gate }
21057c478bd9Sstevel@tonic-gate if ((d16r = big_malloc((2 * nlen + 1) * sizeof (double))) == NULL) {
21067c478bd9Sstevel@tonic-gate err = BIG_NO_MEM;
21077c478bd9Sstevel@tonic-gate goto ret;
21087c478bd9Sstevel@tonic-gate }
21097c478bd9Sstevel@tonic-gate if ((d32r = big_malloc(nlen * sizeof (double))) == NULL) {
21107c478bd9Sstevel@tonic-gate err = BIG_NO_MEM;
21117c478bd9Sstevel@tonic-gate goto ret;
21127c478bd9Sstevel@tonic-gate }
21137c478bd9Sstevel@tonic-gate for (i = 0; i < apowerssize; i++) {
21147c478bd9Sstevel@tonic-gate if ((apowers[i] = big_malloc((2 * nlen + 1) *
21157c478bd9Sstevel@tonic-gate sizeof (double))) == NULL) {
21167c478bd9Sstevel@tonic-gate err = BIG_NO_MEM;
21177c478bd9Sstevel@tonic-gate goto ret;
21187c478bd9Sstevel@tonic-gate }
21197c478bd9Sstevel@tonic-gate }
21207c478bd9Sstevel@tonic-gate
2121b60f2a0bSfr41279 #if (BIG_CHUNK_SIZE == 32)
2122b60f2a0bSfr41279 for (i = 0; i < ma->len; i++) {
2123b60f2a0bSfr41279 nint[i] = ma->value[i];
2124b60f2a0bSfr41279 }
2125b60f2a0bSfr41279 for (; i < nlen; i++) {
2126b60f2a0bSfr41279 nint[i] = 0;
2127b60f2a0bSfr41279 }
2128b60f2a0bSfr41279 #else
2129b60f2a0bSfr41279 for (i = 0; i < ma->len; i++) {
2130b60f2a0bSfr41279 nint[2 * i] = (uint32_t)(ma->value[i] & 0xffffffffULL);
2131b60f2a0bSfr41279 nint[2 * i + 1] = (uint32_t)(ma->value[i] >> 32);
2132b60f2a0bSfr41279 }
2133b60f2a0bSfr41279 for (i = ma->len * 2; i < nlen; i++) {
2134b60f2a0bSfr41279 nint[i] = 0;
2135b60f2a0bSfr41279 }
2136b60f2a0bSfr41279 #endif
21377c478bd9Sstevel@tonic-gate conv_i32_to_d32_and_d16(d32r, apowers[0], nint, nlen);
21387c478bd9Sstevel@tonic-gate
2139b60f2a0bSfr41279 #if (BIG_CHUNK_SIZE == 32)
2140b60f2a0bSfr41279 for (i = 0; i < n->len; i++) {
2141b60f2a0bSfr41279 nint[i] = n->value[i];
2142b60f2a0bSfr41279 }
2143b60f2a0bSfr41279 for (; i < nlen; i++) {
2144b60f2a0bSfr41279 nint[i] = 0;
2145b60f2a0bSfr41279 }
2146b60f2a0bSfr41279 #else
2147b60f2a0bSfr41279 for (i = 0; i < n->len; i++) {
2148b60f2a0bSfr41279 nint[2 * i] = (uint32_t)(n->value[i] & 0xffffffffULL);
2149b60f2a0bSfr41279 nint[2 * i + 1] = (uint32_t)(n->value[i] >> 32);
2150b60f2a0bSfr41279 }
2151b60f2a0bSfr41279 for (i = n->len * 2; i < nlen; i++) {
2152b60f2a0bSfr41279 nint[i] = 0;
2153b60f2a0bSfr41279 }
2154b60f2a0bSfr41279 #endif
21557c478bd9Sstevel@tonic-gate conv_i32_to_d32(dn, nint, nlen);
21567c478bd9Sstevel@tonic-gate
21577c478bd9Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, apowers[0], dt, dn, nint, nlen, dn0);
21587c478bd9Sstevel@tonic-gate conv_i32_to_d32(d32r, prod, nlen);
21597c478bd9Sstevel@tonic-gate for (i = 1; i < apowerssize; i++) {
21607c478bd9Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, apowers[i - 1],
21617c478bd9Sstevel@tonic-gate dt, dn, nint, nlen, dn0);
21627c478bd9Sstevel@tonic-gate conv_i32_to_d16(apowers[i], prod, nlen);
21637c478bd9Sstevel@tonic-gate }
21647c478bd9Sstevel@tonic-gate
2165b60f2a0bSfr41279 #if (BIG_CHUNK_SIZE == 32)
2166b60f2a0bSfr41279 for (i = 0; i < tmp->len; i++) {
2167b60f2a0bSfr41279 prod[i] = tmp->value[i];
2168b60f2a0bSfr41279 }
2169b60f2a0bSfr41279 for (; i < nlen + 1; i++) {
2170b60f2a0bSfr41279 prod[i] = 0;
2171b60f2a0bSfr41279 }
2172b60f2a0bSfr41279 #else
2173b60f2a0bSfr41279 for (i = 0; i < tmp->len; i++) {
2174b60f2a0bSfr41279 prod[2 * i] = (uint32_t)(tmp->value[i] & 0xffffffffULL);
2175b60f2a0bSfr41279 prod[2 * i + 1] = (uint32_t)(tmp->value[i] >> 32);
2176b60f2a0bSfr41279 }
2177b60f2a0bSfr41279 for (i = tmp->len * 2; i < nlen + 1; i++) {
2178b60f2a0bSfr41279 prod[i] = 0;
2179b60f2a0bSfr41279 }
2180b60f2a0bSfr41279 #endif
21817c478bd9Sstevel@tonic-gate
2182b60f2a0bSfr41279 bitind = nbits % BIG_CHUNK_SIZE;
21837c478bd9Sstevel@tonic-gate k = 0;
21847c478bd9Sstevel@tonic-gate l = 0;
21857c478bd9Sstevel@tonic-gate p = 0;
21867c478bd9Sstevel@tonic-gate bitcount = 0;
2187b60f2a0bSfr41279 for (i = nbits / BIG_CHUNK_SIZE; i >= 0; i--) {
21887c478bd9Sstevel@tonic-gate for (j = bitind - 1; j >= 0; j--) {
21897c478bd9Sstevel@tonic-gate bit = (e->value[i] >> j) & 1;
21907c478bd9Sstevel@tonic-gate if ((bitcount == 0) && (bit == 0)) {
21917c478bd9Sstevel@tonic-gate conv_i32_to_d32_and_d16(d32r, d16r,
21927c478bd9Sstevel@tonic-gate prod, nlen);
21937c478bd9Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, d16r,
21947c478bd9Sstevel@tonic-gate dt, dn, nint, nlen, dn0);
21957c478bd9Sstevel@tonic-gate } else {
21967c478bd9Sstevel@tonic-gate bitcount++;
21977c478bd9Sstevel@tonic-gate p = p * 2 + bit;
21987c478bd9Sstevel@tonic-gate if (bit == 1) {
21997c478bd9Sstevel@tonic-gate k = k + l + 1;
22007c478bd9Sstevel@tonic-gate l = 0;
22017c478bd9Sstevel@tonic-gate } else {
22027c478bd9Sstevel@tonic-gate l++;
22037c478bd9Sstevel@tonic-gate }
22047c478bd9Sstevel@tonic-gate if (bitcount == groupbits) {
22057c478bd9Sstevel@tonic-gate for (m = 0; m < k; m++) {
2206b60f2a0bSfr41279 conv_i32_to_d32_and_d16(d32r,
2207b60f2a0bSfr41279 d16r, prod, nlen);
22087c478bd9Sstevel@tonic-gate mont_mulf_noconv(prod, d32r,
22097c478bd9Sstevel@tonic-gate d16r, dt, dn, nint,
22107c478bd9Sstevel@tonic-gate nlen, dn0);
22117c478bd9Sstevel@tonic-gate }
22127c478bd9Sstevel@tonic-gate conv_i32_to_d32(d32r, prod, nlen);
22137c478bd9Sstevel@tonic-gate mont_mulf_noconv(prod, d32r,
22147c478bd9Sstevel@tonic-gate apowers[p >> (l + 1)],
22157c478bd9Sstevel@tonic-gate dt, dn, nint, nlen, dn0);
22167c478bd9Sstevel@tonic-gate for (m = 0; m < l; m++) {
2217b60f2a0bSfr41279 conv_i32_to_d32_and_d16(d32r,
2218b60f2a0bSfr41279 d16r, prod, nlen);
22197c478bd9Sstevel@tonic-gate mont_mulf_noconv(prod, d32r,
22207c478bd9Sstevel@tonic-gate d16r, dt, dn, nint,
22217c478bd9Sstevel@tonic-gate nlen, dn0);
22227c478bd9Sstevel@tonic-gate }
22237c478bd9Sstevel@tonic-gate k = 0;
22247c478bd9Sstevel@tonic-gate l = 0;
22257c478bd9Sstevel@tonic-gate p = 0;
22267c478bd9Sstevel@tonic-gate bitcount = 0;
22277c478bd9Sstevel@tonic-gate }
22287c478bd9Sstevel@tonic-gate }
22297c478bd9Sstevel@tonic-gate }
2230b60f2a0bSfr41279 bitind = BIG_CHUNK_SIZE;
22317c478bd9Sstevel@tonic-gate }
22327c478bd9Sstevel@tonic-gate
22337c478bd9Sstevel@tonic-gate for (m = 0; m < k; m++) {
22347c478bd9Sstevel@tonic-gate conv_i32_to_d32_and_d16(d32r, d16r, prod, nlen);
22357c478bd9Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, d16r, dt, dn, nint, nlen, dn0);
22367c478bd9Sstevel@tonic-gate }
22377c478bd9Sstevel@tonic-gate if (p != 0) {
22387c478bd9Sstevel@tonic-gate conv_i32_to_d32(d32r, prod, nlen);
22397c478bd9Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, apowers[p >> (l + 1)],
22407c478bd9Sstevel@tonic-gate dt, dn, nint, nlen, dn0);
22417c478bd9Sstevel@tonic-gate }
22427c478bd9Sstevel@tonic-gate for (m = 0; m < l; m++) {
22437c478bd9Sstevel@tonic-gate conv_i32_to_d32_and_d16(d32r, d16r, prod, nlen);
22447c478bd9Sstevel@tonic-gate mont_mulf_noconv(prod, d32r, d16r, dt, dn, nint, nlen, dn0);
22457c478bd9Sstevel@tonic-gate }
22467c478bd9Sstevel@tonic-gate
2247b60f2a0bSfr41279 #if (BIG_CHUNK_SIZE == 32)
2248b60f2a0bSfr41279 for (i = 0; i < nlen; i++) {
2249b60f2a0bSfr41279 result->value[i] = prod[i];
2250b60f2a0bSfr41279 }
2251b60f2a0bSfr41279 for (i = nlen - 1; (i > 0) && (prod[i] == 0); i--)
2252b60f2a0bSfr41279 ;
2253b60f2a0bSfr41279 #else
2254b60f2a0bSfr41279 for (i = 0; i < nlen / 2; i++) {
2255b60f2a0bSfr41279 result->value[i] = (uint64_t)(prod[2 * i]) +
2256b60f2a0bSfr41279 (((uint64_t)(prod[2 * i + 1])) << 32);
2257b60f2a0bSfr41279 }
2258b60f2a0bSfr41279 for (i = nlen / 2 - 1; (i > 0) && (result->value[i] == 0); i--)
2259b60f2a0bSfr41279 ;
2260b60f2a0bSfr41279 #endif
2261b60f2a0bSfr41279 result->len = i + 1;
2262b60f2a0bSfr41279
22637c478bd9Sstevel@tonic-gate ret:
22647c478bd9Sstevel@tonic-gate for (i = apowerssize - 1; i >= 0; i--) {
22657c478bd9Sstevel@tonic-gate if (apowers[i] != NULL)
22667c478bd9Sstevel@tonic-gate big_free(apowers[i], (2 * nlen + 1) * sizeof (double));
22677c478bd9Sstevel@tonic-gate }
2268b60f2a0bSfr41279 if (d32r != NULL) {
22697c478bd9Sstevel@tonic-gate big_free(d32r, nlen * sizeof (double));
2270b60f2a0bSfr41279 }
2271b60f2a0bSfr41279 if (d16r != NULL) {
22727c478bd9Sstevel@tonic-gate big_free(d16r, (2 * nlen + 1) * sizeof (double));
2273b60f2a0bSfr41279 }
2274b60f2a0bSfr41279 if (prod != NULL) {
22757c478bd9Sstevel@tonic-gate big_free(prod, (nlen + 1) * sizeof (uint32_t));
2276b60f2a0bSfr41279 }
2277b60f2a0bSfr41279 if (nint != NULL) {
22787c478bd9Sstevel@tonic-gate big_free(nint, nlen * sizeof (uint32_t));
2279b60f2a0bSfr41279 }
2280b60f2a0bSfr41279 if (dt != NULL) {
22817c478bd9Sstevel@tonic-gate big_free(dt, (4 * nlen + 2) * sizeof (double));
2282b60f2a0bSfr41279 }
2283b60f2a0bSfr41279 if (dn != NULL) {
22847c478bd9Sstevel@tonic-gate big_free(dn, nlen * sizeof (double));
22857c478bd9Sstevel@tonic-gate }
22867c478bd9Sstevel@tonic-gate
22877c478bd9Sstevel@tonic-gate #ifdef _KERNEL
2288b60f2a0bSfr41279 big_restorefp(fpu);
22897c478bd9Sstevel@tonic-gate #endif
22907c478bd9Sstevel@tonic-gate
22917c478bd9Sstevel@tonic-gate return (err);
22927c478bd9Sstevel@tonic-gate }
22937c478bd9Sstevel@tonic-gate
22947c478bd9Sstevel@tonic-gate #endif /* USE_FLOATING_POINT */
22957c478bd9Sstevel@tonic-gate
22967c478bd9Sstevel@tonic-gate
22977c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_modexp_ext(BIGNUM * result,BIGNUM * a,BIGNUM * e,BIGNUM * n,BIGNUM * n_rr,big_modexp_ncp_info_t * info)2298b60f2a0bSfr41279 big_modexp_ext(BIGNUM *result, BIGNUM *a, BIGNUM *e, BIGNUM *n, BIGNUM *n_rr,
2299b60f2a0bSfr41279 big_modexp_ncp_info_t *info)
2300b60f2a0bSfr41279 {
2301b60f2a0bSfr41279 BIGNUM ma, tmp, rr;
2302b60f2a0bSfr41279 BIG_CHUNK_TYPE mavalue[BIGTMPSIZE];
2303b60f2a0bSfr41279 BIG_CHUNK_TYPE tmpvalue[BIGTMPSIZE];
2304b60f2a0bSfr41279 BIG_CHUNK_TYPE rrvalue[BIGTMPSIZE];
2305b60f2a0bSfr41279 BIG_ERR_CODE err;
2306b60f2a0bSfr41279 BIG_CHUNK_TYPE n0;
2307b60f2a0bSfr41279
2308b60f2a0bSfr41279 if ((err = big_init1(&ma, n->len, mavalue, arraysize(mavalue))) !=
2309b60f2a0bSfr41279 BIG_OK) {
2310b60f2a0bSfr41279 return (err);
2311b60f2a0bSfr41279 }
2312b60f2a0bSfr41279 ma.len = 1;
2313b60f2a0bSfr41279 ma.value[0] = 0;
2314b60f2a0bSfr41279
2315b60f2a0bSfr41279 if ((err = big_init1(&tmp, 2 * n->len + 1,
2316b60f2a0bSfr41279 tmpvalue, arraysize(tmpvalue))) != BIG_OK) {
2317b60f2a0bSfr41279 goto ret1;
2318b60f2a0bSfr41279 }
2319b60f2a0bSfr41279
23208475e043SDan OpenSolaris Anderson /* clear the malloced bit to help cleanup */
2321b60f2a0bSfr41279 rr.malloced = 0;
23228475e043SDan OpenSolaris Anderson
2323b60f2a0bSfr41279 if (n_rr == NULL) {
2324b60f2a0bSfr41279 if ((err = big_init1(&rr, 2 * n->len + 1,
2325b60f2a0bSfr41279 rrvalue, arraysize(rrvalue))) != BIG_OK) {
2326b60f2a0bSfr41279 goto ret2;
2327b60f2a0bSfr41279 }
2328b60f2a0bSfr41279 if (big_mont_rr(&rr, n) != BIG_OK) {
2329b60f2a0bSfr41279 goto ret;
2330b60f2a0bSfr41279 }
2331b60f2a0bSfr41279 n_rr = &rr;
2332b60f2a0bSfr41279 }
2333b60f2a0bSfr41279
2334b60f2a0bSfr41279 n0 = big_n0(n->value[0]);
2335b60f2a0bSfr41279
2336b60f2a0bSfr41279 if (big_cmp_abs(a, n) > 0) {
2337b60f2a0bSfr41279 if ((err = big_div_pos(NULL, &ma, a, n)) != BIG_OK) {
2338b60f2a0bSfr41279 goto ret;
2339b60f2a0bSfr41279 }
2340b60f2a0bSfr41279 err = big_mont_conv(&ma, &ma, n, n0, n_rr);
2341b60f2a0bSfr41279 } else {
2342b60f2a0bSfr41279 err = big_mont_conv(&ma, a, n, n0, n_rr);
2343b60f2a0bSfr41279 }
2344b60f2a0bSfr41279 if (err != BIG_OK) {
2345b60f2a0bSfr41279 goto ret;
2346b60f2a0bSfr41279 }
2347b60f2a0bSfr41279
2348b60f2a0bSfr41279 tmp.len = 1;
2349b60f2a0bSfr41279 tmp.value[0] = 1;
2350b60f2a0bSfr41279 if ((err = big_mont_conv(&tmp, &tmp, n, n0, n_rr)) != BIG_OK) {
2351b60f2a0bSfr41279 goto ret;
2352b60f2a0bSfr41279 }
2353b60f2a0bSfr41279
2354b60f2a0bSfr41279 if ((info != NULL) && (info->func != NULL)) {
2355b60f2a0bSfr41279 err = (*(info->func))(&tmp, &ma, e, n, &tmp, n0,
2356b60f2a0bSfr41279 info->ncp, info->reqp);
2357b60f2a0bSfr41279 } else {
2358b60f2a0bSfr41279 err = big_modexp_ncp_sw(&tmp, &ma, e, n, &tmp, n0);
2359b60f2a0bSfr41279 }
2360b60f2a0bSfr41279 if (err != BIG_OK) {
2361b60f2a0bSfr41279 goto ret;
2362b60f2a0bSfr41279 }
2363b60f2a0bSfr41279
2364b60f2a0bSfr41279 ma.value[0] = 1;
2365b60f2a0bSfr41279 ma.len = 1;
2366b60f2a0bSfr41279 if ((err = big_mont_mul(&tmp, &tmp, &ma, n, n0)) != BIG_OK) {
2367b60f2a0bSfr41279 goto ret;
2368b60f2a0bSfr41279 }
2369b60f2a0bSfr41279 err = big_copy(result, &tmp);
2370b60f2a0bSfr41279
2371b60f2a0bSfr41279 ret:
2372b60f2a0bSfr41279 if (rr.malloced) {
2373b60f2a0bSfr41279 big_finish(&rr);
2374b60f2a0bSfr41279 }
2375b60f2a0bSfr41279 ret2:
2376b60f2a0bSfr41279 big_finish(&tmp);
2377b60f2a0bSfr41279 ret1:
2378b60f2a0bSfr41279 big_finish(&ma);
2379b60f2a0bSfr41279
2380b60f2a0bSfr41279 return (err);
2381b60f2a0bSfr41279 }
2382b60f2a0bSfr41279
2383b60f2a0bSfr41279 BIG_ERR_CODE
big_modexp(BIGNUM * result,BIGNUM * a,BIGNUM * e,BIGNUM * n,BIGNUM * n_rr)2384b60f2a0bSfr41279 big_modexp(BIGNUM *result, BIGNUM *a, BIGNUM *e, BIGNUM *n, BIGNUM *n_rr)
2385b60f2a0bSfr41279 {
2386b60f2a0bSfr41279 return (big_modexp_ext(result, a, e, n, n_rr, NULL));
2387b60f2a0bSfr41279 }
2388b60f2a0bSfr41279
2389b60f2a0bSfr41279
2390b60f2a0bSfr41279 BIG_ERR_CODE
big_modexp_crt_ext(BIGNUM * result,BIGNUM * a,BIGNUM * dmodpminus1,BIGNUM * dmodqminus1,BIGNUM * p,BIGNUM * q,BIGNUM * pinvmodq,BIGNUM * p_rr,BIGNUM * q_rr,big_modexp_ncp_info_t * info)2391b60f2a0bSfr41279 big_modexp_crt_ext(BIGNUM *result, BIGNUM *a, BIGNUM *dmodpminus1,
23927c478bd9Sstevel@tonic-gate BIGNUM *dmodqminus1, BIGNUM *p, BIGNUM *q, BIGNUM *pinvmodq,
2393b60f2a0bSfr41279 BIGNUM *p_rr, BIGNUM *q_rr, big_modexp_ncp_info_t *info)
23947c478bd9Sstevel@tonic-gate {
23957c478bd9Sstevel@tonic-gate BIGNUM ap, aq, tmp;
23967c478bd9Sstevel@tonic-gate int alen, biglen, sign;
23977c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
23987c478bd9Sstevel@tonic-gate
2399b60f2a0bSfr41279 if (p->len > q->len) {
2400b60f2a0bSfr41279 biglen = p->len;
2401b60f2a0bSfr41279 } else {
2402b60f2a0bSfr41279 biglen = q->len;
2403b60f2a0bSfr41279 }
24047c478bd9Sstevel@tonic-gate
2405b60f2a0bSfr41279 if ((err = big_init1(&ap, p->len, NULL, 0)) != BIG_OK) {
24067c478bd9Sstevel@tonic-gate return (err);
2407b60f2a0bSfr41279 }
2408b60f2a0bSfr41279 if ((err = big_init1(&aq, q->len, NULL, 0)) != BIG_OK) {
24097c478bd9Sstevel@tonic-gate goto ret1;
2410b60f2a0bSfr41279 }
2411b60f2a0bSfr41279 if ((err = big_init1(&tmp, biglen + q->len + 1, NULL, 0)) != BIG_OK) {
24127c478bd9Sstevel@tonic-gate goto ret2;
2413b60f2a0bSfr41279 }
24147c478bd9Sstevel@tonic-gate
24157c478bd9Sstevel@tonic-gate /*
24167c478bd9Sstevel@tonic-gate * check whether a is too short - to avoid timing attacks
24177c478bd9Sstevel@tonic-gate */
24187c478bd9Sstevel@tonic-gate alen = a->len;
24197c478bd9Sstevel@tonic-gate while ((alen > p->len) && (a->value[alen - 1] == 0)) {
24207c478bd9Sstevel@tonic-gate alen--;
24217c478bd9Sstevel@tonic-gate }
24227c478bd9Sstevel@tonic-gate if (alen < p->len + q->len) {
24237c478bd9Sstevel@tonic-gate /*
24247c478bd9Sstevel@tonic-gate * a is too short, add p*q to it before
24257c478bd9Sstevel@tonic-gate * taking it modulo p and q
24267c478bd9Sstevel@tonic-gate * this will also affect timing, but this difference
24277c478bd9Sstevel@tonic-gate * does not depend on p or q, only on a
24287c478bd9Sstevel@tonic-gate * (in "normal" operation, this path will never be
24297c478bd9Sstevel@tonic-gate * taken, so it is not a performance penalty
24307c478bd9Sstevel@tonic-gate */
2431b60f2a0bSfr41279 if ((err = big_mul(&tmp, p, q)) != BIG_OK) {
24327c478bd9Sstevel@tonic-gate goto ret;
24337c478bd9Sstevel@tonic-gate }
2434b60f2a0bSfr41279 if ((err = big_add(&tmp, &tmp, a)) != BIG_OK) {
2435b60f2a0bSfr41279 goto ret;
2436b60f2a0bSfr41279 }
2437b60f2a0bSfr41279 if ((err = big_div_pos(NULL, &ap, &tmp, p)) != BIG_OK) {
2438b60f2a0bSfr41279 goto ret;
2439b60f2a0bSfr41279 }
2440b60f2a0bSfr41279 if ((err = big_div_pos(NULL, &aq, &tmp, q)) != BIG_OK) {
2441b60f2a0bSfr41279 goto ret;
2442b60f2a0bSfr41279 }
2443b60f2a0bSfr41279 } else {
2444b60f2a0bSfr41279 if ((err = big_div_pos(NULL, &ap, a, p)) != BIG_OK) {
2445b60f2a0bSfr41279 goto ret;
2446b60f2a0bSfr41279 }
2447b60f2a0bSfr41279 if ((err = big_div_pos(NULL, &aq, a, q)) != BIG_OK) {
2448b60f2a0bSfr41279 goto ret;
2449b60f2a0bSfr41279 }
2450b60f2a0bSfr41279 }
24517c478bd9Sstevel@tonic-gate
2452b60f2a0bSfr41279 if ((err = big_modexp_ext(&ap, &ap, dmodpminus1, p, p_rr, info)) !=
2453b60f2a0bSfr41279 BIG_OK) {
24547c478bd9Sstevel@tonic-gate goto ret;
2455b60f2a0bSfr41279 }
2456b60f2a0bSfr41279 if ((err = big_modexp_ext(&aq, &aq, dmodqminus1, q, q_rr, info)) !=
2457b60f2a0bSfr41279 BIG_OK) {
24587c478bd9Sstevel@tonic-gate goto ret;
2459b60f2a0bSfr41279 }
2460b60f2a0bSfr41279 if ((err = big_sub(&tmp, &aq, &ap)) != BIG_OK) {
24617c478bd9Sstevel@tonic-gate goto ret;
2462b60f2a0bSfr41279 }
2463b60f2a0bSfr41279 if ((err = big_mul(&tmp, &tmp, pinvmodq)) != BIG_OK) {
24647c478bd9Sstevel@tonic-gate goto ret;
2465b60f2a0bSfr41279 }
24667c478bd9Sstevel@tonic-gate sign = tmp.sign;
24677c478bd9Sstevel@tonic-gate tmp.sign = 1;
2468b60f2a0bSfr41279 if ((err = big_div_pos(NULL, &aq, &tmp, q)) != BIG_OK) {
24697c478bd9Sstevel@tonic-gate goto ret;
2470b60f2a0bSfr41279 }
24717c478bd9Sstevel@tonic-gate if ((sign == -1) && (!big_is_zero(&aq))) {
24727c478bd9Sstevel@tonic-gate (void) big_sub_pos(&aq, q, &aq);
24737c478bd9Sstevel@tonic-gate }
2474b60f2a0bSfr41279 if ((err = big_mul(&tmp, &aq, p)) != BIG_OK) {
24757c478bd9Sstevel@tonic-gate goto ret;
2476b60f2a0bSfr41279 }
24777c478bd9Sstevel@tonic-gate err = big_add_abs(result, &ap, &tmp);
24787c478bd9Sstevel@tonic-gate
24797c478bd9Sstevel@tonic-gate ret:
24807c478bd9Sstevel@tonic-gate big_finish(&tmp);
24817c478bd9Sstevel@tonic-gate ret2:
24827c478bd9Sstevel@tonic-gate big_finish(&aq);
24837c478bd9Sstevel@tonic-gate ret1:
24847c478bd9Sstevel@tonic-gate big_finish(&ap);
24857c478bd9Sstevel@tonic-gate
24867c478bd9Sstevel@tonic-gate return (err);
24877c478bd9Sstevel@tonic-gate }
24887c478bd9Sstevel@tonic-gate
24897c478bd9Sstevel@tonic-gate
2490b60f2a0bSfr41279 BIG_ERR_CODE
big_modexp_crt(BIGNUM * result,BIGNUM * a,BIGNUM * dmodpminus1,BIGNUM * dmodqminus1,BIGNUM * p,BIGNUM * q,BIGNUM * pinvmodq,BIGNUM * p_rr,BIGNUM * q_rr)2491b60f2a0bSfr41279 big_modexp_crt(BIGNUM *result, BIGNUM *a, BIGNUM *dmodpminus1,
2492b60f2a0bSfr41279 BIGNUM *dmodqminus1, BIGNUM *p, BIGNUM *q, BIGNUM *pinvmodq,
2493b60f2a0bSfr41279 BIGNUM *p_rr, BIGNUM *q_rr)
2494b60f2a0bSfr41279 {
2495b60f2a0bSfr41279 return (big_modexp_crt_ext(result, a, dmodpminus1, dmodqminus1,
2496b60f2a0bSfr41279 p, q, pinvmodq, p_rr, q_rr, NULL));
2497b60f2a0bSfr41279 }
24987c478bd9Sstevel@tonic-gate
24997c478bd9Sstevel@tonic-gate
2500b60f2a0bSfr41279 static BIG_CHUNK_TYPE onearr[1] = {(BIG_CHUNK_TYPE)1};
25011e49577aSRod Evans #if !defined(NO_BIG_ONE)
2502b60f2a0bSfr41279 BIGNUM big_One = {1, 1, 1, 0, onearr};
25031e49577aSRod Evans #endif
2504b60f2a0bSfr41279
2505b60f2a0bSfr41279 static BIG_CHUNK_TYPE twoarr[1] = {(BIG_CHUNK_TYPE)2};
25061e49577aSRod Evans #if !defined(NO_BIG_TWO)
2507b60f2a0bSfr41279 BIGNUM big_Two = {1, 1, 1, 0, twoarr};
25081e49577aSRod Evans #endif
2509b60f2a0bSfr41279
2510b60f2a0bSfr41279 static BIG_CHUNK_TYPE fourarr[1] = {(BIG_CHUNK_TYPE)4};
2511b60f2a0bSfr41279 static BIGNUM big_Four = {1, 1, 1, 0, fourarr};
2512b60f2a0bSfr41279
25137c478bd9Sstevel@tonic-gate
25147c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_sqrt_pos(BIGNUM * result,BIGNUM * n)25157c478bd9Sstevel@tonic-gate big_sqrt_pos(BIGNUM *result, BIGNUM *n)
25167c478bd9Sstevel@tonic-gate {
25177c478bd9Sstevel@tonic-gate BIGNUM *high, *low, *mid, *t;
25187c478bd9Sstevel@tonic-gate BIGNUM t1, t2, t3, prod;
2519b60f2a0bSfr41279 BIG_CHUNK_TYPE t1value[BIGTMPSIZE];
2520b60f2a0bSfr41279 BIG_CHUNK_TYPE t2value[BIGTMPSIZE];
2521b60f2a0bSfr41279 BIG_CHUNK_TYPE t3value[BIGTMPSIZE];
2522b60f2a0bSfr41279 BIG_CHUNK_TYPE prodvalue[BIGTMPSIZE];
25238475e043SDan OpenSolaris Anderson int i, diff;
25248475e043SDan OpenSolaris Anderson uint32_t nbits, nrootbits, highbits;
25257c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
25267c478bd9Sstevel@tonic-gate
25277c478bd9Sstevel@tonic-gate nbits = big_numbits(n);
25287c478bd9Sstevel@tonic-gate
25297c478bd9Sstevel@tonic-gate if ((err = big_init1(&t1, n->len + 1,
25307c478bd9Sstevel@tonic-gate t1value, arraysize(t1value))) != BIG_OK)
25317c478bd9Sstevel@tonic-gate return (err);
25327c478bd9Sstevel@tonic-gate if ((err = big_init1(&t2, n->len + 1,
25337c478bd9Sstevel@tonic-gate t2value, arraysize(t2value))) != BIG_OK)
25347c478bd9Sstevel@tonic-gate goto ret1;
25357c478bd9Sstevel@tonic-gate if ((err = big_init1(&t3, n->len + 1,
25367c478bd9Sstevel@tonic-gate t3value, arraysize(t3value))) != BIG_OK)
25377c478bd9Sstevel@tonic-gate goto ret2;
25387c478bd9Sstevel@tonic-gate if ((err = big_init1(&prod, n->len + 1,
25397c478bd9Sstevel@tonic-gate prodvalue, arraysize(prodvalue))) != BIG_OK)
25407c478bd9Sstevel@tonic-gate goto ret3;
25417c478bd9Sstevel@tonic-gate
25427c478bd9Sstevel@tonic-gate nrootbits = (nbits + 1) / 2;
2543b60f2a0bSfr41279 t1.len = t2.len = t3.len = (nrootbits - 1) / BIG_CHUNK_SIZE + 1;
25447c478bd9Sstevel@tonic-gate for (i = 0; i < t1.len; i++) {
25457c478bd9Sstevel@tonic-gate t1.value[i] = 0;
2546b60f2a0bSfr41279 t2.value[i] = BIG_CHUNK_ALLBITS;
25477c478bd9Sstevel@tonic-gate }
2548b60f2a0bSfr41279 highbits = nrootbits - BIG_CHUNK_SIZE * (t1.len - 1);
2549b60f2a0bSfr41279 if (highbits == BIG_CHUNK_SIZE) {
2550b60f2a0bSfr41279 t1.value[t1.len - 1] = BIG_CHUNK_HIGHBIT;
2551b60f2a0bSfr41279 t2.value[t2.len - 1] = BIG_CHUNK_ALLBITS;
25527c478bd9Sstevel@tonic-gate } else {
2553b60f2a0bSfr41279 t1.value[t1.len - 1] = (BIG_CHUNK_TYPE)1 << (highbits - 1);
25547c478bd9Sstevel@tonic-gate t2.value[t2.len - 1] = 2 * t1.value[t1.len - 1] - 1;
25557c478bd9Sstevel@tonic-gate }
2556b60f2a0bSfr41279
25577c478bd9Sstevel@tonic-gate high = &t2;
25587c478bd9Sstevel@tonic-gate low = &t1;
25597c478bd9Sstevel@tonic-gate mid = &t3;
25607c478bd9Sstevel@tonic-gate
2561b60f2a0bSfr41279 if ((err = big_mul(&prod, high, high)) != BIG_OK) {
25627c478bd9Sstevel@tonic-gate goto ret;
2563b60f2a0bSfr41279 }
25647c478bd9Sstevel@tonic-gate diff = big_cmp_abs(&prod, n);
25657c478bd9Sstevel@tonic-gate if (diff <= 0) {
25667c478bd9Sstevel@tonic-gate err = big_copy(result, high);
25677c478bd9Sstevel@tonic-gate goto ret;
25687c478bd9Sstevel@tonic-gate }
25697c478bd9Sstevel@tonic-gate
25707c478bd9Sstevel@tonic-gate (void) big_sub_pos(mid, high, low);
2571b60f2a0bSfr41279 while (big_cmp_abs(&big_One, mid) != 0) {
25727c478bd9Sstevel@tonic-gate (void) big_add_abs(mid, high, low);
25737c478bd9Sstevel@tonic-gate (void) big_half_pos(mid, mid);
25747c478bd9Sstevel@tonic-gate if ((err = big_mul(&prod, mid, mid)) != BIG_OK)
25757c478bd9Sstevel@tonic-gate goto ret;
25767c478bd9Sstevel@tonic-gate diff = big_cmp_abs(&prod, n);
25777c478bd9Sstevel@tonic-gate if (diff > 0) {
25787c478bd9Sstevel@tonic-gate t = high;
25797c478bd9Sstevel@tonic-gate high = mid;
25807c478bd9Sstevel@tonic-gate mid = t;
25817c478bd9Sstevel@tonic-gate } else if (diff < 0) {
25827c478bd9Sstevel@tonic-gate t = low;
25837c478bd9Sstevel@tonic-gate low = mid;
25847c478bd9Sstevel@tonic-gate mid = t;
25857c478bd9Sstevel@tonic-gate } else {
25867c478bd9Sstevel@tonic-gate err = big_copy(result, low);
25877c478bd9Sstevel@tonic-gate goto ret;
25887c478bd9Sstevel@tonic-gate }
25897c478bd9Sstevel@tonic-gate (void) big_sub_pos(mid, high, low);
25907c478bd9Sstevel@tonic-gate }
25917c478bd9Sstevel@tonic-gate
25927c478bd9Sstevel@tonic-gate err = big_copy(result, low);
25937c478bd9Sstevel@tonic-gate ret:
25947c478bd9Sstevel@tonic-gate if (prod.malloced) big_finish(&prod);
25957c478bd9Sstevel@tonic-gate ret3:
25967c478bd9Sstevel@tonic-gate if (t3.malloced) big_finish(&t3);
25977c478bd9Sstevel@tonic-gate ret2:
25987c478bd9Sstevel@tonic-gate if (t2.malloced) big_finish(&t2);
25997c478bd9Sstevel@tonic-gate ret1:
26007c478bd9Sstevel@tonic-gate if (t1.malloced) big_finish(&t1);
26017c478bd9Sstevel@tonic-gate
26027c478bd9Sstevel@tonic-gate return (err);
26037c478bd9Sstevel@tonic-gate }
26047c478bd9Sstevel@tonic-gate
26057c478bd9Sstevel@tonic-gate
26067c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_Jacobi_pos(int * jac,BIGNUM * nn,BIGNUM * mm)26077c478bd9Sstevel@tonic-gate big_Jacobi_pos(int *jac, BIGNUM *nn, BIGNUM *mm)
26087c478bd9Sstevel@tonic-gate {
26097c478bd9Sstevel@tonic-gate BIGNUM *t, *tmp2, *m, *n;
26107c478bd9Sstevel@tonic-gate BIGNUM t1, t2, t3;
2611b60f2a0bSfr41279 BIG_CHUNK_TYPE t1value[BIGTMPSIZE];
2612b60f2a0bSfr41279 BIG_CHUNK_TYPE t2value[BIGTMPSIZE];
2613b60f2a0bSfr41279 BIG_CHUNK_TYPE t3value[BIGTMPSIZE];
26147c478bd9Sstevel@tonic-gate int len, err;
26157c478bd9Sstevel@tonic-gate
26167c478bd9Sstevel@tonic-gate if (big_is_zero(nn) ||
26177c478bd9Sstevel@tonic-gate (((nn->value[0] & 1) | (mm->value[0] & 1)) == 0)) {
26187c478bd9Sstevel@tonic-gate *jac = 0;
26197c478bd9Sstevel@tonic-gate return (BIG_OK);
26207c478bd9Sstevel@tonic-gate }
26217c478bd9Sstevel@tonic-gate
2622b60f2a0bSfr41279 if (nn->len > mm->len) {
2623b60f2a0bSfr41279 len = nn->len;
2624b60f2a0bSfr41279 } else {
2625b60f2a0bSfr41279 len = mm->len;
2626b60f2a0bSfr41279 }
26277c478bd9Sstevel@tonic-gate
26287c478bd9Sstevel@tonic-gate if ((err = big_init1(&t1, len,
2629b60f2a0bSfr41279 t1value, arraysize(t1value))) != BIG_OK) {
26307c478bd9Sstevel@tonic-gate return (err);
2631b60f2a0bSfr41279 }
26327c478bd9Sstevel@tonic-gate if ((err = big_init1(&t2, len,
2633b60f2a0bSfr41279 t2value, arraysize(t2value))) != BIG_OK) {
26347c478bd9Sstevel@tonic-gate goto ret1;
2635b60f2a0bSfr41279 }
26367c478bd9Sstevel@tonic-gate if ((err = big_init1(&t3, len,
2637b60f2a0bSfr41279 t3value, arraysize(t3value))) != BIG_OK) {
26387c478bd9Sstevel@tonic-gate goto ret2;
2639b60f2a0bSfr41279 }
26407c478bd9Sstevel@tonic-gate
26417c478bd9Sstevel@tonic-gate n = &t1;
26427c478bd9Sstevel@tonic-gate m = &t2;
26437c478bd9Sstevel@tonic-gate tmp2 = &t3;
26447c478bd9Sstevel@tonic-gate
26457c478bd9Sstevel@tonic-gate (void) big_copy(n, nn);
26467c478bd9Sstevel@tonic-gate (void) big_copy(m, mm);
26477c478bd9Sstevel@tonic-gate
26487c478bd9Sstevel@tonic-gate *jac = 1;
2649b60f2a0bSfr41279 while (big_cmp_abs(&big_One, m) != 0) {
26507c478bd9Sstevel@tonic-gate if (big_is_zero(n)) {
26517c478bd9Sstevel@tonic-gate *jac = 0;
26527c478bd9Sstevel@tonic-gate goto ret;
26537c478bd9Sstevel@tonic-gate }
26547c478bd9Sstevel@tonic-gate if ((m->value[0] & 1) == 0) {
26557c478bd9Sstevel@tonic-gate if (((n->value[0] & 7) == 3) ||
2656b60f2a0bSfr41279 ((n->value[0] & 7) == 5))
2657b60f2a0bSfr41279 *jac = -*jac;
26587c478bd9Sstevel@tonic-gate (void) big_half_pos(m, m);
26597c478bd9Sstevel@tonic-gate } else if ((n->value[0] & 1) == 0) {
26607c478bd9Sstevel@tonic-gate if (((m->value[0] & 7) == 3) ||
2661b60f2a0bSfr41279 ((m->value[0] & 7) == 5))
2662b60f2a0bSfr41279 *jac = -*jac;
26637c478bd9Sstevel@tonic-gate (void) big_half_pos(n, n);
26647c478bd9Sstevel@tonic-gate } else {
26657c478bd9Sstevel@tonic-gate if (((m->value[0] & 3) == 3) &&
26667c478bd9Sstevel@tonic-gate ((n->value[0] & 3) == 3)) {
26677c478bd9Sstevel@tonic-gate *jac = -*jac;
26687c478bd9Sstevel@tonic-gate }
2669b60f2a0bSfr41279 if ((err = big_div_pos(NULL, tmp2, m, n)) != BIG_OK) {
26707c478bd9Sstevel@tonic-gate goto ret;
2671b60f2a0bSfr41279 }
26727c478bd9Sstevel@tonic-gate t = tmp2;
26737c478bd9Sstevel@tonic-gate tmp2 = m;
26747c478bd9Sstevel@tonic-gate m = n;
26757c478bd9Sstevel@tonic-gate n = t;
26767c478bd9Sstevel@tonic-gate }
26777c478bd9Sstevel@tonic-gate }
26787c478bd9Sstevel@tonic-gate err = BIG_OK;
26797c478bd9Sstevel@tonic-gate
26807c478bd9Sstevel@tonic-gate ret:
26817c478bd9Sstevel@tonic-gate if (t3.malloced) big_finish(&t3);
26827c478bd9Sstevel@tonic-gate ret2:
26837c478bd9Sstevel@tonic-gate if (t2.malloced) big_finish(&t2);
26847c478bd9Sstevel@tonic-gate ret1:
26857c478bd9Sstevel@tonic-gate if (t1.malloced) big_finish(&t1);
26867c478bd9Sstevel@tonic-gate
26877c478bd9Sstevel@tonic-gate return (err);
26887c478bd9Sstevel@tonic-gate }
26897c478bd9Sstevel@tonic-gate
26907c478bd9Sstevel@tonic-gate
26917c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_Lucas(BIGNUM * Lkminus1,BIGNUM * Lk,BIGNUM * p,BIGNUM * k,BIGNUM * n)26927c478bd9Sstevel@tonic-gate big_Lucas(BIGNUM *Lkminus1, BIGNUM *Lk, BIGNUM *p, BIGNUM *k, BIGNUM *n)
26937c478bd9Sstevel@tonic-gate {
26948475e043SDan OpenSolaris Anderson int i;
26958475e043SDan OpenSolaris Anderson uint32_t m, w;
2696b60f2a0bSfr41279 BIG_CHUNK_TYPE bit;
26977c478bd9Sstevel@tonic-gate BIGNUM ki, tmp, tmp2;
2698b60f2a0bSfr41279 BIG_CHUNK_TYPE kivalue[BIGTMPSIZE];
2699b60f2a0bSfr41279 BIG_CHUNK_TYPE tmpvalue[BIGTMPSIZE];
2700b60f2a0bSfr41279 BIG_CHUNK_TYPE tmp2value[BIGTMPSIZE];
27017c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
27027c478bd9Sstevel@tonic-gate
2703b60f2a0bSfr41279 if (big_cmp_abs(k, &big_One) == 0) {
27047c478bd9Sstevel@tonic-gate (void) big_copy(Lk, p);
2705b60f2a0bSfr41279 (void) big_copy(Lkminus1, &big_Two);
27067c478bd9Sstevel@tonic-gate return (BIG_OK);
27077c478bd9Sstevel@tonic-gate }
27087c478bd9Sstevel@tonic-gate
27097c478bd9Sstevel@tonic-gate if ((err = big_init1(&ki, k->len + 1,
27107c478bd9Sstevel@tonic-gate kivalue, arraysize(kivalue))) != BIG_OK)
27117c478bd9Sstevel@tonic-gate return (err);
27127c478bd9Sstevel@tonic-gate
27137c478bd9Sstevel@tonic-gate if ((err = big_init1(&tmp, 2 * n->len + 1,
27147c478bd9Sstevel@tonic-gate tmpvalue, arraysize(tmpvalue))) != BIG_OK)
27157c478bd9Sstevel@tonic-gate goto ret1;
27167c478bd9Sstevel@tonic-gate
27177c478bd9Sstevel@tonic-gate if ((err = big_init1(&tmp2, n->len,
27187c478bd9Sstevel@tonic-gate tmp2value, arraysize(tmp2value))) != BIG_OK)
27197c478bd9Sstevel@tonic-gate goto ret2;
27207c478bd9Sstevel@tonic-gate
27217c478bd9Sstevel@tonic-gate m = big_numbits(k);
2722b60f2a0bSfr41279 ki.len = (m - 1) / BIG_CHUNK_SIZE + 1;
2723b60f2a0bSfr41279 w = (m - 1) / BIG_CHUNK_SIZE;
2724b60f2a0bSfr41279 bit = (BIG_CHUNK_TYPE)1 << ((m - 1) % BIG_CHUNK_SIZE);
2725b60f2a0bSfr41279 for (i = 0; i < ki.len; i++) {
2726b60f2a0bSfr41279 ki.value[i] = 0;
2727b60f2a0bSfr41279 }
27287c478bd9Sstevel@tonic-gate ki.value[ki.len - 1] = bit;
2729b60f2a0bSfr41279 if (big_cmp_abs(k, &ki) != 0) {
27307c478bd9Sstevel@tonic-gate (void) big_double(&ki, &ki);
2731b60f2a0bSfr41279 }
27327c478bd9Sstevel@tonic-gate (void) big_sub_pos(&ki, &ki, k);
27337c478bd9Sstevel@tonic-gate
27347c478bd9Sstevel@tonic-gate (void) big_copy(Lk, p);
2735b60f2a0bSfr41279 (void) big_copy(Lkminus1, &big_Two);
27367c478bd9Sstevel@tonic-gate
27377c478bd9Sstevel@tonic-gate for (i = 0; i < m; i++) {
2738b60f2a0bSfr41279 if ((err = big_mul(&tmp, Lk, Lkminus1)) != BIG_OK) {
27397c478bd9Sstevel@tonic-gate goto ret;
2740b60f2a0bSfr41279 }
27417c478bd9Sstevel@tonic-gate (void) big_add_abs(&tmp, &tmp, n);
27427c478bd9Sstevel@tonic-gate (void) big_sub_pos(&tmp, &tmp, p);
2743b60f2a0bSfr41279 if ((err = big_div_pos(NULL, &tmp2, &tmp, n)) != BIG_OK) {
27447c478bd9Sstevel@tonic-gate goto ret;
2745b60f2a0bSfr41279 }
27467c478bd9Sstevel@tonic-gate if ((ki.value[w] & bit) != 0) {
27477c478bd9Sstevel@tonic-gate if ((err = big_mul(&tmp, Lkminus1, Lkminus1)) !=
2748b60f2a0bSfr41279 BIG_OK) {
27497c478bd9Sstevel@tonic-gate goto ret;
2750b60f2a0bSfr41279 }
27517c478bd9Sstevel@tonic-gate (void) big_add_abs(&tmp, &tmp, n);
2752b60f2a0bSfr41279 (void) big_sub_pos(&tmp, &tmp, &big_Two);
27537c478bd9Sstevel@tonic-gate if ((err = big_div_pos(NULL, Lkminus1, &tmp, n)) !=
2754b60f2a0bSfr41279 BIG_OK) {
27557c478bd9Sstevel@tonic-gate goto ret;
2756b60f2a0bSfr41279 }
27577c478bd9Sstevel@tonic-gate (void) big_copy(Lk, &tmp2);
27587c478bd9Sstevel@tonic-gate } else {
2759b60f2a0bSfr41279 if ((err = big_mul(&tmp, Lk, Lk)) != BIG_OK) {
27607c478bd9Sstevel@tonic-gate goto ret;
2761b60f2a0bSfr41279 }
27627c478bd9Sstevel@tonic-gate (void) big_add_abs(&tmp, &tmp, n);
2763b60f2a0bSfr41279 (void) big_sub_pos(&tmp, &tmp, &big_Two);
2764b60f2a0bSfr41279 if ((err = big_div_pos(NULL, Lk, &tmp, n)) != BIG_OK) {
27657c478bd9Sstevel@tonic-gate goto ret;
2766b60f2a0bSfr41279 }
27677c478bd9Sstevel@tonic-gate (void) big_copy(Lkminus1, &tmp2);
27687c478bd9Sstevel@tonic-gate }
27697c478bd9Sstevel@tonic-gate bit = bit >> 1;
27707c478bd9Sstevel@tonic-gate if (bit == 0) {
2771b60f2a0bSfr41279 bit = BIG_CHUNK_HIGHBIT;
27727c478bd9Sstevel@tonic-gate w--;
27737c478bd9Sstevel@tonic-gate }
27747c478bd9Sstevel@tonic-gate }
27757c478bd9Sstevel@tonic-gate
27767c478bd9Sstevel@tonic-gate err = BIG_OK;
27777c478bd9Sstevel@tonic-gate
27787c478bd9Sstevel@tonic-gate ret:
27797c478bd9Sstevel@tonic-gate if (tmp2.malloced) big_finish(&tmp2);
27807c478bd9Sstevel@tonic-gate ret2:
27817c478bd9Sstevel@tonic-gate if (tmp.malloced) big_finish(&tmp);
27827c478bd9Sstevel@tonic-gate ret1:
27837c478bd9Sstevel@tonic-gate if (ki.malloced) big_finish(&ki);
27847c478bd9Sstevel@tonic-gate
27857c478bd9Sstevel@tonic-gate return (err);
27867c478bd9Sstevel@tonic-gate }
27877c478bd9Sstevel@tonic-gate
27887c478bd9Sstevel@tonic-gate
27897c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_isprime_pos_ext(BIGNUM * n,big_modexp_ncp_info_t * info)2790b60f2a0bSfr41279 big_isprime_pos_ext(BIGNUM *n, big_modexp_ncp_info_t *info)
27917c478bd9Sstevel@tonic-gate {
27927c478bd9Sstevel@tonic-gate BIGNUM o, nminus1, tmp, Lkminus1, Lk;
2793b60f2a0bSfr41279 BIG_CHUNK_TYPE ovalue[BIGTMPSIZE];
2794b60f2a0bSfr41279 BIG_CHUNK_TYPE nminus1value[BIGTMPSIZE];
2795b60f2a0bSfr41279 BIG_CHUNK_TYPE tmpvalue[BIGTMPSIZE];
2796b60f2a0bSfr41279 BIG_CHUNK_TYPE Lkminus1value[BIGTMPSIZE];
2797b60f2a0bSfr41279 BIG_CHUNK_TYPE Lkvalue[BIGTMPSIZE];
27987c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
27997c478bd9Sstevel@tonic-gate int e, i, jac;
28007c478bd9Sstevel@tonic-gate
2801b60f2a0bSfr41279 if (big_cmp_abs(n, &big_One) == 0) {
28027c478bd9Sstevel@tonic-gate return (BIG_FALSE);
2803b60f2a0bSfr41279 }
2804b60f2a0bSfr41279 if (big_cmp_abs(n, &big_Two) == 0) {
28057c478bd9Sstevel@tonic-gate return (BIG_TRUE);
2806b60f2a0bSfr41279 }
2807b60f2a0bSfr41279 if ((n->value[0] & 1) == 0) {
28087c478bd9Sstevel@tonic-gate return (BIG_FALSE);
2809b60f2a0bSfr41279 }
28107c478bd9Sstevel@tonic-gate
2811b60f2a0bSfr41279 if ((err = big_init1(&o, n->len, ovalue, arraysize(ovalue))) !=
2812b60f2a0bSfr41279 BIG_OK) {
28137c478bd9Sstevel@tonic-gate return (err);
2814b60f2a0bSfr41279 }
28157c478bd9Sstevel@tonic-gate
28167c478bd9Sstevel@tonic-gate if ((err = big_init1(&nminus1, n->len,
2817b60f2a0bSfr41279 nminus1value, arraysize(nminus1value))) != BIG_OK) {
28187c478bd9Sstevel@tonic-gate goto ret1;
2819b60f2a0bSfr41279 }
28207c478bd9Sstevel@tonic-gate
28217c478bd9Sstevel@tonic-gate if ((err = big_init1(&tmp, 2 * n->len,
2822b60f2a0bSfr41279 tmpvalue, arraysize(tmpvalue))) != BIG_OK) {
28237c478bd9Sstevel@tonic-gate goto ret2;
2824b60f2a0bSfr41279 }
28257c478bd9Sstevel@tonic-gate
28267c478bd9Sstevel@tonic-gate if ((err = big_init1(&Lkminus1, n->len,
2827b60f2a0bSfr41279 Lkminus1value, arraysize(Lkminus1value))) != BIG_OK) {
28287c478bd9Sstevel@tonic-gate goto ret3;
2829b60f2a0bSfr41279 }
28307c478bd9Sstevel@tonic-gate
28317c478bd9Sstevel@tonic-gate if ((err = big_init1(&Lk, n->len,
2832b60f2a0bSfr41279 Lkvalue, arraysize(Lkvalue))) != BIG_OK) {
28337c478bd9Sstevel@tonic-gate goto ret4;
2834b60f2a0bSfr41279 }
28357c478bd9Sstevel@tonic-gate
2836b60f2a0bSfr41279 (void) big_sub_pos(&o, n, &big_One); /* cannot fail */
28377c478bd9Sstevel@tonic-gate (void) big_copy(&nminus1, &o); /* cannot fail */
28387c478bd9Sstevel@tonic-gate e = 0;
28397c478bd9Sstevel@tonic-gate while ((o.value[0] & 1) == 0) {
28407c478bd9Sstevel@tonic-gate e++;
28417c478bd9Sstevel@tonic-gate (void) big_half_pos(&o, &o); /* cannot fail */
28427c478bd9Sstevel@tonic-gate }
2843b60f2a0bSfr41279 if ((err = big_modexp_ext(&tmp, &big_Two, &o, n, NULL, info)) !=
2844b60f2a0bSfr41279 BIG_OK) {
28457c478bd9Sstevel@tonic-gate goto ret;
2846b60f2a0bSfr41279 }
2847b60f2a0bSfr41279
28487c478bd9Sstevel@tonic-gate i = 0;
28497c478bd9Sstevel@tonic-gate while ((i < e) &&
2850b60f2a0bSfr41279 (big_cmp_abs(&tmp, &big_One) != 0) &&
28517c478bd9Sstevel@tonic-gate (big_cmp_abs(&tmp, &nminus1) != 0)) {
2852b60f2a0bSfr41279 if ((err =
2853b60f2a0bSfr41279 big_modexp_ext(&tmp, &tmp, &big_Two, n, NULL, info)) !=
2854b60f2a0bSfr41279 BIG_OK)
28557c478bd9Sstevel@tonic-gate goto ret;
28567c478bd9Sstevel@tonic-gate i++;
28577c478bd9Sstevel@tonic-gate }
2858b60f2a0bSfr41279
28597c478bd9Sstevel@tonic-gate if (!((big_cmp_abs(&tmp, &nminus1) == 0) ||
2860b60f2a0bSfr41279 ((i == 0) && (big_cmp_abs(&tmp, &big_One) == 0)))) {
28617c478bd9Sstevel@tonic-gate err = BIG_FALSE;
28627c478bd9Sstevel@tonic-gate goto ret;
28637c478bd9Sstevel@tonic-gate }
28647c478bd9Sstevel@tonic-gate
2865b60f2a0bSfr41279 if ((err = big_sqrt_pos(&tmp, n)) != BIG_OK) {
28667c478bd9Sstevel@tonic-gate goto ret;
2867b60f2a0bSfr41279 }
2868b60f2a0bSfr41279
2869b60f2a0bSfr41279 if ((err = big_mul(&tmp, &tmp, &tmp)) != BIG_OK) {
28707c478bd9Sstevel@tonic-gate goto ret;
2871b60f2a0bSfr41279 }
28727c478bd9Sstevel@tonic-gate if (big_cmp_abs(&tmp, n) == 0) {
28737c478bd9Sstevel@tonic-gate err = BIG_FALSE;
28747c478bd9Sstevel@tonic-gate goto ret;
28757c478bd9Sstevel@tonic-gate }
28767c478bd9Sstevel@tonic-gate
2877b60f2a0bSfr41279 (void) big_copy(&o, &big_Two);
28787c478bd9Sstevel@tonic-gate do {
2879b60f2a0bSfr41279 (void) big_add_abs(&o, &o, &big_One);
2880b60f2a0bSfr41279 if ((err = big_mul(&tmp, &o, &o)) != BIG_OK) {
28817c478bd9Sstevel@tonic-gate goto ret;
2882b60f2a0bSfr41279 }
2883b60f2a0bSfr41279 (void) big_sub_pos(&tmp, &tmp, &big_Four);
2884b60f2a0bSfr41279 if ((err = big_Jacobi_pos(&jac, &tmp, n)) != BIG_OK) {
28857c478bd9Sstevel@tonic-gate goto ret;
2886b60f2a0bSfr41279 }
28877c478bd9Sstevel@tonic-gate } while (jac != -1);
28887c478bd9Sstevel@tonic-gate
2889b60f2a0bSfr41279 (void) big_add_abs(&tmp, n, &big_One);
2890b60f2a0bSfr41279 if ((err = big_Lucas(&Lkminus1, &Lk, &o, &tmp, n)) != BIG_OK) {
28917c478bd9Sstevel@tonic-gate goto ret;
2892b60f2a0bSfr41279 }
2893b60f2a0bSfr41279
2894b60f2a0bSfr41279 if ((big_cmp_abs(&Lkminus1, &o) == 0) &&
2895b60f2a0bSfr41279 (big_cmp_abs(&Lk, &big_Two) == 0)) {
28967c478bd9Sstevel@tonic-gate err = BIG_TRUE;
2897b60f2a0bSfr41279 } else {
2898b60f2a0bSfr41279 err = BIG_FALSE;
2899b60f2a0bSfr41279 }
29007c478bd9Sstevel@tonic-gate
29017c478bd9Sstevel@tonic-gate ret:
29027c478bd9Sstevel@tonic-gate if (Lk.malloced) big_finish(&Lk);
29037c478bd9Sstevel@tonic-gate ret4:
29047c478bd9Sstevel@tonic-gate if (Lkminus1.malloced) big_finish(&Lkminus1);
29057c478bd9Sstevel@tonic-gate ret3:
29067c478bd9Sstevel@tonic-gate if (tmp.malloced) big_finish(&tmp);
29077c478bd9Sstevel@tonic-gate ret2:
29087c478bd9Sstevel@tonic-gate if (nminus1.malloced) big_finish(&nminus1);
29097c478bd9Sstevel@tonic-gate ret1:
29107c478bd9Sstevel@tonic-gate if (o.malloced) big_finish(&o);
29117c478bd9Sstevel@tonic-gate
29127c478bd9Sstevel@tonic-gate return (err);
29137c478bd9Sstevel@tonic-gate }
29147c478bd9Sstevel@tonic-gate
29157c478bd9Sstevel@tonic-gate
2916b60f2a0bSfr41279 BIG_ERR_CODE
big_isprime_pos(BIGNUM * n)2917b60f2a0bSfr41279 big_isprime_pos(BIGNUM *n)
2918b60f2a0bSfr41279 {
2919b60f2a0bSfr41279 return (big_isprime_pos_ext(n, NULL));
2920b60f2a0bSfr41279 }
2921b60f2a0bSfr41279
2922b60f2a0bSfr41279
29237c478bd9Sstevel@tonic-gate #define SIEVESIZE 1000
29247c478bd9Sstevel@tonic-gate
29257c478bd9Sstevel@tonic-gate
29267c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_nextprime_pos_ext(BIGNUM * result,BIGNUM * n,big_modexp_ncp_info_t * info)2927b60f2a0bSfr41279 big_nextprime_pos_ext(BIGNUM *result, BIGNUM *n, big_modexp_ncp_info_t *info)
29287c478bd9Sstevel@tonic-gate {
29298475e043SDan OpenSolaris Anderson static const uint32_t smallprimes[] = {
29308475e043SDan OpenSolaris Anderson 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
29318475e043SDan OpenSolaris Anderson 51, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97 };
29327c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
29337c478bd9Sstevel@tonic-gate int sieve[SIEVESIZE];
29347c478bd9Sstevel@tonic-gate int i;
29357c478bd9Sstevel@tonic-gate uint32_t off, p;
29367c478bd9Sstevel@tonic-gate
2937b60f2a0bSfr41279 if ((err = big_copy(result, n)) != BIG_OK) {
29387c478bd9Sstevel@tonic-gate return (err);
2939b60f2a0bSfr41279 }
29407c478bd9Sstevel@tonic-gate result->value[0] |= 1;
2941f56c1286Srobinson /* CONSTCOND */
29427c478bd9Sstevel@tonic-gate while (1) {
29437c478bd9Sstevel@tonic-gate for (i = 0; i < SIEVESIZE; i++) sieve[i] = 0;
29447c478bd9Sstevel@tonic-gate for (i = 0;
2945b60f2a0bSfr41279 i < sizeof (smallprimes) / sizeof (smallprimes[0]); i++) {
29467c478bd9Sstevel@tonic-gate p = smallprimes[i];
2947b60f2a0bSfr41279 off = big_modhalf_pos(result, p);
29487c478bd9Sstevel@tonic-gate off = p - off;
2949b60f2a0bSfr41279 if ((off % 2) == 1) {
2950b60f2a0bSfr41279 off = off + p;
2951b60f2a0bSfr41279 }
29527c478bd9Sstevel@tonic-gate off = off / 2;
29537c478bd9Sstevel@tonic-gate while (off < SIEVESIZE) {
29547c478bd9Sstevel@tonic-gate sieve[off] = 1;
29557c478bd9Sstevel@tonic-gate off = off + p;
29567c478bd9Sstevel@tonic-gate }
29577c478bd9Sstevel@tonic-gate }
29587c478bd9Sstevel@tonic-gate
29597c478bd9Sstevel@tonic-gate for (i = 0; i < SIEVESIZE; i++) {
29607c478bd9Sstevel@tonic-gate if (sieve[i] == 0) {
2961b60f2a0bSfr41279 err = big_isprime_pos_ext(result, info);
29627c478bd9Sstevel@tonic-gate if (err != BIG_FALSE) {
2963b60f2a0bSfr41279 if (err != BIG_TRUE) {
29647c478bd9Sstevel@tonic-gate return (err);
2965b60f2a0bSfr41279 } else {
2966b60f2a0bSfr41279 goto out;
2967b60f2a0bSfr41279 }
29687c478bd9Sstevel@tonic-gate }
29697c478bd9Sstevel@tonic-gate
29707c478bd9Sstevel@tonic-gate }
2971b60f2a0bSfr41279 if ((err = big_add_abs(result, result, &big_Two)) !=
2972b60f2a0bSfr41279 BIG_OK) {
29737c478bd9Sstevel@tonic-gate return (err);
29747c478bd9Sstevel@tonic-gate }
29757c478bd9Sstevel@tonic-gate }
2976b60f2a0bSfr41279 }
2977b60f2a0bSfr41279
2978b60f2a0bSfr41279 out:
2979b60f2a0bSfr41279 return (BIG_OK);
2980b60f2a0bSfr41279 }
2981b60f2a0bSfr41279
2982b60f2a0bSfr41279
2983b60f2a0bSfr41279 BIG_ERR_CODE
big_nextprime_pos(BIGNUM * result,BIGNUM * n)2984b60f2a0bSfr41279 big_nextprime_pos(BIGNUM *result, BIGNUM *n)
2985b60f2a0bSfr41279 {
2986b60f2a0bSfr41279 return (big_nextprime_pos_ext(result, n, NULL));
29877c478bd9Sstevel@tonic-gate }
29887c478bd9Sstevel@tonic-gate
29897c478bd9Sstevel@tonic-gate
29907c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_nextprime_pos_slow(BIGNUM * result,BIGNUM * n)29917c478bd9Sstevel@tonic-gate big_nextprime_pos_slow(BIGNUM *result, BIGNUM *n)
29927c478bd9Sstevel@tonic-gate {
29937c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
29947c478bd9Sstevel@tonic-gate
29957c478bd9Sstevel@tonic-gate
29967c478bd9Sstevel@tonic-gate if ((err = big_copy(result, n)) != BIG_OK)
29977c478bd9Sstevel@tonic-gate return (err);
29987c478bd9Sstevel@tonic-gate result->value[0] |= 1;
2999b60f2a0bSfr41279 while ((err = big_isprime_pos_ext(result, NULL)) != BIG_TRUE) {
30007c478bd9Sstevel@tonic-gate if (err != BIG_FALSE)
30017c478bd9Sstevel@tonic-gate return (err);
3002b60f2a0bSfr41279 if ((err = big_add_abs(result, result, &big_Two)) != BIG_OK)
30037c478bd9Sstevel@tonic-gate return (err);
30047c478bd9Sstevel@tonic-gate }
30057c478bd9Sstevel@tonic-gate return (BIG_OK);
30067c478bd9Sstevel@tonic-gate }
30077c478bd9Sstevel@tonic-gate
30087c478bd9Sstevel@tonic-gate
30097c478bd9Sstevel@tonic-gate /*
30107c478bd9Sstevel@tonic-gate * given m and e, computes the rest in the equation
30117c478bd9Sstevel@tonic-gate * gcd(m, e) = cm * m + ce * e
30127c478bd9Sstevel@tonic-gate */
30137c478bd9Sstevel@tonic-gate BIG_ERR_CODE
big_ext_gcd_pos(BIGNUM * gcd,BIGNUM * cm,BIGNUM * ce,BIGNUM * m,BIGNUM * e)30147c478bd9Sstevel@tonic-gate big_ext_gcd_pos(BIGNUM *gcd, BIGNUM *cm, BIGNUM *ce, BIGNUM *m, BIGNUM *e)
30157c478bd9Sstevel@tonic-gate {
3016b60f2a0bSfr41279 BIGNUM *xi, *ri, *riminus1, *riminus2, *t;
3017b60f2a0bSfr41279 BIGNUM *vmi, *vei, *vmiminus1, *veiminus1;
30187c478bd9Sstevel@tonic-gate BIGNUM t1, t2, t3, t4, t5, t6, t7, t8, tmp;
3019b60f2a0bSfr41279 BIG_CHUNK_TYPE t1value[BIGTMPSIZE];
3020b60f2a0bSfr41279 BIG_CHUNK_TYPE t2value[BIGTMPSIZE];
3021b60f2a0bSfr41279 BIG_CHUNK_TYPE t3value[BIGTMPSIZE];
3022b60f2a0bSfr41279 BIG_CHUNK_TYPE t4value[BIGTMPSIZE];
3023b60f2a0bSfr41279 BIG_CHUNK_TYPE t5value[BIGTMPSIZE];
3024b60f2a0bSfr41279 BIG_CHUNK_TYPE t6value[BIGTMPSIZE];
3025b60f2a0bSfr41279 BIG_CHUNK_TYPE t7value[BIGTMPSIZE];
3026b60f2a0bSfr41279 BIG_CHUNK_TYPE t8value[BIGTMPSIZE];
3027b60f2a0bSfr41279 BIG_CHUNK_TYPE tmpvalue[BIGTMPSIZE];
30287c478bd9Sstevel@tonic-gate BIG_ERR_CODE err;
30297c478bd9Sstevel@tonic-gate int len;
30307c478bd9Sstevel@tonic-gate
3031b60f2a0bSfr41279 if (big_cmp_abs(m, e) >= 0) {
3032b60f2a0bSfr41279 len = m->len;
3033b60f2a0bSfr41279 } else {
3034b60f2a0bSfr41279 len = e->len;
3035b60f2a0bSfr41279 }
30367c478bd9Sstevel@tonic-gate
30377c478bd9Sstevel@tonic-gate if ((err = big_init1(&t1, len,
3038b60f2a0bSfr41279 t1value, arraysize(t1value))) != BIG_OK) {
30397c478bd9Sstevel@tonic-gate return (err);
3040b60f2a0bSfr41279 }
30417c478bd9Sstevel@tonic-gate if ((err = big_init1(&t2, len,
3042b60f2a0bSfr41279 t2value, arraysize(t2value))) != BIG_OK) {
30437c478bd9Sstevel@tonic-gate goto ret1;
3044b60f2a0bSfr41279 }
30457c478bd9Sstevel@tonic-gate if ((err = big_init1(&t3, len,
3046b60f2a0bSfr41279 t3value, arraysize(t3value))) != BIG_OK) {
30477c478bd9Sstevel@tonic-gate goto ret2;
3048b60f2a0bSfr41279 }
30497c478bd9Sstevel@tonic-gate if ((err = big_init1(&t4, len,
3050b60f2a0bSfr41279 t4value, arraysize(t3value))) != BIG_OK) {
30517c478bd9Sstevel@tonic-gate goto ret3;
3052b60f2a0bSfr41279 }
30537c478bd9Sstevel@tonic-gate if ((err = big_init1(&t5, len,
3054b60f2a0bSfr41279 t5value, arraysize(t5value))) != BIG_OK) {
30557c478bd9Sstevel@tonic-gate goto ret4;
3056b60f2a0bSfr41279 }
30577c478bd9Sstevel@tonic-gate if ((err = big_init1(&t6, len,
3058b60f2a0bSfr41279 t6value, arraysize(t6value))) != BIG_OK) {
30597c478bd9Sstevel@tonic-gate goto ret5;
3060b60f2a0bSfr41279 }
30617c478bd9Sstevel@tonic-gate if ((err = big_init1(&t7, len,
3062b60f2a0bSfr41279 t7value, arraysize(t7value))) != BIG_OK) {
30637c478bd9Sstevel@tonic-gate goto ret6;
3064b60f2a0bSfr41279 }
30657c478bd9Sstevel@tonic-gate if ((err = big_init1(&t8, len,
3066b60f2a0bSfr41279 t8value, arraysize(t8value))) != BIG_OK) {
30677c478bd9Sstevel@tonic-gate goto ret7;
3068b60f2a0bSfr41279 }
30697c478bd9Sstevel@tonic-gate
30707c478bd9Sstevel@tonic-gate if ((err = big_init1(&tmp, 2 * len,
3071b60f2a0bSfr41279 tmpvalue, arraysize(tmpvalue))) != BIG_OK) {
30727c478bd9Sstevel@tonic-gate goto ret8;
3073b60f2a0bSfr41279 }
30747c478bd9Sstevel@tonic-gate
30757c478bd9Sstevel@tonic-gate ri = &t1;
30767c478bd9Sstevel@tonic-gate ri->value[0] = 1;
30777c478bd9Sstevel@tonic-gate ri->len = 1;
30787c478bd9Sstevel@tonic-gate xi = &t2;
30797c478bd9Sstevel@tonic-gate riminus1 = &t3;
30807c478bd9Sstevel@tonic-gate riminus2 = &t4;
30817c478bd9Sstevel@tonic-gate vmi = &t5;
30827c478bd9Sstevel@tonic-gate vei = &t6;
30837c478bd9Sstevel@tonic-gate vmiminus1 = &t7;
30847c478bd9Sstevel@tonic-gate veiminus1 = &t8;
30857c478bd9Sstevel@tonic-gate
3086b60f2a0bSfr41279 (void) big_copy(vmiminus1, &big_One);
3087b60f2a0bSfr41279 (void) big_copy(vmi, &big_One);
3088b60f2a0bSfr41279 (void) big_copy(veiminus1, &big_One);
3089b60f2a0bSfr41279 (void) big_copy(xi, &big_One);
30907c478bd9Sstevel@tonic-gate vei->len = 1;
30917c478bd9Sstevel@tonic-gate vei->value[0] = 0;
30927c478bd9Sstevel@tonic-gate
30937c478bd9Sstevel@tonic-gate (void) big_copy(riminus1, m);
30947c478bd9Sstevel@tonic-gate (void) big_copy(ri, e);
30957c478bd9Sstevel@tonic-gate
30967c478bd9Sstevel@tonic-gate while (!big_is_zero(ri)) {
30977c478bd9Sstevel@tonic-gate t = riminus2;
30987c478bd9Sstevel@tonic-gate riminus2 = riminus1;
30997c478bd9Sstevel@tonic-gate riminus1 = ri;
31007c478bd9Sstevel@tonic-gate ri = t;
3101b60f2a0bSfr41279 if ((err = big_mul(&tmp, vmi, xi)) != BIG_OK) {
31027c478bd9Sstevel@tonic-gate goto ret;
3103b60f2a0bSfr41279 }
3104b60f2a0bSfr41279 if ((err = big_sub(vmiminus1, vmiminus1, &tmp)) != BIG_OK) {
31057c478bd9Sstevel@tonic-gate goto ret;
3106b60f2a0bSfr41279 }
31077c478bd9Sstevel@tonic-gate t = vmiminus1;
31087c478bd9Sstevel@tonic-gate vmiminus1 = vmi;
31097c478bd9Sstevel@tonic-gate vmi = t;
3110b60f2a0bSfr41279 if ((err = big_mul(&tmp, vei, xi)) != BIG_OK) {
31117c478bd9Sstevel@tonic-gate goto ret;
3112b60f2a0bSfr41279 }
3113b60f2a0bSfr41279 if ((err = big_sub(veiminus1, veiminus1, &tmp)) != BIG_OK) {
31147c478bd9Sstevel@tonic-gate goto ret;
3115b60f2a0bSfr41279 }
31167c478bd9Sstevel@tonic-gate t = veiminus1;
31177c478bd9Sstevel@tonic-gate veiminus1 = vei;
31187c478bd9Sstevel@tonic-gate vei = t;
3119b60f2a0bSfr41279 if ((err = big_div_pos(xi, ri, riminus2, riminus1)) !=
3120b60f2a0bSfr41279 BIG_OK) {
31217c478bd9Sstevel@tonic-gate goto ret;
31227c478bd9Sstevel@tonic-gate }
3123b60f2a0bSfr41279 }
3124b60f2a0bSfr41279 if ((gcd != NULL) && ((err = big_copy(gcd, riminus1)) != BIG_OK)) {
31257c478bd9Sstevel@tonic-gate goto ret;
3126b60f2a0bSfr41279 }
3127b60f2a0bSfr41279 if ((cm != NULL) && ((err = big_copy(cm, vmi)) != BIG_OK)) {
31287c478bd9Sstevel@tonic-gate goto ret;
3129b60f2a0bSfr41279 }
3130b60f2a0bSfr41279 if (ce != NULL) {
31317c478bd9Sstevel@tonic-gate err = big_copy(ce, vei);
3132b60f2a0bSfr41279 }
31337c478bd9Sstevel@tonic-gate ret:
31347c478bd9Sstevel@tonic-gate if (tmp.malloced) big_finish(&tmp);
31357c478bd9Sstevel@tonic-gate ret8:
31367c478bd9Sstevel@tonic-gate if (t8.malloced) big_finish(&t8);
31377c478bd9Sstevel@tonic-gate ret7:
31387c478bd9Sstevel@tonic-gate if (t7.malloced) big_finish(&t7);
31397c478bd9Sstevel@tonic-gate ret6:
31407c478bd9Sstevel@tonic-gate if (t6.malloced) big_finish(&t6);
31417c478bd9Sstevel@tonic-gate ret5:
31427c478bd9Sstevel@tonic-gate if (t5.malloced) big_finish(&t5);
31437c478bd9Sstevel@tonic-gate ret4:
31447c478bd9Sstevel@tonic-gate if (t4.malloced) big_finish(&t4);
31457c478bd9Sstevel@tonic-gate ret3:
31467c478bd9Sstevel@tonic-gate if (t3.malloced) big_finish(&t3);
31477c478bd9Sstevel@tonic-gate ret2:
31487c478bd9Sstevel@tonic-gate if (t2.malloced) big_finish(&t2);
31497c478bd9Sstevel@tonic-gate ret1:
31507c478bd9Sstevel@tonic-gate if (t1.malloced) big_finish(&t1);
31517c478bd9Sstevel@tonic-gate
31527c478bd9Sstevel@tonic-gate return (err);
31537c478bd9Sstevel@tonic-gate }
3154726fad2aSDina K Nimeh
3155726fad2aSDina K Nimeh /*
3156726fad2aSDina K Nimeh * Get a rlen-bit random number in BIGNUM format. Caller-supplied
3157726fad2aSDina K Nimeh * (*rfunc)(void *dbuf, size_t dlen) must return 0 for success and
3158726fad2aSDina K Nimeh * -1 for failure. Note: (*rfunc)() takes length in bytes, not bits.
3159726fad2aSDina K Nimeh */
3160726fad2aSDina K Nimeh BIG_ERR_CODE
big_random(BIGNUM * r,size_t rlen,int (* rfunc)(void *,size_t))3161726fad2aSDina K Nimeh big_random(BIGNUM *r, size_t rlen, int (*rfunc)(void *, size_t))
3162726fad2aSDina K Nimeh {
3163726fad2aSDina K Nimeh size_t rwords, rbytes;
3164726fad2aSDina K Nimeh int shift;
3165726fad2aSDina K Nimeh
3166726fad2aSDina K Nimeh if (r == NULL || rlen == 0 || rfunc == NULL)
3167726fad2aSDina K Nimeh return (BIG_INVALID_ARGS);
3168726fad2aSDina K Nimeh
3169726fad2aSDina K Nimeh /*
3170726fad2aSDina K Nimeh * Convert rlen bits to r->len words (32- or 64-bit), rbytes bytes
3171726fad2aSDina K Nimeh * and extend r if it's not big enough to hold the random number.
3172726fad2aSDina K Nimeh */
3173726fad2aSDina K Nimeh rwords = BITLEN2BIGNUMLEN(rlen);
3174726fad2aSDina K Nimeh rbytes = rwords * sizeof (BIG_CHUNK_TYPE);
3175726fad2aSDina K Nimeh if (big_extend(r, rwords) != BIG_OK)
3176726fad2aSDina K Nimeh return (BIG_NO_MEM);
3177726fad2aSDina K Nimeh #ifdef BIGNUM_CHUNK_32
3178726fad2aSDina K Nimeh r->len = rwords;
3179726fad2aSDina K Nimeh #else
3180726fad2aSDina K Nimeh r->len = (uint32_t)rwords;
3181726fad2aSDina K Nimeh #endif
3182726fad2aSDina K Nimeh
3183726fad2aSDina K Nimeh if ((*rfunc)(r->value, rbytes) < 0)
3184726fad2aSDina K Nimeh return (BIG_NO_RANDOM);
3185726fad2aSDina K Nimeh
3186726fad2aSDina K Nimeh r->value[rwords - 1] |= BIG_CHUNK_HIGHBIT;
3187726fad2aSDina K Nimeh
3188726fad2aSDina K Nimeh /*
3189726fad2aSDina K Nimeh * If the bit length is not a word boundary, shift the most
3190726fad2aSDina K Nimeh * significant word so that we have an exactly rlen-long number.
3191726fad2aSDina K Nimeh */
3192726fad2aSDina K Nimeh if ((shift = rlen % BIG_CHUNK_SIZE) != 0)
3193726fad2aSDina K Nimeh r->value[rwords - 1] >>= (BIG_CHUNK_SIZE - shift);
3194726fad2aSDina K Nimeh
3195726fad2aSDina K Nimeh r->sign = 1; /* non-negative */
3196726fad2aSDina K Nimeh
3197726fad2aSDina K Nimeh return (BIG_OK);
3198726fad2aSDina K Nimeh }
3199