mrarth1.c

比较新的功能强大的rsa算法源代码,方便使用.

        ASM mov sr,eax
     out2:
        ASM nop
#endif
#if INLINE_ASM == 4

        ASM (
           "movl %4,%%ecx\n"
           "orl  %%ecx,%%ecx\n"
           "je 3f\n"
           "movl %%ecx,%%ebx\n"
           "shll $2,%%ebx\n"
           "movl %2,%%esi\n"
           "addl %%ebx,%%esi\n"
           "movl %1,%%edi\n"
           "addl %%ebx,%%edi\n"
           "movl %3,%%ebx\n"
           "pushl %%ebp\n"
           "xorl %%ebp,%%ebp\n"  
         "2:\n"  
           "subl $4,%%esi\n"
           "movl %%ebp,%%edx\n"
           "movl (%%esi),%%eax\n"
           "divl %%ebx\n"
           "subl $4,%%edi\n"
           "movl %%edx,%%ebp\n"
           "movl %%eax,(%%edi)\n"
           "decl %%ecx\n"
           "jnz 2b\n"
 
           "movl %%ebp,%%eax\n"
           "popl %%ebp\n"
           "movl %%eax,%0\n"
        "3:"
           "nop"  
        :"=m"(sr)
        :"m"(zg),"m"(xg),"m"(sn),"m"(xl)
        :"eax","edi","esi","ebx","ecx","edx","memory"
        );
#endif
#endif
#ifndef INLINE_ASM
        for (i=xl-1;i>=0;i--)
        {
#ifdef MR_NOASM
            dble.h[MR_BOT]=x->w[i];
            dble.h[MR_TOP]=sr;
            z->w[i]=(mr_small)(dble.d/sn);
            sr=(mr_small)(dble.d-(mr_large)z->w[i]*sn);
#else
            z->w[i]=muldvm(sr,x->w[i],sn,&sr);
#endif
        }
#endif
#endif
#ifndef MR_SIMPLE_BASE
    }
    else for (i=xl-1;i>=0;i--)
    { /* divide each digit of x by n */
#ifdef MR_NOASM
        dbled=(mr_large)sr*mr_mip->base+x->w[i];
#ifdef MR_FP_ROUNDING
        z->w[i]=(mr_small)MR_LROUND(dbled*isn);
#else
        z->w[i]=(mr_small)MR_LROUND(dbled/sn);
#endif
        sr=(mr_small)(dbled-(mr_large)z->w[i]*sn);
#else
#ifdef MR_FP_ROUNDING
        z->w[i]=imuldiv(sr,mr_mip->base,x->w[i],sn,isn,&sr);
#else
        z->w[i]=muldiv(sr,mr_mip->base,x->w[i],sn,&sr);
#endif
#endif
    }
#endif
    z->len=x->len;
    mr_lzero(z);
    return sr;
}
         
int subdiv(_MIPD_ big x,int n,big z)
{  /*  subdivide a big number by an int   z=x/n  *
    *  returns int remainder                     */ 
    mr_lentype sx;
#ifdef MR_FP_ROUNDING
    mr_large in;
#endif
    int r,i,msb;
    mr_small lsb;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return 0;

    MR_IN(10)
#ifdef MR_FLASH
    if (mr_notint(x)) mr_berror(_MIPP_ MR_ERR_INT_OP);
#endif
    if (n==0) mr_berror(_MIPP_ MR_ERR_DIV_BY_ZERO);
    if (mr_mip->ERNUM) 
    {
        MR_OUT
        return 0;
    }

    if (x->len==0)
    {
        zero(z);
        MR_OUT
        return 0;
    }
    if (n==1) /* special case */
    {
        copy(x,z);
        MR_OUT
        return 0;
    }
    sx=(x->len&MR_MSBIT);
    if (n==2 && mr_mip->base==0)
    { /* fast division by 2 using shifting */
#ifndef MR_NOFULLWIDTH

/* I don't want this code upsetting the compiler ... */
/* mr_mip->base==0 can't happen with MR_NOFULLWIDTH  */

        copy(x,z);
        msb=(int)(z->len&MR_OBITS)-1;
        r=(int)z->w[0]&1;
        for (i=0;;i++)
        {
            z->w[i]>>=1;
            if (i==msb) 
            {
                if (z->w[i]==0) mr_lzero(z);
                break;
            }
            lsb=z->w[i+1]&1;
            z->w[i]|=(lsb<<(MIRACL-1));
        }

        MR_OUT
        if (sx==0) return r;
        else       return (-r);
#endif
    }

#ifdef MR_FP_ROUNDING
    in=mr_invert(n);
#endif
    if (n<0)
    {
        n=(-n);
#ifdef MR_FP_ROUNDING
        r=(int)mr_sdiv(_MIPP_ x,(mr_small)n,in,z);
#else
        r=(int)mr_sdiv(_MIPP_ x,(mr_small)n,z);
#endif
        if (z->len!=0) z->len^=MR_MSBIT;
    }
#ifdef MR_FP_ROUNDING
    else r=(int)mr_sdiv(_MIPP_ x,(mr_small)n,in,z);
#else
    else r=(int)mr_sdiv(_MIPP_ x,(mr_small)n,z);
#endif
    MR_OUT
    if (sx==0) return r;
    else       return (-r);
}

int remain(_MIPD_ big x,int n)
{ /* return integer remainder when x divided by n */
    int r;
    mr_lentype sx;
#ifdef MR_FP
    mr_small dres;
#endif
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return FALSE;

    MR_IN(88);

    sx=(x->len&MR_MSBIT);

    if (n==2 && MR_REMAIN(mr_mip->base,2)==0)
    { /* fast odd/even check if base is even */
        MR_OUT
        if ((int)MR_REMAIN(x->w[0],2)==0) return 0;
        else
        {
            if (sx==0) return 1;
            else       return (-1);
        } 
    }
    if (n==8 && MR_REMAIN(mr_mip->base,8)==0)
    { /* fast check */
        MR_OUT
        r=(int)MR_REMAIN(x->w[0],8);
        if (sx!=0) r=-r;
        return r;
    }
    
    copy(x,mr_mip->w0);
    r=subdiv(_MIPP_ mr_mip->w0,n,mr_mip->w0);
    MR_OUT
    return r;
}

BOOL subdivisible(_MIPD_ big x,int n)
{
    if (remain(_MIPP_ x,n)==0) return TRUE;
    else                return FALSE;
}

int hamming(_MIPD_ big x)
{
    int h;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return 0;
    MR_IN(148);
    h=0;
    copy(x,mr_mip->w1);
    absol(mr_mip->w1,mr_mip->w1);
    while (size(mr_mip->w1)!=0)
        h+=subdiv(_MIPP_ mr_mip->w1,2,mr_mip->w1);
    
    MR_OUT
    return h;
}

void bytes_to_big(_MIPD_ int len,char *ptr,big x)
{ /* convert len bytes into a big           *
   * The first byte is the Most significant */
    int i,j,m,n,r;
    unsigned int dig;
    unsigned char ch;
    mr_small wrd;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;
    MR_IN(140);

    zero(x);

    if (len<=0)
    {
        MR_OUT
        return;
    }
/* remove leading zeros.. */

    while (*ptr==0) 
    {
        ptr++; len--;
        if (len==0) 
        {
            MR_OUT
            return;
        } 
    }

#ifndef MR_SIMPLE_BASE
    if (mr_mip->base==0)
    { /* pack bytes directly into big */
#endif
#ifndef MR_NOFULLWIDTH
        m=MIRACL/8;  
        n=len/m;

        r=len%m;
		wrd=(mr_small)0;  
        if (r!=0)
        {
            n++; 
            for (j=0;j<r;j++) {wrd<<=8; wrd|=MR_TOBYTE(*ptr++); }
        }
        x->len=n;
        if (n>mr_mip->nib && mr_mip->check)
        {
            mr_berror(_MIPP_ MR_ERR_OVERFLOW);
            MR_OUT
            return;
        }
        if (r!=0) 
        {
            n--;
            x->w[n]=wrd;
        }

        for (i=n-1;i>=0;i--)
        {
            for (j=0;j<m;j++) { wrd<<=8; wrd|=MR_TOBYTE(*ptr++); }
            x->w[i]=wrd;
        }
        mr_lzero(x);     /* needed */
#endif
#ifndef MR_SIMPLE_BASE
    }
    else
    {
        for (i=0;i<len;i++)
        {
            if (mr_mip->ERNUM) break;
#if MIRACL==8
            mr_shift(_MIPP_ x,1,x);
#else
            premult(_MIPP_ x,256,x);
#endif
            ch=MR_TOBYTE(ptr[i]);
            dig=ch;  
            incr(_MIPP_ x,(int)dig,x);
        }
    }
#endif
    MR_OUT
} 

int big_to_bytes(_MIPD_ int max,big x,char *ptr,BOOL justify)
{ /* convert big into octet string */
    int i,j,r,m,n,len,start;
    unsigned int dig;
    unsigned char ch;
    mr_small wrd;

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return 0;

    if (size(x)==0 || (max<=0 && justify)) return 0; 
    MR_IN(141);

    mr_lzero(x);        /* should not be needed.... */
#ifndef MR_SIMPLE_BASE
    if (mr_mip->base==0)
    {
#endif
#ifndef MR_NOFULLWIDTH
        m=MIRACL/8;
        n=(int)(x->len&MR_OBITS);
        n--;
        len=n*m;
        wrd=x->w[n]; /* most significant */
        r=0;
        while (wrd!=(mr_small)0) { r++; wrd>>=8; len++;}
        r%=m;

        if (max>0 && len>max)
        {
            mr_berror(_MIPP_ MR_ERR_TOO_BIG);
            MR_OUT
            return 0; 
        }

        if (justify)
        {
            start=max-len;
            for (i=0;i<start;i++) ptr[i]=0; 
        }
        else start=0;
        
        if (r!=0)
        {
            wrd=x->w[n--];
            for (i=r-1;i>=0;i--)
            {
                ptr[start+i]=(char)(wrd&0xFF);
                wrd>>=8;
            }  
        }

        for (i=r;i<len;i+=m)
        {
            wrd=x->w[n--];
            for (j=m-1;j>=0;j--)
            {
                ptr[start+i+j]=(char)(wrd&0xFF);
                wrd>>=8;
            }
        }
#endif
#ifndef MR_SIMPLE_BASE
    }
    else
    {
        copy(x,mr_mip->w1);
        for (len=0;;len++)
        {
            if (mr_mip->ERNUM) break;

            if (size(mr_mip->w1)==0)
            {
                if (justify)
                {
                   if (len==max) break;
                }
                else break;
            }

            if (max>0 && len>=max)
            {
                mr_berror(_MIPP_ MR_ERR_TOO_BIG);
                MR_OUT
                return 0; 
            }
#if MIRACL==8
            ch=mr_mip->w1->w[0];
            mr_shift(_MIPP_ mr_mip->w1,-1,mr_mip->w1);
#else
            dig=(unsigned int)subdiv(_MIPP_ mr_mip->w1,256,mr_mip->w1);
            ch=MR_TOBYTE(dig);
#endif
            for (i=len;i>0;i--) ptr[i]=ptr[i-1];
            ptr[0]=MR_TOBYTE(ch);
        }
    }
#endif
    MR_OUT
    if (justify) return max;
    else         return len;
}

#ifndef MR_NO_ECC_MULTIADD

/* Solinas's Joint Sparse Form */

void mr_jsf(_MIPD_ big k0,big k1,big u0p,big u0m,big u1p,big u1m)
{
    int j,u0,u1,d0,d1,l0,l1;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (mr_mip->ERNUM) return;   

    MR_IN(191)

    d0=d1=0;

    convert(_MIPP_ 1,mr_mip->w1);
    copy(k0,mr_mip->w2);
    copy(k1,mr_mip->w3);
    zero(u0p); zero(u0m); zero(u1p); zero(u1m);

    j=0;
    while (!mr_mip->ERNUM)
    {
        if (size(mr_mip->w2)==0 && d0==0 && size(mr_mip->w3)==0 && d1==0) break;
        l0=remain(_MIPP_ mr_mip->w2,8);
        l0=(l0+d0)&0x7;
        l1=remain(_MIPP_ mr_mip->w3,8);
        l1=(l1+d1)&0x7;

        if (l0%2==0) u0=0;
        else
        {
            u0=2-(l0%4);
            if ((l0==3 || l0==5) && l1%4==2) u0=-u0;
        }
        if (l1%2==0) u1=0;
        else
        {
            u1=2-(l1%4);
            if ((l1==3 || l1==5) && l0%4==2) u1=-u1;
        }
#ifndef MR_ALWAYS_BINARY
        if (mr_mip->base==mr_mip->base2)
        {
#endif
            if (u0>0) mr_addbit(_MIPP_ u0p,j);
            if (u0<0) mr_addbit(_MIPP_ u0m,j);
            if (u1>0) mr_addbit(_MIPP_ u1p,j);
            if (u1<0) mr_addbit(_MIPP_ u1m,j);

#ifndef MR_ALWAYS_BINARY
        }
        else
        {
            if (u0>0) add(_MIPP_ u0p,mr_mip->w1,u0p);
            if (u0<0) add(_MIPP_ u0m,mr_mip->w1,u0m);
            if (u1>0) add(_MIPP_ u1p,mr_mip->w1,u1p);
            if (u1<0) add(_MIPP_ u1m,mr_mip->w1,u1m);
        }
#endif
      
        if (d0+d0==1+u0) d0=1-d0;
        if (d1+d1==1+u1) d1=1-d1;

        subdiv(_MIPP_ mr_mip->w2,2,mr_mip->w2);
        subdiv(_MIPP_ mr_mip->w3,2,mr_mip->w3);

#ifndef MR_ALWAYS_BINARY
        if (mr_mip->base==mr_mip->base2)
#endif
            j++;
#ifndef MR_ALWAYS_BINARY
        else
            premult(_MIPP_ mr_mip->w1,2,mr_mip->w1);
#endif        
    }
    MR_OUT
    return;
}

#endif