实验三DSA数字签名算法

实验三实验三 DSA 数字签名算法数字签名算法 姓姓 名 名 学学 号号 学学 院 院 信息工程学院信息工程学院 指导老师 指导老师 郑明辉郑明辉 1 DSA 算法原理算法原理 数字签名是数据在公开行信道中传输的安全保障 能够实现数据的公开 公正 不可抵赖等特点的方法 只能公开的密钥 密码签名算法 国际供认 的公开密钥签字算法主要有 RSA 算法 ElGAMAL 算法或者其变形的签名算 法 DSA Digite Signature Arithmotic 是 Schnore 和 ElGamal 算法的变型 美国国家标准技术研究所 NIST 1994 年 5 月 19 日公布了数字签名标准 的 DSS 标准采用的算法便是 DSA 密钥长度为 512 1024 位 密钥长度愈长 签名速度愈慢 制约运算速度的只要因素是大数的模指数运算 2 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 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 则认为签名有效 DSA 是基于整数有限域离散对数难题的 其安全性与 RSA 相比差不多 DSA 的一个重要特点是两个素数公开 这样 当使用别人的 p 和 q 时 即使 不知道私钥 你也能确认它们是否是随机产生的 还是作了手脚 RSA 算法 却做不到 3 源码描述源码描述 include stdafx h include include include BigInt h include sha1 h include time h int shas1 const unsigned int x unsigned char digest 20 SHA1 CTX context unsigned char buffer 16384 digest 20 FILE file SHA1Init SHA1Update SHA1Final digest return 0 CBigInt sha CBigInt y SHA1 CTX context CBigInt X unsigned char buffer 16384 digest 20 CString str char t 0123456789ABCDEF if y m nLength 1 X Mov 0 return X str int a char ch 0 str Insert 0 ch X Mov y while X m ulValue X m nLength 1 0 a X Mod 16 ch t a str Insert 0 ch X Mov X Div 16 int i 0 while str i 0 i for a i i 0 i a i buffer i str i for i a i 64 i buffer i 0 SHA1Init SHA1Update SHA1Final digest int len str GetLength k X Mov 0 for i 0 i 0 else k 0 X Mov X Add k return X CBigInt makerandnumber unsigned int len srand time NULL CBigInt X X m nLength len 31 32 X Mov 0 for unsigned int j 0 j0 if y 2 0 q Mov q Mul q y 2 else p Mov p Mul q y 1 return p CBigInt pow3 CBigInt x CBigInt y CBigInt m CBigInt p t p Mov 1 t Mov 0 while y Cmp t 0 if y m ulValue 0 x Mov x Mod m x Mov x Div 2 else p Mov p Mul x p Mov p Mod m