DSA笔记
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
基本原理
密钥生成
- 选择一个合适的哈希函数目前一般选择 SHA1当前也可以选择强度更高的哈希函数 H。
- 选择密钥的长度 L 和 N这两个值决定了签名的安全程度。在最初的 DSS Digital Signature Standard 中建议 L 必须为 64 的倍数并且 512 ≤ L ≤ 1024 512≤L≤1024 512≤L≤1024 当然也可以更大。N 大小必须不大于哈希函数 H 输出的长度。FIPS 186-3 给出了一些建议的 L 和 N 的取值例子(1024, 160) (2048, 224) (2048, 256)以及 (3,072, 256)。
- 选择 N 比特的素数 q。
- 选择 L 比特的素数 p使得 p-1 是 q 的倍数。
- 选择满足 g k ≡ 1 m o d p g^k≡1\mod p gk≡1modp 的最小正整数 k 为 q 的 g即在模 p 的背景下ord(g)=q 的 g。即 g 在模 p 的意义下其指数次幂可以生成具有 q 个元素的子群。这里我们可以通过计算 g = h p − 1 q m o d p g=h^{\frac{p−1}{q}}\mod p g=hqp−1modp 来得到 g其中 1<h<p−1 。
- 选择私钥 x 0<x<q 计算
y
≡
g
x
m
o
d
p
y≡g^x\mod p
y≡gxmodp ,公钥为 (p,q,g,y)私钥为 (x)。
签名
签名步骤如下 - 选择随机整数数 k 作为临时密钥 0<k<q 。
- 计算 r ≡ ( g k m o d p ) m o d q r ≡ (g^k\mod p)\mod q r≡(gkmodp)modq
- 计算
s
≡
(
H
(
m
)
+
x
r
)
k
−
1
m
o
d
q
s≡(H(m)+xr)k^{−1}\mod q
s≡(H(m)+xr)k−1modq
签名结果为 (r,s)。需要注意的是这里与 Elgamal 很重要的不同是这里使用了哈希函数对消息进行了哈希处理。
验证
验证过程如下 - 计算辅助值 w = s − 1 m o d q w=s^{−1}\mod q w=s−1modq
- 计算辅助值 u 1 = H ( m ) s − 1 m o d q u_1=H(m)s^{−1}\mod q u1=H(m)s−1modq
- 计算辅助值 u 2 = r s − 1 m o d q u2=rs^{-1}\mod q u2=rs−1modq
- 计算 v = ( g u 1 y u 2 m o d p ) m o d q v=(g^{u_1}y^{u_2}\mod p)\mod q v=(gu1yu2modp)modq
- 如果 v 与 r 相等则校验成功。
正确性推导
首先g 满足
g
k
≡
1
m
o
d
p
g^k≡1\mod p
gk≡1modp 的最小正整数 k 为 q。所以
g
q
≡
1
m
o
d
p
g^q≡1\mod p
gq≡1modp。
所以
g
x
≡
(
g
x
m
o
d
q
)
m
o
d
p
g^x≡(g^x\mod q)\mod p
gx≡(gxmodq)modp 。进而
v
=
(
g
u
1
y
u
2
m
o
d
p
)
m
o
d
q
=
g
u
1
g
x
u
2
≡
g
H
(
m
)
s
−
1
g
x
r
s
−
1
≡
g
(
H
(
m
)
+
x
r
)
s
−
1
≡
g
k
v=(g^{u1}y^{u_2}\mod p)\mod q =g^{u_1}g^{xu_2}≡g^{H(m)s^{-1}}g^{xrs^{-1}}≡g^{(H(m)+xr)s^{-1}} ≡g^k
v=(gu1yu2modp)modq=gu1gxu2≡gH(m)s−1gxrs−1≡g(H(m)+xr)s−1≡gk
安全性
如果知道了随机密钥 k那么我们就可以根据
s
≡
(
H
(
m
)
+
x
r
)
k
−
1
m
o
d
q
s≡(H(m)+xr)k^{−1}\mod q
s≡(H(m)+xr)k−1modq 计算私钥 d几乎攻破了 DSA。
这里一般情况下消息的 hash 值都会给出。
x
≡
r
−
1
(
k
s
−
H
(
m
)
)
m
o
d
q
x≡r^{−1}(ks−H(m))\mod q
x≡r−1(ks−H(m))modq
题目
题目大部分都是基于上面那个式子进行各种数学关系推导最后求x
DSA本身是基于离散岁数问题的困难性设计的所以曾经尝试过用discrete_log但失败了
[Imaginaryctf round30]Easy DSA: The beginning
from Crypto.Util.Padding import pad
from Crypto.Util.number import isPrime, getPrime, long_to_bytes
from Crypto.Cipher import AES
from hashlib import sha256
from random import randrange
def gen_key():
p = 0
while not isPrime(p):
q = getPrime(300)
p = 2*q + 1
g = randrange(2, p)**2 % p
k = randrange(2, q)
x = randrange(2, q)
y = pow(g, x, p)
return p, q, g, x, y, k
def H(msg):
return int.from_bytes(sha256(msg).digest(), 'big')
def sign(m):
r = pow(g, k, p) % q
s = (H(m) + x*r) * pow(k, -1, q) % q
return r, s
def verify(m, r, s):
assert 0 < r < q and 0 < s < q
u = pow(s, -1, q)
v = pow(g, H(m) * u, p) * pow(y, r * u, p) % p % q
return v == r
flag = b"ictf{REDACTED}"
p, q, g, x, y, k = gen_key()
ms = b"jctf{powered_by_caffeine}", b"jctf{totally_real_flag}"
sigs = [sign(m) for m in ms]
assert all(verify(m, *sig) for m, sig in zip(ms, sigs))
aes = AES.new(long_to_bytes(x)[:16], AES.MODE_CBC, b'\0'*16)
c = aes.encrypt(pad(flag, 16)).hex()
解析
1.根据题目我们首先将所求结果转化为求x
2.根据p我们可以先求出q
3.我们知道 s k = H ( m ) + x r m o d p sk=H(m)+xr \mod p sk=H(m)+xrmodp
4.题目已知 s , H ( m ) , r s,H(m),r s,H(m),r也就是下面我们只用求出 k k k
5.通过已知的两组 s , m s,m s,m相减得到 k ( s 0 − s 1 ) = H ( m 0 ) − H ( m 1 ) ( 两次的 r , x 的值相同同相减时抵消 ) k(s_0-s_1)=H(m_0)-H(m_1)(两次的r,x的值相同同相减时抵消) k(s0−s1)=H(m0)−H(m1)(两次的r,x的值相同同相减时抵消)
6.求出 k k k直接求 x x x
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
p = 2187927460624367866053138955407692648682473743053236246707558906253741042480006602164664427
g = 375559713231366027661456501312210678588547344177468345614581736759352578046940519482449005
y = 1485107098193369513854775432342726913250546508148678604594096036026212707003506931382110518
ms = (b'jctf{powered_by_caffeine}', b'jctf{totally_real_flag}')
sigs = [(584760320483109456978677291524162809623560744424005784846002481292183647634857441612413242, 43566017108108194938809536454030127793515021629016835721136006757000695802735201944729583), (584760320483109456978677291524162809623560744424005784846002481292183647634857441612413242, 587754055422977160798386807229397695762555861352726788417293238718373985110611538922057038)]
c = '614585db552484e4c81c4168afa8582bd975bfadd5edc8a4d1bf744c29a7d84f30cde5fe4b37f736af3f09480bcb626a'
q = (p-1)//2
hm = [int.from_bytes(sha256(ms[i]).digest(), 'big') for i in range(len(ms))]
r = [sigs[i][0] for i in range(len(sigs))]
s = [sigs[i][1] for i in range(len(sigs))]
k = (hm[0]-hm[1])*inverse(s[0]-s[1],q)
x = (s[0]*k-hm[0])*inverse(r[0],q)%q
aes = AES.new(long_to_bytes(x)[:16], AES.MODE_CBC, b'\0'*16)
f = aes.decrypt(long_to_bytes(int(c,16)))
print(f.decode())
[Imaginaryctf round30]Easy DSA: Elated once.py
from Crypto.Util.Padding import pad
from Crypto.Util.number import isPrime, getPrime, long_to_bytes
from Crypto.Cipher import AES
from hashlib import sha256
from random import randrange
def H(msg):
return int.from_bytes(sha256(msg).digest(), 'big')
def gen_key():
p = 0
while not isPrime(p):
q = getPrime(300)
p = 2*q + 1
g = randrange(2, p)**2 % p
x = randrange(2, q)
y = pow(g, x, p)
return p, q, g, x, y
def gen_nonces():
a = randrange(2, q)
b = randrange(2, q)
k = 0
while 1:
k = (a*k + b) % q
yield k
def sign(m):
k = next(nonces)
r = pow(g, k, p) % q
s = (H(m) + x*r) * pow(k, -1, q) % q
return r, s
def verify(m, r, s):
assert 0 < r < q and 0 < s < q
u = pow(s, -1, q)
v = pow(g, H(m) * u, p) * pow(y, r * u, p) % p % q
return v == r
flag = b"ictf{REDACTED}"
p, q, g, x, y = gen_key()
nonces = gen_nonces()
ms = b'jctf{f4k3_f!4g_7h3_f1r57}', b'jctf{f4k3_f!4g_7h3_53c0nd}', b'jctf{f4k3_f!4g_7h3_7h1rd}'
sigs = [sign(m) for m in ms]
assert all(verify(m, *sig) for m, sig in zip(ms, sigs))
aes = AES.new(long_to_bytes(x)[:16], AES.MODE_CBC, b'\0'*16)
c = aes.encrypt(pad(flag, 16)).hex()
print(f'{p = }\n{g = }\n{y = }\n{ms = }\n{sigs = }\n{c = }')
解析
s
=
(
H
(
m
)
+
x
r
)
∗
k
−
1
m
o
d
q
⇒
x
=
(
s
k
−
H
(
m
)
)
∗
r
−
1
m
o
d
q
s=(H(m)+xr)*k^{-1} \mod q \Rightarrow x =(sk-H(m))*r^{-1} \mod q
s=(H(m)+xr)∗k−1modq⇒x=(sk−H(m))∗r−1modq
联立得到
s
1
r
1
−
1
k
1
−
H
(
m
1
)
∗
r
1
−
1
≡
s
2
r
2
−
1
k
2
−
H
(
m
2
)
∗
r
2
−
1
≡
s
3
r
3
−
1
k
3
−
H
(
m
3
)
∗
r
3
−
1
≡
x
m
o
d
q
s_1r_1^{-1}k_1-H(m_1)*r_1^{-1}\equiv s_2r_2^{-1}k_2-H(m_2)*r_2^{-1}\equiv s_3r_3^{-1}k_3-H(m_3)*r_3^{-1}\equiv x \mod q
s1r1−1k1−H(m1)∗r1−1≡s2r2−1k2−H(m2)∗r2−1≡s3r3−1k3−H(m3)∗r3−1≡xmodq
设
u
i
=
s
i
r
i
−
1
,
v
i
=
−
H
(
m
i
)
r
i
−
1
u_i=s_ir_i^{-1},v_i=-H(m_i)r_i^{-1}
ui=siri−1,vi=−H(mi)ri−1
u
1
k
1
+
v
1
≡
u
2
k
2
+
v
2
≡
u
3
k
3
+
v
3
≡
x
m
o
d
q
u_1k_1+v_1 \equiv u_2k_2+v_2 \equiv u_3k_3+v_3 \equiv x \mod q
u1k1+v1≡u2k2+v2≡u3k3+v3≡xmodq
由
k
1
=
b
,
k
2
=
(
a
+
1
)
b
,
k
3
=
(
a
2
+
a
+
1
)
b
k_1 = b,k_2 = (a+1)b,k_3 = (a^2+a+1)b
k1=b,k2=(a+1)b,k3=(a2+a+1)b
仅考虑mod q域下的得到
{
u
1
b
+
v
1
=
(
u
2
a
+
u
2
)
b
+
v
2
u
1
b
+
v
1
=
(
u
3
a
2
+
u
3
a
+
u
3
)
b
+
v
3
\left\{ \begin{matrix} u_1b+v_1=(u_2a+u_2)b+v_2 \\ u_1b+v_1=(u_3a^2+u_3a+u_3)b+v_3 \end{matrix} \right.
{u1b+v1=(u2a+u2)b+v2u1b+v1=(u3a2+u3a+u3)b+v3
整理得
{
v
1
−
v
2
=
(
u
2
a
+
u
2
−
u
1
)
b
v
1
−
v
3
=
(
u
3
a
2
+
u
3
a
+
u
3
−
u
1
)
b
\left\{ \begin{matrix} v_1-v_2=(u_2a+u_2-u_1)b \\ v_1-v_3=(u_3a^2+u_3a+u_3-u_1)b \end{matrix} \right.
{v1−v2=(u2a+u2−u1)bv1−v3=(u3a2+u3a+u3−u1)b
从而
(
v
1
−
v
3
)
(
u
2
a
+
u
2
−
u
1
)
=
(
u
3
a
2
+
u
3
a
+
u
3
−
u
1
)
b
(
u
2
a
+
u
2
−
u
1
)
=
(
u
3
a
2
+
u
3
a
+
u
3
−
u
1
)
(
v
1
−
v
2
)
(v_1-v_3)(u_2a+u_2-u_1)=(u_3a^2+u_3a+u_3-u_1)b(u_2a+u_2-u_1)=(u_3a^2+u_3a+u_3-u_1)(v_1-v_2)
(v1−v3)(u2a+u2−u1)=(u3a2+u3a+u3−u1)b(u2a+u2−u1)=(u3a2+u3a+u3−u1)(v1−v2)
(
v
1
−
v
3
)
u
2
a
+
(
v
1
−
v
3
)
(
u
2
−
u
1
)
=
(
v
1
−
v
2
)
u
3
a
2
+
(
v
1
−
v
2
)
u
3
a
+
(
u
3
−
u
1
)
(
v
1
−
v
2
)
(v_1-v_3)u_2a + (v_1-v_3)(u_2-u_1) =(v_1-v_2)u_3a^2+(v_1-v_2)u_3a+(u_3-u_1)(v_1-v_2)
(v1−v3)u2a+(v1−v3)(u2−u1)=(v1−v2)u3a2+(v1−v2)u3a+(u3−u1)(v1−v2)
(
v
1
−
v
2
)
u
3
a
2
+
[
(
v
1
−
v
2
)
u
3
−
(
v
1
−
v
3
)
u
2
]
a
+
[
(
u
3
−
u
1
)
(
v
1
−
v
2
)
−
(
v
1
−
v
3
)
(
u
2
−
u
1
)
]
=
0
(v_1-v_2)u_3a^2+[(v_1-v_2)u_3-(v_1-v_3)u_2]a+[(u_3-u_1)(v_1-v_2)-(v_1-v_3)(u_2-u_1)]=0
(v1−v2)u3a2+[(v1−v2)u3−(v1−v3)u2]a+[(u3−u1)(v1−v2)−(v1−v3)(u2−u1)]=0
设三个系数分别为
w
1
,
w
2
,
w
3
w_1,w_2,w_3
w1,w2,w3
下面只用求解
w
1
a
2
+
w
2
a
+
w
3
=
0
m
o
d
q
w_1a^2+w_2a+w_3=0 \mod q
w1a2+w2a+w3=0modq
求出a后
b
=
(
v
1
−
v
2
)
(
u
2
a
+
u
2
−
u
1
)
−
1
b=(v_1-v_2)(u_2a+u_2-u_1)^{-1}
b=(v1−v2)(u2a+u2−u1)−1
⇒
x
=
u
1
b
+
v
1
\Rightarrow x = u_1b+v_1
⇒x=u1b+v1
#sage
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
def H(msg):
return int.from_bytes(sha256(msg).digest(), 'big')
p = 2418412161587048618911490514475907960012278945420538846001723790372197085472346428648374919
q = (p - 1) // 2
g = 2064228484934656182476030526252687681657855524182393204180796682805474532697783234019522938
y = 894978350337386203714743526086207453830598544444498469056621877210054843512079994718204008
ms = (b'jctf{f4k3_f!4g_7h3_f1r57}', b'jctf{f4k3_f!4g_7h3_53c0nd}', b'jctf{f4k3_f!4g_7h3_7h1rd}')
sigs = [(942248975683680318753150798164591935683431794761521087381578596465811760180113404300321118, 342812233069446068155480770741216218496427109436740920046532418711028275917065308430519273), (102001584770818641493080724572692756389337862746330230381962190229233871531362789283064508, 482354383195776716833349859090850583242412163611214463003633128285976770958780493119871011), (187377473811032611481162139226326301755478417757273410261128557099065854699728324076093828, 1171449558094661271371246349171199670184901923277811515634255397001853557943612820379515494)]
c = '4c76bd5dc8d57984526385d696fa0665e4c18f60b8593d42897aff792ec893d826c253646b9cb6875c91f2dfa25eedd4cc2936a3fe3174aa5b677a30ef965a7aa5dbf12c0c8234a73d0c5db5aea76644'
m = [H(i) for i in ms]
r = [i[0] for i in sigs]
s = [i[1] for i in sigs]
inv_r = [inverse(i,q) for i in r]
u = [s[i] * inv_r[i] % q for i in range(3)]
v = [-m[i] * inv_r[i] % q for i in range(3)]
w1 = (v[0]-v[1]) * u[2] % q
w2 = ((v[0]-v[1])*u[2] - (v[0]-v[2])*u[1]) % q
w3 = ((u[2]-u[0])*(v[0]-v[1]) - (v[0]-v[2])*(u[1]-u[0])) % q
R.<x> = Zmod(q)[]
f = w1*x^2 + w2*x +w3
roots = f.roots()
la = [int(i[0]) for i in roots]
for a in la:
b = inverse(u[1]*a+u[1]-u[0],q)*(v[0]-v[1]) % q
k = [b,(a*b+b)%q,((a*b+b)*a+b)%q]
x = (u[0]*b + v[0]) % q
aes = AES.new(long_to_bytes(x)[:16], AES.MODE_CBC, b'\0'*16)
flag = aes.decrypt(long_to_bytes(int(c,16)))
print(flag)
offical solve
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from hashlib import sha256
from sage.all import GF
def H(msg):
return int.from_bytes(sha256(msg).digest(), 'big')
def gen_nonces():wo
k = 0
while 1:
k = (a*k + b) % q
yield k
with open('out.txt', 'r') as file:
exec(file.read())
p: int
g: int
y: int
c: int
ms: list[bytes]
sigs: list[tuple[int, int]]
q = (p-1)//2
K = GF(q)['a,b,x']
a, b, x = K.gens()
polys = [s*k - H(m) - x*r for m, k, (r, s) in zip(ms, gen_nonces(), sigs)]
for sols in K.ideal(polys).variety():
X = int(sols[x])
aes = AES.new(long_to_bytes(X)[:16], AES.MODE_CBC, b'\0'*16)
m = aes.decrypt(bytes.fromhex(c))
print(m)