diff options
Diffstat (limited to 'crypto/bn')
41 files changed, 3750 insertions, 448 deletions
diff --git a/crypto/bn/Makefile.ssl b/crypto/bn/Makefile.ssl index cbddd4f3ea..9809d26cbc 100644 --- a/crypto/bn/Makefile.ssl +++ b/crypto/bn/Makefile.ssl @@ -11,9 +11,12 @@ INSTALLTOP=/usr/local/ssl MAKE= make -f Makefile.ssl MAKEDEPEND= makedepend -f Makefile.ssl MAKEFILE= Makefile.ssl -BN_MULW= bn_mulw.o AR= ar r +BN_MULW= bn_mulw.o +# or use +#BN_MULW= bn86-elf.o + CFLAGS= $(INCLUDES) $(CFLAG) ERR=bn @@ -24,12 +27,14 @@ APPS= LIB=$(TOP)/libcrypto.a LIBSRC= bn_add.c bn_div.c bn_exp.c bn_lib.c bn_mod.c bn_mul.c \ - bn_print.c bn_rand.c bn_shift.c bn_sub.c bn_word.c \ - bn_gcd.c bn_prime.c $(ERRC).c bn_sqr.c bn_mulw.c bn_recp.c bn_mont.c + bn_print.c bn_rand.c bn_shift.c bn_sub.c bn_word.c bn_blind.c \ + bn_gcd.c bn_prime.c $(ERRC).c bn_sqr.c bn_mulw.c bn_recp.c bn_mont.c \ + bn_mpi.c LIBOBJ= bn_add.o bn_div.o bn_exp.o bn_lib.o bn_mod.o bn_mul.o \ - bn_print.o bn_rand.o bn_shift.o bn_sub.o bn_word.o \ - bn_gcd.o bn_prime.o $(ERRC).o bn_sqr.o $(BN_MULW) bn_recp.o bn_mont.o + bn_print.o bn_rand.o bn_shift.o bn_sub.o bn_word.o bn_blind.o \ + bn_gcd.o bn_prime.o $(ERRC).o bn_sqr.o $(BN_MULW) bn_recp.o bn_mont.o \ + bn_mpi.o SRC= $(LIBSRC) @@ -56,6 +61,27 @@ lib: $(LIBOBJ) sh $(TOP)/util/ranlib.sh $(LIB) @touch lib +# elf +asm/bn86-elf.o: asm/bn86unix.cpp + $(CPP) -DELF asm/bn86unix.cpp | as -o asm/bn86-elf.o + +# solaris +asm/bn86-sol.o: asm/bn86unix.cpp + $(CC) -E -DSOL asm/bn86unix.cpp | sed 's/^#.*//' > asm/bn86-sol.s + as -o asm/bn86-sol.o asm/bn86-sol.s + rm -f asm/bn86-sol.s + +# a.out +asm/bn86-out.o: asm/bn86unix.cpp + $(CPP) -DOUT asm/bn86unix.cpp | as -o asm/bn86-out.o + +# bsdi +asm/bn86bsdi.o: asm/bn86unix.cpp + $(CPP) -DBSDI asm/bn86unix.cpp | as -o asm/bn86bsdi.o + +asm/bn86unix.cpp: + (cd asm; perl bn-586.pl cpp >bn86unix.cpp ) + files: perl $(TOP)/util/files.pl Makefile.ssl >> $(TOP)/MINFO @@ -102,6 +128,6 @@ clean: errors: perl $(TOP)/util/err-ins.pl $(ERR).err $(ERR).org # special case .org perl $(TOP)/util/err-ins.pl $(ERR).err $(ERR).h - perl ../err/err_genc.pl $(ERR).h $(ERRC).c + perl ../err/err_genc.pl -s $(ERR).h $(ERRC).c # DO NOT DELETE THIS LINE -- make depend depends on it. diff --git a/crypto/bn/asm/alpha.s b/crypto/bn/asm/alpha.s index d56f715ecd..1d17b1d619 100644 --- a/crypto/bn/asm/alpha.s +++ b/crypto/bn/asm/alpha.s @@ -3,16 +3,15 @@ # Thanks to tzeruch@ceddec.com for sending me the gcc output for # bn_div64. .file 1 "bn_mulw.c" - .version "01.01" .set noat gcc2_compiled.: __gnu_compiled_c: .text .align 3 - .globl bn_mul_add_word - .ent bn_mul_add_word -bn_mul_add_word: -bn_mul_add_word..ng: + .globl bn_mul_add_words + .ent bn_mul_add_words +bn_mul_add_words: +bn_mul_add_words..ng: .frame $30,0,$26,0 .prologue 0 subq $18,2,$25 # num=-2 @@ -74,12 +73,12 @@ $42: .align 4 $43: ret $31,($26),1 - .end bn_mul_add_word + .end bn_mul_add_words .align 3 - .globl bn_mul_word - .ent bn_mul_word -bn_mul_word: -bn_mul_word..ng: + .globl bn_mul_words + .ent bn_mul_words +bn_mul_words: +bn_mul_words..ng: .frame $30,0,$26,0 .prologue 0 subq $18,2,$25 # num=-2 @@ -125,7 +124,7 @@ $242: stq $1,0($16) $243: ret $31,($26),1 - .end bn_mul_word + .end bn_mul_words .align 3 .globl bn_sqr_words .ent bn_sqr_words @@ -173,6 +172,41 @@ $443: ret $31,($26),1 .end bn_sqr_words + .align 3 + .globl bn_add_words + .ent bn_add_words +bn_add_words: +bn_add_words..ng: + .frame $30,0,$26,0 + .prologue 0 + + bis $31,$31,$8 # carry = 0 + ble $19,$900 +$901: + ldq $0,0($17) # a[0] + ldq $1,0($18) # a[1] + + addq $0,$1,$3 # c=a+b; + addq $17,8,$17 # a++ + + cmpult $3,$1,$7 # did we overflow? + addq $18,8,$18 # b++ + + addq $8,$3,$3 # c+=carry + + cmpult $3,$8,$8 # did we overflow? + stq $3,($16) # r[0]=c + + addq $7,$8,$8 # add into overflow + subq $19,1,$19 # loop-- + + addq $16,8,$16 # r++ + bgt $19,$901 +$900: + bis $8,$8,$0 # return carry + ret $31,($26),1 + .end bn_add_words + # # What follows was taken directly from the C compiler with a few # hacks to redo the lables. diff --git a/crypto/bn/asm/bn-586.pl b/crypto/bn/asm/bn-586.pl new file mode 100644 index 0000000000..128f0f29d6 --- /dev/null +++ b/crypto/bn/asm/bn-586.pl @@ -0,0 +1,314 @@ +#!/usr/local/bin/perl +# + +#!/usr/local/bin/perl + +push(@INC,"perlasm","../../perlasm"); +require "x86asm.pl"; + +&asm_init($ARGV[0],"bn-586.pl"); + +&bn_mul_add_words("bn_mul_add_words"); +&bn_mul_words("bn_mul_words"); +&bn_sqr_words("bn_sqr_words"); +&bn_div64("bn_div64"); +&bn_add_words("bn_add_words"); + +&asm_finish(); + +sub bn_mul_add_words + { + local($name)=@_; + + &function_begin($name,""); + + &comment(""); + $Low="eax"; + $High="edx"; + $a="ebx"; + $w="ebp"; + $r="edi"; + $c="esi"; + + &xor($c,$c); # clear carry + &mov($r,&wparam(0)); # + + &mov("ecx",&wparam(2)); # + &mov($a,&wparam(1)); # + + &and("ecx",0xfffffff8); # num / 8 + &mov($w,&wparam(3)); # + + &push("ecx"); # Up the stack for a tmp variable + + &jz(&label("maw_finish")); + + &set_label("maw_loop",0); + + &mov(&swtmp(0),"ecx"); # + + for ($i=0; $i<32; $i+=4) + { + &comment("Round $i"); + + &mov("eax",&DWP($i,$a,"",0)); # *a + &mul($w); # *a * w + &add("eax",$c); # L(t)+= *r + &mov($c,&DWP($i,$r,"",0)); # L(t)+= *r + &adc("edx",0); # H(t)+=carry + &add("eax",$c); # L(t)+=c + &adc("edx",0); # H(t)+=carry + &mov(&DWP($i,$r,"",0),"eax"); # *r= L(t); + &mov($c,"edx"); # c= H(t); + } + + &comment(""); + &mov("ecx",&swtmp(0)); # + &add($a,32); + &add($r,32); + &sub("ecx",8); + &jnz(&label("maw_loop")); + + &set_label("maw_finish",0); + &mov("ecx",&wparam(2)); # get num + &and("ecx",7); + &jnz(&label("maw_finish2")); # helps branch prediction + &jmp(&label("maw_end")); + + &set_label("maw_finish2",1); + for ($i=0; $i<7; $i++) + { + &comment("Tail Round $i"); + &mov("eax",&DWP($i*4,$a,"",0));# *a + &mul($w); # *a * w + &add("eax",$c); # L(t)+=c + &mov($c,&DWP($i*4,$r,"",0)); # L(t)+= *r + &adc("edx",0); # H(t)+=carry + &add("eax",$c); + &adc("edx",0); # H(t)+=carry + &dec("ecx") if ($i != 7-1); + &mov(&DWP($i*4,$r,"",0),"eax"); # *r= L(t); + &mov($c,"edx"); # c= H(t); + &jz(&label("maw_end")) if ($i != 7-1); + } + &set_label("maw_end",0); + &mov("eax",$c); + + &pop("ecx"); # clear variable from + + &function_end($name); + } + +sub bn_mul_words + { + local($name)=@_; + + &function_begin($name,""); + + &comment(""); + $Low="eax"; + $High="edx"; + $a="ebx"; + $w="ecx"; + $r="edi"; + $c="esi"; + $num="ebp"; + + &xor($c,$c); # clear carry + &mov($r,&wparam(0)); # + &mov($a,&wparam(1)); # + &mov($num,&wparam(2)); # + &mov($w,&wparam(3)); # + + &and($num,0xfffffff8); # num / 8 + &jz(&label("mw_finish")); + + &set_label("mw_loop",0); + for ($i=0; $i<32; $i+=4) + { + &comment("Round $i"); + + &mov("eax",&DWP($i,$a,"",0)); # *a + &mul($w); # *a * w + &add("eax",$c); # L(t)+=c + # XXX + + &adc("edx",0); # H(t)+=carry + &mov(&DWP($i,$r,"",0),"eax"); # *r= L(t); + + &mov($c,"edx"); # c= H(t); + } + + &comment(""); + &add($a,32); + &add($r,32); + &sub($num,8); + &jz(&label("mw_finish")); + &jmp(&label("mw_loop")); + + &set_label("mw_finish",0); + &mov($num,&wparam(2)); # get num + &and($num,7); + &jnz(&label("mw_finish2")); + &jmp(&label("mw_end")); + + &set_label("mw_finish2",1); + for ($i=0; $i<7; $i++) + { + &comment("Tail Round $i"); + &mov("eax",&DWP($i*4,$a,"",0));# *a + &mul($w); # *a * w + &add("eax",$c); # L(t)+=c + # XXX + &adc("edx",0); # H(t)+=carry + &mov(&DWP($i*4,$r,"",0),"eax");# *r= L(t); + &mov($c,"edx"); # c= H(t); + &dec($num) if ($i != 7-1); + &jz(&label("mw_end")) if ($i != 7-1); + } + &set_label("mw_end",0); + &mov("eax",$c); + + &function_end($name); + } + +sub bn_sqr_words + { + local($name)=@_; + + &function_begin($name,""); + + &comment(""); + $r="esi"; + $a="edi"; + $num="ebx"; + + &mov($r,&wparam(0)); # + &mov($a,&wparam(1)); # + &mov($num,&wparam(2)); # + + &and($num,0xfffffff8); # num / 8 + &jz(&label("sw_finish")); + + &set_label("sw_loop",0); + for ($i=0; $i<32; $i+=4) + { + &comment("Round $i"); + &mov("eax",&DWP($i,$a,"",0)); # *a + # XXX + &mul("eax"); # *a * *a + &mov(&DWP($i*2,$r,"",0),"eax"); # + &mov(&DWP($i*2+4,$r,"",0),"edx");# + } + + &comment(""); + &add($a,32); + &add($r,64); + &sub($num,8); + &jnz(&label("sw_loop")); + + &set_label("sw_finish",0); + &mov($num,&wparam(2)); # get num + &and($num,7); + &jz(&label("sw_end")); + + for ($i=0; $i<7; $i++) + { + &comment("Tail Round $i"); + &mov("eax",&DWP($i*4,$a,"",0)); # *a + # XXX + &mul("eax"); # *a * *a + &mov(&DWP($i*8,$r,"",0),"eax"); # + &dec($num) if ($i != 7-1); + &mov(&DWP($i*8+4,$r,"",0),"edx"); + &jz(&label("sw_end")) if ($i != 7-1); + } + &set_label("sw_end",0); + + &function_end($name); + } + +sub bn_div64 + { + local($name)=@_; + + &function_begin($name,""); + &mov("edx",&wparam(0)); # + &mov("eax",&wparam(1)); # + &mov("ebx",&wparam(2)); # + &div("ebx"); + &function_end($name); + } + +sub bn_add_words + { + local($name)=@_; + + &function_begin($name,""); + + &comment(""); + $a="esi"; + $b="edi"; + $c="eax"; + $r="ebx"; + $tmp1="ecx"; + $tmp2="edx"; + $num="ebp"; + + &mov($r,&wparam(0)); # get r + &mov($a,&wparam(1)); # get a + &mov($b,&wparam(2)); # get b + &mov($num,&wparam(3)); # get num + &xor($c,$c); # clear carry + &and($num,0xfffffff8); # num / 8 + + &jz(&label("aw_finish")); + + &set_label("aw_loop",0); + for ($i=0; $i<8; $i++) + { + &comment("Round $i"); + + &mov($tmp1,&DWP($i*4,$a,"",0)); # *a + &mov($tmp2,&DWP($i*4,$b,"",0)); # *b + &add($tmp1,$c); + &mov($c,0); + &adc($c,$c); + &add($tmp1,$tmp2); + &adc($c,0); + &mov(&DWP($i*4,$r,"",0),$tmp1); # *r + } + + &comment(""); + &add($a,32); + &add($b,32); + &add($r,32); + &sub($num,8); + &jnz(&label("aw_loop")); + + &set_label("aw_finish",0); + &mov($num,&wparam(3)); # get num + &and($num,7); + &jz(&label("aw_end")); + + for ($i=0; $i<7; $i++) + { + &comment("Tail Round $i"); + &mov($tmp1,&DWP($i*4,$a,"",0)); # *a + &mov($tmp2,&DWP($i*4,$b,"",0));# *b + &add($tmp1,$c); + &mov($c,0); + &adc($c,$c); + &add($tmp1,$tmp2); + &adc($c,0); + &dec($num) if ($i != 6); + &mov(&DWP($i*4,$r,"",0),$tmp1); # *a + &jz(&label("aw_end")) if ($i != 6); + } + &set_label("aw_end",0); + + &mov("eax",$c); + + &function_end($name); + } + diff --git a/crypto/bn/asm/bn-win32.asm b/crypto/bn/asm/bn-win32.asm new file mode 100644 index 0000000000..017ea462b0 --- /dev/null +++ b/crypto/bn/asm/bn-win32.asm @@ -0,0 +1,689 @@ + ; Don't even think of reading this code + ; It was automatically generated by bn-586.pl + ; Which is a perl program used to generate the x86 assember for + ; any of elf, a.out, BSDI,Win32, or Solaris + ; eric <eay@cryptsoft.com> + ; + TITLE bn-586.asm + .386 +.model FLAT +_TEXT SEGMENT +PUBLIC _bn_mul_add_words + +_bn_mul_add_words PROC NEAR + push ebp + push ebx + push esi + push edi + ; + xor esi, esi + mov edi, DWORD PTR 20[esp] + mov ecx, DWORD PTR 28[esp] + mov ebx, DWORD PTR 24[esp] + and ecx, 4294967288 + mov ebp, DWORD PTR 32[esp] + push ecx + jz $L000maw_finish +L001maw_loop: + mov DWORD PTR [esp],ecx + ; Round 0 + mov eax, DWORD PTR [ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR [edi] + adc edx, 0 + add eax, esi + adc edx, 0 + mov DWORD PTR [edi],eax + mov esi, edx + ; Round 4 + mov eax, DWORD PTR 4[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 4[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + mov DWORD PTR 4[edi],eax + mov esi, edx + ; Round 8 + mov eax, DWORD PTR 8[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 8[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + mov DWORD PTR 8[edi],eax + mov esi, edx + ; Round 12 + mov eax, DWORD PTR 12[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 12[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + mov DWORD PTR 12[edi],eax + mov esi, edx + ; Round 16 + mov eax, DWORD PTR 16[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 16[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + mov DWORD PTR 16[edi],eax + mov esi, edx + ; Round 20 + mov eax, DWORD PTR 20[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 20[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + mov DWORD PTR 20[edi],eax + mov esi, edx + ; Round 24 + mov eax, DWORD PTR 24[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 24[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + mov DWORD PTR 24[edi],eax + mov esi, edx + ; Round 28 + mov eax, DWORD PTR 28[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 28[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + mov DWORD PTR 28[edi],eax + mov esi, edx + ; + mov ecx, DWORD PTR [esp] + add ebx, 32 + add edi, 32 + sub ecx, 8 + jnz L001maw_loop +$L000maw_finish: + mov ecx, DWORD PTR 32[esp] + and ecx, 7 + jnz $L002maw_finish2 + jmp $L003maw_end +$L002maw_finish2: + ; Tail Round 0 + mov eax, DWORD PTR [ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR [edi] + adc edx, 0 + add eax, esi + adc edx, 0 + dec ecx + mov DWORD PTR [edi],eax + mov esi, edx + jz $L003maw_end + ; Tail Round 1 + mov eax, DWORD PTR 4[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 4[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + dec ecx + mov DWORD PTR 4[edi],eax + mov esi, edx + jz $L003maw_end + ; Tail Round 2 + mov eax, DWORD PTR 8[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 8[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + dec ecx + mov DWORD PTR 8[edi],eax + mov esi, edx + jz $L003maw_end + ; Tail Round 3 + mov eax, DWORD PTR 12[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 12[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + dec ecx + mov DWORD PTR 12[edi],eax + mov esi, edx + jz $L003maw_end + ; Tail Round 4 + mov eax, DWORD PTR 16[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 16[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + dec ecx + mov DWORD PTR 16[edi],eax + mov esi, edx + jz $L003maw_end + ; Tail Round 5 + mov eax, DWORD PTR 20[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 20[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + dec ecx + mov DWORD PTR 20[edi],eax + mov esi, edx + jz $L003maw_end + ; Tail Round 6 + mov eax, DWORD PTR 24[ebx] + mul ebp + add eax, esi + mov esi, DWORD PTR 24[edi] + adc edx, 0 + add eax, esi + adc edx, 0 + mov DWORD PTR 24[edi],eax + mov esi, edx +$L003maw_end: + mov eax, esi + pop ecx + pop edi + pop esi + pop ebx + pop ebp + ret +_bn_mul_add_words ENDP +_TEXT ENDS +_TEXT SEGMENT +PUBLIC _bn_mul_words + +_bn_mul_words PROC NEAR + push ebp + push ebx + push esi + push edi + ; + xor esi, esi + mov edi, DWORD PTR 20[esp] + mov ebx, DWORD PTR 24[esp] + mov ebp, DWORD PTR 28[esp] + mov ecx, DWORD PTR 32[esp] + and ebp, 4294967288 + jz $L004mw_finish +L005mw_loop: + ; Round 0 + mov eax, DWORD PTR [ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR [edi],eax + mov esi, edx + ; Round 4 + mov eax, DWORD PTR 4[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 4[edi],eax + mov esi, edx + ; Round 8 + mov eax, DWORD PTR 8[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 8[edi],eax + mov esi, edx + ; Round 12 + mov eax, DWORD PTR 12[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 12[edi],eax + mov esi, edx + ; Round 16 + mov eax, DWORD PTR 16[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 16[edi],eax + mov esi, edx + ; Round 20 + mov eax, DWORD PTR 20[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 20[edi],eax + mov esi, edx + ; Round 24 + mov eax, DWORD PTR 24[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 24[edi],eax + mov esi, edx + ; Round 28 + mov eax, DWORD PTR 28[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 28[edi],eax + mov esi, edx + ; + add ebx, 32 + add edi, 32 + sub ebp, 8 + jz $L004mw_finish + jmp L005mw_loop +$L004mw_finish: + mov ebp, DWORD PTR 28[esp] + and ebp, 7 + jnz $L006mw_finish2 + jmp $L007mw_end +$L006mw_finish2: + ; Tail Round 0 + mov eax, DWORD PTR [ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR [edi],eax + mov esi, edx + dec ebp + jz $L007mw_end + ; Tail Round 1 + mov eax, DWORD PTR 4[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 4[edi],eax + mov esi, edx + dec ebp + jz $L007mw_end + ; Tail Round 2 + mov eax, DWORD PTR 8[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 8[edi],eax + mov esi, edx + dec ebp + jz $L007mw_end + ; Tail Round 3 + mov eax, DWORD PTR 12[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 12[edi],eax + mov esi, edx + dec ebp + jz $L007mw_end + ; Tail Round 4 + mov eax, DWORD PTR 16[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 16[edi],eax + mov esi, edx + dec ebp + jz $L007mw_end + ; Tail Round 5 + mov eax, DWORD PTR 20[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 20[edi],eax + mov esi, edx + dec ebp + jz $L007mw_end + ; Tail Round 6 + mov eax, DWORD PTR 24[ebx] + mul ecx + add eax, esi + adc edx, 0 + mov DWORD PTR 24[edi],eax + mov esi, edx +$L007mw_end: + mov eax, esi + pop edi + pop esi + pop ebx + pop ebp + ret +_bn_mul_words ENDP +_TEXT ENDS +_TEXT SEGMENT +PUBLIC _bn_sqr_words + +_bn_sqr_words PROC NEAR + push ebp + push ebx + push esi + push edi + ; + mov esi, DWORD PTR 20[esp] + mov edi, DWORD PTR 24[esp] + mov ebx, DWORD PTR 28[esp] + and ebx, 4294967288 + jz $L008sw_finish +L009sw_loop: + ; Round 0 + mov eax, DWORD PTR [edi] + mul eax + mov DWORD PTR [esi],eax + mov DWORD PTR 4[esi],edx + ; Round 4 + mov eax, DWORD PTR 4[edi] + mul eax + mov DWORD PTR 8[esi],eax + mov DWORD PTR 12[esi],edx + ; Round 8 + mov eax, DWORD PTR 8[edi] + mul eax + mov DWORD PTR 16[esi],eax + mov DWORD PTR 20[esi],edx + ; Round 12 + mov eax, DWORD PTR 12[edi] + mul eax + mov DWORD PTR 24[esi],eax + mov DWORD PTR 28[esi],edx + ; Round 16 + mov eax, DWORD PTR 16[edi] + mul eax + mov DWORD PTR 32[esi],eax + mov DWORD PTR 36[esi],edx + ; Round 20 + mov eax, DWORD PTR 20[edi] + mul eax + mov DWORD PTR 40[esi],eax + mov DWORD PTR 44[esi],edx + ; Round 24 + mov eax, DWORD PTR 24[edi] + mul eax + mov DWORD PTR 48[esi],eax + mov DWORD PTR 52[esi],edx + ; Round 28 + mov eax, DWORD PTR 28[edi] + mul eax + mov DWORD PTR 56[esi],eax + mov DWORD PTR 60[esi],edx + ; + add edi, 32 + add esi, 64 + sub ebx, 8 + jnz L009sw_loop +$L008sw_finish: + mov ebx, DWORD PTR 28[esp] + and ebx, 7 + jz $L010sw_end + ; Tail Round 0 + mov eax, DWORD PTR [edi] + mul eax + mov DWORD PTR [esi],eax + dec ebx + mov DWORD PTR 4[esi],edx + jz $L010sw_end + ; Tail Round 1 + mov eax, DWORD PTR 4[edi] + mul eax + mov DWORD PTR 8[esi],eax + dec ebx + mov DWORD PTR 12[esi],edx + jz $L010sw_end + ; Tail Round 2 + mov eax, DWORD PTR 8[edi] + mul eax + mov DWORD PTR 16[esi],eax + dec ebx + mov DWORD PTR 20[esi],edx + jz $L010sw_end + ; Tail Round 3 + mov eax, DWORD PTR 12[edi] + mul eax + mov DWORD PTR 24[esi],eax + dec ebx + mov DWORD PTR 28[esi],edx + jz $L010sw_end + ; Tail Round 4 + mov eax, DWORD PTR 16[edi] + mul eax + mov DWORD PTR 32[esi],eax + dec ebx + mov DWORD PTR 36[esi],edx + jz $L010sw_end + ; Tail Round 5 + mov eax, DWORD PTR 20[edi] + mul eax + mov DWORD PTR 40[esi],eax + dec ebx + mov DWORD PTR 44[esi],edx + jz $L010sw_end + ; Tail Round 6 + mov eax, DWORD PTR 24[edi] + mul eax + mov DWORD PTR 48[esi],eax + mov DWORD PTR 52[esi],edx +$L010sw_end: + pop edi + pop esi + pop ebx + pop ebp + ret +_bn_sqr_words ENDP +_TEXT ENDS +_TEXT SEGMENT +PUBLIC _bn_div64 + +_bn_div64 PROC NEAR + push ebp + push ebx + push esi + push edi + mov edx, DWORD PTR 20[esp] + mov eax, DWORD PTR 24[esp] + mov ebx, DWORD PTR 28[esp] + div ebx + pop edi + pop esi + pop ebx + pop ebp + ret +_bn_div64 ENDP +_TEXT ENDS +_TEXT SEGMENT +PUBLIC _bn_add_words + +_bn_add_words PROC NEAR + push ebp + push ebx + push esi + push edi + ; + mov ebx, DWORD PTR 20[esp] + mov esi, DWORD PTR 24[esp] + mov edi, DWORD PTR 28[esp] + mov ebp, DWORD PTR 32[esp] + xor eax, eax + and ebp, 4294967288 + jz $L011aw_finish +L012aw_loop: + ; Round 0 + mov ecx, DWORD PTR [esi] + mov edx, DWORD PTR [edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + mov DWORD PTR [ebx],ecx + ; Round 1 + mov ecx, DWORD PTR 4[esi] + mov edx, DWORD PTR 4[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + mov DWORD PTR 4[ebx],ecx + ; Round 2 + mov ecx, DWORD PTR 8[esi] + mov edx, DWORD PTR 8[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + mov DWORD PTR 8[ebx],ecx + ; Round 3 + mov ecx, DWORD PTR 12[esi] + mov edx, DWORD PTR 12[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + mov DWORD PTR 12[ebx],ecx + ; Round 4 + mov ecx, DWORD PTR 16[esi] + mov edx, DWORD PTR 16[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + mov DWORD PTR 16[ebx],ecx + ; Round 5 + mov ecx, DWORD PTR 20[esi] + mov edx, DWORD PTR 20[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + mov DWORD PTR 20[ebx],ecx + ; Round 6 + mov ecx, DWORD PTR 24[esi] + mov edx, DWORD PTR 24[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + mov DWORD PTR 24[ebx],ecx + ; Round 7 + mov ecx, DWORD PTR 28[esi] + mov edx, DWORD PTR 28[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + mov DWORD PTR 28[ebx],ecx + ; + add esi, 32 + add edi, 32 + add ebx, 32 + sub ebp, 8 + jnz L012aw_loop +$L011aw_finish: + mov ebp, DWORD PTR 32[esp] + and ebp, 7 + jz $L013aw_end + ; Tail Round 0 + mov ecx, DWORD PTR [esi] + mov edx, DWORD PTR [edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + dec ebp + mov DWORD PTR [ebx],ecx + jz $L013aw_end + ; Tail Round 1 + mov ecx, DWORD PTR 4[esi] + mov edx, DWORD PTR 4[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + dec ebp + mov DWORD PTR 4[ebx],ecx + jz $L013aw_end + ; Tail Round 2 + mov ecx, DWORD PTR 8[esi] + mov edx, DWORD PTR 8[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + dec ebp + mov DWORD PTR 8[ebx],ecx + jz $L013aw_end + ; Tail Round 3 + mov ecx, DWORD PTR 12[esi] + mov edx, DWORD PTR 12[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + dec ebp + mov DWORD PTR 12[ebx],ecx + jz $L013aw_end + ; Tail Round 4 + mov ecx, DWORD PTR 16[esi] + mov edx, DWORD PTR 16[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + dec ebp + mov DWORD PTR 16[ebx],ecx + jz $L013aw_end + ; Tail Round 5 + mov ecx, DWORD PTR 20[esi] + mov edx, DWORD PTR 20[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + dec ebp + mov DWORD PTR 20[ebx],ecx + jz $L013aw_end + ; Tail Round 6 + mov ecx, DWORD PTR 24[esi] + mov edx, DWORD PTR 24[edi] + add ecx, eax + mov eax, 0 + adc eax, eax + add ecx, edx + adc eax, 0 + mov DWORD PTR 24[ebx],ecx +$L013aw_end: + mov eax, eax + pop edi + pop esi + pop ebx + pop ebp + ret +_bn_add_words ENDP +_TEXT ENDS +END diff --git a/crypto/bn/asm/bn86unix.cpp b/crypto/bn/asm/bn86unix.cpp new file mode 100644 index 0000000000..64702201ea --- /dev/null +++ b/crypto/bn/asm/bn86unix.cpp @@ -0,0 +1,752 @@ +/* Run the C pre-processor over this file with one of the following defined + * ELF - elf object files, + * OUT - a.out object files, + * BSDI - BSDI style a.out object files + * SOL - Solaris style elf + */ + +#define TYPE(a,b) .type a,b +#define SIZE(a,b) .size a,b + +#if defined(OUT) || defined(BSDI) +#define bn_mul_add_words _bn_mul_add_words +#define bn_mul_words _bn_mul_words +#define bn_sqr_words _bn_sqr_words +#define bn_div64 _bn_div64 +#define bn_add_words _bn_add_words + +#endif + +#ifdef OUT +#define OK 1 +#define ALIGN 4 +#endif + +#ifdef BSDI +#define OK 1 +#define ALIGN 4 +#undef SIZE +#undef TYPE +#define SIZE(a,b) +#define TYPE(a,b) +#endif + +#if defined(ELF) || defined(SOL) +#define OK 1 +#define ALIGN 16 +#endif + +#ifndef OK +You need to define one of +ELF - elf systems - linux-elf, NetBSD and DG-UX +OUT - a.out systems - linux-a.out and FreeBSD +SOL - solaris systems, which are elf with strange comment lines +BSDI - a.out with a very primative version of as. +#endif + +/* Let the Assembler begin :-) */ + /* Don't even think of reading this code */ + /* It was automatically generated by bn-586.pl */ + /* Which is a perl program used to generate the x86 assember for */ + /* any of elf, a.out, BSDI,Win32, or Solaris */ + /* eric <eay@cryptsoft.com> */ + + .file "bn-586.s" + .version "01.01" +gcc2_compiled.: +.text + .align ALIGN +.globl bn_mul_add_words + TYPE(bn_mul_add_words,@function) +bn_mul_add_words: + pushl %ebp + pushl %ebx + pushl %esi + pushl %edi + + + xorl %esi, %esi + movl 20(%esp), %edi + movl 28(%esp), %ecx + movl 24(%esp), %ebx + andl $4294967288, %ecx + movl 32(%esp), %ebp + pushl %ecx + jz .L000maw_finish +.L001maw_loop: + movl %ecx, (%esp) + /* Round 0 */ + movl (%ebx), %eax + mull %ebp + addl %esi, %eax + movl (%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + movl %eax, (%edi) + movl %edx, %esi + /* Round 4 */ + movl 4(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 4(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + movl %eax, 4(%edi) + movl %edx, %esi + /* Round 8 */ + movl 8(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 8(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + movl %eax, 8(%edi) + movl %edx, %esi + /* Round 12 */ + movl 12(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 12(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + movl %eax, 12(%edi) + movl %edx, %esi + /* Round 16 */ + movl 16(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 16(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + movl %eax, 16(%edi) + movl %edx, %esi + /* Round 20 */ + movl 20(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 20(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + movl %eax, 20(%edi) + movl %edx, %esi + /* Round 24 */ + movl 24(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 24(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + movl %eax, 24(%edi) + movl %edx, %esi + /* Round 28 */ + movl 28(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 28(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + movl %eax, 28(%edi) + movl %edx, %esi + + movl (%esp), %ecx + addl $32, %ebx + addl $32, %edi + subl $8, %ecx + jnz .L001maw_loop +.L000maw_finish: + movl 32(%esp), %ecx + andl $7, %ecx + jnz .L002maw_finish2 + jmp .L003maw_end +.align ALIGN +.L002maw_finish2: + /* Tail Round 0 */ + movl (%ebx), %eax + mull %ebp + addl %esi, %eax + movl (%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + decl %ecx + movl %eax, (%edi) + movl %edx, %esi + jz .L003maw_end + /* Tail Round 1 */ + movl 4(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 4(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + decl %ecx + movl %eax, 4(%edi) + movl %edx, %esi + jz .L003maw_end + /* Tail Round 2 */ + movl 8(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 8(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + decl %ecx + movl %eax, 8(%edi) + movl %edx, %esi + jz .L003maw_end + /* Tail Round 3 */ + movl 12(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 12(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + decl %ecx + movl %eax, 12(%edi) + movl %edx, %esi + jz .L003maw_end + /* Tail Round 4 */ + movl 16(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 16(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + decl %ecx + movl %eax, 16(%edi) + movl %edx, %esi + jz .L003maw_end + /* Tail Round 5 */ + movl 20(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 20(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + decl %ecx + movl %eax, 20(%edi) + movl %edx, %esi + jz .L003maw_end + /* Tail Round 6 */ + movl 24(%ebx), %eax + mull %ebp + addl %esi, %eax + movl 24(%edi), %esi + adcl $0, %edx + addl %esi, %eax + adcl $0, %edx + movl %eax, 24(%edi) + movl %edx, %esi +.L003maw_end: + movl %esi, %eax + popl %ecx + popl %edi + popl %esi + popl %ebx + popl %ebp + ret +.bn_mul_add_words_end: + SIZE(bn_mul_add_words,.bn_mul_add_words_end-bn_mul_add_words) +.ident "bn_mul_add_words" +.text + .align ALIGN +.globl bn_mul_words + TYPE(bn_mul_words,@function) +bn_mul_words: + pushl %ebp + pushl %ebx + pushl %esi + pushl %edi + + + xorl %esi, %esi + movl 20(%esp), %edi + movl 24(%esp), %ebx + movl 28(%esp), %ebp + movl 32(%esp), %ecx + andl $4294967288, %ebp + jz .L004mw_finish +.L005mw_loop: + /* Round 0 */ + movl (%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, (%edi) + movl %edx, %esi + /* Round 4 */ + movl 4(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 4(%edi) + movl %edx, %esi + /* Round 8 */ + movl 8(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 8(%edi) + movl %edx, %esi + /* Round 12 */ + movl 12(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 12(%edi) + movl %edx, %esi + /* Round 16 */ + movl 16(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 16(%edi) + movl %edx, %esi + /* Round 20 */ + movl 20(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 20(%edi) + movl %edx, %esi + /* Round 24 */ + movl 24(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 24(%edi) + movl %edx, %esi + /* Round 28 */ + movl 28(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 28(%edi) + movl %edx, %esi + + addl $32, %ebx + addl $32, %edi + subl $8, %ebp + jz .L004mw_finish + jmp .L005mw_loop +.L004mw_finish: + movl 28(%esp), %ebp + andl $7, %ebp + jnz .L006mw_finish2 + jmp .L007mw_end +.align ALIGN +.L006mw_finish2: + /* Tail Round 0 */ + movl (%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, (%edi) + movl %edx, %esi + decl %ebp + jz .L007mw_end + /* Tail Round 1 */ + movl 4(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 4(%edi) + movl %edx, %esi + decl %ebp + jz .L007mw_end + /* Tail Round 2 */ + movl 8(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 8(%edi) + movl %edx, %esi + decl %ebp + jz .L007mw_end + /* Tail Round 3 */ + movl 12(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 12(%edi) + movl %edx, %esi + decl %ebp + jz .L007mw_end + /* Tail Round 4 */ + movl 16(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 16(%edi) + movl %edx, %esi + decl %ebp + jz .L007mw_end + /* Tail Round 5 */ + movl 20(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 20(%edi) + movl %edx, %esi + decl %ebp + jz .L007mw_end + /* Tail Round 6 */ + movl 24(%ebx), %eax + mull %ecx + addl %esi, %eax + adcl $0, %edx + movl %eax, 24(%edi) + movl %edx, %esi +.L007mw_end: + movl %esi, %eax + popl %edi + popl %esi + popl %ebx + popl %ebp + ret +.bn_mul_words_end: + SIZE(bn_mul_words,.bn_mul_words_end-bn_mul_words) +.ident "bn_mul_words" +.text + .align ALIGN +.globl bn_sqr_words + TYPE(bn_sqr_words,@function) +bn_sqr_words: + pushl %ebp + pushl %ebx + pushl %esi + pushl %edi + + + movl 20(%esp), %esi + movl 24(%esp), %edi + movl 28(%esp), %ebx + andl $4294967288, %ebx + jz .L008sw_finish +.L009sw_loop: + /* Round 0 */ + movl (%edi), %eax + mull %eax + movl %eax, (%esi) + movl %edx, 4(%esi) + /* Round 4 */ + movl 4(%edi), %eax + mull %eax + movl %eax, 8(%esi) + movl %edx, 12(%esi) + /* Round 8 */ + movl 8(%edi), %eax + mull %eax + movl %eax, 16(%esi) + movl %edx, 20(%esi) + /* Round 12 */ + movl 12(%edi), %eax + mull %eax + movl %eax, 24(%esi) + movl %edx, 28(%esi) + /* Round 16 */ + movl 16(%edi), %eax + mull %eax + movl %eax, 32(%esi) + movl %edx, 36(%esi) + /* Round 20 */ + movl 20(%edi), %eax + mull %eax + movl %eax, 40(%esi) + movl %edx, 44(%esi) + /* Round 24 */ + movl 24(%edi), %eax + mull %eax + movl %eax, 48(%esi) + movl %edx, 52(%esi) + /* Round 28 */ + movl 28(%edi), %eax + mull %eax + movl %eax, 56(%esi) + movl %edx, 60(%esi) + + addl $32, %edi + addl $64, %esi + subl $8, %ebx + jnz .L009sw_loop +.L008sw_finish: + movl 28(%esp), %ebx + andl $7, %ebx + jz .L010sw_end + /* Tail Round 0 */ + movl (%edi), %eax + mull %eax + movl %eax, (%esi) + decl %ebx + movl %edx, 4(%esi) + jz .L010sw_end + /* Tail Round 1 */ + movl 4(%edi), %eax + mull %eax + movl %eax, 8(%esi) + decl %ebx + movl %edx, 12(%esi) + jz .L010sw_end + /* Tail Round 2 */ + movl 8(%edi), %eax + mull %eax + movl %eax, 16(%esi) + decl %ebx + movl %edx, 20(%esi) + jz .L010sw_end + /* Tail Round 3 */ + movl 12(%edi), %eax + mull %eax + movl %eax, 24(%esi) + decl %ebx + movl %edx, 28(%esi) + jz .L010sw_end + /* Tail Round 4 */ + movl 16(%edi), %eax + mull %eax + movl %eax, 32(%esi) + decl %ebx + movl %edx, 36(%esi) + jz .L010sw_end + /* Tail Round 5 */ + movl 20(%edi), %eax + mull %eax + movl %eax, 40(%esi) + decl %ebx + movl %edx, 44(%esi) + jz .L010sw_end + /* Tail Round 6 */ + movl 24(%edi), %eax + mull %eax + movl %eax, 48(%esi) + movl %edx, 52(%esi) +.L010sw_end: + popl %edi + popl %esi + popl %ebx + popl %ebp + ret +.bn_sqr_words_end: + SIZE(bn_sqr_words,.bn_sqr_words_end-bn_sqr_words) +.ident "bn_sqr_words" +.text + .align ALIGN +.globl bn_div64 + TYPE(bn_div64,@function) +bn_div64: + pushl %ebp + pushl %ebx + pushl %esi + pushl %edi + + movl 20(%esp), %edx + movl 24(%esp), %eax + movl 28(%esp), %ebx + divl %ebx + popl %edi + popl %esi + popl %ebx + popl %ebp + ret +.bn_div64_end: + SIZE(bn_div64,.bn_div64_end-bn_div64) +.ident "bn_div64" +.text + .align ALIGN +.globl bn_add_words + TYPE(bn_add_words,@function) +bn_add_words: + pushl %ebp + pushl %ebx + pushl %esi + pushl %edi + + + movl 20(%esp), %ebx + movl 24(%esp), %esi + movl 28(%esp), %edi + movl 32(%esp), %ebp + xorl %eax, %eax + andl $4294967288, %ebp + jz .L011aw_finish +.L012aw_loop: + /* Round 0 */ + movl (%esi), %ecx + movl (%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + movl %ecx, (%ebx) + /* Round 1 */ + movl 4(%esi), %ecx + movl 4(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + movl %ecx, 4(%ebx) + /* Round 2 */ + movl 8(%esi), %ecx + movl 8(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + movl %ecx, 8(%ebx) + /* Round 3 */ + movl 12(%esi), %ecx + movl 12(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + movl %ecx, 12(%ebx) + /* Round 4 */ + movl 16(%esi), %ecx + movl 16(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + movl %ecx, 16(%ebx) + /* Round 5 */ + movl 20(%esi), %ecx + movl 20(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + movl %ecx, 20(%ebx) + /* Round 6 */ + movl 24(%esi), %ecx + movl 24(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + movl %ecx, 24(%ebx) + /* Round 7 */ + movl 28(%esi), %ecx + movl 28(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + movl %ecx, 28(%ebx) + + addl $32, %esi + addl $32, %edi + addl $32, %ebx + subl $8, %ebp + jnz .L012aw_loop +.L011aw_finish: + movl 32(%esp), %ebp + andl $7, %ebp + jz .L013aw_end + /* Tail Round 0 */ + movl (%esi), %ecx + movl (%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + decl %ebp + movl %ecx, (%ebx) + jz .L013aw_end + /* Tail Round 1 */ + movl 4(%esi), %ecx + movl 4(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + decl %ebp + movl %ecx, 4(%ebx) + jz .L013aw_end + /* Tail Round 2 */ + movl 8(%esi), %ecx + movl 8(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + decl %ebp + movl %ecx, 8(%ebx) + jz .L013aw_end + /* Tail Round 3 */ + movl 12(%esi), %ecx + movl 12(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + decl %ebp + movl %ecx, 12(%ebx) + jz .L013aw_end + /* Tail Round 4 */ + movl 16(%esi), %ecx + movl 16(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + decl %ebp + movl %ecx, 16(%ebx) + jz .L013aw_end + /* Tail Round 5 */ + movl 20(%esi), %ecx + movl 20(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + decl %ebp + movl %ecx, 20(%ebx) + jz .L013aw_end + /* Tail Round 6 */ + movl 24(%esi), %ecx + movl 24(%edi), %edx + addl %eax, %ecx + movl $0, %eax + adcl %eax, %eax + addl %edx, %ecx + adcl $0, %eax + movl %ecx, 24(%ebx) +.L013aw_end: + movl %eax, %eax + popl %edi + popl %esi + popl %ebx + popl %ebp + ret +.bn_add_words_end: + SIZE(bn_add_words,.bn_add_words_end-bn_add_words) +.ident "bn_add_words" diff --git a/crypto/bn/asm/pa-risc.s b/crypto/bn/asm/pa-risc.s index c49c433a83..775130a191 100644 --- a/crypto/bn/asm/pa-risc.s +++ b/crypto/bn/asm/pa-risc.s @@ -11,8 +11,8 @@ .SUBSPA $CODE$ .align 4 - .EXPORT bn_mul_add_word,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR -bn_mul_add_word + .EXPORT bn_mul_add_words,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR +bn_mul_add_words .PROC .CALLINFO FRAME=0,CALLS,SAVE_RP .ENTRY @@ -219,8 +219,8 @@ L$0003 .EXIT .PROCEND .align 4 - .EXPORT bn_mul_word,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR -bn_mul_word + .EXPORT bn_mul_words,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR +bn_mul_words .PROC .CALLINFO FRAME=0,CALLS,SAVE_RP .ENTRY diff --git a/crypto/bn/asm/pa-risc2.s b/crypto/bn/asm/pa-risc2.s index 5e07b7d2e8..c2725996a4 100644 --- a/crypto/bn/asm/pa-risc2.s +++ b/crypto/bn/asm/pa-risc2.s @@ -11,8 +11,8 @@ .SUBSPA $CODE$ .align 4 - .EXPORT bn_mul_add_word,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR -bn_mul_add_word + .EXPORT bn_mul_add_words,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR +bn_mul_add_words .PROC .CALLINFO FRAME=64,CALLS,SAVE_RP,ENTRY_GR=4 .ENTRY @@ -117,8 +117,8 @@ L$0011 .EXIT .PROCEND .align 4 - .EXPORT bn_mul_word,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR -bn_mul_word + .EXPORT bn_mul_words,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR +bn_mul_words .PROC .CALLINFO FRAME=64,CALLS,SAVE_RP,ENTRY_GR=3 .ENTRY diff --git a/crypto/bn/asm/r3000.s b/crypto/bn/asm/r3000.s index 5be2a0d0e6..e95269afa3 100644 --- a/crypto/bn/asm/r3000.s +++ b/crypto/bn/asm/r3000.s @@ -55,9 +55,9 @@ __gnu_compiled_c: .byte 0x0 .text .align 2 - .globl bn_mul_add_word - .ent bn_mul_add_word -bn_mul_add_word: + .globl bn_mul_add_words + .ent bn_mul_add_words +bn_mul_add_words: .frame $sp,0,$31 # vars= 0, regs= 0/0, args= 0, extra= 0 .mask 0x00000000,0 .fmask 0x00000000,0 @@ -206,11 +206,11 @@ $L3: .set macro .set reorder - .end bn_mul_add_word + .end bn_mul_add_words .align 2 - .globl bn_mul_word - .ent bn_mul_word -bn_mul_word: + .globl bn_mul_words + .ent bn_mul_words +bn_mul_words: .frame $sp,0,$31 # vars= 0, regs= 0/0, args= 0, extra= 0 .mask 0x00000000,0 .fmask 0x00000000,0 @@ -334,7 +334,7 @@ $L11: .set macro .set reorder - .end bn_mul_word + .end bn_mul_words .align 2 .globl bn_sqr_words .ent bn_sqr_words diff --git a/crypto/bn/asm/sparc.s b/crypto/bn/asm/sparc.s index 37c5fb194e..f9e533caa8 100644 --- a/crypto/bn/asm/sparc.s +++ b/crypto/bn/asm/sparc.s @@ -2,10 +2,10 @@ gcc2_compiled.: .section ".text" .align 4 - .global bn_mul_add_word - .type bn_mul_add_word,#function + .global bn_mul_add_words + .type bn_mul_add_words,#function .proc 016 -bn_mul_add_word: +bn_mul_add_words: !#PROLOGUE# 0 save %sp,-112,%sp !#PROLOGUE# 1 @@ -98,12 +98,12 @@ bn_mul_add_word: ret restore %g0,%i4,%o0 .LLfe1: - .size bn_mul_add_word,.LLfe1-bn_mul_add_word + .size bn_mul_add_words,.LLfe1-bn_mul_add_words .align 4 - .global bn_mul_word - .type bn_mul_word,#function + .global bn_mul_words + .type bn_mul_words,#function .proc 016 -bn_mul_word: +bn_mul_words: !#PROLOGUE# 0 save %sp,-112,%sp !#PROLOGUE# 1 @@ -176,7 +176,7 @@ bn_mul_word: ret restore .LLfe2: - .size bn_mul_word,.LLfe2-bn_mul_word + .size bn_mul_words,.LLfe2-bn_mul_words .align 4 .global bn_sqr_words .type bn_sqr_words,#function @@ -234,10 +234,113 @@ bn_sqr_words: nop .LLfe3: .size bn_sqr_words,.LLfe3-bn_sqr_words + .align 4 + .global bn_add_words + .type bn_add_words,#function + .proc 016 +bn_add_words: + !#PROLOGUE# 0 + save %sp,-112,%sp + !#PROLOGUE# 1 + mov %i0,%o2 + mov %i1,%o3 + mov %i2,%o4 + mov %i3,%i5 + mov 0,%o0 + mov 0,%o1 + add %o2,12,%o7 + add %o4,12,%g4 + b .LL42 + add %o3,12,%g1 +.LL45: + add %i5,-1,%i5 + mov %i4,%g3 + ld [%g4-8],%i4 + mov 0,%g2 + mov %i4,%i1 + mov 0,%i0 + addcc %g3,%i1,%g3 + addx %g2,%i0,%g2 + addcc %o1,%g3,%o1 + addx %o0,%g2,%o0 + st %o1,[%o7-8] + mov %o0,%i3 + mov 0,%i2 + mov %i2,%o0 + mov %i3,%o1 + cmp %i5,0 + ble .LL43 + add %i5,-1,%i5 + ld [%g1-4],%i4 + mov %i4,%g3 + ld [%g4-4],%i4 + mov 0,%g2 + mov %i4,%i1 + mov 0,%i0 + addcc %g3,%i1,%g3 + addx %g2,%i0,%g2 + addcc %o1,%g3,%o1 + addx %o0,%g2,%o0 + st %o1,[%o7-4] + mov %o0,%i3 + mov 0,%i2 + mov %i2,%o0 + mov %i3,%o1 + cmp %i5,0 + ble .LL43 + add %i5,-1,%i5 + ld [%g1],%i4 + mov %i4,%g3 + ld [%g4],%i4 + mov 0,%g2 + mov %i4,%i1 + mov 0,%i0 + addcc %g3,%i1,%g3 + addx %g2,%i0,%g2 + addcc %o1,%g3,%o1 + addx %o0,%g2,%o0 + st %o1,[%o7] + mov %o0,%i3 + mov 0,%i2 + mov %i2,%o0 + mov %i3,%o1 + cmp %i5,0 + ble .LL43 + add %g1,16,%g1 + add %o3,16,%o3 + add %g4,16,%g4 + add %o4,16,%o4 + add %o7,16,%o7 + add %o2,16,%o2 +.LL42: + ld [%o3],%i4 + add %i5,-1,%i5 + mov %i4,%g3 + ld [%o4],%i4 + mov 0,%g2 + mov %i4,%i1 + mov 0,%i0 + addcc %g3,%i1,%g3 + addx %g2,%i0,%g2 + addcc %o1,%g3,%o1 + addx %o0,%g2,%o0 + st %o1,[%o2] + mov %o0,%i3 + mov 0,%i2 + mov %i2,%o0 + mov %i3,%o1 + cmp %i5,0 + bg,a .LL45 + ld [%g1-8],%i4 +.LL43: + ret + restore %g0,%o1,%o0 +.LLfe4: + .size bn_add_words,.LLfe4-bn_add_words .section ".rodata" .align 8 .LLC0: - .asciz "Division would overflow\n" + .asciz "Division would overflow (%d)\n" .section ".text" .align 4 .global bn_div64 @@ -249,20 +352,20 @@ bn_div64: !#PROLOGUE# 1 mov 0,%l1 cmp %i2,0 - bne .LL42 + bne .LL51 mov 2,%l0 - b .LL59 + b .LL68 mov -1,%i0 -.LL42: +.LL51: call BN_num_bits_word,0 mov %i2,%o0 mov %o0,%o2 cmp %o2,32 - be .LL43 + be .LL52 mov 1,%o0 sll %o0,%o2,%o0 cmp %i0,%o0 - bleu .LL60 + bleu .LL69 mov 32,%o0 sethi %hi(__iob+32),%o0 or %o0,%lo(__iob+32),%o0 @@ -271,89 +374,89 @@ bn_div64: or %o1,%lo(.LLC0),%o1 call abort,0 nop -.LL43: +.LL52: mov 32,%o0 -.LL60: +.LL69: cmp %i0,%i2 - blu .LL44 + blu .LL53 sub %o0,%o2,%o2 sub %i0,%i2,%i0 -.LL44: +.LL53: cmp %o2,0 - be .LL45 - sethi %hi(-65536),%o7 - sll %i2,%o2,%i2 + be .LL54 sll %i0,%o2,%o1 + sll %i2,%o2,%i2 sub %o0,%o2,%o0 srl %i1,%o0,%o0 or %o1,%o0,%i0 sll %i1,%o2,%i1 -.LL45: +.LL54: srl %i2,16,%g2 sethi %hi(65535),%o0 or %o0,%lo(65535),%o1 and %i2,%o1,%g3 mov %o0,%g4 + sethi %hi(-65536),%o7 mov %o1,%g1 -.LL46: +.LL55: srl %i0,16,%o0 cmp %o0,%g2 - be .LL50 + be .LL59 or %g4,%lo(65535),%o3 wr %g0,%g0,%y nop nop nop udiv %i0,%g2,%o3 -.LL50: +.LL59: and %i1,%o7,%o0 srl %o0,16,%o5 smul %o3,%g3,%o4 smul %o3,%g2,%o2 -.LL51: +.LL60: sub %i0,%o2,%o1 andcc %o1,%o7,%g0 - bne .LL52 + bne .LL61 sll %o1,16,%o0 add %o0,%o5,%o0 cmp %o4,%o0 - bleu .LL52 + bleu .LL61 sub %o4,%g3,%o4 sub %o2,%g2,%o2 - b .LL51 + b .LL60 add %o3,-1,%o3 -.LL52: +.LL61: smul %o3,%g2,%o2 smul %o3,%g3,%o0 srl %o0,16,%o1 sll %o0,16,%o0 and %o0,%o7,%o0 cmp %i1,%o0 - bgeu .LL56 + bgeu .LL65 add %o2,%o1,%o2 add %o2,1,%o2 -.LL56: +.LL65: cmp %i0,%o2 - bgeu .LL57 + bgeu .LL66 sub %i1,%o0,%i1 add %i0,%i2,%i0 add %o3,-1,%o3 -.LL57: +.LL66: addcc %l0,-1,%l0 - be .LL47 + be .LL56 sub %i0,%o2,%i0 sll %o3,16,%l1 sll %i0,16,%o0 srl %i1,16,%o1 or %o0,%o1,%i0 and %i1,%g1,%o0 - b .LL46 + b .LL55 sll %o0,16,%i1 -.LL47: +.LL56: or %l1,%o3,%i0 -.LL59: +.LL68: ret restore -.LLfe4: - .size bn_div64,.LLfe4-bn_div64 - .ident "GCC: (GNU) 2.7.0" +.LLfe5: + .size bn_div64,.LLfe5-bn_div64 + .ident "GCC: (GNU) 2.7.2.3" diff --git a/crypto/bn/asm/x86w16.asm b/crypto/bn/asm/x86w16.asm index 66874913e9..74a933a8cd 100644 --- a/crypto/bn/asm/x86w16.asm +++ b/crypto/bn/asm/x86w16.asm @@ -14,8 +14,8 @@ DGROUP GROUP CONST, _BSS, _DATA ASSUME DS: DGROUP, SS: DGROUP F_TEXT SEGMENT ASSUME CS: F_TEXT - PUBLIC _bn_mul_add_word -_bn_mul_add_word PROC FAR + PUBLIC _bn_mul_add_words +_bn_mul_add_words PROC FAR ; Line 58 push bp push bx @@ -133,9 +133,9 @@ $L547: ret nop -_bn_mul_add_word ENDP - PUBLIC _bn_mul_word -_bn_mul_word PROC FAR +_bn_mul_add_words ENDP + PUBLIC _bn_mul_words +_bn_mul_words PROC FAR ; Line 76 push bp push bx @@ -202,7 +202,7 @@ $L764: pop bp ret nop -_bn_mul_word ENDP +_bn_mul_words ENDP PUBLIC _bn_sqr_words _bn_sqr_words PROC FAR ; Line 92 diff --git a/crypto/bn/asm/x86w32.asm b/crypto/bn/asm/x86w32.asm index 0e4452dfa9..fc6f917714 100644 --- a/crypto/bn/asm/x86w32.asm +++ b/crypto/bn/asm/x86w32.asm @@ -14,8 +14,8 @@ DGROUP GROUP CONST, _BSS, _DATA ASSUME DS: DGROUP, SS: DGROUP F_TEXT SEGMENT ASSUME CS: F_TEXT - PUBLIC _bn_mul_add_word -_bn_mul_add_word PROC FAR + PUBLIC _bn_mul_add_words +_bn_mul_add_words PROC FAR ; Line 58 push bp push bx @@ -133,10 +133,10 @@ $L547: pop bp ret nop +_bn_mul_add_words ENDP -_bn_mul_add_word ENDP - PUBLIC _bn_mul_word -_bn_mul_word PROC FAR + PUBLIC _bn_mul_words +_bn_mul_words PROC FAR ; Line 76 push bp push bx @@ -206,7 +206,7 @@ $L764: pop bp ret nop -_bn_mul_word ENDP +_bn_mul_words ENDP PUBLIC _bn_sqr_words _bn_sqr_words PROC FAR ; Line 92 @@ -285,8 +285,8 @@ $L645: pop bx pop bp ret - _bn_sqr_words ENDP + PUBLIC _bn_div64 _bn_div64 PROC FAR push bp @@ -299,5 +299,64 @@ _bn_div64 PROC FAR pop bp ret _bn_div64 ENDP + + PUBLIC _bn_add_words +_bn_add_words PROC FAR +; Line 58 + push bp + push bx + push esi + push di + push ds + push es + mov bp,sp +; w = 28 +; num = 26 +; ap = 22 +; rp = 18 + xor esi,esi ;c=0; + mov si,WORD PTR [bp+22] ; load a + mov es,WORD PTR [bp+24] ; load a + mov di,WORD PTR [bp+26] ; load b + mov ds,WORD PTR [bp+28] ; load b + + mov dx,WORD PTR [bp+30] ; load num + dec dx + js $L547 + xor ecx,ecx + +$L5477: + xor ebx,ebx + mov eax,DWORD PTR es:[si] ; *a + add eax,ecx + adc ebx,0 + add si,4 ; a++ + add eax,DWORD PTR ds:[di] ; + *b + mov ecx,ebx + adc ecx,0 + add di,4 + mov bx,WORD PTR [bp+18] + mov ds,WORD PTR [bp+20] + mov DWORD PTR ds:[bx],eax + add bx,4 + mov ds,WORD PTR [bp+28] + mov WORD PTR [bp+18],bx + dec dx + js $L547 ; Note that we are now testing for -1 + jmp $L5477 + ; +$L547: + mov eax,ecx + mov edx,ecx + shr edx,16 + pop es + pop ds + pop di + pop esi + pop bx + pop bp + ret + nop +_bn_add_words ENDP F_TEXT ENDS END diff --git a/crypto/bn/bn.err b/crypto/bn/bn.err index 5fe4b6dbf6..7ccc247c41 100644 --- a/crypto/bn/bn.err +++ b/crypto/bn/bn.err @@ -1,20 +1,27 @@ /* Error codes for the BN functions. */ /* Function codes. */ -#define BN_F_BN_BL_CTX_INIT 100 -#define BN_F_BN_BL_CTX_NEW 101 -#define BN_F_BN_BN2ASCII 102 -#define BN_F_BN_CTX_NEW 103 -#define BN_F_BN_DIV 104 -#define BN_F_BN_EXPAND2 105 -#define BN_F_BN_MOD_EXP_MONT 106 -#define BN_F_BN_MOD_INVERSE 107 -#define BN_F_BN_MOD_MUL_RECIPROCAL 108 -#define BN_F_BN_NEW 109 -#define BN_F_BN_RAND 110 +#define BN_F_BN_BLINDING_CONVERT 100 +#define BN_F_BN_BLINDING_INVERT 101 +#define BN_F_BN_BLINDING_NEW 102 +#define BN_F_BN_BLINDING_UPDATE 103 +#define BN_F_BN_BN2DEC 104 +#define BN_F_BN_BN2HEX 105 +#define BN_F_BN_CTX_NEW 106 +#define BN_F_BN_DIV 107 +#define BN_F_BN_EXPAND2 108 +#define BN_F_BN_MOD_EXP_MONT 109 +#define BN_F_BN_MOD_INVERSE 110 +#define BN_F_BN_MOD_MUL_RECIPROCAL 111 +#define BN_F_BN_MPI2BN 112 +#define BN_F_BN_NEW 113 +#define BN_F_BN_RAND 114 /* Reason codes. */ #define BN_R_BAD_RECIPROCAL 100 #define BN_R_CALLED_WITH_EVEN_MODULUS 101 #define BN_R_DIV_BY_ZERO 102 -#define BN_R_NO_INVERSE 103 +#define BN_R_ENCODING_ERROR 103 +#define BN_R_INVALID_LENGTH 104 +#define BN_R_NOT_INITALISED 105 +#define BN_R_NO_INVERSE 106 diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h index 9326f4df50..66dde285d6 100644 --- a/crypto/bn/bn.h +++ b/crypto/bn/bn.h @@ -121,6 +121,10 @@ extern "C" { #define BN_MASK2h (0xffffffff00000000L) #define BN_MASK2h1 (0xffffffff80000000L) #define BN_TBIT (0x8000000000000000L) +#define BN_DEC_CONV (10000000000000000000L) +#define BN_DEC_FMT1 "%lu" +#define BN_DEC_FMT2 "%019lu" +#define BN_DEC_NUM 19 #endif #ifdef SIXTY_FOUR_BIT @@ -137,6 +141,10 @@ extern "C" { #define BN_MASK2h (0xffffffff00000000LL) #define BN_MASK2h1 (0xffffffff80000000LL) #define BN_TBIT (0x8000000000000000LL) +#define BN_DEC_CONV (10000000000000000000L) +#define BN_DEC_FMT1 "%lu" +#define BN_DEC_FMT2 "%019lu" +#define BN_DEC_NUM 19 #endif #ifdef THIRTY_TWO_BIT @@ -156,6 +164,10 @@ extern "C" { #define BN_MASK2h1 (0xffff8000L) #define BN_MASK2h (0xffff0000L) #define BN_TBIT (0x80000000L) +#define BN_DEC_CONV (1000000000L) +#define BN_DEC_FMT1 "%lu" +#define BN_DEC_FMT2 "%09lu" +#define BN_DEC_NUM 9 #endif #ifdef SIXTEEN_BIT @@ -174,6 +186,10 @@ extern "C" { #define BN_MASK2h1 (0xff80) #define BN_MASK2h (0xff00) #define BN_TBIT (0x8000) +#define BN_DEC_CONV (100000) +#define BN_DEC_FMT1 "%u" +#define BN_DEC_FMT2 "%05u" +#define BN_DEC_NUM 5 #endif #ifdef EIGHT_BIT @@ -192,6 +208,10 @@ extern "C" { #define BN_MASK2h1 (0xf8) #define BN_MASK2h (0xf0) #define BN_TBIT (0x80) +#define BN_DEC_CONV (100) +#define BN_DEC_FMT1 "%u" +#define BN_DEC_FMT2 "%02u" +#define BN_DEC_NUM 2 #endif #define BN_DEFAULT_BITS 1280 @@ -217,6 +237,14 @@ typedef struct bignum_ctx BIGNUM *bn[BN_CTX_NUM+1]; } BN_CTX; +typedef struct bn_blinding_st + { + int init; + BIGNUM *A; + BIGNUM *Ai; + BIGNUM *mod; /* just a reference */ + } BN_BLINDING; + /* Used for montgomery multiplication */ typedef struct bn_mont_ctx_st { @@ -241,6 +269,9 @@ typedef struct bn_mont_ctx_st #define BN_one(a) (BN_set_word((a),1)) #define BN_zero(a) (BN_set_word((a),0)) +#define BN_ascii2bn(a) BN_hex2bn(a) +#define BN_bn2ascii(a) BN_bn2hex(a) + #define bn_fix_top(a) \ { \ BN_ULONG *fix_top_l; \ @@ -248,7 +279,9 @@ typedef struct bn_mont_ctx_st if (*(fix_top_l--)) break; \ } -#define bn_expand(n,b) ((((b)/BN_BITS2) <= (n)->max)?(n):bn_expand2((n),(b))) +#define bn_expand(n,b) ((((b)/BN_BITS2) <= (n)->max)?\ + (n):bn_expand2((n),(b)/BN_BITS2)) +#define bn_wexpand(n,b) (((b) <= (n)->max)?(n):bn_expand2((n),(b))) #ifndef NOPROTO @@ -264,6 +297,8 @@ void BN_clear_free(BIGNUM *a); BIGNUM *BN_copy(BIGNUM *a, BIGNUM *b); BIGNUM *BN_bin2bn(unsigned char *s,int len,BIGNUM *ret); int BN_bn2bin(BIGNUM *a, unsigned char *to); +BIGNUM *BN_mpi2bn(unsigned char *s,int len,BIGNUM *ret); +int BN_bn2mpi(BIGNUM *a, unsigned char *to); int BN_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b); void bn_qsub(BIGNUM *r, BIGNUM *a, BIGNUM *b); void bn_qadd(BIGNUM *r, BIGNUM *a, BIGNUM *b); @@ -274,7 +309,9 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b); int BN_sqr(BIGNUM *r, BIGNUM *a,BN_CTX *ctx); BN_ULONG BN_mod_word(BIGNUM *a, unsigned long w); BN_ULONG BN_div_word(BIGNUM *a, unsigned long w); +int BN_mul_word(BIGNUM *a, unsigned long w); int BN_add_word(BIGNUM *a, unsigned long w); +int BN_sub_word(BIGNUM *a, unsigned long w); int BN_set_word(BIGNUM *a, unsigned long w); unsigned long BN_get_word(BIGNUM *a); int BN_cmp(BIGNUM *a, BIGNUM *b); @@ -282,8 +319,10 @@ void BN_free(BIGNUM *a); int BN_is_bit_set(BIGNUM *a, int n); int BN_lshift(BIGNUM *r, BIGNUM *a, int n); int BN_lshift1(BIGNUM *r, BIGNUM *a); +int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p,BN_CTX *ctx); int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx); -int BN_mod_exp_mont(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx); +int BN_mod_exp_mont(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx, + BN_MONT_CTX *m_ctx); int BN_mod_exp_recp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx); int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx); @@ -309,20 +348,23 @@ BIGNUM *BN_dup(BIGNUM *a); int BN_ucmp(BIGNUM *a, BIGNUM *b); int BN_set_bit(BIGNUM *a, int n); int BN_clear_bit(BIGNUM *a, int n); -char * BN_bn2ascii(BIGNUM *a); -int BN_ascii2bn(BIGNUM **a,char *str); +char * BN_bn2hex(BIGNUM *a); +char * BN_bn2dec(BIGNUM *a); +int BN_hex2bn(BIGNUM **a,char *str); +int BN_dec2bn(BIGNUM **a,char *str); int BN_gcd(BIGNUM *r,BIGNUM *in_a,BIGNUM *in_b,BN_CTX *ctx); BIGNUM *BN_mod_inverse(BIGNUM *a, BIGNUM *n,BN_CTX *ctx); BIGNUM *BN_generate_prime(int bits,int strong,BIGNUM *add, - BIGNUM *rem,void (*callback)(int,int)); -int BN_is_prime(BIGNUM *p,int nchecks,void (*callback)(int,int), - BN_CTX *ctx); + BIGNUM *rem,void (*callback)(int,int,char *),char *cb_arg); +int BN_is_prime(BIGNUM *p,int nchecks,void (*callback)(int,int,char *), + BN_CTX *ctx,char *cb_arg); void ERR_load_BN_strings(void ); -BN_ULONG bn_mul_add_word(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w); -BN_ULONG bn_mul_word(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); +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_div64(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_MONT_CTX *BN_MONT_CTX_new(void ); int BN_mod_mul_montgomery(BIGNUM *r,BIGNUM *a,BIGNUM *b,BN_MONT_CTX *mont, @@ -331,6 +373,12 @@ int BN_from_montgomery(BIGNUM *r,BIGNUM *a,BN_MONT_CTX *mont,BN_CTX *ctx); void BN_MONT_CTX_free(BN_MONT_CTX *mont); int BN_MONT_CTX_set(BN_MONT_CTX *mont,BIGNUM *modulus,BN_CTX *ctx); +BN_BLINDING *BN_BLINDING_new(BIGNUM *A,BIGNUM *Ai,BIGNUM *mod); +void BN_BLINDING_free(BN_BLINDING *b); +int BN_BLINDING_update(BN_BLINDING *b,BN_CTX *ctx); +int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *r, BN_CTX *ctx); +int BN_BLINDING_invert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx); + #else BIGNUM *BN_value_one(); @@ -345,6 +393,8 @@ void BN_clear_free(); BIGNUM *BN_copy(); BIGNUM *BN_bin2bn(); int BN_bn2bin(); +BIGNUM *BN_mpi2bn(); +int BN_bn2mpi(); int BN_sub(); void bn_qsub(); void bn_qadd(); @@ -356,6 +406,8 @@ int BN_sqr(); BN_ULONG BN_mod_word(); BN_ULONG BN_div_word(); int BN_add_word(); +int BN_sub_word(); +int BN_mul_word(); int BN_set_word(); unsigned long BN_get_word(); int BN_cmp(); @@ -363,6 +415,7 @@ void BN_free(); int BN_is_bit_set(); int BN_lshift(); int BN_lshift1(); +int BN_exp(); int BN_mod_exp(); int BN_mod_exp_mont(); int BN_mod_exp_recp(); @@ -383,18 +436,21 @@ BIGNUM *BN_dup(); int BN_ucmp(); int BN_set_bit(); int BN_clear_bit(); -char * BN_bn2ascii(); -int BN_ascii2bn(); +char * BN_bn2hex(); +char * BN_bn2dec(); +int BN_hex2bn(); +int BN_dec2bn(); int BN_gcd(); BIGNUM *BN_mod_inverse(); BIGNUM *BN_generate_prime(); int BN_is_prime(); void ERR_load_BN_strings(); -BN_ULONG bn_mul_add_word(); -BN_ULONG bn_mul_word(); +BN_ULONG bn_mul_add_words(); +BN_ULONG bn_mul_words(); void bn_sqr_words(); BN_ULONG bn_div64(); +BN_ULONG bn_add_words(); int BN_mod_mul_montgomery(); int BN_from_montgomery(); @@ -402,29 +458,42 @@ BN_MONT_CTX *BN_MONT_CTX_new(); void BN_MONT_CTX_free(); int BN_MONT_CTX_set(); +BN_BLINDING *BN_BLINDING_new(); +void BN_BLINDING_free(); +int BN_BLINDING_update(); +int BN_BLINDING_convert(); +int BN_BLINDING_invert(); + #endif /* BEGIN ERROR CODES */ /* Error codes for the BN functions. */ /* Function codes. */ -#define BN_F_BN_BL_CTX_INIT 100 -#define BN_F_BN_BL_CTX_NEW 101 -#define BN_F_BN_BN2ASCII 102 -#define BN_F_BN_CTX_NEW 103 -#define BN_F_BN_DIV 104 -#define BN_F_BN_EXPAND2 105 -#define BN_F_BN_MOD_EXP_MONT 106 -#define BN_F_BN_MOD_INVERSE 107 -#define BN_F_BN_MOD_MUL_RECIPROCAL 108 -#define BN_F_BN_NEW 109 -#define BN_F_BN_RAND 110 +#define BN_F_BN_BLINDING_CONVERT 100 +#define BN_F_BN_BLINDING_INVERT 101 +#define BN_F_BN_BLINDING_NEW 102 +#define BN_F_BN_BLINDING_UPDATE 103 +#define BN_F_BN_BN2DEC 104 +#define BN_F_BN_BN2HEX 105 +#define BN_F_BN_CTX_NEW 106 +#define BN_F_BN_DIV 107 +#define BN_F_BN_EXPAND2 108 +#define BN_F_BN_MOD_EXP_MONT 109 +#define BN_F_BN_MOD_INVERSE 110 +#define BN_F_BN_MOD_MUL_RECIPROCAL 111 +#define BN_F_BN_MPI2BN 112 +#define BN_F_BN_NEW 113 +#define BN_F_BN_RAND 114 /* Reason codes. */ #define BN_R_BAD_RECIPROCAL 100 #define BN_R_CALLED_WITH_EVEN_MODULUS 101 #define BN_R_DIV_BY_ZERO 102 -#define BN_R_NO_INVERSE 103 +#define BN_R_ENCODING_ERROR 103 +#define BN_R_INVALID_LENGTH 104 +#define BN_R_NOT_INITALISED 105 +#define BN_R_NO_INVERSE 106 #ifdef __cplusplus } diff --git a/crypto/bn/bn.org b/crypto/bn/bn.org index 9326f4df50..66dde285d6 100644 --- a/crypto/bn/bn.org +++ b/crypto/bn/bn.org @@ -121,6 +121,10 @@ extern "C" { #define BN_MASK2h (0xffffffff00000000L) #define BN_MASK2h1 (0xffffffff80000000L) #define BN_TBIT (0x8000000000000000L) +#define BN_DEC_CONV (10000000000000000000L) +#define BN_DEC_FMT1 "%lu" +#define BN_DEC_FMT2 "%019lu" +#define BN_DEC_NUM 19 #endif #ifdef SIXTY_FOUR_BIT @@ -137,6 +141,10 @@ extern "C" { #define BN_MASK2h (0xffffffff00000000LL) #define BN_MASK2h1 (0xffffffff80000000LL) #define BN_TBIT (0x8000000000000000LL) +#define BN_DEC_CONV (10000000000000000000L) +#define BN_DEC_FMT1 "%lu" +#define BN_DEC_FMT2 "%019lu" +#define BN_DEC_NUM 19 #endif #ifdef THIRTY_TWO_BIT @@ -156,6 +164,10 @@ extern "C" { #define BN_MASK2h1 (0xffff8000L) #define BN_MASK2h (0xffff0000L) #define BN_TBIT (0x80000000L) +#define BN_DEC_CONV (1000000000L) +#define BN_DEC_FMT1 "%lu" +#define BN_DEC_FMT2 "%09lu" +#define BN_DEC_NUM 9 #endif #ifdef SIXTEEN_BIT @@ -174,6 +186,10 @@ extern "C" { #define BN_MASK2h1 (0xff80) #define BN_MASK2h (0xff00) #define BN_TBIT (0x8000) +#define BN_DEC_CONV (100000) +#define BN_DEC_FMT1 "%u" +#define BN_DEC_FMT2 "%05u" +#define BN_DEC_NUM 5 #endif #ifdef EIGHT_BIT @@ -192,6 +208,10 @@ extern "C" { #define BN_MASK2h1 (0xf8) #define BN_MASK2h (0xf0) #define BN_TBIT (0x80) +#define BN_DEC_CONV (100) +#define BN_DEC_FMT1 "%u" +#define BN_DEC_FMT2 "%02u" +#define BN_DEC_NUM 2 #endif #define BN_DEFAULT_BITS 1280 @@ -217,6 +237,14 @@ typedef struct bignum_ctx BIGNUM *bn[BN_CTX_NUM+1]; } BN_CTX; +typedef struct bn_blinding_st + { + int init; + BIGNUM *A; + BIGNUM *Ai; + BIGNUM *mod; /* just a reference */ + } BN_BLINDING; + /* Used for montgomery multiplication */ typedef struct bn_mont_ctx_st { @@ -241,6 +269,9 @@ typedef struct bn_mont_ctx_st #define BN_one(a) (BN_set_word((a),1)) #define BN_zero(a) (BN_set_word((a),0)) +#define BN_ascii2bn(a) BN_hex2bn(a) +#define BN_bn2ascii(a) BN_bn2hex(a) + #define bn_fix_top(a) \ { \ BN_ULONG *fix_top_l; \ @@ -248,7 +279,9 @@ typedef struct bn_mont_ctx_st if (*(fix_top_l--)) break; \ } -#define bn_expand(n,b) ((((b)/BN_BITS2) <= (n)->max)?(n):bn_expand2((n),(b))) +#define bn_expand(n,b) ((((b)/BN_BITS2) <= (n)->max)?\ + (n):bn_expand2((n),(b)/BN_BITS2)) +#define bn_wexpand(n,b) (((b) <= (n)->max)?(n):bn_expand2((n),(b))) #ifndef NOPROTO @@ -264,6 +297,8 @@ void BN_clear_free(BIGNUM *a); BIGNUM *BN_copy(BIGNUM *a, BIGNUM *b); BIGNUM *BN_bin2bn(unsigned char *s,int len,BIGNUM *ret); int BN_bn2bin(BIGNUM *a, unsigned char *to); +BIGNUM *BN_mpi2bn(unsigned char *s,int len,BIGNUM *ret); +int BN_bn2mpi(BIGNUM *a, unsigned char *to); int BN_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b); void bn_qsub(BIGNUM *r, BIGNUM *a, BIGNUM *b); void bn_qadd(BIGNUM *r, BIGNUM *a, BIGNUM *b); @@ -274,7 +309,9 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b); int BN_sqr(BIGNUM *r, BIGNUM *a,BN_CTX *ctx); BN_ULONG BN_mod_word(BIGNUM *a, unsigned long w); BN_ULONG BN_div_word(BIGNUM *a, unsigned long w); +int BN_mul_word(BIGNUM *a, unsigned long w); int BN_add_word(BIGNUM *a, unsigned long w); +int BN_sub_word(BIGNUM *a, unsigned long w); int BN_set_word(BIGNUM *a, unsigned long w); unsigned long BN_get_word(BIGNUM *a); int BN_cmp(BIGNUM *a, BIGNUM *b); @@ -282,8 +319,10 @@ void BN_free(BIGNUM *a); int BN_is_bit_set(BIGNUM *a, int n); int BN_lshift(BIGNUM *r, BIGNUM *a, int n); int BN_lshift1(BIGNUM *r, BIGNUM *a); +int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p,BN_CTX *ctx); int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx); -int BN_mod_exp_mont(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx); +int BN_mod_exp_mont(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx, + BN_MONT_CTX *m_ctx); int BN_mod_exp_recp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx); int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx); @@ -309,20 +348,23 @@ BIGNUM *BN_dup(BIGNUM *a); int BN_ucmp(BIGNUM *a, BIGNUM *b); int BN_set_bit(BIGNUM *a, int n); int BN_clear_bit(BIGNUM *a, int n); -char * BN_bn2ascii(BIGNUM *a); -int BN_ascii2bn(BIGNUM **a,char *str); +char * BN_bn2hex(BIGNUM *a); +char * BN_bn2dec(BIGNUM *a); +int BN_hex2bn(BIGNUM **a,char *str); +int BN_dec2bn(BIGNUM **a,char *str); int BN_gcd(BIGNUM *r,BIGNUM *in_a,BIGNUM *in_b,BN_CTX *ctx); BIGNUM *BN_mod_inverse(BIGNUM *a, BIGNUM *n,BN_CTX *ctx); BIGNUM *BN_generate_prime(int bits,int strong,BIGNUM *add, - BIGNUM *rem,void (*callback)(int,int)); -int BN_is_prime(BIGNUM *p,int nchecks,void (*callback)(int,int), - BN_CTX *ctx); + BIGNUM *rem,void (*callback)(int,int,char *),char *cb_arg); +int BN_is_prime(BIGNUM *p,int nchecks,void (*callback)(int,int,char *), + BN_CTX *ctx,char *cb_arg); void ERR_load_BN_strings(void ); -BN_ULONG bn_mul_add_word(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w); -BN_ULONG bn_mul_word(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); +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_div64(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_MONT_CTX *BN_MONT_CTX_new(void ); int BN_mod_mul_montgomery(BIGNUM *r,BIGNUM *a,BIGNUM *b,BN_MONT_CTX *mont, @@ -331,6 +373,12 @@ int BN_from_montgomery(BIGNUM *r,BIGNUM *a,BN_MONT_CTX *mont,BN_CTX *ctx); void BN_MONT_CTX_free(BN_MONT_CTX *mont); int BN_MONT_CTX_set(BN_MONT_CTX *mont,BIGNUM *modulus,BN_CTX *ctx); +BN_BLINDING *BN_BLINDING_new(BIGNUM *A,BIGNUM *Ai,BIGNUM *mod); +void BN_BLINDING_free(BN_BLINDING *b); +int BN_BLINDING_update(BN_BLINDING *b,BN_CTX *ctx); +int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *r, BN_CTX *ctx); +int BN_BLINDING_invert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx); + #else BIGNUM *BN_value_one(); @@ -345,6 +393,8 @@ void BN_clear_free(); BIGNUM *BN_copy(); BIGNUM *BN_bin2bn(); int BN_bn2bin(); +BIGNUM *BN_mpi2bn(); +int BN_bn2mpi(); int BN_sub(); void bn_qsub(); void bn_qadd(); @@ -356,6 +406,8 @@ int BN_sqr(); BN_ULONG BN_mod_word(); BN_ULONG BN_div_word(); int BN_add_word(); +int BN_sub_word(); +int BN_mul_word(); int BN_set_word(); unsigned long BN_get_word(); int BN_cmp(); @@ -363,6 +415,7 @@ void BN_free(); int BN_is_bit_set(); int BN_lshift(); int BN_lshift1(); +int BN_exp(); int BN_mod_exp(); int BN_mod_exp_mont(); int BN_mod_exp_recp(); @@ -383,18 +436,21 @@ BIGNUM *BN_dup(); int BN_ucmp(); int BN_set_bit(); int BN_clear_bit(); -char * BN_bn2ascii(); -int BN_ascii2bn(); +char * BN_bn2hex(); +char * BN_bn2dec(); +int BN_hex2bn(); +int BN_dec2bn(); int BN_gcd(); BIGNUM *BN_mod_inverse(); BIGNUM *BN_generate_prime(); int BN_is_prime(); void ERR_load_BN_strings(); -BN_ULONG bn_mul_add_word(); -BN_ULONG bn_mul_word(); +BN_ULONG bn_mul_add_words(); +BN_ULONG bn_mul_words(); void bn_sqr_words(); BN_ULONG bn_div64(); +BN_ULONG bn_add_words(); int BN_mod_mul_montgomery(); int BN_from_montgomery(); @@ -402,29 +458,42 @@ BN_MONT_CTX *BN_MONT_CTX_new(); void BN_MONT_CTX_free(); int BN_MONT_CTX_set(); +BN_BLINDING *BN_BLINDING_new(); +void BN_BLINDING_free(); +int BN_BLINDING_update(); +int BN_BLINDING_convert(); +int BN_BLINDING_invert(); + #endif /* BEGIN ERROR CODES */ /* Error codes for the BN functions. */ /* Function codes. */ -#define BN_F_BN_BL_CTX_INIT 100 -#define BN_F_BN_BL_CTX_NEW 101 -#define BN_F_BN_BN2ASCII 102 -#define BN_F_BN_CTX_NEW 103 -#define BN_F_BN_DIV 104 -#define BN_F_BN_EXPAND2 105 -#define BN_F_BN_MOD_EXP_MONT 106 -#define BN_F_BN_MOD_INVERSE 107 -#define BN_F_BN_MOD_MUL_RECIPROCAL 108 -#define BN_F_BN_NEW 109 -#define BN_F_BN_RAND 110 +#define BN_F_BN_BLINDING_CONVERT 100 +#define BN_F_BN_BLINDING_INVERT 101 +#define BN_F_BN_BLINDING_NEW 102 +#define BN_F_BN_BLINDING_UPDATE 103 +#define BN_F_BN_BN2DEC 104 +#define BN_F_BN_BN2HEX 105 +#define BN_F_BN_CTX_NEW 106 +#define BN_F_BN_DIV 107 +#define BN_F_BN_EXPAND2 108 +#define BN_F_BN_MOD_EXP_MONT 109 +#define BN_F_BN_MOD_INVERSE 110 +#define BN_F_BN_MOD_MUL_RECIPROCAL 111 +#define BN_F_BN_MPI2BN 112 +#define BN_F_BN_NEW 113 +#define BN_F_BN_RAND 114 /* Reason codes. */ #define BN_R_BAD_RECIPROCAL 100 #define BN_R_CALLED_WITH_EVEN_MODULUS 101 #define BN_R_DIV_BY_ZERO 102 -#define BN_R_NO_INVERSE 103 +#define BN_R_ENCODING_ERROR 103 +#define BN_R_INVALID_LENGTH 104 +#define BN_R_NOT_INITALISED 105 +#define BN_R_NO_INVERSE 106 #ifdef __cplusplus } diff --git a/crypto/bn/bn_add.c b/crypto/bn/bn_add.c index ecdb7453b5..efb2e312e8 100644 --- a/crypto/bn/bn_add.c +++ b/crypto/bn/bn_add.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_add.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -81,16 +81,16 @@ BIGNUM *b; { tmp=a; a=b; b=tmp; } /* we are now a - b */ - if (bn_expand(r,((a->top > b->top)?a->top:b->top)*BN_BITS2) - == NULL) return(0); if (BN_ucmp(a,b) < 0) { + if (bn_wexpand(r,b->top) == NULL) return(0); bn_qsub(r,b,a); r->neg=1; } else { + if (bn_wexpand(r,a->top) == NULL) return(0); bn_qsub(r,a,b); r->neg=0; } @@ -103,12 +103,17 @@ BIGNUM *b; r->neg=0; i=(a->top > b->top); - if (bn_expand(r,(((i)?a->top:b->top)+1)*BN_BITS2) == NULL) return(0); if (i) + { + if (bn_wexpand(r,a->top+1) == NULL) return(0); bn_qadd(r,a,b); + } else + { + if (bn_wexpand(r,b->top+1) == NULL) return(0); bn_qadd(r,b,a); + } return(1); } @@ -120,7 +125,7 @@ BIGNUM *b; { register int i; int max,min; - BN_ULONG *ap,*bp,*rp,carry,t1,t2; + BN_ULONG *ap,*bp,*rp,carry,t1; max=a->top; min=b->top; @@ -130,32 +135,24 @@ BIGNUM *b; bp=b->d; rp=r->d; carry=0; - for (i=0; i<min; i++) - { - t1= *(ap++); - t2= *(bp++); - if (carry) - { - carry=(t2 >= ((~t1)&BN_MASK2)); - t2=(t1+t2+1)&BN_MASK2; - } - else - { - t2=(t1+t2)&BN_MASK2; - carry=(t2 < t1); - } - *(rp++)=t2; - } + + carry=bn_add_words(rp,ap,bp,min); + rp+=min; + ap+=min; + bp+=min; + i=min; + if (carry) { while (i < max) { - t1= *(ap++); - t2=(t1+1)&BN_MASK2; - *(rp++)=t2; - carry=(t2 < t1); i++; - if (!carry) break; + t1= *(ap++); + if ((*(rp++)=(t1+1)&BN_MASK2) >= t1) + { + carry=0; + break; + } } if ((i >= max) && carry) { diff --git a/crypto/bn/bn_blind.c b/crypto/bn/bn_blind.c new file mode 100644 index 0000000000..a7b34f0bf0 --- /dev/null +++ b/crypto/bn/bn_blind.c @@ -0,0 +1,143 @@ +/* crypto/bn/bn_blind.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" + +BN_BLINDING *BN_BLINDING_new(A,Ai,mod) +BIGNUM *A; +BIGNUM *Ai; +BIGNUM *mod; + { + BN_BLINDING *ret=NULL; + + if ((ret=(BN_BLINDING *)Malloc(sizeof(BN_BLINDING))) == NULL) + BNerr(BN_F_BN_BLINDING_NEW,ERR_R_MALLOC_FAILURE); + memset(ret,0,sizeof(BN_BLINDING)); + if ((ret->A=BN_new()) == NULL) goto err; + if ((ret->Ai=BN_new()) == NULL) goto err; + if (!BN_copy(ret->A,A)) goto err; + if (!BN_copy(ret->Ai,Ai)) goto err; + ret->mod=mod; + return(ret); +err: + if (ret != NULL) BN_BLINDING_free(ret); + return(ret); + } + +void BN_BLINDING_free(r) +BN_BLINDING *r; + { + if (r->A != NULL) BN_free(r->A ); + if (r->Ai != NULL) BN_free(r->Ai); + Free(r); + } + +int BN_BLINDING_update(b,ctx) +BN_BLINDING *b; +BN_CTX *ctx; + { + int ret=0; + + if ((b->A == NULL) || (b->Ai == NULL)) + { + BNerr(BN_F_BN_BLINDING_UPDATE,BN_R_NOT_INITALISED); + goto err; + } + + if (!BN_mod_mul(b->A,b->A,b->A,b->mod,ctx)) goto err; + if (!BN_mod_mul(b->Ai,b->Ai,b->Ai,b->mod,ctx)) goto err; + + ret=1; +err: + return(ret); + } + +int BN_BLINDING_convert(n,b,ctx) +BIGNUM *n; +BN_BLINDING *b; +BN_CTX *ctx; + { + if ((b->A == NULL) || (b->Ai == NULL)) + { + BNerr(BN_F_BN_BLINDING_CONVERT,BN_R_NOT_INITALISED); + return(0); + } + return(BN_mod_mul(n,n,b->A,b->mod,ctx)); + } + +int BN_BLINDING_invert(n,b,ctx) +BIGNUM *n; +BN_BLINDING *b; +BN_CTX *ctx; + { + int ret; + if ((b->A == NULL) || (b->Ai == NULL)) + { + BNerr(BN_F_BN_BLINDING_INVERT,BN_R_NOT_INITALISED); + return(0); + } + if ((ret=BN_mod_mul(n,n,b->Ai,b->mod,ctx)) >= 0) + { + if (!BN_BLINDING_update(b,ctx)) + return(0); + } + return(ret); + } + diff --git a/crypto/bn/bn_div.c b/crypto/bn/bn_div.c index 0ce4d4182f..2263bdc7da 100644 --- a/crypto/bn/bn_div.c +++ b/crypto/bn/bn_div.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_div.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -132,7 +132,7 @@ BN_CTX *ctx; BN_ULONG d0,d1; int num_n,div_n; - if (BN_is_zero(num)) + if (BN_is_zero(divisor)) { BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO); return(0); @@ -184,11 +184,11 @@ BN_CTX *ctx; /* Setup to 'res' */ res->neg= (num->neg^divisor->neg); res->top=loop; - if (!bn_expand(res,(loop+1)*BN_BITS2)) goto err; + if (!bn_wexpand(res,(loop+1))) goto err; resp= &(res->d[loop-1]); /* space for temp */ - if (!bn_expand(tmp,(div_n+1)*BN_BITS2)) goto err; + if (!bn_wexpand(tmp,(div_n+1))) goto err; if (BN_ucmp(&wnum,sdiv) >= 0) { @@ -237,9 +237,9 @@ BN_CTX *ctx; t3t=LBITS(d0); t3h=HBITS(d0); mul64(t3t,t3h,ql,qh); /* t3=t1-(BN_ULLONG)q*d0; */ - t3l=(t1l-t3t); + t3l=(t1l-t3t)&BN_MASK2; if (t3l > t1l) t3h++; - t3h=(t1h-t3h); + t3h=(t1h-t3h)&BN_MASK2; /*if ((t3>>BN_BITS2) || (t2 <= ((t3<<BN_BITS2)+wnump[-2]))) @@ -252,7 +252,7 @@ BN_CTX *ctx; } #endif } - l0=bn_mul_word(tmp->d,sdiv->d,div_n,q); + l0=bn_mul_words(tmp->d,sdiv->d,div_n,q); tmp->d[div_n]=l0; for (j=div_n+1; j>0; j--) if (tmp->d[j-1]) break; diff --git a/crypto/bn/bn_err.c b/crypto/bn/bn_err.c index 38818d6e67..029ae810d5 100644 --- a/crypto/bn/bn_err.c +++ b/crypto/bn/bn_err.c @@ -60,17 +60,22 @@ #include "bn.h" /* BEGIN ERROR CODES */ +#ifndef NO_ERR static ERR_STRING_DATA BN_str_functs[]= { -{ERR_PACK(0,BN_F_BN_BL_CTX_INIT,0), "BN_BL_CTX_INIT"}, -{ERR_PACK(0,BN_F_BN_BL_CTX_NEW,0), "BN_BL_CTX_NEW"}, -{ERR_PACK(0,BN_F_BN_BN2ASCII,0), "BN_bn2ascii"}, +{ERR_PACK(0,BN_F_BN_BLINDING_CONVERT,0), "BN_BLINDING_convert"}, +{ERR_PACK(0,BN_F_BN_BLINDING_INVERT,0), "BN_BLINDING_invert"}, +{ERR_PACK(0,BN_F_BN_BLINDING_NEW,0), "BN_BLINDING_new"}, +{ERR_PACK(0,BN_F_BN_BLINDING_UPDATE,0), "BN_BLINDING_update"}, +{ERR_PACK(0,BN_F_BN_BN2DEC,0), "BN_bn2dec"}, +{ERR_PACK(0,BN_F_BN_BN2HEX,0), "BN_bn2hex"}, {ERR_PACK(0,BN_F_BN_CTX_NEW,0), "BN_CTX_new"}, {ERR_PACK(0,BN_F_BN_DIV,0), "BN_div"}, {ERR_PACK(0,BN_F_BN_EXPAND2,0), "bn_expand2"}, {ERR_PACK(0,BN_F_BN_MOD_EXP_MONT,0), "BN_mod_exp_mont"}, {ERR_PACK(0,BN_F_BN_MOD_INVERSE,0), "BN_mod_inverse"}, {ERR_PACK(0,BN_F_BN_MOD_MUL_RECIPROCAL,0), "BN_mod_mul_reciprocal"}, +{ERR_PACK(0,BN_F_BN_MPI2BN,0), "BN_mpi2bn"}, {ERR_PACK(0,BN_F_BN_NEW,0), "BN_new"}, {ERR_PACK(0,BN_F_BN_RAND,0), "BN_rand"}, {0,NULL}, @@ -81,18 +86,26 @@ static ERR_STRING_DATA BN_str_reasons[]= {BN_R_BAD_RECIPROCAL ,"bad reciprocal"}, {BN_R_CALLED_WITH_EVEN_MODULUS ,"called with even modulus"}, {BN_R_DIV_BY_ZERO ,"div by zero"}, +{BN_R_ENCODING_ERROR ,"encoding error"}, +{BN_R_INVALID_LENGTH ,"invalid length"}, +{BN_R_NOT_INITALISED ,"not initalised"}, {BN_R_NO_INVERSE ,"no inverse"}, {0,NULL}, }; +#endif + void ERR_load_BN_strings() { static int init=1; - if (init) - { + if (init); + {; init=0; +#ifndef NO_ERR ERR_load_strings(ERR_LIB_BN,BN_str_functs); ERR_load_strings(ERR_LIB_BN,BN_str_reasons); +#endif + } } diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c index 0a0db370c3..c056a5083f 100644 --- a/crypto/bn/bn_exp.c +++ b/crypto/bn/bn_exp.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_exp.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -120,6 +120,38 @@ err: #endif +/* this one works - simple but works */ +int BN_exp(r,a,p,ctx) +BIGNUM *r,*a,*p; +BN_CTX *ctx; + { + int i,bits,ret=0; + BIGNUM *v,*tmp; + + v=ctx->bn[ctx->tos++]; + tmp=ctx->bn[ctx->tos++]; + + if (BN_copy(v,a) == NULL) goto err; + bits=BN_num_bits(p); + + if (BN_is_odd(p)) + { if (BN_copy(r,a) == NULL) goto err; } + else { if (BN_one(r)) goto err; } + + for (i=1; i<bits; i++) + { + if (!BN_sqr(tmp,v,ctx)) goto err; + if (BN_is_bit_set(p,i)) + { + if (!BN_mul(tmp,r,v)) goto err; + } + } + ret=1; +err: + ctx->tos-=2; + return(ret); + } + int BN_mod_exp(r,a,p,m,ctx) BIGNUM *r; BIGNUM *a; @@ -137,7 +169,7 @@ BN_CTX *ctx; /* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ if (BN_is_odd(m)) - { ret=BN_mod_exp_mont(r,a,p,m,ctx); } + { ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); } else #endif #ifdef RECP_MUL_MOD @@ -266,17 +298,19 @@ err: /* #endif */ /* #ifdef MONT_MUL_MOD */ -int BN_mod_exp_mont(r,a,p,m,ctx) +int BN_mod_exp_mont(r,a,p,m,ctx,in_mont) BIGNUM *r; BIGNUM *a; BIGNUM *p; BIGNUM *m; BN_CTX *ctx; +BN_MONT_CTX *in_mont; { +#define TABLE_SIZE 16 int i,j,bits,ret=0,wstart,wend,window,wvalue; int start=1; BIGNUM *d,*aa; - BIGNUM *val[16]; + BIGNUM *val[TABLE_SIZE]; BN_MONT_CTX *mont=NULL; if (!(m->d[0] & 1)) @@ -295,8 +329,15 @@ BN_CTX *ctx; /* If this is not done, things will break in the montgomery * part */ - if ((mont=BN_MONT_CTX_new()) == NULL) goto err; - if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; +#if 1 + if (in_mont != NULL) + mont=in_mont; + else +#endif + { + if ((mont=BN_MONT_CTX_new()) == NULL) goto err; + if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; + } val[0]=BN_new(); if (BN_ucmp(a,m) >= 0) @@ -309,11 +350,11 @@ BN_CTX *ctx; if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */ if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */ - if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */ + if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */ window=1; - else if (bits >= 256) + else if (bits > 250) window=5; /* max size of window */ - else if (bits >= 128) + else if (bits >= 120) window=4; else window=3; @@ -325,7 +366,7 @@ BN_CTX *ctx; if (!BN_mod_mul_montgomery(val[i],val[i-1],d,mont,ctx)) goto err; } - for (; i<16; i++) + for (; i<TABLE_SIZE; i++) val[i]=NULL; start=1; /* This is used to avoid multiplication etc @@ -341,8 +382,10 @@ BN_CTX *ctx; if (BN_is_bit_set(p,wstart) == 0) { if (!start) + { if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) goto err; + } if (wstart == 0) break; wstart--; continue; @@ -388,9 +431,9 @@ BN_CTX *ctx; BN_from_montgomery(r,r,mont,ctx); ret=1; err: - if (mont != NULL) BN_MONT_CTX_free(mont); + if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); ctx->tos--; - for (i=0; i<16; i++) + for (i=0; i<TABLE_SIZE; i++) if (val[i] != NULL) BN_clear_free(val[i]); return(ret); } diff --git a/crypto/bn/bn_gcd.c b/crypto/bn/bn_gcd.c index 9b0bc2b100..071bba3b4b 100644 --- a/crypto/bn/bn_gcd.c +++ b/crypto/bn/bn_gcd.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_gcd.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h index 4d44651df8..edfd788338 100644 --- a/crypto/bn/bn_lcl.h +++ b/crypto/bn/bn_lcl.h @@ -1,5 +1,5 @@ /* crypto/bn/bn_lcl.h */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -78,31 +78,23 @@ extern "C" { if (*(fix_top_l--)) break; \ } -#define bn_expand(n,b) ((((b)/BN_BITS2) <= (n)->max)?(n):bn_expand2((n),(b))) +/* #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; \ t=(BN_ULLONG)w * (a) + (r) + (c); \ - (r)=Lw(t); \ + (r)= Lw(t); \ (c)= Hw(t); \ } #define mul(r,a,w,c) { \ BN_ULLONG t; \ t=(BN_ULLONG)w * (a) + (c); \ - (r)=Lw(t); \ + (r)= Lw(t); \ (c)= Hw(t); \ } -#define bn_mul_words(r1,r2,a,b) \ - { \ - BN_ULLONG t; \ - t=(BN_ULLONG)(a)*(b); \ - r1=Lw(t); \ - r2=Hw(t); \ - } - #else /************************************************************* * No long long type @@ -126,10 +118,10 @@ extern "C" { lt=(bl)*(lt); \ m1=(bl)*(ht); \ ht =(bh)*(ht); \ - m+=m1; if ((m&BN_MASK2) < m1) ht+=L2HBITS(1L); \ + m=(m+m1)&BN_MASK2; if (m < m1) ht+=L2HBITS(1L); \ ht+=HBITS(m); \ m1=L2HBITS(m); \ - lt+=m1; if ((lt&BN_MASK2) < m1) ht++; \ + lt=(lt+m1)&BN_MASK2; if (lt < m1) ht++; \ (l)=lt; \ (h)=ht; \ } @@ -146,7 +138,7 @@ extern "C" { h*=h; \ h+=(m&BN_MASK2h1)>>(BN_BITS4-1); \ m =(m&BN_MASK2l)<<(BN_BITS4+1); \ - l+=m; if ((l&BN_MASK2) < m) h++; \ + l=(l+m)&BN_MASK2; if (l < m) h++; \ (lo)=l; \ (ho)=h; \ } @@ -160,11 +152,11 @@ extern "C" { mul64(l,h,(bl),(bh)); \ \ /* non-multiply part */ \ - l+=(c); if ((l&BN_MASK2) < (c)) h++; \ + l=(l+(c))&BN_MASK2; if (l < (c)) h++; \ (c)=(r); \ - l+=(c); if ((l&BN_MASK2) < (c)) h++; \ + l=(l+(c))&BN_MASK2; if (l < (c)) h++; \ (c)=h&BN_MASK2; \ - (r)=l&BN_MASK2; \ + (r)=l; \ } #define mul(r,a,bl,bh,c) { \ @@ -181,31 +173,22 @@ extern "C" { (r)=l&BN_MASK2; \ } -#define bn_mul_words(r1,r2,a,b) \ - { \ - BN_ULONG l,h,bl,bh; \ - \ - h=(a); \ - l=LBITS(h); \ - h=HBITS(h); \ - bh=(b); \ - bl=LBITS(bh); \ - bh=HBITS(bh); \ - \ - mul64(l,h,bl,bh); \ - \ - (r1)=l; \ - (r2)=h; \ - } #endif #ifndef NOPROTO BIGNUM *bn_expand2(BIGNUM *b, int bits); +#ifdef X86_ASM +void bn_add_words(BN_ULONG *r,BN_ULONG *a,int num); +#endif + #else BIGNUM *bn_expand2(); +#ifdef X86_ASM +BN_ULONG bn_add_words(); +#endif #endif diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 288ebca68c..bfe7628ad4 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_lib.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -60,7 +60,7 @@ #include "cryptlib.h" #include "bn_lcl.h" -char *BN_version="Big Number part of SSLeay 0.8.1b 29-Jun-1998"; +char *BN_version="Big Number part of SSLeay 0.9.0b 29-Jun-1998"; BIGNUM *BN_value_one() { @@ -188,7 +188,7 @@ BIGNUM *a; i=(a->top-1)*BN_BITS2; if (l == 0) { -#ifndef WIN16 +#if !defined(NO_STDIO) && !defined(WIN16) fprintf(stderr,"BAD TOP VALUE\n"); #endif abort(); @@ -279,24 +279,23 @@ BN_CTX *c; Free(c); } -BIGNUM *bn_expand2(b, bits) +BIGNUM *bn_expand2(b, words) BIGNUM *b; -int bits; +int words; { BN_ULONG *p; - register int n; - while (bits > b->max*BN_BITS2) + if (words > b->max) { - n=((bits+BN_BITS2-1)/BN_BITS2)*2; - p=b->d=(BN_ULONG *)Realloc(b->d,sizeof(BN_ULONG)*(n+1)); + p=(BN_ULONG *)Realloc(b->d,sizeof(BN_ULONG)*(words+1)); if (p == NULL) { BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE); return(NULL); } - memset(&(p[b->max]),0,((n+1)-b->max)*sizeof(BN_ULONG)); - b->max=n; + b->d=p; + memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); + b->max=words; } return(b); } @@ -315,10 +314,53 @@ BIGNUM *BN_copy(a, b) BIGNUM *a; BIGNUM *b; { - if (bn_expand(a,b->top*BN_BITS2) == NULL) return(NULL); + int i; + BN_ULONG *A,*B; + + if (a == b) return(a); + if (bn_wexpand(a,b->top) == NULL) return(NULL); + +#if 1 + A=a->d; + B=b->d; + for (i=b->top&(~7); i>0; i-=8) + { + A[0]=B[0]; + A[1]=B[1]; + A[2]=B[2]; + A[3]=B[3]; + A[4]=B[4]; + A[5]=B[5]; + A[6]=B[6]; + A[7]=B[7]; + A+=8; + B+=8; + } + switch (b->top&7) + { + case 7: + A[6]=B[6]; + case 6: + A[5]=B[5]; + case 5: + A[4]=B[4]; + case 4: + A[3]=B[3]; + case 3: + A[2]=B[2]; + case 2: + A[1]=B[1]; + case 1: + A[0]=B[0]; + } +#else memcpy(a->d,b->d,sizeof(b->d[0])*b->top); +#endif + /* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/ a->top=b->top; + if (a->top == 0) + a->d[0]=0; a->neg=b->neg; return(a); } @@ -507,7 +549,11 @@ int n; i=n/BN_BITS2; j=n%BN_BITS2; - if (a->top <= i) return(0); + if (a->top <= i) + { + if (bn_expand(a,n) == NULL) return(0); + a->top=i+1; + } a->d[i]|=(1L<<j); return(1); diff --git a/crypto/bn/bn_m.c b/crypto/bn/bn_m.c new file mode 100644 index 0000000000..5166daaeec --- /dev/null +++ b/crypto/bn/bn_m.c @@ -0,0 +1,169 @@ +/* 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" +#include "stack.h" + +int limit=16; + +typedef struct bn_pool_st + { + int used; + int tos; + STACK *sk; + } BN_POOL; + +BIGNUM *BN_POOL_push(bp) +BN_POOL *bp; + { + BIGNUM *ret; + + if (bp->used >= bp->tos) + { + ret=BN_new(); + sk_push(bp->sk,(char *)ret); + bp->tos++; + bp->used++; + } + else + { + ret=(BIGNUM *)sk_value(bp->sk,bp->used); + bp->used++; + } + return(ret); + } + +void BN_POOL_pop(bp,num) +BN_POOL *bp; +int num; + { + bp->used-=num; + } + +int BN_m(r,a,b) +BIGNUM *r,*a,*b; + { + static BN_POOL bp; + static init=1; + + if (init) + { + bp.used=0; + bp.tos=0; + bp.sk=sk_new_null(); + init=0; + } + return(BN_mm(r,a,b,&bp)); + } + +/* r must be different to a and b */ +int BN_mm(m, A, B, bp) +BIGNUM *m,*A,*B; +BN_POOL *bp; + { + int i,num; + int an,bn; + BIGNUM *a,*b,*c,*d,*ac,*bd; + + an=A->top; + bn=B->top; + if ((an <= limit) || (bn <= limit)) + { + return(BN_mul(m,A,B)); + } + + a=BN_POOL_push(bp); + b=BN_POOL_push(bp); + c=BN_POOL_push(bp); + d=BN_POOL_push(bp); + ac=BN_POOL_push(bp); + bd=BN_POOL_push(bp); + + num=(an <= bn)?an:bn; + num=1<<(BN_num_bits_word(num-1)-1); + + /* Are going to now chop things into 'num' word chunks. */ + num*=BN_BITS2; + + BN_copy(a,A); + BN_mask_bits(a,num); + BN_rshift(b,A,num); + + BN_copy(c,B); + BN_mask_bits(c,num); + BN_rshift(d,B,num); + + BN_sub(ac ,b,a); + BN_sub(bd,c,d); + BN_mm(m,ac,bd,bp); + BN_mm(ac,a,c,bp); + BN_mm(bd,b,d,bp); + + BN_add(m,m,ac); + BN_add(m,m,bd); + BN_lshift(m,m,num); + BN_lshift(bd,bd,num*2); + + BN_add(m,m,ac); + BN_add(m,m,bd); + BN_POOL_pop(bp,6); + return(1); + } + diff --git a/crypto/bn/bn_mod.c b/crypto/bn/bn_mod.c index c94241f59e..c351aac14f 100644 --- a/crypto/bn/bn_mod.c +++ b/crypto/bn/bn_mod.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_mod.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c index 932d10b736..e435df61f8 100644 --- a/crypto/bn/bn_mont.c +++ b/crypto/bn/bn_mont.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_mont.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -95,8 +95,8 @@ BN_MONT_CTX *mont; BN_CTX *ctx; { BIGNUM *n,*t1,*r; - BN_ULONG *ap,*np,*rp,k,n0,v,v2; - int al,nl,max,i,x; + BN_ULONG *ap,*np,*rp,n0,v; + int al,nl,max,i,x,ri; int retn=0; t1=ctx->bn[ctx->tos]; @@ -105,50 +105,76 @@ BN_CTX *ctx; if (!BN_copy(r,a)) goto err; n=mont->N; - if (!BN_copy(t1,a)) goto err; - BN_mask_bits(t1,mont->ri); - - a=t1; + ap=a->d; + /* mont->ri is the size of mont->N in bits/words */ + al=ri=mont->ri/BN_BITS2; - al=a->top; nl=n->top; if ((al == 0) || (nl == 0)) { r->top=0; return(1); } max=(nl+al+1); /* allow for overflow (no?) XXX */ - if (bn_expand(r,(max)*BN_BITS2) == NULL) goto err; + if (bn_wexpand(r,max) == NULL) goto err; + if (bn_wexpand(ret,max) == NULL) goto err; r->neg=a->neg^n->neg; - ap=a->d; np=n->d; rp=r->d; - /* clear the top bytes of T */ + /* clear the top words of T */ +#if 1 for (i=r->top; i<max; i++) /* memset? XXX */ r->d[i]=0; -/* memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); */ +#else + memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); +#endif r->top=max; n0=mont->n0; for (i=0; i<nl; i++) { - /* This is were part words probably goes wrong */ - k=(rp[0]*n0)&BN_MASK2; - v=bn_mul_add_word(rp,np,nl,k); - - for (x=nl; v; x++) +#if 0 + int x1,x2; + + if (i+4 > nl) + { + x2=nl; + x1=0; + } + else { - v2=rp[x]; - v2+=v; - rp[x]=v2; - v=((v2&BN_MASK2) < v)?1:0; /* ever true? XXX */ + x2=i+4; + x1=nl-x2; + } + v=bn_mul_add_words(&(rp[x1]),&(np[x1]),x2,(rp[x1]*n0)&BN_MASK2); +#else + v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2); +#endif + + if (((rp[nl]+=v)&BN_MASK2) < v) + { + for (x=(nl+1); (((++rp[x])&BN_MASK2) == 0); x++) + ; } rp++; } while (r->d[r->top-1] == 0) r->top--; + /* mont->ri will be a multiple of the word size */ +#if 0 BN_rshift(ret,r,mont->ri); +#else + ap=r->d; + rp=ret->d; + x=ri; + al=r->top-x; + for (i=0; i<al; i++) + { + rp[i]=ap[i+x]; + } + ret->top=al; +#endif if (BN_ucmp(ret,mont->N) >= 0) { diff --git a/crypto/bn/bn_mpi.c b/crypto/bn/bn_mpi.c new file mode 100644 index 0000000000..53945c1057 --- /dev/null +++ b/crypto/bn/bn_mpi.c @@ -0,0 +1,134 @@ +/* crypto/bn/bn_mpi.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_bn2mpi(a,d) +BIGNUM *a; +unsigned char *d; + { + int bits; + int num=0; + int ext=0; + long l; + + bits=BN_num_bits(a); + num=(bits+7)/8; + if (bits > 0) + { + ext=((bits & 0x07) == 0); + } + if (d == NULL) + return(num+4+ext); + + l=num+ext; + d[0]=(unsigned char)(l>>24)&0xff; + d[1]=(unsigned char)(l>>16)&0xff; + d[2]=(unsigned char)(l>> 8)&0xff; + d[3]=(unsigned char)(l )&0xff; + if (ext) d[4]=0; + num=BN_bn2bin(a,&(d[4+ext])); + if (a->neg) + d[4]|=0x80; + return(num+4+ext); + } + +BIGNUM *BN_mpi2bn(d,n,a) +unsigned char *d; +int n; +BIGNUM *a; + { + long len; + int neg=0; + + if (n < 4) + { + BNerr(BN_F_BN_MPI2BN,BN_R_INVALID_LENGTH); + return(NULL); + } + len=(d[0]<<24)|(d[1]<<16)|(d[2]<<8)|d[3]; + if ((len+4) != n) + { + BNerr(BN_F_BN_MPI2BN,BN_R_ENCODING_ERROR); + return(NULL); + } + + if (a == NULL) a=BN_new(); + if (a == NULL) return(NULL); + + if (len == 0) + { + a->neg=0; + a->top=0; + return(a); + } + d+=4; + if ((*d) & 0x80) + neg=1; + if (BN_bin2bn(d,(int)len,a) == NULL) + return(NULL); + a->neg=neg; + if (neg) + { + BN_clear_bit(a,BN_num_bits(a)-1); + } + return(a); + } + diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c index 3c8bf23a70..d0c04e1d4b 100644 --- a/crypto/bn/bn_mul.c +++ b/crypto/bn/bn_mul.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_mul.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -61,6 +61,7 @@ #include "bn_lcl.h" /* r must be different to a and b */ +/* int BN_mmul(r, a, b) */ int BN_mul(r, a, b) BIGNUM *r; BIGNUM *a; @@ -79,21 +80,130 @@ BIGNUM *b; } max=(al+bl); - if (bn_expand(r,(max)*BN_BITS2) == NULL) return(0); + 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_word(rp,ap,al,*(bp++)); + rp[al]=bn_mul_words(rp,ap,al,*(bp++)); rp++; for (i=1; i<bl; i++) { - rp[al]=bn_mul_add_word(rp,ap,al,*(bp++)); + rp[al]=bn_mul_add_words(rp,ap,al,*(bp++)); rp++; } if (r->d[max-1] == 0) r->top--; return(1); } +#if 0 +#include "stack.h" + +int limit=16; + +typedef struct bn_pool_st + { + int used; + int tos; + STACK *sk; + } BN_POOL; + +BIGNUM *BN_POOL_push(bp) +BN_POOL *bp; + { + BIGNUM *ret; + + if (bp->used >= bp->tos) + { + ret=BN_new(); + sk_push(bp->sk,(char *)ret); + bp->tos++; + bp->used++; + } + else + { + ret=(BIGNUM *)sk_value(bp->sk,bp->used); + bp->used++; + } + return(ret); + } + +void BN_POOL_pop(bp,num) +BN_POOL *bp; +int num; + { + bp->used-=num; + } + +int BN_mul(r,a,b) +BIGNUM *r,*a,*b; + { + static BN_POOL bp; + static init=1; + + if (init) + { + bp.used=0; + bp.tos=0; + bp.sk=sk_new_null(); + init=0; + } + return(BN_mm(r,a,b,&bp)); + } + +/* r must be different to a and b */ +int BN_mm(m, A, B, bp) +BIGNUM *m,*A,*B; +BN_POOL *bp; + { + int i,num; + int an,bn; + BIGNUM *a,*b,*c,*d,*ac,*bd; + + an=A->top; + bn=B->top; + if ((an <= limit) || (bn <= limit)) + { + return(BN_mmul(m,A,B)); + } + + a=BN_POOL_push(bp); + b=BN_POOL_push(bp); + c=BN_POOL_push(bp); + d=BN_POOL_push(bp); + ac=BN_POOL_push(bp); + bd=BN_POOL_push(bp); + + num=(an <= bn)?an:bn; + num=1<<(BN_num_bits_word(num-1)-1); + + /* Are going to now chop things into 'num' word chunks. */ + num*=BN_BITS2; + + BN_copy(a,A); + BN_mask_bits(a,num); + BN_rshift(b,A,num); + + BN_copy(c,B); + BN_mask_bits(c,num); + BN_rshift(d,B,num); + + BN_sub(ac ,b,a); + BN_sub(bd,c,d); + BN_mm(m,ac,bd,bp); + BN_mm(ac,a,c,bp); + BN_mm(bd,b,d,bp); + + BN_add(m,m,ac); + BN_add(m,m,bd); + BN_lshift(m,m,num); + BN_lshift(bd,bd,num*2); + + BN_add(m,m,ac); + BN_add(m,m,bd); + BN_POOL_pop(bp,6); + return(1); + } +#endif diff --git a/crypto/bn/bn_mulw.c b/crypto/bn/bn_mulw.c index d903127395..abfc7e4d6c 100644 --- a/crypto/bn/bn_mulw.c +++ b/crypto/bn/bn_mulw.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_mulw.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -62,7 +62,7 @@ #ifdef BN_LLONG -BN_ULONG bn_mul_add_word(rp,ap,num,w) +BN_ULONG bn_mul_add_words(rp,ap,num,w) BN_ULONG *rp,*ap; int num; BN_ULONG w; @@ -86,7 +86,7 @@ BN_ULONG w; return(c1); } -BN_ULONG bn_mul_word(rp,ap,num,w) +BN_ULONG bn_mul_words(rp,ap,num,w) BN_ULONG *rp,*ap; int num; BN_ULONG w; @@ -138,9 +138,45 @@ int n; } } +BN_ULONG bn_add_words(r,a,b,n) +BN_ULONG *r,*a,*b; +int n; + { + BN_ULLONG ll; + + ll=0; + for (;;) + { + ll+= (BN_ULLONG)a[0]+b[0]; + r[0]=(BN_ULONG)ll&BN_MASK2; + ll>>=BN_BITS2; + if (--n <= 0) break; + + ll+= (BN_ULLONG)a[1]+b[1]; + r[1]=(BN_ULONG)ll&BN_MASK2; + ll>>=BN_BITS2; + if (--n <= 0) break; + + ll+= (BN_ULLONG)a[2]+b[2]; + r[2]=(BN_ULONG)ll&BN_MASK2; + ll>>=BN_BITS2; + if (--n <= 0) break; + + ll+= (BN_ULLONG)a[3]+b[3]; + r[3]=(BN_ULONG)ll&BN_MASK2; + ll>>=BN_BITS2; + if (--n <= 0) break; + + a+=4; + b+=4; + r+=4; + } + return(ll&BN_MASK2); + } + #else -BN_ULONG bn_mul_add_word(rp,ap,num,w) +BN_ULONG bn_mul_add_words(rp,ap,num,w) BN_ULONG *rp,*ap; int num; BN_ULONG w; @@ -167,7 +203,7 @@ BN_ULONG w; return(c); } -BN_ULONG bn_mul_word(rp,ap,num,w) +BN_ULONG bn_mul_words(rp,ap,num,w) BN_ULONG *rp,*ap; int num; BN_ULONG w; @@ -217,6 +253,33 @@ int n; } } +BN_ULONG bn_add_words(r,a,b,n) +BN_ULONG *r,*a,*b; +int n; + { + BN_ULONG t1,t2; + int carry,i; + + carry=0; + for (i=0; i<n; i++) + { + t1= *(a++); + t2= *(b++); + if (carry) + { + carry=(t2 >= ((~t1)&BN_MASK2)); + t2=(t1+t2+1)&BN_MASK2; + } + else + { + t2=(t1+t2)&BN_MASK2; + carry=(t2<t1); + } + *(r++)=t2; + } + return(carry); + } + #endif #if defined(BN_LLONG) && defined(BN_DIV2W) @@ -242,7 +305,7 @@ BN_ULONG h,l,d; i=BN_num_bits_word(d); if ((i != BN_BITS2) && (h > (BN_ULONG)1<<i)) { -#ifndef WIN16 +#if !defined(NO_STDIO) && !defined(WIN16) fprintf(stderr,"Division would overflow (%d)\n",i); #endif abort(); diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index 07a8289492..0c85f70b59 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_prime.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -69,7 +69,8 @@ #include "bn_prime.h" #ifndef NOPROTO -static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx); +static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2, + BN_MONT_CTX *mont); static int probable_prime(BIGNUM *rnd, int bits); static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem, BN_CTX *ctx); @@ -82,12 +83,13 @@ static int probable_prime_dh(); static int probable_prime_dh_strong(); #endif -BIGNUM *BN_generate_prime(bits,strong,add,rem,callback) +BIGNUM *BN_generate_prime(bits,strong,add,rem,callback,cb_arg) int bits; int strong; BIGNUM *add; BIGNUM *rem; -void (*callback)(P_I_I); +void (*callback)(P_I_I_P); +char *cb_arg; { BIGNUM *rnd=NULL; BIGNUM *ret=NULL; @@ -120,11 +122,11 @@ loop: } } /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */ - if (callback != NULL) callback(0,c1++); + if (callback != NULL) callback(0,c1++,cb_arg); if (!strong) { - i=BN_is_prime(rnd,BN_prime_checks,callback,ctx); + i=BN_is_prime(rnd,BN_prime_checks,callback,ctx,cb_arg); if (i == -1) goto err; if (i == 0) goto loop; } @@ -138,15 +140,15 @@ loop: for (i=0; i<BN_prime_checks; i++) { - j=BN_is_prime(rnd,1,callback,ctx); + j=BN_is_prime(rnd,1,callback,ctx,cb_arg); if (j == -1) goto err; if (j == 0) goto loop; - j=BN_is_prime(t,1,callback,ctx); + j=BN_is_prime(t,1,callback,ctx,cb_arg); if (j == -1) goto err; if (j == 0) goto loop; - if (callback != NULL) callback(2,c1-1); + if (callback != NULL) callback(2,c1-1,cb_arg); /* We have a strong prime test pass */ } } @@ -159,60 +161,78 @@ err: return(ret); } -int BN_is_prime(a,checks,callback,ctx_passed) +int BN_is_prime(a,checks,callback,ctx_passed,cb_arg) BIGNUM *a; int checks; -void (*callback)(P_I_I); +void (*callback)(P_I_I_P); BN_CTX *ctx_passed; +char *cb_arg; { int i,j,c2=0,ret= -1; BIGNUM *check; - BN_CTX *ctx; + BN_CTX *ctx=NULL,*ctx2=NULL; + BN_MONT_CTX *mont=NULL; + if (!BN_is_odd(a)) + return(0); if (ctx_passed != NULL) ctx=ctx_passed; else if ((ctx=BN_CTX_new()) == NULL) goto err; + if ((ctx2=BN_CTX_new()) == NULL) goto err; + if ((mont=BN_MONT_CTX_new()) == NULL) goto err; + check=ctx->bn[ctx->tos++]; + + /* Setup the montgomery structure */ + if (!BN_MONT_CTX_set(mont,a,ctx2)) goto err; + for (i=0; i<checks; i++) { if (!BN_rand(check,BN_num_bits(a)-1,0,0)) goto err; - j=witness(check,a,ctx); + j=witness(check,a,ctx,ctx2,mont); if (j == -1) goto err; if (j) { ret=0; goto err; } - if (callback != NULL) callback(1,c2++); + if (callback != NULL) callback(1,c2++,cb_arg); } ret=1; err: ctx->tos--; if ((ctx_passed == NULL) && (ctx != NULL)) BN_CTX_free(ctx); + if (ctx2 != NULL) + BN_CTX_free(ctx2); + if (mont != NULL) BN_MONT_CTX_free(mont); return(ret); } #define RECP_MUL_MOD -static int witness(a, n,ctx) +static int witness(a,n,ctx,ctx2,mont) BIGNUM *a; BIGNUM *n; -BN_CTX *ctx; +BN_CTX *ctx,*ctx2; +BN_MONT_CTX *mont; { - int k,i,nb,ret= -1; - BIGNUM *d,*dd,*tmp; - BIGNUM *d1,*d2,*x,*n1,*inv; + int k,i,ret= -1,good; + BIGNUM *d,*dd,*tmp,*d1,*d2,*n1; + BIGNUM *mont_one,*mont_n1,*mont_a; d1=ctx->bn[ctx->tos]; d2=ctx->bn[ctx->tos+1]; - x=ctx->bn[ctx->tos+2]; - n1=ctx->bn[ctx->tos+3]; - inv=ctx->bn[ctx->tos+4]; - ctx->tos+=5; + n1=ctx->bn[ctx->tos+2]; + ctx->tos+=3; + + mont_one=ctx2->bn[ctx2->tos]; + mont_n1=ctx2->bn[ctx2->tos+1]; + mont_a=ctx2->bn[ctx2->tos+2]; + ctx2->tos+=3; d=d1; dd=d2; @@ -220,34 +240,29 @@ BN_CTX *ctx; if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */ k=BN_num_bits(n1); - /* i=BN_num_bits(n); */ -#ifdef RECP_MUL_MOD - nb=BN_reciprocal(inv,n,ctx); /**/ - if (nb == -1) goto err; -#endif + if (!BN_to_montgomery(mont_one,BN_value_one(),mont,ctx2)) goto err; + if (!BN_to_montgomery(mont_n1,n1,mont,ctx2)) goto err; + if (!BN_to_montgomery(mont_a,a,mont,ctx2)) goto err; + BN_copy(d,mont_one); for (i=k-1; i>=0; i--) { - if (BN_copy(x,d) == NULL) goto err; -#ifndef RECP_MUL_MOD - if (!BN_mod_mul(dd,d,d,n,ctx)) goto err; -#else - if (!BN_mod_mul_reciprocal(dd,d,d,n,inv,nb,ctx)) goto err; -#endif - if ( BN_is_one(dd) && - !BN_is_one(x) && - (BN_cmp(x,n1) != 0)) + if ( (BN_cmp(d,mont_one) != 0) && + (BN_cmp(d,mont_n1) != 0)) + good=1; + else + good=0; + + BN_mod_mul_montgomery(dd,d,d,mont,ctx2); + + if (good && (BN_cmp(dd,mont_one) == 0)) { ret=1; goto err; } if (BN_is_bit_set(n1,i)) { -#ifndef RECP_MUL_MOD - if (!BN_mod_mul(d,dd,a,n,ctx)) goto err; -#else - if (!BN_mod_mul_reciprocal(d,dd,a,n,inv,nb,ctx)) goto err; -#endif + BN_mod_mul_montgomery(d,dd,mont_a,mont,ctx2); } else { @@ -256,12 +271,13 @@ BN_CTX *ctx; dd=tmp; } } - if (BN_is_one(d)) + if (BN_cmp(d,mont_one) == 0) i=0; else i=1; ret=i; err: - ctx->tos-=5; + ctx->tos-=3; + ctx2->tos-=3; return(ret); } @@ -387,3 +403,71 @@ err: return(ret); } +#if 0 +static int witness(a, n,ctx) +BIGNUM *a; +BIGNUM *n; +BN_CTX *ctx; + { + int k,i,nb,ret= -1; + BIGNUM *d,*dd,*tmp; + BIGNUM *d1,*d2,*x,*n1,*inv; + + d1=ctx->bn[ctx->tos]; + d2=ctx->bn[ctx->tos+1]; + x=ctx->bn[ctx->tos+2]; + n1=ctx->bn[ctx->tos+3]; + inv=ctx->bn[ctx->tos+4]; + ctx->tos+=5; + + d=d1; + dd=d2; + if (!BN_one(d)) goto err; + if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */ + k=BN_num_bits(n1); + + /* i=BN_num_bits(n); */ +#ifdef RECP_MUL_MOD + nb=BN_reciprocal(inv,n,ctx); /**/ + if (nb == -1) goto err; +#endif + + for (i=k-1; i>=0; i--) + { + if (BN_copy(x,d) == NULL) goto err; +#ifndef RECP_MUL_MOD + if (!BN_mod_mul(dd,d,d,n,ctx)) goto err; +#else + if (!BN_mod_mul_reciprocal(dd,d,d,n,inv,nb,ctx)) goto err; +#endif + if ( BN_is_one(dd) && + !BN_is_one(x) && + (BN_cmp(x,n1) != 0)) + { + ret=1; + goto err; + } + if (BN_is_bit_set(n1,i)) + { +#ifndef RECP_MUL_MOD + if (!BN_mod_mul(d,dd,a,n,ctx)) goto err; +#else + if (!BN_mod_mul_reciprocal(d,dd,a,n,inv,nb,ctx)) goto err; +#endif + } + else + { + tmp=d; + d=dd; + dd=tmp; + } + } + if (BN_is_one(d)) + i=0; + else i=1; + ret=i; +err: + ctx->tos-=5; + return(ret); + } +#endif diff --git a/crypto/bn/bn_prime.h b/crypto/bn/bn_prime.h index 1d6df587a8..6fce0210cd 100644 --- a/crypto/bn/bn_prime.h +++ b/crypto/bn/bn_prime.h @@ -1,5 +1,5 @@ /* crypto/bn/bn_prime.h */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written diff --git a/crypto/bn/bn_print.c b/crypto/bn/bn_print.c index 36bc0d1430..2bcc11c852 100644 --- a/crypto/bn/bn_print.c +++ b/crypto/bn/bn_print.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_print.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -65,7 +65,7 @@ static char *Hex="0123456789ABCDEF"; /* Must 'Free' the returned data */ -char *BN_bn2ascii(a) +char *BN_bn2hex(a) BIGNUM *a; { int i,j,v,z=0; @@ -75,7 +75,7 @@ BIGNUM *a; buf=(char *)Malloc(a->top*BN_BYTES*2+2); if (buf == NULL) { - BNerr(BN_F_BN_BN2ASCII,ERR_R_MALLOC_FAILURE); + BNerr(BN_F_BN_BN2HEX,ERR_R_MALLOC_FAILURE); goto err; } p=buf; @@ -100,7 +100,63 @@ err: return(buf); } -int BN_ascii2bn(bn,a) +/* Must 'Free' the returned data */ +char *BN_bn2dec(a) +BIGNUM *a; + { + int i=0,num; + char *buf=NULL; + char *p; + BIGNUM *t=NULL; + BN_ULONG *bn_data=NULL,*lp; + + i=BN_num_bits(a)*3; + num=(i/10+i/1000+3)+1; + bn_data=(BN_ULONG *)Malloc((num/BN_DEC_NUM+1)*sizeof(BN_ULONG)); + buf=(char *)Malloc(num+3); + if ((buf == NULL) || (bn_data == NULL)) + { + BNerr(BN_F_BN_BN2DEC,ERR_R_MALLOC_FAILURE); + goto err; + } + if ((t=BN_dup(a)) == NULL) goto err; + + p=buf; + lp=bn_data; + if (t->neg) *(p++)='-'; + if (t->top == 0) + { + *(p++)='0'; + *(p++)='\0'; + } + else + { + i=0; + while (!BN_is_zero(t)) + { + *lp=BN_div_word(t,BN_DEC_CONV); + lp++; + } + lp--; + /* We now have a series of blocks, BN_DEC_NUM chars + * in length, where the last one needs trucation. + * The blocks need to be reversed in order. */ + sprintf(p,BN_DEC_FMT1,*lp); + while (*p) p++; + while (lp != bn_data) + { + lp--; + sprintf(p,BN_DEC_FMT2,*lp); + while (*p) p++; + } + } +err: + if (bn_data != NULL) Free(bn_data); + if (t != NULL) BN_free(t); + return(buf); + } + +int BN_hex2bn(bn,a) BIGNUM **bn; char *a; { @@ -168,9 +224,68 @@ err: return(0); } +int BN_dec2bn(bn,a) +BIGNUM **bn; +char *a; + { + BIGNUM *ret=NULL; + BN_ULONG l=0; + int neg=0,i,j; + int num; + + if ((a == NULL) || (*a == '\0')) return(0); + if (*a == '-') { neg=1; a++; } + + for (i=0; isdigit(a[i]); i++) + ; + + num=i+neg; + if (bn == NULL) return(num); + + /* a is the start of the digets, and it is 'i' long. + * We chop it into BN_DEC_NUM digets at a time */ + if (*bn == NULL) + { + if ((ret=BN_new()) == NULL) return(0); + } + else + { + ret= *bn; + BN_zero(ret); + } + + /* i is the number of digests, a bit of an over expand; */ + if (bn_expand(ret,i*4) == NULL) goto err; + + j=BN_DEC_NUM-(i%BN_DEC_NUM); + if (j == BN_DEC_NUM) j=0; + l=0; + while (*a) + { + l*=10; + l+= *a-'0'; + a++; + if (++j == BN_DEC_NUM) + { + BN_mul_word(ret,BN_DEC_CONV); + BN_add_word(ret,l); + l=0; + j=0; + } + } + ret->neg=neg; + + bn_fix_top(ret); + *bn=ret; + return(num); +err: + if (*bn == NULL) BN_free(ret); + return(0); + } + #ifndef NO_BIO -#ifndef WIN16 +#ifndef NO_FP_API int BN_print_fp(fp, a) FILE *fp; BIGNUM *a; diff --git a/crypto/bn/bn_rand.c b/crypto/bn/bn_rand.c index e3530a5bf2..75b6b0493b 100644 --- a/crypto/bn/bn_rand.c +++ b/crypto/bn/bn_rand.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_rand.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written diff --git a/crypto/bn/bn_recp.c b/crypto/bn/bn_recp.c index fd9ca4dbf6..72cd69d3fc 100644 --- a/crypto/bn/bn_recp.c +++ b/crypto/bn/bn_recp.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_recp.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written diff --git a/crypto/bn/bn_shift.c b/crypto/bn/bn_shift.c index d711887373..944bf1794b 100644 --- a/crypto/bn/bn_shift.c +++ b/crypto/bn/bn_shift.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_shift.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -70,12 +70,12 @@ BIGNUM *a; if (r != a) { r->neg=a->neg; - if (bn_expand(r,(a->top+1)*BN_BITS2) == NULL) return(0); + if (bn_wexpand(r,a->top+1) == NULL) return(0); r->top=a->top; } else { - if (bn_expand(r,(a->top+1)*BN_BITS2) == NULL) return(0); + if (bn_wexpand(r,a->top+1) == NULL) return(0); } ap=a->d; rp=r->d; @@ -108,7 +108,7 @@ BIGNUM *a; } if (a != r) { - if (bn_expand(r,a->top*BN_BITS2) == NULL) return(0); + if (bn_wexpand(r,a->top) == NULL) return(0); r->top=a->top; r->neg=a->neg; } @@ -135,7 +135,7 @@ int n; BN_ULONG l; r->neg=a->neg; - if (bn_expand(r,(a->top*BN_BITS2)+n) == NULL) return(0); + if (bn_wexpand(r,a->top+(n/BN_BITS2)+1) == NULL) return(0); nw=n/BN_BITS2; lb=n%BN_BITS2; rb=BN_BITS2-lb; @@ -180,7 +180,7 @@ int n; if (r != a) { r->neg=a->neg; - if (bn_expand(r,(a->top-nw+1)*BN_BITS2) == NULL) return(0); + if (bn_wexpand(r,a->top-nw+1) == NULL) return(0); } f= &(a->d[nw]); diff --git a/crypto/bn/bn_sqr.c b/crypto/bn/bn_sqr.c index 4c3f0a0986..a8464610e5 100644 --- a/crypto/bn/bn_sqr.c +++ b/crypto/bn/bn_sqr.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_sqr.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -69,7 +69,7 @@ BN_CTX *ctx; { int i,j,max,al; BIGNUM *tmp; - BN_ULONG *ap,*rp,c; + BN_ULONG *ap,*rp; tmp=ctx->bn[ctx->tos]; @@ -81,8 +81,8 @@ BN_CTX *ctx; } max=(al*2); - if (bn_expand(r,max*BN_BITS2) == NULL) return(0); - if (bn_expand(tmp,max*BN_BITS2) == NULL) return(0); + if (bn_wexpand(r,1+max) == NULL) return(0); + if (bn_wexpand(tmp,1+max) == NULL) return(0); r->neg=0; @@ -95,7 +95,7 @@ BN_CTX *ctx; if (--j > 0) { ap++; - rp[j]=bn_mul_word(rp,ap,j,ap[-1]); + rp[j]=bn_mul_words(rp,ap,j,ap[-1]); rp+=2; } @@ -103,56 +103,17 @@ BN_CTX *ctx; { j--; ap++; - rp[j]=bn_mul_add_word(rp,ap,j,ap[-1]); + rp[j]=bn_mul_add_words(rp,ap,j,ap[-1]); rp+=2; } - /* inlined shift, 2 words at once */ - j=max; - rp=r->d; - c=0; - for (i=0; i<j; i++) - { - BN_ULONG t; + bn_add_words(r->d,r->d,r->d,max); - t= *rp; - *(rp++)=((t<<1)|c)&BN_MASK2; - c=(t & BN_TBIT)?1:0; - -#if 0 - t= *rp; - *(rp++)=((t<<1)|c)&BN_MASK2; - c=(t & BN_TBIT)?1:0; -#endif - } - /* there will not be a carry */ + /* There will not be a carry */ bn_sqr_words(tmp->d,a->d,al); - /* inlined add */ - ap=tmp->d; - rp=r->d; - c=0; - j=max; - for (i=0; i<j; i++) - { - BN_ULONG t1,t2; - - t1= *(ap++); - t2= *rp; - if (c) - { - c=(t2 >= ((~t1)&BN_MASK2)); - t2=(t1+t2+1)&BN_MASK2; - } - else - { - t2=(t1+t2)&BN_MASK2; - c=(t2<t1); - } - *(rp++)=t2; - } - /* there will be no carry */ + bn_add_words(r->d,r->d,tmp->d,max); r->top=max; if (r->d[max-1] == 0) r->top--; diff --git a/crypto/bn/bn_sub.c b/crypto/bn/bn_sub.c index b0febc3421..bba80f8afb 100644 --- a/crypto/bn/bn_sub.c +++ b/crypto/bn/bn_sub.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_sub.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -87,12 +87,12 @@ BIGNUM *b; if (carry) { carry=(t1 <= t2); - t1=(t1-t2-1); + t1=(t1-t2-1)&BN_MASK2; } else { carry=(t1 < t2); - t1=(t1-t2); + t1=(t1-t2)&BN_MASK2; } #if defined(IRIX_CC_BUG) && !defined(LINT) dummy=t1; @@ -110,9 +110,12 @@ BIGNUM *b; if (t1 > t2) break; } } +#if 0 memcpy(rp,ap,sizeof(*rp)*(max-i)); -/* for (; i<max; i++) - *(rp++)= *(ap++);*/ +#else + for (; i<max; i++) + *(rp++)= *(ap++); +#endif r->top=max; bn_fix_top(r); @@ -146,8 +149,9 @@ BIGNUM *b; if (add) { - i=(a->top > b->top); - if (bn_expand(r,(((i)?a->top:b->top)+1)*BN_BITS2) == NULL) + /* As a fast max size, do a a->top | b->top */ + i=(a->top | b->top)+1; + if (bn_wexpand(r,i) == NULL) return(0); if (i) bn_qadd(r,a,b); @@ -160,7 +164,7 @@ BIGNUM *b; /* We are actually doing a - b :-) */ max=(a->top > b->top)?a->top:b->top; - if (bn_expand(r,max*BN_BITS2) == NULL) return(0); + if (bn_wexpand(r,max) == NULL) return(0); if (BN_ucmp(a,b) < 0) { bn_qsub(r,b,a); diff --git a/crypto/bn/bn_word.c b/crypto/bn/bn_word.c index b61ddd95ce..4b3d0f011d 100644 --- a/crypto/bn/bn_word.c +++ b/crypto/bn/bn_word.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_word.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -71,11 +71,12 @@ unsigned long w; #endif int i; + w&=BN_MASK2; for (i=a->top-1; i>=0; i--) { #ifndef BN_LLONG - ret=((ret<<BN_BITS4)|((a->d[i]>>BN_BITS4)&BN_MASK2l))%(int)w; - ret=((ret<<BN_BITS4)|(a->d[i]&BN_MASK2l))%(int)w; + ret=((ret<<BN_BITS4)|((a->d[i]>>BN_BITS4)&BN_MASK2l))%(unsigned long)w; + ret=((ret<<BN_BITS4)|(a->d[i]&BN_MASK2l))%(unsigned long)w; #else ret=(BN_ULLONG)(((ret<<(BN_ULLONG)BN_BITS2)|a->d[i])% (BN_ULLONG)w); @@ -93,18 +94,15 @@ unsigned long w; if (a->top == 0) return(0); ret=0; + w&=BN_MASK2; for (i=a->top-1; i>=0; i--) { -#ifndef BN_LLONG - ret=((ret<<BN_BITS4)|((a->d[i]>>BN_BITS4)&BN_MASK2l))%(int)w; - ret=((ret<<BN_BITS4)|(a->d[i]&BN_MASK2l))%(int)w; -#else - BN_ULLONG ll; - - ll=((BN_ULLONG)ret<<(BN_ULONG)BN_BITS2)|a->d[i]; - a->d[i]=(BN_ULONG)(ll/w); - ret=(BN_ULONG)(ll%w); -#endif + BN_ULONG l,d; + + l=a->d[i]; + d=bn_div64(ret,l,w); + ret=(l-((d*w)&BN_MASK2))&BN_MASK2; + a->d[i]=d; } if (a->d[a->top-1] == 0) a->top--; @@ -118,7 +116,16 @@ unsigned long w; BN_ULONG l; int i; - if (bn_expand(a,a->top*BN_BITS2+1) == NULL) return(0); + if (a->neg) + { + a->neg=0; + i=BN_sub_word(a,w); + if (!BN_is_zero(a)) + a->neg=1; + return(i); + } + w&=BN_MASK2; + if (bn_wexpand(a,a->top+1) == NULL) return(0); i=0; for (;;) { @@ -135,21 +142,63 @@ unsigned long w; return(1); } -#ifdef undef -BN_ULONG *BN_mod_inverse_word(a) -BN_ULONG a; +int BN_sub_word(a, w) +BIGNUM *a; +unsigned long w; { - BN_ULONG A,B,X,Y,M,D,R,RET,T; - int sign,hight=1; + int i; - X=0; - Y=1; - A=0; - B=a; - sign=1; + if (a->neg) + { + a->neg=0; + i=BN_add_word(a,w); + a->neg=1; + return(i); + } - while (B != 0) + w&=BN_MASK2; + if ((a->top == 1) && (a->d[0] < w)) + { + a->d[0]=w-a->d[0]; + a->neg=1; + return(1); + } + i=0; + for (;;) { + if (a->d[i] >= w) + { + a->d[i]-=w; + break; + } + else + { + a->d[i]=(a->d[i]-w)&BN_MASK2; + i++; + w=1; + } + } + if ((a->d[i] == 0) && (i == (a->top-1))) + a->top--; + return(1); + } -#endif +int BN_mul_word(a,w) +BIGNUM *a; +unsigned long w; + { + BN_ULONG ll; + + w&=BN_MASK2; + if (a->top) + { + ll=bn_mul_words(a->d,a->d,a->top,w); + if (ll) + { + if (bn_wexpand(a,a->top+1) == NULL) return(0); + a->d[a->top++]=ll; + } + } + return(0); + } diff --git a/crypto/bn/bnspeed.c b/crypto/bn/bnspeed.c index 3b83a26dea..f7c2790fff 100644 --- a/crypto/bn/bnspeed.c +++ b/crypto/bn/bnspeed.c @@ -1,5 +1,5 @@ /* crypto/bn/bnspeed.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -58,6 +58,7 @@ /* most of this code has been pilfered from my libdes speed.c program */ +#define BASENUM 1000000 #undef PROG #define PROG bnspeed_main @@ -169,8 +170,8 @@ int s; } #define NUM_SIZES 5 -/*static int sizes[NUM_SIZES]={256,512,1024,2048};*/ -static int sizes[NUM_SIZES]={59,179,299,419,539}; +static int sizes[NUM_SIZES]={128,256,512,1024,2048}; +/*static int sizes[NUM_SIZES]={59,179,299,419,539}; */ void do_mul(BIGNUM *r,BIGNUM *a,BIGNUM *b,BN_CTX *ctx); @@ -198,34 +199,41 @@ BN_CTX *ctx; { int i,j,k; double tm; + long num; for (i=0; i<NUM_SIZES; i++) { + num=BASENUM; + if (i) num/=(i*3); BN_rand(a,sizes[i],1,0); for (j=i; j<NUM_SIZES; j++) { BN_rand(b,sizes[j],1,0); Time_F(START); - for (k=0; k<100000; k++) + for (k=0; k<num; k++) BN_mul(r,b,a); tm=Time_F(STOP); - printf("mul %3d x %3d -> %7.4f\n",sizes[i],sizes[j],tm/10.0); + printf("mul %4d x %4d -> %8.3fms\n",sizes[i],sizes[j],tm*1000.0/num); } } for (i=0; i<NUM_SIZES; i++) { + num=BASENUM; + if (i) num/=(i*3); BN_rand(a,sizes[i],1,0); Time_F(START); - for (k=0; k<100000; k++) + for (k=0; k<num; k++) BN_sqr(r,a,ctx); tm=Time_F(STOP); - printf("sqr %3d x %3d -> %7.4f\n",sizes[i],sizes[i],tm/10.0); + printf("sqr %4d x %4d -> %8.3fms\n",sizes[i],sizes[i],tm*1000.0/num); } for (i=0; i<NUM_SIZES; i++) { - BN_rand(a,sizes[i],1,0); + num=BASENUM/10; + if (i) num/=(i*3); + BN_rand(a,sizes[i]-1,1,0); for (j=i; j<NUM_SIZES; j++) { BN_rand(b,sizes[j],1,0); @@ -233,7 +241,7 @@ BN_CTX *ctx; for (k=0; k<100000; k++) BN_div(r, NULL, b, a,ctx); tm=Time_F(STOP); - printf("div %3d / %3d -> %7.4f\n",sizes[j],sizes[i],tm/10.0); + printf("div %4d / %4d -> %8.3fms\n",sizes[j],sizes[i]-1,tm*1000.0/num); } } } diff --git a/crypto/bn/bntest.c b/crypto/bn/bntest.c index 7a2f0b8d6d..9ebd68b429 100644 --- a/crypto/bn/bntest.c +++ b/crypto/bn/bntest.c @@ -1,5 +1,5 @@ /* crypto/bn/bntest.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -59,15 +59,17 @@ #include <stdio.h> #include <stdlib.h> #include <string.h> -#ifdef WIN16 -#define APPS_WIN16 -#endif +#include "e_os.h" #include "bio.h" #include "bn.h" #include "rand.h" #include "x509.h" #include "err.h" +#ifdef WINDOWS +#include "../bio/bss_file.c" +#endif + #ifndef NOPROTO int test_add (BIO *bp); int test_sub (BIO *bp); @@ -102,9 +104,9 @@ int rand_neg(); static int results=0; -#ifdef WIN16 +#ifdef NO_STDIO #define APPS_WIN16 -#include "../bio/bss_file.c" +#include "bss_file.c" #endif int main(argc,argv) @@ -178,20 +180,20 @@ char *argv[]; if (!test_rshift(out)) goto err; fflush(stdout); - fprintf(stderr,"test BN_div\n"); - if (!test_div(out,ctx)) goto err; - fflush(stdout); - - fprintf(stderr,"test BN_mod\n"); - if (!test_mod(out,ctx)) goto err; + fprintf(stderr,"test BN_sqr\n"); + if (!test_sqr(out,ctx)) goto err; fflush(stdout); fprintf(stderr,"test BN_mul\n"); if (!test_mul(out)) goto err; fflush(stdout); - fprintf(stderr,"test BN_sqr\n"); - if (!test_sqr(out,ctx)) goto err; + fprintf(stderr,"test BN_div\n"); + if (!test_div(out,ctx)) goto err; + fflush(stdout); + + fprintf(stderr,"test BN_mod\n"); + if (!test_mod(out,ctx)) goto err; fflush(stdout); fprintf(stderr,"test BN_mod_mul\n"); diff --git a/crypto/bn/expspeed.c b/crypto/bn/expspeed.c new file mode 100644 index 0000000000..344f883d35 --- /dev/null +++ b/crypto/bn/expspeed.c @@ -0,0 +1,230 @@ +/* crypto/bn/expspeed.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 */ + +#define BASENUM 5000 +#undef PROG +#define PROG bnspeed_main + +#include <stdio.h> +#include <stdlib.h> +#include <signal.h> +#include <string.h> +#include "crypto.h" +#include "err.h" + +#ifndef MSDOS +#define TIMES +#endif + +#ifndef VMS +#ifndef _IRIX +#include <time.h> +#endif +#ifdef TIMES +#include <sys/types.h> +#include <sys/times.h> +#endif +#else /* VMS */ +#include <types.h> +struct tms { + time_t tms_utime; + time_t tms_stime; + time_t tms_uchild; /* I dunno... */ + time_t tms_uchildsys; /* so these names are a guess :-) */ + } +#endif +#ifndef TIMES +#include <sys/timeb.h> +#endif + +#ifdef sun +#include <limits.h> +#include <sys/param.h> +#endif + +#include "bn.h" +#include "x509.h" + +/* The following if from times(3) man page. It may need to be changed */ +#ifndef HZ +# ifndef CLK_TCK +# ifndef _BSD_CLK_TCK_ /* FreeBSD hack */ +# ifndef VMS +# define HZ 100.0 +# else /* VMS */ +# define HZ 100.0 +# endif +# else /* _BSD_CLK_TCK_ */ +# define HZ ((double)_BSD_CLK_TCK_) +# endif +# else /* CLK_TCK */ +# define HZ ((double)CLK_TCK) +# endif +#endif + +#undef BUFSIZE +#define BUFSIZE ((long)1024*8) +int run=0; + +#ifndef NOPROTO +static double Time_F(int s); +#else +static double Time_F(); +#endif + +#define START 0 +#define STOP 1 + +static double Time_F(s) +int s; + { + double ret; +#ifdef TIMES + static struct tms tstart,tend; + + if (s == START) + { + times(&tstart); + return(0); + } + else + { + times(&tend); + ret=((double)(tend.tms_utime-tstart.tms_utime))/HZ; + return((ret < 1e-3)?1e-3:ret); + } +#else /* !times() */ + static struct timeb tstart,tend; + long i; + + if (s == START) + { + ftime(&tstart); + return(0); + } + else + { + ftime(&tend); + i=(long)tend.millitm-(long)tstart.millitm; + ret=((double)(tend.time-tstart.time))+((double)i)/1000.0; + return((ret < 0.001)?0.001:ret); + } +#endif + } + +#define NUM_SIZES 6 +static int sizes[NUM_SIZES]={256,512,1024,2048,4096,8192}; +static int mul_c[NUM_SIZES]={8*8*8*8*8,8*8*8*8,8*8*8,8*8,8,1}; +/*static int sizes[NUM_SIZES]={59,179,299,419,539}; */ + +void do_mul_exp(BIGNUM *r,BIGNUM *a,BIGNUM *b,BIGNUM *c,BN_CTX *ctx); + +int main(argc,argv) +int argc; +char **argv; + { + BN_CTX *ctx; + BIGNUM *a,*b,*c,*r; + + ctx=BN_CTX_new(); + a=BN_new(); + b=BN_new(); + c=BN_new(); + r=BN_new(); + + do_mul_exp(r,a,b,c,ctx); + } + +void do_mul_exp(r,a,b,c,ctx) +BIGNUM *r; +BIGNUM *a; +BIGNUM *b; +BIGNUM *c; +BN_CTX *ctx; + { + int i,k; + double tm; + long num; + BN_MONT_CTX m; + + memset(&m,0,sizeof(m)); + + num=BASENUM; + for (i=0; i<NUM_SIZES; i++) + { + BN_rand(a,sizes[i],1,0); + BN_rand(b,sizes[i],1,0); + BN_rand(c,sizes[i],1,1); + BN_mod(a,a,c,ctx); + BN_mod(b,b,c,ctx); + + BN_MONT_CTX_set(&m,c,ctx); + + Time_F(START); + for (k=0; k<num; k++) + BN_mod_exp_mont(r,a,b,c,ctx,&m); + tm=Time_F(STOP); + printf("mul %4d ^ %4d %% %d -> %8.3fms %5.1f\n",sizes[i],sizes[i],sizes[i],tm*1000.0/num,tm*mul_c[i]/num); + num/=7; + if (num <= 0) num=1; + } + + } + diff --git a/crypto/bn/exptest.c b/crypto/bn/exptest.c index 4880df1116..67dc95d726 100644 --- a/crypto/bn/exptest.c +++ b/crypto/bn/exptest.c @@ -1,5 +1,5 @@ /* crypto/bn/exptest.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -63,6 +63,9 @@ #include "bn.h" #include "rand.h" #include "err.h" +#ifdef WINDOWS +#include "../bio/bss_file.c" +#endif #define NUM_BITS (BN_BITS*2) @@ -87,11 +90,8 @@ char *argv[]; (a == NULL) || (b == NULL)) goto err; -#ifdef WIN16 - out=BIO_new(BIO_s_file_internal_w16()); -#else out=BIO_new(BIO_s_file()); -#endif + if (out == NULL) exit(1); BIO_set_fp(out,stdout,BIO_NOCLOSE); @@ -112,7 +112,7 @@ char *argv[]; BN_mod(a,a,m,ctx); BN_mod(b,b,m,ctx); - ret=BN_mod_exp_mont(r_mont,a,b,m,ctx); + ret=BN_mod_exp_mont(r_mont,a,b,m,ctx,NULL); if (ret <= 0) { printf("BN_mod_exp_mont() problems\n"); exit(1); } |