p1363.c

miracl-大数运算库,大家使用有什么问题请多多提意见

/* 
 * MIRACL-based implementation of the IEEE 1363 standard 
 * Version 1.4 December 2005
 *
 * NEW 1.1 - Elliptic curve points now stored in a single OCTET as recommended
 *           in P1363a. Such octets will be 2*fs+1 in length, where fs is
 *           the field size. If compression is used they may be fs+1
 *
 * NEW 1.2 - Auxiliary functions completely re-written
 *           More primitives and functions implemented
 *           New mirvar_mem function used for extra speed 
 *
 * NEW 1.3 - Cryptographically strong RNG interface improved
 *
 * Implements most of the cryptographic primitives, message encoding methods, 
 * key derivation functions and auxiliary functions necessary for realising the 
 * recommended methods. Note that GF(p) and GF(2^m) Elliptic curves are
 * treated seperately.
 *
 * See the IEEE 1363 documentation for details
 * http://grouper.ieee.org/groups/1363/index.html
 * This IS the documentation for this implementation. Each P1363 function
 * has the same name, and same inputs/outputs as those described in the 
 * official 1363 documentation.
 *
 * The user is responsible for the initialisation and maintainance of 
 * "Octet strings" which store Cryptographic keys and application info.
 * These octet strings store big numbers in binary, from MSB down to LSB
 * NOTE:- Leading zeros can be suppressed! Use OCTET_PAD() to insert leading
 * zeros to make an octet a particular length, e.g. 20 bytes, 160 bits.
 * 
 * An instance of a Cryptographically Strong Random Number Generator
 * must be created and initialised by the user with
 * raw random data. This doesn't have to be high quality (e.g. mouse movement 
 * coordinates), but there must be enough of it for it to be unguessable. 
 * It is subsequently maintained internally by the system
 * The secure random number generation method used is based on that described 
 * in ftp://ftp.rsasecurity.com/pub/pdfs/bull-1.pdf
 *
 * The above is the recommended approach. 
 * Alternatvely when generating a key pair a random number can be specified 
 * directly as a private key, and this internal system by-passed. 
 * 
 * Domain and Public/Private key data is stored in structures defined in 
 * p1363.h. The first parameter in each function is a pointer to a function 
 * which will be called during time-consuming calculations - e.g. a Windows 
 * message pump. Negative return values indicate an error - see p1363.h for 
 * definitions. Most common MIRACL errors are mapped to these values.
 * Unlikely MIRACL errors are returned as -(1000+MEC), where MEC
 * is the MIRACL Error Code (see miracl.h)
 *
 * quick start:-
 * cl /O2 test1363.c p1363.c ms32.lib
 *
 * Recommended for use with a (32-bit) MIRACL library built 
 * from a mirdef.h file that looks something like this:-
 *
 * #define MIRACL 32
 * #define MR_LITTLE_ENDIAN
 * #define mr_utype int
 * #define MR_IBITS 32
 * #define MR_LBITS 32
 * #define mr_unsign32 unsigned int
 * #define MR_STRIPPED_DOWN
 * #define MR_GENERIC_MT
 * #define mr_dltype __int64
 * #define mr_unsign64 unsigned __int64
 * #define MAXBASE ((mr_small)1<<(MIRACL-1))
 *
 * Note that this is a multi-threaded build, ideal for a Cryptographic DLL
 * The compiler may need a multithreaded flag set (/MT ??) 
 *
 * The miracl instance variable ERCON is set to TRUE in each routine, so 
 * MIRACL does not attempt to report an error. Instead the variable ERNUM 
 * latches the last error, and if set causes each subsequent routine to 
 * "fall through".  
 *
 * Octet strings are not tested for overflow. In fact overflow will not 
 * happen as octets will be truncated - so buffer overflow attacks against 
 * this code will not succeed. To avoid unintentional overflow its best to 
 * initialise the length of most octets to that recommended and returned by 
 * the XXX_DOMAIN_INIT() routines. Note however that elliptic curve point  
 * octets should be initialised to "twice this length plus 1" (or only "this 
 * length plus 1" if compression is used)
 *
 * A test driver main() function is provided in test1363.c to test all the 
 * functions, and to implement five of the recommended methods, IFSSA, IFSSR, 
 * DLSSR, DLSSR-PV and ECIES 
 *
 * In Win32 MS C:-
 * cl /O2 /MT test1363.c p1363.c miracl.lib  /link /NODEFAULTLIB:libc.lib
 * and run the executable
 *
 * test1363         ; 
 * test1363 -c      ; uses EC point compression
 * test1363 -p      ; uses precomputation for signature
 * test1363 -c -p   ; uses both precomputation and EC point compression
 *
 * To create a Windows P1363 DLL, compile as 
 * cl /O2 /W3 /MT /DMR_P1363_DLL /LD p1363.c miracl.lib /link /NODEFAULTLIB:libc.lib
 * To run the test program to use the DLL, compile as
 * cl /O2 /MT /DMR_P1363_DLL test1363.c p1363.lib
 * 
 * Discrete Logarithm/GF(p) Elliptic Curve/GF(2^m) Elliptic Curve Domain 
 * details are read from the files common.dss, common.ecs and common2.ecs 
 * respectively. Suitable files are included in the standard MIRACL 
 * distribution. You can generate your own using for example the utilities 
 * dssetup.cpp, schoof.cpp and schoof2.cpp. But make sure that the group order
 * in each case is at least 160-bits, or the demo may fail.
 *
 * Note that for a full 1363 implementation various simple message-encoding 
 * regimes must be also implemented, as described in the P1363 and P1363a 
 * documentation. Many of these are now implemented here. Also suitable hashing
 * functions must be available. The SHA1/SHA256/SHA384 and SHA512 algorithms 
 * are recommended, and implemented in MIRACL 
 *
 * Note that some of the message encoding functions can take input from a file
 * rather than from a string. This is convenient for example if "signing" a 
 * large document. In these cases the parameters are typically "octet *x,FILE 
 * *fp", in which case either an OCTET string x can be specified OR a 
 * filename, but not both.
 *
 * Version 1.4
 * Miracl STATIC (no-heap version) supported. However octets (which are oftern variable length)
 * must still be allocated from the heap. 
 * NOTE: Precomputation not directly supported in this mode 
 *
 * NOTE: It would be typical to break this file up and just use the parts that are needed
 * (For example if using Elliptic curve methods only, then the size of structures could be much smaller)
 *
 * Copyright (c) 2000-2004 Shamus Software Ltd.
 */

/* define this next to create Windows DLL */   

/* #define MR_1363_DLL */

#ifdef MR_P1363_DLL
#define P1363_DLL
#endif

#include <stdio.h>
#include <stdlib.h>
#include "p1363.h"

/* Hash IDs for supported EMSA3 hash functions. <hashIDlen>,<hash ID> */

static unsigned char SHA160ID[]={15,0x30,0x21,0x30,0x09,0x06,0x05,0x2b,0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14};
static unsigned char SHA256ID[]={19,0x30,0x21,0x30,0x0d,0x06,0x09,0x60,0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x01,0x05,0x00,0x04,0x20};
static unsigned char SHA384ID[]={19,0x30,0x21,0x30,0x0d,0x06,0x09,0x60,0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x02,0x05,0x00,0x04,0x30};
static unsigned char SHA512ID[]={19,0x30,0x21,0x30,0x0d,0x06,0x09,0x60,0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x03,0x05,0x00,0x04,0x40};

/* IDs for SHA1,RIPEMD,SHA256,SHA384 and SHA512 */
/* NOTE ripemd is not implemented               */

static unsigned char sha_id[]={0x33,0x31,0x34,0x36,0x35};

/* Internal functions */

static long filelength(FILE *fp)
{ /* return file length in reasonably portable fashion */
    long len;
    fseek(fp,0,SEEK_END);
    len=ftell(fp);
    fseek(fp,0,SEEK_SET);
    return len;
}

static void OS2FEP(_MIPD_ octet *s,big w)
{ /* internal:- converts from octet to big format */
    bytes_to_big(_MIPP_ s->len,s->val,w);
}

static void convert_big_octet(_MIPD_ big w,octet *s)
{ /* internal:- converts from big integer to octet format */
    s->len=(oltype)big_to_bytes(_MIPP_ 0,w,s->val,FALSE);
}

static void FE2OSP(_MIPD_ big w,int fsize,octet *s)
{ /* internal:- converts from big to field element format */
    s->len=(oltype)big_to_bytes(_MIPP_ fsize,w,s->val,TRUE);
}

static void EC2OSP(_MIPD_ big x,big y,int cbit,BOOL compressed,int fsize,octet *s)
{ /* internal:- converts from (x,y) to octet string */
    s->len=1; 
    if (compressed) s->val[0]=2+cbit; 
    else            s->val[0]=6+cbit;     /* hybrid */
    s->len+=(oltype)big_to_bytes(_MIPP_ fsize,x,&(s->val[1]),TRUE);
    if (!compressed) s->len+=(oltype)big_to_bytes(_MIPP_ fsize,y,&(s->val[fsize+1]),TRUE);
}

static BOOL OS2ECP(_MIPD_ octet *s,big x,big y,int fsize,int *bit)
{ /* converts from octet string to (x,y) point */

    bytes_to_big(_MIPP_ fsize,&(s->val[1]),x);
    if (s->val[0]&4)
    { /* uncompressed ..but don't put a y if not required */
        if(y!=NULL) bytes_to_big(_MIPP_ fsize,&(s->val[fsize+1]),y);
        return FALSE;
    }   
    else
    { /* compressed */
        *bit=s->val[0]&1;
        return TRUE;
    } 
}

/* return output length of hash function in bytes, also hash function input 
   block size if desired */

static int hash_params(int hash_type,int *block)
{
    switch (hash_type)
    {
    case SHA1:
        if (block!=NULL) *block=64;
        return 20;
    case SHA256:
        if (block!=NULL) *block=64;
        return 32;
#ifdef mr_unsign64
    case SHA384:
        if (block!=NULL) *block=128;
        return 48;
    case SHA512:
        if (block!=NULL) *block=128;
        return 64;   
#endif
    default:
        break;
    }
    return 0;
}

/*** Basic Octet string maintainance routines  ***/
/* initialize an octet string                    */
/* make it impossible to write beyond max length */

P1363_API BOOL OCTET_INIT(octet *w,int bytes)
{
    w->len=0;
    w->max=bytes; 
    w->val=(char *)malloc(bytes);
    if (w->val!=NULL) return TRUE;
    else              return FALSE; 
}

/* clear an octet string */

P1363_API void OCTET_CLEAR(octet *w)
{
    int i;
    for (i=0;i<w->len;i++) w->val[i]=0;
    w->len=0;
}

/* XOR m with all of x */

P1363_API void OCTET_XOR_BYTE(octet *x,int m)
{
    int i;
    for (i=0;i<x->len;i++) x->val[i]^=m;
}

/* XOR common bytes of x with y */

P1363_API void OCTET_XOR(octet *x,octet *y)
{ /* xor first x->len bytes of y */

    int i;
    for (i=0;i<x->len && i<y->len;i++)
    {
        y->val[i]^=x->val[i];
    }
}

/* clear an octet */

P1363_API void OCTET_EMPTY(octet *w)
{
    w->len=0;
}

/* copy an octet string - truncates if no room */

P1363_API void OCTET_COPY(octet *x,octet *y)
{
    int i;
    OCTET_CLEAR(y);
    y->len=x->len;
    if (y->len>y->max) y->len=y->max;

    for (i=0;i<y->len;i++)
        y->val[i]=x->val[i];
}

/* compare 2 octet strings. 
 * If x==y return TRUE, else return FALSE */ 

P1363_API BOOL OCTET_COMPARE(octet *x,octet *y)
{
    int i;
    if (x->len>y->len) return FALSE;
    if (x->len<y->len) return FALSE;
    for (i=0;i<x->len;i++)
    {
        if (x->val[i]!=y->val[i]) return FALSE;
    }
    return TRUE;
}

/* check are first n bytes the same */

P1363_API BOOL OCTET_NCOMPARE(octet *x,octet *y,int n)
{
    int i;
    if (n>y->len || n>x->len) return FALSE;
    for (i=0;i<n;i++)
    {
        if (x->val[i]!=y->val[i]) return FALSE;
    }
    return TRUE;
}

/* Pads an octet with leading zeros - returns FALSE if not enough room */

P1363_API BOOL OCTET_PAD(octet *x,int len)
{
    int i,d;
    if (len>x->max || x->len>len) return FALSE;
    if (len==x->len) return TRUE;
    d=len - x->len;
    for (i=len-1;i>=d;i--)
        x->val[i]=x->val[i-d];

    for (i=0;i<d;i++) x->val[i]=0;
    x->len=(oltype)len;
    return TRUE;
}

/* Shift octet to the left by n bytes. Leftmost bytes disappear  */

P1363_API void OCTET_SHIFT_LEFT(octet *x,int n)
{
    int i;
    if (n>=x->len)
    {
        x->len=0;
        return;
    }
    x->len-=n;
    for (i=0;i<x->len;i++)
        x->val[i]=x->val[i+n];
}    

/* truncates x to n bytes and places the rest in y (if y is not NULL) */

P1363_API void OCTET_CHOP(octet *x,int n,octet *y)
{
    int i;
    if (n>=x->len)
    {
        if (y!=NULL) y->len=0;
        return;
    }
    if (y!=NULL) y->len=x->len-n;
    x->len=n; 

    if (y!=NULL)
    {
        for (i=0;i<y->len && i<y->max;i++) y->val[i]=x->val[i+n];
    }
}

/* Concatenates two octet strings */

P1363_API void OCTET_JOIN_OCTET(octet *x,octet *y)
{ /* y=y || x */
    int i,j;
    if (x==NULL) return;

    for (i=0;i<x->len;i++)
    {
        j=y->len+i;
        if (j>=y->max)
        {
            y->len=y->max;
            return;
        }
        y->val[j]=x->val[i];
    }
    y->len+=x->len;
}

/* OCTET_JOIN_LONG primitive */
/* appends long x to OCTET string of length len */
/* if more than len bytes required, string is increased > len */

P1363_API void OCTET_JOIN_LONG(long x, int len,octet *y)
{
   int i,j,n;
   n=y->len+len;
   if (n>y->max || len<=0) return;
   for (i=y->len;i<n;i++) y->val[i]=0; 
   y->len=n;

   i=len;
   while (x>0)
   {
       if (i==0)
       {
           for (j=y->len;j>0;j--) y->val[j]=y->val[j-1];
           y->len++;
           if (y->len>y->max) break;
           i=1;
       }
       i--;
       y->val[i]=x%256;
       x/=256;
   }    
}

/* Convert C string to octet format - truncates if no room  */

P1363_API void OCTET_JOIN_STRING(char *s,octet *y)
{
    int i,j;
    i=y->len;
    j=0;
    while (s[j]!=0 && i<y->max)
    {
        y->val[i]=s[j];
        y->len++;
        i++;  j++;
    }
}

/* Append binary string to octet - truncates if no room */

P1363_API void OCTET_JOIN_BYTES(char *b,int len,octet *y)
{
    int i,j;
    i=y->len;
    for (j=0;j<len && i<y->max;j++) 
    {
        y->val[i]=b[j];
        y->len++;
        i++;
    }
}

/* Append byte to octet rep times */

P1363_API void OCTET_JOIN_BYTE(int ch,int rep,octet *y)
{
    int i,j;
    i=y->len;
    for (j=0;j<rep && i<y->max;j++) 
    {
        y->val[i]=ch;
        y->len++;
        i++;
    }
}

/* Copy len random bytes into octet */

P1363_API void OCTET_RAND(csprng *RNG,int len,octet *x)
{
    int i;
    if (len>x->max) len=x->max;
    x->len=len;

    for (i=0;i<len;i++) x->val[i]=strong_rng(RNG);
}

/* Output an octet string (Debug Only) */

P1363_API void OCTET_OUTPUT(octet *w)
{
    int i;