lip.h

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

# ifdef KARAT
#  undef ILLEGAL
#  define ILLEGAL 1
# endif
#endif

#ifdef PLAIN
# ifdef KARAT
#  undef ILLEGAL
#  define ILLEGAL 1
# endif
#endif

/******************************************************************************\
*   Internal macros
*
*   Although the package is supposed to be portable, you might want to
*   fine tune it to your particular machine to get better performance.
*   The easiest way to do this is to replace the following macros, which
*   you will find in the source code, by appropriate assembly language
*   versions:
*
*   Also the C-code for zsubmul, zdiv21 and zmulmods can be made
*   much faster in a similar way. I always simply used the macros
*   or the C-code, and I get acceptable performance.
\******************************************************************************/

    static void zaddmulp(long *a, long b, long d, long *t);
        /******************************************************************\
        * a = (a + t + b * d) % RADIX; and simultaneously
        * t = (a + t + b * d) / RADIX;
        \******************************************************************/

    static void zaddmulpsq(long *a, long b, long *t);
        /******************************************************************\
        * a = (a + b * b) % RADIX; and simultaneously
        * t = (a + b * b) / RADIX;
        \******************************************************************/

    static void zaddmulone(verylong a, verylong b);
        /******************************************************************\
        * a += b;
        * a and b not at overlapping addresses
        \******************************************************************/

    static void zaddmul(long d, verylong a, verylong b);
        /******************************************************************\
        * a += d * b;
        * a and b not at overlapping addresses (except if d=1)
        \******************************************************************/

    static void zaddmulsq(long d, verylong a, verylong b);
        /******************************************************************\
        * a += b[0] * b[1:d];
        * a and b not at overlapping addresses (except if d=1)
        \******************************************************************/

    static void zmmulp(verylong a);
        /******************************************************************\
        * a[s:] += (a[s] * zminv) * zn;
        * to make a[s] == 0, where s and zminv are clear from
        * the context, only in Montgomery multiplication
        \******************************************************************/


/******************************************************************************\
*  Basic functions
*  
*  Addition, subtraction, multiplication, squaring, and
*  division with remainder on signed arbitrary length integers.
*  Multiplication and squaring use Karatsuba, if inputs large enough;
*  see KAR_MUL_CROV, KAR_SQU_CROV, and KAR_DEPTH as explained above.
\******************************************************************************/

    void zstart(void);
        /******************************************************************\
        * To initialize some global machine dependent values
        * that have to be computed only once, call this only once per run.
        * Everything still works fine if you forget to call zstart.
        * If you`re sure that you`re not going to forget it, you may
        * compile the package with the -DSTART flag and get slightly
        * faster code.
        *
        * possible error message:
        *   recompile with smaller NBITS
        * result undefined if error occurs
        \******************************************************************/

    void zsadd(verylong a, long d, verylong *b);
        /******************************************************************\
        * *b = a + d;
        * 
        \******************************************************************/

    void zadd(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * *c = a + b;
        * 
        \******************************************************************/

    void zsub(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * *c = a - b;
        * 
        \******************************************************************/

    void zsubpos(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * *c = a - b;
        * 
        * only for a >= b >= 0
        \******************************************************************/

    void zsmul(verylong a, long d, verylong *b);
        /******************************************************************\
        * *b = d * a;
        * 
        \******************************************************************/

    void zmul(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * *c = a * b;
        * 
        * output cannot be input
        \******************************************************************/

    void zmulin(verylong a, verylong *b);
        /******************************************************************\
        * *b = a * b;
        * 
        * output cannot be input
        \******************************************************************/

    void zmul_plain(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * *c = a * b;
        * 
        * output cannot be input, uses ordinary multiplication
        \******************************************************************/

    void zsq(verylong a, verylong *c);
        /******************************************************************\
        * *c = a * a;
        * 
        * output cannot be input
        \******************************************************************/

    void zsqin(verylong *a);
        /******************************************************************\
        * *a = a ^ 2;
        * 
        \******************************************************************/

    void zsq_plain(verylong a, verylong *b);
        /******************************************************************\
        * *b = a ^ 2;
        * 
        * output cannot be input, uses ordinary squaring
        \******************************************************************/

    long zsdiv(verylong a, long d, verylong *b);
        /******************************************************************\
        * *b = a / d;
        * return (a % d);
        * 
        * d != 0,
        * always b * q + (a % d) == a and,
        * unless b divides a, sign(a % d) == sign(d),
        * calls zdiv if |d| >= RADIX
        *
        * possible error message:
        *   division by zero in zsdiv
        * result undefined if error occurs
        \******************************************************************/

    void zdiv(verylong a, verylong b, verylong *q, verylong *r);
        /******************************************************************\
        * *q = a / b;
        * *r = a % b;
        * 
        * b != 0,
        * always b * q + r == a,
        * unless b divides a, sign(r) == sign(b)
        *
        * possible error message:
        *   division by zero in zdiv
        * result undefined if error occurs
        \******************************************************************/

    long zsmod(verylong a, long d);
        /******************************************************************\
        * return (a % d);
        * 
        * calls zsdiv
        \******************************************************************/

    void zmod(verylong a, verylong b, verylong *r);
        /******************************************************************\
        * *r = a % b;
        * 
        * unless b divides a, sign(r) == sign(b),
        * slightly faster than zdiv
        *
        * possible error message:
        *   division by zero in zmod
        * result undefined if error occurs
        \******************************************************************/


/******************************************************************************\
*  Shifting and bit manipulation
*
*  Left and right shifting, removal of all factors 2,
*  parity test, logical and/(x)or, bit selections, weight,
*  concatenation, bit-reverse
*
*  WARNING: The bit manipulation routines need to be debugged carefully
\******************************************************************************/

    void z2mul(verylong n, verylong *a);
        /******************************************************************\
        * *a = 2 * n;
        * 
        \******************************************************************/

    long z2div(verylong n, verylong *a);
        /******************************************************************\
        * *a = n / 2; return (n % 2);
        * 
        * warning: for n == -2 * k + 1 (k > 0), z2div(n, &a)
        * gives a = -k + 1, but zsdiv(a, 2, &b) gives b = -k,
        * both return 1
        \******************************************************************/

    long z2mod(verylong n);
        /******************************************************************\
        * return (n % 2);
        \******************************************************************/

    void zlshift(verylong n, long k, verylong *a);
        /******************************************************************\
        * *a = 2 ^ k * n;
        * 
        * i.e., shifts left over k positions,
        * calls zrshift(n, -k, a) if k < 0
        \******************************************************************/

    void zrshift(verylong n, long k, verylong *a);
        /******************************************************************\
        * *a = n / (2 ^ k);
        * 
        * i.e., shifts right over k positions,
        * calls zlshift(n, -k, a) if k<0
        \******************************************************************/
    
    long zmakeodd(verylong *n);
        /******************************************************************\
        * if (n != 0)
        *     *n = m;
        *     return (k such that n == 2 ^ k * m with m odd);
        * else
        *     return (-1);
        \******************************************************************/

    long zodd(verylong a);
        /******************************************************************\
        * returns 1 if a is odd, returns 0 if a is even
        \******************************************************************/

    void znot(verylong a, verylong *b);
        /******************************************************************\
        * if (a==0) then b gets 1,
        * else b gets the negated bit pattern of the first z2log(|a|)
        * bits of a, and b gets the same sign as a (unless b is zero)
        \******************************************************************/

    void zand(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * c gets bit pattern `bits of |a|` and `bits of |b|`
        \******************************************************************/

    void zor(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * c gets bit pattern `bits of |a|` inclusive or `bits of |b|`
        \******************************************************************/

    void zxor(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * c gets bit pattern `bits of |a|` exclusive or `bits of |b|`
        \******************************************************************/

    long zslowbits(verylong a, long b);
        /******************************************************************\
	* returns b (or NBITS if b>NBITS) lowest order bits of |a|,
        * 0 if b <= 0
        \******************************************************************/

    void zlowbits(verylong a, long b, verylong *c);
        /******************************************************************\
	* c gets b lowest order bits of |a|, c gets 0 if b <= 0
        \******************************************************************/


    long zshighbits(verylong a, long b);
        /******************************************************************\
        * returns b (or NBITS if b>NBITS) highest order bits of |a|,
        * 0 if b <= 0
        \******************************************************************/

    void zhighbits(verylong a, long b, verylong *c);
        /******************************************************************\
        * c gets b highest order bits of |a|, c gets 0 if b <= 0
        \******************************************************************/

    long zweights(long a);
        /******************************************************************\
        * returns the number of one bits in |a|
        \******************************************************************/

    long zweight(verylong a);
        /******************************************************************\
        * returns the number of one bits in |a|
        \******************************************************************/

    void zcat(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * c gets the concatenation of bits of a followed by the bits of b
        * (a becomes the high order and b the low order part of c)
        \******************************************************************/

    long zbit(verylong a, long p);
        /******************************************************************\
        * returns 1 if |p|th bit of |a| is on, 0 if |p|th bit of |a| is off
        * p starts counting at 0
        \******************************************************************/

    void zgetbits(verylong a, long b, long p, verylong *c);
        /******************************************************************\
        * c gets the b bits of |a| starting at |a|`s |p|th bit