diff options
Diffstat (limited to 'crypto/bn')
| -rw-r--r-- | crypto/bn/Makefile.ssl | 28 | ||||
| -rw-r--r-- | crypto/bn/asm/vms.mar | 690 | ||||
| -rw-r--r-- | crypto/bn/bn.h | 144 | ||||
| -rw-r--r-- | crypto/bn/bn_asm.c | 22 | ||||
| -rw-r--r-- | crypto/bn/bn_ctx.c | 6 | ||||
| -rw-r--r-- | crypto/bn/bn_div.c | 53 | ||||
| -rw-r--r-- | crypto/bn/bn_err.c | 8 | ||||
| -rw-r--r-- | crypto/bn/bn_exp.c | 127 | ||||
| -rw-r--r-- | crypto/bn/bn_exp2.c | 27 | ||||
| -rw-r--r-- | crypto/bn/bn_gcd.c | 238 | ||||
| -rw-r--r-- | crypto/bn/bn_lcl.h | 17 | ||||
| -rw-r--r-- | crypto/bn/bn_lib.c | 329 | ||||
| -rw-r--r-- | crypto/bn/bn_mont.c | 13 | ||||
| -rw-r--r-- | crypto/bn/bn_mpi.c | 2 | ||||
| -rw-r--r-- | crypto/bn/bn_mul.c | 482 | ||||
| -rw-r--r-- | crypto/bn/bn_prime.c | 17 | ||||
| -rw-r--r-- | crypto/bn/bn_print.c | 2 | ||||
| -rw-r--r-- | crypto/bn/bn_rand.c | 28 | ||||
| -rw-r--r-- | crypto/bn/bn_recp.c | 20 | ||||
| -rw-r--r-- | crypto/bn/bn_shift.c | 13 | ||||
| -rw-r--r-- | crypto/bn/bn_sqr.c | 16 | ||||
| -rw-r--r-- | crypto/bn/bn_sqrt.c | 84 | ||||
| -rw-r--r-- | crypto/bn/bntest.c | 288 | ||||
| -rw-r--r-- | crypto/bn/expspeed.c | 150 |
24 files changed, 1724 insertions, 1080 deletions
diff --git a/crypto/bn/Makefile.ssl b/crypto/bn/Makefile.ssl index ad36267e26..dd5c35bf64 100644 --- a/crypto/bn/Makefile.ssl +++ b/crypto/bn/Makefile.ssl @@ -35,15 +35,15 @@ TEST=bntest.c exptest.c APPS= LIB=$(TOP)/libcrypto.a -LIBSRC= bn_add.c bn_div.c bn_exp.c bn_lib.c bn_ctx.c bn_mul.c \ +LIBSRC= bn_add.c bn_div.c bn_exp.c bn_lib.c bn_ctx.c bn_mul.c bn_mod.c \ bn_print.c bn_rand.c bn_shift.c bn_word.c bn_blind.c \ - bn_gcd.c bn_prime.c bn_err.c bn_sqr.c bn_asm.c bn_recp.c bn_mont.c \ - bn_mpi.c bn_exp2.c + bn_kron.c bn_sqrt.c bn_gcd.c bn_prime.c bn_err.c bn_sqr.c bn_asm.c \ + bn_recp.c bn_mont.c bn_mpi.c bn_exp2.c -LIBOBJ= bn_add.o bn_div.o bn_exp.o bn_lib.o bn_ctx.o bn_mul.o \ +LIBOBJ= bn_add.o bn_div.o bn_exp.o bn_lib.o bn_ctx.o bn_mul.o bn_mod.o \ bn_print.o bn_rand.o bn_shift.o bn_word.o bn_blind.o \ - bn_gcd.o bn_prime.o bn_err.o bn_sqr.o $(BN_ASM) bn_recp.o bn_mont.o \ - bn_mpi.o bn_exp2.o + bn_kron.o bn_sqrt.o bn_gcd.o bn_prime.o bn_err.o bn_sqr.o $(BN_ASM) \ + bn_recp.o bn_mont.o bn_mpi.o bn_exp2.o SRC= $(LIBSRC) @@ -230,6 +230,8 @@ bn_gcd.o: ../../include/openssl/err.h ../../include/openssl/lhash.h bn_gcd.o: ../../include/openssl/opensslconf.h ../../include/openssl/opensslv.h bn_gcd.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h bn_gcd.o: ../../include/openssl/symhacks.h ../cryptlib.h bn_lcl.h +bn_kron.o: ../../include/openssl/bn.h ../../include/openssl/opensslconf.h +bn_kron.o: bn_lcl.h bn_lib.o: ../../include/openssl/bio.h ../../include/openssl/bn.h bn_lib.o: ../../include/openssl/buffer.h ../../include/openssl/crypto.h bn_lib.o: ../../include/openssl/e_os.h ../../include/openssl/e_os2.h @@ -237,6 +239,13 @@ bn_lib.o: ../../include/openssl/err.h ../../include/openssl/lhash.h bn_lib.o: ../../include/openssl/opensslconf.h ../../include/openssl/opensslv.h bn_lib.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h bn_lib.o: ../../include/openssl/symhacks.h ../cryptlib.h bn_lcl.h +bn_mod.o: ../../include/openssl/bio.h ../../include/openssl/bn.h +bn_mod.o: ../../include/openssl/buffer.h ../../include/openssl/crypto.h +bn_mod.o: ../../include/openssl/e_os.h ../../include/openssl/e_os2.h +bn_mod.o: ../../include/openssl/err.h ../../include/openssl/lhash.h +bn_mod.o: ../../include/openssl/opensslconf.h ../../include/openssl/opensslv.h +bn_mod.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h +bn_mod.o: ../../include/openssl/symhacks.h ../cryptlib.h bn_lcl.h bn_mont.o: ../../include/openssl/bio.h ../../include/openssl/bn.h bn_mont.o: ../../include/openssl/buffer.h ../../include/openssl/crypto.h bn_mont.o: ../../include/openssl/e_os.h ../../include/openssl/e_os2.h @@ -304,6 +313,13 @@ bn_sqr.o: ../../include/openssl/err.h ../../include/openssl/lhash.h bn_sqr.o: ../../include/openssl/opensslconf.h ../../include/openssl/opensslv.h bn_sqr.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h bn_sqr.o: ../../include/openssl/symhacks.h ../cryptlib.h bn_lcl.h +bn_sqrt.o: ../../include/openssl/bio.h ../../include/openssl/bn.h +bn_sqrt.o: ../../include/openssl/buffer.h ../../include/openssl/crypto.h +bn_sqrt.o: ../../include/openssl/e_os.h ../../include/openssl/e_os2.h +bn_sqrt.o: ../../include/openssl/err.h ../../include/openssl/lhash.h +bn_sqrt.o: ../../include/openssl/opensslconf.h ../../include/openssl/opensslv.h +bn_sqrt.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h +bn_sqrt.o: ../../include/openssl/symhacks.h ../cryptlib.h bn_lcl.h bn_word.o: ../../include/openssl/bio.h ../../include/openssl/bn.h bn_word.o: ../../include/openssl/buffer.h ../../include/openssl/crypto.h bn_word.o: ../../include/openssl/e_os.h ../../include/openssl/e_os2.h diff --git a/crypto/bn/asm/vms.mar b/crypto/bn/asm/vms.mar index ac9d57d7b0..754ab5347a 100644 --- a/crypto/bn/asm/vms.mar +++ b/crypto/bn/asm/vms.mar @@ -162,442 +162,236 @@ n=12 ;(AP) n by value (input) movl #1,r0 ; return SS$_NORMAL ret - .title (generated) - - .psect code,nowrt - -.entry BN_DIV_WORDS,^m<r2,r3,r4,r5,r6,r7,r8,r9,r10> - subl2 #4,sp - - clrl r9 - movl #2,r8 - - tstl 12(ap) - bneq noname.2 - mnegl #1,r10 - brw noname.3 - tstl r0 - nop -noname.2: - - pushl 12(ap) - calls #1,BN_NUM_BITS_WORD - movl r0,r7 - - cmpl r7,#32 - beql noname.4 - ashl r7,#1,r2 - cmpl 4(ap),r2 - blequ noname.4 - - pushl r7 - calls #1,BN_DIV_WORDS_ABORT -noname.4: - - subl3 r7,#32,r7 - - movl 12(ap),r2 - cmpl 4(ap),r2 - blssu noname.5 - subl2 r2,4(ap) -noname.5: - - tstl r7 - beql noname.6 - - ashl r7,r2,12(ap) - - ashl r7,4(ap),r4 - subl3 r7,#32,r3 - subl3 r3,#32,r2 - extzv r3,r2,8(ap),r2 - bisl3 r4,r2,4(ap) - - ashl r7,8(ap),8(ap) -noname.6: - - bicl3 #65535,12(ap),r2 - extzv #16,#16,r2,r5 - - bicl3 #-65536,12(ap),r6 - -noname.7: - - moval 4(ap),r2 - movzwl 2(r2),r0 - cmpl r0,r5 - bneq noname.8 - - movzwl #65535,r4 - brb noname.9 -noname.8: - - clrl r1 - movl (r2),r0 - movl r5,r2 - bgeq vcg.1 - cmpl r2,r0 - bgtru vcg.2 - incl r1 - brb vcg.2 - nop -vcg.1: - ediv r2,r0,r1,r0 -vcg.2: - movl r1,r4 -noname.9: - -noname.10: - - mull3 r5,r4,r0 - subl3 r0,4(ap),r3 - - bicl3 #65535,r3,r0 - bneq noname.13 - mull3 r6,r4,r2 - ashl #16,r3,r1 - bicl3 #65535,8(ap),r0 - extzv #16,#16,r0,r0 - addl2 r0,r1 - cmpl r2,r1 - bgtru noname.12 -noname.11: - - brb noname.13 - nop -noname.12: - - decl r4 - brb noname.10 -noname.13: - - mull3 r5,r4,r1 - - mull3 r6,r4,r0 - - extzv #16,#16,r0,r3 - - ashl #16,r0,r2 - bicl3 #65535,r2,r0 - - addl2 r3,r1 - - moval 8(ap),r3 - cmpl (r3),r0 - bgequ noname.15 - incl r1 -noname.15: - - subl2 r0,(r3) - - cmpl 4(ap),r1 - bgequ noname.16 - - addl2 12(ap),4(ap) - - decl r4 -noname.16: + .title vax_bn_div_words unsigned divide +; +; Richard Levitte 20-Nov-2000 +; +; ULONG bn_div_words(ULONG h, ULONG l, ULONG d) +; { +; return ((ULONG)((((ULLONG)h)<<32)|l) / (ULLONG)d); +; } +; +; Using EDIV would be very easy, if it didn't do signed calculations. +; Therefore, som extra things have to happen around it. The way to +; handle that is to shift all operands right one step (basically dividing +; them by 2) and handle the different cases depending on what the lowest +; bit of each operand was. +; +; To start with, let's define the following: +; +; a' = l & 1 +; a2 = <h,l> >> 1 # UNSIGNED shift! +; b' = d & 1 +; b2 = d >> 1 # UNSIGNED shift! +; +; Now, use EDIV to calculate a quotient and a remainder: +; +; q'' = a2/b2 +; r'' = a2 - q''*b2 +; +; If b' is 0, the quotient is already correct, we just need to adjust the +; remainder: +; +; if (b' == 0) +; { +; r = 2*r'' + a' +; q = q'' +; } +; +; If b' is 1, we need to do other adjustements. The first thought is the +; following (note that r' will not always have the right value, but an +; adjustement follows further down): +; +; if (b' == 1) +; { +; q' = q'' +; r' = a - q'*b +; +; However, one can note the folowing relationship: +; +; r'' = a2 - q''*b2 +; => 2*r'' = 2*a2 - 2*q''*b2 +; = { a = 2*a2 + a', b = 2*b2 + b' = 2*b2 + 1, +; q' = q'' } +; = a - a' - q'*(b - 1) +; = a - q'*b - a' + q' +; = r' - a' + q' +; => r' = 2*r'' - q' + a' +; +; This enables us to use r'' instead of discarding and calculating another +; modulo: +; +; if (b' == 1) +; { +; q' = q'' +; r' = (r'' << 1) - q' + a' +; +; Now, all we have to do is adjust r', because it might be < 0: +; +; while (r' < 0) +; { +; r' = r' + b +; q' = q' - 1 +; } +; } +; +; return q' - subl2 r1,4(ap) +h=4 ;(AP) h by value (input) +l=8 ;(AP) l by value (input) +d=12 ;(AP) d by value (input) - decl r8 - beql noname.18 -noname.17: +;aprim=r5 +;a2=r6 +;a20=r6 +;a21=r7 +;bprim=r8 +;b2=r9 +;qprim=r10 ; initially used as q'' +;rprim=r11 ; initially used as r'' - ashl #16,r4,r9 - ashl #16,4(ap),r2 - movzwl 2(r3),r0 - bisl2 r0,r2 - bicl3 #0,r2,4(ap) + .psect code,nowrt - bicl3 #-65536,(r3),r0 - ashl #16,r0,(r3) - brw noname.7 - nop -noname.18: +.entry bn_div_words,^m<r2,r3,r4,r5,r6,r7,r8,r9,r10,r11> + movl l(ap),r2 + movl h(ap),r3 + movl d(ap),r4 - bisl2 r4,r9 + movl #0,r5 + movl #0,r8 + movl #0,r0 - movl r9,r10 + rotl #-1,r2,r6 ; a20 = l >> 1 (almost) + rotl #-1,r3,r7 ; a21 = h >> 1 (almost) + rotl #-1,r4,r9 ; b2 = d >> 1 (almost) -noname.3: + tstl r6 + bgeq 1$ + xorl2 #^X80000000,r6 ; fixup a20 so highest bit is 0 + incl r5 ; a' = 1 +1$: + tstl r7 + bgeq 2$ + xorl2 #^X80000000,r6 ; fixup a20 so highest bit is 1, + ; since that's what was lowest in a21 + xorl2 #^X80000000,r7 ; fixup a21 so highest bit is 1 +2$: + tstl r9 + bgeq 666$ ; Uh-oh, the divisor is 0... + bgtr 3$ + xorl2 #^X80000000,r9 ; fixup b2 so highest bit is 1 + incl r8 +3$: + tstl r9 + bneq 4$ ; if b2 is 0, we know that bprim is 1 + tstl r7 + bneq 666$ ; if higher half isn't 0, we overflow + movl r0,r6 ; otherwise, we have our result + brb 42$ +4$: + ediv r9,r6,r10,r11 + + tstl r8 + bneq 5$ ; If b' != 0, go to the other part +; addl3 r11,r11,r1 +; addl2 r5,r1 + brb 42$ +5$: + ashl #1,r11,r11 + subl2 r10,r11 + addl2 r5,r11 + bgeq 7$ +6$: + decl r10 + addl2 r4,r11 + blss 6$ +7$: +; movl r11,r1 +42$: movl r10,r0 - ret - tstl r0 - +666$: + ret - .psect code,nowrt - -.entry BN_ADD_WORDS,^m<r2,r3,r4,r5,r6,r7> - - tstl 16(ap) - bgtr noname.21 - clrl r7 - brw noname.22 -noname.21: - - clrl r4 - - tstl r0 -noname.23: - - movl 8(ap),r6 - addl3 r4,(r6),r2 - - bicl2 #0,r2 - - clrl r0 - cmpl r2,r4 - bgequ vcg.3 - incl r0 -vcg.3: - movl r0,r4 - - movl 12(ap),r5 - addl3 (r5),r2,r1 - bicl2 #0,r1 - - clrl r0 - cmpl r1,r2 - bgequ vcg.4 - incl r0 -vcg.4: - addl2 r0,r4 - - movl 4(ap),r3 - movl r1,(r3) - - decl 16(ap) - bgtr gen.1 - brw noname.25 -gen.1: -noname.24: - - addl3 r4,4(r6),r2 - - bicl2 #0,r2 - - clrl r0 - cmpl r2,r4 - bgequ vcg.5 - incl r0 -vcg.5: - movl r0,r4 - - addl3 4(r5),r2,r1 - bicl2 #0,r1 - - clrl r0 - cmpl r1,r2 - bgequ vcg.6 - incl r0 -vcg.6: - addl2 r0,r4 - - movl r1,4(r3) - - decl 16(ap) - bleq noname.25 -noname.26: - - addl3 r4,8(r6),r2 - - bicl2 #0,r2 - - clrl r0 - cmpl r2,r4 - bgequ vcg.7 - incl r0 -vcg.7: - movl r0,r4 - - addl3 8(r5),r2,r1 - bicl2 #0,r1 - - clrl r0 - cmpl r1,r2 - bgequ vcg.8 - incl r0 -vcg.8: - addl2 r0,r4 - - movl r1,8(r3) - - decl 16(ap) - bleq noname.25 -noname.27: - - addl3 r4,12(r6),r2 - - bicl2 #0,r2 - - clrl r0 - cmpl r2,r4 - bgequ vcg.9 - incl r0 -vcg.9: - movl r0,r4 - - addl3 12(r5),r2,r1 - bicl2 #0,r1 - - clrl r0 - cmpl r1,r2 - bgequ vcg.10 - incl r0 -vcg.10: - addl2 r0,r4 + .title vax_bn_add_words unsigned add of two arrays +; +; Richard Levitte 20-Nov-2000 +; +; ULONG bn_add_words(ULONG r[], ULONG a[], ULONG b[], int n) { +; ULONG c = 0; +; int i; +; for (i = 0; i < n; i++) <c,r[i]> = a[i] + b[i] + c; +; return(c); +; } - movl r1,12(r3) +r=4 ;(AP) r by reference (output) +a=8 ;(AP) a by reference (input) +b=12 ;(AP) b by reference (input) +n=16 ;(AP) n by value (input) - decl 16(ap) - bleq noname.25 -noname.28: - addl3 #16,r6,8(ap) + .psect code,nowrt - addl3 #16,r5,12(ap) +.entry bn_add_words,^m<r2,r3,r4,r5,r6> - addl3 #16,r3,4(ap) - brw noname.23 - tstl r0 -noname.25: + moval @r(ap),r2 + moval @a(ap),r3 + moval @b(ap),r4 + movl n(ap),r5 ; assumed >0 by C code + clrl r0 ; c - movl r4,r7 + tstl r5 ; carry = 0 + bleq 666$ -noname.22: - movl r7,r0 - ret - nop +0$: + movl (r3)+,r6 ; carry untouched + adwc (r4)+,r6 ; carry used and touched + movl r6,(r2)+ ; carry untouched + sobgtr r5,0$ ; carry untouched + adwc #0,r0 +666$: + ret + .title vax_bn_sub_words unsigned add of two arrays +; +; Richard Levitte 20-Nov-2000 +; +; ULONG bn_sub_words(ULONG r[], ULONG a[], ULONG b[], int n) { +; ULONG c = 0; +; int i; +; for (i = 0; i < n; i++) <c,r[i]> = a[i] - b[i] - c; +; return(c); +; } -;r=4 ;(AP) -;a=8 ;(AP) -;b=12 ;(AP) -;n=16 ;(AP) n by value (input) +r=4 ;(AP) r by reference (output) +a=8 ;(AP) a by reference (input) +b=12 ;(AP) b by reference (input) +n=16 ;(AP) n by value (input) - .psect code,nowrt -.entry BN_SUB_WORDS,^m<r2,r3,r4,r5,r6,r7> + .psect code,nowrt - clrl r6 +.entry bn_sub_words,^m<r2,r3,r4,r5,r6> - tstl 16(ap) - bgtr noname.31 - clrl r7 - brw noname.32 - tstl r0 -noname.31: + moval @r(ap),r2 + moval @a(ap),r3 + moval @b(ap),r4 + movl n(ap),r5 ; assumed >0 by C code + clrl r0 ; c -noname.33: + tstl r5 ; carry = 0 + bleq 666$ - movl 8(ap),r5 - movl (r5),r1 - movl 12(ap),r4 - movl (r4),r2 - - movl 4(ap),r3 - subl3 r2,r1,r0 - subl2 r6,r0 - bicl3 #0,r0,(r3) - - cmpl r1,r2 - beql noname.34 - clrl r0 - cmpl r1,r2 - bgequ vcg.11 - incl r0 -vcg.11: - movl r0,r6 -noname.34: - - decl 16(ap) - bgtr gen.2 - brw noname.36 -gen.2: -noname.35: - - movl 4(r5),r2 - movl 4(r4),r1 - - subl3 r1,r2,r0 - subl2 r6,r0 - bicl3 #0,r0,4(r3) - - cmpl r2,r1 - beql noname.37 - clrl r0 - cmpl r2,r1 - bgequ vcg.12 - incl r0 -vcg.12: - movl r0,r6 -noname.37: - - decl 16(ap) - bleq noname.36 -noname.38: - - movl 8(r5),r1 - movl 8(r4),r2 - - subl3 r2,r1,r0 - subl2 r6,r0 - bicl3 #0,r0,8(r3) - - cmpl r1,r2 - beql noname.39 - clrl r0 - cmpl r1,r2 - bgequ vcg.13 - incl r0 -vcg.13: - movl r0,r6 -noname.39: - - decl 16(ap) - bleq noname.36 -noname.40: - - movl 12(r5),r1 - movl 12(r4),r2 - - subl3 r2,r1,r0 - subl2 r6,r0 - bicl3 #0,r0,12(r3) - - cmpl r1,r2 - beql noname.41 - clrl r0 - cmpl r1,r2 - bgequ vcg.14 - incl r0 -vcg.14: - movl r0,r6 -noname.41: - - decl 16(ap) - bleq noname.36 -noname.42: - - addl3 #16,r5,8(ap) - - addl3 #16,r4,12(ap) - - addl3 #16,r3,4(ap) - brw noname.33 - tstl r0 -noname.36: - - movl r6,r7 - -noname.32: - movl r7,r0 - ret - nop +0$: + movl (r3)+,r6 ; carry untouched + sbwc (r4)+,r6 ; carry used and touched + movl r6,(r2)+ ; carry untouched + sobgtr r5,0$ ; carry untouched + adwc #0,r0 +666$: + ret ;r=4 ;(AP) @@ -6615,81 +6409,3 @@ noname.610: ; For now, the code below doesn't work, so I end this prematurely. .end - - .title vax_bn_div64 division 64/32=>32 -; -; r.l. 16-jan-1998 -; -; unsigned int bn_div64(unsigned long h, unsigned long l, unsigned long d) -; return <h,l>/d; -; - - .psect code,nowrt - -h=4 ;(AP) by value (input) -l=8 ;(AP) by value (input) -d=12 ;(AP) by value (input) - -.entry bn_div64,^m<r2,r3,r4,r5,r6,r7,r8,r9> - - movl l(ap),r2 ; l - movl h(ap),r3 ; h - movl d(ap),r4 ; d - clrl r5 ; q - clrl r6 ; r - - ; Treat "negative" specially - tstl r3 - blss 30$ - - tstl r4 - beql 90$ - - ediv r4,r2,r5,r6 - bvs 666$ - - movl r5,r0 - ret - -30$: - ; The theory here is to do some harmless shifting and a little - ; bit of rounding (brackets are to designate when decimals are - ; cut off): - ; - ; result = 2 * [ ([<h,0>/2] + [d/2]) / d ] + [ l / d ] - - movl #0,r7 - movl r3,r8 ; copy h - ashq #-1,r7,r7 ; [<h,0>/2] => <r8,r7> - bicl2 #^X80000000,r8 ; Remove "sign" - - movl r4,r9 ; copy d - ashl #-1,r9,r9 ; [d/2] => r9 - bicl2 #^X80000000,r9 ; Remove "sign" - - addl2 r9,r7 - adwc #0,r8 ; [<h,0>/2] + [d/2] => <r8,r7> - - ediv r4,r7,r5,r6 ; [ ([<h,0>/2] + [d/2]) / d ] => <r5,r6> - bvs 666$ - - movl #0,r6 - ashq #1,r5,r5 ; 2 * [ ([<h,0>/2] + [d/2]) / d ] => r5 - - movl #0,r3 - ediv r4,r2,r8,r9 ; [ l / d ] => <r8,r9> - - addl2 r8,r5 ; - bcs 666$ - - movl r5,r0 - ret - -90$: - movl #-1,r0 - ret - -666$: - - -.end diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h index 1eb8395b25..47e355ea9d 100644 --- a/crypto/bn/bn.h +++ b/crypto/bn/bn.h @@ -75,8 +75,6 @@ extern "C" { #define BN_MUL_COMBA #define BN_SQR_COMBA #define BN_RECURSION -#define RECP_MUL_MOD -#define MONT_MUL_MOD /* This next option uses the C libraries (2 word)/(1 word) function. * If it is not defined, I use my C version (which is slower). @@ -90,6 +88,7 @@ extern "C" { * be on. Again this in only really a problem on machines * using "long long's", are 32bit, and are not using my assembler code. */ #if defined(MSDOS) || defined(WINDOWS) || defined(WIN32) || defined(linux) +#undef BN_DIV2W #define BN_DIV2W #endif @@ -239,7 +238,7 @@ typedef struct bignum_st } BIGNUM; /* Used for temp variables */ -#define BN_CTX_NUM 12 +#define BN_CTX_NUM 20 #define BN_CTX_NUM_POS 12 typedef struct bignum_ctx { @@ -283,9 +282,6 @@ typedef struct bn_recp_ctx_st int flags; } BN_RECP_CTX; -#define BN_to_montgomery(r,a,mont,ctx) BN_mod_mul_montgomery(\ - r,a,&((mont)->RR),(mont),ctx) - #define BN_prime_checks 0 /* default: select number of iterations based on the size of the number */ @@ -308,10 +304,15 @@ typedef struct bn_recp_ctx_st /* b >= 100 */ 27) #define BN_num_bytes(a) ((BN_num_bits(a)+7)/8) -#define BN_is_word(a,w) (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)(w))) -#define BN_is_zero(a) (((a)->top == 0) || BN_is_word(a,0)) -#define BN_is_one(a) (BN_is_word((a),1)) -#define BN_is_odd(a) (((a)->top > 0) && ((a)->d[0] & 1)) + +/* Note that BN_abs_is_word does not work reliably for w == 0 */ +#define BN_abs_is_word(a,w) (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)(w))) +#define BN_is_zero(a) (((a)->top == 0) || BN_abs_is_word(a,0)) +#define BN_is_one(a) (BN_abs_is_word((a),1) && !(a)->neg) +#define BN_is_word(a,w) ((w) ? BN_abs_is_word((a),(w)) && !(a)->neg : \ + BN_is_zero((a))) +#define BN_is_odd(a) (((a)->top > 0) && ((a)->d[0] & 1)) + #define BN_one(a) (BN_set_word((a),1)) #define BN_zero(a) (BN_set_word((a),0)) @@ -334,44 +335,62 @@ BIGNUM *BN_new(void); void BN_init(BIGNUM *); void BN_clear_free(BIGNUM *a); BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b); +void BN_swap(BIGNUM *a, BIGNUM *b); BIGNUM *BN_bin2bn(const unsigned char *s,int len,BIGNUM *ret); int BN_bn2bin(const BIGNUM *a, unsigned char *to); -BIGNUM *BN_mpi2bn(unsigned char *s,int len,BIGNUM *ret); +BIGNUM *BN_mpi2bn(const unsigned char *s,int len,BIGNUM *ret); int BN_bn2mpi(const BIGNUM *a, unsigned char *to); int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); -int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx); +int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); +int BN_sqr(BIGNUM *r, const BIGNUM *a,BN_CTX *ctx); + int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, - BN_CTX *ctx); -int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); -int BN_sqr(BIGNUM *r, BIGNUM *a,BN_CTX *ctx); + BN_CTX *ctx); +#define BN_mod(rem,m,d,ctx) BN_div(NULL,(rem),(m),(d),(ctx)) +int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx); +int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx); +int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m); +int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx); +int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m); +int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *m, BN_CTX *ctx); +int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); +int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); +int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m); +int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx); +int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m); + BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w); BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w); int BN_mul_word(BIGNUM *a, BN_ULONG w); int BN_add_word(BIGNUM *a, BN_ULONG w); int BN_sub_word(BIGNUM *a, BN_ULONG w); int BN_set_word(BIGNUM *a, BN_ULONG w); -BN_ULONG BN_get_word(BIGNUM *a); +BN_ULONG BN_get_word(const BIGNUM *a); + int BN_cmp(const BIGNUM *a, const BIGNUM *b); void BN_free(BIGNUM *a); int BN_is_bit_set(const BIGNUM *a, int n); int BN_lshift(BIGNUM *r, const 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, const BIGNUM *p, - const BIGNUM *m,BN_CTX *ctx); -int BN_mod_exp_mont(BIGNUM *r, BIGNUM *a, const BIGNUM *p, - const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); +int BN_lshift1(BIGNUM *r, const BIGNUM *a); +int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,BN_CTX *ctx); + +int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m,BN_CTX *ctx); +int BN_mod_exp_mont(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); int BN_mod_exp_mont_word(BIGNUM *r, BN_ULONG a, const BIGNUM *p, - const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); -int BN_mod_exp2_mont(BIGNUM *r, BIGNUM *a1, BIGNUM *p1,BIGNUM *a2, - BIGNUM *p2,BIGNUM *m,BN_CTX *ctx,BN_MONT_CTX *m_ctx); -int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, - BIGNUM *m,BN_CTX *ctx); + const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); +int BN_mod_exp2_mont(BIGNUM *r, const BIGNUM *a1, const BIGNUM *p1, + const BIGNUM *a2, const BIGNUM *p2,const BIGNUM *m, + BN_CTX *ctx,BN_MONT_CTX *m_ctx); +int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m,BN_CTX *ctx); + int BN_mask_bits(BIGNUM *a,int n); -int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx); #ifndef NO_FP_API int BN_print_fp(FILE *fp, const BIGNUM *a); #endif @@ -380,9 +399,9 @@ int BN_print(BIO *fp, const BIGNUM *a); #else int BN_print(void *fp, const BIGNUM *a); #endif -int BN_reciprocal(BIGNUM *r, BIGNUM *m, int len, BN_CTX *ctx); -int BN_rshift(BIGNUM *r, BIGNUM *a, int n); -int BN_rshift1(BIGNUM *r, BIGNUM *a); +int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx); +int BN_rshift(BIGNUM *r, const BIGNUM *a, int n); +int BN_rshift1(BIGNUM *r, const BIGNUM *a); void BN_clear(BIGNUM *a); BIGNUM *BN_dup(const BIGNUM *a); int BN_ucmp(const BIGNUM *a, const BIGNUM *b); @@ -392,23 +411,31 @@ char * BN_bn2hex(const BIGNUM *a); char * BN_bn2dec(const BIGNUM *a); int BN_hex2bn(BIGNUM **a, const char *str); int BN_dec2bn(BIGNUM **a, const char *str); -int BN_gcd(BIGNUM *r,BIGNUM *in_a,BIGNUM *in_b,BN_CTX *ctx); -BIGNUM *BN_mod_inverse(BIGNUM *ret,BIGNUM *a, const BIGNUM *n,BN_CTX *ctx); -BIGNUM *BN_generate_prime(BIGNUM *ret,int bits,int safe,BIGNUM *add, - BIGNUM *rem,void (*callback)(int,int,void *),void *cb_arg); +int BN_gcd(BIGNUM *r,const BIGNUM *a,const BIGNUM *b,BN_CTX *ctx); +int BN_kronecker(const BIGNUM *a,const BIGNUM *b,BN_CTX *ctx); /* returns -2 for error */ +BIGNUM *BN_mod_inverse(BIGNUM *ret, + const BIGNUM *a, const BIGNUM *n,BN_CTX *ctx); +BIGNUM *BN_mod_sqrt(BIGNUM *ret, + const BIGNUM *a, const BIGNUM *n,BN_CTX *ctx); +BIGNUM *BN_generate_prime(BIGNUM *ret,int bits,int safe, + const BIGNUM *add, const BIGNUM *rem, + void (*callback)(int,int,void *),void *cb_arg); int BN_is_prime(const BIGNUM *p,int nchecks, - void (*callback)(int,int,void *), - BN_CTX *ctx,void *cb_arg); + void (*callback)(int,int,void *), + BN_CTX *ctx,void *cb_arg); int BN_is_prime_fasttest(const BIGNUM *p,int nchecks, - void (*callback)(int,int,void *),BN_CTX *ctx,void *cb_arg, - int do_trial_division); + void (*callback)(int,int,void *),BN_CTX *ctx,void *cb_arg, + int do_trial_division); void ERR_load_BN_strings(void ); BN_MONT_CTX *BN_MONT_CTX_new(void ); void BN_MONT_CTX_init(BN_MONT_CTX *ctx); -int BN_mod_mul_montgomery(BIGNUM *r,BIGNUM *a,BIGNUM *b,BN_MONT_CTX *mont, - BN_CTX *ctx); -int BN_from_montgomery(BIGNUM *r,BIGNUM *a,BN_MONT_CTX *mont,BN_CTX *ctx); +int BN_mod_mul_montgomery(BIGNUM *r,const BIGNUM *a,const BIGNUM *b, + BN_MONT_CTX *mont, BN_CTX *ctx); +#define BN_to_montgomery(r,a,mont,ctx) BN_mod_mul_montgomery(\ + (r),(a),&((mont)->RR),(mont),(ctx)) +int BN_from_montgomery(BIGNUM *r,const 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,const BIGNUM *modulus,BN_CTX *ctx); BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to,BN_MONT_CTX *from); @@ -426,12 +453,12 @@ void BN_RECP_CTX_init(BN_RECP_CTX *recp); BN_RECP_CTX *BN_RECP_CTX_new(void); void BN_RECP_CTX_free(BN_RECP_CTX *recp); int BN_RECP_CTX_set(BN_RECP_CTX *recp,const BIGNUM *rdiv,BN_CTX *ctx); -int BN_mod_mul_reciprocal(BIGNUM *r, BIGNUM *x, BIGNUM *y, - BN_RECP_CTX *recp,BN_CTX *ctx); +int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, + BN_RECP_CTX *recp,BN_CTX *ctx); int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, - const BIGNUM *m, BN_CTX *ctx); -int BN_div_recp(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, - BN_RECP_CTX *recp, BN_CTX *ctx); + const BIGNUM *m, BN_CTX *ctx); +int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, + BN_RECP_CTX *recp, BN_CTX *ctx); /* library internal functions */ @@ -439,6 +466,7 @@ int BN_div_recp(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, (a):bn_expand2((a),(bits)/BN_BITS2+1)) #define bn_wexpand(a,words) (((words) <= (a)->dmax)?(a):bn_expand2((a),(words))) BIGNUM *bn_expand2(BIGNUM *a, int words); +BIGNUM *bn_dup_expand(const BIGNUM *a, int words); #define bn_fix_top(a) \ { \ @@ -450,15 +478,15 @@ BIGNUM *bn_expand2(BIGNUM *a, int words); } \ } -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_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w); +BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w); +void bn_sqr_words(BN_ULONG *rp, const BN_ULONG *ap, int num); BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d); -BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num); -BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num); +BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,int num); +BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,int num); #ifdef BN_DEBUG - void bn_dump1(FILE *o, const char *a, BN_ULONG *b,int n); +void bn_dump1(FILE *o, const char *a, const BN_ULONG *b,int n); # define bn_print(a) {fprintf(stderr, #a "="); BN_print_fp(stderr,a); \ fprintf(stderr,"\n");} # define bn_dump(a,n) bn_dump1(stderr,#a,a,n); @@ -467,6 +495,8 @@ BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num); # define bn_dump(a,b) #endif +int BN_bntest_rand(BIGNUM *rnd, int bits, int top,int bottom); + /* BEGIN ERROR CODES */ /* The following lines are auto generated by the script mkerr.pl. Any changes * made after this point may be overwritten when the script is next run. @@ -485,11 +515,14 @@ BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num); #define BN_F_BN_CTX_NEW 106 #define BN_F_BN_DIV 107 #define BN_F_BN_EXPAND2 108 +#define BN_F_BN_EXPAND_INTERNAL 120 #define BN_F_BN_MOD_EXP2_MONT 118 #define BN_F_BN_MOD_EXP_MONT 109 #define BN_F_BN_MOD_EXP_MONT_WORD 117 #define BN_F_BN_MOD_INVERSE 110 +#define BN_F_BN_MOD_LSHIFT_QUICK 119 #define BN_F_BN_MOD_MUL_RECIPROCAL 111 +#define BN_F_BN_MOD_SQRT 121 #define BN_F_BN_MPI2BN 112 #define BN_F_BN_NEW 113 #define BN_F_BN_RAND 114 @@ -498,13 +531,18 @@ BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num); /* Reason codes. */ #define BN_R_ARG2_LT_ARG3 100 #define BN_R_BAD_RECIPROCAL 101 +#define BN_R_BIGNUM_TOO_LONG 114 #define BN_R_CALLED_WITH_EVEN_MODULUS 102 #define BN_R_DIV_BY_ZERO 103 #define BN_R_ENCODING_ERROR 104 #define BN_R_EXPAND_ON_STATIC_BIGNUM_DATA 105 +#define BN_R_INPUT_NOT_REDUCED 110 #define BN_R_INVALID_LENGTH 106 +#define BN_R_NOT_A_SQUARE 111 #define BN_R_NOT_INITIALIZED 107 #define BN_R_NO_INVERSE 108 +#define BN_R_P_IS_NOT_PRIME 112 +#define BN_R_TOO_MANY_ITERATIONS 113 #define BN_R_TOO_MANY_TEMPORARY_VARIABLES 109 #ifdef __cplusplus diff --git a/crypto/bn/bn_asm.c b/crypto/bn/bn_asm.c index 44e52a40db..be8aa3ffc5 100644 --- a/crypto/bn/bn_asm.c +++ b/crypto/bn/bn_asm.c @@ -68,7 +68,7 @@ #if defined(BN_LLONG) || defined(BN_UMULT_HIGH) -BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w) +BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w) { BN_ULONG c1=0; @@ -93,7 +93,7 @@ BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w) return(c1); } -BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w) +BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w) { BN_ULONG c1=0; @@ -117,7 +117,7 @@ BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w) return(c1); } -void bn_sqr_words(BN_ULONG *r, BN_ULONG *a, int n) +void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n) { assert(n >= 0); if (n <= 0) return; @@ -139,7 +139,7 @@ void bn_sqr_words(BN_ULONG *r, BN_ULONG *a, int n) #else /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */ -BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w) +BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w) { BN_ULONG c=0; BN_ULONG bl,bh; @@ -166,7 +166,7 @@ BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w) return(c); } -BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w) +BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w) { BN_ULONG carry=0; BN_ULONG bl,bh; @@ -193,7 +193,7 @@ BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w) return(carry); } -void bn_sqr_words(BN_ULONG *r, BN_ULONG *a, int n) +void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n) { assert(n >= 0); if (n <= 0) return; @@ -296,7 +296,7 @@ BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d) #endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */ #ifdef BN_LLONG -BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) +BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) { BN_ULLONG ll=0; @@ -332,7 +332,7 @@ BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) return((BN_ULONG)ll); } #else /* !BN_LLONG */ -BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) +BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) { BN_ULONG c,l,t; @@ -382,7 +382,7 @@ BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) } #endif /* !BN_LLONG */ -BN_ULONG bn_sub_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) +BN_ULONG bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) { BN_ULONG t1,t2; int c=0; @@ -673,7 +673,7 @@ void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b) r[7]=c2; } -void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a) +void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a) { #ifdef BN_LLONG BN_ULLONG t,tt; @@ -754,7 +754,7 @@ void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a) r[15]=c1; } -void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a) +void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a) { #ifdef BN_LLONG BN_ULLONG t,tt; diff --git a/crypto/bn/bn_ctx.c b/crypto/bn/bn_ctx.c index b1a8d7571e..28b334fbd5 100644 --- a/crypto/bn/bn_ctx.c +++ b/crypto/bn/bn_ctx.c @@ -112,8 +112,14 @@ void BN_CTX_start(BN_CTX *ctx) ctx->depth++; } + BIGNUM *BN_CTX_get(BN_CTX *ctx) { + /* Note: If BN_CTX_get is ever changed to allocate BIGNUMs dynamically, + * make sure that if BN_CTX_get fails once it will return NULL again + * until BN_CTX_end is called. (This is so that callers have to check + * only the last return value.) + */ if (ctx->depth > BN_CTX_NUM_POS || ctx->tos >= BN_CTX_NUM) { if (!ctx->too_many) diff --git a/crypto/bn/bn_div.c b/crypto/bn/bn_div.c index c3772c243b..2e600c7c54 100644 --- a/crypto/bn/bn_div.c +++ b/crypto/bn/bn_div.c @@ -61,6 +61,7 @@ #include "cryptlib.h" #include "bn_lcl.h" + /* The old slow way */ #if 0 int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, @@ -152,6 +153,14 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, # endif /* __GNUC__ */ #endif /* NO_ASM */ + +/* BN_div computes dv := num / divisor, rounding towards zero, and sets up + * rm such that dv*divisor + rm = num holds. + * Thus: + * dv->neg == num->neg ^ divisor->neg (unless the result is zero) + * rm->neg == num->neg (unless the remainder is zero) + * If 'dv' or 'rm' is NULL, the respective value is not returned. + */ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX *ctx) { @@ -180,13 +189,13 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX_start(ctx); tmp=BN_CTX_get(ctx); - tmp->neg=0; snum=BN_CTX_get(ctx); sdiv=BN_CTX_get(ctx); if (dv == NULL) res=BN_CTX_get(ctx); else res=dv; - if (res == NULL) goto err; + if (sdiv == NULL || res == NULL) goto err; + tmp->neg=0; /* First we normalise the numbers */ norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2); @@ -331,7 +340,8 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, if (rm != NULL) { BN_rshift(rm,snum,norm_shift); - rm->neg=num->neg; + if (!BN_is_zero(rm)) + rm->neg = num->neg; } BN_CTX_end(ctx); return(1); @@ -341,40 +351,3 @@ err: } #endif - -/* rem != m */ -int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) - { -#if 0 /* The old slow way */ - int i,nm,nd; - BIGNUM *dv; - - if (BN_ucmp(m,d) < 0) - return((BN_copy(rem,m) == NULL)?0:1); - - BN_CTX_start(ctx); - dv=BN_CTX_get(ctx); - - if (!BN_copy(rem,m)) goto err; - - nm=BN_num_bits(rem); - nd=BN_num_bits(d); - if (!BN_lshift(dv,d,nm-nd)) goto err; - for (i=nm-nd; i>=0; i--) - { - if (BN_cmp(rem,dv) >= 0) - { - if (!BN_sub(rem,rem,dv)) goto err; - } - if (!BN_rshift1(dv,dv)) goto err; - } - BN_CTX_end(ctx); - return(1); - err: - BN_CTX_end(ctx); - return(0); -#else - return(BN_div(NULL,rem,m,d,ctx)); -#endif - } - diff --git a/crypto/bn/bn_err.c b/crypto/bn/bn_err.c index 86550c4c21..d7f0493f47 100644 --- a/crypto/bn/bn_err.c +++ b/crypto/bn/bn_err.c @@ -76,11 +76,14 @@ static ERR_STRING_DATA BN_str_functs[]= {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_EXPAND_INTERNAL,0), "BN_EXPAND_INTERNAL"}, {ERR_PACK(0,BN_F_BN_MOD_EXP2_MONT,0), "BN_mod_exp2_mont"}, {ERR_PACK(0,BN_F_BN_MOD_EXP_MONT,0), "BN_mod_exp_mont"}, {ERR_PACK(0,BN_F_BN_MOD_EXP_MONT_WORD,0), "BN_mod_exp_mont_word"}, {ERR_PACK(0,BN_F_BN_MOD_INVERSE,0), "BN_mod_inverse"}, +{ERR_PACK(0,BN_F_BN_MOD_LSHIFT_QUICK,0), "BN_mod_lshift_quick"}, {ERR_PACK(0,BN_F_BN_MOD_MUL_RECIPROCAL,0), "BN_mod_mul_reciprocal"}, +{ERR_PACK(0,BN_F_BN_MOD_SQRT,0), "BN_mod_sqrt"}, {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"}, @@ -92,13 +95,18 @@ static ERR_STRING_DATA BN_str_reasons[]= { {BN_R_ARG2_LT_ARG3 ,"arg2 lt arg3"}, {BN_R_BAD_RECIPROCAL ,"bad reciprocal"}, +{BN_R_BIGNUM_TOO_LONG ,"bignum too long"}, {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_EXPAND_ON_STATIC_BIGNUM_DATA ,"expand on static bignum data"}, +{BN_R_INPUT_NOT_REDUCED ,"input not reduced"}, {BN_R_INVALID_LENGTH ,"invalid length"}, +{BN_R_NOT_A_SQUARE ,"not a square"}, {BN_R_NOT_INITIALIZED ,"not initialized"}, {BN_R_NO_INVERSE ,"no inverse"}, +{BN_R_P_IS_NOT_PRIME ,"p is not prime"}, +{BN_R_TOO_MANY_ITERATIONS ,"too many iterations"}, {BN_R_TOO_MANY_TEMPORARY_VARIABLES ,"too many temporary variables"}, {0,NULL} }; diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c index d2c91628ac..1739be6864 100644 --- a/crypto/bn/bn_exp.c +++ b/crypto/bn/bn_exp.c @@ -110,38 +110,13 @@ */ -#include <stdio.h> #include "cryptlib.h" #include "bn_lcl.h" #define TABLE_SIZE 32 -/* slow but works */ -int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) - { - BIGNUM *t; - int r=0; - - bn_check_top(a); - bn_check_top(b); - bn_check_top(m); - - BN_CTX_start(ctx); - if ((t = BN_CTX_get(ctx)) == NULL) goto err; - if (a == b) - { if (!BN_sqr(t,a,ctx)) goto err; } - else - { if (!BN_mul(t,a,b,ctx)) goto err; } - if (!BN_mod(ret,t,m,ctx)) goto err; - r=1; -err: - BN_CTX_end(ctx); - return(r); - } - - /* this one works - simple but works */ -int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) +int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) { int i,bits,ret=0; BIGNUM *v,*rr; @@ -176,7 +151,7 @@ err: } -int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, +int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx) { int ret; @@ -185,6 +160,40 @@ int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, bn_check_top(p); bn_check_top(m); + /* For even modulus m = 2^k*m_odd, it might make sense to compute + * a^p mod m_odd and a^p mod 2^k separately (with Montgomery + * exponentiation for the odd part), using appropriate exponent + * reductions, and combine the results using the CRT. + * + * For now, we use Montgomery only if the modulus is odd; otherwise, + * exponentiation using the reciprocal-based quick remaindering + * algorithm is used. + * + * (Timing obtained with expspeed.c [computations a^p mod m + * where a, p, m are of the same length: 256, 512, 1024, 2048, + * 4096, 8192 bits], compared to the running time of the + * standard algorithm: + * + * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration] + * 55 .. 77 % [UltraSparc processor, but + * debug-solaris-sparcv8-gcc conf.] + * + * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration] + * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc] + * + * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont + * at 2048 and more bits, but at 512 and 1024 bits, it was + * slower even than the standard algorithm! + * + * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations] + * should be obtained when the new Montgomery reduction code + * has been integrated into OpenSSL.) + */ + +#define MONT_MUL_MOD +#define MONT_EXP_WORD +#define RECP_MUL_MOD + #ifdef MONT_MUL_MOD /* I have finally been able to take out this pre-condition of * the top bit being set. It was caused by an error in BN_div @@ -194,12 +203,14 @@ int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, if (BN_is_odd(m)) { - if (a->top == 1) +# ifdef MONT_EXP_WORD + if (a->top == 1 && !a->neg) { BN_ULONG A = a->d[0]; ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL); } else +# endif ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); } else @@ -227,8 +238,8 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, if (bits == 0) { - BN_one(r); - return(1); + ret = BN_one(r); + return ret; } BN_CTX_start(ctx); @@ -240,7 +251,12 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_init(&(val[0])); ts=1; - if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ + if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; /* 1 */ + if (BN_is_zero(&(val[0]))) + { + ret = BN_zero(r); + goto err; + } window = BN_window_bits_for_exponent_size(bits); if (window > 1) @@ -325,13 +341,13 @@ err: } -int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p, +int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) { int i,j,bits,ret=0,wstart,wend,window,wvalue; int start=1,ts=0; BIGNUM *d,*r; - BIGNUM *aa; + const BIGNUM *aa; BIGNUM val[TABLE_SIZE]; BN_MONT_CTX *mont=NULL; @@ -347,9 +363,10 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p, bits=BN_num_bits(p); if (bits == 0) { - BN_one(rr); - return(1); + ret = BN_one(rr); + return ret; } + BN_CTX_start(ctx); d = BN_CTX_get(ctx); r = BN_CTX_get(ctx); @@ -368,14 +385,19 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p, BN_init(&val[0]); ts=1; - if (BN_ucmp(a,m) >= 0) + if (a->neg || BN_ucmp(a,m) >= 0) { - if (!BN_mod(&(val[0]),a,m,ctx)) + if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; aa= &(val[0]); } else aa=a; + if (BN_is_zero(aa)) + { + ret = BN_zero(rr); + goto err; + } if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */ window = BN_window_bits_for_exponent_size(bits); @@ -484,17 +506,26 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, bn_check_top(p); bn_check_top(m); - if (!(m->d[0] & 1)) + if (m->top == 0 || !(m->d[0] & 1)) { BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS); return(0); } + if (m->top == 1) + a %= m->d[0]; /* make sure that 'a' is reduced */ + bits = BN_num_bits(p); if (bits == 0) { - BN_one(rr); - return(1); + ret = BN_one(rr); + return ret; + } + if (a == 0) + { + ret = BN_zero(rr); + return ret; } + BN_CTX_start(ctx); d = BN_CTX_get(ctx); r = BN_CTX_get(ctx); @@ -590,8 +621,9 @@ err: /* The old fallback, simple version :-) */ -int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, - BN_CTX *ctx) +int BN_mod_exp_simple(BIGNUM *r, + const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, + BN_CTX *ctx) { int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0; int start=1; @@ -602,8 +634,8 @@ int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, if (bits == 0) { - BN_one(r); - return(1); + ret = BN_one(r); + return ret; } BN_CTX_start(ctx); @@ -611,7 +643,12 @@ int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_init(&(val[0])); ts=1; - if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ + if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; /* 1 */ + if (BN_is_zero(&(val[0]))) + { + ret = BN_zero(r); + goto err; + } window = BN_window_bits_for_exponent_size(bits); if (window > 1) diff --git a/crypto/bn/bn_exp2.c b/crypto/bn/bn_exp2.c index 29029f4c72..73ccd58a83 100644 --- a/crypto/bn/bn_exp2.c +++ b/crypto/bn/bn_exp2.c @@ -115,13 +115,14 @@ #define TABLE_SIZE 32 -int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2, - BIGNUM *p2, BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) +int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, + const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, + BN_CTX *ctx, BN_MONT_CTX *in_mont) { int i,j,bits,b,bits1,bits2,ret=0,wpos1,wpos2,window1,window2,wvalue1,wvalue2; int r_is_one=1,ts1=0,ts2=0; BIGNUM *d,*r; - BIGNUM *a_mod_m; + const BIGNUM *a_mod_m; BIGNUM val1[TABLE_SIZE], val2[TABLE_SIZE]; BN_MONT_CTX *mont=NULL; @@ -140,9 +141,10 @@ int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2, bits2=BN_num_bits(p2); if ((bits1 == 0) && (bits2 == 0)) { - BN_one(rr); - return(1); + ret = BN_one(rr); + return ret; } + bits=(bits1 > bits2)?bits1:bits2; BN_CTX_start(ctx); @@ -166,7 +168,7 @@ int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2, */ BN_init(&val1[0]); ts1=1; - if (BN_ucmp(a1,m) >= 0) + if (a1->neg || BN_ucmp(a1,m) >= 0) { if (!BN_mod(&(val1[0]),a1,m,ctx)) goto err; @@ -174,6 +176,12 @@ int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2, } else a_mod_m = a1; + if (BN_is_zero(a_mod_m)) + { + ret = BN_zero(rr); + goto err; + } + if (!BN_to_montgomery(&(val1[0]),a_mod_m,mont,ctx)) goto err; if (window1 > 1) { @@ -195,7 +203,7 @@ int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2, */ BN_init(&val2[0]); ts2=1; - if (BN_ucmp(a2,m) >= 0) + if (a2->neg || BN_ucmp(a2,m) >= 0) { if (!BN_mod(&(val2[0]),a2,m,ctx)) goto err; @@ -203,6 +211,11 @@ int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2, } else a_mod_m = a2; + if (BN_is_zero(a_mod_m)) + { + ret = BN_zero(rr); + goto err; + } if (!BN_to_montgomery(&(val2[0]),a_mod_m,mont,ctx)) goto err; if (window2 > 1) { diff --git a/crypto/bn/bn_gcd.c b/crypto/bn/bn_gcd.c index 398207196b..d5caf5136f 100644 --- a/crypto/bn/bn_gcd.c +++ b/crypto/bn/bn_gcd.c @@ -55,14 +55,66 @@ * copied and put under another distribution licence * [including the GNU Public Licence.] */ +/* ==================================================================== + * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. + * + * 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 above 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 acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED 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 OpenSSL PROJECT OR + * ITS 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. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ -#include <stdio.h> #include "cryptlib.h" #include "bn_lcl.h" static BIGNUM *euclid(BIGNUM *a, BIGNUM *b); -int BN_gcd(BIGNUM *r, BIGNUM *in_a, BIGNUM *in_b, BN_CTX *ctx) +int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) { BIGNUM *a,*b,*t; int ret=0; @@ -77,6 +129,8 @@ int BN_gcd(BIGNUM *r, BIGNUM *in_a, BIGNUM *in_b, BN_CTX *ctx) if (BN_copy(a,in_a) == NULL) goto err; if (BN_copy(b,in_b) == NULL) goto err; + a->neg = 0; + b->neg = 0; if (BN_cmp(a,b) < 0) { t=a; a=b; b=t; } t=euclid(a,b); @@ -97,10 +151,10 @@ static BIGNUM *euclid(BIGNUM *a, BIGNUM *b) bn_check_top(a); bn_check_top(b); - for (;;) + /* 0 <= b <= a */ + while (!BN_is_zero(b)) { - if (BN_is_zero(b)) - break; + /* 0 < b <= a */ if (BN_is_odd(a)) { @@ -133,7 +187,9 @@ static BIGNUM *euclid(BIGNUM *a, BIGNUM *b) shifts++; } } + /* 0 <= b <= a */ } + if (shifts) { if (!BN_lshift(a,a,shifts)) goto err; @@ -143,11 +199,13 @@ err: return(NULL); } + /* solves ax == 1 (mod n) */ -BIGNUM *BN_mod_inverse(BIGNUM *in, BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) +BIGNUM *BN_mod_inverse(BIGNUM *in, + const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) { - BIGNUM *A,*B,*X,*Y,*M,*D,*R=NULL; - BIGNUM *T,*ret=NULL; + BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL; + BIGNUM *ret=NULL; int sign; bn_check_top(a); @@ -160,7 +218,8 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) D = BN_CTX_get(ctx); M = BN_CTX_get(ctx); Y = BN_CTX_get(ctx); - if (Y == NULL) goto err; + T = BN_CTX_get(ctx); + if (T == NULL) goto err; if (in == NULL) R=BN_new(); @@ -168,34 +227,166 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) R=in; if (R == NULL) goto err; - BN_zero(X); - BN_one(Y); - if (BN_copy(A,a) == NULL) goto err; - if (BN_copy(B,n) == NULL) goto err; - sign=1; + BN_one(X); + BN_zero(Y); + if (BN_copy(B,a) == NULL) goto err; + if (BN_copy(A,n) == NULL) goto err; + A->neg = 0; + if (B->neg || (BN_ucmp(B, A) >= 0)) + { + if (!BN_nnmod(B, B, A, ctx)) goto err; + } + sign = -1; + /* From B = a mod |n|, A = |n| it follows that + * + * 0 <= B < A, + * sign*X*a == B (mod |n|), + * -sign*Y*a == A (mod |n|). + */ while (!BN_is_zero(B)) { - if (!BN_div(D,M,A,B,ctx)) goto err; - T=A; + BIGNUM *tmp; + + /* + * 0 < B < A, + * (*) sign*X*a == B (mod |n|), + * -sign*Y*a == A (mod |n|) + */ + + /* (D, M) := (A/B, A%B) ... */ + if (BN_num_bits(A) == BN_num_bits(B)) + { + if (!BN_one(D)) goto err; + if (!BN_sub(M,A,B)) goto err; + } + else if (BN_num_bits(A) == BN_num_bits(B) + 1) + { + /* A/B is 1, 2, or 3 */ + if (!BN_lshift1(T,B)) goto err; + if (BN_ucmp(A,T) < 0) + { + /* A < 2*B, so D=1 */ + if (!BN_one(D)) goto err; + if (!BN_sub(M,A,B)) goto err; + } + else + { + /* A >= 2*B, so D=2 or D=3 */ + if (!BN_sub(M,A,T)) goto err; + if (!BN_add(D,T,B)) goto err; /* use D (:= 3*B) as temp */ + if (BN_ucmp(A,D) < 0) + { + /* A < 3*B, so D=2 */ + if (!BN_set_word(D,2)) goto err; + /* M (= A - 2*B) already has the correct value */ + } + else + { + /* only D=3 remains */ + if (!BN_set_word(D,3)) goto err; + /* currently M = A - 2*B, but we need M = A - 3*B */ + if (!BN_sub(M,M,B)) goto err; + } + } + } + else + { + if (!BN_div(D,M,A,B,ctx)) goto err; + } + + /* Now + * A = D*B + M; + * thus we have + * (**) -sign*Y*a == D*B + M (mod |n|). + */ + + tmp=A; /* keep the BIGNUM object, the value does not matter */ + + /* (A, B) := (B, A mod B) ... */ A=B; B=M; - /* T has a struct, M does not */ + /* ... so we have 0 <= B < A again */ + + /* Since the former M is now B and the former B is now A, + * (**) translates into + * -sign*Y*a == D*A + B (mod |n|), + * i.e. + * -sign*Y*a - D*A == B (mod |n|). + * Similarly, (*) translates into + * sign*X*a == A (mod |n|). + * + * Thus, + * -sign*Y*a - D*sign*X*a == B (mod |n|), + * i.e. + * -sign*(Y + D*X)*a == B (mod |n|). + * + * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at + * sign*X*a == B (mod |n|), + * -sign*Y*a == A (mod |n|). + * Note that X and Y stay non-negative all the time. + */ - if (!BN_mul(T,D,X,ctx)) goto err; - if (!BN_add(T,T,Y)) goto err; - M=Y; + /* most of the time D is very small, so we can optimize tmp := D*X+Y */ + if (BN_is_one(D)) + { + if (!BN_add(tmp,X,Y)) goto err; + } + else + { + if (BN_is_word(D,2)) + { + if (!BN_lshift1(tmp,X)) goto err; + } + else if (BN_is_word(D,4)) + { + if (!BN_lshift(tmp,X,2)) goto err; + } + else if (D->top == 1) + { + if (!BN_copy(tmp,X)) goto err; + if (!BN_mul_word(tmp,D->d[0])) goto err; + } + else + { + if (!BN_mul(tmp,D,X,ctx)) goto err; + } + if (!BN_add(tmp,tmp,Y)) goto err; + } + + M=Y; /* keep the BIGNUM object, the value does not matter */ Y=X; - X=T; - sign= -sign; + X=tmp; + sign = -sign; } + + /* + * The while loop (Euclid's algorithm) ends when + * A == gcd(a,n); + * we have + * -sign*Y*a == A (mod |n|), + * where Y is non-negative. + */ + if (sign < 0) { if (!BN_sub(Y,n,Y)) goto err; } + /* Now Y*a == A (mod |n|). */ + if (BN_is_one(A)) - { if (!BN_mod(R,Y,n,ctx)) goto err; } + { + /* Y*a == 1 (mod |n|) */ + if (BN_ucmp(Y,n) < 0) + { + if (!BN_copy(R,Y)) goto err; + } + else + { + if (!BN_nnmod(R,Y,n,ctx)) goto err; + } + } else { BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE); @@ -207,4 +398,3 @@ err: BN_CTX_end(ctx); return(ret); } - diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h index 9c959921b4..39ad05631a 100644 --- a/crypto/bn/bn_lcl.h +++ b/crypto/bn/bn_lcl.h @@ -398,14 +398,17 @@ extern "C" { void bn_mul_normal(BN_ULONG *r,BN_ULONG *a,int na,BN_ULONG *b,int nb); void bn_mul_comba8(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b); void bn_mul_comba4(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b); -void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp); -void bn_sqr_comba8(BN_ULONG *r,BN_ULONG *a); -void bn_sqr_comba4(BN_ULONG *r,BN_ULONG *a); -int bn_cmp_words(BN_ULONG *a,BN_ULONG *b,int n); -void bn_mul_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,int n2,BN_ULONG *t); +void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp); +void bn_sqr_comba8(BN_ULONG *r,const BN_ULONG *a); +void bn_sqr_comba4(BN_ULONG *r,const BN_ULONG *a); +int bn_cmp_words(const BN_ULONG *a,const BN_ULONG *b,int n); +int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, + int cl, int dl); +void bn_mul_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,int n2, + int dna,int dnb,BN_ULONG *t); void bn_mul_part_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b, - int tn, int n,BN_ULONG *t); -void bn_sqr_recursive(BN_ULONG *r,BN_ULONG *a, int n2, BN_ULONG *t); + int n,int tna,int tnb,BN_ULONG *t); +void bn_sqr_recursive(BN_ULONG *r,const BN_ULONG *a, int n2, BN_ULONG *t); void bn_mul_low_normal(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b, int n); void bn_mul_low_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,int n2, BN_ULONG *t); diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index b6b0ce4b3c..e37b85bfc5 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -62,6 +62,7 @@ #endif #include <assert.h> +#include <limits.h> #include <stdio.h> #include "cryptlib.h" #include "bn_lcl.h" @@ -304,166 +305,168 @@ BIGNUM *BN_new(void) return(ret); } -/* This is an internal function that should not be used in applications. - * It ensures that 'b' has enough room for a 'words' word number number. - * It is mostly used by the various BIGNUM routines. If there is an error, - * NULL is returned. If not, 'b' is returned. */ - -BIGNUM *bn_expand2(BIGNUM *b, int words) +/* This is used both by bn_expand2() and bn_dup_expand() */ +/* The caller MUST check that words > b->dmax before calling this */ +static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) { - BN_ULONG *A,*a; + BN_ULONG *A,*a = NULL; const BN_ULONG *B; int i; - bn_check_top(b); + if (words > (INT_MAX/(4*BN_BITS2))) + { + BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_BIGNUM_TOO_LONG); + return NULL; + } - if (words > b->dmax) + bn_check_top(b); + if (BN_get_flags(b,BN_FLG_STATIC_DATA)) + { + BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); + return(NULL); + } + a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1)); + if (A == NULL) { - bn_check_top(b); - if (BN_get_flags(b,BN_FLG_STATIC_DATA)) + BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE); + return(NULL); + } +#if 1 + B=b->d; + /* Check if the previous number needs to be copied */ + if (B != NULL) + { + for (i=b->top>>2; i>0; i--,A+=4,B+=4) { - BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); - return(NULL); + /* + * The fact that the loop is unrolled + * 4-wise is a tribute to Intel. It's + * the one that doesn't have enough + * registers to accomodate more data. + * I'd unroll it 8-wise otherwise:-) + * + * <appro@fy.chalmers.se> + */ + BN_ULONG a0,a1,a2,a3; + a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; + A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; } - a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1)); - if (A == NULL) + switch (b->top&3) { - BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE); - return(NULL); + case 3: A[2]=B[2]; + case 2: A[1]=B[1]; + case 1: A[0]=B[0]; + case 0: /* workaround for ultrix cc: without 'case 0', the optimizer does + * the switch table by doing a=top&3; a--; goto jump_table[a]; + * which fails for top== 0 */ + ; } -#if 1 - B=b->d; - /* Check if the previous number needs to be copied */ - if (B != NULL) - { -#if 0 - /* This lot is an unrolled loop to copy b->top - * BN_ULONGs from B to A - */ -/* - * I have nothing against unrolling but it's usually done for - * several reasons, namely: - * - minimize percentage of decision making code, i.e. branches; - * - avoid cache trashing; - * - make it possible to schedule loads earlier; - * Now let's examine the code below. The cornerstone of C is - * "programmer is always right" and that's what we love it for:-) - * For this very reason C compilers have to be paranoid when it - * comes to data aliasing and assume the worst. Yeah, but what - * does it mean in real life? This means that loop body below will - * be compiled to sequence of loads immediately followed by stores - * as compiler assumes the worst, something in A==B+1 style. As a - * result CPU pipeline is going to starve for incoming data. Secondly - * if A and B happen to share same cache line such code is going to - * cause severe cache trashing. Both factors have severe impact on - * performance of modern CPUs and this is the reason why this - * particular piece of code is #ifdefed away and replaced by more - * "friendly" version found in #else section below. This comment - * also applies to BN_copy function. - * - * <appro@fy.chalmers.se> - */ - 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]; - case 0: - /* I need the 'case 0' entry for utrix cc. - * If the optimizer is turned on, it does the - * switch table by doing - * a=top&7 - * a--; - * goto jump_table[a]; - * If top is 0, this makes us jump to 0xffffffc - * which is rather bad :-(. - * eric 23-Apr-1998 - */ - ; - } + } + + /* Now need to zero any data between b->top and b->max */ + /* XXX Why? */ + + A= &(a[b->top]); + for (i=(words - b->top)>>3; i>0; i--,A+=8) + { + A[0]=0; A[1]=0; A[2]=0; A[3]=0; + A[4]=0; A[5]=0; A[6]=0; A[7]=0; + } + for (i=(words - b->top)&7; i>0; i--,A++) + A[0]=0; #else - for (i=b->top>>2; i>0; i--,A+=4,B+=4) + memset(A,0,sizeof(BN_ULONG)*(words+1)); + memcpy(A,b->d,sizeof(b->d[0])*b->top); +#endif + + return(a); + } + +/* This is an internal function that can be used instead of bn_expand2() + * when there is a need to copy BIGNUMs instead of only expanding the + * data part, while still expanding them. + * Especially useful when needing to expand BIGNUMs that are declared + * 'const' and should therefore not be changed. + * The reason to use this instead of a BN_dup() followed by a bn_expand2() + * is memory allocation overhead. A BN_dup() followed by a bn_expand2() + * will allocate new memory for the BIGNUM data twice, and free it once, + * while bn_dup_expand() makes sure allocation is made only once. + */ + +BIGNUM *bn_dup_expand(const BIGNUM *b, int words) + { + BIGNUM *r = NULL; + + if (words > b->dmax) + { + BN_ULONG *a = bn_expand_internal(b, words); + + if (a) + { + r = BN_new(); + if (r) { - /* - * The fact that the loop is unrolled - * 4-wise is a tribute to Intel. It's - * the one that doesn't have enough - * registers to accomodate more data. - * I'd unroll it 8-wise otherwise:-) - * - * <appro@fy.chalmers.se> - */ - BN_ULONG a0,a1,a2,a3; - a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; - A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; + r->top = b->top; + r->dmax = words; + r->neg = b->neg; + r->d = a; } - switch (b->top&3) + else { - case 3: A[2]=B[2]; - case 2: A[1]=B[1]; - case 1: A[0]=B[0]; - case 0: ; /* ultrix cc workaround, see above */ + /* r == NULL, BN_new failure */ + OPENSSL_free(a); } -#endif - OPENSSL_free(b->d); } + /* If a == NULL, there was an error in allocation in + bn_expand_internal(), and NULL should be returned */ + } + else + { + r = BN_dup(b); + } + + return r; + } - b->d=a; - b->dmax=words; +/* This is an internal function that should not be used in applications. + * It ensures that 'b' has enough room for a 'words' word number number. + * It is mostly used by the various BIGNUM routines. If there is an error, + * NULL is returned. If not, 'b' is returned. */ - /* Now need to zero any data between b->top and b->max */ +BIGNUM *bn_expand2(BIGNUM *b, int words) + { + if (words > b->dmax) + { + BN_ULONG *a = bn_expand_internal(b, words); - A= &(b->d[b->top]); - for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8) + if (a) { - A[0]=0; A[1]=0; A[2]=0; A[3]=0; - A[4]=0; A[5]=0; A[6]=0; A[7]=0; - } - for (i=(b->dmax - b->top)&7; i>0; i--,A++) - A[0]=0; -#else - memset(A,0,sizeof(BN_ULONG)*(words+1)); - memcpy(A,b->d,sizeof(b->d[0])*b->top); + if (b->d) + OPENSSL_free(b->d); b->d=a; - b->max=words; -#endif - -/* memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */ -/* { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */ - + b->dmax=words; + } + else + b = NULL; } - return(b); + return b; } BIGNUM *BN_dup(const BIGNUM *a) { - BIGNUM *r; + BIGNUM *r, *t; if (a == NULL) return NULL; bn_check_top(a); - r=BN_new(); - if (r == NULL) return(NULL); - return((BIGNUM *)BN_copy(r,a)); + t = BN_new(); + if (t == NULL) return(NULL); + r = BN_copy(t, a); + /* now r == t || r == NULL */ + if (r == NULL) + BN_free(t); + return r; } BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) @@ -491,7 +494,7 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) case 3: A[2]=B[2]; case 2: A[1]=B[1]; case 1: A[0]=B[0]; - case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */ + case 0: ; /* ultrix cc workaround, see comments in bn_expand_internal */ } #else memcpy(a->d,b->d,sizeof(b->d[0])*b->top); @@ -505,6 +508,35 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) return(a); } +void BN_swap(BIGNUM *a, BIGNUM *b) + { + int flags_old_a, flags_old_b; + BN_ULONG *tmp_d; + int tmp_top, tmp_dmax, tmp_neg; + + flags_old_a = a->flags; + flags_old_b = b->flags; + + tmp_d = a->d; + tmp_top = a->top; + tmp_dmax = a->dmax; + tmp_neg = a->neg; + + a->d = b->d; + a->top = b->top; + a->dmax = b->dmax; + a->neg = b->neg; + + b->d = tmp_d; + b->top = tmp_top; + b->dmax = tmp_dmax; + b->neg = tmp_neg; + + a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); + b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); + } + + void BN_clear(BIGNUM *a) { if (a->d != NULL) @@ -513,7 +545,7 @@ void BN_clear(BIGNUM *a) a->neg=0; } -BN_ULONG BN_get_word(BIGNUM *a) +BN_ULONG BN_get_word(const BIGNUM *a) { int i,n; BN_ULONG ret=0; @@ -561,7 +593,6 @@ int BN_set_word(BIGNUM *a, BN_ULONG w) return(1); } -/* ignore negative */ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) { unsigned int i,m; @@ -582,6 +613,7 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) i=((n-1)/BN_BYTES)+1; m=((n-1)%(BN_BYTES)); ret->top=i; + ret->neg=0; while (n-- > 0) { l=(l<<8L)| *(s++); @@ -736,7 +768,7 @@ int BN_mask_bits(BIGNUM *a, int n) return(1); } -int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n) +int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) { int i; BN_ULONG aa,bb; @@ -753,3 +785,34 @@ int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n) return(0); } +/* Here follows a specialised variants of bn_cmp_words(). It has the + property of performing the operation on arrays of different sizes. + The sizes of those arrays is expressed through cl, which is the + common length ( basicall, min(len(a),len(b)) ), and dl, which is the + delta between the two lengths, calculated as len(a)-len(b). + All lengths are the number of BN_ULONGs... */ + +int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, + int cl, int dl) + { + int n,i; + n = cl-1; + + if (dl < 0) + { + for (i=dl; i<0; i++) + { + if (b[n-i] != 0) + return -1; /* a < b */ + } + } + if (dl > 0) + { + for (i=dl; i>0; i--) + { + if (a[n+i] != 0) + return 1; /* a > b */ + } + } + return bn_cmp_words(a,b,cl); + } diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c index 8cf1febacc..7f8296c893 100644 --- a/crypto/bn/bn_mont.c +++ b/crypto/bn/bn_mont.c @@ -69,20 +69,17 @@ #define MONT_WORD /* use the faster word-based algorithm */ -int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b, +int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_MONT_CTX *mont, BN_CTX *ctx) { - BIGNUM *tmp,*tmp2; + BIGNUM *tmp; int ret=0; BN_CTX_start(ctx); tmp = BN_CTX_get(ctx); - tmp2 = BN_CTX_get(ctx); - if (tmp == NULL || tmp2 == NULL) goto err; + if (tmp == NULL) goto err; bn_check_top(tmp); - bn_check_top(tmp2); - if (a == b) { if (!BN_sqr(tmp,a,ctx)) goto err; @@ -99,7 +96,7 @@ err: return(ret); } -int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont, +int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx) { int retn=0; @@ -144,7 +141,7 @@ int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont, n0=mont->n0; #ifdef BN_COUNT - printf("word BN_from_montgomery %d * %d\n",nl,nl); + fprintf(stderr,"word BN_from_montgomery %d * %d\n",nl,nl); #endif for (i=0; i<nl; i++) { diff --git a/crypto/bn/bn_mpi.c b/crypto/bn/bn_mpi.c index 80e1dca6b7..05fa9d1e9a 100644 --- a/crypto/bn/bn_mpi.c +++ b/crypto/bn/bn_mpi.c @@ -88,7 +88,7 @@ int BN_bn2mpi(const BIGNUM *a, unsigned char *d) return(num+4+ext); } -BIGNUM *BN_mpi2bn(unsigned char *d, int n, BIGNUM *a) +BIGNUM *BN_mpi2bn(const unsigned char *d, int n, BIGNUM *a) { long len; int neg=0; diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c index 3e8d8b9567..eb5d525613 100644 --- a/crypto/bn/bn_mul.c +++ b/crypto/bn/bn_mul.c @@ -56,10 +56,323 @@ * [including the GNU Public Licence.] */ +#ifndef BN_DEBUG +# undef NDEBUG /* avoid conflicting definitions */ +# define NDEBUG +#endif + #include <stdio.h> +#include <assert.h> #include "cryptlib.h" #include "bn_lcl.h" +/* Here follows specialised variants of bn_add_words() and + bn_sub_words(). They have the property performing operations on + arrays of different sizes. The sizes of those arrays is expressed through + cl, which is the common length ( basicall, min(len(a),len(b)) ), and dl, + which is the delta between the two lengths, calculated as len(a)-len(b). + All lengths are the number of BN_ULONGs... For the operations that require + a result array as parameter, it must have the length cl+abs(dl). + These functions should probably end up in bn_asm.c as soon as there are + assembler counterparts for the systems that use assembler files. */ + +BN_ULONG bn_sub_part_words(BN_ULONG *r, + const BN_ULONG *a, const BN_ULONG *b, + int cl, int dl) + { + BN_ULONG c, t; + + assert(cl >= 0); + c = bn_sub_words(r, a, b, cl); + + if (dl == 0) + return c; + + r += cl; + a += cl; + b += cl; + + if (dl < 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); +#endif + for (;;) + { + t = b[0]; + r[0] = (0-t-c)&BN_MASK2; + if (t != 0) c=1; + if (++dl >= 0) break; + + t = b[1]; + r[1] = (0-t-c)&BN_MASK2; + if (t != 0) c=1; + if (++dl >= 0) break; + + t = b[2]; + r[2] = (0-t-c)&BN_MASK2; + if (t != 0) c=1; + if (++dl >= 0) break; + + t = b[3]; + r[3] = (0-t-c)&BN_MASK2; + if (t != 0) c=1; + if (++dl >= 0) break; + + b += 4; + r += 4; + } + } + else + { + int save_dl = dl; +#ifdef BN_COUNT + fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", cl, dl, c); +#endif + while(c) + { + t = a[0]; + r[0] = (t-c)&BN_MASK2; + if (t != 0) c=0; + if (--dl <= 0) break; + + t = a[1]; + r[1] = (t-c)&BN_MASK2; + if (t != 0) c=0; + if (--dl <= 0) break; + + t = a[2]; + r[2] = (t-c)&BN_MASK2; + if (t != 0) c=0; + if (--dl <= 0) break; + + t = a[3]; + r[3] = (t-c)&BN_MASK2; + if (t != 0) c=0; + if (--dl <= 0) break; + + save_dl = dl; + a += 4; + r += 4; + } + if (dl > 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); +#endif + if (save_dl > dl) + { + switch (save_dl - dl) + { + case 1: + r[1] = a[1]; + if (--dl <= 0) break; + case 2: + r[2] = a[2]; + if (--dl <= 0) break; + case 3: + r[3] = a[3]; + if (--dl <= 0) break; + } + a += 4; + r += 4; + } + } + if (dl > 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, copy)\n", cl, dl); +#endif + for(;;) + { + r[0] = a[0]; + if (--dl <= 0) break; + r[1] = a[1]; + if (--dl <= 0) break; + r[2] = a[2]; + if (--dl <= 0) break; + r[3] = a[3]; + if (--dl <= 0) break; + + a += 4; + r += 4; + } + } + } + return c; + } + +BN_ULONG bn_add_part_words(BN_ULONG *r, + const BN_ULONG *a, const BN_ULONG *b, + int cl, int dl) + { + BN_ULONG c, l, t; + + assert(cl >= 0); + c = bn_add_words(r, a, b, cl); + + if (dl == 0) + return c; + + r += cl; + a += cl; + b += cl; + + if (dl < 0) + { + int save_dl = dl; +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); +#endif + while (c) + { + l=(c+b[0])&BN_MASK2; + c=(l < c); + r[0]=l; + if (++dl >= 0) break; + + l=(c+b[1])&BN_MASK2; + c=(l < c); + r[1]=l; + if (++dl >= 0) break; + + l=(c+b[2])&BN_MASK2; + c=(l < c); + r[2]=l; + if (++dl >= 0) break; + + l=(c+b[3])&BN_MASK2; + c=(l < c); + r[3]=l; + if (++dl >= 0) break; + + save_dl = dl; + b+=4; + r+=4; + } + if (dl < 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c == 0)\n", cl, dl); +#endif + if (save_dl < dl) + { + switch (dl - save_dl) + { + case 1: + r[1] = b[1]; + if (++dl >= 0) break; + case 2: + r[2] = b[2]; + if (++dl >= 0) break; + case 3: + r[3] = b[3]; + if (++dl >= 0) break; + } + b += 4; + r += 4; + } + } + if (dl < 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, copy)\n", cl, dl); +#endif + for(;;) + { + r[0] = b[0]; + if (++dl >= 0) break; + r[1] = b[1]; + if (++dl >= 0) break; + r[2] = b[2]; + if (++dl >= 0) break; + r[3] = b[3]; + if (++dl >= 0) break; + + b += 4; + r += 4; + } + } + } + else + { + int save_dl = dl; +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl > 0)\n", cl, dl); +#endif + while (c) + { + t=(a[0]+c)&BN_MASK2; + c=(t < c); + r[0]=t; + if (--dl <= 0) break; + + t=(a[1]+c)&BN_MASK2; + c=(t < c); + r[1]=t; + if (--dl <= 0) break; + + t=(a[2]+c)&BN_MASK2; + c=(t < c); + r[2]=t; + if (--dl <= 0) break; + + t=(a[3]+c)&BN_MASK2; + c=(t < c); + r[3]=t; + if (--dl <= 0) break; + + save_dl = dl; + a+=4; + r+=4; + } +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); +#endif + if (dl > 0) + { + if (save_dl > dl) + { + switch (save_dl - dl) + { + case 1: + r[1] = a[1]; + if (--dl <= 0) break; + case 2: + r[2] = a[2]; + if (--dl <= 0) break; + case 3: + r[3] = a[3]; + if (--dl <= 0) break; + } + a += 4; + r += 4; + } + } + if (dl > 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, copy)\n", cl, dl); +#endif + for(;;) + { + r[0] = a[0]; + if (--dl <= 0) break; + r[1] = a[1]; + if (--dl <= 0) break; + r[2] = a[2]; + if (--dl <= 0) break; + r[3] = a[3]; + if (--dl <= 0) break; + + a += 4; + r += 4; + } + } + } + return c; + } + #ifdef BN_RECURSION /* Karatsuba recursive multiplication algorithm * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ @@ -75,14 +388,15 @@ * a[1]*b[1] */ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, - BN_ULONG *t) + int dna, int dnb, BN_ULONG *t) { int n=n2/2,c1,c2; + int tna=n+dna, tnb=n+dnb; unsigned int neg,zero; BN_ULONG ln,lo,*p; # ifdef BN_COUNT - printf(" bn_mul_recursive %d * %d\n",n2,n2); + fprintf(stderr," bn_mul_recursive %d * %d\n",n2,n2); # endif # ifdef BN_MUL_COMBA # if 0 @@ -105,21 +419,21 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, return; } /* r=(a[0]-a[1])*(b[1]-b[0]) */ - c1=bn_cmp_words(a,&(a[n]),n); - c2=bn_cmp_words(&(b[n]),b,n); + c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); + c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); zero=neg=0; switch (c1*3+c2) { case -4: - bn_sub_words(t, &(a[n]),a, n); /* - */ - bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */ + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ break; case -3: zero=1; break; case -2: - bn_sub_words(t, &(a[n]),a, n); /* - */ - bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */ + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ neg=1; break; case -1: @@ -128,16 +442,16 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, zero=1; break; case 2: - bn_sub_words(t, a, &(a[n]),n); /* + */ - bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */ + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ neg=1; break; case 3: zero=1; break; case 4: - bn_sub_words(t, a, &(a[n]),n); - bn_sub_words(&(t[n]),&(b[n]),b, n); + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); break; } @@ -167,11 +481,11 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, { p= &(t[n2*2]); if (!zero) - bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p); + bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); else memset(&(t[n2]),0,n2*sizeof(BN_ULONG)); - bn_mul_recursive(r,a,b,n,p); - bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,p); + bn_mul_recursive(r,a,b,n,0,0,p); + bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,dna,dnb,p); } /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign @@ -220,39 +534,39 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, /* n+tn is the word length * t needs to be n*4 is size, as does r */ -void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn, - int n, BN_ULONG *t) +void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, + int tna, int tnb, BN_ULONG *t) { int i,j,n2=n*2; unsigned int c1,c2,neg,zero; BN_ULONG ln,lo,*p; # ifdef BN_COUNT - printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n); + fprintf(stderr," bn_mul_part_recursive (%d+%d) * (%d+%d)\n", + tna, n, tnb, n); # endif if (n < 8) { - i=tn+n; - bn_mul_normal(r,a,i,b,i); + bn_mul_normal(r,a,n+tna,b,n+tnb); return; } /* r=(a[0]-a[1])*(b[1]-b[0]) */ - c1=bn_cmp_words(a,&(a[n]),n); - c2=bn_cmp_words(&(b[n]),b,n); + c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); + c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); zero=neg=0; switch (c1*3+c2) { case -4: - bn_sub_words(t, &(a[n]),a, n); /* - */ - bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */ + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ break; case -3: zero=1; /* break; */ case -2: - bn_sub_words(t, &(a[n]),a, n); /* - */ - bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */ + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ neg=1; break; case -1: @@ -261,16 +575,16 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn, zero=1; /* break; */ case 2: - bn_sub_words(t, a, &(a[n]),n); /* + */ - bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */ + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ neg=1; break; case 3: zero=1; /* break; */ case 4: - bn_sub_words(t, a, &(a[n]),n); - bn_sub_words(&(t[n]),&(b[n]),b, n); + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); break; } /* The zero case isn't yet implemented here. The speedup @@ -289,54 +603,59 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn, { bn_mul_comba8(&(t[n2]),t,&(t[n])); bn_mul_comba8(r,a,b); - bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn); - memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2)); + bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); + memset(&(r[n2+tna+tnb]),0,sizeof(BN_ULONG)*(n2-tna-tnb)); } else { p= &(t[n2*2]); - bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p); - bn_mul_recursive(r,a,b,n,p); + bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); + bn_mul_recursive(r,a,b,n,0,0,p); i=n/2; /* If there is only a bottom half to the number, * just do it */ - j=tn-i; + if (tna > tnb) + j = tna - i; + else + j = tnb - i; if (j == 0) { - bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p); + bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]), + i,tna-i,tnb-i,p); memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2)); } else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */ { bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]), - j,i,p); - memset(&(r[n2+tn*2]),0, - sizeof(BN_ULONG)*(n2-tn*2)); + i,tna-i,tnb-i,p); + memset(&(r[n2+tna+tnb]),0, + sizeof(BN_ULONG)*(n2-tna-tnb)); } else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ { memset(&(r[n2]),0,sizeof(BN_ULONG)*n2); - if (tn < BN_MUL_RECURSIVE_SIZE_NORMAL) + if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL + && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { - bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn); + bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); } else { for (;;) { i/=2; - if (i < tn) + if (i < tna && i < tnb) { bn_mul_part_recursive(&(r[n2]), &(a[n]),&(b[n]), - tn-i,i,p); + i,tna-i,tnb-i,p); break; } - else if (i == tn) + else if (i <= tna && i <= tnb) { bn_mul_recursive(&(r[n2]), &(a[n]),&(b[n]), - i,p); + i,tna-i,tnb-i,p); break; } } @@ -397,10 +716,10 @@ void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, int n=n2/2; # ifdef BN_COUNT - printf(" bn_mul_low_recursive %d * %d\n",n2,n2); + fprintf(stderr," bn_mul_low_recursive %d * %d\n",n2,n2); # endif - bn_mul_recursive(r,a,b,n,&(t[0])); + bn_mul_recursive(r,a,b,n,0,0,&(t[0])); if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) { bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2])); @@ -431,7 +750,7 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, BN_ULONG ll,lc,*lp,*mp; # ifdef BN_COUNT - printf(" bn_mul_high %d * %d\n",n2,n2); + fprintf(stderr," bn_mul_high %d * %d\n",n2,n2); # endif n=n2/2; @@ -484,8 +803,8 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, else # endif { - bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2])); - bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2])); + bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,0,0,&(t[n2])); + bn_mul_recursive(r,&(a[n]),&(b[n]),n,0,0,&(t[n2])); } /* s0 == low(al*bl) @@ -608,11 +927,11 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, } #endif /* BN_RECURSION */ -int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) +int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { + int ret=0; int top,al,bl; BIGNUM *rr; - int ret = 0; #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) int i; #endif @@ -622,7 +941,7 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) #endif #ifdef BN_COUNT - printf("BN_mul %d * %d\n",a->top,b->top); + fprintf(stderr,"BN_mul %d * %d\n",a->top,b->top); #endif bn_check_top(a); @@ -675,17 +994,55 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) #ifdef BN_RECURSION if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) { + if (i >= -1 && i <= 1) + { + int sav_j =0; + /* Find out the power of two lower or equal + to the longest of the two numbers */ + if (i >= 0) + { + j = BN_num_bits_word((BN_ULONG)al); + } + if (i == -1) + { + j = BN_num_bits_word((BN_ULONG)bl); + } + sav_j = j; + j = 1<<(j-1); + assert(j <= al || j <= bl); + k = j+j; + t = BN_CTX_get(ctx); + if (al > j || bl > j) + { + bn_wexpand(t,k*4); + bn_wexpand(rr,k*4); + bn_mul_part_recursive(rr->d,a->d,b->d, + j,al-j,bl-j,t->d); + } + else /* al <= j || bl <= j */ + { + bn_wexpand(t,k*2); + bn_wexpand(rr,k*2); + bn_mul_recursive(rr->d,a->d,b->d, + j,al-j,bl-j,t->d); + } + rr->top=top; + goto end; + } +#if 0 if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA)) { - bn_wexpand(b,al); - b->d[bl]=0; + BIGNUM *tmp_bn = (BIGNUM *)b; + bn_wexpand(tmp_bn,al); + tmp_bn->d[bl]=0; bl++; i--; } else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA)) { - bn_wexpand(a,bl); - a->d[al]=0; + BIGNUM *tmp_bn = (BIGNUM *)a; + bn_wexpand(tmp_bn,bl); + tmp_bn->d[al]=0; al++; i++; } @@ -705,19 +1062,14 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) } else { - bn_wexpand(a,k); - bn_wexpand(b,k); bn_wexpand(t,k*4); bn_wexpand(rr,k*4); - for (i=a->top; i<k; i++) - a->d[i]=0; - for (i=b->top; i<k; i++) - b->d[i]=0; bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d); } rr->top=top; goto end; } +#endif } #endif /* BN_RECURSION */ if (bn_wexpand(rr,top) == NULL) goto err; @@ -740,7 +1092,7 @@ void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) BN_ULONG *rr; #ifdef BN_COUNT - printf(" bn_mul_normal %d * %d\n",na,nb); + fprintf(stderr," bn_mul_normal %d * %d\n",na,nb); #endif if (na < nb) @@ -774,7 +1126,7 @@ void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) { #ifdef BN_COUNT - printf(" bn_mul_low_normal %d * %d\n",n,n); + fprintf(stderr," bn_mul_low_normal %d * %d\n",n,n); #endif bn_mul_words(r,a,n,b[0]); diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index a5f01b92eb..b75e58c6ae 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -125,12 +125,13 @@ static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, const BIGNUM *a1_odd, int k, BN_CTX *ctx, 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); + const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); static int probable_prime_dh_safe(BIGNUM *rnd, int bits, - BIGNUM *add, BIGNUM *rem, BN_CTX *ctx); + const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); -BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int safe, BIGNUM *add, - BIGNUM *rem, void (*callback)(int,int,void *), void *cb_arg) +BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int safe, + const BIGNUM *add, const BIGNUM *rem, + void (*callback)(int,int,void *), void *cb_arg) { BIGNUM *rnd=NULL; BIGNUM t; @@ -376,8 +377,8 @@ again: return(1); } -static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem, - BN_CTX *ctx) +static int probable_prime_dh(BIGNUM *rnd, int bits, + const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) { int i,ret=0; BIGNUM *t1; @@ -413,8 +414,8 @@ err: return(ret); } -static int probable_prime_dh_safe(BIGNUM *p, int bits, BIGNUM *padd, - BIGNUM *rem, BN_CTX *ctx) +static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, + const BIGNUM *rem, BN_CTX *ctx) { int i,ret=0; BIGNUM *t1,*qadd,*q; diff --git a/crypto/bn/bn_print.c b/crypto/bn/bn_print.c index 532e66bcc3..d1986d72d0 100644 --- a/crypto/bn/bn_print.c +++ b/crypto/bn/bn_print.c @@ -321,7 +321,7 @@ end: #endif #ifdef BN_DEBUG -void bn_dump1(FILE *o, const char *a, BN_ULONG *b,int n) +void bn_dump1(FILE *o, const char *a, const BN_ULONG *b,int n) { int i; fprintf(o, "%s=", a); diff --git a/crypto/bn/bn_rand.c b/crypto/bn/bn_rand.c index 21ecbc04ed..bab4510345 100644 --- a/crypto/bn/bn_rand.c +++ b/crypto/bn/bn_rand.c @@ -100,6 +100,27 @@ static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom) goto err; } +#if 1 + if (pseudorand == 2) + { + /* generate patterns that are more likely to trigger BN + library bugs */ + int i; + unsigned char c; + + for (i = 0; i < bytes; i++) + { + RAND_pseudo_bytes(&c, 1); + if (c >= 128 && i > 0) + buf[i] = buf[i-1]; + else if (c < 42) + buf[i] = 0; + else if (c < 84) + buf[i] = 255; + } + } +#endif + if (top) { if (bit == 0) @@ -140,3 +161,10 @@ int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) { return bnrand(1, rnd, bits, top, bottom); } + +#if 1 +int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) + { + return bnrand(2, rnd, bits, top, bottom); + } +#endif diff --git a/crypto/bn/bn_recp.c b/crypto/bn/bn_recp.c index d019941d6b..0700a0f063 100644 --- a/crypto/bn/bn_recp.c +++ b/crypto/bn/bn_recp.c @@ -100,11 +100,12 @@ int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx) return(1); } -int BN_mod_mul_reciprocal(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_RECP_CTX *recp, - BN_CTX *ctx) +int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, + BN_RECP_CTX *recp, BN_CTX *ctx) { int ret=0; BIGNUM *a; + const BIGNUM *ca; BN_CTX_start(ctx); if ((a = BN_CTX_get(ctx)) == NULL) goto err; @@ -114,19 +115,20 @@ int BN_mod_mul_reciprocal(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_RECP_CTX *recp, { if (!BN_sqr(a,x,ctx)) goto err; } else { if (!BN_mul(a,x,y,ctx)) goto err; } + ca = a; } else - a=x; /* Just do the mod */ + ca=x; /* Just do the mod */ - BN_div_recp(NULL,r,a,recp,ctx); + BN_div_recp(NULL,r,ca,recp,ctx); ret=1; err: BN_CTX_end(ctx); return(ret); } -int BN_div_recp(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BN_RECP_CTX *recp, - BN_CTX *ctx) +int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, + BN_RECP_CTX *recp, BN_CTX *ctx) { int i,j,ret=0; BIGNUM *a,*b,*d,*r; @@ -165,7 +167,8 @@ int BN_div_recp(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BN_RECP_CTX *recp, if (i != recp->shift) recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N), - i,ctx); + i,ctx); /* BN_reciprocal returns i, or -1 for an error */ + if (recp->shift == -1) goto err; if (!BN_rshift(a,m,j)) goto err; if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err; @@ -201,7 +204,8 @@ err: * We actually calculate with an extra word of precision, so * we can do faster division if the remainder is not required. */ -int BN_reciprocal(BIGNUM *r, BIGNUM *m, int len, BN_CTX *ctx) +/* r := 2^len / m */ +int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) { int ret= -1; BIGNUM t; diff --git a/crypto/bn/bn_shift.c b/crypto/bn/bn_shift.c index 0883247384..70f785ea18 100644 --- a/crypto/bn/bn_shift.c +++ b/crypto/bn/bn_shift.c @@ -60,7 +60,7 @@ #include "cryptlib.h" #include "bn_lcl.h" -int BN_lshift1(BIGNUM *r, BIGNUM *a) +int BN_lshift1(BIGNUM *r, const BIGNUM *a) { register BN_ULONG *ap,*rp,t,c; int i; @@ -92,7 +92,7 @@ int BN_lshift1(BIGNUM *r, BIGNUM *a) return(1); } -int BN_rshift1(BIGNUM *r, BIGNUM *a) +int BN_rshift1(BIGNUM *r, const BIGNUM *a) { BN_ULONG *ap,*rp,t,c; int i; @@ -128,8 +128,8 @@ int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) BN_ULONG l; r->neg=a->neg; - if (bn_wexpand(r,a->top+(n/BN_BITS2)+1) == NULL) return(0); nw=n/BN_BITS2; + if (bn_wexpand(r,a->top+nw+1) == NULL) return(0); lb=n%BN_BITS2; rb=BN_BITS2-lb; f=a->d; @@ -153,7 +153,7 @@ int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) return(1); } -int BN_rshift(BIGNUM *r, BIGNUM *a, int n) +int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) { int i,j,nw,lb,rb; BN_ULONG *t,*f; @@ -172,6 +172,11 @@ int BN_rshift(BIGNUM *r, BIGNUM *a, int n) r->neg=a->neg; if (bn_wexpand(r,a->top-nw+1) == NULL) return(0); } + else + { + if (n == 0) + return 1; /* or the copying loop will go berserk */ + } f= &(a->d[nw]); t=r->d; diff --git a/crypto/bn/bn_sqr.c b/crypto/bn/bn_sqr.c index 75f4f38392..b75e6194d0 100644 --- a/crypto/bn/bn_sqr.c +++ b/crypto/bn/bn_sqr.c @@ -62,14 +62,14 @@ /* r must not be a */ /* I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 */ -int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx) +int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) { int max,al; int ret = 0; BIGNUM *tmp,*rr; #ifdef BN_COUNT -printf("BN_sqr %d * %d\n",a->top,a->top); + fprintf(stderr,"BN_sqr %d * %d\n",a->top,a->top); #endif bn_check_top(a); @@ -88,7 +88,6 @@ printf("BN_sqr %d * %d\n",a->top,a->top); max=(al+al); if (bn_wexpand(rr,max+1) == NULL) goto err; - r->neg=0; if (al == 4) { #ifndef BN_SQR_COMBA @@ -124,7 +123,6 @@ printf("BN_sqr %d * %d\n",a->top,a->top); k=j+j; if (al == j) { - if (bn_wexpand(a,k*2) == NULL) goto err; if (bn_wexpand(tmp,k*2) == NULL) goto err; bn_sqr_recursive(rr->d,a->d,al,tmp->d); } @@ -141,6 +139,7 @@ printf("BN_sqr %d * %d\n",a->top,a->top); } rr->top=max; + rr->neg=0; if ((max > 0) && (rr->d[max-1] == 0)) rr->top--; if (rr != r) BN_copy(r,rr); ret = 1; @@ -150,10 +149,11 @@ printf("BN_sqr %d * %d\n",a->top,a->top); } /* tmp must have 2*n words */ -void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp) +void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp) { int i,j,max; - BN_ULONG *ap,*rp; + const BN_ULONG *ap; + BN_ULONG *rp; max=n*2; ap=a; @@ -197,14 +197,14 @@ void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp) * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) * a[1]*b[1] */ -void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *t) +void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t) { int n=n2/2; int zero,c1; BN_ULONG ln,lo,*p; #ifdef BN_COUNT -printf(" bn_sqr_recursive %d * %d\n",n2,n2); + fprintf(stderr," bn_sqr_recursive %d * %d\n",n2,n2); #endif if (n2 == 4) { diff --git a/crypto/bn/bn_sqrt.c b/crypto/bn/bn_sqrt.c index a54d9d2919..2a72c189cb 100644 --- a/crypto/bn/bn_sqrt.c +++ b/crypto/bn/bn_sqrt.c @@ -93,20 +93,6 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) return(NULL); } - if (BN_is_zero(a) || BN_is_one(a)) - { - if (ret == NULL) - ret = BN_new(); - if (ret == NULL) - goto end; - if (!BN_set_word(ret, BN_is_one(a))) - { - BN_free(ret); - return NULL; - } - return ret; - } - #if 0 /* if BN_mod_sqrt is used with correct input, this just wastes time */ r = BN_kronecker(a, p, ctx); if (r < -1) return NULL; @@ -133,9 +119,7 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) e = 1; while (!BN_is_bit_set(p, e)) e++; - if (e > 2) - /* we don't need this q if e = 1 or 2 */ - if (!BN_rshift(q, p, e)) goto end; + if (!BN_rshift(q, p, e)) goto end; q->neg = 0; if (e == 1) @@ -145,74 +129,16 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) * directly by modular exponentiation. * We have * 2 * (p+1)/4 == 1 (mod (p-1)/2), - * so we can use exponent (p+1)/4, i.e. (p-3)/4 + 1. + * so we can use exponent (p+1)/4, i.e. (q+1)/2. */ - if (!BN_rshift(q, p, 2)) goto end; - if (!BN_add_word(q, 1)) goto end; + if (!BN_add_word(q,1)) goto end; + if (!BN_rshift1(q,q)) goto end; if (!BN_mod_exp(ret, a, q, p, ctx)) goto end; err = 0; goto end; } - if (e == 2) - { - /* p == 5 (mod 8) - * - * In this case 2 is always a non-square since - * Legendre(2,p) = (-1)^((p^2-1)/8) for any odd prime. - * So if a really is a square, then 2*a is a non-square. - * Thus for - * b := (2*a)^((p-5)/8), - * i := (2*a)*b^2 - * we have - * i^2 = (2*a)^((1 + (p-5)/4)*2) - * = (2*a)^((p-1)/2) - * = -1; - * so if we set - * x := a*b*(i-1), - * then - * x^2 = a^2 * b^2 * (i^2 - 2*i + 1) - * = a^2 * b^2 * (-2*i) - * = a*(-i)*(2*a*b^2) - * = a*(-i)*i - * = a. - * - * (This is due to A.O.L. Atkin, - * <URL: http://listserv.nodak.edu/scripts/wa.exe?A2=ind9211&L=nmbrthry&O=T&P=562>, - * November 1992.) - */ - - /* make sure that a is reduced modulo p */ - if (a->neg || BN_ucmp(a, p) >= 0) - { - if (!BN_nnmod(x, a, p, ctx)) goto end; - a = x; /* use x as temporary variable */ - } - - /* t := 2*a */ - if (!BN_mod_lshift1_quick(t, a, p)) goto end; - - /* b := (2*a)^((p-5)/8) */ - if (!BN_rshift(q, p, 3)) goto end; - if (!BN_mod_exp(b, t, q, p, ctx)) goto end; - - /* y := b^2 */ - if (!BN_mod_sqr(y, b, p, ctx)) goto end; - - /* t := (2*a)*b^2 - 1*/ - if (!BN_mod_mul(t, t, y, p, ctx)) goto end; - if (!BN_sub_word(t, 1)) goto end; /* cannot become negative */ - - /* x = a*b*t */ - if (!BN_mod_mul(x, a, b, p, ctx)) goto end; - if (!BN_mod_mul(x, x, t, p, ctx)) goto end; - - if (!BN_copy(ret, x)) goto end; - err = 0; - goto end; - } - - /* e > 2, so we really have to use the Tonelli/Shanks algorithm. + /* e > 1, so we really have to use the Tonelli/Shanks algorithm. * First, find some y that is not a square. */ i = 2; do diff --git a/crypto/bn/bntest.c b/crypto/bn/bntest.c index 0a97af69c5..91563dd222 100644 --- a/crypto/bn/bntest.c +++ b/crypto/bn/bntest.c @@ -91,6 +91,8 @@ int test_mod(BIO *bp,BN_CTX *ctx); int test_mod_mul(BIO *bp,BN_CTX *ctx); int test_mod_exp(BIO *bp,BN_CTX *ctx); int test_exp(BIO *bp,BN_CTX *ctx); +int test_kron(BIO *bp,BN_CTX *ctx); +int test_sqrt(BIO *bp,BN_CTX *ctx); int rand_neg(void); static int results=0; @@ -122,9 +124,7 @@ int main(int argc, char *argv[]) results = 0; - RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_rand may fail, and we don't - * even check its return value - * (which we should) */ + RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */ argc--; argv++; @@ -228,6 +228,14 @@ int main(int argc, char *argv[]) if (!test_exp(out,ctx)) goto err; BIO_flush(out); + message(out,"BN_kronecker"); + if (!test_kron(out,ctx)) goto err; + BIO_flush(out); + + message(out,"BN_mod_sqrt"); + if (!test_sqrt(out,ctx)) goto err; + BIO_flush(out); + BN_CTX_free(ctx); BIO_free(out); @@ -247,21 +255,17 @@ int test_add(BIO *bp) { BIGNUM a,b,c; int i; - int j; BN_init(&a); BN_init(&b); BN_init(&c); - BN_rand(&a,512,0,0); + BN_bntest_rand(&a,512,0,0); for (i=0; i<num0; i++) { - BN_rand(&b,450+i,0,0); + BN_bntest_rand(&b,450+i,0,0); a.neg=rand_neg(); b.neg=rand_neg(); - if (bp == NULL) - for (j=0; j<10000; j++) - BN_add(&c,&a,&b); BN_add(&c,&a,&b); if (bp != NULL) { @@ -295,7 +299,6 @@ int test_sub(BIO *bp) { BIGNUM a,b,c; int i; - int j; BN_init(&a); BN_init(&b); @@ -305,20 +308,17 @@ int test_sub(BIO *bp) { if (i < num1) { - BN_rand(&a,512,0,0); + BN_bntest_rand(&a,512,0,0); BN_copy(&b,&a); if (BN_set_bit(&a,i)==0) return(0); BN_add_word(&b,i); } else { - BN_rand(&b,400+i-num1,0,0); + BN_bntest_rand(&b,400+i-num1,0,0); a.neg=rand_neg(); b.neg=rand_neg(); } - if (bp == NULL) - for (j=0; j<10000; j++) - BN_sub(&c,&a,&b); BN_sub(&c,&a,&b); if (bp != NULL) { @@ -350,7 +350,6 @@ int test_div(BIO *bp, BN_CTX *ctx) { BIGNUM a,b,c,d,e; int i; - int j; BN_init(&a); BN_init(&b); @@ -362,18 +361,15 @@ int test_div(BIO *bp, BN_CTX *ctx) { if (i < num1) { - BN_rand(&a,400,0,0); + BN_bntest_rand(&a,400,0,0); BN_copy(&b,&a); BN_lshift(&a,&a,i); BN_add_word(&a,i); } else - BN_rand(&b,50+3*(i-num1),0,0); + BN_bntest_rand(&b,50+3*(i-num1),0,0); a.neg=rand_neg(); b.neg=rand_neg(); - if (bp == NULL) - for (j=0; j<100; j++) - BN_div(&d,&c,&a,&b,ctx); BN_div(&d,&c,&a,&b,ctx); if (bp != NULL) { @@ -419,7 +415,6 @@ int test_div_recp(BIO *bp, BN_CTX *ctx) BIGNUM a,b,c,d,e; BN_RECP_CTX recp; int i; - int j; BN_RECP_CTX_init(&recp); BN_init(&a); @@ -432,19 +427,16 @@ int test_div_recp(BIO *bp, BN_CTX *ctx) { if (i < num1) { - BN_rand(&a,400,0,0); + BN_bntest_rand(&a,400,0,0); BN_copy(&b,&a); BN_lshift(&a,&a,i); BN_add_word(&a,i); } else - BN_rand(&b,50+3*(i-num1),0,0); + BN_bntest_rand(&b,50+3*(i-num1),0,0); a.neg=rand_neg(); b.neg=rand_neg(); BN_RECP_CTX_set(&recp,&b,ctx); - if (bp == NULL) - for (j=0; j<100; j++) - BN_div_recp(&d,&c,&a,&recp,ctx); BN_div_recp(&d,&c,&a,&recp,ctx); if (bp != NULL) { @@ -495,7 +487,6 @@ int test_mul(BIO *bp) { BIGNUM a,b,c,d,e; int i; - int j; BN_CTX ctx; BN_CTX_init(&ctx); @@ -509,16 +500,13 @@ int test_mul(BIO *bp) { if (i <= num1) { - BN_rand(&a,100,0,0); - BN_rand(&b,100,0,0); + BN_bntest_rand(&a,100,0,0); + BN_bntest_rand(&b,100,0,0); } else - BN_rand(&b,i-num1,0,0); + BN_bntest_rand(&b,i-num1,0,0); a.neg=rand_neg(); b.neg=rand_neg(); - if (bp == NULL) - for (j=0; j<100; j++) - BN_mul(&c,&a,&b,&ctx); BN_mul(&c,&a,&b,&ctx); if (bp != NULL) { @@ -553,7 +541,6 @@ int test_sqr(BIO *bp, BN_CTX *ctx) { BIGNUM a,c,d,e; int i; - int j; BN_init(&a); BN_init(&c); @@ -562,11 +549,8 @@ int test_sqr(BIO *bp, BN_CTX *ctx) for (i=0; i<num0; i++) { - BN_rand(&a,40+i*10,0,0); + BN_bntest_rand(&a,40+i*10,0,0); a.neg=rand_neg(); - if (bp == NULL) - for (j=0; j<100; j++) - BN_sqr(&c,&a,ctx); BN_sqr(&c,&a,ctx); if (bp != NULL) { @@ -600,7 +584,6 @@ int test_mont(BIO *bp, BN_CTX *ctx) BIGNUM a,b,c,d,A,B; BIGNUM n; int i; - int j; BN_MONT_CTX *mont; BN_init(&a); @@ -613,23 +596,23 @@ int test_mont(BIO *bp, BN_CTX *ctx) mont=BN_MONT_CTX_new(); - BN_rand(&a,100,0,0); /**/ - BN_rand(&b,100,0,0); /**/ + BN_bntest_rand(&a,100,0,0); /**/ + BN_bntest_rand(&b,100,0,0); /**/ for (i=0; i<num2; i++) { int bits = (200*(i+1))/num2; if (bits == 0) continue; - BN_rand(&n,bits,0,1); + BN_bntest_rand(&n,bits,0,1); BN_MONT_CTX_set(mont,&n,ctx); + BN_nnmod(&a,&a,&n,ctx); + BN_nnmod(&b,&b,&n,ctx); + BN_to_montgomery(&A,&a,mont,ctx); BN_to_montgomery(&B,&b,mont,ctx); - if (bp == NULL) - for (j=0; j<100; j++) - BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/ BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/ BN_from_montgomery(&A,&c,mont,ctx);/**/ if (bp != NULL) @@ -675,7 +658,6 @@ int test_mod(BIO *bp, BN_CTX *ctx) { BIGNUM *a,*b,*c,*d,*e; int i; - int j; a=BN_new(); b=BN_new(); @@ -683,15 +665,12 @@ int test_mod(BIO *bp, BN_CTX *ctx) d=BN_new(); e=BN_new(); - BN_rand(a,1024,0,0); /**/ + BN_bntest_rand(a,1024,0,0); /**/ for (i=0; i<num0; i++) { - BN_rand(b,450+i*10,0,0); /**/ + BN_bntest_rand(b,450+i*10,0,0); /**/ a->neg=rand_neg(); b->neg=rand_neg(); - if (bp == NULL) - for (j=0; j<100; j++) - BN_mod(c,a,b,ctx);/**/ BN_mod(c,a,b,ctx);/**/ if (bp != NULL) { @@ -732,17 +711,13 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx) d=BN_new(); e=BN_new(); - BN_rand(c,1024,0,0); /**/ + BN_bntest_rand(c,1024,0,0); /**/ for (i=0; i<num0; i++) { - BN_rand(a,475+i*10,0,0); /**/ - BN_rand(b,425+i*11,0,0); /**/ + BN_bntest_rand(a,475+i*10,0,0); /**/ + BN_bntest_rand(b,425+i*11,0,0); /**/ a->neg=rand_neg(); b->neg=rand_neg(); - /* if (bp == NULL) - for (j=0; j<100; j++) - BN_mod_mul(d,a,b,c,ctx);*/ /**/ - if (!BN_mod_mul(e,a,b,c,ctx)) { unsigned long l; @@ -761,6 +736,16 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx) BN_print(bp,b); BIO_puts(bp," % "); BN_print(bp,c); + if ((a->neg ^ b->neg) && !BN_is_zero(e)) + { + /* If (a*b) % c is negative, c must be added + * in order to obtain the normalized remainder + * (new with OpenSSL 0.9.7, previous versions of + * BN_mod_mul could generate negative results) + */ + BIO_puts(bp," + "); + BN_print(bp,c); + } BIO_puts(bp," - "); } BN_print(bp,e); @@ -772,6 +757,7 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx) if(!BN_is_zero(b)) { fprintf(stderr,"Modulo multiply test failed!\n"); + ERR_print_errors_fp(stderr); return 0; } } @@ -794,11 +780,11 @@ int test_mod_exp(BIO *bp, BN_CTX *ctx) d=BN_new(); e=BN_new(); - BN_rand(c,30,0,1); /* must be odd for montgomery */ + BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */ for (i=0; i<num2; i++) { - BN_rand(a,20+i*5,0,0); /**/ - BN_rand(b,2+i,0,0); /**/ + BN_bntest_rand(a,20+i*5,0,0); /**/ + BN_bntest_rand(b,2+i,0,0); /**/ if (!BN_mod_exp(d,a,b,c,ctx)) return(00); @@ -848,8 +834,8 @@ int test_exp(BIO *bp, BN_CTX *ctx) for (i=0; i<num2; i++) { - BN_rand(a,20+i*5,0,0); /**/ - BN_rand(b,2+i,0,0); /**/ + BN_bntest_rand(a,20+i*5,0,0); /**/ + BN_bntest_rand(b,2+i,0,0); /**/ if (!BN_exp(d,a,b,ctx)) return(00); @@ -884,6 +870,172 @@ int test_exp(BIO *bp, BN_CTX *ctx) return(1); } +static void genprime_cb(int p, int n, void *arg) + { + char c='*'; + + if (p == 0) c='.'; + if (p == 1) c='+'; + if (p == 2) c='*'; + if (p == 3) c='\n'; + putc(c, stderr); + fflush(stderr); + (void)n; + (void)arg; + } + +int test_kron(BIO *bp, BN_CTX *ctx) + { + BIGNUM *a,*b,*r,*t; + int i; + int legendre, kronecker; + int ret = 0; + + a = BN_new(); + b = BN_new(); + r = BN_new(); + t = BN_new(); + if (a == NULL || b == NULL || r == NULL || t == NULL) goto err; + + /* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). + * In this case we know that if b is prime, then BN_kronecker(a, b, ctx) + * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). + * So we generate a random prime b and compare these values + * for a number of random a's. (That is, we run the Solovay-Strassen + * primality test to confirm that b is prime, except that we + * don't want to test whether b is prime but whether BN_kronecker + * works.) */ + + if (!BN_generate_prime(b, 512, 0, NULL, NULL, genprime_cb, NULL)) goto err; + putc('\n', stderr); + + for (i = 0; i < num0; i++) + { + if (!BN_bntest_rand(a, 512, 0, 0)) goto err; + a->neg = rand_neg(); + + /* t := (b-1)/2 (note that b is odd) */ + if (!BN_copy(t, b)) goto err; + if (!BN_sub_word(t, 1)) goto err; + if (!BN_rshift1(t, t)) goto err; + /* r := a^t mod b */ + if (!BN_mod_exp(r, a, t, b, ctx)) goto err; + + if (BN_is_word(r, 1)) + legendre = 1; + else if (BN_is_zero(r)) + legendre = 0; + else + { + if (!BN_add_word(r, 1)) goto err; + if (0 != BN_cmp(r, b)) + { + fprintf(stderr, "Legendre symbol computation failed\n"); + goto err; + } + legendre = -1; + } + + kronecker = BN_kronecker(a, b, ctx); + if (kronecker < -1) goto err; + + if (legendre != kronecker) + { + fprintf(stderr, "legendre != kronecker; a = "); + BN_print_fp(stderr, a); + fprintf(stderr, ", b = "); + BN_print_fp(stderr, b); + fprintf(stderr, "\n"); + goto err; + } + + putc('.', stderr); + fflush(stderr); + } + + putc('\n', stderr); + fflush(stderr); + ret = 1; + err: + if (a != NULL) BN_free(a); + if (b != NULL) BN_free(b); + if (r != NULL) BN_free(r); + if (t != NULL) BN_free(t); + return ret; + } + +int test_sqrt(BIO *bp, BN_CTX *ctx) + { + BIGNUM *a,*p,*r; + int i, j; + int ret = 0; + + a = BN_new(); + p = BN_new(); + r = BN_new(); + if (a == NULL || p == NULL || r == NULL) goto err; + + for (i = 0; i < 16; i++) + { + if (i < 8) + { + unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 }; + + if (!BN_set_word(p, primes[i])) goto err; + } + else + { + if (!BN_set_word(a, 32)) goto err; + if (!BN_set_word(r, 2*i + 1)) goto err; + + if (!BN_generate_prime(p, 256, 0, a, r, genprime_cb, NULL)) goto err; + putc('\n', stderr); + } + + for (j = 0; j < num2; j++) + { + /* construct 'a' such that it is a square modulo p, + * but in general not a proper square and not reduced modulo p */ + if (!BN_bntest_rand(r, 256, 0, 3)) goto err; + if (!BN_nnmod(r, r, p, ctx)) goto err; + if (!BN_mod_sqr(r, r, p, ctx)) goto err; + if (!BN_bntest_rand(a, 256, 0, 3)) goto err; + if (!BN_nnmod(a, a, p, ctx)) goto err; + if (!BN_mod_sqr(a, a, p, ctx)) goto err; + if (!BN_mul(a, a, r, ctx)) goto err; + + if (!BN_mod_sqrt(r, a, p, ctx)) goto err; + if (!BN_mod_sqr(r, r, p, ctx)) goto err; + + if (!BN_nnmod(a, a, p, ctx)) goto err; + + if (BN_cmp(a, r) != 0) + { + fprintf(stderr, "BN_mod_sqrt failed: a = "); + BN_print_fp(stderr, a); + fprintf(stderr, ", r = "); + BN_print_fp(stderr, r); + fprintf(stderr, ", p = "); + BN_print_fp(stderr, p); + fprintf(stderr, "\n"); + goto err; + } + + putc('.', stderr); + fflush(stderr); + } + + putc('\n', stderr); + fflush(stderr); + } + ret = 1; + err: + if (a != NULL) BN_free(a); + if (p != NULL) BN_free(p); + if (r != NULL) BN_free(r); + return ret; + } + int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_) { BIGNUM *a,*b,*c,*d; @@ -899,7 +1051,7 @@ int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_) else { a=BN_new(); - BN_rand(a,200,0,0); /**/ + BN_bntest_rand(a,200,0,0); /**/ a->neg=rand_neg(); } for (i=0; i<num0; i++) @@ -951,7 +1103,7 @@ int test_lshift1(BIO *bp) b=BN_new(); c=BN_new(); - BN_rand(a,200,0,0); /**/ + BN_bntest_rand(a,200,0,0); /**/ a->neg=rand_neg(); for (i=0; i<num0; i++) { @@ -995,7 +1147,7 @@ int test_rshift(BIO *bp,BN_CTX *ctx) e=BN_new(); BN_one(c); - BN_rand(a,200,0,0); /**/ + BN_bntest_rand(a,200,0,0); /**/ a->neg=rand_neg(); for (i=0; i<num0; i++) { @@ -1038,7 +1190,7 @@ int test_rshift1(BIO *bp) b=BN_new(); c=BN_new(); - BN_rand(a,200,0,0); /**/ + BN_bntest_rand(a,200,0,0); /**/ a->neg=rand_neg(); for (i=0; i<num0; i++) { diff --git a/crypto/bn/expspeed.c b/crypto/bn/expspeed.c index 2044ab9bff..c55347e297 100644 --- a/crypto/bn/expspeed.c +++ b/crypto/bn/expspeed.c @@ -61,6 +61,28 @@ /* most of this code has been pilfered from my libdes speed.c program */ #define BASENUM 5000 +#define NUM_START 0 + + +/* determine timings for modexp, gcd, or modular inverse */ +#define TEST_EXP +#undef TEST_GCD +#undef TEST_KRON +#undef TEST_INV +#undef TEST_SQRT +#define P_MOD_64 9 /* least significant 6 bits for prime to be used for BN_sqrt timings */ + +#if defined(TEST_EXP) + defined(TEST_GCD) + defined(TEST_KRON) + defined(TEST_INV) +defined(TEST_SQRT) != 1 +# error "choose one test" +#endif + +#if defined(TEST_INV) || defined(TEST_SQRT) +# define C_PRIME +static void genprime_cb(int p, int n, void *arg); +#endif + + + #undef PROG #define PROG bnspeed_main @@ -70,6 +92,7 @@ #include <string.h> #include <openssl/crypto.h> #include <openssl/err.h> +#include <openssl/rand.h> #if !defined(MSDOS) && (!defined(VMS) || defined(__DECC)) #define TIMES @@ -161,11 +184,16 @@ static double Time_F(int s) #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}; +#define NUM_SIZES 7 +#if NUM_START > NUM_SIZES +# error "NUM_START > NUM_SIZES" +#endif +static int sizes[NUM_SIZES]={128,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,8*8*8,8*8,8,1}; /*static int sizes[NUM_SIZES]={59,179,299,419,539}; */ +#define RAND_SEED(string) { const char str[] = string; RAND_seed(string, sizeof str); } + void do_mul_exp(BIGNUM *r,BIGNUM *a,BIGNUM *b,BIGNUM *c,BN_CTX *ctx); int main(int argc, char **argv) @@ -173,13 +201,23 @@ int main(int argc, char **argv) BN_CTX *ctx; BIGNUM *a,*b,*c,*r; +#if 1 + if (!CRYPTO_set_mem_debug_functions(0,0,0,0,0)) + abort(); +#endif + ctx=BN_CTX_new(); a=BN_new(); b=BN_new(); c=BN_new(); r=BN_new(); + while (!RAND_status()) + /* not enough bits */ + RAND_SEED("I demand a manual recount!"); + do_mul_exp(r,a,b,c,ctx); + return 0; } void do_mul_exp(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *c, BN_CTX *ctx) @@ -187,29 +225,107 @@ void do_mul_exp(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++) + for (i=NUM_START; 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); +#ifdef C_PRIME +# ifdef TEST_SQRT + if (!BN_set_word(a, 64)) goto err; + if (!BN_set_word(b, P_MOD_64)) goto err; +# define ADD a +# define REM b +# else +# define ADD NULL +# define REM NULL +# endif + if (!BN_generate_prime(c,sizes[i],0,ADD,REM,genprime_cb,NULL)) goto err; + putc('\n', stderr); + fflush(stderr); +#endif - Time_F(START); for (k=0; k<num; k++) - BN_mod_exp_mont(r,a,b,c,ctx,&m); + { + if (k%50 == 0) /* Average over num/50 different choices of random numbers. */ + { + if (!BN_pseudo_rand(a,sizes[i],1,0)) goto err; + + if (!BN_pseudo_rand(b,sizes[i],1,0)) goto err; + +#ifndef C_PRIME + if (!BN_pseudo_rand(c,sizes[i],1,1)) goto err; +#endif + +#ifdef TEST_SQRT + if (!BN_mod_sqr(a,a,c,ctx)) goto err; + if (!BN_mod_sqr(b,b,c,ctx)) goto err; +#else + if (!BN_nnmod(a,a,c,ctx)) goto err; + if (!BN_nnmod(b,b,c,ctx)) goto err; +#endif + + if (k == 0) + Time_F(START); + } + +#if defined(TEST_EXP) + if (!BN_mod_exp(r,a,b,c,ctx)) goto err; +#elif defined(TEST_GCD) + if (!BN_gcd(r,a,b,ctx)) goto err; + if (!BN_gcd(r,b,c,ctx)) goto err; + if (!BN_gcd(r,c,a,ctx)) goto err; +#elif defined(TEST_KRON) + if (-2 == BN_kronecker(a,b,ctx)) goto err; + if (-2 == BN_kronecker(b,c,ctx)) goto err; + if (-2 == BN_kronecker(c,a,ctx)) goto err; +#elif defined(TEST_INV) + if (!BN_mod_inverse(r,a,c,ctx)) goto err; + if (!BN_mod_inverse(r,b,c,ctx)) goto err; +#else /* TEST_SQRT */ + if (!BN_mod_sqrt(r,a,c,ctx)) goto err; + if (!BN_mod_sqrt(r,b,c,ctx)) goto err; +#endif + } 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); + printf( +#if defined(TEST_EXP) + "modexp %4d ^ %4d %% %4d" +#elif defined(TEST_GCD) + "3*gcd %4d %4d %4d" +#elif defined(TEST_KRON) + "3*kronecker %4d %4d %4d" +#elif defined(TEST_INV) + "2*inv %4d %4d mod %4d" +#else /* TEST_SQRT */ + "2*sqrt [prime == %d (mod 64)] %4d %4d mod %4d" +#endif + " -> %8.3fms %5.1f (%ld)\n", +#ifdef TEST_SQRT + P_MOD_64, +#endif + sizes[i],sizes[i],sizes[i],tm*1000.0/num,tm*mul_c[i]/num, num); num/=7; if (num <= 0) num=1; } + return; + err: + ERR_print_errors_fp(stderr); } + +#ifdef C_PRIME +static void genprime_cb(int p, int n, void *arg) + { + char c='*'; + + if (p == 0) c='.'; + if (p == 1) c='+'; + if (p == 2) c='*'; + if (p == 3) c='\n'; + putc(c, stderr); + fflush(stderr); + (void)n; + (void)arg; + } +#endif |