Elgamal
基本原理
密钥生成
- 选取一个足够大的素数 p（十进制位数不低于 160），以便于在$Z_p$上求解离散对数问题是困难的。
- 选取$Z^*_p$的生成元 g。（通常是g是p的原根）
- 选择一个私钥d，满足$ 1<d<p−1$
- 计算$y=g^dmod\ p$
- 公钥为$(p,g,y)$，私钥为$(d)$。
签名
- 随机生成k，$0<k<q$，满足$gcd(k,p-1)=1$
- 计算$r=g^kmod\ p$
- 计算$s=(H(m)+xr)k^{-1}mod\ p-1$
- 返回$(r,s)$和$H(m)$，若是明文m则存在伪造签名的可能
验签
- 验证$g^m\equiv y^rr^smod\ p$
攻击方式
验签漏洞，未校验r和s的大小
$$已知g^h\equiv y^rr^smod\ p$$
$$构造h’，(r’,s’)\ St.\ g^{h’}\equiv y^{r’}r’^{s’}mod\ p$$
$$\exists h’ = kh\ mod\ (p-1)$$
$$g^{m’}\equiv g^{km}\equiv y^{r’}r’^{s’}\equiv y^{kr}r^{ks}mod\ p$$
$$\left\{\begin{align}r’&=kr\ mod\ p-1 \\ r’&=r\ \ \ mod\ p\end{align}\right.$$
$$\Rightarrow \left\{\begin{align}r’&=crt([kr,r],[p-1,p]) \\ s’&=ks\end{align}\right.$$
DSA数字签名
基本原理
密钥生成
- 选择一个哈希函数$H(m)$，一般使用SHA1
- 确定长度$N_1$和$N_2$，使得$N_2$不大于哈希长度
- 依据$N_1$和$N_2$作为比特长度生成$p$和$q$，满足$gcd(p-1,q)=q$
- 选择满足$g^k\equiv 1\ mod\ p$的最小正整数k为q的g，即在模p的背景下，$ord(g)=q$。即g在模p的意义下，其指数次幂可以生成具有q个元素的子群。这里，我们可以通过计算$g=h^{\frac{p-1}{q}}mod\ p$来得到g，其中$1<h<p-1$.
- 选择私钥d，$0<d<q$，计算$y\equiv g^dmod\ p$。
- 公钥为$(p,q,g,y)$，私钥为$(d)$。
签名
- 随机生成k，$0<k<q$
- 计算$r=(g^kmod\ p)mod\ q$
- 计算$s=(H(m)+dr)k^{-1}mod\ q$
- 返回$(r,s)$和$H(m)$
验签
- 计算$u_1=H(m)w\ mod\ q$
- 计算$u_2=rs^{-1}\ mod\ q$
- 验证$r=(g^{u_1}y^{u_2}mod\ p)mod\ q$
攻击方式
已知k
$$d=(ks-H(m))r^{-1}mod\ q$$
复用k攻击
$$\left\{\begin{matrix}s_1=(H(m_1)+dr)k^{-1}mod\ q\\s_2=(H(m_2)+dr)k^{-1}mod\ q\end{matrix}\right.$$
$$k=(H(m_1)-H(m_2))(s_1-s_2)^{-1}mod\ q$$
线性k攻击
$$\left\{\begin{align}s_1&=(H(m_1)+d_1r)k^{-1}mod\ q \\ s_2&=(H(m_2)+d_2r)(ak+b)^{-1}mod\ q\end{align}\right.$$
$$\left\{\begin{align}ks_1r_2\equiv h_1r_2+xr_1r_2\ mod\ q \\ (ak+b)s_2r_1\equiv h_2r_1+xr_1r_2\ mod\ q\end{align}\right.$$
$$k=(h_1r_2-h_2r_1-bs_2r_1)(s_1r_2-as_2r_1)^{-1}mod\ q$$
二次k攻击
$$k_2=k_1^2，可以看作a=k，b=0$$
$$k^2s_2r_1-ks_1r_2+h_1r_2-h_2r_1=0\ mod\ q$$
用Sage求解一元二次方程在有限域上的整数解
R.<k> = PolynomialRing(Zmod(q))
f = k^2*r1*s2 - k*r2*s1 - H2*r1 + H1*r2
roots=f.roots()
print(roots)
for i in roots:
k = i[0]
d = (k*s1-H1)*pow(r1,-1,q)%q
if y == pow(g,d,p):
print(k,d)
break