SeanBlog

文章

数字签名

CTF 7 分钟 · 1558 字
Crypto数字签名

Elgamal

基本原理

密钥生成

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

签名

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

验签

  • 验证gH(m)equivyrrsmodpg^{H(m)}\\equiv y^rr^smod\\ pgH(m)equivyrrsmodp

攻击方式

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

[0xGame 2024]Elgamal

已知ghequivyrrsmodp已知g^h\\equiv y^rr^smod\\ p已知ghequivyrrsmodp

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

existsh’=khmod(p−1)\\exists h’ = kh\\ mod\\ (p-1)existsh’=khmod(p−1)

gm’equivgkmequivyr’r’s’equivykrrksmodpg^{m’}\\equiv g^{km}\\equiv y^{r’}r’^{s’}\\equiv y^{kr}r^{ks}mod\\ pgm’equivgkmequivyr’r’s’equivykrrksmodp

\\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)H(m)，一般使用SHA1
  • 确定长度N_1N\_1N_1和N_2N\_2N_2，使得N_2N\_2N_2不大于哈希长度
  • 依据N_1N\_1N_1和N_2N\_2N_2作为比特长度生成ppp和qqq，满足gcd(p−1,q)=qgcd(p-1,q)=qgcd(p−1,q)=q
  • 选择满足gkequiv1modpg^k\\equiv 1\\ mod\\ pgkequiv1modp的最小正整数k为q的g，即在模p的背景下，ord(g)=qord(g)=qord(g)=q。即g在模p的意义下，其指数次幂可以生成具有q个元素的子群。这里，我们可以通过计算g=hfracp−1qmodpg=h^{\\frac{p-1}{q}}mod\\ pg=hfracp−1qmodp来得到g，其中1<h<p−11<h<p-11<h<p−1.
  • 选择私钥d，0<d<q0<d<q0<d<q，计算yequivgdmodpy\\equiv g^dmod\\ pyequivgdmodp。
  • 公钥为(p,q,g,y)(p,q,g,y)(p,q,g,y)，私钥为(d)(d)(d)。

签名

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

验签

  • 计算u_1=H(m)s−1modqu\_1=H(m)s^{-1}\\ mod\\ qu_1=H(m)s−1modq
  • 计算u_2=rs−1modqu\_2=rs^{-1}\\ mod\\ qu_2=rs−1modq
  • 验证r=(gu_1yu_2modp)modqr=(g^{u\_1}y^{u\_2}mod\\ p)mod\\ qr=(gu_1yu_2modp)modq

攻击方式

已知k

d=(ks−H(m))r−1modqd=(ks-H(m))r^{-1}mod\\ qd=(ks−H(m))r−1modq

复用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)−1modqk=(H(m\_1)-H(m\_2))(s\_1-s\_2)^{-1}mod\\ qk=(H(m_1)−H(m_2))(s_1−s_2)−1modq

线性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)−1modqk=(h\_1r\_2-h\_2r\_1+bs\_2r\_1)(s\_1r\_2-as\_2r\_1)^{-1}mod\\ qk=(h_1r_2−h_2r_1+bs_2r_1)(s_1r_2−as_2r_1)−1modq

二次k攻击

[国城杯 2024]Ez_sign

k_2=k_12，可以看作a=k，b=0k\_2=k\_1^2，可以看作a=k，b=0k_2=k_12，可以看作a=k，b=0

k2s_2r_1−ks_1r_2+h_1r_2−h_2r_1=0modqk^2s\_2r\_1-ks\_1r\_2+h\_1r\_2-h\_2r\_1=0\\ mod\\ qk2s_2r_1−ks_1r_2+h_1r_2−h_2r_1=0modq

用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

0 条评论