mrgf2mnew.c

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

tt[8]=_mm_srli_epi64(tt[8],4);
tt[4]=_mm_srli_epi64(tt[8],1);
tt[2]=_mm_srli_epi64(tt[4],1);
tt[1]=_mm_srli_epi64(tt[2],1);
tt[3]=tt[5]=tt[7]=tt[9]=tt[11]=tt[13]=tt[15]=tt[1];
tt[3]=_mm_xor_si128(tt[3],tt[2]);
tt[5]=_mm_xor_si128(tt[5],tt[4]);
tt[9]=_mm_xor_si128(tt[9],tt[8]);
tt[6]=_mm_slli_epi64(tt[3],1);
tt[7]=_mm_xor_si128(tt[7],tt[6]);
tt[10]=_mm_slli_epi64(tt[5],1);
tt[11]=_mm_xor_si128(tt[11],tt[10]);
tt[12]=_mm_slli_epi64(tt[6],1);
tt[13]=_mm_xor_si128(tt[13],tt[12]);
tt[14]=_mm_slli_epi64(tt[7],1);
tt[15]=_mm_xor_si128(tt[15],tt[14]);

    tb0=(a&TOPBIT);      
    tb0>>=M1;            
    tb1=(a&SECBIT)<<1;      
    tb1>>=M1;
    tb2=(a&THDBIT)<<2;
    tb2>>=M1;
    tb3=(a&FRHBIT)<<3;
    tb3>>=M1;
	tb4=(a&FIFBIT)<<4;
	tb4>>=M1;
	tb5=(a&SIXBIT)<<5;
	tb5>>=M1;
	tb6=(a&SEVBIT)<<6;
	tb6>>=M1;

pp=_mm_xor_si128(tt[b&0xF],_mm_slli_epi64(tt[(b>>4)&0xF],4));
pp=_mm_xor_si128(pp, _mm_slli_si128( _mm_xor_si128(tt[(b>>8)&0xF], _mm_slli_epi64(tt[(b>>12)&0xF],4))  ,1) );
pp=_mm_xor_si128(pp, _mm_slli_si128(_mm_xor_si128(tt[(b>>16)&0xF], _mm_slli_epi64(tt[(b>>20)&0xF],4))    ,2) );
pp=_mm_xor_si128(pp, _mm_slli_si128(_mm_xor_si128(tt[(b>>24)&0xF], _mm_slli_epi64(tt[(b>>28)&0xF],4))    ,3) );
pp=_mm_xor_si128(pp, _mm_slli_si128(_mm_xor_si128(tt[(b>>32)&0xF], _mm_slli_epi64(tt[(b>>36)&0xF],4))    ,4) );
pp=_mm_xor_si128(pp, _mm_slli_si128(_mm_xor_si128(tt[(b>>40)&0xF], _mm_slli_epi64(tt[(b>>44)&0xF],4))    ,5) );
pp=_mm_xor_si128(pp, _mm_slli_si128(_mm_xor_si128(tt[(b>>48)&0xF], _mm_slli_epi64(tt[(b>>52)&0xF],4))    ,6) );
pp=_mm_xor_si128(pp, _mm_slli_si128(_mm_xor_si128(tt[(b>>56)&0xF], _mm_slli_epi64(tt[(b>>60)],4))    ,7) );

_mm_store_si128((__m128i*)xx,pp);
p=xx[0];
q=xx[1];

    p^=(tb0&(kb<<M1));
    q^=(tb0&(kb>>1));
    p^=(tb1&(kb<<M2));
    q^=(tb1&(kb>>2));
    p^=(tb2&(kb<<M3));
    q^=(tb2&(kb>>3));
	p^=(tb3&(kb<<M4));
    q^=(tb3&(kb>>4));
    p^=(tb4&(kb<<M5));
    q^=(tb4&(kb>>5));
    p^=(tb5&(kb<<M6));
    q^=(tb5&(kb>>6));
    p^=(tb6&(kb<<M7));
    q^=(tb6&(kb>>7));

    *r=p;
    return q;
*/
/*
#if MIRACL <= 32
    t[0]=0;            
    t[3]=t[2]=a<<1;       
    t[1]=t[2]>>1;
    t[3]^=t[1];

    tb0=(mr_utype)(a&TOPBIT);     
    tb0>>=M1;             
#else
    t[0]=0;        
	t[8]=(a<<3);
    t[4]=t[8]>>1;
    t[2]=t[4]>>1;
    t[1]=t[2]>>1;
    t[3]=t[5]=t[7]=t[9]=t[11]=t[13]=t[15]=t[1];
    t[3]^=t[2];
    t[5]^=t[4];
    t[9]^=t[8]; 
    t[6]=t[3]<<1;
    t[7]^=t[6];
    t[10]=t[5]<<1;
    t[11]^=t[10];
    t[12]=t[6]<<1;
    t[13]^=t[12];
    t[14]=t[7]<<1;
    t[15]^=t[14];

    tb0=(a&TOPBIT);       
    tb0>>=M1;             
    tb1=(a&SECBIT)<<1;      
    tb1>>=M1;
    tb2=(a&THDBIT)<<2;
    tb2>>=M1;
*/
/*    tb3=(a&FRHBIT)<<3;
    tb3>>=M1;
	tb4=(a&FIFBIT)<<4;
	tb4>>=M1;
	tb5=(a&SIXBIT)<<5;
	tb5>>=M1;
	tb6=(a&SEVBIT)<<6;
	tb6>>=M1;*/
/*
#endif

#if MIRACL == 8
#define UNWOUNDM
    p=q=t[b&3];                       q>>=2; 
    x=t[(b>>2)&3];  q^=x; p^=(x<<2);  q>>=2;   
    x=t[(b>>4)&3];  q^=x; p^=(x<<4);  q>>=2;   
    x=t[(b>>6)];    q^=x; p^=(x<<6);  q>>=2; 
#endif

#if MIRACL == 16
#define UNWOUNDM
    p=q=t[b&3];                       q>>=2;
    x=t[(b>>2)&3];  q^=x; p^=(x<<2);  q>>=2;   
    x=t[(b>>4)&3];  q^=x; p^=(x<<4);  q>>=2;   
    x=t[(b>>6)&3];  q^=x; p^=(x<<6);  q>>=2;
    x=t[(b>>8)&3];  q^=x; p^=(x<<8);  q>>=2;
    x=t[(b>>10)&3]; q^=x; p^=(x<<10); q>>=2;
    x=t[(b>>12)&3]; q^=x; p^=(x<<12); q>>=2;
    x=t[(b>>14)];   q^=x; p^=(x<<14); q>>=2;
#endif

#if MIRACL == 32
#define UNWOUNDM
    p=q=t[b&3];                       q>>=2;
    x=t[(b>>2)&3];  q^=x; p^=(x<<2);  q>>=2;  
    x=t[(b>>4)&3];  q^=x; p^=(x<<4);  q>>=2;  
    x=t[(b>>6)&3];  q^=x; p^=(x<<6);  q>>=2;
    x=t[(b>>8)&3];  q^=x; p^=(x<<8);  q>>=2;
    x=t[(b>>10)&3]; q^=x; p^=(x<<10); q>>=2;
    x=t[(b>>12)&3]; q^=x; p^=(x<<12); q>>=2;
    x=t[(b>>14)&3]; q^=x; p^=(x<<14); q>>=2;
    x=t[(b>>16)&3]; q^=x; p^=(x<<16); q>>=2;
    x=t[(b>>18)&3]; q^=x; p^=(x<<18); q>>=2;
    x=t[(b>>20)&3]; q^=x; p^=(x<<20); q>>=2;
    x=t[(b>>22)&3]; q^=x; p^=(x<<22); q>>=2;
    x=t[(b>>24)&3]; q^=x; p^=(x<<24); q>>=2;
    x=t[(b>>26)&3]; q^=x; p^=(x<<26); q>>=2;
    x=t[(b>>28)&3]; q^=x; p^=(x<<28); q>>=2;
    x=t[(b>>30)];   q^=x; p^=(x<<30); q>>=2;
#endif

#if MIRACL == 64
#define UNWOUNDM
*/
/*
	p=q=t[b&0xF]^(t[(b>>4)&0xF]<<4);                                      q>>=8;
    x=t[(b>>8)&0xF]^(t[(b>>12)&0xF]<<4);   q^=x; p^=(x<<8);   q>>=8;
    x=t[(b>>16)&0xF]^(t[(b>>20)&0xF]<<4); q^=x; p^=(x<<16);  q>>=8;
    x=t[(b>>24)&0xF]^(t[(b>>28)&0xF]<<4); q^=x; p^=(x<<24);  q>>=8;
    x=t[(b>>32)&0xF]^(t[(b>>36)&0xF]<<4); q^=x; p^=(x<<32);  q>>=8;
    x=t[(b>>40)&0xF]^(t[(b>>44)&0xF]<<4); q^=x; p^=(x<<40);  q>>=8;
    x=t[(b>>48)&0xF]^(t[(b>>52)&0xF]<<4); q^=x; p^=(x<<48);  q>>=8;
    x=t[(b>>56)&0xF]^(t[(b>>60)]<<4);       q^=x; p^=(x<<56);  q>>=8;
*/
/*
    p=q=t[b&0xf];                       q>>=4;
    x=t[(b>>4)&0xf];  q^=x; p^=(x<<4);  q>>=4;
    x=t[(b>>8)&0xf];  q^=x; p^=(x<<8);  q>>=4;
    x=t[(b>>12)&0xf]; q^=x; p^=(x<<12); q>>=4;
    x=t[(b>>16)&0xf]; q^=x; p^=(x<<16); q>>=4;
    x=t[(b>>20)&0xf]; q^=x; p^=(x<<20); q>>=4;
    x=t[(b>>24)&0xf]; q^=x; p^=(x<<24); q>>=4;
    x=t[(b>>28)&0xf]; q^=x; p^=(x<<28); q>>=4;
    x=t[(b>>32)&0xf]; q^=x; p^=(x<<32); q>>=4;
    x=t[(b>>36)&0xf]; q^=x; p^=(x<<36); q>>=4;
    x=t[(b>>40)&0xf]; q^=x; p^=(x<<40); q>>=4;
    x=t[(b>>44)&0xf]; q^=x; p^=(x<<44); q>>=4;
    x=t[(b>>48)&0xf]; q^=x; p^=(x<<48); q>>=4;
    x=t[(b>>52)&0xf]; q^=x; p^=(x<<52); q>>=4;
    x=t[(b>>56)&0xf]; q^=x; p^=(x<<56); q>>=4;
    x=t[(b>>60)];       q^=x; p^=(x<<60); q>>=4;

#endif

#ifndef UNWOUNDM

    q=p=(mr_small)0;
    for (k=0;k<MIRACL;k+=8)
    {                 
        q^=(t[b&3]);   
        b>>=2; 
        p>>=2; 
        p|=q<<M2;
        q>>=2;

        q^=(t[b&3]);
        b>>=2;
        p>>=2;
        p|=q<<M2;
        q>>=2;

        q^=(t[b&3]);
        b>>=2;
        p>>=2;
        p|=q<<M2;
        q>>=2;

        q^=(t[b&3]);
        b>>=2;
        p>>=2;
        p|=q<<M2;
        q>>=2;
    }
#endif

#if MIRACL <= 32
    p^=(tb0&(kb<<M1));  
    q^=(tb0&(kb>>1));       
#else
    p^=(tb0&(kb<<M1));
    q^=(tb0&(kb>>1));
    p^=(tb1&(kb<<M2));
    q^=(tb1&(kb>>2));
    p^=(tb2&(kb<<M3));
    q^=(tb2&(kb>>3));
*/
/*	p^=(tb3&(kb<<M4));
    q^=(tb3&(kb>>4));
    p^=(tb4&(kb<<M5));
    q^=(tb4&(kb>>5));
    p^=(tb5&(kb<<M6));
    q^=(tb5&(kb>>6));
    p^=(tb6&(kb<<M7));
    q^=(tb6&(kb>>7)); */
/*#endif

    *r=p;
    return q; */
}

#endif

#endif

static int numbits(big x)
{ /* return degree of x */
    mr_small *gx=x->w,bit=TOPBIT;
    int m,k=x->len;
    if (k==0) return 0;
    m=k*MIRACL;
    while (!(gx[k-1]&bit))
    {
        m--;
        bit>>=1;
    }
    return m;
}

int degree2(big x)
{ /* returns -1 for x=0 */
    return (numbits(x)-1);
}

/*
static int zerobits(big x)
{ 
    int m,n,k;
    mr_small *gx,lsb,bit=1;
    k=x->len; 
    if (k==0) return (-1);
    gx=x->w;
    for (m=0;m<k;m++)
    {
        if (gx[m]==0) continue;
        n=0;
        lsb=gx[m];
        while (!(bit&lsb))
        {
            n++; 
            bit<<=1;
        }
        break;
    }
    return (MIRACL*m+n);
}

static void shiftrightbits(big x,int m)
{
    int i,k=x->len;
    int w=m/MIRACL;
    int b=m%MIRACL;  
    mr_small *gx=x->w;
    if (k==0 || m==0) return;
    if (w>0)
    {
        for (i=0;i<k-w;i++)
            gx[i]=gx[i+w];
        for (i=k-w;i<k;i++) gx[i]=0;
        x->len-=w;
    }
    if (b!=0) 
    {
        for (i=0;i<k-w-1;i++)
            gx[i]=(gx[i]>>b)|(gx[i+1]<<(MIRACL-b));   
        gx[k-w-1]>>=b;
        if (gx[k-w-1]==0) x->len--;
    }
}
*/

static void shiftleftbits(big x,int m)
{
    int i,k=x->len;
    mr_small j; 
    int w=m/MIRACL;  /* words */
    int b=m%MIRACL;  /* bits  */
    mr_small *gx=x->w;
    if (k==0 || m==0) return;
    if (w>0)
    {
        for (i=k+w-1;i>=w;i--)
            gx[i]=gx[i-w];
        for (i=w-1;i>=0;i--) gx[i]=0;
        x->len+=w;
    }
/* time critical */
    if (b!=0) 
    {
        j=gx[k+w-1]>>(MIRACL-b);
        if (j!=0)
        {
            x->len++;
            gx[k+w]=j;
        }
        for (i=k+w-1;i>w;i--)
        {
            gx[i]=(gx[i]<<b)|(gx[i-1]>>(MIRACL-b));
        }
        gx[w]<<=b;
    }
}

static void square2(big x,big w)
{ /* w=x*x where x can be NULL so be careful */
    int i,j,n,m;
    mr_small a,t,r,*gw;

    static const mr_small look[16]=
    {0,(mr_small)1<<M8,(mr_small)4<<M8,(mr_small)5<<M8,(mr_small)16<<M8,
    (mr_small)17<<M8,(mr_small)20<<M8,(mr_small)21<<M8,(mr_small)64<<M8,
    (mr_small)65<<M8,(mr_small)68<<M8,(mr_small)69<<M8,(mr_small)80<<M8,
    (mr_small)81<<M8,(mr_small)84<<M8,(mr_small)85<<M8};

    if (x!=w) copy(x,w);
    n=w->len;
    if (n==0) return;
    m=n+n;
    w->len=m;
    gw=w->w; 

    for (i=n-1;i>=0;i--)
    {
        a=gw[i];

#if MIRACL == 8
#define UNWOUNDS
        gw[i+i]=look[a&0xF];
        gw[i+i+1]=look[(a>>4)];
#endif

#if MIRACL == 16
#define UNWOUNDS
        gw[i+i]=(look[a&0xF]>>8)|look[(a>>4)&0xF];
        gw[i+i+1]=(look[(a>>8)&0xF]>>8)|look[(a>>12)];
#endif

#if MIRACL == 32
#define UNWOUNDS
        gw[i+i]=(look[a&0xF]>>24)|(look[(a>>4)&0xF]>>16)|(look[(a>>8)&0xF]>>8)|look[(a>>12)&0xF]; 
        gw[i+i+1]=(look[(a>>16)&0xF]>>24)|(look[(a>>20)&0xF]>>16)|(look[(a>>24)&0xF]>>8)|look[(a>>28)];
#endif

#ifndef UNWOUNDS

        r=0;
        for (j=0;j<MIRACL/2;j+=4)
        {
            t=look[a&0xF];
            a>>=4;
            r>>=8;
            r|=t;
        }
        gw[i+i]=r; r=0;

        for (j=0;j<MIRACL/2;j+=4)
        {
            t=look[a&0xF];
            a>>=4;
            r>>=8;
            r|=t;
        }
        gw[i+i+1]=r;

#endif

    }
    if (gw[m-1]==0) 
    {
        w->len--;
        if (gw[m-2]==0)
            mr_lzero(w);
    }
}

/* Use karatsuba to multiply two polynomials with coefficients in GF(2^m) */

#ifndef MR_STATIC

void karmul2_poly(_MIPD_ int n,big *t,big *x,big *y,big *z)
{
    int m,nd2,nd,md,md2;                          
    if (n==1) 
    { /* finished */
        modmult2(_MIPP_ *x,*y,*z);
        zero(z[1]);
        return;
    }       
    if (n==2)
    {  /* in-line 2x2 */
        modmult2(_MIPP_ x[0],y[0],z[0]);
        modmult2(_MIPP_ x[1],y[1],z[2]);
        add2(x[0],x[1],t[0]);
        add2(y[0],y[1],t[1]);
        modmult2(_MIPP_ t[0],t[1],z[1]);
        add2(z[1],z[0],z[1]);
        add2(z[1],z[2],z[1]);
        zero(z[3]);
        return;
    }

    if (n==3)
    {
        modmult2(_MIPP_ x[0],y[0],z[0]); 
        modmult2(_MIPP_ x[1],y[1],z[2]); 
        modmult2(_MIPP_ x[2],y[2],z[4]); 
        add2(x[0],x[1],t[0]);
        add2(y[0],y[1],t[1]);
        modmult2(_MIPP_ t[0],t[1],z[1]); 
        add2(z[1],z[0],z[1]);  
        add2(z[1],z[2],z[1]);  
        add2(x[1],x[2],t[0]);
        add2(y[1],y[2],t[1]);
        modmult2(_MIPP_ t[0],t[1],z[3]); 
        add2(z[3],z[2],z[3]);
        add2(z[3],z[4],z[3]); 
        add2(x[0],x[2],t[0]);
        add2(y[0],y[2],t[1]);   
        modmult2(_MIPP_ t[0],t[1],t[0]); 
        add2(z[2],t[0],z[2]);
        add2(z[2],z[0],z[2]);
        add2(z[2],z[4],z[2]); 
        zero(z[5]);
        return;
    }

    if (n%2==0)
    {
        md=nd=n;
        md2=nd2=n/2;
    }
    else
    {
        nd=n+1;
        md=n-1;
        nd2=nd/2; md2=md/2;
    }

    for (m=0;m<nd2;m++)
    {
        copy(x[m],z[m]);
        copy(y[m],z[nd2+m]);
    }
    for (m=0;m<md2;m++)
    { 
        add2(z[m],x[nd2+m],z[m]);