mrgf2mnew.c

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

        lx=x->len; ly=y->len; lz=z->len;
        lm=lx; if (ly>lx) lm=ly;

        for (i=0;i<lm;i++)
            gz[i]=gx[i]^gy[i];
        for (i=lm;i<lz;i++)
            gz[i]=0;
        z->len=lm;
        if (gz[lm-1]==0) mr_lzero(z);
    }
}

static void remain2(_MIPD_ big y,big x)
{ /* generic "remainder" program. x%=y */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    int my=numbits(y);
    int mx=numbits(x);
    while (mx>=my)
    {
        copy(y,mr_mip->w7);
        shiftleftbits(mr_mip->w7,mx-my);
        add2(x,mr_mip->w7,x);    
        mx=numbits(x);
    }
    return;
}

void gcd2(_MIPD_ big x,big y,big g)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (size(y)==0) 
    {
        copy(x,g);
        return;
    }
    copy(x,mr_mip->w1);
    copy(y,mr_mip->w2);
    forever
    {
        remain2(_MIPP_ mr_mip->w2,mr_mip->w1);
        if (size(mr_mip->w1)==0) break;
        copy(mr_mip->w1,mr_mip->w3);
        copy(mr_mip->w2,mr_mip->w1);
        copy(mr_mip->w3,mr_mip->w2);
    }
    copy(mr_mip->w2,g);
}


/* See "Elliptic Curves in Cryptography", Blake, Seroussi & Smart, 
   Cambridge University Press, 1999, page 20, for this fast reduction
   routine - algorithm II.9 */

void reduce2(_MIPD_ big y,big x)
{ /* reduction wrt the trinomial or pentanomial modulus        *
   * Note that this is linear O(n), and thus not time critical */
    int k1,k2,k3,k4,ls1,ls2,ls3,ls4,rs1,rs2,rs3,rs4,i;
    int M,A,B,C;
    int xl;
    mr_small top,*gx,w;

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (x!=y) copy(y,x);
    xl=x->len;
    gx=x->w;

    M=mr_mip->M;
    A=mr_mip->AA;
    if (A==0)
    {
        mr_berror(_MIPP_ MR_ERR_NO_BASIS);
        return;
    }
    B=mr_mip->BB;
    C=mr_mip->CC;

 
/* If optimizing agressively it makes sense to make this code specific to a particular field
   For example code like this can be optimized for the case 
   m=163. Note that the general purpose code involves lots of branches - these cause breaks in 
   the pipeline and they are slow. Further loop unrolling would be even faster...

   Version 5.10 - optimal code for 32-bit processors and for some NIST curves added
   Version 5.22 - some code for a 16-bit processor..

   Version 5.23 - Use findbase.cpp to find "best" irreducible polynomial
   Version 5.23 - Use utility irp.cpp to automatically generate optimal code for insertion here
*/

#if MIRACL == 8

    if (M==163 && A==7 && B==6 && C==3)
    {
        for (i=xl-1;i>=21;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-19]^=(w>>4)^(w>>5);
            gx[i-20]^=(w>>3)^(w<<4)^(w<<3)^w;
            gx[i-21]^=(w<<5);
        }   /* XORs= 7 shifts= 6 */
        top=gx[20]>>3;
        gx[0]^=top;
        top<<=3;
        gx[0]^=(top<<4)^(top<<3)^top;
        gx[1]^=(top>>4)^(top>>5);
        gx[20]^=top;
        x->len=21;
        if (gx[20]==0) mr_lzero(x);
        return;
    }

    if (M==271 && A==201)
    {
        for (i=xl-1;i>=34;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-8]^=(w>>6);
            gx[i-9]^=(w<<2);
            gx[i-33]^=(w>>7);
            gx[i-34]^=(w<<1);
        }   /* XORs= 4 shifts= 4 */
        top=gx[33]>>7;
        gx[0]^=top;
        top<<=7;
        gx[24]^=(top<<2);
        gx[25]^=(top>>6);
        gx[33]^=top;
        x->len=34;
        if (gx[33]==0) mr_lzero(x);
        return;
    }

    if (M==271 && A==207 && B==175 && C==111)
    {
        for (i=xl-1;i>=34;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-8]^=w;
            gx[i-12]^=w;
            gx[i-20]^=w;
            gx[i-33]^=(w>>7);
            gx[i-34]^=(w<<1);
        }   /* XORs= 5 shifts= 2 */
        top=gx[33]>>7;
        gx[0]^=top;
        top<<=7;
        gx[13]^=top;
        gx[21]^=top;
        gx[25]^=top;
        gx[33]^=top;
        x->len=34;
        if (gx[33]==0) mr_lzero(x);
        return;
    }

#endif

#if MIRACL == 16

    if (M==163 && A==7 && B==6 && C==3)
    {
        for (i=xl-1;i>=11;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-10]^=(w>>3)^(w<<3)^(w<<4)^w;
            gx[i-11]^=(w<<13);
            gx[i-9]^=(w>>12)^(w>>13);
        }
        top=gx[10]>>3;
        gx[0]^=top;
        top<<=3;

        gx[1]^=(top>>12)^(top>>13);
        gx[0]^=(top<<4)^(top<<3)^top;

        gx[10]^=top;
        x->len=11;
        if (gx[10]==0) mr_lzero(x);
        
        return;
    }

    if (M==271 && A==201 && B==0)
    {
        for (i=xl-1;i>=17;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-17]^=(w<<1);
            gx[i-16]^=(w>>15);
            gx[i-5]^=(w<<10);
            gx[i-4]^=(w>>6);
        }
        top=gx[16]>>15;
        gx[0]^=top;
        top<<=15;
        gx[12]^=(top>>6);
        gx[11]^=(top<<10);

        gx[16]^=top;
        x->len=17;
        if (gx[16]==0) mr_lzero(x);

        return;
    }

    if (M==271 && A==207 && B==175 && C==111)
    {
        for (i=xl-1;i>=17;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-4]^=w;
            gx[i-6]^=w;
            gx[i-10]^=w;
            gx[i-16]^=(w>>15);
            gx[i-17]^=(w<<1);
        }   /* XORs= 5 shifts= 2 */
        top=gx[16]>>15;
        gx[0]^=top;
        top<<=15;
        gx[6]^=top;
        gx[10]^=top;
        gx[12]^=top;
        gx[16]^=top;
        x->len=17;
        if (gx[16]==0) mr_lzero(x);
        return;
    }

#endif

#if MIRACL == 32

    if (M==163 && A==7 && B==6 && C==3)
    {
        for (i=xl-1;i>=6;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-5]^=((w>>3)^(w<<4)^(w<<3)^w);
            gx[i-6]^=(w<<29);              
            gx[i-4]^=((w>>28)^(w>>29));
        }
        top=gx[5]>>3;
        
        gx[0]^=top;
        top<<=3;
        gx[1]^=(top>>28)^(top>>29);
        gx[0]^=top^(top<<4)^(top<<3);

        gx[5]^=top;
        
        x->len=6; 
        if (gx[5]==0) mr_lzero(x);
        
        return;
    }

    if (M==163 && A==99 && B==97 && C==3)
    {
        for (i=xl-1;i>=6;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-2]^=w^(w>>2);
            gx[i-3]^=(w<<30);
            gx[i-5]^=(w>>3)^w;
            gx[i-6]^=(w<<29);
        } 
        top=gx[5]>>3;
        gx[0]^=top;
        top<<=3;
        gx[0]^=top;
        gx[2]^=(top<<30);
        gx[3]^=top^(top>>2);
        gx[5]^=top;
        x->len=6;
        if (gx[5]==0) mr_lzero(x);
        return;
    }

    if (M==233 && A==74 && B==0)
    {
        for (i=xl-1;i>=8;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-8]^=(w<<23);
            gx[i-7]^=(w>>9);
            gx[i-5]^=(w<<1);
            gx[i-4]^=(w>>31);
        }
        top=gx[7]>>9;
        gx[0]^=top;
        gx[2]^=(top<<10);
        gx[3]^=(top>>22);
        gx[7]&=0x1FF;

        x->len=8;
        if (gx[7]==0) mr_lzero(x);
        return;
    }

    if (M==233 && A==159 && B==0)
    {
        for (i=xl-1;i>=8;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-2]^=(w>>10);
            gx[i-3]^=(w<<22);
            gx[i-7]^=(w>>9);
            gx[i-8]^=(w<<23);
        }   
        top=gx[7]>>9;
        gx[0]^=top;
        top<<=9;
        gx[4]^=(top<<22);
        gx[5]^=(top>>10);
        gx[7]^=top;
        x->len=8;
        if (gx[7]==0) mr_lzero(x);
        return;
    }

    if (M==233 && A==201 && B==105 && C==9)
    {
        for (i=xl-1;i>=8;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-1]^=w;
            gx[i-4]^=w;
            gx[i-7]^=(w>>9)^w;
            gx[i-8]^=(w<<23);
        }   
        top=gx[7]>>9;
        gx[0]^=top;
        top<<=9;
        gx[0]^=top;
        gx[3]^=top;
        gx[6]^=top;
        gx[7]^=top;
        x->len=8;
        if (gx[7]==0) mr_lzero(x);

        return;
    }

    if (M==103 && A==9 && B==0)
    {
        for (i=xl-1;i>=4;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-3]^=((w>>7)^(w<<2));
            gx[i-4]^=(w<<25);
            gx[i-2]^=(w>>30);
        }
        top=gx[3]>>7;
        gx[0]^=top;
        top<<=7;
        gx[1]^=(top>>30);
        gx[0]^=(top<<2);
        gx[3]^=top;
        x->len=4;
        if (gx[3]==0) mr_lzero(x);

        return;
    }

    if (M==283 && A==12 && B==7 && C==5)
    {
        for (i=xl-1;i>=9;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-9]^=(w<<5)^(w<<10)^(w<<12)^(w<<17);
            gx[i-8]^=(w>>27)^(w>>22)^(w>>20)^(w>>15);
        }

        top=gx[8]>>27;
        gx[0]^=top^(top<<5)^(top<<7)^(top<<12);
        gx[8]&=0x7FFFFFF;

        x->len=9;
        if (gx[8]==0) mr_lzero(x);
        return;
    }

    if (M==283 && A==249 && B==219 && C==27)
    {
        for (i=xl-1;i>=9;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-1]^=(w>>2);
            gx[i-2]^=(w<<30)^w;
            gx[i-8]^=(w>>27)^w;
            gx[i-9]^=(w<<5);
        }   /* XORs= 6 shifts= 4 */
        top=gx[8]>>27;
        gx[0]^=top;
        top<<=27;
        gx[0]^=top;
        gx[6]^=(top<<30)^top;
        gx[7]^=(top>>2);
        gx[8]^=top;
        x->len=9;
        if (gx[8]==0) mr_lzero(x);
        return;
    }

    if (M==313 && A==121 && B==0)
    {
        for (i=xl-1;i>=10;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-6]^=w;
            gx[i-9]^=(w>>25);
            gx[i-10]^=(w<<7);
        }  
        top=gx[9]>>25;
        gx[0]^=top;
        top<<=25;
        gx[3]^=top;
        gx[9]^=top;
        x->len=10;
        if (gx[9]==0) mr_lzero(x);
        return;
    }

    if (M==379 && A==317 && B==315 && C==283)
    {
        for (i=xl-1;i>=12;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-1]^=(w>>30);
            gx[i-2]^=(w<<2)^w;
            gx[i-3]^=w;
            gx[i-11]^=(w>>27);
            gx[i-12]^=(w<<5);
        }   /* XORs= 6 shifts= 4 */
        top=gx[11]>>27;
        gx[0]^=top;
        top<<=27;
        gx[8]^=top;
        gx[9]^=(top<<2)^top;
        gx[10]^=(top>>30);
        gx[11]^=top;
        x->len=12;
        if (gx[11]==0) mr_lzero(x);
        return;
    }

    if (M==571 && A==10 && B==5 && C==2)
    {
        for (i=xl-1;i>=18;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-18]^=(w<<5)^(w<<7)^(w<<10)^(w<<15);
            gx[i-17]^=(w>>27)^(w>>25)^(w>>22)^(w>>17);
        }

        top=gx[17]>>27;
        gx[0]^=top^(top<<2)^(top<<5)^(top<<10);
        gx[17]&=0x7FFFFFF;

        x->len=18;
        if (gx[17]==0) mr_lzero(x);

        return;
    }

    if (M==571 && A==507 && B==475 && C==417)
    {
        for (i=xl-1;i>=18;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-2]^=w;
            gx[i-3]^=w;
            gx[i-4]^=(w>>26);
            gx[i-5]^=(w<<6);
            gx[i-17]^=(w>>27);
            gx[i-18]^=(w<<5);