DSA笔记

基本原理

密钥生成

1. 选择一个合适的哈希函数，目前一般选择 SHA1，当前也可以选择强度更高的哈希函数 H。
2. 选择密钥的长度 L 和 N，这两个值决定了签名的安全程度。在最初的 DSS（ Digital Signature Standard ）中建议 L 必须为 64 的倍数，并且 $512\le L\le 1024$ ，当然，也可以更大。N 大小必须不大于哈希函数 H 输出的长度。FIPS 186-3 给出了一些建议的 L 和 N 的取值例子：(1024, 160)， (2048, 224)， (2048, 256)，以及 (3,072, 256)。
3. 选择 N 比特的素数 q。
4. 选择 L 比特的素数 p，使得 p-1 是 q 的倍数。
5. 选择满足 $g^k\equiv 1\mathrm{mod}p$ 的最小正整数 k 为 q 的 g，即在模 p 的背景下，ord(g)=q 的 g。即 g 在模 p 的意义下，其指数次幂可以生成具有 q 个元素的子群。这里，我们可以通过计算 $g=h^{\frac{p-1}{q}}\mathrm{mod}p$ 来得到 g，其中 1<h<p−1 。
6. 选择私钥 x， 0<x<q ，计算 $y\equiv g^x\mathrm{mod}p$ ,公钥为 (p,q,g,y)，私钥为 (x)。
   签名
   签名步骤如下
7. 选择随机整数数 k 作为临时密钥， 0<k<q 。
8. 计算 $r\equiv (g^k\mathrm{mod}p)\mathrm{mod}q$
9. 计算 $s\equiv (H(m)+xr)k^{-1}\mathrm{mod}q$
   签名结果为 (r,s)。需要注意的是，这里与 Elgamal 很重要的不同是这里使用了哈希函数对消息进行了哈希处理。
   验证
   验证过程如下
10. 计算辅助值， $w=s^{-1}\mathrm{mod}q$
11. 计算辅助值， $u_1=H(m)s^{-1}\mathrm{mod}q$
12. 计算辅助值， $u2=r{s}^{-1}\mathrm{mod}q$
13. 计算 $v=(g^{u_1}{y}^{u_2}\mathrm{mod}p)\mathrm{mod}q$
14. 如果 v 与 r 相等，则校验成功。

正确性推导

首先，g 满足 $g^k\equiv 1\mathrm{mod}p$ 的最小正整数 k 为 q。所以 $g^q\equiv 1\mathrm{mod}p$。
所以$g^x\equiv (g^x\mathrm{mod}q)\mathrm{mod}p$ 。进而
$v=(g^{u1}{y}^{u_2}\mathrm{mod}p)\mathrm{mod}q=g^{u_1}{g}^{x{u}_2}\equiv g^{H(m)s^{-1}}{g}^{xr{s}^{-1}}\equiv g^{(H(m)+xr)s^{-1}}\equiv g^k$

安全性

如果知道了随机密钥 k，那么我们就可以根据 $s\equiv (H(m)+xr)k^{-1}\mathrm{mod}q$ 计算私钥 d，几乎攻破了 DSA。
这里一般情况下，消息的 hash 值都会给出。
$x\equiv r^{-1}(ks-H(m))\mathrm{mod}q$

题目

题目大部分都是基于上面那个式子进行各种数学关系推导，最后求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''*16)
c = aes.encrypt(pad(flag, 16)).hex()

解析

1.根据题目我们首先将所求结果转化为求x
2.根据p我们可以先求出q
3.我们知道$sk=H(m)+xr\mathrm{mod}p$
4.题目已知$s,H(m),r$，也就是下面我们只用求出$k$
5.通过已知的两组$s,m$相减得到$k(s_0-s_1)=H(m_0)-H(m_1)(两次的r,x的值相同，同相减时抵消)$
6.求出$k$，直接求$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''*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''*16)
c = aes.encrypt(pad(flag, 16)).hex()
print(f'{p = }n{g = }n{y = }n{ms = }n{sigs = }n{c = }')

解析

$s=(H(m)+xr)\ast k^{-1}\mathrm{mod}q\Rightarrow x=(sk-H(m))\ast r^{-1}\mathrm{mod}q$
联立得到$$s_1{r}_1^{-1}{k}_1-H(m_1)\ast r_1^{-1}\equiv s_2{r}_2^{-1}{k}_2-H(m_2)\ast r_2^{-1}\equiv s_3{r}_3^{-1}{k}_3-H(m_3)\ast r_3^{-1}\equiv x\mathrm{mod}q$$
设$u_i=s_i{r}_i^{-1},v_i=-H(m_i)r_i^{-1}$
$u_1{k}_1+v_1\equiv u_2{k}_2+v_2\equiv u_3{k}_3+v_3\equiv x\mathrm{mod}q$
由$k_1=b,k_2=(a+1)b,k_3=(a^2+a+1)b$
仅考虑mod q域下的得到$$\{\begin{array}{c}{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\end{array}$$
整理得$$\{\begin{array}{c}{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\end{array}$$
从而$$(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_{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_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$$
设三个系数分别为$w_1,w_2,w_3$
下面只用求解$w_1{a}^2+w_{2}a+w_3=0\mathrm{mod}q$
求出a后$b=(v_1-v_2)(u_{2}a+u_2-u_1{)}^{-1}$
$\Rightarrow x=u_{1}b+v_1$

#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''*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''*16)
m = aes.decrypt(bytes.fromhex(c))
print(m)

最后

以上就是雪白发夹为你收集整理的DSA笔记的全部内容，希望文章能够帮你解决DSA笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。