dsa2.c

这个是数字签名的DSA 算法 !是借用别人的!为了大家的学习和提高!

void ran_num(int bits, unsigned long *rnum)

{
	LINT con;
	int i,bk,bk1,r;
	unsigned long *rnump,mask,mask1=0x00000000;
	div_t x;
	rnump=rnum;
	for(i=0;i<=LENGTH;i++) con[i]=0x0;
	rng(con);
	x=div(bits,32);
	bk=x.quot;
	r=x.rem;
	*rnump=bk;
	rnum++;
	for(i=1;i<=bk;i++,rnum++) *rnum=con[i];
	if(r!=0)
	{
		bk1=bk+1;
		*rnump=bk1;
		mask=RMASK;
		for(i=1;i<=r;i++)
		{
			mask1=(mask1|mask);
			mask<<=1;
		}
		*rnum=(con[bk1]&mask1);
	}
}

void big_num(unsigned lbit, unsigned long *rnum)

{
	LINT num1;
	int bit1,bit2,i;
	for(i=0;i<=LENGTH;i++)
	{
		rnum[i]=0x0;
		num1[i]=0x0;
	}
	if(lbit<=320)
	       ran_num(lbit,rnum);
	else
	{
		bit1=320;
		bit2=lbit-320;
		ran_num(bit1,rnum);
		ran_num(bit2,num1);
		*rnum=*rnum+*num1;
		for(i=1;i<=(*num1);i++)
			*(rnum+i+10)=*(num1+i);
	}
}

void snrprime(unsigned int splen,unsigned long *spn,unsigned int sqlen,unsigned long *sqn)

{
	LINT pt,ps,pr,prs,n_tmp;
	unsigned long *psp,preg;
	int spcnt,spget,tplen,tmp1,tmp2;
	for(spcnt=2;spcnt<=LENGTH;spcnt++)
		n_tmp[spcnt]=0x0;
	n_tmp[0]=1;
	n_tmp[1]=1;
	tplen=(int)(log((double)splen)+4);
	level_prime(sqlen,pr);
	for(tmp1=0;tmp1<=LENGTH;tmp1++)
		sqn[tmp1]=pr[tmp1];
	spcnt=splen-tplen-sqlen;
	level_prime(spcnt,ps);
	inverse(ps,pr,pt);
	shiftleft(pt);
	multiply(ps,pt,pt);
	sub(pt,n_tmp);
	multiply(pr,ps,prs);
	shiftleft(prs);
	for(spcnt=1;spcnt<=LENGTH;spcnt++)
	 pr[spcnt]=0;
	tmp1=splen%32;
	if(tmp1==0)
	{
		pr[0]=splen/32;
		tmp2=pr[0];
		pr[tmp2]=LMASK;
	}
	else
	{
		pr[0]=splen/32+1;
		tmp2=pr[0];
		pr[tmp2]=RMASK;
		pr[tmp2]<<=(tmp1-1);
	}
	division(pr,prs,ps,n_tmp);
	multiply(ps,prs,pr);
	if(compare(pt,n_tmp)<0)
	{
		add(pt,pr);
		add(pt,prs);
	}
	else add(pt,pr);
	spcnt=0;
	spget=0;
	while(spget==0)
	{
		spget=primetest(pt);
		spcnt++;
		if(spget==0) add(pt,prs);
	}
	count=spcnt;
	psp=spn;
	for(spcnt=0;spcnt<=LENGTH;spcnt++,psp++)
		*psp=pt[spcnt];
}

void p_root(unsigned long *spn,unsigned long *sqn,unsigned long *pr)

{
	LINT ptmp,atmp,btmp,dq,dr,da;
	int tmp;
	for(tmp=0;tmp<=LENGTH;tmp++)
	{
		ptmp[tmp]=spn[tmp];
		atmp[tmp]=0x0;
		btmp[tmp]=0x0;
	}
	atmp[0]=1;
	atmp[1]=1;
	btmp[0]=1;
	btmp[1]=2;
	sub(ptmp,atmp);
	do
	{
		modexp(btmp,sqn,spn,da);
		if(compare(da,atmp)==0)
		{
			for(tmp=0;tmp<=LENGTH;tmp++)
				pr[tmp]=btmp[tmp];
			break;
		}
		division(ptmp,sqn,dq,dr);
		modexp(btmp,dq,spn,da);
		if(compare(da,atmp)!=0)
		{
			for(tmp=0;tmp<=LENGTH;tmp++)
				pr[tmp]=da[tmp];
			break;
		}
		add(btmp,atmp);
	}while(1);
}

void secretkey( unsigned srlen,unsigned long *qt,unsigned long *ut)

 {
	 do
	 {
		 big_num(srlen,ut);
		 mod(ut,qt);
	 }while(*ut==0);
 }

append(unsigned long *buffer,int ret)

{
    unsigned long rp;
	int i,count=0;
	while(ret>=4)
	{
		ret-=4;
		count++;
	}
	rp=(*(buffer+count));
	switch(ret)
	{
	  case 0:
		   rp=0x00000001;
		   break;
	  case 1:
		   rp=(rp&RIGHT)+0x00000100;
		   break;
	  case 2:
		  rp=(rp&MID)+0x00010000;
		  break;
	  case 3:
		  rp=(rp&LEFT)+0x01000000;
		  break;
	}
	*(buffer+count)=rp;
	for(i=count+1;i<16;i++)
		*(buffer+i)=(*(buffer+i)&CLEAR);
}




reg(unsigned long *buffer,unsigned long *p,unsigned long *q,unsigned long *s,unsigned long *t)

{
	unsigned long word[4],x[16],tw;
	int ip[3][16]=
	{
		{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15},
		{0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15},
		{0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15}
	};
	int sp[3][16]=
	{
		{3,7,11,19,3,7,11,19,3,7,11,19,3,7,11,19},
		{3,5,9,13,3,5,9,13,3,5,9,13,3,5,9,13},
		{3,9,11,15,3,9,11,15,3,9,11,15,3,9,11,15}
	};
	int i,j,k;
	for(i=0;i<16;i++)
	x[i]=*(buffer+i);
	word[0]=*p;
	word[1]=*q;
	word[2]=*s;
	word[3]=*t;
	for(i=0;i<16;i++)
	{
		k=ip[0][i];
		round1(word,x[k],sp[0][i]);
		tw=word[3];
		for(j=3;j>=1;j--)
			word[j]=word[j-1];
		word[0]=tw;
	}
    for(i=0;i<16;i++)
	{
		k=ip[1][i];
		round2(word,x[k],sp[1][i]);
		tw=word[3];
		for(j=3;j>=1;j--)
			word[j]=word[j-1];
		word[0]=tw;
	}
	for(i=0;i<16;i++)
	{
		k=ip[2][i];
		round3(word,x[k],sp[2][i]);
		tw=word[3];
		for(j=3;j>=1;j--)
			word[j]=word[j-1];
		word[0]=tw;
	}
	*p=word[0]+*p;
	*q=word[1]+*q;
	*s=word[2]+*s;
	*t=word[3]+*t;
}






round1(unsigned long *word,unsigned long v,int s)

{
	unsigned long f,r;
	f=(word[1]&word[2])|((~word[1])&word[3]);
	word[0]=(word[0]+f+v);
	r=word[0];
	word[0]=word[0]<<s;
	r=r>>(32-s);
	word[0]=word[0]+r;
}



round2(unsigned long *word,unsigned long v,int s)

{
	unsigned long g,r;
	g=(word[1]&word[2])|(word[1]&word[3])|(word[2]&word[3]);
	word[0]=(word[0]+g+v+0x5a827999);
	r=word[0];
	word[0]=word[0]<<s;
	r=r>>(32-s);
	word[0]=word[0]+r;
}


round3(unsigned long *word,unsigned long v,int s)

{
	unsigned long h,r;
	h=word[1]^word[2]^word[3];
	word[0]=(word[0]+h+v+0x6ed9eba1);
	r=word[0];
	word[0]=word[0]<<s;
	r=r>>(32-s);
	word[0]=word[0]+r;
}




void hashfun( unsigned long carry, unsigned long length, unsigned long *hafn)

{
	unsigned long addr[17],*buffer,a,b,c,d;
	int i,j,ret;
	a=0x012345467;
	b=0x89abcdef;
	c=0xfedcba98;
	d=0x76543210;
	buffer=addr;
	do
	{
		ret=fread(buffer,sizeof(char),BLOCK,fp);
		if(ret!=BLOCK)
		{
			if(ret<=56)
			{
				append(buffer,ret);
				*(buffer+14)=carry;
				*(buffer+15)=length;
				break;
			}
			else
			{
				append(buffer,ret);
				reg(buffer,&a,&b,&c,&d);
				for(i=0;i<=13;i++)
					*(buffer+i)=0;
				*(buffer+14)=carry;
				*(buffer+15)=length;
				break;
			}
		}
		reg(buffer,&a,&b,&c,&d);
	}while(1);
	reg(buffer,&a,&b,&c,&d);
	for(i=0;i<=LENGTH;i++) hafn[i]=0x0;
	hafn[4]=d;
	hafn[3]=c;
	hafn[2]=b;
	hafn[1]=a;
	hafn[0]=4;
}

void dss_keys(void)
{
	char uans,fn1[20],fn2[20];
	int utmp,ttmp;
	LINT qtmp,rtmp;
	do
	{
		printf("\n Please input your name(1-8 characters&no space): \n");
		scanf("%s",uname);
		printf("\n  Now,login name:%s \n",uname);
		printf("\n Are you sure (Y/N)?   Ans: ");
		uans=getch();
		clrscr();
		if((uans=='Q')||(uans=='q'))
			exit(1);
	}while((uans!='y')&&(uans!='Y'));
	strcpy(fn1,uname);
	strcat(fn1,".pk2");
        printf("\n Now genterate the system keys ,wait for...! \n");
        fp1=fopen(fn1,"wb");
	fp2=fopen(fn2,"wb");
	if(fp1==NULL)
	{
		printf("\n \n  There are some error in disk writing.");
		printf("\n Press any key to exit this system. \n");
		getch();
		exit(1);
	}
	time1=clock();
	utmp=512;
	ttmp=80;
	snrprime(utmp,up,ttmp,uq);
	printf("q=");
	hexout(uq);
	printf("p=");
	hexout(up);
	time2=clock();
	printf("\n The time was: %fminutes. \n",(time2-time1)/(60*CLK_TCK));
	p_root(up,uq,ua);
	time2=clock();
	printf("g=");
	hexout(ua);
	printf("\n ................................................ \n");
	printf("\n The time was: %fminutes. \n",(time2-time1)/(60*CLK_TCK));
        for(utmp=0;utmp<=LENGTH;utmp++)
		 fprintf(fp1,"%lx %lx %lx ",up[utmp],uq[utmp],ua[utmp]);
	printf("\n \n Press any key to exit the main menu!!!");
	fclose(fp1);
}




void dss_sign(void)
{
	LINT zrand,inv_zrand,sh;
	char ch,fn[20],fn1[20];
	unsigned long carry,len;
	int utmp,ttmp;
	printf("\n Please input KAC's login name:");
	scanf("%s",uname);
	strcpy(fn1,uname);
	strcat(fn1,".pk2");
	fp1=fopen(fn1,"rb");
	if((fp1==NULL))
	{
		printf("\n Error login name.Press any key ti exit this system.");
		fclose(fp1);
		return;
	}
	for(utmp=0;utmp<=LENGTH;utmp++)
		fscanf(fp1,"%lx %lx %lx ",up+utmp,uq+utmp,ua+utmp);
	fclose(fp1);
	printf("\n Press any key to continue!! \n");
	ch=getch();
	if(ch!=0x1b)
	{
		printf("p="); hexout(up);
	  	printf("q="); hexout(uq);
		printf("g="); hexout(ua);
	}
	printf("Please input signer's login name(1-8characters& no space):");
	scanf("%s",sname);
	getchar();
	strcpy(fn,sname);
	strcat(fn,".sp2");
	if((fp=fopen(fn,"rb"))==NULL)
	{
		fclose(fp);
		printf(" \n Now generating signer's keys .Waiting about thirty !!!");
		fp=fopen(fn,"wb");
		ttmp=160;
		secretkey(ttmp,uq,us);
		modexp(ua,us,up,ub);
		fprintf(fp,"%lx %lx",us[0],ub[0]);
		for(utmp=1;utmp<=LENGTH;utmp++)
		{
			if(utmp<=us[0])
				*(us+utmp)=*(us+utmp)+4321;
			else
				*(us+utmp)=0x0;
			fprintf(fp1,"%lx %lx",us[utmp],ub[utmp]);
		}
	}
	fscanf(fp,"%lx %lx ",us,ub);
	for(utmp=1;utmp<=LENGTH;utmp++)
	{
		fprintf(fp,"%lx %lx ",us+utmp,ub+utmp);
		if(utmp<=us[0])
			*(us+utmp)=*(us+utmp)-4321;
	}
	fclose(fp);
	printf("\n The signer's public key(y)&secret key(x):");
	printf("\n y=");
	hexout(ub);
	printf("\n x=");
	hexout(us);
	printf("Please input the source data filename(message):");
	scanf("%s",fn1);
	printf("\n");
	fp1=fopen(fn1,"rb");
	if(fp1==NULL)
	{
		printf("\n Error data filename's format.Press any key to exit!! \n");
		fclose(fp1);
		return;
	}
	carry=0x0;
	len=0x0;
	while(getc(fp1)!=EOF)
	{
		if(len==FULS)
			carry++;
		len+=8;
	}
	fclose(fp1);
	time1=clock();
	fp=fopen(fn1,"rb");
	hashfun(carry,len,sh);
	fclose(fp);
	ttmp=80;
	secretkey(ttmp,uq,zrand);
	modexp(ua,zrand,up,ue);
	mod(ue,uq);
	modmul(us,ue,uq,uy);
	add(uy,sh);
	inverse(zrand,uq,inv_zrand);
	modmul(uy,inv_zrand,uq,uy);
	time2=clock();
	printf("The signer's signature(r,s): \n");
	printf("\n r=");
	hexout(ue);
	printf("\n s=");
	hexout(uy);
	printf("\n ..............................................................\n");
	printf("\n The time  was %f seconds.",(time2-time1)/(CLK_TCK));
	strcpy(fn,sname);
	strcat(fn,".sg2");
	fp=fopen(fn,"wb");
	for(utmp=0;utmp<=LENGTH;utmp++)
	  fprintf(fp,"%lx %lx %lx ",ub[utmp],ue[utmp],uy[utmp]);
	fclose(fp);
	printf("\n\n Press any key to exit the main menu!!!");
}




void dss_ver(void)
{
	LINT uw,u1,u2,hf,uv;
	unsigned long carry,len;
	char ch,fn1[20];
	int utmp;
	printf("\n\n Please input KAC's login name:");
	scanf("%s",uname);
	strcpy(fn1,uname);
	strcat(fn1,".pk2");
	fp1=fopen(fn1,"rb");
	if(fp1==NULL)
	{
		printf("\n Error login name.Press any key to exit this system.");
		fclose(fp1);
		return;
	}
	for(utmp=0;utmp<=LENGTH;utmp++)
	 fscanf(fp1,"%lx %lx %lx ",up+utmp,uq+utmp,ua+utmp);
	fclose(fp1);
	printf("\n Please input the signer's name:");
	scanf("%s",sname);
	strcpy(fn1,sname);
	strcat(fn1,".sg2");
	fp1=fopen(fn1,"rb");
	if(fp1==NULL)
	{
          printf("\n The signer's login name does not exit.");
		  printf("\n Press any key to exit this system.");
		  fclose(fp1);
		  return;
	}
	for(utmp=0;utmp<=LENGTH;utmp++)
	fscanf(fp1,"%lx %lx %lx ",ub+utmp,ue+utmp,uy+utmp);
	fclose(fp1);
	printf("\n Press any key to continue!!\n");
	ch=getch();
	if(ch!=0x1b)
	{
		printf("\n The KAC's public key. \n");
		printf("p=");hexout(up);
		printf("q=");hexout(uq);
		printf("g=");hexout(ua);
		printf("\n The signer's public information(b)&signature(e,y). \n");
		printf("y=");hexout(ub);
		printf("r=");hexout(ue);
		printf("s=");hexout(uy);
		printf("\n Press any key to continue!!\n");
		getch();
		clrscr();
	}
	if((compare(ue,uq)!=-1)||(compare(uy,uq)!=-1))
	{
		printf("\n .......................................................\n");
		printf("\n The signature is erroneous!!!");
		printf("\n Press any key to exit the main menu.");
	}
	else
	{
		printf("\n Please input the source data filename(message):");
		scanf("%s",fn1);
		printf("\n");
		if((fp1=fopen(fn1,"rb"))==NULL)
		{
			printf("\n Error data filename's format.");
			printf("\n Press any key to exit!!! \n");
			fclose(fp1);
			return;
		}
		printf("\n Now verifying the signer's signature(message). waiting for....!!!");
		time1=clock();
		carry=0x0;
		len=0x0;
		while(getc(fp1)!=EOF)
		{
			if(len==FULS) carry++;
			len+=8;
		}
		fclose(fp1);
		fp=fopen(fn1,"rb");
		hashfun(carry,len,hf);
		fclose(fp);
		inverse(uy,uq,uw);
		modmul(hf,uw,uq,u1);
		modmul(ue,uw,uq,u2);
		modexp(ua,u1,up,u1);
		modexp(ub,u2,up,u2);
		modmul(u1,u2,up,uv);
		mod(uv,uq);
		time2=clock();
                printf("\n w=");hexout(uw);
                printf("\n u1=");hexout(u1);
                printf("\n u2=");hexout(u2);
                printf("\n v=");hexout(uv);
		printf("\n r=");hexout(ue);
		printf("\n..................................................................\n");
		if(compare(uv,ue)!=0)
			printf("\n The signature is erroneous!!!");
		else
			printf("\n The signature is correct!!");
		printf("\n The time was %fseconds.",(time2-time1)/CLK_TCK);
		printf("\n Press any key to exit the main menu!!!");
	}
}





main()
{
	int cc,ans;
	union
	{
		int i;
		char ch[2];
	}pans;
	window(1,1,80,25);
	do
	{
		clrscr();
		textcolor(YELLOW);
		textbackground(BLUE);
		gotoxy(10,4);
		cprintf("                                                     ");
		gotoxy(10,5);
		cprintf("       Welcome to Enter the Asdzyw-DSS Scheme        ");
		gotoxy(10,6);
	        cprintf("       for Identification & Signature                ");
		gotoxy(10,7);
	        cprintf("                                                     ");
		textcolor(LIGHTCYAN);
		textbackground(BLACK);
		gotoxy(20,9);
		cprintf("Choose one of the following functions");
		ans='a';
		pans.i=0;
		while(pans.i!=0x1c0d)
		{
			for(cc='a';cc<='d';cc++)
			{
				if(cc!=ans)
				{
					textbackground(BLACK);
					textcolor(LIGHTGRAY);
				}
				else
				{
					textbackground(WHITE);
					textcolor(RED);
				}
              switch(cc)
			  {
			    case'a':gotoxy(18,11);
				             cprintf(" a: Key generation     ;");break;
			    case'b':gotoxy(18,13);
				             cprintf(" b: Signature          ;");break;
			    case'c':gotoxy(18,15);
				             cprintf(" c: Verification       ;");break;
			    case'd':gotoxy(18,17);
				             cprintf(" d: Quit & Exit        ;");break;
			  }
			  gotoxy(57,9);
			}
                while(!bioskey(1));
			pans.i=bioskey(0);
			/*if((pans.ch[1]==0x48)&&(ans>'a')) ans--;
			  if((pans.ch[1]==0x50)&&(ans<'d')) ans++;*/
			if((pans.ch[0]>='a')&&(pans.ch[0]<='d')) ans=pans.ch[0];
		}
		textbackground(BLACK);
		textcolor(LIGHTGRAY);
		clrscr();
		switch(ans)
		{
		    case'a':textcolor(YELLOW);
				    textbackground(BLUE);
					gotoxy(15,2);
					cprintf("-----<GENERATE KEYS(Asdzyw-DSS)>-----");
					textcolor(LIGHTGRAY);
					textbackground(BLACK);
					gotoxy(1,5);
					dss_keys();
					getch();
					break;
            case'b':textcolor(YELLOW);
				    textbackground(BLUE);
					gotoxy(15,2);
					cprintf("-----<SIGNATURE(Asdzyw-DSS)>-----");
					textcolor(LIGHTGRAY);
					textbackground(BLACK);
					gotoxy(1,5);
					dss_sign();
					getch();
					break;
			case'c':textcolor(YELLOW);
				    textbackground(BLUE);
					gotoxy(15,2);
					cprintf("-----<VERIFICATION(Asdzyw-DSS)>-----");
					textcolor(LIGHTGRAY);
					textbackground(BLACK);
					gotoxy(1,5);
					dss_ver();
					getch();
					break;
		}
	}
	while(ans!='d');
}