第十六个知识点：描述DSA,Schnorr,RSA-FDH的密钥生成,签名和验证
这是密码学52件事系列中第16篇,这周我们描述关于DSA,Schnorr和RSA-FDH的密钥生成,签名和验证.
1.DSA
数字签名场景(DSA),也叫数字签名标准(the Digital Signature Standard,DSS),在1991年[1]被NIST(国际标准和技术机构)提出.DSA的安全是基于计算离散对数的困难性上.但是却没有一个基于一个标准困难性假设的证明,即便在随机访问模型里.
域参数生成
1.选择一个素数\(p\),其中\(2^{L-1}<p<2^L\),同时\(L\)是64的倍数, \(512 \le L \le 1024\)
2.选择一个\(p-1\)的质因数\(q\),其中\(2^{159}<q<2^{160}\)
3.计算\(q\)阶子群的生成函数\(g\):随机选择一个整数\(r\),其中\(1<r<p-1\),\(g=r^{(p-1)/q} \mod p\) and \(g \ne 1\).
密钥生成
1.选择一个随机整数\(x\),其中\(0<x<q\)
2.计算\(y=g^x \mod p\)
然后公钥是\(y\),私钥是\(x\).
签名
1.选择一个随机的整数\(k\),其中\(0<k<p\)
2.计算\(r=(g^k \mod p ) \mod q\)
3.计算\(s = (h(m)+x*r)*k^{-1} \mod q\),其中\(h(m)\)是\(m\)在使用SHA-1下的函数
m的签名对是\((r,s)\)
验证
1.计算\(u_1 = h(m)*s^{-1} \mod q\)
2.计算\(u_2 = r*s^{-1} \mod q\)
3.计算\(v = (g^{u_1}*g^{u_2}) \mod q\)
4.如果\(v=r\),输出1,否则输出0
正确性
如果\((r,s)\)是一个\(m\)的合法签名,那么我们有
2.Schnorr
Schnorr是一个重要的基于DLP问题的签名场景.它工作在任何素数域.它的安全性在DL假设和随机访问模型下是被证明了的.
域参数生成
1.选择一个素数\(p\)
2.选择一个和\(p-1\)互质的\(q\)
3.选择\(q\)阶子群的生成器\(g\)
密钥生成
1.随机选择一个整数\(x\),其中\(0<x<q\)
2.计算\(y = g^x \mod p\)
公钥就是\(y\),私钥就是\(x\).
签名
1.选择一个随机整数\(k\),其中\(0<k<q\)
2.计算\(a = g^k \mod p\)
3.计算\(r = h(m||a)\),其中\(m\)是被签名的消息,同时\(h:\{0,1\}^* \rightarrow Z_q\).是一个哈希函数.
4.计算\(s = (k+r*x) \mod q\)
签名就是\((r,s)\)
正确性
如果\((r,s)\)是一个正确的签名在\(m\)上,那么我们有
(注意:schnorr协议是一个交互式的协议,这里应该说的不是最初的想法)
3.RSA-FDH
\(RSA-FDH\)(full domain hash)是一种Bellare和Rogaway in [3]中介绍的基于RSA的签名.遵循先hash后签名的范例.它利用哈希函数(输出正好等于RSA的模数),为普通的RSA签名方案生成输出.它保护了textbook RSA签名的代数攻击方案.并且对任意长度的消息都能签名.但是实际中很难创建这样的哈希函数.RSA-FDH可以在随机的oracle模型中证明EU-CMA安全(存在不可为造性).
密钥生成
1.选择两个大素数\(p\)和\(q\)
2.计算\(N = p*q\)
3.选择一个随机整数\(e\),其中\(1<e<\phi(N)\).使得\(gcd(e,\phi(N))=1\).
4.计算一个整数d,使得\(1<d<\phi(N)\),\(e*d=1\mod\phi(N)\)
公钥是\((N,e)\),私钥是\((d,p,q)\)
签名
计算\(s = h(m)^d\mod N\),其中\(m\)是将要被签名,同时\(h:\{0,1\}^* \rightarrow Z_N\)是一个hash函数.
\(m\)的签名就是\(s\).
验证
如果\(s^e=h(m)\),输出\(1\).否则输出0.
正确性验证
Reference
[1] http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf