Run ispell.
authorUlf Möller <ulf@openssl.org>
Thu, 27 Jan 2000 01:50:42 +0000 (01:50 +0000)
committerUlf Möller <ulf@openssl.org>
Thu, 27 Jan 2000 01:50:42 +0000 (01:50 +0000)
Clean up bn_mont.c.

16 files changed:
CHANGES
crypto/bn/bn.h
crypto/bn/bn_mont.c
crypto/bn/bn_print.c
doc/crypto/BN_CTX_new.pod
doc/crypto/BN_add.pod
doc/crypto/BN_add_word.pod
doc/crypto/BN_bn2bin.pod
doc/crypto/BN_mod_mul_reciprocal.pod
doc/crypto/BN_new.pod
doc/crypto/BN_set_bit.pod
doc/crypto/RAND_load_file.pod
doc/crypto/RAND_set_rand_method.pod
doc/crypto/RSA_get_ex_new_index.pod
doc/crypto/bn.pod
doc/crypto/rand.pod

diff --git a/CHANGES b/CHANGES
index 2389e2e..ced9abf 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -4,6 +4,12 @@
 
  Changes between 0.9.4 and 0.9.5  [xx XXX 1999]
 
+  *) Clean up BN_mod_mul_montgomery(): replace the broken (and unreadable)
+     bignum version of BN_from_montgomery() with the working code from
+     SSLeay 0.9.0 (the word based version is faster anyway), and clean up
+     the comments.
+     [Ulf Möller]
+
   *) Avoid a race condition in s2_clnt.c (function get_server_hello) that
      made it impossible to use the same SSL_SESSION data structure in
      SSL2 clients in multiple threads.
index 5d789ff..456d34f 100644 (file)
@@ -257,16 +257,15 @@ typedef struct bn_blinding_st
 
 /* Used for montgomery multiplication */
 typedef struct bn_mont_ctx_st
-        {
-       int use_word;   /* 0 for word form, 1 for long form */
-        int ri;         /* number of bits in R */
-        BIGNUM RR;     /* used to convert to montgomery form */
-        BIGNUM N;      /* The modulus */
-        BIGNUM Ni;     /* The inverse of N */
-       BN_ULONG n0;    /* word form of inverse, normally only one of
-                        * Ni or n0 is defined */
+       {
+       int use_word;  /* 0 for word form, 1 for bignum form */
+       int ri;        /* number of bits in R */
+       BIGNUM RR;     /* used to convert to montgomery form */
+       BIGNUM N;      /* The modulus */
+       BIGNUM Ni;     /* The inverse of N (bignum form) */
+       BN_ULONG n0;   /* The inverse of N in word form */
        int flags;
-        } BN_MONT_CTX;
+       } BN_MONT_CTX;
 
 /* Used for reciprocal division/mod functions
  * It cannot be shared between threads
@@ -360,7 +359,7 @@ int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p,
 int    BN_mask_bits(BIGNUM *a,int n);
 int    BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);
 #ifndef WIN16
-int    BN_print_fp(FILE *fp, BIGNUM *a);
+int    BN_print_fp(FILE *fp, const BIGNUM *a);
 #endif
 #ifdef HEADER_BIO_H
 int    BN_print(BIO *fp, const BIGNUM *a);
index ee0f410..63db577 100644 (file)
@@ -66,8 +66,6 @@
 #include "cryptlib.h"
 #include "bn_lcl.h"
 
-#define MONT_WORD
-
 int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
                          BN_MONT_CTX *mont, BN_CTX *ctx)
        {
@@ -108,6 +106,7 @@ err:
 int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont,
             BN_CTX *ctx)
        {
+       int retn=0;
 #ifdef BN_RECURSION_MONT
        if (mont->use_word)
 #endif
@@ -115,23 +114,23 @@ int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont,
                BIGNUM *n,*r;
                BN_ULONG *ap,*np,*rp,n0,v,*nrp;
                int al,nl,max,i,x,ri;
-               int retn=0;
 
                r= &(ctx->bn[ctx->tos]);
 
-               if (!BN_copy(r,a)) goto err1;
+               if (!BN_copy(r,a)) goto err;
                n= &(mont->N);
 
                ap=a->d;
-               /* mont->ri is the size of mont->N in bits/words */
+               /* mont->ri is the size of mont->N in bits (rounded up
+                   to the word size) */
                al=ri=mont->ri/BN_BITS2;
 
                nl=n->top;
                if ((al == 0) || (nl == 0)) { r->top=0; return(1); }
 
                max=(nl+al+1); /* allow for overflow (no?) XXX */
-               if (bn_wexpand(r,max) == NULL) goto err1;
-               if (bn_wexpand(ret,max) == NULL) goto err1;
+               if (bn_wexpand(r,max) == NULL) goto err;
+               if (bn_wexpand(ret,max) == NULL) goto err;
 
                r->neg=a->neg^n->neg;
                np=n->d;
@@ -204,64 +203,34 @@ printf("word BN_from_montgomery %d * %d\n",nl,nl);
                        BN_usub(ret,ret,&(mont->N)); /* XXX */
                        }
                retn=1;
-err1:
-               return(retn);
                }
 #ifdef BN_RECURSION_MONT
        else /* bignum version */ 
                {
-               BIGNUM *t1,*t2,*t3;
-               int j,i;
+               BIGNUM *t1,*t2;
 
-#ifdef BN_COUNT
-printf("number BN_from_montgomery\n");
-#endif
+               t1=&(ctx->bn[ctx->tos]);
+               t2=&(ctx->bn[ctx->tos+1]);
+               ctx->tos+=2;
 
-               t1= &(ctx->bn[ctx->tos]);
-               t2= &(ctx->bn[ctx->tos+1]);
-               t3= &(ctx->bn[ctx->tos+2]);
+               if (!BN_copy(t1,a)) goto err;
+               BN_mask_bits(t1,mont->ri);
 
-               i=mont->Ni.top;
-               bn_wexpand(ret,i); /* perhaps only i*2 */
-               bn_wexpand(t1,i*4); /* perhaps only i*2 */
-               bn_wexpand(t2,i*2); /* perhaps only i   */
+               if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err;
+               BN_mask_bits(t2,mont->ri);
 
-               bn_mul_low_recursive(t2->d,a->d,mont->Ni.d,i,t1->d);
+               if (!BN_mul(t1,t2,&mont->N,ctx)) goto err;
+               if (!BN_add(t2,a,t1)) goto err;
+               BN_rshift(ret,t2,mont->ri);
 
-               BN_zero(t3);
-               BN_set_bit(t3,mont->N.top*BN_BITS2);
-               bn_sub_words(t3->d,t3->d,a->d,i);
-               bn_mul_high(ret->d,t2->d,mont->N.d,t3->d,i,t1->d);
-
-               /* hmm... if a is between i and 2*i, things are bad */
-               if (a->top > i)
-                       {
-                       j=(int)(bn_add_words(ret->d,ret->d,&(a->d[i]),i));
-                       if (j) /* overflow */
-                               bn_sub_words(ret->d,ret->d,mont->N.d,i);
-                       }
-               ret->top=i;
-               bn_fix_top(ret);
-               if (a->d[0])
-                       BN_add_word(ret,1); /* Always? */
-               else    /* Very very rare */
-                       {
-                       for (i=1; i<mont->N.top-1; i++)
-                               {
-                               if (a->d[i])
-                                       {
-                                       BN_add_word(ret,1); /* Always? */
-                                       break;
-                                       }
-                               }
-                       }
-
-               if (BN_ucmp(ret,&(mont->N)) >= 0)
-                       BN_usub(ret,ret,&(mont->N));
-
-               return(1);
+               if (BN_ucmp(ret,&mont->N) >= 0)
+                       BN_usub(ret,ret,&mont->N);
+               ctx->tos-=2;
+               retn=1;
                }
 #endif
+ err:
+       return(retn);
        }
 
 BN_MONT_CTX *BN_MONT_CTX_new(void)
@@ -307,7 +276,8 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
        BN_copy(&(mont->N),mod);                        /* Set N */
 
 #ifdef BN_RECURSION_MONT
-       if (mont->N.top < BN_MONT_CTX_SET_SIZE_WORD)
+       /* the word-based algorithm is faster */
+       if (mont->N.top > BN_MONT_CTX_SET_SIZE_WORD)
 #endif
                {
                BIGNUM tmod;
@@ -317,74 +287,47 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
 
                mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
                BN_zero(R);
-               BN_set_bit(R,BN_BITS2);
-               /* I was bad, this modification of a passed variable was
-                * breaking the multithreaded stuff :-(
-                * z=mod->top;
-                * mod->top=1; */
+               BN_set_bit(R,BN_BITS2);                 /* R = 2^ri */
 
-               buf[0]=mod->d[0];
+               buf[0]=mod->d[0]; /* tmod = N mod word size */
                buf[1]=0;
                tmod.d=buf;
                tmod.top=1;
-               tmod.max=mod->max;
+               tmod.max=2;
                tmod.neg=mod->neg;
-
+                                                       /* Ri = R^-1 mod N*/
                if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL)
                        goto err;
-               BN_lshift(&Ri,&Ri,BN_BITS2);                    /* R*Ri */
+               BN_lshift(&Ri,&Ri,BN_BITS2);            /* R*Ri */
                if (!BN_is_zero(&Ri))
-                       {
-#if 1
                        BN_sub_word(&Ri,1);
-#else
-                       BN_usub(&Ri,&Ri,BN_value_one());        /* R*Ri - 1 */
-#endif
-                       }
-               else
-                       {
-                       /* This is not common..., 1 in BN_MASK2,
-                        * It happens when buf[0] was == 1.  So for 8 bit,
-                        * this is 1/256, 16bit, 1 in 2^16 etc.
-                        */
-                       BN_set_word(&Ri,BN_MASK2);
-                       }
-               BN_div(&Ri,NULL,&Ri,&tmod,ctx);
+               else /* if N mod word size == 1 */
+                       BN_set_word(&Ri,BN_MASK2);  /* Ri-- (mod word size) */
+               BN_div(&Ri,NULL,&Ri,&tmod,ctx);          /* Ni = (R*Ri-1)/N */
                mont->n0=Ri.d[0];
                BN_free(&Ri);
-               /* mod->top=z; */
                }
 #ifdef BN_RECURSION_MONT
        else
-               {
+               { /* bignum version */
                mont->use_word=0;
-               mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
-#if 1
+               mont->ri=BN_num_bits(mod);
                BN_zero(R);
-               BN_set_bit(R,mont->ri);
-#else
-               BN_lshift(R,BN_value_one(),mont->ri);   /* R */
-#endif
+               BN_set_bit(R,mont->ri);                 /* R = 2^ri */
+                                                       /* Ri = R^-1 mod N*/
                if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL)
                        goto err;
                BN_lshift(&Ri,&Ri,mont->ri);            /* R*Ri */
-#if 1
                BN_sub_word(&Ri,1);
-#else
-               BN_usub(&Ri,&Ri,BN_value_one());        /* R*Ri - 1 */
-#endif
+                                                       /* Ni = (R*Ri-1) / N */
                BN_div(&(mont->Ni),NULL,&Ri,mod,ctx);
                BN_free(&Ri);
                }
 #endif
 
        /* setup RR for conversions */
-#if 1
        BN_zero(&(mont->RR));
        BN_set_bit(&(mont->RR),mont->ri*2);
-#else
-       BN_lshift(mont->RR,BN_value_one(),mont->ri*2);
-#endif
        BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx);
 
        return(1);
index 2f5ab26..92eba45 100644 (file)
@@ -280,7 +280,7 @@ err:
 #ifndef NO_BIO
 
 #ifndef NO_FP_API
-int BN_print_fp(FILE *fp, BIGNUM *a)
+int BN_print_fp(FILE *fp, const BIGNUM *a)
        {
        BIO *b;
        int ret;
index f9ded38..45c70fd 100644 (file)
@@ -42,7 +42,7 @@ L<bn(3)|bn(3)>, L<err(3)|err(3)>, L<BN_add(3)|BN_add(3)>
 
 =head1 HISTORY
 
-BN_CTX_new() and BN_CTX_free() are availabe in all versions on SSLeay
+BN_CTX_new() and BN_CTX_free() are available in all versions on SSLeay
 and OpenSSL. BN_CTX_init() was added in SSLeay 0.9.1b.
 
 =cut
index 3c0bd71..16bb5d4 100644 (file)
@@ -37,13 +37,15 @@ BN_mod_exp, BN_gcd - Arithmetic operations on BIGNUMs
 BN_add() adds B<a> and B<b> and places the result in B<r> (C<r=a+b>).
 B<r> may be the same B<BIGNUM> as B<a> or B<b>.
 
-BN_sub() substracts B<b> from B<a> and places the result in B<r> (C<r=a-b>).
+BN_sub() subtracts B<b> from B<a> and places the result in B<r> (C<r=a-b>).
 
 BN_mul() multiplies B<a> and B<b> and places the result in B<r> (C<r=a*b>).
+For multiplication by powers of 2, use BN_lshift(3).
 
 BN_div() divides B<a> by B<d> and places the result in B<dv> and the
 remainder in B<rem> (C<dv=a/d, rem=a%d>). Either of B<dv> and B<rem> may
 be NULL, in which case the respective value is not returned.
+For division by powers of 2, use BN_rshift(3).
 
 BN_sqr() takes the square of B<a> and places the result in B<r>
 (C<r=a^2>). B<r> and B<a> may be the same B<BIGNUM>.
index 1ee4429..ee02e98 100644 (file)
@@ -27,7 +27,7 @@ arithmetic operations.
 
 BN_add_word() adds B<w> to B<a> (C<a+=w>).
 
-BN_sub_word() substracts B<w> from B<a> (C<a-=w>).
+BN_sub_word() subtracts B<w> from B<a> (C<a-=w>).
 
 BN_mul_word() multiplies B<a> and B<w> (C<a*=b>).
 
index 1a6c237..6bf5f34 100644 (file)
@@ -18,7 +18,7 @@ BN_print, BN_print_fp, BN_bn2mpi, BN_mpi2bn - Format conversions
  int BN_dec2bn(BIGNUM **a, const char *str);
 
  int BN_print(BIO *fp, const BIGNUM *a);
- int BN_print_fp(FILE *fp, BIGNUM *a);
+ int BN_print_fp(FILE *fp, const BIGNUM *a);
 
  int BN_bn2mpi(const BIGNUM *a, unsigned char *to);
  BIGNUM *BN_mpi2bn(unsigned char *s, int len, BIGNUM *ret);
@@ -59,7 +59,7 @@ must be large enough to hold the result. The size can be determined by
 calling BN_bn2mpi(B<a>, NULL).
 
 BN_mpi2bn() converts the B<len> bytes long representation at B<s> to
-a B<BIGNUM> and stores it ar B<ret>, or in a newly allocated B<BIGNUM>
+a B<BIGNUM> and stores it at B<ret>, or in a newly allocated B<BIGNUM>
 if B<ret> is NULL.
 
 =head1 RETURN VALUES
index b158a0f..74d1cc4 100644 (file)
@@ -69,6 +69,6 @@ L<BN_CTX_new(3)|BN_CTX_new(3)>
 
 B<BN_RECP_CTX> was added in SSLeay 0.9.0. Before that, the function
 BN_reciprocal() was used instead, and the BN_mod_mul_reciprocal()
-arguments werde different.
+arguments were different.
 
 =cut
index 8715d99..c1394ff 100644 (file)
@@ -46,7 +46,7 @@ L<bn(3)|bn(3)>, L<err(3)|err(3)>
 
 =head1 HISTORY
 
-BN_new(), BN_clear(), BN_free() and BN_clear_free() are availabe in
+BN_new(), BN_clear(), BN_free() and BN_clear_free() are available in
 all versions on SSLeay and OpenSSL.  BN_init() was added in SSLeay
 0.9.1b.
 
index 75dc5e6..fd887ec 100644 (file)
@@ -33,7 +33,7 @@ error occurs it B<a> is shorter than B<n> bits.
 BN_is_bit_set() tests if bit B<n> in B<a> is set.
 
 BN_mask_bits() truncates B<a> to an B<n> bit number
-(C<q&=~((~0)E<gt>E<gt>n)>).  An error occurs it B<a> already is
+(C<a&=~((~0)E<gt>E<gt>n)>).  An error occurs it B<a> already is
 shorter than B<n> bits.
 
 BN_lshift() shifts B<a> left by B<n> bits and places the result in
index 1cd14dc..dd344fb 100644 (file)
@@ -28,7 +28,7 @@ up to to B<max_bytes> are read; if B<max_bytes> is -1, the complete file
 is read.
 
 RAND_write_file() writes a number of random bytes (currently 1024) to
-file B<filename> which can be used to initialze the PRNG by calling
+file B<filename> which can be used to initialize the PRNG by calling
 RAND_load_file() in a later session.
 
 =head1 RETURN VALUES
index b323ab0..0e3e3d7 100644 (file)
@@ -25,7 +25,7 @@ returns a pointer to that method.
 RAND_set_rand_method() sets the RAND method to B<meth>.
 RAND_get_rand_method() returns a pointer to the current method.
 
-=head1 THE RAND_METHOD STUCTURE
+=head1 THE RAND_METHOD STRUCTURE
 
  typedef struct rand_meth_st
  {
index 30900d9..3e2c525 100644 (file)
@@ -25,8 +25,6 @@ RSA_get_ex_new_index, RSA_set_ex_data, RSA_get_ex_data - add application specifi
  int dup_func(CRYPTO_EX_DATA *to, CRYPTO_EX_DATA *from, void *from_d, 
                                        int idx, long argl, void *argp);
 
-
-
 =head1 DESCRIPTION
 
 Several OpenSSL structures can have application specific data attached to them.
@@ -42,7 +40,7 @@ new application specific data. It takes three optional function pointers which
 are called when the parent structure (in this case an RSA structure) is
 initially created, when it is copied and when it is freed up. If any or all of
 these function pointer arguments are not used they should be set to NULL. The
-precise manner in which these function pointer are called is described in more
+precise manner in which these function pointers are called is described in more
 detail below. B<RSA_get_ex_new_index()> also takes additional long and pointer
 parameters which will be passed to the supplied functions but which otherwise
 have no special meaning. It returns an B<index> which should be stored
@@ -113,10 +111,11 @@ present in the parent RSA structure when it is called.
 
 =head1 SEE ALSO
 
-...
+rsa(3)
 
 =head1 HISTORY
 
-...
+RSA_get_ex_new_index(), RSA_set_ex_data() and RSA_get_ex_data are
+available since SSLeay 0.9.0.
 
 =cut
index bc500ab..ca48019 100644 (file)
@@ -81,7 +81,7 @@ bn - Multiprecision integer arithmetics
  int BN_hex2bn(BIGNUM **a, const char *str);
  int BN_dec2bn(BIGNUM **a, const char *str);
  int BN_print(BIO *fp, const BIGNUM *a);
- int BN_print_fp(FILE *fp, BIGNUM *a);
+ int BN_print_fp(FILE *fp, const BIGNUM *a);
  int BN_bn2mpi(const BIGNUM *a, unsigned char *to);
  BIGNUM *BN_mpi2bn(unsigned char *s, int len, BIGNUM *ret);
 
@@ -125,7 +125,7 @@ should not be modified or accessed directly.
 
 The creation of B<BIGNUM> objects is described in L<BN_new(3)|BN_new(3)>;
 L<BN_add(3)|BN_add(3)> describes most of the arithmetic operations.
-Comparision is described in L<BN_cmp(3)|BN_cmp(3)>; L<BN_zero(3)|BN_zero(3)>
+Comparison is described in L<BN_cmp(3)|BN_cmp(3)>; L<BN_zero(3)|BN_zero(3)>
 describes certain assignments, L<BN_rand(3)|BN_rand(3)> the generation of
 random numbers, L<BN_generate_prime(3)|BN_generate_prime(3)> deals with prime
 numbers and L<BN_set_bit(3)|BN_set_bit(3)> with bit operations. The conversion
index 3797d4b..0b9ae50 100644 (file)
@@ -2,7 +2,7 @@
 
 =head1 NAME
 
-rand - Psdeudo-random number generator
+rand - Pseudo-random number generator
 
 =head1 SYNOPSIS