数字签名

Elgamal

基本原理

密钥生成

• 选取一个足够大的素数 p（十进制位数不低于 160），以便于在$Z_p$Zp​上求解离散对数问题是困难的。
• 选取$Z^\*_p$Zp\*​的生成元 g。（通常是g是p的原根）
• 选择一个私钥d，满足$1<d<p−1$ 1<d<p−1
• 计算$y=g^dmod\ p$y=gdmod p
• 公钥为$(p,g,y)$(p,g,y)，私钥为$(d)$(d)。

签名

• 随机生成k，$0<k<p$0<k<p，满足$gcd(k,p-1)=1$gcd(k,p−1)=1
• 计算$r=g^kmod\ p$r=gkmod p
• 计算$s=(H(m)-dr)k^{-1}mod\ p-1$s=(H(m)−dr)k−1mod p−1
• 返回$(r,s)$(r,s)和$H(m)$H(m)，若是明文m则存在伪造签名的可能

验签

• 验证$g^{H(m)}\equiv y^rr^smod\ p$gH(m)≡yrrsmod p

攻击方式

验签漏洞，未校验r和s的大小

[0xGame 2024]Elgamal

$已知g^h\equiv y^rr^smod\ p$已知gh≡yrrsmod p

$构造h’，(r’,s’)\ St.\ g^{h’}\equiv y^{r’}r’^{s’}mod\ p$构造h’，(r’,s’) St. gh’≡yr’r’s’mod p

$\exists h’ = kh\ mod\ (p-1)$∃h’=kh mod (p−1)

$g^{m’}\equiv g^{km}\equiv y^{r’}r’^{s’}\equiv y^{kr}r^{ks}mod\ p$gm’≡gkm≡yr’r’s’≡ykrrksmod 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)$H(m)，一般使用SHA1
• 确定长度$N_1$N1​和$N_2$N2​，使得$N_2$N2​不大于哈希长度
• 依据$N_1$N1​和$N_2$N2​作为比特长度生成$p$p和$q$q，满足$gcd(p-1,q)=q$gcd(p−1,q)=q
• 选择满足$g^k\equiv 1\ mod\ p$gk≡1 mod p的最小正整数k为q的g，即在模p的背景下，$ord(g)=q$ord(g)=q。即g在模p的意义下，其指数次幂可以生成具有q个元素的子群。这里，我们可以通过计算$g=h^{\frac{p-1}{q}}mod\ p$g=hqp−1​mod p来得到g，其中$1<h<p-1$1<h<p−1.
• 选择私钥d，$0<d<q$0<d<q，计算$y\equiv g^dmod\ p$y≡gdmod p。
• 公钥为$(p,q,g,y)$(p,q,g,y)，私钥为$(d)$(d)。

签名

• 随机生成k，$0<k<q$0<k<q
• 计算$r=(g^kmod\ p)mod\ q$r=(gkmod p)mod q
• 计算$s=(H(m)+dr)k^{-1}mod\ q$s=(H(m)+dr)k−1mod q
• 返回$(r,s)$(r,s)和$H(m)$H(m)

验签

• 计算$u_1=H(m)s^{-1}\ mod\ q$u1​=H(m)s−1 mod q
• 计算$u_2=rs^{-1}\ mod\ q$u2​=rs−1 mod q
• 验证$r=(g^{u_1}y^{u_2}mod\ p)mod\ q$r=(gu1​yu2​mod p)mod q

攻击方式

已知k

$d=(ks-H(m))r^{-1}mod\ q$d=(ks−H(m))r−1mod 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.${s1​=(H(m1​)+dr)k−1mod qs2​=(H(m2​)+dr)k−1mod q​

$k=(H(m_1)-H(m_2))(s_1-s_2)^{-1}mod\ q$k=(H(m1​)−H(m2​))(s1​−s2​)−1mod 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=(h1​r2​−h2​r1​+bs2​r1​)(s1​r2​−as2​r1​)−1mod q

二次k攻击

[国城杯 2024]Ez_sign

$k_2=k_1^2，可以看作a=k，b=0$k2​=k12​，可以看作a=k，b=0

$k^2s_2r_1-ks_1r_2+h_1r_2-h_2r_1=0\ mod\ q$k2s2​r1​−ks1​r2​+h1​r2​−h2​r1​=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