bigint.c

rsh身份验证

		}
        Mov(&X,Sub(&X,Y));
    }
    return X;
}

unsigned long Mod32(psBigInt N, unsigned long A)
{
	int i;
	unsigned __int64 div;
    unsigned long carry=0;
    if(N->m_nLength==1)return(N->m_ulValue[0]%A);   
    for(i=N->m_nLength-1;i>=0;i--)
    {
        div=N->m_ulValue[i];
		div+=carry*0x100000000;
        carry=(unsigned long)(div%A);
    }
    return carry;
}

/****************************************************************************************
从字符串按10进制或16进制格式输入到大数
调用格式：Get(N,str,sys)
返回值：N被赋值为相应大数
sys暂时只能为10或16
****************************************************************************************/
void Get(psBigInt N, char* str, unsigned int system)
{
    int len=sizeof(str),k,i;
    Mov32(N,0);
    for(i=0;i<len;i++)
    {
       Mov(N,Mul32(N,system));
       if((str[i]>='0')&&(str[i]<='9'))k=str[i]-48;
       else if((str[i]>='A')&&(str[i]<='F'))k=str[i]-55;
       else if((str[i]>='a')&&(str[i]<='f'))k=str[i]-87;
       else k=0;
       Mov(N,Add32(N,k));
    }
}

/****************************************************************************************
将大数按10进制或16进制格式输出为字符串
调用格式：Put(N,str,sys)
返回值：无，参数str被赋值为N的sys进制字符串
sys暂时只能为10或16
****************************************************************************************/
void Put(psBigInt N, char* str, unsigned int system)
{
	int a;
    char ch;
	sBigInt X;
	char* t="0123456789ABCDEF";
    if((N->m_nLength==1)&&(N->m_ulValue[0]==0)){str="0";return;}
	str="";    
   // X = (sBigInt)malloc(sizeof(sBigInt));
    Mov(&X,*N);
    while(X.m_ulValue[X.m_nLength-1]>0)
    {
        a=Mod32(&X,system);
        ch=t[a];
        str=Insert(str,0,ch);
        Mov(&X,Div32(&X,system));
    }
}

/****************************************************************************************
求不定方程ax-by=1的最小整数解
调用方式：Euc(N,A)
返回值：X,满足：NX mod A=1
****************************************************************************************/
sBigInt Euc(psBigInt N, sBigInt A)
{
	sBigInt M,E,X,Y,I,J;
    int x,y;
/*
		M = (sBigInt)malloc(sizeof(sBigInt));
		E = (sBigInt)malloc(sizeof(sBigInt));
		X = (sBigInt)malloc(sizeof(sBigInt));
		Y = (sBigInt)malloc(sizeof(sBigInt));
		I = (sBigInt)malloc(sizeof(sBigInt));
		J = (sBigInt)malloc(sizeof(sBigInt));*/
	
	Mov(&M,A);
	Mov(&E,*N);
	Mov32(&X,0);
	Mov32(&Y,1);
	x=y=1;
	while((E.m_nLength!=1)||(E.m_ulValue[0]!=0))
	{
		Mov(&I,Div(&M,E));
		Mov(&J,Mod(&M,E));
		Mov(&M,E);
		Mov(&E,J);
		Mov(&J,Y);
		Mov(&Y,Mul(&Y,I));
		if(x==y)
		{
		    if(Cmp(&X,Y)>=0)Mov(&Y,Sub(&X,Y));
			else{Mov(&Y,Sub(&Y,X));y=0;}
		}
		else{Mov(&Y,Add(&X,Y));x=1-x;y=1-y;}
		Mov(&X,J);
	}
	if(x==0)Mov(&X,Sub(&A,X));
	return X;
}

/****************************************************************************************
求乘方的模
调用方式：RsaTrans(N,A,B)
返回值：X=N^A MOD B
****************************************************************************************/
sBigInt RsaTrans(psBigInt N, sBigInt A, sBigInt B)
{
    sBigInt X,Y;
	int i,j,k;
	unsigned n;
	unsigned long num;
	k=A.m_nLength*32-32;
	num=A.m_ulValue[A.m_nLength-1];
	while(num){num=num>>1;k++;}
/*
		X = (sBigInt)malloc(sizeof(sBigInt));
		Y = (sBigInt)malloc(sizeof(sBigInt));*/
	
	Mov(&X,*N);
	for(i=k-2;i>=0;i--)
	{
		Mov(&Y,Mul32(&X,X.m_ulValue[X.m_nLength-1]));
		Mov(&Y,Mod(&Y,B));
        for(n=1;n<X.m_nLength;n++)
		{          
			for(j=Y.m_nLength;j>0;j--)Y.m_ulValue[j]=Y.m_ulValue[j-1];
			Y.m_ulValue[0]=0;
			Y.m_nLength++;
			Mov(&Y,Add(&Y,Mul32(&X,X.m_ulValue[X.m_nLength-n-1])));
			Mov(&Y,Mod(&Y,B));
		}
		Mov(&X,Y);
		if((A.m_ulValue[i>>5]>>(i&31))&1)
		{
		    Mov(&Y,Mul32(N,X.m_ulValue[X.m_nLength-1]));
		    Mov(&Y,Mod(&Y,B));
            for(n=1;n<X.m_nLength;n++)
			{          
			    for(j=Y.m_nLength;j>0;j--)Y.m_ulValue[j]=Y.m_ulValue[j-1];
			    Y.m_ulValue[0]=0;
			    Y.m_nLength++;
			    Mov(&Y,Add(&Y,Mul32(N,X.m_ulValue[X.m_nLength-n-1])));
			    Mov(&Y,Mod(&Y,B));
			}
		    Mov(&X,Y);
		}
	}
    return X;
}

/****************************************************************************************
拉宾米勒算法测试素数
调用方式：Rab(N)
返回值：若N为素数，返回1，否则返回0
****************************************************************************************/
int Rab(psBigInt N)
{
    unsigned i,j,pass;
	sBigInt S,A,I,K;
    for(i=0;i<550;i++){if(Mod32(N,PrimeTable[i])==0)return 0;}   
/*
    	S = (sBigInt)malloc(sizeof(sBigInt));
    	A = (sBigInt)malloc(sizeof(sBigInt));
    	I = (sBigInt)malloc(sizeof(sBigInt));
    	K = (sBigInt)malloc(sizeof(sBigInt));*/
    
    Mov(&K,*N);
	K.m_ulValue[0]--;
    for(i=0;i<5;i++)
    {
        pass=0;
        Mov32(&A,rand()*rand());
		Mov(&S,K);
        while((S.m_ulValue[0]&1)==0)
		{
            for(j=0;j<S.m_nLength;j++)
			{
			    S.m_ulValue[j]=S.m_ulValue[j]>>1;
			    if(S.m_ulValue[j+1]&1)S.m_ulValue[j]=S.m_ulValue[j]|0x80000000;
			}
		    if(S.m_ulValue[S.m_nLength-1]==0)S.m_nLength--;
			Mov(&I,RsaTrans(&A,S,*N));
			if(Cmp(&I,K)==0){pass=1;break;}
		}
		if((I.m_nLength==1)&&(I.m_ulValue[0]==1))pass=1;
		if(pass==0)return 0;
	}
    return 1;
}

/****************************************************************************************
产生随机素数
调用方法：GetPrime(N,bits)
返回值：N被赋值为一个bits位（0x100000000进制长度）的素数
****************************************************************************************/
void GetPrime(psBigInt N, int bits)
{
    unsigned i;
	sBigInt S,A,I,K;
    N->m_nLength=bits;
begin:
	for(i=0;i<N->m_nLength;i++)
	{N->m_ulValue[i]=rand()*0x10000+rand();
	//printf("%d",N->m_ulValue[i]);
	}
    N->m_ulValue[0]=N->m_ulValue[0]|1;
	for(i=N->m_nLength-1;i>0;i--)
	{
		N->m_ulValue[i]=N->m_ulValue[i]<<1;
		if(N->m_ulValue[i-1]&0x80000000)N->m_ulValue[i]++;
	}
	N->m_ulValue[0]=N->m_ulValue[0]<<1;
	N->m_ulValue[0]++;
    for(i=0;i<550;i++){if(Mod32(N,PrimeTable[i])==0)goto begin;}

	
    Mov(&K,*N);
	K.m_ulValue[0]--;
    for(i=0;i<5;i++)
	{
        Mov32(&A,rand()*rand());
	    Mov(&S,Div32(&K,2));
	    Mov(&I,RsaTrans(&A,S,*N));
	    if(((I.m_nLength!=1)||(I.m_ulValue[0]!=1))&&(Cmp(&I,K)!=0))goto begin;
	}
}

/****************************************************************************************
向字符串中插入字符
调用方法：GetPrime(N,bits)
返回值：在str的iIndex位置插入字符ch
****************************************************************************************/

char* Insert(char* str, int iIndex, char ch)
{
	int len=0,i=0;
	char *p = NULL;
	len = GetStrLen(str);
	if(iIndex>len) return NULL;
	p = str;
	if((str = (char*)malloc(sizeof(char)*(len+2)))==0) return NULL; //printf("%s\naddr:%d",p,str);
	for(i=0;i<iIndex;i++)
	{
		*(str+i) = *(p+i);
	}
	*(str+i++)=ch;
	for(;i<len+2;i++)
	{
		*(str+i)=*(p+i-1);
	}
	//printf("in Insert: str:%s\n",str);
	///*该部分指向传入字符串，并非动态分配，该如何处置该字符串
	free(p);
	p=NULL;//*/
	return str;
}

char* AllocStr(char* const src)
{
	char* str = NULL;
	int i;
	for(i=0;*(src+i)!='\0';i++){}
	str = (char*)malloc((i+1)*sizeof(char));
	if(str==NULL) return NULL;
	for(i=0;*(src+i)!='\0';i++)
		*(str+i) = *(src+i);
	*(str+i) = '\0';
	return str;
}

int GetStrLen(char* str)
{
	int i=0;
	while(*(str+i) != '\0'){i++;}
	return i;
}
/****************************************************************************************
得到会话密钥
调用方法：GetSessionKey(psBigInt m, psBigInt n)
****************************************************************************************/

sBigInt GetSessionKey(psBigInt x, psBigInt p)
{
	unsigned long A;
	sBigInt p1,p2,g1,g2, gx;
	A = (unsigned long) 0x10000;
	
	BigIntInit(&p1);
	BigIntInit(&p2);
	BigIntInit(&g1);
	BigIntInit(&g2);
	Mov32(&p1, P1);
	p1 = Mul32(&p1, A);
	p1 = Mul32(&p1, A);
	p1 = Mul32(&p1, A);
	p1 = Mul32(&p1, A);
	Mov32(&p2, P2);
	p1 = Add(&p1,p2);
	Mov32(&g1, G1);
	g1 = Mul32(&g1, A);
	g1 = Mul32(&g1, A);
	g1 = Mul32(&g1, A);
	g1 = Mul32(&g1, A);
	Mov32(&g2, G2);
	g1 = Add(&g1,g2);
	Mov(p, p1);
	GetPrime(x,BIT);
	*x = Mod(x, *p);
	gx = RsaTrans(&g1,*x,*p);
	return gx;
	
}



/*int main()
{
	
	sBigInt key, x;
	unsigned int i;
	BigIntInit(&key);
	BigIntInit(&x);
	GetSessionKey(&key, &x);
	for(i=0;i<x.m_nLength;i++)
		printf("%x\n",x.m_ulValue[i]);
	printf("\n");
	for(i=0;i<key.m_nLength;i++)
		printf("%x\n",key.m_ulValue[i]);
	Sleep(100000);

	


	PwdDemo pwd;
	FILE *cfPtr;
	
	if((cfPtr=fopen("client.dat","w"))==NULL) printf("File could not be opened.\n");
	else{
		printf("Enter Server Host Name, Local Host Name, P1,P2,G1,G2.\n");
		printf("Enter EOF to end input.\n");
		printf("?");
		scanf("%s,%s,%X,%X,%X,%X",pwd.ServerHostName,
			pwd.LocalHostName,pwd.Pa,pwd.Pb,pwd.Ga,pwd.Gb);
		while(!feof(stdin)){
			fprintf(cfPtr,"%s,%s,%X,%X,%X,%X",pwd.ServerHostName,
			pwd.LocalHostName,pwd.Pa,pwd.Pb,pwd.Ga,pwd.Gb);
			printf("?");
			scanf("%s,%s,%X,%X,%X,%X",pwd.ServerHostName,
			pwd.LocalHostName,pwd.Pa,pwd.Pb,pwd.Ga,pwd.Gb);
		}
		fclose(cfPtr);
	}

	return 0;
}*/