"debug-ben-strict", "gcc:-DBN_DEBUG -DREF_CHECK -DBN_CTX_DEBUG -DCRYPTO_MDEBUG -DCONST_STRICT -O2 -Wall -Wshadow -Werror -Wpointer-arith -Wcast-qual -Wwrite-strings -pipe::(unknown):::::",
"debug-rse","cc:-DTERMIOS -DL_ENDIAN -pipe -O -g -ggdb3 -Wall::(unknown)::BN_LLONG $x86_gcc_des $x86_gcc_opts:$x86_elf_asm",
"debug-bodo", "gcc:-DBIO_PAIR_DEBUG -DL_ENDIAN -DREF_CHECK -DBN_CTX_DEBUG -DCRYPTO_MDEBUG_ALL -g -m486 -pedantic -Wshadow -Wall::-D_REENTRANT::BN_LLONG $x86_gcc_des $x86_gcc_opts:$x86_elf_asm",
-"debug-ulf", "gcc:-DL_ENDIAN -DREF_CHECK -DBN_CTX_DEBUG -DCRYPTO_MDEBUG_ALL -g -O2 -m486 -Wall -Werror -Wshadow -pipe::-D_REENTRANT::$x86_gcc_des $x86_gcc_opts:$x86_elf_asm",
+"debug-ulf", "gcc:-DL_ENDIAN -DREF_CHECK -DBN_DEBUG -DBN_CTX_DEBUG -DCRYPTO_MDEBUG_ALL -g -O2 -m486 -Wall -Werror -Wshadow -pipe::-D_REENTRANT::$x86_gcc_des $x86_gcc_opts:$x86_elf_asm",
"debug-steve", "gcc:-DL_ENDIAN -DREF_CHECK -DBN_CTX_DEBUG -DCRYPTO_MDEBUG_ALL -DPEDANTIC -g -O2 -m486 -pedantic -Wall -Werror -Wshadow -pipe::-D_REENTRANT::$x86_gcc_des $x86_gcc_opts:$x86_elf_asm",
"debug-levitte-linux-elf","gcc:-DRL_DEBUG -DREF_CHECK -DBN_CTX_DEBUG -DCRYPTO_MDEBUG -DNO_ASM -DL_ENDIAN -DTERMIO -D_POSIX_SOURCE -ggdb -g3 -m486 -pedantic -ansi -Wall -Wshadow -Wid-clash-31 -pipe::-D_REENTRANT:::",
"dist", "cc:-O::(unknown):::::",
*** debug-ulf
$cc = gcc
-$cflags = -DL_ENDIAN -DREF_CHECK -DBN_CTX_DEBUG -DCRYPTO_MDEBUG_ALL -g -O2 -m486 -Wall -Werror -Wshadow -pipe
+$cflags = -DL_ENDIAN -DREF_CHECK -DBN_DEBUG -DBN_CTX_DEBUG -DCRYPTO_MDEBUG_ALL -g -O2 -m486 -Wall -Werror -Wshadow -pipe
$unistd =
$thread_cflag = -D_REENTRANT
$lflags =
bn_prime.h: bn_prime.pl
$(PERL) bn_prime.pl >bn_prime.h
-knuth: bn_knuth.c
- cc -pg -I.. -I../../include bn_knuth.c -o knuth $(LIB) #../../../libefence.a
-
-knuth.fast: bn_knuth.c
- cc -pg -fast -I.. -I../../include bn_knuth.c -o knuth $(LIB) #../../../libefence.a
-
-divtest: divtest.c
+divtest: divtest.c ../../libcrypto.a
cc -I../../include divtest.c -o divtest ../../libcrypto.a
+bnbug: bnbug.c ../../libcrypto.a
+ cc -g -I../../include bnbug.c -o bnbug ../../libcrypto.a
+
lib: $(LIBOBJ)
$(AR) $(LIB) $(LIBOBJ)
$(RANLIB) $(LIB)
All assember in this directory are just version of the file
-crypto/bn/bn_mulw.c.
+crypto/bn/bn_asm.c.
Quite a few of these files are just the assember output from gcc since on
quite a few machines they are 2 times faster than the system compiler.
were 64 bits). So the hand assember gives access to the 128 bit result and
a 2 times speedup :-).
-The x86xxxx.obj files are the assembled version of x86xxxx.asm files.
-I had such a hard time finding a macro assember for Microsoft, I decided to
-include the object file to save others the hassle :-).
-
-I have also included uu encoded versions of the .obj incase they get
-trashed.
-
There are 2 versions of assember for the HP PA-RISC.
pa-risc.s is the origional one which works fine.
pa-risc2.s is a new version that often generates warnings but if the
#define BN_prime_checks 0 /* default: select number of iterations
based on the size of the number */
-
/* number of Miller-Rabin iterations for an error rate of less than 2^-80
* for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook
* of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996];
/*#define BN_ascii2bn(a) BN_hex2bn(a) */
/*#define BN_bn2ascii(a) BN_bn2hex(a) */
-#define bn_expand(n,b) ((((((b+BN_BITS2-1))/BN_BITS2)) <= (n)->max)?\
- (n):bn_expand2((n),(b)/BN_BITS2+1))
-#define bn_wexpand(n,b) (((b) <= (n)->max)?(n):bn_expand2((n),(b)))
-
-#define bn_fix_top(a) \
- { \
- BN_ULONG *ftl; \
- if ((a)->top > 0) \
- { \
- for (ftl= &((a)->d[(a)->top-1]); (a)->top > 0; (a)->top--) \
- if (*(ftl--)) break; \
- } \
- }
-
BIGNUM *BN_value_one(void);
char * BN_options(void);
BN_CTX *BN_CTX_new(void);
BIGNUM *m,BN_CTX *ctx);
int BN_mask_bits(BIGNUM *a,int n);
int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);
-#ifndef WIN16
+#ifndef NO_FP_API
int BN_print_fp(FILE *fp, const BIGNUM *a);
#endif
#ifdef HEADER_BIO_H
int BN_print(BIO *fp, const BIGNUM *a);
#else
-int BN_print(char *fp, const BIGNUM *a);
+int BN_print(void *fp, const BIGNUM *a);
#endif
int BN_reciprocal(BIGNUM *r, BIGNUM *m, int len, BN_CTX *ctx);
int BN_rshift(BIGNUM *r, BIGNUM *a, int n);
int BN_rshift1(BIGNUM *r, BIGNUM *a);
void BN_clear(BIGNUM *a);
-BIGNUM *bn_expand2(BIGNUM *b, int bits);
BIGNUM *BN_dup(const BIGNUM *a);
int BN_ucmp(const BIGNUM *a, const BIGNUM *b);
int BN_set_bit(BIGNUM *a, int n);
int do_trial_division);
void ERR_load_BN_strings(void );
-BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
-BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
-void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num);
-BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
-BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num);
-BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num);
-
BN_MONT_CTX *BN_MONT_CTX_new(void );
void BN_MONT_CTX_init(BN_MONT_CTX *ctx);
int BN_mod_mul_montgomery(BIGNUM *r,BIGNUM *a,BIGNUM *b,BN_MONT_CTX *mont,
int BN_div_recp(BIGNUM *dv, BIGNUM *rem, BIGNUM *m,
BN_RECP_CTX *recp, BN_CTX *ctx);
+/* library internal functions */
+
+#define bn_expand(a,bits) ((((((bits+BN_BITS2-1))/BN_BITS2)) <= (a)->max)?\
+ (a):bn_expand2((a),(bits)/BN_BITS2+1))
+#define bn_wexpand(a,words) (((words) <= (a)->max)?(a):bn_expand2((a),(words)))
+BIGNUM *bn_expand2(BIGNUM *a, int words);
+
+#define bn_fix_top(a) \
+ { \
+ BN_ULONG *ftl; \
+ if ((a)->top > 0) \
+ { \
+ for (ftl= &((a)->d[(a)->top-1]); (a)->top > 0; (a)->top--) \
+ if (*(ftl--)) break; \
+ } \
+ }
+
+BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
+BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
+void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num);
+BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
+BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num);
+BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num);
+
+#ifdef BN_DEBUG
+ void bn_dump1(FILE *o, const char *a, BN_ULONG *b,int n);
+# define bn_print(a) {fprintf(stderr, #a "="); BN_print_fp(stderr,a); \
+ fprintf(stderr,"\n");}
+# define bn_dump(a,n) bn_dump1(stderr,#a,a,n);
+#else
+# define bn_print(a)
+# define bn_dump(a,b)
+#endif
/* BEGIN ERROR CODES */
/* The following lines are auto generated by the script mkerr.pl. Any changes
* [including the GNU Public Licence.]
*/
+#ifndef BN_DEBUG
+# undef NDEBUG /* avoid conflicting definitions */
+# define NDEBUG
+#endif
+
#include <stdio.h>
+#include <assert.h>
#include "cryptlib.h"
#include "bn_lcl.h"
{
BN_ULONG c1=0;
- bn_check_num(num);
+ assert(num >= 0);
if (num <= 0) return(c1);
while (num&~3)
{
BN_ULONG c1=0;
- bn_check_num(num);
+ assert(num >= 0);
if (num <= 0) return(c1);
while (num&~3)
void bn_sqr_words(BN_ULONG *r, BN_ULONG *a, int n)
{
- bn_check_num(n);
+ assert(n >= 0);
if (n <= 0) return;
while (n&~3)
{
}
}
-#else
+#else /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
{
BN_ULONG c=0;
BN_ULONG bl,bh;
- bn_check_num(num);
+ assert(num >= 0);
if (num <= 0) return((BN_ULONG)0);
bl=LBITS(w);
BN_ULONG carry=0;
BN_ULONG bl,bh;
- bn_check_num(num);
+ assert(num >= 0);
if (num <= 0) return((BN_ULONG)0);
bl=LBITS(w);
void bn_sqr_words(BN_ULONG *r, BN_ULONG *a, int n)
{
- bn_check_num(n);
+ assert(num >= 0);
if (n <= 0) return;
for (;;)
{
}
}
-#endif
+#endif /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
#if defined(BN_LLONG) && defined(BN_DIV2W)
ret|=q;
return(ret);
}
-#endif
+#endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
#ifdef BN_LLONG
BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
{
BN_ULLONG ll=0;
- bn_check_num(n);
+ assert(n >= 0);
if (n <= 0) return((BN_ULONG)0);
for (;;)
}
return((BN_ULONG)ll);
}
-#else
+#else /* !BN_LLONG */
BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
{
BN_ULONG c,l,t;
- bn_check_num(n);
+ assert(n >= 0);
if (n <= 0) return((BN_ULONG)0);
c=0;
}
return((BN_ULONG)c);
}
-#endif
+#endif /* !BN_LLONG */
BN_ULONG bn_sub_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
{
BN_ULONG t1,t2;
int c=0;
- bn_check_num(n);
+ assert(n >= 0);
if (n <= 0) return((BN_ULONG)0);
for (;;)
#undef bn_sqr_comba8
#undef bn_sqr_comba4
+/* mul_add_c(a,b,c0,c1,c2) -- c+=a*b for three word number c=(c2,c1,c0) */
+/* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
+/* sqr_add_c(a,i,c0,c1,c2) -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
+/* sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number c=(c2,c1,c0) */
+
#ifdef BN_LLONG
#define mul_add_c(a,b,c0,c1,c2) \
t=(BN_ULLONG)a*b; \
#define sqr_add_c2(a,i,j,c0,c1,c2) \
mul_add_c2((a)[i],(a)[j],c0,c1,c2)
-#else
+#else /* !BN_LLONG */
#define mul_add_c(a,b,c0,c1,c2) \
t1=LBITS(a); t2=HBITS(a); \
bl=LBITS(b); bh=HBITS(b); \
#define sqr_add_c2(a,i,j,c0,c1,c2) \
mul_add_c2((a)[i],(a)[j],c0,c1,c2)
-#endif
+#endif /* !BN_LLONG */
void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
{
r[6]=c1;
r[7]=c2;
}
-#else
+#else /* !BN_MUL_COMBA */
/* hmm... is it faster just to do a multiply? */
#undef bn_sqr_comba4
r[15]=bn_mul_add_words(&(r[7]),a,8,b[7]);
}
-#endif /* BN_COMBA */
+#endif /* !BN_MUL_COMBA */
+++ /dev/null
-/* crypto/bn/bn_comba.c */
-#include <stdio.h>
-#include "bn_lcl.h"
-/* Auto generated from crypto/bn/comba.pl
- */
-
-#undef bn_mul_comba8
-#undef bn_mul_comba4
-#undef bn_sqr_comba8
-#undef bn_sqr_comba4
-
-#ifdef BN_LLONG
-#define mul_add_c(a,b,c0,c1,c2) \
- t=(BN_ULLONG)a*b; \
- t1=(BN_ULONG)Lw(t); \
- t2=(BN_ULONG)Hw(t); \
- c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define mul_add_c2(a,b,c0,c1,c2) \
- t=(BN_ULLONG)a*b; \
- tt=(t+t)&BN_MASK; \
- if (tt < t) c2++; \
- t1=(BN_ULONG)Lw(tt); \
- t2=(BN_ULONG)Hw(tt); \
- c0=(c0+t1)&BN_MASK2; \
- if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define sqr_add_c(a,i,c0,c1,c2) \
- t=(BN_ULLONG)a[i]*a[i]; \
- t1=(BN_ULONG)Lw(t); \
- t2=(BN_ULONG)Hw(t); \
- c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define sqr_add_c2(a,i,j,c0,c1,c2) \
- mul_add_c2((a)[i],(a)[j],c0,c1,c2)
-#else
-#define mul_add_c(a,b,c0,c1,c2) \
- t1=LBITS(a); t2=HBITS(a); \
- bl=LBITS(b); bh=HBITS(b); \
- mul64(t1,t2,bl,bh); \
- c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define mul_add_c2(a,b,c0,c1,c2) \
- t1=LBITS(a); t2=HBITS(a); \
- bl=LBITS(b); bh=HBITS(b); \
- mul64(t1,t2,bl,bh); \
- if (t2 & BN_TBIT) c2++; \
- t2=(t2+t2)&BN_MASK2; \
- if (t1 & BN_TBIT) t2++; \
- t1=(t1+t1)&BN_MASK2; \
- c0=(c0+t1)&BN_MASK2; \
- if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define sqr_add_c(a,i,c0,c1,c2) \
- sqr64(t1,t2,(a)[i]); \
- c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define sqr_add_c2(a,i,j,c0,c1,c2) \
- mul_add_c2((a)[i],(a)[j],c0,c1,c2)
-#endif
-
-void bn_mul_comba88(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b);
-void bn_mul_comba44(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b);
-void bn_sqr_comba88(BN_ULONG *r,BN_ULONG *a);
-void bn_sqr_comba44(BN_ULONG *r,BN_ULONG *a);
-
-void bn_mul_comba88(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
- {
-#ifdef BN_LLONG
- BN_ULLONG t;
-#else
- BN_ULONG bl,bh;
-#endif
- BN_ULONG t1,t2;
- BN_ULONG c1,c2,c3;
-
- c1=0;
- c2=0;
- c3=0;
- mul_add_c(a[0],b[0],c1,c2,c3);
- r[0]=c1;
- c1=0;
- mul_add_c(a[0],b[1],c2,c3,c1);
- mul_add_c(a[1],b[0],c2,c3,c1);
- r[1]=c2;
- c2=0;
- mul_add_c(a[2],b[0],c3,c1,c2);
- mul_add_c(a[1],b[1],c3,c1,c2);
- mul_add_c(a[0],b[2],c3,c1,c2);
- r[2]=c3;
- c3=0;
- mul_add_c(a[0],b[3],c1,c2,c3);
- mul_add_c(a[1],b[2],c1,c2,c3);
- mul_add_c(a[2],b[1],c1,c2,c3);
- mul_add_c(a[3],b[0],c1,c2,c3);
- r[3]=c1;
- c1=0;
- mul_add_c(a[4],b[0],c2,c3,c1);
- mul_add_c(a[3],b[1],c2,c3,c1);
- mul_add_c(a[2],b[2],c2,c3,c1);
- mul_add_c(a[1],b[3],c2,c3,c1);
- mul_add_c(a[0],b[4],c2,c3,c1);
- r[4]=c2;
- c2=0;
- mul_add_c(a[0],b[5],c3,c1,c2);
- mul_add_c(a[1],b[4],c3,c1,c2);
- mul_add_c(a[2],b[3],c3,c1,c2);
- mul_add_c(a[3],b[2],c3,c1,c2);
- mul_add_c(a[4],b[1],c3,c1,c2);
- mul_add_c(a[5],b[0],c3,c1,c2);
- r[5]=c3;
- c3=0;
- mul_add_c(a[6],b[0],c1,c2,c3);
- mul_add_c(a[5],b[1],c1,c2,c3);
- mul_add_c(a[4],b[2],c1,c2,c3);
- mul_add_c(a[3],b[3],c1,c2,c3);
- mul_add_c(a[2],b[4],c1,c2,c3);
- mul_add_c(a[1],b[5],c1,c2,c3);
- mul_add_c(a[0],b[6],c1,c2,c3);
- r[6]=c1;
- c1=0;
- mul_add_c(a[0],b[7],c2,c3,c1);
- mul_add_c(a[1],b[6],c2,c3,c1);
- mul_add_c(a[2],b[5],c2,c3,c1);
- mul_add_c(a[3],b[4],c2,c3,c1);
- mul_add_c(a[4],b[3],c2,c3,c1);
- mul_add_c(a[5],b[2],c2,c3,c1);
- mul_add_c(a[6],b[1],c2,c3,c1);
- mul_add_c(a[7],b[0],c2,c3,c1);
- r[7]=c2;
- c2=0;
- mul_add_c(a[7],b[1],c3,c1,c2);
- mul_add_c(a[6],b[2],c3,c1,c2);
- mul_add_c(a[5],b[3],c3,c1,c2);
- mul_add_c(a[4],b[4],c3,c1,c2);
- mul_add_c(a[3],b[5],c3,c1,c2);
- mul_add_c(a[2],b[6],c3,c1,c2);
- mul_add_c(a[1],b[7],c3,c1,c2);
- r[8]=c3;
- c3=0;
- mul_add_c(a[2],b[7],c1,c2,c3);
- mul_add_c(a[3],b[6],c1,c2,c3);
- mul_add_c(a[4],b[5],c1,c2,c3);
- mul_add_c(a[5],b[4],c1,c2,c3);
- mul_add_c(a[6],b[3],c1,c2,c3);
- mul_add_c(a[7],b[2],c1,c2,c3);
- r[9]=c1;
- c1=0;
- mul_add_c(a[7],b[3],c2,c3,c1);
- mul_add_c(a[6],b[4],c2,c3,c1);
- mul_add_c(a[5],b[5],c2,c3,c1);
- mul_add_c(a[4],b[6],c2,c3,c1);
- mul_add_c(a[3],b[7],c2,c3,c1);
- r[10]=c2;
- c2=0;
- mul_add_c(a[4],b[7],c3,c1,c2);
- mul_add_c(a[5],b[6],c3,c1,c2);
- mul_add_c(a[6],b[5],c3,c1,c2);
- mul_add_c(a[7],b[4],c3,c1,c2);
- r[11]=c3;
- c3=0;
- mul_add_c(a[7],b[5],c1,c2,c3);
- mul_add_c(a[6],b[6],c1,c2,c3);
- mul_add_c(a[5],b[7],c1,c2,c3);
- r[12]=c1;
- c1=0;
- mul_add_c(a[6],b[7],c2,c3,c1);
- mul_add_c(a[7],b[6],c2,c3,c1);
- r[13]=c2;
- c2=0;
- mul_add_c(a[7],b[7],c3,c1,c2);
- r[14]=c3;
- r[15]=c1;
- }
-
-void bn_mul_comba44(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
- {
-#ifdef BN_LLONG
- BN_ULLONG t;
-#else
- BN_ULONG bl,bh;
-#endif
- BN_ULONG t1,t2;
- BN_ULONG c1,c2,c3;
-
- c1=0;
- c2=0;
- c3=0;
- mul_add_c(a[0],b[0],c1,c2,c3);
- r[0]=c1;
- c1=0;
- mul_add_c(a[0],b[1],c2,c3,c1);
- mul_add_c(a[1],b[0],c2,c3,c1);
- r[1]=c2;
- c2=0;
- mul_add_c(a[2],b[0],c3,c1,c2);
- mul_add_c(a[1],b[1],c3,c1,c2);
- mul_add_c(a[0],b[2],c3,c1,c2);
- r[2]=c3;
- c3=0;
- mul_add_c(a[0],b[3],c1,c2,c3);
- mul_add_c(a[1],b[2],c1,c2,c3);
- mul_add_c(a[2],b[1],c1,c2,c3);
- mul_add_c(a[3],b[0],c1,c2,c3);
- r[3]=c1;
- c1=0;
- mul_add_c(a[3],b[1],c2,c3,c1);
- mul_add_c(a[2],b[2],c2,c3,c1);
- mul_add_c(a[1],b[3],c2,c3,c1);
- r[4]=c2;
- c2=0;
- mul_add_c(a[2],b[3],c3,c1,c2);
- mul_add_c(a[3],b[2],c3,c1,c2);
- r[5]=c3;
- c3=0;
- mul_add_c(a[3],b[3],c1,c2,c3);
- r[6]=c1;
- r[7]=c2;
- }
-
-void bn_sqr_comba88(BN_ULONG *r, BN_ULONG *a)
- {
-#ifdef BN_LLONG
- BN_ULLONG t,tt;
-#else
- BN_ULONG bl,bh;
-#endif
- BN_ULONG t1,t2;
- BN_ULONG c1,c2,c3;
-
- c1=0;
- c2=0;
- c3=0;
- sqr_add_c(a,0,c1,c2,c3);
- r[0]=c1;
- c1=0;
- sqr_add_c2(a,1,0,c2,c3,c1);
- r[1]=c2;
- c2=0;
- sqr_add_c(a,1,c3,c1,c2);
- sqr_add_c2(a,2,0,c3,c1,c2);
- r[2]=c3;
- c3=0;
- sqr_add_c2(a,3,0,c1,c2,c3);
- sqr_add_c2(a,2,1,c1,c2,c3);
- r[3]=c1;
- c1=0;
- sqr_add_c(a,2,c2,c3,c1);
- sqr_add_c2(a,3,1,c2,c3,c1);
- sqr_add_c2(a,4,0,c2,c3,c1);
- r[4]=c2;
- c2=0;
- sqr_add_c2(a,5,0,c3,c1,c2);
- sqr_add_c2(a,4,1,c3,c1,c2);
- sqr_add_c2(a,3,2,c3,c1,c2);
- r[5]=c3;
- c3=0;
- sqr_add_c(a,3,c1,c2,c3);
- sqr_add_c2(a,4,2,c1,c2,c3);
- sqr_add_c2(a,5,1,c1,c2,c3);
- sqr_add_c2(a,6,0,c1,c2,c3);
- r[6]=c1;
- c1=0;
- sqr_add_c2(a,7,0,c2,c3,c1);
- sqr_add_c2(a,6,1,c2,c3,c1);
- sqr_add_c2(a,5,2,c2,c3,c1);
- sqr_add_c2(a,4,3,c2,c3,c1);
- r[7]=c2;
- c2=0;
- sqr_add_c(a,4,c3,c1,c2);
- sqr_add_c2(a,5,3,c3,c1,c2);
- sqr_add_c2(a,6,2,c3,c1,c2);
- sqr_add_c2(a,7,1,c3,c1,c2);
- r[8]=c3;
- c3=0;
- sqr_add_c2(a,7,2,c1,c2,c3);
- sqr_add_c2(a,6,3,c1,c2,c3);
- sqr_add_c2(a,5,4,c1,c2,c3);
- r[9]=c1;
- c1=0;
- sqr_add_c(a,5,c2,c3,c1);
- sqr_add_c2(a,6,4,c2,c3,c1);
- sqr_add_c2(a,7,3,c2,c3,c1);
- r[10]=c2;
- c2=0;
- sqr_add_c2(a,7,4,c3,c1,c2);
- sqr_add_c2(a,6,5,c3,c1,c2);
- r[11]=c3;
- c3=0;
- sqr_add_c(a,6,c1,c2,c3);
- sqr_add_c2(a,7,5,c1,c2,c3);
- r[12]=c1;
- c1=0;
- sqr_add_c2(a,7,6,c2,c3,c1);
- r[13]=c2;
- c2=0;
- sqr_add_c(a,7,c3,c1,c2);
- r[14]=c3;
- r[15]=c1;
- }
-
-void bn_sqr_comba44(BN_ULONG *r, BN_ULONG *a)
- {
-#ifdef BN_LLONG
- BN_ULLONG t,tt;
-#else
- BN_ULONG bl,bh;
-#endif
- BN_ULONG t1,t2;
- BN_ULONG c1,c2,c3;
-
- c1=0;
- c2=0;
- c3=0;
- sqr_add_c(a,0,c1,c2,c3);
- r[0]=c1;
- c1=0;
- sqr_add_c2(a,1,0,c2,c3,c1);
- r[1]=c2;
- c2=0;
- sqr_add_c(a,1,c3,c1,c2);
- sqr_add_c2(a,2,0,c3,c1,c2);
- r[2]=c3;
- c3=0;
- sqr_add_c2(a,3,0,c1,c2,c3);
- sqr_add_c2(a,2,1,c1,c2,c3);
- r[3]=c1;
- c1=0;
- sqr_add_c(a,2,c2,c3,c1);
- sqr_add_c2(a,3,1,c2,c3,c1);
- r[4]=c2;
- c2=0;
- sqr_add_c2(a,3,2,c3,c1,c2);
- r[5]=c3;
- c3=0;
- sqr_add_c(a,3,c1,c2,c3);
- r[6]=c1;
- r[7]=c2;
- }
#define BN_MUL_LOW_RECURSIVE_SIZE_NORMAL (32) /* 32 */
#define BN_MONT_CTX_SET_SIZE_WORD (64) /* 32 */
-#if 0
-#ifndef BN_MUL_COMBA
-/* #define bn_mul_comba8(r,a,b) bn_mul_normal(r,a,8,b,8) */
-/* #define bn_mul_comba4(r,a,b) bn_mul_normal(r,a,4,b,4) */
-#endif
-
-#ifndef BN_SQR_COMBA
-/* This is probably faster than using the C code - I need to check */
-#define bn_sqr_comba8(r,a) bn_mul_normal(r,a,8,a,8)
-#define bn_sqr_comba4(r,a) bn_mul_normal(r,a,4,a,4)
-#endif
-#endif
-
#if !defined(NO_ASM) && !defined(NO_INLINE_ASM) && !defined(PEDANTIC)
/*
* BN_UMULT_HIGH section.
#define Lw(t) (((BN_ULONG)(t))&BN_MASK2)
#define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2)
-/* These are used for internal error checking and are not normally used */
+/* This is used for internal error checking and is not normally used */
#ifdef BN_DEBUG
-#define bn_check_top(a) \
- { if (((a)->top < 0) || ((a)->top > (a)->max)) \
- { char *nullp=NULL; *nullp='z'; } }
-#define bn_check_num(a) if ((a) < 0) { char *nullp=NULL; *nullp='z'; }
+# include <assert.h>
+# define bn_check_top(a) assert ((a)->top >= 0 && (a)->top <= (a)->max);
#else
-#define bn_check_top(a)
-#define bn_check_num(a)
+# define bn_check_top(a)
#endif
/* This macro is to add extra stuff for development checking */
bn_set_max(r); \
}
-/* #define bn_expand(n,b) ((((b)/BN_BITS2) <= (n)->max)?(n):bn_expand2((n),(b))) */
-
#ifdef BN_LLONG
#define mul_add(r,a,w,c) { \
BN_ULLONG t; \
(c)=h&BN_MASK2; \
(r)=l&BN_MASK2; \
}
-
-#endif
-
-OPENSSL_EXTERN int bn_limit_bits;
-OPENSSL_EXTERN int bn_limit_num; /* (1<<bn_limit_bits) */
-/* Recursive 'low' limit */
-OPENSSL_EXTERN int bn_limit_bits_low;
-OPENSSL_EXTERN int bn_limit_num_low; /* (1<<bn_limit_bits_low) */
-/* Do modified 'high' part calculation' */
-OPENSSL_EXTERN int bn_limit_bits_high;
-OPENSSL_EXTERN int bn_limit_num_high; /* (1<<bn_limit_bits_high) */
-OPENSSL_EXTERN int bn_limit_bits_mont;
-OPENSSL_EXTERN int bn_limit_num_mont; /* (1<<bn_limit_bits_mont) */
-
-BIGNUM *bn_expand2(BIGNUM *b, int bits);
+#endif /* !BN_LLONG */
void bn_mul_normal(BN_ULONG *r,BN_ULONG *a,int na,BN_ULONG *b,int nb);
void bn_mul_comba8(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b);
* 7 - 128 == 4096
* 8 - 256 == 8192
*/
-OPENSSL_GLOBAL int bn_limit_bits=0;
-OPENSSL_GLOBAL int bn_limit_num=8; /* (1<<bn_limit_bits) */
-OPENSSL_GLOBAL int bn_limit_bits_low=0;
-OPENSSL_GLOBAL int bn_limit_num_low=8; /* (1<<bn_limit_bits_low) */
-OPENSSL_GLOBAL int bn_limit_bits_high=0;
-OPENSSL_GLOBAL int bn_limit_num_high=8; /* (1<<bn_limit_bits_high) */
-OPENSSL_GLOBAL int bn_limit_bits_mont=0;
-OPENSSL_GLOBAL int bn_limit_num_mont=8; /* (1<<bn_limit_bits_mont) */
+static int bn_limit_bits=0;
+static int bn_limit_num=8; /* (1<<bn_limit_bits) */
+static int bn_limit_bits_low=0;
+static int bn_limit_num_low=8; /* (1<<bn_limit_bits_low) */
+static int bn_limit_bits_high=0;
+static int bn_limit_num_high=8; /* (1<<bn_limit_bits_high) */
+static int bn_limit_bits_mont=0;
+static int bn_limit_num_mont=8; /* (1<<bn_limit_bits_mont) */
void BN_set_params(int mult, int high, int low, int mont)
{
}
/* This is an internal function that should not be used in applications.
- * It ensures that 'b' has enough room for a 'bits' bit number. It is
- * mostly used by the various BIGNUM routines. If there is an error,
- * NULL is returned. if not, 'b' is returned.
- */
+ * It ensures that 'b' has enough room for a 'words' word number number.
+ * It is mostly used by the various BIGNUM routines. If there is an error,
+ * NULL is returned. If not, 'b' is returned. */
+
BIGNUM *bn_expand2(BIGNUM *b, int words)
{
BN_ULONG *A,*a;
unsigned int neg,zero;
BN_ULONG ln,lo,*p;
-#ifdef BN_COUNT
-printf(" bn_mul_recursive %d * %d\n",n2,n2);
-#endif
-#ifdef BN_MUL_COMBA
-/* if (n2 == 4)
+# ifdef BN_COUNT
+ printf(" bn_mul_recursive %d * %d\n",n2,n2);
+# endif
+# ifdef BN_MUL_COMBA
+# if 0
+ if (n2 == 4)
{
bn_mul_comba4(r,a,b);
return;
}
- else */ if (n2 == 8)
+# endif
+ if (n2 == 8)
{
bn_mul_comba8(r,a,b);
return;
}
-#endif
+# endif /* BN_MUL_COMBA */
if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
{
/* This should not happen */
break;
}
-#ifdef BN_MUL_COMBA
+# ifdef BN_MUL_COMBA
if (n == 4)
{
if (!zero)
bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
}
else
-#endif
+# endif /* BN_MUL_COMBA */
{
p= &(t[n2*2]);
if (!zero)
unsigned int c1;
BN_ULONG ln,lo,*p;
-#ifdef BN_COUNT
-printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
-#endif
+# ifdef BN_COUNT
+ printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
+# endif
if (n < 8)
{
i=tn+n;
bn_sub_words(t, a, &(a[n]),n); /* + */
bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
-/* if (n == 4)
+# if 0
+ if (n == 4)
{
bn_mul_comba4(&(t[n2]),t,&(t[n]));
bn_mul_comba4(r,a,b);
bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
}
- else */ if (n == 8)
+ else
+# endif
+ if (n == 8)
{
bn_mul_comba8(&(t[n2]),t,&(t[n]));
bn_mul_comba8(r,a,b);
{
int n=n2/2;
-#ifdef BN_COUNT
-printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
-#endif
+# ifdef BN_COUNT
+ printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
+# endif
bn_mul_recursive(r,a,b,n,&(t[0]));
if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
int neg,oneg,zero;
BN_ULONG ll,lc,*lp,*mp;
-#ifdef BN_COUNT
-printf(" bn_mul_high %d * %d\n",n2,n2);
-#endif
+# ifdef BN_COUNT
+ printf(" bn_mul_high %d * %d\n",n2,n2);
+# endif
n=n2/2;
/* Calculate (al-ah)*(bh-bl) */
oneg=neg;
/* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
/* r[10] = (a[1]*b[1]) */
-#ifdef BN_MUL_COMBA
+# ifdef BN_MUL_COMBA
if (n == 8)
{
bn_mul_comba8(&(t[0]),&(r[0]),&(r[n]));
bn_mul_comba8(r,&(a[n]),&(b[n]));
}
else
-#endif
+# endif
{
bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
}
}
}
-#endif
+#endif /* BN_RECURSION */
int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
{
int top,al,bl;
BIGNUM *rr;
+ int ret = 0;
+#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
+ int i;
+#endif
#ifdef BN_RECURSION
BIGNUM *t;
- int i,j,k;
+ int j,k;
#endif
#ifdef BN_COUNT
-printf("BN_mul %d * %d\n",a->top,b->top);
+ printf("BN_mul %d * %d\n",a->top,b->top);
#endif
bn_check_top(a);
rr = r;
#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
- if (al == bl)
+ i = al-bl;
+#endif
+#ifdef BN_MUL_COMBA
+ if (i == 0)
{
-# ifdef BN_MUL_COMBA
-/* if (al == 4)
+# if 0
+ if (al == 4)
{
if (bn_wexpand(rr,8) == NULL) goto err;
rr->top=8;
bn_mul_comba4(rr->d,a->d,b->d);
goto end;
}
- else */ if (al == 8)
+# endif
+ if (al == 8)
{
if (bn_wexpand(rr,16) == NULL) goto err;
rr->top=16;
bn_mul_comba8(rr->d,a->d,b->d);
goto end;
}
- else
-# endif
-#ifdef BN_RECURSION
- if (al < BN_MULL_SIZE_NORMAL)
-#endif
- {
- if (bn_wexpand(rr,top) == NULL) goto err;
- rr->top=top;
- bn_mul_normal(rr->d,a->d,al,b->d,bl);
- goto end;
- }
-# ifdef BN_RECURSION
- goto symmetric;
-# endif
}
-#endif
+#endif /* BN_MUL_COMBA */
#ifdef BN_RECURSION
- else if ((al < BN_MULL_SIZE_NORMAL) || (bl < BN_MULL_SIZE_NORMAL))
- {
- if (bn_wexpand(rr,top) == NULL) goto err;
- rr->top=top;
- bn_mul_normal(rr->d,a->d,al,b->d,bl);
- goto end;
- }
- else
+ if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL))
{
- i=(al-bl);
- if ((i == 1) && !BN_get_flags(b,BN_FLG_STATIC_DATA))
+ if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA))
{
bn_wexpand(b,al);
b->d[bl]=0;
bl++;
- goto symmetric;
+ i--;
}
- else if ((i == -1) && !BN_get_flags(a,BN_FLG_STATIC_DATA))
+ else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA))
{
bn_wexpand(a,bl);
a->d[al]=0;
al++;
- goto symmetric;
+ i++;
+ }
+ if (i == 0)
+ {
+ /* symmetric and > 4 */
+ /* 16 or larger */
+ j=BN_num_bits_word((BN_ULONG)al);
+ j=1<<(j-1);
+ k=j+j;
+ t = BN_CTX_get(ctx);
+ if (al == j) /* exact multiple */
+ {
+ bn_wexpand(t,k*2);
+ bn_wexpand(rr,k*2);
+ bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
+ }
+ else
+ {
+ bn_wexpand(a,k);
+ bn_wexpand(b,k);
+ bn_wexpand(t,k*4);
+ bn_wexpand(rr,k*4);
+ for (i=a->top; i<k; i++)
+ a->d[i]=0;
+ for (i=b->top; i<k; i++)
+ b->d[i]=0;
+ bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
+ }
+ rr->top=top;
+ goto end;
}
}
-#endif
+#endif /* BN_RECURSION */
- /* asymmetric and >= 4 */
if (bn_wexpand(rr,top) == NULL) goto err;
rr->top=top;
bn_mul_normal(rr->d,a->d,al,b->d,bl);
-#ifdef BN_RECURSION
- if (0)
- {
-symmetric:
- /* symmetric and > 4 */
- /* 16 or larger */
- j=BN_num_bits_word((BN_ULONG)al);
- j=1<<(j-1);
- k=j+j;
- t = BN_CTX_get(ctx);
- if (al == j) /* exact multiple */
- {
- bn_wexpand(t,k*2);
- bn_wexpand(rr,k*2);
- bn_mul_recursive(rr->d,a->d,b->d,al,t->d);
- }
- else
- {
- bn_wexpand(a,k);
- bn_wexpand(b,k);
- bn_wexpand(t,k*4);
- bn_wexpand(rr,k*4);
- for (i=a->top; i<k; i++)
- a->d[i]=0;
- for (i=b->top; i<k; i++)
- b->d[i]=0;
- bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d);
- }
- rr->top=top;
- }
-#endif
#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
end:
#endif
bn_fix_top(rr);
if (r != rr) BN_copy(r,rr);
- BN_CTX_end(ctx);
- return(1);
+ ret=1;
err:
BN_CTX_end(ctx);
- return(0);
+ return(ret);
}
void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
BN_ULONG *rr;
#ifdef BN_COUNT
-printf(" bn_mul_normal %d * %d\n",na,nb);
+ printf(" bn_mul_normal %d * %d\n",na,nb);
#endif
if (na < nb)
void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
{
#ifdef BN_COUNT
-printf(" bn_mul_low_normal %d * %d\n",n,n);
+ printf(" bn_mul_low_normal %d * %d\n",n,n);
#endif
bn_mul_words(r,a,n,b[0]);
b+=4;
}
}
-
+++ /dev/null
-/* unused */
-
-/* crypto/bn/bn_opts.c */
-/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
- * All rights reserved.
- *
- * This package is an SSL implementation written
- * by Eric Young (eay@cryptsoft.com).
- * The implementation was written so as to conform with Netscapes SSL.
- *
- * This library is free for commercial and non-commercial use as long as
- * the following conditions are aheared to. The following conditions
- * apply to all code found in this distribution, be it the RC4, RSA,
- * lhash, DES, etc., code; not just the SSL code. The SSL documentation
- * included with this distribution is covered by the same copyright terms
- * except that the holder is Tim Hudson (tjh@cryptsoft.com).
- *
- * Copyright remains Eric Young's, and as such any Copyright notices in
- * the code are not to be removed.
- * If this package is used in a product, Eric Young should be given attribution
- * as the author of the parts of the library used.
- * This can be in the form of a textual message at program startup or
- * in documentation (online or textual) provided with the package.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- * must display the following acknowledgement:
- * "This product includes cryptographic software written by
- * Eric Young (eay@cryptsoft.com)"
- * The word 'cryptographic' can be left out if the rouines from the library
- * being used are not cryptographic related :-).
- * 4. If you include any Windows specific code (or a derivative thereof) from
- * the apps directory (application code) you must include an acknowledgement:
- * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
- *
- * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * The licence and distribution terms for any publically available version or
- * derivative of this code cannot be changed. i.e. this code cannot simply be
- * copied and put under another distribution licence
- * [including the GNU Public Licence.]
- */
-
-/* most of this code has been pilfered from my libdes speed.c program */
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <signal.h>
-#include <string.h>
-#include <openssl/crypto.h>
-#include <openssl/tmdiff.h>
-#include <openssl/bn.h>
-#include <openssl/err.h>
-
-#define DEFAULT_SIZE 512
-#define DEFAULT_TIME 3
-
-int verbose=1;
-
-typedef struct parms_st
- {
- char *name;
- void (*func)();
- BIGNUM r;
- BIGNUM a;
- BIGNUM b;
- BIGNUM c;
- BIGNUM low;
- BN_CTX *ctx;
- BN_MONT_CTX *mont;
- int w;
- } PARMS;
-
-void do_mul_exp(int num,PARMS *p);
-void do_mul(int num,PARMS *p);
-void do_sqr(int num,PARMS *p);
-void do_mul_low(int num,PARMS *p);
-void do_mul_high(int num,PARMS *p);
-void do_from_montgomery(int num,PARMS *p);
-int time_it(int sec, PARMS *p);
-void do_it(int sec, PARMS *p);
-
-#define P_EXP 1
-#define P_MUL 2
-#define P_SQR 3
-#define P_MULL 4
-#define P_MULH 5
-#define P_MRED 6
-
-int main(int argc, char **argv)
- {
- PARMS p;
- BN_MONT_CTX *mont;
- int size=0,num;
- char *name;
- int type=P_EXP;
-
- mont=BN_MONT_CTX_new();
- p.mont=NULL;
- p.ctx=BN_CTX_new();
- BN_init(&p.r);
- BN_init(&p.a);
- BN_init(&p.b);
- BN_init(&p.c);
- BN_init(&p.low);
- p.w=0;
-
- for (;;)
- {
- if (argc > 1)
- {
- if (argv[1][0] == '-')
- {
- switch(argv[1][1])
- {
- case 'e': type=P_EXP; break;
- case 'm': type=P_MUL; break;
- case 's': type=P_SQR; break;
- case 'l': type=P_MULL; break;
- case 'h': type=P_MULH; break;
- case 'r': type=P_MRED; break;
- default:
- fprintf(stderr,"options: -[emslhr]\n");
- exit(1);
- }
- }
- else
- {
- size=atoi(argv[1]);
- }
- argc--;
- argv++;
- }
- else
- break;
- }
- if (size == 0)
- size=DEFAULT_SIZE;
-
- printf("bit size:%5d\n",size);
-
- BN_rand(&p.a,size,1,0);
- BN_rand(&p.b,size,1,0);
- BN_rand(&p.c,size,1,1);
- BN_mod(&p.a,&p.a,&p.c,p.ctx);
- BN_mod(&p.b,&p.b,&p.c,p.ctx);
- p.w=(p.a.top+1)/2;
-
- BN_mul(&p.low,&p.a,&p.b,p.ctx);
- p.low.top=p.a.top;
-
- switch(type)
- {
- case P_EXP:
- p.name="r=a^b%c";
- p.func=do_mul_exp;
- p.mont=mont;
- break;
- case P_MUL:
- p.name="r=a*b";
- p.func=do_mul;
- break;
- case P_SQR:
- p.name="r=a*a";
- p.func=do_sqr;
- break;
- case P_MULL:
- p.name="r=low(a*b)";
- p.func=do_mul_low;
- break;
- case P_MULH:
- p.name="r=high(a*b)";
- p.func=do_mul_high;
- break;
- case P_MRED:
- p.name="r=montgomery_reduction(a)";
- p.func=do_from_montgomery;
- p.mont=mont;
- break;
- default:
- fprintf(stderr,"options: -[emslhr]\n");
- exit(1);
- }
-
- num=time_it(DEFAULT_TIME,&p);
- do_it(num,&p);
- }
-
-void do_it(int num, PARMS *p)
- {
- char *start,*end;
- int i,j,number;
- double d;
-
- start=ms_time_new();
- end=ms_time_new();
-
- number=BN_num_bits_word((BN_ULONG)BN_num_bits(&(p->c)))-
- BN_num_bits_word(BN_BITS2)+2;
- for (i=number-1; i >=0; i--)
- {
- if (i == 1) continue;
- BN_set_params(i,i,i,1);
- if (p->mont != NULL)
- BN_MONT_CTX_set(p->mont,&(p->c),p->ctx);
-
- printf("Timing %5d (%2d bit) %2d %2d %2d %2d :",
- (1<<i)*BN_BITS2,i,
- BN_get_params(0),
- BN_get_params(1),
- BN_get_params(2),
- BN_get_params(3));
- fflush(stdout);
-
- ms_time_get(start);
- p->func(num,p);
- ms_time_get(end);
- d=ms_time_diff(start,end);
- printf("%6.6f sec, or %d in %.4f seconds\n",
- (double)d/num,num,d);
- }
- }
-
-int time_it(int sec, PARMS *p)
- {
- char *start,*end;
- int i,j;
- double d;
-
- if (p->mont != NULL)
- BN_MONT_CTX_set(p->mont,&(p->c),p->ctx);
-
- start=ms_time_new();
- end=ms_time_new();
-
- i=1;
- for (;;)
- {
- if (verbose)
- printf("timing %s for %d iterations\n",p->name,i);
-
- ms_time_get(start);
- p->func(i,p);
- ms_time_get(end);
- d=ms_time_diff(start,end);
-
- if (d < 0.01) i*=100;
- else if (d < 0.1 ) i*=10;
- else if (d > (double)sec) break;
- else
- {
- i=(int)(1.0*i*sec/d);
- break;
- }
- }
- if (verbose)
- printf("using %d iterations\n",i);
- return(i);
- }
-
-void do_mul_exp(int num, PARMS *p)
- {
- int i;
-
- for (i=0; i<num; i++)
- BN_mod_exp_mont(&(p->r),&(p->a),&(p->b),&(p->c),
- p->ctx,p->mont);
- }
-
-void do_mul(int num, PARMS *p)
- {
- int i;
-
- for (i=0; i<num; i++)
- BN_mul(&(p->r),&(p->a),&(p->b),p->ctx);
- }
-
-void do_sqr(int num, PARMS *p)
- {
- int i;
-
- for (i=0; i<num; i++)
- BN_sqr(&(p->r),&(p->a),p->ctx);
- }
-
-void do_mul_low(int num, PARMS *p)
- {
- int i;
-
- for (i=0; i<num; i++)
- BN_mul_low(&(p->r),&(p->a),&(p->b),p->w,p->ctx);
- }
-
-void do_mul_high(int num, PARMS *p)
- {
- int i;
-
- for (i=0; i<num; i++)
- BN_mul_low(&(p->r),&(p->a),&(p->b),&(p->low),p->w,p->ctx);
- }
-
-void do_from_montgomery(int num, PARMS *p)
- {
- int i;
-
- for (i=0; i<num; i++)
- BN_from_montgomery(&(p->r),&(p->a),p->mont,p->ctx);
- }
-
}
#ifndef NO_BIO
-
#ifndef NO_FP_API
int BN_print_fp(FILE *fp, const BIGNUM *a)
{
end:
return(ret);
}
+#endif
+#ifdef BN_DEBUG
+void bn_dump1(FILE *o, const char *a, BN_ULONG *b,int n)
+ {
+ int i;
+ fprintf(o, "%s=", a);
+ for (i=n;i>=0;i--)
+ {
+ fprintf(o, "[%08lX]", b[i]);
+ }
+ fprintf(o, "\n");
+ }
#endif
+++ /dev/null
-#!/usr/local/bin/perl
-
-$num=8;
-$num2=8/2;
-
-print <<"EOF";
-/* crypto/bn/bn_comba.c */
-#include <stdio.h>
-#include "bn_lcl.h"
-/* Auto generated from crypto/bn/comba.pl
- */
-
-#undef bn_mul_comba8
-#undef bn_mul_comba4
-#undef bn_sqr_comba8
-#undef bn_sqr_comba4
-
-#ifdef BN_LLONG
-#define mul_add_c(a,b,c0,c1,c2) \\
- t=(BN_ULLONG)a*b; \\
- t1=(BN_ULONG)Lw(t); \\
- t2=(BN_ULONG)Hw(t); \\
- c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \\
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define mul_add_c2(a,b,c0,c1,c2) \\
- t=(BN_ULLONG)a*b; \\
- tt=(t+t)&BN_MASK; \\
- if (tt < t) c2++; \\
- t1=(BN_ULONG)Lw(tt); \\
- t2=(BN_ULONG)Hw(tt); \\
- c0=(c0+t1)&BN_MASK2; \\
- if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \\
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define sqr_add_c(a,i,c0,c1,c2) \\
- t=(BN_ULLONG)a[i]*a[i]; \\
- t1=(BN_ULONG)Lw(t); \\
- t2=(BN_ULONG)Hw(t); \\
- c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \\
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define sqr_add_c2(a,i,j,c0,c1,c2) \\
- mul_add_c2((a)[i],(a)[j],c0,c1,c2)
-#else
-#define mul_add_c(a,b,c0,c1,c2) \\
- t1=LBITS(a); t2=HBITS(a); \\
- bl=LBITS(b); bh=HBITS(b); \\
- mul64(t1,t2,bl,bh); \\
- c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \\
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define mul_add_c2(a,b,c0,c1,c2) \\
- t1=LBITS(a); t2=HBITS(a); \\
- bl=LBITS(b); bh=HBITS(b); \\
- mul64(t1,t2,bl,bh); \\
- if (t2 & BN_TBIT) c2++; \\
- t2=(t2+t2)&BN_MASK2; \\
- if (t1 & BN_TBIT) t2++; \\
- t1=(t1+t1)&BN_MASK2; \\
- c0=(c0+t1)&BN_MASK2; \\
- if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \\
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define sqr_add_c(a,i,c0,c1,c2) \\
- sqr64(t1,t2,(a)[i]); \\
- c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \\
- c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
-
-#define sqr_add_c2(a,i,j,c0,c1,c2) \\
- mul_add_c2((a)[i],(a)[j],c0,c1,c2)
-#endif
-
-void bn_mul_comba${num}(r,a,b)
-BN_ULONG *r,*a,*b;
- {
-#ifdef BN_LLONG
- BN_ULLONG t;
-#else
- BN_ULONG bl,bh;
-#endif
- BN_ULONG t1,t2;
- BN_ULONG c1,c2,c3;
-
-EOF
-$ret=&combas_mul("r","a","b",$num,"c1","c2","c3");
-printf <<"EOF";
- }
-
-void bn_mul_comba${num2}(r,a,b)
-BN_ULONG *r,*a,*b;
- {
-#ifdef BN_LLONG
- BN_ULLONG t;
-#else
- BN_ULONG bl,bh;
-#endif
- BN_ULONG t1,t2;
- BN_ULONG c1,c2,c3;
-
-EOF
-$ret=&combas_mul("r","a","b",$num2,"c1","c2","c3");
-printf <<"EOF";
- }
-
-void bn_sqr_comba${num}(r,a)
-BN_ULONG *r,*a;
- {
-#ifdef BN_LLONG
- BN_ULLONG t,tt;
-#else
- BN_ULONG bl,bh;
-#endif
- BN_ULONG t1,t2;
- BN_ULONG c1,c2,c3;
-
-EOF
-$ret=&combas_sqr("r","a",$num,"c1","c2","c3");
-printf <<"EOF";
- }
-
-void bn_sqr_comba${num2}(r,a)
-BN_ULONG *r,*a;
- {
-#ifdef BN_LLONG
- BN_ULLONG t,tt;
-#else
- BN_ULONG bl,bh;
-#endif
- BN_ULONG t1,t2;
- BN_ULONG c1,c2,c3;
-
-EOF
-$ret=&combas_sqr("r","a",$num2,"c1","c2","c3");
-printf <<"EOF";
- }
-EOF
-
-sub bn_str
- {
- local($var,$val)=@_;
- print "\t$var=$val;\n";
- }
-
-sub bn_ary
- {
- local($var,$idx)=@_;
- return("${var}[$idx]");
- }
-
-sub bn_clr
- {
- local($var)=@_;
-
- print "\t$var=0;\n";
- }
-
-sub bn_mad
- {
- local($a,$b,$c0,$c1,$c2,$num)=@_;
-
- if ($num == 2)
- { printf("\tmul_add_c2($a,$b,$c0,$c1,$c2);\n"); }
- else
- { printf("\tmul_add_c($a,$b,$c0,$c1,$c2);\n"); }
- }
-
-sub bn_sad
- {
- local($a,$i,$j,$c0,$c1,$c2,$num)=@_;
-
- if ($num == 2)
- { printf("\tsqr_add_c2($a,$i,$j,$c0,$c1,$c2);\n"); }
- else
- { printf("\tsqr_add_c($a,$i,$c0,$c1,$c2);\n"); }
- }
-
-sub combas_mul
- {
- local($r,$a,$b,$num,$c0,$c1,$c2)=@_;
- local($i,$as,$ae,$bs,$be,$ai,$bi);
- local($tot,$end);
-
- $as=0;
- $ae=0;
- $bs=0;
- $be=0;
- $tot=$num+$num-1;
- &bn_clr($c0);
- &bn_clr($c1);
- for ($i=0; $i<$tot; $i++)
- {
- $ai=$as;
- $bi=$bs;
- $end=$be+1;
- @numa=@numb=();
-
-#print "($as $ae) ($bs $be) $bs -> $end [$i $num]\n";
- for ($j=$bs; $j<$end; $j++)
- {
- push(@numa,$ai);
- push(@numb,$bi);
- $ai--;
- $bi++;
- }
-
- if ($i & 1)
- {
- @numa=reverse(@numa);
- @numb=reverse(@numb);
- }
-
- &bn_clr($c2);
- for ($j=0; $j<=$#numa; $j++)
- {
- &bn_mad(&bn_ary($a,$numa[$j]),
- &bn_ary($b,$numb[$j]),$c0,$c1,$c2,1);
- }
- &bn_str(&bn_ary($r,$i),$c0);
- ($c0,$c1,$c2)=($c1,$c2,$c0);
-
- $as++ if ($i < ($num-1));
- $ae++ if ($i >= ($num-1));
-
- $bs++ if ($i >= ($num-1));
- $be++ if ($i < ($num-1));
- }
- &bn_str(&bn_ary($r,$i),$c0);
- }
-
-sub combas_sqr
- {
- local($r,$a,$num,$c0,$c1,$c2)=@_;
- local($i,$as,$ae,$bs,$be,$ai,$bi);
- local($b,$tot,$end,$half);
-
- $b=$a;
- $as=0;
- $ae=0;
- $bs=0;
- $be=0;
- $tot=$num+$num-1;
- &bn_clr($c0);
- &bn_clr($c1);
- for ($i=0; $i<$tot; $i++)
- {
- $ai=$as;
- $bi=$bs;
- $end=$be+1;
- @numa=@numb=();
-
-#print "($as $ae) ($bs $be) $bs -> $end [$i $num]\n";
- for ($j=$bs; $j<$end; $j++)
- {
- push(@numa,$ai);
- push(@numb,$bi);
- $ai--;
- $bi++;
- last if ($ai < $bi);
- }
- if (!($i & 1))
- {
- @numa=reverse(@numa);
- @numb=reverse(@numb);
- }
-
- &bn_clr($c2);
- for ($j=0; $j <= $#numa; $j++)
- {
- if ($numa[$j] == $numb[$j])
- {&bn_sad($a,$numa[$j],$numb[$j],$c0,$c1,$c2,1);}
- else
- {&bn_sad($a,$numa[$j],$numb[$j],$c0,$c1,$c2,2);}
- }
- &bn_str(&bn_ary($r,$i),$c0);
- ($c0,$c1,$c2)=($c1,$c2,$c0);
-
- $as++ if ($i < ($num-1));
- $ae++ if ($i >= ($num-1));
-
- $bs++ if ($i >= ($num-1));
- $be++ if ($i < ($num-1));
- }
- &bn_str(&bn_ary($r,$i),$c0);
- }
+++ /dev/null
-/* unused */
-
-#include <stdio.h>
-#include <openssl/bio.h>
-#include "bn_lcl.h"
-
-#define SIZE_A (100*4+4)
-#define SIZE_B (13*4)
-
-main(argc,argv)
-int argc;
-char *argv[];
- {
- BN_CTX ctx;
- BN_RECP_CTX recp;
- BIGNUM a,b,dd,d,r,rr,t,l;
- int i;
-
- MemCheck_start();
- MemCheck_on();
- BN_CTX_init(&ctx);
- BN_RECP_CTX_init(&recp);
-
- BN_init(&r);
- BN_init(&rr);
- BN_init(&d);
- BN_init(&dd);
- BN_init(&a);
- BN_init(&b);
-
- {
- BN_rand(&a,SIZE_A,0,0);
- BN_rand(&b,SIZE_B,0,0);
-
- a.neg=1;
- BN_RECP_CTX_set(&recp,&b,&ctx);
-
- BN_print_fp(stdout,&a); printf(" a\n");
- BN_print_fp(stdout,&b); printf(" b\n");
-
- BN_print_fp(stdout,&recp.N); printf(" N\n");
- BN_print_fp(stdout,&recp.Nr); printf(" Nr num_bits=%d\n",recp.num_bits);
-
- BN_div_recp(&r,&d,&a,&recp,&ctx);
-
-for (i=0; i<300; i++)
- BN_div(&rr,&dd,&a,&b,&ctx);
-
- BN_print_fp(stdout,&r); printf(" div recp\n");
- BN_print_fp(stdout,&rr); printf(" div\n");
- BN_print_fp(stdout,&d); printf(" rem recp\n");
- BN_print_fp(stdout,&dd); printf(" rem\n");
- }
- BN_CTX_free(&ctx);
- BN_RECP_CTX_free(&recp);
-
- BN_free(&r);
- BN_free(&rr);
- BN_free(&d);
- BN_free(&dd);
- BN_free(&a);
- BN_free(&b);
-
- {
- BIO *out;
-
- if ((out=BIO_new(BIO_s_file())) != NULL)
- BIO_set_fp(out,stderr,BIO_NOCLOSE|BIO_FP_TEXT);
-
- CRYPTO_mem_leaks(out);
- BIO_free(out);
- }
-
- }
+DEL
void BN_RECP_CTX_init(BN_RECP_CTX *recp);
BN_RECP_CTX *BN_RECP_CTX_new();
void BN_RECP_CTX_free(BN_RECP_CTX *recp);
+++ /dev/null
-/* crypto/bn/bn_mul.c */
-/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
- * All rights reserved.
- *
- * This package is an SSL implementation written
- * by Eric Young (eay@cryptsoft.com).
- * The implementation was written so as to conform with Netscapes SSL.
- *
- * This library is free for commercial and non-commercial use as long as
- * the following conditions are aheared to. The following conditions
- * apply to all code found in this distribution, be it the RC4, RSA,
- * lhash, DES, etc., code; not just the SSL code. The SSL documentation
- * included with this distribution is covered by the same copyright terms
- * except that the holder is Tim Hudson (tjh@cryptsoft.com).
- *
- * Copyright remains Eric Young's, and as such any Copyright notices in
- * the code are not to be removed.
- * If this package is used in a product, Eric Young should be given attribution
- * as the author of the parts of the library used.
- * This can be in the form of a textual message at program startup or
- * in documentation (online or textual) provided with the package.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- * must display the following acknowledgement:
- * "This product includes cryptographic software written by
- * Eric Young (eay@cryptsoft.com)"
- * The word 'cryptographic' can be left out if the rouines from the library
- * being used are not cryptographic related :-).
- * 4. If you include any Windows specific code (or a derivative thereof) from
- * the apps directory (application code) you must include an acknowledgement:
- * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
- *
- * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * The licence and distribution terms for any publically available version or
- * derivative of this code cannot be changed. i.e. this code cannot simply be
- * copied and put under another distribution licence
- * [including the GNU Public Licence.]
- */
-
-#include <stdio.h>
-#include "cryptlib.h"
-#include "bn_lcl.h"
-
-static int bn_mm(BIGNUM *m,BIGNUM *A,BIGNUM *B, BIGNUM *sk,BN_CTX *ctx);
-
-/* r must be different to a and b */
-/* int BN_mmul(r, a, b) */
-int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b)
- {
- BN_ULONG *ap,*bp,*rp;
- BIGNUM *sk;
- int i,n,ret;
- int max,al,bl;
- BN_CTX ctx;
-
- bn_check_top(a);
- bn_check_top(b);
-
- al=a->top;
- bl=b->top;
- if ((al == 0) || (bl == 0))
- {
- r->top=0;
- return(1);
- }
-#ifdef BN_MUL_DEBUG
-printf("BN_mul(%d,%d)\n",a->top,b->top);
-#endif
-
- if ( (bn_limit_bits > 0) &&
- (bl > bn_limit_num) && (al > bn_limit_num))
- {
- n=(BN_num_bits_word(al|bl)-bn_limit_bits);
- n*=2;
- sk=(BIGNUM *)Malloc(sizeof(BIGNUM)*n);
- memset(sk,0,sizeof(BIGNUM)*n);
- memset(&ctx,0,sizeof(ctx));
-
- ret=bn_mm(r,a,b,&(sk[0]),&ctx);
- for (i=0; i<n; i+=2)
- {
- BN_clear_free(&sk[i]);
- BN_clear_free(&sk[i+1]);
- }
- Free(sk);
- return(ret);
- }
-
- max=(al+bl);
- if (bn_wexpand(r,max) == NULL) return(0);
- r->top=max;
- r->neg=a->neg^b->neg;
- ap=a->d;
- bp=b->d;
- rp=r->d;
-
- rp[al]=bn_mul_words(rp,ap,al,*(bp++));
- rp++;
- for (i=1; i<bl; i++)
- {
- rp[al]=bn_mul_add_words(rp,ap,al,*(bp++));
- rp++;
- }
- if ((max > 0) && (r->d[max-1] == 0)) r->top--;
- return(1);
- }
-
-
-#define ahal (sk[0])
-#define blbh (sk[1])
-
-/* r must be different to a and b */
-int bn_mm(BIGNUM *m, BIGNUM *A, BIGNUM *B, BIGNUM *sk, BN_CTX *ctx)
- {
- int n,num,sqr=0;
- int an,bn;
- BIGNUM ah,al,bh,bl;
-
- an=A->top;
- bn=B->top;
-#ifdef BN_MUL_DEBUG
-printf("bn_mm(%d,%d)\n",A->top,B->top);
-#endif
-
- if (A == B) sqr=1;
- num=(an>bn)?an:bn;
- n=(num+1)/2;
- /* Are going to now chop things into 'num' word chunks. */
-
- BN_init(&ah);
- BN_init(&al);
- BN_init(&bh);
- BN_init(&bl);
-
- bn_set_low (&al,A,n);
- bn_set_high(&ah,A,n);
- bn_set_low (&bl,B,n);
- bn_set_high(&bh,B,n);
-
- BN_sub(&ahal,&ah,&al);
- BN_sub(&blbh,&bl,&bh);
-
- if (num <= (bn_limit_num+bn_limit_num))
- {
- BN_mul(m,&ahal,&blbh);
- if (sqr)
- {
- BN_sqr(&ahal,&al,ctx);
- BN_sqr(&blbh,&ah,ctx);
- }
- else
- {
- BN_mul(&ahal,&al,&bl);
- BN_mul(&blbh,&ah,&bh);
- }
- }
- else
- {
- bn_mm(m,&ahal,&blbh,&(sk[2]),ctx);
- bn_mm(&ahal,&al,&bl,&(sk[2]),ctx);
- bn_mm(&blbh,&ah,&bh,&(sk[2]),ctx);
- }
-
- BN_add(m,m,&ahal);
- BN_add(m,m,&blbh);
-
- BN_lshift(m,m,n*BN_BITS2);
- BN_lshift(&blbh,&blbh,n*BN_BITS2*2);
-
- BN_add(m,m,&ahal);
- BN_add(m,m,&blbh);
-
- m->neg=A->neg^B->neg;
- return(1);
- }
-#undef ahal (sk[0])
-#undef blbh (sk[1])
-
-#include "bn_low.c"
-#include "bn_high.c"
+++ /dev/null
-/* crypto/bn/bn_mulw.c */
-/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
- * All rights reserved.
- *
- * This package is an SSL implementation written
- * by Eric Young (eay@cryptsoft.com).
- * The implementation was written so as to conform with Netscapes SSL.
- *
- * This library is free for commercial and non-commercial use as long as
- * the following conditions are aheared to. The following conditions
- * apply to all code found in this distribution, be it the RC4, RSA,
- * lhash, DES, etc., code; not just the SSL code. The SSL documentation
- * included with this distribution is covered by the same copyright terms
- * except that the holder is Tim Hudson (tjh@cryptsoft.com).
- *
- * Copyright remains Eric Young's, and as such any Copyright notices in
- * the code are not to be removed.
- * If this package is used in a product, Eric Young should be given attribution
- * as the author of the parts of the library used.
- * This can be in the form of a textual message at program startup or
- * in documentation (online or textual) provided with the package.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- * must display the following acknowledgement:
- * "This product includes cryptographic software written by
- * Eric Young (eay@cryptsoft.com)"
- * The word 'cryptographic' can be left out if the rouines from the library
- * being used are not cryptographic related :-).
- * 4. If you include any Windows specific code (or a derivative thereof) from
- * the apps directory (application code) you must include an acknowledgement:
- * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
- *
- * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * The licence and distribution terms for any publically available version or
- * derivative of this code cannot be changed. i.e. this code cannot simply be
- * copied and put under another distribution licence
- * [including the GNU Public Licence.]
- */
-
-#include <stdio.h>
-#include "cryptlib.h"
-#include "bn_lcl.h"
-
-#ifdef BN_LLONG
-
-ab
-12
- a2 b2
-a1 b1
-
-abc
-123
- a3 b3 c3
- a2 b2 c2
-a1 b1 c1
-
-abcd
-1234
- a4 b4 c4 d4
- a3 b3 c3 d3
- a2 b2 c2 d2
-a1 b1 c1 d1
-
-abcde
-01234
- a5 b5 c5 d5 e5
- a4 b4 c4 d4 e4
- a3 b3 c3 d3 e3
- a2 b2 c2 d2 e2
- a1 b1 c1 d1 e1
-a0 b0 c0 d0 e0
+++ /dev/null
-#include <stdio.h>
-#include "cryptlib.h"
-#include "bn_lcl.h"
-
-#undef BN_MUL_HIGH_DEBUG
-
-#ifdef BN_MUL_HIGH_DEBUG
-#define debug_BN_print(a,b,c) BN_print_fp(a,b); printf(c);
-#else
-#define debug_BN_print(a,b,c)
-#endif
-
-int BN_mul_high(BIGNUM *r,BIGNUM *a,BIGNUM *b,BIGNUM *low, int words);
-
-#undef t1
-#undef t2
-
-int BN_mul_high(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *low, int words)
- {
- int w2,borrow=0,full=0;
- BIGNUM t1,t2,t3,h,ah,al,bh,bl,m,s0,s1;
- BN_ULONG ul1,ul2;
-
- BN_mul(r,a,b);
- BN_rshift(r,r,words*BN_BITS2);
- return(1);
-
- w2=(words+1)/2;
-
-#ifdef BN_MUL_HIGH_DEBUG
-fprintf(stdout,"words=%d w2=%d\n",words,w2);
-#endif
-debug_BN_print(stdout,a," a\n");
-debug_BN_print(stdout,b," b\n");
-debug_BN_print(stdout,low," low\n");
- BN_init(&al); BN_init(&ah);
- BN_init(&bl); BN_init(&bh);
- BN_init(&t1); BN_init(&t2); BN_init(&t3);
- BN_init(&s0); BN_init(&s1);
- BN_init(&h); BN_init(&m);
-
- bn_set_low (&al,a,w2);
- bn_set_high(&ah,a,w2);
- bn_set_low (&bl,b,w2);
- bn_set_high(&bh,b,w2);
-
- bn_set_low(&s0,low,w2);
- bn_set_high(&s1,low,w2);
-
-debug_BN_print(stdout,&al," al\n");
-debug_BN_print(stdout,&ah," ah\n");
-debug_BN_print(stdout,&bl," bl\n");
-debug_BN_print(stdout,&bh," bh\n");
-debug_BN_print(stdout,&s0," s0\n");
-debug_BN_print(stdout,&s1," s1\n");
-
- /* Calculate (al-ah)*(bh-bl) */
- BN_sub(&t1,&al,&ah);
- BN_sub(&t2,&bh,&bl);
- BN_mul(&m,&t1,&t2);
-
- /* Calculate ah*bh */
- BN_mul(&h,&ah,&bh);
-
- /* s0 == low(al*bl)
- * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
- * We know s0 and s1 so the only unknown is high(al*bl)
- * high(al*bl) == s1 - low(ah*bh+(al-ah)*(bh-bl)+s0)
- */
- BN_add(&m,&m,&h);
- BN_add(&t2,&m,&s0);
-
-debug_BN_print(stdout,&t2," middle value\n");
-
- /* Quick and dirty mask off of high words */
- if (w2 < t2.top) t2.top=w2;
-#if 0
- bn_set_low(&t3,&t2,w2);
-#endif
-
-debug_BN_print(stdout,&t2," low middle value\n");
- BN_sub(&t1,&s1,&t2);
-
- if (t1.neg)
- {
-debug_BN_print(stdout,&t1," before\n");
- BN_zero(&t2);
- BN_set_bit(&t2,w2*BN_BITS2);
- BN_add(&t1,&t2,&t1);
- /* BN_mask_bits(&t1,w2*BN_BITS2); */
- /* if (words < t1.top) t1.top=words; */
-debug_BN_print(stdout,&t1," after\n");
- borrow=1;
- }
-
-/* XXXXX SPEED THIS UP */
- /* al*bl == high(al*bl)<<words+s0 */
- BN_lshift(&t1,&t1,w2*BN_BITS2);
- BN_add(&t1,&t1,&s0);
- if (w2*2 < t1.top) t1.top=w2*2; /* This should not happen? */
-
- /* We now have
- * al*bl - t1
- * (al-ah)*(bh-bl)+ah*bh - m
- * ah*bh - h
- */
-#if 0
- BN_add(&m,&m,&t1);
-debug_BN_print(stdout,&t1," s10\n");
-debug_BN_print(stdout,&m," s21\n");
-debug_BN_print(stdout,&h," s32\n");
- BN_lshift(&m,&m,w2*BN_BITS2);
- BN_lshift(&h,&h,w2*2*BN_BITS2);
- BN_add(r,&m,&t1);
- BN_add(r,r,&h);
- BN_rshift(r,r,w2*2*BN_BITS2);
-#else
- BN_add(&m,&m,&t1); /* Do a cmp then +1 if needed? */
- bn_set_high(&t3,&t1,w2);
- BN_add(&m,&m,&t3);
- bn_set_high(&t3,&m,w2);
- BN_add(r,&h,&t3);
-#endif
-
-#ifdef BN_MUL_HIGH_DEBUG
-printf("carry=%d\n",borrow);
-#endif
-debug_BN_print(stdout,r," ret\n");
- BN_free(&t1); BN_free(&t2);
- BN_free(&m); BN_free(&h);
- return(1);
- }
-
-
-
+++ /dev/null
-#include <stdio.h>
-#include <stdlib.h>
-#include <strings.h>
-#include "bn_lcl.h"
-
-/* r is 2*n2 words in size,
- * a and b are both n2 words in size.
- * n2 must be a power of 2.
- * We multiply and return the result.
- * t must be 2*n2 words in size
- * We calulate
- * a[0]*b[0]
- * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
- * a[1]*b[1]
- */
-void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
- BN_ULONG *t)
- {
- int n=n2/2;
- int neg,zero,c1,c2;
- BN_ULONG ln,lo,*p;
-
-#ifdef BN_COUNT
-printf(" bn_mul_recursive %d * %d\n",n2,n2);
-#endif
- if (n2 <= 8)
- {
- if (n2 == 8)
- bn_mul_comba8(r,a,b);
- else
- bn_mul_normal(r,a,n2,b,n2);
- return;
- }
-
- if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL)
- {
- /* This should not happen */
- /*abort(); */
- bn_mul_normal(r,a,n2,b,n2);
- return;
- }
- /* r=(a[0]-a[1])*(b[1]-b[0]) */
- c1=bn_cmp_words(a,&(a[n]),n);
- c2=bn_cmp_words(&(b[n]),b,n);
- zero=neg=0;
- switch (c1*3+c2)
- {
- case -4:
- bn_sub_words(t, &(a[n]),a, n); /* - */
- bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
- break;
- case -3:
- zero=1;
- break;
- case -2:
- bn_sub_words(t, &(a[n]),a, n); /* - */
- bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */
- neg=1;
- break;
- case -1:
- case 0:
- case 1:
- zero=1;
- break;
- case 2:
- bn_sub_words(t, a, &(a[n]),n); /* + */
- bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
- neg=1;
- break;
- case 3:
- zero=1;
- break;
- case 4:
- bn_sub_words(t, a, &(a[n]),n);
- bn_sub_words(&(t[n]),&(b[n]),b, n);
- break;
- }
-
- if (n == 8)
- {
- if (!zero)
- bn_mul_comba8(&(t[n2]),t,&(t[n]));
- else
- memset(&(t[n2]),0,8*sizeof(BN_ULONG));
-
- bn_mul_comba8(r,a,b);
- bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n]));
- }
- else
- {
- p= &(t[n2*2]);
- if (!zero)
- bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
- else
- memset(&(t[n2]),0,n*sizeof(BN_ULONG));
- bn_mul_recursive(r,a,b,n,p);
- bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,p);
- }
-
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- */
-
- c1=bn_add_words(t,r,&(r[n2]),n2);
-
- if (neg) /* if t[32] is negative */
- {
- c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
- }
- else
- {
- /* Might have a carry */
- c1+=bn_add_words(&(t[n2]),&(t[n2]),t,n2);
- }
-
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- * c1 holds the carry bits
- */
- c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
- if (c1)
- {
- p= &(r[n+n2]);
- lo= *p;
- ln=(lo+c1)&BN_MASK2;
- *p=ln;
-
- /* The overflow will stop before we over write
- * words we should not overwrite */
- if (ln < c1)
- {
- do {
- p++;
- lo= *p;
- ln=(lo+1)&BN_MASK2;
- *p=ln;
- } while (ln == 0);
- }
- }
- }
-
-/* n+tn is the word length
- * t needs to be n*4 is size, as does r */
-void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
- int n, BN_ULONG *t)
- {
- int n2=n*2,i,j;
- int c1;
- BN_ULONG ln,lo,*p;
-
-#ifdef BN_COUNT
-printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n);
-#endif
- if (n < 8)
- {
- i=tn+n;
- bn_mul_normal(r,a,i,b,i);
- return;
- }
-
- /* r=(a[0]-a[1])*(b[1]-b[0]) */
- bn_sub_words(t, a, &(a[n]),n); /* + */
- bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */
-
- if (n == 8)
- {
- bn_mul_comba8(&(t[n2]),t,&(t[n]));
- bn_mul_comba8(r,a,b);
- bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn);
- memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2));
- }
- else
- {
- p= &(t[n2*2]);
- bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p);
- bn_mul_recursive(r,a,b,n,p);
- i=n/2;
- /* If there is only a bottom half to the number,
- * just do it */
- j=tn-i;
- if (j == 0)
- {
- bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p);
- memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2));
- }
- else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
- {
- bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]),
- j,i,p);
- memset(&(r[n2+tn*2]),0,
- sizeof(BN_ULONG)*(n2-tn*2));
- }
- else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
- {
- memset(&(r[n2]),0,sizeof(BN_ULONG)*(tn*2));
- for (;;)
- {
- i/=2;
- if (i < tn)
- {
- bn_mul_part_recursive(&(r[n2]),
- &(a[n]),&(b[n]),
- tn-i,i,p);
- break;
- }
- else if (i == tn)
- {
- bn_mul_recursive(&(r[n2]),
- &(a[n]),&(b[n]),
- i,p);
- break;
- }
- }
- }
- }
-
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- */
-
- c1=bn_add_words(t,r,&(r[n2]),n2);
- c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
-
- /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- * c1 holds the carry bits
- */
- c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
- if (c1)
- {
- p= &(r[n+n2]);
- lo= *p;
- ln=(lo+c1)&BN_MASK2;
- *p=ln;
-
- /* The overflow will stop before we over write
- * words we should not overwrite */
- if (ln < c1)
- {
- do {
- p++;
- lo= *p;
- ln=(lo+1)&BN_MASK2;
- *p=ln;
- } while (ln == 0);
- }
- }
- }
-
-/* r is 2*n words in size,
- * a and b are both n words in size.
- * n must be a power of 2.
- * We multiply and return the result.
- * t must be 2*n words in size
- * We calulate
- * a[0]*b[0]
- * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
- * a[1]*b[1]
- */
-void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *t)
- {
- int n=n2/2;
- int zero,c1;
- BN_ULONG ln,lo,*p;
-
-#ifdef BN_COUNT
-printf(" bn_sqr_recursive %d * %d\n",n2,n2);
-#endif
- if (n2 == 4)
- {
- bn_sqr_comba4(r,a);
- return;
- }
- else if (n2 == 8)
- {
- bn_sqr_comba8(r,a);
- return;
- }
- if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL)
- {
- bn_sqr_normal(r,a,n2,t);
- return;
- abort();
- }
- /* r=(a[0]-a[1])*(a[1]-a[0]) */
- c1=bn_cmp_words(a,&(a[n]),n);
- zero=0;
- if (c1 > 0)
- bn_sub_words(t,a,&(a[n]),n);
- else if (c1 < 0)
- bn_sub_words(t,&(a[n]),a,n);
- else
- zero=1;
-
- /* The result will always be negative unless it is zero */
-
- if (n == 8)
- {
- if (!zero)
- bn_sqr_comba8(&(t[n2]),t);
- else
- memset(&(t[n2]),0,8*sizeof(BN_ULONG));
-
- bn_sqr_comba8(r,a);
- bn_sqr_comba8(&(r[n2]),&(a[n]));
- }
- else
- {
- p= &(t[n2*2]);
- if (!zero)
- bn_sqr_recursive(&(t[n2]),t,n,p);
- else
- memset(&(t[n2]),0,n*sizeof(BN_ULONG));
- bn_sqr_recursive(r,a,n,p);
- bn_sqr_recursive(&(r[n2]),&(a[n]),n,p);
- }
-
- /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
- * r[10] holds (a[0]*b[0])
- * r[32] holds (b[1]*b[1])
- */
-
- c1=bn_add_words(t,r,&(r[n2]),n2);
-
- /* t[32] is negative */
- c1-=bn_sub_words(&(t[n2]),t,&(t[n2]),n2);
-
- /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
- * r[10] holds (a[0]*a[0])
- * r[32] holds (a[1]*a[1])
- * c1 holds the carry bits
- */
- c1+=bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2);
- if (c1)
- {
- p= &(r[n+n2]);
- lo= *p;
- ln=(lo+c1)&BN_MASK2;
- *p=ln;
-
- /* The overflow will stop before we over write
- * words we should not overwrite */
- if (ln < c1)
- {
- do {
- p++;
- lo= *p;
- ln=(lo+1)&BN_MASK2;
- *p=ln;
- } while (ln == 0);
- }
- }
- }
-
-#if 1
-/* a and b must be the same size, which is n2.
- * r needs to be n2 words and t needs to be n2*2
- */
-void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
- BN_ULONG *t)
- {
- int n=n2/2;
-
-#ifdef BN_COUNT
-printf(" bn_mul_low_recursive %d * %d\n",n2,n2);
-#endif
-
- bn_mul_recursive(r,a,b,n,&(t[0]));
- if (n > BN_MUL_LOW_RECURSIVE_SIZE_NORMAL)
- {
- bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2]));
- bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
- bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2]));
- bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
- }
- else
- {
- bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n);
- bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n);
- bn_add_words(&(r[n]),&(r[n]),&(t[0]),n);
- bn_add_words(&(r[n]),&(r[n]),&(t[n]),n);
- }
- }
-
-/* a and b must be the same size, which is n2.
- * r needs to be n2 words and t needs to be n2*2
- * l is the low words of the output.
- * t needs to be n2*3
- */
-void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2,
- BN_ULONG *t)
- {
- int j,i,n,c1,c2;
- int neg,oneg,zero;
- BN_ULONG ll,lc,*lp,*mp;
-
-#ifdef BN_COUNT
-printf(" bn_mul_high %d * %d\n",n2,n2);
-#endif
- n=(n2+1)/2;
-
- /* Calculate (al-ah)*(bh-bl) */
- neg=zero=0;
- c1=bn_cmp_words(&(a[0]),&(a[n]),n);
- c2=bn_cmp_words(&(b[n]),&(b[0]),n);
- switch (c1*3+c2)
- {
- case -4:
- bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
- bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
- break;
- case -3:
- zero=1;
- break;
- case -2:
- bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n);
- bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
- neg=1;
- break;
- case -1:
- case 0:
- case 1:
- zero=1;
- break;
- case 2:
- bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
- bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n);
- neg=1;
- break;
- case 3:
- zero=1;
- break;
- case 4:
- bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n);
- bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n);
- break;
- }
-
- oneg=neg;
- /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
- bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2]));
- /* r[10] = (a[1]*b[1]) */
- bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2]));
-
- /* s0 == low(al*bl)
- * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
- * We know s0 and s1 so the only unknown is high(al*bl)
- * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
- * high(al*bl) == s1 - (r[0]+l[0]+t[0])
- */
- if (l != NULL)
- {
- lp= &(t[n2+n]);
- c1=bn_add_words(lp,&(r[0]),&(l[0]),n);
- }
- else
- {
- c1=0;
- lp= &(r[0]);
- }
-
- if (neg)
- neg=bn_sub_words(&(t[n2]),lp,&(t[0]),n);
- else
- {
- bn_add_words(&(t[n2]),lp,&(t[0]),n);
- neg=0;
- }
-
- if (l != NULL)
- {
- bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n);
- }
- else
- {
- lp= &(t[n2+n]);
- mp= &(t[n2]);
- for (i=0; i<n; i++)
- lp[i]=((~mp[i])+1)&BN_MASK2;
- }
-
- /* s[0] = low(al*bl)
- * t[3] = high(al*bl)
- * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
- * r[10] = (a[1]*b[1])
- */
- /* R[10] = al*bl
- * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
- * R[32] = ah*bh
- */
- /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
- * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
- * R[3]=r[1]+(carry/borrow)
- */
- if (l != NULL)
- {
- lp= &(t[n2]);
- c1= bn_add_words(lp,&(t[n2+n]),&(l[0]),n);
- }
- else
- {
- lp= &(t[n2+n]);
- c1=0;
- }
- c1+=bn_add_words(&(t[n2]),lp, &(r[0]),n);
- if (oneg)
- c1-=bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n);
- else
- c1+=bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n);
-
- c2 =bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n);
- c2+=bn_add_words(&(r[0]),&(r[0]),&(r[n]),n);
- if (oneg)
- c2-=bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n);
- else
- c2+=bn_add_words(&(r[0]),&(r[0]),&(t[n]),n);
-
- if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */
- {
- i=0;
- if (c1 > 0)
- {
- lc=c1;
- do {
- ll=(r[i]+lc)&BN_MASK2;
- r[i++]=ll;
- lc=(lc > ll);
- } while (lc);
- }
- else
- {
- lc= -c1;
- do {
- ll=r[i];
- r[i++]=(ll-lc)&BN_MASK2;
- lc=(lc > ll);
- } while (lc);
- }
- }
- if (c2 != 0) /* Add starting at r[1] */
- {
- i=n;
- if (c2 > 0)
- {
- lc=c2;
- do {
- ll=(r[i]+lc)&BN_MASK2;
- r[i++]=ll;
- lc=(lc > ll);
- } while (lc);
- }
- else
- {
- lc= -c2;
- do {
- ll=r[i];
- r[i++]=(ll-lc)&BN_MASK2;
- lc=(lc > ll);
- } while (lc);
- }
- }
- }
-#endif
+++ /dev/null
-/* crypto/bn/bn_mul.c */
-/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
- * All rights reserved.
- *
- * This package is an SSL implementation written
- * by Eric Young (eay@cryptsoft.com).
- * The implementation was written so as to conform with Netscapes SSL.
- *
- * This library is free for commercial and non-commercial use as long as
- * the following conditions are aheared to. The following conditions
- * apply to all code found in this distribution, be it the RC4, RSA,
- * lhash, DES, etc., code; not just the SSL code. The SSL documentation
- * included with this distribution is covered by the same copyright terms
- * except that the holder is Tim Hudson (tjh@cryptsoft.com).
- *
- * Copyright remains Eric Young's, and as such any Copyright notices in
- * the code are not to be removed.
- * If this package is used in a product, Eric Young should be given attribution
- * as the author of the parts of the library used.
- * This can be in the form of a textual message at program startup or
- * in documentation (online or textual) provided with the package.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- * must display the following acknowledgement:
- * "This product includes cryptographic software written by
- * Eric Young (eay@cryptsoft.com)"
- * The word 'cryptographic' can be left out if the rouines from the library
- * being used are not cryptographic related :-).
- * 4. If you include any Windows specific code (or a derivative thereof) from
- * the apps directory (application code) you must include an acknowledgement:
- * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
- *
- * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * The licence and distribution terms for any publically available version or
- * derivative of this code cannot be changed. i.e. this code cannot simply be
- * copied and put under another distribution licence
- * [including the GNU Public Licence.]
- */
-
-#include <stdio.h>
-#include "cryptlib.h"
-#include "bn_lcl.h"
-
-static int bn_mm_low(BIGNUM *m,BIGNUM *A,BIGNUM *B, int num,
- BIGNUM *sk,BN_CTX *ctx);
-int BN_mul_low(BIGNUM *r, BIGNUM *a, BIGNUM *b,int words);
-
-/* r must be different to a and b */
-int BN_mul_low(BIGNUM *r, BIGNUM *a, BIGNUM *b, int num)
- {
- BN_ULONG *ap,*bp,*rp;
- BIGNUM *sk;
- int j,i,n,ret;
- int max,al,bl;
- BN_CTX ctx;
-
- bn_check_top(a);
- bn_check_top(b);
-
-#ifdef BN_MUL_DEBUG
-printf("BN_mul_low(%d,%d,%d)\n",a->top,b->top,num);
-#endif
-
- al=a->top;
- bl=b->top;
- if ((al == 0) || (bl == 0))
- {
- r->top=0;
- return(1);
- }
-
- if ((bn_limit_bits_low > 0) && (num > bn_limit_num_low))
- {
- n=BN_num_bits_word(num*2)-bn_limit_bits_low;
- n*=2;
- sk=(BIGNUM *)Malloc(sizeof(BIGNUM)*n);
- memset(sk,0,sizeof(BIGNUM)*n);
- memset(&ctx,0,sizeof(ctx));
-
- ret=bn_mm_low(r,a,b,num,&(sk[0]),&ctx);
- for (i=0; i<n; i+=2)
- {
- BN_clear_free(&sk[i]);
- BN_clear_free(&sk[i+1]);
- }
- Free(sk);
- return(ret);
- }
-
- max=(al+bl);
- if (bn_wexpand(r,max) == NULL) return(0);
- r->neg=a->neg^b->neg;
- ap=a->d;
- bp=b->d;
- rp=r->d;
- r->top=(max > num)?num:max;
-
- rp[al]=bn_mul_words(rp,ap,al,*(bp++));
- rp++;
- j=bl;
- for (i=1; i<j; i++)
- {
- if (al >= num--)
- {
- al--;
- if (al <= 0) break;
- }
- rp[al]=bn_mul_add_words(rp,ap,al,*(bp++));
- rp++;
- }
-
- while ((r->top > 0) && (r->d[r->top-1] == 0))
- r->top--;
- return(1);
- }
-
-
-#define t1 (sk[0])
-#define t2 (sk[1])
-
-/* r must be different to a and b */
-int bn_mm_low(BIGNUM *m, BIGNUM *A, BIGNUM *B, int num, BIGNUM *sk,
- BN_CTX *ctx)
- {
- int n; /* ,sqr=0; */
- int an,bn;
- BIGNUM ah,al,bh,bl;
-
- bn_wexpand(m,num+3);
- an=A->top;
- bn=B->top;
-
-#ifdef BN_MUL_DEBUG
-printf("bn_mm_low(%d,%d,%d)\n",A->top,B->top,num);
-#endif
-
- n=(num+1)/2;
-
- BN_init(&ah); BN_init(&al); BN_init(&bh); BN_init(&bl);
-
- bn_set_low( &al,A,n);
- bn_set_high(&ah,A,n);
- bn_set_low( &bl,B,n);
- bn_set_high(&bh,B,n);
-
- if (num <= (bn_limit_num_low+bn_limit_num_low))
- {
- BN_mul(m,&al,&bl);
- BN_mul_low(&t1,&al,&bh,n);
- BN_mul_low(&t2,&ah,&bl,n);
- }
- else
- {
- bn_mm(m ,&al,&bl,&(sk[2]),ctx);
- bn_mm_low(&t1,&al,&bh,n,&(sk[2]),ctx);
- bn_mm_low(&t2,&ah,&bl,n,&(sk[2]),ctx);
- }
-
- BN_add(&t1,&t1,&t2);
-
- /* We will now do an evil hack instead of
- * BN_lshift(&t1,&t1,n*BN_BITS2);
- * BN_add(m,m,&t1);
- * BN_mask_bits(m,num*BN_BITS2);
- */
- bn_set_high(&ah,m,n); ah.max=num+2;
- BN_add(&ah,&ah,&t1);
- m->top=num;
-
- m->neg=A->neg^B->neg;
- return(1);
- }
-
-#undef t1 (sk[0])
-#undef t2 (sk[1])
+++ /dev/null
-/* crypto/bn/bn_m.c */
-/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
- * All rights reserved.
- *
- * This package is an SSL implementation written
- * by Eric Young (eay@cryptsoft.com).
- * The implementation was written so as to conform with Netscapes SSL.
- *
- * This library is free for commercial and non-commercial use as long as
- * the following conditions are aheared to. The following conditions
- * apply to all code found in this distribution, be it the RC4, RSA,
- * lhash, DES, etc., code; not just the SSL code. The SSL documentation
- * included with this distribution is covered by the same copyright terms
- * except that the holder is Tim Hudson (tjh@cryptsoft.com).
- *
- * Copyright remains Eric Young's, and as such any Copyright notices in
- * the code are not to be removed.
- * If this package is used in a product, Eric Young should be given attribution
- * as the author of the parts of the library used.
- * This can be in the form of a textual message at program startup or
- * in documentation (online or textual) provided with the package.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- * must display the following acknowledgement:
- * "This product includes cryptographic software written by
- * Eric Young (eay@cryptsoft.com)"
- * The word 'cryptographic' can be left out if the rouines from the library
- * being used are not cryptographic related :-).
- * 4. If you include any Windows specific code (or a derivative thereof) from
- * the apps directory (application code) you must include an acknowledgement:
- * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
- *
- * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * The licence and distribution terms for any publically available version or
- * derivative of this code cannot be changed. i.e. this code cannot simply be
- * copied and put under another distribution licence
- * [including the GNU Public Licence.]
- */
-
-#include <stdio.h>
-/*#include "cryptlib.h"*/
-#include "bn_lcl.h"
-
-#define limit_bits 5 /* 2^5, or 32 words */
-#define limit_num (1<<limit_bits)
-
-int BN_m(BIGNUM *r, BIGNUM *a, BIGNUM *b)
- {
- BIGNUM *sk;
- int i,n;
-
- n=(BN_num_bits_word(a->top|b->top)-limit_bits);
- n*=2;
- sk=(BIGNUM *)malloc(sizeof(BIGNUM)*n);
- for (i=0; i<n; i++)
- BN_init(&(sk[i]));
-
- return(BN_mm(r,a,b,&(sk[0])));
- }
-
-#define ahal (sk[0])
-#define blbh (sk[1])
-
-/* r must be different to a and b */
-int BN_mm(BIGNUM *m, BIGNUM *A, BIGNUM *B, BIGNUM *sk)
- {
- int i,num,anum,bnum;
- int an,bn;
- BIGNUM ah,al,bh,bl;
-
- an=A->top;
- bn=B->top;
- if ((an <= limit_num) || (bn <= limit_num))
- {
- return(BN_mul(m,A,B));
- }
-
- anum=(an>bn)?an:bn;
- num=(anum)/2;
-
- /* Are going to now chop things into 'num' word chunks. */
- bnum=num*BN_BITS2;
-
- BN_init(&ahal);
- BN_init(&blbh);
- BN_init(&ah);
- BN_init(&al);
- BN_init(&bh);
- BN_init(&bl);
-
- al.top=num;
- al.d=A->d;
- ah.top=A->top-num;
- ah.d= &(A->d[num]);
-
- bl.top=num;
- bl.d=B->d;
- bh.top=B->top-num;
- bh.d= &(B->d[num]);
-
- BN_sub(&ahal,&ah,&al);
- BN_sub(&blbh,&bl,&bh);
-
- BN_mm(m,&ahal,&blbh,&(sk[2]));
- BN_mm(&ahal,&al,&bl,&(sk[2]));
- BN_mm(&blbh,&ah,&bh,&(sk[2]));
-
- BN_add(m,m,&ahal);
- BN_add(m,m,&blbh);
-
- BN_lshift(m,m,bnum);
- BN_add(m,m,&ahal);
-
- BN_lshift(&blbh,&blbh,bnum*2);
- BN_add(m,m,&blbh);
-
- m->neg=A->neg^B->neg;
- return(1);
- }
-
+++ /dev/null
-/* crypto/bn/bn_mul.c */
-/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
- * All rights reserved.
- *
- * This package is an SSL implementation written
- * by Eric Young (eay@cryptsoft.com).
- * The implementation was written so as to conform with Netscapes SSL.
- *
- * This library is free for commercial and non-commercial use as long as
- * the following conditions are aheared to. The following conditions
- * apply to all code found in this distribution, be it the RC4, RSA,
- * lhash, DES, etc., code; not just the SSL code. The SSL documentation
- * included with this distribution is covered by the same copyright terms
- * except that the holder is Tim Hudson (tjh@cryptsoft.com).
- *
- * Copyright remains Eric Young's, and as such any Copyright notices in
- * the code are not to be removed.
- * If this package is used in a product, Eric Young should be given attribution
- * as the author of the parts of the library used.
- * This can be in the form of a textual message at program startup or
- * in documentation (online or textual) provided with the package.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- * must display the following acknowledgement:
- * "This product includes cryptographic software written by
- * Eric Young (eay@cryptsoft.com)"
- * The word 'cryptographic' can be left out if the rouines from the library
- * being used are not cryptographic related :-).
- * 4. If you include any Windows specific code (or a derivative thereof) from
- * the apps directory (application code) you must include an acknowledgement:
- * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
- *
- * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * The licence and distribution terms for any publically available version or
- * derivative of this code cannot be changed. i.e. this code cannot simply be
- * copied and put under another distribution licence
- * [including the GNU Public Licence.]
- */
-
-#include <stdio.h>
-#include "cryptlib.h"
-#include "bn_lcl.h"
-
-int bn_mm(BIGNUM *m,BIGNUM *A,BIGNUM *B, BIGNUM *sk,BN_CTX *ctx);
-
-/* r must be different to a and b */
-int BN_mul(r, a, b)
-BIGNUM *r;
-BIGNUM *a;
-BIGNUM *b;
- {
- BN_ULONG *ap,*bp,*rp;
- BIGNUM *sk;
- int i,n,ret;
- int max,al,bl;
- BN_CTX ctx;
-
- bn_check_top(a);
- bn_check_top(b);
-
- al=a->top;
- bl=b->top;
- if ((al == 0) || (bl == 0))
- {
- r->top=0;
- return(1);
- }
-#ifdef BN_MUL_DEBUG
-printf("BN_mul(%d,%d)\n",a->top,b->top);
-#endif
-
-#ifdef BN_RECURSION
- if ( (bn_limit_bits > 0) &&
- (bl > bn_limit_num) && (al > bn_limit_num))
- {
- n=(BN_num_bits_word(al|bl)-bn_limit_bits);
- n*=2;
- sk=(BIGNUM *)Malloc(sizeof(BIGNUM)*n);
- memset(sk,0,sizeof(BIGNUM)*n);
- memset(&ctx,0,sizeof(ctx));
-
- ret=bn_mm(r,a,b,&(sk[0]),&ctx);
- for (i=0; i<n; i+=2)
- {
- BN_clear_free(&sk[i]);
- BN_clear_free(&sk[i+1]);
- }
- Free(sk);
- return(ret);
- }
-#endif
-
- max=(al+bl);
- if (bn_wexpand(r,max) == NULL) return(0);
- r->top=max;
- r->neg=a->neg^b->neg;
- ap=a->d;
- bp=b->d;
- rp=r->d;
-
-#ifdef BN_RECURSION
- if ((al == bl) && (al == 8))
- {
- bn_mul_comba8(rp,ap,bp);
- }
- else
-#endif
- {
- rp[al]=bn_mul_words(rp,ap,al,*(bp++));
- rp++;
- for (i=1; i<bl; i++)
- {
- rp[al]=bn_mul_add_words(rp,ap,al,*(bp++));
- rp++;
- }
- }
- if ((max > 0) && (r->d[max-1] == 0)) r->top--;
- return(1);
- }
-
-#ifdef BN_RECURSION
-
-#define ahal (sk[0])
-#define blbh (sk[1])
-
-/* r must be different to a and b */
-int bn_mm(m, A, B, sk,ctx)
-BIGNUM *m,*A,*B;
-BIGNUM *sk;
-BN_CTX *ctx;
- {
- int n,num,sqr=0;
- int an,bn;
- BIGNUM ah,al,bh,bl;
-
- an=A->top;
- bn=B->top;
-#ifdef BN_MUL_DEBUG
-printf("bn_mm(%d,%d)\n",A->top,B->top);
-#endif
-
- if (A == B) sqr=1;
- num=(an>bn)?an:bn;
- n=(num+1)/2;
- /* Are going to now chop things into 'num' word chunks. */
-
- BN_init(&ah);
- BN_init(&al);
- BN_init(&bh);
- BN_init(&bl);
-
- bn_set_low (&al,A,n);
- bn_set_high(&ah,A,n);
- bn_set_low (&bl,B,n);
- bn_set_high(&bh,B,n);
-
- BN_sub(&ahal,&ah,&al);
- BN_sub(&blbh,&bl,&bh);
-
- if (num <= (bn_limit_num+bn_limit_num))
- {
- BN_mul(m,&ahal,&blbh);
- if (sqr)
- {
- BN_sqr(&ahal,&al,ctx);
- BN_sqr(&blbh,&ah,ctx);
- }
- else
- {
- BN_mul(&ahal,&al,&bl);
- BN_mul(&blbh,&ah,&bh);
- }
- }
- else
- {
- bn_mm(m,&ahal,&blbh,&(sk[2]),ctx);
- bn_mm(&ahal,&al,&bl,&(sk[2]),ctx);
- bn_mm(&blbh,&ah,&bh,&(sk[2]),ctx);
- }
-
- BN_add(m,m,&ahal);
- BN_add(m,m,&blbh);
-
- BN_lshift(m,m,n*BN_BITS2);
- BN_lshift(&blbh,&blbh,n*BN_BITS2*2);
-
- BN_add(m,m,&ahal);
- BN_add(m,m,&blbh);
-
- m->neg=A->neg^B->neg;
- return(1);
- }
-#undef ahal (sk[0])
-#undef blbh (sk[1])
-
-#include "bn_low.c"
-#include "bn_high.c"
-#include "f.c"
-
-#endif
+++ /dev/null
-#include <stdio.h>
-#include "bn_lcl.h"
-
-#if 1
-
-int bn_mull(BIGNUM *r,BIGNUM *a,BIGNUM *b, BN_CTX *ctx);
-
-int bn_mull(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
- {
- int top,i,j,k,al,bl;
- BIGNUM *t;
-
-#ifdef BN_COUNT
-printf("bn_mull %d * %d\n",a->top,b->top);
-#endif
-
- bn_check_top(a);
- bn_check_top(b);
- bn_check_top(r);
- BN_CTX_start(ctx);
-
- al=a->top;
- bl=b->top;
- r->neg=a->neg^b->neg;
-
- top=al+bl;
- if ((al < 4) || (bl < 4))
- {
- if (bn_wexpand(r,top) == NULL) return(0);
- r->top=top;
- bn_mul_normal(r->d,a->d,al,b->d,bl);
- goto end;
- }
- else if (al == bl) /* A good start, they are the same size */
- goto symetric;
- else
- {
- i=(al-bl);
- if ((i == 1) && !BN_get_flags(b,BN_FLG_STATIC_DATA))
- {
- bn_wexpand(b,al);
- b->d[bl]=0;
- bl++;
- goto symetric;
- }
- else if ((i == -1) && !BN_get_flags(a,BN_FLG_STATIC_DATA))
- {
- bn_wexpand(a,bl);
- a->d[al]=0;
- al++;
- goto symetric;
- }
- }
-
- /* asymetric and >= 4 */
- if (bn_wexpand(r,top) == NULL) return(0);
- r->top=top;
- bn_mul_normal(r->d,a->d,al,b->d,bl);
-
- if (0)
- {
- /* symetric and > 4 */
-symetric:
- if (al == 4)
- {
- if (bn_wexpand(r,al*2) == NULL) return(0);
- r->top=top;
- bn_mul_comba4(r->d,a->d,b->d);
- goto end;
- }
- if (al == 8)
- {
- if (bn_wexpand(r,al*2) == NULL) return(0);
- r->top=top;
- bn_mul_comba8(r->d,a->d,b->d);
- goto end;
- }
- if (al <= BN_MULL_NORMAL_SIZE)
- {
- if (bn_wexpand(r,al*2) == NULL) return(0);
- r->top=top;
- bn_mul_normal(r->d,a->d,al,b->d,bl);
- goto end;
- }
- /* 16 or larger */
- j=BN_num_bits_word((BN_ULONG)al);
- j=1<<(j-1);
- k=j+j;
- t = BN_CTX_get(ctx);
- if (al == j) /* exact multiple */
- {
- bn_wexpand(t,k*2);
- bn_wexpand(r,k*2);
- bn_mul_recursive(r->d,a->d,b->d,al,t->d);
- }
- else
- {
- bn_wexpand(a,k);
- bn_wexpand(b,k);
- bn_wexpand(t,k*4);
- bn_wexpand(r,k*4);
- for (i=a->top; i<k; i++)
- a->d[i]=0;
- for (i=b->top; i<k; i++)
- b->d[i]=0;
- bn_mul_part_recursive(r->d,a->d,b->d,al-j,j,t->d);
- }
- r->top=top;
- }
-end:
- BN_CTX_end(ctx);
- bn_fix_top(r);
- return(1);
- }
-#endif
-
-void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
- {
- BN_ULONG *rr;
-
-#ifdef BN_COUNT
-printf(" bn_mul_normal %d * %d\n",na,nb);
-#endif
-
- if (na < nb)
- {
- int itmp;
- BN_ULONG *ltmp;
-
- itmp=na; na=nb; nb=itmp;
- ltmp=a; a=b; b=ltmp;
-
- }
- rr= &(r[na]);
- rr[0]=bn_mul_words(r,a,na,b[0]);
-
- for (;;)
- {
- if (--nb <= 0) return;
- rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]);
- if (--nb <= 0) return;
- rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]);
- if (--nb <= 0) return;
- rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]);
- if (--nb <= 0) return;
- rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]);
- rr+=4;
- r+=4;
- b+=4;
- }
- }
-
-#if 1
-void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
- {
-#ifdef BN_COUNT
-printf(" bn_mul_low_normal %d * %d\n",n,n);
-#endif
- bn_mul_words(r,a,n,b[0]);
-
- for (;;)
- {
- if (--n <= 0) return;
- bn_mul_add_words(&(r[1]),a,n,b[1]);
- if (--n <= 0) return;
- bn_mul_add_words(&(r[2]),a,n,b[2]);
- if (--n <= 0) return;
- bn_mul_add_words(&(r[3]),a,n,b[3]);
- if (--n <= 0) return;
- bn_mul_add_words(&(r[4]),a,n,b[4]);
- r+=4;
- b+=4;
- }
- }
-#endif
+++ /dev/null
-#!/bin/sh -x
-
-gcc -g -I../../include test.c -L../.. -lcrypto
+++ /dev/null
-Given A1A0 * B1B0 == S3S2S1S0
-
-S0= low(A0*B0)
-S1= low( (A1-A0)*(B0-B1)) +low( A1*B1) +high(A0*B0)
-S2= high((A1-A0)*(B0-B1)) +high(A1*B1) +low( A1*B1)
-S3= high(A1*B1);
-
-Assume we know S1 and S0, and can calulate A1*B1 and high((A1-A0)*(B0-B1))
-
-k0= S0 == low(A0*B0)
-k1= S1
-k2= low( A1*B1)
-k3= high(A1*B1)
-k4= high((A1-A0)*(B0-B1))
-
-k1= low((A1-A0)*(B0-B1)) +k2 +high(A0*B0)
-S2= k4 +k3 +k2
-S3= k3
-
-S1-k2= low((A1-A0)*(B0-B1)) +high(A0*B0)
-
-We potentially have a carry or a borrow from S1
+++ /dev/null
-#include <stdio.h>
-#include "cryptlib.h"
-#include "bn_lcl.h"
-
-#define SIZE 128
-
-#define BN_MONT_CTX_set bn_mcs
-#define BN_from_montgomery bn_fm
-#define BN_mod_mul_montgomery bn_mmm
-#undef BN_to_montgomery
-#define BN_to_montgomery(r,a,mont,ctx) bn_mmm(\
- r,a,(mont)->RR,(mont),ctx)
-
-main()
- {
- BIGNUM prime,a,b,r,A,B,R;
- BN_MONT_CTX *mont;
- BN_CTX *ctx;
- int i;
-
- ctx=BN_CTX_new();
- BN_init(&prime);
- BN_init(&a); BN_init(&b); BN_init(&r);
- BN_init(&A); BN_init(&B); BN_init(&R);
-
- BN_generate_prime(&prime,SIZE,0,NULL,NULL,NULL,NULL);
- BN_rand(&A,SIZE,1,0);
- BN_rand(&B,SIZE,1,0);
- BN_mod(&A,&A,&prime,ctx);
- BN_mod(&B,&B,&prime,ctx);
-
- mont=BN_MONT_CTX_new();
- BN_MONT_CTX_set(mont,&prime,ctx);
-
- BN_to_montgomery(&a,&A,mont,ctx);
- BN_to_montgomery(&b,&B,mont,ctx);
-
- BN_mul(&r,&a,&b);
- BN_print_fp(stdout,&r); printf("\n");
- BN_from_montgomery(&r,&r,mont,ctx);
- BN_print_fp(stdout,&r); printf("\n");
- BN_from_montgomery(&r,&r,mont,ctx);
- BN_print_fp(stdout,&r); printf("\n");
-
- BN_mod_mul(&R,&A,&B,&prime,ctx);
-
- BN_print_fp(stdout,&a); printf("\n");
- BN_print_fp(stdout,&b); printf("\n");
- BN_print_fp(stdout,&prime); printf("\n");
- BN_print_fp(stdout,&r); printf("\n\n");
-
- BN_print_fp(stdout,&A); printf("\n");
- BN_print_fp(stdout,&B); printf("\n");
- BN_print_fp(stdout,&prime); printf("\n");
- BN_print_fp(stdout,&R); printf("\n\n");
-
- BN_mul(&r,&a,&b);
- BN_print_fp(stdout,&r); printf(" <- BA*DC\n");
- BN_copy(&A,&r);
- i=SIZE/2;
- BN_mask_bits(&A,i*2);
-// BN_print_fp(stdout,&A); printf(" <- low(BA*DC)\n");
- bn_do_lower(&r,&a,&b,&A,i);
-// BN_print_fp(stdout,&r); printf(" <- low(BA*DC)\n");
- }
-
-int bn_mul_low(r,a,b,low,i)
-BIGNUM *r,*a,*b,*low;
-int i;
- {
- int w;
- BIGNUM Kh,Km,t1,t2,h,ah,al,bh,bl,l,m,s0,s1;
-
- BN_init(&Kh); BN_init(&Km); BN_init(&t1); BN_init(&t2); BN_init(&l);
- BN_init(&ah); BN_init(&al); BN_init(&bh); BN_init(&bl); BN_init(&h);
- BN_init(&m); BN_init(&s0); BN_init(&s1);
-
- BN_copy(&al,a); BN_mask_bits(&al,i); BN_rshift(&ah,a,i);
- BN_copy(&bl,b); BN_mask_bits(&bl,i); BN_rshift(&bh,b,i);
-
-
- BN_sub(&t1,&al,&ah);
- BN_sub(&t2,&bh,&bl);
- BN_mul(&m,&t1,&t2);
- BN_mul(&h,&ah,&bh);
-
- BN_copy(&s0,low); BN_mask_bits(&s0,i);
- BN_rshift(&s1,low,i);
-
- BN_add(&t1,&h,&m);
- BN_add(&t1,&t1,&s0);
-
- BN_copy(&t2,&t1); BN_mask_bits(&t2,i);
- BN_sub(&t1,&s1,&t2);
- BN_lshift(&t1,&t1,i);
- BN_add(&t1,&t1,&s0);
- if (t1.neg)
- {
- BN_lshift(&t2,BN_value_one(),i*2);
- BN_add(&t1,&t2,&t1);
- BN_mask_bits(&t1,i*2);
- }
-
- BN_free(&Kh); BN_free(&Km); BN_free(&t1); BN_free(&t2);
- BN_free(&ah); BN_free(&al); BN_free(&bh); BN_free(&bl);
- }
-
-int BN_mod_mul_montgomery(r,a,b,mont,ctx)
-BIGNUM *r,*a,*b;
-BN_MONT_CTX *mont;
-BN_CTX *ctx;
- {
- BIGNUM *tmp;
-
- tmp= &(ctx->bn[ctx->tos++]);
-
- if (a == b)
- {
- if (!BN_sqr(tmp,a,ctx)) goto err;
- }
- else
- {
- if (!BN_mul(tmp,a,b)) goto err;
- }
- /* reduce from aRR to aR */
- if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
- ctx->tos--;
- return(1);
-err:
- return(0);
- }
-
-int BN_from_montgomery(r,a,mont,ctx)
-BIGNUM *r;
-BIGNUM *a;
-BN_MONT_CTX *mont;
-BN_CTX *ctx;
- {
- BIGNUM z1;
- BIGNUM *t1,*t2;
- BN_ULONG *ap,*bp,*rp;
- int j,i,bl,al;
-
- BN_init(&z1);
- t1= &(ctx->bn[ctx->tos]);
- t2= &(ctx->bn[ctx->tos+1]);
-
- if (!BN_copy(t1,a)) goto err;
- /* can cheat */
- BN_mask_bits(t1,mont->ri);
- if (!BN_mul(t2,t1,mont->Ni)) goto err;
- BN_mask_bits(t2,mont->ri);
-
- if (!BN_mul(t1,t2,mont->N)) goto err;
- if (!BN_add(t2,t1,a)) goto err;
-
- /* At this point, t2 has the bottom ri bits set to zero.
- * This means that the bottom ri bits == the 1^ri minus the bottom
- * ri bits of a.
- * This means that only the bits above 'ri' in a need to be added,
- * and XXXXXXXXXXXXXXXXXXXXXXXX
- */
-BN_print_fp(stdout,t2); printf("\n");
- BN_rshift(r,t2,mont->ri);
-
- if (BN_ucmp(r,mont->N) >= 0)
- bn_qsub(r,r,mont->N);
-
- return(1);
-err:
- return(0);
- }
-
-int BN_MONT_CTX_set(mont,mod,ctx)
-BN_MONT_CTX *mont;
-BIGNUM *mod;
-BN_CTX *ctx;
- {
- BIGNUM *Ri=NULL,*R=NULL;
-
- if (mont->RR == NULL) mont->RR=BN_new();
- if (mont->N == NULL) mont->N=BN_new();
-
- R=mont->RR; /* grab RR as a temp */
- BN_copy(mont->N,mod); /* Set N */
-
- mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
- BN_lshift(R,BN_value_one(),mont->ri); /* R */
- if ((Ri=BN_mod_inverse(NULL,R,mod,ctx)) == NULL) goto err;/* Ri */
- BN_lshift(Ri,Ri,mont->ri); /* R*Ri */
- bn_qsub(Ri,Ri,BN_value_one()); /* R*Ri - 1 */
- BN_div(Ri,NULL,Ri,mod,ctx);
- if (mont->Ni != NULL) BN_free(mont->Ni);
- mont->Ni=Ri; /* Ni=(R*Ri-1)/N */
-
- /* setup RR for conversions */
- BN_lshift(mont->RR,BN_value_one(),mont->ri*2);
- BN_mod(mont->RR,mont->RR,mont->N,ctx);
-
- return(1);
-err:
- return(0);
- }
-
-
+++ /dev/null
-/* unused */
-
-#include <stdio.h>
-#include "cryptlib.h"
-#include "bn_lcl.h"
-
-#define SIZE 32
-
-#define BN_MONT_CTX_set bn_mcs
-#define BN_from_montgomery bn_fm
-#define BN_mod_mul_montgomery bn_mmm
-#undef BN_to_montgomery
-#define BN_to_montgomery(r,a,mont,ctx) bn_mmm(\
- r,a,(mont)->RR,(mont),ctx)
-
-main()
- {
- BIGNUM prime,a,b,r,A,B,R;
- BN_MONT_CTX *mont;
- BN_CTX *ctx;
- int i;
-
- ctx=BN_CTX_new();
- BN_init(&prime);
- BN_init(&a); BN_init(&b); BN_init(&r);
- BN_init(&A); BN_init(&B); BN_init(&R);
-
- BN_generate_prime(&prime,SIZE,0,NULL,NULL,NULL,NULL);
- BN_rand(&A,SIZE,1,0);
- BN_rand(&B,SIZE,1,0);
- BN_mod(&A,&A,&prime,ctx);
- BN_mod(&B,&B,&prime,ctx);
-
- i=A.top;
- BN_mul(&R,&A,&B,ctx);
- BN_mask_bits(&R,i*BN_BITS2);
-
-
- BN_print_fp(stdout,&A); printf(" <- a\n");
- BN_print_fp(stdout,&B); printf(" <- b\n");
- BN_mul_high(&r,&A,&B,&R,i);
- BN_print_fp(stdout,&r); printf(" <- high(BA*DC)\n");
-
- BN_mask_bits(&A,i*32);
- BN_mask_bits(&B,i*32);
-
- BN_mul(&R,&A,&B);
- BN_rshift(&R,&R,i*32);
- BN_print_fp(stdout,&R); printf(" <- norm BA*DC\n");
- BN_sub(&R,&R,&r);
- BN_print_fp(stdout,&R); printf(" <- diff\n");
- }
-
-#if 0
-int bn_mul_high(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *low, int words)
- {
- int i;
- BIGNUM t1,t2,t3,h,ah,al,bh,bl,m,s0,s1;
-
- BN_init(&al); BN_init(&ah);
- BN_init(&bl); BN_init(&bh);
- BN_init(&t1); BN_init(&t2); BN_init(&t3);
- BN_init(&s0); BN_init(&s1);
- BN_init(&h); BN_init(&m);
-
- i=a->top;
- if (i >= words)
- {
- al.top=words;
- ah.top=a->top-words;
- ah.d= &(a->d[ah.top]);
- }
- else
- al.top=i;
- al.d=a->d;
-
- i=b->top;
- if (i >= words)
- {
- bl.top=words;
- bh.top=i-words;
- bh.d= &(b->d[bh.top]);
- }
- else
- bl.top=i;
- bl.d=b->d;
-
- i=low->top;
- if (i >= words)
- {
- s0.top=words;
- s1.top=i-words;
- s1.d= &(low->d[s1.top]);
- }
- else
- s0.top=i;
- s0.d=low->d;
-
-al.max=al.top; ah.max=ah.top;
-bl.max=bl.top; bh.max=bh.top;
-s0.max=bl.top; s1.max=bh.top;
-
- /* Calculate (al-ah)*(bh-bl) */
- BN_sub(&t1,&al,&ah);
- BN_sub(&t2,&bh,&bl);
- BN_mul(&m,&t1,&t2);
-
- /* Calculate ah*bh */
- BN_mul(&h,&ah,&bh);
-
- /* s0 == low(al*bl)
- * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
- * We know s0 and s1 so the only unknown is high(al*bl)
- * high(al*bl) == s1 - low(ah*bh+(al-ah)*(bh-bl)+s0)
- */
- BN_add(&m,&m,&h);
- BN_add(&t2,&m,&s0);
- /* Quick and dirty mask off of high words */
- t3.d=t2.d;
- t3.top=(t2.top > words)?words:t2.top;
- t3.neg=t2.neg;
-t3.max=t3.top;
-/* BN_print_fp(stdout,&s1); printf(" s1\n"); */
-/* BN_print_fp(stdout,&t2); printf(" middle value\n"); */
-/* BN_print_fp(stdout,&t3); printf(" low middle value\n"); */
- BN_sub(&t1,&s1,&t3);
-
- if (t1.neg)
- {
-/*printf("neg fixup\n"); BN_print_fp(stdout,&t1); printf(" before\n"); */
- BN_lshift(&t2,BN_value_one(),words*32);
- BN_add(&t1,&t2,&t1);
- BN_mask_bits(&t1,words*32);
-/* BN_print_fp(stdout,&t1); printf(" after\n"); */
- }
- /* al*bl == high(al*bl)<<words+s0 */
- BN_lshift(&t1,&t1,words*32);
- BN_add(&t1,&t1,&s0);
-
- /* We now have
- * al*bl - t1
- * (al-ah)*(bh-bl)+ah*bh - m
- * ah*bh - h
- */
- BN_copy(r,&t1);
- BN_mask_bits(r,words*32*2);
-
- /*BN_lshift(&m,&m,words*/
-
- BN_free(&t1); BN_free(&t2);
- BN_free(&m); BN_free(&h);
- }
-
-int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_MONT_CTX *mont,
- BN_CTX *ctx)
- {
- BIGNUM *tmp;
-
- tmp= &(ctx->bn[ctx->tos++]);
-
- if (a == b)
- {
- if (!BN_sqr(tmp,a,ctx)) goto err;
- }
- else
- {
- if (!BN_mul(tmp,a,b)) goto err;
- }
- /* reduce from aRR to aR */
- if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
- ctx->tos--;
- return(1);
-err:
- return(0);
- }
-
-int BN_from_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx)
- {
- BIGNUM z1;
- BIGNUM *t1,*t2;
- BN_ULONG *ap,*bp,*rp;
- int j,i,bl,al;
-
- BN_init(&z1);
- t1= &(ctx->bn[ctx->tos]);
- t2= &(ctx->bn[ctx->tos+1]);
-
- if (!BN_copy(t1,a)) goto err;
- /* can cheat */
- BN_mask_bits(t1,mont->ri);
- if (!BN_mul(t2,t1,mont->Ni)) goto err;
- BN_mask_bits(t2,mont->ri);
-
- if (!BN_mul(t1,t2,mont->N)) goto err;
- if (!BN_add(t2,t1,a)) goto err;
-
- /* At this point, t2 has the bottom ri bits set to zero.
- * This means that the bottom ri bits == the 1^ri minus the bottom
- * ri bits of a.
- * This means that only the bits above 'ri' in a need to be added,
- * and XXXXXXXXXXXXXXXXXXXXXXXX
- */
-BN_print_fp(stdout,t2); printf("\n");
- BN_rshift(r,t2,mont->ri);
-
- if (BN_ucmp(r,mont->N) >= 0)
- BN_usub(r,r,mont->N);
-
- return(1);
-err:
- return(0);
- }
-
-int BN_MONT_CTX_set(BN_MONT_CTX *mont, BIGNUM *mod, BN_CTX *ctx)
- {
- BIGNUM *Ri=NULL,*R=NULL;
-
- if (mont->RR == NULL) mont->RR=BN_new();
- if (mont->N == NULL) mont->N=BN_new();
-
- R=mont->RR; /* grab RR as a temp */
- BN_copy(mont->N,mod); /* Set N */
-
- mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
- BN_lshift(R,BN_value_one(),mont->ri); /* R */
- if ((Ri=BN_mod_inverse(NULL,R,mod,ctx)) == NULL) goto err;/* Ri */
- BN_lshift(Ri,Ri,mont->ri); /* R*Ri */
- BN_usub(Ri,Ri,BN_value_one()); /* R*Ri - 1 */
- BN_div(Ri,NULL,Ri,mod,ctx);
- if (mont->Ni != NULL) BN_free(mont->Ni);
- mont->Ni=Ri; /* Ni=(R*Ri-1)/N */
-
- /* setup RR for conversions */
- BN_lshift(mont->RR,BN_value_one(),mont->ri*2);
- BN_mod(mont->RR,mont->RR,mont->N,ctx);
-
- return(1);
-err:
- return(0);
- }
-
-
-#endif
numbers and L<BN_set_bit(3)|BN_set_bit(3)> with bit operations. The conversion
of B<BIGNUM>s to external formats is described in L<BN_bn2bin(3)|BN_bn2bin(3)>.
-=head1 INTERNALS
-
-The following description is based on the SSLeay documentation:
-
- typedef struct bignum_st
- {
- int top; /* Index of last used d. */
- BN_ULONG *d; /* Pointer to an array of 'BITS2' bit chunks. */
- int max; /* Size of the d array. */
- int neg;
- } BIGNUM;
-
-The big number is stored in B<d>, a malloc()ed array of B<BN_ULONG>s,
-least significant first. A B<BN_ULONG> can be either 16, 32 or 64 bits
-in size, depending on the 'number of bits' specified in bn.h.
-
-B<max> is the size of the B<d> array that has been allocated. B<top>
-is the 'last' entry being used, so for a value of 4, bn.d[0]=4 and
-bn.top=1. B<neg> is 1 if the number is negative. When a BIGNUM is
-'0', the B<d> field can be NULL and B<top> == 0. Various routines in
-this library require the use of temporary B<BIGNUM> variables during
-their execution. Since dynamic memory allocation to create B<BIGNUM>s
-is rather expensive when used in conjunction with repeated subroutine
-calls, the B<BN_CTX> structure is used. This structure contains
-B<BN_CTX_NUM> B<BIGNUM>s. B<BN_CTX_NUM> is the maximum number of
-temporary B<BIGNUM>s any publicly exported function will use.
-
- #define BN_CTX_NUM 12
- typedef struct bignum_ctx
- {
- int tos; /* top of stack */
- BIGNUM *bn[BN_CTX_NUM]; /* The variables */
- } BN_CTX;
-
-B<tos> is the index of the first unused B<BIGNUM> in the B<bn> array.
-
=head1 SEE ALSO
+L<bn_internal(3)|bn_internal(3)>,
L<dh(3)|dh(3)>, L<err(3)|err(3)>, L<rand(3)|rand(3)>, L<rsa(3)|rsa(3)>,
L<BN_new(3)|BN_new(3)>, L<BN_CTX_new(3)|BN_CTX_new(3)>,
L<BN_copy(3)|BN_copy(3)>, L<BN_num_bytes(3)|BN_num_bytes(3)>,
--- /dev/null
+=pod
+
+=head1 NAME
+
+bn_internal - BIGNUM library internal functions
+
+=head1 SYNOPSIS
+
+ BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);
+ BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num,
+ BN_ULONG w);
+ void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num);
+ BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
+ BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
+ int num);
+ BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
+ int num);
+
+ void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
+ void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
+ void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a);
+ void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a);
+
+ int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n);
+
+ void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b,
+ int nb);
+ void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
+ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
+ BN_ULONG *tmp);
+ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
+ int tn, int n, BN_ULONG *tmp);
+ void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
+ int n2, BN_ULONG *tmp);
+ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l,
+ int n2, BN_ULONG *tmp);
+
+ void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp);
+ void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp);
+
+ void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
+ void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c);
+ void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a);
+
+ BIGNUM *bn_expand(BIGNUM *a, int bits);
+ BIGNUM *bn_wexpand(BIGNUM *a, int n);
+ BIGNUM *bn_expand2(BIGNUM *a, int n);
+ void bn_fix_top(BIGNUM *a);
+
+ void bn_check_top(BIGNUM *a);
+ void bn_print(BIGNUM *a);
+ void bn_dump(BN_ULONG *d, int n);
+ void bn_set_max(BIGNUM *a);
+ void bn_set_high(BIGNUM *r, BIGNUM *a, int n);
+ void bn_set_low(BIGNUM *r, BIGNUM *a, int n);
+
+=head1 DESCRIPTION
+
+This page documents the internal functions used by the OpenSSL
+B<BIGNUM> implementation. They are described here to facilitate
+debugging and extending the library. They are I<not> to be used by
+applications.
+
+=head2 The BIGNUM structure
+
+ typedef struct bignum_st
+ {
+ int top; /* index of last used d (most significant word) */
+ BN_ULONG *d; /* pointer to an array of 'BITS2' bit chunks */
+ int max; /* size of the d array */
+ int neg; /* sign */
+ } BIGNUM;
+
+The big number is stored in B<d>, a malloc()ed array of B<BN_ULONG>s,
+least significant first. A B<BN_ULONG> can be either 16, 32 or 64 bits
+in size (B<BITS2>), depending on the 'number of bits' specified in
+C<openssl/bn.h>.
+
+B<max> is the size of the B<d> array that has been allocated. B<top>
+is the 'last' entry being used, so for a value of 4, bn.d[0]=4 and
+bn.top=1. B<neg> is 1 if the number is negative. When a B<BIGNUM> is
+B<0>, the B<d> field can be B<NULL> and B<top> == B<0>.
+
+Various routines in this library require the use of temporary
+B<BIGNUM> variables during their execution. Since dynamic memory
+allocation to create B<BIGNUM>s is rather expensive when used in
+conjunction with repeated subroutine calls, the B<BN_CTX> structure is
+used. This structure contains B<BN_CTX_NUM> B<BIGNUM>s.
+B<BN_CTX_NUM> is the maximum number of temporary B<BIGNUM>s any
+publicly exported function will use.
+
+ #define BN_CTX_NUM 12
+ typedef struct bignum_ctx
+ {
+ int tos; /* top of stack */
+ BIGNUM *bn[BN_CTX_NUM]; /* The variables */
+ } BN_CTX;
+
+B<tos> is the index of the first unused B<BIGNUM> in the B<bn> array.
+
+=head2 Low-level arithmetic operations
+
+These functions are implemented in C and for several platforms in
+assembly language:
+
+bn_mul_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num> word
+arrays B<rp> and B<ap>. It computes B<ap> * B<w>, places the result
+in B<rp>, and returns the high word (carry).
+
+bn_mul_add_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num>
+word arrays B<rp> and B<ap>. It computes B<ap> * B<w> + B<rp>, places
+the result in B<rp>, and returns the high word (carry).
+
+bn_sqr_words(B<rp>, B<ap>, B<n>) operates on the B<num> word array
+B<ap> and the 2*B<num> word array B<ap>. It computes B<ap> * B<ap>
+word-wise, and places the low and high bytes of the result in B<rp>.
+
+bn_div_words(B<h>, B<l>, B<d>) divides the two word number (B<h>,B<l>)
+by B<d> and returns the result.
+
+bn_add_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word
+arrays B<ap>, B<bp> and B<rp>. It computes B<ap> + B<bp>, places the
+result in B<rp>, and returns the high word (carry).
+
+bn_sub_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word
+arrays B<ap>, B<bp> and B<rp>. It computes B<ap> - B<bp>, places the
+result in B<rp>, and returns the carry (1 if B<bp> E<gt> B<ap>, 0
+otherwise).
+
+bn_mul_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and
+B<b> and the 8 word array B<r>. It computes B<a>*B<b> and places the
+result in B<r>.
+
+bn_mul_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and
+B<b> and the 16 word array B<r>. It computes B<a>*B<b> and places the
+result in B<r>.
+
+bn_sqr_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and
+B<b> and the 8 word array B<r>.
+
+bn_sqr_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and
+B<b> and the 16 word array B<r>.
+
+The following functions are implemented in C:
+
+bn_cmp_words(B<a>, B<b>, B<n>) operates on the B<n> word arrays B<a>
+and B<b>. It returns 1, 0 and -1 if B<a> is greater than, equal and
+less than B<b>.
+
+bn_mul_normal(B<r>, B<a>, B<na>, B<b>, B<nb>) operates on the B<na>
+word array B<a>, the B<nb> word array B<b> and the B<na>+B<nb> word
+array B<r>. It computes B<a>*B<b> and places the result in B<r>.
+
+bn_mul_low_normal(B<r>, B<a>, B<b>, B<n>) operates on the B<n> word
+arrays B<r>, B<a> und B<b>. It computes the B<n> low words of
+B<a>*B<b> and places the result in B<r>.
+
+bn_mul_recursive(B<r>, B<a>, B<b>, B<n2>, B<t>) operates on the B<n2>
+word arrays B<a> and B<b> and the 2*B<n2> word arrays B<r> and B<t>.
+B<n2> must be a power of 2. It computes B<a>*B<b> and places the
+result in B<r>.
+
+bn_mul_part_recursive(B<r>, B<a>, B<b>, B<tn>, B<n>, B<tmp>) operates
+on the B<n>+B<tn> word arrays B<a> and B<b> and the 4*B<n> word arrays
+B<r> and B<tmp>.
+
+bn_mul_low_recursive(B<r>, B<a>, B<b>, B<n2>, B<tmp>) operates on the
+B<n2> word arrays B<r> and B<tmp> and the B<n2>/2 word arrays B<a>
+and B<b>.
+
+bn_mul_high(B<r>, B<a>, B<b>, B<l>, B<n2>, B<tmp>) operates on the
+B<n2> word arrays B<r>, B<a>, B<b> and B<l> (?) and the 3*B<n2> word
+array B<tmp>.
+
+BN_mul() calls bn_mul_normal(), or an optimized implementation if the
+factors have the same size: bn_mul_comba8() is used if they are 8
+words long, bn_mul_recursive() if they are larger than
+B<BN_MULL_SIZE_NORMAL> and the size is an exact multiple of the word
+size, and bn_mul_part_recursive() for others that are larger than
+B<BN_MULL_SIZE_NORMAL>.
+
+bn_sqr_normal(B<r>, B<a>, B<n>, B<tmp>) operates on the B<n> word array
+B<a> and the 2*B<n> word arrays B<tmp> and B<r>.
+
+The implementations use the following macros which, depending on the
+architecture, may use "long long" C operations or inline assembler.
+They are defined in C<bn_lcl.h>.
+
+mul(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<c> and places the
+low word of the result in B<r> and the high word in B<c>.
+
+mul_add(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<r>+B<c> and
+places the low word of the result in B<r> and the high word in B<c>.
+
+sqr(B<r0>, B<r1>, B<a>) computes B<a>*B<a> and places the low word
+of the result in B<r0> and the high word in B<r1>.
+
+=head2 Size changes
+
+bn_expand() ensures that B<b> has enough space for a B<bits> bit
+number. bn_wexpand() ensures that B<b> has enough space for an
+B<n> word number. If the number has to be expanded, both macros
+call bn_expand2(), which allocates a new B<d> array and copies the
+data. They return B<NULL> on error, B<b> otherwise.
+
+The bn_fix_top() macro reduces B<a-E<gt>top> to most significant
+non-zero word when B<a> has shrunk.
+
+=head2 Debugging
+
+bn_check_top() verifies that C<((a)->top E<gt>= 0 && (a)-E<gt>top
+E<lt>= (a)-E<gt>max)>. A violation will cause the program to abort.
+
+bn_print() prints B<a> to stderr. bn_dump() prints B<n> words at B<d>
+(in reverse order, i.e. most significant word first) to stderr.
+
+bn_set_max() makes B<a> a static number with a B<max> of its current size.
+This is used by bn_set_low() and bn_set_high() to make B<r> a read-only
+B<BIGNUM> that contains the B<n> lower or higher words of B<a>.
+
+If B<BN_DEBUG> is not defined, bn_check_top(), bn_print(), bn_dump()
+and bn_set_max() are defined as empty macros.
+
+=head1 SEE ALSO
+
+L<bn(3)|bn(3)>
+
+=cut
cp Makefile.ssl Makefile.save
makedepend -f Makefile.ssl $@
-$TOP/util/clean-depend.pl < Makefile.ssl > Makefile.new
+perl $TOP/util/clean-depend.pl < Makefile.ssl > Makefile.new
mv Makefile.new Makefile.ssl
BIO_callback_ctrl 2252
RAND_egd 2253
RAND_status 2254
+bn_dump1 2255
projects / openssl.git / commitdiff