etat271.c

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

    fadd2(mr_mip->w13,c[0],c[2]);
    fincr2(mr_mip->w11,c[2]);
    fincr2(mr_mip->w1,c[2]);

    fincr2(mr_mip->w1,c[1]);	
    fincr2(mr_mip->w10,mr_mip->w13);
    fincr2(mr_mip->w13,c[1]);

    fincr2(mr_mip->w2,mr_mip->w13);
    fincr2(mr_mip->w13,c[0]);

    return;
}

/* Frobenius action - GF(2^{4m}) ^ 2^m */

void powq(_MIPD_ big *x)
{
    fcopy2(x[1],mr_mip->w1);
    fincr2(x[1],x[0]);
    fcopy2(x[2],x[1]);
    fincr2(x[3],x[1]);
    fcopy2(mr_mip->w1,x[2]);
}

/* return degree of GF(2^{4m}) polynomial */

int degree(big *c)
{
    if (size(c[3])!=0) return 3;
    if (size(c[2])!=0) return 2;
    if (size(c[1])!=0) return 1;
    return 0;
}

/* Raise a GF(2^{4m}) to a power */

void power4(_MIPD_ big *a,big k,big *u)
{ 
    int i,j,m,nb,n,nbw,nzs;
    big u2[4],t[4][4];
#ifndef MR_STATIC
    char *mem=memalloc(_MIPP_ 20);
#else
    char mem[MR_BIG_RESERVE(20)];       
    memset(mem,0,MR_BIG_RESERVE(20));
#endif
    m=0;
    for (i=0;i<4;i++)
        for (j=0;j<4;j++) t[i][j]=mirvar_mem(_MIPP_ mem,m++);

    u2[0]=mirvar_mem(_MIPP_ mem,16);
    u2[1]=mirvar_mem(_MIPP_ mem,17);
    u2[2]=mirvar_mem(_MIPP_ mem,18);
    u2[3]=mirvar_mem(_MIPP_ mem,19);

    if(size(k)==0) 
    {
        convert(_MIPP_ 1,u[0]);
        zero(u[1]);
        zero(u[2]);
        zero(u[3]);
#ifndef MR_STATIC
        memkill(_MIPP_ mem,20);
#else
        memset(mem,0,MR_BIG_RESERVE(20));
#endif
        return;
    }

    for (i=0;i<4;i++)
        fcopy2(a[i],u[i]);

    if (size(k)==1)
    {
#ifndef MR_STATIC
        memkill(_MIPP_ mem,20);
#else
        memset(mem,0,MR_BIG_RESERVE(20));
#endif
        return;
    }

    square4(_MIPP_ u,u2);
    for (i=0;i<4;i++)	
        fcopy2(u[i],t[0][i]);	

    for(i=1;i<4;i++)
        mult4(_MIPP_ u2,t[i-1],t[i]);

    nb=logb2(_MIPP_ k);
    if(nb>1) for(i=nb-2;i>=0;)
    {			
        n=mr_window(_MIPP_ k,i,&nbw,&nzs,3); /* small 3 bit window to save RAM */
        for(j=0;j<nbw;j++)
            square4(_MIPP_ u,u);
        if(n>0)	mult4(_MIPP_ u,t[n/2],u);
        i-=nbw;
        if(nzs!=0)
        {
            for (j=0;j<nzs;j++) square4(_MIPP_ u,u);
            i-=nzs;	 				
        }				
    }	

#ifndef MR_STATIC
    memkill(_MIPP_ mem,20);
#else
    memset(mem,0,MR_BIG_RESERVE(20));
#endif
}

/* Inversion of GF(2^{4m}) - fast but not time critical */

void invert(_MIPD_ big *x)
{
    int degF,degG,degB,degC,d,i,j;
    big alpha,beta,gamma,BB[4],FF[5],CC[4],GG[5],t;
    big *BP=BB,*CP=CC,*FP=FF,*GP=GG,*TP;
#ifndef MR_STATIC
    char *mem=memalloc(_MIPP_ 22);  
#else
    char mem[MR_BIG_RESERVE(22)];       /* 972 bytes from the stack */
    memset(mem,0,MR_BIG_RESERVE(22));
#endif

    alpha=mirvar_mem(_MIPP_ mem,0);
    beta=mirvar_mem(_MIPP_ mem,1);
    gamma=mirvar_mem(_MIPP_ mem,2);
    t=mirvar_mem(_MIPP_ mem,3);

    for (i=0;i<4;i++)
        BB[i]=mirvar_mem(_MIPP_ mem,4+i);
    for (i=0;i<5;i++)
        FF[i]=mirvar_mem(_MIPP_ mem,8+i);
    for (i=0;i<4;i++)
        CC[i]=mirvar_mem(_MIPP_ mem,13+i);
    for (i=0;i<5;i++)
        GG[i]=mirvar_mem(_MIPP_ mem,17+i);

    convert(_MIPP_ 1,CP[0]);
    convert(_MIPP_ 1,FP[0]);
    convert(_MIPP_ 1,FP[1]);
    convert(_MIPP_ 1,FP[4]);   /* F = x^4+x+1 - irreducible polynomial for GF(2^{4m}) */

    degF=4; degG=degree(x); degC=0; degB=-1;

    if (degG==0)
    {
        inverse2(_MIPP_ x[0],x[0]);
        return;
    }

    for (i=0;i<4;i++)
    {
        fcopy2(x[i],GP[i]);
        zero(x[i]);
    }

    while (degF!=0)
    {
        if (degF<degG)
        { /* swap */
            TP=FP; FP=GP; GP=TP;  d=degF; degF=degG; degG=d;
            TP=BP; BP=CP; CP=TP;  d=degB; degB=degC; degC=d;
        }
        j=degF-degG;
        modsquare2(_MIPP_ GP[degG],alpha);
        modmult2(_MIPP_ FP[degF],GP[degG],beta);
        modmult2(_MIPP_ GP[degG],FP[degF-1],t);
        modmult2(_MIPP_ FP[degF],GP[degG-1],gamma);
        fincr2(t,gamma);
        zero(t);

        for (i=0;i<=degF;i++ )
        {
            modmult2(_MIPP_ FP[i],alpha,FP[i]);
            if (i>=j-1)
            {
                modmult2(_MIPP_ gamma,GP[i-j+1],t);
                fincr2(t,FP[i]);
            }  
            if (i>=j)
            {
                modmult2(_MIPP_ beta,GP[i-j],t); 
                fincr2(t,FP[i]);
            }
        }	        
        for (i=0;i<=degB || i<=(degC+j);i++)
        {
            modmult2(_MIPP_ BP[i],alpha,BP[i]);
            if (i>=j-1)
            {	
                modmult2(_MIPP_ gamma,CP[i-j+1],t);	
                fincr2(t,BP[i]);
            }
            if (i>=j)  
            {
                modmult2(_MIPP_ beta,CP[i-j],t);
                fincr2(t,BP[i]);
            }
        }

        while (degF>=0 && size(FP[degF])==0) degF--;
        if (degF==degG)
        {
            fcopy2(FP[degF],alpha);
            for (i=0;i<=degF;i++)
            {
                modmult2(_MIPP_ FP[i],GP[degF],FP[i]);
                modmult2(_MIPP_ alpha,GP[i],t);
                fincr2(t,FP[i]);
            } 
            for (i=0;i<=4-degF;i++)
            {
                modmult2(_MIPP_ BP[i],GP[degF],BP[i]);
                modmult2(_MIPP_ CP[i],alpha,t);
                fincr2(t,BP[i]);

            }
            while (degF>=0 && size(FP[degF])==0) degF--;
        }
        degB=3; 
        while (degB>=0 && size(BP[degB])==0) degB--;
    }

    inverse2(_MIPP_ FP[0],alpha);

    for (i=0;i<=degB;i++)
        modmult2(_MIPP_ alpha,BP[i],x[i]);
#ifndef MR_STATIC   
    memkill(_MIPP_ mem,22);
#else
    memset(mem,0,MR_BIG_RESERVE(22));
#endif
}

/* Tate Pairing - calculated from eta_T pairing */

void eta_T(_MIPD_ epoint *P,epoint *Q,big *f,big *res)
{
    big xp,yp,xq,yq,t,d;
    big miller[4],v[4],u[4];
    int i,m=M;
    int promptr;
#ifndef MR_STATIC
    char *mem=memalloc(_MIPP_ 18);  
#else
    char mem[MR_BIG_RESERVE(18)];            /* 972 bytes from stack */
    memset(mem,0,MR_BIG_RESERVE(18));
#endif

    xp=mirvar_mem(_MIPP_ mem,0);
    yp=mirvar_mem(_MIPP_ mem,1);
    xq=mirvar_mem(_MIPP_ mem,2);
    yq=mirvar_mem(_MIPP_ mem,3);
    t=mirvar_mem(_MIPP_ mem,4);
    d=mirvar_mem(_MIPP_ mem,5);
    for (i=0;i<4;i++) miller[i]=mirvar_mem(_MIPP_ mem,6+i);
    for (i=0;i<4;i++) v[i]=mirvar_mem(_MIPP_ mem,10+i);
    for (i=0;i<4;i++) u[i]=mirvar_mem(_MIPP_ mem,14+i);

    fcopy2(P->X,xp);
    fcopy2(P->Y,yp);
    fcopy2(Q->X,xq);
    fcopy2(Q->Y,yq);

    incr2(xp,1,t);       /* t=xp+1 */

    fadd2(xp,xq,d);
    incr2(d,1,d);        /* xp+xq+1 */
    modmult2(_MIPP_ d,t,d); /* t*(xp+xq+1) */
    fincr2(yp,d);
    fincr2(yq,d);
    incr2(d,B,d);
    incr2(d,1,f[0]);     /* f[0]=t*(xp+xq+1)+yp+yq+B+1 */

    convert(_MIPP_ 1,miller[0]);

    fadd2(t,xq,f[2]);       /* f[2]=t+xq   */
    incr2(f[2],1,f[1]);     /* f[1]=t+xq+1 */   
    zero(f[3]);
    promptr=0;

    for (i=0;i<(m-1)/2;i+=2)
    {
        fcopy2(xp,t);
        sqroot2(_MIPP_ xp,xp);
        sqroot2(_MIPP_ yp,yp);
        fadd2(xp,xq,d);
        modmult2(_MIPP_ d,t,d);
        fincr2(yp,d);
        fincr2(yq,d);
        fadd2(d,xp,v[0]);       /* v[0]=t*(xp+xq)+yp+yq+xp */
        fadd2(t,xq,v[2]);       /* v[2]=t+xq   */
        incr2(v[2],1,v[1]);     /* v[1]=t+xq+1 */
        modsquare2(_MIPP_ xq,xq);  /* xq*=xq */
        modsquare2(_MIPP_ yq,yq);  /* yp*=yp */

        fcopy2(xp,t);           /* same again - unlooped times 2 */

        sqroot2(_MIPP_ xp,xp);
        sqroot2(_MIPP_ yp,yp);

        fadd2(xp,xq,d);
        modmult2(_MIPP_ d,t,d);
        fincr2(yp,d);
        fincr2(yq,d);
        fadd2(d,xp,u[0]);   
        fadd2(t,xq,u[2]);
        incr2(u[2],1,u[1]);   
        modsquare2(_MIPP_ xq,xq);   
        modsquare2(_MIPP_ yq,yq);  

        mul(_MIPP_ u,v,u);         /* fast mul */
        mult4(_MIPP_ miller,u,miller);
    }

    mult4(_MIPP_ miller,f,miller);

    for (i=0;i<4;i++)
    {
        fcopy2(miller[i],u[i]);
        fcopy2(miller[i],v[i]);
        fcopy2(miller[i],f[i]);
    }

    /* final exponentiation */

    for (i=0;i<(m+1)/2;i++) square4(_MIPP_ u,u);  /* u*=u */    
    powq(_MIPP_ u);
    powq(_MIPP_ f);
    for(i=0;i<4;i++) fcopy2(f[i],v[i]);
    powq(_MIPP_ f);
    for(i=0;i<4;i++) fcopy2(f[i],res[i]);
    powq(_MIPP_ f);
    mult4(_MIPP_ f,u,f);
    mult4(_MIPP_ f,miller,f);
    mult4(_MIPP_ res,v,res);
    powq(_MIPP_ u);
    powq(_MIPP_ u);
    mult4(_MIPP_ res,u,res);

    /* doing inversion here could kill the stack... */

#ifndef MR_STATIC
    memkill(_MIPP_ mem,18);
#else
    memset(mem,0,MR_BIG_RESERVE(18));
#endif
}

/* ... so do inversion here to avoid stack overflow */

void tate(_MIPD_ epoint *P,epoint *Q,big *res)
{
    int i;
    big f[4];
#ifndef MR_STATIC
    char *mem=memalloc(_MIPP_ 4);  
#else
    char mem[MR_BIG_RESERVE(4)];            /* 160 bytes from stack */
    memset(mem,0,MR_BIG_RESERVE(4));
#endif
    for (i=0;i<4;i++) f[i]=mirvar_mem(_MIPP_ mem,i);

    eta_T(_MIPP_ P,Q,f,res);

    invert(_MIPP_ f);
    mult4(_MIPP_ res,f,res);

#ifndef MR_STATIC
    memkill(_MIPP_ mem,4);
#else
    memset(mem,0,MR_BIG_RESERVE(4));
#endif
}

/* Max stack requirement < 4K */

int main()
{
    big a2,a6,bx,r;
    big res[4];
    epoint *P,*Q;

    int i,romptr;
    miracl instance;                           /* sizeof(miracl)= 2000 bytes from the stack */
#ifndef MR_STATIC
#ifdef MR_GENERIC_MT
    miracl *mr_mip=mirsys(&instance,WORDS*NPW,16);
#else
    miracl *mr_mip=mirsys(WORDS*NPW,16);
#endif
    char *mem=memalloc(_MIPP_ 8);   
    char *mem1=ecp_memalloc(_MIPP_ 2);
#else
#ifdef MR_GENERIC_MT
    miracl *mr_mip=mirsys(&instance,MR_STATIC*NPW,16); /* size of bigs is fixed */
#else
    miracl *mr_mip=mirsys(&instance,MR_STATIC*NPW,16);
#endif
    char mem[MR_BIG_RESERVE(8)];               /* reserve space on the stack for 8 bigs */
    char mem1[MR_ECP_RESERVE(2)];              /* reserve space on stack for 2 curve points */
    memset(mem,0,MR_BIG_RESERVE(8));           /* clear this memory */
    memset(mem1,0,MR_ECP_RESERVE(2));          /* ~668 bytes in all  */
#endif

    /* Initialise bigs */   

    a2=mirvar_mem(_MIPP_ mem,0);
    a6=mirvar_mem(_MIPP_ mem,1);
    bx=mirvar_mem(_MIPP_ mem,2);
    for (i=0;i<4;i++)
        res[i]=mirvar_mem(_MIPP_ mem,3+i);
    r=mirvar_mem(_MIPP_ mem,7);

    /* printf("ROM size= %d\n",sizeof(rom)+sizeof(prom)); */
#ifndef MR_NO_STANDARD_IO
#ifdef MR_STATIC
    printf("n Bigs require n*%d+%d bytes\n",MR_SIZE,MR_SL);
    printf("n Points require n*%d+%d bytes\n",MR_ESIZE,MR_SL);
    printf("sizeof(miracl)= %d\n",sizeof(miracl));
#endif
#endif
    /* Initialise Elliptic curve points */

    P=epoint_init_mem(_MIPP_ mem1,0);
    Q=epoint_init_mem(_MIPP_ mem1,1);

    /* Initialise supersingular curve */

    convert(_MIPP_ 1,a2);
    convert(_MIPP_ B,a6);

    /* The -M tells MIRACL that this is a supersingular curve */

    if (!ecurve2_init(_MIPP_ -M,T,U,V,a2,a6,FALSE,MR_PROJECTIVE))
    {
#ifndef MR_NO_STANDARD_IO
        printf("Problem with the curve\n");
#endif
        return 0;
    }

    /* Get P and Q from ROM */
    /* These should have been multiplied by the cofactor 487805 = 5*97561 */
    /* 487805 is a cofactor of the group order 2^271+2^136+1 */

    romptr=0;
    init_point_from_rom(P,WORDS,rom,ROMSZ,&romptr);
    init_point_from_rom(Q,WORDS,rom,ROMSZ,&romptr);

#ifndef MR_NO_STANDARD_IO
    printf( "P= \n");
    otnum(_MIPP_ P->X,stdout);
    otnum(_MIPP_ P->Y,stdout);
    printf( "Q= \n");
    otnum(_MIPP_ Q->X,stdout);
    otnum(_MIPP_ Q->Y,stdout);
#endif

    bigbits(_MIPP_ 160,r); 

    /* Simple bilinearity test */

    tate(_MIPP_ P,Q,res);

    /* this could break the 4k stack, 2060+668+2996 >4K    */
    /* so we cannot afford much precomputation in power4   */

    power4(_MIPP_ res,r,res);   /* res=res^{sr} */

#ifndef MR_NO_STANDARD_IO
    printf( "\ne(P,Q)^r= \n");
    for (i=0;i<4;i++)
    {
        otnum(_MIPP_ res[i],stdout);
        zero(res[i]);
    }
#endif    

    ecurve2_mult(_MIPP_ r,Q,Q);   /* Q=rQ */

    epoint2_norm(_MIPP_ Q);

    tate(_MIPP_ P,Q,res);         /* Now invert is taken out of Tate, and the stack should be OK */

#ifndef MR_NO_STANDARD_IO
    printf( "\ne(P,rQ)= \n");
    for (i=0;i<4;i++)
        otnum(_MIPP_ res[i],stdout);
#endif

    /* all done */

#ifndef MR_STATIC
    memkill(_MIPP_ mem,8);
    ecp_memkill(_MIPP_ mem1,2);
#else
    memset(mem,0,MR_BIG_RESERVE(8));        /* clear this stack memory */
    memset(mem1,0,MR_ECP_RESERVE(2));
#endif

    mirexit(_MIPPO_ );  /* clears workspace memory */
    return 0;
}