Timings.

[openssl.git] / crypto / bn / bn_exp.c

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index d2c91628acba0ecce6f4898e67417a340e73ad80..eab394b96231051d0dc5070dd679142f3ceca8f9 100644 (file)
--- 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,39 @@ 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 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,7 +202,7 @@ int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
 
        if (BN_is_odd(m))
                {
-               if (a->top == 1)
+               if (a->top == 1 && !a->neg)
                        {
                        BN_ULONG A = a->d[0];
                        ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
@@ -240,7 +248,7 @@ 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 */
 
        window = BN_window_bits_for_exponent_size(bits);
        if (window > 1)
@@ -325,13 +333,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;
 
@@ -368,9 +376,9 @@ 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]);
                }
@@ -590,8 +598,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;
@@ -611,7 +620,7 @@ 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 */
 
        window = BN_window_bits_for_exponent_size(bits);
        if (window > 1)