lip.h

应用密码学这本书的源代码

  -DNO_ALLOCATE flag. Internal local variables will always be allocated
  to the proper length, no matter what flags you use, and output
  variables will also be reallocated if they didn`t get enough
  space, irrespective of the -DNO_ALLOCATE flag.

- To get an indication of what (re)allocations take place,
  you can use the -DPRT_REALLOC flag. The indications will be
  printed on stderr.

- If an error is detected (division by zero, undefined Montgomery
  modulus, undefined results, etc) a message is printed on stderr
  and the program exits. If the -DNO_HALT flag is used, the
  program won`t exit, but values of variables might be undefined.
  In the function descriptions below the possible error messages are
  described. They are supposed to be self-explanatory, if not
  a short explanation follows between (). If the message implies a bug
  in LIP, please report it to [e-mail] as soon as possible.
  There is one message (`wrong call to zsmexp...BUG`) which can only be
  generated by a wrong call to the internal (and undocumented) function
  zsmexp; if you get this message you`re not using the original code.

- If you don`t want to think about -DNO_ALLOCATE or -DPRT_REALLOC
  flags, allocations, or other unpleasant matters, everything
  should work fine, as long as you make sure that you declare
  the very long ints as indicated above (i.e., verylong a=0, b=0, etc...),
  and give them a & in a function call if they are output.
  So, as you can see below, zadd(a, a, &a) adds a to a and puts
  the result in a. On the other hand, zmul(a, b, &a) leads to
  trouble, because input cannot be output in zmul; use
  zmulin(b, &a) instead.

- If you`re writing your own functions with local very long ints,
  then it`s a good idea to declare the very long ints in frequently
  called non-recursive functions as statics:

        static verylong a = 0;
        static verylong b = 0;
        etc...

  instead of

        verylong a = 0;
        verylong b = 0;
        etc...

  If static is used, reallocation of space for the local
  very long ints is avoided in later calls to that same function,
  unless one of the local very long ints needs more space than
  in any of the previous calls: they always keep their longest
  length. If you don`t use static, new space for the local
  very long ints will be allocated for each new call to the
  function, which is less efficient; also, you should use zfree
  in that case at the end of the function, see below.

Acknowledgments
===============
  Acknowledgments are due to many users for reporting bugs,
  to Achim Flammenkamp for initializing the process of writing
  this documentation, and to Bob Cain for converting to ansi.

Before you compile
==================
  You should make sure that some constants get the right value
  for your environment. Here`s a short description of what you
  need. If in doubt, don`t change it, and just try how it works.

  Include Files Needed
  --------------------
        #include <stdio.h>
        #include <math.h>
        #include <malloc.h>
        #include <sys/resource.h>
        #include "lip.h"

  Machine dependent constants 
  --------------------------- 
        Have a look at the constants with <------, and set them
        to the right value for your environment

        #define CHARL           8       <------ Set this to the number of
                                                bits in a byte. Usually it`s 8.

        #define SIZEOFLONG      4       <------ Set this to the number of
                                                bytes in a long, equals
                                                sizeof(long).

        #define NBITS           30      <------ Set this even, and as large as
                                                possible such that
                                                0 < NBITS < CHARL*SIZEOFLONG.

	(Addition: use -DSINGLE_MUL flag to get NBITS=26 and faster macros
			(at least, on most machines); assumes that words
        in doubles are ordered high-low. Use -DDOUBLE_LOW_HIGH if it`s
        the other way around)

        #define RADIX           (1<<NBITS)      Don`t touch this, but it`s
                                                good to know what the radix is.

        #define KAR_MUL_CROV      30              If in a call zmul(a, b, &c) the
        #define KAR_SQU_CROV    30              number of nits of a or b is
        #define KAR_DEPTH        20              less than KAR_MUL_CROV, then a
                                                and b are multiplied using the
                plain quadratic multiplication function; if that`s not the
                case Karatsuba will be applied, recursively, but to a
                maximum of at most KAR_DEPTH recursions. Same for zsq and
                ZKAR_SQU_CROV. The optimal values of these two cross-over
                values depend on the machine you are going to use. The
                choices above are not too far from optimal on a DEC5000;
                on Sparcs the optimal values are somewhat smaller. You
                can make KAR_DEPTH as large as you like, as long as you
                have enough memory.

        #define SIZE            20      <------ Set this to anything such that
                                                SIZE*NBITS>=CHARL*SIZEOFLONG
                SIZE is the default and minimum allocation size for very
                long ints. Any value >= 2 should work. Depending on your
                application smaller or larger values than 20 might lead
                to more efficient code, because it either uses less space
                (for a smaller SIZE), or it uses fewer allocations (for
                a larger SIZE). If you`re not sure what SIZE to pick,
                compile the package and your program with the -DPRT_REALLOC
                flag, and run a representative example: the output will give
                you an impression of the actual sizes that will be used, and
                SIZE can be set accordingly before you compile again without
                the -DPRT_REALLOC flag. If you don`t change it, it should work
                fine.

        #define OUT_LINE        68      <------ An approximate bound for
                                                the maximal number of digits
                per line of output. You might want to change this to 40
                if you have an unusually narrow screen, or to 132 if you`re
                still using one of these nice old lineprinters.
                
        #define IN_LINE         2048            Input accepts at most
                                                IN_LINE characters per line.
                This should not be too restrictive, because long lines
                can easily be split into smaller lines, see below.

        #define PRIM_BND         16500            This enables you to
                                                generate the primes
                less than (2*PRIM_BND+1)^2 using zpnext, see below.
                For 16500 the last prime that can thus be generated is
                1089065981.
}
#endif



#include <stdio.h>
#include <math.h>
#include <sys/types.h>
#ifndef WIN32
#include <netinet/in.h>
#endif
#include "lippar.h"

/*The type of very long ints.*/
typedef long * verylong;

#ifdef FREE
#define STATIC
#define FREESPACE(x)    zfree(&x);
#define FREE2SPACE(x,y) zfree(&x); zfree(&y);
#define FREE3SPACE(x,y,z) zfree(&x); zfree(&y); zfree(&z);
#else
#define STATIC          static
#define FREESPACE(x)
#define FREE2SPACE(x,y) 
#define FREE3SPACE(x,y,z)
#endif

#define ILLEGAL 0


#ifdef NO_ALLOCATE
# define ALLOCATE 0
#else
# define ALLOCATE 1
#endif

#ifdef PRT_REALLOC
# undef PRT_REALLOC
# define PRT_REALLOC 1
#else
# define PRT_REALLOC 0
#endif

#ifndef CHARL
# define CHARL           8      /* 8 bits per char */
#endif

#ifndef SIZEOFLONG
# define SIZEOFLONG      4      /* set this to sizeof(long) */
#endif

#define BITSOFLONG      (CHARL*SIZEOFLONG)

#ifdef ALPHA
# ifdef ALPHA50
#  undef ILLEGAL
#  define ILLEGAL	1
# endif
# ifndef PLAIN
#  undef KARAT
#  define KARAT  1
# endif
# ifdef SINGLE_MUL
#  undef ILLEGAL
#  define ILLEGAL	1
# endif
# define NBITS          62
# undef BITSOFLONG
# define BITSOFLONG     64
# undef  SIZEOFLONG
# define SIZEOFLONG      8
# define PRIM_BND      (1L<<14)
# define ALPHA_OR_ALPHA50       1
#endif

#ifdef ALPHA50
# ifndef PLAIN
#  undef KARAT
#  define KARAT  1
# endif
# ifdef SINGLE_MUL
#  undef ILLEGAL
#  define ILLEGAL	1
# endif
# define NBITS          62
# undef BITSOFLONG
# define BITSOFLONG     64
# undef  SIZEOFLONG
# define SIZEOFLONG      8
# define PRIM_BND      (1L<<14)
# define ALPHA50NBITS   50
# define ALPHA50NBITSH  (ALPHA50NBITS>>1)
# define ALPHA50RADIX   (1L<<ALPHA50NBITS)
# define        ALPHA50RADIXM   (ALPHA50RADIX-1)
# define        ALPHA50RADIXROOT        (1L<< ALPHA50NBITSH)
# define ALPHA50RADIXROOTM      (ALPHA50RADIXROOT-1)
# define ALPHA_OR_ALPHA50       1
#endif


#ifdef PLAIN
# define PLAIN_OR_KARAT  1
#endif

#ifdef KARAT
# define PLAIN_OR_KARAT  1
#endif


#ifndef NBITS
# ifdef SINGLE_MUL
#  define NBITS        26
# else
#  define NBITS         30
# endif
#endif

#define NBITSH          (NBITS>>1)
#define RADIX           (1L<<NBITS)
#define RADIXM          (RADIX-1)
#define RADIXROOT       (1L<<NBITSH)
#define RADIXROOTM      (RADIXROOT-1)

#ifndef SIZE
# define SIZE           20      /* SIZE*NBITS must be >= BITSOFLONG */
#endif


#ifndef OUT_LINE
# define OUT_LINE       68      /* approximate bound # digits per line */
#endif

#define OUT_LINE_BREAK  '\\'

#ifndef IN_LINE
# define IN_LINE      2048      /* at most 2048 characters per line */
#endif

#define IN_LINE_BREAK   '\\'

#ifndef HEX_BLOCK
# define HEX_BLOCK	8
#endif

#ifndef HEX_BLOCKS_PER_LINE
# define HEX_BLOCKS_PER_LINE	7
#endif

#define HEX_SEP_CHAR	' '

#ifndef PRIM_BND
# ifdef SINGLE_MUL
#  define PRIM_BND      (1L<<14)
# else
#  define PRIM_BND      (1L<<(NBITSH-1))
# endif
                        /* to generate primes <= (2*PRIM_BND+1)^2 */
                        /* last prime for NBITS == 30 is 1073807359 */
			/* same for SINGLE_MUL */
#elif (PRIM_BND>(1L<<(NBITSH-1)))
# undef PRIM_BND
# define PRIM_BND       (1L<<(NBITSH-1))
#endif

#define PRIM_UP         ((((PRIM_BND<<1)+1)*((PRIM_BND<<1)+1))-(NBITS<<2))

#if (NBITS&1)
# undef ILLEGAL
# define ILLEGAL 1
#endif

#if (NBITS <= 0)
# undef ILLEGAL
# define ILLEGAL 1
#endif

#if (NBITS >= BITSOFLONG)
# undef ILLEGAL
# define ILLEGAL 1
#endif

#if (SIZE*NBITS<=BITSOFLONG)
# undef ILLEGAL
# define ILLEGAL 1
#endif

#ifdef SINGLE_MUL
# if (NBITS != 26)
#  undef ILLEGAL
#  define ILLEGAL 1
# endif
# ifdef PLAIN
#  undef ILLEGAL
#  define ILLEGAL 1
# endif