闽盾杯
DDSA
已知条件
\[ s = m * (H(m) + pri*r) \pmod{q} \]
\[ s,H(m),r,q已知 \\ pri \ 384bits \]
变换一下
\[ s*H(m)^{-1}-m*pri*r*H(m)^{-1} = m \pmod{q} \]
\[ -A*m*pri + B = m \pmod{q} \]
两个短向量随便造格子都能出了
形式出来了，开始构造
\(\Rightarrow -m*pri*r*H(m)^{-1}+s*H(m)^{-1} = m \pmod{q}\)
\(A = -r*H(m)^{-1}\)
\(B = s*H(m)^{-1}\)
$x = m*pri $
\(\Rightarrow A*x + B = m \pmod{q}\)
格
\[ \left[ \begin{matrix} k & x & 1 \end{matrix}\right] * \left[ \begin{matrix} q &\ &\ \\ A & 2^{512+384}/2^{1024} &\ \\ B & \ & 2^{512} \end{matrix} \right] = \left[ \begin{matrix} m & x*2^{128} & 2^{512} \end{matrix}\right] \]
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
prime_p = 254843759712120770192107797102254314236912507988317949449773952808056853528137124034192193635099026436082859359975257478069529928753465466553898924428657727410192480025664330547720267491593689914315716652925690802124634579341155119238992435231736067051804606192447508930100501670982605518547228404550199336703
prime_q = 127421879856060385096053898551127157118456253994158974724886976404028426764068562017096096817549513218041429679987628739034764964376732733276949462214328863705096240012832165273860133745796844957157858326462845401062317289670577559619496217615868033525902303096223754465050250835491302759273614202275099668351
generator = 2
public_key = 131245100806313704109021983074816599799682611494124396700782287771480754767743274332741691780892425776722031868255191511222923419219426668626610194783198536014535188970081526577455228295158537145302145709999296345285722858516138341483834025451192165201091236688861670956465115266216945667106331802578702665225
# FLAG= *******************************
hash_value = '46938c7a601182d1df4b9d4a37c17580cfb970c4af7fca6451072f41a5a7065e'
value_r = 96111884388209390044721391857919611346233727898283099068195168118214413138594366255890654775089993119902756462947320027269335626696419779929364994151712885070079726142910724828860334861711912069256665505694001037628060332964882837869076589261126127624577428334370787070801689103729844552184001135328855648606
value_s = 63884781766257658578267883651422406359479884571734348903725487663536666209937842147795563957389353456276674251015988781336376204887566497402098320197366964806927971926305174200837205721424687069413674291833091050243279573371152886068515117170513462518215796377546279552663334023595846897966836811639127624873
hash_value = ZZ(hash_value,16)
A = -value_r*inverse(hash_value,prime_q)%prime_q
B = value_s*inverse(hash_value,prime_q)%prime_q
mat = [[prime_q,0,0],[A,2^(512+384)/2^1024,0],[B,0,2^512]]
M = Matrix(mat)
hh = M.LLL()
print(hh)
m = hh[2][0]
flag = n2s(int(m))
print(flag)
#b'flag{92f63c4190}'
