DSA 题，共享 k 攻击。
首先清楚DSA中的几个变量，p，q，g，x，y。根据定义，(p, q, g, y)组成公钥，公钥是在模 p 体系下的。
还有变量 m，k，r，s，以及hash加密函数H( )。其中:
r = (g ^ k mod p) mod q
s = k^(-1) * (H(m) + xr) mod q
根据定义，(m, r, s)组成签名，签名是在模 q 体系下的。
然后理解一波共享 k 攻击的原理，这种攻击的前提是：在公钥相同的两次签名中共享了 k。

假设有公钥相同的两次加密结果，已知k相同，由于r = (g ^ k mod p) mod q，所以 r1 = r2。然后又有：
s1 = k^(-1) * (H(m1) + xr) mod q
s2 = k^(-1) * (H(m2) + xr) mod q
变换可以得到：
s1 * k ≡ H(m1) + xr (mod q)
s2 * k ≡ H(m2) + xr (mod q)
两式可以相减，得到：
k * (s1 - s2) ≡ H(m1) - H(m2) (mod q)
最终得：
k = (H(m1) - H(m2)) * (s1 - s2)^(-1) mod q
接着求x，
已知：s1 ≡ k^(-1) * (H(m1) + xr) (mod q)，所以有：s1 * k ≡ H(m1) + xr (mod q)
最终化简得：
x = ((s1 * k -H(m1)) * r ^ (-1)) mod q

在 12 次加密中出现了四组共享k的情况，选出其中一组计算得到k，x。这题的 hash 加密函数H( )是 md5，然后利用 s = k^(-1) * (H(m) + xr) mod q 伪造签名即可。
flag 为 flag{Wh4t_a_Prety_Si3nature!}。