/*******************************************************
/* DSA 加密算法原理
/* Digital Signature Algorithm (DSA)是Schnorr和ElGamal签名算法的变种，
/* 被美国NIST作为DSS(DigitalSignature Standard)。
/* 算法中应用了下述参数
/* p：L bits长的素数。L是64的倍数，范围是512到1024；
/* q：p - 1的160bits的素因子�
/* g：g = h^((p-1)/q) mod p，h满足h < p - 1, h^((p-1)/q) mod p > 1�
/* x：x < q，x为私钥 ；
/* y：y = g^x mod p ，( p, q, g, y )为公钥�
/* H( x )：One-Way Hash函数。DSS中选用SHA( Secure Hash Algorithm )。
/* p, q, g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁�
//* 签名算法
/* 1. P产生随机数k，k < q；
/* 2. P计算 r = ( g^k mod p ) mod q
/* s = ( k^(-1) (H(m) + xr)) mod q
/* 签名结果是( m, r, s )�
/* 3. 验证时计算 w = s^(-1)mod q
/* u1 = ( H( m ) * w ) mod q
/* u2 = ( r * w ) mod q
/* v = (( g^u1 * y^u2 ) mod p ) mod q
/* 若v = r，则认为签名有效�
/******************************************************/
/* 算法实现
/*密钥对生成
/* 1\找到一个160bit的素数,作为q;
/* 2\根据要求的p的位数,找一个随机偶数K,要求 K*q的位数和p的位数相同.
/* 3\取p=K*q+1,判断p是否是素数,如果不是,K=K+2,反复测试,注意保证p的位数.
/* 4\在(1,p-1)内任意取h,计算g=h^K mod p,如果g<=1,重新选h,计算g;
/* 5\在(1,q)内任取x,x作为私钥.
/* 6\计算y=g^x mod p , (p,q,g,y)作为公钥
/*签名算法
/* 1\产生随机数k,要求k<q;
/* 2\计算r=( g^k mod p ) mod q
/* 3\计算s = ( k^(-1) (H(m) + xr)) mod q ,其中H(m),是要签名信息m的摘要.
/* 4\签名结果: (m,r,s)
/*验证算法
/* 1\计算w=s^(-1) mod q
/* 2\计算u1=(H(m)*w) mod q
/* 3\计算u2=(r*w) mod q
/* 4\计算v=((g^u1*y^u2) mod p) mod q
/* 5\如果v=r,则认为签名有效.
/******************************************************/
#include "deftype.h"
#include "pubdef.h"
#include "rsa_module.h"
#include "dsa.h"
#include "BigInt.h"
/*********************************************************/
void DSA_GenerateKeys (pR_DSA_KEY pKey)
{
CBigInt Xtmp,Ktmp,Ytmp,Qtmp,Htmp;
UINT16 i;
UINT16 len;
UINT32 tmpw;
BigInitial(&Xtmp);
BigInitial(&Ktmp);
BigInitial(&Ytmp);
BigInitial(&Qtmp);
BigInitial(&Htmp);
if(pKey->bits<512) return; //P 的位数 不小于512
//获取160bit素数Q
GetPrime(&Qtmp,160);
pKey->qLen=Qtmp.m_Len;
for(i=0;i<Qtmp.m_Len;i++) pKey->primeQ[i]=Qtmp.m_Value[i];
// 选取偶数K,
len=pKey->bits-160;
Ktmp.m_Len=len/16;
for(i=0;i<Ktmp.m_Len/2;i++)
{
tmpw=rand_word();
Ktmp.m_Value[2*i]=(UINT16)tmpw;
Ktmp.m_Value[2*i+1]=(UINT16)(tmpw>>16);
}
Ktmp.m_Value[0]&=0xfffe; //偶数
//找出素数P
do
{
BigAddInt(&Ktmp,2,&Ktmp);
BigMulBig(&Qtmp,&Ktmp,&Ytmp);
BigAddInt(&Ytmp,1,&Ytmp);
}while(Labin_Miller(&Ytmp));
pKey->pLen=Ytmp.m_Len;
for(i=0;i<Ytmp.m_Len;i++) pKey->primeP[i]=Ytmp.m_Value[i];
// 取随机数X,作为私钥
Xtmp.m_Len=Qtmp.m_Len;
for(i=0;i<Xtmp.m_Len/2;i++)
{
tmpw=rand_word();
Xtmp.m_Value[2*i]=(UINT16)tmpw;
Xtmp.m_Value[2*i+1]=(UINT16)(tmpw>>16);
}
Xtmp.m_Value[Xtmp.m_Len-1]=Qtmp.m_Value[Qtmp.m_Len-1]-1; //保证X<Q
pKey->xLen=Xtmp.m_Len;
for(i=0;i<Xtmp.m_Len;i++) pKey->privateX[i]=Xtmp.m_Value[i];
// 计算G
Htmp.m_Len=Ytmp.m_Len;
for(i=0;i<Xtmp.m_Len/2;i++)
{
tmpw=rand_word();
Htmp.m_Value[2*i]=(UINT16)tmpw;
Htmp.m_Value[2*i+1]=(UINT16)(tmpw>>16);
}
Htmp.m_Value[Htmp.m_Len-1]=Ytmp.m_Value[Ytmp.m_Len-1]-1; //保证H<P-1
do
{
BigSubInt(&Htmp,1,&Htmp);
Rsa_Crypt(&Qtmp.m_Len,&Htmp.m_Len,&Ytmp.m_Len,&Ktmp.m_Len,RSA_MODE_EXP);
}while((Qtmp.m_Len==1)&&(Qtmp.m_Value[0]=1));
pKey->gLen=Qtmp.m_Len;
for(i=0;i<Qtmp.m_Len;i++) pKey->paramG[i]=Qtmp.m_Value[i];
//计算Y
Rsa_Crypt(&Htmp.m_Len,&Qtmp.m_Len,&Ytmp.m_Len,&Xtmp.m_Len,RSA_MODE_EXP);
pKey->yLen=Htmp.m_Len;
for(i=0;i<Htmp.m_Len;i++) pKey->publicY[i]=Htmp.m_Value[i];
}
/*********************************************************/
// 取报文的随机密数 k
void DSA_Package_Keys (pR_DSA_KEY pKey,UINT16 klen)
{
UINT16 i;
UINT32 tmpw;
if(klen>pKey->qLen) klen=pKey->qLen;
pKey->kLen=klen;
for(i=0;i<(klen/2+klen%2);i++)
{
tmpw=rand_word();
pKey->key[2*i]=(UINT16)tmpw;
pKey->key[2*i+1]=(UINT16)(tmpw>>16);
}
if(pKey->kLen==pKey->qLen)
{
pKey->key[pKey->kLen-1]=pKey->primeQ[pKey->qLen-1]-1; //保证 k < Q
}
}
/*********************************************************/
// DSA 签名算法
//
/*********************************************************/
void DSA_Signature(UINT8 *hm,UINT16 mlen,pR_DSA_PRIVATE_KEY pKey,UINT8 *r,UINT16 *rlen, UINT8 *s, UINT16 *slen)
{
CBigInt Ytmp,Ktmp,Mtmp,Qtmp,Xtmp,Ztmp;
UINT16 i;
BigInitial(&Ytmp);
BigInitial(&Ktmp);
BigInitial(&Mtmp);
BigInitial(&Qtmp);
BigInitial(&Xtmp);
BigInitial(&Ztmp);
//取Q
Qtmp.m_Len=pKey->qLen;
for(i=0;i<Qtmp.m_Len;i++) Qtmp.m_Value[i]=pKey->primeQ[i];
//取X
Xtmp.m_Len=pKey->xLen;
for(i=0;i<Xtmp.m_Len;i++) Xtmp.m_Value[i]=pKey->privateX[i];
//取K
Ktmp.m_Len=pKey->kLen;
for(i=0;i<Ktmp.m_Len;i++) Ktmp.m_Value[i]=pKey->key[i];
//计算出 r
Rsa_Crypt(&Xtmp.m_Len,&pKey->qLen,&pKey->pLen,&pKey->kLen,RSA_MODE_EXP);
BigModBig(&Xtmp,&Qtmp,&Ytmp);
BigIntToStr(&Ytmp,r,rlen);
//计算k的逆元
BigExtEucBig(&Qtmp,&Ktmp,&Ztmp);
//计算出 s
StrToBigInt(hm,mlen,&Mtmp);
BigMulBig(&Xtmp,&Ytmp,&Ktmp);
BigAddBig(&Ktmp,&Mtmp,&Xtmp);
BigMulBig(&Xtmp,&Ztmp,&Ytmp);
BigModBig(&Ytmp,&Qtmp,&Xtmp);
BigIntToStr(&Xtmp,s,slen);
}
/*********************************************************/
// DSA验证算法
//
/*********************************************************/
UINT8 DSA_Vertify(UINT8 *hm,UINT16 mlen,pR_DSA_PUBLIC_KEY pKey,UINT8 *r,UINT16 rlen, UINT8 *s, UINT16 slen)
{
CBigInt Ytmp,Utmp,Mtmp,Qtmp,Xtmp,Vtmp;
UINT16 i;
BigInitial(&Ytmp);
BigInitial(&Utmp);
BigInitial(&Mtmp);
BigInitial(&Qtmp);
BigInitial(&Xtmp);
BigInitial(&Vtmp);
//取Q
Qtmp.m_Len=pKey->qLen;
for(i=0;i<Qtmp.m_Len;i++) Qtmp.m_Value[i]=pKey->primeQ[i];
//求s 在q上的逆元
StrToBigInt(s,slen,&Ytmp);
BigExtEucBig(&Qtmp,&Ytmp,&Xtmp);
//取HM
StrToBigInt(hm,mlen,&Mtmp);
//计算U1
BigMulBig(&Mtmp,&Xtmp,&Ytmp);
BigModBig(&Ytmp,&Qtmp,&Utmp);
//计算U2
StrToBigInt(r,rlen,&Mtmp);
BigMulBig(&Mtmp,&Xtmp,&Ytmp);
BigModBig(&Ytmp,&Qtmp,&Vtmp);
//
Xtmp.m_Len=pKey->gLen;
for(i=0;i<Xtmp.m_Len;i++) Xtmp.m_Value[i]=pKey->paramG[i];
Rsa_Crypt(&Ytmp.m_Len,&Xtmp.m_Len,&pKey->pLen,&Utmp.m_Len,RSA_MODE_EXP);
Rsa_Crypt(&Xtmp.m_Len,&pKey->yLen,&pKey->pLen,&Vtmp.m_Len,RSA_MODE_EXP);
Rsa_Crypt(&Mtmp.m_Len,&Xtmp.m_Len,&pKey->pLen,&Ytmp.m_Len,RSA_MODE_MUL);
BigModBig(&Mtmp,&Qtmp,&Vtmp);
StrToBigInt(r,rlen,&Utmp);
if(BigCmpBig(&Vtmp,&Utmp)==0) return 1; //通过 校验
else return 0; //没通过校验
}
评论0